Page MenuHomePhabricator

[LoopDeletion] Allows deletion of possibly infinite side-effect free loops
Needs ReviewPublic

Authored by atmnpatel on Aug 29 2020, 5:06 PM.

Details

Summary

From C11 and C++11 onwards, a forward-progress requirement has been
introduced for both languages. In the case of C, loops with non-constant
conditionals that do not have any observable side-effects (as defined by
6.8.5p6) can be assumed by the implementation to terminate, and in the
case of C++, this assumption extends to all functions. The clang
frontend will emit the mustprogress function attribute for C++
functions (D86233, D85393, D86841) and emit the loop metadata
llvm.loop.mustprogress for every loop in C11 or later that has a
non-constant conditional.

This patch modifies LoopDeletion so that only loops with
the llvm.loop.mustprogress metadata or loops contained in functions
that are required to make progress (mustprogress or willreturn) are
checked for observable side-effects. If these loops do not have an
observable side-effect, then we delete them.

Loops without observable side-effects that do not satisfy the above
conditions will not be deleted.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
atmnpatel edited the summary of this revision. (Show Details)Sep 4 2020, 11:33 AM
atmnpatel updated this revision to Diff 291474.Sep 13 2020, 3:29 PM

Updated to rely on the new mustprogress attrs.

atmnpatel updated this revision to Diff 291475.Sep 13 2020, 3:40 PM

Added a helper for readibility, and some missed comment updates.

atmnpatel edited the summary of this revision. (Show Details)Sep 14 2020, 9:04 AM
atmnpatel updated this revision to Diff 291735.Sep 14 2020, 4:48 PM

No-op to fix buildbot failure to apply patch.

atmnpatel updated this revision to Diff 294456.Sep 25 2020, 4:54 PM

Small renames.

jdoerfert added inline comments.Sep 27 2020, 10:15 AM
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
94

Check this earlier. It is cheaper than the check before.

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1 ↗(On Diff #294456)

Why?

llvm/test/Transforms/LoopDeletion/mustprogress.ll
47

The result is the same as above because the function attribute is still present. Is that intended?

194

Why is this not deleted?

Please upload with full context

atmnpatel edited the summary of this revision. (Show Details)Sep 27 2020, 3:24 PM
atmnpatel added inline comments.Sep 27 2020, 3:25 PM
llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1 ↗(On Diff #294456)

If we don't apply the pass, there are extra labels that are generated and left there i.e.
`` br label %step1

step1:
  br label %step2
step2:
...

``
Does it make sense to remove that extra pass and check for this?

llvm/test/Transforms/LoopDeletion/mustprogress.ll
47

Yep, just wanted to cover all bases.

jdoerfert added inline comments.Sep 27 2020, 9:51 PM
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
72

Early exists "always". Though I feel this is not the right place for this. Do you need it here at all when u check it also later?

213

This seems to be the only change we need, isn't it?

llvm/test/Analysis/ScalarEvolution/2012-03-26-LoadConstant.ll
1 ↗(On Diff #294456)

add/modify check lines as needed, I think running more passes here is not helpful, it runs enough as it is.

llvm/test/Transforms/LoopDeletion/mustprogress.ll
86

Why is this not deleted. We should know the trip count, right?

jdoerfert added inline comments.Sep 29 2020, 9:21 AM
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
206

not accurate anymore, just go back to the old version, also in the comment above.

216

-or +and

llvm/test/Transforms/LoopDeletion/mustprogress.ll
20

why is the loop not deleted?

51

same as above.

atmnpatel added inline comments.Sep 29 2020, 4:13 PM
llvm/test/Transforms/LoopDeletion/mustprogress.ll
20

Loop Deletion requires a single exit block.

51

same thing, there's no single exit block

atmnpatel updated this revision to Diff 296753.Oct 7 2020, 11:29 AM

Updates made to try to remove infinite loops with no exit edge. It seems to work with the new pass manager, but hopelessly breaks for the old pass manager, changes planned.

atmnpatel planned changes to this revision.Oct 7 2020, 11:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 8 2020, 4:02 PM
Herald added a subscriber: cfe-commits. · View Herald Transcript

The new code/functionality wrt. no exit blocks should be a separate commit.

atmnpatel updated this revision to Diff 298734.Oct 16 2020, 1:13 PM

Reverted to prior diff.

atmnpatel updated this revision to Diff 298736.Oct 16 2020, 1:15 PM
This comment was removed by atmnpatel.
atmnpatel updated this revision to Diff 298740.Oct 16 2020, 1:22 PM

fixed splice.

jdoerfert accepted this revision.Oct 25 2020, 10:58 AM

LGTM.

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

Nit: add the word back.

This revision is now accepted and ready to land.Oct 25 2020, 10:58 AM
atmnpatel updated this revision to Diff 300559.Oct 25 2020, 3:26 PM

Added word back in.

atmnpatel updated this revision to Diff 303597.Fri, Nov 6, 5:29 PM

final fixes.

This revision was landed with ongoing or failed builds.Fri, Nov 6, 7:07 PM
This revision was automatically updated to reflect the committed changes.
atmnpatel reopened this revision.Sun, Nov 29, 5:29 PM

This introduced a compile-time error that showed up during a stage 2 build.

This revision is now accepted and ready to land.Sun, Nov 29, 5:29 PM
atmnpatel updated this revision to Diff 308249.Sun, Nov 29, 5:29 PM

I believe this happened becase when I removed the loop, I did not update MemorySSA. The exact error was from GVN, but this update seems to fix the stage 2 build compile time error locally (I checked by running the build bot script).

atmnpatel requested review of this revision.Sun, Nov 29, 5:30 PM
nikic added a subscriber: nikic.Mon, Nov 30, 1:01 AM
nikic added inline comments.
llvm/lib/Transforms/Utils/LoopUtils.cpp
661

These fixes look unrelated. Is it possible to test them separately?

atmnpatel added inline comments.Mon, Nov 30, 3:05 AM
llvm/lib/Transforms/Utils/LoopUtils.cpp
661

So my understanding is that the actual line that fixes the compile time error is 651, that is, just having that line fixes the compile time error. I would assume its because before I didn't tell the dominator tree to remove the edge connecting the preheader and header, and not having that cascade, GVN was unable to iterate properly in some cases over the (now) dead blocks because it wasn't updated in LLVM's internal structures. The actual error was from the iteration in GVN::assignValNumForDeadCode() where it would try to iterate through a block that partially existed but didn't really.

The lines 652-660 that update MemorySSA I added because in the other more general case above, we seem to update MemorySSA right after updating the Dominator Tree.