This is an archive of the discontinued LLVM Phabricator instance.

Preserve loop metadata when splitting exit blocks
Needs RevisionPublic

Authored by clin1 on Oct 30 2018, 10:44 AM.

Details

Summary

LoopUtils.cpp contains a utility that splits an loop exit block, so that the new block contains only edges coming from the loop. In the case of nested loops, the exit path for the inner loop might also be the back-edge of the outer loop. The new block which is inserted on this path, is now a latch for the outer loop, and it needs to hold the loop metadata for the outer loop. (The test case gives a more concrete view of the situation.)

Diff Detail

Event Timeline

clin1 created this revision.Oct 30 2018, 10:44 AM
efriedma added a subscriber: efriedma.
mkazantsev added inline comments.Nov 1 2018, 12:07 AM
lib/Transforms/Utils/LoopUtils.cpp
84 ↗(On Diff #171724)

{ } not needed here.

86 ↗(On Diff #171724)

Dot in the end of sentence.

96 ↗(On Diff #171724)

Is it possible that their loops don't match? If no, please turn it into an assert. If yes, please add a test on this situation.

test/Transforms/LoopSimplify/preserve-llvm-loop-metadata2.ll
34 ↗(On Diff #171724)

Can the test be reduced to make it clear that it's only supposed to test metadata and not fp computations? I think it can be just reduced to having just blocks with counters.

Maybe also makes sense to rename blocks to smth like outer.loop, inner.loop.

dmgreen added inline comments.
lib/Transforms/Utils/LoopUtils.cpp
39 ↗(On Diff #171724)

These should be in order. I think running clang-format on the patch will do that for you.

test/Transforms/LoopSimplify/preserve-llvm-loop-metadata2.ll
6 ↗(On Diff #171724)

Is it worth-while to make sure the LOOPMD is the correct of the two metadata nodes (still "llvm.loop.unroll_and_jam.count")? And that the inner loops still has nounroll?

63 ↗(On Diff #171724)

You can probably remove the tbaa info too, to make things simpler.

clin1 marked 7 inline comments as done.Nov 2 2018, 3:38 PM
clin1 added inline comments.
lib/Transforms/Utils/LoopUtils.cpp
39 ↗(On Diff #171724)

Added by mistake; thanks.

96 ↗(On Diff #171724)

It's taken care of by the assert below, but it needs a better explanation. Comments have all been rewritten.

clin1 updated this revision to Diff 172449.Nov 2 2018, 3:43 PM
clin1 marked 2 inline comments as done.

Rewrote comments, fixed formatting, simplified test and added checks for specific metadata

clin1 updated this revision to Diff 172451.Nov 2 2018, 3:48 PM

Previous patch was null, this is the right one.

This revision is now accepted and ready to land.Nov 5 2018, 8:23 PM
clin1 added a comment.Nov 6 2018, 3:59 PM

Thank you for the thorough review. I have one more request to the reviewers on this list: could someone give a hand to commit the code? I don't have write access to the repo yet.

This revision was automatically updated to reflect the committed changes.

Thanks for the patch!

In case it comes ever up and is actually still relevant (I haven't checked), there are similar problems all over the place.
The one I tried to fix at some point but never actually did can be found here: https://reviews.llvm.org/D5344

rnk added a subscriber: rnk.Nov 13 2018, 5:46 PM

I think this broke the windows selfhost:
http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/1457/steps/stage%202%20build/logs/stdio

Assertion failed: TI->getMetadata(LLVMContext::MD_loop) == OuterLoopMD && "exit edge to other loop doesn't contain expected metadata", file C:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\Transforms\Utils\LoopUtils.cpp, line 105
#0 0x00007ff647c07f05 HandleAbort c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\support\windows\signals.inc:409:0
#1 0x00007ff99ee4dc17 (C:\windows\SYSTEM32\ucrtbase.DLL+0x6dc17)
#2 0x00007ff99ee4eaa1 (C:\windows\SYSTEM32\ucrtbase.DLL+0x6eaa1)
#3 0x00007ff99ee50751 (C:\windows\SYSTEM32\ucrtbase.DLL+0x70751)
#4 0x00007ff99ee50a5f (C:\windows\SYSTEM32\ucrtbase.DLL+0x70a5f)
#5 0x00007ff647cf0c9e <lambda_e0b0a017e173a90c4e1e4410b36fad3c>::operator() c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\transforms\utils\looputils.cpp:106:0
#6 0x00007ff647cf329a llvm::formDedicatedExitBlocks(class llvm::Loop *,class llvm::DominatorTree *,class llvm::LoopInfo *,bool) c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\transforms\utils\looputils.cpp:135:0
#7 0x00007ff647c749d8 simplifyOneLoop c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\transforms\utils\loopsimplify.cpp:535:0
#8 0x00007ff647c73d4a llvm::simplifyLoop(class llvm::Loop *,class llvm::DominatorTree *,class llvm::LoopInfo *,class llvm::ScalarEvolution *,class llvm::AssumptionCache *,bool) c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\transforms\utils\loopsimplify.cpp:706:0
#9 0x00007ff647c72b6a `anonymous namespace'::LoopSimplify::runOnFunction c:\b\slave\clang-x64-windows-msvc\build\llvm.src\lib\transforms\utils\loopsimplify.cpp:776:0
...

I'll get in a revert.

craig.topper reopened this revision.Nov 13 2018, 6:11 PM
craig.topper added a subscriber: craig.topper.

Reopening as this was reverted in r346823

This revision is now accepted and ready to land.Nov 13 2018, 6:11 PM
rnk added a comment.Nov 14 2018, 9:42 AM

It went green with my change here:
http://lab.llvm.org:8011/builders/clang-x64-windows-msvc/builds/1463

Can you gather the reproducer? I'm a bit busy for that right now.

Sorry for the trouble. I'll figure out what happened.

clin1 updated this revision to Diff 174466.Nov 16 2018, 3:32 PM

Remove duplicate blocks from the list of exit predecessors. This happens when the predecessor inst is a switch with duplicate targets. Avoids block double-processing and maintains the metadata consistency assertion.

You're calling std::unique on an unsorted array?

clin1 updated this revision to Diff 174485.Nov 16 2018, 4:59 PM

Missed the sort call -- thanks.

efriedma added inline comments.Nov 16 2018, 5:25 PM
lib/Transforms/Utils/LoopUtils.cpp
72 ↗(On Diff #174485)

You're calling std::sort on a list of pointers; the result is non-deterministic, which could affect the compiler output.

clin1 updated this revision to Diff 174494.Nov 16 2018, 8:27 PM

Keep the InLoopPredecessors vector in the original order.

Maybe add a separate testcase, instead of modifying an existing testcase? Otherwise looks fine, although maybe wait for @mkazantsev to look again.

clin1 updated this revision to Diff 174807.Nov 20 2018, 10:16 AM

Did not include the reverted part of the code (the important part :) ) in the new patch. Added separate testcase for switch-backedge. Thanks for the fix suggestions.

clin1 marked 3 inline comments as done.Nov 20 2018, 10:17 AM
clin1 updated this revision to Diff 182694.Jan 19 2019, 11:44 PM

@mkazantsev, would you mind taking one more look at this patch? One significant fix was made since your last review, to handle duplicate edges from SwitchInsts. The patch has now been rebased to latest (which hasn't changed it much). Thanks!

This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptOct 7 2019, 3:32 AM
Herald added a subscriber: hiraditya. · View Herald Transcript
efriedma reopened this revision.Oct 7 2019, 12:48 PM
This revision is now accepted and ready to land.Oct 7 2019, 12:48 PM

Is this patch still relevant?

I think yes, together with all the other places were loop metadata is not preserved, such as D66892.

I'm trying to make sense of the history here. It looks like I commited it in November last year. Then it got reverted. So I reopened it but maybe didn't move it to changes required and instead it stayed in accepted. Then @clin1 updated it, but it never got re-reviewed. Then it was rebased in January. And I guess sat in accepted state until today when phabricator lost its mind and closed it to the original commit? And probably erased the January version of the diff and went back to November 18?

craig.topper requested changes to this revision.Oct 7 2019, 5:10 PM
This revision now requires changes to proceed.Oct 7 2019, 5:10 PM

The patch was closed by Phabricator since it discovered a "new" commit from git for this patch while assuming that the committed version is the most recent one. Eli re-opened it suspecting that we still might want to fix this.

clin1 updated this revision to Diff 223794.Oct 8 2019, 12:43 AM

Restoring latest patch.

craig.topper added inline comments.Oct 30 2019, 11:11 AM
lib/Transforms/Utils/LoopUtils.cpp
78 ↗(On Diff #223794)

Can we use 'if (PushBlocks.insert(PredBB).second)'

fhahn requested changes to this revision.Sep 18 2020, 6:11 AM

Looks like this still hasn't landed and probably requires at least a rebase.

This revision now requires changes to proceed.Sep 18 2020, 6:11 AM