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   SetVector<Value *> BasePtrs;
62   for (ScopStmt &Stmt : S)
63     for (MemoryAccess *MA : Stmt)
64       if (!Stmt.isCopyStmt())
65         BasePtrs.insert(MA->getBaseAddr());
66 
67   std::string AliasScopeStr = "polly.alias.scope.";
68   for (Value *BasePtr : BasePtrs)
69     AliasScopeMap[BasePtr] = getID(
70         Ctx, AliasScopeDomain,
71         MDString::get(Ctx, (AliasScopeStr + BasePtr->getName()).str().c_str()));
72 
73   for (Value *BasePtr : BasePtrs) {
74     MDNode *AliasScopeList = MDNode::get(Ctx, {});
75     for (const auto &AliasScopePair : AliasScopeMap) {
76       if (BasePtr == AliasScopePair.first)
77         continue;
78 
79       Metadata *Args = {AliasScopePair.second};
80       AliasScopeList =
81           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
82     }
83 
84     OtherAliasScopeListMap[BasePtr] = AliasScopeList;
85   }
86 }
87 
88 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
89 
90   ActiveLoops.push_back(L);
91   if (!IsParallel)
92     return;
93 
94   BasicBlock *Header = L->getHeader();
95   MDNode *Id = getID(Header->getContext());
96   assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
97   assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
98   MDNode *Ids = ParallelLoops.empty()
99                     ? Id
100                     : MDNode::concatenate(ParallelLoops.back(), Id);
101   ParallelLoops.push_back(Ids);
102 }
103 
104 void ScopAnnotator::popLoop(bool IsParallel) {
105   ActiveLoops.pop_back();
106   if (!IsParallel)
107     return;
108 
109   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
110   ParallelLoops.pop_back();
111 }
112 
113 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
114                                       bool IsParallel) const {
115   if (!IsParallel)
116     return;
117 
118   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
119   MDNode *Ids = ParallelLoops.back();
120   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
121   B->setMetadata("llvm.loop", Id);
122 }
123 
124 void ScopAnnotator::annotate(Instruction *Inst) {
125   if (!Inst->mayReadOrWriteMemory())
126     return;
127 
128   if (!ParallelLoops.empty())
129     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
130 
131   // TODO: Use the ScopArrayInfo once available here.
132   if (!AliasScopeDomain)
133     return;
134 
135   auto MemInst = MemAccInst::dyn_cast(Inst);
136   if (!MemInst)
137     return;
138 
139   auto *Ptr = MemInst.getPointerOperand();
140   if (!Ptr)
141     return;
142 
143   auto *PtrSCEV = SE->getSCEV(Ptr);
144   auto *BaseSCEV = SE->getPointerBase(PtrSCEV);
145   auto *SU = dyn_cast<SCEVUnknown>(BaseSCEV);
146 
147   if (!SU)
148     return;
149 
150   auto *BasePtr = SU->getValue();
151 
152   if (!BasePtr)
153     return;
154 
155   auto AliasScope = AliasScopeMap.lookup(BasePtr);
156 
157   if (!AliasScope) {
158     BasePtr = AlternativeAliasBases.lookup(BasePtr);
159     if (!BasePtr)
160       return;
161 
162     AliasScope = AliasScopeMap.lookup(BasePtr);
163     if (!AliasScope)
164       return;
165   }
166 
167   assert(OtherAliasScopeListMap.count(BasePtr) &&
168          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
169   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
170 
171   Inst->setMetadata("alias.scope", AliasScope);
172   Inst->setMetadata("noalias", OtherAliasScopeList);
173 }
174