87b5fd2f62db98b5fd5ab7cb244108f198eb8360
[scilab.git] / scilab / modules / ast / includes / analysis / gvn / GVN.hxx
1 /*
2  *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
3  *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
4  *
5  *  This file must be used under the terms of the CeCILL.
6  *  This source file is licensed as described in the file COPYING, which
7  *  you should have received as part of this distribution.  The terms
8  *  are also available at
9  *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
10  *
11  */
12
13 #ifndef __GVN_HXX__
14 #define __GVN_HXX__
15
16 #include <string>
17 #include <list>
18 #include <map>
19 #include <unordered_map>
20
21 #include "MultivariatePolynomial.hxx"
22 #include "OpValue.hxx"
23 #include "symbol.hxx"
24 #include "dynlib_ast.h"
25
26 namespace analysis
27 {
28
29 /**
30  * \class GVN
31  * \brief GVN stands for Global Value Numbering
32  *
33  * This class implements a GVN but it is extended to track common expressions represented
34  * by multivariate polynomials.
35  * Symbolic calculus is allowed with integer values (such as matrix dimensions)
36  *
37  * All the pointers GVN::Value* returned by the GVN have the same lifetime than the GVN itself.
38  * For information, the GVN::Value are stored in unordered_map (or multimap) or list.
39  *
40  */
41 class EXTERN_AST GVN
42 {
43
44 public:
45
46     /**
47      * \struct Value
48      * \brief Represents a value and polynomial
49      */
50     struct Value
51     {
52         uint64_t value;
53         const MultivariatePolynomial * poly;
54
55         Value(const uint64_t _value) : value(_value), poly(nullptr) { }
56
57         friend inline std::ostream & operator<<(std::ostream & out, const Value & v)
58         {
59             out << "Value: " << v.value
60                 << ", Poly: ";
61             if (v.poly)
62             {
63                 out << *v.poly;
64             }
65             else
66             {
67                 out << "null";
68             }
69             return out;
70         }
71
72         inline bool operator==(const Value & R) const
73         {
74             return value == R.value;
75         }
76
77         inline bool operator!=(const Value & R) const
78         {
79             return value != R.value;
80         }
81     };
82
83 private:
84
85     typedef std::unordered_map<OpValue, Value, OpValue::Hash, OpValue::Eq> MapValues;
86     typedef std::unordered_map<int64_t, Value> MapInt64;
87     typedef std::multimap<symbol::Symbol, Value> MapSymbols;
88     typedef std::unordered_map<MultivariatePolynomial, Value *, MultivariatePolynomial::Hash, MultivariatePolynomial::Eq> MapPolys;
89     typedef std::list<Value> ListValues;
90
91     MapValues mapv;
92     MapInt64 mapi64;
93     MapSymbols maps;
94     MapPolys mapp;
95     ListValues list;
96
97     uint64_t current;
98
99 public:
100
101     // WARNING: current MUST be initialized with 0 and nothing else !
102     // (because when mpoly are evaluated with a std::vector<MP> the index begins to 0)
103     /**
104      * \brief constructor
105      */
106     GVN() : current(0)
107     {
108     }
109
110     /**
111      * \brief Clear all the maps used in the GVN
112      */
113     void clear();
114
115     /**
116      * \brief Get current value
117      */
118     uint64_t getCurrentValue() const;
119
120     /**
121     * \brief Inserts a value associated with a polynomial
122     * \param mp a polynomial
123     * \param value a value
124     */
125     void insertValue(const MultivariatePolynomial & mp, Value & value);
126
127     /**
128      * \brief Associated a symbol with a polynomial
129      * \param sym a symbol
130      * \param mp a polynomial
131      */
132     void setValue(const symbol::Symbol & sym, const MultivariatePolynomial & mp);
133
134     /**
135      * \brief Associated a symbol with a Value
136      * \param sym a symbol
137      * \param LV a value
138      */
139     void setValue(const symbol::Symbol & sym, const Value & LV);
140
141     /**
142      * \brief Get a value
143      * \return a Value
144      */
145     Value * getValue();
146
147     /**
148      * \brief Get a value associated with a polynomial
149      * \param mp a polynomial
150      * \return a Value
151      */
152     Value * getValue(const MultivariatePolynomial & mp);
153
154     /**
155      * \brief Get a value associated with a symbol
156      * \param sym a symbol
157      * \return a Value
158      */
159     Value * getValue(const symbol::Symbol & sym);
160
161     /**
162      * \brief Get a value associated with a symbol
163      * \param sym a symbol
164      * \return a Value
165      */
166     Value * getExistingValue(const symbol::Symbol & sym);
167
168     /**
169      * \brief Get a value associated with a double
170      * \param x a double
171      * \return a Value
172      */
173     Value * getValue(const double x);
174
175     /**
176      * \brief Get a value associated with an unary operation applyed to a value
177      * \param kind the kind of the operation
178      * \param LV a Value
179      * \return a Value
180      */
181     Value * getValue(const OpValue::Kind kind, const Value & LV);
182
183     /**
184      * \brief Get a value associated with a binary operation applyed to two values
185      * \param kind the kind of the operation
186      * \param LV a Value (Left)
187      * \param RV a Value (Right)
188      * \return a Value
189      */
190     Value * getValue(const OpValue::Kind kind, const Value & LV, const Value & RV);
191
192     /**
193      * \brief Get a map containing association between symbol names and value (as ULL)
194      * \return a map
195      */
196     std::map<std::string, uint64_t> getSymMap() const;
197
198     /**
199      * \brief Overload of the operator << for GVN
200      */
201     EXTERN_AST friend std::ostream & operator<<(std::ostream & out, const GVN & gvn);
202
203 private:
204
205     /**
206      * \brief Get a value associated with a polynomial which is the result of an operation
207      * \param mp a polynomial
208      * \param ov an operation
209      * \return a Value
210      */
211     Value * getValue(const MultivariatePolynomial & mp, const OpValue & ov);
212
213     /**
214      * \brief Helper function to get the result of an unary operation applyed to the polynomial associated with a value
215      * \param OPER the operation
216      * \param LV a value
217      * \param ov the operation kind
218      * \return a Value
219      */
220     Value * getValue(MultivariatePolynomial(OPER)(const MultivariatePolynomial & mp), const Value & LV, const OpValue & ov);
221
222     /**
223      * \brief Helper function to get the result of a binary operation applyed to the polynomials associated with two values
224      * \param OPER the operation
225      * \param LV a value (Left)
226      * \param RV a value (Right)
227      * \param ov the operation kind
228      * \return a Value
229      */
230     Value * getValue(MultivariatePolynomial(OPER)(const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP), const Value & LV, const Value & RV, const OpValue & ov);
231
232 };
233
234 } // namespace analysis
235
236 #endif // __GVN_HXX__