polly/lib/CodeGen/IRBuilder.cpp

   1 //===------ PollyIRBuilder.cpp --------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 //
   9 // The Polly IRBuilder file contains Polly specific extensions for the IRBuilder
  10 // that are used e.g. to emit the llvm.loop.parallel metadata.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "polly/CodeGen/IRBuilder.h"
  15 #include "polly/ScopInfo.h"
  16 #include "polly/Support/ScopHelper.h"
  17 #include "llvm/ADT/SmallVector.h"
  18 #include "llvm/IR/Metadata.h"
  19
  20 using namespace llvm;
  21 using namespace polly;
  22
  23 static const int MaxArraysInAliasScops = 10;
  24
  25 /// Get a self referencing id metadata node.
  26 ///
  27 /// The MDNode looks like this (if arg0/arg1 are not null):
  28 ///
  29 ///    '!n = distinct !{!n, arg0, arg1}'
  30 ///
  31 /// @return The self referencing id metadata node.
  32 static MDNode *getID(LLVMContext &Ctx, Metadata *arg0 = nullptr,
  33                      Metadata *arg1 = nullptr) {
  34   MDNode *ID;
  35   SmallVector<Metadata *, 3> Args;
  36   // Reserve operand 0 for loop id self reference.
  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::getDistinct(Ctx, Args);
  45   ID->replaceOperandWith(0, ID);
  46   return ID;
  47 }
  48
  49 ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {
  50   // Push an empty staging BandAttr.
  51   LoopAttrEnv.emplace_back();
  52 }
  53
  54 ScopAnnotator::~ScopAnnotator() {
  55   assert(LoopAttrEnv.size() == 1 && "Loop stack imbalance");
  56   assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
  57 }
  58
  59 void ScopAnnotator::buildAliasScopes(Scop &S) {
  60   SE = S.getSE();
  61
  62   LLVMContext &Ctx = SE->getContext();
  63   AliasScopeDomain = getID(Ctx, MDString::get(Ctx, "polly.alias.scope.domain"));
  64
  65   AliasScopeMap.clear();
  66   OtherAliasScopeListMap.clear();
  67
  68   // We are only interested in arrays, but no scalar references. Scalars should
  69   // be handled easily by basicaa.
  70   SmallVector<ScopArrayInfo *, 10> Arrays;
  71   for (ScopArrayInfo *Array : S.arrays())
  72     if (Array->isArrayKind())
  73       Arrays.push_back(Array);
  74
  75   // The construction of alias scopes is quadratic in the number of arrays
  76   // involved. In case of too many arrays, skip the construction of alias
  77   // information to avoid quadratic increases in compile time and code size.
  78   if (Arrays.size() > MaxArraysInAliasScops)
  79     return;
  80
  81   std::string AliasScopeStr = "polly.alias.scope.";
  82   for (const ScopArrayInfo *Array : Arrays) {
  83     assert(Array->getBasePtr() && "Base pointer must be present");
  84     AliasScopeMap[Array->getBasePtr()] =
  85         getID(Ctx, AliasScopeDomain,
  86               MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
  87   }
  88
  89   for (const ScopArrayInfo *Array : Arrays) {
  90     MDNode *AliasScopeList = MDNode::get(Ctx, {});
  91     for (const auto &AliasScopePair : AliasScopeMap) {
  92       if (Array->getBasePtr() == AliasScopePair.first)
  93         continue;
  94
  95       Metadata *Args = {AliasScopePair.second};
  96       AliasScopeList =
  97           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
  98     }
  99
 100     OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
 101   }
 102 }
 103
 104 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
 105   ActiveLoops.push_back(L);
 106
 107   if (IsParallel) {
 108     LLVMContext &Ctx = SE->getContext();
 109     MDNode *AccessGroup = MDNode::getDistinct(Ctx, {});
 110     ParallelLoops.push_back(AccessGroup);
 111   }
 112
 113   // Open an empty BandAttr context for loops nested in this one.
 114   LoopAttrEnv.emplace_back();
 115 }
 116
 117 void ScopAnnotator::popLoop(bool IsParallel) {
 118   ActiveLoops.pop_back();
 119
 120   if (IsParallel) {
 121     assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
 122     ParallelLoops.pop_back();
 123   }
 124
 125   // Exit the subloop context.
 126   assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");
 127   assert(LoopAttrEnv.size() >= 2 && "Popped too many");
 128   LoopAttrEnv.pop_back();
 129 }
 130
 131 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
 132                                       bool IsLoopVectorizerDisabled) const {
 133   LLVMContext &Ctx = SE->getContext();
 134   SmallVector<Metadata *, 3> Args;
 135
 136   // For the LoopID self-reference.
 137   Args.push_back(nullptr);
 138
 139   // Add the user-defined loop properties to the annotation, if any. Any
 140   // additional properties are appended.
 141   // FIXME: What to do if these conflict?
 142   MDNode *MData = nullptr;
 143   if (BandAttr *AttrEnv = getActiveAttrEnv()) {
 144     MData = AttrEnv->Metadata;
 145     if (MData)
 146       llvm::append_range(Args, drop_begin(MData->operands(), 1));
 147   }
 148
 149   if (IsLoopVectorizerDisabled) {
 150     MDString *PropName = MDString::get(Ctx, "llvm.loop.vectorize.enable");
 151     ConstantInt *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
 152     ValueAsMetadata *PropValue = ValueAsMetadata::get(FalseValue);
 153     Args.push_back(MDNode::get(Ctx, {PropName, PropValue}));
 154   }
 155
 156   if (IsParallel) {
 157     MDString *PropName = MDString::get(Ctx, "llvm.loop.parallel_accesses");
 158     MDNode *AccGroup = ParallelLoops.back();
 159     Args.push_back(MDNode::get(Ctx, {PropName, AccGroup}));
 160   }
 161
 162   // No metadata to annotate.
 163   if (!MData && Args.size() <= 1)
 164     return;
 165
 166   // Reuse the MData node if possible, this will avoid having to create another
 167   // one that cannot be merged because LoopIDs are 'distinct'. However, we have
 168   // to create a new one if we add properties.
 169   if (!MData || Args.size() > MData->getNumOperands()) {
 170     MData = MDNode::getDistinct(Ctx, Args);
 171     MData->replaceOperandWith(0, MData);
 172   }
 173   B->setMetadata(LLVMContext::MD_loop, MData);
 174 }
 175
 176 /// Get the pointer operand
 177 ///
 178 /// @param Inst The instruction to be analyzed.
 179 /// @return the pointer operand in case @p Inst is a memory access
 180 ///         instruction and nullptr otherwise.
 181 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
 182   auto MemInst = MemAccInst::dyn_cast(Inst);
 183   if (!MemInst)
 184     return nullptr;
 185
 186   return MemInst.getPointerOperand();
 187 }
 188
 189 /// Find the base pointer of an array access.
 190 ///
 191 /// This should be equivalent to ScalarEvolution::getPointerBase, which we
 192 /// cannot use here the IR is still under construction which ScalarEvolution
 193 /// assumes to not be modified.
 194 static Value *findBasePtr(Value *Val) {
 195   while (true) {
 196     if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
 197       Val = Gep->getPointerOperand();
 198       continue;
 199     }
 200     if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
 201       Val = Cast->getOperand(0);
 202       continue;
 203     }
 204
 205     break;
 206   }
 207
 208   return Val;
 209 }
 210
 211 void ScopAnnotator::annotate(Instruction *Inst) {
 212   if (!Inst->mayReadOrWriteMemory())
 213     return;
 214
 215   switch (ParallelLoops.size()) {
 216   case 0:
 217     // Not parallel to anything: no access group needed.
 218     break;
 219   case 1:
 220     // Single parallel loop: use directly.
 221     Inst->setMetadata(LLVMContext::MD_access_group,
 222                       cast<MDNode>(ParallelLoops.front()));
 223     break;
 224   default:
 225     // Parallel to multiple loops: refer to list of access groups.
 226     Inst->setMetadata(LLVMContext::MD_access_group,
 227                       MDNode::get(SE->getContext(),
 228                                   ArrayRef<Metadata *>(
 229                                       (Metadata *const *)ParallelLoops.data(),
 230                                       ParallelLoops.size())));
 231     break;
 232   }
 233
 234   // TODO: Use the ScopArrayInfo once available here.
 235   if (!AliasScopeDomain)
 236     return;
 237
 238   // Do not apply annotations on memory operations that take more than one
 239   // pointer. It would be ambiguous to which pointer the annotation applies.
 240   // FIXME: How can we specify annotations for all pointer arguments?
 241   if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
 242     return;
 243
 244   auto *Ptr = getMemAccInstPointerOperand(Inst);
 245   if (!Ptr)
 246     return;
 247
 248   Value *BasePtr = findBasePtr(Ptr);
 249   if (!BasePtr)
 250     return;
 251
 252   auto AliasScope = AliasScopeMap.lookup(BasePtr);
 253
 254   if (!AliasScope) {
 255     BasePtr = AlternativeAliasBases.lookup(BasePtr);
 256     if (!BasePtr)
 257       return;
 258
 259     AliasScope = AliasScopeMap.lookup(BasePtr);
 260     if (!AliasScope)
 261       return;
 262   }
 263
 264   assert(OtherAliasScopeListMap.count(BasePtr) &&
 265          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
 266   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
 267
 268   Inst->setMetadata("alias.scope", MDNode::get(SE->getContext(), AliasScope));
 269   Inst->setMetadata("noalias", OtherAliasScopeList);
 270 }