1 /* Integrated Register Allocator (IRA) intercommunication header file.
2 Copyright (C) 2006, 2007, 2008
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "alloc-pool.h"
26 #ifdef ENABLE_CHECKING
27 #define ENABLE_IRA_CHECKING
30 #ifdef ENABLE_IRA_CHECKING
31 #define ira_assert(c) gcc_assert (c)
36 /* Compute register frequency from edge frequency FREQ. It is
37 analogous to REG_FREQ_FROM_BB. When optimizing for size, or
38 profile driven feedback is available and the function is never
39 executed, frequency is always equivalent. Otherwise rescale the
41 #define REG_FREQ_FROM_EDGE_FREQ(freq) \
42 (optimize_size || (flag_branch_probabilities && !ENTRY_BLOCK_PTR->count) \
43 ? REG_FREQ_MAX : (freq * REG_FREQ_MAX / BB_FREQ_MAX) \
44 ? (freq * REG_FREQ_MAX / BB_FREQ_MAX) : 1)
46 /* All natural loops. */
47 extern struct loops ira_loops
;
49 /* A modified value of flag `-fira-verbose' used internally. */
50 extern int internal_flag_ira_verbose
;
52 /* Dump file of the allocator if it is not NULL. */
53 extern FILE *ira_dump_file
;
55 /* Typedefs for pointers to allocno live range, allocno, and copy of
57 typedef struct allocno_live_range
*allocno_live_range_t
;
58 typedef struct allocno
*allocno_t
;
59 typedef struct allocno_copy
*copy_t
;
61 /* Definition of vector of allocnos and copies. */
63 DEF_VEC_ALLOC_P(allocno_t
, heap
);
65 DEF_VEC_ALLOC_P(copy_t
, heap
);
67 /* Typedef for pointer to the subsequent structure. */
68 typedef struct loop_tree_node
*loop_tree_node_t
;
70 /* In general case, IRA is a regional allocator. The regions are
71 nested and form a tree. Currently regions are natural loops. The
72 following structure describes loop tree node (representing basic
73 block or loop). We need such tree because the loop tree from
74 cfgloop.h is not convenient for the optimization: basic blocks are
75 not a part of the tree from cfgloop.h. We also use the nodes for
76 storing additional information about basic blocks/loops for the
77 register allocation purposes. */
80 /* The node represents basic block if children == NULL. */
81 basic_block bb
; /* NULL for loop. */
82 struct loop
*loop
; /* NULL for BB. */
83 /* The next (loop) node of with the same father. SUBLOOP_NEXT is
84 always NULL for BBs. */
85 loop_tree_node_t subloop_next
, next
;
86 /* The first (loop) node immediately inside the node. SUBLOOPS is
87 always NULL for BBs. */
88 loop_tree_node_t subloops
, children
;
89 /* The node immediately containing given node. */
90 loop_tree_node_t father
;
92 /* Loop level in range [0, ira_loop_tree_height). */
95 /* All the following members are defined only for nodes representing
98 /* Allocnos in the loop corresponding to their regnos. If it is
99 NULL the loop does not form a separate register allocation region
100 (e.g. because it has abnormal enter/exit edges and we can not put
101 code for register shuffling on the edges if a different
102 allocation is used for a pseudo-register on different sides of
103 the edges). Caps are not in the map (remember we can have more
104 one cap with the same regno in a region). */
105 allocno_t
*regno_allocno_map
;
107 /* Maximal register pressure inside loop for given register class
108 (defined only for the cover classes). */
109 int reg_pressure
[N_REG_CLASSES
];
111 /* Numbers of allocnos referred in the loop node. */
112 bitmap mentioned_allocnos
;
114 /* Regnos of pseudos modified in the loop node (including its
116 bitmap modified_regnos
;
118 /* Numbers of allocnos living at the loop borders. */
119 bitmap border_allocnos
;
121 /* Numbers of copies referred in the corresponding loop. */
125 /* The root of the loop tree corresponding to the all function. */
126 extern loop_tree_node_t ira_loop_tree_root
;
128 /* Height of the loop tree. */
129 extern int ira_loop_tree_height
;
131 /* All nodes representing basic blocks are referred through the
132 following array. We can not use basic block member `aux' for this
133 because it is used for insertion of insns on edges. */
134 extern loop_tree_node_t ira_bb_nodes
;
136 /* Two access macros to the nodes representing basic blocks. */
137 #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)
138 #define IRA_BB_NODE_BY_INDEX(index) __extension__ \
139 (({ loop_tree_node_t _node = (&ira_bb_nodes[index]); \
140 if (_node->children != NULL || _node->loop != NULL || _node->bb == NULL)\
143 "\n%s: %d: error in %s: it is not a block node\n", \
144 __FILE__, __LINE__, __FUNCTION__); \
145 gcc_unreachable (); \
149 #define IRA_BB_NODE_BY_INDEX(index) (&ira_bb_nodes[index])
152 #define IRA_BB_NODE(bb) IRA_BB_NODE_BY_INDEX ((bb)->index)
154 /* All nodes representing loops are referred through the following
156 extern loop_tree_node_t ira_loop_nodes
;
158 /* Two access macros to the nodes representing loops. */
159 #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)
160 #define IRA_LOOP_NODE_BY_INDEX(index) __extension__ \
161 (({ loop_tree_node_t const _node = (&ira_loop_nodes[index]);\
162 if (_node->children == NULL || _node->bb != NULL || _node->loop == NULL)\
165 "\n%s: %d: error in %s: it is not a loop node\n", \
166 __FILE__, __LINE__, __FUNCTION__); \
167 gcc_unreachable (); \
171 #define IRA_LOOP_NODE_BY_INDEX(index) (&ira_loop_nodes[index])
174 #define IRA_LOOP_NODE(loop) IRA_LOOP_NODE_BY_INDEX ((loop)->num)
178 /* The structure describes program points where a given allocno lives.
179 To save memory we store allocno conflicts only for the same cover
180 class allocnos which is enough to assign hard registers. To find
181 conflicts for other allocnos (e.g. to assign stack memory slot) we
182 use the live ranges. If the live ranges of two allocnos are
183 intersected, the allocnos are in conflict. */
184 struct allocno_live_range
186 /* Allocno whose live range is described by given structure. */
188 /* Program point range. */
190 /* Next structure describing program points where the allocno
192 allocno_live_range_t next
;
193 /* Pointer to structures with the same start/finish. */
194 allocno_live_range_t start_next
, finish_next
;
197 /* Program points are enumerated by number from range 0..MAX_POINT-1.
198 There are approximately two times more program points than insns.
199 One program points correspond points between subsequent insns and
200 other ones correspond to points after usage of input operands but
201 before setting the output operands in insns. */
202 extern int max_point
;
204 /* Arrays of size MAX_POINT mapping a program point to the allocno
205 live ranges with given start/finish point. */
206 extern allocno_live_range_t
*start_point_ranges
, *finish_point_ranges
;
208 /* A structure representing an allocno (allocation entity). Allocno
209 represents a pseudo-register in an allocation region. If
210 pseudo-register does not live in a region but it lives in the
211 nested regions, it is represented in the region by special allocno
212 called *cap*. There may be more one cap representing the same
213 pseudo-register in region. It means that the corresponding
214 pseudo-register lives in more one non-intersected subregion. */
217 /* The allocno order number starting with 0. Each allocno has an
218 unique number and the number is never changed for the
221 /* Regno for allocno or cap. */
223 /* Mode of the allocno which is the mode of the corresponding
225 enum machine_mode mode
;
226 /* Final rtx representation of the allocno. */
228 /* Hard register assigned to given allocno. Negative value means
229 that memory was allocated to the allocno. During the reload,
230 spilled allocno has value equal to the corresponding stack slot
231 number (0, ...) - 2. Value -1 is used for allocnos spilled by the
232 reload (at this point pseudo-register has only one allocno) which
233 did not get stack slot yet. */
235 /* Allocnos with the same regno are linked by the following member.
236 Allocnos corresponding to inner loops are first in the list (it
237 corresponds to depth-first traverse of the loops). */
238 allocno_t next_regno_allocno
;
239 /* There may be different allocnos with the same regno in different
240 regions. Allocnos are bound to the corresponding loop tree node.
241 Pseudo-register may have only one regular allocno with given loop
242 tree node but more than one cap (see comments above). */
243 loop_tree_node_t loop_tree_node
;
244 /* Accumulated usage references of the allocno. Here and below,
245 word 'accumulated' means info for given region and all nested
246 subregions. In this case, 'accumulated' means sum of references
247 of the corresponding pseudo-register in this region and in all
248 nested subregions recursively. */
250 /* Accumulated frequency of usage of the allocno. */
252 /* Register class which should be used for allocation for given
253 allocno. NO_REGS means that we should use memory. */
254 enum reg_class cover_class
;
255 /* Minimal accumulated cost of usage register of the cover class for
257 int cover_class_cost
;
258 /* Minimal accumulated, and updated costs of memory for the allocno.
259 At the allocation start, the original and updated costs are
260 equal. The updated cost may be changed after finishing
261 allocation in a region and starting allocation in a subregion.
262 The change reflects the cost of spill/restore code on the
263 subregion border if we assign memory to the pseudo in the
265 int memory_cost
, updated_memory_cost
;
266 /* Accumulated number of points where the allocno lives and there is
267 excess pressure for its class. Excess pressure for a register
268 class at some point means that there are more allocnos of given
269 register class living at the point than number of hard-registers
270 of the class available for the allocation. */
271 int excess_pressure_points_num
;
272 /* Copies to other non-conflicting allocnos. The copies can
273 represent move insn or potential move insn usually because of two
274 operand insn constraints. */
275 copy_t allocno_copies
;
276 /* It is a allocno (cap) representing given allocno on upper loop tree
279 /* It is a link to allocno (cap) on lower loop level represented by
280 given cap. Null if given allocno is not a cap. */
281 allocno_t cap_member
;
282 /* Coalesced allocnos form a cyclic list. One allocno given by
283 FIRST_COALESCED_ALLOCNO represents all coalesced allocnos. The
284 list is chained by NEXT_COALESCED_ALLOCNO. */
285 allocno_t first_coalesced_allocno
;
286 allocno_t next_coalesced_allocno
;
287 /* Pointer to structures describing at what program point the
288 allocno lives. We always maintain the list in such way that *the
289 ranges in the list are not intersected and ordered by decreasing
290 their program points*. */
291 allocno_live_range_t live_ranges
;
292 /* Before building conflicts the two member values are
293 correspondingly minimal and maximal points of the accumulated
294 allocno live ranges. After building conflicts the values are
295 correspondingly minimal and maximal conflict ids of allocnos with
296 which given allocno can conflict. */
298 /* The unique member value represents given allocno in conflict bit
301 /* Vector of accumulated conflicting allocnos with NULL end marker
302 (if CONFLICT_VEC_P is true) or conflict bit vector otherwise.
303 Only allocnos with the same cover class are in the vector or in
305 void *conflict_allocno_array
;
306 /* Allocated size of the previous array. */
307 unsigned int conflict_allocno_array_size
;
308 /* Number of accumulated conflicts in the vector of conflicting
310 int conflict_allocnos_num
;
311 /* Initial and accumulated hard registers conflicting with this
312 allocno and as a consequences can not be assigned to the allocno.
313 All non-allocatable hard regs and hard regs of cover classes
314 different from given allocno one are included in the sets. */
315 HARD_REG_SET conflict_hard_regs
, total_conflict_hard_regs
;
316 /* Accumulated frequency of calls which given allocno
319 /* Start index of calls intersected by the allocno in array
320 regno_calls[regno]. */
321 int calls_crossed_start
;
322 /* Length of the previous array (number of the intersected calls). */
323 int calls_crossed_num
;
324 /* Non NULL if we remove restoring value from given allocno to
325 MEM_OPTIMIZED_DEST at loop exit (see ira-emit.c) because the
326 allocno value is not changed inside the loop. */
327 allocno_t mem_optimized_dest
;
328 /* TRUE if the allocno assigned to memory was a destination of
329 removed move (see ira-emit.c) at loop exit because the value of
330 the corresponding pseudo-register is not changed inside the
332 unsigned int mem_optimized_dest_p
: 1;
333 /* TRUE if the corresponding pseudo-register has disjoint live
334 ranges and the other allocnos of the pseudo-register except this
336 unsigned int somewhere_renamed_p
: 1;
337 /* TRUE if allocno with the same REGNO in a subregion has been
338 renamed, in other words, got a new pseudo-register. */
339 unsigned int child_renamed_p
: 1;
340 /* During the reload, value TRUE means that we should not reassign a
341 hard register to the allocno got memory earlier. It is set up
342 when we removed memory-memory move insn before each iteration of
344 unsigned int dont_reassign_p
: 1;
346 /* Set to TRUE if allocno can't be assigned to the stack hard
347 register correspondingly in this region and area including the
348 region and all its subregions recursively. */
349 unsigned int no_stack_reg_p
: 1, total_no_stack_reg_p
: 1;
351 /* TRUE value means that the allocno was not removed yet from the
352 conflicting graph during colouring. */
353 unsigned int in_graph_p
: 1;
354 /* TRUE if a hard register or memory has been assigned to the
356 unsigned int assigned_p
: 1;
357 /* TRUE if it is put on the stack to make other allocnos
359 unsigned int may_be_spilled_p
: 1;
360 /* TRUE if the allocno was removed from the splay tree used to
361 choose allocn for spilling (see ira-color.c::. */
362 unsigned int splay_removed_p
: 1;
363 /* TRUE if conflicts for given allocno are represented by vector of
364 pointers to the conflicting allocnos. Otherwise, we use a bit
365 vector where a bit with given index represents allocno with the
367 unsigned int conflict_vec_p
: 1;
368 /* Array of usage costs (accumulated and the one updated during
369 coloring) for each hard register of the allocno cover class. The
370 member value can be NULL if all costs are the same and equal to
371 COVER_CLASS_COST. For example, the costs of two different hard
372 registers can be different if one hard register is callee-saved
373 and another one is callee-used and the allocno lives through
374 calls. Another example can be case when for some insn the
375 corresponding pseudo-register value should be put in specific
376 register class (e.g. AREG for x86) which is a strict subset of
377 the allocno cover class (GENERAL_REGS for x86). We have updated
378 costs to reflect the situation when the usage cost of a hard
379 register is decreased because the allocno is connected to another
380 allocno by a copy and the another allocno has been assigned to
381 the hard register. */
382 int *hard_reg_costs
, *updated_hard_reg_costs
;
383 /* Array of decreasing costs (accumulated and the one updated during
384 coloring) for allocnos conflicting with given allocno for hard
385 regno of the allocno cover class. The member value can be NULL
386 if all costs are the same. These costs are used to reflect
387 preferences of other allocnos not assigned yet during assigning
389 int *conflict_hard_reg_costs
, *updated_conflict_hard_reg_costs
;
390 /* Number of the same cover class allocnos with TRUE in_graph_p
391 value and conflicting with given allocno during each point of
393 int left_conflicts_num
;
394 /* Number of hard registers of the allocno cover class really
395 available for the allocno allocation. */
396 int available_regs_num
;
397 /* Allocnos in a bucket (used in coloring) chained by the following
399 allocno_t next_bucket_allocno
;
400 allocno_t prev_bucket_allocno
;
401 /* Used for temporary purposes. */
405 /* All members of the allocno structures should be accessed only
406 through the following macros. */
407 #define ALLOCNO_NUM(A) ((A)->num)
408 #define ALLOCNO_REGNO(A) ((A)->regno)
409 #define ALLOCNO_REG(A) ((A)->reg)
410 #define ALLOCNO_NEXT_REGNO_ALLOCNO(A) ((A)->next_regno_allocno)
411 #define ALLOCNO_LOOP_TREE_NODE(A) ((A)->loop_tree_node)
412 #define ALLOCNO_CAP(A) ((A)->cap)
413 #define ALLOCNO_CAP_MEMBER(A) ((A)->cap_member)
414 #define ALLOCNO_CONFLICT_ALLOCNO_ARRAY(A) ((A)->conflict_allocno_array)
415 #define ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE(A) \
416 ((A)->conflict_allocno_array_size)
417 #define ALLOCNO_CONFLICT_ALLOCNOS_NUM(A) \
418 ((A)->conflict_allocnos_num)
419 #define ALLOCNO_CONFLICT_HARD_REGS(A) ((A)->conflict_hard_regs)
420 #define ALLOCNO_TOTAL_CONFLICT_HARD_REGS(A) ((A)->total_conflict_hard_regs)
421 #define ALLOCNO_NREFS(A) ((A)->nrefs)
422 #define ALLOCNO_FREQ(A) ((A)->freq)
423 #define ALLOCNO_HARD_REGNO(A) ((A)->hard_regno)
424 #define ALLOCNO_CALL_FREQ(A) ((A)->call_freq)
425 #define ALLOCNO_CALLS_CROSSED_START(A) ((A)->calls_crossed_start)
426 #define ALLOCNO_CALLS_CROSSED_NUM(A) ((A)->calls_crossed_num)
427 #define ALLOCNO_MEM_OPTIMIZED_DEST(A) ((A)->mem_optimized_dest)
428 #define ALLOCNO_MEM_OPTIMIZED_DEST_P(A) ((A)->mem_optimized_dest_p)
429 #define ALLOCNO_SOMEWHERE_RENAMED_P(A) ((A)->somewhere_renamed_p)
430 #define ALLOCNO_CHILD_RENAMED_P(A) ((A)->child_renamed_p)
431 #define ALLOCNO_DONT_REASSIGN_P(A) ((A)->dont_reassign_p)
433 #define ALLOCNO_NO_STACK_REG_P(A) ((A)->no_stack_reg_p)
434 #define ALLOCNO_TOTAL_NO_STACK_REG_P(A) ((A)->total_no_stack_reg_p)
436 #define ALLOCNO_IN_GRAPH_P(A) ((A)->in_graph_p)
437 #define ALLOCNO_ASSIGNED_P(A) ((A)->assigned_p)
438 #define ALLOCNO_MAY_BE_SPILLED_P(A) ((A)->may_be_spilled_p)
439 #define ALLOCNO_SPLAY_REMOVED_P(A) ((A)->splay_removed_p)
440 #define ALLOCNO_CONFLICT_VEC_P(A) ((A)->conflict_vec_p)
441 #define ALLOCNO_MODE(A) ((A)->mode)
442 #define ALLOCNO_COPIES(A) ((A)->allocno_copies)
443 #define ALLOCNO_HARD_REG_COSTS(A) ((A)->hard_reg_costs)
444 #define ALLOCNO_UPDATED_HARD_REG_COSTS(A) ((A)->updated_hard_reg_costs)
445 #define ALLOCNO_CONFLICT_HARD_REG_COSTS(A) \
446 ((A)->conflict_hard_reg_costs)
447 #define ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS(A) \
448 ((A)->updated_conflict_hard_reg_costs)
449 #define ALLOCNO_LEFT_CONFLICTS_NUM(A) ((A)->left_conflicts_num)
450 #define ALLOCNO_COVER_CLASS(A) ((A)->cover_class)
451 #define ALLOCNO_COVER_CLASS_COST(A) ((A)->cover_class_cost)
452 #define ALLOCNO_MEMORY_COST(A) ((A)->memory_cost)
453 #define ALLOCNO_UPDATED_MEMORY_COST(A) ((A)->updated_memory_cost)
454 #define ALLOCNO_EXCESS_PRESSURE_POINTS_NUM(A) ((A)->excess_pressure_points_num)
455 #define ALLOCNO_AVAILABLE_REGS_NUM(A) ((A)->available_regs_num)
456 #define ALLOCNO_NEXT_BUCKET_ALLOCNO(A) ((A)->next_bucket_allocno)
457 #define ALLOCNO_PREV_BUCKET_ALLOCNO(A) ((A)->prev_bucket_allocno)
458 #define ALLOCNO_TEMP(A) ((A)->temp)
459 #define ALLOCNO_FIRST_COALESCED_ALLOCNO(A) ((A)->first_coalesced_allocno)
460 #define ALLOCNO_NEXT_COALESCED_ALLOCNO(A) ((A)->next_coalesced_allocno)
461 #define ALLOCNO_LIVE_RANGES(A) ((A)->live_ranges)
462 #define ALLOCNO_MIN(A) ((A)->min)
463 #define ALLOCNO_MAX(A) ((A)->max)
464 #define ALLOCNO_CONFLICT_ID(A) ((A)->conflict_id)
466 /* Map regno -> allocnos with given regno (see comments for
467 allocno member `next_regno_allocno'). */
468 extern allocno_t
*regno_allocno_map
;
470 /* Array of references to all allocnos. The order number of the
471 allocno corresponds to the index in the array. Removed allocnos
472 have NULL element value. */
473 extern allocno_t
*allocnos
;
475 /* Sizes of the previous array. */
476 extern int allocnos_num
;
478 /* Map conflict id -> allocno with given conflict id (see comments for
479 allocno member `conflict_id'). */
480 extern allocno_t
*conflict_id_allocno_map
;
482 /* The following structure represents a copy of two allocnos. The
483 copies represent move insns or potential move insns usually because
484 of two operand insn constraints. */
487 /* The unique order number of the copy node starting with 0. */
489 /* Allocnos connected by the copy. The first allocno should have
490 smaller order number than the second one. */
491 allocno_t first
, second
;
492 /* Execution frequency of the copy. */
494 /* It is an insn which is an origin of the copy. It may be a move
495 insn or insn whose operand should be the same as the result
496 (2-operand insns). To remove register shuffle, we create copies
497 between allocno which is output of an insn and allocno becoming
498 dead in the insn. The member value for the copy created to
499 remove register shuffle is NULL and the frequency is smaller than
500 the corresponding insn execution frequency. */
502 /* All copies with the same allocno as FIRST are linked by the two
503 following members. */
504 copy_t prev_first_allocno_copy
, next_first_allocno_copy
;
505 /* All copies with the same allocno as SECOND are linked by the two
506 following members. */
507 copy_t prev_second_allocno_copy
, next_second_allocno_copy
;
508 /* Region from which given copy is originated. */
509 loop_tree_node_t loop_tree_node
;
512 /* Array of references to all copies. The order number of the copy
513 corresponds to the index in the array. Removed copies have NULL
515 extern copy_t
*copies
;
517 /* Size of the previous array. */
518 extern int copies_num
;
520 /* The following structure describes a stack slot used for spilled
522 struct spilled_reg_stack_slot
524 /* pseudo-registers assigned to the stack slot. */
525 regset_head spilled_regs
;
526 /* RTL representation of the stack slot. */
528 /* Size of the stack slot. */
532 /* The number of elements in the following array. */
533 extern int spilled_reg_stack_slots_num
;
535 /* The following array contains info about spilled pseudo-registers
536 stack slots used in current function so far. */
537 extern struct spilled_reg_stack_slot
*spilled_reg_stack_slots
;
539 /* Correspondingly overall cost of the allocation, cost of the
540 allocnos assigned to hard-registers, cost of the allocnos assigned
541 to memory, cost of loads, stores and register move insns generated
542 for pseudo-register live range splitting (see ira-emit.c). */
543 extern int overall_cost
;
544 extern int reg_cost
, mem_cost
;
545 extern int load_cost
, store_cost
, shuffle_cost
;
546 extern int move_loops_num
, additional_jumps_num
;
548 /* Map: register class x machine mode -> number of hard registers of
549 given class needed to store value of given mode. If the number for
550 some hard-registers of the register class is different, the size
552 extern int reg_class_nregs
[N_REG_CLASSES
][MAX_MACHINE_MODE
];
554 /* Maximal value of the previous array elements. */
555 extern int max_nregs
;
557 /* The number of bits in each element of array used to implement a bit
558 vector of allocnos and what type that element has. We use the
559 largest integer format on the host machine. */
560 #define INT_BITS HOST_BITS_PER_WIDE_INT
561 #define INT_TYPE HOST_WIDE_INT
563 /* Set, clear or test bit number I in R, a bit vector of elements with
564 minimal index and maximal index equal correspondingly to MIN and
566 #if defined ENABLE_IRA_CHECKING && (GCC_VERSION >= 2007)
568 #define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
569 (({ int _min = (MIN), _max = (MAX), _i = (I); \
570 if (_i < _min || _i > _max) \
573 "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \
574 __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \
575 gcc_unreachable (); \
577 ((R)[(unsigned) (_i - _min) / INT_BITS] \
578 |= ((INT_TYPE) 1 << ((unsigned) (_i - _min) % INT_BITS))); }))
581 #define CLEAR_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
582 (({ int _min = (MIN), _max = (MAX), _i = (I); \
583 if (_i < _min || _i > _max) \
586 "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \
587 __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \
588 gcc_unreachable (); \
590 ((R)[(unsigned) (_i - _min) / INT_BITS] \
591 &= ~((INT_TYPE) 1 << ((unsigned) (_i - _min) % INT_BITS))); }))
593 #define TEST_ALLOCNO_SET_BIT(R, I, MIN, MAX) __extension__ \
594 (({ int _min = (MIN), _max = (MAX), _i = (I); \
595 if (_i < _min || _i > _max) \
598 "\n%s: %d: error in %s: %d not in range [%d,%d]\n", \
599 __FILE__, __LINE__, __FUNCTION__, _i, _min, _max); \
600 gcc_unreachable (); \
602 ((R)[(unsigned) (_i - _min) / INT_BITS] \
603 & ((INT_TYPE) 1 << ((unsigned) (_i - _min) % INT_BITS))); }))
607 #define SET_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
608 ((R)[(unsigned) ((I) - (MIN)) / INT_BITS] \
609 |= ((INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % INT_BITS)))
611 #define CLEAR_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
612 ((R)[(unsigned) ((I) - (MIN)) / INT_BITS] \
613 &= ~((INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % INT_BITS)))
615 #define TEST_ALLOCNO_SET_BIT(R, I, MIN, MAX) \
616 ((R)[(unsigned) ((I) - (MIN)) / INT_BITS] \
617 & ((INT_TYPE) 1 << ((unsigned) ((I) - (MIN)) % INT_BITS)))
621 /* The iterator for allocno set implemented ed as allocno bit
625 /* Array containing the allocno bit vector. */
628 /* The number of the current element in the vector. */
629 unsigned int word_num
;
631 /* The number of bits in the bit vector. */
634 /* The current bit index of the bit vector. */
635 unsigned int bit_num
;
637 /* Index corresponding to the 1st bit of the bit vector. */
640 /* The word of the bit vector currently visited. */
641 unsigned INT_TYPE word
;
642 } allocno_set_iterator
;
644 /* Initialize the iterator I for allocnos bit vector VEC containing
645 minimal and maximal values MIN and MAX. */
647 allocno_set_iter_init (allocno_set_iterator
*i
, INT_TYPE
*vec
, int min
, int max
)
651 i
->nel
= max
< min
? 0 : max
- min
+ 1;
654 i
->word
= i
->nel
== 0 ? 0 : vec
[0];
657 /* Return TRUE if we have more allocnos to visit, in which case *N is
658 set to the allocno number to be visited. Otherwise, return
661 allocno_set_iter_cond (allocno_set_iterator
*i
, int *n
)
663 /* Skip words that are zeros. */
664 for (; i
->word
== 0; i
->word
= i
->vec
[i
->word_num
])
667 i
->bit_num
= i
->word_num
* INT_BITS
;
669 /* If we have reached the end, break. */
670 if (i
->bit_num
>= i
->nel
)
674 /* Skip bits that are zero. */
675 for (; (i
->word
& 1) == 0; i
->word
>>= 1)
678 *n
= (int) i
->bit_num
+ i
->start_val
;
683 /* Advance to the next allocno in the set. */
685 allocno_set_iter_next (allocno_set_iterator
*i
)
691 /* Loop over all elements of allocno set given by bit vector VEC and
692 their minimal and maximal values MIN and MAX. In each iteration, N
693 is set to the number of next allocno. ITER is an instance of
694 allocno_set_iterator used to iterate the allocnos in the set. */
695 #define FOR_EACH_ALLOCNO_IN_SET(VEC, MIN, MAX, N, ITER) \
696 for (allocno_set_iter_init (&(ITER), (VEC), (MIN), (MAX)); \
697 allocno_set_iter_cond (&(ITER), &(N)); \
698 allocno_set_iter_next (&(ITER)))
702 /* Hard regsets whose all bits are correspondingly zero or one. */
703 extern HARD_REG_SET zero_hard_reg_set
;
704 extern HARD_REG_SET one_hard_reg_set
;
706 /* Map: hard regs X modes -> set of hard registers for storing value
707 of given mode starting with given hard register. */
708 extern HARD_REG_SET reg_mode_hard_regset
709 [FIRST_PSEUDO_REGISTER
][NUM_MACHINE_MODES
];
711 /* Arrays analogous to macros MEMORY_MOVE_COST and
712 REGISTER_MOVE_COST. */
713 extern short memory_move_cost
[MAX_MACHINE_MODE
][N_REG_CLASSES
][2];
714 extern move_table
*register_move_cost
[MAX_MACHINE_MODE
];
716 /* Similar to may_move_in_cost but it is calculated in IRA instead of
717 regclass. Another difference we take only available hard registers
718 into account to figure out that one register class is a subset of
720 extern move_table
*register_may_move_in_cost
[MAX_MACHINE_MODE
];
722 /* Similar to may_move_out_cost but it is calculated in IRA instead of
723 regclass. Another difference we take only available hard registers
724 into account to figure out that one register class is a subset of
726 extern move_table
*register_may_move_out_cost
[MAX_MACHINE_MODE
];
728 /* Register class subset relation: TRUE if the first class is a subset
729 of the second one considering only hard registers available for the
731 extern int class_subset_p
[N_REG_CLASSES
][N_REG_CLASSES
];
733 /* Array of number of hard registers of given class which are
734 available for the allocation. The order is defined by the
736 extern short class_hard_regs
[N_REG_CLASSES
][FIRST_PSEUDO_REGISTER
];
738 /* The number of elements of the above array for given register
740 extern int class_hard_regs_num
[N_REG_CLASSES
];
742 /* Index (in class_hard_regs) for given register class and hard
743 register (in general case a hard register can belong to several
744 register classes). The index is negative for hard registers
745 unavailable for the allocation. */
746 extern short class_hard_reg_index
[N_REG_CLASSES
][FIRST_PSEUDO_REGISTER
];
748 /* Function specific hard registers can not be used for the register
750 extern HARD_REG_SET no_alloc_regs
;
752 /* Number of given class hard registers available for the register
753 allocation for given classes. */
754 extern int available_class_regs
[N_REG_CLASSES
];
756 /* Array whose values are hard regset of hard registers available for
757 the allocation of given register class whose HARD_REGNO_MODE_OK
758 values for given mode are zero. */
759 extern HARD_REG_SET prohibited_class_mode_regs
760 [N_REG_CLASSES
][NUM_MACHINE_MODES
];
762 /* Array whose values are hard regset of hard registers for which
763 move of the hard register in given mode into itself is
765 extern HARD_REG_SET prohibited_mode_move_regs
[NUM_MACHINE_MODES
];
767 /* Number of cover classes. Cover classes is non-intersected register
768 classes containing all hard-registers available for the
770 extern int reg_class_cover_size
;
772 /* The array containing cover classes (see also comments for macro
773 IRA_COVER_CLASSES). Only first REG_CLASS_COVER_SIZE elements are
775 extern enum reg_class reg_class_cover
[N_REG_CLASSES
];
777 /* The value is number of elements in the subsequent array. */
778 extern int important_classes_num
;
780 /* The array containing non-empty classes (including non-empty cover
781 classes) which are subclasses of cover classes. Such classes is
782 important for calculation of the hard register usage costs. */
783 extern enum reg_class important_classes
[N_REG_CLASSES
];
785 /* The array containing indexes of important classes in the previous
786 array. The array elements are defined only for important
788 extern int important_class_nums
[N_REG_CLASSES
];
790 /* Map of all register classes to corresponding cover class containing
791 the given class. If given class is not a subset of a cover class,
792 we translate it into the cheapest cover class. */
793 extern enum reg_class class_translate
[N_REG_CLASSES
];
795 /* The biggest important class inside of intersection of the two
796 classes (that is calculated taking only hard registers available
797 for allocation into account). If the both classes contain no hard
798 registers available for allocation, the value is calculated with
799 taking all hard-registers including fixed ones into account. */
800 extern enum reg_class reg_class_intersect
[N_REG_CLASSES
][N_REG_CLASSES
];
802 /* The biggest important class inside of union of the two classes
803 (that is calculated taking only hard registers available for
804 allocation into account). If the both classes contain no hard
805 registers available for allocation, the value is calculated with
806 taking all hard-registers including fixed ones into account. In
807 other words, the value is the corresponding reg_class_subunion
809 extern enum reg_class reg_class_union
[N_REG_CLASSES
][N_REG_CLASSES
];
811 extern void set_non_alloc_regs (int);
812 extern void *ira_allocate (size_t);
813 extern void *ira_reallocate (void *, size_t);
814 extern void ira_free (void *addr
);
815 extern bitmap
ira_allocate_bitmap (void);
816 extern void ira_free_bitmap (bitmap
);
817 extern void print_disposition (FILE *);
818 extern void debug_disposition (void);
819 extern void debug_class_cover (void);
820 extern void init_register_move_cost (enum machine_mode
);
822 /* The length of the two following arrays. */
823 extern int reg_equiv_len
;
825 /* The element value is TRUE if the corresponding regno value is
827 extern int *reg_equiv_invariant_p
;
829 /* The element value is equiv constant of given pseudo-register or
831 extern rtx
*reg_equiv_const
;
835 /* The current loop tree node and its regno allocno map. */
836 extern loop_tree_node_t ira_curr_loop_tree_node
;
837 extern allocno_t
*ira_curr_regno_allocno_map
;
839 /* Array of vectors containing calls given pseudo-register lives
841 extern VEC(rtx
, heap
) **regno_calls
;
843 extern int add_regno_call (int, rtx
);
845 extern void debug_allocno_copies (allocno_t
);
847 extern void traverse_loop_tree (int, loop_tree_node_t
,
848 void (*) (loop_tree_node_t
),
849 void (*) (loop_tree_node_t
));
850 extern allocno_t
create_allocno (int, int, loop_tree_node_t
);
851 extern void set_allocno_cover_class (allocno_t
, enum reg_class
);
852 extern int conflict_vector_profitable_p (allocno_t
, int);
853 extern void allocate_allocno_conflict_vec (allocno_t
, int);
854 extern void allocate_allocno_conflicts (allocno_t
, int);
855 extern void add_allocno_conflict (allocno_t
, allocno_t
);
856 extern void print_expanded_allocno (allocno_t
);
857 extern allocno_live_range_t
create_allocno_live_range (allocno_t
, int, int,
858 allocno_live_range_t
);
859 extern void finish_allocno_live_range (allocno_live_range_t
);
860 extern void free_allocno_updated_costs (allocno_t
);
861 extern copy_t
create_copy (allocno_t
, allocno_t
, int, rtx
, loop_tree_node_t
);
862 extern void add_allocno_copy_to_list (copy_t
);
863 extern void swap_allocno_copy_ends_if_necessary (copy_t
);
864 extern void remove_allocno_copy_from_list (copy_t
);
865 extern copy_t
add_allocno_copy (allocno_t
, allocno_t
, int, rtx
,
868 extern int *allocate_cost_vector (enum reg_class
);
869 extern void free_cost_vector (int *, enum reg_class
);
871 extern void ira_flattening (int, int);
872 extern int ira_build (int);
873 extern void ira_destroy (void);
876 extern void init_ira_costs_once (void);
877 extern void init_ira_costs (void);
878 extern void finish_ira_costs_once (void);
879 extern void ira_costs (void);
880 extern void tune_allocno_costs_and_cover_classes (void);
884 extern void rebuild_start_finish_chains (void);
885 extern void print_live_range_list (FILE *, allocno_live_range_t
);
886 extern void debug_live_range_list (allocno_live_range_t
);
887 extern void debug_allocno_live_ranges (allocno_t
);
888 extern void debug_live_ranges (void);
889 extern void create_allocno_live_ranges (void);
890 extern void finish_allocno_live_ranges (void);
892 /* ira-conflicts.c */
893 extern int allocno_live_ranges_intersect_p (allocno_t
, allocno_t
);
894 extern int pseudo_live_ranges_intersect_p (int, int);
895 extern void debug_conflicts (int);
896 extern void ira_build_conflicts (void);
899 extern int loop_edge_freq (loop_tree_node_t
, int, int);
900 extern void reassign_conflict_allocnos (int);
901 extern void initiate_ira_assign (void);
902 extern void finish_ira_assign (void);
903 extern void ira_color (void);
904 extern void ira_fast_allocation (void);
907 extern void ira_emit (int);
911 /* The iterator for all allocnos. */
913 /* The number of the current element in ALLOCNOS. */
917 /* Initialize the iterator I. */
919 allocno_iter_init (allocno_iterator
*i
)
924 /* Return TRUE if we have more allocnos to visit, in which case *A is
925 set to the allocno to be visited. Otherwise, return FALSE. */
927 allocno_iter_cond (allocno_iterator
*i
, allocno_t
*a
)
931 for (n
= i
->n
; n
< allocnos_num
; n
++)
932 if (allocnos
[n
] != NULL
)
941 /* Loop over all allocnos. In each iteration, A is set to the next
942 allocno. ITER is an instance of allocno_iterator used to iterate
944 #define FOR_EACH_ALLOCNO(A, ITER) \
945 for (allocno_iter_init (&(ITER)); \
946 allocno_iter_cond (&(ITER), &(A));)
951 /* The iterator for copies. */
953 /* The number of the current element in COPIES. */
957 /* Initialize the iterator I. */
959 copy_iter_init (copy_iterator
*i
)
964 /* Return TRUE if we have more copies to visit, in which case *CP is
965 set to the copy to be visited. Otherwise, return FALSE. */
967 copy_iter_cond (copy_iterator
*i
, copy_t
*cp
)
971 for (n
= i
->n
; n
< copies_num
; n
++)
972 if (copies
[n
] != NULL
)
981 /* Loop over all copies. In each iteration, C is set to the next
982 copy. ITER is an instance of copy_iterator used to iterate
984 #define FOR_EACH_COPY(C, ITER) \
985 for (copy_iter_init (&(ITER)); \
986 copy_iter_cond (&(ITER), &(C));)
991 /* The iterator for allocno conflicts. */
994 /* TRUE if the conflicts are represented by vector of allocnos. */
995 int allocno_conflict_vec_p
;
997 /* The conflict vector or conflict bit vector. */
1000 /* The number of the current element in the vector (of type
1001 allocno_t or INT_TYPE). */
1002 unsigned int word_num
;
1004 /* The bit vector size. It is defined only if
1005 ALLOCNO_CONFLICT_VEC_P is FALSE. */
1008 /* The current bit index of bit vector. It is defined only if
1009 ALLOCNO_CONFLICT_VEC_P is FALSE. */
1010 unsigned int bit_num
;
1012 /* Allocno conflict id corresponding to the 1st bit of the bit
1013 vector. It is defined only if ALLOCNO_CONFLICT_VEC_P is
1015 int base_conflict_id
;
1017 /* The word of bit vector currently visited. It is defined only if
1018 ALLOCNO_CONFLICT_VEC_P is FALSE. */
1019 unsigned INT_TYPE word
;
1020 } allocno_conflict_iterator
;
1022 /* Initialize the iterator I with ALLOCNO conflicts. */
1024 allocno_conflict_iter_init (allocno_conflict_iterator
*i
, allocno_t allocno
)
1026 i
->allocno_conflict_vec_p
= ALLOCNO_CONFLICT_VEC_P (allocno
);
1027 i
->vec
= ALLOCNO_CONFLICT_ALLOCNO_ARRAY (allocno
);
1029 if (i
->allocno_conflict_vec_p
)
1030 i
->size
= i
->bit_num
= i
->base_conflict_id
= i
->word
= 0;
1033 if (ALLOCNO_MIN (allocno
) > ALLOCNO_MAX (allocno
))
1036 i
->size
= ((ALLOCNO_MAX (allocno
) - ALLOCNO_MIN (allocno
) + INT_BITS
)
1037 / INT_BITS
) * sizeof (INT_TYPE
);
1039 i
->base_conflict_id
= ALLOCNO_MIN (allocno
);
1040 i
->word
= (i
->size
== 0 ? 0 : ((INT_TYPE
*) i
->vec
)[0]);
1044 /* Return TRUE if we have more conflicting allocnos to visit, in which
1045 case *A is set to the allocno to be visited. Otherwise, return
1048 allocno_conflict_iter_cond (allocno_conflict_iterator
*i
, allocno_t
*a
)
1050 allocno_t conflict_allocno
;
1052 if (i
->allocno_conflict_vec_p
)
1054 conflict_allocno
= ((allocno_t
*) i
->vec
)[i
->word_num
];
1055 if (conflict_allocno
== NULL
)
1057 *a
= conflict_allocno
;
1062 /* Skip words that are zeros. */
1063 for (; i
->word
== 0; i
->word
= ((INT_TYPE
*) i
->vec
)[i
->word_num
])
1067 /* If we have reached the end, break. */
1068 if (i
->word_num
* sizeof (INT_TYPE
) >= i
->size
)
1071 i
->bit_num
= i
->word_num
* INT_BITS
;
1074 /* Skip bits that are zero. */
1075 for (; (i
->word
& 1) == 0; i
->word
>>= 1)
1078 *a
= conflict_id_allocno_map
[i
->bit_num
+ i
->base_conflict_id
];
1084 /* Advance to the next conflicting allocno. */
1086 allocno_conflict_iter_next (allocno_conflict_iterator
*i
)
1088 if (i
->allocno_conflict_vec_p
)
1097 /* Loop over all allocnos conflicting with ALLOCNO. In each
1098 iteration, A is set to the next conflicting allocno. ITER is an
1099 instance of allocno_conflict_iterator used to iterate the
1101 #define FOR_EACH_ALLOCNO_CONFLICT(ALLOCNO, A, ITER) \
1102 for (allocno_conflict_iter_init (&(ITER), (ALLOCNO)); \
1103 allocno_conflict_iter_cond (&(ITER), &(A)); \
1104 allocno_conflict_iter_next (&(ITER)))
1108 /* The function returns TRUE if hard registers starting with
1109 HARD_REGNO and containing value of MODE are not in set
1112 hard_reg_not_in_set_p (int hard_regno
, enum machine_mode mode
,
1113 HARD_REG_SET hard_regset
)
1117 ira_assert (hard_regno
>= 0);
1118 for (i
= hard_regno_nregs
[hard_regno
][mode
] - 1; i
>= 0; i
--)
1119 if (TEST_HARD_REG_BIT (hard_regset
, hard_regno
+ i
))
1126 /* To save memory we use a lazy approach for allocation and
1127 initialization of the cost vectors. We do this only when it is
1128 really necessary. */
1130 /* Allocate cost vector *VEC for hard registers of COVER_CLASS and
1131 initialize the elements by VAL if it is necessary */
1133 allocate_and_set_costs (int **vec
, enum reg_class cover_class
, int val
)
1140 *vec
= reg_costs
= allocate_cost_vector (cover_class
);
1141 len
= class_hard_regs_num
[cover_class
];
1142 for (i
= 0; i
< len
; i
++)
1146 /* Allocate cost vector *VEC for hard registers of COVER_CLASS and
1147 copy values of vector SRC into the vector if it is necessary */
1149 allocate_and_copy_costs (int **vec
, enum reg_class cover_class
, int *src
)
1153 if (*vec
!= NULL
|| src
== NULL
)
1155 *vec
= allocate_cost_vector (cover_class
);
1156 len
= class_hard_regs_num
[cover_class
];
1157 memcpy (*vec
, src
, sizeof (int) * len
);
1160 /* Allocate cost vector *VEC for hard registers of COVER_CLASS and
1161 copy values of vector SRC into the vector or initialize it by VAL
1162 (if SRC is null). */
1164 allocate_and_set_or_copy_costs (int **vec
, enum reg_class cover_class
,
1172 *vec
= reg_costs
= allocate_cost_vector (cover_class
);
1173 len
= class_hard_regs_num
[cover_class
];
1175 memcpy (reg_costs
, src
, sizeof (int) * len
);
1178 for (i
= 0; i
< len
; i
++)