Index: polly/include/polly/ScopBuilder.h =================================================================== --- polly/include/polly/ScopBuilder.h +++ polly/include/polly/ScopBuilder.h @@ -394,6 +394,14 @@ /// Required inv. loads: LB[0], LB[1], (V, if it may alias with A or LB) void hoistInvariantLoads(); + /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt. + void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs); + + /// Check if @p MA can always be hoisted without execution context. + bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, + bool MAInvalidCtxIsEmpty, + bool NonHoistableCtxIsEmpty); + /// Return true if and only if @p LI is a required invariant load. bool isRequiredInvariantLoad(LoadInst *LI) const { return scop->getRequiredInvariantLoads().count(LI); Index: polly/include/polly/ScopInfo.h =================================================================== --- polly/include/polly/ScopInfo.h +++ polly/include/polly/ScopInfo.h @@ -2033,11 +2033,6 @@ /// Return the access for the base ptr of @p MA if any. MemoryAccess *lookupBasePtrAccess(MemoryAccess *MA); - /// Check if @p MA can always be hoisted without execution context. - bool canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, - bool MAInvalidCtxIsEmpty, - bool NonHoistableCtxIsEmpty); - /// Create an id for @p Param and store it in the ParameterIds map. void createParameterId(const SCEV *Param); @@ -2312,9 +2307,6 @@ InvEquivClassVMap[LoadInst] = ClassRep; } - /// Add invariant loads listed in @p InvMAs with the domain of @p Stmt. - void addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs); - /// Remove the metadata stored for @p Access. void removeAccessData(MemoryAccess *Access); @@ -2340,6 +2332,12 @@ return make_range(Parameters.begin(), Parameters.end()); } + /// Return an interator range containing invariant accesses + iterator_range invariantEquivClasses() { + return make_range(InvariantEquivClasses.begin(), + InvariantEquivClasses.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 @@ -76,6 +76,16 @@ cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory)); +static cl::opt PollyAllowDereferenceOfAllFunctionParams( + "polly-allow-dereference-of-all-function-parameters", + cl::desc( + "Treat all parameters to functions that are pointers as dereferencible." + " This is useful for invariant load hoisting, since we can generate" + " less runtime checks. This is only valid if all pointers to functions" + " are always initialized, so that Polly can choose to hoist" + " their loads. "), + cl::Hidden, cl::init(false), cl::cat(PollyCategory)); + static cl::opt UnprofitableScalarAccs( "polly-unprofitable-scalar-accs", cl::desc("Count statements with scalar accesses as not optimizable"), @@ -1343,7 +1353,7 @@ // Transfer the memory access from the statement to the SCoP. for (auto InvMA : InvariantAccesses) Stmt.removeMemoryAccess(InvMA.MA); - scop->addInvariantLoads(Stmt, InvariantAccesses); + addInvariantLoads(Stmt, InvariantAccesses); } } @@ -1456,6 +1466,169 @@ return WrittenCtx; } +bool isAParameter(llvm::Value *maybeParam, const Function &F) { + for (const llvm::Argument &Arg : F.args()) + if (&Arg == maybeParam) + return true; + + return false; +} + +bool ScopBuilder::canAlwaysBeHoisted(MemoryAccess *MA, + bool StmtInvalidCtxIsEmpty, + bool MAInvalidCtxIsEmpty, + bool NonHoistableCtxIsEmpty) { + LoadInst *LInst = cast(MA->getAccessInstruction()); + const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout(); + if (PollyAllowDereferenceOfAllFunctionParams && + isAParameter(LInst->getPointerOperand(), scop->getFunction())) + return true; + + // TODO: We can provide more information for better but more expensive + // results. + if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(), + LInst->getAlignment(), DL)) + return false; + + // If the location might be overwritten we do not hoist it unconditionally. + // + // TODO: This is probably too conservative. + if (!NonHoistableCtxIsEmpty) + return false; + + // If a dereferenceable load is in a statement that is modeled precisely we + // can hoist it. + if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty) + return true; + + // Even if the statement is not modeled precisely we can hoist the load if it + // does not involve any parameters that might have been specialized by the + // statement domain. + for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++) + if (!isa(MA->getSubscript(u))) + return false; + return true; +} + +void ScopBuilder::addInvariantLoads(ScopStmt &Stmt, + InvariantAccessesTy &InvMAs) { + if (InvMAs.empty()) + return; + + isl::set StmtInvalidCtx = Stmt.getInvalidContext(); + bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty(); + + // Get the context under which the statement is executed but remove the error + // context under which this statement is reached. + isl::set DomainCtx = Stmt.getDomain().params(); + DomainCtx = DomainCtx.subtract(StmtInvalidCtx); + + if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) { + auto *AccInst = InvMAs.front().MA->getAccessInstruction(); + scop->invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent()); + return; + } + + // Project out all parameters that relate to loads in the statement. Otherwise + // we could have cyclic dependences on the constraints under which the + // hoisted loads are executed and we could not determine an order in which to + // pre-load them. This happens because not only lower bounds are part of the + // domain but also upper bounds. + for (auto &InvMA : InvMAs) { + auto *MA = InvMA.MA; + Instruction *AccInst = MA->getAccessInstruction(); + if (SE.isSCEVable(AccInst->getType())) { + SetVector Values; + for (const SCEV *Parameter : scop->parameters()) { + Values.clear(); + findValues(Parameter, SE, Values); + if (!Values.count(AccInst)) + continue; + + if (isl::id ParamId = scop->getIdForParam(Parameter)) { + int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId); + if (Dim >= 0) + DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1); + } + } + } + } + + for (auto &InvMA : InvMAs) { + auto *MA = InvMA.MA; + isl::set NHCtx = InvMA.NonHoistableCtx; + + // Check for another invariant access that accesses the same location as + // MA and if found consolidate them. Otherwise create a new equivalence + // class at the end of InvariantEquivClasses. + LoadInst *LInst = cast(MA->getAccessInstruction()); + Type *Ty = LInst->getType(); + const SCEV *PointerSCEV = SE.getSCEV(LInst->getPointerOperand()); + + isl::set MAInvalidCtx = MA->getInvalidContext(); + bool NonHoistableCtxIsEmpty = NHCtx.is_empty(); + bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty(); + + isl::set MACtx; + // Check if we know that this pointer can be speculatively accessed. + if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty, + NonHoistableCtxIsEmpty)) { + MACtx = isl::set::universe(DomainCtx.get_space()); + } else { + MACtx = DomainCtx; + MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx)); + MACtx = MACtx.gist_params(scop->getContext()); + } + + bool Consolidated = false; + for (auto &IAClass : scop->invariantEquivClasses()) { + if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType) + continue; + + // If the pointer and the type is equal check if the access function wrt. + // to the domain is equal too. It can happen that the domain fixes + // parameter values and these can be different for distinct part of the + // SCoP. If this happens we cannot consolidate the loads but need to + // create a new invariant load equivalence class. + auto &MAs = IAClass.InvariantAccesses; + if (!MAs.empty()) { + auto *LastMA = MAs.front(); + + isl::set AR = MA->getAccessRelation().range(); + isl::set LastAR = LastMA->getAccessRelation().range(); + bool SameAR = AR.is_equal(LastAR); + + if (!SameAR) + continue; + } + + // Add MA to the list of accesses that are in this class. + MAs.push_front(MA); + + Consolidated = true; + + // Unify the execution context of the class and this statement. + isl::set IAClassDomainCtx = IAClass.ExecutionContext; + if (IAClassDomainCtx) + IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce(); + else + IAClassDomainCtx = MACtx; + IAClass.ExecutionContext = IAClassDomainCtx; + break; + } + + if (Consolidated) + continue; + + MACtx = MACtx.coalesce(); + + // If we did not consolidate MA, thus did not find an equivalence class + // for it, we create a new one. + scop->addInvariantEquivClass( + InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty}); + } +} + void ScopBuilder::collectCandidateReductionLoads( MemoryAccess *StoreMA, SmallVectorImpl &Loads) { ScopStmt *Stmt = StoreMA->getStatement(); Index: polly/lib/Analysis/ScopInfo.cpp =================================================================== --- polly/lib/Analysis/ScopInfo.cpp +++ polly/lib/Analysis/ScopInfo.cpp @@ -171,16 +171,6 @@ "Do not add parameter bounds and do no gist simplify sets accordingly"), cl::Hidden, cl::init(false), cl::cat(PollyCategory)); -static cl::opt PollyAllowDereferenceOfAllFunctionParams( - "polly-allow-dereference-of-all-function-parameters", - cl::desc( - "Treat all parameters to functions that are pointers as dereferencible." - " This is useful for invariant load hoisting, since we can generate" - " less runtime checks. This is only valid if all pointers to functions" - " are always initialized, so that Polly can choose to hoist" - " their loads. "), - cl::Hidden, cl::init(false), cl::cat(PollyCategory)); - static cl::opt PollyPreciseFoldAccesses( "polly-precise-fold-accesses", cl::desc("Fold memory accesses to model more possible delinearizations " @@ -3500,167 +3490,6 @@ return nullptr; } -bool isAParameter(llvm::Value *maybeParam, const Function &F) { - for (const llvm::Argument &Arg : F.args()) - if (&Arg == maybeParam) - return true; - - return false; -} - -bool Scop::canAlwaysBeHoisted(MemoryAccess *MA, bool StmtInvalidCtxIsEmpty, - bool MAInvalidCtxIsEmpty, - bool NonHoistableCtxIsEmpty) { - LoadInst *LInst = cast(MA->getAccessInstruction()); - const DataLayout &DL = LInst->getParent()->getModule()->getDataLayout(); - if (PollyAllowDereferenceOfAllFunctionParams && - isAParameter(LInst->getPointerOperand(), getFunction())) - return true; - - // TODO: We can provide more information for better but more expensive - // results. - if (!isDereferenceableAndAlignedPointer(LInst->getPointerOperand(), - LInst->getAlignment(), DL)) - return false; - - // If the location might be overwritten we do not hoist it unconditionally. - // - // TODO: This is probably too conservative. - if (!NonHoistableCtxIsEmpty) - return false; - - // If a dereferenceable load is in a statement that is modeled precisely we - // can hoist it. - if (StmtInvalidCtxIsEmpty && MAInvalidCtxIsEmpty) - return true; - - // Even if the statement is not modeled precisely we can hoist the load if it - // does not involve any parameters that might have been specialized by the - // statement domain. - for (unsigned u = 0, e = MA->getNumSubscripts(); u < e; u++) - if (!isa(MA->getSubscript(u))) - return false; - return true; -} - -void Scop::addInvariantLoads(ScopStmt &Stmt, InvariantAccessesTy &InvMAs) { - if (InvMAs.empty()) - return; - - isl::set StmtInvalidCtx = Stmt.getInvalidContext(); - bool StmtInvalidCtxIsEmpty = StmtInvalidCtx.is_empty(); - - // Get the context under which the statement is executed but remove the error - // context under which this statement is reached. - isl::set DomainCtx = Stmt.getDomain().params(); - DomainCtx = DomainCtx.subtract(StmtInvalidCtx); - - if (DomainCtx.n_basic_set() >= MaxDisjunctsInDomain) { - auto *AccInst = InvMAs.front().MA->getAccessInstruction(); - invalidate(COMPLEXITY, AccInst->getDebugLoc(), AccInst->getParent()); - return; - } - - // Project out all parameters that relate to loads in the statement. Otherwise - // we could have cyclic dependences on the constraints under which the - // hoisted loads are executed and we could not determine an order in which to - // pre-load them. This happens because not only lower bounds are part of the - // domain but also upper bounds. - for (auto &InvMA : InvMAs) { - auto *MA = InvMA.MA; - Instruction *AccInst = MA->getAccessInstruction(); - if (SE->isSCEVable(AccInst->getType())) { - SetVector Values; - for (const SCEV *Parameter : Parameters) { - Values.clear(); - findValues(Parameter, *SE, Values); - if (!Values.count(AccInst)) - continue; - - if (isl::id ParamId = getIdForParam(Parameter)) { - int Dim = DomainCtx.find_dim_by_id(isl::dim::param, ParamId); - if (Dim >= 0) - DomainCtx = DomainCtx.eliminate(isl::dim::param, Dim, 1); - } - } - } - } - - for (auto &InvMA : InvMAs) { - auto *MA = InvMA.MA; - isl::set NHCtx = InvMA.NonHoistableCtx; - - // Check for another invariant access that accesses the same location as - // MA and if found consolidate them. Otherwise create a new equivalence - // class at the end of InvariantEquivClasses. - LoadInst *LInst = cast(MA->getAccessInstruction()); - Type *Ty = LInst->getType(); - const SCEV *PointerSCEV = SE->getSCEV(LInst->getPointerOperand()); - - isl::set MAInvalidCtx = MA->getInvalidContext(); - bool NonHoistableCtxIsEmpty = NHCtx.is_empty(); - bool MAInvalidCtxIsEmpty = MAInvalidCtx.is_empty(); - - isl::set MACtx; - // Check if we know that this pointer can be speculatively accessed. - if (canAlwaysBeHoisted(MA, StmtInvalidCtxIsEmpty, MAInvalidCtxIsEmpty, - NonHoistableCtxIsEmpty)) { - MACtx = isl::set::universe(DomainCtx.get_space()); - } else { - MACtx = DomainCtx; - MACtx = MACtx.subtract(MAInvalidCtx.unite(NHCtx)); - MACtx = MACtx.gist_params(getContext()); - } - - bool Consolidated = false; - for (auto &IAClass : InvariantEquivClasses) { - if (PointerSCEV != IAClass.IdentifyingPointer || Ty != IAClass.AccessType) - continue; - - // If the pointer and the type is equal check if the access function wrt. - // to the domain is equal too. It can happen that the domain fixes - // parameter values and these can be different for distinct part of the - // SCoP. If this happens we cannot consolidate the loads but need to - // create a new invariant load equivalence class. - auto &MAs = IAClass.InvariantAccesses; - if (!MAs.empty()) { - auto *LastMA = MAs.front(); - - isl::set AR = MA->getAccessRelation().range(); - isl::set LastAR = LastMA->getAccessRelation().range(); - bool SameAR = AR.is_equal(LastAR); - - if (!SameAR) - continue; - } - - // Add MA to the list of accesses that are in this class. - MAs.push_front(MA); - - Consolidated = true; - - // Unify the execution context of the class and this statement. - isl::set IAClassDomainCtx = IAClass.ExecutionContext; - if (IAClassDomainCtx) - IAClassDomainCtx = IAClassDomainCtx.unite(MACtx).coalesce(); - else - IAClassDomainCtx = MACtx; - IAClass.ExecutionContext = IAClassDomainCtx; - break; - } - - if (Consolidated) - continue; - - MACtx = MACtx.coalesce(); - - // If we did not consolidate MA, thus did not find an equivalence class - // for it, we create a new one. - addInvariantEquivClass( - InvariantEquivClassTy{PointerSCEV, MemoryAccessList{MA}, MACtx, Ty}); - } -} - ScopArrayInfo *Scop::getOrCreateScopArrayInfo(Value *BasePtr, Type *ElementType, ArrayRef Sizes, MemoryKind Kind,