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