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/ConstantHandling.h"
12 #include "llvm/Function.h"
14 ExprType::ExprType(Value *Val) {
16 if (ConstantInt *CPI = dyn_cast<ConstantInt>(Val)) {
24 Var = Val; Offset = 0;
25 ExprTy = Var ? Linear : Constant;
29 ExprType::ExprType(const ConstantInt *scale, Value *var,
30 const ConstantInt *offset) {
31 Scale = var ? scale : 0; Var = var; Offset = offset;
32 ExprTy = Scale ? ScaledLinear : (Var ? Linear : Constant);
33 if (Scale && Scale->isNullValue()) { // Simplify 0*Var + const
40 const Type *ExprType::getExprType(const Type *Default) const {
41 if (Offset) return Offset->getType();
42 if (Scale) return Scale->getType();
43 return Var ? Var->getType() : Default;
49 const ConstantInt * const Val;
50 const Type * const Ty;
52 inline DefVal(const ConstantInt *val, const Type *ty) : Val(val), Ty(ty) {}
54 inline const Type *getType() const { return Ty; }
55 inline const ConstantInt *getVal() const { return Val; }
56 inline operator const ConstantInt * () const { return Val; }
57 inline const ConstantInt *operator->() const { return Val; }
60 struct DefZero : public DefVal {
61 inline DefZero(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {}
62 inline DefZero(const ConstantInt *val) : DefVal(val, val->getType()) {}
65 struct DefOne : public DefVal {
66 inline DefOne(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {}
70 // getUnsignedConstant - Return a constant value of the specified type. If the
71 // constant value is not valid for the specified type, return null. This cannot
72 // happen for values in the range of 0 to 127.
74 static ConstantInt *getUnsignedConstant(uint64_t V, const Type *Ty) {
75 if (isa<PointerType>(Ty)) Ty = Type::ULongTy;
77 // If this value is not a valid unsigned value for this type, return null!
78 if (V > 127 && ((int64_t)V < 0 ||
79 !ConstantSInt::isValueValidForType(Ty, (int64_t)V)))
81 return ConstantSInt::get(Ty, V);
83 // If this value is not a valid unsigned value for this type, return null!
84 if (V > 255 && !ConstantUInt::isValueValidForType(Ty, V))
86 return ConstantUInt::get(Ty, V);
90 // Add - Helper function to make later code simpler. Basically it just adds
91 // the two constants together, inserts the result into the constant pool, and
92 // returns it. Of course life is not simple, and this is no exception. Factors
93 // that complicate matters:
94 // 1. Either argument may be null. If this is the case, the null argument is
95 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
96 // 2. Types get in the way. We want to do arithmetic operations without
97 // regard for the underlying types. It is assumed that the constants are
98 // integral constants. The new value takes the type of the left argument.
99 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
100 // is false, a null return value indicates a value of 0.
102 static const ConstantInt *Add(const ConstantInt *Arg1,
103 const ConstantInt *Arg2, bool DefOne) {
104 assert(Arg1 && Arg2 && "No null arguments should exist now!");
105 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
107 // Actually perform the computation now!
108 Constant *Result = *Arg1 + *Arg2;
109 assert(Result && Result->getType() == Arg1->getType() &&
110 "Couldn't perform addition!");
111 ConstantInt *ResultI = cast<ConstantInt>(Result);
113 // Check to see if the result is one of the special cases that we want to
115 if (ResultI->equalsInt(DefOne ? 1 : 0))
116 return 0; // Yes it is, simply return null.
121 inline const ConstantInt *operator+(const DefZero &L, const DefZero &R) {
122 if (L == 0) return R;
123 if (R == 0) return L;
124 return Add(L, R, false);
127 inline const ConstantInt *operator+(const DefOne &L, const DefOne &R) {
130 return getUnsignedConstant(2, L.getType());
132 return Add(getUnsignedConstant(1, L.getType()), R, true);
134 return Add(L, getUnsignedConstant(1, L.getType()), true);
136 return Add(L, R, true);
140 // Mul - Helper function to make later code simpler. Basically it just
141 // multiplies the two constants together, inserts the result into the constant
142 // pool, and returns it. Of course life is not simple, and this is no
143 // exception. Factors that complicate matters:
144 // 1. Either argument may be null. If this is the case, the null argument is
145 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
146 // 2. Types get in the way. We want to do arithmetic operations without
147 // regard for the underlying types. It is assumed that the constants are
148 // integral constants.
149 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
150 // is false, a null return value indicates a value of 0.
152 inline const ConstantInt *Mul(const ConstantInt *Arg1,
153 const ConstantInt *Arg2, bool DefOne) {
154 assert(Arg1 && Arg2 && "No null arguments should exist now!");
155 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
157 // Actually perform the computation now!
158 Constant *Result = *Arg1 * *Arg2;
159 assert(Result && Result->getType() == Arg1->getType() &&
160 "Couldn't perform multiplication!");
161 ConstantInt *ResultI = cast<ConstantInt>(Result);
163 // Check to see if the result is one of the special cases that we want to
165 if (ResultI->equalsInt(DefOne ? 1 : 0))
166 return 0; // Yes it is, simply return null.
171 inline const ConstantInt *operator*(const DefZero &L, const DefZero &R) {
172 if (L == 0 || R == 0) return 0;
173 return Mul(L, R, false);
175 inline const ConstantInt *operator*(const DefOne &L, const DefZero &R) {
176 if (R == 0) return getUnsignedConstant(0, L.getType());
177 if (L == 0) return R->equalsInt(1) ? 0 : R.getVal();
178 return Mul(L, R, true);
180 inline const ConstantInt *operator*(const DefZero &L, const DefOne &R) {
181 if (L == 0 || R == 0) return L.getVal();
182 return Mul(R, L, false);
185 // handleAddition - Add two expressions together, creating a new expression that
186 // represents the composite of the two...
188 static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) {
189 const Type *Ty = V->getType();
190 if (Left.ExprTy > Right.ExprTy)
191 std::swap(Left, Right); // Make left be simpler than right
193 switch (Left.ExprTy) {
194 case ExprType::Constant:
195 return ExprType(Right.Scale, Right.Var,
196 DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty));
197 case ExprType::Linear: // RHS side must be linear or scaled
198 case ExprType::ScaledLinear: // RHS must be scaled
199 if (Left.Var != Right.Var) // Are they the same variables?
200 return V; // if not, we don't know anything!
202 return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty),
204 DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty));
206 assert(0 && "Dont' know how to handle this case!");
211 // negate - Negate the value of the specified expression...
213 static inline ExprType negate(const ExprType &E, Value *V) {
214 const Type *Ty = V->getType();
215 ConstantInt *Zero = getUnsignedConstant(0, Ty);
216 ConstantInt *One = getUnsignedConstant(1, Ty);
217 ConstantInt *NegOne = cast<ConstantInt>(*Zero - *One);
218 if (NegOne == 0) return V; // Couldn't subtract values...
220 return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var,
221 DefZero(E.Offset, Ty) * NegOne);
225 // ClassifyExpression: Analyze an expression to determine the complexity of the
226 // expression, and which other values it depends on.
228 // Note that this analysis cannot get into infinite loops because it treats PHI
229 // nodes as being an unknown linear expression.
231 ExprType ClassifyExpression(Value *Expr) {
232 assert(Expr != 0 && "Can't classify a null expression!");
233 if (Expr->getType() == Type::FloatTy || Expr->getType() == Type::DoubleTy)
234 return Expr; // FIXME: Can't handle FP expressions
236 switch (Expr->getValueType()) {
237 case Value::InstructionVal: break; // Instruction... hmmm... investigate.
238 case Value::TypeVal: case Value::BasicBlockVal:
239 case Value::FunctionVal: default:
240 //assert(0 && "Unexpected expression type to classify!");
241 std::cerr << "Bizarre thing to expr classify: " << Expr << "\n";
243 case Value::GlobalVariableVal: // Global Variable & Function argument:
244 case Value::ArgumentVal: // nothing known, return variable itself
246 case Value::ConstantVal: // Constant value, just return constant
247 if (ConstantInt *CPI = dyn_cast<ConstantInt>(cast<Constant>(Expr)))
248 // It's an integral constant!
249 return ExprType(CPI->isNullValue() ? 0 : CPI);
253 Instruction *I = cast<Instruction>(Expr);
254 const Type *Ty = I->getType();
256 switch (I->getOpcode()) { // Handle each instruction type seperately
257 case Instruction::Add: {
258 ExprType Left (ClassifyExpression(I->getOperand(0)));
259 ExprType Right(ClassifyExpression(I->getOperand(1)));
260 return handleAddition(Left, Right, I);
261 } // end case Instruction::Add
263 case Instruction::Sub: {
264 ExprType Left (ClassifyExpression(I->getOperand(0)));
265 ExprType Right(ClassifyExpression(I->getOperand(1)));
266 ExprType RightNeg = negate(Right, I);
267 if (RightNeg.Var == I && !RightNeg.Offset && !RightNeg.Scale)
268 return I; // Could not negate value...
269 return handleAddition(Left, RightNeg, I);
270 } // end case Instruction::Sub
272 case Instruction::Shl: {
273 ExprType Right(ClassifyExpression(I->getOperand(1)));
274 if (Right.ExprTy != ExprType::Constant) break;
275 ExprType Left(ClassifyExpression(I->getOperand(0)));
276 if (Right.Offset == 0) return Left; // shl x, 0 = x
277 assert(Right.Offset->getType() == Type::UByteTy &&
278 "Shift amount must always be a unsigned byte!");
279 uint64_t ShiftAmount = ((ConstantUInt*)Right.Offset)->getValue();
280 ConstantInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty);
282 // We don't know how to classify it if they are shifting by more than what
283 // is reasonable. In most cases, the result will be zero, but there is one
284 // class of cases where it is not, so we cannot optimize without checking
285 // for it. The case is when you are shifting a signed value by 1 less than
286 // the number of bits in the value. For example:
287 // %X = shl sbyte %Y, ubyte 7
288 // will try to form an sbyte multiplier of 128, which will give a null
289 // multiplier, even though the result is not 0. Until we can check for this
290 // case, be conservative. TODO.
295 return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var,
296 DefZero(Left.Offset, Ty) * Multiplier);
297 } // end case Instruction::Shl
299 case Instruction::Mul: {
300 ExprType Left (ClassifyExpression(I->getOperand(0)));
301 ExprType Right(ClassifyExpression(I->getOperand(1)));
302 if (Left.ExprTy > Right.ExprTy)
303 std::swap(Left, Right); // Make left be simpler than right
305 if (Left.ExprTy != ExprType::Constant) // RHS must be > constant
306 return I; // Quadratic eqn! :(
308 const ConstantInt *Offs = Left.Offset;
309 if (Offs == 0) return ExprType();
310 return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var,
311 DefZero(Right.Offset, Ty) * Offs);
312 } // end case Instruction::Mul
314 case Instruction::Cast: {
315 ExprType Src(ClassifyExpression(I->getOperand(0)));
316 const Type *DestTy = I->getType();
317 if (isa<PointerType>(DestTy))
318 DestTy = Type::ULongTy; // Pointer types are represented as ulong
320 if (!Src.getExprType(0)->isLosslesslyConvertibleTo(DestTy)) {
321 if (Src.ExprTy != ExprType::Constant)
322 return I; // Converting cast, and not a constant value...
325 const ConstantInt *Offset = Src.Offset;
326 const ConstantInt *Scale = Src.Scale;
328 const Constant *CPV = ConstantFoldCastInstruction(Offset, DestTy);
330 Offset = cast<ConstantInt>(CPV);
333 const Constant *CPV = ConstantFoldCastInstruction(Scale, DestTy);
335 Scale = cast<ConstantInt>(CPV);
337 return ExprType(Scale, Src.Var, Offset);
338 } // end case Instruction::Cast
339 // TODO: Handle SUB, SHR?
343 // Otherwise, I don't know anything about this value!