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