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