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