1 //===- Expressions.cpp - Expression Analysis Utilities --------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by the LLVM research group and is distributed under
6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file defines a package of expression analysis utilties:
12 // ClassifyExpression: Analyze an expression to determine the complexity of the
13 // expression, and which other variables it depends on.
15 //===----------------------------------------------------------------------===//
17 #include "llvm/Analysis/Expressions.h"
18 #include "llvm/Constants.h"
19 #include "llvm/Function.h"
20 #include "llvm/Type.h"
25 ExprType::ExprType(Value *Val) {
27 if (ConstantInt *CPI = dyn_cast<ConstantInt>(Val)) {
35 Var = Val; Offset = 0;
36 ExprTy = Var ? Linear : Constant;
40 ExprType::ExprType(const ConstantInt *scale, Value *var,
41 const ConstantInt *offset) {
42 Scale = var ? scale : 0; Var = var; Offset = offset;
43 ExprTy = Scale ? ScaledLinear : (Var ? Linear : Constant);
44 if (Scale && Scale->isNullValue()) { // Simplify 0*Var + const
51 const Type *ExprType::getExprType(const Type *Default) const {
52 if (Offset) return Offset->getType();
53 if (Scale) return Scale->getType();
54 return Var ? Var->getType() : Default;
60 const ConstantInt * const Val;
61 const Type * const Ty;
63 inline DefVal(const ConstantInt *val, const Type *ty) : Val(val), Ty(ty) {}
65 inline const Type *getType() const { return Ty; }
66 inline const ConstantInt *getVal() const { return Val; }
67 inline operator const ConstantInt * () const { return Val; }
68 inline const ConstantInt *operator->() const { return Val; }
71 struct DefZero : public DefVal {
72 inline DefZero(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {}
73 inline DefZero(const ConstantInt *val) : DefVal(val, val->getType()) {}
76 struct DefOne : public DefVal {
77 inline DefOne(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {}
82 // getUnsignedConstant - Return a constant value of the specified type. If the
83 // constant value is not valid for the specified type, return null. This cannot
84 // happen for values in the range of 0 to 127.
86 static ConstantInt *getUnsignedConstant(uint64_t V, const Type *Ty) {
87 if (isa<PointerType>(Ty)) Ty = Type::ULongTy;
89 // If this value is not a valid unsigned value for this type, return null!
90 if (V > 127 && ((int64_t)V < 0 ||
91 !ConstantSInt::isValueValidForType(Ty, (int64_t)V)))
93 return ConstantSInt::get(Ty, V);
95 // If this value is not a valid unsigned value for this type, return null!
96 if (V > 255 && !ConstantUInt::isValueValidForType(Ty, V))
98 return ConstantUInt::get(Ty, V);
102 // Add - Helper function to make later code simpler. Basically it just adds
103 // the two constants together, inserts the result into the constant pool, and
104 // returns it. Of course life is not simple, and this is no exception. Factors
105 // that complicate matters:
106 // 1. Either argument may be null. If this is the case, the null argument is
107 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
108 // 2. Types get in the way. We want to do arithmetic operations without
109 // regard for the underlying types. It is assumed that the constants are
110 // integral constants. The new value takes the type of the left argument.
111 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
112 // is false, a null return value indicates a value of 0.
114 static const ConstantInt *Add(const ConstantInt *Arg1,
115 const ConstantInt *Arg2, bool DefOne) {
116 assert(Arg1 && Arg2 && "No null arguments should exist now!");
117 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
119 // Actually perform the computation now!
120 Constant *Result = ConstantExpr::get(Instruction::Add, (Constant*)Arg1,
122 ConstantInt *ResultI = cast<ConstantInt>(Result);
124 // Check to see if the result is one of the special cases that we want to
126 if (ResultI->equalsInt(DefOne ? 1 : 0))
127 return 0; // Yes it is, simply return null.
132 static inline const ConstantInt *operator+(const DefZero &L, const DefZero &R) {
133 if (L == 0) return R;
134 if (R == 0) return L;
135 return Add(L, R, false);
138 static inline const ConstantInt *operator+(const DefOne &L, const DefOne &R) {
141 return getUnsignedConstant(2, L.getType());
143 return Add(getUnsignedConstant(1, L.getType()), R, true);
145 return Add(L, getUnsignedConstant(1, L.getType()), true);
147 return Add(L, R, true);
151 // Mul - Helper function to make later code simpler. Basically it just
152 // multiplies the two constants together, inserts the result into the constant
153 // pool, and returns it. Of course life is not simple, and this is no
154 // exception. Factors that complicate matters:
155 // 1. Either argument may be null. If this is the case, the null argument is
156 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
157 // 2. Types get in the way. We want to do arithmetic operations without
158 // regard for the underlying types. It is assumed that the constants are
159 // integral constants.
160 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne
161 // is false, a null return value indicates a value of 0.
163 static inline const ConstantInt *Mul(const ConstantInt *Arg1,
164 const ConstantInt *Arg2, bool DefOne) {
165 assert(Arg1 && Arg2 && "No null arguments should exist now!");
166 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
168 // Actually perform the computation now!
169 Constant *Result = ConstantExpr::get(Instruction::Mul, (Constant*)Arg1,
171 assert(Result && Result->getType() == Arg1->getType() &&
172 "Couldn't perform multiplication!");
173 ConstantInt *ResultI = cast<ConstantInt>(Result);
175 // Check to see if the result is one of the special cases that we want to
177 if (ResultI->equalsInt(DefOne ? 1 : 0))
178 return 0; // Yes it is, simply return null.
184 inline const ConstantInt *operator*(const DefZero &L, const DefZero &R) {
185 if (L == 0 || R == 0) return 0;
186 return Mul(L, R, false);
188 inline const ConstantInt *operator*(const DefOne &L, const DefZero &R) {
189 if (R == 0) return getUnsignedConstant(0, L.getType());
190 if (L == 0) return R->equalsInt(1) ? 0 : R.getVal();
191 return Mul(L, R, true);
193 inline const ConstantInt *operator*(const DefZero &L, const DefOne &R) {
194 if (L == 0 || R == 0) return L.getVal();
195 return Mul(R, L, false);
199 // handleAddition - Add two expressions together, creating a new expression that
200 // represents the composite of the two...
202 static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) {
203 const Type *Ty = V->getType();
204 if (Left.ExprTy > Right.ExprTy)
205 std::swap(Left, Right); // Make left be simpler than right
207 switch (Left.ExprTy) {
208 case ExprType::Constant:
209 return ExprType(Right.Scale, Right.Var,
210 DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty));
211 case ExprType::Linear: // RHS side must be linear or scaled
212 case ExprType::ScaledLinear: // RHS must be scaled
213 if (Left.Var != Right.Var) // Are they the same variables?
214 return V; // if not, we don't know anything!
216 return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty),
218 DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty));
220 assert(0 && "Dont' know how to handle this case!");
225 // negate - Negate the value of the specified expression...
227 static inline ExprType negate(const ExprType &E, Value *V) {
228 const Type *Ty = V->getType();
229 ConstantInt *Zero = getUnsignedConstant(0, Ty);
230 ConstantInt *One = getUnsignedConstant(1, Ty);
231 ConstantInt *NegOne = cast<ConstantInt>(ConstantExpr::get(Instruction::Sub,
233 if (NegOne == 0) return V; // Couldn't subtract values...
235 return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var,
236 DefZero(E.Offset, Ty) * NegOne);
240 // ClassifyExpr: Analyze an expression to determine the complexity of the
241 // expression, and which other values it depends on.
243 // Note that this analysis cannot get into infinite loops because it treats PHI
244 // nodes as being an unknown linear expression.
246 ExprType llvm::ClassifyExpr(Value *Expr) {
247 assert(Expr != 0 && "Can't classify a null expression!");
248 if (Expr->getType()->isFloatingPoint())
249 return Expr; // FIXME: Can't handle FP expressions
251 if (Constant *C = dyn_cast<Constant>(Expr)) {
252 if (ConstantInt *CPI = dyn_cast<ConstantInt>(cast<Constant>(Expr)))
253 // It's an integral constant!
254 return ExprType(CPI->isNullValue() ? 0 : CPI);
256 } else if (!isa<Instruction>(Expr)) {
261 Instruction *I = cast<Instruction>(Expr);
262 const Type *Ty = I->getType();
264 switch (I->getOpcode()) { // Handle each instruction type separately
265 case Instruction::Add: {
266 ExprType Left (ClassifyExpr(I->getOperand(0)));
267 ExprType Right(ClassifyExpr(I->getOperand(1)));
268 return handleAddition(Left, Right, I);
269 } // end case Instruction::Add
271 case Instruction::Sub: {
272 ExprType Left (ClassifyExpr(I->getOperand(0)));
273 ExprType Right(ClassifyExpr(I->getOperand(1)));
274 ExprType RightNeg = negate(Right, I);
275 if (RightNeg.Var == I && !RightNeg.Offset && !RightNeg.Scale)
276 return I; // Could not negate value...
277 return handleAddition(Left, RightNeg, I);
278 } // end case Instruction::Sub
280 case Instruction::Shl: {
281 ExprType Right(ClassifyExpr(I->getOperand(1)));
282 if (Right.ExprTy != ExprType::Constant) break;
283 ExprType Left(ClassifyExpr(I->getOperand(0)));
284 if (Right.Offset == 0) return Left; // shl x, 0 = x
285 assert(Right.Offset->getType() == Type::UByteTy &&
286 "Shift amount must always be a unsigned byte!");
287 uint64_t ShiftAmount = cast<ConstantUInt>(Right.Offset)->getValue();
288 ConstantInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty);
290 // We don't know how to classify it if they are shifting by more than what
291 // is reasonable. In most cases, the result will be zero, but there is one
292 // class of cases where it is not, so we cannot optimize without checking
293 // for it. The case is when you are shifting a signed value by 1 less than
294 // the number of bits in the value. For example:
295 // %X = shl sbyte %Y, ubyte 7
296 // will try to form an sbyte multiplier of 128, which will give a null
297 // multiplier, even though the result is not 0. Until we can check for this
298 // case, be conservative. TODO.
303 return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var,
304 DefZero(Left.Offset, Ty) * Multiplier);
305 } // end case Instruction::Shl
307 case Instruction::Mul: {
308 ExprType Left (ClassifyExpr(I->getOperand(0)));
309 ExprType Right(ClassifyExpr(I->getOperand(1)));
310 if (Left.ExprTy > Right.ExprTy)
311 std::swap(Left, Right); // Make left be simpler than right
313 if (Left.ExprTy != ExprType::Constant) // RHS must be > constant
314 return I; // Quadratic eqn! :(
316 const ConstantInt *Offs = Left.Offset;
317 if (Offs == 0) return ExprType();
318 return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var,
319 DefZero(Right.Offset, Ty) * Offs);
320 } // end case Instruction::Mul
322 case Instruction::Cast: {
323 ExprType Src(ClassifyExpr(I->getOperand(0)));
324 const Type *DestTy = I->getType();
325 if (isa<PointerType>(DestTy))
326 DestTy = Type::ULongTy; // Pointer types are represented as ulong
328 const Type *SrcValTy = Src.getExprType(0);
329 if (!SrcValTy) return I;
330 if (!SrcValTy->isLosslesslyConvertibleTo(DestTy)) {
331 if (Src.ExprTy != ExprType::Constant)
332 return I; // Converting cast, and not a constant value...
335 const ConstantInt *Offset = Src.Offset;
336 const ConstantInt *Scale = Src.Scale;
338 const Constant *CPV = ConstantExpr::getCast((Constant*)Offset, DestTy);
339 if (!isa<ConstantInt>(CPV)) return I;
340 Offset = cast<ConstantInt>(CPV);
343 const Constant *CPV = ConstantExpr::getCast((Constant*)Scale, DestTy);
345 Scale = cast<ConstantInt>(CPV);
347 return ExprType(Scale, Src.Var, Offset);
348 } // end case Instruction::Cast
349 // TODO: Handle SUB, SHR?
353 // Otherwise, I don't know anything about this value!