351 lines · cpp
1//===- llvm/unittests/IR/DominatorTreeBatchUpdatesTest.cpp ----------------===//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 "CFGBuilder.h"10#include "llvm/Analysis/PostDominators.h"11#include "llvm/IR/Dominators.h"12#include "llvm/Support/GenericDomTreeConstruction.h"13#include "gtest/gtest.h"14#include <random>15 16#define DEBUG_TYPE "batch-update-tests"17 18using namespace llvm;19 20namespace {21const auto CFGInsert = CFGBuilder::ActionKind::Insert;22const auto CFGDelete = CFGBuilder::ActionKind::Delete;23 24using DomUpdate = DominatorTree::UpdateType;25static_assert(26 std::is_same_v<DomUpdate, PostDominatorTree::UpdateType>,27 "Trees differing only in IsPostDom should have the same update types");28using DomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBDomTree>;29using PostDomSNCA = DomTreeBuilder::SemiNCAInfo<DomTreeBuilder::BBPostDomTree>;30const auto Insert = DominatorTree::Insert;31const auto Delete = DominatorTree::Delete;32 33std::vector<DomUpdate> ToDomUpdates(CFGBuilder &B,34 std::vector<CFGBuilder::Update> &In) {35 std::vector<DomUpdate> Res;36 Res.reserve(In.size());37 38 for (const auto &CFGU : In)39 Res.push_back({CFGU.Action == CFGInsert ? Insert : Delete,40 B.getOrAddBlock(CFGU.Edge.From),41 B.getOrAddBlock(CFGU.Edge.To)});42 return Res;43}44} // namespace45 46TEST(DominatorTreeBatchUpdates, LegalizeDomUpdates) {47 CFGHolder Holder;48 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});49 50 BasicBlock *A = Builder.getOrAddBlock("A");51 BasicBlock *B = Builder.getOrAddBlock("B");52 BasicBlock *C = Builder.getOrAddBlock("C");53 BasicBlock *D = Builder.getOrAddBlock("D");54 55 std::vector<DomUpdate> Updates = {56 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},57 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};58 SmallVector<DomUpdate, 4> Legalized;59 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, false);60 LLVM_DEBUG(dbgs() << "Legalized updates:\t");61 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });62 LLVM_DEBUG(dbgs() << "\n");63 EXPECT_EQ(Legalized.size(), 3UL);64 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, C}));65 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, B, D}));66 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, A, B}));67}68 69TEST(DominatorTreeBatchUpdates, LegalizePostDomUpdates) {70 CFGHolder Holder;71 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {});72 73 BasicBlock *A = Builder.getOrAddBlock("A");74 BasicBlock *B = Builder.getOrAddBlock("B");75 BasicBlock *C = Builder.getOrAddBlock("C");76 BasicBlock *D = Builder.getOrAddBlock("D");77 78 std::vector<DomUpdate> Updates = {79 {Insert, B, C}, {Insert, C, D}, {Delete, B, C}, {Insert, B, C},80 {Insert, B, D}, {Delete, C, D}, {Delete, A, B}};81 SmallVector<DomUpdate, 4> Legalized;82 cfg::LegalizeUpdates<BasicBlock *>(Updates, Legalized, true);83 LLVM_DEBUG(dbgs() << "Legalized postdom updates:\t");84 LLVM_DEBUG(for (auto &U : Legalized) { U.dump(); dbgs() << ", "; });85 LLVM_DEBUG(dbgs() << "\n");86 EXPECT_EQ(Legalized.size(), 3UL);87 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, C, B}));88 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Insert, D, B}));89 EXPECT_TRUE(llvm::is_contained(Legalized, DomUpdate{Delete, B, A}));90}91 92TEST(DominatorTreeBatchUpdates, SingleInsertion) {93 CFGHolder Holder;94 CFGBuilder Builder(Holder.F, {{"A", "B"}}, {{CFGInsert, {"B", "C"}}});95 96 DominatorTree DT(*Holder.F);97 EXPECT_TRUE(DT.verify());98 PostDominatorTree PDT(*Holder.F);99 EXPECT_TRUE(PDT.verify());100 101 BasicBlock *B = Builder.getOrAddBlock("B");102 BasicBlock *C = Builder.getOrAddBlock("C");103 std::vector<DomUpdate> Updates = {{Insert, B, C}};104 105 ASSERT_TRUE(Builder.applyUpdate());106 107 DT.applyUpdates(Updates);108 EXPECT_TRUE(DT.verify());109 PDT.applyUpdates(Updates);110 EXPECT_TRUE(PDT.verify());111}112 113TEST(DominatorTreeBatchUpdates, SingleDeletion) {114 CFGHolder Holder;115 CFGBuilder Builder(Holder.F, {{"A", "B"}, {"B", "C"}},116 {{CFGDelete, {"B", "C"}}});117 118 DominatorTree DT(*Holder.F);119 EXPECT_TRUE(DT.verify());120 PostDominatorTree PDT(*Holder.F);121 EXPECT_TRUE(PDT.verify());122 123 BasicBlock *B = Builder.getOrAddBlock("B");124 BasicBlock *C = Builder.getOrAddBlock("C");125 std::vector<DomUpdate> Updates = {{Delete, B, C}};126 127 ASSERT_TRUE(Builder.applyUpdate());128 129 DT.applyUpdates(Updates);130 EXPECT_TRUE(DT.verify());131 PDT.applyUpdates(Updates);132 EXPECT_TRUE(PDT.verify());133}134 135TEST(DominatorTreeBatchUpdates, FewInsertion) {136 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGInsert, {"B", "C"}},137 {CFGInsert, {"C", "B"}},138 {CFGInsert, {"C", "D"}},139 {CFGInsert, {"D", "E"}}};140 141 CFGHolder Holder;142 CFGBuilder Builder(Holder.F, {{"A", "B"}}, CFGUpdates);143 144 DominatorTree DT(*Holder.F);145 EXPECT_TRUE(DT.verify());146 PostDominatorTree PDT(*Holder.F);147 EXPECT_TRUE(PDT.verify());148 149 BasicBlock *B = Builder.getOrAddBlock("B");150 BasicBlock *C = Builder.getOrAddBlock("C");151 BasicBlock *D = Builder.getOrAddBlock("D");152 BasicBlock *E = Builder.getOrAddBlock("E");153 154 std::vector<DomUpdate> Updates = {155 {Insert, B, C}, {Insert, C, B}, {Insert, C, D}, {Insert, D, E}};156 157 while (Builder.applyUpdate())158 ;159 160 DT.applyUpdates(Updates);161 EXPECT_TRUE(DT.verify());162 PDT.applyUpdates(Updates);163 EXPECT_TRUE(PDT.verify());164}165 166TEST(DominatorTreeBatchUpdates, FewDeletions) {167 std::vector<CFGBuilder::Update> CFGUpdates = {{CFGDelete, {"B", "C"}},168 {CFGDelete, {"C", "B"}},169 {CFGDelete, {"B", "D"}},170 {CFGDelete, {"D", "E"}}};171 172 CFGHolder Holder;173 CFGBuilder Builder(174 Holder.F, {{"A", "B"}, {"B", "C"}, {"B", "D"}, {"D", "E"}, {"C", "B"}},175 CFGUpdates);176 177 DominatorTree DT(*Holder.F);178 EXPECT_TRUE(DT.verify());179 PostDominatorTree PDT(*Holder.F);180 EXPECT_TRUE(PDT.verify());181 182 auto Updates = ToDomUpdates(Builder, CFGUpdates);183 184 while (Builder.applyUpdate())185 ;186 187 DT.applyUpdates(Updates);188 EXPECT_TRUE(DT.verify());189 PDT.applyUpdates(Updates);190 EXPECT_TRUE(PDT.verify());191}192 193TEST(DominatorTreeBatchUpdates, InsertDelete) {194 std::vector<CFGBuilder::Arc> Arcs = {195 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},196 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};197 198 std::vector<CFGBuilder::Update> Updates = {199 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},200 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},201 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},202 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},203 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},204 {CFGDelete, {"11", "12"}}};205 206 CFGHolder Holder;207 CFGBuilder B(Holder.F, Arcs, Updates);208 DominatorTree DT(*Holder.F);209 EXPECT_TRUE(DT.verify());210 PostDominatorTree PDT(*Holder.F);211 EXPECT_TRUE(PDT.verify());212 213 while (B.applyUpdate())214 ;215 216 auto DomUpdates = ToDomUpdates(B, Updates);217 DT.applyUpdates(DomUpdates);218 EXPECT_TRUE(DT.verify());219 PDT.applyUpdates(DomUpdates);220 EXPECT_TRUE(PDT.verify());221}222 223TEST(DominatorTreeBatchUpdates, InsertDeleteExhaustive) {224 std::vector<CFGBuilder::Arc> Arcs = {225 {"1", "2"}, {"2", "3"}, {"3", "4"}, {"4", "5"}, {"5", "6"}, {"5", "7"},226 {"3", "8"}, {"8", "9"}, {"9", "10"}, {"8", "11"}, {"11", "12"}};227 228 std::vector<CFGBuilder::Update> Updates = {229 {CFGInsert, {"2", "4"}}, {CFGInsert, {"12", "10"}},230 {CFGInsert, {"10", "9"}}, {CFGInsert, {"7", "6"}},231 {CFGInsert, {"7", "5"}}, {CFGDelete, {"3", "8"}},232 {CFGInsert, {"10", "7"}}, {CFGInsert, {"2", "8"}},233 {CFGDelete, {"3", "4"}}, {CFGDelete, {"8", "9"}},234 {CFGDelete, {"11", "12"}}};235 236 std::mt19937 Generator(0);237 for (unsigned i = 0; i < 16; ++i) {238 std::shuffle(Updates.begin(), Updates.end(), Generator);239 CFGHolder Holder;240 CFGBuilder B(Holder.F, Arcs, Updates);241 DominatorTree DT(*Holder.F);242 EXPECT_TRUE(DT.verify());243 PostDominatorTree PDT(*Holder.F);244 EXPECT_TRUE(PDT.verify());245 246 while (B.applyUpdate())247 ;248 249 auto DomUpdates = ToDomUpdates(B, Updates);250 DT.applyUpdates(DomUpdates);251 EXPECT_TRUE(DT.verify());252 PDT.applyUpdates(DomUpdates);253 EXPECT_TRUE(PDT.verify());254 }255}256 257// These are some odd flowgraphs, usually generated from csmith cases,258// which are difficult on post dom trees.259TEST(DominatorTreeBatchUpdates, InfiniteLoop) {260 std::vector<CFGBuilder::Arc> Arcs = {261 {"1", "2"},262 {"2", "3"},263 {"3", "6"}, {"3", "5"},264 {"4", "5"},265 {"5", "2"},266 {"6", "3"}, {"6", "4"}};267 268 // SplitBlock on 3 -> 5269 std::vector<CFGBuilder::Update> Updates = {270 {CFGInsert, {"N", "5"}}, {CFGInsert, {"3", "N"}}, {CFGDelete, {"3", "5"}}};271 272 CFGHolder Holder;273 CFGBuilder B(Holder.F, Arcs, Updates);274 DominatorTree DT(*Holder.F);275 EXPECT_TRUE(DT.verify());276 PostDominatorTree PDT(*Holder.F);277 EXPECT_TRUE(PDT.verify());278 279 while (B.applyUpdate())280 ;281 282 auto DomUpdates = ToDomUpdates(B, Updates);283 DT.applyUpdates(DomUpdates);284 EXPECT_TRUE(DT.verify());285 PDT.applyUpdates(DomUpdates);286 EXPECT_TRUE(PDT.verify());287}288 289TEST(DominatorTreeBatchUpdates, DeadBlocks) {290 std::vector<CFGBuilder::Arc> Arcs = {291 {"1", "2"},292 {"2", "3"},293 {"3", "4"}, {"3", "7"},294 {"4", "4"},295 {"5", "6"}, {"5", "7"},296 {"6", "7"},297 {"7", "2"}, {"7", "8"}};298 299 // Remove dead 5 and 7,300 // plus SplitBlock on 7 -> 8301 std::vector<CFGBuilder::Update> Updates = {302 {CFGDelete, {"6", "7"}}, {CFGDelete, {"5", "7"}}, {CFGDelete, {"5", "6"}},303 {CFGInsert, {"N", "8"}}, {CFGInsert, {"7", "N"}}, {CFGDelete, {"7", "8"}}};304 305 CFGHolder Holder;306 CFGBuilder B(Holder.F, Arcs, Updates);307 DominatorTree DT(*Holder.F);308 EXPECT_TRUE(DT.verify());309 PostDominatorTree PDT(*Holder.F);310 EXPECT_TRUE(PDT.verify());311 312 while (B.applyUpdate())313 ;314 315 auto DomUpdates = ToDomUpdates(B, Updates);316 DT.applyUpdates(DomUpdates);317 EXPECT_TRUE(DT.verify());318 PDT.applyUpdates(DomUpdates);319 EXPECT_TRUE(PDT.verify());320}321 322TEST(DominatorTreeBatchUpdates, InfiniteLoop2) {323 std::vector<CFGBuilder::Arc> Arcs = {324 {"1", "2"},325 {"2", "6"}, {"2", "3"},326 {"3", "4"},327 {"4", "5"}, {"4", "6"},328 {"5", "4"},329 {"6", "2"}};330 331 // SplitBlock on 4 -> 6332 std::vector<CFGBuilder::Update> Updates = {333 {CFGInsert, {"N", "6"}}, {CFGInsert, {"4", "N"}}, {CFGDelete, {"4", "6"}}};334 335 CFGHolder Holder;336 CFGBuilder B(Holder.F, Arcs, Updates);337 DominatorTree DT(*Holder.F);338 EXPECT_TRUE(DT.verify());339 PostDominatorTree PDT(*Holder.F);340 EXPECT_TRUE(PDT.verify());341 342 while (B.applyUpdate())343 ;344 345 auto DomUpdates = ToDomUpdates(B, Updates);346 DT.applyUpdates(DomUpdates);347 EXPECT_TRUE(DT.verify());348 PDT.applyUpdates(DomUpdates);349 EXPECT_TRUE(PDT.verify());350}351