/* Integrated Register Allocator (IRA) intercommunication header file.
- Copyright (C) 2006, 2007, 2008
+ Copyright (C) 2006, 2007, 2008, 2009
Free Software Foundation, Inc.
Contributed by Vladimir Makarov <vmakarov@redhat.com>.
#ifdef ENABLE_IRA_CHECKING
#define ira_assert(c) gcc_assert (c)
#else
-#define ira_assert(c)
+/* 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
/* The node represents basic block if children == NULL. */
basic_block bb; /* NULL for loop. */
struct loop *loop; /* NULL for BB. */
- /* The next (loop) node of with the same parent. SUBLOOP_NEXT is
- always NULL for BBs. */
+ /* 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;
- /* The first (loop) node immediately inside the node. SUBLOOPS is
- always NULL for BBs. */
+ /* 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;
/* All the following members are defined only for nodes representing
loops. */
+ /* 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
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 cover classes). */
int reg_pressure[N_REG_CLASSES];
/* Mode of the allocno which is the mode of the corresponding
pseudo-register. */
enum machine_mode mode;
- /* Final rtx representation of the allocno. */
- rtx reg;
/* 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
reload (at this point pseudo-register has only one allocno) which
did not get stack slot yet. */
int hard_regno;
+ /* Final rtx representation of the allocno. */
+ rtx reg;
/* 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). */
/* Register class which should be used for allocation for given
allocno. NO_REGS means that we should use memory. */
enum reg_class cover_class;
- /* Minimal accumulated cost of usage register of the cover class for
- the allocno. */
- int cover_class_cost;
+ /* Minimal accumulated and updated costs of usage register of the
+ cover class for the allocno. */
+ int cover_class_cost, updated_cover_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
correspondingly minimal and maximal conflict ids of allocnos with
which given allocno can conflict. */
int min, max;
- /* The unique member value represents given allocno in conflict bit
- vectors. */
- int conflict_id;
/* Vector of accumulated conflicting allocnos with NULL end marker
(if CONFLICT_VEC_P is true) or conflict bit vector otherwise.
Only allocnos with the same cover class are in the vector or in
the bit vector. */
void *conflict_allocno_array;
+ /* The unique member value represents given allocno in conflict bit
+ vectors. */
+ int conflict_id;
/* Allocated size of the previous array. */
unsigned int conflict_allocno_array_size;
- /* Number of accumulated conflicts in the vector of conflicting
- allocnos. */
- int conflict_allocnos_num;
/* Initial and accumulated hard registers conflicting with this
allocno and as a consequences can not be assigned to the allocno.
All non-allocatable hard regs and hard regs of cover 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
+ allocnos. */
+ int conflict_allocnos_num;
/* Accumulated frequency of calls which given allocno
intersects. */
int call_freq;
- /* Length of the previous array (number of the intersected calls). */
+ /* Accumulated number of the intersected calls. */
int calls_crossed_num;
- /* 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;
/* 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
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 value means that the allocno was not removed yet from the
conflicting graph during colouring. */
unsigned int in_graph_p : 1;
vector where a bit with given index represents allocno with the
same number. */
unsigned int conflict_vec_p : 1;
+ /* 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;
/* Array of usage costs (accumulated and the one updated during
coloring) for each hard register of the allocno cover class. The
member value can be NULL if all costs are the same and equal to
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;
#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_IN_GRAPH_P(A) ((A)->in_graph_p)
#define ALLOCNO_ASSIGNED_P(A) ((A)->assigned_p)
#define ALLOCNO_MAY_BE_SPILLED_P(A) ((A)->may_be_spilled_p)
((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_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_AVAILABLE_REGS_NUM(A) ((A)->available_regs_num)
#define ALLOCNO_NEXT_BUCKET_ALLOCNO(A) ((A)->next_bucket_allocno)
#define ALLOCNO_PREV_BUCKET_ALLOCNO(A) ((A)->prev_bucket_allocno)
-#define IRA_ALLOCNO_TEMP(A) ((A)->temp)
+#define ALLOCNO_TEMP(A) ((A)->temp)
#define ALLOCNO_FIRST_COALESCED_ALLOCNO(A) ((A)->first_coalesced_allocno)
#define ALLOCNO_NEXT_COALESCED_ALLOCNO(A) ((A)->next_coalesced_allocno)
#define ALLOCNO_LIVE_RANGES(A) ((A)->live_ranges)
#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;
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
extern int ira_load_cost, ira_store_cost, ira_shuffle_cost;
extern int ira_move_loops_num, ira_additional_jumps_num;
-/* 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
} \
((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__ \
(({ int _min = (MIN), _max = (MAX), _i = (I); \
{
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;
}
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 analogous to macro 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];
-
/* Index (in ira_class_hard_regs) for given register class and hard
register (in general case a hard register can belong to several
register classes). The index is negative for hard registers
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
taking all hard-registers including fixed ones into account. */
extern enum reg_class ira_reg_class_intersect[N_REG_CLASSES][N_REG_CLASSES];
+/* True if the two classes (that is calculated taking only hard
+ registers available for allocation into account) are
+ intersected. */
+extern bool ira_reg_classes_intersect_p[N_REG_CLASSES][N_REG_CLASSES];
+
+/* Classes with end marker LIM_REG_CLASSES which are intersected with
+ given class (the first index). That includes given class itself.
+ This is calculated taking only hard registers available for
+ allocation into account. */
+extern enum reg_class ira_reg_class_super_classes[N_REG_CLASSES][N_REG_CLASSES];
/* The biggest important class inside of union 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_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 void ira_free_allocno_updated_costs (ira_allocno_t);
extern ira_copy_t ira_create_copy (ira_allocno_t, ira_allocno_t,
- int, rtx, ira_loop_tree_node_t);
+ int, bool, rtx, ira_loop_tree_node_t);
extern void ira_add_allocno_copy_to_list (ira_copy_t);
extern void ira_swap_allocno_copy_ends_if_necessary (ira_copy_t);
extern void ira_remove_allocno_copy_from_list (ira_copy_t);
-extern ira_copy_t ira_add_allocno_copy (ira_allocno_t, ira_allocno_t, int, rtx,
- ira_loop_tree_node_t);
+extern ira_copy_t ira_add_allocno_copy (ira_allocno_t, ira_allocno_t, int,
+ bool, rtx, ira_loop_tree_node_t);
extern int *ira_allocate_cost_vector (enum reg_class);
extern void ira_free_cost_vector (int *, enum reg_class);
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);
+extern void ira_compress_allocno_live_ranges (void);
extern void ira_finish_allocno_live_ranges (void);
/* ira-conflicts.c */
-extern bool ira_allocno_live_ranges_intersect_p (ira_allocno_t, ira_allocno_t);
-extern bool ira_pseudo_live_ranges_intersect_p (int, int);
extern void ira_debug_conflicts (bool);
extern void ira_build_conflicts (void);
extern void ira_initiate_assign (void);
extern void ira_finish_assign (void);
extern void ira_color (void);
-extern void ira_fast_allocation (void);
/* ira-emit.c */
extern void ira_emit (bool);
\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;
}
}
OSDN Git Service
