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

Data Structures

struct  input_reload
struct  usage_insns
struct  to_inherit


static rtxstrip_subreg ()
static int get_try_hard_regno ()
static int get_final_hard_regno ()
static int get_hard_regno ()
static enum reg_class get_reg_class ()
static bool in_class_p ()
static bool in_mem_p ()
static rtx get_equiv_substitution ()
static void init_curr_operand_mode ()
static void init_curr_insn_input_reloads ()
static void change_class (int regno, enum reg_class new_class, const char *title, bool nl_p)
static bool get_reload_reg (enum op_type type, enum machine_mode mode, rtx original, enum reg_class rclass, const char *title, rtx *result_reg)
static bool ok_for_index_p_nonstrict ()
static bool ok_for_base_p_nonstrict (rtx reg, enum machine_mode mode, addr_space_t as, enum rtx_code outer_code, enum rtx_code index_code)
int lra_constraint_offset ()
static bool operands_match_p ()
static void narrow_reload_pseudo_class ()
static void match_reload (signed char out, signed char *ins, enum reg_class goal_class, rtx *before, rtx *after)
static enum reg_class reg_class_from_constraints ()
static enum reg_class get_op_class ()
static rtx emit_spill_move ()
static bool check_and_process_move ()
static bool process_addr_reg ()
static void insert_move_for_subreg ()
static bool simplify_operand_subreg ()
static bool uses_hard_regs_p ()
static bool spilled_pseudo_p ()
static bool general_constant_p ()
static bool reg_in_class_p ()
static bool process_alt_operands ()
static int valid_address_p (enum machine_mode mode, rtx addr, addr_space_t as)
static bool valid_address_p ()
static rtx base_plus_disp_to_reg ()
static bool can_add_disp_p ()
static bool equiv_address_substitution ()
static bool process_address ()
static rtx emit_inc ()
static bool simple_move_p ()
static void swap_operands ()
static bool curr_insn_transform ()
static bool in_list_p ()
static bool contains_reg_p ()
static bool loc_equivalence_change_p ()
static rtx loc_equivalence_callback ()
static bool multi_block_pseudo_p ()
static bool contains_deleted_insn_p ()
static bool dead_pseudo_p ()
static bool insn_rhs_dead_pseudo_p ()
static bool init_insn_rhs_dead_pseudo_p ()
static bool reverse_equiv_p ()
static bool contains_reloaded_insn_p ()
bool lra_constraints ()
void lra_constraints_init ()
void lra_constraints_finish ()
static void setup_next_usage_insn ()
static void add_next_usage_insn ()
static bool substitute_pseudo ()
static rtx skip_usage_debug_insns ()
static bool check_secondary_memory_needed_p (enum reg_class inher_cl, rtx usage_insns)
static bool inherit_reload_reg (bool def_p, int original_regno, enum reg_class cl, rtx insn, rtx next_usage_insns)
static bool need_for_call_save_p ()
static bool need_for_split_p ()
static enum reg_class choose_split_class (enum reg_class allocno_class, int hard_regno, enum machine_mode mode)
static bool split_reg ()
static bool split_if_necessary (int regno, enum machine_mode mode, HARD_REG_SET potential_reload_hard_regs, bool before_p, rtx insn, int max_uid)
static void update_ebb_live_info ()
static void add_to_inherit ()
static rtx get_last_insertion_point ()
static void get_live_on_other_edges ()
static bool inherit_in_ebb ()
void lra_inheritance ()
static void fix_bb_live_info ()
static int get_regno ()
static bool remove_inheritance_pseudos ()
static bool undo_optional_reloads ()
bool lra_undo_inheritance ()


static int bb_reload_num
static rtx curr_insn
static rtx curr_insn_set
static basic_block curr_bb
static lra_insn_recog_data_t curr_id
static struct
static enum machine_mode curr_operand_mode [MAX_RECOG_OPERANDS]
static int new_regno_start
static int new_insn_uid_start
static int curr_insn_input_reloads_num
static struct input_reload curr_insn_input_reloads [LRA_MAX_INSN_RELOADS]
static enum reg_class goal_alt [MAX_RECOG_OPERANDS]
static bool goal_alt_match_win [MAX_RECOG_OPERANDS]
static bool goal_alt_win [MAX_RECOG_OPERANDS]
static bool goal_alt_offmemok [MAX_RECOG_OPERANDS]
static int goal_alt_matches [MAX_RECOG_OPERANDS]
static int goal_alt_dont_inherit_ops_num
static int goal_alt_dont_inherit_ops [MAX_RECOG_OPERANDS]
static bool goal_alt_swapped
static int goal_alt_number
static int best_losers
static int best_overall
static int best_reload_nregs
static int best_reload_sum
static bool no_input_reloads_p
static bool no_output_reloads_p
static int curr_swapped
int lra_constraint_iter
int lra_constraint_iter_after_spill
bool lra_risky_transformations_p
static int reloads_num
static int calls_num
static int curr_usage_insns_check
static struct usage_insnsusage_insns
static bitmap_head check_only_regs
static bitmap_head ebb_global_regs
static bitmap_head live_regs
static struct to_inherit to_inherit [LRA_MAX_INSN_RELOADS]
static int to_inherit_num
static bitmap_head temp_bitmap
int lra_inheritance_iter
int lra_undo_inheritance_iter

Function Documentation

static void add_next_usage_insn ( )
   The function is used to form list REGNO usages which consists of
   optional debug insns finished by a non-debug insn using REGNO.
   RELOADS_NUM is current number of reload insns processed so far.  
         Check that we did not add the debug insn yet.  

Referenced by add_to_inherit().

static void add_to_inherit ( )
   Add inheritance info REGNO and INSNS. Their meaning is described in
   structure to_inherit.  

References add_next_usage_insn(), OP_IN, and reg_renumber.

static rtx base_plus_disp_to_reg ( )
   Make reload base reg + disp from address AD.  Return the new pseudo.  

References address_info::base_term, and address_info::base_term2.

static bool can_add_disp_p ( )
   Return true if we can add a displacement to address AD, even if that
   makes the address invalid.  The fix-up code requires any new address
   to be the sum of the BASE_TERM, INDEX and DISP_TERM fields.  
static void change_class ( int  regno,
enum reg_class  new_class,
const char *  title,
bool  nl_p 
   Change class of pseudo REGNO to NEW_CLASS.  Print info about it
   using TITLE.  Output a new line if NL_P.  

References lra_create_new_reg_with_unique_value().

static bool check_and_process_move ( )
   Process a special case insn (register move), return true if we
   don't need to process it anymore.  INSN should be a single set
   insn.  Set up that RTL was changed through CHANGE_P and macro
   SECONDARY_MEMORY_NEEDED says to use secondary memory through
       ALL_REGS is used for new pseudos created by transformations
       like reload of SUBREG_REG (see function
       simplify_operand_subreg).  We don't know their class yet.  We
       should figure out the class from processing the insn
       constraints not in this fast path function.  Even if ALL_REGS
       were a right class for the pseudo, secondary_... hooks usually
       are not define for ALL_REGS.  
       See comments above.  
     Set up hard register for a reload pseudo for hook
     secondary_reload because some targets just ignore unassigned
     pseudos in the hook.  
         Check the target hook consistency.  

References reg_renumber.

static bool check_secondary_memory_needed_p ( enum reg_class  inher_cl,
rtx  usage_insns 
   Return true if we need secondary memory moves for insn in
   USAGE_INSNS after inserting inherited pseudo of class INHER_CL
   into the insn.  
static enum reg_class choose_split_class ( enum reg_class  allocno_class,
int  hard_regno,
enum machine_mode  mode 
   Return class for the split pseudo created from original pseudo with
   ALLOCNO_CLASS and MODE which got a hard register HARD_REGNO.  We
   choose subclass of ALLOCNO_CLASS which contains HARD_REGNO and
   results in no secondary memory movements.  
static bool contains_deleted_insn_p ( )
   Return true if LIST contains a deleted insn.  
static bool contains_reg_p ( )
   Return true if X contains an allocatable hard register (if
   HARD_REG_P) or a (spilled if SPILLED_P) pseudo.  
static bool contains_reloaded_insn_p ( )
   Return TRUE if REGNO was reloaded in an equivalence init insn.  We
   call this function only for non-reverse equivalence.  
static bool curr_insn_transform ( )
   Main entry point of the constraint code: search the body of the
   current insn to choose the best alternative.  It is mimicking insn
   alternative cost calculation model of former reload pass.  That is
   because machine descriptions were written to use this model.  This
   model can be changed in future.  Make commutative operand exchange
   if it is chosen.

   Return true if some RTL changes happened during function call.  
     Flag that the insn has been changed through a transformation.  
     JUMP_INSNs and CALL_INSNs are not allowed to have any output
     reloads; neither are insns that SET cc0.  Insns that use CC0 are
     not allowed to have any input reloads.  
     Just return "no reloads" if insn has no operands with
     Now see what we need for pseudos that didn't get hard regs or got
     the wrong kind of hard reg.  For this, we must consider all the
     operands together against the register constraints.  
     Make equivalence substitution and memory subreg elimination
     before address processing because an address legitimacy can
     depend on memory mode.  
     Reload address registers and displacements.  We do it before
     finding an alternative because of memory constraints.  
       If we've changed the instruction then any alternative that
       we chose previously may no longer be valid.  
     If insn is commutative (it's safe to exchange a certain pair of
     operands) then we need to try each alternative twice, the second
     time matching those two operands as if we had exchanged them.  To
     do this, really exchange them in operands.

     If we have just tried the alternatives the second time, return
     operands to normal and drop through.  
         No alternative works with reloads??  
         Avoid further trouble with this insn.  
     If the best alternative is with operands 1 and 2 swapped, swap
     them.  Update the operand numbers of any reloads already
         Swap the duplicates too.  
     Some target macros SECONDARY_MEMORY_NEEDED (e.g. x86) are defined
     too conservatively.  So we use the secondary memory only if there
     is no any alternative without reloads.  
         If the mode is changed, it should be wider.  
             If the target says specifically to use another mode for
             secondary memory moves we can not reuse the original
             We may have non null BEFORE here (e.g. after address
             See comments above.  
     Right now, for any pair of operands I and J that are required to
     match, with J < I, goal_alt_matches[I] is J.  Add I to
           We allow matching one output operand and several input
     Any constants that aren't allowed and can't be reloaded into
     registers are here changed into memory references.  
               If the alternative accepts constant pool refs directly
               there will be no reload needed at all.  
               Skip alternatives before the one requested.  
                 When we assign NO_REGS it means that we will not
                 assign a hard register to the scratch pseudo by
                 assigment pass and the scratch pseudo will be
                 spilled.  Spilled scratch pseudos are transformed
                 back to scratches at the LRA end.  
                   We don't have to mark all insn affected by the
                   spilled pseudo as there is only one such insn, the
                   current one.  
             We can do an optional reload.  If the pseudo got a hard
             reg, we might improve the code through inheritance.  If
             it does not get a hard register we coalesce memory/memory
             moves later.  Ignore move insns to avoid cycling.  
         Operands that match previous ones have already been handled.  
         We should not have an operand with a non-offsettable address
         appearing where an offsettable address will do.  It also may
         be a case when the address should be special in other words
         not a general one (e.g. it needs no index reg).  
                                   This value does not matter for MODIFY.  
                     Strict_low_part requires reload the register not
                     the sub-register.  
             generate reloads for input and matched outputs.  
           Generate reloads for output and matched inputs.  
             Generate reloads for matched inputs.  
           We must generate code in any case when function
           process_alt_operands decides that it is possible.  
         Something changes -- process the insn.  
static bool dead_pseudo_p ( )
   Return true if X contains a pseudo dying in INSN.  
static rtx emit_inc ( )
   Emit insns to reload VALUE into a new register.  VALUE is an
   auto-increment or auto-decrement RTX whose operand is a register or
   memory location; so reloading involves incrementing that location.
   IN is either identical to VALUE, or some cheaper place to reload
   value being incremented/decremented from.

   INC_AMOUNT is the number to increment or decrement by (always
   positive and ignored for POST_MODIFY/PRE_MODIFY).

   Return pseudo containing the result.  
     REG or MEM to be copied and incremented.  
     Nonzero if increment after copying.  
         First copy the location to the result register.  
     We suppose that there are insns to add/sub with the constant
     increment permitted in {PRE/POST)_{DEC/INC/MODIFY}.  At least the
     old reload worked with this assumption.  If the assumption
     becomes wrong, we should use approach in function
         See if we can directly increment INCLOC.  
     If couldn't do the increment directly, must increment in RESULT.
     The way we do this depends on whether this is pre- or
     post-increment.  For pre-increment, copy INCLOC to the reload
     register, increment it there, then save back.  

         Because this might be a jump insn or a compare, and because
         RESULT may not be available after the insn in an input
         reload, we must do the incrementing before the insn being
         reloaded for.

         We have already copied IN to RESULT.  Increment the copy in
         RESULT, save that back, then decrement RESULT so it has
         the original value.  
         Restore non-modified value for the result.  We prefer this
         way because it does not require an additional hard
static rtx emit_spill_move ( )
   Return generated insn mem_pseudo:=val if TO_P or val:=mem_pseudo
   otherwise.  If modes of MEM_PSEUDO and VAL are different, use
   SUBREG for VAL to make them equal.  
         Usually size of mem_pseudo is greater than val size but in
         rare cases it can be less as it can be defined by target
         dependent macro HARD_REGNO_CALLER_SAVE_MODE.  
static bool equiv_address_substitution ( )
   Make equiv substitution in address AD.  Return true if a substitution
   was made.  

Referenced by valid_address_p().

static void fix_bb_live_info ( )
   Fix BB live info LIVE after removing pseudos created on pass doing
   inheritance/split which are REMOVED_PSEUDOS.  
static bool general_constant_p ( )
   Return true if X is a general constant.  

Referenced by process_alt_operands().

static rtx get_equiv_substitution ( )
   If we have decided to substitute X with another value, return that
   value, otherwise return X.  
static int get_final_hard_regno ( )
   Return final hard regno (plus offset) which will be after
   elimination.  We do this for matching constraints because the final
   hard regno could have a different class.  

References offset.

static int get_hard_regno ( )
   Return hard regno of X after removing subreg and making
   elimination.  If X is not a register or subreg of register, return
   -1.  For pseudo use its assignment.  

Referenced by ok_for_base_p_nonstrict(), process_alt_operands(), and uses_hard_regs_p().

static rtx get_last_insertion_point ( )
   Return the last non-debug insn in basic block BB, or the block begin
   note if none.  

References curr_insn, OP_IN, split_if_necessary(), and lra_insn_reg::subreg_p.

static void get_live_on_other_edges ( )
   Set up RES by registers living on edges FROM except the edge (FROM,
   TO) or by registers set up in a jump insn in BB FROM.  
static enum reg_class get_op_class ( )
   If OP is a register, return the class of the register as per
   get_reg_class, otherwise return NO_REGS.  
static enum reg_class get_reg_class ( )
   If REGNO is a hard register or has been allocated a hard register,
   return the class of that register.  If REGNO is a reload pseudo
   created by the current constraints pass, return its allocno class.
   Return NO_REGS otherwise.  

Referenced by process_alt_operands().

static int get_regno ( )
   Return regno of the (subreg of) REG. Otherwise, return a negative
static bool get_reload_reg ( enum op_type  type,
enum machine_mode  mode,
rtx  original,
enum reg_class  rclass,
const char *  title,
rtx result_reg 
   Create a new pseudo using MODE, RCLASS, ORIGINAL or reuse already
   created input reload pseudo (only if TYPE is not OP_OUT).  The
   result pseudo is returned through RESULT_REG.  Return TRUE if we
   created a new pseudo, FALSE if we reused the already created input
   reload pseudo.  Use TITLE to describe new registers for debug
     Prevent reuse value of expression with side effects,
     e.g. volatile memory.  
             If input is equal to original and both are VOIDmode,
             GET_MODE (reg) might be still different from mode.
             Ensure we don't return *result_reg with wrong mode.  

Referenced by insert_move_for_subreg().

static int get_try_hard_regno ( )
   Return hard regno of REGNO or if it is was not assigned to a hard
   register, use a hard register from its allocno class.  
static bool in_class_p ( )
   Return true if REG satisfies (or will satisfy) reg class constraint
   CL.  Use elimination first if REG is a hard register.  If REG is a
   reload pseudo created by this constraints pass, assume that it will
   be allocated a hard register from its allocno class, but allow that
   class to be narrowed to CL if it is currently a superset of CL.

   If NEW_CLASS is nonnull, set *NEW_CLASS to the new allocno class of
   REGNO (reg), or NO_REGS if no change in its class was needed.  
         Do not allow the constraints for reload instructions to
         influence the classes of new pseudos.  These reloads are
         typically moves that have many alternatives, and restricting
         reload pseudos for one alternative may lead to situations
         where other reload pseudos are no longer allocatable.  
       When we don't know what class will be used finally for reload
       pseudos, we use ALL_REGS.  
         Check that there are enough allocatable regs.  

Referenced by process_alt_operands().

static bool in_list_p ( )
   Return true if X is in LIST.  
static bool in_mem_p ( )
   Return true if REGNO satisfies a memory constraint.  
static bool inherit_in_ebb ( )
   Do inheritance/split transformations in EBB starting with HEAD and
   finishing on TAIL.  We process EBB insns in the reverse order.
   Return true if we did any inheritance/split transformation in the

   We should avoid excessive splitting which results in worse code
   because of inaccurate cost calculations for spilling new split
   pseudos in such case.  To achieve this we do splitting only if
   register pressure is high in given basic block and there are reload
   pseudos requiring hard registers.  We could do more register
   pressure calculations at any given program point to avoid necessary
   splitting even more but it is to expensive and the current approach
   works well enough.  
     We don't process new insns generated in the loop.  
             We are at the end of BB.  Add qualified living
             pseudos for potential splitting.  
                 We are somewhere in the middle of EBB.  
             'reload_pseudo <- original_pseudo'.  
             'original_pseudo <- reload_pseudo'.  
             Process insn definitions.  
                         Don't do inheritance if the pseudo is also
                         used in the insn.  
                           We can not do inheritance right now
                           because the current insn reg info (chain
                           regs) can change after that.  
                     We can not process one reg twice here because of
                     usage_insns invalidation.  
                     We should invalidate potential inheritance or
                     splitting for the current insn usages to the next
                     usage insns (see code below) as the output pseudo
                     prevents this.  
                         Invalidate and mark definitions.  
                     If there are pending saves/restores, the
                     optimization is not worth.  
                     Restore the pseudo from the call result as
                     REG_RETURNED note says that the pseudo value is
                     in the call result and the pseudo is an argument
                     of the call.  
                     We don't need to save/restore of the pseudo from
                     this call.  
             Process insn usages.  
                           Add usages but only if the reg is not set up
                           in the same insn.  
         We reached the start of the current basic block.  
             We reached the beginning of the current block -- do
             rest of spliting in the current BB.  
                 We are somewhere in the middle of EBB.  
static bool inherit_reload_reg ( bool  def_p,
int  original_regno,
enum reg_class  cl,
rtx  insn,
rtx  next_usage_insns 
   Do inheritance transformations for insn INSN, which defines (if
   DEF_P) or uses ORIGINAL_REGNO.  NEXT_USAGE_INSNS specifies which
   instruction in the EBB next uses ORIGINAL_REGNO; it has the same
   form as the "insns" field of usage_insns.  Return true if we
   succeed in such transformation.

   The transformations look like:

     p <- ...             i <- ...
     ...                  p <- i    (new insn)
     ...             =>
     <- ... p ...         <- ... i ...
     ...                  i <- p    (new insn)
     <- ... p ...         <- ... i ...
     ...             =>
     <- ... p ...         <- ... i ...
   where p is a spilled original pseudo and i is a new inheritance pseudo.

   The inheritance pseudo has the smallest class of two classes CL and
   class of ORIGINAL REGNO.  
         We don't use a subset of two classes because it can be
         NO_REGS.  This transformation is still profitable in most
         cases even if the classes are not intersected as register
         move is probably cheaper than a memory load.  
         Reject inheritance resulting in secondary memory moves.
         Otherwise, there is a danger in LRA cycling.  Also such
         transformation will be unprofitable.  
       We now have a new usage insn for original regno.  
static void init_curr_insn_input_reloads ( )
   Initiate data concerning reuse of input reloads for the current

References OP_OUT.

static void init_curr_operand_mode ( )
   Set up curr_operand_mode.  
             The .md mode for address operands is the mode of the
             addressed value rather than the mode of the address itself.  
static bool init_insn_rhs_dead_pseudo_p ( )
   Return true if any init insn of REGNO contains a dying pseudo in
   insn right hand side.  
static void insert_move_for_subreg ( )
   Insert move insn in simplify_operand_subreg. BEFORE returns
   the insn to be inserted before curr insn. AFTER returns the
   the insn to be inserted after curr insn.  ORIGREG and NEWREG
   are the original reg and new reg for reload.  

References bitmap_set_bit(), get_reload_reg(), lra_process_new_insns(), lra_subreg_reload_pseudos, OP_IN, OP_OUT, lra_static_insn_data::operand, and targetm.

static bool insn_rhs_dead_pseudo_p ( )
   Return true if INSN contains a dying pseudo in INSN right hand
static rtx loc_equivalence_callback ( )
   Similar to loc_equivalence_change_p, but for use as
   simplify_replace_fn_rtx callback.  
static bool loc_equivalence_change_p ( )
   Process all regs in location *LOC and change them on equivalent
   substitution.  Return true if any change was done.  
             We cannot reload debug location.  Simplify subreg here
             while we know the inner mode.  
     Scan all the operand sub-expressions.  
int lra_constraint_offset ( )
   The page contains major code to choose the current insn alternative
   and generate reloads for it.  
   Return the offset from REGNO of the least significant register
   in (reg:MODE REGNO).

   This function is used to tell whether two registers satisfy
   a matching constraint.  (reg:MODE1 REGNO1) matches (reg:MODE2 REGNO2) if:

         REGNO1 + lra_constraint_offset (REGNO1, MODE1)
         == REGNO2 + lra_constraint_offset (REGNO2, MODE2)  
bool lra_constraints ( )
   Entry function of LRA constraint pass.  Return true if the
   constraint pass did change the code.  
               After RTL transformation, we can not guarantee that
               pseudo in the substitution was not reloaded which might
               make equivalence invalid.  For example, in reverse
               equiv of p0

               p0 <- ...
               equiv_mem <- p0

               the memory address register was reloaded before the 2nd
                   We don't use DF for compilation speed sake.  So it
                   is problematic to update live info when we use an
                   equivalence containing pseudos in more than one
                   If an init insn was deleted for some reason, cancel
                   the equiv.  We could update the equiv insns after
                   transformations including an equiv insn deletion
                   but it is not worthy as such cases are extremely
                   If it is not a reverse equivalence, we check that a
                   pseudo in rhs of the init insn is not dying in the
                   insn.  Otherwise, the live info at the beginning of
                   the corresponding BB might be wrong after we
                   removed the insn.  When the equiv can be a
                   constant, the right hand side of the init insn can
                   be a pseudo.  
                           If we reloaded the pseudo in an equivalence
                           init insn, we can not remove the equiv init
                           insns and the init insns might write into
                           const memory in this case.  
                   Prevent access beyond equivalent memory for
                   paradoxical subregs.  
     We should add all insns containing pseudos which should be
     substituted by their equivalences.  
             We need to check equivalence in debug insn and change
             pseudo to the equivalent value if necessary.  
                 The equivalence pseudo could be set up as SUBREG in a
                 case when it is a call restore insn in a mode
                 different from the pseudo mode.  
                      Remove insns which set up a pseudo whose value
                      can not be changed.  Such insns might be not in
                      init_insns because we don't update equiv data
                      during insn transformations.
                      As an example, let suppose that a pseudo got
                      hard register and on the 1st pass was not
                      changed to equivalent constant.  We generate an
                      additional insn setting up the pseudo because of
                      secondary memory movement.  Then the pseudo is
                      spilled and we use the equiv constant.  In this
                      case we should remove the additional insn and
                      this insn is not init_insns list.  
                          Check that this is actually an insn setting
                          up the equivalence.  
                     This is equiv init insn of pseudo which did not get a
                     hard register -- remove the insn.  
             Check non-transformed insns too for equiv change as USE
             or CLOBBER don't need reloads but can contain pseudos
             being changed on their equivalences.  
     If we used a new hard regno, changed_p should be true because the
     hard reg is assigned to a new pseudo.  

References usage_insns::after_p, usage_insns::calls_num, usage_insns::check, usage_insns::insns, and usage_insns::reloads_num.

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
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().

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 match_reload ( signed char  out,
signed char *  ins,
enum reg_class  goal_class,
rtx before,
rtx after 
   Generate reloads for matching OUT and INS (array of input operand
   numbers with end marker -1) with reg class GOAL_CLASS.  Add input
   and output reloads correspondingly to the lists *BEFORE and *AFTER.
   OUT might be negative.  In this case we generate input reloads for
   matched input operands INS.  
             If the input reg is dying here, we can use the same hard
             register for REG and IN_RTX.  We do it only for original
             pseudos as reload pseudos can die although original
             pseudos still live where reload pseudos dies.  
             NEW_IN_REG is non-paradoxical subreg.  We don't want
             NEW_OUT_REG living above.  We add clobber clause for
             this.  This is just a temporary clobber.  We can remove
             it at the end of LRA work.  
                 If SUBREG_REG is dying here and sub-registers IN_RTX
                 and NEW_IN_REG are similar, we can use the same hard
                 register for REG and SUBREG_REG.  
         Pseudos have values -- see comments for lra_reg_info.
         Different pseudos with the same value do not conflict even if
         they live in the same place.  When we create a pseudo we
         assign value of original pseudo (if any) from which we
         created the new pseudo.  If we create the pseudo from the
         input pseudo, the new pseudo will no conflict with the input
         pseudo which is wrong when the input pseudo lives after the
         insn and as the new pseudo value is changed by the insn
         output.  Therefore we create the new pseudo from the output.

         We cannot reuse the current output register because we might
         have a situation like "a <- a op b", where the constraints
         force the second input operand ("b") to match the output
         operand ("a").  "b" must then be copied into a new register
         so that it doesn't clobber the current value of "a".  
     In operand can be got from transformations before processing insn
     constraints.  One example of such transformations is subreg
     reloading (see function simplify_operand_subreg).  The new
     pseudos created by the transformations might have inaccurate
     class (ALL_REGS) and we should make their classes more
     See a comment for the input operand above.  

References find_regno_note(), lra_assign_reg_val(), and lra_new_regno_start.

static bool multi_block_pseudo_p ( )
   Return true if REGNO is referenced in more than one block.  
static void narrow_reload_pseudo_class ( )
   If REG is a reload pseudo, try to make its class satisfying CL.  
     Do not make more accurate class from reloads generated.  They are
     mostly moves with a lot of constraints.  Making more accurate
     class may results in very narrow class and impossibility of find
     registers for several reloads of one insn.  
static bool need_for_call_save_p ( )
   Return true if we need a caller save/restore for pseudo REGNO which
   was assigned to a hard register.  

Referenced by substitute_pseudo().

static bool need_for_split_p ( )
   Return true if we need a split for hard register REGNO or pseudo
   REGNO which was assigned to a hard register.
   POTENTIAL_RELOAD_HARD_REGS contains hard registers which might be
   used for reloads since the EBB end.  It is an approximation of the
   used hard registers in the split range.  The exact value would
   require expensive calculations.  If we were aggressive with
   splitting because of the approximation, the split pseudo will save
   the same hard register assignment and will be removed in the undo
   pass.  We still need the approximation because too aggressive
   splitting would result in too inaccurate cost calculation in the
   assignment pass because of too many generated moves which will be
   probably removed in the undo pass.  
              Don't split eliminable hard registers, otherwise we can
              split hard registers like hard frame pointer, which
              lives on BB start/end according to DF-infrastructure,
              when there is a pseudo assigned to the register and
              living in the same BB.  
              Don't split call clobbered hard regs living through
              calls, otherwise we might have a check problem in the
              assign sub-pass as in the most cases (exception is a
              situation when lra_risky_transformations_p value is
              true) the assign pass assumes that all pseudos living
              through calls are assigned to call saved hard regs.  
              We need at least 2 reloads to make pseudo splitting
              profitable.  We should provide hard regno splitting in
              any case to solve 1st insn scheduling problem when
              moving hard register definition up might result in
              impossibility to find hard register for reload pseudo of
              small register class.  
                  For short living pseudos, spilling + inheritance can
                  be considered a substitution for splitting.
                  Therefore we do not splitting for local pseudos.  It
                  decreases also aggressiveness of splitting.  The
                  minimal number of references is chosen taking into
                  account that for 2 references splitting has no sense
                  as we can just spill the pseudo.  
static bool ok_for_base_p_nonstrict ( rtx  reg,
enum machine_mode  mode,
addr_space_t  as,
enum rtx_code  outer_code,
enum rtx_code  index_code 
   A version of regno_ok_for_base_p for use here, when all pseudos
   should count as OK.  Arguments as for regno_ok_for_base_p.  

References get_hard_regno().

static bool ok_for_index_p_nonstrict ( )
   The page contains code to extract memory address parts.  
   Wrapper around REGNO_OK_FOR_INDEX_P, to allow pseudos.  
static bool operands_match_p ( )
   Like rtx_equal_p except that it allows a REG and a SUBREG to match
   if they are the same hard reg, and has special hacks for
   auto-increment and auto-decrement.  This is specifically intended for
   process_alt_operands to use in determining whether two operands
   match.  X is the operand whose number is the lower of the two.

   It is supposed that X is the output operand and Y is the input
   operand.  Y_HARD_REGNO is the final hard regno of register Y or
   register in subreg Y as we know it now.  Otherwise, it is a
   negative value.  
     If two operands must match, because they are really a single
     operand of an assembler insn, then two post-increments are invalid
     because the assembler insn would increment only once.  On the
     other hand, a post-increment matches ordinary indexing if the
     post-increment is the output operand.  
     Two pre-increments are invalid because the assembler insn would
     increment only once.  On the other hand, a pre-increment matches
     ordinary indexing if the pre-increment is the input operand.  
     Now we have disposed of all the cases in which different rtx
     codes can match.  
     (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  
     Compare the elements.  If any pair of corresponding elements fail
     to match, return false for the whole things.  
             It is believed that rtx's at this level will never
             contain anything but integers and other rtx's, except for
             within LABEL_REFs and SYMBOL_REFs.  

Referenced by find_reloads(), process_alt_operands(), and strict_memory_address_addr_space_p().

static bool process_addr_reg ( )
   Arrange for address element *LOC to be a register of class CL.
   Add any input reloads to list BEFORE.  AFTER is nonnull if *LOC is an
   automodified value; handle that case by adding the required output
   reloads to list AFTER.  Return true if the RTL was changed.  
         Always reload memory in an address even if the target supports
         such addresses.  

Referenced by valid_address_p().

static bool process_address ( )
   Major function to make reloads for an address in operand NOP.
   The supported cases are:

   1) an address that existed before LRA started, at which point it
   must have been valid.  These addresses are subject to elimination
   and may have become invalid due to the elimination offset being out
   of range.

   2) an address created by forcing a constant to memory
   (force_const_to_mem).  The initial form of these addresses might
   not be valid, and it is this function's job to make them valid.

   3) a frame address formed from a register and a (possibly zero)
   constant offset.  As above, these addresses might not be valid and
   this function must make them so.

   Add reloads to the lists *BEFORE and *AFTER.  We might need to add
   reloads to *AFTER because of inc/dec, {pre, post} modify in the
   address.  Return true for any RTL change.  
     Target hooks sometimes reject extra constraint addresses -- use
     EXTRA_CONSTRAINT_STR for the validation.  
     There are three cases where the shape of *AD.INNER may now be invalid:

     1) the original address was valid, but either elimination or
     equiv_address_substitution was applied and that made
     the address invalid.

     2) the address is an invalid symbolic address created by

     3) the address is a frame address with an invalid offset.

     All these cases involve a non-autoinc address, so there is no
     point revalidating other types.  
     Any index existed before LRA started, so we can assume that the
     presence and shape of the index is valid.  
               addr => lo_sum (new_base, addr), case (2) above.  
                       Try to put lo_sum into register.  
                 addr => new_base, case (2) above.  
             index * scale + disp => new base + index * scale,
             case (1) above.  
         base + disp => new base, cases (1) and (3) above.  
         Another option would be to reload the displacement into an
         index register.  However, postreload has code to optimize
         address reloads that have the same base and different
         displacements, so reloading into an index register would
         not necessarily be a win.  
         If we generated at least two insns, try last insn source as
         an address.  If we succeed, we generate one less insn.  
         base + scale * index + disp => new base + scale * index,
         case (1) above.  
static bool process_alt_operands ( )
   Major function to choose the current insn alternative and what
   operands should be reloaded and how.  If ONLY_ALTERNATIVE is not
   negative we should consider only this alternative.  Return false if
   we can not choose the alternative or find how to reload the
     LOSERS counts the operands that don't fit this alternative and
     would require loading.  
     REJECT is a count of how undesirable this alternative says it is
     if any reloading is required.  If the alternative matches exactly
     then REJECT is ignored, but otherwise it gets this much counted
     against it in addition to the reloading needed.  
     The number of elements in the following array.  
     Numbers of operands which are early clobber registers.  
     The number of elements in the following array.  
     Numbers of operands whose reload pseudos should not be inherited.  
     The register when the operand is a subreg of register, otherwise the
     operand itself.  
     The register if the operand is a register or subreg of register,
     otherwise NULL.  
     Calculate some data common for all alternatives to speed up the
         The real hard regno of the operand after the allocation.  
     The constraints are made of several alternatives.  Each operand's
     constraint looks like foo,bar,... with commas separating the
     alternatives.  The first alternatives for all operands go
     together, the second alternatives go together, etc.

     First loop over alternatives.  
         Loop over operands for one constraint alternative.  
             false => this operand can be reloaded somehow for this
             true => this operand can be reloaded if the alternative
             allows regs.  
             True if a constant forced into memory would be OK for
             this operand.  
                 Fast track for no constraints at all.  
             We update set of possible hard regs besides its class
             because reg class might be inaccurate.  For example,
             union of LO_REGS (l), HI_REGS(h), and STACK_REG(k) in ARM
             is translated in HI_REGS because classes are merged by
             pairs and there is no accurate intermediate class.  
             An empty constraint should be excluded by the fast
             Scan this alternative's specs for this operand; set WIN
             if the operand fits any letter in this alternative.
             Otherwise, clear BADOP if this operand could fit some
             letter after reloads, or set WINREG if this operand could
             fit after reloads provided the constraint allows some
                     We only support one commutative marker, the first
                     one.  We already set commutative above.  
                     Ignore rest of this alternative.  
                       We are supposed to match a previous operand.
                       If we do, we win if that one did.  If we do
                       not, count both of the operands as losers.
                       (This is too conservative, since most of the
                       time only a single reload insn will be needed
                       to make the two operands win.  As a result,
                       this alternative may be rejected when it is
                       actually desirable.)  
                           We should reject matching of an early
                           clobber operand if the matching operand is
                           not dying in the insn.  
                           If we are matching a non-offsettable
                           address where an offsettable address was
                           expected, then we must reject this
                           combination, because we can't reload
                           Operands don't match.  Both operands must
                           allow a reload register, otherwise we
                           cannot make them match.  
                           Retroactively mark the operand we had to
                           match as a loser, if it wasn't already and
                           it wasn't matched to a register constraint
                           (e.g it might be matched by memory). 
                           We prefer no matching alternatives because
                           it gives more freedom in RA.  
                       If we have to reload this operand and some
                       previous operand also had to match the same
                       thing as this operand, we don't know how to do
                       This can be fixed with reloads if the operand
                       we are supposed to match can be fixed with
                     We can put constant or pseudo value into memory
                     to satisfy the constraint.  
                     Memory op whose address is not offsettable.  
                     Memory operand whose address is offsettable.  
                     We can put constant or pseudo value into memory
                     or make memory address offsetable to satisfy the
                     This constraint should be excluded by the fast
                     Drop through into 'r' case.  
                             If we didn't already win, we can reload
                             constants via force_const_mem or put the
                             pseudo value into memory, or make other
                             memory by reloading the address like for
                             If we didn't already win, we can reload
                             the address into a base register.  
             Record which operands fit this alternative.  
                         Prefer won reg to spilled pseudo under other
                         equal conditions for possibe inheritance.  
                     We simulate the behaviour of old reload here.
                     Although scratches need hard registers and it
                     might result in spilling other pseudos, no reload
                     insns are generated for the scratches.  So it
                     might cost something but probably less than old
                     reload pass believes.  
                 If this alternative asks for a specific reg class, see if there
                 is at least one allocatable register in that class.  
                 For asms, verify that the class for this alternative is possible
                 for the mode that is specified.  
                 If this operand accepts a register, and if the
                 register class has at least one allocatable register,
                 then this operand can be reloaded.  
                 If the operand is dying, has a matching constraint,
                 and satisfies constraints of the matched operand
                 which failed to satisfy the own constraints, we do
                 not need to generate a reload insn for this
                     Strict_low_part requires to reload the register
                     not the sub-register.  In this case we should
                     check that a final reload hard reg can hold the
                     value mode.  
                     Output operands and matched input operands are
                     not inherited.  The following conditions do not
                     exactly describe the previous statement but they
                     are pretty close.  
                 If this is a constant that is reloaded into the
                 desired class by copying it to memory first, count
                 that as another reload.  This is consistent with
                 other code and is required to avoid choosing another
                 alternative when the constant is moved into memory.
                 Note that the test here is precisely the same as in
                 the code below that calls force_const_mem.  
                 Alternative loses if it requires a type of reload not
                 permitted for this insn.  We can always reload
                 objects with a REG_UNUSED note.  
                 Check strong discouragement of reload of non-constant
                 into class THIS_ALTERNATIVE.  
                     We prefer to reload pseudos over reloading other
                     things, since such reloads may be able to be
                     eliminated later.  So bump REJECT in other cases.
                     Don't do this in the case where we are forcing a
                     constant into memory and it will then win since
                     we don't want to have a different alternative
                     match then.  
                 We are trying to spill pseudo into memory.  It is
                 usually more costly than moving to a hard register
                 although it might takes the same number of
                 If reload requires moving value through secondary
                 memory, it will need one more insn at least.  
                 Input reloads can be inherited more often than output
                 reloads can be removed, so penalize output
             ??? We check early clobbers after processing all operands
             (see loop below) and there we update the costs more.
             Should we update the cost (may be approximately) here
             because of early clobber register reloads or it is a rare
             or non-important thing to be worth to do it.  
             Prevent processing non-move insns.  
                     If it is a result of recent elimination in move
                     insn we can transform it into an add still by
                     using this alternative.  
             We have a move insn and a new reload insn will be similar
             to the current insn.  We should avoid such situation as it
             results in LRA cycling.  
                   We don't want process insides of match_operator and
                   match_parallel because otherwise we would process
                   their operands once again generating a wrong
               If we don't reload j-th operand, check conflicts.  
             If earlyclobber operand conflicts with another
             non-matching operand which is actually the same register
             as the earlyclobber operand, it is better to reload the
             another operand as an operand matching the earlyclobber
             operand can be also the same.  
                 Early clobber was already reflected in REJECT. 
                 We need to reload early clobbered register and the
                 matched registers.  
                     Remember pseudos used for match reloads are never
                 Early clobber was already reflected in REJECT. 
         If this alternative can be made to work by reloading, and it
         needs less reloading than the others checked so far, record
         it as the chosen goal for reloading.  
                         If the cost of the reloads is the same,
                         prefer alternative which requires minimal
                         number of reload regs.  
           Everything is satisfied.  Do not process alternatives

References operand_alternative::anything_ok, base_reg_class(), bb_reload_num, operand_alternative::constraint, curr_operand_mode, lra_operand_data::early_clobber, find_reg_note(), find_regno_note(), general_constant_p(), get_hard_regno(), get_reg_class(), hard_reg_set_subset_p(), in_class_p(), in_hard_reg_set_p(), lra_reg::last_reload, len, lra_dump_file, lra_former_scratch_p(), lra_no_alloc_regs, lra_reg_info, address_info::mode, offsettable_nonstrict_memref_p(), OP_IN, OP_OUT, lra_static_insn_data::operand, lra_static_insn_data::operand_alternative, lra_insn_recog_data::operand_loc, operands_match_p(), reject(), spilled_pseudo_p(), lra_operand_data::strict_low, and targetm.

static enum reg_class reg_class_from_constraints ( )
   Return register class which is union of all reg classes in insn
   constraint alternative string starting with P.  

References gen_lowpart_SUBREG(), gen_move_insn(), and gen_rtx_SUBREG().

static bool reg_in_class_p ( )
static bool remove_inheritance_pseudos ( )
   Remove inheritance/split pseudos which are in REMOVE_PSEUDOS and
   return true if we did any change.  The undo transformations for
   inheritance looks like
      i <- i2
      p <- i      =>   p <- i2
   or removing
      p <- i, i <- p, and i <- i3
   where p is original pseudo from which inheritance pseudo i was
   created, i and i3 are removed inheritance pseudos, i2 is another
   not removed inheritance pseudo.  All split pseudos or other
   occurrences of removed inheritance pseudos are changed on the
   corresponding original pseudos.

   The function also schedules insns changed and created during
   inheritance/split pass for processing by the subsequent constraint
     We can not finish the function right away if CHANGE_P is true
     because we need to marks insns affected by previous
     inheritance/split pass for processing by the subsequent
     constraint pass.  
                   One of the following cases:
                     original <- removed inheritance pseudo
                     removed inherit pseudo <- another removed inherit pseudo
                     removed inherit pseudo <- original pseudo
                     removed_split_pseudo <- original_reg
                     original_reg <- removed_split_pseudo 
                     Search the following pattern:
                       inherit_or_split_pseudo1 <- inherit_or_split_pseudo2
                       original_pseudo <- inherit_or_split_pseudo1
                    where the 2nd insn is the current insn and
                    inherit_or_split_pseudo2 is not removed.  If it is found,
                    change the current insn onto:
                       original_pseudo <- inherit_or_split_pseudo2.  
                         There should be no subregs in insn we are
                         searching because only the original reg might
                         be in subreg when we changed the mode of
                         load/store for splitting.  
                         As we consider chain of inheritance or
                         splitting described in above comment we should
                         check that sregno and prev_sregno were
                         inheritance/split pseudos created from the
                         same original regno.  
                     The instruction has changed since the previous
                     constraints pass.  
                   The instruction has been restored to the form that
                   it had during the previous constraints pass.  
static bool reverse_equiv_p ( )
   Return TRUE if REGNO has a reverse equivalence.  The equivalence is
   reverse only if we have one init insn with given REGNO as a

References df_regs_ever_live_p(), lra_get_regno_hard_regno(), and new_regno_start.

static void setup_next_usage_insn ( )
static bool simple_move_p ( )
   Return true if the current move insn does not need processing as we
   already know that it satisfies its constraints.  
             The backend guarantees that register moves of cost 2
             never need reloads.  
static bool simplify_operand_subreg ( )
   Make reloads for subreg in operand NOP with internal subreg mode
   REG_MODE, add new reloads for further processing.  Return true if
   any reload was generated.  
     If we change address for paradoxical subreg of memory, the
     address might violate the necessary alignment or the access might
     be slow.  So take this into consideration.  We should not worry
     about access beyond allocated memory for paradoxical memory
     subregs as we don't substitute such equiv memory (see processing
     equivalences in function lra_constraints) and because for spilled
     pseudos we allocate stack memory enough for the biggest
     corresponding paradoxical subreg.  
     Put constant into memory when we have mixed modes.  It generates
     a better code in most cases as it does not need a secondary
     reload memory.  It also prevents LRA looping when LRA is using
     secondary reload memory again and again.  
     Force a reload of the SUBREG_REG if this is a constant or PLUS or
     if there may be a problem accessing OPERAND in the outer
          Don't reload paradoxical subregs because we could be looping
          having repeatedly final regno out of hard regs range.  
          Don't reload subreg for matching reload.  It is actually
          valid subreg in LRA.  
         The class will be defined later in curr_insn_transform.  
     Force a reload for a paradoxical subreg. For paradoxical subreg,
     IRA allocates hardreg to the inner pseudo reg according to its mode
     instead of the outermode, so the size of the hardreg may not be enough
     to contain the outermode operand, in that case we may need to insert
     reload for the reg. For the following two types of paradoxical subreg,
     we need to insert reload:
     1. If the op_type is OP_IN, and the hardreg could not be paired with
        other hardreg to contain the outermode operand
        (checked by in_hard_reg_set_p), we need to insert the reload.
     2. If the op_type is OP_OUT or OP_INOUT.

     Here is a paradoxical subreg example showing how the reload is generated:

     (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
        (subreg:TI (reg:DI 107 [ __comp ]) 0)) {*movti_internal_rex64}

     In IRA, reg107 is allocated to a DImode hardreg. We use x86-64 as example
     here, if reg107 is assigned to hardreg R15, because R15 is the last
     hardreg, compiler cannot find another hardreg to pair with R15 to
     contain TImode data. So we insert a TImode reload reg180 for it.
     After reload is inserted:

     (insn 283 0 0 (set (subreg:DI (reg:TI 180 [orig:107 __comp ] [107]) 0)
        (reg:DI 107 [ __comp ])) -1
     (insn 5 4 7 2 (set (reg:TI 106 [ __comp ])
        (subreg:TI (reg:TI 180 [orig:107 __comp ] [107]) 0)) {*movti_internal_rex64}

     Two reload hard registers will be allocated to reg180 to save TImode data
     in LRA_assign.  
         The class will be defined later in curr_insn_transform.  
static rtx skip_usage_debug_insns ( )
   Return first non-debug insn in list USAGE_INSNS.  
     Skip debug insns.  
static bool spilled_pseudo_p ( )
   Return true if OP is a spilled pseudo. 

Referenced by process_alt_operands().

static bool split_if_necessary ( int  regno,
enum machine_mode  mode,
HARD_REG_SET  potential_reload_hard_regs,
bool  before_p,
rtx  insn,
int  max_uid 
   Recognize that we need a split transformation for insn INSN, which
   defines or uses REGNO in its insn biggest MODE (we use it only if
   REGNO is a hard register).  POTENTIAL_RELOAD_HARD_REGS contains
   hard registers which might be used for reloads since the EBB end.
   Put the save before INSN if BEFORE_P is true.  MAX_UID is maximla
   uid before starting INSN processing.  Return true if we succeed in
   such transformation.  
           To avoid processing the register twice or more.  

Referenced by get_last_insertion_point().

static bool split_reg ( )
   Do split transformations for insn INSN, which defines or uses
   ORIGINAL_REGNO.  NEXT_USAGE_INSNS specifies which instruction in
   the EBB next uses ORIGINAL_REGNO; it has the same form as the
   "insns" field of usage_insns.

   The transformations look like:

     p <- ...             p <- ...
     ...                  s <- p    (new insn -- save)
     ...             =>
     ...                  p <- s    (new insn -- restore)
     <- ... p ...         <- ... p ...
     <- ... p ...         <- ... p ...
     ...                  s <- p    (new insn -- save)
     ...             =>
     ...                  p <- s    (new insn -- restore)
     <- ... p ...         <- ... p ...

   where p is an original pseudo got a hard register or a hard
   register and s is a new split pseudo.  The save is put before INSN
   if BEFORE_P is true.  Return true if we succeed in such
       If we are trying to split multi-register.  We should check
       conflicts on the next assignment sub-pass.  IRA can allocate on
       sub-register levels, LRA do this on pseudos level right now and
       this discrepancy may create allocation conflicts after

References to_inherit::insns, to_inherit::regno, and to_inherit_num.

static rtx* strip_subreg ( )
   If LOC is nonnull, strip any outer subreg from it.  

References lra_get_regno_hard_regno().

static bool substitute_pseudo ( )
   Replace all references to register OLD_REGNO in *LOC with pseudo
   register NEW_REG.  Return true if any change was made.  
     Scan all the operand sub-expressions.  

References bitmap_bit_p(), eliminable_regset, lra_no_alloc_regs, need_for_call_save_p(), and reg_renumber.

static void swap_operands ( )
   Swap operands NOP and NOP + 1. 
     Swap the duplicates too.  

References lra_dump_file.

static bool undo_optional_reloads ( )
   If optional reload pseudos failed to get a hard register or was not
   inherited, it is better to remove optional reloads.  We do this
   transformation after undoing inheritance to figure out necessity to
   remove optional reloads easier.  Return true if we do any
         Keep optional reloads from previous subpasses.  
             If the original pseudo changed its allocation, just
             removing the optional pseudo is dangerous as the original
             pseudo will have longer live range.  
                   Ignore insn for optional reloads itself.  
                   Check only inheritance on last inheritance pass.  
                   Check that the optional reload was inherited.  
                 We should not worry about generation memory-memory
                 moves here as if the corresponding inheritance did
                 not work (inheritance pseudo did not get a hard reg),
                 we remove the inheritance pseudo and the optional
     Clear restore_regnos.  
static void update_ebb_live_info ( )
   Update live info in EBB given by its HEAD and TAIL insns after
   inheritance/split transformation.  The function removes dead moves
         We need to process empty blocks too.  They contain
         NOTE_INSN_BASIC_BLOCK referring for the basic block.  
                 Update df_get_live_in (prev_bb):  
                 Update df_get_live_out (curr_bb):  
         See which defined values die here.  
         Mark each used value as live.  
         It is quite important to remove dead move insns because it
         means removing dead store.  We don't need to process them for
static bool uses_hard_regs_p ( )
   Return TRUE if X refers for a hard register from SET.  

References get_hard_regno(), and lra_insn_recog_data::operand_loc.

static int valid_address_p ( enum machine_mode  mode,
rtx  addr,
addr_space_t  as 
   Return 1 if ADDR is a valid memory address for mode MODE in address
   space AS, and check that each pseudo has the proper kind of hard

References dump_value_slim(), lra_dump_file, and address_info::outer.

static bool valid_address_p ( )
   Return whether address AD is valid.  
     Some ports do not check displacements for eliminable registers,
     so we replace them temporarily with the elimination target.  

References address_info::base_term, lra_operand_data::constraint, decompose_lea_address(), decompose_mem_address(), equiv_address_substitution(), lra_static_insn_data::operand, lra_insn_recog_data::operand_loc, and process_addr_reg().

Variable Documentation

int bb_reload_num
   Code for RTL transformations to satisfy insn constraints.
   Copyright (C) 2010-2013 Free Software Foundation, Inc.
   Contributed by Vladimir Makarov <vmakarov@redhat.com>.

   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

   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
   This file contains code for 3 passes: constraint pass,
   inheritance/split pass, and pass for undoing failed inheritance and

   The major goal of constraint pass is to transform RTL to satisfy
   insn and address constraints by:
     o choosing insn alternatives;
     o generating *reload insns* (or reloads in brief) and *reload
       pseudos* which will get necessary hard registers later;
     o substituting pseudos with equivalent values and removing the
       instructions that initialized those pseudos.

   The constraint pass has biggest and most complicated code in LRA.
   There are a lot of important details like:
     o reuse of input reload pseudos to simplify reload pseudo
     o some heuristics to choose insn alternative to improve the
     o early clobbers etc.

   The pass is mimicking former reload pass in alternative choosing
   because the reload pass is oriented to current machine description
   model.  It might be changed if the machine description model is

   There is special code for preventing all LRA and this pass cycling
   in case of bugs.

   On the first iteration of the pass we process every instruction and
   choose an alternative for each one.  On subsequent iterations we try
   to avoid reprocessing instructions if we can be sure that the old
   choice is still valid.

   The inheritance/spilt pass is to transform code to achieve
   ineheritance and live range splitting.  It is done on backward
   traversal of EBBs.

   The inheritance optimization goal is to reuse values in hard
   registers. There is analogous optimization in old reload pass.  The
   inheritance is achieved by following transformation:

       reload_p1 <- p        reload_p1 <- p
       ...                   new_p <- reload_p1
       ...              =>   ...
       reload_p2 <- p        reload_p2 <- new_p

   where p is spilled and not changed between the insns.  Reload_p1 is
   also called *original pseudo* and new_p is called *inheritance

   The subsequent assignment pass will try to assign the same (or
   another if it is not possible) hard register to new_p as to
   reload_p1 or reload_p2.

   If the assignment pass fails to assign a hard register to new_p,
   this file will undo the inheritance and restore the original code.
   This is because implementing the above sequence with a spilled
   new_p would make the code much worse.  The inheritance is done in
   EBB scope.  The above is just a simplified example to get an idea
   of the inheritance as the inheritance is also done for non-reload

   Splitting (transformation) is also done in EBB scope on the same
   pass as the inheritance:

       r <- ... or ... <- r              r <- ... or ... <- r
       ...                               s <- r (new insn -- save)
       ...                        =>
       ...                               r <- s (new insn -- restore)
       ... <- r                          ... <- r

    The *split pseudo* s is assigned to the hard register of the
    original pseudo or hard register r.

    Splitting is done:
      o In EBBs with high register pressure for global pseudos (living
        in at least 2 BBs) and assigned to hard registers when there
        are more one reloads needing the hard registers;
      o for pseudos needing save/restore code around calls.

    If the split pseudo still has the same hard register as the
    original pseudo after the subsequent assignment pass or the
    original pseudo was split, the opposite transformation is done on
    the same pass for undoing inheritance.  
   Value of LRA_CURR_RELOAD_NUM at the beginning of BB of the current
   insn.  Remember that LRA_CURR_RELOAD_NUM is the number of emitted
   reload insns.  

Referenced by process_alt_operands().

int best_losers
   The following five variables are used to choose the best insn
   alternative.  They reflect final characteristics of the best
   Number of necessary reloads and overall cost reflecting the
   previous value and other unpleasantness of the best alternative.  
int best_overall
int best_reload_nregs
   Overall number hard registers used for reloads.  For example, on
   some targets we need 2 general registers to reload DFmode and only
   one floating point register.  
int best_reload_sum
   Overall number reflecting distances of previous reloading the same
   value.  The distances are counted from the current BB start.  It is
   used to improve inheritance chances.  
int calls_num
   Number of calls passed so far in current EBB.  
bitmap_head check_only_regs
   Registers involved in inheritance/split in the current EBB
   (inheritance/split pseudos and original registers).  
basic_block curr_bb
lra_insn_recog_data_t curr_id
rtx curr_insn
   The current insn being processed and corresponding its single set
   (NULL otherwise), its data (basic block, the insn data, the insn
   static data, and the mode of each operand).  

Referenced by get_last_insertion_point().

struct input_reload curr_insn_input_reloads[LRA_MAX_INSN_RELOADS]
   Array containing info about input reloads.  It is used to find the
   same input reload and reuse the reload pseudo in this case.  
int curr_insn_input_reloads_num
   The number of elements in the following array.  
rtx curr_insn_set
enum machine_mode curr_operand_mode[MAX_RECOG_OPERANDS]

Referenced by process_alt_operands().

struct lra_static_insn_data* curr_static_id
int curr_swapped
   True if we swapped the commutative operands in the current
int curr_usage_insns_check
   Current reload pseudo check for validity of elements in
bitmap_head ebb_global_regs
   Global registers occurring in the current EBB.  
enum reg_class goal_alt[MAX_RECOG_OPERANDS]
   The following data describe the result of process_alt_operands.
   The data are used in curr_insn_transform to generate reloads.  
   The chosen reg classes which should be used for the corresponding
int goal_alt_dont_inherit_ops[MAX_RECOG_OPERANDS]
   Numbers of operands whose reload pseudos should not be inherited.  
int goal_alt_dont_inherit_ops_num
   The number of elements in the following array.  
bool goal_alt_match_win[MAX_RECOG_OPERANDS]
   True if the operand should be the same as another operand and that
   other operand does not need a reload.  
int goal_alt_matches[MAX_RECOG_OPERANDS]
   The number of an operand to which given operand can be matched to.  
int goal_alt_number
   The chosen insn alternative.  
bool goal_alt_offmemok[MAX_RECOG_OPERANDS]
   True if the operand can be offsetable memory.  
bool goal_alt_swapped
   True if the insn commutative operands should be swapped.  
bool goal_alt_win[MAX_RECOG_OPERANDS]
   True if the operand does not need a reload.  
bitmap_head live_regs
   Check only registers living at the current program point in the
   current EBB.  
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_inheritance_iter
   Current number of inheritance/split iteration.  
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
int lra_undo_inheritance_iter
   This page contains code to undo failed inheritance/split
   Current number of iteration undoing inheritance/split.  
int new_insn_uid_start
int new_regno_start
   Start numbers for new registers and insns at the current constraints
   pass start.  

Referenced by reverse_equiv_p().

bool no_input_reloads_p
   True if the current insn should have no correspondingly input or
   output reloads.  
bool no_output_reloads_p
int reloads_num
   This page contains code to do inheritance/split
   Number of reloads passed so far in current EBB.  
bitmap_head temp_bitmap
   Used as a temporary results of some bitmap calculations.  
struct to_inherit to_inherit[LRA_MAX_INSN_RELOADS]
   Array containing all info for doing inheritance from the current
int to_inherit_num
   Number elements in the previous array.  

Referenced by split_reg().

struct usage_insns* usage_insns
   Map: regno -> corresponding pseudo usage insns.