[ADCE] Fix for non-determistic uselists after dead block removal

[Gerolf]

Summary

The order of blocks in BlocksWithDeadTerminators may impact uselists.
They can differ from run to run for the same input. The attached test case is
only meant to show the problem to anyone interested. It is not a test I plan to
commit, at least not in its current form.

[efriedma]

Maybe worth explicitly mentioning in the commit message that AggressiveDeadCodeElimination::updateDeadRegions loops over BlocksWithDeadTerminators.

It's fine to commit non-determinism patches without a test, I think, because it's hard to write a useful regression test for these issues. I mean, you could theoretically CHECK the use-list itself, but that isn't really productive.

lib/Transforms/Scalar/ADCE.cpp

 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/ADCE.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DepthFirstIterator.h"
 #include "llvm/ADT/GraphTraits.h"
 #include "llvm/ADT/MapVector.h"
 #include "llvm/ADT/PostOrderIterator.h"
+#include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/DomTreeUpdater.h"
 #include "llvm/Analysis/GlobalsModRef.h"
 #include "llvm/Analysis/IteratedDominanceFrontier.h"
 #include "llvm/Analysis/PostDominators.h"
 #include "llvm/IR/BasicBlock.h"
class AggressiveDeadCodeElimination {
   /// Instructions known to be live where we need to mark
   /// reaching definitions as live.
   SmallVector<Instruction *, 128> Worklist;
 
   /// Debug info scopes around a live instruction.
   SmallPtrSet<const Metadata *, 32> AliveScopes;
 
   /// Set of blocks with not known to have live terminators.
-  SmallPtrSet<BasicBlock *, 16> BlocksWithDeadTerminators;
+  SmallSetVector<BasicBlock *, 16> BlocksWithDeadTerminators;
 
   /// The set of blocks which we have determined whose control
   /// dependence sources must be live and which have not had
   /// those dependences analyzed.
   SmallPtrSet<BasicBlock *, 16> NewLiveBlocks;
 
   /// Set up auxiliary data structures for Instructions and BasicBlocks and
   /// initialize the Worklist to the set of must-be-live Instruscions.
void AggressiveDeadCodeElimination::markLive(Instruction *I) {
 
   // Collect the live debug info scopes attached to this instruction.
   if (const DILocation *DL = I->getDebugLoc())
     collectLiveScopes(*DL);
 
   // Mark the containing block live
   auto &BBInfo = *Info.Block;
   if (BBInfo.Terminator == I) {
-    BlocksWithDeadTerminators.erase(BBInfo.BB);
+    BlocksWithDeadTerminators.remove(BBInfo.BB);
     // For live terminators, mark destination blocks
     // live to preserve this control flow edges.
     if (!BBInfo.UnconditionalBranch)
       for (auto *BB : successors(I->getParent()))
         markLive(BB);
   }
   markLive(BBInfo);
 }
void AggressiveDeadCodeElimination::markLiveBranchesFromControlDependences() {
   // control graph is the set of blocks upon which X is control
   // dependent. The following sequence computes the set of blocks
   // which currently have dead terminators that are control
   // dependence sources of a block which is in NewLiveBlocks.
 
   SmallVector<BasicBlock *, 32> IDFBlocks;
   ReverseIDFCalculator IDFs(PDT);
   IDFs.setDefiningBlocks(NewLiveBlocks);
-  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  SmallPtrSet<BasicBlock *, 16> S(BlocksWithDeadTerminators.begin(),
+                                  BlocksWithDeadTerminators.end());
+  IDFs.setLiveInBlocks(S);
   IDFs.calculate(IDFBlocks);
   NewLiveBlocks.clear();
 
   // Dead terminators which control live blocks are now marked live.
   for (auto *BB : IDFBlocks) {
     LLVM_DEBUG(dbgs() << "live control in: " << BB->getName() << '\n');
     markLive(BB->getTerminator());
   }

test/Transforms/ADCE/adce_random0.ll

+; RUN: opt -S -adce < %s
+; Exposed a non-deterministic bitcode
+; Run it N times eg.
+; for i in `seq 10`
+; do opt -ipsccp  -o out < %s
+; shasum out
+; done | sort -u | wc -l
+
+define void @foo() {
+bb:
+  br i1 false, label %bb1, label %bb22
+
+bb1:                                              ; preds = %bb
+  br i1 undef, label %bb2, label %bb20
+
+bb2:                                              ; preds = %bb1
+  br label %bb5
+
+bb5:                                              ; preds = %bb16, %bb2
+  br i1 undef, label %bb6, label %bb17
+
+bb6:                                              ; preds = %bb5
+  br i1 undef, label %bb7, label %bb16
+
+bb7:                                              ; preds = %bb6
+  br i1 undef, label %bb9, label %bb8
+
+bb8:                                              ; preds = %bb7
+  br i1 undef, label %bb9, label %bb10
+
+bb9:                                              ; preds = %bb8, %bb7
+  br label %bb13
+
+bb10:                                             ; preds = %bb8
+  br label %bb12
+
+bb12:                                             ; preds = %bb10
+  br label %bb13
+
+bb13:                                             ; preds = %bb12, %bb9
+  br label %bb14
+
+bb14:                                             ; preds = %bb13
+  br label %bb15
+
+bb15:                                             ; preds = %bb14
+  br label %bb16
+
+bb16:                                             ; preds = %bb15, %bb6
+  br label %bb5
+
+bb17:                                             ; preds = %bb5
+  br label %bb19
+
+bb19:                                             ; preds = %bb17
+  br label %bb21
+
+bb20:                                             ; preds = %bb1
+  br label %bb21
+
+bb21:                                             ; preds = %bb20, %bb19
+  br label %bb22
+
+bb22:                                             ; preds = %bb21, %bb
+  ret void
+}