Page MenuHomePhabricator

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

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

Unit TestsFailed

TimeTest
50 mslinux > Clang.Misc::loop-opt-setup.c
Script: -- : 'RUN: at line 1'; /mnt/disks/ssd0/agent/llvm-project/build/bin/clang -O1 -fno-unroll-loops -S -o - /mnt/disks/ssd0/agent/llvm-project/clang/test/Misc/loop-opt-setup.c -emit-llvm | /mnt/disks/ssd0/agent/llvm-project/build/bin/FileCheck /mnt/disks/ssd0/agent/llvm-project/clang/test/Misc/loop-opt-setup.c
400 mslinux > HWAddressSanitizer-x86_64.TestCases::sizes.cpp
Script: -- : 'RUN: at line 3'; /mnt/disks/ssd0/agent/llvm-project/build/./bin/clang --driver-mode=g++ -m64 -gline-tables-only -fsanitize=hwaddress -fuse-ld=lld -mcmodel=large -mllvm -hwasan-globals -mllvm -hwasan-use-short-granules -mllvm -hwasan-instrument-landing-pads=0 -mllvm -hwasan-instrument-personality-functions /mnt/disks/ssd0/agent/llvm-project/compiler-rt/test/hwasan/TestCases/sizes.cpp -nostdlib++ -lstdc++ -o /mnt/disks/ssd0/agent/llvm-project/build/projects/compiler-rt/test/hwasan/X86_64/TestCases/Output/sizes.cpp.tmp
110 mswindows > Clang.Misc::loop-opt-setup.c
Script: -- : 'RUN: at line 1'; c:\ws\w16-1\llvm-project\premerge-checks\build\bin\clang.exe -O1 -fno-unroll-loops -S -o - C:\ws\w16-1\llvm-project\premerge-checks\clang\test\Misc\loop-opt-setup.c -emit-llvm | c:\ws\w16-1\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w16-1\llvm-project\premerge-checks\clang\test\Misc\loop-opt-setup.c

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
atmnpatel requested review of this revision.Aug 29 2020, 5:06 PM

I think the metadata name needs to be reversed, or at least made the opposite of the attribute name.
By default progress is required/guaranteed. With the function attribute it is not. With the metadata it is again for the loop. It has to be this way because the metadata can be dropped. It is only sound to go from required/guaranteed progress to not required/guaranteed, not the other way around.

That means in loop deletion we can remove the loop if:

  1. the trip count is known
  2. the function does not have the attribute
  3. the loop has the metadata

We also need llvm-ir tests for the loop deletion pass that go through all combinations of attribute and metadata.

llvm/include/llvm/Transforms/Utils/LoopUtils.h
232

Describe the metadata rather then the effect.

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

llvm.loop.XXXX, licm is an optimization, this is generic "loop metadata".

atmnpatel updated this revision to Diff 289842.Sep 3 2020, 6:36 PM

Addressed comments, added tests.

atmnpatel updated this revision to Diff 289857.Sep 3 2020, 9:31 PM

Cleaned up tests, and made the changes necessary for changing the attribute names.

atmnpatel retitled this revision from [Loops] Introduces handling for the noprogress loop metadata. to [LoopDeletion] Allows deletion of possibly infinite side-effect free loops.Sep 3 2020, 9:33 PM
atmnpatel edited the summary of this revision. (Show Details)
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
76

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?

211

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
204

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

214

-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.Wed, Oct 7, 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.Wed, Oct 7, 11:30 AM
Herald added a project: Restricted Project. · View Herald TranscriptThu, Oct 8, 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.Fri, Oct 16, 1:13 PM

Reverted to prior diff.

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

fixed splice.

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

LGTM.

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

Nit: add the word back.

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

Added word back in.