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             name="("+name+")";
 197         }
 198         return name;
 199     }
 200
 201     public Opcode getOpcode() {
 202         return opcode;
 203     }
 204
 205     public boolean equals(Map remap, Expr e) {
 206         if (e==null||!(e instanceof OpExpr))
 207             return false;
 208         OpExpr oe=(OpExpr)e;
 209         if (opcode!=oe.opcode)
 210             return false;
 211         if (!left.equals(remap,oe.left))
 212             return false;
 213         if ((opcode!=Opcode.NOT)&&(opcode!=Opcode.RND)&&(opcode!=Opcode.NOP))
 214             if (!right.equals(remap,oe.right))
 215                 return false;
 216         return true;
 217     }
 218
 219     public DNFRule constructDNF() {
 220         if (opcode==Opcode.AND) {
 221             DNFRule leftd=left.constructDNF();
 222             DNFRule rightd=right.constructDNF();
 223             return leftd.and(rightd);
 224         } else if (opcode==Opcode.OR) {
 225             DNFRule leftd=left.constructDNF();
 226             DNFRule rightd=right.constructDNF();
 227             return leftd.or(rightd);
 228         } else if (opcode==Opcode.NOT) {
 229             DNFRule leftd=left.constructDNF();
 230             return leftd.not();
 231         } else return new DNFRule(this);
 232     }
 233
 234     public boolean usesDescriptor(Descriptor d) {
 235         return left.usesDescriptor(d)||(right!=null&&right.usesDescriptor(d));
 236     }
 237
 238     public void findmatch(Descriptor d, Set  s) {
 239         left.findmatch(d,s);
 240         if (right!=null)
 241             right.findmatch(d,s);
 242     }
 243
 244     public Set useDescriptor(Descriptor d) {
 245         HashSet newset=new HashSet();
 246         newset.addAll(left.useDescriptor(d));
 247         if (right!=null)
 248             newset.addAll(right.useDescriptor(d));
 249         return newset;
 250     }
 251
 252     public int[] getRepairs(boolean negated, Termination t) {
 253         if (left instanceof RelationExpr)
 254             return new int[] {AbstractRepair.MODIFYRELATION};
 255         if (left instanceof SizeofExpr) {
 256             Opcode op=opcode;
 257             if (negated) {
 258                 /* remove negation through opcode translation */
 259                 if (op==Opcode.GT)
 260                     op=Opcode.LE;
 261                 else if (op==Opcode.GE)
 262                     op=Opcode.LT;
 263                 else if (op==Opcode.EQ)
 264                     op=Opcode.NE;
 265                 else if (op==Opcode.NE)
 266                     op=Opcode.EQ;
 267                 else if (op==Opcode.LT)
 268                     op=Opcode.GE;
 269                 else if (op==Opcode.LE)
 270                     op=Opcode.GT;
 271             }
 272
 273             int maxsize=t.maxsize.getsize(getDescriptor());
 274             int size=getInt(right);
 275
 276
 277             boolean isRelation=((SizeofExpr)left).setexpr instanceof ImageSetExpr;
 278             if (isRelation) {
 279                 if (op==Opcode.EQ) {
 280                     if (size==0)
 281                         return new int[] {AbstractRepair.REMOVEFROMRELATION};
 282                     else {
 283                         if ((maxsize!=-1)&&maxsize<=size)
 284                             return new int[] {AbstractRepair.ADDTORELATION};
 285                         return new int[] {AbstractRepair.ADDTORELATION,
 286                                           AbstractRepair.REMOVEFROMRELATION};
 287                     }
 288                 } else if (op==Opcode.GE||op==Opcode.GT) {
 289                     return new int[]{AbstractRepair.ADDTORELATION};
 290                 } else if (op==Opcode.LE||op==Opcode.LT) {
 291                     if ((op==Opcode.LT&&maxsize!=-1&&maxsize<size)||(op==Opcode.LE&&maxsize!=-1&&maxsize<=size))
 292                         return new int[0];
 293                     return new int[]{AbstractRepair.REMOVEFROMRELATION};
 294                 } else if (op==Opcode.NE) {
 295                     if (maxsize<size&&maxsize!=-1)
 296                         return new int[0];
 297                     return new int[]{AbstractRepair.ADDTORELATION};
 298                 } else throw new Error();
 299             } else {
 300                 if (op==Opcode.EQ) {
 301                     if (size==0)
 302                         return new int[] {AbstractRepair.REMOVEFROMSET};
 303                     else {
 304                         if (maxsize<=size&&maxsize!=-1)
 305                             return new int[] {AbstractRepair.ADDTOSET};
 306                         return new int[] {AbstractRepair.ADDTOSET,
 307                                               AbstractRepair.REMOVEFROMSET};
 308                     }
 309                 } else if (op==Opcode.GE||op==Opcode.GT) {
 310                     return new int[] {AbstractRepair.ADDTOSET};
 311                 } else if (op==Opcode.LE||op==Opcode.LT) {
 312                     if ((op==Opcode.LT&&maxsize<size&&maxsize!=-1)||(op==Opcode.LE&&maxsize<=size&&maxsize!=-1))
 313                         return new int[0];
 314                     return new int[] {AbstractRepair.REMOVEFROMSET};
 315                 } else if (op==Opcode.NE) {
 316                     if (maxsize<size&&maxsize!=-1)
 317                         return new int[0];
 318                     return new int[] {AbstractRepair.ADDTOSET};
 319                 } else throw new Error();
 320             }
 321         }
 322         throw new Error("BAD");
 323     }
 324
 325     public Descriptor getDescriptor() {
 326         return left.getDescriptor();
 327     }
 328
 329     public boolean inverted() {
 330         return left.inverted();
 331     }
 332
 333     public Set getInversedRelations() {
 334         Set set = left.getInversedRelations();
 335         if (right != null) {
 336             set.addAll(right.getInversedRelations());
 337         }
 338         return set;
 339     }
 340
 341     public Set getRequiredDescriptors() {
 342         Set v = left.getRequiredDescriptors();
 343
 344         if (right != null) {
 345             v.addAll(right.getRequiredDescriptors());
 346         }
 347
 348         return v;
 349     }
 350
 351     public void generate(CodeWriter writer, VarDescriptor dest) {
 352         VarDescriptor ld = VarDescriptor.makeNew("leftop");
 353         /* Check for loop invariant hoisting. */
 354         if (writer.getInvariantValue()!=null&&
 355             writer.getInvariantValue().isInvariant(this)) {
 356             writer.addDeclaration("int",dest.getSafeSymbol());
 357             writer.outputline(dest.getSafeSymbol()+"="+writer.getInvariantValue().getValue(this).getSafeSymbol()+";");
 358             writer.outputline("maybe="+writer.getInvariantValue().getMaybe(this).getSafeSymbol()+";");
 359             return;
 360         }
 361
 362         left.generate(writer, ld);
 363         VarDescriptor rd = null;
 364         VarDescriptor lm=VarDescriptor.makeNew("lm");
 365         VarDescriptor rm=VarDescriptor.makeNew("rm");
 366
 367         if (right != null) {
 368             if ((opcode==Opcode.OR)||
 369                 (opcode==Opcode.AND)) {
 370                 writer.addDeclaration("int",lm.getSafeSymbol());
 371                 writer.outputline(lm.getSafeSymbol()+"=maybe;");
 372                 writer.outputline("maybe=0;");
 373             }
 374
 375             rd = VarDescriptor.makeNew("rightop");
 376             right.generate(writer, rd);
 377         }
 378
 379         String code;
 380         if (opcode == Opcode.RND) {
 381             writer.addDeclaration("int",dest.getSafeSymbol());
 382             writer.outputline(dest.getSafeSymbol() + " = (" +
 383                               ld.getSafeSymbol() + ">>3)<<3; ");
 384             writer.outputline("if ("+ld.getSafeSymbol()+" % 8) "+dest.getSafeSymbol()+"+=8;");
 385         } else if (opcode == Opcode.NOP) {
 386             writer.addDeclaration("int", dest.getSafeSymbol());
 387             writer.outputline(dest.getSafeSymbol() + " = " +
 388                               ld.getSafeSymbol() +"; ");
 389         } else if (opcode == Opcode.AND) {
 390             writer.addDeclaration("int",rm.getSafeSymbol());
 391             writer.outputline(rm.getSafeSymbol()+"=maybe;");
 392             writer.outputline("maybe = (" + ld.getSafeSymbol() + " && " + rm.getSafeSymbol() + ") || (" + rd.getSafeSymbol() + " && " + lm.getSafeSymbol() + ") || (" + lm.getSafeSymbol() + " && " + rm.getSafeSymbol() + ");");
 393             writer.addDeclaration("int",dest.getSafeSymbol());
 394             writer.outputline(dest.getSafeSymbol() + " = " + ld.getSafeSymbol() + " && " + rd.getSafeSymbol() + ";");
 395         } else if (opcode == Opcode.OR) {
 396             writer.addDeclaration("int",rm.getSafeSymbol());
 397             writer.outputline(rm.getSafeSymbol()+"=maybe;");
 398             writer.outputline("maybe = (!" + ld.getSafeSymbol() + " && " + rm.getSafeSymbol() + ") || (!" + rd.getSafeSymbol() +
 399                               " && " + lm.getSafeSymbol() + ") || (" + lm.getSafeSymbol() + " && " + rm.getSafeSymbol() + ");");
 400             writer.addDeclaration("int",dest.getSafeSymbol());
 401             writer.outputline(dest.getSafeSymbol() + " = " + ld.getSafeSymbol() + " || " + rd.getSafeSymbol() + ";");
 402         } else if (opcode != Opcode.NOT) { /* two operands */
 403             assert rd != null;
 404             writer.addDeclaration("int", dest.getSafeSymbol());
 405             writer.outputline(dest.getSafeSymbol() + " = " +
 406                               ld.getSafeSymbol() + " " + opcode.toString() + " " + rd.getSafeSymbol() + ";");
 407         } else if (opcode == Opcode.NOT) {
 408             writer.addDeclaration("int", dest.getSafeSymbol());
 409             writer.outputline(dest.getSafeSymbol() + " = !" + ld.getSafeSymbol() + ";");
 410         }
 411     }
 412
 413     public void prettyPrint(PrettyPrinter pp) {
 414         pp.output("(");
 415         if (opcode == Opcode.NOT) {
 416             pp.output("!(");
 417             left.prettyPrint(pp);
 418             pp.output(")");
 419         } else if (opcode == Opcode.NOP) {
 420             left.prettyPrint(pp);
 421         } else if (opcode == Opcode.RND) {
 422             pp.output("RND ");
 423             left.prettyPrint(pp);
 424         } else {
 425             left.prettyPrint(pp);
 426             pp.output(" " + opcode.toString() + " ");
 427             assert right != null;
 428             right.prettyPrint(pp);
 429         }
 430         pp.output(")");
 431     }
 432
 433     public TypeDescriptor typecheck(SemanticAnalyzer sa) {
 434         TypeDescriptor lt = left.typecheck(sa);
 435         TypeDescriptor rt = right == null ? null : right.typecheck(sa);
 436
 437         if (lt == null) {
 438             return null;
 439         } else if (right != null && rt == null) {
 440             return null;
 441         }
 442
 443         boolean ok = true;
 444
 445         if (!ok) {
 446             return null;
 447         }
 448
 449         this.td = ReservedTypeDescriptor.INT;
 450         return this.td;
 451     }
 452
 453 }