GCC Middle and Back End API Reference
lra-assigns.c File Reference

Data Structures

struct  regno_assign_info


static void process_copy_to_form_thread ()
static void init_regno_assign_info ()
static void finish_regno_assign_info ()
static int reload_pseudo_compare_func ()
static int pseudo_compare_func ()
static void create_live_range_start_chains ()
static void insert_in_live_range_start_chain ()
static void finish_live_range_start_chains ()
static void init_lives ()
static void finish_lives ()
static void update_lives ()
static void init_live_reload_and_inheritance_pseudos ()
static void finish_live_reload_and_inheritance_pseudos ()
static void adjust_hard_regno_cost ()
static int find_hard_regno_for ()
static void update_hard_regno_preference ()
static const char * pseudo_prefix_title ()
void lra_setup_reg_renumber ()
static void setup_try_hard_regno_pseudos ()
static void assign_temporarily ()
static int spill_for ()
static void assign_hard_regno ()
static void setup_live_pseudos_and_spill_after_risky_transforms (bitmap spilled_pseudo_bitmap)
static void improve_inheritance ()
static void assign_by_spills ()
bool lra_assign ()


static enum reg_class * regno_allocno_class_array
static struct regno_assign_inforegno_assign_info
static bitmap_head non_reload_pseudos
static lra_live_range_tstart_point_ranges
static struct lra_live_range not_in_chain_mark
static bitmap_headlive_hard_reg_pseudos
static bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
static int * live_pseudos_reg_renumber
static sparseset live_range_hard_reg_pseudos
static sparseset live_range_reload_inheritance_pseudos
static sparseset conflict_reload_and_inheritance_pseudos
static bitmap_headlive_reload_and_inheritance_pseudos
static bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
static int curr_hard_regno_costs_check = 0
static int hard_regno_costs_check [FIRST_PSEUDO_REGISTER]
static int hard_regno_costs [FIRST_PSEUDO_REGISTER]
static int curr_update_hard_regno_preference_check
static int * update_hard_regno_preference_check
static bitmap_head insn_conflict_pseudos
static bitmap_head spill_pseudos_bitmap
static bitmap_head best_spill_pseudos_bitmap
static int curr_pseudo_check
static int try_hard_reg_pseudos_check [FIRST_PSEUDO_REGISTER]
static bitmap_head try_hard_reg_pseudos [FIRST_PSEUDO_REGISTER]
static int * sorted_reload_pseudos
static int * sorted_pseudos
static bitmap_head all_spilled_pseudos
static bitmap_head changed_pseudo_bitmap

Function Documentation

static void adjust_hard_regno_cost ( )
   Adjust cost of HARD_REGNO by INCR.  Reset the cost first if it is
   not defined yet.  

References lra_live_range::start_next.

static void assign_by_spills ( )
   Assign hard registers to reload pseudos and other pseudos.  
                 This register might have been spilled by the previous
                 pass.  Indicate that it is no longer spilled.  
                   As non-reload pseudo assignment is changed we
                   should reconsider insns referring for the
             We did not assign hard regs to reload pseudos after two
             iteration.  It means something is wrong with asm insn
             constraints.  Report it.  
                 Assign an arbitrary hard register of regno class to
                 avoid further trouble with the asm insns.  
                     Avoid further trouble with this insn.
                     For asm goto, instead of fixing up all the edges
                     just clear the template and clear input operands
                     (asm goto doesn't have any output operands).  
         This is a very rare event.  We can not assign a hard
         register to reload pseudo because the hard register was
         assigned to another reload pseudo on a previous
         assignment pass.  For x86 example, on the 1st pass we
         assigned CX (although another hard register could be used
         for this) to reload pseudo in an insn, on the 2nd pass we
         need CX (and only this) hard register for a new reload
         pseudo in the same insn.  
         FIXME: Look up the changed insns in the cached LRA insn data using
         an EXECUTE_IF_SET_IN_BITMAP over changed_insns.  
                   A reload pseudo did not get a hard register on the
                   first iteration because of the conflict with
                   another reload pseudos in the same insn.  So we
                   consider only reload pseudos assigned to hard
                   registers.  We shall exclude inheritance pseudos as
                   they can occur in original insns (not reload ones).
                   We can omit the check for split pseudos because
                   they occur only in move insns containing non-reload
         We should not assign to original pseudos of inheritance
         pseudos or split pseudos if any its inheritance pseudo did
         not get hard register or any its split pseudo was not split
         because undo inheritance/split pass will extend live range of
         such inheritance or split pseudos.  
                 We change allocation for non-reload pseudo on this
                 iteration -- mark the pseudo for invalidation of used
                 alternatives of insns containing the pseudo.  

References assign_hard_regno(), bitmap_clear_bit(), bitmap_ior_into(), and regno_allocno_class_array.

static void assign_hard_regno ( )
   Assign HARD_REGNO to REGNO.  

Referenced by assign_by_spills().

static void assign_temporarily ( )
   Assign temporarily HARD_REGNO to pseudo REGNO.  Temporary
   assignment means that we might undo the data change.  
static void create_live_range_start_chains ( )
static int find_hard_regno_for ( )
   Try to find a free hard register for pseudo REGNO.  Return the
   hard register on success and set *COST to the cost of using
   that register.  (If several registers have equal cost, the one with
   the highest priority wins.)  Return -1 on failure.

   If TRY_ONLY_HARD_REGNO >= 0, consider only that hard register,
   otherwise consider all hard registers in REGNO's class.  
           Remember about multi-register pseudos.  For example, 2 hard
           register pseudos can start on the same hard register but can
           not start on HR and HR+1/HR-1.  
     Make sure that all registers in a multi-word pseudo belong to the
     required class.  
             We can not use prohibited_class_mode_regs because it is
             not defined for all classes.  
                 It needs save restore.  
static void finish_live_range_start_chains ( )

References lra_live_max_point, max_reg_num(), and sparseset_alloc().

static void finish_live_reload_and_inheritance_pseudos ( )
   Finalize data about living reload pseudos at any given program

References offset, and priority().

static void finish_lives ( )
   Free the data about living pseudos at program points.  
static void finish_regno_assign_info ( )
static void improve_inheritance ( )
   Improve allocation by assigning the same hard regno of inheritance
   pseudos to the connected pseudos.  We need this because inheritance
   pseudos are allocated after reload pseudos in the thread and when
   we assign a hard register to a reload pseudo we don't know yet that
   the connected inheritance pseudos can get the same hard register.
   Add pseudos with changed allocation to bitmap CHANGED_PSEUDOS.  
             Don't change reload pseudo allocation.  It might have
             this allocation for a purpose and changing it can result
             in LRA cycling.  
static void init_live_reload_and_inheritance_pseudos ( )
   Allocate and initialize data about living reload pseudos at any
   given program point.  

References curr_hard_regno_costs_check.

static void init_lives ( )
   Allocate and initialize the data about living pseudos at program

References bitmap_clear_bit(), lra_live_range::finish, lra_reg_info, lra_live_range::next, reg_renumber, lra_live_range::regno, and lra_live_range::start.

static void init_regno_assign_info ( )
   Initialize REGNO_ASSIGN_INFO and form threads.  
     Form the threads.  
static void insert_in_live_range_start_chain ( )
   Insert live ranges of pseudo REGNO into start chains if they are
   not there yet.  
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.  
void lra_setup_reg_renumber ( )
   Update REG_RENUMBER and other pseudo preferences by assignment of
   HARD_REGNO to pseudo REGNO and print about it if PRINT_P.  
     We can not just reassign hard register.  

References bitmap_clear(), bitmap_set_bit(), curr_pseudo_check, and overlaps_hard_reg_set_p().

static void process_copy_to_form_thread ( )
   Process a pseudo copy with execution frequency COPY_FREQ connecting
   REGNO1 and REGNO2 to form threads.  

References regno_assign_info::first, first, regno_assign_info::freq, last, and regno_assign_info::next.

static int pseudo_compare_func ( )
   The function is used to sort *non-reload* pseudos to try to assign
   them hard registers.  The order calculation is simpler than in the
   previous function and based on the pseudo frequency usage.  
     Prefer to assign more frequently used registers first.  
     If regs are equally good, sort by their numbers, so that the
     results of qsort leave nothing to chance.  
static const char* pseudo_prefix_title ( )
   Return prefix title for pseudo REGNO.  

Referenced by update_hard_regno_preference().

static int reload_pseudo_compare_func ( )
   The function is used to sort *reload* and *inheritance* pseudos to
   try to assign them hard registers.  We put pseudos from the same
   thread always nearby.  
     Prefer to assign reload registers with smaller classes first to
     guarantee assignment to all reload registers.  
         The code below executes rarely as nregs == 1 in most cases.
         So we should not worry about using faster data structures to
         check reload pseudos.  
     Allocate bigger pseudos first to avoid register file
     Put pseudos from the thread nearby.  
     If regs are equally good, sort by their numbers, so that the
     results of qsort leave nothing to chance.  
static void setup_live_pseudos_and_spill_after_risky_transforms ( bitmap  spilled_pseudo_bitmap)
   The constraints pass is allowed to create equivalences between
   pseudos that make the current allocation "incorrect" (in the sense
   that pseudos are assigned to hard registers from their own conflict
   sets).  The global variable lra_risky_transformations_p says
   whether this might have happened.

   Process pseudos assigned to hard registers (less frequently used
   first), spill if a conflict is found, and mark the spilled pseudos
   pseudos, assigned to hard registers.  
               If it is multi-register pseudos they should start on
               the same hard register.  
static void setup_try_hard_regno_pseudos ( )
   Set up try_hard_reg_pseudos for given program point P and class
   RCLASS.  Those are pseudos living at P and assigned to a hard
   register of RCLASS.  In other words, those are pseudos which can be
   spilled to assign a hard register of RCLASS to a pseudo living at
     Find what pseudos could be spilled.  

References bitmap_clear(), bitmap_set_bit(), lra_get_insn_regs(), lra_reg_info, lra_insn_reg::next, reg_renumber, lra_live_range::regno, lra_insn_reg::regno, and regno_allocno_class_array.

static int spill_for ( )
   Spill some pseudos for a reload pseudo REGNO and return hard
   register which should be used for pseudo after spilling.  The
   function adds spilled pseudos to SPILLED_PSEUDO_BITMAP.  When we
   choose hard register (and pseudos occupying the hard registers and
   to be spilled), we take into account not only how REGNO will
   benefit from the spills but also how other reload pseudos not yet
   assigned to hard registers benefit from the spills too.  In very
   rare cases, the function can fail and return -1.  
     Invalidate try_hard_reg_pseudos elements.  
         Spill pseudos.  
         Restore the live hard reg pseudo info for spilled pseudos.  

References lra_constraint_new_regno_start, lra_live_range::regno, sparseset_set_bit(), lra_live_range::start, and lra_live_range::start_next.

static void update_hard_regno_preference ( )
   Update the preference for using HARD_REGNO for pseudos that are
   connected directly or indirectly with REGNO.  Apply divisor DIV
   to any preference adjustments.

   The more indirectly a pseudo is connected, the smaller its effect
   should be.  We therefore increase DIV on each "hop".  
     Search depth 5 seems to be enough.  

References lra_reg::freq, lra_dump_file, lra_hard_reg_usage, lra_reg_info, pseudo_prefix_title(), reg_renumber, and lra_live_range::regno.

static void update_lives ( )
   entries for pseudo REGNO.  Assume that the register has been
   spilled if FREE_P, otherwise assume that it has been assigned
   reg_renumber[REGNO] (if >= 0).  We also insert the pseudo live
   ranges in the start chains when it is assumed to be assigned to a
   hard register because we use the chains of pseudos assigned to hard
   registers during allocation.  

References bitmap_obstack_initialize(), bitmap_set_bit(), lra_live_range::finish, lra_constraint_new_regno_start, lra_live_max_point, lra_reg_info, max_reg_num(), max_regno, lra_live_range::next, sparseset_alloc(), and lra_live_range::start.

Variable Documentation

bitmap_head all_spilled_pseudos
   Bitmap finally containing all pseudos spilled on this assignment
bitmap_head best_spill_pseudos_bitmap
bitmap_head changed_pseudo_bitmap
   All pseudos whose allocation was changed.  
sparseset conflict_reload_and_inheritance_pseudos
   Sparseset used to calculate reload pseudos conflicting with a given
   pseudo when we are trying to find a hard register for the given
int curr_hard_regno_costs_check = 0
   The value used to check that cost of given hard reg is really
   defined currently.  

Referenced by init_live_reload_and_inheritance_pseudos().

int curr_pseudo_check
   Current pseudo check for validity of elements in

Referenced by lra_setup_reg_renumber().

int curr_update_hard_regno_preference_check
   Current value used for checking elements in
int hard_regno_costs[FIRST_PSEUDO_REGISTER]
   The current costs of allocation of hard regs.  Defined only if the
   value of the corresponding element of the previous array is equal to
int hard_regno_costs_check[FIRST_PSEUDO_REGISTER]
   Array used to check that cost of the corresponding hard reg (the
   array element index) is really defined currently.  
bitmap_head insn_conflict_pseudos
   Pseudos which occur in insns containing a particular pseudo.  
bitmap_head* live_hard_reg_pseudos
   Map: program point -> bitmap of all pseudos living at the point and
   assigned to hard registers.  
bitmap_obstack live_hard_reg_pseudos_bitmap_obstack
int* live_pseudos_reg_renumber
   reg_renumber corresponding to pseudos marked in
   live_hard_reg_pseudos.  reg_renumber might be not matched to
   live_hard_reg_pseudos but live_pseudos_reg_renumber always reflects
sparseset live_range_hard_reg_pseudos
   Sparseset used to calculate living hard reg pseudos for some program
   point range.  
sparseset live_range_reload_inheritance_pseudos
   Sparseset used to calculate living reload/inheritance pseudos for
   some program point range.  
bitmap_head* live_reload_and_inheritance_pseudos
   Map: program point -> bitmap of all reload and inheritance pseudos
   living at the point.  
bitmap_obstack live_reload_and_inheritance_pseudos_bitmap_obstack
bitmap_head non_reload_pseudos
   All inherited, subreg or optional pseudos created before last spill
   sub-pass.  Such pseudos are permitted to get memory instead of hard
struct lra_live_range not_in_chain_mark
   Used as a flag that a live range is not inserted in the start point

Referenced by create_live_range_start_chains().

enum reg_class* regno_allocno_class_array

Assign reload 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's main objective is to assign hard registers to reload
   pseudos.  It also tries to allocate hard registers to other
   pseudos, but at a lower priority than the reload pseudos.  The pass
   does not transform the RTL.

   We must allocate a hard register to every reload pseudo.  We try to
   increase the chances of finding a viable allocation by assigning
   the pseudos in order of fewest available hard registers first.  If
   we still fail to find a hard register, we spill other (non-reload)
   pseudos in order to make room.

   find_hard_regno_for finds hard registers for allocation without
   spilling.  spill_for does the same with spilling.  Both functions
   use a cost model to determine the most profitable choice of hard
   and spill registers.

   Once we have finished allocating reload pseudos, we also try to
   assign registers to other (non-reload) pseudos.  This is useful if
   hard registers were freed up by the spilling just described.

   We try to assign hard registers by collecting pseudos into threads.
   These threads contain reload and inheritance pseudos that are
   connected by copies (move insns).  Doing this improves the chances
   of pseudos in the thread getting the same hard register and, as a
   result, of allowing some move insns to be deleted.

   When we assign a hard register to a pseudo, we decrease the cost of
   using the same hard register for pseudos that are connected by

   If two hard registers have the same frequency-derived cost, we
   prefer hard registers with higher priorities.  The mapping of
   registers to priorities is controlled by the register_priority
   target hook.  For example, x86-64 has a few register priorities:
   hard registers with and without REX prefixes have different
   priorities.  This permits us to generate smaller code as insns
   without REX prefixes are shorter.

   If a few hard registers are still equally good for the assignment,
   we choose the least used hard register.  It is called leveling and
   may be profitable for some targets.

   Only insns with changed allocation pseudos are processed on the
   next constraint pass.

   The pseudo live-ranges are used to find conflicting pseudos.

   For understanding the code, it is important to keep in mind that
   inheritance, split, and reload pseudos created since last
   constraint pass have regno >= lra_constraint_new_regno_start.
   Inheritance and split pseudos created on any pass are in the
   corresponding bitmaps.  Inheritance and split pseudos since the
   last constraint pass have also the corresponding non-negative
   Array containing corresponding values of function
   lra_get_allocno_class.  It is used to speed up the code.  

Referenced by assign_by_spills(), and setup_try_hard_regno_pseudos().

   Map regno to the corresponding regno assignment info.  
int* sorted_pseudos
   Array used for sorting different pseudos.  
int* sorted_reload_pseudos
   Array used for sorting reload pseudos for subsequent allocation
   after spilling some pseudo.  
bitmap_head spill_pseudos_bitmap
   Bitmaps used to contain spill pseudos for given pseudo hard regno
   and best spill pseudos for given pseudo (and best hard regno).  
lra_live_range_t* start_point_ranges
   Arrays of size LRA_LIVE_MAX_POINT mapping a program point to the
   pseudo live ranges with given start point.  We insert only live
   ranges of pseudos interesting for assignment purposes.  They are
   reload pseudos and pseudos assigned to hard registers.  
bitmap_head try_hard_reg_pseudos[FIRST_PSEUDO_REGISTER]
   Pseudos who hold given hard register at the considered points.  
int try_hard_reg_pseudos_check[FIRST_PSEUDO_REGISTER]
   Array used for validity of elements in TRY_HARD_REG_PSEUDOS.  
int* update_hard_regno_preference_check
   If an element value is equal to the above variable value, then the
   corresponding regno has been processed for preference