Line data    Source code

       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          81 :   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