[LoopSimplifyCFG] Teach LoopSimplifyCFG to constant-fold branches and switches

This patch introduces infrastructure and the simplest case for constant-folding
of branch and switch instructions within loop into unconditional branches.
It is useful as a cleanup for such passes as loop unswitching that sometimes
produce such branches.

Only the simplest case supported in this patch: after the folding, no block
should become dead or stop being part of the loop. Support for more
sophisticated cases will go separately in follow-up patches.

Differential Revision: https://reviews.llvm.org/D54021
Reviewed By: anna

llvm-svn: 347183

1 files changed, 48 insertions, 9 deletions

diff --git a/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll b/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll
index 44f1c0bcd88..944eab00ce8 100644
--- a/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll
+++ b/llvm/test/Transforms/LoopSimplifyCFG/constant-fold-branch.ll
@@ -1,10 +1,53 @@
 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
-; RUN: opt -S -loop-simplifycfg < %s | FileCheck %s
-; RUN: opt -S -passes='require<domtree>,loop(simplify-cfg)' < %s | FileCheck %s
-; RUN: opt -S -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa < %s | FileCheck %s
+; RUN: opt -S -loop-simplifycfg -debug-only=loop-simplifycfg 2>&1 < %s | FileCheck %s
+; RUN: opt -S -passes='require<domtree>,loop(simplify-cfg)' -debug-only=loop-simplifycfg 2>&1 < %s | FileCheck %s
+; RUN: opt -S -loop-simplifycfg -enable-mssa-loop-dependency=true -verify-memoryssa -debug-only=loop-simplifycfg 2>&1 < %s | FileCheck %s
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128-ni:1"
 
+; CHECK-LABEL: In function dead_backedge_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support blocks that are not dead, but will stop being a part of the loop after constant-folding.
+; CHECK-LABEL: In function dead_backedge_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support blocks that are not dead, but will stop being a part of the loop after constant-folding.
+; CHECK-LABEL: In function dead_block_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function dead_block_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function dead_block_propogate_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function dead_block_propogate_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function dead_exit_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits.
+; CHECK-LABEL: In function dead_exit_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support dead loop exits.
+; CHECK-LABEL: In function dead_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function dead_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function dead_sub_loop_test_branch_loop: No constant terminator folding candidates found in loop dead_loop
+; CHECK-LABEL: In function dead_sub_loop_test_branch_loop: No constant terminator folding candidates found in loop live_loop
+; CHECK-LABEL: In function dead_sub_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function dead_sub_loop_test_switch_loop: No constant terminator folding candidates found in loop live_loop
+; CHECK-LABEL: In function dead_sub_loop_test_switch_loop: No constant terminator folding candidates found in loop dead_loop
+; CHECK-LABEL: In function dead_sub_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function inf_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function inf_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function live_block_test_branch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header<header>,%check,%live,%backedge<latch><exiting>
+; CHECK:         Replacing terminator of check with an unconditional branch to the block backedge
+; CHECK-LABEL: In function live_block_test_switch_loop: Constant terminator folding for loop Loop at depth 1 containing: %header<header>,%check,%live,%backedge<latch><exiting>
+; CHECK:         Replacing terminator of check with an unconditional branch to the block backedge
+; CHECK-LABEL: In function partial_sub_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function partial_sub_loop_test_branch_loop: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function partial_sub_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function partial_sub_loop_test_switch_loop: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_1: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_1: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_1: Give up constant terminator folding in loop header: we don't currently support deletion of the current loop.
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_1: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: Give up constant terminator folding in loop header: we don't currently support dead loop exits.
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_2: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: Give up constant terminator folding in loop header: we don't currently support dead loop exits.
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_2: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function full_sub_loop_test_branch_loop_inverse_3: No constant terminator folding candidates found in loop outer_header
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: Give up constant terminator folding in loop header: we don't currently support deletion of dead in-loop blocks.
+; CHECK-LABEL: In function full_sub_loop_test_switch_loop_inverse_3: No constant terminator folding candidates found in loop outer_header
+
 ; Make sure that we can eliminate a provably dead backedge.
 define i32 @dead_backedge_test_branch_loop(i32 %end) {
 ; CHECK-LABEL: @dead_backedge_test_branch_loop(
@@ -707,7 +750,7 @@ define i32 @live_block_test_branch_loop(i1 %c, i32 %end) {
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 ; CHECK:       check:
-; CHECK-NEXT:    br i1 true, label [[BACKEDGE]], label [[LIVE]]
+; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       live:
 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 ; CHECK-NEXT:    br label [[BACKEDGE]]
@@ -752,11 +795,7 @@ define i32 @live_block_test_switch_loop(i1 %c, i32 %end) {
 ; CHECK-NEXT:    [[I:%.*]] = phi i32 [ 0, [[PREHEADER:%.*]] ], [ [[I_INC:%.*]], [[BACKEDGE:%.*]] ]
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[CHECK:%.*]], label [[LIVE:%.*]]
 ; CHECK:       check:
-; CHECK-NEXT:    switch i32 1, label [[LIVE]] [
-; CHECK-NEXT:    i32 0, label [[LIVE]]
-; CHECK-NEXT:    i32 1, label [[BACKEDGE]]
-; CHECK-NEXT:    i32 2, label [[LIVE]]
-; CHECK-NEXT:    ]
+; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       live:
 ; CHECK-NEXT:    [[I_2:%.*]] = add i32 [[I]], 1
 ; CHECK-NEXT:    br label [[BACKEDGE]]