001 /* Copyright 2000, 2001, Compaq Computer Corporation */
002
003 package escjava.translate;
004
005
006 import java.util.Hashtable;
007 import java.util.Enumeration;
008
009 import javafe.ast.*;
010 import javafe.util.*;
011
012 import escjava.ast.*;
013 import escjava.ast.TagConstants;
014
015 /**
016 ** Infers more precise loop targets.
017 **
018 ** @author Cormac Flanagan
019 **/
020
021 public final class ATarget {
022 public GenericVarDecl x;
023 public Expr [] indices; // null if not loop invariant
024
025 private static Set targets;
026
027 public static Set compute(GuardedCmd gc) {
028 targets = new Set();
029 Hashtable env = new Hashtable();
030 Hashtable[] out = new Hashtable[2];
031 F( gc, env, out );
032 //System.out.println("atargets are " + targets.toString());
033 return targets;
034 }
035
036 private static Expr nonConst = LiteralExpr.make(TagConstants.INTLIT,
037 new Integer(0), Location.NULL);
038
039 ATarget(GenericVarDecl x, Expr [] indices) {
040 this.x = x;
041 this.indices = indices;
042 }
043
044 private static void addTarget( GenericVarDecl vd ) {
045 Expr [] indices = { };
046 addTarget(vd, indices);
047 }
048
049 private static void addTarget( GenericVarDecl vd, Expr index ) {
050 Expr [] indices = { index };
051 addTarget(vd, indices);
052 }
053
054 private static void addTarget( GenericVarDecl vd, Expr index1, Expr index2 ) {
055 Expr [] indices = { index1, index2 };
056 addTarget(vd, indices);
057 }
058
059 private static void addTarget( GenericVarDecl vd, Expr[] indices ) {
060 targets.add( new ATarget(vd, indices) );
061 }
062
063 public boolean equals(Object o) {
064 if( ! (o instanceof ATarget) ) return false;
065 ATarget t = (ATarget)o;
066 if( x != t.x ) return false;
067 for(int i=0; i<indices.length; i++) {
068 if( i >= t.indices.length ||
069 !(indices[i]==t.indices[i])) {
070 return false;
071 }
072 }
073 return true;
074 }
075
076 public int hashCode() {
077 return x.hashCode();
078 }
079
080 public static boolean mentions(Expr expr, Set s) {
081 if (expr instanceof VariableAccess) {
082 return s.contains(((VariableAccess) expr).decl);
083 } else {
084 for (int i = 0; i < expr.childCount(); i++) {
085 Object child = expr.childAt(i);
086 if (child instanceof Expr && mentions((Expr) child, s)) {
087 return true;
088 }
089 }
090 return false;
091 }
092 }
093
094 /* out[0] is normal, out[1] is exceptional.
095 out[i] may be null if no such exit possible.
096
097 call may mutate in.
098 Each Hashtable maps GenericVarDecls to
099 1) Expr, if var assigned a loop-invariant expr;
100 2) null, if variable loop-constant
101 3) nonConst, if variable not loop-invariant
102 */
103 private static void F(/*@ non_null */ GuardedCmd g, Hashtable in, Hashtable[] out) {
104
105 //System.out.println("F("+g+"), in = "+in);
106
107 Assert.notNull(g);
108 Assert.notNull(out);
109
110 out[0] = in;
111 out[1] = null;
112
113 if( in == null ) {
114 // this code unreachable
115 return;
116 }
117
118 switch (g.getTag()) {
119
120 case TagConstants.ASSERTCMD:
121 case TagConstants.ASSUMECMD:
122 case TagConstants.RESTOREFROMCMD:
123 case TagConstants.SKIPCMD:
124 {
125 break;
126 }
127
128 case TagConstants.RAISECMD:
129 {
130 out[0] = null;
131 out[1] = in;
132 break;
133 }
134
135 case TagConstants.LOOPCMD:
136 {
137 LoopCmd lp= (LoopCmd)g;
138
139 Set t = Targets.normal(g);
140 // remove t from in
141 for(Enumeration e = t.elements(); e.hasMoreElements(); ) {
142 GenericVarDecl vd = (GenericVarDecl)e.nextElement();
143 in.put(vd, nonConst);
144 }
145
146 F( lp.guard, in, out );
147 Hashtable ex=out[1];
148 F( lp.body, out[0], out );
149 out[1] = mergeEnv( out[1], ex );
150
151 break;
152 }
153
154 case TagConstants.CALL:
155 {
156 Call call= (Call)g;
157 // TBW
158 F( call.desugared, in, out );
159 break;
160 }
161
162 case TagConstants.GETSCMD:
163 {
164 GetsCmd gc = (GetsCmd)g;
165 addTarget( gc.v.decl );
166 extendEnv( out[0], gc.v.decl, applyEnv( in, gc.rhs ));
167 break;
168 }
169
170 case TagConstants.SUBGETSCMD:
171 {
172 SubGetsCmd gc = (SubGetsCmd)g;
173 addTarget( gc.v.decl, applyEnv( in, gc.index ));
174 extendEnv( out[0], gc.v.decl, null );
175 break;
176 }
177
178 case TagConstants.SUBSUBGETSCMD:
179 {
180 SubSubGetsCmd gc = (SubSubGetsCmd)g;
181 addTarget( gc.v.decl, applyEnv( in, gc.index1 ), applyEnv( in, gc.index2 ));
182 extendEnv( out[0], gc.v.decl, null );
183 break;
184 }
185
186 case TagConstants.VARINCMD:
187 {
188 VarInCmd vc = (VarInCmd)g;
189 for (int i = 0; i < vc.v.size(); i++) {
190 in.put( vc.v.elementAt(i), nonConst );
191 }
192 F( vc.g, in, out );
193 // remove from targets
194 for (int i = 0; i < vc.v.size(); i++) {
195 for(Enumeration e = targets.elements(); e.hasMoreElements(); ) {
196 ATarget t = (ATarget)e.nextElement();
197 if( t.x == vc.v.elementAt(i) ) {
198 targets.remove(t);
199 break; //enum loop
200 }
201 }
202 }
203 break;
204 }
205
206 case TagConstants.DYNINSTCMD:
207 {
208 DynInstCmd dc = (DynInstCmd)g;
209 F( dc.g, in, out );
210 break;
211 }
212
213 case TagConstants.SEQCMD:
214 {
215 SeqCmd sc = (SeqCmd)g;
216 Hashtable ex = null;
217 for (int i = 0; i < sc.cmds.size(); i++) {
218 F( sc.cmds.elementAt(i), out[0], out);
219 ex = mergeEnv( ex, out[1] );
220 }
221 out[1] = ex;
222 break;
223 }
224
225 case TagConstants.TRYCMD:
226 {
227 CmdCmdCmd tc = (CmdCmdCmd)g;
228 F( tc.g1, in, out );
229 Hashtable norm = out[0];
230 F( tc.g2, out[1], out );
231 out[0] = mergeEnv( out[0], norm );
232 break;
233 }
234
235 case TagConstants.CHOOSECMD:
236 {
237 CmdCmdCmd cc = (CmdCmdCmd)g;
238 Hashtable in2 = (Hashtable)in.clone();
239 Hashtable[] out2 = new Hashtable[2];
240
241 F( cc.g1, in, out );
242 F( cc.g1, in2, out2 );
243 out[0] = mergeEnv( out[0], out2[0] );
244 out[1] = mergeEnv( out[1], out2[1] );
245 break;
246 }
247
248 default:
249 //@ unreachable;
250 Assert.fail("Fall thru on "+g);
251 }
252 }
253
254 static private void extendEnv( Hashtable env, GenericVarDecl d, Expr e) {
255 if( e == null ) e = nonConst;
256 env.put(d,e);
257 }
258
259 static private Hashtable mergeEnv( Hashtable a, Hashtable b ) {
260 if( a == null ) return b;
261 if( b == null ) return a;
262
263 Hashtable r = new Hashtable();
264 for(Enumeration e = a.keys(); e.hasMoreElements(); ) {
265 Object key = e.nextElement();
266 Object o = a.get(key);
267 if( o.equals( b.get(key) ) ) {
268 r.put( key, o );
269 } else {
270 r.put( key, nonConst );
271 }
272 }
273 for(Enumeration e = b.keys(); e.hasMoreElements(); ) {
274 Object key = e.nextElement();
275 if( a.get(key) == nonConst ) {
276 r.put( key, nonConst );
277 }
278 }
279 return r;
280 }
281
282 /** Returns null if expr not loop constant */
283
284 static private Expr applyEnv( Hashtable env, Expr expr ) {
285 Set vars = new Set();
286 computeMentionsSet( expr, vars );
287 for(Enumeration e = vars.elements(); e.hasMoreElements(); ) {
288 GenericVarDecl var = (GenericVarDecl)e.nextElement();
289 Expr val = (Expr)env.get( var );
290
291 if( val == nonConst ) {
292 return null;
293 } else if( val != null ) {
294 expr = GC.subst(Location.NULL, Location.NULL, var, val, expr );
295 }
296 // else var is loop-invariant
297 }
298 return expr;
299 }
300
301 private static void computeMentionsSet(ASTNode n, Set s) {
302 if( n instanceof VariableAccess ) {
303 VariableAccess va = (VariableAccess)n;
304 if( va.decl != null ) {
305 s.add(va.decl);
306 }
307 }
308 for(int i=0; i<n.childCount(); i++) {
309 Object c = n.childAt(i);
310 if( c instanceof ASTNode ) {
311 computeMentionsSet((ASTNode)c,s);
312 }
313 }
314 }
315
316 public /*@non_null*/String toString() {
317 StringBuffer s = new StringBuffer("[aTarget: x =" + x.id + "\n");
318
319 for (int i = 0; i < indices.length; i++) {
320 s.append(" index[" + i + "] is " + indices[i]+"\n");
321 // FIXME - fix end of line character
322 }
323 s.append("]\n"); // FIXME - fix end of line character
324 return s.toString();
325 }
326 }