Index: polly/trunk/include/polly/ScopBuilder.h =================================================================== --- polly/trunk/include/polly/ScopBuilder.h +++ polly/trunk/include/polly/ScopBuilder.h @@ -61,48 +61,48 @@ /// Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction + /// @param Stmt The parent statement of the instruction /// /// @returns True if the access could be built, False otherwise. - bool buildAccessMultiDimFixed(MemAccInst Inst, Loop *L); + bool buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt); /// Try to build a multi-dimensional parameteric sized MemoryAccess. /// from the Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction + /// @param Stmt The parent statement of the instruction /// /// @returns True if the access could be built, False otherwise. - bool buildAccessMultiDimParam(MemAccInst Inst, Loop *L); + bool buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt); /// Try to build a MemoryAccess for a memory intrinsic. /// /// @param Inst The instruction that access the memory - /// @param L The parent loop of the instruction + /// @param Stmt The parent statement of the instruction /// /// @returns True if the access could be built, False otherwise. - bool buildAccessMemIntrinsic(MemAccInst Inst, Loop *L); + bool buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt); /// Try to build a MemoryAccess for a call instruction. /// /// @param Inst The call instruction that access the memory - /// @param L The parent loop of the instruction + /// @param Stmt The parent statement of the instruction /// /// @returns True if the access could be built, False otherwise. - bool buildAccessCallInst(MemAccInst Inst, Loop *L); + bool buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt); /// Build a single-dimensional parametric sized MemoryAccess /// from the Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - void buildAccessSingleDim(MemAccInst Inst, Loop *L); + /// @param Stmt The parent statement of the instruction + void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); /// Build an instance of MemoryAccess from the Load/Store instruction. /// /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - void buildMemoryAccess(MemAccInst Inst, Loop *L); + /// @param Stmt The parent statement of the instruction + void buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt); /// Analyze and extract the cross-BB scalar dependences (or, dataflow /// dependencies) of an instruction. Index: polly/trunk/include/polly/ScopInfo.h =================================================================== --- polly/trunk/include/polly/ScopInfo.h +++ polly/trunk/include/polly/ScopInfo.h @@ -1112,10 +1112,10 @@ const ScopStmt &operator=(const ScopStmt &) = delete; /// Create the ScopStmt from a BasicBlock. - ScopStmt(Scop &parent, BasicBlock &bb); + ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop); /// Create an overapproximating ScopStmt for the region @p R. - ScopStmt(Scop &parent, Region &R); + ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop); /// Create a copy statement. /// @@ -1216,6 +1216,9 @@ std::string BaseName; + /// The closest loop that contains this statement. + Loop *SurroundingLoop; + /// Build the statement. //@{ void buildDomain(); @@ -1311,6 +1314,34 @@ /// statements, return its entry block. BasicBlock *getEntryBlock() const; + /// Return whether @p L is boxed within this statement. + bool contains(const Loop *L) const { + // Block statements never contain loops. + if (isBlockStmt()) + return false; + + return getRegion()->contains(L); + } + + /// Return the closest innermost loop that contains this statement, but is not + /// contained in it. + /// + /// For block statement, this is just the loop that contains the block. Region + /// statements can contain boxed loops, so getting the loop of one of the + /// region's BBs might return such an inner loop. For instance, the region's + /// entry could be a header of a loop, but the region might extend to BBs + /// after the loop exit. Similarly, the region might only contain parts of the + /// loop body and still include the loop header. + /// + /// Most of the time the surrounding loop is the top element of #NestLoops, + /// except when it is empty. In that case it return the loop that the whole + /// SCoP is contained in. That can be nullptr if there is no such loop. + Loop *getSurroundingLoop() const { + assert(!isCopyStmt() && + "No surrounding loop for artificially created statements"); + return SurroundingLoop; + } + /// Return true if this statement does not contain any accesses. bool isEmpty() const { return MemAccs.empty(); } @@ -1881,16 +1912,18 @@ /// vector /// and map. /// - /// @param BB The basic block we build the statement for. - void addScopStmt(BasicBlock *BB); + /// @param BB The basic block we build the statement for. + /// @param SurroundingLoop The loop the created statement is contained in. + void addScopStmt(BasicBlock *BB, Loop *SurroundingLoop); /// Create a new SCoP statement for @p R. /// /// A new statement for @p R will be created and added to the statement vector /// and map. /// - /// @param R The region we build the statement for. - void addScopStmt(Region *R); + /// @param R The region we build the statement for. + /// @param SurroundingLoop The loop the created statement is contained in. + void addScopStmt(Region *R, Loop *SurroundingLoop); /// Update access dimensionalities. /// Index: polly/trunk/include/polly/Support/ScopHelper.h =================================================================== --- polly/trunk/include/polly/Support/ScopHelper.h +++ polly/trunk/include/polly/Support/ScopHelper.h @@ -426,24 +426,5 @@ std::tuple, std::vector> getIndexExpressionsFromGEP(llvm::GetElementPtrInst *GEP, llvm::ScalarEvolution &SE); - -// If the loop is nonaffine/boxed, return the first non-boxed surrounding loop -// for Polly. If the loop is affine, return the loop itself. -// -// @param L Pointer to the Loop object to analyze. -// @param LI Reference to the LoopInfo. -// @param Boxed Loops Set of Boxed Loops we get from the SCoP. -llvm::Loop *getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, - const BoxedLoopsSetTy &BoxedLoops); - -// If the Basic Block belongs to a loop that is nonaffine/boxed, return the -// first non-boxed surrounding loop for Polly. If the loop is affine, return -// the loop itself. -// -// @param BB Pointer to the Basic Block to analyze. -// @param LI Reference to the LoopInfo. -// @param Boxed Loops Set of Boxed Loops we get from the SCoP. -llvm::Loop *getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, llvm::LoopInfo &LI, - const BoxedLoopsSetTy &BoxedLoops); } // namespace polly #endif Index: polly/trunk/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopBuilder.cpp +++ polly/trunk/lib/Analysis/ScopBuilder.cpp @@ -112,11 +112,12 @@ } } -bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, Loop *L) { +bool ScopBuilder::buildAccessMultiDimFixed(MemAccInst Inst, ScopStmt *Stmt) { Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); Value *Address = Inst.getPointerOperand(); - const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L); + const SCEV *AccessFunction = + SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent())); const SCEVUnknown *BasePointer = dyn_cast(SE.getPointerBase(AccessFunction)); enum MemoryAccess::AccessType AccType = @@ -158,7 +159,7 @@ const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads(); - Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops()); + Loop *SurroundingLoop = Stmt->getSurroundingLoop(); for (auto *Subscript : Subscripts) { InvariantLoadsSetTy AccessILS; if (!isAffineExpr(&scop->getRegion(), SurroundingLoop, Subscript, SE, @@ -184,7 +185,7 @@ return true; } -bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, Loop *L) { +bool ScopBuilder::buildAccessMultiDimParam(MemAccInst Inst, ScopStmt *Stmt) { if (!PollyDelinearize) return false; @@ -195,7 +196,8 @@ enum MemoryAccess::AccessType AccType = isa(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE; - const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L); + const SCEV *AccessFunction = + SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent())); const SCEVUnknown *BasePointer = dyn_cast(SE.getPointerBase(AccessFunction)); @@ -227,12 +229,13 @@ return true; } -bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, Loop *L) { +bool ScopBuilder::buildAccessMemIntrinsic(MemAccInst Inst, ScopStmt *Stmt) { auto *MemIntr = dyn_cast_or_null(Inst); if (MemIntr == nullptr) return false; + auto *L = LI.getLoopFor(Inst->getParent()); auto *LengthVal = SE.getSCEVAtScope(MemIntr->getLength(), L); assert(LengthVal); @@ -240,7 +243,7 @@ InvariantLoadsSetTy AccessILS; const InvariantLoadsSetTy &ScopRIL = scop->getRequiredInvariantLoads(); - Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, scop->getBoxedLoops()); + Loop *SurroundingLoop = Stmt->getSurroundingLoop(); bool LengthIsAffine = isAffineExpr(&scop->getRegion(), SurroundingLoop, LengthVal, SE, &AccessILS); for (LoadInst *LInst : AccessILS) @@ -295,7 +298,7 @@ return true; } -bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, Loop *L) { +bool ScopBuilder::buildAccessCallInst(MemAccInst Inst, ScopStmt *Stmt) { auto *CI = dyn_cast_or_null(Inst); if (CI == nullptr) @@ -324,6 +327,7 @@ // Fall through case FMRB_OnlyAccessesArgumentPointees: auto AccType = ReadOnly ? MemoryAccess::READ : MemoryAccess::MAY_WRITE; + Loop *L = LI.getLoopFor(Inst->getParent()); for (const auto &Arg : CI->arg_operands()) { if (!Arg->getType()->isPointerTy()) continue; @@ -342,14 +346,15 @@ return true; } -void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, Loop *L) { +void ScopBuilder::buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt) { Value *Address = Inst.getPointerOperand(); Value *Val = Inst.getValueOperand(); Type *ElementType = Val->getType(); enum MemoryAccess::AccessType AccType = isa(Inst) ? MemoryAccess::READ : MemoryAccess::MUST_WRITE; - const SCEV *AccessFunction = SE.getSCEVAtScope(Address, L); + const SCEV *AccessFunction = + SE.getSCEVAtScope(Address, LI.getLoopFor(Inst->getParent())); const SCEVUnknown *BasePointer = dyn_cast(SE.getPointerBase(AccessFunction)); @@ -359,15 +364,16 @@ // Check if the access depends on a loop contained in a non-affine subregion. bool isVariantInNonAffineLoop = false; SetVector Loops; - auto &BoxedLoops = scop->getBoxedLoops(); findLoops(AccessFunction, Loops); for (const Loop *L : Loops) - if (BoxedLoops.count(L)) + if (Stmt->contains(L)) { isVariantInNonAffineLoop = true; + break; + } InvariantLoadsSetTy AccessILS; - Loop *SurroundingLoop = getFirstNonBoxedLoopFor(L, LI, BoxedLoops); + Loop *SurroundingLoop = Stmt->getSurroundingLoop(); bool IsAffine = !isVariantInNonAffineLoop && isAffineExpr(&scop->getRegion(), SurroundingLoop, AccessFunction, SE, &AccessILS); @@ -384,21 +390,21 @@ {AccessFunction}, {nullptr}, Val); } -void ScopBuilder::buildMemoryAccess(MemAccInst Inst, Loop *L) { +void ScopBuilder::buildMemoryAccess(MemAccInst Inst, ScopStmt *Stmt) { - if (buildAccessMemIntrinsic(Inst, L)) + if (buildAccessMemIntrinsic(Inst, Stmt)) return; - if (buildAccessCallInst(Inst, L)) + if (buildAccessCallInst(Inst, Stmt)) return; - if (buildAccessMultiDimFixed(Inst, L)) + if (buildAccessMultiDimFixed(Inst, Stmt)) return; - if (buildAccessMultiDimParam(Inst, L)) + if (buildAccessMultiDimParam(Inst, Stmt)) return; - buildAccessSingleDim(Inst, L); + buildAccessSingleDim(Inst, Stmt); } void ScopBuilder::buildAccessFunctions(Region &SR) { @@ -419,15 +425,21 @@ void ScopBuilder::buildStmts(Region &SR) { if (scop->isNonAffineSubRegion(&SR)) { - scop->addScopStmt(&SR); + Loop *SurroundingLoop = LI.getLoopFor(SR.getEntry()); + auto &BoxedLoops = scop->getBoxedLoops(); + while (BoxedLoops.count(SurroundingLoop)) + SurroundingLoop = SurroundingLoop->getParentLoop(); + scop->addScopStmt(&SR, SurroundingLoop); return; } for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I) if (I->isSubRegion()) buildStmts(*I->getNodeAs()); - else - scop->addScopStmt(I->getNodeAs()); + else { + Loop *SurroundingLoop = LI.getLoopFor(I->getNodeAs()); + scop->addScopStmt(I->getNodeAs(), SurroundingLoop); + } } void ScopBuilder::buildAccessFunctions(BasicBlock &BB, @@ -438,7 +450,7 @@ if (isErrorBlock(BB, scop->getRegion(), LI, DT) && !IsExitBlock) return; - Loop *L = LI.getLoopFor(&BB); + ScopStmt *Stmt = scop->getStmtFor(&BB); for (Instruction &Inst : BB) { PHINode *PHI = dyn_cast(&Inst); @@ -449,8 +461,10 @@ if (!PHI && IsExitBlock) break; - if (auto MemInst = MemAccInst::dyn_cast(Inst)) - buildMemoryAccess(MemInst, L); + if (auto MemInst = MemAccInst::dyn_cast(Inst)) { + assert(Stmt && "Cannot build access function in non-existing statement"); + buildMemoryAccess(MemInst, Stmt); + } if (isIgnoredIntrinsic(&Inst)) continue; Index: polly/trunk/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/trunk/lib/Analysis/ScopInfo.cpp +++ polly/trunk/lib/Analysis/ScopInfo.cpp @@ -1560,16 +1560,16 @@ } } -ScopStmt::ScopStmt(Scop &parent, Region &R) +ScopStmt::ScopStmt(Scop &parent, Region &R, Loop *SurroundingLoop) : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(nullptr), - R(&R), Build(nullptr) { + R(&R), Build(nullptr), SurroundingLoop(SurroundingLoop) { BaseName = getIslCompatibleName("Stmt_", R.getNameStr(), ""); } -ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb) +ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, Loop *SurroundingLoop) : Parent(parent), InvalidDomain(nullptr), Domain(nullptr), BB(&bb), - R(nullptr), Build(nullptr) { + R(nullptr), Build(nullptr), SurroundingLoop(SurroundingLoop) { BaseName = getIslCompatibleName("Stmt_", &bb, ""); } @@ -2485,8 +2485,6 @@ bool Scop::propagateInvalidStmtDomains(Region *R, DominatorTree &DT, LoopInfo &LI) { - auto &BoxedLoops = getBoxedLoops(); - ReversePostOrderTraversal RTraversal(R); for (auto *RN : RTraversal) { @@ -2541,7 +2539,7 @@ if (DT.dominates(SuccBB, BB)) continue; - auto *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, BoxedLoops); + auto *SuccBBLoop = SuccStmt->getSurroundingLoop(); auto *AdjustedInvalidDomain = adjustDomainDimensions( *this, isl_set_copy(InvalidDomain), BBLoop, SuccBBLoop); auto *SuccInvalidDomain = SuccStmt->getInvalidDomain(); @@ -2579,7 +2577,6 @@ if (!BBReg || BBReg->getEntry() != BB || !contains(ExitBB)) return; - auto &BoxedLoops = getBoxedLoops(); // 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; @@ -2595,7 +2592,8 @@ auto *Domain = DomainMap[BB]; assert(Domain && "Cannot propagate a nullptr"); - auto *ExitBBLoop = getFirstNonBoxedLoopFor(ExitBB, LI, BoxedLoops); + auto *ExitStmt = getStmtFor(ExitBB); + auto *ExitBBLoop = ExitStmt->getSurroundingLoop(); // Since the dimensions of @p BB and @p ExitBB might be different we have to // adjust the domain before we can propagate it. @@ -2609,7 +2607,6 @@ ExitDomain ? isl_set_union(AdjustedDomain, ExitDomain) : AdjustedDomain; // Initialize the invalid domain. - auto *ExitStmt = getStmtFor(ExitBB); ExitStmt->setInvalidDomain(isl_set_empty(isl_set_get_space(ExitDomain))); FinishedExitBlocks.insert(ExitBB); @@ -2713,8 +2710,7 @@ continue; } - auto &BoxedLoops = getBoxedLoops(); - auto *SuccBBLoop = getFirstNonBoxedLoopFor(SuccBB, LI, BoxedLoops); + auto *SuccBBLoop = SuccStmt->getSurroundingLoop(); CondSet = adjustDomainDimensions(*this, CondSet, BBLoop, SuccBBLoop); // Set the domain for the successor or merge it with an existing domain in @@ -2753,13 +2749,10 @@ if (R.getEntry() == BB) return isl_set_universe(isl_set_get_space(Domain)); - // The set of boxed loops (loops in non-affine subregions) for this SCoP. - auto &BoxedLoops = getBoxedLoops(); - // The region info of this function. auto &RI = *R.getRegionInfo(); - auto *BBLoop = getFirstNonBoxedLoopFor(BB, LI, BoxedLoops); + auto *BBLoop = getStmtFor(BB)->getSurroundingLoop(); // 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. @@ -2795,7 +2788,7 @@ } auto *PredBBDom = getDomainConditions(PredBB); - auto *PredBBLoop = getFirstNonBoxedLoopFor(PredBB, LI, BoxedLoops); + auto *PredBBLoop = getStmtFor(PredBB)->getSurroundingLoop(); PredBBDom = adjustDomainDimensions(*this, PredBBDom, PredBBLoop, BBLoop); PredDom = isl_set_union(PredDom, PredBBDom); @@ -4435,16 +4428,16 @@ return isl_multi_union_pw_aff_from_union_pw_multi_aff(Data.Res); } -void Scop::addScopStmt(BasicBlock *BB) { +void Scop::addScopStmt(BasicBlock *BB, Loop *SurroundingLoop) { assert(BB && "Unexpected nullptr!"); - Stmts.emplace_back(*this, *BB); + Stmts.emplace_back(*this, *BB, SurroundingLoop); auto *Stmt = &Stmts.back(); StmtMap[BB] = Stmt; } -void Scop::addScopStmt(Region *R) { +void Scop::addScopStmt(Region *R, Loop *SurroundingLoop) { assert(R && "Unexpected nullptr!"); - Stmts.emplace_back(*this, *R); + Stmts.emplace_back(*this, *R, SurroundingLoop); auto *Stmt = &Stmts.back(); for (BasicBlock *BB : R->blocks()) StmtMap[BB] = Stmt; Index: polly/trunk/lib/Support/ScopHelper.cpp =================================================================== --- polly/trunk/lib/Support/ScopHelper.cpp +++ polly/trunk/lib/Support/ScopHelper.cpp @@ -561,17 +561,3 @@ return std::make_tuple(Subscripts, Sizes); } - -llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::Loop *L, llvm::LoopInfo &LI, - const BoxedLoopsSetTy &BoxedLoops) { - while (BoxedLoops.count(L)) - L = L->getParentLoop(); - return L; -} - -llvm::Loop *polly::getFirstNonBoxedLoopFor(llvm::BasicBlock *BB, - llvm::LoopInfo &LI, - const BoxedLoopsSetTy &BoxedLoops) { - Loop *L = LI.getLoopFor(BB); - return getFirstNonBoxedLoopFor(L, LI, BoxedLoops); -}