LLVM  16.0.0git
LoopVectorize.h
Go to the documentation of this file.
1 //===- LoopVectorize.h ------------------------------------------*- 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 // This is the LLVM loop vectorizer. This pass modifies 'vectorizable' loops
10 // and generates target-independent LLVM-IR.
11 // The vectorizer uses the TargetTransformInfo analysis to estimate the costs
12 // of instructions in order to estimate the profitability of vectorization.
13 //
14 // The loop vectorizer combines consecutive loop iterations into a single
15 // 'wide' iteration. After this transformation the index is incremented
16 // by the SIMD vector width, and not by one.
17 //
18 // This pass has three parts:
19 // 1. The main loop pass that drives the different parts.
20 // 2. LoopVectorizationLegality - A unit that checks for the legality
21 // of the vectorization.
22 // 3. InnerLoopVectorizer - A unit that performs the actual
23 // widening of instructions.
24 // 4. LoopVectorizationCostModel - A unit that checks for the profitability
25 // of vectorization. It decides on the optimal vector width, which
26 // can be one, if vectorization is not profitable.
27 //
28 // There is a development effort going on to migrate loop vectorizer to the
29 // VPlan infrastructure and to introduce outer loop vectorization support (see
30 // docs/Proposal/VectorizationPlan.rst and
31 // http://lists.llvm.org/pipermail/llvm-dev/2017-December/119523.html). For this
32 // purpose, we temporarily introduced the VPlan-native vectorization path: an
33 // alternative vectorization path that is natively implemented on top of the
34 // VPlan infrastructure. See EnableVPlanNativePath for enabling.
35 //
36 //===----------------------------------------------------------------------===//
37 //
38 // The reduction-variable vectorization is based on the paper:
39 // D. Nuzman and R. Henderson. Multi-platform Auto-vectorization.
40 //
41 // Variable uniformity checks are inspired by:
42 // Karrenberg, R. and Hack, S. Whole Function Vectorization.
43 //
44 // The interleaved access vectorization is based on the paper:
45 // Dorit Nuzman, Ira Rosen and Ayal Zaks. Auto-Vectorization of Interleaved
46 // Data for SIMD
47 //
48 // Other ideas/concepts are from:
49 // A. Zaks and D. Nuzman. Autovectorization in GCC-two years later.
50 //
51 // S. Maleki, Y. Gao, M. Garzaran, T. Wong and D. Padua. An Evaluation of
52 // Vectorizing Compilers.
53 //
54 //===----------------------------------------------------------------------===//
55 
56 #ifndef LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
57 #define LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
58 
59 #include "llvm/IR/PassManager.h"
61 #include <functional>
62 
63 namespace llvm {
64 
65 class AAResults;
66 class AssumptionCache;
67 class BlockFrequencyInfo;
68 class DemandedBits;
69 class DominatorTree;
70 class Function;
71 class Loop;
72 class LoopAccessInfoManager;
73 class LoopInfo;
74 class OptimizationRemarkEmitter;
75 class ProfileSummaryInfo;
76 class ScalarEvolution;
77 class TargetLibraryInfo;
78 class TargetTransformInfo;
79 
80 extern cl::opt<bool> EnableLoopInterleaving;
81 extern cl::opt<bool> EnableLoopVectorization;
82 
83 /// A marker to determine if extra passes after loop vectorization should be
84 /// run.
86  : public AnalysisInfoMixin<ShouldRunExtraVectorPasses> {
87  static AnalysisKey Key;
88  struct Result {
91  // Check whether the analysis has been explicitly invalidated. Otherwise,
92  // it remains preserved.
93  auto PAC = PA.getChecker<ShouldRunExtraVectorPasses>();
94  return !PAC.preservedWhenStateless();
95  }
96  };
97 
99 };
100 
101 /// A pass manager to run a set of extra function simplification passes after
102 /// vectorization, if requested. LoopVectorize caches the
103 /// ShouldRunExtraVectorPasses analysis to request extra simplifications, if
104 /// they could be beneficial.
107  auto PA = PreservedAnalyses::all();
109  PA.intersect(FunctionPassManager::run(F, AM));
110  PA.abandon<ShouldRunExtraVectorPasses>();
111  return PA;
112  }
113 };
114 
116  /// If false, consider all loops for interleaving.
117  /// If true, only loops that explicitly request interleaving are considered.
119 
120  /// If false, consider all loops for vectorization.
121  /// If true, only loops that explicitly request vectorization are considered.
123 
124  /// The current defaults when creating the pass with no arguments are:
125  /// EnableLoopInterleaving = true and EnableLoopVectorization = true. This
126  /// means that interleaving default is consistent with the cl::opt flag, while
127  /// vectorization is not.
128  /// FIXME: The default for EnableLoopVectorization in the cl::opt should be
129  /// set to true, and the corresponding change to account for this be made in
130  /// opt.cpp. The initializations below will become:
131  /// InterleaveOnlyWhenForced(!EnableLoopInterleaving)
132  /// VectorizeOnlyWhenForced(!EnableLoopVectorization).
139 
142  return *this;
143  }
144 
147  return *this;
148  }
149 };
150 
151 /// Storage for information about made changes.
155 
158 };
159 
160 /// The LoopVectorize Pass.
161 struct LoopVectorizePass : public PassInfoMixin<LoopVectorizePass> {
162 private:
163  /// If false, consider all loops for interleaving.
164  /// If true, only loops that explicitly request interleaving are considered.
165  bool InterleaveOnlyWhenForced;
166 
167  /// If false, consider all loops for vectorization.
168  /// If true, only loops that explicitly request vectorization are considered.
169  bool VectorizeOnlyWhenForced;
170 
171 public:
173 
186 
188  void printPipeline(raw_ostream &OS,
189  function_ref<StringRef(StringRef)> MapClassName2PassName);
190 
191  // Shim for old PM.
198 
199  bool processLoop(Loop *L);
200 };
201 
202 /// Reports a vectorization failure: print \p DebugMsg for debugging
203 /// purposes along with the corresponding optimization remark \p RemarkName.
204 /// If \p I is passed, it is an instruction that prevents vectorization.
205 /// Otherwise, the loop \p TheLoop is used for the location of the remark.
206 void reportVectorizationFailure(const StringRef DebugMsg,
207  const StringRef OREMsg, const StringRef ORETag,
208  OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr);
209 
210 /// Reports an informative message: print \p Msg for debugging purposes as well
211 /// as an optimization remark. Uses either \p I as location of the remark, or
212 /// otherwise \p TheLoop.
213 void reportVectorizationInfo(const StringRef OREMsg, const StringRef ORETag,
214  OptimizationRemarkEmitter *ORE, Loop *TheLoop,
215  Instruction *I = nullptr);
216 
217 } // end namespace llvm
218 
219 #endif // LLVM_TRANSFORMS_VECTORIZE_LOOPVECTORIZE_H
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::LoopVectorizeOptions::LoopVectorizeOptions
LoopVectorizeOptions()
The current defaults when creating the pass with no arguments are: EnableLoopInterleaving = true and ...
Definition: LoopVectorize.h:133
llvm::LoopVectorizeResult::MadeCFGChange
bool MadeCFGChange
Definition: LoopVectorize.h:154
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LoopVectorizePass::printPipeline
void printPipeline(raw_ostream &OS, function_ref< StringRef(StringRef)> MapClassName2PassName)
Definition: LoopVectorize.cpp:10665
llvm::LoopAccessInfoManager
Definition: LoopAccessAnalysis.h:768
llvm::LoopVectorizePass::ORE
OptimizationRemarkEmitter * ORE
Definition: LoopVectorize.h:184
llvm::ShouldRunExtraVectorPasses::Result
Definition: LoopVectorize.h:88
llvm::PassInfoMixin
A CRTP mix-in to automatically provide informational APIs needed for passes.
Definition: PassManager.h:371
llvm::Function
Definition: Function.h:60
llvm::Loop
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:547
llvm::LoopVectorizeOptions::VectorizeOnlyWhenForced
bool VectorizeOnlyWhenForced
If false, consider all loops for vectorization.
Definition: LoopVectorize.h:122
llvm::TargetTransformInfo
This pass provides access to the codegen interfaces that are needed for IR-level transformations.
Definition: TargetTransformInfo.h:173
llvm::ScalarEvolution
The main scalar evolution driver.
Definition: ScalarEvolution.h:449
llvm::DominatorTree
Concrete subclass of DominatorTreeBase that is used to compute a normal dominator tree.
Definition: Dominators.h:166
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
llvm::reportVectorizationFailure
void reportVectorizationFailure(const StringRef DebugMsg, const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I=nullptr)
Reports a vectorization failure: print DebugMsg for debugging purposes along with the corresponding o...
Definition: LoopVectorize.cpp:976
llvm::LoopVectorizeOptions::setInterleaveOnlyWhenForced
LoopVectorizeOptions & setInterleaveOnlyWhenForced(bool Value)
Definition: LoopVectorize.h:140
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LoopVectorizePass::AC
AssumptionCache * AC
Definition: LoopVectorize.h:182
llvm::LoopVectorizeOptions::LoopVectorizeOptions
LoopVectorizeOptions(bool InterleaveOnlyWhenForced, bool VectorizeOnlyWhenForced)
Definition: LoopVectorize.h:135
CommandLine.h
llvm::LoopVectorizePass::runImpl
LoopVectorizeResult runImpl(Function &F, ScalarEvolution &SE_, LoopInfo &LI_, TargetTransformInfo &TTI_, DominatorTree &DT_, BlockFrequencyInfo &BFI_, TargetLibraryInfo *TLI_, DemandedBits &DB_, AAResults &AA_, AssumptionCache &AC_, LoopAccessInfoManager &LAIs_, OptimizationRemarkEmitter &ORE_, ProfileSummaryInfo *PSI_)
Definition: LoopVectorize.cpp:10550
llvm::BlockFrequencyInfo
BlockFrequencyInfo pass uses BlockFrequencyInfoImpl implementation to estimate IR basic block frequen...
Definition: BlockFrequencyInfo.h:37
llvm::LoopVectorizePass::LI
LoopInfo * LI
Definition: LoopVectorize.h:175
llvm::AAResults
Definition: AliasAnalysis.h:294
llvm::reportVectorizationInfo
void reportVectorizationInfo(const StringRef OREMsg, const StringRef ORETag, OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I=nullptr)
Reports an informative message: print Msg for debugging purposes as well as an optimization remark.
Definition: LoopVectorize.cpp:987
llvm::LoopVectorizePass::LAIs
LoopAccessInfoManager * LAIs
Definition: LoopVectorize.h:183
false
Definition: StackSlotColoring.cpp:141
llvm::LoopVectorizeResult::MadeAnyChange
bool MadeAnyChange
Definition: LoopVectorize.h:153
llvm::Instruction
Definition: Instruction.h:42
llvm::raw_ostream
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:53
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
llvm::LoopVectorizePass::TTI
TargetTransformInfo * TTI
Definition: LoopVectorize.h:176
llvm::EnableLoopVectorization
cl::opt< bool > EnableLoopVectorization
llvm::ProfileSummaryInfo
Analysis providing profile information.
Definition: ProfileSummaryInfo.h:40
llvm::function_ref
An efficient, type-erasing, non-owning reference to a callable.
Definition: STLFunctionalExtras.h:36
llvm::ShouldRunExtraVectorPasses
A marker to determine if extra passes after loop vectorization should be run.
Definition: LoopVectorize.h:85
llvm::LoopVectorizePass::AA
AAResults * AA
Definition: LoopVectorize.h:181
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
llvm::DemandedBits
Definition: DemandedBits.h:41
llvm::ExtraVectorPassManager
A pass manager to run a set of extra function simplification passes after vectorization,...
Definition: LoopVectorize.h:105
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::AnalysisInfoMixin
A CRTP mix-in that provides informational APIs needed for analysis passes.
Definition: PassManager.h:394
llvm::ExtraVectorPassManager::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopVectorize.h:106
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::OptimizationRemarkEmitter
The optimization diagnostic interface.
Definition: OptimizationRemarkEmitter.h:33
llvm::StringRef
StringRef - Represent a constant reference to a string, i.e.
Definition: StringRef.h:50
llvm::AssumptionCache
A cache of @llvm.assume calls within a function.
Definition: AssumptionCache.h:42
llvm::ShouldRunExtraVectorPasses::Key
static AnalysisKey Key
Definition: LoopVectorize.h:87
llvm::LoopVectorizeOptions::setVectorizeOnlyWhenForced
LoopVectorizeOptions & setVectorizeOnlyWhenForced(bool Value)
Definition: LoopVectorize.h:145
llvm::LoopVectorizeOptions
Definition: LoopVectorize.h:115
llvm::PassManager< Function >
llvm::ShouldRunExtraVectorPasses::run
Result run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopVectorize.h:98
llvm::LoopVectorizePass::processLoop
bool processLoop(Loop *L)
Definition: LoopVectorize.cpp:10148
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
llvm::LoopVectorizePass::TLI
TargetLibraryInfo * TLI
Definition: LoopVectorize.h:179
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
PassManager.h
llvm::TargetLibraryInfo
Provides information about what library functions are available for the current target.
Definition: TargetLibraryInfo.h:226
llvm::LoopVectorizePass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
Definition: LoopVectorize.cpp:10616
llvm::LoopVectorizeResult
Storage for information about made changes.
Definition: LoopVectorize.h:152
llvm::ShouldRunExtraVectorPasses::Result::invalidate
bool invalidate(Function &F, const PreservedAnalyses &PA, FunctionAnalysisManager::Invalidator &)
Definition: LoopVectorize.h:89
llvm::LoopVectorizePass::DB
DemandedBits * DB
Definition: LoopVectorize.h:180
llvm::LoopVectorizePass::BFI
BlockFrequencyInfo * BFI
Definition: LoopVectorize.h:178
llvm::PassManager< Function >::run
PreservedAnalyses run(Function &IR, AnalysisManager< Function > &AM, ExtraArgTs... ExtraArgs)
Run all of the passes in this manager over the given unit of IR.
Definition: PassManager.h:498
llvm::LoopVectorizeResult::LoopVectorizeResult
LoopVectorizeResult(bool MadeAnyChange, bool MadeCFGChange)
Definition: LoopVectorize.h:156
llvm::LoopVectorizePass::PSI
ProfileSummaryInfo * PSI
Definition: LoopVectorize.h:185
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::LoopVectorizeOptions::InterleaveOnlyWhenForced
bool InterleaveOnlyWhenForced
If false, consider all loops for interleaving.
Definition: LoopVectorize.h:118
llvm::LoopVectorizePass::LoopVectorizePass
LoopVectorizePass(LoopVectorizeOptions Opts={})
Definition: LoopVectorize.cpp:10142
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::LoopVectorizePass
The LoopVectorize Pass.
Definition: LoopVectorize.h:161
llvm::codeview::PublicSymFlags::Function
@ Function
llvm::LoopVectorizePass::DT
DominatorTree * DT
Definition: LoopVectorize.h:177
llvm::LoopVectorizePass::SE
ScalarEvolution * SE
Definition: LoopVectorize.h:174
llvm::EnableLoopInterleaving
cl::opt< bool > EnableLoopInterleaving