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 
17 #include "polly/ScopInfo.h"
18 #include "polly/Support/ScopHelper.h"
19 
20 #include "llvm/IR/Metadata.h"
21 #include "llvm/Support/Debug.h"
22 
23 using namespace llvm;
24 using namespace polly;
25 
26 /// @brief 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, Value *arg0 = nullptr,
34                      Value *arg1 = nullptr) {
35   MDNode *ID;
36   SmallVector<Value *, 3> Args;
37   Args.push_back(nullptr);
38 
39   if (arg0)
40     Args.push_back(arg0);
41   if (arg1)
42     Args.push_back(arg1);
43 
44   ID = MDNode::get(Ctx, Args);
45   ID->replaceOperandWith(0, ID);
46   return ID;
47 }
48 
49 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {}
50 
51 void ScopAnnotator::buildAliasScopes(Scop &S) {
52   SE = S.getSE();
53 
54   LLVMContext &Ctx = SE->getContext();
55   AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
56 
57   AliasScopeMap.clear();
58   OtherAliasScopeListMap.clear();
59 
60   SetVector<Value *> BasePtrs;
61   for (ScopStmt *Stmt : S)
62     for (MemoryAccess *MA : *Stmt)
63       BasePtrs.insert(MA->getBaseAddr());
64 
65   std::string AliasScopeStr = "polly.alias.scope.";
66   for (Value *BasePtr : BasePtrs)
67     AliasScopeMap[BasePtr] = getID(
68         Ctx, AliasScopeDomain,
69         MDString::get(Ctx, (AliasScopeStr + BasePtr->getName()).str().c_str()));
70 
71   for (Value *BasePtr : BasePtrs) {
72     MDNode *AliasScopeList = MDNode::get(Ctx, {});
73     for (const auto &AliasScopePair : AliasScopeMap) {
74       if (BasePtr == AliasScopePair.first)
75         continue;
76 
77       Value *Args = {AliasScopePair.second};
78       AliasScopeList =
79           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
80     }
81 
82     OtherAliasScopeListMap[BasePtr] = AliasScopeList;
83   }
84 }
85 
86 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
87 
88   ActiveLoops.push_back(L);
89   if (!IsParallel)
90     return;
91 
92   BasicBlock *Header = L->getHeader();
93   MDNode *Id = getID(Header->getContext());
94   Value *Args[] = {Id};
95   MDNode *Ids = ParallelLoops.empty()
96                     ? MDNode::get(Header->getContext(), Args)
97                     : MDNode::concatenate(ParallelLoops.back(), Id);
98   ParallelLoops.push_back(Ids);
99 }
100 
101 void ScopAnnotator::popLoop(bool IsParallel) {
102   ActiveLoops.pop_back();
103   if (!IsParallel)
104     return;
105 
106   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
107   ParallelLoops.pop_back();
108 }
109 
110 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L,
111                                       bool IsParallel) const {
112   if (!IsParallel)
113     return;
114 
115   assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
116   MDNode *Ids = ParallelLoops.back();
117   MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
118   B->setMetadata("llvm.loop", Id);
119 }
120 
121 void ScopAnnotator::annotate(Instruction *Inst) {
122   if (!Inst->mayReadOrWriteMemory())
123     return;
124 
125   // TODO: Use the ScopArrayInfo once available here.
126   if (AliasScopeDomain) {
127     Value *BasePtr = nullptr;
128     if (isa<StoreInst>(Inst) || isa<LoadInst>(Inst)) {
129       const SCEV *PtrSCEV = SE->getSCEV(getPointerOperand(*Inst));
130       const SCEV *BaseSCEV = SE->getPointerBase(PtrSCEV);
131       if (const SCEVUnknown *SU = dyn_cast<SCEVUnknown>(BaseSCEV))
132         BasePtr = SU->getValue();
133     }
134 
135     if (BasePtr) {
136       Inst->setMetadata("alias.scope", AliasScopeMap[BasePtr]);
137       Inst->setMetadata("noalias", OtherAliasScopeListMap[BasePtr]);
138     }
139   }
140 
141   if (ParallelLoops.empty())
142     return;
143 
144   Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
145 }
146