This is an archive of the discontinued LLVM Phabricator instance.

[NewGVN] Decrement UseCount only if SSA copy has an use
AbandonedPublic

Authored by vladimirradosavljevic on Aug 7 2023, 3:14 AM.

Details

Reviewers
fhahn
Summary

If SSA copy is not in the UseCounts map, don't insert it because it should be in the ProbablyDead and map can grow and lead to a dangling reference to the LeaderUseCount.

Diff Detail

Event Timeline

vladimirradosavljevic requested review of this revision.Aug 7 2023, 3:14 AM
Herald added a project: Restricted Project. · View Herald TranscriptAug 7 2023, 3:14 AM

Tests?

Adding a small reproducer for this would be tricky, as we would need to hit the case where UseCounts map grows on the following line:

unsigned &IIUseCount = UseCounts[II];

This problem was caught by the sanitizers and here is the small trace:

READ of size 4 at 0x61d0000db3d8 thread T0
#0 0x7fcf39604358 in eliminateInstructions llvm/lib/Transforms/Scalar/NewGVN.cpp:4123

freed by thread T0 here:
#8 0x7fcf396040f0 in eliminateInstructions llvm/lib/Transforms/Scalar/NewGVN.cpp:4119

previously allocated by thread T0 here:
#9 0x7fcf395e967c in convertClassToDFSOrdered llvm/lib/Transforms/Scalar/NewGVN.cpp:3688

Here is what happens:

auto &LeaderUseCount = UseCounts[DominatingLeader]; <--- Taking reference
....
unsigned &IIUseCount = UseCounts[II]; <-- DenseMap grows under the hood
....
++LeaderUseCount; <--- Accessing freed memory

Managed to create a test case that reproduces this issue using the llvm-reduce tool. Please take a look.

kmitropoulou added inline comments.Aug 18 2023, 2:19 PM
llvm/lib/Transforms/Scalar/NewGVN.cpp
4119

The test case does not crash in my workspace. Anyway, I think the problem is here. If II is not in the UseCounts map, then it just adds it and it returns zero. Will the following change solve the problem?

if (isSSACopy) {

auto It = UseCounts.find(II);
if (It != UseCounts.end()) {
    unsigned &IIUseCount = It->second;
    if (--IIUseCount == 0)
         ProbablyDead.insert(II);
}

}

llvm/lib/Transforms/Scalar/NewGVN.cpp
4119

Could you please try to run it with valgrind/sanitizers, because it happens occasionally and this is why it is such a dangerous bug.
Yes, proposed solution fixes the problem. Please note that I'm not familiar with the NewGVN pass, but if II is not in UseCounts map, should we also insert it into ProbablyDead?

kmitropoulou added inline comments.Aug 22 2023, 7:04 PM
llvm/lib/Transforms/Scalar/NewGVN.cpp
4119

I am not expert on this part of NewGVN, but I think that if II is in UseCounts map, then II should be already in ProbablyDead. This logic is towards the bottom of convertClassToDFSOrdered() .

Regarding the test, if it crashes with the sanitizer, then it is OK. But, the test is way too big. Please make it smaller.

Since NewGVN is not enabled by default, we should run the tests from test-suite with NewGVN enabled. Please be aware that there are some tests that are failing due to NewGVN.

kmitropoulou added inline comments.Aug 23 2023, 9:56 AM
llvm/lib/Transforms/Scalar/NewGVN.cpp
4119

I am sorry I meant:

I think that if II is not in UseCounts map, then II should be already in ProbablyDead.

vladimirradosavljevic retitled this revision from [NewGVN] Fix an use after free when updating use count to [NewGVN] Don't always update use counts for SSA copies.
vladimirradosavljevic edited the summary of this revision. (Show Details)

Comments addressed.

llvm/lib/Transforms/Scalar/NewGVN.cpp
4119

Thanks for the clarification! I submitted the new patch with your suggestion. Regarding the test case, it is the smallest reproducer I managed to create, and I used llvm-reduce test to do so.

LGTM! Please change the title to something like:
Decrement UseCount only if SSA copy has a use.

vladimirradosavljevic retitled this revision from [NewGVN] Don't always update use counts for SSA copies to [NewGVN] Decrement UseCount only if SSA copy has an use.Sep 8 2023, 1:27 AM

LGTM! Please change the title to something like:
Decrement UseCount only if SSA copy has a use.

@kmitropoulou Done!

Thanks for the review! Could you please commit this on my behalf?
E-Mail: Vladimir Radosavljevic <vr@matterlabs.dev>

I will do it :)

kmitropoulou added a comment.EditedSep 11 2023, 6:12 PM

The patch was merged in:

commit 3a318382baceacc94992f0239636d6d243a57565

Can you please close the ticket?