[Function Specialisation] Fix use after free

[labrinea]

Summary

This is a fix for a use-after-free found by the address sanitizer when compiling GCC: https://github.com/llvm/llvm-project/issues/52821

The Function Specialization pass may remove instructions, cached inside the PredicateBase class, which are later being dereferenced from the SCCPInstVisitor class. To prevent the dangling references I am lazily deleting the dead instructions after the Solver has run.

[nikic]

Can you please explain in more detail where exactly an instruction referenced by PredicateInfo gets removed, and why other passes using PredicateInfo (IPSCCP and NewGVN) do not encounter this issue?

[labrinea]

In D118591#3283559, @nikic wrote:

Can you please explain in more detail where exactly an instruction referenced by PredicateInfo gets removed, and why other passes using PredicateInfo (IPSCCP and NewGVN) do not encounter this issue?

Hi. If you follow the github link there's a dump from the address sanitizer and some explanation on the description of the issue. The instruction is removed by the function specialization pass inside tryToReplaceWithConstant after all its uses have been replaced. As far as I understand, the dangling pointer is then being dereferenced inside PredicateBase::getConstraint() (the function I've patched), which is being called from SCCPInstVisitor::handleCallResult. Both FunctionSpecialization and IPSCCP are using the SCCPSolver, which in turn is using the SCCPInstVisitor. The bug was exposed with ASAN when compilig GCC, so if the NewGVN is using the same machinery as the other passes, then it is potentially affected. I made a bootstrap build of clang with ASAN and FunctionSpecialization enabled and it succeeded. Also the reproducer is not triggering the use-after-free anymore.

[fhahn]

In D118591#3283811, @labrinea wrote:

In D118591#3283559, @nikic wrote:

Can you please explain in more detail where exactly an instruction referenced by PredicateInfo gets removed, and why other passes using PredicateInfo (IPSCCP and NewGVN) do not encounter this issue?

Hi. If you follow the github link there's a dump from the address sanitizer and some explanation on the description of the issue. The instruction is removed by the function specialization pass inside tryToReplaceWithConstant after all its uses have been replaced. As far as I understand, the dangling pointer is then being dereferenced inside PredicateBase::getConstraint() (the function I've patched), which is being called from SCCPInstVisitor::handleCallResult. Both FunctionSpecialization and IPSCCP are using the SCCPSolver, which in turn is using the SCCPInstVisitor. The bug was exposed with ASAN when compilig GCC, so if the NewGVN is using the same machinery as the other passes, then it is potentially affected. I made a bootstrap build of clang with ASAN and FunctionSpecialization enabled and it succeeded. Also the reproducer is not triggering the use-after-free anymore.

It sounds like the real problem may be that FunctionSpecialization removes instructions before the solver is finished and this lead to issues if the removed instructions has an associated PredicateInfo. WeakVH seems like a very heavy hammer to fix the underlying issue. Could FunctionSpecialization just delay removing instructions until all solving is done? If that's not possible, we may have to add a way to remove stale predicate info entries.

[labrinea]

As suggested by Florian, instead of using a WeakVH I am lazily removing the replaced instructions after the Solver has run. None of the existing tests actually covers this code path I am afraid. Examining the debug output of the reproducer I found two PhiNode instructions being replaced with null.

[SjoerdMeijer]

Agreed, lazily removing the instructions in this way is what I was expecting.

But this is a bit odd, a.k.a. not what I was expecting:

None of the existing tests actually covers this code path I am afraid.

Do you mean this:

if (I->isSafeToRemove()) {
   I->eraseFromParent();
   Solver.removeLatticeValueFor(I);
 }

Only triggers in the reproducer attached to the bugreport and not in the regression tests? I think we should first try hard to get a test for that, which I hope is doable. Otherwise, we might as well remove this code and rely on later clean up passes to delete dead code which I think is a valid strategy and alternative if it makes things really complicated here. But again, better would be to see if we can trigger this and a test for it.

[labrinea]

Added some debug output:

• when replacing a value
• when removing dead instructions

[labrinea]

In D118591#3286671, @SjoerdMeijer wrote:

Agreed, lazily removing the instructions in this way is what I was expecting.

But this is a bit odd, a.k.a. not what I was expecting:

None of the existing tests actually covers this code path I am afraid.

Do you mean this:

if (I->isSafeToRemove()) {
   I->eraseFromParent();
   Solver.removeLatticeValueFor(I);
 }

Only triggers in the reproducer attached to the bugreport and not in the regression tests? I think we should first try hard to get a test for that, which I hope is doable. Otherwise, we might as well remove this code and rely on later clean up passes to delete dead code which I think is a valid strategy and alternative if it makes things really complicated here. But again, better would be to see if we can trigger this and a test for it.

I was wrong when I said we are not testing the removal of dead instructions. I was looking at the tests under the original commit D93838, but we have actually added more tests since. For example function-specialization-constant-expression.ll is exercising this code path.

[SjoerdMeijer]

In D118591#3286952, @labrinea wrote:

I was wrong when I said we are not testing the removal of dead instructions. I was looking at the tests under the original commit D93838, but we have actually added more tests since. For example function-specialization-constant-expression.ll is exercising this code path.

Ok, very good, that's what I thought.

One more question about tests: does the sanitzer failure also happens/happened on these existing tests? If so, I think we are done. If not, we are possibly missing something and in this case, do we need to add a sanitizer test? I have never looked that, so don't even know if there are sanitizers tests that run opt.

[fhahn]

In D118591#3287222, @SjoerdMeijer wrote:

In D118591#3286952, @labrinea wrote:

I was wrong when I said we are not testing the removal of dead instructions. I was looking at the tests under the original commit D93838, but we have actually added more tests since. For example function-specialization-constant-expression.ll is exercising this code path.

Ok, very good, that's what I thought.

One more question about tests: does the sanitzer failure also happens/happened on these existing tests? If so, I think we are done. If not, we are possibly missing something and in this case, do we need to add a sanitizer test? I have never looked that, so don't even know if there are sanitizers tests that run opt.

To expose the issue, we might have to add a test where a compare that is used in a predicate gets simplified to a constant and removed and the solver needs to run again on the function.

[labrinea]

I have heavily modified the original reproducer, but the problem is that we don't have buildbots running the llvm regression tests with asan. I can only see two builders for libc with asan here https://lab.llvm.org/buildbot/#/builders. Do you think there's still value in adding this testcase?

[fhahn]

In D118591#3290145, @labrinea wrote:

I have heavily modified the original reproducer, but the problem is that we don't have buildbots running the llvm regression tests with asan. I can only see two builders for libc with asan here https://lab.llvm.org/buildbot/#/builders. Do you think there's still value in adding this testcase?

There should be multiple bots that run with various sanitizers, e.g. https://lab.llvm.org/buildbot/#/builders/168

[SjoerdMeijer]

In D118591#3290167, @fhahn wrote:

In D118591#3290145, @labrinea wrote:

I have heavily modified the original reproducer, but the problem is that we don't have buildbots running the llvm regression tests with asan. I can only see two builders for libc with asan here https://lab.llvm.org/buildbot/#/builders. Do you think there's still value in adding this testcase?

There should be multiple bots that run with various sanitizers, e.g. https://lab.llvm.org/buildbot/#/builders/168

In that case, let's do it; we have got a fix that looks reasonable and we have a test case. Before committing, the test case could do with a comment and checking a bit more though. Let's at least check the statements that the solver is changing and/or perhaps check for absence of the statements that are deleted (if that is still the case here).

[labrinea]

Ah, right, I didn't notice there was another builder page. I'll generate some check lines and commit. Thanks both :)

llvm/include/llvm/Transforms/Utils/PredicateInfo.h

 // Base class for all predicate information we provide.
 // All of our predicate information has at least a comparison.
 class PredicateBase : public ilist_node<PredicateBase> {
 public:
   PredicateType Type;
   // The original operand before we renamed it.
   // This can be use by passes, when destroying predicateinfo, to know
   // whether they can just drop the intrinsic, or have to merge metadata.
-  Value *OriginalOp;
+  WeakVH OriginalOp;
   // The renamed operand in the condition used for this predicate. For nested
   // predicates, this is different to OriginalOp which refers to the initial
   // operand.
-  Value *RenamedOp;
+  WeakVH RenamedOp;
   // The condition associated with this predicate.
-  Value *Condition;
+  WeakVH Condition;
 
   PredicateBase(const PredicateBase &) = delete;
   PredicateBase &operator=(const PredicateBase &) = delete;
   PredicateBase() = delete;
   virtual ~PredicateBase() = default;
   static bool classof(const PredicateBase *PB) {
     return PB->Type == PT_Assume || PB->Type == PT_Branch ||
            PB->Type == PT_Switch;

llvm/lib/Transforms/Utils/PredicateInfo.cpp

PredicateInfo::~PredicateInfo() {
   for (Function *F : FunctionPtrs) {
     assert(F->user_begin() == F->user_end() &&
            "PredicateInfo consumer did not remove all SSA copies.");
     F->eraseFromParent();
   }
 }
 
 Optional<PredicateConstraint> PredicateBase::getConstraint() const {
+  if (!OriginalOp || !RenamedOp || !Condition)
+    return None;
+
   switch (Type) {
   case PT_Assume:
   case PT_Branch: {
     bool TrueEdge = true;
     if (auto *PBranch = dyn_cast<PredicateBranch>(this))
       TrueEdge = PBranch->TrueEdge;
 
     if (Condition == RenamedOp) {
public:
   PredicateInfoAnnotatedWriter(const PredicateInfo *M) : PredInfo(M) {}
 
   void emitBasicBlockStartAnnot(const BasicBlock *BB,
                                 formatted_raw_ostream &OS) override {}
 
   void emitInstructionAnnot(const Instruction *I,
                             formatted_raw_ostream &OS) override {
     if (const auto *PI = PredInfo->getPredicateInfoFor(I)) {
+      if (!PI->OriginalOp || !PI->RenamedOp || !PI->Condition)
+        return;
       OS << "; Has predicate info\n";
       if (const auto *PB = dyn_cast<PredicateBranch>(PI)) {
         OS << "; branch predicate info { TrueEdge: " << PB->TrueEdge
            << " Comparison:" << *PB->Condition << " Edge: [";
         PB->From->printAsOperand(OS);
         OS << ",";
         PB->To->printAsOperand(OS);
         OS << "]";