summaryrefslogtreecommitdiffstats
path: root/polly/lib/Analysis/ScopInfo.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'polly/lib/Analysis/ScopInfo.cpp')
-rw-r--r--polly/lib/Analysis/ScopInfo.cpp915
1 files changed, 0 insertions, 915 deletions
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index f8f215fe003..6fc9a0a8081 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -1185,347 +1185,6 @@ void ScopStmt::realignParams() {
Domain = Domain.gist_params(Ctx);
}
-/// Add @p BSet to set @p BoundedParts if @p BSet is bounded.
-static isl::set collectBoundedParts(isl::set S) {
- isl::set BoundedParts = isl::set::empty(S.get_space());
- for (isl::basic_set BSet : S.get_basic_set_list())
- if (BSet.is_bounded())
- BoundedParts = BoundedParts.unite(isl::set(BSet));
- return BoundedParts;
-}
-
-/// Compute the (un)bounded parts of @p S wrt. to dimension @p Dim.
-///
-/// @returns A separation of @p S into first an unbounded then a bounded subset,
-/// both with regards to the dimension @p Dim.
-static std::pair<isl::set, isl::set> partitionSetParts(isl::set S,
- unsigned Dim) {
- for (unsigned u = 0, e = S.n_dim(); u < e; u++)
- S = S.lower_bound_si(isl::dim::set, u, 0);
-
- unsigned NumDimsS = S.n_dim();
- isl::set OnlyDimS = S;
-
- // Remove dimensions that are greater than Dim as they are not interesting.
- assert(NumDimsS >= Dim + 1);
- OnlyDimS = OnlyDimS.project_out(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
-
- // Create artificial parametric upper bounds for dimensions smaller than Dim
- // as we are not interested in them.
- OnlyDimS = OnlyDimS.insert_dims(isl::dim::param, 0, Dim);
-
- for (unsigned u = 0; u < Dim; u++) {
- isl::constraint C = isl::constraint::alloc_inequality(
- isl::local_space(OnlyDimS.get_space()));
- C = C.set_coefficient_si(isl::dim::param, u, 1);
- C = C.set_coefficient_si(isl::dim::set, u, -1);
- OnlyDimS = OnlyDimS.add_constraint(C);
- }
-
- // Collect all bounded parts of OnlyDimS.
- isl::set BoundedParts = collectBoundedParts(OnlyDimS);
-
- // Create the dimensions greater than Dim again.
- BoundedParts =
- BoundedParts.insert_dims(isl::dim::set, Dim + 1, NumDimsS - Dim - 1);
-
- // Remove the artificial upper bound parameters again.
- BoundedParts = BoundedParts.remove_dims(isl::dim::param, 0, Dim);
-
- isl::set UnboundedParts = S.subtract(BoundedParts);
- return std::make_pair(UnboundedParts, BoundedParts);
-}
-
-/// Create the conditions under which @p L @p Pred @p R is true.
-static isl::set buildConditionSet(ICmpInst::Predicate Pred, isl::pw_aff L,
- isl::pw_aff R) {
- switch (Pred) {
- case ICmpInst::ICMP_EQ:
- return L.eq_set(R);
- case ICmpInst::ICMP_NE:
- return L.ne_set(R);
- case ICmpInst::ICMP_SLT:
- return L.lt_set(R);
- case ICmpInst::ICMP_SLE:
- return L.le_set(R);
- case ICmpInst::ICMP_SGT:
- return L.gt_set(R);
- case ICmpInst::ICMP_SGE:
- return L.ge_set(R);
- case ICmpInst::ICMP_ULT:
- return L.lt_set(R);
- case ICmpInst::ICMP_UGT:
- return L.gt_set(R);
- case ICmpInst::ICMP_ULE:
- return L.le_set(R);
- case ICmpInst::ICMP_UGE:
- return L.ge_set(R);
- default:
- llvm_unreachable("Non integer predicate not supported");
- }
-}
-
-/// Compute the isl representation for the SCEV @p E in this BB.
-///
-/// @param S The Scop in which @p BB resides in.
-/// @param BB The BB for which isl representation is to be
-/// computed.
-/// @param InvalidDomainMap A map of BB to their invalid domains.
-/// @param E The SCEV that should be translated.
-/// @param NonNegative Flag to indicate the @p E has to be non-negative.
-///
-/// Note that this function will also adjust the invalid context accordingly.
-
-__isl_give isl_pw_aff *
-getPwAff(Scop &S, BasicBlock *BB,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap, const SCEV *E,
- bool NonNegative = false) {
- PWACtx PWAC = S.getPwAff(E, BB, NonNegative);
- InvalidDomainMap[BB] = InvalidDomainMap[BB].unite(PWAC.second);
- return PWAC.first.release();
-}
-
-/// Build the conditions sets for the switch @p SI in the @p Domain.
-///
-/// This will fill @p ConditionSets with the conditions under which control
-/// will be moved from @p SI to its successors. Hence, @p ConditionSets will
-/// have as many elements as @p SI has successors.
-bool buildConditionSets(Scop &S, BasicBlock *BB, SwitchInst *SI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
- Value *Condition = getConditionFromTerminator(SI);
- assert(Condition && "No condition for switch");
-
- ScalarEvolution &SE = *S.getSE();
- isl_pw_aff *LHS, *RHS;
- LHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEVAtScope(Condition, L));
-
- unsigned NumSuccessors = SI->getNumSuccessors();
- ConditionSets.resize(NumSuccessors);
- for (auto &Case : SI->cases()) {
- unsigned Idx = Case.getSuccessorIndex();
- ConstantInt *CaseValue = Case.getCaseValue();
-
- RHS = getPwAff(S, BB, InvalidDomainMap, SE.getSCEV(CaseValue));
- isl_set *CaseConditionSet =
- buildConditionSet(ICmpInst::ICMP_EQ, isl::manage_copy(LHS),
- isl::manage(RHS))
- .release();
- ConditionSets[Idx] = isl_set_coalesce(
- isl_set_intersect(CaseConditionSet, isl_set_copy(Domain)));
- }
-
- assert(ConditionSets[0] == nullptr && "Default condition set was set");
- isl_set *ConditionSetUnion = isl_set_copy(ConditionSets[1]);
- for (unsigned u = 2; u < NumSuccessors; u++)
- ConditionSetUnion =
- isl_set_union(ConditionSetUnion, isl_set_copy(ConditionSets[u]));
- ConditionSets[0] = isl_set_subtract(isl_set_copy(Domain), ConditionSetUnion);
-
- isl_pw_aff_free(LHS);
-
- return true;
-}
-
-/// Build condition sets for unsigned ICmpInst(s).
-/// Special handling is required for unsigned operands to ensure that if
-/// MSB (aka the Sign bit) is set for an operands in an unsigned ICmpInst
-/// it should wrap around.
-///
-/// @param IsStrictUpperBound holds information on the predicate relation
-/// between TestVal and UpperBound, i.e,
-/// TestVal < UpperBound OR TestVal <= UpperBound
-__isl_give isl_set *polly::buildUnsignedConditionSets(
- Scop &S, BasicBlock *BB, Value *Condition, __isl_keep isl_set *Domain,
- const SCEV *SCEV_TestVal, const SCEV *SCEV_UpperBound,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- bool IsStrictUpperBound) {
- // Do not take NonNeg assumption on TestVal
- // as it might have MSB (Sign bit) set.
- isl_pw_aff *TestVal = getPwAff(S, BB, InvalidDomainMap, SCEV_TestVal, false);
- // Take NonNeg assumption on UpperBound.
- isl_pw_aff *UpperBound =
- getPwAff(S, BB, InvalidDomainMap, SCEV_UpperBound, true);
-
- // 0 <= TestVal
- isl_set *First =
- isl_pw_aff_le_set(isl_pw_aff_zero_on_domain(isl_local_space_from_space(
- isl_pw_aff_get_domain_space(TestVal))),
- isl_pw_aff_copy(TestVal));
-
- isl_set *Second;
- if (IsStrictUpperBound)
- // TestVal < UpperBound
- Second = isl_pw_aff_lt_set(TestVal, UpperBound);
- else
- // TestVal <= UpperBound
- Second = isl_pw_aff_le_set(TestVal, UpperBound);
-
- isl_set *ConsequenceCondSet = isl_set_intersect(First, Second);
- return ConsequenceCondSet;
-}
-
-bool polly::buildConditionSets(
- Scop &S, BasicBlock *BB, Value *Condition, Instruction *TI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
- ScalarEvolution &SE = *S.getSE();
- isl_set *ConsequenceCondSet = nullptr;
-
- if (auto Load = dyn_cast<LoadInst>(Condition)) {
- const SCEV *LHSSCEV = SE.getSCEVAtScope(Load, L);
- const SCEV *RHSSCEV = SE.getZero(LHSSCEV->getType());
- bool NonNeg = false;
- isl_pw_aff *LHS = getPwAff(S, BB, InvalidDomainMap, LHSSCEV, NonNeg);
- isl_pw_aff *RHS = getPwAff(S, BB, InvalidDomainMap, RHSSCEV, NonNeg);
- ConsequenceCondSet = buildConditionSet(ICmpInst::ICMP_SLE, isl::manage(LHS),
- isl::manage(RHS))
- .release();
- } else if (auto *PHI = dyn_cast<PHINode>(Condition)) {
- auto *Unique = dyn_cast<ConstantInt>(
- getUniqueNonErrorValue(PHI, &S.getRegion(), *S.getLI(), *S.getDT()));
-
- if (Unique->isZero())
- ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
- else
- ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
- } else if (auto *CCond = dyn_cast<ConstantInt>(Condition)) {
- if (CCond->isZero())
- ConsequenceCondSet = isl_set_empty(isl_set_get_space(Domain));
- else
- ConsequenceCondSet = isl_set_universe(isl_set_get_space(Domain));
- } else if (BinaryOperator *BinOp = dyn_cast<BinaryOperator>(Condition)) {
- auto Opcode = BinOp->getOpcode();
- assert(Opcode == Instruction::And || Opcode == Instruction::Or);
-
- bool Valid = buildConditionSets(S, BB, BinOp->getOperand(0), TI, L, Domain,
- InvalidDomainMap, ConditionSets) &&
- buildConditionSets(S, BB, BinOp->getOperand(1), TI, L, Domain,
- InvalidDomainMap, ConditionSets);
- if (!Valid) {
- while (!ConditionSets.empty())
- isl_set_free(ConditionSets.pop_back_val());
- return false;
- }
-
- isl_set_free(ConditionSets.pop_back_val());
- isl_set *ConsCondPart0 = ConditionSets.pop_back_val();
- isl_set_free(ConditionSets.pop_back_val());
- isl_set *ConsCondPart1 = ConditionSets.pop_back_val();
-
- if (Opcode == Instruction::And)
- ConsequenceCondSet = isl_set_intersect(ConsCondPart0, ConsCondPart1);
- else
- ConsequenceCondSet = isl_set_union(ConsCondPart0, ConsCondPart1);
- } else {
- auto *ICond = dyn_cast<ICmpInst>(Condition);
- assert(ICond &&
- "Condition of exiting branch was neither constant nor ICmp!");
-
- LoopInfo &LI = *S.getLI();
- DominatorTree &DT = *S.getDT();
- Region &R = S.getRegion();
-
- isl_pw_aff *LHS, *RHS;
- // For unsigned comparisons we assumed the signed bit of neither operand
- // to be set. The comparison is equal to a signed comparison under this
- // assumption.
- bool NonNeg = ICond->isUnsigned();
- const SCEV *LeftOperand = SE.getSCEVAtScope(ICond->getOperand(0), L),
- *RightOperand = SE.getSCEVAtScope(ICond->getOperand(1), L);
-
- LeftOperand = tryForwardThroughPHI(LeftOperand, R, SE, LI, DT);
- RightOperand = tryForwardThroughPHI(RightOperand, R, SE, LI, DT);
-
- switch (ICond->getPredicate()) {
- case ICmpInst::ICMP_ULT:
- ConsequenceCondSet =
- buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
- RightOperand, InvalidDomainMap, true);
- break;
- case ICmpInst::ICMP_ULE:
- ConsequenceCondSet =
- buildUnsignedConditionSets(S, BB, Condition, Domain, LeftOperand,
- RightOperand, InvalidDomainMap, false);
- break;
- case ICmpInst::ICMP_UGT:
- ConsequenceCondSet =
- buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
- LeftOperand, InvalidDomainMap, true);
- break;
- case ICmpInst::ICMP_UGE:
- ConsequenceCondSet =
- buildUnsignedConditionSets(S, BB, Condition, Domain, RightOperand,
- LeftOperand, InvalidDomainMap, false);
- break;
- default:
- LHS = getPwAff(S, BB, InvalidDomainMap, LeftOperand, NonNeg);
- RHS = getPwAff(S, BB, InvalidDomainMap, RightOperand, NonNeg);
- ConsequenceCondSet = buildConditionSet(ICond->getPredicate(),
- isl::manage(LHS), isl::manage(RHS))
- .release();
- break;
- }
- }
-
- // If no terminator was given we are only looking for parameter constraints
- // under which @p Condition is true/false.
- if (!TI)
- ConsequenceCondSet = isl_set_params(ConsequenceCondSet);
- assert(ConsequenceCondSet);
- ConsequenceCondSet = isl_set_coalesce(
- isl_set_intersect(ConsequenceCondSet, isl_set_copy(Domain)));
-
- isl_set *AlternativeCondSet = nullptr;
- bool TooComplex =
- isl_set_n_basic_set(ConsequenceCondSet) >= MaxDisjunctsInDomain;
-
- if (!TooComplex) {
- AlternativeCondSet = isl_set_subtract(isl_set_copy(Domain),
- isl_set_copy(ConsequenceCondSet));
- TooComplex =
- isl_set_n_basic_set(AlternativeCondSet) >= MaxDisjunctsInDomain;
- }
-
- if (TooComplex) {
- S.invalidate(COMPLEXITY, TI ? TI->getDebugLoc() : DebugLoc(),
- TI ? TI->getParent() : nullptr /* BasicBlock */);
- isl_set_free(AlternativeCondSet);
- isl_set_free(ConsequenceCondSet);
- return false;
- }
-
- ConditionSets.push_back(ConsequenceCondSet);
- ConditionSets.push_back(isl_set_coalesce(AlternativeCondSet));
-
- return true;
-}
-
-bool polly::buildConditionSets(
- Scop &S, BasicBlock *BB, Instruction *TI, Loop *L,
- __isl_keep isl_set *Domain,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap,
- SmallVectorImpl<__isl_give isl_set *> &ConditionSets) {
- if (SwitchInst *SI = dyn_cast<SwitchInst>(TI))
- return buildConditionSets(S, BB, SI, L, Domain, InvalidDomainMap,
- ConditionSets);
-
- assert(isa<BranchInst>(TI) && "Terminator was neither branch nor switch.");
-
- if (TI->getNumSuccessors() == 1) {
- ConditionSets.push_back(isl_set_copy(Domain));
- return true;
- }
-
- Value *Condition = getConditionFromTerminator(TI);
- assert(Condition && "No condition for Terminator");
-
- return buildConditionSets(S, BB, Condition, TI, L, Domain, InvalidDomainMap,
- ConditionSets);
-}
-
ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,
Loop *SurroundingLoop,
std::vector<Instruction *> EntryBlockInstructions)
@@ -2008,38 +1667,6 @@ void Scop::simplifyContexts() {
InvalidContext = InvalidContext.align_params(getParamSpace());
}
-/// Helper to treat non-affine regions and basic blocks the same.
-///
-///{
-
-/// Return the block that is the representing block for @p RN.
-static inline BasicBlock *getRegionNodeBasicBlock(RegionNode *RN) {
- return RN->isSubRegion() ? RN->getNodeAs<Region>()->getEntry()
- : RN->getNodeAs<BasicBlock>();
-}
-
-/// Return the @p idx'th block that is executed after @p RN.
-static inline BasicBlock *
-getRegionNodeSuccessor(RegionNode *RN, Instruction *TI, unsigned idx) {
- if (RN->isSubRegion()) {
- assert(idx == 0);
- return RN->getNodeAs<Region>()->getExit();
- }
- return TI->getSuccessor(idx);
-}
-
-static bool containsErrorBlock(RegionNode *RN, const Region &R, LoopInfo &LI,
- const DominatorTree &DT) {
- if (!RN->isSubRegion())
- return isErrorBlock(*RN->getNodeAs<BasicBlock>(), R, LI, DT);
- for (BasicBlock *BB : RN->getNodeAs<Region>()->blocks())
- if (isErrorBlock(*BB, R, LI, DT))
- return true;
- return false;
-}
-
-///}
-
isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {
return getDomainConditions(Stmt->getEntryBlock());
}
@@ -2056,548 +1683,6 @@ isl::set Scop::getDomainConditions(BasicBlock *BB) const {
return getDomainConditions(BBR->getEntry());
}
-bool Scop::buildDomains(Region *R, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- bool IsOnlyNonAffineRegion = isNonAffineSubRegion(R);
- auto *EntryBB = R->getEntry();
- auto *L = IsOnlyNonAffineRegion ? nullptr : LI.getLoopFor(EntryBB);
- int LD = getRelativeLoopDepth(L);
- auto *S = isl_set_universe(isl_space_set_alloc(getIslCtx().get(), 0, LD + 1));
-
- while (LD-- >= 0) {
- L = L->getParentLoop();
- }
-
- InvalidDomainMap[EntryBB] = isl::manage(isl_set_empty(isl_set_get_space(S)));
- DomainMap[EntryBB] = isl::manage(S);
-
- if (IsOnlyNonAffineRegion)
- return !containsErrorBlock(R->getNode(), *R, LI, DT);
-
- if (!buildDomainsWithBranchConstraints(R, DT, LI, InvalidDomainMap))
- return false;
-
- if (!propagateDomainConstraints(R, DT, LI, InvalidDomainMap))
- return false;
-
- // Error blocks and blocks dominated by them have been assumed to never be
- // executed. Representing them in the Scop does not add any value. In fact,
- // it is likely to cause issues during construction of the ScopStmts. The
- // contents of error blocks have not been verified to be expressible and
- // will cause problems when building up a ScopStmt for them.
- // Furthermore, basic blocks dominated by error blocks may reference
- // instructions in the error block which, if the error block is not modeled,
- // can themselves not be constructed properly. To this end we will replace
- // the domains of error blocks and those only reachable via error blocks
- // with an empty set. Additionally, we will record for each block under which
- // parameter combination it would be reached via an error block in its
- // InvalidDomain. This information is needed during load hoisting.
- if (!propagateInvalidStmtDomains(R, DT, LI, InvalidDomainMap))
- return false;
-
- return true;
-}
-
-/// Adjust the dimensions of @p Dom that was constructed for @p OldL
-/// to be compatible to domains constructed for loop @p NewL.
-///
-/// This function assumes @p NewL and @p OldL are equal or there is a CFG
-/// edge from @p OldL to @p NewL.
-static isl::set adjustDomainDimensions(Scop &S, isl::set Dom, Loop *OldL,
- Loop *NewL) {
- // If the loops are the same there is nothing to do.
- if (NewL == OldL)
- return Dom;
-
- int OldDepth = S.getRelativeLoopDepth(OldL);
- int NewDepth = S.getRelativeLoopDepth(NewL);
- // If both loops are non-affine loops there is nothing to do.
- if (OldDepth == -1 && NewDepth == -1)
- return Dom;
-
- // Distinguish three cases:
- // 1) The depth is the same but the loops are not.
- // => One loop was left one was entered.
- // 2) The depth increased from OldL to NewL.
- // => One loop was entered, none was left.
- // 3) The depth decreased from OldL to NewL.
- // => Loops were left were difference of the depths defines how many.
- if (OldDepth == NewDepth) {
- assert(OldL->getParentLoop() == NewL->getParentLoop());
- Dom = Dom.project_out(isl::dim::set, NewDepth, 1);
- Dom = Dom.add_dims(isl::dim::set, 1);
- } else if (OldDepth < NewDepth) {
- assert(OldDepth + 1 == NewDepth);
- auto &R = S.getRegion();
- (void)R;
- assert(NewL->getParentLoop() == OldL ||
- ((!OldL || !R.contains(OldL)) && R.contains(NewL)));
- Dom = Dom.add_dims(isl::dim::set, 1);
- } else {
- assert(OldDepth > NewDepth);
- int Diff = OldDepth - NewDepth;
- int NumDim = Dom.n_dim();
- assert(NumDim >= Diff);
- Dom = Dom.project_out(isl::dim::set, NumDim - Diff, Diff);
- }
-
- return Dom;
-}
-
-bool Scop::propagateInvalidStmtDomains(
- Region *R, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- ReversePostOrderTraversal<Region *> RTraversal(R);
- for (auto *RN : RTraversal) {
-
- // Recurse for affine subregions but go on for basic blocks and non-affine
- // subregions.
- if (RN->isSubRegion()) {
- Region *SubRegion = RN->getNodeAs<Region>();
- if (!isNonAffineSubRegion(SubRegion)) {
- propagateInvalidStmtDomains(SubRegion, DT, LI, InvalidDomainMap);
- continue;
- }
- }
-
- bool ContainsErrorBlock = containsErrorBlock(RN, getRegion(), LI, DT);
- BasicBlock *BB = getRegionNodeBasicBlock(RN);
- isl::set &Domain = DomainMap[BB];
- assert(Domain && "Cannot propagate a nullptr");
-
- isl::set InvalidDomain = InvalidDomainMap[BB];
-
- bool IsInvalidBlock = ContainsErrorBlock || Domain.is_subset(InvalidDomain);
-
- if (!IsInvalidBlock) {
- InvalidDomain = InvalidDomain.intersect(Domain);
- } else {
- InvalidDomain = Domain;
- isl::set DomPar = Domain.params();
- recordAssumption(ERRORBLOCK, DomPar, BB->getTerminator()->getDebugLoc(),
- AS_RESTRICTION);
- Domain = isl::set::empty(Domain.get_space());
- }
-
- if (InvalidDomain.is_empty()) {
- InvalidDomainMap[BB] = InvalidDomain;
- continue;
- }
-
- auto *BBLoop = getRegionNodeLoop(RN, LI);
- auto *TI = BB->getTerminator();
- unsigned NumSuccs = RN->isSubRegion() ? 1 : TI->getNumSuccessors();
- for (unsigned u = 0; u < NumSuccs; u++) {
- auto *SuccBB = getRegionNodeSuccessor(RN, TI, u);
-
- // Skip successors outside the SCoP.
- if (!contains(SuccBB))
- continue;
-
- // Skip backedges.
- if (DT.dominates(SuccBB, BB))
- continue;
-
- Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
-
- auto AdjustedInvalidDomain =
- adjustDomainDimensions(*this, InvalidDomain, BBLoop, SuccBBLoop);
-
- isl::set SuccInvalidDomain = InvalidDomainMap[SuccBB];
- SuccInvalidDomain = SuccInvalidDomain.unite(AdjustedInvalidDomain);
- SuccInvalidDomain = SuccInvalidDomain.coalesce();
- unsigned NumConjucts = SuccInvalidDomain.n_basic_set();
-
- InvalidDomainMap[SuccBB] = SuccInvalidDomain;
-
- // Check if the maximal number of domain disjunctions was reached.
- // In case this happens we will bail.
- if (NumConjucts < MaxDisjunctsInDomain)
- continue;
-
- InvalidDomainMap.erase(BB);
- invalidate(COMPLEXITY, TI->getDebugLoc(), TI->getParent());
- return false;
- }
-
- InvalidDomainMap[BB] = InvalidDomain;
- }
-
- return true;
-}
-
-void Scop::propagateDomainConstraintsToRegionExit(
- BasicBlock *BB, Loop *BBLoop,
- SmallPtrSetImpl<BasicBlock *> &FinishedExitBlocks, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- // Check if the block @p BB is the entry of a region. If so we propagate it's
- // domain to the exit block of the region. Otherwise we are done.
- auto *RI = R.getRegionInfo();
- auto *BBReg = RI ? RI->getRegionFor(BB) : nullptr;
- auto *ExitBB = BBReg ? BBReg->getExit() : nullptr;
- if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB))
- return;
-
- // Do not propagate the domain if there is a loop backedge inside the region
- // that would prevent the exit block from being executed.
- auto *L = BBLoop;
- while (L && contains(L)) {
- SmallVector<BasicBlock *, 4> LatchBBs;
- BBLoop->getLoopLatches(LatchBBs);
- for (auto *LatchBB : LatchBBs)
- if (BB != LatchBB && BBReg->contains(LatchBB))
- return;
- L = L->getParentLoop();
- }
-
- isl::set Domain = DomainMap[BB];
- assert(Domain && "Cannot propagate a nullptr");
-
- Loop *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, getBoxedLoops());
-
- // Since the dimensions of @p BB and @p ExitBB might be different we have to
- // adjust the domain before we can propagate it.
- isl::set AdjustedDomain =
- adjustDomainDimensions(*this, Domain, BBLoop, ExitBBLoop);
- isl::set &ExitDomain = DomainMap[ExitBB];
-
- // If the exit domain is not yet created we set it otherwise we "add" the
- // current domain.
- ExitDomain = ExitDomain ? AdjustedDomain.unite(ExitDomain) : AdjustedDomain;
-
- // Initialize the invalid domain.
- InvalidDomainMap[ExitBB] = ExitDomain.empty(ExitDomain.get_space());
-
- FinishedExitBlocks.insert(ExitBB);
-}
-
-bool Scop::buildDomainsWithBranchConstraints(
- Region *R, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- // To create the domain for each block in R we iterate over all blocks and
- // subregions in R and propagate the conditions under which the current region
- // element is executed. To this end we iterate in reverse post order over R as
- // it ensures that we first visit all predecessors of a region node (either a
- // basic block or a subregion) before we visit the region node itself.
- // Initially, only the domain for the SCoP region entry block is set and from
- // there we propagate the current domain to all successors, however we add the
- // condition that the successor is actually executed next.
- // As we are only interested in non-loop carried constraints here we can
- // simply skip loop back edges.
-
- SmallPtrSet<BasicBlock *, 8> FinishedExitBlocks;
- ReversePostOrderTraversal<Region *> RTraversal(R);
- for (auto *RN : RTraversal) {
- // Recurse for affine subregions but go on for basic blocks and non-affine
- // subregions.
- if (RN->isSubRegion()) {
- Region *SubRegion = RN->getNodeAs<Region>();
- if (!isNonAffineSubRegion(SubRegion)) {
- if (!buildDomainsWithBranchConstraints(SubRegion, DT, LI,
- InvalidDomainMap))
- return false;
- continue;
- }
- }
-
- if (containsErrorBlock(RN, getRegion(), LI, DT))
- HasErrorBlock = true;
-
- BasicBlock *BB = getRegionNodeBasicBlock(RN);
- Instruction *TI = BB->getTerminator();
-
- if (isa<UnreachableInst>(TI))
- continue;
-
- isl::set Domain = DomainMap.lookup(BB);
- if (!Domain)
- continue;
- MaxLoopDepth = std::max(MaxLoopDepth, isl_set_n_dim(Domain.get()));
-
- auto *BBLoop = getRegionNodeLoop(RN, LI);
- // Propagate the domain from BB directly to blocks that have a superset
- // domain, at the moment only region exit nodes of regions that start in BB.
- propagateDomainConstraintsToRegionExit(BB, BBLoop, FinishedExitBlocks, LI,
- InvalidDomainMap);
-
- // If all successors of BB have been set a domain through the propagation
- // above we do not need to build condition sets but can just skip this
- // block. However, it is important to note that this is a local property
- // with regards to the region @p R. To this end FinishedExitBlocks is a
- // local variable.
- auto IsFinishedRegionExit = [&FinishedExitBlocks](BasicBlock *SuccBB) {
- return FinishedExitBlocks.count(SuccBB);
- };
- if (std::all_of(succ_begin(BB), succ_end(BB), IsFinishedRegionExit))
- continue;
-
- // Build the condition sets for the successor nodes of the current region
- // node. If it is a non-affine subregion we will always execute the single
- // exit node, hence the single entry node domain is the condition set. For
- // basic blocks we use the helper function buildConditionSets.
- SmallVector<isl_set *, 8> ConditionSets;
- if (RN->isSubRegion())
- ConditionSets.push_back(Domain.copy());
- else if (!buildConditionSets(*this, BB, TI, BBLoop, Domain.get(),
- InvalidDomainMap, ConditionSets))
- return false;
-
- // Now iterate over the successors and set their initial domain based on
- // their condition set. We skip back edges here and have to be careful when
- // we leave a loop not to keep constraints over a dimension that doesn't
- // exist anymore.
- assert(RN->isSubRegion() || TI->getNumSuccessors() == ConditionSets.size());
- for (unsigned u = 0, e = ConditionSets.size(); u < e; u++) {
- isl::set CondSet = isl::manage(ConditionSets[u]);
- BasicBlock *SuccBB = getRegionNodeSuccessor(RN, TI, u);
-
- // Skip blocks outside the region.
- if (!contains(SuccBB))
- continue;
-
- // If we propagate the domain of some block to "SuccBB" we do not have to
- // adjust the domain.
- if (FinishedExitBlocks.count(SuccBB))
- continue;
-
- // Skip back edges.
- if (DT.dominates(SuccBB, BB))
- continue;
-
- Loop *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, getBoxedLoops());
-
- CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop);
-
- // Set the domain for the successor or merge it with an existing domain in
- // case there are multiple paths (without loop back edges) to the
- // successor block.
- isl::set &SuccDomain = DomainMap[SuccBB];
-
- if (SuccDomain) {
- SuccDomain = SuccDomain.unite(CondSet).coalesce();
- } else {
- // Initialize the invalid domain.
- InvalidDomainMap[SuccBB] = CondSet.empty(CondSet.get_space());
- SuccDomain = CondSet;
- }
-
- SuccDomain = SuccDomain.detect_equalities();
-
- // Check if the maximal number of domain disjunctions was reached.
- // In case this happens we will clean up and bail.
- if (SuccDomain.n_basic_set() < MaxDisjunctsInDomain)
- continue;
-
- invalidate(COMPLEXITY, DebugLoc());
- while (++u < ConditionSets.size())
- isl_set_free(ConditionSets[u]);
- return false;
- }
- }
-
- return true;
-}
-
-isl::set Scop::getPredecessorDomainConstraints(BasicBlock *BB, isl::set Domain,
- DominatorTree &DT,
- LoopInfo &LI) {
- // If @p BB is the ScopEntry we are done
- if (R.getEntry() == BB)
- return isl::set::universe(Domain.get_space());
-
- // The region info of this function.
- auto &RI = *R.getRegionInfo();
-
- Loop *BBLoop = getFirstNonBoxedLoopFor(BB, LI, getBoxedLoops());
-
- // A domain to collect all predecessor domains, thus all conditions under
- // which the block is executed. To this end we start with the empty domain.
- isl::set PredDom = isl::set::empty(Domain.get_space());
-
- // Set of regions of which the entry block domain has been propagated to BB.
- // all predecessors inside any of the regions can be skipped.
- SmallSet<Region *, 8> PropagatedRegions;
-
- for (auto *PredBB : predecessors(BB)) {
- // Skip backedges.
- if (DT.dominates(BB, PredBB))
- continue;
-
- // If the predecessor is in a region we used for propagation we can skip it.
- auto PredBBInRegion = [PredBB](Region *PR) { return PR->contains(PredBB); };
- if (std::any_of(PropagatedRegions.begin(), PropagatedRegions.end(),
- PredBBInRegion)) {
- continue;
- }
-
- // Check if there is a valid region we can use for propagation, thus look
- // for a region that contains the predecessor and has @p BB as exit block.
- auto *PredR = RI.getRegionFor(PredBB);
- while (PredR->getExit() != BB && !PredR->contains(BB))
- PredR->getParent();
-
- // If a valid region for propagation was found use the entry of that region
- // for propagation, otherwise the PredBB directly.
- if (PredR->getExit() == BB) {
- PredBB = PredR->getEntry();
- PropagatedRegions.insert(PredR);
- }
-
- isl::set PredBBDom = getDomainConditions(PredBB);
- Loop *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, getBoxedLoops());
- PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop);
- PredDom = PredDom.unite(PredBBDom);
- }
-
- return PredDom;
-}
-
-bool Scop::propagateDomainConstraints(
- Region *R, DominatorTree &DT, LoopInfo &LI,
- DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- // Iterate over the region R and propagate the domain constrains from the
- // predecessors to the current node. In contrast to the
- // buildDomainsWithBranchConstraints function, this one will pull the domain
- // information from the predecessors instead of pushing it to the successors.
- // Additionally, we assume the domains to be already present in the domain
- // map here. However, we iterate again in reverse post order so we know all
- // predecessors have been visited before a block or non-affine subregion is
- // visited.
-
- ReversePostOrderTraversal<Region *> RTraversal(R);
- for (auto *RN : RTraversal) {
- // Recurse for affine subregions but go on for basic blocks and non-affine
- // subregions.
- if (RN->isSubRegion()) {
- Region *SubRegion = RN->getNodeAs<Region>();
- if (!isNonAffineSubRegion(SubRegion)) {
- if (!propagateDomainConstraints(SubRegion, DT, LI, InvalidDomainMap))
- return false;
- continue;
- }
- }
-
- BasicBlock *BB = getRegionNodeBasicBlock(RN);
- isl::set &Domain = DomainMap[BB];
- assert(Domain);
-
- // Under the union of all predecessor conditions we can reach this block.
- isl::set PredDom = getPredecessorDomainConstraints(BB, Domain, DT, LI);
- Domain = Domain.intersect(PredDom).coalesce();
- Domain = Domain.align_params(getParamSpace());
-
- Loop *BBLoop = getRegionNodeLoop(RN, LI);
- if (BBLoop && BBLoop->getHeader() == BB && contains(BBLoop))
- if (!addLoopBoundsToHeaderDomain(BBLoop, LI, InvalidDomainMap))
- return false;
- }
-
- return true;
-}
-
-/// Create a map to map from a given iteration to a subsequent iteration.
-///
-/// This map maps from SetSpace -> SetSpace where the dimensions @p Dim
-/// is incremented by one and all other dimensions are equal, e.g.,
-/// [i0, i1, i2, i3] -> [i0, i1, i2 + 1, i3]
-///
-/// if @p Dim is 2 and @p SetSpace has 4 dimensions.
-static isl::map createNextIterationMap(isl::space SetSpace, unsigned Dim) {
- isl::space MapSpace = SetSpace.map_from_set();
- isl::map NextIterationMap = isl::map::universe(MapSpace);
- for (unsigned u = 0; u < NextIterationMap.dim(isl::dim::in); u++)
- if (u != Dim)
- NextIterationMap =
- NextIterationMap.equate(isl::dim::in, u, isl::dim::out, u);
- isl::constraint C =
- isl::constraint::alloc_equality(isl::local_space(MapSpace));
- C = C.set_constant_si(1);
- C = C.set_coefficient_si(isl::dim::in, Dim, 1);
- C = C.set_coefficient_si(isl::dim::out, Dim, -1);
- NextIterationMap = NextIterationMap.add_constraint(C);
- return NextIterationMap;
-}
-
-bool Scop::addLoopBoundsToHeaderDomain(
- Loop *L, LoopInfo &LI, DenseMap<BasicBlock *, isl::set> &InvalidDomainMap) {
- int LoopDepth = getRelativeLoopDepth(L);
- assert(LoopDepth >= 0 && "Loop in region should have at least depth one");
-
- BasicBlock *HeaderBB = L->getHeader();
- assert(DomainMap.count(HeaderBB));
- isl::set &HeaderBBDom = DomainMap[HeaderBB];
-
- isl::map NextIterationMap =
- createNextIterationMap(HeaderBBDom.get_space(), LoopDepth);
-
- isl::set UnionBackedgeCondition = HeaderBBDom.empty(HeaderBBDom.get_space());
-
- SmallVector<BasicBlock *, 4> LatchBlocks;
- L->getLoopLatches(LatchBlocks);
-
- for (BasicBlock *LatchBB : LatchBlocks) {
- // If the latch is only reachable via error statements we skip it.
- isl::set LatchBBDom = DomainMap.lookup(LatchBB);
- if (!LatchBBDom)
- continue;
-
- isl::set BackedgeCondition = nullptr;
-
- Instruction *TI = LatchBB->getTerminator();
- BranchInst *BI = dyn_cast<BranchInst>(TI);
- assert(BI && "Only branch instructions allowed in loop latches");
-
- if (BI->isUnconditional())
- BackedgeCondition = LatchBBDom;
- else {
- SmallVector<isl_set *, 8> ConditionSets;
- int idx = BI->getSuccessor(0) != HeaderBB;
- if (!buildConditionSets(*this, LatchBB, TI, L, LatchBBDom.get(),
- InvalidDomainMap, ConditionSets))
- return false;
-
- // Free the non back edge condition set as we do not need it.
- isl_set_free(ConditionSets[1 - idx]);
-
- BackedgeCondition = isl::manage(ConditionSets[idx]);
- }
-
- int LatchLoopDepth = getRelativeLoopDepth(LI.getLoopFor(LatchBB));
- assert(LatchLoopDepth >= LoopDepth);
- BackedgeCondition = BackedgeCondition.project_out(
- isl::dim::set, LoopDepth + 1, LatchLoopDepth - LoopDepth);
- UnionBackedgeCondition = UnionBackedgeCondition.unite(BackedgeCondition);
- }
-
- isl::map ForwardMap = ForwardMap.lex_le(HeaderBBDom.get_space());
- for (int i = 0; i < LoopDepth; i++)
- ForwardMap = ForwardMap.equate(isl::dim::in, i, isl::dim::out, i);
-
- isl::set UnionBackedgeConditionComplement =
- UnionBackedgeCondition.complement();
- UnionBackedgeConditionComplement =
- UnionBackedgeConditionComplement.lower_bound_si(isl::dim::set, LoopDepth,
- 0);
- UnionBackedgeConditionComplement =
- UnionBackedgeConditionComplement.apply(ForwardMap);
- HeaderBBDom = HeaderBBDom.subtract(UnionBackedgeConditionComplement);
- HeaderBBDom = HeaderBBDom.apply(NextIterationMap);
-
- auto Parts = partitionSetParts(HeaderBBDom, LoopDepth);
- HeaderBBDom = Parts.second;
-
- // Check if there is a <nsw> tagged AddRec for this loop and if so do not add
- // the bounded assumptions to the context as they are already implied by the
- // <nsw> tag.
- if (Affinator.hasNSWAddRecForLoop(L))
- return true;
-
- isl::set UnboundedCtx = Parts.first.params();
- recordAssumption(INFINITELOOP, UnboundedCtx,
- HeaderBB->getTerminator()->getDebugLoc(), AS_RESTRICTION);
- return true;
-}
-
int Scop::NextScopID = 0;
std::string Scop::CurrentFunc;
OpenPOWER on IntegriCloud