1 //===------ PollyIRBuilder.cpp --------------------------------------------===//
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 // The Polly IRBuilder file contains Polly specific extensions for the IRBuilder
10 // that are used e.g. to emit the llvm.loop.parallel metadata.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "polly/CodeGen/IRBuilder.h"
15 #include "polly/ScopInfo.h"
16 #include "polly/Support/ScopHelper.h"
17 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Metadata.h"
19
20 using namespace llvm;
21 using namespace polly;
22
23 static const int MaxArraysInAliasScops = 10;
24
25 /// Get a self referencing id metadata node.
26 ///
27 /// The MDNode looks like this (if arg0/arg1 are not null):
28 ///
29 /// '!n = distinct !{!n, arg0, arg1}'
30 ///
31 /// @return The self referencing id metadata node.
getID(LLVMContext & Ctx,Metadata * arg0=nullptr,Metadata * arg1=nullptr)32 static MDNode *getID(LLVMContext &Ctx, Metadata *arg0 = nullptr,
33 Metadata *arg1 = nullptr) {
34 MDNode *ID;
35 SmallVector<Metadata *, 3> Args;
36 // Reserve operand 0 for loop id self reference.
37 Args.push_back(nullptr);
38
39 if (arg0)
40 Args.push_back(arg0);
41 if (arg1)
42 Args.push_back(arg1);
43
44 ID = MDNode::getDistinct(Ctx, Args);
45 ID->replaceOperandWith(0, ID);
46 return ID;
47 }
48
ScopAnnotator()49 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {
50 // Push an empty staging BandAttr.
51 LoopAttrEnv.emplace_back();
52 }
53
~ScopAnnotator()54 ScopAnnotator::~ScopAnnotator() {
55 assert(LoopAttrEnv.size() == 1 && "Loop stack imbalance");
56 assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
57 }
58
buildAliasScopes(Scop & S)59 void ScopAnnotator::buildAliasScopes(Scop &S) {
60 SE = S.getSE();
61
62 LLVMContext &Ctx = SE->getContext();
63 AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
64
65 AliasScopeMap.clear();
66 OtherAliasScopeListMap.clear();
67
68 // We are only interested in arrays, but no scalar references. Scalars should
69 // be handled easily by basicaa.
70 SmallVector<ScopArrayInfo *, 10> Arrays;
71 for (ScopArrayInfo *Array : S.arrays())
72 if (Array->isArrayKind())
73 Arrays.push_back(Array);
74
75 // The construction of alias scopes is quadratic in the number of arrays
76 // involved. In case of too many arrays, skip the construction of alias
77 // information to avoid quadratic increases in compile time and code size.
78 if (Arrays.size() > MaxArraysInAliasScops)
79 return;
80
81 std::string AliasScopeStr = "polly.alias.scope.";
82 for (const ScopArrayInfo *Array : Arrays) {
83 assert(Array->getBasePtr() && "Base pointer must be present");
84 AliasScopeMap[Array->getBasePtr()] =
85 getID(Ctx, AliasScopeDomain,
86 MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
87 }
88
89 for (const ScopArrayInfo *Array : Arrays) {
90 MDNode *AliasScopeList = MDNode::get(Ctx, {});
91 for (const auto &AliasScopePair : AliasScopeMap) {
92 if (Array->getBasePtr() == AliasScopePair.first)
93 continue;
94
95 Metadata *Args = {AliasScopePair.second};
96 AliasScopeList =
97 MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
98 }
99
100 OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
101 }
102 }
103
pushLoop(Loop * L,bool IsParallel)104 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
105 ActiveLoops.push_back(L);
106
107 if (IsParallel) {
108 LLVMContext &Ctx = SE->getContext();
109 MDNode *AccessGroup = MDNode::getDistinct(Ctx, {});
110 ParallelLoops.push_back(AccessGroup);
111 }
112
113 // Open an empty BandAttr context for loops nested in this one.
114 LoopAttrEnv.emplace_back();
115 }
116
popLoop(bool IsParallel)117 void ScopAnnotator::popLoop(bool IsParallel) {
118 ActiveLoops.pop_back();
119
120 if (IsParallel) {
121 assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
122 ParallelLoops.pop_back();
123 }
124
125 // Exit the subloop context.
126 assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
127 assert(LoopAttrEnv.size() >= 2 && "Popped too many");
128 LoopAttrEnv.pop_back();
129 }
130
annotateLoopLatch(BranchInst * B,Loop * L,bool IsParallel,bool IsLoopVectorizerDisabled) const131 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
132 bool IsLoopVectorizerDisabled) const {
133 LLVMContext &Ctx = SE->getContext();
134 SmallVector<Metadata *, 3> Args;
135
136 // For the LoopID self-reference.
137 Args.push_back(nullptr);
138
139 // Add the user-defined loop properties to the annotation, if any. Any
140 // additional properties are appended.
141 // FIXME: What to do if these conflict?
142 MDNode *MData = nullptr;
143 if (BandAttr *AttrEnv = getActiveAttrEnv()) {
144 MData = AttrEnv->Metadata;
145 if (MData)
146 llvm::append_range(Args, drop_begin(MData->operands(), 1));
147 }
148
149 if (IsLoopVectorizerDisabled) {
150 MDString *PropName = MDString::get(Ctx, "llvm.loop.vectorize.enable");
151 ConstantInt *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
152 ValueAsMetadata *PropValue = ValueAsMetadata::get(FalseValue);
153 Args.push_back(MDNode::get(Ctx, {PropName, PropValue}));
154 }
155
156 if (IsParallel) {
157 MDString *PropName = MDString::get(Ctx, "llvm.loop.parallel_accesses");
158 MDNode *AccGroup = ParallelLoops.back();
159 Args.push_back(MDNode::get(Ctx, {PropName, AccGroup}));
160 }
161
162 // No metadata to annotate.
163 if (!MData && Args.size() <= 1)
164 return;
165
166 // Reuse the MData node if possible, this will avoid having to create another
167 // one that cannot be merged because LoopIDs are 'distinct'. However, we have
168 // to create a new one if we add properties.
169 if (!MData || Args.size() > MData->getNumOperands()) {
170 MData = MDNode::getDistinct(Ctx, Args);
171 MData->replaceOperandWith(0, MData);
172 }
173 B->setMetadata(LLVMContext::MD_loop, MData);
174 }
175
176 /// Get the pointer operand
177 ///
178 /// @param Inst The instruction to be analyzed.
179 /// @return the pointer operand in case @p Inst is a memory access
180 /// instruction and nullptr otherwise.
getMemAccInstPointerOperand(Instruction * Inst)181 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
182 auto MemInst = MemAccInst::dyn_cast(Inst);
183 if (!MemInst)
184 return nullptr;
185
186 return MemInst.getPointerOperand();
187 }
188
annotateSecondLevel(llvm::Instruction * Inst,llvm::Value * BasePtr)189 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
190 llvm::Value *BasePtr) {
191 Value *Ptr = getMemAccInstPointerOperand(Inst);
192 if (!Ptr)
193 return;
194
195 auto *PtrSCEV = SE->getSCEV(Ptr);
196 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
197
198 auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
199 auto SecondLevelOtherAliasScopeList =
200 SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
201 if (!SecondLevelAliasScope) {
202 auto AliasScope = AliasScopeMap.lookup(BasePtr);
203 if (!AliasScope)
204 return;
205 LLVMContext &Ctx = SE->getContext();
206 SecondLevelAliasScope = getID(
207 Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
208 SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
209 Metadata *Args = {SecondLevelAliasScope};
210 auto SecondLevelBasePtrAliasScopeList =
211 SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
212 SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
213 SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
214 auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
215 SecondLevelOtherAliasScopeList = MDNode::concatenate(
216 OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
217 SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
218 }
219 Inst->setMetadata("alias.scope", SecondLevelAliasScope);
220 Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
221 }
222
223 /// Find the base pointer of an array access.
224 ///
225 /// This should be equivalent to ScalarEvolution::getPointerBase, which we
226 /// cannot use here the IR is still under construction which ScalarEvolution
227 /// assumes to not be modified.
findBasePtr(Value * Val)228 static Value *findBasePtr(Value *Val) {
229 while (true) {
230 if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
231 Val = Gep->getPointerOperand();
232 continue;
233 }
234 if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
235 Val = Cast->getOperand(0);
236 continue;
237 }
238
239 break;
240 }
241
242 return Val;
243 }
244
annotate(Instruction * Inst)245 void ScopAnnotator::annotate(Instruction *Inst) {
246 if (!Inst->mayReadOrWriteMemory())
247 return;
248
249 switch (ParallelLoops.size()) {
250 case 0:
251 // Not parallel to anything: no access group needed.
252 break;
253 case 1:
254 // Single parallel loop: use directly.
255 Inst->setMetadata(LLVMContext::MD_access_group,
256 cast<MDNode>(ParallelLoops.front()));
257 break;
258 default:
259 // Parallel to multiple loops: refer to list of access groups.
260 Inst->setMetadata(LLVMContext::MD_access_group,
261 MDNode::get(SE->getContext(),
262 ArrayRef<Metadata *>(
263 (Metadata *const *)ParallelLoops.data(),
264 ParallelLoops.size())));
265 break;
266 }
267
268 // TODO: Use the ScopArrayInfo once available here.
269 if (!AliasScopeDomain)
270 return;
271
272 // Do not apply annotations on memory operations that take more than one
273 // pointer. It would be ambiguous to which pointer the annotation applies.
274 // FIXME: How can we specify annotations for all pointer arguments?
275 if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
276 return;
277
278 auto *Ptr = getMemAccInstPointerOperand(Inst);
279 if (!Ptr)
280 return;
281
282 Value *BasePtr = findBasePtr(Ptr);
283 if (!BasePtr)
284 return;
285
286 auto AliasScope = AliasScopeMap.lookup(BasePtr);
287
288 if (!AliasScope) {
289 BasePtr = AlternativeAliasBases.lookup(BasePtr);
290 if (!BasePtr)
291 return;
292
293 AliasScope = AliasScopeMap.lookup(BasePtr);
294 if (!AliasScope)
295 return;
296 }
297
298 assert(OtherAliasScopeListMap.count(BasePtr) &&
299 "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
300 auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
301
302 if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
303 annotateSecondLevel(Inst, BasePtr);
304 return;
305 }
306
307 Inst->setMetadata("alias.scope", AliasScope);
308 Inst->setMetadata("noalias", OtherAliasScopeList);
309 }
310
addInterIterationAliasFreeBasePtr(llvm::Value * BasePtr)311 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
312 if (!BasePtr)
313 return;
314
315 InterIterationAliasFreeBasePtrs.insert(BasePtr);
316 }
317