This is an archive of the discontinued LLVM Phabricator instance.

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

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

atmnpatel created this revision.Aug 29 2020, 5:06 PM
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
258

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
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?

214

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
207

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

217

-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.Nov 6 2020, 5:29 PM

final fixes.

This revision was landed with ongoing or failed builds.Nov 6 2020, 7:07 PM
This revision was automatically updated to reflect the committed changes.
atmnpatel reopened this revision.Nov 29 2020, 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.Nov 29 2020, 5:29 PM
atmnpatel updated this revision to Diff 308249.Nov 29 2020, 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.Nov 29 2020, 5:30 PM
nikic added a subscriber: nikic.Nov 30 2020, 1:01 AM
nikic added inline comments.
llvm/lib/Transforms/Utils/LoopUtils.cpp
663

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

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

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.

@nikic Is this OK or do you want it split?

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

Nit: Move DTU into the conditional

@nikic Is this OK or do you want it split?

After looking again, I assume this can't really be split, because prior to this change we would never delete a loop without an exit block, so the code was not reachable before. So this looks fine to me.

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

Unrelated, but why do these updates happen before the branch from preheader to exit is added in IR? Shouldn't it be the other way around according to the DTU contract?

663

You might also move this code after the if/else, as it's the same in both branches. As the update strategy is eager, reusing the same DTU object shouldn't make a difference. (Feel free to leave as is though.)

fhahn added a subscriber: fhahn.Dec 22 2020, 2:22 AM
fhahn added inline comments.
clang/test/Misc/loop-opt-setup.c
27–29

This comment needs updating, there's no loop there now. Or better, add a run-line with a C standard version that does not have the forward progress guarantee, e.g. -std=c99 and one with an explicit standard that has it and have different check lines for the 2 cases.

llvm/test/Other/loop-deletion-printer.ll
17 ↗(On Diff #308249)

Is this change related to the patch? Same for the other test changes that just add willreturn?

jonpa added a subscriber: jonpa.Dec 22 2020, 3:34 PM
jonpa added inline comments.
llvm/lib/Transforms/Scalar/LoopDeletion.cpp
130–131

Seems like it would be nice to update this comment.

211–212

and also this comment..?

Addressed comments

atmnpatel added inline comments.Dec 22 2020, 10:15 PM
llvm/lib/Transforms/Utils/LoopUtils.cpp
637

Isn't that branch added on line 602? My understanding was the changes on line 640 onwards are for removing, not introducing a branch.

llvm/test/Other/loop-deletion-printer.ll
17 ↗(On Diff #308249)

Yep, if these test functions aren't marked willreturn, we won't delete the loop because it could be a legal infinite loop from C/C++.

fhahn added inline comments.Dec 23 2020, 2:05 AM
llvm/test/Other/loop-deletion-printer.ll
17 ↗(On Diff #308249)

I don't think that is the case here. The trip count of the loop here is constant, so it cannot be infinite. Also, the existing code already removes the loop, without willreturn, as implied by no changes to the check lines?

I did not check all other cases, but I would expect that willreturn does not need to be added to cases where the trip count is a known constant and that already get removed.

As expected, @fhahn was right, adding willreturn to all those tests was an artifact from previous revisions of this patch and it passed the tests so I didn't pay them any mind, but I removed them now.

Can you reland this patch now?

Yep, sorry, I'm just waiting for a final stamp of approval from one of the reviewers.

fhahn accepted this revision.Dec 28 2020, 5:06 AM

LGTM, thanks!

clang/test/Misc/loop-opt-setup.c
27–29

Can you also explain the C99 case in the comment?

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

Shouldn't it be the other way around according to the DTU contract?

Yes I think so. Perhaps a missing case in the DTU validator. Probably good to check/fix separately.

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

probably good to also add -verify-dom-info

6

FWIW, I don't think the C code doesn't add much, but I don't have any strong feelings about it. The IR is what is key and it's really small.

This revision is now accepted and ready to land.Dec 28 2020, 5:06 AM

Do you plan to implement gcc’s option in Clang as followup?

-ffinite-loops / -fno-finite-loops
Assume that a loop with an exit will eventually take the exit and not loop indefinitely. This allows the compiler to remove loops that otherwise have no side-effects, not considering eventual endless looping as such.

This option is enabled by default at -O2 for C++ with -std=c++11 or higher.

?

Do you plan to implement gcc’s option in Clang as followup?

I was not planning on it but I can if no one is planning on it and doesn't mind waiting a bit.

Also, clang/test/Misc/loop-opt-setup.c had a bad run line, it's being fixed in D93952, and I'll try to land it again after that.

fhahn added a comment.Jan 5 2021, 11:21 AM

Now that the test is fixed, this could be re-landed, right?

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

fhahn added a comment.Jan 7 2021, 8:44 AM
int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

atmnpatel added a comment.EditedJan 7 2021, 8:56 AM
int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

fhahn added a comment.Jan 7 2021, 9:02 AM

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

The source is C++, so the C11 standard should be irrelevant. I left a comment at D86841, this seems more appropriate to discuss the issue, as it is unrelated to -loop-deletion.

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

For C yes, but are there such rules for C++? GCC in c++ mode does not check for non-zero constant expr and happily performs this optimization.

int a, b;

int f(void) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

int g(int a, int b) {
    while (1) {
        if (a != b) return 1;
    }
    return 0;
}

LLVM does not catch these cases; gcc does.

https://godbolt.org/z/jW7son

Looks like must progress does not get added? If it gets added to the IR the loops get removed: https://godbolt.org/z/77v17P

I might be misunderstanding the standard here but since 1 is a non-zero constant expression, it can't be assumed to terminate by the implementation right? The relevant section from C11 at least is "An iteration statement whose controlling expression is not a constant expression that performs [explanation of what it deems as progress] may be assumed by the implementation to terminate" (C11 6.8.5 p6). I think these cases fall outside of the scope of this particular change ...

For C yes, but are there such rules for C++? GCC in c++ mode does not check for non-zero constant expr and happily performs this optimization.

@xbolva00 want to provide a follow up patch then :) ?

uabelho added a subscriber: uabelho.Oct 3 2022, 6:58 AM

I wrote
https://github.com/llvm/llvm-project/issues/58123
about a crash that I bisected to this patch.

Herald added a project: Restricted Project. · View Herald TranscriptOct 3 2022, 6:58 AM