Data Structures
struct	btr_def_group_s
struct	btr_user_s
struct	btr_def_s
struct	defs_uses_info

Typedefs
typedef struct btr_def_group_s *	btr_def_group
typedef struct btr_user_s *	btr_user
typedef struct btr_def_s *	btr_def

Functions
static int	basic_block_freq (const_basic_block)
static int	insn_sets_btr_p (const_rtx, int, int *)
static rtx *	find_btr_use (rtx)
static int	btr_referenced_p (rtx, rtx *)
static int	find_btr_reference (rtx , void )
static void	find_btr_def_group (btr_def_group *, btr_def)
static btr_def	add_btr_def (fibheap_t, basic_block, int, rtx, unsigned int, int, btr_def_group *)
static btr_user	new_btr_user (basic_block, int, rtx)
static void	dump_hard_reg_set (HARD_REG_SET)
static void	dump_btrs_live (int)
static void	note_other_use_this_block (unsigned int, btr_user)
static void	compute_defs_uses_and_gen (fibheap_t, btr_def , btr_user , sbitmap , sbitmap , HARD_REG_SET *)
static void	compute_kill (sbitmap , sbitmap , HARD_REG_SET *)
static void	compute_out (sbitmap bb_out, sbitmap , sbitmap *, int)
static void	link_btr_uses (btr_def , btr_user , sbitmap , sbitmap , int)
static void	build_btr_def_use_webs (fibheap_t)
static int	block_at_edge_of_live_range_p (int, btr_def)
static void	clear_btr_from_live_range (btr_def def)
static void	add_btr_to_live_range (btr_def, int)
static void	augment_live_range (bitmap, HARD_REG_SET *, basic_block, basic_block, int)
static int	choose_btr (HARD_REG_SET)
static void	combine_btr_defs (btr_def, HARD_REG_SET *)
static void	btr_def_live_range (btr_def, HARD_REG_SET *)
static void	move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *)
static int	migrate_btr_def (btr_def, int)
static void	migrate_btr_defs (enum reg_class, int)
static int	can_move_up (const_basic_block, const_rtx, int)
static void	note_btr_set (rtx, const_rtx, void *)
static int	basic_block_freq ()
static int	find_btr_reference ()
static int	btr_referenced_p ()
static int	insn_sets_btr_p ()
static rtx *	find_btr_use ()
static void	find_btr_def_group ()
static btr_user	new_btr_user ()
static void	dump_hard_reg_set ()
static void	dump_btrs_live ()
static void	note_other_use_this_block ()
static void	note_btr_set ()
static void	compute_out ()
static void	build_btr_def_use_webs ()
static int	block_at_edge_of_live_range_p ()
static void	clear_btr_from_live_range ()
static void	add_btr_to_live_range ()
static int	choose_btr ()
static void	btr_def_live_range ()
static void	combine_btr_defs ()
static int	can_move_up ()
static int	migrate_btr_def ()
static void	migrate_btr_defs ()
static void	branch_target_load_optimize ()
static bool	gate_handle_branch_target_load_optimize1 ()
static unsigned int	rest_of_handle_branch_target_load_optimize1 ()
rtl_opt_pass *	make_pass_branch_target_load_optimize1 ()
static bool	gate_handle_branch_target_load_optimize2 ()
static unsigned int	rest_of_handle_branch_target_load_optimize2 ()
rtl_opt_pass *	make_pass_branch_target_load_optimize2 ()

Variables
static int	issue_rate
static struct obstack	migrate_btrl_obstack
static HARD_REG_SET *	btrs_live
static HARD_REG_SET *	btrs_live_at_end
static HARD_REG_SET	all_btrs
static int	first_btr
static int	last_btr
static rtx *	btr_reference_found

Typedef Documentation

typedef struct btr_def_s * btr_def

   btr_def structs appear on three lists:
     1. A list of all btr_def structures (head is
        ALL_BTR_DEFS, linked by the NEXT field).
     2. A list of branch reg definitions per basic block (head is
        BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
     3. A list of all branch reg definitions belonging to the same
        group (head is in a BTR_DEF_GROUP struct, linked by
        NEXT_THIS_GROUP field).

typedef struct btr_def_group_s * btr_def_group

@verbatim

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

   Target register optimizations - these are performed after reload.

typedef struct btr_user_s * btr_user

Function Documentation

static btr_def add_btr_def	(	fibheap_t	all_btr_defs,
		basic_block	bb,
		int	insn_luid,
		rtx	insn,
		unsigned int	dest_reg,
		int	other_btr_uses_before_def,
		btr_def_group *	all_btr_def_groups
	)

static

   Create a new target register definition structure, for a definition in
   block BB, instruction INSN, and insert it into ALL_BTR_DEFS.  Return
   the new definition.

static void add_btr_to_live_range	(	btr_def	,
		int
	)

static

static void add_btr_to_live_range ( )

static

   We are adding the def/use web DEF.  Add the target register used
   in this web to the live set of all of the basic blocks that contain
   the live range of the web.
   If OWN_END is set, also show that the register is live from our
   definitions at the end of the basic block where it is defined.

static void augment_live_range	(	bitmap	live_range,
		HARD_REG_SET *	btrs_live_in_range,
		basic_block	head_bb,
		basic_block	new_bb,
		int	full_range
	)

static

   Update a live range to contain the basic block NEW_BLOCK, and all
   blocks on paths between the existing live range and NEW_BLOCK.
   HEAD is a block contained in the existing live range that dominates
   all other blocks in the existing live range.
   Also add to the set BTRS_LIVE_IN_RANGE all target registers that
   are live in the blocks that we add to the live range.
   If FULL_RANGE is set, include the full live range of NEW_BB;
   otherwise, if NEW_BB dominates HEAD_BB, only add registers that
   are life at the end of NEW_BB for NEW_BB itself.
   It is a precondition that either NEW_BLOCK dominates HEAD,or
   HEAD dom NEW_BLOCK.  This is used to speed up the
   implementation of this function.

         A previous btr migration could have caused a register to be
        live just at the end of new_block which we need in full, so
        use trs_live_at_end even if full_range is set.

             A previous btr migration could have caused a register to be
             live just at the end of a block which we need in full.

Referenced by btr_def_live_range(), and migrate_btr_def().

static int basic_block_freq ( const_basic_block )

static

Referenced by migrate_btr_def().

static int basic_block_freq ( )

static

   Return an estimate of the frequency of execution of block bb.

static int block_at_edge_of_live_range_p	(	int	,
		btr_def
	)

static

static int block_at_edge_of_live_range_p ( )

static

   Return true if basic block BB contains the start or end of the
   live range of the definition DEF, AND there are other live
   ranges of the same target register that include BB.

static void branch_target_load_optimize ( )

static

         Initialize issue_rate.

             Build the CFG for migrate_btr_defs.

             This may or may not be needed, depending on where we
             run this phase.

         Dominator info is also needed for migrate_btr_def.

References gate_handle_branch_target_load_optimize1().

static void btr_def_live_range	(	btr_def	,
		HARD_REG_SET *
	)

static

Referenced by btr_def_live_range().

static void btr_def_live_range ( )

static

   Calculate the set of basic blocks that contain the live range of
   the def/use web DEF.
   Also calculate the set of target registers that are live at time
   in this live range, but ignore the live range represented by DEF
   when calculating this set.

         def->live_range is accurate, but we need to recompute
         the set of target registers live over it, because migration
         of other PT instructions may have affected it.

References augment_live_range(), btr_user_s::bb, btr_def_s::bb, bitmap_copy(), btr_def_s::btr, btr_def_live_range(), CDI_DOMINATORS, choose_btr(), dominated_by_p(), dump_file, btr_def_s::has_ambiguous_use, btr_user_s::insn, btr_def_s::insn, btr_def_s::live_range, btr_user_s::next, and btr_def_s::uses.

static int btr_referenced_p	(	rtx	,
		rtx *
	)

static

static int btr_referenced_p ( )

static

   Return nonzero if X references (sets or reads) any branch target register.
   If EXCLUDEP is set, disregard any references within the rtx pointed to
   by it.  If returning nonzero, also set btr_reference_found as above.

static void build_btr_def_use_webs ( fibheap_t )

static

static void build_btr_def_use_webs ( )

static

References btr_user_s::bb, btr_user_s::next, and btr_def_s::uses.

static int can_move_up	(	const_basic_block	,
		const_rtx	,
		int
	)

static

static int can_move_up ( )

static

   We anticipate intra-block scheduling to be done.  See if INSN could move
   up within BB by N_INSNS.

         ??? What if we have an anti-dependency that actually prevents the
         scheduler from doing the move?  We'd like to re-allocate the register,
         but not necessarily put the load into another basic block.

static int choose_btr ( HARD_REG_SET )

static

Referenced by btr_def_live_range(), and migrate_btr_def().

static int choose_btr ( )

static

    Return the most desirable target register that is not in
    the set USED_BTRS.

static void clear_btr_from_live_range ( btr_def def )

static

static void clear_btr_from_live_range ( )

static

   We are removing the def/use web DEF.  The target register
   used in this web is therefore no longer live in the live range
   of this web, so remove it from the live set of all basic blocks
   in the live range of the web.
   Blocks at the boundary of the live range may contain other live
   ranges for the same target register, so we have to be careful
   to remove the target register from the live set of these blocks
   only if they do not contain other live ranges for the same register.

static void combine_btr_defs	(	btr_def	,
		HARD_REG_SET *
	)

static

static void combine_btr_defs ( )

static

   Merge into the def/use web DEF any other def/use webs in the same
   group that are dominated by DEF, provided that there is a target
   register available to allocate to the merged web.

             def->bb dominates the other def, so def and other_def could
             be combined.

             Merge their live ranges, and get the set of
             target registers live over the merged range.

                 We can combine them.

                 Combining def/use webs can make target registers live
                 after uses where they previously were not.  This means
                 some REG_DEAD notes may no longer be correct.  We could
                 be more precise about this if we looked at the combined
                 live range, but here I just delete any REG_DEAD notes
                 in case they are no longer correct.

                 Delete the old target register initialization.

static void compute_defs_uses_and_gen	(	fibheap_t	all_btr_defs,
		btr_def *	def_array,
		btr_user *	use_array,
		sbitmap *	btr_defset,
		sbitmap *	bb_gen,
		HARD_REG_SET *	btrs_written
	)

static

     Scan the code building up the set of all defs and all uses.
     For each target register, build the set of defs of that register.
     For each block, calculate the set of target registers
     written in that block.
     Also calculate the set of btrs ever live in that block.

                 Check for the blockage emitted by expand_nl_goto_receiver.

                     Do the equivalent of calling note_other_use_this_block
                     for every target register.

                         Check for sibcall.

         If this block ends in a jump insn, add any uses or even clobbers
         of branch target registers that it might have.

         ??? for the fall-through edge, it would make sense to insert the
         btr set on the edge, but that would require to split the block
         early on so that we can distinguish between dominance from the fall
         through edge - which can use the call-clobbered registers - from
         dominance by the throw edge.

static void compute_kill	(	sbitmap *	bb_kill,
		sbitmap *	btr_defset,
		HARD_REG_SET *	btrs_written
	)

static

     For each basic block, form the set BB_KILL - the set
     of definitions that the block kills.

References bitmap_ior_and_compl(), and bitmap_union_of_preds().

static void compute_out	(	sbitmap *	bb_out,
		sbitmap *	,
		sbitmap *	,
		int
	)

static

static void compute_out ( )

static

     Perform iterative dataflow:
      Initially, for all blocks, BB_OUT = BB_GEN.
      For each block,
        BB_IN  = union over predecessors of BB_OUT(pred)
        BB_OUT = (BB_IN - BB_KILL) + BB_GEN
     Iterate until the bb_out sets stop growing.

References bitmap_and_compl(), bitmap_set_bit(), bitmap_union_of_preds(), btr_def_s::btr, first_btr, and last.

static void dump_btrs_live ( int )

static

static void dump_btrs_live ( )

static

   Write the set of target regs live in block BB to the dump file.

static void dump_hard_reg_set ( HARD_REG_SET )

static

Referenced by migrate_btr_def().

static void dump_hard_reg_set ( )

static

   Write the contents of S to the dump file.

static void find_btr_def_group	(	btr_def_group *	,
		btr_def
	)

static

static void find_btr_def_group ( )

static

   Find the group that the target register definition DEF belongs
   to in the list starting with *ALL_BTR_DEF_GROUPS.  If no such
   group exists, create one.  Add def to the group.

         ?? This linear search is an efficiency concern, particularly
         as the search will almost always fail to find a match.

static int find_btr_reference	(	rtx *	,
		void *
	)

static

Referenced by find_btr_reference().

static int find_btr_reference ( )

static

   A subroutine of btr_referenced_p, called through for_each_rtx.
   PREG is a pointer to an rtx that is to be excluded from the
   traversal.  If we find a reference to a target register anywhere
   else, return 1, and put a pointer to it into btr_reference_found.

References find_btr_reference(), and for_each_rtx().

static rtx* find_btr_use ( rtx )

static

static rtx* find_btr_use ( )

static

   Find and return a use of a target register within an instruction INSN.

References btr_def_group_s::members, migrate_btrl_obstack, and btr_def_group_s::src.

static bool gate_handle_branch_target_load_optimize1 ( )

static

Referenced by branch_target_load_optimize().

static bool gate_handle_branch_target_load_optimize2 ( )

static

static int insn_sets_btr_p	(	const_rtx	,
		int	,
		int *
	)

static

static int insn_sets_btr_p ( )

static

   Return true if insn is an instruction that sets a target register.
   if CHECK_CONST is true, only return true if the source is constant.
   If such a set is found and REGNO is nonzero, assign the register number
   of the destination register to *REGNO.

static void link_btr_uses	(	btr_def *	def_array,
		btr_user *	use_array,
		sbitmap *	bb_out,
		sbitmap *	btr_defset,
		int	max_uid
	)

static

     Link uses to the uses lists of all of their reaching defs.
     Count up the number of reaching defs of each use.

                     Remove all reaching defs of regno except
                     for this one.

                     Find all the reaching defs for this use.

                         We now know that def reaches user.

rtl_opt_pass* make_pass_branch_target_load_optimize1 ( )

rtl_opt_pass* make_pass_branch_target_load_optimize2 ( )

static int migrate_btr_def	(	btr_def	,
		int
	)

static

static int migrate_btr_def ( )

static

   Attempt to migrate the target register definition DEF to an
   earlier point in the flowgraph.

   It is a precondition of this function that DEF is migratable:
   i.e. it has a constant source, and all uses are unambiguous.

   Only migrations that reduce the cost of DEF will be made.
   MIN_COST is the lower bound on the cost of the DEF after migration.
   If we migrate DEF so that its cost falls below MIN_COST,
   then we do not attempt to migrate further.  The idea is that
   we migrate definitions in a priority order based on their cost,
   when the cost of this definition falls below MIN_COST, then
   there is another definition with cost == MIN_COST which now
   has a higher priority than this definition.

   Return nonzero if there may be benefit from attempting to
   migrate this DEF further (i.e. we have reduced the cost below
   MIN_COST, but we may be able to reduce it further).
   Return zero if no further migration is possible.

       These defs are not migratable.

       We have combined this def with another in the same group, so
       no need to consider it further.

         Try to move the instruction that sets the target register into
         basic block ATTEMPT.

         If ATTEMPT has abnormal edges, skip it.

                 There are no free target registers available to move
                 this far forward, so give up

References augment_live_range(), basic_block_freq(), btr_def_s::bb, bitmap_copy(), choose_btr(), dump_hard_reg_set(), btr_def_s::live_range, and move_btr_def().

static void migrate_btr_defs	(	enum	reg_class,
		int
	)

static

static void migrate_btr_defs ( )

static

   Attempt to move instructions that set target registers earlier
   in the flowgraph, away from their corresponding uses.

References cleanup_cfg().

static void move_btr_def	(	basic_block	new_def_bb,
		int	btr,
		btr_def	def,
		bitmap	live_range,
		HARD_REG_SET *	btrs_live_in_range
	)

static

   Move the definition DEF from its current position to basic
   block NEW_DEF_BB, and modify it to use branch target register BTR.
   Delete the old defining insn, and insert a new one in NEW_DEF_BB.
   Update all reaching uses of DEF in the RTL to use BTR.
   If this new position means that other defs in the
   same group can be combined with DEF then combine them.

     We can move the instruction.
     Set a target register in block NEW_DEF_BB to the value
     needed for this target register definition.
     Replace all uses of the old target register definition by
     uses of the new definition.  Delete the old definition.

     N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now.  Some
     optimizations can result in insp being both first and last insn of
     its basic block.

     ?? some assertions to check that insp is sensible?

     Insert target register initialization at head of basic block.

     Delete the old target register initialization.

     Replace each use of the old target register by a use of the new target
     register.

         Some extra work here to ensure consistent modes, because
         it seems that a target register REG rtx can be given a different
         mode depending on the context (surely that should not be
         the case?).

Referenced by migrate_btr_def().

static btr_user new_btr_user	(	basic_block	,
		int	,
		rtx
	)

static

static btr_user new_btr_user ( )

static

   Create a new target register user structure, for a use in block BB,
   instruction INSN.  Return the new user.

     This instruction reads target registers.  We need
     to decide whether we can replace all target register
     uses easily.

         We want to ensure that USE is the only use of a target
         register in INSN, so that we know that to rewrite INSN to use
         a different target register, all we have to do is replace USE.

References dump_file, basic_block_def::index, and btr_user_s::use.

static void note_btr_set	(	rtx	,
		const_rtx	,
		void *
	)

static

static void note_btr_set ( )

static

   Called via note_stores or directly to register stores into /
   clobbers of a branch target register DEST that are not recognized as
   straightforward definitions.  DATA points to information about the
   current basic block that needs updating.

static void note_other_use_this_block	(	unsigned	int,
		btr_user
	)

static

static void note_other_use_this_block ( )

static

   REGNO is the number of a branch target register that is being used or
   set.  USERS_THIS_BB is a list of preceding branch target register users;
   If any of them use the same register, set their other_use_this_block
   flag.

static unsigned int rest_of_handle_branch_target_load_optimize1 ( )

static

References RTL_PASS, and TV_NONE.

static unsigned int rest_of_handle_branch_target_load_optimize2 ( )

static

     Leave this a warning for now so that it is possible to experiment
     with running this pass twice.  In 3.6, we should either make this
     an error, or use separate dump files.

Variable Documentation

HARD_REG_SET all_btrs

static

   Set of all target registers that we are willing to allocate.

rtx* btr_reference_found

static

HARD_REG_SET* btrs_live

static

   Array indexed by basic block number, giving the set of registers
   live in that block.

HARD_REG_SET* btrs_live_at_end

static

   Array indexed by basic block number, giving the set of registers live at
  the end of that block, including any uses by a final jump insn, if any.

int first_btr

static

   Provide lower and upper bounds for target register numbers, so that
   we don't need to search through all the hard registers all the time.

Referenced by compute_out().

int issue_rate

static

Referenced by compute_av_set_on_boundaries(), loop_canon_p(), ok_for_early_queue_removal(), and remove_node_from_ps().

int last_btr

static

struct obstack migrate_btrl_obstack

static

   The following code performs code motion of target load instructions
   (instructions that set branch target registers), to move them
   forward away from the branch instructions and out of loops (or,
   more generally, from a more frequently executed place to a less
   frequently executed place).
   Moving target load instructions further in front of the branch
   instruction that uses the target register value means that the hardware
   has a better chance of preloading the instructions at the branch
   target by the time the branch is reached.  This avoids bubbles
   when a taken branch needs to flush out the pipeline.
   Moving target load instructions out of loops means they are executed
   less frequently.

   An obstack to hold the def-use web data structures built up for
   migrating branch target load instructions.

Referenced by find_btr_use().

Data Structures

Typedefs

Functions

Variables

Typedef Documentation

Function Documentation

Variable Documentation