lib/Transforms/Scalar/InstructionCombining.cpp

   1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
   2 //
   3 // InstructionCombining - Combine instructions to form fewer, simple
   4 // instructions.  This pass does not modify the CFG This pass is where algebraic
   5 // simplification happens.
   6 //
   7 // This pass combines things like:
   8 //    %Y = add int 1, %X
   9 //    %Z = add int 1, %Y
  10 // into:
  11 //    %Z = add int 2, %X
  12 //
  13 // This is a simple worklist driven algorithm.
  14 //
  15 // This pass guarantees that the following canonicalizations are performed on
  16 // the program:
  17 //    1. If a binary operator has a constant operand, it is moved to the RHS
  18 //    2. Bitwise operators with constant operands are always grouped so that
  19 //       shifts are performed first, then or's, then and's, then xor's.
  20 //    3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible
  21 //    4. All SetCC instructions on boolean values are replaced with logical ops
  22 //    5. add X, X is represented as (X*2) => (X << 1)
  23 //    6. Multiplies with a power-of-two constant argument are transformed into
  24 //       shifts.
  25 //    N. This list is incomplete
  26 //
  27 //===----------------------------------------------------------------------===//
  28
  29 #include "llvm/Transforms/Scalar.h"
  30 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  31 #include "llvm/Transforms/Utils/Local.h"
  32 #include "llvm/Instructions.h"
  33 #include "llvm/Pass.h"
  34 #include "llvm/Constants.h"
  35 #include "llvm/ConstantHandling.h"
  36 #include "llvm/DerivedTypes.h"
  37 #include "llvm/GlobalVariable.h"
  38 #include "llvm/Support/InstIterator.h"
  39 #include "llvm/Support/InstVisitor.h"
  40 #include "llvm/Support/CallSite.h"
  41 #include "Support/Statistic.h"
  42 #include <algorithm>
  43
  44 namespace {
  45   Statistic<> NumCombined ("instcombine", "Number of insts combined");
  46   Statistic<> NumConstProp("instcombine", "Number of constant folds");
  47   Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
  48
  49   class InstCombiner : public FunctionPass,
  50                        public InstVisitor<InstCombiner, Instruction*> {
  51     // Worklist of all of the instructions that need to be simplified.
  52     std::vector<Instruction*> WorkList;
  53
  54     void AddUsesToWorkList(Instruction &I) {
  55       // The instruction was simplified, add all users of the instruction to
  56       // the work lists because they might get more simplified now...
  57       //
  58       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
  59            UI != UE; ++UI)
  60         WorkList.push_back(cast<Instruction>(*UI));
  61     }
  62
  63     // removeFromWorkList - remove all instances of I from the worklist.
  64     void removeFromWorkList(Instruction *I);
  65   public:
  66     virtual bool runOnFunction(Function &F);
  67
  68     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  69       AU.setPreservesCFG();
  70     }
  71
  72     // Visitation implementation - Implement instruction combining for different
  73     // instruction types.  The semantics are as follows:
  74     // Return Value:
  75     //    null        - No change was made
  76     //     I          - Change was made, I is still valid, I may be dead though
  77     //   otherwise    - Change was made, replace I with returned instruction
  78     //
  79     Instruction *visitAdd(BinaryOperator &I);
  80     Instruction *visitSub(BinaryOperator &I);
  81     Instruction *visitMul(BinaryOperator &I);
  82     Instruction *visitDiv(BinaryOperator &I);
  83     Instruction *visitRem(BinaryOperator &I);
  84     Instruction *visitAnd(BinaryOperator &I);
  85     Instruction *visitOr (BinaryOperator &I);
  86     Instruction *visitXor(BinaryOperator &I);
  87     Instruction *visitSetCondInst(BinaryOperator &I);
  88     Instruction *visitShiftInst(ShiftInst &I);
  89     Instruction *visitCastInst(CastInst &CI);
  90     Instruction *visitCallInst(CallInst &CI);
  91     Instruction *visitInvokeInst(InvokeInst &II);
  92     Instruction *visitPHINode(PHINode &PN);
  93     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
  94     Instruction *visitAllocationInst(AllocationInst &AI);
  95     Instruction *visitLoadInst(LoadInst &LI);
  96     Instruction *visitBranchInst(BranchInst &BI);
  97
  98     // visitInstruction - Specify what to return for unhandled instructions...
  99     Instruction *visitInstruction(Instruction &I) { return 0; }
 100
 101   private:
 102     bool transformConstExprCastCall(CallSite CS);
 103
 104     // InsertNewInstBefore - insert an instruction New before instruction Old
 105     // in the program.  Add the new instruction to the worklist.
 106     //
 107     void InsertNewInstBefore(Instruction *New, Instruction &Old) {
 108       assert(New && New->getParent() == 0 &&
 109              "New instruction already inserted into a basic block!");
 110       BasicBlock *BB = Old.getParent();
 111       BB->getInstList().insert(&Old, New);  // Insert inst
 112       WorkList.push_back(New);              // Add to worklist
 113     }
 114
 115   public:
 116     // ReplaceInstUsesWith - This method is to be used when an instruction is
 117     // found to be dead, replacable with another preexisting expression.  Here
 118     // we add all uses of I to the worklist, replace all uses of I with the new
 119     // value, then return I, so that the inst combiner will know that I was
 120     // modified.
 121     //
 122     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
 123       AddUsesToWorkList(I);         // Add all modified instrs to worklist
 124       I.replaceAllUsesWith(V);
 125       return &I;
 126     }
 127   private:
 128     /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
 129     /// InsertBefore instruction.  This is specialized a bit to avoid inserting
 130     /// casts that are known to not do anything...
 131     ///
 132     Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
 133                                    Instruction *InsertBefore);
 134
 135     // SimplifyCommutative - This performs a few simplifications for commutative
 136     // operators...
 137     bool SimplifyCommutative(BinaryOperator &I);
 138   };
 139
 140   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
 141 }
 142
 143 // getComplexity:  Assign a complexity or rank value to LLVM Values...
 144 //   0 -> Constant, 1 -> Other, 2 -> Argument, 2 -> Unary, 3 -> OtherInst
 145 static unsigned getComplexity(Value *V) {
 146   if (isa<Instruction>(V)) {
 147     if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
 148       return 2;
 149     return 3;
 150   }
 151   if (isa<Argument>(V)) return 2;
 152   return isa<Constant>(V) ? 0 : 1;
 153 }
 154
 155 // isOnlyUse - Return true if this instruction will be deleted if we stop using
 156 // it.
 157 static bool isOnlyUse(Value *V) {
 158   return V->use_size() == 1 || isa<Constant>(V);
 159 }
 160
 161 // SimplifyCommutative - This performs a few simplifications for commutative
 162 // operators:
 163 //
 164 //  1. Order operands such that they are listed from right (least complex) to
 165 //     left (most complex).  This puts constants before unary operators before
 166 //     binary operators.
 167 //
 168 //  2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
 169 //  3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 170 //
 171 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
 172   bool Changed = false;
 173   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
 174     Changed = !I.swapOperands();
 175
 176   if (!I.isAssociative()) return Changed;
 177   Instruction::BinaryOps Opcode = I.getOpcode();
 178   if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
 179     if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
 180       if (isa<Constant>(I.getOperand(1))) {
 181         Constant *Folded = ConstantExpr::get(I.getOpcode(),
 182                                              cast<Constant>(I.getOperand(1)),
 183                                              cast<Constant>(Op->getOperand(1)));
 184         I.setOperand(0, Op->getOperand(0));
 185         I.setOperand(1, Folded);
 186         return true;
 187       } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
 188         if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
 189             isOnlyUse(Op) && isOnlyUse(Op1)) {
 190           Constant *C1 = cast<Constant>(Op->getOperand(1));
 191           Constant *C2 = cast<Constant>(Op1->getOperand(1));
 192
 193           // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 194           Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
 195           Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
 196                                                     Op1->getOperand(0),
 197                                                     Op1->getName(), &I);
 198           WorkList.push_back(New);
 199           I.setOperand(0, New);
 200           I.setOperand(1, Folded);
 201           return true;
 202         }
 203     }
 204   return Changed;
 205 }
 206
 207 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
 208 // if the LHS is a constant zero (which is the 'negate' form).
 209 //
 210 static inline Value *dyn_castNegVal(Value *V) {
 211   if (BinaryOperator::isNeg(V))
 212     return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
 213
 214   // Constants can be considered to be negated values if they can be folded...
 215   if (Constant *C = dyn_cast<Constant>(V))
 216     return ConstantExpr::get(Instruction::Sub,
 217                              Constant::getNullValue(V->getType()), C);
 218   return 0;
 219 }
 220
 221 static inline Value *dyn_castNotVal(Value *V) {
 222   if (BinaryOperator::isNot(V))
 223     return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
 224
 225   // Constants can be considered to be not'ed values...
 226   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
 227     return ConstantExpr::get(Instruction::Xor,
 228                              ConstantIntegral::getAllOnesValue(C->getType()),C);
 229   return 0;
 230 }
 231
 232 // dyn_castFoldableMul - If this value is a multiply that can be folded into
 233 // other computations (because it has a constant operand), return the
 234 // non-constant operand of the multiply.
 235 //
 236 static inline Value *dyn_castFoldableMul(Value *V) {
 237   if (V->use_size() == 1 && V->getType()->isInteger())
 238     if (Instruction *I = dyn_cast<Instruction>(V))
 239       if (I->getOpcode() == Instruction::Mul)
 240         if (isa<Constant>(I->getOperand(1)))
 241           return I->getOperand(0);
 242   return 0;
 243 }
 244
 245 // dyn_castMaskingAnd - If this value is an And instruction masking a value with
 246 // a constant, return the constant being anded with.
 247 //
 248 template<class ValueType>
 249 static inline Constant *dyn_castMaskingAnd(ValueType *V) {
 250   if (Instruction *I = dyn_cast<Instruction>(V))
 251     if (I->getOpcode() == Instruction::And)
 252       return dyn_cast<Constant>(I->getOperand(1));
 253
 254   // If this is a constant, it acts just like we were masking with it.
 255   return dyn_cast<Constant>(V);
 256 }
 257
 258 // Log2 - Calculate the log base 2 for the specified value if it is exactly a
 259 // power of 2.
 260 static unsigned Log2(uint64_t Val) {
 261   assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!");
 262   unsigned Count = 0;
 263   while (Val != 1) {
 264     if (Val & 1) return 0;    // Multiple bits set?
 265     Val >>= 1;
 266     ++Count;
 267   }
 268   return Count;
 269 }
 270
 271
 272 /// AssociativeOpt - Perform an optimization on an associative operator.  This
 273 /// function is designed to check a chain of associative operators for a
 274 /// potential to apply a certain optimization.  Since the optimization may be
 275 /// applicable if the expression was reassociated, this checks the chain, then
 276 /// reassociates the expression as necessary to expose the optimization
 277 /// opportunity.  This makes use of a special Functor, which must define
 278 /// 'shouldApply' and 'apply' methods.
 279 ///
 280 template<typename Functor>
 281 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) {
 282   unsigned Opcode = Root.getOpcode();
 283   Value *LHS = Root.getOperand(0);
 284
 285   // Quick check, see if the immediate LHS matches...
 286   if (F.shouldApply(LHS))
 287     return F.apply(Root);
 288
 289   // Otherwise, if the LHS is not of the same opcode as the root, return.
 290   Instruction *LHSI = dyn_cast<Instruction>(LHS);
 291   while (LHSI && LHSI->getOpcode() == Opcode && LHSI->use_size() == 1) {
 292     // Should we apply this transform to the RHS?
 293     bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
 294
 295     // If not to the RHS, check to see if we should apply to the LHS...
 296     if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) {
 297       cast<BinaryOperator>(LHSI)->swapOperands();   // Make the LHS the RHS
 298       ShouldApply = true;
 299     }
 300
 301     // If the functor wants to apply the optimization to the RHS of LHSI,
 302     // reassociate the expression from ((? op A) op B) to (? op (A op B))
 303     if (ShouldApply) {
 304       BasicBlock *BB = Root.getParent();
 305       // All of the instructions have a single use and have no side-effects,
 306       // because of this, we can pull them all into the current basic block.
 307       if (LHSI->getParent() != BB) {
 308         // Move all of the instructions from root to LHSI into the current
 309         // block.
 310         Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
 311         Instruction *LastUse = &Root;
 312         while (TmpLHSI->getParent() == BB) {
 313           LastUse = TmpLHSI;
 314           TmpLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
 315         }
 316
 317         // Loop over all of the instructions in other blocks, moving them into
 318         // the current one.
 319         Value *TmpLHS = TmpLHSI;
 320         do {
 321           TmpLHSI = cast<Instruction>(TmpLHS);
 322           // Remove from current block...
 323           TmpLHSI->getParent()->getInstList().remove(TmpLHSI);
 324           // Insert before the last instruction...
 325           BB->getInstList().insert(LastUse, TmpLHSI);
 326           TmpLHS = TmpLHSI->getOperand(0);
 327         } while (TmpLHSI != LHSI);
 328       }
 329
 330       // Now all of the instructions are in the current basic block, go ahead
 331       // and perform the reassociation.
 332       Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
 333
 334       // First move the selected RHS to the LHS of the root...
 335       Root.setOperand(0, LHSI->getOperand(1));
 336
 337       // Make what used to be the LHS of the root be the user of the root...
 338       Value *ExtraOperand = TmpLHSI->getOperand(1);
 339       Root.replaceAllUsesWith(TmpLHSI);          // Users now use TmpLHSI
 340       TmpLHSI->setOperand(1, &Root);             // TmpLHSI now uses the root
 341       BB->getInstList().remove(&Root);           // Remove root from the BB
 342       BB->getInstList().insert(TmpLHSI, &Root);  // Insert root before TmpLHSI
 343
 344       // Now propagate the ExtraOperand down the chain of instructions until we
 345       // get to LHSI.
 346       while (TmpLHSI != LHSI) {
 347         Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
 348         Value *NextOp = NextLHSI->getOperand(1);
 349         NextLHSI->setOperand(1, ExtraOperand);
 350         TmpLHSI = NextLHSI;
 351         ExtraOperand = NextOp;
 352       }
 353
 354       // Now that the instructions are reassociated, have the functor perform
 355       // the transformation...
 356       return F.apply(Root);
 357     }
 358
 359     LHSI = dyn_cast<Instruction>(LHSI->getOperand(0));
 360   }
 361   return 0;
 362 }
 363
 364
 365 // AddRHS - Implements: X + X --> X << 1
 366 struct AddRHS {
 367   Value *RHS;
 368   AddRHS(Value *rhs) : RHS(rhs) {}
 369   bool shouldApply(Value *LHS) const { return LHS == RHS; }
 370   Instruction *apply(BinaryOperator &Add) const {
 371     return new ShiftInst(Instruction::Shl, Add.getOperand(0),
 372                          ConstantInt::get(Type::UByteTy, 1));
 373   }
 374 };
 375
 376 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2)
 377 //                 iff C1&C2 == 0
 378 struct AddMaskingAnd {
 379   Constant *C2;
 380   AddMaskingAnd(Constant *c) : C2(c) {}
 381   bool shouldApply(Value *LHS) const {
 382     if (Constant *C1 = dyn_castMaskingAnd(LHS))
 383       return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue();
 384     return false;
 385   }
 386   Instruction *apply(BinaryOperator &Add) const {
 387     return BinaryOperator::create(Instruction::Or, Add.getOperand(0),
 388                                   Add.getOperand(1));
 389   }
 390 };
 391
 392
 393
 394 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 395   bool Changed = SimplifyCommutative(I);
 396   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 397
 398   // X + 0 --> X
 399   if (RHS == Constant::getNullValue(I.getType()))
 400     return ReplaceInstUsesWith(I, LHS);
 401
 402   // X + X --> X << 1
 403   if (I.getType()->isInteger())
 404     if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
 405
 406   // -A + B  -->  B - A
 407   if (Value *V = dyn_castNegVal(LHS))
 408     return BinaryOperator::create(Instruction::Sub, RHS, V);
 409
 410   // A + -B  -->  A - B
 411   if (!isa<Constant>(RHS))
 412     if (Value *V = dyn_castNegVal(RHS))
 413       return BinaryOperator::create(Instruction::Sub, LHS, V);
 414
 415   // X*C + X --> X * (C+1)
 416   if (dyn_castFoldableMul(LHS) == RHS) {
 417     Constant *CP1 =
 418       ConstantExpr::get(Instruction::Add,
 419                         cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
 420                         ConstantInt::get(I.getType(), 1));
 421     return BinaryOperator::create(Instruction::Mul, RHS, CP1);
 422   }
 423
 424   // X + X*C --> X * (C+1)
 425   if (dyn_castFoldableMul(RHS) == LHS) {
 426     Constant *CP1 =
 427       ConstantExpr::get(Instruction::Add,
 428                         cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
 429                         ConstantInt::get(I.getType(), 1));
 430     return BinaryOperator::create(Instruction::Mul, LHS, CP1);
 431   }
 432
 433   // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
 434   if (Constant *C2 = dyn_castMaskingAnd(RHS))
 435     if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
 436
 437   return Changed ? &I : 0;
 438 }
 439
 440 // isSignBit - Return true if the value represented by the constant only has the
 441 // highest order bit set.
 442 static bool isSignBit(ConstantInt *CI) {
 443   unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
 444   return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1));
 445 }
 446
 447 static unsigned getTypeSizeInBits(const Type *Ty) {
 448   return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8;
 449 }
 450
 451 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 452   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 453
 454   if (Op0 == Op1)         // sub X, X  -> 0
 455     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 456
 457   // If this is a 'B = x-(-A)', change to B = x+A...
 458   if (Value *V = dyn_castNegVal(Op1))
 459     return BinaryOperator::create(Instruction::Add, Op0, V);
 460
 461   // Replace (-1 - A) with (~A)...
 462   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0))
 463     if (C->isAllOnesValue())
 464       return BinaryOperator::createNot(Op1);
 465
 466   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
 467     if (Op1I->use_size() == 1) {
 468       // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
 469       // is not used by anyone else...
 470       //
 471       if (Op1I->getOpcode() == Instruction::Sub) {
 472         // Swap the two operands of the subexpr...
 473         Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 474         Op1I->setOperand(0, IIOp1);
 475         Op1I->setOperand(1, IIOp0);
 476
 477         // Create the new top level add instruction...
 478         return BinaryOperator::create(Instruction::Add, Op0, Op1);
 479       }
 480
 481       // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
 482       //
 483       if (Op1I->getOpcode() == Instruction::And &&
 484           (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
 485         Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
 486
 487         Instruction *NewNot = BinaryOperator::createNot(OtherOp, "B.not", &I);
 488         return BinaryOperator::create(Instruction::And, Op0, NewNot);
 489       }
 490
 491       // X - X*C --> X * (1-C)
 492       if (dyn_castFoldableMul(Op1I) == Op0) {
 493         Constant *CP1 =
 494           ConstantExpr::get(Instruction::Sub,
 495                             ConstantInt::get(I.getType(), 1),
 496                          cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
 497         assert(CP1 && "Couldn't constant fold 1-C?");
 498         return BinaryOperator::create(Instruction::Mul, Op0, CP1);
 499       }
 500     }
 501
 502   // X*C - X --> X * (C-1)
 503   if (dyn_castFoldableMul(Op0) == Op1) {
 504     Constant *CP1 =
 505       ConstantExpr::get(Instruction::Sub,
 506                         cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
 507                         ConstantInt::get(I.getType(), 1));
 508     assert(CP1 && "Couldn't constant fold C - 1?");
 509     return BinaryOperator::create(Instruction::Mul, Op1, CP1);
 510   }
 511
 512   return 0;
 513 }
 514
 515 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 516   bool Changed = SimplifyCommutative(I);
 517   Value *Op0 = I.getOperand(0);
 518
 519   // Simplify mul instructions with a constant RHS...
 520   if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
 521     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 522
 523       // ((X << C1)*C2) == (X * (C2 << C1))
 524       if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
 525         if (SI->getOpcode() == Instruction::Shl)
 526           if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
 527             return BinaryOperator::create(Instruction::Mul, SI->getOperand(0),
 528                                           *CI << *ShOp);
 529
 530       if (CI->isNullValue())
 531         return ReplaceInstUsesWith(I, Op1);  // X * 0  == 0
 532       if (CI->equalsInt(1))                  // X * 1  == X
 533         return ReplaceInstUsesWith(I, Op0);
 534       if (CI->isAllOnesValue())              // X * -1 == 0 - X
 535         return BinaryOperator::createNeg(Op0, I.getName());
 536
 537       int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
 538       if (uint64_t C = Log2(Val))            // Replace X*(2^C) with X << C
 539         return new ShiftInst(Instruction::Shl, Op0,
 540                              ConstantUInt::get(Type::UByteTy, C));
 541     } else {
 542       ConstantFP *Op1F = cast<ConstantFP>(Op1);
 543       if (Op1F->isNullValue())
 544         return ReplaceInstUsesWith(I, Op1);
 545
 546       // "In IEEE floating point, x*1 is not equivalent to x for nans.  However,
 547       // ANSI says we can drop signals, so we can do this anyway." (from GCC)
 548       if (Op1F->getValue() == 1.0)
 549         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'mul double %X, 1.0'
 550     }
 551   }
 552
 553   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
 554     if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
 555       return BinaryOperator::create(Instruction::Mul, Op0v, Op1v);
 556
 557   return Changed ? &I : 0;
 558 }
 559
 560 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
 561   // div X, 1 == X
 562   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
 563     if (RHS->equalsInt(1))
 564       return ReplaceInstUsesWith(I, I.getOperand(0));
 565
 566     // Check to see if this is an unsigned division with an exact power of 2,
 567     // if so, convert to a right shift.
 568     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
 569       if (uint64_t Val = C->getValue())    // Don't break X / 0
 570         if (uint64_t C = Log2(Val))
 571           return new ShiftInst(Instruction::Shr, I.getOperand(0),
 572                                ConstantUInt::get(Type::UByteTy, C));
 573   }
 574
 575   // 0 / X == 0, we don't need to preserve faults!
 576   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
 577     if (LHS->equalsInt(0))
 578       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 579
 580   return 0;
 581 }
 582
 583
 584 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
 585   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
 586     if (RHS->equalsInt(1))  // X % 1 == 0
 587       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 588
 589     // Check to see if this is an unsigned remainder with an exact power of 2,
 590     // if so, convert to a bitwise and.
 591     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
 592       if (uint64_t Val = C->getValue())    // Don't break X % 0 (divide by zero)
 593         if (Log2(Val))
 594           return BinaryOperator::create(Instruction::And, I.getOperand(0),
 595                                         ConstantUInt::get(I.getType(), Val-1));
 596   }
 597
 598   // 0 % X == 0, we don't need to preserve faults!
 599   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
 600     if (LHS->equalsInt(0))
 601       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 602
 603   return 0;
 604 }
 605
 606 // isMaxValueMinusOne - return true if this is Max-1
 607 static bool isMaxValueMinusOne(const ConstantInt *C) {
 608   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
 609     // Calculate -1 casted to the right type...
 610     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 611     uint64_t Val = ~0ULL;                // All ones
 612     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 613     return CU->getValue() == Val-1;
 614   }
 615
 616   const ConstantSInt *CS = cast<ConstantSInt>(C);
 617
 618   // Calculate 0111111111..11111
 619   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 620   int64_t Val = INT64_MAX;             // All ones
 621   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 622   return CS->getValue() == Val-1;
 623 }
 624
 625 // isMinValuePlusOne - return true if this is Min+1
 626 static bool isMinValuePlusOne(const ConstantInt *C) {
 627   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
 628     return CU->getValue() == 1;
 629
 630   const ConstantSInt *CS = cast<ConstantSInt>(C);
 631
 632   // Calculate 1111111111000000000000
 633   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 634   int64_t Val = -1;                    // All ones
 635   Val <<= TypeBits-1;                  // Shift over to the right spot
 636   return CS->getValue() == Val+1;
 637 }
 638
 639 /// getSetCondCode - Encode a setcc opcode into a three bit mask.  These bits
 640 /// are carefully arranged to allow folding of expressions such as:
 641 ///
 642 ///      (A < B) | (A > B) --> (A != B)
 643 ///
 644 /// Bit value '4' represents that the comparison is true if A > B, bit value '2'
 645 /// represents that the comparison is true if A == B, and bit value '1' is true
 646 /// if A < B.
 647 ///
 648 static unsigned getSetCondCode(const SetCondInst *SCI) {
 649   switch (SCI->getOpcode()) {
 650     // False -> 0
 651   case Instruction::SetGT: return 1;
 652   case Instruction::SetEQ: return 2;
 653   case Instruction::SetGE: return 3;
 654   case Instruction::SetLT: return 4;
 655   case Instruction::SetNE: return 5;
 656   case Instruction::SetLE: return 6;
 657     // True -> 7
 658   default:
 659     assert(0 && "Invalid SetCC opcode!");
 660     return 0;
 661   }
 662 }
 663
 664 /// getSetCCValue - This is the complement of getSetCondCode, which turns an
 665 /// opcode and two operands into either a constant true or false, or a brand new
 666 /// SetCC instruction.
 667 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
 668   switch (Opcode) {
 669   case 0: return ConstantBool::False;
 670   case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
 671   case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
 672   case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
 673   case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
 674   case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
 675   case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
 676   case 7: return ConstantBool::True;
 677   default: assert(0 && "Illegal SetCCCode!"); return 0;
 678   }
 679 }
 680
 681 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
 682 struct FoldSetCCLogical {
 683   InstCombiner &IC;
 684   Value *LHS, *RHS;
 685   FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
 686     : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
 687   bool shouldApply(Value *V) const {
 688     if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 689       return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
 690               SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
 691     return false;
 692   }
 693   Instruction *apply(BinaryOperator &Log) const {
 694     SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
 695     if (SCI->getOperand(0) != LHS) {
 696       assert(SCI->getOperand(1) == LHS);
 697       SCI->swapOperands();  // Swap the LHS and RHS of the SetCC
 698     }
 699
 700     unsigned LHSCode = getSetCondCode(SCI);
 701     unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
 702     unsigned Code;
 703     switch (Log.getOpcode()) {
 704     case Instruction::And: Code = LHSCode & RHSCode; break;
 705     case Instruction::Or:  Code = LHSCode | RHSCode; break;
 706     case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
 707     default: assert(0 && "Illegal logical opcode!");
 708     }
 709
 710     Value *RV = getSetCCValue(Code, LHS, RHS);
 711     if (Instruction *I = dyn_cast<Instruction>(RV))
 712       return I;
 713     // Otherwise, it's a constant boolean value...
 714     return IC.ReplaceInstUsesWith(Log, RV);
 715   }
 716 };
 717
 718
 719
 720 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
 721   bool Changed = SimplifyCommutative(I);
 722   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 723
 724   // and X, X = X   and X, 0 == 0
 725   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 726     return ReplaceInstUsesWith(I, Op1);
 727
 728   // and X, -1 == X
 729   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
 730     if (RHS->isAllOnesValue())
 731       return ReplaceInstUsesWith(I, Op0);
 732
 733     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
 734       Value *X = Op0I->getOperand(0);
 735       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
 736         if (Op0I->getOpcode() == Instruction::Xor) {
 737           if ((*RHS & *Op0CI)->isNullValue()) {
 738             // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
 739             return BinaryOperator::create(Instruction::And, X, RHS);
 740           } else if (isOnlyUse(Op0)) {
 741             // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
 742             std::string Op0Name = Op0I->getName(); Op0I->setName("");
 743             Instruction *And = BinaryOperator::create(Instruction::And,
 744                                                       X, RHS, Op0Name);
 745             InsertNewInstBefore(And, I);
 746             return BinaryOperator::create(Instruction::Xor, And, *RHS & *Op0CI);
 747           }
 748         } else if (Op0I->getOpcode() == Instruction::Or) {
 749           // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
 750           if ((*RHS & *Op0CI)->isNullValue())
 751             return BinaryOperator::create(Instruction::And, X, RHS);
 752
 753           Constant *Together = *RHS & *Op0CI;
 754           if (Together == RHS) // (X | C) & C --> C
 755             return ReplaceInstUsesWith(I, RHS);
 756
 757           if (isOnlyUse(Op0)) {
 758             if (Together != Op0CI) {
 759               // (X | C1) & C2 --> (X | (C1&C2)) & C2
 760               std::string Op0Name = Op0I->getName(); Op0I->setName("");
 761               Instruction *Or = BinaryOperator::create(Instruction::Or, X,
 762                                                        Together, Op0Name);
 763               InsertNewInstBefore(Or, I);
 764               return BinaryOperator::create(Instruction::And, Or, RHS);
 765             }
 766           }
 767         }
 768     }
 769   }
 770
 771   Value *Op0NotVal = dyn_castNotVal(Op0);
 772   Value *Op1NotVal = dyn_castNotVal(Op1);
 773
 774   // (~A & ~B) == (~(A | B)) - Demorgan's Law
 775   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
 776     Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal,
 777                                              Op1NotVal,I.getName()+".demorgan");
 778     InsertNewInstBefore(Or, I);
 779     return BinaryOperator::createNot(Or);
 780   }
 781
 782   if (Op0NotVal == Op1 || Op1NotVal == Op0)  // A & ~A  == ~A & A == 0
 783     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 784
 785   // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
 786   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
 787     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
 788       return R;
 789
 790   return Changed ? &I : 0;
 791 }
 792
 793
 794
 795 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
 796   bool Changed = SimplifyCommutative(I);
 797   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 798
 799   // or X, X = X   or X, 0 == X
 800   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 801     return ReplaceInstUsesWith(I, Op0);
 802
 803   // or X, -1 == -1
 804   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
 805     if (RHS->isAllOnesValue())
 806       return ReplaceInstUsesWith(I, Op1);
 807
 808     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
 809       // (X & C1) | C2 --> (X | C2) & (C1|C2)
 810       if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0))
 811         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
 812           std::string Op0Name = Op0I->getName(); Op0I->setName("");
 813           Instruction *Or = BinaryOperator::create(Instruction::Or,
 814                                                    Op0I->getOperand(0), RHS,
 815                                                    Op0Name);
 816           InsertNewInstBefore(Or, I);
 817           return BinaryOperator::create(Instruction::And, Or, *RHS | *Op0CI);
 818         }
 819
 820       // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
 821       if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0))
 822         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
 823           std::string Op0Name = Op0I->getName(); Op0I->setName("");
 824           Instruction *Or = BinaryOperator::create(Instruction::Or,
 825                                                    Op0I->getOperand(0), RHS,
 826                                                    Op0Name);
 827           InsertNewInstBefore(Or, I);
 828           return BinaryOperator::create(Instruction::Xor, Or, *Op0CI & *~*RHS);
 829         }
 830     }
 831   }
 832
 833   // (A & C1)|(A & C2) == A & (C1|C2)
 834   if (Instruction *LHS = dyn_cast<BinaryOperator>(Op0))
 835     if (Instruction *RHS = dyn_cast<BinaryOperator>(Op1))
 836       if (LHS->getOperand(0) == RHS->getOperand(0))
 837         if (Constant *C0 = dyn_castMaskingAnd(LHS))
 838           if (Constant *C1 = dyn_castMaskingAnd(RHS))
 839             return BinaryOperator::create(Instruction::And, LHS->getOperand(0),
 840                                           *C0 | *C1);
 841
 842   Value *Op0NotVal = dyn_castNotVal(Op0);
 843   Value *Op1NotVal = dyn_castNotVal(Op1);
 844
 845   if (Op1 == Op0NotVal)   // ~A | A == -1
 846     return ReplaceInstUsesWith(I,
 847                                ConstantIntegral::getAllOnesValue(I.getType()));
 848
 849   if (Op0 == Op1NotVal)   // A | ~A == -1
 850     return ReplaceInstUsesWith(I,
 851                                ConstantIntegral::getAllOnesValue(I.getType()));
 852
 853   // (~A | ~B) == (~(A & B)) - Demorgan's Law
 854   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
 855     Instruction *And = BinaryOperator::create(Instruction::And, Op0NotVal,
 856                                               Op1NotVal,I.getName()+".demorgan",
 857                                               &I);
 858     WorkList.push_back(And);
 859     return BinaryOperator::createNot(And);
 860   }
 861
 862   // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
 863   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
 864     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
 865       return R;
 866
 867   return Changed ? &I : 0;
 868 }
 869
 870
 871
 872 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
 873   bool Changed = SimplifyCommutative(I);
 874   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 875
 876   // xor X, X = 0
 877   if (Op0 == Op1)
 878     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 879
 880   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
 881     // xor X, 0 == X
 882     if (RHS->isNullValue())
 883       return ReplaceInstUsesWith(I, Op0);
 884
 885     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
 886       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
 887       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
 888         if (RHS == ConstantBool::True && SCI->use_size() == 1)
 889           return new SetCondInst(SCI->getInverseCondition(),
 890                                  SCI->getOperand(0), SCI->getOperand(1));
 891
 892       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
 893         if (Op0I->getOpcode() == Instruction::And) {
 894           // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
 895           if ((*RHS & *Op0CI)->isNullValue())
 896             return BinaryOperator::create(Instruction::Or, Op0, RHS);
 897         } else if (Op0I->getOpcode() == Instruction::Or) {
 898           // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
 899           if ((*RHS & *Op0CI) == RHS)
 900             return BinaryOperator::create(Instruction::And, Op0, ~*RHS);
 901         }
 902     }
 903   }
 904
 905   if (Value *X = dyn_castNotVal(Op0))   // ~A ^ A == -1
 906     if (X == Op1)
 907       return ReplaceInstUsesWith(I,
 908                                 ConstantIntegral::getAllOnesValue(I.getType()));
 909
 910   if (Value *X = dyn_castNotVal(Op1))   // A ^ ~A == -1
 911     if (X == Op0)
 912       return ReplaceInstUsesWith(I,
 913                                 ConstantIntegral::getAllOnesValue(I.getType()));
 914
 915   if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
 916     if (Op1I->getOpcode() == Instruction::Or)
 917       if (Op1I->getOperand(0) == Op0) {              // B^(B|A) == (A|B)^B
 918         cast<BinaryOperator>(Op1I)->swapOperands();
 919         I.swapOperands();
 920         std::swap(Op0, Op1);
 921       } else if (Op1I->getOperand(1) == Op0) {       // B^(A|B) == (A|B)^B
 922         I.swapOperands();
 923         std::swap(Op0, Op1);
 924       }
 925
 926   if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
 927     if (Op0I->getOpcode() == Instruction::Or && Op0I->use_size() == 1) {
 928       if (Op0I->getOperand(0) == Op1)                // (B|A)^B == (A|B)^B
 929         cast<BinaryOperator>(Op0I)->swapOperands();
 930       if (Op0I->getOperand(1) == Op1) {              // (A|B)^B == A & ~B
 931         Value *NotB = BinaryOperator::createNot(Op1, Op1->getName()+".not", &I);
 932         WorkList.push_back(cast<Instruction>(NotB));
 933         return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
 934                                       NotB);
 935       }
 936     }
 937
 938   // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0
 939   if (Constant *C1 = dyn_castMaskingAnd(Op0))
 940     if (Constant *C2 = dyn_castMaskingAnd(Op1))
 941       if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
 942         return BinaryOperator::create(Instruction::Or, Op0, Op1);
 943
 944   // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
 945   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
 946     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
 947       return R;
 948
 949   return Changed ? &I : 0;
 950 }
 951
 952 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
 953 static Constant *AddOne(ConstantInt *C) {
 954   Constant *Result = ConstantExpr::get(Instruction::Add, C,
 955                                        ConstantInt::get(C->getType(), 1));
 956   assert(Result && "Constant folding integer addition failed!");
 957   return Result;
 958 }
 959 static Constant *SubOne(ConstantInt *C) {
 960   Constant *Result = ConstantExpr::get(Instruction::Sub, C,
 961                                        ConstantInt::get(C->getType(), 1));
 962   assert(Result && "Constant folding integer addition failed!");
 963   return Result;
 964 }
 965
 966 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
 967 // true when both operands are equal...
 968 //
 969 static bool isTrueWhenEqual(Instruction &I) {
 970   return I.getOpcode() == Instruction::SetEQ ||
 971          I.getOpcode() == Instruction::SetGE ||
 972          I.getOpcode() == Instruction::SetLE;
 973 }
 974
 975 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
 976   bool Changed = SimplifyCommutative(I);
 977   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 978   const Type *Ty = Op0->getType();
 979
 980   // setcc X, X
 981   if (Op0 == Op1)
 982     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
 983
 984   // setcc <global/alloca*>, 0 - Global/Stack value addresses are never null!
 985   if (isa<ConstantPointerNull>(Op1) &&
 986       (isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0)))
 987     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
 988
 989
 990   // setcc's with boolean values can always be turned into bitwise operations
 991   if (Ty == Type::BoolTy) {
 992     // If this is <, >, or !=, we can change this into a simple xor instruction
 993     if (!isTrueWhenEqual(I))
 994       return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
 995
 996     // Otherwise we need to make a temporary intermediate instruction and insert
 997     // it into the instruction stream.  This is what we are after:
 998     //
 999     //  seteq bool %A, %B -> ~(A^B)
1000     //  setle bool %A, %B -> ~A | B
1001     //  setge bool %A, %B -> A | ~B
1002     //
1003     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
1004       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
1005                                                 I.getName()+"tmp");
1006       InsertNewInstBefore(Xor, I);
1007       return BinaryOperator::createNot(Xor, I.getName());
1008     }
1009
1010     // Handle the setXe cases...
1011     assert(I.getOpcode() == Instruction::SetGE ||
1012            I.getOpcode() == Instruction::SetLE);
1013
1014     if (I.getOpcode() == Instruction::SetGE)
1015       std::swap(Op0, Op1);                   // Change setge -> setle
1016
1017     // Now we just have the SetLE case.
1018     Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
1019     InsertNewInstBefore(Not, I);
1020     return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
1021   }
1022
1023   // Check to see if we are doing one of many comparisons against constant
1024   // integers at the end of their ranges...
1025   //
1026   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1027     // Simplify seteq and setne instructions...
1028     if (I.getOpcode() == Instruction::SetEQ ||
1029         I.getOpcode() == Instruction::SetNE) {
1030       bool isSetNE = I.getOpcode() == Instruction::SetNE;
1031
1032       // If the first operand is (and|or|xor) with a constant, and the second
1033       // operand is a constant, simplify a bit.
1034       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
1035         switch (BO->getOpcode()) {
1036         case Instruction::Add:
1037           if (CI->isNullValue()) {
1038             // Replace ((add A, B) != 0) with (A != -B) if A or B is
1039             // efficiently invertible, or if the add has just this one use.
1040             Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
1041             if (Value *NegVal = dyn_castNegVal(BOp1))
1042               return new SetCondInst(I.getOpcode(), BOp0, NegVal);
1043             else if (Value *NegVal = dyn_castNegVal(BOp0))
1044               return new SetCondInst(I.getOpcode(), NegVal, BOp1);
1045             else if (BO->use_size() == 1) {
1046               Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
1047               BO->setName("");
1048               InsertNewInstBefore(Neg, I);
1049               return new SetCondInst(I.getOpcode(), BOp0, Neg);
1050             }
1051           }
1052           break;
1053         case Instruction::Xor:
1054           // For the xor case, we can xor two constants together, eliminating
1055           // the explicit xor.
1056           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1057             return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
1058                                           *CI ^ *BOC);
1059
1060           // FALLTHROUGH
1061         case Instruction::Sub:
1062           // Replace (([sub|xor] A, B) != 0) with (A != B)
1063           if (CI->isNullValue())
1064             return new SetCondInst(I.getOpcode(), BO->getOperand(0),
1065                                    BO->getOperand(1));
1066           break;
1067
1068         case Instruction::Or:
1069           // If bits are being or'd in that are not present in the constant we
1070           // are comparing against, then the comparison could never succeed!
1071           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1072             if (!(*BOC & *~*CI)->isNullValue())
1073               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1074           break;
1075
1076         case Instruction::And:
1077           if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1078             // If bits are being compared against that are and'd out, then the
1079             // comparison can never succeed!
1080             if (!(*CI & *~*BOC)->isNullValue())
1081               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1082
1083             // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
1084             // to be a signed value as appropriate.
1085             if (isSignBit(BOC)) {
1086               Value *X = BO->getOperand(0);
1087               // If 'X' is not signed, insert a cast now...
1088               if (!BOC->getType()->isSigned()) {
1089                 const Type *DestTy;
1090                 switch (BOC->getType()->getPrimitiveID()) {
1091                 case Type::UByteTyID:  DestTy = Type::SByteTy; break;
1092                 case Type::UShortTyID: DestTy = Type::ShortTy; break;
1093                 case Type::UIntTyID:   DestTy = Type::IntTy;   break;
1094                 case Type::ULongTyID:  DestTy = Type::LongTy;  break;
1095                 default: assert(0 && "Invalid unsigned integer type!"); abort();
1096                 }
1097                 CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed");
1098                 InsertNewInstBefore(NewCI, I);
1099                 X = NewCI;
1100               }
1101               return new SetCondInst(isSetNE ? Instruction::SetLT :
1102                                          Instruction::SetGE, X,
1103                                      Constant::getNullValue(X->getType()));
1104             }
1105           }
1106         default: break;
1107         }
1108       }
1109     }
1110
1111     // Check to see if we are comparing against the minimum or maximum value...
1112     if (CI->isMinValue()) {
1113       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
1114         return ReplaceInstUsesWith(I, ConstantBool::False);
1115       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
1116         return ReplaceInstUsesWith(I, ConstantBool::True);
1117       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
1118         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
1119       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
1120         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
1121
1122     } else if (CI->isMaxValue()) {
1123       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
1124         return ReplaceInstUsesWith(I, ConstantBool::False);
1125       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
1126         return ReplaceInstUsesWith(I, ConstantBool::True);
1127       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
1128         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
1129       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
1130         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
1131
1132       // Comparing against a value really close to min or max?
1133     } else if (isMinValuePlusOne(CI)) {
1134       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
1135         return BinaryOperator::create(Instruction::SetEQ, Op0,
1136                                       SubOne(CI), I.getName());
1137       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
1138         return BinaryOperator::create(Instruction::SetNE, Op0,
1139                                       SubOne(CI), I.getName());
1140
1141     } else if (isMaxValueMinusOne(CI)) {
1142       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
1143         return BinaryOperator::create(Instruction::SetEQ, Op0,
1144                                       AddOne(CI), I.getName());
1145       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
1146         return BinaryOperator::create(Instruction::SetNE, Op0,
1147                                       AddOne(CI), I.getName());
1148     }
1149   }
1150
1151   return Changed ? &I : 0;
1152 }
1153
1154
1155
1156 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
1157   assert(I.getOperand(1)->getType() == Type::UByteTy);
1158   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1159   bool isLeftShift = I.getOpcode() == Instruction::Shl;
1160
1161   // shl X, 0 == X and shr X, 0 == X
1162   // shl 0, X == 0 and shr 0, X == 0
1163   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
1164       Op0 == Constant::getNullValue(Op0->getType()))
1165     return ReplaceInstUsesWith(I, Op0);
1166
1167   // shr int -1, X = -1   (for any arithmetic shift rights of ~0)
1168   if (!isLeftShift)
1169     if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
1170       if (CSI->isAllOnesValue())
1171         return ReplaceInstUsesWith(I, CSI);
1172
1173   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
1174     // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
1175     // of a signed value.
1176     //
1177     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
1178     if (CUI->getValue() >= TypeBits &&
1179         (!Op0->getType()->isSigned() || isLeftShift))
1180       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
1181
1182     // ((X*C1) << C2) == (X * (C1 << C2))
1183     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
1184       if (BO->getOpcode() == Instruction::Mul && isLeftShift)
1185         if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
1186           return BinaryOperator::create(Instruction::Mul, BO->getOperand(0),
1187                                         *BOOp << *CUI);
1188
1189
1190     // If the operand is an bitwise operator with a constant RHS, and the
1191     // shift is the only use, we can pull it out of the shift.
1192     if (Op0->use_size() == 1)
1193       if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
1194         if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
1195           bool isValid = true;     // Valid only for And, Or, Xor
1196           bool highBitSet = false; // Transform if high bit of constant set?
1197
1198           switch (Op0BO->getOpcode()) {
1199           default: isValid = false; break;   // Do not perform transform!
1200           case Instruction::Or:
1201           case Instruction::Xor:
1202             highBitSet = false;
1203             break;
1204           case Instruction::And:
1205             highBitSet = true;
1206             break;
1207           }
1208
1209           // If this is a signed shift right, and the high bit is modified
1210           // by the logical operation, do not perform the transformation.
1211           // The highBitSet boolean indicates the value of the high bit of
1212           // the constant which would cause it to be modified for this
1213           // operation.
1214           //
1215           if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
1216             uint64_t Val = Op0C->getRawValue();
1217             isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
1218           }
1219
1220           if (isValid) {
1221             Constant *NewRHS =
1222               ConstantFoldShiftInstruction(I.getOpcode(), Op0C, CUI);
1223
1224             Instruction *NewShift =
1225               new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
1226                             Op0BO->getName());
1227             Op0BO->setName("");
1228             InsertNewInstBefore(NewShift, I);
1229
1230             return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
1231                                           NewRHS);
1232           }
1233         }
1234
1235     // If this is a shift of a shift, see if we can fold the two together...
1236     if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
1237       if (ConstantUInt *ShiftAmt1C =
1238                                  dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
1239         unsigned ShiftAmt1 = ShiftAmt1C->getValue();
1240         unsigned ShiftAmt2 = CUI->getValue();
1241
1242         // Check for (A << c1) << c2   and   (A >> c1) >> c2
1243         if (I.getOpcode() == Op0SI->getOpcode()) {
1244           unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift...
1245           return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
1246                                ConstantUInt::get(Type::UByteTy, Amt));
1247         }
1248
1249         // Check for (A << c1) >> c2 or visaversa.  If we are dealing with
1250         // signed types, we can only support the (A >> c1) << c2 configuration,
1251         // because it can not turn an arbitrary bit of A into a sign bit.
1252         if (I.getType()->isUnsigned() || isLeftShift) {
1253           // Calculate bitmask for what gets shifted off the edge...
1254           Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
1255           if (isLeftShift)
1256             C = ConstantExpr::getShift(Instruction::Shl, C, ShiftAmt1C);
1257           else
1258             C = ConstantExpr::getShift(Instruction::Shr, C, ShiftAmt1C);
1259
1260           Instruction *Mask =
1261             BinaryOperator::create(Instruction::And, Op0SI->getOperand(0),
1262                                    C, Op0SI->getOperand(0)->getName()+".mask");
1263           InsertNewInstBefore(Mask, I);
1264
1265           // Figure out what flavor of shift we should use...
1266           if (ShiftAmt1 == ShiftAmt2)
1267             return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
1268           else if (ShiftAmt1 < ShiftAmt2) {
1269             return new ShiftInst(I.getOpcode(), Mask,
1270                          ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
1271           } else {
1272             return new ShiftInst(Op0SI->getOpcode(), Mask,
1273                          ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
1274           }
1275         }
1276       }
1277   }
1278
1279   return 0;
1280 }
1281
1282
1283 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
1284 // instruction.
1285 //
1286 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
1287                                           const Type *DstTy) {
1288
1289   // It is legal to eliminate the instruction if casting A->B->A if the sizes
1290   // are identical and the bits don't get reinterpreted (for example
1291   // int->float->int would not be allowed)
1292   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
1293     return true;
1294
1295   // Allow free casting and conversion of sizes as long as the sign doesn't
1296   // change...
1297   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
1298     unsigned SrcSize = SrcTy->getPrimitiveSize();
1299     unsigned MidSize = MidTy->getPrimitiveSize();
1300     unsigned DstSize = DstTy->getPrimitiveSize();
1301
1302     // Cases where we are monotonically decreasing the size of the type are
1303     // always ok, regardless of what sign changes are going on.
1304     //
1305     if (SrcSize >= MidSize && MidSize >= DstSize)
1306       return true;
1307
1308     // Cases where the source and destination type are the same, but the middle
1309     // type is bigger are noops.
1310     //
1311     if (SrcSize == DstSize && MidSize > SrcSize)
1312       return true;
1313
1314     // If we are monotonically growing, things are more complex.
1315     //
1316     if (SrcSize <= MidSize && MidSize <= DstSize) {
1317       // We have eight combinations of signedness to worry about. Here's the
1318       // table:
1319       static const int SignTable[8] = {
1320         // CODE, SrcSigned, MidSigned, DstSigned, Comment
1321         1,     //   U          U          U       Always ok
1322         1,     //   U          U          S       Always ok
1323         3,     //   U          S          U       Ok iff SrcSize != MidSize
1324         3,     //   U          S          S       Ok iff SrcSize != MidSize
1325         0,     //   S          U          U       Never ok
1326         2,     //   S          U          S       Ok iff MidSize == DstSize
1327         1,     //   S          S          U       Always ok
1328         1,     //   S          S          S       Always ok
1329       };
1330
1331       // Choose an action based on the current entry of the signtable that this
1332       // cast of cast refers to...
1333       unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
1334       switch (SignTable[Row]) {
1335       case 0: return false;              // Never ok
1336       case 1: return true;               // Always ok
1337       case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
1338       case 3:                            // Ok iff SrcSize != MidSize
1339         return SrcSize != MidSize || SrcTy == Type::BoolTy;
1340       default: assert(0 && "Bad entry in sign table!");
1341       }
1342     }
1343   }
1344
1345   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
1346   // like:  short -> ushort -> uint, because this can create wrong results if
1347   // the input short is negative!
1348   //
1349   return false;
1350 }
1351
1352 static bool ValueRequiresCast(const Value *V, const Type *Ty) {
1353   if (V->getType() == Ty || isa<Constant>(V)) return false;
1354   if (const CastInst *CI = dyn_cast<CastInst>(V))
1355     if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty))
1356       return false;
1357   return true;
1358 }
1359
1360 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
1361 /// InsertBefore instruction.  This is specialized a bit to avoid inserting
1362 /// casts that are known to not do anything...
1363 ///
1364 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
1365                                              Instruction *InsertBefore) {
1366   if (V->getType() == DestTy) return V;
1367   if (Constant *C = dyn_cast<Constant>(V))
1368     return ConstantExpr::getCast(C, DestTy);
1369
1370   CastInst *CI = new CastInst(V, DestTy, V->getName());
1371   InsertNewInstBefore(CI, *InsertBefore);
1372   return CI;
1373 }
1374
1375 // CastInst simplification
1376 //
1377 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
1378   Value *Src = CI.getOperand(0);
1379
1380   // If the user is casting a value to the same type, eliminate this cast
1381   // instruction...
1382   if (CI.getType() == Src->getType())
1383     return ReplaceInstUsesWith(CI, Src);
1384
1385   // If casting the result of another cast instruction, try to eliminate this
1386   // one!
1387   //
1388   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
1389     if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
1390                                CSrc->getType(), CI.getType())) {
1391       // This instruction now refers directly to the cast's src operand.  This
1392       // has a good chance of making CSrc dead.
1393       CI.setOperand(0, CSrc->getOperand(0));
1394       return &CI;
1395     }
1396
1397     // If this is an A->B->A cast, and we are dealing with integral types, try
1398     // to convert this into a logical 'and' instruction.
1399     //
1400     if (CSrc->getOperand(0)->getType() == CI.getType() &&
1401         CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
1402         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
1403         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
1404       assert(CSrc->getType() != Type::ULongTy &&
1405              "Cannot have type bigger than ulong!");
1406       uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
1407       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
1408       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
1409                                     AndOp);
1410     }
1411   }
1412
1413   // If casting the result of a getelementptr instruction with no offset, turn
1414   // this into a cast of the original pointer!
1415   //
1416   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
1417     bool AllZeroOperands = true;
1418     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
1419       if (!isa<Constant>(GEP->getOperand(i)) ||
1420           !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
1421         AllZeroOperands = false;
1422         break;
1423       }
1424     if (AllZeroOperands) {
1425       CI.setOperand(0, GEP->getOperand(0));
1426       return &CI;
1427     }
1428   }
1429
1430   // If the source value is an instruction with only this use, we can attempt to
1431   // propagate the cast into the instruction.  Also, only handle integral types
1432   // for now.
1433   if (Instruction *SrcI = dyn_cast<Instruction>(Src))
1434     if (SrcI->use_size() == 1 && Src->getType()->isIntegral() &&
1435         CI.getType()->isInteger()) {  // Don't mess with casts to bool here
1436       const Type *DestTy = CI.getType();
1437       unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
1438       unsigned DestBitSize = getTypeSizeInBits(DestTy);
1439
1440       Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
1441       Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
1442
1443       switch (SrcI->getOpcode()) {
1444       case Instruction::Add:
1445       case Instruction::Mul:
1446       case Instruction::And:
1447       case Instruction::Or:
1448       case Instruction::Xor:
1449         // If we are discarding information, or just changing the sign, rewrite.
1450         if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
1451           // Don't insert two casts if they cannot be eliminated.  We allow two
1452           // casts to be inserted if the sizes are the same.  This could only be
1453           // converting signedness, which is a noop.
1454           if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) ||
1455               !ValueRequiresCast(Op0, DestTy)) {
1456             Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1457             Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
1458             return BinaryOperator::create(cast<BinaryOperator>(SrcI)
1459                              ->getOpcode(), Op0c, Op1c);
1460           }
1461         }
1462         break;
1463       case Instruction::Shl:
1464         // Allow changing the sign of the source operand.  Do not allow changing
1465         // the size of the shift, UNLESS the shift amount is a constant.  We
1466         // mush not change variable sized shifts to a smaller size, because it
1467         // is undefined to shift more bits out than exist in the value.
1468         if (DestBitSize == SrcBitSize ||
1469             (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
1470           Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
1471           return new ShiftInst(Instruction::Shl, Op0c, Op1);
1472         }
1473         break;
1474       }
1475     }
1476
1477   return 0;
1478 }
1479
1480 // CallInst simplification
1481 //
1482 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
1483   if (transformConstExprCastCall(&CI)) return 0;
1484   return 0;
1485 }
1486
1487 // InvokeInst simplification
1488 //
1489 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
1490   if (transformConstExprCastCall(&II)) return 0;
1491   return 0;
1492 }
1493
1494 // getPromotedType - Return the specified type promoted as it would be to pass
1495 // though a va_arg area...
1496 static const Type *getPromotedType(const Type *Ty) {
1497   switch (Ty->getPrimitiveID()) {
1498   case Type::SByteTyID:
1499   case Type::ShortTyID:  return Type::IntTy;
1500   case Type::UByteTyID:
1501   case Type::UShortTyID: return Type::UIntTy;
1502   case Type::FloatTyID:  return Type::DoubleTy;
1503   default:               return Ty;
1504   }
1505 }
1506
1507 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
1508 // attempt to move the cast to the arguments of the call/invoke.
1509 //
1510 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
1511   if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
1512   ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
1513   if (CE->getOpcode() != Instruction::Cast ||
1514       !isa<ConstantPointerRef>(CE->getOperand(0)))
1515     return false;
1516   ConstantPointerRef *CPR = cast<ConstantPointerRef>(CE->getOperand(0));
1517   if (!isa<Function>(CPR->getValue())) return false;
1518   Function *Callee = cast<Function>(CPR->getValue());
1519   Instruction *Caller = CS.getInstruction();
1520
1521   // Okay, this is a cast from a function to a different type.  Unless doing so
1522   // would cause a type conversion of one of our arguments, change this call to
1523   // be a direct call with arguments casted to the appropriate types.
1524   //
1525   const FunctionType *FT = Callee->getFunctionType();
1526   const Type *OldRetTy = Caller->getType();
1527
1528   if (Callee->isExternal() &&
1529       !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()))
1530     return false;   // Cannot transform this return value...
1531
1532   unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
1533   unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
1534
1535   CallSite::arg_iterator AI = CS.arg_begin();
1536   for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
1537     const Type *ParamTy = FT->getParamType(i);
1538     bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
1539     if (Callee->isExternal() && !isConvertible) return false;
1540   }
1541
1542   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
1543       Callee->isExternal())
1544     return false;   // Do not delete arguments unless we have a function body...
1545
1546   // Okay, we decided that this is a safe thing to do: go ahead and start
1547   // inserting cast instructions as necessary...
1548   std::vector<Value*> Args;
1549   Args.reserve(NumActualArgs);
1550
1551   AI = CS.arg_begin();
1552   for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
1553     const Type *ParamTy = FT->getParamType(i);
1554     if ((*AI)->getType() == ParamTy) {
1555       Args.push_back(*AI);
1556     } else {
1557       Instruction *Cast = new CastInst(*AI, ParamTy, "tmp");
1558       InsertNewInstBefore(Cast, *Caller);
1559       Args.push_back(Cast);
1560     }
1561   }
1562
1563   // If the function takes more arguments than the call was taking, add them
1564   // now...
1565   for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
1566     Args.push_back(Constant::getNullValue(FT->getParamType(i)));
1567
1568   // If we are removing arguments to the function, emit an obnoxious warning...
1569   if (FT->getNumParams() < NumActualArgs)
1570     if (!FT->isVarArg()) {
1571       std::cerr << "WARNING: While resolving call to function '"
1572                 << Callee->getName() << "' arguments were dropped!\n";
1573     } else {
1574       // Add all of the arguments in their promoted form to the arg list...
1575       for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
1576         const Type *PTy = getPromotedType((*AI)->getType());
1577         if (PTy != (*AI)->getType()) {
1578           // Must promote to pass through va_arg area!
1579           Instruction *Cast = new CastInst(*AI, PTy, "tmp");
1580           InsertNewInstBefore(Cast, *Caller);
1581           Args.push_back(Cast);
1582         } else {
1583           Args.push_back(*AI);
1584         }
1585       }
1586     }
1587
1588   if (FT->getReturnType() == Type::VoidTy)
1589     Caller->setName("");   // Void type should not have a name...
1590
1591   Instruction *NC;
1592   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
1593     NC = new InvokeInst(Callee, II->getNormalDest(), II->getExceptionalDest(),
1594                         Args, Caller->getName(), Caller);
1595   } else {
1596     NC = new CallInst(Callee, Args, Caller->getName(), Caller);
1597   }
1598
1599   // Insert a cast of the return type as necessary...
1600   Value *NV = NC;
1601   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
1602     if (NV->getType() != Type::VoidTy) {
1603       NV = NC = new CastInst(NC, Caller->getType(), "tmp");
1604       InsertNewInstBefore(NC, *Caller);
1605       AddUsesToWorkList(*Caller);
1606     } else {
1607       NV = Constant::getNullValue(Caller->getType());
1608     }
1609   }
1610
1611   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
1612     Caller->replaceAllUsesWith(NV);
1613   Caller->getParent()->getInstList().erase(Caller);
1614   removeFromWorkList(Caller);
1615   return true;
1616 }
1617
1618
1619
1620 // PHINode simplification
1621 //
1622 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
1623   // If the PHI node only has one incoming value, eliminate the PHI node...
1624   if (PN.getNumIncomingValues() == 1)
1625     return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
1626
1627   // Otherwise if all of the incoming values are the same for the PHI, replace
1628   // the PHI node with the incoming value.
1629   //
1630   Value *InVal = 0;
1631   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
1632     if (PN.getIncomingValue(i) != &PN)  // Not the PHI node itself...
1633       if (InVal && PN.getIncomingValue(i) != InVal)
1634         return 0;  // Not the same, bail out.
1635       else
1636         InVal = PN.getIncomingValue(i);
1637
1638   // The only case that could cause InVal to be null is if we have a PHI node
1639   // that only has entries for itself.  In this case, there is no entry into the
1640   // loop, so kill the PHI.
1641   //
1642   if (InVal == 0) InVal = Constant::getNullValue(PN.getType());
1643
1644   // All of the incoming values are the same, replace the PHI node now.
1645   return ReplaceInstUsesWith(PN, InVal);
1646 }
1647
1648
1649 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
1650   // Is it 'getelementptr %P, long 0'  or 'getelementptr %P'
1651   // If so, eliminate the noop.
1652   if ((GEP.getNumOperands() == 2 &&
1653        GEP.getOperand(1) == Constant::getNullValue(Type::LongTy)) ||
1654       GEP.getNumOperands() == 1)
1655     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
1656
1657   // Combine Indices - If the source pointer to this getelementptr instruction
1658   // is a getelementptr instruction, combine the indices of the two
1659   // getelementptr instructions into a single instruction.
1660   //
1661   if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
1662     std::vector<Value *> Indices;
1663
1664     // Can we combine the two pointer arithmetics offsets?
1665     if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
1666         isa<Constant>(GEP.getOperand(1))) {
1667       // Replace: gep (gep %P, long C1), long C2, ...
1668       // With:    gep %P, long (C1+C2), ...
1669       Value *Sum = ConstantExpr::get(Instruction::Add,
1670                                      cast<Constant>(Src->getOperand(1)),
1671                                      cast<Constant>(GEP.getOperand(1)));
1672       assert(Sum && "Constant folding of longs failed!?");
1673       GEP.setOperand(0, Src->getOperand(0));
1674       GEP.setOperand(1, Sum);
1675       AddUsesToWorkList(*Src);   // Reduce use count of Src
1676       return &GEP;
1677     } else if (Src->getNumOperands() == 2) {
1678       // Replace: gep (gep %P, long B), long A, ...
1679       // With:    T = long A+B; gep %P, T, ...
1680       //
1681       Value *Sum = BinaryOperator::create(Instruction::Add, Src->getOperand(1),
1682                                           GEP.getOperand(1),
1683                                           Src->getName()+".sum", &GEP);
1684       GEP.setOperand(0, Src->getOperand(0));
1685       GEP.setOperand(1, Sum);
1686       WorkList.push_back(cast<Instruction>(Sum));
1687       return &GEP;
1688     } else if (*GEP.idx_begin() == Constant::getNullValue(Type::LongTy) &&
1689                Src->getNumOperands() != 1) {
1690       // Otherwise we can do the fold if the first index of the GEP is a zero
1691       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
1692       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
1693     } else if (Src->getOperand(Src->getNumOperands()-1) ==
1694                Constant::getNullValue(Type::LongTy)) {
1695       // If the src gep ends with a constant array index, merge this get into
1696       // it, even if we have a non-zero array index.
1697       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end()-1);
1698       Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
1699     }
1700
1701     if (!Indices.empty())
1702       return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
1703
1704   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
1705     // GEP of global variable.  If all of the indices for this GEP are
1706     // constants, we can promote this to a constexpr instead of an instruction.
1707
1708     // Scan for nonconstants...
1709     std::vector<Constant*> Indices;
1710     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
1711     for (; I != E && isa<Constant>(*I); ++I)
1712       Indices.push_back(cast<Constant>(*I));
1713
1714     if (I == E) {  // If they are all constants...
1715       Constant *CE =
1716         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
1717
1718       // Replace all uses of the GEP with the new constexpr...
1719       return ReplaceInstUsesWith(GEP, CE);
1720     }
1721   }
1722
1723   return 0;
1724 }
1725
1726 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
1727   // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
1728   if (AI.isArrayAllocation())    // Check C != 1
1729     if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
1730       const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
1731       AllocationInst *New = 0;
1732
1733       // Create and insert the replacement instruction...
1734       if (isa<MallocInst>(AI))
1735         New = new MallocInst(NewTy, 0, AI.getName(), &AI);
1736       else {
1737         assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
1738         New = new AllocaInst(NewTy, 0, AI.getName(), &AI);
1739       }
1740
1741       // Scan to the end of the allocation instructions, to skip over a block of
1742       // allocas if possible...
1743       //
1744       BasicBlock::iterator It = New;
1745       while (isa<AllocationInst>(*It)) ++It;
1746
1747       // Now that I is pointing to the first non-allocation-inst in the block,
1748       // insert our getelementptr instruction...
1749       //
1750       std::vector<Value*> Idx(2, Constant::getNullValue(Type::LongTy));
1751       Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
1752
1753       // Now make everything use the getelementptr instead of the original
1754       // allocation.
1755       ReplaceInstUsesWith(AI, V);
1756       return &AI;
1757     }
1758   return 0;
1759 }
1760
1761 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
1762 /// constantexpr, return the constant value being addressed by the constant
1763 /// expression, or null if something is funny.
1764 ///
1765 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
1766   if (CE->getOperand(1) != Constant::getNullValue(Type::LongTy))
1767     return 0;  // Do not allow stepping over the value!
1768
1769   // Loop over all of the operands, tracking down which value we are
1770   // addressing...
1771   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
1772     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
1773       ConstantStruct *CS = cast<ConstantStruct>(C);
1774       if (CU->getValue() >= CS->getValues().size()) return 0;
1775       C = cast<Constant>(CS->getValues()[CU->getValue()]);
1776     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
1777       ConstantArray *CA = cast<ConstantArray>(C);
1778       if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
1779       C = cast<Constant>(CA->getValues()[CS->getValue()]);
1780     } else
1781       return 0;
1782   return C;
1783 }
1784
1785 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
1786   Value *Op = LI.getOperand(0);
1787   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Op))
1788     Op = CPR->getValue();
1789
1790   // Instcombine load (constant global) into the value loaded...
1791   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
1792     if (GV->isConstant() && !GV->isExternal())
1793       return ReplaceInstUsesWith(LI, GV->getInitializer());
1794
1795   // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
1796   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
1797     if (CE->getOpcode() == Instruction::GetElementPtr)
1798       if (ConstantPointerRef *G=dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
1799         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
1800           if (GV->isConstant() && !GV->isExternal())
1801             if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
1802               return ReplaceInstUsesWith(LI, V);
1803   return 0;
1804 }
1805
1806
1807 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
1808   // Change br (not X), label True, label False to: br X, label False, True
1809   if (BI.isConditional() && !isa<Constant>(BI.getCondition()))
1810     if (Value *V = dyn_castNotVal(BI.getCondition())) {
1811       BasicBlock *TrueDest = BI.getSuccessor(0);
1812       BasicBlock *FalseDest = BI.getSuccessor(1);
1813       // Swap Destinations and condition...
1814       BI.setCondition(V);
1815       BI.setSuccessor(0, FalseDest);
1816       BI.setSuccessor(1, TrueDest);
1817       return &BI;
1818     }
1819   return 0;
1820 }
1821
1822
1823 void InstCombiner::removeFromWorkList(Instruction *I) {
1824   WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
1825                  WorkList.end());
1826 }
1827
1828 bool InstCombiner::runOnFunction(Function &F) {
1829   bool Changed = false;
1830
1831   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
1832
1833   while (!WorkList.empty()) {
1834     Instruction *I = WorkList.back();  // Get an instruction from the worklist
1835     WorkList.pop_back();
1836
1837     // Check to see if we can DCE or ConstantPropagate the instruction...
1838     // Check to see if we can DIE the instruction...
1839     if (isInstructionTriviallyDead(I)) {
1840       // Add operands to the worklist...
1841       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1842         if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
1843           WorkList.push_back(Op);
1844
1845       ++NumDeadInst;
1846       BasicBlock::iterator BBI = I;
1847       if (dceInstruction(BBI)) {
1848         removeFromWorkList(I);
1849         continue;
1850       }
1851     }
1852
1853     // Instruction isn't dead, see if we can constant propagate it...
1854     if (Constant *C = ConstantFoldInstruction(I)) {
1855       // Add operands to the worklist...
1856       for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
1857         if (Instruction *Op = dyn_cast<Instruction>(I->getOperand(i)))
1858           WorkList.push_back(Op);
1859       ReplaceInstUsesWith(*I, C);
1860
1861       ++NumConstProp;
1862       BasicBlock::iterator BBI = I;
1863       if (dceInstruction(BBI)) {
1864         removeFromWorkList(I);
1865         continue;
1866       }
1867     }
1868
1869     // Now that we have an instruction, try combining it to simplify it...
1870     if (Instruction *Result = visit(*I)) {
1871       ++NumCombined;
1872       // Should we replace the old instruction with a new one?
1873       if (Result != I) {
1874         // Instructions can end up on the worklist more than once.  Make sure
1875         // we do not process an instruction that has been deleted.
1876         removeFromWorkList(I);
1877         ReplaceInstWithInst(I, Result);
1878       } else {
1879         BasicBlock::iterator II = I;
1880
1881         // If the instruction was modified, it's possible that it is now dead.
1882         // if so, remove it.
1883         if (dceInstruction(II)) {
1884           // Instructions may end up in the worklist more than once.  Erase them
1885           // all.
1886           removeFromWorkList(I);
1887           Result = 0;
1888         }
1889       }
1890
1891       if (Result) {
1892         WorkList.push_back(Result);
1893         AddUsesToWorkList(*Result);
1894       }
1895       Changed = true;
1896     }
1897   }
1898
1899   return Changed;
1900 }
1901
1902 Pass *createInstructionCombiningPass() {
1903   return new InstCombiner();
1904 }