LCOV - code coverage report
Current view: top level - gcc - splay-tree-utils.h (source / functions) Coverage Total Hit
Test: gcc.info Lines: 100.0 % 12 12
Test Date: 2024-03-23 14:05:01 Functions: - 0 0
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: - 0 0

             Branch data     Line data    Source code
       1                 :             : // Splay tree utilities                                             -*- C++ -*-
       2                 :             : // Copyright (C) 2020-2024 Free Software Foundation, Inc.
       3                 :             : //
       4                 :             : // This file is part of GCC.
       5                 :             : //
       6                 :             : // GCC is free software; you can redistribute it and/or modify it under
       7                 :             : // the terms of the GNU General Public License as published by the Free
       8                 :             : // Software Foundation; either version 3, or (at your option) any later
       9                 :             : // version.
      10                 :             : //
      11                 :             : // GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12                 :             : // WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13                 :             : // FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14                 :             : // for more details.
      15                 :             : //
      16                 :             : // You should have received a copy of the GNU General Public License
      17                 :             : // along with GCC; see the file COPYING3.  If not see
      18                 :             : // <http://www.gnu.org/licenses/>.
      19                 :             : 
      20                 :             : // Implement splay tree node accessors for a class that stores its
      21                 :             : // two child nodes in a member variable of the form:
      22                 :             : //
      23                 :             : //    Node m_children[2];
      24                 :             : template<typename Node>
      25                 :             : class default_splay_tree_accessors
      26                 :             : {
      27                 :             : public:
      28                 :             :   using node_type = Node;
      29                 :             : 
      30                 :             :   static auto
      31                 :   168589665 :   child (node_type node, unsigned int index)
      32                 :             :     -> decltype (node->m_children[index]) &
      33                 :             :   {
      34                 :    26550113 :     return node->m_children[index];
      35                 :             :   }
      36                 :             : };
      37                 :             : 
      38                 :             : // Implement splay tree node accessors for a class that stores its
      39                 :             : // two child nodes in a member variable of the form:
      40                 :             : //
      41                 :             : //    Node m_children[2];
      42                 :             : //
      43                 :             : // and also stores its parent node in a member variable of the form:
      44                 :             : //
      45                 :             : //    Node m_parent;
      46                 :             : template<typename Node>
      47                 :             : class default_splay_tree_accessors_with_parent
      48                 :             :   : public default_splay_tree_accessors<Node>
      49                 :             : {
      50                 :             : public:
      51                 :             :   using node_type = Node;
      52                 :             : 
      53                 :             :   static auto
      54                 :             :   parent (node_type node) -> decltype (node->m_parent) &
      55                 :             :   {
      56                 :             :     return node->m_parent;
      57                 :             :   }
      58                 :             : };
      59                 :             : 
      60                 :             : // Base is a splay tree accessor class for nodes that have no parent field.
      61                 :             : // Base therefore provides a Base::child method but does not provide a
      62                 :             : // Base::parent method.  Extend Base with dummy routines for setting the
      63                 :             : // parent, which is a no-op when the parent is not stored.
      64                 :             : template<typename Base>
      65                 :             : class splay_tree_accessors_without_parent : public Base
      66                 :             : {
      67                 :             : public:
      68                 :             :   using typename Base::node_type;
      69                 :             : 
      70                 :        2274 :   static void set_parent (node_type, node_type) {}
      71                 :             : };
      72                 :             : 
      73                 :             : // Base is splay tree accessor class for nodes that have a parent field.
      74                 :             : // Base therefore provides both Base::child and Base::parent methods.
      75                 :             : // Extend Base with routines for setting the parent.
      76                 :             : template<typename Base>
      77                 :             : class splay_tree_accessors_with_parent : public Base
      78                 :             : {
      79                 :             : public:
      80                 :             :   using typename Base::node_type;
      81                 :             : 
      82                 :             :   // Record that NODE's parent is now NEW_PARENT.
      83                 :             :   static void
      84                 :    30356718 :   set_parent (node_type node, node_type new_parent)
      85                 :             :   {
      86                 :      826600 :     Base::parent (node) = new_parent;
      87                 :      242741 :   }
      88                 :             : };
      89                 :             : 
      90                 :             : // A base class that provides some splay tree operations that are common
      91                 :             : // to both rooted_splay_tree and rootless_splay_tree.
      92                 :             : //
      93                 :             : // Nodes in the splay tree have type Accessors::node_type; this is
      94                 :             : // usually a pointer type.  The Accessors class provides the following
      95                 :             : // static member functions for accessing nodes:
      96                 :             : //
      97                 :             : // - Accessors::child (NODE, INDEX)
      98                 :             : //     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
      99                 :             : //     to where NODE's left child is stored, otherwise return a reference
     100                 :             : //     to where NODE's right child is stored.
     101                 :             : //
     102                 :             : // - Accessors::set_parent (NODE, PARENT)
     103                 :             : //     Record that NODE's parent node is now PARENT.
     104                 :             : template<typename Accessors>
     105                 :             : class base_splay_tree : protected Accessors
     106                 :             : {
     107                 :             : public:
     108                 :             :   using typename Accessors::node_type;
     109                 :             : 
     110                 :             :   // INDEX is either 0 or 1.  If INDEX is 0, insert CHILD immediately
     111                 :             :   // before NODE, otherwise insert CHILD immediately after NODE.
     112                 :             :   //
     113                 :             :   // Complexity: O(1).
     114                 :             :   static void insert_child (node_type node, unsigned int index,
     115                 :             :                             node_type child);
     116                 :             : 
     117                 :             :   // Print NODE and its child nodes to PP for debugging purposes,
     118                 :             :   // using PRINTER (PP, N) to print the data for node N.
     119                 :             :   template<typename Printer>
     120                 :             :   static void print (pretty_printer *pp, node_type node, Printer printer);
     121                 :             : 
     122                 :             : protected:
     123                 :             :   using Accessors::set_parent;
     124                 :             : 
     125                 :             :   static node_type get_child (node_type, unsigned int);
     126                 :             :   static void set_child (node_type, unsigned int, node_type);
     127                 :             :   static node_type promote_child (node_type, unsigned int);
     128                 :             :   static void promote_child (node_type, unsigned int, node_type);
     129                 :             : 
     130                 :             :   template<unsigned int N>
     131                 :             :   static node_type splay_limit (node_type);
     132                 :             : 
     133                 :             :   static node_type remove_node_internal (node_type);
     134                 :             : 
     135                 :             :   template<typename Printer>
     136                 :             :   static void print (pretty_printer *pp, node_type node, Printer printer,
     137                 :             :                      char, vec<char> &);
     138                 :             : };
     139                 :             : 
     140                 :             : // This class provides splay tree routines for cases in which the root
     141                 :             : // of the splay tree is known.  It works with both nodes that store
     142                 :             : // their parent node and nodes that don't.
     143                 :             : //
     144                 :             : // The class is lightweight: it only contains a single root node.
     145                 :             : template<typename Accessors>
     146                 :             : class rooted_splay_tree : public base_splay_tree<Accessors>
     147                 :             : {
     148                 :             :   using parent = base_splay_tree<Accessors>;
     149                 :             : 
     150                 :             : public:
     151                 :             :   using typename Accessors::node_type;
     152                 :             : 
     153                 :             : protected:
     154                 :             :   // The root of the splay tree, or node_type () if the tree is empty.
     155                 :             :   node_type m_root;
     156                 :             : 
     157                 :             : public:
     158                 :   154973400 :   rooted_splay_tree () : m_root () {}
     159                 :             : 
     160                 :             :   // Construct a tree with the specified root node.
     161                 :    32332927 :   rooted_splay_tree (node_type root) : m_root (root) {}
     162                 :             : 
     163                 :             :   // Return the root of the tree.
     164                 :     3311674 :   node_type root () const { return m_root; }
     165                 :             : 
     166                 :             :   // Return true if the tree contains any nodes.
     167                 :   197543530 :   explicit operator bool () const { return m_root; }
     168                 :             : 
     169                 :             :   // Dereference the root node.
     170                 :    15797759 :   node_type operator-> () { return m_root; }
     171                 :             : 
     172                 :             :   // Insert NEW_NODE into the splay tree, if no equivalent node already
     173                 :             :   // exists.  For a given node N, COMPARE (N) should return:
     174                 :             :   //
     175                 :             :   // - a negative value if NEW_NODE should come before N
     176                 :             :   // - zero if NEW_NODE and N are the same
     177                 :             :   // - a positive value if NEW_NODE should come after N
     178                 :             :   //
     179                 :             :   // Return true if NEW_NODE was inserted.
     180                 :             :   //
     181                 :             :   // On return, NEW_NODE or its equivalent is the root of the tree.
     182                 :             :   //
     183                 :             :   // Complexity: amortized O(C log N), worst-cast O(C N), where C is
     184                 :             :   // the complexity of the comparison.
     185                 :             :   template<typename Comparator>
     186                 :             :   bool insert (node_type new_node, Comparator compare);
     187                 :             : 
     188                 :             :   // Insert NEW_NODE into the splay tree, given that NEW_NODE is the
     189                 :             :   // maximum node of the new tree.  On return, NEW_NODE is also the
     190                 :             :   // root of the tree.
     191                 :             :   //
     192                 :             :   // Complexity: O(1).
     193                 :             :   void insert_max_node (node_type new_node);
     194                 :             : 
     195                 :             :   // Splice NEXT_TREE onto this one, given that all nodes in NEXT_TREE
     196                 :             :   // are greater than the maximum node in this tree.  NEXT_TREE should
     197                 :             :   // not be used afterwards.
     198                 :             :   //
     199                 :             :   // Complexity: O(1) if the root of the splay tree is already the maximum
     200                 :             :   // node.  Otherwise amortized O(log N), worst-cast O(N).
     201                 :             :   void splice_next_tree (rooted_splay_tree next_tree);
     202                 :             : 
     203                 :             :   // The root of the tree is currently the maximum node.  Replace it
     204                 :             :   // with NEW_NODE.
     205                 :             :   //
     206                 :             :   // Complexity: O(1).
     207                 :             :   void replace_max_node_at_root (node_type new_node);
     208                 :             : 
     209                 :             :   // Remove the root node of the splay tree.
     210                 :             :   //
     211                 :             :   // Complexity: O(1) if removing the maximum or minimum node.
     212                 :             :   // Otherwise amortized O(log N), worst-cast O(N).
     213                 :             :   void remove_root ();
     214                 :             : 
     215                 :             :   // Split the left child of the current root out into a separate tree
     216                 :             :   // and return the new tree.
     217                 :             :   rooted_splay_tree split_before_root ();
     218                 :             : 
     219                 :             :   // Split the right child of the current root out into a separate tree
     220                 :             :   // and return the new tree.
     221                 :             :   rooted_splay_tree split_after_root ();
     222                 :             : 
     223                 :             :   // If the root is not the minimum node of the splay tree, bring the previous
     224                 :             :   // node to the root and return true, otherwise return false.
     225                 :             :   //
     226                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     227                 :             :   bool splay_prev_node ();
     228                 :             : 
     229                 :             :   // If the root is not the maximum node of the splay tree, bring the next
     230                 :             :   // node to the root and return true, otherwise return false.
     231                 :             :   //
     232                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     233                 :             :   bool splay_next_node ();
     234                 :             : 
     235                 :             :   // Bring the minimum node of the splay tree to the root.
     236                 :             :   //
     237                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     238                 :             :   void splay_min_node ();
     239                 :             : 
     240                 :             :   // Bring the maximum node of the splay tree to the root.
     241                 :             :   //
     242                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     243                 :             :   void splay_max_node ();
     244                 :             : 
     245                 :             :   // Return the minimum node of the splay tree, or node_type () if the
     246                 :             :   // tree is empty.  On return, the minimum node (if any) is also the
     247                 :             :   // root of the tree.
     248                 :             :   //
     249                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     250                 :             :   node_type min_node ();
     251                 :             : 
     252                 :             :   // Return the maximum node of the splay tree, or node_type () if the
     253                 :             :   // tree is empty.  On return, the maximum node (if any) is also the
     254                 :             :   // root of the tree.
     255                 :             :   //
     256                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     257                 :             :   node_type max_node ();
     258                 :             : 
     259                 :             :   // Search the splay tree.  For a given node N, COMPARE (N) should return:
     260                 :             :   //
     261                 :             :   // - a negative value if N is bigger than the node being searched for
     262                 :             :   // - zero if N is the node being searched for
     263                 :             :   // - a positive value if N is smaller than the node being searched for
     264                 :             :   //
     265                 :             :   // If the node that COMPARE is looking for exists, install it as the root
     266                 :             :   // node of the splay tree.  Otherwise, arbitrarily pick either:
     267                 :             :   //
     268                 :             :   // - the maximum node that is smaller than the node being searched for or
     269                 :             :   // - the minimum node that is bigger than the node being searched for
     270                 :             :   //
     271                 :             :   // and install that node as the root instead.
     272                 :             :   //
     273                 :             :   // Return the result of COMPARE for the new root.
     274                 :             :   //
     275                 :             :   // This form of lookup is intended for cases in which both the following
     276                 :             :   // are true:
     277                 :             :   //
     278                 :             :   // (a) The work that COMPARE needs to do to detect if a node is too big
     279                 :             :   //     is the same as the work that COMPARE needs to do to detect if a
     280                 :             :   //     node is too small.  (This is not true of range comparisons,
     281                 :             :   //     for example.)
     282                 :             :   //
     283                 :             :   // (b) COMPARE is (or might be) relatively complex.
     284                 :             :   //
     285                 :             :   // This form of lookup is also useful if the items being compared naturally
     286                 :             :   // provide a <=>-style comparison result, without the result having to be
     287                 :             :   // forced by the equivalent of a ?: expression.
     288                 :             :   //
     289                 :             :   // The implementation only invokes COMPARE once per node.
     290                 :             :   //
     291                 :             :   // Complexity: amortized O(C log N), worst-cast O(C N), where C is
     292                 :             :   // the complexity of the comparison.
     293                 :             :   template<typename Comparator>
     294                 :             :   auto lookup (Comparator compare) -> decltype (compare (m_root));
     295                 :             : 
     296                 :             :   // Search the splay tree.  For a given node N, WANT_SOMETHING_SMALLER (N)
     297                 :             :   // is true if N is too big and WANT_SOMETHING_BIGGER (N) is true if N
     298                 :             :   // is too small.  Both functions return false if N is the node being
     299                 :             :   // searched for.
     300                 :             :   //
     301                 :             :   // If the node that is being searched for exists, install it as the root
     302                 :             :   // node of the splay tree and return 0.  Otherwise, arbitrarily choose
     303                 :             :   // between these two options:
     304                 :             :   //
     305                 :             :   // - Install the maximum node that is smaller than the node being
     306                 :             :   //   searched for as the root of the splay tree and return 1.
     307                 :             :   //
     308                 :             :   // - Install the minimum node that is bigger than the node being
     309                 :             :   //   searched for and return -1.
     310                 :             :   //
     311                 :             :   // This form of lookup is intended for cases in which either of the
     312                 :             :   // following are true:
     313                 :             :   //
     314                 :             :   // (a) WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER test different
     315                 :             :   //     parts of the node's data.  For example, when comparing ranges,
     316                 :             :   //     WANT_SOMETHING_SMALLER would test the lower limit of the given
     317                 :             :   //     node's range while WANT_SOMETHING_BIGGER would test the upper
     318                 :             :   //     limit of the given node's range.
     319                 :             :   //
     320                 :             :   // (b) There is no significant overhead to calling both
     321                 :             :   //     WANT_SOMETHING_SMALLER and WANT_SOMETHING_BIGGER for the same node.
     322                 :             :   //
     323                 :             :   // Complexity: amortized O(C log N), worst-cast O(C N), where C is
     324                 :             :   // the complexity of the comparisons.
     325                 :             :   template<typename LeftPredicate, typename RightPredicate>
     326                 :             :   int lookup (LeftPredicate want_something_smaller,
     327                 :             :               RightPredicate want_something_bigger);
     328                 :             : 
     329                 :             :   // Keep the ability to print subtrees.
     330                 :             :   using parent::print;
     331                 :             : 
     332                 :             :   // Print the tree to PP for debugging purposes, using PRINTER (PP, N)
     333                 :             :   // to print the data for node N.
     334                 :             :   template<typename Printer>
     335                 :             :   void print (pretty_printer *pp, Printer printer) const;
     336                 :             : 
     337                 :             : protected:
     338                 :             :   using parent::get_child;
     339                 :             :   using parent::set_child;
     340                 :             :   using parent::promote_child;
     341                 :             : 
     342                 :             :   using parent::set_parent;
     343                 :             : 
     344                 :             :   template<unsigned int N>
     345                 :             :   bool splay_neighbor ();
     346                 :             : };
     347                 :             : 
     348                 :             : // Provide splay tree routines for nodes of type Accessors::node_type,
     349                 :             : // which doesn't have a parent field.  Use Accessors::child to access
     350                 :             : // the children of a node.
     351                 :             : template<typename Accessors>
     352                 :             : using splay_tree_without_parent
     353                 :             :   = rooted_splay_tree<splay_tree_accessors_without_parent<Accessors>>;
     354                 :             : 
     355                 :             : // A splay tree for nodes of type Node, which is usually a pointer type.
     356                 :             : // The child nodes are stored in a member variable:
     357                 :             : //
     358                 :             : //    Node m_children[2];
     359                 :             : //
     360                 :             : // Node does not have a parent field.
     361                 :             : template<typename Node>
     362                 :             : using default_splay_tree
     363                 :             :   = splay_tree_without_parent<default_splay_tree_accessors<Node>>;
     364                 :             : 
     365                 :             : // A simple splay tree node that stores a value of type T.
     366                 :             : template<typename T>
     367                 :             : class splay_tree_node
     368                 :             : {
     369                 :             :   friend class default_splay_tree_accessors<splay_tree_node *>;
     370                 :             : 
     371                 :             : public:
     372                 :             :   splay_tree_node () = default;
     373                 :    30473640 :   splay_tree_node (T value) : m_value (value), m_children () {}
     374                 :             : 
     375                 :             :   T &value () { return m_value; }
     376                 :             :   const T &value () const { return m_value; }
     377                 :             : 
     378                 :             : private:
     379                 :             :   T m_value;
     380                 :             :   splay_tree_node *m_children[2];
     381                 :             : };
     382                 :             : 
     383                 :             : // A splay tree whose nodes hold values of type T.
     384                 :             : template<typename T>
     385                 :             : using splay_tree = default_splay_tree<splay_tree_node<T> *>;
     386                 :             : 
     387                 :             : // Provide splay tree routines for cases in which the root of the tree
     388                 :             : // is not explicitly stored.
     389                 :             : //
     390                 :             : // The nodes of the tree have type Accessors::node_type, which is usually
     391                 :             : // a pointer type.  The nodes have a link back to their parent.
     392                 :             : //
     393                 :             : // The Accessors class provides the following static member functions:
     394                 :             : //
     395                 :             : // - Accessors::child (NODE, INDEX)
     396                 :             : //     INDEX is guaranteed to be 0 or 1.  If INDEX is 0, return a reference
     397                 :             : //     to where NODE's left child is stored, otherwise return a reference
     398                 :             : //     to where NODE's right child is stored.
     399                 :             : //
     400                 :             : // - Accessors::parent (NODE)
     401                 :             : //     Return a reference to where NODE's parent is stored.
     402                 :             : template<typename Accessors>
     403                 :             : class rootless_splay_tree
     404                 :             :   : public base_splay_tree<splay_tree_accessors_with_parent<Accessors>>
     405                 :             : {
     406                 :             :   using full_accessors = splay_tree_accessors_with_parent<Accessors>;
     407                 :             :   using parent = base_splay_tree<full_accessors>;
     408                 :             : 
     409                 :             : public:
     410                 :             :   using rooted = rooted_splay_tree<full_accessors>;
     411                 :             : 
     412                 :             :   using typename Accessors::node_type;
     413                 :             : 
     414                 :             :   // Remove NODE from the splay tree.  Return the node that replaces it,
     415                 :             :   // or null if NODE had no children.
     416                 :             :   //
     417                 :             :   // Complexity: O(1) if removing the maximum or minimum node.
     418                 :             :   // Otherwise amortized O(log N), worst-cast O(N).
     419                 :             :   static node_type remove_node (node_type node);
     420                 :             : 
     421                 :             :   // Splay NODE so that it becomes the root of the splay tree.
     422                 :             :   //
     423                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     424                 :             :   static void splay (node_type node);
     425                 :             : 
     426                 :             :   // Like splay, but take advantage of the fact that NODE is known to be
     427                 :             :   // the minimum node in the tree.
     428                 :             :   //
     429                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     430                 :             :   static void splay_known_min_node (node_type node);
     431                 :             : 
     432                 :             :   // Like splay, but take advantage of the fact that NODE is known to be
     433                 :             :   // the maximum node in the tree.
     434                 :             :   //
     435                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     436                 :             :   static void splay_known_max_node (node_type node);
     437                 :             : 
     438                 :             :   // Splay NODE while looking for an ancestor node N for which PREDICATE (N)
     439                 :             :   // is true.  If such an ancestor node exists, stop the splay operation
     440                 :             :   // early and return PREDICATE (N).  Otherwise, complete the splay operation
     441                 :             :   // and return DEFAULT_RESULT.  In the latter case, NODE is now the root of
     442                 :             :   // the splay tree.
     443                 :             :   //
     444                 :             :   // Note that this routine only examines nodes that happen to be ancestors
     445                 :             :   // of NODE.  It does not search the full tree.
     446                 :             :   //
     447                 :             :   // Complexity: amortized O(P log N), worst-cast O(P N), where P is the
     448                 :             :   // complexity of the predicate.
     449                 :             :   template<typename DefaultResult, typename Predicate>
     450                 :             :   static auto splay_and_search (node_type node, DefaultResult default_result,
     451                 :             :                                 Predicate predicate)
     452                 :             :     -> decltype (predicate (node, 0));
     453                 :             : 
     454                 :             :   // NODE1 and NODE2 are known to belong to the same splay tree.  Return:
     455                 :             :   //
     456                 :             :   // -1 if NODE1 < NODE2
     457                 :             :   // 0 if NODE1 == NODE2
     458                 :             :   // 1 if NODE1 > NODE2
     459                 :             :   //
     460                 :             :   // Complexity: amortized O(log N), worst-cast O(N).
     461                 :             :   static int compare_nodes (node_type node1, node_type node2);
     462                 :             : 
     463                 :             : protected:
     464                 :             :   using parent::get_child;
     465                 :             :   using parent::set_child;
     466                 :             :   using parent::promote_child;
     467                 :             : 
     468                 :             :   static node_type get_parent (node_type);
     469                 :             :   using parent::set_parent;
     470                 :             : 
     471                 :             :   static unsigned int child_index (node_type, node_type);
     472                 :             : 
     473                 :             :   static int compare_nodes_one_way (node_type, node_type);
     474                 :             : 
     475                 :             :   template<unsigned int N>
     476                 :             :   static void splay_known_limit (node_type);
     477                 :             : };
     478                 :             : 
     479                 :             : // Provide rootless splay tree routines for nodes of type Node.
     480                 :             : // The child nodes are stored in a member variable:
     481                 :             : //
     482                 :             : //    Node m_children[2];
     483                 :             : //
     484                 :             : // and the parent node is stored in a member variable:
     485                 :             : //
     486                 :             : //    Node m_parent;
     487                 :             : template<typename Node>
     488                 :             : using default_rootless_splay_tree
     489                 :             :   = rootless_splay_tree<default_splay_tree_accessors_with_parent<Node>>;
     490                 :             : 
     491                 :             : #include "splay-tree-utils.tcc"
        

Generated by: LCOV version 2.0-1

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.