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