GCC Middle and Back End API Reference

Data Structures  
struct  vn_nary_op_hasher 
struct  vn_phi_hasher 
struct  vn_reference_hasher 
struct  vn_tables_s 
struct  vn_constant_hasher 
Typedefs  
typedef hash_table < vn_nary_op_hasher >  vn_nary_op_table_type 
typedef vn_nary_op_table_type::iterator  vn_nary_op_iterator_type 
typedef hash_table< vn_phi_hasher >  vn_phi_table_type 
typedef vn_phi_table_type::iterator  vn_phi_iterator_type 
typedef hash_table < vn_reference_hasher >  vn_reference_table_type 
typedef vn_reference_table_type::iterator  vn_reference_iterator_type 
typedef struct vn_tables_s *  vn_tables_t 
Variables  
static hash_table < vn_constant_hasher >  constant_to_value_id 
static bitmap  constant_value_ids 
static vn_tables_t  valid_info 
static vn_tables_t  optimistic_info 
static vn_tables_t  current_info 
static int *  rpo_numbers 
tree  VN_TOP 
static unsigned int  next_value_id 
static unsigned int  next_dfs_num 
static vec< tree >  sccstack 
static vec< vn_ssa_aux_t >  vn_ssa_aux_table 
static struct obstack  vn_ssa_aux_obstack 
static vec< vn_reference_op_s >  shared_lookup_references 
static tree *  last_vuse_ptr 
static vn_lookup_kind  vn_walk_kind 
static vn_lookup_kind  default_vn_walk_kind 
static vec< tree >  shared_lookup_phiargs 
typedef vn_nary_op_table_type::iterator vn_nary_op_iterator_type 
typedef vn_phi_table_type::iterator vn_phi_iterator_type 
typedef hash_table<vn_phi_hasher> vn_phi_table_type 
typedef vn_reference_table_type::iterator vn_reference_iterator_type 
typedef struct vn_tables_s * vn_tables_t 
The set of hashtables and alloc_pool's for their items.

static 
Allocate and initialize a vn_nary_op_t on CURRENT_INFO's obstack.

static 
Allocate a vn_nary_op_t with LENGTH operands on STACK.

static 
Allocate a value number table.
References OEP_PURE_SAME, and operand_equal_p().
bool ao_ref_init_from_vn_reference  (  ao_ref *  ref, 
alias_set_type  set,  
tree  type,  
vec< vn_reference_op_s >  ops  
) 
Build a aliasoracle reference abstraction in *REF from the vn_reference operands in *OPS, the reference alias set SET and the reference type TYPE. Return true if something useful was produced.
First get the final access size from just the outermost expression.
Initially, maxsize is the same as the accessed element size. In the following it will only grow (or become 1).
Compute cumulative bitoffset for nested componentrefs and arrayrefs, and find the ultimate containing object.
These may be in the reference ops, but we cannot do anything sensible with them here.
Apart from ADDR_EXPR arguments to MEM_REF.
Fallthru.
Record the base objects.
And now the usual componentreference style ops.
We do not have a complete COMPONENT_REF tree here so we cannot use component_ref_field_offset. Do the interesting parts manually.
We recorded the lower bound and the element size.
We discount volatiles from valuenumbering elsewhere.

static 
Compare two operands by reverse postorder index

static 

static 
Insert the no longer used phi OPHI to the hash INFO.

static 
Insert the no longer used reference OREF to the hash INFO.
References hash_table< Descriptor, Allocator >::create(), create_alloc_pool(), vn_tables_s::nary, vn_tables_s::nary_obstack, vn_tables_s::phis, vn_tables_s::phis_pool, vn_tables_s::references, and vn_tables_s::references_pool.
void copy_reference_ops_from_call  (  gimple  call, 
vec< vn_reference_op_s > *  result  
) 
Copy the operations present in load/store/call REF into RESULT, a vector of vn_reference_op_s's.
If 2 calls have a different nonssa lhs, vdef value numbers should be different. By adding the lhs here in the vector, we ensure that the hashcode is different, guaranteeing a different value number.
Copy the type, opcode, function being called and static chain.
Copy the call arguments. As they can be references as well, just chain them together.
Referenced by insert_aux().
void copy_reference_ops_from_ref  (  ) 
Copy the operations present in load/store REF into RESULT, a vector of vn_reference_op_s's.
For noncalls, store the information that makes up the address.
The base address gets its own vn_reference_op_s structure.
Record bits and position.
The field decl is enough to unambiguously specify the field, a matching type is not necessary and a mismatching type is always a spurious difference.
Record index as operand.
Always record lower bounds and element size.
Fallthru.
Canonicalize decls to MEM[&decl] which is what we end up with when valueizing MEM[ptr] with ptr = &decl.
Fallthrough.
These are only interesting for their operands, their existence, and their type. They will never be the last ref in the chain of references (IE they require an operand), so we don't have to put anything for op* as it will be handled by the iteration
This is only interesting for its constant offset.

static 
Create a vector of vn_reference_op_s structures from CALL, a call statement. The vector is not shared.

static 
Set all definitions in STMT to value number to themselves. Return true if a value number changed.

static 
Depth first search on NAME to discover and process SCC's in the SSA graph. Execution of this algorithm relies on the fact that the SCC's are popped off the stack in topological order. Returns true if successful, false if we stopped processing SCC's due to resource constraints.
SCC info
Recursively DFS on our operands, looking for SCC's.
Push a new iterator.
If we are done processing uses of a name, go up the stack of iterators and process SCCs as we found them.
See if we found an SCC.
Check if we are done.
Restore the last use walker and continue walking there.
Since we handle phi nodes, we will sometimes get invariants in the use expression.
Recurse by pushing the current use walking state on the stack and starting over.
References current_function_decl, dump_file, dump_flags, free_scc_vn(), get_next_value_id(), get_or_alloc_constant_value_id(), has_zero_uses(), init_scc_vn(), is_gimple_min_invariant(), print_generic_expr(), set_hashtable_value_ids(), ssa_default_def(), valid_info, vn_ssa_aux::valnum, vn_ssa_aux::value_id, visited, and VN_INFO().

static 
Referenced by simplify_binary_expression().

static 
Return true if EXPR contains constants.
Constants inside reference ops are rarely interesting, but it can take a lot of looking to find them.
References gimple_assign_rhs1().
bool expressions_equal_p  (  ) 
Compare two expressions E1 and E2 and return true if they are equal.
The obvious case.
If only one of them is null, they cannot be equal.
Now perform the actual comparison.
Referenced by vn_nary_op_lookup(), and vn_reference_compute_hash().

static 
Pop the components of the found SCC for NAME off the SCC stack and process them. Returns true if all went well, false if we run into resource limits.
Found an SCC, pop the components off the SCC stack and process them.
Bail out of SCCVN in case a SCC turns out to be incredibly large.
References release_ssa_name(), and VN_INFO().

inlinestatic 
Free a reference operation structure VP.
void free_scc_vn  (  void  ) 
Referenced by DFS().

static 
Free a value number table.
tree fully_constant_vn_reference_p  (  ) 
Optimize the reference REF to a constant if possible or return NULL_TREE if not.
Try to simplify the translated expression if it is a call to a builtin function with at most two arguments.
Simplify reads from constant strings.
unsigned int get_constant_value_id  (  ) 
Lookup a value id for CONSTANT and return it. If it does not exist returns 0.
References bitmap_bit_p().
unsigned int get_max_value_id  (  void  ) 
Return the maximum value id we have ever seen.
unsigned int get_next_value_id  (  void  ) 
Return the next unique value id.
Referenced by create_component_ref_by_pieces(), and DFS().
unsigned int get_or_alloc_constant_value_id  (  ) 
Lookup a value id for CONSTANT, and if it does not exist, create a new one and return it. If it does exist, return it.
References HOST_WIDE_INT, vn_reference_op_struct::off, vn_reference_op_struct::opcode, and vn_reference_s::operands.
Referenced by DFS().

static 
VEC_alloc doesn't actually grow it to the right size, it just preallocates the space to do so.
RPO numbers is an array of rpo ordering, rpo[i] = bb means that the i'th block in RPO order is bb. We want to map bb's to RPO numbers, so we need to rearrange this array.
Create the VN_INFO structures, and initialize value numbers to TOP.
Create the valid and optimistic value numbering tables.
References vn_nary_op_s::type.
Referenced by DFS().

static 
Initialize VNO from OP.
References sizeof_vn_nary_op().

static 
Initialize VNO from the pieces provided.
References init_vn_nary_op_from_stmt(), sizeof_vn_nary_op(), vn_nary_length_from_stmt(), and vn_nary_op_lookup_1().
Referenced by vn_nary_op_eq().

static 
Initialize VNO from STMT.
Referenced by init_vn_nary_op_from_pieces().

static 
Mark as processed all the definitions in the defining stmt of USE, or the USE itself.

static 
Print set of components in strongly connected component SCC to OUT.

static 
Process a strongly connected component in the SSA graph.
If the SCC has a single member, just visit it.
We need to make sure it doesn't form a cycle itself, which can happen for selfreferential PHI nodes. In that case we would end up inserting an expression with VN_TOP operands into the valid table which makes us derive bogus equivalences later. The cheapest way to check this is to assume it for all PHI nodes.
Fallthru to iteration.
Iterate over the SCC with the optimistic table until it stops changing.
As we are valuenumbering optimistically we have to clear the expression tables and the simplified expressions in each iteration until we converge.
Finally, copy the contents of the no longer used optimistic table to the valid table.
References hash_table< Descriptor, Allocator >::dispose(), free_alloc_pool(), vn_tables_s::nary, vn_tables_s::nary_obstack, vn_tables_s::phis, vn_tables_s::phis_pool, vn_tables_s::references, and vn_tables_s::references_pool.
bool run_scc_vn  (  ) 
Do SCCVN. Returns true if it finished, false if we bailed out due to resource constraints. DEFAULT_VN_WALK_KIND_ specifies how we use the alias oracle walking during the VN process.
Initialize the value ids.
Propagate.

static 
Set the value ids in the valid hash tables.
Now set the value ids of the things we had put in the hash table.
Referenced by DFS().

inlinestatic 
Set the value number of FROM to TO, return true if it has changed as a result.
The only thing we allow as value numbers are VN_TOP, ssa_names and invariants. So assert that here.
??? For addresses involving volatile objects or types operand_equal_p does not reliably detect ADDR_EXPRs as equal. We know we are only getting invariant gimple addresses here, so can use get_addr_base_and_unit_offset to do this comparison.
Referenced by simplify_binary_expression(), visit_nary_op(), and visit_reference_op_load().

static 
Set *ID according to RESULT.

static 
Simplify the binary expression RHS, and return the result if simplified.
This will not catch every single case we could combine, but will catch those with constants. The goal here is to simultaneously combine constants between expressions, but avoid infinite expansion of expressions during simplification.
Pointer plus constant can be represented as invariant address. Do so to allow further propatation, see also tree forwprop.
Avoid folding if nothing changed.
Make sure result is not a complex expression consisting of operators of operators (IE (a + b) + (a + c)) Otherwise, we will end up with unbounded expressions if fold does anything at all.
References dump_file, dump_flags, vn_ssa_aux::expr, expr_has_constants(), gimple_assign_lhs(), gimple_assign_rhs1(), gimple_assign_rhs_code(), vn_ssa_aux::has_constants, is_gimple_min_invariant(), print_generic_expr(), print_gimple_expr(), set_ssa_val_to(), stmt_has_constants(), try_to_simplify(), unshare_expr(), visit_copy(), and VN_INFO().

static 
Simplify the unary expression RHS, and return the result if simplified.
We handle some tcc_reference codes here that are all GIMPLE_ASSIGN_SINGLE codes.
We want to do treecombining on conversionlike expressions. Make sure we feed only SSA_NAMEs or constants to fold though.
Avoid folding if nothing changed, but remember the expression.

static 
Sort an array containing members of a strongly connected component SCC so that the members are ordered by RPO number. This means that when the sort is complete, iterating through the array will give you the members in RPO order.

static 
Return true if STMT contains constants.
Fallthru.
Fallthru.
Constants inside reference ops are rarely interesting, but it can take a lot of looking to find them.
Referenced by simplify_binary_expression().

static 
Try to simplify RHS using equivalences and constant folding.
For stores we can end up simplifying a SSA_NAME rhs. Just return in this case, there is no point in doing extra work.
First try constant folding based on our current lattice.
If that didn't work try combining multiple statements.
Fallthrough for some unary codes that can operate on registers.
We could do a little more with unary ops, if they expand into binary ops, but it's debatable whether it is worth it.
Referenced by simplify_binary_expression().
bool value_id_constant_p  (  ) 
Return true if V is a value id for a constant.
References iterative_hash_hashval_t(), vn_reference_op_struct::op0, and vn_reference_op_struct::opcode.
Referenced by bitmap_set_and(), bitmap_set_contains_expr(), and bitmap_set_new().

static 
Replace SSA_NAMES in expr with their value numbers, and return the result. This is performed in place.
Fallthru.

static 

static 
Transform any SSA_NAME's in a vector of vn_reference_op_s structures into their value numbers. This is done inplace, and the vector passed in is returned. *VALUEIZED_ANYTHING will specify whether any operands were valueized.
If it transforms from an SSA_NAME to a constant, update the opcode.
If it transforms from an SSA_NAME to an address, fold with a preceding indirect reference.
If it transforms a nonconstant ARRAY_REF into a constant one, adjust the constant offset.

static 
Create a vector of vn_reference_op_s structures from CALL, a call statement. The vector is shared among all callers of this function.

static 
Create a vector of vn_reference_op_s structures from REF, a REFERENCE_CLASS_P tree. The vector is shared among all callers of this function. *VALUEIZED_ANYTHING will specify whether any operands were valueized.
References vn_reference_s::operands, vn_reference_s::result, vn_reference_s::value_id, and vn_reference_s::vuse.

static 
Visit a copy between LHS and RHS, return true if the value number changed.
The copy may have a more interesting constant filled expression (we don't, since we know our RHS is just an SSA name).
And finally valueize.
References dump_file, and print_generic_expr().
Referenced by simplify_binary_expression().

static 
Visit a nary operator RHS, value number it, and return true if the value number of LHS has changed as a result.
References set_ssa_val_to(), and vn_reference_insert().

static 
Visit and value number PHI, return true if the value number changed.
TODO: We could check for this in init_sccvn, and replace this with a gcc_assert.
See if all nonTOP arguments have the same value. TOP is equivalent to everything, so we can ignore it.
If all value numbered to the same value, the phi node has that value.
Otherwise, see if it is equivalent to a phi node in this block.

static 
Visit a call STMT storing into LHS. Return true if the value number of the LHS has changed as a result.
Nonssa lhs is handled in copy_reference_ops_from_call.

static 
Visit a load from a reference operator RHS, part of STMT, value number it, and return true if the value number of the LHS has changed as a result.
If we have a VCE, try looking up its operand as it might be stored in a different type.
We handle typepunning through unions by valuenumbering based on offset and size of the access. Be prepared to handle a typemismatch here via creating a VIEW_CONVERT_EXPR.
We will be setting the value number of lhs to the value number of VIEW_CONVERT_EXPR <TREE_TYPE (result)> (result). So first simplify and lookup this expression to see if it is already available.
If the expression is not yet available, valuenumber lhs to a new SSA_NAME we create.
Initialize valuenumber information properly.
As all "inserted" statements are singleton SCCs, insert to the valid table. This is strictly needed to avoid regenerating new value SSA_NAMEs for the same expression during SCC iteration over and over (the optimistic table gets cleared after each iteration). We do not need to insert into the optimistic table, as lookups there will fall back to the valid table.
References dump_file, dump_flags, and set_ssa_val_to().

static 
Visit a store to a reference operator LHS, part of STMT, value number it, and return true if the value number of the LHS has changed as a result.
First we want to lookup using the *vuses* from the store and see if there the last store to this location with the same address had the same value. The vuses represent the memory state before the store. If the memory state, address, and value of the store is the same as the last store to this location, then this store will produce the same memory state as that store. In this case the vdef versions for this store are value numbered to those vuse versions, since they represent the same memory state after this store. Otherwise, the vdefs for the store are used when inserting into the table, since the store generates a new memory state.
Have to set value numbers before insert, since insert is going to valueize the references inplace.
Do not insert structure copies into the tables.
We had a match, so value number the vdef to have the value number of the vuse it came from.

static 
Visit and value number USE, return true if the value number changed.
Handle uninitialized uses.
Shortcut for copies. Simplifying copies is pointless, since we copy the expression and value they represent.
Setting value numbers to constants will occasionally screw up phi congruence because constants are not uniquely associated with a single ssa name that can be looked up.
We have to unshare the expression or else valuizing may change the IL stream.
We reset expr and constantness here because we may have been value numbering optimistically, and iterating. They may become nonconstant in this case, even if they were optimistically constant.
We can substitute SSA_NAMEs that are live over abnormal edges with their constant value.
Stores or copies from SSA_NAMEs that are live over abnormal edges are a problem.
First try to lookup the simplified expression.
Otherwise visit the original statement.
??? We could try to simplify calls.
We reset expr and constantness here because we may have been value numbering optimistically, and iterating. They may become nonconstant in this case, even if they were optimistically constant.
If calls have a vdef, subsequent calls won't have the same incoming vuse. So, if 2 calls with vdef have the same vuse, we know they're not subsequent. We can value number 2 calls to the same function with the same vuse and the same operands which are not subsequent the same, because there is no code in the program that can compare the 2 values...
... unless the call returns a pointer which does not alias with anything else. In which case the information that the values are distinct are encoded in the IL.
tree vn_get_expr_for  (  ) 
Get the representative expression for the SSA_NAME NAME. Returns the representative SSA_NAME if there is no expression associated with it.
If the valuenumber is a constant it is the representative expression.
Get to the information of the value of this SSA_NAME.
If the valuenumber is a constant it is the representative expression.
Else if we have an expression, return it.
Otherwise use the defining statement to build the expression.
If the value number is not an assignment use it directly.
FIXME tuples. This is incomplete and likely will miss some simplifications.
Cache the expression.
enum vn_kind vn_get_stmt_kind  (  ) 
Return the vn_kind the expression computed by the stmt should be associated with.
VOPless references can go through unary case.
Fallthrough.
vn_ssa_aux_t VN_INFO  (  ) 
Return the value numbering information for a given SSA name.
Referenced by bitmap_find_leader(), copy_nary(), create_component_ref_by_pieces(), DFS(), extract_and_process_scc_for_name(), get_expr_type(), phi_translate_1(), simplify_binary_expression(), vn_nary_op_insert_into(), and vn_phi_eq().
vn_ssa_aux_t VN_INFO_GET  (  ) 
Initialize the value numbering info for a given SSA name. This should be called just once for every SSA name.
Referenced by create_component_ref_by_pieces().

inlinestatic 
Set the value numbering info for a given SSA name to a given value.

static 
Return the number of operands for a vn_nary ops structure from STMT.
Referenced by init_vn_nary_op_from_pieces().
bool vn_nary_may_trap  (  ) 
Return true if the nary operation NARY may trap. This is a copy of stmt_could_throw_1_p adjusted to the SCCVN IL.
hashval_t vn_nary_op_compute_hash  (  ) 
Compute and return the hash value for nary operation VBO1.
References hash_table< Descriptor, Allocator >::find_slot_with_hash(), vn_nary_op_s::hashcode, vn_tables_s::nary, and vn_nary_op_s::result.
bool vn_nary_op_eq  (  ) 
Compare nary operations VNO1 and VNO2 and return true if they are equivalent.
References init_vn_nary_op_from_pieces(), sizeof_vn_nary_op(), and vn_nary_op_lookup_1().
Referenced by vn_nary_op_hasher::hash().
vn_nary_op_t vn_nary_op_insert  (  ) 
Insert OP into the current hash table with a value number of RESULT. Return the vn_nary_op_t structure we created and put in the hashtable.

static 
Insert VNO into TABLE. If COMPUTE_HASH is true, then compute VNO>HASHCODE first.
References vn_phi_s::block, gimple_bb(), gimple_phi_num_args(), gimple_phi_result(), vn_phi_s::hashcode, vn_phi_s::phiargs, vn_tables_s::phis_pool, pool_alloc(), vn_phi_s::result, vn_phi_s::type, vn_phi_s::value_id, vn_ssa_aux::value_id, VN_INFO(), vn_phi_compute_hash(), and vNULL.
vn_nary_op_t vn_nary_op_insert_pieces  (  unsigned int  length, 
enum tree_code  code,  
tree  type,  
tree *  ops,  
tree  result,  
unsigned int  value_id  
) 
Insert a nary operation into the current hash table using it's pieces. Return the vn_nary_op_t structure we created and put in the hashtable.
vn_nary_op_t vn_nary_op_insert_stmt  (  ) 
Insert the rhs of STMT into the current hash table with a value number of RESULT.
References dump_file, and dump_flags.
tree vn_nary_op_lookup  (  ) 
Lookup OP in the current hash table, and return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table or if the result field of the operation is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable if it exists.
References expressions_equal_p(), and vn_phi_s::phiargs.

static 
Compute the hashcode for VNO and look for it in the hash table; return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table or if the result field of the operation is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable if it exists.
Referenced by init_vn_nary_op_from_pieces(), and vn_nary_op_eq().
tree vn_nary_op_lookup_pieces  (  unsigned int  length, 
enum tree_code  code,  
tree  type,  
tree *  ops,  
vn_nary_op_t *  vnresult  
) 
Lookup a nary operation by its pieces and return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table or if the result field of the operation is NULL. VNRESULT will contain the vn_nary_op_t from the hashtable if it exists.
tree vn_nary_op_lookup_stmt  (  ) 
Lookup the rhs of STMT in the current hash table, and return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table. VNRESULT will contain the vn_nary_op_t from the hashtable if it exists.

inlinestatic 
Compute a hashcode for PHI operation VP1 and return it.
If all PHI arguments are constants we need to distinguish the PHI node via its type.
Referenced by vn_nary_op_insert_into().

static 
vn_phi hashtable helpers.
Referenced by vn_phi_hasher::hash().

static 
Compare two phi entries for equality, ignoring VN_TOP arguments.
If the PHI nodes do not have compatible types they are not the same.
Any phi in the same block will have it's arguments in the same edge order, because of how we store phi nodes.
References dump_file, dump_flags, vn_ssa_aux::valnum, and VN_INFO().

static 
Insert PHI into the current hash table with a value number of RESULT.
Canonicalize the SSA_NAME's to their value number.
Because we iterate over phi operations more than once, it's possible the slot might already exist here, hence no assert.

static 
Lookup PHI in the current hash table, and return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table.
Canonicalize the SSA_NAME's to their value number.
hashval_t vn_reference_compute_hash  (  ) 
Compute a hash for the reference operation VR1 and return it.
References expressions_equal_p(), vn_reference_s::hashcode, HOST_WIDE_INT, vn_reference_s::operands, vn_reference_s::type, and vn_reference_s::vuse.
bool vn_reference_eq  (  ) 
Return true if reference operations VR1 and VR2 are equivalent. This means they have the same set of operands and vuses.
Early out if this is not a hash collision.
The VOP needs to be the same.
If the operands are the same we are done.
void vn_reference_fold_indirect  (  vec< vn_reference_op_s > *  ops, 
unsigned int *  i_p  
) 
Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates *I_P to point to the last element of the replacement.
The only thing we have to do is from &OBJ.foo.bar add the offset from .foo.bar to the preceding MEM_REF offset and replace the address with &OBJ.
vn_reference_t vn_reference_insert  (  ) 
Insert OP into the current hash table with a value number of RESULT, and return the resulting reference structure we created.
Because we lookup stores using vuses, and value number failures using the vdefs (see visit_reference_op_store for how and why), it's possible that on failure we may try to insert an already inserted store. This is not wrong, there is no ssa name for a store that we could use as a differentiator anyway. Thus, unlike the other lookup functions, you cannot gcc_assert (!*slot) here.
But free the old slot in case of a collision.
Referenced by visit_nary_op().
vn_reference_t vn_reference_insert_pieces  (  tree  vuse, 
alias_set_type  set,  
tree  type,  
vec< vn_reference_op_s >  operands,  
tree  result,  
unsigned int  value_id  
) 
Insert a reference by it's pieces into the current hash table with a value number of RESULT. Return the resulting reference structure we created.
At this point we should have all the things inserted that we have seen before, and we should never try inserting something that already exists.
tree vn_reference_lookup  (  tree  op, 
tree  vuse,  
vn_lookup_kind  kind,  
vn_reference_t *  vnresult  
) 
Lookup OP in the current hash table, and return the resulting value number if it exists in the hash table. Return NULL_TREE if it does not exist in the hash table or if the result field of the structure was NULL.. VNRESULT will be filled in with the vn_reference_t stored in the hashtable if one exists.
Make sure to use a valueized reference if we valueized anything. Otherwise preserve the full reference for advanced TBAA.
References commutative_tree_code(), iterative_hash_expr(), iterative_hash_hashval_t(), vn_nary_op_s::length, vn_nary_op_s::op, and tree_swap_operands_p().

static 
Lookup a SCCVN reference operation VR in the current hash table. Returns the resulting value number if it exists in the hash table, NULL_TREE otherwise. VNRESULT will be filled in with the actual vn_reference_t stored in the hashtable if something is found.
References gimple_assign_lhs(), HOST_WIDE_INT, is_gimple_assign(), offset, and vNULL.
Callback for walk_non_aliased_vuses. Adjusts the vn_reference_t VR_ with the current VUSE and performs the expression lookup.
This bounds the stmt walks we perform on reference lookups to O(1) instead of O(N) where N is the number of dominating stores.
Fixup vuse and hash.

static 
Callback for walk_non_aliased_vuses. Tries to perform a lookup from the statement defining VUSE and if not successful tries to translate *REFP and VR_ through an aggregate copy at the definition of VUSE.
First try to disambiguate after valuereplacing in the definitions LHS.
Avoid reallocation overhead.
If we cannot constrain the size of the reference we cannot test if anything kills it.
We can't deduce anything useful from clobbers.
def_stmt maydefs *ref. See if we can derive a value for *ref from that definition. 1) Memset.
2) Assignment from an empty CONSTRUCTOR.
3) Assignment from a constant. We can use folds native encode/interpret routines to extract the assigned bits.
We support up to 512bit values (for V8DFmode).
4) Assignment from an SSA name which definition we may be able to access pieces from.
5) For aggregate copies translate the reference through them if the copy kills ref.
See if the assignment kills REF.
Find the common base of ref and the lhs. lhs_ops already contains valueized operands for the lhs.
??? The innermost op should always be a MEM_REF and we already checked that the assignment to the lhs kills vr. Thus for aggregate copies using char[] types the vn_reference_op_eq may fail when comparing types for compatibility. But we really don't care here  further lookups with the rewritten operands will simply fail if we messed up types too badly.
i now points to the first additional op. ??? LHS may not be completely contained in VR, one or more VIEW_CONVERT_EXPRs could be in its way. We could at least try handling outermost VIEW_CONVERT_EXPRs.
Now rewrite REF to be based on the rhs of the assignment.
We need to prepend vr>operands[0..i] to rhs.
Adjust *ref from the new operands.
This can happen with bitfields.
Do not update last seen VUSE after translating.
Keep looking for the adjusted *REF / VR pair.
6) For memcpy copies translate the reference through them if the copy kills ref.
??? Handle BCOPY as well.
Only handle nonvariable, addressable refs.
Extract a pointer base and an offset for the destination.
Extract a pointer base and an offset for the source.
The bases of the destination and the references have to agree.
And the access has to be contained within the memcpy destination.
Make room for 2 operands in the new reference.
The lookedthrough reference is a simple MEM_REF.
Adjust *ref from the new operands.
This can happen with bitfields.
Do not update last seen VUSE after translating.
Keep looking for the adjusted *REF / VR pair.
Bail out and stop walking.
References buffer, get_ref_base_and_extent(), gimple_assign_lhs(), gimple_assign_rhs1(), len, native_encode_expr(), native_interpret_expr(), operand_equal_p(), vn_reference_s::operands, vn_reference_s::set, ao_ref_s::size, vn_reference_s::type, and vn_reference_lookup_or_insert_for_pieces().

static 
Lookup an existing or insert a new vn_reference entry into the value table for the VUSE, SET, TYPE, OPERANDS reference which has the value VALUE which is either a constant or an SSA name.
References build_zero_cst(), vn_reference_s::operands, vn_reference_s::set, and vn_reference_s::type.
Referenced by vn_reference_lookup_3().
tree vn_reference_lookup_pieces  (  tree  vuse, 
alias_set_type  set,  
tree  type,  
vec< vn_reference_op_s >  operands,  
vn_reference_t *  vnresult,  
vn_lookup_kind  kind  
) 
Lookup a reference operation by it's parts, in the current hash table. Returns the resulting value number if it exists in the hash table, NULL_TREE otherwise. VNRESULT will be filled in with the actual vn_reference_t stored in the hashtable if something is found.
Referenced by insert_aux().

static 
Fold *& at position *I_P in a vn_reference_op_s vector *OPS. Updates *I_P to point to the last element of the replacement.
The only thing we have to do is from &OBJ.foo.bar add the offset from .foo.bar to the preceding MEM_REF offset and replace the address with &OBJ.
And recurse.
References build_call_expr(), is_gimple_min_invariant(), vn_reference_op_struct::op0, vn_reference_op_struct::opcode, and tcc_constant.

static 
Compute the hash for a reference operand VRO1.
References iterative_hash_expr(), iterative_hash_hashval_t(), and vn_reference_op_struct::op0.

static 
Compare two reference operands P1 and P2 for equality. Return true if they are equal, and false otherwise.
We do not care for differences in type qualification.

static 

static 

static 
Pointer to the set of hashtables that is currently being used. Should always point to either the optimistic_info, or the valid_info.

static 

static 

static 
Next DFS number and the stack for strongly connected component detection.

static 
Unique counter for our value ids.

static 
Optimistic hashtables storing information we are making assumptions about during iterations.

static 
Reverse post order index for each basic block.

static 

static 
Valid hashtables storing information we have proven to be correct.
Referenced by DFS().

static 

static 
Table of vn_ssa_aux_t's, one per ssa_name. The vn_ssa_aux_t objects are allocated on an obstack for locality reasons, and to free them without looping over the vec.
tree VN_TOP 
This represents the top of the VN lattice, which is the universal value.

static 