From c1b825d4b8a68178613972a50088b2b73105e91e Mon Sep 17 00:00:00 2001 From: Roman Lebedev Date: Thu, 31 Dec 2020 20:13:30 +0300 Subject: [PATCH] [SimplifyCFG] Teach FoldValueComparisonIntoPredecessors() to preserve DomTree, part 1 --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp | 20 ++++++++++++++++++-- llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll | 4 ++-- llvm/test/Transforms/JumpThreading/lvi-tristate.ll | 2 +- .../SimplifyCFG/2005-08-01-PHIUpdateFail.ll | 2 +- llvm/test/Transforms/SimplifyCFG/2006-08-03-Crash.ll | 2 +- .../SimplifyCFG/ARM/switch-to-lookup-table.ll | 10 +++++----- llvm/test/Transforms/SimplifyCFG/DeadSetCC.ll | 2 +- llvm/test/Transforms/SimplifyCFG/X86/MagicPointer.ll | 2 +- .../SimplifyCFG/preserve-branchweights-partial.ll | 4 ++-- .../preserve-branchweights-switch-create.ll | 2 +- 10 files changed, 33 insertions(+), 17 deletions(-) diff --git a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp index 7e49d3a..f1e6c50 100644 --- a/llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -1088,11 +1088,14 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(Instruction *TI, SmallSetVector FailBlocks; if (!SafeToMergeTerminators(TI, PTI, &FailBlocks)) { for (auto *Succ : FailBlocks) { - if (!SplitBlockPredecessors(Succ, TI->getParent(), ".fold.split")) + if (!SplitBlockPredecessors(Succ, TI->getParent(), ".fold.split", + DTU ? &DTU->getDomTree() : nullptr)) return false; } } + std::vector Updates; + // Figure out which 'cases' to copy from SI to PSI. std::vector BBCases; BasicBlock *BBDefault = GetValueEqualityComparisonCases(TI, BBCases); @@ -1156,6 +1159,7 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(Instruction *TI, // Reconstruct the new switch statement we will be building. if (PredDefault != BBDefault) { PredDefault->removePredecessor(Pred); + Updates.push_back({DominatorTree::Delete, Pred, PredDefault}); PredDefault = BBDefault; NewSuccessors.push_back(BBDefault); } @@ -1232,8 +1236,10 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(Instruction *TI, // Okay, at this point, we know which new successor Pred will get. Make // sure we update the number of entries in the PHI nodes for these // successors. - for (BasicBlock *NewSuccessor : NewSuccessors) + for (BasicBlock *NewSuccessor : NewSuccessors) { AddPredecessorToBlock(NewSuccessor, Pred, BB); + Updates.push_back({DominatorTree::Insert, Pred, NewSuccessor}); + } Builder.SetInsertPoint(PTI); // Convert pointer to int before we switch. @@ -1272,10 +1278,20 @@ bool SimplifyCFGOpt::FoldValueComparisonIntoPredecessors(Instruction *TI, InfLoopBlock = BasicBlock::Create(BB->getContext(), "infloop", BB->getParent()); BranchInst::Create(InfLoopBlock, InfLoopBlock); + Updates.push_back( + {DominatorTree::Insert, InfLoopBlock, InfLoopBlock}); } NewSI->setSuccessor(i, InfLoopBlock); } + if (InfLoopBlock) { + Updates.push_back({DominatorTree::Delete, Pred, BB}); + Updates.push_back({DominatorTree::Insert, Pred, InfLoopBlock}); + } + + if (DTU) + DTU->applyUpdatesPermissive(Updates); + Changed = true; } } diff --git a/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll b/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll index 018eb79..1175288 100644 --- a/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll +++ b/llvm/test/Transforms/ADCE/domtree-DoubleDeletion.ll @@ -1,5 +1,5 @@ -; RUN: opt < %s -gvn -simplifycfg -adce | llvm-dis -; RUN: opt < %s -gvn -simplifycfg -adce -verify-dom-info | llvm-dis +; RUN: opt < %s -gvn -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -adce | llvm-dis +; RUN: opt < %s -gvn -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -adce -verify-dom-info | llvm-dis ; This test makes sure that the DominatorTree properly handles ; deletion of edges that go to forward-unreachable regions. diff --git a/llvm/test/Transforms/JumpThreading/lvi-tristate.ll b/llvm/test/Transforms/JumpThreading/lvi-tristate.ll index 94fd0e5..ee01400 100644 --- a/llvm/test/Transforms/JumpThreading/lvi-tristate.ll +++ b/llvm/test/Transforms/JumpThreading/lvi-tristate.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -jump-threading -simplifycfg -S < %s | FileCheck %s +; RUN: opt -jump-threading -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S < %s | FileCheck %s declare void @ham() define void @hoge() { diff --git a/llvm/test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll b/llvm/test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll index c459867..da7d080 100644 --- a/llvm/test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll +++ b/llvm/test/Transforms/SimplifyCFG/2005-08-01-PHIUpdateFail.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -simplifycfg -disable-output +; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -disable-output ; END. define void @main() { diff --git a/llvm/test/Transforms/SimplifyCFG/2006-08-03-Crash.ll b/llvm/test/Transforms/SimplifyCFG/2006-08-03-Crash.ll index 6003bfb..ddf336e 100644 --- a/llvm/test/Transforms/SimplifyCFG/2006-08-03-Crash.ll +++ b/llvm/test/Transforms/SimplifyCFG/2006-08-03-Crash.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -gvn -simplifycfg -disable-output +; RUN: opt < %s -gvn -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -disable-output ; PR867 target datalayout = "E-p:32:32" diff --git a/llvm/test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll b/llvm/test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll index 5c50b27..4dcc373 100644 --- a/llvm/test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll +++ b/llvm/test/Transforms/SimplifyCFG/ARM/switch-to-lookup-table.ll @@ -1,9 +1,9 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S -simplifycfg -switch-to-lookup -mtriple=arm -relocation-model=static < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE -; RUN: opt -S -simplifycfg -switch-to-lookup -mtriple=arm -relocation-model=pic < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE -; RUN: opt -S -simplifycfg -switch-to-lookup -mtriple=arm -relocation-model=ropi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE -; RUN: opt -S -simplifycfg -switch-to-lookup -mtriple=arm -relocation-model=rwpi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE -; RUN: opt -S -simplifycfg -switch-to-lookup -mtriple=arm -relocation-model=ropi-rwpi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE +; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -mtriple=arm -relocation-model=static < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE +; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -mtriple=arm -relocation-model=pic < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE +; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -mtriple=arm -relocation-model=ropi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE +; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -mtriple=arm -relocation-model=rwpi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE +; RUN: opt -S -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -mtriple=arm -relocation-model=ropi-rwpi < %s | FileCheck %s --check-prefix=CHECK --check-prefix=DISABLE ; RUN: opt -S -passes='simplify-cfg' -mtriple=arm -relocation-model=static < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE ; RUN: opt -S -passes='simplify-cfg' -mtriple=arm -relocation-model=pic < %s | FileCheck %s --check-prefix=CHECK --check-prefix=ENABLE diff --git a/llvm/test/Transforms/SimplifyCFG/DeadSetCC.ll b/llvm/test/Transforms/SimplifyCFG/DeadSetCC.ll index c625600..8bfb0a0 100644 --- a/llvm/test/Transforms/SimplifyCFG/DeadSetCC.ll +++ b/llvm/test/Transforms/SimplifyCFG/DeadSetCC.ll @@ -1,4 +1,4 @@ -; RUN: opt < %s -simplifycfg -S | \ +; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | \ ; RUN: not grep "icmp eq" ; Check that simplifycfg deletes a dead 'seteq' instruction when it diff --git a/llvm/test/Transforms/SimplifyCFG/X86/MagicPointer.ll b/llvm/test/Transforms/SimplifyCFG/X86/MagicPointer.ll index 7789600..7996780 100644 --- a/llvm/test/Transforms/SimplifyCFG/X86/MagicPointer.ll +++ b/llvm/test/Transforms/SimplifyCFG/X86/MagicPointer.ll @@ -1,6 +1,6 @@ ; Test that simplifycfg can create switch instructions from constant pointers. ; -; RUN: opt < %s -simplifycfg -S | FileCheck %s +; RUN: opt < %s -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S | FileCheck %s target datalayout = "e-p:64:64:64-p1:16:16:16-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64" target triple = "x86_64-apple-darwin10.0.0" diff --git a/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-partial.ll b/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-partial.ll index b2b3841..aa7a7a0 100644 --- a/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-partial.ll +++ b/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-partial.ll @@ -1,8 +1,8 @@ -; RUN: opt -simplifycfg -S -o - < %s | FileCheck %s +; RUN: opt -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S -o - < %s | FileCheck %s ; This test case was written to trigger an incorrect assert statement in ; -simplifycfg. Thus we don't actually want to check the output, just that -; -simplifycfg ran successfully. Thus we only check that the function still +; -simplifycfg -simplifycfg-require-and-preserve-domtree=1 ran successfully. Thus we only check that the function still ; exists, and that it still calls foo(). ; ; NOTE: There are some obviously dead blocks and missing branch weight diff --git a/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-switch-create.ll b/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-switch-create.ll index 32a30c3..dd463b1 100644 --- a/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-switch-create.ll +++ b/llvm/test/Transforms/SimplifyCFG/preserve-branchweights-switch-create.ll @@ -1,4 +1,4 @@ -; RUN: opt -simplifycfg -S -o - < %s | FileCheck %s +; RUN: opt -simplifycfg -simplifycfg-require-and-preserve-domtree=1 -S -o - < %s | FileCheck %s declare void @func2(i32) declare void @func4(i32) -- 2.7.4