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/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   // The construction of alias scopes is quadratic in the number of arrays
64   // involved. In case of too many arrays, skip the construction of alias
65   // information to avoid quadratic increases in compile time and code size.
66   if (std::distance(S.array_begin(), S.array_end()) > MaxArraysInAliasScops)
67     return;
68 
69   std::string AliasScopeStr = "polly.alias.scope.";
70   for (const ScopArrayInfo *Array : S.arrays()) {
71     assert(Array->getBasePtr() && "Base pointer must be present");
72     AliasScopeMap[Array->getBasePtr()] =
73         getID(Ctx, AliasScopeDomain,
74               MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
75   }
76 
77   for (const ScopArrayInfo *Array : S.arrays()) {
78     MDNode *AliasScopeList = MDNode::get(Ctx, {});
79     for (const auto &AliasScopePair : AliasScopeMap) {
80       if (Array->getBasePtr() == AliasScopePair.first)
81         continue;
82 
83       Metadata *Args = {AliasScopePair.second};
84       AliasScopeList =
85           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
86     }
87 
88     OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
89   }
90 }
91 
92 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
93 
94   ActiveLoops.push_back(L);
95   if (!IsParallel)
96     return;
97 
98   BasicBlock *Header = L->getHeader();
99   MDNode *Id = getID(Header->getContext());
100   assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
101   assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
102   MDNode *Ids = ParallelLoops.empty()
103                     ? Id
104                     : MDNode::concatenate(ParallelLoops.back(), Id);
105   ParallelLoops.push_back(Ids);
106 }
107 
108 void ScopAnnotator::popLoop(bool IsParallel) {
109   ActiveLoops.pop_back();
110   if (!IsParallel)
111     return;
112 
113   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
114   ParallelLoops.pop_back();
115 }
116 
117 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
118                                       bool IsParallel) const {
119   if (!IsParallel)
120     return;
121 
122   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
123   MDNode *Ids = ParallelLoops.back();
124   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
125   B->setMetadata("llvm.loop", Id);
126 }
127 
128 /// Get the pointer operand
129 ///
130 /// @param Inst The instruction to be analyzed.
131 /// @return the pointer operand in case @p Inst is a memory access
132 ///         instruction and nullptr otherwise.
133 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
134   auto MemInst = MemAccInst::dyn_cast(Inst);
135   if (!MemInst)
136     return nullptr;
137 
138   return MemInst.getPointerOperand();
139 }
140 
141 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
142                                         llvm::Value *BasePtr) {
143   auto *Ptr = getMemAccInstPointerOperand(Inst);
144   if (!Ptr)
145     return;
146   auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(Ptr);
147   auto SecondLevelOtherAliasScopeList =
148       SecondLevelOtherAliasScopeListMap.lookup(Ptr);
149   if (!SecondLevelAliasScope) {
150     auto AliasScope = AliasScopeMap.lookup(BasePtr);
151     if (!AliasScope)
152       return;
153     LLVMContext &Ctx = SE->getContext();
154     SecondLevelAliasScope = getID(
155         Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
156     SecondLevelAliasScopeMap[Ptr] = SecondLevelAliasScope;
157     Metadata *Args = {SecondLevelAliasScope};
158     auto SecondLevelBasePtrAliasScopeList =
159         SecondLevelAliasScopeMap.lookup(BasePtr);
160     SecondLevelAliasScopeMap[BasePtr] = MDNode::concatenate(
161         SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
162     auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
163     SecondLevelOtherAliasScopeList = MDNode::concatenate(
164         OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
165     SecondLevelOtherAliasScopeListMap[Ptr] = SecondLevelOtherAliasScopeList;
166   }
167   Inst->setMetadata("alias.scope", SecondLevelAliasScope);
168   Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
169 }
170 
171 void ScopAnnotator::annotate(Instruction *Inst) {
172   if (!Inst->mayReadOrWriteMemory())
173     return;
174 
175   if (!ParallelLoops.empty())
176     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
177 
178   // TODO: Use the ScopArrayInfo once available here.
179   if (!AliasScopeDomain)
180     return;
181 
182   auto *Ptr = getMemAccInstPointerOperand(Inst);
183   if (!Ptr)
184     return;
185 
186   auto *PtrSCEV = SE->getSCEV(Ptr);
187   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
188   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
189 
190   if (!SU)
191     return;
192 
193   auto *BasePtr = SU->getValue();
194 
195   if (!BasePtr)
196     return;
197 
198   auto AliasScope = AliasScopeMap.lookup(BasePtr);
199 
200   if (!AliasScope) {
201     BasePtr = AlternativeAliasBases.lookup(BasePtr);
202     if (!BasePtr)
203       return;
204 
205     AliasScope = AliasScopeMap.lookup(BasePtr);
206     if (!AliasScope)
207       return;
208   }
209 
210   assert(OtherAliasScopeListMap.count(BasePtr) &&
211          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
212   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
213 
214   if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
215     annotateSecondLevel(Inst, BasePtr);
216     return;
217   }
218 
219   Inst->setMetadata("alias.scope", AliasScope);
220   Inst->setMetadata("noalias", OtherAliasScopeList);
221 }
222 
223 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
224   if (!BasePtr)
225     return;
226 
227   InterIterationAliasFreeBasePtrs.insert(BasePtr);
228 }
229