[SimpleLoopUnswitch] Run LICM for nested unswitching tests.

[fhahn]

Summary

When enabling freeze-loop-unswitch-cond the inserted freeze instruction
may block unswitching of parent loops if they get inserted in a block in
the parent loop (as the llvm::Loop-based invariance check only checks
whether an instruction is in a loop block or not).

In the optimization pipeline, LICM is responsible to hoist out loop
invariant instructions to enable further unswitching. Also run LICM for
nested unswitching tests in preparation for flipping the default of
freeze-loop-unswitch-cond.

[nikic]

LG, but maybe add a brief comment in the tests for why LICM is run?

[asbirlea]

+ 1 to please clarify in the test why this is necessary.
Without the context, the question will be: why not generate the IR after LICM and only test SLU? Clarify the test needs the sequence SLU on inner loop, licm to hoist freeze condition and then SLU on outer loop can be done.

[asbirlea]

As a side note, the fact the freeze instruction needs licm and simple loop unswitch interleaved, will likely affect the plan we had around splitting off the non-trivial unswitch functionality into a separate function pass (the context for that is regarding using divergence analysis: https://reviews.llvm.org/D109762)
It seems like tracking the added freeze instructions and including the functionality of hoisting them as part of the "new" non-trivial SLU pass will resolve this, but I'd like to hear folks feedback on this.

[fhahn]

In D124251#3468747, @asbirlea wrote:

As a side note, the fact the freeze instruction needs licm and simple loop unswitch interleaved, will likely affect the plan we had around splitting off the non-trivial unswitch functionality into a separate function pass (the context for that is regarding using divergence analysis: https://reviews.llvm.org/D109762)
It seems like tracking the added freeze instructions and including the functionality of hoisting them as part of the "new" non-trivial SLU pass will resolve this, but I'd like to hear folks feedback on this.

We could either hoist the freeze instructions or generate them at a place where no hoisting is required. At least as things are at the moment, I am not sure if it is worth it though, as it is just for testing in cases with nested loops that get unswitched from the inside out. Note that we don't only have this problem with freeze instructions we generate but potentially also with AND/ORs we generate when we have multiple invariant conditions.

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

 ;
 ; There should be just a single copy of each loop when strictest mutiplier
 ; candidates formula (unscaled candidates == 0) is enforced:
 
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
+; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
 ; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; When we relax the candidates part of a multiplier formula
 ; (unscaled candidates == 4) we start getting  some unswitches,
 ; which leads to siblings multiplier kicking in.
 ;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
-; RUN:     -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV1
+; The tests below also run licm, because it is needed to hoist out
+; 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(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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
 ;
 ; 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(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-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-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(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-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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=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:
 ;

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

 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \
 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; When we relax the candidates part of a multiplier formula
-; When we relax the candidates part of a multiplier formula
 ; (unscaled candidates == 2) we start getting some unswitches in outer loops,
 ; which leads to siblings multiplier kicking in.
 ;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
-; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1
+; The tests below also run licm, because it is needed to hoist out
+; loop-invariant freeze instructions, which otherwise may block further
+; unswitching.
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-UNSCALE3-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=3 -unswitch-siblings-toplevel-div=2 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
-;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
-; RUN:     -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-UNSCALE3-DIV2
 ;
 ; With disabled cost-multiplier we get maximal possible amount of unswitches.
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
-;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-MAX
 ;
 ; Single loop nest, not unswitched
 ; LOOP1:     Loop at depth 1 containing:
 ; LOOP1-NOT:  Loop at depth 1 containing:
 ; LOOP1:     Loop at depth 2 containing:
 ; LOOP1-NOT:  Loop at depth 2 containing:
 ; LOOP1:     Loop at depth 3 containing:

llvm/test/Transforms/SimpleLoopUnswitch/exponential-switch-unswitch.ll

 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
 ; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; With relaxed candidates multiplier (unscaled candidates == 8) we should allow
 ; some unswitches to happen until siblings multiplier starts kicking in:
 ;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
-; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX
+; The tests below also run licm, because it is needed to hoist out
+; loop-invariant freeze instructions, which otherwise may block further
+; unswitching.
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=1 \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-RELAX
 ;
 ; With relaxed candidates multiplier (unscaled candidates == 8) and with relaxed
 ; siblings multiplier for top-level loops (toplevel-div == 8) we should get
 ; considerably more copies of the loop (especially top-level ones).
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
 ; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=8 \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX2
-;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
-; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=8 \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-RELAX2
 ;
 ; We get hundreds of copies of the loop when cost multiplier is disabled:
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
-; RUN:     -passes='loop(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
-; RUN:     sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
-;
-; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
-; RUN:     -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&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-MAX
 
 ; Single loop nest, not unswitched
 ; LOOP1:     Loop at depth 1 containing:
 ; LOOP1-NOT: Loop at depth 1 containing:
 ; LOOP1:     Loop at depth 2 containing:
 ; LOOP1-NOT: Loop at depth 2 containing:
 ;