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