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