Transforms/Scalar/SimpleLoopUnswitch.h

0001 //===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
0010 #define LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H
0011
0012 #include "llvm/ADT/STLFunctionalExtras.h"
0013 #include "llvm/Analysis/LoopAnalysisManager.h"
0014 #include "llvm/IR/PassManager.h"
0015 #include "llvm/Transforms/Scalar/LoopPassManager.h"
0016 #include "llvm/Transforms/Utils/ExtraPassManager.h"
0017
0018 namespace llvm {
0019
0020 class LPMUpdater;
0021 class Loop;
0022 class StringRef;
0023 class raw_ostream;
0024
0025 /// This pass transforms loops that contain branches or switches on loop-
0026 /// invariant conditions to have multiple loops. For example, it turns the left
0027 /// into the right code:
0028 ///
0029 ///  for (...)                  if (lic)
0030 ///    A                          for (...)
0031 ///    if (lic)                     A; B; C
0032 ///      B                      else
0033 ///    C                          for (...)
0034 ///                                 A; C
0035 ///
0036 /// This can increase the size of the code exponentially (doubling it every time
0037 /// a loop is unswitched) so we only unswitch if the resultant code will be
0038 /// smaller than a threshold.
0039 ///
0040 /// This pass expects LICM to be run before it to hoist invariant conditions out
0041 /// of the loop, to make the unswitching opportunity obvious.
0042 ///
0043 /// There is a taxonomy of unswitching that we use to classify different forms
0044 /// of this transformaiton:
0045 ///
0046 /// - Trival unswitching: this is when the condition can be unswitched without
0047 ///   cloning any code from inside the loop. A non-trivial unswitch requires
0048 ///   code duplication.
0049 ///
0050 /// - Full unswitching: this is when the branch or switch is completely moved
0051 ///   from inside the loop to outside the loop. Partial unswitching removes the
0052 ///   branch from the clone of the loop but must leave a (somewhat simplified)
0053 ///   branch in the original loop. While theoretically partial unswitching can
0054 ///   be done for switches, the requirements are extreme - we need the loop
0055 ///   invariant input to the switch to be sufficient to collapse to a single
0056 ///   successor in each clone.
0057 ///
0058 /// This pass always does trivial, full unswitching for both branches and
0059 /// switches. For branches, it also always does trivial, partial unswitching.
0060 ///
0061 /// If enabled (via the constructor's `NonTrivial` parameter), this pass will
0062 /// additionally do non-trivial, full unswitching for branches and switches, and
0063 /// will do non-trivial, partial unswitching for branches.
0064 ///
0065 /// Because partial unswitching of switches is extremely unlikely to be possible
0066 /// in practice and significantly complicates the implementation, this pass does
0067 /// not currently implement that in any mode.
0068 class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
0069   bool NonTrivial;
0070   bool Trivial;
0071
0072 public:
0073   SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true)
0074       : NonTrivial(NonTrivial), Trivial(Trivial) {}
0075
0076   PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
0077                         LoopStandardAnalysisResults &AR, LPMUpdater &U);
0078
0079   void printPipeline(raw_ostream &OS,
0080                      function_ref<StringRef(StringRef)> MapClassName2PassName);
0081 };
0082
0083 /// A marker analysis to determine if SimpleLoopUnswitch should run again on a
0084 /// given loop.
0085 struct ShouldRunExtraSimpleLoopUnswitch
0086     : public ShouldRunExtraPasses<ShouldRunExtraSimpleLoopUnswitch>,
0087       public AnalysisInfoMixin<ShouldRunExtraSimpleLoopUnswitch> {
0088   static AnalysisKey Key;
0089 };
0090
0091 } // end namespace llvm
0092
0093 #endif // LLVM_TRANSFORMS_SCALAR_SIMPLELOOPUNSWITCH_H