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 1, %X
  16 //    %Z = add int 1, %Y
  17 // into:
  18 //    %Z = add int 2, %X
  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 //    N. This list is incomplete
  33 //
  34 //===----------------------------------------------------------------------===//
  35
  36 #define DEBUG_TYPE "instcombine"
  37 #include "llvm/Transforms/Scalar.h"
  38 #include "llvm/Instructions.h"
  39 #include "llvm/Intrinsics.h"
  40 #include "llvm/Pass.h"
  41 #include "llvm/Constants.h"
  42 #include "llvm/DerivedTypes.h"
  43 #include "llvm/GlobalVariable.h"
  44 #include "llvm/Target/TargetData.h"
  45 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  46 #include "llvm/Transforms/Utils/Local.h"
  47 #include "llvm/Support/CallSite.h"
  48 #include "llvm/Support/GetElementPtrTypeIterator.h"
  49 #include "llvm/Support/InstIterator.h"
  50 #include "llvm/Support/InstVisitor.h"
  51 #include "Support/Debug.h"
  52 #include "Support/Statistic.h"
  53 #include <algorithm>
  54 using namespace llvm;
  55
  56 namespace {
  57   Statistic<> NumCombined ("instcombine", "Number of insts combined");
  58   Statistic<> NumConstProp("instcombine", "Number of constant folds");
  59   Statistic<> NumDeadInst ("instcombine", "Number of dead inst eliminated");
  60
  61   class InstCombiner : public FunctionPass,
  62                        public InstVisitor<InstCombiner, Instruction*> {
  63     // Worklist of all of the instructions that need to be simplified.
  64     std::vector<Instruction*> WorkList;
  65     TargetData *TD;
  66
  67     /// AddUsersToWorkList - When an instruction is simplified, add all users of
  68     /// the instruction to the work lists because they might get more simplified
  69     /// now.
  70     ///
  71     void AddUsersToWorkList(Instruction &I) {
  72       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
  73            UI != UE; ++UI)
  74         WorkList.push_back(cast<Instruction>(*UI));
  75     }
  76
  77     /// AddUsesToWorkList - When an instruction is simplified, add operands to
  78     /// the work lists because they might get more simplified now.
  79     ///
  80     void AddUsesToWorkList(Instruction &I) {
  81       for (unsigned i = 0, e = I.getNumOperands(); i != e; ++i)
  82         if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(i)))
  83           WorkList.push_back(Op);
  84     }
  85
  86     // removeFromWorkList - remove all instances of I from the worklist.
  87     void removeFromWorkList(Instruction *I);
  88   public:
  89     virtual bool runOnFunction(Function &F);
  90
  91     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  92       AU.addRequired<TargetData>();
  93       AU.setPreservesCFG();
  94     }
  95
  96     TargetData &getTargetData() const { return *TD; }
  97
  98     // Visitation implementation - Implement instruction combining for different
  99     // instruction types.  The semantics are as follows:
 100     // Return Value:
 101     //    null        - No change was made
 102     //     I          - Change was made, I is still valid, I may be dead though
 103     //   otherwise    - Change was made, replace I with returned instruction
 104     //
 105     Instruction *visitAdd(BinaryOperator &I);
 106     Instruction *visitSub(BinaryOperator &I);
 107     Instruction *visitMul(BinaryOperator &I);
 108     Instruction *visitDiv(BinaryOperator &I);
 109     Instruction *visitRem(BinaryOperator &I);
 110     Instruction *visitAnd(BinaryOperator &I);
 111     Instruction *visitOr (BinaryOperator &I);
 112     Instruction *visitXor(BinaryOperator &I);
 113     Instruction *visitSetCondInst(BinaryOperator &I);
 114     Instruction *visitShiftInst(ShiftInst &I);
 115     Instruction *visitCastInst(CastInst &CI);
 116     Instruction *visitSelectInst(SelectInst &CI);
 117     Instruction *visitCallInst(CallInst &CI);
 118     Instruction *visitInvokeInst(InvokeInst &II);
 119     Instruction *visitPHINode(PHINode &PN);
 120     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
 121     Instruction *visitAllocationInst(AllocationInst &AI);
 122     Instruction *visitFreeInst(FreeInst &FI);
 123     Instruction *visitLoadInst(LoadInst &LI);
 124     Instruction *visitBranchInst(BranchInst &BI);
 125
 126     // visitInstruction - Specify what to return for unhandled instructions...
 127     Instruction *visitInstruction(Instruction &I) { return 0; }
 128
 129   private:
 130     Instruction *visitCallSite(CallSite CS);
 131     bool transformConstExprCastCall(CallSite CS);
 132
 133   public:
 134     // InsertNewInstBefore - insert an instruction New before instruction Old
 135     // in the program.  Add the new instruction to the worklist.
 136     //
 137     Value *InsertNewInstBefore(Instruction *New, Instruction &Old) {
 138       assert(New && New->getParent() == 0 &&
 139              "New instruction already inserted into a basic block!");
 140       BasicBlock *BB = Old.getParent();
 141       BB->getInstList().insert(&Old, New);  // Insert inst
 142       WorkList.push_back(New);              // Add to worklist
 143       return New;
 144     }
 145
 146     // ReplaceInstUsesWith - This method is to be used when an instruction is
 147     // found to be dead, replacable with another preexisting expression.  Here
 148     // we add all uses of I to the worklist, replace all uses of I with the new
 149     // value, then return I, so that the inst combiner will know that I was
 150     // modified.
 151     //
 152     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
 153       AddUsersToWorkList(I);         // Add all modified instrs to worklist
 154       if (&I != V) {
 155         I.replaceAllUsesWith(V);
 156         return &I;
 157       } else {
 158         // If we are replacing the instruction with itself, this must be in a
 159         // segment of unreachable code, so just clobber the instruction.
 160         I.replaceAllUsesWith(Constant::getNullValue(I.getType()));
 161         return &I;
 162       }
 163     }
 164
 165     // EraseInstFromFunction - When dealing with an instruction that has side
 166     // effects or produces a void value, we can't rely on DCE to delete the
 167     // instruction.  Instead, visit methods should return the value returned by
 168     // this function.
 169     Instruction *EraseInstFromFunction(Instruction &I) {
 170       assert(I.use_empty() && "Cannot erase instruction that is used!");
 171       AddUsesToWorkList(I);
 172       removeFromWorkList(&I);
 173       I.getParent()->getInstList().erase(&I);
 174       return 0;  // Don't do anything with FI
 175     }
 176
 177
 178   private:
 179     /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
 180     /// InsertBefore instruction.  This is specialized a bit to avoid inserting
 181     /// casts that are known to not do anything...
 182     ///
 183     Value *InsertOperandCastBefore(Value *V, const Type *DestTy,
 184                                    Instruction *InsertBefore);
 185
 186     // SimplifyCommutative - This performs a few simplifications for commutative
 187     // operators...
 188     bool SimplifyCommutative(BinaryOperator &I);
 189
 190     Instruction *OptAndOp(Instruction *Op, ConstantIntegral *OpRHS,
 191                           ConstantIntegral *AndRHS, BinaryOperator &TheAnd);
 192   };
 193
 194   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
 195 }
 196
 197 // getComplexity:  Assign a complexity or rank value to LLVM Values...
 198 //   0 -> Constant, 1 -> Other, 2 -> Argument, 2 -> Unary, 3 -> OtherInst
 199 static unsigned getComplexity(Value *V) {
 200   if (isa<Instruction>(V)) {
 201     if (BinaryOperator::isNeg(V) || BinaryOperator::isNot(V))
 202       return 2;
 203     return 3;
 204   }
 205   if (isa<Argument>(V)) return 2;
 206   return isa<Constant>(V) ? 0 : 1;
 207 }
 208
 209 // isOnlyUse - Return true if this instruction will be deleted if we stop using
 210 // it.
 211 static bool isOnlyUse(Value *V) {
 212   return V->hasOneUse() || isa<Constant>(V);
 213 }
 214
 215 // getSignedIntegralType - Given an unsigned integral type, return the signed
 216 // version of it that has the same size.
 217 static const Type *getSignedIntegralType(const Type *Ty) {
 218   switch (Ty->getPrimitiveID()) {
 219   default: assert(0 && "Invalid unsigned integer type!"); abort();
 220   case Type::UByteTyID:  return Type::SByteTy;
 221   case Type::UShortTyID: return Type::ShortTy;
 222   case Type::UIntTyID:   return Type::IntTy;
 223   case Type::ULongTyID:  return Type::LongTy;
 224   }
 225 }
 226
 227 // getUnsignedIntegralType - Given an signed integral type, return the unsigned
 228 // version of it that has the same size.
 229 static const Type *getUnsignedIntegralType(const Type *Ty) {
 230   switch (Ty->getPrimitiveID()) {
 231   default: assert(0 && "Invalid signed integer type!"); abort();
 232   case Type::SByteTyID: return Type::UByteTy;
 233   case Type::ShortTyID: return Type::UShortTy;
 234   case Type::IntTyID:   return Type::UIntTy;
 235   case Type::LongTyID:  return Type::ULongTy;
 236   }
 237 }
 238
 239 // getPromotedType - Return the specified type promoted as it would be to pass
 240 // though a va_arg area...
 241 static const Type *getPromotedType(const Type *Ty) {
 242   switch (Ty->getPrimitiveID()) {
 243   case Type::SByteTyID:
 244   case Type::ShortTyID:  return Type::IntTy;
 245   case Type::UByteTyID:
 246   case Type::UShortTyID: return Type::UIntTy;
 247   case Type::FloatTyID:  return Type::DoubleTy;
 248   default:               return Ty;
 249   }
 250 }
 251
 252 // SimplifyCommutative - This performs a few simplifications for commutative
 253 // operators:
 254 //
 255 //  1. Order operands such that they are listed from right (least complex) to
 256 //     left (most complex).  This puts constants before unary operators before
 257 //     binary operators.
 258 //
 259 //  2. Transform: (op (op V, C1), C2) ==> (op V, (op C1, C2))
 260 //  3. Transform: (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 261 //
 262 bool InstCombiner::SimplifyCommutative(BinaryOperator &I) {
 263   bool Changed = false;
 264   if (getComplexity(I.getOperand(0)) < getComplexity(I.getOperand(1)))
 265     Changed = !I.swapOperands();
 266
 267   if (!I.isAssociative()) return Changed;
 268   Instruction::BinaryOps Opcode = I.getOpcode();
 269   if (BinaryOperator *Op = dyn_cast<BinaryOperator>(I.getOperand(0)))
 270     if (Op->getOpcode() == Opcode && isa<Constant>(Op->getOperand(1))) {
 271       if (isa<Constant>(I.getOperand(1))) {
 272         Constant *Folded = ConstantExpr::get(I.getOpcode(),
 273                                              cast<Constant>(I.getOperand(1)),
 274                                              cast<Constant>(Op->getOperand(1)));
 275         I.setOperand(0, Op->getOperand(0));
 276         I.setOperand(1, Folded);
 277         return true;
 278       } else if (BinaryOperator *Op1=dyn_cast<BinaryOperator>(I.getOperand(1)))
 279         if (Op1->getOpcode() == Opcode && isa<Constant>(Op1->getOperand(1)) &&
 280             isOnlyUse(Op) && isOnlyUse(Op1)) {
 281           Constant *C1 = cast<Constant>(Op->getOperand(1));
 282           Constant *C2 = cast<Constant>(Op1->getOperand(1));
 283
 284           // Fold (op (op V1, C1), (op V2, C2)) ==> (op (op V1, V2), (op C1,C2))
 285           Constant *Folded = ConstantExpr::get(I.getOpcode(), C1, C2);
 286           Instruction *New = BinaryOperator::create(Opcode, Op->getOperand(0),
 287                                                     Op1->getOperand(0),
 288                                                     Op1->getName(), &I);
 289           WorkList.push_back(New);
 290           I.setOperand(0, New);
 291           I.setOperand(1, Folded);
 292           return true;
 293         }
 294     }
 295   return Changed;
 296 }
 297
 298 // dyn_castNegVal - Given a 'sub' instruction, return the RHS of the instruction
 299 // if the LHS is a constant zero (which is the 'negate' form).
 300 //
 301 static inline Value *dyn_castNegVal(Value *V) {
 302   if (BinaryOperator::isNeg(V))
 303     return BinaryOperator::getNegArgument(cast<BinaryOperator>(V));
 304
 305   // Constants can be considered to be negated values if they can be folded...
 306   if (Constant *C = dyn_cast<Constant>(V))
 307     return ConstantExpr::get(Instruction::Sub,
 308                              Constant::getNullValue(V->getType()), C);
 309   return 0;
 310 }
 311
 312 static Constant *NotConstant(Constant *C) {
 313   return ConstantExpr::get(Instruction::Xor, C,
 314                            ConstantIntegral::getAllOnesValue(C->getType()));
 315 }
 316
 317 static inline Value *dyn_castNotVal(Value *V) {
 318   if (BinaryOperator::isNot(V))
 319     return BinaryOperator::getNotArgument(cast<BinaryOperator>(V));
 320
 321   // Constants can be considered to be not'ed values...
 322   if (ConstantIntegral *C = dyn_cast<ConstantIntegral>(V))
 323     return NotConstant(C);
 324   return 0;
 325 }
 326
 327 // dyn_castFoldableMul - If this value is a multiply that can be folded into
 328 // other computations (because it has a constant operand), return the
 329 // non-constant operand of the multiply.
 330 //
 331 static inline Value *dyn_castFoldableMul(Value *V) {
 332   if (V->hasOneUse() && V->getType()->isInteger())
 333     if (Instruction *I = dyn_cast<Instruction>(V))
 334       if (I->getOpcode() == Instruction::Mul)
 335         if (isa<Constant>(I->getOperand(1)))
 336           return I->getOperand(0);
 337   return 0;
 338 }
 339
 340 // dyn_castMaskingAnd - If this value is an And instruction masking a value with
 341 // a constant, return the constant being anded with.
 342 //
 343 template<class ValueType>
 344 static inline Constant *dyn_castMaskingAnd(ValueType *V) {
 345   if (Instruction *I = dyn_cast<Instruction>(V))
 346     if (I->getOpcode() == Instruction::And)
 347       return dyn_cast<Constant>(I->getOperand(1));
 348
 349   // If this is a constant, it acts just like we were masking with it.
 350   return dyn_cast<Constant>(V);
 351 }
 352
 353 // Log2 - Calculate the log base 2 for the specified value if it is exactly a
 354 // power of 2.
 355 static unsigned Log2(uint64_t Val) {
 356   assert(Val > 1 && "Values 0 and 1 should be handled elsewhere!");
 357   unsigned Count = 0;
 358   while (Val != 1) {
 359     if (Val & 1) return 0;    // Multiple bits set?
 360     Val >>= 1;
 361     ++Count;
 362   }
 363   return Count;
 364 }
 365
 366
 367 /// AssociativeOpt - Perform an optimization on an associative operator.  This
 368 /// function is designed to check a chain of associative operators for a
 369 /// potential to apply a certain optimization.  Since the optimization may be
 370 /// applicable if the expression was reassociated, this checks the chain, then
 371 /// reassociates the expression as necessary to expose the optimization
 372 /// opportunity.  This makes use of a special Functor, which must define
 373 /// 'shouldApply' and 'apply' methods.
 374 ///
 375 template<typename Functor>
 376 Instruction *AssociativeOpt(BinaryOperator &Root, const Functor &F) {
 377   unsigned Opcode = Root.getOpcode();
 378   Value *LHS = Root.getOperand(0);
 379
 380   // Quick check, see if the immediate LHS matches...
 381   if (F.shouldApply(LHS))
 382     return F.apply(Root);
 383
 384   // Otherwise, if the LHS is not of the same opcode as the root, return.
 385   Instruction *LHSI = dyn_cast<Instruction>(LHS);
 386   while (LHSI && LHSI->getOpcode() == Opcode && LHSI->hasOneUse()) {
 387     // Should we apply this transform to the RHS?
 388     bool ShouldApply = F.shouldApply(LHSI->getOperand(1));
 389
 390     // If not to the RHS, check to see if we should apply to the LHS...
 391     if (!ShouldApply && F.shouldApply(LHSI->getOperand(0))) {
 392       cast<BinaryOperator>(LHSI)->swapOperands();   // Make the LHS the RHS
 393       ShouldApply = true;
 394     }
 395
 396     // If the functor wants to apply the optimization to the RHS of LHSI,
 397     // reassociate the expression from ((? op A) op B) to (? op (A op B))
 398     if (ShouldApply) {
 399       BasicBlock *BB = Root.getParent();
 400       // All of the instructions have a single use and have no side-effects,
 401       // because of this, we can pull them all into the current basic block.
 402       if (LHSI->getParent() != BB) {
 403         // Move all of the instructions from root to LHSI into the current
 404         // block.
 405         Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
 406         Instruction *LastUse = &Root;
 407         while (TmpLHSI->getParent() == BB) {
 408           LastUse = TmpLHSI;
 409           TmpLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
 410         }
 411
 412         // Loop over all of the instructions in other blocks, moving them into
 413         // the current one.
 414         Value *TmpLHS = TmpLHSI;
 415         do {
 416           TmpLHSI = cast<Instruction>(TmpLHS);
 417           // Remove from current block...
 418           TmpLHSI->getParent()->getInstList().remove(TmpLHSI);
 419           // Insert before the last instruction...
 420           BB->getInstList().insert(LastUse, TmpLHSI);
 421           TmpLHS = TmpLHSI->getOperand(0);
 422         } while (TmpLHSI != LHSI);
 423       }
 424
 425       // Now all of the instructions are in the current basic block, go ahead
 426       // and perform the reassociation.
 427       Instruction *TmpLHSI = cast<Instruction>(Root.getOperand(0));
 428
 429       // First move the selected RHS to the LHS of the root...
 430       Root.setOperand(0, LHSI->getOperand(1));
 431
 432       // Make what used to be the LHS of the root be the user of the root...
 433       Value *ExtraOperand = TmpLHSI->getOperand(1);
 434       if (&Root != TmpLHSI)
 435         Root.replaceAllUsesWith(TmpLHSI);        // Users now use TmpLHSI
 436       else {
 437         Root.replaceAllUsesWith(Constant::getNullValue(TmpLHSI->getType()));
 438         return 0;
 439       }
 440       TmpLHSI->setOperand(1, &Root);             // TmpLHSI now uses the root
 441       BB->getInstList().remove(&Root);           // Remove root from the BB
 442       BB->getInstList().insert(TmpLHSI, &Root);  // Insert root before TmpLHSI
 443
 444       // Now propagate the ExtraOperand down the chain of instructions until we
 445       // get to LHSI.
 446       while (TmpLHSI != LHSI) {
 447         Instruction *NextLHSI = cast<Instruction>(TmpLHSI->getOperand(0));
 448         Value *NextOp = NextLHSI->getOperand(1);
 449         NextLHSI->setOperand(1, ExtraOperand);
 450         TmpLHSI = NextLHSI;
 451         ExtraOperand = NextOp;
 452       }
 453
 454       // Now that the instructions are reassociated, have the functor perform
 455       // the transformation...
 456       return F.apply(Root);
 457     }
 458
 459     LHSI = dyn_cast<Instruction>(LHSI->getOperand(0));
 460   }
 461   return 0;
 462 }
 463
 464
 465 // AddRHS - Implements: X + X --> X << 1
 466 struct AddRHS {
 467   Value *RHS;
 468   AddRHS(Value *rhs) : RHS(rhs) {}
 469   bool shouldApply(Value *LHS) const { return LHS == RHS; }
 470   Instruction *apply(BinaryOperator &Add) const {
 471     return new ShiftInst(Instruction::Shl, Add.getOperand(0),
 472                          ConstantInt::get(Type::UByteTy, 1));
 473   }
 474 };
 475
 476 // AddMaskingAnd - Implements (A & C1)+(B & C2) --> (A & C1)|(B & C2)
 477 //                 iff C1&C2 == 0
 478 struct AddMaskingAnd {
 479   Constant *C2;
 480   AddMaskingAnd(Constant *c) : C2(c) {}
 481   bool shouldApply(Value *LHS) const {
 482     if (Constant *C1 = dyn_castMaskingAnd(LHS))
 483       return ConstantExpr::get(Instruction::And, C1, C2)->isNullValue();
 484     return false;
 485   }
 486   Instruction *apply(BinaryOperator &Add) const {
 487     return BinaryOperator::create(Instruction::Or, Add.getOperand(0),
 488                                   Add.getOperand(1));
 489   }
 490 };
 491
 492 static Value *FoldOperationIntoSelectOperand(Instruction &BI, Value *SO,
 493                                              InstCombiner *IC) {
 494   // Figure out if the constant is the left or the right argument.
 495   bool ConstIsRHS = isa<Constant>(BI.getOperand(1));
 496   Constant *ConstOperand = cast<Constant>(BI.getOperand(ConstIsRHS));
 497
 498   if (Constant *SOC = dyn_cast<Constant>(SO)) {
 499     if (ConstIsRHS)
 500       return ConstantExpr::get(BI.getOpcode(), SOC, ConstOperand);
 501     return ConstantExpr::get(BI.getOpcode(), ConstOperand, SOC);
 502   }
 503
 504   Value *Op0 = SO, *Op1 = ConstOperand;
 505   if (!ConstIsRHS)
 506     std::swap(Op0, Op1);
 507   Instruction *New;
 508   if (BinaryOperator *BO = dyn_cast<BinaryOperator>(&BI))
 509     New = BinaryOperator::create(BO->getOpcode(), Op0, Op1);
 510   else if (ShiftInst *SI = dyn_cast<ShiftInst>(&BI))
 511     New = new ShiftInst(SI->getOpcode(), Op0, Op1);
 512   else {
 513     assert(0 && "Unknown binary instruction type!");
 514     abort();
 515   }
 516   return IC->InsertNewInstBefore(New, BI);
 517 }
 518
 519 // FoldBinOpIntoSelect - Given an instruction with a select as one operand and a
 520 // constant as the other operand, try to fold the binary operator into the
 521 // select arguments.
 522 static Instruction *FoldBinOpIntoSelect(Instruction &BI, SelectInst *SI,
 523                                         InstCombiner *IC) {
 524   // Don't modify shared select instructions
 525   if (!SI->hasOneUse()) return 0;
 526   Value *TV = SI->getOperand(1);
 527   Value *FV = SI->getOperand(2);
 528
 529   if (isa<Constant>(TV) || isa<Constant>(FV)) {
 530     Value *SelectTrueVal = FoldOperationIntoSelectOperand(BI, TV, IC);
 531     Value *SelectFalseVal = FoldOperationIntoSelectOperand(BI, FV, IC);
 532
 533     return new SelectInst(SI->getCondition(), SelectTrueVal,
 534                           SelectFalseVal);
 535   }
 536   return 0;
 537 }
 538
 539 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 540   bool Changed = SimplifyCommutative(I);
 541   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 542
 543   if (Constant *RHSC = dyn_cast<Constant>(RHS)) {
 544     // X + 0 --> X
 545     if (!I.getType()->isFloatingPoint() && // -0 + +0 = +0, so it's not a noop
 546         RHSC->isNullValue())
 547       return ReplaceInstUsesWith(I, LHS);
 548
 549     // X + (signbit) --> X ^ signbit
 550     if (ConstantInt *CI = dyn_cast<ConstantInt>(RHSC)) {
 551       unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
 552       uint64_t Val = CI->getRawValue() & (1ULL << NumBits)-1;
 553       if (Val == (1ULL << NumBits-1))
 554         return BinaryOperator::create(Instruction::Xor, LHS, RHS);
 555     }
 556   }
 557
 558   // X + X --> X << 1
 559   if (I.getType()->isInteger())
 560     if (Instruction *Result = AssociativeOpt(I, AddRHS(RHS))) return Result;
 561
 562   // -A + B  -->  B - A
 563   if (Value *V = dyn_castNegVal(LHS))
 564     return BinaryOperator::create(Instruction::Sub, RHS, V);
 565
 566   // A + -B  -->  A - B
 567   if (!isa<Constant>(RHS))
 568     if (Value *V = dyn_castNegVal(RHS))
 569       return BinaryOperator::create(Instruction::Sub, LHS, V);
 570
 571   // X*C + X --> X * (C+1)
 572   if (dyn_castFoldableMul(LHS) == RHS) {
 573     Constant *CP1 =
 574       ConstantExpr::get(Instruction::Add,
 575                         cast<Constant>(cast<Instruction>(LHS)->getOperand(1)),
 576                         ConstantInt::get(I.getType(), 1));
 577     return BinaryOperator::create(Instruction::Mul, RHS, CP1);
 578   }
 579
 580   // X + X*C --> X * (C+1)
 581   if (dyn_castFoldableMul(RHS) == LHS) {
 582     Constant *CP1 =
 583       ConstantExpr::get(Instruction::Add,
 584                         cast<Constant>(cast<Instruction>(RHS)->getOperand(1)),
 585                         ConstantInt::get(I.getType(), 1));
 586     return BinaryOperator::create(Instruction::Mul, LHS, CP1);
 587   }
 588
 589   // (A & C1)+(B & C2) --> (A & C1)|(B & C2) iff C1&C2 == 0
 590   if (Constant *C2 = dyn_castMaskingAnd(RHS))
 591     if (Instruction *R = AssociativeOpt(I, AddMaskingAnd(C2))) return R;
 592
 593   if (ConstantInt *CRHS = dyn_cast<ConstantInt>(RHS)) {
 594     if (Instruction *ILHS = dyn_cast<Instruction>(LHS)) {
 595       switch (ILHS->getOpcode()) {
 596       case Instruction::Xor:
 597         // ~X + C --> (C-1) - X
 598         if (ConstantInt *XorRHS = dyn_cast<ConstantInt>(ILHS->getOperand(1)))
 599           if (XorRHS->isAllOnesValue())
 600             return BinaryOperator::create(Instruction::Sub,
 601                                           ConstantExpr::get(Instruction::Sub,
 602                                     CRHS, ConstantInt::get(I.getType(), 1)),
 603                                           ILHS->getOperand(0));
 604         break;
 605       case Instruction::Select:
 606         // Try to fold constant add into select arguments.
 607         if (Instruction *R = FoldBinOpIntoSelect(I,cast<SelectInst>(ILHS),this))
 608           return R;
 609
 610       default: break;
 611       }
 612     }
 613   }
 614
 615   return Changed ? &I : 0;
 616 }
 617
 618 // isSignBit - Return true if the value represented by the constant only has the
 619 // highest order bit set.
 620 static bool isSignBit(ConstantInt *CI) {
 621   unsigned NumBits = CI->getType()->getPrimitiveSize()*8;
 622   return (CI->getRawValue() & ~(-1LL << NumBits)) == (1ULL << (NumBits-1));
 623 }
 624
 625 static unsigned getTypeSizeInBits(const Type *Ty) {
 626   return Ty == Type::BoolTy ? 1 : Ty->getPrimitiveSize()*8;
 627 }
 628
 629 /// RemoveNoopCast - Strip off nonconverting casts from the value.
 630 ///
 631 static Value *RemoveNoopCast(Value *V) {
 632   if (CastInst *CI = dyn_cast<CastInst>(V)) {
 633     const Type *CTy = CI->getType();
 634     const Type *OpTy = CI->getOperand(0)->getType();
 635     if (CTy->isInteger() && OpTy->isInteger()) {
 636       if (CTy->getPrimitiveSize() == OpTy->getPrimitiveSize())
 637         return RemoveNoopCast(CI->getOperand(0));
 638     } else if (isa<PointerType>(CTy) && isa<PointerType>(OpTy))
 639       return RemoveNoopCast(CI->getOperand(0));
 640   }
 641   return V;
 642 }
 643
 644 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 645   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 646
 647   if (Op0 == Op1)         // sub X, X  -> 0
 648     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 649
 650   // If this is a 'B = x-(-A)', change to B = x+A...
 651   if (Value *V = dyn_castNegVal(Op1))
 652     return BinaryOperator::create(Instruction::Add, Op0, V);
 653
 654   if (ConstantInt *C = dyn_cast<ConstantInt>(Op0)) {
 655     // Replace (-1 - A) with (~A)...
 656     if (C->isAllOnesValue())
 657       return BinaryOperator::createNot(Op1);
 658
 659     // C - ~X == X + (1+C)
 660     if (BinaryOperator::isNot(Op1))
 661       return BinaryOperator::create(Instruction::Add,
 662                BinaryOperator::getNotArgument(cast<BinaryOperator>(Op1)),
 663                     ConstantExpr::get(Instruction::Add, C,
 664                                       ConstantInt::get(I.getType(), 1)));
 665     // -((uint)X >> 31) -> ((int)X >> 31)
 666     // -((int)X >> 31) -> ((uint)X >> 31)
 667     if (C->isNullValue()) {
 668       Value *NoopCastedRHS = RemoveNoopCast(Op1);
 669       if (ShiftInst *SI = dyn_cast<ShiftInst>(NoopCastedRHS))
 670         if (SI->getOpcode() == Instruction::Shr)
 671           if (ConstantUInt *CU = dyn_cast<ConstantUInt>(SI->getOperand(1))) {
 672             const Type *NewTy;
 673             if (SI->getType()->isSigned())
 674               NewTy = getUnsignedIntegralType(SI->getType());
 675             else
 676               NewTy = getSignedIntegralType(SI->getType());
 677             // Check to see if we are shifting out everything but the sign bit.
 678             if (CU->getValue() == SI->getType()->getPrimitiveSize()*8-1) {
 679               // Ok, the transformation is safe.  Insert a cast of the incoming
 680               // value, then the new shift, then the new cast.
 681               Instruction *FirstCast = new CastInst(SI->getOperand(0), NewTy,
 682                                                  SI->getOperand(0)->getName());
 683               Value *InV = InsertNewInstBefore(FirstCast, I);
 684               Instruction *NewShift = new ShiftInst(Instruction::Shr, FirstCast,
 685                                                     CU, SI->getName());
 686               if (NewShift->getType() == I.getType())
 687                 return NewShift;
 688               else {
 689                 InV = InsertNewInstBefore(NewShift, I);
 690                 return new CastInst(NewShift, I.getType());
 691               }
 692             }
 693           }
 694     }
 695
 696     // Try to fold constant sub into select arguments.
 697     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
 698       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
 699         return R;
 700   }
 701
 702   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
 703     if (Op1I->hasOneUse()) {
 704       // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression
 705       // is not used by anyone else...
 706       //
 707       if (Op1I->getOpcode() == Instruction::Sub &&
 708           !Op1I->getType()->isFloatingPoint()) {
 709         // Swap the two operands of the subexpr...
 710         Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 711         Op1I->setOperand(0, IIOp1);
 712         Op1I->setOperand(1, IIOp0);
 713
 714         // Create the new top level add instruction...
 715         return BinaryOperator::create(Instruction::Add, Op0, Op1);
 716       }
 717
 718       // Replace (A - (A & B)) with (A & ~B) if this is the only use of (A&B)...
 719       //
 720       if (Op1I->getOpcode() == Instruction::And &&
 721           (Op1I->getOperand(0) == Op0 || Op1I->getOperand(1) == Op0)) {
 722         Value *OtherOp = Op1I->getOperand(Op1I->getOperand(0) == Op0);
 723
 724         Instruction *NewNot = BinaryOperator::createNot(OtherOp, "B.not", &I);
 725         return BinaryOperator::create(Instruction::And, Op0, NewNot);
 726       }
 727
 728       // X - X*C --> X * (1-C)
 729       if (dyn_castFoldableMul(Op1I) == Op0) {
 730         Constant *CP1 =
 731           ConstantExpr::get(Instruction::Sub,
 732                             ConstantInt::get(I.getType(), 1),
 733                          cast<Constant>(cast<Instruction>(Op1)->getOperand(1)));
 734         assert(CP1 && "Couldn't constant fold 1-C?");
 735         return BinaryOperator::create(Instruction::Mul, Op0, CP1);
 736       }
 737     }
 738
 739   // X*C - X --> X * (C-1)
 740   if (dyn_castFoldableMul(Op0) == Op1) {
 741     Constant *CP1 =
 742       ConstantExpr::get(Instruction::Sub,
 743                         cast<Constant>(cast<Instruction>(Op0)->getOperand(1)),
 744                         ConstantInt::get(I.getType(), 1));
 745     assert(CP1 && "Couldn't constant fold C - 1?");
 746     return BinaryOperator::create(Instruction::Mul, Op1, CP1);
 747   }
 748
 749   return 0;
 750 }
 751
 752 /// isSignBitCheck - Given an exploded setcc instruction, return true if it is
 753 /// really just returns true if the most significant (sign) bit is set.
 754 static bool isSignBitCheck(unsigned Opcode, Value *LHS, ConstantInt *RHS) {
 755   if (RHS->getType()->isSigned()) {
 756     // True if source is LHS < 0 or LHS <= -1
 757     return Opcode == Instruction::SetLT && RHS->isNullValue() ||
 758            Opcode == Instruction::SetLE && RHS->isAllOnesValue();
 759   } else {
 760     ConstantUInt *RHSC = cast<ConstantUInt>(RHS);
 761     // True if source is LHS > 127 or LHS >= 128, where the constants depend on
 762     // the size of the integer type.
 763     if (Opcode == Instruction::SetGE)
 764       return RHSC->getValue() == 1ULL<<(RHS->getType()->getPrimitiveSize()*8-1);
 765     if (Opcode == Instruction::SetGT)
 766       return RHSC->getValue() ==
 767         (1ULL << (RHS->getType()->getPrimitiveSize()*8-1))-1;
 768   }
 769   return false;
 770 }
 771
 772 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 773   bool Changed = SimplifyCommutative(I);
 774   Value *Op0 = I.getOperand(0);
 775
 776   // Simplify mul instructions with a constant RHS...
 777   if (Constant *Op1 = dyn_cast<Constant>(I.getOperand(1))) {
 778     if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 779
 780       // ((X << C1)*C2) == (X * (C2 << C1))
 781       if (ShiftInst *SI = dyn_cast<ShiftInst>(Op0))
 782         if (SI->getOpcode() == Instruction::Shl)
 783           if (Constant *ShOp = dyn_cast<Constant>(SI->getOperand(1)))
 784             return BinaryOperator::create(Instruction::Mul, SI->getOperand(0),
 785                                  ConstantExpr::get(Instruction::Shl, CI, ShOp));
 786
 787       if (CI->isNullValue())
 788         return ReplaceInstUsesWith(I, Op1);  // X * 0  == 0
 789       if (CI->equalsInt(1))                  // X * 1  == X
 790         return ReplaceInstUsesWith(I, Op0);
 791       if (CI->isAllOnesValue())              // X * -1 == 0 - X
 792         return BinaryOperator::createNeg(Op0, I.getName());
 793
 794       int64_t Val = (int64_t)cast<ConstantInt>(CI)->getRawValue();
 795       if (uint64_t C = Log2(Val))            // Replace X*(2^C) with X << C
 796         return new ShiftInst(Instruction::Shl, Op0,
 797                              ConstantUInt::get(Type::UByteTy, C));
 798     } else {
 799       ConstantFP *Op1F = cast<ConstantFP>(Op1);
 800       if (Op1F->isNullValue())
 801         return ReplaceInstUsesWith(I, Op1);
 802
 803       // "In IEEE floating point, x*1 is not equivalent to x for nans.  However,
 804       // ANSI says we can drop signals, so we can do this anyway." (from GCC)
 805       if (Op1F->getValue() == 1.0)
 806         return ReplaceInstUsesWith(I, Op0);  // Eliminate 'mul double %X, 1.0'
 807     }
 808
 809     // Try to fold constant mul into select arguments.
 810     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
 811       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
 812         return R;
 813   }
 814
 815   if (Value *Op0v = dyn_castNegVal(Op0))     // -X * -Y = X*Y
 816     if (Value *Op1v = dyn_castNegVal(I.getOperand(1)))
 817       return BinaryOperator::create(Instruction::Mul, Op0v, Op1v);
 818
 819   // If one of the operands of the multiply is a cast from a boolean value, then
 820   // we know the bool is either zero or one, so this is a 'masking' multiply.
 821   // See if we can simplify things based on how the boolean was originally
 822   // formed.
 823   CastInst *BoolCast = 0;
 824   if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(0)))
 825     if (CI->getOperand(0)->getType() == Type::BoolTy)
 826       BoolCast = CI;
 827   if (!BoolCast)
 828     if (CastInst *CI = dyn_cast<CastInst>(I.getOperand(1)))
 829       if (CI->getOperand(0)->getType() == Type::BoolTy)
 830         BoolCast = CI;
 831   if (BoolCast) {
 832     if (SetCondInst *SCI = dyn_cast<SetCondInst>(BoolCast->getOperand(0))) {
 833       Value *SCIOp0 = SCI->getOperand(0), *SCIOp1 = SCI->getOperand(1);
 834       const Type *SCOpTy = SCIOp0->getType();
 835
 836       // If the setcc is true iff the sign bit of X is set, then convert this
 837       // multiply into a shift/and combination.
 838       if (isa<ConstantInt>(SCIOp1) &&
 839           isSignBitCheck(SCI->getOpcode(), SCIOp0, cast<ConstantInt>(SCIOp1))) {
 840         // Shift the X value right to turn it into "all signbits".
 841         Constant *Amt = ConstantUInt::get(Type::UByteTy,
 842                                           SCOpTy->getPrimitiveSize()*8-1);
 843         if (SCIOp0->getType()->isUnsigned()) {
 844           const Type *NewTy = getSignedIntegralType(SCIOp0->getType());
 845           SCIOp0 = InsertNewInstBefore(new CastInst(SCIOp0, NewTy,
 846                                                     SCIOp0->getName()), I);
 847         }
 848
 849         Value *V =
 850           InsertNewInstBefore(new ShiftInst(Instruction::Shr, SCIOp0, Amt,
 851                                             BoolCast->getOperand(0)->getName()+
 852                                             ".mask"), I);
 853
 854         // If the multiply type is not the same as the source type, sign extend
 855         // or truncate to the multiply type.
 856         if (I.getType() != V->getType())
 857           V = InsertNewInstBefore(new CastInst(V, I.getType(), V->getName()),I);
 858
 859         Value *OtherOp = Op0 == BoolCast ? I.getOperand(1) : Op0;
 860         return BinaryOperator::create(Instruction::And, V, OtherOp);
 861       }
 862     }
 863   }
 864
 865   return Changed ? &I : 0;
 866 }
 867
 868 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
 869   // div X, 1 == X
 870   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
 871     if (RHS->equalsInt(1))
 872       return ReplaceInstUsesWith(I, I.getOperand(0));
 873
 874     // Check to see if this is an unsigned division with an exact power of 2,
 875     // if so, convert to a right shift.
 876     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
 877       if (uint64_t Val = C->getValue())    // Don't break X / 0
 878         if (uint64_t C = Log2(Val))
 879           return new ShiftInst(Instruction::Shr, I.getOperand(0),
 880                                ConstantUInt::get(Type::UByteTy, C));
 881   }
 882
 883   // 0 / X == 0, we don't need to preserve faults!
 884   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
 885     if (LHS->equalsInt(0))
 886       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 887
 888   return 0;
 889 }
 890
 891
 892 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
 893   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1))) {
 894     if (RHS->equalsInt(1))  // X % 1 == 0
 895       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 896     if (RHS->isAllOnesValue())  // X % -1 == 0
 897       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 898
 899     // Check to see if this is an unsigned remainder with an exact power of 2,
 900     // if so, convert to a bitwise and.
 901     if (ConstantUInt *C = dyn_cast<ConstantUInt>(RHS))
 902       if (uint64_t Val = C->getValue())    // Don't break X % 0 (divide by zero)
 903         if (Log2(Val))
 904           return BinaryOperator::create(Instruction::And, I.getOperand(0),
 905                                         ConstantUInt::get(I.getType(), Val-1));
 906   }
 907
 908   // 0 % X == 0, we don't need to preserve faults!
 909   if (ConstantInt *LHS = dyn_cast<ConstantInt>(I.getOperand(0)))
 910     if (LHS->equalsInt(0))
 911       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 912
 913   return 0;
 914 }
 915
 916 // isMaxValueMinusOne - return true if this is Max-1
 917 static bool isMaxValueMinusOne(const ConstantInt *C) {
 918   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
 919     // Calculate -1 casted to the right type...
 920     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 921     uint64_t Val = ~0ULL;                // All ones
 922     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 923     return CU->getValue() == Val-1;
 924   }
 925
 926   const ConstantSInt *CS = cast<ConstantSInt>(C);
 927
 928   // Calculate 0111111111..11111
 929   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 930   int64_t Val = INT64_MAX;             // All ones
 931   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 932   return CS->getValue() == Val-1;
 933 }
 934
 935 // isMinValuePlusOne - return true if this is Min+1
 936 static bool isMinValuePlusOne(const ConstantInt *C) {
 937   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
 938     return CU->getValue() == 1;
 939
 940   const ConstantSInt *CS = cast<ConstantSInt>(C);
 941
 942   // Calculate 1111111111000000000000
 943   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 944   int64_t Val = -1;                    // All ones
 945   Val <<= TypeBits-1;                  // Shift over to the right spot
 946   return CS->getValue() == Val+1;
 947 }
 948
 949 /// getSetCondCode - Encode a setcc opcode into a three bit mask.  These bits
 950 /// are carefully arranged to allow folding of expressions such as:
 951 ///
 952 ///      (A < B) | (A > B) --> (A != B)
 953 ///
 954 /// Bit value '4' represents that the comparison is true if A > B, bit value '2'
 955 /// represents that the comparison is true if A == B, and bit value '1' is true
 956 /// if A < B.
 957 ///
 958 static unsigned getSetCondCode(const SetCondInst *SCI) {
 959   switch (SCI->getOpcode()) {
 960     // False -> 0
 961   case Instruction::SetGT: return 1;
 962   case Instruction::SetEQ: return 2;
 963   case Instruction::SetGE: return 3;
 964   case Instruction::SetLT: return 4;
 965   case Instruction::SetNE: return 5;
 966   case Instruction::SetLE: return 6;
 967     // True -> 7
 968   default:
 969     assert(0 && "Invalid SetCC opcode!");
 970     return 0;
 971   }
 972 }
 973
 974 /// getSetCCValue - This is the complement of getSetCondCode, which turns an
 975 /// opcode and two operands into either a constant true or false, or a brand new
 976 /// SetCC instruction.
 977 static Value *getSetCCValue(unsigned Opcode, Value *LHS, Value *RHS) {
 978   switch (Opcode) {
 979   case 0: return ConstantBool::False;
 980   case 1: return new SetCondInst(Instruction::SetGT, LHS, RHS);
 981   case 2: return new SetCondInst(Instruction::SetEQ, LHS, RHS);
 982   case 3: return new SetCondInst(Instruction::SetGE, LHS, RHS);
 983   case 4: return new SetCondInst(Instruction::SetLT, LHS, RHS);
 984   case 5: return new SetCondInst(Instruction::SetNE, LHS, RHS);
 985   case 6: return new SetCondInst(Instruction::SetLE, LHS, RHS);
 986   case 7: return ConstantBool::True;
 987   default: assert(0 && "Illegal SetCCCode!"); return 0;
 988   }
 989 }
 990
 991 // FoldSetCCLogical - Implements (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
 992 struct FoldSetCCLogical {
 993   InstCombiner &IC;
 994   Value *LHS, *RHS;
 995   FoldSetCCLogical(InstCombiner &ic, SetCondInst *SCI)
 996     : IC(ic), LHS(SCI->getOperand(0)), RHS(SCI->getOperand(1)) {}
 997   bool shouldApply(Value *V) const {
 998     if (SetCondInst *SCI = dyn_cast<SetCondInst>(V))
 999       return (SCI->getOperand(0) == LHS && SCI->getOperand(1) == RHS ||
1000               SCI->getOperand(0) == RHS && SCI->getOperand(1) == LHS);
1001     return false;
1002   }
1003   Instruction *apply(BinaryOperator &Log) const {
1004     SetCondInst *SCI = cast<SetCondInst>(Log.getOperand(0));
1005     if (SCI->getOperand(0) != LHS) {
1006       assert(SCI->getOperand(1) == LHS);
1007       SCI->swapOperands();  // Swap the LHS and RHS of the SetCC
1008     }
1009
1010     unsigned LHSCode = getSetCondCode(SCI);
1011     unsigned RHSCode = getSetCondCode(cast<SetCondInst>(Log.getOperand(1)));
1012     unsigned Code;
1013     switch (Log.getOpcode()) {
1014     case Instruction::And: Code = LHSCode & RHSCode; break;
1015     case Instruction::Or:  Code = LHSCode | RHSCode; break;
1016     case Instruction::Xor: Code = LHSCode ^ RHSCode; break;
1017     default: assert(0 && "Illegal logical opcode!"); return 0;
1018     }
1019
1020     Value *RV = getSetCCValue(Code, LHS, RHS);
1021     if (Instruction *I = dyn_cast<Instruction>(RV))
1022       return I;
1023     // Otherwise, it's a constant boolean value...
1024     return IC.ReplaceInstUsesWith(Log, RV);
1025   }
1026 };
1027
1028
1029 // OptAndOp - This handles expressions of the form ((val OP C1) & C2).  Where
1030 // the Op parameter is 'OP', OpRHS is 'C1', and AndRHS is 'C2'.  Op is
1031 // guaranteed to be either a shift instruction or a binary operator.
1032 Instruction *InstCombiner::OptAndOp(Instruction *Op,
1033                                     ConstantIntegral *OpRHS,
1034                                     ConstantIntegral *AndRHS,
1035                                     BinaryOperator &TheAnd) {
1036   Value *X = Op->getOperand(0);
1037   Constant *Together = 0;
1038   if (!isa<ShiftInst>(Op))
1039     Together = ConstantExpr::get(Instruction::And, AndRHS, OpRHS);
1040
1041   switch (Op->getOpcode()) {
1042   case Instruction::Xor:
1043     if (Together->isNullValue()) {
1044       // (X ^ C1) & C2 --> (X & C2) iff (C1&C2) == 0
1045       return BinaryOperator::create(Instruction::And, X, AndRHS);
1046     } else if (Op->hasOneUse()) {
1047       // (X ^ C1) & C2 --> (X & C2) ^ (C1&C2)
1048       std::string OpName = Op->getName(); Op->setName("");
1049       Instruction *And = BinaryOperator::create(Instruction::And,
1050                                                 X, AndRHS, OpName);
1051       InsertNewInstBefore(And, TheAnd);
1052       return BinaryOperator::create(Instruction::Xor, And, Together);
1053     }
1054     break;
1055   case Instruction::Or:
1056     // (X | C1) & C2 --> X & C2 iff C1 & C1 == 0
1057     if (Together->isNullValue())
1058       return BinaryOperator::create(Instruction::And, X, AndRHS);
1059     else {
1060       if (Together == AndRHS) // (X | C) & C --> C
1061         return ReplaceInstUsesWith(TheAnd, AndRHS);
1062
1063       if (Op->hasOneUse() && Together != OpRHS) {
1064         // (X | C1) & C2 --> (X | (C1&C2)) & C2
1065         std::string Op0Name = Op->getName(); Op->setName("");
1066         Instruction *Or = BinaryOperator::create(Instruction::Or, X,
1067                                                  Together, Op0Name);
1068         InsertNewInstBefore(Or, TheAnd);
1069         return BinaryOperator::create(Instruction::And, Or, AndRHS);
1070       }
1071     }
1072     break;
1073   case Instruction::Add:
1074     if (Op->hasOneUse()) {
1075       // Adding a one to a single bit bit-field should be turned into an XOR
1076       // of the bit.  First thing to check is to see if this AND is with a
1077       // single bit constant.
1078       unsigned long long AndRHSV = cast<ConstantInt>(AndRHS)->getRawValue();
1079
1080       // Clear bits that are not part of the constant.
1081       AndRHSV &= (1ULL << AndRHS->getType()->getPrimitiveSize()*8)-1;
1082
1083       // If there is only one bit set...
1084       if ((AndRHSV & (AndRHSV-1)) == 0) {
1085         // Ok, at this point, we know that we are masking the result of the
1086         // ADD down to exactly one bit.  If the constant we are adding has
1087         // no bits set below this bit, then we can eliminate the ADD.
1088         unsigned long long AddRHS = cast<ConstantInt>(OpRHS)->getRawValue();
1089
1090         // Check to see if any bits below the one bit set in AndRHSV are set.
1091         if ((AddRHS & (AndRHSV-1)) == 0) {
1092           // If not, the only thing that can effect the output of the AND is
1093           // the bit specified by AndRHSV.  If that bit is set, the effect of
1094           // the XOR is to toggle the bit.  If it is clear, then the ADD has
1095           // no effect.
1096           if ((AddRHS & AndRHSV) == 0) { // Bit is not set, noop
1097             TheAnd.setOperand(0, X);
1098             return &TheAnd;
1099           } else {
1100             std::string Name = Op->getName(); Op->setName("");
1101             // Pull the XOR out of the AND.
1102             Instruction *NewAnd =
1103               BinaryOperator::create(Instruction::And, X, AndRHS, Name);
1104             InsertNewInstBefore(NewAnd, TheAnd);
1105             return BinaryOperator::create(Instruction::Xor, NewAnd, AndRHS);
1106           }
1107         }
1108       }
1109     }
1110     break;
1111
1112   case Instruction::Shl: {
1113     // We know that the AND will not produce any of the bits shifted in, so if
1114     // the anded constant includes them, clear them now!
1115     //
1116     Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1117     Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
1118                             ConstantExpr::get(Instruction::Shl, AllOne, OpRHS));
1119     if (CI != AndRHS) {
1120       TheAnd.setOperand(1, CI);
1121       return &TheAnd;
1122     }
1123     break;
1124   }
1125   case Instruction::Shr:
1126     // We know that the AND will not produce any of the bits shifted in, so if
1127     // the anded constant includes them, clear them now!  This only applies to
1128     // unsigned shifts, because a signed shr may bring in set bits!
1129     //
1130     if (AndRHS->getType()->isUnsigned()) {
1131       Constant *AllOne = ConstantIntegral::getAllOnesValue(AndRHS->getType());
1132       Constant *CI = ConstantExpr::get(Instruction::And, AndRHS,
1133                             ConstantExpr::get(Instruction::Shr, AllOne, OpRHS));
1134       if (CI != AndRHS) {
1135         TheAnd.setOperand(1, CI);
1136         return &TheAnd;
1137       }
1138     }
1139     break;
1140   }
1141   return 0;
1142 }
1143
1144
1145 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
1146   bool Changed = SimplifyCommutative(I);
1147   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1148
1149   // and X, X = X   and X, 0 == 0
1150   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1151     return ReplaceInstUsesWith(I, Op1);
1152
1153   // and X, -1 == X
1154   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1155     if (RHS->isAllOnesValue())
1156       return ReplaceInstUsesWith(I, Op0);
1157
1158     // Optimize a variety of ((val OP C1) & C2) combinations...
1159     if (isa<BinaryOperator>(Op0) || isa<ShiftInst>(Op0)) {
1160       Instruction *Op0I = cast<Instruction>(Op0);
1161       Value *X = Op0I->getOperand(0);
1162       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1163         if (Instruction *Res = OptAndOp(Op0I, Op0CI, RHS, I))
1164           return Res;
1165     }
1166
1167     // Try to fold constant and into select arguments.
1168     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1169       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
1170         return R;
1171   }
1172
1173   Value *Op0NotVal = dyn_castNotVal(Op0);
1174   Value *Op1NotVal = dyn_castNotVal(Op1);
1175
1176   // (~A & ~B) == (~(A | B)) - Demorgan's Law
1177   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1178     Instruction *Or = BinaryOperator::create(Instruction::Or, Op0NotVal,
1179                                              Op1NotVal,I.getName()+".demorgan");
1180     InsertNewInstBefore(Or, I);
1181     return BinaryOperator::createNot(Or);
1182   }
1183
1184   if (Op0NotVal == Op1 || Op1NotVal == Op0)  // A & ~A  == ~A & A == 0
1185     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1186
1187   // (setcc1 A, B) & (setcc2 A, B) --> (setcc3 A, B)
1188   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1189     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1190       return R;
1191
1192   return Changed ? &I : 0;
1193 }
1194
1195
1196
1197 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
1198   bool Changed = SimplifyCommutative(I);
1199   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1200
1201   // or X, X = X   or X, 0 == X
1202   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
1203     return ReplaceInstUsesWith(I, Op0);
1204
1205   // or X, -1 == -1
1206   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1207     if (RHS->isAllOnesValue())
1208       return ReplaceInstUsesWith(I, Op1);
1209
1210     if (Instruction *Op0I = dyn_cast<Instruction>(Op0)) {
1211       // (X & C1) | C2 --> (X | C2) & (C1|C2)
1212       if (Op0I->getOpcode() == Instruction::And && isOnlyUse(Op0))
1213         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
1214           std::string Op0Name = Op0I->getName(); Op0I->setName("");
1215           Instruction *Or = BinaryOperator::create(Instruction::Or,
1216                                                    Op0I->getOperand(0), RHS,
1217                                                    Op0Name);
1218           InsertNewInstBefore(Or, I);
1219           return BinaryOperator::create(Instruction::And, Or,
1220                              ConstantExpr::get(Instruction::Or, RHS, Op0CI));
1221         }
1222
1223       // (X ^ C1) | C2 --> (X | C2) ^ (C1&~C2)
1224       if (Op0I->getOpcode() == Instruction::Xor && isOnlyUse(Op0))
1225         if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1))) {
1226           std::string Op0Name = Op0I->getName(); Op0I->setName("");
1227           Instruction *Or = BinaryOperator::create(Instruction::Or,
1228                                                    Op0I->getOperand(0), RHS,
1229                                                    Op0Name);
1230           InsertNewInstBefore(Or, I);
1231           return BinaryOperator::create(Instruction::Xor, Or,
1232                             ConstantExpr::get(Instruction::And, Op0CI,
1233                                               NotConstant(RHS)));
1234         }
1235     }
1236
1237     // Try to fold constant and into select arguments.
1238     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1239       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
1240         return R;
1241   }
1242
1243   // (A & C1)|(A & C2) == A & (C1|C2)
1244   if (Instruction *LHS = dyn_cast<BinaryOperator>(Op0))
1245     if (Instruction *RHS = dyn_cast<BinaryOperator>(Op1))
1246       if (LHS->getOperand(0) == RHS->getOperand(0))
1247         if (Constant *C0 = dyn_castMaskingAnd(LHS))
1248           if (Constant *C1 = dyn_castMaskingAnd(RHS))
1249             return BinaryOperator::create(Instruction::And, LHS->getOperand(0),
1250                                     ConstantExpr::get(Instruction::Or, C0, C1));
1251
1252   Value *Op0NotVal = dyn_castNotVal(Op0);
1253   Value *Op1NotVal = dyn_castNotVal(Op1);
1254
1255   if (Op1 == Op0NotVal)   // ~A | A == -1
1256     return ReplaceInstUsesWith(I,
1257                                ConstantIntegral::getAllOnesValue(I.getType()));
1258
1259   if (Op0 == Op1NotVal)   // A | ~A == -1
1260     return ReplaceInstUsesWith(I,
1261                                ConstantIntegral::getAllOnesValue(I.getType()));
1262
1263   // (~A | ~B) == (~(A & B)) - Demorgan's Law
1264   if (Op0NotVal && Op1NotVal && isOnlyUse(Op0) && isOnlyUse(Op1)) {
1265     Instruction *And = BinaryOperator::create(Instruction::And, Op0NotVal,
1266                                               Op1NotVal,I.getName()+".demorgan",
1267                                               &I);
1268     WorkList.push_back(And);
1269     return BinaryOperator::createNot(And);
1270   }
1271
1272   // (setcc1 A, B) | (setcc2 A, B) --> (setcc3 A, B)
1273   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1274     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1275       return R;
1276
1277   return Changed ? &I : 0;
1278 }
1279
1280 // XorSelf - Implements: X ^ X --> 0
1281 struct XorSelf {
1282   Value *RHS;
1283   XorSelf(Value *rhs) : RHS(rhs) {}
1284   bool shouldApply(Value *LHS) const { return LHS == RHS; }
1285   Instruction *apply(BinaryOperator &Xor) const {
1286     return &Xor;
1287   }
1288 };
1289
1290
1291 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
1292   bool Changed = SimplifyCommutative(I);
1293   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1294
1295   // xor X, X = 0, even if X is nested in a sequence of Xor's.
1296   if (Instruction *Result = AssociativeOpt(I, XorSelf(Op1))) {
1297     assert(Result == &I && "AssociativeOpt didn't work?");
1298     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
1299   }
1300
1301   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1)) {
1302     // xor X, 0 == X
1303     if (RHS->isNullValue())
1304       return ReplaceInstUsesWith(I, Op0);
1305
1306     if (BinaryOperator *Op0I = dyn_cast<BinaryOperator>(Op0)) {
1307       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
1308       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0I))
1309         if (RHS == ConstantBool::True && SCI->hasOneUse())
1310           return new SetCondInst(SCI->getInverseCondition(),
1311                                  SCI->getOperand(0), SCI->getOperand(1));
1312
1313       // ~(c-X) == X-c-1 == X+(-c-1)
1314       if (Op0I->getOpcode() == Instruction::Sub && RHS->isAllOnesValue())
1315         if (Constant *Op0I0C = dyn_cast<Constant>(Op0I->getOperand(0))) {
1316           Constant *NegOp0I0C = ConstantExpr::get(Instruction::Sub,
1317                              Constant::getNullValue(Op0I0C->getType()), Op0I0C);
1318           Constant *ConstantRHS = ConstantExpr::get(Instruction::Sub, NegOp0I0C,
1319                                               ConstantInt::get(I.getType(), 1));
1320           return BinaryOperator::create(Instruction::Add, Op0I->getOperand(1),
1321                                         ConstantRHS);
1322         }
1323
1324       if (ConstantInt *Op0CI = dyn_cast<ConstantInt>(Op0I->getOperand(1)))
1325         switch (Op0I->getOpcode()) {
1326         case Instruction::Add:
1327           // ~(X-c) --> (-c-1)-X
1328           if (RHS->isAllOnesValue()) {
1329             Constant *NegOp0CI = ConstantExpr::get(Instruction::Sub,
1330                                Constant::getNullValue(Op0CI->getType()), Op0CI);
1331             return BinaryOperator::create(Instruction::Sub,
1332                            ConstantExpr::get(Instruction::Sub, NegOp0CI,
1333                                              ConstantInt::get(I.getType(), 1)),
1334                                           Op0I->getOperand(0));
1335           }
1336           break;
1337         case Instruction::And:
1338           // (X & C1) ^ C2 --> (X & C1) | C2 iff (C1&C2) == 0
1339           if (ConstantExpr::get(Instruction::And, RHS, Op0CI)->isNullValue())
1340             return BinaryOperator::create(Instruction::Or, Op0, RHS);
1341           break;
1342         case Instruction::Or:
1343           // (X | C1) ^ C2 --> (X | C1) & ~C2 iff (C1&C2) == C2
1344           if (ConstantExpr::get(Instruction::And, RHS, Op0CI) == RHS)
1345             return BinaryOperator::create(Instruction::And, Op0,
1346                                           NotConstant(RHS));
1347           break;
1348         default: break;
1349         }
1350     }
1351
1352     // Try to fold constant and into select arguments.
1353     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1354       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
1355         return R;
1356   }
1357
1358   if (Value *X = dyn_castNotVal(Op0))   // ~A ^ A == -1
1359     if (X == Op1)
1360       return ReplaceInstUsesWith(I,
1361                                 ConstantIntegral::getAllOnesValue(I.getType()));
1362
1363   if (Value *X = dyn_castNotVal(Op1))   // A ^ ~A == -1
1364     if (X == Op0)
1365       return ReplaceInstUsesWith(I,
1366                                 ConstantIntegral::getAllOnesValue(I.getType()));
1367
1368   if (Instruction *Op1I = dyn_cast<Instruction>(Op1))
1369     if (Op1I->getOpcode() == Instruction::Or) {
1370       if (Op1I->getOperand(0) == Op0) {              // B^(B|A) == (A|B)^B
1371         cast<BinaryOperator>(Op1I)->swapOperands();
1372         I.swapOperands();
1373         std::swap(Op0, Op1);
1374       } else if (Op1I->getOperand(1) == Op0) {       // B^(A|B) == (A|B)^B
1375         I.swapOperands();
1376         std::swap(Op0, Op1);
1377       }
1378     } else if (Op1I->getOpcode() == Instruction::Xor) {
1379       if (Op0 == Op1I->getOperand(0))                        // A^(A^B) == B
1380         return ReplaceInstUsesWith(I, Op1I->getOperand(1));
1381       else if (Op0 == Op1I->getOperand(1))                   // A^(B^A) == B
1382         return ReplaceInstUsesWith(I, Op1I->getOperand(0));
1383     }
1384
1385   if (Instruction *Op0I = dyn_cast<Instruction>(Op0))
1386     if (Op0I->getOpcode() == Instruction::Or && Op0I->hasOneUse()) {
1387       if (Op0I->getOperand(0) == Op1)                // (B|A)^B == (A|B)^B
1388         cast<BinaryOperator>(Op0I)->swapOperands();
1389       if (Op0I->getOperand(1) == Op1) {              // (A|B)^B == A & ~B
1390         Value *NotB = BinaryOperator::createNot(Op1, Op1->getName()+".not", &I);
1391         WorkList.push_back(cast<Instruction>(NotB));
1392         return BinaryOperator::create(Instruction::And, Op0I->getOperand(0),
1393                                       NotB);
1394       }
1395     } else if (Op0I->getOpcode() == Instruction::Xor) {
1396       if (Op1 == Op0I->getOperand(0))                        // (A^B)^A == B
1397         return ReplaceInstUsesWith(I, Op0I->getOperand(1));
1398       else if (Op1 == Op0I->getOperand(1))                   // (B^A)^A == B
1399         return ReplaceInstUsesWith(I, Op0I->getOperand(0));
1400     }
1401
1402   // (A & C1)^(B & C2) -> (A & C1)|(B & C2) iff C1^C2 == 0
1403   if (Constant *C1 = dyn_castMaskingAnd(Op0))
1404     if (Constant *C2 = dyn_castMaskingAnd(Op1))
1405       if (ConstantExpr::get(Instruction::And, C1, C2)->isNullValue())
1406         return BinaryOperator::create(Instruction::Or, Op0, Op1);
1407
1408   // (setcc1 A, B) ^ (setcc2 A, B) --> (setcc3 A, B)
1409   if (SetCondInst *RHS = dyn_cast<SetCondInst>(I.getOperand(1)))
1410     if (Instruction *R = AssociativeOpt(I, FoldSetCCLogical(*this, RHS)))
1411       return R;
1412
1413   return Changed ? &I : 0;
1414 }
1415
1416 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
1417 static Constant *AddOne(ConstantInt *C) {
1418   Constant *Result = ConstantExpr::get(Instruction::Add, C,
1419                                        ConstantInt::get(C->getType(), 1));
1420   assert(Result && "Constant folding integer addition failed!");
1421   return Result;
1422 }
1423 static Constant *SubOne(ConstantInt *C) {
1424   Constant *Result = ConstantExpr::get(Instruction::Sub, C,
1425                                        ConstantInt::get(C->getType(), 1));
1426   assert(Result && "Constant folding integer addition failed!");
1427   return Result;
1428 }
1429
1430 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
1431 // true when both operands are equal...
1432 //
1433 static bool isTrueWhenEqual(Instruction &I) {
1434   return I.getOpcode() == Instruction::SetEQ ||
1435          I.getOpcode() == Instruction::SetGE ||
1436          I.getOpcode() == Instruction::SetLE;
1437 }
1438
1439 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
1440   bool Changed = SimplifyCommutative(I);
1441   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1442   const Type *Ty = Op0->getType();
1443
1444   // setcc X, X
1445   if (Op0 == Op1)
1446     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
1447
1448   // setcc <global/alloca*>, 0 - Global/Stack value addresses are never null!
1449   if (isa<ConstantPointerNull>(Op1) &&
1450       (isa<GlobalValue>(Op0) || isa<AllocaInst>(Op0)))
1451     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
1452
1453
1454   // setcc's with boolean values can always be turned into bitwise operations
1455   if (Ty == Type::BoolTy) {
1456     // If this is <, >, or !=, we can change this into a simple xor instruction
1457     if (!isTrueWhenEqual(I))
1458       return BinaryOperator::create(Instruction::Xor, Op0, Op1);
1459
1460     // Otherwise we need to make a temporary intermediate instruction and insert
1461     // it into the instruction stream.  This is what we are after:
1462     //
1463     //  seteq bool %A, %B -> ~(A^B)
1464     //  setle bool %A, %B -> ~A | B
1465     //  setge bool %A, %B -> A | ~B
1466     //
1467     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
1468       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
1469                                                 I.getName()+"tmp");
1470       InsertNewInstBefore(Xor, I);
1471       return BinaryOperator::createNot(Xor);
1472     }
1473
1474     // Handle the setXe cases...
1475     assert(I.getOpcode() == Instruction::SetGE ||
1476            I.getOpcode() == Instruction::SetLE);
1477
1478     if (I.getOpcode() == Instruction::SetGE)
1479       std::swap(Op0, Op1);                   // Change setge -> setle
1480
1481     // Now we just have the SetLE case.
1482     Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
1483     InsertNewInstBefore(Not, I);
1484     return BinaryOperator::create(Instruction::Or, Not, Op1);
1485   }
1486
1487   // Check to see if we are doing one of many comparisons against constant
1488   // integers at the end of their ranges...
1489   //
1490   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
1491     // Simplify seteq and setne instructions...
1492     if (I.getOpcode() == Instruction::SetEQ ||
1493         I.getOpcode() == Instruction::SetNE) {
1494       bool isSetNE = I.getOpcode() == Instruction::SetNE;
1495
1496       // If the first operand is (and|or|xor) with a constant, and the second
1497       // operand is a constant, simplify a bit.
1498       if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0)) {
1499         switch (BO->getOpcode()) {
1500         case Instruction::Add:
1501           if (CI->isNullValue()) {
1502             // Replace ((add A, B) != 0) with (A != -B) if A or B is
1503             // efficiently invertible, or if the add has just this one use.
1504             Value *BOp0 = BO->getOperand(0), *BOp1 = BO->getOperand(1);
1505             if (Value *NegVal = dyn_castNegVal(BOp1))
1506               return new SetCondInst(I.getOpcode(), BOp0, NegVal);
1507             else if (Value *NegVal = dyn_castNegVal(BOp0))
1508               return new SetCondInst(I.getOpcode(), NegVal, BOp1);
1509             else if (BO->hasOneUse()) {
1510               Instruction *Neg = BinaryOperator::createNeg(BOp1, BO->getName());
1511               BO->setName("");
1512               InsertNewInstBefore(Neg, I);
1513               return new SetCondInst(I.getOpcode(), BOp0, Neg);
1514             }
1515           }
1516           break;
1517         case Instruction::Xor:
1518           // For the xor case, we can xor two constants together, eliminating
1519           // the explicit xor.
1520           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1)))
1521             return BinaryOperator::create(I.getOpcode(), BO->getOperand(0),
1522                                   ConstantExpr::get(Instruction::Xor, CI, BOC));
1523
1524           // FALLTHROUGH
1525         case Instruction::Sub:
1526           // Replace (([sub|xor] A, B) != 0) with (A != B)
1527           if (CI->isNullValue())
1528             return new SetCondInst(I.getOpcode(), BO->getOperand(0),
1529                                    BO->getOperand(1));
1530           break;
1531
1532         case Instruction::Or:
1533           // If bits are being or'd in that are not present in the constant we
1534           // are comparing against, then the comparison could never succeed!
1535           if (Constant *BOC = dyn_cast<Constant>(BO->getOperand(1))) {
1536             Constant *NotCI = NotConstant(CI);
1537             if (!ConstantExpr::get(Instruction::And, BOC, NotCI)->isNullValue())
1538               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1539           }
1540           break;
1541
1542         case Instruction::And:
1543           if (ConstantInt *BOC = dyn_cast<ConstantInt>(BO->getOperand(1))) {
1544             // If bits are being compared against that are and'd out, then the
1545             // comparison can never succeed!
1546             if (!ConstantExpr::get(Instruction::And, CI,
1547                                    NotConstant(BOC))->isNullValue())
1548               return ReplaceInstUsesWith(I, ConstantBool::get(isSetNE));
1549
1550             // Replace (and X, (1 << size(X)-1) != 0) with x < 0, converting X
1551             // to be a signed value as appropriate.
1552             if (isSignBit(BOC)) {
1553               Value *X = BO->getOperand(0);
1554               // If 'X' is not signed, insert a cast now...
1555               if (!BOC->getType()->isSigned()) {
1556                 const Type *DestTy = getSignedIntegralType(BOC->getType());
1557                 CastInst *NewCI = new CastInst(X,DestTy,X->getName()+".signed");
1558                 InsertNewInstBefore(NewCI, I);
1559                 X = NewCI;
1560               }
1561               return new SetCondInst(isSetNE ? Instruction::SetLT :
1562                                          Instruction::SetGE, X,
1563                                      Constant::getNullValue(X->getType()));
1564             }
1565           }
1566         default: break;
1567         }
1568       }
1569     } else {  // Not a SetEQ/SetNE
1570       // If the LHS is a cast from an integral value of the same size,
1571       if (CastInst *Cast = dyn_cast<CastInst>(Op0)) {
1572         Value *CastOp = Cast->getOperand(0);
1573         const Type *SrcTy = CastOp->getType();
1574         unsigned SrcTySize = SrcTy->getPrimitiveSize();
1575         if (SrcTy != Cast->getType() && SrcTy->isInteger() &&
1576             SrcTySize == Cast->getType()->getPrimitiveSize()) {
1577           assert((SrcTy->isSigned() ^ Cast->getType()->isSigned()) &&
1578                  "Source and destination signednesses should differ!");
1579           if (Cast->getType()->isSigned()) {
1580             // If this is a signed comparison, check for comparisons in the
1581             // vicinity of zero.
1582             if (I.getOpcode() == Instruction::SetLT && CI->isNullValue())
1583               // X < 0  => x > 127
1584               return BinaryOperator::create(Instruction::SetGT, CastOp,
1585                          ConstantUInt::get(SrcTy, (1ULL << (SrcTySize*8-1))-1));
1586             else if (I.getOpcode() == Instruction::SetGT &&
1587                      cast<ConstantSInt>(CI)->getValue() == -1)
1588               // X > -1  => x < 128
1589               return BinaryOperator::create(Instruction::SetLT, CastOp,
1590                          ConstantUInt::get(SrcTy, 1ULL << (SrcTySize*8-1)));
1591           } else {
1592             ConstantUInt *CUI = cast<ConstantUInt>(CI);
1593             if (I.getOpcode() == Instruction::SetLT &&
1594                 CUI->getValue() == 1ULL << (SrcTySize*8-1))
1595               // X < 128 => X > -1
1596               return BinaryOperator::create(Instruction::SetGT, CastOp,
1597                                             ConstantSInt::get(SrcTy, -1));
1598             else if (I.getOpcode() == Instruction::SetGT &&
1599                      CUI->getValue() == (1ULL << (SrcTySize*8-1))-1)
1600               // X > 127 => X < 0
1601               return BinaryOperator::create(Instruction::SetLT, CastOp,
1602                                             Constant::getNullValue(SrcTy));
1603           }
1604         }
1605       }
1606     }
1607
1608     // Check to see if we are comparing against the minimum or maximum value...
1609     if (CI->isMinValue()) {
1610       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
1611         return ReplaceInstUsesWith(I, ConstantBool::False);
1612       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
1613         return ReplaceInstUsesWith(I, ConstantBool::True);
1614       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
1615         return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
1616       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
1617         return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
1618
1619     } else if (CI->isMaxValue()) {
1620       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
1621         return ReplaceInstUsesWith(I, ConstantBool::False);
1622       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
1623         return ReplaceInstUsesWith(I, ConstantBool::True);
1624       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
1625         return BinaryOperator::create(Instruction::SetEQ, Op0, Op1);
1626       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
1627         return BinaryOperator::create(Instruction::SetNE, Op0, Op1);
1628
1629       // Comparing against a value really close to min or max?
1630     } else if (isMinValuePlusOne(CI)) {
1631       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
1632         return BinaryOperator::create(Instruction::SetEQ, Op0, SubOne(CI));
1633       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
1634         return BinaryOperator::create(Instruction::SetNE, Op0, SubOne(CI));
1635
1636     } else if (isMaxValueMinusOne(CI)) {
1637       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
1638         return BinaryOperator::create(Instruction::SetEQ, Op0, AddOne(CI));
1639       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
1640         return BinaryOperator::create(Instruction::SetNE, Op0, AddOne(CI));
1641     }
1642
1643     // If we still have a setle or setge instruction, turn it into the
1644     // appropriate setlt or setgt instruction.  Since the border cases have
1645     // already been handled above, this requires little checking.
1646     //
1647     if (I.getOpcode() == Instruction::SetLE)
1648       return BinaryOperator::create(Instruction::SetLT, Op0, AddOne(CI));
1649     if (I.getOpcode() == Instruction::SetGE)
1650       return BinaryOperator::create(Instruction::SetGT, Op0, SubOne(CI));
1651   }
1652
1653   // Test to see if the operands of the setcc are casted versions of other
1654   // values.  If the cast can be stripped off both arguments, we do so now.
1655   if (CastInst *CI = dyn_cast<CastInst>(Op0)) {
1656     Value *CastOp0 = CI->getOperand(0);
1657     if (CastOp0->getType()->isLosslesslyConvertibleTo(CI->getType()) &&
1658         (isa<Constant>(Op1) || isa<CastInst>(Op1)) &&
1659         (I.getOpcode() == Instruction::SetEQ ||
1660          I.getOpcode() == Instruction::SetNE)) {
1661       // We keep moving the cast from the left operand over to the right
1662       // operand, where it can often be eliminated completely.
1663       Op0 = CastOp0;
1664
1665       // If operand #1 is a cast instruction, see if we can eliminate it as
1666       // well.
1667       if (CastInst *CI2 = dyn_cast<CastInst>(Op1))
1668         if (CI2->getOperand(0)->getType()->isLosslesslyConvertibleTo(
1669                                                                Op0->getType()))
1670           Op1 = CI2->getOperand(0);
1671
1672       // If Op1 is a constant, we can fold the cast into the constant.
1673       if (Op1->getType() != Op0->getType())
1674         if (Constant *Op1C = dyn_cast<Constant>(Op1)) {
1675           Op1 = ConstantExpr::getCast(Op1C, Op0->getType());
1676         } else {
1677           // Otherwise, cast the RHS right before the setcc
1678           Op1 = new CastInst(Op1, Op0->getType(), Op1->getName());
1679           InsertNewInstBefore(cast<Instruction>(Op1), I);
1680         }
1681       return BinaryOperator::create(I.getOpcode(), Op0, Op1);
1682     }
1683
1684     // Handle the special case of: setcc (cast bool to X), <cst>
1685     // This comes up when you have code like
1686     //   int X = A < B;
1687     //   if (X) ...
1688     // For generality, we handle any zero-extension of any operand comparison
1689     // with a constant.
1690     if (ConstantInt *ConstantRHS = dyn_cast<ConstantInt>(Op1)) {
1691       const Type *SrcTy = CastOp0->getType();
1692       const Type *DestTy = Op0->getType();
1693       if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
1694           (SrcTy->isUnsigned() || SrcTy == Type::BoolTy)) {
1695         // Ok, we have an expansion of operand 0 into a new type.  Get the
1696         // constant value, masink off bits which are not set in the RHS.  These
1697         // could be set if the destination value is signed.
1698         uint64_t ConstVal = ConstantRHS->getRawValue();
1699         ConstVal &= (1ULL << DestTy->getPrimitiveSize()*8)-1;
1700
1701         // If the constant we are comparing it with has high bits set, which
1702         // don't exist in the original value, the values could never be equal,
1703         // because the source would be zero extended.
1704         unsigned SrcBits =
1705           SrcTy == Type::BoolTy ? 1 : SrcTy->getPrimitiveSize()*8;
1706         bool HasSignBit = ConstVal & (1ULL << (DestTy->getPrimitiveSize()*8-1));
1707         if (ConstVal & ~((1ULL << SrcBits)-1)) {
1708           switch (I.getOpcode()) {
1709           default: assert(0 && "Unknown comparison type!");
1710           case Instruction::SetEQ:
1711             return ReplaceInstUsesWith(I, ConstantBool::False);
1712           case Instruction::SetNE:
1713             return ReplaceInstUsesWith(I, ConstantBool::True);
1714           case Instruction::SetLT:
1715           case Instruction::SetLE:
1716             if (DestTy->isSigned() && HasSignBit)
1717               return ReplaceInstUsesWith(I, ConstantBool::False);
1718             return ReplaceInstUsesWith(I, ConstantBool::True);
1719           case Instruction::SetGT:
1720           case Instruction::SetGE:
1721             if (DestTy->isSigned() && HasSignBit)
1722               return ReplaceInstUsesWith(I, ConstantBool::True);
1723             return ReplaceInstUsesWith(I, ConstantBool::False);
1724           }
1725         }
1726
1727         // Otherwise, we can replace the setcc with a setcc of the smaller
1728         // operand value.
1729         Op1 = ConstantExpr::getCast(cast<Constant>(Op1), SrcTy);
1730         return BinaryOperator::create(I.getOpcode(), CastOp0, Op1);
1731       }
1732     }
1733   }
1734   return Changed ? &I : 0;
1735 }
1736
1737
1738
1739 Instruction *InstCombiner::visitShiftInst(ShiftInst &I) {
1740   assert(I.getOperand(1)->getType() == Type::UByteTy);
1741   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
1742   bool isLeftShift = I.getOpcode() == Instruction::Shl;
1743
1744   // shl X, 0 == X and shr X, 0 == X
1745   // shl 0, X == 0 and shr 0, X == 0
1746   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
1747       Op0 == Constant::getNullValue(Op0->getType()))
1748     return ReplaceInstUsesWith(I, Op0);
1749
1750   // shr int -1, X = -1   (for any arithmetic shift rights of ~0)
1751   if (!isLeftShift)
1752     if (ConstantSInt *CSI = dyn_cast<ConstantSInt>(Op0))
1753       if (CSI->isAllOnesValue())
1754         return ReplaceInstUsesWith(I, CSI);
1755
1756   // Try to fold constant and into select arguments.
1757   if (isa<Constant>(Op0))
1758     if (SelectInst *SI = dyn_cast<SelectInst>(Op1))
1759       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
1760         return R;
1761
1762   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
1763     // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr
1764     // of a signed value.
1765     //
1766     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
1767     if (CUI->getValue() >= TypeBits) {
1768       if (!Op0->getType()->isSigned() || isLeftShift)
1769         return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
1770       else {
1771         I.setOperand(1, ConstantUInt::get(Type::UByteTy, TypeBits-1));
1772         return &I;
1773       }
1774     }
1775
1776     // ((X*C1) << C2) == (X * (C1 << C2))
1777     if (BinaryOperator *BO = dyn_cast<BinaryOperator>(Op0))
1778       if (BO->getOpcode() == Instruction::Mul && isLeftShift)
1779         if (Constant *BOOp = dyn_cast<Constant>(BO->getOperand(1)))
1780           return BinaryOperator::create(Instruction::Mul, BO->getOperand(0),
1781                                 ConstantExpr::get(Instruction::Shl, BOOp, CUI));
1782
1783     // Try to fold constant and into select arguments.
1784     if (SelectInst *SI = dyn_cast<SelectInst>(Op0))
1785       if (Instruction *R = FoldBinOpIntoSelect(I, SI, this))
1786         return R;
1787
1788     // If the operand is an bitwise operator with a constant RHS, and the
1789     // shift is the only use, we can pull it out of the shift.
1790     if (Op0->hasOneUse())
1791       if (BinaryOperator *Op0BO = dyn_cast<BinaryOperator>(Op0))
1792         if (ConstantInt *Op0C = dyn_cast<ConstantInt>(Op0BO->getOperand(1))) {
1793           bool isValid = true;     // Valid only for And, Or, Xor
1794           bool highBitSet = false; // Transform if high bit of constant set?
1795
1796           switch (Op0BO->getOpcode()) {
1797           default: isValid = false; break;   // Do not perform transform!
1798           case Instruction::Or:
1799           case Instruction::Xor:
1800             highBitSet = false;
1801             break;
1802           case Instruction::And:
1803             highBitSet = true;
1804             break;
1805           }
1806
1807           // If this is a signed shift right, and the high bit is modified
1808           // by the logical operation, do not perform the transformation.
1809           // The highBitSet boolean indicates the value of the high bit of
1810           // the constant which would cause it to be modified for this
1811           // operation.
1812           //
1813           if (isValid && !isLeftShift && !I.getType()->isUnsigned()) {
1814             uint64_t Val = Op0C->getRawValue();
1815             isValid = ((Val & (1 << (TypeBits-1))) != 0) == highBitSet;
1816           }
1817
1818           if (isValid) {
1819             Constant *NewRHS = ConstantExpr::get(I.getOpcode(), Op0C, CUI);
1820
1821             Instruction *NewShift =
1822               new ShiftInst(I.getOpcode(), Op0BO->getOperand(0), CUI,
1823                             Op0BO->getName());
1824             Op0BO->setName("");
1825             InsertNewInstBefore(NewShift, I);
1826
1827             return BinaryOperator::create(Op0BO->getOpcode(), NewShift,
1828                                           NewRHS);
1829           }
1830         }
1831
1832     // If this is a shift of a shift, see if we can fold the two together...
1833     if (ShiftInst *Op0SI = dyn_cast<ShiftInst>(Op0))
1834       if (ConstantUInt *ShiftAmt1C =
1835                                  dyn_cast<ConstantUInt>(Op0SI->getOperand(1))) {
1836         unsigned ShiftAmt1 = ShiftAmt1C->getValue();
1837         unsigned ShiftAmt2 = CUI->getValue();
1838
1839         // Check for (A << c1) << c2   and   (A >> c1) >> c2
1840         if (I.getOpcode() == Op0SI->getOpcode()) {
1841           unsigned Amt = ShiftAmt1+ShiftAmt2;   // Fold into one big shift...
1842           if (Op0->getType()->getPrimitiveSize()*8 < Amt)
1843             Amt = Op0->getType()->getPrimitiveSize()*8;
1844           return new ShiftInst(I.getOpcode(), Op0SI->getOperand(0),
1845                                ConstantUInt::get(Type::UByteTy, Amt));
1846         }
1847
1848         // Check for (A << c1) >> c2 or visaversa.  If we are dealing with
1849         // signed types, we can only support the (A >> c1) << c2 configuration,
1850         // because it can not turn an arbitrary bit of A into a sign bit.
1851         if (I.getType()->isUnsigned() || isLeftShift) {
1852           // Calculate bitmask for what gets shifted off the edge...
1853           Constant *C = ConstantIntegral::getAllOnesValue(I.getType());
1854           if (isLeftShift)
1855             C = ConstantExpr::get(Instruction::Shl, C, ShiftAmt1C);
1856           else
1857             C = ConstantExpr::get(Instruction::Shr, C, ShiftAmt1C);
1858
1859           Instruction *Mask =
1860             BinaryOperator::create(Instruction::And, Op0SI->getOperand(0),
1861                                    C, Op0SI->getOperand(0)->getName()+".mask");
1862           InsertNewInstBefore(Mask, I);
1863
1864           // Figure out what flavor of shift we should use...
1865           if (ShiftAmt1 == ShiftAmt2)
1866             return ReplaceInstUsesWith(I, Mask);  // (A << c) >> c  === A & c2
1867           else if (ShiftAmt1 < ShiftAmt2) {
1868             return new ShiftInst(I.getOpcode(), Mask,
1869                          ConstantUInt::get(Type::UByteTy, ShiftAmt2-ShiftAmt1));
1870           } else {
1871             return new ShiftInst(Op0SI->getOpcode(), Mask,
1872                          ConstantUInt::get(Type::UByteTy, ShiftAmt1-ShiftAmt2));
1873           }
1874         }
1875       }
1876   }
1877
1878   return 0;
1879 }
1880
1881
1882 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
1883 // instruction.
1884 //
1885 static inline bool isEliminableCastOfCast(const Type *SrcTy, const Type *MidTy,
1886                                           const Type *DstTy) {
1887
1888   // It is legal to eliminate the instruction if casting A->B->A if the sizes
1889   // are identical and the bits don't get reinterpreted (for example
1890   // int->float->int would not be allowed)
1891   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertibleTo(MidTy))
1892     return true;
1893
1894   // Allow free casting and conversion of sizes as long as the sign doesn't
1895   // change...
1896   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral()) {
1897     unsigned SrcSize = SrcTy->getPrimitiveSize();
1898     unsigned MidSize = MidTy->getPrimitiveSize();
1899     unsigned DstSize = DstTy->getPrimitiveSize();
1900
1901     // Cases where we are monotonically decreasing the size of the type are
1902     // always ok, regardless of what sign changes are going on.
1903     //
1904     if (SrcSize >= MidSize && MidSize >= DstSize)
1905       return true;
1906
1907     // Cases where the source and destination type are the same, but the middle
1908     // type is bigger are noops.
1909     //
1910     if (SrcSize == DstSize && MidSize > SrcSize)
1911       return true;
1912
1913     // If we are monotonically growing, things are more complex.
1914     //
1915     if (SrcSize <= MidSize && MidSize <= DstSize) {
1916       // We have eight combinations of signedness to worry about. Here's the
1917       // table:
1918       static const int SignTable[8] = {
1919         // CODE, SrcSigned, MidSigned, DstSigned, Comment
1920         1,     //   U          U          U       Always ok
1921         1,     //   U          U          S       Always ok
1922         3,     //   U          S          U       Ok iff SrcSize != MidSize
1923         3,     //   U          S          S       Ok iff SrcSize != MidSize
1924         0,     //   S          U          U       Never ok
1925         2,     //   S          U          S       Ok iff MidSize == DstSize
1926         1,     //   S          S          U       Always ok
1927         1,     //   S          S          S       Always ok
1928       };
1929
1930       // Choose an action based on the current entry of the signtable that this
1931       // cast of cast refers to...
1932       unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
1933       switch (SignTable[Row]) {
1934       case 0: return false;              // Never ok
1935       case 1: return true;               // Always ok
1936       case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
1937       case 3:                            // Ok iff SrcSize != MidSize
1938         return SrcSize != MidSize || SrcTy == Type::BoolTy;
1939       default: assert(0 && "Bad entry in sign table!");
1940       }
1941     }
1942   }
1943
1944   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
1945   // like:  short -> ushort -> uint, because this can create wrong results if
1946   // the input short is negative!
1947   //
1948   return false;
1949 }
1950
1951 static bool ValueRequiresCast(const Value *V, const Type *Ty) {
1952   if (V->getType() == Ty || isa<Constant>(V)) return false;
1953   if (const CastInst *CI = dyn_cast<CastInst>(V))
1954     if (isEliminableCastOfCast(CI->getOperand(0)->getType(), CI->getType(), Ty))
1955       return false;
1956   return true;
1957 }
1958
1959 /// InsertOperandCastBefore - This inserts a cast of V to DestTy before the
1960 /// InsertBefore instruction.  This is specialized a bit to avoid inserting
1961 /// casts that are known to not do anything...
1962 ///
1963 Value *InstCombiner::InsertOperandCastBefore(Value *V, const Type *DestTy,
1964                                              Instruction *InsertBefore) {
1965   if (V->getType() == DestTy) return V;
1966   if (Constant *C = dyn_cast<Constant>(V))
1967     return ConstantExpr::getCast(C, DestTy);
1968
1969   CastInst *CI = new CastInst(V, DestTy, V->getName());
1970   InsertNewInstBefore(CI, *InsertBefore);
1971   return CI;
1972 }
1973
1974 // CastInst simplification
1975 //
1976 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
1977   Value *Src = CI.getOperand(0);
1978
1979   // If the user is casting a value to the same type, eliminate this cast
1980   // instruction...
1981   if (CI.getType() == Src->getType())
1982     return ReplaceInstUsesWith(CI, Src);
1983
1984   // If casting the result of another cast instruction, try to eliminate this
1985   // one!
1986   //
1987   if (CastInst *CSrc = dyn_cast<CastInst>(Src)) {
1988     if (isEliminableCastOfCast(CSrc->getOperand(0)->getType(),
1989                                CSrc->getType(), CI.getType())) {
1990       // This instruction now refers directly to the cast's src operand.  This
1991       // has a good chance of making CSrc dead.
1992       CI.setOperand(0, CSrc->getOperand(0));
1993       return &CI;
1994     }
1995
1996     // If this is an A->B->A cast, and we are dealing with integral types, try
1997     // to convert this into a logical 'and' instruction.
1998     //
1999     if (CSrc->getOperand(0)->getType() == CI.getType() &&
2000         CI.getType()->isInteger() && CSrc->getType()->isInteger() &&
2001         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
2002         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
2003       assert(CSrc->getType() != Type::ULongTy &&
2004              "Cannot have type bigger than ulong!");
2005       uint64_t AndValue = (1ULL << CSrc->getType()->getPrimitiveSize()*8)-1;
2006       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
2007       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
2008                                     AndOp);
2009     }
2010   }
2011
2012   // If casting the result of a getelementptr instruction with no offset, turn
2013   // this into a cast of the original pointer!
2014   //
2015   if (GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(Src)) {
2016     bool AllZeroOperands = true;
2017     for (unsigned i = 1, e = GEP->getNumOperands(); i != e; ++i)
2018       if (!isa<Constant>(GEP->getOperand(i)) ||
2019           !cast<Constant>(GEP->getOperand(i))->isNullValue()) {
2020         AllZeroOperands = false;
2021         break;
2022       }
2023     if (AllZeroOperands) {
2024       CI.setOperand(0, GEP->getOperand(0));
2025       return &CI;
2026     }
2027   }
2028
2029   // If we are casting a malloc or alloca to a pointer to a type of the same
2030   // size, rewrite the allocation instruction to allocate the "right" type.
2031   //
2032   if (AllocationInst *AI = dyn_cast<AllocationInst>(Src))
2033     if (AI->hasOneUse() && !AI->isArrayAllocation())
2034       if (const PointerType *PTy = dyn_cast<PointerType>(CI.getType())) {
2035         // Get the type really allocated and the type casted to...
2036         const Type *AllocElTy = AI->getAllocatedType();
2037         unsigned AllocElTySize = TD->getTypeSize(AllocElTy);
2038         const Type *CastElTy = PTy->getElementType();
2039         unsigned CastElTySize = TD->getTypeSize(CastElTy);
2040
2041         // If the allocation is for an even multiple of the cast type size
2042         if (CastElTySize && (AllocElTySize % CastElTySize == 0)) {
2043           Value *Amt = ConstantUInt::get(Type::UIntTy,
2044                                          AllocElTySize/CastElTySize);
2045           std::string Name = AI->getName(); AI->setName("");
2046           AllocationInst *New;
2047           if (isa<MallocInst>(AI))
2048             New = new MallocInst(CastElTy, Amt, Name);
2049           else
2050             New = new AllocaInst(CastElTy, Amt, Name);
2051           InsertNewInstBefore(New, CI);
2052           return ReplaceInstUsesWith(CI, New);
2053         }
2054       }
2055
2056   // If the source value is an instruction with only this use, we can attempt to
2057   // propagate the cast into the instruction.  Also, only handle integral types
2058   // for now.
2059   if (Instruction *SrcI = dyn_cast<Instruction>(Src))
2060     if (SrcI->hasOneUse() && Src->getType()->isIntegral() &&
2061         CI.getType()->isInteger()) {  // Don't mess with casts to bool here
2062       const Type *DestTy = CI.getType();
2063       unsigned SrcBitSize = getTypeSizeInBits(Src->getType());
2064       unsigned DestBitSize = getTypeSizeInBits(DestTy);
2065
2066       Value *Op0 = SrcI->getNumOperands() > 0 ? SrcI->getOperand(0) : 0;
2067       Value *Op1 = SrcI->getNumOperands() > 1 ? SrcI->getOperand(1) : 0;
2068
2069       switch (SrcI->getOpcode()) {
2070       case Instruction::Add:
2071       case Instruction::Mul:
2072       case Instruction::And:
2073       case Instruction::Or:
2074       case Instruction::Xor:
2075         // If we are discarding information, or just changing the sign, rewrite.
2076         if (DestBitSize <= SrcBitSize && DestBitSize != 1) {
2077           // Don't insert two casts if they cannot be eliminated.  We allow two
2078           // casts to be inserted if the sizes are the same.  This could only be
2079           // converting signedness, which is a noop.
2080           if (DestBitSize == SrcBitSize || !ValueRequiresCast(Op1, DestTy) ||
2081               !ValueRequiresCast(Op0, DestTy)) {
2082             Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
2083             Value *Op1c = InsertOperandCastBefore(Op1, DestTy, SrcI);
2084             return BinaryOperator::create(cast<BinaryOperator>(SrcI)
2085                              ->getOpcode(), Op0c, Op1c);
2086           }
2087         }
2088         break;
2089       case Instruction::Shl:
2090         // Allow changing the sign of the source operand.  Do not allow changing
2091         // the size of the shift, UNLESS the shift amount is a constant.  We
2092         // mush not change variable sized shifts to a smaller size, because it
2093         // is undefined to shift more bits out than exist in the value.
2094         if (DestBitSize == SrcBitSize ||
2095             (DestBitSize < SrcBitSize && isa<Constant>(Op1))) {
2096           Value *Op0c = InsertOperandCastBefore(Op0, DestTy, SrcI);
2097           return new ShiftInst(Instruction::Shl, Op0c, Op1);
2098         }
2099         break;
2100       }
2101     }
2102
2103   return 0;
2104 }
2105
2106 /// GetSelectFoldableOperands - We want to turn code that looks like this:
2107 ///   %C = or %A, %B
2108 ///   %D = select %cond, %C, %A
2109 /// into:
2110 ///   %C = select %cond, %B, 0
2111 ///   %D = or %A, %C
2112 ///
2113 /// Assuming that the specified instruction is an operand to the select, return
2114 /// a bitmask indicating which operands of this instruction are foldable if they
2115 /// equal the other incoming value of the select.
2116 ///
2117 static unsigned GetSelectFoldableOperands(Instruction *I) {
2118   switch (I->getOpcode()) {
2119   case Instruction::Add:
2120   case Instruction::Mul:
2121   case Instruction::And:
2122   case Instruction::Or:
2123   case Instruction::Xor:
2124     return 3;              // Can fold through either operand.
2125   case Instruction::Sub:   // Can only fold on the amount subtracted.
2126   case Instruction::Shl:   // Can only fold on the shift amount.
2127   case Instruction::Shr:
2128     return 1;
2129   default:
2130     return 0;              // Cannot fold
2131   }
2132 }
2133
2134 /// GetSelectFoldableConstant - For the same transformation as the previous
2135 /// function, return the identity constant that goes into the select.
2136 static Constant *GetSelectFoldableConstant(Instruction *I) {
2137   switch (I->getOpcode()) {
2138   default: assert(0 && "This cannot happen!"); abort();
2139   case Instruction::Add:
2140   case Instruction::Sub:
2141   case Instruction::Or:
2142   case Instruction::Xor:
2143     return Constant::getNullValue(I->getType());
2144   case Instruction::Shl:
2145   case Instruction::Shr:
2146     return Constant::getNullValue(Type::UByteTy);
2147   case Instruction::And:
2148     return ConstantInt::getAllOnesValue(I->getType());
2149   case Instruction::Mul:
2150     return ConstantInt::get(I->getType(), 1);
2151   }
2152 }
2153
2154 Instruction *InstCombiner::visitSelectInst(SelectInst &SI) {
2155   Value *CondVal = SI.getCondition();
2156   Value *TrueVal = SI.getTrueValue();
2157   Value *FalseVal = SI.getFalseValue();
2158
2159   // select true, X, Y  -> X
2160   // select false, X, Y -> Y
2161   if (ConstantBool *C = dyn_cast<ConstantBool>(CondVal))
2162     if (C == ConstantBool::True)
2163       return ReplaceInstUsesWith(SI, TrueVal);
2164     else {
2165       assert(C == ConstantBool::False);
2166       return ReplaceInstUsesWith(SI, FalseVal);
2167     }
2168
2169   // select C, X, X -> X
2170   if (TrueVal == FalseVal)
2171     return ReplaceInstUsesWith(SI, TrueVal);
2172
2173   if (SI.getType() == Type::BoolTy)
2174     if (ConstantBool *C = dyn_cast<ConstantBool>(TrueVal)) {
2175       if (C == ConstantBool::True) {
2176         // Change: A = select B, true, C --> A = or B, C
2177         return BinaryOperator::create(Instruction::Or, CondVal, FalseVal);
2178       } else {
2179         // Change: A = select B, false, C --> A = and !B, C
2180         Value *NotCond =
2181           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
2182                                              "not."+CondVal->getName()), SI);
2183         return BinaryOperator::create(Instruction::And, NotCond, FalseVal);
2184       }
2185     } else if (ConstantBool *C = dyn_cast<ConstantBool>(FalseVal)) {
2186       if (C == ConstantBool::False) {
2187         // Change: A = select B, C, false --> A = and B, C
2188         return BinaryOperator::create(Instruction::And, CondVal, TrueVal);
2189       } else {
2190         // Change: A = select B, C, true --> A = or !B, C
2191         Value *NotCond =
2192           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
2193                                              "not."+CondVal->getName()), SI);
2194         return BinaryOperator::create(Instruction::Or, NotCond, TrueVal);
2195       }
2196     }
2197
2198   // Selecting between two integer constants?
2199   if (ConstantInt *TrueValC = dyn_cast<ConstantInt>(TrueVal))
2200     if (ConstantInt *FalseValC = dyn_cast<ConstantInt>(FalseVal)) {
2201       // select C, 1, 0 -> cast C to int
2202       if (FalseValC->isNullValue() && TrueValC->getRawValue() == 1) {
2203         return new CastInst(CondVal, SI.getType());
2204       } else if (TrueValC->isNullValue() && FalseValC->getRawValue() == 1) {
2205         // select C, 0, 1 -> cast !C to int
2206         Value *NotCond =
2207           InsertNewInstBefore(BinaryOperator::createNot(CondVal,
2208                                                "not."+CondVal->getName()), SI);
2209         return new CastInst(NotCond, SI.getType());
2210       }
2211     }
2212
2213   // See if we can fold the select into one of our operands.
2214   if (SI.getType()->isInteger()) {
2215     // See the comment above GetSelectFoldableOperands for a description of the
2216     // transformation we are doing here.
2217     if (Instruction *TVI = dyn_cast<Instruction>(TrueVal))
2218       if (TVI->hasOneUse() && TVI->getNumOperands() == 2 &&
2219           !isa<Constant>(FalseVal))
2220         if (unsigned SFO = GetSelectFoldableOperands(TVI)) {
2221           unsigned OpToFold = 0;
2222           if ((SFO & 1) && FalseVal == TVI->getOperand(0)) {
2223             OpToFold = 1;
2224           } else  if ((SFO & 2) && FalseVal == TVI->getOperand(1)) {
2225             OpToFold = 2;
2226           }
2227
2228           if (OpToFold) {
2229             Constant *C = GetSelectFoldableConstant(TVI);
2230             std::string Name = TVI->getName(); TVI->setName("");
2231             Instruction *NewSel =
2232               new SelectInst(SI.getCondition(), TVI->getOperand(2-OpToFold), C,
2233                              Name);
2234             InsertNewInstBefore(NewSel, SI);
2235             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(TVI))
2236               return BinaryOperator::create(BO->getOpcode(), FalseVal, NewSel);
2237             else if (ShiftInst *SI = dyn_cast<ShiftInst>(TVI))
2238               return new ShiftInst(SI->getOpcode(), FalseVal, NewSel);
2239             else {
2240               assert(0 && "Unknown instruction!!");
2241             }
2242           }
2243         }
2244
2245     if (Instruction *FVI = dyn_cast<Instruction>(FalseVal))
2246       if (FVI->hasOneUse() && FVI->getNumOperands() == 2 &&
2247           !isa<Constant>(TrueVal))
2248         if (unsigned SFO = GetSelectFoldableOperands(FVI)) {
2249           unsigned OpToFold = 0;
2250           if ((SFO & 1) && TrueVal == FVI->getOperand(0)) {
2251             OpToFold = 1;
2252           } else  if ((SFO & 2) && TrueVal == FVI->getOperand(1)) {
2253             OpToFold = 2;
2254           }
2255
2256           if (OpToFold) {
2257             Constant *C = GetSelectFoldableConstant(FVI);
2258             std::string Name = FVI->getName(); FVI->setName("");
2259             Instruction *NewSel =
2260               new SelectInst(SI.getCondition(), C, FVI->getOperand(2-OpToFold),
2261                              Name);
2262             InsertNewInstBefore(NewSel, SI);
2263             if (BinaryOperator *BO = dyn_cast<BinaryOperator>(FVI))
2264               return BinaryOperator::create(BO->getOpcode(), TrueVal, NewSel);
2265             else if (ShiftInst *SI = dyn_cast<ShiftInst>(FVI))
2266               return new ShiftInst(SI->getOpcode(), TrueVal, NewSel);
2267             else {
2268               assert(0 && "Unknown instruction!!");
2269             }
2270           }
2271         }
2272   }
2273   return 0;
2274 }
2275
2276
2277 // CallInst simplification
2278 //
2279 Instruction *InstCombiner::visitCallInst(CallInst &CI) {
2280   // Intrinsics cannot occur in an invoke, so handle them here instead of in
2281   // visitCallSite.
2282   if (Function *F = CI.getCalledFunction())
2283     switch (F->getIntrinsicID()) {
2284     case Intrinsic::memmove:
2285     case Intrinsic::memcpy:
2286     case Intrinsic::memset:
2287       // memmove/cpy/set of zero bytes is a noop.
2288       if (Constant *NumBytes = dyn_cast<Constant>(CI.getOperand(3))) {
2289         if (NumBytes->isNullValue())
2290           return EraseInstFromFunction(CI);
2291       }
2292       break;
2293     default:
2294       break;
2295     }
2296
2297   return visitCallSite(&CI);
2298 }
2299
2300 // InvokeInst simplification
2301 //
2302 Instruction *InstCombiner::visitInvokeInst(InvokeInst &II) {
2303   return visitCallSite(&II);
2304 }
2305
2306 // visitCallSite - Improvements for call and invoke instructions.
2307 //
2308 Instruction *InstCombiner::visitCallSite(CallSite CS) {
2309   bool Changed = false;
2310
2311   // If the callee is a constexpr cast of a function, attempt to move the cast
2312   // to the arguments of the call/invoke.
2313   if (transformConstExprCastCall(CS)) return 0;
2314
2315   Value *Callee = CS.getCalledValue();
2316   const PointerType *PTy = cast<PointerType>(Callee->getType());
2317   const FunctionType *FTy = cast<FunctionType>(PTy->getElementType());
2318   if (FTy->isVarArg()) {
2319     // See if we can optimize any arguments passed through the varargs area of
2320     // the call.
2321     for (CallSite::arg_iterator I = CS.arg_begin()+FTy->getNumParams(),
2322            E = CS.arg_end(); I != E; ++I)
2323       if (CastInst *CI = dyn_cast<CastInst>(*I)) {
2324         // If this cast does not effect the value passed through the varargs
2325         // area, we can eliminate the use of the cast.
2326         Value *Op = CI->getOperand(0);
2327         if (CI->getType()->isLosslesslyConvertibleTo(Op->getType())) {
2328           *I = Op;
2329           Changed = true;
2330         }
2331       }
2332   }
2333
2334   return Changed ? CS.getInstruction() : 0;
2335 }
2336
2337 // transformConstExprCastCall - If the callee is a constexpr cast of a function,
2338 // attempt to move the cast to the arguments of the call/invoke.
2339 //
2340 bool InstCombiner::transformConstExprCastCall(CallSite CS) {
2341   if (!isa<ConstantExpr>(CS.getCalledValue())) return false;
2342   ConstantExpr *CE = cast<ConstantExpr>(CS.getCalledValue());
2343   if (CE->getOpcode() != Instruction::Cast ||
2344       !isa<ConstantPointerRef>(CE->getOperand(0)))
2345     return false;
2346   ConstantPointerRef *CPR = cast<ConstantPointerRef>(CE->getOperand(0));
2347   if (!isa<Function>(CPR->getValue())) return false;
2348   Function *Callee = cast<Function>(CPR->getValue());
2349   Instruction *Caller = CS.getInstruction();
2350
2351   // Okay, this is a cast from a function to a different type.  Unless doing so
2352   // would cause a type conversion of one of our arguments, change this call to
2353   // be a direct call with arguments casted to the appropriate types.
2354   //
2355   const FunctionType *FT = Callee->getFunctionType();
2356   const Type *OldRetTy = Caller->getType();
2357
2358   // Check to see if we are changing the return type...
2359   if (OldRetTy != FT->getReturnType()) {
2360     if (Callee->isExternal() &&
2361         !OldRetTy->isLosslesslyConvertibleTo(FT->getReturnType()) &&
2362         !Caller->use_empty())
2363       return false;   // Cannot transform this return value...
2364
2365     // If the callsite is an invoke instruction, and the return value is used by
2366     // a PHI node in a successor, we cannot change the return type of the call
2367     // because there is no place to put the cast instruction (without breaking
2368     // the critical edge).  Bail out in this case.
2369     if (!Caller->use_empty())
2370       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller))
2371         for (Value::use_iterator UI = II->use_begin(), E = II->use_end();
2372              UI != E; ++UI)
2373           if (PHINode *PN = dyn_cast<PHINode>(*UI))
2374             if (PN->getParent() == II->getNormalDest() ||
2375                 PN->getParent() == II->getUnwindDest())
2376               return false;
2377   }
2378
2379   unsigned NumActualArgs = unsigned(CS.arg_end()-CS.arg_begin());
2380   unsigned NumCommonArgs = std::min(FT->getNumParams(), NumActualArgs);
2381
2382   CallSite::arg_iterator AI = CS.arg_begin();
2383   for (unsigned i = 0, e = NumCommonArgs; i != e; ++i, ++AI) {
2384     const Type *ParamTy = FT->getParamType(i);
2385     bool isConvertible = (*AI)->getType()->isLosslesslyConvertibleTo(ParamTy);
2386     if (Callee->isExternal() && !isConvertible) return false;
2387   }
2388
2389   if (FT->getNumParams() < NumActualArgs && !FT->isVarArg() &&
2390       Callee->isExternal())
2391     return false;   // Do not delete arguments unless we have a function body...
2392
2393   // Okay, we decided that this is a safe thing to do: go ahead and start
2394   // inserting cast instructions as necessary...
2395   std::vector<Value*> Args;
2396   Args.reserve(NumActualArgs);
2397
2398   AI = CS.arg_begin();
2399   for (unsigned i = 0; i != NumCommonArgs; ++i, ++AI) {
2400     const Type *ParamTy = FT->getParamType(i);
2401     if ((*AI)->getType() == ParamTy) {
2402       Args.push_back(*AI);
2403     } else {
2404       Args.push_back(InsertNewInstBefore(new CastInst(*AI, ParamTy, "tmp"),
2405                                          *Caller));
2406     }
2407   }
2408
2409   // If the function takes more arguments than the call was taking, add them
2410   // now...
2411   for (unsigned i = NumCommonArgs; i != FT->getNumParams(); ++i)
2412     Args.push_back(Constant::getNullValue(FT->getParamType(i)));
2413
2414   // If we are removing arguments to the function, emit an obnoxious warning...
2415   if (FT->getNumParams() < NumActualArgs)
2416     if (!FT->isVarArg()) {
2417       std::cerr << "WARNING: While resolving call to function '"
2418                 << Callee->getName() << "' arguments were dropped!\n";
2419     } else {
2420       // Add all of the arguments in their promoted form to the arg list...
2421       for (unsigned i = FT->getNumParams(); i != NumActualArgs; ++i, ++AI) {
2422         const Type *PTy = getPromotedType((*AI)->getType());
2423         if (PTy != (*AI)->getType()) {
2424           // Must promote to pass through va_arg area!
2425           Instruction *Cast = new CastInst(*AI, PTy, "tmp");
2426           InsertNewInstBefore(Cast, *Caller);
2427           Args.push_back(Cast);
2428         } else {
2429           Args.push_back(*AI);
2430         }
2431       }
2432     }
2433
2434   if (FT->getReturnType() == Type::VoidTy)
2435     Caller->setName("");   // Void type should not have a name...
2436
2437   Instruction *NC;
2438   if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
2439     NC = new InvokeInst(Callee, II->getNormalDest(), II->getUnwindDest(),
2440                         Args, Caller->getName(), Caller);
2441   } else {
2442     NC = new CallInst(Callee, Args, Caller->getName(), Caller);
2443   }
2444
2445   // Insert a cast of the return type as necessary...
2446   Value *NV = NC;
2447   if (Caller->getType() != NV->getType() && !Caller->use_empty()) {
2448     if (NV->getType() != Type::VoidTy) {
2449       NV = NC = new CastInst(NC, Caller->getType(), "tmp");
2450
2451       // If this is an invoke instruction, we should insert it after the first
2452       // non-phi, instruction in the normal successor block.
2453       if (InvokeInst *II = dyn_cast<InvokeInst>(Caller)) {
2454         BasicBlock::iterator I = II->getNormalDest()->begin();
2455         while (isa<PHINode>(I)) ++I;
2456         InsertNewInstBefore(NC, *I);
2457       } else {
2458         // Otherwise, it's a call, just insert cast right after the call instr
2459         InsertNewInstBefore(NC, *Caller);
2460       }
2461       AddUsersToWorkList(*Caller);
2462     } else {
2463       NV = Constant::getNullValue(Caller->getType());
2464     }
2465   }
2466
2467   if (Caller->getType() != Type::VoidTy && !Caller->use_empty())
2468     Caller->replaceAllUsesWith(NV);
2469   Caller->getParent()->getInstList().erase(Caller);
2470   removeFromWorkList(Caller);
2471   return true;
2472 }
2473
2474
2475
2476 // PHINode simplification
2477 //
2478 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
2479   if (Value *V = hasConstantValue(&PN))
2480     return ReplaceInstUsesWith(PN, V);
2481
2482   // If the only user of this instruction is a cast instruction, and all of the
2483   // incoming values are constants, change this PHI to merge together the casted
2484   // constants.
2485   if (PN.hasOneUse())
2486     if (CastInst *CI = dyn_cast<CastInst>(PN.use_back()))
2487       if (CI->getType() != PN.getType()) {  // noop casts will be folded
2488         bool AllConstant = true;
2489         for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
2490           if (!isa<Constant>(PN.getIncomingValue(i))) {
2491             AllConstant = false;
2492             break;
2493           }
2494         if (AllConstant) {
2495           // Make a new PHI with all casted values.
2496           PHINode *New = new PHINode(CI->getType(), PN.getName(), &PN);
2497           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i) {
2498             Constant *OldArg = cast<Constant>(PN.getIncomingValue(i));
2499             New->addIncoming(ConstantExpr::getCast(OldArg, New->getType()),
2500                              PN.getIncomingBlock(i));
2501           }
2502
2503           // Update the cast instruction.
2504           CI->setOperand(0, New);
2505           WorkList.push_back(CI);    // revisit the cast instruction to fold.
2506           WorkList.push_back(New);   // Make sure to revisit the new Phi
2507           return &PN;                // PN is now dead!
2508         }
2509       }
2510   return 0;
2511 }
2512
2513 static Value *InsertSignExtendToPtrTy(Value *V, const Type *DTy,
2514                                       Instruction *InsertPoint,
2515                                       InstCombiner *IC) {
2516   unsigned PS = IC->getTargetData().getPointerSize();
2517   const Type *VTy = V->getType();
2518   Instruction *Cast;
2519   if (!VTy->isSigned() && VTy->getPrimitiveSize() < PS)
2520     // We must insert a cast to ensure we sign-extend.
2521     V = IC->InsertNewInstBefore(new CastInst(V, VTy->getSignedVersion(),
2522                                              V->getName()), *InsertPoint);
2523   return IC->InsertNewInstBefore(new CastInst(V, DTy, V->getName()),
2524                                  *InsertPoint);
2525 }
2526
2527
2528 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
2529   // Is it 'getelementptr %P, long 0'  or 'getelementptr %P'
2530   // If so, eliminate the noop.
2531   if (GEP.getNumOperands() == 1)
2532     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
2533
2534   bool HasZeroPointerIndex = false;
2535   if (Constant *C = dyn_cast<Constant>(GEP.getOperand(1)))
2536     HasZeroPointerIndex = C->isNullValue();
2537
2538   if (GEP.getNumOperands() == 2 && HasZeroPointerIndex)
2539     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
2540
2541   // Eliminate unneeded casts for indices.
2542   bool MadeChange = false;
2543   gep_type_iterator GTI = gep_type_begin(GEP);
2544   for (unsigned i = 1, e = GEP.getNumOperands(); i != e; ++i, ++GTI)
2545     if (isa<SequentialType>(*GTI)) {
2546       if (CastInst *CI = dyn_cast<CastInst>(GEP.getOperand(i))) {
2547         Value *Src = CI->getOperand(0);
2548         const Type *SrcTy = Src->getType();
2549         const Type *DestTy = CI->getType();
2550         if (Src->getType()->isInteger()) {
2551           if (SrcTy->getPrimitiveSize() == DestTy->getPrimitiveSize()) {
2552             // We can always eliminate a cast from ulong or long to the other.
2553             // We can always eliminate a cast from uint to int or the other on
2554             // 32-bit pointer platforms.
2555             if (DestTy->getPrimitiveSize() >= TD->getPointerSize()) {
2556               MadeChange = true;
2557               GEP.setOperand(i, Src);
2558             }
2559           } else if (SrcTy->getPrimitiveSize() < DestTy->getPrimitiveSize() &&
2560                      SrcTy->getPrimitiveSize() == 4) {
2561             // We can always eliminate a cast from int to [u]long.  We can
2562             // eliminate a cast from uint to [u]long iff the target is a 32-bit
2563             // pointer target.
2564             if (SrcTy->isSigned() ||
2565                 SrcTy->getPrimitiveSize() >= TD->getPointerSize()) {
2566               MadeChange = true;
2567               GEP.setOperand(i, Src);
2568             }
2569           }
2570         }
2571       }
2572       // If we are using a wider index than needed for this platform, shrink it
2573       // to what we need.  If the incoming value needs a cast instruction,
2574       // insert it.  This explicit cast can make subsequent optimizations more
2575       // obvious.
2576       Value *Op = GEP.getOperand(i);
2577       if (Op->getType()->getPrimitiveSize() > TD->getPointerSize())
2578         if (!isa<Constant>(Op)) {
2579           Op = InsertNewInstBefore(new CastInst(Op, TD->getIntPtrType(),
2580                                                 Op->getName()), GEP);
2581           GEP.setOperand(i, Op);
2582           MadeChange = true;
2583         }
2584     }
2585   if (MadeChange) return &GEP;
2586
2587   // Combine Indices - If the source pointer to this getelementptr instruction
2588   // is a getelementptr instruction, combine the indices of the two
2589   // getelementptr instructions into a single instruction.
2590   //
2591   std::vector<Value*> SrcGEPOperands;
2592   if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
2593     SrcGEPOperands.assign(Src->op_begin(), Src->op_end());
2594   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP.getOperand(0))) {
2595     if (CE->getOpcode() == Instruction::GetElementPtr)
2596       SrcGEPOperands.assign(CE->op_begin(), CE->op_end());
2597   }
2598
2599   if (!SrcGEPOperands.empty()) {
2600     std::vector<Value *> Indices;
2601
2602     // Can we combine the two pointer arithmetics offsets?
2603     if (SrcGEPOperands.size() == 2 && isa<Constant>(SrcGEPOperands[1]) &&
2604         isa<Constant>(GEP.getOperand(1))) {
2605       Constant *SGC = cast<Constant>(SrcGEPOperands[1]);
2606       Constant *GC  = cast<Constant>(GEP.getOperand(1));
2607       if (SGC->getType() != GC->getType()) {
2608         SGC = ConstantExpr::getSignExtend(SGC, Type::LongTy);
2609         GC = ConstantExpr::getSignExtend(GC, Type::LongTy);
2610       }
2611
2612       // Replace: gep (gep %P, long C1), long C2, ...
2613       // With:    gep %P, long (C1+C2), ...
2614       GEP.setOperand(0, SrcGEPOperands[0]);
2615       GEP.setOperand(1, ConstantExpr::getAdd(SGC, GC));
2616       if (Instruction *I = dyn_cast<Instruction>(GEP.getOperand(0)))
2617         AddUsersToWorkList(*I);   // Reduce use count of Src
2618       return &GEP;
2619     } else if (SrcGEPOperands.size() == 2) {
2620       // Replace: gep (gep %P, long B), long A, ...
2621       // With:    T = long A+B; gep %P, T, ...
2622       //
2623       // Note that if our source is a gep chain itself that we wait for that
2624       // chain to be resolved before we perform this transformation.  This
2625       // avoids us creating a TON of code in some cases.
2626       //
2627       if (isa<GetElementPtrInst>(SrcGEPOperands[0]) &&
2628           cast<Instruction>(SrcGEPOperands[0])->getNumOperands() == 2)
2629         return 0;   // Wait until our source is folded to completion.
2630
2631       Value *Sum, *SO1 = SrcGEPOperands[1], *GO1 = GEP.getOperand(1);
2632       if (SO1 == Constant::getNullValue(SO1->getType())) {
2633         Sum = GO1;
2634       } else if (GO1 == Constant::getNullValue(GO1->getType())) {
2635         Sum = SO1;
2636       } else {
2637         // If they aren't the same type, convert both to an integer of the
2638         // target's pointer size.
2639         if (SO1->getType() != GO1->getType()) {
2640           if (Constant *SO1C = dyn_cast<Constant>(SO1)) {
2641             SO1 = ConstantExpr::getCast(SO1C, GO1->getType());
2642           } else if (Constant *GO1C = dyn_cast<Constant>(GO1)) {
2643             GO1 = ConstantExpr::getCast(GO1C, SO1->getType());
2644           } else {
2645             unsigned PS = TD->getPointerSize();
2646             Instruction *Cast;
2647             if (SO1->getType()->getPrimitiveSize() == PS) {
2648               // Convert GO1 to SO1's type.
2649               GO1 = InsertSignExtendToPtrTy(GO1, SO1->getType(), &GEP, this);
2650
2651             } else if (GO1->getType()->getPrimitiveSize() == PS) {
2652               // Convert SO1 to GO1's type.
2653               SO1 = InsertSignExtendToPtrTy(SO1, GO1->getType(), &GEP, this);
2654             } else {
2655               const Type *PT = TD->getIntPtrType();
2656               SO1 = InsertSignExtendToPtrTy(SO1, PT, &GEP, this);
2657               GO1 = InsertSignExtendToPtrTy(GO1, PT, &GEP, this);
2658             }
2659           }
2660         }
2661         Sum = BinaryOperator::create(Instruction::Add, SO1, GO1,
2662                                      GEP.getOperand(0)->getName()+".sum", &GEP);
2663         WorkList.push_back(cast<Instruction>(Sum));
2664       }
2665       GEP.setOperand(0, SrcGEPOperands[0]);
2666       GEP.setOperand(1, Sum);
2667       return &GEP;
2668     } else if (isa<Constant>(*GEP.idx_begin()) &&
2669                cast<Constant>(*GEP.idx_begin())->isNullValue() &&
2670                SrcGEPOperands.size() != 1) {
2671       // Otherwise we can do the fold if the first index of the GEP is a zero
2672       Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
2673                      SrcGEPOperands.end());
2674       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
2675     } else if (SrcGEPOperands.back() ==
2676                Constant::getNullValue(SrcGEPOperands.back()->getType())) {
2677       // We have to check to make sure this really is an ARRAY index we are
2678       // ending up with, not a struct index.
2679       generic_gep_type_iterator<std::vector<Value*>::iterator>
2680         GTI = gep_type_begin(SrcGEPOperands[0]->getType(),
2681                              SrcGEPOperands.begin()+1, SrcGEPOperands.end());
2682       std::advance(GTI, SrcGEPOperands.size()-2);
2683       if (isa<SequentialType>(*GTI)) {
2684         // If the src gep ends with a constant array index, merge this get into
2685         // it, even if we have a non-zero array index.
2686         Indices.insert(Indices.end(), SrcGEPOperands.begin()+1,
2687                        SrcGEPOperands.end()-1);
2688         Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
2689       }
2690     }
2691
2692     if (!Indices.empty())
2693       return new GetElementPtrInst(SrcGEPOperands[0], Indices, GEP.getName());
2694
2695   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
2696     // GEP of global variable.  If all of the indices for this GEP are
2697     // constants, we can promote this to a constexpr instead of an instruction.
2698
2699     // Scan for nonconstants...
2700     std::vector<Constant*> Indices;
2701     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
2702     for (; I != E && isa<Constant>(*I); ++I)
2703       Indices.push_back(cast<Constant>(*I));
2704
2705     if (I == E) {  // If they are all constants...
2706       Constant *CE =
2707         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
2708
2709       // Replace all uses of the GEP with the new constexpr...
2710       return ReplaceInstUsesWith(GEP, CE);
2711     }
2712   } else if (ConstantExpr *CE = dyn_cast<ConstantExpr>(GEP.getOperand(0))) {
2713     if (CE->getOpcode() == Instruction::Cast) {
2714       if (HasZeroPointerIndex) {
2715         // transform: GEP (cast [10 x ubyte]* X to [0 x ubyte]*), long 0, ...
2716         // into     : GEP [10 x ubyte]* X, long 0, ...
2717         //
2718         // This occurs when the program declares an array extern like "int X[];"
2719         //
2720         Constant *X = CE->getOperand(0);
2721         const PointerType *CPTy = cast<PointerType>(CE->getType());
2722         if (const PointerType *XTy = dyn_cast<PointerType>(X->getType()))
2723           if (const ArrayType *XATy =
2724               dyn_cast<ArrayType>(XTy->getElementType()))
2725             if (const ArrayType *CATy =
2726                 dyn_cast<ArrayType>(CPTy->getElementType()))
2727               if (CATy->getElementType() == XATy->getElementType()) {
2728                 // At this point, we know that the cast source type is a pointer
2729                 // to an array of the same type as the destination pointer
2730                 // array.  Because the array type is never stepped over (there
2731                 // is a leading zero) we can fold the cast into this GEP.
2732                 GEP.setOperand(0, X);
2733                 return &GEP;
2734               }
2735       }
2736     }
2737   }
2738
2739   return 0;
2740 }
2741
2742 Instruction *InstCombiner::visitAllocationInst(AllocationInst &AI) {
2743   // Convert: malloc Ty, C - where C is a constant != 1 into: malloc [C x Ty], 1
2744   if (AI.isArrayAllocation())    // Check C != 1
2745     if (const ConstantUInt *C = dyn_cast<ConstantUInt>(AI.getArraySize())) {
2746       const Type *NewTy = ArrayType::get(AI.getAllocatedType(), C->getValue());
2747       AllocationInst *New = 0;
2748
2749       // Create and insert the replacement instruction...
2750       if (isa<MallocInst>(AI))
2751         New = new MallocInst(NewTy, 0, AI.getName());
2752       else {
2753         assert(isa<AllocaInst>(AI) && "Unknown type of allocation inst!");
2754         New = new AllocaInst(NewTy, 0, AI.getName());
2755       }
2756
2757       InsertNewInstBefore(New, AI);
2758
2759       // Scan to the end of the allocation instructions, to skip over a block of
2760       // allocas if possible...
2761       //
2762       BasicBlock::iterator It = New;
2763       while (isa<AllocationInst>(*It)) ++It;
2764
2765       // Now that I is pointing to the first non-allocation-inst in the block,
2766       // insert our getelementptr instruction...
2767       //
2768       std::vector<Value*> Idx(2, Constant::getNullValue(Type::IntTy));
2769       Value *V = new GetElementPtrInst(New, Idx, New->getName()+".sub", It);
2770
2771       // Now make everything use the getelementptr instead of the original
2772       // allocation.
2773       return ReplaceInstUsesWith(AI, V);
2774     }
2775
2776   // If alloca'ing a zero byte object, replace the alloca with a null pointer.
2777   // Note that we only do this for alloca's, because malloc should allocate and
2778   // return a unique pointer, even for a zero byte allocation.
2779   if (isa<AllocaInst>(AI) && TD->getTypeSize(AI.getAllocatedType()) == 0)
2780     return ReplaceInstUsesWith(AI, Constant::getNullValue(AI.getType()));
2781
2782   return 0;
2783 }
2784
2785 Instruction *InstCombiner::visitFreeInst(FreeInst &FI) {
2786   Value *Op = FI.getOperand(0);
2787
2788   // Change free <ty>* (cast <ty2>* X to <ty>*) into free <ty2>* X
2789   if (CastInst *CI = dyn_cast<CastInst>(Op))
2790     if (isa<PointerType>(CI->getOperand(0)->getType())) {
2791       FI.setOperand(0, CI->getOperand(0));
2792       return &FI;
2793     }
2794
2795   // If we have 'free null' delete the instruction.  This can happen in stl code
2796   // when lots of inlining happens.
2797   if (isa<ConstantPointerNull>(Op))
2798     return EraseInstFromFunction(FI);
2799
2800   return 0;
2801 }
2802
2803
2804 /// GetGEPGlobalInitializer - Given a constant, and a getelementptr
2805 /// constantexpr, return the constant value being addressed by the constant
2806 /// expression, or null if something is funny.
2807 ///
2808 static Constant *GetGEPGlobalInitializer(Constant *C, ConstantExpr *CE) {
2809   if (CE->getOperand(1) != Constant::getNullValue(CE->getOperand(1)->getType()))
2810     return 0;  // Do not allow stepping over the value!
2811
2812   // Loop over all of the operands, tracking down which value we are
2813   // addressing...
2814   for (unsigned i = 2, e = CE->getNumOperands(); i != e; ++i)
2815     if (ConstantUInt *CU = dyn_cast<ConstantUInt>(CE->getOperand(i))) {
2816       ConstantStruct *CS = dyn_cast<ConstantStruct>(C);
2817       if (CS == 0) return 0;
2818       if (CU->getValue() >= CS->getValues().size()) return 0;
2819       C = cast<Constant>(CS->getValues()[CU->getValue()]);
2820     } else if (ConstantSInt *CS = dyn_cast<ConstantSInt>(CE->getOperand(i))) {
2821       ConstantArray *CA = dyn_cast<ConstantArray>(C);
2822       if (CA == 0) return 0;
2823       if ((uint64_t)CS->getValue() >= CA->getValues().size()) return 0;
2824       C = cast<Constant>(CA->getValues()[CS->getValue()]);
2825     } else
2826       return 0;
2827   return C;
2828 }
2829
2830 Instruction *InstCombiner::visitLoadInst(LoadInst &LI) {
2831   Value *Op = LI.getOperand(0);
2832   if (LI.isVolatile()) return 0;
2833
2834   if (ConstantPointerRef *CPR = dyn_cast<ConstantPointerRef>(Op))
2835     Op = CPR->getValue();
2836
2837   // Instcombine load (constant global) into the value loaded...
2838   if (GlobalVariable *GV = dyn_cast<GlobalVariable>(Op))
2839     if (GV->isConstant() && !GV->isExternal())
2840       return ReplaceInstUsesWith(LI, GV->getInitializer());
2841
2842   // Instcombine load (constantexpr_GEP global, 0, ...) into the value loaded...
2843   if (ConstantExpr *CE = dyn_cast<ConstantExpr>(Op))
2844     if (CE->getOpcode() == Instruction::GetElementPtr)
2845       if (ConstantPointerRef *G=dyn_cast<ConstantPointerRef>(CE->getOperand(0)))
2846         if (GlobalVariable *GV = dyn_cast<GlobalVariable>(G->getValue()))
2847           if (GV->isConstant() && !GV->isExternal())
2848             if (Constant *V = GetGEPGlobalInitializer(GV->getInitializer(), CE))
2849               return ReplaceInstUsesWith(LI, V);
2850
2851   // load (cast X) --> cast (load X) iff safe
2852   if (CastInst *CI = dyn_cast<CastInst>(Op)) {
2853     const Type *DestPTy = cast<PointerType>(CI->getType())->getElementType();
2854     if (const PointerType *SrcTy =
2855         dyn_cast<PointerType>(CI->getOperand(0)->getType())) {
2856       const Type *SrcPTy = SrcTy->getElementType();
2857       if (TD->getTypeSize(SrcPTy) == TD->getTypeSize(DestPTy) &&
2858           (SrcPTy->isInteger() || isa<PointerType>(SrcPTy)) &&
2859           (DestPTy->isInteger() || isa<PointerType>(DestPTy))) {
2860         // Okay, we are casting from one integer or pointer type to another of
2861         // the same size.  Instead of casting the pointer before the load, cast
2862         // the result of the loaded value.
2863         Value *NewLoad = InsertNewInstBefore(new LoadInst(CI->getOperand(0),
2864                                                           CI->getName()), LI);
2865         // Now cast the result of the load.
2866         return new CastInst(NewLoad, LI.getType());
2867       }
2868     }
2869   }
2870
2871   return 0;
2872 }
2873
2874
2875 Instruction *InstCombiner::visitBranchInst(BranchInst &BI) {
2876   // Change br (not X), label True, label False to: br X, label False, True
2877   if (BI.isConditional() && !isa<Constant>(BI.getCondition())) {
2878     if (Value *V = dyn_castNotVal(BI.getCondition())) {
2879       BasicBlock *TrueDest = BI.getSuccessor(0);
2880       BasicBlock *FalseDest = BI.getSuccessor(1);
2881       // Swap Destinations and condition...
2882       BI.setCondition(V);
2883       BI.setSuccessor(0, FalseDest);
2884       BI.setSuccessor(1, TrueDest);
2885       return &BI;
2886     } else if (SetCondInst *I = dyn_cast<SetCondInst>(BI.getCondition())) {
2887       // Cannonicalize setne -> seteq
2888       if ((I->getOpcode() == Instruction::SetNE ||
2889            I->getOpcode() == Instruction::SetLE ||
2890            I->getOpcode() == Instruction::SetGE) && I->hasOneUse()) {
2891         std::string Name = I->getName(); I->setName("");
2892         Instruction::BinaryOps NewOpcode =
2893           SetCondInst::getInverseCondition(I->getOpcode());
2894         Value *NewSCC =  BinaryOperator::create(NewOpcode, I->getOperand(0),
2895                                                 I->getOperand(1), Name, I);
2896         BasicBlock *TrueDest = BI.getSuccessor(0);
2897         BasicBlock *FalseDest = BI.getSuccessor(1);
2898         // Swap Destinations and condition...
2899         BI.setCondition(NewSCC);
2900         BI.setSuccessor(0, FalseDest);
2901         BI.setSuccessor(1, TrueDest);
2902         removeFromWorkList(I);
2903         I->getParent()->getInstList().erase(I);
2904         WorkList.push_back(cast<Instruction>(NewSCC));
2905         return &BI;
2906       }
2907     }
2908   }
2909   return 0;
2910 }
2911
2912
2913 void InstCombiner::removeFromWorkList(Instruction *I) {
2914   WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
2915                  WorkList.end());
2916 }
2917
2918 bool InstCombiner::runOnFunction(Function &F) {
2919   bool Changed = false;
2920   TD = &getAnalysis<TargetData>();
2921
2922   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
2923
2924   while (!WorkList.empty()) {
2925     Instruction *I = WorkList.back();  // Get an instruction from the worklist
2926     WorkList.pop_back();
2927
2928     // Check to see if we can DCE or ConstantPropagate the instruction...
2929     // Check to see if we can DIE the instruction...
2930     if (isInstructionTriviallyDead(I)) {
2931       // Add operands to the worklist...
2932       if (I->getNumOperands() < 4)
2933         AddUsesToWorkList(*I);
2934       ++NumDeadInst;
2935
2936       I->getParent()->getInstList().erase(I);
2937       removeFromWorkList(I);
2938       continue;
2939     }
2940
2941     // Instruction isn't dead, see if we can constant propagate it...
2942     if (Constant *C = ConstantFoldInstruction(I)) {
2943       // Add operands to the worklist...
2944       AddUsesToWorkList(*I);
2945       ReplaceInstUsesWith(*I, C);
2946
2947       ++NumConstProp;
2948       I->getParent()->getInstList().erase(I);
2949       removeFromWorkList(I);
2950       continue;
2951     }
2952
2953     // Check to see if any of the operands of this instruction are a
2954     // ConstantPointerRef.  Since they sneak in all over the place and inhibit
2955     // optimization, we want to strip them out unconditionally!
2956     for (unsigned i = 0, e = I->getNumOperands(); i != e; ++i)
2957       if (ConstantPointerRef *CPR =
2958           dyn_cast<ConstantPointerRef>(I->getOperand(i))) {
2959         I->setOperand(i, CPR->getValue());
2960         Changed = true;
2961       }
2962
2963     // Now that we have an instruction, try combining it to simplify it...
2964     if (Instruction *Result = visit(*I)) {
2965       ++NumCombined;
2966       // Should we replace the old instruction with a new one?
2967       if (Result != I) {
2968         DEBUG(std::cerr << "IC: Old = " << *I
2969                         << "    New = " << *Result);
2970
2971         // Instructions can end up on the worklist more than once.  Make sure
2972         // we do not process an instruction that has been deleted.
2973         removeFromWorkList(I);
2974
2975         // Move the name to the new instruction first...
2976         std::string OldName = I->getName(); I->setName("");
2977         Result->setName(OldName);
2978
2979         // Insert the new instruction into the basic block...
2980         BasicBlock *InstParent = I->getParent();
2981         InstParent->getInstList().insert(I, Result);
2982
2983         // Everything uses the new instruction now...
2984         I->replaceAllUsesWith(Result);
2985
2986         // Erase the old instruction.
2987         InstParent->getInstList().erase(I);
2988       } else {
2989         DEBUG(std::cerr << "IC: MOD = " << *I);
2990
2991         BasicBlock::iterator II = I;
2992
2993         // If the instruction was modified, it's possible that it is now dead.
2994         // if so, remove it.
2995         if (dceInstruction(II)) {
2996           // Instructions may end up in the worklist more than once.  Erase them
2997           // all.
2998           removeFromWorkList(I);
2999           Result = 0;
3000         }
3001       }
3002
3003       if (Result) {
3004         WorkList.push_back(Result);
3005         AddUsersToWorkList(*Result);
3006       }
3007       Changed = true;
3008     }
3009   }
3010
3011   return Changed;
3012 }
3013
3014 Pass *llvm::createInstructionCombiningPass() {
3015   return new InstCombiner();
3016 }
3017