From 6782d71680ea1cbddd7a98f176e2d9b5b78536d8 Mon Sep 17 00:00:00 2001 From: Congzhe Cao Date: Wed, 21 Sep 2022 23:35:10 -0400 Subject: [PATCH] [LoopPassManager] Ensure to construct loop nests with the outermost loop This patch is to resolve the bug reported and discussed in https://reviews.llvm.org/D124926#3718761 and https://reviews.llvm.org/D124926#3719876. The problem is that loop interchange is a loopnest pass under the new pass manager, but the loop nest may not be constructed correctly by the loop pass manager after running loop interchange and before running the next pass, which might cause problems when it continues running the next pass. The reason that the loop nest is constructed incorrectly is that the outermost loop might have changed after interchange, and what was the original outermost loop is not the current outermost loop anymore. Constructing the loop nest based on the original outermost loop would generate an invalid loop nest. The fix in this patch is that, in the loop pass manager before running each loopnest pass, we re-cosntruct the loop nest based on the current outermost loop, if LPMUpdater notifies the loop pass manager that the previous loop nest has been invalidated by passes like loop interchange. Reviewed By: aeubanks Differential Revision: https://reviews.llvm.org/D132199 --- .../llvm/Transforms/Scalar/LoopPassManager.h | 17 ++++++- llvm/lib/Transforms/Scalar/LoopInterchange.cpp | 2 + llvm/lib/Transforms/Scalar/LoopPassManager.cpp | 17 +++++-- .../LoopInterchange/interchanged-loop-nest-4.ll | 53 ++++++++++++++++++++++ 4 files changed, 83 insertions(+), 6 deletions(-) create mode 100644 llvm/test/Transforms/LoopInterchange/interchanged-loop-nest-4.ll diff --git a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h index 3cdd68a..987b6fa 100644 --- a/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h +++ b/llvm/include/llvm/Transforms/Scalar/LoopPassManager.h @@ -356,6 +356,16 @@ public: Worklist.insert(CurrentL); } + bool isLoopNestChanged() const { + return LoopNestChanged; + } + + /// Loopnest passes should use this method to indicate if the + /// loopnest has been modified. + void markLoopNestChanged(bool Changed) { + LoopNestChanged = Changed; + } + private: friend class llvm::FunctionToLoopPassAdaptor; @@ -368,6 +378,7 @@ private: Loop *CurrentL; bool SkipCurrentLoop; const bool LoopNestMode; + bool LoopNestChanged; #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS // In debug builds we also track the parent loop to implement asserts even in @@ -376,8 +387,10 @@ private: #endif LPMUpdater(SmallPriorityWorklist &Worklist, - LoopAnalysisManager &LAM, bool LoopNestMode = false) - : Worklist(Worklist), LAM(LAM), LoopNestMode(LoopNestMode) {} + LoopAnalysisManager &LAM, bool LoopNestMode = false, + bool LoopNestChanged = false) + : Worklist(Worklist), LAM(LAM), LoopNestMode(LoopNestMode), + LoopNestChanged(LoopNestChanged) {} }; template diff --git a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp index 465dfe7..ce7ff88 100644 --- a/llvm/lib/Transforms/Scalar/LoopInterchange.cpp +++ b/llvm/lib/Transforms/Scalar/LoopInterchange.cpp @@ -44,6 +44,7 @@ #include "llvm/Support/ErrorHandling.h" #include "llvm/Support/raw_ostream.h" #include "llvm/Transforms/Scalar.h" +#include "llvm/Transforms/Scalar/LoopPassManager.h" #include "llvm/Transforms/Utils/BasicBlockUtils.h" #include "llvm/Transforms/Utils/LoopUtils.h" #include @@ -1766,5 +1767,6 @@ PreservedAnalyses LoopInterchangePass::run(LoopNest &LN, OptimizationRemarkEmitter ORE(&F); if (!LoopInterchange(&AR.SE, &AR.LI, &DI, &AR.DT, CC, &ORE).run(LN)) return PreservedAnalyses::all(); + U.markLoopNestChanged(true); return getLoopPassPreservedAnalyses(); } diff --git a/llvm/lib/Transforms/Scalar/LoopPassManager.cpp b/llvm/lib/Transforms/Scalar/LoopPassManager.cpp index b30e45a..e701ce5 100644 --- a/llvm/lib/Transforms/Scalar/LoopPassManager.cpp +++ b/llvm/lib/Transforms/Scalar/LoopPassManager.cpp @@ -84,6 +84,7 @@ LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, // invalid when encountering a loop-nest pass. std::unique_ptr LoopNestPtr; bool IsLoopNestPtrValid = false; + Loop *OuterMostLoop = &L; for (size_t I = 0, E = IsLoopNestPass.size(); I != E; ++I) { Optional PassPA; @@ -97,10 +98,18 @@ LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, // If the loop-nest object calculated before is no longer valid, // re-calculate it here before running the loop-nest pass. - if (!IsLoopNestPtrValid) { - LoopNestPtr = LoopNest::getLoopNest(L, AR.SE); + // + // FIXME: PreservedAnalysis should not be abused to tell if the + // status of loopnest has been changed. We should use and only + // use LPMUpdater for this purpose. + if (!IsLoopNestPtrValid || U.isLoopNestChanged()) { + while (auto *ParentLoop = OuterMostLoop->getParentLoop()) + OuterMostLoop = ParentLoop; + LoopNestPtr = LoopNest::getLoopNest(*OuterMostLoop, AR.SE); IsLoopNestPtrValid = true; + U.markLoopNestChanged(false); } + PassPA = runSinglePass(*LoopNestPtr, Pass, AM, AR, U, PI); } @@ -118,7 +127,7 @@ LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, // Update the analysis manager as each pass runs and potentially // invalidates analyses. - AM.invalidate(L, *PassPA); + AM.invalidate(IsLoopNestPass[I] ? *OuterMostLoop : L, *PassPA); // Finally, we intersect the final preserved analyses to compute the // aggregate preserved set for this pass manager. @@ -130,7 +139,7 @@ LoopPassManager::runWithLoopNestPasses(Loop &L, LoopAnalysisManager &AM, // After running the loop pass, the parent loop might change and we need to // notify the updater, otherwise U.ParentL might gets outdated and triggers // assertion failures in addSiblingLoops and addChildLoops. - U.setParentLoop(L.getParentLoop()); + U.setParentLoop((IsLoopNestPass[I] ? *OuterMostLoop : L).getParentLoop()); } return PA; } diff --git a/llvm/test/Transforms/LoopInterchange/interchanged-loop-nest-4.ll b/llvm/test/Transforms/LoopInterchange/interchanged-loop-nest-4.ll new file mode 100644 index 0000000..70fff16 --- /dev/null +++ b/llvm/test/Transforms/LoopInterchange/interchanged-loop-nest-4.ll @@ -0,0 +1,53 @@ +; REQUIRES: asserts +; RUN: opt < %s -passes="loop(loop-interchange,loop-interchange)" -cache-line-size=8 -verify-dom-info -verify-loop-info \ +; RUN: -debug-only=loop-interchange 2>&1 | FileCheck %s + +target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" + +@g_75 = external global i32, align 1 +@g_78 = external global [6 x ptr], align 1 + +; Loop interchange as a loopnest pass should always construct the loop nest from +; the outermost loop. This test case runs loop interchange twice. In the loop pass +; manager, it might occur that after the first loop interchange transformation +; the original outermost loop becomes a inner loop hence the loop nest constructed +; afterwards for the second loop interchange pass turns out to be a loop list of size +; 2 and is not valid. This causes functional issues. +; +; Make sure we always construct the valid and correct loop nest at the beginning +; of execution of a loopnest pass. + +; CHECK: Processing LoopList of size = 3 +; CHECK: Processing LoopList of size = 3 +define void @loopnest_01() { +entry: + br label %for.cond5.preheader.i.i.i + +for.cond5.preheader.i.i.i: ; preds = %for.end16.i.i.i, %entry + %storemerge11.i.i.i = phi i32 [ 4, %entry ], [ %sub18.i.i.i, %for.end16.i.i.i ] + br label %for.cond8.preheader.i.i.i + +for.cond8.preheader.i.i.i: ; preds = %for.inc14.i.i.i, %for.cond5.preheader.i.i.i + %l_105.18.i.i.i = phi i16 [ 0, %for.cond5.preheader.i.i.i ], [ %add15.i.i.i, %for.inc14.i.i.i ] + br label %for.body10.i.i.i + +for.body10.i.i.i: ; preds = %for.body10.i.i.i, %for.cond8.preheader.i.i.i + %storemerge56.i.i.i = phi i16 [ 5, %for.cond8.preheader.i.i.i ], [ %sub.i.i.i, %for.body10.i.i.i ] + %arrayidx.i.i.i = getelementptr [6 x ptr], ptr @g_78, i16 0, i16 %storemerge56.i.i.i + store ptr @g_75, ptr %arrayidx.i.i.i, align 1 + %sub.i.i.i = add nsw i16 %storemerge56.i.i.i, -1 + br i1 true, label %for.inc14.i.i.i, label %for.body10.i.i.i + +for.inc14.i.i.i: ; preds = %for.body10.i.i.i + %add15.i.i.i = add nuw nsw i16 %l_105.18.i.i.i, 1 + %exitcond.not.i.i.i = icmp eq i16 %add15.i.i.i, 6 + br i1 %exitcond.not.i.i.i, label %for.end16.i.i.i, label %for.cond8.preheader.i.i.i + +for.end16.i.i.i: ; preds = %for.inc14.i.i.i + %sub18.i.i.i = add nsw i32 %storemerge11.i.i.i, -1 + %cmp.i10.not.i.i = icmp eq i32 %storemerge11.i.i.i, 0 + br i1 %cmp.i10.not.i.i, label %func_4.exit.i, label %for.cond5.preheader.i.i.i + +func_4.exit.i: ; preds = %for.end16.i.i.i + unreachable +} -- 2.7.4