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.
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 
49 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
50 
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 
96 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
97   ActiveLoops.push_back(L);
98 
99   if (IsParallel) {
100     LLVMContext &Ctx = SE->getContext();
101     MDNode *AccessGroup = MDNode::getDistinct(Ctx, {});
102     ParallelLoops.push_back(AccessGroup);
103   }
104 }
105 
106 void ScopAnnotator::popLoop(bool IsParallel) {
107   ActiveLoops.pop_back();
108 
109   if (IsParallel) {
110     assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
111     ParallelLoops.pop_back();
112   }
113 }
114 
115 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
116                                       bool IsLoopVectorizerDisabled) const {
117   LLVMContext &Ctx = SE->getContext();
118   SmallVector<Metadata *, 3> Args;
119 
120   // For the LoopID self-reference.
121   Args.push_back(nullptr);
122 
123   if (IsLoopVectorizerDisabled) {
124     MDString *PropName = MDString::get(Ctx, "llvm.loop.vectorize.enable");
125     ConstantInt *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
126     ValueAsMetadata *PropValue = ValueAsMetadata::get(FalseValue);
127     Args.push_back(MDNode::get(Ctx, {PropName, PropValue}));
128   }
129 
130   if (IsParallel) {
131     MDString *PropName = MDString::get(Ctx, "llvm.loop.parallel_accesses");
132     MDNode *AccGroup = ParallelLoops.back();
133     Args.push_back(MDNode::get(Ctx, {PropName, AccGroup}));
134   }
135 
136   // No metadata to annotate.
137   if (Args.size() <= 1)
138     return;
139 
140   MDNode *MData = MDNode::getDistinct(Ctx, Args);
141   MData->replaceOperandWith(0, MData);
142   B->setMetadata(LLVMContext::MD_loop, MData);
143 }
144 
145 /// Get the pointer operand
146 ///
147 /// @param Inst The instruction to be analyzed.
148 /// @return the pointer operand in case @p Inst is a memory access
149 ///         instruction and nullptr otherwise.
150 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
151   auto MemInst = MemAccInst::dyn_cast(Inst);
152   if (!MemInst)
153     return nullptr;
154 
155   return MemInst.getPointerOperand();
156 }
157 
158 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
159                                         llvm::Value *BasePtr) {
160   Value *Ptr = getMemAccInstPointerOperand(Inst);
161   if (!Ptr)
162     return;
163 
164   auto *PtrSCEV = SE->getSCEV(Ptr);
165   auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
166 
167   auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
168   auto SecondLevelOtherAliasScopeList =
169       SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
170   if (!SecondLevelAliasScope) {
171     auto AliasScope = AliasScopeMap.lookup(BasePtr);
172     if (!AliasScope)
173       return;
174     LLVMContext &Ctx = SE->getContext();
175     SecondLevelAliasScope = getID(
176         Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
177     SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
178     Metadata *Args = {SecondLevelAliasScope};
179     auto SecondLevelBasePtrAliasScopeList =
180         SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
181     SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
182         SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
183     auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
184     SecondLevelOtherAliasScopeList = MDNode::concatenate(
185         OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
186     SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
187   }
188   Inst->setMetadata("alias.scope", SecondLevelAliasScope);
189   Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
190 }
191 
192 /// Find the base pointer of an array access.
193 ///
194 /// This should be equivalent to ScalarEvolution::getPointerBase, which we
195 /// cannot use here the IR is still under construction which ScalarEvolution
196 /// assumes to not be modified.
197 static Value *findBasePtr(Value *Val) {
198   while (true) {
199     if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
200       Val = Gep->getPointerOperand();
201       continue;
202     }
203     if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
204       Val = Cast->getOperand(0);
205       continue;
206     }
207 
208     break;
209   }
210 
211   return Val;
212 }
213 
214 void ScopAnnotator::annotate(Instruction *Inst) {
215   if (!Inst->mayReadOrWriteMemory())
216     return;
217 
218   switch (ParallelLoops.size()) {
219   case 0:
220     // Not parallel to anything: no access group needed.
221     break;
222   case 1:
223     // Single parallel loop: use directly.
224     Inst->setMetadata(LLVMContext::MD_access_group,
225                       cast<MDNode>(ParallelLoops.front()));
226     break;
227   default:
228     // Parallel to multiple loops: refer to list of access groups.
229     Inst->setMetadata(LLVMContext::MD_access_group,
230                       MDNode::get(SE->getContext(),
231                                   ArrayRef<Metadata *>(
232                                       (Metadata *const *)ParallelLoops.data(),
233                                       ParallelLoops.size())));
234     break;
235   }
236 
237   // TODO: Use the ScopArrayInfo once available here.
238   if (!AliasScopeDomain)
239     return;
240 
241   // Do not apply annotations on memory operations that take more than one
242   // pointer. It would be ambiguous to which pointer the annotation applies.
243   // FIXME: How can we specify annotations for all pointer arguments?
244   if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
245     return;
246 
247   auto *Ptr = getMemAccInstPointerOperand(Inst);
248   if (!Ptr)
249     return;
250 
251   Value *BasePtr = findBasePtr(Ptr);
252   if (!BasePtr)
253     return;
254 
255   auto AliasScope = AliasScopeMap.lookup(BasePtr);
256 
257   if (!AliasScope) {
258     BasePtr = AlternativeAliasBases.lookup(BasePtr);
259     if (!BasePtr)
260       return;
261 
262     AliasScope = AliasScopeMap.lookup(BasePtr);
263     if (!AliasScope)
264       return;
265   }
266 
267   assert(OtherAliasScopeListMap.count(BasePtr) &&
268          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
269   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
270 
271   if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
272     annotateSecondLevel(Inst, BasePtr);
273     return;
274   }
275 
276   Inst->setMetadata("alias.scope", AliasScope);
277   Inst->setMetadata("noalias", OtherAliasScopeList);
278 }
279 
280 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
281   if (!BasePtr)
282     return;
283 
284   InterIterationAliasFreeBasePtrs.insert(BasePtr);
285 }
286