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.equals(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.equals(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.equals(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(true) {
  87             if (!(ptr instanceof DotExpr))
  88                 return null; /* Does something other than a dereference */
  89             DotExpr de=(DotExpr)ptr;
  90             dotvector.add(de);
  91             ptr=de.left;
  92             if (ptr instanceof VarExpr) {
  93                 VarExpr ve=(VarExpr)ptr;
  94                 VarDescriptor vd=ve.getVar();
  95                 AccessPath ap=new AccessPath();
  96                 if (vd.isGlobal()) {
  97                     ap.startVar(vd);
  98                 } else {
  99                     for(int i=0;i<r.numQuantifiers();i++) {
 100                         Quantifier q=r.getQuantifier(i);
 101                         if ((q instanceof SetQuantifier)&&
 102                             ((SetQuantifier)q).getVar()==vd) {
 103                             SetDescriptor sd=((SetQuantifier)q).getSet();
 104                             int size=termination.exactsize.getsize(sd);
 105                             if (size==1) {
 106                                 ap.startSet(sd);
 107                                 break;
 108                             } else
 109                                 return AccessPath.NONE;
 110
 111                         }
 112                     }
 113                     if (!ap.setStart)
 114                         return AccessPath.NONE;
 115                 }
 116                 /* Starting point finished - parse dereferences */
 117                 boolean foundarray=false;
 118                 for(int j=dotvector.size()-1;j>=0;j--) {
 119                     DotExpr de2=(DotExpr) dotvector.get(j);
 120                     FieldDescriptor fd=de2.getField();
 121                     if (fd instanceof ArrayDescriptor) {
 122                         foundarray=true;
 123                         if (((ArrayDescriptor)fd).getField().getPtr())
 124                             return AccessPath.NONE;
 125                     } else {
 126                         if (foundarray&&fd.getPtr())
 127                             return AccessPath.NONE;
 128                     }
 129                     ap.addField(fd);
 130                 }
 131                 return ap;
 132             }
 133         }
 134     }
 135
 136     public static class AccessPath {
 137         public static final AccessPath NONE=new AccessPath();
 138
 139         public AccessPath() {
 140             path=new Vector();
 141         }
 142         boolean setStart;
 143         SetDescriptor startset;
 144         VarDescriptor startvar;
 145
 146         public void startSet(SetDescriptor sd) {
 147             this.startset=sd;
 148             setStart=true;
 149         }
 150
 151         public void startVar(VarDescriptor vd) {
 152             assert vd.isGlobal();
 153             this.startvar=vd;
 154             setStart=false;
 155         }
 156
 157         Vector path;
 158         public void addField(FieldDescriptor fd) {
 159             path.add(fd);
 160         }
 161         public boolean equal(AccessPath ap) {
 162             if (this==ap)
 163                 return true;
 164             if (setStart&&this.startset!=ap.startset)
 165                 return false;
 166             if ((!setStart)&&this.startvar!=ap.startvar)
 167                 return false;
 168             if (this.path.size()!=ap.path.size())
 169                 return false;
 170             for(int i=0;i<this.path.size();i++) {
 171                 if (this.path.get(i)!=ap.path.get(i))
 172                     return false;
 173             }
 174             return true;
 175         }
 176     }
 177 }