lib/CodeGen/IRBuilder.cpp

   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 }