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