diff options
Diffstat (limited to 'polly/lib/Support/SCEVValidator.cpp')
-rw-r--r-- | polly/lib/Support/SCEVValidator.cpp | 231 |
1 files changed, 231 insertions, 0 deletions
diff --git a/polly/lib/Support/SCEVValidator.cpp b/polly/lib/Support/SCEVValidator.cpp new file mode 100644 index 00000000000..52de6bc087c --- /dev/null +++ b/polly/lib/Support/SCEVValidator.cpp @@ -0,0 +1,231 @@ + +#include "polly/Support/SCEVValidator.h" + +#include "llvm/Analysis/ScalarEvolution.h" +#include "llvm/Analysis/ScalarEvolutionExpressions.h" +#include "llvm/Analysis/RegionInfo.h" + +using namespace llvm; + +namespace SCEVType { + enum TYPE {INT, PARAM, IV, INVALID}; +} + +struct ValidatorResult { + SCEVType::TYPE type; + + ValidatorResult() : type(SCEVType::INVALID) {}; + + ValidatorResult(const ValidatorResult &vres) { + type = vres.type; + }; + + ValidatorResult(SCEVType::TYPE type) : type(type) {}; + + bool isConstant() { + return type == SCEVType::INT || type == SCEVType::PARAM; + } + + bool isValid() { + return type != SCEVType::INVALID; + } + + bool isIV() { + return type == SCEVType::IV; + } + + bool isINT() { + return type == SCEVType::INT; + } +}; + +/// Check if a SCEV is valid in a SCoP. +struct SCEVValidator + : public SCEVVisitor<SCEVValidator, struct ValidatorResult> { +private: + const Region *R; + ScalarEvolution &SE; + Value **BaseAddress; + +public: + SCEVValidator(const Region *R, ScalarEvolution &SE, + Value **BaseAddress) : R(R), SE(SE), + BaseAddress(BaseAddress) {}; + + struct ValidatorResult visitConstant(const SCEVConstant *Constant) { + return ValidatorResult(SCEVType::INT); + } + + struct ValidatorResult visitTruncateExpr(const SCEVTruncateExpr* Expr) { + ValidatorResult Op = visit(Expr->getOperand()); + + // We currently do not represent a truncate expression as an affine + // expression. If it is constant during Scop execution, we treat it as a + // parameter, otherwise we bail out. + if (Op.isConstant()) + return ValidatorResult(SCEVType::PARAM); + + return ValidatorResult (SCEVType::INVALID); + } + + struct ValidatorResult visitZeroExtendExpr(const SCEVZeroExtendExpr * Expr) { + ValidatorResult Op = visit(Expr->getOperand()); + + // We currently do not represent a zero extend expression as an affine + // expression. If it is constant during Scop execution, we treat it as a + // parameter, otherwise we bail out. + if (Op.isConstant()) + return ValidatorResult (SCEVType::PARAM); + + return ValidatorResult(SCEVType::INVALID); + } + + struct ValidatorResult visitSignExtendExpr(const SCEVSignExtendExpr* Expr) { + // We currently allow only signed SCEV expressions. In the case of a + // signed value, a sign extend is a noop. + // + // TODO: Reconsider this when we add support for unsigned values. + return visit(Expr->getOperand()); + } + + struct ValidatorResult visitAddExpr(const SCEVAddExpr* Expr) { + ValidatorResult Return(SCEVType::INT); + + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { + ValidatorResult Op = visit(Expr->getOperand(i)); + + if (!Op.isValid()) + return ValidatorResult(SCEVType::INVALID); + + Return.type = std::max(Return.type, Op.type); + } + + // TODO: Check for NSW and NUW. + return Return; + } + + struct ValidatorResult visitMulExpr(const SCEVMulExpr* Expr) { + ValidatorResult Return(SCEVType::INT); + + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { + ValidatorResult Op = visit(Expr->getOperand(i)); + + if (Op.type == SCEVType::INT) + continue; + + if (Op.type == SCEVType::INVALID || Return.type != SCEVType::INT) + return ValidatorResult(SCEVType::INVALID); + + Return.type = Op.type; + } + + // TODO: Check for NSW and NUW. + return Return; + } + + struct ValidatorResult visitUDivExpr(const SCEVUDivExpr* Expr) { + ValidatorResult LHS = visit(Expr->getLHS()); + ValidatorResult RHS = visit(Expr->getRHS()); + + // We currently do not represent a unsigned devision as an affine + // expression. If the division is constant during Scop execution we treat it + // as a parameter, otherwise we bail out. + if (LHS.isConstant() && RHS.isConstant()) + return ValidatorResult(SCEVType::PARAM); + + return ValidatorResult(SCEVType::INVALID); + } + + struct ValidatorResult visitAddRecExpr(const SCEVAddRecExpr* Expr) { + if (!Expr->isAffine()) + return ValidatorResult(SCEVType::INVALID); + + ValidatorResult Start = visit(Expr->getStart()); + ValidatorResult Recurrence = visit(Expr->getStepRecurrence(SE)); + + if (!Start.isValid() || !Recurrence.isValid() || Recurrence.isIV()) + return ValidatorResult(SCEVType::INVALID); + + + if (!R->contains(Expr->getLoop())) { + if (Start.isIV()) + return ValidatorResult(SCEVType::INVALID); + else + return ValidatorResult(SCEVType::PARAM); + } + + if (!Recurrence.isINT()) + return ValidatorResult(SCEVType::INVALID); + + return ValidatorResult(SCEVType::IV); + } + + struct ValidatorResult visitSMaxExpr(const SCEVSMaxExpr* Expr) { + ValidatorResult Return(SCEVType::INT); + + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { + ValidatorResult Op = visit(Expr->getOperand(i)); + + if (!Op.isValid()) + return ValidatorResult(SCEVType::INVALID); + + Return.type = std::max(Return.type, Op.type); + } + + return Return; + } + + struct ValidatorResult visitUMaxExpr(const SCEVUMaxExpr* Expr) { + // We do not support unsigned operations. If 'Expr' is constant during Scop + // execution we treat this as a parameter, otherwise we bail out. + for (int i = 0, e = Expr->getNumOperands(); i < e; ++i) { + ValidatorResult Op = visit(Expr->getOperand(i)); + + if (!Op.isConstant()) + return ValidatorResult(SCEVType::INVALID); + } + + return ValidatorResult(SCEVType::PARAM); + } + + ValidatorResult visitUnknown(const SCEVUnknown* Expr) { + Value *V = Expr->getValue(); + + if (isa<UndefValue>(V)) + return ValidatorResult(SCEVType::INVALID); + + if (BaseAddress) { + if (*BaseAddress) + return ValidatorResult(SCEVType::INVALID); + else + *BaseAddress = V; + } + + if (Instruction *I = dyn_cast<Instruction>(Expr->getValue())) + if (R->contains(I)) + return ValidatorResult(SCEVType::INVALID); + + if (BaseAddress) + return ValidatorResult(SCEVType::PARAM); + else + return ValidatorResult(SCEVType::PARAM); + } +}; + +namespace polly { + bool isAffineExpr(const Region *R, const SCEV *Expr, ScalarEvolution &SE, + Value **BaseAddress) { + if (isa<SCEVCouldNotCompute>(Expr)) + return false; + + if (BaseAddress) + *BaseAddress = NULL; + + SCEVValidator Validator(R, SE, BaseAddress); + ValidatorResult Result = Validator.visit(Expr); + + return Result.isValid(); + } +} + + |