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