1 kkz 1.1 // PointsToQuadVisitor.java, created Sat Jul 13 17:33:45 2002 by kkz
2 kkz 1.1 // Copyright (C) 2000 Karen Zee <kkz@tmi.lcs.mit.edu>
3 kkz 1.1 // Licensed under the terms of the GNU GPL; see COPYING for details.
4 kkz 1.1 package harpoon.Analysis.PreciseGC;
5 kkz 1.1
6 kkz 1.1 import harpoon.ClassFile.HClass;
7 kkz 1.1 import harpoon.ClassFile.HCode;
8 kkz 1.1 import harpoon.ClassFile.HCodeAndMaps;
9 kkz 1.1 import harpoon.ClassFile.HCodeFactory;
10 kkz 1.1 import harpoon.ClassFile.HConstructor;
11 kkz 1.1 import harpoon.ClassFile.HMethod;
12 kkz 1.1 import harpoon.ClassFile.Linker;
13 kkz 1.1 import harpoon.IR.Properties.CFGEdge;
14 kkz 1.1 import harpoon.IR.Quads.ANEW;
15 kkz 1.1 import harpoon.IR.Quads.ARRAYINIT;
16 kkz 1.1 import harpoon.IR.Quads.ASET;
17 kkz 1.1 import harpoon.IR.Quads.CALL;
18 kkz 1.1 import harpoon.IR.Quads.Code;
19 kkz 1.1 import harpoon.IR.Quads.Edge;
20 kkz 1.1 import harpoon.IR.Quads.FOOTER;
21 kkz 1.1 import harpoon.IR.Quads.HEADER;
22 kkz 1.1 import harpoon.IR.Quads.METHOD;
23 kkz 1.1 import harpoon.IR.Quads.MOVE;
24 kkz 1.1 import harpoon.IR.Quads.NEW;
25 kkz 1.1 import harpoon.IR.Quads.PHI;
26 kkz 1.1 import harpoon.IR.Quads.Quad;
27 kkz 1.1 import harpoon.IR.Quads.QuadFactory;
28 kkz 1.1 import harpoon.IR.Quads.RETURN;
29 kkz 1.1 import harpoon.IR.Quads.SET;
30 kkz 1.1 import harpoon.IR.Quads.SIGMA;
31 kkz 1.1 import harpoon.IR.Quads.THROW;
32 kkz 1.1 import harpoon.Temp.Temp;
33 kkz 1.1 import harpoon.Util.Worklist;
34 kkz 1.1 import harpoon.Util.Collections.WorkSet;
35 kkz 1.1
36 kkz 1.1 import java.util.Collections;
37 kkz 1.1 import java.util.HashMap;
38 kkz 1.1 import java.util.HashSet;
39 kkz 1.1 import java.util.Iterator;
40 kkz 1.1 import java.util.Map;
41 kkz 1.1 import java.util.Set;
42 kkz 1.1
43 kkz 1.1 /**
44 kkz 1.1 * <code>PointsToQuadVisitor</code> performs local points to analysis,
45 kkz 1.1 * and can be subclassed for more specific purposes.
46 kkz 1.1 *
47 kkz 1.1 * @author Karen Zee <kkz@tmi.lcs.mit.edu>
48 kkz 1.1 * @version $Id: PointsToQuadVisitor.java,v 1.1 2002/07/18 21:06:00 kkz Exp $ */
49 kkz 1.1 public class PointsToQuadVisitor extends harpoon.IR.Quads.QuadVisitor {
50 kkz 1.1
51 kkz 1.1 private final boolean DEBUG1 = false;
52 kkz 1.1
53 kkz 1.1 protected final Worklist toDo = new WorkSet();
54 kkz 1.1 protected final Code code;
55 kkz 1.1
56 kkz 1.1 /** Creates a <code>PointsToQuadVisitor</code>. */
57 kkz 1.1 public PointsToQuadVisitor(Code code) {
58 kkz 1.1 this.code = code;
59 kkz 1.1 }
60 kkz 1.1
61 kkz 1.1 // map of CFGEdges to aliases (Sets of Temps)
62 kkz 1.1 protected final Map EdgeToTemps = new HashMap();
63 kkz 1.1
64 kkz 1.1 // Performs analysis with the given initial data flow fact for the
65 kkz 1.1 // entry point of the method.
66 kkz 1.1 protected void analyze(Set aliases) {
67 kkz 1.1 METHOD start = ((HEADER) code.getRootElement()).method();
68 kkz 1.1 assert start.nextLength() == 1;
69 kkz 1.1 // initialize dataflow facts
70 kkz 1.1 EdgeToTemps.put(start.nextEdge(0), aliases);
71 kkz 1.1 // initialize to-do list
72 kkz 1.1 toDo.push(start.next(0));
73 kkz 1.1 // go, gadget, go!
74 kkz 1.1 while(!toDo.isEmpty()) {
75 kkz 1.1 Quad q = (Quad) toDo.pull();
76 kkz 1.1 if (DEBUG1) System.out.println(q);
77 kkz 1.1 q.accept(this);
78 kkz 1.1 }
79 kkz 1.1 }
80 kkz 1.1
81 kkz 1.1 public void visit(CALL q) {
82 kkz 1.1 assert q.prevLength() == 1;
83 kkz 1.1 Set aliases = get(q.prevEdge(0));
84 kkz 1.1 // handle normal edge
85 kkz 1.1 Temp retval = q.retval();
86 kkz 1.1 if (retval != null)
87 kkz 1.1 aliases.remove(retval);
88 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), 0);
89 kkz 1.1 // handle exception edge
90 kkz 1.1 Temp retex = q.retex();
91 kkz 1.1 if (retex != null) {
92 kkz 1.1 aliases.remove(retex);
93 kkz 1.1 // if retex == null, then the CALL has only
94 kkz 1.1 // one outgoing edge (only happens in quad-
95 kkz 1.1 // with-try), so only handle exception edge
96 kkz 1.1 // if retex != null
97 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), 1);
98 kkz 1.1 }
99 kkz 1.1 }
100 kkz 1.1
101 kkz 1.1 public void visit(FOOTER q) { /* do nothing */ }
102 kkz 1.1
103 kkz 1.1 public void visit(MOVE q) {
104 kkz 1.1 assert q.prevLength() == 1 && q.nextLength() == 1;
105 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
106 kkz 1.1 if (aliases.contains(q.src()))
107 kkz 1.1 aliases.add(q.dst());
108 kkz 1.1 else
109 kkz 1.1 aliases.remove(q.dst());
110 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
111 kkz 1.1 }
112 kkz 1.1
113 kkz 1.1 public void visit (PHI q) {
114 kkz 1.1 // start with the first non-null edge
115 kkz 1.1 int i;
116 kkz 1.1 Set aliases = null;
117 kkz 1.1 for (i = 0; i < q.arity(); i++) {
118 kkz 1.1 aliases = get(q.prevEdge(i));
119 kkz 1.1 if (aliases != null) break;
120 kkz 1.1 }
121 kkz 1.1 if (aliases == null) {
122 kkz 1.1 raiseValue(q.nextEdge(0), null);
123 kkz 1.1 return;
124 kkz 1.1 }
125 kkz 1.1 Set renamed = new HashSet(aliases);
126 kkz 1.1 for (int j = 0 ; j < q.numPhis(); j++) {
127 kkz 1.1 // rename aliases as needed
128 kkz 1.1 Temp src = q.src(j, i);
129 kkz 1.1 // perform check on original set
130 kkz 1.1 // in case an alias has multiple
131 kkz 1.1 // renames
132 kkz 1.1 if (aliases.contains(src)) {
133 kkz 1.1 renamed.remove(src);
134 kkz 1.1 renamed.add(q.dst(j));
135 kkz 1.1 }
136 kkz 1.1 }
137 kkz 1.1 // handle rest of edges
138 kkz 1.1 for (i = i+1 ; i < q.arity(); i++) {
139 kkz 1.1 aliases = get(q.prevEdge(i));
140 kkz 1.1 if (aliases == null) continue;
141 kkz 1.1 Set renamed2 = new HashSet(aliases);
142 kkz 1.1 for(int j = 0; j < q.numPhis(); j++) {
143 kkz 1.1 // rename aliases as needed
144 kkz 1.1 Temp src = q.src(j, i);
145 kkz 1.1 // perform check on original set
146 kkz 1.1 // in case an alias has multiple
147 kkz 1.1 // renames
148 kkz 1.1 if (aliases.contains(src)) {
149 kkz 1.1 renamed2.remove(src);
150 kkz 1.1 renamed2.add(q.dst(j));
151 kkz 1.1 }
152 kkz 1.1 }
153 kkz 1.1 // since this is a must analysis,
154 kkz 1.1 // we use set intersection: keep
155 kkz 1.1 // only if present in both sets
156 kkz 1.1 renamed.retainAll(renamed2);
157 kkz 1.1 }
158 kkz 1.1 raiseValue(q.nextEdge(0), renamed);
159 kkz 1.1 }
160 kkz 1.1
161 kkz 1.1 public void visit(Quad q) {
162 kkz 1.1 assert q.prevLength() == 1 && q.nextLength() == 1;
163 kkz 1.1 Set aliases = new HashSet(get(q.prevEdge(0)));
164 kkz 1.1 // remove redefined aliases, if any
165 kkz 1.1 aliases.removeAll(q.defC());
166 kkz 1.1 raiseValue(q.nextEdge(0), aliases);
167 kkz 1.1 }
168 kkz 1.1
169 kkz 1.1 public void visit(SIGMA q) {
170 kkz 1.1 assert q.prevLength() == 1;
171 kkz 1.1 Set aliases = get(q.prevEdge(0));
172 kkz 1.1 // iterate over successor edges
173 kkz 1.1 for(int i = 0; i < q.nextLength(); i++)
174 kkz 1.1 handleSIGMAEdge(q, new HashSet(aliases), i);
175 kkz 1.1 }
176 kkz 1.1
177 kkz 1.1 // retreive dataflow fact for CFGEdge e
178 kkz 1.1 protected Set get(CFGEdge e) {
179 kkz 1.1 Set V = (Set) EdgeToTemps.get(e);
180 kkz 1.1 if (DEBUG1) {
181 kkz 1.1 if (V == null)
182 kkz 1.1 System.out.println("\tget: {*}");
183 kkz 1.1 else
184 kkz 1.1 System.out.println("\tget: " + V);
185 kkz 1.1 }
186 kkz 1.1 return V;
187 kkz 1.1 }
188 kkz 1.1
189 kkz 1.1 // update dataflow fact for CFGEdge e
190 kkz 1.1 protected void raiseValue(CFGEdge e, Set raised) {
191 kkz 1.1 if (DEBUG1) {
192 kkz 1.1 if (raised == null)
193 kkz 1.1 System.out.println("\traiseValue: {*}");
194 kkz 1.1 else
195 kkz 1.1 System.out.println("\traiseValue: " + raised);
196 kkz 1.1 }
197 kkz 1.1 // add successor to to-do list, if necessary
198 kkz 1.1 if (!EdgeToTemps.containsKey(e)/*never processed before*/||
199 kkz 1.1 !((Set) EdgeToTemps.get(e)).equals(raised)/*changed value*/) {
200 kkz 1.1 EdgeToTemps.put(e, raised);
201 kkz 1.1 toDo.push(e.to());
202 kkz 1.1 }
203 kkz 1.1 }
204 kkz 1.1
205 kkz 1.1 // handleSIGMAEdge handles the index'th outgoing edge of the
206 kkz 1.1 // SIGMA q, given the set of aliases on the incoming edge
207 kkz 1.1 // requires: aliases be a Set of Temps
208 kkz 1.1 // modifies: aliases
209 kkz 1.1 protected void handleSIGMAEdge(SIGMA q, Set aliases, int index) {
210 kkz 1.1 Set insert = new HashSet();
211 kkz 1.1 Set remove = new HashSet();
212 kkz 1.1 // iterate over sigma functions
213 kkz 1.1 for(int j = 0; j < q.numSigmas(); j++) {
214 kkz 1.1 Temp src = q.src(j);
215 kkz 1.1 if (aliases.contains(src)) {
216 kkz 1.1 insert.add(q.dst(j, index));
217 kkz 1.1 remove.add(src);
218 kkz 1.1 }
219 kkz 1.1 }
220 kkz 1.1 aliases.removeAll(remove);
221 kkz 1.1 aliases.addAll(insert);
222 kkz 1.1 raiseValue(q.nextEdge(index), aliases);
223 kkz 1.1 }
224 kkz 1.1 }