diff options
Diffstat (limited to 'polly/lib/Analysis/ScopDetection.cpp')
-rw-r--r-- | polly/lib/Analysis/ScopDetection.cpp | 231 |
1 files changed, 5 insertions, 226 deletions
diff --git a/polly/lib/Analysis/ScopDetection.cpp b/polly/lib/Analysis/ScopDetection.cpp index 883fe2ceafc..efc7dfa3f85 100644 --- a/polly/lib/Analysis/ScopDetection.cpp +++ b/polly/lib/Analysis/ScopDetection.cpp @@ -48,6 +48,7 @@ #include "polly/LinkAllPasses.h" #include "polly/Support/ScopHelper.h" +#include "polly/Support/SCEVValidator.h" #include "polly/Support/AffineSCEVIterator.h" #include "llvm/LLVMContext.h" @@ -108,227 +109,6 @@ BADSCOP_STAT(Other, "Others"); //===----------------------------------------------------------------------===// // ScopDetection. - -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: - static bool isValid(const Region *R, const SCEV *Scev, - ScalarEvolution &SE, - Value **BaseAddress = NULL) { - if (isa<SCEVCouldNotCompute>(Scev)) - return false; - - if (BaseAddress) - *BaseAddress = NULL; - - SCEVValidator Validator(R, SE, BaseAddress); - ValidatorResult Result = Validator.visit(Scev); - - return Result.isValid(); - } - - 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); - } -}; - bool ScopDetection::isMaxRegionInScop(const Region &R) const { // The Region is valid only if it could be found in the set. return ValidRegions.count(&R); @@ -457,8 +237,8 @@ bool ScopDetection::isValidCFG(BasicBlock &BB, DetectionContext &Context) const const SCEV *ScevLHS = SE->getSCEV(ICmp->getOperand(0)); const SCEV *ScevRHS = SE->getSCEV(ICmp->getOperand(1)); - bool affineLHS = SCEVValidator::isValid(&Context.CurRegion, ScevLHS, *SE); - bool affineRHS = SCEVValidator::isValid(&Context.CurRegion, ScevRHS, *SE); + bool affineLHS = isAffineExpr(&Context.CurRegion, ScevLHS, *SE); + bool affineRHS = isAffineExpr(&Context.CurRegion, ScevRHS, *SE); if (!affineLHS || !affineRHS) INVALID(AffFunc, "Non affine branch in BB: " + BB.getNameStr()); @@ -499,8 +279,7 @@ bool ScopDetection::isValidMemoryAccess(Instruction &Inst, Value *Ptr = getPointerOperand(Inst), *BasePtr; const SCEV *AccessFunction = SE->getSCEV(Ptr); - if (!SCEVValidator::isValid(&Context.CurRegion, AccessFunction, *SE, - &BasePtr)) + if (!isAffineExpr(&Context.CurRegion, AccessFunction, *SE, &BasePtr)) INVALID(AffFunc, "Bad memory address " << *AccessFunction); // FIXME: Also check with isValidAffineFunction, as for the moment it is @@ -628,7 +407,7 @@ bool ScopDetection::isValidLoop(Loop *L, DetectionContext &Context) const { // Is the loop count affine? const SCEV *LoopCount = SE->getBackedgeTakenCount(L); - if (!SCEVValidator::isValid(&Context.CurRegion, LoopCount, *SE)) + if (!isAffineExpr(&Context.CurRegion, LoopCount, *SE)) INVALID(LoopBound, "Non affine loop bound '" << *LoopCount << "' in loop: " << L->getHeader()->getNameStr()); |