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