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/ConstantPool.h"
  13 #include "llvm/Method.h"
  14 #include "llvm/BasicBlock.h"
  15
  16 using namespace opt;  // Get all the constant handling stuff
  17 using namespace analysis;
  18
  19 class DefVal {
  20   const ConstPoolInt * const Val;
  21   ConstantPool &CP;
  22   const Type * const Ty;
  23 protected:
  24   inline DefVal(const ConstPoolInt *val, ConstantPool &cp, const Type *ty)
  25     : Val(val), CP(cp), Ty(ty) {}
  26 public:
  27   inline const Type *getType() const { return Ty; }
  28   inline ConstantPool &getCP() const { return CP; }
  29   inline const ConstPoolInt *getVal() const { return Val; }
  30   inline operator const ConstPoolInt * () const { return Val; }
  31   inline const ConstPoolInt *operator->() const { return Val; }
  32 };
  33
  34 struct DefZero : public DefVal {
  35   inline DefZero(const ConstPoolInt *val, ConstantPool &cp, const Type *ty)
  36     : DefVal(val, cp, ty) {}
  37   inline DefZero(const ConstPoolInt *val)
  38     : DefVal(val, (ConstantPool&)val->getParent()->getConstantPool(),
  39              val->getType()) {}
  40 };
  41
  42 struct DefOne : public DefVal {
  43   inline DefOne(const ConstPoolInt *val, ConstantPool &cp, const Type *ty)
  44     : DefVal(val, cp, ty) {}
  45 };
  46
  47
  48 // getIntegralConstant - Wrapper around the ConstPoolInt member of the same
  49 // name.  This method first checks to see if the desired constant is already in
  50 // the constant pool.  If it is, it is quickly recycled, otherwise a new one
  51 // is allocated and added to the constant pool.
  52 //
  53 static ConstPoolInt *getIntegralConstant(ConstantPool &CP, unsigned char V,
  54                                          const Type *Ty) {
  55   // FIXME: Lookup prexisting constant in table!
  56
  57   ConstPoolInt *CPI = ConstPoolInt::get(Ty, V);
  58   CP.insert(CPI);
  59   return CPI;
  60 }
  61
  62 static ConstPoolInt *getUnsignedConstant(ConstantPool &CP, uint64_t V,
  63                                          const Type *Ty) {
  64   // FIXME: Lookup prexisting constant in table!
  65
  66   ConstPoolInt *CPI;
  67   CPI = Ty->isSigned() ? new ConstPoolSInt(Ty, V) : new ConstPoolUInt(Ty, V);
  68   CP.insert(CPI);
  69   return CPI;
  70 }
  71
  72 // Add - Helper function to make later code simpler.  Basically it just adds
  73 // the two constants together, inserts the result into the constant pool, and
  74 // returns it.  Of course life is not simple, and this is no exception.  Factors
  75 // that complicate matters:
  76 //   1. Either argument may be null.  If this is the case, the null argument is
  77 //      treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
  78 //   2. Types get in the way.  We want to do arithmetic operations without
  79 //      regard for the underlying types.  It is assumed that the constants are
  80 //      integral constants.  The new value takes the type of the left argument.
  81 //   3. If DefOne is true, a null return value indicates a value of 1, if DefOne
  82 //      is false, a null return value indicates a value of 0.
  83 //
  84 static const ConstPoolInt *Add(ConstantPool &CP, const ConstPoolInt *Arg1,
  85                                const ConstPoolInt *Arg2, bool DefOne) {
  86   assert(Arg1 && Arg2 && "No null arguments should exist now!");
  87   assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
  88
  89   // Actually perform the computation now!
  90   ConstPoolVal *Result = *Arg1 + *Arg2;
  91   assert(Result && Result->getType() == Arg1->getType() &&
  92          "Couldn't perform addition!");
  93   ConstPoolInt *ResultI = (ConstPoolInt*)Result;
  94
  95   // Check to see if the result is one of the special cases that we want to
  96   // recognize...
  97   if (ResultI->equalsInt(DefOne ? 1 : 0)) {
  98     // Yes it is, simply delete the constant and return null.
  99     delete ResultI;
 100     return 0;
 101   }
 102
 103   CP.insert(ResultI);
 104   return ResultI;
 105 }
 106
 107 inline const ConstPoolInt *operator+(const DefZero &L, const DefZero &R) {
 108   if (L == 0) return R;
 109   if (R == 0) return L;
 110   return Add(L.getCP(), L, R, false);
 111 }
 112
 113 inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) {
 114   if (L == 0) {
 115     if (R == 0)
 116       return getIntegralConstant(L.getCP(), 2, L.getType());
 117     else
 118       return Add(L.getCP(), getIntegralConstant(L.getCP(), 1, L.getType()),
 119                  R, true);
 120   } else if (R == 0) {
 121     return Add(L.getCP(), L,
 122                getIntegralConstant(L.getCP(), 1, L.getType()), true);
 123   }
 124   return Add(L.getCP(), L, R, true);
 125 }
 126
 127
 128 // Mul - Helper function to make later code simpler.  Basically it just
 129 // multiplies the two constants together, inserts the result into the constant
 130 // pool, and returns it.  Of course life is not simple, and this is no
 131 // exception.  Factors that complicate matters:
 132 //   1. Either argument may be null.  If this is the case, the null argument is
 133 //      treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
 134 //   2. Types get in the way.  We want to do arithmetic operations without
 135 //      regard for the underlying types.  It is assumed that the constants are
 136 //      integral constants.
 137 //   3. If DefOne is true, a null return value indicates a value of 1, if DefOne
 138 //      is false, a null return value indicates a value of 0.
 139 //
 140 inline const ConstPoolInt *Mul(ConstantPool &CP, const ConstPoolInt *Arg1,
 141                                const ConstPoolInt *Arg2, bool DefOne = false) {
 142   assert(Arg1 && Arg2 && "No null arguments should exist now!");
 143   assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!");
 144
 145   // Actually perform the computation now!
 146   ConstPoolVal *Result = *Arg1 * *Arg2;
 147   assert(Result && Result->getType() == Arg1->getType() &&
 148          "Couldn't perform mult!");
 149   ConstPoolInt *ResultI = (ConstPoolInt*)Result;
 150
 151   // Check to see if the result is one of the special cases that we want to
 152   // recognize...
 153   if (ResultI->equalsInt(DefOne ? 1 : 0)) {
 154     // Yes it is, simply delete the constant and return null.
 155     delete ResultI;
 156     return 0;
 157   }
 158
 159   CP.insert(ResultI);
 160   return ResultI;
 161 }
 162
 163 inline const ConstPoolInt *operator*(const DefZero &L, const DefZero &R) {
 164   if (L == 0 || R == 0) return 0;
 165   return Mul(L.getCP(), L, R, false);
 166 }
 167 inline const ConstPoolInt *operator*(const DefOne &L, const DefZero &R) {
 168   if (R == 0) return getIntegralConstant(L.getCP(), 0, L.getType());
 169   if (L == 0) return R->equalsInt(1) ? 0 : R.getVal();
 170   return Mul(L.getCP(), L, R, false);
 171 }
 172 inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) {
 173   return R*L;
 174 }
 175
 176
 177
 178 // ClassifyExpression: Analyze an expression to determine the complexity of the
 179 // expression, and which other values it depends on.
 180 //
 181 // Note that this analysis cannot get into infinite loops because it treats PHI
 182 // nodes as being an unknown linear expression.
 183 //
 184 ExprType analysis::ClassifyExpression(Value *Expr) {
 185   assert(Expr != 0 && "Can't classify a null expression!");
 186   switch (Expr->getValueType()) {
 187   case Value::InstructionVal: break;    // Instruction... hmmm... investigate.
 188   case Value::TypeVal:   case Value::BasicBlockVal:
 189   case Value::MethodVal: case Value::ModuleVal:
 190     assert(0 && "Unexpected expression type to classify!");
 191   case Value::MethodArgumentVal:        // Method arg: nothing known, return var
 192     return Expr;
 193   case Value::ConstantVal:              // Constant value, just return constant
 194     ConstPoolVal *CPV = Expr->castConstantAsserting();
 195     if (CPV->getType()->isIntegral()) { // It's an integral constant!
 196       ConstPoolInt *CPI = (ConstPoolInt*)Expr;
 197       return ExprType(CPI->equalsInt(0) ? 0 : (ConstPoolInt*)Expr);
 198     }
 199     return Expr;
 200   }
 201
 202   Instruction *I = Expr->castInstructionAsserting();
 203   ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
 204   const Type *Ty = I->getType();
 205
 206   switch (I->getOpcode()) {       // Handle each instruction type seperately
 207   case Instruction::Add: {
 208     ExprType Left (ClassifyExpression(I->getOperand(0)));
 209     ExprType Right(ClassifyExpression(I->getOperand(1)));
 210     if (Left.ExprTy > Right.ExprTy)
 211       swap(Left, Right);   // Make left be simpler than right
 212
 213     switch (Left.ExprTy) {
 214     case ExprType::Constant:
 215       return ExprType(Right.Scale, Right.Var,
 216                       DefZero(Right.Offset,CP,Ty) + DefZero(Left.Offset, CP,Ty));
 217     case ExprType::Linear:        // RHS side must be linear or scaled
 218     case ExprType::ScaledLinear:  // RHS must be scaled
 219       if (Left.Var != Right.Var)        // Are they the same variables?
 220         return ExprType(I);       //   if not, we don't know anything!
 221
 222       return ExprType(DefOne(Left.Scale  ,CP,Ty) + DefOne(Right.Scale  , CP,Ty),
 223                       Left.Var,
 224                       DefZero(Left.Offset,CP,Ty) + DefZero(Right.Offset, CP,Ty));
 225     }
 226   }  // end case Instruction::Add
 227
 228   case Instruction::Shl: {
 229     ExprType Right(ClassifyExpression(I->getOperand(1)));
 230     if (Right.ExprTy != ExprType::Constant) break;
 231     ExprType Left(ClassifyExpression(I->getOperand(0)));
 232     if (Right.Offset == 0) return Left;   // shl x, 0 = x
 233     assert(Right.Offset->getType() == Type::UByteTy &&
 234            "Shift amount must always be a unsigned byte!");
 235     uint64_t ShiftAmount = ((ConstPoolUInt*)Right.Offset)->getValue();
 236     ConstPoolInt *Multiplier = getUnsignedConstant(CP, 1ULL << ShiftAmount, Ty);
 237
 238     return ExprType(DefOne(Left.Scale, CP, Ty) * Multiplier,
 239                     Left.Var,
 240                     DefZero(Left.Offset, CP, Ty) * Multiplier);
 241   }  // end case Instruction::Shl
 242
 243   case Instruction::Mul: {
 244     ExprType Left (ClassifyExpression(I->getOperand(0)));
 245     ExprType Right(ClassifyExpression(I->getOperand(1)));
 246     if (Left.ExprTy > Right.ExprTy)
 247       swap(Left, Right);   // Make left be simpler than right
 248
 249     if (Left.ExprTy != ExprType::Constant)  // RHS must be > constant
 250       return I;         // Quadratic eqn! :(
 251
 252     const ConstPoolInt *Offs = Left.Offset;
 253     if (Offs == 0) return ExprType();
 254     return ExprType(DefOne(Right.Scale, CP, Ty) * Offs,
 255                     Right.Var,
 256                     DefZero(Right.Offset, CP, Ty) * Offs);
 257   } // end case Instruction::Mul
 258
 259   case Instruction::Cast: {
 260     ExprType Src(ClassifyExpression(I->getOperand(0)));
 261     if (Src.ExprTy != ExprType::Constant)
 262       return I;
 263     const ConstPoolInt *Offs = Src.Offset;
 264     if (Offs == 0) return ExprType();
 265
 266     if (I->getType()->isPointerType())
 267       return Offs;  // Pointer types do not lose precision
 268
 269     assert(I->getType()->isIntegral() && "Can only handle integral types!");
 270
 271     const ConstPoolVal *CPV = ConstRules::get(*Offs)->castTo(Offs, I->getType());
 272     if (!CPV) return I;
 273     assert(CPV->getType()->isIntegral() && "Must have an integral type!");
 274     return (ConstPoolInt*)CPV;
 275   } // end case Instruction::Cast
 276     // TODO: Handle SUB (at least!)
 277
 278   }  // end switch
 279
 280   // Otherwise, I don't know anything about this value!
 281   return I;
 282 }