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

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.

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.

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:

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.
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.
We could value number vuses in more cases, particularly, whole structure copies. vn_nary_op hashtable helpers.