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
20using namespace llvm;
21using namespace polly;
22
23static 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.
32static 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(Elt: nullptr);
38
39 if (arg0)
40 Args.push_back(Elt: arg0);
41 if (arg1)
42 Args.push_back(Elt: arg1);
43
44 ID = MDNode::getDistinct(Context&: Ctx, MDs: Args);
45 ID->replaceOperandWith(I: 0, New: ID);
46 return ID;
47}
48
49ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {
50 // Push an empty staging BandAttr.
51 LoopAttrEnv.emplace_back();
52}
53
54ScopAnnotator::~ScopAnnotator() {
55 assert(LoopAttrEnv.size() == 1 && "Loop stack imbalance");
56 assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
57}
58
59void ScopAnnotator::buildAliasScopes(Scop &S) {
60 SE = S.getSE();
61
62 LLVMContext &Ctx = SE->getContext();
63 AliasScopeDomain = getID(Ctx, arg0: MDString::get(Context&: Ctx, Str: "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(Elt: 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, arg0: AliasScopeDomain,
86 arg1: MDString::get(Context&: Ctx, Str: (AliasScopeStr + Array->getName()).c_str()));
87 }
88
89 for (const ScopArrayInfo *Array : Arrays) {
90 MDNode *AliasScopeList = MDNode::get(Context&: Ctx, MDs: {});
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(A: AliasScopeList, B: MDNode::get(Context&: Ctx, MDs: Args));
98 }
99
100 OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
101 }
102}
103
104void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
105 ActiveLoops.push_back(Elt: L);
106
107 if (IsParallel) {
108 LLVMContext &Ctx = SE->getContext();
109 MDNode *AccessGroup = MDNode::getDistinct(Context&: Ctx, MDs: {});
110 ParallelLoops.push_back(Elt: AccessGroup);
111 }
112
113 // Open an empty BandAttr context for loops nested in this one.
114 LoopAttrEnv.emplace_back();
115}
116
117void 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
131void 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(Elt: 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(C&: Args, R: drop_begin(RangeOrContainer: MData->operands(), N: 1));
147 }
148
149 if (IsLoopVectorizerDisabled) {
150 MDString *PropName = MDString::get(Context&: Ctx, Str: "llvm.loop.vectorize.enable");
151 ConstantInt *FalseValue = ConstantInt::get(Ty: Type::getInt1Ty(C&: Ctx), V: 0);
152 ValueAsMetadata *PropValue = ValueAsMetadata::get(V: FalseValue);
153 Args.push_back(Elt: MDNode::get(Context&: Ctx, MDs: {PropName, PropValue}));
154 }
155
156 if (IsParallel) {
157 MDString *PropName = MDString::get(Context&: Ctx, Str: "llvm.loop.parallel_accesses");
158 MDNode *AccGroup = ParallelLoops.back();
159 Args.push_back(Elt: MDNode::get(Context&: Ctx, MDs: {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(Context&: Ctx, MDs: Args);
171 MData->replaceOperandWith(I: 0, New: MData);
172 }
173 B->setMetadata(KindID: LLVMContext::MD_loop, Node: 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.
181static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
182 auto MemInst = MemAccInst::dyn_cast(V: Inst);
183 if (!MemInst)
184 return nullptr;
185
186 return MemInst.getPointerOperand();
187}
188
189/// Find the base pointer of an array access.
190///
191/// This should be equivalent to ScalarEvolution::getPointerBase, which we
192/// cannot use here the IR is still under construction which ScalarEvolution
193/// assumes to not be modified.
194static Value *findBasePtr(Value *Val) {
195 while (true) {
196 if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
197 Val = Gep->getPointerOperand();
198 continue;
199 }
200 if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
201 Val = Cast->getOperand(i_nocapture: 0);
202 continue;
203 }
204
205 break;
206 }
207
208 return Val;
209}
210
211void ScopAnnotator::annotate(Instruction *Inst) {
212 if (!Inst->mayReadOrWriteMemory())
213 return;
214
215 switch (ParallelLoops.size()) {
216 case 0:
217 // Not parallel to anything: no access group needed.
218 break;
219 case 1:
220 // Single parallel loop: use directly.
221 Inst->setMetadata(KindID: LLVMContext::MD_access_group,
222 Node: cast<MDNode>(Val: ParallelLoops.front()));
223 break;
224 default:
225 // Parallel to multiple loops: refer to list of access groups.
226 Inst->setMetadata(KindID: LLVMContext::MD_access_group,
227 Node: MDNode::get(Context&: SE->getContext(),
228 MDs: ArrayRef<Metadata *>(
229 (Metadata *const *)ParallelLoops.data(),
230 ParallelLoops.size())));
231 break;
232 }
233
234 // TODO: Use the ScopArrayInfo once available here.
235 if (!AliasScopeDomain)
236 return;
237
238 // Do not apply annotations on memory operations that take more than one
239 // pointer. It would be ambiguous to which pointer the annotation applies.
240 // FIXME: How can we specify annotations for all pointer arguments?
241 if (isa<CallInst>(Val: Inst) && !isa<MemSetInst>(Val: Inst))
242 return;
243
244 auto *Ptr = getMemAccInstPointerOperand(Inst);
245 if (!Ptr)
246 return;
247
248 Value *BasePtr = findBasePtr(Val: Ptr);
249 if (!BasePtr)
250 return;
251
252 auto AliasScope = AliasScopeMap.lookup(Key: BasePtr);
253
254 if (!AliasScope) {
255 BasePtr = AlternativeAliasBases.lookup(Val: BasePtr);
256 if (!BasePtr)
257 return;
258
259 AliasScope = AliasScopeMap.lookup(Key: BasePtr);
260 if (!AliasScope)
261 return;
262 }
263
264 assert(OtherAliasScopeListMap.count(BasePtr) &&
265 "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
266 auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
267
268 Inst->setMetadata(Kind: "alias.scope", Node: MDNode::get(Context&: SE->getContext(), MDs: AliasScope));
269 Inst->setMetadata(Kind: "noalias", Node: OtherAliasScopeList);
270}
271

source code of polly/lib/CodeGen/IRBuilder.cpp