souffle::ast::transform::MagicSetTransformer Class Reference

Magic Set Transformation. More...

#include <MagicSet.h>

Inheritance diagram for souffle::ast::transform::MagicSetTransformer:

Collaboration diagram for souffle::ast::transform::MagicSetTransformer:

Data Structures
class	AdornDatabaseTransformer
	Database adornment. More...
class	LabelDatabaseTransformer
	Database labeller. More...
class	MagicSetCoreTransformer
	Core section of the magic set transformer. More...
class	NormaliseDatabaseTransformer
	Database normaliser for MST. More...

Public Member Functions
MagicSetTransformer *	clone () const override
std::string	getName () const override
	MagicSetTransformer ()
Public Member Functions inherited from souffle::ast::transform::PipelineTransformer
PipelineTransformer *	clone () const override
void	disableTransformers (const std::set< std::string > &transforms) override
std::string	getName () const override
std::vector< Transformer * >	getSubtransformers () const override
template<typename... Args>
	PipelineTransformer (Args... args)
	PipelineTransformer (VecOwn< Transformer > pipeline)
void	setDebugReport () override
void	setVerbosity (bool verbose) override
Public Member Functions inherited from souffle::ast::transform::MetaTransformer
bool	applySubtransformer (TranslationUnit &translationUnit, Transformer *transformer)
Public Member Functions inherited from souffle::ast::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
virtual	~Transformer ()=default

Private Member Functions
bool	transform (TranslationUnit &tu) override

Static Private Member Functions
static std::set< QualifiedName >	getRelationsToNotLabel (const TranslationUnit &tu)
	Gets the set of relations to not label. More...
static std::set< QualifiedName >	getStronglyIgnoredRelations (const TranslationUnit &tu)
	Gets the set of relations to strongly ignore during the MST process. More...
static std::set< QualifiedName >	getTriviallyIgnoredRelations (const TranslationUnit &tu)
	Gets the set of relations that are trivially computable, and so should not be magic-set. More...
static std::set< QualifiedName >	getWeaklyIgnoredRelations (const TranslationUnit &tu)
	Gets the set of relations to weakly ignore during the MST process. More...
static bool	shouldRun (const TranslationUnit &tu)
	Determines whether any part of the MST should be run. More...

Additional Inherited Members
Protected Member Functions inherited from souffle::ast::transform::PipelineTransformer
bool	transform (TranslationUnit &translationUnit) override
Protected Attributes inherited from souffle::ast::transform::PipelineTransformer
VecOwn< Transformer >	pipeline
Protected Attributes inherited from souffle::ast::transform::MetaTransformer
bool	verbose = false

Detailed Description

Magic Set Transformation.

Involves four stages: (1) NormaliseDatabaseTransformer, for assumptions to hold (2) LabelDatabaseTransformer, to support negation (3) AdornDatabaseTransformer, to annotate information flow (4) MagicSetCoreTransformer, to perform the core magifying transformation

Definition at line 51 of file MagicSet.h.

Constructor & Destructor Documentation

MagicSetTransformer()

souffle::ast::transform::MagicSetTransformer::MagicSetTransformer ( )

inline

Definition at line 58 of file MagicSet.h.

            : PipelineTransformer(mk<NormaliseDatabaseTransformer>(), mk<LabelDatabaseTransformer>(),
                      mk<RemoveRedundantRelationsTransformer>(), mk<AdornDatabaseTransformer>(),
                      mk<RemoveRedundantRelationsTransformer>(), mk<MagicSetCoreTransformer>()) {}

Referenced by clone().

Member Function Documentation

clone()

MagicSetTransformer* souffle::ast::transform::MagicSetTransformer::clone ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::MetaTransformer.

Definition at line 67 of file MagicSet.h.

                                                {
        return new MagicSetTransformer();
    }

References MagicSetTransformer().

Here is the call graph for this function:

getName()

std::string souffle::ast::transform::MagicSetTransformer::getName ( ) const

inlineoverridevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 63 of file MagicSet.h.

                                       {
        return "MagicSetTransformer";
    }

getRelationsToNotLabel()

std::set< QualifiedName > souffle::ast::transform::MagicSetTransformer::getRelationsToNotLabel ( const TranslationUnit &  tu )

staticprivate

Gets the set of relations to not label.

The union of strongly and trivially ignored.

Definition at line 270 of file MagicSet.cpp.

                                                             {
    const Program& program = tu.getProgram();
    if (Global::config().has("magic-transform")) return true;
    for (const auto* rel : program.getRelations()) {
        if (rel->hasQualifier(RelationQualifier::MAGIC)) return true;

getStronglyIgnoredRelations()

std::set< QualifiedName > souffle::ast::transform::MagicSetTransformer::getStronglyIgnoredRelations ( const TranslationUnit &  tu )

staticprivate

Gets the set of relations to strongly ignore during the MST process.

Strongly-ignored relations cannot be safely duplicated without affecting semantics.

Definition at line 219 of file MagicSet.cpp.

                            : program.getClauses()) {
        bool containsCounter = false;
        visitDepthFirst(*clause, [&](const Counter& /* counter */) { containsCounter = true; });
        if (containsCounter) {
            stronglyIgnoredRelations.insert(clause->getHead()->getQualifiedName());
        }
    }
 
    bool fixpointReached = false;
    while (!fixpointReached) {
        fixpointReached = true;
        // - To prevent poslabelling issues, all dependent strata should also be strongly ignored
        std::set<QualifiedName> dependentRelations;
        for (const auto& relName : stronglyIgnoredRelations) {
            precedenceGraph.visitDepthFirst(getRelation(program, relName), [&](const auto* dependentRel) {
                dependentRelations.insert(dependentRel->getQualifiedName());
            });
        }
        for (const auto& depRel : dependentRelations) {
            if (!contains(stronglyIgnoredRelations, depRel)) {
                fixpointReached = false;
                stronglyIgnoredRelations.insert(depRel);
            }
        }
 
        // - Since we can't duplicate the rules, nothing should be labelled in the bodies as well
        std::set<QualifiedName> bodyRelations;
        for (const auto& relName : stronglyIgnoredRelations) {
            for (const auto* clause : relDetail.getClauses(relName)) {
                visitDepthFirst(
                        *clause, [&](const Atom& atom) { bodyRelations.insert(atom.getQualifiedName()); });
            }
        }
        for (const auto& bodyRel : bodyRelations) {
            if (!contains(stronglyIgnoredRelations, bodyRel)) {
                fixpointReached = false;
                stronglyIgnoredRelations.insert(bodyRel);
            }
        }
    }
 
    return stronglyIgnoredRelations;
}
 
std::set<QualifiedName> MagicSetTransformer::getRelationsToNotLabel(const TranslationUnit& tu) {
    std::set<QualifiedName> result;
    for (const auto& name : getTriviallyIgnoredRelations(tu)) {
        result.insert(name);
    }

References souffle::ast::visitDepthFirst().

Here is the call graph for this function:

getTriviallyIgnoredRelations()

std::set< QualifiedName > souffle::ast::transform::MagicSetTransformer::getTriviallyIgnoredRelations ( const TranslationUnit &  tu )

staticprivate

Gets the set of relations that are trivially computable, and so should not be magic-set.

Definition at line 70 of file MagicSet.cpp.

                   : program.getRelations()) {
        // Input relations
        if (ioTypes.isInput(rel)) {
            triviallyIgnoredRelations.insert(rel->getQualifiedName());
            continue;
        }
 
        // Any relations not dependent on any atoms
        bool hasRules = false;
        for (const auto* clause : getClauses(program, rel->getQualifiedName())) {
            visitDepthFirst(clause->getBodyLiterals(), [&](const Atom& /* atom */) { hasRules = true; });
        }
        if (!hasRules) {
            triviallyIgnoredRelations.insert(rel->getQualifiedName());
        }
    }
 
    return triviallyIgnoredRelations;
}
 
std::set<QualifiedName> MagicSetTransformer::getWeaklyIgnoredRelations(const TranslationUnit& tu) {
    const auto& program = tu.getProgram();
    const auto& precedenceGraph = tu.getAnalysis<analysis::PrecedenceGraphAnalysis>()->graph();
    const auto& polyAnalysis = *tu.getAnalysis<analysis::PolymorphicObjectsAnalysis>();
    std::set<QualifiedName> weaklyIgnoredRelations;

References souffle::ast::getClauses(), rel(), and souffle::ast::visitDepthFirst().

Here is the call graph for this function:

getWeaklyIgnoredRelations()

std::set< QualifiedName > souffle::ast::transform::MagicSetTransformer::getWeaklyIgnoredRelations ( const TranslationUnit &  tu )

staticprivate

Gets the set of relations to weakly ignore during the MST process.

Weakly-ignored relations cannot be adorned/magic'd. Superset of strongly-ignored relations.

Definition at line 96 of file MagicSet.cpp.

                            : configRels) {
        std::vector<std::string> qualifiers = splitString(relStr, '.');
        specifiedRelations.push_back(QualifiedName(qualifiers));
    }
 
    // Pick up specified relations from relation tags
    for (const auto* rel : program.getRelations()) {
        if (rel->hasQualifier(RelationQualifier::MAGIC)) {
            specifiedRelations.push_back(rel->getQualifiedName());
        }
    }
 
    // Get the complement if not everything is magic'd
    if (!contains(configRels, "*")) {
        for (const Relation* rel : program.getRelations()) {
            if (!contains(specifiedRelations, rel->getQualifiedName())) {
                weaklyIgnoredRelations.insert(rel->getQualifiedName());
            }
        }
    }
 
    // - Add trivially computable relations
    for (const auto& relName : getTriviallyIgnoredRelations(tu)) {
        weaklyIgnoredRelations.insert(relName);
    }
 
    // - Any relation with a neglabel
    visitDepthFirst(program, [&](const Atom& atom) {
        const auto& qualifiers = atom.getQualifiedName().getQualifiers();
        if (!qualifiers.empty() && qualifiers[0] == "@neglabel") {
            weaklyIgnoredRelations.insert(atom.getQualifiedName());
        }
    });
 
    // - Any relation with a clause containing float-related binary constraints
    const std::set<BinaryConstraintOp> floatOps(
            {BinaryConstraintOp::FEQ, BinaryConstraintOp::FNE, BinaryConstraintOp::FLE,
                    BinaryConstraintOp::FGE, BinaryConstraintOp::FLT, BinaryConstraintOp::FGT});
    for (const auto* clause : program.getClauses()) {
        visitDepthFirst(*clause, [&](const BinaryConstraint& bc) {
            if (contains(floatOps, polyAnalysis.getOverloadedOperator(&bc))) {
                weaklyIgnoredRelations.insert(clause->getHead()->getQualifiedName());
            }
        });
    }
 
    // - Any relation with a clause containing order-dependent functors
    const std::set<FunctorOp> orderDepFuncOps(
            {FunctorOp::MOD, FunctorOp::FDIV, FunctorOp::DIV, FunctorOp::UMOD});
    for (const auto* clause : program.getClauses()) {
        visitDepthFirst(*clause, [&](const IntrinsicFunctor& functor) {
            if (contains(orderDepFuncOps, polyAnalysis.getOverloadedFunctionOp(&functor))) {
                weaklyIgnoredRelations.insert(clause->getHead()->getQualifiedName());
            }
        });
    }
 
    // - Any eqrel relation
    for (auto* rel : program.getRelations()) {
        if (rel->getRepresentation() == RelationRepresentation::EQREL) {
            weaklyIgnoredRelations.insert(rel->getQualifiedName());
        }
    }
 
    // - Any relation with execution plans
    for (auto* clause : program.getClauses()) {
        if (clause->getExecutionPlan() != nullptr) {
            weaklyIgnoredRelations.insert(clause->getHead()->getQualifiedName());
        }
    }
 
    // - Any atom appearing in a clause containing a counter
    for (auto* clause : program.getClauses()) {
        bool containsCounter = false;
        visitDepthFirst(*clause, [&](const Counter& /* counter */) { containsCounter = true; });
        if (containsCounter) {
            visitDepthFirst(*clause,
                    [&](const Atom& atom) { weaklyIgnoredRelations.insert(atom.getQualifiedName()); });
        }
    }
 
    // - Deal with strongly ignored relations
    const auto& stronglyIgnoredRelations = getStronglyIgnoredRelations(tu);
 
    // Add them in directly
    for (const auto& relName : stronglyIgnoredRelations) {
        weaklyIgnoredRelations.insert(relName);
    }
 
    // Add in any atoms whose magic rules might cause a need for neglabelling
    //  - Essentially, suppose R is strongly-ignored and A depends on R. Then, we must weakly ignore
    //    any relation that appears after A in any clause, otherwise a magic-set might be created that
    //    requires R to be neglabelled.
    for (const auto& relName : stronglyIgnoredRelations) {
        precedenceGraph.visitDepthFirst(getRelation(program, relName), [&](const auto* dependentRel) {
            const auto& depName = dependentRel->getQualifiedName();
            for (const auto* clause : program.getClauses()) {
                const auto& atoms = getBodyLiterals<Atom>(*clause);
                bool startIgnoring = false;
                for (const auto& atom : atoms) {
                    startIgnoring |= (atom->getQualifiedName() == depName);
                    if (startIgnoring) {
                        weaklyIgnoredRelations.insert(atom->getQualifiedName());
                    }
                }
            }
        });
    }
 
    return weaklyIgnoredRelations;
}
 
std::set<QualifiedName> MagicSetTransformer::getStronglyIgnoredRelations(const TranslationUnit& tu) {
    const auto& program = tu.getProgram();
    const auto& relDetail = *tu.getAnalysis<analysis::RelationDetailCacheAnalysis>();
    const auto& precedenceGraph = tu.getAnalysis<analysis::PrecedenceGraphAnalysis>()->graph();
    std::set<QualifiedName> stronglyIgnoredRelations;

shouldRun()

bool souffle::ast::transform::MagicSetTransformer::shouldRun ( const TranslationUnit &  tu )

staticprivate

Determines whether any part of the MST should be run.

Definition at line 281 of file MagicSet.cpp.

                                                                             {
    bool changed = false;
 
    /** (1) Partition input and output relations */
    changed |= partitionIO(translationUnit);

Referenced by transform().

transform()

bool souffle::ast::transform::MagicSetTransformer::transform ( TranslationUnit &  tu )

inlineoverrideprivatevirtual

Implements souffle::ast::transform::Transformer.

Definition at line 72 of file MagicSet.h.

                                                 {
        return shouldRun(tu) ? PipelineTransformer::transform(tu) : false;
    }

References shouldRun(), and souffle::ast::transform::PipelineTransformer::transform().

Here is the call graph for this function:

---

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

• ast/transform/MagicSet.h
• ast/transform/MagicSet.cpp