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/ConstantPool.h"
  13 #include "llvm/Method.h"
  14 #include "llvm/BasicBlock.h"
  15
  16 using namespace opt;  // Get all the constant handling stuff
  17
  18 // getIntegralConstant - Wrapper around the ConstPoolInt member of the same
  19 // name.  This method first checks to see if the desired constant is already in
  20 // the constant pool.  If it is, it is quickly recycled, otherwise a new one
  21 // is allocated and added to the constant pool.
  22 //
  23 static ConstPoolInt *getIntegralConstant(ConstantPool &CP, unsigned char V,
  24                                          const Type *Ty) {
  25   // FIXME: Lookup prexisting constant in table!
  26
  27   ConstPoolInt *CPI = ConstPoolInt::get(Ty, V);
  28   CP.insert(CPI);
  29   return CPI;
  30 }
  31
  32 static ConstPoolUInt *getUnsignedConstant(ConstantPool &CP, uint64_t V) {
  33   // FIXME: Lookup prexisting constant in table!
  34
  35   ConstPoolUInt *CPUI = new ConstPoolUInt(Type::ULongTy, V);
  36   CP.insert(CPUI);
  37   return CPUI;
  38 }
  39
  40
  41 // Add - Helper function to make later code simpler.  Basically it just adds
  42 // the two constants together, inserts the result into the constant pool, and
  43 // returns it.  Of course life is not simple, and this is no exception.  Factors
  44 // that complicate matters:
  45 //   1. Either argument may be null.  If this is the case, the null argument is
  46 //      treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
  47 //   2. Types get in the way.  We want to do arithmetic operations without
  48 //      regard for the underlying types.  It is assumed that the constants are
  49 //      integral constants.  The new value takes the type of the left argument.
  50 //   3. If DefOne is true, a null return value indicates a value of 1, if DefOne
  51 //      is false, a null return value indicates a value of 0.
  52 //
  53 inline const ConstPoolInt *Add(ConstantPool &CP, const ConstPoolInt *Arg1,
  54                                const ConstPoolInt *Arg2, bool DefOne = false) {
  55   if (DefOne == false) { // Handle degenerate cases first...
  56     if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0
  57     if (Arg2 == 0) return Arg1;
  58   } else {               // These aren't degenerate... :(
  59     if (Arg1 == 0 && Arg2 == 0) return getIntegralConstant(CP, 2, Type::UIntTy);
  60     if (Arg1 == 0) Arg1 = getIntegralConstant(CP, 1, Arg2->getType());
  61     if (Arg2 == 0) Arg2 = getIntegralConstant(CP, 1, Arg2->getType());
  62   }
  63
  64   assert(Arg1 && Arg2 && "No null arguments should exist now!");
  65
  66   // FIXME: Make types compatible!
  67
  68   // Actually perform the computation now!
  69   ConstPoolVal *Result = *Arg1 + *Arg2;
  70   assert(Result && Result->getType()->isIntegral() && "Couldn't perform add!");
  71   ConstPoolInt *ResultI = (ConstPoolInt*)Result;
  72
  73   // Check to see if the result is one of the special cases that we want to
  74   // recognize...
  75   if (ResultI->equals(DefOne ? 1 : 0)) {
  76     // Yes it is, simply delete the constant and return null.
  77     delete ResultI;
  78     return 0;
  79   }
  80
  81   CP.insert(ResultI);
  82   return ResultI;
  83 }
  84
  85
  86 ExprAnalysisResult ExprAnalysisResult::operator+(const ConstPoolInt *NewOff) {
  87   if (NewOff == 0) return *this;   // No change!
  88
  89   ConstantPool &CP = (ConstantPool&)NewOff->getParent()->getConstantPool();
  90   return ExprAnalysisResult(Scale, Var, Add(CP, Offset, NewOff));
  91 }
  92
  93
  94 // Mult - Helper function to make later code simpler.  Basically it just
  95 // multiplies the two constants together, inserts the result into the constant
  96 // pool, and returns it.  Of course life is not simple, and this is no
  97 // exception.  Factors that complicate matters:
  98 //   1. Either argument may be null.  If this is the case, the null argument is
  99 //      treated as either 0 (if DefOne = false) or 1 (if DefOne = true)
 100 //   2. Types get in the way.  We want to do arithmetic operations without
 101 //      regard for the underlying types.  It is assumed that the constants are
 102 //      integral constants.
 103 //   3. If DefOne is true, a null return value indicates a value of 1, if DefOne
 104 //      is false, a null return value indicates a value of 0.
 105 //
 106 inline const ConstPoolInt *Mult(ConstantPool &CP, const ConstPoolInt *Arg1,
 107                                 const ConstPoolInt *Arg2, bool DefOne = false) {
 108   if (DefOne == false) { // Handle degenerate cases first...
 109     if (Arg1 == 0 || Arg2 == 0) return 0;  // 0 * x == 0
 110   } else {               // These aren't degenerate... :(
 111     if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0
 112     if (Arg2 == 0) return Arg1;
 113   }
 114   assert(Arg1 && Arg2 && "No null arguments should exist now!");
 115
 116   // FIXME: Make types compatible!
 117
 118   // Actually perform the computation now!
 119   ConstPoolVal *Result = *Arg1 * *Arg2;
 120   assert(Result && Result->getType()->isIntegral() && "Couldn't perform mult!");
 121   ConstPoolInt *ResultI = (ConstPoolInt*)Result;
 122
 123   // Check to see if the result is one of the special cases that we want to
 124   // recognize...
 125   if (ResultI->equals(DefOne ? 1 : 0)) {
 126     // Yes it is, simply delete the constant and return null.
 127     delete ResultI;
 128     return 0;
 129   }
 130
 131   CP.insert(ResultI);
 132   return ResultI;
 133 }
 134
 135
 136 // ClassifyExpression: Analyze an expression to determine the complexity of the
 137 // expression, and which other values it depends on.
 138 //
 139 // Note that this analysis cannot get into infinite loops because it treats PHI
 140 // nodes as being an unknown linear expression.
 141 //
 142 ExprAnalysisResult ClassifyExpression(Value *Expr) {
 143   assert(Expr != 0 && "Can't classify a null expression!");
 144   switch (Expr->getValueType()) {
 145   case Value::InstructionVal: break;    // Instruction... hmmm... investigate.
 146   case Value::TypeVal:   case Value::BasicBlockVal:
 147   case Value::MethodVal: case Value::ModuleVal:
 148     assert(0 && "Unexpected expression type to classify!");
 149   case Value::MethodArgumentVal:        // Method arg: nothing known, return var
 150     return Expr;
 151   case Value::ConstantVal:              // Constant value, just return constant
 152     ConstPoolVal *CPV = Expr->castConstantAsserting();
 153     if (CPV->getType()->isIntegral()) { // It's an integral constant!
 154       ConstPoolInt *CPI = (ConstPoolInt*)Expr;
 155       return ExprAnalysisResult(CPI->equals(0) ? 0 : (ConstPoolInt*)Expr);
 156     }
 157     return Expr;
 158   }
 159
 160   Instruction *I = Expr->castInstructionAsserting();
 161   ConstantPool &CP = I->getParent()->getParent()->getConstantPool();
 162
 163   switch (I->getOpcode()) {       // Handle each instruction type seperately
 164   case Instruction::Add: {
 165     ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0)));
 166     ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1)));
 167     if (LeftTy.ExprType > RightTy.ExprType)
 168       swap(LeftTy, RightTy);   // Make left be simpler than right
 169
 170     switch (LeftTy.ExprType) {
 171     case ExprAnalysisResult::Constant:
 172       return RightTy + LeftTy.Offset;
 173     case ExprAnalysisResult::Linear:        // RHS side must be linear or scaled
 174     case ExprAnalysisResult::ScaledLinear:  // RHS must be scaled
 175       if (LeftTy.Var != RightTy.Var)        // Are they the same variables?
 176         return ExprAnalysisResult(I);       //   if not, we don't know anything!
 177
 178       const ConstPoolInt *NewScale  = Add(CP, LeftTy.Scale, RightTy.Scale,true);
 179       const ConstPoolInt *NewOffset = Add(CP, LeftTy.Offset, RightTy.Offset);
 180       return ExprAnalysisResult(NewScale, LeftTy.Var, NewOffset);
 181     }
 182   }  // end case Instruction::Add
 183
 184   case Instruction::Shl: {
 185     ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1)));
 186     if (RightTy.ExprType != ExprAnalysisResult::Constant)
 187       break;  // TODO: Can get some info if it's (<unsigned> X + <offset>)
 188
 189     ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0)));
 190     if (RightTy.Offset == 0) return LeftTy;   // shl x, 0 = x
 191     assert(RightTy.Offset->getType() == Type::UByteTy &&
 192            "Shift amount must always be a unsigned byte!");
 193     uint64_t ShiftAmount = ((ConstPoolUInt*)RightTy.Offset)->getValue();
 194     ConstPoolUInt *Multiplier = getUnsignedConstant(CP, 1ULL << ShiftAmount);
 195
 196     return ExprAnalysisResult(Mult(CP, LeftTy.Scale, Multiplier, true),
 197                               LeftTy.Var,
 198                               Mult(CP, LeftTy.Offset, Multiplier));
 199   }  // end case Instruction::Shl
 200
 201     // TODO: Handle CAST, SUB, MULT (at least!)
 202
 203   }  // end switch
 204
 205   // Otherwise, I don't know anything about this value!
 206   return ExprAnalysisResult(I);
 207 }