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