LLVM API Documentation

Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members | Related Pages

Expressions.cpp

Go to the documentation of this file.
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 }