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