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     // Is this a "NOT" instruction?
 332     if (Op1C->isAllOnesValue()) {
 333       // xor (xor X, -1), -1 = not (not X) = X
 334       if (Value *X = dyn_castNotInst(Op0))
 335         return ReplaceInstUsesWith(I, X);
 336
 337       // xor (setcc A, B), true = not (setcc A, B) = setncc A, B
 338       if (SetCondInst *SCI = dyn_cast<SetCondInst>(Op0))
 339         if (SCI->use_size() == 1)
 340           return new SetCondInst(SCI->getInverseCondition(),
 341                                  SCI->getOperand(0), SCI->getOperand(1));
 342     }
 343   }
 344
 345   return Changed ? &I : 0;
 346 }
 347
 348 // AddOne, SubOne - Add or subtract a constant one from an integer constant...
 349 static Constant *AddOne(ConstantInt *C) {
 350   Constant *Result = *C + *ConstantInt::get(C->getType(), 1);
 351   assert(Result && "Constant folding integer addition failed!");
 352   return Result;
 353 }
 354 static Constant *SubOne(ConstantInt *C) {
 355   Constant *Result = *C - *ConstantInt::get(C->getType(), 1);
 356   assert(Result && "Constant folding integer addition failed!");
 357   return Result;
 358 }
 359
 360 // isTrueWhenEqual - Return true if the specified setcondinst instruction is
 361 // true when both operands are equal...
 362 //
 363 static bool isTrueWhenEqual(Instruction &I) {
 364   return I.getOpcode() == Instruction::SetEQ ||
 365          I.getOpcode() == Instruction::SetGE ||
 366          I.getOpcode() == Instruction::SetLE;
 367 }
 368
 369 Instruction *InstCombiner::visitSetCondInst(BinaryOperator &I) {
 370   bool Changed = SimplifyBinOp(I);
 371   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 372   const Type *Ty = Op0->getType();
 373
 374   // setcc X, X
 375   if (Op0 == Op1)
 376     return ReplaceInstUsesWith(I, ConstantBool::get(isTrueWhenEqual(I)));
 377
 378   // setcc <global*>, 0 - Global value addresses are never null!
 379   if (isa<GlobalValue>(Op0) && isa<ConstantPointerNull>(Op1))
 380     return ReplaceInstUsesWith(I, ConstantBool::get(!isTrueWhenEqual(I)));
 381
 382   // setcc's with boolean values can always be turned into bitwise operations
 383   if (Ty == Type::BoolTy) {
 384     // If this is <, >, or !=, we can change this into a simple xor instruction
 385     if (!isTrueWhenEqual(I))
 386       return BinaryOperator::create(Instruction::Xor, Op0, Op1, I.getName());
 387
 388     // Otherwise we need to make a temporary intermediate instruction and insert
 389     // it into the instruction stream.  This is what we are after:
 390     //
 391     //  seteq bool %A, %B -> ~(A^B)
 392     //  setle bool %A, %B -> ~A | B
 393     //  setge bool %A, %B -> A | ~B
 394     //
 395     if (I.getOpcode() == Instruction::SetEQ) {  // seteq case
 396       Instruction *Xor = BinaryOperator::create(Instruction::Xor, Op0, Op1,
 397                                                 I.getName()+"tmp");
 398       InsertNewInstBefore(Xor, I);
 399       return BinaryOperator::createNot(Xor, I.getName());
 400     }
 401
 402     // Handle the setXe cases...
 403     assert(I.getOpcode() == Instruction::SetGE ||
 404            I.getOpcode() == Instruction::SetLE);
 405
 406     if (I.getOpcode() == Instruction::SetGE)
 407       std::swap(Op0, Op1);                   // Change setge -> setle
 408
 409     // Now we just have the SetLE case.
 410     Instruction *Not = BinaryOperator::createNot(Op0, I.getName()+"tmp");
 411     InsertNewInstBefore(Not, I);
 412     return BinaryOperator::create(Instruction::Or, Not, Op1, I.getName());
 413   }
 414
 415   // Check to see if we are doing one of many comparisons against constant
 416   // integers at the end of their ranges...
 417   //
 418   if (ConstantInt *CI = dyn_cast<ConstantInt>(Op1)) {
 419     // Check to see if we are comparing against the minimum or maximum value...
 420     if (CI->isMinValue()) {
 421       if (I.getOpcode() == Instruction::SetLT)       // A < MIN -> FALSE
 422         return ReplaceInstUsesWith(I, ConstantBool::False);
 423       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN -> TRUE
 424         return ReplaceInstUsesWith(I, ConstantBool::True);
 425       if (I.getOpcode() == Instruction::SetLE)       // A <= MIN -> A == MIN
 426         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 427       if (I.getOpcode() == Instruction::SetGT)       // A > MIN -> A != MIN
 428         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 429
 430     } else if (CI->isMaxValue()) {
 431       if (I.getOpcode() == Instruction::SetGT)       // A > MAX -> FALSE
 432         return ReplaceInstUsesWith(I, ConstantBool::False);
 433       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX -> TRUE
 434         return ReplaceInstUsesWith(I, ConstantBool::True);
 435       if (I.getOpcode() == Instruction::SetGE)       // A >= MAX -> A == MAX
 436         return BinaryOperator::create(Instruction::SetEQ, Op0,Op1, I.getName());
 437       if (I.getOpcode() == Instruction::SetLT)       // A < MAX -> A != MAX
 438         return BinaryOperator::create(Instruction::SetNE, Op0,Op1, I.getName());
 439
 440       // Comparing against a value really close to min or max?
 441     } else if (isMinValuePlusOne(CI)) {
 442       if (I.getOpcode() == Instruction::SetLT)       // A < MIN+1 -> A == MIN
 443         return BinaryOperator::create(Instruction::SetEQ, Op0,
 444                                       SubOne(CI), I.getName());
 445       if (I.getOpcode() == Instruction::SetGE)       // A >= MIN-1 -> A != MIN
 446         return BinaryOperator::create(Instruction::SetNE, Op0,
 447                                       SubOne(CI), I.getName());
 448
 449     } else if (isMaxValueMinusOne(CI)) {
 450       if (I.getOpcode() == Instruction::SetGT)       // A > MAX-1 -> A == MAX
 451         return BinaryOperator::create(Instruction::SetEQ, Op0,
 452                                       AddOne(CI), I.getName());
 453       if (I.getOpcode() == Instruction::SetLE)       // A <= MAX-1 -> A != MAX
 454         return BinaryOperator::create(Instruction::SetNE, Op0,
 455                                       AddOne(CI), I.getName());
 456     }
 457   }
 458
 459   return Changed ? &I : 0;
 460 }
 461
 462
 463
 464 Instruction *InstCombiner::visitShiftInst(Instruction &I) {
 465   assert(I.getOperand(1)->getType() == Type::UByteTy);
 466   Value *Op0 = I.getOperand(0), *Op1 = I.getOperand(1);
 467
 468   // shl X, 0 == X and shr X, 0 == X
 469   // shl 0, X == 0 and shr 0, X == 0
 470   if (Op1 == Constant::getNullValue(Type::UByteTy) ||
 471       Op0 == Constant::getNullValue(Op0->getType()))
 472     return ReplaceInstUsesWith(I, Op0);
 473
 474   // shl uint X, 32 = 0 and shr ubyte Y, 9 = 0, ... just don't eliminate shr of
 475   // a signed value.
 476   //
 477   if (ConstantUInt *CUI = dyn_cast<ConstantUInt>(Op1)) {
 478     unsigned TypeBits = Op0->getType()->getPrimitiveSize()*8;
 479     if (CUI->getValue() >= TypeBits &&
 480         !(Op0->getType()->isSigned() && I.getOpcode() == Instruction::Shr))
 481       return ReplaceInstUsesWith(I, Constant::getNullValue(Op0->getType()));
 482   }
 483   return 0;
 484 }
 485
 486
 487 // isCIntegral - For the purposes of casting, we allow conversion of sizes and
 488 // stuff as long as the value type acts basically integral like.
 489 //
 490 static bool isCIntegral(const Type *Ty) {
 491   return Ty->isIntegral() || Ty == Type::BoolTy;
 492 }
 493
 494 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
 495 // instruction.
 496 //
 497 static inline bool isEliminableCastOfCast(const CastInst &CI,
 498                                           const CastInst *CSrc) {
 499   assert(CI.getOperand(0) == CSrc);
 500   const Type *SrcTy = CSrc->getOperand(0)->getType();
 501   const Type *MidTy = CSrc->getType();
 502   const Type *DstTy = CI.getType();
 503
 504   // It is legal to eliminate the instruction if casting A->B->A if the sizes
 505   // are identical and the bits don't get reinterpreted (for example
 506   // int->float->int would not be allowed)
 507   if (SrcTy == DstTy && SrcTy->isLosslesslyConvertableTo(MidTy))
 508     return true;
 509
 510   // Allow free casting and conversion of sizes as long as the sign doesn't
 511   // change...
 512   if (isCIntegral(SrcTy) && isCIntegral(MidTy) && isCIntegral(DstTy)) {
 513     unsigned SrcSize = SrcTy->getPrimitiveSize();
 514     unsigned MidSize = MidTy->getPrimitiveSize();
 515     unsigned DstSize = DstTy->getPrimitiveSize();
 516
 517     // Cases where we are monotonically decreasing the size of the type are
 518     // always ok, regardless of what sign changes are going on.
 519     //
 520     if (SrcSize >= MidSize && MidSize >= DstSize)
 521       return true;
 522
 523     // If we are monotonically growing, things are more complex.
 524     //
 525     if (SrcSize <= MidSize && MidSize <= DstSize) {
 526       // We have eight combinations of signedness to worry about. Here's the
 527       // table:
 528       static const int SignTable[8] = {
 529         // CODE, SrcSigned, MidSigned, DstSigned, Comment
 530         1,     //   U          U          U       Always ok
 531         1,     //   U          U          S       Always ok
 532         3,     //   U          S          U       Ok iff SrcSize != MidSize
 533         3,     //   U          S          S       Ok iff SrcSize != MidSize
 534         0,     //   S          U          U       Never ok
 535         2,     //   S          U          S       Ok iff MidSize == DstSize
 536         1,     //   S          S          U       Always ok
 537         1,     //   S          S          S       Always ok
 538       };
 539
 540       // Choose an action based on the current entry of the signtable that this
 541       // cast of cast refers to...
 542       unsigned Row = SrcTy->isSigned()*4+MidTy->isSigned()*2+DstTy->isSigned();
 543       switch (SignTable[Row]) {
 544       case 0: return false;              // Never ok
 545       case 1: return true;               // Always ok
 546       case 2: return MidSize == DstSize; // Ok iff MidSize == DstSize
 547       case 3:                            // Ok iff SrcSize != MidSize
 548         return SrcSize != MidSize || SrcTy == Type::BoolTy;
 549       default: assert(0 && "Bad entry in sign table!");
 550       }
 551     }
 552   }
 553
 554   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
 555   // like:  short -> ushort -> uint, because this can create wrong results if
 556   // the input short is negative!
 557   //
 558   return false;
 559 }
 560
 561
 562 // CastInst simplification
 563 //
 564 Instruction *InstCombiner::visitCastInst(CastInst &CI) {
 565   // If the user is casting a value to the same type, eliminate this cast
 566   // instruction...
 567   if (CI.getType() == CI.getOperand(0)->getType())
 568     return ReplaceInstUsesWith(CI, CI.getOperand(0));
 569
 570   // If casting the result of another cast instruction, try to eliminate this
 571   // one!
 572   //
 573   if (CastInst *CSrc = dyn_cast<CastInst>(CI.getOperand(0))) {
 574     if (isEliminableCastOfCast(CI, CSrc)) {
 575       // This instruction now refers directly to the cast's src operand.  This
 576       // has a good chance of making CSrc dead.
 577       CI.setOperand(0, CSrc->getOperand(0));
 578       return &CI;
 579     }
 580
 581     // If this is an A->B->A cast, and we are dealing with integral types, try
 582     // to convert this into a logical 'and' instruction.
 583     //
 584     if (CSrc->getOperand(0)->getType() == CI.getType() &&
 585         CI.getType()->isIntegral() && CSrc->getType()->isIntegral() &&
 586         CI.getType()->isUnsigned() && CSrc->getType()->isUnsigned() &&
 587         CSrc->getType()->getPrimitiveSize() < CI.getType()->getPrimitiveSize()){
 588       assert(CSrc->getType() != Type::ULongTy &&
 589              "Cannot have type bigger than ulong!");
 590       unsigned AndValue = (1U << CSrc->getType()->getPrimitiveSize()*8)-1;
 591       Constant *AndOp = ConstantUInt::get(CI.getType(), AndValue);
 592       return BinaryOperator::create(Instruction::And, CSrc->getOperand(0),
 593                                     AndOp);
 594     }
 595   }
 596
 597   return 0;
 598 }
 599
 600
 601 // PHINode simplification
 602 //
 603 Instruction *InstCombiner::visitPHINode(PHINode &PN) {
 604   // If the PHI node only has one incoming value, eliminate the PHI node...
 605   if (PN.getNumIncomingValues() == 0)
 606     return ReplaceInstUsesWith(PN, Constant::getNullValue(PN.getType()));
 607   if (PN.getNumIncomingValues() == 1)
 608     return ReplaceInstUsesWith(PN, PN.getIncomingValue(0));
 609
 610   // Otherwise if all of the incoming values are the same for the PHI, replace
 611   // the PHI node with the incoming value.
 612   //
 613   Value *InVal = 0;
 614   for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
 615     if (PN.getIncomingValue(i) != &PN)  // Not the PHI node itself...
 616       if (InVal && PN.getIncomingValue(i) != InVal)
 617         return 0;  // Not the same, bail out.
 618       else
 619         InVal = PN.getIncomingValue(i);
 620
 621   // The only case that could cause InVal to be null is if we have a PHI node
 622   // that only has entries for itself.  In this case, there is no entry into the
 623   // loop, so kill the PHI.
 624   //
 625   if (InVal == 0) InVal = Constant::getNullValue(PN.getType());
 626
 627   // All of the incoming values are the same, replace the PHI node now.
 628   return ReplaceInstUsesWith(PN, InVal);
 629 }
 630
 631
 632 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst &GEP) {
 633   // Is it 'getelementptr %P, uint 0'  or 'getelementptr %P'
 634   // If so, eliminate the noop.
 635   if ((GEP.getNumOperands() == 2 &&
 636        GEP.getOperand(1) == Constant::getNullValue(Type::UIntTy)) ||
 637       GEP.getNumOperands() == 1)
 638     return ReplaceInstUsesWith(GEP, GEP.getOperand(0));
 639
 640   // Combine Indices - If the source pointer to this getelementptr instruction
 641   // is a getelementptr instruction, combine the indices of the two
 642   // getelementptr instructions into a single instruction.
 643   //
 644   if (GetElementPtrInst *Src = dyn_cast<GetElementPtrInst>(GEP.getOperand(0))) {
 645     std::vector<Value *> Indices;
 646
 647     // Can we combine the two pointer arithmetics offsets?
 648     if (Src->getNumOperands() == 2 && isa<Constant>(Src->getOperand(1)) &&
 649         isa<Constant>(GEP.getOperand(1))) {
 650       // Replace the index list on this GEP with the index on the getelementptr
 651       Indices.insert(Indices.end(), GEP.idx_begin(), GEP.idx_end());
 652       Indices[0] = *cast<Constant>(Src->getOperand(1)) +
 653                    *cast<Constant>(GEP.getOperand(1));
 654       assert(Indices[0] != 0 && "Constant folding of uint's failed!?");
 655
 656     } else if (*GEP.idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
 657       // Otherwise we can do the fold if the first index of the GEP is a zero
 658       Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 659       Indices.insert(Indices.end(), GEP.idx_begin()+1, GEP.idx_end());
 660     }
 661
 662     if (!Indices.empty())
 663       return new GetElementPtrInst(Src->getOperand(0), Indices, GEP.getName());
 664
 665   } else if (GlobalValue *GV = dyn_cast<GlobalValue>(GEP.getOperand(0))) {
 666     // GEP of global variable.  If all of the indices for this GEP are
 667     // constants, we can promote this to a constexpr instead of an instruction.
 668
 669     // Scan for nonconstants...
 670     std::vector<Constant*> Indices;
 671     User::op_iterator I = GEP.idx_begin(), E = GEP.idx_end();
 672     for (; I != E && isa<Constant>(*I); ++I)
 673       Indices.push_back(cast<Constant>(*I));
 674
 675     if (I == E) {  // If they are all constants...
 676       ConstantExpr *CE =
 677         ConstantExpr::getGetElementPtr(ConstantPointerRef::get(GV), Indices);
 678
 679       // Replace all uses of the GEP with the new constexpr...
 680       return ReplaceInstUsesWith(GEP, CE);
 681     }
 682   }
 683
 684   return 0;
 685 }
 686
 687
 688 bool InstCombiner::runOnFunction(Function &F) {
 689   bool Changed = false;
 690
 691   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
 692
 693   while (!WorkList.empty()) {
 694     Instruction *I = WorkList.back();  // Get an instruction from the worklist
 695     WorkList.pop_back();
 696
 697     // Now that we have an instruction, try combining it to simplify it...
 698     if (Instruction *Result = visit(*I)) {
 699       ++NumCombined;
 700       // Should we replace the old instruction with a new one?
 701       if (Result != I) {
 702         // Instructions can end up on the worklist more than once.  Make sure
 703         // we do not process an instruction that has been deleted.
 704         WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 705                        WorkList.end());
 706
 707         ReplaceInstWithInst(I, Result);
 708       } else {
 709         BasicBlock::iterator II = I;
 710
 711         // If the instruction was modified, it's possible that it is now dead.
 712         // if so, remove it.
 713         if (dceInstruction(II)) {
 714           // Instructions may end up in the worklist more than once.  Erase them
 715           // all.
 716           WorkList.erase(std::remove(WorkList.begin(), WorkList.end(), I),
 717                          WorkList.end());
 718           Result = 0;
 719         }
 720       }
 721
 722       if (Result) {
 723         WorkList.push_back(Result);
 724         AddUsesToWorkList(*Result);
 725       }
 726       Changed = true;
 727     }
 728   }
 729
 730   return Changed;
 731 }
 732
 733 Pass *createInstructionCombiningPass() {
 734   return new InstCombiner();
 735 }