brintos / llvm-project-archived public Read only

1//===- ScopInfo.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// Create a polyhedral description for a static control flow region.10//11// The pass creates a polyhedral description of the Scops detected by the Scop12// detection derived from their LLVM-IR code.13//14// This representation is shared among several tools in the polyhedral15// community, which are e.g. Cloog, Pluto, Loopo, Graphite.16//17//===----------------------------------------------------------------------===//18 19#include "polly/ScopInfo.h"20#include "polly/Options.h"21#include "polly/ScopBuilder.h"22#include "polly/ScopDetection.h"23#include "polly/Support/GICHelper.h"24#include "polly/Support/ISLOStream.h"25#include "polly/Support/ISLTools.h"26#include "polly/Support/SCEVAffinator.h"27#include "polly/Support/SCEVValidator.h"28#include "polly/Support/ScopHelper.h"29#include "llvm/ADT/APInt.h"30#include "llvm/ADT/ArrayRef.h"31#include "llvm/ADT/PostOrderIterator.h"32#include "llvm/ADT/Sequence.h"33#include "llvm/ADT/SmallPtrSet.h"34#include "llvm/ADT/SmallSet.h"35#include "llvm/ADT/Statistic.h"36#include "llvm/ADT/StringExtras.h"37#include "llvm/Analysis/AliasAnalysis.h"38#include "llvm/Analysis/AssumptionCache.h"39#include "llvm/Analysis/Loads.h"40#include "llvm/Analysis/LoopInfo.h"41#include "llvm/Analysis/OptimizationRemarkEmitter.h"42#include "llvm/Analysis/RegionInfo.h"43#include "llvm/Analysis/RegionIterator.h"44#include "llvm/Analysis/ScalarEvolution.h"45#include "llvm/Analysis/ScalarEvolutionExpressions.h"46#include "llvm/IR/BasicBlock.h"47#include "llvm/IR/ConstantRange.h"48#include "llvm/IR/DataLayout.h"49#include "llvm/IR/DebugLoc.h"50#include "llvm/IR/Dominators.h"51#include "llvm/IR/Function.h"52#include "llvm/IR/InstrTypes.h"53#include "llvm/IR/Instruction.h"54#include "llvm/IR/Instructions.h"55#include "llvm/IR/Module.h"56#include "llvm/IR/Type.h"57#include "llvm/IR/Value.h"58#include "llvm/Support/Compiler.h"59#include "llvm/Support/Debug.h"60#include "llvm/Support/ErrorHandling.h"61#include "llvm/Support/raw_ostream.h"62#include "isl/aff.h"63#include "isl/local_space.h"64#include "isl/map.h"65#include "isl/options.h"66#include "isl/set.h"67#include <cassert>68#include <numeric>69 70using namespace llvm;71using namespace polly;72 73#include "polly/Support/PollyDebug.h"74#define DEBUG_TYPE "polly-scops"75 76STATISTIC(AssumptionsAliasing, "Number of aliasing assumptions taken.");77STATISTIC(AssumptionsInbounds, "Number of inbounds assumptions taken.");78STATISTIC(AssumptionsWrapping, "Number of wrapping assumptions taken.");79STATISTIC(AssumptionsUnsigned, "Number of unsigned assumptions taken.");80STATISTIC(AssumptionsComplexity, "Number of too complex SCoPs.");81STATISTIC(AssumptionsUnprofitable, "Number of unprofitable SCoPs.");82STATISTIC(AssumptionsErrorBlock, "Number of error block assumptions taken.");83STATISTIC(AssumptionsInfiniteLoop, "Number of bounded loop assumptions taken.");84STATISTIC(AssumptionsInvariantLoad,85          "Number of invariant loads assumptions taken.");86STATISTIC(AssumptionsDelinearization,87          "Number of delinearization assumptions taken.");88 89STATISTIC(NumScops, "Number of feasible SCoPs after ScopInfo");90STATISTIC(NumLoopsInScop, "Number of loops in scops");91STATISTIC(NumBoxedLoops, "Number of boxed loops in SCoPs after ScopInfo");92STATISTIC(NumAffineLoops, "Number of affine loops in SCoPs after ScopInfo");93 94STATISTIC(NumScopsDepthZero, "Number of scops with maximal loop depth 0");95STATISTIC(NumScopsDepthOne, "Number of scops with maximal loop depth 1");96STATISTIC(NumScopsDepthTwo, "Number of scops with maximal loop depth 2");97STATISTIC(NumScopsDepthThree, "Number of scops with maximal loop depth 3");98STATISTIC(NumScopsDepthFour, "Number of scops with maximal loop depth 4");99STATISTIC(NumScopsDepthFive, "Number of scops with maximal loop depth 5");100STATISTIC(NumScopsDepthLarger,101          "Number of scops with maximal loop depth 6 and larger");102STATISTIC(MaxNumLoopsInScop, "Maximal number of loops in scops");103 104STATISTIC(NumValueWrites, "Number of scalar value writes after ScopInfo");105STATISTIC(106    NumValueWritesInLoops,107    "Number of scalar value writes nested in affine loops after ScopInfo");108STATISTIC(NumPHIWrites, "Number of scalar phi writes after ScopInfo");109STATISTIC(NumPHIWritesInLoops,110          "Number of scalar phi writes nested in affine loops after ScopInfo");111STATISTIC(NumSingletonWrites, "Number of singleton writes after ScopInfo");112STATISTIC(NumSingletonWritesInLoops,113          "Number of singleton writes nested in affine loops after ScopInfo");114 115unsigned const polly::MaxDisjunctsInDomain = 20;116 117// The number of disjunct in the context after which we stop to add more118// disjuncts. This parameter is there to avoid exponential growth in the119// number of disjunct when adding non-convex sets to the context.120static int const MaxDisjunctsInContext = 4;121 122// Be a bit more generous for the defined behavior context which is used less123// often.124static int const MaxDisjunktsInDefinedBehaviourContext = 8;125 126static cl::opt<bool> PollyRemarksMinimal(127    "polly-remarks-minimal",128    cl::desc("Do not emit remarks about assumptions that are known"),129    cl::Hidden, cl::cat(PollyCategory));130 131static cl::opt<bool>132    IslOnErrorAbort("polly-on-isl-error-abort",133                    cl::desc("Abort if an isl error is encountered"),134                    cl::init(true), cl::cat(PollyCategory));135 136static cl::opt<bool> PollyPreciseInbounds(137    "polly-precise-inbounds",138    cl::desc("Take more precise inbounds assumptions (do not scale well)"),139    cl::Hidden, cl::init(false), cl::cat(PollyCategory));140 141static cl::opt<bool> PollyIgnoreParamBounds(142    "polly-ignore-parameter-bounds",143    cl::desc(144        "Do not add parameter bounds and do no gist simplify sets accordingly"),145    cl::Hidden, cl::init(false), cl::cat(PollyCategory));146 147static cl::opt<bool> PollyPreciseFoldAccesses(148    "polly-precise-fold-accesses",149    cl::desc("Fold memory accesses to model more possible delinearizations "150             "(does not scale well)"),151    cl::Hidden, cl::init(false), cl::cat(PollyCategory));152 153bool polly::UseInstructionNames;154 155static cl::opt<bool, true> XUseInstructionNames(156    "polly-use-llvm-names",157    cl::desc("Use LLVM-IR names when deriving statement names"),158    cl::location(UseInstructionNames), cl::Hidden, cl::cat(PollyCategory));159 160static cl::opt<bool> PollyPrintInstructions(161    "polly-print-instructions", cl::desc("Output instructions per ScopStmt"),162    cl::Hidden, cl::Optional, cl::init(false), cl::cat(PollyCategory));163 164static cl::list<std::string> IslArgs("polly-isl-arg",165                                     cl::value_desc("argument"),166                                     cl::desc("Option passed to ISL"),167                                     cl::cat(PollyCategory));168 169//===----------------------------------------------------------------------===//170 171static isl::set addRangeBoundsToSet(isl::set S, const ConstantRange &Range,172                                    int dim, isl::dim type) {173  isl::val V;174  isl::ctx Ctx = S.ctx();175 176  // The upper and lower bound for a parameter value is derived either from177  // the data type of the parameter or from the - possibly more restrictive -178  // range metadata.179  V = valFromAPInt(Ctx.get(), Range.getSignedMin(), true);180  S = S.lower_bound_val(type, dim, V);181  V = valFromAPInt(Ctx.get(), Range.getSignedMax(), true);182  S = S.upper_bound_val(type, dim, V);183 184  if (Range.isFullSet())185    return S;186 187  if (S.n_basic_set().release() > MaxDisjunctsInContext)188    return S;189 190  // In case of signed wrapping, we can refine the set of valid values by191  // excluding the part not covered by the wrapping range.192  if (Range.isSignWrappedSet()) {193    V = valFromAPInt(Ctx.get(), Range.getLower(), true);194    isl::set SLB = S.lower_bound_val(type, dim, V);195 196    V = valFromAPInt(Ctx.get(), Range.getUpper(), true);197    V = V.sub(1);198    isl::set SUB = S.upper_bound_val(type, dim, V);199    S = SLB.unite(SUB);200  }201 202  return S;203}204 205static const ScopArrayInfo *identifyBasePtrOriginSAI(Scop *S, Value *BasePtr) {206  LoadInst *BasePtrLI = dyn_cast<LoadInst>(BasePtr);207  if (!BasePtrLI)208    return nullptr;209 210  if (!S->contains(BasePtrLI))211    return nullptr;212 213  ScalarEvolution &SE = *S->getSE();214 215  const SCEV *OriginBaseSCEV =216      SE.getPointerBase(SE.getSCEV(BasePtrLI->getPointerOperand()));217  if (!OriginBaseSCEV)218    return nullptr;219 220  auto *OriginBaseSCEVUnknown = dyn_cast<SCEVUnknown>(OriginBaseSCEV);221  if (!OriginBaseSCEVUnknown)222    return nullptr;223 224  return S->getScopArrayInfo(OriginBaseSCEVUnknown->getValue(),225                             MemoryKind::Array);226}227 228ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl::ctx Ctx,229                             ArrayRef<const SCEV *> Sizes, MemoryKind Kind,230                             const DataLayout &DL, Scop *S,231                             const char *BaseName)232    : BasePtr(BasePtr), ElementType(ElementType), Kind(Kind), DL(DL), S(*S) {233  std::string BasePtrName =234      BaseName ? BaseName235               : getIslCompatibleName("MemRef", BasePtr, S->getNextArrayIdx(),236                                      Kind == MemoryKind::PHI ? "__phi" : "",237                                      UseInstructionNames);238  Id = isl::id::alloc(Ctx, BasePtrName, this);239 240  updateSizes(Sizes);241 242  if (!BasePtr || Kind != MemoryKind::Array) {243    BasePtrOriginSAI = nullptr;244    return;245  }246 247  BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr);248  if (BasePtrOriginSAI)249    const_cast<ScopArrayInfo *>(BasePtrOriginSAI)->addDerivedSAI(this);250}251 252ScopArrayInfo::~ScopArrayInfo() = default;253 254isl::space ScopArrayInfo::getSpace() const {255  auto Space = isl::space(Id.ctx(), 0, getNumberOfDimensions());256  Space = Space.set_tuple_id(isl::dim::set, Id);257  return Space;258}259 260bool ScopArrayInfo::isReadOnly() {261  isl::union_set WriteSet = S.getWrites().range();262  isl::space Space = getSpace();263  WriteSet = WriteSet.extract_set(Space);264 265  return bool(WriteSet.is_empty());266}267 268bool ScopArrayInfo::isCompatibleWith(const ScopArrayInfo *Array) const {269  if (Array->getElementType() != getElementType())270    return false;271 272  if (Array->getNumberOfDimensions() != getNumberOfDimensions())273    return false;274 275  for (unsigned i = 0; i < getNumberOfDimensions(); i++)276    if (Array->getDimensionSize(i) != getDimensionSize(i))277      return false;278 279  return true;280}281 282void ScopArrayInfo::updateElementType(Type *NewElementType) {283  if (NewElementType == ElementType)284    return;285 286  auto OldElementSize = DL.getTypeAllocSizeInBits(ElementType);287  auto NewElementSize = DL.getTypeAllocSizeInBits(NewElementType);288 289  if (NewElementSize == OldElementSize || NewElementSize == 0)290    return;291 292  if (NewElementSize % OldElementSize == 0 && NewElementSize < OldElementSize) {293    ElementType = NewElementType;294  } else {295    auto GCD = std::gcd((uint64_t)NewElementSize, (uint64_t)OldElementSize);296    ElementType = IntegerType::get(ElementType->getContext(), GCD);297  }298}299 300bool ScopArrayInfo::updateSizes(ArrayRef<const SCEV *> NewSizes,301                                bool CheckConsistency) {302  int SharedDims = std::min(NewSizes.size(), DimensionSizes.size());303  int ExtraDimsNew = NewSizes.size() - SharedDims;304  int ExtraDimsOld = DimensionSizes.size() - SharedDims;305 306  if (CheckConsistency) {307    for (int i = 0; i < SharedDims; i++) {308      auto *NewSize = NewSizes[i + ExtraDimsNew];309      auto *KnownSize = DimensionSizes[i + ExtraDimsOld];310      if (NewSize && KnownSize && NewSize != KnownSize)311        return false;312    }313 314    if (DimensionSizes.size() >= NewSizes.size())315      return true;316  }317 318  DimensionSizes.clear();319  DimensionSizes.insert(DimensionSizes.begin(), NewSizes.begin(),320                        NewSizes.end());321  DimensionSizesPw.clear();322  for (const SCEV *Expr : DimensionSizes) {323    if (!Expr) {324      DimensionSizesPw.push_back(isl::pw_aff());325      continue;326    }327    isl::pw_aff Size = S.getPwAffOnly(Expr);328    DimensionSizesPw.push_back(Size);329  }330  return true;331}332 333std::string ScopArrayInfo::getName() const { return Id.get_name(); }334 335int ScopArrayInfo::getElemSizeInBytes() const {336  return DL.getTypeAllocSize(ElementType);337}338 339isl::id ScopArrayInfo::getBasePtrId() const { return Id; }340 341#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)342LLVM_DUMP_METHOD void ScopArrayInfo::dump() const { print(errs()); }343#endif344 345void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const {346  OS.indent(8) << *getElementType() << " " << getName();347  unsigned u = 0;348 349  if (getNumberOfDimensions() > 0 && !getDimensionSize(0)) {350    OS << "[*]";351    u++;352  }353  for (; u < getNumberOfDimensions(); u++) {354    OS << "[";355 356    if (SizeAsPwAff) {357      isl::pw_aff Size = getDimensionSizePw(u);358      OS << " " << Size << " ";359    } else {360      OS << *getDimensionSize(u);361    }362 363    OS << "]";364  }365 366  OS << ";";367 368  if (BasePtrOriginSAI)369    OS << " [BasePtrOrigin: " << BasePtrOriginSAI->getName() << "]";370 371  OS << " // Element size " << getElemSizeInBytes() << "\n";372}373 374const ScopArrayInfo *375ScopArrayInfo::getFromAccessFunction(isl::pw_multi_aff PMA) {376  isl::id Id = PMA.get_tuple_id(isl::dim::out);377  assert(!Id.is_null() && "Output dimension didn't have an ID");378  return getFromId(Id);379}380 381const ScopArrayInfo *ScopArrayInfo::getFromId(isl::id Id) {382  void *User = Id.get_user();383  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);384  return SAI;385}386 387void MemoryAccess::wrapConstantDimensions() {388  auto *SAI = getScopArrayInfo();389  isl::space ArraySpace = SAI->getSpace();390  isl::ctx Ctx = ArraySpace.ctx();391  unsigned DimsArray = SAI->getNumberOfDimensions();392 393  isl::multi_aff DivModAff = isl::multi_aff::identity(394      ArraySpace.map_from_domain_and_range(ArraySpace));395  isl::local_space LArraySpace = isl::local_space(ArraySpace);396 397  // Begin with last dimension, to iteratively carry into higher dimensions.398  for (int i = DimsArray - 1; i > 0; i--) {399    auto *DimSize = SAI->getDimensionSize(i);400    auto *DimSizeCst = dyn_cast<SCEVConstant>(DimSize);401 402    // This transformation is not applicable to dimensions with dynamic size.403    if (!DimSizeCst)404      continue;405 406    // This transformation is not applicable to dimensions of size zero.407    if (DimSize->isZero())408      continue;409 410    isl::val DimSizeVal =411        valFromAPInt(Ctx.get(), DimSizeCst->getAPInt(), false);412    isl::aff Var = isl::aff::var_on_domain(LArraySpace, isl::dim::set, i);413    isl::aff PrevVar =414        isl::aff::var_on_domain(LArraySpace, isl::dim::set, i - 1);415 416    // Compute: index % size417    // Modulo must apply in the divide of the previous iteration, if any.418    isl::aff Modulo = Var.mod(DimSizeVal);419    Modulo = Modulo.pullback(DivModAff);420 421    // Compute: floor(index / size)422    isl::aff Divide = Var.div(isl::aff(LArraySpace, DimSizeVal));423    Divide = Divide.floor();424    Divide = Divide.add(PrevVar);425    Divide = Divide.pullback(DivModAff);426 427    // Apply Modulo and Divide.428    DivModAff = DivModAff.set_aff(i, Modulo);429    DivModAff = DivModAff.set_aff(i - 1, Divide);430  }431 432  // Apply all modulo/divides on the accesses.433  isl::map Relation = AccessRelation;434  Relation = Relation.apply_range(isl::map::from_multi_aff(DivModAff));435  Relation = Relation.detect_equalities();436  AccessRelation = Relation;437}438 439void MemoryAccess::updateDimensionality() {440  auto *SAI = getScopArrayInfo();441  isl::space ArraySpace = SAI->getSpace();442  isl::space AccessSpace = AccessRelation.get_space().range();443  isl::ctx Ctx = ArraySpace.ctx();444 445  unsigned DimsArray = unsignedFromIslSize(ArraySpace.dim(isl::dim::set));446  unsigned DimsAccess = unsignedFromIslSize(AccessSpace.dim(isl::dim::set));447  assert(DimsArray >= DimsAccess);448  unsigned DimsMissing = DimsArray - DimsAccess;449 450  auto *BB = getStatement()->getEntryBlock();451  auto &DL = BB->getModule()->getDataLayout();452  unsigned ArrayElemSize = SAI->getElemSizeInBytes();453  unsigned ElemBytes = DL.getTypeAllocSize(getElementType());454 455  isl::map Map = isl::map::from_domain_and_range(456      isl::set::universe(AccessSpace), isl::set::universe(ArraySpace));457 458  for (auto i : seq<unsigned>(0, DimsMissing))459    Map = Map.fix_si(isl::dim::out, i, 0);460 461  for (auto i : seq<unsigned>(DimsMissing, DimsArray))462    Map = Map.equate(isl::dim::in, i - DimsMissing, isl::dim::out, i);463 464  AccessRelation = AccessRelation.apply_range(Map);465 466  // For the non delinearized arrays, divide the access function of the last467  // subscript by the size of the elements in the array.468  //469  // A stride one array access in C expressed as A[i] is expressed in470  // LLVM-IR as something like A[i * elementsize]. This hides the fact that471  // two subsequent values of 'i' index two values that are stored next to472  // each other in memory. By this division we make this characteristic473  // obvious again. If the base pointer was accessed with offsets not divisible474  // by the accesses element size, we will have chosen a smaller ArrayElemSize475  // that divides the offsets of all accesses to this base pointer.476  if (DimsAccess == 1) {477    isl::val V = isl::val(Ctx, ArrayElemSize);478    AccessRelation = AccessRelation.floordiv_val(V);479  }480 481  // We currently do this only if we added at least one dimension, which means482  // some dimension's indices have not been specified, an indicator that some483  // index values have been added together.484  // TODO: Investigate general usefulness; Effect on unit tests is to make index485  // expressions more complicated.486  if (DimsMissing)487    wrapConstantDimensions();488 489  if (!isAffine())490    computeBoundsOnAccessRelation(ArrayElemSize);491 492  // Introduce multi-element accesses in case the type loaded by this memory493  // access is larger than the canonical element type of the array.494  //495  // An access ((float *)A)[i] to an array char *A is modeled as496  // {[i] -> A[o] : 4 i <= o <= 4 i + 3497  if (ElemBytes > ArrayElemSize) {498    assert(ElemBytes % ArrayElemSize == 0 &&499           "Loaded element size should be multiple of canonical element size");500    assert(DimsArray >= 1);501    isl::map Map = isl::map::from_domain_and_range(502        isl::set::universe(ArraySpace), isl::set::universe(ArraySpace));503    for (auto i : seq<unsigned>(0, DimsArray - 1))504      Map = Map.equate(isl::dim::in, i, isl::dim::out, i);505 506    isl::constraint C;507    isl::local_space LS;508 509    LS = isl::local_space(Map.get_space());510    int Num = ElemBytes / getScopArrayInfo()->getElemSizeInBytes();511 512    C = isl::constraint::alloc_inequality(LS);513    C = C.set_constant_val(isl::val(Ctx, Num - 1));514    C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, 1);515    C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, -1);516    Map = Map.add_constraint(C);517 518    C = isl::constraint::alloc_inequality(LS);519    C = C.set_coefficient_si(isl::dim::in, DimsArray - 1, -1);520    C = C.set_coefficient_si(isl::dim::out, DimsArray - 1, 1);521    C = C.set_constant_val(isl::val(Ctx, 0));522    Map = Map.add_constraint(C);523    AccessRelation = AccessRelation.apply_range(Map);524  }525}526 527std::string528MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) {529  switch (RT) {530  case MemoryAccess::RT_NONE:531    llvm_unreachable("Requested a reduction operator string for a memory "532                     "access which isn't a reduction");533  case MemoryAccess::RT_BOTTOM:534    llvm_unreachable("Requested a reduction operator string for a internal "535                     "reduction type!");536  case MemoryAccess::RT_ADD:537    return "+";538  case MemoryAccess::RT_MUL:539    return "*";540  case MemoryAccess::RT_BOR:541    return "|";542  case MemoryAccess::RT_BXOR:543    return "^";544  case MemoryAccess::RT_BAND:545    return "&";546  }547  llvm_unreachable("Unknown reduction type");548}549 550const ScopArrayInfo *MemoryAccess::getOriginalScopArrayInfo() const {551  isl::id ArrayId = getArrayId();552  void *User = ArrayId.get_user();553  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);554  return SAI;555}556 557const ScopArrayInfo *MemoryAccess::getLatestScopArrayInfo() const {558  isl::id ArrayId = getLatestArrayId();559  void *User = ArrayId.get_user();560  const ScopArrayInfo *SAI = static_cast<ScopArrayInfo *>(User);561  return SAI;562}563 564isl::id MemoryAccess::getOriginalArrayId() const {565  return AccessRelation.get_tuple_id(isl::dim::out);566}567 568isl::id MemoryAccess::getLatestArrayId() const {569  if (!hasNewAccessRelation())570    return getOriginalArrayId();571  return NewAccessRelation.get_tuple_id(isl::dim::out);572}573 574isl::map MemoryAccess::getAddressFunction() const {575  return getAccessRelation().lexmin();576}577 578isl::pw_multi_aff579MemoryAccess::applyScheduleToAccessRelation(isl::union_map USchedule) const {580  isl::map Schedule, ScheduledAccRel;581  isl::union_set UDomain;582 583  UDomain = getStatement()->getDomain();584  USchedule = USchedule.intersect_domain(UDomain);585  Schedule = isl::map::from_union_map(USchedule);586  ScheduledAccRel = getAddressFunction().apply_domain(Schedule);587  return isl::pw_multi_aff::from_map(ScheduledAccRel);588}589 590isl::map MemoryAccess::getOriginalAccessRelation() const {591  return AccessRelation;592}593 594std::string MemoryAccess::getOriginalAccessRelationStr() const {595  return stringFromIslObj(AccessRelation);596}597 598isl::space MemoryAccess::getOriginalAccessRelationSpace() const {599  return AccessRelation.get_space();600}601 602isl::map MemoryAccess::getNewAccessRelation() const {603  return NewAccessRelation;604}605 606std::string MemoryAccess::getNewAccessRelationStr() const {607  return stringFromIslObj(NewAccessRelation);608}609 610std::string MemoryAccess::getAccessRelationStr() const {611  return stringFromIslObj(getAccessRelation());612}613 614isl::basic_map MemoryAccess::createBasicAccessMap(ScopStmt *Statement) {615  isl::space Space = isl::space(Statement->getIslCtx(), 0, 1);616  Space = Space.align_params(Statement->getDomainSpace());617 618  return isl::basic_map::from_domain_and_range(619      isl::basic_set::universe(Statement->getDomainSpace()),620      isl::basic_set::universe(Space));621}622 623// Formalize no out-of-bound access assumption624//625// When delinearizing array accesses we optimistically assume that the626// delinearized accesses do not access out of bound locations (the subscript627// expression of each array evaluates for each statement instance that is628// executed to a value that is larger than zero and strictly smaller than the629// size of the corresponding dimension). The only exception is the outermost630// dimension for which we do not need to assume any upper bound.  At this point631// we formalize this assumption to ensure that at code generation time the632// relevant run-time checks can be generated.633//634// To find the set of constraints necessary to avoid out of bound accesses, we635// first build the set of data locations that are not within array bounds. We636// then apply the reverse access relation to obtain the set of iterations that637// may contain invalid accesses and reduce this set of iterations to the ones638// that are actually executed by intersecting them with the domain of the639// statement. If we now project out all loop dimensions, we obtain a set of640// parameters that may cause statement instances to be executed that may641// possibly yield out of bound memory accesses. The complement of these642// constraints is the set of constraints that needs to be assumed to ensure such643// statement instances are never executed.644isl::set MemoryAccess::assumeNoOutOfBound() {645  auto *SAI = getScopArrayInfo();646  isl::space Space = getOriginalAccessRelationSpace().range();647  isl::set Outside = isl::set::empty(Space);648  for (int i = 1, Size = Space.dim(isl::dim::set).release(); i < Size; ++i) {649    isl::local_space LS(Space);650    isl::pw_aff Var = isl::pw_aff::var_on_domain(LS, isl::dim::set, i);651    isl::pw_aff Zero = isl::pw_aff(LS);652 653    isl::set DimOutside = Var.lt_set(Zero);654    isl::pw_aff SizeE = SAI->getDimensionSizePw(i);655    SizeE = SizeE.add_dims(isl::dim::in, Space.dim(isl::dim::set).release());656    SizeE = SizeE.set_tuple_id(isl::dim::in, Space.get_tuple_id(isl::dim::set));657    DimOutside = DimOutside.unite(SizeE.le_set(Var));658 659    Outside = Outside.unite(DimOutside);660  }661 662  Outside = Outside.apply(getAccessRelation().reverse());663  Outside = Outside.intersect(Statement->getDomain());664  Outside = Outside.params();665 666  // Remove divs to avoid the construction of overly complicated assumptions.667  // Doing so increases the set of parameter combinations that are assumed to668  // not appear. This is always save, but may make the resulting run-time check669  // bail out more often than strictly necessary.670  Outside = Outside.remove_divs();671  Outside = Outside.complement();672 673  if (!PollyPreciseInbounds)674    Outside = Outside.gist_params(Statement->getDomain().params());675  return Outside;676}677 678void MemoryAccess::buildMemIntrinsicAccessRelation() {679  assert(isMemoryIntrinsic());680  assert(Subscripts.size() == 2 && Sizes.size() == 1);681 682  isl::pw_aff SubscriptPWA = getPwAff(Subscripts[0]);683  isl::map SubscriptMap = isl::map::from_pw_aff(SubscriptPWA);684 685  isl::map LengthMap;686  if (Subscripts[1] == nullptr) {687    LengthMap = isl::map::universe(SubscriptMap.get_space());688  } else {689    isl::pw_aff LengthPWA = getPwAff(Subscripts[1]);690    LengthMap = isl::map::from_pw_aff(LengthPWA);691    isl::space RangeSpace = LengthMap.get_space().range();692    LengthMap = LengthMap.apply_range(isl::map::lex_gt(RangeSpace));693  }694  LengthMap = LengthMap.lower_bound_si(isl::dim::out, 0, 0);695  LengthMap = LengthMap.align_params(SubscriptMap.get_space());696  SubscriptMap = SubscriptMap.align_params(LengthMap.get_space());697  LengthMap = LengthMap.sum(SubscriptMap);698  AccessRelation =699      LengthMap.set_tuple_id(isl::dim::in, getStatement()->getDomainId());700}701 702void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {703  ScalarEvolution *SE = Statement->getParent()->getSE();704 705  auto MAI = MemAccInst(getAccessInstruction());706  if (isa<MemIntrinsic>(MAI))707    return;708 709  Value *Ptr = MAI.getPointerOperand();710  if (!Ptr || !SE->isSCEVable(Ptr->getType()))711    return;712 713  const SCEV *PtrSCEV = SE->getSCEV(Ptr);714  if (isa<SCEVCouldNotCompute>(PtrSCEV))715    return;716 717  const SCEV *BasePtrSCEV = SE->getPointerBase(PtrSCEV);718  if (BasePtrSCEV && !isa<SCEVCouldNotCompute>(BasePtrSCEV))719    PtrSCEV = SE->getMinusSCEV(PtrSCEV, BasePtrSCEV);720 721  const ConstantRange &Range = SE->getSignedRange(PtrSCEV);722  if (Range.isFullSet())723    return;724 725  if (Range.isUpperWrapped() || Range.isSignWrappedSet())726    return;727 728  bool isWrapping = Range.isSignWrappedSet();729 730  unsigned BW = Range.getBitWidth();731  const auto One = APInt(BW, 1);732  const auto LB = isWrapping ? Range.getLower() : Range.getSignedMin();733  const auto UB = isWrapping ? (Range.getUpper() - One) : Range.getSignedMax();734 735  auto Min = LB.sdiv(APInt(BW, ElementSize));736  auto Max = UB.sdiv(APInt(BW, ElementSize)) + One;737 738  assert(Min.sle(Max) && "Minimum expected to be less or equal than max");739 740  isl::map Relation = AccessRelation;741  isl::set AccessRange = Relation.range();742  AccessRange = addRangeBoundsToSet(AccessRange, ConstantRange(Min, Max), 0,743                                    isl::dim::set);744  AccessRelation = Relation.intersect_range(AccessRange);745}746 747void MemoryAccess::foldAccessRelation() {748  if (Sizes.size() < 2 || isa<SCEVConstant>(Sizes[1]))749    return;750 751  int Size = Subscripts.size();752 753  isl::map NewAccessRelation = AccessRelation;754 755  for (int i = Size - 2; i >= 0; --i) {756    isl::space Space;757    isl::map MapOne, MapTwo;758    isl::pw_aff DimSize = getPwAff(Sizes[i + 1]);759 760    isl::space SpaceSize = DimSize.get_space();761    isl::id ParamId = SpaceSize.get_dim_id(isl::dim::param, 0);762 763    Space = AccessRelation.get_space();764    Space = Space.range().map_from_set();765    Space = Space.align_params(SpaceSize);766 767    int ParamLocation = Space.find_dim_by_id(isl::dim::param, ParamId);768 769    MapOne = isl::map::universe(Space);770    for (int j = 0; j < Size; ++j)771      MapOne = MapOne.equate(isl::dim::in, j, isl::dim::out, j);772    MapOne = MapOne.lower_bound_si(isl::dim::in, i + 1, 0);773 774    MapTwo = isl::map::universe(Space);775    for (int j = 0; j < Size; ++j)776      if (j < i || j > i + 1)777        MapTwo = MapTwo.equate(isl::dim::in, j, isl::dim::out, j);778 779    isl::local_space LS(Space);780    isl::constraint C;781    C = isl::constraint::alloc_equality(LS);782    C = C.set_constant_si(-1);783    C = C.set_coefficient_si(isl::dim::in, i, 1);784    C = C.set_coefficient_si(isl::dim::out, i, -1);785    MapTwo = MapTwo.add_constraint(C);786    C = isl::constraint::alloc_equality(LS);787    C = C.set_coefficient_si(isl::dim::in, i + 1, 1);788    C = C.set_coefficient_si(isl::dim::out, i + 1, -1);789    C = C.set_coefficient_si(isl::dim::param, ParamLocation, 1);790    MapTwo = MapTwo.add_constraint(C);791    MapTwo = MapTwo.upper_bound_si(isl::dim::in, i + 1, -1);792 793    MapOne = MapOne.unite(MapTwo);794    NewAccessRelation = NewAccessRelation.apply_range(MapOne);795  }796 797  isl::id BaseAddrId = getScopArrayInfo()->getBasePtrId();798  isl::space Space = Statement->getDomainSpace();799  NewAccessRelation = NewAccessRelation.set_tuple_id(800      isl::dim::in, Space.get_tuple_id(isl::dim::set));801  NewAccessRelation = NewAccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);802  NewAccessRelation = NewAccessRelation.gist_domain(Statement->getDomain());803 804  // Access dimension folding might in certain cases increase the number of805  // disjuncts in the memory access, which can possibly complicate the generated806  // run-time checks and can lead to costly compilation.807  if (!PollyPreciseFoldAccesses && NewAccessRelation.n_basic_map().release() >808                                       AccessRelation.n_basic_map().release()) {809  } else {810    AccessRelation = NewAccessRelation;811  }812}813 814void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) {815  assert(AccessRelation.is_null() && "AccessRelation already built");816 817  // Initialize the invalid domain which describes all iterations for which the818  // access relation is not modeled correctly.819  isl::set StmtInvalidDomain = getStatement()->getInvalidDomain();820  InvalidDomain = isl::set::empty(StmtInvalidDomain.get_space());821 822  isl::ctx Ctx = Id.ctx();823  isl::id BaseAddrId = SAI->getBasePtrId();824 825  if (getAccessInstruction() && isa<MemIntrinsic>(getAccessInstruction())) {826    buildMemIntrinsicAccessRelation();827    AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);828    return;829  }830 831  if (!isAffine()) {832    // We overapproximate non-affine accesses with a possible access to the833    // whole array. For read accesses it does not make a difference, if an834    // access must or may happen. However, for write accesses it is important to835    // differentiate between writes that must happen and writes that may happen.836    if (AccessRelation.is_null())837      AccessRelation = createBasicAccessMap(Statement);838 839    AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);840    return;841  }842 843  isl::space Space = isl::space(Ctx, 0, Statement->getNumIterators(), 0);844  AccessRelation = isl::map::universe(Space);845 846  for (int i = 0, Size = Subscripts.size(); i < Size; ++i) {847    isl::pw_aff Affine = getPwAff(Subscripts[i]);848    isl::map SubscriptMap = isl::map::from_pw_aff(Affine);849    AccessRelation = AccessRelation.flat_range_product(SubscriptMap);850  }851 852  Space = Statement->getDomainSpace();853  AccessRelation = AccessRelation.set_tuple_id(854      isl::dim::in, Space.get_tuple_id(isl::dim::set));855  AccessRelation = AccessRelation.set_tuple_id(isl::dim::out, BaseAddrId);856 857  AccessRelation = AccessRelation.gist_domain(Statement->getDomain());858}859 860MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst,861                           AccessType AccType, Value *BaseAddress,862                           Type *ElementType, bool Affine,863                           ArrayRef<const SCEV *> Subscripts,864                           ArrayRef<const SCEV *> Sizes, Value *AccessValue,865                           MemoryKind Kind)866    : Kind(Kind), AccType(AccType), Statement(Stmt), InvalidDomain(),867      BaseAddr(BaseAddress), ElementType(ElementType),868      Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst),869      AccessValue(AccessValue), IsAffine(Affine),870      Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(),871      NewAccessRelation() {872  static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};873  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());874 875  std::string IdName = Stmt->getBaseName() + Access;876  Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);877}878 879MemoryAccess::MemoryAccess(ScopStmt *Stmt, AccessType AccType, isl::map AccRel)880    : Kind(MemoryKind::Array), AccType(AccType), Statement(Stmt),881      InvalidDomain(), AccessRelation(), NewAccessRelation(AccRel) {882  isl::id ArrayInfoId = NewAccessRelation.get_tuple_id(isl::dim::out);883  auto *SAI = ScopArrayInfo::getFromId(ArrayInfoId);884  Sizes.push_back(nullptr);885  for (unsigned i = 1; i < SAI->getNumberOfDimensions(); i++)886    Sizes.push_back(SAI->getDimensionSize(i));887  ElementType = SAI->getElementType();888  BaseAddr = SAI->getBasePtr();889  static const std::string TypeStrings[] = {"", "_Read", "_Write", "_MayWrite"};890  const std::string Access = TypeStrings[AccType] + utostr(Stmt->size());891 892  std::string IdName = Stmt->getBaseName() + Access;893  Id = isl::id::alloc(Stmt->getParent()->getIslCtx(), IdName, this);894}895 896MemoryAccess::~MemoryAccess() = default;897 898void MemoryAccess::realignParams() {899  isl::set Ctx = Statement->getParent()->getContext();900  InvalidDomain = InvalidDomain.gist_params(Ctx);901  AccessRelation = AccessRelation.gist_params(Ctx);902 903  // Predictable parameter order is required for JSON imports. Ensure alignment904  // by explicitly calling align_params.905  isl::space CtxSpace = Ctx.get_space();906  InvalidDomain = InvalidDomain.align_params(CtxSpace);907  AccessRelation = AccessRelation.align_params(CtxSpace);908}909 910std::string MemoryAccess::getReductionOperatorStr() const {911  return MemoryAccess::getReductionOperatorStr(getReductionType());912}913 914isl::id MemoryAccess::getId() const { return Id; }915 916raw_ostream &polly::operator<<(raw_ostream &OS,917                               MemoryAccess::ReductionType RT) {918  switch (RT) {919  case MemoryAccess::RT_NONE:920  case MemoryAccess::RT_BOTTOM:921    OS << "NONE";922    break;923  default:924    OS << MemoryAccess::getReductionOperatorStr(RT);925    break;926  }927  return OS;928}929 930void MemoryAccess::print(raw_ostream &OS) const {931  switch (AccType) {932  case READ:933    OS.indent(12) << "ReadAccess :=\t";934    break;935  case MUST_WRITE:936    OS.indent(12) << "MustWriteAccess :=\t";937    break;938  case MAY_WRITE:939    OS.indent(12) << "MayWriteAccess :=\t";940    break;941  }942 943  OS << "[Reduction Type: " << getReductionType() << "] ";944 945  OS << "[Scalar: " << isScalarKind() << "]\n";946  OS.indent(16) << getOriginalAccessRelationStr() << ";\n";947  if (hasNewAccessRelation())948    OS.indent(11) << "new: " << getNewAccessRelationStr() << ";\n";949}950 951#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)952LLVM_DUMP_METHOD void MemoryAccess::dump() const { print(errs()); }953#endif954 955isl::pw_aff MemoryAccess::getPwAff(const SCEV *E) {956  auto *Stmt = getStatement();957  PWACtx PWAC = Stmt->getParent()->getPwAff(E, Stmt->getEntryBlock());958  isl::set StmtDom = getStatement()->getDomain();959  StmtDom = StmtDom.reset_tuple_id();960  isl::set NewInvalidDom = StmtDom.intersect(PWAC.second);961  InvalidDomain = InvalidDomain.unite(NewInvalidDom);962  return PWAC.first;963}964 965// Create a map in the size of the provided set domain, that maps from the966// one element of the provided set domain to another element of the provided967// set domain.968// The mapping is limited to all points that are equal in all but the last969// dimension and for which the last dimension of the input is strict smaller970// than the last dimension of the output.971//972//   getEqualAndLarger(set[i0, i1, ..., iX]):973//974//   set[i0, i1, ..., iX] -> set[o0, o1, ..., oX]975//     : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1), iX < oX976//977static isl::map getEqualAndLarger(isl::space SetDomain) {978  isl::space Space = SetDomain.map_from_set();979  isl::map Map = isl::map::universe(Space);980  unsigned lastDimension = Map.domain_tuple_dim().release() - 1;981 982  // Set all but the last dimension to be equal for the input and output983  //984  //   input[i0, i1, ..., iX] -> output[o0, o1, ..., oX]985  //     : i0 = o0, i1 = o1, ..., i(X-1) = o(X-1)986  for (unsigned i = 0; i < lastDimension; ++i)987    Map = Map.equate(isl::dim::in, i, isl::dim::out, i);988 989  // Set the last dimension of the input to be strict smaller than the990  // last dimension of the output.991  //992  //   input[?,?,?,...,iX] -> output[?,?,?,...,oX] : iX < oX993  Map = Map.order_lt(isl::dim::in, lastDimension, isl::dim::out, lastDimension);994  return Map;995}996 997isl::set MemoryAccess::getStride(isl::map Schedule) const {998  isl::map AccessRelation = getAccessRelation();999  isl::space Space = Schedule.get_space().range();1000  isl::map NextScatt = getEqualAndLarger(Space);1001 1002  Schedule = Schedule.reverse();1003  NextScatt = NextScatt.lexmin();1004 1005  NextScatt = NextScatt.apply_range(Schedule);1006  NextScatt = NextScatt.apply_range(AccessRelation);1007  NextScatt = NextScatt.apply_domain(Schedule);1008  NextScatt = NextScatt.apply_domain(AccessRelation);1009 1010  isl::set Deltas = NextScatt.deltas();1011  return Deltas;1012}1013 1014bool MemoryAccess::isStrideX(isl::map Schedule, int StrideWidth) const {1015  isl::set Stride, StrideX;1016  bool IsStrideX;1017 1018  Stride = getStride(Schedule);1019  StrideX = isl::set::universe(Stride.get_space());1020  int Size = unsignedFromIslSize(StrideX.tuple_dim());1021  for (auto i : seq<int>(0, Size - 1))1022    StrideX = StrideX.fix_si(isl::dim::set, i, 0);1023  StrideX = StrideX.fix_si(isl::dim::set, Size - 1, StrideWidth);1024  IsStrideX = Stride.is_subset(StrideX);1025 1026  return IsStrideX;1027}1028 1029bool MemoryAccess::isStrideZero(isl::map Schedule) const {1030  return isStrideX(Schedule, 0);1031}1032 1033bool MemoryAccess::isStrideOne(isl::map Schedule) const {1034  return isStrideX(Schedule, 1);1035}1036 1037void MemoryAccess::setAccessRelation(isl::map NewAccess) {1038  AccessRelation = NewAccess;1039}1040 1041void MemoryAccess::setNewAccessRelation(isl::map NewAccess) {1042  assert(!NewAccess.is_null());1043 1044#ifndef NDEBUG1045  // Check domain space compatibility.1046  isl::space NewSpace = NewAccess.get_space();1047  isl::space NewDomainSpace = NewSpace.domain();1048  isl::space OriginalDomainSpace = getStatement()->getDomainSpace();1049  assert(OriginalDomainSpace.has_equal_tuples(NewDomainSpace));1050 1051  // Reads must be executed unconditionally. Writes might be executed in a1052  // subdomain only.1053  if (isRead()) {1054    // Check whether there is an access for every statement instance.1055    isl::set StmtDomain = getStatement()->getDomain();1056    isl::set DefinedContext =1057        getStatement()->getParent()->getBestKnownDefinedBehaviorContext();1058    StmtDomain = StmtDomain.intersect_params(DefinedContext);1059    isl::set NewDomain = NewAccess.domain();1060    assert(!StmtDomain.is_subset(NewDomain).is_false() &&1061           "Partial READ accesses not supported");1062  }1063 1064  isl::space NewAccessSpace = NewAccess.get_space();1065  assert(NewAccessSpace.has_tuple_id(isl::dim::set) &&1066         "Must specify the array that is accessed");1067  isl::id NewArrayId = NewAccessSpace.get_tuple_id(isl::dim::set);1068  auto *SAI = static_cast<ScopArrayInfo *>(NewArrayId.get_user());1069  assert(SAI && "Must set a ScopArrayInfo");1070 1071  if (SAI->isArrayKind() && SAI->getBasePtrOriginSAI()) {1072    InvariantEquivClassTy *EqClass =1073        getStatement()->getParent()->lookupInvariantEquivClass(1074            SAI->getBasePtr());1075    assert(EqClass &&1076           "Access functions to indirect arrays must have an invariant and "1077           "hoisted base pointer");1078  }1079 1080  // Check whether access dimensions correspond to number of dimensions of the1081  // accesses array.1082  unsigned Dims = SAI->getNumberOfDimensions();1083  unsigned SpaceSize = unsignedFromIslSize(NewAccessSpace.dim(isl::dim::set));1084  assert(SpaceSize == Dims && "Access dims must match array dims");1085#endif1086 1087  NewAccess = NewAccess.gist_params(getStatement()->getParent()->getContext());1088  NewAccess = NewAccess.gist_domain(getStatement()->getDomain());1089  NewAccessRelation = NewAccess;1090}1091 1092bool MemoryAccess::isLatestPartialAccess() const {1093  isl::set StmtDom = getStatement()->getDomain();1094  isl::set AccDom = getLatestAccessRelation().domain();1095 1096  return !StmtDom.is_subset(AccDom);1097}1098 1099//===----------------------------------------------------------------------===//1100 1101isl::map ScopStmt::getSchedule() const {1102  isl::set Domain = getDomain();1103  if (Domain.is_empty())1104    return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));1105  auto Schedule = getParent()->getSchedule();1106  if (Schedule.is_null())1107    return {};1108  Schedule = Schedule.intersect_domain(isl::union_set(Domain));1109  if (Schedule.is_empty())1110    return isl::map::from_aff(isl::aff(isl::local_space(getDomainSpace())));1111  isl::map M = M.from_union_map(Schedule);1112  M = M.coalesce();1113  M = M.gist_domain(Domain);1114  M = M.coalesce();1115  return M;1116}1117 1118void ScopStmt::restrictDomain(isl::set NewDomain) {1119  assert(NewDomain.is_subset(Domain) &&1120         "New domain is not a subset of old domain!");1121  Domain = NewDomain;1122}1123 1124void ScopStmt::addAccess(MemoryAccess *Access, bool Prepend) {1125  Instruction *AccessInst = Access->getAccessInstruction();1126 1127  if (Access->isArrayKind()) {1128    MemoryAccessList &MAL = InstructionToAccess[AccessInst];1129    MAL.emplace_front(Access);1130  } else if (Access->isValueKind() && Access->isWrite()) {1131    Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());1132    assert(!ValueWrites.lookup(AccessVal));1133 1134    ValueWrites[AccessVal] = Access;1135  } else if (Access->isValueKind() && Access->isRead()) {1136    Value *AccessVal = Access->getAccessValue();1137    assert(!ValueReads.lookup(AccessVal));1138 1139    ValueReads[AccessVal] = Access;1140  } else if (Access->isAnyPHIKind() && Access->isWrite()) {1141    PHINode *PHI = cast<PHINode>(Access->getAccessValue());1142    assert(!PHIWrites.lookup(PHI));1143 1144    PHIWrites[PHI] = Access;1145  } else if (Access->isAnyPHIKind() && Access->isRead()) {1146    PHINode *PHI = cast<PHINode>(Access->getAccessValue());1147    assert(!PHIReads.lookup(PHI));1148 1149    PHIReads[PHI] = Access;1150  }1151 1152  if (Prepend) {1153    MemAccs.insert(MemAccs.begin(), Access);1154    return;1155  }1156  MemAccs.push_back(Access);1157}1158 1159void ScopStmt::realignParams() {1160  for (MemoryAccess *MA : *this)1161    MA->realignParams();1162 1163  simplify(InvalidDomain);1164  simplify(Domain);1165 1166  isl::set Ctx = Parent.getContext();1167  InvalidDomain = InvalidDomain.gist_params(Ctx);1168  Domain = Domain.gist_params(Ctx);1169 1170  // Predictable parameter order is required for JSON imports. Ensure alignment1171  // by explicitly calling align_params.1172  isl::space CtxSpace = Ctx.get_space();1173  InvalidDomain = InvalidDomain.align_params(CtxSpace);1174  Domain = Domain.align_params(CtxSpace);1175}1176 1177ScopStmt::ScopStmt(Scop &parent, Region &R, StringRef Name,1178                   Loop *SurroundingLoop,1179                   std::vector<Instruction *> EntryBlockInstructions)1180    : Parent(parent), InvalidDomain(), Domain(), R(&R), Build(), BaseName(Name),1181      SurroundingLoop(SurroundingLoop), Instructions(EntryBlockInstructions) {}1182 1183ScopStmt::ScopStmt(Scop &parent, BasicBlock &bb, StringRef Name,1184                   Loop *SurroundingLoop,1185                   std::vector<Instruction *> Instructions)1186    : Parent(parent), InvalidDomain(), Domain(), BB(&bb), Build(),1187      BaseName(Name), SurroundingLoop(SurroundingLoop),1188      Instructions(Instructions) {}1189 1190ScopStmt::ScopStmt(Scop &parent, isl::map SourceRel, isl::map TargetRel,1191                   isl::set NewDomain)1192    : Parent(parent), InvalidDomain(), Domain(NewDomain), Build() {1193  BaseName = getIslCompatibleName("CopyStmt_", "",1194                                  std::to_string(parent.getCopyStmtsNum()));1195  isl::id Id = isl::id::alloc(getIslCtx(), getBaseName(), this);1196  Domain = Domain.set_tuple_id(Id);1197  TargetRel = TargetRel.set_tuple_id(isl::dim::in, Id);1198  auto *Access =1199      new MemoryAccess(this, MemoryAccess::AccessType::MUST_WRITE, TargetRel);1200  parent.addAccessFunction(Access);1201  addAccess(Access);1202  SourceRel = SourceRel.set_tuple_id(isl::dim::in, Id);1203  Access = new MemoryAccess(this, MemoryAccess::AccessType::READ, SourceRel);1204  parent.addAccessFunction(Access);1205  addAccess(Access);1206}1207 1208ScopStmt::~ScopStmt() = default;1209 1210std::string ScopStmt::getDomainStr() const { return stringFromIslObj(Domain); }1211 1212std::string ScopStmt::getScheduleStr() const {1213  return stringFromIslObj(getSchedule());1214}1215 1216void ScopStmt::setInvalidDomain(isl::set ID) { InvalidDomain = ID; }1217 1218BasicBlock *ScopStmt::getEntryBlock() const {1219  if (isBlockStmt())1220    return getBasicBlock();1221  return getRegion()->getEntry();1222}1223 1224unsigned ScopStmt::getNumIterators() const { return NestLoops.size(); }1225 1226const char *ScopStmt::getBaseName() const { return BaseName.c_str(); }1227 1228Loop *ScopStmt::getLoopForDimension(unsigned Dimension) const {1229  return NestLoops[Dimension];1230}1231 1232isl::ctx ScopStmt::getIslCtx() const { return Parent.getIslCtx(); }1233 1234isl::set ScopStmt::getDomain() const { return Domain; }1235 1236isl::space ScopStmt::getDomainSpace() const { return Domain.get_space(); }1237 1238isl::id ScopStmt::getDomainId() const { return Domain.get_tuple_id(); }1239 1240void ScopStmt::printInstructions(raw_ostream &OS) const {1241  OS << "Instructions {\n";1242 1243  for (Instruction *Inst : Instructions)1244    OS.indent(16) << *Inst << "\n";1245 1246  OS.indent(12) << "}\n";1247}1248 1249void ScopStmt::print(raw_ostream &OS, bool PrintInstructions) const {1250  OS << "\t" << getBaseName() << "\n";1251  OS.indent(12) << "Domain :=\n";1252 1253  if (!Domain.is_null()) {1254    OS.indent(16) << getDomainStr() << ";\n";1255  } else1256    OS.indent(16) << "n/a\n";1257 1258  OS.indent(12) << "Schedule :=\n";1259 1260  if (!Domain.is_null()) {1261    OS.indent(16) << getScheduleStr() << ";\n";1262  } else1263    OS.indent(16) << "n/a\n";1264 1265  for (MemoryAccess *Access : MemAccs)1266    Access->print(OS);1267 1268  if (PrintInstructions)1269    printInstructions(OS.indent(12));1270}1271 1272#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)1273LLVM_DUMP_METHOD void ScopStmt::dump() const { print(dbgs(), true); }1274#endif1275 1276void ScopStmt::removeAccessData(MemoryAccess *MA) {1277  if (MA->isRead() && MA->isOriginalValueKind()) {1278    bool Found = ValueReads.erase(MA->getAccessValue());1279    (void)Found;1280    assert(Found && "Expected access data not found");1281  }1282  if (MA->isWrite() && MA->isOriginalValueKind()) {1283    bool Found = ValueWrites.erase(cast<Instruction>(MA->getAccessValue()));1284    (void)Found;1285    assert(Found && "Expected access data not found");1286  }1287  if (MA->isWrite() && MA->isOriginalAnyPHIKind()) {1288    bool Found = PHIWrites.erase(cast<PHINode>(MA->getAccessInstruction()));1289    (void)Found;1290    assert(Found && "Expected access data not found");1291  }1292  if (MA->isRead() && MA->isOriginalAnyPHIKind()) {1293    bool Found = PHIReads.erase(cast<PHINode>(MA->getAccessInstruction()));1294    (void)Found;1295    assert(Found && "Expected access data not found");1296  }1297}1298 1299void ScopStmt::removeMemoryAccess(MemoryAccess *MA) {1300  // Remove the memory accesses from this statement together with all scalar1301  // accesses that were caused by it. MemoryKind::Value READs have no access1302  // instruction, hence would not be removed by this function. However, it is1303  // only used for invariant LoadInst accesses, its arguments are always affine,1304  // hence synthesizable, and therefore there are no MemoryKind::Value READ1305  // accesses to be removed.1306  auto Predicate = [&](MemoryAccess *Acc) {1307    return Acc->getAccessInstruction() == MA->getAccessInstruction();1308  };1309  for (auto *MA : MemAccs) {1310    if (Predicate(MA)) {1311      removeAccessData(MA);1312      Parent.removeAccessData(MA);1313    }1314  }1315  llvm::erase_if(MemAccs, Predicate);1316  InstructionToAccess.erase(MA->getAccessInstruction());1317}1318 1319void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA, bool AfterHoisting) {1320  if (AfterHoisting) {1321    auto MAIt = std::find(MemAccs.begin(), MemAccs.end(), MA);1322    assert(MAIt != MemAccs.end());1323    MemAccs.erase(MAIt);1324 1325    removeAccessData(MA);1326    Parent.removeAccessData(MA);1327  }1328 1329  auto It = InstructionToAccess.find(MA->getAccessInstruction());1330  if (It != InstructionToAccess.end()) {1331    It->second.remove(MA);1332    if (It->second.empty())1333      InstructionToAccess.erase(MA->getAccessInstruction());1334  }1335}1336 1337MemoryAccess *ScopStmt::ensureValueRead(Value *V) {1338  MemoryAccess *Access = lookupInputAccessOf(V);1339  if (Access)1340    return Access;1341 1342  ScopArrayInfo *SAI =1343      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);1344  Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),1345                            true, {}, {}, V, MemoryKind::Value);1346  Parent.addAccessFunction(Access);1347  Access->buildAccessRelation(SAI);1348  addAccess(Access);1349  Parent.addAccessData(Access);1350  return Access;1351}1352 1353raw_ostream &polly::operator<<(raw_ostream &OS, const ScopStmt &S) {1354  S.print(OS, PollyPrintInstructions);1355  return OS;1356}1357 1358//===----------------------------------------------------------------------===//1359/// Scop class implement1360 1361void Scop::setContext(isl::set NewContext) {1362  Context = NewContext.align_params(Context.get_space());1363}1364 1365namespace {1366 1367/// Remap parameter values but keep AddRecs valid wrt. invariant loads.1368class SCEVSensitiveParameterRewriter final1369    : public SCEVRewriteVisitor<SCEVSensitiveParameterRewriter> {1370  const ValueToValueMap &VMap;1371 1372public:1373  SCEVSensitiveParameterRewriter(const ValueToValueMap &VMap,1374                                 ScalarEvolution &SE)1375      : SCEVRewriteVisitor(SE), VMap(VMap) {}1376 1377  static const SCEV *rewrite(const SCEV *E, ScalarEvolution &SE,1378                             const ValueToValueMap &VMap) {1379    SCEVSensitiveParameterRewriter SSPR(VMap, SE);1380    return SSPR.visit(E);1381  }1382 1383  const SCEV *visitAddRecExpr(const SCEVAddRecExpr *E) {1384    const SCEV *Start = visit(E->getStart());1385    const SCEV *AddRec = SE.getAddRecExpr(SE.getConstant(E->getType(), 0),1386                                          visit(E->getStepRecurrence(SE)),1387                                          E->getLoop(), SCEV::FlagAnyWrap);1388    return SE.getAddExpr(Start, AddRec);1389  }1390 1391  const SCEV *visitUnknown(const SCEVUnknown *E) {1392    if (auto *NewValue = VMap.lookup(E->getValue()))1393      return SE.getUnknown(NewValue);1394    return E;1395  }1396};1397 1398/// Check whether we should remap a SCEV expression.1399class SCEVFindInsideScop : public SCEVTraversal<SCEVFindInsideScop> {1400  const ValueToValueMap &VMap;1401  bool FoundInside = false;1402  const Scop *S;1403 1404public:1405  SCEVFindInsideScop(const ValueToValueMap &VMap, ScalarEvolution &SE,1406                     const Scop *S)1407      : SCEVTraversal(*this), VMap(VMap), S(S) {}1408 1409  static bool hasVariant(const SCEV *E, ScalarEvolution &SE,1410                         const ValueToValueMap &VMap, const Scop *S) {1411    SCEVFindInsideScop SFIS(VMap, SE, S);1412    SFIS.visitAll(E);1413    return SFIS.FoundInside;1414  }1415 1416  bool follow(const SCEV *E) {1417    if (auto *AddRec = dyn_cast<SCEVAddRecExpr>(E)) {1418      FoundInside |= S->getRegion().contains(AddRec->getLoop());1419    } else if (auto *Unknown = dyn_cast<SCEVUnknown>(E)) {1420      if (Instruction *I = dyn_cast<Instruction>(Unknown->getValue()))1421        FoundInside |= S->getRegion().contains(I) && !VMap.count(I);1422    }1423    return !FoundInside;1424  }1425 1426  bool isDone() { return FoundInside; }1427};1428} // end anonymous namespace1429 1430const SCEV *Scop::getRepresentingInvariantLoadSCEV(const SCEV *E) const {1431  // Check whether it makes sense to rewrite the SCEV.  (ScalarEvolution1432  // doesn't like addition between an AddRec and an expression that1433  // doesn't have a dominance relationship with it.)1434  if (SCEVFindInsideScop::hasVariant(E, *SE, InvEquivClassVMap, this))1435    return E;1436 1437  // Rewrite SCEV.1438  return SCEVSensitiveParameterRewriter::rewrite(E, *SE, InvEquivClassVMap);1439}1440 1441void Scop::createParameterId(const SCEV *Parameter) {1442  assert(Parameters.count(Parameter));1443  assert(!ParameterIds.count(Parameter));1444 1445  std::string ParameterName = "p_" + std::to_string(getNumParams() - 1);1446 1447  if (const SCEVUnknown *ValueParameter = dyn_cast<SCEVUnknown>(Parameter)) {1448    Value *Val = ValueParameter->getValue();1449 1450    if (UseInstructionNames) {1451      // If this parameter references a specific Value and this value has a name1452      // we use this name as it is likely to be unique and more useful than just1453      // a number.1454      if (Val->hasName())1455        ParameterName = Val->getName().str();1456      else if (LoadInst *LI = dyn_cast<LoadInst>(Val)) {1457        auto *LoadOrigin = LI->getPointerOperand()->stripInBoundsOffsets();1458        if (LoadOrigin->hasName()) {1459          ParameterName += "_loaded_from_";1460          ParameterName +=1461              LI->getPointerOperand()->stripInBoundsOffsets()->getName();1462        }1463      }1464    }1465 1466    ParameterName = getIslCompatibleName("", ParameterName, "");1467  }1468 1469  isl::id Id = isl::id::alloc(getIslCtx(), ParameterName,1470                              const_cast<void *>((const void *)Parameter));1471  ParameterIds[Parameter] = Id;1472}1473 1474void Scop::addParams(const ParameterSetTy &NewParameters) {1475  for (const SCEV *Parameter : NewParameters) {1476    // Normalize the SCEV to get the representing element for an invariant load.1477    Parameter = extractConstantFactor(Parameter, *SE).second;1478    Parameter = getRepresentingInvariantLoadSCEV(Parameter);1479 1480    if (Parameters.insert(Parameter))1481      createParameterId(Parameter);1482  }1483}1484 1485isl::id Scop::getIdForParam(const SCEV *Parameter) const {1486  // Normalize the SCEV to get the representing element for an invariant load.1487  Parameter = getRepresentingInvariantLoadSCEV(Parameter);1488  return ParameterIds.lookup(Parameter);1489}1490 1491bool Scop::isDominatedBy(const DominatorTree &DT, BasicBlock *BB) const {1492  return DT.dominates(BB, getEntry());1493}1494 1495void Scop::buildContext() {1496  isl::space Space = isl::space::params_alloc(getIslCtx(), 0);1497  Context = isl::set::universe(Space);1498  InvalidContext = isl::set::empty(Space);1499  AssumedContext = isl::set::universe(Space);1500  DefinedBehaviorContext = isl::set::universe(Space);1501}1502 1503void Scop::addParameterBounds() {1504  unsigned PDim = 0;1505  for (auto *Parameter : Parameters) {1506    ConstantRange SRange = SE->getSignedRange(Parameter);1507    Context = addRangeBoundsToSet(Context, SRange, PDim++, isl::dim::param);1508  }1509  intersectDefinedBehavior(Context, AS_ASSUMPTION);1510}1511 1512void Scop::realignParams() {1513  if (PollyIgnoreParamBounds)1514    return;1515 1516  // Add all parameters into a common model.1517  isl::space Space = getFullParamSpace();1518 1519  // Align the parameters of all data structures to the model.1520  Context = Context.align_params(Space);1521  AssumedContext = AssumedContext.align_params(Space);1522  InvalidContext = InvalidContext.align_params(Space);1523 1524  // As all parameters are known add bounds to them.1525  addParameterBounds();1526 1527  for (ScopStmt &Stmt : *this)1528    Stmt.realignParams();1529  // Simplify the schedule according to the context too.1530  Schedule = Schedule.gist_domain_params(getContext());1531 1532  // Predictable parameter order is required for JSON imports. Ensure alignment1533  // by explicitly calling align_params.1534  Schedule = Schedule.align_params(Space);1535}1536 1537static isl::set simplifyAssumptionContext(isl::set AssumptionContext,1538                                          const Scop &S) {1539  // If we have modeled all blocks in the SCoP that have side effects we can1540  // simplify the context with the constraints that are needed for anything to1541  // be executed at all. However, if we have error blocks in the SCoP we already1542  // assumed some parameter combinations cannot occur and removed them from the1543  // domains, thus we cannot use the remaining domain to simplify the1544  // assumptions.1545  if (!S.hasErrorBlock()) {1546    auto DomainParameters = S.getDomains().params();1547    AssumptionContext = AssumptionContext.gist_params(DomainParameters);1548  }1549 1550  AssumptionContext = AssumptionContext.gist_params(S.getContext());1551  return AssumptionContext;1552}1553 1554void Scop::simplifyContexts() {1555  // The parameter constraints of the iteration domains give us a set of1556  // constraints that need to hold for all cases where at least a single1557  // statement iteration is executed in the whole scop. We now simplify the1558  // assumed context under the assumption that such constraints hold and at1559  // least a single statement iteration is executed. For cases where no1560  // statement instances are executed, the assumptions we have taken about1561  // the executed code do not matter and can be changed.1562  //1563  // WARNING: This only holds if the assumptions we have taken do not reduce1564  //          the set of statement instances that are executed. Otherwise we1565  //          may run into a case where the iteration domains suggest that1566  //          for a certain set of parameter constraints no code is executed,1567  //          but in the original program some computation would have been1568  //          performed. In such a case, modifying the run-time conditions and1569  //          possibly influencing the run-time check may cause certain scops1570  //          to not be executed.1571  //1572  // Example:1573  //1574  //   When delinearizing the following code:1575  //1576  //     for (long i = 0; i < 100; i++)1577  //       for (long j = 0; j < m; j++)1578  //         A[i+p][j] = 1.0;1579  //1580  //   we assume that the condition m <= 0 or (m >= 1 and p >= 0) holds as1581  //   otherwise we would access out of bound data. Now, knowing that code is1582  //   only executed for the case m >= 0, it is sufficient to assume p >= 0.1583  AssumedContext = simplifyAssumptionContext(AssumedContext, *this);1584  InvalidContext = InvalidContext.align_params(getParamSpace());1585  simplify(DefinedBehaviorContext);1586  DefinedBehaviorContext = DefinedBehaviorContext.align_params(getParamSpace());1587}1588 1589isl::set Scop::getDomainConditions(const ScopStmt *Stmt) const {1590  return getDomainConditions(Stmt->getEntryBlock());1591}1592 1593isl::set Scop::getDomainConditions(BasicBlock *BB) const {1594  auto DIt = DomainMap.find(BB);1595  if (DIt != DomainMap.end())1596    return DIt->getSecond();1597 1598  auto &RI = *R.getRegionInfo();1599  auto *BBR = RI.getRegionFor(BB);1600  while (BBR->getEntry() == BB)1601    BBR = BBR->getParent();1602  return getDomainConditions(BBR->getEntry());1603}1604 1605Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, LoopInfo &LI,1606           DominatorTree &DT, ScopDetection::DetectionContext &DC,1607           OptimizationRemarkEmitter &ORE, int ID)1608    : IslCtx(isl_ctx_alloc(), isl_ctx_free), SE(&ScalarEvolution), DT(&DT),1609      R(R), name(std::nullopt), HasSingleExitEdge(R.getExitingBlock()), DC(DC),1610      ORE(ORE), Affinator(this, LI), ID(ID) {1611 1612  // Options defaults that are different from ISL's.1613  isl_options_set_schedule_serialize_sccs(IslCtx.get(), true);1614 1615  SmallVector<char *, 8> IslArgv;1616  IslArgv.reserve(1 + IslArgs.size());1617 1618  // Substitute for program name.1619  IslArgv.push_back(const_cast<char *>("-polly-isl-arg"));1620 1621  for (std::string &Arg : IslArgs)1622    IslArgv.push_back(const_cast<char *>(Arg.c_str()));1623 1624  // Abort if unknown argument is passed.1625  // Note that "-V" (print isl version) will always call exit(0), so we cannot1626  // avoid ISL aborting the program at this point.1627  unsigned IslParseFlags = ISL_ARG_ALL;1628 1629  isl_ctx_parse_options(IslCtx.get(), IslArgv.size(), IslArgv.data(),1630                        IslParseFlags);1631 1632  if (IslOnErrorAbort)1633    isl_options_set_on_error(getIslCtx().get(), ISL_ON_ERROR_ABORT);1634  buildContext();1635}1636 1637Scop::~Scop() = default;1638 1639void Scop::removeFromStmtMap(ScopStmt &Stmt) {1640  for (Instruction *Inst : Stmt.getInstructions())1641    InstStmtMap.erase(Inst);1642 1643  if (Stmt.isRegionStmt()) {1644    for (BasicBlock *BB : Stmt.getRegion()->blocks()) {1645      StmtMap.erase(BB);1646      // Skip entry basic block, as its instructions are already deleted as1647      // part of the statement's instruction list.1648      if (BB == Stmt.getEntryBlock())1649        continue;1650      for (Instruction &Inst : *BB)1651        InstStmtMap.erase(&Inst);1652    }1653  } else {1654    auto StmtMapIt = StmtMap.find(Stmt.getBasicBlock());1655    if (StmtMapIt != StmtMap.end())1656      llvm::erase(StmtMapIt->second, &Stmt);1657    for (Instruction *Inst : Stmt.getInstructions())1658      InstStmtMap.erase(Inst);1659  }1660}1661 1662void Scop::removeStmts(function_ref<bool(ScopStmt &)> ShouldDelete,1663                       bool AfterHoisting) {1664  for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {1665    if (!ShouldDelete(*StmtIt)) {1666      StmtIt++;1667      continue;1668    }1669 1670    // Start with removing all of the statement's accesses including erasing it1671    // from all maps that are pointing to them.1672    // Make a temporary copy because removing MAs invalidates the iterator.1673    SmallVector<MemoryAccess *, 16> MAList(StmtIt->begin(), StmtIt->end());1674    for (MemoryAccess *MA : MAList)1675      StmtIt->removeSingleMemoryAccess(MA, AfterHoisting);1676 1677    removeFromStmtMap(*StmtIt);1678    StmtIt = Stmts.erase(StmtIt);1679  }1680}1681 1682void Scop::removeStmtNotInDomainMap() {1683  removeStmts([this](ScopStmt &Stmt) -> bool {1684    isl::set Domain = DomainMap.lookup(Stmt.getEntryBlock());1685    if (Domain.is_null())1686      return true;1687    return Domain.is_empty();1688  });1689}1690 1691void Scop::simplifySCoP(bool AfterHoisting) {1692  removeStmts(1693      [AfterHoisting](ScopStmt &Stmt) -> bool {1694        // Never delete statements that contain calls to debug functions.1695        if (hasDebugCall(&Stmt))1696          return false;1697 1698        bool RemoveStmt = Stmt.isEmpty();1699 1700        // Remove read only statements only after invariant load hoisting.1701        if (!RemoveStmt && AfterHoisting) {1702          bool OnlyRead = true;1703          for (MemoryAccess *MA : Stmt) {1704            if (MA->isRead())1705              continue;1706 1707            OnlyRead = false;1708            break;1709          }1710 1711          RemoveStmt = OnlyRead;1712        }1713        return RemoveStmt;1714      },1715      AfterHoisting);1716}1717 1718InvariantEquivClassTy *Scop::lookupInvariantEquivClass(Value *Val) {1719  LoadInst *LInst = dyn_cast<LoadInst>(Val);1720  if (!LInst)1721    return nullptr;1722 1723  if (Value *Rep = InvEquivClassVMap.lookup(LInst))1724    LInst = cast<LoadInst>(Rep);1725 1726  Type *Ty = LInst->getType();1727  const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand());1728  for (auto &IAClass : InvariantEquivClasses) {1729    if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType)1730      continue;1731 1732    auto &MAs = IAClass.InvariantAccesses;1733    for (auto *MA : MAs)1734      if (MA->getAccessInstruction() == Val)1735        return &IAClass;1736  }1737 1738  return nullptr;1739}1740 1741ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType,1742                                              ArrayRef<const SCEV *> Sizes,1743                                              MemoryKind Kind,1744                                              const char *BaseName) {1745  assert((BasePtr || BaseName) &&1746         "BasePtr and BaseName can not be nullptr at the same time.");1747  assert(!(BasePtr && BaseName) && "BaseName is redundant.");1748  auto &SAI = BasePtr ? ScopArrayInfoMap[std::make_pair(BasePtr, Kind)]1749                      : ScopArrayNameMap[BaseName];1750  if (!SAI) {1751    auto &DL = getFunction().getParent()->getDataLayout();1752    SAI.reset(new ScopArrayInfo(BasePtr, ElementType, getIslCtx(), Sizes, Kind,1753                                DL, this, BaseName));1754    ScopArrayInfoSet.insert(SAI.get());1755  } else {1756    SAI->updateElementType(ElementType);1757    // In case of mismatching array sizes, we bail out by setting the run-time1758    // context to false.1759    if (!SAI->updateSizes(Sizes))1760      invalidate(DELINEARIZATION, DebugLoc());1761  }1762  return SAI.get();1763}1764 1765ScopArrayInfo *Scop::createScopArrayInfo(Type *ElementType,1766                                         const std::string &BaseName,1767                                         const std::vector<unsigned> &Sizes) {1768  auto *DimSizeType = Type::getInt64Ty(getSE()->getContext());1769  std::vector<const SCEV *> SCEVSizes;1770 1771  for (auto size : Sizes)1772    if (size)1773      SCEVSizes.push_back(getSE()->getConstant(DimSizeType, size, false));1774    else1775      SCEVSizes.push_back(nullptr);1776 1777  auto *SAI = getOrCreateScopArrayInfo(nullptr, ElementType, SCEVSizes,1778                                       MemoryKind::Array, BaseName.c_str());1779  return SAI;1780}1781 1782ScopArrayInfo *Scop::getScopArrayInfoOrNull(Value *BasePtr, MemoryKind Kind) {1783  auto *SAI = ScopArrayInfoMap[std::make_pair(BasePtr, Kind)].get();1784  return SAI;1785}1786 1787ScopArrayInfo *Scop::getScopArrayInfo(Value *BasePtr, MemoryKind Kind) {1788  auto *SAI = getScopArrayInfoOrNull(BasePtr, Kind);1789  assert(SAI && "No ScopArrayInfo available for this base pointer");1790  return SAI;1791}1792 1793std::string Scop::getContextStr() const {1794  return stringFromIslObj(getContext());1795}1796 1797std::string Scop::getAssumedContextStr() const {1798  assert(!AssumedContext.is_null() && "Assumed context not yet built");1799  return stringFromIslObj(AssumedContext);1800}1801 1802std::string Scop::getInvalidContextStr() const {1803  return stringFromIslObj(InvalidContext);1804}1805 1806std::string Scop::getNameStr() const {1807  std::string ExitName, EntryName;1808  std::tie(EntryName, ExitName) = getEntryExitStr();1809  return EntryName + "---" + ExitName;1810}1811 1812std::pair<std::string, std::string> Scop::getEntryExitStr() const {1813  std::string ExitName, EntryName;1814  raw_string_ostream ExitStr(ExitName);1815  raw_string_ostream EntryStr(EntryName);1816 1817  R.getEntry()->printAsOperand(EntryStr, false);1818 1819  if (R.getExit()) {1820    R.getExit()->printAsOperand(ExitStr, false);1821  } else1822    ExitName = "FunctionExit";1823 1824  return std::make_pair(EntryName, ExitName);1825}1826 1827isl::set Scop::getContext() const { return Context; }1828 1829isl::space Scop::getParamSpace() const { return getContext().get_space(); }1830 1831isl::space Scop::getFullParamSpace() const {1832 1833  isl::space Space = isl::space::params_alloc(getIslCtx(), ParameterIds.size());1834 1835  unsigned PDim = 0;1836  for (const SCEV *Parameter : Parameters) {1837    isl::id Id = getIdForParam(Parameter);1838    Space = Space.set_dim_id(isl::dim::param, PDim++, Id);1839  }1840 1841  return Space;1842}1843 1844isl::set Scop::getAssumedContext() const {1845  assert(!AssumedContext.is_null() && "Assumed context not yet built");1846  return AssumedContext;1847}1848 1849bool Scop::isProfitable(bool ScalarsAreUnprofitable) const {1850  if (PollyProcessUnprofitable)1851    return true;1852 1853  if (isEmpty())1854    return false;1855 1856  unsigned OptimizableStmtsOrLoops = 0;1857  for (auto &Stmt : *this) {1858    if (Stmt.getNumIterators() == 0)1859      continue;1860 1861    bool ContainsArrayAccs = false;1862    bool ContainsScalarAccs = false;1863    for (auto *MA : Stmt) {1864      if (MA->isRead())1865        continue;1866      ContainsArrayAccs |= MA->isLatestArrayKind();1867      ContainsScalarAccs |= MA->isLatestScalarKind();1868    }1869 1870    if (!ScalarsAreUnprofitable || (ContainsArrayAccs && !ContainsScalarAccs))1871      OptimizableStmtsOrLoops += Stmt.getNumIterators();1872  }1873 1874  return OptimizableStmtsOrLoops > 1;1875}1876 1877bool Scop::hasFeasibleRuntimeContext() const {1878  if (Stmts.empty())1879    return false;1880 1881  isl::set PositiveContext = getAssumedContext();1882  isl::set NegativeContext = getInvalidContext();1883  PositiveContext = PositiveContext.intersect_params(Context);1884  PositiveContext = PositiveContext.intersect_params(getDomains().params());1885  return PositiveContext.is_empty().is_false() &&1886         PositiveContext.is_subset(NegativeContext).is_false();1887}1888 1889MemoryAccess *Scop::lookupBasePtrAccess(MemoryAccess *MA) {1890  Value *PointerBase = MA->getOriginalBaseAddr();1891 1892  auto *PointerBaseInst = dyn_cast<Instruction>(PointerBase);1893  if (!PointerBaseInst)1894    return nullptr;1895 1896  auto *BasePtrStmt = getStmtFor(PointerBaseInst);1897  if (!BasePtrStmt)1898    return nullptr;1899 1900  return BasePtrStmt->getArrayAccessOrNULLFor(PointerBaseInst);1901}1902 1903static std::string toString(AssumptionKind Kind) {1904  switch (Kind) {1905  case ALIASING:1906    return "No-aliasing";1907  case INBOUNDS:1908    return "Inbounds";1909  case WRAPPING:1910    return "No-overflows";1911  case UNSIGNED:1912    return "Signed-unsigned";1913  case COMPLEXITY:1914    return "Low complexity";1915  case PROFITABLE:1916    return "Profitable";1917  case ERRORBLOCK:1918    return "No-error";1919  case INFINITELOOP:1920    return "Finite loop";1921  case INVARIANTLOAD:1922    return "Invariant load";1923  case DELINEARIZATION:1924    return "Delinearization";1925  }1926  llvm_unreachable("Unknown AssumptionKind!");1927}1928 1929bool Scop::isEffectiveAssumption(isl::set Set, AssumptionSign Sign) {1930  if (Sign == AS_ASSUMPTION) {1931    if (Context.is_subset(Set))1932      return false;1933 1934    if (AssumedContext.is_subset(Set))1935      return false;1936  } else {1937    if (Set.is_disjoint(Context))1938      return false;1939 1940    if (Set.is_subset(InvalidContext))1941      return false;1942  }1943  return true;1944}1945 1946bool Scop::trackAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,1947                           AssumptionSign Sign, BasicBlock *BB) {1948  if (PollyRemarksMinimal && !isEffectiveAssumption(Set, Sign))1949    return false;1950 1951  // Do never emit trivial assumptions as they only clutter the output.1952  if (!PollyRemarksMinimal) {1953    isl::set Univ;1954    if (Sign == AS_ASSUMPTION)1955      Univ = isl::set::universe(Set.get_space());1956 1957    bool IsTrivial = (Sign == AS_RESTRICTION && Set.is_empty()) ||1958                     (Sign == AS_ASSUMPTION && Univ.is_equal(Set));1959 1960    if (IsTrivial)1961      return false;1962  }1963 1964  switch (Kind) {1965  case ALIASING:1966    AssumptionsAliasing++;1967    break;1968  case INBOUNDS:1969    AssumptionsInbounds++;1970    break;1971  case WRAPPING:1972    AssumptionsWrapping++;1973    break;1974  case UNSIGNED:1975    AssumptionsUnsigned++;1976    break;1977  case COMPLEXITY:1978    AssumptionsComplexity++;1979    break;1980  case PROFITABLE:1981    AssumptionsUnprofitable++;1982    break;1983  case ERRORBLOCK:1984    AssumptionsErrorBlock++;1985    break;1986  case INFINITELOOP:1987    AssumptionsInfiniteLoop++;1988    break;1989  case INVARIANTLOAD:1990    AssumptionsInvariantLoad++;1991    break;1992  case DELINEARIZATION:1993    AssumptionsDelinearization++;1994    break;1995  }1996 1997  auto Suffix = Sign == AS_ASSUMPTION ? " assumption:\t" : " restriction:\t";1998  std::string Msg = toString(Kind) + Suffix + stringFromIslObj(Set);1999  if (BB)2000    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc, BB)2001             << Msg);2002  else2003    ORE.emit(OptimizationRemarkAnalysis(DEBUG_TYPE, "AssumpRestrict", Loc,2004                                        R.getEntry())2005             << Msg);2006  return true;2007}2008 2009void Scop::addAssumption(AssumptionKind Kind, isl::set Set, DebugLoc Loc,2010                         AssumptionSign Sign, BasicBlock *BB,2011                         bool RequiresRTC) {2012  // Simplify the assumptions/restrictions first.2013  Set = Set.gist_params(getContext());2014  intersectDefinedBehavior(Set, Sign);2015 2016  if (!RequiresRTC)2017    return;2018 2019  if (!trackAssumption(Kind, Set, Loc, Sign, BB))2020    return;2021 2022  if (Sign == AS_ASSUMPTION)2023    AssumedContext = AssumedContext.intersect(Set).coalesce();2024  else2025    InvalidContext = InvalidContext.unite(Set).coalesce();2026}2027 2028void Scop::intersectDefinedBehavior(isl::set Set, AssumptionSign Sign) {2029  if (DefinedBehaviorContext.is_null())2030    return;2031 2032  if (Sign == AS_ASSUMPTION)2033    DefinedBehaviorContext = DefinedBehaviorContext.intersect(Set);2034  else2035    DefinedBehaviorContext = DefinedBehaviorContext.subtract(Set);2036 2037  // Limit the complexity of the context. If complexity is exceeded, simplify2038  // the set and check again.2039  if (DefinedBehaviorContext.n_basic_set().release() >2040      MaxDisjunktsInDefinedBehaviourContext) {2041    simplify(DefinedBehaviorContext);2042    if (DefinedBehaviorContext.n_basic_set().release() >2043        MaxDisjunktsInDefinedBehaviourContext)2044      DefinedBehaviorContext = {};2045  }2046}2047 2048void Scop::invalidate(AssumptionKind Kind, DebugLoc Loc, BasicBlock *BB) {2049  POLLY_DEBUG(dbgs() << "Invalidate SCoP because of reason " << Kind << "\n");2050  addAssumption(Kind, isl::set::empty(getParamSpace()), Loc, AS_ASSUMPTION, BB);2051}2052 2053isl::set Scop::getInvalidContext() const { return InvalidContext; }2054 2055void Scop::printContext(raw_ostream &OS) const {2056  OS << "Context:\n";2057  OS.indent(4) << Context << "\n";2058 2059  OS.indent(4) << "Assumed Context:\n";2060  OS.indent(4) << AssumedContext << "\n";2061 2062  OS.indent(4) << "Invalid Context:\n";2063  OS.indent(4) << InvalidContext << "\n";2064 2065  OS.indent(4) << "Defined Behavior Context:\n";2066  if (!DefinedBehaviorContext.is_null())2067    OS.indent(4) << DefinedBehaviorContext << "\n";2068  else2069    OS.indent(4) << "<unavailable>\n";2070 2071  unsigned Dim = 0;2072  for (const SCEV *Parameter : Parameters)2073    OS.indent(4) << "p" << Dim++ << ": " << *Parameter << "\n";2074}2075 2076void Scop::printAliasAssumptions(raw_ostream &OS) const {2077  int noOfGroups = 0;2078  for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {2079    if (Pair.second.size() == 0)2080      noOfGroups += 1;2081    else2082      noOfGroups += Pair.second.size();2083  }2084 2085  OS.indent(4) << "Alias Groups (" << noOfGroups << "):\n";2086  if (MinMaxAliasGroups.empty()) {2087    OS.indent(8) << "n/a\n";2088    return;2089  }2090 2091  for (const MinMaxVectorPairTy &Pair : MinMaxAliasGroups) {2092 2093    // If the group has no read only accesses print the write accesses.2094    if (Pair.second.empty()) {2095      OS.indent(8) << "[[";2096      for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {2097        OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second2098           << ">";2099      }2100      OS << " ]]\n";2101    }2102 2103    for (const MinMaxAccessTy &MMAReadOnly : Pair.second) {2104      OS.indent(8) << "[[";2105      OS << " <" << MMAReadOnly.first << ", " << MMAReadOnly.second << ">";2106      for (const MinMaxAccessTy &MMANonReadOnly : Pair.first) {2107        OS << " <" << MMANonReadOnly.first << ", " << MMANonReadOnly.second2108           << ">";2109      }2110      OS << " ]]\n";2111    }2112  }2113}2114 2115void Scop::printStatements(raw_ostream &OS, bool PrintInstructions) const {2116  OS << "Statements {\n";2117 2118  for (const ScopStmt &Stmt : *this) {2119    OS.indent(4);2120    Stmt.print(OS, PrintInstructions);2121  }2122 2123  OS.indent(4) << "}\n";2124}2125 2126void Scop::printArrayInfo(raw_ostream &OS) const {2127  OS << "Arrays {\n";2128 2129  for (auto &Array : arrays())2130    Array->print(OS);2131 2132  OS.indent(4) << "}\n";2133 2134  OS.indent(4) << "Arrays (Bounds as pw_affs) {\n";2135 2136  for (auto &Array : arrays())2137    Array->print(OS, /* SizeAsPwAff */ true);2138 2139  OS.indent(4) << "}\n";2140}2141 2142void Scop::print(raw_ostream &OS, bool PrintInstructions) const {2143  OS.indent(4) << "Function: " << getFunction().getName() << "\n";2144  OS.indent(4) << "Region: " << getNameStr() << "\n";2145  OS.indent(4) << "Max Loop Depth:  " << getMaxLoopDepth() << "\n";2146  OS.indent(4) << "Invariant Accesses: {\n";2147  for (const auto &IAClass : InvariantEquivClasses) {2148    const auto &MAs = IAClass.InvariantAccesses;2149    if (MAs.empty()) {2150      OS.indent(12) << "Class Pointer: " << *IAClass.IdentifyingPointer << "\n";2151    } else {2152      MAs.front()->print(OS);2153      OS.indent(12) << "Execution Context: " << IAClass.ExecutionContext2154                    << "\n";2155    }2156  }2157  OS.indent(4) << "}\n";2158  printContext(OS.indent(4));2159  printArrayInfo(OS.indent(4));2160  printAliasAssumptions(OS);2161  printStatements(OS.indent(4), PrintInstructions);2162}2163 2164#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)2165LLVM_DUMP_METHOD void Scop::dump() const { print(dbgs(), true); }2166#endif2167 2168isl::ctx Scop::getIslCtx() const { return IslCtx.get(); }2169 2170__isl_give PWACtx Scop::getPwAff(const SCEV *E, BasicBlock *BB,2171                                 bool NonNegative,2172                                 RecordedAssumptionsTy *RecordedAssumptions) {2173  // First try to use the SCEVAffinator to generate a piecewise defined2174  // affine function from @p E in the context of @p BB. If that tasks becomes to2175  // complex the affinator might return a nullptr. In such a case we invalidate2176  // the SCoP and return a dummy value. This way we do not need to add error2177  // handling code to all users of this function.2178  auto PWAC = Affinator.getPwAff(E, BB, RecordedAssumptions);2179  if (!PWAC.first.is_null()) {2180    // TODO: We could use a heuristic and either use:2181    //         SCEVAffinator::takeNonNegativeAssumption2182    //       or2183    //         SCEVAffinator::interpretAsUnsigned2184    //       to deal with unsigned or "NonNegative" SCEVs.2185    if (NonNegative)2186      Affinator.takeNonNegativeAssumption(PWAC, RecordedAssumptions);2187    return PWAC;2188  }2189 2190  auto DL = BB ? BB->getTerminator()->getDebugLoc() : DebugLoc();2191  invalidate(COMPLEXITY, DL, BB);2192  return Affinator.getPwAff(SE->getZero(E->getType()), BB, RecordedAssumptions);2193}2194 2195isl::union_set Scop::getDomains() const {2196  isl_space *EmptySpace = isl_space_params_alloc(getIslCtx().get(), 0);2197  isl_union_set *Domain = isl_union_set_empty(EmptySpace);2198 2199  for (const ScopStmt &Stmt : *this)2200    Domain = isl_union_set_add_set(Domain, Stmt.getDomain().release());2201 2202  return isl::manage(Domain);2203}2204 2205isl::pw_aff Scop::getPwAffOnly(const SCEV *E, BasicBlock *BB,2206                               RecordedAssumptionsTy *RecordedAssumptions) {2207  PWACtx PWAC = getPwAff(E, BB, RecordedAssumptions);2208  return PWAC.first;2209}2210 2211isl::union_map2212Scop::getAccessesOfType(std::function<bool(MemoryAccess &)> Predicate) {2213  isl::union_map Accesses = isl::union_map::empty(getIslCtx());2214 2215  for (ScopStmt &Stmt : *this) {2216    for (MemoryAccess *MA : Stmt) {2217      if (!Predicate(*MA))2218        continue;2219 2220      isl::set Domain = Stmt.getDomain();2221      isl::map AccessDomain = MA->getAccessRelation();2222      AccessDomain = AccessDomain.intersect_domain(Domain);2223      Accesses = Accesses.unite(AccessDomain);2224    }2225  }2226 2227  return Accesses.coalesce();2228}2229 2230isl::union_map Scop::getMustWrites() {2231  return getAccessesOfType([](MemoryAccess &MA) { return MA.isMustWrite(); });2232}2233 2234isl::union_map Scop::getMayWrites() {2235  return getAccessesOfType([](MemoryAccess &MA) { return MA.isMayWrite(); });2236}2237 2238isl::union_map Scop::getWrites() {2239  return getAccessesOfType([](MemoryAccess &MA) { return MA.isWrite(); });2240}2241 2242isl::union_map Scop::getReads() {2243  return getAccessesOfType([](MemoryAccess &MA) { return MA.isRead(); });2244}2245 2246isl::union_map Scop::getAccesses() {2247  return getAccessesOfType([](MemoryAccess &MA) { return true; });2248}2249 2250isl::union_map Scop::getAccesses(ScopArrayInfo *Array) {2251  return getAccessesOfType(2252      [Array](MemoryAccess &MA) { return MA.getScopArrayInfo() == Array; });2253}2254 2255isl::union_map Scop::getSchedule() const {2256  auto Tree = getScheduleTree();2257  return Tree.get_map();2258}2259 2260isl::schedule Scop::getScheduleTree() const {2261  return Schedule.intersect_domain(getDomains());2262}2263 2264void Scop::setSchedule(isl::union_map NewSchedule) {2265  auto S = isl::schedule::from_domain(getDomains());2266  Schedule = S.insert_partial_schedule(2267      isl::multi_union_pw_aff::from_union_map(NewSchedule));2268  ScheduleModified = true;2269}2270 2271void Scop::setScheduleTree(isl::schedule NewSchedule) {2272  Schedule = NewSchedule;2273  ScheduleModified = true;2274}2275 2276bool Scop::restrictDomains(isl::union_set Domain) {2277  bool Changed = false;2278  for (ScopStmt &Stmt : *this) {2279    isl::union_set StmtDomain = isl::union_set(Stmt.getDomain());2280    isl::union_set NewStmtDomain = StmtDomain.intersect(Domain);2281 2282    if (StmtDomain.is_subset(NewStmtDomain))2283      continue;2284 2285    Changed = true;2286 2287    NewStmtDomain = NewStmtDomain.coalesce();2288 2289    if (NewStmtDomain.is_empty())2290      Stmt.restrictDomain(isl::set::empty(Stmt.getDomainSpace()));2291    else2292      Stmt.restrictDomain(isl::set(NewStmtDomain));2293  }2294  return Changed;2295}2296 2297ScalarEvolution *Scop::getSE() const { return SE; }2298 2299void Scop::addScopStmt(BasicBlock *BB, StringRef Name, Loop *SurroundingLoop,2300                       std::vector<Instruction *> Instructions) {2301  assert(BB && "Unexpected nullptr!");2302  Stmts.emplace_back(*this, *BB, Name, SurroundingLoop, Instructions);2303  auto *Stmt = &Stmts.back();2304  StmtMap[BB].push_back(Stmt);2305  for (Instruction *Inst : Instructions) {2306    assert(!InstStmtMap.count(Inst) &&2307           "Unexpected statement corresponding to the instruction.");2308    InstStmtMap[Inst] = Stmt;2309  }2310}2311 2312void Scop::addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop,2313                       std::vector<Instruction *> Instructions) {2314  assert(R && "Unexpected nullptr!");2315  Stmts.emplace_back(*this, *R, Name, SurroundingLoop, Instructions);2316  auto *Stmt = &Stmts.back();2317 2318  for (Instruction *Inst : Instructions) {2319    assert(!InstStmtMap.count(Inst) &&2320           "Unexpected statement corresponding to the instruction.");2321    InstStmtMap[Inst] = Stmt;2322  }2323 2324  for (BasicBlock *BB : R->blocks()) {2325    StmtMap[BB].push_back(Stmt);2326    if (BB == R->getEntry())2327      continue;2328    for (Instruction &Inst : *BB) {2329      assert(!InstStmtMap.count(&Inst) &&2330             "Unexpected statement corresponding to the instruction.");2331      InstStmtMap[&Inst] = Stmt;2332    }2333  }2334}2335 2336ScopStmt *Scop::addScopStmt(isl::map SourceRel, isl::map TargetRel,2337                            isl::set Domain) {2338#ifndef NDEBUG2339  isl::set SourceDomain = SourceRel.domain();2340  isl::set TargetDomain = TargetRel.domain();2341  assert(Domain.is_subset(TargetDomain) &&2342         "Target access not defined for complete statement domain");2343  assert(Domain.is_subset(SourceDomain) &&2344         "Source access not defined for complete statement domain");2345#endif2346  Stmts.emplace_back(*this, SourceRel, TargetRel, Domain);2347  CopyStmtsNum++;2348  return &(Stmts.back());2349}2350 2351ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {2352  auto StmtMapIt = StmtMap.find(BB);2353  if (StmtMapIt == StmtMap.end())2354    return {};2355  return StmtMapIt->second;2356}2357 2358ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {2359  auto *PHI = cast<PHINode>(U.getUser());2360  BasicBlock *IncomingBB = PHI->getIncomingBlock(U);2361 2362  // If the value is a non-synthesizable from the incoming block, use the2363  // statement that contains it as user statement.2364  if (auto *IncomingInst = dyn_cast<Instruction>(U.get())) {2365    if (IncomingInst->getParent() == IncomingBB) {2366      if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst))2367        return IncomingStmt;2368    }2369  }2370 2371  // Otherwise, use the epilogue/last statement.2372  return getLastStmtFor(IncomingBB);2373}2374 2375ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {2376  ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);2377  if (!StmtList.empty())2378    return StmtList.back();2379  return nullptr;2380}2381 2382ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {2383  if (RN->isSubRegion())2384    return getStmtListFor(RN->getNodeAs<Region>());2385  return getStmtListFor(RN->getNodeAs<BasicBlock>());2386}2387 2388ArrayRef<ScopStmt *> Scop::getStmtListFor(Region *R) const {2389  return getStmtListFor(R->getEntry());2390}2391 2392int Scop::getRelativeLoopDepth(const Loop *L) const {2393  if (!L || !R.contains(L))2394    return -1;2395  // outermostLoopInRegion always returns nullptr for top level regions2396  if (R.isTopLevelRegion()) {2397    // LoopInfo's depths start at 1, we start at 02398    return L->getLoopDepth() - 1;2399  } else {2400    Loop *OuterLoop = R.outermostLoopInRegion(const_cast<Loop *>(L));2401    assert(OuterLoop);2402    return L->getLoopDepth() - OuterLoop->getLoopDepth();2403  }2404}2405 2406ScopArrayInfo *Scop::getArrayInfoByName(const std::string BaseName) {2407  for (auto &SAI : arrays()) {2408    if (SAI->getName() == BaseName)2409      return SAI;2410  }2411  return nullptr;2412}2413 2414void Scop::addAccessData(MemoryAccess *Access) {2415  const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo();2416  assert(SAI && "can only use after access relations have been constructed");2417 2418  if (Access->isOriginalValueKind() && Access->isRead())2419    ValueUseAccs[SAI].push_back(Access);2420  else if (Access->isOriginalAnyPHIKind() && Access->isWrite())2421    PHIIncomingAccs[SAI].push_back(Access);2422}2423 2424void Scop::removeAccessData(MemoryAccess *Access) {2425  if (Access->isOriginalValueKind() && Access->isWrite()) {2426    ValueDefAccs.erase(Access->getAccessValue());2427  } else if (Access->isOriginalValueKind() && Access->isRead()) {2428    auto &Uses = ValueUseAccs[Access->getScopArrayInfo()];2429    llvm::erase(Uses, Access);2430  } else if (Access->isOriginalPHIKind() && Access->isRead()) {2431    PHINode *PHI = cast<PHINode>(Access->getAccessInstruction());2432    PHIReadAccs.erase(PHI);2433  } else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) {2434    auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()];2435    llvm::erase(Incomings, Access);2436  }2437}2438 2439MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const {2440  assert(SAI->isValueKind());2441 2442  Instruction *Val = dyn_cast<Instruction>(SAI->getBasePtr());2443  if (!Val)2444    return nullptr;2445 2446  return ValueDefAccs.lookup(Val);2447}2448 2449ArrayRef<MemoryAccess *> Scop::getValueUses(const ScopArrayInfo *SAI) const {2450  assert(SAI->isValueKind());2451  auto It = ValueUseAccs.find(SAI);2452  if (It == ValueUseAccs.end())2453    return {};2454  return It->second;2455}2456 2457MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const {2458  assert(SAI->isPHIKind() || SAI->isExitPHIKind());2459 2460  if (SAI->isExitPHIKind())2461    return nullptr;2462 2463  PHINode *PHI = cast<PHINode>(SAI->getBasePtr());2464  return PHIReadAccs.lookup(PHI);2465}2466 2467ArrayRef<MemoryAccess *> Scop::getPHIIncomings(const ScopArrayInfo *SAI) const {2468  assert(SAI->isPHIKind() || SAI->isExitPHIKind());2469  auto It = PHIIncomingAccs.find(SAI);2470  if (It == PHIIncomingAccs.end())2471    return {};2472  return It->second;2473}2474 2475bool Scop::isEscaping(Instruction *Inst) {2476  assert(contains(Inst) && "The concept of escaping makes only sense for "2477                           "values defined inside the SCoP");2478 2479  for (Use &Use : Inst->uses()) {2480    BasicBlock *UserBB = getUseBlock(Use);2481    if (!contains(UserBB))2482      return true;2483 2484    // When the SCoP region exit needs to be simplified, PHIs in the region exit2485    // move to a new basic block such that its incoming blocks are not in the2486    // SCoP anymore.2487    if (hasSingleExitEdge() && isa<PHINode>(Use.getUser()) &&2488        isExit(cast<PHINode>(Use.getUser())->getParent()))2489      return true;2490  }2491  return false;2492}2493 2494void Scop::incrementNumberOfAliasingAssumptions(unsigned step) {2495  AssumptionsAliasing += step;2496}2497 2498Scop::ScopStatistics Scop::getStatistics() const {2499  ScopStatistics Result;2500#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)2501  auto LoopStat = ScopDetection::countBeneficialLoops(&R, *SE, *getLI(), 0);2502 2503  int NumTotalLoops = LoopStat.NumLoops;2504  Result.NumBoxedLoops = getBoxedLoops().size();2505  Result.NumAffineLoops = NumTotalLoops - Result.NumBoxedLoops;2506 2507  for (const ScopStmt &Stmt : *this) {2508    isl::set Domain = Stmt.getDomain().intersect_params(getContext());2509    bool IsInLoop = Stmt.getNumIterators() >= 1;2510    for (MemoryAccess *MA : Stmt) {2511      if (!MA->isWrite())2512        continue;2513 2514      if (MA->isLatestValueKind()) {2515        Result.NumValueWrites += 1;2516        if (IsInLoop)2517          Result.NumValueWritesInLoops += 1;2518      }2519 2520      if (MA->isLatestAnyPHIKind()) {2521        Result.NumPHIWrites += 1;2522        if (IsInLoop)2523          Result.NumPHIWritesInLoops += 1;2524      }2525 2526      isl::set AccSet =2527          MA->getAccessRelation().intersect_domain(Domain).range();2528      if (AccSet.is_singleton()) {2529        Result.NumSingletonWrites += 1;2530        if (IsInLoop)2531          Result.NumSingletonWritesInLoops += 1;2532      }2533    }2534  }2535#endif2536  return Result;2537}2538 2539raw_ostream &polly::operator<<(raw_ostream &OS, const Scop &scop) {2540  scop.print(OS, PollyPrintInstructions);2541  return OS;2542}2543 2544void updateLoopCountStatistic(ScopDetection::LoopStats Stats,2545                              Scop::ScopStatistics ScopStats) {2546  assert(Stats.NumLoops == ScopStats.NumAffineLoops + ScopStats.NumBoxedLoops);2547 2548  NumScops++;2549  NumLoopsInScop += Stats.NumLoops;2550  MaxNumLoopsInScop =2551      std::max(MaxNumLoopsInScop.getValue(), (uint64_t)Stats.NumLoops);2552 2553  if (Stats.MaxDepth == 0)2554    NumScopsDepthZero++;2555  else if (Stats.MaxDepth == 1)2556    NumScopsDepthOne++;2557  else if (Stats.MaxDepth == 2)2558    NumScopsDepthTwo++;2559  else if (Stats.MaxDepth == 3)2560    NumScopsDepthThree++;2561  else if (Stats.MaxDepth == 4)2562    NumScopsDepthFour++;2563  else if (Stats.MaxDepth == 5)2564    NumScopsDepthFive++;2565  else2566    NumScopsDepthLarger++;2567 2568  NumAffineLoops += ScopStats.NumAffineLoops;2569  NumBoxedLoops += ScopStats.NumBoxedLoops;2570 2571  NumValueWrites += ScopStats.NumValueWrites;2572  NumValueWritesInLoops += ScopStats.NumValueWritesInLoops;2573  NumPHIWrites += ScopStats.NumPHIWrites;2574  NumPHIWritesInLoops += ScopStats.NumPHIWritesInLoops;2575  NumSingletonWrites += ScopStats.NumSingletonWrites;2576  NumSingletonWritesInLoops += ScopStats.NumSingletonWritesInLoops;2577}2578 2579ScopInfo::ScopInfo(const DataLayout &DL, ScopDetection &SD, ScalarEvolution &SE,2580                   LoopInfo &LI, AliasAnalysis &AA, DominatorTree &DT,2581                   AssumptionCache &AC, OptimizationRemarkEmitter &ORE)2582    : DL(DL), SD(SD), SE(SE), LI(LI), AA(AA), DT(DT), AC(AC), ORE(ORE) {2583  recompute();2584}2585 2586void ScopInfo::recompute() {2587  RegionToScopMap.clear();2588  /// Create polyhedral description of scops for all the valid regions of a2589  /// function.2590  for (auto &It : SD) {2591    Region *R = const_cast<Region *>(It);2592    if (!SD.isMaxRegionInScop(*R))2593      continue;2594 2595    ScopBuilder SB(R, AC, AA, DL, DT, LI, SD, SE, ORE);2596    std::unique_ptr<Scop> S = SB.getScop();2597    if (!S)2598      continue;2599#if !defined(NDEBUG) || defined(LLVM_ENABLE_STATS)2600    ScopDetection::LoopStats Stats =2601        ScopDetection::countBeneficialLoops(&S->getRegion(), SE, LI, 0);2602    updateLoopCountStatistic(Stats, S->getStatistics());2603#endif2604    bool Inserted = RegionToScopMap.insert({R, std::move(S)}).second;2605    assert(Inserted && "Building Scop for the same region twice!");2606    (void)Inserted;2607  }2608}2609 2610bool ScopInfo::invalidate(Function &F, const PreservedAnalyses &PA,2611                          FunctionAnalysisManager::Invalidator &Inv) {2612  // Check whether the analysis, all analyses on functions have been preserved2613  // or anything we're holding references to is being invalidated2614  auto PAC = PA.getChecker<ScopInfoAnalysis>();2615  return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Function>>()) ||2616         Inv.invalidate<ScopAnalysis>(F, PA) ||2617         Inv.invalidate<ScalarEvolutionAnalysis>(F, PA) ||2618         Inv.invalidate<LoopAnalysis>(F, PA) ||2619         Inv.invalidate<AAManager>(F, PA) ||2620         Inv.invalidate<DominatorTreeAnalysis>(F, PA) ||2621         Inv.invalidate<AssumptionAnalysis>(F, PA);2622}2623 2624AnalysisKey ScopInfoAnalysis::Key;2625 2626ScopInfoAnalysis::Result ScopInfoAnalysis::run(Function &F,2627                                               FunctionAnalysisManager &FAM) {2628  auto &SD = FAM.getResult<ScopAnalysis>(F);2629  auto &SE = FAM.getResult<ScalarEvolutionAnalysis>(F);2630  auto &LI = FAM.getResult<LoopAnalysis>(F);2631  auto &AA = FAM.getResult<AAManager>(F);2632  auto &DT = FAM.getResult<DominatorTreeAnalysis>(F);2633  auto &AC = FAM.getResult<AssumptionAnalysis>(F);2634  auto &DL = F.getParent()->getDataLayout();2635  auto &ORE = FAM.getResult<OptimizationRemarkEmitterAnalysis>(F);2636  return {DL, SD, SE, LI, AA, DT, AC, ORE};2637}2638 2639PreservedAnalyses ScopInfoPrinterPass::run(Function &F,2640                                           FunctionAnalysisManager &FAM) {2641  auto &SI = FAM.getResult<ScopInfoAnalysis>(F);2642  // Since the legacy PM processes Scops in bottom up, we print them in reverse2643  // order here to keep the output persistent2644  for (auto &It : reverse(SI)) {2645    if (It.second)2646      It.second->print(Stream, PollyPrintInstructions);2647    else2648      Stream << "Invalid Scop!\n";2649  }2650  return PreservedAnalyses::all();2651}2652