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
  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   // We are only interested in arrays, but no scalar references. Scalars should
  61   // be handled easily by basicaa.
  62   SmallVector<ScopArrayInfo *, 10> Arrays;
  63   for (ScopArrayInfo *Array : S.arrays())
  64     if (Array->isArrayKind())
  65       Arrays.push_back(Array);
  66
  67   // The construction of alias scopes is quadratic in the number of arrays
  68   // involved. In case of too many arrays, skip the construction of alias
  69   // information to avoid quadratic increases in compile time and code size.
  70   if (Arrays.size() > MaxArraysInAliasScops)
  71     return;
  72
  73   std::string AliasScopeStr = "polly.alias.scope.";
  74   for (const ScopArrayInfo *Array : Arrays) {
  75     assert(Array->getBasePtr() && "Base pointer must be present");
  76     AliasScopeMap[Array->getBasePtr()] =
  77         getID(Ctx, AliasScopeDomain,
  78               MDString::get(Ctx, (AliasScopeStr + Array->getName()).c_str()));
  79   }
  80
  81   for (const ScopArrayInfo *Array : Arrays) {
  82     MDNode *AliasScopeList = MDNode::get(Ctx, {});
  83     for (const auto &AliasScopePair : AliasScopeMap) {
  84       if (Array->getBasePtr() == AliasScopePair.first)
  85         continue;
  86
  87       Metadata *Args = {AliasScopePair.second};
  88       AliasScopeList =
  89           MDNode::concatenate(AliasScopeList, MDNode::get(Ctx, Args));
  90     }
  91
  92     OtherAliasScopeListMap[Array->getBasePtr()] = AliasScopeList;
  93   }
  94 }
  95
  96 void ScopAnnotator::pushLoop(Loop *L, bool IsParallel) {
  97
  98   ActiveLoops.push_back(L);
  99   if (!IsParallel)
 100     return;
 101
 102   BasicBlock *Header = L->getHeader();
 103   MDNode *Id = getID(Header->getContext());
 104   assert(Id->getOperand(0) == Id && "Expected Id to be a self-reference");
 105   assert(Id->getNumOperands() == 1 && "Unexpected extra operands in Id");
 106   MDNode *Ids = ParallelLoops.empty()
 107                     ? Id
 108                     : MDNode::concatenate(ParallelLoops.back(), Id);
 109   ParallelLoops.push_back(Ids);
 110 }
 111
 112 void ScopAnnotator::popLoop(bool IsParallel) {
 113   ActiveLoops.pop_back();
 114   if (!IsParallel)
 115     return;
 116
 117   assert(!ParallelLoops.empty() && "Expected a parallel loop to pop");
 118   ParallelLoops.pop_back();
 119 }
 120
 121 void ScopAnnotator::annotateLoopLatch(BranchInst *B, Loop *L, bool IsParallel,
 122                                       bool IsLoopVectorizerDisabled) const {
 123   MDNode *MData = nullptr;
 124
 125   if (IsLoopVectorizerDisabled) {
 126     SmallVector<Metadata *, 3> Args;
 127     LLVMContext &Ctx = SE->getContext();
 128     Args.push_back(MDString::get(Ctx, "llvm.loop.vectorize.enable"));
 129     auto *FalseValue = ConstantInt::get(Type::getInt1Ty(Ctx), 0);
 130     Args.push_back(ValueAsMetadata::get(FalseValue));
 131     MData = MDNode::concatenate(MData, getID(Ctx, MDNode::get(Ctx, Args)));
 132   }
 133
 134   if (IsParallel) {
 135     assert(!ParallelLoops.empty() && "Expected a parallel loop to annotate");
 136     MDNode *Ids = ParallelLoops.back();
 137     MDNode *Id = cast<MDNode>(Ids->getOperand(Ids->getNumOperands() - 1));
 138     MData = MDNode::concatenate(MData, Id);
 139   }
 140
 141   B->setMetadata("llvm.loop", MData);
 142 }
 143
 144 /// Get the pointer operand
 145 ///
 146 /// @param Inst The instruction to be analyzed.
 147 /// @return the pointer operand in case @p Inst is a memory access
 148 ///         instruction and nullptr otherwise.
 149 static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {
 150   auto MemInst = MemAccInst::dyn_cast(Inst);
 151   if (!MemInst)
 152     return nullptr;
 153
 154   return MemInst.getPointerOperand();
 155 }
 156
 157 void ScopAnnotator::annotateSecondLevel(llvm::Instruction *Inst,
 158                                         llvm::Value *BasePtr) {
 159   Value *Ptr = getMemAccInstPointerOperand(Inst);
 160   if (!Ptr)
 161     return;
 162
 163   auto *PtrSCEV = SE->getSCEV(Ptr);
 164   auto *BasePtrSCEV = SE->getPointerBase(PtrSCEV);
 165
 166   auto SecondLevelAliasScope = SecondLevelAliasScopeMap.lookup(PtrSCEV);
 167   auto SecondLevelOtherAliasScopeList =
 168       SecondLevelOtherAliasScopeListMap.lookup(PtrSCEV);
 169   if (!SecondLevelAliasScope) {
 170     auto AliasScope = AliasScopeMap.lookup(BasePtr);
 171     if (!AliasScope)
 172       return;
 173     LLVMContext &Ctx = SE->getContext();
 174     SecondLevelAliasScope = getID(
 175         Ctx, AliasScope, MDString::get(Ctx, "second level alias metadata"));
 176     SecondLevelAliasScopeMap[PtrSCEV] = SecondLevelAliasScope;
 177     Metadata *Args = {SecondLevelAliasScope};
 178     auto SecondLevelBasePtrAliasScopeList =
 179         SecondLevelAliasScopeMap.lookup(BasePtrSCEV);
 180     SecondLevelAliasScopeMap[BasePtrSCEV] = MDNode::concatenate(
 181         SecondLevelBasePtrAliasScopeList, MDNode::get(Ctx, Args));
 182     auto OtherAliasScopeList = OtherAliasScopeListMap.lookup(BasePtr);
 183     SecondLevelOtherAliasScopeList = MDNode::concatenate(
 184         OtherAliasScopeList, SecondLevelBasePtrAliasScopeList);
 185     SecondLevelOtherAliasScopeListMap[PtrSCEV] = SecondLevelOtherAliasScopeList;
 186   }
 187   Inst->setMetadata("alias.scope", SecondLevelAliasScope);
 188   Inst->setMetadata("noalias", SecondLevelOtherAliasScopeList);
 189 }
 190
 191 /// Find the base pointer of an array access.
 192 ///
 193 /// This should be equivalent to ScalarEvolution::getPointerBase, which we
 194 /// cannot use here the IR is still under construction which ScalarEvolution
 195 /// assumes to not be modified.
 196 static Value *findBasePtr(Value *Val) {
 197   while (true) {
 198     if (auto *Gep = dyn_cast<GEPOperator>(Val)) {
 199       Val = Gep->getPointerOperand();
 200       continue;
 201     }
 202     if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {
 203       Val = Cast->getOperand(0);
 204       continue;
 205     }
 206
 207     break;
 208   }
 209
 210   return Val;
 211 }
 212
 213 void ScopAnnotator::annotate(Instruction *Inst) {
 214   if (!Inst->mayReadOrWriteMemory())
 215     return;
 216
 217   if (!ParallelLoops.empty())
 218     Inst->setMetadata("llvm.mem.parallel_loop_access", ParallelLoops.back());
 219
 220   // TODO: Use the ScopArrayInfo once available here.
 221   if (!AliasScopeDomain)
 222     return;
 223
 224   // Do not apply annotations on memory operations that take more than one
 225   // pointer. It would be ambiguous to which pointer the annotation applies.
 226   // FIXME: How can we specify annotations for all pointer arguments?
 227   if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))
 228     return;
 229
 230   auto *Ptr = getMemAccInstPointerOperand(Inst);
 231   if (!Ptr)
 232     return;
 233
 234   Value *BasePtr = findBasePtr(Ptr);
 235   if (!BasePtr)
 236     return;
 237
 238   auto AliasScope = AliasScopeMap.lookup(BasePtr);
 239
 240   if (!AliasScope) {
 241     BasePtr = AlternativeAliasBases.lookup(BasePtr);
 242     if (!BasePtr)
 243       return;
 244
 245     AliasScope = AliasScopeMap.lookup(BasePtr);
 246     if (!AliasScope)
 247       return;
 248   }
 249
 250   assert(OtherAliasScopeListMap.count(BasePtr) &&
 251          "BasePtr either expected in AliasScopeMap and OtherAlias...Map");
 252   auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];
 253
 254   if (InterIterationAliasFreeBasePtrs.count(BasePtr)) {
 255     annotateSecondLevel(Inst, BasePtr);
 256     return;
 257   }
 258
 259   Inst->setMetadata("alias.scope", AliasScope);
 260   Inst->setMetadata("noalias", OtherAliasScopeList);
 261 }
 262
 263 void ScopAnnotator::addInterIterationAliasFreeBasePtr(llvm::Value *BasePtr) {
 264   if (!BasePtr)
 265     return;
 266
 267   InterIterationAliasFreeBasePtrs.insert(BasePtr);
 268 }