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 #include "llvm/Transforms/Scalar/LoopPassManager.h" 16 17 namespace llvm { 18 19 class LPMUpdater; 20 class Loop; 21 class StringRef; 22 class raw_ostream; 23 24 struct ShouldRunExtraSimpleLoopUnswitch 25 : public AnalysisInfoMixin<ShouldRunExtraSimpleLoopUnswitch> { 26 static AnalysisKey Key; 27 struct Result { invalidateShouldRunExtraSimpleLoopUnswitch::Result28 bool invalidate(Loop &L, const PreservedAnalyses &PA, 29 LoopAnalysisManager::Invalidator &) { 30 // Check whether the analysis has been explicitly invalidated. Otherwise, 31 // it remains preserved. 32 auto PAC = PA.getChecker<ShouldRunExtraSimpleLoopUnswitch>(); 33 return !PAC.preservedWhenStateless(); 34 } 35 }; 36 runShouldRunExtraSimpleLoopUnswitch37 Result run(Loop &L, LoopAnalysisManager &AM, 38 LoopStandardAnalysisResults &AR) { 39 return Result(); 40 } 41 isRequiredShouldRunExtraSimpleLoopUnswitch42 static bool isRequired() { return true; } 43 }; 44 45 struct ExtraSimpleLoopUnswitchPassManager : public LoopPassManager { runExtraSimpleLoopUnswitchPassManager46 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 47 LoopStandardAnalysisResults &AR, LPMUpdater &U) { 48 auto PA = PreservedAnalyses::all(); 49 if (AM.getCachedResult<ShouldRunExtraSimpleLoopUnswitch>(L)) 50 PA.intersect(LoopPassManager::run(L, AM, AR, U)); 51 PA.abandon<ShouldRunExtraSimpleLoopUnswitch>(); 52 return PA; 53 } 54 isRequiredExtraSimpleLoopUnswitchPassManager55 static bool isRequired() { return true; } 56 }; 57 58 /// This pass transforms loops that contain branches or switches on loop- 59 /// invariant conditions to have multiple loops. For example, it turns the left 60 /// into the right code: 61 /// 62 /// for (...) if (lic) 63 /// A for (...) 64 /// if (lic) A; B; C 65 /// B else 66 /// C for (...) 67 /// A; C 68 /// 69 /// This can increase the size of the code exponentially (doubling it every time 70 /// a loop is unswitched) so we only unswitch if the resultant code will be 71 /// smaller than a threshold. 72 /// 73 /// This pass expects LICM to be run before it to hoist invariant conditions out 74 /// of the loop, to make the unswitching opportunity obvious. 75 /// 76 /// There is a taxonomy of unswitching that we use to classify different forms 77 /// of this transformaiton: 78 /// 79 /// - Trival unswitching: this is when the condition can be unswitched without 80 /// cloning any code from inside the loop. A non-trivial unswitch requires 81 /// code duplication. 82 /// 83 /// - Full unswitching: this is when the branch or switch is completely moved 84 /// from inside the loop to outside the loop. Partial unswitching removes the 85 /// branch from the clone of the loop but must leave a (somewhat simplified) 86 /// branch in the original loop. While theoretically partial unswitching can 87 /// be done for switches, the requirements are extreme - we need the loop 88 /// invariant input to the switch to be sufficient to collapse to a single 89 /// successor in each clone. 90 /// 91 /// This pass always does trivial, full unswitching for both branches and 92 /// switches. For branches, it also always does trivial, partial unswitching. 93 /// 94 /// If enabled (via the constructor's `NonTrivial` parameter), this pass will 95 /// additionally do non-trivial, full unswitching for branches and switches, and 96 /// will do non-trivial, partial unswitching for branches. 97 /// 98 /// Because partial unswitching of switches is extremely unlikely to be possible 99 /// in practice and significantly complicates the implementation, this pass does 100 /// not currently implement that in any mode. 101 class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> { 102 bool NonTrivial; 103 bool Trivial; 104 105 public: 106 SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true) NonTrivial(NonTrivial)107 : NonTrivial(NonTrivial), Trivial(Trivial) {} 108 109 PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, 110 LoopStandardAnalysisResults &AR, LPMUpdater &U); 111 112 void printPipeline(raw_ostream &OS, 113 function_ref<StringRef(StringRef)> MapClassName2PassName); 114 }; 115 116 } // end namespace llvm 117 118 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H 119