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
|
//===- 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/Transforms/Scalar/ConstantHandling.h"
#include "llvm/Method.h"
#include "llvm/iMemory.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))) {
if (I->getOpcode() == Instruction::Add) {
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;
}
}
}
}
}
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;
}
bool InstructionCombining::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);
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;
}
bool InstructionCombining::doit(Method *M) {
// Start the worklist out with all of the instructions in the method 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;
}
|
