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