1 cananian 1.1.2.1 // HoistingCheckOracle.java, created Sat Jan 13 14:45:14 2001 by cananian
2 cananian 1.1.2.7 // Copyright (C) 2000 C. Scott Ananian <cananian@alumni.princeton.edu>
3 cananian 1.1.2.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 cananian 1.1.2.1 package harpoon.Analysis.Transactions;
5 cananian 1.1.2.1
6 cananian 1.1.2.1 import harpoon.Analysis.DomTree;
7 cananian 1.1.2.1 import harpoon.ClassFile.HCode;
8 cananian 1.1.2.6 import harpoon.ClassFile.HCodeEdge;
9 cananian 1.1.2.1 import harpoon.ClassFile.HCodeElement;
10 cananian 1.1.2.6 import harpoon.IR.Properties.CFGrapher;
11 cananian 1.1.2.1 import harpoon.IR.Properties.UseDefer;
12 cananian 1.1.2.2 import harpoon.IR.Quads.MONITORENTER;
13 cananian 1.1.2.1 import harpoon.Temp.Temp;
14 cananian 1.1.2.1 import harpoon.Util.ArrayIterator;
15 cananian 1.5 import net.cscott.jutil.AggregateSetFactory;
16 cananian 1.5 import net.cscott.jutil.GenericMultiMap;
17 cananian 1.5 import net.cscott.jutil.MultiMap;
18 cananian 1.5 import net.cscott.jutil.SetFactory;
19 cananian 1.1.2.1
20 cananian 1.1.2.1 import java.util.Collection;
21 cananian 1.1.2.1 import java.util.Collections;
22 cananian 1.1.2.1 import java.util.Iterator;
23 cananian 1.1.2.1 import java.util.Set;
24 cananian 1.1.2.1 /**
25 cananian 1.1.2.1 * A <code>HoistingCheckOracle</code> tries to hoist and coalesce checks
26 cananian 1.1.2.3 * whenever possible. It improves on the results of a client
27 cananian 1.1.2.3 * <code>CheckOracle</code>.
28 cananian 1.1.2.1 * <p>
29 cananian 1.1.2.1 * The algorithm used is as follows: each check placed by the input
30 cananian 1.1.2.1 * oracle is moved to its immediate dominator iff that node is
31 cananian 1.1.2.1 * postdominated by the current node and that node is dominated by
32 cananian 1.1.2.1 * the definition of the variable referenced in the check. The
33 cananian 1.1.2.1 * process is repeated until no checks can be moved higher.
34 cananian 1.1.2.1 *
35 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
36 cananian 1.5 * @version $Id: HoistingCheckOracle.java,v 1.5 2004/02/08 01:54:21 cananian Exp $
37 cananian 1.1.2.1 */
38 cananian 1.3 // note: doesn't allow hoisting past sigmas. since input is SSA, this is
39 cananian 1.3 // fine. If you ever want to give it SSI instead, you should fix this.
40 cananian 1.1.2.3 class HoistingCheckOracle extends AnalysisCheckOracle {
41 cananian 1.1.2.1 /** Creates a <code>HoistingCheckOracle</code> for the given
42 cananian 1.1.2.1 * <code>HCode</code> which refines the checks placed by
43 cananian 1.1.2.1 * <code>CheckOracle</code> <code>co</code>. */
44 cananian 1.1.2.6 public HoistingCheckOracle(HCode hc, CFGrapher cfgr, UseDefer udr,
45 cananian 1.1.2.6 CheckOracle co) {
46 cananian 1.1.2.6 this(hc, cfgr, udr, new DomTree(hc, cfgr, false), co);
47 cananian 1.1.2.3 }
48 cananian 1.1.2.3 // separate constructor to let us reuse an existing domtree.
49 cananian 1.1.2.6 HoistingCheckOracle(HCode hc, CFGrapher cfgr, UseDefer udr,
50 cananian 1.1.2.6 DomTree dt, CheckOracle co) {
51 cananian 1.1.2.3 /* compute the proper check locations (post-order down dt) */
52 cananian 1.1.2.3 DomTree pdt = new DomTree(hc, true);
53 cananian 1.1.2.1 for (Iterator it=new ArrayIterator(dt.roots()); it.hasNext(); )
54 cananian 1.1.2.6 hoister((HCodeElement)it.next(), co, cfgr, udr, dt, pdt,
55 cananian 1.1.2.1 false/*can't hoist above root*/);
56 cananian 1.1.2.1 /* done! */
57 cananian 1.1.2.1 }
58 cananian 1.1.2.1
59 cananian 1.1.2.1 /* Returns checks which can be hoisted to immediate dominator */
60 cananian 1.1.2.6 CheckSet hoister(HCodeElement hce, CheckOracle co,
61 cananian 1.1.2.6 CFGrapher cfgr, UseDefer udr,
62 cananian 1.1.2.1 DomTree dt, DomTree pdt, boolean canHoist)
63 cananian 1.1.2.1 {
64 cananian 1.1.2.1 /* collect checks from dominated children and from check oracle */
65 cananian 1.1.2.3 CheckSet checks = new CheckSet(co, hce);
66 cananian 1.1.2.1 for (Iterator it=new ArrayIterator(dt.children(hce)); it.hasNext(); )
67 cananian 1.1.2.6 checks.addAll(hoister((HCodeElement)it.next(),
68 cananian 1.1.2.6 co, cfgr, udr, dt, pdt, true));
69 cananian 1.1.2.6 /** find common checks in successors. */
70 cananian 1.4 HCodeEdge[] succ = (HCodeEdge[]) cfgr.succC(hce).toArray(new HCodeEdge[0]);
71 cananian 1.1.2.6 CheckSet common = null; // will contain intersection of all succ. chks
72 cananian 1.1.2.6 for (int i=0; i<succ.length; i++) {
73 cananian 1.1.2.6 CheckSet scs = (CheckSet) results.get(succ[i].to());
74 cananian 1.1.2.6 if (scs==null) { common=null; break; /* bail out */}
75 cananian 1.1.2.6 if (common==null) common=new CheckSet(scs);
76 cananian 1.1.2.6 else {
77 cananian 1.1.2.6 scs = new CheckSet(scs);
78 cananian 1.1.2.6 scs.readVersions.addAll(scs.writeVersions);
79 cananian 1.1.2.6 common.retainAll(scs);
80 cananian 1.1.2.6 }
81 cananian 1.1.2.6 common.readVersions.addAll(common.writeVersions);
82 cananian 1.1.2.6 }
83 cananian 1.1.2.6 /** filter common checks */
84 cananian 1.1.2.6 if (hce instanceof MONITORENTER) common=null;
85 cananian 1.1.2.8 // XXX: common=null if hoisting past possible call to Object.wait().
86 cananian 1.1.2.6 if (common!=null) common.removeAll(udr.defC(hce));
87 cananian 1.1.2.6 /** steal filtered common checks from successors */
88 cananian 1.1.2.6 if (common!=null && !common.isEmpty()) {
89 cananian 1.1.2.6 System.err.println("HOISTING: "+common+" "+hce.getSourceFile());
90 cananian 1.1.2.6 for (int i=0; i<succ.length; i++) {
91 cananian 1.1.2.6 CheckSet scs = (CheckSet) results.get(succ[i].to());
92 cananian 1.1.2.6 scs.removeAll(common);
93 cananian 1.1.2.6 }
94 cananian 1.1.2.6 checks.addAll(common);
95 cananian 1.1.2.6 }
96 cananian 1.1.2.1 /** optimize: write versions are read versions */
97 cananian 1.1.2.1 checks.readVersions.removeAll(checks.writeVersions);
98 cananian 1.1.2.5 /** copy set of all checks. */
99 cananian 1.1.2.5 CheckSet nohoist = new CheckSet(checks);
100 cananian 1.1.2.1
101 cananian 1.1.2.1 /* can't hoist anything unless this==pidom(idom(this)) */
102 cananian 1.1.2.1 canHoist = canHoist && (hce == pdt.idom(dt.idom(hce)));
103 cananian 1.1.2.2 /* never hoist above a MONITORENTER */
104 cananian 1.1.2.2 canHoist = canHoist && !(dt.idom(hce) instanceof MONITORENTER);
105 cananian 1.1.2.5 /* okay, remove all if !canHoist */
106 cananian 1.1.2.5 if (!canHoist) checks.clear();
107 cananian 1.1.2.1
108 cananian 1.1.2.1 /* fetch the set of temps defined in our idom */
109 cananian 1.1.2.1 Collection idomDef = (dt.idom(hce)==null) ? Collections.EMPTY_SET :
110 cananian 1.1.2.1 udr.defC(dt.idom(hce)); /* defs in idom of this */
111 cananian 1.1.2.5 /* checks for a temp can't be hoisted above def */
112 cananian 1.1.2.5 checks.removeAll(idomDef);
113 cananian 1.1.2.5
114 cananian 1.1.2.5 /** leave checks here which we can't hoist. */
115 cananian 1.1.2.5 nohoist.removeAll(checks);
116 cananian 1.1.2.4 results.put(hce, nohoist);
117 cananian 1.1.2.1
118 cananian 1.1.2.1 /** give all of the rest of the checks to the idom */
119 cananian 1.1.2.1 return checks;
120 cananian 1.1.2.1 }
121 cananian 1.2 }