280 lines · 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-exception6//7//===----------------------------------------------------------------------===//8//9// The Polly IRBuilder file contains Polly specific extensions for the IRBuilder10// 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 20using namespace llvm;21using namespace polly;22 23static 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.32static 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 49ScopAnnotator::ScopAnnotator() : SE(nullptr), AliasScopeDomain(nullptr) {50 // Push an empty staging BandAttr.51 LoopAttrEnv.emplace_back();52}53 54ScopAnnotator::~ScopAnnotator() {55 assert(LoopAttrEnv.size() == 1 && "Loop stack imbalance");56 assert(!getStagingAttrEnv() && "Forgot to clear staging attr env");57}58 59void 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 should69 // 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 arrays76 // involved. In case of too many arrays, skip the construction of alias77 // 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 104void 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 117void 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 131static void addVectorizeMetadata(LLVMContext &Ctx,132 SmallVector<Metadata *, 3> *Args,133 bool EnableLoopVectorizer) {134 MDString *PropName = MDString::get(Ctx, "llvm.loop.vectorize.enable");135 ConstantInt *Value =136 ConstantInt::get(Type::getInt1Ty(Ctx), EnableLoopVectorizer);137 ValueAsMetadata *PropValue = ValueAsMetadata::get(Value);138 Args->push_back(MDNode::get(Ctx, {PropName, PropValue}));139}140 141void addParallelMetadata(LLVMContext &Ctx, SmallVector<Metadata *, 3> *Args,142 llvm::SmallVector<llvm::MDNode *, 8> ParallelLoops) {143 MDString *PropName = MDString::get(Ctx, "llvm.loop.parallel_accesses");144 MDNode *AccGroup = ParallelLoops.back();145 Args->push_back(MDNode::get(Ctx, {PropName, AccGroup}));146}147 148void ScopAnnotator::annotateLoopLatch(149 BranchInst *B, bool IsParallel,150 std::optional<bool> EnableVectorizeMetadata) const {151 LLVMContext &Ctx = SE->getContext();152 SmallVector<Metadata *, 3> Args;153 154 // For the LoopID self-reference.155 Args.push_back(nullptr);156 157 // Add the user-defined loop properties to the annotation, if any. Any158 // additional properties are appended.159 // FIXME: What to do if these conflict?160 MDNode *MData = nullptr;161 if (BandAttr *AttrEnv = getActiveAttrEnv()) {162 MData = AttrEnv->Metadata;163 if (MData)164 llvm::append_range(Args, drop_begin(MData->operands(), 1));165 }166 if (IsParallel)167 addParallelMetadata(Ctx, &Args, ParallelLoops);168 if (EnableVectorizeMetadata.has_value())169 addVectorizeMetadata(Ctx, &Args, *EnableVectorizeMetadata);170 171 // No metadata to annotate.172 if (!MData && Args.size() <= 1)173 return;174 175 // Reuse the MData node if possible, this will avoid having to create another176 // one that cannot be merged because LoopIDs are 'distinct'. However, we have177 // to create a new one if we add properties.178 if (!MData || Args.size() > MData->getNumOperands()) {179 MData = MDNode::getDistinct(Ctx, Args);180 MData->replaceOperandWith(0, MData);181 }182 B->setMetadata(LLVMContext::MD_loop, MData);183}184 185/// Get the pointer operand186///187/// @param Inst The instruction to be analyzed.188/// @return the pointer operand in case @p Inst is a memory access189/// instruction and nullptr otherwise.190static llvm::Value *getMemAccInstPointerOperand(Instruction *Inst) {191 auto MemInst = MemAccInst::dyn_cast(Inst);192 if (!MemInst)193 return nullptr;194 195 return MemInst.getPointerOperand();196}197 198/// Find the base pointer of an array access.199///200/// This should be equivalent to ScalarEvolution::getPointerBase, which we201/// cannot use here the IR is still under construction which ScalarEvolution202/// assumes to not be modified.203static Value *findBasePtr(Value *Val) {204 while (true) {205 if (auto *Gep = dyn_cast<GEPOperator>(Val)) {206 Val = Gep->getPointerOperand();207 continue;208 }209 if (auto *Cast = dyn_cast<BitCastOperator>(Val)) {210 Val = Cast->getOperand(0);211 continue;212 }213 214 break;215 }216 217 return Val;218}219 220void ScopAnnotator::annotate(Instruction *Inst) {221 if (!Inst->mayReadOrWriteMemory())222 return;223 224 switch (ParallelLoops.size()) {225 case 0:226 // Not parallel to anything: no access group needed.227 break;228 case 1:229 // Single parallel loop: use directly.230 Inst->setMetadata(LLVMContext::MD_access_group,231 cast<MDNode>(ParallelLoops.front()));232 break;233 default:234 // Parallel to multiple loops: refer to list of access groups.235 Inst->setMetadata(LLVMContext::MD_access_group,236 MDNode::get(SE->getContext(),237 ArrayRef<Metadata *>(238 (Metadata *const *)ParallelLoops.data(),239 ParallelLoops.size())));240 break;241 }242 243 // TODO: Use the ScopArrayInfo once available here.244 if (!AliasScopeDomain)245 return;246 247 // Do not apply annotations on memory operations that take more than one248 // pointer. It would be ambiguous to which pointer the annotation applies.249 // FIXME: How can we specify annotations for all pointer arguments?250 if (isa<CallInst>(Inst) && !isa<MemSetInst>(Inst))251 return;252 253 auto *Ptr = getMemAccInstPointerOperand(Inst);254 if (!Ptr)255 return;256 257 Value *BasePtr = findBasePtr(Ptr);258 if (!BasePtr)259 return;260 261 auto AliasScope = AliasScopeMap.lookup(BasePtr);262 263 if (!AliasScope) {264 BasePtr = AlternativeAliasBases.lookup(BasePtr);265 if (!BasePtr)266 return;267 268 AliasScope = AliasScopeMap.lookup(BasePtr);269 if (!AliasScope)270 return;271 }272 273 assert(OtherAliasScopeListMap.count(BasePtr) &&274 "BasePtr either expected in AliasScopeMap and OtherAlias...Map");275 auto *OtherAliasScopeList = OtherAliasScopeListMap[BasePtr];276 277 Inst->setMetadata("alias.scope", MDNode::get(SE->getContext(), AliasScope));278 Inst->setMetadata("noalias", OtherAliasScopeList);279}280