Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -327,6 +327,9 @@ BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock); + /// Add all recorded assumptions to the assumed context. + void addRecordedAssumptions(); + /// Create a MemoryAccess for reading the value of a phi. /// /// The modeling assumes that all incoming blocks write their incoming value Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -1624,6 +1624,24 @@ /// 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; +}; + /// Static Control Part /// /// A Scop is the polyhedral representation of a control flow region detected @@ -1782,24 +1800,7 @@ /// need to be "false". Otherwise they behave the same. isl::set InvalidContext; - /// 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; - }; - + using RecordedAssumptionsTy = SmallVector; /// Collection to hold taken assumptions. /// /// There are two reasons why we want to record assumptions first before we @@ -1810,7 +1811,7 @@ /// 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. - SmallVector RecordedAssumptions; + RecordedAssumptionsTy RecordedAssumptions; /// The schedule of the SCoP /// @@ -2338,6 +2339,12 @@ InvariantEquivClasses.end()); } + /// Return an iterator range containing hold assumptions. + iterator_range + recorded_assumptions() const { + return make_range(RecordedAssumptions.begin(), RecordedAssumptions.end()); + } + /// Return whether this scop is empty, i.e. contains no statements that /// could be executed. bool isEmpty() const { return Stmts.empty(); } @@ -2494,6 +2501,9 @@ /// @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. @@ -2559,9 +2569,6 @@ void recordAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc, AssumptionSign Sign, BasicBlock *BB = nullptr); - /// Add all recorded assumptions to the assumed context. - void addRecordedAssumptions(); - /// Mark the scop as invalid. /// /// This method adds an assumption to the scop that is always invalid. As a Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -385,6 +385,40 @@ return Descriptor; } +void ScopBuilder::addRecordedAssumptions() { + for (auto &AS : llvm::reverse(scop->recorded_assumptions())) { + + if (!AS.BB) { + scop->addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, + nullptr /* BasicBlock */); + continue; + } + + // If the domain was deleted the assumptions are void. + isl_set *Dom = scop->getDomainConditions(AS.BB).release(); + if (!Dom) + continue; + + // If a basic block was given use its domain to simplify the assumption. + // In case of restrictions we know they only have to hold on the domain, + // thus we can intersect them with the domain of the block. However, for + // assumptions the domain has to imply them, thus: + // _ _____ + // Dom => S <==> A v B <==> A - B + // + // To avoid the complement we will register A - B as a restriction not an + // assumption. + isl_set *S = AS.Set.copy(); + if (AS.Sign == AS_RESTRICTION) + S = isl_set_params(isl_set_intersect(S, Dom)); + else /* (AS.Sign == AS_ASSUMPTION) */ + S = isl_set_params(isl_set_subtract(Dom, S)); + + scop->addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.BB); + } + scop->clearRecordedAssumptions(); +} + bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); @@ -1972,7 +2006,7 @@ // After the context was fully constructed, thus all our knowledge about // the parameters is in there, we add all recorded assumptions to the // assumed/invalid context. - scop->addRecordedAssumptions(); + addRecordedAssumptions(); scop->simplifyContexts(); if (!scop->buildAliasChecks(AA)) { Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -3779,39 +3779,6 @@ RecordedAssumptions.push_back({Kind, Sign, Set, Loc, BB}); } -void Scop::addRecordedAssumptions() { - while (!RecordedAssumptions.empty()) { - Assumption AS = RecordedAssumptions.pop_back_val(); - - if (!AS.BB) { - addAssumption(AS.Kind, AS.Set, AS.Loc, AS.Sign, nullptr /* BasicBlock */); - continue; - } - - // If the domain was deleted the assumptions are void. - isl_set *Dom = getDomainConditions(AS.BB).release(); - if (!Dom) - continue; - - // If a basic block was given use its domain to simplify the assumption. - // In case of restrictions we know they only have to hold on the domain, - // thus we can intersect them with the domain of the block. However, for - // assumptions the domain has to imply them, thus: - // _ _____ - // Dom => S <==> A v B <==> A - B - // - // To avoid the complement we will register A - B as a restriction not an - // assumption. - isl_set *S = AS.Set.copy(); - if (AS.Sign == AS_RESTRICTION) - S = isl_set_params(isl_set_intersect(S, Dom)); - else /* (AS.Sign == AS_ASSUMPTION) */ - S = isl_set_params(isl_set_subtract(Dom, S)); - - addAssumption(AS.Kind, isl::manage(S), AS.Loc, AS_RESTRICTION, AS.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);