/* Typedefs for pointers to allocno live range, allocno, and copy of
allocnos. */
-typedef struct ira_allocno_live_range *allocno_live_range_t;
+typedef struct live_range *live_range_t;
typedef struct ira_allocno *ira_allocno_t;
typedef struct ira_allocno_copy *ira_copy_t;
conflicts for other allocnos (e.g. to assign stack memory slot) we
use the live ranges. If the live ranges of two allocnos are
intersected, the allocnos are in conflict. */
-struct ira_allocno_live_range
+struct live_range
{
/* Allocno whose live range is described by given structure. */
ira_allocno_t allocno;
int start, finish;
/* Next structure describing program points where the allocno
lives. */
- allocno_live_range_t next;
+ live_range_t next;
/* Pointer to structures with the same start/finish. */
- allocno_live_range_t start_next, finish_next;
+ live_range_t start_next, finish_next;
};
/* Program points are enumerated by numbers from range
/* Arrays of size IRA_MAX_POINT mapping a program point to the allocno
live ranges with given start/finish point. */
-extern allocno_live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
+extern live_range_t *ira_start_point_ranges, *ira_finish_point_ranges;
/* A structure representing an allocno (allocation entity). Allocno
represents a pseudo-register in an allocation region. If
allocno 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*. */
- allocno_live_range_t live_ranges;
+ live_range_t live_ranges;
/* Before building conflicts the two member values are
correspondingly minimal and maximal points of the accumulated
allocno live ranges. After building conflicts the values are
preferences of other allocnos not assigned yet during assigning
to given allocno. */
int *conflict_hard_reg_costs, *updated_conflict_hard_reg_costs;
- /* Number of the same cover class allocnos with TRUE in_graph_p
- value and conflicting with given allocno during each point of
- graph coloring. */
- int left_conflicts_num;
+ /* Size (in hard registers) of the same cover class allocnos with
+ TRUE in_graph_p value and conflicting with given allocno during
+ each point of graph coloring. */
+ int left_conflicts_size;
/* Number of hard registers of the allocno cover class really
available for the allocno allocation. */
int available_regs_num;
((A)->conflict_hard_reg_costs)
#define ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS(A) \
((A)->updated_conflict_hard_reg_costs)
-#define ALLOCNO_LEFT_CONFLICTS_NUM(A) ((A)->left_conflicts_num)
+#define ALLOCNO_LEFT_CONFLICTS_SIZE(A) ((A)->left_conflicts_size)
#define ALLOCNO_COVER_CLASS(A) ((A)->cover_class)
#define ALLOCNO_COVER_CLASS_COST(A) ((A)->cover_class_cost)
#define ALLOCNO_UPDATED_COVER_CLASS_COST(A) ((A)->updated_cover_class_cost)
#define ALLOCNO_MAX(A) ((A)->max)
#define ALLOCNO_CONFLICT_ID(A) ((A)->conflict_id)
-/* Map regno -> allocnos with given regno (see comments for
+/* Map regno -> allocnos with given regno (see comments for
allocno member `next_regno_allocno'). */
extern ira_allocno_t *ira_regno_allocno_map;
struct ira_spilled_reg_stack_slot
{
/* pseudo-registers assigned to the stack slot. */
- regset_head spilled_regs;
+ bitmap_head spilled_regs;
/* RTL representation of the stack slot. */
rtx mem;
/* Size of the stack slot. */
extern int ira_load_cost, ira_store_cost, ira_shuffle_cost;
extern int ira_move_loops_num, ira_additional_jumps_num;
-/* Map: hard register number -> cover class it belongs to. If the
- corresponding class is NO_REGS, the hard register is not available
- for allocation. */
-extern enum reg_class ira_hard_regno_cover_class[FIRST_PSEUDO_REGISTER];
-
-/* Map: register class x machine mode -> number of hard registers of
- given class needed to store value of given mode. If the number for
- some hard-registers of the register class is different, the size
- will be negative. */
-extern int ira_reg_class_nregs[N_REG_CLASSES][MAX_MACHINE_MODE];
-
-/* Maximal value of the previous array elements. */
+/* Maximal value of element of array ira_reg_class_nregs. */
extern int ira_max_nregs;
-
-/* The number of bits in each element of array used to implement a bit
- vector of allocnos and what type that element has. We use the
- largest integer format on the host machine. */
+\f
+/* 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
MAX. */
#if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)
-#define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
+#define SET_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \
(({ int _min = (MIN), _max = (MAX), _i = (I); \
if (_i < _min || _i > _max) \
{ \
} \
((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \
|= ((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); }))
-
-#define CLEAR_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
+
+#define CLEAR_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \
(({ int _min = (MIN), _max = (MAX), _i = (I); \
if (_i < _min || _i > _max) \
{ \
((R)[(unsigned) (_i - _min) / IRA_INT_BITS] \
&= ~((IRA_INT_TYPE) 1 << ((unsigned) (_i - _min) % IRA_INT_BITS))); }))
-#define TEST_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
+#define TEST_MINMAX_SET_BIT(R, I, MIN, MAX) __extension__ \
(({ int _min = (MIN), _max = (MAX), _i = (I); \
if (_i < _min || _i > _max) \
{ \
#else
-#define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
+#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_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
+#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_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
+#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 allocno set implemented ed as allocno bit
- vector. */
+/* The iterator for min/max sets. */
typedef struct {
- /* Array containing the allocno bit vector. */
+ /* Array containing the bit vector. */
IRA_INT_TYPE *vec;
/* The number of the current element in the vector. */
/* The word of the bit vector currently visited. */
unsigned IRA_INT_TYPE word;
-} ira_allocno_set_iterator;
+} minmax_set_iterator;
-/* Initialize the iterator I for allocnos bit vector VEC containing
- minimal and maximal values MIN and MAX. */
+/* Initialize the iterator I for bit vector VEC containing minimal and
+ maximal values MIN and MAX. */
static inline void
-ira_allocno_set_iter_init (ira_allocno_set_iterator *i,
- IRA_INT_TYPE *vec, int min, int max)
+minmax_set_iter_init (minmax_set_iterator *i, IRA_INT_TYPE *vec, int min,
+ int max)
{
i->vec = vec;
i->word_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 allocno number to be visited. Otherwise, return
+/* Return TRUE if we have more elements to visit, in which case *N is
+ set to the number of the element to be visited. Otherwise, return
FALSE. */
static inline bool
-ira_allocno_set_iter_cond (ira_allocno_set_iterator *i, int *n)
+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 allocno in the set. */
+/* Advance to the next element in the set. */
static inline void
-ira_allocno_set_iter_next (ira_allocno_set_iterator *i)
+minmax_set_iter_next (minmax_set_iterator *i)
{
i->word >>= 1;
i->bit_num++;
}
-/* Loop over all elements of allocno set given by bit vector VEC and
+/* 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
- ira_allocno_set_iterator used to iterate the allocnos in the set. */
-#define FOR_EACH_ALLOCNO_IN_SET(VEC, MIN, MAX, N, ITER) \
- for (ira_allocno_set_iter_init (&(ITER), (VEC), (MIN), (MAX)); \
- ira_allocno_set_iter_cond (&(ITER), &(N)); \
- ira_allocno_set_iter_next (&(ITER)))
-
+ 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)))
+\f
/* ira.c: */
/* Map: hard regs X modes -> set of hard registers for storing value
extern HARD_REG_SET ira_reg_mode_hard_regset
[FIRST_PSEUDO_REGISTER][NUM_MACHINE_MODES];
-/* Arrays analogous to macros MEMORY_MOVE_COST and
- REGISTER_MOVE_COST. */
-extern short ira_memory_move_cost[MAX_MACHINE_MODE][N_REG_CLASSES][2];
+/* Array based on TARGET_REGISTER_MOVE_COST. Don't use
+ ira_register_move_cost directly. Use function of
+ ira_get_may_move_cost instead. */
extern move_table *ira_register_move_cost[MAX_MACHINE_MODE];
/* Similar to may_move_in_cost but it is calculated in IRA instead of
regclass. Another difference we take only available hard registers
into account to figure out that one register class is a subset of
- the another one. */
+ the another one. Don't use it directly. Use function of
+ ira_get_may_move_cost instead. */
extern move_table *ira_may_move_in_cost[MAX_MACHINE_MODE];
/* Similar to may_move_out_cost but it is calculated in IRA instead of
regclass. Another difference we take only available hard registers
into account to figure out that one register class is a subset of
- the another one. */
+ the another one. Don't use it directly. Use function of
+ ira_get_may_move_cost instead. */
extern move_table *ira_may_move_out_cost[MAX_MACHINE_MODE];
/* Register class subset relation: TRUE if the first class is a subset
allocation. */
extern int ira_class_subset_p[N_REG_CLASSES][N_REG_CLASSES];
-/* Array of number of hard registers of given class which are
- available for the allocation. The order is defined by the
- allocation order. */
-extern short ira_class_hard_regs[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
-
-/* The number of elements of the above array for given register
- class. */
-extern int ira_class_hard_regs_num[N_REG_CLASSES];
+/* Array of the number of hard registers of given class which are
+ available for allocation. The order is defined by the the hard
+ register numbers. */
+extern short ira_non_ordered_class_hard_regs[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
/* Index (in ira_class_hard_regs) for given register class and hard
register (in general case a hard register can belong to several
unavailable for the allocation. */
extern short ira_class_hard_reg_index[N_REG_CLASSES][FIRST_PSEUDO_REGISTER];
-/* Function specific hard registers can not be used for the register
- allocation. */
-extern HARD_REG_SET ira_no_alloc_regs;
-
-/* Number of given class hard registers available for the register
- allocation for given classes. */
-extern int ira_available_class_regs[N_REG_CLASSES];
-
/* Array whose values are hard regset of hard registers available for
the allocation of given register class whose HARD_REGNO_MODE_OK
values for given mode are zero. */
prohibited. */
extern HARD_REG_SET ira_prohibited_mode_move_regs[NUM_MACHINE_MODES];
-/* Number of cover classes. Cover classes is non-intersected register
- classes containing all hard-registers available for the
- allocation. */
-extern int ira_reg_class_cover_size;
-
-/* The array containing cover classes (see also comments for macro
- IRA_COVER_CLASSES). Only first IRA_REG_CLASS_COVER_SIZE elements are
- used for this. */
-extern enum reg_class ira_reg_class_cover[N_REG_CLASSES];
-
/* The value is number of elements in the subsequent array. */
extern int ira_important_classes_num;
classes. */
extern int ira_important_class_nums[N_REG_CLASSES];
-/* Map of all register classes to corresponding cover class containing
- the given class. If given class is not a subset of a cover class,
- we translate it into the cheapest cover class. */
-extern enum reg_class ira_class_translate[N_REG_CLASSES];
-
/* The biggest important class inside of intersection of the two
classes (that is calculated taking only hard registers available
for allocation into account). If the both classes contain no hard
extern void ira_traverse_loop_tree (bool, ira_loop_tree_node_t,
void (*) (ira_loop_tree_node_t),
void (*) (ira_loop_tree_node_t));
+extern ira_allocno_t ira_parent_allocno (ira_allocno_t);
+extern ira_allocno_t ira_parent_or_cap_allocno (ira_allocno_t);
extern ira_allocno_t ira_create_allocno (int, bool, ira_loop_tree_node_t);
extern void ira_set_allocno_cover_class (ira_allocno_t, enum reg_class);
extern bool ira_conflict_vector_profitable_p (ira_allocno_t, int);
extern void ira_allocate_allocno_conflicts (ira_allocno_t, int);
extern void ira_add_allocno_conflict (ira_allocno_t, ira_allocno_t);
extern void ira_print_expanded_allocno (ira_allocno_t);
-extern allocno_live_range_t ira_create_allocno_live_range
- (ira_allocno_t, int, int, allocno_live_range_t);
-extern allocno_live_range_t ira_copy_allocno_live_range_list
- (allocno_live_range_t);
-extern allocno_live_range_t ira_merge_allocno_live_ranges
- (allocno_live_range_t, allocno_live_range_t);
-extern bool ira_allocno_live_ranges_intersect_p (allocno_live_range_t,
- allocno_live_range_t);
-extern void ira_finish_allocno_live_range (allocno_live_range_t);
-extern void ira_finish_allocno_live_range_list (allocno_live_range_t);
+extern live_range_t ira_create_allocno_live_range (ira_allocno_t, int, int,
+ live_range_t);
+extern live_range_t ira_copy_allocno_live_range_list (live_range_t);
+extern live_range_t ira_merge_allocno_live_ranges (live_range_t, live_range_t);
+extern bool ira_allocno_live_ranges_intersect_p (live_range_t, live_range_t);
+extern void ira_finish_allocno_live_range (live_range_t);
+extern void ira_finish_allocno_live_range_list (live_range_t);
extern void ira_free_allocno_updated_costs (ira_allocno_t);
extern ira_copy_t ira_create_copy (ira_allocno_t, ira_allocno_t,
int, bool, rtx, ira_loop_tree_node_t);
/* ira-lives.c */
extern void ira_rebuild_start_finish_chains (void);
-extern void ira_print_live_range_list (FILE *, allocno_live_range_t);
-extern void ira_debug_live_range_list (allocno_live_range_t);
+extern void ira_print_live_range_list (FILE *, live_range_t);
+extern void ira_debug_live_range_list (live_range_t);
extern void ira_debug_allocno_live_ranges (ira_allocno_t);
extern void ira_debug_live_ranges (void);
extern void ira_create_allocno_live_ranges (void);
\f
+/* Return cost of moving value of MODE from register of class FROM to
+ register of class TO. */
+static inline int
+ira_get_register_move_cost (enum machine_mode mode,
+ enum reg_class from, enum reg_class to)
+{
+ if (ira_register_move_cost[mode] == NULL)
+ ira_init_register_move_cost (mode);
+ return ira_register_move_cost[mode][from][to];
+}
+
+/* Return cost of moving value of MODE from register of class FROM to
+ register of class TO. Return zero if IN_P is true and FROM is
+ subset of TO or if IN_P is false and FROM is superset of TO. */
+static inline int
+ira_get_may_move_cost (enum machine_mode mode,
+ enum reg_class from, enum reg_class to,
+ bool in_p)
+{
+ if (ira_register_move_cost[mode] == NULL)
+ ira_init_register_move_cost (mode);
+ return (in_p
+ ? ira_may_move_in_cost[mode][from][to]
+ : ira_may_move_out_cost[mode][from][to]);
+}
+
+\f
+
/* The iterator for all allocnos. */
typedef struct {
/* The number of the current element in IRA_ALLOCNOS. */
for (; i->word == 0; i->word = ((IRA_INT_TYPE *) i->vec)[i->word_num])
{
i->word_num++;
-
+
/* If we have reached the end, break. */
if (i->word_num * sizeof (IRA_INT_TYPE) >= i->size)
return false;
-
+
i->bit_num = i->word_num * IRA_INT_BITS;
}
-
+
/* Skip bits that are zero. */
for (; (i->word & 1) == 0; i->word >>= 1)
i->bit_num++;
-
+
*a = ira_conflict_id_allocno_map[i->bit_num + i->base_conflict_id];
-
+
return true;
}
}