Page MenuHomePhabricator

[InstCombine] convert assumes to operand bundles
ClosedPublic

Authored by Tyker on Jun 27 2020, 4:23 AM.

Details

Summary

Instcombine will convert the nonnull and alignment assumption that use the boolean condtion
to an assumption that uses the operand bundles when knowledge retention is enabled.

Diff Detail

Event Timeline

Tyker created this revision.Jun 27 2020, 4:23 AM
Herald added a project: Restricted Project. · View Herald TranscriptJun 27 2020, 4:23 AM
Tyker updated this revision to Diff 273897.Jun 27 2020, 4:28 AM

there is an NFC change to the test that was excluded from the diff to make it easier to read.

Initial comments.

llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h
45

Please add some documentation here.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1535

I don't get this. Doesn't it replace the operand of an assume with false if there is one with the same condition following? That seems wrong, maybe "true" is what you wanted?

1558

Comments on what is happening here and below please.

1570

Isn't this call the same as the 5 lines before?

llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp
308

It is odd that this takes an insertion point but apparently does not insert the instruction. Can we change either to confuse me less?

llvm/test/Transforms/InstCombine/assume.ll
186–187

Why do we have SAME checking the function twice? Is this a bug in the update script?

Tyker updated this revision to Diff 275501.Jul 4 2020, 7:42 AM
Tyker marked 6 inline comments as done.

addressed the comments
the previous patch had many stupid mistakes

llvm/test/Transforms/InstCombine/assume.ll
186–187

Is this a bug in the update script?

perhaps but after purging every CHECK line the issue is gone.

Looks conceptually good but there are some oddities, potentially in the lookup.

llvm/test/Transforms/InstCombine/assume.ll
48

This doesn't seem to work properly.

@lebedev.ri found other problematic cases. One that I now know of is multiple bundles: https://godbolt.org/z/To5obz

316

Can u add a FIXME or NOTE here to indicate we could duplicate the load instead and keep a assume with ["nonnull"(%load)] around.

499

Again a fold missing CMP = true

Tyker updated this revision to Diff 276824.Jul 9 2020, 1:22 PM

I had to merge the previous patch with other i had laying around and add some more
to make the bundle mode be at least as good as the default. so this revision got
quite a bit bigger.

I hope its still fine.

jdoerfert added inline comments.Aug 4 2020, 5:37 PM
llvm/include/llvm/Analysis/AssumeBundleQueries.h
111

This is not a strict order. Let's use AttrKind and WasOn as well.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
93

Add a sentence what this controls/means.

1520

I'd add a message to the assert and a comment before the lambda.

1595

Shouldn't we build a GEP for the offset instead, if the offset is not a multiple of the alignment that is.

Tyker updated this revision to Diff 283996.Aug 7 2020, 12:46 PM
Tyker marked 3 inline comments as done.

addressed comments

jdoerfert added inline comments.Aug 10 2020, 11:16 AM
llvm/include/llvm/Analysis/AssumeBundleQueries.h
114

Nit: Add a message to the assert please explaining what usage is allowed.

llvm/lib/Analysis/Loads.cpp
99

Nit: Add a comment describe what is happening here.

I guess we should have a todo that states partial information, e.g., only AlignRK or DerefRK, should be used in other places too. The entire function should be rewritten for that so it is out of scope.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1595

At least a TODO would be good.

Tyker updated this revision to Diff 287209.Aug 22 2020, 11:02 AM
Tyker marked an inline comment as done.

Addressed comments.

Tyker updated this revision to Diff 294500.Sep 26 2020, 7:00 AM

rebased
add cannonicalization of assume bundles

jdoerfert added inline comments.
llvm/test/Transforms/InstCombine/assume.ll
270

It is questionable if we should prefer the assume or the !nonnull metadata here.

748

Also unclear if this is better than the GEP. I guess the case with an offset of 4 is clear but this one I don't know.

@Tyker are you going to upstream this? If not, can someone take over?

Tyker updated this revision to Diff 317164.Jan 16 2021, 3:38 AM

@Tyker are you going to upstream this? If not, can someone take over?

I can do the upstreaming but i don't know what the current state is for upstreaming this.

llvm/test/Transforms/InstCombine/assume.ll
748

this is one of the default canonicalization done when building assumes maybe we should keep both.
the idea behind it is to make the knowledge usable by all derived pointers and also minimize the number of assumes but i agree it is not clear its better.

Tyker added inline comments.Jan 16 2021, 3:39 AM
llvm/test/Transforms/InstCombine/assume.ll
270

fixed

@Tyker are you going to upstream this? If not, can someone take over?

I can do the upstreaming but i don't know what the current state is for upstreaming this.

I think there are different things in this patch, some can be upstreamed some need minor adjustment, and some I don't understand yet. See my comments. It would be great if we can finish this line of assume optimizations though.

llvm/include/llvm/Transforms/Utils/AssumeBundleBuilder.h
67

Nit: The first sentence is hard to read.

llvm/lib/Analysis/ValueTracking.cpp
756 ↗(On Diff #317164)

Why can we allow ephemeral here without potentially throwing away an assume that was used to argue it itself is useless? Should we not do the AllowEphemeral stuff for now?

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1522

Nit: Typo, arguement

1626

Nit: typo: help

1633

losses what?

1641

I'm not sure why we return nullptr here and not continue going.

llvm/lib/Transforms/Utils/AssumeBundleBuilder.cpp
315

!Assume means Assume->GetModule() will crash, probably add a DL argument.

llvm/test/Analysis/ValueTracking/assume.ll
75

How do we get an alignment of 8 here?

Tyker updated this revision to Diff 320289.Jan 30 2021, 1:26 AM
Tyker marked 13 inline comments as done.

rebased, addressed comments. fixed issues.

llvm/lib/Analysis/ValueTracking.cpp
756 ↗(On Diff #317164)

i fixed the issue AllowEphemeral was "solving" by other means.

llvm/test/Analysis/ValueTracking/assume.ll
75

this was just an addition arbitrary test. left the old test as is a added a new.

llvm/test/Transforms/InstCombine/assume.ll
748

I think we should try to avoid having any extra instructions that are only used by an assume because it is part of the issue with the boolean assume model.

With the current representation of RetainedKnowledge there is no way to represent offsets.
this restriction could be lifetd by refactoring and is not the only limitation of RetainedKnowledge that could be removed.
when forming a RetainedKnowledge of a "align"(i8* %3, i64 16, i64 4) the RetainedKnowledge will conservativly have the value 4.

since canonicalization is done on RetainedKnowledge cannonicalization can't interact with offsets and stays conservative.

jdoerfert accepted this revision.Jan 31 2021, 10:57 AM

One minor comment and a nit, I assume those can be addressed before committing the patch. LGTM, thanks for finishing this up!

llvm/lib/Analysis/Loads.cpp
105

Nit: If you move the lambda declaration before the conditional, we get one level of indirection less.

llvm/lib/Transforms/InstCombine/InstCombineCalls.cpp
1637

Nit: early continue, if (CanonRK == RK) continue

1653

Again, unsure why we return. there might be operand bundles left.

This revision is now accepted and ready to land.Jan 31 2021, 10:57 AM
This revision was landed with ongoing or failed builds.Feb 9 2021, 10:34 AM
This revision was automatically updated to reflect the committed changes.

Hi. I suspect this patch might be causing this test failure we're seeing on our builders (https://luci-milo.appspot.com/p/fuchsia/builders/ci/clang-linux-x64/b8855749711840653472?):

FAIL: Clang :: CodeGen/builtin-align-assumption.c (3421 of 27242)
******************** TEST 'Clang :: CodeGen/builtin-align-assumption.c' FAILED ********************
Script:
--
: 'RUN: at line 3';   /b/s/w/ir/x/w/staging/llvm_build/bin/clang -cc1 -internal-isystem /b/s/w/ir/x/w/staging/llvm_build/lib/clang/13.0.0/include -nostdsysteminc -triple=x86_64-unknown-unknown /b/s/w/ir/x/w/llvm-project/clang/test/CodeGen/builtin-align-assumption.c -emit-llvm -O1 -o - | /b/s/w/ir/x/w/staging/llvm_build/bin/FileCheck /b/s/w/ir/x/w/llvm-project/clang/test/CodeGen/builtin-align-assumption.c
--
Exit Code: 1

Command Output (stderr):
--
/b/s/w/ir/x/w/llvm-project/clang/test/CodeGen/builtin-align-assumption.c:6:11: error: CHECK: expected string not found in input
// CHECK: call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 64 dereferenceable(16) {{%.+}}, i8* nonnull align 1 dereferenceable(16) {{%.+}}, i64 16, i1 false)
          ^
<stdin>:7:32: note: scanning from here
define dso_local void @align_up(i8* nocapture readonly %data, i32* %ptr) local_unnamed_addr #0 {
                               ^
<stdin>:16:2: note: possible intended match here
 call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 4 dereferenceable(16) %aligned_result, i8* nonnull align 1 dereferenceable(16) %data, i64 16, i1 false)
 ^

Input file: <stdin>
Check file: /b/s/w/ir/x/w/llvm-project/clang/test/CodeGen/builtin-align-assumption.c

-dump-input=help explains the following input dump.

...

********************
Testing:  0.. 10.. 20.. 30.. 40.. 50.. 60.. 70.. 80.. 90.. 
********************
Failed Tests (1):
  Clang :: CodeGen/builtin-align-assumption.c

Would you mind taking a look and either send out a fix or reverting? Thanks.

Hi @Tyker , I believe this patch is causing the following test to fail: clang/test/CodeGen/builtin-align-assumption.c

Here's some buildbot links for reference:
http://lab.llvm.org:8011/#/builders/123/builds/2854
http://lab.llvm.org:8011/#/builders/110/builds/888

Could you take a look?

dmajor added a subscriber: dmajor.Feb 9 2021, 2:34 PM
jdoerfert added inline comments.Sat, Mar 27, 1:34 PM
llvm/test/Transforms/InstCombine/assume.ll
2

It seems the RUN lines did not get included in this commit. I doubt this is testing much right now :(