Page MenuHomePhabricator

[Attributor] Introduce AAAssumptionInfo to propagate assumptions

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



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

Diff Detail

Event Timeline

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

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


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.


Style: move down to the block of includes


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


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


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


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


No this, also elsewhere.


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.


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.


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


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


Same comments as in the other manifest.


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.

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


Made a function that always appends assumptions.


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

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


I would check the cheap part first, so isvalidstate.


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


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.


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.


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

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


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


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


We should not cache "changed" anywhere.


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


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


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.


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


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


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


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".


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.Tue, Nov 9, 8:02 AM

LG, minor comments to address prior to the merge.


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


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

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

Making suggested changes.

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

Fix bug and unused variable.

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