Yi Kong | b551264 | 2019-04-18 17:31:16 -0700 | [diff] [blame^] | 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/Analysis/LoopAnalysisManager.h" |
| 13 | #include "llvm/Analysis/LoopInfo.h" |
| 14 | #include "llvm/IR/PassManager.h" |
| 15 | #include "llvm/Transforms/Scalar/LoopPassManager.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 | |
| 68 | PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, |
| 69 | LoopStandardAnalysisResults &AR, LPMUpdater &U); |
| 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 |