    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    }