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