GCC Middle and Back End API Reference
bt-load.c File Reference

Data Structures

struct  btr_def_group_s
struct  btr_user_s
struct  btr_def_s
struct  defs_uses_info


typedef struct btr_def_group_sbtr_def_group
typedef struct btr_user_sbtr_user
typedef struct btr_def_sbtr_def


static int basic_block_freq (const_basic_block)
static int insn_sets_btr_p (const_rtx, int, int *)
static rtxfind_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 rtxfind_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_passmake_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_passmake_pass_branch_target_load_optimize2 ()


static int issue_rate
static struct obstack migrate_btrl_obstack
static HARD_REG_SETbtrs_live
static HARD_REG_SETbtrs_live_at_end
static HARD_REG_SET all_btrs
static int first_btr
static int last_btr
static rtxbtr_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

Perform branch target register load optimizations. Copyright (C) 2001-2013 Free Software Foundation, Inc.

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 
   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  ,
static void add_btr_to_live_range ( )
   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 
   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  )

Referenced by migrate_btr_def().

static int basic_block_freq ( )
   Return an estimate of the frequency of execution of block bb.  
static int block_at_edge_of_live_range_p ( int  ,
static int block_at_edge_of_live_range_p ( )
   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 ( )
         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  ,

Referenced by btr_def_live_range().

static void btr_def_live_range ( )
   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  ,
static int btr_referenced_p ( )
   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 void build_btr_def_use_webs ( )
static int can_move_up ( const_basic_block  ,
const_rtx  ,
static int can_move_up ( )
   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 int choose_btr ( )
    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 void clear_btr_from_live_range ( )
   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  ,
static void combine_btr_defs ( )
   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 
     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 
     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 ,
static void compute_out ( )
     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 void dump_btrs_live ( )
   Write the set of target regs live in block BB to the dump file.  
static void dump_hard_reg_set ( HARD_REG_SET  )

Referenced by migrate_btr_def().

static void dump_hard_reg_set ( )
   Write the contents of S to the dump file.  
static void find_btr_def_group ( btr_def_group ,
static void find_btr_def_group ( )
   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 *   

Referenced by find_btr_reference().

static int find_btr_reference ( )
   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 rtx* find_btr_use ( )
   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 bool gate_handle_branch_target_load_optimize2 ( )
static int insn_sets_btr_p ( const_rtx  ,
int  ,
int *   
static int insn_sets_btr_p ( )
   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 
     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  ,
static int migrate_btr_def ( )
   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,
static void migrate_btr_defs ( )
   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 
   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
         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  ,
static btr_user new_btr_user ( )
   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 void note_btr_set ( )
   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,
static void note_other_use_this_block ( )
   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
static unsigned int rest_of_handle_branch_target_load_optimize1 ( )

References RTL_PASS, and TV_NONE.

static unsigned int rest_of_handle_branch_target_load_optimize2 ( )
     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
   Set of all target registers that we are willing to allocate.  
rtx* btr_reference_found
HARD_REG_SET* btrs_live
   Array indexed by basic block number, giving the set of registers
   live in that block.  
HARD_REG_SET* btrs_live_at_end
   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
   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 last_btr
struct obstack migrate_btrl_obstack
   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().