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 *visitAdd(BinaryOperator &I);
  64     Instruction *visitSub(BinaryOperator &I);
  65     Instruction *visitMul(BinaryOperator &I);
  66     Instruction *visitDiv(BinaryOperator &I);
  67     Instruction *visitRem(BinaryOperator &I);
  68     Instruction *visitAnd(BinaryOperator &I);
  69     Instruction *visitOr (BinaryOperator &I);
  70     Instruction *visitXor(BinaryOperator &I);
  71     Instruction *visitSetCondInst(BinaryOperator &I);
  72     Instruction *visitShiftInst(Instruction &I);
  73     Instruction *visitCastInst(CastInst &CI);
  74     Instruction *visitPHINode(PHINode &PN);
  75     Instruction *visitGetElementPtrInst(GetElementPtrInst &GEP);
  76
  77     // visitInstruction - Specify what to return for unhandled instructions...
  78     Instruction *visitInstruction(Instruction &I) { return 0; }
  79
  80     // InsertNewInstBefore - insert an instruction New before instruction Old
  81     // in the program.  Add the new instruction to the worklist.
  82     //
  83     void InsertNewInstBefore(Instruction *New, Instruction &Old) {
  84       assert(New && New->getParent() == 0 &&
  85              "New instruction already inserted into a basic block!");
  86       BasicBlock *BB = Old.getParent();
  87       BB->getInstList().insert(&Old, New);  // Insert inst
  88       WorkList.push_back(New);              // Add to worklist
  89     }
  90
  91     // ReplaceInstUsesWith - This method is to be used when an instruction is
  92     // found to be dead, replacable with another preexisting expression.  Here
  93     // we add all uses of I to the worklist, replace all uses of I with the new
  94     // value, then return I, so that the inst combiner will know that I was
  95     // modified.
  96     //
  97     Instruction *ReplaceInstUsesWith(Instruction &I, Value *V) {
  98       AddUsesToWorkList(I);         // Add all modified instrs to worklist
  99       I.replaceAllUsesWith(V);
 100       return &I;
 101     }
 102   };
 103
 104   RegisterOpt<InstCombiner> X("instcombine", "Combine redundant instructions");
 105 }
 106
 107
 108 // Make sure that this instruction has a constant on the right hand side if it
 109 // has any constant arguments.  If not, fix it an return true.
 110 //
 111 static bool SimplifyBinOp(BinaryOperator &I) {
 112   if (isa<Constant>(I.getOperand(0)) && !isa<Constant>(I.getOperand(1)))
 113     return !I.swapOperands();
 114   return false;
 115 }
 116
 117 // dyn_castNegInst - Given a 'sub' instruction, return the RHS of the
 118 // instruction if the LHS is a constant zero (which is the 'negate' form).
 119 //
 120 static inline Value *dyn_castNegInst(Value *V) {
 121   Instruction *I = dyn_cast<Instruction>(V);
 122   if (!I || I->getOpcode() != Instruction::Sub) return 0;
 123
 124   if (I->getOperand(0) == Constant::getNullValue(I->getType()))
 125     return I->getOperand(1);
 126   return 0;
 127 }
 128
 129 static inline Value *dyn_castNotInst(Value *V) {
 130   Instruction *I = dyn_cast<Instruction>(V);
 131   if (!I || I->getOpcode() != Instruction::Xor) return 0;
 132
 133   if (ConstantIntegral *CI = dyn_cast<ConstantIntegral>(I->getOperand(1)))
 134     if (CI->isAllOnesValue())
 135       return I->getOperand(0);
 136   return 0;
 137 }
 138
 139 Instruction *InstCombiner::visitAdd(BinaryOperator &I) {
 140   bool Changed = SimplifyBinOp(I);
 141   Value *LHS = I.getOperand(0), *RHS = I.getOperand(1);
 142
 143   // Eliminate 'add int %X, 0'
 144   if (RHS == Constant::getNullValue(I.getType()))
 145     return ReplaceInstUsesWith(I, LHS);
 146
 147   // -A + B  -->  B - A
 148   if (Value *V = dyn_castNegInst(LHS))
 149     return BinaryOperator::create(Instruction::Sub, RHS, V);
 150
 151   // A + -B  -->  A - B
 152   if (Value *V = dyn_castNegInst(RHS))
 153     return BinaryOperator::create(Instruction::Sub, LHS, V);
 154
 155   // Simplify add instructions with a constant RHS...
 156   if (Constant *Op2 = dyn_cast<Constant>(RHS)) {
 157     if (BinaryOperator *ILHS = dyn_cast<BinaryOperator>(LHS)) {
 158       if (ILHS->getOpcode() == Instruction::Add &&
 159           isa<Constant>(ILHS->getOperand(1))) {
 160         // Fold:
 161         //    %Y = add int %X, 1
 162         //    %Z = add int %Y, 1
 163         // into:
 164         //    %Z = add int %X, 2
 165         //
 166         if (Constant *Val = *Op2 + *cast<Constant>(ILHS->getOperand(1))) {
 167           I.setOperand(0, ILHS->getOperand(0));
 168           I.setOperand(1, Val);
 169           return &I;
 170         }
 171       }
 172     }
 173   }
 174
 175   return Changed ? &I : 0;
 176 }
 177
 178 Instruction *InstCombiner::visitSub(BinaryOperator &I) {
 179   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 180
 181   if (Op0 == Op1)         // sub X, X  -> 0
 182     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 183
 184   // If this is a subtract instruction with a constant RHS, convert it to an add
 185   // instruction of a negative constant
 186   //
 187   if (Constant *Op2 = dyn_cast<Constant>(Op1))
 188     if (Constant *RHS = *Constant::getNullValue(I.getType()) - *Op2) // 0 - RHS
 189       return BinaryOperator::create(Instruction::Add, Op0, RHS, I.getName());
 190
 191   // If this is a 'B = x-(-A)', change to B = x+A...
 192   if (Value *V = dyn_castNegInst(Op1))
 193     return BinaryOperator::create(Instruction::Add, Op0, V);
 194
 195   // Replace (x - (y - z)) with (x + (z - y)) if the (y - z) subexpression is
 196   // not used by anyone else...
 197   //
 198   if (BinaryOperator *Op1I = dyn_cast<BinaryOperator>(Op1))
 199     if (Op1I->use_size() == 1 && Op1I->getOpcode() == Instruction::Sub) {
 200       // Swap the two operands of the subexpr...
 201       Value *IIOp0 = Op1I->getOperand(0), *IIOp1 = Op1I->getOperand(1);
 202       Op1I->setOperand(0, IIOp1);
 203       Op1I->setOperand(1, IIOp0);
 204
 205       // Create the new top level add instruction...
 206       return BinaryOperator::create(Instruction::Add, Op0, Op1);
 207     }
 208   return 0;
 209 }
 210
 211 Instruction *InstCombiner::visitMul(BinaryOperator &I) {
 212   bool Changed = SimplifyBinOp(I);
 213   Value *Op1 = I.getOperand(0);
 214
 215   // Simplify mul instructions with a constant RHS...
 216   if (Constant *Op2 = dyn_cast<Constant>(I.getOperand(1))) {
 217     if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(1))
 218       return ReplaceInstUsesWith(I, Op1);  // Eliminate 'mul int %X, 1'
 219
 220     if (I.getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(2))
 221       // Convert 'mul int %X, 2' to 'add int %X, %X'
 222       return BinaryOperator::create(Instruction::Add, Op1, Op1, I.getName());
 223
 224     if (Op2->isNullValue())
 225       return ReplaceInstUsesWith(I, Op2);  // Eliminate 'mul int %X, 0'
 226   }
 227
 228   return Changed ? &I : 0;
 229 }
 230
 231
 232 Instruction *InstCombiner::visitDiv(BinaryOperator &I) {
 233   // div X, 1 == X
 234   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1)))
 235     if (RHS->equalsInt(1))
 236       return ReplaceInstUsesWith(I, I.getOperand(0));
 237   return 0;
 238 }
 239
 240
 241 Instruction *InstCombiner::visitRem(BinaryOperator &I) {
 242   // rem X, 1 == 0
 243   if (ConstantInt *RHS = dyn_cast<ConstantInt>(I.getOperand(1)))
 244     if (RHS->equalsInt(1))
 245       return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 246
 247   return 0;
 248 }
 249
 250 // isMaxValueMinusOne - return true if this is Max-1
 251 static bool isMaxValueMinusOne(const ConstantInt *C) {
 252   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C)) {
 253     // Calculate -1 casted to the right type...
 254     unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 255     uint64_t Val = ~0ULL;                // All ones
 256     Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 257     return CU->getValue() == Val-1;
 258   }
 259
 260   const ConstantSInt *CS = cast<ConstantSInt>(C);
 261
 262   // Calculate 0111111111..11111
 263   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 264   int64_t Val = INT64_MAX;             // All ones
 265   Val >>= 64-TypeBits;                 // Shift out unwanted 1 bits...
 266   return CS->getValue() == Val-1;
 267 }
 268
 269 // isMinValuePlusOne - return true if this is Min+1
 270 static bool isMinValuePlusOne(const ConstantInt *C) {
 271   if (const ConstantUInt *CU = dyn_cast<ConstantUInt>(C))
 272     return CU->getValue() == 1;
 273
 274   const ConstantSInt *CS = cast<ConstantSInt>(C);
 275
 276   // Calculate 1111111111000000000000
 277   unsigned TypeBits = C->getType()->getPrimitiveSize()*8;
 278   int64_t Val = -1;                    // All ones
 279   Val <<= TypeBits-1;                  // Shift over to the right spot
 280   return CS->getValue() == Val+1;
 281 }
 282
 283
 284 Instruction *InstCombiner::visitAnd(BinaryOperator &I) {
 285   bool Changed = SimplifyBinOp(I);
 286   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 287
 288   // and X, X = X   and X, 0 == 0
 289   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 290     return ReplaceInstUsesWith(I, Op1);
 291
 292   // and X, -1 == X
 293   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1))
 294     if (RHS->isAllOnesValue())
 295       return ReplaceInstUsesWith(I, Op0);
 296
 297   // and (not A), (not B) == not (or A, B)
 298   if (Op0->use_size() == 1 && Op1->use_size() == 1)
 299     if (Value *A = dyn_castNotInst(Op0))
 300       if (Value *B = dyn_castNotInst(Op1)) {
 301         Instruction *Or = BinaryOperator::create(Instruction::Or, A, B,
 302                                                  I.getName()+".demorgan");
 303         InsertNewInstBefore(Or, I);
 304         return BinaryOperator::createNot(Or, I.getName());
 305       }
 306
 307   return Changed ? &I : 0;
 308 }
 309
 310
 311
 312 Instruction *InstCombiner::visitOr(BinaryOperator &I) {
 313   bool Changed = SimplifyBinOp(I);
 314   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 315
 316   // or X, X = X   or X, 0 == X
 317   if (Op0 == Op1 || Op1 == Constant::getNullValue(I.getType()))
 318     return ReplaceInstUsesWith(I, Op0);
 319
 320   // or X, -1 == -1
 321   if (ConstantIntegral *RHS = dyn_cast<ConstantIntegral>(Op1))
 322     if (RHS->isAllOnesValue())
 323       return ReplaceInstUsesWith(I, Op1);
 324
 325   return Changed ? &I : 0;
 326 }
 327
 328
 329
 330 Instruction *InstCombiner::visitXor(BinaryOperator &I) {
 331   bool Changed = SimplifyBinOp(I);
 332   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 333
 334   // xor X, X = 0
 335   if (Op0 == Op1)
 336     return ReplaceInstUsesWith(I, Constant::getNullValue(I.getType()));
 337
 338   if (ConstantIntegral *Op1C = dyn_cast<ConstantIntegral>(Op1)) {
 339     // xor X, 0 == X
 340     if (Op1C->isNullValue())
 341       return ReplaceInstUsesWith(I, Op0);
 342
 343     // Is this a "NOT" instruction?
 344     if (Op1C->isAllOnesValue()) {
 345       // xor (xor X, -1), -1 = not (not X) = X
 346       if (Value *X = dyn_castNotInst(Op0))
 347         return ReplaceInstUsesWith(I, X);
 348
 349       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
 350       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0))
 351         if (SCI->use_size() == 1)
 352           return new SetCondInst(SCI->getInverseCondition(),
 353                                  SCI->getOperand(0), SCI->getOperand(1));
 354     }
 355   }
 356
 357   return Changed ? &I : 0;
 358 }
 359
 360 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
 361 static Constant *AddOne(ConstantInt *C) {
 362   Constant *Result = *C + *ConstantInt::get(C->getType(), 1);
 363   assert(Result && "Constant folding integer addition failed!");
 364   return Result;
 365 }
 366 static Constant *SubOne(ConstantInt *C) {
 367   Constant *Result = *C - *ConstantInt::get(C->getType(), 1);
 368   assert(Result && "Constant folding integer addition failed!");
 369   return Result;
 370 }
 371
 372 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
 373 // true when both operands are equal...
 374 //
 375 static bool isTrueWhenEqual(Instruction &I) {
 376   return I.getOpcode() == Instruction::SetEQ ||
 377          I.getOpcode() == Instruction::SetGE ||
 378          I.getOpcode() == Instruction::SetLE;
 379 }
 380
 381 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
 382   bool Changed = SimplifyBinOp(I);
 383   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 384   const Type *Ty = Op0->getType();
 385
 386   // setcc X, X
 387   if (Op0 == Op1)
 388     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
 389
 390   // setcc <global*>, 0 - Global value addresses are never null!
 391   if (isa<GlobalValue>(Op0) && isa<ConstantPointerNull>(Op1))
 392     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
 393
 394   // setcc's with boolean values can always be turned into bitwise operations
 395   if (Ty == Type::BoolTy) {
 396     // If this is <, >, or !=, we can change this into a simple xor instruction
 397     if (!isTrueWhenEqual(I))
 398       return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
 399
 400     // Otherwise we need to make a temporary intermediate instruction and insert
 401     // it into the instruction stream.  This is what we are after:
 402     //
 403     //  seteq bool %A, %B -> ~(A^B)
 404     //  setle bool %A, %B -> ~A | B
 405     //  setge bool %A, %B -> A | ~B
 406     //
 407     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
 408       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
 409                                                 I.getName()+"tmp");
 410       InsertNewInstBefore(Xor, I);
 411       return BinaryOperator::createNot(Xor, I.getName());
 412     }
 413
 414     // Handle the setXe cases...
 415     assert(I.getOpcode() == Instruction::SetGE ||
 416            I.getOpcode() == Instruction::SetLE);
 417
 418     if (I.getOpcode() == Instruction::SetGE)
 419       std::swap(Op0, Op1);                   // Change setge -> setle
 420
 421     // Now we just have the SetLE case.
 422     Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
 423     InsertNewInstBefore(Not, I);
 424     return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
 425   }
 426
 427   // Check to see if we are doing one of many comparisons against constant
 428   // integers at the end of their ranges...
 429   //
 430   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 431     // Check to see if we are comparing against the minimum or maximum value...
 432     if (CI->isMinValue()) {
 433       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
 434         return ReplaceInstUsesWith(I, ConstantBool::False);
 435       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
 436         return ReplaceInstUsesWith(I, ConstantBool::True);
 437       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
 438         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 439       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
 440         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 441
 442     } else if (CI->isMaxValue()) {
 443       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
 444         return ReplaceInstUsesWith(I, ConstantBool::False);
 445       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
 446         return ReplaceInstUsesWith(I, ConstantBool::True);
 447       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
 448         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 449       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
 450         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 451
 452       // Comparing against a value really close to min or max?
 453     } else if (isMinValuePlusOne(CI)) {
 454       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
 455         return BinaryOperator::create(Instruction::SetEQ, Op0,
 456                                       SubOne(CI), I.getName());
 457       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
 458         return BinaryOperator::create(Instruction::SetNE, Op0,
 459                                       SubOne(CI), I.getName());
 460
 461     } else if (isMaxValueMinusOne(CI)) {
 462       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
 463         return BinaryOperator::create(Instruction::SetEQ, Op0,
 464                                       AddOne(CI), I.getName());
 465       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
 466         return BinaryOperator::create(Instruction::SetNE, Op0,
 467                                       AddOne(CI), I.getName());
 468     }
 469   }
 470
 471   return Changed ? &I : 0;
 472 }
 473
 474
 475
 476 Instruction *InstCombiner::visitShiftInst(Instruction &I) {
 477   assert(I.getOperand(1)->getType() == Type::UByteTy);
 478   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 479
 480   // shl X, 0 == X and shr X, 0 == X
 481   // shl 0, X == 0 and shr 0, X == 0
 482   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
 483       Op0 == Constant::getNullValue(Op0->getType()))
 484     return ReplaceInstUsesWith(I, Op0);
 485
 486   // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of
 487   // a signed value.
 488   //
 489   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
 490     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
 491     if (CUI->getValue() >= TypeBits &&
 492         !(Op0->getType()->isSigned() && I.getOpcode() == Instruction::Shr))
 493       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
 494   }
 495   return 0;
 496 }
 497
 498
 499 // isCIntegral - For the purposes of casting, we allow conversion of sizes and
 500 // stuff as long as the value type acts basically integral like.
 501 //
 502 static bool isCIntegral(const Type *Ty) {
 503   return Ty->isIntegral() || Ty == Type::BoolTy;
 504 }
 505
 506 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
 507 // instruction.
 508 //
 509 static inline bool isEliminableCastOfCast(const CastInst &CI,
 510                                           const CastInst *CSrc) {
 511   assert(CI.getOperand(0) == CSrc);
 512   const Type *SrcTy = CSrc->getOperand(0)->getType();
 513   const Type *MidTy = CSrc->getType();
 514   const Type *DstTy = CI.getType();
 515
 516   // It is legal to eliminate the instruction if casting A->B->A if the sizes
 517   // are identical and the bits don't get reinterpreted (for example
 518   // int->float->int would not be allowed)
 519   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy))
 520     return true;
 521
 522   // Allow free casting and conversion of sizes as long as the sign doesn't
 523   // change...
 524   if (isCIntegral(SrcTy) && isCIntegral(MidTy) && isCIntegral(DstTy)) {
 525     unsigned SrcSize = SrcTy->getPrimitiveSize();
 526     unsigned MidSize = MidTy->getPrimitiveSize();
 527     unsigned DstSize = DstTy->getPrimitiveSize();
 528
 529     // Cases where we are monotonically decreasing the size of the type are
 530     // always ok, regardless of what sign changes are going on.
 531     //
 532     if (SrcSize >= MidSize && MidSize >= DstSize)
 533       return true;
 534
 535     // If we are monotonically growing, things are more complex.
 536     //
 537     if (SrcSize <= MidSize && MidSize <= DstSize) {
 538       // We have eight combinations of signedness to worry about. Here's the
 539       // table:
 540       static const int SignTable[8] = {
 541         // CODE, SrcSigned, MidSigned, DstSigned, Comment
 542         1,     //   U          U          U       Always ok
 543         1,     //   U          U          S       Always ok
 544         3,     //   U          S          U       Ok iff SrcSize != MidSize
 545         3,     //   U          S          S       Ok iff SrcSize != MidSize
 546         0,     //   S          U          U       Never ok
 547         2,     //   S          U          S       Ok iff MidSize == DstSize
 548         1,     //   S          S          U       Always ok
 549         1,     //   S          S          S       Always ok
 550       };
 551
 552       // Choose an action based on the current entry of the signtable that this
 553       // cast of cast refers to...
 554       unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
 555       switch (SignTable[Row]) {
 556       case 0: return false;              // Never ok
 557       case 1: return true;               // Always ok
 558       case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
 559       case 3:                            // Ok iff SrcSize != MidSize
 560         return SrcSize != MidSize || SrcTy == Type::BoolTy;
 561       default: assert(0 && "Bad entry in sign table!");
 562       }
 563     }
 564   }
 565
 566   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
 567   // like:  short -> ushort -> uint, because this can create wrong results if
 568   // the input short is negative!
 569   //
 570   return false;
 571 }
 572
 573
 574 // CastInst simplification
 575 //
 576 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
 577   // If the user is casting a value to the same type, eliminate this cast
 578   // instruction...
 579   if (CI.getType() == CI.getOperand(0)->getType())
 580     return ReplaceInstUsesWith(CI, CI.getOperand(0));
 581
 582   // If casting the result of another cast instruction, try to eliminate this
 583   // one!
 584   //
 585   if (CastInst *CSrc = dyn_cast<CastInst>(CI.getOperand(0))) {
 586     if (isEliminableCastOfCast(CI, CSrc)) {
 587       // This instruction now refers directly to the cast's src operand.  This
 588       // has a good chance of making CSrc dead.
 589       CI.setOperand(0, CSrc->getOperand(0));
 590       return &CI;
 591     }
 592
 593     // If this is an A->B->A cast, and we are dealing with integral types, try
 594     // to convert this into a logical 'and' instruction.
 595     //
 596     if (CSrc->getOperand(0)->getType() == CI.getType() &&
 597         CI.getType()->isIntegral() && CSrc->getType()->isIntegral() &&
 598         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
 599         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
 600       assert(CSrc->getType() != Type::ULongTy &&
 601              "Cannot have type bigger than ulong!");
 602       unsigned AndValue = (1U << CSrc->getType()->getPrimitiveSize()*8)-1;
 603       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
 604       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
 605                                     AndOp);
 606     }
 607   }
 608
 609   return 0;
 610 }
 611
 612
 613 // PHINode simplification
 614 //
 615 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
 616   // If the PHI node only has one incoming value, eliminate the PHI node...
 617   if (PN.getNumIncomingValues() == 0)
 618     return ReplaceInstUsesWith(PN, Constant::getNullValue(PN.getType()));
 619   if (PN.getNumIncomingValues() == 1)
 620     return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
 621
 622   // Otherwise if all of the incoming values are the same for the PHI, replace
 623   // the PHI node with the incoming value.
 624   //
 625   Value *InVal = 0;
 626   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 627     if (PN.getIncomingValue(i) != &PN)  // Not the PHI node itself...
 628       if (InVal && PN.getIncomingValue(i) != InVal)
 629         return 0;  // Not the same, bail out.
 630       else
 631         InVal = PN.getIncomingValue(i);
 632
 633   // The only case that could cause InVal to be null is if we have a PHI node
 634   // that only has entries for itself.  In this case, there is no entry into the
 635   // loop, so kill the PHI.
 636   //
 637   if (InVal == 0) InVal = Constant::getNullValue(PN.getType());
 638
 639   // All of the incoming values are the same, replace the PHI node now.
 640   return ReplaceInstUsesWith(PN, InVal);
 641 }
 642
 643
 644 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 645   // Is it 'getelementptr %P, uint 0'  or 'getelementptr %P'
 646   // If so, eliminate the noop.
 647   if ((GEP.getNumOperands() == 2 &&
 648        GEP.getOperand(1) == Constant::getNullValue(Type::UIntTy)) ||
 649       GEP.getNumOperands() == 1)
 650     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
 651
 652   // Combine Indices - If the source pointer to this getelementptr instruction
 653   // is a getelementptr instruction, combine the indices of the two
 654   // getelementptr instructions into a single instruction.
 655   //
 656   if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
 657     std::vector<Value *> Indices;
 658
 659     // Can we combine the two pointer arithmetics offsets?
 660     if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
 661         isa<Constant>(GEP.getOperand(1))) {
 662       // Replace the index list on this GEP with the index on the getelementptr
 663       Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
 664       Indices[0] = *cast<Constant>(Src->getOperand(1)) +
 665                    *cast<Constant>(GEP.getOperand(1));
 666       assert(Indices[0] != 0 && "Constant folding of uint's failed!?");
 667
 668     } else if (*GEP.idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
 669       // Otherwise we can do the fold if the first index of the GEP is a zero
 670       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 671       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
 672     }
 673
 674     if (!Indices.empty())
 675       return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
 676
 677   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
 678     // GEP of global variable.  If all of the indices for this GEP are
 679     // constants, we can promote this to a constexpr instead of an instruction.
 680
 681     // Scan for nonconstants...
 682     std::vector<Constant*> Indices;
 683     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
 684     for (; I != E && isa<Constant>(*I); ++I)
 685       Indices.push_back(cast<Constant>(*I));
 686
 687     if (I == E) {  // If they are all constants...
 688       ConstantExpr *CE =
 689         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
 690
 691       // Replace all uses of the GEP with the new constexpr...
 692       return ReplaceInstUsesWith(GEP, CE);
 693     }
 694   }
 695
 696   return 0;
 697 }
 698
 699
 700 bool InstCombiner::runOnFunction(Function &F) {
 701   bool Changed = false;
 702
 703   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
 704
 705   while (!WorkList.empty()) {
 706     Instruction *I = WorkList.back();  // Get an instruction from the worklist
 707     WorkList.pop_back();
 708
 709     // Now that we have an instruction, try combining it to simplify it...
 710     if (Instruction *Result = visit(*I)) {
 711       ++NumCombined;
 712       // Should we replace the old instruction with a new one?
 713       if (Result != I) {
 714         // Instructions can end up on the worklist more than once.  Make sure
 715         // we do not process an instruction that has been deleted.
 716         WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 717                        WorkList.end());
 718
 719         ReplaceInstWithInst(I, Result);
 720       } else {
 721         BasicBlock::iterator II = I;
 722
 723         // If the instruction was modified, it's possible that it is now dead.
 724         // if so, remove it.
 725         if (dceInstruction(II)) {
 726           // Instructions may end up in the worklist more than once.  Erase them
 727           // all.
 728           WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 729                          WorkList.end());
 730           Result = 0;
 731         }
 732       }
 733
 734       if (Result) {
 735         WorkList.push_back(Result);
 736         AddUsesToWorkList(*Result);
 737       }
 738       Changed = true;
 739     }
 740   }
 741
 742   return Changed;
 743 }
 744
 745 Pass *createInstructionCombiningPass() {
 746   return new InstCombiner();
 747 }