Page MenuHomePhabricator

[BFI] Use CallbackVH to notify BFI about deletion of basic blocks
ClosedPublic

Authored by DaniilSuchkov on Feb 28 2020, 4:27 AM.

Details

Summary

With AssertingVHs instead of bare pointers in BlockFrequencyInfoImpl::Nodes (but without CallbackVHs) ~1/36 of all tests ran by make check fail (in my setup it's 1042 out of 36257). It means that there are users of BFI that delete basic blocks while keeping BFI. Some of those transformations add new basic blocks, so if a new basic block happens to be allocated at address where an already deleted block was and we don't explicitly set block frequency for that new block, BFI will report some non-default frequency for the block even though frequency for the block was never set. Inliner is an example of a transformation that adds and removes BBs while querying and updating BFI, however I can't provide a test case that would show non-deterministic inlining caused by this issue.

Diff Detail

Event Timeline

DaniilSuchkov created this revision.Feb 28 2020, 4:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 28 2020, 4:27 AM

Just a quick comment, that IMO this is a great patch to have, even without an actual test showing the non-determinism.
We've seen issues like this with BFI between passes, and I tried to prevent using a cached BFI due to precisely the problem you describe.
I did not however handle the situation of BFI being invalidated by a pass and used by the same pass.
I'm sorry I don't have a good suggestion for your const_cast question.

The changes lgtm, but I'd let the other reviewers chime in too.

Alternatively I think it would be reasonable to expect the passes claiming to preserve BFI to notify BFI about deleted/added blocks, like we do for many other analysis. Do you have any idea of how much effort that would take?

Can you make BlockKeyT to be AssertingVH<const BasicBlock> to avoid the const castings?

Can you make BlockKeyT to be AssertingVH<const BasicBlock> to avoid the const castings?

Sadly, ValueHandles don't work with non-const pointers.

Do you mean it does not work well for const pointers? There are existing uses of AssertingVH<const BasicBlock> or AssertingVH<const Value>?

DaniilSuchkov added a comment.EditedFeb 28 2020, 9:01 PM

Alternatively I think it would be reasonable to expect the passes claiming to preserve BFI to notify BFI about deleted/added blocks, like we do for many other analysis. Do you have any idea of how much effort that would take?

Yeah, I considered this option but I don't think it's any better.
First, even with that approach we'll still need AssertingVHs in order to verify that we didn't miss any updates, and given that most of ugly const_casts are required by AssertingVH, it's not much of an improvement.
UPD: First, given that const_casts aren't an issue, I don't see any benefits of manual updates.

Second, CallbackVHs "automatically" notify BFI about changes, so they solve this part of the issue once and for all, while with manual notifications it'll be a classic whack-a-mole kind of effort, we'll be fixing AssertingVH's crashes on regular basis (maybe not too often though).
Third, it requires considerable amount of pretty intrusive changes, even more than providing BFI with non-const Functions/BasicBlocks does.

Do you mean it does not work well for const pointers? There are existing uses of AssertingVH<const BasicBlock> or AssertingVH<const Value>?

Actually you're right, thank you!
It didn't cross my mind that someone could've already included const_casts into AssertingVH itself, so that unlike other ValueHandles it accepts const pointers.

DaniilSuchkov added a comment.EditedFeb 28 2020, 9:18 PM

One thing I don't understand is why three out of four kinds of VHs perform the const_cast, not the ValueHandleBase. I think it's time to change that (and by doing so, allow CallbackVH accept const pointers too).
Given that three out of four VH kinds already perform const_cast inside, I think it makes sense to add one to CallbackVH too.

DaniilSuchkov planned changes to this revision.Feb 28 2020, 10:01 PM
DaniilSuchkov edited the summary of this revision. (Show Details)

Got rid of all const_casts except one, which was moved into CallbackVH's constructor.

This looks good, but it does have implications on memory consumption for BFI. To avoid that, gate the data structure change on #ifndef NDEBUG.

This looks good, but it does have implications on memory consumption for BFI. To avoid that, gate the data structure change on #ifndef NDEBUG.

I understand that, but I don't think we can do anything about it. You see, AssertingVH already gates itself in a way that turns it into a pointer wrapper in Release configuration and BFICallbackVH is always required for correctness, since it updates BFI.
Or am I missing something?

The value field of the NodesMap now becomes a pair unconditionally -- which is unnecessary for nonAsserting Build.

You mean we don't need to update BFI in non-asserting mode? It's not just for verification, it's required for correctness.

I think we should explicitly fix the real problems that new blocks are not updated frequency information instead of just letting them get a known default value. Doing it later can make it harder to find those problems, right?

I think we should explicitly fix the real problems that new blocks are not updated frequency information instead of just letting them get a known default value. Doing it later can make it harder to find those problems, right?

Cases when we don't properly set frequencies are inefficiencies, which are unfortunate, but they aren't critical, to catch them there is already a CheckBFIUnknownBlockQueries option. This patch, on the other hand, not about mere inefficiencies, it's about non-deterministic behavior of compiler, which is a pretty nasty thing, I find even possibility of this happening a real problem. What I here propose would protect us from such issues and it won't cover cases CheckBFIUnknownBlockQueries is made to detect, so it won't make finding such cases any harder.

Actually, this change will even help CheckBFIUnknownBlockQueries: since every missed update will result in a missing NodesMap entry, without exclusion of cases when new BB happens to be in the same address where some old BB was.

davidxl accepted this revision.Mar 4 2020, 9:27 AM

lgtm

This revision is now accepted and ready to land.Mar 4 2020, 9:27 AM
This revision was automatically updated to reflect the committed changes.

Sorry for not noticing this patch sooner. I think this helps bring some more sanity in the BFI staleness issue. LGTM.