1 //===- InstructionCombining.cpp - Combine multiple instructions -------------=//
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.
7 // This pass combines things like:
13 // This is a simple worklist driven algorithm.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Transforms/Scalar/InstructionCombining.h"
18 #include "../TransformInternals.h"
19 #include "llvm/Optimizations/ConstantHandling.h"
20 #include "llvm/Method.h"
21 #include "llvm/iMemory.h"
25 static Instruction *CombineBinOp(BinaryOperator *I) {
28 // First thing we do is make sure that this instruction has a constant on the
29 // right hand side if it has any constant arguments.
31 if (isa<Constant>(I->getOperand(0)) && !isa<Constant>(I->getOperand(1)))
32 if (!I->swapOperands())
35 bool LocalChange = true;
38 Value *Op1 = I->getOperand(0);
39 if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(1))) {
40 if (I->getOpcode() == Instruction::Add) {
41 if (Instruction *IOp1 = dyn_cast<Instruction>(Op1)) {
42 if (IOp1->getOpcode() == Instruction::Add &&
43 isa<Constant>(IOp1->getOperand(1))) {
50 // Constant fold both constants...
51 Constant *Val = *Op2 + *cast<Constant>(IOp1->getOperand(1));
54 I->setOperand(0, IOp1->getOperand(0));
55 I->setOperand(1, Val);
63 Changed |= LocalChange;
66 if (!Changed) return 0;
70 // Combine Indices - If the source pointer to this mem access instruction is a
71 // getelementptr instruction, combine the indices of the GEP into this
74 static Instruction *CombineIndicies(MemAccessInst *MAI) {
75 GetElementPtrInst *Src =
76 dyn_cast<GetElementPtrInst>(MAI->getPointerOperand());
79 vector<Value *> Indices;
81 // Only special case we have to watch out for is pointer arithmetic on the
83 unsigned FirstIdx = MAI->getFirstIndexOperandNumber();
84 if (FirstIdx == MAI->getNumOperands() ||
85 (FirstIdx == MAI->getNumOperands()-1 &&
86 MAI->getOperand(FirstIdx) == ConstantUInt::get(Type::UIntTy, 0))) {
87 // Replace the index list on this MAI with the index on the getelementptr
88 Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
89 } else if (*MAI->idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
90 // Otherwise we can do the fold if the first index of the GEP is a zero
91 Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
92 Indices.insert(Indices.end(), MAI->idx_begin()+1, MAI->idx_end());
95 if (Indices.empty()) return 0; // Can't do the fold?
97 switch (MAI->getOpcode()) {
98 case Instruction::GetElementPtr:
99 return new GetElementPtrInst(Src->getOperand(0), Indices, MAI->getName());
100 case Instruction::Load:
101 return new LoadInst(Src->getOperand(0), Indices, MAI->getName());
102 case Instruction::Store:
103 return new StoreInst(MAI->getOperand(0), Src->getOperand(0),
104 Indices, MAI->getName());
106 assert(0 && "Unknown memaccessinst!");
113 bool InstructionCombining::CombineInstruction(Instruction *I) {
114 Instruction *Result = 0;
115 if (BinaryOperator *BOP = dyn_cast<BinaryOperator>(I))
116 Result = CombineBinOp(BOP);
117 else if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(I))
118 Result = CombineIndicies(MAI);
120 if (!Result) return false;
121 if (Result == I) return true;
123 // If we get to here, we are to replace I with Result.
124 ReplaceInstWithInst(I, Result);
129 bool InstructionCombining::doit(Method *M) {
130 // Start the worklist out with all of the instructions in the method in it.
131 vector<Instruction*> WorkList(M->inst_begin(), M->inst_end());
133 while (!WorkList.empty()) {
134 Instruction *I = WorkList.back(); // Get an instruction from the worklist
137 // Now that we have an instruction, try combining it to simplify it...
138 if (CombineInstruction(I)) {
139 // The instruction was simplified, add all users of the instruction to
140 // the work lists because they might get more simplified now...
142 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
144 if (Instruction *User = dyn_cast<Instruction>(*UI))
145 WorkList.push_back(User);