1 //===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
11 #define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
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"
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:
24 /// for (...) if (lic)
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.
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.
38 /// There is a taxonomy of unswitching that we use to classify different forms
39 /// of this transformaiton:
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
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.
53 /// This pass always does trivial, full unswitching for both branches and
54 /// switches. For branches, it also always does trivial, partial unswitching.
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.
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> {
67 SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {}
69 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
70 LoopStandardAnalysisResults &AR, LPMUpdater &U);
73 /// Create the legacy pass object for the simple loop unswitcher.
75 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
76 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
78 } // end namespace llvm
80 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H