Page MenuHomePhabricator

[LoopUnrollAndJam] Change LoopUnrollAndJamPass to LoopNest pass
ClosedPublic

Authored by uint256_t on Mar 23 2021, 12:28 AM.

Diff Detail

Unit TestsFailed

TimeTest
7,720 msx64 debian > libarcher.races::lock-unrelated.c
Script: -- : 'RUN: at line 13'; /var/lib/buildkite-agent/builds/llvm-project/build/./bin/clang -fopenmp -pthread -fno-experimental-isel -g -O1 -fsanitize=thread -I /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests -I /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/runtime/src -L /var/lib/buildkite-agent/builds/llvm-project/build/lib -Wl,-rpath,/var/lib/buildkite-agent/builds/llvm-project/build/lib /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/lock-unrelated.c -o /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp -latomic && env TSAN_OPTIONS='ignore_noninstrumented_modules=0:ignore_noninstrumented_modules=1' /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/deflake.bash /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp 2>&1 | tee /var/lib/buildkite-agent/builds/llvm-project/build/projects/openmp/tools/archer/tests/races/Output/lock-unrelated.c.tmp.log | /var/lib/buildkite-agent/builds/llvm-project/build/./bin/FileCheck /var/lib/buildkite-agent/builds/llvm-project/openmp/tools/archer/tests/races/lock-unrelated.c

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
uint256_t requested review of this revision.Mar 23 2021, 12:28 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 23 2021, 12:28 AM
uint256_t updated this revision to Diff 332678.EditedMar 23 2021, 7:50 AM

Followed clang-tidy's warning

This sounds good to me, so long as all the existing tests are still doing OK.

Does it work, in general, to have a loop pass that creates and destroys loops? Even if the outer loop is completely unrolled?

And does unroll and jam preserve memory-ssa correctly?

uint256_t added a comment.EditedMar 25 2021, 11:49 PM

Does it work, in general, to have a loop pass that creates and destroys loops? Even if the outer loop is completely unrolled?

I should have added code like

if (Result == LoopUnrollResult::FullyUnrolled)
      LPM.markLoopAsDeleted(*L);

after calling tryToUnrollAndJamLoop.

And does unroll and jam preserve memory-ssa correctly?

I'm not sure, but according to https://reviews.llvm.org/D72230, I think

OptimizePM.addPass(createFunctionToLoopPassAdaptor(
        std::move(LPM), EnableMSSALoopDependency,
        /*UseBlockFrequencyInfo=*/true, DebugLogging));

should be simply like

OptimizePM.addPass(createFunctionToLoopPassAdaptor(std::move(LPM));

(I may be misunderstanding the problem)

Updated the code

Whitney accepted this revision.May 10 2021, 5:35 PM

Approve with minor comment.

llvm/lib/Passes/PassBuilder.cpp
1409

OptimizePM.addPass(createFunctionToLoopPassAdaptor(LoopUnrollAndJamPass(Level.getSpeedupLevel())));

This revision is now accepted and ready to land.May 10 2021, 5:35 PM
uint256_t updated this revision to Diff 344392.May 11 2021, 7:26 AM
uint256_t marked an inline comment as done.

Updated the code. Thanks.

Whitney accepted this revision.May 11 2021, 7:34 AM
uint256_t added a comment.EditedMay 11 2021, 6:29 PM

The pre-merge checks failed, so I fixed it.

uint256_t reopened this revision.May 22 2021, 1:38 AM
This revision is now accepted and ready to land.May 22 2021, 1:38 AM
uint256_t updated this revision to Diff 347194.May 22 2021, 3:48 AM

To avoid a failure by address sanitizer

This caused a layering violation.

LLVMScalarOpts (lib/Transforms/Scalar) depends on LLVMTransformUtils (lib/Transforms/Utils) however LLVMTransformUtils now a header dependency #include "llvm/Transforms/Scalar/LoopPassManager.h" on LLVMScalarOpts.

Thank you for reporting. I'll revert the commit and fix the problem.

uint256_t reopened this revision.May 24 2021, 7:41 PM
This revision is now accepted and ready to land.May 24 2021, 7:41 PM
uint256_t updated this revision to Diff 347666.May 25 2021, 6:50 AM

Maybe fixed the problem.

uint256_t added inline comments.May 25 2021, 6:54 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
261

I don't know if this change is ok, but I think CurrentL is always a top-level loop if it's loop nest mode.

Whitney added inline comments.May 25 2021, 7:08 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
261

If CurrentL is always a top-level loop if it's loop nest mode, then why do we need to change from L.isOutermost() to CurrentL == &L?

uint256_t added inline comments.May 25 2021, 7:13 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
261

I found that markLoopAsDeleted is sometimes called on loops that are already destroyed (e.g. by LI->erase(L)). Then L.isOutermost() is invalid since the destructor of L is called. (asan detected it)

Whitney added inline comments.May 27 2021, 9:07 AM
llvm/include/llvm/Transforms/Scalar/LoopPassManager.h
261
/// This runs the destructor of the loop object making it invalid to
/// reference afterward. The memory is retained so that the *pointer* to the
/// loop remains valid.
destroy()

So I agree L.isOutermost() should be changed.

llvm/lib/Transforms/Utils/LoopUnrollAndJam.cpp
52 ↗(On Diff #347666)

Is this change still needed?

uint256_t updated this revision to Diff 348301.May 27 2021, 9:14 AM
Whitney accepted this revision.May 27 2021, 9:16 AM

LGTM, thanks!

This revision was landed with ongoing or failed builds.May 27 2021, 9:17 AM
This revision was automatically updated to reflect the committed changes.
hvdijk added a subscriber: hvdijk.Jun 6 2021, 7:00 AM

I'm seeing test failures now that this has been committed. These tests pass again after reverting this. (Tested on 21653600 directly and re-tested on 12f53e53, and tested the revert on top of the latter.) However, I have not found the same errors in the CI results, https://lab.llvm.org/buildbot/#/changes/22300 shows these tests as passing even in configurations that enable assertions. Is it possible that something in here, or something relied upon by something in here, is not fully deterministic and produces different results in different build configurations? I will try different build configurations to see if I can find one where the tests pass, and compare just what the two different builds do, but if you can spot a potential problem straightaway and suggest something to try that would be very helpful.

LLVM :: Transforms/LoopUnrollAndJam/dependencies.ll
LLVM :: Transforms/LoopUnrollAndJam/dependencies_multidims.ll
LLVM :: Transforms/LoopUnrollAndJam/disable.ll
LLVM :: Transforms/LoopUnrollAndJam/pragma-explicit.ll
LLVM :: Transforms/LoopUnrollAndJam/unroll-and-jam.ll

Of these, the unroll-and-jam failure looks the most interesting. The others have wrong output, but this one hard-fails with an assertion failure for me:

FAIL: LLVM :: Transforms/LoopUnrollAndJam/unroll-and-jam.ll (1 of 1)
******************** TEST 'LLVM :: Transforms/LoopUnrollAndJam/unroll-and-jam.ll' FAILED ********************
Script:
--
: 'RUN: at line 2';   /home/harald/llvm-project/build/bin/opt -basic-aa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder < /home/harald/llvm-project/llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll -S | /home/harald/llvm-project/build/bin/FileCheck /home/harald/llvm-project/llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll
: 'RUN: at line 3';   /home/harald/llvm-project/build/bin/opt -aa-pipeline=tbaa,basic-aa -passes='loop-unroll-and-jam' -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder < /home/harald/llvm-project/llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll -S | /home/harald/llvm-project/build/bin/FileCheck /home/harald/llvm-project/llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll
--
Exit Code: 2

Command Output (stderr):
--
opt: /home/harald/llvm-project/llvm/lib/Transforms/Utils/LoopSimplify.cpp:731: bool llvm::simplifyLoop(llvm::Loop *, llvm::DominatorTree *, llvm::LoopInfo *, llvm::ScalarEvolution *, llvm::AssumptionCache *, llvm::MemorySSAUpdater *, bool): Assertion `L->isRecursivelyLCSSAForm(*DT, *LI) && "Requested to preserve LCSSA, but it's already broken."' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace.
Stack dump:
0.	Program arguments: /home/harald/llvm-project/build/bin/opt -basic-aa -tbaa -loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 -unroll-remainder -S
1.	Running pass 'Function Pass Manager' on module '<stdin>'.
2.	Running pass 'Loop Pass Manager' on function '@test8'
3.	Running pass 'Unroll and Jam loops' on basic block '%for.outer'
 #0 0x0000000001b4abf3 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/harald/llvm-project/build/bin/opt+0x1b4abf3)
 #1 0x0000000001b4898e llvm::sys::RunSignalHandlers() (/home/harald/llvm-project/build/bin/opt+0x1b4898e)
 #2 0x0000000001b4b0ba SignalHandler(int) Signals.cpp:0:0
 #3 0x00007ffa3a712d00 __restore_rt sigaction.c:0:0
 #4 0x00007ffa3a269d4d raise (/lib64/libc.so.6+0x37d4d)
 #5 0x00007ffa3a254526 abort (/lib64/libc.so.6+0x22526)
 #6 0x00007ffa3a25441f _nl_load_domain.cold loadmsgcat.c:0:0
 #7 0x00007ffa3a262ac2 (/lib64/libc.so.6+0x30ac2)
 #8 0x0000000001bf538f (/home/harald/llvm-project/build/bin/opt+0x1bf538f)
 #9 0x0000000001bffba3 llvm::UnrollLoop(llvm::Loop*, llvm::UnrollLoopOptions, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::TargetTransformInfo const*, llvm::OptimizationRemarkEmitter*, bool, llvm::Loop**) (/home/harald/llvm-project/build/bin/opt+0x1bffba3)
#10 0x0000000001c0ed22 llvm::UnrollRuntimeLoopRemainder(llvm::Loop*, unsigned int, bool, bool, bool, bool, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::TargetTransformInfo const*, bool, llvm::Loop**) (/home/harald/llvm-project/build/bin/opt+0x1c0ed22)
#11 0x0000000001c01c65 llvm::UnrollAndJamLoop(llvm::Loop*, unsigned int, unsigned int, unsigned int, bool, llvm::LoopInfo*, llvm::ScalarEvolution*, llvm::DominatorTree*, llvm::AssumptionCache*, llvm::TargetTransformInfo const*, llvm::OptimizationRemarkEmitter*, llvm::Loop**) (/home/harald/llvm-project/build/bin/opt+0x1c01c65)
#12 0x000000000194f77a tryToUnrollAndJamLoop(llvm::Loop*, llvm::DominatorTree&, llvm::LoopInfo*, llvm::ScalarEvolution&, llvm::TargetTransformInfo const&, llvm::AssumptionCache&, llvm::DependenceInfo&, llvm::OptimizationRemarkEmitter&, int) LoopUnrollAndJamPass.cpp:0:0
#13 0x000000000194e6e7 (anonymous namespace)::LoopUnrollAndJam::runOnLoop(llvm::Loop*, llvm::LPPassManager&) LoopUnrollAndJamPass.cpp:0:0
#14 0x0000000000b6a8c5 llvm::LPPassManager::runOnFunction(llvm::Function&) (/home/harald/llvm-project/build/bin/opt+0xb6a8c5)
#15 0x0000000001362558 llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/harald/llvm-project/build/bin/opt+0x1362558)
#16 0x0000000001368eb1 llvm::FPPassManager::runOnModule(llvm::Module&) (/home/harald/llvm-project/build/bin/opt+0x1368eb1)
#17 0x0000000001362c16 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/harald/llvm-project/build/bin/opt+0x1362c16)
#18 0x000000000072c858 main (/home/harald/llvm-project/build/bin/opt+0x72c858)
#19 0x00007ffa3a2557dd __libc_start_main (/lib64/libc.so.6+0x237dd)
#20 0x00000000007158aa _start (/home/harald/llvm-project/build/bin/opt+0x7158aa)
FileCheck error: '<stdin>' is empty.
FileCheck command line:  /home/harald/llvm-project/build/bin/FileCheck /home/harald/llvm-project/llvm/test/Transforms/LoopUnrollAndJam/unroll-and-jam.ll
hvdijk added a comment.Jun 6 2021, 7:40 AM

Ah, problem found, I think: this breaks when ENABLE_EXPERIMENTAL_NEW_PASS_MANAGER=OFF, which I never explicitly set but had inherited as I was using a CMakeCache.txt generated when that was the default. As far as I know this is, for now, a supported configuration. The new pass manager was enabled by default by D95380 and one of the major differences listed there is "LCSSA and LoopSimplify are run before all loop passes"; it seems like this change may be relying on that. Should this perhaps be reverted until the problem can be fixed?

uint256_t added inline comments.Jun 6 2021, 8:12 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

@hvdijk Could you try reversing the running order of LoopSimplify and LCSSAWrapperPass, and check if the problem still reproduces?

hvdijk added inline comments.Jun 6 2021, 8:41 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

Tried now, and I see the same results if I reverse those two lines.

uint256_t added inline comments.Jun 6 2021, 8:53 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

Thank you for reporting! I didn't care about the legacy pass manager. Maybe I'll make a new patch to fix the problem, so I think this need not be reverted.
Do you mind if unroll-and-jam fails on legacy pass manager now?

hvdijk added inline comments.Jun 6 2021, 9:02 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

It's not my call to make, but according to the description of D95380, users are supposed to be able to switch to the legacy pass manager if they encounter problems with the new pass manager. It may be acceptable for the two pass managers to produce slightly different results, but if we now get crashes with the legacy pass manager, users may not have the option to switch if needed. Unless the legacy pass manager is removed entirely (which should at least have some discussion on the mailing list), I think at least the crash will need fixing.

uint256_t added inline comments.Jun 6 2021, 9:29 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

I reverted the commit to fix the problem. thanks.

hvdijk added inline comments.Jun 6 2021, 9:42 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

Thanks. Happy to re-test if you later have a new version, if you want.

uint256_t updated this revision to Diff 350170.Jun 6 2021, 8:37 PM

Code updated. No crash on legacy pass manager in my environment.

uint256_t added inline comments.Jun 6 2021, 8:49 PM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

In my environment there's no more crash on legacy pass manager. Could you please re-test yourself?

hvdijk added inline comments.Jun 7 2021, 2:19 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

Nice, I see no crash, and the tests I mentioned all pass even with the old pass manager. One other test fails (Transforms/SimpleLoopUnswitch/implicit-null-checks.ll) but it's not a crash, just different test output. I'll check deeper later to make sure there's no real issue, but I think it's probably fine.

uint256_t added inline comments.Jun 7 2021, 2:49 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

The failure on 'Transforms/SimpleLoopUnswitch/implicit-null-checks.ll' seems to reproduce even if reverting this patch. I'm not sure if I had better fix it.

hvdijk added inline comments.Jun 7 2021, 9:39 AM
llvm/lib/Transforms/Scalar/LoopUnrollAndJamPass.cpp
514

Oh, if you are already seeing it fail even without re-committing this, then sure, no need to fix it as part of this. :) I am not entirely sure whether you should get this re-approved before re-pushing, but it looks good to me.

uint256_t updated this revision to Diff 350480.Jun 7 2021, 8:16 PM
uint256_t marked an inline comment as done.

Just a small change.