Analysis pass computing a topologically sorted strongly connected component (SCC) graph. More...

#include <TopologicallySortedSCCGraph.h>

Inheritance diagram for souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis:

Collaboration diagram for souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis:

Public Member Functions
size_t	indexOfScc (const size_t scc) const

std::set< size_t >	indexOfScc (const std::set< size_t > &sccs) const

const std::vector< size_t > &	order () const

void	print (std::ostream &os) const override
	Output topologically sorted strongly connected component graph in text format. More...

void	run (const TranslationUnit &translationUnit) override
	run analysis for a Ast translation unit More...

size_t	sccOfIndex (const size_t index) const

	TopologicallySortedSCCGraphAnalysis ()

Public Member Functions inherited from souffle::ast::analysis::Analysis
	Analysis (std::string identifier)

virtual const std::string &	getName () const
	get name of the analysis More...

virtual	~Analysis ()=default

Static Public Attributes
static constexpr const char *	name = "topological-scc-graph"

Private Member Functions
void	computeTopologicalOrdering (size_t scc, std::vector< bool > &visited)
	Recursive component for the forwards algorithm computing the topological ordering of the SCCs. More...

int	topologicalOrderingCost (const std::vector< size_t > &permutationOfSCCs) const
	Calculate the topological ordering cost of a permutation of as of yet unordered SCCs using the ordered SCCs. More...

Private Attributes
SCCGraphAnalysis *	sccGraph = nullptr
	The strongly connected component (SCC) graph. More...

std::vector< size_t >	sccOrder
	The final topological ordering of the SCCs. More...

Additional Inherited Members
Protected Attributes inherited from souffle::ast::analysis::Analysis
const std::string	identifier

Detailed Description

Analysis pass computing a topologically sorted strongly connected component (SCC) graph.

Definition at line 49 of file TopologicallySortedSCCGraph.h.

Constructor & Destructor Documentation

◆ TopologicallySortedSCCGraphAnalysis()

souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::TopologicallySortedSCCGraphAnalysis ( )

inline

Definition at line 53 of file TopologicallySortedSCCGraph.h.

53 {

References sccOrder.

Member Function Documentation

◆ computeTopologicalOrdering()

void souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::computeTopologicalOrdering	(	size_t	scc,
		std::vector< bool > &	visited
	)

private

Recursive component for the forwards algorithm computing the topological ordering of the SCCs.

Definition at line 77 of file TopologicallySortedSCCGraph.cpp.

                             {
             continue;
         }
         hasUnvisitedPredecessor = false;
         const auto& successorsPredecessors = sccGraph->getPredecessorSCCs(scc_i);
         for (const auto scc_j : successorsPredecessors) {
             if (!visited[scc_j]) {
                 hasUnvisitedPredecessor = true;
                 break;
             }
         }
         if (!hasUnvisitedPredecessor) {
             // give it a temporary marking
             visited[scc_i] = true;
             // add it to the permanent ordering
             sccOrder.push_back(scc_i);
             // and use it as a root node in a recursive call to this function
             computeTopologicalOrdering(scc_i, visited);
             // finally, indicate that a successor has been found for this node
             found = true;
         }
     }
     // return at once if no valid successors have been found; as either it has none or they all have a
     // better predecessor
     if (!found) {
         return;
     }
     hasUnvisitedPredecessor = false;
     const auto& predecessors = sccGraph->getPredecessorSCCs(scc);
     for (const auto scc_j : predecessors) {
         if (!visited[scc_j]) {
             hasUnvisitedPredecessor = true;
             break;
         }
     }
     hasUnvisitedSuccessor = false;
     const auto& successors = sccGraph->getSuccessorSCCs(scc);
     for (const auto scc_j : successors) {
         if (!visited[scc_j]) {
             hasUnvisitedSuccessor = true;
             break;
         }
     }
     // otherwise, if more white successors remain for the current scc, use it again as the root node in a
     // recursive call to this function
     if (hasUnvisitedSuccessor && !hasUnvisitedPredecessor) {
         computeTopologicalOrdering(scc, visited);
     }
 }
  
 void TopologicallySortedSCCGraphAnalysis::run(const TranslationUnit& translationUnit) {
     // obtain the scc graph
     sccGraph = translationUnit.getAnalysis<SCCGraphAnalysis>();
     // clear the list of ordered sccs
     sccOrder.clear();
     std::vector<bool> visited;
     visited.resize(sccGraph->getNumberOfSCCs());

Referenced by run().

◆ indexOfScc() [1/2]

size_t souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::indexOfScc ( const size_t scc ) const

inline

Definition at line 65 of file TopologicallySortedSCCGraph.h.

                             : sccs) {
             indices.insert(indexOfScc(scc));
         }
         return indices;
     }

◆ indexOfScc() [2/2]

std::set<size_t> souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::indexOfScc ( const std::set< size_t > & sccs ) const

inline

Definition at line 71 of file TopologicallySortedSCCGraph.h.

        :
     /** The strongly connected component (SCC) graph. */
     SCCGraphAnalysis* sccGraph = nullptr;
  

◆ order()

const std::vector<size_t>& souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::order ( ) const

inline

Definition at line 57 of file TopologicallySortedSCCGraph.h.

                                               {
         auto it = std::find(sccOrder.begin(), sccOrder.end(), scc);
         assert(it != sccOrder.end());

References sccOrder.

Referenced by souffle::ast::analysis::RelationScheduleAnalysis::run().

◆ print()

void souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::print ( std::ostream & os ) const

overridevirtual

Output topologically sorted strongly connected component graph in text format.

Reimplemented from souffle::ast::analysis::Analysis.

Definition at line 159 of file TopologicallySortedSCCGraph.cpp.

                                      : successorSccs) {
             const auto successorSccIndex = *std::find(sccOrder.begin(), sccOrder.end(), successorScc);
             os << sccIndex << " " << successorSccIndex << std::endl;
         }
     }
     os << "--- total order with relations of each strata ---" << std::endl;
     for (size_t i = 0; i < sccOrder.size(); i++) {
         os << i << ": [";
         os << join(sccGraph->getInternalRelations(sccOrder[i]), ", ",
                 [](std::ostream& out, const Relation* rel) { out << rel->getQualifiedName(); });
         os << "]" << std::endl;
     }
     os << std::endl;
     os << "--- statistics of topological order ---" << std::endl;
     os << "cost: " << topologicalOrderingCost(sccOrder) << std::endl;
 }
  
 }  // namespace souffle::ast::analysis

◆ run()

void souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::run ( const TranslationUnit & )

overridevirtual

run analysis for a Ast translation unit

Implements souffle::ast::analysis::Analysis.

Definition at line 135 of file TopologicallySortedSCCGraph.cpp.

                                                                    {
         // if that scc has no predecessors
         if (sccGraph->getPredecessorSCCs(scc).empty()) {
             // put it in the ordering
             sccOrder.push_back(scc);
             visited[scc] = true;
             // if the scc has successors
             if (!sccGraph->getSuccessorSCCs(scc).empty()) {
                 computeTopologicalOrdering(scc, visited);
             }
         }
     }
 }
  
 void TopologicallySortedSCCGraphAnalysis::print(std::ostream& os) const {
     os << "--- partial order of strata as list of pairs ---" << std::endl;
     for (size_t sccIndex = 0; sccIndex < sccOrder.size(); sccIndex++) {
         const auto& successorSccs = sccGraph->getSuccessorSCCs(sccOrder.at(sccIndex));
         // use a self-loop to indicate that an SCC has no successors or predecessors
         if (successorSccs.empty() && sccGraph->getPredecessorSCCs(sccOrder.at(sccIndex)).empty()) {
             os << sccIndex << " " << sccIndex << std::endl;

References computeTopologicalOrdering(), souffle::ast::analysis::SCCGraphAnalysis::getPredecessorSCCs(), souffle::ast::analysis::SCCGraphAnalysis::getSuccessorSCCs(), sccGraph, and sccOrder.

Here is the call graph for this function:

◆ sccOfIndex()

size_t souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::sccOfIndex ( const size_t index ) const

inline

Definition at line 61 of file TopologicallySortedSCCGraph.h.

63 {

◆ topologicalOrderingCost()

int souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::topologicalOrderingCost ( const std::vector< size_t > & permutationOfSCCs ) const

private

Calculate the topological ordering cost of a permutation of as of yet unordered SCCs using the ordered SCCs.

Returns -1 if the given vector is not a valid topological ordering.

Definition at line 39 of file TopologicallySortedSCCGraph.cpp.

                                                                                                         {
         // if the index of the current scc is after the end of the ordered partition
         if (it_i >= it_k) {
             // check that the index of all predecessor sccs of are before the index of the current scc
             for (auto scc : sccGraph->getPredecessorSCCs(*it_i)) {
                 if (std::find(permutationOfSCCs.begin(), it_i, scc) == it_i) {
                     // if not, the sort is not a valid topological sort
                     return -1;
                 }
             }
         }
         // otherwise, calculate the cost of the current scc
         // as the number of sccs with an index before the current scc
         for (auto it_j = permutationOfSCCs.begin(); it_j != it_i; ++it_j) {
             // having some successor scc with an index after the current scc
             for (auto scc : sccGraph->getSuccessorSCCs(*it_j)) {
                 if (std::find(permutationOfSCCs.begin(), it_i, scc) == it_i) {
                     costOfSCC++;
                 }
             }
         }
         // and if this cost is greater than the maximum recorded cost for the whole permutation so far,
         // set the cost of the permutation to it
         if (costOfSCC > costOfPermutation) {
             costOfPermutation = costOfSCC;
         }
     }
     return costOfPermutation;
 }
  
 void TopologicallySortedSCCGraphAnalysis::computeTopologicalOrdering(size_t scc, std::vector<bool>& visited) {
     // create a flag to indicate that a successor was visited (by default it hasn't been)
     bool found = false;
     bool hasUnvisitedSuccessor = false;
     bool hasUnvisitedPredecessor = false;
     // for each successor of the input scc
     const auto& successorsToVisit = sccGraph->getSuccessorSCCs(scc);