Repair/RepairCompiler/MCC/IR/ArrayAnalysis.java

   1 package MCC.IR;
   2 import java.util.*;
   3 import MCC.State;
   4
   5 public class ArrayAnalysis {
   6     Termination termination;
   7     State state;
   8
   9     public ArrayAnalysis(State state, Termination t) {
  10         this.state=state;
  11         this.termination=t;
  12         this.set=new Hashtable();
  13         this.leftrelation=new Hashtable();
  14         this.rightrelation=new Hashtable();
  15
  16         assert termination.exactsize!=null;
  17         doAnalysis();
  18     }
  19
  20     Hashtable set;
  21     Hashtable leftrelation;
  22     Hashtable rightrelation;
  23
  24     public AccessPath getSet(SetDescriptor sd) {
  25         if (set.containsKey(sd))
  26             return (AccessPath)set.get(sd);
  27         return null;
  28     }
  29
  30
  31     public AccessPath getDomain(RelationDescriptor rd) {
  32         if (leftrelation.containsKey(rd))
  33             return (AccessPath)leftrelation.get(rd);
  34         return null;
  35     }
  36
  37     public AccessPath getRange(RelationDescriptor rd) {
  38         if (rightrelation.containsKey(rd))
  39             return (AccessPath)rightrelation.get(rd);
  40         return null;
  41     }
  42
  43     private void doAnalysis() {
  44         Vector rules=state.vRules;
  45         for(int i=0;i<rules.size();i++) {
  46             Rule r=(Rule)rules.get(i);
  47             Inclusion inc=r.getInclusion();
  48             if (inc instanceof SetInclusion) {
  49                 SetInclusion si=(SetInclusion)inc;
  50
  51                 AccessPath oldap=set.containsKey(si.getSet())?(AccessPath)set.get(si.getSet()):null;
  52                 AccessPath newap=analyzeExpr(r,si.getExpr());
  53                 if (oldap==null) {
  54                     set.put(si.getSet(),newap);
  55                 } else {
  56                     if (!oldap.equal(newap))
  57                         set.put(si.getSet(),AccessPath.NONE);
  58                 }
  59             } else if (inc instanceof RelationInclusion) {
  60                 RelationInclusion ri=(RelationInclusion)inc;
  61
  62                 AccessPath oldapl=leftrelation.containsKey(ri.getRelation())?(AccessPath)leftrelation.get(ri.getRelation()):null;
  63                 AccessPath newapl=analyzeExpr(r,ri.getLeftExpr());
  64                 if (oldapl==null) {
  65                     leftrelation.put(ri.getRelation(),newapl);
  66                 } else {
  67                     if (!oldapl.equal(newapl))
  68                         leftrelation.put(ri.getRelation(),AccessPath.NONE);
  69                 }
  70
  71                 AccessPath oldapr=rightrelation.containsKey(ri.getRelation())?(AccessPath)rightrelation.get(ri.getRelation()):null;
  72                 AccessPath newapr=analyzeExpr(r,ri.getRightExpr());
  73                 if (oldapr==null) {
  74                     rightrelation.put(ri.getRelation(),newapr);
  75                 } else {
  76                     if (!oldapr.equal(newapr))
  77                         rightrelation.put(ri.getRelation(),AccessPath.NONE);
  78                 }
  79             } else throw new Error();
  80         }
  81     }
  82
  83     public AccessPath analyzeExpr(Rule r,Expr e) {
  84         Vector dotvector=new Vector();
  85         Expr ptr=e;
  86         while (ptr instanceof CastExpr)
  87             ptr=((CastExpr)ptr).getExpr();
  88
  89         while(true) {
  90             /* Does something other than a dereference? */
  91
  92             if (!(ptr instanceof DotExpr)) {
  93                 return AccessPath.NONE;
  94             }
  95
  96             DotExpr de=(DotExpr)ptr;
  97             dotvector.add(de);
  98             ptr=de.left;
  99             while (ptr instanceof CastExpr)
 100                 ptr=((CastExpr)ptr).getExpr();
 101
 102             if (ptr instanceof VarExpr) {
 103                 VarExpr ve=(VarExpr)ptr;
 104                 VarDescriptor vd=ve.getVar();
 105                 AccessPath ap=new AccessPath();
 106                 if (vd.isGlobal()) {
 107                     ap.startVar(vd);
 108                 } else {
 109                     for(int i=0;i<r.numQuantifiers();i++) {
 110                         Quantifier q=r.getQuantifier(i);
 111                         if ((q instanceof SetQuantifier)&&
 112                             ((SetQuantifier)q).getVar()==vd) {
 113                             SetDescriptor sd=((SetQuantifier)q).getSet();
 114                             int size=termination.exactsize.getsize(sd);
 115                             if (size==1) {
 116                                 ap.startSet(sd);
 117                                 break;
 118                             } else {
 119                                 return AccessPath.NONE;
 120                             }
 121                         }
 122                     }
 123                     if (!ap.setStart) {
 124                         return AccessPath.NONE;
 125                     }
 126                 }
 127                 /* Starting point finished - parse dereferences */
 128                 boolean foundarray=false;
 129                 for(int j=dotvector.size()-1;j>=0;j--) {
 130                     DotExpr de2=(DotExpr) dotvector.get(j);
 131                     FieldDescriptor fd=de2.getField();
 132                     if (fd instanceof ArrayDescriptor) {
 133                         foundarray=true;
 134                         if (((ArrayDescriptor)fd).getField().getPtr()) {
 135                             return AccessPath.NONE;
 136                         }
 137                     } else {
 138                         if (foundarray&&fd.getPtr()) {
 139                             return AccessPath.NONE;
 140                         }
 141                     }
 142                     ap.addField(fd);
 143                 }
 144                 return ap;
 145             }
 146         }
 147     }
 148
 149     public static class AccessPath {
 150         public static final AccessPath NONE=new AccessPath();
 151
 152         public AccessPath() {
 153             path=new Vector();
 154         }
 155         boolean setStart;
 156         SetDescriptor startset;
 157         VarDescriptor startvar;
 158
 159         public boolean isSet() {
 160             return setStart;
 161         }
 162
 163         public SetDescriptor getSet() {
 164             return startset;
 165         }
 166
 167         public VarDescriptor getVar() {
 168             return startvar;
 169         }
 170
 171
 172         public void startSet(SetDescriptor sd) {
 173             this.startset=sd;
 174             setStart=true;
 175         }
 176
 177         public void startVar(VarDescriptor vd) {
 178             assert vd.isGlobal();
 179             this.startvar=vd;
 180             setStart=false;
 181         }
 182
 183         Vector path;
 184         public void addField(FieldDescriptor fd) {
 185             path.add(fd);
 186         }
 187
 188         public int numFields() {
 189             return path.size();
 190         }
 191
 192         public FieldDescriptor getField(int i) {
 193             return (FieldDescriptor)path.get(i);
 194         }
 195
 196         public String toString() {
 197             String st="";
 198             if (setStart)
 199                 st+=this.startset;
 200             else
 201                 st+=this.startvar;
 202
 203             for(int i=0;i<numFields();i++) {
 204                 st+="."+getField(i);
 205             }
 206             return st;
 207         }
 208
 209         public boolean equal(AccessPath ap) {
 210             if (this==ap)
 211                 return true;
 212             if (setStart&&this.startset!=ap.startset)
 213                 return false;
 214             if ((!setStart)&&this.startvar!=ap.startvar)
 215                 return false;
 216             if (this.path.size()!=ap.path.size())
 217                 return false;
 218             for(int i=0;i<this.path.size();i++) {
 219                 if (this.path.get(i)!=ap.path.get(i))
 220                     return false;
 221             }
 222             return true;
 223         }
 224     }
 225 }