[LoopUtils] Consider unreachable-terminated blocks as deoptimizing

[dmakogon]

Summary

Previously in function getExpectedExitLoopLatchBranch we considered a block deoptimizing if it had a terminating deoptimize call.
Now updated to it to keep in sync with almost the same logic in LoopPeel (see https://reviews.llvm.org/D110922).
From that patch:

Added support for peeling loops with "deoptimizing" exits - such exits that it or any of its children (or any of their children, etc) either has a @llvm.experimental.deoptimize call
prior to the terminating return instruction of this basic block or is terminated with unreachable. All blocks in the the sequence must have a single successor, maybe except for the > last one.
Previously we only checked the exit block for being deoptimizing. Now we check if the last reachable block from the exit is deoptimizing.

So now we can consider a block deoptimizing if it meets the condition from the quote.
This should help peel loops which have profile data and which have such exits that all paths starting from them converge to a unreachable terminated block or a block which has a terminating deopt call.

[mkazantsev]

Any test?

[dmakogon]

Added test and fixed getExpectedExitLoopLatchBranch annotation

[reames]

This is not a comment on the code, but a comment on the commit message.

"deoptimizing" has a very specific meaning. An unreachable block is *not* deoptimizing. Given that, the description on the review makes zero sense. (As in, without looking at the code, I literally had no idea what you were trying for.) You need to rework the commit message before this is meaningfully reviewable.

llvm/lib/Transforms/Utils/LoopUtils.cpp

void llvm::breakLoopBackedge(Loop *L, DominatorTree &DT, ScalarEvolution &SE,
   // caused a block to be removed from the parent loop (see loop_nest_lcssa
   // test case in zero-btc.ll for an example), thus changing the parent's
   // exit blocks.  If that happened, we need to rebuild LCSSA on the outermost
   // loop which might have a had a block removed.
   if (OutermostLoop != L)
     formLCSSARecursively(*OutermostLoop, DT, &LI, &SE);
 }
 
 
 /// Checks if \p L has single exit through latch block except possibly
-/// "deoptimizing" exits. Returns branch instruction terminating the loop
-/// latch if above check is successful, nullptr otherwise.
+/// "deoptimizing" (@llvm.experimental.deoptimize or unreachable-terminated)
+/// exits or such exits that all paths starting from them converge
+/// to a block that either has a @llvm.experimental.deoptimize call
+/// prior to its terminating return instruction or is terminated by unreachable.
+/// Returns branch instruction terminating the loop latch if above check is
+/// successful, nullptr otherwise.
 static BranchInst *getExpectedExitLoopLatchBranch(Loop *L) {
   BasicBlock *Latch = L->getLoopLatch();
   if (!Latch)
     return nullptr;
 
   BranchInst *LatchBR = dyn_cast<BranchInst>(Latch->getTerminator());
   if (!LatchBR || LatchBR->getNumSuccessors() != 2 || !L->isLoopExiting(Latch))
     return nullptr;
 
   assert((LatchBR->getSuccessor(0) == L->getHeader() ||
           LatchBR->getSuccessor(1) == L->getHeader()) &&
          "At least one edge out of the latch must go to the header");
 
   SmallVector<BasicBlock *, 4> ExitBlocks;
   L->getUniqueNonLatchExitBlocks(ExitBlocks);
-  if (any_of(ExitBlocks, [](const BasicBlock *EB) {
-        return !EB->getTerminatingDeoptimizeCall();
+
+  if (any_of(ExitBlocks, [&](const BasicBlock *EB) {
+        return !IsBlockFollowedByDeoptOrUnreachable(EB);
       }))
     return nullptr;
 
   return LatchBR;
 }
 
 Optional<unsigned>
 llvm::getLoopEstimatedTripCount(Loop *L,

llvm/test/Transforms/LoopUnroll/peel-multiple-unreachable-exits.ll

 unreachable.term:
   call void @baz()
   unreachable
 }
 
 define void @peel_exits_to_blocks_branch_to_unreachable_block_with_profile(i32* %ptr, i32 %N, i32 %x, i1 %c.1) !prof !0 {
 ; CHECK-LABEL: @peel_exits_to_blocks_branch_to_unreachable_block_with_profile(
 ; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL_BEGIN:%.*]]
+; CHECK:       loop.header.peel.begin:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL:%.*]]
+; CHECK:       loop.header.peel:
+; CHECK-NEXT:    [[C_PEEL:%.*]] = icmp ult i32 1, [[N:%.*]]
+; CHECK-NEXT:    br i1 [[C_PEEL]], label [[THEN_PEEL:%.*]], label [[ELSE_PEEL:%.*]], !prof [[PROF4:![0-9]+]]
+; CHECK:       else.peel:
+; CHECK-NEXT:    [[C_2_PEEL:%.*]] = icmp eq i32 1, [[X:%.*]]
+; CHECK-NEXT:    br i1 [[C_2_PEEL]], label [[EXIT_2:%.*]], label [[LOOP_LATCH_PEEL:%.*]]
+; CHECK:       then.peel:
+; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[EXIT_1:%.*]], label [[LOOP_LATCH_PEEL]]
+; CHECK:       loop.latch.peel:
+; CHECK-NEXT:    [[M_PEEL:%.*]] = phi i32 [ 0, [[THEN_PEEL]] ], [ [[X]], [[ELSE_PEEL]] ]
+; CHECK-NEXT:    [[GEP_PEEL:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i32 1
+; CHECK-NEXT:    store i32 [[M_PEEL]], i32* [[GEP_PEEL]], align 4
+; CHECK-NEXT:    [[IV_NEXT_PEEL:%.*]] = add nuw nsw i32 1, 1
+; CHECK-NEXT:    [[C_3_PEEL:%.*]] = icmp ult i32 [[IV_NEXT_PEEL]], [[N]]
+; CHECK-NEXT:    br i1 [[C_3_PEEL]], label [[LOOP_HEADER_PEEL_NEXT:%.*]], label [[EXIT:%.*]], !prof [[PROF4]]
+; CHECK:       loop.header.peel.next:
+; CHECK-NEXT:    br label [[LOOP_HEADER_PEEL_NEXT1:%.*]]
+; CHECK:       loop.header.peel.next1:
+; CHECK-NEXT:    br label [[ENTRY_PEEL_NEWPH:%.*]]
+; CHECK:       entry.peel.newph:
 ; CHECK-NEXT:    br label [[LOOP_HEADER:%.*]]
 ; CHECK:       loop.header:
-; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 1, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
-; CHECK-NEXT:    [[C:%.*]] = icmp ult i32 [[IV]], [[N:%.*]]
-; CHECK-NEXT:    br i1 [[C]], label [[THEN:%.*]], label [[ELSE:%.*]], !prof [[PROF3:![0-9]+]]
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ [[IV_NEXT_PEEL]], [[ENTRY_PEEL_NEWPH]] ], [ [[IV_NEXT:%.*]], [[LOOP_LATCH:%.*]] ]
+; CHECK-NEXT:    br i1 true, label [[THEN:%.*]], label [[ELSE:%.*]], !prof [[PROF4]]
 ; CHECK:       then:
-; CHECK-NEXT:    br i1 [[C_1:%.*]], label [[EXIT_1:%.*]], label [[LOOP_LATCH]]
+; CHECK-NEXT:    br i1 [[C_1]], label [[EXIT_1_LOOPEXIT:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       else:
-; CHECK-NEXT:    [[C_2:%.*]] = icmp eq i32 [[IV]], [[X:%.*]]
-; CHECK-NEXT:    br i1 [[C_2]], label [[EXIT_2:%.*]], label [[LOOP_LATCH]]
+; CHECK-NEXT:    br i1 true, label [[EXIT_2_LOOPEXIT:%.*]], label [[LOOP_LATCH]]
 ; CHECK:       loop.latch:
 ; CHECK-NEXT:    [[M:%.*]] = phi i32 [ 0, [[THEN]] ], [ [[X]], [[ELSE]] ]
-; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, i32* [[PTR:%.*]], i32 [[IV]]
+; CHECK-NEXT:    [[GEP:%.*]] = getelementptr i32, i32* [[PTR]], i32 [[IV]]
 ; CHECK-NEXT:    store i32 [[M]], i32* [[GEP]], align 4
 ; CHECK-NEXT:    [[IV_NEXT]] = add nuw nsw i32 [[IV]], 1
 ; CHECK-NEXT:    [[C_3:%.*]] = icmp ult i32 [[IV_NEXT]], [[N]]
-; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP_HEADER]], label [[EXIT:%.*]], !prof [[PROF3]]
+; CHECK-NEXT:    br i1 [[C_3]], label [[LOOP_HEADER]], label [[EXIT_LOOPEXIT:%.*]], !prof [[PROF4]], !llvm.loop [[LOOP5:![0-9]+]]
+; CHECK:       exit.loopexit:
+; CHECK-NEXT:    br label [[EXIT]]
 ; CHECK:       exit:
 ; CHECK-NEXT:    ret void
+; CHECK:       exit.1.loopexit:
+; CHECK-NEXT:    br label [[EXIT_1]]
 ; CHECK:       exit.1:
 ; CHECK-NEXT:    call void @foo()
 ; CHECK-NEXT:    br label [[UNREACHABLE_TERM:%.*]]
+; CHECK:       exit.2.loopexit:
+; CHECK-NEXT:    br label [[EXIT_2]]
 ; CHECK:       exit.2:
 ; CHECK-NEXT:    call void @bar()
 ; CHECK-NEXT:    br label [[UNREACHABLE_TERM]]
 ; CHECK:       unreachable.term:
 ; CHECK-NEXT:    call void @baz()
 ; CHECK-NEXT:    unreachable
 ;
 entry: