Page MenuHomePhabricator

[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

There are a very large number of changes, so older changes are hidden. Show Older Changes
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
59

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
649

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
649

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
649

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
617–618

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?

649

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
26 ↗(On Diff #308249)

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

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
128

Seems like it would be nice to update this comment.

204

and also this comment..?

Addressed comments

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

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

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

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.Mon, Dec 28, 5:06 AM

LGTM, thanks!

clang/test/Misc/loop-opt-setup.c
26 ↗(On Diff #308249)

Can you also explain the C99 case in the comment?

llvm/lib/Transforms/Utils/LoopUtils.cpp
617–618

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.Mon, Dec 28, 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.Tue, Jan 5, 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.Thu, Jan 7, 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.EditedThu, Jan 7, 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.Thu, Jan 7, 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 :) ?