Page MenuHomePhabricator

[JumpThreading] Prevent dangling pointer problems in BranchProbabilityInfo
ClosedPublic

Authored by igor-laevsky on Jun 3 2016, 5:19 AM.

Details

Summary

We should update results of the BranchProbabilityInfo after removing block in JumpThreading. Otherwise we will get dangling pointer inside BranchProbabilityInfo cache. Which can lead to various problems. Note that there is similar issue for the BlockFrequencyInfo but it's a subject for separate change.

Diff Detail

Repository
rL LLVM

Event Timeline

igor-laevsky retitled this revision from to [JumpThreading] Prevent dangling pointer problems in BranchProbabilityInfo.
igor-laevsky updated this object.
igor-laevsky added reviewers: sanjoy, reames, hfinkel.
igor-laevsky added a subscriber: llvm-commits.
sanjoy requested changes to this revision.Jun 6 2016, 2:36 PM
sanjoy edited edge metadata.
sanjoy added inline comments.
include/llvm/Analysis/BranchProbabilityInfo.h
120 ↗(On Diff #59535)

New code should not use \brief, since we have autobrief enabled for our doxygen.

include/llvm/Transforms/Utils/Local.h
302 ↗(On Diff #59535)

Nit: document the new parameter (and maybe the \p LVI as well)?

lib/Analysis/BranchProbabilityInfo.cpp
643 ↗(On Diff #59535)

Why do you need to do a linear search here? Isn't Probs a DenseMap<Edge, BranchProbability>? IOW, why not:

for (int i = 0; i < BB->numSuccessors(); i++)
  Probs.erase({BB, i});
unittests/Analysis/BlockFrequencyInfoTest.cpp
58 ↗(On Diff #59535)

Should this be called releaseBPI?

59 ↗(On Diff #59535)

Nit: spelling. Also add a period after the sentence.

This revision now requires changes to proceed.Jun 6 2016, 2:36 PM
igor-laevsky edited edge metadata.
igor-laevsky marked 3 inline comments as done.
igor-laevsky added inline comments.
lib/Analysis/BranchProbabilityInfo.cpp
643 ↗(On Diff #59535)

Problem with this approach is that contents of the BB could have been changed since it was first recorded. If conditional terminator was replaced with unconditional jump, we may leave some BB references hanging in the map.

unittests/Analysis/BlockFrequencyInfoTest.cpp
58 ↗(On Diff #59535)

This is to be symmetric with buildBFI. Besides I suspect that BFI has the same issue and we will need to add "BFI->releaseMemory()" here.

sanjoy added inline comments.
lib/Analysis/BranchProbabilityInfo.cpp
644 ↗(On Diff #59894)

I see, but I'm not sure that this won't be a compile time regression. Maybe @dnovillo or @congh (names that show up on git-blame) will have an idea?

unittests/Analysis/BlockFrequencyInfoTest.cpp
58 ↗(On Diff #59894)

In that case, let's call it destroyBFI?

igor-laevsky marked an inline comment as done.
igor-laevsky added inline comments.
lib/Analysis/BranchProbabilityInfo.cpp
644 ↗(On Diff #59894)

Yes, compile time might be an issue here. It would be possible to avoid linear search by changing data type of the branch probability storage from:

DenseMap<pair<BasicBlock*, unsigned>, BranchProbability> Probs;

into:

DenseMap<BasicBlock*, IndexedMap<unsigned>> Probs;

However it would be fairly large change and I don't wont to mix it with this one. Does it sound reasonable if I will submit this version first and then follow up with a data type change?

sanjoy added inline comments.Jun 9 2016, 12:15 PM
lib/Analysis/BranchProbabilityInfo.cpp
644 ↗(On Diff #59894)

Right, other than that issue, this lgtm; but I'd prefer waiting till someone more familiar with this code has had time to chime in about the potential compile time problems.

dnovillo requested changes to this revision.Jun 9 2016, 3:45 PM
dnovillo edited edge metadata.

I agree with Igor's analysis. Let's first fix the correctness issue. Any compile-time problems that show up, can be fixed with a data structure change later. Igor, do you have any test cases that show the problem? Without a test case, it's harder to justify this change.

Thanks. Diego.

This revision now requires changes to proceed.Jun 9 2016, 3:45 PM
igor-laevsky edited edge metadata.

I agree with Igor's analysis. Let's first fix the correctness issue. Any compile-time problems that show up, can be fixed with a data structure change later. Igor, do you have any test cases that show the problem? Without a test case, it's harder to justify this change.

Thanks. Diego.

Hi,

Noticeable effect of this failure appears only if new BasicBlock was allocated at the same place as the removed one. It will depend on many things which are impossible to guarantee for a single test case. I've added test which will fail AssertingVH in case if BasicBlock was not removed. Should be enough to guarantee that no one forgets to call eraseBlock in the future.

davidxl added inline comments.Jun 10 2016, 10:41 AM
lib/Transforms/Scalar/JumpThreading.cpp
238 ↗(On Diff #60360)

maybe just check nullness of BPI

268 ↗(On Diff #60360)

Same here.

753 ↗(On Diff #60360)

This pattern repeats many times, it is better to create a small wrapper member function to erase BB.

test/Transforms/JumpThreading/dangling-pointers-in-bpi.ll
1 ↗(On Diff #60360)

What does this test do? THere is no check string?

igor-laevsky edited edge metadata.
igor-laevsky marked 4 inline comments as done.
davidxl added inline comments.Jun 14 2016, 10:10 AM
lib/Transforms/Scalar/JumpThreading.cpp
1955 ↗(On Diff #60673)

nit: ForgetBlockAnalysisResults --> dropBlockAnalysisResults(..)

test/Transforms/JumpThreading/dangling-pointers-in-bpi.ll
1 ↗(On Diff #60673)

should 2>&1 be needed ?

igor-laevsky marked 2 inline comments as done.
davidxl accepted this revision.Jun 15 2016, 1:22 PM
davidxl added a reviewer: davidxl.

lgtm

dnovillo accepted this revision.Jun 15 2016, 1:33 PM
dnovillo edited edge metadata.

LGTM

Thanks for the test case.

This revision was automatically updated to reflect the committed changes.

This change was reverted due to the failing AssertingVH on some of the buildbots. Looked very much like a problem described in llvm-dev thread "Should analyses be able to hold AssertingVH to IR? (related to PR28400)". I bypassed this issue by using CallbackVH instead of AssertingVH and resubmitted (r275563).