GCC Middle and Back End API Reference
ira-emit.c File Reference

Data Structures

struct  move


typedef void * void_p
typedef struct movemove_t


void ira_initiate_emit_data ()
void ira_finish_emit_data ()
static ira_allocno_t create_new_allocno ()
static move_t create_move ()
static void free_move ()
static void free_move_list ()
static bool eq_move_lists_p ()
static void print_move_list ()
void ira_debug_move_list (move_t list)
void ira_debug_move_list ()
static bool change_regs ()
static void add_to_edge_list ()
rtx ira_create_new_reg ()
static bool subloop_tree_node_p ()
static void set_allocno_reg ()
static bool entered_from_non_parent_p ()
static void setup_entered_from_non_parent_p ()
static bool store_can_be_removed_p ()
static void generate_edge_moves ()
static void change_loop ()
static void set_allocno_somewhere_renamed_p ()
static bool eq_edge_move_lists_p ()
static void unify_moves ()
static void traverse_moves ()
static move_t modify_move_list ()
static rtx emit_move_list ()
static void emit_moves ()
static void update_costs ()
static void add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node, bitmap live_through, int freq)
static void add_ranges_and_copies ()
void ira_emit ()


ira_emit_data_t ira_allocno_emit_data
static vec< void_pnew_allocno_emit_data_vec
static move_tat_bb_start
static move_tat_bb_end
static int max_regno_before_changing
static bitmap local_allocno_bitmap
static bitmap used_regno_bitmap
static bitmap renamed_regno_bitmap
static move_t hard_regno_last_set [FIRST_PSEUDO_REGISTER]
static int hard_regno_last_set_check [FIRST_PSEUDO_REGISTER]
static move_tallocno_last_set
static int * allocno_last_set_check
static vec< move_tmove_vec
static int curr_tick

Typedef Documentation

typedef struct move* move_t
   See comments below.  
typedef void* void_p
   Definitions for vectors of pointers.  

Function Documentation

static void add_range_and_copies_from_move_list ( move_t  list,
ira_loop_tree_node_t  node,
bitmap  live_through,
int  freq 
   Process moves from LIST with execution FREQ to add ranges, copies,
   and modify costs for allocnos involved in the moves.  All regnos
   living through the list is in LIVE_THROUGH, and the loop tree node
   used to find corresponding allocnos is NODE.  
     This is a trick to guarantee that new ranges is not merged with
     the old ones.  
static void add_ranges_and_copies ( )
   Process all move list to add ranges, conflicts, copies, and modify
   costs for allocnos involved in the moves.  
         It does not matter what loop_tree_node (of source or
         destination block) to use for searching allocnos by their
         regnos because of subsequent IR flattening.  

References free_move_list().

static void add_to_edge_list ( )
   Attach MOVE to the edge E.  The move is attached to the head of the
   list if HEAD_P is TRUE.  
static void change_loop ( )
   Change (if necessary) pseudo-registers inside loop given by loop
   tree node NODE.  
             We generate the same hard register move because the
             reload pass can put an allocno into memory in this case
             we will have live range splitting.  If it does not happen
             such the same hard register moves will be removed.  The
             worst case when the both allocnos are put into memory by
             the reload is very rare.  
                     don't create copies because reload can spill an
                     allocno set by copy although the allocno will not
                     get memory slot.  
     Rename locals: Local allocnos with same regno in different loops
     might get the different hard register.  So we need to change
static bool change_regs ( )
   This recursive function changes pseudo-registers in *LOC if it is
   necessary.  The function returns TRUE if a change was done.  
           It is a shared register which was changed already.  
static move_t create_move ( )
   Return new move of allocnos TO and FROM.  

Referenced by modify_move_list().

static ira_allocno_t create_new_allocno ( )
   Create and return a new allocno with given REGNO and
   LOOP_TREE_NODE.  Allocate emit data for it.  

Referenced by modify_move_list().

static rtx emit_move_list ( )
   Generate RTX move insns from the move list LIST.  This updates
   allocation cost using move execution frequency FREQ.  
             The reload needs to have set up insn codes.  If the
             reload sets up insn codes by itself, it may fail because
             insns will have hard registers instead of pseudos and
             there may be no machine insn with given hard
             Add insn to equiv init insn list if it is necessary.
             Otherwise reload will not remove this insn if it decides
             to use the equivalence.  

References ira_load_cost.

static void emit_moves ( )
   Generate RTX move insns from move lists attached to basic blocks
   and edges.  
static bool entered_from_non_parent_p ( )
   Return true if there is an entry to given loop not from its parent
   (or grandparent) block.  For example, it is possible for two
   adjacent loops inside another loop.  
                   That is an exit from a nested loop -- skip it.  
static bool eq_edge_move_lists_p ( )
   Return TRUE if move lists on all edges given in vector VEC are
static bool eq_move_lists_p ( )
   Return TRUE if the move list LIST1 and LIST2 are equal (two
   moves are equal if they involve the same allocnos).  

References print_move_list().

static void free_move ( )
   Free memory for MOVE and its dependencies.  

References move::from, move::next, and move::to.

static void free_move_list ( )
   Free memory for list of the moves given by its HEAD.  

Referenced by add_ranges_and_copies(), and set_allocno_somewhere_renamed_p().

static void generate_edge_moves ( )
   Generate and attach moves to the edge E.  This looks at the final
   regnos of allocnos living on the edge with the same original regno
   to figure out when moves should be generated.  
           Remove unnecessary stores at the region exit.  We should do
           this for readonly memory for sure and this is guaranteed by
           that we never generate moves on region borders (see
           checking in function change_loop).  
rtx ira_create_new_reg ( )
   Create and return new pseudo-register with the same attributes as

References ira_regno_allocno_map, and subloop_tree_node_p().

Referenced by modify_move_list().

void ira_debug_move_list ( move_t  list)
void ira_debug_move_list ( )
   Print move list LIST into stderr.  
void ira_emit ( )
   The entry function changes code and generates shuffling allocnos on
   region borders for the regional (LOOPS_P is TRUE in this case)
   register allocation.  
     Clean up: 
     Fix insn codes.  It is necessary to do it before reload because
     reload assumes initial insn codes defined.  The insn codes can be
     invalidated by CFG infrastructure for example in jump

Referenced by split_live_ranges_for_shrink_wrap().

void ira_finish_emit_data ( void  )
   Free the emit data.  

References ira_free().

void ira_initiate_emit_data ( void  )
   Allocate and initiate the emit data.  

Referenced by split_live_ranges_for_shrink_wrap().

static move_t modify_move_list ( )
   Remove unnecessary moves in the LIST, makes topological sorting,
   and removes cycles on hard reg dependencies by introducing new
   allocnos assigned to memory and additional moves.  It returns the
   result move list.  
     Creat move deps.  
     Toplogical sorting:  
     Removing cycles:  
                   It does not matter what loop_tree_node (of TO or
                   FROM) to use for the new allocno because of
                   subsequent IRA internal representation
                   Make it possibly conflicting with all earlier
                   created allocnos.  Cases where temporary allocnos
                   created to remove the cycles are quite rare.  

References allocno_emit_reg(), create_move(), create_new_allocno(), curr_tick, move::from, internal_flag_ira_verbose, ira_create_allocno_objects(), ira_create_new_reg(), ira_dump_file, ira_move_loops_num, ira_objects_num, ira_set_allocno_class(), and move::to.

static void print_move_list ( )
   Print move list LIST into file F.  

Referenced by eq_move_lists_p().

static void set_allocno_reg ( )
   Set up member `reg' to REG for allocnos which has the same regno as
   ALLOCNO and which are inside the loop corresponding to ALLOCNO. 
static void set_allocno_somewhere_renamed_p ( )
   Process to set up flag somewhere_renamed_p.  

References edge_def::aux, and free_move_list().

static void setup_entered_from_non_parent_p ( )
   Set up ENTERED_FROM_NON_PARENT_P for each loop region.  
static bool store_can_be_removed_p ( )
   Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
   DEST_ALLOCNO (assigned to memory) can be removed because it does
   not change value of the destination.  One possible reason for this
   is the situation when SRC_ALLOCNO is not modified in the
   corresponding loop.  
           We achieved the destination and everything is ok.  
           If there is a path from a destination loop block to the
           source loop header containing basic blocks of non-parents
           (grandparents) of the source loop, we should have checked
           modifications of the pseudo on this path too to decide
           about possibility to remove the store.  It could be done by
           solving a data-flow problem.  Unfortunately such global
           solution would complicate IR flattening.  Therefore we just
           prohibit removal of the store in such complicated case.  
     It is actually a loop entry -- do not remove the store.  
static bool subloop_tree_node_p ( )
   Return TRUE if loop given by SUBNODE inside the loop given by

References ira_loop_tree_node::parent, and ira_loop_tree_node::regno_allocno_map.

Referenced by ira_create_new_reg().

static void traverse_moves ( )
   This recursive function traverses dependencies of MOVE and produces
   topological sorting (in depth-first order).  

Referenced by unify_moves().

static void unify_moves ( )
   Look at all entry edges (if START_P) or exit edges of basic block
   BB and put move lists at the BB start or end if it is possible.  In
   other words, this decreases code duplication of allocno moves.  

References move::deps, move::deps_num, traverse_moves(), and move::visited_p.

static void update_costs ( )
   Update costs of A and corresponding allocnos on upper levels on the
   loop tree from reading (if READ_P) or writing A on an execution
   path with FREQ.  

Variable Documentation

move_t* allocno_last_set
   Last move (in move sequence being processed) setting up the
   corresponding allocno.  
int* allocno_last_set_check
   If the element value is equal to CURR_TICK then the corresponding
   element in . `allocno_last_set' is defined and correct.  
move_t * at_bb_end
move_t* at_bb_start
   Array of moves (indexed by BB index) which should be put at the
   start/end of the corresponding basic blocks.  
int curr_tick
   The variable value is used to check correctness of values of
   elements of arrays `hard_regno_last_set' and

Referenced by modify_move_list().

move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER]
   Last move (in move sequence being processed) setting up the
   corresponding hard register.  
int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER]
   If the element value is equal to CURR_TICK then the corresponding
   element in `hard_regno_last_set' is defined and correct.  
ira_emit_data_t ira_allocno_emit_data

Integrated Register Allocator. Changing code and generating moves. Copyright (C) 2006-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/.

   When we have more one region, we need to change the original RTL
   code after coloring.  Let us consider two allocnos representing the
   same pseudo-register outside and inside a region respectively.
   They can get different hard-registers.  The reload pass works on
   pseudo registers basis and there is no way to say the reload that
   pseudo could be in different registers and it is even more
   difficult to say in what places of the code the pseudo should have
   particular hard-registers.  So in this case IRA has to create and
   use a new pseudo-register inside the region and adds code to move
   allocno values on the region's borders.  This is done by the code
   in this file.

   The code makes top-down traversal of the regions and generate new
   pseudos and the move code on the region borders.  In some
   complicated cases IRA can create a new pseudo used temporarily to
   move allocno values when a swap of values stored in two
   hard-registers is needed (e.g. two allocnos representing different
   pseudos outside region got respectively hard registers 1 and 2 and
   the corresponding allocnos inside the region got respectively hard
   registers 2 and 1).  At this stage, the new pseudo is marked as

   IRA still creates the pseudo-register and the moves on the region
   borders even when the both corresponding allocnos were assigned to
   the same hard-register.  It is done because, if the reload pass for
   some reason spills a pseudo-register representing the original
   pseudo outside or inside the region, the effect will be smaller
   because another pseudo will still be in the hard-register.  In most
   cases, this is better then spilling the original pseudo in its
   whole live-range.  If reload does not change the allocation for the
   two pseudo-registers, the trivial move will be removed by
   post-reload optimizations.

   IRA does not generate a new pseudo and moves for the allocno values
   if the both allocnos representing an original pseudo inside and
   outside region assigned to the same hard register when the register
   pressure in the region for the corresponding pressure class is less
   than number of available hard registers for given pressure class.

   IRA also does some optimizations to remove redundant moves which is
   transformed into stores by the reload pass on CFG edges
   representing exits from the region.

   IRA tries to reduce duplication of code generated on CFG edges
   which are enters and exits to/from regions by moving some code to
   the edge sources or destinations when it is possible.  
   Data used to emit live range split insns and to flattening IR.  
bitmap local_allocno_bitmap
   Bitmap of allocnos local for the current loop.  
int max_regno_before_changing
   Max regno before renaming some pseudo-registers.  For example, the
   same pseudo-register can be renamed in a loop if its allocation is
   different outside the loop.  
vec<move_t> move_vec
   Definition of vector of moves.  
   This vec contains moves sorted topologically (depth-first) on their
   dependency graph.  
vec<void_p> new_allocno_emit_data_vec
   Pointers to data allocated for allocnos being created during
   emitting.  Usually there are quite few such allocnos because they
   are created only for resolving loop in register shuffling.  
bitmap renamed_regno_bitmap
   This bitmap contains regnos of allocnos which were renamed locally
   because the allocnos correspond to disjoint live ranges in loops
   with a common parent.  
bitmap used_regno_bitmap
   This bitmap is used to find that we need to generate and to use a
   new pseudo-register when processing allocnos with the same original