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 __INFERENCE_CONSTRAINT_HXX__
17 #define __INFERENCE_CONSTRAINT_HXX__
18 
19 #include <cmath>
20 #include <iostream>
21 #include <unordered_set>
22 #include <vector>
23 
24 #include "GVN.hxx"
25 #include "tools.hxx"
26 
27 namespace analysis
28 {
29 
30 struct MPolyConstraint;
31 struct MPolyConstraintSet;
32 
33 struct InferenceConstraint
34 {
35     enum Result
36     {
37         RESULT_TRUE, RESULT_FALSE, RESULT_DUNNO
38     };
39 
40     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const = 0;
41     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const = 0;
applyConstraintsanalysis::InferenceConstraint42     virtual void applyConstraints(const std::vector<GVN::Value *> & /*values*/) const { }
43 
getArgsanalysis::InferenceConstraint44     inline static std::vector<const MultivariatePolynomial *> getArgs(const std::vector<GVN::Value *> & values)
45     {
46         std::vector<const MultivariatePolynomial *> args;
47         args.reserve(values.size());
48         for (const auto value : values)
49         {
50             args.emplace_back(value->poly);
51         }
52         return args;
53     }
54 
applyEqualityanalysis::InferenceConstraint55     inline static void applyEquality(GVN::Value & x, GVN::Value & y)
56     {
57         if (x != y)
58         {
59             if (x.poly->polynomial.size() < y.poly->polynomial.size())
60             {
61                 y = x;
62             }
63             else
64             {
65                 x = y;
66             }
67         }
68     }
69 };
70 
71 struct SameDimsConstraint : public InferenceConstraint
72 {
73     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
74     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
75     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
76 };
77 
78 struct EqualConstraint : public InferenceConstraint
79 {
80     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
81     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
82     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
83 };
84 
85 struct PositiveConstraint : public InferenceConstraint
86 {
87     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
88     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
89     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
90 };
91 
92 struct StrictPositiveConstraint : public InferenceConstraint
93 {
94     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
95     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
96     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
97 };
98 
99 struct GreaterConstraint : public InferenceConstraint
100 {
101     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
102     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
103     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
104 };
105 
106 struct StrictGreaterConstraint : public InferenceConstraint
107 {
108     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
109     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
110     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
111 };
112 
113 struct ValidIndexConstraint : public InferenceConstraint
114 {
115     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
116     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
117     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
118 };
119 
120 struct ValidRangeConstraint : public InferenceConstraint
121 {
122     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const /*override*/;
123     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
124     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const /*override*/;
125 };
126 
127 struct MPolyConstraint : public InferenceConstraint
128 {
129     enum Kind
130     {
131         EQ0, NEQ0, GT0, GEQ0
132     };
133 
134     MultivariatePolynomial poly;
135     Kind kind;
136 
MPolyConstraintanalysis::MPolyConstraint137     MPolyConstraint(const MultivariatePolynomial & _poly, const Kind _kind) : poly(_poly), kind(_kind)
138     {
139         int64_t common;
140         if (poly.getCommonCoeff(common) && common != 1 && common != 0)
141         {
142             if (kind == EQ0)
143             {
144                 poly /= common;
145             }
146             else
147             {
148                 poly /= std::abs(common);
149             }
150         }
151     }
152 
isConstantanalysis::MPolyConstraint153     inline bool isConstant() const
154     {
155         return poly.isConstant();
156     }
157 
158     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const override;
159     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const override;
160     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const override;
161 
162     struct Hash
163     {
operator ()analysis::MPolyConstraint::Hash164         inline std::size_t operator()(const MPolyConstraint & mpc) const
165         {
166             return tools::hash_combine(mpc.kind, mpc.poly.hash());
167         }
168     };
169 
operator ==analysis::MPolyConstraint170     inline bool operator==(const MPolyConstraint & R) const
171     {
172         return kind == R.kind && poly == R.poly;
173     }
174 
175     struct Eq
176     {
operator ()analysis::MPolyConstraint::Eq177         inline bool operator()(const MPolyConstraint & L, const MPolyConstraint & R) const
178         {
179             return L == R;
180         }
181     };
182 
183     friend std::wostream & operator<<(std::wostream & out, const MPolyConstraint & mpc);
184 };
185 
186 struct MPolyConstraintSet : public InferenceConstraint
187 {
188     std::unordered_set<MPolyConstraint, MPolyConstraint::Hash, MPolyConstraint::Eq> constraints;
189 
MPolyConstraintSetanalysis::MPolyConstraintSet190     MPolyConstraintSet() { }
MPolyConstraintSetanalysis::MPolyConstraintSet191     MPolyConstraintSet(const unsigned int size)
192     {
193         constraints.reserve(size);
194     }
195 
addanalysis::MPolyConstraintSet196     inline void add(MPolyConstraint && mpc)
197     {
198         if (!mpc.isConstant())
199         {
200             constraints.emplace(std::move(mpc));
201         }
202     }
203 
addanalysis::MPolyConstraintSet204     inline void add(MultivariatePolynomial && poly, MPolyConstraint::Kind kind)
205     {
206         if (!poly.isConstant())
207         {
208             constraints.emplace(std::move(poly), kind);
209         }
210     }
211 
addanalysis::MPolyConstraintSet212     inline void add(const MultivariatePolynomial & poly, MPolyConstraint::Kind kind)
213     {
214         if (!poly.isConstant())
215         {
216             constraints.emplace(poly, kind);
217         }
218     }
219 
addanalysis::MPolyConstraintSet220     inline void add(const MPolyConstraintSet & set)
221     {
222         constraints.insert(set.constraints.begin(), set.constraints.end());
223     }
224 
emptyanalysis::MPolyConstraintSet225     inline bool empty() const
226     {
227         return constraints.empty();
228     }
229 
sizeanalysis::MPolyConstraintSet230     inline std::size_t size() const
231     {
232         return constraints.size();
233     }
234 
235     virtual Result check(GVN & gvn, const std::vector<GVN::Value *> & values) const override;
236     virtual MPolyConstraintSet getMPConstraints(const std::vector<GVN::Value *> & values) const override;
237     virtual void applyConstraints(const std::vector<GVN::Value *> & values) const override;
238 
239     friend std::wostream & operator<<(std::wostream & out, const MPolyConstraintSet & mpcs);
240 
241     struct Hash
242     {
operator ()analysis::MPolyConstraintSet::Hash243         inline std::size_t operator()(const MPolyConstraintSet & mpcs) const
244         {
245             std::size_t seed = 0;
246             for (const auto & c : mpcs.constraints)
247             {
248                 seed = tools::hash_combine(seed, MPolyConstraint::Hash()(c));
249             }
250             return seed;
251         }
252     };
253 
254     struct Eq
255     {
operator ()analysis::MPolyConstraintSet::Eq256         inline bool operator()(const MPolyConstraintSet & L, const MPolyConstraintSet & R) const
257         {
258             return L.constraints == R.constraints;
259         }
260     };
261 };
262 
263 
264 } // namespace analysis
265 
266 #endif // __INFERENCE_CONSTRAINT_HXX__
267