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