LLVM 19.0.0git
Go to the documentation of this file.
1//===- SimpleLoopUnswitch.h - Hoist loop-invariant control flow -*- C++ -*-===//
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
14#include "llvm/IR/PassManager.h"
17namespace llvm {
19class LPMUpdater;
20class Loop;
21class StringRef;
22class raw_ostream;
25 : public AnalysisInfoMixin<ShouldRunExtraSimpleLoopUnswitch> {
27 struct Result {
28 bool invalidate(Loop &L, const PreservedAnalyses &PA,
30 // Check whether the analysis has been explicitly invalidated. Otherwise,
31 // it remains preserved.
33 return !PAC.preservedWhenStateless();
34 }
35 };
39 return Result();
40 }
42 static bool isRequired() { return true; }
48 auto PA = PreservedAnalyses::all();
50 PA.intersect(LoopPassManager::run(L, AM, AR, U));
52 return PA;
53 }
55 static bool isRequired() { return true; }
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:
62/// for (...) if (lic)
63/// A for (...)
64/// if (lic) A; B; C
65/// B else
66/// C for (...)
67/// A; C
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.
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.
76/// There is a taxonomy of unswitching that we use to classify different forms
77/// of this transformaiton:
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.
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.
91/// This pass always does trivial, full unswitching for both branches and
92/// switches. For branches, it also always does trivial, partial unswitching.
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.
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.
101class SimpleLoopUnswitchPass : public PassInfoMixin<SimpleLoopUnswitchPass> {
102 bool NonTrivial;
103 bool Trivial;
106 SimpleLoopUnswitchPass(bool NonTrivial = false, bool Trivial = true)
107 : NonTrivial(NonTrivial), Trivial(Trivial) {}
113 function_ref<StringRef(StringRef)> MapClassName2PassName);
116} // end namespace llvm
This header provides classes for managing per-loop analyses.
This header provides classes for managing a pipeline of passes over loops in LLVM IR.
This header defines various interfaces for pass management in LLVM.
raw_pwrite_stream & OS
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:360
A container for analyses that lazily runs them and caches their results.
Definition: PassManager.h:321
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:492
This class provides an interface for updating the loop pass manager based on mutations to the loop ne...
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:44
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
Add either a loop pass or a loop-nest pass to the pass manager.
A set of analyses that are preserved following a run of a transformation pass.
Definition: Analysis.h:109
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: Analysis.h:115
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: Analysis.h:264
This pass transforms loops that contain branches or switches on loop- invariant conditions to have mu...
SimpleLoopUnswitchPass(bool NonTrivial=false, bool Trivial=true)
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
An efficient, type-erasing, non-owning reference to a callable.
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:97
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: Analysis.h:26
PreservedAnalyses run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR, LPMUpdater &U)
The adaptor from a function pass to a loop pass computes these analyses and makes them available to t...
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:74
bool invalidate(Loop &L, const PreservedAnalyses &PA, LoopAnalysisManager::Invalidator &)
Result run(Loop &L, LoopAnalysisManager &AM, LoopStandardAnalysisResults &AR)