1 cananian 1.1.2.1 // MustParamOracle.java, created Wed Nov 7 15:39:11 2001 by cananian
2 cananian 1.1.2.1 // 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.Quads;
5 cananian 1.1.2.1
6 cananian 1.1.2.2 import harpoon.ClassFile.HCode;
7 cananian 1.1.2.2 import harpoon.IR.Quads.HEADER;
8 cananian 1.1.2.2 import harpoon.IR.Quads.METHOD;
9 cananian 1.1.2.2 import harpoon.IR.Quads.MOVE;
10 cananian 1.1.2.2 import harpoon.IR.Quads.PHI;
11 cananian 1.1.2.2 import harpoon.IR.Quads.Quad;
12 cananian 1.1.2.2 import harpoon.IR.Quads.QuadVisitor;
13 cananian 1.1.2.2 import harpoon.IR.Quads.SIGMA;
14 cananian 1.1.2.2 import harpoon.Temp.Temp;
15 cananian 1.1.2.2 import harpoon.Util.Util;
16 cananian 1.1.2.1
17 cananian 1.1.2.2 import java.util.Arrays;
18 cananian 1.1.2.2 import java.util.HashMap;
19 cananian 1.1.2.2 import java.util.HashSet;
20 cananian 1.1.2.2 import java.util.Iterator;
21 cananian 1.1.2.2 import java.util.Map;
22 cananian 1.1.2.2 import java.util.Set;
23 cananian 1.1.2.1
24 cananian 1.1.2.1 /**
25 cananian 1.1.2.1 * A <code>MustParamOracle</code> tells you what method variables
26 cananian 1.1.2.1 * *must* contain the values passed in as parameters to the method.
27 cananian 1.1.2.1 * This can tell you which values must be the 'this' object, for
28 cananian 1.1.2.1 * non-static methods, or which values in (say) a field-set
29 cananian 1.1.2.1 * operation directly correspond to constructor parameters.
30 cananian 1.1.2.1 *
31 cananian 1.1.2.1 * @author C. Scott Ananian <cananian@alumni.princeton.edu>
32 cananian 1.4 * @version $Id: MustParamOracle.java,v 1.4 2002/04/10 03:00:59 cananian Exp $
33 cananian 1.1.2.1 */
34 cananian 1.1.2.1 public class MustParamOracle {
35 cananian 1.1.2.1 // could make this an invertibleMap if you want sets.
36 cananian 1.1.2.1 final Map results = new HashMap();
37 cananian 1.1.2.1
38 cananian 1.1.2.1 /** Returns <code>true</code> iff the given <code>Temp</code> *must*
39 cananian 1.1.2.1 * contain the value of some parameter. */
40 cananian 1.1.2.3 public boolean isMustParam(Temp t) { return results.containsKey(t); }
41 cananian 1.1.2.1 /** Returns the parameter which the given <code>Temp</code> *must*
42 cananian 1.1.2.1 * contain the value of. */
43 cananian 1.1.2.3 public int whichMustParam(Temp t) {
44 cananian 1.1.2.3 return ((Integer)results.get(t)).intValue();
45 cananian 1.1.2.3 }
46 cananian 1.1.2.4 public String toString() { return results.toString(); }
47 cananian 1.1.2.1
48 cananian 1.1.2.1 /** Creates a <code>MustParamOracle</code> which gives you information
49 cananian 1.1.2.1 * on variables in <code>HCode</code> <code>hc</code> (which should
50 cananian 1.1.2.1 * be in SSI or SSA form, for best results). */
51 cananian 1.1.2.1 public MustParamOracle(HCode hc) {
52 cananian 1.1.2.1 // compute # of method parameters
53 cananian 1.1.2.1 METHOD method = (METHOD) ((HEADER)hc.getRootElement()).next(1);
54 cananian 1.1.2.1 int nparam = method.paramsLength();
55 cananian 1.1.2.1 // for each parameter...
56 cananian 1.1.2.1 for (int i=0; i<nparam; i++) {
57 cananian 1.1.2.1 // do analysis.
58 cananian 1.1.2.1 OracleVisitor ov = new OracleVisitor(hc, i);
59 cananian 1.1.2.1 // transfer results into more compact form.
60 cananian 1.1.2.1 Integer paramNum = new Integer(i);
61 cananian 1.1.2.1 for (Iterator it=ov.paramvars.iterator(); it.hasNext(); ) {
62 cananian 1.1.2.1 Object old = results.put((Temp)it.next(), paramNum);
63 cananian 1.3.2.1 assert old==null : "temp can't be multiple params!";
64 cananian 1.1.2.1 }
65 cananian 1.1.2.1 // and do next.
66 cananian 1.1.2.1 }
67 cananian 1.1.2.1 // done!
68 cananian 1.1.2.1 }
69 cananian 1.1.2.1
70 cananian 1.1.2.1 static class OracleVisitor extends QuadVisitor {
71 cananian 1.1.2.1 final int which_param; // which parameter are we interested in?
72 cananian 1.1.2.1 /** an array of sets: one for each method parameter. the sets
73 cananian 1.1.2.1 * contain all variables which 'may' contain the method parameter. */
74 cananian 1.1.2.1 final Set paramvars = new HashSet();
75 cananian 1.1.2.1 /** an array of sets, as above. the sets in this case contain
76 cananian 1.1.2.1 * all variables which *may not* contain the method parameter. */
77 cananian 1.1.2.1 final Set notparamvars = new HashSet();
78 cananian 1.1.2.1 // the paramvars set minus the notparamvars set is the
79 cananian 1.1.2.1 // set of variables which *must* contain the method parameter.
80 cananian 1.1.2.1
81 cananian 1.1.2.1 /** The 'relevant' set consists of those quads which change the
82 cananian 1.1.2.1 * paramvars or notparamvars sets. We can save time in our
83 cananian 1.1.2.1 * dataflow analysis by only iterating over these. */
84 cananian 1.1.2.1 final Set relevant = new HashSet();
85 cananian 1.1.2.1
86 cananian 1.1.2.1 OracleVisitor(HCode hc, int which) {
87 cananian 1.1.2.1 this.which_param = which;
88 cananian 1.1.2.1 // once through all elements.
89 cananian 1.1.2.1 for (Iterator it=hc.getElementsI(); it.hasNext(); )
90 cananian 1.1.2.1 ((Quad)it.next()).accept(this);
91 cananian 1.1.2.1 // iterate through relevant elements until the sets stop
92 cananian 1.1.2.1 // changing size.
93 cananian 1.1.2.1 int oldsize = 0, size = paramvars.size() + notparamvars.size();
94 cananian 1.1.2.1 while (size > oldsize) {
95 cananian 1.1.2.1 for (Iterator it=relevant.iterator(); it.hasNext(); )
96 cananian 1.1.2.1 ((Quad)it.next()).accept(this);
97 cananian 1.1.2.1 oldsize = size;
98 cananian 1.1.2.1 size = paramvars.size() + notparamvars.size();
99 cananian 1.1.2.1 }
100 cananian 1.1.2.1 // clean up paramvars set by removing not-param variables.
101 cananian 1.1.2.1 paramvars.removeAll(notparamvars);
102 cananian 1.1.2.1 // done!
103 cananian 1.1.2.1 }
104 cananian 1.1.2.1 // lattice: don't know, this, not-this. -->move-->
105 cananian 1.1.2.1 // presence in 'not-this' overrides presence in 'this'.
106 cananian 1.1.2.1 // sets can only grow.
107 cananian 1.1.2.1 public void visit(Quad q) {
108 cananian 1.1.2.1 /* look for overwrites, which are always not 'this' */
109 cananian 1.1.2.1 notparamvars.addAll(q.defC());
110 cananian 1.1.2.1 }
111 cananian 1.1.2.1 public void visit(METHOD q) {
112 cananian 1.1.2.1 // param 'which' is 'param'; all others are 'not-param'
113 cananian 1.1.2.1 for (int i=0; i<q.paramsLength(); i++)
114 cananian 1.1.2.1 if (i==which_param)
115 cananian 1.1.2.1 paramvars.add(q.params(i));
116 cananian 1.1.2.1 else
117 cananian 1.1.2.1 notparamvars.add(q.params(i));
118 cananian 1.1.2.1 }
119 cananian 1.1.2.1 public void visit(MOVE q) {
120 cananian 1.1.2.1 relevant.add(q);
121 cananian 1.1.2.1 if (paramvars.contains(q.src()) &&
122 cananian 1.1.2.1 !notparamvars.contains(q.src()))
123 cananian 1.1.2.1 paramvars.add(q.dst());
124 cananian 1.1.2.1 else
125 cananian 1.1.2.1 notparamvars.add(q.dst());
126 cananian 1.1.2.1 }
127 cananian 1.1.2.1 public void visit(SIGMA q) {
128 cananian 1.1.2.1 relevant.add(q);
129 cananian 1.1.2.1 // get rid of overwrites.
130 cananian 1.1.2.1 Set s = new HashSet(q.defC());
131 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
132 cananian 1.1.2.1 s.removeAll(Arrays.asList(q.dst(i)));
133 cananian 1.1.2.1 notparamvars.addAll(s);
134 cananian 1.1.2.1 // now look for src==this.
135 cananian 1.1.2.1 for (int i=0; i<q.numSigmas(); i++)
136 cananian 1.1.2.1 if (notparamvars.contains(q.src(i)))
137 cananian 1.1.2.1 notparamvars.addAll(Arrays.asList(q.dst(i)));
138 cananian 1.1.2.1 else if (paramvars.contains(q.src(i)))
139 cananian 1.1.2.1 // found! add all dst to paramvars.
140 cananian 1.1.2.1 paramvars.addAll(Arrays.asList(q.dst(i)));
141 cananian 1.1.2.1 }
142 cananian 1.1.2.1 public void visit(PHI q) {
143 cananian 1.1.2.1 relevant.add(q);
144 cananian 1.1.2.1 // phi(x,y) is 'param' iff x *and* y are 'param' and
145 cananian 1.1.2.1 // neither x nor y is *not* 'param'
146 cananian 1.1.2.1 for (int i=0; i<q.numPhis(); i++)
147 cananian 1.1.2.1 for (int j=0; j<q.arity(); j++)
148 cananian 1.1.2.1 if (notparamvars.contains(q.src(i, j)))
149 cananian 1.1.2.1 notparamvars.add(q.dst(i));
150 cananian 1.1.2.1 else if (paramvars.contains(q.src(i, j)))
151 cananian 1.1.2.1 paramvars.add(q.dst(i));
152 cananian 1.1.2.1 }
153 cananian 1.1.2.1 }
154 cananian 1.2 }