Convert (Scan/If)/(IndexScan/If) operaitons to (Choice)/(IndexChoice) operations. More...

#include <ChoiceConversion.h>

Inheritance diagram for souffle::ram::transform::ChoiceConversionTransformer:

Collaboration diagram for souffle::ram::transform::ChoiceConversionTransformer:

Public Member Functions
bool	convertScans (Program &program)
	Apply choice-conversion to the whole program. More...

std::string	getName () const override
	@Brief get name of the transformer More...

Own< Operation >	rewriteIndexScan (const IndexScan *indexScan)
	Rewrite IndexScan operations. More...

Own< Operation >	rewriteScan (const Scan *scan)
	Rewrite Scan operations. More...

Public Member Functions inherited from souffle::ram::transform::Transformer
bool	apply (TranslationUnit &translationUnit)
	@Brief apply the transformer to a translation unit @Param translationUnit that will be transformed. More...

virtual	~Transformer ()=default

Protected Member Functions
bool	transform (TranslationUnit &translationUnit) override
	@Brief transform the translation unit / used by apply @Param translationUnit that will be transformed. More...

Protected Attributes
analysis::LevelAnalysis *	rla {nullptr}

Detailed Description

Convert (Scan/If)/(IndexScan/If) operaitons to (Choice)/(IndexChoice) operations.

If there exists Scan/IndexScan operations in the RAM, and the variables are used in a subsequent Filter operation but no subsequent operation in the tree (up until and including the Project), the operations are rewritten to Choice/IndexChoice operations.

For example,

QUERY
 ...
  FOR t1 IN A ON INDEX t1.x=10 AND t1.y = 20
   IF (t1.x, t1.y) NOT IN A
        ... // no occurrence of t1

will be rewritten to

QUERY
 ...
  CHOICE A AS t1 ON INDEX t1.x=10 AND t1.y = 20
  WHERE (t1.x, t1.y) NOT IN A
    ...

Definition at line 65 of file ChoiceConversion.h.

Member Function Documentation

◆ convertScans()

bool souffle::ram::transform::ChoiceConversionTransformer::convertScans ( Program & program )

Apply choice-conversion to the whole program.

Parameters

RAM program

Returns: A flag indicating whether the RAM program has been changed.

Search for queries and rewrite their Scan/IndexScan and If operations if possible.

Definition at line 116 of file ChoiceConversion.cpp.

                                                                     {
                 if (Own<Operation> op = rewriteScan(scan)) {
                     changed = true;
                     node = std::move(op);
                 }
             } else if (const IndexScan* indexScan = dynamic_cast<IndexScan*>(node.get())) {
                 if (Own<Operation> op = rewriteIndexScan(indexScan)) {
                     changed = true;
                     node = std::move(op);
                 }
             }
             node->apply(makeLambdaRamMapper(scanRewriter));
  
             return node;
         };
         const_cast<Query*>(&query)->apply(makeLambdaRamMapper(scanRewriter));
     });
  
     return changed;
 }
  
 }  // namespace souffle::ram::transform

References rewriteScan().

Here is the call graph for this function:

◆ getName()

std::string souffle::ram::transform::ChoiceConversionTransformer::getName ( ) const

inlineoverridevirtual

@Brief get name of the transformer

Implements souffle::ram::transform::Transformer.

Definition at line 67 of file ChoiceConversion.h.

96 :

97 analysis::LevelAnalysis* rla{nullptr};

◆ rewriteIndexScan()

Own< Operation > souffle::ram::transform::ChoiceConversionTransformer::rewriteIndexScan ( const IndexScan * indexScan )

Rewrite IndexScan operations.

Parameters

An	index operation

Returns: The old operation if the if-conversion fails; otherwise the IndexChoice operation

Rewrites IndexScan/If pair to an IndexChoice operation if value is not used in a consecutive RAM operation

Definition at line 68 of file ChoiceConversion.cpp.

                                                                                       {
         // Check that the Filter uses the identifier in the IndexScan
         if (rla->getLevel(&filter->getCondition()) == indexScan->getTupleId()) {
             transformTuple = true;
  
             // Check that the filter is not referred to after
             const auto* nextNode = dynamic_cast<const Node*>(&filter->getOperation());
  
             visitDepthFirst(*nextNode, [&](const TupleElement& element) {
                 if (element.getTupleId() == indexScan->getTupleId()) {
                     transformTuple = false;
                 }
             });
         }
     }
  
     // Convert the IndexScan/If pair into an IndexChoice
     if (transformTuple) {
         RamPattern newValues;
         const auto* filter = dynamic_cast<const Filter*>(&indexScan->getOperation());
         const int identifier = indexScan->getTupleId();
         const std::string& rel = indexScan->getRelation();
  
         for (auto& cur : indexScan->getRangePattern().first) {
             Expression* val = nullptr;
             if (cur != nullptr) {
                 val = cur->clone();
             }
             newValues.first.emplace_back(val);
         }
         for (auto& cur : indexScan->getRangePattern().second) {
             Expression* val = nullptr;
             if (cur != nullptr) {
                 val = cur->clone();
             }
             newValues.second.emplace_back(val);
         }
  
         return mk<IndexChoice>(rel, identifier, souffle::clone(&filter->getCondition()), std::move(newValues),
                 souffle::clone(&filter->getOperation()), indexScan->getProfileText());
     }
     return nullptr;
 }
  
 bool ChoiceConversionTransformer::convertScans(Program& program) {
     bool changed = false;
     visitDepthFirst(program, [&](const Query& query) {

References souffle::filter(), souffle::ram::analysis::LevelAnalysis::getLevel(), souffle::ram::TupleElement::getTupleId(), rla, and souffle::ram::visitDepthFirst().

Here is the call graph for this function:

◆ rewriteScan()

Own< Operation > souffle::ram::transform::ChoiceConversionTransformer::rewriteScan ( const Scan * scan )

Rewrite Scan operations.

Parameters

A	scan operation

Returns: The old operation if the if-conversion fails; otherwise the Choice operation

Rewrites Scan/If pair to a Choice operation if value is not used in a consecutive RAM operation

Definition at line 36 of file ChoiceConversion.cpp.

                                                                                  {
         // Check that the Filter uses the identifier in the Scan
         if (rla->getLevel(&filter->getCondition()) == scan->getTupleId()) {
             transformTuple = true;
  
             // Check that the filter is not referred to after
             const auto* nextNode = dynamic_cast<const Node*>(&filter->getOperation());
  
             visitDepthFirst(*nextNode, [&](const TupleElement& element) {
                 if (element.getTupleId() == scan->getTupleId()) {
                     transformTuple = false;
                 }
             });
         }
     }
  
     // Convert the Scan/If pair into a Choice
     if (transformTuple) {
         VecOwn<Expression> newValues;
         const auto* filter = dynamic_cast<const Filter*>(&scan->getOperation());
         const int identifier = scan->getTupleId();
  
         return mk<Choice>(scan->getRelation(), identifier, souffle::clone(&filter->getCondition()),
                 souffle::clone(&filter->getOperation()), scan->getProfileText());
     }
     return nullptr;
 }
  
 Own<Operation> ChoiceConversionTransformer::rewriteIndexScan(const IndexScan* indexScan) {
     bool transformTuple = false;
  