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
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
|
//===- Expressions.cpp - Expression Analysis Utilities ----------------------=//
//
// This file defines a package of expression analysis utilties:
//
// ClassifyExpression: Analyze an expression to determine the complexity of the
// expression, and which other variables it depends on.
//
//===----------------------------------------------------------------------===//
#include "llvm/Analysis/Expressions.h"
#include "llvm/Optimizations/ConstantHandling.h"
#include "llvm/ConstantPool.h"
#include "llvm/Method.h"
#include "llvm/BasicBlock.h"
using namespace opt; // Get all the constant handling stuff
// getIntegralConstant - Wrapper around the ConstPoolInt member of the same
// name. This method first checks to see if the desired constant is already in
// the constant pool. If it is, it is quickly recycled, otherwise a new one
// is allocated and added to the constant pool.
//
static ConstPoolInt *getIntegralConstant(ConstantPool &CP, unsigned char V,
const Type *Ty) {
// FIXME: Lookup prexisting constant in table!
ConstPoolInt *CPI = ConstPoolInt::get(Ty, V);
CP.insert(CPI);
return CPI;
}
static ConstPoolUInt *getUnsignedConstant(ConstantPool &CP, uint64_t V) {
// FIXME: Lookup prexisting constant in table!
ConstPoolUInt *CPUI = new ConstPoolUInt(Type::ULongTy, V);
CP.insert(CPUI);
return CPUI;
}
// Add - Helper function to make later code simpler. Basically it just adds
// the two constants together, inserts the result into the constant pool, and
// returns it. Of course life is not simple, and this is no exception. Factors
// that complicate matters:
// 1. Either argument may be null. If this is the case, the null argument is
// treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
// 2. Types get in the way. We want to do arithmetic operations without
// regard for the underlying types. It is assumed that the constants are
// integral constants. The new value takes the type of the left argument.
// 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
// is false, a null return value indicates a value of 0.
//
inline const ConstPoolInt *Add(ConstantPool &CP, const ConstPoolInt *Arg1,
const ConstPoolInt *Arg2, bool DefOne = false) {
if (DefOne == false) { // Handle degenerate cases first...
if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0
if (Arg2 == 0) return Arg1;
} else { // These aren't degenerate... :(
if (Arg1 == 0 && Arg2 == 0) return getIntegralConstant(CP, 2, Type::UIntTy);
if (Arg1 == 0) Arg1 = getIntegralConstant(CP, 1, Arg2->getType());
if (Arg2 == 0) Arg2 = getIntegralConstant(CP, 1, Arg2->getType());
}
assert(Arg1 && Arg2 && "No null arguments should exist now!");
// FIXME: Make types compatible!
// Actually perform the computation now!
ConstPoolVal *Result = *Arg1 + *Arg2;
assert(Result && Result->getType()->isIntegral() && "Couldn't perform add!");
ConstPoolInt *ResultI = (ConstPoolInt*)Result;
// Check to see if the result is one of the special cases that we want to
// recognize...
if (ResultI->equals(DefOne ? 1 : 0)) {
// Yes it is, simply delete the constant and return null.
delete ResultI;
return 0;
}
CP.insert(ResultI);
return ResultI;
}
ExprAnalysisResult ExprAnalysisResult::operator+(const ConstPoolInt *NewOff) {
if (NewOff == 0) return *this; // No change!
ConstantPool &CP = (ConstantPool&)NewOff->getParent()->getConstantPool();
return ExprAnalysisResult(Scale, Var, Add(CP, Offset, NewOff));
}
// Mult - Helper function to make later code simpler. Basically it just
// multiplies the two constants together, inserts the result into the constant
// pool, and returns it. Of course life is not simple, and this is no
// exception. Factors that complicate matters:
// 1. Either argument may be null. If this is the case, the null argument is
// treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
// 2. Types get in the way. We want to do arithmetic operations without
// regard for the underlying types. It is assumed that the constants are
// integral constants.
// 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
// is false, a null return value indicates a value of 0.
//
inline const ConstPoolInt *Mult(ConstantPool &CP, const ConstPoolInt *Arg1,
const ConstPoolInt *Arg2, bool DefOne = false) {
if (DefOne == false) { // Handle degenerate cases first...
if (Arg1 == 0 || Arg2 == 0) return 0; // 0 * x == 0
} else { // These aren't degenerate... :(
if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0
if (Arg2 == 0) return Arg1;
}
assert(Arg1 && Arg2 && "No null arguments should exist now!");
// FIXME: Make types compatible!
// Actually perform the computation now!
ConstPoolVal *Result = *Arg1 * *Arg2;
assert(Result && Result->getType()->isIntegral() && "Couldn't perform mult!");
ConstPoolInt *ResultI = (ConstPoolInt*)Result;
// Check to see if the result is one of the special cases that we want to
// recognize...
if (ResultI->equals(DefOne ? 1 : 0)) {
// Yes it is, simply delete the constant and return null.
delete ResultI;
return 0;
}
CP.insert(ResultI);
return ResultI;
}
// ClassifyExpression: Analyze an expression to determine the complexity of the
// expression, and which other values it depends on.
//
// Note that this analysis cannot get into infinite loops because it treats PHI
// nodes as being an unknown linear expression.
//
ExprAnalysisResult ClassifyExpression(Value *Expr) {
assert(Expr != 0 && "Can't classify a null expression!");
switch (Expr->getValueType()) {
case Value::InstructionVal: break; // Instruction... hmmm... investigate.
case Value::TypeVal: case Value::BasicBlockVal:
case Value::MethodVal: case Value::ModuleVal:
assert(0 && "Unexpected expression type to classify!");
case Value::MethodArgumentVal: // Method arg: nothing known, return var
return Expr;
case Value::ConstantVal: // Constant value, just return constant
ConstPoolVal *CPV = Expr->castConstantAsserting();
if (CPV->getType()->isIntegral()) { // It's an integral constant!
ConstPoolInt *CPI = (ConstPoolInt*)Expr;
return ExprAnalysisResult(CPI->equals(0) ? 0 : (ConstPoolInt*)Expr);
}
return Expr;
}
Instruction *I = Expr->castInstructionAsserting();
ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
switch (I->getOpcode()) { // Handle each instruction type seperately
case Instruction::Add: {
ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0)));
ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1)));
if (LeftTy.ExprType > RightTy.ExprType)
swap(LeftTy, RightTy); // Make left be simpler than right
switch (LeftTy.ExprType) {
case ExprAnalysisResult::Constant:
return RightTy + LeftTy.Offset;
case ExprAnalysisResult::Linear: // RHS side must be linear or scaled
case ExprAnalysisResult::ScaledLinear: // RHS must be scaled
if (LeftTy.Var != RightTy.Var) // Are they the same variables?
return ExprAnalysisResult(I); // if not, we don't know anything!
const ConstPoolInt *NewScale = Add(CP, LeftTy.Scale, RightTy.Scale,true);
const ConstPoolInt *NewOffset = Add(CP, LeftTy.Offset, RightTy.Offset);
return ExprAnalysisResult(NewScale, LeftTy.Var, NewOffset);
}
} // end case Instruction::Add
case Instruction::Shl: {
ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1)));
if (RightTy.ExprType != ExprAnalysisResult::Constant)
break; // TODO: Can get some info if it's (<unsigned> X + <offset>)
ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0)));
if (RightTy.Offset == 0) return LeftTy; // shl x, 0 = x
assert(RightTy.Offset->getType() == Type::UByteTy &&
"Shift amount must always be a unsigned byte!");
uint64_t ShiftAmount = ((ConstPoolUInt*)RightTy.Offset)->getValue();
ConstPoolUInt *Multiplier = getUnsignedConstant(CP, 1ULL << ShiftAmount);
return ExprAnalysisResult(Mult(CP, LeftTy.Scale, Multiplier, true),
LeftTy.Var,
Mult(CP, LeftTy.Offset, Multiplier));
} // end case Instruction::Shl
// TODO: Handle CAST, SUB, MULT (at least!)
} // end switch
// Otherwise, I don't know anything about this value!
return ExprAnalysisResult(I);
}
|
