souffle  2.0.2-371-g6315b36
ChoiceConversion.h
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 ChoiceConversion.h
12  *
13  ***********************************************************************/
14 
15 #pragma once
16 
17 #include "ram/IndexScan.h"
18 #include "ram/Operation.h"
19 #include "ram/Program.h"
20 #include "ram/Scan.h"
21 #include "ram/TranslationUnit.h"
22 #include "ram/analysis/Level.h"
24 #include <memory>
25 #include <string>
26 
27 namespace souffle::ram::transform {
28 
29 /**
30  * @class ChoiceConversionTransformer
31  * @brief Convert (Scan/If)/(IndexScan/If) operaitons to
32  * (Choice)/(IndexChoice) operations
33 
34  * If there exists Scan/IndexScan operations in the RAM, and the
35  * variables are used in a subsequent Filter operation but no
36  * subsequent operation in the tree (up until and including
37  * the Project), the operations are rewritten to Choice/IndexChoice
38  * operations.
39  *
40  * For example,
41  *
42  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~
43  * QUERY
44  * ...
45  * FOR t1 IN A ON INDEX t1.x=10 AND t1.y = 20
46  * IF (t1.x, t1.y) NOT IN A
47  * ... // no occurrence of t1
48  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~
49  *
50  * will be rewritten to
51  *
52  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~
53  * QUERY
54  * ...
55  * CHOICE A AS t1 ON INDEX t1.x=10 AND t1.y = 20
56  * WHERE (t1.x, t1.y) NOT IN A
57  * ...
58  * ~~~~~~~~~~~~~~~~~~~~~~~~~~~
59  *
60  */
61 class ChoiceConversionTransformer : public Transformer {
62 public:
63  std::string getName() const override {
64  return "ChoiceConversionTransformer";
65  }
66 
67  /**
68  * @brief Rewrite Scan operations
69  * @param A scan operation
70  * @result The old operation if the if-conversion fails; otherwise the Choice operation
71  *
72  * Rewrites Scan/If pair to a Choice operation if value
73  * is not used in a consecutive RAM operation
74  */
75  Own<Operation> rewriteScan(const Scan* scan);
76 
77  /**
78  * @brief Rewrite IndexScan operations
79  * @param An index operation
80  * @result The old operation if the if-conversion fails; otherwise the IndexChoice operation
81  *
82  * Rewrites IndexScan/If pair to an IndexChoice operation if value
83  * is not used in a consecutive RAM operation
84  */
85  Own<Operation> rewriteIndexScan(const IndexScan* indexScan);
86 
87  /**
88  * @brief Apply choice-conversion to the whole program
89  * @param RAM program
90  * @result A flag indicating whether the RAM program has been changed.
91  *
92  * Search for queries and rewrite their Scan/IndexScan and If operations if possible.
93  */
94  bool convertScans(Program& program);
95 
96 protected:
97  analysis::LevelAnalysis* rla{nullptr};
98  bool transform(TranslationUnit& translationUnit) override {
99  rla = translationUnit.getAnalysis<analysis::LevelAnalysis>();
100  return convertScans(translationUnit.getProgram());
101  }
102 };
103 
104 } // namespace souffle::ram::transform
souffle::ram::transform
Definition: ChoiceConversion.cpp:30
souffle::ram::Program
RAM program relation declaration and functions.
Definition: Program.h:58
souffle::ram::TranslationUnit::getAnalysis
Analysis * getAnalysis() const
Get an analysis.
Definition: TranslationUnit.h:66
Scan.h
souffle::ram::transform::ChoiceConversionTransformer::transform
bool transform(TranslationUnit &translationUnit) override
@Brief transform the translation unit / used by apply @Param translationUnit that will be transformed...
Definition: ChoiceConversion.h:102
souffle::ram::analysis::LevelAnalysis
A Ram Analysis for determining the level of a expression/condition.
Definition: Level.h:51
souffle::Own
std::unique_ptr< A > Own
Definition: ContainerUtil.h:42
souffle::ram::transform::ChoiceConversionTransformer::getName
std::string getName() const override
@Brief get name of the transformer
Definition: ChoiceConversion.h:67
souffle::ram::transform::ChoiceConversionTransformer::rewriteIndexScan
Own< Operation > rewriteIndexScan(const IndexScan *indexScan)
Rewrite IndexScan operations.
Definition: ChoiceConversion.cpp:68
Program.h
souffle::ram::TranslationUnit::getProgram
Program & getProgram() const
Get the RAM Program of the translation unit
Definition: TranslationUnit.h:107
souffle::ram::TranslationUnit
Translating a RAM program.
Definition: TranslationUnit.h:55
IndexScan.h
souffle::ram::transform::ChoiceConversionTransformer::rla
analysis::LevelAnalysis * rla
Definition: ChoiceConversion.h:101
souffle::ram::transform::ChoiceConversionTransformer::convertScans
bool convertScans(Program &program)
Apply choice-conversion to the whole program.
Definition: ChoiceConversion.cpp:116
TranslationUnit.h
Transformer.h
souffle::ram::Scan
Iterate all tuples of a relation.
Definition: Scan.h:47
souffle::ram::IndexScan
Search for tuples of a relation matching a criteria.
Definition: IndexScan.h:52
souffle::ram::transform::ChoiceConversionTransformer::rewriteScan
Own< Operation > rewriteScan(const Scan *scan)
Rewrite Scan operations.
Definition: ChoiceConversion.cpp:36
Operation.h
Level.h