lib/Transforms/Scalar/InstructionCombining.cpp

   1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by the LLVM research group and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // InstructionCombining - Combine instructions to form fewer, simple
  11 // instructions.  This pass does not modify the CFG This pass is where algebraic
  12 // simplification happens.
  13 //
  14 // This pass combines things like:
  15 //    %Y = add int %X, 1
  16 //    %Z = add int %Y, 1
  17 // into:
  18 //    %Z = add int %X, 2
  19 //
  20 // This is a simple worklist driven algorithm.
  21 //
  22 // This pass guarantees that the following canonicalizations are performed on
  23 // the program:
  24 //    1. If a binary operator has a constant operand, it is moved to the RHS
  25 //    2. Bitwise operators with constant operands are always grouped so that
  26 //       shifts are performed first, then or's, then and's, then xor's.
  27 //    3. SetCC instructions are converted from <,>,<=,>= to ==,!= if possible
  28 //    4. All SetCC instructions on boolean values are replaced with logical ops
  29 //    5. add X, X is represented as (X*2) => (X << 1)
  30 //    6. Multiplies with a power-of-two constant argument are transformed into
  31 //       shifts.
  32 //   ... etc.
  33 //
  34 //===----------------------------------------------------------------------===//
  35
  36 #define DEBUG_TYPE "instcombine"
  37 #include "llvm/Transforms/Scalar.h"
  38 #include "llvm/IntrinsicInst.h"
  39 #include "llvm/Pass.h"
  40 #include "llvm/DerivedTypes.h"
  41 #include "llvm/GlobalVariable.h"
  42 #include "llvm/Target/TargetData.h"
  43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  44 #include "llvm/Transforms/Utils/Local.h"
  45 #include "llvm/Support/CallSite.h"
  46 #include "llvm/Support/Debug.h"
  47 #include "llvm/Support/GetElementPtrTypeIterator.h"
  48 #include "llvm/Support/InstIterator.h"
  49 #include "llvm/Support/InstVisitor.h"
  50 #include "llvm/Support/PatternMatch.h"
  51 #include "llvm/ADT/Statistic.h"
  52 #include "llvm/ADT/STLExtras.h"
  53 #include <algorithm>
  54 using namespace llvm;
  55 using namespace llvm::PatternMatch;
  56
  57 namespace {
  58   Statistic<> NumCombined ("instcombine", "Number of insts combined");
  59   Statistic<> NumConstProp("instcombine", "Number of constant folds");
  60   Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
  61   Statistic<> NumSunkInst ("instcombine", "Number of instructions sunk");
  62
  63   class InstCombiner : public FunctionPass,
  64                        public InstVisitor<InstCombiner, Instruction*> {
  65     // Worklist of all of the instructions that need to be simplified.
  66     std::vector<Instruction*> WorkList;
  67     TargetData *TD;
  68
  69     /// AddUsersToWorkList - When an instruction is simplified, add all users of
  70     /// the instruction to the work lists because they might get more simplified
  71     /// now.
  72     ///
  73     void AddUsersToWorkList(Instruction &I) {
  74       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
  75            UI != UE; ++UI)
  76         WorkList.push_back(cast<Instruction>(*UI));
  77     }
  78
  79     /// AddUsesToWorkList - When an instruction is simplified, add operands to
  80     /// the work lists because they might get more simplified now.
  81     ///
  82     void AddUsesToWorkList(Instruction &I) {
  83       for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
  84         if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i)))
  85           WorkList.push_back(Op);
  86     }
  87
  88     // removeFromWorkList - remove all instances of I from the worklist.
  89     void removeFromWorkList(Instruction *I);
  90   public:
  91     virtual bool runOnFunction(Function &F);
  92
  93     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  94       AU.addRequired<TargetData>();
  95       AU.setPreservesCFG();
  96     }
  97
  98     TargetData &getTargetData() const { return *TD; }
  99
 100     // Visitation implementation - Implement instruction combining for different
 101     // instruction types.  The semantics are as follows:
 102     // Return Value:
 103     //    null        - No change was made
 104     //     I          - Change was made, I is still valid, I may be dead though
 105     //   otherwise    - Change was made, replace I with returned instruction
 106     //
 107     Instruction *visitAdd(BinaryOperator &I);
 108     Instruction *visitSub(BinaryOperator &I);
 109     Instruction *visitMul(BinaryOperator &I);
 110     Instruction *visitDiv(BinaryOperator &I);
 111     Instruction *visitRem(BinaryOperator &I);
 112     Instruction *visitAnd(BinaryOperator &I);
 113     Instruction *visitOr (BinaryOperator &I);
 114     Instruction *visitXor(BinaryOperator &I);
 115     Instruction *visitSetCondInst(BinaryOperator &I);
 116     Instruction *visitSetCondInstWithCastAndConstant(BinaryOperator&I,
 117                                                      CastInst*LHSI,
 118                                                      ConstantInt* CI);
 119     Instruction *FoldGEPSetCC(User *GEPLHS, Value *RHS,
 120                               Instruction::BinaryOps Cond, Instruction &I);
 121     Instruction *visitShiftInst(ShiftInst &I);
 122     Instruction *visitCastInst(CastInst &CI);
 123     Instruction *visitSelectInst(SelectInst &CI);
 124     Instruction *visitCallInst(CallInst &CI);
 125     Instruction *visitInvokeInst(InvokeInst &II);
 126     Instruction *visitPHINode(PHINode &PN);
 127     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
 128     Instruction *visitAllocationInst(AllocationInst &AI);
 129     Instruction *visitFreeInst(FreeInst &FI);
 130     Instruction *visitLoadInst(LoadInst &LI);
 131     Instruction *visitBranchInst(BranchInst &BI);
 132     Instruction *visitSwitchInst(SwitchInst &SI);
 133
 134     // visitInstruction - Specify what to return for unhandled instructions...
 135     Instruction *visitInstruction(Instruction &I) { return 0; }
 136
 137   private:
 138     Instruction *visitCallSite(CallSite CS);
 139     bool transformConstExprCastCall(CallSite CS);
 140
 141   public:
 142     // InsertNewInstBefore - insert an instruction New before instruction Old
 143     // in the program.  Add the new instruction to the worklist.
 144     //
 145     Instruction *InsertNewInstBefore(Instruction *New, Instruction &Old) {
 146       assert(New && New->getParent() == 0 &&
 147              "New instruction already inserted into a basic block!");
 148       BasicBlock *BB = Old.getParent();
 149       BB->getInstList().insert(&Old, New);  // Insert inst
 150       WorkList.push_back(New);              // Add to worklist
 151       return New;
 152     }
 153
 154     /// InsertCastBefore - Insert a cast of V to TY before the instruction POS.
 155     /// This also adds the cast to the worklist.  Finally, this returns the
 156     /// cast.
 157     Value *InsertCastBefore(Value *V, const Type *Ty, Instruction &Pos) {
 158       if (V->getType() == Ty) return V;
 159
 160       Instruction *C = new CastInst(V, Ty, V->getName(), &Pos);
 161       WorkList.push_back(C);
 162       return C;
 163     }
 164
 165     // ReplaceInstUsesWith - This method is to be used when an instruction is
 166     // found to be dead, replacable with another preexisting expression.  Here
 167     // we add all uses of I to the worklist, replace all uses of I with the new
 168     // value, then return I, so that the inst combiner will know that I was
 169     // modified.
 170     //
 171     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
 172       AddUsersToWorkList(I);         // Add all modified instrs to worklist
 173       if (&I != V) {
 174         I.replaceAllUsesWith(V);
 175         return &I;
 176       } else {
 177         // If we are replacing the instruction with itself, this must be in a
 178         // segment of unreachable code, so just clobber the instruction.
 179         I.replaceAllUsesWith(UndefValue::get(I.getType()));
 180         return &I;
 181       }
 182     }
 183
 184     // EraseInstFromFunction - When dealing with an instruction that has side
 185     // effects or produces a void value, we can't rely on DCE to delete the
 186     // instruction.  Instead, visit methods should return the value returned by
 187     // this function.
 188     Instruction *EraseInstFromFunction(Instruction &I) {
 189       assert(I.use_empty() && "Cannot erase instruction that is used!");
 190       AddUsesToWorkList(I);
 191       removeFromWorkList(&I);
 192       I.eraseFromParent();
 193       return 0;  // Don't do anything with FI
 194     }
 195
 196
 197   private:
 198     /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
 199     /// InsertBefore instruction.  This is specialized a bit to avoid inserting
 200     /// casts that are known to not do anything...
 201     ///
 202     Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
 203                                    Instruction *InsertBefore);
 204
 205     // SimplifyCommutative - This performs a few simplifications for commutative
 206     // operators.
 207     bool SimplifyCommutative(BinaryOperator &I);
 208
 209
 210     // FoldOpIntoPhi - Given a binary operator or cast instruction which has a
 211     // PHI node as operand #0, see if we can fold the instruction into the PHI
 212     // (which is only possible if all operands to the PHI are constants).
 213     Instruction *FoldOpIntoPhi(Instruction &I);
 214
 215     // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
 216     // operator and they all are only used by the PHI, PHI together their
 217     // inputs, and do the operation once, to the result of the PHI.
 218     Instruction *FoldPHIArgOpIntoPHI(PHINode &PN);
 219
 220     Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS,
 221                           ConstantIntegral *AndRHS, BinaryOperator &TheAnd);
 222
 223     Instruction *InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
 224                                  bool Inside, Instruction &IB);
 225   };
 226
 227   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
 228 }
 229
 230 // getComplexity:  Assign a complexity or rank value to LLVM Values...
 231 //   0 -> undef, 1 -> Const, 2 -> Other, 3 -> Arg, 3 -> Unary, 4 -> OtherInst
 232 static unsigned getComplexity(Value *V) {
 233   if (isa<Instruction>(V)) {
 234     if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
 235       return 3;
 236     return 4;
 237   }
 238   if (isa<Argument>(V)) return 3;
 239   return isa<Constant>(V) ? (isa<UndefValue>(V) ? 0 : 1) : 2;
 240 }
 241
 242 // isOnlyUse - Return true if this instruction will be deleted if we stop using
 243 // it.
 244 static bool isOnlyUse(Value *V) {
 245   return V->hasOneUse() || isa<Constant>(V);
 246 }
 247
 248 // getPromotedType - Return the specified type promoted as it would be to pass
 249 // though a va_arg area...
 250 static const Type *getPromotedType(const Type *Ty) {
 251   switch (Ty->getTypeID()) {
 252   case Type::SByteTyID:
 253   case Type::ShortTyID:  return Type::IntTy;
 254   case Type::UByteTyID:
 255   case Type::UShortTyID: return Type::UIntTy;
 256   case Type::FloatTyID:  return Type::DoubleTy;
 257   default:               return Ty;
 258   }
 259 }
 260
 261 // SimplifyCommutative - This performs a few simplifications for commutative
 262 // operators:
 263 //
 264 //  1. Order operands such that they are listed from right (least complex) to
 265 //     left (most complex).  This puts constants before unary operators before
 266 //     binary operators.
 267 //
 268 //  2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
 269 //  3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 270 //
 271 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
 272   bool Changed = false;
 273   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
 274     Changed = !I.swapOperands();
 275
 276   if (!I.isAssociative()) return Changed;
 277   Instruction::BinaryOps Opcode = I.getOpcode();
 278   if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
 279     if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
 280       if (isa<Constant>(I.getOperand(1))) {
 281         Constant *Folded = ConstantExpr::get(I.getOpcode(),
 282                                              cast<Constant>(I.getOperand(1)),
 283                                              cast<Constant>(Op->getOperand(1)));
 284         I.setOperand(0, Op->getOperand(0));
 285         I.setOperand(1, Folded);
 286         return true;
 287       } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
 288         if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
 289             isOnlyUse(Op) && isOnlyUse(Op1)) {
 290           Constant *C1 = cast<Constant>(Op->getOperand(1));
 291           Constant *C2 = cast<Constant>(Op1->getOperand(1));
 292
 293           // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 294           Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
 295           Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
 296                                                     Op1->getOperand(0),
 297                                                     Op1->getName(), &I);
 298           WorkList.push_back(New);
 299           I.setOperand(0, New);
 300           I.setOperand(1, Folded);
 301           return true;
 302         }
 303     }
 304   return Changed;
 305 }
 306
 307 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
 308 // if the LHS is a constant zero (which is the 'negate' form).
 309 //
 310 static inline Value *dyn_castNegVal(Value *V) {
 311   if (BinaryOperator::isNeg(V))
 312     return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
 313
 314   // Constants can be considered to be negated values if they can be folded.
 315   if (ConstantInt *C = dyn_cast<ConstantInt>(V))
 316     return ConstantExpr::getNeg(C);
 317   return 0;
 318 }
 319
 320 static inline Value *dyn_castNotVal(Value *V) {
 321   if (BinaryOperator::isNot(V))
 322     return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
 323
 324   // Constants can be considered to be not'ed values...
 325   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
 326     return ConstantExpr::getNot(C);
 327   return 0;
 328 }
 329
 330 // dyn_castFoldableMul - If this value is a multiply that can be folded into
 331 // other computations (because it has a constant operand), return the
 332 // non-constant operand of the multiply, and set CST to point to the multiplier.
 333 // Otherwise, return null.
 334 //
 335 static inline Value *dyn_castFoldableMul(Value *V, ConstantInt *&CST) {
 336   if (V->hasOneUse() && V->getType()->isInteger())
 337     if (Instruction *I = dyn_cast<Instruction>(V)) {
 338       if (I->getOpcode() == Instruction::Mul)
 339         if ((CST = dyn_cast<ConstantInt>(I->getOperand(1))))
 340           return I->getOperand(0);
 341       if (I->getOpcode() == Instruction::Shl)
 342         if ((CST = dyn_cast<ConstantInt>(I->getOperand(1)))) {
 343           // The multiplier is really 1 << CST.
 344           Constant *One = ConstantInt::get(V->getType(), 1);
 345           CST = cast<ConstantInt>(ConstantExpr::getShl(One, CST));
 346           return I->getOperand(0);
 347         }
 348     }
 349   return 0;
 350 }
 351
 352 /// dyn_castGetElementPtr - If this is a getelementptr instruction or constant
 353 /// expression, return it.
 354 static User *dyn_castGetElementPtr(Value *V) {
 355   if (isa<GetElementPtrInst>(V)) return cast<User>(V);
 356   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(V))
 357     if (CE->getOpcode() == Instruction::GetElementPtr)
 358       return cast<User>(V);
 359   return false;
 360 }
 361
 362 // Log2 - Calculate the log base 2 for the specified value if it is exactly a
 363 // power of 2.
 364 static unsigned Log2(uint64_t Val) {
 365   assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!");
 366   unsigned Count = 0;
 367   while (Val != 1) {
 368     if (Val & 1) return 0;    // Multiple bits set?
 369     Val >>= 1;
 370     ++Count;
 371   }
 372   return Count;
 373 }
 374
 375 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
 376 static ConstantInt *AddOne(ConstantInt *C) {
 377   return cast<ConstantInt>(ConstantExpr::getAdd(C,
 378                                          ConstantInt::get(C->getType(), 1)));
 379 }
 380 static ConstantInt *SubOne(ConstantInt *C) {
 381   return cast<ConstantInt>(ConstantExpr::getSub(C,
 382                                          ConstantInt::get(C->getType(), 1)));
 383 }
 384
 385 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
 386 // true when both operands are equal...
 387 //
 388 static bool isTrueWhenEqual(Instruction &I) {
 389   return I.getOpcode() == Instruction::SetEQ ||
 390          I.getOpcode() == Instruction::SetGE ||
 391          I.getOpcode() == Instruction::SetLE;
 392 }
 393
 394 /// AssociativeOpt - Perform an optimization on an associative operator.  This
 395 /// function is designed to check a chain of associative operators for a
 396 /// potential to apply a certain optimization.  Since the optimization may be
 397 /// applicable if the expression was reassociated, this checks the chain, then
 398 /// reassociates the expression as necessary to expose the optimization
 399 /// opportunity.  This makes use of a special Functor, which must define
 400 /// 'shouldApply' and 'apply' methods.
 401 ///
 402 template<typename Functor>
 403 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) {
 404   unsigned Opcode = Root.getOpcode();
 405   Value *LHS = Root.getOperand(0);
 406
 407   // Quick check, see if the immediate LHS matches...
 408   if (F.shouldApply(LHS))
 409     return F.apply(Root);
 410
 411   // Otherwise, if the LHS is not of the same opcode as the root, return.
 412   Instruction *LHSI = dyn_cast<Instruction>(LHS);
 413   while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) {
 414     // Should we apply this transform to the RHS?
 415     bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
 416
 417     // If not to the RHS, check to see if we should apply to the LHS...
 418     if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) {
 419       cast<BinaryOperator>(LHSI)->swapOperands();   // Make the LHS the RHS
 420       ShouldApply = true;
 421     }
 422
 423     // If the functor wants to apply the optimization to the RHS of LHSI,
 424     // reassociate the expression from ((? op A) op B) to (? op (A op B))
 425     if (ShouldApply) {
 426       BasicBlock *BB = Root.getParent();
 427
 428       // Now all of the instructions are in the current basic block, go ahead
 429       // and perform the reassociation.
 430       Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
 431
 432       // First move the selected RHS to the LHS of the root...
 433       Root.setOperand(0, LHSI->getOperand(1));
 434
 435       // Make what used to be the LHS of the root be the user of the root...
 436       Value *ExtraOperand = TmpLHSI->getOperand(1);
 437       if (&Root == TmpLHSI) {
 438         Root.replaceAllUsesWith(Constant::getNullValue(TmpLHSI->getType()));
 439         return 0;
 440       }
 441       Root.replaceAllUsesWith(TmpLHSI);          // Users now use TmpLHSI
 442       TmpLHSI->setOperand(1, &Root);             // TmpLHSI now uses the root
 443       TmpLHSI->getParent()->getInstList().remove(TmpLHSI);
 444       BasicBlock::iterator ARI = &Root; ++ARI;
 445       BB->getInstList().insert(ARI, TmpLHSI);    // Move TmpLHSI to after Root
 446       ARI = Root;
 447
 448       // Now propagate the ExtraOperand down the chain of instructions until we
 449       // get to LHSI.
 450       while (TmpLHSI != LHSI) {
 451         Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
 452         // Move the instruction to immediately before the chain we are
 453         // constructing to avoid breaking dominance properties.
 454         NextLHSI->getParent()->getInstList().remove(NextLHSI);
 455         BB->getInstList().insert(ARI, NextLHSI);
 456         ARI = NextLHSI;
 457
 458         Value *NextOp = NextLHSI->getOperand(1);
 459         NextLHSI->setOperand(1, ExtraOperand);
 460         TmpLHSI = NextLHSI;
 461         ExtraOperand = NextOp;
 462       }
 463
 464       // Now that the instructions are reassociated, have the functor perform
 465       // the transformation...
 466       return F.apply(Root);
 467     }
 468
 469     LHSI = dyn_cast<Instruction>(LHSI->getOperand(0));
 470   }
 471   return 0;
 472 }
 473
 474
 475 // AddRHS - Implements: X + X --> X << 1
 476 struct AddRHS {
 477   Value *RHS;
 478   AddRHS(Value *rhs) : RHS(rhs) {}
 479   bool shouldApply(Value *LHS) const { return LHS == RHS; }
 480   Instruction *apply(BinaryOperator &Add) const {
 481     return new ShiftInst(Instruction::Shl, Add.getOperand(0),
 482                          ConstantInt::get(Type::UByteTy, 1));
 483   }
 484 };
 485
 486 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2)
 487 //                 iff C1&C2 == 0
 488 struct AddMaskingAnd {
 489   Constant *C2;
 490   AddMaskingAnd(Constant *c) : C2(c) {}
 491   bool shouldApply(Value *LHS) const {
 492     ConstantInt *C1;
 493     return match(LHS, m_And(m_Value(), m_ConstantInt(C1))) &&
 494            ConstantExpr::getAnd(C1, C2)->isNullValue();
 495   }
 496   Instruction *apply(BinaryOperator &Add) const {
 497     return BinaryOperator::createOr(Add.getOperand(0), Add.getOperand(1));
 498   }
 499 };
 500
 501 static Value *FoldOperationIntoSelectOperand(Instruction &I, Value *SO,
 502                                              InstCombiner *IC) {
 503   if (isa<CastInst>(I)) {
 504     if (Constant *SOC = dyn_cast<Constant>(SO))
 505       return ConstantExpr::getCast(SOC, I.getType());
 506
 507     return IC->InsertNewInstBefore(new CastInst(SO, I.getType(),
 508                                                 SO->getName() + ".cast"), I);
 509   }
 510
 511   // Figure out if the constant is the left or the right argument.
 512   bool ConstIsRHS = isa<Constant>(I.getOperand(1));
 513   Constant *ConstOperand = cast<Constant>(I.getOperand(ConstIsRHS));
 514
 515   if (Constant *SOC = dyn_cast<Constant>(SO)) {
 516     if (ConstIsRHS)
 517       return ConstantExpr::get(I.getOpcode(), SOC, ConstOperand);
 518     return ConstantExpr::get(I.getOpcode(), ConstOperand, SOC);
 519   }
 520
 521   Value *Op0 = SO, *Op1 = ConstOperand;
 522   if (!ConstIsRHS)
 523     std::swap(Op0, Op1);
 524   Instruction *New;
 525   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&I))
 526     New = BinaryOperator::create(BO->getOpcode(), Op0, Op1,SO->getName()+".op");
 527   else if (ShiftInst *SI = dyn_cast<ShiftInst>(&I))
 528     New = new ShiftInst(SI->getOpcode(), Op0, Op1, SO->getName()+".sh");
 529   else {
 530     assert(0 && "Unknown binary instruction type!");
 531     abort();
 532   }
 533   return IC->InsertNewInstBefore(New, I);
 534 }
 535
 536 // FoldOpIntoSelect - Given an instruction with a select as one operand and a
 537 // constant as the other operand, try to fold the binary operator into the
 538 // select arguments.  This also works for Cast instructions, which obviously do
 539 // not have a second operand.
 540 static Instruction *FoldOpIntoSelect(Instruction &Op, SelectInst *SI,
 541                                      InstCombiner *IC) {
 542   // Don't modify shared select instructions
 543   if (!SI->hasOneUse()) return 0;
 544   Value *TV = SI->getOperand(1);
 545   Value *FV = SI->getOperand(2);
 546
 547   if (isa<Constant>(TV) || isa<Constant>(FV)) {
 548     Value *SelectTrueVal = FoldOperationIntoSelectOperand(Op, TV, IC);
 549     Value *SelectFalseVal = FoldOperationIntoSelectOperand(Op, FV, IC);
 550
 551     return new SelectInst(SI->getCondition(), SelectTrueVal,
 552                           SelectFalseVal);
 553   }
 554   return 0;
 555 }
 556
 557
 558 /// FoldOpIntoPhi - Given a binary operator or cast instruction which has a PHI
 559 /// node as operand #0, see if we can fold the instruction into the PHI (which
 560 /// is only possible if all operands to the PHI are constants).
 561 Instruction *InstCombiner::FoldOpIntoPhi(Instruction &I) {
 562   PHINode *PN = cast<PHINode>(I.getOperand(0));
 563   unsigned NumPHIValues = PN->getNumIncomingValues();
 564   if (!PN->hasOneUse() || NumPHIValues == 0 ||
 565       !isa<Constant>(PN->getIncomingValue(0))) return 0;
 566
 567   // Check to see if all of the operands of the PHI are constants.  If not, we
 568   // cannot do the transformation.
 569   for (unsigned i = 1; i != NumPHIValues; ++i)
 570     if (!isa<Constant>(PN->getIncomingValue(i)))
 571       return 0;
 572
 573   // Okay, we can do the transformation: create the new PHI node.
 574   PHINode *NewPN = new PHINode(I.getType(), I.getName());
 575   I.setName("");
 576   NewPN->op_reserve(PN->getNumOperands());
 577   InsertNewInstBefore(NewPN, *PN);
 578
 579   // Next, add all of the operands to the PHI.
 580   if (I.getNumOperands() == 2) {
 581     Constant *C = cast<Constant>(I.getOperand(1));
 582     for (unsigned i = 0; i != NumPHIValues; ++i) {
 583       Constant *InV = cast<Constant>(PN->getIncomingValue(i));
 584       NewPN->addIncoming(ConstantExpr::get(I.getOpcode(), InV, C),
 585                          PN->getIncomingBlock(i));
 586     }
 587   } else {
 588     assert(isa<CastInst>(I) && "Unary op should be a cast!");
 589     const Type *RetTy = I.getType();
 590     for (unsigned i = 0; i != NumPHIValues; ++i) {
 591       Constant *InV = cast<Constant>(PN->getIncomingValue(i));
 592       NewPN->addIncoming(ConstantExpr::getCast(InV, RetTy),
 593                          PN->getIncomingBlock(i));
 594     }
 595   }
 596   return ReplaceInstUsesWith(I, NewPN);
 597 }
 598
 599 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 600   bool Changed = SimplifyCommutative(I);
 601   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 602
 603   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 604     // X + undef -> undef
 605     if (isa<UndefValue>(RHS))
 606       return ReplaceInstUsesWith(I, RHS);
 607
 608     // X + 0 --> X
 609     if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop
 610         RHSC->isNullValue())
 611       return ReplaceInstUsesWith(I, LHS);
 612
 613     // X + (signbit) --> X ^ signbit
 614     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) {
 615       unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
 616       uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1;
 617       if (Val == (1ULL << (NumBits-1)))
 618         return BinaryOperator::createXor(LHS, RHS);
 619     }
 620
 621     if (isa<PHINode>(LHS))
 622       if (Instruction *NV = FoldOpIntoPhi(I))
 623         return NV;
 624   }
 625
 626   // X + X --> X << 1
 627   if (I.getType()->isInteger()) {
 628     if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
 629   }
 630
 631   // -A + B  -->  B - A
 632   if (Value *V = dyn_castNegVal(LHS))
 633     return BinaryOperator::createSub(RHS, V);
 634
 635   // A + -B  -->  A - B
 636   if (!isa<Constant>(RHS))
 637     if (Value *V = dyn_castNegVal(RHS))
 638       return BinaryOperator::createSub(LHS, V);
 639
 640   ConstantInt *C2;
 641   if (Value *X = dyn_castFoldableMul(LHS, C2)) {
 642     if (X == RHS)   // X*C + X --> X * (C+1)
 643       return BinaryOperator::createMul(RHS, AddOne(C2));
 644
 645     // X*C1 + X*C2 --> X * (C1+C2)
 646     ConstantInt *C1;
 647     if (X == dyn_castFoldableMul(RHS, C1))
 648       return BinaryOperator::createMul(X, ConstantExpr::getAdd(C1, C2));
 649   }
 650
 651   // X + X*C --> X * (C+1)
 652   if (dyn_castFoldableMul(RHS, C2) == LHS)
 653     return BinaryOperator::createMul(LHS, AddOne(C2));
 654
 655
 656   // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
 657   if (match(RHS, m_And(m_Value(), m_ConstantInt(C2))))
 658     if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
 659
 660   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
 661     Value *X;
 662     if (match(LHS, m_Not(m_Value(X)))) {   // ~X + C --> (C-1) - X
 663       Constant *C= ConstantExpr::getSub(CRHS, ConstantInt::get(I.getType(), 1));
 664       return BinaryOperator::createSub(C, X);
 665     }
 666
 667     // (X & FF00) + xx00  -> (X+xx00) & FF00
 668     if (LHS->hasOneUse() && match(LHS, m_And(m_Value(X), m_ConstantInt(C2)))) {
 669       Constant *Anded = ConstantExpr::getAnd(CRHS, C2);
 670       if (Anded == CRHS) {
 671         // See if all bits from the first bit set in the Add RHS up are included
 672         // in the mask.  First, get the rightmost bit.
 673         uint64_t AddRHSV = CRHS->getRawValue();
 674
 675         // Form a mask of all bits from the lowest bit added through the top.
 676         uint64_t AddRHSHighBits = ~((AddRHSV & -AddRHSV)-1);
 677         AddRHSHighBits &= (1ULL << C2->getType()->getPrimitiveSize()*8)-1;
 678
 679         // See if the and mask includes all of these bits.
 680         uint64_t AddRHSHighBitsAnd = AddRHSHighBits & C2->getRawValue();
 681
 682         if (AddRHSHighBits == AddRHSHighBitsAnd) {
 683           // Okay, the xform is safe.  Insert the new add pronto.
 684           Value *NewAdd = InsertNewInstBefore(BinaryOperator::createAdd(X, CRHS,
 685                                                             LHS->getName()), I);
 686           return BinaryOperator::createAnd(NewAdd, C2);
 687         }
 688       }
 689     }
 690
 691     // Try to fold constant add into select arguments.
 692     if (SelectInst *SI = dyn_cast<SelectInst>(LHS))
 693       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
 694         return R;
 695   }
 696
 697   return Changed ? &I : 0;
 698 }
 699
 700 // isSignBit - Return true if the value represented by the constant only has the
 701 // highest order bit set.
 702 static bool isSignBit(ConstantInt *CI) {
 703   unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
 704   return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1));
 705 }
 706
 707 static unsigned getTypeSizeInBits(const Type *Ty) {
 708   return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8;
 709 }
 710
 711 /// RemoveNoopCast - Strip off nonconverting casts from the value.
 712 ///
 713 static Value *RemoveNoopCast(Value *V) {
 714   if (CastInst *CI = dyn_cast<CastInst>(V)) {
 715     const Type *CTy = CI->getType();
 716     const Type *OpTy = CI->getOperand(0)->getType();
 717     if (CTy->isInteger() && OpTy->isInteger()) {
 718       if (CTy->getPrimitiveSize() == OpTy->getPrimitiveSize())
 719         return RemoveNoopCast(CI->getOperand(0));
 720     } else if (isa<PointerType>(CTy) && isa<PointerType>(OpTy))
 721       return RemoveNoopCast(CI->getOperand(0));
 722   }
 723   return V;
 724 }
 725
 726 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 727   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 728
 729   if (Op0 == Op1)         // sub X, X  -> 0
 730     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 731
 732   // If this is a 'B = x-(-A)', change to B = x+A...
 733   if (Value *V = dyn_castNegVal(Op1))
 734     return BinaryOperator::createAdd(Op0, V);
 735
 736   if (isa<UndefValue>(Op0))
 737     return ReplaceInstUsesWith(I, Op0);    // undef - X -> undef
 738   if (isa<UndefValue>(Op1))
 739     return ReplaceInstUsesWith(I, Op1);    // X - undef -> undef
 740
 741   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
 742     // Replace (-1 - A) with (~A)...
 743     if (C->isAllOnesValue())
 744       return BinaryOperator::createNot(Op1);
 745
 746     // C - ~X == X + (1+C)
 747     Value *X;
 748     if (match(Op1, m_Not(m_Value(X))))
 749       return BinaryOperator::createAdd(X,
 750                     ConstantExpr::getAdd(C, ConstantInt::get(I.getType(), 1)));
 751     // -((uint)X >> 31) -> ((int)X >> 31)
 752     // -((int)X >> 31) -> ((uint)X >> 31)
 753     if (C->isNullValue()) {
 754       Value *NoopCastedRHS = RemoveNoopCast(Op1);
 755       if (ShiftInst *SI = dyn_cast<ShiftInst>(NoopCastedRHS))
 756         if (SI->getOpcode() == Instruction::Shr)
 757           if (ConstantUInt *CU = dyn_cast<ConstantUInt>(SI->getOperand(1))) {
 758             const Type *NewTy;
 759             if (SI->getType()->isSigned())
 760               NewTy = SI->getType()->getUnsignedVersion();
 761             else
 762               NewTy = SI->getType()->getSignedVersion();
 763             // Check to see if we are shifting out everything but the sign bit.
 764             if (CU->getValue() == SI->getType()->getPrimitiveSize()*8-1) {
 765               // Ok, the transformation is safe.  Insert a cast of the incoming
 766               // value, then the new shift, then the new cast.
 767               Instruction *FirstCast = new CastInst(SI->getOperand(0), NewTy,
 768                                                  SI->getOperand(0)->getName());
 769               Value *InV = InsertNewInstBefore(FirstCast, I);
 770               Instruction *NewShift = new ShiftInst(Instruction::Shr, FirstCast,
 771                                                     CU, SI->getName());
 772               if (NewShift->getType() == I.getType())
 773                 return NewShift;
 774               else {
 775                 InV = InsertNewInstBefore(NewShift, I);
 776                 return new CastInst(NewShift, I.getType());
 777               }
 778             }
 779           }
 780     }
 781
 782     // Try to fold constant sub into select arguments.
 783     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 784       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
 785         return R;
 786
 787     if (isa<PHINode>(Op0))
 788       if (Instruction *NV = FoldOpIntoPhi(I))
 789         return NV;
 790   }
 791
 792   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
 793     if (Op1I->hasOneUse()) {
 794       // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
 795       // is not used by anyone else...
 796       //
 797       if (Op1I->getOpcode() == Instruction::Sub &&
 798           !Op1I->getType()->isFloatingPoint()) {
 799         // Swap the two operands of the subexpr...
 800         Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 801         Op1I->setOperand(0, IIOp1);
 802         Op1I->setOperand(1, IIOp0);
 803
 804         // Create the new top level add instruction...
 805         return BinaryOperator::createAdd(Op0, Op1);
 806       }
 807
 808       // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
 809       //
 810       if (Op1I->getOpcode() == Instruction::And &&
 811           (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
 812         Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
 813
 814         Value *NewNot =
 815           InsertNewInstBefore(BinaryOperator::createNot(OtherOp, "B.not"), I);
 816         return BinaryOperator::createAnd(Op0, NewNot);
 817       }
 818
 819       // -(X sdiv C)  -> (X sdiv -C)
 820       if (Op1I->getOpcode() == Instruction::Div)
 821         if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
 822           if (CSI->getValue() == 0)
 823             if (Constant *DivRHS = dyn_cast<Constant>(Op1I->getOperand(1)))
 824               return BinaryOperator::createDiv(Op1I->getOperand(0),
 825                                                ConstantExpr::getNeg(DivRHS));
 826
 827       // X - X*C --> X * (1-C)
 828       ConstantInt *C2;
 829       if (dyn_castFoldableMul(Op1I, C2) == Op0) {
 830         Constant *CP1 =
 831           ConstantExpr::getSub(ConstantInt::get(I.getType(), 1), C2);
 832         return BinaryOperator::createMul(Op0, CP1);
 833       }
 834     }
 835
 836
 837   ConstantInt *C1;
 838   if (Value *X = dyn_castFoldableMul(Op0, C1)) {
 839     if (X == Op1) { // X*C - X --> X * (C-1)
 840       Constant *CP1 = ConstantExpr::getSub(C1, ConstantInt::get(I.getType(),1));
 841       return BinaryOperator::createMul(Op1, CP1);
 842     }
 843
 844     ConstantInt *C2;   // X*C1 - X*C2 -> X * (C1-C2)
 845     if (X == dyn_castFoldableMul(Op1, C2))
 846       return BinaryOperator::createMul(Op1, ConstantExpr::getSub(C1, C2));
 847   }
 848   return 0;
 849 }
 850
 851 /// isSignBitCheck - Given an exploded setcc instruction, return true if it is
 852 /// really just returns true if the most significant (sign) bit is set.
 853 static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) {
 854   if (RHS->getType()->isSigned()) {
 855     // True if source is LHS < 0 or LHS <= -1
 856     return Opcode == Instruction::SetLT && RHS->isNullValue() ||
 857            Opcode == Instruction::SetLE && RHS->isAllOnesValue();
 858   } else {
 859     ConstantUInt *RHSC = cast<ConstantUInt>(RHS);
 860     // True if source is LHS > 127 or LHS >= 128, where the constants depend on
 861     // the size of the integer type.
 862     if (Opcode == Instruction::SetGE)
 863       return RHSC->getValue() == 1ULL<<(RHS->getType()->getPrimitiveSize()*8-1);
 864     if (Opcode == Instruction::SetGT)
 865       return RHSC->getValue() ==
 866         (1ULL << (RHS->getType()->getPrimitiveSize()*8-1))-1;
 867   }
 868   return false;
 869 }
 870
 871 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 872   bool Changed = SimplifyCommutative(I);
 873   Value *Op0 = I.getOperand(0);
 874
 875   if (isa<UndefValue>(I.getOperand(1)))              // undef * X -> 0
 876     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 877
 878   // Simplify mul instructions with a constant RHS...
 879   if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
 880     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 881
 882       // ((X << C1)*C2) == (X * (C2 << C1))
 883       if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
 884         if (SI->getOpcode() == Instruction::Shl)
 885           if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
 886             return BinaryOperator::createMul(SI->getOperand(0),
 887                                              ConstantExpr::getShl(CI, ShOp));
 888
 889       if (CI->isNullValue())
 890         return ReplaceInstUsesWith(I, Op1);  // X * 0  == 0
 891       if (CI->equalsInt(1))                  // X * 1  == X
 892         return ReplaceInstUsesWith(I, Op0);
 893       if (CI->isAllOnesValue())              // X * -1 == 0 - X
 894         return BinaryOperator::createNeg(Op0, I.getName());
 895
 896       int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
 897       if (uint64_t C = Log2(Val))            // Replace X*(2^C) with X << C
 898         return new ShiftInst(Instruction::Shl, Op0,
 899                              ConstantUInt::get(Type::UByteTy, C));
 900     } else if (ConstantFP *Op1F = dyn_cast<ConstantFP>(Op1)) {
 901       if (Op1F->isNullValue())
 902         return ReplaceInstUsesWith(I, Op1);
 903
 904       // "In IEEE floating point, x*1 is not equivalent to x for nans.  However,
 905       // ANSI says we can drop signals, so we can do this anyway." (from GCC)
 906       if (Op1F->getValue() == 1.0)
 907         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'mul double %X, 1.0'
 908     }
 909
 910     // Try to fold constant mul into select arguments.
 911     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 912       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
 913         return R;
 914
 915     if (isa<PHINode>(Op0))
 916       if (Instruction *NV = FoldOpIntoPhi(I))
 917         return NV;
 918   }
 919
 920   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
 921     if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
 922       return BinaryOperator::createMul(Op0v, Op1v);
 923
 924   // If one of the operands of the multiply is a cast from a boolean value, then
 925   // we know the bool is either zero or one, so this is a 'masking' multiply.
 926   // See if we can simplify things based on how the boolean was originally
 927   // formed.
 928   CastInst *BoolCast = 0;
 929   if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(0)))
 930     if (CI->getOperand(0)->getType() == Type::BoolTy)
 931       BoolCast = CI;
 932   if (!BoolCast)
 933     if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(1)))
 934       if (CI->getOperand(0)->getType() == Type::BoolTy)
 935         BoolCast = CI;
 936   if (BoolCast) {
 937     if (SetCondInst *SCI = dyn_cast<SetCondInst>(BoolCast->getOperand(0))) {
 938       Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1);
 939       const Type *SCOpTy = SCIOp0->getType();
 940
 941       // If the setcc is true iff the sign bit of X is set, then convert this
 942       // multiply into a shift/and combination.
 943       if (isa<ConstantInt>(SCIOp1) &&
 944           isSignBitCheck(SCI->getOpcode(), SCIOp0, cast<ConstantInt>(SCIOp1))) {
 945         // Shift the X value right to turn it into "all signbits".
 946         Constant *Amt = ConstantUInt::get(Type::UByteTy,
 947                                           SCOpTy->getPrimitiveSize()*8-1);
 948         if (SCIOp0->getType()->isUnsigned()) {
 949           const Type *NewTy = SCIOp0->getType()->getSignedVersion();
 950           SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy,
 951                                                     SCIOp0->getName()), I);
 952         }
 953
 954         Value *V =
 955           InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt,
 956                                             BoolCast->getOperand(0)->getName()+
 957                                             ".mask"), I);
 958
 959         // If the multiply type is not the same as the source type, sign extend
 960         // or truncate to the multiply type.
 961         if (I.getType() != V->getType())
 962           V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I);
 963
 964         Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
 965         return BinaryOperator::createAnd(V, OtherOp);
 966       }
 967     }
 968   }
 969
 970   return Changed ? &I : 0;
 971 }
 972
 973 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
 974   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 975
 976   if (isa<UndefValue>(Op0))              // undef / X -> 0
 977     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 978   if (isa<UndefValue>(Op1))
 979     return ReplaceInstUsesWith(I, Op1);  // X / undef -> undef
 980
 981   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
 982     // div X, 1 == X
 983     if (RHS->equalsInt(1))
 984       return ReplaceInstUsesWith(I, Op0);
 985
 986     // div X, -1 == -X
 987     if (RHS->isAllOnesValue())
 988       return BinaryOperator::createNeg(Op0);
 989
 990     if (Instruction *LHS = dyn_cast<Instruction>(Op0))
 991       if (LHS->getOpcode() == Instruction::Div)
 992         if (ConstantInt *LHSRHS = dyn_cast<ConstantInt>(LHS->getOperand(1))) {
 993           // (X / C1) / C2  -> X / (C1*C2)
 994           return BinaryOperator::createDiv(LHS->getOperand(0),
 995                                            ConstantExpr::getMul(RHS, LHSRHS));
 996         }
 997
 998     // Check to see if this is an unsigned division with an exact power of 2,
 999     // if so, convert to a right shift.
1000     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
1001       if (uint64_t Val = C->getValue())    // Don't break X / 0
1002         if (uint64_t C = Log2(Val))
1003           return new ShiftInst(Instruction::Shr, Op0,
1004                                ConstantUInt::get(Type::UByteTy, C));
1005
1006     // -X/C -> X/-C
1007     if (RHS->getType()->isSigned())
1008       if (Value *LHSNeg = dyn_castNegVal(Op0))
1009         return BinaryOperator::createDiv(LHSNeg, ConstantExpr::getNeg(RHS));
1010
1011     if (!RHS->isNullValue()) {
1012       if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1013         if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1014           return R;
1015       if (isa<PHINode>(Op0))
1016         if (Instruction *NV = FoldOpIntoPhi(I))
1017           return NV;
1018     }
1019   }
1020
1021   // If this is 'udiv X, (Cond ? C1, C2)' where C1&C2 are powers of two,
1022   // transform this into: '(Cond ? (udiv X, C1) : (udiv X, C2))'.
1023   if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1024     if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
1025       if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
1026         if (STO->getValue() == 0) { // Couldn't be this argument.
1027           I.setOperand(1, SFO);
1028           return &I;
1029         } else if (SFO->getValue() == 0) {
1030           I.setOperand(1, STO);
1031           return &I;
1032         }
1033
1034         if (uint64_t TSA = Log2(STO->getValue()))
1035           if (uint64_t FSA = Log2(SFO->getValue())) {
1036             Constant *TC = ConstantUInt::get(Type::UByteTy, TSA);
1037             Instruction *TSI = new ShiftInst(Instruction::Shr, Op0,
1038                                              TC, SI->getName()+".t");
1039             TSI = InsertNewInstBefore(TSI, I);
1040
1041             Constant *FC = ConstantUInt::get(Type::UByteTy, FSA);
1042             Instruction *FSI = new ShiftInst(Instruction::Shr, Op0,
1043                                              FC, SI->getName()+".f");
1044             FSI = InsertNewInstBefore(FSI, I);
1045             return new SelectInst(SI->getOperand(0), TSI, FSI);
1046           }
1047       }
1048
1049   // 0 / X == 0, we don't need to preserve faults!
1050   if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
1051     if (LHS->equalsInt(0))
1052       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1053
1054   return 0;
1055 }
1056
1057
1058 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
1059   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1060   if (I.getType()->isSigned())
1061     if (Value *RHSNeg = dyn_castNegVal(Op1))
1062       if (!isa<ConstantSInt>(RHSNeg) ||
1063           cast<ConstantSInt>(RHSNeg)->getValue() > 0) {
1064         // X % -Y -> X % Y
1065         AddUsesToWorkList(I);
1066         I.setOperand(1, RHSNeg);
1067         return &I;
1068       }
1069
1070   if (isa<UndefValue>(Op0))              // undef % X -> 0
1071     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1072   if (isa<UndefValue>(Op1))
1073     return ReplaceInstUsesWith(I, Op1);  // X % undef -> undef
1074
1075   if (ConstantInt *RHS = dyn_cast<ConstantInt>(Op1)) {
1076     if (RHS->equalsInt(1))  // X % 1 == 0
1077       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1078
1079     // Check to see if this is an unsigned remainder with an exact power of 2,
1080     // if so, convert to a bitwise and.
1081     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
1082       if (uint64_t Val = C->getValue())    // Don't break X % 0 (divide by zero)
1083         if (!(Val & (Val-1)))              // Power of 2
1084           return BinaryOperator::createAnd(Op0,
1085                                          ConstantUInt::get(I.getType(), Val-1));
1086
1087     if (!RHS->isNullValue()) {
1088       if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1089         if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1090           return R;
1091       if (isa<PHINode>(Op0))
1092         if (Instruction *NV = FoldOpIntoPhi(I))
1093           return NV;
1094     }
1095   }
1096
1097   // If this is 'urem X, (Cond ? C1, C2)' where C1&C2 are powers of two,
1098   // transform this into: '(Cond ? (urem X, C1) : (urem X, C2))'.
1099   if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1100     if (ConstantUInt *STO = dyn_cast<ConstantUInt>(SI->getOperand(1)))
1101       if (ConstantUInt *SFO = dyn_cast<ConstantUInt>(SI->getOperand(2))) {
1102         if (STO->getValue() == 0) { // Couldn't be this argument.
1103           I.setOperand(1, SFO);
1104           return &I;
1105         } else if (SFO->getValue() == 0) {
1106           I.setOperand(1, STO);
1107           return &I;
1108         }
1109
1110         if (!(STO->getValue() & (STO->getValue()-1)) &&
1111             !(SFO->getValue() & (SFO->getValue()-1))) {
1112           Value *TrueAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
1113                                          SubOne(STO), SI->getName()+".t"), I);
1114           Value *FalseAnd = InsertNewInstBefore(BinaryOperator::createAnd(Op0,
1115                                          SubOne(SFO), SI->getName()+".f"), I);
1116           return new SelectInst(SI->getOperand(0), TrueAnd, FalseAnd);
1117         }
1118       }
1119
1120   // 0 % X == 0, we don't need to preserve faults!
1121   if (ConstantInt *LHS = dyn_cast<ConstantInt>(Op0))
1122     if (LHS->equalsInt(0))
1123       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1124
1125   return 0;
1126 }
1127
1128 // isMaxValueMinusOne - return true if this is Max-1
1129 static bool isMaxValueMinusOne(const ConstantInt *C) {
1130   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
1131     // Calculate -1 casted to the right type...
1132     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
1133     uint64_t Val = ~0ULL;                // All ones
1134     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
1135     return CU->getValue() == Val-1;
1136   }
1137
1138   const ConstantSInt *CS = cast<ConstantSInt>(C);
1139
1140   // Calculate 0111111111..11111
1141   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
1142   int64_t Val = INT64_MAX;             // All ones
1143   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
1144   return CS->getValue() == Val-1;
1145 }
1146
1147 // isMinValuePlusOne - return true if this is Min+1
1148 static bool isMinValuePlusOne(const ConstantInt *C) {
1149   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
1150     return CU->getValue() == 1;
1151
1152   const ConstantSInt *CS = cast<ConstantSInt>(C);
1153
1154   // Calculate 1111111111000000000000
1155   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
1156   int64_t Val = -1;                    // All ones
1157   Val <<= TypeBits-1;                  // Shift over to the right spot
1158   return CS->getValue() == Val+1;
1159 }
1160
1161 // isOneBitSet - Return true if there is exactly one bit set in the specified
1162 // constant.
1163 static bool isOneBitSet(const ConstantInt *CI) {
1164   uint64_t V = CI->getRawValue();
1165   return V && (V & (V-1)) == 0;
1166 }
1167
1168 #if 0   // Currently unused
1169 // isLowOnes - Return true if the constant is of the form 0+1+.
1170 static bool isLowOnes(const ConstantInt *CI) {
1171   uint64_t V = CI->getRawValue();
1172
1173   // There won't be bits set in parts that the type doesn't contain.
1174   V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
1175
1176   uint64_t U = V+1;  // If it is low ones, this should be a power of two.
1177   return U && V && (U & V) == 0;
1178 }
1179 #endif
1180
1181 // isHighOnes - Return true if the constant is of the form 1+0+.
1182 // This is the same as lowones(~X).
1183 static bool isHighOnes(const ConstantInt *CI) {
1184   uint64_t V = ~CI->getRawValue();
1185
1186   // There won't be bits set in parts that the type doesn't contain.
1187   V &= ConstantInt::getAllOnesValue(CI->getType())->getRawValue();
1188
1189   uint64_t U = V+1;  // If it is low ones, this should be a power of two.
1190   return U && V && (U & V) == 0;
1191 }
1192
1193
1194 /// getSetCondCode - Encode a setcc opcode into a three bit mask.  These bits
1195 /// are carefully arranged to allow folding of expressions such as:
1196 ///
1197 ///      (A < B) | (A > B) --> (A != B)
1198 ///
1199 /// Bit value '4' represents that the comparison is true if A > B, bit value '2'
1200 /// represents that the comparison is true if A == B, and bit value '1' is true
1201 /// if A < B.
1202 ///
1203 static unsigned getSetCondCode(const SetCondInst *SCI) {
1204   switch (SCI->getOpcode()) {
1205     // False -> 0
1206   case Instruction::SetGT: return 1;
1207   case Instruction::SetEQ: return 2;
1208   case Instruction::SetGE: return 3;
1209   case Instruction::SetLT: return 4;
1210   case Instruction::SetNE: return 5;
1211   case Instruction::SetLE: return 6;
1212     // True -> 7
1213   default:
1214     assert(0 && "Invalid SetCC opcode!");
1215     return 0;
1216   }
1217 }
1218
1219 /// getSetCCValue - This is the complement of getSetCondCode, which turns an
1220 /// opcode and two operands into either a constant true or false, or a brand new
1221 /// SetCC instruction.
1222 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
1223   switch (Opcode) {
1224   case 0: return ConstantBool::False;
1225   case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
1226   case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
1227   case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
1228   case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
1229   case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
1230   case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
1231   case 7: return ConstantBool::True;
1232   default: assert(0 && "Illegal SetCCCode!"); return 0;
1233   }
1234 }
1235
1236 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1237 struct FoldSetCCLogical {
1238   InstCombiner &IC;
1239   Value *LHS, *RHS;
1240   FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
1241     : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
1242   bool shouldApply(Value *V) const {
1243     if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
1244       return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
1245               SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
1246     return false;
1247   }
1248   Instruction *apply(BinaryOperator &Log) const {
1249     SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
1250     if (SCI->getOperand(0) != LHS) {
1251       assert(SCI->getOperand(1) == LHS);
1252       SCI->swapOperands();  // Swap the LHS and RHS of the SetCC
1253     }
1254
1255     unsigned LHSCode = getSetCondCode(SCI);
1256     unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
1257     unsigned Code;
1258     switch (Log.getOpcode()) {
1259     case Instruction::And: Code = LHSCode & RHSCode; break;
1260     case Instruction::Or:  Code = LHSCode | RHSCode; break;
1261     case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
1262     default: assert(0 && "Illegal logical opcode!"); return 0;
1263     }
1264
1265     Value *RV = getSetCCValue(Code, LHS, RHS);
1266     if (Instruction *I = dyn_cast<Instruction>(RV))
1267       return I;
1268     // Otherwise, it's a constant boolean value...
1269     return IC.ReplaceInstUsesWith(Log, RV);
1270   }
1271 };
1272
1273
1274 /// MaskedValueIsZero - Return true if 'V & Mask' is known to be zero.  We use
1275 /// this predicate to simplify operations downstream.  V and Mask are known to
1276 /// be the same type.
1277 static bool MaskedValueIsZero(Value *V, ConstantIntegral *Mask) {
1278   if (isa<UndefValue>(V) || Mask->isNullValue())
1279     return true;
1280   if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(V))
1281     return ConstantExpr::getAnd(CI, Mask)->isNullValue();
1282
1283   if (Instruction *I = dyn_cast<Instruction>(V)) {
1284     switch (I->getOpcode()) {
1285     case Instruction::And:
1286       // (X & C1) & C2 == 0   iff   C1 & C2 == 0.
1287       if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(I->getOperand(1)))
1288         if (ConstantExpr::getAnd(CI, Mask)->isNullValue())
1289           return true;
1290       break;
1291     case Instruction::Cast: {
1292       const Type *SrcTy = I->getOperand(0)->getType();
1293       if (SrcTy->isIntegral()) {
1294         // (cast <ty> X to int) & C2 == 0  iff <ty> could not have contained C2.
1295         if (SrcTy->isUnsigned() &&                      // Only handle zero ext.
1296             ConstantExpr::getCast(Mask, SrcTy)->isNullValue())
1297           return true;
1298
1299         // If this is a noop cast, recurse.
1300         if (SrcTy != Type::BoolTy)
1301           if ((SrcTy->isSigned() && SrcTy->getUnsignedVersion() ==I->getType()) ||
1302               SrcTy->getSignedVersion() == I->getType()) {
1303             Constant *NewMask =
1304               ConstantExpr::getCast(Mask, I->getOperand(0)->getType());
1305             return MaskedValueIsZero(I->getOperand(0),
1306                                      cast<ConstantIntegral>(NewMask));
1307           }
1308       }
1309       break;
1310     }
1311     case Instruction::Shl:
1312       // (shl X, C1) & C2 == 0   iff  (-1 << C1) & C2 == 0
1313       if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1))) {
1314         Constant *C1 = ConstantIntegral::getAllOnesValue(I->getType());
1315         C1 = ConstantExpr::getShl(C1, SA);
1316         C1 = ConstantExpr::getAnd(C1, Mask);
1317         if (C1->isNullValue())
1318           return true;
1319       }
1320       break;
1321     case Instruction::Shr:
1322       // (ushr X, C1) & C2 == 0   iff  (-1 >> C1) & C2 == 0
1323       if (ConstantUInt *SA = dyn_cast<ConstantUInt>(I->getOperand(1)))
1324         if (I->getType()->isUnsigned()) {
1325           Constant *C1 = ConstantIntegral::getAllOnesValue(I->getType());
1326           C1 = ConstantExpr::getShr(C1, SA);
1327           C1 = ConstantExpr::getAnd(C1, Mask);
1328           if (C1->isNullValue())
1329             return true;
1330         }
1331       break;
1332     }
1333   }
1334
1335   return false;
1336 }
1337
1338 // OptAndOp - This handles expressions of the form ((val OP C1) & C2).  Where
1339 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.  Op is
1340 // guaranteed to be either a shift instruction or a binary operator.
1341 Instruction *InstCombiner::OptAndOp(Instruction *Op,
1342                                     ConstantIntegral *OpRHS,
1343                                     ConstantIntegral *AndRHS,
1344                                     BinaryOperator &TheAnd) {
1345   Value *X = Op->getOperand(0);
1346   Constant *Together = 0;
1347   if (!isa<ShiftInst>(Op))
1348     Together = ConstantExpr::getAnd(AndRHS, OpRHS);
1349
1350   switch (Op->getOpcode()) {
1351   case Instruction::Xor:
1352     if (Op->hasOneUse()) {
1353       // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1354       std::string OpName = Op->getName(); Op->setName("");
1355       Instruction *And = BinaryOperator::createAnd(X, AndRHS, OpName);
1356       InsertNewInstBefore(And, TheAnd);
1357       return BinaryOperator::createXor(And, Together);
1358     }
1359     break;
1360   case Instruction::Or:
1361     if (Together == AndRHS) // (X | C) & C --> C
1362       return ReplaceInstUsesWith(TheAnd, AndRHS);
1363
1364     if (Op->hasOneUse() && Together != OpRHS) {
1365       // (X | C1) & C2 --> (X | (C1&C2)) & C2
1366       std::string Op0Name = Op->getName(); Op->setName("");
1367       Instruction *Or = BinaryOperator::createOr(X, Together, Op0Name);
1368       InsertNewInstBefore(Or, TheAnd);
1369       return BinaryOperator::createAnd(Or, AndRHS);
1370     }
1371     break;
1372   case Instruction::Add:
1373     if (Op->hasOneUse()) {
1374       // Adding a one to a single bit bit-field should be turned into an XOR
1375       // of the bit.  First thing to check is to see if this AND is with a
1376       // single bit constant.
1377       uint64_t AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
1378
1379       // Clear bits that are not part of the constant.
1380       AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1;
1381
1382       // If there is only one bit set...
1383       if (isOneBitSet(cast<ConstantInt>(AndRHS))) {
1384         // Ok, at this point, we know that we are masking the result of the
1385         // ADD down to exactly one bit.  If the constant we are adding has
1386         // no bits set below this bit, then we can eliminate the ADD.
1387         uint64_t AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
1388
1389         // Check to see if any bits below the one bit set in AndRHSV are set.
1390         if ((AddRHS & (AndRHSV-1)) == 0) {
1391           // If not, the only thing that can effect the output of the AND is
1392           // the bit specified by AndRHSV.  If that bit is set, the effect of
1393           // the XOR is to toggle the bit.  If it is clear, then the ADD has
1394           // no effect.
1395           if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
1396             TheAnd.setOperand(0, X);
1397             return &TheAnd;
1398           } else {
1399             std::string Name = Op->getName(); Op->setName("");
1400             // Pull the XOR out of the AND.
1401             Instruction *NewAnd = BinaryOperator::createAnd(X, AndRHS, Name);
1402             InsertNewInstBefore(NewAnd, TheAnd);
1403             return BinaryOperator::createXor(NewAnd, AndRHS);
1404           }
1405         }
1406       }
1407     }
1408     break;
1409
1410   case Instruction::Shl: {
1411     // We know that the AND will not produce any of the bits shifted in, so if
1412     // the anded constant includes them, clear them now!
1413     //
1414     Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1415     Constant *ShlMask = ConstantExpr::getShl(AllOne, OpRHS);
1416     Constant *CI = ConstantExpr::getAnd(AndRHS, ShlMask);
1417
1418     if (CI == ShlMask) {   // Masking out bits that the shift already masks
1419       return ReplaceInstUsesWith(TheAnd, Op);   // No need for the and.
1420     } else if (CI != AndRHS) {                  // Reducing bits set in and.
1421       TheAnd.setOperand(1, CI);
1422       return &TheAnd;
1423     }
1424     break;
1425   }
1426   case Instruction::Shr:
1427     // We know that the AND will not produce any of the bits shifted in, so if
1428     // the anded constant includes them, clear them now!  This only applies to
1429     // unsigned shifts, because a signed shr may bring in set bits!
1430     //
1431     if (AndRHS->getType()->isUnsigned()) {
1432       Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1433       Constant *ShrMask = ConstantExpr::getShr(AllOne, OpRHS);
1434       Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
1435
1436       if (CI == ShrMask) {   // Masking out bits that the shift already masks.
1437         return ReplaceInstUsesWith(TheAnd, Op);
1438       } else if (CI != AndRHS) {
1439         TheAnd.setOperand(1, CI);  // Reduce bits set in and cst.
1440         return &TheAnd;
1441       }
1442     } else {   // Signed shr.
1443       // See if this is shifting in some sign extension, then masking it out
1444       // with an and.
1445       if (Op->hasOneUse()) {
1446         Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1447         Constant *ShrMask = ConstantExpr::getUShr(AllOne, OpRHS);
1448         Constant *CI = ConstantExpr::getAnd(AndRHS, ShrMask);
1449         if (CI == AndRHS) {          // Masking out bits shifted in.
1450           // Make the argument unsigned.
1451           Value *ShVal = Op->getOperand(0);
1452           ShVal = InsertCastBefore(ShVal,
1453                                    ShVal->getType()->getUnsignedVersion(),
1454                                    TheAnd);
1455           ShVal = InsertNewInstBefore(new ShiftInst(Instruction::Shr, ShVal,
1456                                                     OpRHS, Op->getName()),
1457                                       TheAnd);
1458           Value *AndRHS2 = ConstantExpr::getCast(AndRHS, ShVal->getType());
1459           ShVal = InsertNewInstBefore(BinaryOperator::createAnd(ShVal, AndRHS2,
1460                                                              TheAnd.getName()),
1461                                       TheAnd);
1462           return new CastInst(ShVal, Op->getType());
1463         }
1464       }
1465     }
1466     break;
1467   }
1468   return 0;
1469 }
1470
1471
1472 /// InsertRangeTest - Emit a computation of: (V >= Lo && V < Hi) if Inside is
1473 /// true, otherwise (V < Lo || V >= Hi).  In pratice, we emit the more efficient
1474 /// (V-Lo) <u Hi-Lo.  This method expects that Lo <= Hi.  IB is the location to
1475 /// insert new instructions.
1476 Instruction *InstCombiner::InsertRangeTest(Value *V, Constant *Lo, Constant *Hi,
1477                                            bool Inside, Instruction &IB) {
1478   assert(cast<ConstantBool>(ConstantExpr::getSetLE(Lo, Hi))->getValue() &&
1479          "Lo is not <= Hi in range emission code!");
1480   if (Inside) {
1481     if (Lo == Hi)  // Trivially false.
1482       return new SetCondInst(Instruction::SetNE, V, V);
1483     if (cast<ConstantIntegral>(Lo)->isMinValue())
1484       return new SetCondInst(Instruction::SetLT, V, Hi);
1485
1486     Constant *AddCST = ConstantExpr::getNeg(Lo);
1487     Instruction *Add = BinaryOperator::createAdd(V, AddCST,V->getName()+".off");
1488     InsertNewInstBefore(Add, IB);
1489     // Convert to unsigned for the comparison.
1490     const Type *UnsType = Add->getType()->getUnsignedVersion();
1491     Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
1492     AddCST = ConstantExpr::getAdd(AddCST, Hi);
1493     AddCST = ConstantExpr::getCast(AddCST, UnsType);
1494     return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
1495   }
1496
1497   if (Lo == Hi)  // Trivially true.
1498     return new SetCondInst(Instruction::SetEQ, V, V);
1499
1500   Hi = SubOne(cast<ConstantInt>(Hi));
1501   if (cast<ConstantIntegral>(Lo)->isMinValue()) // V < 0 || V >= Hi ->'V > Hi-1'
1502     return new SetCondInst(Instruction::SetGT, V, Hi);
1503
1504   // Emit X-Lo > Hi-Lo-1
1505   Constant *AddCST = ConstantExpr::getNeg(Lo);
1506   Instruction *Add = BinaryOperator::createAdd(V, AddCST, V->getName()+".off");
1507   InsertNewInstBefore(Add, IB);
1508   // Convert to unsigned for the comparison.
1509   const Type *UnsType = Add->getType()->getUnsignedVersion();
1510   Value *OffsetVal = InsertCastBefore(Add, UnsType, IB);
1511   AddCST = ConstantExpr::getAdd(AddCST, Hi);
1512   AddCST = ConstantExpr::getCast(AddCST, UnsType);
1513   return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
1514 }
1515
1516
1517 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
1518   bool Changed = SimplifyCommutative(I);
1519   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1520
1521   if (isa<UndefValue>(Op1))                         // X & undef -> 0
1522     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1523
1524   // and X, X = X
1525   if (Op0 == Op1)
1526     return ReplaceInstUsesWith(I, Op1);
1527
1528   // and X, -1 == X
1529   if (ConstantIntegral *AndRHS = dyn_cast<ConstantIntegral>(Op1)) {
1530     if (AndRHS->isAllOnesValue())              // and X, -1 == X
1531       return ReplaceInstUsesWith(I, Op0);
1532
1533     if (MaskedValueIsZero(Op0, AndRHS))        // LHS & RHS == 0
1534       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1535
1536     // If the mask is not masking out any bits, there is no reason to do the
1537     // and in the first place.
1538     if (MaskedValueIsZero(Op0,
1539                           cast<ConstantIntegral>(ConstantExpr::getNot(AndRHS))))
1540         return ReplaceInstUsesWith(I, Op0);
1541
1542     // Optimize a variety of ((val OP C1) & C2) combinations...
1543     if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
1544       Instruction *Op0I = cast<Instruction>(Op0);
1545       Value *Op0LHS = Op0I->getOperand(0);
1546       Value *Op0RHS = Op0I->getOperand(1);
1547       switch (Op0I->getOpcode()) {
1548       case Instruction::Xor:
1549       case Instruction::Or:
1550         // (X ^ V) & C2 --> (X & C2) iff (V & C2) == 0
1551         // (X | V) & C2 --> (X & C2) iff (V & C2) == 0
1552         if (MaskedValueIsZero(Op0LHS, AndRHS))
1553           return BinaryOperator::createAnd(Op0RHS, AndRHS);
1554         if (MaskedValueIsZero(Op0RHS, AndRHS))
1555           return BinaryOperator::createAnd(Op0LHS, AndRHS);
1556         break;
1557       case Instruction::And:
1558         // (X & V) & C2 --> 0 iff (V & C2) == 0
1559         if (MaskedValueIsZero(Op0LHS, AndRHS) ||
1560             MaskedValueIsZero(Op0RHS, AndRHS))
1561           return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1562         break;
1563       }
1564
1565       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1566         if (Instruction *Res = OptAndOp(Op0I, Op0CI, AndRHS, I))
1567           return Res;
1568     } else if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
1569       const Type *SrcTy = CI->getOperand(0)->getType();
1570
1571       // If this is an integer sign or zero extension instruction.
1572       if (SrcTy->isIntegral() &&
1573           SrcTy->getPrimitiveSize() < CI->getType()->getPrimitiveSize()) {
1574
1575         if (SrcTy->isUnsigned()) {
1576           // See if this and is clearing out bits that are known to be zero
1577           // anyway (due to the zero extension).
1578           Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
1579           Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
1580           Constant *Result = ConstantExpr::getAnd(Mask, AndRHS);
1581           if (Result == Mask)  // The "and" isn't doing anything, remove it.
1582             return ReplaceInstUsesWith(I, CI);
1583           if (Result != AndRHS) { // Reduce the and RHS constant.
1584             I.setOperand(1, Result);
1585             return &I;
1586           }
1587
1588         } else {
1589           if (CI->hasOneUse() && SrcTy->isInteger()) {
1590             // We can only do this if all of the sign bits brought in are masked
1591             // out.  Compute this by first getting 0000011111, then inverting
1592             // it.
1593             Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy);
1594             Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());
1595             Mask = ConstantExpr::getNot(Mask);    // 1's in the new bits.
1596             if (ConstantExpr::getAnd(Mask, AndRHS)->isNullValue()) {
1597               // If the and is clearing all of the sign bits, change this to a
1598               // zero extension cast.  To do this, cast the cast input to
1599               // unsigned, then to the requested size.
1600               Value *CastOp = CI->getOperand(0);
1601               Instruction *NC =
1602                 new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
1603                              CI->getName()+".uns");
1604               NC = InsertNewInstBefore(NC, I);
1605               // Finally, insert a replacement for CI.
1606               NC = new CastInst(NC, CI->getType(), CI->getName());
1607               CI->setName("");
1608               NC = InsertNewInstBefore(NC, I);
1609               WorkList.push_back(CI);  // Delete CI later.
1610               I.setOperand(0, NC);
1611               return &I;               // The AND operand was modified.
1612             }
1613           }
1614         }
1615       }
1616     }
1617
1618     // Try to fold constant and into select arguments.
1619     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1620       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1621         return R;
1622     if (isa<PHINode>(Op0))
1623       if (Instruction *NV = FoldOpIntoPhi(I))
1624         return NV;
1625   }
1626
1627   Value *Op0NotVal = dyn_castNotVal(Op0);
1628   Value *Op1NotVal = dyn_castNotVal(Op1);
1629
1630   if (Op0NotVal == Op1 || Op1NotVal == Op0)  // A & ~A  == ~A & A == 0
1631     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1632
1633   // (~A & ~B) == (~(A | B)) - De Morgan's Law
1634   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1635     Instruction *Or = BinaryOperator::createOr(Op0NotVal, Op1NotVal,
1636                                                I.getName()+".demorgan");
1637     InsertNewInstBefore(Or, I);
1638     return BinaryOperator::createNot(Or);
1639   }
1640
1641   if (SetCondInst *RHS = dyn_cast<SetCondInst>(Op1)) {
1642     // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1643     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1644       return R;
1645
1646     Value *LHSVal, *RHSVal;
1647     ConstantInt *LHSCst, *RHSCst;
1648     Instruction::BinaryOps LHSCC, RHSCC;
1649     if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
1650       if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
1651         if (LHSVal == RHSVal &&    // Found (X setcc C1) & (X setcc C2)
1652             // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
1653             LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
1654             RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
1655           // Ensure that the larger constant is on the RHS.
1656           Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
1657           SetCondInst *LHS = cast<SetCondInst>(Op0);
1658           if (cast<ConstantBool>(Cmp)->getValue()) {
1659             std::swap(LHS, RHS);
1660             std::swap(LHSCst, RHSCst);
1661             std::swap(LHSCC, RHSCC);
1662           }
1663
1664           // At this point, we know we have have two setcc instructions
1665           // comparing a value against two constants and and'ing the result
1666           // together.  Because of the above check, we know that we only have
1667           // SetEQ, SetNE, SetLT, and SetGT here.  We also know (from the
1668           // FoldSetCCLogical check above), that the two constants are not
1669           // equal.
1670           assert(LHSCst != RHSCst && "Compares not folded above?");
1671
1672           switch (LHSCC) {
1673           default: assert(0 && "Unknown integer condition code!");
1674           case Instruction::SetEQ:
1675             switch (RHSCC) {
1676             default: assert(0 && "Unknown integer condition code!");
1677             case Instruction::SetEQ:  // (X == 13 & X == 15) -> false
1678             case Instruction::SetGT:  // (X == 13 & X > 15)  -> false
1679               return ReplaceInstUsesWith(I, ConstantBool::False);
1680             case Instruction::SetNE:  // (X == 13 & X != 15) -> X == 13
1681             case Instruction::SetLT:  // (X == 13 & X < 15)  -> X == 13
1682               return ReplaceInstUsesWith(I, LHS);
1683             }
1684           case Instruction::SetNE:
1685             switch (RHSCC) {
1686             default: assert(0 && "Unknown integer condition code!");
1687             case Instruction::SetLT:
1688               if (LHSCst == SubOne(RHSCst)) // (X != 13 & X < 14) -> X < 13
1689                 return new SetCondInst(Instruction::SetLT, LHSVal, LHSCst);
1690               break;                        // (X != 13 & X < 15) -> no change
1691             case Instruction::SetEQ:        // (X != 13 & X == 15) -> X == 15
1692             case Instruction::SetGT:        // (X != 13 & X > 15)  -> X > 15
1693               return ReplaceInstUsesWith(I, RHS);
1694             case Instruction::SetNE:
1695               if (LHSCst == SubOne(RHSCst)) {// (X != 13 & X != 14) -> X-13 >u 1
1696                 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
1697                 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
1698                                                       LHSVal->getName()+".off");
1699                 InsertNewInstBefore(Add, I);
1700                 const Type *UnsType = Add->getType()->getUnsignedVersion();
1701                 Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
1702                 AddCST = ConstantExpr::getSub(RHSCst, LHSCst);
1703                 AddCST = ConstantExpr::getCast(AddCST, UnsType);
1704                 return new SetCondInst(Instruction::SetGT, OffsetVal, AddCST);
1705               }
1706               break;                        // (X != 13 & X != 15) -> no change
1707             }
1708             break;
1709           case Instruction::SetLT:
1710             switch (RHSCC) {
1711             default: assert(0 && "Unknown integer condition code!");
1712             case Instruction::SetEQ:  // (X < 13 & X == 15) -> false
1713             case Instruction::SetGT:  // (X < 13 & X > 15)  -> false
1714               return ReplaceInstUsesWith(I, ConstantBool::False);
1715             case Instruction::SetNE:  // (X < 13 & X != 15) -> X < 13
1716             case Instruction::SetLT:  // (X < 13 & X < 15) -> X < 13
1717               return ReplaceInstUsesWith(I, LHS);
1718             }
1719           case Instruction::SetGT:
1720             switch (RHSCC) {
1721             default: assert(0 && "Unknown integer condition code!");
1722             case Instruction::SetEQ:  // (X > 13 & X == 15) -> X > 13
1723               return ReplaceInstUsesWith(I, LHS);
1724             case Instruction::SetGT:  // (X > 13 & X > 15)  -> X > 15
1725               return ReplaceInstUsesWith(I, RHS);
1726             case Instruction::SetNE:
1727               if (RHSCst == AddOne(LHSCst)) // (X > 13 & X != 14) -> X > 14
1728                 return new SetCondInst(Instruction::SetGT, LHSVal, RHSCst);
1729               break;                        // (X > 13 & X != 15) -> no change
1730             case Instruction::SetLT:   // (X > 13 & X < 15) -> (X-14) <u 1
1731               return InsertRangeTest(LHSVal, AddOne(LHSCst), RHSCst, true, I);
1732             }
1733           }
1734         }
1735   }
1736
1737   return Changed ? &I : 0;
1738 }
1739
1740 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
1741   bool Changed = SimplifyCommutative(I);
1742   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1743
1744   if (isa<UndefValue>(Op1))
1745     return ReplaceInstUsesWith(I,                         // X | undef -> -1
1746                                ConstantIntegral::getAllOnesValue(I.getType()));
1747
1748   // or X, X = X   or X, 0 == X
1749   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1750     return ReplaceInstUsesWith(I, Op0);
1751
1752   // or X, -1 == -1
1753   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1754     // If X is known to only contain bits that already exist in RHS, just
1755     // replace this instruction with RHS directly.
1756     if (MaskedValueIsZero(Op0,
1757                           cast<ConstantIntegral>(ConstantExpr::getNot(RHS))))
1758       return ReplaceInstUsesWith(I, RHS);
1759
1760     ConstantInt *C1; Value *X;
1761     // (X & C1) | C2 --> (X | C2) & (C1|C2)
1762     if (match(Op0, m_And(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
1763       std::string Op0Name = Op0->getName(); Op0->setName("");
1764       Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
1765       InsertNewInstBefore(Or, I);
1766       return BinaryOperator::createAnd(Or, ConstantExpr::getOr(RHS, C1));
1767     }
1768
1769     // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
1770     if (match(Op0, m_Xor(m_Value(X), m_ConstantInt(C1))) && isOnlyUse(Op0)) {
1771       std::string Op0Name = Op0->getName(); Op0->setName("");
1772       Instruction *Or = BinaryOperator::createOr(X, RHS, Op0Name);
1773       InsertNewInstBefore(Or, I);
1774       return BinaryOperator::createXor(Or,
1775                  ConstantExpr::getAnd(C1, ConstantExpr::getNot(RHS)));
1776     }
1777
1778     // Try to fold constant and into select arguments.
1779     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1780       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1781         return R;
1782     if (isa<PHINode>(Op0))
1783       if (Instruction *NV = FoldOpIntoPhi(I))
1784         return NV;
1785   }
1786
1787   // (A & C1)|(A & C2) == A & (C1|C2)
1788   Value *A, *B; ConstantInt *C1, *C2;
1789   if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
1790       match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) && A == B)
1791     return BinaryOperator::createAnd(A, ConstantExpr::getOr(C1, C2));
1792
1793   if (match(Op0, m_Not(m_Value(A)))) {   // ~A | Op1
1794     if (A == Op1)   // ~A | A == -1
1795       return ReplaceInstUsesWith(I,
1796                                 ConstantIntegral::getAllOnesValue(I.getType()));
1797   } else {
1798     A = 0;
1799   }
1800
1801   if (match(Op1, m_Not(m_Value(B)))) {   // Op0 | ~B
1802     if (Op0 == B)
1803       return ReplaceInstUsesWith(I,
1804                                 ConstantIntegral::getAllOnesValue(I.getType()));
1805
1806     // (~A | ~B) == (~(A & B)) - De Morgan's Law
1807     if (A && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1808       Value *And = InsertNewInstBefore(BinaryOperator::createAnd(A, B,
1809                                               I.getName()+".demorgan"), I);
1810       return BinaryOperator::createNot(And);
1811     }
1812   }
1813
1814   // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
1815   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1))) {
1816     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1817       return R;
1818
1819     Value *LHSVal, *RHSVal;
1820     ConstantInt *LHSCst, *RHSCst;
1821     Instruction::BinaryOps LHSCC, RHSCC;
1822     if (match(Op0, m_SetCond(LHSCC, m_Value(LHSVal), m_ConstantInt(LHSCst))))
1823       if (match(RHS, m_SetCond(RHSCC, m_Value(RHSVal), m_ConstantInt(RHSCst))))
1824         if (LHSVal == RHSVal &&    // Found (X setcc C1) | (X setcc C2)
1825             // Set[GL]E X, CST is folded to Set[GL]T elsewhere.
1826             LHSCC != Instruction::SetGE && LHSCC != Instruction::SetLE &&
1827             RHSCC != Instruction::SetGE && RHSCC != Instruction::SetLE) {
1828           // Ensure that the larger constant is on the RHS.
1829           Constant *Cmp = ConstantExpr::getSetGT(LHSCst, RHSCst);
1830           SetCondInst *LHS = cast<SetCondInst>(Op0);
1831           if (cast<ConstantBool>(Cmp)->getValue()) {
1832             std::swap(LHS, RHS);
1833             std::swap(LHSCst, RHSCst);
1834             std::swap(LHSCC, RHSCC);
1835           }
1836
1837           // At this point, we know we have have two setcc instructions
1838           // comparing a value against two constants and or'ing the result
1839           // together.  Because of the above check, we know that we only have
1840           // SetEQ, SetNE, SetLT, and SetGT here.  We also know (from the
1841           // FoldSetCCLogical check above), that the two constants are not
1842           // equal.
1843           assert(LHSCst != RHSCst && "Compares not folded above?");
1844
1845           switch (LHSCC) {
1846           default: assert(0 && "Unknown integer condition code!");
1847           case Instruction::SetEQ:
1848             switch (RHSCC) {
1849             default: assert(0 && "Unknown integer condition code!");
1850             case Instruction::SetEQ:
1851               if (LHSCst == SubOne(RHSCst)) {// (X == 13 | X == 14) -> X-13 <u 2
1852                 Constant *AddCST = ConstantExpr::getNeg(LHSCst);
1853                 Instruction *Add = BinaryOperator::createAdd(LHSVal, AddCST,
1854                                                       LHSVal->getName()+".off");
1855                 InsertNewInstBefore(Add, I);
1856                 const Type *UnsType = Add->getType()->getUnsignedVersion();
1857                 Value *OffsetVal = InsertCastBefore(Add, UnsType, I);
1858                 AddCST = ConstantExpr::getSub(AddOne(RHSCst), LHSCst);
1859                 AddCST = ConstantExpr::getCast(AddCST, UnsType);
1860                 return new SetCondInst(Instruction::SetLT, OffsetVal, AddCST);
1861               }
1862               break;                  // (X == 13 | X == 15) -> no change
1863
1864             case Instruction::SetGT:
1865               if (LHSCst == SubOne(RHSCst)) // (X == 13 | X > 14) -> X > 13
1866                 return new SetCondInst(Instruction::SetGT, LHSVal, LHSCst);
1867               break;                        // (X == 13 | X > 15) -> no change
1868             case Instruction::SetNE:  // (X == 13 | X != 15) -> X != 15
1869             case Instruction::SetLT:  // (X == 13 | X < 15)  -> X < 15
1870               return ReplaceInstUsesWith(I, RHS);
1871             }
1872             break;
1873           case Instruction::SetNE:
1874             switch (RHSCC) {
1875             default: assert(0 && "Unknown integer condition code!");
1876             case Instruction::SetLT:        // (X != 13 | X < 15) -> X < 15
1877               return ReplaceInstUsesWith(I, RHS);
1878             case Instruction::SetEQ:        // (X != 13 | X == 15) -> X != 13
1879             case Instruction::SetGT:        // (X != 13 | X > 15)  -> X != 13
1880               return ReplaceInstUsesWith(I, LHS);
1881             case Instruction::SetNE:        // (X != 13 | X != 15) -> true
1882               return ReplaceInstUsesWith(I, ConstantBool::True);
1883             }
1884             break;
1885           case Instruction::SetLT:
1886             switch (RHSCC) {
1887             default: assert(0 && "Unknown integer condition code!");
1888             case Instruction::SetEQ:  // (X < 13 | X == 14) -> no change
1889               break;
1890             case Instruction::SetGT:  // (X < 13 | X > 15)  -> (X-13) > 2
1891               return InsertRangeTest(LHSVal, LHSCst, AddOne(RHSCst), false, I);
1892             case Instruction::SetNE:  // (X < 13 | X != 15) -> X != 15
1893             case Instruction::SetLT:  // (X < 13 | X < 15) -> X < 15
1894               return ReplaceInstUsesWith(I, RHS);
1895             }
1896             break;
1897           case Instruction::SetGT:
1898             switch (RHSCC) {
1899             default: assert(0 && "Unknown integer condition code!");
1900             case Instruction::SetEQ:  // (X > 13 | X == 15) -> X > 13
1901             case Instruction::SetGT:  // (X > 13 | X > 15)  -> X > 13
1902               return ReplaceInstUsesWith(I, LHS);
1903             case Instruction::SetNE:  // (X > 13 | X != 15)  -> true
1904             case Instruction::SetLT:  // (X > 13 | X < 15) -> true
1905               return ReplaceInstUsesWith(I, ConstantBool::True);
1906             }
1907           }
1908         }
1909   }
1910   return Changed ? &I : 0;
1911 }
1912
1913 // XorSelf - Implements: X ^ X --> 0
1914 struct XorSelf {
1915   Value *RHS;
1916   XorSelf(Value *rhs) : RHS(rhs) {}
1917   bool shouldApply(Value *LHS) const { return LHS == RHS; }
1918   Instruction *apply(BinaryOperator &Xor) const {
1919     return &Xor;
1920   }
1921 };
1922
1923
1924 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
1925   bool Changed = SimplifyCommutative(I);
1926   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1927
1928   if (isa<UndefValue>(Op1))
1929     return ReplaceInstUsesWith(I, Op1);  // X ^ undef -> undef
1930
1931   // xor X, X = 0, even if X is nested in a sequence of Xor's.
1932   if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) {
1933     assert(Result == &I && "AssociativeOpt didn't work?");
1934     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1935   }
1936
1937   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1938     // xor X, 0 == X
1939     if (RHS->isNullValue())
1940       return ReplaceInstUsesWith(I, Op0);
1941
1942     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1943       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
1944       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
1945         if (RHS == ConstantBool::True && SCI->hasOneUse())
1946           return new SetCondInst(SCI->getInverseCondition(),
1947                                  SCI->getOperand(0), SCI->getOperand(1));
1948
1949       // ~(c-X) == X-c-1 == X+(-c-1)
1950       if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
1951         if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
1952           Constant *NegOp0I0C = ConstantExpr::getNeg(Op0I0C);
1953           Constant *ConstantRHS = ConstantExpr::getSub(NegOp0I0C,
1954                                               ConstantInt::get(I.getType(), 1));
1955           return BinaryOperator::createAdd(Op0I->getOperand(1), ConstantRHS);
1956         }
1957
1958       // ~(~X & Y) --> (X | ~Y)
1959       if (Op0I->getOpcode() == Instruction::And && RHS->isAllOnesValue()) {
1960         if (dyn_castNotVal(Op0I->getOperand(1))) Op0I->swapOperands();
1961         if (Value *Op0NotVal = dyn_castNotVal(Op0I->getOperand(0))) {
1962           Instruction *NotY =
1963             BinaryOperator::createNot(Op0I->getOperand(1),
1964                                       Op0I->getOperand(1)->getName()+".not");
1965           InsertNewInstBefore(NotY, I);
1966           return BinaryOperator::createOr(Op0NotVal, NotY);
1967         }
1968       }
1969
1970       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1971         switch (Op0I->getOpcode()) {
1972         case Instruction::Add:
1973           // ~(X-c) --> (-c-1)-X
1974           if (RHS->isAllOnesValue()) {
1975             Constant *NegOp0CI = ConstantExpr::getNeg(Op0CI);
1976             return BinaryOperator::createSub(
1977                            ConstantExpr::getSub(NegOp0CI,
1978                                              ConstantInt::get(I.getType(), 1)),
1979                                           Op0I->getOperand(0));
1980           }
1981           break;
1982         case Instruction::And:
1983           // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
1984           if (ConstantExpr::getAnd(RHS, Op0CI)->isNullValue())
1985             return BinaryOperator::createOr(Op0, RHS);
1986           break;
1987         case Instruction::Or:
1988           // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
1989           if (ConstantExpr::getAnd(RHS, Op0CI) == RHS)
1990             return BinaryOperator::createAnd(Op0, ConstantExpr::getNot(RHS));
1991           break;
1992         default: break;
1993         }
1994     }
1995
1996     // Try to fold constant and into select arguments.
1997     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1998       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
1999         return R;
2000     if (isa<PHINode>(Op0))
2001       if (Instruction *NV = FoldOpIntoPhi(I))
2002         return NV;
2003   }
2004
2005   if (Value *X = dyn_castNotVal(Op0))   // ~A ^ A == -1
2006     if (X == Op1)
2007       return ReplaceInstUsesWith(I,
2008                                 ConstantIntegral::getAllOnesValue(I.getType()));
2009
2010   if (Value *X = dyn_castNotVal(Op1))   // A ^ ~A == -1
2011     if (X == Op0)
2012       return ReplaceInstUsesWith(I,
2013                                 ConstantIntegral::getAllOnesValue(I.getType()));
2014
2015   if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
2016     if (Op1I->getOpcode() == Instruction::Or) {
2017       if (Op1I->getOperand(0) == Op0) {              // B^(B|A) == (A|B)^B
2018         cast<BinaryOperator>(Op1I)->swapOperands();
2019         I.swapOperands();
2020         std::swap(Op0, Op1);
2021       } else if (Op1I->getOperand(1) == Op0) {       // B^(A|B) == (A|B)^B
2022         I.swapOperands();
2023         std::swap(Op0, Op1);
2024       }
2025     } else if (Op1I->getOpcode() == Instruction::Xor) {
2026       if (Op0 == Op1I->getOperand(0))                        // A^(A^B) == B
2027         return ReplaceInstUsesWith(I, Op1I->getOperand(1));
2028       else if (Op0 == Op1I->getOperand(1))                   // A^(B^A) == B
2029         return ReplaceInstUsesWith(I, Op1I->getOperand(0));
2030     }
2031
2032   if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
2033     if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) {
2034       if (Op0I->getOperand(0) == Op1)                // (B|A)^B == (A|B)^B
2035         cast<BinaryOperator>(Op0I)->swapOperands();
2036       if (Op0I->getOperand(1) == Op1) {              // (A|B)^B == A & ~B
2037         Value *NotB = InsertNewInstBefore(BinaryOperator::createNot(Op1,
2038                                                      Op1->getName()+".not"), I);
2039         return BinaryOperator::createAnd(Op0I->getOperand(0), NotB);
2040       }
2041     } else if (Op0I->getOpcode() == Instruction::Xor) {
2042       if (Op1 == Op0I->getOperand(0))                        // (A^B)^A == B
2043         return ReplaceInstUsesWith(I, Op0I->getOperand(1));
2044       else if (Op1 == Op0I->getOperand(1))                   // (B^A)^A == B
2045         return ReplaceInstUsesWith(I, Op0I->getOperand(0));
2046     }
2047
2048   // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1&C2 == 0
2049   Value *A, *B; ConstantInt *C1, *C2;
2050   if (match(Op0, m_And(m_Value(A), m_ConstantInt(C1))) &&
2051       match(Op1, m_And(m_Value(B), m_ConstantInt(C2))) &&
2052       ConstantExpr::getAnd(C1, C2)->isNullValue())
2053     return BinaryOperator::createOr(Op0, Op1);
2054
2055   // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
2056   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
2057     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
2058       return R;
2059
2060   return Changed ? &I : 0;
2061 }
2062
2063 /// MulWithOverflow - Compute Result = In1*In2, returning true if the result
2064 /// overflowed for this type.
2065 static bool MulWithOverflow(ConstantInt *&Result, ConstantInt *In1,
2066                             ConstantInt *In2) {
2067   Result = cast<ConstantInt>(ConstantExpr::getMul(In1, In2));
2068   return !In2->isNullValue() && ConstantExpr::getDiv(Result, In2) != In1;
2069 }
2070
2071 static bool isPositive(ConstantInt *C) {
2072   return cast<ConstantSInt>(C)->getValue() >= 0;
2073 }
2074
2075 /// AddWithOverflow - Compute Result = In1+In2, returning true if the result
2076 /// overflowed for this type.
2077 static bool AddWithOverflow(ConstantInt *&Result, ConstantInt *In1,
2078                             ConstantInt *In2) {
2079   Result = cast<ConstantInt>(ConstantExpr::getAdd(In1, In2));
2080
2081   if (In1->getType()->isUnsigned())
2082     return cast<ConstantUInt>(Result)->getValue() <
2083            cast<ConstantUInt>(In1)->getValue();
2084   if (isPositive(In1) != isPositive(In2))
2085     return false;
2086   if (isPositive(In1))
2087     return cast<ConstantSInt>(Result)->getValue() <
2088            cast<ConstantSInt>(In1)->getValue();
2089   return cast<ConstantSInt>(Result)->getValue() >
2090          cast<ConstantSInt>(In1)->getValue();
2091 }
2092
2093 /// EmitGEPOffset - Given a getelementptr instruction/constantexpr, emit the
2094 /// code necessary to compute the offset from the base pointer (without adding
2095 /// in the base pointer).  Return the result as a signed integer of intptr size.
2096 static Value *EmitGEPOffset(User *GEP, Instruction &I, InstCombiner &IC) {
2097   TargetData &TD = IC.getTargetData();
2098   gep_type_iterator GTI = gep_type_begin(GEP);
2099   const Type *UIntPtrTy = TD.getIntPtrType();
2100   const Type *SIntPtrTy = UIntPtrTy->getSignedVersion();
2101   Value *Result = Constant::getNullValue(SIntPtrTy);
2102
2103   // Build a mask for high order bits.
2104   uint64_t PtrSizeMask = ~0ULL;
2105   PtrSizeMask >>= 64-(TD.getPointerSize()*8);
2106
2107   for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
2108     Value *Op = GEP->getOperand(i);
2109     uint64_t Size = TD.getTypeSize(GTI.getIndexedType()) & PtrSizeMask;
2110     Constant *Scale = ConstantExpr::getCast(ConstantUInt::get(UIntPtrTy, Size),
2111                                             SIntPtrTy);
2112     if (Constant *OpC = dyn_cast<Constant>(Op)) {
2113       if (!OpC->isNullValue()) {
2114         OpC = ConstantExpr::getCast(OpC, SIntPtrTy);
2115         Scale = ConstantExpr::getMul(OpC, Scale);
2116         if (Constant *RC = dyn_cast<Constant>(Result))
2117           Result = ConstantExpr::getAdd(RC, Scale);
2118         else {
2119           // Emit an add instruction.
2120           Result = IC.InsertNewInstBefore(
2121              BinaryOperator::createAdd(Result, Scale,
2122                                        GEP->getName()+".offs"), I);
2123         }
2124       }
2125     } else {
2126       // Convert to correct type.
2127       Op = IC.InsertNewInstBefore(new CastInst(Op, SIntPtrTy,
2128                                                Op->getName()+".c"), I);
2129       if (Size != 1)
2130         // We'll let instcombine(mul) convert this to a shl if possible.
2131         Op = IC.InsertNewInstBefore(BinaryOperator::createMul(Op, Scale,
2132                                                     GEP->getName()+".idx"), I);
2133
2134       // Emit an add instruction.
2135       Result = IC.InsertNewInstBefore(BinaryOperator::createAdd(Op, Result,
2136                                                     GEP->getName()+".offs"), I);
2137     }
2138   }
2139   return Result;
2140 }
2141
2142 /// FoldGEPSetCC - Fold comparisons between a GEP instruction and something
2143 /// else.  At this point we know that the GEP is on the LHS of the comparison.
2144 Instruction *InstCombiner::FoldGEPSetCC(User *GEPLHS, Value *RHS,
2145                                         Instruction::BinaryOps Cond,
2146                                         Instruction &I) {
2147   assert(dyn_castGetElementPtr(GEPLHS) && "LHS is not a getelementptr!");
2148
2149   if (CastInst *CI = dyn_cast<CastInst>(RHS))
2150     if (isa<PointerType>(CI->getOperand(0)->getType()))
2151       RHS = CI->getOperand(0);
2152
2153   Value *PtrBase = GEPLHS->getOperand(0);
2154   if (PtrBase == RHS) {
2155     // As an optimization, we don't actually have to compute the actual value of
2156     // OFFSET if this is a seteq or setne comparison, just return whether each
2157     // index is zero or not.
2158     if (Cond == Instruction::SetEQ || Cond == Instruction::SetNE) {
2159       Instruction *InVal = 0;
2160       for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i) {
2161         bool EmitIt = true;
2162         if (Constant *C = dyn_cast<Constant>(GEPLHS->getOperand(i))) {
2163           if (isa<UndefValue>(C))  // undef index -> undef.
2164             return ReplaceInstUsesWith(I, UndefValue::get(I.getType()));
2165           if (C->isNullValue())
2166             EmitIt = false;
2167           else if (isa<ConstantInt>(C))
2168             return ReplaceInstUsesWith(I, // No comparison is needed here.
2169                                  ConstantBool::get(Cond == Instruction::SetNE));
2170         }
2171
2172         if (EmitIt) {
2173           Instruction *Comp =
2174             new SetCondInst(Cond, GEPLHS->getOperand(i),
2175                     Constant::getNullValue(GEPLHS->getOperand(i)->getType()));
2176           if (InVal == 0)
2177             InVal = Comp;
2178           else {
2179             InVal = InsertNewInstBefore(InVal, I);
2180             InsertNewInstBefore(Comp, I);
2181             if (Cond == Instruction::SetNE)   // True if any are unequal
2182               InVal = BinaryOperator::createOr(InVal, Comp);
2183             else                              // True if all are equal
2184               InVal = BinaryOperator::createAnd(InVal, Comp);
2185           }
2186         }
2187       }
2188
2189       if (InVal)
2190         return InVal;
2191       else
2192         ReplaceInstUsesWith(I, // No comparison is needed here, all indexes = 0
2193                             ConstantBool::get(Cond == Instruction::SetEQ));
2194     }
2195
2196     // Only lower this if the setcc is the only user of the GEP or if we expect
2197     // the result to fold to a constant!
2198     if (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) {
2199       // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
2200       Value *Offset = EmitGEPOffset(GEPLHS, I, *this);
2201       return new SetCondInst(Cond, Offset,
2202                              Constant::getNullValue(Offset->getType()));
2203     }
2204   } else if (User *GEPRHS = dyn_castGetElementPtr(RHS)) {
2205     if (PtrBase != GEPRHS->getOperand(0))
2206       return 0;
2207
2208     // If one of the GEPs has all zero indices, recurse.
2209     bool AllZeros = true;
2210     for (unsigned i = 1, e = GEPLHS->getNumOperands(); i != e; ++i)
2211       if (!isa<Constant>(GEPLHS->getOperand(i)) ||
2212           !cast<Constant>(GEPLHS->getOperand(i))->isNullValue()) {
2213         AllZeros = false;
2214         break;
2215       }
2216     if (AllZeros)
2217       return FoldGEPSetCC(GEPRHS, GEPLHS->getOperand(0),
2218                           SetCondInst::getSwappedCondition(Cond), I);
2219
2220     // If the other GEP has all zero indices, recurse.
2221     AllZeros = true;
2222     for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
2223       if (!isa<Constant>(GEPRHS->getOperand(i)) ||
2224           !cast<Constant>(GEPRHS->getOperand(i))->isNullValue()) {
2225         AllZeros = false;
2226         break;
2227       }
2228     if (AllZeros)
2229       return FoldGEPSetCC(GEPLHS, GEPRHS->getOperand(0), Cond, I);
2230
2231     if (GEPLHS->getNumOperands() == GEPRHS->getNumOperands()) {
2232       // If the GEPs only differ by one index, compare it.
2233       unsigned NumDifferences = 0;  // Keep track of # differences.
2234       unsigned DiffOperand = 0;     // The operand that differs.
2235       for (unsigned i = 1, e = GEPRHS->getNumOperands(); i != e; ++i)
2236         if (GEPLHS->getOperand(i) != GEPRHS->getOperand(i)) {
2237           if (GEPLHS->getOperand(i)->getType() !=
2238                      GEPRHS->getOperand(i)->getType()) {
2239             // Irreconsilable differences.
2240             NumDifferences = 2;
2241             break;
2242           } else {
2243             if (NumDifferences++) break;
2244             DiffOperand = i;
2245           }
2246         }
2247
2248       if (NumDifferences == 0)   // SAME GEP?
2249         return ReplaceInstUsesWith(I, // No comparison is needed here.
2250                                  ConstantBool::get(Cond == Instruction::SetEQ));
2251       else if (NumDifferences == 1) {
2252         return new SetCondInst(Cond, GEPLHS->getOperand(DiffOperand),
2253                                GEPRHS->getOperand(DiffOperand));
2254       }
2255     }
2256
2257     // Only lower this if the setcc is the only user of the GEP or if we expect
2258     // the result to fold to a constant!
2259     if ((isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
2260         (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
2261       // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)  --->  (OFFSET1 cmp OFFSET2)
2262       Value *L = EmitGEPOffset(GEPLHS, I, *this);
2263       Value *R = EmitGEPOffset(GEPRHS, I, *this);
2264       return new SetCondInst(Cond, L, R);
2265     }
2266   }
2267   return 0;
2268 }
2269
2270
2271 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
2272   bool Changed = SimplifyCommutative(I);
2273   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2274   const Type *Ty = Op0->getType();
2275
2276   // setcc X, X
2277   if (Op0 == Op1)
2278     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
2279
2280   if (isa<UndefValue>(Op1))                  // X setcc undef -> undef
2281     return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy));
2282
2283   // setcc <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
2284   // addresses never equal each other!  We already know that Op0 != Op1.
2285   if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
2286        isa<ConstantPointerNull>(Op0)) &&
2287       (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) ||
2288        isa<ConstantPointerNull>(Op1)))
2289     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
2290
2291   // setcc's with boolean values can always be turned into bitwise operations
2292   if (Ty == Type::BoolTy) {
2293     switch (I.getOpcode()) {
2294     default: assert(0 && "Invalid setcc instruction!");
2295     case Instruction::SetEQ: {     //  seteq bool %A, %B -> ~(A^B)
2296       Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp");
2297       InsertNewInstBefore(Xor, I);
2298       return BinaryOperator::createNot(Xor);
2299     }
2300     case Instruction::SetNE:
2301       return BinaryOperator::createXor(Op0, Op1);
2302
2303     case Instruction::SetGT:
2304       std::swap(Op0, Op1);                   // Change setgt -> setlt
2305       // FALL THROUGH
2306     case Instruction::SetLT: {               // setlt bool A, B -> ~X & Y
2307       Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2308       InsertNewInstBefore(Not, I);
2309       return BinaryOperator::createAnd(Not, Op1);
2310     }
2311     case Instruction::SetGE:
2312       std::swap(Op0, Op1);                   // Change setge -> setle
2313       // FALL THROUGH
2314     case Instruction::SetLE: {     //  setle bool %A, %B -> ~A | B
2315       Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2316       InsertNewInstBefore(Not, I);
2317       return BinaryOperator::createOr(Not, Op1);
2318     }
2319     }
2320   }
2321
2322   // See if we are doing a comparison between a constant and an instruction that
2323   // can be folded into the comparison.
2324   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2325     // Check to see if we are comparing against the minimum or maximum value...
2326     if (CI->isMinValue()) {
2327       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
2328         return ReplaceInstUsesWith(I, ConstantBool::False);
2329       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
2330         return ReplaceInstUsesWith(I, ConstantBool::True);
2331       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
2332         return BinaryOperator::createSetEQ(Op0, Op1);
2333       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
2334         return BinaryOperator::createSetNE(Op0, Op1);
2335
2336     } else if (CI->isMaxValue()) {
2337       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
2338         return ReplaceInstUsesWith(I, ConstantBool::False);
2339       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
2340         return ReplaceInstUsesWith(I, ConstantBool::True);
2341       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
2342         return BinaryOperator::createSetEQ(Op0, Op1);
2343       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
2344         return BinaryOperator::createSetNE(Op0, Op1);
2345
2346       // Comparing against a value really close to min or max?
2347     } else if (isMinValuePlusOne(CI)) {
2348       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
2349         return BinaryOperator::createSetEQ(Op0, SubOne(CI));
2350       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
2351         return BinaryOperator::createSetNE(Op0, SubOne(CI));
2352
2353     } else if (isMaxValueMinusOne(CI)) {
2354       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
2355         return BinaryOperator::createSetEQ(Op0, AddOne(CI));
2356       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
2357         return BinaryOperator::createSetNE(Op0, AddOne(CI));
2358     }
2359
2360     // If we still have a setle or setge instruction, turn it into the
2361     // appropriate setlt or setgt instruction.  Since the border cases have
2362     // already been handled above, this requires little checking.
2363     //
2364     if (I.getOpcode() == Instruction::SetLE)
2365       return BinaryOperator::createSetLT(Op0, AddOne(CI));
2366     if (I.getOpcode() == Instruction::SetGE)
2367       return BinaryOperator::createSetGT(Op0, SubOne(CI));
2368
2369     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
2370       switch (LHSI->getOpcode()) {
2371       case Instruction::PHI:
2372         if (Instruction *NV = FoldOpIntoPhi(I))
2373           return NV;
2374         break;
2375       case Instruction::And:
2376         if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
2377             LHSI->getOperand(0)->hasOneUse()) {
2378           // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
2379           // could exist), turn it into (X & (C2 << C1)) != (C3 << C1).  This
2380           // happens a LOT in code produced by the C front-end, for bitfield
2381           // access.
2382           ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0));
2383           ConstantUInt *ShAmt;
2384           ShAmt = Shift ? dyn_cast<ConstantUInt>(Shift->getOperand(1)) : 0;
2385           ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
2386           const Type *Ty = LHSI->getType();
2387
2388           // We can fold this as long as we can't shift unknown bits
2389           // into the mask.  This can only happen with signed shift
2390           // rights, as they sign-extend.
2391           if (ShAmt) {
2392             bool CanFold = Shift->getOpcode() != Instruction::Shr ||
2393                            Shift->getType()->isUnsigned();
2394             if (!CanFold) {
2395               // To test for the bad case of the signed shr, see if any
2396               // of the bits shifted in could be tested after the mask.
2397               Constant *OShAmt = ConstantUInt::get(Type::UByteTy,
2398                                    Ty->getPrimitiveSize()*8-ShAmt->getValue());
2399               Constant *ShVal =
2400                 ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), OShAmt);
2401               if (ConstantExpr::getAnd(ShVal, AndCST)->isNullValue())
2402                 CanFold = true;
2403             }
2404
2405             if (CanFold) {
2406               Constant *NewCst;
2407               if (Shift->getOpcode() == Instruction::Shl)
2408                 NewCst = ConstantExpr::getUShr(CI, ShAmt);
2409               else
2410                 NewCst = ConstantExpr::getShl(CI, ShAmt);
2411
2412               // Check to see if we are shifting out any of the bits being
2413               // compared.
2414               if (ConstantExpr::get(Shift->getOpcode(), NewCst, ShAmt) != CI){
2415                 // If we shifted bits out, the fold is not going to work out.
2416                 // As a special case, check to see if this means that the
2417                 // result is always true or false now.
2418                 if (I.getOpcode() == Instruction::SetEQ)
2419                   return ReplaceInstUsesWith(I, ConstantBool::False);
2420                 if (I.getOpcode() == Instruction::SetNE)
2421                   return ReplaceInstUsesWith(I, ConstantBool::True);
2422               } else {
2423                 I.setOperand(1, NewCst);
2424                 Constant *NewAndCST;
2425                 if (Shift->getOpcode() == Instruction::Shl)
2426                   NewAndCST = ConstantExpr::getUShr(AndCST, ShAmt);
2427                 else
2428                   NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
2429                 LHSI->setOperand(1, NewAndCST);
2430                 LHSI->setOperand(0, Shift->getOperand(0));
2431                 WorkList.push_back(Shift); // Shift is dead.
2432                 AddUsesToWorkList(I);
2433                 return &I;
2434               }
2435             }
2436           }
2437         }
2438         break;
2439
2440       // (setcc (cast X to larger), CI)
2441       case Instruction::Cast:
2442         if (Instruction *R =
2443                 visitSetCondInstWithCastAndConstant(I,cast<CastInst>(LHSI),CI))
2444           return R;
2445         break;
2446
2447       case Instruction::Shl:         // (setcc (shl X, ShAmt), CI)
2448         if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2449           switch (I.getOpcode()) {
2450           default: break;
2451           case Instruction::SetEQ:
2452           case Instruction::SetNE: {
2453             // If we are comparing against bits always shifted out, the
2454             // comparison cannot succeed.
2455             Constant *Comp =
2456               ConstantExpr::getShl(ConstantExpr::getShr(CI, ShAmt), ShAmt);
2457             if (Comp != CI) {// Comparing against a bit that we know is zero.
2458               bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2459               Constant *Cst = ConstantBool::get(IsSetNE);
2460               return ReplaceInstUsesWith(I, Cst);
2461             }
2462
2463             if (LHSI->hasOneUse()) {
2464               // Otherwise strength reduce the shift into an and.
2465               unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2466               unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
2467               uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1;
2468
2469               Constant *Mask;
2470               if (CI->getType()->isUnsigned()) {
2471                 Mask = ConstantUInt::get(CI->getType(), Val);
2472               } else if (ShAmtVal != 0) {
2473                 Mask = ConstantSInt::get(CI->getType(), Val);
2474               } else {
2475                 Mask = ConstantInt::getAllOnesValue(CI->getType());
2476               }
2477
2478               Instruction *AndI =
2479                 BinaryOperator::createAnd(LHSI->getOperand(0),
2480                                           Mask, LHSI->getName()+".mask");
2481               Value *And = InsertNewInstBefore(AndI, I);
2482               return new SetCondInst(I.getOpcode(), And,
2483                                      ConstantExpr::getUShr(CI, ShAmt));
2484             }
2485           }
2486           }
2487         }
2488         break;
2489
2490       case Instruction::Shr:         // (setcc (shr X, ShAmt), CI)
2491         if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2492           switch (I.getOpcode()) {
2493           default: break;
2494           case Instruction::SetEQ:
2495           case Instruction::SetNE: {
2496             // If we are comparing against bits always shifted out, the
2497             // comparison cannot succeed.
2498             Constant *Comp =
2499               ConstantExpr::getShr(ConstantExpr::getShl(CI, ShAmt), ShAmt);
2500
2501             if (Comp != CI) {// Comparing against a bit that we know is zero.
2502               bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2503               Constant *Cst = ConstantBool::get(IsSetNE);
2504               return ReplaceInstUsesWith(I, Cst);
2505             }
2506
2507             if (LHSI->hasOneUse() || CI->isNullValue()) {
2508               unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2509
2510               // Otherwise strength reduce the shift into an and.
2511               uint64_t Val = ~0ULL;          // All ones.
2512               Val <<= ShAmtVal;              // Shift over to the right spot.
2513
2514               Constant *Mask;
2515               if (CI->getType()->isUnsigned()) {
2516                 unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
2517                 Val &= (1ULL << TypeBits)-1;
2518                 Mask = ConstantUInt::get(CI->getType(), Val);
2519               } else {
2520                 Mask = ConstantSInt::get(CI->getType(), Val);
2521               }
2522
2523               Instruction *AndI =
2524                 BinaryOperator::createAnd(LHSI->getOperand(0),
2525                                           Mask, LHSI->getName()+".mask");
2526               Value *And = InsertNewInstBefore(AndI, I);
2527               return new SetCondInst(I.getOpcode(), And,
2528                                      ConstantExpr::getShl(CI, ShAmt));
2529             }
2530             break;
2531           }
2532           }
2533         }
2534         break;
2535
2536       case Instruction::Div:
2537         // Fold: (div X, C1) op C2 -> range check
2538         if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
2539           // Fold this div into the comparison, producing a range check.
2540           // Determine, based on the divide type, what the range is being
2541           // checked.  If there is an overflow on the low or high side, remember
2542           // it, otherwise compute the range [low, hi) bounding the new value.
2543           bool LoOverflow = false, HiOverflow = 0;
2544           ConstantInt *LoBound = 0, *HiBound = 0;
2545
2546           ConstantInt *Prod;
2547           bool ProdOV = MulWithOverflow(Prod, CI, DivRHS);
2548
2549           Instruction::BinaryOps Opcode = I.getOpcode();
2550
2551           if (DivRHS->isNullValue()) {  // Don't hack on divide by zeros.
2552           } else if (LHSI->getType()->isUnsigned()) {  // udiv
2553             LoBound = Prod;
2554             LoOverflow = ProdOV;
2555             HiOverflow = ProdOV || AddWithOverflow(HiBound, LoBound, DivRHS);
2556           } else if (isPositive(DivRHS)) {             // Divisor is > 0.
2557             if (CI->isNullValue()) {       // (X / pos) op 0
2558               // Can't overflow.
2559               LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
2560               HiBound = DivRHS;
2561             } else if (isPositive(CI)) {   // (X / pos) op pos
2562               LoBound = Prod;
2563               LoOverflow = ProdOV;
2564               HiOverflow = ProdOV || AddWithOverflow(HiBound, Prod, DivRHS);
2565             } else {                       // (X / pos) op neg
2566               Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
2567               LoOverflow = AddWithOverflow(LoBound, Prod,
2568                                            cast<ConstantInt>(DivRHSH));
2569               HiBound = Prod;
2570               HiOverflow = ProdOV;
2571             }
2572           } else {                                     // Divisor is < 0.
2573             if (CI->isNullValue()) {       // (X / neg) op 0
2574               LoBound = AddOne(DivRHS);
2575               HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
2576             } else if (isPositive(CI)) {   // (X / neg) op pos
2577               HiOverflow = LoOverflow = ProdOV;
2578               if (!LoOverflow)
2579                 LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS));
2580               HiBound = AddOne(Prod);
2581             } else {                       // (X / neg) op neg
2582               LoBound = Prod;
2583               LoOverflow = HiOverflow = ProdOV;
2584               HiBound = cast<ConstantInt>(ConstantExpr::getSub(Prod, DivRHS));
2585             }
2586
2587             // Dividing by a negate swaps the condition.
2588             Opcode = SetCondInst::getSwappedCondition(Opcode);
2589           }
2590
2591           if (LoBound) {
2592             Value *X = LHSI->getOperand(0);
2593             switch (Opcode) {
2594             default: assert(0 && "Unhandled setcc opcode!");
2595             case Instruction::SetEQ:
2596               if (LoOverflow && HiOverflow)
2597                 return ReplaceInstUsesWith(I, ConstantBool::False);
2598               else if (HiOverflow)
2599                 return new SetCondInst(Instruction::SetGE, X, LoBound);
2600               else if (LoOverflow)
2601                 return new SetCondInst(Instruction::SetLT, X, HiBound);
2602               else
2603                 return InsertRangeTest(X, LoBound, HiBound, true, I);
2604             case Instruction::SetNE:
2605               if (LoOverflow && HiOverflow)
2606                 return ReplaceInstUsesWith(I, ConstantBool::True);
2607               else if (HiOverflow)
2608                 return new SetCondInst(Instruction::SetLT, X, LoBound);
2609               else if (LoOverflow)
2610                 return new SetCondInst(Instruction::SetGE, X, HiBound);
2611               else
2612                 return InsertRangeTest(X, LoBound, HiBound, false, I);
2613             case Instruction::SetLT:
2614               if (LoOverflow)
2615                 return ReplaceInstUsesWith(I, ConstantBool::False);
2616               return new SetCondInst(Instruction::SetLT, X, LoBound);
2617             case Instruction::SetGT:
2618               if (HiOverflow)
2619                 return ReplaceInstUsesWith(I, ConstantBool::False);
2620               return new SetCondInst(Instruction::SetGE, X, HiBound);
2621             }
2622           }
2623         }
2624         break;
2625       case Instruction::Select:
2626         // If either operand of the select is a constant, we can fold the
2627         // comparison into the select arms, which will cause one to be
2628         // constant folded and the select turned into a bitwise or.
2629         Value *Op1 = 0, *Op2 = 0;
2630         if (LHSI->hasOneUse()) {
2631           if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
2632             // Fold the known value into the constant operand.
2633             Op1 = ConstantExpr::get(I.getOpcode(), C, CI);
2634             // Insert a new SetCC of the other select operand.
2635             Op2 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
2636                                                       LHSI->getOperand(2), CI,
2637                                                       I.getName()), I);
2638           } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
2639             // Fold the known value into the constant operand.
2640             Op2 = ConstantExpr::get(I.getOpcode(), C, CI);
2641             // Insert a new SetCC of the other select operand.
2642             Op1 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
2643                                                       LHSI->getOperand(1), CI,
2644                                                       I.getName()), I);
2645           }
2646         }
2647
2648         if (Op1)
2649           return new SelectInst(LHSI->getOperand(0), Op1, Op2);
2650         break;
2651       }
2652
2653     // Simplify seteq and setne instructions...
2654     if (I.getOpcode() == Instruction::SetEQ ||
2655         I.getOpcode() == Instruction::SetNE) {
2656       bool isSetNE = I.getOpcode() == Instruction::SetNE;
2657
2658       // If the first operand is (and|or|xor) with a constant, and the second
2659       // operand is a constant, simplify a bit.
2660       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
2661         switch (BO->getOpcode()) {
2662         case Instruction::Rem:
2663           // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
2664           if (CI->isNullValue() && isa<ConstantSInt>(BO->getOperand(1)) &&
2665               BO->hasOneUse() &&
2666               cast<ConstantSInt>(BO->getOperand(1))->getValue() > 1)
2667             if (unsigned L2 =
2668                 Log2(cast<ConstantSInt>(BO->getOperand(1))->getValue())) {
2669               const Type *UTy = BO->getType()->getUnsignedVersion();
2670               Value *NewX = InsertNewInstBefore(new CastInst(BO->getOperand(0),
2671                                                              UTy, "tmp"), I);
2672               Constant *RHSCst = ConstantUInt::get(UTy, 1ULL << L2);
2673               Value *NewRem =InsertNewInstBefore(BinaryOperator::createRem(NewX,
2674                                                     RHSCst, BO->getName()), I);
2675               return BinaryOperator::create(I.getOpcode(), NewRem,
2676                                             Constant::getNullValue(UTy));
2677             }
2678           break;
2679
2680         case Instruction::Add:
2681           // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
2682           if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2683             if (BO->hasOneUse())
2684               return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2685                                      ConstantExpr::getSub(CI, BOp1C));
2686           } else if (CI->isNullValue()) {
2687             // Replace ((add A, B) != 0) with (A != -B) if A or B is
2688             // efficiently invertible, or if the add has just this one use.
2689             Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
2690
2691             if (Value *NegVal = dyn_castNegVal(BOp1))
2692               return new SetCondInst(I.getOpcode(), BOp0, NegVal);
2693             else if (Value *NegVal = dyn_castNegVal(BOp0))
2694               return new SetCondInst(I.getOpcode(), NegVal, BOp1);
2695             else if (BO->hasOneUse()) {
2696               Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
2697               BO->setName("");
2698               InsertNewInstBefore(Neg, I);
2699               return new SetCondInst(I.getOpcode(), BOp0, Neg);
2700             }
2701           }
2702           break;
2703         case Instruction::Xor:
2704           // For the xor case, we can xor two constants together, eliminating
2705           // the explicit xor.
2706           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
2707             return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
2708                                   ConstantExpr::getXor(CI, BOC));
2709
2710           // FALLTHROUGH
2711         case Instruction::Sub:
2712           // Replace (([sub|xor] A, B) != 0) with (A != B)
2713           if (CI->isNullValue())
2714             return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2715                                    BO->getOperand(1));
2716           break;
2717
2718         case Instruction::Or:
2719           // If bits are being or'd in that are not present in the constant we
2720           // are comparing against, then the comparison could never succeed!
2721           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
2722             Constant *NotCI = ConstantExpr::getNot(CI);
2723             if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
2724               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2725           }
2726           break;
2727
2728         case Instruction::And:
2729           if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2730             // If bits are being compared against that are and'd out, then the
2731             // comparison can never succeed!
2732             if (!ConstantExpr::getAnd(CI,
2733                                       ConstantExpr::getNot(BOC))->isNullValue())
2734               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2735
2736             // If we have ((X & C) == C), turn it into ((X & C) != 0).
2737             if (CI == BOC && isOneBitSet(CI))
2738               return new SetCondInst(isSetNE ? Instruction::SetEQ :
2739                                      Instruction::SetNE, Op0,
2740                                      Constant::getNullValue(CI->getType()));
2741
2742             // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
2743             // to be a signed value as appropriate.
2744             if (isSignBit(BOC)) {
2745               Value *X = BO->getOperand(0);
2746               // If 'X' is not signed, insert a cast now...
2747               if (!BOC->getType()->isSigned()) {
2748                 const Type *DestTy = BOC->getType()->getSignedVersion();
2749                 X = InsertCastBefore(X, DestTy, I);
2750               }
2751               return new SetCondInst(isSetNE ? Instruction::SetLT :
2752                                          Instruction::SetGE, X,
2753                                      Constant::getNullValue(X->getType()));
2754             }
2755
2756             // ((X & ~7) == 0) --> X < 8
2757             if (CI->isNullValue() && isHighOnes(BOC)) {
2758               Value *X = BO->getOperand(0);
2759               Constant *NegX = ConstantExpr::getNeg(BOC);
2760
2761               // If 'X' is signed, insert a cast now.
2762               if (NegX->getType()->isSigned()) {
2763                 const Type *DestTy = NegX->getType()->getUnsignedVersion();
2764                 X = InsertCastBefore(X, DestTy, I);
2765                 NegX = ConstantExpr::getCast(NegX, DestTy);
2766               }
2767
2768               return new SetCondInst(isSetNE ? Instruction::SetGE :
2769                                      Instruction::SetLT, X, NegX);
2770             }
2771
2772           }
2773         default: break;
2774         }
2775       }
2776     } else {  // Not a SetEQ/SetNE
2777       // If the LHS is a cast from an integral value of the same size,
2778       if (CastInst *Cast = dyn_cast<CastInst>(Op0)) {
2779         Value *CastOp = Cast->getOperand(0);
2780         const Type *SrcTy = CastOp->getType();
2781         unsigned SrcTySize = SrcTy->getPrimitiveSize();
2782         if (SrcTy != Cast->getType() && SrcTy->isInteger() &&
2783             SrcTySize == Cast->getType()->getPrimitiveSize()) {
2784           assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) &&
2785                  "Source and destination signednesses should differ!");
2786           if (Cast->getType()->isSigned()) {
2787             // If this is a signed comparison, check for comparisons in the
2788             // vicinity of zero.
2789             if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
2790               // X < 0  => x > 127
2791               return BinaryOperator::createSetGT(CastOp,
2792                          ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1));
2793             else if (I.getOpcode() == Instruction::SetGT &&
2794                      cast<ConstantSInt>(CI)->getValue() == -1)
2795               // X > -1  => x < 128
2796               return BinaryOperator::createSetLT(CastOp,
2797                          ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1)));
2798           } else {
2799             ConstantUInt *CUI = cast<ConstantUInt>(CI);
2800             if (I.getOpcode() == Instruction::SetLT &&
2801                 CUI->getValue() == 1ULL << (SrcTySize*8-1))
2802               // X < 128 => X > -1
2803               return BinaryOperator::createSetGT(CastOp,
2804                                                  ConstantSInt::get(SrcTy, -1));
2805             else if (I.getOpcode() == Instruction::SetGT &&
2806                      CUI->getValue() == (1ULL << (SrcTySize*8-1))-1)
2807               // X > 127 => X < 0
2808               return BinaryOperator::createSetLT(CastOp,
2809                                                  Constant::getNullValue(SrcTy));
2810           }
2811         }
2812       }
2813     }
2814   }
2815
2816   // If we can optimize a 'setcc GEP, P' or 'setcc P, GEP', do so now.
2817   if (User *GEP = dyn_castGetElementPtr(Op0))
2818     if (Instruction *NI = FoldGEPSetCC(GEP, Op1, I.getOpcode(), I))
2819       return NI;
2820   if (User *GEP = dyn_castGetElementPtr(Op1))
2821     if (Instruction *NI = FoldGEPSetCC(GEP, Op0,
2822                            SetCondInst::getSwappedCondition(I.getOpcode()), I))
2823       return NI;
2824
2825   // Test to see if the operands of the setcc are casted versions of other
2826   // values.  If the cast can be stripped off both arguments, we do so now.
2827   if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
2828     Value *CastOp0 = CI->getOperand(0);
2829     if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
2830         (isa<Constant>(Op1) || isa<CastInst>(Op1)) &&
2831         (I.getOpcode() == Instruction::SetEQ ||
2832          I.getOpcode() == Instruction::SetNE)) {
2833       // We keep moving the cast from the left operand over to the right
2834       // operand, where it can often be eliminated completely.
2835       Op0 = CastOp0;
2836
2837       // If operand #1 is a cast instruction, see if we can eliminate it as
2838       // well.
2839       if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
2840         if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
2841                                                                Op0->getType()))
2842           Op1 = CI2->getOperand(0);
2843
2844       // If Op1 is a constant, we can fold the cast into the constant.
2845       if (Op1->getType() != Op0->getType())
2846         if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
2847           Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
2848         } else {
2849           // Otherwise, cast the RHS right before the setcc
2850           Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
2851           InsertNewInstBefore(cast<Instruction>(Op1), I);
2852         }
2853       return BinaryOperator::create(I.getOpcode(), Op0, Op1);
2854     }
2855
2856     // Handle the special case of: setcc (cast bool to X), <cst>
2857     // This comes up when you have code like
2858     //   int X = A < B;
2859     //   if (X) ...
2860     // For generality, we handle any zero-extension of any operand comparison
2861     // with a constant.
2862     if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) {
2863       const Type *SrcTy = CastOp0->getType();
2864       const Type *DestTy = Op0->getType();
2865       if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
2866           (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) {
2867         // Ok, we have an expansion of operand 0 into a new type.  Get the
2868         // constant value, masink off bits which are not set in the RHS.  These
2869         // could be set if the destination value is signed.
2870         uint64_t ConstVal = ConstantRHS->getRawValue();
2871         ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1;
2872
2873         // If the constant we are comparing it with has high bits set, which
2874         // don't exist in the original value, the values could never be equal,
2875         // because the source would be zero extended.
2876         unsigned SrcBits =
2877           SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8;
2878         bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1));
2879         if (ConstVal & ~((1ULL << SrcBits)-1)) {
2880           switch (I.getOpcode()) {
2881           default: assert(0 && "Unknown comparison type!");
2882           case Instruction::SetEQ:
2883             return ReplaceInstUsesWith(I, ConstantBool::False);
2884           case Instruction::SetNE:
2885             return ReplaceInstUsesWith(I, ConstantBool::True);
2886           case Instruction::SetLT:
2887           case Instruction::SetLE:
2888             if (DestTy->isSigned() && HasSignBit)
2889               return ReplaceInstUsesWith(I, ConstantBool::False);
2890             return ReplaceInstUsesWith(I, ConstantBool::True);
2891           case Instruction::SetGT:
2892           case Instruction::SetGE:
2893             if (DestTy->isSigned() && HasSignBit)
2894               return ReplaceInstUsesWith(I, ConstantBool::True);
2895             return ReplaceInstUsesWith(I, ConstantBool::False);
2896           }
2897         }
2898
2899         // Otherwise, we can replace the setcc with a setcc of the smaller
2900         // operand value.
2901         Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy);
2902         return BinaryOperator::create(I.getOpcode(), CastOp0, Op1);
2903       }
2904     }
2905   }
2906   return Changed ? &I : 0;
2907 }
2908
2909 // visitSetCondInstWithCastAndConstant - this method is part of the
2910 // visitSetCondInst method. It handles the situation where we have:
2911 //   (setcc (cast X to larger), CI)
2912 // It tries to remove the cast and even the setcc if the CI value
2913 // and range of the cast allow it.
2914 Instruction *
2915 InstCombiner::visitSetCondInstWithCastAndConstant(BinaryOperator&I,
2916                                                   CastInst* LHSI,
2917                                                   ConstantInt* CI) {
2918   const Type *SrcTy = LHSI->getOperand(0)->getType();
2919   const Type *DestTy = LHSI->getType();
2920   if (!SrcTy->isIntegral() || !DestTy->isIntegral())
2921     return 0;
2922
2923   unsigned SrcBits = SrcTy->getPrimitiveSize()*8;
2924   unsigned DestBits = DestTy->getPrimitiveSize()*8;
2925   if (SrcTy == Type::BoolTy)
2926     SrcBits = 1;
2927   if (DestTy == Type::BoolTy)
2928     DestBits = 1;
2929   if (SrcBits < DestBits) {
2930     // There are fewer bits in the source of the cast than in the result
2931     // of the cast. Any other case doesn't matter because the constant
2932     // value won't have changed due to sign extension.
2933     Constant *NewCst = ConstantExpr::getCast(CI, SrcTy);
2934     if (ConstantExpr::getCast(NewCst, DestTy) == CI) {
2935       // The constant value operand of the setCC before and after a
2936       // cast to the source type of the cast instruction is the same
2937       // value, so we just replace with the same setcc opcode, but
2938       // using the source value compared to the constant casted to the
2939       // source type.
2940       if (SrcTy->isSigned() && DestTy->isUnsigned()) {
2941         CastInst* Cst = new CastInst(LHSI->getOperand(0),
2942                                      SrcTy->getUnsignedVersion(),
2943                                      LHSI->getName());
2944         InsertNewInstBefore(Cst,I);
2945         return new SetCondInst(I.getOpcode(), Cst,
2946                                ConstantExpr::getCast(CI,
2947                                                  SrcTy->getUnsignedVersion()));
2948       }
2949       return new SetCondInst(I.getOpcode(), LHSI->getOperand(0),NewCst);
2950     }
2951
2952     // The constant value before and after a cast to the source type
2953     // is different, so various cases are possible depending on the
2954     // opcode and the signs of the types involved in the cast.
2955     switch (I.getOpcode()) {
2956     case Instruction::SetLT: {
2957       return 0;
2958       Constant* Max = ConstantIntegral::getMaxValue(SrcTy);
2959       Max = ConstantExpr::getCast(Max, DestTy);
2960       return ReplaceInstUsesWith(I, ConstantExpr::getSetLT(Max, CI));
2961     }
2962     case Instruction::SetGT: {
2963       return 0; // FIXME! RENABLE.  This breaks for (cast sbyte to uint) > 255
2964       Constant* Min = ConstantIntegral::getMinValue(SrcTy);
2965       Min = ConstantExpr::getCast(Min, DestTy);
2966       return ReplaceInstUsesWith(I, ConstantExpr::getSetGT(Min, CI));
2967     }
2968     case Instruction::SetEQ:
2969       // We're looking for equality, and we know the values are not
2970       // equal so replace with constant False.
2971       return ReplaceInstUsesWith(I, ConstantBool::False);
2972     case Instruction::SetNE:
2973       // We're testing for inequality, and we know the values are not
2974       // equal so replace with constant True.
2975       return ReplaceInstUsesWith(I, ConstantBool::True);
2976     case Instruction::SetLE:
2977     case Instruction::SetGE:
2978       assert(0 && "SetLE and SetGE should be handled elsewhere");
2979     default:
2980       assert(0 && "unknown integer comparison");
2981     }
2982   }
2983   return 0;
2984 }
2985
2986
2987 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
2988   assert(I.getOperand(1)->getType() == Type::UByteTy);
2989   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2990   bool isLeftShift = I.getOpcode() == Instruction::Shl;
2991
2992   // shl X, 0 == X and shr X, 0 == X
2993   // shl 0, X == 0 and shr 0, X == 0
2994   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
2995       Op0 == Constant::getNullValue(Op0->getType()))
2996     return ReplaceInstUsesWith(I, Op0);
2997
2998   if (isa<UndefValue>(Op0)) {            // undef >>s X -> undef
2999     if (!isLeftShift && I.getType()->isSigned())
3000       return ReplaceInstUsesWith(I, Op0);
3001     else                         // undef << X -> 0   AND  undef >>u X -> 0
3002       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
3003   }
3004   if (isa<UndefValue>(Op1)) {
3005     if (isLeftShift || I.getType()->isUnsigned())
3006       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
3007     else
3008       return ReplaceInstUsesWith(I, Op0);          // X >>s undef -> X
3009   }
3010
3011   // shr int -1, X = -1   (for any arithmetic shift rights of ~0)
3012   if (!isLeftShift)
3013     if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
3014       if (CSI->isAllOnesValue())
3015         return ReplaceInstUsesWith(I, CSI);
3016
3017   // Try to fold constant and into select arguments.
3018   if (isa<Constant>(Op0))
3019     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
3020       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
3021         return R;
3022
3023   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
3024     // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
3025     // of a signed value.
3026     //
3027     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
3028     if (CUI->getValue() >= TypeBits) {
3029       if (!Op0->getType()->isSigned() || isLeftShift)
3030         return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
3031       else {
3032         I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1));
3033         return &I;
3034       }
3035     }
3036
3037     // ((X*C1) << C2) == (X * (C1 << C2))
3038     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
3039       if (BO->getOpcode() == Instruction::Mul && isLeftShift)
3040         if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
3041           return BinaryOperator::createMul(BO->getOperand(0),
3042                                            ConstantExpr::getShl(BOOp, CUI));
3043
3044     // Try to fold constant and into select arguments.
3045     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
3046       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
3047         return R;
3048     if (isa<PHINode>(Op0))
3049       if (Instruction *NV = FoldOpIntoPhi(I))
3050         return NV;
3051
3052     if (Op0->hasOneUse()) {
3053       // If this is a SHL of a sign-extending cast, see if we can turn the input
3054       // into a zero extending cast (a simple strength reduction).
3055       if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
3056         const Type *SrcTy = CI->getOperand(0)->getType();
3057         if (isLeftShift && SrcTy->isInteger() && SrcTy->isSigned() &&
3058             SrcTy->getPrimitiveSize() < CI->getType()->getPrimitiveSize()) {
3059           // We can change it to a zero extension if we are shifting out all of
3060           // the sign extended bits.  To check this, form a mask of all of the
3061           // sign extend bits, then shift them left and see if we have anything
3062           // left.
3063           Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy); //     1111
3064           Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());   // 00001111
3065           Mask = ConstantExpr::getNot(Mask);   // 1's in the sign bits: 11110000
3066           if (ConstantExpr::getShl(Mask, CUI)->isNullValue()) {
3067             // If the shift is nuking all of the sign bits, change this to a
3068             // zero extension cast.  To do this, cast the cast input to
3069             // unsigned, then to the requested size.
3070             Value *CastOp = CI->getOperand(0);
3071             Instruction *NC =
3072               new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
3073                            CI->getName()+".uns");
3074             NC = InsertNewInstBefore(NC, I);
3075             // Finally, insert a replacement for CI.
3076             NC = new CastInst(NC, CI->getType(), CI->getName());
3077             CI->setName("");
3078             NC = InsertNewInstBefore(NC, I);
3079             WorkList.push_back(CI);  // Delete CI later.
3080             I.setOperand(0, NC);
3081             return &I;               // The SHL operand was modified.
3082           }
3083         }
3084       }
3085
3086       // If the operand is an bitwise operator with a constant RHS, and the
3087       // shift is the only use, we can pull it out of the shift.
3088       if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
3089         if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
3090           bool isValid = true;     // Valid only for And, Or, Xor
3091           bool highBitSet = false; // Transform if high bit of constant set?
3092
3093           switch (Op0BO->getOpcode()) {
3094           default: isValid = false; break;   // Do not perform transform!
3095           case Instruction::Add:
3096             isValid = isLeftShift;
3097             break;
3098           case Instruction::Or:
3099           case Instruction::Xor:
3100             highBitSet = false;
3101             break;
3102           case Instruction::And:
3103             highBitSet = true;
3104             break;
3105           }
3106
3107           // If this is a signed shift right, and the high bit is modified
3108           // by the logical operation, do not perform the transformation.
3109           // The highBitSet boolean indicates the value of the high bit of
3110           // the constant which would cause it to be modified for this
3111           // operation.
3112           //
3113           if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
3114             uint64_t Val = Op0C->getRawValue();
3115             isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
3116           }
3117
3118           if (isValid) {
3119             Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI);
3120
3121             Instruction *NewShift =
3122               new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
3123                             Op0BO->getName());
3124             Op0BO->setName("");
3125             InsertNewInstBefore(NewShift, I);
3126
3127             return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
3128                                           NewRHS);
3129           }
3130         }
3131     }
3132
3133     // If this is a shift of a shift, see if we can fold the two together...
3134     if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
3135       if (ConstantUInt *ShiftAmt1C =
3136                                  dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
3137         unsigned ShiftAmt1 = (unsigned)ShiftAmt1C->getValue();
3138         unsigned ShiftAmt2 = (unsigned)CUI->getValue();
3139
3140         // Check for (A << c1) << c2   and   (A >> c1) >> c2
3141         if (I.getOpcode() == Op0SI->getOpcode()) {
3142           unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift...
3143           if (Op0->getType()->getPrimitiveSize()*8 < Amt)
3144             Amt = Op0->getType()->getPrimitiveSize()*8;
3145           return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
3146                                ConstantUInt::get(Type::UByteTy, Amt));
3147         }
3148
3149         // Check for (A << c1) >> c2 or visaversa.  If we are dealing with
3150         // signed types, we can only support the (A >> c1) << c2 configuration,
3151         // because it can not turn an arbitrary bit of A into a sign bit.
3152         if (I.getType()->isUnsigned() || isLeftShift) {
3153           // Calculate bitmask for what gets shifted off the edge...
3154           Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
3155           if (isLeftShift)
3156             C = ConstantExpr::getShl(C, ShiftAmt1C);
3157           else
3158             C = ConstantExpr::getShr(C, ShiftAmt1C);
3159
3160           Instruction *Mask =
3161             BinaryOperator::createAnd(Op0SI->getOperand(0), C,
3162                                       Op0SI->getOperand(0)->getName()+".mask");
3163           InsertNewInstBefore(Mask, I);
3164
3165           // Figure out what flavor of shift we should use...
3166           if (ShiftAmt1 == ShiftAmt2)
3167             return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
3168           else if (ShiftAmt1 < ShiftAmt2) {
3169             return new ShiftInst(I.getOpcode(), Mask,
3170                          ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
3171           } else {
3172             return new ShiftInst(Op0SI->getOpcode(), Mask,
3173                          ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
3174           }
3175         }
3176       }
3177   }
3178
3179   return 0;
3180 }
3181
3182 enum CastType {
3183   Noop     = 0,
3184   Truncate = 1,
3185   Signext  = 2,
3186   Zeroext  = 3
3187 };
3188
3189 /// getCastType - In the future, we will split the cast instruction into these
3190 /// various types.  Until then, we have to do the analysis here.
3191 static CastType getCastType(const Type *Src, const Type *Dest) {
3192   assert(Src->isIntegral() && Dest->isIntegral() &&
3193          "Only works on integral types!");
3194   unsigned SrcSize = Src->getPrimitiveSize()*8;
3195   if (Src == Type::BoolTy) SrcSize = 1;
3196   unsigned DestSize = Dest->getPrimitiveSize()*8;
3197   if (Dest == Type::BoolTy) DestSize = 1;
3198
3199   if (SrcSize == DestSize) return Noop;
3200   if (SrcSize > DestSize)  return Truncate;
3201   if (Src->isSigned()) return Signext;
3202   return Zeroext;
3203 }
3204
3205
3206 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
3207 // instruction.
3208 //
3209 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
3210                                           const Type *DstTy, TargetData *TD) {
3211
3212   // It is legal to eliminate the instruction if casting A->B->A if the sizes
3213   // are identical and the bits don't get reinterpreted (for example
3214   // int->float->int would not be allowed).
3215   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
3216     return true;
3217
3218   // If we are casting between pointer and integer types, treat pointers as
3219   // integers of the appropriate size for the code below.
3220   if (isa<PointerType>(SrcTy)) SrcTy = TD->getIntPtrType();
3221   if (isa<PointerType>(MidTy)) MidTy = TD->getIntPtrType();
3222   if (isa<PointerType>(DstTy)) DstTy = TD->getIntPtrType();
3223
3224   // Allow free casting and conversion of sizes as long as the sign doesn't
3225   // change...
3226   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
3227     CastType FirstCast = getCastType(SrcTy, MidTy);
3228     CastType SecondCast = getCastType(MidTy, DstTy);
3229
3230     // Capture the effect of these two casts.  If the result is a legal cast,
3231     // the CastType is stored here, otherwise a special code is used.
3232     static const unsigned CastResult[] = {
3233       // First cast is noop
3234       0, 1, 2, 3,
3235       // First cast is a truncate
3236       1, 1, 4, 4,         // trunc->extend is not safe to eliminate
3237       // First cast is a sign ext
3238       2, 5, 2, 4,         // signext->zeroext never ok
3239       // First cast is a zero ext
3240       3, 5, 3, 3,
3241     };
3242
3243     unsigned Result = CastResult[FirstCast*4+SecondCast];
3244     switch (Result) {
3245     default: assert(0 && "Illegal table value!");
3246     case 0:
3247     case 1:
3248     case 2:
3249     case 3:
3250       // FIXME: in the future, when LLVM has explicit sign/zeroextends and
3251       // truncates, we could eliminate more casts.
3252       return (unsigned)getCastType(SrcTy, DstTy) == Result;
3253     case 4:
3254       return false;  // Not possible to eliminate this here.
3255     case 5:
3256       // Sign or zero extend followed by truncate is always ok if the result
3257       // is a truncate or noop.
3258       CastType ResultCast = getCastType(SrcTy, DstTy);
3259       if (ResultCast == Noop || ResultCast == Truncate)
3260         return true;
3261       // Otherwise we are still growing the value, we are only safe if the
3262       // result will match the sign/zeroextendness of the result.
3263       return ResultCast == FirstCast;
3264     }
3265   }
3266   return false;
3267 }
3268
3269 static bool ValueRequiresCast(const Value *V, const Type *Ty, TargetData *TD) {
3270   if (V->getType() == Ty || isa<Constant>(V)) return false;
3271   if (const CastInst *CI = dyn_cast<CastInst>(V))
3272     if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty,
3273                                TD))
3274       return false;
3275   return true;
3276 }
3277
3278 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
3279 /// InsertBefore instruction.  This is specialized a bit to avoid inserting
3280 /// casts that are known to not do anything...
3281 ///
3282 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
3283                                              Instruction *InsertBefore) {
3284   if (V->getType() == DestTy) return V;
3285   if (Constant *C = dyn_cast<Constant>(V))
3286     return ConstantExpr::getCast(C, DestTy);
3287
3288   CastInst *CI = new CastInst(V, DestTy, V->getName());
3289   InsertNewInstBefore(CI, *InsertBefore);
3290   return CI;
3291 }
3292
3293 // CastInst simplification
3294 //
3295 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
3296   Value *Src = CI.getOperand(0);
3297
3298   // If the user is casting a value to the same type, eliminate this cast
3299   // instruction...
3300   if (CI.getType() == Src->getType())
3301     return ReplaceInstUsesWith(CI, Src);
3302
3303   if (isa<UndefValue>(Src))   // cast undef -> undef
3304     return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType()));
3305
3306   // If casting the result of another cast instruction, try to eliminate this
3307   // one!
3308   //
3309   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {   // A->B->C cast
3310     Value *A = CSrc->getOperand(0);
3311     if (isEliminableCastOfCast(A->getType(), CSrc->getType(),
3312                                CI.getType(), TD)) {
3313       // This instruction now refers directly to the cast's src operand.  This
3314       // has a good chance of making CSrc dead.
3315       CI.setOperand(0, CSrc->getOperand(0));
3316       return &CI;
3317     }
3318
3319     // If this is an A->B->A cast, and we are dealing with integral types, try
3320     // to convert this into a logical 'and' instruction.
3321     //
3322     if (A->getType()->isInteger() &&
3323         CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
3324         CSrc->getType()->isUnsigned() &&   // B->A cast must zero extend
3325         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()&&
3326         A->getType()->getPrimitiveSize() == CI.getType()->getPrimitiveSize()) {
3327       assert(CSrc->getType() != Type::ULongTy &&
3328              "Cannot have type bigger than ulong!");
3329       uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
3330       Constant *AndOp = ConstantUInt::get(A->getType()->getUnsignedVersion(),
3331                                           AndValue);
3332       AndOp = ConstantExpr::getCast(AndOp, A->getType());
3333       Instruction *And = BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
3334       if (And->getType() != CI.getType()) {
3335         And->setName(CSrc->getName()+".mask");
3336         InsertNewInstBefore(And, CI);
3337         And = new CastInst(And, CI.getType());
3338       }
3339       return And;
3340     }
3341   }
3342
3343   // If this is a cast to bool, turn it into the appropriate setne instruction.
3344   if (CI.getType() == Type::BoolTy)
3345     return BinaryOperator::createSetNE(CI.getOperand(0),
3346                        Constant::getNullValue(CI.getOperand(0)->getType()));
3347
3348   // If casting the result of a getelementptr instruction with no offset, turn
3349   // this into a cast of the original pointer!
3350   //
3351   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
3352     bool AllZeroOperands = true;
3353     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
3354       if (!isa<Constant>(GEP->getOperand(i)) ||
3355           !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
3356         AllZeroOperands = false;
3357         break;
3358       }
3359     if (AllZeroOperands) {
3360       CI.setOperand(0, GEP->getOperand(0));
3361       return &CI;
3362     }
3363   }
3364
3365   // If we are casting a malloc or alloca to a pointer to a type of the same
3366   // size, rewrite the allocation instruction to allocate the "right" type.
3367   //
3368   if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
3369     if (AI->hasOneUse() && !AI->isArrayAllocation())
3370       if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
3371         // Get the type really allocated and the type casted to...
3372         const Type *AllocElTy = AI->getAllocatedType();
3373         const Type *CastElTy = PTy->getElementType();
3374         if (AllocElTy->isSized() && CastElTy->isSized()) {
3375           uint64_t AllocElTySize = TD->getTypeSize(AllocElTy);
3376           uint64_t CastElTySize = TD->getTypeSize(CastElTy);
3377
3378           // If the allocation is for an even multiple of the cast type size
3379           if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
3380             Value *Amt = ConstantUInt::get(Type::UIntTy,
3381                                          AllocElTySize/CastElTySize);
3382             std::string Name = AI->getName(); AI->setName("");
3383             AllocationInst *New;
3384             if (isa<MallocInst>(AI))
3385               New = new MallocInst(CastElTy, Amt, Name);
3386             else
3387               New = new AllocaInst(CastElTy, Amt, Name);
3388             InsertNewInstBefore(New, *AI);
3389             return ReplaceInstUsesWith(CI, New);
3390           }
3391         }
3392       }
3393
3394   if (SelectInst *SI = dyn_cast<SelectInst>(Src))
3395     if (Instruction *NV = FoldOpIntoSelect(CI, SI, this))
3396       return NV;
3397   if (isa<PHINode>(Src))
3398     if (Instruction *NV = FoldOpIntoPhi(CI))
3399       return NV;
3400
3401   // If the source value is an instruction with only this use, we can attempt to
3402   // propagate the cast into the instruction.  Also, only handle integral types
3403   // for now.
3404   if (Instruction *SrcI = dyn_cast<Instruction>(Src))
3405     if (SrcI->hasOneUse() && Src->getType()->isIntegral() &&
3406         CI.getType()->isInteger()) {  // Don't mess with casts to bool here
3407       const Type *DestTy = CI.getType();
3408       unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
3409       unsigned DestBitSize = getTypeSizeInBits(DestTy);
3410
3411       Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
3412       Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
3413
3414       switch (SrcI->getOpcode()) {
3415       case Instruction::Add:
3416       case Instruction::Mul:
3417       case Instruction::And:
3418       case Instruction::Or:
3419       case Instruction::Xor:
3420         // If we are discarding information, or just changing the sign, rewrite.
3421         if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
3422           // Don't insert two casts if they cannot be eliminated.  We allow two
3423           // casts to be inserted if the sizes are the same.  This could only be
3424           // converting signedness, which is a noop.
3425           if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy,TD) ||
3426               !ValueRequiresCast(Op0, DestTy, TD)) {
3427             Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3428             Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
3429             return BinaryOperator::create(cast<BinaryOperator>(SrcI)
3430                              ->getOpcode(), Op0c, Op1c);
3431           }
3432         }
3433         break;
3434       case Instruction::Shl:
3435         // Allow changing the sign of the source operand.  Do not allow changing
3436         // the size of the shift, UNLESS the shift amount is a constant.  We
3437         // mush not change variable sized shifts to a smaller size, because it
3438         // is undefined to shift more bits out than exist in the value.
3439         if (DestBitSize == SrcBitSize ||
3440             (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
3441           Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3442           return new ShiftInst(Instruction::Shl, Op0c, Op1);
3443         }
3444         break;
3445       }
3446     }
3447
3448   return 0;
3449 }
3450
3451 /// GetSelectFoldableOperands - We want to turn code that looks like this:
3452 ///   %C = or %A, %B
3453 ///   %D = select %cond, %C, %A
3454 /// into:
3455 ///   %C = select %cond, %B, 0
3456 ///   %D = or %A, %C
3457 ///
3458 /// Assuming that the specified instruction is an operand to the select, return
3459 /// a bitmask indicating which operands of this instruction are foldable if they
3460 /// equal the other incoming value of the select.
3461 ///
3462 static unsigned GetSelectFoldableOperands(Instruction *I) {
3463   switch (I->getOpcode()) {
3464   case Instruction::Add:
3465   case Instruction::Mul:
3466   case Instruction::And:
3467   case Instruction::Or:
3468   case Instruction::Xor:
3469     return 3;              // Can fold through either operand.
3470   case Instruction::Sub:   // Can only fold on the amount subtracted.
3471   case Instruction::Shl:   // Can only fold on the shift amount.
3472   case Instruction::Shr:
3473     return 1;
3474   default:
3475     return 0;              // Cannot fold
3476   }
3477 }
3478
3479 /// GetSelectFoldableConstant - For the same transformation as the previous
3480 /// function, return the identity constant that goes into the select.
3481 static Constant *GetSelectFoldableConstant(Instruction *I) {
3482   switch (I->getOpcode()) {
3483   default: assert(0 && "This cannot happen!"); abort();
3484   case Instruction::Add:
3485   case Instruction::Sub:
3486   case Instruction::Or:
3487   case Instruction::Xor:
3488     return Constant::getNullValue(I->getType());
3489   case Instruction::Shl:
3490   case Instruction::Shr:
3491     return Constant::getNullValue(Type::UByteTy);
3492   case Instruction::And:
3493     return ConstantInt::getAllOnesValue(I->getType());
3494   case Instruction::Mul:
3495     return ConstantInt::get(I->getType(), 1);
3496   }
3497 }
3498
3499 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
3500   Value *CondVal = SI.getCondition();
3501   Value *TrueVal = SI.getTrueValue();
3502   Value *FalseVal = SI.getFalseValue();
3503
3504   // select true, X, Y  -> X
3505   // select false, X, Y -> Y
3506   if (ConstantBool *C = dyn_cast<ConstantBool>(CondVal))
3507     if (C == ConstantBool::True)
3508       return ReplaceInstUsesWith(SI, TrueVal);
3509     else {
3510       assert(C == ConstantBool::False);
3511       return ReplaceInstUsesWith(SI, FalseVal);
3512     }
3513
3514   // select C, X, X -> X
3515   if (TrueVal == FalseVal)
3516     return ReplaceInstUsesWith(SI, TrueVal);
3517
3518   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
3519     return ReplaceInstUsesWith(SI, FalseVal);
3520   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
3521     return ReplaceInstUsesWith(SI, TrueVal);
3522   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
3523     if (isa<Constant>(TrueVal))
3524       return ReplaceInstUsesWith(SI, TrueVal);
3525     else
3526       return ReplaceInstUsesWith(SI, FalseVal);
3527   }
3528
3529   if (SI.getType() == Type::BoolTy)
3530     if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
3531       if (C == ConstantBool::True) {
3532         // Change: A = select B, true, C --> A = or B, C
3533         return BinaryOperator::createOr(CondVal, FalseVal);
3534       } else {
3535         // Change: A = select B, false, C --> A = and !B, C
3536         Value *NotCond =
3537           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3538                                              "not."+CondVal->getName()), SI);
3539         return BinaryOperator::createAnd(NotCond, FalseVal);
3540       }
3541     } else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) {
3542       if (C == ConstantBool::False) {
3543         // Change: A = select B, C, false --> A = and B, C
3544         return BinaryOperator::createAnd(CondVal, TrueVal);
3545       } else {
3546         // Change: A = select B, C, true --> A = or !B, C
3547         Value *NotCond =
3548           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3549                                              "not."+CondVal->getName()), SI);
3550         return BinaryOperator::createOr(NotCond, TrueVal);
3551       }
3552     }
3553
3554   // Selecting between two integer constants?
3555   if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal))
3556     if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) {
3557       // select C, 1, 0 -> cast C to int
3558       if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) {
3559         return new CastInst(CondVal, SI.getType());
3560       } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) {
3561         // select C, 0, 1 -> cast !C to int
3562         Value *NotCond =
3563           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3564                                                "not."+CondVal->getName()), SI);
3565         return new CastInst(NotCond, SI.getType());
3566       }
3567
3568       // If one of the constants is zero (we know they can't both be) and we
3569       // have a setcc instruction with zero, and we have an 'and' with the
3570       // non-constant value, eliminate this whole mess.  This corresponds to
3571       // cases like this: ((X & 27) ? 27 : 0)
3572       if (TrueValC->isNullValue() || FalseValC->isNullValue())
3573         if (Instruction *IC = dyn_cast<Instruction>(SI.getCondition()))
3574           if ((IC->getOpcode() == Instruction::SetEQ ||
3575                IC->getOpcode() == Instruction::SetNE) &&
3576               isa<ConstantInt>(IC->getOperand(1)) &&
3577               cast<Constant>(IC->getOperand(1))->isNullValue())
3578             if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0)))
3579               if (ICA->getOpcode() == Instruction::And &&
3580                   isa<ConstantInt>(ICA->getOperand(1)) &&
3581                   (ICA->getOperand(1) == TrueValC ||
3582                    ICA->getOperand(1) == FalseValC) &&
3583                   isOneBitSet(cast<ConstantInt>(ICA->getOperand(1)))) {
3584                 // Okay, now we know that everything is set up, we just don't
3585                 // know whether we have a setne or seteq and whether the true or
3586                 // false val is the zero.
3587                 bool ShouldNotVal = !TrueValC->isNullValue();
3588                 ShouldNotVal ^= IC->getOpcode() == Instruction::SetNE;
3589                 Value *V = ICA;
3590                 if (ShouldNotVal)
3591                   V = InsertNewInstBefore(BinaryOperator::create(
3592                                   Instruction::Xor, V, ICA->getOperand(1)), SI);
3593                 return ReplaceInstUsesWith(SI, V);
3594               }
3595     }
3596
3597   // See if we are selecting two values based on a comparison of the two values.
3598   if (SetCondInst *SCI = dyn_cast<SetCondInst>(CondVal)) {
3599     if (SCI->getOperand(0) == TrueVal && SCI->getOperand(1) == FalseVal) {
3600       // Transform (X == Y) ? X : Y  -> Y
3601       if (SCI->getOpcode() == Instruction::SetEQ)
3602         return ReplaceInstUsesWith(SI, FalseVal);
3603       // Transform (X != Y) ? X : Y  -> X
3604       if (SCI->getOpcode() == Instruction::SetNE)
3605         return ReplaceInstUsesWith(SI, TrueVal);
3606       // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
3607
3608     } else if (SCI->getOperand(0) == FalseVal && SCI->getOperand(1) == TrueVal){
3609       // Transform (X == Y) ? Y : X  -> X
3610       if (SCI->getOpcode() == Instruction::SetEQ)
3611         return ReplaceInstUsesWith(SI, FalseVal);
3612       // Transform (X != Y) ? Y : X  -> Y
3613       if (SCI->getOpcode() == Instruction::SetNE)
3614         return ReplaceInstUsesWith(SI, TrueVal);
3615       // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
3616     }
3617   }
3618
3619   // Turn select C, (X+Y), (X-Y) --> (X+(select C, Y, (-Y))).  This is legal for
3620   // FP as well.
3621   if (Instruction *TI = dyn_cast<Instruction>(TrueVal))
3622     if (Instruction *FI = dyn_cast<Instruction>(FalseVal))
3623       if (TI->hasOneUse() && FI->hasOneUse()) {
3624         bool isInverse = false;
3625         Instruction *AddOp = 0, *SubOp = 0;
3626
3627         if (TI->getOpcode() == Instruction::Sub &&
3628             FI->getOpcode() == Instruction::Add) {
3629           AddOp = FI; SubOp = TI;
3630         } else if (FI->getOpcode() == Instruction::Sub &&
3631                    TI->getOpcode() == Instruction::Add) {
3632           AddOp = TI; SubOp = FI;
3633         }
3634
3635         if (AddOp) {
3636           Value *OtherAddOp = 0;
3637           if (SubOp->getOperand(0) == AddOp->getOperand(0)) {
3638             OtherAddOp = AddOp->getOperand(1);
3639           } else if (SubOp->getOperand(0) == AddOp->getOperand(1)) {
3640             OtherAddOp = AddOp->getOperand(0);
3641           }
3642
3643           if (OtherAddOp) {
3644             // So at this point we know we have:
3645             //        select C, (add X, Y), (sub X, ?)
3646             // We can do the transform profitably if either 'Y' = '?' or '?' is
3647             // a constant.
3648             if (SubOp->getOperand(1) == AddOp ||
3649                 isa<Constant>(SubOp->getOperand(1))) {
3650               Value *NegVal;
3651               if (Constant *C = dyn_cast<Constant>(SubOp->getOperand(1))) {
3652                 NegVal = ConstantExpr::getNeg(C);
3653               } else {
3654                 NegVal = InsertNewInstBefore(
3655                            BinaryOperator::createNeg(SubOp->getOperand(1)), SI);
3656               }
3657
3658               Value *NewTrueOp = OtherAddOp;
3659               Value *NewFalseOp = NegVal;
3660               if (AddOp != TI)
3661                 std::swap(NewTrueOp, NewFalseOp);
3662               Instruction *NewSel =
3663                 new SelectInst(CondVal, NewTrueOp,NewFalseOp,SI.getName()+".p");
3664
3665               NewSel = InsertNewInstBefore(NewSel, SI);
3666               return BinaryOperator::createAdd(SubOp->getOperand(0), NewSel);
3667             }
3668           }
3669         }
3670       }
3671
3672   // See if we can fold the select into one of our operands.
3673   if (SI.getType()->isInteger()) {
3674     // See the comment above GetSelectFoldableOperands for a description of the
3675     // transformation we are doing here.
3676     if (Instruction *TVI = dyn_cast<Instruction>(TrueVal))
3677       if (TVI->hasOneUse() && TVI->getNumOperands() == 2 &&
3678           !isa<Constant>(FalseVal))
3679         if (unsigned SFO = GetSelectFoldableOperands(TVI)) {
3680           unsigned OpToFold = 0;
3681           if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
3682             OpToFold = 1;
3683           } else  if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
3684             OpToFold = 2;
3685           }
3686
3687           if (OpToFold) {
3688             Constant *C = GetSelectFoldableConstant(TVI);
3689             std::string Name = TVI->getName(); TVI->setName("");
3690             Instruction *NewSel =
3691               new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C,
3692                              Name);
3693             InsertNewInstBefore(NewSel, SI);
3694             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
3695               return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel);
3696             else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI))
3697               return new ShiftInst(SI->getOpcode(), FalseVal, NewSel);
3698             else {
3699               assert(0 && "Unknown instruction!!");
3700             }
3701           }
3702         }
3703
3704     if (Instruction *FVI = dyn_cast<Instruction>(FalseVal))
3705       if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
3706           !isa<Constant>(TrueVal))
3707         if (unsigned SFO = GetSelectFoldableOperands(FVI)) {
3708           unsigned OpToFold = 0;
3709           if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
3710             OpToFold = 1;
3711           } else  if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
3712             OpToFold = 2;
3713           }
3714
3715           if (OpToFold) {
3716             Constant *C = GetSelectFoldableConstant(FVI);
3717             std::string Name = FVI->getName(); FVI->setName("");
3718             Instruction *NewSel =
3719               new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold),
3720                              Name);
3721             InsertNewInstBefore(NewSel, SI);
3722             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
3723               return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel);
3724             else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI))
3725               return new ShiftInst(SI->getOpcode(), TrueVal, NewSel);
3726             else {
3727               assert(0 && "Unknown instruction!!");
3728             }
3729           }
3730         }
3731   }
3732   return 0;
3733 }
3734
3735
3736 // CallInst simplification
3737 //
3738 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
3739   // Intrinsics cannot occur in an invoke, so handle them here instead of in
3740   // visitCallSite.
3741   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&CI)) {
3742     bool Changed = false;
3743
3744     // memmove/cpy/set of zero bytes is a noop.
3745     if (Constant *NumBytes = dyn_cast<Constant>(MI->getLength())) {
3746       if (NumBytes->isNullValue()) return EraseInstFromFunction(CI);
3747
3748       // FIXME: Increase alignment here.
3749
3750       if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes))
3751         if (CI->getRawValue() == 1) {
3752           // Replace the instruction with just byte operations.  We would
3753           // transform other cases to loads/stores, but we don't know if
3754           // alignment is sufficient.
3755         }
3756     }
3757
3758     // If we have a memmove and the source operation is a constant global,
3759     // then the source and dest pointers can't alias, so we can change this
3760     // into a call to memcpy.
3761     if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI))
3762       if (GlobalVariable *GVSrc = dyn_cast<GlobalVariable>(MMI->getSource()))
3763         if (GVSrc->isConstant()) {
3764           Module *M = CI.getParent()->getParent()->getParent();
3765           Function *MemCpy = M->getOrInsertFunction("llvm.memcpy",
3766                                      CI.getCalledFunction()->getFunctionType());
3767           CI.setOperand(0, MemCpy);
3768           Changed = true;
3769         }
3770
3771     if (Changed) return &CI;
3772   } else if (DbgStopPointInst *SPI = dyn_cast<DbgStopPointInst>(&CI)) {
3773     // If this stoppoint is at the same source location as the previous
3774     // stoppoint in the chain, it is not needed.
3775     if (DbgStopPointInst *PrevSPI =
3776         dyn_cast<DbgStopPointInst>(SPI->getChain()))
3777       if (SPI->getLineNo() == PrevSPI->getLineNo() &&
3778           SPI->getColNo() == PrevSPI->getColNo()) {
3779         SPI->replaceAllUsesWith(PrevSPI);
3780         return EraseInstFromFunction(CI);
3781       }
3782   }
3783
3784   return visitCallSite(&CI);
3785 }
3786
3787 // InvokeInst simplification
3788 //
3789 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
3790   return visitCallSite(&II);
3791 }
3792
3793 // visitCallSite - Improvements for call and invoke instructions.
3794 //
3795 Instruction *InstCombiner::visitCallSite(CallSite CS) {
3796   bool Changed = false;
3797
3798   // If the callee is a constexpr cast of a function, attempt to move the cast
3799   // to the arguments of the call/invoke.
3800   if (transformConstExprCastCall(CS)) return 0;
3801
3802   Value *Callee = CS.getCalledValue();
3803
3804   if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
3805     // This instruction is not reachable, just remove it.  We insert a store to
3806     // undef so that we know that this code is not reachable, despite the fact
3807     // that we can't modify the CFG here.
3808     new StoreInst(ConstantBool::True,
3809                   UndefValue::get(PointerType::get(Type::BoolTy)),
3810                   CS.getInstruction());
3811
3812     if (!CS.getInstruction()->use_empty())
3813       CS.getInstruction()->
3814         replaceAllUsesWith(UndefValue::get(CS.getInstruction()->getType()));
3815
3816     if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
3817       // Don't break the CFG, insert a dummy cond branch.
3818       new BranchInst(II->getNormalDest(), II->getUnwindDest(),
3819                      ConstantBool::True, II);
3820     }
3821     return EraseInstFromFunction(*CS.getInstruction());
3822   }
3823
3824   const PointerType *PTy = cast<PointerType>(Callee->getType());
3825   const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
3826   if (FTy->isVarArg()) {
3827     // See if we can optimize any arguments passed through the varargs area of
3828     // the call.
3829     for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(),
3830            E = CS.arg_end(); I != E; ++I)
3831       if (CastInst *CI = dyn_cast<CastInst>(*I)) {
3832         // If this cast does not effect the value passed through the varargs
3833         // area, we can eliminate the use of the cast.
3834         Value *Op = CI->getOperand(0);
3835         if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) {
3836           *I = Op;
3837           Changed = true;
3838         }
3839       }
3840   }
3841
3842   return Changed ? CS.getInstruction() : 0;
3843 }
3844
3845 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
3846 // attempt to move the cast to the arguments of the call/invoke.
3847 //
3848 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
3849   if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
3850   ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
3851   if (CE->getOpcode() != Instruction::Cast || !isa<Function>(CE->getOperand(0)))
3852     return false;
3853   Function *Callee = cast<Function>(CE->getOperand(0));
3854   Instruction *Caller = CS.getInstruction();
3855
3856   // Okay, this is a cast from a function to a different type.  Unless doing so
3857   // would cause a type conversion of one of our arguments, change this call to
3858   // be a direct call with arguments casted to the appropriate types.
3859   //
3860   const FunctionType *FT = Callee->getFunctionType();
3861   const Type *OldRetTy = Caller->getType();
3862
3863   // Check to see if we are changing the return type...
3864   if (OldRetTy != FT->getReturnType()) {
3865     if (Callee->isExternal() &&
3866         !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) &&
3867         !Caller->use_empty())
3868       return false;   // Cannot transform this return value...
3869
3870     // If the callsite is an invoke instruction, and the return value is used by
3871     // a PHI node in a successor, we cannot change the return type of the call
3872     // because there is no place to put the cast instruction (without breaking
3873     // the critical edge).  Bail out in this case.
3874     if (!Caller->use_empty())
3875       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller))
3876         for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
3877              UI != E; ++UI)
3878           if (PHINode *PN = dyn_cast<PHINode>(*UI))
3879             if (PN->getParent() == II->getNormalDest() ||
3880                 PN->getParent() == II->getUnwindDest())
3881               return false;
3882   }
3883
3884   unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
3885   unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
3886
3887   CallSite::arg_iterator AI = CS.arg_begin();
3888   for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
3889     const Type *ParamTy = FT->getParamType(i);
3890     bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
3891     if (Callee->isExternal() && !isConvertible) return false;
3892   }
3893
3894   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
3895       Callee->isExternal())
3896     return false;   // Do not delete arguments unless we have a function body...
3897
3898   // Okay, we decided that this is a safe thing to do: go ahead and start
3899   // inserting cast instructions as necessary...
3900   std::vector<Value*> Args;
3901   Args.reserve(NumActualArgs);
3902
3903   AI = CS.arg_begin();
3904   for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
3905     const Type *ParamTy = FT->getParamType(i);
3906     if ((*AI)->getType() == ParamTy) {
3907       Args.push_back(*AI);
3908     } else {
3909       Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"),
3910                                          *Caller));
3911     }
3912   }
3913
3914   // If the function takes more arguments than the call was taking, add them
3915   // now...
3916   for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
3917     Args.push_back(Constant::getNullValue(FT->getParamType(i)));
3918
3919   // If we are removing arguments to the function, emit an obnoxious warning...
3920   if (FT->getNumParams() < NumActualArgs)
3921     if (!FT->isVarArg()) {
3922       std::cerr << "WARNING: While resolving call to function '"
3923                 << Callee->getName() << "' arguments were dropped!\n";
3924     } else {
3925       // Add all of the arguments in their promoted form to the arg list...
3926       for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
3927         const Type *PTy = getPromotedType((*AI)->getType());
3928         if (PTy != (*AI)->getType()) {
3929           // Must promote to pass through va_arg area!
3930           Instruction *Cast = new CastInst(*AI, PTy, "tmp");
3931           InsertNewInstBefore(Cast, *Caller);
3932           Args.push_back(Cast);
3933         } else {
3934           Args.push_back(*AI);
3935         }
3936       }
3937     }
3938
3939   if (FT->getReturnType() == Type::VoidTy)
3940     Caller->setName("");   // Void type should not have a name...
3941
3942   Instruction *NC;
3943   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
3944     NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
3945                         Args, Caller->getName(), Caller);
3946   } else {
3947     NC = new CallInst(Callee, Args, Caller->getName(), Caller);
3948   }
3949
3950   // Insert a cast of the return type as necessary...
3951   Value *NV = NC;
3952   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
3953     if (NV->getType() != Type::VoidTy) {
3954       NV = NC = new CastInst(NC, Caller->getType(), "tmp");
3955
3956       // If this is an invoke instruction, we should insert it after the first
3957       // non-phi, instruction in the normal successor block.
3958       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
3959         BasicBlock::iterator I = II->getNormalDest()->begin();
3960         while (isa<PHINode>(I)) ++I;
3961         InsertNewInstBefore(NC, *I);
3962       } else {
3963         // Otherwise, it's a call, just insert cast right after the call instr
3964         InsertNewInstBefore(NC, *Caller);
3965       }
3966       AddUsersToWorkList(*Caller);
3967     } else {
3968       NV = UndefValue::get(Caller->getType());
3969     }
3970   }
3971
3972   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
3973     Caller->replaceAllUsesWith(NV);
3974   Caller->getParent()->getInstList().erase(Caller);
3975   removeFromWorkList(Caller);
3976   return true;
3977 }
3978
3979
3980 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
3981 // operator and they all are only used by the PHI, PHI together their
3982 // inputs, and do the operation once, to the result of the PHI.
3983 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
3984   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
3985
3986   // Scan the instruction, looking for input operations that can be folded away.
3987   // If all input operands to the phi are the same instruction (e.g. a cast from
3988   // the same type or "+42") we can pull the operation through the PHI, reducing
3989   // code size and simplifying code.
3990   Constant *ConstantOp = 0;
3991   const Type *CastSrcTy = 0;
3992   if (isa<CastInst>(FirstInst)) {
3993     CastSrcTy = FirstInst->getOperand(0)->getType();
3994   } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst)) {
3995     // Can fold binop or shift if the RHS is a constant.
3996     ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
3997     if (ConstantOp == 0) return 0;
3998   } else {
3999     return 0;  // Cannot fold this operation.
4000   }
4001
4002   // Check to see if all arguments are the same operation.
4003   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
4004     if (!isa<Instruction>(PN.getIncomingValue(i))) return 0;
4005     Instruction *I = cast<Instruction>(PN.getIncomingValue(i));
4006     if (!I->hasOneUse() || I->getOpcode() != FirstInst->getOpcode())
4007       return 0;
4008     if (CastSrcTy) {
4009       if (I->getOperand(0)->getType() != CastSrcTy)
4010         return 0;  // Cast operation must match.
4011     } else if (I->getOperand(1) != ConstantOp) {
4012       return 0;
4013     }
4014   }
4015
4016   // Okay, they are all the same operation.  Create a new PHI node of the
4017   // correct type, and PHI together all of the LHS's of the instructions.
4018   PHINode *NewPN = new PHINode(FirstInst->getOperand(0)->getType(),
4019                                PN.getName()+".in");
4020   NewPN->op_reserve(PN.getNumOperands());
4021
4022   Value *InVal = FirstInst->getOperand(0);
4023   NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
4024
4025   // Add all operands to the new PHI.
4026   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
4027     Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
4028     if (NewInVal != InVal)
4029       InVal = 0;
4030     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
4031   }
4032
4033   Value *PhiVal;
4034   if (InVal) {
4035     // The new PHI unions all of the same values together.  This is really
4036     // common, so we handle it intelligently here for compile-time speed.
4037     PhiVal = InVal;
4038     delete NewPN;
4039   } else {
4040     InsertNewInstBefore(NewPN, PN);
4041     PhiVal = NewPN;
4042   }
4043
4044   // Insert and return the new operation.
4045   if (isa<CastInst>(FirstInst))
4046     return new CastInst(PhiVal, PN.getType());
4047   else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst))
4048     return BinaryOperator::create(BinOp->getOpcode(), PhiVal, ConstantOp);
4049   else
4050     return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(),
4051                          PhiVal, ConstantOp);
4052 }
4053
4054 /// DeadPHICycle - Return true if this PHI node is only used by a PHI node cycle
4055 /// that is dead.
4056 static bool DeadPHICycle(PHINode *PN, std::set<PHINode*> &PotentiallyDeadPHIs) {
4057   if (PN->use_empty()) return true;
4058   if (!PN->hasOneUse()) return false;
4059
4060   // Remember this node, and if we find the cycle, return.
4061   if (!PotentiallyDeadPHIs.insert(PN).second)
4062     return true;
4063
4064   if (PHINode *PU = dyn_cast<PHINode>(PN->use_back()))
4065     return DeadPHICycle(PU, PotentiallyDeadPHIs);
4066
4067   return false;
4068 }
4069
4070 // PHINode simplification
4071 //
4072 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
4073   if (Value *V = hasConstantValue(&PN)) {
4074     // If V is an instruction, we have to be certain that it dominates PN.
4075     // However, because we don't have dom info, we can't do a perfect job.
4076     if (Instruction *I = dyn_cast<Instruction>(V)) {
4077       // We know that the instruction dominates the PHI if there are no undef
4078       // values coming in.
4079       if (I->getParent() != &I->getParent()->getParent()->front() ||
4080           isa<InvokeInst>(I))
4081         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
4082           if (isa<UndefValue>(PN.getIncomingValue(i))) {
4083             V = 0;
4084             break;
4085           }
4086     }
4087
4088     if (V)
4089       return ReplaceInstUsesWith(PN, V);
4090   }
4091
4092   // If the only user of this instruction is a cast instruction, and all of the
4093   // incoming values are constants, change this PHI to merge together the casted
4094   // constants.
4095   if (PN.hasOneUse())
4096     if (CastInst *CI = dyn_cast<CastInst>(PN.use_back()))
4097       if (CI->getType() != PN.getType()) {  // noop casts will be folded
4098         bool AllConstant = true;
4099         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
4100           if (!isa<Constant>(PN.getIncomingValue(i))) {
4101             AllConstant = false;
4102             break;
4103           }
4104         if (AllConstant) {
4105           // Make a new PHI with all casted values.
4106           PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN);
4107           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
4108             Constant *OldArg = cast<Constant>(PN.getIncomingValue(i));
4109             New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()),
4110                              PN.getIncomingBlock(i));
4111           }
4112
4113           // Update the cast instruction.
4114           CI->setOperand(0, New);
4115           WorkList.push_back(CI);    // revisit the cast instruction to fold.
4116           WorkList.push_back(New);   // Make sure to revisit the new Phi
4117           return &PN;                // PN is now dead!
4118         }
4119       }
4120
4121   // If all PHI operands are the same operation, pull them through the PHI,
4122   // reducing code size.
4123   if (isa<Instruction>(PN.getIncomingValue(0)) &&
4124       PN.getIncomingValue(0)->hasOneUse())
4125     if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
4126       return Result;
4127
4128   // If this is a trivial cycle in the PHI node graph, remove it.  Basically, if
4129   // this PHI only has a single use (a PHI), and if that PHI only has one use (a
4130   // PHI)... break the cycle.
4131   if (PN.hasOneUse())
4132     if (PHINode *PU = dyn_cast<PHINode>(PN.use_back())) {
4133       std::set<PHINode*> PotentiallyDeadPHIs;
4134       PotentiallyDeadPHIs.insert(&PN);
4135       if (DeadPHICycle(PU, PotentiallyDeadPHIs))
4136         return ReplaceInstUsesWith(PN, UndefValue::get(PN.getType()));
4137     }
4138
4139   return 0;
4140 }
4141
4142 static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy,
4143                                       Instruction *InsertPoint,
4144                                       InstCombiner *IC) {
4145   unsigned PS = IC->getTargetData().getPointerSize();
4146   const Type *VTy = V->getType();
4147   if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS)
4148     // We must insert a cast to ensure we sign-extend.
4149     V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(),
4150                                              V->getName()), *InsertPoint);
4151   return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()),
4152                                  *InsertPoint);
4153 }
4154
4155
4156 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
4157   Value *PtrOp = GEP.getOperand(0);
4158   // Is it 'getelementptr %P, long 0'  or 'getelementptr %P'
4159   // If so, eliminate the noop.
4160   if (GEP.getNumOperands() == 1)
4161     return ReplaceInstUsesWith(GEP, PtrOp);
4162
4163   if (isa<UndefValue>(GEP.getOperand(0)))
4164     return ReplaceInstUsesWith(GEP, UndefValue::get(GEP.getType()));
4165
4166   bool HasZeroPointerIndex = false;
4167   if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
4168     HasZeroPointerIndex = C->isNullValue();
4169
4170   if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
4171     return ReplaceInstUsesWith(GEP, PtrOp);
4172
4173   // Eliminate unneeded casts for indices.
4174   bool MadeChange = false;
4175   gep_type_iterator GTI = gep_type_begin(GEP);
4176   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI)
4177     if (isa<SequentialType>(*GTI)) {
4178       if (CastInst *CI = dyn_cast<CastInst>(GEP.getOperand(i))) {
4179         Value *Src = CI->getOperand(0);
4180         const Type *SrcTy = Src->getType();
4181         const Type *DestTy = CI->getType();
4182         if (Src->getType()->isInteger()) {
4183           if (SrcTy->getPrimitiveSize() == DestTy->getPrimitiveSize()) {
4184             // We can always eliminate a cast from ulong or long to the other.
4185             // We can always eliminate a cast from uint to int or the other on
4186             // 32-bit pointer platforms.
4187             if (DestTy->getPrimitiveSize() >= TD->getPointerSize()) {
4188               MadeChange = true;
4189               GEP.setOperand(i, Src);
4190             }
4191           } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
4192                      SrcTy->getPrimitiveSize() == 4) {
4193             // We can always eliminate a cast from int to [u]long.  We can
4194             // eliminate a cast from uint to [u]long iff the target is a 32-bit
4195             // pointer target.
4196             if (SrcTy->isSigned() ||
4197                 SrcTy->getPrimitiveSize() >= TD->getPointerSize()) {
4198               MadeChange = true;
4199               GEP.setOperand(i, Src);
4200             }
4201           }
4202         }
4203       }
4204       // If we are using a wider index than needed for this platform, shrink it
4205       // to what we need.  If the incoming value needs a cast instruction,
4206       // insert it.  This explicit cast can make subsequent optimizations more
4207       // obvious.
4208       Value *Op = GEP.getOperand(i);
4209       if (Op->getType()->getPrimitiveSize() > TD->getPointerSize())
4210         if (Constant *C = dyn_cast<Constant>(Op)) {
4211           GEP.setOperand(i, ConstantExpr::getCast(C,
4212                                      TD->getIntPtrType()->getSignedVersion()));
4213           MadeChange = true;
4214         } else {
4215           Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(),
4216                                                 Op->getName()), GEP);
4217           GEP.setOperand(i, Op);
4218           MadeChange = true;
4219         }
4220
4221       // If this is a constant idx, make sure to canonicalize it to be a signed
4222       // operand, otherwise CSE and other optimizations are pessimized.
4223       if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op)) {
4224         GEP.setOperand(i, ConstantExpr::getCast(CUI,
4225                                           CUI->getType()->getSignedVersion()));
4226         MadeChange = true;
4227       }
4228     }
4229   if (MadeChange) return &GEP;
4230
4231   // Combine Indices - If the source pointer to this getelementptr instruction
4232   // is a getelementptr instruction, combine the indices of the two
4233   // getelementptr instructions into a single instruction.
4234   //
4235   std::vector<Value*> SrcGEPOperands;
4236   if (User *Src = dyn_castGetElementPtr(PtrOp))
4237     SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
4238
4239   if (!SrcGEPOperands.empty()) {
4240     // Note that if our source is a gep chain itself that we wait for that
4241     // chain to be resolved before we perform this transformation.  This
4242     // avoids us creating a TON of code in some cases.
4243     //
4244     if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
4245         cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
4246       return 0;   // Wait until our source is folded to completion.
4247
4248     std::vector<Value *> Indices;
4249
4250     // Find out whether the last index in the source GEP is a sequential idx.
4251     bool EndsWithSequential = false;
4252     for (gep_type_iterator I = gep_type_begin(*cast<User>(PtrOp)),
4253            E = gep_type_end(*cast<User>(PtrOp)); I != E; ++I)
4254       EndsWithSequential = !isa<StructType>(*I);
4255
4256     // Can we combine the two pointer arithmetics offsets?
4257     if (EndsWithSequential) {
4258       // Replace: gep (gep %P, long B), long A, ...
4259       // With:    T = long A+B; gep %P, T, ...
4260       //
4261       Value *Sum, *SO1 = SrcGEPOperands.back(), *GO1 = GEP.getOperand(1);
4262       if (SO1 == Constant::getNullValue(SO1->getType())) {
4263         Sum = GO1;
4264       } else if (GO1 == Constant::getNullValue(GO1->getType())) {
4265         Sum = SO1;
4266       } else {
4267         // If they aren't the same type, convert both to an integer of the
4268         // target's pointer size.
4269         if (SO1->getType() != GO1->getType()) {
4270           if (Constant *SO1C = dyn_cast<Constant>(SO1)) {
4271             SO1 = ConstantExpr::getCast(SO1C, GO1->getType());
4272           } else if (Constant *GO1C = dyn_cast<Constant>(GO1)) {
4273             GO1 = ConstantExpr::getCast(GO1C, SO1->getType());
4274           } else {
4275             unsigned PS = TD->getPointerSize();
4276             if (SO1->getType()->getPrimitiveSize() == PS) {
4277               // Convert GO1 to SO1's type.
4278               GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this);
4279
4280             } else if (GO1->getType()->getPrimitiveSize() == PS) {
4281               // Convert SO1 to GO1's type.
4282               SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this);
4283             } else {
4284               const Type *PT = TD->getIntPtrType();
4285               SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this);
4286               GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this);
4287             }
4288           }
4289         }
4290         if (isa<Constant>(SO1) && isa<Constant>(GO1))
4291           Sum = ConstantExpr::getAdd(cast<Constant>(SO1), cast<Constant>(GO1));
4292         else {
4293           Sum = BinaryOperator::createAdd(SO1, GO1, PtrOp->getName()+".sum");
4294           InsertNewInstBefore(cast<Instruction>(Sum), GEP);
4295         }
4296       }
4297
4298       // Recycle the GEP we already have if possible.
4299       if (SrcGEPOperands.size() == 2) {
4300         GEP.setOperand(0, SrcGEPOperands[0]);
4301         GEP.setOperand(1, Sum);
4302         return &GEP;
4303       } else {
4304         Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4305                        SrcGEPOperands.end()-1);
4306         Indices.push_back(Sum);
4307         Indices.insert(Indices.end(), GEP.op_begin()+2, GEP.op_end());
4308       }
4309     } else if (isa<Constant>(*GEP.idx_begin()) &&
4310                cast<Constant>(*GEP.idx_begin())->isNullValue() &&
4311                SrcGEPOperands.size() != 1) {
4312       // Otherwise we can do the fold if the first index of the GEP is a zero
4313       Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4314                      SrcGEPOperands.end());
4315       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
4316     }
4317
4318     if (!Indices.empty())
4319       return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
4320
4321   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
4322     // GEP of global variable.  If all of the indices for this GEP are
4323     // constants, we can promote this to a constexpr instead of an instruction.
4324
4325     // Scan for nonconstants...
4326     std::vector<Constant*> Indices;
4327     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
4328     for (; I != E && isa<Constant>(*I); ++I)
4329       Indices.push_back(cast<Constant>(*I));
4330
4331     if (I == E) {  // If they are all constants...
4332       Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices);
4333
4334       // Replace all uses of the GEP with the new constexpr...
4335       return ReplaceInstUsesWith(GEP, CE);
4336     }
4337   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) {
4338     if (CE->getOpcode() == Instruction::Cast) {
4339       if (HasZeroPointerIndex) {
4340         // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
4341         // into     : GEP [10 x ubyte]* X, long 0, ...
4342         //
4343         // This occurs when the program declares an array extern like "int X[];"
4344         //
4345         Constant *X = CE->getOperand(0);
4346         const PointerType *CPTy = cast<PointerType>(CE->getType());
4347         if (const PointerType *XTy = dyn_cast<PointerType>(X->getType()))
4348           if (const ArrayType *XATy =
4349               dyn_cast<ArrayType>(XTy->getElementType()))
4350             if (const ArrayType *CATy =
4351                 dyn_cast<ArrayType>(CPTy->getElementType()))
4352               if (CATy->getElementType() == XATy->getElementType()) {
4353                 // At this point, we know that the cast source type is a pointer
4354                 // to an array of the same type as the destination pointer
4355                 // array.  Because the array type is never stepped over (there
4356                 // is a leading zero) we can fold the cast into this GEP.
4357                 GEP.setOperand(0, X);
4358                 return &GEP;
4359               }
4360       } else if (GEP.getNumOperands() == 2 &&
4361                  isa<PointerType>(CE->getOperand(0)->getType())) {
4362         // Transform things like:
4363         // %t = getelementptr ubyte* cast ([2 x sbyte]* %str to ubyte*), uint %V
4364         // into:  %t1 = getelementptr [2 x sbyte*]* %str, int 0, uint %V; cast
4365         Constant *X = CE->getOperand(0);
4366         const Type *SrcElTy = cast<PointerType>(X->getType())->getElementType();
4367         const Type *ResElTy =cast<PointerType>(CE->getType())->getElementType();
4368         if (isa<ArrayType>(SrcElTy) &&
4369             TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) ==
4370             TD->getTypeSize(ResElTy)) {
4371           Value *V = InsertNewInstBefore(
4372                  new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy),
4373                                        GEP.getOperand(1), GEP.getName()), GEP);
4374           return new CastInst(V, GEP.getType());
4375         }
4376       }
4377     }
4378   }
4379
4380   return 0;
4381 }
4382
4383 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
4384   // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
4385   if (AI.isArrayAllocation())    // Check C != 1
4386     if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
4387       const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
4388       AllocationInst *New = 0;
4389
4390       // Create and insert the replacement instruction...
4391       if (isa<MallocInst>(AI))
4392         New = new MallocInst(NewTy, 0, AI.getName());
4393       else {
4394         assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
4395         New = new AllocaInst(NewTy, 0, AI.getName());
4396       }
4397
4398       InsertNewInstBefore(New, AI);
4399
4400       // Scan to the end of the allocation instructions, to skip over a block of
4401       // allocas if possible...
4402       //
4403       BasicBlock::iterator It = New;
4404       while (isa<AllocationInst>(*It)) ++It;
4405
4406       // Now that I is pointing to the first non-allocation-inst in the block,
4407       // insert our getelementptr instruction...
4408       //
4409       std::vector<Value*> Idx(2, Constant::getNullValue(Type::IntTy));
4410       Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
4411
4412       // Now make everything use the getelementptr instead of the original
4413       // allocation.
4414       return ReplaceInstUsesWith(AI, V);
4415     } else if (isa<UndefValue>(AI.getArraySize())) {
4416       return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4417     }
4418
4419   // If alloca'ing a zero byte object, replace the alloca with a null pointer.
4420   // Note that we only do this for alloca's, because malloc should allocate and
4421   // return a unique pointer, even for a zero byte allocation.
4422   if (isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized() &&
4423       TD->getTypeSize(AI.getAllocatedType()) == 0)
4424     return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4425
4426   return 0;
4427 }
4428
4429 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) {
4430   Value *Op = FI.getOperand(0);
4431
4432   // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X
4433   if (CastInst *CI = dyn_cast<CastInst>(Op))
4434     if (isa<PointerType>(CI->getOperand(0)->getType())) {
4435       FI.setOperand(0, CI->getOperand(0));
4436       return &FI;
4437     }
4438
4439   // free undef -> unreachable.
4440   if (isa<UndefValue>(Op)) {
4441     // Insert a new store to null because we cannot modify the CFG here.
4442     new StoreInst(ConstantBool::True,
4443                   UndefValue::get(PointerType::get(Type::BoolTy)), &FI);
4444     return EraseInstFromFunction(FI);
4445   }
4446
4447   // If we have 'free null' delete the instruction.  This can happen in stl code
4448   // when lots of inlining happens.
4449   if (isa<ConstantPointerNull>(Op))
4450     return EraseInstFromFunction(FI);
4451
4452   return 0;
4453 }
4454
4455
4456 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
4457 /// constantexpr, return the constant value being addressed by the constant
4458 /// expression, or null if something is funny.
4459 ///
4460 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
4461   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
4462     return 0;  // Do not allow stepping over the value!
4463
4464   // Loop over all of the operands, tracking down which value we are
4465   // addressing...
4466   gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
4467   for (++I; I != E; ++I)
4468     if (const StructType *STy = dyn_cast<StructType>(*I)) {
4469       ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
4470       assert(CU->getValue() < STy->getNumElements() &&
4471              "Struct index out of range!");
4472       unsigned El = (unsigned)CU->getValue();
4473       if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
4474         C = CS->getOperand(El);
4475       } else if (isa<ConstantAggregateZero>(C)) {
4476         C = Constant::getNullValue(STy->getElementType(El));
4477       } else if (isa<UndefValue>(C)) {
4478         C = UndefValue::get(STy->getElementType(El));
4479       } else {
4480         return 0;
4481       }
4482     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
4483       const ArrayType *ATy = cast<ArrayType>(*I);
4484       if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
4485       if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
4486         C = CA->getOperand((unsigned)CI->getRawValue());
4487       else if (isa<ConstantAggregateZero>(C))
4488         C = Constant::getNullValue(ATy->getElementType());
4489       else if (isa<UndefValue>(C))
4490         C = UndefValue::get(ATy->getElementType());
4491       else
4492         return 0;
4493     } else {
4494       return 0;
4495     }
4496   return C;
4497 }
4498
4499 static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
4500   User *CI = cast<User>(LI.getOperand(0));
4501
4502   const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
4503   if (const PointerType *SrcTy =
4504       dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
4505     const Type *SrcPTy = SrcTy->getElementType();
4506     if (SrcPTy->isSized() && DestPTy->isSized() &&
4507         IC.getTargetData().getTypeSize(SrcPTy) ==
4508             IC.getTargetData().getTypeSize(DestPTy) &&
4509         (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
4510         (DestPTy->isInteger() || isa<PointerType>(DestPTy))) {
4511       // Okay, we are casting from one integer or pointer type to another of
4512       // the same size.  Instead of casting the pointer before the load, cast
4513       // the result of the loaded value.
4514       Value *NewLoad = IC.InsertNewInstBefore(new LoadInst(CI->getOperand(0),
4515                                                            CI->getName(),
4516                                                            LI.isVolatile()),LI);
4517       // Now cast the result of the load.
4518       return new CastInst(NewLoad, LI.getType());
4519     }
4520   }
4521   return 0;
4522 }
4523
4524 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
4525 /// from this value cannot trap.  If it is not obviously safe to load from the
4526 /// specified pointer, we do a quick local scan of the basic block containing
4527 /// ScanFrom, to determine if the address is already accessed.
4528 static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
4529   // If it is an alloca or global variable, it is always safe to load from.
4530   if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
4531
4532   // Otherwise, be a little bit agressive by scanning the local block where we
4533   // want to check to see if the pointer is already being loaded or stored
4534   // from/to.  If so, the previous load or store would have already trapped,
4535   // so there is no harm doing an extra load (also, CSE will later eliminate
4536   // the load entirely).
4537   BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
4538
4539   while (BBI != E) {
4540     --BBI;
4541
4542     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
4543       if (LI->getOperand(0) == V) return true;
4544     } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
4545       if (SI->getOperand(1) == V) return true;
4546
4547   }
4548   return false;
4549 }
4550
4551 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
4552   Value *Op = LI.getOperand(0);
4553
4554   if (Constant *C = dyn_cast<Constant>(Op)) {
4555     if ((C->isNullValue() || isa<UndefValue>(C)) &&
4556         !LI.isVolatile()) {                          // load null/undef -> undef
4557       // Insert a new store to null instruction before the load to indicate that
4558       // this code is not reachable.  We do this instead of inserting an
4559       // unreachable instruction directly because we cannot modify the CFG.
4560       new StoreInst(UndefValue::get(LI.getType()), C, &LI);
4561       return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
4562     }
4563
4564     // Instcombine load (constant global) into the value loaded.
4565     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
4566       if (GV->isConstant() && !GV->isExternal())
4567         return ReplaceInstUsesWith(LI, GV->getInitializer());
4568
4569     // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded.
4570     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
4571       if (CE->getOpcode() == Instruction::GetElementPtr) {
4572         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
4573           if (GV->isConstant() && !GV->isExternal())
4574             if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
4575               return ReplaceInstUsesWith(LI, V);
4576       } else if (CE->getOpcode() == Instruction::Cast) {
4577         if (Instruction *Res = InstCombineLoadCast(*this, LI))
4578           return Res;
4579       }
4580   }
4581
4582   // load (cast X) --> cast (load X) iff safe
4583   if (CastInst *CI = dyn_cast<CastInst>(Op))
4584     if (Instruction *Res = InstCombineLoadCast(*this, LI))
4585       return Res;
4586
4587   if (!LI.isVolatile() && Op->hasOneUse()) {
4588     // Change select and PHI nodes to select values instead of addresses: this
4589     // helps alias analysis out a lot, allows many others simplifications, and
4590     // exposes redundancy in the code.
4591     //
4592     // Note that we cannot do the transformation unless we know that the
4593     // introduced loads cannot trap!  Something like this is valid as long as
4594     // the condition is always false: load (select bool %C, int* null, int* %G),
4595     // but it would not be valid if we transformed it to load from null
4596     // unconditionally.
4597     //
4598     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
4599       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
4600       if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) &&
4601           isSafeToLoadUnconditionally(SI->getOperand(2), SI)) {
4602         Value *V1 = InsertNewInstBefore(new LoadInst(SI->getOperand(1),
4603                                      SI->getOperand(1)->getName()+".val"), LI);
4604         Value *V2 = InsertNewInstBefore(new LoadInst(SI->getOperand(2),
4605                                      SI->getOperand(2)->getName()+".val"), LI);
4606         return new SelectInst(SI->getCondition(), V1, V2);
4607       }
4608
4609       // load (select (cond, null, P)) -> load P
4610       if (Constant *C = dyn_cast<Constant>(SI->getOperand(1)))
4611         if (C->isNullValue()) {
4612           LI.setOperand(0, SI->getOperand(2));
4613           return &LI;
4614         }
4615
4616       // load (select (cond, P, null)) -> load P
4617       if (Constant *C = dyn_cast<Constant>(SI->getOperand(2)))
4618         if (C->isNullValue()) {
4619           LI.setOperand(0, SI->getOperand(1));
4620           return &LI;
4621         }
4622
4623     } else if (PHINode *PN = dyn_cast<PHINode>(Op)) {
4624       // load (phi (&V1, &V2, &V3))  --> phi(load &V1, load &V2, load &V3)
4625       bool Safe = PN->getParent() == LI.getParent();
4626
4627       // Scan all of the instructions between the PHI and the load to make
4628       // sure there are no instructions that might possibly alter the value
4629       // loaded from the PHI.
4630       if (Safe) {
4631         BasicBlock::iterator I = &LI;
4632         for (--I; !isa<PHINode>(I); --I)
4633           if (isa<StoreInst>(I) || isa<CallInst>(I)) {
4634             Safe = false;
4635             break;
4636           }
4637       }
4638
4639       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e && Safe; ++i)
4640         if (!isSafeToLoadUnconditionally(PN->getIncomingValue(i),
4641                                     PN->getIncomingBlock(i)->getTerminator()))
4642           Safe = false;
4643
4644       if (Safe) {
4645         // Create the PHI.
4646         PHINode *NewPN = new PHINode(LI.getType(), PN->getName());
4647         InsertNewInstBefore(NewPN, *PN);
4648         std::map<BasicBlock*,Value*> LoadMap;  // Don't insert duplicate loads
4649
4650         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
4651           BasicBlock *BB = PN->getIncomingBlock(i);
4652           Value *&TheLoad = LoadMap[BB];
4653           if (TheLoad == 0) {
4654             Value *InVal = PN->getIncomingValue(i);
4655             TheLoad = InsertNewInstBefore(new LoadInst(InVal,
4656                                                        InVal->getName()+".val"),
4657                                           *BB->getTerminator());
4658           }
4659           NewPN->addIncoming(TheLoad, BB);
4660         }
4661         return ReplaceInstUsesWith(LI, NewPN);
4662       }
4663     }
4664   }
4665   return 0;
4666 }
4667
4668 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
4669   // Change br (not X), label True, label False to: br X, label False, True
4670   Value *X;
4671   BasicBlock *TrueDest;
4672   BasicBlock *FalseDest;
4673   if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
4674       !isa<Constant>(X)) {
4675     // Swap Destinations and condition...
4676     BI.setCondition(X);
4677     BI.setSuccessor(0, FalseDest);
4678     BI.setSuccessor(1, TrueDest);
4679     return &BI;
4680   }
4681
4682   // Cannonicalize setne -> seteq
4683   Instruction::BinaryOps Op; Value *Y;
4684   if (match(&BI, m_Br(m_SetCond(Op, m_Value(X), m_Value(Y)),
4685                       TrueDest, FalseDest)))
4686     if ((Op == Instruction::SetNE || Op == Instruction::SetLE ||
4687          Op == Instruction::SetGE) && BI.getCondition()->hasOneUse()) {
4688       SetCondInst *I = cast<SetCondInst>(BI.getCondition());
4689       std::string Name = I->getName(); I->setName("");
4690       Instruction::BinaryOps NewOpcode = SetCondInst::getInverseCondition(Op);
4691       Value *NewSCC =  BinaryOperator::create(NewOpcode, X, Y, Name, I);
4692       // Swap Destinations and condition...
4693       BI.setCondition(NewSCC);
4694       BI.setSuccessor(0, FalseDest);
4695       BI.setSuccessor(1, TrueDest);
4696       removeFromWorkList(I);
4697       I->getParent()->getInstList().erase(I);
4698       WorkList.push_back(cast<Instruction>(NewSCC));
4699       return &BI;
4700     }
4701
4702   return 0;
4703 }
4704
4705 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
4706   Value *Cond = SI.getCondition();
4707   if (Instruction *I = dyn_cast<Instruction>(Cond)) {
4708     if (I->getOpcode() == Instruction::Add)
4709       if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
4710         // change 'switch (X+4) case 1:' into 'switch (X) case -3'
4711         for (unsigned i = 2, e = SI.getNumOperands(); i != e; i += 2)
4712           SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
4713                                                 AddRHS));
4714         SI.setOperand(0, I->getOperand(0));
4715         WorkList.push_back(I);
4716         return &SI;
4717       }
4718   }
4719   return 0;
4720 }
4721
4722
4723 void InstCombiner::removeFromWorkList(Instruction *I) {
4724   WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
4725                  WorkList.end());
4726 }
4727
4728
4729 /// TryToSinkInstruction - Try to move the specified instruction from its
4730 /// current block into the beginning of DestBlock, which can only happen if it's
4731 /// safe to move the instruction past all of the instructions between it and the
4732 /// end of its block.
4733 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
4734   assert(I->hasOneUse() && "Invariants didn't hold!");
4735
4736   // Cannot move control-flow-involving instructions.
4737   if (isa<PHINode>(I) || isa<InvokeInst>(I) || isa<CallInst>(I)) return false;
4738
4739   // Do not sink alloca instructions out of the entry block.
4740   if (isa<AllocaInst>(I) && I->getParent() == &DestBlock->getParent()->front())
4741     return false;
4742
4743   // We can only sink load instructions if there is nothing between the load and
4744   // the end of block that could change the value.
4745   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
4746     if (LI->isVolatile()) return false;  // Don't sink volatile loads.
4747
4748     for (BasicBlock::iterator Scan = LI, E = LI->getParent()->end();
4749          Scan != E; ++Scan)
4750       if (Scan->mayWriteToMemory())
4751         return false;
4752   }
4753
4754   BasicBlock::iterator InsertPos = DestBlock->begin();
4755   while (isa<PHINode>(InsertPos)) ++InsertPos;
4756
4757   BasicBlock *SrcBlock = I->getParent();
4758   DestBlock->getInstList().splice(InsertPos, SrcBlock->getInstList(), I);
4759   ++NumSunkInst;
4760   return true;
4761 }
4762
4763 bool InstCombiner::runOnFunction(Function &F) {
4764   bool Changed = false;
4765   TD = &getAnalysis<TargetData>();
4766
4767   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)
4768     WorkList.push_back(&*i);
4769
4770
4771   while (!WorkList.empty()) {
4772     Instruction *I = WorkList.back();  // Get an instruction from the worklist
4773     WorkList.pop_back();
4774
4775     // Check to see if we can DCE or ConstantPropagate the instruction...
4776     // Check to see if we can DIE the instruction...
4777     if (isInstructionTriviallyDead(I)) {
4778       // Add operands to the worklist...
4779       if (I->getNumOperands() < 4)
4780         AddUsesToWorkList(*I);
4781       ++NumDeadInst;
4782
4783       I->getParent()->getInstList().erase(I);
4784       removeFromWorkList(I);
4785       continue;
4786     }
4787
4788     // Instruction isn't dead, see if we can constant propagate it...
4789     if (Constant *C = ConstantFoldInstruction(I)) {
4790       Value* Ptr = I->getOperand(0);
4791       if (isa<GetElementPtrInst>(I) &&
4792           cast<Constant>(Ptr)->isNullValue() &&
4793           !isa<ConstantPointerNull>(C) &&
4794           cast<PointerType>(Ptr->getType())->getElementType()->isSized()) {
4795         // If this is a constant expr gep that is effectively computing an
4796         // "offsetof", fold it into 'cast int X to T*' instead of 'gep 0, 0, 12'
4797         bool isFoldableGEP = true;
4798         for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
4799           if (!isa<ConstantInt>(I->getOperand(i)))
4800             isFoldableGEP = false;
4801         if (isFoldableGEP) {
4802           uint64_t Offset = TD->getIndexedOffset(Ptr->getType(),
4803                              std::vector<Value*>(I->op_begin()+1, I->op_end()));
4804           C = ConstantUInt::get(Type::ULongTy, Offset);
4805           C = ConstantExpr::getCast(C, TD->getIntPtrType());
4806           C = ConstantExpr::getCast(C, I->getType());
4807         }
4808       }
4809
4810       // Add operands to the worklist...
4811       AddUsesToWorkList(*I);
4812       ReplaceInstUsesWith(*I, C);
4813
4814       ++NumConstProp;
4815       I->getParent()->getInstList().erase(I);
4816       removeFromWorkList(I);
4817       continue;
4818     }
4819
4820     // See if we can trivially sink this instruction to a successor basic block.
4821     if (I->hasOneUse()) {
4822       BasicBlock *BB = I->getParent();
4823       BasicBlock *UserParent = cast<Instruction>(I->use_back())->getParent();
4824       if (UserParent != BB) {
4825         bool UserIsSuccessor = false;
4826         // See if the user is one of our successors.
4827         for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
4828           if (*SI == UserParent) {
4829             UserIsSuccessor = true;
4830             break;
4831           }
4832
4833         // If the user is one of our immediate successors, and if that successor
4834         // only has us as a predecessors (we'd have to split the critical edge
4835         // otherwise), we can keep going.
4836         if (UserIsSuccessor && !isa<PHINode>(I->use_back()) &&
4837             next(pred_begin(UserParent)) == pred_end(UserParent))
4838           // Okay, the CFG is simple enough, try to sink this instruction.
4839           Changed |= TryToSinkInstruction(I, UserParent);
4840       }
4841     }
4842
4843     // Now that we have an instruction, try combining it to simplify it...
4844     if (Instruction *Result = visit(*I)) {
4845       ++NumCombined;
4846       // Should we replace the old instruction with a new one?
4847       if (Result != I) {
4848         DEBUG(std::cerr << "IC: Old = " << *I
4849                         << "    New = " << *Result);
4850
4851         // Everything uses the new instruction now.
4852         I->replaceAllUsesWith(Result);
4853
4854         // Push the new instruction and any users onto the worklist.
4855         WorkList.push_back(Result);
4856         AddUsersToWorkList(*Result);
4857
4858         // Move the name to the new instruction first...
4859         std::string OldName = I->getName(); I->setName("");
4860         Result->setName(OldName);
4861
4862         // Insert the new instruction into the basic block...
4863         BasicBlock *InstParent = I->getParent();
4864         BasicBlock::iterator InsertPos = I;
4865
4866         if (!isa<PHINode>(Result))        // If combining a PHI, don't insert
4867           while (isa<PHINode>(InsertPos)) // middle of a block of PHIs.
4868             ++InsertPos;
4869
4870         InstParent->getInstList().insert(InsertPos, Result);
4871
4872         // Make sure that we reprocess all operands now that we reduced their
4873         // use counts.
4874         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
4875           if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
4876             WorkList.push_back(OpI);
4877
4878         // Instructions can end up on the worklist more than once.  Make sure
4879         // we do not process an instruction that has been deleted.
4880         removeFromWorkList(I);
4881
4882         // Erase the old instruction.
4883         InstParent->getInstList().erase(I);
4884       } else {
4885         DEBUG(std::cerr << "IC: MOD = " << *I);
4886
4887         // If the instruction was modified, it's possible that it is now dead.
4888         // if so, remove it.
4889         if (isInstructionTriviallyDead(I)) {
4890           // Make sure we process all operands now that we are reducing their
4891           // use counts.
4892           for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
4893             if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
4894               WorkList.push_back(OpI);
4895
4896           // Instructions may end up in the worklist more than once.  Erase all
4897           // occurrances of this instruction.
4898           removeFromWorkList(I);
4899           I->getParent()->getInstList().erase(I);
4900         } else {
4901           WorkList.push_back(Result);
4902           AddUsersToWorkList(*Result);
4903         }
4904       }
4905       Changed = true;
4906     }
4907   }
4908
4909   return Changed;
4910 }
4911
4912 FunctionPass *llvm::createInstructionCombiningPass() {
4913   return new InstCombiner();
4914 }
4915