5 public class ArrayAnalysis {
6 Termination termination;
9 public ArrayAnalysis(State state, Termination t) {
12 this.set=new Hashtable();
13 this.leftrelation=new Hashtable();
14 this.rightrelation=new Hashtable();
16 assert termination.exactsize!=null;
21 Hashtable leftrelation;
22 Hashtable rightrelation;
24 public AccessPath getSet(SetDescriptor sd) {
25 if (set.containsKey(sd))
26 return (AccessPath)set.get(sd);
31 public AccessPath getDomain(RelationDescriptor rd) {
32 if (leftrelation.containsKey(rd))
33 return (AccessPath)leftrelation.get(rd);
37 public AccessPath getRange(RelationDescriptor rd) {
38 if (rightrelation.containsKey(rd))
39 return (AccessPath)rightrelation.get(rd);
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;
51 AccessPath oldap=set.containsKey(si.getSet())?(AccessPath)set.get(si.getSet()):null;
52 AccessPath newap=analyzeExpr(r,si.getExpr());
54 set.put(si.getSet(),newap);
56 if (!oldap.equals(newap))
57 set.put(si.getSet(),AccessPath.NONE);
59 } else if (inc instanceof RelationInclusion) {
60 RelationInclusion ri=(RelationInclusion)inc;
62 AccessPath oldapl=leftrelation.containsKey(ri.getRelation())?(AccessPath)leftrelation.get(ri.getRelation()):null;
63 AccessPath newapl=analyzeExpr(r,ri.getLeftExpr());
65 leftrelation.put(ri.getRelation(),newapl);
67 if (!oldapl.equals(newapl))
68 leftrelation.put(ri.getRelation(),AccessPath.NONE);
71 AccessPath oldapr=rightrelation.containsKey(ri.getRelation())?(AccessPath)rightrelation.get(ri.getRelation()):null;
72 AccessPath newapr=analyzeExpr(r,ri.getRightExpr());
74 rightrelation.put(ri.getRelation(),newapr);
76 if (!oldapr.equals(newapr))
77 rightrelation.put(ri.getRelation(),AccessPath.NONE);
79 } else throw new Error();
83 public AccessPath analyzeExpr(Rule r,Expr e) {
84 Vector dotvector=new Vector();
87 if (!(ptr instanceof DotExpr))
88 return null; /* Does something other than a dereference */
89 DotExpr de=(DotExpr)ptr;
92 if (ptr instanceof VarExpr) {
93 VarExpr ve=(VarExpr)ptr;
94 VarDescriptor vd=ve.getVar();
95 AccessPath ap=new AccessPath();
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);
109 return AccessPath.NONE;
114 return AccessPath.NONE;
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) {
123 if (((ArrayDescriptor)fd).getField().getPtr())
124 return AccessPath.NONE;
126 if (foundarray&&fd.getPtr())
127 return AccessPath.NONE;
136 public static class AccessPath {
137 public static final AccessPath NONE=new AccessPath();
139 public AccessPath() {
143 SetDescriptor startset;
144 VarDescriptor startvar;
146 public void startSet(SetDescriptor sd) {
151 public void startVar(VarDescriptor vd) {
152 assert vd.isGlobal();
158 public void addField(FieldDescriptor fd) {
161 public boolean equal(AccessPath ap) {
164 if (setStart&&this.startset!=ap.startset)
166 if ((!setStart)&&this.startvar!=ap.startvar)
168 if (this.path.size()!=ap.path.size())
170 for(int i=0;i<this.path.size();i++) {
171 if (this.path.get(i)!=ap.path.get(i))