blob: 68c121560b13ee86971d82c1b4251330d6b350da [file] [log] [blame]
//===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
#include "llvm/ADT/STLFunctionalExtras.h"
#include "llvm/Analysis/LoopAnalysisManager.h"
#include "llvm/IR/PassManager.h"
namespace llvm {
class LPMUpdater;
class Loop;
class Pass;
class StringRef;
class raw_ostream;
/// This pass transforms loops that contain branches or switches on loop-
/// invariant conditions to have multiple loops. For example, it turns the left
/// into the right code:
/// for (...) if (lic)
/// A for (...)
/// if (lic) A; B; C
/// B else
/// C for (...)
/// A; C
/// This can increase the size of the code exponentially (doubling it every time
/// a loop is unswitched) so we only unswitch if the resultant code will be
/// smaller than a threshold.
/// This pass expects LICM to be run before it to hoist invariant conditions out
/// of the loop, to make the unswitching opportunity obvious.
/// There is a taxonomy of unswitching that we use to classify different forms
/// of this transformaiton:
/// - Trival unswitching: this is when the condition can be unswitched without
/// cloning any code from inside the loop. A non-trivial unswitch requires
/// code duplication.
/// - Full unswitching: this is when the branch or switch is completely moved
/// from inside the loop to outside the loop. Partial unswitching removes the
/// branch from the clone of the loop but must leave a (somewhat simplified)
/// branch in the original loop. While theoretically partial unswitching can
/// be done for switches, the requirements are extreme - we need the loop
/// invariant input to the switch to be sufficient to collapse to a single
/// successor in each clone.
/// This pass always does trivial, full unswitching for both branches and
/// switches. For branches, it also always does trivial, partial unswitching.
/// If enabled (via the constructor's `NonTrivial` parameter), this pass will
/// additionally do non-trivial, full unswitching for branches and switches, and
/// will do non-trivial, partial unswitching for branches.
/// Because partial unswitching of switches is extremely unlikely to be possible
/// in practice and significantly complicates the implementation, this pass does
/// not currently implement that in any mode.
class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
bool NonTrivial;
bool Trivial;
SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true)
: NonTrivial(NonTrivial), Trivial(Trivial) {}
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM,
LoopStandardAnalysisResults &AR, LPMUpdater &U);
void printPipeline(raw_ostream &OS,
function_ref<StringRef(StringRef)> MapClassName2PassName);
/// Create the legacy pass object for the simple loop unswitcher.
/// See the documentaion for `SimpleLoopUnswitchPass` for details.
Pass *createSimpleLoopUnswitchLegacyPass(bool NonTrivial = false);
} // end namespace llvm