474 lines · cpp
1//===- MaximalStaticExpansion.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// This pass fully expand the memory accesses of a Scop to get rid of10// dependencies.11//12//===----------------------------------------------------------------------===//13 14#include "polly/MaximalStaticExpansion.h"15#include "polly/DependenceInfo.h"16#include "polly/Options.h"17#include "polly/ScopInfo.h"18#include "polly/Support/ISLTools.h"19#include "llvm/ADT/SmallPtrSet.h"20#include "llvm/ADT/StringRef.h"21#include "llvm/Analysis/OptimizationRemarkEmitter.h"22#include "isl/isl-noexceptions.h"23#include "isl/union_map.h"24#include <cassert>25#include <limits>26#include <string>27#include <vector>28 29using namespace llvm;30using namespace polly;31 32#define DEBUG_TYPE "polly-mse"33 34namespace {35 36static cl::opt<bool>37 PollyPrintMSE("polly-print-mse",38 cl::desc("Polly - Print Maximal static expansion of SCoP"),39 cl::cat(PollyCategory));40 41#ifndef NDEBUG42/// Whether a dimension of a set is bounded (lower and upper) by a constant,43/// i.e. there are two constants Min and Max, such that every value x of the44/// chosen dimensions is Min <= x <= Max.45static bool isDimBoundedByConstant(isl::set Set, unsigned dim) {46 auto ParamDims = unsignedFromIslSize(Set.dim(isl::dim::param));47 Set = Set.project_out(isl::dim::param, 0, ParamDims);48 Set = Set.project_out(isl::dim::set, 0, dim);49 auto SetDims = unsignedFromIslSize(Set.tuple_dim());50 assert(SetDims >= 1);51 Set = Set.project_out(isl::dim::set, 1, SetDims - 1);52 return bool(Set.is_bounded());53}54#endif55 56class MaximalStaticExpansionImpl {57 OptimizationRemarkEmitter &ORE;58 Scop &S;59 isl::union_map &Dependences;60 61 /// Emit remark62 void emitRemark(StringRef Msg, Instruction *Inst) {63 ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "ExpansionRejection", Inst)64 << Msg);65 }66 67 /// Filter the dependences to have only one related to current memory access.68 ///69 /// @param S The SCop in which the memory access appears in.70 /// @param MapDependences The dependences to filter.71 /// @param MA The memory access that need to be expanded.72 isl::union_map filterDependences(const isl::union_map &Dependences,73 MemoryAccess *MA) {74 auto SAI = MA->getLatestScopArrayInfo();75 76 auto AccessDomainSet = MA->getAccessRelation().domain();77 auto AccessDomainId = AccessDomainSet.get_tuple_id();78 79 isl::union_map MapDependences = isl::union_map::empty(S.getIslCtx());80 81 for (isl::map Map : Dependences.get_map_list()) {82 // Filter out Statement to Statement dependences.83 if (!Map.can_curry())84 continue;85 86 // Intersect with the relevant SAI.87 auto TmpMapDomainId =88 Map.get_space().domain().unwrap().range().get_tuple_id(isl::dim::set);89 90 ScopArrayInfo *UserSAI =91 static_cast<ScopArrayInfo *>(TmpMapDomainId.get_user());92 93 if (SAI != UserSAI)94 continue;95 96 // Get the correct S1[] -> S2[] dependence.97 auto NewMap = Map.factor_domain();98 auto NewMapDomainId = NewMap.domain().get_tuple_id();99 100 if (AccessDomainId.get() != NewMapDomainId.get())101 continue;102 103 // Add the corresponding map to MapDependences.104 MapDependences = MapDependences.unite(NewMap);105 }106 107 return MapDependences;108 }109 110 /// Return true if the SAI in parameter is expandable.111 ///112 /// @param SAI the SAI that need to be checked.113 /// @param Writes A set that will contains all the write accesses.114 /// @param Reads A set that will contains all the read accesses.115 /// @param S The SCop in which the SAI is in.116 /// @param Dependences The RAW dependences of the SCop.117 bool isExpandable(const ScopArrayInfo *SAI,118 SmallPtrSetImpl<MemoryAccess *> &Writes,119 SmallPtrSetImpl<MemoryAccess *> &Reads, Scop &S) {120 if (SAI->isValueKind()) {121 Writes.insert(S.getValueDef(SAI));122 Reads.insert_range(S.getValueUses(SAI));123 return true;124 } else if (SAI->isPHIKind()) {125 auto Read = S.getPHIRead(SAI);126 127 auto StmtDomain = isl::union_set(Read->getStatement()->getDomain());128 129 auto Writes = S.getPHIIncomings(SAI);130 131 // Get the domain where all the writes are writing to.132 auto WriteDomain = isl::union_set::empty(S.getIslCtx());133 134 for (auto Write : Writes) {135 auto MapDeps = filterDependences(Dependences, Write);136 for (isl::map Map : MapDeps.get_map_list())137 WriteDomain = WriteDomain.unite(Map.range());138 }139 140 // For now, read from original scalar is not possible.141 if (!StmtDomain.is_equal(WriteDomain)) {142 emitRemark(SAI->getName() + " read from its original value.",143 Read->getAccessInstruction());144 return false;145 }146 147 return true;148 } else if (SAI->isExitPHIKind()) {149 // For now, we are not able to expand ExitPhi.150 emitRemark(SAI->getName() + " is a ExitPhi node.",151 &*S.getEnteringBlock()->getFirstNonPHIIt());152 return false;153 }154 155 int NumberWrites = 0;156 for (ScopStmt &Stmt : S) {157 auto StmtReads = isl::union_map::empty(S.getIslCtx());158 auto StmtWrites = isl::union_map::empty(S.getIslCtx());159 160 for (MemoryAccess *MA : Stmt) {161 // Check if the current MemoryAccess involved the current SAI.162 if (SAI != MA->getLatestScopArrayInfo())163 continue;164 165 // For now, we are not able to expand array where read come after write166 // (to the same location) in a same statement.167 auto AccRel = isl::union_map(MA->getAccessRelation());168 if (MA->isRead()) {169 // Reject load after store to same location.170 if (!StmtWrites.is_disjoint(AccRel)) {171 emitRemark(SAI->getName() + " has read after write to the same "172 "element in same statement. The "173 "dependences found during analysis may "174 "be wrong because Polly is not able to "175 "handle such case for now.",176 MA->getAccessInstruction());177 return false;178 }179 180 StmtReads = StmtReads.unite(AccRel);181 } else {182 StmtWrites = StmtWrites.unite(AccRel);183 }184 185 // For now, we are not able to expand MayWrite.186 if (MA->isMayWrite()) {187 emitRemark(SAI->getName() + " has a maywrite access.",188 MA->getAccessInstruction());189 return false;190 }191 192 // For now, we are not able to expand SAI with more than one write.193 if (MA->isMustWrite()) {194 Writes.insert(MA);195 NumberWrites++;196 if (NumberWrites > 1) {197 emitRemark(SAI->getName() + " has more than 1 write access.",198 MA->getAccessInstruction());199 return false;200 }201 }202 203 // Check if it is possible to expand this read.204 if (MA->isRead()) {205 // Get the domain of the current ScopStmt.206 auto StmtDomain = Stmt.getDomain();207 208 // Get the domain of the future Read access.209 auto ReadDomainSet = MA->getAccessRelation().domain();210 auto ReadDomain = isl::union_set(ReadDomainSet);211 212 // Get the dependences relevant for this MA213 auto MapDependences = filterDependences(Dependences.reverse(), MA);214 unsigned NumberElementMap = isl_union_map_n_map(MapDependences.get());215 216 if (NumberElementMap == 0) {217 emitRemark("The expansion of " + SAI->getName() +218 " would lead to a read from the original array.",219 MA->getAccessInstruction());220 return false;221 }222 223 auto DepsDomain = MapDependences.domain();224 225 // If there are multiple maps in the Deps, we cannot handle this case226 // for now.227 if (NumberElementMap != 1) {228 emitRemark(SAI->getName() +229 " has too many dependences to be handle for now.",230 MA->getAccessInstruction());231 return false;232 }233 234 auto DepsDomainSet = isl::set(DepsDomain);235 236 // For now, read from the original array is not possible.237 if (!StmtDomain.is_subset(DepsDomainSet)) {238 emitRemark("The expansion of " + SAI->getName() +239 " would lead to a read from the original array.",240 MA->getAccessInstruction());241 return false;242 }243 244 Reads.insert(MA);245 }246 }247 }248 249 // No need to expand SAI with no write.250 if (NumberWrites == 0) {251 emitRemark(SAI->getName() + " has 0 write access.",252 &*S.getEnteringBlock()->getFirstNonPHIIt());253 return false;254 }255 256 return true;257 }258 259 /// Expand the MemoryAccess according to Dependences and already expanded260 /// MemoryAccesses.261 ///262 /// @param The SCop in which the memory access appears in.263 /// @param The memory access that need to be expanded.264 /// @param Dependences The RAW dependences of the SCop.265 /// @param ExpandedSAI The expanded SAI created during write expansion.266 /// @param Reverse if true, the Dependences union_map is reversed before267 /// intersection.268 void mapAccess(SmallPtrSetImpl<MemoryAccess *> &Accesses,269 const isl::union_map &Dependences, ScopArrayInfo *ExpandedSAI,270 bool Reverse) {271 for (auto MA : Accesses) {272 // Get the current AM.273 auto CurrentAccessMap = MA->getAccessRelation();274 275 // Get RAW dependences for the current WA.276 auto DomainSet = MA->getAccessRelation().domain();277 auto Domain = isl::union_set(DomainSet);278 279 // Get the dependences relevant for this MA.280 isl::union_map MapDependences =281 filterDependences(Reverse ? Dependences.reverse() : Dependences, MA);282 283 // If no dependences, no need to modify anything.284 if (MapDependences.is_empty())285 return;286 287 assert(isl_union_map_n_map(MapDependences.get()) == 1 &&288 "There are more than one RAW dependencies in the union map.");289 auto NewAccessMap = isl::map::from_union_map(MapDependences);290 291 auto Id = ExpandedSAI->getBasePtrId();292 293 // Replace the out tuple id with the one of the access array.294 NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, Id);295 296 // Set the new access relation.297 MA->setNewAccessRelation(NewAccessMap);298 }299 }300 301 /// Expand the MemoryAccess according to its domain.302 ///303 /// @param S The SCop in which the memory access appears in.304 /// @param MA The memory access that need to be expanded.305 ScopArrayInfo *expandAccess(MemoryAccess *MA) {306 // Get the current AM.307 auto CurrentAccessMap = MA->getAccessRelation();308 309 unsigned in_dimensions =310 unsignedFromIslSize(CurrentAccessMap.domain_tuple_dim());311 312 // Get domain from the current AM.313 auto Domain = CurrentAccessMap.domain();314 315 // Create a new AM from the domain.316 auto NewAccessMap = isl::map::from_domain(Domain);317 318 // Add dimensions to the new AM according to the current in_dim.319 NewAccessMap = NewAccessMap.add_dims(isl::dim::out, in_dimensions);320 321 // Create the string representing the name of the new SAI.322 // One new SAI for each statement so that each write go to a different323 // memory cell.324 auto CurrentStmtDomain = MA->getStatement()->getDomain();325 auto CurrentStmtName = CurrentStmtDomain.get_tuple_name();326 auto CurrentOutId = CurrentAccessMap.get_tuple_id(isl::dim::out);327 std::string CurrentOutIdString =328 MA->getScopArrayInfo()->getName() + "_" + CurrentStmtName + "_expanded";329 330 // Set the tuple id for the out dimension.331 NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, CurrentOutId);332 333 // Create the size vector.334 std::vector<unsigned> Sizes;335 for (unsigned i = 0; i < in_dimensions; i++) {336 assert(isDimBoundedByConstant(CurrentStmtDomain, i) &&337 "Domain boundary are not constant.");338 auto UpperBound = getConstant(CurrentStmtDomain.dim_max(i), true, false);339 assert(!UpperBound.is_null() && UpperBound.is_pos() &&340 !UpperBound.is_nan() &&341 "The upper bound is not a positive integer.");342 assert(UpperBound.le(isl::val(CurrentAccessMap.ctx(),343 std::numeric_limits<int>::max() - 1)) &&344 "The upper bound overflow a int.");345 Sizes.push_back(UpperBound.get_num_si() + 1);346 }347 348 // Get the ElementType of the current SAI.349 auto ElementType = MA->getLatestScopArrayInfo()->getElementType();350 351 // Create (or get if already existing) the new expanded SAI.352 auto ExpandedSAI =353 S.createScopArrayInfo(ElementType, CurrentOutIdString, Sizes);354 ExpandedSAI->setIsOnHeap(true);355 356 // Get the out Id of the expanded Array.357 auto NewOutId = ExpandedSAI->getBasePtrId();358 359 // Set the out id of the new AM to the new SAI id.360 NewAccessMap = NewAccessMap.set_tuple_id(isl::dim::out, NewOutId);361 362 // Add constraints to linked output with input id.363 auto SpaceMap = NewAccessMap.get_space();364 auto ConstraintBasicMap = isl::basic_map::equal(365 SpaceMap, unsignedFromIslSize(SpaceMap.dim(isl::dim::in)));366 NewAccessMap = isl::map(ConstraintBasicMap);367 368 // Set the new access relation map.369 MA->setNewAccessRelation(NewAccessMap);370 371 return ExpandedSAI;372 }373 374 /// Expand PHI memory accesses.375 ///376 /// @param The SCop in which the memory access appears in.377 /// @param The ScopArrayInfo representing the PHI accesses to expand.378 /// @param Dependences The RAW dependences of the SCop.379 void expandPhi(Scop &S, const ScopArrayInfo *SAI,380 const isl::union_map &Dependences) {381 SmallPtrSet<MemoryAccess *, 4> Writes(llvm::from_range,382 S.getPHIIncomings(SAI));383 auto Read = S.getPHIRead(SAI);384 auto ExpandedSAI = expandAccess(Read);385 386 mapAccess(Writes, Dependences, ExpandedSAI, false);387 }388 389public:390 MaximalStaticExpansionImpl(Scop &S, isl::union_map &Dependences,391 OptimizationRemarkEmitter &ORE)392 : ORE(ORE), S(S), Dependences(Dependences) {}393 394 /// Expand the accesses of the SCoP395 ///396 /// @param S The SCoP that must be expanded397 /// @param D The dependencies information of SCoP398 void expand() {399 SmallVector<ScopArrayInfo *, 4> CurrentSAI(S.arrays().begin(),400 S.arrays().end());401 for (auto SAI : CurrentSAI) {402 SmallPtrSet<MemoryAccess *, 4> AllWrites;403 SmallPtrSet<MemoryAccess *, 4> AllReads;404 if (!isExpandable(SAI, AllWrites, AllReads, S))405 continue;406 407 if (SAI->isValueKind() || SAI->isArrayKind()) {408 assert(AllWrites.size() == 1 || SAI->isValueKind());409 410 auto TheWrite = *(AllWrites.begin());411 ScopArrayInfo *ExpandedArray = expandAccess(TheWrite);412 413 mapAccess(AllReads, Dependences, ExpandedArray, true);414 } else if (SAI->isPHIKind()) {415 expandPhi(S, SAI, Dependences);416 }417 }418 }419 420 /// Dump the internal information about a performed MSE to @p OS.421 void print(llvm::raw_ostream &OS) {422 OS << "After arrays {\n";423 424 for (auto &Array : S.arrays())425 Array->print(OS);426 427 OS << "}\n";428 429 OS << "After accesses {\n";430 for (auto &Stmt : S) {431 OS.indent(4) << Stmt.getBaseName() << "{\n";432 for (auto *MA : Stmt)433 MA->print(OS);434 OS.indent(4) << "}\n";435 }436 OS << "}\n";437 }438};439 440static std::unique_ptr<MaximalStaticExpansionImpl>441runMaximalStaticExpansionImpl(Scop &S, OptimizationRemarkEmitter &ORE,442 const Dependences &D) {443 auto Dependences = D.getDependences(Dependences::TYPE_RAW);444 445 std::unique_ptr<MaximalStaticExpansionImpl> Impl =446 std::make_unique<MaximalStaticExpansionImpl>(S, Dependences, ORE);447 448 Impl->expand();449 return Impl;450}451} // namespace452 453void polly::runMaximalStaticExpansion(Scop &S, DependenceAnalysis::Result &DI) {454 OptimizationRemarkEmitter ORE(&S.getFunction());455 456 auto &D = DI.getDependences(Dependences::AL_Reference);457 458 std::unique_ptr<MaximalStaticExpansionImpl> Impl =459 runMaximalStaticExpansionImpl(S, ORE, D);460 461 if (PollyPrintMSE) {462 outs()463 << "Printing analysis 'Polly - Maximal static expansion of SCoP' for "464 "region: '"465 << S.getName() << "' in function '" << S.getFunction().getName()466 << "':\n";467 468 if (Impl) {469 outs() << "MSE result:\n";470 Impl->print(llvm::outs());471 }472 }473}474