Data Structures
struct	_elim_graph

Typedefs
typedef struct _elim_graph *	elim_graph

Functions
static void	set_location_for_edge ()
static rtx	emit_partition_copy ()
static void	insert_partition_copy_on_edge ()
static void	insert_value_copy_on_edge ()
static void	insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp, source_location locus)
static void	insert_part_to_rtx_on_edge ()
static elim_graph	new_elim_graph ()
static void	clear_elim_graph ()
static void	delete_elim_graph ()
static int	elim_graph_size ()
static void	elim_graph_add_node ()
static void	elim_graph_add_edge ()
static int	elim_graph_remove_succ_edge ()
static void	eliminate_name ()
static void	eliminate_build ()
static void	elim_forward ()
static int	elim_unvisited_predecessor ()
static void	elim_backward ()
static rtx	get_temp_reg ()
static void	elim_create ()
static void	eliminate_phi ()
static void	remove_gimple_phi_args ()
static void	eliminate_useless_phis ()
static void	rewrite_trees ()
void	expand_phi_nodes ()
static void	remove_ssa_form ()
static void	maybe_renumber_stmts_bb ()
static bool	trivially_conflicts_p ()
static void	insert_backedge_copies ()
void	finish_out_of_ssa ()
unsigned int	rewrite_out_of_ssa ()

Typedef Documentation

typedef struct _elim_graph * elim_graph

@verbatim Convert a program in SSA form into Normal form.

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/.

FIXME: A lot of code here deals with expanding to RTL.  All that code
   should be in cfgexpand.c.

Used to hold all the components required to do SSA PHI elimination.
   The node and pred/succ list is a simple linear list of nodes and
   edges represented as pairs of nodes.

   The predecessor and successor list:  Nodes are entered in pairs, where
   [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
   predecessors, all the odd elements are successors.

   Rationale:
   When implemented as bitmaps, very large programs SSA->Normal times were
   being dominated by clearing the interference graph.

   Typically this list of edges is extremely small since it only includes
   PHI results and uses from a single edge which have not coalesced with
   each other.  This means that no virtual PHI nodes are included, and
   empirical evidence suggests that the number of edges rarely exceed
   3, and in a bootstrap of GCC, the maximum size encountered was 7.
   This also limits the number of possible nodes that are involved to
   rarely more than 6, and in the bootstrap of gcc, the maximum number
   of nodes encountered was 12.

Function Documentation

static void clear_elim_graph ( )

inlinestatic

Empty elimination graph G.

References _elim_graph::edge_list, _elim_graph::edge_locus, and _elim_graph::nodes.

Referenced by eliminate_build().

static void delete_elim_graph ( )

inlinestatic

Delete elimination graph G.

References _elim_graph::const_copies, _elim_graph::const_dests, _elim_graph::copy_locus, _elim_graph::edge_list, _elim_graph::edge_locus, free(), _elim_graph::nodes, sbitmap_free(), _elim_graph::stack, and _elim_graph::visited.

Referenced by expand_phi_nodes().

static void elim_backward ( )

static

Process predecessors first, and insert a copy.

References bitmap_bit_p(), bitmap_set_bit(), _elim_graph::e, insert_partition_copy_on_edge(), and _elim_graph::visited.

Referenced by elim_create().

static void elim_create ( )

static

Insert required copies for T in graph G.  Check for a strongly connected
   region, and create a temporary to break the cycle if one is found.

References bitmap_bit_p(), _elim_graph::e, elim_backward(), elim_unvisited_predecessor(), get_temp_reg(), insert_part_to_rtx_on_edge(), insert_rtx_to_part_on_edge(), _elim_graph::map, partition_to_var(), and _elim_graph::visited.

Referenced by eliminate_phi().

static void elim_forward ( )

static

Push successors of T onto the elimination stack for G.

References bitmap_bit_p(), bitmap_set_bit(), _elim_graph::stack, and _elim_graph::visited.

Referenced by eliminate_phi().

static void elim_graph_add_edge ( )

inlinestatic

Add the edge PRED->SUCC to graph G.

References _elim_graph::edge_list, and _elim_graph::edge_locus.

Referenced by eliminate_build().

static void elim_graph_add_node ( )

inlinestatic

Add NODE to graph G, if it doesn't exist already.

References _elim_graph::nodes.

Referenced by eliminate_name().

static int elim_graph_remove_succ_edge ( )

inlinestatic

Remove an edge from graph G for which NODE is the predecessor, and
   return the successor node.  -1 is returned if there is no such edge.

References _elim_graph::edge_list, and _elim_graph::edge_locus.

static int elim_graph_size ( )

inlinestatic

Return the number of nodes in graph G.

References _elim_graph::nodes.

Referenced by eliminate_phi().

static int elim_unvisited_predecessor ( )

static

Return 1 if there unvisited predecessors of T in graph G.

References bitmap_bit_p(), and _elim_graph::visited.

Referenced by elim_create().

static void eliminate_build ( )

static

Build elimination graph G for basic block BB on incoming PHI edge
   G->e.

References clear_elim_graph(), _elim_graph::const_copies, _elim_graph::const_dests, _elim_graph::copy_locus, edge_def::dest, edge_def::dest_idx, _elim_graph::e, elim_graph_add_edge(), eliminate_name(), gimple_phi_arg_location_from_edge(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), _elim_graph::map, phi_ssa_name_p(), and var_to_partition().

Referenced by eliminate_phi().

static void eliminate_name ( )

inlinestatic

Add T to elimination graph G.

References elim_graph_add_node().

Referenced by eliminate_build().

static void eliminate_phi ( )

static

Eliminate all the phi nodes on edge E in graph G.

References bitmap_bit_p(), bitmap_clear(), _elim_graph::const_copies, _elim_graph::const_dests, _elim_graph::copy_locus, _elim_graph::e, elim_create(), elim_forward(), elim_graph_size(), eliminate_build(), edge_def::flags, insert_value_copy_on_edge(), _elim_graph::nodes, _elim_graph::stack, and _elim_graph::visited.

Referenced by expand_phi_nodes().

static void eliminate_useless_phis ( )

static

Remove any PHI node which is a virtual PHI, or a PHI with no uses.

References gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), has_zero_uses(), internal_error(), print_generic_expr(), print_gimple_stmt(), remove_gimple_phi_args(), remove_phi_node(), and virtual_operand_p().

Referenced by rewrite_out_of_ssa().

static rtx emit_partition_copy ( )

inlinestatic

Emit insns to copy SRC into DEST converting SRC if necessary.  As
   SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
   which we deduce the size to copy in that case.

References BLOCK_OP_NORMAL, convert_to_mode(), emit_block_move(), emit_move_insn(), end_sequence(), expr_size(), get_insns(), and start_sequence().

Referenced by insert_part_to_rtx_on_edge(), insert_partition_copy_on_edge(), and insert_rtx_to_part_on_edge().

void expand_phi_nodes ( )

Given the out-of-ssa info object SA (with prepared partitions)
   eliminate all phi nodes in all basic blocks.  Afterwards no
   basic block will have phi nodes anymore and there are possibly
   some RTL instructions inserted on edges.

References delete_elim_graph(), edge_def::dest, ei_next(), ei_safe_edge(), eliminate_phi(), edge_def::flags, g, gimple_seq_empty_p(), edge_def::insns, ssaexpand::map, _elim_graph::map, new_elim_graph(), basic_block_def::next_bb, _var_map::num_partitions, phi_nodes(), basic_block_def::preds, edge_def::edge_def_insns::r, set_phi_nodes(), single_pred_edge(), single_pred_p(), and split_edge().

void finish_out_of_ssa ( )

Free all memory associated with going out of SSA form.  SA is
   the outof-SSA info object.

References delete_var_map(), free(), ssaexpand::map, memset(), ssaexpand::partition_has_default_def, ssaexpand::partition_to_pseudo, and ssaexpand::values.

static rtx get_temp_reg ( )

static

Allocate a new pseudo register usable for storing values sitting
   in NAME (a decl or SSA name), i.e. with matching mode and attributes.

References gen_reg_rtx(), mark_reg_pointer(), promote_decl_mode(), and reg_mode.

Referenced by elim_create().

static void insert_backedge_copies ( )

static

Search every PHI node for arguments associated with backedges which
   we can trivially determine will need a copy (the argument is either
   not an SSA_NAME or the argument has a different underlying variable
   than the PHI result).

   Insert a copy from the PHI argument to a new destination at the
   end of the block with the backedge to the top of the loop.  Update
   the PHI argument to reference this new destination.

References basic_block_def::aux, copy_ssa_name(), edge_def::flags, gimple_phi_arg_def(), gimple_phi_arg_edge(), gimple_phi_arg_has_location(), gimple_phi_arg_location(), gimple_phi_num_args(), gimple_phi_result(), gimple_set_location(), gsi_end_p(), gsi_insert_after(), gsi_insert_before(), gsi_last_bb(), GSI_NEW_STMT, gsi_next(), gsi_start_phis(), gsi_stmt(), last, mark_dfs_back_edges(), stmt_ends_bb_p(), trivially_conflicts_p(), and virtual_operand_p().

Referenced by rewrite_out_of_ssa().

static void insert_part_to_rtx_on_edge ( )

static

Insert a copy instruction from partition SRC to RTL lvalue DEST
   onto edge E.

References edge_def::dest, dump_file, dump_flags, emit_partition_copy(), basic_block_def::index, insert_insn_on_edge(), ssaexpand::map, ssaexpand::partition_to_pseudo, partition_to_var(), print_simple_rtl(), SA, set_curr_insn_location(), set_location_for_edge(), and edge_def::src.

Referenced by elim_create().

static void insert_partition_copy_on_edge ( )

static

Insert a copy instruction from partition SRC to DEST onto edge E.

References edge_def::dest, dump_file, dump_flags, emit_partition_copy(), basic_block_def::index, insert_insn_on_edge(), ssaexpand::map, ssaexpand::partition_to_pseudo, partition_to_var(), SA, set_curr_insn_location(), set_location_for_edge(), and edge_def::src.

Referenced by elim_backward().

static void insert_rtx_to_part_on_edge	(	edge	e,
		int	dest,
		rtx	src,
		int	unsignedsrcp,
		source_location	locus
	)

static

Insert a copy instruction from RTL expression SRC to partition DEST
   onto edge E.

References edge_def::dest, dump_file, dump_flags, emit_partition_copy(), basic_block_def::index, insert_insn_on_edge(), ssaexpand::map, ssaexpand::partition_to_pseudo, partition_to_var(), print_simple_rtl(), SA, set_curr_insn_location(), set_location_for_edge(), and edge_def::src.

Referenced by elim_create().

static void insert_value_copy_on_edge ( )

static

Insert a copy instruction from expression SRC to partition DEST
   onto edge E.

References convert_modes(), edge_def::dest, dump_file, dump_flags, emit_move_insn(), end_sequence(), expand_expr(), EXPAND_NORMAL, get_insns(), basic_block_def::index, insert_insn_on_edge(), ssaexpand::map, ssaexpand::partition_to_pseudo, partition_to_var(), print_generic_expr(), promote_decl_mode(), SA, set_curr_insn_location(), set_location_for_edge(), edge_def::src, start_sequence(), and store_expr().

Referenced by eliminate_phi().

static void maybe_renumber_stmts_bb ( )

static

If not already done so for basic block BB, assign increasing uids
   to each of its instructions.

References basic_block_def::aux, gimple_set_uid(), gsi_end_p(), gsi_next(), gsi_start_bb(), and gsi_stmt().

Referenced by trivially_conflicts_p().

static elim_graph new_elim_graph ( )

static

Create an elimination graph with SIZE nodes and associated data
   structures.

References _elim_graph::const_copies, _elim_graph::const_dests, _elim_graph::copy_locus, _elim_graph::edge_list, _elim_graph::edge_locus, g, _elim_graph::nodes, sbitmap_alloc(), _elim_graph::stack, and _elim_graph::visited.

Referenced by expand_phi_nodes().

static void remove_gimple_phi_args ( )

static

Remove each argument from PHI.  If an arg was the last use of an SSA_NAME,
   check to see if this allows another PHI node to be removed.

References dump_file, dump_flags, gsi_for_stmt(), has_zero_uses(), print_gimple_stmt(), and remove_phi_node().

Referenced by eliminate_useless_phis().

static void remove_ssa_form ( )

static

Remove the ssa-names in the current function and translate them into normal
   compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
   should also be used.

References bitmap_set_bit(), coalesce_ssa_name(), dump_file, dump_flags, dump_replaceable_exprs(), dump_var_map(), find_replaceable_exprs(), ssaexpand::map, map, ssaexpand::partition_has_default_def, partition_view_normal(), rewrite_trees(), ssaexpand::values, and var_to_partition().

Referenced by rewrite_out_of_ssa().

unsigned int rewrite_out_of_ssa ( )

Take the current function out of SSA form, translating PHIs as described in
   R. Morgan, ``Building an Optimizing Compiler'',
   Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.

References dump_file, dump_flags, eliminate_useless_phis(), gimple_dump_cfg(), insert_backedge_copies(), and remove_ssa_form().

static void rewrite_trees ( )

static

This function will rewrite the current program using the variable mapping
   found in MAP.  If the replacement vector VALUES is provided, any
   occurrences of partitions with non-null entries in the vector will be
   replaced with the expression in the vector instead of its mapped
   variable.

References gimple_phi_num_args(), gimple_phi_result(), gsi_end_p(), gsi_next(), gsi_start_phis(), gsi_stmt(), internal_error(), map, print_generic_expr(), print_gimple_stmt(), var_to_partition(), and var_to_partition_to_var().

Referenced by remove_ssa_form().

static void set_location_for_edge ( )

static

For an edge E find out a good source location to associate with
   instructions inserted on edge E.  If E has an implicit goto set,
   use its location.  Otherwise search instructions in predecessors
   of E for a location, and use that one.  That makes sense because
   we insert on edges for PHI nodes, and effects of PHIs happen on
   the end of the predecessor conceptually.

References gimple_block(), gimple_has_location(), gimple_location(), edge_def::goto_locus, gsi_end_p(), gsi_last_bb(), gsi_prev(), gsi_stmt(), is_gimple_debug(), set_curr_insn_location(), single_pred(), single_pred_p(), and edge_def::src.

Referenced by insert_part_to_rtx_on_edge(), insert_partition_copy_on_edge(), insert_rtx_to_part_on_edge(), and insert_value_copy_on_edge().

static bool trivially_conflicts_p ( )

static

Return true if we can determine that the SSA_NAMEs RESULT (a result
   of a PHI node) and ARG (one of its arguments) conflict.  Return false
   otherwise, also when we simply aren't sure.

References gimple_uid(), is_gimple_debug(), and maybe_renumber_stmts_bb().

Referenced by insert_backedge_copies().

Data Structures

Typedefs

Functions

Typedef Documentation

Function Documentation