This is an archive of the discontinued LLVM Phabricator instance.

[SROA] Remove Dead Instructions while creating speculative instructions
ClosedPublic

Authored by arnamoy10 on Dec 1 2020, 2:12 PM.

Details

Summary

The SROA pass tries to be lazy for removing dead instructions that are collected during iterative run of the pass in the DeadInsts list. However it does not remove instructions from the dead list while running eraseFromParent() on those instructions.

This causes (rare) null pointer dereferences. For example, in the speculatePHINodeLoads() instruction, in the following code snippet:

while (!PN.use_empty()) {
  LoadInst *LI = cast<LoadInst>(PN.user_back());
  LI->replaceAllUsesWith(NewPN);
  LI->eraseFromParent();
}

If the Load instruction LI belongs to the DeadInsts list, it should be removed when eraseFromParent() is called. However, the bug does not show up in most cases, because immediately in the same function, a new LoadInst is created in the following line:

LoadInst *Load = PredBuilder.CreateAlignedLoad(
         LoadTy, InVal, Alignment,
         (PN.getName() + ".sroa.speculate.load." + Pred->getName()));

This new LoadInst object takes the same memory address of the just deleted LI using eraseFromParent(), therefore the bug does not materialize. In very rare cases, the addresses differ and therefore, a dangling pointer is created, causing a crash.

Diff Detail

Event Timeline

arnamoy10 created this revision.Dec 1 2020, 2:12 PM
Herald added a project: Restricted Project. · View Herald TranscriptDec 1 2020, 2:12 PM
arnamoy10 requested review of this revision.Dec 1 2020, 2:12 PM

Here is a diff for the content of DeadInsts just before and after a speculatePHINodeLoads()

The address of the deleted LI was NOT taken by the new speculative load, giving rise to a dangling pointer in DeadInsts.

PS: The bug does not show up when running sroa standalone with opt or with Vanilla LLVM10 pipeline. We discovered the bug while compiling a test program for our custom compiler. The bitcode just before the crashing sroa was as follows:

davide removed a reviewer: davide.Dec 1 2020, 2:25 PM
davide added a subscriber: davide.

I apologize, but I don't work on this anymore.

davide removed a subscriber: davide.Dec 1 2020, 2:26 PM

This should be simpler.
Just change DeadInstsTy (without defining it) to use weakWH instead of Instruction*, and update the code that needs updating to skip over nulled weakWH's.

lebedev.ri requested changes to this revision.Dec 3 2020, 1:54 PM
This revision now requires changes to proceed.Dec 3 2020, 1:54 PM
arnamoy10 added a comment.EditedDec 4 2020, 6:55 AM

Hello @lebedev.ri ;

Thanks for the suggestion, as per your suggestion, I did the modification in the deleteDeadInstructions() function as follows:

bool SROA::deleteDeadInstructions( SmallPtrSetImpl<AllocaInst *> &DeletedAllocas) {
  bool Changed = false;
  while (!DeadInsts.empty()) {
    // BEGIN modification
    Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
    if (I == NULL) continue;
    // END modification

    LLVM_DEBUG(dbgs() << "Deleting dead instruction: " << *I << "\n");

    // If the instruction is an alloca, find the possible dbg.declare connected
    // to it, and remove it too. We must do this before calling RAUW or we will
    // not be able to find it.
    if (AllocaInst *AI = dyn_cast<AllocaInst>(I)) {
      DeletedAllocas.insert(AI);
      for (DbgVariableIntrinsic *OldDII : FindDbgAddrUses(AI))
        OldDII->eraseFromParent();
    }
    I->replaceAllUsesWith(UndefValue::get(I->getType()));

    for (Use &Operand : I->operands())
      if (Instruction *U = dyn_cast<Instruction>(Operand)) {
        // Zero out the operand and see if it becomes trivially dead.
       Operand = nullptr;
        if (isInstructionTriviallyDead(U))
          DeadInsts.insert(U);
      }
    ++NumDeleted;

    I->eraseFromParent();
    Changed = true;
  }
  return Changed;
}

Where I modified the definition of DeadInsts to use WeakVH

But I am getting the following error:

clang-10: /home/a00567935/for_upload/llvm-project_1141/llvm/include/llvm/ADT/DenseMap.h:378: void llvm::DenseMapBase<DerivedT, KeyT, ValueT, KeyInfoT, BucketT>::moveFromOldBuckets(BucketT*, BucketT*) [with DerivedT = llvm::DenseMap<llvm::WeakVH, llvm::detail::DenseSetEmpty, llvm::DenseMapInfo<llvm::WeakVH>, llvm::detail::DenseSetPair<llvm::WeakVH> >; KeyT = llvm::WeakVH; ValueT = llvm::detail::DenseSetEmpty; KeyInfoT = llvm::DenseMapInfo<llvm::WeakVH>; BucketT = llvm::detail::DenseSetPair<llvm::WeakVH>]: Assertion `!FoundVal && "Key already in new map?"' failed.

Stack dump:

0.      Program arguments: /home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10 -cc1 -triple aarch64-unknown-linux-gnu -emit-obj -disable-free -main-file-name test.c -mrelocation-model static -mthread-model posix -mllvm -pass-remarks= -mllvm -pass-remarks-missed= -mllvm -pass-remarks-analysis= -mframe-pointer=non-leaf -fmath-errno -ffp-contract=fast -fno-rounding-math -masm-verbose -mconstructor-aliases -target-cpu tsv110 -target-feature +v8.2a -target-feature +fp-armv8 -target-feature +neon -target-feature +crc -target-feature +crypto -target-feature +dotprod -target-feature +fp16fml -target-feature +spe -target-feature +ras -target-feature +lse -target-feature +rdm -target-feature +complxnum -target-feature +fullfp16 -target-feature +sha2 -target-feature +aes -target-abi aapcs -fallow-half-arguments-and-returns -dwarf-column-info -fno-split-dwarf-inlining -debugger-tuning=gdb -resource-dir /home/a00567935/for_upload/llvm-project_1141/install/lib/clang/10.0.1 -internal-isystem /usr/local/include -internal-isystem /home/a00567935/for_upload/llvm-project_1141/install/lib/clang/10.0.1/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -w -fdebug-compilation-dir /home/a00567935/bug/1141 -ferror-limit 19 -fmessage-length 0 -fno-signed-char -fgnuc-version=4.2.1 -fobjc-runtime=gcc -fdiagnostics-show-option -fcolor-diagnostics -vectorize-loops -vectorize-slp -faddrsig -o /tmp/test-2538e6.o -x c test.c

1.      <eof> parser at end of file
2.      Per-module optimization passes
3.      Running pass 'CallGraph Pass Manager' on module 'test.c'.
4.      Running pass 'SROA' on function '@g'

#0 0x0000aaaabb35fd18 llvm::sys::PrintStackTrace(llvm::raw_ostream&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2045d18)
#1 0x0000aaaabb35dee0 llvm::sys::RunSignalHandlers() (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2043ee0)
#2 0x0000aaaabb35e6b0 SignalHandler(int) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x20446b0)
#3 0x0000ffffb778c698 (linux-vdso.so.1+0x698)
#4 0x0000ffffb7451140 raise (/lib64/libc.so.6+0x33140)
#5 0x0000ffffb74524ec abort (/lib64/libc.so.6+0x344ec)
#6 0x0000ffffb744a54c __assert_fail_base (/lib64/libc.so.6+0x2c54c)
#7 0x0000ffffb744a5cc (/lib64/libc.so.6+0x2c5cc)
#8 0x0000aaaabb25ffc0 llvm::DenseMap<llvm::WeakVH, llvm::detail::DenseSetEmpty, llvm::DenseMapInfo<llvm::WeakVH>, llvm::detail::DenseSetPair<llvm::WeakVH> >::grow(unsigned int) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1f45fc0)
#9 0x0000aaaabb260178 llvm::SetVector<llvm::WeakVH, llvm::SmallVector<llvm::WeakVH, 8u>, llvm::DenseSet<llvm::WeakVH, llvm::DenseMapInfo<llvm::WeakVH> > >::insert(llvm::WeakVH const&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1f46178)
#10 0x0000aaaabb2624fc llvm::SROA::deleteDeadInstructions(llvm::SmallPtrSetImpl<llvm::AllocaInst*>&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1f484fc)
#11 0x0000aaaabb26d3f8 llvm::SROA::runImpl(llvm::Function&, llvm::DominatorTree&, llvm::AssumptionCache&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1f533f8)
#12 0x0000aaaabb26dcbc llvm::sroa::SROALegacyPass::runOnFunction(llvm::Function&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1f53cbc)
#13 0x0000aaaabad26a6c llvm::FPPassManager::runOnFunction(llvm::Function&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1a0ca6c)
#14 0x0000aaaabd46f164 (anonymous namespace)::CGPassManager::runOnModule(llvm::Module&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x4155164)
#15 0x0000aaaabad27730 llvm::legacy::PassManagerImpl::run(llvm::Module&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x1a0d730)
#16 0x0000aaaabb55ddc8 (anonymous namespace)::EmitAssemblyHelper::EmitAssembly(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2243dc8)
#17 0x0000aaaabb55efe4 clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::DataLayout const&, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2244fe4)
#18 0x0000aaaabbf3e5d4 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2c245d4)
#19 0x0000aaaabc8953d4 clang::ParseAST(clang::Sema&, bool, bool) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x357b3d4)
#20 0x0000aaaabbf3d670 clang::CodeGenAction::ExecuteAction() (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x2c23670)
#21 0x0000aaaabba0de00 clang::FrontendAction::Execute() (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x26f3e00)
#22 0x0000aaaabb9da140 clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x26c0140
#23 0x0000aaaabbac0d80 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0x27a6d80)
#24 0x0000aaaab9edafbc cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0xbc0fbc)
#25 0x0000aaaab9ed79f0 ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0xbbd9f0)
#26 0x0000aaaab9e7aad8 main (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0xb60ad8)
#27 0x0000ffffb743eb20 __libc_start_main (/lib64/libc.so.6+0x20b20)
#28 0x0000aaaab9ed74ec _start (/home/a00567935/for_upload/llvm-project_1141/install/bin/clang-10+0xbbd4ec)
clang-10: error: unable to execute command: Aborted (core dumped)
clang-10: error: clang frontend command failed due to signal (use -v to see invocation)

I think it is failing in the line DeadInsts.insert(U);

Could you please advise how to fix this?

arnamoy10 updated this revision to Diff 310942.Dec 10 2020, 9:43 AM
arnamoy10 added reviewers: jmorse, dexonsmith.

Using WeakVH instead of Instruction to take care of dangling pointers. Had to replace the "insert" calls of SetVector with a SmallVector push_back

Could you upload the patch with context please, as it's easier to navigate the changes. Instructions can be found here: https://llvm.org/docs/Phabricator.html#requesting-a-review-via-the-web-interface

Adding more context to the diff.

tra added a subscriber: tra.Dec 10 2020, 11:08 AM
tra added inline comments.
clang/lib/Driver/ToolChains/Cuda.h
33 ↗(On Diff #310951)

Were CUDA changes intended to be included in this patch?

arnamoy10 updated this revision to Diff 311249.Dec 11 2020, 9:12 AM

Creating a patch with more context

lebedev.ri accepted this revision.Dec 11 2020, 9:23 AM

Looks good to me.

This revision is now accepted and ready to land.Dec 11 2020, 9:23 AM
nikic added a subscriber: nikic.Dec 11 2020, 9:40 AM
nikic added inline comments.
llvm/lib/Transforms/Scalar/SROA.cpp
4668

This should be if (!I) continue;. Or if (I == nullptr) continue;, but that's unusual style for LLVM.

Nullptr check change

If you need help landing this please state so and specify Name <e@ma.il> to be used for commit.

arnamoy10 marked an inline comment as done.Dec 17 2020, 8:32 AM

@lebedev.ri Is there any instructions on how to land this? Sorry I am doing it for the first time

clang/lib/Driver/ToolChains/Cuda.h
33 ↗(On Diff #310951)

Update patch accordingly, no CUDA changes were not intended to be included.

arnamoy10 updated this revision to Diff 312779.Dec 18 2020, 6:08 AM

Rebased to the latest master of LLVM

@lebedev.ri Is there any instructions on how to land this? Sorry I am doing it for the first time

If you need help landing this please state so and specify Name <e@ma.il> to be used for commit.