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