[SROA] Remove Dead Instructions while creating speculative instructions

[arnamoy10]

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.

[arnamoy10]

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:

test.ll10 KBDownload

[davide]

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

[lebedev.ri]

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.

[arnamoy10]

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]

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

[jmorse]

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

[arnamoy10]

Adding more context to the diff.

[tra]

clang/lib/Driver/ToolChains/Cuda.h

33 ↗

(On Diff #310951)

Were CUDA changes intended to be included in this patch?

[arnamoy10]

Creating a patch with more context

[lebedev.ri]

Looks good to me.

[nikic]

llvm/lib/Transforms/Scalar/SROA.cpp

4702

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

[arnamoy10]

Nullptr check change

[lebedev.ri]

If you need help landing this please state so and specify Name <[e-mail]> to be used for commit.

[arnamoy10]

@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]

Rebased to the latest master of LLVM

[lebedev.ri]

In D92431#2460629, @arnamoy10 wrote:

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

In D92431#2460560, @lebedev.ri wrote:

If you need help landing this please state so and specify Name <[e-mail]> to be used for commit.

llvm/lib/Transforms/Scalar/SROA.cpp

if (isSafeToLoadUnconditionally(InVal, MaxAlign, MaxSize, DL, TI))
       continue;
 
     return false;
   }
 
   return true;
 }
 
-static void speculatePHINodeLoads(PHINode &PN) {
+typedef SetVector<Instruction *, SmallVector<Instruction *,8>> DeadInstsTy;
+
+static void speculatePHINodeLoads(PHINode &PN, DeadInstsTy &DeadInsts) {
   LLVM_DEBUG(dbgs() << "    original: " << PN << "\n");
 
   LoadInst *SomeLoad = cast<LoadInst>(PN.user_back());
   Type *LoadTy = SomeLoad->getType();
   IRBuilderTy PHIBuilder(&PN);
   PHINode *NewPN = PHIBuilder.CreatePHI(LoadTy, PN.getNumIncomingValues(),
                                         PN.getName() + ".sroa.speculated");
 
   // Get the AA tags and alignment to use from one of the loads. It does not
   // matter which one we get and if any differ.
   AAMDNodes AATags;
   SomeLoad->getAAMetadata(AATags);
   Align Alignment = SomeLoad->getAlign();
 
   // Rewrite all loads of the PN to use the new PHI.
   while (!PN.use_empty()) {
     LoadInst *LI = cast<LoadInst>(PN.user_back());
     LI->replaceAllUsesWith(NewPN);
+    // Remove from DeadInsts to avoid dangling pointers
+    if (DeadInsts.count(LI) > 0)
+      DeadInsts.remove(LI);
     LI->eraseFromParent();
   }
 
   // Inject loads into all of the pred blocks.
   DenseMap<BasicBlock*, Value*> InjectedLoads;
   for (unsigned Idx = 0, Num = PN.getNumIncomingValues(); Idx != Num; ++Idx) {
     BasicBlock *Pred = PN.getIncomingBlock(Idx);
     Value *InVal = PN.getIncomingValue(Idx);
for (User *U : SI.users()) {
     if (!isSafeToLoadUnconditionally(FValue, LI->getType(),
                                      LI->getAlign(), DL, LI))
       return false;
   }
 
   return true;
 }
 
-static void speculateSelectInstLoads(SelectInst &SI) {
+static void speculateSelectInstLoads(SelectInst &SI, DeadInstsTy &DeadInsts) {
   LLVM_DEBUG(dbgs() << "    original: " << SI << "\n");
 
   IRBuilderTy IRB(&SI);
   Value *TV = SI.getTrueValue();
   Value *FV = SI.getFalseValue();
   // Replace the loads of the select with a select of two loads.
   while (!SI.use_empty()) {
     LoadInst *LI = cast<LoadInst>(SI.user_back());
     assert(LI->isSimple() && "We only speculate simple loads");
 
+    // Do not have to process DEAD Loads
+    if (DeadInsts.count(LI) > 0) {
+      DeadInsts.remove(LI);
+      LI->eraseFromParent();
+      continue;
+    }
+
     IRB.SetInsertPoint(LI);
     LoadInst *TL = IRB.CreateLoad(LI->getType(), TV,
                                   LI->getName() + ".sroa.speculate.load.true");
     LoadInst *FL = IRB.CreateLoad(LI->getType(), FV,
                                   LI->getName() + ".sroa.speculate.load.false");
     NumLoadsSpeculated += 2;
 
     // Transfer alignment and AA info if present.
bool SROA::runOnAlloca(AllocaInst &AI) {
   // No slices to split. Leave the dead alloca for a later pass to clean up.
   if (AS.begin() == AS.end())
     return Changed;
 
   Changed |= splitAlloca(AI, AS);
 
   LLVM_DEBUG(dbgs() << "  Speculating PHIs\n");
   while (!SpeculatablePHIs.empty())
-    speculatePHINodeLoads(*SpeculatablePHIs.pop_back_val());
+    speculatePHINodeLoads(*SpeculatablePHIs.pop_back_val(), DeadInsts);
 
   LLVM_DEBUG(dbgs() << "  Speculating Selects\n");
   while (!SpeculatableSelects.empty())
-    speculateSelectInstLoads(*SpeculatableSelects.pop_back_val());
+    speculateSelectInstLoads(*SpeculatableSelects.pop_back_val(), DeadInsts);
 
   return Changed;
 }
 
 /// Delete the dead instructions accumulated in this run.
 ///
 /// Recursively deletes the dead instructions we've accumulated. This is done
 /// at the very end to maximize locality of the recursive delete and to
 /// minimize the problems of invalidated instruction pointers as such pointers
 /// are used heavily in the intermediate stages of the algorithm.
 ///
 /// We also record the alloca instructions deleted here so that they aren't
 /// subsequently handed to mem2reg to promote.
 bool SROA::deleteDeadInstructions(
     SmallPtrSetImpl<AllocaInst *> &DeletedAllocas) {
   bool Changed = false;
   while (!DeadInsts.empty()) {
     Instruction *I = DeadInsts.pop_back_val();
     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();