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.
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 // 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
ScopAnnotator()51 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
52
buildAliasScopes(Scop & S)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
pushLoop(Loop * L,bool IsParallel)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
popLoop(bool IsParallel)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
annotateLoopLatch(BranchInst * B,Loop * L,bool IsParallel,bool IsLoopVectorizerDisabled) const123 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.
getMemAccInstPointerOperand(Instruction * Inst)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
annotateSecondLevel(llvm::Instruction * Inst,llvm::Value * BasePtr)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
annotate(Instruction * Inst)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
addInterIterationAliasFreeBasePtr(llvm::Value * BasePtr)251 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
252 if (!BasePtr)
253 return;
254
255 InterIterationAliasFreeBasePtrs.insert(BasePtr);
256 }
257