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