[SROA] Correctly invalidate analyses when dead instructions deleted

[tejohnson]

Summary

SROA can fail in rewriting alloca but still rewrite a phi resulting
in dead instruction elimination. The Changed flag was not being set
correctly, resulting in downstream passes using stale analyses.
The included test case will assert during the second BDCE pass as a
result.

[tejohnson]

Ping

[davide]

This is correct but please simplify the testcase :) [I don't think you need branch weight metadata]

[tejohnson]

Simplify the test case as much as possible

[davide]

LGTM

test/Transforms/SROA/dead-inst.ll

15–16

you don't need these two.

[tejohnson]

Remove ModuleID and source_filename

include/llvm/Transforms/Scalar/SROA.h

PreservedAnalyses runImpl(Function &F, DominatorTree &RunDT,
                             AssumptionCache &RunAC);
 
   bool presplitLoadsAndStores(AllocaInst &AI, sroa::AllocaSlices &AS);
   AllocaInst *rewritePartition(AllocaInst &AI, sroa::AllocaSlices &AS,
                                sroa::Partition &P);
   bool splitAlloca(AllocaInst &AI, sroa::AllocaSlices &AS);
   bool runOnAlloca(AllocaInst &AI);
   void clobberUse(Use &U);
-  void deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
+  bool deleteDeadInstructions(SmallPtrSetImpl<AllocaInst *> &DeletedAllocas);
   bool promoteAllocas(Function &F);
 };
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SROA_H

lib/Transforms/Scalar/SROA.cpp

 ///
 /// 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.
-void SROA::deleteDeadInstructions(
+bool SROA::deleteDeadInstructions(
     SmallPtrSetImpl<AllocaInst *> &DeletedAllocas) {
+  bool Changed = false;
   while (!DeadInsts.empty()) {
     Instruction *I = DeadInsts.pop_back_val();
     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)) {
for (Use &Operand : I->operands())
         // 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;
 }
 
 /// \brief Promote the allocas, using the best available technique.
 ///
 /// This attempts to promote whatever allocas have been identified as viable in
 /// the PromotableAllocas list. If that list is empty, there is nothing to do.
 /// This function returns whether any promotion occurred.
 bool SROA::promoteAllocas(Function &F) {
PreservedAnalyses SROA::runImpl(Function &F, DominatorTree &RunDT,
   bool Changed = false;
   // A set of deleted alloca instruction pointers which should be removed from
   // the list of promotable allocas.
   SmallPtrSet<AllocaInst *, 4> DeletedAllocas;
 
   do {
     while (!Worklist.empty()) {
       Changed |= runOnAlloca(*Worklist.pop_back_val());
-      deleteDeadInstructions(DeletedAllocas);
+      Changed |= deleteDeadInstructions(DeletedAllocas);
 
       // Remove the deleted allocas from various lists so that we don't try to
       // continue processing them.
       if (!DeletedAllocas.empty()) {
         auto IsInSet = [&](AllocaInst *AI) { return DeletedAllocas.count(AI); };
         Worklist.remove_if(IsInSet);
         PostPromotionWorklist.remove_if(IsInSet);
         PromotableAllocas.erase(llvm::remove_if(PromotableAllocas, IsInSet),

test/Transforms/SROA/dead-inst.ll

+; SROA fails to rewrite allocs but does rewrite some phis and delete
+; dead instructions. Ensure that this invalidates analyses required
+; for other passes.
+; RUN: opt < %s -passes=bdce,sroa,bdce -o %t -debug-pass-manager 2>&1 | FileCheck %s
+; CHECK: Running pass: BDCEPass on H
+; CHECK: Running analysis: DemandedBitsAnalysis on H
+; CHECK: Running pass: SROA on H
+; CHECK: Invalidating all non-preserved analyses for: H
+; CHECK: Invalidating analysis: DemandedBitsAnalysis on H
+; CHECK: Running pass: BDCEPass on H
+; CHECK: Running analysis: DemandedBitsAnalysis on H
+; CHECK: Finished llvm::Function pass manager run.
+
+target datalayout = "e-m:e-i64:64-n32:64"
+target triple = "powerpc64le-grtev4-linux-gnu"
+
+%class.b = type { i64 }
+
+declare void @D(%class.b* sret, %class.b* dereferenceable(32)) local_unnamed_addr
+
+; Function Attrs: nounwind
+define hidden fastcc void @H(%class.b* noalias nocapture readnone, [2 x i64]) unnamed_addr {
+  %3 = alloca %class.b, align 8
+  %.sroa.0 = alloca i64, align 8
+  store i64 0, i64* %.sroa.0, align 8
+  %4 = extractvalue [2 x i64] %1, 1
+  switch i64 %4, label %6 [
+    i64 4, label %foo
+    i64 5, label %5
+  ]
+
+; <label>:5:
+  %.sroa.0.0..sroa_cast3 = bitcast i64* %.sroa.0 to i8**
+  br label %12
+
+; <label>:6:
+  %7 = icmp ugt i64 %4, 5
+  %.sroa.0.0..sroa_cast5 = bitcast i64* %.sroa.0 to i8**
+  br i1 %7, label %8, label %12
+
+; <label>:8:
+  %9 = load i8, i8* inttoptr (i64 4 to i8*), align 4
+  %10 = icmp eq i8 %9, 47
+  %11 = select i1 %10, i64 5, i64 4
+  br label %12
+
+; <label>:12:
+  %13 = phi i8** [ %.sroa.0.0..sroa_cast3, %5 ], [ %.sroa.0.0..sroa_cast5, %8 ], [ %.sroa.0.0..sroa_cast5, %6 ]
+  %14 = phi i64 [ 4, %5 ], [ %11, %8 ], [ 4, %6 ]
+  %15 = icmp ne i64 %4, 0
+  %16 = icmp ugt i64 %4, %14
+  %17 = and i1 %15, %16
+  br i1 %17, label %18, label %a.exit
+
+; <label>:18:
+  %19 = tail call i8* @memchr(i8* undef, i32 signext undef, i64 undef)
+  %20 = icmp eq i8* %19, null
+  %21 = sext i1 %20 to i64
+  br label %a.exit
+
+a.exit:
+  %22 = phi i64 [ -1, %12 ], [ %21, %18 ]
+  %23 = load i8*, i8** %13, align 8
+  %24 = sub nsw i64 %22, %14
+  %25 = bitcast %class.b* %3 to i8*
+  call void @llvm.lifetime.start.p0i8(i64 32, i8* nonnull %25)
+  %26 = icmp ult i64 %24, 2
+  br i1 %26, label %G.exit, label %27
+
+; <label>:27:
+  %28 = getelementptr inbounds i8, i8* %23, i64 undef
+  %29 = icmp eq i8* %28, null
+  br i1 %29, label %30, label %31
+
+; <label>:30:
+  unreachable
+
+; <label>:31:
+  call void @D(%class.b* nonnull sret %3, %class.b* nonnull dereferenceable(32) undef)
+  br label %G.exit
+
+G.exit:
+  call void @llvm.lifetime.end.p0i8(i64 32, i8* nonnull %25)
+  br label %foo
+
+foo:
+  ret void
+}
+
+; Function Attrs: nounwind readonly
+declare i8* @memchr(i8*, i32 signext, i64) local_unnamed_addr
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.start.p0i8(i64, i8* nocapture)
+
+; Function Attrs: argmemonly nounwind
+declare void @llvm.lifetime.end.p0i8(i64, i8* nocapture)