Index: llvm/include/llvm/Support/GenericDomTreeConstruction.h =================================================================== --- llvm/include/llvm/Support/GenericDomTreeConstruction.h +++ llvm/include/llvm/Support/GenericDomTreeConstruction.h @@ -217,7 +217,8 @@ // edges for postdominators. template unsigned runDFS(NodePtr V, unsigned LastNum, DescendCondition Condition, - unsigned AttachToNum) { + unsigned AttachToNum, + DenseMap *SuccOrder = nullptr) { assert(V); SmallVector WorkList = {V}; if (NodeToInfo.count(V) != 0) NodeToInfo[V].Parent = AttachToNum; @@ -233,8 +234,14 @@ NumToNode.push_back(BB); constexpr bool Direction = IsReverse != IsPostDom; // XOR. - for (const NodePtr Succ : - ChildrenGetter::Get(BB, BatchUpdates)) { + auto Successors = ChildrenGetter::Get(BB, BatchUpdates); + if (SuccOrder && Successors.size() > 1) + std::sort(Successors.begin(), Successors.end(), + [=](NodePtr A, NodePtr B) { + return (*SuccOrder)[A] < (*SuccOrder)[B]; + }); + + for (const NodePtr Succ : Successors) { const auto SIT = NodeToInfo.find(Succ); // Don't visit nodes more than once but remember to collect // ReverseChildren. @@ -430,6 +437,11 @@ // nodes. if (Total + 1 != Num) { HasNonTrivialRoots = true; + + // Used to make the calculation of FurthestAway node immune to swap + // successors transformation. + std::unique_ptr> SuccOrder; + // Make another DFS pass over all other nodes to find the // reverse-unreachable blocks, and find the furthest paths we'll be able // to make. @@ -454,7 +466,17 @@ // expensive and does not always lead to a minimal set of roots. LLVM_DEBUG(dbgs() << "\t\t\tRunning forward DFS\n"); - const unsigned NewNum = SNCA.runDFS(I, Num, AlwaysDescend, Num); + // Lazy creation of SuccOrder, which is the order of blocks in the + // function. This order is insensitive to the order of successors. + // It makes PostDomTree unchanged while changing order of successors + // (e.g. canonicalizing branch predicates). + if (!SuccOrder) { + SuccOrder.reset(new DenseMap()); + for (const auto NodePtr : nodes(DT.Parent)) + SuccOrder->try_emplace(NodePtr, SuccOrder->size()); + } + const unsigned NewNum = + SNCA.runDFS(I, Num, AlwaysDescend, Num, SuccOrder.get()); const NodePtr FurthestAway = SNCA.NumToNode[NewNum]; LLVM_DEBUG(dbgs() << "\t\t\tFound a new furthest away node " << "(non-trivial root): " Index: llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll =================================================================== --- /dev/null +++ llvm/test/Transforms/InstCombine/infinite-loop-postdom.ll @@ -0,0 +1,118 @@ +; RUN: opt %s -disable-output -branch-prob -instcombine -block-freq -verify-dom-info +; RUN: opt %s -postdomtree -analyze | FileCheck --check-prefixes=CHECK-POSTDOM %s +; RUN: opt %s -passes='print' 2>&1 | FileCheck --check-prefixes=CHECK-POSTDOM %s + +; Demonstrate that Predicate Canonicalization (InstCombine) does not invalidate PostDomTree +; if the basic block is post-dom unreachable. + +define void @test1(i24 %a, i24 %b) { +entry: + br label %LOOP + +LOOP: + %f = icmp uge i24 %a, %b + br i1 %f, label %B1, label %B2 + +B1: + %x = add i24 %a, %b + br label %B2 + +B2: + br label %LOOP +} + +; The same as @test1 except the LOOP condition canonicalized (as by instcombine). +define void @test1-canonicalized(i24 %a, i24 %b) { +entry: + br label %LOOP + +LOOP: + %f.not = icmp ult i24 %a, %b + br i1 %f.not, label %B2, label %B1 + +B1: + %x = add i24 %a, %b + br label %B2 + +B2: + br label %LOOP +} + +; The same as @test2 but different order of B1 and B2 in the function. +; The different order makes PostDomTree different in presense of postdom +; unreachable blocks. +define void @test2(i24 %a, i24 %b) { +entry: + br label %LOOP + +LOOP: + %f = icmp uge i24 %a, %b + br i1 %f, label %B1, label %B2 + +B2: + br label %LOOP + +B1: + %x = add i24 %a, %b + br label %B2 +} + +; The same as @test2 except the LOOP condition canonicalized (as by instcombine). +define void @test2-canonicalized(i24 %a, i24 %b) { +entry: + br label %LOOP + +LOOP: + %f.not = icmp ult i24 %a, %b + br i1 %f.not, label %B2, label %B1 + +B2: + br label %LOOP + +B1: + %x = add i24 %a, %b + br label %B2 +} + +; PostDomTrees of @test1() and @test2() are different. +; PostDomTrees of @testX() and @testX-canonicalize() are the same. + +; CHECK-POSTDOM-LABEL: test1 +; CHECK-POSTDOM-NEXT: =============================-------------------------------- +; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries. +; CHECK-POSTDOM-NEXT: [1] <> +; CHECK-POSTDOM-NEXT: [2] %B1 +; CHECK-POSTDOM-NEXT: [3] %LOOP +; CHECK-POSTDOM-NEXT: [4] %entry +; CHECK-POSTDOM-NEXT: [4] %B2 +; CHECK-POSTDOM-NEXT: Roots: %B1 + +; CHECK-POSTDOM-LABEL: test1-canonicalized +; CHECK-POSTDOM-NEXT: =============================-------------------------------- +; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries. +; CHECK-POSTDOM-NEXT: [1] <> +; CHECK-POSTDOM-NEXT: [2] %B1 +; CHECK-POSTDOM-NEXT: [3] %LOOP +; CHECK-POSTDOM-NEXT: [4] %entry +; CHECK-POSTDOM-NEXT: [4] %B2 +; CHECK-POSTDOM-NEXT: Roots: %B1 + +; CHECK-POSTDOM-LABEL: test2 +; CHECK-POSTDOM-NEXT: =============================-------------------------------- +; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries. +; CHECK-POSTDOM-NEXT: [1] <> +; CHECK-POSTDOM-NEXT: [2] %B2 +; CHECK-POSTDOM-NEXT: [3] %LOOP +; CHECK-POSTDOM-NEXT: [4] %entry +; CHECK-POSTDOM-NEXT: [3] %B1 +; CHECK-POSTDOM-NEXT: Roots: %B2 + +; CHECK-POSTDOM-LABEL: test2-canonicalized +; CHECK-POSTDOM-NEXT: =============================-------------------------------- +; CHECK-POSTDOM-NEXT: Inorder PostDominator Tree: DFSNumbers invalid: 0 slow queries. +; CHECK-POSTDOM-NEXT: [1] <> +; CHECK-POSTDOM-NEXT: [2] %B2 +; CHECK-POSTDOM-NEXT: [3] %LOOP +; CHECK-POSTDOM-NEXT: [4] %entry +; CHECK-POSTDOM-NEXT: [3] %B1 +; CHECK-POSTDOM-NEXT: Roots: %B2