Index: include/llvm/IR/Dominators.h =================================================================== --- include/llvm/IR/Dominators.h +++ include/llvm/IR/Dominators.h @@ -23,6 +23,7 @@ #include "llvm/IR/BasicBlock.h" #include "llvm/IR/CFG.h" #include "llvm/IR/Function.h" +#include "llvm/IR/Instructions.h" #include "llvm/Pass.h" #include "llvm/Support/Compiler.h" #include "llvm/Support/GenericDomTree.h" @@ -62,6 +63,64 @@ bool isSingleEdge() const; }; +/// Is a node the exit node of a graph as needed for dominator tree calculation. +/// +/// All basic blocks that have no successors are exit nodes of the graph, except +/// the ones that terminate with an UnreachableInst. Not including unreachable +/// instructions allows us to treat unreachable basic blocks like infinite +/// loops. This means unreachable parts of the CFG will not be visible in the +/// post-dominator tree and - more importantly - will not affect the other parts +/// of the post-dominator tree. If we would model unreachable basic blocks as +/// exit blocks of the CFG the post-dominator tree would be flattened out and +/// we would miss important post-dominance relations. +/// +/// +/// CFG +/// === +/// | +/// bb1 +/// / \ +/// bb2 ^ +/// / \ / +/// unreachable bb3 +/// | +/// exit +/// +/// +/// Post dominator tree with unreachable nodes as exit node +/// ======================================================= +/// +/// virtual root +/// / | \ +/// unreachable exit bb2 +/// | | +/// bb3 bb1 +/// +/// Post dominator tree without unreachable nodes as exit node +/// ========================================================== +/// +/// virtual root +/// | +/// exit +/// | +/// bb3 +/// | +/// bb2 +/// | +/// bb1 +/// +/// When ignoring unreachables we can now correctly determine that bb2 is +/// post-dominated by bb3. +template <> +inline bool isDomTreeExit>( + typename GraphTraits::NodeType *N) { + if (GraphTraits::child_begin(N) != + GraphTraits::child_end(N)) + return false; + + return !isa(N->getTerminator()); +} + /// \brief Concrete subclass of DominatorTreeBase that is used to compute a /// normal dominator tree. class DominatorTree : public DominatorTreeBase { Index: include/llvm/Support/GenericDomTree.h =================================================================== --- include/llvm/Support/GenericDomTree.h +++ include/llvm/Support/GenericDomTree.h @@ -62,6 +62,19 @@ bool isPostDominator() const { return IsPostDominators; } }; +/// Is a node the exit node of a graph as needed for dominator tree calculation. +/// +/// By default we just assume that each node that does not have a successor +/// is an exit node of the graph. However, specializations of the dominator +/// tree for specific graph types can overwrite this function in case more +/// detailed information is available. E.g. one may ignore unreachable +/// instructions, which have no successors but also do not return from the +/// function. +template +bool isDomTreeExit(typename GraphTy::NodeType *N) { + return GraphTy::child_begin(N) == GraphTy::child_end(N); +} + template class DominatorTreeBase; struct PostDominatorTree; @@ -732,7 +745,7 @@ for (typename TraitsTy::nodes_iterator I = TraitsTy::nodes_begin(&F), E = TraitsTy::nodes_end(&F); I != E; ++I) { - if (TraitsTy::child_begin(I) == TraitsTy::child_end(I)) + if (isDomTreeExit(I)) addRoot(I); // Prepopulate maps so that we don't get iterator invalidation issues Index: test/Analysis/PostDominators/unreachables.ll =================================================================== --- /dev/null +++ test/Analysis/PostDominators/unreachables.ll @@ -0,0 +1,34 @@ +; RUN: opt -regions -analyze < %s | FileCheck %s + +; Make sure we do _not_ add the unreachable node to the root nodes of the post +; dominator tree, as otherwise the post-dominator tree would flatten out and +; loose its structure. Instead, unreachable branches are just ignored in +; the post-dominator tree the same way infinite loops are left out. + +; CHECK: Inorder PostDominator Tree: +; CHECK: [1] <> {0,11} +; CHECK: [2] %exit {1,10} +; CHECK: [3] %loop.backedge {2,9} +; CHECK: [4] %loop.next {3,8} +; CHECK: [5] %loop {4,7} +; CHECK: [6] %entry {5,6} + +define void @foo.bar() { +entry: + br label %loop + +loop: + br label %loop.next + +loop.next: + br i1 false, label %loop.backedge, label %loop.unreachable + +loop.unreachable: + unreachable + +loop.backedge: + br i1 false, label %loop, label %exit + +exit: + ret void +} Index: test/Analysis/RegionInfo/condition_complicated_2.ll =================================================================== --- test/Analysis/RegionInfo/condition_complicated_2.ll +++ test/Analysis/RegionInfo/condition_complicated_2.ll @@ -23,12 +23,10 @@ end172: br label %exit - exit: - unreachable - - + ret void } + ; CHECK-NOT: => ; CHECK: [0] end33 => ; CHECK-NEXT: [1] end33 => exit Index: test/Analysis/RegionInfo/unreachable_bb.ll =================================================================== --- test/Analysis/RegionInfo/unreachable_bb.ll +++ test/Analysis/RegionInfo/unreachable_bb.ll @@ -1,29 +1,26 @@ ; RUN: opt -regions -analyze < %s | FileCheck %s -; We should not crash if there are some bbs that are not reachable. -define void @f() { +; CHECK: Region tree: +; CHECK: [0] entry => +; CHECK: [1] loop => exit +; CHECK: [2] loop.next => loop.backedge + +define void @foo.bar() { entry: - br label %for.pre + br label %loop -notintree: ; No predecessors! - br label %ret +loop: + br label %loop.next -for.pre: ; preds = %entry - br label %for +loop.next: + br i1 false, label %loop.backedge, label %loop.unreachable -for: ; preds = %for.inc, %for.pre - %indvar = phi i64 [ 0, %for.pre ], [ %indvar.next, %for.inc ] - %exitcond = icmp ne i64 %indvar, 200 - br i1 %exitcond, label %for.inc, label %ret +loop.unreachable: + unreachable -for.inc: ; preds = %for - %indvar.next = add i64 %indvar, 1 - br label %for +loop.backedge: + br i1 false, label %loop, label %exit -ret: ; preds = %for, %notintree +exit: ret void } - -; CHECK: [0] entry => -; CHECK: [1] for => ret -