1 pnkfelix 1.1.2.1 // ReachingDefsCachingImpl.java, created Thu Jul 13 13:37:11 2000 by pnkfelix
2 cananian 1.1.2.3 // Copyright (C) 2000 Felix S. Klock II <pnkfelix@mit.edu>
3 pnkfelix 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 pnkfelix 1.1.2.1 package harpoon.Analysis;
5 pnkfelix 1.1.2.1
6 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCode;
7 pnkfelix 1.1.2.1 import harpoon.ClassFile.HCodeElement;
8 pnkfelix 1.1.2.1 import harpoon.IR.Properties.CFGrapher;
9 pnkfelix 1.1.2.1 import harpoon.IR.Properties.UseDefer;
10 pnkfelix 1.1.2.1 import harpoon.IR.Quads.TYPECAST;
11 pnkfelix 1.1.2.1 import harpoon.Temp.Temp;
12 pnkfelix 1.1.2.1
13 pnkfelix 1.1.2.2 import harpoon.Util.Util;
14 cananian 1.4 import net.cscott.jutil.BitSetFactory;
15 pnkfelix 1.1.2.1
16 pnkfelix 1.1.2.1 import java.util.Collection;
17 pnkfelix 1.1.2.1 import java.util.Collections;
18 pnkfelix 1.1.2.1 import java.util.Map;
19 pnkfelix 1.1.2.2 import java.util.HashMap;
20 pnkfelix 1.1.2.2 import java.util.List;
21 pnkfelix 1.1.2.1 import java.util.Set;
22 pnkfelix 1.1.2.2 import java.util.HashSet;
23 pnkfelix 1.1.2.1 import java.util.Iterator;
24 pnkfelix 1.1.2.1 import java.util.HashMap;
25 pnkfelix 1.1.2.1
26 pnkfelix 1.1.2.1 /**
27 pnkfelix 1.1.2.1 * <code>ReachingDefsCachingImpl</code> is an extension of
28 pnkfelix 1.1.2.1 * <code>ReachingDefsImpl</code> that keeps a BasicBlock local cache
29 pnkfelix 1.1.2.1 * mapping Temp:t -> HCodeElement:h -> Set:s where s is the result of
30 pnkfelix 1.1.2.1 * calling reachingDefs(h, t). This way repeated queries in the same
31 pnkfelix 1.1.2.1 * <code>BasicBlock</code> as the last query don't have to iterate
32 pnkfelix 1.1.2.1 * over all the statements in the BasicBlock again.
33 pnkfelix 1.1.2.1 *
34 cananian 1.1.2.3 * @author Felix S. Klock II <pnkfelix@mit.edu>
35 cananian 1.5 * @version $Id: ReachingDefsCachingImpl.java,v 1.5 2004/02/08 03:19:12 cananian Exp $
36 pnkfelix 1.1.2.1 */
37 cananian 1.2.2.1 public class ReachingDefsCachingImpl<HCE extends HCodeElement>
38 cananian 1.2.2.1 extends ReachingDefsAltImpl<HCE> {
39 pnkfelix 1.1.2.1
40 pnkfelix 1.1.2.1 /** Tracks the last basic block a query was done on. */
41 cananian 1.2.2.1 BasicBlock<HCE> lastBlock = null;
42 pnkfelix 1.1.2.1
43 pnkfelix 1.1.2.1 /** Maps Temp:t -> HCodeElement:h -> Set:s where s is the result
44 pnkfelix 1.1.2.1 of calling reachingDefs(h, t).
45 pnkfelix 1.1.2.1 */
46 cananian 1.2.2.1 Map<Temp,Map<HCE,Set<HCE>>> myCache;
47 pnkfelix 1.1.2.1
48 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsCachingImpl</code>. */
49 cananian 1.2.2.1 public ReachingDefsCachingImpl(HCode<HCE> hc) {
50 pnkfelix 1.1.2.1 super(hc);
51 pnkfelix 1.1.2.1 }
52 pnkfelix 1.1.2.1
53 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsCachingImpl</code>. */
54 cananian 1.2.2.1 public ReachingDefsCachingImpl(HCode<HCE> hc, CFGrapher<HCE> c) {
55 pnkfelix 1.1.2.1 super(hc, c);
56 pnkfelix 1.1.2.1 }
57 pnkfelix 1.1.2.1
58 pnkfelix 1.1.2.1 /** Creates a <code>ReachingDefsCachingImpl</code>. */
59 cananian 1.2.2.1 public ReachingDefsCachingImpl(HCode<HCE> hc, CFGrapher<HCE> c, UseDefer<HCE> ud) {
60 pnkfelix 1.1.2.1 super(hc, c, ud);
61 pnkfelix 1.1.2.1 }
62 pnkfelix 1.1.2.1
63 pnkfelix 1.1.2.1 /** Returns the Set of <code>HCodeElement</code>s providing definitions
64 pnkfelix 1.1.2.1 * of <code>Temp</code> <code>t</code> which reach
65 pnkfelix 1.1.2.1 * <code>HCodeElement</code> <code>hce</code>.
66 pnkfelix 1.1.2.1 */
67 cananian 1.2.2.1 public Set<HCE> reachingDefs(HCE hce, Temp t) {
68 pnkfelix 1.1.2.1 // find out which BasicBlock this HCodeElement is from
69 cananian 1.2.2.1 BasicBlock<HCE> b = bbf.getBlock(hce);
70 pnkfelix 1.1.2.1 if (b == lastBlock) {
71 pnkfelix 1.1.2.2 // System.out.print(" _"+b.statements().size());
72 pnkfelix 1.1.2.1 if (myCache.keySet().contains(t))
73 cananian 1.2.2.1 return myCache.get(t).get(hce);
74 pnkfelix 1.1.2.1 } else {
75 pnkfelix 1.1.2.2 // System.out.print(" M"+b.statements().size());
76 cananian 1.2.2.1 myCache = new HashMap<Temp,Map<HCE,Set<HCE>>>();
77 pnkfelix 1.1.2.2 lastBlock = b;
78 pnkfelix 1.1.2.1 }
79 pnkfelix 1.1.2.1
80 cananian 1.2.2.1 Map<HCE,Set<HCE>> hceToResults = new HashMap<HCE,Set<HCE>>();
81 pnkfelix 1.1.2.1 myCache.put(t, hceToResults);
82 pnkfelix 1.1.2.1
83 pnkfelix 1.1.2.1 // get the map for the BasicBlock
84 cananian 1.2.2.1 Record r = cache.get(b);
85 pnkfelix 1.1.2.2
86 pnkfelix 1.1.2.2 // find HCodeElements associated with `t' in the IN Set
87 pnkfelix 1.1.2.2 Set results = bsf.makeSet(r.IN);
88 cananian 1.2.2.1 results.retainAll( tempToAllDefs.get(t) );
89 pnkfelix 1.1.2.2
90 pnkfelix 1.1.2.2 Iterator pairs = results.iterator();
91 pnkfelix 1.1.2.2 results = new HashSet();
92 pnkfelix 1.1.2.2 while(pairs.hasNext()) {
93 pnkfelix 1.1.2.2 results.add( ((List)pairs.next()).get(1) );
94 pnkfelix 1.1.2.2 }
95 pnkfelix 1.1.2.2
96 pnkfelix 1.1.2.1 // propagate in Set through the HCodeElements
97 pnkfelix 1.1.2.1 // of the BasicBlock in correct order
98 pnkfelix 1.1.2.2 // report("Propagating...");
99 cananian 1.5 for(HCE curr : b.statements()) {
100 pnkfelix 1.1.2.1 hceToResults.put(curr, results);
101 pnkfelix 1.1.2.1
102 cananian 1.2.2.1 Collection<Temp> defC = null;
103 pnkfelix 1.1.2.1 // special treatment of TYPECAST
104 pnkfelix 1.1.2.1 if(check_typecast && (curr instanceof TYPECAST))
105 pnkfelix 1.1.2.1 defC = Collections.singleton(((TYPECAST)curr).objectref());
106 pnkfelix 1.1.2.1 else
107 pnkfelix 1.1.2.1 defC = ud.defC(curr);
108 pnkfelix 1.1.2.2
109 pnkfelix 1.1.2.1 if (defC.contains(t))
110 pnkfelix 1.1.2.2 results = Collections.singleton(curr);
111 pnkfelix 1.1.2.1 }
112 pnkfelix 1.1.2.1
113 cananian 1.2.2.1 return hceToResults.get(hce);
114 pnkfelix 1.1.2.1 }
115 cananian 1.2 }