llvm/llvm/unittests/IR/DominatorTreeTest.cpp

//===- llvm/unittests/IR/DominatorTreeTest.cpp - Constants unit tests -----===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//

#include <random>
#include "llvm/Analysis/PostDominators.h"
#include "llvm/Analysis/IteratedDominanceFrontier.h"
#include "llvm/AsmParser/Parser.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Dominators.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Module.h"
#include "llvm/Support/SourceMgr.h"
#include "CFGBuilder.h"
#include "gtest/gtest.h"

usingnamespacellvm;


/// Build the dominator tree for the function and run the Test.
static void runWithDomTree(
    Module &M, StringRef FuncName,
    function_ref<void(Function &F, DominatorTree *DT, PostDominatorTree *PDT)>
        Test) { … }

static std::unique_ptr<Module> makeLLVMModule(LLVMContext &Context,
                                              StringRef ModuleStr) { … }

TEST(DominatorTree, PHIs) { … }

TEST(DominatorTree, Unreachable) { … }

TEST(DominatorTree, NonUniqueEdges) { … }

// Verify that the PDT is correctly updated in case an edge removal results
// in a new unreachable CFG node. Also make sure that the updated PDT is the
// same as a freshly recalculated one.
//
// For the following input code and initial PDT:
//
//          CFG                   PDT
//
//           A                    Exit
//           |                     |
//          _B                     D
//         / | \                   |
//        ^  v  \                  B
//        \ /    D                / \
//         C      \              C   A
//                v
//                Exit
//
// we verify that CFG' and PDT-updated is obtained after removal of edge C -> B.
//
//          CFG'               PDT-updated
//
//           A                    Exit
//           |                   / | \
//           B                  C  B  D
//           | \                   |
//           v  \                  A
//          /    D
//         C      \
//         |       \
// unreachable    Exit
//
// Both the blocks that end with ret and with unreachable become trivial
// PostDominatorTree roots, as they have no successors.
//
TEST(DominatorTree, DeletingEdgesIntroducesUnreachables) { … }

// Verify that the PDT is correctly updated in case an edge removal results
// in an infinite loop. Also make sure that the updated PDT is the
// same as a freshly recalculated one.
//
// Test case:
//
//          CFG                   PDT
//
//           A                    Exit
//           |                     |
//          _B                     D
//         / | \                   |
//        ^  v  \                  B
//        \ /    D                / \
//         C      \              C   A
//        / \      v
//       ^  v      Exit
//        \_/
//
// After deleting the edge C->B, C is part of an infinite reverse-unreachable
// loop:
//
//          CFG'                  PDT'
//
//           A                    Exit
//           |                   / | \
//           B                  C  B  D
//           | \                   |
//           v  \                  A
//          /    D
//         C      \
//        / \      v
//       ^  v      Exit
//        \_/
//
// As C now becomes reverse-unreachable, it forms a new non-trivial root and
// gets connected to the virtual exit.
// D does not postdominate B anymore, because there are two forward paths from
// B to the virtual exit:
//  - B -> C -> VirtualExit
//  - B -> D -> VirtualExit.
//
TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop) { … }

// Verify that the PDT is correctly updated in case an edge removal results
// in an infinite loop.
//
// Test case:
//
//          CFG                   PDT
//
//           A                    Exit
//           |                   / | \
//           B--               C2  B  D
//           |  \              /   |
//           v   \            C    A
//          /     D
//         C--C2   \
//        / \  \    v
//       ^  v  --Exit
//        \_/
//
// After deleting the edge C->E, C is part of an infinite reverse-unreachable
// loop:
//
//          CFG'                  PDT'
//
//           A                    Exit
//           |                   / | \
//           B                  C  B  D
//           | \                   |
//           v  \                  A
//          /    D
//         C      \
//        / \      v
//       ^  v      Exit
//        \_/
//
// In PDT, D does not post-dominate B. After the edge C -> C2 is removed,
// C becomes a new nontrivial PDT root.
//
TEST(DominatorTree, DeletingEdgesIntroducesInfiniteLoop2) { … }

// Verify that the IDF returns blocks in a deterministic way.
//
// Test case:
//
//          CFG
//
//          (A)
//          / \
//         /   \
//       (B)   (C)
//        |\   /|
//        |  X  |
//        |/   \|
//       (D)   (E)
//
// IDF for block B is {D, E}, and the order of blocks in this list is defined by
// their 1) level in dom-tree and 2) DFSIn number if the level is the same.
//
TEST(DominatorTree, IDFDeterminismTest) { … }

namespace {
const auto Insert = …;
const auto Delete = …;

bool CompUpdates(const CFGBuilder::Update &A, const CFGBuilder::Update &B) { … }
}  // namespace

TEST(DominatorTree, InsertReachable) { … }

TEST(DominatorTree, InsertReachable2) { … }

TEST(DominatorTree, InsertUnreachable) { … }

TEST(DominatorTree, InsertFromUnreachable) { … }

TEST(DominatorTree, InsertMixed) { … }

TEST(DominatorTree, InsertPermut) { … }

TEST(DominatorTree, DeleteReachable) { … }

TEST(DominatorTree, DeleteUnreachable) { … }

TEST(DominatorTree, InsertDelete) { … }

TEST(DominatorTree, InsertDeleteExhaustive) { … }

TEST(DominatorTree, InsertIntoIrreducible) { … }

TEST(DominatorTree, EdgeDomination) { … }

TEST(DominatorTree, ValueDomination) { … }
TEST(DominatorTree, CallBrDomination) { … }