1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
//===- InstructionCombining.cpp - Combine multiple instructions -------------=//
//
// InstructionCombining - Combine instructions to form fewer, simple
// instructions. This pass does not modify the CFG, and has a tendancy to
// make instructions dead, so a subsequent DCE pass is useful.
//
// This pass combines things like:
// %Y = add int 1, %X
// %Z = add int 1, %Y
// into:
// %Z = add int 2, %X
//
// This is a simple worklist driven algorithm.
//
//===----------------------------------------------------------------------===//
#include "llvm/Transforms/Scalar/InstructionCombining.h"
#include "llvm/ConstantHandling.h"
#include "llvm/Function.h"
#include "llvm/iMemory.h"
#include "llvm/iOther.h"
#include "llvm/InstrTypes.h"
#include "llvm/Pass.h"
#include "llvm/Support/InstIterator.h"
#include "../TransformInternals.h"
static Instruction *CombineBinOp(BinaryOperator *I) {
bool Changed = false;
// First thing we do is make sure that this instruction has a constant on the
// right hand side if it has any constant arguments.
//
if (isa<Constant>(I->getOperand(0)) && !isa<Constant>(I->getOperand(1)))
if (!I->swapOperands())
Changed = true;
bool LocalChange = true;
while (LocalChange) {
LocalChange = false;
Value *Op1 = I->getOperand(0);
if (Constant *Op2 = dyn_cast<Constant>(I->getOperand(1))) {
switch (I->getOpcode()) {
case Instruction::Add:
if (I->getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(0)){
// Eliminate 'add int %X, 0'
I->replaceAllUsesWith(Op1); // FIXME: This breaks the worklist
Changed = true;
return I;
}
if (Instruction *IOp1 = dyn_cast<Instruction>(Op1)) {
if (IOp1->getOpcode() == Instruction::Add &&
isa<Constant>(IOp1->getOperand(1))) {
// Fold:
// %Y = add int %X, 1
// %Z = add int %Y, 1
// into:
// %Z = add int %X, 2
//
// Constant fold both constants...
Constant *Val = *Op2 + *cast<Constant>(IOp1->getOperand(1));
if (Val) {
I->setOperand(0, IOp1->getOperand(0));
I->setOperand(1, Val);
LocalChange = true;
break;
}
}
}
break;
case Instruction::Mul:
if (I->getType()->isIntegral() && cast<ConstantInt>(Op2)->equalsInt(1)){
// Eliminate 'mul int %X, 1'
I->replaceAllUsesWith(Op1); // FIXME: This breaks the worklist
LocalChange = true;
break;
}
default:
break;
}
}
Changed |= LocalChange;
}
if (!Changed) return 0;
return I;
}
// Combine Indices - If the source pointer to this mem access instruction is a
// getelementptr instruction, combine the indices of the GEP into this
// instruction
//
static Instruction *CombineIndicies(MemAccessInst *MAI) {
GetElementPtrInst *Src =
dyn_cast<GetElementPtrInst>(MAI->getPointerOperand());
if (!Src) return 0;
std::vector<Value *> Indices;
// Only special case we have to watch out for is pointer arithmetic on the
// 0th index of MAI.
unsigned FirstIdx = MAI->getFirstIndexOperandNumber();
if (FirstIdx == MAI->getNumOperands() ||
(FirstIdx == MAI->getNumOperands()-1 &&
MAI->getOperand(FirstIdx) == ConstantUInt::get(Type::UIntTy, 0))) {
// Replace the index list on this MAI with the index on the getelementptr
Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
} else if (*MAI->idx_begin() == ConstantUInt::get(Type::UIntTy, 0)) {
// Otherwise we can do the fold if the first index of the GEP is a zero
Indices.insert(Indices.end(), Src->idx_begin(), Src->idx_end());
Indices.insert(Indices.end(), MAI->idx_begin()+1, MAI->idx_end());
}
if (Indices.empty()) return 0; // Can't do the fold?
switch (MAI->getOpcode()) {
case Instruction::GetElementPtr:
return new GetElementPtrInst(Src->getOperand(0), Indices, MAI->getName());
case Instruction::Load:
return new LoadInst(Src->getOperand(0), Indices, MAI->getName());
case Instruction::Store:
return new StoreInst(MAI->getOperand(0), Src->getOperand(0),
Indices, MAI->getName());
default:
assert(0 && "Unknown memaccessinst!");
break;
}
abort();
return 0;
}
static bool CombineInstruction(Instruction *I) {
Instruction *Result = 0;
if (BinaryOperator *BOP = dyn_cast<BinaryOperator>(I))
Result = CombineBinOp(BOP);
else if (MemAccessInst *MAI = dyn_cast<MemAccessInst>(I))
Result = CombineIndicies(MAI);
else if (CastInst *CI = dyn_cast<CastInst>(I)) {
if (CI->getType() == CI->getOperand(0)->getType() && !CI->use_empty()) {
CI->replaceAllUsesWith(CI->getOperand(0));
return true;
}
}
if (!Result) return false;
if (Result == I) return true;
// If we get to here, we are to replace I with Result.
ReplaceInstWithInst(I, Result);
return true;
}
static bool doInstCombining(Function *M) {
// Start the worklist out with all of the instructions in the function in it.
std::vector<Instruction*> WorkList(inst_begin(M), inst_end(M));
while (!WorkList.empty()) {
Instruction *I = WorkList.back(); // Get an instruction from the worklist
WorkList.pop_back();
// Now that we have an instruction, try combining it to simplify it...
if (CombineInstruction(I)) {
// The instruction was simplified, add all users of the instruction to
// the work lists because they might get more simplified now...
//
for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
UI != UE; ++UI)
if (Instruction *User = dyn_cast<Instruction>(*UI))
WorkList.push_back(User);
}
}
return false;
}
namespace {
struct InstructionCombining : public MethodPass {
virtual bool runOnMethod(Function *F) { return doInstCombining(F); }
};
}
Pass *createInstructionCombiningPass() {
return new InstructionCombining();
}
|
