lib/Transforms/Scalar/InstructionCombining.cpp

   1 //===- InstructionCombining.cpp - Combine multiple instructions -----------===//
   2 //
   3 // InstructionCombining - Combine instructions to form fewer, simple
   4 //   instructions.  This pass does not modify the CFG, and has a tendancy to
   5 //   make instructions dead, so a subsequent DIE pass is useful.  This pass is
   6 //   where algebraic simplification happens.
   7 //
   8 // This pass combines things like:
   9 //    %Y = add int 1, %X
  10 //    %Z = add int 1, %Y
  11 // into:
  12 //    %Z = add int 2, %X
  13 //
  14 // This is a simple worklist driven algorithm.
  15 //
  16 //===----------------------------------------------------------------------===//
  17
  18 #include "llvm/Transforms/Scalar.h"
  19 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  20 #include "llvm/Transforms/Utils/Local.h"
  21 #include "llvm/ConstantHandling.h"
  22 #include "llvm/iMemory.h"
  23 #include "llvm/iOther.h"
  24 #include "llvm/iPHINode.h"
  25 #include "llvm/iOperators.h"
  26 #include "llvm/Pass.h"
  27 #include "llvm/Support/InstIterator.h"
  28 #include "llvm/Support/InstVisitor.h"
  29 #include "Support/StatisticReporter.h"
  30 #include <algorithm>
  31
  32 static Statistic<> NumCombined("instcombine\t- Number of insts combined");
  33
  34 namespace {
  35   class InstCombiner : public FunctionPass,
  36                        public InstVisitor<InstCombiner, Instruction*> {
  37     // Worklist of all of the instructions that need to be simplified.
  38     std::vector<Instruction*> WorkList;
  39
  40     void AddUsesToWorkList(Instruction &I) {
  41       // The instruction was simplified, add all users of the instruction to
  42       // the work lists because they might get more simplified now...
  43       //
  44       for (Value::use_iterator UI = I.use_begin(), UE = I.use_end();
  45            UI != UE; ++UI)
  46         WorkList.push_back(cast<Instruction>(*UI));
  47     }
  48
  49   public:
  50     virtual bool runOnFunction(Function &F);
  51
  52     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
  53       AU.preservesCFG();
  54     }
  55
  56     // Visitation implementation - Implement instruction combining for different
  57     // instruction types.  The semantics are as follows:
  58     // Return Value:
  59     //    null        - No change was made
  60     //     I          - Change was made, I is still valid, I may be dead though
  61     //   otherwise    - Change was made, replace I with returned instruction
  62     //
  63     Instruction *visitNot(UnaryOperator &I);
  64     Instruction *visitAdd(BinaryOperator &I);
  65     Instruction *visitSub(BinaryOperator &I);
  66     Instruction *visitMul(BinaryOperator &I);
  67     Instruction *visitDiv(BinaryOperator &I);
  68     Instruction *visitRem(BinaryOperator &I);
  69     Instruction *visitAnd(BinaryOperator &I);
  70     Instruction *visitOr (BinaryOperator &I);
  71     Instruction *visitXor(BinaryOperator &I);
  72     Instruction *visitSetCondInst(BinaryOperator &I);
  73     Instruction *visitShiftInst(Instruction &I);
  74     Instruction *visitCastInst(CastInst &CI);
  75     Instruction *visitPHINode(PHINode &PN);
  76     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
  77
  78     // visitInstruction - Specify what to return for unhandled instructions...
  79     Instruction *visitInstruction(Instruction &I) { return 0; }
  80
  81     // InsertNewInstBefore - insert an instruction New before instruction Old
  82     // in the program.  Add the new instruction to the worklist.
  83     //
  84     void InsertNewInstBefore(Instruction *New, Instruction &Old) {
  85       BasicBlock *BB = Old.getParent();
  86       BB->getInstList().insert(&Old, New);  // Insert inst
  87       WorkList.push_back(New);              // Add to worklist
  88     }
  89
  90     // ReplaceInstUsesWith - This method is to be used when an instruction is
  91     // found to be dead, replacable with another preexisting expression.  Here
  92     // we add all uses of I to the worklist, replace all uses of I with the new
  93     // value, then return I, so that the inst combiner will know that I was
  94     // modified.
  95     //
  96     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
  97       AddUsesToWorkList(I);         // Add all modified instrs to worklist
  98       I.replaceAllUsesWith(V);
  99       return &I;
 100     }
 101   };
 102
 103   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
 104 }
 105
 106
 107 Instruction *InstCombiner::visitNot(UnaryOperator &I) {
 108   // not (not X) = X
 109   if (Instruction *Op = dyn_cast<Instruction>(I.getOperand(0)))
 110     if (Op->getOpcode() == Instruction::Not)
 111       return ReplaceInstUsesWith(I, Op->getOperand(0));
 112   return 0;
 113 }
 114
 115
 116 // Make sure that this instruction has a constant on the right hand side if it
 117 // has any constant arguments.  If not, fix it an return true.
 118 //
 119 static bool SimplifyBinOp(BinaryOperator &I) {
 120   if (isa<Constant>(I.getOperand(0)) && !isa<Constant>(I.getOperand(1)))
 121     return !I.swapOperands();
 122   return false;
 123 }
 124
 125 // dyn_castNegInst - Given a 'sub' instruction, return the RHS of the
 126 // instruction if the LHS is a constant zero (which is the 'negate' form).
 127 //
 128 static inline Value *dyn_castNegInst(Value *V) {
 129   Instruction *I = dyn_cast<Instruction>(V);
 130   if (!I || I->getOpcode() != Instruction::Sub) return 0;
 131
 132   if (I->getOperand(0) == Constant::getNullValue(I->getType()))
 133     return I->getOperand(1);
 134   return 0;
 135 }
 136
 137 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 138   bool Changed = SimplifyBinOp(I);
 139   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 140
 141   // Eliminate 'add int %X, 0'
 142   if (RHS == Constant::getNullValue(I.getType()))
 143     return ReplaceInstUsesWith(I, LHS);
 144
 145   // -A + B  -->  B - A
 146   if (Value *V = dyn_castNegInst(LHS))
 147     return BinaryOperator::create(Instruction::Sub, RHS, V);
 148
 149   // A + -B  -->  A - B
 150   if (Value *V = dyn_castNegInst(RHS))
 151     return BinaryOperator::create(Instruction::Sub, LHS, V);
 152
 153   // Simplify add instructions with a constant RHS...
 154   if (Constant *Op2 = dyn_cast<Constant>(RHS)) {
 155     if (BinaryOperator *ILHS = dyn_cast<BinaryOperator>(LHS)) {
 156       if (ILHS->getOpcode() == Instruction::Add &&
 157           isa<Constant>(ILHS->getOperand(1))) {
 158         // Fold:
 159         //    %Y = add int %X, 1
 160         //    %Z = add int %Y, 1
 161         // into:
 162         //    %Z = add int %X, 2
 163         //
 164         if (Constant *Val = *Op2 + *cast<Constant>(ILHS->getOperand(1))) {
 165           I.setOperand(0, ILHS->getOperand(0));
 166           I.setOperand(1, Val);
 167           return &I;
 168         }
 169       }
 170     }
 171   }
 172
 173   return Changed ? &I : 0;
 174 }
 175
 176 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 177   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 178
 179   if (Op0 == Op1)         // sub X, X  -> 0
 180     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 181
 182   // If this is a subtract instruction with a constant RHS, convert it to an add
 183   // instruction of a negative constant
 184   //
 185   if (Constant *Op2 = dyn_cast<Constant>(Op1))
 186     if (Constant *RHS = *Constant::getNullValue(I.getType()) - *Op2) // 0 - RHS
 187       return BinaryOperator::create(Instruction::Add, Op0, RHS, I.getName());
 188
 189   // If this is a 'B = x-(-A)', change to B = x+A...
 190   if (Value *V = dyn_castNegInst(Op1))
 191     return BinaryOperator::create(Instruction::Add, Op0, V);
 192
 193   // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression is
 194   // not used by anyone else...
 195   //
 196   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
 197     if (Op1I->use_size() == 1 && Op1I->getOpcode() == Instruction::Sub) {
 198       // Swap the two operands of the subexpr...
 199       Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 200       Op1I->setOperand(0, IIOp1);
 201       Op1I->setOperand(1, IIOp0);
 202
 203       // Create the new top level add instruction...
 204       return BinaryOperator::create(Instruction::Add, Op0, Op1);
 205     }
 206   return 0;
 207 }
 208
 209 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 210   bool Changed = SimplifyBinOp(I);
 211   Value *Op1 = I.getOperand(0);
 212
 213   // Simplify mul instructions with a constant RHS...
 214   if (Constant *Op2 = dyn_cast<Constant>(I.getOperand(1))) {
 215     if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(1))
 216       return ReplaceInstUsesWith(I, Op1);  // Eliminate 'mul int %X, 1'
 217
 218     if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(2))
 219       // Convert 'mul int %X, 2' to 'add int %X, %X'
 220       return BinaryOperator::create(Instruction::Add, Op1, Op1, I.getName());
 221
 222     if (Op2->isNullValue())
 223       return ReplaceInstUsesWith(I, Op2);  // Eliminate 'mul int %X, 0'
 224   }
 225
 226   return Changed ? &I : 0;
 227 }
 228
 229
 230 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
 231   // div X, 1 == X
 232   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1)))
 233     if (RHS->equalsInt(1))
 234       return ReplaceInstUsesWith(I, I.getOperand(0));
 235   return 0;
 236 }
 237
 238
 239 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
 240   // rem X, 1 == 0
 241   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1)))
 242     if (RHS->equalsInt(1))
 243       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 244
 245   return 0;
 246 }
 247
 248 // isMaxValueMinusOne - return true if this is Max-1
 249 static bool isMaxValueMinusOne(const ConstantInt *C) {
 250   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
 251     // Calculate -1 casted to the right type...
 252     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 253     uint64_t Val = ~0ULL;                // All ones
 254     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 255     return CU->getValue() == Val-1;
 256   }
 257
 258   const ConstantSInt *CS = cast<ConstantSInt>(C);
 259
 260   // Calculate 0111111111..11111
 261   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 262   int64_t Val = INT64_MAX;             // All ones
 263   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 264   return CS->getValue() == Val-1;
 265 }
 266
 267 // isMinValuePlusOne - return true if this is Min+1
 268 static bool isMinValuePlusOne(const ConstantInt *C) {
 269   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
 270     return CU->getValue() == 1;
 271
 272   const ConstantSInt *CS = cast<ConstantSInt>(C);
 273
 274   // Calculate 1111111111000000000000
 275   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 276   int64_t Val = -1;                    // All ones
 277   Val <<= TypeBits-1;                  // Shift over to the right spot
 278   return CS->getValue() == Val+1;
 279 }
 280
 281
 282 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
 283   bool Changed = SimplifyBinOp(I);
 284   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 285
 286   // and X, X = X   and X, 0 == 0
 287   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 288     return ReplaceInstUsesWith(I, Op1);
 289
 290   // and X, -1 == X
 291   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1))
 292     if (RHS->isAllOnesValue())
 293       return ReplaceInstUsesWith(I, Op0);
 294
 295   return Changed ? &I : 0;
 296 }
 297
 298
 299
 300 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
 301   bool Changed = SimplifyBinOp(I);
 302   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 303
 304   // or X, X = X   or X, 0 == X
 305   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 306     return ReplaceInstUsesWith(I, Op0);
 307
 308   // or X, -1 == -1
 309   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1))
 310     if (RHS->isAllOnesValue())
 311       return ReplaceInstUsesWith(I, Op1);
 312
 313   return Changed ? &I : 0;
 314 }
 315
 316
 317
 318 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
 319   bool Changed = SimplifyBinOp(I);
 320   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 321
 322   // xor X, X = 0
 323   if (Op0 == Op1)
 324     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 325
 326   if (ConstantIntegral *Op1C = dyn_cast<ConstantIntegral>(Op1)) {
 327     // xor X, 0 == X
 328     if (Op1C->isNullValue())
 329       return ReplaceInstUsesWith(I, Op0);
 330
 331     // xor X, -1 = not X
 332     if (Op1C->isAllOnesValue())
 333       return UnaryOperator::create(Instruction::Not, Op0, I.getName());
 334   }
 335
 336   return Changed ? &I : 0;
 337 }
 338
 339 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
 340 static Constant *AddOne(ConstantInt *C) {
 341   Constant *Result = *C + *ConstantInt::get(C->getType(), 1);
 342   assert(Result && "Constant folding integer addition failed!");
 343   return Result;
 344 }
 345 static Constant *SubOne(ConstantInt *C) {
 346   Constant *Result = *C - *ConstantInt::get(C->getType(), 1);
 347   assert(Result && "Constant folding integer addition failed!");
 348   return Result;
 349 }
 350
 351 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
 352 // true when both operands are equal...
 353 //
 354 static bool isTrueWhenEqual(Instruction &I) {
 355   return I.getOpcode() == Instruction::SetEQ ||
 356          I.getOpcode() == Instruction::SetGE ||
 357          I.getOpcode() == Instruction::SetLE;
 358 }
 359
 360 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
 361   bool Changed = SimplifyBinOp(I);
 362   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 363   const Type *Ty = Op0->getType();
 364
 365   // setcc X, X
 366   if (Op0 == Op1)
 367     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
 368
 369   // setcc <global*>, 0 - Global value addresses are never null!
 370   if (isa<GlobalValue>(Op0) && isa<ConstantPointerNull>(Op1))
 371     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
 372
 373   // setcc's with boolean values can always be turned into bitwise operations
 374   if (Ty == Type::BoolTy) {
 375     // If this is <, >, or !=, we can change this into a simple xor instruction
 376     if (!isTrueWhenEqual(I))
 377       return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
 378
 379     // Otherwise we need to make a temporary intermediate instruction and insert
 380     // it into the instruction stream.  This is what we are after:
 381     //
 382     //  seteq bool %A, %B -> ~(A^B)
 383     //  setle bool %A, %B -> ~A | B
 384     //  setge bool %A, %B -> A | ~B
 385     //
 386     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
 387       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
 388                                                 I.getName()+"tmp");
 389       InsertNewInstBefore(Xor, I);
 390       return UnaryOperator::create(Instruction::Not, Xor, I.getName());
 391     }
 392
 393     // Handle the setXe cases...
 394     assert(I.getOpcode() == Instruction::SetGE ||
 395            I.getOpcode() == Instruction::SetLE);
 396
 397     if (I.getOpcode() == Instruction::SetGE)
 398       std::swap(Op0, Op1);                   // Change setge -> setle
 399
 400     // Now we just have the SetLE case.
 401     Instruction *Not =
 402       UnaryOperator::create(Instruction::Not, Op0, I.getName()+"tmp");
 403     InsertNewInstBefore(Not, I);
 404     return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
 405   }
 406
 407   // Check to see if we are doing one of many comparisons against constant
 408   // integers at the end of their ranges...
 409   //
 410   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 411     // Check to see if we are comparing against the minimum or maximum value...
 412     if (CI->isMinValue()) {
 413       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
 414         return ReplaceInstUsesWith(I, ConstantBool::False);
 415       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
 416         return ReplaceInstUsesWith(I, ConstantBool::True);
 417       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
 418         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 419       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
 420         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 421
 422     } else if (CI->isMaxValue()) {
 423       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
 424         return ReplaceInstUsesWith(I, ConstantBool::False);
 425       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
 426         return ReplaceInstUsesWith(I, ConstantBool::True);
 427       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
 428         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 429       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
 430         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 431
 432       // Comparing against a value really close to min or max?
 433     } else if (isMinValuePlusOne(CI)) {
 434       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
 435         return BinaryOperator::create(Instruction::SetEQ, Op0,
 436                                       SubOne(CI), I.getName());
 437       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
 438         return BinaryOperator::create(Instruction::SetNE, Op0,
 439                                       SubOne(CI), I.getName());
 440
 441     } else if (isMaxValueMinusOne(CI)) {
 442       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
 443         return BinaryOperator::create(Instruction::SetEQ, Op0,
 444                                       AddOne(CI), I.getName());
 445       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
 446         return BinaryOperator::create(Instruction::SetNE, Op0,
 447                                       AddOne(CI), I.getName());
 448     }
 449   }
 450
 451   return Changed ? &I : 0;
 452 }
 453
 454
 455
 456 Instruction *InstCombiner::visitShiftInst(Instruction &I) {
 457   assert(I.getOperand(1)->getType() == Type::UByteTy);
 458   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 459
 460   // shl X, 0 == X and shr X, 0 == X
 461   // shl 0, X == 0 and shr 0, X == 0
 462   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
 463       Op0 == Constant::getNullValue(Op0->getType()))
 464     return ReplaceInstUsesWith(I, Op0);
 465
 466   // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of
 467   // a signed value.
 468   //
 469   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
 470     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
 471     if (CUI->getValue() >= TypeBits &&
 472         !(Op0->getType()->isSigned() && I.getOpcode() == Instruction::Shr))
 473       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
 474   }
 475   return 0;
 476 }
 477
 478
 479 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
 480 // instruction.
 481 //
 482 static inline bool isEliminableCastOfCast(const CastInst &CI,
 483                                           const CastInst *CSrc) {
 484   assert(CI.getOperand(0) == CSrc);
 485   const Type *SrcTy = CSrc->getOperand(0)->getType();
 486   const Type *MidTy = CSrc->getType();
 487   const Type *DstTy = CI.getType();
 488
 489   // It is legal to eliminate the instruction if casting A->B->A if the sizes
 490   // are identical and the bits don't get reinterpreted (for example
 491   // int->float->int)
 492   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy))
 493     return true;
 494
 495   // Allow free casting and conversion of sizes as long as the sign doesn't
 496   // change...
 497   if (SrcTy->isIntegral() && MidTy->isIntegral() && DstTy->isIntegral() &&
 498       SrcTy->isSigned() == MidTy->isSigned() &&
 499       MidTy->isSigned() == DstTy->isSigned()) {
 500     // Only accept cases where we are either monotonically increasing the type
 501     // size, or monotonically decreasing it.
 502     //
 503     unsigned SrcSize = SrcTy->getPrimitiveSize();
 504     unsigned MidSize = MidTy->getPrimitiveSize();
 505     unsigned DstSize = DstTy->getPrimitiveSize();
 506     if (SrcSize < MidSize && MidSize < DstSize)
 507       return true;
 508
 509     if (SrcSize > MidSize && MidSize > DstSize)
 510       return true;
 511   }
 512
 513   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
 514   // like:  short -> ushort -> uint, because this can create wrong results if
 515   // the input short is negative!
 516   //
 517   return false;
 518 }
 519
 520
 521 // CastInst simplification
 522 //
 523 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
 524   // If the user is casting a value to the same type, eliminate this cast
 525   // instruction...
 526   if (CI.getType() == CI.getOperand(0)->getType())
 527     return ReplaceInstUsesWith(CI, CI.getOperand(0));
 528
 529   // If casting the result of another cast instruction, try to eliminate this
 530   // one!
 531   //
 532   if (CastInst *CSrc = dyn_cast<CastInst>(CI.getOperand(0))) {
 533     if (isEliminableCastOfCast(CI, CSrc)) {
 534       // This instruction now refers directly to the cast's src operand.  This
 535       // has a good chance of making CSrc dead.
 536       CI.setOperand(0, CSrc->getOperand(0));
 537       return &CI;
 538     }
 539
 540     // If this is an A->B->A cast, and we are dealing with integral types, try
 541     // to convert this into a logical 'and' instruction.
 542     //
 543     if (CSrc->getOperand(0)->getType() == CI.getType() &&
 544         CI.getType()->isIntegral() && CSrc->getType()->isIntegral() &&
 545         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
 546         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
 547       assert(CSrc->getType() != Type::ULongTy &&
 548              "Cannot have type bigger than ulong!");
 549       unsigned AndValue = (1U << CSrc->getType()->getPrimitiveSize()*8)-1;
 550       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
 551       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
 552                                     AndOp);
 553     }
 554   }
 555
 556   return 0;
 557 }
 558
 559
 560 // PHINode simplification
 561 //
 562 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
 563   // If the PHI node only has one incoming value, eliminate the PHI node...
 564   if (PN.getNumIncomingValues() == 1)
 565     return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
 566
 567   return 0;
 568 }
 569
 570
 571 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 572   // Is it 'getelementptr %P, uint 0'  or 'getelementptr %P'
 573   // If so, eliminate the noop.
 574   if ((GEP.getNumOperands() == 2 &&
 575        GEP.getOperand(1) == Constant::getNullValue(Type::UIntTy)) ||
 576       GEP.getNumOperands() == 1)
 577     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
 578
 579   // Combine Indices - If the source pointer to this getelementptr instruction
 580   // is a getelementptr instruction, combine the indices of the two
 581   // getelementptr instructions into a single instruction.
 582   //
 583   if (GetElementPtrInst *Src =
 584       dyn_cast<GetElementPtrInst>(GEP.getPointerOperand())) {
 585     std::vector<Value *> Indices;
 586
 587     // Can we combine the two pointer arithmetics offsets?
 588     if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
 589         isa<Constant>(GEP.getOperand(1))) {
 590       // Replace the index list on this GEP with the index on the getelementptr
 591       Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
 592       Indices[0] = *cast<Constant>(Src->getOperand(1)) +
 593                    *cast<Constant>(GEP.getOperand(1));
 594       assert(Indices[0] != 0 && "Constant folding of uint's failed!?");
 595
 596     } else if (*GEP.idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
 597       // Otherwise we can do the fold if the first index of the GEP is a zero
 598       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 599       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
 600     }
 601
 602     if (!Indices.empty())
 603       return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
 604   }
 605
 606   return 0;
 607 }
 608
 609
 610 bool InstCombiner::runOnFunction(Function &F) {
 611   bool Changed = false;
 612
 613   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
 614
 615   while (!WorkList.empty()) {
 616     Instruction *I = WorkList.back();  // Get an instruction from the worklist
 617     WorkList.pop_back();
 618
 619     // Now that we have an instruction, try combining it to simplify it...
 620     if (Instruction *Result = visit(*I)) {
 621       ++NumCombined;
 622       // Should we replace the old instruction with a new one?
 623       if (Result != I) {
 624         // Instructions can end up on the worklist more than once.  Make sure
 625         // we do not process an instruction that has been deleted.
 626         WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 627                        WorkList.end());
 628
 629         ReplaceInstWithInst(I, Result);
 630       } else {
 631         BasicBlock::iterator II = I;
 632
 633         // If the instruction was modified, it's possible that it is now dead.
 634         // if so, remove it.
 635         if (dceInstruction(II)) {
 636           // Instructions may end up in the worklist more than once.  Erase them
 637           // all.
 638           WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 639                          WorkList.end());
 640           Result = 0;
 641         }
 642       }
 643
 644       if (Result) {
 645         WorkList.push_back(Result);
 646         AddUsesToWorkList(*Result);
 647       }
 648       Changed = true;
 649     }
 650   }
 651
 652   return Changed;
 653 }
 654
 655 Pass *createInstructionCombiningPass() {
 656   return new InstCombiner();
 657 }