This is an archive of the discontinued LLVM Phabricator instance.

[Attributor] Introduce AAPointerInfo
ClosedPublic

Authored by jdoerfert on Jun 16 2021, 6:53 PM.

Details

Summary

This patch introduces AAPointerInfo which tracks the uses of a pointer
and places them in "bins" based on their offset from the base and access
size.

As with other AAs, any pointer can be tracked but it is up to the user
to make sense of the results. The user in this patch is AAValueSimplify
and AAPotentialValues which both utilize AAPointerInfo to determine the
value of a load. For now, this is restricted to loads of allocas and
internal globals. Through the use of AAPointerInfo and the "bins" we can
track struct members separately. The users also know that storing only
zeros (at unknown indices) will result in loading only 0 (from unknown
indices). Other than that, the users are flow and context insensitive
(for now).

To deal with the "bins" more easily, AAPointerInfo provides a
forallInterfearingAccesses that applies a callback on all accesses
that might interfere with a given load or store.

Diff Detail

Event Timeline

jdoerfert created this revision.Jun 16 2021, 6:53 PM
jdoerfert requested review of this revision.Jun 16 2021, 6:53 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 16 2021, 6:53 PM
Herald added a subscriber: bbn. · View Herald Transcript
ormris removed a subscriber: ormris.Jun 23 2021, 9:45 AM
nikic added a subscriber: nikic.Jul 5 2021, 11:55 AM
nikic added inline comments.
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1147

Access to pointer element type. Is this supposed to use Ty instead?

jdoerfert added inline comments.Jul 8 2021, 4:55 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1147

Good catch. Yes, I added Ty later and did not modify this use.

jdoerfert updated this revision to Diff 357828.Jul 11 2021, 7:17 PM
jdoerfert marked an inline comment as done.

Rebase

kuter added inline comments.Jul 13 2021, 10:34 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1012–1013

This function is going to be called from the updateImpl method of a attribute.
Maybe it would make sense to make it a little faster at least in some common cases or maybe some caching ?

1034

Maybe it would be worth handling the case where the access is always aligned ?
like int array[100];

Maybe we can have a flag inside the state that tells us that all the load/store instructions that we looked at have aligned access.
Then we can just use the offset (maybe through a hashmap lookup) to find any interfering access.

Or maybe if we have sorted set like std::set (sorted by offset). We can limit where we end our scan.
We would only scan [0, OAS.getOffset() + OAS.getSize()].

Or even better if we have maximum access size for all access
We can just scan just scan the range [OAS.getOffset() - MaxSize, OAS.getOffset() + OAS.getSize()].

1102

Maybe we can use addAccess here ?

1203

Maybe an early return here would be easier to read ?

kuter added inline comments.Jul 13 2021, 11:01 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
835–838
jdoerfert updated this revision to Diff 358459.Jul 13 2021, 5:01 PM
jdoerfert marked 3 inline comments as done.

Address comments, track original access instruction together with local one,
handle byval properly, improve debug messages

llvm/lib/Transforms/IPO/AttributorAttributes.cpp
835–838

simplified :)

1012–1013

Can we postpone this as it will be more meaningful as we start using AAPointerInfo. Then we can actually measure any "optimization" here properly.

1034

The bins need a lot more logic for this but I can see that it can help. We basically would want to store what the modulo is between offset and base. That would even allow us to handle non-static offsets much better if we know they come from a specific multiple, that is gep .. %i. That said, I'd prefer to postpone such optimizations for later.

1102

Good catch. Did that :)

1203

will do.

kuter accepted this revision.Jul 14 2021, 3:55 PM

LGTM as far as I can see. One small nit.

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

NIT
This depends on the argument position places of MemIntrinsic right.
the first one is always the destination and the second one is always the source ?
It's kinda hard to see what's going on here. Maybe some documentation would be great.

This revision is now accepted and ready to land.Jul 14 2021, 3:55 PM
This revision was landed with ongoing or failed builds.Jul 19 2021, 8:50 PM
This revision was automatically updated to reflect the committed changes.
RKSimon added inline comments.
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1338

@jdoerfert Static analysis is warning about an uninitialised variable - should this be ChangeStatus::UNCHANGED?

https://llvm.org/reports/scan-build/report-AttributorAttributes.cpp-handleAccess-10-6bf086.html#EndPath

jdoerfert added inline comments.Feb 24 2022, 2:45 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1338

Yes, will fix.

ayrivera added inline comments.
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1101

Hi,

I attached a example that produces a segmentation fault in line 1100. The example is pretty simple, a function foo that allocates a space which is a structure type, the argument of foo is written in one field, then calls bar, which writes in another field of the allocated space.

I'm not familiar with this optimization, but will try to explain the best I can. Tracing the issue I found that getAAFor is called in line 1242 from updateImpl (recent version of the file should be around 1495), the creation of an AA calls a function that updates the information (updateImpl), which calls translateAndAddCalleeState from line 1363 (1628 in the recent file). The condition in 1101 happens for one of the entries in It.second, so addChange didn't run for a particular access.

Once the AA is created for line 1242 (1495), the function translateAndAddCalleeState runs again in line 1245 (1498). But now we have states (It) where the second entry in the pair is a null pointer. This produces a segmentation fault when traversing the loop in line 1100. The reason seems to be because addChange skipped an access during the first call of translateAndAddCalleeState then there is no information for the access.

You can run the test case with the following command:

opt simple_attributor.ll -S

Herald added a project: Restricted Project. · View Herald TranscriptApr 26 2022, 12:37 PM
sameerds added inline comments.
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1203

Old change, but when is this condition false? Just above this, there is an early return if any index is not a constant.

jdoerfert added inline comments.Aug 26 2022, 8:33 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
1203

You are right. Feel free to remove this and use cast<..>