195 lines · cpp
1//===- unittests/Analysis/CFGDominatorTree.cpp - CFG tests ----------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9#include "CFGBuildResult.h"10#include "clang/Analysis/Analyses/Dominators.h"11#include "gtest/gtest.h"12 13namespace clang {14namespace analysis {15namespace {16 17TEST(CFGDominatorTree, DomTree) {18 const char *Code = R"(enum Kind {19 A20 };21 22 void f() {23 switch(Kind{}) {24 case A:25 break;26 }27 })";28 BuildResult Result = BuildCFG(Code);29 EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());30 31 // [B3 (ENTRY)] -> [B1] -> [B2] -> [B0 (EXIT)]32 // switch case A33 34 CFG *cfg = Result.getCFG();35 36 // Basic correctness checks.37 EXPECT_EQ(cfg->size(), 4u);38 39 CFGBlock *ExitBlock = *cfg->begin();40 EXPECT_EQ(ExitBlock, &cfg->getExit());41 42 CFGBlock *SwitchBlock = *(cfg->begin() + 1);43 44 CFGBlock *CaseABlock = *(cfg->begin() + 2);45 46 CFGBlock *EntryBlock = *(cfg->begin() + 3);47 EXPECT_EQ(EntryBlock, &cfg->getEntry());48 49 // Test the dominator tree.50 CFGDomTree Dom;51 Dom.buildDominatorTree(cfg);52 53 EXPECT_TRUE(Dom.dominates(ExitBlock, ExitBlock));54 EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));55 EXPECT_TRUE(Dom.dominates(CaseABlock, ExitBlock));56 EXPECT_TRUE(Dom.dominates(SwitchBlock, ExitBlock));57 EXPECT_TRUE(Dom.dominates(EntryBlock, ExitBlock));58 59 EXPECT_TRUE(Dom.dominates(CaseABlock, CaseABlock));60 EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));61 EXPECT_TRUE(Dom.dominates(SwitchBlock, CaseABlock));62 EXPECT_TRUE(Dom.dominates(EntryBlock, CaseABlock));63 64 EXPECT_TRUE(Dom.dominates(SwitchBlock, SwitchBlock));65 EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));66 EXPECT_TRUE(Dom.dominates(EntryBlock, SwitchBlock));67 68 EXPECT_TRUE(Dom.dominates(EntryBlock, EntryBlock));69 EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));70 71 // Test the post dominator tree.72 73 CFGPostDomTree PostDom;74 PostDom.buildDominatorTree(cfg);75 76 EXPECT_TRUE(PostDom.dominates(ExitBlock, EntryBlock));77 EXPECT_TRUE(PostDom.dominates(CaseABlock, EntryBlock));78 EXPECT_TRUE(PostDom.dominates(SwitchBlock, EntryBlock));79 EXPECT_TRUE(PostDom.dominates(EntryBlock, EntryBlock));80 EXPECT_FALSE(Dom.properlyDominates(EntryBlock, EntryBlock));81 82 EXPECT_TRUE(PostDom.dominates(ExitBlock, SwitchBlock));83 EXPECT_TRUE(PostDom.dominates(CaseABlock, SwitchBlock));84 EXPECT_TRUE(PostDom.dominates(SwitchBlock, SwitchBlock));85 EXPECT_FALSE(Dom.properlyDominates(SwitchBlock, SwitchBlock));86 87 EXPECT_TRUE(PostDom.dominates(ExitBlock, CaseABlock));88 EXPECT_TRUE(PostDom.dominates(CaseABlock, CaseABlock));89 EXPECT_FALSE(Dom.properlyDominates(CaseABlock, CaseABlock));90 91 EXPECT_TRUE(PostDom.dominates(ExitBlock, ExitBlock));92 EXPECT_FALSE(Dom.properlyDominates(ExitBlock, ExitBlock));93 94 // Tests for the post dominator tree's virtual root.95 EXPECT_TRUE(PostDom.dominates(nullptr, EntryBlock));96 EXPECT_TRUE(PostDom.dominates(nullptr, SwitchBlock));97 EXPECT_TRUE(PostDom.dominates(nullptr, CaseABlock));98 EXPECT_TRUE(PostDom.dominates(nullptr, ExitBlock));99}100 101TEST(CFGDominatorTree, ControlDependency) {102 const char *Code = R"(bool coin();103 104 void funcWithBranch() {105 int x = 0;106 if (coin()) {107 if (coin()) {108 x = 5;109 }110 int j = 10 / x;111 (void)j;112 }113 };)";114 BuildResult Result = BuildCFG(Code);115 EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());116 117 // 1st if 2nd if118 // [B5 (ENTRY)] -> [B4] -> [B3] -> [B2] -> [B1] -> [B0 (EXIT)]119 // \ \ / /120 // \ -------------> /121 // ------------------------------>122 123 CFG *cfg = Result.getCFG();124 125 // Basic correctness checks.126 EXPECT_EQ(cfg->size(), 6u);127 128 CFGBlock *ExitBlock = *cfg->begin();129 EXPECT_EQ(ExitBlock, &cfg->getExit());130 131 CFGBlock *NullDerefBlock = *(cfg->begin() + 1);132 133 CFGBlock *SecondThenBlock = *(cfg->begin() + 2);134 135 CFGBlock *SecondIfBlock = *(cfg->begin() + 3);136 137 CFGBlock *FirstIfBlock = *(cfg->begin() + 4);138 139 CFGBlock *EntryBlock = *(cfg->begin() + 5);140 EXPECT_EQ(EntryBlock, &cfg->getEntry());141 142 ControlDependencyCalculator Control(cfg);143 144 EXPECT_TRUE(Control.isControlDependent(SecondThenBlock, SecondIfBlock));145 EXPECT_TRUE(Control.isControlDependent(SecondIfBlock, FirstIfBlock));146 EXPECT_FALSE(Control.isControlDependent(NullDerefBlock, SecondIfBlock));147}148 149TEST(CFGDominatorTree, ControlDependencyWithLoops) {150 const char *Code = R"(int test3() {151 int x,y,z;152 153 x = y = z = 1;154 if (x > 0) {155 while (x >= 0){156 while (y >= x) {157 x = x-1;158 y = y/2;159 }160 }161 }162 z = y;163 164 return 0;165 })";166 BuildResult Result = BuildCFG(Code);167 EXPECT_EQ(BuildResult::BuiltCFG, Result.getStatus());168 169 // <- [B2] <-170 // / \171 // [B8 (ENTRY)] -> [B7] -> [B6] ---> [B5] -> [B4] -> [B3]172 // \ | \ /173 // \ | <-------------174 // \ \175 // --------> [B1] -> [B0 (EXIT)]176 177 CFG *cfg = Result.getCFG();178 179 ControlDependencyCalculator Control(cfg);180 181 auto GetBlock = [cfg] (unsigned Index) -> CFGBlock * {182 assert(Index < cfg->size());183 return *(cfg->begin() + Index);184 };185 186 // While not immediately obvious, the second block in fact post dominates the187 // fifth, hence B5 is not a control dependency of 2.188 EXPECT_FALSE(Control.isControlDependent(GetBlock(5), GetBlock(2)));189}190 191 192} // namespace193} // namespace analysis194} // namespace clang195