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 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 }