Repair/RepairCompiler/MCC/IR/UpdateNode.java

   1 package MCC.IR;
   2 import java.util.*;
   3 import MCC.State;
   4
   5 class UpdateNode {
   6     Vector updates;
   7     Vector bindings;
   8     Hashtable binding;
   9     Rule rule;
  10
  11
  12     public UpdateNode(Rule r) {
  13         updates=new Vector();
  14         bindings=new Vector();
  15         binding=new Hashtable();
  16         rule=r;
  17     }
  18
  19     public Rule getRule() {
  20         return rule;
  21     }
  22
  23     public String toString() {
  24         String st="";
  25         for(int i=0;i<bindings.size();i++)
  26             st+=bindings.get(i).toString()+"\n";
  27         st+="---------------------\n";
  28         for(int i=0;i<updates.size();i++)
  29             st+=updates.get(i).toString()+"\n";
  30         return st;
  31     }
  32
  33     public void addBindings(Vector v) {
  34         for (int i=0;i<v.size();i++) {
  35             addBinding((Binding)v.get(i));
  36         }
  37     }
  38
  39     public boolean checkupdates() {
  40         if (!checkconflicts()) /* Do we have conflicting concrete updates */
  41             return false;
  42         if (computeordering()) /* Ordering exists */
  43             return true;
  44         return false;
  45     }
  46
  47     private boolean computeordering() {
  48         /* Build dependency graph between updates */
  49         HashSet graph=new HashSet();
  50         Hashtable mapping=new Hashtable();
  51         for(int i=0;i<updates.size();i++) {
  52             Updates u=(Updates)updates.get(i);
  53             GraphNode gn=new GraphNode(String.valueOf(i),u);
  54             mapping.put(u, gn);
  55             graph.add(gn);
  56         }
  57         for(int i=0;i<updates.size();i++) {
  58             Updates u1=(Updates)updates.get(i);
  59             if (u1.isAbstract())
  60                 continue;
  61             for(int j=0;j<updates.size();j++) {
  62                 Updates u2=(Updates)updates.get(j);
  63                 if (!u2.isExpr())
  64                     continue;
  65                 Descriptor d=u1.getDescriptor();
  66                 if (u2.getRightExpr().usesDescriptor(d)) {
  67                     /* Add edge for dependency */
  68                     GraphNode gn1=(GraphNode) mapping.get(u1);
  69                     GraphNode gn2=(GraphNode) mapping.get(u2);
  70                     GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
  71                     gn1.addEdge(e);
  72                 }
  73             }
  74         }
  75
  76         if (!GraphNode.DFS.depthFirstSearch(graph))  /* DFS & check for acyclicity */
  77             return false;
  78
  79         TreeSet topologicalsort = new TreeSet(new Comparator() {
  80                 public boolean equals(Object obj) { return false; }
  81                 public int compare(Object o1, Object o2) {
  82                     GraphNode g1 = (GraphNode) o1;
  83                     GraphNode g2 = (GraphNode) o2;
  84                     return g2.getFinishingTime() - g1.getFinishingTime();
  85                 }
  86             });
  87         topologicalsort.addAll(graph);
  88         Vector sortedvector=new Vector();
  89         for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
  90             GraphNode gn=(GraphNode)sort.next();
  91             sortedvector.add(gn.getOwner());
  92         }
  93         updates=sortedvector; //replace updates with the sorted array
  94         return true;
  95     }
  96
  97     private boolean checkconflicts() {
  98         Set toremove=new HashSet();
  99         for(int i=0;i<updates.size();i++) {
 100             Updates u1=(Updates)updates.get(i);
 101             for(int j=0;j<updates.size();j++) {
 102                 Updates u2=(Updates)updates.get(j);
 103                 if (i==j)
 104                     continue;
 105                 if (u1.isAbstract()||u2.isAbstract())
 106                     continue;  /* Abstract updates are already accounted for by graph */
 107                 if (u1.getDescriptor()!=u2.getDescriptor())
 108                     continue; /* No interference - different descriptors */
 109
 110                 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
 111                     (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
 112                     continue; /* Can be satisfied simultaneously */
 113
 114                 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
 115                     (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
 116                     continue;
 117                 if ((u1.getOpcode()==u2.getOpcode())&&
 118                     u1.isExpr()&&u2.isExpr()&&
 119                     u1.getRightExpr().equals(null, u2.getRightExpr())) {
 120                     /*We'll remove the second occurence*/
 121                     if (i>j)
 122                         toremove.add(u1);
 123                     else
 124                         toremove.add(u2);
 125                     continue;
 126                 }
 127
 128                 /* Handle = or != NULL */
 129                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 130                      ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 131                     (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
 132                      ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
 133                     if (u1.getOpcode()==Opcode.NE)
 134                         toremove.add(u1);
 135                     else
 136                         toremove.add(u2);
 137                     continue;
 138                 }
 139
 140                 /* Handle = and != to different constants */
 141                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 142                     ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 143                     (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
 144                     (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
 145                     !u1.getRightExpr().equals(u2.getRightExpr())) {
 146                     if (u1.getOpcode()==Opcode.NE)
 147                         toremove.add(u1);
 148                     else
 149                         toremove.add(u2);
 150                     continue;
 151                 }
 152
 153                 /* Compatible operations < & <= */
 154                 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
 155                     ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
 156                     continue;
 157
 158                 /* Compatible operations > & >= */
 159                 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
 160                     ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
 161                     continue;
 162                 /* Ranges */
 163
 164                 //XXXXXX: TODO
 165                 /* Equality & Comparisons */
 166                 //XXXXXX: TODO
 167
 168                 return false; /* They interfere */
 169             }
 170         }
 171         updates.removeAll(toremove);
 172         return true;
 173     }
 174
 175     public void addBinding(Binding b) {
 176         bindings.add(b);
 177         binding.put(b.getVar(),b);
 178     }
 179
 180     public int numBindings() {
 181         return bindings.size();
 182     }
 183
 184     public Binding getBinding(int i) {
 185         return (Binding)bindings.get(i);
 186     }
 187
 188     public Binding getBinding(VarDescriptor vd) {
 189         if (binding.containsKey(vd))
 190             return (Binding)binding.get(vd);
 191         else
 192             return null;
 193     }
 194
 195     public void addUpdate(Updates u) {
 196         updates.add(u);
 197     }
 198
 199     public int numUpdates() {
 200         return updates.size();
 201     }
 202     public Updates getUpdate(int i) {
 203         return (Updates)updates.get(i);
 204     }
 205
 206     private MultUpdateNode getMultUpdateNode(boolean negate, Descriptor d, RepairGenerator rg) {
 207         Termination termination=rg.termination;
 208         MultUpdateNode mun=null;
 209         GraphNode gn;
 210         if (negate)
 211             gn=(GraphNode)termination.abstractremove.get(d);
 212         else
 213             gn=(GraphNode)termination.abstractadd.get(d);
 214         TermNode tn=(TermNode)gn.getOwner();
 215         for(Iterator edgeit=gn.edges();edgeit.hasNext();) {
 216             GraphNode gn2=((GraphNode.Edge) edgeit.next()).getTarget();
 217             if (!rg.removed.contains(gn2)) {
 218                 TermNode tn2=(TermNode)gn2.getOwner();
 219                 if (tn2.getType()==TermNode.UPDATE) {
 220                     mun=tn2.getUpdate();
 221                     break;
 222                 }
 223             }
 224         }
 225         if (mun==null)
 226             throw new Error("Can't find update node!");
 227         return mun;
 228     }
 229
 230     public void generate_abstract(CodeWriter cr, Updates u, RepairGenerator rg) {
 231         State state=rg.state;
 232         Expr abstractexpr=u.getLeftExpr();
 233         boolean negated=u.negate;
 234         Descriptor d=null;
 235         Expr left=null;
 236         Expr right=null;
 237         boolean istuple=false;
 238         if (abstractexpr instanceof TupleOfExpr) {
 239             TupleOfExpr toe=(TupleOfExpr) abstractexpr;
 240             d=toe.relation;
 241             left=toe.left;
 242             right=toe.right;
 243             istuple=true;
 244         } else if (abstractexpr instanceof ElementOfExpr) {
 245             ElementOfExpr eoe=(ElementOfExpr) abstractexpr;
 246             d=eoe.set;
 247             left=eoe.element;
 248             istuple=false;
 249         } else {
 250             throw new Error("Unsupported Expr");
 251         }
 252         MultUpdateNode mun=getMultUpdateNode(negated,d,rg);
 253         VarDescriptor leftvar=VarDescriptor.makeNew("leftvar");
 254         VarDescriptor rightvar=VarDescriptor.makeNew("rightvar");
 255         left.generate(cr, leftvar);
 256         if (istuple)
 257             right.generate(cr,rightvar);
 258
 259         if (negated) {
 260             if (istuple) {
 261                 RelationDescriptor rd=(RelationDescriptor)d;
 262                 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
 263                 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
 264                 if (usageimage)
 265                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
 266                 if (usageinvimage)
 267                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->remove((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
 268
 269                 for(int i=0;i<state.vRules.size();i++) {
 270                     Rule r=(Rule)state.vRules.get(i);
 271                     if (r.getInclusion().getTargetDescriptors().contains(rd)) {
 272                         for(int j=0;j<mun.numUpdates();j++) {
 273                             UpdateNode un=mun.getUpdate(i);
 274                             if (un.getRule()==r) {
 275                                 /* Update for rule rule r */
 276                                 String name=(String)rg.updatenames.get(un);
 277                                 cr.outputline(rg.strepairtable+"->addrelation("+rd.getNum()+","+r.getNum()+","+leftvar.getSafeSymbol()+","+rightvar.getSafeSymbol()+",(int) &"+name+");");
 278                             }
 279                         }
 280                     }
 281                 }
 282             } else {
 283                 SetDescriptor sd=(SetDescriptor) d;
 284                 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->remove((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
 285
 286                 for(int i=0;i<state.vRules.size();i++) {
 287                     Rule r=(Rule)state.vRules.get(i);
 288                     if (r.getInclusion().getTargetDescriptors().contains(sd)) {
 289                         for(int j=0;j<mun.numUpdates();j++) {
 290                             UpdateNode un=mun.getUpdate(j);
 291                             if (un.getRule()==r) {
 292                                 /* Update for rule rule r */
 293                                 String name=(String)rg.updatenames.get(un);
 294                                 cr.outputline(rg.strepairtable+"->addset("+sd.getNum()+","+r.getNum()+","+leftvar.getSafeSymbol()+",(int) &"+name+");");
 295                             }
 296                         }
 297                     }
 298                 }
 299             }
 300         } else {
 301             /* Generate update */
 302             if (istuple) {
 303                 RelationDescriptor rd=(RelationDescriptor) d;
 304                 boolean usageimage=rd.testUsage(RelationDescriptor.IMAGE);
 305                 boolean usageinvimage=rd.testUsage(RelationDescriptor.INVIMAGE);
 306                 if (usageimage)
 307                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + rightvar.getSafeSymbol() + ");");
 308                 if (usageinvimage)
 309                     cr.outputline(rg.stmodel+"->"+rd.getJustSafeSymbol() + "_hashinv->add((int)" + rightvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
 310
 311                 UpdateNode un=mun.getUpdate(0);
 312                 String name=(String)rg.updatenames.get(un);
 313                 cr.outputline(name+"(this,"+rg.stmodel+","+rg.strepairtable+","+leftvar.getSafeSymbol()+","+rightvar.getSafeSymbol()+");");
 314             } else {
 315                 SetDescriptor sd=(SetDescriptor)d;
 316                 cr.outputline(rg.stmodel+"->"+sd.getJustSafeSymbol() + "_hash->add((int)" + leftvar.getSafeSymbol() + ", (int)" + leftvar.getSafeSymbol() + ");");
 317
 318                 UpdateNode un=mun.getUpdate(0);
 319                 /* Update for rule rule r */
 320                 String name=(String)rg.updatenames.get(un);
 321                 cr.outputline(name+"(this,"+rg.stmodel+","+rg.strepairtable+","+leftvar.getSafeSymbol()+");");
 322             }
 323         }
 324
 325     }
 326
 327     public void generate(CodeWriter cr, boolean removal, boolean modify, String slot0, String slot1, String slot2, RepairGenerator rg) {
 328         if (!removal&&!modify)
 329             generate_bindings(cr, slot0,slot1);
 330         for(int i=0;i<updates.size();i++) {
 331             Updates u=(Updates)updates.get(i);
 332             VarDescriptor right=VarDescriptor.makeNew("right");
 333             if (u.getType()==Updates.ABSTRACT) {
 334                 generate_abstract(cr, u, rg);
 335                 return;
 336             }
 337
 338             switch(u.getType()) {
 339             case Updates.EXPR:
 340                 u.getRightExpr().generate(cr,right);
 341                 break;
 342             case Updates.POSITION:
 343             case Updates.ACCESSPATH:
 344                 if (u.getRightPos()==0)
 345                     cr.outputline("int "+right.getSafeSymbol()+"="+slot0+";");
 346                 else if (u.getRightPos()==1)
 347                     cr.outputline("int "+right.getSafeSymbol()+"="+slot1+";");
 348                 else if (u.getRightPos()==2)
 349                     cr.outputline("int "+right.getSafeSymbol()+"="+slot2+";");
 350                 else throw new Error("Error w/ Position");
 351                 break;
 352             default:
 353                 throw new Error();
 354             }
 355
 356             if (u.getType()==Updates.ACCESSPATH) {
 357                 VarDescriptor newright=VarDescriptor.makeNew("right");
 358                 /* Need to do the modulo computation here...FIXME */
 359                 generate_accesspath(cr, right,newright,u);
 360                 right=newright;
 361             }
 362             VarDescriptor left=VarDescriptor.makeNew("left");
 363             u.getLeftExpr().generate(cr,left);
 364             Opcode op=u.getOpcode();
 365             cr.outputline("if (!("+left.getSafeSymbol()+op+right.getSafeSymbol()+"))");
 366             cr.startblock();
 367
 368             if (op==Opcode.GT)
 369                 cr.outputline(right.getSafeSymbol()+"++;");
 370             else if (op==Opcode.GE)
 371                 ;
 372             else if (op==Opcode.EQ)
 373                 ;
 374             else if (op==Opcode.NE)
 375                 cr.outputline(right.getSafeSymbol()+"++;");
 376             else if (op==Opcode.LT)
 377                 cr.outputline(right.getSafeSymbol()+"--;");
 378             else if (op==Opcode.LE)
 379                 ;
 380             else throw new Error();
 381             if (u.isGlobal()) {
 382                 VarDescriptor vd=((VarExpr)u.getLeftExpr()).getVar();
 383                 cr.outputline(vd.getSafeSymbol()+"="+right.getSafeSymbol()+";");
 384             } else if (u.isField()) {
 385                 /* NEED TO FIX */
 386                 Expr subexpr=((DotExpr)u.getLeftExpr()).getExpr();
 387                 Expr intindex=((DotExpr)u.getLeftExpr()).getIndex();
 388                 VarDescriptor subvd=VarDescriptor.makeNew("subexpr");
 389                 VarDescriptor indexvd=VarDescriptor.makeNew("index");
 390                 subexpr.generate(cr,subvd);
 391                 if (intindex!=null)
 392                     intindex.generate(cr,indexvd);
 393                 FieldDescriptor fd=(FieldDescriptor)u.getDescriptor();
 394                 StructureTypeDescriptor std=(StructureTypeDescriptor)subexpr.getType();
 395                 if (fd instanceof ArrayDescriptor) {
 396                     fd = ((ArrayDescriptor) fd).getField();
 397                 }
 398
 399                 Expr offsetbits = std.getOffsetExpr(fd);
 400                 if (intindex != null) {
 401                     Expr basesize = fd.getBaseSizeExpr();
 402                     offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
 403                 }
 404                 Expr offsetbytes = new OpExpr(Opcode.SHR, offsetbits,new IntegerLiteralExpr(3));
 405                 Expr byteaddress=new OpExpr(Opcode.ADD, offsetbytes, subexpr);
 406                 VarDescriptor addr=VarDescriptor.makeNew("byteaddress");
 407                 byteaddress.generate(cr,addr);
 408
 409                 if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
 410                     ReservedTypeDescriptor rtd=(ReservedTypeDescriptor)fd.getType();
 411                     if (rtd==ReservedTypeDescriptor.INT) {
 412                         cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 413                     } else if (rtd==ReservedTypeDescriptor.SHORT) {
 414                         cr.outputline("*((short *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 415                     } else if (rtd==ReservedTypeDescriptor.BYTE) {
 416                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 417                     } else if (rtd==ReservedTypeDescriptor.BIT) {
 418                         Expr tmp = new OpExpr(Opcode.SHL, offsetbytes, new IntegerLiteralExpr(3));
 419                         Expr offset=new OpExpr(Opcode.SUB, offsetbits, tmp);
 420                         Expr mask=new OpExpr(Opcode.SHR, new IntegerLiteralExpr(1), offset);
 421                         VarDescriptor maskvar=VarDescriptor.makeNew("mask");
 422                         mask.generate(cr,maskvar);
 423                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")|="+maskvar.getSafeSymbol()+";");
 424                         cr.outputline("if (!"+right.getSafeSymbol()+")");
 425                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")^="+maskvar.getSafeSymbol()+";");
 426                     } else throw new Error();
 427                 } else {
 428                     /* Pointer */
 429                     cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 430                 }
 431             }
 432             cr.endblock();
 433         }
 434     }
 435
 436
 437     private void generate_accesspath(CodeWriter cr, VarDescriptor right, VarDescriptor newright, Updates u) {
 438         Vector dotvector=new Vector();
 439         Expr ptr=u.getRightExpr();
 440
 441         while(true) {
 442             /* Does something other than a dereference? */
 443             dotvector.add(ptr);
 444             if (ptr instanceof DotExpr)
 445                 ptr=((DotExpr)ptr).left;
 446             else if (ptr instanceof CastExpr)
 447                 ptr=((CastExpr)ptr).getExpr();
 448
 449             if (ptr instanceof VarExpr) {
 450                 /* Finished constructing vector */
 451                 break;
 452             }
 453         }
 454         ArrayAnalysis.AccessPath ap=u.getAccessPath();
 455         VarDescriptor init=VarDescriptor.makeNew("init");
 456         if (ap.isSet()) {
 457             cr.outputline("int "+init.getSafeSymbol()+"="+ap.getSet().getSafeSymbol()+"_hash->firstkey();")
 458         } else {
 459             init=ap.getVar();
 460         }
 461         for(int i=dotvector.size()-1;i>=0;i--) {
 462             Expr e=(Expr)dotvector.get(i);
 463
 464         }
 465
 466     }
 467
 468     private void generate_bindings(CodeWriter cr, String slot0, String slot1) {
 469         for(int i=0;i<bindings.size();i++) {
 470             Binding b=(Binding)bindings.get(i);
 471
 472             if (b.getType()==Binding.SEARCH) {
 473                 VarDescriptor vd=b.getVar();
 474                 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+b.getSet().getSafeSymbol()+"->firstkey();");
 475             } else if (b.getType()==Binding.CREATE) {
 476                 throw new Error("Creation not supported");
 477                 //              source.generateSourceAlloc(cr,vd,b.getSet());
 478             } else {
 479                 VarDescriptor vd=b.getVar();
 480                 switch(b.getPosition()) {
 481                 case 0:
 482                     cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot0+";");
 483                     break;
 484                 case 1:
 485                     cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot1+";");
 486                     break;
 487                 default:
 488                     throw new Error("Slot >1 doesn't exist.");
 489                 }
 490             }
 491         }
 492     }
 493 }