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   // Push an empty staging BandAttr.
51   LoopAttrEnv.emplace_back();
52 }
53 
54 ScopAnnotator::~ScopAnnotator() {
55   assert(LoopAttrEnv.size() == 1 && "Loop stack imbalance");
56   assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
57 }
58 
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 
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 
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 
131 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.
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 
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.
194 static 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(0);
202       continue;
203     }
204 
205     break;
206   }
207 
208   return Val;
209 }
210 
211 void 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(LLVMContext::MD_access_group,
222                       cast<MDNode>(ParallelLoops.front()));
223     break;
224   default:
225     // Parallel to multiple loops: refer to list of access groups.
226     Inst->setMetadata(LLVMContext::MD_access_group,
227                       MDNode::get(SE->getContext(),
228                                   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>(Inst) && !isa<MemSetInst>(Inst))
242     return;
243 
244   auto *Ptr = getMemAccInstPointerOperand(Inst);
245   if (!Ptr)
246     return;
247 
248   Value *BasePtr = findBasePtr(Ptr);
249   if (!BasePtr)
250     return;
251 
252   auto AliasScope = AliasScopeMap.lookup(BasePtr);
253 
254   if (!AliasScope) {
255     BasePtr = AlternativeAliasBases.lookup(BasePtr);
256     if (!BasePtr)
257       return;
258 
259     AliasScope = AliasScopeMap.lookup(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("alias.scope", MDNode::get(SE->getContext(), AliasScope));
269   Inst->setMetadata("noalias", OtherAliasScopeList);
270 }
271