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