This is an archive of the discontinued LLVM Phabricator instance.

[AAPointerInfo] refactor how offsets and Access objects are tracked
ClosedPublic

Authored by sameerds on Oct 22 2022, 6:15 AM.

Details

Summary

AAPointerInfo now maintains a list of all Access objects that it owns, along
with the following maps:

  • OffsetBins: OffsetAndSize -> { Access }
  • InstTupleMap: RemoteI x LocalI -> Access

A RemoteI is any instruction that accesses memory. RemoteI is different from
LocalI if and only if LocalI is a call; then RemoteI is some instruction in the
callgraph starting from LocalI.

Motivation: When AAPointerInfo recomputes the offset for an instruction, it sets
the value to Unknown if the new offset is not the same as the old offset. The
instruction must now be moved from its current bin to the bin corresponding to
the new offset. This happens for example, when:

  • A PHINode has operands that result in different offsets.
  • The same remote inst is reachable from the same local inst via different paths in the callgraph:
  A (local inst)
  |
  B
 / \
C1  C2
 \ /
  D (remote inst)

This fixes a bug where a store is incorrectly eliminated in a lit test.

Diff Detail

Unit TestsFailed

Event Timeline

sameerds created this revision.Oct 22 2022, 6:15 AM
Herald added a project: Restricted Project. · View Herald TranscriptOct 22 2022, 6:15 AM
sameerds requested review of this revision.Oct 22 2022, 6:15 AM
Herald added a reviewer: sstefan1. · View Herald Transcript
Herald added a project: Restricted Project. · View Herald Transcript

Can you point out the test that this fixes? Maybe a standalone reproducer would be good too. I read only the commit message and I'm not sure I understand the problem.

Can you point out the test that this fixes? Maybe a standalone reproducer would be good too. I read only the commit message and I'm not sure I understand the problem.

I did leave comments on the Phab page for that other commit ... https://reviews.llvm.org/rGad98ef8be409 . But I guess it's incorrect to say that the other commit introduced the bug. It's a latent bug that was exposed by tests like phi_no_store_2.

Essentially, the PHI %p in phi_no_store_2 is visited twice. The first time, it is assigned the offset 0, and the second time it is set to unknown. This results in the following bins being printed in the debug log:

Accesses by bin after update:
[0-1] : 1

  • 10 - store i8 1, i8* %p, align 1
    • c: i8 1

[-2--1] : 1

  • 10 - store i8 1, i8* %p, align 1
    • c: i8 1

Then forallInterferingAccesses comes along and sees only the first bin with the assumption that one access can only be in one bin. Hence it concludes that the store does not have a potential copy in load %l21, and hence eliminates the store. This is incorrect, since the load is still there and it should see the value written by that store. The store can be eliminated only by recognizing the potential copy and first propagating the value to the load.

The root cause is that if an access is already in a bin, and its offset is updated to unknown, then the access needs to first be removed from its current bin. This change ensures this behaviour by improving the plumbing of how accesses are tracked in bin, so that clients don't have to worry about these things.

The root cause is that if an access is already in a bin, and its offset is updated to unknown, then the access needs to first be removed from its current bin. This change ensures this behaviour by improving the plumbing of how accesses are tracked in bin, so that clients don't have to worry about these things.

I see. The error description makes sense. Can we split this into a fix and the rewrite though? The fix would be to remove the entry from the bin as soon as the offset changes (which can only become invalid I assume). The rewrite gets rid of the bins and keeps lists of instructions per access, right? There is a change in one of the tests that I think is caused by the rewrite and should not be. We also need tests to capture the benefits of the rewrite then. Also, are the bins itself bad or simply bad that we have on offset per access?

llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll
746

Why do we miss out on these propagations? There are no PHIs involved, right? Something is amiss.

sameerds updated this revision to Diff 470424.Oct 25 2022, 2:33 AM

The refactor now accounts for remote/local instructions. This restores all the other affected lit tests.

sameerds edited the summary of this revision. (Show Details)Oct 25 2022, 2:37 AM
sameerds edited the summary of this revision. (Show Details)

The root cause is that if an access is already in a bin, and its offset is updated to unknown, then the access needs to first be removed from its current bin. This change ensures this behaviour by improving the plumbing of how accesses are tracked in bin, so that clients don't have to worry about these things.

I see. The error description makes sense. Can we split this into a fix and the rewrite though? The fix would be to remove the entry from the bin as soon as the offset changes (which can only become invalid I assume). The rewrite gets rid of the bins and keeps lists of instructions per access, right? There is a change in one of the tests that I think is caused by the rewrite and should not be. We also need tests to capture the benefits of the rewrite then. Also, are the bins itself bad or simply bad that we have on offset per access?

It's the one-offset-per-access that causes loss of information. I've updated the change description to talk more about this. Hope that clarifies the situation! Also fixed the side effect on other places. I had failed to distinguish between multiple local insts pointing to the same remote inst.

sameerds added inline comments.Oct 25 2022, 2:43 AM
llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll
746

When I don't distinguish between calls that reach the same remote inst, that remote inst is conservatively treated as unknown. I thought it would be okay to "improve" this later, but then realized that the solution is very relevant to the refactoring. The new change does it right, and this side-effect disappears.

Test impact looks good now. I have two issues with the patch but we can resolve both. One is the update of the OAS which needs to also trigger an update of the access kind and value, e.g., if we loose precise information we cannot keep the MUST kind and value around. Second, we should probably avoid nested DenseMaps, I tried to propose some alternatives.

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

At this point we need to signal the access it is a May not Must access anymore if the offset or size changed from something that was not unassigned, right? We also need to give up on the value I suppose.

273

Not super happy about first and second. Should we wrap it in setOffset setSize ?

5099

Documentation, for all of these. See the surrounding code.

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

We could use Access* here to get stable addresses.

835

I'm not sure nested DenseMaps are a good idea. I think it usually ends up using way too much memory.
Let's try to use an encoding without it.

878

This looks like we could map instructions to a list of OAS instead. Or directly the Access*?

896

Also here, if we have RemoteI -> list<Access*> we should be fine, no?

sameerds added inline comments.Oct 26 2022, 9:57 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
832

We could, but then we have to worry about memory allocation on the stack. In fact, I am still wondering about the copy constructor for PointerInfo::State. It seems to make a shallow copy of AccessBins. Doesn't that result in a double free?

If we keep a list of Access*, instead of a list of Access, it looks like more code with no clear benefit. TBH, I am a big fan of "never use new". For now, the unsigned index into the list of Access is sufficient for its very local use. If it needs to be exposed to clients, maybe could wrap it in a custom iterator instead of exposing stable pointers?

Of course I am open to using a list of Access* if you think that is beneficial.

sameerds added inline comments.Oct 26 2022, 9:59 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
832

s/stack/heap

jdoerfert added inline comments.Oct 26 2022, 10:56 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
832

"never use new" is not a good argument. For one, we have a bump allocator for the Attributor so the "cost" argument doesn't apply at all. Second, even if we don't use the bump allocator, new is not inherently costly. DenseMaps of DenseMaps (or similar nested structures) can hover grow fast. They also will inherently use new, so all you do here is to hide the heap allocations and cause more of them.

We could, but then we have to worry about memory allocation on the stack. In fact, I am still wondering about the copy constructor for PointerInfo::State. It seems to make a shallow copy of AccessBins. Doesn't that result in a double free?

As far as I can tell, PpinterInfo::State did not have a copy constructor. The move constructor did not cause double free problems as it cleared the other access bin after moving the content. If the new version requires adequate handling for copy/move constructor, that should be easy to add, no?

Of course I am open to using a list of Access* if you think that is beneficial.

As I said, I had mixed experience with nested maps. This is not exactly the same case but the first one I could find: https://reviews.llvm.org/rG14cb0bdf2b6ca0b7befbb07fe9f73dad5786f59b

sameerds added inline comments.Oct 26 2022, 6:51 PM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
832

Right, there is no copy constructor in state, but there is a copy assignment operator which does a shallow copy. I guess it didn't matter because it only got used in places where the state is empty.

We don't seem to be talking about the same thing here. I totally agree with not using DenseMap, and I am working on using a list instead. My comment was a reply to this granparent comment:

We could use Access* here to get stable addresses.

Where in this specific case do you see the need for stable addresses?

To me, stable addresses means something like this:

SmallVector<Access*> AccessList

auto *Acc = new Access;
AccessList.push_back(Acc)

Which means now I have to remember to destroy those Access objects later and also worry about deep copies.

If the new version requires adequate handling for copy/move constructor, that should be easy to add, no?

Memory management may be easy, but it is also easily missed. I am quite the fan of coding practices that simply avoid the hassle. For example, I see a commit in git history where the destruction on AccessBins was missed.

I would much prefer the following:

SmallVector<Access> AccessList;
AccessList.emplace_back({....});

Here, AccessList manages the allocation of the Access object and I don't have to worry about destruction and copying.

This is what "never use new" means. To repeat, it has nothing to do with the cost of DenseMap. It also has nothing to do with custom Allocators. The point is that application programmers should refrain from using the new operator, and instead rely on containers to take care of the allocation. The simplest such container is unique_ptr, for example. All containers take Allocators as template arguments, so the question of which Allocator to use is completely orthogonal. "never use new" is a code hygiene concept, not a performance concept.

So do you really see a reason to have stable pointers to Access objects? Otherwise I would much prefer keeping them directly in a SmallVector.

jdoerfert added inline comments.Oct 26 2022, 10:06 PM
llvm/include/llvm/Transforms/IPO/Attributor.h
271

^ this one we need to handle as well.

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

I'm happy with alternatives. Stable addresses would have allowed to do avoid all the indices and double lookups, though, that is not by itself a problem. I thought below it would be easier if we could store Access*, if you think we don't need to, that's generally OK.

sameerds updated this revision to Diff 471175.Oct 27 2022, 8:39 AM
sameerds edited the summary of this revision. (Show Details)

Addressed most of the review comments. Replaced the nested DenseMap with a list.

This diff includes https://reviews.llvm.org/D136745 (OffsetAndSize without the
std::pair) merged into it, so that I don't have to rebase the current diff.
Those changes will get filtered out when submitting to tip of main.

sameerds added inline comments.Oct 27 2022, 8:47 AM
llvm/lib/Transforms/IPO/AttributorAttributes.cpp
878

Should we do this in a separate change? Latest diff addresses pretty much all the other comments.

tschuett added inline comments.
llvm/include/llvm/Transforms/IPO/Attributor.h
223

Would a class with public and private make this safer to use?

jdoerfert accepted this revision.Oct 27 2022, 11:25 AM

I think this looks good. Fixes an error and I hope doesn't introduce new ones.
Could you, in a follow up, add some tests for the multi access per instruction support you introduced now?

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

We use it as a POD, basically a pair with helper functions and nicer names. I doubt there is much value in private members and public setters.

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

This doesn't need addressing per se. Let's keep it as is for now.

This revision is now accepted and ready to land.Oct 27 2022, 11:25 AM
sameerds updated this revision to Diff 471491.Oct 28 2022, 4:17 AM
  • Rebased to tip of main.
  • Added test for callgraph from the description: a leaf instruction may have Unknown offset if different offsets reach along different paths in the callgraph.
NOTE: I intend to commit this on Sunday night, IST.
sameerds added inline comments.Oct 28 2022, 4:21 AM
llvm/test/Transforms/Attributor/value-simplify-pointer-info.ll
1707

Oops! This was not supposed to happen. Checking.

sameerds updated this revision to Diff 472069.Oct 31 2022, 10:47 AM

rebased to include a recent fix; added lit tests

sameerds reopened this revision.Nov 14 2022, 2:48 PM
This revision is now accepted and ready to land.Nov 14 2022, 2:48 PM
sameerds updated this revision to Diff 475283.Nov 14 2022, 2:48 PM

Fixes https://github.com/llvm/llvm-project/issues/58774

When merging to Access objects, don't call reset() on the content, but it needs
to be set to nullptr instead. The latter means that the content was determined
to be unknown. Added an assertion to getWrittenValue() to which would have
caught this more quickly.

ye-luo accepted this revision.Nov 14 2022, 10:30 PM

Pass tests on my side. Thanks

This revision was landed with ongoing or failed builds.Nov 15 2022, 5:26 AM
This revision was automatically updated to reflect the committed changes.