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