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

[vladimirradosavljevic]

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.

[kmitropoulou]

Tests?

[vladimirradosavljevic]

In D157267#4568479, @kmitropoulou wrote:

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

[vladimirradosavljevic]

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

[kmitropoulou]

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);
}

}

[vladimirradosavljevic]

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]

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]

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]

Comments addressed.

[vladimirradosavljevic]

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.

[vladimirradosavljevic]

Ping.

[vladimirradosavljevic]

Ping.

[kmitropoulou]

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

[vladimirradosavljevic]

In D157267#4641527, @kmitropoulou wrote:

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 <[e-mail]>

[kmitropoulou]

I will do it :)

[kmitropoulou]

The patch was merged in:

commit 3a318382baceacc94992f0239636d6d243a57565

[kmitropoulou]

Can you please close the ticket?

[vladimirradosavljevic]

Merged in rG798f2465f3dfdbe21463f3008c51a6e63cc271c2.
@kmitropoulou Thanks!

llvm/lib/Transforms/Scalar/NewGVN.cpp

if (alwaysAvailable(Leader)) {
           // original operand, as we already know we can just drop it.
           auto *ReplacedInst = cast<Instruction>(U->get());
           auto *PI = PredInfo->getPredicateInfoFor(ReplacedInst);
           if (!PI || DominatingLeader != PI->OriginalOp)
             patchReplacementInstruction(ReplacedInst, DominatingLeader);
           U->set(DominatingLeader);
           // This is now a use of the dominating leader, which means if the
           // dominating leader was dead, it's now live!
-          auto &LeaderUseCount = UseCounts[DominatingLeader];
+          auto LeaderUseCount = UseCounts[DominatingLeader];
           // It's about to be alive again.
           if (LeaderUseCount == 0 && isa<Instruction>(DominatingLeader))
             ProbablyDead.erase(cast<Instruction>(DominatingLeader));
           // For copy instructions, we use their operand as a leader,
           // which means we remove a user of the copy and it may become dead.
           if (isSSACopy) {
             unsigned &IIUseCount = UseCounts[II];
             if (--IIUseCount == 0)
               ProbablyDead.insert(II);
           }
-          ++LeaderUseCount;
+          ++UseCounts[DominatingLeader];
           AnythingReplaced = true;
         }
       }
     }
 
     // At this point, anything still in the ProbablyDead set is actually dead if
     // would be trivially dead.
     for (auto *I : ProbablyDead)