Index: include/polly/LinkAllPasses.h =================================================================== --- include/polly/LinkAllPasses.h +++ include/polly/LinkAllPasses.h @@ -43,7 +43,7 @@ llvm::Pass *createJSONImporterPass(); llvm::Pass *createPollyCanonicalizePass(); llvm::Pass *createPolyhedralInfoPass(); -llvm::Pass *createScopDetectionPass(); +llvm::Pass *createScopDetectionWrapperPassPass(); llvm::Pass *createScopInfoRegionPassPass(); llvm::Pass *createScopInfoWrapperPassPass(); llvm::Pass *createIslAstInfoPass(); @@ -78,7 +78,7 @@ polly::createDOTViewerPass(); polly::createJSONExporterPass(); polly::createJSONImporterPass(); - polly::createScopDetectionPass(); + polly::createScopDetectionWrapperPassPass(); polly::createScopInfoRegionPassPass(); polly::createPollyCanonicalizePass(); polly::createPolyhedralInfoPass(); Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -119,7 +119,7 @@ //===----------------------------------------------------------------------===// /// Pass to detect the maximal static control parts (Scops) of a /// function. -class ScopDetection : public FunctionPass { +class ScopDetection { public: typedef SetVector RegionSet; @@ -198,16 +198,14 @@ private: //===--------------------------------------------------------------------===// - ScopDetection(const ScopDetection &) = delete; - const ScopDetection &operator=(const ScopDetection &) = delete; - /// Analysis passes used. + /// Analyses used //@{ - const DominatorTree *DT; - ScalarEvolution *SE; - LoopInfo *LI; - RegionInfo *RI; - AliasAnalysis *AA; + const DominatorTree &DT; + ScalarEvolution &SE; + LoopInfo &LI; + RegionInfo &RI; + AliasAnalysis &AA; //@} /// Map to remember detection contexts for all regions. @@ -527,16 +525,16 @@ Args &&... Arguments) const; public: - static char ID; - explicit ScopDetection(); + ScopDetection(Function &F, const DominatorTree &DT, ScalarEvolution &SE, + LoopInfo &LI, RegionInfo &RI, AliasAnalysis &AA); /// Get the RegionInfo stored in this pass. /// /// This was added to give the DOT printer easy access to this information. - RegionInfo *getRI() const { return RI; } + RegionInfo *getRI() const { return &RI; } /// Get the LoopInfo stored in this pass. - LoopInfo *getLI() const { return LI; } + LoopInfo *getLI() const { return &LI; } /// Is the region is the maximum region of a Scop? /// @@ -598,14 +596,6 @@ /// @param R The Region to verify. void verifyRegion(const Region &R) const; - /// @name FunctionPass interface - //@{ - virtual void getAnalysisUsage(AnalysisUsage &AU) const; - virtual void releaseMemory(); - virtual bool runOnFunction(Function &F); - virtual void print(raw_ostream &OS, const Module *) const; - //@} - /// Count the number of loops and the maximal loop depth in @p R. /// /// @param R The region to check @@ -619,11 +609,40 @@ unsigned MinProfitableTrips); }; +struct ScopAnalysis : public AnalysisInfoMixin { + static AnalysisKey Key; + using Result = ScopDetection; + Result run(Function &F, FunctionAnalysisManager &FAM); +}; + +struct ScopAnalysisPrinterPass : public PassInfoMixin { + ScopAnalysisPrinterPass(raw_ostream &O) : Stream(O) {} + PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); + raw_ostream &Stream; +}; + +struct ScopDetectionWrapperPass : public FunctionPass { + static char ID; + std::unique_ptr Result; + + ScopDetectionWrapperPass(); + /// @name FunctionPass interface + //@{ + virtual void getAnalysisUsage(AnalysisUsage &AU) const; + virtual void releaseMemory(); + virtual bool runOnFunction(Function &F); + virtual void print(raw_ostream &OS, const Module *) const; + //@} + + ScopDetection &getSD() { return *Result; } + const ScopDetection &getSD() const { return *Result; } +}; + } // end namespace polly namespace llvm { class PassRegistry; -void initializeScopDetectionPass(llvm::PassRegistry &); +void initializeScopDetectionWrapperPassPass(llvm::PassRegistry &); } // namespace llvm #endif Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -23,6 +23,7 @@ #include "llvm/ADT/MapVector.h" #include "llvm/Analysis/RegionPass.h" +#include "llvm/IR/PassManager.h" #include "isl/aff.h" #include "isl/ctx.h" #include "isl/set.h" Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -225,6 +225,9 @@ STATISTIC(MaxNumLoopsInProfScop, "Maximal number of loops in scops (profitable scops only)"); +static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, + bool OnlyProfitable); + class DiagnosticScopFound : public DiagnosticInfo { private: static int PluginDiagnosticKind; @@ -266,10 +269,55 @@ //===----------------------------------------------------------------------===// // ScopDetection. -ScopDetection::ScopDetection() : FunctionPass(ID) { - // Disable runtime alias checks if we ignore aliasing all together. - if (IgnoreAliasing) - PollyUseRuntimeAliasChecks = false; +ScopDetection::ScopDetection(Function &F, const DominatorTree &DT, + ScalarEvolution &SE, LoopInfo &LI, RegionInfo &RI, + AliasAnalysis &AA) + : DT(DT), SE(SE), LI(LI), RI(RI), AA(AA) { + + if (!PollyProcessUnprofitable && LI.empty()) + return; + + Region *TopRegion = RI.getTopLevelRegion(); + + if (OnlyFunction != "" && !F.getName().count(OnlyFunction)) + return; + + if (!isValidFunction(F)) + return; + + findScops(*TopRegion); + + NumScopRegions += ValidRegions.size(); + + // Prune non-profitable regions. + for (auto &DIt : DetectionContextMap) { + auto &DC = DIt.getSecond(); + if (DC.Log.hasErrors()) + continue; + if (!ValidRegions.count(&DC.CurRegion)) + continue; + LoopStats Stats = countBeneficialLoops(&DC.CurRegion, SE, LI, 0); + updateLoopCountStatistic(Stats, false /* OnlyProfitable */); + if (isProfitableRegion(DC)) { + updateLoopCountStatistic(Stats, true /* OnlyProfitable */); + continue; + } + + ValidRegions.remove(&DC.CurRegion); + } + + NumProfScopRegions += ValidRegions.size(); + NumLoopsOverall += countBeneficialLoops(TopRegion, SE, LI, 0).NumLoops; + + // Only makes sense when we tracked errors. + if (PollyTrackFailures) + emitMissedRemarks(F); + + if (ReportLevel) + printLocations(F); + + assert(ValidRegions.size() <= DetectionContextMap.size() && + "Cached more results than valid regions"); } template @@ -300,7 +348,7 @@ DetectionContextMap.erase(getBBPairForRegion(&R)); const auto &It = DetectionContextMap.insert(std::make_pair( getBBPairForRegion(&R), - DetectionContext(const_cast(R), *AA, false /*verifying*/))); + DetectionContext(const_cast(R), AA, false /*verifying*/))); DetectionContext &Context = It.first->second; return isValidRegion(Context); } @@ -333,7 +381,7 @@ // are accesses that depend on the iteration count. for (BasicBlock *BB : AR->blocks()) { - Loop *L = LI->getLoopFor(BB); + Loop *L = LI.getLoopFor(BB); if (AR->contains(L)) Context.BoxedLoopsSet.insert(L); } @@ -358,7 +406,7 @@ if (Context.RequiredILS.count(Load)) continue; - if (!isHoistableLoad(Load, CurRegion, *LI, *SE, *DT)) + if (!isHoistableLoad(Load, CurRegion, LI, SE, DT)) return false; for (auto NonAffineRegion : Context.NonAffineSubRegionSet) { @@ -381,9 +429,9 @@ bool ScopDetection::involvesMultiplePtrs(const SCEV *S0, const SCEV *S1, Loop *Scope) const { SetVector Values; - findValues(S0, *SE, Values); + findValues(S0, SE, Values); if (S1) - findValues(S1, *SE, Values); + findValues(S1, SE, Values); SmallPtrSet PtrVals; for (auto *V : Values) { @@ -393,18 +441,18 @@ if (!V->getType()->isPointerTy()) continue; - auto *PtrSCEV = SE->getSCEVAtScope(V, Scope); + auto *PtrSCEV = SE.getSCEVAtScope(V, Scope); if (isa(PtrSCEV)) continue; - auto *BasePtr = dyn_cast(SE->getPointerBase(PtrSCEV)); + auto *BasePtr = dyn_cast(SE.getPointerBase(PtrSCEV)); if (!BasePtr) return true; auto *BasePtrVal = BasePtr->getValue(); if (PtrVals.insert(BasePtrVal).second) { for (auto *PtrVal : PtrVals) - if (PtrVal != BasePtrVal && !AA->isNoAlias(PtrVal, BasePtrVal)) + if (PtrVal != BasePtrVal && !AA.isNoAlias(PtrVal, BasePtrVal)) return true; } } @@ -416,7 +464,7 @@ DetectionContext &Context) const { InvariantLoadsSetTy AccessILS; - if (!isAffineExpr(&Context.CurRegion, Scope, S, *SE, &AccessILS)) + if (!isAffineExpr(&Context.CurRegion, Scope, S, SE, &AccessILS)) return false; if (!onlyValidRequiredInvariantLoads(AccessILS, Context)) @@ -428,8 +476,8 @@ bool ScopDetection::isValidSwitch(BasicBlock &BB, SwitchInst *SI, Value *Condition, bool IsLoopBranch, DetectionContext &Context) const { - Loop *L = LI->getLoopFor(&BB); - const SCEV *ConditionSCEV = SE->getSCEVAtScope(Condition, L); + Loop *L = LI.getLoopFor(&BB); + const SCEV *ConditionSCEV = SE.getSCEVAtScope(Condition, L); if (IsLoopBranch && L->isLoopLatch(&BB)) return false; @@ -442,7 +490,7 @@ return true; if (AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; return invalid(Context, /*Assert=*/true, &BB, @@ -470,7 +518,7 @@ // Non constant conditions of branches need to be ICmpInst. if (!isa(Condition)) { if (!IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; return invalid(Context, /*Assert=*/true, BI, &BB); } @@ -482,14 +530,14 @@ isa(ICmp->getOperand(1))) return invalid(Context, /*Assert=*/true, &BB, ICmp); - Loop *L = LI->getLoopFor(&BB); - const SCEV *LHS = SE->getSCEVAtScope(ICmp->getOperand(0), L); - const SCEV *RHS = SE->getSCEVAtScope(ICmp->getOperand(1), L); + Loop *L = LI.getLoopFor(&BB); + const SCEV *LHS = SE.getSCEVAtScope(ICmp->getOperand(0), L); + const SCEV *RHS = SE.getSCEVAtScope(ICmp->getOperand(1), L); // If unsigned operations are not allowed try to approximate the region. if (ICmp->isUnsigned() && !PollyAllowUnsignedOperations) return !IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context); + addOverApproximatedRegion(RI.getRegionFor(&BB), Context); // Check for invalid usage of different pointers in one expression. if (ICmp->isEquality() && involvesMultiplePtrs(LHS, nullptr, L) && @@ -504,7 +552,7 @@ return true; if (!IsLoopBranch && AllowNonAffineSubRegions && - addOverApproximatedRegion(RI->getRegionFor(&BB), Context)) + addOverApproximatedRegion(RI.getRegionFor(&BB), Context)) return true; if (IsLoopBranch) @@ -565,7 +613,7 @@ return false; if (AllowModrefCall) { - switch (AA->getModRefBehavior(CalledFunction)) { + switch (AA.getModRefBehavior(CalledFunction)) { case FMRB_UnknownModRefBehavior: return false; case FMRB_DoesNotAccessMemory: @@ -583,11 +631,11 @@ // Bail if a pointer argument has a base address not known to // ScalarEvolution. Note that a zero pointer is acceptable. - auto *ArgSCEV = SE->getSCEVAtScope(Arg, LI->getLoopFor(CI.getParent())); + auto *ArgSCEV = SE.getSCEVAtScope(Arg, LI.getLoopFor(CI.getParent())); if (ArgSCEV->isZero()) continue; - auto *BP = dyn_cast(SE->getPointerBase(ArgSCEV)); + auto *BP = dyn_cast(SE.getPointerBase(ArgSCEV)); if (!BP) return false; @@ -614,7 +662,7 @@ return true; // The closest loop surrounding the call instruction. - Loop *L = LI->getLoopFor(II.getParent()); + Loop *L = LI.getLoopFor(II.getParent()); // The access function and base pointer for memory intrinsics. const SCEV *AF; @@ -624,25 +672,25 @@ // Memory intrinsics that can be represented are supported. case llvm::Intrinsic::memmove: case llvm::Intrinsic::memcpy: - AF = SE->getSCEVAtScope(cast(II).getSource(), L); + AF = SE.getSCEVAtScope(cast(II).getSource(), L); if (!AF->isZero()) { - BP = dyn_cast(SE->getPointerBase(AF)); + BP = dyn_cast(SE.getPointerBase(AF)); // Bail if the source pointer is not valid. if (!isValidAccess(&II, AF, BP, Context)) return false; } // Fall through case llvm::Intrinsic::memset: - AF = SE->getSCEVAtScope(cast(II).getDest(), L); + AF = SE.getSCEVAtScope(cast(II).getDest(), L); if (!AF->isZero()) { - BP = dyn_cast(SE->getPointerBase(AF)); + BP = dyn_cast(SE.getPointerBase(AF)); // Bail if the destination pointer is not valid. if (!isValidAccess(&II, AF, BP, Context)) return false; } // Bail if the length is not affine. - if (!isAffine(SE->getSCEVAtScope(cast(II).getLength(), L), L, + if (!isAffine(SE.getSCEVAtScope(cast(II).getLength(), L), L, Context)) return false; @@ -722,7 +770,7 @@ SmallVector Terms; for (const auto &Pair : Context.Accesses[BasePointer]) { std::vector MaxTerms; - SCEVRemoveMax::rewrite(Pair.second, *SE, &MaxTerms); + SCEVRemoveMax::rewrite(Pair.second, SE, &MaxTerms); if (MaxTerms.size() > 0) { Terms.insert(Terms.begin(), MaxTerms.begin(), MaxTerms.end()); continue; @@ -738,7 +786,7 @@ if (auto *AF = dyn_cast(Pair.second)) { for (auto Op : AF->operands()) { if (auto *AF2 = dyn_cast(Op)) - SE->collectParametricTerms(AF2, Terms); + SE.collectParametricTerms(AF2, Terms); if (auto *AF2 = dyn_cast(Op)) { SmallVector Operands; @@ -756,12 +804,12 @@ } } if (Operands.size()) - Terms.push_back(SE->getMulExpr(Operands)); + Terms.push_back(SE.getMulExpr(Operands)); } } } if (Terms.empty()) - SE->collectParametricTerms(Pair.second, Terms); + SE.collectParametricTerms(Pair.second, Terms); } return Terms; } @@ -781,7 +829,7 @@ auto *V = dyn_cast(Unknown->getValue()); if (auto *Load = dyn_cast(V)) { if (Context.CurRegion.contains(Load) && - isHoistableLoad(Load, CurRegion, *LI, *SE, *DT)) + isHoistableLoad(Load, CurRegion, LI, SE, DT)) Context.RequiredILS.insert(Load); continue; } @@ -828,11 +876,11 @@ for (const auto &Pair : Context.Accesses[BasePointer]) { const Instruction *Insn = Pair.first; auto *AF = Pair.second; - AF = SCEVRemoveMax::rewrite(AF, *SE); + AF = SCEVRemoveMax::rewrite(AF, SE); bool IsNonAffine = false; TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape))); MemAcc *Acc = &TempMemoryAccesses.find(Insn)->second; - auto *Scope = LI->getLoopFor(Insn->getParent()); + auto *Scope = LI.getLoopFor(Insn->getParent()); if (!AF) { if (isAffine(Pair.second, Scope, Context)) @@ -840,8 +888,8 @@ else IsNonAffine = true; } else { - SE->computeAccessFunctions(AF, Acc->DelinearizedSubscripts, - Shape->DelinearizedSizes); + SE.computeAccessFunctions(AF, Acc->DelinearizedSubscripts, + Shape->DelinearizedSizes); if (Acc->DelinearizedSubscripts.size() == 0) IsNonAffine = true; for (const SCEV *S : Acc->DelinearizedSubscripts) @@ -874,8 +922,8 @@ auto Terms = getDelinearizationTerms(Context, BasePointer); - SE->findArrayDimensions(Terms, Shape->DelinearizedSizes, - Context.ElementSize[BasePointer]); + SE.findArrayDimensions(Terms, Shape->DelinearizedSizes, + Context.ElementSize[BasePointer]); if (!hasValidArraySizes(Context, Shape->DelinearizedSizes, BasePointer, Scope)) @@ -923,15 +971,15 @@ if (!isInvariant(*BV, Context.CurRegion, Context)) return invalid(Context, /*Assert=*/true, BV, Inst); - AF = SE->getMinusSCEV(AF, BP); + AF = SE.getMinusSCEV(AF, BP); const SCEV *Size; if (!isa(Inst)) { - Size = SE->getElementSize(Inst); + Size = SE.getElementSize(Inst); } else { auto *SizeTy = - SE->getEffectiveSCEVType(PointerType::getInt8PtrTy(SE->getContext())); - Size = SE->getConstant(SizeTy, 8); + SE.getEffectiveSCEVType(PointerType::getInt8PtrTy(SE.getContext())); + Size = SE.getConstant(SizeTy, 8); } if (Context.ElementSize[BP]) { @@ -939,7 +987,7 @@ return invalid(Context, /*Assert=*/true, Inst, BV); - Context.ElementSize[BP] = SE->getSMinExpr(Size, Context.ElementSize[BP]); + Context.ElementSize[BP] = SE.getSMinExpr(Size, Context.ElementSize[BP]); } else { Context.ElementSize[BP] = Size; } @@ -951,7 +999,7 @@ if (Context.BoxedLoopsSet.count(L)) IsVariantInNonAffineLoop = true; - auto *Scope = LI->getLoopFor(Inst->getParent()); + auto *Scope = LI.getLoopFor(Inst->getParent()); bool IsAffine = !IsVariantInNonAffineLoop && isAffine(AF, Scope, Context); // Do not try to delinearize memory intrinsics and force them to be affine. if (isa(Inst) && !IsAffine) { @@ -962,7 +1010,7 @@ if (!IsAffine) Context.NonAffineAccesses.insert( - std::make_pair(BP, LI->getLoopFor(Inst->getParent()))); + std::make_pair(BP, LI.getLoopFor(Inst->getParent()))); } else if (!AllowNonAffine && !IsAffine) { return invalid(Context, /*Assert=*/true, AF, Inst, BV); @@ -990,7 +1038,7 @@ Instruction *Inst = dyn_cast(Ptr.getValue()); if (Inst && Context.CurRegion.contains(Inst)) { auto *Load = dyn_cast(Inst); - if (Load && isHoistableLoad(Load, Context.CurRegion, *LI, *SE, *DT)) { + if (Load && isHoistableLoad(Load, Context.CurRegion, LI, SE, DT)) { Context.RequiredILS.insert(Load); continue; } @@ -1012,11 +1060,11 @@ bool ScopDetection::isValidMemoryAccess(MemAccInst Inst, DetectionContext &Context) const { Value *Ptr = Inst.getPointerOperand(); - Loop *L = LI->getLoopFor(Inst->getParent()); - const SCEV *AccessFunction = SE->getSCEVAtScope(Ptr, L); + Loop *L = LI.getLoopFor(Inst->getParent()); + const SCEV *AccessFunction = SE.getSCEVAtScope(Ptr, L); const SCEVUnknown *BasePointer; - BasePointer = dyn_cast(SE->getPointerBase(AccessFunction)); + BasePointer = dyn_cast(SE.getPointerBase(AccessFunction)); return isValidAccess(Inst, AccessFunction, BasePointer, Context); } @@ -1029,7 +1077,7 @@ if (!OpInst) continue; - if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, *LI, *DT)) + if (isErrorBlock(*OpInst->getParent(), Context.CurRegion, LI, DT)) return false; } @@ -1130,7 +1178,7 @@ return true; if (AllowNonAffineSubLoops && AllowNonAffineSubRegions) { - Region *R = RI->getRegionFor(L->getHeader()); + Region *R = RI.getRegionFor(L->getHeader()); while (R != &Context.CurRegion && !R->contains(L)) R = R->getParent(); @@ -1138,7 +1186,7 @@ return true; } - const SCEV *LoopCount = SE->getBackedgeTakenCount(L); + const SCEV *LoopCount = SE.getBackedgeTakenCount(L); return invalid(Context, /*Assert=*/true, L, LoopCount); } @@ -1199,7 +1247,7 @@ while (ExpandedRegion) { const auto &It = DetectionContextMap.insert(std::make_pair( getBBPairForRegion(ExpandedRegion.get()), - DetectionContext(*ExpandedRegion, *AA, false /*verifying*/))); + DetectionContext(*ExpandedRegion, AA, false /*verifying*/))); DetectionContext &Context = It.first->second; DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n"); // Only expand when we did not collect errors. @@ -1244,9 +1292,9 @@ return LastValidRegion.release(); } -static bool regionWithoutLoops(Region &R, LoopInfo *LI) { +static bool regionWithoutLoops(Region &R, LoopInfo &LI) { for (const BasicBlock *BB : R.blocks()) - if (R.contains(LI->getLoopFor(BB))) + if (R.contains(LI.getLoopFor(BB))) return false; return true; @@ -1267,7 +1315,7 @@ void ScopDetection::findScops(Region &R) { const auto &It = DetectionContextMap.insert(std::make_pair( - getBBPairForRegion(&R), DetectionContext(R, *AA, false /*verifying*/))); + getBBPairForRegion(&R), DetectionContext(R, AA, false /*verifying*/))); DetectionContext &Context = It.first->second; bool RegionIsValid = false; @@ -1326,14 +1374,14 @@ Region &CurRegion = Context.CurRegion; for (const BasicBlock *BB : CurRegion.blocks()) { - Loop *L = LI->getLoopFor(BB); + Loop *L = LI.getLoopFor(BB); if (L && L->getHeader() == BB && CurRegion.contains(L) && (!isValidLoop(L, Context) && !KeepGoing)) return false; } for (BasicBlock *BB : CurRegion.blocks()) { - bool IsErrorBlock = isErrorBlock(*BB, CurRegion, *LI, *DT); + bool IsErrorBlock = isErrorBlock(*BB, CurRegion, LI, DT); // Also check exception blocks (and possibly register them as non-affine // regions). Even though exception blocks are not modeled, we use them @@ -1363,7 +1411,7 @@ return false; for (auto *BB : Context.CurRegion.blocks()) - if (Context.CurRegion.contains(LI->getLoopFor(BB))) + if (Context.CurRegion.contains(LI.getLoopFor(BB))) InstCount += BB->size(); InstCount = InstCount / NumLoops; @@ -1374,7 +1422,7 @@ bool ScopDetection::hasPossiblyDistributableLoop( DetectionContext &Context) const { for (auto *BB : Context.CurRegion.blocks()) { - auto *L = LI->getLoopFor(BB); + auto *L = LI.getLoopFor(BB); if (!Context.CurRegion.contains(L)) continue; if (Context.BoxedLoopsSet.count(L)) @@ -1403,7 +1451,7 @@ return invalid(Context, /*Assert=*/true, &CurRegion); int NumLoops = - countBeneficialLoops(&CurRegion, *SE, *LI, MIN_LOOP_TRIP_COUNT).NumLoops; + countBeneficialLoops(&CurRegion, SE, LI, MIN_LOOP_TRIP_COUNT).NumLoops; int NumAffineLoops = NumLoops - Context.BoxedLoopsSet.size(); // Scops with at least two loops may allow either loop fusion or tiling and @@ -1553,7 +1601,7 @@ // GREY indicates a loop in the control flow. // If the destination dominates the source, it is a natural loop // else, an irreducible control flow in the region is detected. - if (!DT->dominates(SuccBB, CurrBB)) { + if (!DT.dominates(SuccBB, CurrBB)) { // Get debug info of instruction which causes irregular control flow. DbgLoc = TInst->getDebugLoc(); return false; @@ -1570,8 +1618,8 @@ return true; } -void updateLoopCountStatistic(ScopDetection::LoopStats Stats, - bool OnlyProfitable) { +static void updateLoopCountStatistic(ScopDetection::LoopStats Stats, + bool OnlyProfitable) { if (!OnlyProfitable) { NumLoopsInScop += Stats.NumLoops; MaxNumLoopsInScop = @@ -1607,61 +1655,6 @@ } } -bool ScopDetection::runOnFunction(llvm::Function &F) { - LI = &getAnalysis().getLoopInfo(); - RI = &getAnalysis().getRegionInfo(); - if (!PollyProcessUnprofitable && LI->empty()) - return false; - - AA = &getAnalysis().getAAResults(); - SE = &getAnalysis().getSE(); - DT = &getAnalysis().getDomTree(); - Region *TopRegion = RI->getTopLevelRegion(); - - releaseMemory(); - - if (OnlyFunction != "" && !F.getName().count(OnlyFunction)) - return false; - - if (!isValidFunction(F)) - return false; - - findScops(*TopRegion); - - NumScopRegions += ValidRegions.size(); - - // Prune non-profitable regions. - for (auto &DIt : DetectionContextMap) { - auto &DC = DIt.getSecond(); - if (DC.Log.hasErrors()) - continue; - if (!ValidRegions.count(&DC.CurRegion)) - continue; - LoopStats Stats = countBeneficialLoops(&DC.CurRegion, *SE, *LI, 0); - updateLoopCountStatistic(Stats, false /* OnlyProfitable */); - if (isProfitableRegion(DC)) { - updateLoopCountStatistic(Stats, true /* OnlyProfitable */); - continue; - } - - ValidRegions.remove(&DC.CurRegion); - } - - NumProfScopRegions += ValidRegions.size(); - NumLoopsOverall += countBeneficialLoops(TopRegion, *SE, *LI, 0).NumLoops; - - // Only makes sense when we tracked errors. - if (PollyTrackFailures) - emitMissedRemarks(F); - - if (ReportLevel) - printLocations(F); - - assert(ValidRegions.size() <= DetectionContextMap.size() && - "Cached more results than valid regions"); - return false; -} - ScopDetection::DetectionContext * ScopDetection::getDetectionContext(const Region *R) const { auto DCMIt = DetectionContextMap.find(getBBPairForRegion(R)); @@ -1678,7 +1671,7 @@ void polly::ScopDetection::verifyRegion(const Region &R) const { assert(isMaxRegionInScop(R) && "Expect R is a valid region."); - DetectionContext Context(const_cast(R), *AA, true /*verifying*/); + DetectionContext Context(const_cast(R), AA, true /*verifying*/); isValidRegion(Context); } @@ -1690,7 +1683,17 @@ verifyRegion(*R); } -void ScopDetection::getAnalysisUsage(AnalysisUsage &AU) const { +bool ScopDetectionWrapperPass::runOnFunction(llvm::Function &F) { + auto &LI = getAnalysis().getLoopInfo(); + auto &RI = getAnalysis().getRegionInfo(); + auto &AA = getAnalysis().getAAResults(); + auto &SE = getAnalysis().getSE(); + auto &DT = getAnalysis().getDomTree(); + Result.reset(new ScopDetection(F, DT, SE, LI, RI, AA)); + return false; +} + +void ScopDetectionWrapperPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); AU.addRequiredTransitive(); AU.addRequired(); @@ -1700,25 +1703,49 @@ AU.setPreservesAll(); } -void ScopDetection::print(raw_ostream &OS, const Module *) const { - for (const Region *R : ValidRegions) +void ScopDetectionWrapperPass::print(raw_ostream &OS, const Module *) const { + for (const Region *R : Result->ValidRegions) OS << "Valid Region for Scop: " << R->getNameStr() << '\n'; OS << "\n"; } -void ScopDetection::releaseMemory() { - ValidRegions.clear(); - DetectionContextMap.clear(); +ScopDetectionWrapperPass::ScopDetectionWrapperPass() : FunctionPass(ID) { + // Disable runtime alias checks if we ignore aliasing all together. + if (IgnoreAliasing) + PollyUseRuntimeAliasChecks = false; +} + +void ScopDetectionWrapperPass::releaseMemory() { Result.reset(); } + +char ScopDetectionWrapperPass::ID; + +AnalysisKey ScopAnalysis::Key; - // Do not clear the invalid function set. +ScopDetection ScopAnalysis::run(Function &F, FunctionAnalysisManager &FAM) { + auto &LI = FAM.getResult(F); + auto &RI = FAM.getResult(F); + auto &AA = FAM.getResult(F); + auto &SE = FAM.getResult(F); + auto &DT = FAM.getResult(F); + return {F, DT, SE, LI, RI, AA}; } -char ScopDetection::ID = 0; +PreservedAnalyses ScopAnalysisPrinterPass::run(Function &F, + FunctionAnalysisManager &FAM) { + auto &SD = FAM.getResult(F); + for (const Region *R : SD.ValidRegions) + Stream << "Valid Region for Scop: " << R->getNameStr() << '\n'; -Pass *polly::createScopDetectionPass() { return new ScopDetection(); } + Stream << "\n"; + return PreservedAnalyses::all(); +} + +Pass *polly::createScopDetectionWrapperPassPass() { + return new ScopDetectionWrapperPass(); +} -INITIALIZE_PASS_BEGIN(ScopDetection, "polly-detect", +INITIALIZE_PASS_BEGIN(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false); INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass); @@ -1726,5 +1753,5 @@ INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_END(ScopDetection, "polly-detect", +INITIALIZE_PASS_END(ScopDetectionWrapperPass, "polly-detect", "Polly - Detect static control parts (SCoPs)", false, false) Index: lib/Analysis/ScopGraphPrinter.cpp =================================================================== --- lib/Analysis/ScopGraphPrinter.cpp +++ lib/Analysis/ScopGraphPrinter.cpp @@ -47,6 +47,20 @@ } }; +template <> +struct GraphTraits + : public GraphTraits { + static NodeRef getEntryNode(ScopDetectionWrapperPass *P) { + return GraphTraits::getEntryNode(&P->getSD()); + } + static nodes_iterator nodes_begin(ScopDetectionWrapperPass *P) { + return nodes_iterator::begin(getEntryNode(P)); + } + static nodes_iterator nodes_end(ScopDetectionWrapperPass *P) { + return nodes_iterator::end(getEntryNode(P)); + } +}; + template <> struct DOTGraphTraits : public DefaultDOTGraphTraits { DOTGraphTraits(bool isSimple = false) : DefaultDOTGraphTraits(isSimple) {} @@ -67,15 +81,19 @@ }; template <> -struct DOTGraphTraits : public DOTGraphTraits { +struct DOTGraphTraits + : public DOTGraphTraits { DOTGraphTraits(bool isSimple = false) : DOTGraphTraits(isSimple) {} - static std::string getGraphName(ScopDetection *SD) { return "Scop Graph"; } + static std::string getGraphName(ScopDetectionWrapperPass *SD) { + return "Scop Graph"; + } std::string getEdgeAttributes(RegionNode *srcNode, GraphTraits::ChildIteratorType CI, - ScopDetection *SD) { + ScopDetectionWrapperPass *P) { RegionNode *destNode = *CI; + auto *SD = &P->getSD(); if (srcNode->isSubRegion() || destNode->isSubRegion()) return ""; @@ -99,9 +117,10 @@ return ""; } - std::string getNodeLabel(RegionNode *Node, ScopDetection *SD) { + std::string getNodeLabel(RegionNode *Node, ScopDetectionWrapperPass *P) { return DOTGraphTraits::getNodeLabel( - Node, reinterpret_cast(SD->getRI()->getTopLevelRegion())); + Node, reinterpret_cast( + P->getSD().getRI()->getTopLevelRegion())); } static std::string escapeString(std::string String) { @@ -169,20 +188,24 @@ O.indent(2 * depth) << "}\n"; } - static void addCustomGraphFeatures(const ScopDetection *SD, - GraphWriter &GW) { + static void + addCustomGraphFeatures(const ScopDetectionWrapperPass *SD, + GraphWriter &GW) { raw_ostream &O = GW.getOStream(); O << "\tcolorscheme = \"paired12\"\n"; - printRegionCluster(SD, SD->getRI()->getTopLevelRegion(), O, 4); + printRegionCluster(&SD->getSD(), SD->getSD().getRI()->getTopLevelRegion(), + O, 4); } }; } // end namespace llvm -struct ScopViewer : public DOTGraphTraitsViewer { +struct ScopViewer + : public DOTGraphTraitsViewer { static char ID; - ScopViewer() : DOTGraphTraitsViewer("scops", ID) {} - bool processFunction(Function &F, ScopDetection &SD) override { + ScopViewer() + : DOTGraphTraitsViewer("scops", ID) {} + bool processFunction(Function &F, ScopDetectionWrapperPass &SD) override { if (ViewFilter != "" && !F.getName().count(ViewFilter)) return false; @@ -190,28 +213,33 @@ return true; // Check that at least one scop was detected. - return std::distance(SD.begin(), SD.end()) > 0; + return std::distance(SD.getSD().begin(), SD.getSD().end()) > 0; } }; char ScopViewer::ID = 0; -struct ScopOnlyViewer : public DOTGraphTraitsViewer { +struct ScopOnlyViewer + : public DOTGraphTraitsViewer { static char ID; ScopOnlyViewer() - : DOTGraphTraitsViewer("scopsonly", ID) {} + : DOTGraphTraitsViewer("scopsonly", ID) {} }; char ScopOnlyViewer::ID = 0; -struct ScopPrinter : public DOTGraphTraitsPrinter { +struct ScopPrinter + : public DOTGraphTraitsPrinter { static char ID; - ScopPrinter() : DOTGraphTraitsPrinter("scops", ID) {} + ScopPrinter() + : DOTGraphTraitsPrinter("scops", ID) {} }; char ScopPrinter::ID = 0; -struct ScopOnlyPrinter : public DOTGraphTraitsPrinter { +struct ScopOnlyPrinter + : public DOTGraphTraitsPrinter { static char ID; ScopOnlyPrinter() - : DOTGraphTraitsPrinter("scopsonly", ID) {} + : DOTGraphTraitsPrinter("scopsonly", ID) { + } }; char ScopOnlyPrinter::ID = 0; Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -4747,7 +4747,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); @@ -4773,7 +4773,7 @@ } bool ScopInfoRegionPass::runOnRegion(Region *R, RGPassManager &RGM) { - auto &SD = getAnalysis(); + auto &SD = getAnalysis().getSD(); if (!SD.isMaxRegionInScop(*R)) return false; @@ -4817,7 +4817,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_END(ScopInfoRegionPass, "polly-scops", "Polly - Create polyhedral description of Scops", false, @@ -4829,14 +4829,14 @@ AU.addRequired(); AU.addRequired(); AU.addRequiredTransitive(); - AU.addRequiredTransitive(); + AU.addRequiredTransitive(); AU.addRequired(); AU.addRequired(); AU.setPreservesAll(); } bool ScopInfoWrapperPass::runOnFunction(Function &F) { - auto &SD = getAnalysis(); + auto &SD = getAnalysis().getSD(); auto &SE = getAnalysis().getSE(); auto &LI = getAnalysis().getLoopInfo(); @@ -4888,7 +4888,7 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass); INITIALIZE_PASS_END( ScopInfoWrapperPass, "polly-function-scops", Index: lib/CodeGen/CodeGeneration.cpp =================================================================== --- lib/CodeGen/CodeGeneration.cpp +++ lib/CodeGen/CodeGeneration.cpp @@ -276,7 +276,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -288,7 +288,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -311,6 +311,6 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_END(CodeGeneration, "polly-codegen", "Polly - Create LLVM-IR from SCoPs", false, false) Index: lib/CodeGen/PPCGCodeGeneration.cpp =================================================================== --- lib/CodeGen/PPCGCodeGeneration.cpp +++ lib/CodeGen/PPCGCodeGeneration.cpp @@ -2694,7 +2694,7 @@ AU.addRequired(); AU.addRequired(); AU.addRequired(); - AU.addRequired(); + AU.addRequired(); AU.addRequired(); AU.addRequired(); @@ -2703,7 +2703,7 @@ AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); - AU.addPreserved(); + AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); @@ -2731,6 +2731,6 @@ INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass); INITIALIZE_PASS_DEPENDENCY(RegionInfoPass); INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass); -INITIALIZE_PASS_DEPENDENCY(ScopDetection); +INITIALIZE_PASS_DEPENDENCY(ScopDetectionWrapperPass); INITIALIZE_PASS_END(PPCGCodeGeneration, "polly-codegen-ppcg", "Polly - Apply PPCG translation to SCOP", false, false) Index: lib/Support/RegisterPasses.cpp =================================================================== --- lib/Support/RegisterPasses.cpp +++ lib/Support/RegisterPasses.cpp @@ -234,7 +234,7 @@ initializeIslScheduleOptimizerPass(Registry); initializePollyCanonicalizePass(Registry); initializePolyhedralInfoPass(Registry); - initializeScopDetectionPass(Registry); + initializeScopDetectionWrapperPassPass(Registry); initializeScopInfoRegionPassPass(Registry); initializeScopInfoWrapperPassPass(Registry); initializeCodegenCleanupPass(Registry); @@ -277,7 +277,7 @@ for (auto &Filename : DumpBeforeFile) PM.add(polly::createDumpModulePass(Filename, false)); - PM.add(polly::createScopDetectionPass()); + PM.add(polly::createScopDetectionWrapperPassPass()); if (PollyDetectOnly) return;