[CodeGen] Make block removal order deterministic in CodeGenPrepare

[dstenb]

Summary

Replace use of a SmallPtrSet with a SmallSetVector to make the worklist
iteration order deterministic. This is done as the order the blocks are
removed may affect whether or not PHI nodes in successor blocks are
removed.

For example, consider the following case where %bb1 and %bb2 are
removed:

bb1:
  br i1 undef, label %bb3, label %bb4
bb2:
  br i1 undef, label %bb4, label %bb3
bb3:
  pv1 = phi type [ undef, %bb1 ], [ undef, %bb2], [ v0, %other ]
  br label %bb4
bb4:
  pv2 = phi type [ undef, %bb1 ], [ undef, %bb2 ],
                 [ pv1, %bb3 ], [ v0, %other ]

If %bb2 is removed before %bb1, the incoming values from %bb1 and %bb2
to pv1 will be removed before %bb1 is removed as a predecessor to %bb4.
The pv1 node will thus be optimized out (to v0) at the time %bb1 is
removed as a predecessor to %bb4, leaving the blocks as following when
the incoming value from %bb1 has been removed:

bb3:
  ; pv1 optimized out, incoming value to pv2 is v0
  br label %bb4
bb4:
  pv2 = phi type [ v0, %bb3 ], [ v0, %other ]

The pv2 PHI node will be optimized away by removePredecessor() as all
incoming values are identical.

In case %bb2 is removed after %bb1, pv1 will not be optimized out at the
time %bb2 is removed as a predecessor to %bb4, leaving the blocks as
following when the incoming value from %bb2 to pv2 has been removed:

bb3:
  pv1 = phi type [ undef, %bb2 ], [ v0, %other ]
  br label %bb4
bb4:
  pv2 = phi type [ pv1, %bb3 ], [ v0, %other ]

The pv2 PHI node will thus not be removed in this case, ultimately
leading to the following output:

bb3:
  ; pv1 optimized out, incoming value to pv2 is v0
  br label %bb4
bb4:
  pv2 = phi type [ v0, %bb3 ], [ v0, %other ]

I have not looked into changing DeleteDeadBlock() so that the redundant
PHI nodes are removed.

I have not added a test case, as I was not able to create a particularly
small and (not messy) reproducer. This is likely due to SmallPtrSet
behaving deterministically when in small mode.

[spatel]

Adding potential reviewers based on a grep of 'deterministic' in recent commits messages. :)

[fhahn]

lib/CodeGen/CodeGenPrepare.cpp

468

IIUC for each BB we look at the successor and only add a successor to the worklist, if it has exactly one predecessor, right? Doesn't that mean we only ever add each BB once and there wouldn't be a need for a set?

[dexonsmith]

lib/CodeGen/CodeGenPrepare.cpp

482–483

This call to remove is linear. Popping from the back would be amortized constant time:

BasicBlock *BB = WorkList.pop_back_val();

[dstenb]

lib/CodeGen/CodeGenPrepare.cpp

468

At least with how successors are handled now, we need it to be a set due to switch instructions where multiple cases share the same successor (for example %bb857.i in test/CodeGen/X86/2010-01-11-ExtraPHIArg.ll).

482–483

Oh, sorry! Fixed in the next revision.

[dstenb]

Use pop_back_val() for getting the items from the worklist.

[dexonsmith]

Resigning as reviewer (thanks for fixing the complexity); I'll let the other reviewers sort out if SmallVector is an even better solution here.

[fhahn]

LGTM, but please wait a bit with committing, in case there are any more comments.

lib/CodeGen/CodeGenPrepare.cpp

468

Right!

[dstenb]

Thanks for the reviews!

I'll submit this shortly then, unless someone objects.

lib/CodeGen/CodeGenPrepare.cpp

while (MadeChange) {
 
     EverMadeChange |= MadeChange;
   }
 
   SunkAddrs.clear();
 
   if (!DisableBranchOpts) {
     MadeChange = false;
-    SmallPtrSet<BasicBlock*, 8> WorkList;
+    // Use a set vector to get deterministic iteration order. The order the
+    // blocks are removed may affect whether or not PHI nodes in successors
+    // are removed.
+    SmallSetVector<BasicBlock*, 8> WorkList;
     for (BasicBlock &BB : F) {
       SmallVector<BasicBlock *, 2> Successors(succ_begin(&BB), succ_end(&BB));
       MadeChange |= ConstantFoldTerminator(&BB, true);
       if (!MadeChange) continue;
 
       for (SmallVectorImpl<BasicBlock*>::iterator
              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
         if (pred_begin(*II) == pred_end(*II))
           WorkList.insert(*II);
     }
 
     // Delete the dead blocks and any of their dead successors.
     MadeChange |= !WorkList.empty();
     while (!WorkList.empty()) {
-      BasicBlock *BB = *WorkList.begin();
-      WorkList.erase(BB);
+      BasicBlock *BB = WorkList.pop_back_val();
       SmallVector<BasicBlock*, 2> Successors(succ_begin(BB), succ_end(BB));
 
       DeleteDeadBlock(BB);
 
       for (SmallVectorImpl<BasicBlock*>::iterator
              II = Successors.begin(), IE = Successors.end(); II != IE; ++II)
         if (pred_begin(*II) == pred_end(*II))
           WorkList.insert(*II);