Analysis pass computing the strongly connected component (SCC) graph for the datalog program. More...

#include <SCCGraph.h>

Inheritance diagram for souffle::ast::analysis::SCCGraphAnalysis:

Collaboration diagram for souffle::ast::analysis::SCCGraphAnalysis:

Public Member Functions
std::set< const Relation * >	getExternalNonOutputPredecessorRelations (const size_t scc) const
	Get all external non-output predecessor relations of a given SCC. More...

std::set< const Relation * >	getExternalOutputPredecessorRelations (const size_t scc) const
	Get all external output predecessor relations of a given SCC. More...

std::set< const Relation * >	getExternalPredecessorRelations (const size_t scc) const
	Get all external predecessor relations of a given SCC. More...

std::set< const Relation * >	getInternalInputRelations (const size_t scc) const
	Get all internal input relations of a given SCC. More...

std::set< const Relation * >	getInternalNonOutputRelationsWithExternalSuccessors (const size_t scc) const
	Get all internal non-output relations of a given SCC with external successors. More...

std::set< const Relation * >	getInternalOutputRelations (const size_t scc) const
	Get all internal output relations of a given SCC. More...

const std::set< const Relation * > &	getInternalRelations (const size_t scc) const
	Get all internal relations of a given SCC. More...

std::set< const Relation * >	getInternalRelationsWithExternalSuccessors (const size_t scc) const
	Get all internal relations of a given SCC with external successors. More...

size_t	getNumberOfSCCs () const
	Get the number of SCCs in the graph. More...

std::set< size_t >	getPredecessorSCCs (const Relation *relation) const
	Get all SCCs containing a predecessor of a given relation. More...

const std::set< size_t > &	getPredecessorSCCs (const size_t scc) const
	Get all predecessor SCCs of a given SCC. More...

size_t	getSCC (const Relation *rel) const
	Get the SCC of the given relation. More...

std::set< size_t >	getSuccessorSCCs (const Relation *relation) const
	Get all SCCs containing a successor of a given relation. More...

const std::set< size_t > &	getSuccessorSCCs (const size_t scc) const
	Get all successor SCCs of a given SCC. More...

bool	isRecursive (const size_t scc) const
	Return if the given SCC is recursive. More...

void	print (std::ostream &os) const override
	Print the SCC graph. More...

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

	SCCGraphAnalysis ()

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 = "scc-graph"

Private Member Functions
void	scR (const Relation relation, std::map< const Relation , size_t > &preOrder, size_t &counter, std::stack< const Relation * > &S, std::stack< const Relation * > &P, size_t &numSCCs)
	Recursive scR method for computing SCC. More...

Private Attributes
IOTypeAnalysis *	ioType = nullptr

PrecedenceGraphAnalysis *	precedenceGraph = nullptr

std::vector< std::set< size_t > >	predecessors
	Predecessor set for the SCC graph. More...

std::map< const Relation *, size_t >	relationToScc
	Map from node number to SCC number. More...

std::vector< std::set< const Relation * > >	sccToRelation
	Relations contained in a SCC. More...

std::vector< std::set< size_t > >	successors
	Adjacency lists for the SCC graph. More...

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

Detailed Description

Analysis pass computing the strongly connected component (SCC) graph for the datalog program.

Definition at line 50 of file SCCGraph.h.

Constructor & Destructor Documentation

◆ SCCGraphAnalysis()

souffle::ast::analysis::SCCGraphAnalysis::SCCGraphAnalysis ( )

inline

Definition at line 54 of file SCCGraph.h.

56 {

References rel(), and relationToScc.

Here is the call graph for this function:

Member Function Documentation

◆ getExternalNonOutputPredecessorRelations()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getExternalNonOutputPredecessorRelations ( const size_t scc ) const

inline

Get all external non-output predecessor relations of a given SCC.

Definition at line 123 of file SCCGraph.h.

                                                                                     {
         std::set<const Relation*> externPreds;
         for (const auto& relation : getInternalRelations(scc)) {
             for (const auto& predecessor : precedenceGraph->graph().predecessors(relation)) {
                 if (relationToScc.at(predecessor) != scc) {
                     externPreds.insert(predecessor);

◆ getExternalOutputPredecessorRelations()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getExternalOutputPredecessorRelations ( const size_t scc ) const

inline

Get all external output predecessor relations of a given SCC.

Definition at line 110 of file SCCGraph.h.

                                                                                              {
         std::set<const Relation*> externNonOutPreds;
         for (const auto& relation : getInternalRelations(scc)) {
             for (const auto& predecessor : precedenceGraph->graph().predecessors(relation)) {
                 if (relationToScc.at(predecessor) != scc && !ioType->isOutput(predecessor)) {
                     externNonOutPreds.insert(predecessor);

◆ getExternalPredecessorRelations()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getExternalPredecessorRelations ( const size_t scc ) const

inline

Get all external predecessor relations of a given SCC.

Definition at line 136 of file SCCGraph.h.

                                                                                {
         std::set<const Relation*> internOuts;
         for (const auto& relation : getInternalRelations(scc)) {
             if (ioType->isOutput(relation)) {
                 internOuts.insert(relation);
             }

◆ getInternalInputRelations()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getInternalInputRelations ( const size_t scc ) const

inline

Get all internal input relations of a given SCC.

Definition at line 190 of file SCCGraph.h.

                                              {
         const std::set<const Relation*>& sccRelations = sccToRelation.at(scc);
         if (sccRelations.size() == 1) {
             const Relation* singleRelation = *sccRelations.begin();
             if (precedenceGraph->graph().predecessors(singleRelation).count(singleRelation) == 0u) {
                 return false;

◆ getInternalNonOutputRelationsWithExternalSuccessors()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getInternalNonOutputRelationsWithExternalSuccessors ( const size_t scc ) const

inline

Get all internal non-output relations of a given SCC with external successors.

Definition at line 174 of file SCCGraph.h.

                                                                               {
         std::set<const Relation*> internIns;
         for (const auto& relation : getInternalRelations(scc)) {
             if (ioType->isInput(relation)) {
                 internIns.insert(relation);
             }

◆ getInternalOutputRelations()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getInternalOutputRelations ( const size_t scc ) const

inline

Get all internal output relations of a given SCC.

Definition at line 149 of file SCCGraph.h.

                                                                                                {
         std::set<const Relation*> internsWithExternSuccs;
         for (const auto& relation : getInternalRelations(scc)) {
             for (const auto& successor : precedenceGraph->graph().successors(relation)) {
                 if (relationToScc.at(successor) != scc) {
                     internsWithExternSuccs.insert(relation);

◆ getInternalRelations()

const std::set<const Relation*>& souffle::ast::analysis::SCCGraphAnalysis::getInternalRelations ( const size_t scc ) const

inline

Get all internal relations of a given SCC.

Definition at line 105 of file SCCGraph.h.

                                          : precedenceGraph->graph().predecessors(relation)) {
                 if (relationToScc.at(predecessor) != scc && ioType->isOutput(predecessor)) {
                     externOutPreds.insert(predecessor);

References ioType, souffle::ast::analysis::IOTypeAnalysis::isOutput(), and relationToScc.

Here is the call graph for this function:

◆ getInternalRelationsWithExternalSuccessors()

std::set<const Relation*> souffle::ast::analysis::SCCGraphAnalysis::getInternalRelationsWithExternalSuccessors ( const size_t scc ) const

inline

Get all internal relations of a given SCC with external successors.

Definition at line 160 of file SCCGraph.h.

                                                                                                         {
         std::set<const Relation*> internNonOutsWithExternSuccs;
         for (const auto& relation : getInternalRelations(scc)) {
             if (!ioType->isOutput(relation)) {
                 for (const auto& successor : precedenceGraph->graph().successors(relation)) {
                     if (relationToScc.at(successor) != scc) {

◆ getNumberOfSCCs()

size_t souffle::ast::analysis::SCCGraphAnalysis::getNumberOfSCCs ( ) const

inline

Get the number of SCCs in the graph.

Definition at line 59 of file SCCGraph.h.

61 {

References successors.

◆ getPredecessorSCCs() [1/2]

std::set<size_t> souffle::ast::analysis::SCCGraphAnalysis::getPredecessorSCCs ( const Relation * relation ) const

inline

Get all SCCs containing a predecessor of a given relation.

Definition at line 92 of file SCCGraph.h.

                                                                                 {
         return sccToRelation.at(scc);
     }
  
     /** Get all external output predecessor relations of a given SCC. */
     std::set<const Relation*> getExternalOutputPredecessorRelations(const size_t scc) const {

◆ getPredecessorSCCs() [2/2]

const std::set<size_t>& souffle::ast::analysis::SCCGraphAnalysis::getPredecessorSCCs ( const size_t scc ) const

inline

Get all predecessor SCCs of a given SCC.

Definition at line 74 of file SCCGraph.h.

                                    : precedenceGraph->graph().successors(relation)) {
             const auto successorScc = relationToScc.at(successor);
             if (successorScc != scc) {

References relationToScc.

Referenced by souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::run(), and souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::topologicalOrderingCost().

◆ getSCC()

size_t souffle::ast::analysis::SCCGraphAnalysis::getSCC ( const Relation * rel ) const

inline

Get the SCC of the given relation.

Definition at line 64 of file SCCGraph.h.

66 {

References predecessors.

◆ getSuccessorSCCs() [1/2]

std::set<size_t> souffle::ast::analysis::SCCGraphAnalysis::getSuccessorSCCs ( const Relation * relation ) const

inline

Get all SCCs containing a successor of a given relation.

Definition at line 79 of file SCCGraph.h.

                                                                       {
         std::set<size_t> predecessorSccs;
         const auto scc = relationToScc.at(relation);
         for (const auto& predecessor : precedenceGraph->graph().predecessors(relation)) {
             const auto predecessorScc = relationToScc.at(predecessor);
             if (predecessorScc != scc) {

◆ getSuccessorSCCs() [2/2]

const std::set<size_t>& souffle::ast::analysis::SCCGraphAnalysis::getSuccessorSCCs ( const size_t scc ) const

inline

Get all successor SCCs of a given SCC.

Definition at line 69 of file SCCGraph.h.

71 {

References relation, and relationToScc.

Referenced by souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::run(), and souffle::ast::analysis::TopologicallySortedSCCGraphAnalysis::topologicalOrderingCost().

◆ isRecursive()

bool souffle::ast::analysis::SCCGraphAnalysis::isRecursive ( const size_t scc ) const

inline

Return if the given SCC is recursive.

Definition at line 201 of file SCCGraph.h.

        :
     PrecedenceGraphAnalysis* precedenceGraph = nullptr;
  
     /** Map from node number to SCC number */

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

◆ print()

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

overridevirtual

Print the SCC graph.

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

Definition at line 124 of file SCCGraph.cpp.

                                                          { out << rel->getQualifiedName(); });
         ss << "\" ];" << std::endl;
     }
     for (size_t scc = 0; scc < getNumberOfSCCs(); scc++) {
         for (auto succ : getSuccessorSCCs(scc)) {
             ss << "\t" << name << "_" << scc << " -> " << name << "_" << succ << ";" << std::endl;
         }
     }
     ss << "}";
     printHTMLGraph(os, ss.str(), getName());
 }
  
 }  // namespace souffle::ast::analysis

References rel().

Here is the call graph for this function:

◆ run()

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

overridevirtual

run analysis for a Ast translation unit

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

Definition at line 44 of file SCCGraph.cpp.

                                   : relations) {
         relationToScc[relation] = preOrder[relation] = (size_t)-1;
     }
     for (const Relation* relation : relations) {
         if (preOrder[relation] == (size_t)-1) {
             scR(relation, preOrder, counter, S, P, numSCCs);
         }
     }
  
     /* Build SCC graph */
     successors.resize(numSCCs);
     predecessors.resize(numSCCs);
     for (const Relation* u : relations) {
         for (const Relation* v : precedenceGraph->graph().predecessors(u)) {
             auto scc_u = relationToScc[u];
             auto scc_v = relationToScc[v];
             assert(scc_u < numSCCs && "Wrong range");
             assert(scc_v < numSCCs && "Wrong range");
             if (scc_u != scc_v) {
                 predecessors[scc_u].insert(scc_v);
                 successors[scc_v].insert(scc_u);
             }
         }
     }
  
     /* Store the relations for each SCC */
     sccToRelation.resize(numSCCs);
     for (const Relation* relation : relations) {
         sccToRelation[relationToScc[relation]].insert(relation);
     }
 }
  
 /* Compute strongly connected components using Gabow's algorithm (cf. Algorithms in
  * Java by Robert Sedgewick / Part 5 / Graph *  algorithms). The algorithm has linear
  * runtime. */
 void SCCGraphAnalysis::scR(const Relation* w, std::map<const Relation*, size_t>& preOrder, size_t& counter,
         std::stack<const Relation*>& S, std::stack<const Relation*>& P, size_t& numSCCs) {
     preOrder[w] = counter++;
     S.push(w);

References relation, and relationToScc.

◆ scR()

void souffle::ast::analysis::SCCGraphAnalysis::scR	(	const Relation *	relation,
		std::map< const Relation *, size_t > &	preOrder,
		size_t &	counter,
		std::stack< const Relation * > &	S,
		std::stack< const Relation * > &	P,
		size_t &	numSCCs
	)

private

Recursive scR method for computing SCC.

Definition at line 95 of file SCCGraph.cpp.

                                                    {
             while (preOrder[P.top()] > preOrder[t]) {
                 P.pop();
             }
         }
     }
     if (P.top() == w) {
         P.pop();
     } else {
         return;
     }
  
     const Relation* v;
     do {
         v = S.top();
         S.pop();
         relationToScc[v] = numSCCs;
     } while (v != w);
     numSCCs++;
 }
  
 void SCCGraphAnalysis::print(std::ostream& os) const {
     const std::string& name = Global::config().get("name");
     std::stringstream ss;
     /* Print SCC graph */
     ss << "digraph {" << std::endl;
     /* Print nodes of SCC graph */
     for (size_t scc = 0; scc < getNumberOfSCCs(); scc++) {

Field Documentation

◆ ioType

IOTypeAnalysis* souffle::ast::analysis::SCCGraphAnalysis::ioType = nullptr

private

Definition at line 234 of file SCCGraph.h.

Referenced by getInternalRelations().

◆ name

constexpr const char* souffle::ast::analysis::SCCGraphAnalysis::name = "scc-graph"

staticconstexpr

Definition at line 52 of file SCCGraph.h.

◆ precedenceGraph

PrecedenceGraphAnalysis* souffle::ast::analysis::SCCGraphAnalysis::precedenceGraph = nullptr

private

Definition at line 216 of file SCCGraph.h.

◆ predecessors

std::vector<std::set<size_t> > souffle::ast::analysis::SCCGraphAnalysis::predecessors

private

Predecessor set for the SCC graph.

Definition at line 225 of file SCCGraph.h.

Referenced by getSCC().

◆ relationToScc

std::map<const Relation*, size_t> souffle::ast::analysis::SCCGraphAnalysis::relationToScc

private

Map from node number to SCC number.

Definition at line 219 of file SCCGraph.h.

Referenced by getInternalRelations(), getPredecessorSCCs(), getSuccessorSCCs(), run(), and SCCGraphAnalysis().

◆ sccToRelation

std::vector<std::set<const Relation*> > souffle::ast::analysis::SCCGraphAnalysis::sccToRelation

private

Relations contained in a SCC.

Definition at line 228 of file SCCGraph.h.

◆ successors

std::vector<std::set<size_t> > souffle::ast::analysis::SCCGraphAnalysis::successors

private

Adjacency lists for the SCC graph.

Definition at line 222 of file SCCGraph.h.

Referenced by getNumberOfSCCs().

The documentation for this class was generated from the following files:

ast/analysis/SCCGraph.h
ast/analysis/SCCGraph.cpp

Public Member Functions

Static Public Attributes

Private Member Functions

Private Attributes

Additional Inherited Members

Detailed Description

Constructor & Destructor Documentation

◆ SCCGraphAnalysis()

Member Function Documentation

◆ getExternalNonOutputPredecessorRelations()

◆ getExternalOutputPredecessorRelations()

◆ getExternalPredecessorRelations()

◆ getInternalInputRelations()

◆ getInternalNonOutputRelationsWithExternalSuccessors()

◆ getInternalOutputRelations()

◆ getInternalRelations()

◆ getInternalRelationsWithExternalSuccessors()

◆ getNumberOfSCCs()

◆ getPredecessorSCCs() [1/2]

◆ getPredecessorSCCs() [2/2]

◆ getSCC()

◆ getSuccessorSCCs() [1/2]

◆ getSuccessorSCCs() [2/2]

◆ isRecursive()

◆ print()

◆ run()

◆ scR()

Field Documentation

◆ ioType

◆ name

◆ precedenceGraph

◆ predecessors

◆ relationToScc

◆ sccToRelation

◆ successors