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