Index: include/polly/ScopInfo.h =================================================================== --- include/polly/ScopInfo.h +++ include/polly/ScopInfo.h @@ -1836,6 +1836,15 @@ /// A number that uniquely represents a Scop within its function const int ID; + /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value + /// scalar. + DenseMap> ValueUseAccs; + + /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or + /// MemoryKind::ExitPHI scalar. + DenseMap> + PHIIncomingAccs; + /// Return the ID for a new Scop within a function static int getNextID(std::string ParentFunc); @@ -2300,6 +2309,12 @@ AccessFunctions.emplace_back(Access); } + /// Add metadata for @p Access. + void addAccessData(MemoryAccess *Access); + + /// Remove the metadata stored for @p Access. + void removeAccessData(MemoryAccess *Access); + ScalarEvolution *getSE() const; /// Get the count of parameters used in this Scop. @@ -2872,6 +2887,27 @@ /// This function returns a unique index which can be used to identify a /// statement. long getNextStmtIdx() { return StmtIdx++; } + + /// Return the MemoryAccess that writes an llvm::Value, represented by a + /// ScopArrayInfo. + /// + /// There can be at most one such MemoryAccess per llvm::Value in the SCoP. + /// Zero is possible for read-only values. + MemoryAccess *getValueDef(const ScopArrayInfo *SAI) const; + + /// Return all MemoryAccesses that us an llvm::Value, represented by a + /// ScopArrayInfo. + ArrayRef getValueUses(const ScopArrayInfo *SAI) const; + + /// Return the MemoryAccess that represents an llvm::PHINode. + /// + /// ExitPHIs's PHINode is not within the SCoPs. This function returns nullptr + /// for them. + MemoryAccess *getPHIRead(const ScopArrayInfo *SAI) const; + + /// Return all MemoryAccesses for all incoming statements of a PHINode, + /// represented by a ScopArrayInfo. + ArrayRef getPHIIncomings(const ScopArrayInfo *SAI) const; }; /// Print Scop scop to raw_ostream O. Index: lib/Analysis/ScopInfo.cpp =================================================================== --- lib/Analysis/ScopInfo.cpp +++ lib/Analysis/ScopInfo.cpp @@ -1305,6 +1305,7 @@ auto *SAI = S.getOrCreateScopArrayInfo(Access->getOriginalBaseAddr(), ElementType, Access->Sizes, Ty); Access->buildAccessRelation(SAI); + S.addAccessData(Access); } } @@ -1963,8 +1964,10 @@ return Acc->getAccessInstruction() == MA->getAccessInstruction(); }; for (auto *MA : MemAccs) { - if (Predicate(MA)) + if (Predicate(MA)) { removeAccessData(MA); + Parent.removeAccessData(MA); + } } MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate), MemAccs.end()); @@ -1977,6 +1980,7 @@ MemAccs.erase(MAIt); removeAccessData(MA); + Parent.removeAccessData(MA); auto It = InstructionToAccess.find(MA->getAccessInstruction()); if (It != InstructionToAccess.end()) { @@ -4946,6 +4950,69 @@ return nullptr; } +void Scop::addAccessData(MemoryAccess *Access) { + const ScopArrayInfo *SAI = Access->getOriginalScopArrayInfo(); + assert(SAI && "can only use after access relations have been constructed"); + + if (Access->isOriginalValueKind() && Access->isRead()) + ValueUseAccs[SAI].push_back(Access); + else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) + PHIIncomingAccs[SAI].push_back(Access); +} + +void Scop::removeAccessData(MemoryAccess *Access) { + if (Access->isOriginalValueKind() && Access->isRead()) { + auto &Uses = ValueUseAccs[Access->getScopArrayInfo()]; + std::remove(Uses.begin(), Uses.end(), Access); + } else if (Access->isOriginalAnyPHIKind() && Access->isWrite()) { + auto &Incomings = PHIIncomingAccs[Access->getScopArrayInfo()]; + std::remove(Incomings.begin(), Incomings.end(), Access); + } +} + +MemoryAccess *Scop::getValueDef(const ScopArrayInfo *SAI) const { + assert(SAI->isValueKind()); + + Instruction *Val = dyn_cast(SAI->getBasePtr()); + if (!Val) + return nullptr; + + ScopStmt *Stmt = getStmtFor(Val); + if (!Stmt) + return nullptr; + + return Stmt->lookupValueWriteOf(Val); +} + +ArrayRef Scop::getValueUses(const ScopArrayInfo *SAI) const { + assert(SAI->isValueKind()); + auto It = ValueUseAccs.find(SAI); + if (It == ValueUseAccs.end()) + return {}; + return It->second; +} + +MemoryAccess *Scop::getPHIRead(const ScopArrayInfo *SAI) const { + assert(SAI->isPHIKind() || SAI->isExitPHIKind()); + + if (SAI->isExitPHIKind()) + return nullptr; + + PHINode *PHI = cast(SAI->getBasePtr()); + ScopStmt *Stmt = getStmtFor(PHI); + assert(Stmt && "PHINode must be within the SCoP"); + + return Stmt->lookupPHIReadOf(PHI); +} + +ArrayRef Scop::getPHIIncomings(const ScopArrayInfo *SAI) const { + assert(SAI->isPHIKind() || SAI->isExitPHIKind()); + auto It = PHIIncomingAccs.find(SAI); + if (It == PHIIncomingAccs.end()) + return {}; + return It->second; +} + //===----------------------------------------------------------------------===// void ScopInfoRegionPass::getAnalysisUsage(AnalysisUsage &AU) const { AU.addRequired(); Index: lib/Transform/DeLICM.cpp =================================================================== --- lib/Transform/DeLICM.cpp +++ lib/Transform/DeLICM.cpp @@ -199,99 +199,6 @@ STATISTIC(TargetsMapped, "Number of stores used for at least one mapping"); STATISTIC(DeLICMScopsModified, "Number of SCoPs optimized"); -/// Class for keeping track of scalar def-use chains in the polyhedral -/// representation. -/// -/// MemoryKind::Value: -/// There is one definition per llvm::Value or zero (read-only values defined -/// before the SCoP) and an arbitrary number of reads. -/// -/// MemoryKind::PHI, MemoryKind::ExitPHI: -/// There is at least one write (the incoming blocks/stmts) and one -/// (MemoryKind::PHI) or zero (MemoryKind::ExitPHI) reads per llvm::PHINode. -class ScalarDefUseChains { -private: - /// The definitions (i.e. write MemoryAccess) of a MemoryKind::Value scalar. - DenseMap ValueDefAccs; - - /// List of all uses (i.e. read MemoryAccesses) for a MemoryKind::Value - /// scalar. - DenseMap> ValueUseAccs; - - /// The receiving part (i.e. read MemoryAccess) of a MemoryKind::PHI scalar. - DenseMap PHIReadAccs; - - /// List of all incoming values (write MemoryAccess) of a MemoryKind::PHI or - /// MemoryKind::ExitPHI scalar. - DenseMap> - PHIIncomingAccs; - -public: - /// Find the MemoryAccesses that access the ScopArrayInfo-represented memory. - /// - /// @param S The SCoP to analyze. - void compute(Scop *S) { - // Purge any previous result. - reset(); - - for (auto &Stmt : *S) { - for (auto *MA : Stmt) { - if (MA->isOriginalValueKind() && MA->isWrite()) { - auto *SAI = MA->getScopArrayInfo(); - assert(!ValueDefAccs.count(SAI) && - "There can be at most one " - "definition per MemoryKind::Value scalar"); - ValueDefAccs[SAI] = MA; - } - - if (MA->isOriginalValueKind() && MA->isRead()) - ValueUseAccs[MA->getScopArrayInfo()].push_back(MA); - - if (MA->isOriginalAnyPHIKind() && MA->isRead()) { - auto *SAI = MA->getScopArrayInfo(); - assert(!PHIReadAccs.count(SAI) && - "There must be exactly one read " - "per PHI (that's where the PHINode is)"); - PHIReadAccs[SAI] = MA; - } - - if (MA->isOriginalAnyPHIKind() && MA->isWrite()) - PHIIncomingAccs[MA->getScopArrayInfo()].push_back(MA); - } - } - } - - /// Free all memory used by the analysis. - void reset() { - ValueDefAccs.clear(); - ValueUseAccs.clear(); - PHIReadAccs.clear(); - PHIIncomingAccs.clear(); - } - - MemoryAccess *getValueDef(const ScopArrayInfo *SAI) const { - return ValueDefAccs.lookup(SAI); - } - - ArrayRef getValueUses(const ScopArrayInfo *SAI) const { - auto It = ValueUseAccs.find(SAI); - if (It == ValueUseAccs.end()) - return {}; - return It->second; - } - - MemoryAccess *getPHIRead(const ScopArrayInfo *SAI) const { - return PHIReadAccs.lookup(SAI); - } - - ArrayRef getPHIIncomings(const ScopArrayInfo *SAI) const { - auto It = PHIIncomingAccs.find(SAI); - if (It == PHIIncomingAccs.end()) - return {}; - return It->second; - } -}; - isl::union_map computeReachingDefinition(isl::union_map Schedule, isl::union_map Writes, bool InclDef, bool InclRedef) { @@ -1393,9 +1300,6 @@ /// transformations. Knowledge Zone; - /// For getting the MemoryAccesses that write or read a given scalar. - ScalarDefUseChains DefUse; - /// Number of StoreInsts something can be mapped to. int NumberOfCompatibleTargets = 0; @@ -1424,7 +1328,7 @@ assert(SAI); if (SAI->isValueKind()) { - auto *MA = DefUse.getValueDef(SAI); + auto *MA = S->getValueDef(SAI); if (!MA) { DEBUG(dbgs() << " Reject because value is read-only within the scop\n"); @@ -1451,7 +1355,7 @@ } if (SAI->isPHIKind()) { - auto *MA = DefUse.getPHIRead(SAI); + auto *MA = S->getPHIRead(SAI); assert(MA); // Mapping of an incoming block from before the SCoP is not supported by @@ -1488,14 +1392,14 @@ auto Reads = makeEmptyUnionSet(); // Find all uses. - for (auto *MA : DefUse.getValueUses(SAI)) + for (auto *MA : S->getValueUses(SAI)) Reads = give(isl_union_set_add_set(Reads.take(), getDomainFor(MA).take())); // { DomainRead[] -> Scatter[] } auto ReadSchedule = getScatterFor(Reads); - auto *DefMA = DefUse.getValueDef(SAI); + auto *DefMA = S->getValueDef(SAI); assert(DefMA); // { DomainDef[] } @@ -1544,14 +1448,14 @@ auto PHIWriteScatter = makeEmptyUnionMap(); // Collect all incoming block timepoint. - for (auto *MA : DefUse.getPHIIncomings(SAI)) { + for (auto *MA : S->getPHIIncomings(SAI)) { auto Scatter = getScatterFor(MA); PHIWriteScatter = give(isl_union_map_add_map(PHIWriteScatter.take(), Scatter.take())); } // { DomainPHIRead[] -> Scatter[] } - auto PHIReadScatter = getScatterFor(DefUse.getPHIRead(SAI)); + auto PHIReadScatter = getScatterFor(S->getPHIRead(SAI)); // { DomainPHIRead[] -> Scatter[] } auto BeforeRead = beforeScatter(PHIReadScatter, true); @@ -1584,7 +1488,7 @@ bool tryMapValue(const ScopArrayInfo *SAI, isl::map TargetElt) { assert(SAI->isValueKind()); - auto *DefMA = DefUse.getValueDef(SAI); + auto *DefMA = S->getValueDef(SAI); assert(DefMA->isValueKind()); assert(DefMA->isMustWrite()); auto *V = DefMA->getAccessValue(); @@ -1686,7 +1590,7 @@ isl::union_map UseTarget, isl::map Lifetime, Knowledge Proposed) { // Redirect the read accesses. - for (auto *MA : DefUse.getValueUses(SAI)) { + for (auto *MA : S->getValueUses(SAI)) { // { DomainUse[] } auto Domain = getDomainFor(MA); @@ -1699,7 +1603,7 @@ MA->setNewAccessRelation(isl_map_from_union_map(NewAccRel.take())); } - auto *WA = DefUse.getValueDef(SAI); + auto *WA = S->getValueDef(SAI); WA->setNewAccessRelation(DefTarget.copy()); applyLifetime(Proposed); @@ -1717,7 +1621,7 @@ auto Result = makeEmptyUnionMap(); // Collect the incoming values. - for (auto *MA : DefUse.getPHIIncomings(SAI)) { + for (auto *MA : S->getPHIIncomings(SAI)) { // { DomainWrite[] -> ValInst[] } isl::union_map ValInst; auto *WriteStmt = MA->getStatement(); @@ -1753,7 +1657,7 @@ /// /// @return true if the PHI scalar has been mapped. bool tryMapPHI(const ScopArrayInfo *SAI, isl::map TargetElt) { - auto *PHIRead = DefUse.getPHIRead(SAI); + auto *PHIRead = S->getPHIRead(SAI); assert(PHIRead->isPHIKind()); assert(PHIRead->isRead()); @@ -1789,7 +1693,7 @@ // { DomainWrite[] } auto UniverseWritesDom = give(isl_union_set_empty(ParamSpace.copy())); - for (auto *MA : DefUse.getPHIIncomings(SAI)) + for (auto *MA : S->getPHIIncomings(SAI)) UniverseWritesDom = give(isl_union_set_add_set(UniverseWritesDom.take(), getDomainFor(MA).take())); @@ -1882,7 +1786,7 @@ isl::union_map WriteTarget, isl::map Lifetime, Knowledge Proposed) { // Redirect the PHI incoming writes. - for (auto *MA : DefUse.getPHIIncomings(SAI)) { + for (auto *MA : S->getPHIIncomings(SAI)) { // { DomainWrite[] } auto Domain = getDomainFor(MA); @@ -1896,7 +1800,7 @@ } // Redirect the PHI read. - auto *PHIRead = DefUse.getPHIRead(SAI); + auto *PHIRead = S->getPHIRead(SAI); PHIRead->setNewAccessRelation(ReadTarget.copy()); applyLifetime(Proposed); @@ -1992,7 +1896,7 @@ if (!tryMapValue(SAI, EltTarget)) continue; - auto *DefAcc = DefUse.getValueDef(SAI); + auto *DefAcc = S->getValueDef(SAI); ProcessAllIncoming(DefAcc->getStatement()); AnyMapped = true; @@ -2005,7 +1909,7 @@ continue; // Add inputs of all incoming statements to the worklist. Prefer the // input accesses of the incoming blocks. - for (auto *PHIWrite : DefUse.getPHIIncomings(SAI)) { + for (auto *PHIWrite : S->getPHIIncomings(SAI)) { auto *PHIWriteStmt = PHIWrite->getStatement(); bool FoundAny = false; for (auto Incoming : PHIWrite->getIncoming()) { @@ -2120,7 +2024,6 @@ return false; } - DefUse.compute(S); isl::union_set EltUnused; isl::union_map EltKnown, EltWritten;