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;
19 const ConstPoolInt * const Val;
20 const Type * const Ty;
22 inline DefVal(const ConstPoolInt *val, const Type *ty) : Val(val), Ty(ty) {}
24 inline const Type *getType() const { return Ty; }
25 inline const ConstPoolInt *getVal() const { return Val; }
26 inline operator const ConstPoolInt * () const { return Val; }
27 inline const ConstPoolInt *operator->() const { return Val; }
30 struct DefZero : public DefVal {
31 inline DefZero(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {}
32 inline DefZero(const ConstPoolInt *val) : DefVal(val, val->getType()) {}
35 struct DefOne : public DefVal {
36 inline DefOne(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {}
40 // getIntegralConstant - Wrapper around the ConstPoolInt member of the same
41 // name. This method first checks to see if the desired constant is already in
42 // the constant pool. If it is, it is quickly recycled, otherwise a new one
43 // is allocated and added to the constant pool.
45 static ConstPoolInt *getIntegralConstant(unsigned char V, const Type *Ty) {
46 return ConstPoolInt::get(Ty, V);
49 static ConstPoolInt *getUnsignedConstant(uint64_t V, const Type *Ty) {
50 if (Ty->isPointerType()) Ty = Type::ULongTy;
52 return Ty->isSigned() ? ConstPoolSInt::get(Ty, V) : ConstPoolUInt::get(Ty, V);
55 // Add - Helper function to make later code simpler. Basically it just adds
56 // the two constants together, inserts the result into the constant pool, and
57 // returns it. Of course life is not simple, and this is no exception. Factors
58 // that complicate matters:
59 // 1. Either argument may be null. If this is the case, the null argument is
60 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
61 // 2. Types get in the way. We want to do arithmetic operations without
62 // regard for the underlying types. It is assumed that the constants are
63 // integral constants. The new value takes the type of the left argument.
64 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
65 // is false, a null return value indicates a value of 0.
67 static const ConstPoolInt *Add(const ConstPoolInt *Arg1,
68 const ConstPoolInt *Arg2, bool DefOne) {
69 assert(Arg1 && Arg2 && "No null arguments should exist now!");
70 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
72 // Actually perform the computation now!
73 ConstPoolVal *Result = *Arg1 + *Arg2;
74 assert(Result && Result->getType() == Arg1->getType() &&
75 "Couldn't perform addition!");
76 ConstPoolInt *ResultI = (ConstPoolInt*)Result;
78 // Check to see if the result is one of the special cases that we want to
80 if (ResultI->equalsInt(DefOne ? 1 : 0)) {
81 // Yes it is, simply delete the constant and return null.
89 inline const ConstPoolInt *operator+(const DefZero &L, const DefZero &R) {
92 return Add(L, R, false);
95 inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) {
98 return getIntegralConstant(2, L.getType());
100 return Add(getIntegralConstant(1, L.getType()), R, true);
102 return Add(L, getIntegralConstant(1, L.getType()), true);
104 return Add(L, R, true);
108 // Mul - Helper function to make later code simpler. Basically it just
109 // multiplies the two constants together, inserts the result into the constant
110 // pool, and returns it. Of course life is not simple, and this is no
111 // exception. Factors that complicate matters:
112 // 1. Either argument may be null. If this is the case, the null argument is
113 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
114 // 2. Types get in the way. We want to do arithmetic operations without
115 // regard for the underlying types. It is assumed that the constants are
116 // integral constants.
117 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
118 // is false, a null return value indicates a value of 0.
120 inline const ConstPoolInt *Mul(const ConstPoolInt *Arg1,
121 const ConstPoolInt *Arg2, bool DefOne = false) {
122 assert(Arg1 && Arg2 && "No null arguments should exist now!");
123 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
125 // Actually perform the computation now!
126 ConstPoolVal *Result = *Arg1 * *Arg2;
127 assert(Result && Result->getType() == Arg1->getType() &&
128 "Couldn't perform mult!");
129 ConstPoolInt *ResultI = (ConstPoolInt*)Result;
131 // Check to see if the result is one of the special cases that we want to
133 if (ResultI->equalsInt(DefOne ? 1 : 0)) {
134 // Yes it is, simply delete the constant and return null.
142 inline const ConstPoolInt *operator*(const DefZero &L, const DefZero &R) {
143 if (L == 0 || R == 0) return 0;
144 return Mul(L, R, false);
146 inline const ConstPoolInt *operator*(const DefOne &L, const DefZero &R) {
147 if (R == 0) return getIntegralConstant(0, L.getType());
148 if (L == 0) return R->equalsInt(1) ? 0 : R.getVal();
149 return Mul(L, R, false);
151 inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) {
157 // ClassifyExpression: Analyze an expression to determine the complexity of the
158 // expression, and which other values it depends on.
160 // Note that this analysis cannot get into infinite loops because it treats PHI
161 // nodes as being an unknown linear expression.
163 ExprType analysis::ClassifyExpression(Value *Expr) {
164 assert(Expr != 0 && "Can't classify a null expression!");
165 switch (Expr->getValueType()) {
166 case Value::InstructionVal: break; // Instruction... hmmm... investigate.
167 case Value::TypeVal: case Value::BasicBlockVal:
168 case Value::MethodVal: case Value::ModuleVal:
169 assert(0 && "Unexpected expression type to classify!");
170 case Value::MethodArgumentVal: // Method arg: nothing known, return var
172 case Value::ConstantVal: // Constant value, just return constant
173 ConstPoolVal *CPV = Expr->castConstantAsserting();
174 if (CPV->getType()->isIntegral()) { // It's an integral constant!
175 ConstPoolInt *CPI = (ConstPoolInt*)Expr;
176 return ExprType(CPI->equalsInt(0) ? 0 : (ConstPoolInt*)Expr);
181 Instruction *I = Expr->castInstructionAsserting();
182 const Type *Ty = I->getType();
184 switch (I->getOpcode()) { // Handle each instruction type seperately
185 case Instruction::Add: {
186 ExprType Left (ClassifyExpression(I->getOperand(0)));
187 ExprType Right(ClassifyExpression(I->getOperand(1)));
188 if (Left.ExprTy > Right.ExprTy)
189 swap(Left, Right); // Make left be simpler than right
191 switch (Left.ExprTy) {
192 case ExprType::Constant:
193 return ExprType(Right.Scale, Right.Var,
194 DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty));
195 case ExprType::Linear: // RHS side must be linear or scaled
196 case ExprType::ScaledLinear: // RHS must be scaled
197 if (Left.Var != Right.Var) // Are they the same variables?
198 return ExprType(I); // if not, we don't know anything!
200 return ExprType( DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty),
202 DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty));
204 } // end case Instruction::Add
206 case Instruction::Shl: {
207 ExprType Right(ClassifyExpression(I->getOperand(1)));
208 if (Right.ExprTy != ExprType::Constant) break;
209 ExprType Left(ClassifyExpression(I->getOperand(0)));
210 if (Right.Offset == 0) return Left; // shl x, 0 = x
211 assert(Right.Offset->getType() == Type::UByteTy &&
212 "Shift amount must always be a unsigned byte!");
213 uint64_t ShiftAmount = ((ConstPoolUInt*)Right.Offset)->getValue();
214 ConstPoolInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty);
216 return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var,
217 DefZero(Left.Offset, Ty) * Multiplier);
218 } // end case Instruction::Shl
220 case Instruction::Mul: {
221 ExprType Left (ClassifyExpression(I->getOperand(0)));
222 ExprType Right(ClassifyExpression(I->getOperand(1)));
223 if (Left.ExprTy > Right.ExprTy)
224 swap(Left, Right); // Make left be simpler than right
226 if (Left.ExprTy != ExprType::Constant) // RHS must be > constant
227 return I; // Quadratic eqn! :(
229 const ConstPoolInt *Offs = Left.Offset;
230 if (Offs == 0) return ExprType();
231 return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var,
232 DefZero(Right.Offset, Ty) * Offs);
233 } // end case Instruction::Mul
235 case Instruction::Cast: {
236 ExprType Src(ClassifyExpression(I->getOperand(0)));
237 if (Src.ExprTy != ExprType::Constant)
239 const ConstPoolInt *Offs = Src.Offset;
240 if (Offs == 0) return ExprType();
242 if (I->getType()->isPointerType())
243 return Offs; // Pointer types do not lose precision
245 assert(I->getType()->isIntegral() && "Can only handle integral types!");
247 const ConstPoolVal *CPV =ConstRules::get(*Offs)->castTo(Offs, I->getType());
249 assert(CPV->getType()->isIntegral() && "Must have an integral type!");
250 return (ConstPoolInt*)CPV;
251 } // end case Instruction::Cast
252 // TODO: Handle SUB, SHR?
256 // Otherwise, I don't know anything about this value!