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
buildAliasScopes(Scop & S)51 void ScopAnnotator::buildAliasScopes(Scop &S) {
52 SE = S.getSE();
53
54 LLVMContext &Ctx = SE->getContext();
55 AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
56
57 AliasScopeMap.clear();
58 OtherAliasScopeListMap.clear();
59
60 // We are only interested in arrays, but no scalar references. Scalars should
61 // be handled easily by basicaa.
62 SmallVector<ScopArrayInfo *, 10> Arrays;
63 for (ScopArrayInfo *Array : S.arrays())
64 if (Array->isArrayKind())
65 Arrays.push_back(Array);
66
67 // The construction of alias scopes is quadratic in the number of arrays
68 // involved. In case of too many arrays, skip the construction of alias
69 // information to avoid quadratic increases in compile time and code size.
70 if (Arrays.size() > MaxArraysInAliasScops)
71 return;
72
73 std::string AliasScopeStr = "polly.alias.scope.";
74 for (const ScopArrayInfo *Array : Arrays) {
75 assert(Array->getBasePtr() && "Base pointer must be present");
76 AliasScopeMap[Array->getBasePtr()] =
77 getID(Ctx, AliasScopeDomain,
78 MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
79 }
80
81 for (const ScopArrayInfo *Array : Arrays) {
82 MDNode *AliasScopeList = MDNode::get(Ctx, {});
83 for (const auto &AliasScopePair : AliasScopeMap) {
84 if (Array->getBasePtr() == AliasScopePair.first)
85 continue;
86
87 Metadata *Args = {AliasScopePair.second};
88 AliasScopeList =
89 MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
90 }
91
92 OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
93 }
94 }
95
pushLoop(Loop * L,bool IsParallel)96 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
97
98 ActiveLoops.push_back(L);
99 if (!IsParallel)
100 return;
101
102 BasicBlock *Header = L->getHeader();
103 MDNode *Id = getID(Header->getContext());
104 assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
105 assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
106 MDNode *Ids = ParallelLoops.empty()
107 ? Id
108 : MDNode::concatenate(ParallelLoops.back(), Id);
109 ParallelLoops.push_back(Ids);
110 }
111
popLoop(bool IsParallel)112 void ScopAnnotator::popLoop(bool IsParallel) {
113 ActiveLoops.pop_back();
114 if (!IsParallel)
115 return;
116
117 assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
118 ParallelLoops.pop_back();
119 }
120
annotateLoopLatch(BranchInst * B,Loop * L,bool IsParallel,bool IsLoopVectorizerDisabled) const121 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
122 bool IsLoopVectorizerDisabled) const {
123 MDNode *MData = nullptr;
124
125 if (IsLoopVectorizerDisabled) {
126 SmallVector<Metadata *, 3> Args;
127 LLVMContext &Ctx = SE->getContext();
128 Args.push_back(MDString::get(Ctx, "llvm.loop.vectorize.enable"));
129 auto *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
130 Args.push_back(ValueAsMetadata::get(FalseValue));
131 MData = MDNode::concatenate(MData, getID(Ctx, MDNode::get(Ctx, Args)));
132 }
133
134 if (IsParallel) {
135 assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
136 MDNode *Ids = ParallelLoops.back();
137 MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
138 MData = MDNode::concatenate(MData, Id);
139 }
140
141 B->setMetadata("llvm.loop", MData);
142 }
143
144 /// Get the pointer operand
145 ///
146 /// @param Inst The instruction to be analyzed.
147 /// @return the pointer operand in case @p Inst is a memory access
148 /// instruction and nullptr otherwise.
getMemAccInstPointerOperand(Instruction * Inst)149 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
150 auto MemInst = MemAccInst::dyn_cast(Inst);
151 if (!MemInst)
152 return nullptr;
153
154 return MemInst.getPointerOperand();
155 }
156
annotateSecondLevel(llvm::Instruction * Inst,llvm::Value * BasePtr)157 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
158 llvm::Value *BasePtr) {
159 Value *Ptr = getMemAccInstPointerOperand(Inst);
160 if (!Ptr)
161 return;
162
163 auto *PtrSCEV = SE->getSCEV(Ptr);
164 auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
165
166 auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
167 auto SecondLevelOtherAliasScopeList =
168 SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
169 if (!SecondLevelAliasScope) {
170 auto AliasScope = AliasScopeMap.lookup(BasePtr);
171 if (!AliasScope)
172 return;
173 LLVMContext &Ctx = SE->getContext();
174 SecondLevelAliasScope = getID(
175 Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
176 SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
177 Metadata *Args = {SecondLevelAliasScope};
178 auto SecondLevelBasePtrAliasScopeList =
179 SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
180 SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
181 SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
182 auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
183 SecondLevelOtherAliasScopeList = MDNode::concatenate(
184 OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
185 SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
186 }
187 Inst->setMetadata("alias.scope", SecondLevelAliasScope);
188 Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
189 }
190
191 /// Find the base pointer of an array access.
192 ///
193 /// This should be equivalent to ScalarEvolution::getPointerBase, which we
194 /// cannot use here the IR is still under construction which ScalarEvolution
195 /// assumes to not be modified.
findBasePtr(Value * Val)196 static Value *findBasePtr(Value *Val) {
197 while (true) {
198 if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
199 Val = Gep->getPointerOperand();
200 continue;
201 }
202 if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
203 Val = Cast->getOperand(0);
204 continue;
205 }
206
207 break;
208 }
209
210 return Val;
211 }
212
annotate(Instruction * Inst)213 void ScopAnnotator::annotate(Instruction *Inst) {
214 if (!Inst->mayReadOrWriteMemory())
215 return;
216
217 if (!ParallelLoops.empty())
218 Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
219
220 // TODO: Use the ScopArrayInfo once available here.
221 if (!AliasScopeDomain)
222 return;
223
224 // Do not apply annotations on memory operations that take more than one
225 // pointer. It would be ambiguous to which pointer the annotation applies.
226 // FIXME: How can we specify annotations for all pointer arguments?
227 if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
228 return;
229
230 auto *Ptr = getMemAccInstPointerOperand(Inst);
231 if (!Ptr)
232 return;
233
234 Value *BasePtr = findBasePtr(Ptr);
235 if (!BasePtr)
236 return;
237
238 auto AliasScope = AliasScopeMap.lookup(BasePtr);
239
240 if (!AliasScope) {
241 BasePtr = AlternativeAliasBases.lookup(BasePtr);
242 if (!BasePtr)
243 return;
244
245 AliasScope = AliasScopeMap.lookup(BasePtr);
246 if (!AliasScope)
247 return;
248 }
249
250 assert(OtherAliasScopeListMap.count(BasePtr) &&
251 "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
252 auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
253
254 if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
255 annotateSecondLevel(Inst, BasePtr);
256 return;
257 }
258
259 Inst->setMetadata("alias.scope", AliasScope);
260 Inst->setMetadata("noalias", OtherAliasScopeList);
261 }
262
addInterIterationAliasFreeBasePtr(llvm::Value * BasePtr)263 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
264 if (!BasePtr)
265 return;
266
267 InterIterationAliasFreeBasePtrs.insert(BasePtr);
268 }
269