This is an archive of the discontinued LLVM Phabricator instance.

[WIP][Attributor] AAReachability Attribute
ClosedPublic

Authored by pgode on Nov 14 2019, 4:08 AM.

Details

Summary

Working towards Johannes's suggestion for fixme, in Attributor's Noalias attribute deduction.
(ii) Check whether the value is captured in the scope using AANoCapture.
FIXME: This is conservative though, it is better to look at CFG and
// check only uses possibly executed before this call site.

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

Diff Detail

Event Timeline

pgode created this revision.Nov 14 2019, 4:08 AM
Herald added a project: Restricted Project. · View Herald Transcript
pgode retitled this revision from [WIP][NOT FOR COMMIT] AAReachability Attribute to [WIP][NOT FOR COMMIT][Attributor] AAReachability Attribute.Nov 14 2019, 4:09 AM

Thanks for putting this in the open! I hope we can improve this and get it in!


Here are some high-level comments I had after looking over the patch:

I don't know how we would handle "reachability" as an actual IR-attribute. For now you might want to strip this to only the Attributor parts which can deal with it as an "abstract" attribute, like liveness or heaptostack.

We should start with AAReachabilityFunction only which answers the following questions:
Given two IRPositions, is one assumed/known reachable from another.
To this end, AAReachability will need to expose these query functions, e.g.,:
AAReachability::isAssumedReachable(const IRPosition &From, const IRPosition &To)
AAReachability::isKnownReachable(const IRPosition &From, const IRPosition &To)

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

You don't need this to be an IRAttribute, an AbstractAttribute is sufficient. You will need to store the IRPosition in the class explicitly though.

llvm/lib/Transforms/IPO/Attributor.cpp
5482

I don't know if we need to create AAReachability or if we only want to "derive" it whenever another attribute requests the information. Since for now we cannot manifest it, I would not try to create it eagerly but only on demand. That means, remove these two getOrCreateAAFor calls but we later add getOrCreateAAFor<AAReachability> as part of the deduction (via updateImpl) in other attributes.

5828

We should start by a function only abstract attribute (like AAHeapToStack).
The macro for those is CREATE_FUNCTION_ONLY_ABSTRACT_ATTRIBUTE_FOR_POSITION
and you only need the AAReachabilityFunction derivation of AAReachability.
(See the main comment).

Nice to see other people working on this! :)

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

I guess then we don't even need to have an actual IR attribute (and all the boilerplate that comes with it).

uenoku added a comment.EditedNov 14 2019, 10:08 PM

I think reachability attribute is a good idea!

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

At the starting point, in AAReachability deduction, it might be a good idea to use AAIsDead to determine that "does execution at point A never reach point B" (because AAIsDead answers whether point B is dead).

Btw, I think AAIsDead is a strict subset of AAReachability. If we have AAReachability::isAssumedReachable(Instruction &From, Instruction &To), AAIsDead::isAssumedDead(Instruction &I) is equivalent to `!AAReachability::isAssumedReachable(EntryPointOfFunction, I).So you should probably extend AAIsDead.

Maybe you can refer must-be-executed-context which handles the similar property.

I think reachability attribute is a good idea!

A Reachability abstract attribute answers the question "does execution at point A potentially reach point B". If this question is answered with false for all other uses of the value that might be captured, we know it is not *yet* captured and can continue with the noalias deduction. Currently, information AAReachability provides is completely pessimistic.

At the starting point, it might be a good idea to use AAIsDead to determine that "does execution at point A never reach point B" (because AAIsDead answers whether point B is dead).

Btw, I think AAIsDead is a strict subset of AAReachability. If we have AAReachability::isAssumedReachable(Instruction &From, Instruction &To), AAIsDead::isAssumedDead(Instruction &I) is equivalent to `!AAReachability::isAssumedReachable(EntryPointOfFunction, I).So you should probably extend AAIsDead.

Maybe you can refer must-be-executed-context which handles the similar property.

I agree and this is certainly an option. At the end of the day, it should not matter if we keep it separate or merge them, we can always use on from the other.
Let's get the class skeleton in place with the right methods etc and we take it step by step from there.

pgode updated this revision to Diff 229566.Nov 15 2019, 8:49 AM

Thank you @jdoerfert , @sstefan1 and @uenoku for your helpful comments.
Submitting updated patch with corrections.

pgode marked 4 inline comments as done.Nov 15 2019, 8:52 AM

Thanks for the quick update.

You can (for now) remove the changes that are not in Attributor.{h,cpp} as they all relate to an IR attribute (which we might want to have but that is a different beast).
Other than that there is the query interface that needs to change to provide the positions the user is interested in (see below).

Once these two changes are done we can merge the skeleton code in.

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

I would replace the two methods above by:

AAReachability::isAssumedReachable(const IRPosition &From, const IRPosition &To)
AAReachability::isKnownReachable(const IRPosition &From, const IRPosition &To)

with their implementation (initially always return true) in AAReachabilityImpl or AAReachabilityFunction.

The idea is that users provide the two positions they are interested in and the class determines (and caches) reachability.

llvm/lib/Transforms/IPO/Attributor.cpp
2074

If you keep two classes only one needs the trackStatistics

2082

For functions we use:
STATS_DECLTRACK_FN_ATTR

pgode updated this revision to Diff 229591.Nov 15 2019, 10:38 AM

@jdoerfert Thank you suggesting the corrections.
Updating the corrected patch.

I think, function getAsStr() should be returning 'from' and 'to' position, but for that we need to store the From and To.
For now, I am returning 'reachable' by default.

pgode marked 3 inline comments as done.Nov 15 2019, 10:40 AM

@jdoerfert Thank you suggesting the corrections.
Updating the corrected patch.

I think you still need to remove the other files from the patch, then it will be good to go in.
I'll accept the patch ones it is updated.

Btw., do you have commit access?

I think, function getAsStr() should be returning 'from' and 'to' position, but for that we need to store the From and To.
For now, I am returning 'reachable' by default.

That is fine for now. We do not have a concept of "attribute for pairs". Instead AAReachability is more like a container that computes and caches queries. You can return the number of cached queries in the getAsStr(), similar to what AAHeapToStack does.


Next step is to use AANoReachable at the capture todo we talked about. Even if it is captured, we can iterate over all uses of the pointer, skip the one in the call site we are looking at, and if the call site is not reachable from any of the uses, we can allow noalias still. Does that make sense?

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

Nit Please update the comments of the functions.

pgode updated this revision to Diff 229708.Nov 17 2019, 2:59 AM

Thanks @jdoerfert for the helpful corrections. I have removed the files. (I should have removed them in the last patch.)
I will start working on the next part.

pgode updated this revision to Diff 229712.EditedNov 17 2019, 3:22 AM

Updated the function comments.

pgode marked an inline comment as done.Nov 17 2019, 3:23 AM
pgode added a comment.Nov 17 2019, 6:25 AM

Btw., do you have commit access?

Yes, I have commit access. I had requested Tom Stellard for it.

pgode retitled this revision from [WIP][NOT FOR COMMIT][Attributor] AAReachability Attribute to [WIP][Attributor] AAReachability Attribute.Nov 19 2019, 9:07 PM

It seems a bit weird for me to use IRPosition as a program point. Therefore, I think it is better to use Instruction instead of IRPosition. So the interface will be

bool isAssumedReachable(const Instruction &From, const Instruction &To)

What do you think?

llvm/lib/Transforms/IPO/Attributor.cpp
2066

nit: You can call indicatePessimisticFixpoint directly.

pgode added a comment.Nov 20 2019, 9:19 AM

It seems a bit weird for me to use IRPosition as a program point. Therefore, I think it is better to use Instruction instead of IRPosition. So the interface will be

bool isAssumedReachable(const Instruction &From, const Instruction &To)

What do you think?

Thanks for reviewing. I think the IRPosition gives better information than Instruction, in the reachability context. I observe that IRPosition is created for Function, Argument, Callsite etc.
Nevertheless, if client tries to use Instruction instead of IRPosition then we need to overload.

pgode updated this revision to Diff 230279.Nov 20 2019, 9:20 AM

Thanks for highlighting the nit. Corrected it.

pgode marked an inline comment as done.Nov 20 2019, 9:21 AM
sstefan1 added inline comments.Nov 20 2019, 11:36 AM
llvm/include/llvm/Transforms/IPO/Attributor.h
1690

I kind of agree with @uenoku here. If you still want to stick with IRPosition, then you might want to change these comments.

pgode marked an inline comment as done.Nov 20 2019, 10:40 PM
pgode added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
1690

I looked at isKnownDead(Instruction*) and isAssumedDead(Instruction *) and I think we are expecting something similar.
I will make the changes and submit the updated patch.
Thanks for clarifying.

pgode updated this revision to Diff 230372.Nov 20 2019, 10:50 PM

Updated the patch as per review comments.

pgode marked an inline comment as done.Nov 20 2019, 10:51 PM

This is LGTM from me now, but lets wait for Johaness as well.

This revision is now accepted and ready to land.Nov 21 2019, 9:29 AM

We can merge this and then add a user as we talked about.

pgode set the repository for this revision to rG LLVM Github Monorepo.Nov 22 2019, 8:51 AM
pgode closed this revision.Nov 26 2019, 1:35 AM