Repair/RepairCompiler/MCC/IR/OpExpr.java

   1 package MCC.IR;
   2
   3 import java.util.*;
   4
   5 public class OpExpr extends Expr {
   6
   7     Expr left;
   8     Expr right;
   9     Opcode opcode;
  10
  11     public Expr getUpper() {
  12         Expr lupper=left.getUpper();
  13         if (lupper==null)
  14             return null;
  15         if (right!=null) {
  16             Expr rupper=right.getUpper();
  17             if (rupper==null)
  18                 return null;
  19             OpExpr oe=new OpExpr(this.opcode,lupper,rupper);
  20             oe.td = ReservedTypeDescriptor.INT;
  21             return oe;
  22         } else return lupper;
  23     }
  24
  25     public Expr getLower() {
  26         Expr llower=left.getLower();
  27         if (llower==null)
  28             return null;
  29         if (right!=null) {
  30             Expr rlower=right.getLower();
  31             if (rlower==null)
  32                 return null;
  33             OpExpr oe=new OpExpr(this.opcode,llower,rlower);
  34             oe.td = ReservedTypeDescriptor.INT;
  35             return oe;
  36         } else return llower;
  37     }
  38
  39
  40     public boolean isSafe() {
  41         if (right==null)
  42             return left.isSafe();
  43         return left.isSafe()&&right.isSafe();
  44     }
  45
  46     public boolean isInvariant(Set vars) {
  47         return left.isInvariant(vars)&&((right==null)||right.isInvariant(vars));
  48     }
  49
  50     public Set findInvariants(Set vars) {
  51         if (isInt(this)) {
  52             /* Don't hoist ints */
  53             return new HashSet();
  54         } else if (isInvariant(vars)) {
  55             Set s=new HashSet();
  56             s.add(this);
  57             return s;
  58         } else {
  59             Set ls=left.findInvariants(vars);
  60             if (right!=null)
  61                 ls.addAll(right.findInvariants(vars));
  62             return ls;
  63         }
  64     }
  65
  66     public Set getfunctions() {
  67         Set leftfunctions=left.getfunctions();
  68         Set rightfunctions=null;
  69         if (right!=null) rightfunctions=right.getfunctions();
  70         if (leftfunctions!=null&&rightfunctions!=null) {
  71             HashSet functions=new HashSet();
  72             functions.addAll(leftfunctions);
  73             functions.addAll(rightfunctions);
  74             return functions;
  75         }
  76         if (leftfunctions!=null)
  77             return leftfunctions;
  78         return rightfunctions;
  79     }
  80
  81     public static boolean isInt(Expr e) {
  82         if (e==null)
  83             return false;
  84         if ((e instanceof IntegerLiteralExpr)||
  85             ((e instanceof OpExpr)&&(((OpExpr)e).opcode==Opcode.NOP)&&(((OpExpr)e).getLeftExpr() instanceof IntegerLiteralExpr)))
  86             return true;
  87         return false;
  88     }
  89
  90     public static int getInt(Expr e) {
  91         if (e instanceof IntegerLiteralExpr)
  92             return ((IntegerLiteralExpr)e).getValue();
  93         else if ((e instanceof OpExpr) && (((OpExpr)e).getLeftExpr() instanceof IntegerLiteralExpr))
  94             return ((IntegerLiteralExpr)((OpExpr)e).getLeftExpr()).getValue();
  95         else throw new Error();
  96     }
  97
  98     public OpExpr(Opcode opcode, Expr left, Expr right) {
  99         if ((isInt(left)&&isInt(right))||
 100             (isInt(left)&&(opcode==Opcode.NOT))||
 101             (isInt(left)&&(opcode==Opcode.RND))) {
 102             this.opcode=Opcode.NOP;
 103             this.right=null;
 104             int lint=isInt(left)?getInt(left):0;
 105             int rint=isInt(right)?getInt(right):0;
 106             int value=0;
 107             if (opcode==Opcode.ADD) {
 108                 value=lint+rint;
 109             } else if (opcode==Opcode.SUB) {
 110                 value=lint-rint;
 111             } else if (opcode==Opcode.SHL) {
 112                 value=lint<<rint;
 113             } else if (opcode==Opcode.SHR) {
 114                 value=lint>>rint;
 115             } else if (opcode==Opcode.MULT) {
 116                 value=lint*rint;
 117             } else if (opcode==Opcode.DIV) {
 118                 value=lint/rint;
 119             } else if (opcode==Opcode.GT) {
 120                 if (lint>rint)
 121                     value=1;
 122             } else if (opcode==Opcode.GE) {
 123                 if (lint>=rint)
 124                     value=1;
 125             } else if (opcode==Opcode.LT) {
 126                 if (lint<rint)
 127                     value=1;
 128             } else if (opcode==Opcode.LE) {
 129                 if (lint<=rint)
 130                     value=1;
 131             } else if (opcode==Opcode.EQ) {
 132                 if (lint==rint)
 133                     value=1;
 134             } else if (opcode==Opcode.NE) {
 135                 if (lint!=rint)
 136                     value=1;
 137             } else if (opcode==Opcode.AND) {
 138                 if ((lint!=0)&&(rint!=0))
 139                     value=1;
 140             } else if (opcode==Opcode.OR) {
 141                 if ((lint!=0)||(rint!=0))
 142                     value=1;
 143             } else if (opcode==Opcode.NOT) {
 144                 if (lint==0)
 145                     value=1;
 146             } else if (opcode==Opcode.RND) {
 147                 value=((lint>>3)<<3);
 148                 if ((lint % 8)!=0)
 149                     value+=8;
 150             } else throw new Error("Unrecognized Opcode");
 151             this.left=new IntegerLiteralExpr(value);
 152         } else if ((opcode==Opcode.MULT)&&
 153                    ((isInt(left)&&(getInt(left)==0))
 154                     ||(isInt(right)&&(getInt(right)==0)))) {
 155             this.opcode=Opcode.NOP;
 156             this.right=null;
 157             this.left=new IntegerLiteralExpr(0);
 158         } else {
 159             this.opcode = opcode;
 160             this.left = left;
 161             this.right = right;
 162             assert (right == null && (opcode == Opcode.NOT||opcode==Opcode.RND)) || (right != null);
 163         }
 164     }
 165
 166     public Expr getRightExpr() {
 167         return right;
 168     }
 169
 170     public Expr getLeftExpr() {
 171         return left;
 172     }
 173
 174     public Set freeVars() {
 175         Set lset=left.freeVars();
 176         Set rset=null;
 177         if (right!=null)
 178             rset=right.freeVars();
 179         if (lset==null)
 180             return rset;
 181         if (rset!=null)
 182             lset.addAll(rset);
 183         return lset;
 184     }
 185
 186     public String name() {
 187         if (opcode==Opcode.NOT)
 188             return "!("+left.name()+")";
 189         if (opcode==Opcode.NOP)
 190             return left.name();
 191         if (opcode==Opcode.RND)
 192             return "Round("+left.name()+")";
 193         String name=left.name()+opcode.toString();
 194         if (right!=null)
 195             name+=right.name();
 196         return name;
 197     }
 198
 199     public Opcode getOpcode() {
 200         return opcode;
 201     }
 202
 203     public boolean equals(Map remap, Expr e) {
 204         if (e==null||!(e instanceof OpExpr))
 205             return false;
 206         OpExpr oe=(OpExpr)e;
 207         if (opcode!=oe.opcode)
 208             return false;
 209         if (!left.equals(remap,oe.left))
 210             return false;
 211         if ((opcode!=Opcode.NOT)&&(opcode!=Opcode.RND)&&(opcode!=Opcode.NOP))
 212             if (!right.equals(remap,oe.right))
 213                 return false;
 214         return true;
 215     }
 216
 217     public DNFRule constructDNF() {
 218         if (opcode==Opcode.AND) {
 219             DNFRule leftd=left.constructDNF();
 220             DNFRule rightd=right.constructDNF();
 221             return leftd.and(rightd);
 222         } else if (opcode==Opcode.OR) {
 223             DNFRule leftd=left.constructDNF();
 224             DNFRule rightd=right.constructDNF();
 225             return leftd.or(rightd);
 226         } else if (opcode==Opcode.NOT) {
 227             DNFRule leftd=left.constructDNF();
 228             return leftd.not();
 229         } else return new DNFRule(this);
 230     }
 231
 232     public boolean usesDescriptor(Descriptor d) {
 233         return left.usesDescriptor(d)||(right!=null&&right.usesDescriptor(d));
 234     }
 235
 236     public void findmatch(Descriptor d, Set  s) {
 237         left.findmatch(d,s);
 238         if (right!=null)
 239             right.findmatch(d,s);
 240     }
 241
 242     public Set useDescriptor(Descriptor d) {
 243         HashSet newset=new HashSet();
 244         newset.addAll(left.useDescriptor(d));
 245         if (right!=null)
 246             newset.addAll(right.useDescriptor(d));
 247         return newset;
 248     }
 249
 250     public int[] getRepairs(boolean negated, Termination t) {
 251         if (left instanceof RelationExpr)
 252             return new int[] {AbstractRepair.MODIFYRELATION};
 253         if (left instanceof SizeofExpr) {
 254             Opcode op=opcode;
 255             if (negated) {
 256                 /* remove negation through opcode translation */
 257                 if (op==Opcode.GT)
 258                     op=Opcode.LE;
 259                 else if (op==Opcode.GE)
 260                     op=Opcode.LT;
 261                 else if (op==Opcode.EQ)
 262                     op=Opcode.NE;
 263                 else if (op==Opcode.NE)
 264                     op=Opcode.EQ;
 265                 else if (op==Opcode.LT)
 266                     op=Opcode.GE;
 267                 else if (op==Opcode.LE)
 268                     op=Opcode.GT;
 269             }
 270
 271             int maxsize=t.maxsize.getsize(getDescriptor());
 272             int size=getInt(right);
 273
 274
 275             boolean isRelation=((SizeofExpr)left).setexpr instanceof ImageSetExpr;
 276             if (isRelation) {
 277                 if (op==Opcode.EQ) {
 278                     if (size==0)
 279                         return new int[] {AbstractRepair.REMOVEFROMRELATION};
 280                     else {
 281                         if ((maxsize!=-1)&&maxsize<=size)
 282                             return new int[] {AbstractRepair.ADDTORELATION};
 283                         return new int[] {AbstractRepair.ADDTORELATION,
 284                                           AbstractRepair.REMOVEFROMRELATION};
 285                     }
 286                 } else if (op==Opcode.GE||op==Opcode.GT) {
 287                     return new int[]{AbstractRepair.ADDTORELATION};
 288                 } else if (op==Opcode.LE||op==Opcode.LT) {
 289                     if ((op==Opcode.LT&&maxsize!=-1&&maxsize<size)||(op==Opcode.LE&&maxsize!=-1&&maxsize<=size))
 290                         return new int[0];
 291                     return new int[]{AbstractRepair.REMOVEFROMRELATION};
 292                 } else if (op==Opcode.NE) {
 293                     if (maxsize<size&&maxsize!=-1)
 294                         return new int[0];
 295                     return new int[]{AbstractRepair.ADDTORELATION};
 296                 } else throw new Error();
 297             } else {
 298                 if (op==Opcode.EQ) {
 299                     if (size==0)
 300                         return new int[] {AbstractRepair.REMOVEFROMSET};
 301                     else {
 302                         if (maxsize<=size&&maxsize!=-1)
 303                             return new int[] {AbstractRepair.ADDTOSET};
 304                         return new int[] {AbstractRepair.ADDTOSET,
 305                                               AbstractRepair.REMOVEFROMSET};
 306                     }
 307                 } else if (op==Opcode.GE||op==Opcode.GT) {
 308                     return new int[] {AbstractRepair.ADDTOSET};
 309                 } else if (op==Opcode.LE||op==Opcode.LT) {
 310                     if ((op==Opcode.LT&&maxsize<size&&maxsize!=-1)||(op==Opcode.LE&&maxsize<=size&&maxsize!=-1))
 311                         return new int[0];
 312                     return new int[] {AbstractRepair.REMOVEFROMSET};
 313                 } else if (op==Opcode.NE) {
 314                     if (maxsize<size&&maxsize!=-1)
 315                         return new int[0];
 316                     return new int[] {AbstractRepair.ADDTOSET};
 317                 } else throw new Error();
 318             }
 319         }
 320         throw new Error("BAD");
 321     }
 322
 323     public Descriptor getDescriptor() {
 324         return left.getDescriptor();
 325     }
 326
 327     public boolean inverted() {
 328         return left.inverted();
 329     }
 330
 331     public Set getInversedRelations() {
 332         Set set = left.getInversedRelations();
 333         if (right != null) {
 334             set.addAll(right.getInversedRelations());
 335         }
 336         return set;
 337     }
 338
 339     public Set getRequiredDescriptors() {
 340         Set v = left.getRequiredDescriptors();
 341
 342         if (right != null) {
 343             v.addAll(right.getRequiredDescriptors());
 344         }
 345
 346         return v;
 347     }
 348
 349     public void generate(CodeWriter writer, VarDescriptor dest) {
 350         VarDescriptor ld = VarDescriptor.makeNew("leftop");
 351         if (writer.getInvariantValue()!=null&&
 352             writer.getInvariantValue().isInvariant(this)) {
 353             writer.outputline("maybe="+writer.getInvariantValue().getMaybe(this).getSafeSymbol()+";");
 354             writer.outputline("int "+dest.getSafeSymbol()+"="+writer.getInvariantValue().getValue(this).getSafeSymbol()+";");
 355             return;
 356         }
 357
 358         left.generate(writer, ld);
 359         VarDescriptor rd = null;
 360         VarDescriptor lm=VarDescriptor.makeNew("lm");
 361         VarDescriptor rm=VarDescriptor.makeNew("rm");
 362
 363         if (right != null) {
 364             if ((opcode==Opcode.OR)||
 365                 (opcode==Opcode.AND)) {
 366                 writer.outputline("int "+lm.getSafeSymbol()+"=maybe;");
 367                 writer.outputline("maybe=0;");
 368             }
 369
 370             rd = VarDescriptor.makeNew("rightop");
 371             right.generate(writer, rd);
 372         }
 373
 374         String code;
 375         if (opcode == Opcode.RND) {
 376             writer.outputline("int " +dest.getSafeSymbol() + " = (" +
 377                               ld.getSafeSymbol() + ">>3)<<3; ");
 378             writer.outputline("if ("+ld.getSafeSymbol()+" % 8) "+dest.getSafeSymbol()+"+=8;");
 379         } else if (opcode == Opcode.NOP) {
 380             writer.outputline("int " +dest.getSafeSymbol() + " = " +
 381                               ld.getSafeSymbol() +"; ");
 382         } else if (opcode == Opcode.AND) {
 383             writer.outputline("int "+rm.getSafeSymbol()+"=maybe;");
 384             writer.outputline("maybe = (" + ld.getSafeSymbol() + " && " + rm.getSafeSymbol() + ") || (" + rd.getSafeSymbol() + " && " + lm.getSafeSymbol() + ") || (" + lm.getSafeSymbol() + " && " + rm.getSafeSymbol() + ");");
 385             writer.outputline("int "+dest.getSafeSymbol() + " = " + ld.getSafeSymbol() + " && " + rd.getSafeSymbol() + ";");
 386         } else if (opcode == Opcode.OR) {
 387             writer.outputline("int "+rm.getSafeSymbol()+"=maybe;");
 388             writer.outputline("maybe = (!" + ld.getSafeSymbol() + " && " + rm.getSafeSymbol() + ") || (!" + rd.getSafeSymbol() +
 389                               " && " + lm.getSafeSymbol() + ") || (" + lm.getSafeSymbol() + " && " + rm.getSafeSymbol() + ");");
 390             writer.outputline("int "+dest.getSafeSymbol() + " = " + ld.getSafeSymbol() + " || " + rd.getSafeSymbol() + ";");
 391         } else if (opcode != Opcode.NOT) { /* two operands */
 392             assert rd != null;
 393             writer.outputline("int " + dest.getSafeSymbol() + " = " +
 394                               ld.getSafeSymbol() + " " + opcode.toString() + " " + rd.getSafeSymbol() + ";");
 395         } else if (opcode == Opcode.NOT) {
 396             writer.outputline("int " + dest.getSafeSymbol() + " = !" + ld.getSafeSymbol() + ";");
 397         }
 398     }
 399
 400     public void prettyPrint(PrettyPrinter pp) {
 401         pp.output("(");
 402         if (opcode == Opcode.NOT) {
 403             pp.output("!");
 404             left.prettyPrint(pp);
 405         } else if (opcode == Opcode.NOP) {
 406             left.prettyPrint(pp);
 407         } else if (opcode == Opcode.RND) {
 408             pp.output("RND ");
 409             left.prettyPrint(pp);
 410         } else {
 411             left.prettyPrint(pp);
 412             pp.output(" " + opcode.toString() + " ");
 413             assert right != null;
 414             right.prettyPrint(pp);
 415         }
 416         pp.output(")");
 417     }
 418
 419     public TypeDescriptor typecheck(SemanticAnalyzer sa) {
 420         TypeDescriptor lt = left.typecheck(sa);
 421         TypeDescriptor rt = right == null ? null : right.typecheck(sa);
 422
 423         if (lt == null) {
 424             return null;
 425         } else if (right != null && rt == null) {
 426             return null;
 427         }
 428
 429         boolean ok = true;
 430
 431         if (!ok) {
 432             return null;
 433         }
 434
 435         this.td = ReservedTypeDescriptor.INT;
 436         return this.td;
 437     }
 438
 439 }