Data Structures
struct	occr
struct	expr
struct	hash_table_d

Typedefs
typedef struct occr *	occr_t

Functions
static void *	cprop_alloc ()
static int	reg_available_p ()
static unsigned int	hash_set ()
static void	insert_set_in_table (rtx dest, rtx src, rtx insn, struct hash_table_d *table, bool implicit)
static bool	cprop_constant_p ()
static void	hash_scan_set ()
static void	hash_scan_insn ()
static void	dump_hash_table ()
static void	make_set_regs_unavailable ()
static void	compute_hash_table_work ()
static void	alloc_hash_table ()
static void	free_hash_table ()
static void	compute_hash_table ()
static struct expr *	lookup_set ()
static struct expr *	next_set ()
static void	reset_opr_set_tables ()
static int	reg_not_set_p ()
static void	mark_oprs_set ()
static void	alloc_cprop_mem ()
static void	free_cprop_mem ()
static void	compute_local_properties (sbitmap kill, sbitmap comp, struct hash_table_d *table)
static void	compute_cprop_data ()
static void	find_used_regs ()
static int	try_replace_reg ()
static struct expr *	find_avail_set ()
static int	cprop_jump ()
static int	constprop_register ()
static int	cprop_insn ()
static void	local_cprop_find_used_regs ()
static bool	do_local_cprop ()
static int	local_cprop_pass ()
rtx	fis_get_condition ()
static bool	implicit_set_cond_p ()
static bool	find_implicit_sets ()
static struct expr *	find_bypass_set ()
static bool	reg_killed_on_edge ()
static int	bypass_block ()
static int	bypass_conditional_jumps ()
static bool	is_too_expensive ()
static int	one_cprop_pass ()
static bool	gate_rtl_cprop ()
static unsigned int	execute_rtl_cprop ()
rtl_opt_pass *	make_pass_rtl_cprop ()

Variables
static struct obstack	cprop_obstack
static struct hash_table_d	set_hash_table
static rtx *	implicit_sets
static int *	implicit_set_indexes
static regset	reg_set_bitmap
static int	bytes_used
static int	local_const_prop_count
static int	local_copy_prop_count
static int	global_const_prop_count
static int	global_copy_prop_count
static sbitmap *	cprop_avloc
static sbitmap *	cprop_kill
static sbitmap *	cprop_avin
static sbitmap *	cprop_avout
static rtx	reg_use_table [MAX_USES]
static unsigned	reg_use_count
static int	bypass_last_basic_block

Typedef Documentation

typedef struct occr* occr_t

Function Documentation

static void alloc_cprop_mem ( )

static

Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
   basic blocks.  N_SETS is the number of sets.

References sbitmap_vector_alloc().

Referenced by one_cprop_pass().

static void alloc_hash_table ( )

static

Allocate space for the set/expr hash TABLE.
   It is used to determine the number of buckets to use.

References get_max_insn_count(), hash_table_d::size, and hash_table_d::table.

Referenced by one_cprop_pass().

static int bypass_block ( )

static

Subroutine of bypass_conditional_jumps that attempts to bypass the given
   basic block BB which has more than one predecessor.  If not NULL, SETCC
   is the first instruction of BB, which is immediately followed by JUMP_INSN
   JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
   Returns nonzero if a change was made.

   During the jump bypassing pass, we may place copies of SETCC instructions
   on CFG edges.  The following routine must be careful to pay attention to
   these inserted insns when performing its transformations.

References bypass_last_basic_block, copy_insn(), edge_def::dest, expr::dest, dump_file, ei_next(), ei_safe_edge(), find_bypass_set(), find_edge(), find_reg_equal_equiv_note(), find_used_regs(), edge_def::flags, loop::header, basic_block_def::index, insert_insn_on_edge(), edge_def::insns, basic_block_def::loop_father, note_uses(), pc_rtx, pc_set(), basic_block_def::preds, print_rtl(), edge_def::edge_def_insns::r, redirect_edge_and_branch_force(), reg_killed_on_edge(), reg_use_count, reg_use_table, simplify_replace_rtx(), edge_def::src, expr::src, and set::src.

Referenced by bypass_conditional_jumps().

static int bypass_conditional_jumps ( )

static

Find basic blocks with more than one predecessor that only contain a
   single conditional jump.  If the result of the comparison is known at
   compile-time from any incoming edge, redirect that edge to the
   appropriate target.  Return nonzero if a change was made.

   This function is now mis-named, because we also handle indirect jumps.

References any_condjump_p(), bypass_block(), bypass_last_basic_block, changed, commit_edge_insertions(), computed_jump_p(), expr::dest, mark_dfs_back_edges(), basic_block_def::next_bb, onlyjump_p(), SET, and single_pred_p().

Referenced by one_cprop_pass().

static void compute_cprop_data ( )

static

Hash table support.

Top level routine to do the dataflow analysis needed by copy/const
   propagation.

References bitmap_set_bit(), compute_available(), compute_local_properties(), implicit_set_indexes, basic_block_def::index, and set_hash_table.

Referenced by one_cprop_pass().

static void compute_hash_table ( void )

static

Compute the hash TABLE for doing copy/const propagation or
   expression hash table.

References compute_hash_table_work(), memset(), hash_table_d::n_elems, hash_table_d::size, and hash_table_d::table.

Referenced by one_cprop_pass().

static void compute_hash_table_work ( )

static

Top level function to create an assignment hash table.

   Assignment entries are placed in the hash table if
   - they are of the form (set (pseudo-reg) src),
   - src is something we want to perform const/copy propagation on,
   - none of the operands or target are subsequently modified in the block

   Currently src must be a pseudo-reg or a const_int.

   TABLE is the table computed.

References hash_scan_insn(), hash_scan_set(), implicit_sets, basic_block_def::index, df_insn_info::insn, and make_set_regs_unavailable().

Referenced by compute_hash_table().

static void compute_local_properties	(	sbitmap *	kill,
		sbitmap *	comp,
		struct hash_table_d *	table
	)

static

Compute the local properties of each recorded expression.

   Local properties are those that are defined by the block, irrespective of
   other blocks.

   An expression is killed in a block if its operands, either DEST or SRC, are
   modified in the block.

   An expression is computed (locally available) in a block if it is computed
   at least once and expression would contain the same value if the
   computation was moved to the end of the block.

   KILL and COMP are destination sbitmaps for recording local properties.

References expr::avail_occr, expr::bitmap_index, bitmap_set_bit(), bitmap_vector_clear(), expr::dest, expr::expr, occr::insn, occr::next, expr::next_same_hash, hash_table_d::size, expr::src, and hash_table_d::table.

Referenced by compute_cprop_data().

static int constprop_register ( )

static

Subroutine of cprop_insn that tries to propagate constants.  FROM is what
   we will try to replace, SRC is the constant we will try to substitute for
   it and INSN is the instruction where this will be happening.

References any_condjump_p(), cprop_jump(), expr::dest, onlyjump_p(), and try_replace_reg().

Referenced by cprop_insn(), and do_local_cprop().

static void* cprop_alloc ( )

static

Cover function to obstack_alloc.

References bytes_used, cprop_obstack, and hash_table_d::size.

static bool cprop_constant_p ( )

static

Determine whether the rtx X should be treated as a constant for CPROP.
   Since X might be inserted more than once we have to take care that it
   is sharable.

References shared_const_p().

Referenced by cprop_insn(), do_local_cprop(), find_avail_set(), find_bypass_set(), hash_scan_set(), and implicit_set_cond_p().

static int cprop_insn ( )

static

Perform constant and copy propagation on INSN.
   Return nonzero if a change was made.

References changed, constprop_register(), cprop_constant_p(), dump_file, find_avail_set(), find_reg_equal_equiv_note(), find_used_regs(), global_const_prop_count, global_copy_prop_count, note_uses(), print_rtl(), reg_not_set_p(), reg_use_count, reg_use_table, expr::src, and try_replace_reg().

Referenced by one_cprop_pass().

static int cprop_jump ( )

static

Subroutine of cprop_insn that tries to propagate constants into
   JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
   it is the instruction that immediately precedes JUMP, and must be a
   single SET of a register.  FROM is what we will try to replace,
   SRC is the constant we will try to substitute for it.  Return nonzero
   if a change was made.

References copy_rtx(), delete_insn(), edge_def::dest, dump_file, find_reg_equal_equiv_note(), edge_def::flags, global_const_prop_count, modified_between_p(), modified_in_p(), pc_rtx, pc_set(), print_rtl(), purge_dead_edges(), remove_note(), rtx_equal_p(), set_unique_reg_note(), simplejump_p(), simplify_replace_rtx(), basic_block_def::succs, and validate_unshare_change().

Referenced by constprop_register().

static bool do_local_cprop ( )

static

Try to perform local const/copy propagation on X in INSN.

References asm_noperands(), constprop_register(), cprop_constant_p(), cselib_lookup(), dump_file, find_reg_note(), elt_loc_list::loc, local_const_prop_count, local_copy_prop_count, cselib_val_struct::locs, elt_loc_list::next, print_rtl(), elt_loc_list::setting_insn, and try_replace_reg().

Referenced by local_cprop_pass().

static void dump_hash_table ( )

static

Dump the hash table TABLE to file FILE under the name NAME.

References expr::bitmap_index, expr::dest, expr::expr, free(), hash_table_d::n_elems, expr::next_same_hash, print_rtl(), hash_table_d::size, expr::src, and hash_table_d::table.

Referenced by gcse_after_reload_main(), and one_cprop_pass().

static unsigned int execute_rtl_cprop ( )

static

References changed, cleanup_cfg(), delete_unreachable_blocks(), df_analyze(), DF_LR_RUN_DCE, df_set_flags(), flag_rerun_cse_after_global_opts, and one_cprop_pass().

static struct expr* find_avail_set ( )

staticread

Find a set of REGNOs that are available on entry to INSN's block.  Return
   NULL no such set is found.

References bitmap_bit_p(), cprop_constant_p(), lookup_set(), next_set(), reg_not_set_p(), set_hash_table, and expr::src.

Referenced by cprop_insn().

static struct expr* find_bypass_set ( )

staticread

Find a set of REGNO to a constant that is available at the end of basic
   block BB.  Return NULL if no such set is found.  Based heavily upon
   find_avail_set.

References bitmap_bit_p(), cprop_constant_p(), lookup_set(), next_set(), set_hash_table, and expr::src.

Referenced by bypass_block().

static bool find_implicit_sets ( )

static

Find the implicit sets of a function.  An "implicit set" is a constraint
   on the value of a variable, implied by a conditional jump.  For example,
   following "if (x == 2)", the then branch may be optimized as though the
   conditional performed an "explicit set", in this example, "x = 2".  This
   function records the set patterns that are implicit at the start of each
   basic block.

   If an implicit set is found but the set is implicit on a critical edge,
   this critical edge is split.

   Return true if the CFG was modified, false otherwise.

References count, dump_file, find_edge(), fis_get_condition(), implicit_set_cond_p(), implicit_sets, basic_block_def::index, memset(), single_pred_p(), split_edge(), and basic_block_def::succs.

Referenced by one_cprop_pass().

static void find_used_regs ( )

static

Set up a list of register numbers used in INSN.  The found uses are stored
   in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
   and contains the number of uses in the table upon exit.

   ??? If a register appears multiple times we will record it multiple times.
   This doesn't hurt anything but it will slow things down.

References reg_use_count, and reg_use_table.

Referenced by bypass_block(), cprop_insn(), and local_cprop_find_used_regs().

rtx fis_get_condition ( )

Similar to get_condition, only the resulting condition must be
   valid at JUMP, instead of at EARLIEST.

   This differs from noce_get_condition in ifcvt.c in that we prefer not to
   settle for the condition variable in the jump instruction being integral.
   We prefer to be able to record the value of a user variable, rather than
   the value of a temporary used in a condition.  This could be solved by
   recording the value of *every* register scanned by canonicalize_condition,
   but this would require some code reorganization.

References get_condition().

Referenced by find_implicit_sets(), and reload_cse_move2add().

static void free_cprop_mem ( )

static

Free vars used by copy/const propagation.

References sbitmap_vector_free().

Referenced by one_cprop_pass().

static void free_hash_table ( )

static

Free things allocated by alloc_hash_table.

References free(), and hash_table_d::table.

Referenced by one_cprop_pass().

static bool gate_rtl_cprop ( )

static

All the passes implemented in this file.  Each pass has its
   own gate and execute function, and at the end of the file a
   pass definition for passes.c.

   We do not construct an accurate cfg in functions which call
   setjmp, so none of these passes runs if the function calls
   setjmp.
   FIXME: Should just handle setjmp via REG_SETJMP notes.

References function::calls_setjmp, cfun, and dbg_cnt().

static void hash_scan_insn ( )

static

Process INSN and add hash table entries as appropriate.

References hash_scan_set(), and SET.

Referenced by compute_hash_table_work().

static void hash_scan_set ( )

static

Scan SET present in INSN and add an entry to the hash TABLE.
   IMPLICIT is true if it's an implicit set, false otherwise.

References can_copy_p(), cprop_constant_p(), find_reg_equal_equiv_note(), insert_set_in_table(), and reg_available_p().

Referenced by compute_hash_table(), compute_hash_table_work(), and hash_scan_insn().

static unsigned int hash_set ( )

static

Hash a set of register REGNO.

   Sets are hashed on the register that is set.  This simplifies the PRE copy
   propagation code.

   ??? May need to make things more elaborate.  Later, as necessary.

Referenced by insert_set_in_table(), and lookup_set().

static bool implicit_set_cond_p ( )

static

Check the comparison COND to see if we can safely form an implicit
   set from it.

References cprop_constant_p(), and dconst0.

Referenced by find_implicit_sets().

static void insert_set_in_table	(	rtx	dest,
		rtx	src,
		rtx	insn,
		struct hash_table_d *	table,
		bool	implicit
	)

static

Insert assignment DEST:=SET from INSN in the hash table.
   DEST is a register and SET is a register or a suitable constant.
   If the assignment is already present in the table, record it as
   the last occurrence in INSN's basic block.
   IMPLICIT is true if it's an implicit set, false otherwise.

References expr::avail_occr, expr::bitmap_index, bytes_used, copy_rtx(), expr::dest, expr::hash, hash_set(), implicit_set_indexes, occr::insn, hash_table_d::n_elems, occr::next, expr::next_same_hash, hash_table_d::size, expr::src, and hash_table_d::table.

Referenced by hash_scan_set().

static bool is_too_expensive ( )

static

Return true if the graph is too expensive to optimize.  PASS is the
   optimization about to be performed.

References max_reg_num(), and warning().

Referenced by one_cprop_pass().

static void local_cprop_find_used_regs ( )

static

Like find_used_regs, but avoid recording uses that appear in
   input-output contexts such as zero_extract or pre_dec.  This
   restricts the cases we consider to those for which local cprop
   can legitimately make replacements.

References find_used_regs().

Referenced by local_cprop_pass().

static int local_cprop_pass ( )

static

Do local const/copy propagation (i.e. within each basic block).

References changed, cselib_clear_table(), cselib_finish(), cselib_init(), cselib_process_insn(), do_local_cprop(), find_reg_equal_equiv_note(), local_cprop_find_used_regs(), note_uses(), reg_use_count, and reg_use_table.

Referenced by one_cprop_pass().

static struct expr* lookup_set ( )

staticread

Expression tracking support.

Lookup REGNO in the set TABLE.  The result is a pointer to the
   table entry, or NULL if not found.

References expr::dest, expr::expr, expr::hash, hash_set(), expr::next_same_hash, hash_table_d::size, and hash_table_d::table.

Referenced by find_avail_set(), and find_bypass_set().

rtl_opt_pass* make_pass_rtl_cprop ( )

static void make_set_regs_unavailable ( )

static

Record as unavailable all registers that are DEF operands of INSN.

Referenced by compute_hash_table_work().

static void mark_oprs_set ( )

static

Record things set by INSN.
   This data is used by reg_not_set_p.

Referenced by one_cprop_pass().

static struct expr* next_set ( )

staticread

Return the next entry for REGNO in list EXPR.

References expr::dest, expr::expr, and expr::next_same_hash.

Referenced by find_avail_set(), and find_bypass_set().

static int one_cprop_pass ( )

static

Main function for the CPROP pass.

References alloc_cprop_mem(), alloc_hash_table(), bypass_conditional_jumps(), bytes_used, changed, compute_cprop_data(), compute_hash_table(), cprop_insn(), cprop_obstack, current_function_name(), delete_unreachable_blocks(), df_analyze(), dump_file, dump_hash_table(), find_implicit_sets(), free(), free_cprop_mem(), free_hash_table(), global_const_prop_count, global_copy_prop_count, implicit_set_indexes, implicit_sets, is_too_expensive(), local_const_prop_count, local_copy_prop_count, local_cprop_pass(), mark_oprs_set(), hash_table_d::n_elems, basic_block_def::next_bb, reset_opr_set_tables(), and set_hash_table.

Referenced by execute_rtl_cprop().

static int reg_available_p ( )

static

Return nonzero if register X is unchanged from INSN to the end
   of INSN's basic block.

Referenced by hash_scan_set().

static bool reg_killed_on_edge ( )

static

Subroutine of bypass_block that checks whether a pseudo is killed by
   any of the instructions inserted on an edge.  Jump bypassing places
   condition code setters on CFG edges using insert_insn_on_edge.  This
   function is required to check that our data flow analysis is still
   valid prior to commit_edge_insertions.

References edge_def::insns, edge_def::edge_def_insns::r, and reg_set_p().

Referenced by bypass_block(), and eliminate_partially_redundant_load().

static int reg_not_set_p ( )

static

Return nonzero if the register X has not been set yet [since the
   start of the basic block containing INSN].

Referenced by cprop_insn(), and find_avail_set().

static void reset_opr_set_tables ( void )

static

Reset tables used to keep track of what's still available [since the
   start of the block].

Referenced by one_cprop_pass().

static int try_replace_reg ( )

static

Try to replace all uses of FROM in INSN with TO.
   Return nonzero if successful.

References apply_change_group(), copy_rtx(), find_reg_equal_equiv_note(), num_changes_pending(), reg_mentioned_p(), remove_note(), rtx_equal_p(), set_unique_reg_note(), simplify_replace_rtx(), simplify_rtx(), validate_change(), and validate_replace_src_group().

Referenced by constprop_register(), cprop_insn(), and do_local_cprop().

Variable Documentation

int bypass_last_basic_block

static

Bypass conditional jumps.

The value of last_basic_block at the beginning of the jump_bypass
   pass.  The use of redirect_edge_and_branch_force may introduce new
   basic blocks, but the data flow analysis is only valid for basic
   block indices less than bypass_last_basic_block.

Referenced by bypass_block(), and bypass_conditional_jumps().

int bytes_used

static

Various variables for statistics gathering.

Memory used in a pass.
   This isn't intended to be absolutely precise.  Its intent is only
   to keep an eye on memory usage.

Referenced by cprop_alloc(), insert_set_in_table(), and one_cprop_pass().

sbitmap* cprop_avin

static

Global properties of assignments (computed from the local properties).

sbitmap* cprop_avloc

static

Compute copy/constant propagation working variables.

Local properties of assignments.

sbitmap* cprop_avout

static

sbitmap* cprop_kill

static

struct obstack cprop_obstack

static

@verbatim Global constant/copy propagation for RTL.

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

An obstack for our working variables.

Referenced by cprop_alloc(), and one_cprop_pass().

int global_const_prop_count

static

Number of global constants propagated.

Referenced by cprop_insn(), cprop_jump(), and one_cprop_pass().

int global_copy_prop_count

static

Number of global copies propagated.

Referenced by cprop_insn(), and one_cprop_pass().

int* implicit_set_indexes

static

Array of indexes of expressions for implicit set patterns indexed by basic
   block index.  In other words, implicit_set_indexes[i] is the bitmap_index
   of the expression whose RTX is implicit_sets[i].

Referenced by compute_cprop_data(), insert_set_in_table(), and one_cprop_pass().

rtx* implicit_sets

static

Array of implicit set patterns indexed by basic block index.

Referenced by compute_hash_table_work(), find_implicit_sets(), and one_cprop_pass().

int local_const_prop_count

static

Number of local constants propagated.

Referenced by do_local_cprop(), and one_cprop_pass().

int local_copy_prop_count

static

Number of local copies propagated.

Referenced by do_local_cprop(), and one_cprop_pass().

regset reg_set_bitmap

static

Bitmap containing one bit for each register in the program.
   Used when performing GCSE to track which registers have been set since
   the start or end of the basic block while traversing that block.

unsigned reg_use_count

static

Index into `reg_use_table' while building it.

Referenced by bypass_block(), cprop_insn(), find_used_regs(), and local_cprop_pass().

rtx reg_use_table[MAX_USES]

static

Table of uses (registers, both hard and pseudo) found in an insn.
   Allocated statically to avoid alloc/free complexity and overhead.

Referenced by bypass_block(), cprop_insn(), find_used_regs(), and local_cprop_pass().

struct hash_table_d set_hash_table

static

Copy propagation hash table.

Referenced by compute_cprop_data(), find_avail_set(), find_bypass_set(), and one_cprop_pass().

Data Structures

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation