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
18namespace 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.
63class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
64 bool NonTrivial;
65
66public:
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.
76Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
77
78} // end namespace llvm
79
80#endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
81