LLVM  16.0.0git
SimpleLoopUnswitch.h
Go to the documentation of this file.
1 //===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
10 #define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
11 
14 #include "llvm/IR/PassManager.h"
15 
16 namespace llvm {
17 
18 class LPMUpdater;
19 class Loop;
20 class Pass;
21 class StringRef;
22 class raw_ostream;
23 
24 /// This pass transforms loops that contain branches or switches on loop-
25 /// invariant conditions to have multiple loops. For example, it turns the left
26 /// into the right code:
27 ///
28 /// for (...) if (lic)
29 /// A for (...)
30 /// if (lic) A; B; C
31 /// B else
32 /// C for (...)
33 /// A; C
34 ///
35 /// This can increase the size of the code exponentially (doubling it every time
36 /// a loop is unswitched) so we only unswitch if the resultant code will be
37 /// smaller than a threshold.
38 ///
39 /// This pass expects LICM to be run before it to hoist invariant conditions out
40 /// of the loop, to make the unswitching opportunity obvious.
41 ///
42 /// There is a taxonomy of unswitching that we use to classify different forms
43 /// of this transformaiton:
44 ///
45 /// - Trival unswitching: this is when the condition can be unswitched without
46 /// cloning any code from inside the loop. A non-trivial unswitch requires
47 /// code duplication.
48 ///
49 /// - Full unswitching: this is when the branch or switch is completely moved
50 /// from inside the loop to outside the loop. Partial unswitching removes the
51 /// branch from the clone of the loop but must leave a (somewhat simplified)
52 /// branch in the original loop. While theoretically partial unswitching can
53 /// be done for switches, the requirements are extreme - we need the loop
54 /// invariant input to the switch to be sufficient to collapse to a single
55 /// successor in each clone.
56 ///
57 /// This pass always does trivial, full unswitching for both branches and
58 /// switches. For branches, it also always does trivial, partial unswitching.
59 ///
60 /// If enabled (via the constructor's `NonTrivial` parameter), this pass will
61 /// additionally do non-trivial, full unswitching for branches and switches, and
62 /// will do non-trivial, partial unswitching for branches.
63 ///
64 /// Because partial unswitching of switches is extremely unlikely to be possible
65 /// in practice and significantly complicates the implementation, this pass does
66 /// not currently implement that in any mode.
67 class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
68  bool NonTrivial;
69  bool Trivial;
70 
71 public:
72  SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true)
73  : NonTrivial(NonTrivial), Trivial(Trivial) {}
74 
77 
78  void printPipeline(raw_ostream &OS,
79  function_ref<StringRef(StringRef)> MapClassName2PassName);
80 };
81 
82 /// Create the legacy pass object for the simple loop unswitcher.
83 ///
84 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
85 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
86 
87 } // end namespace llvm
88 
89 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::createSimpleLoopUnswitchLegacyPass
Pass * createSimpleLoopUnswitchLegacyPass(bool NonTrivial=false)
Create the legacy pass object for the simple loop unswitcher.
Definition: SimpleLoopUnswitch.cpp:3294
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1979
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:546
llvm::LoopStandardAnalysisResults
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
Definition: LoopAnalysisManager.h:51
llvm::SimpleLoopUnswitchPass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: SimpleLoopUnswitch.cpp:3186
LoopAnalysisManager.h
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
STLFunctionalExtras.h
llvm::SimpleLoopUnswitchPass
This pass transforms loops that contain branches or switches on loop- invariant conditions to have mu...
Definition: SimpleLoopUnswitch.h:67
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::LPMUpdater
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Definition: LoopPassManager.h:262
llvm::SimpleLoopUnswitchPass::SimpleLoopUnswitchPass
SimpleLoopUnswitchPass(bool NonTrivial=false, bool Trivial=true)
Definition: SimpleLoopUnswitch.h:72
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::SimpleLoopUnswitchPass::run
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Definition: SimpleLoopUnswitch.cpp:3114
PassManager.h
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42