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