[SelectionDAG] Update the dominator after splitting critical edges

[davide]

Summary

Running llc -verify-dom-info on the attached testcase results in a crash in the verifier, due to a stale dominator tree.

i.e.

DominatorTree is not up to date!
Computed:
=============================--------------------------------
Inorder Dominator Tree: 
  [1] %safe_mod_func_uint8_t_u_u.exit.i.i.i {0,7}
    [2] %lor.lhs.false.i61.i.i.i {1,2}
    [2] %safe_mod_func_int8_t_s_s.exit.i.i.i {3,6}
      [3] %safe_div_func_int64_t_s_s.exit66.i.i.i {4,5}

Actual:
=============================--------------------------------
Inorder Dominator Tree: 
  [1] %safe_mod_func_uint8_t_u_u.exit.i.i.i {0,9}
    [2] %lor.lhs.false.i61.i.i.i {1,2}
    [2] %safe_mod_func_int8_t_s_s.exit.i.i.i {3,8}
      [3] %safe_div_func_int64_t_s_s.exit66.i.i.i {4,5}
      [3] %safe_mod_func_int8_t_s_s.exit.i.i.i.lor.lhs.false.i61.i.i.i_crit_edge {6,7}

This is because in SelectionDAGIsel we split critical edges without updating the corresponding dominator for the function (and we claim in MachineFunctionPass::getAnalysisUsage() that the domtree is preserved).

We could either stop preserving the domtree in getAnalysisUsage or tell splitCriticalEdge() to update it.
As the second option is easy to implement, that's the one I chose.

Side note: not sure why this went unnoticed for so long.

[efriedma]

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

405 ↗

(On Diff #101109)

Can you use getAnalysisIfAvailable here?

test/CodeGen/X86/O0-pipeline.ll

35 ↗

(On Diff #101109)

This test is specifically here to make sure we don't add unnecessary passes to -O0. This is not progress in the right direction.

[davide]

lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

405 ↗

(On Diff #101109)

I can indeed, updating this patch in a sec.

[davide]

Update after Eli's review.

[qcolombet]

test/CodeGen/X86/pr33266.ll

3 ↗

(On Diff #101120)

Could you use a more explicit filename and list the PR within the comment here?

[davide]

test/CodeGen/X86/pr33266.ll

3 ↗

(On Diff #101120)

Done. I used selectiondag-dominator.ll, but if you have other suggestions, I'll be happy to change it.

[davide]

Quentin's comment.

[qcolombet]

LGTM.

[davide]

Thank you for the reviews. Submitting in a sec.

llvm/trunk/lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp

void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
   if (UseMBPI && OptLevel != CodeGenOpt::None)
     AU.addRequired<BranchProbabilityInfoWrapperPass>();
   MachineFunctionPass::getAnalysisUsage(AU);
 }
 
 /// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
 /// may trap on it.  In this case we have to split the edge so that the path
 /// through the predecessor block that doesn't go to the phi block doesn't
-/// execute the possibly trapping instruction.
-///
+/// execute the possibly trapping instruction. If available, we pass a
+/// dominator tree to be updated when we split critical edges. This is because
+/// SelectionDAGISel preserves the DominatorTree.
 /// This is required for correctness, so it must be done at -O0.
 ///
-static void SplitCriticalSideEffectEdges(Function &Fn) {
+static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT) {
   // Loop for blocks with phi nodes.
   for (BasicBlock &BB : Fn) {
     PHINode *PN = dyn_cast<PHINode>(BB.begin());
     if (!PN) continue;
 
   ReprocessBlock:
     // For each block with a PHI node, check to see if any of the input values
     // are potentially trapping constant expressions.  Constant expressions are
for (BasicBlock::iterator I = BB.begin(); (PN = dyn_cast<PHINode>(I)); ++I)
         // edges: check to see if the pred has multiple successors.
         BasicBlock *Pred = PN->getIncomingBlock(i);
         if (Pred->getTerminator()->getNumSuccessors() == 1)
           continue;
 
         // Okay, we have to split this edge.
         SplitCriticalEdge(
             Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
-            CriticalEdgeSplittingOptions().setMergeIdenticalEdges());
+            CriticalEdgeSplittingOptions(DT).setMergeIdenticalEdges());
         goto ReprocessBlock;
       }
   }
 }
 
 bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
   // If we already selected that function, we do not need to run SDISel.
   if (mf.getProperties().hasProperty(
bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
   OptLevelChanger OLC(*this, NewOptLevel);
 
   TII = MF->getSubtarget().getInstrInfo();
   TLI = MF->getSubtarget().getTargetLowering();
   RegInfo = &MF->getRegInfo();
   LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
   GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
   ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
+  auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
 
   DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
 
-  SplitCriticalSideEffectEdges(const_cast<Function &>(Fn));
+  SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT);
 
   CurDAG->init(*MF, *ORE);
   FuncInfo->set(Fn, *MF, CurDAG);
 
   // Now get the optional analyzes if we want to.
   // This is based on the possibly changed OptLevel (after optnone is taken
   // into account).  That's unfortunate but OK because it just means we won't
   // ask for passes that have been required anyway.

llvm/trunk/test/CodeGen/X86/selectiondag-dominator.ll

+; Make sure we don't crash because we have a stale dominator tree.
+; PR33266
+; REQUIRES: asserts
+; RUN: llc -verify-dom-info %s
+
+target triple = "x86_64-unknown-linux-gnu"
+
+@global = external global [8 x [8 x [4 x i8]]], align 2
+@global.1 = external global { i8, [3 x i8] }, align 4
+
+define void @patatino() local_unnamed_addr {
+bb:
+  br label %bb1
+
+bb1:
+  br label %bb2
+
+bb2:
+  br i1 icmp ne (i8* getelementptr inbounds ({ i8, [3 x i8] }, { i8, [3 x i8] }* @global.1, i64 0, i32 0), i8* getelementptr inbounds ([8 x [8 x [4 x i8]]], [8 x [8 x [4 x i8]]]* @global, i64 0, i64 6, i64 6, i64 2)), label %bb4, label %bb3
+
+bb3:
+  br i1 icmp eq (i64 ashr (i64 shl (i64 zext (i32 srem (i32 7, i32 zext (i1 icmp eq (i8* getelementptr inbounds ({ i8, [3 x i8] }, { i8, [3 x i8] }* @global.1, i64 0, i32 0), i8* getelementptr inbounds ([8 x [8 x [4 x i8]]], [8 x [8 x [4 x i8]]]* @global, i64 0, i64 6, i64 6, i64 2)) to i32)) to i64), i64 56), i64 56), i64 0), label %bb5, label %bb4
+
+bb4:
+  %tmp = phi i64 [ ashr (i64 shl (i64 zext (i32 srem (i32 7, i32 zext (i1 icmp eq (i8* getelementptr inbounds ({ i8, [3 x i8] }, { i8, [3 x i8] }* @global.1, i64 0, i32 0), i8* getelementptr inbounds ([8 x [8 x [4 x i8]]], [8 x [8 x [4 x i8]]]* @global, i64 0, i64 6, i64 6, i64 2)) to i32)) to i64), i64 56), i64 56), %bb3 ], [ 7, %bb2 ]
+  ret void
+
+bb5:
+  ret void
+}