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