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 | |
12 | #include "llvm/ADT/STLFunctionalExtras.h" |
13 | #include "llvm/Analysis/LoopAnalysisManager.h" |
14 | #include "llvm/IR/PassManager.h" |
15 | |
16 | namespace llvm { |
17 | |
18 | class LPMUpdater; |
19 | class Loop; |
20 | class StringRef; |
21 | class raw_ostream; |
22 | |
23 | /// This pass transforms loops that contain branches or switches on loop- |
24 | /// invariant conditions to have multiple loops. For example, it turns the left |
25 | /// into the right code: |
26 | /// |
27 | /// for (...) if (lic) |
28 | /// A for (...) |
29 | /// if (lic) A; B; C |
30 | /// B else |
31 | /// C for (...) |
32 | /// A; C |
33 | /// |
34 | /// This can increase the size of the code exponentially (doubling it every time |
35 | /// a loop is unswitched) so we only unswitch if the resultant code will be |
36 | /// smaller than a threshold. |
37 | /// |
38 | /// This pass expects LICM to be run before it to hoist invariant conditions out |
39 | /// of the loop, to make the unswitching opportunity obvious. |
40 | /// |
41 | /// There is a taxonomy of unswitching that we use to classify different forms |
42 | /// of this transformaiton: |
43 | /// |
44 | /// - Trival unswitching: this is when the condition can be unswitched without |
45 | /// cloning any code from inside the loop. A non-trivial unswitch requires |
46 | /// code duplication. |
47 | /// |
48 | /// - Full unswitching: this is when the branch or switch is completely moved |
49 | /// from inside the loop to outside the loop. Partial unswitching removes the |
50 | /// branch from the clone of the loop but must leave a (somewhat simplified) |
51 | /// branch in the original loop. While theoretically partial unswitching can |
52 | /// be done for switches, the requirements are extreme - we need the loop |
53 | /// invariant input to the switch to be sufficient to collapse to a single |
54 | /// successor in each clone. |
55 | /// |
56 | /// This pass always does trivial, full unswitching for both branches and |
57 | /// switches. For branches, it also always does trivial, partial unswitching. |
58 | /// |
59 | /// If enabled (via the constructor's `NonTrivial` parameter), this pass will |
60 | /// additionally do non-trivial, full unswitching for branches and switches, and |
61 | /// will do non-trivial, partial unswitching for branches. |
62 | /// |
63 | /// Because partial unswitching of switches is extremely unlikely to be possible |
64 | /// in practice and significantly complicates the implementation, this pass does |
65 | /// not currently implement that in any mode. |
66 | class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> { |
67 | bool NonTrivial; |
68 | bool Trivial; |
69 | |
70 | public: |
71 | SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true) |
72 | : NonTrivial(NonTrivial), Trivial(Trivial) {} |
73 | |
74 | PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, |
75 | LoopStandardAnalysisResults &AR, LPMUpdater &U); |
76 | |
77 | void printPipeline(raw_ostream &OS, |
78 | function_ref<StringRef(StringRef)> MapClassName2PassName); |
79 | }; |
80 | |
81 | } // end namespace llvm |
82 | |
83 | #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H |
84 | |