[LoopDeletion] Handle Phis with similar inputs from different block

[mkazantsev]

Summary

This patch lifts the requirement to have the only incoming live block
for Phis. There can be multiple live blocks if the same value comes to
phi from all live incoming blocks.

[nikic]

LGTM

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

247–248

Comment needs an update.

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

657–658

TODO can be dropped.

[mkazantsev]

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

657–658

True, thanks!

[mkazantsev]

Per underlying patch change

[mkazantsev]

Rebased, comments updated. Will wait couple days before landing, in case if underlying patch breaks.
@nikic could you please check if this has negative CT impact? I imagine it could, just interesting how big it is.

If it's visible, then maybe we should return to idea of lazy phi evaluation.

[nikic]

Not seeing any compile-time impact, and rebased versions still looks good.

[mkazantsev]

Thanks! Let's give the dependent patch some time to break, and if it's fine, I'll merge this one.

[lebedev.ri]

This seems fine to me.
I think there may be some room for undef/poison incoming value handling.

[mkazantsev]

Indeed, we can skip undefs as well.

[mkazantsev]

In D103959#2827873, @lebedev.ri wrote:

This seems fine to me.
I think there may be some room for undef/poison incoming value handling.

D104618

[nathanchance]

This causes a crash while building the Linux kernel: https://github.com/ClangBuiltLinux/linux/issues/1403

$ cat cpu_errata.i
__boot_cpu_mode_0;
enum { false, true } arch_static_branch_jump() {
  asm goto("" : : : : l_yes);
  return false;
l_yes:
  return true;
}
is_hyp_mode_available() {
  if (({
        _Bool branch = arch_static_branch_jump();
        __builtin_expect(branch, 1);
      }))
    return true;
  return __boot_cpu_mode_0;
}
needs_tx2_tvm_workaround() {
  int i;
  if (!is_hyp_mode_available())
    return false;
  for (; i = cpumask_next(i);)
    ;
}

$ clang -O2 --target=aarch64-linux-gnu -c -o /dev/null cpu_errata.i
...
clang: /home/nathan/cbl/github/tc-build/llvm-project/llvm/include/llvm/IR/Instructions.h:2785: llvm::Value *llvm::PHINode::getIncomingValueForBlock(const llvm::BasicBlock *) const: Assertion `Idx >= 0 && "Invalid basic block argument!"' failed.
PLEASE submit a bug report to https://bugs.llvm.org/ and include the crash backtrace, preprocessed source, and associated run script.
Stack dump:
0.	Program arguments: clang -O2 --target=aarch64-linux-gnu -c -o /dev/null cpu_errata.i
1.	<eof> parser at end of file
2.	Optimizer
 #0 0x0000000002f40033 llvm::sys::PrintStackTrace(llvm::raw_ostream&, int) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2f40033)
 #1 0x0000000002f3de7e llvm::sys::RunSignalHandlers() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2f3de7e)
 #2 0x0000000002ecea43 (anonymous namespace)::CrashRecoveryContextImpl::HandleCrash(int, unsigned long) CrashRecoveryContext.cpp:0:0
 #3 0x0000000002eceb7e CrashRecoverySignalHandler(int) CrashRecoveryContext.cpp:0:0
 #4 0x00007fe3a8a10870 __restore_rt sigaction.c:0:0
 #5 0x00007fe3a84cad22 raise (/usr/lib/libc.so.6+0x3cd22)
 #6 0x00007fe3a84b4862 abort (/usr/lib/libc.so.6+0x26862)
 #7 0x00007fe3a84b4747 _nl_load_domain.cold loadmsgcat.c:0:0
 #8 0x00007fe3a84c3616 (/usr/lib/libc.so.6+0x35616)
 #9 0x0000000002d3d3ca breakBackedgeIfNotTaken(llvm::Loop*, llvm::DominatorTree&, llvm::ScalarEvolution&, llvm::LoopInfo&, llvm::MemorySSA*, llvm::OptimizationRemarkEmitter&) LoopDeletion.cpp:0:0
#10 0x0000000002d3b671 llvm::LoopDeletionPass::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2d3b671)
#11 0x0000000004069ccd llvm::detail::PassModel<llvm::Loop, llvm::LoopDeletionPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) PassBuilder.cpp:0:0
#12 0x00000000040a803f llvm::Optional<llvm::PreservedAnalyses> llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runSinglePass<llvm::Loop, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > > >(llvm::Loop&, std::unique_ptr<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, std::default_delete<llvm::detail::PassConcept<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&> > >&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&, llvm::PassInstrumentation&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x40a803f)
#13 0x00000000040a7d97 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::runWithoutLoopNestPasses(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x40a7d97)
#14 0x00000000040a74b8 llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x40a74b8)
#15 0x000000000405f7fd llvm::detail::PassModel<llvm::Loop, llvm::PassManager<llvm::Loop, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&>::run(llvm::Loop&, llvm::AnalysisManager<llvm::Loop, llvm::LoopStandardAnalysisResults&>&, llvm::LoopStandardAnalysisResults&, llvm::LPMUpdater&) PassBuilder.cpp:0:0
#16 0x00000000040a91bd llvm::FunctionToLoopPassAdaptor::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x40a91bd)
#17 0x000000000406a14d llvm::detail::PassModel<llvm::Function, llvm::FunctionToLoopPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) PassBuilder.cpp:0:0
#18 0x00000000028b0e71 llvm::PassManager<llvm::Function, llvm::AnalysisManager<llvm::Function> >::run(llvm::Function&, llvm::AnalysisManager<llvm::Function>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x28b0e71)
#19 0x000000000361f61d 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
#20 0x0000000002916e1e llvm::CGSCCToFunctionPassAdaptor::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2916e1e)
#21 0x000000000406d65d 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
#22 0x0000000002911351 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/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2911351)
#23 0x0000000002a060ad 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
#24 0x0000000002914f4a llvm::DevirtSCCRepeatedPass::run(llvm::LazyCallGraph::SCC&, llvm::AnalysisManager<llvm::LazyCallGraph::SCC, llvm::LazyCallGraph&>&, llvm::LazyCallGraph&, llvm::CGSCCUpdateResult&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2914f4a)
#25 0x0000000002a063ed 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
#26 0x00000000029134c5 llvm::ModuleToPostOrderCGSCCPassAdaptor::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x29134c5)
#27 0x0000000002a0624d llvm::detail::PassModel<llvm::Module, llvm::ModuleToPostOrderCGSCCPassAdaptor, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) Inliner.cpp:0:0
#28 0x00000000028afba4 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x28afba4)
#29 0x0000000002a02d2e llvm::ModuleInlinerWrapperPass::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2a02d2e)
#30 0x000000000406d90d llvm::detail::PassModel<llvm::Module, llvm::ModuleInlinerWrapperPass, llvm::PreservedAnalyses, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) PassBuilder.cpp:0:0
#31 0x00000000028afba4 llvm::PassManager<llvm::Module, llvm::AnalysisManager<llvm::Module> >::run(llvm::Module&, llvm::AnalysisManager<llvm::Module>&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x28afba4)
#32 0x0000000003615a65 (anonymous namespace)::EmitAssemblyHelper::EmitAssemblyWithNewPassManager(clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) BackendUtil.cpp:0:0
#33 0x000000000361024c clang::EmitBackendOutput(clang::DiagnosticsEngine&, clang::HeaderSearchOptions const&, clang::CodeGenOptions const&, clang::TargetOptions const&, clang::LangOptions const&, llvm::StringRef, llvm::Module*, clang::BackendAction, std::unique_ptr<llvm::raw_pwrite_stream, std::default_delete<llvm::raw_pwrite_stream> >) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x361024c)
#34 0x0000000003a8da60 clang::BackendConsumer::HandleTranslationUnit(clang::ASTContext&) CodeGenAction.cpp:0:0
#35 0x00000000041c73b4 clang::ParseAST(clang::Sema&, bool, bool) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x41c73b4)
#36 0x00000000039e2190 clang::FrontendAction::Execute() (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x39e2190)
#37 0x00000000039556df clang::CompilerInstance::ExecuteAction(clang::FrontendAction&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x39556df)
#38 0x0000000003a87b37 clang::ExecuteCompilerInvocation(clang::CompilerInstance*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x3a87b37)
#39 0x0000000001b4d708 cc1_main(llvm::ArrayRef<char const*>, char const*, void*) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x1b4d708)
#40 0x0000000001b4b25d ExecuteCC1Tool(llvm::SmallVectorImpl<char const*>&) driver.cpp:0:0
#41 0x00000000037f8512 void llvm::function_ref<void ()>::callback_fn<clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const::$_1>(long) Job.cpp:0:0
#42 0x0000000002ece957 llvm::CrashRecoveryContext::RunSafely(llvm::function_ref<void ()>) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x2ece957)
#43 0x00000000037f8077 clang::driver::CC1Command::Execute(llvm::ArrayRef<llvm::Optional<llvm::StringRef> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >*, bool*) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x37f8077)
#44 0x00000000037bfe48 clang::driver::Compilation::ExecuteCommand(clang::driver::Command const&, clang::driver::Command const*&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x37bfe48)
#45 0x00000000037c0117 clang::driver::Compilation::ExecuteJobs(clang::driver::JobList const&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) const (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x37c0117)
#46 0x00000000037d87e1 clang::driver::Driver::ExecuteCompilation(clang::driver::Compilation&, llvm::SmallVectorImpl<std::pair<int, clang::driver::Command const*> >&) (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x37d87e1)
#47 0x0000000001b4ab26 main (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x1b4ab26)
#48 0x00007fe3a84b5b25 __libc_start_main (/usr/lib/libc.so.6+0x27b25)
#49 0x0000000001b47ece _start (/home/nathan/cbl/github/tc-build/build/llvm/stage1/bin/clang-13+0x1b47ece)
clang-13: error: clang frontend command failed with exit code 134 (use -v to see invocation)
ClangBuiltLinux clang version 13.0.0 (https://github.com/llvm/llvm-project 0a2d4f3f24a377dc7d3cbed16d30603dc27554a8)
Target: aarch64-unknown-linux-gnu
Thread model: posix
InstalledDir: /home/nathan/cbl/github/tc-build/build/llvm/stage1/bin
clang-13: note: diagnostic msg: Error generating preprocessed source(s) - no preprocessable inputs.

[reames]

@nathanchance - I'd suggest reverting until @mkazantsev can investigate. He's offline for the next few hours due to time zones.

[nathanchance]

In D103959#2830963, @reames wrote:

@nathanchance - I'd suggest reverting until @mkazantsev can investigate. He's offline for the next few hours due to time zones.

Done, thanks!

f52666985d7011b539f26f54e09a5c89b62dad56

[mkazantsev]

Hi @nathanchance ! Thanks for revert. The failure doesn't make much sense to me though. My only idea is that this happens in unreachable code, where loop info may lie about something being a header. I'll try to reproduce this.

[mkazantsev]

Ok, we stepped on a loop that doesn't have a sole predecessor (I didn't even know it's possible, but looks like the loops weren't canonicalized). Reduced IR repro:

opt -S -loop-deletion

target datalayout = "e-m:e-i8:8:32-i16:16:32-i64:64-i128:128-n32:64-S128"
target triple = "aarch64-unknown-linux-gnu"

define dso_local i32 @hoge() local_unnamed_addr #0 {
bb:
  callbr void asm sideeffect "", "X"(i8* blockaddress(@hoge, %bb2)) #1
          to label %bb1 [label %bb2]

bb1:                                              ; preds = %bb
  br label %bb2

bb2:                                              ; preds = %bb2, %bb1, %bb
  %tmp = phi i32 [ undef, %bb1 ], [ %tmp3, %bb2 ], [ undef, %bb ]
  %tmp3 = tail call i32 bitcast (i32 (...)* @widget to i32 (i32)*)(i32 %tmp) #1
  br label %bb2
}

declare dso_local i32 @widget(...) local_unnamed_addr #0

Failure was exposed, but no caused by this patch. I will land a fix and then return this one.

llvm/lib/Transforms/Scalar/LoopDeletion.cpp

auto MarkLiveEdge = [&](BasicBlock *From, BasicBlock *To) {
     LiveBlocks.insert(To);
     LiveEdges.insert({ From, To });
   };
 
   auto MarkAllSuccessorsLive = [&](BasicBlock *BB) {
     for (auto *Succ : successors(BB))
       MarkLiveEdge(BB, Succ);
   };
 
-  // Check if there is only one predecessor on 1st iteration. Note that because
-  // we iterate in RPOT, we have already visited all its (non-latch)
-  // predecessors.
-  auto GetSolePredecessorOnFirstIteration = [&](BasicBlock * BB)->BasicBlock * {
+  // Check if there is only one value coming from all live predecessor blocks.
+  // Note that because we iterate in RPOT, we have already visited all its
+  // (non-latch) predecessors.
+  auto GetSoleInputOnFirstIteration = [&](PHINode & PN)->Value * {
+    BasicBlock *BB = PN.getParent();
     if (BB == Header)
-      return L->getLoopPredecessor();
-    BasicBlock *OnlyPred = nullptr;
+      return PN.getIncomingValueForBlock(L->getLoopPredecessor());
+    Value *OnlyInput = nullptr;
     for (auto *Pred : predecessors(BB))
-      if (OnlyPred != Pred && LiveEdges.count({ Pred, BB })) {
-        // 2 live preds.
-        if (OnlyPred)
+      if (LiveEdges.count({ Pred, BB })) {
+        Value *Incoming = PN.getIncomingValueForBlock(Pred);
+        // Two inputs.
+        if (OnlyInput && OnlyInput != Incoming)
           return nullptr;
-        OnlyPred = Pred;
+        OnlyInput = Incoming;
       }
 
-    assert(OnlyPred && "No live predecessors?");
-    return OnlyPred;
+    assert(OnlyInput && "No live predecessors?");
+    return OnlyInput;
   };
   DenseMap<Value *, Value *> FirstIterValue;
 
   // Use the following algorithm to prove we never take the latch on the 1st
   // iteration:
   // 1. Traverse in topological order, so that whenever we visit a block, all
   //    its predecessors are already visited.
   // 2. If we can prove that the block may have only 1 predecessor on the 1st
if (!LiveBlocks.count(BB))
       continue;
 
     // Skip inner loops.
     if (LI.getLoopFor(BB) != L) {
       MarkAllSuccessorsLive(BB);
       continue;
     }
 
-    // If this block has only one live pred, map its phis onto their SCEVs.
-    if (auto *OnlyPred = GetSolePredecessorOnFirstIteration(BB))
-      for (auto &PN : BB->phis()) {
-        if (!PN.getType()->isIntegerTy())
-          continue;
-        auto *Incoming = PN.getIncomingValueForBlock(OnlyPred);
-        if (DT.dominates(Incoming, BB->getTerminator())) {
-          Value *FirstIterV =
-              getValueOnFirstIteration(Incoming, FirstIterValue, SQ);
-          FirstIterValue[&PN] = FirstIterV;
-        }
-      }
+    // If Phi has only one input from all live input blocks, use it.
+      auto *Incoming = GetSoleInputOnFirstIteration(PN);
+      if (Incoming && DT.dominates(Incoming, BB->getTerminator())) {
 
     using namespace PatternMatch;
     ICmpInst::Predicate Pred;
     Value *LHS, *RHS;
     BasicBlock *IfTrue, *IfFalse;
     auto *Term = BB->getTerminator();
     // TODO: Handle switch.
     if (!match(Term, m_Br(m_ICmp(Pred, m_Value(LHS), m_Value(RHS)),

llvm/test/Transforms/LoopDeletion/eval_first_iteration.ll

 
 done:                                             ; preds = %backedge
   %sum.next.lcssa = phi i32 [ %sum.next, %backedge ]
   ret i32 %sum.next.lcssa
 
 failure:
   unreachable
 }
 
-; TODO: We can break the backedge here.
 define i32 @test_multiple_pred_2() {
 ; CHECK-LABEL: @test_multiple_pred_2(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[LOOP:%.*]]
 ; CHECK:       loop:
-; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[SUM_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[SUM:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ]
 ; CHECK-NEXT:    [[SUB:%.*]] = sub i32 4, [[SUM]]
 ; CHECK-NEXT:    [[IS_POSITIVE:%.*]] = icmp sgt i32 [[SUB]], 0
 ; CHECK-NEXT:    br i1 [[IS_POSITIVE]], label [[IF_TRUE:%.*]], label [[IF_FALSE:%.*]]
 ; CHECK:       if.true:
 ; CHECK-NEXT:    br i1 undef, label [[IF_TRUE_1:%.*]], label [[IF_TRUE_2:%.*]]
 ; CHECK:       if.true.1:
-; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK-NEXT:    br label [[BACKEDGE:%.*]]
 ; CHECK:       if.true.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false:
 ; CHECK-NEXT:    br i1 undef, label [[IF_FALSE_1:%.*]], label [[IF_FALSE_2:%.*]]
 ; CHECK:       if.false.1:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       if.false.2:
 ; CHECK-NEXT:    br label [[BACKEDGE]]
 ; CHECK:       backedge:
 ; CHECK-NEXT:    [[MERGE_PHI:%.*]] = phi i32 [ 0, [[IF_FALSE_1]] ], [ 0, [[IF_FALSE_2]] ], [ [[SUB]], [[IF_TRUE_1]] ], [ [[SUB]], [[IF_TRUE_2]] ]
-; CHECK-NEXT:    [[SUM_NEXT]] = add i32 [[SUM]], [[MERGE_PHI]]
+; CHECK-NEXT:    [[SUM_NEXT:%.*]] = add i32 [[SUM]], [[MERGE_PHI]]
 ; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp ne i32 [[SUM_NEXT]], 4
-; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[DONE:%.*]]
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[BACKEDGE_LOOP_CRIT_EDGE:%.*]], label [[DONE:%.*]]
+; CHECK:       backedge.loop_crit_edge:
+; CHECK-NEXT:    unreachable
 ; CHECK:       done:
 ; CHECK-NEXT:    [[SUM_NEXT_LCSSA:%.*]] = phi i32 [ [[SUM_NEXT]], [[BACKEDGE]] ]
 ; CHECK-NEXT:    ret i32 [[SUM_NEXT_LCSSA]]
 ; CHECK:       failure:
 ; CHECK-NEXT:    unreachable
 ;
 entry: