Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -59,7 +59,7 @@ namespace polly { -class IRAccess; +class MemoryAccess; class Scop; class ScopStmt; class ScopInfo; @@ -93,7 +93,7 @@ /// through the loop. typedef std::map LoopBoundMapType; -typedef std::vector> AccFuncSetType; +typedef std::deque AccFuncSetType; typedef std::map AccFuncMapType; /// @brief A class to store information about arrays in the SCoP. @@ -212,81 +212,11 @@ bool IsPHI; }; -//===---------------------------------------------------------------------===// -/// @brief A memory access described by a SCEV expression and the access type. -class IRAccess { -public: - Value *BaseAddress; - Value *AccessValue; - - const SCEV *Offset; - - // The type of the scev affine function - enum TypeKind { - READ = 0x1, - MUST_WRITE = 0x2, - MAY_WRITE = 0x3, - }; - -private: - unsigned ElemBytes; - TypeKind Type; - bool IsAffine; - - /// @brief Is this IRAccess modeling special PHI node accesses? - bool IsPHI; - -public: - SmallVector Subscripts, Sizes; - - /// @brief Create a new IRAccess - /// - /// @param IsPHI Are we modeling special PHI node accesses? - explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, - unsigned elemBytes, bool Affine, Value *AccessValue, - bool IsPHI = false) - : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), - ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {} - - explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset, - unsigned elemBytes, bool Affine, - ArrayRef Subscripts, - ArrayRef Sizes, Value *AccessValue) - : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset), - ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false), - Subscripts(Subscripts.begin(), Subscripts.end()), - Sizes(Sizes.begin(), Sizes.end()) {} - - enum TypeKind getType() const { return Type; } - - Value *getBase() const { return BaseAddress; } - - Value *getAccessValue() const { return AccessValue; } - - const SCEV *getOffset() const { return Offset; } - - unsigned getElemSizeInBytes() const { return ElemBytes; } - - bool isAffine() const { return IsAffine; } - - bool isRead() const { return Type == READ; } - - bool isWrite() const { return Type == MUST_WRITE; } - - void setMayWrite() { Type = MAY_WRITE; } - - bool isMayWrite() const { return Type == MAY_WRITE; } - - bool isScalar() const { return Subscripts.size() == 0; } - - // @brief Is this IRAccess modeling special PHI node accesses? - bool isPHI() const { return IsPHI; } - - void print(raw_ostream &OS) const; -}; - /// @brief Represent memory accesses in statements. class MemoryAccess { + friend class Scop; + friend class ScopStmt; + public: /// @brief The access type of a memory access /// @@ -308,7 +238,11 @@ /// A certain set of memory locations may be written. The memory location may /// contain a new value if there is actually a write or the old value may /// remain, if no write happens. - enum AccessType { READ, MUST_WRITE, MAY_WRITE }; + enum AccessType { + READ = 0x1, + MUST_WRITE = 0x2, + MAY_WRITE = 0x3, + }; /// @brief Reduction access type /// @@ -326,15 +260,18 @@ MemoryAccess(const MemoryAccess &) = delete; const MemoryAccess &operator=(const MemoryAccess &) = delete; - isl_map *AccessRelation; - enum AccessType AccType; + /// @brief A unique identifier for this memory access. + /// + /// The identifier is unique between all memory accesses belonging to the same + /// scop statement. + isl_id *Id; - /// @brief The base address (e.g., A for A[i+j]). - Value *BaseAddr; + /// @brief Is this MemoryAccess modeling special PHI node accesses? + bool IsPHI; - std::string BaseName; - __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement); - ScopStmt *Statement; + /// @brief Whether it a reading or writing access, and if writing, whether it + /// is conditional (MAY_WRITE). + enum AccessType AccType; /// @brief Reduction type for reduction like accesses, RT_NONE otherwise /// @@ -362,6 +299,29 @@ /// could allow us to handle the above example. ReductionType RedType = RT_NONE; + /// @brief Parent ScopStmt of this access. + ScopStmt *Statement; + + // Properties describing the accessed array. + // TODO: It might be possible to move them to ScopArrayInfo. + // @{ + + /// @brief The base address (e.g., A for A[i+j]). + Value *BaseAddr; + + /// @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. + // @{ + /// @brief The access instruction of this memory access. Instruction *AccessInstruction; @@ -373,16 +333,38 @@ /// Value *AccessValue; - /// Updated access relation read from JSCOP file. + /// @brief Accessed element relative to the base pointer (in bytes). + /// + /// Currently only used by printIR. + const SCEV *Offset; + + /// @brief Are all the subscripts affine expression? + bool IsAffine; + + /// @brief Subscript expression for each dimension. + SmallVector Subscripts; + + /// @brief Relation from statment instances to the accessed array elements. + isl_map *AccessRelation; + + /// @brief Updated access relation read from JSCOP file. isl_map *NewAccessRelation; + // @} - /// @brief A unique identifier for this memory access. - /// - /// The identifier is unique between all memory accesses belonging to the same - /// scop statement. - isl_id *Id; + unsigned getElemSizeInBytes() const { return ElemBytes; } + + bool isAffine() const { return IsAffine; } + + /// @brief Is this MemoryAccess modeling special PHI node accesses? + bool isPHI() const { return IsPHI; } - void assumeNoOutOfBound(const IRAccess &Access); + void printIR(raw_ostream &OS) const; + + void setStatement(ScopStmt *Stmt) { this->Statement = Stmt; } + + __isl_give isl_basic_map *createBasicAccessMap(ScopStmt *Statement); + + void assumeNoOutOfBound(); /// @brief Compute bounds on an over approximated access relation. /// @@ -426,22 +408,37 @@ /// The introduction of different cases necessarily complicates the memory /// access function, but cases that can be statically proven to not happen /// will be eliminated later on. - __isl_give isl_map *foldAccess(const IRAccess &Access, - __isl_take isl_map *AccessRelation, + __isl_give isl_map *foldAccess(__isl_take isl_map *AccessRelation, ScopStmt *Statement); -public: - /// @brief Create a memory access from an access in LLVM-IR. + /// @brief Assemble the access relation from all availbale information. + /// + /// In particular, used the information passes in the constructor and the + /// parent ScopStmt set by setStatment(). /// - /// @param Access The memory access. - /// @param AccInst The access instruction. - /// @param Statement The statement that contains the access. - /// @param SAI The ScopArrayInfo object for this base pointer. - /// @param Identifier An identifier that is unique for all memory accesses - /// belonging to the same scop statement. - MemoryAccess(const IRAccess &Access, Instruction *AccInst, - ScopStmt *Statement, const ScopArrayInfo *SAI, int Identifier); + /// @param SAI Info object for the accessed array. + void buildAccessRelation(const ScopArrayInfo *SAI); +public: + /// @brief Create a new MemoryAccess. + /// + /// @param AccessInst The instruction doing the access. + /// @param Id Identifier that is guranteed to be unique within the + /// same ScopStmt. + /// @param BaseAddr The accessed array's address. + /// @param Offset Accessed memoray location relative to @p BaseAddr. + /// @param ElemBytes Number of accessed bytes. + /// @param AccType Whether read or write access. + /// @param IsAffine Whether the subscripts are affine expressions. + /// @param IsPHI Are we modeling special PHI node accesses? + /// @param Subscripts Subscipt expressions + /// @param Sizes Dimension lengths of the accessed array. + /// @param BaseName Name of the acessed array. + MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, AccessType Type, + Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes, + bool Affine, ArrayRef Subscripts, + ArrayRef Sizes, Value *AccessValue, bool IsPHI, + StringRef BaseName); ~MemoryAccess(); /// @brief Get the type of a memory access. @@ -582,7 +579,7 @@ class ScopStmt { public: /// @brief List to hold all (scalar) memory accesses mapped to an instruction. - using MemoryAccessList = std::forward_list; + using MemoryAccessList = std::forward_list; ScopStmt(const ScopStmt &) = delete; const ScopStmt &operator=(const ScopStmt &) = delete; @@ -784,8 +781,7 @@ /// @brief Return the __first__ (scalar) memory access for @p Inst if any. MemoryAccess *lookupAccessFor(const Instruction *Inst) const { auto It = InstructionToAccess.find(Inst); - return It == InstructionToAccess.end() ? nullptr - : &It->getSecond()->front(); + return It == InstructionToAccess.end() ? nullptr : It->getSecond()->front(); } void setBasicBlock(BasicBlock *Block) { @@ -1437,6 +1433,9 @@ const DataLayout *TD; // Access function of statements (currently BasicBlocks) . + // + // This owns all the MemoryAccess objects of the Scop created in this pass. It + // must live until #scop is deleted. AccFuncMapType AccFuncMap; // Pre-created zero for the scalar accesses, with it we do not need create a @@ -1453,16 +1452,13 @@ // Build the SCoP for Region @p R. Scop *buildScop(Region &R, DominatorTree &DT); - /// @brief Build an instance of IRAccess from the Load/Store instruction. + /// @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. - /// - /// @return The IRAccess to describe the access function of the - /// instruction. - IRAccess buildIRAccess(Instruction *Inst, Loop *L, Region *R, + void buildMemoryAccess(Instruction *Inst, Loop *L, Region *R, const ScopDetection::BoxedLoopsSetTy *BoxedLoops); /// @brief Analyze and extract the cross-BB scalar dependences (or, @@ -1477,15 +1473,14 @@ bool buildScalarDependences(Instruction *Inst, Region *R, Region *NonAffineSubRegio); - /// @brief Create IRAccesses for the given PHI node in the given region. + /// @brief Create MemoryAccesses for the given PHI node in the given region. /// /// @param PHI The PHI node to be handled /// @param R The SCoP region - /// @param Functions The access functions of the current BB /// @param NonAffineSubRegion The non affine sub-region @p PHI is in. /// @param IsExitBlock Flag to indicate that @p PHI is in the exit BB. - void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions, - Region *NonAffineSubRegion, bool IsExitBlock = false); + void buildPHIAccesses(PHINode *PHI, Region &R, Region *NonAffineSubRegion, + bool IsExitBlock = false); /// @brief Build the access functions for the subregion @p SR. /// @@ -1503,6 +1498,44 @@ Region *NonAffineSubRegion = nullptr, bool IsExitBlock = false); + /// @brief Create a new MemoryAccess object and add it to #AccFuncMap. + /// + /// @param BB The block where the access takes place. + /// @param Inst The instruction doing the access. It is not necessarily + /// inside @p BB. + /// @param Type The kind of access. + /// @param BaseAddress The accessed array's base address. + /// @param Offset Accessed location relative to @p BaseAddress. + /// @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 IsPHI Whether this is an emulated PHI node. + void addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, Value *BaseAddress, + const SCEV *Offset, unsigned ElemBytes, bool Affine, + Value *AccessValue, ArrayRef Subscripts, + ArrayRef Sizes, bool IsPHI); + + void addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, Value *BaseAddress, + const SCEV *Offset, unsigned ElemBytes, bool Affine, + Value *AccessValue, bool IsPHI = false) { + addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine, + AccessValue, ArrayRef(), + ArrayRef(), IsPHI); + } + + void addMemoryAccess(BasicBlock *BB, Instruction *Inst, + MemoryAccess::AccessType Type, Value *BaseAddress, + const SCEV *Offset, unsigned ElemBytes, bool Affine, + ArrayRef Subscripts, + ArrayRef Sizes, Value *AccessValue) { + addMemoryAccess(BB, Inst, Type, BaseAddress, Offset, ElemBytes, Affine, + AccessValue, Subscripts, Sizes, false); + } + public: static char ID; explicit ScopInfo(); Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -227,7 +227,7 @@ return SAI; } -void IRAccess::print(raw_ostream &OS) const { +void MemoryAccess::printIR(raw_ostream &OS) const { if (isRead()) OS << "Read "; else { @@ -235,7 +235,7 @@ OS << "May"; OS << "Write "; } - OS << BaseAddress->getName() << '[' << *Offset << "]\n"; + OS << BaseAddr->getName() << '[' << *Offset << "]\n"; } const std::string @@ -290,8 +290,6 @@ } } -//===----------------------------------------------------------------------===// - /// @brief Derive the individual index expressions from a GEP instruction /// /// This function optimistically assumes the GEP references into a fixed size @@ -359,18 +357,6 @@ isl_map_free(NewAccessRelation); } -static MemoryAccess::AccessType getMemoryAccessType(const IRAccess &Access) { - switch (Access.getType()) { - case IRAccess::READ: - return MemoryAccess::READ; - case IRAccess::MUST_WRITE: - return MemoryAccess::MUST_WRITE; - case IRAccess::MAY_WRITE: - return MemoryAccess::MAY_WRITE; - } - llvm_unreachable("Unknown IRAccess type!"); -} - const ScopArrayInfo *MemoryAccess::getScopArrayInfo() const { isl_id *ArrayId = getArrayId(); void *User = isl_id_get_user(ArrayId); @@ -446,10 +432,10 @@ // 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(const IRAccess &Access) { +void MemoryAccess::assumeNoOutOfBound() { isl_space *Space = isl_space_range(getOriginalAccessRelationSpace()); isl_set *Outside = isl_set_empty(isl_space_copy(Space)); - for (int i = 1, Size = Access.Subscripts.size(); i < Size; ++i) { + for (int i = 1, Size = Subscripts.size(); i < Size; ++i) { isl_local_space *LS = isl_local_space_from_space(isl_space_copy(Space)); isl_pw_aff *Var = isl_pw_aff_var_on_domain(isl_local_space_copy(LS), isl_dim_set, i); @@ -458,7 +444,7 @@ isl_set *DimOutside; DimOutside = isl_pw_aff_lt_set(isl_pw_aff_copy(Var), Zero); - isl_pw_aff *SizeE = Statement->getPwAff(Access.Sizes[i - 1]); + isl_pw_aff *SizeE = Statement->getPwAff(Sizes[i - 1]); SizeE = isl_pw_aff_drop_dims(SizeE, isl_dim_in, 0, Statement->getNumIterators()); @@ -519,15 +505,14 @@ AccessRelation = isl_map_intersect_range(AccessRelation, AccessRange); } -__isl_give isl_map *MemoryAccess::foldAccess(const IRAccess &Access, - __isl_take isl_map *AccessRelation, +__isl_give isl_map *MemoryAccess::foldAccess(__isl_take isl_map *AccessRelation, ScopStmt *Statement) { - int Size = Access.Subscripts.size(); + 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(Access.Sizes[i]); + isl_pw_aff *DimSize = Statement->getPwAff(Sizes[i]); isl_space *SpaceSize = isl_pw_aff_get_space(DimSize); isl_pw_aff_free(DimSize); @@ -570,23 +555,13 @@ return AccessRelation; } -MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst, - ScopStmt *Statement, const ScopArrayInfo *SAI, - int Identifier) - : AccType(getMemoryAccessType(Access)), Statement(Statement), - AccessInstruction(AccInst), AccessValue(Access.getAccessValue()), - NewAccessRelation(nullptr) { - - isl_ctx *Ctx = Statement->getIslCtx(); - BaseAddr = Access.getBase(); - BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), ""); +void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) { + assert(!AccessRelation && "AccessReltation already built"); + isl_ctx *Ctx = isl_id_get_ctx(Id); isl_id *BaseAddrId = SAI->getBasePtrId(); - auto IdName = "__polly_array_ref_" + std::to_string(Identifier); - Id = isl_id_alloc(Ctx, IdName.c_str(), nullptr); - - if (!Access.isAffine()) { + if (!isAffine()) { // We overapproximate non-affine accesses with a possible access to the // whole array. For read accesses it does not make a difference, if an // access must or may happen. However, for write accesses it is important to @@ -595,15 +570,15 @@ AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); - computeBoundsOnAccessRelation(Access.getElemSizeInBytes()); + computeBoundsOnAccessRelation(getElemSizeInBytes()); return; } isl_space *Space = isl_space_alloc(Ctx, 0, Statement->getNumIterators(), 0); AccessRelation = isl_map_universe(Space); - for (int i = 0, Size = Access.Subscripts.size(); i < Size; ++i) { - isl_pw_aff *Affine = Statement->getPwAff(Access.Subscripts[i]); + for (int i = 0, Size = Subscripts.size(); i < Size; ++i) { + isl_pw_aff *Affine = Statement->getPwAff(Subscripts[i]); if (Size == 1) { // For the non delinearized arrays, divide the access function of the last @@ -614,7 +589,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, Access.getElemSizeInBytes()); + isl_val *v = isl_val_int_from_si(Ctx, getElemSizeInBytes()); Affine = isl_pw_aff_scale_down_val(Affine, v); } @@ -623,8 +598,8 @@ AccessRelation = isl_map_flat_range_product(AccessRelation, SubscriptMap); } - if (Access.Sizes.size() > 1 && !isa(Access.Sizes[0])) - AccessRelation = foldAccess(Access, AccessRelation, Statement); + if (Sizes.size() > 1 && !isa(Sizes[0])) + AccessRelation = foldAccess(AccessRelation, Statement); Space = Statement->getDomainSpace(); AccessRelation = isl_map_set_tuple_id( @@ -632,11 +607,24 @@ AccessRelation = isl_map_set_tuple_id(AccessRelation, isl_dim_out, BaseAddrId); - assumeNoOutOfBound(Access); + assumeNoOutOfBound(); AccessRelation = isl_map_gist_domain(AccessRelation, Statement->getDomain()); isl_space_free(Space); } +MemoryAccess::MemoryAccess(Instruction *AccessInst, __isl_take isl_id *Id, + AccessType Type, Value *BaseAddress, + const SCEV *Offset, unsigned ElemBytes, bool Affine, + ArrayRef Subscripts, + ArrayRef Sizes, Value *AccessValue, + bool IsPHI, StringRef BaseName) + : Id(Id), IsPHI(IsPHI), AccType(Type), RedType(RT_NONE), Statement(nullptr), + BaseAddr(BaseAddress), BaseName(BaseName), ElemBytes(ElemBytes), + Sizes(Sizes.begin(), Sizes.end()), AccessInstruction(AccessInst), + AccessValue(AccessValue), Offset(Offset), IsAffine(Affine), + Subscripts(Subscripts.begin(), Subscripts.end()), AccessRelation(nullptr), + NewAccessRelation(nullptr) {} + void MemoryAccess::realignParams() { isl_space *ParamSpace = Statement->getParent()->getParamSpace(); AccessRelation = isl_map_align_params(AccessRelation, ParamSpace); @@ -808,22 +796,23 @@ if (!AFS) return; - for (auto &AccessPair : *AFS) { - IRAccess &Access = AccessPair.first; - Instruction *AccessInst = AccessPair.second; + for (auto &Access : *AFS) { + Instruction *AccessInst = Access.getAccessInstruction(); Type *ElementType = Access.getAccessValue()->getType(); const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo( - Access.getBase(), ElementType, Access.Sizes, Access.isPHI()); + Access.getBaseAddr(), ElementType, Access.Sizes, Access.isPHI()); - if (isApproximated && Access.isWrite()) - Access.setMayWrite(); + if (isApproximated && Access.isMustWrite()) + Access.AccType = MemoryAccess::MAY_WRITE; MemoryAccessList *&MAL = InstructionToAccess[AccessInst]; if (!MAL) MAL = new MemoryAccessList(); - MAL->emplace_front(Access, AccessInst, this, SAI, MemAccs.size()); - MemAccs.push_back(&MAL->front()); + Access.setStatement(this); + Access.buildAccessRelation(SAI); + MAL->emplace_front(&Access); + MemAccs.push_back(MAL->front()); } } @@ -2741,7 +2730,7 @@ for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE; ++AI) - AI->first.print(OS.indent(ind + 2)); + AI->printIR(OS.indent(ind + 2)); } } @@ -2754,7 +2743,6 @@ } void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R, - AccFuncSetType &Functions, Region *NonAffineSubRegion, bool IsExitBlock) { // PHI nodes that are in the exit block of the region, hence if IsExitBlock is @@ -2792,11 +2780,10 @@ // we have to insert a scalar dependence from the definition of OpI to // OpBB if the definition is not in OpBB. if (OpIBB != OpBB) { - IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI); - AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI)); - IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true, - OpI); - AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI)); + addMemoryAccess(OpBB, PHI, MemoryAccess::READ, OpI, ZeroOffset, 1, true, + OpI); + addMemoryAccess(OpIBB, OpI, MemoryAccess::MUST_WRITE, OpI, ZeroOffset, + 1, true, OpI); } } @@ -2804,15 +2791,14 @@ // instruction. OpI = OpBB->getTerminator(); - IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op, - /* IsPHI */ !IsExitBlock); - AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI)); + addMemoryAccess(OpBB, OpI, MemoryAccess::MUST_WRITE, PHI, ZeroOffset, 1, + true, Op, /* IsPHI */ !IsExitBlock); } if (!OnlyNonAffineSubRegionOperands) { - IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI, - /* IsPHI */ !IsExitBlock); - Functions.push_back(std::make_pair(ScalarAccess, PHI)); + addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, ZeroOffset, + 1, true, PHI, + /* IsPHI */ !IsExitBlock); } } @@ -2866,10 +2852,10 @@ AnyCrossStmtUse = true; // Do not build a read access that is not in the current SCoP - // Use the def instruction as base address of the IRAccess, so that it will - // become the name of the scalar access in the polyhedral form. - IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst); - AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI)); + // Use the def instruction as base address of the MemoryAccess, so that it + // will become the name of the scalar access in the polyhedral form. + addMemoryAccess(UseParent, UI, MemoryAccess::READ, Inst, ZeroOffset, 1, + true, Inst); } if (ModelReadOnlyScalars) { @@ -2884,9 +2870,8 @@ if (isa(Op)) continue; - IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op); - AccFuncMap[Inst->getParent()].push_back( - std::make_pair(ScalarAccess, Inst)); + addMemoryAccess(Inst->getParent(), Inst, MemoryAccess::READ, Op, + ZeroOffset, 1, true, Op); } } @@ -2895,24 +2880,24 @@ extern MapInsnToMemAcc InsnToMemAcc; -IRAccess -ScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R, - const ScopDetection::BoxedLoopsSetTy *BoxedLoops) { +void ScopInfo::buildMemoryAccess( + Instruction *Inst, Loop *L, Region *R, + const ScopDetection::BoxedLoopsSetTy *BoxedLoops) { unsigned Size; Type *SizeType; Value *Val; - enum IRAccess::TypeKind Type; + enum MemoryAccess::AccessType Type; if (LoadInst *Load = dyn_cast(Inst)) { SizeType = Load->getType(); Size = TD->getTypeStoreSize(SizeType); - Type = IRAccess::READ; + Type = MemoryAccess::READ; Val = Load; } else { StoreInst *Store = cast(Inst); SizeType = Store->getValueOperand()->getType(); Size = TD->getTypeStoreSize(SizeType); - Type = IRAccess::MUST_WRITE; + Type = MemoryAccess::MUST_WRITE; Val = Store->getValueOperand(); } @@ -2957,17 +2942,20 @@ SizesSCEV.push_back(SE->getSCEV(ConstantInt::get( IntegerType::getInt64Ty(BasePtr->getContext()), Size))); - return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, - true, Subscripts, SizesSCEV, Val); + addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), + AccessFunction, Size, true, Subscripts, SizesSCEV, Val); } } } auto AccItr = InsnToMemAcc.find(Inst); - if (PollyDelinearize && AccItr != InsnToMemAcc.end()) - return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true, + if (PollyDelinearize && AccItr != InsnToMemAcc.end()) { + addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), + AccessFunction, Size, true, AccItr->second.DelinearizedSubscripts, AccItr->second.Shape->DelinearizedSizes, Val); + return; + } // Check if the access depends on a loop contained in a non-affine subregion. bool isVariantInNonAffineLoop = false; @@ -2986,11 +2974,11 @@ Subscripts.push_back(AccessFunction); Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size)); - if (!IsAffine && Type == IRAccess::MUST_WRITE) - Type = IRAccess::MAY_WRITE; + if (!IsAffine && Type == MemoryAccess::MUST_WRITE) + Type = MemoryAccess::MAY_WRITE; - return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine, - Subscripts, Sizes, Val); + addMemoryAccess(Inst->getParent(), Inst, Type, BasePointer->getValue(), + AccessFunction, Size, IsAffine, Subscripts, Sizes, Val); } void ScopInfo::buildAccessFunctions(Region &R, Region &SR) { @@ -3011,7 +2999,6 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB, Region *NonAffineSubRegion, bool IsExitBlock) { - AccFuncSetType Functions; Loop *L = LI->getLoopFor(&BB); // The set of loops contained in non-affine subregions that are part of R. @@ -3022,35 +3009,42 @@ PHINode *PHI = dyn_cast(Inst); if (PHI) - buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock); + buildPHIAccesses(PHI, R, NonAffineSubRegion, IsExitBlock); // For the exit block we stop modeling after the last PHI node. if (!PHI && IsExitBlock) break; if (isa(Inst) || isa(Inst)) - Functions.push_back( - std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst)); + buildMemoryAccess(Inst, L, &R, BoxedLoops); if (isIgnoredIntrinsic(Inst)) continue; if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) { - // If the Instruction is used outside the statement, we need to build the - // write access. - if (!isa(Inst)) { - IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true, - Inst); - Functions.push_back(std::make_pair(ScalarAccess, Inst)); - } + if (!isa(Inst)) + addMemoryAccess(&BB, Inst, MemoryAccess::MUST_WRITE, Inst, ZeroOffset, + 1, true, Inst); } } +} - if (Functions.empty()) - return; +void ScopInfo::addMemoryAccess( + BasicBlock *BB, Instruction *Inst, MemoryAccess::AccessType Type, + Value *BaseAddress, const SCEV *Offset, unsigned ElemBytes, bool Affine, + Value *AccessValue, ArrayRef Subscripts, + ArrayRef Sizes, bool IsPHI = false) { + AccFuncSetType &AccList = AccFuncMap[BB]; + size_t Identifier = AccList.size(); + + Value *BaseAddr = BaseAddress; + std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, ""); + + std::string IdName = "__polly_array_ref_" + std::to_string(Identifier); + isl_id *Id = isl_id_alloc(ctx, IdName.c_str(), nullptr); - AccFuncSetType &Accs = AccFuncMap[&BB]; - Accs.insert(Accs.end(), Functions.begin(), Functions.end()); + AccList.emplace_back(Inst, Id, Type, BaseAddress, Offset, ElemBytes, Affine, + Subscripts, Sizes, AccessValue, IsPHI, BaseName); } Scop *ScopInfo::buildScop(Region &R, DominatorTree &DT) { Index: lib/CodeGen/BlockGenerators.cpp =================================================================== --- lib/CodeGen/BlockGenerators.cpp +++ lib/CodeGen/BlockGenerators.cpp @@ -406,12 +406,12 @@ if (!MAL) return; - for (MemoryAccess &MA : *MAL) { - if (!MA.isScalar() || !MA.isRead()) + for (MemoryAccess *MA : *MAL) { + if (!MA->isScalar() || !MA->isRead()) continue; - auto *Address = getOrCreateAlloca(MA); - BBMap[MA.getBaseAddr()] = + auto *Address = getOrCreateAlloca(*MA); + BBMap[MA->getBaseAddr()] = Builder.CreateLoad(Address, Address->getName() + ".reload"); } } Index: test/DependenceInfo/do_pluto_matmult.ll =================================================================== --- test/DependenceInfo/do_pluto_matmult.ll +++ test/DependenceInfo/do_pluto_matmult.ll @@ -73,8 +73,8 @@ ; MEMORY: RAW dependences: -; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 } +; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 } ; MEMORY: WAR dependences: -; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 } +; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 } ; MEMORY: WAW dependences: -; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 and o2 >= 0 } +; MEMORY: { Stmt_do_body2[i0, i1, i2] -> Stmt_do_body2[i0, i1, o2] : i0 <= 35 and i0 >= 0 and i1 <= 35 and i1 >= 0 and i2 >= 0 and o2 >= 1 + i2 and o2 <= 35 } Index: test/ScopInfo/loop_carry.ll =================================================================== --- test/ScopInfo/loop_carry.ll +++ test/ScopInfo/loop_carry.ll @@ -53,10 +53,10 @@ ; CHECK: [n] -> { Stmt_bb[i0] -> [i0] }; ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK: [n] -> { Stmt_bb[i0] -> MemRef_1__phi[] }; -; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] -; CHECK: [n] -> { Stmt_bb[i0] -> MemRef_k_05__phi[] }; ; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK: [n] -> { Stmt_bb[i0] -> MemRef_1__phi[] }; +; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1] +; CHECK: [n] -> { Stmt_bb[i0] -> MemRef_k_05__phi[] }; ; CHECK: ReadAccess := [Reduction Type: NONE] [Scalar: 1] ; CHECK: [n] -> { Stmt_bb[i0] -> MemRef_k_05__phi[] }; ; CHECK: MustWriteAccess := [Reduction Type: NONE] [Scalar: 0]