modify the insertion of freeze instructions for SLU pass

[drcut]

Summary

Directly insert the freeze instructions generated by SLU to the place it will be hoisted by LICM. Thus, we do not require LICM as a following pass for SLU.

[drcut]

Fix bug for hoisting freeze instruction

[fhahn]

Hmm, aren't there other places in the code that rely on instructions being hoisted out by LICM? Unless I am mis-remembering, It's not clear to me if/why freeze should be treated in a special way.

[drcut]

In D127765#3814900, @fhahn wrote:

Hmm, aren't there other places in the code that rely on instructions being hoisted out by LICM? Unless I am mis-remembering, It's not clear to me if/why freeze should be treated in a special way.

This patch is related to D127698, for migrating SLU from LoopPass to FuncPass. In the original O3 pipeline, both LICM and SLU are in the same LoopPass Manager. After migrating SLU to FuncPass, it will be removed from the LoopPass Manager. So some loops won't be changed by LICM after applying SLU. Thus, we need to apply parts of LICM in SLU. We found the only instruction we need to hoist is the freeze instruction, as it is the only instruction inserted by SLU.

[aeubanks]

we've given up on that approach though, it's probably best to abandon these patches as to not confuse people who stumble across this

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

if (FullUnswitch) {
 
     // First wire up the moved terminator to the preheaders.
     if (BI) {
       BasicBlock *ClonedPH = ClonedPHs.begin()->second;
       BI->setSuccessor(ClonedSucc, ClonedPH);
       BI->setSuccessor(1 - ClonedSucc, LoopPH);
       Value *Cond = skipTrivialSelect(BI->getCondition());
       if (InsertFreeze) {
-        if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, BI, &DT))
-          Cond = new FreezeInst(Cond, Cond->getName() + ".fr", BI);
+        if (!isGuaranteedNotToBeUndefOrPoison(Cond, &AC, BI, &DT)) {
+          // directly insert the freeze inst to the place it will be hoisted by
+          // LICM, so that we do not require LICM as a following pass
+          Instruction *InsertPoint = BI;
+          while (Loop *OuterLoop = LI.getLoopFor(InsertPoint->getParent())) {
+            if (OuterLoop->isLoopInvariant(Cond)) {
+              InsertPoint = OuterLoop->getLoopPreheader()->getTerminator();
+            } else {
+              break;
+            }
+          }
+          Cond = new FreezeInst(Cond, Cond->getName() + ".fr", InsertPoint);
+        }
       }
       BI->setCondition(Cond);
       DTUpdates.push_back({DominatorTree::Insert, SplitBB, ClonedPH});
     } else {
       assert(SI && "Must either be a branch or switch!");
 
       // Walk the cases and directly update their successors.
       assert(SI->getDefaultDest() == RetainedSuccBB &&

llvm/test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch-nested.ll

 ; loop-invariant freeze instructions, which otherwise may block further
 ; unswitching.
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=1 \
 ; RUN:     -passes='loop-mssa(licm,simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV1
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
+; RUN:     -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=1 \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | \
+; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV1
+;
 ; NB: sort -b is essential here and below, otherwise blanks might lead to different
 ; order depending on locale.
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=2 \
 ; RUN:     -passes='loop-mssa(licm,simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV2
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
+; RUN:     -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=2 \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | \
+; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV2
+;
 ; Get
 ;    2^(num conds) == 2^5 = 32
 ; loop nests when cost multiplier is disabled:
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
 ; RUN:     -passes='loop-mssa(licm,simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
 ; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP32
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | \
+; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP32
+;
 ; Single loop nest, not unswitched
 ; LOOP1:     Loop at depth 1 containing:
 ; LOOP1:     Loop at depth 2 containing:
 ; LOOP1:     Loop at depth 3 containing:
 ; LOOP1-NOT: Loop at depth {{[0-9]+}} containing:
 ;
 ; Half unswitched loop nests, with unscaled4 and div1 it gets less depth1 loops unswitched
 ; since they have more cost.

llvm/test/Transforms/SimpleLoopUnswitch/nontrivial-unswitch.ll

 ; predecessors of the unswitched loop header. That can allow us to find the loop
 ; through multiple different paths.
 define void @test21(i1 %a, i1 %b) {
 ; CHECK-LABEL: @test21(
 bb:
   br label %bb3
 ; CHECK-NOT:     br i1 %a
 ;
-; CHECK:         %[[FROZEN:.+]] = freeze i1 %a
-; CHECK-NEXT:    br i1 %[[FROZEN]], label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]]
+; CHECK:         %[[FROZENA:.+]] = freeze i1 %a
+; CHECK:         %[[FROZENB:.+]] = freeze i1 %b
+; CHECK-NEXT:    br i1 %[[FROZENA]], label %[[BB_SPLIT_US:.*]], label %[[BB_SPLIT:.*]]
 ;
 ; CHECK-NOT:     br i1 %a
 ; CHECK-NOT:     br i1 %b
 ;
 ; CHECK:       [[BB_SPLIT]]:
 ; CHECK:         br i1 %b
 ;
 ; CHECK-NOT:     br i1 %a