Subversion Repositories openrisc

/* Integrated Register Allocator (IRA) intercommunication header file.

   Copyright (C) 2006, 2007, 2008, 2009, 2010

   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

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

#include "cfgloop.h"

#include "ira.h"

#include "alloc-pool.h"

/* To provide consistency in naming, all IRA external variables,

   functions, common typedefs start with prefix ira_.  */

#ifdef ENABLE_CHECKING

#define ENABLE_IRA_CHECKING

#endif

#ifdef ENABLE_IRA_CHECKING

#define ira_assert(c) gcc_assert (c)

#else

/* Always define and include C, so that warnings for empty body in an

  ‘if’ statement and unused variable do not occur.  */

#define ira_assert(c) ((void)(0 && (c)))

#endif

/* Compute register frequency from edge frequency FREQ.  It is

   analogous to REG_FREQ_FROM_BB.  When optimizing for size, or

   profile driven feedback is available and the function is never

   executed, frequency is always equivalent.  Otherwise rescale the

   edge frequency.  */

#define REG_FREQ_FROM_EDGE_FREQ(freq)                                      \

  (optimize_size || (flag_branch_probabilities && !ENTRY_BLOCK_PTR->count) \

   ? REG_FREQ_MAX : (freq * REG_FREQ_MAX / BB_FREQ_MAX)                    \

   ? (freq * REG_FREQ_MAX / BB_FREQ_MAX) : 1)

/* All natural loops.  */

extern struct loops ira_loops;

/* A modified value of flag `-fira-verbose' used internally.  */

extern int internal_flag_ira_verbose;

/* Dump file of the allocator if it is not NULL.  */

extern FILE *ira_dump_file;

/* Typedefs for pointers to allocno live range, allocno, and copy of

   allocnos.  */

typedef struct live_range *live_range_t;

typedef struct ira_allocno *ira_allocno_t;

typedef struct ira_allocno_copy *ira_copy_t;

typedef struct ira_object *ira_object_t;

/* Definition of vector of allocnos and copies.  */

DEF_VEC_P(ira_allocno_t);

DEF_VEC_ALLOC_P(ira_allocno_t, heap);

DEF_VEC_P(ira_object_t);

DEF_VEC_ALLOC_P(ira_object_t, heap);

DEF_VEC_P(ira_copy_t);

DEF_VEC_ALLOC_P(ira_copy_t, heap);

/* Typedef for pointer to the subsequent structure.  */

typedef struct ira_loop_tree_node *ira_loop_tree_node_t;

/* In general case, IRA is a regional allocator.  The regions are

   nested and form a tree.  Currently regions are natural loops.  The

   following structure describes loop tree node (representing basic

   block or loop).  We need such tree because the loop tree from

   cfgloop.h is not convenient for the optimization: basic blocks are

   not a part of the tree from cfgloop.h.  We also use the nodes for

   storing additional information about basic blocks/loops for the

   register allocation purposes.  */

struct ira_loop_tree_node

{

  /* The node represents basic block if children == NULL.  */

  basic_block bb;    /* NULL for loop.  */

  /* NULL for BB or for loop tree root if we did not build CFG loop tree.  */

  struct loop *loop;

  /* NEXT/SUBLOOP_NEXT is the next node/loop-node of the same parent.

     SUBLOOP_NEXT is always NULL for BBs.  */

  ira_loop_tree_node_t subloop_next, next;

  /* CHILDREN/SUBLOOPS is the first node/loop-node immediately inside

     the node.  They are NULL for BBs.  */

  ira_loop_tree_node_t subloops, children;

  /* The node immediately containing given node.  */

  ira_loop_tree_node_t parent;

  /* Loop level in range [0, ira_loop_tree_height).  */

  int level;

  /* All the following members are defined only for nodes representing

     loops.  */

  /* The loop number from CFG loop tree.  The root number is 0.  */

  int loop_num;

  /* True if the loop was marked for removal from the register

     allocation.  */

  bool to_remove_p;

  /* Allocnos in the loop corresponding to their regnos.  If it is

     NULL the loop does not form a separate register allocation region

     (e.g. because it has abnormal enter/exit edges and we can not put

     code for register shuffling on the edges if a different

     allocation is used for a pseudo-register on different sides of

     the edges).  Caps are not in the map (remember we can have more

     one cap with the same regno in a region).  */

  ira_allocno_t *regno_allocno_map;

  /* True if there is an entry to given loop not from its parent (or

     grandparent) basic block.  For example, it is possible for two

     adjacent loops inside another loop.  */

  bool entered_from_non_parent_p;

  /* Maximal register pressure inside loop for given register class

     (defined only for the pressure classes).  */

  int reg_pressure[N_REG_CLASSES];

  /* Numbers of allocnos referred or living in the loop node (except

     for its subloops).  */

  bitmap all_allocnos;

  /* Numbers of allocnos living at the loop borders.  */

  bitmap border_allocnos;

  /* Regnos of pseudos modified in the loop node (including its

     subloops).  */

  bitmap modified_regnos;

  /* Numbers of copies referred in the corresponding loop.  */

  bitmap local_copies;

};

/* The root of the loop tree corresponding to the all function.  */

extern ira_loop_tree_node_t ira_loop_tree_root;

/* Height of the loop tree.  */

extern int ira_loop_tree_height;

/* All nodes representing basic blocks are referred through the

   following array.  We can not use basic block member `aux' for this

   because it is used for insertion of insns on edges.  */

extern ira_loop_tree_node_t ira_bb_nodes;

/* Two access macros to the nodes representing basic blocks.  */

#if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)

#define IRA_BB_NODE_BY_INDEX(index) __extension__                       \

(({ ira_loop_tree_node_t _node = (&ira_bb_nodes[index]);                \

     if (_node->children != NULL || _node->loop != NULL || _node->bb == NULL)\

       {                                                                \

         fprintf (stderr,                                               \

                  "\n%s: %d: error in %s: it is not a block node\n",    \

                  __FILE__, __LINE__, __FUNCTION__);                    \

         gcc_unreachable ();                                            \

       }                                                                \

     _node; }))

#else

#define IRA_BB_NODE_BY_INDEX(index) (&ira_bb_nodes[index])

#endif

#define IRA_BB_NODE(bb) IRA_BB_NODE_BY_INDEX ((bb)->index)

/* All nodes representing loops are referred through the following

   array.  */

extern ira_loop_tree_node_t ira_loop_nodes;

/* Two access macros to the nodes representing loops.  */

#if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)

#define IRA_LOOP_NODE_BY_INDEX(index) __extension__                     \

(({ ira_loop_tree_node_t const _node = (&ira_loop_nodes[index]);        \

     if (_node->children == NULL || _node->bb != NULL                   \

         || (_node->loop == NULL && current_loops != NULL))             \

       {                                                                \

         fprintf (stderr,                                               \

                  "\n%s: %d: error in %s: it is not a loop node\n",     \

                  __FILE__, __LINE__, __FUNCTION__);                    \

         gcc_unreachable ();                                            \

       }                                                                \

     _node; }))

#else

#define IRA_LOOP_NODE_BY_INDEX(index) (&ira_loop_nodes[index])

#endif

#define IRA_LOOP_NODE(loop) IRA_LOOP_NODE_BY_INDEX ((loop)->num)

/* The structure describes program points where a given allocno lives.

   If the live ranges of two allocnos are intersected, the allocnos

   are in conflict.  */

struct live_range

{

  /* Object whose live range is described by given structure.  */

  ira_object_t object;

  /* Program point range.  */

  int start, finish;

  /* Next structure describing program points where the allocno

     lives.  */

  live_range_t next;

  /* Pointer to structures with the same start/finish.  */

  live_range_t start_next, finish_next;

};

/* Program points are enumerated by numbers from range

   0..IRA_MAX_POINT-1.  There are approximately two times more program

   points than insns.  Program points are places in the program where

   liveness info can be changed.  In most general case (there are more

   complicated cases too) some program points correspond to places

   where input operand dies and other ones correspond to places where

   output operands are born.  */

extern int ira_max_point;

/* Arrays of size IRA_MAX_POINT mapping a program point to the allocno

   live ranges with given start/finish point.  */

extern live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;

/* A structure representing conflict information for an allocno

   (or one of its subwords).  */

struct ira_object

{

  /* The allocno associated with this record.  */

  ira_allocno_t allocno;

  /* Vector of accumulated conflicting conflict_redords with NULL end

     marker (if OBJECT_CONFLICT_VEC_P is true) or conflict bit vector

     otherwise.  */

  void *conflicts_array;

  /* Pointer to structures describing at what program point the

     object lives.  We always maintain the list in such way that *the

     ranges in the list are not intersected and ordered by decreasing

     their program points*.  */

  live_range_t live_ranges;

  /* The subword within ALLOCNO which is represented by this object.

     Zero means the lowest-order subword (or the entire allocno in case

     it is not being tracked in subwords).  */

  int subword;

  /* Allocated size of the conflicts array.  */

  unsigned int conflicts_array_size;

  /* A unique number for every instance of this structure, which is used

     to represent it in conflict bit vectors.  */

  int id;

  /* Before building conflicts, MIN and MAX are initialized to

     correspondingly minimal and maximal points of the accumulated

     live ranges.  Afterwards, they hold the minimal and maximal ids

     of other ira_objects that this one can conflict with.  */

  int min, max;

  /* Initial and accumulated hard registers conflicting with this

     object and as a consequences can not be assigned to the allocno.

     All non-allocatable hard regs and hard regs of register classes

     different from given allocno one are included in the sets.  */

  HARD_REG_SET conflict_hard_regs, total_conflict_hard_regs;

  /* Number of accumulated conflicts in the vector of conflicting

     objects.  */

  int num_accumulated_conflicts;

  /* TRUE if conflicts are represented by a vector of pointers to

     ira_object structures.  Otherwise, we use a bit vector indexed

     by conflict ID numbers.  */

  unsigned int conflict_vec_p : 1;

};

/* A structure representing an allocno (allocation entity).  Allocno

   represents a pseudo-register in an allocation region.  If

   pseudo-register does not live in a region but it lives in the

   nested regions, it is represented in the region by special allocno

   called *cap*.  There may be more one cap representing the same

   pseudo-register in region.  It means that the corresponding

   pseudo-register lives in more one non-intersected subregion.  */

struct ira_allocno

{

  /* The allocno order number starting with 0.  Each allocno has an

     unique number and the number is never changed for the

     allocno.  */

  int num;

  /* Regno for allocno or cap.  */

  int regno;

  /* Mode of the allocno which is the mode of the corresponding

     pseudo-register.  */

  ENUM_BITFIELD (machine_mode) mode : 8;

  /* Register class which should be used for allocation for given

     allocno.  NO_REGS means that we should use memory.  */

  ENUM_BITFIELD (reg_class) aclass : 16;

  /* During the reload, value TRUE means that we should not reassign a

     hard register to the allocno got memory earlier.  It is set up

     when we removed memory-memory move insn before each iteration of

     the reload.  */

  unsigned int dont_reassign_p : 1;

#ifdef STACK_REGS

  /* Set to TRUE if allocno can't be assigned to the stack hard

     register correspondingly in this region and area including the

     region and all its subregions recursively.  */

  unsigned int no_stack_reg_p : 1, total_no_stack_reg_p : 1;

#endif

  /* TRUE value means that there is no sense to spill the allocno

     during coloring because the spill will result in additional

     reloads in reload pass.  */

  unsigned int bad_spill_p : 1;

  /* TRUE if a hard register or memory has been assigned to the

     allocno.  */

  unsigned int assigned_p : 1;

  /* TRUE if conflicts for given allocno are represented by vector of

     pointers to the conflicting allocnos.  Otherwise, we use a bit

     vector where a bit with given index represents allocno with the

     same number.  */

  unsigned int conflict_vec_p : 1;

  /* Hard register assigned to given allocno.  Negative value means

     that memory was allocated to the allocno.  During the reload,

     spilled allocno has value equal to the corresponding stack slot

     number (0, ...) - 2.  Value -1 is used for allocnos spilled by the

     reload (at this point pseudo-register has only one allocno) which

     did not get stack slot yet.  */

  short int hard_regno;

  /* Allocnos with the same regno are linked by the following member.

     Allocnos corresponding to inner loops are first in the list (it

     corresponds to depth-first traverse of the loops).  */

  ira_allocno_t next_regno_allocno;

  /* There may be different allocnos with the same regno in different

     regions.  Allocnos are bound to the corresponding loop tree node.

     Pseudo-register may have only one regular allocno with given loop

     tree node but more than one cap (see comments above).  */

  ira_loop_tree_node_t loop_tree_node;

  /* Accumulated usage references of the allocno.  Here and below,

     word 'accumulated' means info for given region and all nested

     subregions.  In this case, 'accumulated' means sum of references

     of the corresponding pseudo-register in this region and in all

     nested subregions recursively. */

  int nrefs;

  /* Accumulated frequency of usage of the allocno.  */

  int freq;

  /* Minimal accumulated and updated costs of usage register of the

     allocno class.  */

  int class_cost, updated_class_cost;

  /* Minimal accumulated, and updated costs of memory for the allocno.

     At the allocation start, the original and updated costs are

     equal.  The updated cost may be changed after finishing

     allocation in a region and starting allocation in a subregion.

     The change reflects the cost of spill/restore code on the

     subregion border if we assign memory to the pseudo in the

     subregion.  */

  int memory_cost, updated_memory_cost;

  /* Accumulated number of points where the allocno lives and there is

     excess pressure for its class.  Excess pressure for a register

     class at some point means that there are more allocnos of given

     register class living at the point than number of hard-registers

     of the class available for the allocation.  */

  int excess_pressure_points_num;

  /* Copies to other non-conflicting allocnos.  The copies can

     represent move insn or potential move insn usually because of two

     operand insn constraints.  */

  ira_copy_t allocno_copies;

  /* It is a allocno (cap) representing given allocno on upper loop tree

     level.  */

  ira_allocno_t cap;

  /* It is a link to allocno (cap) on lower loop level represented by

     given cap.  Null if given allocno is not a cap.  */

  ira_allocno_t cap_member;

  /* The number of objects tracked in the following array.  */

  int num_objects;

  /* An array of structures describing conflict information and live

     ranges for each object associated with the allocno.  There may be

     more than one such object in cases where the allocno represents a

     multi-word register.  */

  ira_object_t objects[2];

  /* Accumulated frequency of calls which given allocno

     intersects.  */

  int call_freq;

  /* Accumulated number of the intersected calls.  */

  int calls_crossed_num;

  /* Array of usage costs (accumulated and the one updated during

     coloring) for each hard register of the allocno class.  The

     member value can be NULL if all costs are the same and equal to

     CLASS_COST.  For example, the costs of two different hard

     registers can be different if one hard register is callee-saved

     and another one is callee-used and the allocno lives through

     calls.  Another example can be case when for some insn the

     corresponding pseudo-register value should be put in specific

     register class (e.g. AREG for x86) which is a strict subset of

     the allocno class (GENERAL_REGS for x86).  We have updated costs

     to reflect the situation when the usage cost of a hard register

     is decreased because the allocno is connected to another allocno

     by a copy and the another allocno has been assigned to the hard

     register.  */

  int *hard_reg_costs, *updated_hard_reg_costs;

  /* Array of decreasing costs (accumulated and the one updated during

     coloring) for allocnos conflicting with given allocno for hard

     regno of the allocno class.  The member value can be NULL if all

     costs are the same.  These costs are used to reflect preferences

     of other allocnos not assigned yet during assigning to given

     allocno.  */

  int *conflict_hard_reg_costs, *updated_conflict_hard_reg_costs;

  /* Different additional data.  It is used to decrease size of

     allocno data footprint.  */

  void *add_data;

};

/* All members of the allocno structures should be accessed only

   through the following macros.  */

#define ALLOCNO_NUM(A) ((A)->num)

#define ALLOCNO_REGNO(A) ((A)->regno)

#define ALLOCNO_REG(A) ((A)->reg)

#define ALLOCNO_NEXT_REGNO_ALLOCNO(A) ((A)->next_regno_allocno)

#define ALLOCNO_LOOP_TREE_NODE(A) ((A)->loop_tree_node)

#define ALLOCNO_CAP(A) ((A)->cap)

#define ALLOCNO_CAP_MEMBER(A) ((A)->cap_member)

#define ALLOCNO_NREFS(A) ((A)->nrefs)

#define ALLOCNO_FREQ(A) ((A)->freq)

#define ALLOCNO_HARD_REGNO(A) ((A)->hard_regno)

#define ALLOCNO_CALL_FREQ(A) ((A)->call_freq)

#define ALLOCNO_CALLS_CROSSED_NUM(A) ((A)->calls_crossed_num)

#define ALLOCNO_MEM_OPTIMIZED_DEST(A) ((A)->mem_optimized_dest)

#define ALLOCNO_MEM_OPTIMIZED_DEST_P(A) ((A)->mem_optimized_dest_p)

#define ALLOCNO_SOMEWHERE_RENAMED_P(A) ((A)->somewhere_renamed_p)

#define ALLOCNO_CHILD_RENAMED_P(A) ((A)->child_renamed_p)

#define ALLOCNO_DONT_REASSIGN_P(A) ((A)->dont_reassign_p)

#ifdef STACK_REGS

#define ALLOCNO_NO_STACK_REG_P(A) ((A)->no_stack_reg_p)

#define ALLOCNO_TOTAL_NO_STACK_REG_P(A) ((A)->total_no_stack_reg_p)

#endif

#define ALLOCNO_BAD_SPILL_P(A) ((A)->bad_spill_p)

#define ALLOCNO_ASSIGNED_P(A) ((A)->assigned_p)

#define ALLOCNO_MODE(A) ((A)->mode)

#define ALLOCNO_COPIES(A) ((A)->allocno_copies)

#define ALLOCNO_HARD_REG_COSTS(A) ((A)->hard_reg_costs)

#define ALLOCNO_UPDATED_HARD_REG_COSTS(A) ((A)->updated_hard_reg_costs)

#define ALLOCNO_CONFLICT_HARD_REG_COSTS(A) \

  ((A)->conflict_hard_reg_costs)

#define ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS(A) \

  ((A)->updated_conflict_hard_reg_costs)

#define ALLOCNO_CLASS(A) ((A)->aclass)

#define ALLOCNO_CLASS_COST(A) ((A)->class_cost)

#define ALLOCNO_UPDATED_CLASS_COST(A) ((A)->updated_class_cost)

#define ALLOCNO_MEMORY_COST(A) ((A)->memory_cost)

#define ALLOCNO_UPDATED_MEMORY_COST(A) ((A)->updated_memory_cost)

#define ALLOCNO_EXCESS_PRESSURE_POINTS_NUM(A) \

  ((A)->excess_pressure_points_num)

#define ALLOCNO_OBJECT(A,N) ((A)->objects[N])

#define ALLOCNO_NUM_OBJECTS(A) ((A)->num_objects)

#define ALLOCNO_ADD_DATA(A) ((A)->add_data)

/* Typedef for pointer to the subsequent structure.  */

typedef struct ira_emit_data *ira_emit_data_t;

/* Allocno bound data used for emit pseudo live range split insns and

   to flattening IR.  */

struct ira_emit_data

{

  /* TRUE if the allocno assigned to memory was a destination of

     removed move (see ira-emit.c) at loop exit because the value of

     the corresponding pseudo-register is not changed inside the

     loop.  */

  unsigned int mem_optimized_dest_p : 1;

  /* TRUE if the corresponding pseudo-register has disjoint live

     ranges and the other allocnos of the pseudo-register except this

     one changed REG.  */

  unsigned int somewhere_renamed_p : 1;

  /* TRUE if allocno with the same REGNO in a subregion has been

     renamed, in other words, got a new pseudo-register.  */

  unsigned int child_renamed_p : 1;

  /* Final rtx representation of the allocno.  */

  rtx reg;

  /* Non NULL if we remove restoring value from given allocno to

     MEM_OPTIMIZED_DEST at loop exit (see ira-emit.c) because the

     allocno value is not changed inside the loop.  */

  ira_allocno_t mem_optimized_dest;

};

#define ALLOCNO_EMIT_DATA(a) ((ira_emit_data_t) ALLOCNO_ADD_DATA (a))

/* Data used to emit live range split insns and to flattening IR.  */

extern ira_emit_data_t ira_allocno_emit_data;

/* Abbreviation for frequent emit data access.  */

static inline rtx

allocno_emit_reg (ira_allocno_t a)

{

  return ALLOCNO_EMIT_DATA (a)->reg;

}

#define OBJECT_ALLOCNO(O) ((O)->allocno)

#define OBJECT_SUBWORD(O) ((O)->subword)

#define OBJECT_CONFLICT_ARRAY(O) ((O)->conflicts_array)

#define OBJECT_CONFLICT_VEC(O) ((ira_object_t *)(O)->conflicts_array)

#define OBJECT_CONFLICT_BITVEC(O) ((IRA_INT_TYPE *)(O)->conflicts_array)

#define OBJECT_CONFLICT_ARRAY_SIZE(O) ((O)->conflicts_array_size)

#define OBJECT_CONFLICT_VEC_P(O) ((O)->conflict_vec_p)

#define OBJECT_NUM_CONFLICTS(O) ((O)->num_accumulated_conflicts)

#define OBJECT_CONFLICT_HARD_REGS(O) ((O)->conflict_hard_regs)

#define OBJECT_TOTAL_CONFLICT_HARD_REGS(O) ((O)->total_conflict_hard_regs)

#define OBJECT_MIN(O) ((O)->min)

#define OBJECT_MAX(O) ((O)->max)

#define OBJECT_CONFLICT_ID(O) ((O)->id)

#define OBJECT_LIVE_RANGES(O) ((O)->live_ranges)

/* Map regno -> allocnos with given regno (see comments for

   allocno member `next_regno_allocno').  */

extern ira_allocno_t *ira_regno_allocno_map;

/* Array of references to all allocnos.  The order number of the

   allocno corresponds to the index in the array.  Removed allocnos

   have NULL element value.  */

extern ira_allocno_t *ira_allocnos;

/* The size of the previous array.  */

extern int ira_allocnos_num;

/* Map a conflict id to its corresponding ira_object structure.  */

extern ira_object_t *ira_object_id_map;

/* The size of the previous array.  */

extern int ira_objects_num;

/* The following structure represents a copy of two allocnos.  The

   copies represent move insns or potential move insns usually because

   of two operand insn constraints.  To remove register shuffle, we

   also create copies between allocno which is output of an insn and

   allocno becoming dead in the insn.  */

struct ira_allocno_copy

{

  /* The unique order number of the copy node starting with 0.  */

  int num;

  /* Allocnos connected by the copy.  The first allocno should have

     smaller order number than the second one.  */

  ira_allocno_t first, second;

  /* Execution frequency of the copy.  */

  int freq;

  bool constraint_p;

  /* It is a move insn which is an origin of the copy.  The member

     value for the copy representing two operand insn constraints or

     for the copy created to remove register shuffle is NULL.  In last

     case the copy frequency is smaller than the corresponding insn

     execution frequency.  */

  rtx insn;

  /* All copies with the same allocno as FIRST are linked by the two

     following members.  */

  ira_copy_t prev_first_allocno_copy, next_first_allocno_copy;

  /* All copies with the same allocno as SECOND are linked by the two

     following members.  */

  ira_copy_t prev_second_allocno_copy, next_second_allocno_copy;

  /* Region from which given copy is originated.  */

  ira_loop_tree_node_t loop_tree_node;

};

/* Array of references to all copies.  The order number of the copy

   corresponds to the index in the array.  Removed copies have NULL

   element value.  */

extern ira_copy_t *ira_copies;

/* Size of the previous array.  */

extern int ira_copies_num;

/* The following structure describes a stack slot used for spilled

   pseudo-registers.  */

struct ira_spilled_reg_stack_slot

{

  /* pseudo-registers assigned to the stack slot.  */

  bitmap_head spilled_regs;

  /* RTL representation of the stack slot.  */

  rtx mem;

  /* Size of the stack slot.  */

  unsigned int width;

};

/* The number of elements in the following array.  */

extern int ira_spilled_reg_stack_slots_num;

/* The following array contains info about spilled pseudo-registers

   stack slots used in current function so far.  */

extern struct ira_spilled_reg_stack_slot *ira_spilled_reg_stack_slots;

/* Correspondingly overall cost of the allocation, cost of the

   allocnos assigned to hard-registers, cost of the allocnos assigned

   to memory, cost of loads, stores and register move insns generated

   for pseudo-register live range splitting (see ira-emit.c).  */

extern int ira_overall_cost;

extern int ira_reg_cost, ira_mem_cost;

extern int ira_load_cost, ira_store_cost, ira_shuffle_cost;

extern int ira_move_loops_num, ira_additional_jumps_num;

/* This page contains a bitset implementation called 'min/max sets' used to

   record conflicts in IRA.

   They are named min/maxs set since we keep track of a minimum and a maximum

   bit number for each set representing the bounds of valid elements.  Otherwise,

   the implementation resembles sbitmaps in that we store an array of integers

   whose bits directly represent the members of the set.  */

/* The type used as elements in the array, and the number of bits in

   this type.  */

#define IRA_INT_BITS HOST_BITS_PER_WIDE_INT

#define IRA_INT_TYPE HOST_WIDE_INT

/* Set, clear or test bit number I in R, a bit vector of elements with

   minimal index and maximal index equal correspondingly to MIN and

   MAX.  */

#if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)

#define SET_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__                \

  (({ int _min = (MIN), _max = (MAX), _i = (I);                         \

     if (_i < _min || _i > _max)                                        \

       {                                                                \

         fprintf (stderr,                                               \

                  "\n%s: %d: error in %s: %d not in range [%d,%d]\n",   \

                  __FILE__, __LINE__, __FUNCTION__, _i, _min, _max);    \

         gcc_unreachable ();                                            \

       }                                                                \

     ((R)[(unsigned) (_i - _min) / IRA_INT_BITS]                        \

      |= ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); }))

#define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__              \

  (({ int _min = (MIN), _max = (MAX), _i = (I);                         \

     if (_i < _min || _i > _max)                                        \

       {                                                                \

         fprintf (stderr,                                               \

                  "\n%s: %d: error in %s: %d not in range [%d,%d]\n",   \

                  __FILE__, __LINE__, __FUNCTION__, _i, _min, _max);    \

         gcc_unreachable ();                                            \

       }                                                                \

     ((R)[(unsigned) (_i - _min) / IRA_INT_BITS]                        \

      &= ~((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); }))

#define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__               \

  (({ int _min = (MIN), _max = (MAX), _i = (I);                         \

     if (_i < _min || _i > _max)                                        \

       {                                                                \

         fprintf (stderr,                                               \

                  "\n%s: %d: error in %s: %d not in range [%d,%d]\n",   \

                  __FILE__, __LINE__, __FUNCTION__, _i, _min, _max);    \

         gcc_unreachable ();                                            \

       }                                                                \

     ((R)[(unsigned) (_i - _min) / IRA_INT_BITS]                        \

      & ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); }))

#else

#define SET_MINMAX_SET_BIT(R, I, MIN, MAX)                      \

  ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS]                 \

   |= ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS)))

#define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX)                    \

  ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS]                 \

   &= ~((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS)))

#define TEST_MINMAX_SET_BIT(R, I, MIN, MAX)                     \

  ((R)[(unsigned) ((I) - (MIN)) / IRA_INT_BITS]                 \

   & ((IRA_INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % IRA_INT_BITS)))

#endif

/* The iterator for min/max sets.  */

typedef struct {

  /* Array containing the bit vector.  */

  IRA_INT_TYPE *vec;

  /* The number of the current element in the vector.  */

  unsigned int word_num;

  /* The number of bits in the bit vector.  */

  unsigned int nel;

  /* The current bit index of the bit vector.  */

  unsigned int bit_num;

  /* Index corresponding to the 1st bit of the bit vector.   */

  int start_val;

  /* The word of the bit vector currently visited.  */

  unsigned IRA_INT_TYPE word;

} minmax_set_iterator;

/* Initialize the iterator I for bit vector VEC containing minimal and

   maximal values MIN and MAX.  */

static inline void

minmax_set_iter_init (minmax_set_iterator *i, IRA_INT_TYPE *vec, int min,

                      int max)

{

  i->vec = vec;

  i->word_num = 0;

  i->nel = max < min ? 0 : max - min + 1;

  i->start_val = min;

  i->bit_num = 0;

  i->word = i->nel == 0 ? 0 : vec[0];

}

/* Return TRUE if we have more allocnos to visit, in which case *N is

   set to the number of the element to be visited.  Otherwise, return

   FALSE.  */

static inline bool

minmax_set_iter_cond (minmax_set_iterator *i, int *n)

{

  /* Skip words that are zeros.  */

  for (; i->word == 0; i->word = i->vec[i->word_num])

    {

      i->word_num++;

      i->bit_num = i->word_num * IRA_INT_BITS;

      /* If we have reached the end, break.  */

      if (i->bit_num >= i->nel)

        return false;

    }

  /* Skip bits that are zero.  */

  for (; (i->word & 1) == 0; i->word >>= 1)

    i->bit_num++;

  *n = (int) i->bit_num + i->start_val;

  return true;

}

/* Advance to the next element in the set.  */

static inline void

minmax_set_iter_next (minmax_set_iterator *i)

{

  i->word >>= 1;

  i->bit_num++;

}

/* Loop over all elements of a min/max set given by bit vector VEC and

   their minimal and maximal values MIN and MAX.  In each iteration, N

   is set to the number of next allocno.  ITER is an instance of

   minmax_set_iterator used to iterate over the set.  */

#define FOR_EACH_BIT_IN_MINMAX_SET(VEC, MIN, MAX, N, ITER)      \

  for (minmax_set_iter_init (&(ITER), (VEC), (MIN), (MAX));     \

       minmax_set_iter_cond (&(ITER), &(N));                    \

       minmax_set_iter_next (&(ITER)))

struct target_ira_int {

  /* Initialized once.  It is a maximal possible size of the allocated

     struct costs.  */

  int x_max_struct_costs_size;

  /* Allocated and initialized once, and used to initialize cost values

     for each insn.  */

  struct costs *x_init_cost;

  /* Allocated once, and used for temporary purposes.  */

  struct costs *x_temp_costs;

  /* Allocated once, and used for the cost calculation.  */

  struct costs *x_op_costs[MAX_RECOG_OPERANDS];

  struct costs *x_this_op_costs[MAX_RECOG_OPERANDS];

  /* Hard registers that can not be used for the register allocator for

     all functions of the current compilation unit.  */

  HARD_REG_SET x_no_unit_alloc_regs;

  /* Map: hard regs X modes -> set of hard registers for storing value

     of given mode starting with given hard register.  */