1 //===- Expressions.cpp - Expression Analysis Utilities ----------------------=//
3 // This file defines a package of expression analysis utilties:
5 // ClassifyExpression: Analyze an expression to determine the complexity of the
6 // expression, and which other variables it depends on.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/Analysis/Expressions.h"
11 #include "llvm/Optimizations/ConstantHandling.h"
12 #include "llvm/Method.h"
13 #include "llvm/BasicBlock.h"
15 using namespace opt; // Get all the constant handling stuff
16 using namespace analysis;
18 ExprType::ExprType(Value *Val) {
19 if (Val && Val->isConstant() && Val->getType()->isIntegral()) {
20 Offset = (ConstPoolInt*)Val->castConstant();
24 Var = Val; Offset = 0;
25 ExprTy = Var ? Linear : Constant;
30 ExprType::ExprType(const ConstPoolInt *scale, Value *var,
31 const ConstPoolInt *offset) {
32 Scale = scale; Var = var; Offset = offset;
33 ExprTy = Scale ? ScaledLinear : (Var ? Linear : Constant);
34 if (Scale && Scale->equalsInt(0)) { // Simplify 0*Var + const
41 const Type *ExprType::getExprType(const Type *Default) const {
42 if (Offset) return Offset->getType();
43 if (Scale) return Scale->getType();
44 return Var ? Var->getType() : Default;
50 const ConstPoolInt * const Val;
51 const Type * const Ty;
53 inline DefVal(const ConstPoolInt *val, const Type *ty) : Val(val), Ty(ty) {}
55 inline const Type *getType() const { return Ty; }
56 inline const ConstPoolInt *getVal() const { return Val; }
57 inline operator const ConstPoolInt * () const { return Val; }
58 inline const ConstPoolInt *operator->() const { return Val; }
61 struct DefZero : public DefVal {
62 inline DefZero(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {}
63 inline DefZero(const ConstPoolInt *val) : DefVal(val, val->getType()) {}
66 struct DefOne : public DefVal {
67 inline DefOne(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {}
71 static ConstPoolInt *getUnsignedConstant(uint64_t V, const Type *Ty) {
72 if (Ty->isPointerType()) Ty = Type::ULongTy;
73 return Ty->isSigned() ? ConstPoolSInt::get(Ty, V) : ConstPoolUInt::get(Ty, V);
76 // Add - Helper function to make later code simpler. Basically it just adds
77 // the two constants together, inserts the result into the constant pool, and
78 // returns it. Of course life is not simple, and this is no exception. Factors
79 // that complicate matters:
80 // 1. Either argument may be null. If this is the case, the null argument is
81 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
82 // 2. Types get in the way. We want to do arithmetic operations without
83 // regard for the underlying types. It is assumed that the constants are
84 // integral constants. The new value takes the type of the left argument.
85 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
86 // is false, a null return value indicates a value of 0.
88 static const ConstPoolInt *Add(const ConstPoolInt *Arg1,
89 const ConstPoolInt *Arg2, bool DefOne) {
90 assert(Arg1 && Arg2 && "No null arguments should exist now!");
91 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
93 // Actually perform the computation now!
94 ConstPoolVal *Result = *Arg1 + *Arg2;
95 assert(Result && Result->getType() == Arg1->getType() &&
96 "Couldn't perform addition!");
97 ConstPoolInt *ResultI = (ConstPoolInt*)Result;
99 // Check to see if the result is one of the special cases that we want to
101 if (ResultI->equalsInt(DefOne ? 1 : 0))
102 return 0; // Yes it is, simply return null.
107 inline const ConstPoolInt *operator+(const DefZero &L, const DefZero &R) {
108 if (L == 0) return R;
109 if (R == 0) return L;
110 return Add(L, R, false);
113 inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) {
116 return getUnsignedConstant(2, L.getType());
118 return Add(getUnsignedConstant(1, L.getType()), R, true);
120 return Add(L, getUnsignedConstant(1, L.getType()), true);
122 return Add(L, R, true);
126 // Mul - Helper function to make later code simpler. Basically it just
127 // multiplies the two constants together, inserts the result into the constant
128 // pool, and returns it. Of course life is not simple, and this is no
129 // exception. Factors that complicate matters:
130 // 1. Either argument may be null. If this is the case, the null argument is
131 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
132 // 2. Types get in the way. We want to do arithmetic operations without
133 // regard for the underlying types. It is assumed that the constants are
134 // integral constants.
135 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
136 // is false, a null return value indicates a value of 0.
138 inline const ConstPoolInt *Mul(const ConstPoolInt *Arg1,
139 const ConstPoolInt *Arg2, bool DefOne = false) {
140 assert(Arg1 && Arg2 && "No null arguments should exist now!");
141 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
143 // Actually perform the computation now!
144 ConstPoolVal *Result = *Arg1 * *Arg2;
145 assert(Result && Result->getType() == Arg1->getType() &&
146 "Couldn't perform mult!");
147 ConstPoolInt *ResultI = (ConstPoolInt*)Result;
149 // Check to see if the result is one of the special cases that we want to
151 if (ResultI->equalsInt(DefOne ? 1 : 0))
152 return 0; // Yes it is, simply return null.
157 inline const ConstPoolInt *operator*(const DefZero &L, const DefZero &R) {
158 if (L == 0 || R == 0) return 0;
159 return Mul(L, R, false);
161 inline const ConstPoolInt *operator*(const DefOne &L, const DefZero &R) {
162 if (R == 0) return getUnsignedConstant(0, L.getType());
163 if (L == 0) return R->equalsInt(1) ? 0 : R.getVal();
164 return Mul(L, R, false);
166 inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) {
170 // handleAddition - Add two expressions together, creating a new expression that
171 // represents the composite of the two...
173 static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) {
174 const Type *Ty = V->getType();
175 if (Left.ExprTy > Right.ExprTy)
176 swap(Left, Right); // Make left be simpler than right
178 switch (Left.ExprTy) {
179 case ExprType::Constant:
180 return ExprType(Right.Scale, Right.Var,
181 DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty));
182 case ExprType::Linear: // RHS side must be linear or scaled
183 case ExprType::ScaledLinear: // RHS must be scaled
184 if (Left.Var != Right.Var) // Are they the same variables?
185 return ExprType(V); // if not, we don't know anything!
187 return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty),
189 DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty));
191 assert(0 && "Dont' know how to handle this case!");
196 // negate - Negate the value of the specified expression...
198 static inline ExprType negate(const ExprType &E, Value *V) {
199 const Type *Ty = V->getType();
200 const Type *ETy = E.getExprType(Ty);
201 ConstPoolInt *Zero = getUnsignedConstant(0, ETy);
202 ConstPoolInt *One = getUnsignedConstant(1, ETy);
203 ConstPoolInt *NegOne = (ConstPoolInt*)(*Zero - *One);
204 if (NegOne == 0) return V; // Couldn't subtract values...
206 return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var,
207 DefZero(E.Offset, Ty) * NegOne);
211 // ClassifyExpression: Analyze an expression to determine the complexity of the
212 // expression, and which other values it depends on.
214 // Note that this analysis cannot get into infinite loops because it treats PHI
215 // nodes as being an unknown linear expression.
217 ExprType analysis::ClassifyExpression(Value *Expr) {
218 assert(Expr != 0 && "Can't classify a null expression!");
219 switch (Expr->getValueType()) {
220 case Value::InstructionVal: break; // Instruction... hmmm... investigate.
221 case Value::TypeVal: case Value::BasicBlockVal:
222 case Value::MethodVal: case Value::ModuleVal: default:
223 assert(0 && "Unexpected expression type to classify!");
224 case Value::GlobalVal: // Global Variable & Method argument:
225 case Value::MethodArgumentVal: // nothing known, return variable itself
227 case Value::ConstantVal: // Constant value, just return constant
228 ConstPoolVal *CPV = Expr->castConstantAsserting();
229 if (CPV->getType()->isIntegral()) { // It's an integral constant!
230 ConstPoolInt *CPI = (ConstPoolInt*)Expr;
231 return ExprType(CPI->equalsInt(0) ? 0 : CPI);
236 Instruction *I = cast<Instruction>(Expr);
237 const Type *Ty = I->getType();
239 switch (I->getOpcode()) { // Handle each instruction type seperately
240 case Instruction::Add: {
241 ExprType Left (ClassifyExpression(I->getOperand(0)));
242 ExprType Right(ClassifyExpression(I->getOperand(1)));
243 return handleAddition(Left, Right, I);
244 } // end case Instruction::Add
246 case Instruction::Sub: {
247 ExprType Left (ClassifyExpression(I->getOperand(0)));
248 ExprType Right(ClassifyExpression(I->getOperand(1)));
249 return handleAddition(Left, negate(Right, I), I);
250 } // end case Instruction::Sub
252 case Instruction::Shl: {
253 ExprType Right(ClassifyExpression(I->getOperand(1)));
254 if (Right.ExprTy != ExprType::Constant) break;
255 ExprType Left(ClassifyExpression(I->getOperand(0)));
256 if (Right.Offset == 0) return Left; // shl x, 0 = x
257 assert(Right.Offset->getType() == Type::UByteTy &&
258 "Shift amount must always be a unsigned byte!");
259 uint64_t ShiftAmount = ((ConstPoolUInt*)Right.Offset)->getValue();
260 ConstPoolInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty);
262 return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var,
263 DefZero(Left.Offset, Ty) * Multiplier);
264 } // end case Instruction::Shl
266 case Instruction::Mul: {
267 ExprType Left (ClassifyExpression(I->getOperand(0)));
268 ExprType Right(ClassifyExpression(I->getOperand(1)));
269 if (Left.ExprTy > Right.ExprTy)
270 swap(Left, Right); // Make left be simpler than right
272 if (Left.ExprTy != ExprType::Constant) // RHS must be > constant
273 return I; // Quadratic eqn! :(
275 const ConstPoolInt *Offs = Left.Offset;
276 if (Offs == 0) return ExprType();
277 return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var,
278 DefZero(Right.Offset, Ty) * Offs);
279 } // end case Instruction::Mul
281 case Instruction::Cast: {
282 ExprType Src(ClassifyExpression(I->getOperand(0)));
283 if (Src.ExprTy != ExprType::Constant)
285 const ConstPoolInt *Offs = Src.Offset;
286 if (Offs == 0) return ExprType();
288 const Type *DestTy = I->getType();
289 if (DestTy->isPointerType())
290 DestTy = Type::ULongTy; // Pointer types are represented as ulong
292 assert(DestTy->isIntegral() && "Can only handle integral types!");
294 const ConstPoolVal *CPV =ConstRules::get(*Offs)->castTo(Offs, DestTy);
296 assert(CPV->getType()->isIntegral() && "Must have an integral type!");
297 return (ConstPoolInt*)CPV;
298 } // end case Instruction::Cast
299 // TODO: Handle SUB, SHR?
303 // Otherwise, I don't know anything about this value!