This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Introduce AAAssumptionInfo to propagate assumptions
ClosedPublic

Authored by jhuber6 on Oct 4 2021, 6:19 AM.

Details

Summary

This patch introduces a new abstract attributor instance that propagates
assumption information from functions. Conceptually, if a function is
only called by functions that have certain assumptions, then we can
apply the same assumptions to that function. This problem is similar to
calculating the dominator set, but the assumptions are merged instead of
nodes.

Diff Detail

Event Timeline

jhuber6 created this revision.Oct 4 2021, 6:19 AM
jhuber6 requested review of this revision.Oct 4 2021, 6:19 AM
Herald added a reviewer: baziotis. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript
jdoerfert added inline comments.Oct 4 2021, 9:44 AM
llvm/include/llvm/IR/Assumptions.h
60

Consider passing the set as reference, unsure how much work copying it is

llvm/include/llvm/Transforms/IPO/Attributor.h
4752

I don't like the pair approach for long lived data. Make it a struct with properly named members. Costs the same but is much easier to read.

4757
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
15

Style: move down to the block of includes

9671

This should be in the constructor. Initialize can and should already look at the underlying value.

9724
9727
9732

Does this overwrite an existing assumptions attribute? Do we have a test for that?

9734

Adding assumptions is a change. Maybe return if it's empty with unchanged and otherwise add + CHANGED.

9737–9740

Not needed. If you just redirect to the base class, remove it.

9747

No this, also elsewhere.

9753

getIntersection returns if a change was made. CallSitePred should return false only if the traversal of call sites failed and we should give up. I think the return value of the CB here should be:
NotUniversal && AssumptionSet.empty() or something like that.

9759

This is not how checkForAllXXXX work. If they return false it means no all XXXX have been visited and you cannot rely on the information gathered.
Basically if (!checkForAllCXXXX(...)) return indicatePessimisticFixpoint(); is the way to go almost always.

9766

This won't be necessary because checkForAllCallSites returns false if you asked for *all* and not all call be visited.

9770

This is invariant, so it should happen in the initialize.

9809

Same comments as in the other manifest.

llvm/test/Transforms/Attributor/assumes_info.ll
3

Use the same run lines as other tests (4 total)

jhuber6 updated this revision to Diff 377029.Oct 4 2021, 1:51 PM

Addressing comments.

jhuber6 marked 17 inline comments as done.Oct 4 2021, 1:57 PM
jhuber6 added inline comments.
llvm/include/llvm/IR/Assumptions.h
60

Passing it as a reference would require some external lifetime right? Copy elision should apply in this case, but I'm not sure.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
9732

Made a function that always appends assumptions.

9770

The set at some points will still be in the universal state, we only want to add this attribute once it has some known values.

jdoerfert added inline comments.Oct 4 2021, 2:39 PM
llvm/lib/Transforms/IPO/Attributor.cpp
2507

We need to initialize this for call sites too, at least if they are not direct call sites.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
9651
9654

I would check the cheap part first, so isvalidstate.

9674

This makes it sound like a push-scheme while the updatImpl uses a pull-scheme.

9711

If the state has "known" and "assumed" assumptions (see also below) you can always fallback to the known ones if you indicate a pessimistic fixpoint. You basically reimplemented parts of the inidicatePessimistic/OptimisticFixpoint stuff here but only partially as part of the state. In line 9742 you do Assumed = Known, which is the definition of indicatePessimisticFixpoint in the integer and boolean state. The special case (line 9737/8) is not necessary at all as Known == Assume == empty in that case anyway.

9723

This is basically the "known assumptions" set while Assumptions is the "assumed assumptions" set. Maybe use those terms to match the rest of the AAs. We might even need to provide two APIs to query a known and an assumed assumption.
It's also not clear why this is only in the Function AA and not the Impl as call sites can have assumptions too which are not part of the caller or callee.

9756

I doubt assumptions.empty() means something changed. If you return changed and nothing changed you just force a timeout after the max iteration count.

jhuber6 updated this revision to Diff 377291.Oct 5 2021, 10:24 AM
jhuber6 marked 3 inline comments as done.

Rewriting to use standard state encoding semantics. This currently crashes for
the test case provided when using the cgscc pass for some reason.

jhuber6 marked 7 inline comments as done.Oct 5 2021, 10:26 AM
jhuber6 updated this revision to Diff 377310.Oct 5 2021, 11:16 AM

Changing known and assumed usage.

jdoerfert added inline comments.Oct 6 2021, 8:45 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
2524

Unsure if I'd call this "UniversalSet" as it might not be a universal set ;)

2588

Why would it not be valid if assumed is not universal anymore?
One way is to define Assumed.empty() as invalid.

2624

You should not remove any known assumptions, so remove known from RHS first.

2642

We should not cache "changed" anywhere.

llvm/lib/IR/Assumptions.cpp
129

The two functions above are equal, make it a local template function and call it from the two exposed ones.

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
9702

You can/should query the call site AA here. Through inlining and such the call site might have more assumptions than the caller.

9718

The way this is set up it might signal change even if things did not change. That is bad as it will spin until the iteration limit is reached. Either consider known in the intersect or keep track of the number of assumptions you had before and have now.

9730

Technically we can add the caller assumptions and the callee assumptions to the known set here if we want. Not needed right now though.

9732

No need to union something into assumed which is universal at this point.

9747

You can add the Assumed here. We are in a fixpoint state but the AA above might not have been informed of that yet.

9761

We should not look at the callee but caller. The callee is known and asked for "hasAssumption" queries anyway. The caller is what might disappear while the call site sticks around. So propagation direction is "caller -> call site -> callee".

9763

This doesn't actually update the state of this AA at all. You want to add the caller assumptions to the call site and indicate a change if that caused the call site to change.

jhuber6 updated this revision to Diff 377595.Oct 6 2021, 10:20 AM

Addressing comments.

jhuber6 updated this revision to Diff 377698.Oct 6 2021, 2:45 PM

More changes, I think it works this time.

jhuber6 updated this revision to Diff 377701.Oct 6 2021, 3:00 PM
jhuber6 marked an inline comment as done.

Fixing isValidState.

jhuber6 marked 9 inline comments as done.Oct 6 2021, 3:15 PM
jhuber6 updated this revision to Diff 378029.Oct 7 2021, 3:19 PM

Fixing issue not initializing isAtFixpoint.

jhuber6 updated this revision to Diff 378276.Oct 8 2021, 9:37 AM

The CallBase instance should inherit the attributes from the function it's
calling on initialization.

jhuber6 updated this revision to Diff 378305.Oct 8 2021, 10:46 AM

Fix assumption checking and manifest on call sites.

jdoerfert accepted this revision.Nov 9 2021, 8:02 AM

LG, minor comments to address prior to the merge.

llvm/include/llvm/Transforms/IPO/Attributor.h
2521
2592
2620
2626
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
9754

The parent function assumptions should always be in the assumed set, adding them here should not be necessary.

9781

Also add the scope assumptions here, all of them are known.

This revision is now accepted and ready to land.Nov 9 2021, 8:02 AM
jhuber6 updated this revision to Diff 385844.Nov 9 2021, 8:58 AM

Making suggested changes.

jhuber6 updated this revision to Diff 385948.Nov 9 2021, 1:07 PM

Fix bug and unused variable.

This revision was landed with ongoing or failed builds.Nov 9 2021, 2:39 PM
This revision was automatically updated to reflect the committed changes.