add non-trivial LoopUnswitch FuncPass

[drcut]

Summary

Since non-trivial LoopUnswitch may need FunctionAnalysis, we plan to migrate the current LoopPass implementation to FunctionPass

llvm/include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h

 //===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
+//
+// This file contains two Pass: a LoopPass and a FunctionPass. The LoopPass
+// applies both trivial and non-trivial LoopUnswitch, while the FunctionPass
+// only applies non-trivial LoopUnswitch.
+//===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
 #define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
 
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/Analysis/LoopAnalysisManager.h"
 #include "llvm/IR/PassManager.h"
 
public:
 
   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
 
   void printPipeline(raw_ostream &OS,
                      function_ref<StringRef(StringRef)> MapClassName2PassName);
 };
 
+// This pass only applies non-trivial LoopUnswitch, and share code with the
+// above LoopPass implementation. We re-implement the non-trivial LoopUnswitch
+// with FunctionPass becuase we may need FunctionAnalysis to apply
+// non-trivial LoopUnswitch,
+class FuncSimpleLoopUnswitchPass
+    : public PassInfoMixin<FuncSimpleLoopUnswitchPass> {
+public:
+  PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM);
+};
+
 /// Create the legacy pass object for the simple loop unswitcher.
 ///
 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
 
 } // end namespace llvm
 
 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H

llvm/lib/Passes/PassRegistry.def

 FUNCTION_PASS("print-memderefs", MemDerefPrinterPass(dbgs()))
 FUNCTION_PASS("reassociate", ReassociatePass())
 FUNCTION_PASS("redundant-dbg-inst-elim", RedundantDbgInstEliminationPass())
 FUNCTION_PASS("reg2mem", RegToMemPass())
 FUNCTION_PASS("scalarize-masked-mem-intrin", ScalarizeMaskedMemIntrinPass())
 FUNCTION_PASS("scalarizer", ScalarizerPass())
 FUNCTION_PASS("separate-const-offset-from-gep", SeparateConstOffsetFromGEPPass())
 FUNCTION_PASS("sccp", SCCPPass())
+FUNCTION_PASS("loop-unswitch-func", FuncSimpleLoopUnswitchPass())
 FUNCTION_PASS("sink", SinkingPass())
 FUNCTION_PASS("slp-vectorizer", SLPVectorizerPass())
 FUNCTION_PASS("slsr", StraightLineStrengthReducePass())
 FUNCTION_PASS("speculative-execution", SpeculativeExecutionPass())
 FUNCTION_PASS("sroa", SROAPass())
 FUNCTION_PASS("strip-gc-relocates", StripGCRelocates())
 FUNCTION_PASS("structurizecfg", StructurizeCFGPass())
 FUNCTION_PASS("tailcallelim", TailCallElimPass())

llvm/lib/Transforms/Scalar/SimpleLoopUnswitch.cpp

-///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow ---------===//
+///===- SimpleLoopUnswitch.cpp - Hoist loop-invariant control flow
+///---------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
+//
+// This file implements LoopUnswitch for both trivial and non-trivial cases
+//
+//===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/Scalar/SimpleLoopUnswitch.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/SetVector.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/SmallVector.h"
PreservedAnalyses SimpleLoopUnswitchPass::run(Loop &L, LoopAnalysisManager &AM,
   assert(AR.DT.verify(DominatorTree::VerificationLevel::Fast));
 
   auto PA = getLoopPassPreservedAnalyses();
   if (AR.MSSA)
     PA.preserve<MemorySSAAnalysis>();
   return PA;
 }
 
+PreservedAnalyses FuncSimpleLoopUnswitchPass::run(Function &F,
+                                                  FunctionAnalysisManager &AM) {
+  LoopInfo &LI = AM.getResult<LoopAnalysis>(F);
+  auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
+  auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
+  auto MSSA = &AM.getResult<MemorySSAAnalysis>(F).getMSSA();
+  Optional<MemorySSAUpdater> MSSAU;
+  if (MSSA) {
+    MSSAU = MemorySSAUpdater(MSSA);
+    if (VerifyMemorySSA)
+      MSSA->verifyMemorySSA();
+  }
+  bool Changed = false;
+  for (const auto &L : LI) {
+    Changed |= simplifyLoop(L, &DT, &LI, &SE, nullptr, MSSAU.getPointer(),
+                            /*PreserveLCSSA=*/false);
+    Changed |= formLCSSARecursively(*L, DT, &LI, &SE);
+  }
+
+  SmallPriorityWorklist<Loop *, 4> Worklist;
+  appendLoopsToWorklist(LI, Worklist);
+  while (!Worklist.empty()) {
+    Loop &L = *Worklist.pop_back_val();
+    LLVM_DEBUG(dbgs() << "Unswitching loop in " << F.getName() << ": " << L
+                      << "\n");
+
+    // Save the current loop name in a variable so that we can report it even
+    // after it has been deleted.
+    std::string LoopName = std::string(L.getName());
+
+    auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
+
+    auto UnswitchCB = [&L, &LAM, &LoopName, &Worklist](
+                          bool CurrentLoopValid, bool PartiallyInvariant,
+                          ArrayRef<Loop *> NewLoops) {
+      // If we did a non-trivial unswitch, we have added new (cloned) loops.
+      if (!NewLoops.empty())
+        appendLoopsToWorklist(NewLoops, Worklist);
+
+      // If the current loop remains valid, we should revisit it to catch any
+      // other unswitch opportunities. Otherwise, we need to mark it as deleted.
+      if (CurrentLoopValid) {
+        if (PartiallyInvariant) {
+          // Mark the new loop as partially unswitched, to avoid unswitching on
+          // the same condition again.
+          auto &Context = L.getHeader()->getContext();
+          MDNode *DisableUnswitchMD = MDNode::get(
+              Context,
+              MDString::get(Context, "llvm.loop.unswitch.partial.disable"));
+          MDNode *NewLoopID = makePostTransformationMetadata(
+              Context, L.getLoopID(), {"llvm.loop.unswitch.partial"},
+              {DisableUnswitchMD});
+          L.setLoopID(NewLoopID);
+        } else
+          Worklist.insert(&L);
+      } else
+        LAM.clear(L, LoopName);
+    };
+
+    auto DestroyLoopCB = [&LAM](Loop &L, StringRef Name) {
+      LAM.clear(L, Name);
+    };
+    Changed |= unswitchLoop(
+        L, AM.getResult<DominatorTreeAnalysis>(F),
+        AM.getResult<LoopAnalysis>(F), AM.getResult<AssumptionAnalysis>(F),
+        AM.getResult<AAManager>(F), AM.getResult<TargetIRAnalysis>(F),
+        /*Trivial=*/false, /*NonTrivial=*/true,
+        UnswitchCB, &AM.getResult<ScalarEvolutionAnalysis>(F),
+        MSSAU.hasValue() ? MSSAU.getPointer() : nullptr, DestroyLoopCB);
+  }
+  if (!Changed)
+    return PreservedAnalyses::all();
+
+  if (MSSA && VerifyMemorySSA)
+    MSSA->verifyMemorySSA();
+
+  // Historically this pass has had issues with the dominator tree so verify it
+  // in asserts builds.
+  assert(AM.getResult<DominatorTreeAnalysis>(F).verify(
+      DominatorTree::VerificationLevel::Fast));
+
+  auto PA = getLoopPassPreservedAnalyses();
+  if (MSSA)
+    PA.preserve<MemorySSAAnalysis>();
+  return PA;
+}
+
 void SimpleLoopUnswitchPass::printPipeline(
     raw_ostream &OS, function_ref<StringRef(StringRef)> MapClassName2PassName) {
   static_cast<PassInfoMixin<SimpleLoopUnswitchPass> *>(this)->printPipeline(
       OS, MapClassName2PassName);
 
   OS << "<";
   OS << (NonTrivial ? "" : "no-") << "nontrivial;";
   OS << (Trivial ? "" : "no-") << "trivial";

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

 ; 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
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
+; RUN:     -unswitch-num-initial-unscaled-candidates=0 -unswitch-siblings-toplevel-div=16 \
+; RUN:     -passes='loop-unswitch-func,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.
 ;
 ; The tests below also run licm, because it is needed to hoist out
 ; loop-invariant freeze instructions, which otherwise may block further
 ; unswitching.
 ;

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

 ; 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=8 \
 ; 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=8 \
+; RUN:     -passes='loop-unswitch-func,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:
 ; 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 | FileCheck %s --check-prefixes=LOOP5
 ;
 ; 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 | FileCheck %s --check-prefixes=LOOP5
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
+; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=1 \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP5
+;
 ; With relaxed candidates multiplier (unscaled candidates == 8) and with relaxed
 ; siblings multiplier for top-level loops (toplevel-div == 8) we should get
 ;    2^(num conds) == 2^5 == 32
 ; copies of the loop:
 ;
 ; 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 | FileCheck %s --check-prefixes=LOOP32
 ;
 ; 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 | FileCheck %s --check-prefixes=LOOP32
 ;
+; RUN: opt < %s -enable-unswitch-cost-multiplier=true \
+; RUN:     -unswitch-num-initial-unscaled-candidates=8 -unswitch-siblings-toplevel-div=8 \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP32
+;
 ; Similarly get
 ;    2^(num conds) == 2^5 == 32
 ; 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 | FileCheck %s --check-prefixes=LOOP32
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \

llvm/test/Transforms/SimpleLoopUnswitch/exponential-nontrivial-unswitch2.ll

 ;
 ; 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 | FileCheck %s --check-prefixes=LOOP1
 ;
 ; RUN: opt < %s -enable-unswitch-cost-multiplier=false \
 ; 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=false \
+; RUN:     -passes='loop-unswitch-func,print<loops>' -disable-output 2>&1 | FileCheck %s --check-prefixes=LOOP1
+;
 ;
 ; Single loop, not unswitched
 ; LOOP1:     Loop at depth 1 containing:
 ; LOOP1-NOT: Loop at depth 1 containing:
 
 declare void @bar()
 
 define void @loop_simple5(i32* %addr, i1 %c1, i1 %c2, i1 %c3, i1 %c4, i1 %c5) {

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

 ; Specifically exercise the cost modeling for non-trivial loop unswitching.
 ;
 ; RUN: opt -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
 ; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -unswitch-threshold=5 -verify-memoryssa -S < %s | FileCheck %s
+; RUN: opt -passes='loop-unswitch-func,verify<loops>' -unswitch-threshold=5 -S < %s | FileCheck %s
 
 declare void @a()
 declare void @b()
 declare void @x()
 
 ; First establish enough code size in the duplicated 'loop_begin' block to
 ; suppress unswitching.
 define void @test_no_unswitch(i1* %ptr, i1 %cond) {

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -freeze-loop-unswitch-cond -passes='loop(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
 ; RUN: opt -freeze-loop-unswitch-cond -passes='loop-mssa(simple-loop-unswitch<nontrivial>),verify<loops>' -S < %s | FileCheck %s
 ; RUN: opt -freeze-loop-unswitch-cond -simple-loop-unswitch -enable-nontrivial-unswitch -verify-memoryssa -S < %s | FileCheck %s
+; RUN: opt -freeze-loop-unswitch-cond -passes='loop-unswitch-func,verify<loops>' -S < %s | FileCheck %s
 
 declare i32 @a()
 declare i32 @b()
 declare i32 @c()
 declare i32 @d()
 
 declare void @sink1(i32)
 declare void @sink2(i32)

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

-; RUN: opt < %s -enable-loop-distribute -passes='loop-distribute,loop-mssa(simple-loop-unswitch<nontrivial>),loop-distribute' -o /dev/null -S -debug-pass-manager=verbose 2>&1 | FileCheck %s
-
+; RUN: opt < %s -enable-loop-distribute -passes='loop-distribute,loop-mssa(simple-loop-unswitch<nontrivial>),loop-distribute' -o /dev/null -S -debug-pass-manager=verbose 2>&1 | FileCheck %s --check-prefixes=LOOPPASS
+; RUN: opt < %s -enable-loop-distribute -passes='loop-distribute,loop-unswitch-func,loop-distribute' -o /dev/null -S -debug-pass-manager=verbose 2>&1 | FileCheck %s --check-prefixes=FUNCPASS
 
 ; Running loop-distribute will result in LoopAccessAnalysis being required and
 ; cached in the LoopAnalysisManagerFunctionProxy.
 ;
 ; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 2 containing: %loop_a_inner<header><latch><exiting>
 
 
 ; Then simple-loop-unswitch is removing/replacing some loops (resulting in
 ; Loop objects used as key in the analyses cache is destroyed). So here we
 ; want to see that any analysis results cached on the destroyed loop is
 ; cleared. A special case here is that loop_a_inner is destroyed when
 ; unswitching the parent loop.
 ;
 ; The bug solved and verified by this test case was related to the
 ; SimpleLoopUnswitch not marking the Loop as removed, so we missed clearing
 ; the analysis caches.
 ;
-; CHECK: Running pass: SimpleLoopUnswitchPass on Loop at depth 1 containing: %loop_begin<header>,%loop_b,%loop_b_inner,%loop_b_inner_exit,%loop_a,%loop_a_inner,%loop_a_inner_exit,%latch<latch><exiting>
-; CHECK-NEXT: Clearing all analysis results for: loop_a_inner
+; LOOPPASS: Running pass: SimpleLoopUnswitchPass on Loop at depth 1 containing: %loop_begin<header>,%loop_b,%loop_b_inner,%loop_b_inner_exit,%loop_a,%loop_a_inner,%loop_a_inner_exit,%latch<latch><exiting>
+; FUNCPASS: Running pass: FuncSimpleLoopUnswitchPass on test6
+; CHECK: Clearing all analysis results for: loop_a_inner
 
 
 ; When running loop-distribute the second time we can see that loop_a_inner
 ; isn't analysed because the loop no longer exists (instead we find a new loop,
 ; loop_a_inner.us). This kind of verifies that it was correct to remove the
 ; loop_a_inner related analysis above.
 ;
 ; CHECK: Running analysis: LoopAccessAnalysis on Loop at depth 2 containing: %loop_a_inner.us<header><latch><exiting>

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

 ; REQUIRES: asserts
 ; RUN: opt -passes='simple-loop-unswitch<nontrivial>' -disable-output -S < %s
 ; RUN: opt -passes='loop-mssa(simple-loop-unswitch<nontrivial>)' -disable-output -S < %s
 ; RUN: opt -simple-loop-unswitch -enable-nontrivial-unswitch -disable-output -S < %s
+; RUN: opt -passes='loop-unswitch-func' -disable-output -S < %s
 
 ; This loop shouldn't trigger asserts in SimpleLoopUnswitch.
 define void @test_redundant_switch(i1* %ptr, i32 %cond) {
 entry:
   br label %loop_begin
 
 loop_begin:
   switch i32 %cond, label %loop_body [

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

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -passes='simple-loop-unswitch<nontrivial>' -S < %s | FileCheck %s
+; RUN: opt -passes='loop-unswitch-func' -S < %s | FileCheck %s
 
 ; If we try to replace uses of `true` outside of `@foo`, we'll see it here.
 define i1 @bar() {
 ; CHECK-LABEL: @bar(
 ; CHECK-NEXT:    ret i1 true
 ;
   ret i1 true
 }