Repair/RepairCompiler/MCC/IR/ExactSize.java

   1 package MCC.IR;
   2 import java.util.*;
   3 import MCC.State;
   4
   5
   6 class ExactSize {
   7     State state;
   8     private Hashtable sizemap;
   9     private Hashtable constraintmap;
  10     private SetAnalysis setanalysis;
  11     private Hashtable minsize;
  12     private Hashtable constraintensureminsize;
  13
  14     public ExactSize(State state) {
  15         this.state=state;
  16         this.sizemap=new Hashtable();
  17         this.minsize=new Hashtable();
  18         this.constraintensureminsize=new Hashtable();
  19         this.constraintmap=new Hashtable();
  20         this.setanalysis=state.setanalysis;
  21         computesizes();
  22     }
  23
  24     public int minSize(SetDescriptor sd) {
  25         SizeObject so=new SizeObject(sd);
  26         if (minsize.containsKey(so))
  27             return ((Integer)minsize.get(so)).intValue();
  28         else
  29             return 0;
  30     }
  31
  32     public Constraint ensuresMinSize(SetDescriptor sd) {
  33         SizeObject so=new SizeObject(sd);
  34         return (Constraint)constraintensureminsize.get(so);
  35     }
  36
  37     public int getsize(SetDescriptor sd) {
  38         SizeObject so=new SizeObject(sd);
  39         if (sizemap.containsKey(so))
  40             return ((Integer)sizemap.get(so)).intValue();
  41         else
  42             return -1;
  43     }
  44     public Constraint getConstraint(SetDescriptor sd) {
  45         SizeObject so=new SizeObject(sd);
  46         return (Constraint)constraintmap.get(so);
  47     }
  48
  49     public int getsize(RelationDescriptor rd, SetDescriptor sd, boolean inverted) {
  50         Iterator it=setanalysis.getSuperset(sd).iterator();
  51         while(sd!=null) {
  52             SizeObject so=new SizeObject(rd,sd,inverted);
  53             if (sizemap.containsKey(so))
  54                 return ((Integer)sizemap.get(so)).intValue();
  55             sd=null;
  56             if (it.hasNext())
  57                 sd=(SetDescriptor)it.next();
  58         }
  59         return -1;
  60     }
  61
  62     public Constraint getConstraint(RelationDescriptor rd, SetDescriptor sd, boolean inverted) {
  63         Iterator it=setanalysis.getSuperset(sd).iterator();
  64         while(sd!=null) {
  65             SizeObject so=new SizeObject(rd,sd,inverted);
  66             if (constraintmap.containsKey(so))
  67                 return ((Constraint)constraintmap.get(so));
  68             sd=null;
  69             if (it.hasNext())
  70                 sd=(SetDescriptor)it.next();
  71         }
  72         return null;
  73     }
  74
  75     private void constructminsizes() {
  76         boolean change=true;
  77         HashSet usedsources=new HashSet();
  78         while (change) {
  79             change=false;
  80             for(int i=0;i<state.vRules.size();i++) {
  81                 Rule r=(Rule)state.vRules.get(i);
  82                 //model defition rule with no condition
  83                 if ((!(r.getGuardExpr() instanceof BooleanLiteralExpr))||
  84                     (!((BooleanLiteralExpr)r.getGuardExpr()).getValue()))
  85                     continue;
  86                 //inclusion condition needs to be safe
  87                 if ((!(r.getInclusion() instanceof SetInclusion))||
  88                     (!((SetInclusion)r.getInclusion()).getExpr().isSafe()))
  89                     continue;
  90                 //needs exactly 1 quantifier which is a set quantifier
  91                 if (r.numQuantifiers()!=1||
  92                     (!(r.getQuantifier(0) instanceof SetQuantifier)))
  93                     continue;
  94                 SetQuantifier sq=(SetQuantifier)r.getQuantifier(0);
  95                 SetDescriptor sd=sq.getSet();
  96                 int size=-1;
  97                 Constraint source=null;
  98                 if (getsize(sd)>0) {
  99                     size=getsize(sd);
 100                     source=getConstraint(sd);
 101                 } else if (minSize(sd)>0) {
 102                     size=minSize(sd);
 103                     source=ensuresMinSize(sd);
 104                 } else continue;
 105                 if (size>1)
 106                     size=1; //would need more in depth analysis otherwise
 107                 SetDescriptor newsd=((SetInclusion)r.getInclusion()).getSet();
 108                 if (usedsources.contains(newsd))
 109                     continue; //avoid dependence cycles in our analysis
 110                 //need to force repair to fix one of the constraints in the cycle
 111                 int currentsize=minSize(newsd);
 112                 if (size>currentsize) {
 113                     SizeObject so=new SizeObject(newsd);
 114                     minsize.put(so, new Integer(size));
 115                     constraintensureminsize.put(so,source);
 116                     usedsources.add(source);
 117                     System.out.println("Set "+newsd.toString()+" has minimum size "+size);
 118                     change=true;
 119                     //need update
 120                 }
 121             }
 122         }
 123     }
 124
 125     private void computesizes() {
 126         for(Iterator it=state.stSets.descriptors();it.hasNext();) {
 127             SetDescriptor sd=(SetDescriptor)it.next();
 128             for(int i=0;i<state.vConstraints.size();i++) {
 129                 Constraint c=(Constraint)state.vConstraints.get(i);
 130                 if (c.numQuantifiers()!=0)
 131                     continue;
 132                 DNFConstraint dconst=c.dnfconstraint;
 133                 int oldsize=-1;
 134                 boolean matches=true;
 135                 for(int j=0;j<dconst.size();j++) {
 136                     Conjunction conj=dconst.get(j);
 137                     boolean goodmatch=false;
 138                     for(int k=0;k<conj.size();k++) {
 139                         DNFPredicate dpred=conj.get(k);
 140                         if (!dpred.isNegated()) {
 141                             Predicate p=dpred.getPredicate();
 142                             if (p instanceof ExprPredicate) {
 143                                 ExprPredicate ep=(ExprPredicate)p;
 144                                 if (ep.getType()==ExprPredicate.SIZE&&
 145                                     ep.getOp()==Opcode.EQ&&
 146                                     ep.getDescriptor()==sd&&
 147                                     ep.isRightInt()) {
 148                                     if (j==0) {
 149                                         oldsize=ep.rightSize();
 150                                         goodmatch=true;
 151                                         break;
 152                                     } else {
 153                                         if (oldsize==ep.rightSize()) {
 154                                             goodmatch=true;
 155                                             break;
 156                                         }
 157                                     }
 158                                 }
 159                             }
 160                         }
 161                     }
 162                     if (!goodmatch) {
 163                         matches=false;
 164                         break; //this constraint won't work
 165                     }
 166                 }
 167                 if (matches) {
 168                     System.out.println("Set "+sd.toString()+" has size "+oldsize);
 169                     SizeObject so=new SizeObject(sd);
 170                     sizemap.put(so,new Integer(oldsize));
 171                     constraintmap.put(so,c);
 172                 }
 173             }
 174         }
 175
 176         for(Iterator it=state.stRelations.descriptors();it.hasNext();) {
 177             RelationDescriptor rd=(RelationDescriptor)it.next();
 178             for(int i=0;i<state.vConstraints.size();i++) {
 179                 Constraint c=(Constraint)state.vConstraints.get(i);
 180                 if (c.numQuantifiers()!=1||!(c.getQuantifier(0) instanceof SetQuantifier))
 181                     continue;
 182                 SetQuantifier q=(SetQuantifier) c.getQuantifier(0);
 183
 184                 DNFConstraint dconst=c.dnfconstraint;
 185                 int oldsize=-1;
 186                 boolean matches=true;
 187                 boolean inverted=false;
 188                 for(int j=0;j<dconst.size();j++) {
 189                     Conjunction conj=dconst.get(j);
 190                     boolean goodmatch=false;
 191                     for(int k=0;k<conj.size();k++) {
 192                         DNFPredicate dpred=conj.get(k);
 193                         if (!dpred.isNegated()) {
 194                             Predicate p=dpred.getPredicate();
 195                             if (p instanceof ExprPredicate) {
 196                                 ExprPredicate ep=(ExprPredicate)p;
 197                                 if (ep.getType()==ExprPredicate.SIZE&&
 198                                     ep.getOp()==Opcode.EQ&&
 199                                     ep.getDescriptor()==rd&&
 200                                     ep.isRightInt()&&
 201                                     ((ImageSetExpr)((SizeofExpr)((OpExpr)ep.expr).left).getSetExpr()).getVar()==q.getVar()) {
 202                                     if (j==0) {
 203                                         oldsize=ep.rightSize();
 204                                         goodmatch=true;
 205                                         inverted=ep.inverted();
 206                                         break;
 207                                     } else {
 208                                         if (oldsize==ep.rightSize()&&inverted==ep.inverted()) {
 209                                             goodmatch=true;
 210                                             break;
 211                                         }
 212                                     }
 213                                 }
 214                             }
 215                         }
 216                     }
 217                     if (!goodmatch) {
 218                         matches=false;
 219                         break; //this constraint won't work
 220                     }
 221                 }
 222                 if (matches) {
 223                     System.out.println("Set "+rd.toString()+" has size "+oldsize);
 224                     SizeObject so=new SizeObject(rd,q.getSet(),inverted);
 225                     sizemap.put(so,new Integer(oldsize));
 226                     constraintmap.put(so,c);
 227                 }
 228             }
 229         }
 230         constructminsizes();
 231     }
 232 }