Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -61,6 +61,18 @@ // The Scop std::unique_ptr scop; + /// Collection to hold taken assumptions. + /// + /// There are two reasons why we want to record assumptions first before we + /// add them to the assumed/invalid context: + /// 1) If the SCoP is not profitable or otherwise invalid without the + /// assumed/invalid context we do not have to compute it. + /// 2) Information about the context are gathered rather late in the SCoP + /// construction (basically after we know all parameters), thus the user + /// might see overly complicated assumptions to be taken while they will + /// only be simplified later on. + RecordedAssumptionsTy RecordedAssumptions; + // Methods for pattern matching against Fortran code generated by dragonegg. // @{ Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -19,6 +19,7 @@ #include "polly/ScopDetection.h" #include "polly/Support/SCEVAffinator.h" +#include "polly/Support/ScopHelper.h" #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/MapVector.h" #include "llvm/ADT/SetVector.h" @@ -54,23 +55,6 @@ // are also unlikely to result in good code. extern int const MaxDisjunctsInDomain; -/// Enumeration of assumptions Polly can take. -enum AssumptionKind { - ALIASING, - INBOUNDS, - WRAPPING, - UNSIGNED, - PROFITABLE, - ERRORBLOCK, - COMPLEXITY, - INFINITELOOP, - INVARIANTLOAD, - DELINEARIZATION, -}; - -/// Enum to distinguish between assumptions and restrictions. -enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION }; - /// The different memory kinds used in Polly. /// /// We distinguish between arrays and various scalar memory objects. We use @@ -633,7 +617,7 @@ isl::basic_map createBasicAccessMap(ScopStmt *Statement); - void assumeNoOutOfBound(); + isl::set assumeNoOutOfBound(); /// Compute bounds on an over approximated access relation. /// @@ -1624,24 +1608,6 @@ /// Print ScopStmt S to raw_ostream OS. raw_ostream &operator<<(raw_ostream &OS, const ScopStmt &S); -/// Helper struct to remember assumptions. -struct Assumption { - /// The kind of the assumption (e.g., WRAPPING). - AssumptionKind Kind; - - /// Flag to distinguish assumptions and restrictions. - AssumptionSign Sign; - - /// The valid/invalid context if this is an assumption/restriction. - isl::set Set; - - /// The location that caused this assumption. - DebugLoc Loc; - - /// An optional block whose domain can simplify the assumption. - BasicBlock *BB; -}; - /// Build the conditions sets for the branch condition @p Condition in /// the @p Domain. /// @@ -1838,19 +1804,6 @@ /// need to be "false". Otherwise they behave the same. isl::set InvalidContext; - using RecordedAssumptionsTy = SmallVector; - /// Collection to hold taken assumptions. - /// - /// There are two reasons why we want to record assumptions first before we - /// add them to the assumed/invalid context: - /// 1) If the SCoP is not profitable or otherwise invalid without the - /// assumed/invalid context we do not have to compute it. - /// 2) Information about the context are gathered rather late in the SCoP - /// construction (basically after we know all parameters), thus the user - /// might see overly complicated assumptions to be taken while they will - /// only be simplified later on. - RecordedAssumptionsTy RecordedAssumptions; - /// The schedule of the SCoP /// /// The schedule of the SCoP describes the execution order of the statements @@ -2129,12 +2082,6 @@ InvariantEquivClasses.end()); } - /// Return an iterator range containing hold assumptions. - iterator_range - recorded_assumptions() const { - return make_range(RecordedAssumptions.begin(), RecordedAssumptions.end()); - } - /// Return an iterator range containing all the MemoryAccess objects of the /// Scop. iterator_range access_functions() { @@ -2297,9 +2244,6 @@ /// @returns True if the optimized SCoP can be executed. bool hasFeasibleRuntimeContext() const; - /// Clear assumptions which have been already processed. - void clearRecordedAssumptions() { return RecordedAssumptions.clear(); } - /// Check if the assumption in @p Set is trivial or not. /// /// @param Set The relations between parameters that are assumed to hold. @@ -2347,24 +2291,6 @@ void addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB); - /// Record an assumption for later addition to the assumed context. - /// - /// This function will add the assumption to the RecordedAssumptions. This - /// collection will be added (@see addAssumption) to the assumed context once - /// all paramaters are known and the context is fully built. - /// - /// @param Kind The assumption kind describing the underlying cause. - /// @param Set The relations between parameters that are assumed to hold. - /// @param Loc The location in the source that caused this assumption. - /// @param Sign Enum to indicate if the assumptions in @p Set are positive - /// (needed/assumptions) or negative (invalid/restrictions). - /// @param BB The block in which this assumption was taken. If it is - /// set, the domain of that block will be used to simplify the - /// actual assumption in @p Set once it is added. This is useful - /// if the assumption was created prior to the domain. - void recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, - AssumptionSign Sign, BasicBlock *BB = nullptr); - /// Mark the scop as invalid. /// /// This method adds an assumption to the scop that is always invalid. As a @@ -2504,7 +2430,7 @@ /// /// @returns The ScopArrayInfo pointer or NULL if no such pointer is /// available. - const ScopArrayInfo *getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind); + ScopArrayInfo *getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind); /// Return the cached ScopArrayInfo object for @p BasePtr. /// @@ -2513,7 +2439,7 @@ /// /// @returns The ScopArrayInfo pointer (may assert if no such pointer is /// available). - const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind); + ScopArrayInfo *getScopArrayInfo(Value *BasePtr, MemoryKind Kind); /// Invalidate ScopArrayInfo object for base address. /// @@ -2589,13 +2515,16 @@ /// a dummy value of appropriate dimension is returned. This allows to bail /// for complex cases without "error handling code" needed on the users side. PWACtx getPwAff(const SCEV *E, BasicBlock *BB = nullptr, - bool NonNegative = false); + bool NonNegative = false, + RecordedAssumptionsTy *RecordedAssumptions = nullptr); /// Compute the isl representation for the SCEV @p E /// /// This function is like @see Scop::getPwAff() but strips away the invalid /// domain part associated with the piecewise affine function. - isl::pw_aff getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr); + isl::pw_aff + getPwAffOnly(const SCEV *E, BasicBlock *BB = nullptr, + RecordedAssumptionsTy *RecordedAssumptions = nullptr); /// Check if an AddRec for the loop L is cached. bool hasNSWAddRecForLoop(Loop *L) { return Affinator.hasNSWAddRecForLoop(L); } Index: polly/include/polly/Support/SCEVAffinator.h =================================================================== --- polly/include/polly/Support/SCEVAffinator.h +++ polly/include/polly/Support/SCEVAffinator.h @@ -13,6 +13,7 @@ #ifndef POLLY_SCEV_AFFINATOR_H #define POLLY_SCEV_AFFINATOR_H +#include "polly/Support/ScopHelper.h" #include "llvm/Analysis/ScalarEvolutionExpressions.h" #include "isl/isl-noexceptions.h" @@ -36,10 +37,12 @@ /// @param BB The block in which @p E is executed. /// /// @returns The isl representation of the SCEV @p E in @p Domain. - PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr); + PWACtx getPwAff(const llvm::SCEV *E, llvm::BasicBlock *BB = nullptr, + RecordedAssumptionsTy *RecordedAssumptions = nullptr); /// Take the assumption that @p PWAC is non-negative. - void takeNonNegativeAssumption(PWACtx &PWAC); + void takeNonNegativeAssumption( + PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions = nullptr); /// Interpret the PWA in @p PWAC as an unsigned value. void interpretAsUnsigned(PWACtx &PWAC, unsigned Width); @@ -87,31 +90,49 @@ /// @param PWAC The isl representation of @p Expr with the invalid domain. /// /// @returns The isl representation @p PWAC with a possibly adjusted domain. - PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC) const; + PWACtx checkForWrapping(const llvm::SCEV *Expr, PWACtx PWAC, + RecordedAssumptionsTy *RecordedAssumptions) const; /// Whether to track the value of this expression precisely, rather than /// assuming it won't wrap. bool computeModuloForExpr(const llvm::SCEV *Expr); - PWACtx visit(const llvm::SCEV *E); - PWACtx visitConstant(const llvm::SCEVConstant *E); - PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E); - PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E); - PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E); - PWACtx visitAddExpr(const llvm::SCEVAddExpr *E); - PWACtx visitMulExpr(const llvm::SCEVMulExpr *E); - PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E); - PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E); - PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E); - PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E); - PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E); - PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E); - PWACtx visitUnknown(const llvm::SCEVUnknown *E); - PWACtx visitSDivInstruction(llvm::Instruction *SDiv); - PWACtx visitSRemInstruction(llvm::Instruction *SRem); + PWACtx visit(const llvm::SCEV *E, RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSCEV(const llvm::SCEV *S, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitConstant(const llvm::SCEVConstant *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitTruncateExpr(const llvm::SCEVTruncateExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitZeroExtendExpr(const llvm::SCEVZeroExtendExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSignExtendExpr(const llvm::SCEVSignExtendExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitAddExpr(const llvm::SCEVAddExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitMulExpr(const llvm::SCEVMulExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitUDivExpr(const llvm::SCEVUDivExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitAddRecExpr(const llvm::SCEVAddRecExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSMaxExpr(const llvm::SCEVSMaxExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSMinExpr(const llvm::SCEVSMinExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitUMaxExpr(const llvm::SCEVUMaxExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitUMinExpr(const llvm::SCEVUMinExpr *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitUnknown(const llvm::SCEVUnknown *E, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitCouldNotCompute(const llvm::SCEVCouldNotCompute *S, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSDivInstruction(llvm::Instruction *SDiv, + RecordedAssumptionsTy *RecordedAssumptions); + PWACtx visitSRemInstruction(llvm::Instruction *SRem, + RecordedAssumptionsTy *RecordedAssumptions); PWACtx complexityBailout(); - - friend struct llvm::SCEVVisitor; }; } // namespace polly Index: polly/include/polly/Support/ScopHelper.h =================================================================== --- polly/include/polly/Support/ScopHelper.h +++ polly/include/polly/Support/ScopHelper.h @@ -17,6 +17,7 @@ #include "llvm/IR/Instructions.h" #include "llvm/IR/IntrinsicInst.h" #include "llvm/IR/ValueHandle.h" +#include "isl/isl-noexceptions.h" namespace llvm { class LoopInfo; @@ -34,6 +35,63 @@ class Scop; class ScopStmt; +/// Enumeration of assumptions Polly can take. +enum AssumptionKind { + ALIASING, + INBOUNDS, + WRAPPING, + UNSIGNED, + PROFITABLE, + ERRORBLOCK, + COMPLEXITY, + INFINITELOOP, + INVARIANTLOAD, + DELINEARIZATION, +}; + +/// Enum to distinguish between assumptions and restrictions. +enum AssumptionSign { AS_ASSUMPTION, AS_RESTRICTION }; + +/// Helper struct to remember assumptions. +struct Assumption { + /// The kind of the assumption (e.g., WRAPPING). + AssumptionKind Kind; + + /// Flag to distinguish assumptions and restrictions. + AssumptionSign Sign; + + /// The valid/invalid context if this is an assumption/restriction. + isl::set Set; + + /// The location that caused this assumption. + llvm::DebugLoc Loc; + + /// An optional block whose domain can simplify the assumption. + llvm::BasicBlock *BB; +}; + +using RecordedAssumptionsTy = llvm::SmallVector; + +/// Record an assumption for later addition to the assumed context. +/// +/// This function will add the assumption to the RecordedAssumptions. This +/// collection will be added (@see addAssumption) to the assumed context once +/// all paramaters are known and the context is fully built. +/// +/// @param RecordedAssumption container which keeps all recorded assumptions. +/// @param Kind The assumption kind describing the underlying cause. +/// @param Set The relations between parameters that are assumed to hold. +/// @param Loc The location in the source that caused this assumption. +/// @param Sign Enum to indicate if the assumptions in @p Set are positive +/// (needed/assumptions) or negative (invalid/restrictions). +/// @param BB The block in which this assumption was taken. If it is +/// set, the domain of that block will be used to simplify the +/// actual assumption in @p Set once it is added. This is useful +/// if the assumption was created prior to the domain. +void recordAssumption(RecordedAssumptionsTy *RecordedAssumptions, + AssumptionKind Kind, isl::set Set, llvm::DebugLoc Loc, + AssumptionSign Sign, llvm::BasicBlock *BB = nullptr); + /// Type to remap values. using ValueMapT = llvm::DenseMap, llvm::AssertingVH>; Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -96,6 +96,11 @@ " their loads. "), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); +static cl::opt + PollyIgnoreInbounds("polly-ignore-inbounds", + cl::desc("Do not take inbounds assumptions at all"), + cl::Hidden, cl::init(false), cl::cat(PollyCategory)); + static cl::opt RunTimeChecksMaxArraysPerGroup( "polly-rtc-max-arrays-per-group", cl::desc("The maximal number of arrays to compare in each alias group."), @@ -344,7 +349,7 @@ ScopBuilder::getPwAff(BasicBlock *BB, DenseMap &InvalidDomainMap, const SCEV *E, bool NonNegative) { - PWACtx PWAC = scop->getPwAff(E, BB, NonNegative); + PWACtx PWAC = scop->getPwAff(E, BB, NonNegative, &RecordedAssumptions); InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second); return PWAC.first.release(); } @@ -796,9 +801,8 @@ return true; isl::set UnboundedCtx = Parts.first.params(); - scop->recordAssumption(INFINITELOOP, UnboundedCtx, - HeaderBB->getTerminator()->getDebugLoc(), - AS_RESTRICTION); + recordAssumption(&RecordedAssumptions, INFINITELOOP, UnboundedCtx, + HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION); return true; } @@ -1019,9 +1023,8 @@ } else { InvalidDomain = Domain; isl::set DomPar = Domain.params(); - scop->recordAssumption(ERRORBLOCK, DomPar, - BB->getTerminator()->getDebugLoc(), - AS_RESTRICTION); + recordAssumption(&RecordedAssumptions, ERRORBLOCK, DomPar, + BB->getTerminator()->getDebugLoc(), AS_RESTRICTION); Domain = isl::set::empty(Domain.get_space()); } @@ -1488,7 +1491,7 @@ } void ScopBuilder::addRecordedAssumptions() { - for (auto &AS : llvm::reverse(scop->recorded_assumptions())) { + for (auto &AS : llvm::reverse(RecordedAssumptions)) { if (!AS.BB) { scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, @@ -1518,7 +1521,6 @@ scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB); } - scop->clearRecordedAssumptions(); } void ScopBuilder::addUserAssumptions( @@ -2502,9 +2504,17 @@ } void ScopBuilder::assumeNoOutOfBounds() { + if (PollyIgnoreInbounds) + return; for (auto &Stmt : *scop) - for (auto &Access : Stmt) - Access->assumeNoOutOfBound(); + for (auto &Access : Stmt) { + isl::set Outside = Access->assumeNoOutOfBound(); + const auto &Loc = Access->getAccessInstruction() + ? Access->getAccessInstruction()->getDebugLoc() + : DebugLoc(); + recordAssumption(&RecordedAssumptions, INBOUNDS, Outside, Loc, + AS_ASSUMPTION); + } } void ScopBuilder::ensureValueWrite(Instruction *Inst) { @@ -3214,8 +3224,26 @@ else Ty = MemoryKind::Array; + // Create isl::pw_aff for SCEVs which describe sizes. Collect all + // assumptions which are taken. isl::pw_aff objects are cached internally and + // they are used later by scop. + for (auto &size : Access->Sizes) { + if (!size) + continue; + scop->getPwAff(size, nullptr, false, &RecordedAssumptions); + } auto *SAI = scop->getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(), ElementType, Access->Sizes, Ty); + + // Create isl::pw_aff for SCEVs which describe subscripts. Collect all + // assumptions which are taken. isl::pw_aff objects are cached internally and + // they are used later by scop. + for (auto &subscript : Access->Subscripts) { + if (!Access->isAffine() || !subscript) + continue; + scop->getPwAff(subscript, Stmt.getEntryBlock(), false, + &RecordedAssumptions); + } Access->buildAccessRelation(SAI); scop->addAccessData(Access); } @@ -3768,6 +3796,7 @@ InfeasibleScops++; Msg = "SCoP ends here but was dismissed."; LLVM_DEBUG(dbgs() << "SCoP detected but dismissed\n"); + RecordedAssumptions.clear(); scop.reset(); } else { Msg = "SCoP ends here."; Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -133,11 +133,6 @@ cl::desc("Take more precise inbounds assumptions (do not scale well)"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); -static cl::opt - PollyIgnoreInbounds("polly-ignore-inbounds", - cl::desc("Do not take inbounds assumptions at all"), - cl::Hidden, cl::init(false), cl::cat(PollyCategory)); - static cl::opt PollyIgnoreParamBounds( "polly-ignore-parameter-bounds", cl::desc( @@ -662,9 +657,7 @@ // possibly yield out of bound memory accesses. The complement of these // constraints is the set of constraints that needs to be assumed to ensure such // statement instances are never executed. -void MemoryAccess::assumeNoOutOfBound() { - if (PollyIgnoreInbounds) - return; +isl::set MemoryAccess::assumeNoOutOfBound() { auto *SAI = getScopArrayInfo(); isl::space Space = getOriginalAccessRelationSpace().range(); isl::set Outside = isl::set::empty(Space); @@ -692,13 +685,10 @@ // bail out more often than strictly necessary. Outside = Outside.remove_divs(); Outside = Outside.complement(); - const auto &Loc = getAccessInstruction() - ? getAccessInstruction()->getDebugLoc() - : DebugLoc(); + if (!PollyPreciseInbounds) Outside = Outside.gist_params(Statement->getDomain().params()); - Statement->getParent()->recordAssumption(INBOUNDS, Outside, Loc, - AS_ASSUMPTION); + return Outside; } void MemoryAccess::buildMemIntrinsicAccessRelation() { @@ -1856,13 +1846,12 @@ return SAI; } -const ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, - MemoryKind Kind) { +ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind) { auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get(); return SAI; } -const ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) { +ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) { auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind); assert(SAI && "No ScopArrayInfo available for this base pointer"); return SAI; @@ -2117,13 +2106,6 @@ InvalidContext = InvalidContext.unite(Set).coalesce(); } -void Scop::recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, - AssumptionSign Sign, BasicBlock *BB) { - assert((Set.is_params() || BB) && - "Assumptions without a basic block must be parameter sets"); - RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB}); -} - void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) { LLVM_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n"); addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB); @@ -2241,13 +2223,14 @@ isl::ctx Scop::getIslCtx() const { return IslCtx.get(); } __isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB, - bool NonNegative) { + bool NonNegative, + RecordedAssumptionsTy *RecordedAssumptions) { // First try to use the SCEVAffinator to generate a piecewise defined // affine function from @p E in the context of @p BB. If that tasks becomes to // complex the affinator might return a nullptr. In such a case we invalidate // the SCoP and return a dummy value. This way we do not need to add error // handling code to all users of this function. - auto PWAC = Affinator.getPwAff(E, BB); + auto PWAC = Affinator.getPwAff(E, BB, RecordedAssumptions); if (PWAC.first) { // TODO: We could use a heuristic and either use: // SCEVAffinator::takeNonNegativeAssumption @@ -2255,13 +2238,13 @@ // SCEVAffinator::interpretAsUnsigned // to deal with unsigned or "NonNegative" SCEVs. if (NonNegative) - Affinator.takeNonNegativeAssumption(PWAC); + Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions); return PWAC; } auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc(); invalidate(COMPLEXITY, DL, BB); - return Affinator.getPwAff(SE->getZero(E->getType()), BB); + return Affinator.getPwAff(SE->getZero(E->getType()), BB, RecordedAssumptions); } isl::union_set Scop::getDomains() const { @@ -2274,8 +2257,9 @@ return isl::manage(Domain); } -isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB) { - PWACtx PWAC = getPwAff(E, BB); +isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB, + RecordedAssumptionsTy *RecordedAssumptions) { + PWACtx PWAC = getPwAff(E, BB, RecordedAssumptions); return PWAC.first; } Index: polly/lib/Support/SCEVAffinator.cpp =================================================================== --- polly/lib/Support/SCEVAffinator.cpp +++ polly/lib/Support/SCEVAffinator.cpp @@ -95,22 +95,25 @@ NonNegPWA, isl_pw_aff_add(PWAC.first.release(), ExpPWA))); } -void SCEVAffinator::takeNonNegativeAssumption(PWACtx &PWAC) { +void SCEVAffinator::takeNonNegativeAssumption( + PWACtx &PWAC, RecordedAssumptionsTy *RecordedAssumptions) { + auto *NegPWA = isl_pw_aff_neg(PWAC.first.copy()); auto *NegDom = isl_pw_aff_pos_set(NegPWA); PWAC.second = isl::manage(isl_set_union(PWAC.second.release(), isl_set_copy(NegDom))); auto *Restriction = BB ? NegDom : isl_set_params(NegDom); auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc(); - S->recordAssumption(UNSIGNED, isl::manage(Restriction), DL, AS_RESTRICTION, - BB); + recordAssumption(RecordedAssumptions, UNSIGNED, isl::manage(Restriction), DL, + AS_RESTRICTION, BB); } PWACtx SCEVAffinator::getPWACtxFromPWA(isl::pw_aff PWA) { return std::make_pair(PWA, isl::set::empty(isl::space(Ctx, 0, NumIterators))); } -PWACtx SCEVAffinator::getPwAff(const SCEV *Expr, BasicBlock *BB) { +PWACtx SCEVAffinator::getPwAff(const SCEV *Expr, BasicBlock *BB, + RecordedAssumptionsTy *RecordedAssumptions) { this->BB = BB; if (BB) { @@ -120,10 +123,12 @@ } else NumIterators = 0; - return visit(Expr); + return visit(Expr, RecordedAssumptions); } -PWACtx SCEVAffinator::checkForWrapping(const SCEV *Expr, PWACtx PWAC) const { +PWACtx SCEVAffinator::checkForWrapping( + const SCEV *Expr, PWACtx PWAC, + RecordedAssumptionsTy *RecordedAssumptions) const { // If the SCEV flags do contain NSW (no signed wrap) then PWA already // represents Expr in modulo semantic (it is not allowed to overflow), thus we // are done. Otherwise, we will compute: @@ -145,7 +150,8 @@ NotEqualSet = NotEqualSet.coalesce(); if (!NotEqualSet.is_empty()) - S->recordAssumption(WRAPPING, NotEqualSet, Loc, AS_RESTRICTION, BB); + recordAssumption(RecordedAssumptions, WRAPPING, NotEqualSet, Loc, + AS_RESTRICTION, BB); return PWAC; } @@ -187,7 +193,8 @@ return Width <= MaxSmallBitWidth; } -PWACtx SCEVAffinator::visit(const SCEV *Expr) { +PWACtx SCEVAffinator::visit(const SCEV *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { auto Key = std::make_pair(Expr, BB); PWACtx PWAC = CachedExpressions[Key]; @@ -215,15 +222,16 @@ PWAC = getPWACtxFromPWA(isl::manage(isl_pw_aff_alloc(Domain, Affine))); } else { - PWAC = SCEVVisitor::visit(Expr); + PWAC = visitSCEV(Expr, RecordedAssumptions); if (computeModuloForExpr(Expr)) PWAC.first = addModuloSemantic(PWAC.first, Expr->getType()); else - PWAC = checkForWrapping(Expr, PWAC); + PWAC = checkForWrapping(Expr, PWAC, RecordedAssumptions); } if (!Factor->getType()->isIntegerTy(1)) { - PWAC = combine(PWAC, visitConstant(Factor), isl_pw_aff_mul); + PWAC = combine(PWAC, visitConstant(Factor, RecordedAssumptions), + isl_pw_aff_mul); if (computeModuloForExpr(Key.first)) PWAC.first = addModuloSemantic(PWAC.first, Expr->getType()); } @@ -232,13 +240,59 @@ // return it. PWAC.first = PWAC.first.coalesce(); if (!computeModuloForExpr(Key.first)) - PWAC = checkForWrapping(Key.first, PWAC); + PWAC = checkForWrapping(Key.first, PWAC, RecordedAssumptions); CachedExpressions[Key] = PWAC; return PWAC; } -PWACtx SCEVAffinator::visitConstant(const SCEVConstant *Expr) { +PWACtx SCEVAffinator::visitSCEV(const SCEV *S, + RecordedAssumptionsTy *RecordedAssumptions) { + switch (S->getSCEVType()) { + case scConstant: + return visitConstant((const SCEVConstant *)S, RecordedAssumptions); + case scTruncate: + return visitTruncateExpr((const SCEVTruncateExpr *)S, RecordedAssumptions); + case scZeroExtend: + return visitZeroExtendExpr((const SCEVZeroExtendExpr *)S, + RecordedAssumptions); + case scSignExtend: + return visitSignExtendExpr((const SCEVSignExtendExpr *)S, + RecordedAssumptions); + case scAddExpr: + return visitAddExpr((const SCEVAddExpr *)S, RecordedAssumptions); + case scMulExpr: + return visitMulExpr((const SCEVMulExpr *)S, RecordedAssumptions); + case scUDivExpr: + return visitUDivExpr((const SCEVUDivExpr *)S, RecordedAssumptions); + case scAddRecExpr: + return visitAddRecExpr((const SCEVAddRecExpr *)S, RecordedAssumptions); + case scSMaxExpr: + return visitSMaxExpr((const SCEVSMaxExpr *)S, RecordedAssumptions); + case scUMaxExpr: + return visitUMaxExpr((const SCEVUMaxExpr *)S, RecordedAssumptions); + case scSMinExpr: + return visitSMinExpr((const SCEVSMinExpr *)S, RecordedAssumptions); + case scUMinExpr: + return visitUMinExpr((const SCEVUMinExpr *)S, RecordedAssumptions); + case scUnknown: + return visitUnknown((const SCEVUnknown *)S, RecordedAssumptions); + case scCouldNotCompute: + return visitCouldNotCompute((const SCEVCouldNotCompute *)S, + RecordedAssumptions); + default: + llvm_unreachable("Unknown SCEV type!"); + } +} + +PWACtx SCEVAffinator::visitCouldNotCompute( + const SCEVCouldNotCompute *S, RecordedAssumptionsTy *RecordedAssumptions) { + llvm_unreachable("Invalid use of SCEVCouldNotCompute!"); +} + +PWACtx +SCEVAffinator::visitConstant(const SCEVConstant *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { ConstantInt *Value = Expr->getValue(); isl_val *v; @@ -260,14 +314,16 @@ isl::manage(isl_pw_aff_from_aff(isl_aff_val_on_domain(ls, v)))); } -PWACtx SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr) { +PWACtx +SCEVAffinator::visitTruncateExpr(const SCEVTruncateExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { // Truncate operations are basically modulo operations, thus we can // model them that way. However, for large types we assume the operand // to fit in the new type size instead of introducing a modulo with a very // large constant. auto *Op = Expr->getOperand(); - auto OpPWAC = visit(Op); + auto OpPWAC = visit(Op, RecordedAssumptions); unsigned Width = TD.getTypeSizeInBits(Expr->getType()); @@ -289,13 +345,15 @@ OutOfBoundsDom = isl_set_params(OutOfBoundsDom); } - S->recordAssumption(UNSIGNED, isl::manage(OutOfBoundsDom), DebugLoc(), - AS_RESTRICTION, BB); + recordAssumption(RecordedAssumptions, UNSIGNED, isl::manage(OutOfBoundsDom), + DebugLoc(), AS_RESTRICTION, BB); return OpPWAC; } -PWACtx SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr) { +PWACtx +SCEVAffinator::visitZeroExtendExpr(const SCEVZeroExtendExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { // A zero-extended value can be interpreted as a piecewise defined signed // value. If the value was non-negative it stays the same, otherwise it // is the sum of the original value and 2^n where n is the bit-width of @@ -340,11 +398,11 @@ // assumptions and assume the "former negative" piece will not exist. auto *Op = Expr->getOperand(); - auto OpPWAC = visit(Op); + auto OpPWAC = visit(Op, RecordedAssumptions); // If the width is to big we assume the negative part does not occur. if (!computeModuloForExpr(Op)) { - takeNonNegativeAssumption(OpPWAC); + takeNonNegativeAssumption(OpPWAC, RecordedAssumptions); return OpPWAC; } @@ -355,16 +413,20 @@ return OpPWAC; } -PWACtx SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr) { +PWACtx +SCEVAffinator::visitSignExtendExpr(const SCEVSignExtendExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { // As all values are represented as signed, a sign extension is a noop. - return visit(Expr->getOperand()); + return visit(Expr->getOperand(), RecordedAssumptions); } -PWACtx SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr) { - PWACtx Sum = visit(Expr->getOperand(0)); +PWACtx SCEVAffinator::visitAddExpr(const SCEVAddExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { + PWACtx Sum = visit(Expr->getOperand(0), RecordedAssumptions); for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) { - Sum = combine(Sum, visit(Expr->getOperand(i)), isl_pw_aff_add); + Sum = combine(Sum, visit(Expr->getOperand(i), RecordedAssumptions), + isl_pw_aff_add); if (isTooComplex(Sum)) return complexityBailout(); } @@ -372,11 +434,13 @@ return Sum; } -PWACtx SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr) { - PWACtx Prod = visit(Expr->getOperand(0)); +PWACtx SCEVAffinator::visitMulExpr(const SCEVMulExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { + PWACtx Prod = visit(Expr->getOperand(0), RecordedAssumptions); for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) { - Prod = combine(Prod, visit(Expr->getOperand(i)), isl_pw_aff_mul); + Prod = combine(Prod, visit(Expr->getOperand(i), RecordedAssumptions), + isl_pw_aff_mul); if (isTooComplex(Prod)) return complexityBailout(); } @@ -384,7 +448,9 @@ return Prod; } -PWACtx SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr) { +PWACtx +SCEVAffinator::visitAddRecExpr(const SCEVAddRecExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { assert(Expr->isAffine() && "Only affine AddRecurrences allowed"); auto Flags = Expr->getNoWrapFlags(); @@ -394,7 +460,7 @@ assert(S->contains(Expr->getLoop()) && "Scop does not contain the loop referenced in this AddRec"); - PWACtx Step = visit(Expr->getOperand(1)); + PWACtx Step = visit(Expr->getOperand(1), RecordedAssumptions); isl_space *Space = isl_space_set_alloc(Ctx.get(), 0, NumIterators); isl_local_space *LocalSpace = isl_local_space_from_space(Space); @@ -417,17 +483,20 @@ SE.getAddRecExpr(SE.getConstant(Expr->getStart()->getType(), 0), Expr->getStepRecurrence(SE), Expr->getLoop(), Flags); - PWACtx Result = visit(ZeroStartExpr); - PWACtx Start = visit(Expr->getStart()); + PWACtx Result = visit(ZeroStartExpr, RecordedAssumptions); + PWACtx Start = visit(Expr->getStart(), RecordedAssumptions); Result = combine(Result, Start, isl_pw_aff_add); return Result; } -PWACtx SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr) { - PWACtx Max = visit(Expr->getOperand(0)); +PWACtx +SCEVAffinator::visitSMaxExpr(const SCEVSMaxExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { + PWACtx Max = visit(Expr->getOperand(0), RecordedAssumptions); for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) { - Max = combine(Max, visit(Expr->getOperand(i)), isl_pw_aff_max); + Max = combine(Max, visit(Expr->getOperand(i), RecordedAssumptions), + isl_pw_aff_max); if (isTooComplex(Max)) return complexityBailout(); } @@ -435,11 +504,14 @@ return Max; } -PWACtx SCEVAffinator::visitSMinExpr(const SCEVSMinExpr *Expr) { - PWACtx Min = visit(Expr->getOperand(0)); +PWACtx +SCEVAffinator::visitSMinExpr(const SCEVSMinExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { + PWACtx Min = visit(Expr->getOperand(0), RecordedAssumptions); for (int i = 1, e = Expr->getNumOperands(); i < e; ++i) { - Min = combine(Min, visit(Expr->getOperand(i)), isl_pw_aff_min); + Min = combine(Min, visit(Expr->getOperand(i), RecordedAssumptions), + isl_pw_aff_min); if (isTooComplex(Min)) return complexityBailout(); } @@ -447,15 +519,21 @@ return Min; } -PWACtx SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr) { +PWACtx +SCEVAffinator::visitUMaxExpr(const SCEVUMaxExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { llvm_unreachable("SCEVUMaxExpr not yet supported"); } -PWACtx SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr) { +PWACtx +SCEVAffinator::visitUMinExpr(const SCEVUMinExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { llvm_unreachable("SCEVUMinExpr not yet supported"); } -PWACtx SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr) { +PWACtx +SCEVAffinator::visitUDivExpr(const SCEVUDivExpr *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { // The handling of unsigned division is basically the same as for signed // division, except the interpretation of the operands. As the divisor // has to be constant in both cases we can simply interpret it as an @@ -468,8 +546,8 @@ assert(isa(Divisor) && "UDiv is no parameter but has a non-constant RHS."); - auto DividendPWAC = visit(Dividend); - auto DivisorPWAC = visit(Divisor); + auto DividendPWAC = visit(Dividend, RecordedAssumptions); + auto DivisorPWAC = visit(Divisor, RecordedAssumptions); if (SE.isKnownNegative(Divisor)) { // Interpret negative divisors unsigned. This is a special case of the @@ -485,7 +563,7 @@ // precise but therefor a heuristic is needed. // Assume a non-negative dividend. - takeNonNegativeAssumption(DividendPWAC); + takeNonNegativeAssumption(DividendPWAC, RecordedAssumptions); DividendPWAC = combine(DividendPWAC, DivisorPWAC, isl_pw_aff_div); DividendPWAC.first = DividendPWAC.first.floor(); @@ -493,51 +571,56 @@ return DividendPWAC; } -PWACtx SCEVAffinator::visitSDivInstruction(Instruction *SDiv) { +PWACtx SCEVAffinator::visitSDivInstruction( + Instruction *SDiv, RecordedAssumptionsTy *RecordedAssumptions) { assert(SDiv->getOpcode() == Instruction::SDiv && "Assumed SDiv instruction!"); auto *Scope = getScope(); auto *Divisor = SDiv->getOperand(1); auto *DivisorSCEV = SE.getSCEVAtScope(Divisor, Scope); - auto DivisorPWAC = visit(DivisorSCEV); + auto DivisorPWAC = visit(DivisorSCEV, RecordedAssumptions); assert(isa(DivisorSCEV) && "SDiv is no parameter but has a non-constant RHS."); auto *Dividend = SDiv->getOperand(0); auto *DividendSCEV = SE.getSCEVAtScope(Dividend, Scope); - auto DividendPWAC = visit(DividendSCEV); + auto DividendPWAC = visit(DividendSCEV, RecordedAssumptions); DividendPWAC = combine(DividendPWAC, DivisorPWAC, isl_pw_aff_tdiv_q); return DividendPWAC; } -PWACtx SCEVAffinator::visitSRemInstruction(Instruction *SRem) { +PWACtx SCEVAffinator::visitSRemInstruction( + Instruction *SRem, RecordedAssumptionsTy *RecordedAssumptions) { assert(SRem->getOpcode() == Instruction::SRem && "Assumed SRem instruction!"); auto *Scope = getScope(); auto *Divisor = SRem->getOperand(1); auto *DivisorSCEV = SE.getSCEVAtScope(Divisor, Scope); - auto DivisorPWAC = visit(DivisorSCEV); + auto DivisorPWAC = visit(DivisorSCEV, RecordedAssumptions); assert(isa(Divisor) && "SRem is no parameter but has a non-constant RHS."); auto *Dividend = SRem->getOperand(0); auto *DividendSCEV = SE.getSCEVAtScope(Dividend, Scope); - auto DividendPWAC = visit(DividendSCEV); + auto DividendPWAC = visit(DividendSCEV, RecordedAssumptions); DividendPWAC = combine(DividendPWAC, DivisorPWAC, isl_pw_aff_tdiv_r); return DividendPWAC; } -PWACtx SCEVAffinator::visitUnknown(const SCEVUnknown *Expr) { +PWACtx SCEVAffinator::visitUnknown(const SCEVUnknown *Expr, + RecordedAssumptionsTy *RecordedAssumptions) { if (Instruction *I = dyn_cast(Expr->getValue())) { switch (I->getOpcode()) { case Instruction::IntToPtr: - return visit(SE.getSCEVAtScope(I->getOperand(0), getScope())); + return visit(SE.getSCEVAtScope(I->getOperand(0), getScope()), + RecordedAssumptions); case Instruction::PtrToInt: - return visit(SE.getSCEVAtScope(I->getOperand(0), getScope())); + return visit(SE.getSCEVAtScope(I->getOperand(0), getScope()), + RecordedAssumptions); case Instruction::SDiv: - return visitSDivInstruction(I); + return visitSDivInstruction(I, RecordedAssumptions); case Instruction::SRem: - return visitSRemInstruction(I); + return visitSRemInstruction(I, RecordedAssumptions); default: break; // Fall through. } @@ -552,5 +635,6 @@ // and return a constant zero. const DebugLoc &Loc = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc(); S->invalidate(COMPLEXITY, Loc); - return visit(SE.getZero(Type::getInt32Ty(S->getFunction().getContext()))); + return visit(SE.getZero(Type::getInt32Ty(S->getFunction().getContext())), + nullptr); } Index: polly/lib/Support/ScopHelper.cpp =================================================================== --- polly/lib/Support/ScopHelper.cpp +++ polly/lib/Support/ScopHelper.cpp @@ -221,6 +221,16 @@ polly::splitEntryBlockForAlloca(EntryBlock, DT, LI, RI); } +void polly::recordAssumption(polly::RecordedAssumptionsTy *RecordedAssumptions, + polly::AssumptionKind Kind, isl::set Set, + DebugLoc Loc, polly::AssumptionSign Sign, + BasicBlock *BB) { + assert((Set.is_params() || BB) && + "Assumptions without a basic block must be parameter sets"); + if (RecordedAssumptions) + RecordedAssumptions->push_back({Kind, Sign, Set, Loc, BB}); +} + /// The SCEVExpander will __not__ generate any code for an existing SDiv/SRem /// instruction but just use it, if it is referenced as a SCEVUnknown. We want /// however to generate new code if the instruction is in the analyzed region