This is an archive of the discontinued LLVM Phabricator instance.

[LoopSimplifyCFG] Delete dead in-loop blocks
ClosedPublic

Authored by mkazantsev on Nov 1 2018, 9:46 PM.

Diff Detail

Event Timeline

dmgreen added a subscriber: dmgreen.Nov 4 2018, 1:03 PM
mkazantsev planned changes to this revision.Nov 6 2018, 9:30 PM

Needs rebase.

anna added inline comments.Nov 20 2018, 8:34 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
237

Looking at how DeadLoopBlocks get populated, these contain blocks within sub-loops as well.

So, there are 2 ways a subloop can become dead (either properly nested loop or a sibling loop). BB here belongs to a subloop and is:

  1. header of that loop, which is the case you've handled here, i.e. that loop is removed from LI.
  2. latch of that loop, which I don't see being handled. Once latch is removed, that subloop is no longer a loop either.
240

So, this removes the dead block and updates DT.
However, what about this case:

deadblock:
  br anotherblock:

anotherblock:
  <no phis, so we're guaranteed there's exactly one pred, which is deadblock>

DeleteDeadBlock does not recursively remove dead blocks. It handles the case where: dead block is *one of the predecessors* of anotherblock - see BasicBlock::removePredecessor.

I don't think DeadLoopBlocks contains anotherblock, since it became dead/unreachable when deadblock is dead.

mkazantsev added inline comments.Nov 20 2018, 10:49 PM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
237

When collecting fold candidates, we *only* collect candidates that immediately belong to the current loop. Therefore, we cannot modify inner loop's backedge while processing outer loop, assuming that we should have handled it while handling the inner loop.

240

DeadLoopBlocks must contain it by construction, otherwise it's a bug.
I'll add tests on that.

mkazantsev added inline comments.Nov 20 2018, 11:17 PM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
240

Actually we already test this in tests dead_block_propogate_test_branch_loop. In this test, block dead is dead because its predecessor goes to it by false condition, and dummy is dead because dead is its only predecessor.

It is all handled by the algorithm that collects our block sets: it knows what blocks will be dead after *all* folding will be done. It knows it all in advance.

fedor.sergeev added inline comments.Nov 22 2018, 12:42 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
228

Dont you want to add an assert here on

BlocksInLoopAfterFolding + DeadLoopBlocks <= NumBlocks ?

you seem to be relying on that invariant later on (when comparing this sum with numblocks for equality).

mkazantsev added inline comments.Nov 22 2018, 4:20 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
228

Well, by construction BlocksInLoopAfterFolding is a subset of LiveLoopBlocks (see IsEdgeLive), and we have this:

assert(L.getNumBlocks() == LiveLoopBlocks.size() + DeadLoopBlocks.size() &&
       "Malformed block sets?");

Do you really think that what you propose is needed?

mkazantsev added inline comments.Nov 22 2018, 4:46 AM
lib/Transforms/Scalar/LoopSimplifyCFG.cpp
228

I've commited rL347458, along with the assert in my comment above they ensure what you need.

mkazantsev marked an inline comment as done.Nov 22 2018, 4:47 AM
anna added a comment.Nov 22 2018, 10:26 AM

There's an LCSSA not being preserved bug in the original landed change (@dmgreen added the test case). As part of fixing it, pls add the following options to your RUN command in the test "-verify-loop-info -verify-dom-info -verify-loop-lcssa". This will make sure all forms of verification are checked.

Verification flags added at rL347483

Underlying bug fixed, pass re-enabled and I have no failure reports for couple of days; I think we can go ahead and review this.

Me bad, it seems that some tests from https://bugs.llvm.org/show_bug.cgi?id=39783 are still failing.

mkazantsev planned changes to this revision.Nov 29 2018, 12:05 AM

Hold it until this bug is fixed.

It will need a MemorySSA update when we delete blocks.

Rebased, added removal of blocks from MSSA.

anna requested changes to this revision.Dec 4 2018, 7:15 AM

Pls add -verify-memoryssa to the RUN command as well, now that MSSA is getting updated.
Comment inline.

lib/Transforms/Scalar/LoopSimplifyCFG.cpp
240

yes, I see that. thanks for the clarification.

408

Shouldn't we check here that L is still alive before calling mergeBlocksIntoPredecessors? When header is removed from the loop, the loop is removed from LI and no longer a loop (line 248).
If the case of the current loop being deleted is not handled in this patch, pls update the patch summary to state that.

... Ah, I see the deleteCurrentLoop early return at start of analyze().

Could you please add an assert like this before deleting the loop at line 248:

if (LI.isLoopHeader(BB)) {
    assert(L != LI.getLoopFor(BB) && "should not be current loop!");  
    LI.erase(LI.getLoopFor(BB));
}
This revision now requires changes to proceed.Dec 4 2018, 7:15 AM

There is already a mode with memorySSA being constructed and verified in constant-fold-branch.ll:

; RUN: opt -S -enable-loop-simplifycfg-term-folding=true -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg -verify-loop-info -verify-dom-info -verify-loop-lcssa 2>&1 < %s | FileCheck %s
mkazantsev updated this revision to Diff 176762.Dec 4 2018, 9:34 PM
mkazantsev marked an inline comment as done.

Added asserts that we do not delete current loop and its header while dealing with dead blocks.

anna accepted this revision.Dec 5 2018, 12:20 PM

LGTM. Thanks for working through the revisions.

This revision is now accepted and ready to land.Dec 5 2018, 12:20 PM
This revision was automatically updated to reflect the committed changes.
mkazantsev reopened this revision.Dec 6 2018, 9:07 PM

Patch has been reverted, likely because it triggered a bug fixed by D55357 (underlying bug, not directly connected to this patch). Waiting for confirmation, if so, I will recommit it after the fix is merged.

This revision is now accepted and ready to land.Dec 6 2018, 9:07 PM
This revision was automatically updated to reflect the committed changes.