*** empty log message ***
[repair.git] / 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 }