GCC Middle and Back End API Reference
lra-int.h File Reference

Go to the source code of this file.

Data Structures

struct  lra_live_range
struct  lra_copy
struct  lra_reg
struct  lra_operand_data
struct  lra_insn_reg
struct  lra_static_insn_data
struct  lra_insn_recog_data
struct  target_lra_int


typedef struct lra_live_rangelra_live_range_t
typedef struct lra_copylra_copy_t
typedef struct


static int lra_get_regno_hard_regno ()
void lra_push_insn (rtx)
void lra_push_insn_by_uid (unsigned int)
void lra_push_insn_and_update_insn_regno_info (rtx)
rtx lra_pop_insn (void)
unsigned int lra_insn_stack_length (void)
rtx lra_create_new_reg_with_unique_value (enum machine_mode, rtx, enum reg_class, const char *)
void lra_set_regno_unique_value (int)
void lra_invalidate_insn_data (rtx)
void lra_set_insn_deleted (rtx)
void lra_delete_dead_insn (rtx)
void lra_emit_add (rtx, rtx, rtx)
void lra_emit_move (rtx, rtx)
void lra_update_dups (lra_insn_recog_data_t, signed char *)
void lra_process_new_insns (rtx, rtx, rtx, const char *)
lra_insn_recog_data_t lra_set_insn_recog_data (rtx)
lra_insn_recog_data_t lra_update_insn_recog_data (rtx)
void lra_set_used_insn_alternative (rtx, int)
void lra_set_used_insn_alternative_by_uid (int, int)
void lra_invalidate_insn_regno_info (rtx)
void lra_update_insn_regno_info (rtx)
struct lra_insn_reglra_get_insn_regs (int)
void lra_free_copies (void)
void lra_create_copy (int, int, int)
lra_copy_t lra_get_copy (int)
bool lra_former_scratch_p (int)
bool lra_former_scratch_operand_p (rtx, int)
int lra_constraint_offset (int, enum machine_mode)
bool lra_constraints (bool)
void lra_constraints_init (void)
void lra_constraints_finish (void)
void lra_inheritance (void)
bool lra_undo_inheritance (void)
void lra_create_live_ranges (bool)
lra_live_range_t lra_copy_live_range_list (lra_live_range_t)
lra_live_range_t lra_merge_live_ranges (lra_live_range_t, lra_live_range_t)
bool lra_intersected_live_ranges_p (lra_live_range_t, lra_live_range_t)
void lra_print_live_range_list (FILE *, lra_live_range_t)
void debug (lra_live_range &ref)
void debug (lra_live_range *ptr)
void lra_debug_live_range_list (lra_live_range_t)
void lra_debug_pseudo_live_ranges (int)
void lra_debug_live_ranges (void)
void lra_clear_live_ranges (void)
void lra_live_ranges_init (void)
void lra_live_ranges_finish (void)
void lra_setup_reload_pseudo_preferenced_hard_reg (int, int, int)
void lra_setup_reg_renumber (int, int, bool)
bool lra_assign (void)
bool lra_coalesce (void)
bool lra_need_for_spills_p (void)
void lra_spill (void)
void lra_final_code_change (void)
void lra_debug_elim_table (void)
int lra_get_elimination_hard_regno (int)
rtx lra_eliminate_regs_1 (rtx, enum machine_mode, bool, bool, bool)
void lra_eliminate (bool)
void lra_eliminate_reg_if_possible (rtx *)
static void lra_update_dup ()
static void lra_update_operator_dups ()
static lra_insn_recog_data_t lra_get_insn_recog_data ()
static void lra_update_reg_val_offset ()
static bool lra_reg_val_equal_p ()
static void lra_assign_reg_val ()


struct lra_reglra_reg_info
FILE * lra_dump_file
bool lra_reg_spill_p
HARD_REG_SET lra_no_alloc_regs
int lra_insn_recog_data_len
int lra_curr_reload_num
int lra_new_regno_start
int lra_constraint_new_regno_start
bitmap_head lra_inheritance_pseudos
bitmap_head lra_split_regs
bitmap_head lra_subreg_reload_pseudos
bitmap_head lra_optional_reload_pseudos
int lra_constraint_new_insn_uid_start
int lra_constraint_iter
int lra_constraint_iter_after_spill
bool lra_risky_transformations_p
int lra_inheritance_iter
int lra_undo_inheritance_iter
int lra_live_max_point
int * lra_point_freq
int lra_hard_reg_usage [FIRST_PSEUDO_REGISTER]
int lra_live_range_iter
int lra_coalesce_iter
struct target_lra_int default_target_lra_int
struct target_lra_intthis_target_lra_int

Typedef Documentation

typedef struct lra_copy* lra_copy_t

Function Documentation

void debug ( lra_live_range ref)
void debug ( lra_live_range ptr)
bool lra_assign ( void  )
   Entry function to assign hard registers to new reload pseudos
   starting with LRA_CONSTRAINT_NEW_REGNO_START (by possible spilling
   of old pseudos) and possibly to the old pseudos.  The function adds
   what insns to process for the next constraint pass.  Those are all
   insns who contains non-reload and non-inheritance pseudos with
   changed allocation.

   Return true if we did not spill any non-reload and non-inheritance
     Setup insns to process on the next constraint pass.  
       We ignore spilled pseudos created on last inheritance pass
       because they will be removed.  
         Invalidate alternatives for insn should be processed.  
static void lra_assign_reg_val ( )
   Assign value of register FROM to TO.  

Referenced by match_reload().

void lra_clear_live_ranges ( void  )
   Finish all live ranges.  
bool lra_coalesce ( void  )
   The major function for aggressive pseudo coalescing of moves only
   if the both pseudos were spilled and not special reload pseudos.  
     Collect moves.  
     Coalesced copies, most frequently executed first.  
             We updated involved_insns_bitmap when doing the merge.  
                   Coalesced move.  
int lra_constraint_offset ( int  ,
enum  machine_mode 
bool lra_constraints ( bool  )
void lra_constraints_finish ( void  )
   Finalize the LRA constraint pass.  It is done once per
void lra_constraints_init ( void  )
   Initiate the LRA constraint pass.  It is done once per
lra_live_range_t lra_copy_live_range_list ( lra_live_range_t  )
void lra_create_copy ( int  ,
int  ,
void lra_create_live_ranges ( bool  )

Referenced by setup_reg_spill_flag().

rtx lra_create_new_reg_with_unique_value ( enum machine_mode  md_mode,
rtx  original,
enum reg_class  rclass,
const char *  title 
   Create and return a new reg of ORIGINAL mode.  If ORIGINAL is NULL
   or of VOIDmode, use MD_MODE for the new reg.  Initialize its
   register class to RCLASS.  Print message about assigning class
   RCLASS containing new register name TITLE unless it is NULL.  Use
   attributes of ORIGINAL if it is a register.  The created register
   will have unique held value.  

Referenced by change_class().

void lra_debug_elim_table ( void  )
   Print info about elimination table to stderr.  
void lra_debug_live_range_list ( lra_live_range_t  )
void lra_debug_live_ranges ( void  )
   Print live ranges of all pseudos to stderr.  

References lra_reg::freq, lra_hard_reg_usage, lra_reg_info, and reg_renumber.

void lra_debug_pseudo_live_ranges ( int  )
void lra_delete_dead_insn ( rtx  )
void lra_eliminate ( bool  )
void lra_eliminate_reg_if_possible ( rtx )
rtx lra_eliminate_regs_1 ( rtx  x,
enum machine_mode  mem_mode,
bool  subst_p,
bool  update_p,
bool  full_p 
   Scan X and replace any eliminable registers (such as fp) with a
   replacement (such as sp) if SUBST_P, plus an offset.  The offset is
   a change in the offset between the eliminable register and its
   substitution if UPDATE_P, or the full offset if FULL_P, or
   otherwise zero.

   MEM_MODE is the mode of an enclosing MEM.  We need this to know how
   much to adjust a register for, e.g., PRE_DEC.  Also, if we are
   inside a MEM, we are allowed to replace a sum of a hard register
   and the constant zero with the hard register, which we cannot do
   outside a MEM.  In addition, we need to record the fact that a
   hard register is referenced outside a MEM.

   Alternatively, INSN may be a note (an EXPR_LIST or INSN_LIST).
   That's used when we eliminate in expressions stored in notes.  
         First handle the case where we encounter a bare hard register
         that is eliminable.  Replace it with a PLUS.  
         If this is the sum of an eliminable register and a constant, rework
         the sum.  
             If the hard register is not eliminable, we are done since
             the other operand is a constant.  
         If this is part of an address, we want to bring any constant
         to the outermost PLUS.  We will do this by doing hard
         register replacement in our operands and seeing if a constant
         shows up in one of them.

         Note that there is no risk of modifying the structure of the
         insn, since we only get called for its operands, thus we are
         either modifying the address inside a MEM, or something like
         an address operand of a load-address insn.  
         If this is the product of an eliminable hard register and a
         constant, apply the distribute law and move the constant out
         so that we have (plus (mult ..) ..).  This is needed in order
         to keep load-address insns valid.  This case is pathological.
         We ignore the possibility of overflow here.  
         ... fall through ...  
       See comments before PLUS about handling MINUS.  
         If we have something in XEXP (x, 0), the usual case,
         eliminate it.  
                 If this is a REG_DEAD note, it is not valid anymore.
                 Using the eliminated version could result in creating a
                 REG_DEAD note for the stack or frame pointer.  
         ... fall through ...  
         Now do eliminations in the rest of the chain.  If this was
         an EXPR_LIST, this might result in allocating more memory than is
         strictly needed, but it simplifies the code.  
         We do not support elimination of a register that is modified.
         elimination_effects has already make sure that this does not
         We do not support elimination of a hard register that is
         modified.  LRA has already make sure that this does not
         happen. The only remaining case we need to consider here is
         that the increment value may be an eliminable register.  
         Our only special processing is to pass the mode of the MEM to our
         recursive call and copy the flags.  While we are here, handle this
         case more efficiently.  
         Handle insn_list USE that a call to a pure function may generate.  
     Process each of our operands recursively.  If any have changed, make a
     copy of the rtx.  

References elim_table::from_rtx, elim_table::offset, plus_constant(), elim_table::previous_offset, elim_table::to, and elim_table::to_rtx.

Referenced by assign_mem_slot().

void lra_emit_add ( rtx  ,
rtx  ,
void lra_emit_move ( rtx  ,
void lra_final_code_change ( void  )
   Final change of pseudos got hard registers into the corresponding
   hard registers and removing temporary clobbers.  
                 Remove clobbers temporarily created in LRA.  We don't
                 need them anymore and don't want to waste compiler
                 time processing them in a few subsequent passes.  
                 Remove an useless move insn but only involving
                 pseudos as some subsequent optimizations are based on
                 that move insns involving originally hard registers
                 are preserved.  IRA can generate move insns involving
                 pseudos.  It is better remove them earlier to speed
                 up compiler a bit.  It is also better to do it here
                 as they might not pass final RTL check in LRA,
                 (e.g. insn moving a control register into

References delete_insn(), and lra_invalidate_insn_data().

bool lra_former_scratch_operand_p ( rtx  ,
bool lra_former_scratch_p ( int  )
void lra_free_copies ( void  )
   Free all copies.  
lra_copy_t lra_get_copy ( int  )
int lra_get_elimination_hard_regno ( int  )
static lra_insn_recog_data_t lra_get_insn_recog_data ( )
   Return info about INSN.  Set up the info if it is not done yet.  
         Check that we did not change insn without updating the insn

Referenced by push_insns().

struct lra_insn_reg* lra_get_insn_regs ( int  )
static int lra_get_regno_hard_regno ( )
   Return the hard register which given pseudo REGNO assigned to.
   Negative value means that the register got memory or we don't know
   allocation yet.  

Referenced by assign_stack_slot_num_and_sort_pseudos(), remove_pseudos(), reverse_equiv_p(), and strip_subreg().

void lra_inheritance ( void  )
   Entry function for inheritance/split pass.  
         Form a EBB starting with BB.  
           Remember that the EBB head and tail can change in

References dump_insn_slim(), lra_dump_file, and lra_set_insn_deleted().

unsigned int lra_insn_stack_length ( void  )
   Return the current size of the insn stack.  
bool lra_intersected_live_ranges_p ( lra_live_range_t  ,

Referenced by add_pseudo_to_slot().

void lra_invalidate_insn_data ( rtx  )
void lra_invalidate_insn_regno_info ( rtx  )
void lra_live_ranges_finish ( void  )
   Finish live ranges data once per function.  
void lra_live_ranges_init ( void  )
   Initialize live ranges data once per function.  
lra_live_range_t lra_merge_live_ranges ( lra_live_range_t  ,
bool lra_need_for_spills_p ( void  )
   Return true if we need to change some pseudos into memory.  
rtx lra_pop_insn ( void  )
   Take the last-inserted insns off the stack and return it.  

References sloc::insn.

void lra_print_live_range_list ( FILE *  ,
void lra_process_new_insns ( rtx  ,
rtx  ,
rtx  ,
const char *   

Referenced by insert_move_for_subreg().

void lra_push_insn ( rtx  )
void lra_push_insn_and_update_insn_regno_info ( rtx  )
void lra_push_insn_by_uid ( unsigned  int)
static bool lra_reg_val_equal_p ( )
   Return true if register content is equal to VAL with OFFSET.  
void lra_set_insn_deleted ( rtx  )

Referenced by lra_inheritance().

lra_insn_recog_data_t lra_set_insn_recog_data ( rtx  )
void lra_set_regno_unique_value ( int  )
void lra_set_used_insn_alternative ( rtx  ,

Referenced by init_elim_table(), and remove_pseudos().

void lra_set_used_insn_alternative_by_uid ( int  ,
void lra_setup_reg_renumber ( int  ,
int  ,
void lra_setup_reload_pseudo_preferenced_hard_reg ( int  regno,
int  hard_regno,
int  profit 
   Update the preference of HARD_REGNO for pseudo REGNO by PROFIT.  
     Keep the 1st hard regno as more profitable.  
void lra_spill ( void  )
   Change spilled pseudos into memory or spill hard regs.  Put changed
   insns on the constraint stack (these insns will be considered on
   the next constraint pass).  The changed insns are all insns in
   which pseudos were changed.  
           We do not want to assign memory for former scratches.  
     Sort regnos according their usage frequencies.  
       If we have a stack frame, we must align it now.  The stack size
       may be a part of the offset computation for register
bool lra_undo_inheritance ( void  )
   Entry function for undoing inheritance/split transformation.  Return true
   if we did any RTL change in this pass.  
               If the original pseudo changed its allocation, just
               removing inheritance is dangerous as for changing
               allocation we used shorter live-ranges.  
     Clear restore_regnos.  
static void lra_update_dup ( )
   Update insn operands which are duplication of NOP operand.  The
   insn is represented by its LRA internal representation ID.  

References lra_reg::offset, and lra_reg::val.

Referenced by push_insns().

void lra_update_dups ( lra_insn_recog_data_t  ,
signed char *   
lra_insn_recog_data_t lra_update_insn_recog_data ( rtx  )

Referenced by init_elim_table().

void lra_update_insn_regno_info ( rtx  )
static void lra_update_operator_dups ( )
   Process operator duplications in insn with ID.  We do it after the
   operands processing.  Generally speaking, we could do this probably
   simultaneously with operands processing because a common practice
   is to enumerate the operators after their operands.  
static void lra_update_reg_val_offset ( )
   Update offset from pseudos with VAL by INCR.  

Variable Documentation

struct target_lra_int default_target_lra_int
   This page contains code dealing LRA insn info (or in other words
   LRA internal insn representation).  
int lra_coalesce_iter
   The current iteration (1, 2, ...) of the coalescing pass.  
int lra_constraint_iter
   The current iteration number of this LRA pass.  
int lra_constraint_iter_after_spill
   The current iteration number of this LRA pass after the last spill
int lra_constraint_new_insn_uid_start
   First UID of insns generated before a new spill pass.  
int lra_constraint_new_regno_start
   Start of reload pseudo regnos before the new spill pass.  

Referenced by bb_has_abnormal_call_pred(), spill_for(), and update_lives().

int lra_curr_reload_num
   The number of emitted reload insns so far.  
int lra_hard_reg_usage[FIRST_PSEUDO_REGISTER]
   Accumulated execution frequency of all references for each hard

Referenced by lra_debug_live_ranges(), and update_hard_regno_preference().

int lra_inheritance_iter
   Current number of inheritance/split iteration.  
bitmap_head lra_inheritance_pseudos
   Inheritance pseudo regnos before the new spill pass.  
   Map INSN_UID -> the insn recog data (NULL if unknown).  
int lra_insn_recog_data_len
   The current length of the following array.  
int lra_live_max_point

Build live ranges for pseudos. Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmaka.nosp@m.rov@.nosp@m.redha.nosp@m.t.co.nosp@m.m.

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

   This file contains code to build pseudo live-ranges (analogous
   structures used in IRA, so read comments about the live-ranges
   there) and other info necessary for other passes to assign
   hard-registers to pseudos, coalesce the spilled pseudos, and assign
   stack memory slots to spilled pseudos.  
   Program points are enumerated by numbers from range
   0..LRA_LIVE_MAX_POINT-1.  There are approximately two times more
   program points than insns.  Program points are places in the
   program where liveness info can be changed.  In most general case
   (there are more complicated cases too) some program points
   correspond to places where input operand dies and other ones
   correspond to places where output operands are born.  

Referenced by finish_live_range_start_chains(), remove_some_program_points_and_update_live_ranges(), and update_lives().

int lra_live_range_iter
   The number of the current live range pass.  
int lra_new_regno_start
   Start of pseudo regnos before the LRA.  

Referenced by match_reload().

HARD_REG_SET lra_no_alloc_regs

LRA (local register allocator) driver and LRA utilities. Copyright (C) 2010-2013 Free Software Foundation, Inc. Contributed by Vladimir Makarov vmaka.nosp@m.rov@.nosp@m.redha.nosp@m.t.co.nosp@m.m.

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

   The Local Register Allocator (LRA) is a replacement of former
   reload pass.  It is focused to simplify code solving the reload
   pass tasks, to make the code maintenance easier, and to implement new
   perspective optimizations.

   The major LRA design solutions are:
     o division small manageable, separated sub-tasks
     o reflection of all transformations and decisions in RTL as more
       as possible
     o insn constraints as a primary source of the info (minimizing
       number of target-depended macros/hooks)

   In brief LRA works by iterative insn process with the final goal is
   to satisfy all insn and address constraints:
     o New reload insns (in brief reloads) and reload pseudos might be
     o Some pseudos might be spilled to assign hard registers to
       new reload pseudos;
     o Changing spilled pseudos to stack memory or their equivalences;
     o Allocation stack memory changes the address displacement and
       new iteration is needed.

   Here is block diagram of LRA passes:

           ---------------     | Undo inheritance for   |     ---------------
          | Memory-memory |    | spilled pseudos,       |    | New (and old) |
          | move coalesce |<---| splits for pseudos got |<-- |   pseudos     |
           ---------------     | the same hard regs,    |    |  assignment   |
  Start           |            | and optional reloads   |     ---------------
    |             |             ------------------------            ^
    V             |              ----------------                   |
 -----------      V             | Update virtual |                  |
|  Remove   |----> ------------>|    register    |                  |
| scratches |     ^             |  displacements |                  |
 -----------      |              ----------------                   |
                  |                      |                          |
                  |                      V         New              |
         ----------------    No    ------------  pseudos   -------------------
        | Spilled pseudo | change |Constraints:| or insns | Inheritance/split |
        |    to memory   |<-------|    RTL     |--------->|  transformations  |
        |  substitution  |        | transfor-  |          |    in EBB scope   |
         ----------------         |  mations   |           -------------------
                |                   ------------
   | Hard regs substitution, |
   |  devirtalization, and   |------> Finish
   | restoring scratches got |
   |         memory          |

   To speed up the process:
     o We process only insns affected by changes on previous
     o We don't use DFA-infrastructure because it results in much slower
       compiler speed than a special IR described below does;
     o We use a special insn representation for quick access to insn
       info which is always *synchronized* with the current RTL;
       o Insn IR is minimized by memory.  It is divided on three parts:
         o one specific for each insn in RTL (only operand locations);
         o one common for all insns in RTL with the same insn code
           (different operand attributes from machine descriptions);
         o one oriented for maintenance of live info (list of pseudos).
       o Pseudo data:
         o all insns where the pseudo is referenced;
         o live info (conflicting hard regs, live ranges, # of
           references etc);
         o data used for assigning (preferred hard regs, costs etc).

   This file contains LRA driver, LRA utility functions and data, and
   code for dealing with scratches.  
   Hard registers currently not available for allocation.  It can
   changed after some hard  registers become not eliminable.  

Referenced by lra_intersected_live_ranges_p(), process_alt_operands(), and substitute_pseudo().

bitmap_head lra_optional_reload_pseudos
   Reload pseudo regnos before the new assignmnet pass which still can
   be spilled after the assinment pass as memory is also accepted in
   insns for the reload pseudos.  
int* lra_point_freq
   The start of the above vector elements.  
bool lra_reg_spill_p
   True if we should try spill into registers of different classes
   instead of memory.  

Referenced by remove_pseudos().

bool lra_risky_transformations_p
   True if we substituted equiv which needs checking register
   allocation correctness because the equivalent value contains
   allocatable hard registers or when we restore multi-register
bitmap_head lra_split_regs
   Split regnos before the new spill pass.  
bitmap_head lra_subreg_reload_pseudos
   Pseudo regnos used for subreg reloads before the new assignment
   pass.  Such pseudos still can be spilled after the assinment

Referenced by insert_move_for_subreg().

int lra_undo_inheritance_iter
   This page contains code to undo failed inheritance/split
   Current number of iteration undoing inheritance/split.  
struct target_lra_int* this_target_lra_int