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