Analysis: add a GVN with symbolic calculus capacities 15/16115/2
Calixte DENIZET [Mon, 9 Mar 2015 13:11:46 +0000 (14:11 +0100)]
 * GVN = Global Value Numbering: initially it is used to find common sub-expressions in an AST
 * it has been extended to be able to make symbolic computations with symbols representing integer values
 * symbolic expressions are represented by multivariate polynpomials
 * the goal is to use it with matrice dimensions (which are unsigned integer values)
   and to be able to make some proofs on the equality between expressions related to dimensions

Change-Id: I7fb5fca1ff30eaed449f601a48bc7e494c51c2e9

23 files changed:
scilab/modules/ast/ast.vcxproj
scilab/modules/ast/ast.vcxproj.filters
scilab/modules/ast/includes/analysis/gvn/GVN.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/MultivariateMonomial.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/MultivariatePolynomial.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/OpValue.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/SymbolicDimension.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/SymbolicRange.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/TestGVNVisitor.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/gvn/VarExp.hxx [new file with mode: 0644]
scilab/modules/ast/includes/analysis/tools.hxx [new file with mode: 0644]
scilab/modules/ast/includes/exps/exp.hxx
scilab/modules/ast/includes/exps/seqexp.hxx
scilab/modules/ast/includes/exps/simplevar.hxx
scilab/modules/ast/tests/unit_tests/gvn.dia.ref [new file with mode: 0644]
scilab/modules/ast/tests/unit_tests/gvn.tst [new file with mode: 0644]
scilab/modules/functions/Makefile.am
scilab/modules/functions/Makefile.in
scilab/modules/functions/includes/functions_gw.hxx
scilab/modules/functions/sci_gateway/cpp/functions_gw.vcxproj
scilab/modules/functions/sci_gateway/cpp/functions_gw.vcxproj.filters
scilab/modules/functions/sci_gateway/cpp/sci_testGVN.cpp [new file with mode: 0644]
scilab/modules/functions/sci_gateway/functions_gateway.xml

index ccb4e61..3191828 100644 (file)
@@ -262,6 +262,14 @@ lib /DEF:"$(ProjectDir)fileio_import.def" /SUBSYSTEM:WINDOWS /MACHINE:$(Platform
     <ClInclude Include="includes\analysis\Checkers.hxx" />
     <ClInclude Include="includes\analysis\Decorator.hxx" />
     <ClInclude Include="includes\analysis\ForList.hxx" />
+    <ClInclude Include="includes\analysis\gvn\GVN.hxx" />
+    <ClInclude Include="includes\analysis\gvn\MultivariateMonomial.hxx" />
+    <ClInclude Include="includes\analysis\gvn\MultivariatePolynomial.hxx" />
+    <ClInclude Include="includes\analysis\gvn\OpValue.hxx" />
+    <ClInclude Include="includes\analysis\gvn\SymbolicDimension.hxx" />
+    <ClInclude Include="includes\analysis\gvn\SymbolicRange.hxx" />
+    <ClInclude Include="includes\analysis\gvn\TestGVNVisitor.hxx" />
+    <ClInclude Include="includes\analysis\gvn\VarExp.hxx" />
     <ClInclude Include="includes\analysis\Result.hxx" />
     <ClInclude Include="includes\analysis\SymInfo.hxx" />
     <ClInclude Include="includes\analysis\TIType.hxx" />
index 1470833..7b2025c 100644 (file)
@@ -57,6 +57,9 @@
     <Filter Include="Header Files\analysis">
       <UniqueIdentifier>{86c0db79-0efd-47e5-b679-e5d4faef469b}</UniqueIdentifier>
     </Filter>
+    <Filter Include="Header Files\analysis\gvn">
+      <UniqueIdentifier>{f05ded2d-aeba-4235-9374-99bcb9247786}</UniqueIdentifier>
+    </Filter>
   </ItemGroup>
   <ItemGroup>
     <None Include="core_Import.def">
     <ClInclude Include="includes\ast\treevisitor.hxx">
       <Filter>Header Files\ast</Filter>
     </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\GVN.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\MultivariateMonomial.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\MultivariatePolynomial.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\OpValue.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\SymbolicDimension.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\SymbolicRange.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\TestGVNVisitor.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
+    <ClInclude Include="includes\analysis\gvn\VarExp.hxx">
+      <Filter>Header Files\analysis\gvn</Filter>
+    </ClInclude>
   </ItemGroup>
   <ItemGroup>
     <ClCompile Include="src\cpp\ast\debugvisitor.cpp">
diff --git a/scilab/modules/ast/includes/analysis/gvn/GVN.hxx b/scilab/modules/ast/includes/analysis/gvn/GVN.hxx
new file mode 100644 (file)
index 0000000..ea7c4d6
--- /dev/null
@@ -0,0 +1,468 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __GVN_HXX__
+#define __GVN_HXX__
+
+#include <string>
+#include <list>
+#include <map>
+#include <unordered_map>
+
+#include "tools.hxx"
+#include "MultivariatePolynomial.hxx"
+#include "OpValue.hxx"
+#include "symbol.hxx"
+
+namespace analysis
+{
+
+/**
+ * \class GVN
+ * \brief GVN stands for Global Value Numbering
+ *
+ * This class implements a GVN but it is extended to track common expressions represented
+ * by multivariate polynomials.
+ * Symbolic calculus is allowed with integer values (such as matrix dimensions)
+ *
+ * All the pointers GVN::Value* returned by the GVN have the same lifetime than the GVN itself.
+ * For information, the GVN::Value are stored in unordered_map (or multimap) or list.
+ *
+ */
+class GVN
+{
+
+public:
+
+    /**
+     * \struct Value
+     * \brief Represents a value and polynomial
+     */
+    struct Value
+    {
+        unsigned long long value;
+        const MultivariatePolynomial * poly;
+
+        Value(const unsigned long long _value) : value(_value), poly(nullptr) { }
+
+        friend inline std::wostream & operator<<(std::wostream & out, const Value & v)
+        {
+            out << L"Value: " << v.value
+                << L", Poly: ";
+            if (v.poly)
+            {
+                out << *v.poly;
+            }
+            else
+            {
+                out << L"null";
+            }
+            return out;
+        }
+
+        inline bool operator==(const Value & R) const
+        {
+            return value == R.value;
+        }
+
+        inline bool operator!=(const Value & R) const
+        {
+            return value != R.value;
+        }
+    };
+
+private:
+
+    typedef std::unordered_map<OpValue, Value, OpValue::Hash, OpValue::Eq> MapValues;
+    typedef std::unordered_map<double, Value> MapDoubles;
+    typedef std::multimap<symbol::Symbol, Value> MapSymbols;
+    typedef std::unordered_map<MultivariatePolynomial, Value *, MultivariatePolynomial::Hash, MultivariatePolynomial::Eq> MapPolys;
+    typedef std::list<Value> ListValues;
+
+    MapValues mapv;
+    MapDoubles mapd;
+    MapSymbols maps;
+    MapPolys mapp;
+    ListValues list;
+
+    unsigned long long current;
+
+public:
+
+    // WARNING: current MUST be initialized with 0 and nothing else !
+    // (because when mpoly are evaluated with a std::vector<MP> the index begins to 0)
+    /**
+     * \brief constructor
+     */
+    GVN() : current(0)
+    {
+    }
+
+    /**
+     * \brief Clear all the maps used in the GVN
+     */
+    inline void clear()
+    {
+        mapv.clear();
+        mapd.clear();
+        maps.clear();
+        mapp.clear();
+        list.clear();
+        current = 0;
+    }
+
+    /**
+     * \brief Inserts a value associated with a polynomial
+     * \param mp a polynomial
+     * \param value a value
+     */
+    inline void insertValue(const MultivariatePolynomial & mp, Value & value)
+    {
+        MapPolys::iterator i = mapp.find(mp);
+        if (i == mapp.end())
+        {
+            value.poly = &mapp.emplace(mp, &value).first->first;
+        }
+        else
+        {
+            value.value = i->second->value;
+            value.poly = &i->first;
+        }
+    }
+
+    /**
+     * \brief Associated a symbol with a polynomial
+     * \param sym a symbol
+     * \param mp a polynomial
+     */
+    inline void setValue(const symbol::Symbol & sym, const MultivariatePolynomial & mp)
+    {
+        MapPolys::iterator i = mapp.find(mp);
+        if (i != mapp.end())
+        {
+            maps.emplace(sym, i->second->value)->second.poly = i->second->poly;
+        }
+        else
+        {
+            Value & value = maps.emplace(sym, current++)->second;
+            insertValue(mp, value);
+            if (mp.isConstant() && mapd.find(mp.constant) == mapd.end())
+            {
+                mapd.emplace(mp.constant, value);
+            }
+        }
+    }
+
+    /**
+     * \brief Associated a symbol with a Value
+     * \param sym a symbol
+     * \param LV a value
+     */
+    inline void setValue(const symbol::Symbol & sym, const Value & LV)
+    {
+        maps.emplace(sym, LV.value)->second.poly = LV.poly;
+    }
+
+    /**
+     * \brief Get an invalid value (i.e. a polynomial == NaN)
+     * \return an invalid Value
+     */
+    inline Value * getInvalid()
+    {
+        return getValue(tools::NaN());
+    }
+
+    /**
+     * \brief Get a value
+     * \return a Value
+     */
+    inline Value * getValue()
+    {
+        list.emplace_back(current);
+        Value & value = list.back();
+        insertValue(current++, value);
+
+        return &value;
+    }
+
+    /**
+     * \brief Get a value associated with a polynomial
+     * \param mp a polynomial
+     * \return a Value
+     */
+    inline Value * getValue(const MultivariatePolynomial & mp)
+    {
+        const auto i = mapp.find(mp);
+        if (i != mapp.end())
+        {
+            return i->second;
+        }
+        else
+        {
+            Value * val = getValue();
+            insertValue(mp, *val);
+
+            return val;
+        }
+    }
+
+    /**
+     * \brief Get a value associated with a symbol
+     * \param sym a symbol
+     * \return a Value
+     */
+    inline Value * getValue(const symbol::Symbol & sym)
+    {
+        const auto i = maps.equal_range(sym);
+        if (i.first == i.second)
+        {
+            Value & value = maps.emplace(sym, current)->second;
+            insertValue(current++, value);
+
+            return &value;
+        }
+        else
+        {
+            return &std::prev(i.second)->second;
+        }
+    }
+
+    /**
+     * \brief Get a value associated with a double
+     * \param x a double
+     * \return a Value
+     */
+    inline Value * getValue(const double x)
+    {
+        const auto i = mapd.find(x);
+        if (i == mapd.end())
+        {
+            Value & value = mapd.emplace(x, current++).first->second;
+            insertValue(x, value);
+
+            return &value;
+        }
+        else
+        {
+            return &i->second;
+        }
+    }
+
+    /**
+     * \brief Get a value associated with an unary operation applyed to a value
+     * \param kind the kind of the operation
+     * \param LV a Value
+     * \return a Value
+     */
+    inline Value * getValue(const OpValue::Kind kind, const Value & LV)
+    {
+        OpValue ov(kind, LV.value);
+
+        switch (kind)
+        {
+            case OpValue::UNARYMINUS :
+                return getValue([](const MultivariatePolynomial & mp)
+                {
+                    return -mp;
+                }, LV, ov);
+            default :
+                return getValue([](const MultivariatePolynomial & mp)
+                {
+                    return MultivariatePolynomial::getInvalid();
+                }, LV, ov);
+        }
+    }
+
+    /**
+     * \brief Get a value associated with a binary operation applyed to two values
+     * \param kind the kind of the operation
+     * \param LV a Value (Left)
+     * \param RV a Value (Right)
+     * \return a Value
+     */
+    inline Value * getValue(const OpValue::Kind kind, const Value & LV, const Value & RV)
+    {
+        OpValue ov(kind, LV.value, RV.value);
+
+        switch (kind)
+        {
+            case OpValue::PLUS :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return LMP + RMP;
+                }, LV, RV, ov);
+            case OpValue::MINUS :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return LMP - RMP;
+                }, LV, RV, ov);
+            case OpValue::TIMES :
+            case OpValue::DOTTIMES :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return LMP * RMP;
+                }, LV, RV, ov);
+            case OpValue::RDIV :
+            case OpValue::DOTRDIV :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return LMP / RMP;
+                }, LV, RV, ov);
+            case OpValue::POWER :
+            case OpValue::DOTPOWER :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return LMP ^ RMP;
+                }, LV, RV, ov);
+            default :
+                return getValue([](const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP)
+                {
+                    return MultivariatePolynomial::getInvalid();
+                }, LV, RV, ov);
+        }
+    }
+
+    /**
+     * \brief Get a map containing association between symbol names and value (as ULL)
+     * \return a map
+     */
+    inline std::map<std::wstring, unsigned long long> getSymMap() const
+    {
+        std::map<std::wstring, unsigned long long> map;
+        for (const auto & p : maps)
+        {
+            map.emplace(p.first.getName(), p.second.value);
+        }
+
+        return map;
+    }
+
+    /**
+     * \brief Overload of the operator << for GVN
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const GVN & gvn)
+    {
+        out << L"Constants:" << std::endl;
+        for (const auto & p : gvn.mapd)
+        {
+            out << L"  " << p.first << L" -> " << p.second.value << std::endl;
+        }
+
+        out << L"Symbols:" << std::endl;
+        for (const auto & p : gvn.maps)
+        {
+            out << L"  " << p.first << L" -> " << p.second.value << std::endl;
+        }
+
+        std::map<unsigned long long, std::wstring> map;
+        for (const auto & p : gvn.maps)
+        {
+            map.emplace(p.second.value, p.first.getName());
+        }
+
+        out << L"OpValues:" << std::endl;
+        for (const auto & p : gvn.mapv)
+        {
+            out << L"  " << p.first << L" -> " << p.second.value << L", P: " << p.second.poly->print(map) << std::endl;
+        }
+
+        // Don't remove: useful to debug
+
+        /*const bool show_collisions = true;
+        out << std::endl << L"Map polynomials stats:" << std::endl;
+        tools::printMapInfo(out, gvn.mapp, show_collisions);
+
+        out << std::endl << L"Map constants stats:" << std::endl;
+        tools::printMapInfo(out, gvn.mapd, show_collisions);
+
+        out << std::endl << L"Map values stats:" << std::endl;
+        tools::printMapInfo(out, gvn.mapv, show_collisions);*/
+
+        return out;
+    }
+
+private:
+
+    /**
+     * \brief Get a value associated with a polynomial which is the result of an operation
+     * \param mp a polynomial
+     * \param ov an operation
+     * \return a Value
+     */
+    inline Value * getValue(const MultivariatePolynomial & mp, const OpValue & ov)
+    {
+        if (mp.isConstant())
+        {
+            return getValue(mp.constant);
+        }
+        else
+        {
+            const auto j = mapp.find(mp);
+            if (j == mapp.end())
+            {
+                Value * value = &mapv.emplace(ov, current++).first->second;
+                value->poly = &mapp.emplace(mp, value).first->first;
+
+                return value;
+            }
+            else
+            {
+                return j->second;
+            }
+        }
+    }
+
+    /**
+     * \brief Helper function to get the result of an unary operation applyed to the polynomial associated with a value
+     * \param OPER the operation
+     * \param LV a value
+     * \param ov the operation kind
+     * \return a Value
+     */
+    inline Value * getValue(MultivariatePolynomial (OPER)(const MultivariatePolynomial & mp), const Value & LV, const OpValue & ov)
+    {
+        const auto i = mapv.find(ov);
+        if (i == mapv.end())
+        {
+            return getValue(OPER(*LV.poly), ov);
+        }
+        else
+        {
+            return &i->second;
+        }
+    }
+
+    /**
+     * \brief Helper function to get the result of a binary operation applyed to the polynomials associated with two values
+     * \param OPER the operation
+     * \param LV a value (Left)
+     * \param RV a value (Right)
+     * \param ov the operation kind
+     * \return a Value
+     */
+    inline Value * getValue(MultivariatePolynomial (OPER)(const MultivariatePolynomial & LMP, const MultivariatePolynomial & RMP), const Value & LV, const Value & RV, const OpValue & ov)
+    {
+        const auto i = mapv.find(ov);
+        if (i == mapv.end())
+        {
+            return getValue(OPER(*LV.poly, *RV.poly), ov);
+        }
+        else
+        {
+            return &i->second;
+        }
+    }
+};
+
+} // namespace analysis
+
+#endif // __GVN_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/MultivariateMonomial.hxx b/scilab/modules/ast/includes/analysis/gvn/MultivariateMonomial.hxx
new file mode 100644 (file)
index 0000000..d0f2254
--- /dev/null
@@ -0,0 +1,352 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __MULTIVARIATE_MONOMIAL_HXX__
+#define __MULTIVARIATE_MONOMIAL_HXX__
+
+#include <cmath>
+#include <functional>
+#include <iostream>
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+
+#include "tools.hxx"
+#include "VarExp.hxx"
+
+namespace analysis
+{
+
+/**
+ * \struct MultivariateMonomial
+ * \brief Represents a multivariate monomial
+ */
+struct MultivariateMonomial
+{
+    typedef std::set<VarExp, VarExp::Compare> Monomial;
+
+    // Since the coeff is not used to compute the hash we must set is as mutable to be able to modify it when extract
+    // from an unordered_set or unordered_map.
+    mutable double coeff;
+    Monomial monomial;
+
+    /**
+     * \brief constructor
+     * \param var the default var to put in the monomial
+     */
+    MultivariateMonomial(const unsigned long long var) : coeff(1)
+    {
+        monomial.emplace(var);
+    }
+
+    /**
+     * \brief constructor
+     * \param coeff the default coefficient for this empty monomial
+     */
+    MultivariateMonomial(const double _coeff = 1) : coeff(_coeff) { }
+
+    /**
+     * \brief copy-constructor
+     * \param mm the monomial to copy
+     */
+    MultivariateMonomial(const MultivariateMonomial & mm) : coeff(mm.coeff), monomial(mm.monomial) { }
+
+    /**
+     * Check if the variables of the monomial have an id lower or equal to max
+     * \param max an id
+     * \return true if all the variables have an id leq to max
+     */
+    inline bool checkVariable(const unsigned long long max) const
+    {
+        for (const auto & ve : monomial)
+        {
+            if (ve.var > max)
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * \brief Get the sum of the exponents in the monomial
+     * \return the total exponent
+     */
+    inline unsigned int exponent() const
+    {
+        unsigned int exp = 0;
+        for (const auto & ve : monomial)
+        {
+            exp += ve.exp;
+        }
+        return exp;
+    }
+
+    /**
+     * \brief Add a varexp in the monomial
+     * \param ve the varexp to add
+     * \return *this
+     */
+    inline MultivariateMonomial & add(const VarExp & ve)
+    {
+        Monomial::iterator i = monomial.find(ve);
+        if (i == monomial.end())
+        {
+            monomial.insert(ve);
+        }
+        else
+        {
+            i->exp += ve.exp;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Add a varexp in the monomial
+     * \param ve the varexp to add
+     * \return *this
+     */
+    inline MultivariateMonomial & add(VarExp && ve)
+    {
+        Monomial::iterator i = monomial.find(ve);
+        if (i == monomial.end())
+        {
+            monomial.emplace(std::move(ve));
+        }
+        else
+        {
+            i->exp += ve.exp;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Product of two monomials
+     * \param R the RHS monomial
+     * \return the product of *this and R
+     */
+    inline MultivariateMonomial operator*(const MultivariateMonomial & R) const
+    {
+        MultivariateMonomial res(*this);
+        res.coeff *= R.coeff;
+        for (const auto & ve : R.monomial)
+        {
+            res.add(ve);
+        }
+        return res;
+    }
+
+    /**
+     * \brief Product-assignment
+     */
+    inline MultivariateMonomial & operator*=(const MultivariateMonomial & R)
+    {
+        coeff *= R.coeff;
+        for (const auto & ve : R.monomial)
+        {
+            add(ve);
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Product by a double
+     */
+    friend inline MultivariateMonomial operator*(const double L, const MultivariateMonomial & R)
+    {
+        return R * L;
+    }
+
+    /**
+     * \brief Product by a double
+     */
+    inline MultivariateMonomial operator*(const double R) const
+    {
+        MultivariateMonomial res(*this);
+        res.coeff *= R;
+        return res;
+    }
+
+    /**
+     * \brief Product-assignment by a double
+     */
+    inline MultivariateMonomial & operator*=(const double R)
+    {
+        coeff *= R;
+        return *this;
+    }
+
+    /**
+     * \brief Division by a double
+     */
+    inline MultivariateMonomial operator/(const double R) const
+    {
+        MultivariateMonomial res(*this);
+        res.coeff /= R;
+        return res;
+    }
+
+    /**
+     * \brief Division-assignment by a double
+     */
+    inline MultivariateMonomial & operator/=(const double R)
+    {
+        coeff /= R;
+        return *this;
+    }
+
+    /**
+     * \brief Exponentation by an uint
+     */
+    inline MultivariateMonomial operator^(unsigned int R) const
+    {
+        MultivariateMonomial res(*this);
+        if (R > 1)
+        {
+            coeff = std::pow(coeff, R);
+            for (auto & ve : res.monomial)
+            {
+                ve.exp *= R;
+            }
+        }
+        return res;
+    }
+
+    /**
+     * \brief Equality
+     */
+    inline bool operator==(const MultivariateMonomial & R) const
+    {
+        return coeff == R.coeff && monomial == R.monomial;
+    }
+
+    /**
+     * \brief Print a monomial
+     * \param vars a map containing var id -> string representation
+     * \return the printed monomial
+     */
+    inline const std::wstring print(const std::map<unsigned long long, std::wstring> & vars) const
+    {
+        std::wostringstream wos;
+        wos << coeff;
+        for (const auto & ve : monomial)
+        {
+            wos << L"*" << ve.print(vars);
+        }
+        return wos.str();
+    }
+
+    /**
+     * \brief Overload of the << operator
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const MultivariateMonomial & m)
+    {
+        out << m.coeff;
+        for (const auto & ve : m.monomial)
+        {
+            out << L"*" << ve;
+        }
+        return out;
+    }
+
+    /**
+     * \struct Hash
+     * \brief To be used in an unordered container
+     */
+    struct Hash
+    {
+        inline std::size_t operator()(const MultivariateMonomial & m) const
+        {
+            // We don't consider the coefficient of the monomial : take care it is not a bug !!
+            // when we add a monomial 1.23*a*b in a polynomial we search in the unordered_set ?*a*b and
+            // we add 1.23 to its coefficient
+            std::size_t h = 0;
+            for (const auto & ve : m.monomial)
+            {
+                h = tools::hash_combine(h, std::hash<unsigned long long>()(ve.var), std::hash<unsigned int>()(ve.exp));
+            }
+            return h;
+        }
+    };
+
+    /**
+     * \struct Eq
+     * \brief To be used in an unordered container
+     */
+    struct Eq
+    {
+        inline bool operator()(const MultivariateMonomial & L, const MultivariateMonomial & R) const
+        {
+            // See the comment above (to see why we ignore the coefficient)
+            return L.monomial == R.monomial;
+        }
+    };
+
+    /**
+     * \struct Compare
+     * \brief To be used in an ordered container
+     */
+    struct Compare
+    {
+        inline bool operator()(const MultivariateMonomial & L, const MultivariateMonomial & R) const
+        {
+            const unsigned int le = L.exponent();
+            const unsigned int re = R.exponent();
+            if (le < re)
+            {
+                return true;
+            }
+            else if (le == re)
+            {
+                const unsigned int ls = L.monomial.size();
+                const unsigned int rs = R.monomial.size();
+                if (ls > rs)
+                {
+                    return true;
+                }
+                else if (ls == rs)
+                {
+                    for (Monomial::const_iterator i = L.monomial.begin(), j = R.monomial.begin(), e = L.monomial.end(); i != e; ++i, ++j)
+                    {
+                        if (VarExp::Compare()(*i, *j))
+                        {
+                            return true;
+                        }
+                        else if (!VarExp::Eq()(*i, *j))
+                        {
+                            return false;
+                        }
+                    }
+
+                    for (Monomial::const_iterator i = L.monomial.begin(), j = R.monomial.begin(), e = L.monomial.end(); i != e; ++i, ++j)
+                    {
+                        if (i->exp < j->exp)
+                        {
+                            return true;
+                        }
+                        else if (i->exp > j->exp)
+                        {
+                            return false;
+                        }
+                    }
+
+                }
+            }
+            return false;
+        }
+    };
+};
+
+} // namespace analysis
+
+#endif // __MULTIVARIATE_MONOMIAL_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/MultivariatePolynomial.hxx b/scilab/modules/ast/includes/analysis/gvn/MultivariatePolynomial.hxx
new file mode 100644 (file)
index 0000000..c359fc0
--- /dev/null
@@ -0,0 +1,1158 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __MULTIVARIATE_POLYNOMIAL_HXX__
+#define __MULTIVARIATE_POLYNOMIAL_HXX__
+
+#include <cmath>
+#include <functional>
+#include <iostream>
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+#include <unordered_set>
+
+#include "core_math.h"
+#include "tools.hxx"
+#include "MultivariateMonomial.hxx"
+
+namespace analysis
+{
+/**
+ * \struct MultivariatePolynomial
+ * \brief Represents a multivariate polynomial
+ */
+struct MultivariatePolynomial
+{
+    typedef std::unordered_set<MultivariateMonomial, MultivariateMonomial::Hash, MultivariateMonomial::Eq> Polynomial;
+    double constant;
+    Polynomial polynomial;
+
+    /**
+     * \brief constructor
+     * \param var to init polynomial
+     */
+    MultivariatePolynomial(const unsigned long long var) : constant(0)
+    {
+        polynomial.emplace(var);
+    }
+
+    /**
+     * \brief constructor
+     * \param _constant to init polynomial
+     */
+    MultivariatePolynomial(const double _constant = 0) : constant(_constant) { }
+
+    /**
+     * \brief constructor
+     * \param _size the size of the polynomial (used to reserve the unordered_set)
+     * \param _constant to init polynomial
+     */
+    MultivariatePolynomial(const unsigned int _size, const double _constant) : constant(_constant), polynomial(_size) { }
+
+    /**
+     * \brief copy constructor
+     */
+    MultivariatePolynomial(const MultivariatePolynomial & mp) : constant(mp.constant), polynomial(mp.polynomial) { }
+
+    /**
+     * \brief Get an invalid polynomial (i.e. constant == NaN)
+     * \return invalid polynomial
+     */
+    inline static MultivariatePolynomial getInvalid()
+    {
+        return MultivariatePolynomial(tools::NaN());
+    }
+
+    /**
+     * \brief Check if it is valid
+     * \return true if it is valid
+     */
+    inline bool isValid() const
+    {
+        return !tools::isNaN(constant);
+    }
+
+    /**
+     * \brief Check if it is invalid
+     * \return true if it is invalid
+     */
+    inline bool isInvalid() const
+    {
+        return tools::isNaN(constant);
+    }
+
+    /**
+     * \brief Invalidate the polynomial
+     */
+    inline void invalid()
+    {
+        constant = tools::NaN();
+        polynomial.clear();
+    }
+
+    /**
+     * \brief Check if the variables of the polynomial have an id lower or equal to max
+     * \param max an id
+     * \return true if all the variables have an id leq to max
+     */
+    inline bool checkVariable(const unsigned long long max) const
+    {
+        for (const auto & m : polynomial)
+        {
+            if (!m.checkVariable(max))
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * \brief Add a monomial in the polynomial
+     * \param m the monomial to add
+     * \param coeff the multiplcative coefficient to applicate to the monomial
+     * \return *this
+     */
+    inline MultivariatePolynomial & add(const MultivariateMonomial & m, const double coeff = 1)
+    {
+        const double c = m.coeff * coeff;
+        if (c)
+        {
+            Polynomial::iterator i = polynomial.find(m);
+            if (i == polynomial.end())
+            {
+                Polynomial::iterator j = polynomial.insert(m).first;
+                j->coeff = c;
+            }
+            else
+            {
+                if (i->coeff == -c)
+                {
+                    polynomial.erase(i);
+                }
+                else
+                {
+                    i->coeff += c;
+                }
+            }
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Subtract a monomial in the polynomial
+     * \param m the monomial to add
+     */
+    inline void sub(const MultivariateMonomial & m)
+    {
+        Polynomial::iterator i = polynomial.find(m);
+        if (i == polynomial.end())
+        {
+            if (m.coeff)
+            {
+                polynomial.insert(m).first->coeff = -m.coeff;
+            }
+        }
+        else
+        {
+            if (i->coeff == m.coeff)
+            {
+                polynomial.erase(i);
+            }
+            else
+            {
+                i->coeff -= m.coeff;
+            }
+        }
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline MultivariatePolynomial operator+(const MultivariateMonomial & R) const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.add(R);
+            return res;
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the += operator
+     */
+    inline MultivariatePolynomial & operator+=(const MultivariateMonomial & R)
+    {
+        if (isValid())
+        {
+            add(R);
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline MultivariatePolynomial operator+(const double R) const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.constant += R;
+            return res;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the += operator
+     */
+    inline MultivariatePolynomial & operator+=(const double R)
+    {
+        if (isValid())
+        {
+            constant += R;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline MultivariatePolynomial operator-(const MultivariateMonomial & R) const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.sub(R);
+            return res;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the -= operator
+     */
+    inline MultivariatePolynomial & operator-=(const MultivariateMonomial & R)
+    {
+        if (isValid())
+        {
+            sub(R);
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline MultivariatePolynomial operator-(const double R) const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.constant -= R;
+            return res;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the - operator (unary)
+     */
+    inline MultivariatePolynomial operator-() const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.constant = -res.constant;
+            for (auto & m : res.polynomial)
+            {
+                m.coeff = -m.coeff;
+            }
+            return res;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the -= operator
+     */
+    inline MultivariatePolynomial & operator-=(const double R)
+    {
+        if (isValid())
+        {
+            constant -= R;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline MultivariatePolynomial operator+(const MultivariatePolynomial & R) const
+    {
+        if (isValid() && R.isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.constant += R.constant;
+            for (const auto & m : R.polynomial)
+            {
+                res.add(m);
+            }
+            return res;
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the += operator
+     */
+    inline MultivariatePolynomial & operator+=(const MultivariatePolynomial & R)
+    {
+        if (isValid() && R.isValid())
+        {
+            constant += R.constant;
+            for (const auto & m : R.polynomial)
+            {
+                add(m);
+            }
+        }
+        else
+        {
+            invalid();
+        }
+
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline MultivariatePolynomial operator-(const MultivariatePolynomial & R) const
+    {
+        if (isValid() && R.isValid())
+        {
+            MultivariatePolynomial res(*this);
+            res.constant -= R.constant;
+            for (const auto & m : R.polynomial)
+            {
+                res.sub(m);
+            }
+            return res;
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the -= operator
+     */
+    inline MultivariatePolynomial & operator-=(const MultivariatePolynomial & R)
+    {
+        if (isValid() && R.isValid())
+        {
+            constant -= R.constant;
+            for (const auto & m : R.polynomial)
+            {
+                sub(m);
+            }
+        }
+        else
+        {
+            invalid();
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline MultivariatePolynomial operator*(const MultivariatePolynomial & R) const
+    {
+        if (isValid() && R.isValid())
+        {
+            if (R.isConstant())
+            {
+                return *this * R.constant;
+            }
+            else if (isConstant())
+            {
+                return R * constant;
+            }
+            else
+            {
+                MultivariatePolynomial res((polynomial.size() + 1) * (R.polynomial.size() + 1) - 1, constant * R.constant);
+                for (const auto & mR : R.polynomial)
+                {
+                    res.add(mR, constant);
+                }
+                for (const auto & mL : polynomial)
+                {
+                    res.add(mL, R.constant);
+                    for (const auto & mR : R.polynomial)
+                    {
+                        res.add(mL * mR);
+                    }
+                }
+                return res;
+            }
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline MultivariatePolynomial operator/(const MultivariatePolynomial & R) const
+    {
+        if (isValid() && R.isValid())
+        {
+            if (R.isConstant())
+            {
+                if (R.constant != 1)
+                {
+                    return *this / R.constant;
+                }
+                else
+                {
+                    return *this;
+                }
+            }
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the /= operator
+     */
+    inline MultivariatePolynomial & operator/=(const MultivariatePolynomial & R)
+    {
+        if (isValid() && R.isValid())
+        {
+            if (R.polynomial.empty())
+            {
+                constant /= R.constant;
+                for (auto & m : polynomial)
+                {
+                    m.coeff /= R.constant;
+                }
+            }
+            else
+            {
+                MultivariatePolynomial res(*this / R);
+                polynomial = res.polynomial;
+                constant = res.constant;
+            }
+        }
+        else
+        {
+            invalid();
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the *= operator
+     */
+    inline MultivariatePolynomial & operator*=(const MultivariatePolynomial & R)
+    {
+        if (isValid() && R.isValid())
+        {
+            if (R.polynomial.empty())
+            {
+                constant *= R.constant;
+                for (auto & m : polynomial)
+                {
+                    m.coeff *= R.constant;
+                }
+            }
+            else
+            {
+                MultivariatePolynomial res(*this * R);
+                polynomial = res.polynomial;
+                constant = res.constant;
+            }
+        }
+        else
+        {
+            invalid();
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline MultivariatePolynomial operator*(const MultivariateMonomial & R) const
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res(polynomial.size() + 1, 0.);
+            res.add(constant * R);
+            for (const auto & mL : polynomial)
+            {
+                res.add(mL * R);
+            }
+            return res;
+        }
+        else
+        {
+            return getInvalid();
+        }
+    }
+
+    /**
+     * \brief Overload of the *= operator
+     */
+    inline MultivariatePolynomial & operator*=(const MultivariateMonomial & R)
+    {
+        if (isValid())
+        {
+            MultivariatePolynomial res = *this * R;
+            polynomial = res.polynomial;
+            constant = res.constant;
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline MultivariatePolynomial operator*(const double R) const
+    {
+        if (isValid())
+        {
+            if (R)
+            {
+                if (R == 1)
+                {
+                    return *this;
+                }
+                else
+                {
+                    MultivariatePolynomial res(*this);
+                    res.constant *= R;
+                    for (auto & m : res.polynomial)
+                    {
+                        m.coeff *= R;
+                    }
+                    return res;
+                }
+            }
+            else
+            {
+                return MultivariatePolynomial(0.);
+            }
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the *= operator
+     */
+    inline MultivariatePolynomial & operator*=(const double R)
+    {
+        if (isValid())
+        {
+            if (R == 0)
+            {
+                constant = 0.;
+                polynomial.clear();
+            }
+            else if (R != 1)
+            {
+                constant *= R;
+                for (auto & m : polynomial)
+                {
+                    m.coeff *= R;
+                }
+            }
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline MultivariatePolynomial operator/(const double R) const
+    {
+        if (isValid())
+        {
+            if (R != 1)
+            {
+                MultivariatePolynomial res(*this);
+                res.constant /= R;
+                for (auto & m : res.polynomial)
+                {
+                    m.coeff /= R;
+                }
+                return res;
+            }
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the /= operator
+     */
+    inline MultivariatePolynomial & operator/=(const double R)
+    {
+        if (isValid())
+        {
+            if (R != 1)
+            {
+                constant /= R;
+                for (auto & m : polynomial)
+                {
+                    m.coeff /= R;
+                }
+            }
+        }
+        return *this;
+    }
+
+    /**
+     * \brief Overload of the ^ operator (exponentiation)
+     */
+    inline MultivariatePolynomial operator^(unsigned int R) const
+    {
+        if (isValid())
+        {
+            if (R == 0)
+            {
+                return MultivariatePolynomial(1.);
+            }
+            else if (R == 1)
+            {
+                return *this;
+            }
+            else
+            {
+                if (constant == 0)
+                {
+                    if (polynomial.empty())
+                    {
+                        return MultivariatePolynomial(0.);
+                    }
+                    else if (polynomial.size() == 1)
+                    {
+                        const MultivariateMonomial & m = *polynomial.begin();
+                        MultivariatePolynomial res;
+                        res.polynomial.emplace(m ^ R);
+
+                        return res;
+                    }
+                }
+
+                if (polynomial.empty())
+                {
+                    return MultivariatePolynomial(std::pow(constant, R));
+                }
+
+                MultivariatePolynomial p = *this;
+                MultivariatePolynomial y = (R & 1) ? *this : MultivariatePolynomial(1.);
+
+                while (R >>= 1)
+                {
+                    p *= p;
+                    if (R & 1)
+                    {
+                        y *= p;
+                    }
+                }
+
+                return y;
+            }
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Overload of the ^ operator (exponentiation)
+     */
+    inline MultivariatePolynomial operator^(const MultivariatePolynomial & R) const
+    {
+        if (isValid() && R.isValid())
+        {
+            if (R.isConstant() && R.constant == (unsigned int)R.constant)
+            {
+                return (*this) ^ ((unsigned int)R.constant);
+            }
+        }
+        return getInvalid();
+    }
+
+    /**
+     * \brief Evaluate a polynomial
+     * \param values an unordered_map<ULL, const MultivariatePolynomial *> containing mapping between var number and polynomial
+     *        or a std::vector<const MultivariatePolynomial *> (0->vector[0], 1->vector[1], ...)
+     * \return the result of the evaluation
+     */
+    template<typename T>
+    inline MultivariatePolynomial eval(T && values) const
+    {
+        if (isInvalid())
+        {
+            return getInvalid();
+        }
+        if (!MultivariatePolynomial::__isValid(values))
+        {
+            return getInvalid();
+        }
+
+        std::unordered_map<unsigned long long, std::set<unsigned int>> expected_exps;
+        for (const auto & m : polynomial)
+        {
+            for (const auto & ve : m.monomial)
+            {
+                if (ve.exp >= 2 && MultivariatePolynomial::__contains(values, ve.var))
+                {
+                    expected_exps[ve.var].emplace(ve.exp);
+                }
+            }
+        }
+
+        std::unordered_map<unsigned long long, std::unordered_map<unsigned int, MultivariatePolynomial>> exps;
+        for (const auto & p : expected_exps)
+        {
+            if (p.second.size() == 1)
+            {
+                const unsigned int expo = *p.second.begin();
+                auto & map = exps.emplace(p.first, std::unordered_map<unsigned int, MultivariatePolynomial>()).first->second;
+                map.emplace(expo, (*values[p.first]) ^ expo);
+            }
+            else
+            {
+                unsigned int estim = 0;
+                for (const auto i : p.second)
+                {
+                    estim += tools::popcount(i) + tools::log2(i) - 1;
+                }
+                unsigned int max = *std::prev(p.second.end());
+                auto & map = exps.emplace(p.first, std::unordered_map<unsigned int, MultivariatePolynomial>()).first->second;
+
+                // if we have p^3, p^5, p^6 and p^9 to compute:
+                //   i) cost of p^3 is 2 mults
+                //   ii) cost of p^5 is 3 mults
+                //   iii) cost of p^6 is 3 mults
+                //   iv) cost of p^9 is 4 mults
+                //   v) total cost is 12
+                //   vi) 12 > 9 so we compute p^2, p^3, p^4, ..., p^9 and we retains only the exponents 3, 5, 6, 9
+                // if we just have p^3, p^9:
+                //   i) total cost is 6
+                //   ii) we compute p^3 and p^9 separatly in using fast exponentiation
+                if (estim > max)
+                {
+                    MultivariatePolynomial mp(*values[p.first]);
+                    auto it = p.second.begin();
+                    for (unsigned int i = 2; i <= max; ++i)
+                    {
+                        mp *= *values[p.first];
+                        if (i == *it)
+                        {
+                            map.emplace(i, mp);
+                            ++it;
+                        }
+                    }
+                }
+                else
+                {
+                    for (const auto expo : p.second)
+                    {
+                        map.emplace(expo, (*values[p.first]) ^ expo);
+                    }
+                }
+            }
+        }
+
+        MultivariatePolynomial res(constant);
+        for (const auto & m : polynomial)
+        {
+            MultivariatePolynomial r(m.coeff);
+            for (const auto & ve : m.monomial)
+            {
+                const MultivariatePolynomial * mp = MultivariatePolynomial::__get(values, ve.var);
+                if (mp)
+                {
+                    if (ve.exp == 1)
+                    {
+                        r *= *mp;
+                    }
+                    else if (ve.exp > 1)
+                    {
+                        r *= exps[ve.var][ve.exp];
+                    }
+                }
+                else
+                {
+                    MultivariateMonomial mm(1.);
+                    r *= mm.add(ve);
+                }
+            }
+            res += r;
+        }
+
+        return res;
+    }
+
+    /**
+     * \brief Check positivity
+     * \return true if all the coeffs are positive and the exponents are even
+     */
+    inline bool isPositive() const
+    {
+        if (constant >= 0)
+        {
+            for (const auto & m : polynomial)
+            {
+                if (m.coeff >= 0)
+                {
+                    for (const auto & ve : m.monomial)
+                    {
+                        if (ve.exp % 2) // exp is odd
+                        {
+                            return false;
+                        }
+                    }
+                }
+                else
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * \brief Check strict positivity
+     * \param checkConstant if true the constant is checked too
+     * \return true if all the coeffs are strict positive
+     */
+    inline bool isCoeffStrictPositive(const bool checkConstant = true) const
+    {
+        if (!checkConstant || (constant > 0))
+        {
+            for (const auto & m : polynomial)
+            {
+                if (m.coeff <= 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * \brief Check positivity
+     * \param checkConstant if true the constant is checked too
+     * \return true if all the coeffs are positive
+     */
+    inline bool isCoeffPositive(const bool checkConstant = true) const
+    {
+        if (!checkConstant || (constant >= 0))
+        {
+            for (const auto & m : polynomial)
+            {
+                if (m.coeff < 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * \brief Check strict negativity
+     * \param checkConstant if true the constant is checked too
+     * \return true if all the coeffs are strict negative
+     */
+    inline bool isCoeffStrictNegative(const bool checkConstant = true) const
+    {
+        if (!checkConstant || (constant < 0))
+        {
+            for (const auto & m : polynomial)
+            {
+                if (m.coeff >= 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * \brief Check negativity
+     * \param checkConstant if true the constant is checked too
+     * \return true if all the coeffs are negative
+     */
+    inline bool isCoeffNegative(const bool checkConstant = true) const
+    {
+        if (!checkConstant || (constant <= 0))
+        {
+            for (const auto & m : polynomial)
+            {
+                if (m.coeff > 0)
+                {
+                    return false;
+                }
+            }
+            return true;
+        }
+        return false;
+    }
+
+    /**
+     * \brief Helper function to print a polynomial
+     * \param vars a mapping between vars numbers and wstring representation
+     * \return a wstring representing this polynomial
+     */
+    inline const std::wstring print(const std::map<unsigned long long, std::wstring> & vars) const
+    {
+        std::wostringstream wos;
+        wos << constant;
+        std::set<MultivariateMonomial, MultivariateMonomial::Compare> s(polynomial.begin(), polynomial.end());
+        for (const auto & m : s)
+        {
+            wos << L" + " << m.print(vars);
+        }
+        return wos.str();
+    }
+
+    /**
+     * \brief Overload of << operator
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const MultivariatePolynomial & p)
+    {
+        const std::map<unsigned long long, std::wstring> vars;
+        out << p.constant;
+        std::set<MultivariateMonomial, MultivariateMonomial::Compare> s(p.polynomial.begin(), p.polynomial.end());
+        for (const auto & m : s)
+        {
+            out << L" + " << m.print(vars);
+        }
+        return out;
+    }
+
+    /**
+     * \return true if the two polynomials are differing only by a constant
+     */
+    inline bool isDiffConstant(const MultivariatePolynomial & R) const
+    {
+        return polynomial == R.polynomial;
+    }
+
+    /**
+     * \return true if the polynomial is constant
+     */
+    inline bool isConstant() const
+    {
+        return polynomial.empty();
+    }
+
+    /**
+     * \brief Check if a polynomial is constant and equal to a value
+     * \param val the constant value to check
+     * \return true if the polynomial is constant and equal to val
+     */
+    inline bool isConstant(const double val) const
+    {
+        return isConstant() && constant == val;
+    }
+
+    /**
+     * \brief Get the common coeff for all the monomials
+     * \param[out] common the common value
+     * \return true if there is a common coeff
+     */
+    inline bool getCommonCoeff(double & common) const
+    {
+        if (constant != 0)
+        {
+            return false;
+        }
+        if (polynomial.empty())
+        {
+            common = constant;
+            return true;
+        }
+
+        common = polynomial.begin()->coeff;
+        for (Polynomial::const_iterator i = std::next(polynomial.begin()), e = polynomial.end(); i != e; ++i)
+        {
+            if (i->coeff != common)
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    /**
+     * \brief Overload of == operator
+     */
+    inline bool operator==(const MultivariatePolynomial & R) const
+    {
+        return constant == R.constant && polynomial == R.polynomial;
+    }
+
+    /**
+     * \brief Overload of != operator
+     */
+    inline bool operator!=(const MultivariatePolynomial & R) const
+    {
+        return !(*this == R);
+    }
+
+    /**
+     * \brief Overload of == operator
+     */
+    inline bool operator==(const double R) const
+    {
+        return polynomial.empty() && constant == R;
+    }
+
+    /**
+     * \brief Overload of != operator
+     */
+    inline bool operator!=(const double R) const
+    {
+        return !(*this == R);
+    }
+
+    /**
+     * \brief Overload of == operator
+     */
+    friend inline bool operator==(const double L, const MultivariatePolynomial & R)
+    {
+        return R == L;
+    }
+
+    /**
+     * \brief Overload of != operator
+     */
+    friend inline bool operator!=(const double L, const MultivariatePolynomial & R)
+    {
+        return R != L;
+    }
+
+    /**
+     * \return a hash
+     */
+    inline std::size_t hash() const
+    {
+        std::size_t h = std::hash<double>()(constant);
+        for (const auto & m : polynomial)
+        {
+            // since the order of the monomials is not always the same
+            // we must use a commutative operation to combine the monomial's hashes
+            h += tools::hash_combine(std::hash<double>()(m.coeff), MultivariateMonomial::Hash()(m));
+        }
+
+        return h;
+    }
+
+    /**
+     * \struct Hash
+     * \brief To be used in an unordered container
+     */
+    struct Hash
+    {
+        inline std::size_t operator()(const MultivariatePolynomial & mp) const
+        {
+            return mp.hash();
+        }
+    };
+
+    /**
+     * \struct Eq
+     * \brief To be used in an unordered container
+     */
+    struct Eq
+    {
+        inline bool operator()(const MultivariatePolynomial & L, const MultivariatePolynomial & R) const
+        {
+            return L == R;
+        }
+    };
+
+private:
+
+    // Helper function to use with eval
+    inline static bool __isValid(const std::unordered_map<unsigned long long, const MultivariatePolynomial *> & values)
+    {
+        for (const auto & p : values)
+        {
+            if (p.second->isInvalid())
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    // Helper function to use with eval
+    inline static bool __isValid(const std::vector<const MultivariatePolynomial *> & values)
+    {
+        for (const auto & v : values)
+        {
+            if (v->isInvalid())
+            {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    // Helper function to use with eval
+    inline static bool __contains(const std::unordered_map<unsigned long long, const MultivariatePolynomial *> & values, const unsigned long long val)
+    {
+        return values.find(val) != values.end();
+    }
+
+    // Helper function to use with eval
+    inline static bool __contains(const std::vector<const MultivariatePolynomial *> & values, const unsigned long long val)
+    {
+        return val < values.size();
+    }
+
+    // Helper function to use with eval
+    inline static const MultivariatePolynomial * __get(const std::unordered_map<unsigned long long, const MultivariatePolynomial *> & values, const unsigned long long val)
+    {
+        const auto i = values.find(val);
+        if (i != values.end())
+        {
+            return i->second;
+        }
+        return nullptr;
+    }
+
+    // Helper function to use with eval
+    inline static const MultivariatePolynomial * __get(const std::vector<const MultivariatePolynomial *> & values, const unsigned long long val)
+    {
+        return values[val];
+    }
+};
+
+} // namespace analysis
+
+#endif // __MULTIVARIATE_POLYNOMIAL_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/OpValue.hxx b/scilab/modules/ast/includes/analysis/gvn/OpValue.hxx
new file mode 100644 (file)
index 0000000..47cc578
--- /dev/null
@@ -0,0 +1,169 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __OPVALUE_HXX__
+#define __OPVALUE_HXX__
+
+#include <iostream>
+
+namespace analysis
+{
+
+/**
+ * \struct OpValue
+ * \brief OpValue represents an operation between one or two operands
+ *
+ * This is struct is mainly used by the GVN.
+ */
+struct OpValue
+{
+    enum Kind : unsigned char { UNARYMINUS = 0, UNARYNEG, PLUS, MINUS, TIMES, DOTTIMES, RDIV, DOTRDIV, POWER, DOTPOWER };
+    const Kind kind;
+    unsigned long long lnum : 60;
+    unsigned long long rnum : 60;
+
+    /**
+     * \brief constructor for unary operation
+     * \param _kind the operation kind
+     * \param _lnum the value of the operand
+     */
+    OpValue(Kind _kind, unsigned long long _lnum) : kind(_kind), lnum(_lnum) { }
+
+    /**
+     * \brief constructor for binary operation
+     * \param _kind the operation kind
+     * \param _lnum the value of the left operand
+     * \param _rnum the value of the right operand
+     */
+    OpValue(Kind _kind, unsigned long long _lnum, unsigned long long _rnum) : kind(_kind), lnum(_lnum), rnum(_rnum)
+    {
+        if (isCommutative() && lnum > rnum)
+        {
+            const unsigned long long x = lnum;
+            lnum = rnum;
+            rnum = x;
+        }
+    }
+
+    /**
+     * \brief Check if the operation is commutative
+     * \return true if the operation is commutative
+     */
+    inline bool isCommutative() const
+    {
+        return kind == PLUS || kind == TIMES || kind == DOTTIMES;
+    }
+
+    /**
+     * \brief Check if the operation is unary
+     * \return true if the operation is unary
+     */
+    inline bool isUnary() const
+    {
+        return kind == UNARYMINUS || kind == UNARYNEG;
+    }
+
+    /**
+     * \brief Compute the hash
+     * \return the hash
+     */
+    inline std::size_t hash() const
+    {
+        return tools::hash_combine(kind, lnum, rnum);
+    }
+
+    /**
+     * \brief Overload of the operator ==
+     */
+    inline bool operator==(const OpValue & R) const
+    {
+        if (kind == R.kind)
+        {
+            if (isUnary())
+            {
+                return lnum == R.lnum;
+            }
+            else
+            {
+                return lnum == R.lnum && rnum == R.rnum;
+            }
+        }
+        return false;
+    }
+
+    /**
+     * \brief Overload of the operator <<
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const OpValue & ov)
+    {
+        switch (ov.kind)
+        {
+            case UNARYMINUS :
+                out << L"-" << ov.lnum;
+                break;
+            case UNARYNEG :
+                out << L"~" << ov.lnum;
+                break;
+            case PLUS :
+                out << ov.lnum << L"+" << ov.rnum;
+                break;
+            case MINUS :
+                out << ov.lnum << L"-" << ov.rnum;
+                break;
+            case TIMES :
+            case DOTTIMES :
+                out << ov.lnum << L"*" << ov.rnum;
+                break;
+            case RDIV :
+            case DOTRDIV :
+                out << ov.lnum << L"/" << ov.rnum;
+                break;
+            case POWER :
+            case DOTPOWER :
+                out << ov.lnum << L"^" << ov.rnum;
+                break;
+            default :
+                out << ov.lnum << L"??" << ov.rnum;
+                break;
+        }
+
+        return out;
+    }
+
+    /**
+     * \struct Hash
+     * \brief Helper struct to be used in unordered_map
+     */
+    struct Hash
+    {
+        inline std::size_t operator()(const OpValue & ov) const
+        {
+            return ov.hash();
+        }
+    };
+
+    /**
+     * \struct Eq
+     * \brief Helper struct to be used in unordered_map
+     */
+    struct Eq
+    {
+        inline bool operator()(const OpValue & L, const OpValue & R) const
+        {
+            return L == R;
+        }
+    };
+};
+
+} // namespace analysis
+
+#endif // __OPVALUE_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/SymbolicDimension.hxx b/scilab/modules/ast/includes/analysis/gvn/SymbolicDimension.hxx
new file mode 100644 (file)
index 0000000..a2415cd
--- /dev/null
@@ -0,0 +1,337 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __SYMBOLIC_DIMENSION_HXX__
+#define __SYMBOLIC_DIMENSION_HXX__
+
+#include <iostream>
+
+#include "GVN.hxx"
+#include "tools.hxx"
+
+namespace analysis
+{
+
+/**
+ * \class SymbolicDimension
+ * \brief Manage a symbolic dimension
+ */
+class SymbolicDimension
+{
+    GVN * gvn;
+    GVN::Value * value;
+
+public :
+
+    /**
+     * \brief default constructor
+     */
+    SymbolicDimension() : gvn(nullptr), value(nullptr) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN associated with this dimension
+     */
+    SymbolicDimension(GVN & _gvn) : gvn(&_gvn), value(_gvn.getValue()) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN associated with this dimension
+     * \param _value the value of this dimension
+     */
+    SymbolicDimension(GVN * _gvn, GVN::Value * _value) : gvn(_gvn), value(_value) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN associated with this dimension
+     * \param _value the value of this dimension
+     */
+    SymbolicDimension(GVN & _gvn, GVN::Value * _value) : gvn(&_gvn), value(_value) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN associated with this dimension
+     * \param dim the value of this dimension
+     */
+    SymbolicDimension(GVN & _gvn, double dim) : gvn(&_gvn), value(dim == -1 ? _gvn.getValue() : _gvn.getValue(dim)) { }
+
+    /**
+     * \brief Get the associated GVN
+     * \return the GVN
+     */
+    inline GVN * getGVN()
+    {
+        return gvn;
+    }
+
+    /**
+     * \brief Invalidate this dimension
+     */
+    inline void invalid()
+    {
+        value = gvn->getInvalid();
+    }
+
+    /**
+     * \brief Check if this dimension is valid
+     * \return true if valid
+     */
+    inline bool isValid() const
+    {
+        return value->poly->isValid();
+    }
+
+    /**
+     * \brief Check if this dimension is constant (i.e. the associated polynomial is constant)
+     * \return true if constant
+     */
+    inline bool isConstant() const
+    {
+        return value->poly->isConstant();
+    }
+
+    /**
+     * \brief Get the constant part of the associated polynomial
+     * \return the constant
+     */
+    inline double getConstant() const
+    {
+        return value->poly->constant;
+    }
+
+    /**
+     * \brief Get the associated polynomial
+     * \return a polynomial
+     */
+    inline const MultivariatePolynomial * getPoly() const
+    {
+        return value->poly;
+    }
+
+    /**
+     * \brief Get the associated Value
+     * \return a Value
+     */
+    inline const GVN::Value * getValue() const
+    {
+        return value;
+    }
+
+    /**
+     * \brief Get the associated Value
+     * \return a Value
+     */
+    inline GVN::Value * getValue()
+    {
+        return value;
+    }
+
+    /**
+     * \brief Set the associated Value
+     * \param _value a Value
+     */
+    inline void setValue(GVN::Value * _value)
+    {
+        value = _value;
+    }
+
+    /**
+     * \brief Set the associated GVN
+     * \param _gvn a GVN
+     */
+    inline void setGVN(GVN * _gvn)
+    {
+        gvn = _gvn;
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline SymbolicDimension operator+(const SymbolicDimension & R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::PLUS, *value, *R.value));
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline SymbolicDimension operator+(const double R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::PLUS, *value, *gvn->getValue(R)));
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline SymbolicDimension operator-(const SymbolicDimension & R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::MINUS, *value, *R.value));
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline SymbolicDimension operator-(const double R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::MINUS, *value, *gvn->getValue(R)));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline SymbolicDimension operator*(const SymbolicDimension & R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::TIMES, *value, *R.value));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline SymbolicDimension operator*(const double R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::TIMES, *value, *gvn->getValue(R)));
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline SymbolicDimension operator/(const SymbolicDimension & R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::RDIV, *value, *R.value));
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline SymbolicDimension operator/(const double R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::RDIV, *value, *gvn->getValue(R)));
+    }
+
+    /**
+     * \brief Overload of the ^ operator
+     */
+    inline SymbolicDimension operator^(const SymbolicDimension & R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::POWER, *value, *R.value));
+    }
+
+    /**
+     * \brief Overload of the ^ operator
+     */
+    inline SymbolicDimension operator^(const double R) const
+    {
+        return SymbolicDimension(gvn, gvn->getValue(OpValue::Kind::POWER, *value, *gvn->getValue(R)));
+    }
+
+    /**
+     * \brief Overload of the == operator
+     */
+    inline bool operator==(const SymbolicDimension & R) const
+    {
+        return value->value == R.value->value;
+    }
+
+    /**
+     * \brief Overload of the == operator
+     */
+    inline bool operator==(const double R) const
+    {
+        return value->value == gvn->getValue(R)->value;
+    }
+
+    /**
+     * \brief Overload of the != operator
+     */
+    inline bool operator!=(const SymbolicDimension & R) const
+    {
+        return value->value != R.value->value;
+    }
+
+    /**
+     * \brief Overload of the != operator
+     */
+    inline bool operator!=(const double R) const
+    {
+        return value->value != gvn->getValue(R)->value;
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline friend SymbolicDimension operator+(const double L, const SymbolicDimension & R)
+    {
+        return R + L;
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline friend SymbolicDimension operator-(const double L, const SymbolicDimension & R)
+    {
+        return SymbolicDimension(R.gvn, R.gvn->getValue(OpValue::Kind::MINUS, *R.gvn->getValue(L), *R.value));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline friend SymbolicDimension operator*(const double L, const SymbolicDimension & R)
+    {
+        return R * L;
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline friend SymbolicDimension operator/(const double L, const SymbolicDimension & R)
+    {
+        return SymbolicDimension(R.gvn, R.gvn->getValue(OpValue::Kind::RDIV, *R.gvn->getValue(L), *R.value));
+    }
+
+    /**
+     * \brief Overload of the ^ operator
+     */
+    inline friend SymbolicDimension operator^(const double L, const SymbolicDimension & R)
+    {
+        return SymbolicDimension(R.gvn, R.gvn->getValue(OpValue::Kind::POWER, *R.gvn->getValue(L), *R.value));
+    }
+
+    /**
+     * \brief Overload of the == operator
+     */
+    inline friend bool operator==(const double L, const SymbolicDimension & R)
+    {
+        return R == L;
+    }
+
+    /**
+     * \brief Overload of the != operator
+     */
+    inline friend bool operator!=(const double L, const SymbolicDimension & R)
+    {
+        return R != L;
+    }
+
+    /**
+     * \brief Overload of the << operator
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const SymbolicDimension & d)
+    {
+        out << *d.value->poly;
+
+        return out;
+    }
+};
+
+} // namespace analysis
+
+#endif // __SYMBOLIC_DIMENSION_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/SymbolicRange.hxx b/scilab/modules/ast/includes/analysis/gvn/SymbolicRange.hxx
new file mode 100644 (file)
index 0000000..e15dc1f
--- /dev/null
@@ -0,0 +1,243 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2014 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __SYMBOLIC_RANGE_HXX__
+#define __SYMBOLIC_RANGE_HXX__
+
+#include <iostream>
+
+#include "GVN.hxx"
+#include "tools.hxx"
+
+namespace analysis
+{
+
+/**
+ * \class SymbolicRange
+ * \brief Manage a symbolic range
+ */
+class SymbolicRange
+{
+    GVN * gvn;
+    GVN::Value * start;
+    GVN::Value * end;
+
+public :
+
+    /**
+     * \brief default constructor
+     */
+    SymbolicRange() : gvn(nullptr), start(nullptr), end(nullptr) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN to use
+     * \param _start the starting value
+     * \param _end the ending value
+     */
+    SymbolicRange(GVN & _gvn, GVN::Value * _start, GVN::Value * _end) : gvn(&_gvn), start(_start), end(_end) { }
+
+    /**
+     * \brief constructor
+     * \param _gvn the GVN to use
+     * \param _start the starting value
+     * \param _end the ending value
+     */
+    SymbolicRange(GVN & _gvn, double _start, double _end) : gvn(&_gvn), start(_gvn.getValue(_start)), end(_gvn.getValue(_end)) { }
+
+    /**
+     * \brief Get the associated GVN
+     * \return the GVN
+     */
+    inline GVN * getGVN()
+    {
+        return gvn;
+    }
+
+    /**
+     * \brief Invalidate this range
+     */
+    inline void invalid()
+    {
+        start = end = gvn->getInvalid();
+    }
+
+    /**
+     * \brief Check if this range is valid
+     * \return true if valid
+     */
+    inline bool isValid() const
+    {
+        return start->poly->isValid() && end->poly->isValid();
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline SymbolicRange operator+(const SymbolicRange & R) const
+    {
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::PLUS, *start, *R.start),
+                             gvn->getValue(OpValue::Kind::PLUS, *end, *R.end));
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline SymbolicRange operator+(const double R) const
+    {
+        GVN::Value * const val = gvn->getValue(R);
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::PLUS, *start, *val),
+                             gvn->getValue(OpValue::Kind::PLUS, *end, *val));
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline SymbolicRange operator-(const SymbolicRange & R) const
+    {
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::MINUS, *start, *R.end),
+                             gvn->getValue(OpValue::Kind::MINUS, *end, *R.start));
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline SymbolicRange operator-(const double R) const
+    {
+        GVN::Value * const val = gvn->getValue(R);
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::MINUS, *start, *val),
+                             gvn->getValue(OpValue::Kind::MINUS, *end, *val));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline SymbolicRange operator*(const SymbolicRange & R) const
+    {
+        // We suppose that all the values are positive or null
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::TIMES, *start, *R.start),
+                             gvn->getValue(OpValue::Kind::TIMES, *end, *R.end));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline SymbolicRange operator*(const double R) const
+    {
+        GVN::Value * const val = gvn->getValue(R);
+        if (R >= 0)
+        {
+            return SymbolicRange(gvn,
+                                 gvn->getValue(OpValue::Kind::TIMES, *start, *val),
+                                 gvn->getValue(OpValue::Kind::TIMES, *end, *val));
+        }
+        else
+        {
+            return SymbolicRange(gvn,
+                                 gvn->getValue(OpValue::Kind::TIMES, *end, *val),
+                                 gvn->getValue(OpValue::Kind::TIMES, *start, *val));
+        }
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline SymbolicRange operator/(const SymbolicRange & R) const
+    {
+        // We suppose that all the values are positive or null
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::RDIV, *start, *R.start),
+                             gvn->getValue(OpValue::Kind::RDIV, *end, *R.end));
+    }
+
+    /**
+     * \brief Overload of the / operator
+     */
+    inline SymbolicRange operator/(const double R) const
+    {
+        GVN::Value * const val = gvn->getValue(R);
+        if (R >= 0)
+        {
+            return SymbolicRange(gvn,
+                                 gvn->getValue(OpValue::Kind::RDIV, *start, *val),
+                                 gvn->getValue(OpValue::Kind::RDIV, *end, *val));
+        }
+        else
+        {
+            return SymbolicRange(gvn,
+                                 gvn->getValue(OpValue::Kind::RDIV, *end, *val),
+                                 gvn->getValue(OpValue::Kind::RDIV, *start, *val));
+        }
+    }
+
+    /**
+     * \brief Overload of the == operator
+     */
+    inline bool operator==(const SymbolicRange & R) const
+    {
+        return start->value == R.start->value && end->value == R.end->value;
+    }
+
+    /**
+     * \brief Overload of the != operator
+     */
+    inline bool operator!=(const SymbolicRange & R) const
+    {
+        return start->value != R.start->value || end->value != R.end->value;
+    }
+
+    /**
+     * \brief Overload of the + operator
+     */
+    inline friend SymbolicRange operator+(const double L, const SymbolicRange & R)
+    {
+        return R + L;
+    }
+
+    /**
+     * \brief Overload of the - operator
+     */
+    inline friend SymbolicRange operator-(const double L, const SymbolicRange & R)
+    {
+        GVN::Value * const val = gvn->getValue(R);
+        return SymbolicRange(gvn,
+                             gvn->getValue(OpValue::Kind::MINUS, *val, *end),
+                             gvn->getValue(OpValue::Kind::MINUS, *val, *start));
+    }
+
+    /**
+     * \brief Overload of the * operator
+     */
+    inline friend SymbolicRange operator*(const double L, const SymbolicRange & R)
+    {
+        return R * L;
+    }
+
+    /**
+     * \brief Overload of the << operator
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const SymbolicRange & r)
+    {
+        out << L"[" << *r.start->poly << L" ; " << *r.end->poly << L"]";
+
+        return out;
+    }
+};
+
+} // namespace analysis
+
+#endif // __SYMBOLIC_RANGE_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/TestGVNVisitor.hxx b/scilab/modules/ast/includes/analysis/gvn/TestGVNVisitor.hxx
new file mode 100644 (file)
index 0000000..cc96788
--- /dev/null
@@ -0,0 +1,318 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2014 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __TEST_GVN_VISITOR_HXX__
+#define __TEST_GVN_VISITOR_HXX__
+
+#include <iostream>
+#include <string>
+#include <map>
+
+#include "visitor.hxx"
+#include "execvisitor.hxx"
+#include "allexp.hxx"
+#include "allvar.hxx"
+//#include "Chrono.hxx"
+#include "GVN.hxx"
+
+namespace analysis
+{
+
+class TestGVNVisitor : public ast::Visitor /*, public Chrono */
+{
+
+    GVN gvn;
+    const GVN::Value * _result;
+
+public:
+
+    TestGVNVisitor()
+    {
+        //start_chrono();
+    }
+
+    virtual ~TestGVNVisitor()
+    {
+    }
+
+    inline void print_info()
+    {
+        //stop_chrono();
+        std::wcout << L"GVN: " << /* *static_cast<Chrono *>(this) << */ std::endl;
+        std::wcout << gvn << std::endl;
+    }
+
+    inline void result_set(const GVN::Value * val)
+    {
+        _result = val;
+    }
+
+    inline const GVN::Value & result_get()
+    {
+        return *_result;
+    }
+
+    inline std::map<std::wstring, unsigned long long> getSymMap() const
+    {
+        return gvn.getSymMap();
+    }
+
+private:
+
+    void visit(ast::SimpleVar & e)
+    {
+        result_set(gvn.getValue(e.getSymbol()));
+    }
+
+    void visit(ast::DollarVar & e)
+    {
+        // nothing to do
+    }
+
+    void visit(ast::ColonVar & e)
+    {
+        // nothing to do
+    }
+
+    void visit(ast::ArrayListVar & e)
+    {
+    }
+
+    void visit(ast::DoubleExp & e)
+    {
+        result_set(gvn.getValue(e.getValue()));
+    }
+
+    void visit(ast::BoolExp & e)
+    {
+    }
+
+    void visit(ast::StringExp & e)
+    {
+    }
+
+    void visit(ast::CommentExp & e)
+    {
+        // ignored
+    }
+
+    void visit(ast::NilExp & e)
+    {
+        // nothing to do
+    }
+
+    void visit(ast::CallExp & e)
+    {
+    }
+
+    void visit(ast::CellCallExp & e)
+    {
+    }
+
+    void visit(ast::OpExp & e)
+    {
+        e.getLeft().accept(*this);
+        const GVN::Value & LV = result_get();
+        e.getRight().accept(*this);
+        const GVN::Value & RV = result_get();
+
+        switch (e.getOper())
+        {
+            case ast::OpExp::plus :
+                result_set(gvn.getValue(OpValue::PLUS, LV, RV));
+                break;
+            case ast::OpExp::minus :
+                result_set(gvn.getValue(OpValue::MINUS, LV, RV));
+                break;
+            case ast::OpExp::unaryMinus :
+                result_set(gvn.getValue(OpValue::UNARYMINUS, RV));
+                break;
+            case ast::OpExp::rdivide :
+                result_set(gvn.getValue(OpValue::RDIV, LV, RV));
+                break;
+            case ast::OpExp::dotrdivide :
+                result_set(gvn.getValue(OpValue::DOTRDIV, LV, RV));
+                break;
+            case ast::OpExp::times :
+                result_set(gvn.getValue(OpValue::TIMES, LV, RV));
+                break;
+            case ast::OpExp::dottimes :
+                result_set(gvn.getValue(OpValue::DOTTIMES, LV, RV));
+                break;
+            case ast::OpExp::power :
+                result_set(gvn.getValue(OpValue::POWER, LV, RV));
+                break;
+            case ast::OpExp::dotpower :
+                result_set(gvn.getValue(OpValue::DOTPOWER, LV, RV));
+                break;
+            case ast::OpExp::eq :
+                if (LV.value == RV.value)
+                {
+                    result_set(gvn.getValue(1));
+                }
+                else
+                {
+                    result_set(gvn.getValue(0));
+                }
+                break;
+            case ast::OpExp::ne :
+                if (LV.value != RV.value)
+                {
+                    result_set(gvn.getValue(1));
+                }
+                else
+                {
+                    result_set(gvn.getValue(0));
+                }
+                break;
+        }
+    }
+
+    void visit(ast::LogicalOpExp & e)
+    {
+    }
+
+    void visit(ast::AssignExp & e)
+    {
+        if (e.getLeftExp().isSimpleVar())
+        {
+            ast::SimpleVar & Lvar = static_cast<ast::SimpleVar &>(e.getLeftExp());
+            symbol::Symbol & Lsym = Lvar.getSymbol();
+
+            if (e.getRightExp().isCallExp())
+            {
+                ast::CallExp & ce = static_cast<ast::CallExp &>(e.getRightExp());
+                std::unordered_map<unsigned long long, const MultivariatePolynomial *> args;
+                const symbol::Symbol & sym = static_cast<ast::SimpleVar &>(ce.getName()).getSymbol();
+                for (auto & arg : ce.getExps())
+                {
+                    if (arg->isAssignExp())
+                    {
+                        ast::AssignExp & ae = static_cast<ast::AssignExp &>(*arg);
+                        const symbol::Symbol & _Lsym = static_cast<ast::SimpleVar &>(ae.getLeftExp()).getSymbol();
+                        ae.getRightExp().accept(*this);
+                        args[gvn.getValue(_Lsym)->value] = result_get().poly;
+                    }
+                }
+                const GVN::Value * callee = gvn.getValue(sym);
+                gvn.setValue(Lsym, callee->poly->eval(args));
+            }
+            else
+            {
+                e.getRightExp().accept(*this);
+                gvn.setValue(Lsym, result_get());
+            }
+        }
+    }
+
+    void visit(ast::IfExp & e)
+    {
+    }
+
+    void visit(ast::WhileExp & e)
+    {
+    }
+
+    void visit(ast::ForExp & e)
+    {
+    }
+
+    void visit(ast::BreakExp & e)
+    {
+        // nothing to do
+    }
+
+    void visit(ast::ContinueExp & e)
+    {
+        // nothing to do
+    }
+
+    void visit(ast::TryCatchExp & e)
+    {
+    }
+
+    void visit(ast::SelectExp & e)
+    {
+    }
+
+    void visit(ast::CaseExp & e)
+    {
+    }
+
+    void visit(ast::ReturnExp & e)
+    {
+    }
+
+    void visit(ast::FieldExp & e)
+    {
+    }
+
+    void visit(ast::NotExp & e)
+    {
+    }
+
+    void visit(ast::TransposeExp & e)
+    {
+    }
+
+    void visit(ast::MatrixExp & e)
+    {
+    }
+
+    void visit(ast::MatrixLineExp & e)
+    {
+    }
+
+    void visit(ast::CellExp & e)
+    {
+    }
+
+    void visit(ast::SeqExp & e)
+    {
+        for (auto exp : e.getExps())
+        {
+            exp->accept(*this);
+        }
+    }
+
+    void visit(ast::ArrayListExp & e)
+    {
+    }
+
+    void visit(ast::AssignListExp & e)
+    {
+    }
+
+    void visit(ast::VarDec & e)
+    {
+    }
+
+    void visit(ast::FunctionDec & e)
+    {
+    }
+
+    void visit(ast::ListExp & e)
+    {
+    }
+
+    void visit(ast::OptimizedExp & e)
+    {
+    }
+
+    void visit(ast::DAXPYExp & e)
+    {
+    }
+};
+
+} // namespace analysis
+
+#endif // __TEST_GVN_VISITOR_HXX__
diff --git a/scilab/modules/ast/includes/analysis/gvn/VarExp.hxx b/scilab/modules/ast/includes/analysis/gvn/VarExp.hxx
new file mode 100644 (file)
index 0000000..8b3068a
--- /dev/null
@@ -0,0 +1,130 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __VAR_DEF_HXX__
+#define __VAR_DEF_HXX__
+
+#include <iostream>
+#include <map>
+#include <sstream>
+#include <string>
+
+namespace analysis
+{
+
+/**
+ * \struct VarExp
+ * \brief Represents a variable with an exponent
+ *
+ * This struct is mainly used in MultivariateMonomial.
+ */
+struct VarExp
+{
+    unsigned long long var;
+
+    // this field is mutable since it is not used in the hash computation
+    // and could me modified.
+    mutable unsigned int exp;
+
+    /**
+     * \brief constructor
+     * \param _var the var number
+     * \param _exp the exponent
+     */
+    VarExp(unsigned long long _var, unsigned int _exp = 1) : var(_var), exp(_exp) { }
+
+    /**
+     * \brief Print this VarExp
+     * \param vars a map containing association between var number and wstring
+     * \return a wstring containing the representation of this VarExp
+     */
+    inline const std::wstring print(const std::map<unsigned long long, std::wstring> & vars) const
+    {
+        std::wostringstream wos;
+        const auto i = vars.find(var);
+        if (i != vars.end())
+        {
+            wos << i->second;
+        }
+        else
+        {
+            wos << L"$" << var;
+        }
+
+        if (exp > 1)
+        {
+            wos << L"^" << exp;
+        }
+        return wos.str();
+    }
+
+    /**
+     * \brief Overload of the operator <<
+     */
+    friend inline std::wostream & operator<<(std::wostream & out, const VarExp & ve)
+    {
+        out << (char)('a' + ve.var);
+        if (ve.exp > 1)
+        {
+            out << L"^" << ve.exp;
+        }
+        return out;
+    }
+
+    /**
+     * \brief Overload of the operator <<
+     */
+    inline bool operator==(const VarExp & R) const
+    {
+        return var == R.var && exp == R.exp;
+    }
+
+    /**
+     * \struct Hash
+     * \brief Helper struct to be used in unordered container
+     */
+    struct Hash
+    {
+        inline std::size_t operator()(const VarExp & ve) const
+        {
+            return ve.var;
+        }
+    };
+
+    /**
+     * \struct Eq
+     * \brief Helper struct to be used in unordered container
+     */
+    struct Eq
+    {
+        inline bool operator()(const VarExp & L, const VarExp & R) const
+        {
+            return L.var == R.var;
+        }
+    };
+
+    /**
+     * \struct Compare
+     * \brief Helper struct to be used in map or set
+     */
+    struct Compare
+    {
+        inline bool operator()(const VarExp & L, const VarExp & R) const
+        {
+            return L.var < R.var;
+        }
+    };
+};
+
+} // namespace analysis
+
+#endif // __VAR_DEF_HXX__
diff --git a/scilab/modules/ast/includes/analysis/tools.hxx b/scilab/modules/ast/includes/analysis/tools.hxx
new file mode 100644 (file)
index 0000000..10c619c
--- /dev/null
@@ -0,0 +1,264 @@
+/*
+ *  Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+ *  Copyright (C) 2014 - Scilab Enterprises - Calixte DENIZET
+ *
+ *  This file must be used under the terms of the CeCILL.
+ *  This source file is licensed as described in the file COPYING, which
+ *  you should have received as part of this distribution.  The terms
+ *  are also available at
+ *  http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+ *
+ */
+
+#ifndef __TOOLS_HXX__
+#define __TOOLS_HXX__
+
+#include <bitset>
+#include <cmath>
+#include <cstdint>
+#include <iostream>
+#include <limits>
+#include <map>
+#include <set>
+
+#ifdef _MSC_VER
+#include "stdint.h"
+#include <intrin.h>
+#endif
+
+#include "core_math.h"
+
+namespace analysis
+{
+
+namespace tools
+{
+
+#ifdef _MSC_VER
+inline static double trunc(const double x)
+{
+    return x > 0 ? floor(x) : ceil(x);
+}
+
+inline static uint32_t clz(const uint32_t x)
+{
+    unsigned long r = 0;
+    _BitScanForward(&r, x);
+    return r;
+}
+
+inline static uint64_t clzll(const uint64_t x)
+{
+    unsigned long r = 0;
+    _BitScanForward64(&r, x);
+    return r;
+}
+#else
+inline static double trunc(const double x)
+{
+    return std::trunc(x);
+}
+
+inline static uint32_t clz(const uint32_t x)
+{
+    return __builtin_clz(x);
+}
+
+inline static uint32_t clzll(const uint64_t x)
+{
+    return __builtin_clzll(x);
+}
+#endif
+
+inline static double NaN()
+{
+    return std::numeric_limits<double>::quiet_NaN();
+}
+
+inline static bool isNaN(const double x)
+{
+    return ISNAN(x);
+}
+
+inline static bool isFinite(const double x)
+{
+    return finite(x);
+}
+
+inline static bool isInfinite(const double x)
+{
+    return !isFinite(x);
+}
+
+enum IntType { NOTANINT, SIGNED, UNSIGNED };
+
+inline static IntType getIntType(const double x)
+{
+    if (x == trunc(x))
+    {
+        if (x >= 0)
+        {
+            if (x <= (double)std::numeric_limits<uint64_t>::max())
+            {
+                return UNSIGNED;
+            }
+        }
+        else if (x >= (double)std::numeric_limits<int64_t>::min())
+        {
+            return SIGNED;
+        }
+    }
+
+    return NOTANINT;
+}
+
+inline static bool isAnInt(const double x)
+{
+    return getIntType(x) != NOTANINT;
+}
+
+template<typename T>
+inline static T cast(const double x)
+{
+    if (x < static_cast<double>(std::numeric_limits<T>::max()))
+    {
+        if (x > static_cast<double>(std::numeric_limits<T>::min()))
+        {
+            return static_cast<T>(x);
+        }
+        else
+        {
+            return std::numeric_limits<T>::min();
+        }
+    }
+    else
+    {
+        return std::numeric_limits<T>::max();
+    }
+}
+
+inline std::wostream & operator<<(std::wostream & out, const IntType & it)
+{
+    switch (it)
+    {
+        case IntType::NOTANINT :
+            out << L"NAI";
+            break;
+        case IntType::SIGNED :
+            out << L"S";
+            break;
+        case IntType::UNSIGNED :
+            out << L"U";
+            break;
+    }
+    return out;
+}
+
+template<typename T>
+inline static unsigned char popcount(const T x)
+{
+    return std::bitset<sizeof(T)>(x).count();
+}
+
+inline static unsigned char log2(const unsigned int x)
+{
+    return (sizeof(unsigned int) << 3) - clz(x) - 1;
+}
+
+inline static unsigned char log2(const unsigned long long x)
+{
+    return (sizeof(unsigned long long) << 3) - clzll(x) - 1;
+}
+
+template<typename T>
+static void printSet(const T & set, std::wostream & out)
+{
+    if (set.empty())
+    {
+        out << L"{}";
+    }
+    else
+    {
+        out << L"{";
+        typename T::const_iterator e = --set.end();
+        for (typename T::const_iterator i = set.begin(); i != e; ++i)
+        {
+            out << *i << L",";
+        }
+        out << *e << L"}";
+    }
+}
+
+template<typename T>
+static void printMapInfo(std::wostream & out, const T & map, const bool show_collisions = false)
+{
+    double mean = 0;
+    double variance = 0;
+    double count = map.bucket_count();
+    unsigned int empty_bucket_count = 0;
+    unsigned int collision_count = 0;
+
+    out << L"Map size: " << map.size() << std::endl;
+    out << L"Number of buckets: " << count << std::endl;
+
+    for (unsigned int i = 0; i < map.bucket_count(); ++i)
+    {
+        if (unsigned int s = map.bucket_size(i))
+        {
+            mean += s;
+            if (s > 1)
+            {
+                ++collision_count;
+            }
+        }
+        else
+        {
+            ++empty_bucket_count;
+        }
+    }
+    mean /= count;
+
+    for (unsigned int i = 0; i < map.bucket_count(); ++i)
+    {
+        const unsigned int s = map.bucket_size(i);
+        variance += (mean - s) * (mean - s);
+    }
+    variance /= count;
+
+    out << L"Number of elements by buckets: mean=" << mean << L", sigma=" << std::sqrt(variance) << std::endl;
+    out << L"Number of empty buckets: " << empty_bucket_count << std::endl;
+    out << L"Number of collisions: " << collision_count << std::endl;
+
+    if (show_collisions)
+    {
+        std::multimap<unsigned int, typename T::key_type> collisions;
+        for (const auto & p : map)
+        {
+            collisions.emplace(map.bucket(p.first), p.first);
+        }
+
+        for (const auto & p : collisions)
+        {
+            out << L"Bucket " << p.first << L": " << p.second << L", hash=" << (typename T::hasher()(p.second)) << std::endl;
+        }
+    }
+}
+
+inline static std::size_t hash_combine(const std::size_t seed)
+{
+    return seed;
+}
+
+template<typename... Args>
+inline static std::size_t hash_combine(const std::size_t seed, Args... args)
+{
+    // it is the way Boost has implemented hash_combine:
+    // http://www.boost.org/doc/libs/1_35_0/doc/html/boost/hash_combine_id241013.html
+    return seed ^ (hash_combine(args...) + 0x9e3779b9 + (seed << 6) + (seed >> 2));
+}
+
+} // namespace tools
+
+} // namespace analysis
+
+#endif // __TOOLS_HXX__
index a7ec6d8..62df94f 100644 (file)
@@ -505,6 +505,16 @@ public:
         }
     }
 
+    inline const exps_t & getExps() const
+    {
+        return _exps;
+    }
+
+    inline exps_t & getExps()
+    {
+        return _exps;
+    }
+
 private:
     bool _verbose;
     bool _bBreak;
index f086c69..2cc0d69 100644 (file)
@@ -84,15 +84,6 @@ public:
     /** \name Accessors.
     ** \{ */
 public:
-    const exps_t& getExps() const
-    {
-        return _exps;
-    }
-
-    exps_t& getExps()
-    {
-        return _exps;
-    }
 
     void clearExps()
     {
index e04440a..40e217c 100644 (file)
@@ -77,7 +77,12 @@ public:
     ** \{ */
 public:
     /** \brief Return the Variable's name. */
-    symbol::Symbol getSymbol () const
+    const symbol::Symbol & getSymbol() const
+    {
+        return _name;
+    }
+
+    symbol::Symbol & getSymbol()
     {
         return _name;
     }
diff --git a/scilab/modules/ast/tests/unit_tests/gvn.dia.ref b/scilab/modules/ast/tests/unit_tests/gvn.dia.ref
new file mode 100644 (file)
index 0000000..d6c9e6f
--- /dev/null
@@ -0,0 +1,52 @@
+// ============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+//
+//  This file is distributed under the same license as the Scilab package.
+// ============================================================================
+// <-- JVM NOT MANDATORY -->
+out = testGVN("a=1;b=1");
+assert_checkequal(out.a, out.b);
+out = testGVN("a=-1-5+4-3;b=7-12");
+assert_checkequal(out.a, out.b);
+out = testGVN("a=n+1;b=1+n");
+assert_checkequal(out.a, out.b);
+out = testGVN("a=n*3;b=3*n");
+assert_checkequal(out.a, out.b);
+out = testGVN("a=0.5*x;b=x/2");
+assert_checkequal(out.a, out.b);
+out = testGVN("a=2*n+1;b=1+n;c=b+n");
+assert_checkequal(out.a, out.c);
+out = testGVN("a=x+2;b=x+x*x+5+2*x-1+x;c=a*a;d=a^2;e=(x+2)*(2+x)");
+assert_checkequal(out.b, out.c);
+assert_checkequal(out.b, out.d);
+assert_checkequal(out.b, out.e);
+out = testGVN("a=b+c;d=a^3;e=(b+c)*(b+c)^2;f=b^3+3*b^2*c+3*b*c^2+c^3");
+assert_checkequal(out.d, out.e);
+assert_checkequal(out.d, out.f);
+out = testGVN("a=b+c;d=a*(e+f);g=d^2;h=b^2*e^2+b^2*f^2+c^2*e^2+c^2*f^2+2*b^2*e*f+2*b*c*e^2+4*b*e*c*f+2*b*c*f^2+2*c^2*e*f");
+assert_checkequal(out.g, out.h);
+out = testGVN("a=x-3;b=a^3;c=-18/2*x^2+(32-5)*x-(168/6-1)+x^2*x");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=n+1;b=a+n;c=2*b;d=c+b;e=d+a-1;A=n+1;B=2*n+1;C=4*n+2;D=6*n+3;E=7*n+3");
+assert_checkequal(out.a, out.A);
+assert_checkequal(out.b, out.B);
+assert_checkequal(out.c, out.C);
+assert_checkequal(out.d, out.D);
+assert_checkequal(out.e, out.E);
+out = testGVN("a=x^10+y*x+1;b=a(x=d+1,y=d+e);c=(d+1)^10+(d+e)*(d+1)+1");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(x=d+1,y=d+e);c=(d+1)^5+(d+1)^3+(d+1)^2+(d+e)*(d+1)+1");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^10+y*x+1;b=a(x=2,y=5);c=1035");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^10+y*x+1;b=a(x=y);c=y^10+y^2+1");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^10+y*x+1;b=a(x=2);c=1025+2*y");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^10+y*x+1;b=a(y=3);c=x^10+3*x+1");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(x=2);c=45+2*y");
+assert_checkequal(out.b, out.c);
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(y=x);c=x^5+x^3+2*x^2+1");
+assert_checkequal(out.b, out.c);
diff --git a/scilab/modules/ast/tests/unit_tests/gvn.tst b/scilab/modules/ast/tests/unit_tests/gvn.tst
new file mode 100644 (file)
index 0000000..e42f9ee
--- /dev/null
@@ -0,0 +1,72 @@
+// ============================================================================
+// Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+// Copyright (C) 2015 - Scilab Enterprises - Calixte DENIZET
+//
+//  This file is distributed under the same license as the Scilab package.
+// ============================================================================
+
+// <-- JVM NOT MANDATORY -->
+
+out = testGVN("a=1;b=1");
+assert_checkequal(out.a, out.b);
+
+out = testGVN("a=-1-5+4-3;b=7-12");
+assert_checkequal(out.a, out.b);
+
+out = testGVN("a=n+1;b=1+n");
+assert_checkequal(out.a, out.b);
+
+out = testGVN("a=n*3;b=3*n");
+assert_checkequal(out.a, out.b);
+
+out = testGVN("a=0.5*x;b=x/2");
+assert_checkequal(out.a, out.b);
+
+out = testGVN("a=2*n+1;b=1+n;c=b+n");
+assert_checkequal(out.a, out.c);
+
+out = testGVN("a=x+2;b=x+x*x+5+2*x-1+x;c=a*a;d=a^2;e=(x+2)*(2+x)");
+assert_checkequal(out.b, out.c);
+assert_checkequal(out.b, out.d);
+assert_checkequal(out.b, out.e);
+
+out = testGVN("a=b+c;d=a^3;e=(b+c)*(b+c)^2;f=b^3+3*b^2*c+3*b*c^2+c^3");
+assert_checkequal(out.d, out.e);
+assert_checkequal(out.d, out.f);
+
+out = testGVN("a=b+c;d=a*(e+f);g=d^2;h=b^2*e^2+b^2*f^2+c^2*e^2+c^2*f^2+2*b^2*e*f+2*b*c*e^2+4*b*e*c*f+2*b*c*f^2+2*c^2*e*f");
+assert_checkequal(out.g, out.h);
+
+out = testGVN("a=x-3;b=a^3;c=-18/2*x^2+(32-5)*x-(168/6-1)+x^2*x");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=n+1;b=a+n;c=2*b;d=c+b;e=d+a-1;A=n+1;B=2*n+1;C=4*n+2;D=6*n+3;E=7*n+3");
+assert_checkequal(out.a, out.A);
+assert_checkequal(out.b, out.B);
+assert_checkequal(out.c, out.C);
+assert_checkequal(out.d, out.D);
+assert_checkequal(out.e, out.E);
+
+out = testGVN("a=x^10+y*x+1;b=a(x=d+1,y=d+e);c=(d+1)^10+(d+e)*(d+1)+1");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(x=d+1,y=d+e);c=(d+1)^5+(d+1)^3+(d+1)^2+(d+e)*(d+1)+1");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^10+y*x+1;b=a(x=2,y=5);c=1035");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^10+y*x+1;b=a(x=y);c=y^10+y^2+1");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^10+y*x+1;b=a(x=2);c=1025+2*y");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^10+y*x+1;b=a(y=3);c=x^10+3*x+1");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(x=2);c=45+2*y");
+assert_checkequal(out.b, out.c);
+
+out = testGVN("a=x^5+x^3+x^2+y*x+1;b=a(y=x);c=x^5+x^3+2*x^2+1");
+assert_checkequal(out.b, out.c);
\ No newline at end of file
index 449d350..f829a0e 100644 (file)
@@ -15,7 +15,8 @@ GATEWAY_CPP_SOURCES =  \
     sci_gateway/cpp/sci_getThreads.cpp \
     sci_gateway/cpp/sci_macrovar.cpp \
     sci_gateway/cpp/sci_libraryinfo.cpp \
-    sci_gateway/cpp/sci_librarieslist.cpp
+    sci_gateway/cpp/sci_librarieslist.cpp \
+    sci_gateway/cpp/sci_testGVN.cpp
 
 libscifunctions_la_CPPFLAGS = \
     -I$(srcdir)/includes/ \
index f3aca39..72e66ec 100644 (file)
@@ -173,7 +173,8 @@ am__objects_2 = sci_gateway/cpp/libscifunctions_la-sci_exec.lo \
        sci_gateway/cpp/libscifunctions_la-sci_getThreads.lo \
        sci_gateway/cpp/libscifunctions_la-sci_macrovar.lo \
        sci_gateway/cpp/libscifunctions_la-sci_libraryinfo.lo \
-       sci_gateway/cpp/libscifunctions_la-sci_librarieslist.lo
+       sci_gateway/cpp/libscifunctions_la-sci_librarieslist.lo \
+       sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo
 am_libscifunctions_la_OBJECTS = $(am__objects_1) $(am__objects_2)
 libscifunctions_la_OBJECTS = $(am_libscifunctions_la_OBJECTS)
 AM_V_lt = $(am__v_lt_@AM_V@)
@@ -557,7 +558,8 @@ GATEWAY_CPP_SOURCES = \
     sci_gateway/cpp/sci_getThreads.cpp \
     sci_gateway/cpp/sci_macrovar.cpp \
     sci_gateway/cpp/sci_libraryinfo.cpp \
-    sci_gateway/cpp/sci_librarieslist.cpp
+    sci_gateway/cpp/sci_librarieslist.cpp \
+    sci_gateway/cpp/sci_testGVN.cpp
 
 libscifunctions_la_CPPFLAGS = \
     -I$(srcdir)/includes/ \
@@ -792,6 +794,9 @@ sci_gateway/cpp/libscifunctions_la-sci_libraryinfo.lo:  \
 sci_gateway/cpp/libscifunctions_la-sci_librarieslist.lo:  \
        sci_gateway/cpp/$(am__dirstamp) \
        sci_gateway/cpp/$(DEPDIR)/$(am__dirstamp)
+sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo:  \
+       sci_gateway/cpp/$(am__dirstamp) \
+       sci_gateway/cpp/$(DEPDIR)/$(am__dirstamp)
 
 libscifunctions.la: $(libscifunctions_la_OBJECTS) $(libscifunctions_la_DEPENDENCIES) $(EXTRA_libscifunctions_la_DEPENDENCIES) 
        $(AM_V_CXXLD)$(CXXLINK) -rpath $(pkglibdir) $(libscifunctions_la_OBJECTS) $(libscifunctions_la_LIBADD) $(LIBS)
@@ -815,6 +820,7 @@ distclean-compile:
 @AMDEP_TRUE@@am__include@ @am__quote@sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_librarieslist.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_libraryinfo.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_macrovar.Plo@am__quote@
+@AMDEP_TRUE@@am__include@ @am__quote@sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_testGVN.Plo@am__quote@
 @AMDEP_TRUE@@am__include@ @am__quote@sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_whereis.Plo@am__quote@
 
 .c.o:
@@ -935,6 +941,13 @@ sci_gateway/cpp/libscifunctions_la-sci_librarieslist.lo: sci_gateway/cpp/sci_lib
 @AMDEP_TRUE@@am__fastdepCXX_FALSE@     DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
 @am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CXX $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libscifunctions_la_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o sci_gateway/cpp/libscifunctions_la-sci_librarieslist.lo `test -f 'sci_gateway/cpp/sci_librarieslist.cpp' || echo '$(srcdir)/'`sci_gateway/cpp/sci_librarieslist.cpp
 
+sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo: sci_gateway/cpp/sci_testGVN.cpp
+@am__fastdepCXX_TRUE@  $(AM_V_CXX)$(LIBTOOL) $(AM_V_lt) --tag=CXX $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libscifunctions_la_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -MT sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo -MD -MP -MF sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_testGVN.Tpo -c -o sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo `test -f 'sci_gateway/cpp/sci_testGVN.cpp' || echo '$(srcdir)/'`sci_gateway/cpp/sci_testGVN.cpp
+@am__fastdepCXX_TRUE@  $(AM_V_at)$(am__mv) sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_testGVN.Tpo sci_gateway/cpp/$(DEPDIR)/libscifunctions_la-sci_testGVN.Plo
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@     $(AM_V_CXX)source='sci_gateway/cpp/sci_testGVN.cpp' object='sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo' libtool=yes @AMDEPBACKSLASH@
+@AMDEP_TRUE@@am__fastdepCXX_FALSE@     DEPDIR=$(DEPDIR) $(CXXDEPMODE) $(depcomp) @AMDEPBACKSLASH@
+@am__fastdepCXX_FALSE@ $(AM_V_CXX@am__nodep@)$(LIBTOOL) $(AM_V_lt) --tag=CXX $(AM_LIBTOOLFLAGS) $(LIBTOOLFLAGS) --mode=compile $(CXX) $(DEFS) $(DEFAULT_INCLUDES) $(INCLUDES) $(libscifunctions_la_CPPFLAGS) $(CPPFLAGS) $(AM_CXXFLAGS) $(CXXFLAGS) -c -o sci_gateway/cpp/libscifunctions_la-sci_testGVN.lo `test -f 'sci_gateway/cpp/sci_testGVN.cpp' || echo '$(srcdir)/'`sci_gateway/cpp/sci_testGVN.cpp
+
 mostlyclean-libtool:
        -rm -f *.lo
 
index 7099802..e13ee27 100644 (file)
@@ -26,6 +26,7 @@ CPP_GATEWAY_PROTOTYPE_EXPORT(sci_getThreads, FUNCTIONS_GW_IMPEXP);
 CPP_GATEWAY_PROTOTYPE_EXPORT(sci_macrovar, FUNCTIONS_GW_IMPEXP);
 CPP_GATEWAY_PROTOTYPE_EXPORT(sci_libraryinfo, FUNCTIONS_GW_IMPEXP);
 CPP_GATEWAY_PROTOTYPE_EXPORT(sci_librarieslist, FUNCTIONS_GW_IMPEXP);
+CPP_GATEWAY_PROTOTYPE_EXPORT(sci_testGVN, FUNCTIONS_GW_IMPEXP);
 
 #endif /* __FUNCTIONS_GW_HXX__ */
 
index 1abe911..d9c19bc 100644 (file)
     <ClCompile Include="sci_libraryinfo.cpp" />
     <ClCompile Include="sci_librarieslist.cpp" />
     <ClCompile Include="sci_macrovar.cpp" />
+    <ClCompile Include="sci_testGVN.cpp" />
     <ClCompile Include="sci_whereis.cpp" />
   </ItemGroup>
   <ItemGroup>
index 94443d0..c2011f4 100644 (file)
@@ -42,6 +42,9 @@
     <ClCompile Include="sci_librarieslist.cpp">
       <Filter>Source Files</Filter>
     </ClCompile>
+    <ClCompile Include="sci_testGVN.cpp">
+      <Filter>Source Files</Filter>
+    </ClCompile>
   </ItemGroup>
   <ItemGroup>
     <ClInclude Include="..\..\includes\dynlib_functions_gw.h">
diff --git a/scilab/modules/functions/sci_gateway/cpp/sci_testGVN.cpp b/scilab/modules/functions/sci_gateway/cpp/sci_testGVN.cpp
new file mode 100644 (file)
index 0000000..b0a3393
--- /dev/null
@@ -0,0 +1,94 @@
+/*
+* Scilab ( http://www.scilab.org/ ) - This file is part of Scilab
+* Copyright (C) 2006 - INRIA - Antoine ELIAS
+*
+* This file must be used under the terms of the CeCILL.
+* This source file is licensed as described in the file COPYING, which
+* you should have received as part of this distribution.  The terms
+* are also available at
+* http://www.cecill.info/licences/Licence_CeCILL_V2-en.txt
+*
+*/
+
+#include <string.h>
+
+#include "gvn/TestGVNVisitor.hxx"
+
+#include "parser.hxx"
+#include "functions_gw.hxx"
+#include "execvisitor.hxx"
+#include "mutevisitor.hxx"
+#include "debugvisitor.hxx"
+#include "printvisitor.hxx"
+#include "visitor_common.hxx"
+#include "scilabWrite.hxx"
+#include "scilabexception.hxx"
+#include "configvariable.hxx"
+#include "context.hxx"
+
+#include <iostream>
+#include <fstream>
+#include <string>
+
+extern "C"
+{
+#include "Scierror.h"
+#include "localization.h"
+}
+
+using namespace std;
+using namespace types;
+using namespace ast;
+
+/*--------------------------------------------------------------------------*/
+Function::ReturnValue sci_testGVN(types::typed_list &in, int _iRetCount, types::typed_list &out)
+{
+    ast::Exp * pExp = 0;
+
+    if (in.size() != 1)
+    {
+        Scierror(999, _("%s: Wrong number of input arguments: %d expected.\n"), "jit" , 1);
+        return Function::Error;
+    }
+
+    if (!in[0]->isString() || in[0]->getAs<types::String>()->getSize() != 1)
+    {
+        Scierror(999, _("%s: Wrong type for input argument #%d: A string expected.\n"), "jit" , 1);
+        return Function::Error;
+    }
+
+    Parser parser;
+    parser.parse(in[0]->getAs<types::String>()->get(0));
+    if (parser.getExitStatus() != Parser::Succeded)
+    {
+        char* pst = wide_string_to_UTF8(parser.getErrorMessage());
+        Scierror(999, "%s", pst);
+        FREE(pst);
+        return Function::Error;
+    }
+
+    pExp = parser.getTree();
+
+    if (!pExp)
+    {
+        return Function::Error;
+    }
+
+    analysis::TestGVNVisitor gvn;
+    pExp->accept(gvn);
+    //gvn.print_info();
+
+    Struct * pOut = new Struct(1, 1);
+    std::map<std::wstring, unsigned long long> maps = gvn.getSymMap();
+    for (const auto & p : maps)
+    {
+        pOut->addField(p.first);
+        pOut->get(0)->set(p.first, new Double((double) p.second));
+    }
+
+    out.push_back(pOut);
+
+    delete pExp;
+
+    return Function::OK;
+}
index c4d4425..4ba3cf8 100644 (file)
@@ -28,4 +28,5 @@
     <gateway name="sci_macrovar"            function="macrovar"             type="1" />
     <gateway name="sci_libraryinfo"         function="libraryinfo"          type="1" />
     <gateway name="sci_librarieslist"       function="librarieslist"        type="1" />
+    <gateway name="sci_testGVN"             function="testGVN"              type="1" />
 </module>