[SimpleLoopUnswitch] Preserve make.implicit in non-trivial unswitch if legal

[mkazantsev]

Summary

We can preserve make.implicit metadata in the split block if it is
guaranteed that after following the branch we always reach the block
where processing of null case happens, which is equivalent to
"initial condition must execute if the loop is entered".

[asbirlea]

lgtm

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2080

I'm wondering if there is a case where we'd rather always drop the metadata than incur the cost of computing loop safety info (i.e. if a flag should exist to have this option).

[mkazantsev]

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

2080

I can add such flag as a follow-up. Thanks for idea!

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

 #include "llvm/Analysis/GuardUtils.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/LoopIterator.h"
 #include "llvm/Analysis/LoopPass.h"
 #include "llvm/Analysis/MemorySSA.h"
 #include "llvm/Analysis/MemorySSAUpdater.h"
+#include "llvm/Analysis/MustExecute.h"
 #include "llvm/IR/BasicBlock.h"
 #include "llvm/IR/Constant.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/InstrTypes.h"
 #include "llvm/IR/Instruction.h"
 #include "llvm/IR/Instructions.h"
static void unswitchNontrivialInvariants(
   SmallDenseMap<BasicBlock *, BasicBlock *, 4> ClonedPHs;
   for (auto *SuccBB : UnswitchedSuccBBs) {
     VMaps.emplace_back(new ValueToValueMapTy());
     ClonedPHs[SuccBB] = buildClonedLoopBlocks(
         L, LoopPH, SplitBB, ExitBlocks, ParentBB, SuccBB, RetainedSuccBB,
         DominatingSucc, *VMaps.back(), DTUpdates, AC, DT, LI, MSSAU);
   }
 
-  // Drop metadata if we may break its semantics by moving this branch into the
+  // Drop metadata if we may break its semantics by moving this instr into the
   // split block.
-  // TODO: We can keep make.implicit metadata if we prove that TI always
-  // executes and we cannot leave unswitched loop before getting to null check
-  // block. See @test_may_keep_make_implicit_non_trivial.
+  if (TI.getMetadata(LLVMContext::MD_make_implicit)) {
+    // It is only legal to preserve make.implicit metadata if we are guaranteed
+    // to reach implicit null check block after following this branch.
+    ICFLoopSafetyInfo SafetyInfo;
+    SafetyInfo.computeLoopSafetyInfo(&L);
+    if (!SafetyInfo.isGuaranteedToExecute(TI, &DT, &L))
       TI.setMetadata(LLVMContext::MD_make_implicit, nullptr);
+  }
 
   // The stitching of the branched code back together depends on whether we're
   // doing full unswitching or not with the exception that we always want to
   // nuke the initial terminator placed in the split block.
   SplitBB->getTerminator()->eraseFromParent();
   if (FullUnswitch) {
     // Splice the terminator from the original loop and rewrite its
     // successors.

llvm/test/Transforms/SimpleLoopUnswitch/implicit-null-checks.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -enable-nontrivial-unswitch=true -simple-loop-unswitch -S < %s | FileCheck %s
 ; RUN: opt -enable-nontrivial-unswitch=true -passes='loop(unswitch),verify<loops>' -S < %s | FileCheck %s
 
+declare void @may_exit()
 declare void @throw_npe()
 
 ; It is illegal to preserve make_implicit notion of the condition being
 ; unswitched because we may exit loop before we reach the condition, so
 ; there is no guarantee that following implicit branch always means getting
 ; to throw_npe block.
 define i32 @test_should_drop_make_implicit(i32* %p1, i32* %p2) {
 ; CHECK-LABEL: @test_should_drop_make_implicit(

 throw_npe:
   call void @throw_npe()
   unreachable
 
 exit:
   ret i32 %x
 }
 
-; TODO: This is a non-trivial unswitch, but it would still be legal to keep
-; !make.implicit in entry block. Currently we do not have enough analysis to
-; prove it.
 define i32 @test_may_keep_make_implicit_non_trivial(i32* %p1, i32* %p2) {
 ; CHECK-LABEL: @test_may_keep_make_implicit_non_trivial(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i32* [[P2:%.*]], null
-; CHECK-NOT:     !make.implicit
-; CHECK-NEXT:    br i1 [[NULL_CHECK]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK-NEXT:    br i1 [[NULL_CHECK]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]], !make.implicit !0
 ; CHECK:       entry.split.us:
 ; CHECK-NEXT:    br label [[LOOP_US:%.*]]
 ; CHECK:       loop.us:
 ; CHECK-NEXT:    [[IV_US:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT_US]] ]
 ; CHECK-NEXT:    [[X_US:%.*]] = load i32, i32* [[P1:%.*]], align 4
 ; CHECK-NEXT:    [[INNER_BLOCK_COND_US:%.*]] = icmp eq i32 [[X_US]], 0
 ; CHECK-NEXT:    br i1 [[INNER_BLOCK_COND_US]], label [[INNER_BLOCK_US:%.*]], label [[NULL_CHECK_BLOCK_US:%.*]]
 ; CHECK:       inner_block.us:

 throw_npe:
   call void @throw_npe()
   unreachable
 
 exit:
   ret i32 %x
 }
 
+; Here make.implicit notion should be dropped because of exiting call.
+define i32 @test_should_drop_make_implicit_exiting_call(i32* %p1, i32* %p2) {
+; CHECK-LABEL: @test_should_drop_make_implicit_exiting_call(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i32* [[P2:%.*]], null
+; CHECK-NOT:     !make.implicit
+; CHECK-NEXT:    br i1 [[NULL_CHECK]], label [[ENTRY_SPLIT_US:%.*]], label [[ENTRY_SPLIT:%.*]]
+; CHECK:       entry.split.us:
+; CHECK-NEXT:    br label [[LOOP_US:%.*]]
+; CHECK:       loop.us:
+; CHECK-NEXT:    [[IV_US:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT_US]] ]
+; CHECK-NEXT:    call void @may_exit()
+; CHECK-NEXT:    [[X_US:%.*]] = load i32, i32* [[P1:%.*]], align 4
+; CHECK-NEXT:    [[SIDE_EXIT_COND_US:%.*]] = icmp eq i32 [[X_US]], 0
+; CHECK-NEXT:    br label [[THROW_NPE_SPLIT_US:%.*]]
+; CHECK:       throw_npe.split.us:
+; CHECK-NEXT:    br label [[THROW_NPE:%.*]]
+; CHECK:       entry.split:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    call void @may_exit()
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P1]], align 4
+; CHECK-NEXT:    [[SIDE_EXIT_COND:%.*]] = icmp eq i32 [[X]], 0
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 10000
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       throw_npe:
+; CHECK-NEXT:    call void @throw_npe()
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    [[X_LCSSA1:%.*]] = phi i32 [ [[X]], [[BACKEDGE]] ]
+; CHECK-NEXT:    ret i32 [[X_LCSSA1]]
+;
+entry:
+  %null_check = icmp eq i32* %p2, null
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  call void @may_exit()
+  %x = load i32, i32* %p1
+  %side_exit_cond = icmp eq i32 %x, 0
+  br i1 %null_check, label %throw_npe, label %backedge, !make.implicit !0
+
+backedge:
+  %iv.next = add i32 %iv,1
+  %loop_cond = icmp slt i32 %iv.next, 10000
+  br i1 %loop_cond, label %loop, label %exit
+
+throw_npe:
+  call void @throw_npe()
+  unreachable
+
+exit:
+  ret i32 %x
+}
+
+; Here exiting call goes after the null check, so make.implicit may be preserved.
+define i32 @test_may_keep_make_implicit_exiting_call(i32* %p1, i32* %p2) {
+; CHECK-LABEL: @test_may_keep_make_implicit_exiting_call(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[NULL_CHECK:%.*]] = icmp eq i32* [[P2:%.*]], null
+; CHECK-NEXT:    br i1 [[NULL_CHECK]], label [[THROW_NPE:%.*]], label [[ENTRY_SPLIT:%.*]], !make.implicit !0
+; CHECK:       entry.split:
+; CHECK-NEXT:    br label [[LOOP:%.*]]
+; CHECK:       loop:
+; CHECK-NEXT:    [[IV:%.*]] = phi i32 [ 0, [[ENTRY_SPLIT]] ], [ [[IV_NEXT:%.*]], [[BACKEDGE:%.*]] ]
+; CHECK-NEXT:    [[X:%.*]] = load i32, i32* [[P1:%.*]], align 4
+; CHECK-NEXT:    [[SIDE_EXIT_COND:%.*]] = icmp eq i32 [[X]], 0
+; CHECK-NEXT:    br label [[BACKEDGE]]
+; CHECK:       backedge:
+; CHECK-NEXT:    [[IV_NEXT]] = add i32 [[IV]], 1
+; CHECK-NEXT:    [[LOOP_COND:%.*]] = icmp slt i32 [[IV_NEXT]], 10000
+; CHECK-NEXT:    call void @may_exit()
+; CHECK-NEXT:    br i1 [[LOOP_COND]], label [[LOOP]], label [[EXIT:%.*]]
+; CHECK:       throw_npe:
+; CHECK-NEXT:    call void @throw_npe()
+; CHECK-NEXT:    unreachable
+; CHECK:       exit:
+; CHECK-NEXT:    [[X_LCSSA1:%.*]] = phi i32 [ [[X]], [[BACKEDGE]] ]
+; CHECK-NEXT:    ret i32 [[X_LCSSA1]]
+;
+entry:
+  %null_check = icmp eq i32* %p2, null
+  br label %loop
+loop:
+  %iv = phi i32 [0, %entry], [%iv.next, %backedge]
+  %x = load i32, i32* %p1
+  %side_exit_cond = icmp eq i32 %x, 0
+  br i1 %null_check, label %throw_npe, label %backedge, !make.implicit !0
+
+backedge:
+  %iv.next = add i32 %iv,1
+  %loop_cond = icmp slt i32 %iv.next, 10000
+  call void @may_exit()
+  br i1 %loop_cond, label %loop, label %exit
+
+throw_npe:
+  call void @throw_npe()
+  unreachable
+
+exit:
+  ret i32 %x
+}
+
 !0 = !{}