lib/Analysis/Expressions.cpp

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