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)
NonTrivial(NonTrivial)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