From c3ccf5d77baa8cf4237e3eb68858eda97155e037 Mon Sep 17 00:00:00 2001 From: Igor Laevsky Date: Fri, 28 Oct 2016 12:57:20 +0000 Subject: [PATCH] [LCSSA] Perform LCSSA verification only for the current loop nest. Now LPPassManager will run LCSSA verification only for the top-level loop which was processed on the current iteration. Differential Revision: https://reviews.llvm.org/D25873 llvm-svn: 285394 --- llvm/include/llvm/Analysis/LoopPass.h | 16 ++++++++++++++++ llvm/include/llvm/InitializePasses.h | 3 ++- llvm/lib/Analysis/Analysis.cpp | 1 + llvm/lib/Analysis/LoopPass.cpp | 14 ++++++++++++++ llvm/lib/Transforms/Utils/LCSSA.cpp | 29 +++++++++++++++++++++++++---- llvm/lib/Transforms/Utils/LoopUtils.cpp | 5 +++++ 6 files changed, 63 insertions(+), 5 deletions(-) diff --git a/llvm/include/llvm/Analysis/LoopPass.h b/llvm/include/llvm/Analysis/LoopPass.h index a4043fb..496ae18 100644 --- a/llvm/include/llvm/Analysis/LoopPass.h +++ b/llvm/include/llvm/Analysis/LoopPass.h @@ -155,6 +155,22 @@ private: Loop *CurrentLoop; }; +// This pass is required by the LCSSA transformation. It is used inside +// LPPassManager to check if current pass preserves LCSSA form, and if it does +// pass manager calls lcssa verification for the current loop. +struct LCSSAVerificationPass : public FunctionPass { + static char ID; + LCSSAVerificationPass() : FunctionPass(ID) { + initializeLCSSAVerificationPassPass(*PassRegistry::getPassRegistry()); + } + + bool runOnFunction(Function &F) override { return false; } + + void getAnalysisUsage(AnalysisUsage &AU) const override { + AU.setPreservesAll(); + } +}; + } // End llvm namespace #endif diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h index 46dc528..5d50abf 100644 --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -166,7 +166,8 @@ void initializeInterleavedAccessPass(PassRegistry &); void initializeInternalizeLegacyPassPass(PassRegistry&); void initializeIntervalPartitionPass(PassRegistry&); void initializeJumpThreadingPass(PassRegistry&); -void initializeLCSSAWrapperPassPass(PassRegistry &); +void initializeLCSSAWrapperPassPass(PassRegistry&); +void initializeLCSSAVerificationPassPass(PassRegistry&); void initializeLegacyLICMPassPass(PassRegistry&); void initializeLegacyLoopSinkPassPass(PassRegistry&); void initializeLazyBranchProbabilityInfoPassPass(PassRegistry&); diff --git a/llvm/lib/Analysis/Analysis.cpp b/llvm/lib/Analysis/Analysis.cpp index 635e3c7..0e7cf40 100644 --- a/llvm/lib/Analysis/Analysis.cpp +++ b/llvm/lib/Analysis/Analysis.cpp @@ -77,6 +77,7 @@ void llvm::initializeAnalysis(PassRegistry &Registry) { initializeTargetTransformInfoWrapperPassPass(Registry); initializeTypeBasedAAWrapperPassPass(Registry); initializeScopedNoAliasAAWrapperPassPass(Registry); + initializeLCSSAVerificationPassPass(Registry); } void LLVMInitializeAnalysis(LLVMPassRegistryRef R) { diff --git a/llvm/lib/Analysis/LoopPass.cpp b/llvm/lib/Analysis/LoopPass.cpp index daaf2dc..b5b8040 100644 --- a/llvm/lib/Analysis/LoopPass.cpp +++ b/llvm/lib/Analysis/LoopPass.cpp @@ -15,6 +15,7 @@ #include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/LoopPassManager.h" +#include "llvm/IR/Dominators.h" #include "llvm/IR/IRPrintingPasses.h" #include "llvm/IR/LLVMContext.h" #include "llvm/IR/OptBisect.h" @@ -140,6 +141,7 @@ void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { // LPPassManager needs LoopInfo. In the long term LoopInfo class will // become part of LPPassManager. Info.addRequired(); + Info.addRequired(); Info.setPreservesAll(); } @@ -148,6 +150,7 @@ void LPPassManager::getAnalysisUsage(AnalysisUsage &Info) const { bool LPPassManager::runOnFunction(Function &F) { auto &LIWP = getAnalysis(); LI = &LIWP.getLoopInfo(); + DominatorTree *DT = &getAnalysis().getDomTree(); bool Changed = false; // Collect inherited analysis from Module level pass manager. @@ -218,6 +221,12 @@ bool LPPassManager::runOnFunction(Function &F) { TimeRegion PassTimer(getPassTimer(&LIWP)); CurrentLoop->verifyLoop(); } + // Here we apply same reasoning as in the above case. Only difference + // is that LPPassManager might run passes which do not require LCSSA + // form (LoopPassPrinter for example). We should skip verification for + // such passes. + if (mustPreserveAnalysisID(LCSSAVerificationPass::ID)) + CurrentLoop->isRecursivelyLCSSAForm(*DT, *LI); // Then call the regular verifyAnalysis functions. verifyPreservedAnalysis(P); @@ -353,3 +362,8 @@ bool LoopPass::skipLoop(const Loop *L) const { } return false; } + +char LCSSAVerificationPass::ID = 0; +INITIALIZE_PASS(LCSSAVerificationPass, "lcssa-verification", "LCSSA Verifier", + false, false) + diff --git a/llvm/lib/Transforms/Utils/LCSSA.cpp b/llvm/lib/Transforms/Utils/LCSSA.cpp index 5d818cc..68c6b74 100644 --- a/llvm/lib/Transforms/Utils/LCSSA.cpp +++ b/llvm/lib/Transforms/Utils/LCSSA.cpp @@ -51,6 +51,15 @@ using namespace llvm; STATISTIC(NumLCSSA, "Number of live out of a loop variables"); +#ifdef EXPENSIVE_CHECKS +static bool VerifyLoopLCSSA = true; +#else +static bool VerifyLoopLCSSA = false; +#endif +static cl::opt +VerifyLoopLCSSAFlag("verify-loop-lcssa", cl::location(VerifyLoopLCSSA), + cl::desc("Verify loop lcssa form (time consuming)")); + /// Return true if the specified block is in the list. static bool isExitBlock(BasicBlock *BB, const SmallVectorImpl &ExitBlocks) { @@ -322,10 +331,17 @@ struct LCSSAWrapperPass : public FunctionPass { bool runOnFunction(Function &F) override; void verifyAnalysis() const override { - assert( - all_of(*LI, - [&](Loop *L) { return L->isRecursivelyLCSSAForm(*DT, *LI); }) && - "LCSSA form is broken!"); + // This check is very expensive. On the loop intensive compiles it may cause + // up to 10x slowdown. Currently it's disabled by default. LPPassManager + // always does limited form of the LCSSA verification. Similar reasoning + // was used for the LoopInfo verifier. + if (VerifyLoopLCSSA) { + assert(all_of(*LI, + [&](Loop *L) { + return L->isRecursivelyLCSSAForm(*DT, *LI); + }) && + "LCSSA form is broken!"); + } }; /// This transformation requires natural loop information & requires that @@ -342,6 +358,10 @@ struct LCSSAWrapperPass : public FunctionPass { AU.addPreserved(); AU.addPreserved(); AU.addPreserved(); + + // This is needed to perform LCSSA verification inside LPPassManager + AU.addRequired(); + AU.addPreserved(); } }; } @@ -351,6 +371,7 @@ INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", false, false) INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) +INITIALIZE_PASS_DEPENDENCY(LCSSAVerificationPass) INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", false, false) diff --git a/llvm/lib/Transforms/Utils/LoopUtils.cpp b/llvm/lib/Transforms/Utils/LoopUtils.cpp index 8878689..824bc14 100644 --- a/llvm/lib/Transforms/Utils/LoopUtils.cpp +++ b/llvm/lib/Transforms/Utils/LoopUtils.cpp @@ -17,6 +17,7 @@ #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/GlobalsModRef.h" #include "llvm/Analysis/LoopInfo.h" +#include "llvm/Analysis/LoopPass.h" #include "llvm/Analysis/ScalarEvolution.h" #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" #include "llvm/Analysis/ScalarEvolutionExpander.h" @@ -946,6 +947,10 @@ void llvm::getLoopAnalysisUsage(AnalysisUsage &AU) { AU.addPreservedID(LoopSimplifyID); AU.addRequiredID(LCSSAID); AU.addPreservedID(LCSSAID); + // This is used in the LPPassManager to perform LCSSA verification on passes + // which preserve lcssa form + AU.addRequired(); + AU.addPreserved(); // Loop passes are designed to run inside of a loop pass manager which means // that any function analyses they require must be required by the first loop -- 2.7.4