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   ++GTI;   // Measure type stepping over.
2108   for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i, ++GTI) {
2109     Value *Op = GEP->getOperand(i);
2110     uint64_t Size = TD.getTypeSize(*GTI) & PtrSizeMask;
2111     Constant *Scale = ConstantExpr::getCast(ConstantUInt::get(UIntPtrTy, Size),
2112                                             SIntPtrTy);
2113     if (Constant *OpC = dyn_cast<Constant>(Op)) {
2114       if (!OpC->isNullValue()) {
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       // We'll let instcombine(mul) convert this to a shl if possible.
2127       Value *Offs =
2128         IC.InsertNewInstBefore(BinaryOperator::createMul(Op, Scale,
2129                                                    GEP->getName()+".idx"), I);
2130
2131       // Emit an add instruction.
2132       Result = IC.InsertNewInstBefore(BinaryOperator::createAdd(Offs, Result,
2133                                                     GEP->getName()+".offs"), I);
2134     }
2135   }
2136   return Result;
2137 }
2138
2139 /// FoldGEPSetCC - Fold comparisons between a GEP instruction and something
2140 /// else.  At this point we know that the GEP is on the LHS of the comparison.
2141 Instruction *InstCombiner::FoldGEPSetCC(User *GEPLHS, Value *RHS,
2142                                         Instruction::BinaryOps Cond,
2143                                         Instruction &I) {
2144   assert(dyn_castGetElementPtr(GEPLHS) && "LHS is not a getelementptr!");
2145
2146   Value *PtrBase = GEPLHS->getOperand(0);
2147   if (PtrBase == RHS) {
2148     // As an optimization, we don't actually have to compute the actual value of
2149     // OFFSET if this is a seteq or setne comparison, just return whether each
2150     // index is zero or not.
2151
2152     // Only lower this if the setcc is the only user of the GEP or if we expect
2153     // the result to fold to a constant!
2154     if (isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) {
2155       // ((gep Ptr, OFFSET) cmp Ptr)   ---> (OFFSET cmp 0).
2156       Value *Offset = EmitGEPOffset(GEPLHS, I, *this);
2157       return new SetCondInst(Cond, Offset,
2158                              Constant::getNullValue(Offset->getType()));
2159     }
2160   } else if (User *GEPRHS = dyn_castGetElementPtr(RHS)) {
2161     if (PtrBase != GEPRHS->getOperand(0))
2162       return 0;
2163
2164     // Only lower this if the setcc is the only user of the GEP or if we expect
2165     // the result to fold to a constant!
2166     if ((isa<ConstantExpr>(GEPLHS) || GEPLHS->hasOneUse()) &&
2167         (isa<ConstantExpr>(GEPRHS) || GEPRHS->hasOneUse())) {
2168       // ((gep Ptr, OFFSET1) cmp (gep Ptr, OFFSET2)  --->  (OFFSET1 cmp OFFSET2)
2169       Value *L = EmitGEPOffset(GEPLHS, I, *this);
2170       Value *R = EmitGEPOffset(GEPRHS, I, *this);
2171       return new SetCondInst(Cond, L, R);
2172     }
2173   }
2174   return 0;
2175 }
2176
2177
2178 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
2179   bool Changed = SimplifyCommutative(I);
2180   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2181   const Type *Ty = Op0->getType();
2182
2183   // setcc X, X
2184   if (Op0 == Op1)
2185     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
2186
2187   if (isa<UndefValue>(Op1))                  // X setcc undef -> undef
2188     return ReplaceInstUsesWith(I, UndefValue::get(Type::BoolTy));
2189
2190   // setcc <global/alloca*/null>, <global/alloca*/null> - Global/Stack value
2191   // addresses never equal each other!  We already know that Op0 != Op1.
2192   if ((isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0) ||
2193        isa<ConstantPointerNull>(Op0)) &&
2194       (isa<GlobalValue>(Op1) || isa<AllocaInst>(Op1) ||
2195        isa<ConstantPointerNull>(Op1)))
2196     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
2197
2198   // setcc's with boolean values can always be turned into bitwise operations
2199   if (Ty == Type::BoolTy) {
2200     switch (I.getOpcode()) {
2201     default: assert(0 && "Invalid setcc instruction!");
2202     case Instruction::SetEQ: {     //  seteq bool %A, %B -> ~(A^B)
2203       Instruction *Xor = BinaryOperator::createXor(Op0, Op1, I.getName()+"tmp");
2204       InsertNewInstBefore(Xor, I);
2205       return BinaryOperator::createNot(Xor);
2206     }
2207     case Instruction::SetNE:
2208       return BinaryOperator::createXor(Op0, Op1);
2209
2210     case Instruction::SetGT:
2211       std::swap(Op0, Op1);                   // Change setgt -> setlt
2212       // FALL THROUGH
2213     case Instruction::SetLT: {               // setlt bool A, B -> ~X & Y
2214       Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2215       InsertNewInstBefore(Not, I);
2216       return BinaryOperator::createAnd(Not, Op1);
2217     }
2218     case Instruction::SetGE:
2219       std::swap(Op0, Op1);                   // Change setge -> setle
2220       // FALL THROUGH
2221     case Instruction::SetLE: {     //  setle bool %A, %B -> ~A | B
2222       Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
2223       InsertNewInstBefore(Not, I);
2224       return BinaryOperator::createOr(Not, Op1);
2225     }
2226     }
2227   }
2228
2229   // See if we are doing a comparison between a constant and an instruction that
2230   // can be folded into the comparison.
2231   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
2232     // Check to see if we are comparing against the minimum or maximum value...
2233     if (CI->isMinValue()) {
2234       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
2235         return ReplaceInstUsesWith(I, ConstantBool::False);
2236       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
2237         return ReplaceInstUsesWith(I, ConstantBool::True);
2238       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
2239         return BinaryOperator::createSetEQ(Op0, Op1);
2240       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
2241         return BinaryOperator::createSetNE(Op0, Op1);
2242
2243     } else if (CI->isMaxValue()) {
2244       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
2245         return ReplaceInstUsesWith(I, ConstantBool::False);
2246       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
2247         return ReplaceInstUsesWith(I, ConstantBool::True);
2248       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
2249         return BinaryOperator::createSetEQ(Op0, Op1);
2250       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
2251         return BinaryOperator::createSetNE(Op0, Op1);
2252
2253       // Comparing against a value really close to min or max?
2254     } else if (isMinValuePlusOne(CI)) {
2255       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
2256         return BinaryOperator::createSetEQ(Op0, SubOne(CI));
2257       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
2258         return BinaryOperator::createSetNE(Op0, SubOne(CI));
2259
2260     } else if (isMaxValueMinusOne(CI)) {
2261       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
2262         return BinaryOperator::createSetEQ(Op0, AddOne(CI));
2263       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
2264         return BinaryOperator::createSetNE(Op0, AddOne(CI));
2265     }
2266
2267     // If we still have a setle or setge instruction, turn it into the
2268     // appropriate setlt or setgt instruction.  Since the border cases have
2269     // already been handled above, this requires little checking.
2270     //
2271     if (I.getOpcode() == Instruction::SetLE)
2272       return BinaryOperator::createSetLT(Op0, AddOne(CI));
2273     if (I.getOpcode() == Instruction::SetGE)
2274       return BinaryOperator::createSetGT(Op0, SubOne(CI));
2275
2276     if (Instruction *LHSI = dyn_cast<Instruction>(Op0))
2277       switch (LHSI->getOpcode()) {
2278       case Instruction::PHI:
2279         if (Instruction *NV = FoldOpIntoPhi(I))
2280           return NV;
2281         break;
2282       case Instruction::And:
2283         if (LHSI->hasOneUse() && isa<ConstantInt>(LHSI->getOperand(1)) &&
2284             LHSI->getOperand(0)->hasOneUse()) {
2285           // If this is: (X >> C1) & C2 != C3 (where any shift and any compare
2286           // could exist), turn it into (X & (C2 << C1)) != (C3 << C1).  This
2287           // happens a LOT in code produced by the C front-end, for bitfield
2288           // access.
2289           ShiftInst *Shift = dyn_cast<ShiftInst>(LHSI->getOperand(0));
2290           ConstantUInt *ShAmt;
2291           ShAmt = Shift ? dyn_cast<ConstantUInt>(Shift->getOperand(1)) : 0;
2292           ConstantInt *AndCST = cast<ConstantInt>(LHSI->getOperand(1));
2293           const Type *Ty = LHSI->getType();
2294
2295           // We can fold this as long as we can't shift unknown bits
2296           // into the mask.  This can only happen with signed shift
2297           // rights, as they sign-extend.
2298           if (ShAmt) {
2299             bool CanFold = Shift->getOpcode() != Instruction::Shr ||
2300                            Shift->getType()->isUnsigned();
2301             if (!CanFold) {
2302               // To test for the bad case of the signed shr, see if any
2303               // of the bits shifted in could be tested after the mask.
2304               Constant *OShAmt = ConstantUInt::get(Type::UByteTy,
2305                                    Ty->getPrimitiveSize()*8-ShAmt->getValue());
2306               Constant *ShVal =
2307                 ConstantExpr::getShl(ConstantInt::getAllOnesValue(Ty), OShAmt);
2308               if (ConstantExpr::getAnd(ShVal, AndCST)->isNullValue())
2309                 CanFold = true;
2310             }
2311
2312             if (CanFold) {
2313               Constant *NewCst;
2314               if (Shift->getOpcode() == Instruction::Shl)
2315                 NewCst = ConstantExpr::getUShr(CI, ShAmt);
2316               else
2317                 NewCst = ConstantExpr::getShl(CI, ShAmt);
2318
2319               // Check to see if we are shifting out any of the bits being
2320               // compared.
2321               if (ConstantExpr::get(Shift->getOpcode(), NewCst, ShAmt) != CI){
2322                 // If we shifted bits out, the fold is not going to work out.
2323                 // As a special case, check to see if this means that the
2324                 // result is always true or false now.
2325                 if (I.getOpcode() == Instruction::SetEQ)
2326                   return ReplaceInstUsesWith(I, ConstantBool::False);
2327                 if (I.getOpcode() == Instruction::SetNE)
2328                   return ReplaceInstUsesWith(I, ConstantBool::True);
2329               } else {
2330                 I.setOperand(1, NewCst);
2331                 Constant *NewAndCST;
2332                 if (Shift->getOpcode() == Instruction::Shl)
2333                   NewAndCST = ConstantExpr::getUShr(AndCST, ShAmt);
2334                 else
2335                   NewAndCST = ConstantExpr::getShl(AndCST, ShAmt);
2336                 LHSI->setOperand(1, NewAndCST);
2337                 LHSI->setOperand(0, Shift->getOperand(0));
2338                 WorkList.push_back(Shift); // Shift is dead.
2339                 AddUsesToWorkList(I);
2340                 return &I;
2341               }
2342             }
2343           }
2344         }
2345         break;
2346
2347       // (setcc (cast X to larger), CI)
2348       case Instruction::Cast: {
2349         Instruction* replacement =
2350           visitSetCondInstWithCastAndConstant(I,cast<CastInst>(LHSI),CI);
2351         if (replacement)
2352           return replacement;
2353         break;
2354       }
2355
2356       case Instruction::Shl:         // (setcc (shl X, ShAmt), CI)
2357         if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2358           switch (I.getOpcode()) {
2359           default: break;
2360           case Instruction::SetEQ:
2361           case Instruction::SetNE: {
2362             // If we are comparing against bits always shifted out, the
2363             // comparison cannot succeed.
2364             Constant *Comp =
2365               ConstantExpr::getShl(ConstantExpr::getShr(CI, ShAmt), ShAmt);
2366             if (Comp != CI) {// Comparing against a bit that we know is zero.
2367               bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2368               Constant *Cst = ConstantBool::get(IsSetNE);
2369               return ReplaceInstUsesWith(I, Cst);
2370             }
2371
2372             if (LHSI->hasOneUse()) {
2373               // Otherwise strength reduce the shift into an and.
2374               unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2375               unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
2376               uint64_t Val = (1ULL << (TypeBits-ShAmtVal))-1;
2377
2378               Constant *Mask;
2379               if (CI->getType()->isUnsigned()) {
2380                 Mask = ConstantUInt::get(CI->getType(), Val);
2381               } else if (ShAmtVal != 0) {
2382                 Mask = ConstantSInt::get(CI->getType(), Val);
2383               } else {
2384                 Mask = ConstantInt::getAllOnesValue(CI->getType());
2385               }
2386
2387               Instruction *AndI =
2388                 BinaryOperator::createAnd(LHSI->getOperand(0),
2389                                           Mask, LHSI->getName()+".mask");
2390               Value *And = InsertNewInstBefore(AndI, I);
2391               return new SetCondInst(I.getOpcode(), And,
2392                                      ConstantExpr::getUShr(CI, ShAmt));
2393             }
2394           }
2395           }
2396         }
2397         break;
2398
2399       case Instruction::Shr:         // (setcc (shr X, ShAmt), CI)
2400         if (ConstantUInt *ShAmt = dyn_cast<ConstantUInt>(LHSI->getOperand(1))) {
2401           switch (I.getOpcode()) {
2402           default: break;
2403           case Instruction::SetEQ:
2404           case Instruction::SetNE: {
2405             // If we are comparing against bits always shifted out, the
2406             // comparison cannot succeed.
2407             Constant *Comp =
2408               ConstantExpr::getShr(ConstantExpr::getShl(CI, ShAmt), ShAmt);
2409
2410             if (Comp != CI) {// Comparing against a bit that we know is zero.
2411               bool IsSetNE = I.getOpcode() == Instruction::SetNE;
2412               Constant *Cst = ConstantBool::get(IsSetNE);
2413               return ReplaceInstUsesWith(I, Cst);
2414             }
2415
2416             if (LHSI->hasOneUse() || CI->isNullValue()) {
2417               unsigned ShAmtVal = (unsigned)ShAmt->getValue();
2418
2419               // Otherwise strength reduce the shift into an and.
2420               uint64_t Val = ~0ULL;          // All ones.
2421               Val <<= ShAmtVal;              // Shift over to the right spot.
2422
2423               Constant *Mask;
2424               if (CI->getType()->isUnsigned()) {
2425                 unsigned TypeBits = CI->getType()->getPrimitiveSize()*8;
2426                 Val &= (1ULL << TypeBits)-1;
2427                 Mask = ConstantUInt::get(CI->getType(), Val);
2428               } else {
2429                 Mask = ConstantSInt::get(CI->getType(), Val);
2430               }
2431
2432               Instruction *AndI =
2433                 BinaryOperator::createAnd(LHSI->getOperand(0),
2434                                           Mask, LHSI->getName()+".mask");
2435               Value *And = InsertNewInstBefore(AndI, I);
2436               return new SetCondInst(I.getOpcode(), And,
2437                                      ConstantExpr::getShl(CI, ShAmt));
2438             }
2439             break;
2440           }
2441           }
2442         }
2443         break;
2444
2445       case Instruction::Div:
2446         // Fold: (div X, C1) op C2 -> range check
2447         if (ConstantInt *DivRHS = dyn_cast<ConstantInt>(LHSI->getOperand(1))) {
2448           // Fold this div into the comparison, producing a range check.
2449           // Determine, based on the divide type, what the range is being
2450           // checked.  If there is an overflow on the low or high side, remember
2451           // it, otherwise compute the range [low, hi) bounding the new value.
2452           bool LoOverflow = false, HiOverflow = 0;
2453           ConstantInt *LoBound = 0, *HiBound = 0;
2454
2455           ConstantInt *Prod;
2456           bool ProdOV = MulWithOverflow(Prod, CI, DivRHS);
2457
2458           Instruction::BinaryOps Opcode = I.getOpcode();
2459
2460           if (DivRHS->isNullValue()) {  // Don't hack on divide by zeros.
2461           } else if (LHSI->getType()->isUnsigned()) {  // udiv
2462             LoBound = Prod;
2463             LoOverflow = ProdOV;
2464             HiOverflow = ProdOV || AddWithOverflow(HiBound, LoBound, DivRHS);
2465           } else if (isPositive(DivRHS)) {             // Divisor is > 0.
2466             if (CI->isNullValue()) {       // (X / pos) op 0
2467               // Can't overflow.
2468               LoBound = cast<ConstantInt>(ConstantExpr::getNeg(SubOne(DivRHS)));
2469               HiBound = DivRHS;
2470             } else if (isPositive(CI)) {   // (X / pos) op pos
2471               LoBound = Prod;
2472               LoOverflow = ProdOV;
2473               HiOverflow = ProdOV || AddWithOverflow(HiBound, Prod, DivRHS);
2474             } else {                       // (X / pos) op neg
2475               Constant *DivRHSH = ConstantExpr::getNeg(SubOne(DivRHS));
2476               LoOverflow = AddWithOverflow(LoBound, Prod,
2477                                            cast<ConstantInt>(DivRHSH));
2478               HiBound = Prod;
2479               HiOverflow = ProdOV;
2480             }
2481           } else {                                     // Divisor is < 0.
2482             if (CI->isNullValue()) {       // (X / neg) op 0
2483               LoBound = AddOne(DivRHS);
2484               HiBound = cast<ConstantInt>(ConstantExpr::getNeg(DivRHS));
2485             } else if (isPositive(CI)) {   // (X / neg) op pos
2486               HiOverflow = LoOverflow = ProdOV;
2487               if (!LoOverflow)
2488                 LoOverflow = AddWithOverflow(LoBound, Prod, AddOne(DivRHS));
2489               HiBound = AddOne(Prod);
2490             } else {                       // (X / neg) op neg
2491               LoBound = Prod;
2492               LoOverflow = HiOverflow = ProdOV;
2493               HiBound = cast<ConstantInt>(ConstantExpr::getSub(Prod, DivRHS));
2494             }
2495
2496             // Dividing by a negate swaps the condition.
2497             Opcode = SetCondInst::getSwappedCondition(Opcode);
2498           }
2499
2500           if (LoBound) {
2501             Value *X = LHSI->getOperand(0);
2502             switch (Opcode) {
2503             default: assert(0 && "Unhandled setcc opcode!");
2504             case Instruction::SetEQ:
2505               if (LoOverflow && HiOverflow)
2506                 return ReplaceInstUsesWith(I, ConstantBool::False);
2507               else if (HiOverflow)
2508                 return new SetCondInst(Instruction::SetGE, X, LoBound);
2509               else if (LoOverflow)
2510                 return new SetCondInst(Instruction::SetLT, X, HiBound);
2511               else
2512                 return InsertRangeTest(X, LoBound, HiBound, true, I);
2513             case Instruction::SetNE:
2514               if (LoOverflow && HiOverflow)
2515                 return ReplaceInstUsesWith(I, ConstantBool::True);
2516               else if (HiOverflow)
2517                 return new SetCondInst(Instruction::SetLT, X, LoBound);
2518               else if (LoOverflow)
2519                 return new SetCondInst(Instruction::SetGE, X, HiBound);
2520               else
2521                 return InsertRangeTest(X, LoBound, HiBound, false, I);
2522             case Instruction::SetLT:
2523               if (LoOverflow)
2524                 return ReplaceInstUsesWith(I, ConstantBool::False);
2525               return new SetCondInst(Instruction::SetLT, X, LoBound);
2526             case Instruction::SetGT:
2527               if (HiOverflow)
2528                 return ReplaceInstUsesWith(I, ConstantBool::False);
2529               return new SetCondInst(Instruction::SetGE, X, HiBound);
2530             }
2531           }
2532         }
2533         break;
2534       case Instruction::Select:
2535         // If either operand of the select is a constant, we can fold the
2536         // comparison into the select arms, which will cause one to be
2537         // constant folded and the select turned into a bitwise or.
2538         Value *Op1 = 0, *Op2 = 0;
2539         if (LHSI->hasOneUse()) {
2540           if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(1))) {
2541             // Fold the known value into the constant operand.
2542             Op1 = ConstantExpr::get(I.getOpcode(), C, CI);
2543             // Insert a new SetCC of the other select operand.
2544             Op2 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
2545                                                       LHSI->getOperand(2), CI,
2546                                                       I.getName()), I);
2547           } else if (Constant *C = dyn_cast<Constant>(LHSI->getOperand(2))) {
2548             // Fold the known value into the constant operand.
2549             Op2 = ConstantExpr::get(I.getOpcode(), C, CI);
2550             // Insert a new SetCC of the other select operand.
2551             Op1 = InsertNewInstBefore(new SetCondInst(I.getOpcode(),
2552                                                       LHSI->getOperand(1), CI,
2553                                                       I.getName()), I);
2554           }
2555         }
2556
2557         if (Op1)
2558           return new SelectInst(LHSI->getOperand(0), Op1, Op2);
2559         break;
2560       }
2561
2562     // Simplify seteq and setne instructions...
2563     if (I.getOpcode() == Instruction::SetEQ ||
2564         I.getOpcode() == Instruction::SetNE) {
2565       bool isSetNE = I.getOpcode() == Instruction::SetNE;
2566
2567       // If the first operand is (and|or|xor) with a constant, and the second
2568       // operand is a constant, simplify a bit.
2569       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
2570         switch (BO->getOpcode()) {
2571         case Instruction::Rem:
2572           // If we have a signed (X % (2^c)) == 0, turn it into an unsigned one.
2573           if (CI->isNullValue() && isa<ConstantSInt>(BO->getOperand(1)) &&
2574               BO->hasOneUse() &&
2575               cast<ConstantSInt>(BO->getOperand(1))->getValue() > 1)
2576             if (unsigned L2 =
2577                 Log2(cast<ConstantSInt>(BO->getOperand(1))->getValue())) {
2578               const Type *UTy = BO->getType()->getUnsignedVersion();
2579               Value *NewX = InsertNewInstBefore(new CastInst(BO->getOperand(0),
2580                                                              UTy, "tmp"), I);
2581               Constant *RHSCst = ConstantUInt::get(UTy, 1ULL << L2);
2582               Value *NewRem =InsertNewInstBefore(BinaryOperator::createRem(NewX,
2583                                                     RHSCst, BO->getName()), I);
2584               return BinaryOperator::create(I.getOpcode(), NewRem,
2585                                             Constant::getNullValue(UTy));
2586             }
2587           break;
2588
2589         case Instruction::Add:
2590           // Replace ((add A, B) != C) with (A != C-B) if B & C are constants.
2591           if (ConstantInt *BOp1C = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2592             if (BO->hasOneUse())
2593               return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2594                                      ConstantExpr::getSub(CI, BOp1C));
2595           } else if (CI->isNullValue()) {
2596             // Replace ((add A, B) != 0) with (A != -B) if A or B is
2597             // efficiently invertible, or if the add has just this one use.
2598             Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
2599
2600             if (Value *NegVal = dyn_castNegVal(BOp1))
2601               return new SetCondInst(I.getOpcode(), BOp0, NegVal);
2602             else if (Value *NegVal = dyn_castNegVal(BOp0))
2603               return new SetCondInst(I.getOpcode(), NegVal, BOp1);
2604             else if (BO->hasOneUse()) {
2605               Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
2606               BO->setName("");
2607               InsertNewInstBefore(Neg, I);
2608               return new SetCondInst(I.getOpcode(), BOp0, Neg);
2609             }
2610           }
2611           break;
2612         case Instruction::Xor:
2613           // For the xor case, we can xor two constants together, eliminating
2614           // the explicit xor.
2615           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
2616             return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
2617                                   ConstantExpr::getXor(CI, BOC));
2618
2619           // FALLTHROUGH
2620         case Instruction::Sub:
2621           // Replace (([sub|xor] A, B) != 0) with (A != B)
2622           if (CI->isNullValue())
2623             return new SetCondInst(I.getOpcode(), BO->getOperand(0),
2624                                    BO->getOperand(1));
2625           break;
2626
2627         case Instruction::Or:
2628           // If bits are being or'd in that are not present in the constant we
2629           // are comparing against, then the comparison could never succeed!
2630           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
2631             Constant *NotCI = ConstantExpr::getNot(CI);
2632             if (!ConstantExpr::getAnd(BOC, NotCI)->isNullValue())
2633               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2634           }
2635           break;
2636
2637         case Instruction::And:
2638           if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
2639             // If bits are being compared against that are and'd out, then the
2640             // comparison can never succeed!
2641             if (!ConstantExpr::getAnd(CI,
2642                                       ConstantExpr::getNot(BOC))->isNullValue())
2643               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
2644
2645             // If we have ((X & C) == C), turn it into ((X & C) != 0).
2646             if (CI == BOC && isOneBitSet(CI))
2647               return new SetCondInst(isSetNE ? Instruction::SetEQ :
2648                                      Instruction::SetNE, Op0,
2649                                      Constant::getNullValue(CI->getType()));
2650
2651             // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
2652             // to be a signed value as appropriate.
2653             if (isSignBit(BOC)) {
2654               Value *X = BO->getOperand(0);
2655               // If 'X' is not signed, insert a cast now...
2656               if (!BOC->getType()->isSigned()) {
2657                 const Type *DestTy = BOC->getType()->getSignedVersion();
2658                 X = InsertCastBefore(X, DestTy, I);
2659               }
2660               return new SetCondInst(isSetNE ? Instruction::SetLT :
2661                                          Instruction::SetGE, X,
2662                                      Constant::getNullValue(X->getType()));
2663             }
2664
2665             // ((X & ~7) == 0) --> X < 8
2666             if (CI->isNullValue() && isHighOnes(BOC)) {
2667               Value *X = BO->getOperand(0);
2668               Constant *NegX = ConstantExpr::getNeg(BOC);
2669
2670               // If 'X' is signed, insert a cast now.
2671               if (NegX->getType()->isSigned()) {
2672                 const Type *DestTy = NegX->getType()->getUnsignedVersion();
2673                 X = InsertCastBefore(X, DestTy, I);
2674                 NegX = ConstantExpr::getCast(NegX, DestTy);
2675               }
2676
2677               return new SetCondInst(isSetNE ? Instruction::SetGE :
2678                                      Instruction::SetLT, X, NegX);
2679             }
2680
2681           }
2682         default: break;
2683         }
2684       }
2685     } else {  // Not a SetEQ/SetNE
2686       // If the LHS is a cast from an integral value of the same size,
2687       if (CastInst *Cast = dyn_cast<CastInst>(Op0)) {
2688         Value *CastOp = Cast->getOperand(0);
2689         const Type *SrcTy = CastOp->getType();
2690         unsigned SrcTySize = SrcTy->getPrimitiveSize();
2691         if (SrcTy != Cast->getType() && SrcTy->isInteger() &&
2692             SrcTySize == Cast->getType()->getPrimitiveSize()) {
2693           assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) &&
2694                  "Source and destination signednesses should differ!");
2695           if (Cast->getType()->isSigned()) {
2696             // If this is a signed comparison, check for comparisons in the
2697             // vicinity of zero.
2698             if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
2699               // X < 0  => x > 127
2700               return BinaryOperator::createSetGT(CastOp,
2701                          ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1));
2702             else if (I.getOpcode() == Instruction::SetGT &&
2703                      cast<ConstantSInt>(CI)->getValue() == -1)
2704               // X > -1  => x < 128
2705               return BinaryOperator::createSetLT(CastOp,
2706                          ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1)));
2707           } else {
2708             ConstantUInt *CUI = cast<ConstantUInt>(CI);
2709             if (I.getOpcode() == Instruction::SetLT &&
2710                 CUI->getValue() == 1ULL << (SrcTySize*8-1))
2711               // X < 128 => X > -1
2712               return BinaryOperator::createSetGT(CastOp,
2713                                                  ConstantSInt::get(SrcTy, -1));
2714             else if (I.getOpcode() == Instruction::SetGT &&
2715                      CUI->getValue() == (1ULL << (SrcTySize*8-1))-1)
2716               // X > 127 => X < 0
2717               return BinaryOperator::createSetLT(CastOp,
2718                                                  Constant::getNullValue(SrcTy));
2719           }
2720         }
2721       }
2722     }
2723   }
2724
2725   // If we can optimize a 'setcc GEP, P' or 'setcc P, GEP', do so now.
2726   if (User *GEP = dyn_castGetElementPtr(Op0))
2727     if (Instruction *NI = FoldGEPSetCC(GEP, Op1, I.getOpcode(), I))
2728       return NI;
2729   if (User *GEP = dyn_castGetElementPtr(Op1))
2730     if (Instruction *NI = FoldGEPSetCC(GEP, Op0,
2731                            SetCondInst::getSwappedCondition(I.getOpcode()), I))
2732       return NI;
2733
2734   // Test to see if the operands of the setcc are casted versions of other
2735   // values.  If the cast can be stripped off both arguments, we do so now.
2736   if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
2737     Value *CastOp0 = CI->getOperand(0);
2738     if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
2739         (isa<Constant>(Op1) || isa<CastInst>(Op1)) &&
2740         (I.getOpcode() == Instruction::SetEQ ||
2741          I.getOpcode() == Instruction::SetNE)) {
2742       // We keep moving the cast from the left operand over to the right
2743       // operand, where it can often be eliminated completely.
2744       Op0 = CastOp0;
2745
2746       // If operand #1 is a cast instruction, see if we can eliminate it as
2747       // well.
2748       if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
2749         if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
2750                                                                Op0->getType()))
2751           Op1 = CI2->getOperand(0);
2752
2753       // If Op1 is a constant, we can fold the cast into the constant.
2754       if (Op1->getType() != Op0->getType())
2755         if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
2756           Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
2757         } else {
2758           // Otherwise, cast the RHS right before the setcc
2759           Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
2760           InsertNewInstBefore(cast<Instruction>(Op1), I);
2761         }
2762       return BinaryOperator::create(I.getOpcode(), Op0, Op1);
2763     }
2764
2765     // Handle the special case of: setcc (cast bool to X), <cst>
2766     // This comes up when you have code like
2767     //   int X = A < B;
2768     //   if (X) ...
2769     // For generality, we handle any zero-extension of any operand comparison
2770     // with a constant.
2771     if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) {
2772       const Type *SrcTy = CastOp0->getType();
2773       const Type *DestTy = Op0->getType();
2774       if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
2775           (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) {
2776         // Ok, we have an expansion of operand 0 into a new type.  Get the
2777         // constant value, masink off bits which are not set in the RHS.  These
2778         // could be set if the destination value is signed.
2779         uint64_t ConstVal = ConstantRHS->getRawValue();
2780         ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1;
2781
2782         // If the constant we are comparing it with has high bits set, which
2783         // don't exist in the original value, the values could never be equal,
2784         // because the source would be zero extended.
2785         unsigned SrcBits =
2786           SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8;
2787         bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1));
2788         if (ConstVal & ~((1ULL << SrcBits)-1)) {
2789           switch (I.getOpcode()) {
2790           default: assert(0 && "Unknown comparison type!");
2791           case Instruction::SetEQ:
2792             return ReplaceInstUsesWith(I, ConstantBool::False);
2793           case Instruction::SetNE:
2794             return ReplaceInstUsesWith(I, ConstantBool::True);
2795           case Instruction::SetLT:
2796           case Instruction::SetLE:
2797             if (DestTy->isSigned() && HasSignBit)
2798               return ReplaceInstUsesWith(I, ConstantBool::False);
2799             return ReplaceInstUsesWith(I, ConstantBool::True);
2800           case Instruction::SetGT:
2801           case Instruction::SetGE:
2802             if (DestTy->isSigned() && HasSignBit)
2803               return ReplaceInstUsesWith(I, ConstantBool::True);
2804             return ReplaceInstUsesWith(I, ConstantBool::False);
2805           }
2806         }
2807
2808         // Otherwise, we can replace the setcc with a setcc of the smaller
2809         // operand value.
2810         Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy);
2811         return BinaryOperator::create(I.getOpcode(), CastOp0, Op1);
2812       }
2813     }
2814   }
2815   return Changed ? &I : 0;
2816 }
2817
2818 // visitSetCondInstWithCastAndConstant - this method is part of the
2819 // visitSetCondInst method. It handles the situation where we have:
2820 //   (setcc (cast X to larger), CI)
2821 // It tries to remove the cast and even the setcc if the CI value
2822 // and range of the cast allow it.
2823 Instruction *
2824 InstCombiner::visitSetCondInstWithCastAndConstant(BinaryOperator&I,
2825                                                   CastInst* LHSI,
2826                                                   ConstantInt* CI) {
2827   const Type *SrcTy = LHSI->getOperand(0)->getType();
2828   const Type *DestTy = LHSI->getType();
2829   if (SrcTy->isIntegral() && DestTy->isIntegral()) {
2830     unsigned SrcBits = SrcTy->getPrimitiveSize()*8;
2831     unsigned DestBits = DestTy->getPrimitiveSize()*8;
2832     if (SrcTy == Type::BoolTy)
2833       SrcBits = 1;
2834     if (DestTy == Type::BoolTy)
2835       DestBits = 1;
2836     if (SrcBits < DestBits) {
2837       // There are fewer bits in the source of the cast than in the result
2838       // of the cast. Any other case doesn't matter because the constant
2839       // value won't have changed due to sign extension.
2840       Constant *NewCst = ConstantExpr::getCast(CI, SrcTy);
2841       if (ConstantExpr::getCast(NewCst, DestTy) == CI) {
2842         // The constant value operand of the setCC before and after a
2843         // cast to the source type of the cast instruction is the same
2844         // value, so we just replace with the same setcc opcode, but
2845         // using the source value compared to the constant casted to the
2846         // source type.
2847         if (SrcTy->isSigned() && DestTy->isUnsigned()) {
2848           CastInst* Cst = new CastInst(LHSI->getOperand(0),
2849             SrcTy->getUnsignedVersion(), LHSI->getName());
2850           InsertNewInstBefore(Cst,I);
2851           return new SetCondInst(I.getOpcode(), Cst,
2852               ConstantExpr::getCast(CI, SrcTy->getUnsignedVersion()));
2853         }
2854         return new SetCondInst(I.getOpcode(), LHSI->getOperand(0),NewCst);
2855       }
2856       // The constant value before and after a cast to the source type
2857       // is different, so various cases are possible depending on the
2858       // opcode and the signs of the types involved in the cast.
2859       switch (I.getOpcode()) {
2860         case Instruction::SetLT: {
2861           Constant* Max = ConstantIntegral::getMaxValue(SrcTy);
2862           Max = ConstantExpr::getCast(Max, DestTy);
2863           return ReplaceInstUsesWith(I, ConstantExpr::getSetLT(Max, CI));
2864         }
2865         case Instruction::SetGT: {
2866           Constant* Min = ConstantIntegral::getMinValue(SrcTy);
2867           Min = ConstantExpr::getCast(Min, DestTy);
2868           return ReplaceInstUsesWith(I, ConstantExpr::getSetGT(Min, CI));
2869         }
2870         case Instruction::SetEQ:
2871           // We're looking for equality, and we know the values are not
2872           // equal so replace with constant False.
2873           return ReplaceInstUsesWith(I, ConstantBool::False);
2874         case Instruction::SetNE:
2875           // We're testing for inequality, and we know the values are not
2876           // equal so replace with constant True.
2877           return ReplaceInstUsesWith(I, ConstantBool::True);
2878         case Instruction::SetLE:
2879         case Instruction::SetGE:
2880           assert(!"SetLE and SetGE should be handled elsewhere");
2881         default:
2882           assert(!"unknown integer comparison");
2883       }
2884     }
2885   }
2886   return 0;
2887 }
2888
2889
2890 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
2891   assert(I.getOperand(1)->getType() == Type::UByteTy);
2892   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
2893   bool isLeftShift = I.getOpcode() == Instruction::Shl;
2894
2895   // shl X, 0 == X and shr X, 0 == X
2896   // shl 0, X == 0 and shr 0, X == 0
2897   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
2898       Op0 == Constant::getNullValue(Op0->getType()))
2899     return ReplaceInstUsesWith(I, Op0);
2900
2901   if (isa<UndefValue>(Op0)) {            // undef >>s X -> undef
2902     if (!isLeftShift && I.getType()->isSigned())
2903       return ReplaceInstUsesWith(I, Op0);
2904     else                         // undef << X -> 0   AND  undef >>u X -> 0
2905       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
2906   }
2907   if (isa<UndefValue>(Op1)) {
2908     if (isLeftShift || I.getType()->isUnsigned())
2909       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
2910     else
2911       return ReplaceInstUsesWith(I, Op0);          // X >>s undef -> X
2912   }
2913
2914   // shr int -1, X = -1   (for any arithmetic shift rights of ~0)
2915   if (!isLeftShift)
2916     if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
2917       if (CSI->isAllOnesValue())
2918         return ReplaceInstUsesWith(I, CSI);
2919
2920   // Try to fold constant and into select arguments.
2921   if (isa<Constant>(Op0))
2922     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
2923       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
2924         return R;
2925
2926   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
2927     // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
2928     // of a signed value.
2929     //
2930     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
2931     if (CUI->getValue() >= TypeBits) {
2932       if (!Op0->getType()->isSigned() || isLeftShift)
2933         return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
2934       else {
2935         I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1));
2936         return &I;
2937       }
2938     }
2939
2940     // ((X*C1) << C2) == (X * (C1 << C2))
2941     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
2942       if (BO->getOpcode() == Instruction::Mul && isLeftShift)
2943         if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
2944           return BinaryOperator::createMul(BO->getOperand(0),
2945                                            ConstantExpr::getShl(BOOp, CUI));
2946
2947     // Try to fold constant and into select arguments.
2948     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
2949       if (Instruction *R = FoldOpIntoSelect(I, SI, this))
2950         return R;
2951     if (isa<PHINode>(Op0))
2952       if (Instruction *NV = FoldOpIntoPhi(I))
2953         return NV;
2954
2955     if (Op0->hasOneUse()) {
2956       // If this is a SHL of a sign-extending cast, see if we can turn the input
2957       // into a zero extending cast (a simple strength reduction).
2958       if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
2959         const Type *SrcTy = CI->getOperand(0)->getType();
2960         if (isLeftShift && SrcTy->isInteger() && SrcTy->isSigned() &&
2961             SrcTy->getPrimitiveSize() < CI->getType()->getPrimitiveSize()) {
2962           // We can change it to a zero extension if we are shifting out all of
2963           // the sign extended bits.  To check this, form a mask of all of the
2964           // sign extend bits, then shift them left and see if we have anything
2965           // left.
2966           Constant *Mask = ConstantIntegral::getAllOnesValue(SrcTy); //     1111
2967           Mask = ConstantExpr::getZeroExtend(Mask, CI->getType());   // 00001111
2968           Mask = ConstantExpr::getNot(Mask);   // 1's in the sign bits: 11110000
2969           if (ConstantExpr::getShl(Mask, CUI)->isNullValue()) {
2970             // If the shift is nuking all of the sign bits, change this to a
2971             // zero extension cast.  To do this, cast the cast input to
2972             // unsigned, then to the requested size.
2973             Value *CastOp = CI->getOperand(0);
2974             Instruction *NC =
2975               new CastInst(CastOp, CastOp->getType()->getUnsignedVersion(),
2976                            CI->getName()+".uns");
2977             NC = InsertNewInstBefore(NC, I);
2978             // Finally, insert a replacement for CI.
2979             NC = new CastInst(NC, CI->getType(), CI->getName());
2980             CI->setName("");
2981             NC = InsertNewInstBefore(NC, I);
2982             WorkList.push_back(CI);  // Delete CI later.
2983             I.setOperand(0, NC);
2984             return &I;               // The SHL operand was modified.
2985           }
2986         }
2987       }
2988
2989       // If the operand is an bitwise operator with a constant RHS, and the
2990       // shift is the only use, we can pull it out of the shift.
2991       if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
2992         if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
2993           bool isValid = true;     // Valid only for And, Or, Xor
2994           bool highBitSet = false; // Transform if high bit of constant set?
2995
2996           switch (Op0BO->getOpcode()) {
2997           default: isValid = false; break;   // Do not perform transform!
2998           case Instruction::Add:
2999             isValid = isLeftShift;
3000             break;
3001           case Instruction::Or:
3002           case Instruction::Xor:
3003             highBitSet = false;
3004             break;
3005           case Instruction::And:
3006             highBitSet = true;
3007             break;
3008           }
3009
3010           // If this is a signed shift right, and the high bit is modified
3011           // by the logical operation, do not perform the transformation.
3012           // The highBitSet boolean indicates the value of the high bit of
3013           // the constant which would cause it to be modified for this
3014           // operation.
3015           //
3016           if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
3017             uint64_t Val = Op0C->getRawValue();
3018             isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
3019           }
3020
3021           if (isValid) {
3022             Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI);
3023
3024             Instruction *NewShift =
3025               new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
3026                             Op0BO->getName());
3027             Op0BO->setName("");
3028             InsertNewInstBefore(NewShift, I);
3029
3030             return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
3031                                           NewRHS);
3032           }
3033         }
3034     }
3035
3036     // If this is a shift of a shift, see if we can fold the two together...
3037     if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
3038       if (ConstantUInt *ShiftAmt1C =
3039                                  dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
3040         unsigned ShiftAmt1 = (unsigned)ShiftAmt1C->getValue();
3041         unsigned ShiftAmt2 = (unsigned)CUI->getValue();
3042
3043         // Check for (A << c1) << c2   and   (A >> c1) >> c2
3044         if (I.getOpcode() == Op0SI->getOpcode()) {
3045           unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift...
3046           if (Op0->getType()->getPrimitiveSize()*8 < Amt)
3047             Amt = Op0->getType()->getPrimitiveSize()*8;
3048           return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
3049                                ConstantUInt::get(Type::UByteTy, Amt));
3050         }
3051
3052         // Check for (A << c1) >> c2 or visaversa.  If we are dealing with
3053         // signed types, we can only support the (A >> c1) << c2 configuration,
3054         // because it can not turn an arbitrary bit of A into a sign bit.
3055         if (I.getType()->isUnsigned() || isLeftShift) {
3056           // Calculate bitmask for what gets shifted off the edge...
3057           Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
3058           if (isLeftShift)
3059             C = ConstantExpr::getShl(C, ShiftAmt1C);
3060           else
3061             C = ConstantExpr::getShr(C, ShiftAmt1C);
3062
3063           Instruction *Mask =
3064             BinaryOperator::createAnd(Op0SI->getOperand(0), C,
3065                                       Op0SI->getOperand(0)->getName()+".mask");
3066           InsertNewInstBefore(Mask, I);
3067
3068           // Figure out what flavor of shift we should use...
3069           if (ShiftAmt1 == ShiftAmt2)
3070             return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
3071           else if (ShiftAmt1 < ShiftAmt2) {
3072             return new ShiftInst(I.getOpcode(), Mask,
3073                          ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
3074           } else {
3075             return new ShiftInst(Op0SI->getOpcode(), Mask,
3076                          ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
3077           }
3078         }
3079       }
3080   }
3081
3082   return 0;
3083 }
3084
3085 enum CastType {
3086   Noop     = 0,
3087   Truncate = 1,
3088   Signext  = 2,
3089   Zeroext  = 3
3090 };
3091
3092 /// getCastType - In the future, we will split the cast instruction into these
3093 /// various types.  Until then, we have to do the analysis here.
3094 static CastType getCastType(const Type *Src, const Type *Dest) {
3095   assert(Src->isIntegral() && Dest->isIntegral() &&
3096          "Only works on integral types!");
3097   unsigned SrcSize = Src->getPrimitiveSize()*8;
3098   if (Src == Type::BoolTy) SrcSize = 1;
3099   unsigned DestSize = Dest->getPrimitiveSize()*8;
3100   if (Dest == Type::BoolTy) DestSize = 1;
3101
3102   if (SrcSize == DestSize) return Noop;
3103   if (SrcSize > DestSize)  return Truncate;
3104   if (Src->isSigned()) return Signext;
3105   return Zeroext;
3106 }
3107
3108
3109 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
3110 // instruction.
3111 //
3112 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
3113                                           const Type *DstTy, TargetData *TD) {
3114
3115   // It is legal to eliminate the instruction if casting A->B->A if the sizes
3116   // are identical and the bits don't get reinterpreted (for example
3117   // int->float->int would not be allowed).
3118   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
3119     return true;
3120
3121   // If we are casting between pointer and integer types, treat pointers as
3122   // integers of the appropriate size for the code below.
3123   if (isa<PointerType>(SrcTy)) SrcTy = TD->getIntPtrType();
3124   if (isa<PointerType>(MidTy)) MidTy = TD->getIntPtrType();
3125   if (isa<PointerType>(DstTy)) DstTy = TD->getIntPtrType();
3126
3127   // Allow free casting and conversion of sizes as long as the sign doesn't
3128   // change...
3129   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
3130     CastType FirstCast = getCastType(SrcTy, MidTy);
3131     CastType SecondCast = getCastType(MidTy, DstTy);
3132
3133     // Capture the effect of these two casts.  If the result is a legal cast,
3134     // the CastType is stored here, otherwise a special code is used.
3135     static const unsigned CastResult[] = {
3136       // First cast is noop
3137       0, 1, 2, 3,
3138       // First cast is a truncate
3139       1, 1, 4, 4,         // trunc->extend is not safe to eliminate
3140       // First cast is a sign ext
3141       2, 5, 2, 4,         // signext->zeroext never ok
3142       // First cast is a zero ext
3143       3, 5, 3, 3,
3144     };
3145
3146     unsigned Result = CastResult[FirstCast*4+SecondCast];
3147     switch (Result) {
3148     default: assert(0 && "Illegal table value!");
3149     case 0:
3150     case 1:
3151     case 2:
3152     case 3:
3153       // FIXME: in the future, when LLVM has explicit sign/zeroextends and
3154       // truncates, we could eliminate more casts.
3155       return (unsigned)getCastType(SrcTy, DstTy) == Result;
3156     case 4:
3157       return false;  // Not possible to eliminate this here.
3158     case 5:
3159       // Sign or zero extend followed by truncate is always ok if the result
3160       // is a truncate or noop.
3161       CastType ResultCast = getCastType(SrcTy, DstTy);
3162       if (ResultCast == Noop || ResultCast == Truncate)
3163         return true;
3164       // Otherwise we are still growing the value, we are only safe if the
3165       // result will match the sign/zeroextendness of the result.
3166       return ResultCast == FirstCast;
3167     }
3168   }
3169   return false;
3170 }
3171
3172 static bool ValueRequiresCast(const Value *V, const Type *Ty, TargetData *TD) {
3173   if (V->getType() == Ty || isa<Constant>(V)) return false;
3174   if (const CastInst *CI = dyn_cast<CastInst>(V))
3175     if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty,
3176                                TD))
3177       return false;
3178   return true;
3179 }
3180
3181 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
3182 /// InsertBefore instruction.  This is specialized a bit to avoid inserting
3183 /// casts that are known to not do anything...
3184 ///
3185 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
3186                                              Instruction *InsertBefore) {
3187   if (V->getType() == DestTy) return V;
3188   if (Constant *C = dyn_cast<Constant>(V))
3189     return ConstantExpr::getCast(C, DestTy);
3190
3191   CastInst *CI = new CastInst(V, DestTy, V->getName());
3192   InsertNewInstBefore(CI, *InsertBefore);
3193   return CI;
3194 }
3195
3196 // CastInst simplification
3197 //
3198 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
3199   Value *Src = CI.getOperand(0);
3200
3201   // If the user is casting a value to the same type, eliminate this cast
3202   // instruction...
3203   if (CI.getType() == Src->getType())
3204     return ReplaceInstUsesWith(CI, Src);
3205
3206   if (isa<UndefValue>(Src))   // cast undef -> undef
3207     return ReplaceInstUsesWith(CI, UndefValue::get(CI.getType()));
3208
3209   // If casting the result of another cast instruction, try to eliminate this
3210   // one!
3211   //
3212   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {   // A->B->C cast
3213     Value *A = CSrc->getOperand(0);
3214     if (isEliminableCastOfCast(A->getType(), CSrc->getType(),
3215                                CI.getType(), TD)) {
3216       // This instruction now refers directly to the cast's src operand.  This
3217       // has a good chance of making CSrc dead.
3218       CI.setOperand(0, CSrc->getOperand(0));
3219       return &CI;
3220     }
3221
3222     // If this is an A->B->A cast, and we are dealing with integral types, try
3223     // to convert this into a logical 'and' instruction.
3224     //
3225     if (A->getType()->isInteger() &&
3226         CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
3227         CSrc->getType()->isUnsigned() &&   // B->A cast must zero extend
3228         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()&&
3229         A->getType()->getPrimitiveSize() == CI.getType()->getPrimitiveSize()) {
3230       assert(CSrc->getType() != Type::ULongTy &&
3231              "Cannot have type bigger than ulong!");
3232       uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
3233       Constant *AndOp = ConstantUInt::get(A->getType()->getUnsignedVersion(),
3234                                           AndValue);
3235       AndOp = ConstantExpr::getCast(AndOp, A->getType());
3236       Instruction *And = BinaryOperator::createAnd(CSrc->getOperand(0), AndOp);
3237       if (And->getType() != CI.getType()) {
3238         And->setName(CSrc->getName()+".mask");
3239         InsertNewInstBefore(And, CI);
3240         And = new CastInst(And, CI.getType());
3241       }
3242       return And;
3243     }
3244   }
3245
3246   // If this is a cast to bool, turn it into the appropriate setne instruction.
3247   if (CI.getType() == Type::BoolTy)
3248     return BinaryOperator::createSetNE(CI.getOperand(0),
3249                        Constant::getNullValue(CI.getOperand(0)->getType()));
3250
3251   // If casting the result of a getelementptr instruction with no offset, turn
3252   // this into a cast of the original pointer!
3253   //
3254   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
3255     bool AllZeroOperands = true;
3256     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
3257       if (!isa<Constant>(GEP->getOperand(i)) ||
3258           !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
3259         AllZeroOperands = false;
3260         break;
3261       }
3262     if (AllZeroOperands) {
3263       CI.setOperand(0, GEP->getOperand(0));
3264       return &CI;
3265     }
3266   }
3267
3268   // If we are casting a malloc or alloca to a pointer to a type of the same
3269   // size, rewrite the allocation instruction to allocate the "right" type.
3270   //
3271   if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
3272     if (AI->hasOneUse() && !AI->isArrayAllocation())
3273       if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
3274         // Get the type really allocated and the type casted to...
3275         const Type *AllocElTy = AI->getAllocatedType();
3276         const Type *CastElTy = PTy->getElementType();
3277         if (AllocElTy->isSized() && CastElTy->isSized()) {
3278           uint64_t AllocElTySize = TD->getTypeSize(AllocElTy);
3279           uint64_t CastElTySize = TD->getTypeSize(CastElTy);
3280
3281           // If the allocation is for an even multiple of the cast type size
3282           if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
3283             Value *Amt = ConstantUInt::get(Type::UIntTy,
3284                                          AllocElTySize/CastElTySize);
3285             std::string Name = AI->getName(); AI->setName("");
3286             AllocationInst *New;
3287             if (isa<MallocInst>(AI))
3288               New = new MallocInst(CastElTy, Amt, Name);
3289             else
3290               New = new AllocaInst(CastElTy, Amt, Name);
3291             InsertNewInstBefore(New, *AI);
3292             return ReplaceInstUsesWith(CI, New);
3293           }
3294         }
3295       }
3296
3297   if (SelectInst *SI = dyn_cast<SelectInst>(Src))
3298     if (Instruction *NV = FoldOpIntoSelect(CI, SI, this))
3299       return NV;
3300   if (isa<PHINode>(Src))
3301     if (Instruction *NV = FoldOpIntoPhi(CI))
3302       return NV;
3303
3304   // If the source value is an instruction with only this use, we can attempt to
3305   // propagate the cast into the instruction.  Also, only handle integral types
3306   // for now.
3307   if (Instruction *SrcI = dyn_cast<Instruction>(Src))
3308     if (SrcI->hasOneUse() && Src->getType()->isIntegral() &&
3309         CI.getType()->isInteger()) {  // Don't mess with casts to bool here
3310       const Type *DestTy = CI.getType();
3311       unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
3312       unsigned DestBitSize = getTypeSizeInBits(DestTy);
3313
3314       Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
3315       Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
3316
3317       switch (SrcI->getOpcode()) {
3318       case Instruction::Add:
3319       case Instruction::Mul:
3320       case Instruction::And:
3321       case Instruction::Or:
3322       case Instruction::Xor:
3323         // If we are discarding information, or just changing the sign, rewrite.
3324         if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
3325           // Don't insert two casts if they cannot be eliminated.  We allow two
3326           // casts to be inserted if the sizes are the same.  This could only be
3327           // converting signedness, which is a noop.
3328           if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy,TD) ||
3329               !ValueRequiresCast(Op0, DestTy, TD)) {
3330             Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3331             Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
3332             return BinaryOperator::create(cast<BinaryOperator>(SrcI)
3333                              ->getOpcode(), Op0c, Op1c);
3334           }
3335         }
3336         break;
3337       case Instruction::Shl:
3338         // Allow changing the sign of the source operand.  Do not allow changing
3339         // the size of the shift, UNLESS the shift amount is a constant.  We
3340         // mush not change variable sized shifts to a smaller size, because it
3341         // is undefined to shift more bits out than exist in the value.
3342         if (DestBitSize == SrcBitSize ||
3343             (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
3344           Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
3345           return new ShiftInst(Instruction::Shl, Op0c, Op1);
3346         }
3347         break;
3348       }
3349     }
3350
3351   return 0;
3352 }
3353
3354 /// GetSelectFoldableOperands - We want to turn code that looks like this:
3355 ///   %C = or %A, %B
3356 ///   %D = select %cond, %C, %A
3357 /// into:
3358 ///   %C = select %cond, %B, 0
3359 ///   %D = or %A, %C
3360 ///
3361 /// Assuming that the specified instruction is an operand to the select, return
3362 /// a bitmask indicating which operands of this instruction are foldable if they
3363 /// equal the other incoming value of the select.
3364 ///
3365 static unsigned GetSelectFoldableOperands(Instruction *I) {
3366   switch (I->getOpcode()) {
3367   case Instruction::Add:
3368   case Instruction::Mul:
3369   case Instruction::And:
3370   case Instruction::Or:
3371   case Instruction::Xor:
3372     return 3;              // Can fold through either operand.
3373   case Instruction::Sub:   // Can only fold on the amount subtracted.
3374   case Instruction::Shl:   // Can only fold on the shift amount.
3375   case Instruction::Shr:
3376     return 1;
3377   default:
3378     return 0;              // Cannot fold
3379   }
3380 }
3381
3382 /// GetSelectFoldableConstant - For the same transformation as the previous
3383 /// function, return the identity constant that goes into the select.
3384 static Constant *GetSelectFoldableConstant(Instruction *I) {
3385   switch (I->getOpcode()) {
3386   default: assert(0 && "This cannot happen!"); abort();
3387   case Instruction::Add:
3388   case Instruction::Sub:
3389   case Instruction::Or:
3390   case Instruction::Xor:
3391     return Constant::getNullValue(I->getType());
3392   case Instruction::Shl:
3393   case Instruction::Shr:
3394     return Constant::getNullValue(Type::UByteTy);
3395   case Instruction::And:
3396     return ConstantInt::getAllOnesValue(I->getType());
3397   case Instruction::Mul:
3398     return ConstantInt::get(I->getType(), 1);
3399   }
3400 }
3401
3402 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
3403   Value *CondVal = SI.getCondition();
3404   Value *TrueVal = SI.getTrueValue();
3405   Value *FalseVal = SI.getFalseValue();
3406
3407   // select true, X, Y  -> X
3408   // select false, X, Y -> Y
3409   if (ConstantBool *C = dyn_cast<ConstantBool>(CondVal))
3410     if (C == ConstantBool::True)
3411       return ReplaceInstUsesWith(SI, TrueVal);
3412     else {
3413       assert(C == ConstantBool::False);
3414       return ReplaceInstUsesWith(SI, FalseVal);
3415     }
3416
3417   // select C, X, X -> X
3418   if (TrueVal == FalseVal)
3419     return ReplaceInstUsesWith(SI, TrueVal);
3420
3421   if (isa<UndefValue>(TrueVal))   // select C, undef, X -> X
3422     return ReplaceInstUsesWith(SI, FalseVal);
3423   if (isa<UndefValue>(FalseVal))   // select C, X, undef -> X
3424     return ReplaceInstUsesWith(SI, TrueVal);
3425   if (isa<UndefValue>(CondVal)) {  // select undef, X, Y -> X or Y
3426     if (isa<Constant>(TrueVal))
3427       return ReplaceInstUsesWith(SI, TrueVal);
3428     else
3429       return ReplaceInstUsesWith(SI, FalseVal);
3430   }
3431
3432   if (SI.getType() == Type::BoolTy)
3433     if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
3434       if (C == ConstantBool::True) {
3435         // Change: A = select B, true, C --> A = or B, C
3436         return BinaryOperator::createOr(CondVal, FalseVal);
3437       } else {
3438         // Change: A = select B, false, C --> A = and !B, C
3439         Value *NotCond =
3440           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3441                                              "not."+CondVal->getName()), SI);
3442         return BinaryOperator::createAnd(NotCond, FalseVal);
3443       }
3444     } else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) {
3445       if (C == ConstantBool::False) {
3446         // Change: A = select B, C, false --> A = and B, C
3447         return BinaryOperator::createAnd(CondVal, TrueVal);
3448       } else {
3449         // Change: A = select B, C, true --> A = or !B, C
3450         Value *NotCond =
3451           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3452                                              "not."+CondVal->getName()), SI);
3453         return BinaryOperator::createOr(NotCond, TrueVal);
3454       }
3455     }
3456
3457   // Selecting between two integer constants?
3458   if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal))
3459     if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) {
3460       // select C, 1, 0 -> cast C to int
3461       if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) {
3462         return new CastInst(CondVal, SI.getType());
3463       } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) {
3464         // select C, 0, 1 -> cast !C to int
3465         Value *NotCond =
3466           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
3467                                                "not."+CondVal->getName()), SI);
3468         return new CastInst(NotCond, SI.getType());
3469       }
3470
3471       // If one of the constants is zero (we know they can't both be) and we
3472       // have a setcc instruction with zero, and we have an 'and' with the
3473       // non-constant value, eliminate this whole mess.  This corresponds to
3474       // cases like this: ((X & 27) ? 27 : 0)
3475       if (TrueValC->isNullValue() || FalseValC->isNullValue())
3476         if (Instruction *IC = dyn_cast<Instruction>(SI.getCondition()))
3477           if ((IC->getOpcode() == Instruction::SetEQ ||
3478                IC->getOpcode() == Instruction::SetNE) &&
3479               isa<ConstantInt>(IC->getOperand(1)) &&
3480               cast<Constant>(IC->getOperand(1))->isNullValue())
3481             if (Instruction *ICA = dyn_cast<Instruction>(IC->getOperand(0)))
3482               if (ICA->getOpcode() == Instruction::And &&
3483                   isa<ConstantInt>(ICA->getOperand(1)) &&
3484                   (ICA->getOperand(1) == TrueValC ||
3485                    ICA->getOperand(1) == FalseValC) &&
3486                   isOneBitSet(cast<ConstantInt>(ICA->getOperand(1)))) {
3487                 // Okay, now we know that everything is set up, we just don't
3488                 // know whether we have a setne or seteq and whether the true or
3489                 // false val is the zero.
3490                 bool ShouldNotVal = !TrueValC->isNullValue();
3491                 ShouldNotVal ^= IC->getOpcode() == Instruction::SetNE;
3492                 Value *V = ICA;
3493                 if (ShouldNotVal)
3494                   V = InsertNewInstBefore(BinaryOperator::create(
3495                                   Instruction::Xor, V, ICA->getOperand(1)), SI);
3496                 return ReplaceInstUsesWith(SI, V);
3497               }
3498     }
3499
3500   // See if we are selecting two values based on a comparison of the two values.
3501   if (SetCondInst *SCI = dyn_cast<SetCondInst>(CondVal)) {
3502     if (SCI->getOperand(0) == TrueVal && SCI->getOperand(1) == FalseVal) {
3503       // Transform (X == Y) ? X : Y  -> Y
3504       if (SCI->getOpcode() == Instruction::SetEQ)
3505         return ReplaceInstUsesWith(SI, FalseVal);
3506       // Transform (X != Y) ? X : Y  -> X
3507       if (SCI->getOpcode() == Instruction::SetNE)
3508         return ReplaceInstUsesWith(SI, TrueVal);
3509       // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
3510
3511     } else if (SCI->getOperand(0) == FalseVal && SCI->getOperand(1) == TrueVal){
3512       // Transform (X == Y) ? Y : X  -> X
3513       if (SCI->getOpcode() == Instruction::SetEQ)
3514         return ReplaceInstUsesWith(SI, FalseVal);
3515       // Transform (X != Y) ? Y : X  -> Y
3516       if (SCI->getOpcode() == Instruction::SetNE)
3517         return ReplaceInstUsesWith(SI, TrueVal);
3518       // NOTE: if we wanted to, this is where to detect MIN/MAX/ABS/etc.
3519     }
3520   }
3521
3522   // See if we can fold the select into one of our operands.
3523   if (SI.getType()->isInteger()) {
3524     // See the comment above GetSelectFoldableOperands for a description of the
3525     // transformation we are doing here.
3526     if (Instruction *TVI = dyn_cast<Instruction>(TrueVal))
3527       if (TVI->hasOneUse() && TVI->getNumOperands() == 2 &&
3528           !isa<Constant>(FalseVal))
3529         if (unsigned SFO = GetSelectFoldableOperands(TVI)) {
3530           unsigned OpToFold = 0;
3531           if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
3532             OpToFold = 1;
3533           } else  if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
3534             OpToFold = 2;
3535           }
3536
3537           if (OpToFold) {
3538             Constant *C = GetSelectFoldableConstant(TVI);
3539             std::string Name = TVI->getName(); TVI->setName("");
3540             Instruction *NewSel =
3541               new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C,
3542                              Name);
3543             InsertNewInstBefore(NewSel, SI);
3544             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
3545               return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel);
3546             else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI))
3547               return new ShiftInst(SI->getOpcode(), FalseVal, NewSel);
3548             else {
3549               assert(0 && "Unknown instruction!!");
3550             }
3551           }
3552         }
3553
3554     if (Instruction *FVI = dyn_cast<Instruction>(FalseVal))
3555       if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
3556           !isa<Constant>(TrueVal))
3557         if (unsigned SFO = GetSelectFoldableOperands(FVI)) {
3558           unsigned OpToFold = 0;
3559           if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
3560             OpToFold = 1;
3561           } else  if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
3562             OpToFold = 2;
3563           }
3564
3565           if (OpToFold) {
3566             Constant *C = GetSelectFoldableConstant(FVI);
3567             std::string Name = FVI->getName(); FVI->setName("");
3568             Instruction *NewSel =
3569               new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold),
3570                              Name);
3571             InsertNewInstBefore(NewSel, SI);
3572             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
3573               return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel);
3574             else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI))
3575               return new ShiftInst(SI->getOpcode(), TrueVal, NewSel);
3576             else {
3577               assert(0 && "Unknown instruction!!");
3578             }
3579           }
3580         }
3581   }
3582   return 0;
3583 }
3584
3585
3586 // CallInst simplification
3587 //
3588 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
3589   // Intrinsics cannot occur in an invoke, so handle them here instead of in
3590   // visitCallSite.
3591   if (MemIntrinsic *MI = dyn_cast<MemIntrinsic>(&CI)) {
3592     bool Changed = false;
3593
3594     // memmove/cpy/set of zero bytes is a noop.
3595     if (Constant *NumBytes = dyn_cast<Constant>(MI->getLength())) {
3596       if (NumBytes->isNullValue()) return EraseInstFromFunction(CI);
3597
3598       // FIXME: Increase alignment here.
3599
3600       if (ConstantInt *CI = dyn_cast<ConstantInt>(NumBytes))
3601         if (CI->getRawValue() == 1) {
3602           // Replace the instruction with just byte operations.  We would
3603           // transform other cases to loads/stores, but we don't know if
3604           // alignment is sufficient.
3605         }
3606     }
3607
3608     // If we have a memmove and the source operation is a constant global,
3609     // then the source and dest pointers can't alias, so we can change this
3610     // into a call to memcpy.
3611     if (MemMoveInst *MMI = dyn_cast<MemMoveInst>(MI))
3612       if (GlobalVariable *GVSrc = dyn_cast<GlobalVariable>(MMI->getSource()))
3613         if (GVSrc->isConstant()) {
3614           Module *M = CI.getParent()->getParent()->getParent();
3615           Function *MemCpy = M->getOrInsertFunction("llvm.memcpy",
3616                                      CI.getCalledFunction()->getFunctionType());
3617           CI.setOperand(0, MemCpy);
3618           Changed = true;
3619         }
3620
3621     if (Changed) return &CI;
3622   } else if (DbgStopPointInst *SPI = dyn_cast<DbgStopPointInst>(&CI)) {
3623     // If this stoppoint is at the same source location as the previous
3624     // stoppoint in the chain, it is not needed.
3625     if (DbgStopPointInst *PrevSPI =
3626         dyn_cast<DbgStopPointInst>(SPI->getChain()))
3627       if (SPI->getLineNo() == PrevSPI->getLineNo() &&
3628           SPI->getColNo() == PrevSPI->getColNo()) {
3629         SPI->replaceAllUsesWith(PrevSPI);
3630         return EraseInstFromFunction(CI);
3631       }
3632   }
3633
3634   return visitCallSite(&CI);
3635 }
3636
3637 // InvokeInst simplification
3638 //
3639 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
3640   return visitCallSite(&II);
3641 }
3642
3643 // visitCallSite - Improvements for call and invoke instructions.
3644 //
3645 Instruction *InstCombiner::visitCallSite(CallSite CS) {
3646   bool Changed = false;
3647
3648   // If the callee is a constexpr cast of a function, attempt to move the cast
3649   // to the arguments of the call/invoke.
3650   if (transformConstExprCastCall(CS)) return 0;
3651
3652   Value *Callee = CS.getCalledValue();
3653
3654   if (isa<ConstantPointerNull>(Callee) || isa<UndefValue>(Callee)) {
3655     // This instruction is not reachable, just remove it.  We insert a store to
3656     // undef so that we know that this code is not reachable, despite the fact
3657     // that we can't modify the CFG here.
3658     new StoreInst(ConstantBool::True,
3659                   UndefValue::get(PointerType::get(Type::BoolTy)),
3660                   CS.getInstruction());
3661
3662     if (!CS.getInstruction()->use_empty())
3663       CS.getInstruction()->
3664         replaceAllUsesWith(UndefValue::get(CS.getInstruction()->getType()));
3665
3666     if (InvokeInst *II = dyn_cast<InvokeInst>(CS.getInstruction())) {
3667       // Don't break the CFG, insert a dummy cond branch.
3668       new BranchInst(II->getNormalDest(), II->getUnwindDest(),
3669                      ConstantBool::True, II);
3670     }
3671     return EraseInstFromFunction(*CS.getInstruction());
3672   }
3673
3674   const PointerType *PTy = cast<PointerType>(Callee->getType());
3675   const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
3676   if (FTy->isVarArg()) {
3677     // See if we can optimize any arguments passed through the varargs area of
3678     // the call.
3679     for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(),
3680            E = CS.arg_end(); I != E; ++I)
3681       if (CastInst *CI = dyn_cast<CastInst>(*I)) {
3682         // If this cast does not effect the value passed through the varargs
3683         // area, we can eliminate the use of the cast.
3684         Value *Op = CI->getOperand(0);
3685         if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) {
3686           *I = Op;
3687           Changed = true;
3688         }
3689       }
3690   }
3691
3692   return Changed ? CS.getInstruction() : 0;
3693 }
3694
3695 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
3696 // attempt to move the cast to the arguments of the call/invoke.
3697 //
3698 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
3699   if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
3700   ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
3701   if (CE->getOpcode() != Instruction::Cast || !isa<Function>(CE->getOperand(0)))
3702     return false;
3703   Function *Callee = cast<Function>(CE->getOperand(0));
3704   Instruction *Caller = CS.getInstruction();
3705
3706   // Okay, this is a cast from a function to a different type.  Unless doing so
3707   // would cause a type conversion of one of our arguments, change this call to
3708   // be a direct call with arguments casted to the appropriate types.
3709   //
3710   const FunctionType *FT = Callee->getFunctionType();
3711   const Type *OldRetTy = Caller->getType();
3712
3713   // Check to see if we are changing the return type...
3714   if (OldRetTy != FT->getReturnType()) {
3715     if (Callee->isExternal() &&
3716         !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) &&
3717         !Caller->use_empty())
3718       return false;   // Cannot transform this return value...
3719
3720     // If the callsite is an invoke instruction, and the return value is used by
3721     // a PHI node in a successor, we cannot change the return type of the call
3722     // because there is no place to put the cast instruction (without breaking
3723     // the critical edge).  Bail out in this case.
3724     if (!Caller->use_empty())
3725       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller))
3726         for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
3727              UI != E; ++UI)
3728           if (PHINode *PN = dyn_cast<PHINode>(*UI))
3729             if (PN->getParent() == II->getNormalDest() ||
3730                 PN->getParent() == II->getUnwindDest())
3731               return false;
3732   }
3733
3734   unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
3735   unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
3736
3737   CallSite::arg_iterator AI = CS.arg_begin();
3738   for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
3739     const Type *ParamTy = FT->getParamType(i);
3740     bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
3741     if (Callee->isExternal() && !isConvertible) return false;
3742   }
3743
3744   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
3745       Callee->isExternal())
3746     return false;   // Do not delete arguments unless we have a function body...
3747
3748   // Okay, we decided that this is a safe thing to do: go ahead and start
3749   // inserting cast instructions as necessary...
3750   std::vector<Value*> Args;
3751   Args.reserve(NumActualArgs);
3752
3753   AI = CS.arg_begin();
3754   for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
3755     const Type *ParamTy = FT->getParamType(i);
3756     if ((*AI)->getType() == ParamTy) {
3757       Args.push_back(*AI);
3758     } else {
3759       Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"),
3760                                          *Caller));
3761     }
3762   }
3763
3764   // If the function takes more arguments than the call was taking, add them
3765   // now...
3766   for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
3767     Args.push_back(Constant::getNullValue(FT->getParamType(i)));
3768
3769   // If we are removing arguments to the function, emit an obnoxious warning...
3770   if (FT->getNumParams() < NumActualArgs)
3771     if (!FT->isVarArg()) {
3772       std::cerr << "WARNING: While resolving call to function '"
3773                 << Callee->getName() << "' arguments were dropped!\n";
3774     } else {
3775       // Add all of the arguments in their promoted form to the arg list...
3776       for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
3777         const Type *PTy = getPromotedType((*AI)->getType());
3778         if (PTy != (*AI)->getType()) {
3779           // Must promote to pass through va_arg area!
3780           Instruction *Cast = new CastInst(*AI, PTy, "tmp");
3781           InsertNewInstBefore(Cast, *Caller);
3782           Args.push_back(Cast);
3783         } else {
3784           Args.push_back(*AI);
3785         }
3786       }
3787     }
3788
3789   if (FT->getReturnType() == Type::VoidTy)
3790     Caller->setName("");   // Void type should not have a name...
3791
3792   Instruction *NC;
3793   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
3794     NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
3795                         Args, Caller->getName(), Caller);
3796   } else {
3797     NC = new CallInst(Callee, Args, Caller->getName(), Caller);
3798   }
3799
3800   // Insert a cast of the return type as necessary...
3801   Value *NV = NC;
3802   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
3803     if (NV->getType() != Type::VoidTy) {
3804       NV = NC = new CastInst(NC, Caller->getType(), "tmp");
3805
3806       // If this is an invoke instruction, we should insert it after the first
3807       // non-phi, instruction in the normal successor block.
3808       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
3809         BasicBlock::iterator I = II->getNormalDest()->begin();
3810         while (isa<PHINode>(I)) ++I;
3811         InsertNewInstBefore(NC, *I);
3812       } else {
3813         // Otherwise, it's a call, just insert cast right after the call instr
3814         InsertNewInstBefore(NC, *Caller);
3815       }
3816       AddUsersToWorkList(*Caller);
3817     } else {
3818       NV = UndefValue::get(Caller->getType());
3819     }
3820   }
3821
3822   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
3823     Caller->replaceAllUsesWith(NV);
3824   Caller->getParent()->getInstList().erase(Caller);
3825   removeFromWorkList(Caller);
3826   return true;
3827 }
3828
3829
3830 // FoldPHIArgOpIntoPHI - If all operands to a PHI node are the same "unary"
3831 // operator and they all are only used by the PHI, PHI together their
3832 // inputs, and do the operation once, to the result of the PHI.
3833 Instruction *InstCombiner::FoldPHIArgOpIntoPHI(PHINode &PN) {
3834   Instruction *FirstInst = cast<Instruction>(PN.getIncomingValue(0));
3835
3836   // Scan the instruction, looking for input operations that can be folded away.
3837   // If all input operands to the phi are the same instruction (e.g. a cast from
3838   // the same type or "+42") we can pull the operation through the PHI, reducing
3839   // code size and simplifying code.
3840   Constant *ConstantOp = 0;
3841   const Type *CastSrcTy = 0;
3842   if (isa<CastInst>(FirstInst)) {
3843     CastSrcTy = FirstInst->getOperand(0)->getType();
3844   } else if (isa<BinaryOperator>(FirstInst) || isa<ShiftInst>(FirstInst)) {
3845     // Can fold binop or shift if the RHS is a constant.
3846     ConstantOp = dyn_cast<Constant>(FirstInst->getOperand(1));
3847     if (ConstantOp == 0) return 0;
3848   } else {
3849     return 0;  // Cannot fold this operation.
3850   }
3851
3852   // Check to see if all arguments are the same operation.
3853   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
3854     if (!isa<Instruction>(PN.getIncomingValue(i))) return 0;
3855     Instruction *I = cast<Instruction>(PN.getIncomingValue(i));
3856     if (!I->hasOneUse() || I->getOpcode() != FirstInst->getOpcode())
3857       return 0;
3858     if (CastSrcTy) {
3859       if (I->getOperand(0)->getType() != CastSrcTy)
3860         return 0;  // Cast operation must match.
3861     } else if (I->getOperand(1) != ConstantOp) {
3862       return 0;
3863     }
3864   }
3865
3866   // Okay, they are all the same operation.  Create a new PHI node of the
3867   // correct type, and PHI together all of the LHS's of the instructions.
3868   PHINode *NewPN = new PHINode(FirstInst->getOperand(0)->getType(),
3869                                PN.getName()+".in");
3870   NewPN->op_reserve(PN.getNumOperands());
3871
3872   Value *InVal = FirstInst->getOperand(0);
3873   NewPN->addIncoming(InVal, PN.getIncomingBlock(0));
3874
3875   // Add all operands to the new PHI.
3876   for (unsigned i = 1, e = PN.getNumIncomingValues(); i != e; ++i) {
3877     Value *NewInVal = cast<Instruction>(PN.getIncomingValue(i))->getOperand(0);
3878     if (NewInVal != InVal)
3879       InVal = 0;
3880     NewPN->addIncoming(NewInVal, PN.getIncomingBlock(i));
3881   }
3882
3883   Value *PhiVal;
3884   if (InVal) {
3885     // The new PHI unions all of the same values together.  This is really
3886     // common, so we handle it intelligently here for compile-time speed.
3887     PhiVal = InVal;
3888     delete NewPN;
3889   } else {
3890     InsertNewInstBefore(NewPN, PN);
3891     PhiVal = NewPN;
3892   }
3893
3894   // Insert and return the new operation.
3895   if (isa<CastInst>(FirstInst))
3896     return new CastInst(PhiVal, PN.getType());
3897   else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(FirstInst))
3898     return BinaryOperator::create(BinOp->getOpcode(), PhiVal, ConstantOp);
3899   else
3900     return new ShiftInst(cast<ShiftInst>(FirstInst)->getOpcode(),
3901                          PhiVal, ConstantOp);
3902 }
3903
3904 // PHINode simplification
3905 //
3906 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
3907   if (Value *V = hasConstantValue(&PN)) {
3908     // If V is an instruction, we have to be certain that it dominates PN.
3909     // However, because we don't have dom info, we can't do a perfect job.
3910     if (Instruction *I = dyn_cast<Instruction>(V)) {
3911       // We know that the instruction dominates the PHI if there are no undef
3912       // values coming in.
3913       if (I->getParent() != &I->getParent()->getParent()->front() ||
3914           isa<InvokeInst>(I))
3915         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
3916           if (isa<UndefValue>(PN.getIncomingValue(i))) {
3917             V = 0;
3918             break;
3919           }
3920     }
3921
3922     if (V)
3923       return ReplaceInstUsesWith(PN, V);
3924   }
3925
3926   // If the only user of this instruction is a cast instruction, and all of the
3927   // incoming values are constants, change this PHI to merge together the casted
3928   // constants.
3929   if (PN.hasOneUse())
3930     if (CastInst *CI = dyn_cast<CastInst>(PN.use_back()))
3931       if (CI->getType() != PN.getType()) {  // noop casts will be folded
3932         bool AllConstant = true;
3933         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
3934           if (!isa<Constant>(PN.getIncomingValue(i))) {
3935             AllConstant = false;
3936             break;
3937           }
3938         if (AllConstant) {
3939           // Make a new PHI with all casted values.
3940           PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN);
3941           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
3942             Constant *OldArg = cast<Constant>(PN.getIncomingValue(i));
3943             New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()),
3944                              PN.getIncomingBlock(i));
3945           }
3946
3947           // Update the cast instruction.
3948           CI->setOperand(0, New);
3949           WorkList.push_back(CI);    // revisit the cast instruction to fold.
3950           WorkList.push_back(New);   // Make sure to revisit the new Phi
3951           return &PN;                // PN is now dead!
3952         }
3953       }
3954
3955   // If all PHI operands are the same operation, pull them through the PHI,
3956   // reducing code size.
3957   if (isa<Instruction>(PN.getIncomingValue(0)) &&
3958       PN.getIncomingValue(0)->hasOneUse())
3959     if (Instruction *Result = FoldPHIArgOpIntoPHI(PN))
3960       return Result;
3961
3962
3963   return 0;
3964 }
3965
3966 static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy,
3967                                       Instruction *InsertPoint,
3968                                       InstCombiner *IC) {
3969   unsigned PS = IC->getTargetData().getPointerSize();
3970   const Type *VTy = V->getType();
3971   if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS)
3972     // We must insert a cast to ensure we sign-extend.
3973     V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(),
3974                                              V->getName()), *InsertPoint);
3975   return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()),
3976                                  *InsertPoint);
3977 }
3978
3979
3980 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
3981   Value *PtrOp = GEP.getOperand(0);
3982   // Is it 'getelementptr %P, long 0'  or 'getelementptr %P'
3983   // If so, eliminate the noop.
3984   if (GEP.getNumOperands() == 1)
3985     return ReplaceInstUsesWith(GEP, PtrOp);
3986
3987   if (isa<UndefValue>(GEP.getOperand(0)))
3988     return ReplaceInstUsesWith(GEP, UndefValue::get(GEP.getType()));
3989
3990   bool HasZeroPointerIndex = false;
3991   if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
3992     HasZeroPointerIndex = C->isNullValue();
3993
3994   if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
3995     return ReplaceInstUsesWith(GEP, PtrOp);
3996
3997   // Eliminate unneeded casts for indices.
3998   bool MadeChange = false;
3999   gep_type_iterator GTI = gep_type_begin(GEP);
4000   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI)
4001     if (isa<SequentialType>(*GTI)) {
4002       if (CastInst *CI = dyn_cast<CastInst>(GEP.getOperand(i))) {
4003         Value *Src = CI->getOperand(0);
4004         const Type *SrcTy = Src->getType();
4005         const Type *DestTy = CI->getType();
4006         if (Src->getType()->isInteger()) {
4007           if (SrcTy->getPrimitiveSize() == DestTy->getPrimitiveSize()) {
4008             // We can always eliminate a cast from ulong or long to the other.
4009             // We can always eliminate a cast from uint to int or the other on
4010             // 32-bit pointer platforms.
4011             if (DestTy->getPrimitiveSize() >= TD->getPointerSize()) {
4012               MadeChange = true;
4013               GEP.setOperand(i, Src);
4014             }
4015           } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
4016                      SrcTy->getPrimitiveSize() == 4) {
4017             // We can always eliminate a cast from int to [u]long.  We can
4018             // eliminate a cast from uint to [u]long iff the target is a 32-bit
4019             // pointer target.
4020             if (SrcTy->isSigned() ||
4021                 SrcTy->getPrimitiveSize() >= TD->getPointerSize()) {
4022               MadeChange = true;
4023               GEP.setOperand(i, Src);
4024             }
4025           }
4026         }
4027       }
4028       // If we are using a wider index than needed for this platform, shrink it
4029       // to what we need.  If the incoming value needs a cast instruction,
4030       // insert it.  This explicit cast can make subsequent optimizations more
4031       // obvious.
4032       Value *Op = GEP.getOperand(i);
4033       if (Op->getType()->getPrimitiveSize() > TD->getPointerSize())
4034         if (Constant *C = dyn_cast<Constant>(Op)) {
4035           GEP.setOperand(i, ConstantExpr::getCast(C,
4036                                      TD->getIntPtrType()->getSignedVersion()));
4037           MadeChange = true;
4038         } else {
4039           Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(),
4040                                                 Op->getName()), GEP);
4041           GEP.setOperand(i, Op);
4042           MadeChange = true;
4043         }
4044
4045       // If this is a constant idx, make sure to canonicalize it to be a signed
4046       // operand, otherwise CSE and other optimizations are pessimized.
4047       if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op)) {
4048         GEP.setOperand(i, ConstantExpr::getCast(CUI,
4049                                           CUI->getType()->getSignedVersion()));
4050         MadeChange = true;
4051       }
4052     }
4053   if (MadeChange) return &GEP;
4054
4055   // Combine Indices - If the source pointer to this getelementptr instruction
4056   // is a getelementptr instruction, combine the indices of the two
4057   // getelementptr instructions into a single instruction.
4058   //
4059   std::vector<Value*> SrcGEPOperands;
4060   if (User *Src = dyn_castGetElementPtr(PtrOp))
4061     SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
4062
4063   if (!SrcGEPOperands.empty()) {
4064     // Note that if our source is a gep chain itself that we wait for that
4065     // chain to be resolved before we perform this transformation.  This
4066     // avoids us creating a TON of code in some cases.
4067     //
4068     if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
4069         cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
4070       return 0;   // Wait until our source is folded to completion.
4071
4072     std::vector<Value *> Indices;
4073
4074     // Find out whether the last index in the source GEP is a sequential idx.
4075     bool EndsWithSequential = false;
4076     for (gep_type_iterator I = gep_type_begin(*cast<User>(PtrOp)),
4077            E = gep_type_end(*cast<User>(PtrOp)); I != E; ++I)
4078       EndsWithSequential = !isa<StructType>(*I);
4079
4080     // Can we combine the two pointer arithmetics offsets?
4081     if (EndsWithSequential) {
4082       // Replace: gep (gep %P, long B), long A, ...
4083       // With:    T = long A+B; gep %P, T, ...
4084       //
4085       Value *Sum, *SO1 = SrcGEPOperands.back(), *GO1 = GEP.getOperand(1);
4086       if (SO1 == Constant::getNullValue(SO1->getType())) {
4087         Sum = GO1;
4088       } else if (GO1 == Constant::getNullValue(GO1->getType())) {
4089         Sum = SO1;
4090       } else {
4091         // If they aren't the same type, convert both to an integer of the
4092         // target's pointer size.
4093         if (SO1->getType() != GO1->getType()) {
4094           if (Constant *SO1C = dyn_cast<Constant>(SO1)) {
4095             SO1 = ConstantExpr::getCast(SO1C, GO1->getType());
4096           } else if (Constant *GO1C = dyn_cast<Constant>(GO1)) {
4097             GO1 = ConstantExpr::getCast(GO1C, SO1->getType());
4098           } else {
4099             unsigned PS = TD->getPointerSize();
4100             if (SO1->getType()->getPrimitiveSize() == PS) {
4101               // Convert GO1 to SO1's type.
4102               GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this);
4103
4104             } else if (GO1->getType()->getPrimitiveSize() == PS) {
4105               // Convert SO1 to GO1's type.
4106               SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this);
4107             } else {
4108               const Type *PT = TD->getIntPtrType();
4109               SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this);
4110               GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this);
4111             }
4112           }
4113         }
4114         if (isa<Constant>(SO1) && isa<Constant>(GO1))
4115           Sum = ConstantExpr::getAdd(cast<Constant>(SO1), cast<Constant>(GO1));
4116         else {
4117           Sum = BinaryOperator::createAdd(SO1, GO1, PtrOp->getName()+".sum");
4118           InsertNewInstBefore(cast<Instruction>(Sum), GEP);
4119         }
4120       }
4121
4122       // Recycle the GEP we already have if possible.
4123       if (SrcGEPOperands.size() == 2) {
4124         GEP.setOperand(0, SrcGEPOperands[0]);
4125         GEP.setOperand(1, Sum);
4126         return &GEP;
4127       } else {
4128         Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4129                        SrcGEPOperands.end()-1);
4130         Indices.push_back(Sum);
4131         Indices.insert(Indices.end(), GEP.op_begin()+2, GEP.op_end());
4132       }
4133     } else if (isa<Constant>(*GEP.idx_begin()) &&
4134                cast<Constant>(*GEP.idx_begin())->isNullValue() &&
4135                SrcGEPOperands.size() != 1) {
4136       // Otherwise we can do the fold if the first index of the GEP is a zero
4137       Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
4138                      SrcGEPOperands.end());
4139       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
4140     }
4141
4142     if (!Indices.empty())
4143       return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
4144
4145   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(PtrOp)) {
4146     // GEP of global variable.  If all of the indices for this GEP are
4147     // constants, we can promote this to a constexpr instead of an instruction.
4148
4149     // Scan for nonconstants...
4150     std::vector<Constant*> Indices;
4151     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
4152     for (; I != E && isa<Constant>(*I); ++I)
4153       Indices.push_back(cast<Constant>(*I));
4154
4155     if (I == E) {  // If they are all constants...
4156       Constant *CE = ConstantExpr::getGetElementPtr(GV, Indices);
4157
4158       // Replace all uses of the GEP with the new constexpr...
4159       return ReplaceInstUsesWith(GEP, CE);
4160     }
4161   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(PtrOp)) {
4162     if (CE->getOpcode() == Instruction::Cast) {
4163       if (HasZeroPointerIndex) {
4164         // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
4165         // into     : GEP [10 x ubyte]* X, long 0, ...
4166         //
4167         // This occurs when the program declares an array extern like "int X[];"
4168         //
4169         Constant *X = CE->getOperand(0);
4170         const PointerType *CPTy = cast<PointerType>(CE->getType());
4171         if (const PointerType *XTy = dyn_cast<PointerType>(X->getType()))
4172           if (const ArrayType *XATy =
4173               dyn_cast<ArrayType>(XTy->getElementType()))
4174             if (const ArrayType *CATy =
4175                 dyn_cast<ArrayType>(CPTy->getElementType()))
4176               if (CATy->getElementType() == XATy->getElementType()) {
4177                 // At this point, we know that the cast source type is a pointer
4178                 // to an array of the same type as the destination pointer
4179                 // array.  Because the array type is never stepped over (there
4180                 // is a leading zero) we can fold the cast into this GEP.
4181                 GEP.setOperand(0, X);
4182                 return &GEP;
4183               }
4184       } else if (GEP.getNumOperands() == 2 &&
4185                  isa<PointerType>(CE->getOperand(0)->getType())) {
4186         // Transform things like:
4187         // %t = getelementptr ubyte* cast ([2 x sbyte]* %str to ubyte*), uint %V
4188         // into:  %t1 = getelementptr [2 x sbyte*]* %str, int 0, uint %V; cast
4189         Constant *X = CE->getOperand(0);
4190         const Type *SrcElTy = cast<PointerType>(X->getType())->getElementType();
4191         const Type *ResElTy =cast<PointerType>(CE->getType())->getElementType();
4192         if (isa<ArrayType>(SrcElTy) &&
4193             TD->getTypeSize(cast<ArrayType>(SrcElTy)->getElementType()) ==
4194             TD->getTypeSize(ResElTy)) {
4195           Value *V = InsertNewInstBefore(
4196                  new GetElementPtrInst(X, Constant::getNullValue(Type::IntTy),
4197                                        GEP.getOperand(1), GEP.getName()), GEP);
4198           return new CastInst(V, GEP.getType());
4199         }
4200       }
4201     }
4202   }
4203
4204   return 0;
4205 }
4206
4207 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
4208   // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
4209   if (AI.isArrayAllocation())    // Check C != 1
4210     if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
4211       const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
4212       AllocationInst *New = 0;
4213
4214       // Create and insert the replacement instruction...
4215       if (isa<MallocInst>(AI))
4216         New = new MallocInst(NewTy, 0, AI.getName());
4217       else {
4218         assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
4219         New = new AllocaInst(NewTy, 0, AI.getName());
4220       }
4221
4222       InsertNewInstBefore(New, AI);
4223
4224       // Scan to the end of the allocation instructions, to skip over a block of
4225       // allocas if possible...
4226       //
4227       BasicBlock::iterator It = New;
4228       while (isa<AllocationInst>(*It)) ++It;
4229
4230       // Now that I is pointing to the first non-allocation-inst in the block,
4231       // insert our getelementptr instruction...
4232       //
4233       std::vector<Value*> Idx(2, Constant::getNullValue(Type::IntTy));
4234       Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
4235
4236       // Now make everything use the getelementptr instead of the original
4237       // allocation.
4238       return ReplaceInstUsesWith(AI, V);
4239     } else if (isa<UndefValue>(AI.getArraySize())) {
4240       return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4241     }
4242
4243   // If alloca'ing a zero byte object, replace the alloca with a null pointer.
4244   // Note that we only do this for alloca's, because malloc should allocate and
4245   // return a unique pointer, even for a zero byte allocation.
4246   if (isa<AllocaInst>(AI) && AI.getAllocatedType()->isSized() &&
4247       TD->getTypeSize(AI.getAllocatedType()) == 0)
4248     return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
4249
4250   return 0;
4251 }
4252
4253 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) {
4254   Value *Op = FI.getOperand(0);
4255
4256   // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X
4257   if (CastInst *CI = dyn_cast<CastInst>(Op))
4258     if (isa<PointerType>(CI->getOperand(0)->getType())) {
4259       FI.setOperand(0, CI->getOperand(0));
4260       return &FI;
4261     }
4262
4263   // free undef -> unreachable.
4264   if (isa<UndefValue>(Op)) {
4265     // Insert a new store to null because we cannot modify the CFG here.
4266     new StoreInst(ConstantBool::True,
4267                   UndefValue::get(PointerType::get(Type::BoolTy)), &FI);
4268     return EraseInstFromFunction(FI);
4269   }
4270
4271   // If we have 'free null' delete the instruction.  This can happen in stl code
4272   // when lots of inlining happens.
4273   if (isa<ConstantPointerNull>(Op))
4274     return EraseInstFromFunction(FI);
4275
4276   return 0;
4277 }
4278
4279
4280 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
4281 /// constantexpr, return the constant value being addressed by the constant
4282 /// expression, or null if something is funny.
4283 ///
4284 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
4285   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
4286     return 0;  // Do not allow stepping over the value!
4287
4288   // Loop over all of the operands, tracking down which value we are
4289   // addressing...
4290   gep_type_iterator I = gep_type_begin(CE), E = gep_type_end(CE);
4291   for (++I; I != E; ++I)
4292     if (const StructType *STy = dyn_cast<StructType>(*I)) {
4293       ConstantUInt *CU = cast<ConstantUInt>(I.getOperand());
4294       assert(CU->getValue() < STy->getNumElements() &&
4295              "Struct index out of range!");
4296       unsigned El = (unsigned)CU->getValue();
4297       if (ConstantStruct *CS = dyn_cast<ConstantStruct>(C)) {
4298         C = CS->getOperand(El);
4299       } else if (isa<ConstantAggregateZero>(C)) {
4300         C = Constant::getNullValue(STy->getElementType(El));
4301       } else if (isa<UndefValue>(C)) {
4302         C = UndefValue::get(STy->getElementType(El));
4303       } else {
4304         return 0;
4305       }
4306     } else if (ConstantInt *CI = dyn_cast<ConstantInt>(I.getOperand())) {
4307       const ArrayType *ATy = cast<ArrayType>(*I);
4308       if ((uint64_t)CI->getRawValue() >= ATy->getNumElements()) return 0;
4309       if (ConstantArray *CA = dyn_cast<ConstantArray>(C))
4310         C = CA->getOperand((unsigned)CI->getRawValue());
4311       else if (isa<ConstantAggregateZero>(C))
4312         C = Constant::getNullValue(ATy->getElementType());
4313       else if (isa<UndefValue>(C))
4314         C = UndefValue::get(ATy->getElementType());
4315       else
4316         return 0;
4317     } else {
4318       return 0;
4319     }
4320   return C;
4321 }
4322
4323 static Instruction *InstCombineLoadCast(InstCombiner &IC, LoadInst &LI) {
4324   User *CI = cast<User>(LI.getOperand(0));
4325
4326   const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
4327   if (const PointerType *SrcTy =
4328       dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
4329     const Type *SrcPTy = SrcTy->getElementType();
4330     if (SrcPTy->isSized() && DestPTy->isSized() &&
4331         IC.getTargetData().getTypeSize(SrcPTy) ==
4332             IC.getTargetData().getTypeSize(DestPTy) &&
4333         (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
4334         (DestPTy->isInteger() || isa<PointerType>(DestPTy))) {
4335       // Okay, we are casting from one integer or pointer type to another of
4336       // the same size.  Instead of casting the pointer before the load, cast
4337       // the result of the loaded value.
4338       Value *NewLoad = IC.InsertNewInstBefore(new LoadInst(CI->getOperand(0),
4339                                                            CI->getName(),
4340                                                            LI.isVolatile()),LI);
4341       // Now cast the result of the load.
4342       return new CastInst(NewLoad, LI.getType());
4343     }
4344   }
4345   return 0;
4346 }
4347
4348 /// isSafeToLoadUnconditionally - Return true if we know that executing a load
4349 /// from this value cannot trap.  If it is not obviously safe to load from the
4350 /// specified pointer, we do a quick local scan of the basic block containing
4351 /// ScanFrom, to determine if the address is already accessed.
4352 static bool isSafeToLoadUnconditionally(Value *V, Instruction *ScanFrom) {
4353   // If it is an alloca or global variable, it is always safe to load from.
4354   if (isa<AllocaInst>(V) || isa<GlobalVariable>(V)) return true;
4355
4356   // Otherwise, be a little bit agressive by scanning the local block where we
4357   // want to check to see if the pointer is already being loaded or stored
4358   // from/to.  If so, the previous load or store would have already trapped,
4359   // so there is no harm doing an extra load (also, CSE will later eliminate
4360   // the load entirely).
4361   BasicBlock::iterator BBI = ScanFrom, E = ScanFrom->getParent()->begin();
4362
4363   while (BBI != E) {
4364     --BBI;
4365
4366     if (LoadInst *LI = dyn_cast<LoadInst>(BBI)) {
4367       if (LI->getOperand(0) == V) return true;
4368     } else if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
4369       if (SI->getOperand(1) == V) return true;
4370
4371   }
4372   return false;
4373 }
4374
4375 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
4376   Value *Op = LI.getOperand(0);
4377
4378   if (Constant *C = dyn_cast<Constant>(Op)) {
4379     if ((C->isNullValue() || isa<UndefValue>(C)) &&
4380         !LI.isVolatile()) {                          // load null/undef -> undef
4381       // Insert a new store to null instruction before the load to indicate that
4382       // this code is not reachable.  We do this instead of inserting an
4383       // unreachable instruction directly because we cannot modify the CFG.
4384       new StoreInst(UndefValue::get(LI.getType()), C, &LI);
4385       return ReplaceInstUsesWith(LI, UndefValue::get(LI.getType()));
4386     }
4387
4388     // Instcombine load (constant global) into the value loaded.
4389     if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
4390       if (GV->isConstant() && !GV->isExternal())
4391         return ReplaceInstUsesWith(LI, GV->getInitializer());
4392
4393     // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded.
4394     if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
4395       if (CE->getOpcode() == Instruction::GetElementPtr) {
4396         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(CE->getOperand(0)))
4397           if (GV->isConstant() && !GV->isExternal())
4398             if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
4399               return ReplaceInstUsesWith(LI, V);
4400       } else if (CE->getOpcode() == Instruction::Cast) {
4401         if (Instruction *Res = InstCombineLoadCast(*this, LI))
4402           return Res;
4403       }
4404   }
4405
4406   // load (cast X) --> cast (load X) iff safe
4407   if (CastInst *CI = dyn_cast<CastInst>(Op))
4408     if (Instruction *Res = InstCombineLoadCast(*this, LI))
4409       return Res;
4410
4411   if (!LI.isVolatile() && Op->hasOneUse()) {
4412     // Change select and PHI nodes to select values instead of addresses: this
4413     // helps alias analysis out a lot, allows many others simplifications, and
4414     // exposes redundancy in the code.
4415     //
4416     // Note that we cannot do the transformation unless we know that the
4417     // introduced loads cannot trap!  Something like this is valid as long as
4418     // the condition is always false: load (select bool %C, int* null, int* %G),
4419     // but it would not be valid if we transformed it to load from null
4420     // unconditionally.
4421     //
4422     if (SelectInst *SI = dyn_cast<SelectInst>(Op)) {
4423       // load (select (Cond, &V1, &V2))  --> select(Cond, load &V1, load &V2).
4424       if (isSafeToLoadUnconditionally(SI->getOperand(1), SI) &&
4425           isSafeToLoadUnconditionally(SI->getOperand(2), SI)) {
4426         Value *V1 = InsertNewInstBefore(new LoadInst(SI->getOperand(1),
4427                                      SI->getOperand(1)->getName()+".val"), LI);
4428         Value *V2 = InsertNewInstBefore(new LoadInst(SI->getOperand(2),
4429                                      SI->getOperand(2)->getName()+".val"), LI);
4430         return new SelectInst(SI->getCondition(), V1, V2);
4431       }
4432
4433       // load (select (cond, null, P)) -> load P
4434       if (Constant *C = dyn_cast<Constant>(SI->getOperand(1)))
4435         if (C->isNullValue()) {
4436           LI.setOperand(0, SI->getOperand(2));
4437           return &LI;
4438         }
4439
4440       // load (select (cond, P, null)) -> load P
4441       if (Constant *C = dyn_cast<Constant>(SI->getOperand(2)))
4442         if (C->isNullValue()) {
4443           LI.setOperand(0, SI->getOperand(1));
4444           return &LI;
4445         }
4446
4447     } else if (PHINode *PN = dyn_cast<PHINode>(Op)) {
4448       // load (phi (&V1, &V2, &V3))  --> phi(load &V1, load &V2, load &V3)
4449       bool Safe = PN->getParent() == LI.getParent();
4450
4451       // Scan all of the instructions between the PHI and the load to make
4452       // sure there are no instructions that might possibly alter the value
4453       // loaded from the PHI.
4454       if (Safe) {
4455         BasicBlock::iterator I = &LI;
4456         for (--I; !isa<PHINode>(I); --I)
4457           if (isa<StoreInst>(I) || isa<CallInst>(I)) {
4458             Safe = false;
4459             break;
4460           }
4461       }
4462
4463       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e && Safe; ++i)
4464         if (!isSafeToLoadUnconditionally(PN->getIncomingValue(i),
4465                                     PN->getIncomingBlock(i)->getTerminator()))
4466           Safe = false;
4467
4468       if (Safe) {
4469         // Create the PHI.
4470         PHINode *NewPN = new PHINode(LI.getType(), PN->getName());
4471         InsertNewInstBefore(NewPN, *PN);
4472         std::map<BasicBlock*,Value*> LoadMap;  // Don't insert duplicate loads
4473
4474         for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) {
4475           BasicBlock *BB = PN->getIncomingBlock(i);
4476           Value *&TheLoad = LoadMap[BB];
4477           if (TheLoad == 0) {
4478             Value *InVal = PN->getIncomingValue(i);
4479             TheLoad = InsertNewInstBefore(new LoadInst(InVal,
4480                                                        InVal->getName()+".val"),
4481                                           *BB->getTerminator());
4482           }
4483           NewPN->addIncoming(TheLoad, BB);
4484         }
4485         return ReplaceInstUsesWith(LI, NewPN);
4486       }
4487     }
4488   }
4489   return 0;
4490 }
4491
4492 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
4493   // Change br (not X), label True, label False to: br X, label False, True
4494   Value *X;
4495   BasicBlock *TrueDest;
4496   BasicBlock *FalseDest;
4497   if (match(&BI, m_Br(m_Not(m_Value(X)), TrueDest, FalseDest)) &&
4498       !isa<Constant>(X)) {
4499     // Swap Destinations and condition...
4500     BI.setCondition(X);
4501     BI.setSuccessor(0, FalseDest);
4502     BI.setSuccessor(1, TrueDest);
4503     return &BI;
4504   }
4505
4506   // Cannonicalize setne -> seteq
4507   Instruction::BinaryOps Op; Value *Y;
4508   if (match(&BI, m_Br(m_SetCond(Op, m_Value(X), m_Value(Y)),
4509                       TrueDest, FalseDest)))
4510     if ((Op == Instruction::SetNE || Op == Instruction::SetLE ||
4511          Op == Instruction::SetGE) && BI.getCondition()->hasOneUse()) {
4512       SetCondInst *I = cast<SetCondInst>(BI.getCondition());
4513       std::string Name = I->getName(); I->setName("");
4514       Instruction::BinaryOps NewOpcode = SetCondInst::getInverseCondition(Op);
4515       Value *NewSCC =  BinaryOperator::create(NewOpcode, X, Y, Name, I);
4516       // Swap Destinations and condition...
4517       BI.setCondition(NewSCC);
4518       BI.setSuccessor(0, FalseDest);
4519       BI.setSuccessor(1, TrueDest);
4520       removeFromWorkList(I);
4521       I->getParent()->getInstList().erase(I);
4522       WorkList.push_back(cast<Instruction>(NewSCC));
4523       return &BI;
4524     }
4525
4526   return 0;
4527 }
4528
4529 Instruction *InstCombiner::visitSwitchInst(SwitchInst &SI) {
4530   Value *Cond = SI.getCondition();
4531   if (Instruction *I = dyn_cast<Instruction>(Cond)) {
4532     if (I->getOpcode() == Instruction::Add)
4533       if (ConstantInt *AddRHS = dyn_cast<ConstantInt>(I->getOperand(1))) {
4534         // change 'switch (X+4) case 1:' into 'switch (X) case -3'
4535         for (unsigned i = 2, e = SI.getNumOperands(); i != e; i += 2)
4536           SI.setOperand(i,ConstantExpr::getSub(cast<Constant>(SI.getOperand(i)),
4537                                                 AddRHS));
4538         SI.setOperand(0, I->getOperand(0));
4539         WorkList.push_back(I);
4540         return &SI;
4541       }
4542   }
4543   return 0;
4544 }
4545
4546
4547 void InstCombiner::removeFromWorkList(Instruction *I) {
4548   WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
4549                  WorkList.end());
4550 }
4551
4552
4553 /// TryToSinkInstruction - Try to move the specified instruction from its
4554 /// current block into the beginning of DestBlock, which can only happen if it's
4555 /// safe to move the instruction past all of the instructions between it and the
4556 /// end of its block.
4557 static bool TryToSinkInstruction(Instruction *I, BasicBlock *DestBlock) {
4558   assert(I->hasOneUse() && "Invariants didn't hold!");
4559
4560   // Cannot move control-flow-involving instructions.
4561   if (isa<PHINode>(I) || isa<InvokeInst>(I) || isa<CallInst>(I)) return false;
4562
4563   // Do not sink alloca instructions out of the entry block.
4564   if (isa<AllocaInst>(I) && I->getParent() == &DestBlock->getParent()->front())
4565     return false;
4566
4567   // We can only sink load instructions if there is nothing between the load and
4568   // the end of block that could change the value.
4569   if (LoadInst *LI = dyn_cast<LoadInst>(I)) {
4570     if (LI->isVolatile()) return false;  // Don't sink volatile loads.
4571
4572     for (BasicBlock::iterator Scan = LI, E = LI->getParent()->end();
4573          Scan != E; ++Scan)
4574       if (Scan->mayWriteToMemory())
4575         return false;
4576   }
4577
4578   BasicBlock::iterator InsertPos = DestBlock->begin();
4579   while (isa<PHINode>(InsertPos)) ++InsertPos;
4580
4581   BasicBlock *SrcBlock = I->getParent();
4582   DestBlock->getInstList().splice(InsertPos, SrcBlock->getInstList(), I);
4583   ++NumSunkInst;
4584   return true;
4585 }
4586
4587 bool InstCombiner::runOnFunction(Function &F) {
4588   bool Changed = false;
4589   TD = &getAnalysis<TargetData>();
4590
4591   for (inst_iterator i = inst_begin(F), e = inst_end(F); i != e; ++i)
4592     WorkList.push_back(&*i);
4593
4594
4595   while (!WorkList.empty()) {
4596     Instruction *I = WorkList.back();  // Get an instruction from the worklist
4597     WorkList.pop_back();
4598
4599     // Check to see if we can DCE or ConstantPropagate the instruction...
4600     // Check to see if we can DIE the instruction...
4601     if (isInstructionTriviallyDead(I)) {
4602       // Add operands to the worklist...
4603       if (I->getNumOperands() < 4)
4604         AddUsesToWorkList(*I);
4605       ++NumDeadInst;
4606
4607       I->getParent()->getInstList().erase(I);
4608       removeFromWorkList(I);
4609       continue;
4610     }
4611
4612     // Instruction isn't dead, see if we can constant propagate it...
4613     if (Constant *C = ConstantFoldInstruction(I)) {
4614       Value* Ptr = I->getOperand(0);
4615       if (isa<GetElementPtrInst>(I) &&
4616           cast<Constant>(Ptr)->isNullValue() &&
4617           !isa<ConstantPointerNull>(C) &&
4618           cast<PointerType>(Ptr->getType())->getElementType()->isSized()) {
4619         // If this is a constant expr gep that is effectively computing an
4620         // "offsetof", fold it into 'cast int X to T*' instead of 'gep 0, 0, 12'
4621         bool isFoldableGEP = true;
4622         for (unsigned i = 1, e = I->getNumOperands(); i != e; ++i)
4623           if (!isa<ConstantInt>(I->getOperand(i)))
4624             isFoldableGEP = false;
4625         if (isFoldableGEP) {
4626           uint64_t Offset = TD->getIndexedOffset(Ptr->getType(),
4627                              std::vector<Value*>(I->op_begin()+1, I->op_end()));
4628           C = ConstantUInt::get(Type::ULongTy, Offset);
4629           C = ConstantExpr::getCast(C, TD->getIntPtrType());
4630           C = ConstantExpr::getCast(C, I->getType());
4631         }
4632       }
4633
4634       // Add operands to the worklist...
4635       AddUsesToWorkList(*I);
4636       ReplaceInstUsesWith(*I, C);
4637
4638       ++NumConstProp;
4639       I->getParent()->getInstList().erase(I);
4640       removeFromWorkList(I);
4641       continue;
4642     }
4643
4644     // See if we can trivially sink this instruction to a successor basic block.
4645     if (I->hasOneUse()) {
4646       BasicBlock *BB = I->getParent();
4647       BasicBlock *UserParent = cast<Instruction>(I->use_back())->getParent();
4648       if (UserParent != BB) {
4649         bool UserIsSuccessor = false;
4650         // See if the user is one of our successors.
4651         for (succ_iterator SI = succ_begin(BB), E = succ_end(BB); SI != E; ++SI)
4652           if (*SI == UserParent) {
4653             UserIsSuccessor = true;
4654             break;
4655           }
4656
4657         // If the user is one of our immediate successors, and if that successor
4658         // only has us as a predecessors (we'd have to split the critical edge
4659         // otherwise), we can keep going.
4660         if (UserIsSuccessor && !isa<PHINode>(I->use_back()) &&
4661             next(pred_begin(UserParent)) == pred_end(UserParent))
4662           // Okay, the CFG is simple enough, try to sink this instruction.
4663           Changed |= TryToSinkInstruction(I, UserParent);
4664       }
4665     }
4666
4667     // Now that we have an instruction, try combining it to simplify it...
4668     if (Instruction *Result = visit(*I)) {
4669       ++NumCombined;
4670       // Should we replace the old instruction with a new one?
4671       if (Result != I) {
4672         DEBUG(std::cerr << "IC: Old = " << *I
4673                         << "    New = " << *Result);
4674
4675         // Everything uses the new instruction now.
4676         I->replaceAllUsesWith(Result);
4677
4678         // Push the new instruction and any users onto the worklist.
4679         WorkList.push_back(Result);
4680         AddUsersToWorkList(*Result);
4681
4682         // Move the name to the new instruction first...
4683         std::string OldName = I->getName(); I->setName("");
4684         Result->setName(OldName);
4685
4686         // Insert the new instruction into the basic block...
4687         BasicBlock *InstParent = I->getParent();
4688         BasicBlock::iterator InsertPos = I;
4689
4690         if (!isa<PHINode>(Result))        // If combining a PHI, don't insert
4691           while (isa<PHINode>(InsertPos)) // middle of a block of PHIs.
4692             ++InsertPos;
4693
4694         InstParent->getInstList().insert(InsertPos, Result);
4695
4696         // Make sure that we reprocess all operands now that we reduced their
4697         // use counts.
4698         for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
4699           if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
4700             WorkList.push_back(OpI);
4701
4702         // Instructions can end up on the worklist more than once.  Make sure
4703         // we do not process an instruction that has been deleted.
4704         removeFromWorkList(I);
4705
4706         // Erase the old instruction.
4707         InstParent->getInstList().erase(I);
4708       } else {
4709         DEBUG(std::cerr << "IC: MOD = " << *I);
4710
4711         // If the instruction was modified, it's possible that it is now dead.
4712         // if so, remove it.
4713         if (isInstructionTriviallyDead(I)) {
4714           // Make sure we process all operands now that we are reducing their
4715           // use counts.
4716           for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
4717             if (Instruction *OpI = dyn_cast<Instruction>(I->getOperand(i)))
4718               WorkList.push_back(OpI);
4719
4720           // Instructions may end up in the worklist more than once.  Erase all
4721           // occurrances of this instruction.
4722           removeFromWorkList(I);
4723           I->getParent()->getInstList().erase(I);
4724         } else {
4725           WorkList.push_back(Result);
4726           AddUsersToWorkList(*Result);
4727         }
4728       }
4729       Changed = true;
4730     }
4731   }
4732
4733   return Changed;
4734 }
4735
4736 FunctionPass *llvm::createInstructionCombiningPass() {
4737   return new InstCombiner();
4738 }
4739