souffle  2.0.2-371-g6315b36
IfConversion.cpp
Go to the documentation of this file.
1 /*
2  * Souffle - A Datalog Compiler
3  * Copyright (c) 2018, The Souffle Developers. All rights reserved
4  * Licensed under the Universal Permissive License v 1.0 as shown at:
5  * - https://opensource.org/licenses/UPL
6  * - <souffle root>/licenses/SOUFFLE-UPL.txt
7  */
8 
9 /************************************************************************
10  *
11  * @file IfConversion.cpp
12  *
13  ***********************************************************************/
14 
16 #include "ram/Condition.h"
17 #include "ram/Expression.h"
18 #include "ram/Node.h"
19 #include "ram/Operation.h"
20 #include "ram/Program.h"
21 #include "ram/Relation.h"
22 #include "ram/Statement.h"
23 #include "ram/utility/Visitor.h"
25 #include <algorithm>
26 #include <cstddef>
27 #include <functional>
28 #include <utility>
29 #include <vector>
30 
31 namespace souffle::ram::transform {
32 
33 Own<Operation> IfConversionTransformer::rewriteIndexScan(const IndexScan* indexScan) {
34  // check whether tuple is used in subsequent operations
35  bool tupleNotUsed = true;
36  visitDepthFirst(*indexScan, [&](const TupleElement& element) {
37  if (element.getTupleId() == indexScan->getTupleId()) {
38  tupleNotUsed = false;
39  }
40  });
41 
42  // if not used, transform the IndexScan operation to an existence check
43  if (tupleNotUsed) {
44  // replace IndexScan with an Filter/Existence check
45  VecOwn<Expression> newValues;
46 
47  size_t arity = indexScan->getRangePattern().first.size();
48  for (size_t i = 0; i < arity; ++i) {
49  if (*(indexScan->getRangePattern().first[i]) != *(indexScan->getRangePattern().second[i])) {
50  return nullptr;
51  }
52  }
53 
54  for (auto& cur : indexScan->getRangePattern().second) {
55  Expression* val = nullptr;
56  if (cur != nullptr) {
57  val = cur->clone();
58  }
59  newValues.emplace_back(val);
60  }
61 
62  // check if there is a break statement nested in the Scan - if so, remove it
63  Operation* newOp;
64  if (const auto* breakOp = dynamic_cast<const Break*>(&indexScan->getOperation())) {
65  newOp = breakOp->getOperation().clone();
66  } else {
67  newOp = indexScan->getOperation().clone();
68  }
69 
70  return mk<Filter>(mk<ExistenceCheck>(indexScan->getRelation(), std::move(newValues)),
71  Own<Operation>(newOp), indexScan->getProfileText());
72  }
73  return nullptr;
74 }
75 
76 bool IfConversionTransformer::convertIndexScans(Program& program) {
77  bool changed = false;
78  visitDepthFirst(program, [&](const Query& query) {
79  std::function<Own<Node>(Own<Node>)> scanRewriter = [&](Own<Node> node) -> Own<Node> {
80  if (const IndexScan* scan = dynamic_cast<IndexScan*>(node.get())) {
81  if (Own<Operation> op = rewriteIndexScan(scan)) {
82  changed = true;
83  node = std::move(op);
84  }
85  }
86  node->apply(makeLambdaRamMapper(scanRewriter));
87  return node;
88  };
89  const_cast<Query*>(&query)->apply(makeLambdaRamMapper(scanRewriter));
90  });
91  return changed;
92 }
93 
94 } // namespace souffle::ram::transform
souffle::ram::transform
Definition: ChoiceConversion.cpp:30
souffle::ram::Query
A relational algebra query.
Definition: Query.h:50
souffle::ram::transform::IfConversionTransformer::convertIndexScans
bool convertIndexScans(Program &program)
Apply if-conversion to the whole program.
Definition: IfConversion.cpp:80
souffle::ram::transform::Transformer::apply
bool apply(TranslationUnit &translationUnit)
@Brief apply the transformer to a translation unit @Param translationUnit that will be transformed.
Definition: Transformer.cpp:39
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
MiscUtil.h
Program.h
Visitor.h
i
size_t i
Definition: json11.h:663
Relation.h
Condition.h
souffle::ram::IndexScan
Search for tuples of a relation matching a criteria.
Definition: IndexScan.h:52
souffle::ram::Expression::clone
Expression * clone() const override=0
Create a clone (i.e.
Node.h
Operation.h
Statement.h
IfConversion.h
Expression.h
souffle::ram::visitDepthFirst
void visitDepthFirst(const Node &root, Visitor< R, Ps... > &visitor, Args &... args)
A utility function visiting all nodes within the RAM fragments rooted by the given node recursively i...
Definition: Visitor.h:357
souffle::VecOwn
std::vector< Own< A > > VecOwn
Definition: ContainerUtil.h:45
souffle::ram::Expression
Abstract class for describing scalar values in RAM.
Definition: Expression.h:33
souffle::ram::transform::IfConversionTransformer::rewriteIndexScan
Own< Operation > rewriteIndexScan(const IndexScan *indexScan)
Rewrite IndexScan operations.
Definition: IfConversion.cpp:37
souffle::ram::makeLambdaRamMapper
LambdaNodeMapper< Lambda > makeLambdaRamMapper(const Lambda &lambda)
Creates a node mapper based on a corresponding lambda expression.
Definition: LambdaNodeMapper.h:67