X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FExpressions.cpp;h=f6bec7d160757252a42c58fbeff42732eea93c9b;hb=4c6cb7a2b1fca93742a7751640375854bca762ae;hp=a6f889f698d21908f467c510d61bb44b81a11bf3;hpb=9636a91649f168f41b477cba705287665e054f79;p=oota-llvm.git diff --git a/lib/Analysis/Expressions.cpp b/lib/Analysis/Expressions.cpp index a6f889f698d..f6bec7d1607 100644 --- a/lib/Analysis/Expressions.cpp +++ b/lib/Analysis/Expressions.cpp @@ -1,4 +1,11 @@ -//===- Expressions.cpp - Expression Analysis Utilities ----------------------=// +//===- Expressions.cpp - Expression Analysis Utilities --------------------===// +// +// The LLVM Compiler Infrastructure +// +// This file was developed by the LLVM research group and is distributed under +// the University of Illinois Open Source License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// // // This file defines a package of expression analysis utilties: // @@ -8,30 +15,31 @@ //===----------------------------------------------------------------------===// #include "llvm/Analysis/Expressions.h" -#include "llvm/Optimizations/ConstantHandling.h" -#include "llvm/Method.h" -#include "llvm/BasicBlock.h" - -using namespace opt; // Get all the constant handling stuff -using namespace analysis; +#include "llvm/Constants.h" +#include "llvm/Function.h" +#include "llvm/Type.h" +using namespace llvm; ExprType::ExprType(Value *Val) { - if (Val && Val->isConstant() && Val->getType()->isIntegral()) { - Offset = (ConstPoolInt*)Val->castConstant(); - Var = 0; - ExprTy = Constant; - } else { - Var = Val; Offset = 0; - ExprTy = Var ? Linear : Constant; - } + if (Val) + if (ConstantInt *CPI = dyn_cast(Val)) { + Offset = CPI; + Var = 0; + ExprTy = Constant; + Scale = 0; + return; + } + + Var = Val; Offset = 0; + ExprTy = Var ? Linear : Constant; Scale = 0; } -ExprType::ExprType(const ConstPoolInt *scale, Value *var, - const ConstPoolInt *offset) { - Scale = scale; Var = var; Offset = offset; +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->equalsInt(0)) { // Simplify 0*Var + const + if (Scale && Scale->isNullValue()) { // Simplify 0*Var + const Scale = 0; Var = 0; ExprTy = Constant; } @@ -45,32 +53,48 @@ const Type *ExprType::getExprType(const Type *Default) const { } - -class DefVal { - const ConstPoolInt * const Val; - const Type * const Ty; -protected: - inline DefVal(const ConstPoolInt *val, const Type *ty) : Val(val), Ty(ty) {} -public: - inline const Type *getType() const { return Ty; } - inline const ConstPoolInt *getVal() const { return Val; } - inline operator const ConstPoolInt * () const { return Val; } - inline const ConstPoolInt *operator->() const { return Val; } -}; - -struct DefZero : public DefVal { - inline DefZero(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {} - inline DefZero(const ConstPoolInt *val) : DefVal(val, val->getType()) {} -}; - -struct DefOne : public DefVal { - inline DefOne(const ConstPoolInt *val, const Type *ty) : DefVal(val, ty) {} -}; +namespace { + 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) {} + }; +} -static ConstPoolInt *getUnsignedConstant(uint64_t V, const Type *Ty) { - if (Ty->isPointerType()) Ty = Type::ULongTy; - return Ty->isSigned() ? ConstPoolSInt::get(Ty, V) : ConstPoolUInt::get(Ty, V); +// 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 @@ -85,16 +109,15 @@ static ConstPoolInt *getUnsignedConstant(uint64_t V, const Type *Ty) { // 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. // -static const ConstPoolInt *Add(const ConstPoolInt *Arg1, - const ConstPoolInt *Arg2, bool DefOne) { +static const ConstantInt *Add(const ConstantInt *Arg1, + const ConstantInt *Arg2, bool DefOne) { assert(Arg1 && Arg2 && "No null arguments should exist now!"); assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); // Actually perform the computation now! - ConstPoolVal *Result = *Arg1 + *Arg2; - assert(Result && Result->getType() == Arg1->getType() && - "Couldn't perform addition!"); - ConstPoolInt *ResultI = (ConstPoolInt*)Result; + Constant *Result = ConstantExpr::get(Instruction::Add, (Constant*)Arg1, + (Constant*)Arg2); + ConstantInt *ResultI = cast(Result); // Check to see if the result is one of the special cases that we want to // recognize... @@ -104,13 +127,13 @@ static const ConstPoolInt *Add(const ConstPoolInt *Arg1, return ResultI; } -inline const ConstPoolInt *operator+(const DefZero &L, const DefZero &R) { +static 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); } -inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) { +static inline const ConstantInt *operator+(const DefOne &L, const DefOne &R) { if (L == 0) { if (R == 0) return getUnsignedConstant(2, L.getType()); @@ -135,16 +158,17 @@ inline const ConstPoolInt *operator+(const DefOne &L, const DefOne &R) { // 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 *Mul(const ConstPoolInt *Arg1, - const ConstPoolInt *Arg2, bool DefOne = false) { +static inline const ConstantInt *Mul(const ConstantInt *Arg1, + const ConstantInt *Arg2, bool DefOne) { assert(Arg1 && Arg2 && "No null arguments should exist now!"); assert(Arg1->getType() == Arg2->getType() && "Types must be compatible!"); // Actually perform the computation now! - ConstPoolVal *Result = *Arg1 * *Arg2; + Constant *Result = ConstantExpr::get(Instruction::Mul, (Constant*)Arg1, + (Constant*)Arg2); assert(Result && Result->getType() == Arg1->getType() && - "Couldn't perform mult!"); - ConstPoolInt *ResultI = (ConstPoolInt*)Result; + "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... @@ -154,17 +178,20 @@ inline const ConstPoolInt *Mul(const ConstPoolInt *Arg1, return ResultI; } -inline const ConstPoolInt *operator*(const DefZero &L, const DefZero &R) { - if (L == 0 || R == 0) return 0; - return Mul(L, R, false); -} -inline const ConstPoolInt *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, false); -} -inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) { - return R*L; +namespace { + 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 @@ -173,19 +200,19 @@ inline const ConstPoolInt *operator*(const DefZero &L, const DefOne &R) { static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) { const Type *Ty = V->getType(); if (Left.ExprTy > Right.ExprTy) - swap(Left, Right); // Make left be simpler than right + 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)); + 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 ExprType(V); // if not, we don't know anything! + return V; // if not, we don't know anything! return ExprType(DefOne(Left.Scale , Ty) + DefOne(Right.Scale , Ty), - Left.Var, + Right.Var, DefZero(Left.Offset, Ty) + DefZero(Right.Offset, Ty)); default: assert(0 && "Dont' know how to handle this case!"); @@ -197,10 +224,10 @@ static ExprType handleAddition(ExprType Left, ExprType Right, Value *V) { // static inline ExprType negate(const ExprType &E, Value *V) { const Type *Ty = V->getType(); - const Type *ETy = E.getExprType(Ty); - ConstPoolInt *Zero = getUnsignedConstant(0, ETy); - ConstPoolInt *One = getUnsignedConstant(1, ETy); - ConstPoolInt *NegOne = (ConstPoolInt*)(*Zero - *One); + ConstantInt *Zero = getUnsignedConstant(0, Ty); + ConstantInt *One = getUnsignedConstant(1, Ty); + ConstantInt *NegOne = cast(ConstantExpr::get(Instruction::Sub, + Zero, One)); if (NegOne == 0) return V; // Couldn't subtract values... return ExprType(DefOne (E.Scale , Ty) * NegOne, E.Var, @@ -208,93 +235,121 @@ static inline ExprType negate(const ExprType &E, Value *V) { } -// ClassifyExpression: Analyze an expression to determine the complexity of the -// expression, and which other values it depends on. +// ClassifyExpr: Analyze an expression to determine the complexity of the +// expression, and which other values it depends on. // // Note that this analysis cannot get into infinite loops because it treats PHI // nodes as being an unknown linear expression. // -ExprType analysis::ClassifyExpression(Value *Expr) { +ExprType llvm::ClassifyExpr(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: default: - assert(0 && "Unexpected expression type to classify!"); - case Value::GlobalVal: // Global Variable & Method argument: - case Value::MethodArgumentVal: // nothing known, return variable itself + 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 ExprType(CPI->equalsInt(0) ? 0 : CPI); - } + if (ConstantInt *CPI = dyn_cast(cast(Expr))) + // It's an integral constant! + return ExprType(CPI->isNullValue() ? 0 : CPI); return Expr; } Instruction *I = cast(Expr); const Type *Ty = I->getType(); - switch (I->getOpcode()) { // Handle each instruction type seperately + switch (I->getOpcode()) { // Handle each instruction type separately case Instruction::Add: { - ExprType Left (ClassifyExpression(I->getOperand(0))); - ExprType Right(ClassifyExpression(I->getOperand(1))); + ExprType Left (ClassifyExpr(I->getOperand(0))); + ExprType Right(ClassifyExpr(I->getOperand(1))); return handleAddition(Left, Right, I); } // end case Instruction::Add case Instruction::Sub: { - ExprType Left (ClassifyExpression(I->getOperand(0))); - ExprType Right(ClassifyExpression(I->getOperand(1))); - return handleAddition(Left, negate(Right, I), I); + ExprType Left (ClassifyExpr(I->getOperand(0))); + ExprType Right(ClassifyExpr(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 case Instruction::Shl: { - ExprType Right(ClassifyExpression(I->getOperand(1))); + ExprType Right(ClassifyExpr(I->getOperand(1))); if (Right.ExprTy != ExprType::Constant) break; - ExprType Left(ClassifyExpression(I->getOperand(0))); + ExprType Left(ClassifyExpr(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*)Right.Offset)->getValue(); - ConstPoolInt *Multiplier = getUnsignedConstant(1ULL << ShiftAmount, Ty); - + uint64_t ShiftAmount = cast(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 case Instruction::Mul: { - ExprType Left (ClassifyExpression(I->getOperand(0))); - ExprType Right(ClassifyExpression(I->getOperand(1))); + ExprType Left (ClassifyExpr(I->getOperand(0))); + ExprType Right(ClassifyExpr(I->getOperand(1))); if (Left.ExprTy > Right.ExprTy) - swap(Left, Right); // Make left be simpler than right + std::swap(Left, Right); // Make left be simpler than right if (Left.ExprTy != ExprType::Constant) // RHS must be > constant return I; // Quadratic eqn! :( - const ConstPoolInt *Offs = Left.Offset; + 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))); - if (Src.ExprTy != ExprType::Constant) - return I; - const ConstPoolInt *Offs = Src.Offset; - if (Offs == 0) return ExprType(); - + ExprType Src(ClassifyExpr(I->getOperand(0))); const Type *DestTy = I->getType(); - if (DestTy->isPointerType()) + if (isa(DestTy)) DestTy = Type::ULongTy; // Pointer types are represented as ulong - assert(DestTy->isIntegral() && "Can only handle integral types!"); + const Type *SrcValTy = Src.getExprType(0); + if (!SrcValTy) return I; + if (!SrcValTy->isLosslesslyConvertibleTo(DestTy)) { + if (Src.ExprTy != ExprType::Constant) + return I; // Converting cast, and not a constant value... + } - const ConstPoolVal *CPV =ConstRules::get(*Offs)->castTo(Offs, DestTy); - if (!CPV) return I; - assert(CPV->getType()->isIntegral() && "Must have an integral type!"); - return (ConstPoolInt*)CPV; + const ConstantInt *Offset = Src.Offset; + const ConstantInt *Scale = Src.Scale; + if (Offset) { + const Constant *CPV = ConstantExpr::getCast((Constant*)Offset, DestTy); + if (!isa(CPV)) return I; + Offset = cast(CPV); + } + if (Scale) { + const Constant *CPV = ConstantExpr::getCast((Constant*)Scale, DestTy); + if (!CPV) return I; + Scale = cast(CPV); + } + return ExprType(Scale, Src.Var, Offset); } // end case Instruction::Cast // TODO: Handle SUB, SHR?