Repair/RepairCompiler/MCC/IR/UpdateNode.java

   1 package MCC.IR;
   2 import java.util.*;
   3
   4 class UpdateNode {
   5     Vector updates;
   6     Vector bindings;
   7     Hashtable binding;
   8     Rule rule;
   9
  10
  11     public UpdateNode(Rule r) {
  12         updates=new Vector();
  13         bindings=new Vector();
  14         binding=new Hashtable();
  15         rule=r;
  16     }
  17
  18     public Rule getRule() {
  19         return rule;
  20     }
  21
  22     public String toString() {
  23         String st="";
  24         for(int i=0;i<bindings.size();i++)
  25             st+=bindings.get(i).toString()+"\n";
  26         st+="---------------------\n";
  27         for(int i=0;i<updates.size();i++)
  28             st+=updates.get(i).toString()+"\n";
  29         return st;
  30     }
  31
  32     public void addBindings(Vector v) {
  33         for (int i=0;i<v.size();i++) {
  34             addBinding((Binding)v.get(i));
  35         }
  36     }
  37
  38     public boolean checkupdates() {
  39         if (!checkconflicts()) /* Do we have conflicting concrete updates */
  40             return false;
  41         if (computeordering()) /* Ordering exists */
  42             return true;
  43         return false;
  44     }
  45
  46     private boolean computeordering() {
  47         /* Build dependency graph between updates */
  48         HashSet graph=new HashSet();
  49         Hashtable mapping=new Hashtable();
  50         for(int i=0;i<updates.size();i++) {
  51             Updates u=(Updates)updates.get(i);
  52             GraphNode gn=new GraphNode(String.valueOf(i),u);
  53             mapping.put(u, gn);
  54             graph.add(gn);
  55         }
  56         for(int i=0;i<updates.size();i++) {
  57             Updates u1=(Updates)updates.get(i);
  58             if (u1.isAbstract())
  59                 continue;
  60             for(int j=0;j<updates.size();j++) {
  61                 Updates u2=(Updates)updates.get(j);
  62                 if (!u2.isExpr())
  63                     continue;
  64                 Descriptor d=u1.getDescriptor();
  65                 if (u2.getRightExpr().usesDescriptor(d)) {
  66                     /* Add edge for dependency */
  67                     GraphNode gn1=(GraphNode) mapping.get(u1);
  68                     GraphNode gn2=(GraphNode) mapping.get(u2);
  69                     GraphNode.Edge e=new GraphNode.Edge("dependency",gn2);
  70                     gn1.addEdge(e);
  71                 }
  72             }
  73         }
  74
  75         if (!GraphNode.DFS.depthFirstSearch(graph))  /* DFS & check for acyclicity */
  76             return false;
  77
  78         TreeSet topologicalsort = new TreeSet(new Comparator() {
  79                 public boolean equals(Object obj) { return false; }
  80                 public int compare(Object o1, Object o2) {
  81                     GraphNode g1 = (GraphNode) o1;
  82                     GraphNode g2 = (GraphNode) o2;
  83                     return g2.getFinishingTime() - g1.getFinishingTime();
  84                 }
  85             });
  86         topologicalsort.addAll(graph);
  87         Vector sortedvector=new Vector();
  88         for(Iterator sort=topologicalsort.iterator();sort.hasNext();) {
  89             GraphNode gn=(GraphNode)sort.next();
  90             sortedvector.add(gn.getOwner());
  91         }
  92         updates=sortedvector; //replace updates with the sorted array
  93         return true;
  94     }
  95
  96     private boolean checkconflicts() {
  97         Set toremove=new HashSet();
  98         for(int i=0;i<updates.size();i++) {
  99             Updates u1=(Updates)updates.get(i);
 100             for(int j=0;j<updates.size();j++) {
 101                 Updates u2=(Updates)updates.get(j);
 102                 if (i==j)
 103                     continue;
 104                 if (u1.isAbstract()||u2.isAbstract())
 105                     continue;  /* Abstract updates are already accounted for by graph */
 106                 if (u1.getDescriptor()!=u2.getDescriptor())
 107                     continue; /* No interference - different descriptors */
 108
 109                 if ((u1.getOpcode()==Opcode.GT||u1.getOpcode()==Opcode.GE)&&
 110                     (u2.getOpcode()==Opcode.GT||u2.getOpcode()==Opcode.GE))
 111                     continue; /* Can be satisfied simultaneously */
 112
 113                 if ((u1.getOpcode()==Opcode.LT||u1.getOpcode()==Opcode.LE)&&
 114                     (u2.getOpcode()==Opcode.LT||u2.getOpcode()==Opcode.LE))
 115                     continue;
 116                 if ((u1.getOpcode()==u2.getOpcode())&&
 117                     u1.isExpr()&&u2.isExpr()&&
 118                     u1.getRightExpr().equals(null, u2.getRightExpr())) {
 119                     /*We'll remove the second occurence*/
 120                     if (i>j)
 121                         toremove.add(u1);
 122                     else
 123                         toremove.add(u2);
 124                     continue;
 125                 }
 126
 127                 /* Handle = or != NULL */
 128                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 129                      ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 130                     (((u1.isExpr()&&u1.getRightExpr().isNull())&&(!u2.isExpr()||u2.getRightExpr().isNonNull()))
 131                      ||((!u1.isExpr()||u1.getRightExpr().isNonNull())&&(u2.isExpr()&&u2.getRightExpr().isNull())))) {
 132                     if (u1.getOpcode()==Opcode.NE)
 133                         toremove.add(u1);
 134                     else
 135                         toremove.add(u2);
 136                     continue;
 137                 }
 138
 139                 /* Handle = and != to different constants */
 140                 if ((((u1.getOpcode()==Opcode.EQ)&&(u2.getOpcode()==Opcode.NE))||
 141                     ((u1.getOpcode()==Opcode.NE)&&(u2.getOpcode()==Opcode.EQ)))&&
 142                     (u1.isExpr()&&u1.getRightExpr() instanceof LiteralExpr)&&
 143                     (u2.isExpr()&&u2.getRightExpr() instanceof LiteralExpr)&&
 144                     !u1.getRightExpr().equals(u2.getRightExpr())) {
 145                     if (u1.getOpcode()==Opcode.NE)
 146                         toremove.add(u1);
 147                     else
 148                         toremove.add(u2);
 149                     continue;
 150                 }
 151
 152                 /* Compatible operations < & <= */
 153                 if (((u1.getOpcode()==Opcode.LT)||(u1.getOpcode()==Opcode.LE))&&
 154                     ((u2.getOpcode()==Opcode.LT)||(u2.getOpcode()==Opcode.LE)))
 155                     continue;
 156
 157                 /* Compatible operations > & >= */
 158                 if (((u1.getOpcode()==Opcode.GT)||(u1.getOpcode()==Opcode.GE))&&
 159                     ((u2.getOpcode()==Opcode.GT)||(u2.getOpcode()==Opcode.GE)))
 160                     continue;
 161                 /* Ranges */
 162
 163                 //XXXXXX: TODO
 164                 /* Equality & Comparisons */
 165                 //XXXXXX: TODO
 166
 167                 return false; /* They interfere */
 168             }
 169         }
 170         updates.removeAll(toremove);
 171         return true;
 172     }
 173
 174     public void addBinding(Binding b) {
 175         bindings.add(b);
 176         binding.put(b.getVar(),b);
 177     }
 178
 179     public Binding getBinding(VarDescriptor vd) {
 180         if (binding.containsKey(vd))
 181             return (Binding)binding.get(vd);
 182         else
 183             return null;
 184     }
 185
 186     public void addUpdate(Updates u) {
 187         updates.add(u);
 188     }
 189
 190     public int numUpdates() {
 191         return updates.size();
 192     }
 193     public Updates getUpdate(int i) {
 194         return (Updates)updates.get(i);
 195     }
 196     public void generate(CodeWriter cr, boolean removal, String slot0, String slot1) {
 197         if (!removal)
 198             generate_bindings(cr, slot0,slot1);
 199         for(int i=0;i<updates.size();i++) {
 200             Updates u=(Updates)updates.get(i);
 201             VarDescriptor right=VarDescriptor.makeNew("right");
 202             if (u.getType()==Updates.ABSTRACT)
 203                 throw new Error("Abstract update not implemented");
 204
 205             switch(u.getType()) {
 206             case Updates.EXPR:
 207                 u.getRightExpr().generate(cr,right);
 208                 break;
 209             case Updates.POSITION:
 210                 if (u.getRightPos()==0)
 211                     cr.outputline("int "+right.getSafeSymbol()+"="+slot0+";");
 212                 else if (u.getRightPos()==1)
 213                     cr.outputline("int "+right.getSafeSymbol()+"="+slot1+";");
 214                 else throw new Error("Error w/ Position");
 215                 break;
 216             default:
 217                 throw new Error();
 218             }
 219             VarDescriptor left=VarDescriptor.makeNew("left");
 220             u.getLeftExpr().generate(cr,left);
 221             Opcode op=u.getOpcode();
 222             cr.outputline("if (!("+left.getSafeSymbol()+op+right.getSafeSymbol()+"))");
 223             cr.startblock();
 224
 225             if (op==Opcode.GT)
 226                 cr.outputline(right.getSafeSymbol()+"++;");
 227             else if (op==Opcode.GE)
 228                 ;
 229             else if (op==Opcode.EQ)
 230                 ;
 231             else if (op==Opcode.NE)
 232                 cr.outputline(right.getSafeSymbol()+"++;");
 233             else if (op==Opcode.LT)
 234                 cr.outputline(right.getSafeSymbol()+"--;");
 235             else if (op==Opcode.LE)
 236                 ;
 237             else throw new Error();
 238             if (u.isGlobal()) {
 239                 VarDescriptor vd=((VarExpr)u.getLeftExpr()).getVar();
 240                 cr.outputline(vd.getSafeSymbol()+"="+right.getSafeSymbol()+";");
 241             } else if (u.isField()) {
 242                 /* NEED TO FIX */
 243                 Expr subexpr=((DotExpr)u.getLeftExpr()).getExpr();
 244                 Expr intindex=((DotExpr)u.getLeftExpr()).getIndex();
 245                 VarDescriptor subvd=VarDescriptor.makeNew("subexpr");
 246                 VarDescriptor indexvd=VarDescriptor.makeNew("index");
 247                 subexpr.generate(cr,subvd);
 248                 if (intindex!=null)
 249                     intindex.generate(cr,indexvd);
 250                 FieldDescriptor fd=(FieldDescriptor)u.getDescriptor();
 251                 StructureTypeDescriptor std=(StructureTypeDescriptor)subexpr.getType();
 252                 if (fd instanceof ArrayDescriptor) {
 253                     fd = ((ArrayDescriptor) fd).getField();
 254                 }
 255
 256                 Expr offsetbits = std.getOffsetExpr(fd);
 257                 if (intindex != null) {
 258                     Expr basesize = fd.getBaseSizeExpr();
 259                     offsetbits = new OpExpr(Opcode.ADD, offsetbits, new OpExpr(Opcode.MULT, basesize, intindex));
 260                 }
 261                 Expr offsetbytes = new OpExpr(Opcode.SHR, offsetbits,new IntegerLiteralExpr(3));
 262                 Expr byteaddress=new OpExpr(Opcode.ADD, offsetbytes, subexpr);
 263                 VarDescriptor addr=VarDescriptor.makeNew("byteaddress");
 264                 byteaddress.generate(cr,addr);
 265
 266                 if (fd.getType() instanceof ReservedTypeDescriptor && !fd.getPtr()) {
 267                     ReservedTypeDescriptor rtd=(ReservedTypeDescriptor)fd.getType();
 268                     if (rtd==ReservedTypeDescriptor.INT) {
 269                         cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 270                     } else if (rtd==ReservedTypeDescriptor.SHORT) {
 271                         cr.outputline("*((short *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 272                     } else if (rtd==ReservedTypeDescriptor.BYTE) {
 273                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 274                     } else if (rtd==ReservedTypeDescriptor.BIT) {
 275                         Expr tmp = new OpExpr(Opcode.SHL, offsetbytes, new IntegerLiteralExpr(3));
 276                         Expr offset=new OpExpr(Opcode.SUB, offsetbits, tmp);
 277                         Expr mask=new OpExpr(Opcode.SHR, new IntegerLiteralExpr(1), offset);
 278                         VarDescriptor maskvar=VarDescriptor.makeNew("mask");
 279                         mask.generate(cr,maskvar);
 280                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")|="+maskvar.getSafeSymbol()+";");
 281                         cr.outputline("if (!"+right.getSafeSymbol()+")");
 282                         cr.outputline("*((char *) "+addr.getSafeSymbol()+")^="+maskvar.getSafeSymbol()+";");
 283                     } else throw new Error();
 284                 } else {
 285                     /* Pointer */
 286                     cr.outputline("*((int *) "+addr.getSafeSymbol()+")="+right.getSafeSymbol()+";");
 287                 }
 288             }
 289             cr.endblock();
 290         }
 291     }
 292
 293     private int bitmask(int bits) {
 294         int mask = 0;
 295
 296         for (int i = 0; i < bits; i++) {
 297             mask <<= 1;
 298             mask += 1;
 299         }
 300
 301         return mask;
 302     }
 303
 304     private void generate_bindings(CodeWriter cr, String slot0, String slot1) {
 305         for(int i=0;i<bindings.size();i++) {
 306             Binding b=(Binding)bindings.get(i);
 307             if (b.search)
 308                 throw new Error("Search not implemented for bindings");
 309             VarDescriptor vd=b.getVar();
 310             switch(b.getPosition()) {
 311             case 0:
 312                 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot0+";");
 313                 break;
 314             case 1:
 315                 cr.outputline(vd.getType().getGenerateType().getSafeSymbol()+" "+vd.getSafeSymbol()+"="+slot1+";");
 316                 break;
 317             default:
 318                 throw new Error("Slot >1 doesn't exist.");
 319             }
 320         }
 321     }
 322 }