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    }