[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

4668

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/include/llvm/Transforms/Scalar/SROA.h

 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_SROA_H
 #define LLVM_TRANSFORMS_SCALAR_SROA_H
 
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/IR/PassManager.h"
+#include "llvm/IR/ValueHandle.h"
 #include <vector>
 
 namespace llvm {
 
 class AllocaInst;
 class AssumptionCache;
 class DominatorTree;
 class Function;
class SROA : public PassInfoMixin<SROA> {
   /// added to it as well to recursively simplify unless that alloca can be
   /// directly promoted. Finally, each time we rewrite a use of an alloca other
   /// the one being actively rewritten, we add it back onto the list if not
   /// already present to ensure it is re-visited.
   SetVector<AllocaInst *, SmallVector<AllocaInst *, 16>> Worklist;
 
   /// A collection of instructions to delete.
   /// We try to batch deletions to simplify code and make things a bit more
-  /// efficient.
-  SetVector<Instruction *, SmallVector<Instruction *, 8>> DeadInsts;
+  /// efficient. We also make sure there is no dangling pointers.
+  SmallVector<WeakVH, 8> DeadInsts;
 
   /// Post-promotion worklist.
   ///
   /// Sometimes we discover an alloca which has a high probability of becoming
   /// viable for SROA after a round of promotion takes place. In those cases,
   /// the alloca is enqueued here for re-processing.
   ///
   /// Note that we have to be very careful to clear allocas out of this list in

llvm/lib/Transforms/Scalar/SROA.cpp

unsigned getIndex(uint64_t Offset) {
     uint32_t Index = RelOffset / ElementSize;
     assert(Index * ElementSize == RelOffset);
     return Index;
   }
 
   void deleteIfTriviallyDead(Value *V) {
     Instruction *I = cast<Instruction>(V);
     if (isInstructionTriviallyDead(I))
-      Pass.DeadInsts.insert(I);
+      Pass.DeadInsts.push_back(I);
   }
 
   Value *rewriteVectorizedLoadInst() {
     unsigned BeginIndex = getIndex(NewBeginOffset);
     unsigned EndIndex = getIndex(NewEndOffset);
     assert(EndIndex > BeginIndex && "Empty vector!");
 
     Value *V = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
if (IsSplit) {
                         "insert");
       LI.replaceAllUsesWith(V);
       Placeholder->replaceAllUsesWith(&LI);
       Placeholder->deleteValue();
     } else {
       LI.replaceAllUsesWith(V);
     }
 
-    Pass.DeadInsts.insert(&LI);
+    Pass.DeadInsts.push_back(&LI);
     deleteIfTriviallyDead(OldOp);
     LLVM_DEBUG(dbgs() << "          to: " << *V << "\n");
     return !LI.isVolatile() && !IsPtrAdjusted;
   }
 
   bool rewriteVectorizedStoreInst(Value *V, StoreInst &SI, Value *OldOp,
                                   AAMDNodes AATags) {
     if (V->getType() != VecTy) {
if (V->getType() != VecTy) {
       // Mix in the existing elements.
       Value *Old = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                          NewAI.getAlign(), "load");
       V = insertVector(IRB, Old, V, BeginIndex, "vec");
     }
     StoreInst *Store = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlign());
     if (AATags)
       Store->setAAMetadata(AATags);
-    Pass.DeadInsts.insert(&SI);
+    Pass.DeadInsts.push_back(&SI);
 
     LLVM_DEBUG(dbgs() << "          to: " << *Store << "\n");
     return true;
   }
 
   bool rewriteIntegerStore(Value *V, StoreInst &SI, AAMDNodes AATags) {
     assert(IntTy && "We cannot extract an integer from the alloca");
     assert(!SI.isVolatile());
     if (DL.getTypeSizeInBits(V->getType()).getFixedSize() !=
         IntTy->getBitWidth()) {
       Value *Old = IRB.CreateAlignedLoad(NewAI.getAllocatedType(), &NewAI,
                                          NewAI.getAlign(), "oldload");
       Old = convertValue(DL, IRB, Old, IntTy);
       assert(BeginOffset >= NewAllocaBeginOffset && "Out of bounds offset");
       uint64_t Offset = BeginOffset - NewAllocaBeginOffset;
       V = insertInteger(DL, IRB, Old, SI.getValueOperand(), Offset, "insert");
     }
     V = convertValue(DL, IRB, V, NewAllocaTy);
     StoreInst *Store = IRB.CreateAlignedStore(V, &NewAI, NewAI.getAlign());
     Store->copyMetadata(SI, {LLVMContext::MD_mem_parallel_loop_access,
                              LLVMContext::MD_access_group});
     if (AATags)
       Store->setAAMetadata(AATags);
-    Pass.DeadInsts.insert(&SI);
+    Pass.DeadInsts.push_back(&SI);
     LLVM_DEBUG(dbgs() << "          to: " << *Store << "\n");
     return true;
   }
 
   bool visitStoreInst(StoreInst &SI) {
     LLVM_DEBUG(dbgs() << "    original: " << SI << "\n");
     Value *OldOp = SI.getOperand(1);
     assert(OldOp == OldPtr);
bool visitStoreInst(StoreInst &SI) {
     NewSI->copyMetadata(SI, {LLVMContext::MD_mem_parallel_loop_access,
                              LLVMContext::MD_access_group});
     if (AATags)
       NewSI->setAAMetadata(AATags);
     if (SI.isVolatile())
       NewSI->setAtomic(SI.getOrdering(), SI.getSyncScopeID());
     if (NewSI->isAtomic())
       NewSI->setAlignment(SI.getAlign());
-    Pass.DeadInsts.insert(&SI);
+    Pass.DeadInsts.push_back(&SI);
     deleteIfTriviallyDead(OldOp);
 
     LLVM_DEBUG(dbgs() << "          to: " << *NewSI << "\n");
     return NewSI->getPointerOperand() == &NewAI && !SI.isVolatile();
   }
 
   /// Compute an integer value from splatting an i8 across the given
   /// number of bytes.
if (!isa<Constant>(II.getLength())) {
       II.setDest(getNewAllocaSlicePtr(IRB, OldPtr->getType()));
       II.setDestAlignment(getSliceAlign());
 
       deleteIfTriviallyDead(OldPtr);
       return false;
     }
 
     // Record this instruction for deletion.
-    Pass.DeadInsts.insert(&II);
+    Pass.DeadInsts.push_back(&II);
 
     Type *AllocaTy = NewAI.getAllocatedType();
     Type *ScalarTy = AllocaTy->getScalarType();
 
     const bool CanContinue = [&]() {
       if (VecTy || IntTy)
         return true;
       if (BeginOffset > NewAllocaBeginOffset ||
if (EmitMemCpy && &OldAI == &NewAI) {
 
       // Rewrite the size as needed.
       if (NewEndOffset != EndOffset)
         II.setLength(ConstantInt::get(II.getLength()->getType(),
                                       NewEndOffset - NewBeginOffset));
       return false;
     }
     // Record this instruction for deletion.
-    Pass.DeadInsts.insert(&II);
+    Pass.DeadInsts.push_back(&II);
 
     // Strip all inbounds GEPs and pointer casts to try to dig out any root
     // alloca that should be re-examined after rewriting this instruction.
     Value *OtherPtr = IsDest ? II.getRawSource() : II.getRawDest();
     if (AllocaInst *AI =
             dyn_cast<AllocaInst>(OtherPtr->stripInBoundsOffsets())) {
       assert(AI != &OldAI && AI != &NewAI &&
              "Splittable transfers cannot reach the same alloca on both ends.");
#endif
   }
 
   bool visitIntrinsicInst(IntrinsicInst &II) {
     assert((II.isLifetimeStartOrEnd() || II.isDroppable()) &&
            "Unexpected intrinsic!");
     LLVM_DEBUG(dbgs() << "    original: " << II << "\n");
 
     // Record this instruction for deletion.
-    Pass.DeadInsts.insert(&II);
+    Pass.DeadInsts.push_back(&II);
 
     if (II.isDroppable()) {
       assert(II.getIntrinsicID() == Intrinsic::assume && "Expected assume");
       // TODO For now we forget assumed information, this can be improved.
       OldPtr->dropDroppableUsesIn(II);
       return true;
     }
 
for (User *LU : LI->users()) {
         ResplitPromotableAllocas.insert(OtherAI);
         Worklist.insert(OtherAI);
       } else if (AllocaInst *OtherAI = dyn_cast<AllocaInst>(
                      StoreBasePtr->stripInBoundsOffsets())) {
         Worklist.insert(OtherAI);
       }
 
       // Mark the original store as dead.
-      DeadInsts.insert(SI);
+      DeadInsts.push_back(SI);
     }
 
     // Save the split loads if there are deferred stores among the users.
     if (DeferredStores)
       SplitLoadsMap.insert(std::make_pair(LI, std::move(SplitLoads)));
 
     // Mark the original load as dead and kill the original slice.
-    DeadInsts.insert(LI);
+    DeadInsts.push_back(LI);
     Offsets.S->kill();
   }
 
   // Second, we rewrite all of the split stores. At this point, we know that
   // all loads from this alloca have been split already. For stores of such
   // loads, we can simply look up the pre-existing split loads. For stores of
   // other loads, we split those loads first and then write split stores of
   // them.
for (StoreInst *SI : Stores) {
     // for some other alloca, but it may be a normal load. This may introduce
     // redundant loads, but where those can be merged the rest of the optimizer
     // should handle the merging, and this uncovers SSA splits which is more
     // important. In practice, the original loads will almost always be fully
     // split and removed eventually, and the splits will be merged by any
     // trivial CSE, including instcombine.
     if (LI->hasOneUse()) {
       assert(*LI->user_begin() == SI && "Single use isn't this store!");
-      DeadInsts.insert(LI);
+      DeadInsts.push_back(LI);
     }
-    DeadInsts.insert(SI);
+    DeadInsts.push_back(SI);
     Offsets.S->kill();
   }
 
   // Remove the killed slices that have ben pre-split.
   llvm::erase_if(AS, [](const Slice &S) { return S.isDead(); });
 
   // Insert our new slices. This will sort and merge them into the sorted
   // sequence.
for (SelectInst *Sel : SelectUsers)
     }
 
   if (Promotable) {
     for (Use *U : AS.getDeadUsesIfPromotable()) {
       auto *OldInst = dyn_cast<Instruction>(U->get());
       Value::dropDroppableUse(*U);
       if (OldInst)
         if (isInstructionTriviallyDead(OldInst))
-          DeadInsts.insert(OldInst);
+          DeadInsts.push_back(OldInst);
     }
     if (PHIUsers.empty() && SelectUsers.empty()) {
       // Promote the alloca.
       PromotableAllocas.push_back(NewAI);
     } else {
       // If we have either PHIs or Selects to speculate, add them to those
       // worklists and re-queue the new alloca so that we promote in on the
       // next iteration.
void SROA::clobberUse(Use &U) {
   // Replace the use with an undef value.
   U = UndefValue::get(OldV->getType());
 
   // Check for this making an instruction dead. We have to garbage collect
   // all the dead instructions to ensure the uses of any alloca end up being
   // minimal.
   if (Instruction *OldI = dyn_cast<Instruction>(OldV))
     if (isInstructionTriviallyDead(OldI)) {
-      DeadInsts.insert(OldI);
+      DeadInsts.push_back(OldI);
     }
 }
 
 /// Analyze an alloca for SROA.
 ///
 /// This analyzes the alloca to ensure we can reason about it, builds
 /// the slices of the alloca, and then hands it off to be split and
 /// rewritten as needed.
for (Instruction *DeadUser : AS.getDeadUsers()) {
     // Free up everything used by this instruction.
     for (Use &DeadOp : DeadUser->operands())
       clobberUse(DeadOp);
 
     // Now replace the uses of this instruction.
     DeadUser->replaceAllUsesWith(UndefValue::get(DeadUser->getType()));
 
     // And mark it for deletion.
-    DeadInsts.insert(DeadUser);
+    DeadInsts.push_back(DeadUser);
     Changed = true;
   }
   for (Use *DeadOp : AS.getDeadOperands()) {
     clobberUse(*DeadOp);
     Changed = true;
   }
 
   // No slices to split. Leave the dead alloca for a later pass to clean up.

 /// 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();
+    Instruction *I = dyn_cast_or_null<Instruction>(DeadInsts.pop_back_val());
+    if (!I) continue; 
     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);
+          DeadInsts.push_back(U);
       }
 
     ++NumDeleted;
     I->eraseFromParent();
     Changed = true;
   }
   return Changed;
 }