include/llvm/Transforms/Scalar/SimpleLoopUnswitch.h

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