[ADCE] Fix non-deterministic behaviour due to iterating over a pointer set

[aemerson]

Summary

The following IR run through opt -adce 50 times will show a difference, but writing a test for this particular kind of behavior isn't possible AFAIK.

Original patch by Yann Laigle-Chapuy

[aemerson]

Test IR:

target datalayout = "e-m:o-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-apple-macosx10.10.0"

; Function Attrs: noinline nounwind ssp uwtable
define void @ham() local_unnamed_addr #0 {
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
}

attributes #0 = { noinline nounwind ssp uwtable "correctly-rounded-divide-sqrt-fp-math"="false" "disable-tail-calls"="false" "less-precise-fpmad"="false" "no-frame-pointer-elim"="true" "no-frame-pointer-elim-non-leaf" "no-infs-fp-math"="false" "no-jump-tables"="false" "no-nans-fp-math"="false" "no-signed-zeros-fp-math"="false" "no-trapping-math"="false" "stack-protector-buffer-size"="8" "target-cpu"="core2" "target-features"="+cx16,+fxsr,+mmx,+sse,+sse2,+sse3,+ssse3,+x87" "unsafe-fp-math"="false" "use-soft-float"="false" }

!llvm.module.flags = !{!0}

!0 = !{i32 7, !"PIC Level", i32 2}

[fhahn]

LGTM, thanks. We iterate over BlocksWithDeadTerminators later on, which can cause edges to BBs to be removed a different order.

I think you should add the test IR test, just pass and check -preserve-ll-uselistorder. There should be an upstream bot setting LLVM_REVERSE_ITERATION, which should result in a different use-list ordering without this patch.

llvm/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() {
   });
 
   // The dominance frontier of a live block X in the reverse
   // 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.
 
+  const SmallPtrSet<BasicBlock *, 16> BWDT{
+      BlocksWithDeadTerminators.begin(),
+      BlocksWithDeadTerminators.end()
+  };
   SmallVector<BasicBlock *, 32> IDFBlocks;
   ReverseIDFCalculator IDFs(PDT);
   IDFs.setDefiningBlocks(NewLiveBlocks);
-  IDFs.setLiveInBlocks(BlocksWithDeadTerminators);
+  IDFs.setLiveInBlocks(BWDT);
   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());
   }