Skip to content

Commit fb4d5c0

Browse files
committedJun 5, 2017
[SelectionDAG] Update the dominator after splitting critical edges.
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. Differential Revision: https://reviews.llvm.org/D33800 llvm-svn: 304742
1 parent 88101da commit fb4d5c0

File tree

2 files changed

+38
-5
lines changed

2 files changed

+38
-5
lines changed
 

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

+8-5
Original file line numberDiff line numberDiff line change
@@ -333,11 +333,12 @@ void SelectionDAGISel::getAnalysisUsage(AnalysisUsage &AU) const {
333333
/// SplitCriticalSideEffectEdges - Look for critical edges with a PHI value that
334334
/// may trap on it. In this case we have to split the edge so that the path
335335
/// through the predecessor block that doesn't go to the phi block doesn't
336-
/// execute the possibly trapping instruction.
337-
///
336+
/// execute the possibly trapping instruction. If available, we pass a
337+
/// dominator tree to be updated when we split critical edges. This is because
338+
/// SelectionDAGISel preserves the DominatorTree.
338339
/// This is required for correctness, so it must be done at -O0.
339340
///
340-
static void SplitCriticalSideEffectEdges(Function &Fn) {
341+
static void SplitCriticalSideEffectEdges(Function &Fn, DominatorTree *DT) {
341342
// Loop for blocks with phi nodes.
342343
for (BasicBlock &BB : Fn) {
343344
PHINode *PN = dyn_cast<PHINode>(BB.begin());
@@ -363,7 +364,7 @@ static void SplitCriticalSideEffectEdges(Function &Fn) {
363364
// Okay, we have to split this edge.
364365
SplitCriticalEdge(
365366
Pred->getTerminator(), GetSuccessorNumber(Pred, &BB),
366-
CriticalEdgeSplittingOptions().setMergeIdenticalEdges());
367+
CriticalEdgeSplittingOptions(DT).setMergeIdenticalEdges());
367368
goto ReprocessBlock;
368369
}
369370
}
@@ -399,10 +400,12 @@ bool SelectionDAGISel::runOnMachineFunction(MachineFunction &mf) {
399400
LibInfo = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
400401
GFI = Fn.hasGC() ? &getAnalysis<GCModuleInfo>().getFunctionInfo(Fn) : nullptr;
401402
ORE = make_unique<OptimizationRemarkEmitter>(&Fn);
403+
auto *DTWP = getAnalysisIfAvailable<DominatorTreeWrapperPass>();
404+
DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr;
402405

403406
DEBUG(dbgs() << "\n\n\n=== " << Fn.getName() << "\n");
404407

405-
SplitCriticalSideEffectEdges(const_cast<Function &>(Fn));
408+
SplitCriticalSideEffectEdges(const_cast<Function &>(Fn), DT);
406409

407410
CurDAG->init(*MF, *ORE);
408411
FuncInfo->set(Fn, *MF, CurDAG);
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
; Make sure we don't crash because we have a stale dominator tree.
2+
; PR33266
3+
; REQUIRES: asserts
4+
; RUN: llc -verify-dom-info %s
5+
6+
target triple = "x86_64-unknown-linux-gnu"
7+
8+
@global = external global [8 x [8 x [4 x i8]]], align 2
9+
@global.1 = external global { i8, [3 x i8] }, align 4
10+
11+
define void @patatino() local_unnamed_addr {
12+
bb:
13+
br label %bb1
14+
15+
bb1:
16+
br label %bb2
17+
18+
bb2:
19+
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
20+
21+
bb3:
22+
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
23+
24+
bb4:
25+
%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 ]
26+
ret void
27+
28+
bb5:
29+
ret void
30+
}

0 commit comments

Comments
 (0)
Please sign in to comment.