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