This is an archive of the discontinued LLVM Phabricator instance.

[LoopDeletion] Remove dead loops with no exit blocks
ClosedPublic

Authored by atmnpatel on Oct 25 2020, 2:21 AM.

Details

Summary

Currently, LoopDeletion refuses to remove dead loops with no exit blocks
because it cannot statically determine the control flow after it removes
the block. This leads to miscompiles if the loop is an infinite loop and
should've been removed.

Diff Detail

Event Timeline

atmnpatel created this revision.Oct 25 2020, 2:21 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 25 2020, 2:21 AM
atmnpatel requested review of this revision.Oct 25 2020, 2:21 AM
atmnpatel updated this revision to Diff 300531.Oct 25 2020, 2:22 AM

Add parent revision for buildkite.

lebedev.ri added inline comments.
llvm/include/llvm/Analysis/LoopInfoImpl.h
146

I'd put this directly after getExitBlocks(),
and potentially use getExitBlocks(), not getUniqueExitBlocks(),
since uniqification won't really affect the existence of said blocks.

Logic is sound to me. Some nits below.

Please add a test in which an endless loop w/o exits and w/o side-effects can be replaced with unreachable but the loop has more instructions. So, a phi and some control flow that computes the new phi value.

llvm/include/llvm/Analysis/LoopInfoImpl.h
150

Nit: size==0 => empty

llvm/lib/Transforms/Utils/LoopUtils.cpp
587

Can't you move ExitBlock into the else branch. Or branch on ExitBlock and assert hasNoExitBlocks if it is null?

Also, do we need to do all the stuff below in the endless case? Could we just return from the then branch?

Nit: Not sure why you need to set the insert point again.

atmnpatel updated this revision to Diff 300561.Oct 25 2020, 5:34 PM
  • Adds test.
  • Uses getExitBlocks() instead of getUniqueExitBlocks() and moved definition.
  • Changed definition of hasNoExitBlocks() to use empty() instead of conditional
  • Style changes in deleteDeadLoop for readibility.
atmnpatel updated this revision to Diff 300562.Oct 25 2020, 5:36 PM

Update comments.

jdoerfert accepted this revision.Oct 26 2020, 4:25 PM

LGTM, a few nits to be addressed prior to the merge.

llvm/include/llvm/Analysis/LoopInfoImpl.h
75

-Unique

llvm/lib/Transforms/Scalar/LoopDeletion.cpp
200

Nit: aka, at most one exit block ;)

llvm/lib/Transforms/Utils/LoopUtils.cpp
685

Assuming the only use of the DeadDebugInst vector is the code blow that we don't execute (no point to "move" the stuff to), this entire loop is useless for the no-exit case.

Line 668 is trivially true for the no-exit case and 677-684 not needed as described above.

Thus, move the if(ExitBlock) to 648.

This revision is now accepted and ready to land.Oct 26 2020, 4:25 PM
atmnpatel updated this revision to Diff 303323.Nov 5 2020, 8:46 PM
  • Addressed nits
  • Rebase
  • Final Pre-commit testing
atmnpatel updated this revision to Diff 303324.Nov 5 2020, 8:55 PM

using buildkite recommended fix

atmnpatel updated this revision to Diff 303325.Nov 5 2020, 9:03 PM

removed non-parent revision.

atmnpatel updated this revision to Diff 303523.Nov 6 2020, 12:20 PM
  • Fixed failing test
This revision was landed with ongoing or failed builds.Nov 6 2020, 2:09 PM
This revision was automatically updated to reflect the committed changes.