[SimplifyCFG] Thread branches on same condition in more cases (PR54980)

[nikic]

Summary

SimplifyCFG implements basic jump threading, if a branch is performed on a phi node with constant operands. However, InstCombine canonicalizes such phis to the condition value of a previous branch, if possible. SimplifyCFG does support this as well, but only in the very limited case where the same condition is used in a direct predecessor -- notably, this does not include the common diamond pattern (i.e. two consecutive if/elses on the same condition).

This patch extends the code to look back a limited number of blocks to find a branch on the same value, rather than only looking at the direct predecessor.

Fixes https://github.com/llvm/llvm-project/issues/54980.

[nikic]

llvm/test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll

39

There is a branch on %tobool.i.i.i higher up that would get threaded -- as that doesn't seem like the point of the test, I've replaced it with a different condition.

[nikic]

Update some clang tests. Nothing actually changes there, there are only some differences in block order/naming. And it doesn't look like update_cc_test_checks works for these tests :/

[nikic]

Ping

[fhahn]

LGTM, thanks!

[HanKuanChen]

HI, the following code get infinite loop after this commit.

; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
; RUN: opt -passes="simplifycfg<bonus-inst-threshold=1;forward-switch-cond;switch-range-to-icmp;switch-to-lookup;no-keep-loops;hoist-common-insts;sink-common-insts>" -S < %s | FileCheck %s

define void @_Z10alignedboxl(i1 %cmp.a, i1 %cmp.b, i1 %cmp.c) {
; CHECK-LABEL: @_Z10alignedboxl(
; CHECK-NEXT:  entry:
; CHECK-NEXT:    br label [[WHILE_COND:%.*]]
; CHECK:       while.cond:
; CHECK-NEXT:    br i1 [[CMP_A:%.*]], label [[FOR:%.*]], label [[WHILE_BODY_THREAD:%.*]]
; CHECK:       for.body:
; CHECK-NEXT:    br i1 [[CMP_B:%.*]], label [[WHILE_BODY:%.*]], label [[FOR_BODY:%.*]]
; CHECK:       for:
; CHECK-NEXT:    tail call void @XXX()
; CHECK-NEXT:    br label [[FOR_BODY]]
; CHECK:       while.body:
; CHECK-NEXT:    br i1 [[CMP_C:%.*]], label [[C_EXIT:%.*]], label [[LAND:%.*]]
; CHECK:       while.body.thread:
; CHECK-NEXT:    br i1 [[CMP_C]], label [[WHILE_COND]], label [[LAND]]
; CHECK:       land:
; CHECK-NEXT:    tail call void @XXX()
; CHECK-NEXT:    br label [[WHILE_COND]]
; CHECK:       c.exit:
; CHECK-NEXT:    br i1 [[CMP_A]], label [[FOR_D:%.*]], label [[WHILE_BODY_THREAD]]
; CHECK:       for.d:
; CHECK-NEXT:    ret void
;
entry:
  br label %while.cond

while.cond:                                       ; preds = %land, %while.body.thread, %entry
  br i1 %cmp.a, label %for, label %while.body.thread

for.body:                                         ; preds = %for, %for.body
  br i1 %cmp.b, label %while.body, label %for.body

for:                                              ; preds = %while.cond
  tail call void @XXX()
  br label %for.body

while.body:                                       ; preds = %for.body
  br i1 %cmp.c, label %c.exit, label %land

while.body.thread:                                ; preds = %c.exit, %while.cond
  br i1 %cmp.c, label %while.cond, label %land

land:                                             ; preds = %while.body.thread, %while.body
  tail call void @XXX()
  br label %while.cond

c.exit:                                           ; preds = %while.body
  br i1 %cmp.a, label %for.d, label %while.cond

for.d:                                            ; preds = %c.exit
  ret void
}

declare void @XXX()

[nikic]

@HanKuanChen Thanks for the report! I've landed a fix for this test case in https://github.com/llvm/llvm-project/commit/dc969061c68e62328607d68215ed8b9ef4a1e4b1. This is based on making SimplifyCFG behave more like JumpThreading, which does not have an infinite loop for this case. Let me know if you see further issues.

[nikic]

I ended up reverting this patch in https://github.com/llvm/llvm-project/commit/a4772cbaf0dc717ab6b4639272ca2910897613f0, because I reduced another infinite loop (https://github.com/llvm/llvm-project/issues/56203) to it as well, which makes it the third one. It's probably not possible to reliably prevent infinite combine loops in this area with a dominator tree.

[nathanchance]

Should dc969061c68e62328607d68215ed8b9ef4a1e4b1 be reverted as well? I just bisected an assertion failure while building the Linux kernel for arm64 to that change:

clang: /home/nathan/cbl/src/llvm-project/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp:1136: llvm::BasicBlock *SplitBlockPredecessorsImpl(llvm::BasicBlock *, ArrayRef<llvm::BasicBlock *>, const char *, llvm::DomTreeUpdater *, llvm::DominatorTree *, llvm::LoopInfo *, llvm::MemorySSAUpdater *, bool): Assertion `!isa<CallBrInst>(Preds[i]->getTerminator()) && "Cannot split an edge from a CallBrInst"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: /home/nathan/tmp/build/llvm-bisect/stage1/bin/clang -mlittle-endian -Qunused-arguments -fmacro-prefix-map=/home/nathan/cbl/src/linux/= -Wall -Wundef -Werror=strict-prototypes -Wno-trigraphs -fno-strict-aliasing -fno-common -fshort-wchar -fno-PIE -Werror=implicit-function-declaration -Werror=implicit-int -Werror=return-type -Wno-format-security -std=gnu11 --target=aarch64-linux-gnu -fintegrated-as -Werror=unknown-warning-option -Werror=ignored-optimization-argument -mgeneral-regs-only -Wno-psabi -fno-asynchronous-unwind-tables -fno-unwind-tables -mbranch-protection=pac-ret+leaf+bti -fno-delete-null-pointer-checks -Wno-frame-address -Wno-address-of-packed-member -O2 -Wframe-larger-than=2048 -fstack-protector-strong -Wimplicit-fallthrough -Wno-gnu -Wno-unused-but-set-variable -Wno-unused-const-variable -fno-omit-frame-pointer -fno-optimize-sibling-calls -ftrivial-auto-var-init=zero -enable-trivial-auto-var-init-zero-knowing-it-will-be-removed-from-clang -fno-stack-clash-protection -Wdeclaration-after-statement -Wvla -Wno-pointer-sign -Wcast-function-type -fno-strict-overflow -fno-stack-check -Werror=date-time -Werror=incompatible-pointer-types -Wno-initializer-overrides -Wno-format -Wno-sign-compare -Wno-format-zero-length -Wno-pointer-to-enum-cast -Wno-tautological-constant-out-of-range-compare -Wno-unaligned-access -mstack-protector-guard=sysreg -mstack-protector-guard-reg=sp_el0 -mstack-protector-guard-offset=1184 -Wa,-march=armv8.5-a -nostdinc -I/home/nathan/cbl/src/linux/arch/arm64/include -I./arch/arm64/include/generated -I/home/nathan/cbl/src/linux/include -I./include -I/home/nathan/cbl/src/linux/arch/arm64/include/uapi -I./arch/arm64/include/generated/uapi -I/home/nathan/cbl/src/linux/include/uapi -I./include/generated/uapi -include /home/nathan/cbl/src/linux/include/linux/compiler-version.h -include /home/nathan/cbl/src/linux/include/linux/kconfig.h -include /home/nathan/cbl/src/linux/include/linux/compiler_types.h -D__KERNEL__ -DKASAN_SHADOW_SCALE_SHIFT= -DCONFIG_CC_HAS_K_CONSTRAINT=1 -DARM64_ASM_ARCH=\"armv8.5-a\" -DKASAN_SHADOW_SCALE_SHIFT= -I /home/nathan/cbl/src/linux/arch/arm64/crypto -I ./arch/arm64/crypto -DKBUILD_MODFILE=\"arch/arm64/crypto/aes-ce-cipher\" -DKBUILD_BASENAME=\"aes_ce_glue\" -DKBUILD_MODNAME=\"aes_ce_cipher\" -D__KBUILD_MODNAME=kmod_aes_ce_cipher -c -Wp,-MMD,arch/arm64/crypto/.aes-ce-glue.o.d -fcolor-diagnostics -o arch/arm64/crypto/aes-ce-glue.o /home/nathan/cbl/src/linux/arch/arm64/crypto/aes-ce-glue.c
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x000055aae2db8b83 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3e2fb83)
 #1 0x000055aae2db6b1e llvm::sys::RunSignalHandlers() (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3e2db1e)
 #2 0x000055aae2d40c13 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x000055aae2d40d8e CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007fdd27ea18e0 (/usr/lib/libc.so.6+0x3e8e0)
 #5 0x00007fdd27ef136c (/usr/lib/libc.so.6+0x8e36c)
 #6 0x00007fdd27ea1838 gsignal (/usr/lib/libc.so.6+0x3e838)
 #7 0x00007fdd27e8b535 abort (/usr/lib/libc.so.6+0x28535)
 #8 0x00007fdd27e8b45c (/usr/lib/libc.so.6+0x2845c)
 #9 0x00007fdd27e9a366 (/usr/lib/libc.so.6+0x37366)
#10 0x000055aae2dcb9b6 SplitBlockPredecessorsImpl(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DomTreeUpdater*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) BasicBlockUtils.cpp:0:0
#11 0x000055aae2dcba4c llvm::SplitBlockPredecessors(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DomTreeUpdater*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3e42a4c)
#12 0x000055aae2ef5b01 (anonymous namespace)::SimplifyCFGOpt::simplifyCondBranch(llvm::BranchInst*, llvm::IRBuilder<llvm::ConstantFolder, llvm::IRBuilderDefaultInserter>&) SimplifyCFG.cpp:0:0
#13 0x000055aae2ee2e29 (anonymous namespace)::SimplifyCFGOpt::run(llvm::BasicBlock*) SimplifyCFG.cpp:0:0
#14 0x000055aae2edfe84 llvm::simplifyCFG(llvm::BasicBlock*, llvm::TargetTransformInfo const&, llvm::DomTreeUpdater*, llvm::SimplifyCFGOptions const&, llvm::ArrayRef<llvm::WeakVH>) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3f56e84)
#15 0x000055aae2ce66da iterativelySimplifyCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DomTreeUpdater*, llvm::SimplifyCFGOptions const&) SimplifyCFGPass.cpp:0:0
#16 0x000055aae2ce6127 simplifyFunctionCFGImpl(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DominatorTree*, llvm::SimplifyCFGOptions const&) SimplifyCFGPass.cpp:0:0
#17 0x000055aae2ce4d0d simplifyFunctionCFG(llvm::Function&, llvm::TargetTransformInfo const&, llvm::DominatorTree*, llvm::SimplifyCFGOptions const&) SimplifyCFGPass.cpp:0:0
#18 0x000055aae2ce4a6b llvm::SimplifyCFGPass::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3d5ba6b)
#19 0x000055aae3f9d10d llvm::detail::PassModel<llvm::Function, llvm::SimplifyCFGPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#20 0x000055aae268c68d llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x370368d)
#21 0x000055aae35ccbbd llvm::detail::PassModel<llvm::Function, llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function>>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function>>::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) BackendUtil.cpp:0:0
#22 0x000055aae26ec953 llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3763953)
#23 0x000055aae3f9f50d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::CGSCCToFunctionPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) PassBuilder.cpp:0:0
#24 0x000055aae26e7067 llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x375e067)
#25 0x000055aae2810d7d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::PassManager<llvm::LazyCallGraph::SCC, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#26 0x000055aae26eaae8 llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3761ae8)
#27 0x000055aae281155d llvm::detail::PassModel<llvm::LazyCallGraph::SCC, llvm::DevirtSCCRepeatedPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&>::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) Inliner.cpp:0:0
#28 0x000055aae26e9259 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/tmp/build/llvm-bisect/stage1/bin/clang+0x3760259)
...

# bad: [a1cd3f49b68022337c356482c8c4ec36221f4d1b] [RISCV] Use a switch statement in PreprocessISelDAG. NFC
# good: [142aca7741d5b06207e87bf4880fbe308c8d6823] [InstCombine] fold sub of min/max of sub with common operand
git bisect start 'a1cd3f49b68022337c356482c8c4ec36221f4d1b' '142aca7741d5b06207e87bf4880fbe308c8d6823'
# good: [ebb78a95cede526ece9b904e9ba623d4b963df60] [LV] Remove stray dbgs() call after  774fc63490939.
git bisect good ebb78a95cede526ece9b904e9ba623d4b963df60
# bad: [e7a0fa4df00c6386632d1395799c6150f39a3e33] [DAG] foldAddSubOfSignBit - don't bother creating the new shift node unless constant folding succeeds
git bisect bad e7a0fa4df00c6386632d1395799c6150f39a3e33
# bad: [935570b2ad808035a1fd9bf6fa894657babc8694] [ConstExpr] Don't create div/rem expressions
git bisect bad 935570b2ad808035a1fd9bf6fa894657babc8694
# bad: [6e2058e58832058f05372c93e8be50695efcc6be] [Compiler-RT]  Remove FlushViewOfFile call when unmapping gcda files on win32.
git bisect bad 6e2058e58832058f05372c93e8be50695efcc6be
# bad: [8cd79bc12c366de01cedb88e2e2fc026619e64ea] [AMDGPU][GlobalISel] Support register offsets for SMRDs.
git bisect bad 8cd79bc12c366de01cedb88e2e2fc026619e64ea
# bad: [9fbf1107cc763783a82b89953be8a45097ba3390] [pseudo] Eliminate LRTable::Action. NFC
git bisect bad 9fbf1107cc763783a82b89953be8a45097ba3390
# bad: [dc969061c68e62328607d68215ed8b9ef4a1e4b1] [SimplifyCFG] Thread all predecessors with same value at once
git bisect bad dc969061c68e62328607d68215ed8b9ef4a1e4b1
# first bad commit: [dc969061c68e62328607d68215ed8b9ef4a1e4b1] [SimplifyCFG] Thread all predecessors with same value at once

I can reduce something down if necessary.

[nathanchance]

I ended up reducing something down anyways. At the parent commit of dc969061c68e62328607d68215ed8b9ef4a1e4b1, there is no crash.

_Bool fpsimd_context_busy;
enum { false, true } arch_static_branch_jump() {
  asm goto("" : : : : l_yes);
  return false;
l_yes:
  return true;
}
_Bool __preempt_count_dec_and_test();
void preempt_schedule_notrace();
long __percpu_read_8();
_Bool may_use_simd() {
  return ({ ({ arch_static_branch_jump(); }); }) && ({
           typeof(fpsimd_context_busy) pscr_ret__ = ({
             typeof(fpsimd_context_busy) __retval = __percpu_read_8();
             if (__builtin_expect(__preempt_count_dec_and_test(), 0))
               preempt_schedule_notrace();
             __retval;
           });
           pscr_ret__;
         });
}
void aes_cipher_encrypt() {
  if (may_use_simd())
    preempt_schedule_notrace();
}

$ clang --target=aarch64-linux-gnu -O2 -c -o /dev/null aes-ce-glue.i
clang: /home/nathan/cbl/src/llvm-project/llvm/lib/Transforms/Utils/BasicBlockUtils.cpp:1136: llvm::BasicBlock *SplitBlockPredecessorsImpl(llvm::BasicBlock *, ArrayRef<llvm::BasicBlock *>, const char *, llvm::DomTreeUpdater *, llvm::DominatorTree *, llvm::LoopInfo *, llvm::MemorySSAUpdater *, bool): Assertion `!isa<CallBrInst>(Preds[i]->getTerminator()) && "Cannot split an edge from a CallBrInst"' failed.
PLEASE submit a bug report to https://github.com/llvm/llvm-project/issues/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.      Program arguments: clang --target=aarch64-linux-gnu -O2 -c -o /dev/null aes-ce-glue.i
1.      <eof> parser at end of file
2.      Optimizer
 #0 0x0000aaaad1ad36b8 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/tmp/install/llvm/dc969061c68e62328607d68215ed8b9ef4a1e4b1/bin/clang-15+0x35336b8)
 #1 0x0000aaaad1ad18d8 llvm::sys::RunSignalHandlers() (/home/nathan/tmp/install/llvm/dc969061c68e62328607d68215ed8b9ef4a1e4b1/bin/clang-15+0x35318d8)
 #2 0x0000aaaad1a5e6e4 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x0000aaaad1a5e894 CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x0000ffffa099e854 (linux-vdso.so.1+0x854)
 #5 0x0000ffffa04b28a8 __pthread_kill_implementation (/lib64/libc.so.6+0x828a8)
 #6 0x0000ffffa046ae40 gsignal (/lib64/libc.so.6+0x3ae40)
 #7 0x0000ffffa04572f8 abort (/lib64/libc.so.6+0x272f8)
 #8 0x0000ffffa0464538 __assert_fail_base (/lib64/libc.so.6+0x34538)
 #9 0x0000ffffa04645a0 __assert_perror_fail (/lib64/libc.so.6+0x345a0)
#10 0x0000aaaad1ae30c0 SplitBlockPredecessorsImpl(llvm::BasicBlock*, llvm::ArrayRef<llvm::BasicBlock*>, char const*, llvm::DomTreeUpdater*, llvm::DominatorTree*, llvm::LoopInfo*, llvm::MemorySSAUpdater*, bool) BasicBlockUtils.cpp:0:0
...

[nikic]

@nathanchance Thanks for the report. I've applied the obvious fix in https://github.com/llvm/llvm-project/commit/20962c1240691d25b21ce425313c81eed0b1b358. However, I think that this (and similar limitations relating to critical edge splitting) might actually be unnecessary since https://github.com/llvm/llvm-project/commit/7a7bba289521e6d4da199565cf72dc9eaed3d671. callbr has stricter semantics than indirectbr, and apparently updating successors of a callbr is supposed to be possible (because the blockaddresses used by it must be directly used in the call arguments and thus can be updated, while in the indirectbr case they may be passed indirectly).

clang/test/CodeGenObjC/exceptions.m

void f1(void) {
 
   while (1) {
     // CHECK:      call void @objc_exception_try_enter
     // CHECK-NEXT: getelementptr
     // CHECK-NEXT: call i32 @_setjmp(
     // CHECK-NEXT: icmp
     // CHECK-NEXT: br i1
     @try {
-    // CHECK:      call void asm sideeffect "", "=*m"
     // CHECK:      call void asm sideeffect "", "*m"
     // CHECK-NEXT: call void @foo()
       foo();
     // CHECK:      call void @objc_exception_try_exit
+    // CHECK:      try.handler:
+    // CHECK:      call void asm sideeffect "", "=*m"
 
     } @finally {
       break;
     }
   }
 }
 
 // Test that modifications to local variables are respected under
 // optimization.  rdar://problem/8160285
 
 // CHECK-LABEL: define{{.*}} i32 @f2()
 int f2(void) {
   extern void foo(void);
 
   // CHECK:        [[X:%.*]] = alloca i32
   // CHECK:        store i32 5, i32* [[X]]
   int x = 0;
   x += 5;
 
   // CHECK:        [[SETJMP:%.*]] = call i32 @_setjmp
   // CHECK-NEXT:   [[CAUGHT:%.*]] = icmp eq i32 [[SETJMP]], 0
   // CHECK-NEXT:   br i1 [[CAUGHT]]
   @try {
-    // Landing pad.  Note that we elide the re-enter.
-    // CHECK:      call void asm sideeffect "", "=*m,=*m"(i32* nonnull elementtype(i32) [[X]]
-    // CHECK-NEXT: call i8* @objc_exception_extract
-    // CHECK-NEXT: [[T1:%.*]] = load i32, i32* [[X]]
-    // CHECK-NEXT: [[T2:%.*]] = add nsw i32 [[T1]], -1
-
     // CHECK: store i32 6, i32* [[X]]
     x++;
     // CHECK-NEXT: call void asm sideeffect "", "*m,*m"(i32* nonnull elementtype(i32) [[X]]
     // CHECK-NEXT: call void @foo()
     // CHECK-NEXT: call void @objc_exception_try_exit
     // CHECK-NEXT: [[T:%.*]] = load i32, i32* [[X]]
     foo();
   } @catch (id) {
+    // Landing pad.  Note that we elide the re-enter.
+    // CHECK:      call void asm sideeffect "", "=*m,=*m"(i32* nonnull elementtype(i32) [[X]]
+    // CHECK-NEXT: call i8* @objc_exception_extract
+    // CHECK-NEXT: [[T1:%.*]] = load i32, i32* [[X]]
+    // CHECK-NEXT: [[T2:%.*]] = add nsw i32 [[T1]], -1
+
     x--;
   }
 
   return x;
 }
 
 // Test that the cleanup destination is saved when entering a finally
 // block.  rdar://problem/8293901

clang/test/CodeGenObjCXX/exceptions-legacy.mm

 // CHECK-NEXT: [[T0:%.*]] = getelementptr inbounds [[BUF_T]], [[BUF_T]]* [[BUF]], i32 0, i32 0, i32 0
 // CHECK-NEXT: [[T1:%.*]] = call i32 @_setjmp(i32* nonnull [[T0]])
 // CHECK-NEXT: [[T2:%.*]] = icmp eq i32 [[T1]], 0
 // CHECK-NEXT: br i1 [[T2]],
 
 //   Body.
 // CHECK:      invoke void @_Z3foov()
 
-//   Catch handler.  Reload of 'failed' address is unnecessary.
-// CHECK:      [[T0:%.*]] = load i8*, i8**
-// CHECK-NEXT: store i8 1, i8* [[T0]],
-// CHECK-NEXT: br label
-
 //   Leave the @try.
 // CHECK:      call void @objc_exception_try_exit([[BUF_T]]* nonnull [[BUF]])
 // CHECK-NEXT: br label
 // CHECK:      ret void
 
-
 //   Real EH cleanup.
 // CHECK:      [[T0:%.*]] = landingpad
 // CHECK-NEXT:    cleanup
 // CHECK-NEXT: call void @objc_exception_try_exit([[BUF_T]]* nonnull [[BUF]])
 // CHECK-NEXT: resume
 
+//   Catch handler.  Reload of 'failed' address is unnecessary.
+// CHECK:      [[T0:%.*]] = load i8*, i8**
+// CHECK-NEXT: store i8 1, i8* [[T0]],
+// CHECK-NEXT: br label
+

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

for (Instruction &I : reverse(BB->instructionsWithoutDebug(false))) {
     }
 
     // Looks ok, continue checking.
   }
 
   return true;
 }
 
-static ConstantInt *getKnownValueOnEdge(Value *V, BasicBlock *From,
-                                        BasicBlock *To) {
+static ConstantInt *
+getKnownValueOnEdge(Value *V, BasicBlock *From, BasicBlock *To,
+                    SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>,
+                                  ConstantInt *> &Visited) {
   // Don't look past the block defining the value, we might get the value from
   // a previous loop iteration.
   auto *I = dyn_cast<Instruction>(V);
   if (I && I->getParent() == To)
     return nullptr;
 
   // We know the value if the From block branches on it.
   auto *BI = dyn_cast<BranchInst>(From->getTerminator());
   if (BI && BI->isConditional() && BI->getCondition() == V &&
       BI->getSuccessor(0) != BI->getSuccessor(1))
     return BI->getSuccessor(0) == To ? ConstantInt::getTrue(BI->getContext())
                                      : ConstantInt::getFalse(BI->getContext());
 
+  // Limit the amount of blocks we inspect.
+  if (Visited.size() >= 8)
     return nullptr;
+
+  auto Pair = Visited.try_emplace({From, To}, nullptr);
+  if (!Pair.second)
+    return Pair.first->second;
+
+  // Check whether the known value is the same for all predecessors.
+  ConstantInt *Common = nullptr;
+  for (BasicBlock *Pred : predecessors(From)) {
+    ConstantInt *C = getKnownValueOnEdge(V, Pred, From, Visited);
+    if (!C || (Common && Common != C))
+      return nullptr;
+    Common = C;
+  }
+  return Visited[{From, To}] = Common;
 }
 
 /// If we have a conditional branch on something for which we know the constant
 /// value in predecessors (e.g. a phi node in the current block), thread edges
 /// from the predecessor to their ultimate destination.
 static Optional<bool>
 FoldCondBranchOnValueKnownInPredecessorImpl(BranchInst *BI, DomTreeUpdater *DTU,
                                             const DataLayout &DL,
                                             AssumptionCache *AC) {
   SmallMapVector<BasicBlock *, ConstantInt *, 8> KnownValues;
   BasicBlock *BB = BI->getParent();
   Value *Cond = BI->getCondition();
   PHINode *PN = dyn_cast<PHINode>(Cond);
   if (PN && PN->getParent() == BB) {
     // Degenerate case of a single entry PHI.
     if (PN->getNumIncomingValues() == 1) {
       FoldSingleEntryPHINodes(PN->getParent());
       return true;
     }
 
     for (Use &U : PN->incoming_values())
       if (auto *CB = dyn_cast<ConstantInt>(U))
         KnownValues.insert({PN->getIncomingBlock(U), CB});
   } else {
+    SmallDenseMap<std::pair<BasicBlock *, BasicBlock *>, ConstantInt *> Visited;
     for (BasicBlock *Pred : predecessors(BB)) {
-      if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB))
+      if (ConstantInt *CB = getKnownValueOnEdge(Cond, Pred, BB, Visited))
         KnownValues.insert({Pred, CB});
     }
   }
 
   if (KnownValues.empty())
     return false;
 
   // Now we know that this block has multiple preds and two succs.

llvm/test/CodeGen/AArch64/arm64-andCmpBrToTBZ.ll

if.then3:                                         ; preds = %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit, %land.rhs.i
   %tmp11 = load i8, i8* %str14, align 8
   %tmp12 = and i8 %tmp11, 2
   %tmp13 = icmp ne i8 %tmp12, 0
   br label %return
 
 if.end5:                                          ; preds = %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit, %lor.rhs.i.i.i
 ; CHECK: %if.end5
 ; CHECK: tbz
-  br i1 %tobool.i.i.i, label %if.end12, label %land.rhs.i19, !prof !1
+  br i1 %IsEditable, label %if.end12, label %land.rhs.i19, !prof !1
 
 land.rhs.i19:                                     ; preds = %if.end5
   %cmp.i.i.i18 = icmp eq i8* %str6, %str7
   br i1 %cmp.i.i.i18, label %if.then7, label %lor.rhs.i.i.i23
 
 lor.rhs.i.i.i23:                                  ; preds = %land.rhs.i19
   %cmp.i13.i.i.i22 = icmp eq i8* %str3, %str4
   br i1 %cmp.i13.i.i.i22, label %_ZNK7WebCore4Node10hasTagNameERKNS_13QualifiedNameE.exit28, label %if.end12

llvm/test/Transforms/GVNSink/sink-common-code.ll

 
 succ:
   %p = phi i32 [ 0, %entry ], [ %add1, %one ], [ %add2, %two ]
   br label %one
 }
 declare void @g()
 
 ; CHECK-LABEL: test_pr30292
-; CHECK: phi i32 [ 0, %entry ], [ %add1, %succ ], [ %add2, %two ]
+; CHECK: phi i32 [ 0, %entry ], [ %add1, %succ ]
 
 define zeroext i1 @test_pr30244(i1 zeroext %flag, i1 zeroext %flag2, i32 %blksA, i32 %blksB, i32 %nblks) {
 
 entry:
   %p = alloca i8
   br i1 %flag, label %if.then, label %if.else
 
 if.then:

llvm/test/Transforms/SimplifyCFG/X86/sink-common-code.ll

 define void @test_pr30292(i1 %cond, i1 %cond2, i32 %a, i32 %b) {
 ; CHECK-LABEL: @test_pr30292(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[ADD1:%.*]] = add i32 [[A:%.*]], 1
 ; CHECK-NEXT:    br label [[SUCC:%.*]]
 ; CHECK:       two:
 ; CHECK-NEXT:    call void @g()
 ; CHECK-NEXT:    [[ADD2:%.*]] = add i32 [[A]], 1
-; CHECK-NEXT:    br label [[SUCC]]
+; CHECK-NEXT:    br label [[TWO:%.*]]
 ; CHECK:       succ:
-; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD1]], [[SUCC]] ], [ [[ADD2]], [[TWO:%.*]] ]
+; CHECK-NEXT:    [[P:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[ADD1]], [[SUCC]] ]
 ; CHECK-NEXT:    br i1 [[COND:%.*]], label [[TWO]], label [[SUCC]]
 ;
 entry:
   %add1 = add i32 %a, 1
   br label %succ
 
 one:
   br i1 %cond, label %two, label %succ

llvm/test/Transforms/SimplifyCFG/jump-threading.ll

join2:
   ret void
 }
 
 define void @test_same_cond_simple(i1 %c) {
 ; CHECK-LABEL: @test_same_cond_simple(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo()
-; CHECK-NEXT:    br label [[JOIN:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    call void @bar()
-; CHECK-NEXT:    br label [[JOIN]]
-; CHECK:       join:
-; CHECK-NEXT:    br i1 [[C]], label [[IF2:%.*]], label [[ELSE2:%.*]]
-; CHECK:       if2:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[JOIN2:%.*]]
-; CHECK:       else2:
+; CHECK:       else:
+; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[JOIN2]]
 ; CHECK:       join2:
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %if, label %else
 
 if:
join2:
   ret void
 }
 
 define void @test_same_cond_extra_use(i1 %c) {
 ; CHECK-LABEL: @test_same_cond_extra_use(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo()
-; CHECK-NEXT:    br label [[JOIN:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    call void @bar()
-; CHECK-NEXT:    br label [[JOIN]]
-; CHECK:       join:
 ; CHECK-NEXT:    call void @use.i1(i1 [[C]])
-; CHECK-NEXT:    br i1 [[C]], label [[IF2:%.*]], label [[ELSE2:%.*]]
-; CHECK:       if2:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[JOIN2:%.*]]
-; CHECK:       else2:
+; CHECK:       else:
+; CHECK-NEXT:    call void @bar()
+; CHECK-NEXT:    call void @use.i1(i1 [[C]])
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[JOIN2]]
 ; CHECK:       join2:
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %if, label %else
 
 if:
join2:
   ret void
 }
 
 define void @test_same_cond_extra_use_different_block(i1 %c) {
 ; CHECK-LABEL: @test_same_cond_extra_use_different_block(
 ; CHECK-NEXT:    br i1 [[C:%.*]], label [[IF:%.*]], label [[ELSE:%.*]]
 ; CHECK:       if:
 ; CHECK-NEXT:    call void @foo()
-; CHECK-NEXT:    br label [[JOIN:%.*]]
-; CHECK:       else:
-; CHECK-NEXT:    call void @bar()
-; CHECK-NEXT:    br label [[JOIN]]
-; CHECK:       join:
-; CHECK-NEXT:    br i1 [[C]], label [[IF2:%.*]], label [[ELSE2:%.*]]
-; CHECK:       if2:
 ; CHECK-NEXT:    call void @use.i1(i1 [[C]])
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[JOIN2:%.*]]
-; CHECK:       else2:
+; CHECK:       else:
+; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    call void @use.i1(i1 [[C]])
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[JOIN2]]
 ; CHECK:       join2:
 ; CHECK-NEXT:    ret void
 ;
   br i1 %c, label %if, label %else
 

llvm/test/Transforms/SimplifyCFG/wc-widen-block.ll

 return:
   ret i32 0
 }
 
 
 define i32 @neg_loop(i1 %cond_0, i1 %cond_1) {
 ; CHECK-LABEL: @neg_loop(
 ; CHECK-NEXT:  entry:
-; CHECK-NEXT:    br label [[GUARDED:%.*]]
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[LOOP:%.*]], label [[DEOPT2:%.*]], !prof [[PROF0]]
+; CHECK:       loop.critedge:
+; CHECK-NEXT:    call void @unknown()
+; CHECK-NEXT:    br label [[LOOP]]
 ; CHECK:       loop:
 ; CHECK-NEXT:    [[WIDENABLE_COND:%.*]] = call i1 @llvm.experimental.widenable.condition()
 ; CHECK-NEXT:    [[EXIPLICIT_GUARD_COND:%.*]] = and i1 [[COND_0:%.*]], [[WIDENABLE_COND]]
-; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[GUARDED]], label [[DEOPT:%.*]], !prof [[PROF0]]
+; CHECK-NEXT:    br i1 [[EXIPLICIT_GUARD_COND]], label [[LOOP_CRITEDGE:%.*]], label [[DEOPT:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt:
 ; CHECK-NEXT:    [[DEOPTRET:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
 ; CHECK-NEXT:    ret i32 [[DEOPTRET]]
-; CHECK:       guarded:
-; CHECK-NEXT:    call void @unknown()
-; CHECK-NEXT:    br i1 [[COND_1:%.*]], label [[LOOP:%.*]], label [[DEOPT2:%.*]], !prof [[PROF0]]
 ; CHECK:       deopt2:
 ; CHECK-NEXT:    [[DEOPTRET2:%.*]] = call i32 (...) @llvm.experimental.deoptimize.i32() [ "deopt"() ]
 ; CHECK-NEXT:    ret i32 [[DEOPTRET2]]
 ;
 entry:
   br label %guarded
 
 loop: