This is an archive of the discontinued LLVM Phabricator instance.

Differential D124251

[SimpleLoopUnswitch] Run LICM for nested unswitching tests.
ClosedPublic

Authored by fhahn on Apr 22 2022, 5:06 AM.

Details

Reviewers
asbirlea
nikic
aeubanks
aqjune
Commits
rG2fee8dd621bb: [SimpleLoopUnswitch] Run LICM for nested unswitching tests.
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.

Diff Detail

Unit TestsFailed

TimeTest
60,040 msx64 debian > libFuzzer.libFuzzer::large.test

Event Timeline

fhahn created this revision.Apr 22 2022, 5:06 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 22 2022, 5:07 AM
fhahn requested review of this revision.Apr 22 2022, 5:07 AM
Herald added a project: Restricted Project. · View Herald TranscriptApr 22 2022, 5:07 AM
fhahn added a child revision: D124252: [SimpleLoopUnswitch] Enable freezing of conditions by default..Apr 22 2022, 5:14 AM
nikic accepted this revision.Apr 22 2022, 5:30 AM

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

This revision is now accepted and ready to land.Apr 22 2022, 5:30 AM
Harbormaster completed remote builds in B160832: Diff 424444.Apr 22 2022, 6:39 AM
asbirlea added a comment.Apr 22 2022, 12:18 PM

+ 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 added a comment.Apr 22 2022, 1:01 PM

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 added a comment.Apr 22 2022, 1:23 PM
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.

This revision was landed with ongoing or failed builds.Apr 25 2022, 4:49 AM
Closed by commit rG2fee8dd621bb: [SimpleLoopUnswitch] Run LICM for nested unswitching tests. (authored by fhahn). · Explain Why
This revision was automatically updated to reflect the committed changes.
fhahn added a commit: rG2fee8dd621bb: [SimpleLoopUnswitch] Run LICM for nested unswitching tests..

Revision Contents

Diff 424444

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

; ;
; There should be just a single copy of each loop when strictest mutiplier ; There should be just a single copy of each loop when strictest mutiplier
; candidates formula (unscaled candidates == 0) is enforced: ; candidates formula (unscaled candidates == 0) is enforced:
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \ ; 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: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \ ; 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: -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: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=1 \ ; 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: -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: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \ ; 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 ; 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 == 4) we start getting some unswitches, ; (unscaled candidates == 4) we start getting some unswitches,
; which leads to siblings multiplier kicking in. ; which leads to siblings multiplier kicking in.
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=1 \ ; 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: -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-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV1 ; 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 ; NB: sort -b is essential here and below, otherwise blanks might lead to different
; order depending on locale. ; order depending on locale.
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=4 -unswitch-siblings-toplevel-div=2 \ ; 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: -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-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV2 ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE4-DIV2
; ;
; Get ; Get
; 2^(num conds) == 2^5 = 32 ; 2^(num conds) == 2^5 = 32
; loop nests when cost multiplier is disabled: ; loop nests when cost multiplier is disabled:
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop(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
;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP32 ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP32
; ;
; Single loop nest, not unswitched ; Single loop nest, not unswitched
; LOOP1: Loop at depth 1 containing: ; LOOP1: Loop at depth 1 containing:
; LOOP1: Loop at depth 2 containing: ; LOOP1: Loop at depth 2 containing:
; LOOP1: Loop at depth 3 containing: ; LOOP1: Loop at depth 3 containing:
; LOOP1-NOT: Loop at depth {{[0-9]+}} containing: ; LOOP1-NOT: Loop at depth {{[0-9]+}} containing:
; ;
▲ Show 20 Lines • Show All 94 Lines • Show Last 20 Lines

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

Show All 24 Lines
; ;
; When we relax the candidates part of a multiplier formula ; When we relax the candidates part of a multiplier formula
; 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, ; (unscaled candidates == 2) we start getting some unswitches in outer loops,
; which leads to siblings multiplier kicking in. ; which leads to siblings multiplier kicking in.
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=1 \ ; 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: -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
;
; 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: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV1 ; 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 ; NB: sort -b is essential here and below, otherwise blanks might lead to different
; order depending on locale. ; order depending on locale.
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=3 -unswitch-siblings-toplevel-div=2 \ ; 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: -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
;
; 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: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2 ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-UNSCALE3-DIV2
; ;
; With disabled cost-multiplier we get maximal possible amount of unswitches. ; With disabled cost-multiplier we get maximal possible amount of unswitches.
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop(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
;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
; ;
; Single loop nest, not unswitched ; Single loop nest, not unswitched
; LOOP1: Loop at depth 1 containing: ; LOOP1: Loop at depth 1 containing:
; LOOP1-NOT: Loop at depth 1 containing: ; LOOP1-NOT: Loop at depth 1 containing:
; LOOP1: Loop at depth 2 containing: ; LOOP1: Loop at depth 2 containing:
; LOOP1-NOT: Loop at depth 2 containing: ; LOOP1-NOT: Loop at depth 2 containing:
; LOOP1: Loop at depth 3 containing: ; LOOP1: Loop at depth 3 containing:
▲ Show 20 Lines • Show All 102 Lines • Show Last 20 Lines

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

Show All 24 Lines
; RUN: -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \ ; 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 ; 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 ; With relaxed candidates multiplier (unscaled candidates == 8) we should allow
; some unswitches to happen until siblings multiplier starts kicking in: ; some unswitches to happen until siblings multiplier starts kicking in:
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=1 \ ; 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: -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
;
; 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: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX
; ;
; With relaxed candidates multiplier (unscaled candidates == 8) and with relaxed ; With relaxed candidates multiplier (unscaled candidates == 8) and with relaxed
; siblings multiplier for top-level loops (toplevel-div == 8) we should get ; siblings multiplier for top-level loops (toplevel-div == 8) we should get
; considerably more copies of the loop (especially top-level ones). ; considerably more copies of the loop (especially top-level ones).
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=true \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
; RUN: -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=8 \ ; 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: -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
;
; 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: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX2 ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-RELAX2
; ;
; We get hundreds of copies of the loop when cost multiplier is disabled: ; We get hundreds of copies of the loop when cost multiplier is disabled:
; ;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \ ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop(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
;
; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
; RUN: -passes='loop-mssa(simple-loop-unswitch<nontrivial>),print<loops>' -disable-output 2>&1 | \
; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX ; RUN: sort -b -k 1 | FileCheck %s --check-prefixes=LOOP-MAX
; Single loop nest, not unswitched ; Single loop nest, not unswitched
; LOOP1: Loop at depth 1 containing: ; LOOP1: Loop at depth 1 containing:
; LOOP1-NOT: Loop at depth 1 containing: ; LOOP1-NOT: Loop at depth 1 containing:
; LOOP1: Loop at depth 2 containing: ; LOOP1: Loop at depth 2 containing:
; LOOP1-NOT: Loop at depth 2 containing: ; LOOP1-NOT: Loop at depth 2 containing:
; ;
▲ Show 20 Lines • Show All 68 Lines • Show Last 20 Lines