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