From 8a685ebd4f3f110bf687bb84ebe772660e13f5fa Mon Sep 17 00:00:00 2001 From: bdemsky Date: Thu, 29 Apr 2004 04:47:36 +0000 Subject: [PATCH] Added improvements to ImplicitSchema analysis, bug fixes to ImplicitSchema and SetAnalysis, added edges for abstract repairs. --- .../RepairCompiler/MCC/IR/ArrayAnalysis.java | 56 ++- .../RepairCompiler/MCC/IR/ImplicitSchema.java | 32 +- .../MCC/IR/RepairGenerator.java | 18 +- Repair/RepairCompiler/MCC/IR/SetAnalysis.java | 22 +- Repair/RepairCompiler/MCC/IR/Termination.java | 409 ++++++++++++------ Repair/RepairCompiler/MCC/IR/UpdateNode.java | 7 + Repair/RepairCompiler/MCC/IR/Updates.java | 109 +++-- 7 files changed, 436 insertions(+), 217 deletions(-) diff --git a/Repair/RepairCompiler/MCC/IR/ArrayAnalysis.java b/Repair/RepairCompiler/MCC/IR/ArrayAnalysis.java index 670cd79..ca142f7 100755 --- a/Repair/RepairCompiler/MCC/IR/ArrayAnalysis.java +++ b/Repair/RepairCompiler/MCC/IR/ArrayAnalysis.java @@ -53,7 +53,7 @@ public class ArrayAnalysis { if (oldap==null) { set.put(si.getSet(),newap); } else { - if (!oldap.equals(newap)) + if (!oldap.equal(newap)) set.put(si.getSet(),AccessPath.NONE); } } else if (inc instanceof RelationInclusion) { @@ -64,7 +64,7 @@ public class ArrayAnalysis { if (oldapl==null) { leftrelation.put(ri.getRelation(),newapl); } else { - if (!oldapl.equals(newapl)) + if (!oldapl.equal(newapl)) leftrelation.put(ri.getRelation(),AccessPath.NONE); } @@ -73,7 +73,7 @@ public class ArrayAnalysis { if (oldapr==null) { rightrelation.put(ri.getRelation(),newapr); } else { - if (!oldapr.equals(newapr)) + if (!oldapr.equal(newapr)) rightrelation.put(ri.getRelation(),AccessPath.NONE); } } else throw new Error(); @@ -83,12 +83,22 @@ public class ArrayAnalysis { public AccessPath analyzeExpr(Rule r,Expr e) { Vector dotvector=new Vector(); Expr ptr=e; + while (ptr instanceof CastExpr) + ptr=((CastExpr)ptr).getExpr(); + while(true) { - if (!(ptr instanceof DotExpr)) - return AccessPath.NONE; /* Does something other than a dereference */ + /* Does something other than a dereference? */ + + if (!(ptr instanceof DotExpr)) { + return AccessPath.NONE; + } + DotExpr de=(DotExpr)ptr; dotvector.add(de); ptr=de.left; + while (ptr instanceof CastExpr) + ptr=((CastExpr)ptr).getExpr(); + if (ptr instanceof VarExpr) { VarExpr ve=(VarExpr)ptr; VarDescriptor vd=ve.getVar(); @@ -105,13 +115,14 @@ public class ArrayAnalysis { if (size==1) { ap.startSet(sd); break; - } else + } else { return AccessPath.NONE; - + } } } - if (!ap.setStart) + if (!ap.setStart) { return AccessPath.NONE; + } } /* Starting point finished - parse dereferences */ boolean foundarray=false; @@ -120,11 +131,13 @@ public class ArrayAnalysis { FieldDescriptor fd=de2.getField(); if (fd instanceof ArrayDescriptor) { foundarray=true; - if (((ArrayDescriptor)fd).getField().getPtr()) + if (((ArrayDescriptor)fd).getField().getPtr()) { return AccessPath.NONE; + } } else { - if (foundarray&&fd.getPtr()) + if (foundarray&&fd.getPtr()) { return AccessPath.NONE; + } } ap.addField(fd); } @@ -143,6 +156,7 @@ public class ArrayAnalysis { SetDescriptor startset; VarDescriptor startvar; + public void startSet(SetDescriptor sd) { this.startset=sd; setStart=true; @@ -158,6 +172,28 @@ public class ArrayAnalysis { public void addField(FieldDescriptor fd) { path.add(fd); } + + public int numFields() { + return path.size(); + } + + public FieldDescriptor getField(int i) { + return (FieldDescriptor)path.get(i); + } + + public String toString() { + String st=""; + if (setStart) + st+=this.startset; + else + st+=this.startvar; + + for(int i=0;iiterator();"+iterator.getSafeSymbol()+".hasNext();)"); @@ -1118,9 +1116,9 @@ public class RepairGenerator { cr.outputline(newobject.getSafeSymbol()+"="+iterator.getSafeSymbol()+".key();"); cr.outputline(iterator.getSafeSymbol()+"->next();"); cr.endblock(); - } else if (sources.relallocSource(rd,!ep.inverted())) { + } else if (termination.sources.relallocSource(rd,!ep.inverted())) { /* Allocation Source*/ - sources.relgenerateSourceAlloc(cr,newobject,rd,!ep.inverted()); + termination.sources.relgenerateSourceAlloc(cr,newobject,rd,!ep.inverted()); } else throw new Error("No source for adding to Relation"); if (ep.inverted()) { boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE); @@ -1146,10 +1144,10 @@ public class RepairGenerator { } } else { SetDescriptor sd=(SetDescriptor)d; - if (sources.setSource(sd)) { + if (termination.sources.setSource(sd)) { /* Set Source */ /* Set Source */ - SetDescriptor sourcesd=sources.getSourceSet(sd); + SetDescriptor sourcesd=termination.sources.getSourceSet(sd); VarDescriptor iterator=VarDescriptor.makeNew("iterator"); cr.outputline(sourcesd.getType().getGenerateType().getSafeSymbol() +" "+newobject.getSafeSymbol()+";"); cr.outputline("for("+iterator.getSafeSymbol()+"="+sourcesd.getSafeSymbol()+"_hash->iterator();"+iterator.getSafeSymbol()+".hasNext();)"); @@ -1158,9 +1156,9 @@ public class RepairGenerator { cr.outputline(newobject.getSafeSymbol()+"="+iterator.getSafeSymbol()+".key();"); cr.outputline(iterator.getSafeSymbol()+"->next();"); cr.endblock(); - } else if (sources.allocSource(sd)) { + } else if (termination.sources.allocSource(sd)) { /* Allocation Source*/ - sources.generateSourceAlloc(cr,newobject,sd); + termination.sources.generateSourceAlloc(cr,newobject,sd); } else throw new Error("No source for adding to Set"); cr.outputline(sd.getSafeSymbol()+"_hash->add("+newobject.getSafeSymbol()+","+newobject.getSafeSymbol()+");"); UpdateNode un=munadd.getUpdate(0); diff --git a/Repair/RepairCompiler/MCC/IR/SetAnalysis.java b/Repair/RepairCompiler/MCC/IR/SetAnalysis.java index 7717ca6..1f91029 100755 --- a/Repair/RepairCompiler/MCC/IR/SetAnalysis.java +++ b/Repair/RepairCompiler/MCC/IR/SetAnalysis.java @@ -21,11 +21,11 @@ public class SetAnalysis { } public boolean isSubset(SetDescriptor set1, SetDescriptor set2) { - return subset.contains(set1)&&((Set)subset.get(set1)).contains(set2); + return subset.containsKey(set1)&&((Set)subset.get(set1)).contains(set2); } public boolean noIntersection(SetDescriptor set1, SetDescriptor set2) { - return intersection.contains(set1)&&((Set)intersection.get(set1)).contains(set2); + return intersection.containsKey(set1)&&((Set)intersection.get(set1)).contains(set2); } void doanalysis() { @@ -35,17 +35,27 @@ public class SetAnalysis { SetDescriptor sd=(SetDescriptor)descriptors.get(i); Stack st=new Stack(); st.addAll(sd.getSubsets()); + + if (!subset.containsKey(sd)) + subset.put(sd,new HashSet()); + ((HashSet)subset.get(sd)).addAll(sd.getSubsets()); + for(Iterator it=sd.getSubsets().iterator();it.hasNext();) { + SetDescriptor sd2=(SetDescriptor)it.next(); + if (!superset.containsKey(sd2)) + superset.put(sd2,new HashSet()); + ((HashSet)superset.get(sd2)).add(sd); + } + while(!st.empty()) { SetDescriptor subsetsd=(SetDescriptor)st.pop(); - System.out.print(subsetsd.toString()); st.addAll(subsetsd.getSubsets()); - if (!subset.contains(sd)) + if (!subset.containsKey(sd)) subset.put(sd,new HashSet()); ((HashSet)subset.get(sd)).addAll(subsetsd.getSubsets()); for(Iterator it=subsetsd.getSubsets().iterator();it.hasNext();) { SetDescriptor sd2=(SetDescriptor)it.next(); - if (!superset.contains(sd2)) + if (!superset.containsKey(sd2)) superset.put(sd2,new HashSet()); ((HashSet)superset.get(sd2)).add(sd); } @@ -63,7 +73,7 @@ public class SetAnalysis { for(Iterator it3=sd1.allSubsets().iterator();it3.hasNext();) { SetDescriptor sd3=(SetDescriptor)it3.next(); - if (!intersection.contains(sd3)) + if (!intersection.containsKey(sd3)) intersection.put(sd3,new HashSet()); ((HashSet)intersection.get(sd3)).addAll(sd2.allSubsets()); } diff --git a/Repair/RepairCompiler/MCC/IR/Termination.java b/Repair/RepairCompiler/MCC/IR/Termination.java index 751ff99..465675c 100755 --- a/Repair/RepairCompiler/MCC/IR/Termination.java +++ b/Repair/RepairCompiler/MCC/IR/Termination.java @@ -29,6 +29,7 @@ public class Termination { ConstraintDependence constraintdependence; ExactSize exactsize; ArrayAnalysis arrayanalysis; + Sources sources; public Termination(State state) { this.state=state; @@ -48,13 +49,14 @@ public class Termination { predtoabstractmap=new Hashtable(); if (!Compiler.REPAIR) return; - + for(int i=0;i=0;i--) { + if (e==null) + e=lexpr; + else + e=((DotExpr)e).getExpr(); + + while (e instanceof CastExpr) + e=((CastExpr)e).getExpr(); + + DotExpr de=(DotExpr)e; + FieldDescriptor fd=ap.getField(i); + if (fd instanceof ArrayDescriptor) { + // We have an ArrayDescriptor! + Expr index=de.getIndex(); + if (!index.isValue()) {/* Not assignable */ + System.out.println("ERROR:Index is assignable"); + return false; + } + Updates updates=new Updates(index,i,ap,slotnumber); + un.addUpdate(updates); + } + } + return true; + } + /** This method constructs bindings for an update using rule * r. The boolean flag isremoval indicates that the update * performs a removal. The function returns true if it is able to @@ -763,94 +1002,6 @@ public class Termination { } return goodupdate; } - - static int addtocount=0; - void generateaddtosetrelation(GraphNode gn, AbstractRepair ar) { - for(int i=0;i