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 DCE pass is useful.
   6 //
   7 // This pass combines things like:
   8 //    %Y = add int 1, %X
   9 //    %Z = add int 1, %Y
  10 // into:
  11 //    %Z = add int 2, %X
  12 //
  13 // This is a simple worklist driven algorithm.
  14 //
  15 //===----------------------------------------------------------------------===//
  16
  17 #include "llvm/Transforms/Scalar/InstructionCombining.h"
  18 #include "llvm/ConstantHandling.h"
  19 #include "llvm/Function.h"
  20 #include "llvm/iMemory.h"
  21 #include "llvm/iOther.h"
  22 #include "llvm/iOperators.h"
  23 #include "llvm/Pass.h"
  24 #include "llvm/Support/InstIterator.h"
  25 #include "llvm/Support/InstVisitor.h"
  26 #include "../TransformInternals.h"
  27
  28
  29 namespace {
  30   class InstCombiner : public MethodPass,
  31                        public InstVisitor<InstCombiner, Instruction*> {
  32     // Worklist of all of the instructions that need to be simplified.
  33     std::vector<Instruction*> WorkList;
  34
  35     void AddUsesToWorkList(Instruction *I) {
  36       // The instruction was simplified, add all users of the instruction to
  37       // the work lists because they might get more simplified now...
  38       //
  39       for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
  40            UI != UE; ++UI)
  41         WorkList.push_back(cast<Instruction>(*UI));
  42     }
  43
  44   public:
  45
  46
  47     virtual bool runOnMethod(Function *F);
  48
  49     // Visitation implementation - Implement instruction combining for different
  50     // instruction types.  The semantics are as follows:
  51     // Return Value:
  52     //    null        - No change was made
  53     //     I          - Change was made, I is still valid
  54     //   otherwise    - Change was made, replace I with returned instruction
  55     //
  56
  57     Instruction *visitAdd(BinaryOperator *I);
  58     Instruction *visitSub(BinaryOperator *I);
  59     Instruction *visitMul(BinaryOperator *I);
  60     Instruction *visitCastInst(CastInst *CI);
  61     Instruction *visitMemAccessInst(MemAccessInst *MAI);
  62
  63     // visitInstruction - Specify what to return for unhandled instructions...
  64     Instruction *visitInstruction(Instruction *I) { return 0; }
  65   };
  66 }
  67
  68
  69
  70 // Make sure that this instruction has a constant on the right hand side if it
  71 // has any constant arguments.  If not, fix it an return true.
  72 //
  73 static bool SimplifyBinOp(BinaryOperator *I) {
  74   if (isa<Constant>(I->getOperand(0)) && !isa<Constant>(I->getOperand(1)))
  75     if (!I->swapOperands())
  76       return true;
  77   return false;
  78 }
  79
  80 Instruction *InstCombiner::visitAdd(BinaryOperator *I) {
  81   if (I->use_empty()) return 0;       // Don't fix dead add instructions...
  82   bool Changed = SimplifyBinOp(I);
  83   Value *Op1 = I->getOperand(0);
  84
  85   // Simplify add instructions with a constant RHS...
  86   if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(1))) {
  87     // Eliminate 'add int %X, 0'
  88     if (I->getType()->isIntegral() && Op2->isNullValue()) {
  89       AddUsesToWorkList(I);         // Add all modified instrs to worklist
  90       I->replaceAllUsesWith(Op1);
  91       return I;
  92     }
  93
  94     if (BinaryOperator *IOp1 = dyn_cast<BinaryOperator>(Op1)) {
  95       Changed |= SimplifyBinOp(IOp1);
  96
  97       if (IOp1->getOpcode() == Instruction::Add &&
  98           isa<Constant>(IOp1->getOperand(1))) {
  99         // Fold:
 100         //    %Y = add int %X, 1
 101         //    %Z = add int %Y, 1
 102         // into:
 103         //    %Z = add int %X, 2
 104         //
 105         if (Constant *Val = *Op2 + *cast<Constant>(IOp1->getOperand(1))) {
 106           I->setOperand(0, IOp1->getOperand(0));
 107           I->setOperand(1, Val);
 108           return I;
 109         }
 110       }
 111     }
 112   }
 113
 114   return Changed ? I : 0;
 115 }
 116
 117 Instruction *InstCombiner::visitSub(BinaryOperator *I) {
 118   if (I->use_empty()) return 0;       // Don't fix dead add instructions...
 119   bool Changed = SimplifyBinOp(I);
 120
 121   // If this is a subtract instruction with a constant RHS, convert it to an add
 122   // instruction of a negative constant
 123   //
 124   if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(1)))
 125     // Calculate 0 - RHS
 126     if (Constant *RHS = *Constant::getNullConstant(I->getType()) - *Op2) {
 127       return BinaryOperator::create(Instruction::Add, I->getOperand(0), RHS,
 128                                     I->getName());
 129     }
 130
 131   return Changed ? I : 0;
 132 }
 133
 134 Instruction *InstCombiner::visitMul(BinaryOperator *I) {
 135   if (I->use_empty()) return 0;       // Don't fix dead add instructions...
 136   bool Changed = SimplifyBinOp(I);
 137   Value *Op1 = I->getOperand(0);
 138
 139   // Simplify add instructions with a constant RHS...
 140   if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(1))) {
 141     if (I->getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(1)){
 142       // Eliminate 'mul int %X, 1'
 143       AddUsesToWorkList(I);         // Add all modified instrs to worklist
 144       I->replaceAllUsesWith(Op1);
 145       return I;
 146     }
 147   }
 148
 149   return Changed ? I : 0;
 150 }
 151
 152
 153 // CastInst simplification - If the user is casting a value to the same type,
 154 // eliminate this cast instruction...
 155 //
 156 Instruction *InstCombiner::visitCastInst(CastInst *CI) {
 157   if (CI->getType() == CI->getOperand(0)->getType() && !CI->use_empty()) {
 158     AddUsesToWorkList(CI);         // Add all modified instrs to worklist
 159     CI->replaceAllUsesWith(CI->getOperand(0));
 160     return CI;
 161   }
 162   return 0;
 163 }
 164
 165 // Combine Indices - If the source pointer to this mem access instruction is a
 166 // getelementptr instruction, combine the indices of the GEP into this
 167 // instruction
 168 //
 169 Instruction *InstCombiner::visitMemAccessInst(MemAccessInst *MAI) {
 170   GetElementPtrInst *Src =
 171     dyn_cast<GetElementPtrInst>(MAI->getPointerOperand());
 172   if (!Src) return 0;
 173
 174   std::vector<Value *> Indices;
 175
 176   // Only special case we have to watch out for is pointer arithmetic on the
 177   // 0th index of MAI.
 178   unsigned FirstIdx = MAI->getFirstIndexOperandNumber();
 179   if (FirstIdx == MAI->getNumOperands() ||
 180       (FirstIdx == MAI->getNumOperands()-1 &&
 181        MAI->getOperand(FirstIdx) == ConstantUInt::get(Type::UIntTy, 0))) {
 182     // Replace the index list on this MAI with the index on the getelementptr
 183     Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 184   } else if (*MAI->idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
 185     // Otherwise we can do the fold if the first index of the GEP is a zero
 186     Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 187     Indices.insert(Indices.end(), MAI->idx_begin()+1, MAI->idx_end());
 188   }
 189
 190   if (Indices.empty()) return 0;  // Can't do the fold?
 191
 192   switch (MAI->getOpcode()) {
 193   case Instruction::GetElementPtr:
 194     return new GetElementPtrInst(Src->getOperand(0), Indices, MAI->getName());
 195   case Instruction::Load:
 196     return new LoadInst(Src->getOperand(0), Indices, MAI->getName());
 197   case Instruction::Store:
 198     return new StoreInst(MAI->getOperand(0), Src->getOperand(0), Indices);
 199   default:
 200     assert(0 && "Unknown memaccessinst!");
 201     break;
 202   }
 203   abort();
 204   return 0;
 205 }
 206
 207
 208 bool InstCombiner::runOnMethod(Function *F) {
 209   bool Changed = false;
 210
 211   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
 212
 213   while (!WorkList.empty()) {
 214     Instruction *I = WorkList.back();  // Get an instruction from the worklist
 215     WorkList.pop_back();
 216
 217     // Now that we have an instruction, try combining it to simplify it...
 218     Instruction *Result = visit(I);
 219     if (Result) {
 220       // Should we replace the old instruction with a new one?
 221       if (Result != I)
 222         ReplaceInstWithInst(I, Result);
 223
 224       WorkList.push_back(Result);
 225       AddUsesToWorkList(Result);
 226       Changed = true;
 227     }
 228   }
 229
 230   return Changed;
 231 }
 232
 233 Pass *createInstructionCombiningPass() {
 234   return new InstCombiner();
 235 }