LLVM  10.0.0svn
SimpleLoopUnswitch.h
Go to the documentation of this file.
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 
13 #include "llvm/Analysis/LoopInfo.h"
14 #include "llvm/IR/PassManager.h"
16 
17 namespace llvm {
18 
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:
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 ///
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.
62 class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
63  bool NonTrivial;
64 
65 public:
66  SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {}
67 
70 };
71 
72 /// Create the legacy pass object for the simple loop unswitcher.
73 ///
74 /// See the documentaion for `SimpleLoopUnswitchPass` for details.
75 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
76 
77 } // end namespace llvm
78 
79 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
This class represents lattice values for constants.
Definition: AllocatorList.h:23
This header provides classes for managing a pipeline of passes over loops in LLVM IR...
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
This pass transforms loops that contain branches or switches on loop- invariant conditions to have mu...
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:372
This header provides classes for managing per-loop analyses.
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Pass * createSimpleLoopUnswitchLegacyPass(bool NonTrivial=false)
Create the legacy pass object for the simple loop unswitcher.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
A container for analyses that lazily runs them and caches their results.
This header defines various interfaces for pass management in LLVM.
SimpleLoopUnswitchPass(bool NonTrivial=false)