Index: include/polly/ScopDetection.h =================================================================== --- include/polly/ScopDetection.h +++ include/polly/ScopDetection.h @@ -101,7 +101,7 @@ }; typedef std::map MapInsnToMemAcc; -typedef std::pair PairInstSCEV; +typedef std::pair PairInstSCEV; typedef std::vector AFs; typedef std::map BaseToAFs; typedef std::map BaseToElSize; @@ -150,6 +150,8 @@ SetVector NonAffineAccesses; BaseToElSize ElementSize; + MapInsnToMemAcc InsnToMemAcc; + /// @brief The region has at least one load instruction. bool hasLoads; Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -89,11 +89,10 @@ /// @param BasePtr The array base pointer. /// @param ElementType The type of the elements stored in the array. /// @param IslCtx The isl context used to create the base pointer id. - /// @param DimensionSizes A vector containing the size of each dimension. /// @param IsPHI Is this a PHI node specific array info object. /// @param S The scop this array object belongs to. - ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx, - ArrayRef DimensionSizes, bool IsPHI, Scop *S); + ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *IslCtx, bool IsPHI, + Scop *S); /// @brief Update the sizes of the ScopArrayInfo object. /// @@ -412,12 +411,6 @@ /// @brief An unique name of the accessed array. std::string BaseName; - - /// @brief Size in bytes of a single array element. - unsigned ElemBytes; - - /// @brief Size of each dimension of the accessed array. - SmallVector Sizes; // @} // Properties describing the accessed element. @@ -447,8 +440,6 @@ isl_map *NewAccessRelation; // @} - unsigned getElemSizeInBytes() const { return ElemBytes; } - bool isAffine() const { return IsAffine; } /// @brief Is this MemoryAccess modeling special PHI node accesses? @@ -456,7 +447,7 @@ __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement); - void assumeNoOutOfBound(); + void assumeNoOutOfBound(const ScopArrayInfo *SAI); /// @brief Compute bounds on an over approximated access relation. /// @@ -501,7 +492,7 @@ /// access function, but cases that can be statically proven to not happen /// will be eliminated later on. __isl_give isl_map *foldAccess(__isl_take isl_map *AccessRelation, - ScopStmt *Statement); + ScopStmt *Statement, const ScopArrayInfo *SAI); /// @brief Assemble the access relation from all availbale information. /// @@ -519,17 +510,14 @@ /// @param Id Identifier that is guranteed to be unique within the /// same ScopStmt. /// @param BaseAddr The accessed array's address. - /// @param ElemBytes Number of accessed bytes. /// @param AccType Whether read or write access. /// @param IsAffine Whether the subscripts are affine expressions. /// @param Origin What is the purpose of this access? /// @param Subscripts Subscipt expressions - /// @param Sizes Dimension lengths of the accessed array. /// @param BaseName Name of the acessed array. MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, __isl_take isl_id *Id, - AccessType Type, Value *BaseAddress, unsigned ElemBytes, - bool Affine, ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue, + AccessType Type, Value *BaseAddress, bool Affine, + ArrayRef Subscripts, Value *AccessValue, AccessOrigin Origin, StringRef BaseName); ~MemoryAccess(); @@ -646,16 +634,6 @@ /// @brief Align the parameters in the access relation to the scop context void realignParams(); - /// @brief Update the dimensionality of the memory access. - /// - /// During scop construction some memory accesses may not be constructed with - /// their full dimensionality, but outer dimensions that may have been omitted - /// if they took the value 'zero'. By updating the dimensionality of the - /// statement we add additional zero-valued dimensions to match the - /// dimensionality of the ScopArrayInfo object that belongs to this memory - /// access. - void updateDimensionality(); - /// @brief Get identifier for the memory access. /// /// This identifier is unique for all accesses that belong to the same scop @@ -1143,7 +1121,9 @@ unsigned MaxLoopDepth); /// @brief Initialize this ScopInfo . - void init(AliasAnalysis &AA); + void + init(AliasAnalysis &AA, + DenseMap> &AccessSizes); /// @brief Add loop carried constraints to the header block of the loop @p L. /// @@ -1186,6 +1166,16 @@ /// @see isIgnored() void simplifySCoP(bool RemoveIgnoredStmts); + /// @brief Create a new ScopArrayInfo object. + /// + /// @param BasePtr The base pointer of the array. + /// @param ElementType The type of the elements stored in this array. + ScopArrayInfo *createScopArrayInfo(Value *BasePtr, Type *ElementType); + + /// @brief Create the ScopArrayInfo objects for memory accesses in this SCoP. + void buildScopArrays( + DenseMap> &AccessSizes); + /// @brief Hoist invariant memory loads and check for required ones. /// /// We first identify "common" invariant loads, thus loads that are invariant @@ -1229,15 +1219,6 @@ /// @param R The region we build the statement for (or null). ScopStmt *addScopStmt(BasicBlock *BB, Region *R); - /// @param Update access dimensionalities. - /// - /// When detecting memory accesses different accesses to the same array may - /// have built with different dimensionality, as outer zero-values dimensions - /// may not have been recognized as separate dimensions. This function goes - /// again over all memory accesses and updates their dimensionality to match - /// the dimensionality of the underlying ScopArrayInfo object. - void updateAccessDimensionality(); - /// @brief Build Schedule and ScopStmts. /// /// @param R The current region traversed. @@ -1455,7 +1436,6 @@ /// PHI node storage. const ScopArrayInfo *getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType, - ArrayRef Sizes, bool IsPHI = false); /// @brief Return the cached ScopArrayInfo object for @p BasePtr. @@ -1582,6 +1562,11 @@ // must live until #scop is deleted. AccFuncMapType AccFuncMap; + /// @brief Helper map to remember the delinearization shape of GEPs + /// + /// TODO: This should be unified with the rest of the delinearization. + DenseMap> AccessSizes; + // The Scop Scop *scop; isl_ctx *ctx; @@ -1601,14 +1586,12 @@ /// @brief Build an instance of MemoryAccess from the Load/Store instruction. /// - /// @param Inst The Load/Store instruction that access the memory - /// @param L The parent loop of the instruction - /// @param R The region on which to build the data access dictionary. - /// @param BoxedLoops The set of loops that are overapproximated in @p R. - /// @param ScopRIL The required invariant loads equivalence classes. + /// @param Inst The Load/Store instruction that access the memory + /// @param L The parent loop of the instruction + /// @param R The region on which to build the data access dictionary. + /// @param DC The detection context for @p R. void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL); + const ScopDetection::DetectionContext *DC); /// @brief Analyze and extract the cross-BB scalar dependences (or, /// dataflow dependencies) of an instruction. @@ -1660,17 +1643,14 @@ /// inside @p BB. /// @param Type The kind of access. /// @param BaseAddress The accessed array's base address. - /// @param ElemBytes Size of accessed array element. /// @param Affine Whether all subscripts are affine expressions. /// @param AccessValue Value read or written. /// @param Subscripts Access subscripts per dimension. - /// @param Sizes The array diminsion's sizes. /// @param Origin Purpose of this access. void addMemoryAccess(BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, Value *BaseAddress, - unsigned ElemBytes, bool Affine, Value *AccessValue, + bool Affine, Value *AccessValue, ArrayRef Subscripts, - ArrayRef Sizes, MemoryAccess::AccessOrigin Origin); /// @brief Create a MemoryAccess that represents either a LoadInst or @@ -1679,16 +1659,13 @@ /// @param MemAccInst The LoadInst or StoreInst. /// @param Type The kind of access. /// @param BaseAddress The accessed array's base address. - /// @param ElemBytes Size of accessed array element. /// @param IsAffine Whether all subscripts are affine expressions. /// @param Subscripts Access subscripts per dimension. - /// @param Sizes The array dimension's sizes. /// @param AccessValue Value read or written. /// @see AccessOrigin void addExplicitAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type, - Value *BaseAddress, unsigned ElemBytes, bool IsAffine, - ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue); + Value *BaseAddress, bool IsAffine, + ArrayRef Subscripts, Value *AccessValue); /// @brief Create a MemoryAccess for writing an llvm::Value. /// Index: lib/Analysis/ScopDetection.cpp =================================================================== --- lib/Analysis/ScopDetection.cpp +++ lib/Analysis/ScopDetection.cpp @@ -472,8 +472,6 @@ return true; } -MapInsnToMemAcc InsnToMemAcc; - bool ScopDetection::hasAffineMemoryAccesses(DetectionContext &Context) const { Region &CurRegion = Context.CurRegion; @@ -531,16 +529,19 @@ if (auto *Unknown = dyn_cast(DelinearizedSize)) { auto *value = dyn_cast(Unknown->getValue()); if (isa(value)) { - invalid( - Context, /*Assert=*/true, - Context.Accesses[BasePointer].front().first, BaseValue); + const Instruction *Insn = + cast(Context.Accesses[BasePointer].front().first); + invalid(Context, /*Assert=*/true, + Insn, BaseValue); return false; } } - if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion)) - invalid( - Context, /*Assert=*/true, DelinearizedSize, - Context.Accesses[BasePointer].front().first, BaseValue); + if (hasScalarDepsInsideRegion(DelinearizedSize, &CurRegion)) { + const Instruction *Insn = + cast(Context.Accesses[BasePointer].front().first); + invalid(Context, /*Assert=*/true, + DelinearizedSize, Insn, BaseValue); + } } // No array shape derived. @@ -549,7 +550,7 @@ continue; for (const auto &Pair : Context.Accesses[BasePointer]) { - const Instruction *Insn = Pair.first; + const Instruction *Insn = cast(Pair.first); const SCEV *AF = Pair.second; if (!isAffine(AF, Context, BaseValue)) { @@ -572,7 +573,7 @@ // when translated to a polyhedral representation. MapInsnToMemAcc TempMemoryAccesses; for (const auto &Pair : Context.Accesses[BasePointer]) { - const Instruction *Insn = Pair.first; + const Instruction *Insn = cast(Pair.first); auto *AF = Pair.second; bool IsNonAffine = false; TempMemoryAccesses.insert(std::make_pair(Insn, MemAcc(Insn, Shape))); @@ -605,7 +606,8 @@ } if (!BasePtrHasNonAffine) - InsnToMemAcc.insert(TempMemoryAccesses.begin(), TempMemoryAccesses.end()); + Context.InsnToMemAcc.insert(TempMemoryAccesses.begin(), + TempMemoryAccesses.end()); } return true; } @@ -657,14 +659,18 @@ if (Context.BoxedLoopsSet.count(L)) isVariantInNonAffineLoop = true; - if (PollyDelinearize && !isVariantInNonAffineLoop) { - Context.Accesses[BasePointer].push_back({&Inst, AccessFunction}); + Context.Accesses[BasePointer].push_back({&Inst, AccessFunction}); - if (!isAffine(AccessFunction, Context, BaseValue)) + if (isVariantInNonAffineLoop) { + if (AllowNonAffine) Context.NonAffineAccesses.insert(BasePointer); - } else if (!AllowNonAffine) { - if (isVariantInNonAffineLoop || - !isAffine(AccessFunction, Context, BaseValue)) + else + return invalid(Context, /*Assert=*/true, + AccessFunction, &Inst, BaseValue); + } else if (!isAffine(AccessFunction, Context, BaseValue)) { + if (AllowNonAffine || PollyDelinearize) + Context.NonAffineAccesses.insert(BasePointer); + else return invalid(Context, /*Assert=*/true, AccessFunction, &Inst, BaseValue); } @@ -974,10 +980,10 @@ return false; } - if (!hasAffineMemoryAccesses(Context)) - return false; + if (PollyDelinearize) + return hasAffineMemoryAccesses(Context); - return true; + return AllowNonAffine || Context.NonAffineAccesses.empty(); } bool ScopDetection::isValidRegion(DetectionContext &Context) const { @@ -1180,7 +1186,6 @@ void ScopDetection::releaseMemory() { RejectLogs.clear(); ValidRegions.clear(); - InsnToMemAcc.clear(); DetectionContextMap.clear(); // Do not clear the invalid function set. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -155,13 +155,12 @@ } ScopArrayInfo::ScopArrayInfo(Value *BasePtr, Type *ElementType, isl_ctx *Ctx, - ArrayRef Sizes, bool IsPHI, Scop *S) + bool IsPHI, Scop *S) : BasePtr(BasePtr), ElementType(ElementType), IsPHI(IsPHI), S(*S) { std::string BasePtrName = getIslCompatibleName("MemRef_", BasePtr, IsPHI ? "__phi" : ""); Id = isl_id_alloc(Ctx, BasePtrName.c_str(), this); - updateSizes(Sizes); BasePtrOriginSAI = identifyBasePtrOriginSAI(S, BasePtr); if (BasePtrOriginSAI) const_cast(BasePtrOriginSAI)->addDerivedSAI(this); @@ -206,7 +205,8 @@ std::string ScopArrayInfo::getName() const { return isl_id_get_name(Id); } int ScopArrayInfo::getElemSizeInBytes() const { - return ElementType->getPrimitiveSizeInBits() / 8; + const auto *DL = &S.getRegion().getEntry()->getModule()->getDataLayout(); + return DL->getTypeAllocSize(ElementType); } isl_id *ScopArrayInfo::getBasePtrId() const { return isl_id_copy(Id); } @@ -215,7 +215,7 @@ void ScopArrayInfo::print(raw_ostream &OS, bool SizeAsPwAff) const { OS.indent(8) << *getElementType() << " " << getName() << "[*]"; - for (unsigned u = 0; u < getNumberOfDimensions(); u++) { + for (int u = 0, e = getNumberOfDimensions() - 1; u < e; u++) { OS << "["; if (SizeAsPwAff) @@ -246,26 +246,6 @@ return SAI; } -void MemoryAccess::updateDimensionality() { - auto ArraySpace = getScopArrayInfo()->getSpace(); - auto AccessSpace = isl_space_range(isl_map_get_space(AccessRelation)); - - auto DimsArray = isl_space_dim(ArraySpace, isl_dim_set); - auto DimsAccess = isl_space_dim(AccessSpace, isl_dim_set); - auto DimsMissing = DimsArray - DimsAccess; - - auto Map = isl_map_from_domain_and_range(isl_set_universe(AccessSpace), - isl_set_universe(ArraySpace)); - - for (unsigned i = 0; i < DimsMissing; i++) - Map = isl_map_fix_si(Map, isl_dim_out, i, 0); - - for (unsigned i = DimsMissing; i < DimsArray; i++) - Map = isl_map_equate(Map, isl_dim_in, i - DimsMissing, isl_dim_out, i); - - AccessRelation = isl_map_apply_range(AccessRelation, Map); -} - const std::string MemoryAccess::getReductionOperatorStr(MemoryAccess::ReductionType RT) { switch (RT) { @@ -460,7 +440,7 @@ // possibly yield out of bound memory accesses. The complement of these // constraints is the set of constraints that needs to be assumed to ensure such // statement instances are never executed. -void MemoryAccess::assumeNoOutOfBound() { +void MemoryAccess::assumeNoOutOfBound(const ScopArrayInfo *SAI) { isl_space *Space = isl_space_range(getOriginalAccessRelationSpace()); isl_set *Outside = isl_set_empty(isl_space_copy(Space)); for (int i = 1, Size = Subscripts.size(); i < Size; ++i) { @@ -472,7 +452,7 @@ isl_set *DimOutside; DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero); - isl_pw_aff *SizeE = Statement->getPwAff(Sizes[i - 1]); + isl_pw_aff *SizeE = Statement->getPwAff(SAI->getDimensionSize(i - 1)); SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0, Statement->getNumIterators()); @@ -534,13 +514,14 @@ } __isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation, - ScopStmt *Statement) { + ScopStmt *Statement, + const ScopArrayInfo *SAI) { int Size = Subscripts.size(); for (int i = Size - 2; i >= 0; --i) { isl_space *Space; isl_map *MapOne, *MapTwo; - isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]); + isl_pw_aff *DimSize = Statement->getPwAff(SAI->getDimensionSize(i)); isl_space *SpaceSize = isl_pw_aff_get_space(DimSize); isl_pw_aff_free(DimSize); @@ -586,6 +567,16 @@ void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) { assert(!AccessRelation && "AccessReltation already built"); + unsigned SAINumDim = SAI->getNumberOfDimensions(); + if (isExplicit() && Subscripts.size() <= SAINumDim) { + while (Subscripts.size() < SAINumDim) { + ScalarEvolution *SE = Statement->getParent()->getSE(); + auto *I64Ty = IntegerType::getInt64Ty(AccessValue->getContext()); + auto *ZeroSCEV = SE->getConstant(I64Ty, 0); + Subscripts.insert(Subscripts.begin(), ZeroSCEV); + } + } + isl_ctx *Ctx = isl_id_get_ctx(Id); isl_id *BaseAddrId = SAI->getBasePtrId(); @@ -598,7 +589,7 @@ AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); - computeBoundsOnAccessRelation(getElemSizeInBytes()); + computeBoundsOnAccessRelation(SAI->getElemSizeInBytes()); return; } @@ -617,7 +608,7 @@ // two subsequent values of 'i' index two values that are stored next to // each other in memory. By this division we make this characteristic // obvious again. - isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes()); + isl_val *v = isl_val_int_from_si(Ctx, SAI->getElemSizeInBytes()); Affine = isl_pw_aff_scale_down_val(Affine, v); } @@ -626,8 +617,8 @@ AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap); } - if (Sizes.size() > 1 && !isa(Sizes[0])) - AccessRelation = foldAccess(AccessRelation, Statement); + if (SAINumDim > 1 && !isa(SAI->getDimensionSize(0))) + AccessRelation = foldAccess(AccessRelation, Statement, SAI); Space = Statement->getDomainSpace(); AccessRelation = isl_map_set_tuple_id( @@ -635,20 +626,19 @@ AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); - assumeNoOutOfBound(); + assumeNoOutOfBound(SAI); AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain()); isl_space_free(Space); } MemoryAccess::MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type, - Value *BaseAddress, unsigned ElemBytes, bool Affine, + Value *BaseAddress, bool Affine, ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue, - AccessOrigin Origin, StringRef BaseName) + Value *AccessValue, AccessOrigin Origin, + StringRef BaseName) : Id(Id), Origin(Origin), AccType(Type), RedType(RT_NONE), Statement(Stmt), - BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes), - Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst), + BaseAddr(BaseAddress), BaseName(BaseName), AccessInstruction(AccessInst), AccessValue(AccessValue), IsAffine(Affine), Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr), NewAccessRelation(nullptr) {} @@ -820,7 +810,7 @@ Type *ElementType = Access->getAccessValue()->getType(); const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo( - Access->getBaseAddr(), ElementType, Access->Sizes, Access->isPHI()); + Access->getBaseAddr(), ElementType, Access->isPHI()); Access->buildAccessRelation(SAI); } @@ -1495,6 +1485,59 @@ isl_space_free(Space); } +void Scop::buildScopArrays( + DenseMap> &AccessSizes) { + const auto &DC = *SD.getDetectionContext(&getRegion()); + + for (auto &B2AIt : DC.Accesses) { + + const SCEVUnknown *BasePtrSCEV = B2AIt.first; + Value *BasePtr = BasePtrSCEV->getValue(); + assert(BasePtr); + + Type *ArrayType = nullptr; + for (auto &InstIt : B2AIt.second) { + if (!InstIt.first) + continue; + + unsigned TypeSize = UINT_MAX; + Value *PtrOp = getPointerOperand(*cast(InstIt.first)); + if (TypeSize > PtrOp->getType()->getPrimitiveSizeInBits()) { + ArrayType = PtrOp->getType(); + TypeSize = ArrayType->getPrimitiveSizeInBits(); + } + } + + if (!ArrayType) + continue; + + auto *SAI = + createScopArrayInfo(BasePtr, ArrayType->getPointerElementType()); + + for (auto &InstIt : B2AIt.second) { + if (!InstIt.first) + continue; + + auto AccItr = DC.InsnToMemAcc.find(cast(InstIt.first)); + if (AccItr != DC.InsnToMemAcc.end()) { + auto &Sizes = AccItr->second.Shape->DelinearizedSizes; + if (Sizes.size() > SAI->getNumberOfDimensions()) + SAI->updateSizes(Sizes); + } + + auto ASIt = AccessSizes.find(cast(InstIt.first)); + if (ASIt != AccessSizes.end()) { + auto &Sizes = ASIt->second; + Sizes.push_back( + SE->getConstant(IntegerType::getInt64Ty(BasePtr->getContext()), + SAI->getElemSizeInBytes())); + if (Sizes.size() > SAI->getNumberOfDimensions()) + SAI->updateSizes(Sizes); + } + } + } +} + void Scop::buildContext() { isl_space *Space = isl_space_params_alloc(IslCtx, 0); Context = isl_set_universe(isl_space_copy(Space)); @@ -2315,7 +2358,9 @@ IslCtx(Context), Context(nullptr), Affinator(this), AssumedContext(nullptr), BoundaryContext(nullptr), Schedule(nullptr) {} -void Scop::init(AliasAnalysis &AA) { +void Scop::init( + AliasAnalysis &AA, + DenseMap> &AccessSizes) { buildContext(); buildDomains(&R); @@ -2325,6 +2370,8 @@ if (Stmts.empty()) return; + buildScopArrays(AccessSizes); + // The ScopStmts now have enough information to initialize themselves. for (ScopStmt &Stmt : Stmts) Stmt.init(); @@ -2333,7 +2380,6 @@ Loop *L = getLoopSurroundingRegion(R, LI); LoopSchedules[L]; buildSchedule(&R, LoopSchedules); - updateAccessDimensionality(); Schedule = LoopSchedules[L].first; realignParams(); @@ -2372,12 +2418,6 @@ isl_set_free(IA.second); } -void Scop::updateAccessDimensionality() { - for (auto &Stmt : *this) - for (auto &Access : Stmt) - Access->updateDimensionality(); -} - void Scop::simplifySCoP(bool RemoveIgnoredStmts) { for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) { ScopStmt &Stmt = *StmtIt; @@ -2538,17 +2578,18 @@ compareInvariantAccesses); } +ScopArrayInfo *Scop::createScopArrayInfo(Value *BasePtr, Type *AccessType) { + auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, false)]; + assert(!SAI && "SAI already created"); + SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), false, this)); + return SAI.get(); +} + const ScopArrayInfo * -Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType, - ArrayRef Sizes, bool IsPHI) { +Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *AccessType, bool IsPHI) { auto &SAI = ScopArrayInfoMap[std::make_pair(BasePtr, IsPHI)]; - if (!SAI) { - SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), Sizes, IsPHI, - this)); - } else { - if (Sizes.size() > SAI->getNumberOfDimensions()) - SAI->updateSizes(Sizes); - } + if (!SAI) + SAI.reset(new ScopArrayInfo(BasePtr, AccessType, getIslCtx(), IsPHI, this)); return SAI.get(); } @@ -3171,26 +3212,16 @@ return AnyCrossStmtUse; } -extern MapInsnToMemAcc InsnToMemAcc; - -void ScopInfo::buildMemoryAccess( - Instruction *Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops, - const InvariantLoadsSetTy &ScopRIL) { - unsigned Size; - Type *SizeType; +void ScopInfo::buildMemoryAccess(Instruction *Inst, Loop *L, Region *R, + const ScopDetection::DetectionContext *DC) { Value *Val; enum MemoryAccess::AccessType Type; if (LoadInst *Load = dyn_cast(Inst)) { - SizeType = Load->getType(); - Size = TD->getTypeStoreSize(SizeType); Type = MemoryAccess::READ; Val = Load; } else { StoreInst *Store = cast(Inst); - SizeType = Store->getValueOperand()->getType(); - Size = TD->getTypeStoreSize(SizeType); Type = MemoryAccess::MUST_WRITE; Val = Store->getValueOperand(); } @@ -3220,7 +3251,7 @@ std::tie(Subscripts, Sizes) = getIndexExpressionsFromGEP(GEP, *SE); auto BasePtr = GEP->getOperand(0); - std::vector SizesSCEV; + std::vector &SizesSCEV = AccessSizes[Inst]; bool AllAffineSubcripts = true; for (auto Subscript : Subscripts) { @@ -3229,7 +3260,7 @@ isAffineExpr(R, Subscript, *SE, nullptr, &AccessILS); for (LoadInst *LInst : AccessILS) - if (!ScopRIL.count(LInst)) + if (!DC->RequiredILS.count(LInst)) AllAffineSubcripts = false; if (!AllAffineSubcripts) @@ -3240,31 +3271,29 @@ for (auto V : Sizes) SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( IntegerType::getInt64Ty(BasePtr->getContext()), V))); - SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( - IntegerType::getInt64Ty(BasePtr->getContext()), Size))); - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true, - Subscripts, SizesSCEV, Val); + // TODO: Unify the delinearization. + addExplicitAccess(Inst, Type, BasePointer->getValue(), true, Subscripts, + Val); return; } } } - auto AccItr = InsnToMemAcc.find(Inst); - if (PollyDelinearize && AccItr != InsnToMemAcc.end()) { - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, true, - AccItr->second.DelinearizedSubscripts, - AccItr->second.Shape->DelinearizedSizes, Val); + auto AccItr = DC->InsnToMemAcc.find(Inst); + if (PollyDelinearize && AccItr != DC->InsnToMemAcc.end()) { + addExplicitAccess(Inst, Type, BasePointer->getValue(), true, + AccItr->second.DelinearizedSubscripts, Val); return; } // Check if the access depends on a loop contained in a non-affine subregion. bool isVariantInNonAffineLoop = false; - if (BoxedLoops) { + if (!DC->BoxedLoopsSet.empty()) { SetVector Loops; findLoops(AccessFunction, Loops); for (const Loop *L : Loops) - if (BoxedLoops->count(L)) + if (DC->BoxedLoopsSet.count(L)) isVariantInNonAffineLoop = true; } @@ -3274,20 +3303,14 @@ isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue(), &AccessILS); for (LoadInst *LInst : AccessILS) - if (!ScopRIL.count(LInst)) + if (!DC->RequiredILS.count(LInst)) IsAffine = false; - // FIXME: Size of the number of bytes of an array element, not the number of - // elements as probably intended here. - const SCEV *SizeSCEV = - SE->getConstant(TD->getIntPtrType(Inst->getContext()), Size); - if (!IsAffine && Type == MemoryAccess::MUST_WRITE) Type = MemoryAccess::MAY_WRITE; - addExplicitAccess(Inst, Type, BasePointer->getValue(), Size, IsAffine, - ArrayRef(AccessFunction), - ArrayRef(SizeSCEV), Val); + addExplicitAccess(Inst, Type, BasePointer->getValue(), IsAffine, + ArrayRef(AccessFunction), Val); } void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { @@ -3325,11 +3348,8 @@ bool IsExitBlock) { Loop *L = LI->getLoopFor(&BB); - // The set of loops contained in non-affine subregions that are part of R. - const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R); - - // The set of loads that are required to be invariant. - auto &ScopRIL = *SD->getRequiredInvariantLoads(&R); + // The detection context for @R + const ScopDetection::DetectionContext *DC = SD->getDetectionContext(&R); for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) { Instruction *Inst = I; @@ -3342,19 +3362,19 @@ if (!PHI && IsExitBlock) break; - // TODO: At this point we only know that elements of ScopRIL have to be - // invariant and will be hoisted for the SCoP to be processed. Though, - // there might be other invariant accesses that will be hoisted and - // that would allow to make a non-affine access affine. + // TODO: At this point we only know that elements of DC->RequiredILS have to + // be invariant and will be hoisted for the SCoP to be processed. + // Though,there might be other invariant accesses that will be hoisted + // and that would allow to make a non-affine access affine. if (isa(Inst) || isa(Inst)) - buildMemoryAccess(Inst, L, &R, BoxedLoops, ScopRIL); + buildMemoryAccess(Inst, L, &R, DC); if (isIgnoredIntrinsic(Inst)) continue; // Do not build scalar dependences for required invariant loads as we will // hoist them later on anyway or drop the SCoP if we cannot. - if (ScopRIL.count(dyn_cast(Inst))) + if (DC->RequiredILS.count(dyn_cast(Inst))) continue; if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { @@ -3366,10 +3386,9 @@ void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, - Value *BaseAddress, unsigned ElemBytes, - bool Affine, Value *AccessValue, + Value *BaseAddress, bool Affine, + Value *AccessValue, ArrayRef Subscripts, - ArrayRef Sizes, MemoryAccess::AccessOrigin Origin) { ScopStmt *Stmt = scop->getStmtForBasicBlock(BB); @@ -3392,49 +3411,45 @@ if (isApproximated && Type == MemoryAccess::MUST_WRITE) Type = MemoryAccess::MAY_WRITE; - AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, ElemBytes, Affine, - Subscripts, Sizes, AccessValue, Origin, BaseName); + AccList.emplace_back(Stmt, Inst, Id, Type, BaseAddress, Affine, Subscripts, + AccessValue, Origin, BaseName); Stmt->addAccess(&AccList.back()); } -void ScopInfo::addExplicitAccess( - Instruction *MemAccInst, MemoryAccess::AccessType Type, Value *BaseAddress, - unsigned ElemBytes, bool IsAffine, ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue) { +void ScopInfo::addExplicitAccess(Instruction *MemAccInst, + MemoryAccess::AccessType Type, + Value *BaseAddress, bool IsAffine, + ArrayRef Subscripts, + Value *AccessValue) { assert(isa(MemAccInst) || isa(MemAccInst)); assert(isa(MemAccInst) == (Type == MemoryAccess::READ)); addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress, - ElemBytes, IsAffine, AccessValue, Subscripts, Sizes, - MemoryAccess::EXPLICIT); + IsAffine, AccessValue, Subscripts, MemoryAccess::EXPLICIT); } void ScopInfo::addScalarWriteAccess(Instruction *Value) { - addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1, - true, Value, ArrayRef(), - ArrayRef(), MemoryAccess::SCALAR); + addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, + true, Value, ArrayRef(), MemoryAccess::SCALAR); } void ScopInfo::addScalarReadAccess(Value *Value, Instruction *User) { assert(!isa(User)); - addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true, - Value, ArrayRef(), ArrayRef(), - MemoryAccess::SCALAR); + addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, true, + Value, ArrayRef(), MemoryAccess::SCALAR); } void ScopInfo::addScalarReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB) { - addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value, - ArrayRef(), ArrayRef(), - MemoryAccess::SCALAR); + addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, true, Value, + ArrayRef(), MemoryAccess::SCALAR); } void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock, Value *IncomingValue, bool IsExitBlock) { addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(), - MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue, - ArrayRef(), ArrayRef(), + MemoryAccess::MUST_WRITE, PHI, true, IncomingValue, + ArrayRef(), IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI); } void ScopInfo::addPHIReadAccess(PHINode *PHI) { - addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI, - ArrayRef(), ArrayRef(), - MemoryAccess::PHI); + addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, true, PHI, + ArrayRef(), MemoryAccess::PHI); } void ScopInfo::buildScop(Region &R, DominatorTree &DT) { @@ -3454,7 +3469,7 @@ if (!R.getExitingBlock()) buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true); - scop->init(*AA); + scop->init(*AA, AccessSizes); } void ScopInfo::print(raw_ostream &OS, const Module *) const { @@ -3468,6 +3483,7 @@ void ScopInfo::clear() { AccFuncMap.clear(); + AccessSizes.clear(); if (scop) { delete scop; scop = 0; Index: test/ScopDetect/cross_loop_non_single_exit.ll =================================================================== --- test/ScopDetect/cross_loop_non_single_exit.ll +++ test/ScopDetect/cross_loop_non_single_exit.ll @@ -44,5 +44,5 @@ ret void } -; CHECK: Valid Region for Scop: next => return -; CHECK: Valid Region for Scop: next2 => return +; CHECK-DAG: Valid Region for Scop: next => return +; CHECK-DAG: Valid Region for Scop: next2 => return Index: test/ScopInfo/delinearize-together-all-data-refs.ll =================================================================== --- test/ScopInfo/delinearize-together-all-data-refs.ll +++ test/ScopInfo/delinearize-together-all-data-refs.ll @@ -11,7 +11,7 @@ ; CHECK: Arrays { -; CHECK: double MemRef_A[*][%m][%o][8] // Element size 8 +; CHECK: double MemRef_A[*][%m][%o] // Element size 8 ; CHECK: } ; CHECK: [m, o, n] -> { Stmt_for_body6[i0, i1, i2] -> MemRef_A[3 + i0, i1, 7 + i2] }; Index: test/ScopInfo/invariant_load_ptr_ptr_noalias.ll =================================================================== --- test/ScopInfo/invariant_load_ptr_ptr_noalias.ll +++ test/ScopInfo/invariant_load_ptr_ptr_noalias.ll @@ -13,15 +13,15 @@ ; CHECK: } ; ; CHECK: Arrays { -; CHECK: i32** MemRef_A[*][8] -; CHECK: i32* MemRef_tmp3[*][8] [BasePtrOrigin: MemRef_A] -; CHECK: i32 MemRef_tmp5[*][4] [BasePtrOrigin: MemRef_tmp3] +; CHECK: i32** MemRef_A[*] +; CHECK: i32* MemRef_tmp3[*] [BasePtrOrigin: MemRef_A] +; CHECK: i32 MemRef_tmp5[*] [BasePtrOrigin: MemRef_tmp3] ; CHECK: } ; ; CHECK: Arrays (Bounds as pw_affs) { -; CHECK: i32** MemRef_A[*][ { [] -> [(8)] } ] -; CHECK: i32* MemRef_tmp3[*][ { [] -> [(8)] } ] [BasePtrOrigin: MemRef_A] -; CHECK: i32 MemRef_tmp5[*][ { [] -> [(4)] } ] [BasePtrOrigin: MemRef_tmp3] +; CHECK: i32** MemRef_A[*] +; CHECK: i32* MemRef_tmp3[*] [BasePtrOrigin: MemRef_A] +; CHECK: i32 MemRef_tmp5[*] [BasePtrOrigin: MemRef_tmp3] ; CHECK: } ; ; void f(int ***A) { Index: test/ScopInfo/multi-scop.ll =================================================================== --- test/ScopInfo/multi-scop.ll +++ test/ScopInfo/multi-scop.ll @@ -32,6 +32,6 @@ ret void } -; CHECK: Valid Region for Scop: entry.split => for.end -; CHECK: Valid Region for Scop: for.body81 => for.end170 +; CHECK-DAG: Valid Region for Scop: entry.split => for.end +; CHECK-DAG: Valid Region for Scop: for.body81 => for.end170 Index: test/ScopInfo/multidim_only_ivs_3d_cast.ll =================================================================== --- test/ScopInfo/multidim_only_ivs_3d_cast.ll +++ test/ScopInfo/multidim_only_ivs_3d_cast.ll @@ -25,10 +25,10 @@ ; CHECK-NOT: p5 ; CHECK: Arrays { -; CHECK: double MemRef_A[*][(zext i32 %m to i64)][(zext i32 %o to i64)][8] // Element size 8 +; CHECK: double MemRef_A[*][(zext i32 %m to i64)][(zext i32 %o to i64)] // Element size 8 ; CHECK: } ; CHECK: Arrays (Bounds as pw_affs) { -; CHECK: double MemRef_A[*][ [p_3] -> { [] -> [(p_3)] } ][ [p_4] -> { [] -> [(p_4)] } ][ { [] -> [(8)] } ] // Element size 8 +; CHECK: double MemRef_A[*][ [p_3] -> { [] -> [(p_3)] } ][ [p_4] -> { [] -> [(p_4)] } ] // Element size 8 ; CHECK: } Index: test/ScopInfo/non_affine_region_4.ll =================================================================== --- test/ScopInfo/non_affine_region_4.ll +++ test/ScopInfo/non_affine_region_4.ll @@ -15,13 +15,13 @@ ; CHECK: Region: %bb1---%bb11 ; ; CHECK: Arrays { -; CHECK: i32 MemRef_A[*][4] +; CHECK: i32 MemRef_A[*] ; CHECK: i32 MemRef_x[*] [BasePtrOrigin: MemRef_A] ; CHECK: i32 MemRef_y__phi[*] ; CHECK: } ; ; CHECK: Arrays (Bounds as pw_affs) { -; CHECK: i32 MemRef_A[*][ { [] -> [(4)] } ] +; CHECK: i32 MemRef_A[*] ; CHECK: i32 MemRef_x[*] [BasePtrOrigin: MemRef_A] ; CHECK: i32 MemRef_y__phi[*] ; CHECK: } Index: test/ScopInfo/scalar.ll =================================================================== --- test/ScopInfo/scalar.ll +++ test/ScopInfo/scalar.ll @@ -30,12 +30,12 @@ } ; CHECK: Arrays { -; CHECK: i64 MemRef_a[*][8] +; CHECK: i64 MemRef_a[*] ; CHECK: i64 MemRef_val[*] [BasePtrOrigin: MemRef_a] ; CHECK: } ; ; CHECK: Arrays (Bounds as pw_affs) { -; CHECK: i64 MemRef_a[*][ { [] -> [(8)] } ] +; CHECK: i64 MemRef_a[*] ; CHECK: i64 MemRef_val[*] [BasePtrOrigin: MemRef_a] ; CHECK: } Index: test/ScopInfo/simple_loop_1.ll =================================================================== --- test/ScopInfo/simple_loop_1.ll +++ test/ScopInfo/simple_loop_1.ll @@ -27,7 +27,7 @@ ; CHECK: Assumed Context: ; CHECK: { : } ; CHECK: Arrays { -; CHECK: i64 MemRef_a[*][8] // Element size 8 +; CHECK: i64 MemRef_a[*] // Element size 8 ; CHECK: } ; CHECK: Stmt_bb