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 
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 
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 
121 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.
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 
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 void ScopAnnotator::annotate(Instruction *Inst) {
192   if (!Inst->mayReadOrWriteMemory())
193     return;
194 
195   if (!ParallelLoops.empty())
196     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
197 
198   // TODO: Use the ScopArrayInfo once available here.
199   if (!AliasScopeDomain)
200     return;
201 
202   // Do not apply annotations on memory operations that take more than one
203   // pointer. It would be ambiguous to which pointer the annotation applies.
204   // FIXME: How can we specify annotations for all pointer arguments?
205   if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
206     return;
207 
208   auto *Ptr = getMemAccInstPointerOperand(Inst);
209   if (!Ptr)
210     return;
211 
212   auto *PtrSCEV = SE->getSCEV(Ptr);
213   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
214   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
215 
216   if (!SU)
217     return;
218 
219   auto *BasePtr = SU->getValue();
220 
221   if (!BasePtr)
222     return;
223 
224   auto AliasScope = AliasScopeMap.lookup(BasePtr);
225 
226   if (!AliasScope) {
227     BasePtr = AlternativeAliasBases.lookup(BasePtr);
228     if (!BasePtr)
229       return;
230 
231     AliasScope = AliasScopeMap.lookup(BasePtr);
232     if (!AliasScope)
233       return;
234   }
235 
236   assert(OtherAliasScopeListMap.count(BasePtr) &&
237          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
238   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
239 
240   if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
241     annotateSecondLevel(Inst, BasePtr);
242     return;
243   }
244 
245   Inst->setMetadata("alias.scope", AliasScope);
246   Inst->setMetadata("noalias", OtherAliasScopeList);
247 }
248 
249 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
250   if (!BasePtr)
251     return;
252 
253   InterIterationAliasFreeBasePtrs.insert(BasePtr);
254 }
255