souffle::ast::transform::ResolveAliasesTransformer Class Reference

Transformation pass to eliminate grounded aliases. More...

#include <ResolveAliases.h>

Inheritance diagram for souffle::ast::transform::ResolveAliasesTransformer:

Collaboration diagram for souffle::ast::transform::ResolveAliasesTransformer:

Public Member Functions
ResolveAliasesTransformer *	clone () const override
std::string	getName () const override
Public Member Functions inherited from souffle::ast::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
virtual	~Transformer ()=default

Static Public Member Functions
static Own< Clause >	removeComplexTermsInAtoms (const Clause &clause)
	Removes complex terms in atoms, replacing them with constrained variables. More...
static Own< Clause >	removeTrivialEquality (const Clause &clause)
	Removes trivial equalities of the form t = t from the given clause. More...
static Own< Clause >	resolveAliases (const Clause &clause)
	Converts the given clause into a version without variables aliasing grounded variables. More...

Private Member Functions
bool	transform (TranslationUnit &translationUnit) override

Detailed Description

Transformation pass to eliminate grounded aliases.

e.g. resolve: a(r) , r = [x,y] => a(x,y) e.g. resolve: a(x) , !b(y) , y = x => a(x) , !b(x)

Definition at line 35 of file ResolveAliases.h.

Member Function Documentation

clone()

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

inlineoverridevirtual

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

Definition at line 70 of file ResolveAliases.h.

getName()

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

inlineoverridevirtual

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

Definition at line 41 of file ResolveAliases.h.

                                                      {

removeComplexTermsInAtoms()

Own< Clause > souffle::ast::transform::ResolveAliasesTransformer::removeComplexTermsInAtoms ( const Clause &  clause )

static

Removes complex terms in atoms, replacing them with constrained variables.

Parameters

clause

the clause to be processed

Returns

a modified clone of the processed clause

Definition at line 389 of file ResolveAliases.cpp.

                          : atoms) {
        for (const Argument* arg : atom->getArguments()) {
            // ignore if not a functor
            if (!isA<Functor>(arg)) {
                continue;
            }
 
            // add this functor if not seen yet
            if (!any_of(terms, [&](const Argument* cur) { return *cur == *arg; })) {
                terms.push_back(arg);
            }
        }
    }
 
    // find all functors in records too
    visitDepthFirst(atoms, [&](const RecordInit& rec) {
        for (const Argument* arg : rec.getArguments()) {
            // ignore if not a functor
            if (!isA<Functor>(arg)) {
                continue;
            }
 
            // add this functor if not seen yet
            if (!any_of(terms, [&](const Argument* cur) { return *cur == *arg; })) {
                terms.push_back(arg);
            }
        }
    });
 
    // substitute them with new variables (a real map would compare pointers)
    using substitution_map = std::vector<std::pair<Own<Argument>, Own<ast::Variable>>>;
    substitution_map termToVar;
 
    static int varCounter = 0;
    for (const Argument* arg : terms) {
        // create a new mapping for this term
        auto term = souffle::clone(arg);
        auto newVariable = mk<ast::Variable>(" _tmp_" + toString(varCounter++));
        termToVar.push_back(std::make_pair(std::move(term), std::move(newVariable)));
    }
 
    // apply mapping to replace the terms with the variables
    struct Update : public NodeMapper {
        const substitution_map& map;
 
        Update(const substitution_map& map) : map(map) {}
 
        Own<Node> operator()(Own<Node> node) const override {
            // check whether node needs to be replaced
            for (const auto& pair : map) {
                auto& term = pair.first;
                auto& variable = pair.second;
 
                if (*term == *node) {
                    return souffle::clone(variable);
                }
            }
 
            // continue recursively
            node->apply(*this);
            return node;
        }
    };
 
    // update atoms
    Update update(termToVar);
    for (Atom* atom : atoms) {
        atom->apply(update);
    }
 
    // add the necessary variable constraints to the clause
    for (const auto& pair : termToVar) {
        auto& term = pair.first;
        auto& variable = pair.second;
 
        res->addToBody(
                mk<BinaryConstraint>(BinaryConstraintOp::EQ, souffle::clone(variable), souffle::clone(term)));
    }
 
    return res;
}
 
bool ResolveAliasesTransformer::transform(TranslationUnit& translationUnit) {
    bool changed = false;
    Program& program = translationUnit.getProgram();
 
    // get all clauses
    std::vector<const Clause*> clauses;

References souffle::any_of().

Here is the call graph for this function:

removeTrivialEquality()

Own< Clause > souffle::ast::transform::ResolveAliasesTransformer::removeTrivialEquality ( const Clause &  clause )

static

Removes trivial equalities of the form t = t from the given clause.

Parameters

clause

the clause to be processed

Returns

a modified clone of the given clause

Definition at line 368 of file ResolveAliases.cpp.

                                                               {
                if (*constraint->getLHS() == *constraint->getRHS()) {
                    continue;  // skip this one
                }
            }
        }
 
        res->addToBody(souffle::clone(literal));
    }
 
    // done
    return res;
}
 
Own<Clause> ResolveAliasesTransformer::removeComplexTermsInAtoms(const Clause& clause) {
    Own<Clause> res(clause.clone());
 
    // get list of atoms
    std::vector<Atom*> atoms = getBodyLiterals<Atom>(*res);
 

resolveAliases()

Own< Clause > souffle::ast::transform::ResolveAliasesTransformer::resolveAliases ( const Clause &  clause )

static

Converts the given clause into a version without variables aliasing grounded variables.

Parameters

clause

the clause to be processed

Returns

a modified clone of the processed clause

Definition at line 214 of file ResolveAliases.cpp.

                                          { return isA<RecordInit>(&arg); };
 
    // tests whether something is a multi-result functor
    auto isMultiResultFunctor = [&](const Argument& arg) {
        const auto* inf = dynamic_cast<const IntrinsicFunctor*>(&arg);
        if (inf == nullptr) return false;
        return analysis::FunctorAnalysis::isMultiResult(*inf);
    };
 
    // tests whether a value `a` occurs in a term `b`
    auto occurs = [](const Argument& a, const Argument& b) {
        bool res = false;
        visitDepthFirst(b, [&](const Argument& arg) { res = (res || (arg == a)); });
        return res;
    };
 
    // variables appearing as functorless arguments in atoms or records should not
    // be resolved
    std::set<std::string> baseGroundedVariables;
    for (const auto* atom : getBodyLiterals<Atom>(clause)) {
        for (const Argument* arg : atom->getArguments()) {
            if (const auto* var = dynamic_cast<const ast::Variable*>(arg)) {
                baseGroundedVariables.insert(var->getName());
            }
        }
        visitDepthFirst(*atom, [&](const RecordInit& rec) {
            for (const Argument* arg : rec.getArguments()) {
                if (const auto* var = dynamic_cast<const ast::Variable*>(arg)) {
                    baseGroundedVariables.insert(var->getName());
                }
            }
        });
    }
 
    // I) extract equations
    std::vector<Equation> equations;
    visitDepthFirst(clause, [&](const BinaryConstraint& constraint) {
        if (isEqConstraint(constraint.getBaseOperator())) {
            equations.push_back(Equation(constraint.getLHS(), constraint.getRHS()));
        }
    });
 
    // II) compute unifying substitution
    Substitution substitution;
 
    // a utility for processing newly identified mappings
    auto newMapping = [&](const std::string& var, const Argument* term) {
        // found a new substitution
        Substitution newMapping(var, term);
 
        // apply substitution to all remaining equations
        for (auto& equation : equations) {
            equation.apply(newMapping);
        }
 
        // add mapping v -> t to substitution
        substitution.append(newMapping);
    };
 
    while (!equations.empty()) {
        // get next equation to compute
        Equation equation = equations.back();
        equations.pop_back();
 
        // shortcuts for left/right
        const Argument& lhs = *equation.lhs;
        const Argument& rhs = *equation.rhs;
 
        // #1:  t = t   => skip
        if (lhs == rhs) {
            continue;
        }
 
        // #2:  [..] = [..]  => decompose
        if (isRec(lhs) && isRec(rhs)) {
            // get arguments
            const auto& lhs_args = static_cast<const RecordInit&>(lhs).getArguments();
            const auto& rhs_args = static_cast<const RecordInit&>(rhs).getArguments();
 
            // make sure sizes are identical
            assert(lhs_args.size() == rhs_args.size() && "Record lengths not equal");
 
            // create new equalities
            for (size_t i = 0; i < lhs_args.size(); i++) {
                equations.push_back(Equation(lhs_args[i], rhs_args[i]));
            }
 
            continue;
        }
 
        // #3:  neither is a variable    => skip
        if (!isVar(lhs) && !isVar(rhs)) {
            continue;
        }
 
        // #4:  v = w    => add mapping
        if (isVar(lhs) && isVar(rhs)) {
            auto& var = static_cast<const ast::Variable&>(lhs);
            newMapping(var.getName(), &rhs);
            continue;
        }
 
        // #5:  t = v   => swap
        if (!isVar(lhs)) {
            equations.push_back(Equation(rhs, lhs));
            continue;
        }
 
        // now we know lhs is a variable
        assert(isVar(lhs));
 
        // therefore, we have v = t
        const auto& v = static_cast<const ast::Variable&>(lhs);
        const Argument& t = rhs;
 
        // #6:  t is a multi-result functor => skip
        if (isMultiResultFunctor(t)) {
            continue;
        }
 
        // #7:  v occurs in t   => skip
        if (occurs(v, t)) {
            continue;
        }
 
        assert(!occurs(v, t));
 
        // #8:  t is a record   => add mapping
        if (isRec(t)) {
            newMapping(v.getName(), &t);
            continue;
        }
 
        // #9:  v is already grounded   => skip
        auto pos = baseGroundedVariables.find(v.getName());
        if (pos != baseGroundedVariables.end()) {
            continue;
        }
 
        // add new mapping
        newMapping(v.getName(), &t);
    }
 
    // III) compute resulting clause
    return substitution(souffle::clone(&clause));
}
 
Own<Clause> ResolveAliasesTransformer::removeTrivialEquality(const Clause& clause) {
    Own<Clause> res(cloneHead(&clause));
 
    // add all literals, except filtering out t = t constraints
    for (Literal* literal : clause.getBodyLiterals()) {
        if (auto* constraint = dynamic_cast<BinaryConstraint*>(literal)) {

transform()

bool souffle::ast::transform::ResolveAliasesTransformer::transform ( TranslationUnit &  translationUnit )

overrideprivatevirtual

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

Definition at line 479 of file ResolveAliases.cpp.

                                : getClauses(program, rel)) {
            clauses.push_back(clause);
        }
    });
 
    // clean all clauses
    for (const Clause* clause : clauses) {
        // -- Step 1 --
        // get rid of aliases
        Own<Clause> noAlias = resolveAliases(*clause);
 
        // clean up equalities
        Own<Clause> cleaned = removeTrivialEquality(*noAlias);
 
        // -- Step 2 --
        // restore simple terms in atoms
        Own<Clause> normalised = removeComplexTermsInAtoms(*cleaned);
 
        // swap if changed
        if (*normalised != *clause) {
            changed = true;
            program.removeClause(clause);
            program.addClause(std::move(normalised));
        }
    }
 
    return changed;
}
 
}  // namespace souffle::ast::transform

References clauses.

---

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

• ast/transform/ResolveAliases.h
• ast/transform/ResolveAliases.cpp