Page MenuHomePhabricator

[LoopSimplifyCFG] Change logic of dead loops removal to avoid hitting asserts
ClosedPublic

Authored by mkazantsev on Jan 25 2019, 1:23 AM.

Details

Summary

The function LI.erase has some invariants that need to be preserved when it tries to
remove a loop which is not the top-level loop. In particular, it requires loop's preheader
to be strictly in loop's parent. Our current logic of deletion of dead blocks may erase the
information about preheader before we handle the loop, and therefore we may hit this
assertion.

This patch changes the logic of loop deletion: we make them top-level loops before
we actually erase them. This allows us to trigger the simple branch of erase logic which
just detatches blocks from the loop and does not try to do some complex stuff that need
this invariant.

Thanks to @uabelho for reporting this!

Diff Detail

Repository
rL LLVM

Event Timeline

mkazantsev created this revision.Jan 25 2019, 1:23 AM

It solves the problem I saw, thanks!

The change looks fine to me but I don't know this code so let someone else ok it.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

Perhaps replace

if (DL->getParentLoop()) {
  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())

with

while (auto *PL = DL->getParentLoop()) {

?

mkazantsev marked an inline comment as done.Jan 29 2019, 3:40 AM
mkazantsev added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

And loop infinitely? :) We need to change DL somehow, otherwise PL is always the same loop.

uabelho added inline comments.Jan 29 2019, 3:43 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

Doesn't
DL->getParentLoop()->removeChildLoop(DL);
disconnect DL from PL, so in the next loop round DL doesn't have the old PL as parent anymore?

mkazantsev marked an inline comment as done.Jan 29 2019, 10:28 PM
mkazantsev added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

The line DL->getParentLoop()->removeChildLoop(DL); is executed once *after* this loop. You seem to be misreading the code. :)

uabelho added inline comments.Jan 30 2019, 12:08 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

Right. When I tried what I suggested I did

while (auto *PL = DL->getParentLoop()) {
  for (auto *BB : DL->getBlocks())
    PL->removeBlockFromLoop(BB);
  DL->getParentLoop()->removeChildLoop(DL);
  LI.addTopLevelLoop(DL);
}

with that all the testcases (including the reproducer in this patch) passes but perhaps it's stupid to call LI.addTopLevelLoop(DL) several times.
But nvm, I just thought the

if (DL->getParentLoop()) {
  for (auto *PL = DL->getParentLoop(); PL; PL = PL->getParentLoop())

was cumbersome and could be simplified, I didn't mean to make a mess :)

mkazantsev marked an inline comment as done.Jan 30 2019, 2:21 AM
mkazantsev added inline comments.
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
408–409 ↗(On Diff #183494)

I've seen that pattern across the code and think it's fine. Feel free to refactor it if you like. :)

Aside from refactoring that we can make as follow-up if needed (yet I don't really think it does), does it look OK? :)

Aside from refactoring that we can make as follow-up if needed (yet I don't really think it does), does it look OK? :)

It does to me but as I said I don't know this code so I think someone else should ok it.

fedor.sergeev accepted this revision.Feb 11 2019, 5:28 AM
fedor.sergeev added a subscriber: fedor.sergeev.

LGTM.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp
404 ↗(On Diff #183494)

Please, put a short comment here describing the idea of this first loop through dead blocks.

This revision is now accepted and ready to land.Feb 11 2019, 5:28 AM
mkazantsev marked an inline comment as done.Feb 12 2019, 1:31 AM
This revision was automatically updated to reflect the committed changes.
Herald added a project: Restricted Project. · View Herald TranscriptFeb 12 2019, 1:36 AM
sammccall added inline comments.
llvm/trunk/test/Transforms/LoopSimplifyCFG/update_parents.ll
2

this REQUIRES was still needed because of the use of -debug-only.
Fixed in r353842