X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FExpressions.cpp;h=bfab20c42c8f49feee9ee64c444956ba50664cef;hb=c53544af06acf3fba1788613a364f1f40317869e;hp=ac6bdc1105a91f90f5323a09564c1144707b8666;hpb=369bbeb62cef986b6eb5213c9edab1a4c4f157af;p=oota-llvm.git diff --git a/lib/Analysis/Expressions.cpp b/lib/Analysis/Expressions.cpp index ac6bdc1105a..bfab20c42c8 100644 --- a/lib/Analysis/Expressions.cpp +++ b/lib/Analysis/Expressions.cpp @@ -8,36 +8,85 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/Expressions.h" -#include "llvm/Optimizations/ConstantHandling.h" -#include "llvm/ConstantPool.h" -#include "llvm/Method.h" -#include "llvm/BasicBlock.h" - -using namespace opt; // Get all the constant handling stuff +#include "llvm/ConstantHandling.h" +#include "llvm/Function.h" + +ExprType::ExprType(Value *Val) { + if (Val) + if (ConstantInt *CPI = dyn_cast(Val)) { + Offset = CPI; + Var = 0; + ExprTy = Constant; + Scale = 0; + return; + } -// getIntegralConstant - Wrapper around the ConstPoolInt member of the same -// name. This method first checks to see if the desired constant is already in -// the constant pool. If it is, it is quickly recycled, otherwise a new one -// is allocated and added to the constant pool. -// -static ConstPoolInt *getIntegralConstant(ConstantPool &CP, unsigned char V, - const Type *Ty) { - // FIXME: Lookup prexisting constant in table! + Var = Val; Offset = 0; + ExprTy = Var ? Linear : Constant; + Scale = 0; +} - ConstPoolInt *CPI = ConstPoolInt::get(Ty, V); - CP.insert(CPI); - return CPI; +ExprType::ExprType(const ConstantInt *scale, Value *var, + const ConstantInt *offset) { + Scale = var ? scale : 0; Var = var; Offset = offset; + ExprTy = Scale ? ScaledLinear : (Var ? Linear : Constant); + if (Scale && Scale->isNullValue()) { // Simplify 0*Var + const + Scale = 0; Var = 0; + ExprTy = Constant; + } } -static ConstPoolUInt *getUnsignedConstant(ConstantPool &CP, uint64_t V) { - // FIXME: Lookup prexisting constant in table! - ConstPoolUInt *CPUI = new ConstPoolUInt(Type::ULongTy, V); - CP.insert(CPUI); - return CPUI; +const Type *ExprType::getExprType(const Type *Default) const { + if (Offset) return Offset->getType(); + if (Scale) return Scale->getType(); + return Var ? Var->getType() : Default; } + +class DefVal { + const ConstantInt * const Val; + const Type * const Ty; +protected: + inline DefVal(const ConstantInt *val, const Type *ty) : Val(val), Ty(ty) {} +public: + inline const Type *getType() const { return Ty; } + inline const ConstantInt *getVal() const { return Val; } + inline operator const ConstantInt * () const { return Val; } + inline const ConstantInt *operator->() const { return Val; } +}; + +struct DefZero : public DefVal { + inline DefZero(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {} + inline DefZero(const ConstantInt *val) : DefVal(val, val->getType()) {} +}; + +struct DefOne : public DefVal { + inline DefOne(const ConstantInt *val, const Type *ty) : DefVal(val, ty) {} +}; + + +// getUnsignedConstant - Return a constant value of the specified type. If the +// constant value is not valid for the specified type, return null. This cannot +// happen for values in the range of 0 to 127. +// +static ConstantInt *getUnsignedConstant(uint64_t V, const Type *Ty) { + if (isa(Ty)) Ty = Type::ULongTy; + if (Ty->isSigned()) { + // If this value is not a valid unsigned value for this type, return null! + if (V > 127 && ((int64_t)V < 0 || + !ConstantSInt::isValueValidForType(Ty, (int64_t)V))) + return 0; + return ConstantSInt::get(Ty, V); + } else { + // If this value is not a valid unsigned value for this type, return null! + if (V > 255 && !ConstantUInt::isValueValidForType(Ty, V)) + return 0; + return ConstantUInt::get(Ty, V); + } +} + // Add - Helper function to make later code simpler. Basically it just adds // the two constants together, inserts the result into the constant pool, and // returns it. Of course life is not simple, and this is no exception. Factors @@ -50,48 +99,45 @@ static ConstPoolUInt *getUnsignedConstant(ConstantPool &CP, uint64_t V) { // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne // is false, a null return value indicates a value of 0. // -inline const ConstPoolInt *Add(ConstantPool &CP, const ConstPoolInt *Arg1, - const ConstPoolInt *Arg2, bool DefOne = false) { - if (DefOne == false) { // Handle degenerate cases first... - if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0 - if (Arg2 == 0) return Arg1; - } else { // These aren't degenerate... :( - if (Arg1 == 0 && Arg2 == 0) return getIntegralConstant(CP, 2, Type::UIntTy); - if (Arg1 == 0) Arg1 = getIntegralConstant(CP, 1, Arg2->getType()); - if (Arg2 == 0) Arg2 = getIntegralConstant(CP, 1, Arg2->getType()); - } - +static const ConstantInt *Add(const ConstantInt *Arg1, + const ConstantInt *Arg2, bool DefOne) { assert(Arg1 && Arg2 && "No null arguments should exist now!"); - - // FIXME: Make types compatible! + assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); // Actually perform the computation now! - ConstPoolVal *Result = *Arg1 + *Arg2; - assert(Result && Result->getType()->isIntegral() && "Couldn't perform add!"); - ConstPoolInt *ResultI = (ConstPoolInt*)Result; + Constant *Result = *Arg1 + *Arg2; + assert(Result && Result->getType() == Arg1->getType() && + "Couldn't perform addition!"); + ConstantInt *ResultI = cast(Result); // Check to see if the result is one of the special cases that we want to // recognize... - if (ResultI->equals(DefOne ? 1 : 0)) { - // Yes it is, simply delete the constant and return null. - delete ResultI; - return 0; - } + if (ResultI->equalsInt(DefOne ? 1 : 0)) + return 0; // Yes it is, simply return null. - CP.insert(ResultI); return ResultI; } +inline const ConstantInt *operator+(const DefZero &L, const DefZero &R) { + if (L == 0) return R; + if (R == 0) return L; + return Add(L, R, false); +} -ExprAnalysisResult ExprAnalysisResult::operator+(const ConstPoolInt *NewOff) { - if (NewOff == 0) return *this; // No change! - - ConstantPool &CP = (ConstantPool&)NewOff->getParent()->getConstantPool(); - return ExprAnalysisResult(Scale, Var, Add(CP, Offset, NewOff)); +inline const ConstantInt *operator+(const DefOne &L, const DefOne &R) { + if (L == 0) { + if (R == 0) + return getUnsignedConstant(2, L.getType()); + else + return Add(getUnsignedConstant(1, L.getType()), R, true); + } else if (R == 0) { + return Add(L, getUnsignedConstant(1, L.getType()), true); + } + return Add(L, R, true); } -// Mult - Helper function to make later code simpler. Basically it just +// Mul - Helper function to make later code simpler. Basically it just // multiplies the two constants together, inserts the result into the constant // pool, and returns it. Of course life is not simple, and this is no // exception. Factors that complicate matters: @@ -103,35 +149,78 @@ ExprAnalysisResult ExprAnalysisResult::operator+(const ConstPoolInt *NewOff) { // 3. If DefOne is true, a null return value indicates a value of 1, if DefOne // is false, a null return value indicates a value of 0. // -inline const ConstPoolInt *Mult(ConstantPool &CP, const ConstPoolInt *Arg1, - const ConstPoolInt *Arg2, bool DefOne = false) { - if (DefOne == false) { // Handle degenerate cases first... - if (Arg1 == 0 || Arg2 == 0) return 0; // 0 * x == 0 - } else { // These aren't degenerate... :( - if (Arg1 == 0) return Arg2; // Also handles case of Arg1 == Arg2 == 0 - if (Arg2 == 0) return Arg1; - } +inline const ConstantInt *Mul(const ConstantInt *Arg1, + const ConstantInt *Arg2, bool DefOne) { assert(Arg1 && Arg2 && "No null arguments should exist now!"); - - // FIXME: Make types compatible! + assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); // Actually perform the computation now! - ConstPoolVal *Result = *Arg1 * *Arg2; - assert(Result && Result->getType()->isIntegral() && "Couldn't perform mult!"); - ConstPoolInt *ResultI = (ConstPoolInt*)Result; + Constant *Result = *Arg1 * *Arg2; + assert(Result && Result->getType() == Arg1->getType() && + "Couldn't perform multiplication!"); + ConstantInt *ResultI = cast(Result); // Check to see if the result is one of the special cases that we want to // recognize... - if (ResultI->equals(DefOne ? 1 : 0)) { - // Yes it is, simply delete the constant and return null. - delete ResultI; - return 0; - } + if (ResultI->equalsInt(DefOne ? 1 : 0)) + return 0; // Yes it is, simply return null. - CP.insert(ResultI); return ResultI; } +inline const ConstantInt *operator*(const DefZero &L, const DefZero &R) { + if (L == 0 || R == 0) return 0; + return Mul(L, R, false); +} +inline const ConstantInt *operator*(const DefOne &L, const DefZero &R) { + if (R == 0) return getUnsignedConstant(0, L.getType()); + if (L == 0) return R->equalsInt(1) ? 0 : R.getVal(); + return Mul(L, R, true); +} +inline const ConstantInt *operator*(const DefZero &L, const DefOne &R) { + if (L == 0 || R == 0) return L.getVal(); + return Mul(R, L, false); +} + +// handleAddition - Add two expressions together, creating a new expression that +// represents the composite of the two... +// +static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) { + const Type *Ty = V->getType(); + if (Left.ExprTy > Right.ExprTy) + std::swap(Left, Right); // Make left be simpler than right + + switch (Left.ExprTy) { + case ExprType::Constant: + return ExprType(Right.Scale, Right.Var, + DefZero(Right.Offset, Ty) + DefZero(Left.Offset, Ty)); + case ExprType::Linear: // RHS side must be linear or scaled + case ExprType::ScaledLinear: // RHS must be scaled + if (Left.Var != Right.Var) // Are they the same variables? + return V; // if not, we don't know anything! + + return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty), + Right.Var, + DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty)); + default: + assert(0 && "Dont' know how to handle this case!"); + return ExprType(); + } +} + +// negate - Negate the value of the specified expression... +// +static inline ExprType negate(const ExprType &E, Value *V) { + const Type *Ty = V->getType(); + ConstantInt *Zero = getUnsignedConstant(0, Ty); + ConstantInt *One = getUnsignedConstant(1, Ty); + ConstantInt *NegOne = cast(*Zero - *One); + if (NegOne == 0) return V; // Couldn't subtract values... + + return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var, + DefZero(E.Offset, Ty) * NegOne); +} + // ClassifyExpression: Analyze an expression to determine the complexity of the // expression, and which other values it depends on. @@ -139,69 +228,120 @@ inline const ConstPoolInt *Mult(ConstantPool &CP, const ConstPoolInt *Arg1, // Note that this analysis cannot get into infinite loops because it treats PHI // nodes as being an unknown linear expression. // -ExprAnalysisResult ClassifyExpression(Value *Expr) { +ExprType ClassifyExpression(Value *Expr) { assert(Expr != 0 && "Can't classify a null expression!"); + if (Expr->getType() == Type::FloatTy || Expr->getType() == Type::DoubleTy) + return Expr; // FIXME: Can't handle FP expressions + switch (Expr->getValueType()) { case Value::InstructionVal: break; // Instruction... hmmm... investigate. case Value::TypeVal: case Value::BasicBlockVal: - case Value::MethodVal: case Value::ModuleVal: - assert(0 && "Unexpected expression type to classify!"); - case Value::MethodArgumentVal: // Method arg: nothing known, return var + case Value::FunctionVal: default: + //assert(0 && "Unexpected expression type to classify!"); + std::cerr << "Bizarre thing to expr classify: " << Expr << "\n"; + return Expr; + case Value::GlobalVariableVal: // Global Variable & Function argument: + case Value::ArgumentVal: // nothing known, return variable itself return Expr; case Value::ConstantVal: // Constant value, just return constant - ConstPoolVal *CPV = Expr->castConstantAsserting(); - if (CPV->getType()->isIntegral()) { // It's an integral constant! - ConstPoolInt *CPI = (ConstPoolInt*)Expr; - return ExprAnalysisResult(CPI->equals(0) ? 0 : (ConstPoolInt*)Expr); - } + if (ConstantInt *CPI = dyn_cast(cast(Expr))) + // It's an integral constant! + return ExprType(CPI->isNullValue() ? 0 : CPI); return Expr; } - Instruction *I = Expr->castInstructionAsserting(); - ConstantPool &CP = I->getParent()->getParent()->getConstantPool(); + Instruction *I = cast(Expr); + const Type *Ty = I->getType(); switch (I->getOpcode()) { // Handle each instruction type seperately case Instruction::Add: { - ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0))); - ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1))); - if (LeftTy.ExprType > RightTy.ExprType) - swap(LeftTy, RightTy); // Make left be simpler than right - - switch (LeftTy.ExprType) { - case ExprAnalysisResult::Constant: - return RightTy + LeftTy.Offset; - case ExprAnalysisResult::Linear: // RHS side must be linear or scaled - case ExprAnalysisResult::ScaledLinear: // RHS must be scaled - if (LeftTy.Var != RightTy.Var) // Are they the same variables? - return ExprAnalysisResult(I); // if not, we don't know anything! - - const ConstPoolInt *NewScale = Add(CP, LeftTy.Scale, RightTy.Scale,true); - const ConstPoolInt *NewOffset = Add(CP, LeftTy.Offset, RightTy.Offset); - return ExprAnalysisResult(NewScale, LeftTy.Var, NewOffset); - } + ExprType Left (ClassifyExpression(I->getOperand(0))); + ExprType Right(ClassifyExpression(I->getOperand(1))); + return handleAddition(Left, Right, I); } // end case Instruction::Add - case Instruction::Shl: { - ExprAnalysisResult RightTy(ClassifyExpression(I->getOperand(1))); - if (RightTy.ExprType != ExprAnalysisResult::Constant) - break; // TODO: Can get some info if it's ( X + ) + case Instruction::Sub: { + ExprType Left (ClassifyExpression(I->getOperand(0))); + ExprType Right(ClassifyExpression(I->getOperand(1))); + ExprType RightNeg = negate(Right, I); + if (RightNeg.Var == I && !RightNeg.Offset && !RightNeg.Scale) + return I; // Could not negate value... + return handleAddition(Left, RightNeg, I); + } // end case Instruction::Sub - ExprAnalysisResult LeftTy (ClassifyExpression(I->getOperand(0))); - if (RightTy.Offset == 0) return LeftTy; // shl x, 0 = x - assert(RightTy.Offset->getType() == Type::UByteTy && + case Instruction::Shl: { + ExprType Right(ClassifyExpression(I->getOperand(1))); + if (Right.ExprTy != ExprType::Constant) break; + ExprType Left(ClassifyExpression(I->getOperand(0))); + if (Right.Offset == 0) return Left; // shl x, 0 = x + assert(Right.Offset->getType() == Type::UByteTy && "Shift amount must always be a unsigned byte!"); - uint64_t ShiftAmount = ((ConstPoolUInt*)RightTy.Offset)->getValue(); - ConstPoolUInt *Multiplier = getUnsignedConstant(CP, 1ULL << ShiftAmount); - - return ExprAnalysisResult(Mult(CP, LeftTy.Scale, Multiplier, true), - LeftTy.Var, - Mult(CP, LeftTy.Offset, Multiplier)); + uint64_t ShiftAmount = ((ConstantUInt*)Right.Offset)->getValue(); + ConstantInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty); + + // We don't know how to classify it if they are shifting by more than what + // is reasonable. In most cases, the result will be zero, but there is one + // class of cases where it is not, so we cannot optimize without checking + // for it. The case is when you are shifting a signed value by 1 less than + // the number of bits in the value. For example: + // %X = shl sbyte %Y, ubyte 7 + // will try to form an sbyte multiplier of 128, which will give a null + // multiplier, even though the result is not 0. Until we can check for this + // case, be conservative. TODO. + // + if (Multiplier == 0) + return Expr; + + return ExprType(DefOne(Left.Scale, Ty) * Multiplier, Left.Var, + DefZero(Left.Offset, Ty) * Multiplier); } // end case Instruction::Shl - // TODO: Handle CAST, SUB, MULT (at least!) + case Instruction::Mul: { + ExprType Left (ClassifyExpression(I->getOperand(0))); + ExprType Right(ClassifyExpression(I->getOperand(1))); + if (Left.ExprTy > Right.ExprTy) + std::swap(Left, Right); // Make left be simpler than right + + if (Left.ExprTy != ExprType::Constant) // RHS must be > constant + return I; // Quadratic eqn! :( + + const ConstantInt *Offs = Left.Offset; + if (Offs == 0) return ExprType(); + return ExprType( DefOne(Right.Scale , Ty) * Offs, Right.Var, + DefZero(Right.Offset, Ty) * Offs); + } // end case Instruction::Mul + + case Instruction::Cast: { + ExprType Src(ClassifyExpression(I->getOperand(0))); + const Type *DestTy = I->getType(); + if (isa(DestTy)) + DestTy = Type::ULongTy; // Pointer types are represented as ulong + + /* + if (!Src.getExprType(0)->isLosslesslyConvertableTo(DestTy)) { + if (Src.ExprTy != ExprType::Constant) + return I; // Converting cast, and not a constant value... + } + */ + + const ConstantInt *Offset = Src.Offset; + const ConstantInt *Scale = Src.Scale; + if (Offset) { + const Constant *CPV = ConstantFoldCastInstruction(Offset, DestTy); + if (!CPV) return I; + Offset = cast(CPV); + } + if (Scale) { + const Constant *CPV = ConstantFoldCastInstruction(Scale, DestTy); + if (!CPV) return I; + Scale = cast(CPV); + } + return ExprType(Scale, Src.Var, Offset); + } // end case Instruction::Cast + // TODO: Handle SUB, SHR? } // end switch // Otherwise, I don't know anything about this value! - return ExprAnalysisResult(I); + return I; }