LLVM API Documentation
00001 //===- Expressions.cpp - Expression Analysis Utilities --------------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines a package of expression analysis utilties: 00011 // 00012 // ClassifyExpression: Analyze an expression to determine the complexity of the 00013 // expression, and which other variables it depends on. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #include "llvm/Analysis/Expressions.h" 00018 #include "llvm/Constants.h" 00019 #include "llvm/Function.h" 00020 #include "llvm/Type.h" 00021 #include <iostream> 00022 00023 using namespace llvm; 00024 00025 ExprType::ExprType(Value *Val) { 00026 if (Val) 00027 if (ConstantInt *CPI = dyn_cast<ConstantInt>(Val)) { 00028 Offset = CPI; 00029 Var = 0; 00030 ExprTy = Constant; 00031 Scale = 0; 00032 return; 00033 } 00034 00035 Var = Val; Offset = 0; 00036 ExprTy = Var ? Linear : Constant; 00037 Scale = 0; 00038 } 00039 00040 ExprType::ExprType(const ConstantInt *scale, Value *var, 00041 const ConstantInt *offset) { 00042 Scale = var ? scale : 0; Var = var; Offset = offset; 00043 ExprTy = Scale ? ScaledLinear : (Var ? Linear : Constant); 00044 if (Scale && Scale->isNullValue()) { // Simplify 0*Var + const 00045 Scale = 0; Var = 0; 00046 ExprTy = Constant; 00047 } 00048 } 00049 00050 00051 const Type *ExprType::getExprType(const Type *Default) const { 00052 if (Offset) return Offset->getType(); 00053 if (Scale) return Scale->getType(); 00054 return Var ? Var->getType() : Default; 00055 } 00056 00057 00058 namespace { 00059 class DefVal { 00060 const ConstantInt * const Val; 00061 const Type * const Ty; 00062 protected: 00063 inline DefVal(const ConstantInt *val, const Type *ty) : Val(val), Ty(ty) {} 00064 public: 00065 inline const Type *getType() const { return Ty; } 00066 inline const ConstantInt *getVal() const { return Val; } 00067 inline operator const ConstantInt * () const { return Val; } 00068 inline const ConstantInt *operator->() const { return Val; } 00069 }; 00070 00071 struct DefZero : public DefVal { 00072 inline DefZero(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {} 00073 inline DefZero(const ConstantInt *val) : DefVal(val, val->getType()) {} 00074 }; 00075 00076 struct DefOne : public DefVal { 00077 inline DefOne(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {} 00078 }; 00079 } 00080 00081 00082 // getUnsignedConstant - Return a constant value of the specified type. If the 00083 // constant value is not valid for the specified type, return null. This cannot 00084 // happen for values in the range of 0 to 127. 00085 // 00086 static ConstantInt *getUnsignedConstant(uint64_t V, const Type *Ty) { 00087 if (isa<PointerType>(Ty)) Ty = Type::ULongTy; 00088 if (Ty->isSigned()) { 00089 // If this value is not a valid unsigned value for this type, return null! 00090 if (V > 127 && ((int64_t)V < 0 || 00091 !ConstantSInt::isValueValidForType(Ty, (int64_t)V))) 00092 return 0; 00093 return ConstantSInt::get(Ty, V); 00094 } else { 00095 // If this value is not a valid unsigned value for this type, return null! 00096 if (V > 255 && !ConstantUInt::isValueValidForType(Ty, V)) 00097 return 0; 00098 return ConstantUInt::get(Ty, V); 00099 } 00100 } 00101 00102 // Add - Helper function to make later code simpler. Basically it just adds 00103 // the two constants together, inserts the result into the constant pool, and 00104 // returns it. Of course life is not simple, and this is no exception. Factors 00105 // that complicate matters: 00106 // 1. Either argument may be null. If this is the case, the null argument is 00107 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true) 00108 // 2. Types get in the way. We want to do arithmetic operations without 00109 // regard for the underlying types. It is assumed that the constants are 00110 // integral constants. The new value takes the type of the left argument. 00111 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne 00112 // is false, a null return value indicates a value of 0. 00113 // 00114 static const ConstantInt *Add(const ConstantInt *Arg1, 00115 const ConstantInt *Arg2, bool DefOne) { 00116 assert(Arg1 && Arg2 && "No null arguments should exist now!"); 00117 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); 00118 00119 // Actually perform the computation now! 00120 Constant *Result = ConstantExpr::get(Instruction::Add, (Constant*)Arg1, 00121 (Constant*)Arg2); 00122 ConstantInt *ResultI = cast<ConstantInt>(Result); 00123 00124 // Check to see if the result is one of the special cases that we want to 00125 // recognize... 00126 if (ResultI->equalsInt(DefOne ? 1 : 0)) 00127 return 0; // Yes it is, simply return null. 00128 00129 return ResultI; 00130 } 00131 00132 static inline const ConstantInt *operator+(const DefZero &L, const DefZero &R) { 00133 if (L == 0) return R; 00134 if (R == 0) return L; 00135 return Add(L, R, false); 00136 } 00137 00138 static inline const ConstantInt *operator+(const DefOne &L, const DefOne &R) { 00139 if (L == 0) { 00140 if (R == 0) 00141 return getUnsignedConstant(2, L.getType()); 00142 else 00143 return Add(getUnsignedConstant(1, L.getType()), R, true); 00144 } else if (R == 0) { 00145 return Add(L, getUnsignedConstant(1, L.getType()), true); 00146 } 00147 return Add(L, R, true); 00148 } 00149 00150 00151 // Mul - Helper function to make later code simpler. Basically it just 00152 // multiplies the two constants together, inserts the result into the constant 00153 // pool, and returns it. Of course life is not simple, and this is no 00154 // exception. Factors that complicate matters: 00155 // 1. Either argument may be null. If this is the case, the null argument is 00156 // treated as either 0 (if DefOne = false) or 1 (if DefOne = true) 00157 // 2. Types get in the way. We want to do arithmetic operations without 00158 // regard for the underlying types. It is assumed that the constants are 00159 // integral constants. 00160 // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne 00161 // is false, a null return value indicates a value of 0. 00162 // 00163 static inline const ConstantInt *Mul(const ConstantInt *Arg1, 00164 const ConstantInt *Arg2, bool DefOne) { 00165 assert(Arg1 && Arg2 && "No null arguments should exist now!"); 00166 assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); 00167 00168 // Actually perform the computation now! 00169 Constant *Result = ConstantExpr::get(Instruction::Mul, (Constant*)Arg1, 00170 (Constant*)Arg2); 00171 assert(Result && Result->getType() == Arg1->getType() && 00172 "Couldn't perform multiplication!"); 00173 ConstantInt *ResultI = cast<ConstantInt>(Result); 00174 00175 // Check to see if the result is one of the special cases that we want to 00176 // recognize... 00177 if (ResultI->equalsInt(DefOne ? 1 : 0)) 00178 return 0; // Yes it is, simply return null. 00179 00180 return ResultI; 00181 } 00182 00183 namespace { 00184 inline const ConstantInt *operator*(const DefZero &L, const DefZero &R) { 00185 if (L == 0 || R == 0) return 0; 00186 return Mul(L, R, false); 00187 } 00188 inline const ConstantInt *operator*(const DefOne &L, const DefZero &R) { 00189 if (R == 0) return getUnsignedConstant(0, L.getType()); 00190 if (L == 0) return R->equalsInt(1) ? 0 : R.getVal(); 00191 return Mul(L, R, true); 00192 } 00193 inline const ConstantInt *operator*(const DefZero &L, const DefOne &R) { 00194 if (L == 0 || R == 0) return L.getVal(); 00195 return Mul(R, L, false); 00196 } 00197 } 00198 00199 // handleAddition - Add two expressions together, creating a new expression that 00200 // represents the composite of the two... 00201 // 00202 static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) { 00203 const Type *Ty = V->getType(); 00204 if (Left.ExprTy > Right.ExprTy) 00205 std::swap(Left, Right); // Make left be simpler than right 00206 00207 switch (Left.ExprTy) { 00208 case ExprType::Constant: 00209 return ExprType(Right.Scale, Right.Var, 00210 DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty)); 00211 case ExprType::Linear: // RHS side must be linear or scaled 00212 case ExprType::ScaledLinear: // RHS must be scaled 00213 if (Left.Var != Right.Var) // Are they the same variables? 00214 return V; // if not, we don't know anything! 00215 00216 return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty), 00217 Right.Var, 00218 DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty)); 00219 default: 00220 assert(0 && "Dont' know how to handle this case!"); 00221 return ExprType(); 00222 } 00223 } 00224 00225 // negate - Negate the value of the specified expression... 00226 // 00227 static inline ExprType negate(const ExprType &E, Value *V) { 00228 const Type *Ty = V->getType(); 00229 ConstantInt *Zero = getUnsignedConstant(0, Ty); 00230 ConstantInt *One = getUnsignedConstant(1, Ty); 00231 ConstantInt *NegOne = cast<ConstantInt>(ConstantExpr::get(Instruction::Sub, 00232 Zero, One)); 00233 if (NegOne == 0) return V; // Couldn't subtract values... 00234 00235 return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var, 00236 DefZero(E.Offset, Ty) * NegOne); 00237 } 00238 00239 00240 // ClassifyExpr: Analyze an expression to determine the complexity of the 00241 // expression, and which other values it depends on. 00242 // 00243 // Note that this analysis cannot get into infinite loops because it treats PHI 00244 // nodes as being an unknown linear expression. 00245 // 00246 ExprType llvm::ClassifyExpr(Value *Expr) { 00247 assert(Expr != 0 && "Can't classify a null expression!"); 00248 if (Expr->getType()->isFloatingPoint()) 00249 return Expr; // FIXME: Can't handle FP expressions 00250 00251 if (Constant *C = dyn_cast<Constant>(Expr)) { 00252 if (ConstantInt *CPI = dyn_cast<ConstantInt>(cast<Constant>(Expr))) 00253 // It's an integral constant! 00254 return ExprType(CPI->isNullValue() ? 0 : CPI); 00255 return Expr; 00256 } else if (!isa<Instruction>(Expr)) { 00257 return Expr; 00258 } 00259 00260 00261 Instruction *I = cast<Instruction>(Expr); 00262 const Type *Ty = I->getType(); 00263 00264 switch (I->getOpcode()) { // Handle each instruction type separately 00265 case Instruction::Add: { 00266 ExprType Left (ClassifyExpr(I->getOperand(0))); 00267 ExprType Right(ClassifyExpr(I->getOperand(1))); 00268 return handleAddition(Left, Right, I); 00269 } // end case Instruction::Add 00270 00271 case Instruction::Sub: { 00272 ExprType Left (ClassifyExpr(I->getOperand(0))); 00273 ExprType Right(ClassifyExpr(I->getOperand(1))); 00274 ExprType RightNeg = negate(Right, I); 00275 if (RightNeg.Var == I && !RightNeg.Offset && !RightNeg.Scale) 00276 return I; // Could not negate value... 00277 return handleAddition(Left, RightNeg, I); 00278 } // end case Instruction::Sub 00279 00280 case Instruction::Shl: { 00281 ExprType Right(ClassifyExpr(I->getOperand(1))); 00282 if (Right.ExprTy != ExprType::Constant) break; 00283 ExprType Left(ClassifyExpr(I->getOperand(0))); 00284 if (Right.Offset == 0) return Left; // shl x, 0 = x 00285 assert(Right.Offset->getType() == Type::UByteTy && 00286 "Shift amount must always be a unsigned byte!"); 00287 uint64_t ShiftAmount = cast<ConstantUInt>(Right.Offset)->getValue(); 00288 ConstantInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty); 00289 00290 // We don't know how to classify it if they are shifting by more than what 00291 // is reasonable. In most cases, the result will be zero, but there is one 00292 // class of cases where it is not, so we cannot optimize without checking 00293 // for it. The case is when you are shifting a signed value by 1 less than 00294 // the number of bits in the value. For example: 00295 // %X = shl sbyte %Y, ubyte 7 00296 // will try to form an sbyte multiplier of 128, which will give a null 00297 // multiplier, even though the result is not 0. Until we can check for this 00298 // case, be conservative. TODO. 00299 // 00300 if (Multiplier == 0) 00301 return Expr; 00302 00303 return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var, 00304 DefZero(Left.Offset, Ty) * Multiplier); 00305 } // end case Instruction::Shl 00306 00307 case Instruction::Mul: { 00308 ExprType Left (ClassifyExpr(I->getOperand(0))); 00309 ExprType Right(ClassifyExpr(I->getOperand(1))); 00310 if (Left.ExprTy > Right.ExprTy) 00311 std::swap(Left, Right); // Make left be simpler than right 00312 00313 if (Left.ExprTy != ExprType::Constant) // RHS must be > constant 00314 return I; // Quadratic eqn! :( 00315 00316 const ConstantInt *Offs = Left.Offset; 00317 if (Offs == 0) return ExprType(); 00318 return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var, 00319 DefZero(Right.Offset, Ty) * Offs); 00320 } // end case Instruction::Mul 00321 00322 case Instruction::Cast: { 00323 ExprType Src(ClassifyExpr(I->getOperand(0))); 00324 const Type *DestTy = I->getType(); 00325 if (isa<PointerType>(DestTy)) 00326 DestTy = Type::ULongTy; // Pointer types are represented as ulong 00327 00328 const Type *SrcValTy = Src.getExprType(0); 00329 if (!SrcValTy) return I; 00330 if (!SrcValTy->isLosslesslyConvertibleTo(DestTy)) { 00331 if (Src.ExprTy != ExprType::Constant) 00332 return I; // Converting cast, and not a constant value... 00333 } 00334 00335 const ConstantInt *Offset = Src.Offset; 00336 const ConstantInt *Scale = Src.Scale; 00337 if (Offset) { 00338 const Constant *CPV = ConstantExpr::getCast((Constant*)Offset, DestTy); 00339 if (!isa<ConstantInt>(CPV)) return I; 00340 Offset = cast<ConstantInt>(CPV); 00341 } 00342 if (Scale) { 00343 const Constant *CPV = ConstantExpr::getCast((Constant*)Scale, DestTy); 00344 if (!CPV) return I; 00345 Scale = cast<ConstantInt>(CPV); 00346 } 00347 return ExprType(Scale, Src.Var, Offset); 00348 } // end case Instruction::Cast 00349 // TODO: Handle SUB, SHR? 00350 00351 } // end switch 00352 00353 // Otherwise, I don't know anything about this value! 00354 return I; 00355 }