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 @@ -1944,7 +1897,8 @@ /// Scop constructor; invoked from ScopBuilder::buildScop. Scop(Region &R, ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, - ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE); + ScopDetection::DetectionContext &DC, OptimizationRemarkEmitter &ORE, + RecordedAssumptionsTy &RecordedAssumptions); //@} @@ -2129,12 +2083,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 +2245,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 +2292,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 +2431,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 +2440,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. /// 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" @@ -28,7 +29,8 @@ /// Translate a SCEV to an isl::pw_aff and the domain on which it is invalid. struct SCEVAffinator : public llvm::SCEVVisitor { public: - SCEVAffinator(Scop *S, llvm::LoopInfo &LI); + SCEVAffinator(Scop *S, llvm::LoopInfo &LI, + RecordedAssumptionsTy &RecordedAssumptions); /// Translate a SCEV to an isl::pw_aff. /// @@ -63,6 +65,7 @@ llvm::ScalarEvolution &SE; llvm::LoopInfo &LI; llvm::BasicBlock *BB; + RecordedAssumptionsTy &RecordedAssumptions; /// Target data for element size computing. const llvm::DataLayout &TD; 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."), @@ -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,8 @@ } void ScopBuilder::addRecordedAssumptions() { - for (auto &AS : llvm::reverse(scop->recorded_assumptions())) { + for (auto &AS : llvm::reverse(make_range(RecordedAssumptions.begin(), + RecordedAssumptions.end()))) { if (!AS.BB) { scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, @@ -1518,7 +1522,7 @@ scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB); } - scop->clearRecordedAssumptions(); + RecordedAssumptions.clear(); } void ScopBuilder::addUserAssumptions( @@ -2490,9 +2494,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) { @@ -3585,7 +3597,8 @@ #endif void ScopBuilder::buildScop(Region &R, AssumptionCache &AC) { - scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE)); + scop.reset(new Scop(R, SE, LI, DT, *SD.getDetectionContext(&R), ORE, + RecordedAssumptions)); buildStmts(R); @@ -3756,6 +3769,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 @@ -132,11 +132,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( @@ -661,9 +656,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); @@ -691,13 +684,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() { @@ -1358,8 +1348,7 @@ if (Access) return Access; - ScopArrayInfo *SAI = - Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value); + ScopArrayInfo *SAI = Parent.getScopArrayInfo(V, MemoryKind::Value); Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(), true, {}, {}, V, MemoryKind::Value); Parent.addAccessFunction(Access); @@ -1697,10 +1686,11 @@ Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI, DominatorTree &DT, ScopDetection::DetectionContext &DC, - OptimizationRemarkEmitter &ORE) + OptimizationRemarkEmitter &ORE, + RecordedAssumptionsTy &RecordedAssumptions) : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT), R(R), name(None), HasSingleExitEdge(R.getExitingBlock()), DC(DC), - ORE(ORE), Affinator(this, LI), + ORE(ORE), Affinator(this, LI, RecordedAssumptions), ID(getNextID((*R.getEntry()->getParent()).getName().str())) { if (IslOnErrorAbort) isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT); @@ -1855,13 +1845,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; @@ -2116,13 +2105,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); Index: polly/lib/Support/SCEVAffinator.cpp =================================================================== --- polly/lib/Support/SCEVAffinator.cpp +++ polly/lib/Support/SCEVAffinator.cpp @@ -80,8 +80,10 @@ return isl_pw_aff_val_on_domain(Dom, ExpVal); } -SCEVAffinator::SCEVAffinator(Scop *S, LoopInfo &LI) +SCEVAffinator::SCEVAffinator(Scop *S, LoopInfo &LI, + RecordedAssumptionsTy &RecordedAssumptions) : S(S), Ctx(S->getIslCtx().get()), SE(*S->getSE()), LI(LI), + RecordedAssumptions(RecordedAssumptions), TD(S->getFunction().getParent()->getDataLayout()) {} Loop *SCEVAffinator::getScope() { return BB ? LI.getLoopFor(BB) : nullptr; } @@ -102,8 +104,8 @@ 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) { @@ -145,7 +147,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; } @@ -289,8 +292,8 @@ 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; } Index: polly/lib/Support/ScopHelper.cpp =================================================================== --- polly/lib/Support/ScopHelper.cpp +++ polly/lib/Support/ScopHelper.cpp @@ -152,6 +152,14 @@ // ExitBB // // / \ // } +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"); + RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB}); +} void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI, RegionInfo *RI) {