1 //===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is distributed under the University of Illinois Open Source 6 // License. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H 11 #define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H 12 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" 17 18 namespace llvm { 19 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: 23 /// 24 /// for (...) if (lic) 25 /// A for (...) 26 /// if (lic) A; B; C 27 /// B else 28 /// C for (...) 29 /// A; C 30 /// 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. 34 /// 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. 37 /// 38 /// There is a taxonomy of unswitching that we use to classify different forms 39 /// of this transformaiton: 40 /// 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 43 /// code duplication. 44 /// 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. 52 /// 53 /// This pass always does trivial, full unswitching for both branches and 54 /// switches. For branches, it also always does trivial, partial unswitching. 55 /// 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. 59 /// 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> { 64 bool NonTrivial; 65 66 public: 67 SimpleLoopUnswitchPass(bool NonTrivial = false) : NonTrivial(NonTrivial) {} 68 69 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 70 LoopStandardAnalysisResults &AR, LPMUpdater &U); 71 }; 72 73 /// Create the legacy pass object for the simple loop unswitcher. 74 /// 75 /// See the documentaion for `SimpleLoopUnswitchPass` for details. 76 Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false); 77 78 } // end namespace llvm 79 80 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H 81
