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
131static void addVectorizeMetadata(LLVMContext &Ctx,
132 SmallVector<Metadata *, 3> *Args,
133 bool EnableLoopVectorizer) {
134 MDString *PropName = MDString::get(Context&: Ctx, Str: "llvm.loop.vectorize.enable");
135 ConstantInt *Value =
136 ConstantInt::get(Ty: Type::getInt1Ty(C&: Ctx), V: EnableLoopVectorizer);
137 ValueAsMetadata *PropValue = ValueAsMetadata::get(V: Value);
138 Args->push_back(Elt: MDNode::get(Context&: Ctx, MDs: {PropName, PropValue}));
139}
140
141void addParallelMetadata(LLVMContext &Ctx, SmallVector<Metadata *, 3> *Args,
142 llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops) {
143 MDString *PropName = MDString::get(Context&: Ctx, Str: "llvm.loop.parallel_accesses");
144 MDNode *AccGroup = ParallelLoops.back();
145 Args->push_back(Elt: MDNode::get(Context&: Ctx, MDs: {PropName, AccGroup}));
146}
147
148void ScopAnnotator::annotateLoopLatch(
149 BranchInst *B, bool IsParallel,
150 std::optional<bool> EnableVectorizeMetadata) const {
151 LLVMContext &Ctx = SE->getContext();
152 SmallVector<Metadata *, 3> Args;
153
154 // For the LoopID self-reference.
155 Args.push_back(Elt: nullptr);
156
157 // Add the user-defined loop properties to the annotation, if any. Any
158 // additional properties are appended.
159 // FIXME: What to do if these conflict?
160 MDNode *MData = nullptr;
161 if (BandAttr *AttrEnv = getActiveAttrEnv()) {
162 MData = AttrEnv->Metadata;
163 if (MData)
164 llvm::append_range(C&: Args, R: drop_begin(RangeOrContainer: MData->operands(), N: 1));
165 }
166 if (IsParallel)
167 addParallelMetadata(Ctx, Args: &Args, ParallelLoops);
168 if (EnableVectorizeMetadata.has_value())
169 addVectorizeMetadata(Ctx, Args: &Args, EnableLoopVectorizer: *EnableVectorizeMetadata);
170
171 // No metadata to annotate.
172 if (!MData && Args.size() <= 1)
173 return;
174
175 // Reuse the MData node if possible, this will avoid having to create another
176 // one that cannot be merged because LoopIDs are 'distinct'. However, we have
177 // to create a new one if we add properties.
178 if (!MData || Args.size() > MData->getNumOperands()) {
179 MData = MDNode::getDistinct(Context&: Ctx, MDs: Args);
180 MData->replaceOperandWith(I: 0, New: MData);
181 }
182 B->setMetadata(KindID: LLVMContext::MD_loop, Node: MData);
183}
184
185/// Get the pointer operand
186///
187/// @param Inst The instruction to be analyzed.
188/// @return the pointer operand in case @p Inst is a memory access
189/// instruction and nullptr otherwise.
190static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
191 auto MemInst = MemAccInst::dyn_cast(V: Inst);
192 if (!MemInst)
193 return nullptr;
194
195 return MemInst.getPointerOperand();
196}
197
198/// Find the base pointer of an array access.
199///
200/// This should be equivalent to ScalarEvolution::getPointerBase, which we
201/// cannot use here the IR is still under construction which ScalarEvolution
202/// assumes to not be modified.
203static Value *findBasePtr(Value *Val) {
204 while (true) {
205 if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
206 Val = Gep->getPointerOperand();
207 continue;
208 }
209 if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
210 Val = Cast->getOperand(i_nocapture: 0);
211 continue;
212 }
213
214 break;
215 }
216
217 return Val;
218}
219
220void ScopAnnotator::annotate(Instruction *Inst) {
221 if (!Inst->mayReadOrWriteMemory())
222 return;
223
224 switch (ParallelLoops.size()) {
225 case 0:
226 // Not parallel to anything: no access group needed.
227 break;
228 case 1:
229 // Single parallel loop: use directly.
230 Inst->setMetadata(KindID: LLVMContext::MD_access_group,
231 Node: cast<MDNode>(Val: ParallelLoops.front()));
232 break;
233 default:
234 // Parallel to multiple loops: refer to list of access groups.
235 Inst->setMetadata(KindID: LLVMContext::MD_access_group,
236 Node: MDNode::get(Context&: SE->getContext(),
237 MDs: ArrayRef<Metadata *>(
238 (Metadata *const *)ParallelLoops.data(),
239 ParallelLoops.size())));
240 break;
241 }
242
243 // TODO: Use the ScopArrayInfo once available here.
244 if (!AliasScopeDomain)
245 return;
246
247 // Do not apply annotations on memory operations that take more than one
248 // pointer. It would be ambiguous to which pointer the annotation applies.
249 // FIXME: How can we specify annotations for all pointer arguments?
250 if (isa<CallInst>(Val: Inst) && !isa<MemSetInst>(Val: Inst))
251 return;
252
253 auto *Ptr = getMemAccInstPointerOperand(Inst);
254 if (!Ptr)
255 return;
256
257 Value *BasePtr = findBasePtr(Val: Ptr);
258 if (!BasePtr)
259 return;
260
261 auto AliasScope = AliasScopeMap.lookup(Key: BasePtr);
262
263 if (!AliasScope) {
264 BasePtr = AlternativeAliasBases.lookup(Val: BasePtr);
265 if (!BasePtr)
266 return;
267
268 AliasScope = AliasScopeMap.lookup(Key: BasePtr);
269 if (!AliasScope)
270 return;
271 }
272
273 assert(OtherAliasScopeListMap.count(BasePtr) &&
274 "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
275 auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
276
277 Inst->setMetadata(Kind: "alias.scope", Node: MDNode::get(Context&: SE->getContext(), MDs: AliasScope));
278 Inst->setMetadata(Kind: "noalias", Node: OtherAliasScopeList);
279}
280

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