#include "config.h"
#include "system.h"
#include "coretypes.h"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
#include "regs.h"
#include "fibheap.h"
#include "target.h"
#include "expr.h"
#include "flags.h"
#include "insn-attr.h"
#include "function.h"
#include "except.h"
#include "tm_p.h"
#include "diagnostic-core.h"
#include "tree-pass.h"
#include "recog.h"
#include "df.h"
#include "cfgloop.h"

Include dependency graph for bt-load.c:

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:

A list of all btr_def structures (head is ALL_BTR_DEFS, linked by the NEXT field).
A list of branch reg definitions per basic block (head is BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
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

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, BB_END, BITMAP_ALLOC, bitmap_copy(), btr_def_s::btr, btr_def_live_range(), CDI_DOMINATORS, choose_btr(), COPY_HARD_REG_SET, dominated_by_p(), dump_file, HARD_REG_SET, btr_def_s::has_ambiguous_use, btr_user_s::insn, btr_def_s::insn, INSN_UID, JUMP_P, btr_def_s::live_range, btr_user_s::next, NULL, 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 BASIC_BLOCK, btr_user_s::bb, btr_user_s::next, NULL, 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 BASIC_BLOCK, bitmap_ior_and_compl(), bitmap_union_of_preds(), last_basic_block, and NUM_FIXED_BLOCKS.

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 BASIC_BLOCK, BB_END, BB_HEAD, bitmap_and_compl(), bitmap_set_bit, bitmap_union_of_preds(), btr_def_s::btr, first_btr, INSN_P, INSN_UID, last, NEXT_INSN, and NULL.

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, NULL, 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.

References 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(), and CLEANUP_EXPENSIVE.

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, INSN_UID, REGNO, 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 OPTGROUP_NONE, 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

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