This is an archive of the discontinued LLVM Phabricator instance.

[clang] Add mustprogress and llvm.loop.mustprogress attribute deduction
ClosedPublic

Authored by atmnpatel on Aug 29 2020, 1:38 PM.

Details

Summary

Since C++11, the C++ standard has a forward progress guarantee
[intro.progress], so all such functions must have the mustprogress
requirement. In addition, from C11 and onwards, loops without a non-zero
constant conditional or no conditional are also required to make
progress (C11 6.8.5p6). This patch implements these attribute deductions
so they can be used by the optimization passes.

Diff Detail

Event Timeline

atmnpatel created this revision.Aug 29 2020, 1:38 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 29 2020, 1:39 PM
atmnpatel requested review of this revision.Aug 29 2020, 1:39 PM
atmnpatel edited the summary of this revision. (Show Details)Aug 29 2020, 1:39 PM

Does that wording apply to both the C and C++ (OpenCL?)?
Regardless, might be good to test that.

clang/test/CodeGen/attr-noprogress.c
1–2 ↗(On Diff #288806)

Please just FileCheck the expected output. Bonus points for using llvm/utils/update_cc_test_checks.py

atmnpatel updated this revision to Diff 288817.Aug 29 2020, 4:57 PM
atmnpatel edited the summary of this revision. (Show Details)

Sorry, Fixed the test, added a C++ test. I checked the C++, OpenCL C, and OpenCL C++ specs and couldn't find anything that diverged from C spec in this regard, but none of them explicitly stated this behavior either.

atmnpatel updated this revision to Diff 288818.Aug 29 2020, 4:59 PM

Fixed comment in C++ test.

atmnpatel retitled this revision from [clang] Adds noprogress attribute deduction for infinite loops to [clang] Add noprogress attribute deduction for infinite loops.Aug 29 2020, 5:21 PM
aaron.ballman added inline comments.Aug 31 2020, 6:24 AM
clang/lib/CodeGen/CGLoopInfo.h
211

I'd drop the top-level const on the declaration of NoProgress (that's not a style we typically use in the project).

atmnpatel updated this revision to Diff 289821.EditedSep 3 2020, 3:26 PM

Renamed llvm loop metadata, changed the way it is deduced. Fixed broken test.

atmnpatel marked an inline comment as done.Sep 3 2020, 3:27 PM
atmnpatel added inline comments.
clang/lib/CodeGen/CGLoopInfo.h
211

My bad, thanks!

atmnpatel marked 2 inline comments as done.Sep 3 2020, 3:28 PM
atmnpatel updated this revision to Diff 289849.Sep 3 2020, 8:52 PM

In Summary:

  • I changed the llvm loop metadata name to mustprogress, to indicate that loops with this attribute are required to have side-effects.
  • The mayprogress function attribute is applied to functions where an infinite loop is found with a constant conditional.
  • The mustprogress attribute is applied to loops within a mayprogress function that do not have a constant conditional.
atmnpatel retitled this revision from [clang] Add noprogress attribute deduction for infinite loops to [clang] Add mayprogress and llvm.loop.mustprogress attribute deduction.Sep 3 2020, 10:00 PM
atmnpatel edited the summary of this revision. (Show Details)
atmnpatel updated this revision to Diff 289997.Sep 4 2020, 11:03 AM

Renamed mayprogress to maynotprogress.

atmnpatel updated this revision to Diff 291249.Sep 11 2020, 9:29 AM

More tightly follows both the C and C++ standards. maynotprogress is only added to C functions when compiled with C11 or later.

uenoku added a subscriber: uenoku.Sep 11 2020, 9:46 AM
atmnpatel updated this revision to Diff 291471.Sep 13 2020, 1:00 PM

Flipped direction.

atmnpatel retitled this revision from [clang] Add mayprogress and llvm.loop.mustprogress attribute deduction to [clang] Add mustprogress and llvm.loop.mustprogress attribute deduction.Sep 13 2020, 3:56 PM
atmnpatel edited the summary of this revision. (Show Details)
atmnpatel updated this revision to Diff 291567.Sep 14 2020, 7:11 AM

Fixed failing test.

atmnpatel updated this revision to Diff 291581.Sep 14 2020, 8:22 AM

Tests renamed.

In what situation do we generate mustprogress function attributes now? I was expecting them in clang/test/CodeGen/attr-mustprogress.cpp but did not see any.

atmnpatel updated this revision to Diff 294569.Sep 27 2020, 3:13 PM

Split them into pre and post forward progress requirement tests, now the difference is much easier to catch.

atmnpatel added inline comments.Sep 27 2020, 3:14 PM
clang/test/CodeGen/attr-mustprogress-0.cpp
3

changing this asap.

atmnpatel updated this revision to Diff 294570.Sep 27 2020, 3:20 PM

All language standards (minus gnu extensions) are now tested.

atmnpatel updated this revision to Diff 294575.Sep 27 2020, 3:52 PM

rebase to hopefully fix buildbot

jdoerfert added inline comments.Sep 28 2020, 1:31 PM
clang/test/CodeGen/attr-mustprogress-1.cpp
25

Now here, and below with while(1) I would *not* expect mustprogress.

186

Here I would not expect the function attr but the metadata on the second loop. I guess we might want to add the metadata always for loops w/o a constant condition especially because the order of the two loops might be swapped (please add a test).

atmnpatel updated this revision to Diff 294864.Sep 28 2020, 7:07 PM

more fixes.

jdoerfert added inline comments.Sep 29 2020, 9:29 AM
clang/lib/CodeGen/CGStmt.cpp
803

Also in C? And C2x in the end is probably CPLusPlus2x?

901

Maybe call this FnIsMustProgress or the other one LoopMustProgress.

905

same as above

951

same as above.

Don't we have to update IsMustProgress here too?

clang/lib/CodeGen/CodeGenFunction.cpp
1166

no braces. why the mustprogress check?

1170

Say that we do this late because we need to see the body.

atmnpatel updated this revision to Diff 295119.Sep 29 2020, 2:12 PM

NFC fixes.

atmnpatel marked 3 inline comments as done.Sep 29 2020, 4:19 PM
atmnpatel added inline comments.
clang/lib/CodeGen/CGStmt.cpp
803

Also in C?

Not quite sure what you mean here.

But LangOptions.def seems to say that C2x is the upcoming C standard, not any upcoming C++ standard.

atmnpatel updated this revision to Diff 295149.Sep 29 2020, 4:24 PM

Fixing buildkite build.

aqjune added inline comments.Sep 30 2020, 3:22 PM
clang/lib/CodeGen/CGStmt.cpp
803

A silly question: does old C/C++ not guarantee that loops should make forward progress?

atmnpatel added inline comments.Sep 30 2020, 10:29 PM
clang/lib/CodeGen/CGStmt.cpp
803

Nope, it was introduced explicitly simultaneously in C11 (6.8.5p6) and C++11 has it implicitly through [intro.progress].

One minor nit from me.

@jyknight @aaron.ballman @rjmccall any more thoughts?

clang/lib/CodeGen/CGStmt.cpp
803

Move this condition into a helper function somewhere with documentation. If we use another (similar) condition the same. This has to be updated over time and that way makes it much easier (also to read).

atmnpatel updated this revision to Diff 296752.Oct 7 2020, 11:24 AM

Bump for bot.

atmnpatel updated this revision to Diff 302407.Nov 2 2020, 2:21 PM
  • Added triple to fix mangling errors in test
  • Modified (unrelated) recently added test to have the mustprogress attribute
jdoerfert accepted this revision.Nov 2 2020, 5:18 PM

LGTM, some nits

clang/lib/CodeGen/CGStmt.cpp
802

Nit: Add braces here.

903

Same as above.

This revision is now accepted and ready to land.Nov 2 2020, 5:18 PM
atmnpatel updated this revision to Diff 302459.Nov 2 2020, 9:51 PM

ignore, testing pre-build bots again.

atmnpatel updated this revision to Diff 302606.Nov 3 2020, 10:04 AM

Hopefully the unrelated hwasan test failure is now fixed on master, trying again.

This revision was landed with ongoing or failed builds.Nov 4 2020, 7:03 PM
This revision was automatically updated to reflect the committed changes.
fhahn added inline comments.
clang/lib/CodeGen/CGStmt.cpp
799

Shouldn't this only apply for C? http://eel.is/c++draft/intro.progress#1 does not seem to have this escape hatch?

See the example by @xbolva00 for which we fail to eliminate the loops from a C++ source https://godbolt.org/z/jW7son

I'm happy to add a patch amending this, the reason it wasn't done that way was because at the time and even now, out of icc/clang/msvc/gcc, gcc seems to be the only one that happily removed such loops in C++ (https://godbolt.org/z/W9vj99), and I didn't have a particularly strong opinion on which way we should lean at the time.

fhahn added a comment.Jan 8 2021, 7:17 AM

I'm happy to add a patch amending this, the reason it wasn't done that way was because at the time and even now, out of icc/clang/msvc/gcc, gcc seems to be the only one that happily removed such loops in C++ (https://godbolt.org/z/W9vj99), and I didn't have a particularly strong opinion on which way we should lean at the time.

I think ideally we would make this decision on what the standard allows. AFAICT the C++ spec for iteration statements (http://eel.is/c++draft/stmt.iter) does not have the same escape hatch as C. So IMO the current behavior is surprising and potentially leads to confusion for users (e.g. wondering why are some loops removed, but others not, even if the C++ spec allows for both to be removed).

There may be practical reasons for opting to be more conservative (e.g. if it would break a large number of user codes), but so far there seems to be no such indication in the discussion. It would probably be good to also implement -ffinite-loops as suggested by @xbolva00 so users can better control this.