LLVM  16.0.0git
LoopVersioning.h
Go to the documentation of this file.
1 //===- LoopVersioning.h - Utility to version a loop -------------*- 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 file defines a utility class to perform loop versioning. The versioned
10 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
11 // emits checks to prove this.
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #ifndef LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
16 #define LLVM_TRANSFORMS_UTILS_LOOPVERSIONING_H
17 
18 #include "llvm/IR/PassManager.h"
21 
22 namespace llvm {
23 
24 class Loop;
25 class SCEVPredicate;
26 class ScalarEvolution;
27 class LoopAccessInfo;
28 class LoopInfo;
29 struct RuntimeCheckingPtrGroup;
30 typedef std::pair<const RuntimeCheckingPtrGroup *,
31  const RuntimeCheckingPtrGroup *>
33 
34 template <typename T> class ArrayRef;
35 
36 /// This class emits a version of the loop where run-time checks ensure
37 /// that may-alias pointers can't overlap.
38 ///
39 /// It currently only supports single-exit loops and assumes that the loop
40 /// already has a preheader.
42 public:
43  /// Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
44  /// It uses runtime check provided by the user. If \p UseLAIChecks is true,
45  /// we will retain the default checks made by LAI. Otherwise, construct an
46  /// object having no checks and we expect the user to add them.
47  LoopVersioning(const LoopAccessInfo &LAI,
50 
51  /// Performs the CFG manipulation part of versioning the loop including
52  /// the DominatorTree and LoopInfo updates.
53  ///
54  /// The loop that was used to construct the class will be the "versioned" loop
55  /// i.e. the loop that will receive control if all the memchecks pass.
56  ///
57  /// This allows the loop transform pass to operate on the same loop regardless
58  /// of whether versioning was necessary or not:
59  ///
60  /// for each loop L:
61  /// analyze L
62  /// if versioning is necessary version L
63  /// transform L
65 
66  /// Same but if the client has already precomputed the set of values
67  /// used outside the loop, this API will allows passing that.
68  void versionLoop(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
69 
70  /// Returns the versioned loop. Control flows here if pointers in the
71  /// loop don't alias (i.e. all memchecks passed). (This loop is actually the
72  /// same as the original loop that we got constructed with.)
73  Loop *getVersionedLoop() { return VersionedLoop; }
74 
75  /// Returns the fall-back loop. Control flows here if pointers in the
76  /// loop may alias (i.e. one of the memchecks failed).
77  Loop *getNonVersionedLoop() { return NonVersionedLoop; }
78 
79  /// Annotate memory instructions in the versioned loop with no-alias
80  /// metadata based on the memchecks issued.
81  ///
82  /// This is just wrapper that calls prepareNoAliasMetadata and
83  /// annotateInstWithNoAlias on the instructions of the versioned loop.
85 
86  /// Set up the aliasing scopes based on the memchecks. This needs to
87  /// be called before the first call to annotateInstWithNoAlias.
89 
90  /// Add the noalias annotations to \p VersionedInst.
91  ///
92  /// \p OrigInst is the instruction corresponding to \p VersionedInst in the
93  /// original loop. Initialize the aliasing scopes with
94  /// prepareNoAliasMetadata once before this can be called.
95  void annotateInstWithNoAlias(Instruction *VersionedInst,
96  const Instruction *OrigInst);
97 
98 private:
99  /// Adds the necessary PHI nodes for the versioned loops based on the
100  /// loop-defined values used outside of the loop.
101  ///
102  /// This needs to be called after versionLoop if there are defs in the loop
103  /// that are used outside the loop.
104  void addPHINodes(const SmallVectorImpl<Instruction *> &DefsUsedOutside);
105 
106  /// Add the noalias annotations to \p I. Initialize the aliasing
107  /// scopes with prepareNoAliasMetadata once before this can be called.
110  }
111 
112  /// The original loop. This becomes the "versioned" one. I.e.,
113  /// control flows here if pointers in the loop don't alias.
114  Loop *VersionedLoop;
115  /// The fall-back loop. I.e. control flows here if pointers in the
116  /// loop may alias (memchecks failed).
117  Loop *NonVersionedLoop = nullptr;
118 
119  /// This maps the instructions from VersionedLoop to their counterpart
120  /// in NonVersionedLoop.
121  ValueToValueMapTy VMap;
122 
123  /// The set of alias checks that we are versioning for.
124  SmallVector<RuntimePointerCheck, 4> AliasChecks;
125 
126  /// The set of SCEV checks that we are versioning for.
127  const SCEVPredicate &Preds;
128 
129  /// Maps a pointer to the pointer checking group that the pointer
130  /// belongs to.
131  DenseMap<const Value *, const RuntimeCheckingPtrGroup *> PtrToGroup;
132 
133  /// The alias scope corresponding to a pointer checking group.
134  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *> GroupToScope;
135 
136  /// The list of alias scopes that a pointer checking group can't alias.
137  DenseMap<const RuntimeCheckingPtrGroup *, MDNode *>
138  GroupToNonAliasingScopeList;
139 
140  /// Analyses used.
141  const LoopAccessInfo &LAI;
142  LoopInfo *LI;
143  DominatorTree *DT;
144  ScalarEvolution *SE;
145 };
146 
147 /// Expose LoopVersioning as a pass. Currently this is only used for
148 /// unit-testing. It adds all memchecks necessary to remove all may-aliasing
149 /// array accesses from the loop.
150 class LoopVersioningPass : public PassInfoMixin<LoopVersioningPass> {
151 public:
153 };
154 }
155 
156 #endif
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::RuntimePointerCheck
std::pair< const RuntimeCheckingPtrGroup *, const RuntimeCheckingPtrGroup * > RuntimePointerCheck
A memcheck which made up of a pair of grouped pointers.
Definition: LoopAccessAnalysis.h:369
ValueMapper.h
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::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::findDefsUsedOutsideOfLoop
SmallVector< Instruction *, 8 > findDefsUsedOutsideOfLoop(Loop *L)
Returns the instructions that use values defined in the loop.
Definition: LoopUtils.cpp:124
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::LoopVersioning::annotateInstWithNoAlias
void annotateInstWithNoAlias(Instruction *VersionedInst, const Instruction *OrigInst)
Add the noalias annotations to VersionedInst.
Definition: LoopVersioning.cpp:228
llvm::LoopVersioningPass
Expose LoopVersioning as a pass.
Definition: LoopVersioning.h:150
llvm::LoopVersioning::prepareNoAliasMetadata
void prepareNoAliasMetadata()
Set up the aliasing scopes based on the memchecks.
Definition: LoopVersioning.cpp:174
llvm::LoopVersioning::getNonVersionedLoop
Loop * getNonVersionedLoop()
Returns the fall-back loop.
Definition: LoopVersioning.h:77
llvm::Instruction
Definition: Instruction.h:42
LoopUtils.h
llvm::LoopVersioning
This class emits a version of the loop where run-time checks ensure that may-alias pointers can't ove...
Definition: LoopVersioning.h:41
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::LoopAccessInfo
Drive the analysis of memory accesses in the loop.
Definition: LoopAccessAnalysis.h:562
llvm::ValueToValueMapTy
ValueMap< const Value *, WeakTrackingVH > ValueToValueMapTy
Definition: MemorySSAUpdater.h:50
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::LoopInfo
Definition: LoopInfo.h:1108
llvm::LoopVersioningPass::run
PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM)
Definition: LoopVersioning.cpp:345
llvm::LoopVersioning::LoopVersioning
LoopVersioning(const LoopAccessInfo &LAI, ArrayRef< RuntimePointerCheck > Checks, Loop *L, LoopInfo *LI, DominatorTree *DT, ScalarEvolution *SE)
Expects LoopAccessInfo, Loop, LoopInfo, DominatorTree as input.
Definition: LoopVersioning.cpp:40
llvm::LoopVersioning::versionLoop
void versionLoop()
Performs the CFG manipulation part of versioning the loop including the DominatorTree and LoopInfo up...
Definition: LoopVersioning.h:64
PassManager.h
llvm::SmallVectorImpl< Instruction * >
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::LoopVersioning::annotateLoopWithNoAlias
void annotateLoopWithNoAlias()
Annotate memory instructions in the versioned loop with no-alias metadata based on the memchecks issu...
Definition: LoopVersioning.cpp:215
llvm::LoopVersioning::getVersionedLoop
Loop * getVersionedLoop()
Returns the versioned loop.
Definition: LoopVersioning.h:73