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.
   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 *visitGetElementPtrInst(GetElementPtrInst *GEP);
  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     return !I->swapOperands();
  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     } else if (I->getType()->isIntegral() &&
 151                cast<ConstantInt>(Op2)->equalsInt(2)) {
 152       // Convert 'mul int %X, 2' to 'add int %X, %X'
 153       return BinaryOperator::create(Instruction::Add, Op1, Op1, I->getName());
 154
 155     } else if (Op2->isNullValue()) {
 156       // Eliminate 'mul int %X, 0'
 157       AddUsesToWorkList(I);         // Add all modified instrs to worklist
 158       I->replaceAllUsesWith(Op2);   // Set this value to zero directly
 159       return I;
 160     }
 161   }
 162
 163   return Changed ? I : 0;
 164 }
 165
 166
 167 // isEliminableCastOfCast - Return true if it is valid to eliminate the CI
 168 // instruction.
 169 //
 170 static inline bool isEliminableCastOfCast(const CastInst *CI,
 171                                           const CastInst *CSrc) {
 172   assert(CI->getOperand(0) == CSrc);
 173   const Type *SrcTy = CSrc->getOperand(0)->getType();
 174   const Type *MidTy = CSrc->getType();
 175   const Type *DstTy = CI->getType();
 176
 177   // It is legal to eliminate the instruction if casting A->B->A
 178   if (SrcTy == DstTy) return true;
 179
 180   // Allow free casting and conversion of sizes as long as the sign doesn't
 181   // change...
 182   if (SrcTy->isSigned() == MidTy->isSigned() &&
 183       MidTy->isSigned() == DstTy->isSigned())
 184     return true;
 185
 186   // Otherwise, we cannot succeed.  Specifically we do not want to allow things
 187   // like:  short -> ushort -> uint, because this can create wrong results if
 188   // the input short is negative!
 189   //
 190   return false;
 191 }
 192
 193
 194 // CastInst simplification
 195 //
 196 Instruction *InstCombiner::visitCastInst(CastInst *CI) {
 197   // If the user is casting a value to the same type, eliminate this cast
 198   // instruction...
 199   if (CI->getType() == CI->getOperand(0)->getType() && !CI->use_empty()) {
 200     AddUsesToWorkList(CI);         // Add all modified instrs to worklist
 201     CI->replaceAllUsesWith(CI->getOperand(0));
 202     return CI;
 203   }
 204
 205
 206   // If casting the result of another cast instruction, try to eliminate this
 207   // one!
 208   //
 209   if (CastInst *CSrc = dyn_cast<CastInst>(CI->getOperand(0)))
 210     if (isEliminableCastOfCast(CI, CSrc)) {
 211       // This instruction now refers directly to the cast's src operand.  This
 212       // has a good chance of making CSrc dead.
 213       CI->setOperand(0, CSrc->getOperand(0));
 214       return CI;
 215     }
 216
 217   return 0;
 218 }
 219
 220
 221
 222 Instruction *InstCombiner::visitGetElementPtrInst(GetElementPtrInst *GEP) {
 223   // Is it getelementptr %P, uint 0
 224   // If so, elminate the noop.
 225   if (GEP->getNumOperands() == 2 && !GEP->use_empty() &&
 226       GEP->getOperand(1) == Constant::getNullValue(Type::UIntTy)) {
 227     AddUsesToWorkList(GEP);         // Add all modified instrs to worklist
 228     GEP->replaceAllUsesWith(GEP->getOperand(0));
 229     return GEP;
 230   }
 231
 232   return visitMemAccessInst(GEP);
 233 }
 234
 235
 236 // Combine Indices - If the source pointer to this mem access instruction is a
 237 // getelementptr instruction, combine the indices of the GEP into this
 238 // instruction
 239 //
 240 Instruction *InstCombiner::visitMemAccessInst(MemAccessInst *MAI) {
 241   GetElementPtrInst *Src =
 242     dyn_cast<GetElementPtrInst>(MAI->getPointerOperand());
 243   if (!Src) return 0;
 244
 245   std::vector<Value *> Indices;
 246
 247   // Only special case we have to watch out for is pointer arithmetic on the
 248   // 0th index of MAI.
 249   unsigned FirstIdx = MAI->getFirstIndexOperandNumber();
 250   if (FirstIdx == MAI->getNumOperands() ||
 251       (FirstIdx == MAI->getNumOperands()-1 &&
 252        MAI->getOperand(FirstIdx) == ConstantUInt::get(Type::UIntTy, 0))) {
 253     // Replace the index list on this MAI with the index on the getelementptr
 254     Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 255   } else if (*MAI->idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
 256     // Otherwise we can do the fold if the first index of the GEP is a zero
 257     Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
 258     Indices.insert(Indices.end(), MAI->idx_begin()+1, MAI->idx_end());
 259   }
 260
 261   if (Indices.empty()) return 0;  // Can't do the fold?
 262
 263   switch (MAI->getOpcode()) {
 264   case Instruction::GetElementPtr:
 265     return new GetElementPtrInst(Src->getOperand(0), Indices, MAI->getName());
 266   case Instruction::Load:
 267     return new LoadInst(Src->getOperand(0), Indices, MAI->getName());
 268   case Instruction::Store:
 269     return new StoreInst(MAI->getOperand(0), Src->getOperand(0), Indices);
 270   default:
 271     assert(0 && "Unknown memaccessinst!");
 272     break;
 273   }
 274   abort();
 275   return 0;
 276 }
 277
 278
 279 bool InstCombiner::runOnFunction(Function *F) {
 280   bool Changed = false;
 281
 282   WorkList.insert(WorkList.end(), inst_begin(F), inst_end(F));
 283
 284   while (!WorkList.empty()) {
 285     Instruction *I = WorkList.back();  // Get an instruction from the worklist
 286     WorkList.pop_back();
 287
 288     // Now that we have an instruction, try combining it to simplify it...
 289     Instruction *Result = visit(I);
 290     if (Result) {
 291       // Should we replace the old instruction with a new one?
 292       if (Result != I)
 293         ReplaceInstWithInst(I, Result);
 294
 295       WorkList.push_back(Result);
 296       AddUsesToWorkList(Result);
 297       Changed = true;
 298     }
 299   }
 300
 301   return Changed;
 302 }
 303
 304 Pass *createInstructionCombiningPass() {
 305   return new InstCombiner();
 306 }