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 /// Get a self referencing id metadata node.
25 ///
26 /// The MDNode looks like this (if arg0/arg1 are not null):
27 ///
28 ///    '!n = metadata !{metadata !n, arg0, arg1}'
29 ///
30 /// @return The self referencing id metadata node.
31 static MDNode *getID(LLVMContext &Ctx, Metadata *arg0 = nullptr,
32                      Metadata *arg1 = nullptr) {
33   MDNode *ID;
34   SmallVector<Metadata *, 3> Args;
35   // Use a temporary node to safely create a unique pointer for the first arg.
36   auto TempNode = MDNode::getTemporary(Ctx, None);
37   // Reserve operand 0 for loop id self reference.
38   Args.push_back(TempNode.get());
39 
40   if (arg0)
41     Args.push_back(arg0);
42   if (arg1)
43     Args.push_back(arg1);
44 
45   ID = MDNode::get(Ctx, Args);
46   ID->replaceOperandWith(0, ID);
47   return ID;
48 }
49 
50 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
51 
52 void ScopAnnotator::buildAliasScopes(Scop &S) {
53   SE = S.getSE();
54 
55   LLVMContext &Ctx = SE->getContext();
56   AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
57 
58   AliasScopeMap.clear();
59   OtherAliasScopeListMap.clear();
60 
61   std::string AliasScopeStr = "polly.alias.scope.";
62   for (const ScopArrayInfo *Array : S.arrays())
63     AliasScopeMap[Array->getBasePtr()] =
64         getID(Ctx, AliasScopeDomain,
65               MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
66 
67   for (const ScopArrayInfo *Array : S.arrays()) {
68     MDNode *AliasScopeList = MDNode::get(Ctx, {});
69     for (const auto &AliasScopePair : AliasScopeMap) {
70       if (Array->getBasePtr() == AliasScopePair.first)
71         continue;
72 
73       Metadata *Args = {AliasScopePair.second};
74       AliasScopeList =
75           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
76     }
77 
78     OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
79   }
80 }
81 
82 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
83 
84   ActiveLoops.push_back(L);
85   if (!IsParallel)
86     return;
87 
88   BasicBlock *Header = L->getHeader();
89   MDNode *Id = getID(Header->getContext());
90   assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
91   assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
92   MDNode *Ids = ParallelLoops.empty()
93                     ? Id
94                     : MDNode::concatenate(ParallelLoops.back(), Id);
95   ParallelLoops.push_back(Ids);
96 }
97 
98 void ScopAnnotator::popLoop(bool IsParallel) {
99   ActiveLoops.pop_back();
100   if (!IsParallel)
101     return;
102 
103   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
104   ParallelLoops.pop_back();
105 }
106 
107 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
108                                       bool IsParallel) const {
109   if (!IsParallel)
110     return;
111 
112   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
113   MDNode *Ids = ParallelLoops.back();
114   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
115   B->setMetadata("llvm.loop", Id);
116 }
117 
118 /// Get the pointer operand
119 ///
120 /// @param Inst The instruction to be analyzed.
121 /// @return the pointer operand in case @p Inst is a memory access
122 ///         instruction and nullptr otherwise.
123 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
124   auto MemInst = MemAccInst::dyn_cast(Inst);
125   if (!MemInst)
126     return nullptr;
127 
128   return MemInst.getPointerOperand();
129 }
130 
131 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
132                                         llvm::Value *BasePtr) {
133   auto *Ptr = getMemAccInstPointerOperand(Inst);
134   if (!Ptr)
135     return;
136   auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(Ptr);
137   auto SecondLevelOtherAliasScopeList =
138       SecondLevelOtherAliasScopeListMap.lookup(Ptr);
139   if (!SecondLevelAliasScope) {
140     auto AliasScope = AliasScopeMap.lookup(BasePtr);
141     if (!AliasScope)
142       return;
143     LLVMContext &Ctx = SE->getContext();
144     SecondLevelAliasScope = getID(
145         Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
146     SecondLevelAliasScopeMap[Ptr] = SecondLevelAliasScope;
147     Metadata *Args = {SecondLevelAliasScope};
148     auto SecondLevelBasePtrAliasScopeList =
149         SecondLevelAliasScopeMap.lookup(BasePtr);
150     SecondLevelAliasScopeMap[BasePtr] = MDNode::concatenate(
151         SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
152     auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
153     SecondLevelOtherAliasScopeList = MDNode::concatenate(
154         OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
155     SecondLevelOtherAliasScopeListMap[Ptr] = SecondLevelOtherAliasScopeList;
156   }
157   Inst->setMetadata("alias.scope", SecondLevelAliasScope);
158   Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
159 }
160 
161 void ScopAnnotator::annotate(Instruction *Inst) {
162   if (!Inst->mayReadOrWriteMemory())
163     return;
164 
165   if (!ParallelLoops.empty())
166     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
167 
168   // TODO: Use the ScopArrayInfo once available here.
169   if (!AliasScopeDomain)
170     return;
171 
172   auto *Ptr = getMemAccInstPointerOperand(Inst);
173   if (!Ptr)
174     return;
175 
176   auto *PtrSCEV = SE->getSCEV(Ptr);
177   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
178   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
179 
180   if (!SU)
181     return;
182 
183   auto *BasePtr = SU->getValue();
184 
185   if (!BasePtr)
186     return;
187 
188   auto AliasScope = AliasScopeMap.lookup(BasePtr);
189 
190   if (!AliasScope) {
191     BasePtr = AlternativeAliasBases.lookup(BasePtr);
192     if (!BasePtr)
193       return;
194 
195     AliasScope = AliasScopeMap.lookup(BasePtr);
196     if (!AliasScope)
197       return;
198   }
199 
200   assert(OtherAliasScopeListMap.count(BasePtr) &&
201          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
202   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
203 
204   if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
205     annotateSecondLevel(Inst, BasePtr);
206     return;
207   }
208 
209   Inst->setMetadata("alias.scope", AliasScope);
210   Inst->setMetadata("noalias", OtherAliasScopeList);
211 }
212 
213 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
214   if (!BasePtr)
215     return;
216 
217   InterIterationAliasFreeBasePtrs.insert(BasePtr);
218 }
219