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" |
19 | #include "llvm/Transforms/Utils/LoopUtils.h" |
20 | #include "llvm/Transforms/Utils/ValueMapper.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 *> |
32 | RuntimePointerCheck; |
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. |
41 | class LoopVersioning { |
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, |
48 | ArrayRef<RuntimePointerCheck> Checks, Loop *L, LoopInfo *LI, |
49 | DominatorTree *DT, ScalarEvolution *SE); |
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 |
64 | void versionLoop() { versionLoop(DefsUsedOutside: findDefsUsedOutsideOfLoop(L: VersionedLoop)); } |
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. |
84 | void annotateLoopWithNoAlias(); |
85 | |
86 | /// Set up the aliasing scopes based on the memchecks. This needs to |
87 | /// be called before the first call to annotateInstWithNoAlias. |
88 | void prepareNoAliasMetadata(); |
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. |
108 | void annotateInstWithNoAlias(Instruction *I) { |
109 | annotateInstWithNoAlias(VersionedInst: I, OrigInst: I); |
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: |
152 | PreservedAnalyses run(Function &F, FunctionAnalysisManager &FAM); |
153 | }; |
154 | } |
155 | |
156 | #endif |
157 | |