This is an archive of the discontinued LLVM Phabricator instance.

[AssumeBundles] Use operand bundles to encode alignment assumptions
ClosedPublic

Authored by Tyker on Dec 19 2019, 5:38 PM.

Details

Summary
NOTE: There is a mailing list discussion on this: http://lists.llvm.org/pipermail/llvm-dev/2019-December/137632.html

Complemantary to the assumption outliner prototype in D71692, this patch
shows how we could simplify the code emitted for an alignemnt
assumption. The generated code is smaller, less fragile, and it makes it
easier to recognize the additional use as a "assumption use".

As mentioned in D71692 and on the mailing list, we could adopt this
scheme, and similar schemes for other patterns, without adopting the
assumption outlining.

Diff Detail

Event Timeline

jdoerfert created this revision.Dec 19 2019, 5:38 PM
Herald added projects: Restricted Project, Restricted Project. · View Herald TranscriptDec 19 2019, 5:38 PM

Unit tests: unknown.

clang-tidy: unknown.

clang-format: unknown.

Build artifacts: diff.json, console-log.txt

Unit tests: fail. 60947 tests passed, 20 failed and 726 were skipped.

failed: Clang.CodeGen/align_value.cpp
failed: Clang.CodeGen/builtin-assume-aligned.c
failed: Clang.CodeGen/builtin-movdir.c
failed: Clang.CodeGen/catch-alignment-assumption-attribute-align_value-on-lvalue.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-align_value-on-paramvar.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-alloc_align-on-function-variable.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-alloc_align-on-function.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-assume_aligned-on-function-two-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-attribute-assume_aligned-on-function.cpp
failed: Clang.CodeGen/catch-alignment-assumption-blacklist.c
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-three-params-variable.cpp
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-three-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-builtin_assume_aligned-two-params.cpp
failed: Clang.CodeGen/catch-alignment-assumption-openmp.cpp
failed: Clang.OpenMP/simd_codegen.cpp
failed: Clang.OpenMP/simd_metadata.c
failed: Clang.OpenMP/target_teams_distribute_parallel_for_simd_codegen.cpp
failed: LLVM.Transforms/AlignmentFromAssumptions/simple32.ll
failed: LLVM.Transforms/Inline/align.ll
failed: LLVM.Transforms/InstCombine/assume.ll

clang-tidy: fail. Please fix clang-tidy findings.

clang-format: fail. Please format your changes with clang-format by running git-clang-format HEAD^ or applying this patch.

Build artifacts: diff.json, clang-tidy.txt, clang-format.patch, CMakeCache.txt, console-log.txt, test-results.xml

fhahn added a subscriber: fhahn.Dec 20 2019, 3:41 AM

What's the status here?

@lebedev.ri We'd need to identify other uses of the alignment encoding in-tree so we can replace them as well. Also, this patch uses not only the alignment but also the offset in the operand bundle. We can either allow that or encode the offset via a gep in the IR. I guess the latter is easier to implement until we have more reasons to allow more complex operand bundles (which we will need to have eventually).

@Tyker Do you want to take this?

Tyker added a comment.Apr 5 2020, 11:25 AM

@lebedev.ri We'd need to identify other uses of the alignment encoding in-tree so we can replace them as well. Also, this patch uses not only the alignment but also the offset in the operand bundle. We can either allow that or encode the offset via a gep in the IR. I guess the latter is easier to implement until we have more reasons to allow more complex operand bundles (which we will need to have eventually).

for now i think we will stay with the current "simple" alignment assumptions in operand bundles. but we can improve it later.

@Tyker Do you want to take this?

i am fine with taking this. but there is a few thing to do before this.

i think that this patch depends on a few things:

  • add an API to build assumes from provided knowledge.
  • update users of alignment assumptions.

and a few things that i would like to do before:

  • finish patches currently in review.
  • improve generation of assume with operand bundles to minimize duplicates and extra instructions.
Tyker commandeered this revision.May 20 2020, 5:39 AM
Tyker edited reviewers, added: jdoerfert; removed: Tyker.
Tyker updated this revision to Diff 265215.May 20 2020, 5:42 AM
Tyker retitled this revision from [WIP] Use operand bundles to encode alignment assumptions to [AssumeBundles] Use operand bundles to encode alignment assumptions.
Tyker edited the summary of this revision. (Show Details)

i rebased the patch and adapted the current code on assume bundles and tests

I guess alignment is one of the main users of the old format, great to see it go :)

First set of comments.

llvm/lib/Analysis/AssumeBundleQueries.cpp
104

I think this is a problem for things like deref which should default to 0?

110

Is this the min of the alignment and offset? If so, I'm not sure about min. Either way, can you clang format this and add a comment why alignment is special and how it looks?

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

Can we split these changes off. Seem unrelated and easier.

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp
273

I'm curious, why was this needed?

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

Can you add the "beginning" of the operand bundles here so it becomes clear we do not have a no-op assume.

Is there a good reason for this to use the same llvm.assume intrinsic as before?

Are there restrictions about what assumptions can be combined on a single intrinsic call? There can only be one bundle of a particular name on an instruction, right?

llvm/lib/IR/Verifier.cpp
4418

Should the alignment and offset be restricted to constants and given value restrictions?

Tyker updated this revision to Diff 265692.May 22 2020, 3:29 AM
Tyker marked 5 inline comments as done.

addressed comments

Tyker added a comment.May 22 2020, 3:55 AM

Is there a good reason for this to use the same llvm.assume intrinsic as before?

thee hasn't been any discussion i am aware of on this topic.
but personally i think keeping the same intrinsic makes sens because it logically expresses an assumption hence assume is a good name.
and most passes don't need to treat classic assumes differently from assume with operand bundles.

Are there restrictions about what assumptions can be combined on a single intrinsic call? There can only be one bundle of a particular name on an instruction, right?

there is any IR legality restriction about what combination or number of bundles can be present in an assume. however there is restrictions about argument of a given bundle.
having a single "align" bundle is just how the front-end used assume bundles for its alignment assumptions.

for example:
to salvage a store like
store i8 0, i8* %P, align 1
we could generate
call void @llvm.assume(i1 true) [ "dereferenceable"(i8* %P, i64 1), "nonnull"(i8* %P) ]

llvm/lib/Analysis/AssumeBundleQueries.cpp
104

currently only Alignment can have a non constant argument. but yes this will change if we support non-constant integer for deref.

the verifier has been updated this way, but i added an assert to make it clear.

110

Is this the min of the alignment and offset?

Yes

If so, I'm not sure about min

the objective of this is to make sure that getKnowledgeFromBundle doesn't misinterpret the contents of a bundles with a non-zero offset.
the description of MinAlign seems to match with what i needed

/// A and B are either alignments or offsets. Return the minimum alignment that
/// may be assumed after adding the two together.

the results seems to be correct aswell.

llvm/lib/IR/Verifier.cpp
4418

the system operand bundles are replacing could deal with non-constant indexes and offsets
so i adapted alignment assume bundles to handle non-constant arguments.

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp
273

this code is part of the from the previous version of the patch, i left it untouched because it seemed to work as intended.

changes in this function seem to have no impact on the resulting behavior. and could be removed.

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

i don't think call void @llvm.assume(i1 false) is no-op since it exhibits UB. but it is redundant.
anyway this has been split of to an other patch.

there is any IR legality restriction about what combination or number of bundles can be present in an assume. however there is restrictions about argument of a given bundle.
having a single "align" bundle is just how the front-end used assume bundles for its alignment assumptions.

Hmm. It does seem to be true that operand bundles don't inherently enforce that the names are unique on a callsite; the verifier just has an ever-growing list of bundles that it does that for specially. That feels weird to me, but alright.

I think the code looks good, we should make the test changes clearer, see below.

clang/test/CodeGen/align_value.cpp
7

Can you first make an NFC patch introducing autogenerated check lines for the tests, with --function-signature please. That way the difference becomes clear here.

I don't think such a patch is controversial but we should give others the chance to comment on it.

llvm/lib/IR/IRBuilder.cpp
1084

Nit: Make it size 4 to avoid a trivial dynamic allocation

I think this should go on, could you address the minor comments so we can merge it?

Tyker updated this revision to Diff 272194.Jun 19 2020, 3:10 PM

sorry for not doing much recently.

i split with an NFC patch with only test updates.
and addressed comments

jdoerfert accepted this revision.Jun 23 2020, 1:28 PM

Two nits and one question about removed check lines. If they can be re-added, LGTM. Otherwise we need to look into that.

clang/lib/CodeGen/CodeGenFunction.cpp
2187

Maybe invert the conditions:

llvm::Instruction *Assumption = Builder.CreateAlignmentAssumption(
      CGM.getDataLayout(), PtrValue, Alignment, OffsetValue);
 if (!SanOpts.has(SanitizerKind::Alignment))
   return;
//sanitizer stuff
clang/test/CodeGen/builtin-align.c
48

Why did these go away?

llvm/test/Transforms/AlignmentFromAssumptions/simple32.ll
14

I think we should change to the new encoding here too.

This revision is now accepted and ready to land.Jun 23 2020, 1:28 PM
Tyker updated this revision to Diff 272968.Jun 24 2020, 4:13 AM
Tyker marked 2 inline comments as done.

addressed comments

This revision was automatically updated to reflect the committed changes.
This revision is now accepted and ready to land.Jul 4 2020, 2:23 PM
lebedev.ri requested changes to this revision.Jul 4 2020, 2:23 PM
This revision now requires changes to proceed.Jul 4 2020, 2:23 PM
Tyker updated this revision to Diff 275550.Jul 5 2020, 8:23 AM

fixed the issue with multiple align in a single assume.

jdoerfert accepted this revision.Jul 7 2020, 5:13 PM

LGTM. @lebedev.ri ?

llvm/lib/Transforms/Scalar/AlignmentFromAssumptions.cpp
227

Early exit please.

Tyker updated this revision to Diff 276498.Jul 8 2020, 11:32 AM

addressed commemt.

thopre added a subscriber: thopre.Jul 13 2020, 2:52 AM
This revision was not accepted when it landed; it landed in state Needs Review.Jul 13 2020, 4:06 PM
This revision was automatically updated to reflect the committed changes.
Tyker added a comment.Sep 12 2020, 5:13 AM
This comment was removed by Tyker.
Tyker updated this revision to Diff 291382.Sep 12 2020, 5:35 AM

rebased