Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -183,6 +183,69 @@ /// @param Stmt The parent statement of the instruction void buildAccessSingleDim(MemAccInst Inst, ScopStmt *Stmt); + /// Finalize all access relations. + /// + /// When building up access relations, temporary access relations that + /// correctly represent each individual access are constructed. However, these + /// access relations can be inconsistent or non-optimal when looking at the + /// set of accesses as a whole. This function finalizes the memory accesses + /// and constructs a globally consistent state. + void finalizeAccesses(); + + /// 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(); + + /// Fold size constants to the right. + /// + /// In case all memory accesses in a given dimension are multiplied with a + /// common constant, we can remove this constant from the individual access + /// functions and move it to the size of the memory access. We do this as this + /// increases the size of the innermost dimension, consequently widens the + /// valid range the array subscript in this dimension can evaluate to, and + /// as a result increases the likelihood that our delinearization is + /// correct. + /// + /// Example: + /// + /// A[][n] + /// S[i,j] -> A[2i][2j+1] + /// S[i,j] -> A[2i][2j] + /// + /// => + /// + /// A[][2n] + /// S[i,j] -> A[i][2j+1] + /// S[i,j] -> A[i][2j] + /// + /// Constants in outer dimensions can arise when the elements of a parametric + /// multi-dimensional array are not elementary data types, but e.g., + /// structures. + void foldSizeConstantsToRight(); + + /// Fold memory accesses to handle parametric offset. + /// + /// As a post-processing step, we 'fold' memory accesses to parametric + /// offsets in the access functions. @see MemoryAccess::foldAccess for + /// details. + void foldAccessRelations(); + + /// Assume that all memory accesses are within bounds. + /// + /// After we have built a model of all memory accesses, we need to assume + /// that the model we built matches reality -- aka. all modeled memory + /// accesses always remain within bounds. We do this as last step, after + /// all memory accesses have been modeled and canonicalized. + void assumeNoOutOfBounds(); + + /// Mark arrays that have memory accesses with FortranArrayDescriptor. + void markFortranArrays(); + /// Build the alias checks for this SCoP. bool buildAliasChecks(AliasAnalysis &AA, OptimizationRemarkEmitter &ORE); Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -2084,57 +2084,6 @@ void addScopStmt(Region *R, StringRef Name, Loop *SurroundingLoop, std::vector EntryBlockInstructions); - /// 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(); - - /// Fold size constants to the right. - /// - /// In case all memory accesses in a given dimension are multiplied with a - /// common constant, we can remove this constant from the individual access - /// functions and move it to the size of the memory access. We do this as this - /// increases the size of the innermost dimension, consequently widens the - /// valid range the array subscript in this dimension can evaluate to, and - /// as a result increases the likelihood that our delinearization is - /// correct. - /// - /// Example: - /// - /// A[][n] - /// S[i,j] -> A[2i][2j+1] - /// S[i,j] -> A[2i][2j] - /// - /// => - /// - /// A[][2n] - /// S[i,j] -> A[i][2j+1] - /// S[i,j] -> A[i][2j] - /// - /// Constants in outer dimensions can arise when the elements of a parametric - /// multi-dimensional array are not elementary data types, but e.g., - /// structures. - void foldSizeConstantsToRight(); - - /// Fold memory accesses to handle parametric offset. - /// - /// As a post-processing step, we 'fold' memory accesses to parametric - /// offsets in the access functions. @see MemoryAccess::foldAccess for - /// details. - void foldAccessRelations(); - - /// Assume that all memory accesses are within bounds. - /// - /// After we have built a model of all memory accesses, we need to assume - /// that the model we built matches reality -- aka. all modeled memory - /// accesses always remain within bounds. We do this as last step, after - /// all memory accesses have been modeled and canonicalized. - void assumeNoOutOfBounds(); - /// Remove statements from the list of scop statements. /// /// @param ShouldDelete A function that returns true if the statement passed @@ -2154,18 +2103,6 @@ /// have a corresponding domain in the domain map (or it is empty). void removeStmtNotInDomainMap(); - /// Mark arrays that have memory accesses with FortranArrayDescriptor. - void markFortranArrays(); - - /// Finalize all access relations. - /// - /// When building up access relations, temporary access relations that - /// correctly represent each individual access are constructed. However, these - /// access relations can be inconsistent or non-optimal when looking at the - /// set of accesses as a whole. This function finalizes the memory accesses - /// and constructs a globally consistent state. - void finalizeAccesses(); - /// Construct the schedule of this SCoP. /// /// @param LI The LoopInfo for the current function. @@ -2342,6 +2279,12 @@ return make_range(RecordedAssumptions.rbegin(), RecordedAssumptions.rend()); } + /// Return an iterator range containing all the MemoryAccess objects of the + /// Scop. + iterator_range accessFunctions() { + return make_range(AccessFunctions.begin(), AccessFunctions.end()); + } + /// Return whether this scop is empty, i.e. contains no statements that /// could be executed. bool isEmpty() const { return Stmts.empty(); } Index: polly/lib/Analysis/ScopBuilder.cpp =================================================================== --- polly/lib/Analysis/ScopBuilder.cpp +++ polly/lib/Analysis/ScopBuilder.cpp @@ -1155,6 +1155,195 @@ MemAccess->setFortranArrayDescriptor(FAD); } +/// Check if @p Expr is divisible by @p Size. +static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) { + assert(Size != 0); + if (Size == 1) + return true; + + // Only one factor needs to be divisible. + if (auto *MulExpr = dyn_cast(Expr)) { + for (auto *FactorExpr : MulExpr->operands()) + if (isDivisible(FactorExpr, Size, SE)) + return true; + return false; + } + + // For other n-ary expressions (Add, AddRec, Max,...) all operands need + // to be divisible. + if (auto *NAryExpr = dyn_cast(Expr)) { + for (auto *OpExpr : NAryExpr->operands()) + if (!isDivisible(OpExpr, Size, SE)) + return false; + return true; + } + + auto *SizeSCEV = SE.getConstant(Expr->getType(), Size); + auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV); + auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV); + return MulSCEV == Expr; +} + +void ScopBuilder::foldSizeConstantsToRight() { + isl::union_set Accessed = scop->getAccesses().range(); + + for (auto Array : scop->arrays()) { + if (Array->getNumberOfDimensions() <= 1) + continue; + + isl::space Space = Array->getSpace(); + Space = Space.align_params(Accessed.get_space()); + + if (!Accessed.contains(Space)) + continue; + + isl::set Elements = Accessed.extract_set(Space); + isl::map Transform = isl::map::universe(Array->getSpace().map_from_set()); + + std::vector Int; + int Dims = Elements.dim(isl::dim::set); + for (int i = 0; i < Dims; i++) { + isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i); + DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1); + DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0); + + isl::basic_set DimHull = DimOnly.affine_hull(); + + if (i == Dims - 1) { + Int.push_back(1); + Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i); + continue; + } + + if (DimHull.dim(isl::dim::div) == 1) { + isl::aff Diff = DimHull.get_div(0); + isl::val Val = Diff.get_denominator_val(); + + int ValInt = 1; + if (Val.is_int()) { + auto ValAPInt = APIntFromVal(Val); + if (ValAPInt.isSignedIntN(32)) + ValInt = ValAPInt.getSExtValue(); + } else { + } + + Int.push_back(ValInt); + isl::constraint C = isl::constraint::alloc_equality( + isl::local_space(Transform.get_space())); + C = C.set_coefficient_si(isl::dim::out, i, ValInt); + C = C.set_coefficient_si(isl::dim::in, i, -1); + Transform = Transform.add_constraint(C); + continue; + } + + isl::basic_set ZeroSet = isl::basic_set(DimHull); + ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0); + + int ValInt = 1; + if (ZeroSet.is_equal(DimHull)) { + ValInt = 0; + } + + Int.push_back(ValInt); + Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i); + } + + isl::set MappedElements = isl::map(Transform).domain(); + if (!Elements.is_subset(MappedElements)) + continue; + + bool CanFold = true; + if (Int[0] <= 1) + CanFold = false; + + unsigned NumDims = Array->getNumberOfDimensions(); + for (unsigned i = 1; i < NumDims - 1; i++) + if (Int[0] != Int[i] && Int[i]) + CanFold = false; + + if (!CanFold) + continue; + + for (auto &Access : scop->accessFunctions()) + if (Access->getScopArrayInfo() == Array) + Access->setAccessRelation( + Access->getAccessRelation().apply_range(Transform)); + + std::vector Sizes; + for (unsigned i = 0; i < NumDims; i++) { + auto Size = Array->getDimensionSize(i); + + if (i == NumDims - 1) + Size = SE.getMulExpr(Size, SE.getConstant(Size->getType(), Int[0])); + Sizes.push_back(Size); + } + + Array->updateSizes(Sizes, false /* CheckConsistency */); + } +} + +void ScopBuilder::markFortranArrays() { + for (ScopStmt &Stmt : *scop) { + for (MemoryAccess *MemAcc : Stmt) { + Value *FAD = MemAcc->getFortranArrayDescriptor(); + if (!FAD) + continue; + + // TODO: const_cast-ing to edit + ScopArrayInfo *SAI = + const_cast(MemAcc->getLatestScopArrayInfo()); + assert(SAI && "memory access into a Fortran array does not " + "have an associated ScopArrayInfo"); + SAI->applyAndSetFAD(FAD); + } + } +} + +void ScopBuilder::finalizeAccesses() { + updateAccessDimensionality(); + foldSizeConstantsToRight(); + foldAccessRelations(); + assumeNoOutOfBounds(); + markFortranArrays(); +} + +void ScopBuilder::updateAccessDimensionality() { + // Check all array accesses for each base pointer and find a (virtual) element + // size for the base pointer that divides all access functions. + for (ScopStmt &Stmt : *scop) + for (MemoryAccess *Access : Stmt) { + if (!Access->isArrayKind()) + continue; + ScopArrayInfo *Array = + const_cast(Access->getScopArrayInfo()); + + if (Array->getNumberOfDimensions() != 1) + continue; + unsigned DivisibleSize = Array->getElemSizeInBytes(); + const SCEV *Subscript = Access->getSubscript(0); + while (!isDivisible(Subscript, DivisibleSize, SE)) + DivisibleSize /= 2; + auto *Ty = IntegerType::get(SE.getContext(), DivisibleSize * 8); + Array->updateElementType(Ty); + } + + for (auto &Stmt : *scop) + for (auto &Access : Stmt) + Access->updateDimensionality(); +} + +void ScopBuilder::foldAccessRelations() { + for (auto &Stmt : *scop) + for (auto &Access : Stmt) + Access->foldAccessRelation(); +} + +void ScopBuilder::assumeNoOutOfBounds() { + for (auto &Stmt : *scop) + for (auto &Access : Stmt) + Access->assumeNoOutOfBound(); +} + void ScopBuilder::ensureValueWrite(Instruction *Inst) { // Find the statement that defines the value of Inst. That statement has to // write the value to make it available to those statements that read it. @@ -2411,7 +2600,7 @@ scop->buildSchedule(LI); - scop->finalizeAccesses(); + finalizeAccesses(); scop->realignParams(); addUserContext(); Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -848,35 +848,6 @@ } } -/// Check if @p Expr is divisible by @p Size. -static bool isDivisible(const SCEV *Expr, unsigned Size, ScalarEvolution &SE) { - assert(Size != 0); - if (Size == 1) - return true; - - // Only one factor needs to be divisible. - if (auto *MulExpr = dyn_cast(Expr)) { - for (auto *FactorExpr : MulExpr->operands()) - if (isDivisible(FactorExpr, Size, SE)) - return true; - return false; - } - - // For other n-ary expressions (Add, AddRec, Max,...) all operands need - // to be divisible. - if (auto *NAryExpr = dyn_cast(Expr)) { - for (auto *OpExpr : NAryExpr->operands()) - if (!isDivisible(OpExpr, Size, SE)) - return false; - return true; - } - - auto *SizeSCEV = SE.getConstant(Expr->getType(), Size); - auto *UDivSCEV = SE.getUDivExpr(Expr, SizeSCEV); - auto *MulSCEV = SE.getMulExpr(UDivSCEV, SizeSCEV); - return MulSCEV == Expr; -} - void MemoryAccess::buildAccessRelation(const ScopArrayInfo *SAI) { assert(AccessRelation.is_null() && "AccessRelation already built"); @@ -2834,168 +2805,6 @@ buildContext(); } -Scop::~Scop() = default; - -void Scop::foldSizeConstantsToRight() { - isl::union_set Accessed = getAccesses().range(); - - for (auto Array : arrays()) { - if (Array->getNumberOfDimensions() <= 1) - continue; - - isl::space Space = Array->getSpace(); - Space = Space.align_params(Accessed.get_space()); - - if (!Accessed.contains(Space)) - continue; - - isl::set Elements = Accessed.extract_set(Space); - isl::map Transform = isl::map::universe(Array->getSpace().map_from_set()); - - std::vector Int; - int Dims = Elements.dim(isl::dim::set); - for (int i = 0; i < Dims; i++) { - isl::set DimOnly = isl::set(Elements).project_out(isl::dim::set, 0, i); - DimOnly = DimOnly.project_out(isl::dim::set, 1, Dims - i - 1); - DimOnly = DimOnly.lower_bound_si(isl::dim::set, 0, 0); - - isl::basic_set DimHull = DimOnly.affine_hull(); - - if (i == Dims - 1) { - Int.push_back(1); - Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i); - continue; - } - - if (DimHull.dim(isl::dim::div) == 1) { - isl::aff Diff = DimHull.get_div(0); - isl::val Val = Diff.get_denominator_val(); - - int ValInt = 1; - if (Val.is_int()) { - auto ValAPInt = APIntFromVal(Val); - if (ValAPInt.isSignedIntN(32)) - ValInt = ValAPInt.getSExtValue(); - } else { - } - - Int.push_back(ValInt); - isl::constraint C = isl::constraint::alloc_equality( - isl::local_space(Transform.get_space())); - C = C.set_coefficient_si(isl::dim::out, i, ValInt); - C = C.set_coefficient_si(isl::dim::in, i, -1); - Transform = Transform.add_constraint(C); - continue; - } - - isl::basic_set ZeroSet = isl::basic_set(DimHull); - ZeroSet = ZeroSet.fix_si(isl::dim::set, 0, 0); - - int ValInt = 1; - if (ZeroSet.is_equal(DimHull)) { - ValInt = 0; - } - - Int.push_back(ValInt); - Transform = Transform.equate(isl::dim::in, i, isl::dim::out, i); - } - - isl::set MappedElements = isl::map(Transform).domain(); - if (!Elements.is_subset(MappedElements)) - continue; - - bool CanFold = true; - if (Int[0] <= 1) - CanFold = false; - - unsigned NumDims = Array->getNumberOfDimensions(); - for (unsigned i = 1; i < NumDims - 1; i++) - if (Int[0] != Int[i] && Int[i]) - CanFold = false; - - if (!CanFold) - continue; - - for (auto &Access : AccessFunctions) - if (Access->getScopArrayInfo() == Array) - Access->setAccessRelation( - Access->getAccessRelation().apply_range(Transform)); - - std::vector Sizes; - for (unsigned i = 0; i < NumDims; i++) { - auto Size = Array->getDimensionSize(i); - - if (i == NumDims - 1) - Size = SE->getMulExpr(Size, SE->getConstant(Size->getType(), Int[0])); - Sizes.push_back(Size); - } - - Array->updateSizes(Sizes, false /* CheckConsistency */); - } -} - -void Scop::markFortranArrays() { - for (ScopStmt &Stmt : Stmts) { - for (MemoryAccess *MemAcc : Stmt) { - Value *FAD = MemAcc->getFortranArrayDescriptor(); - if (!FAD) - continue; - - // TODO: const_cast-ing to edit - ScopArrayInfo *SAI = - const_cast(MemAcc->getLatestScopArrayInfo()); - assert(SAI && "memory access into a Fortran array does not " - "have an associated ScopArrayInfo"); - SAI->applyAndSetFAD(FAD); - } - } -} - -void Scop::finalizeAccesses() { - updateAccessDimensionality(); - foldSizeConstantsToRight(); - foldAccessRelations(); - assumeNoOutOfBounds(); - markFortranArrays(); -} - -void Scop::updateAccessDimensionality() { - // Check all array accesses for each base pointer and find a (virtual) element - // size for the base pointer that divides all access functions. - for (ScopStmt &Stmt : *this) - for (MemoryAccess *Access : Stmt) { - if (!Access->isArrayKind()) - continue; - ScopArrayInfo *Array = - const_cast(Access->getScopArrayInfo()); - - if (Array->getNumberOfDimensions() != 1) - continue; - unsigned DivisibleSize = Array->getElemSizeInBytes(); - const SCEV *Subscript = Access->getSubscript(0); - while (!isDivisible(Subscript, DivisibleSize, *SE)) - DivisibleSize /= 2; - auto *Ty = IntegerType::get(SE->getContext(), DivisibleSize * 8); - Array->updateElementType(Ty); - } - - for (auto &Stmt : *this) - for (auto &Access : Stmt) - Access->updateDimensionality(); -} - -void Scop::foldAccessRelations() { - for (auto &Stmt : *this) - for (auto &Access : Stmt) - Access->foldAccessRelation(); -} - -void Scop::assumeNoOutOfBounds() { - for (auto &Stmt : *this) - for (auto &Access : Stmt) - Access->assumeNoOutOfBound(); -} - void Scop::removeFromStmtMap(ScopStmt &Stmt) { for (Instruction *Inst : Stmt.getInstructions()) InstStmtMap.erase(Inst); @@ -3021,6 +2830,8 @@ } } +Scop::~Scop() = default; + void Scop::removeStmts(std::function ShouldDelete, bool AfterHoisting) { for (auto StmtIt = Stmts.begin(), StmtEnd = Stmts.end(); StmtIt != StmtEnd;) {