lib/Analysis/Expressions.cpp

   1 //===- Expressions.cpp - Expression Analysis Utilities ----------------------=//
   2 //
   3 // This file defines a package of expression analysis utilties:
   4 //
   5 // ClassifyExpression: Analyze an expression to determine the complexity of the
   6 //   expression, and which other variables it depends on.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/Analysis/Expressions.h"
  11 #include "llvm/Optimizations/ConstantHandling.h"
  12 #include "llvm/Method.h"
  13 #include "llvm/BasicBlock.h"
  14
  15 using namespace opt;  // Get all the constant handling stuff
  16 using namespace analysis;
  17
  18 class DefVal {
  19   const ConstPoolInt * const Val;
  20   const Type * const Ty;
  21 protected:
  22   inline DefVal(const ConstPoolInt *val, const Type *ty) : Val(val), Ty(ty) {}
  23 public:
  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; }
  28 };
  29
  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()) {}
  33 };
  34
  35 struct DefOne : public DefVal {
  36   inline DefOne(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {}
  37 };
  38
  39
  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.
  44 //
  45 static ConstPoolInt *getIntegralConstant(unsigned char V, const Type *Ty) {
  46   return ConstPoolInt::get(Ty, V);
  47 }
  48
  49 static ConstPoolInt *getUnsignedConstant(uint64_t V, const Type *Ty) {
  50   if (Ty->isPointerType()) Ty = Type::ULongTy;
  51
  52   return Ty->isSigned() ? ConstPoolSInt::get(Ty, V) : ConstPoolUInt::get(Ty, V);
  53 }
  54
  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.
  66 //
  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!");
  71
  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;
  77
  78   // Check to see if the result is one of the special cases that we want to
  79   // recognize...
  80   if (ResultI->equalsInt(DefOne ? 1 : 0)) {
  81     // Yes it is, simply delete the constant and return null.
  82     delete ResultI;
  83     return 0;
  84   }
  85
  86   return ResultI;
  87 }
  88
  89 inline const ConstPoolInt *operator+(const DefZero &L, const DefZero &R) {
  90   if (L == 0) return R;
  91   if (R == 0) return L;
  92   return Add(L, R, false);
  93 }
  94
  95 inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) {
  96   if (L == 0) {
  97     if (R == 0)
  98       return getIntegralConstant(2, L.getType());
  99     else
 100       return Add(getIntegralConstant(1, L.getType()), R, true);
 101   } else if (R == 0) {
 102     return Add(L, getIntegralConstant(1, L.getType()), true);
 103   }
 104   return Add(L, R, true);
 105 }
 106
 107
 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.
 119 //
 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!");
 124
 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;
 130
 131   // Check to see if the result is one of the special cases that we want to
 132   // recognize...
 133   if (ResultI->equalsInt(DefOne ? 1 : 0)) {
 134     // Yes it is, simply delete the constant and return null.
 135     delete ResultI;
 136     return 0;
 137   }
 138
 139   return ResultI;
 140 }
 141
 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);
 145 }
 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);
 150 }
 151 inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) {
 152   return R*L;
 153 }
 154
 155
 156
 157 // ClassifyExpression: Analyze an expression to determine the complexity of the
 158 // expression, and which other values it depends on.
 159 //
 160 // Note that this analysis cannot get into infinite loops because it treats PHI
 161 // nodes as being an unknown linear expression.
 162 //
 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: default:
 169     assert(0 && "Unexpected expression type to classify!");
 170   case Value::GlobalVal:                // Global Variable & Method argument:
 171   case Value::MethodArgumentVal:        // nothing known, return variable itself
 172     return Expr;
 173   case Value::ConstantVal:              // Constant value, just return constant
 174     ConstPoolVal *CPV = Expr->castConstantAsserting();
 175     if (CPV->getType()->isIntegral()) { // It's an integral constant!
 176       ConstPoolInt *CPI = (ConstPoolInt*)Expr;
 177       return ExprType(CPI->equalsInt(0) ? 0 : (ConstPoolInt*)Expr);
 178     }
 179     return Expr;
 180   }
 181
 182   Instruction *I = Expr->castInstructionAsserting();
 183   const Type *Ty = I->getType();
 184
 185   switch (I->getOpcode()) {       // Handle each instruction type seperately
 186   case Instruction::Add: {
 187     ExprType Left (ClassifyExpression(I->getOperand(0)));
 188     ExprType Right(ClassifyExpression(I->getOperand(1)));
 189     if (Left.ExprTy > Right.ExprTy)
 190       swap(Left, Right);   // Make left be simpler than right
 191
 192     switch (Left.ExprTy) {
 193     case ExprType::Constant:
 194       return ExprType(Right.Scale, Right.Var,
 195                       DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty));
 196     case ExprType::Linear:        // RHS side must be linear or scaled
 197     case ExprType::ScaledLinear:  // RHS must be scaled
 198       if (Left.Var != Right.Var)        // Are they the same variables?
 199         return ExprType(I);       //   if not, we don't know anything!
 200
 201       return ExprType( DefOne(Left.Scale , Ty) +  DefOne(Right.Scale , Ty),
 202                       Left.Var,
 203                       DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty));
 204     }
 205   }  // end case Instruction::Add
 206
 207   case Instruction::Shl: {
 208     ExprType Right(ClassifyExpression(I->getOperand(1)));
 209     if (Right.ExprTy != ExprType::Constant) break;
 210     ExprType Left(ClassifyExpression(I->getOperand(0)));
 211     if (Right.Offset == 0) return Left;   // shl x, 0 = x
 212     assert(Right.Offset->getType() == Type::UByteTy &&
 213            "Shift amount must always be a unsigned byte!");
 214     uint64_t ShiftAmount = ((ConstPoolUInt*)Right.Offset)->getValue();
 215     ConstPoolInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty);
 216
 217     return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var,
 218                     DefZero(Left.Offset, Ty) * Multiplier);
 219   }  // end case Instruction::Shl
 220
 221   case Instruction::Mul: {
 222     ExprType Left (ClassifyExpression(I->getOperand(0)));
 223     ExprType Right(ClassifyExpression(I->getOperand(1)));
 224     if (Left.ExprTy > Right.ExprTy)
 225       swap(Left, Right);   // Make left be simpler than right
 226
 227     if (Left.ExprTy != ExprType::Constant)  // RHS must be > constant
 228       return I;         // Quadratic eqn! :(
 229
 230     const ConstPoolInt *Offs = Left.Offset;
 231     if (Offs == 0) return ExprType();
 232     return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var,
 233                     DefZero(Right.Offset, Ty) * Offs);
 234   } // end case Instruction::Mul
 235
 236   case Instruction::Cast: {
 237     ExprType Src(ClassifyExpression(I->getOperand(0)));
 238     if (Src.ExprTy != ExprType::Constant)
 239       return I;
 240     const ConstPoolInt *Offs = Src.Offset;
 241     if (Offs == 0) return ExprType();
 242
 243     if (I->getType()->isPointerType())
 244       return Offs;  // Pointer types do not lose precision
 245
 246     assert(I->getType()->isIntegral() && "Can only handle integral types!");
 247
 248     const ConstPoolVal *CPV =ConstRules::get(*Offs)->castTo(Offs, I->getType());
 249     if (!CPV) return I;
 250     assert(CPV->getType()->isIntegral() && "Must have an integral type!");
 251     return (ConstPoolInt*)CPV;
 252   } // end case Instruction::Cast
 253     // TODO: Handle SUB, SHR?
 254
 255   }  // end switch
 256
 257   // Otherwise, I don't know anything about this value!
 258   return I;
 259 }