Inheritance diagram for vn_nary_op_hasher:

Collaboration diagram for vn_nary_op_hasher:

Public Types
typedef vn_nary_op_s	value_type
typedef vn_nary_op_s	compare_type

Static Public Member Functions
static hashval_t	hash (const value_type *)
static bool	equal (const value_type , const compare_type )
static void	remove (vn_nary_op_s *p)

Detailed Description

@verbatim SCC value numbering for trees

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.

This algorithm is based on the SCC algorithm presented by Keith
   Cooper and L. Taylor Simpson in "SCC-Based Value numbering"
   (http://citeseer.ist.psu.edu/41805.html).  In
   straight line code, it is equivalent to a regular hash based value
   numbering that is performed in reverse postorder.

   For code with cycles, there are two alternatives, both of which
   require keeping the hashtables separate from the actual list of
   value numbers for SSA names.

   1. Iterate value numbering in an RPO walk of the blocks, removing
   all the entries from the hashtable after each iteration (but
   keeping the SSA name->value number mapping between iterations).
   Iterate until it does not change.

   2. Perform value numbering as part of an SCC walk on the SSA graph,
   iterating only the cycles in the SSA graph until they do not change
   (using a separate, optimistic hashtable for value numbering the SCC
   operands).

   The second is not just faster in practice (because most SSA graph
   cycles do not involve all the variables in the graph), it also has
   some nice properties.

   One of these nice properties is that when we pop an SCC off the
   stack, we are guaranteed to have processed all the operands coming from
   *outside of that SCC*, so we do not need to do anything special to
   ensure they have value numbers.

   Another nice property is that the SCC walk is done as part of a DFS
   of the SSA graph, which makes it easy to perform combining and
   simplifying operations at the same time.

   The code below is deliberately written in a way that makes it easy
   to separate the SCC walk from the other work it does.

   In order to propagate constants through the code, we track which
   expressions contain constants, and use those while folding.  In
   theory, we could also track expressions whose value numbers are
   replaced, in case we end up folding based on expression
   identities.

   In order to value number memory, we assign value numbers to vuses.
   This enables us to note that, for example, stores to the same
   address of the same value from the same starting memory states are
   equivalent.
   TODO:

   1. We can iterate only the changing portions of the SCC's, but
   I have not seen an SCC big enough for this to be a win.
   2. If you differentiate between phi nodes for loops and phi nodes
   for if-then-else, you can properly consider phi nodes in different
   blocks for equivalence.
   3. We could value number vuses in more cases, particularly, whole
   structure copies.

vn_nary_op hashtable helpers.

Member Typedef Documentation

typedef vn_nary_op_s vn_nary_op_hasher::compare_type

typedef vn_nary_op_s vn_nary_op_hasher::value_type

Member Function Documentation

bool vn_nary_op_hasher::equal	(	const value_type *	vno1,
		const compare_type *	vno2
	)

inlinestatic

Compare nary operations P1 and P2 and return true if they are
   equivalent.

References vn_nary_op_eq().

hashval_t vn_nary_op_hasher::hash ( const value_type * vno1 )

inlinestatic

Return the computed hashcode for nary operation P1.

References vn_nary_op_s::hashcode.

static void typed_noop_remove< vn_nary_op_s >::remove ( vn_nary_op_s * p )

inlinestaticinherited

Remove doing nothing.

The documentation for this struct was generated from the following file:

tree-ssa-sccvn.c

Public Types

Static Public Member Functions

Detailed Description

Member Typedef Documentation

Member Function Documentation