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