1 /* Building internal representation for IRA.
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 "coretypes.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "insn-config.h"
40 #include "sparseset.h"
43 static ira_copy_t
find_allocno_copy (ira_allocno_t
, ira_allocno_t
, rtx
,
44 ira_loop_tree_node_t
);
46 /* The root of the loop tree corresponding to the all function. */
47 ira_loop_tree_node_t ira_loop_tree_root
;
49 /* Height of the loop tree. */
50 int ira_loop_tree_height
;
52 /* All nodes representing basic blocks are referred through the
53 following array. We can not use basic block member `aux' for this
54 because it is used for insertion of insns on edges. */
55 ira_loop_tree_node_t ira_bb_nodes
;
57 /* All nodes representing loops are referred through the following
59 ira_loop_tree_node_t ira_loop_nodes
;
61 /* Map regno -> allocnos with given regno (see comments for
62 allocno member `next_regno_allocno'). */
63 ira_allocno_t
*ira_regno_allocno_map
;
65 /* Array of references to all allocnos. The order number of the
66 allocno corresponds to the index in the array. Removed allocnos
67 have NULL element value. */
68 ira_allocno_t
*ira_allocnos
;
70 /* Sizes of the previous array. */
73 /* Map conflict id -> allocno with given conflict id (see comments for
74 allocno member `conflict_id'). */
75 ira_allocno_t
*ira_conflict_id_allocno_map
;
77 /* Array of references to all copies. The order number of the copy
78 corresponds to the index in the array. Removed copies have NULL
80 ira_copy_t
*ira_copies
;
82 /* Size of the previous array. */
87 /* LAST_BASIC_BLOCK before generating additional insns because of live
88 range splitting. Emitting insns on a critical edge creates a new
90 static int last_basic_block_before_change
;
92 /* The following function allocates the loop tree nodes. If LOOPS_P
93 is FALSE, the nodes corresponding to the loops (except the root
94 which corresponds the all function) will be not allocated but nodes
95 will still be allocated for basic blocks. */
97 create_loop_tree_nodes (bool loops_p
)
104 VEC (edge
, heap
) *edges
;
108 = ((struct ira_loop_tree_node
*)
109 ira_allocate (sizeof (struct ira_loop_tree_node
) * last_basic_block
));
110 last_basic_block_before_change
= last_basic_block
;
111 for (i
= 0; i
< (unsigned int) last_basic_block
; i
++)
113 ira_bb_nodes
[i
].regno_allocno_map
= NULL
;
114 memset (ira_bb_nodes
[i
].reg_pressure
, 0,
115 sizeof (ira_bb_nodes
[i
].reg_pressure
));
116 ira_bb_nodes
[i
].all_allocnos
= NULL
;
117 ira_bb_nodes
[i
].modified_regnos
= NULL
;
118 ira_bb_nodes
[i
].border_allocnos
= NULL
;
119 ira_bb_nodes
[i
].local_copies
= NULL
;
121 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
122 ira_allocate (sizeof (struct ira_loop_tree_node
)
123 * VEC_length (loop_p
, ira_loops
.larray
)));
124 max_regno
= max_reg_num ();
125 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
127 if (loop
!= ira_loops
.tree_root
)
129 ira_loop_nodes
[i
].regno_allocno_map
= NULL
;
133 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
134 if (e
->src
!= loop
->latch
135 && (e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
142 edges
= get_loop_exit_edges (loop
);
143 for (j
= 0; VEC_iterate (edge
, edges
, j
, e
); j
++)
144 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
149 VEC_free (edge
, heap
, edges
);
153 ira_loop_nodes
[i
].regno_allocno_map
154 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
) * max_regno
);
155 memset (ira_loop_nodes
[i
].regno_allocno_map
, 0,
156 sizeof (ira_allocno_t
) * max_regno
);
157 memset (ira_loop_nodes
[i
].reg_pressure
, 0,
158 sizeof (ira_loop_nodes
[i
].reg_pressure
));
159 ira_loop_nodes
[i
].all_allocnos
= ira_allocate_bitmap ();
160 ira_loop_nodes
[i
].modified_regnos
= ira_allocate_bitmap ();
161 ira_loop_nodes
[i
].border_allocnos
= ira_allocate_bitmap ();
162 ira_loop_nodes
[i
].local_copies
= ira_allocate_bitmap ();
166 /* The function returns TRUE if there are more one allocation
169 more_one_region_p (void)
174 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
175 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
176 && ira_loop_tree_root
!= &ira_loop_nodes
[i
])
181 /* Free the loop tree node of a loop. */
183 finish_loop_tree_node (ira_loop_tree_node_t loop
)
185 if (loop
->regno_allocno_map
!= NULL
)
187 ira_assert (loop
->bb
== NULL
);
188 ira_free_bitmap (loop
->local_copies
);
189 ira_free_bitmap (loop
->border_allocnos
);
190 ira_free_bitmap (loop
->modified_regnos
);
191 ira_free_bitmap (loop
->all_allocnos
);
192 ira_free (loop
->regno_allocno_map
);
193 loop
->regno_allocno_map
= NULL
;
197 /* Free the loop tree nodes. */
199 finish_loop_tree_nodes (void)
204 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
205 finish_loop_tree_node (&ira_loop_nodes
[i
]);
206 ira_free (ira_loop_nodes
);
207 for (i
= 0; i
< (unsigned int) last_basic_block_before_change
; i
++)
209 if (ira_bb_nodes
[i
].local_copies
!= NULL
)
210 ira_free_bitmap (ira_bb_nodes
[i
].local_copies
);
211 if (ira_bb_nodes
[i
].border_allocnos
!= NULL
)
212 ira_free_bitmap (ira_bb_nodes
[i
].border_allocnos
);
213 if (ira_bb_nodes
[i
].modified_regnos
!= NULL
)
214 ira_free_bitmap (ira_bb_nodes
[i
].modified_regnos
);
215 if (ira_bb_nodes
[i
].all_allocnos
!= NULL
)
216 ira_free_bitmap (ira_bb_nodes
[i
].all_allocnos
);
217 if (ira_bb_nodes
[i
].regno_allocno_map
!= NULL
)
218 ira_free (ira_bb_nodes
[i
].regno_allocno_map
);
220 ira_free (ira_bb_nodes
);
225 /* The following recursive function adds LOOP to the loop tree
226 hierarchy. LOOP is added only once. */
228 add_loop_to_tree (struct loop
*loop
)
231 ira_loop_tree_node_t loop_node
, parent_node
;
233 /* We can not use loop node access macros here because of potential
234 checking and because the nodes are not initialized enough
236 if (loop_outer (loop
) != NULL
)
237 add_loop_to_tree (loop_outer (loop
));
238 if (ira_loop_nodes
[loop
->num
].regno_allocno_map
!= NULL
239 && ira_loop_nodes
[loop
->num
].children
== NULL
)
241 /* We have not added loop node to the tree yet. */
242 loop_node
= &ira_loop_nodes
[loop
->num
];
243 loop_node
->loop
= loop
;
244 loop_node
->bb
= NULL
;
245 for (parent
= loop_outer (loop
);
247 parent
= loop_outer (parent
))
248 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
252 loop_node
->next
= NULL
;
253 loop_node
->subloop_next
= NULL
;
254 loop_node
->parent
= NULL
;
258 parent_node
= &ira_loop_nodes
[parent
->num
];
259 loop_node
->next
= parent_node
->children
;
260 parent_node
->children
= loop_node
;
261 loop_node
->subloop_next
= parent_node
->subloops
;
262 parent_node
->subloops
= loop_node
;
263 loop_node
->parent
= parent_node
;
268 /* The following recursive function sets up levels of nodes of the
269 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
270 The function returns maximal value of level in the tree + 1. */
272 setup_loop_tree_level (ira_loop_tree_node_t loop_node
, int level
)
274 int height
, max_height
;
275 ira_loop_tree_node_t subloop_node
;
277 ira_assert (loop_node
->bb
== NULL
);
278 loop_node
->level
= level
;
279 max_height
= level
+ 1;
280 for (subloop_node
= loop_node
->subloops
;
281 subloop_node
!= NULL
;
282 subloop_node
= subloop_node
->subloop_next
)
284 ira_assert (subloop_node
->bb
== NULL
);
285 height
= setup_loop_tree_level (subloop_node
, level
+ 1);
286 if (height
> max_height
)
292 /* Create the loop tree. The algorithm is designed to provide correct
293 order of loops (they are ordered by their last loop BB) and basic
294 blocks in the chain formed by member next. */
296 form_loop_tree (void)
301 ira_loop_tree_node_t bb_node
, loop_node
;
304 /* We can not use loop/bb node access macros because of potential
305 checking and because the nodes are not initialized enough
307 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
308 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
310 ira_loop_nodes
[i
].children
= NULL
;
311 ira_loop_nodes
[i
].subloops
= NULL
;
315 bb_node
= &ira_bb_nodes
[bb
->index
];
317 bb_node
->loop
= NULL
;
318 bb_node
->subloops
= NULL
;
319 bb_node
->children
= NULL
;
320 bb_node
->subloop_next
= NULL
;
321 bb_node
->next
= NULL
;
322 for (parent
= bb
->loop_father
;
324 parent
= loop_outer (parent
))
325 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
327 add_loop_to_tree (parent
);
328 loop_node
= &ira_loop_nodes
[parent
->num
];
329 bb_node
->next
= loop_node
->children
;
330 bb_node
->parent
= loop_node
;
331 loop_node
->children
= bb_node
;
333 ira_loop_tree_root
= IRA_LOOP_NODE_BY_INDEX (ira_loops
.tree_root
->num
);
334 ira_loop_tree_height
= setup_loop_tree_level (ira_loop_tree_root
, 0);
335 ira_assert (ira_loop_tree_root
->regno_allocno_map
!= NULL
);
340 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
343 rebuild_regno_allocno_maps (void)
346 int max_regno
, regno
;
348 ira_loop_tree_node_t loop_tree_node
;
350 ira_allocno_iterator ai
;
352 max_regno
= max_reg_num ();
353 for (l
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, l
, loop
); l
++)
354 if (ira_loop_nodes
[l
].regno_allocno_map
!= NULL
)
356 ira_free (ira_loop_nodes
[l
].regno_allocno_map
);
357 ira_loop_nodes
[l
].regno_allocno_map
358 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
360 memset (ira_loop_nodes
[l
].regno_allocno_map
, 0,
361 sizeof (ira_allocno_t
) * max_regno
);
363 ira_free (ira_regno_allocno_map
);
364 ira_regno_allocno_map
365 = (ira_allocno_t
*) ira_allocate (max_regno
* sizeof (ira_allocno_t
));
366 memset (ira_regno_allocno_map
, 0, max_regno
* sizeof (ira_allocno_t
));
367 FOR_EACH_ALLOCNO (a
, ai
)
369 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
370 /* Caps are not in the regno allocno maps. */
372 regno
= ALLOCNO_REGNO (a
);
373 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
374 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
375 ira_regno_allocno_map
[regno
] = a
;
376 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
377 /* Remember that we can create temporary allocnos to break
378 cycles in register shuffle. */
379 loop_tree_node
->regno_allocno_map
[regno
] = a
;
385 /* Pools for allocnos and allocno live ranges. */
386 static alloc_pool allocno_pool
, allocno_live_range_pool
;
388 /* Vec containing references to all created allocnos. It is a
389 container of array allocnos. */
390 static VEC(ira_allocno_t
,heap
) *allocno_vec
;
392 /* Vec containing references to all created allocnos. It is a
393 container of ira_conflict_id_allocno_map. */
394 static VEC(ira_allocno_t
,heap
) *ira_conflict_id_allocno_map_vec
;
396 /* Initialize data concerning allocnos. */
398 initiate_allocnos (void)
400 allocno_live_range_pool
401 = create_alloc_pool ("allocno live ranges",
402 sizeof (struct ira_allocno_live_range
), 100);
404 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno
), 100);
405 allocno_vec
= VEC_alloc (ira_allocno_t
, heap
, max_reg_num () * 2);
407 ira_allocnos_num
= 0;
408 ira_conflict_id_allocno_map_vec
409 = VEC_alloc (ira_allocno_t
, heap
, max_reg_num () * 2);
410 ira_conflict_id_allocno_map
= NULL
;
411 ira_regno_allocno_map
412 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
413 memset (ira_regno_allocno_map
, 0, max_reg_num () * sizeof (ira_allocno_t
));
416 /* Create and return the allocno corresponding to REGNO in
417 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
418 same regno if CAP_P is FALSE. */
420 ira_create_allocno (int regno
, bool cap_p
, ira_loop_tree_node_t loop_tree_node
)
424 a
= (ira_allocno_t
) pool_alloc (allocno_pool
);
425 ALLOCNO_REGNO (a
) = regno
;
426 ALLOCNO_LOOP_TREE_NODE (a
) = loop_tree_node
;
429 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
430 ira_regno_allocno_map
[regno
] = a
;
431 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
432 /* Remember that we can create temporary allocnos to break
433 cycles in register shuffle on region borders (see
435 loop_tree_node
->regno_allocno_map
[regno
] = a
;
437 ALLOCNO_CAP (a
) = NULL
;
438 ALLOCNO_CAP_MEMBER (a
) = NULL
;
439 ALLOCNO_NUM (a
) = ira_allocnos_num
;
440 bitmap_set_bit (loop_tree_node
->all_allocnos
, ALLOCNO_NUM (a
));
441 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = NULL
;
442 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
443 COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
), ira_no_alloc_regs
);
444 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), ira_no_alloc_regs
);
445 ALLOCNO_NREFS (a
) = 0;
446 ALLOCNO_FREQ (a
) = 0;
447 ALLOCNO_HARD_REGNO (a
) = -1;
448 ALLOCNO_CALL_FREQ (a
) = 0;
449 ALLOCNO_CALLS_CROSSED_NUM (a
) = 0;
451 ALLOCNO_NO_STACK_REG_P (a
) = false;
452 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = false;
454 ALLOCNO_MEM_OPTIMIZED_DEST (a
) = NULL
;
455 ALLOCNO_MEM_OPTIMIZED_DEST_P (a
) = false;
456 ALLOCNO_SOMEWHERE_RENAMED_P (a
) = false;
457 ALLOCNO_CHILD_RENAMED_P (a
) = false;
458 ALLOCNO_DONT_REASSIGN_P (a
) = false;
459 ALLOCNO_IN_GRAPH_P (a
) = false;
460 ALLOCNO_ASSIGNED_P (a
) = false;
461 ALLOCNO_MAY_BE_SPILLED_P (a
) = false;
462 ALLOCNO_SPLAY_REMOVED_P (a
) = false;
463 ALLOCNO_CONFLICT_VEC_P (a
) = false;
464 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
465 ALLOCNO_COPIES (a
) = NULL
;
466 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
467 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
468 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
469 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
470 ALLOCNO_LEFT_CONFLICTS_NUM (a
) = -1;
471 ALLOCNO_COVER_CLASS (a
) = NO_REGS
;
472 ALLOCNO_COVER_CLASS_COST (a
) = 0;
473 ALLOCNO_MEMORY_COST (a
) = 0;
474 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
475 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
476 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = NULL
;
477 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
478 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
479 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
480 ALLOCNO_LIVE_RANGES (a
) = NULL
;
481 ALLOCNO_MIN (a
) = INT_MAX
;
482 ALLOCNO_MAX (a
) = -1;
483 ALLOCNO_CONFLICT_ID (a
) = ira_allocnos_num
;
484 VEC_safe_push (ira_allocno_t
, heap
, allocno_vec
, a
);
485 ira_allocnos
= VEC_address (ira_allocno_t
, allocno_vec
);
486 ira_allocnos_num
= VEC_length (ira_allocno_t
, allocno_vec
);
487 VEC_safe_push (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
, a
);
488 ira_conflict_id_allocno_map
489 = VEC_address (ira_allocno_t
, ira_conflict_id_allocno_map_vec
);
493 /* Set up cover class for A and update its conflict hard registers. */
495 ira_set_allocno_cover_class (ira_allocno_t a
, enum reg_class cover_class
)
497 ALLOCNO_COVER_CLASS (a
) = cover_class
;
498 IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
499 reg_class_contents
[cover_class
]);
500 IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
501 reg_class_contents
[cover_class
]);
504 /* Return TRUE if the conflict vector with NUM elements is more
505 profitable than conflict bit vector for A. */
507 ira_conflict_vector_profitable_p (ira_allocno_t a
, int num
)
511 if (ALLOCNO_MAX (a
) < ALLOCNO_MIN (a
))
512 /* We prefer bit vector in such case because it does not result in
516 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
) / IRA_INT_BITS
;
517 return (2 * sizeof (ira_allocno_t
) * (num
+ 1)
518 < 3 * nw
* sizeof (IRA_INT_TYPE
));
521 /* Allocates and initialize the conflict vector of A for NUM
522 conflicting allocnos. */
524 ira_allocate_allocno_conflict_vec (ira_allocno_t a
, int num
)
529 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
530 num
++; /* for NULL end marker */
531 size
= sizeof (ira_allocno_t
) * num
;
532 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
533 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
535 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
536 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
537 ALLOCNO_CONFLICT_VEC_P (a
) = true;
540 /* Allocate and initialize the conflict bit vector of A. */
542 allocate_allocno_conflict_bit_vec (ira_allocno_t a
)
546 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
547 size
= ((ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
)
548 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
549 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
550 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0, size
);
551 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
552 ALLOCNO_CONFLICT_VEC_P (a
) = false;
555 /* Allocate and initialize the conflict vector or conflict bit vector
556 of A for NUM conflicting allocnos whatever is more profitable. */
558 ira_allocate_allocno_conflicts (ira_allocno_t a
, int num
)
560 if (ira_conflict_vector_profitable_p (a
, num
))
561 ira_allocate_allocno_conflict_vec (a
, num
);
563 allocate_allocno_conflict_bit_vec (a
);
566 /* Add A2 to the conflicts of A1. */
568 add_to_allocno_conflicts (ira_allocno_t a1
, ira_allocno_t a2
)
573 if (ALLOCNO_CONFLICT_VEC_P (a1
))
577 num
= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
) + 2;
578 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
)
579 >= num
* sizeof (ira_allocno_t
))
580 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
583 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
584 vec
= (ira_allocno_t
*) ira_allocate (size
);
585 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
586 sizeof (ira_allocno_t
) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
));
587 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
588 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
589 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
593 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
)++;
597 int nw
, added_head_nw
, id
;
600 id
= ALLOCNO_CONFLICT_ID (a2
);
601 vec
= (IRA_INT_TYPE
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
602 if (ALLOCNO_MIN (a1
) > id
)
604 /* Expand head of the bit vector. */
605 added_head_nw
= (ALLOCNO_MIN (a1
) - id
- 1) / IRA_INT_BITS
+ 1;
606 nw
= (ALLOCNO_MAX (a1
) - ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
607 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
608 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) >= size
)
610 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
611 vec
, nw
* sizeof (IRA_INT_TYPE
));
612 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
617 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
618 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
619 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
620 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
621 nw
* sizeof (IRA_INT_TYPE
));
622 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
624 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
625 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
626 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
627 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
628 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
630 ALLOCNO_MIN (a1
) -= added_head_nw
* IRA_INT_BITS
;
632 else if (ALLOCNO_MAX (a1
) < id
)
634 nw
= (id
- ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
635 size
= nw
* sizeof (IRA_INT_TYPE
);
636 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) < size
)
638 /* Expand tail of the bit vector. */
639 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
640 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
641 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
642 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
643 memset ((char *) vec
+ ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
),
644 0, size
- ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
645 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
646 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
647 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
649 ALLOCNO_MAX (a1
) = id
;
651 SET_ALLOCNO_SET_BIT (vec
, id
, ALLOCNO_MIN (a1
), ALLOCNO_MAX (a1
));
655 /* Add A1 to the conflicts of A2 and vise versa. */
657 ira_add_allocno_conflict (ira_allocno_t a1
, ira_allocno_t a2
)
659 add_to_allocno_conflicts (a1
, a2
);
660 add_to_allocno_conflicts (a2
, a1
);
663 /* Clear all conflicts of allocno A. */
665 clear_allocno_conflicts (ira_allocno_t a
)
667 if (ALLOCNO_CONFLICT_VEC_P (a
))
669 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
670 ((ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
))[0] = NULL
;
672 else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) != 0)
676 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
)) / IRA_INT_BITS
+ 1;
677 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0,
678 nw
* sizeof (IRA_INT_TYPE
));
682 /* The array used to find duplications in conflict vectors of
684 static int *allocno_conflict_check
;
686 /* The value used to mark allocation presence in conflict vector of
687 the current allocno. */
688 static int curr_allocno_conflict_check_tick
;
690 /* Remove duplications in conflict vector of A. */
692 compress_allocno_conflict_vec (ira_allocno_t a
)
694 ira_allocno_t
*vec
, conflict_a
;
697 ira_assert (ALLOCNO_CONFLICT_VEC_P (a
));
698 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
699 curr_allocno_conflict_check_tick
++;
700 for (i
= j
= 0; (conflict_a
= vec
[i
]) != NULL
; i
++)
702 if (allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
703 != curr_allocno_conflict_check_tick
)
705 allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
706 = curr_allocno_conflict_check_tick
;
707 vec
[j
++] = conflict_a
;
710 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = j
;
714 /* Remove duplications in conflict vectors of all allocnos. */
716 compress_conflict_vecs (void)
719 ira_allocno_iterator ai
;
721 allocno_conflict_check
722 = (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
723 memset (allocno_conflict_check
, 0, sizeof (int) * ira_allocnos_num
);
724 curr_allocno_conflict_check_tick
= 0;
725 FOR_EACH_ALLOCNO (a
, ai
)
726 if (ALLOCNO_CONFLICT_VEC_P (a
))
727 compress_allocno_conflict_vec (a
);
728 ira_free (allocno_conflict_check
);
731 /* This recursive function outputs allocno A and if it is a cap the
732 function outputs its members. */
734 ira_print_expanded_allocno (ira_allocno_t a
)
738 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
739 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
740 fprintf (ira_dump_file
, ",b%d", bb
->index
);
742 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop
->num
);
743 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
745 fprintf (ira_dump_file
, ":");
746 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
748 fprintf (ira_dump_file
, ")");
751 /* Create and return the cap representing allocno A in the
754 create_cap_allocno (ira_allocno_t a
)
757 ira_loop_tree_node_t parent
;
758 enum reg_class cover_class
;
760 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
761 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) == a
);
762 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
763 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
764 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
765 cover_class
= ALLOCNO_COVER_CLASS (a
);
766 ira_set_allocno_cover_class (cap
, cover_class
);
767 ALLOCNO_AVAILABLE_REGS_NUM (cap
) = ALLOCNO_AVAILABLE_REGS_NUM (a
);
768 ALLOCNO_CAP_MEMBER (cap
) = a
;
769 ALLOCNO_CAP (a
) = cap
;
770 ALLOCNO_COVER_CLASS_COST (cap
) = ALLOCNO_COVER_CLASS_COST (a
);
771 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
772 ALLOCNO_UPDATED_MEMORY_COST (cap
) = ALLOCNO_UPDATED_MEMORY_COST (a
);
773 ira_allocate_and_copy_costs
774 (&ALLOCNO_HARD_REG_COSTS (cap
), cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
775 ira_allocate_and_copy_costs
776 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), cover_class
,
777 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
778 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
779 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
780 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
781 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap
),
782 ALLOCNO_CONFLICT_HARD_REGS (a
));
783 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap
),
784 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
785 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
787 ALLOCNO_NO_STACK_REG_P (cap
) = ALLOCNO_NO_STACK_REG_P (a
);
788 ALLOCNO_TOTAL_NO_STACK_REG_P (cap
) = ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
790 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
792 fprintf (ira_dump_file
, " Creating cap ");
793 ira_print_expanded_allocno (cap
);
794 fprintf (ira_dump_file
, "\n");
799 /* Create and return allocno live range with given attributes. */
801 ira_create_allocno_live_range (ira_allocno_t a
, int start
, int finish
,
802 allocno_live_range_t next
)
804 allocno_live_range_t p
;
806 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
814 /* Copy allocno live range R and return the result. */
815 static allocno_live_range_t
816 copy_allocno_live_range (allocno_live_range_t r
)
818 allocno_live_range_t p
;
820 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
825 /* Copy allocno live range list given by its head R and return the
827 static allocno_live_range_t
828 copy_allocno_live_range_list (allocno_live_range_t r
)
830 allocno_live_range_t p
, first
, last
;
834 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
836 p
= copy_allocno_live_range (r
);
846 /* Free allocno live range R. */
848 ira_finish_allocno_live_range (allocno_live_range_t r
)
850 pool_free (allocno_live_range_pool
, r
);
853 /* Free updated register costs of allocno A. */
855 ira_free_allocno_updated_costs (ira_allocno_t a
)
857 enum reg_class cover_class
;
859 cover_class
= ALLOCNO_COVER_CLASS (a
);
860 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
861 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
862 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
863 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
864 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
866 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
869 /* Free the memory allocated for allocno A. */
871 finish_allocno (ira_allocno_t a
)
873 allocno_live_range_t r
, next_r
;
874 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
876 ira_allocnos
[ALLOCNO_NUM (a
)] = NULL
;
877 ira_conflict_id_allocno_map
[ALLOCNO_CONFLICT_ID (a
)] = NULL
;
878 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) != NULL
)
879 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
));
880 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
881 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a
), cover_class
);
882 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
883 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
), cover_class
);
884 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
885 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
886 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
887 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
889 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= next_r
)
892 ira_finish_allocno_live_range (r
);
894 pool_free (allocno_pool
, a
);
897 /* Free the memory allocated for all allocnos. */
899 finish_allocnos (void)
902 ira_allocno_iterator ai
;
904 FOR_EACH_ALLOCNO (a
, ai
)
906 ira_free (ira_regno_allocno_map
);
907 VEC_free (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
);
908 VEC_free (ira_allocno_t
, heap
, allocno_vec
);
909 free_alloc_pool (allocno_pool
);
910 free_alloc_pool (allocno_live_range_pool
);
915 /* Pools for copies. */
916 static alloc_pool copy_pool
;
918 /* Vec containing references to all created copies. It is a
919 container of array ira_copies. */
920 static VEC(ira_copy_t
,heap
) *copy_vec
;
922 /* The function initializes data concerning allocno copies. */
924 initiate_copies (void)
927 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy
), 100);
928 copy_vec
= VEC_alloc (ira_copy_t
, heap
, get_max_uid ());
933 /* Return copy connecting A1 and A2 and originated from INSN of
934 LOOP_TREE_NODE if any. */
936 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx insn
,
937 ira_loop_tree_node_t loop_tree_node
)
939 ira_copy_t cp
, next_cp
;
940 ira_allocno_t another_a
;
942 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
946 next_cp
= cp
->next_first_allocno_copy
;
947 another_a
= cp
->second
;
949 else if (cp
->second
== a1
)
951 next_cp
= cp
->next_second_allocno_copy
;
952 another_a
= cp
->first
;
956 if (another_a
== a2
&& cp
->insn
== insn
957 && cp
->loop_tree_node
== loop_tree_node
)
963 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
964 SECOND, FREQ, and INSN. */
966 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
, rtx insn
,
967 ira_loop_tree_node_t loop_tree_node
)
971 cp
= (ira_copy_t
) pool_alloc (copy_pool
);
972 cp
->num
= ira_copies_num
;
977 cp
->loop_tree_node
= loop_tree_node
;
978 VEC_safe_push (ira_copy_t
, heap
, copy_vec
, cp
);
979 ira_copies
= VEC_address (ira_copy_t
, copy_vec
);
980 ira_copies_num
= VEC_length (ira_copy_t
, copy_vec
);
984 /* Attach a copy CP to allocnos involved into the copy. */
986 ira_add_allocno_copy_to_list (ira_copy_t cp
)
988 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
990 cp
->prev_first_allocno_copy
= NULL
;
991 cp
->prev_second_allocno_copy
= NULL
;
992 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
993 if (cp
->next_first_allocno_copy
!= NULL
)
995 if (cp
->next_first_allocno_copy
->first
== first
)
996 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
998 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1000 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1001 if (cp
->next_second_allocno_copy
!= NULL
)
1003 if (cp
->next_second_allocno_copy
->second
== second
)
1004 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1006 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1008 ALLOCNO_COPIES (first
) = cp
;
1009 ALLOCNO_COPIES (second
) = cp
;
1012 /* Detach a copy CP from allocnos involved into the copy. */
1014 ira_remove_allocno_copy_from_list (ira_copy_t cp
)
1016 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1017 ira_copy_t prev
, next
;
1019 next
= cp
->next_first_allocno_copy
;
1020 prev
= cp
->prev_first_allocno_copy
;
1022 ALLOCNO_COPIES (first
) = next
;
1023 else if (prev
->first
== first
)
1024 prev
->next_first_allocno_copy
= next
;
1026 prev
->next_second_allocno_copy
= next
;
1029 if (next
->first
== first
)
1030 next
->prev_first_allocno_copy
= prev
;
1032 next
->prev_second_allocno_copy
= prev
;
1034 cp
->prev_first_allocno_copy
= cp
->next_first_allocno_copy
= NULL
;
1036 next
= cp
->next_second_allocno_copy
;
1037 prev
= cp
->prev_second_allocno_copy
;
1039 ALLOCNO_COPIES (second
) = next
;
1040 else if (prev
->second
== second
)
1041 prev
->next_second_allocno_copy
= next
;
1043 prev
->next_first_allocno_copy
= next
;
1046 if (next
->second
== second
)
1047 next
->prev_second_allocno_copy
= prev
;
1049 next
->prev_first_allocno_copy
= prev
;
1051 cp
->prev_second_allocno_copy
= cp
->next_second_allocno_copy
= NULL
;
1054 /* Make a copy CP a canonical copy where number of the
1055 first allocno is less than the second one. */
1057 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1062 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1066 cp
->first
= cp
->second
;
1069 temp_cp
= cp
->prev_first_allocno_copy
;
1070 cp
->prev_first_allocno_copy
= cp
->prev_second_allocno_copy
;
1071 cp
->prev_second_allocno_copy
= temp_cp
;
1073 temp_cp
= cp
->next_first_allocno_copy
;
1074 cp
->next_first_allocno_copy
= cp
->next_second_allocno_copy
;
1075 cp
->next_second_allocno_copy
= temp_cp
;
1078 /* Create (or update frequency if the copy already exists) and return
1079 the copy of allocnos FIRST and SECOND with frequency FREQ
1080 corresponding to move insn INSN (if any) and originated from
1083 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1084 rtx insn
, ira_loop_tree_node_t loop_tree_node
)
1088 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1093 cp
= ira_create_copy (first
, second
, freq
, insn
, loop_tree_node
);
1094 ira_assert (first
!= NULL
&& second
!= NULL
);
1095 ira_add_allocno_copy_to_list (cp
);
1096 ira_swap_allocno_copy_ends_if_necessary (cp
);
1100 /* Print info about copy CP into file F. */
1102 print_copy (FILE *f
, ira_copy_t cp
)
1104 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d\n", cp
->num
,
1105 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1106 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
);
1109 /* Print info about copy CP into stderr. */
1111 ira_debug_copy (ira_copy_t cp
)
1113 print_copy (stderr
, cp
);
1116 /* Print info about all copies into file F. */
1118 print_copies (FILE *f
)
1121 ira_copy_iterator ci
;
1123 FOR_EACH_COPY (cp
, ci
)
1127 /* Print info about all copies into stderr. */
1129 ira_debug_copies (void)
1131 print_copies (stderr
);
1134 /* Print info about copies involving allocno A into file F. */
1136 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1138 ira_allocno_t another_a
;
1139 ira_copy_t cp
, next_cp
;
1141 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1142 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1146 next_cp
= cp
->next_first_allocno_copy
;
1147 another_a
= cp
->second
;
1149 else if (cp
->second
== a
)
1151 next_cp
= cp
->next_second_allocno_copy
;
1152 another_a
= cp
->first
;
1156 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1157 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1162 /* Print info about copies involving allocno A into stderr. */
1164 ira_debug_allocno_copies (ira_allocno_t a
)
1166 print_allocno_copies (stderr
, a
);
1169 /* The function frees memory allocated for copy CP. */
1171 finish_copy (ira_copy_t cp
)
1173 pool_free (copy_pool
, cp
);
1177 /* Free memory allocated for all copies. */
1179 finish_copies (void)
1182 ira_copy_iterator ci
;
1184 FOR_EACH_COPY (cp
, ci
)
1186 VEC_free (ira_copy_t
, heap
, copy_vec
);
1187 free_alloc_pool (copy_pool
);
1192 /* Pools for cost vectors. It is defined only for cover classes. */
1193 static alloc_pool cost_vector_pool
[N_REG_CLASSES
];
1195 /* The function initiates work with hard register cost vectors. It
1196 creates allocation pool for each cover class. */
1198 initiate_cost_vectors (void)
1201 enum reg_class cover_class
;
1203 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1205 cover_class
= ira_reg_class_cover
[i
];
1206 cost_vector_pool
[cover_class
]
1207 = create_alloc_pool ("cost vectors",
1209 * ira_class_hard_regs_num
[cover_class
],
1214 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1216 ira_allocate_cost_vector (enum reg_class cover_class
)
1218 return (int *) pool_alloc (cost_vector_pool
[cover_class
]);
1221 /* Free a cost vector VEC for COVER_CLASS. */
1223 ira_free_cost_vector (int *vec
, enum reg_class cover_class
)
1225 ira_assert (vec
!= NULL
);
1226 pool_free (cost_vector_pool
[cover_class
], vec
);
1229 /* Finish work with hard register cost vectors. Release allocation
1230 pool for each cover class. */
1232 finish_cost_vectors (void)
1235 enum reg_class cover_class
;
1237 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1239 cover_class
= ira_reg_class_cover
[i
];
1240 free_alloc_pool (cost_vector_pool
[cover_class
]);
1246 /* The current loop tree node and its regno allocno map. */
1247 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1248 ira_allocno_t
*ira_curr_regno_allocno_map
;
1250 /* This recursive function traverses loop tree with root LOOP_NODE
1251 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1252 correspondingly in preorder and postorder. The function sets up
1253 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1254 basic block nodes of LOOP_NODE is also processed (before its
1257 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1258 void (*preorder_func
) (ira_loop_tree_node_t
),
1259 void (*postorder_func
) (ira_loop_tree_node_t
))
1261 ira_loop_tree_node_t subloop_node
;
1263 ira_assert (loop_node
->bb
== NULL
);
1264 ira_curr_loop_tree_node
= loop_node
;
1265 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1267 if (preorder_func
!= NULL
)
1268 (*preorder_func
) (loop_node
);
1271 for (subloop_node
= loop_node
->children
;
1272 subloop_node
!= NULL
;
1273 subloop_node
= subloop_node
->next
)
1274 if (subloop_node
->bb
!= NULL
)
1276 if (preorder_func
!= NULL
)
1277 (*preorder_func
) (subloop_node
);
1279 if (postorder_func
!= NULL
)
1280 (*postorder_func
) (subloop_node
);
1283 for (subloop_node
= loop_node
->subloops
;
1284 subloop_node
!= NULL
;
1285 subloop_node
= subloop_node
->subloop_next
)
1287 ira_assert (subloop_node
->bb
== NULL
);
1288 ira_traverse_loop_tree (bb_p
, subloop_node
,
1289 preorder_func
, postorder_func
);
1292 ira_curr_loop_tree_node
= loop_node
;
1293 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1295 if (postorder_func
!= NULL
)
1296 (*postorder_func
) (loop_node
);
1301 /* The basic block currently being processed. */
1302 static basic_block curr_bb
;
1304 /* This recursive function creates allocnos corresponding to
1305 pseudo-registers containing in X. True OUTPUT_P means that X is
1308 create_insn_allocnos (rtx x
, bool output_p
)
1312 enum rtx_code code
= GET_CODE (x
);
1318 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1322 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1323 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1325 ALLOCNO_NREFS (a
)++;
1326 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1328 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1332 else if (code
== SET
)
1334 create_insn_allocnos (SET_DEST (x
), true);
1335 create_insn_allocnos (SET_SRC (x
), false);
1338 else if (code
== CLOBBER
)
1340 create_insn_allocnos (XEXP (x
, 0), true);
1343 else if (code
== MEM
)
1345 create_insn_allocnos (XEXP (x
, 0), false);
1348 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1349 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1351 create_insn_allocnos (XEXP (x
, 0), true);
1352 create_insn_allocnos (XEXP (x
, 0), false);
1356 fmt
= GET_RTX_FORMAT (code
);
1357 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1360 create_insn_allocnos (XEXP (x
, i
), output_p
);
1361 else if (fmt
[i
] == 'E')
1362 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1363 create_insn_allocnos (XVECEXP (x
, i
, j
), output_p
);
1367 /* Create allocnos corresponding to pseudo-registers living in the
1368 basic block represented by the corresponding loop tree node
1371 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1378 curr_bb
= bb
= bb_node
->bb
;
1379 ira_assert (bb
!= NULL
);
1380 FOR_BB_INSNS_REVERSE (bb
, insn
)
1382 create_insn_allocnos (PATTERN (insn
), false);
1383 /* It might be a allocno living through from one subloop to
1385 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1386 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1387 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1390 /* Create allocnos corresponding to pseudo-registers living on edge E
1391 (a loop entry or exit). Also mark the allocnos as living on the
1394 create_loop_allocnos (edge e
)
1397 bitmap live_in_regs
, border_allocnos
;
1399 ira_loop_tree_node_t parent
;
1401 live_in_regs
= DF_LR_IN (e
->dest
);
1402 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1403 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e
->src
),
1404 FIRST_PSEUDO_REGISTER
, i
, bi
)
1405 if (bitmap_bit_p (live_in_regs
, i
))
1407 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1409 /* The order of creations is important for right
1410 ira_regno_allocno_map. */
1411 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1412 && parent
->regno_allocno_map
[i
] == NULL
)
1413 ira_create_allocno (i
, false, parent
);
1414 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1416 bitmap_set_bit (border_allocnos
,
1417 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1421 /* Create allocnos corresponding to pseudo-registers living in loop
1422 represented by the corresponding loop tree node LOOP_NODE. This
1423 function is called by ira_traverse_loop_tree. */
1425 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1427 if (loop_node
->bb
!= NULL
)
1428 create_bb_allocnos (loop_node
);
1429 else if (loop_node
!= ira_loop_tree_root
)
1434 VEC (edge
, heap
) *edges
;
1436 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1437 if (e
->src
!= loop_node
->loop
->latch
)
1438 create_loop_allocnos (e
);
1440 edges
= get_loop_exit_edges (loop_node
->loop
);
1441 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1442 create_loop_allocnos (e
);
1443 VEC_free (edge
, heap
, edges
);
1447 /* Propagate information about allocnos modified inside the loop given
1448 by its LOOP_TREE_NODE to its parent. */
1450 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
1452 if (loop_tree_node
== ira_loop_tree_root
)
1454 ira_assert (loop_tree_node
->bb
== NULL
);
1455 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
1456 loop_tree_node
->modified_regnos
);
1459 /* Propagate new info about allocno A (see comments about accumulated
1460 info in allocno definition) to the corresponding allocno on upper
1461 loop tree level. So allocnos on upper levels accumulate
1462 information about the corresponding allocnos in nested regions.
1463 The new info means allocno info finally calculated in this
1466 propagate_allocno_info (void)
1469 ira_allocno_t a
, parent_a
;
1470 ira_loop_tree_node_t parent
;
1471 enum reg_class cover_class
;
1473 if (flag_ira_algorithm
!= IRA_ALGORITHM_REGIONAL
1474 && flag_ira_algorithm
!= IRA_ALGORITHM_MIXED
)
1476 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
1477 for (a
= ira_regno_allocno_map
[i
];
1479 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
1480 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
1481 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
1482 /* There are no caps yet at this point. So use
1483 border_allocnos to find allocnos for the propagation. */
1484 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
1487 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
1488 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
1489 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
1491 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
1492 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
1494 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
1495 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1496 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
1497 += ALLOCNO_CALLS_CROSSED_NUM (a
);
1498 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
1499 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1500 cover_class
= ALLOCNO_COVER_CLASS (a
);
1501 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (parent_a
));
1502 ira_allocate_and_accumulate_costs
1503 (&ALLOCNO_HARD_REG_COSTS (parent_a
), cover_class
,
1504 ALLOCNO_HARD_REG_COSTS (a
));
1505 ira_allocate_and_accumulate_costs
1506 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
1508 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
1509 ALLOCNO_COVER_CLASS_COST (parent_a
)
1510 += ALLOCNO_COVER_CLASS_COST (a
);
1511 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
1512 ALLOCNO_UPDATED_MEMORY_COST (parent_a
)
1513 += ALLOCNO_UPDATED_MEMORY_COST (a
);
1517 /* Create allocnos corresponding to pseudo-registers in the current
1518 function. Traverse the loop tree for this. */
1520 create_allocnos (void)
1522 /* We need to process BB first to correctly link allocnos by member
1523 next_regno_allocno. */
1524 ira_traverse_loop_tree (true, ira_loop_tree_root
,
1525 create_loop_tree_node_allocnos
, NULL
);
1527 ira_traverse_loop_tree (false, ira_loop_tree_root
, NULL
,
1528 propagate_modified_regnos
);
1533 /* The page contains function to remove some regions from a separate
1534 register allocation. We remove regions whose separate allocation
1535 will hardly improve the result. As a result we speed up regional
1536 register allocation. */
1538 /* Merge ranges R1 and R2 and returns the result. The function
1539 maintains the order of ranges and tries to minimize number of the
1541 static allocno_live_range_t
1542 merge_ranges (allocno_live_range_t r1
, allocno_live_range_t r2
)
1544 allocno_live_range_t first
, last
, temp
;
1550 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
1552 if (r1
->start
< r2
->start
)
1558 if (r1
->start
<= r2
->finish
+ 1)
1560 /* Intersected ranges: merge r1 and r2 into r1. */
1561 r1
->start
= r2
->start
;
1562 if (r1
->finish
< r2
->finish
)
1563 r1
->finish
= r2
->finish
;
1566 ira_finish_allocno_live_range (temp
);
1569 /* To try to merge with subsequent ranges in r1. */
1576 /* Add r1 to the result. */
1587 /* To try to merge with subsequent ranges in r2. */
1599 ira_assert (r1
->next
== NULL
);
1601 else if (r2
!= NULL
)
1607 ira_assert (r2
->next
== NULL
);
1611 ira_assert (last
->next
== NULL
);
1616 /* The function changes allocno in range list given by R onto A. */
1618 change_allocno_in_range_list (allocno_live_range_t r
, ira_allocno_t a
)
1620 for (; r
!= NULL
; r
= r
->next
)
1624 /* Return TRUE if NODE represents a loop with low register
1627 low_pressure_loop_node_p (ira_loop_tree_node_t node
)
1630 enum reg_class cover_class
;
1632 if (node
->bb
!= NULL
)
1635 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1637 cover_class
= ira_reg_class_cover
[i
];
1638 if (node
->reg_pressure
[cover_class
]
1639 > ira_available_class_regs
[cover_class
])
1645 /* Return TRUE if NODE represents a loop with should be removed from
1646 regional allocation. We remove a loop with low register pressure
1647 inside another loop with register pressure. In this case a
1648 separate allocation of the loop hardly helps (for irregular
1649 register file architecture it could help by choosing a better hard
1650 register in the loop but we prefer faster allocation even in this
1653 loop_node_to_be_removed_p (ira_loop_tree_node_t node
)
1655 return (node
->parent
!= NULL
&& low_pressure_loop_node_p (node
->parent
)
1656 && low_pressure_loop_node_p (node
));
1659 /* Definition of vector of loop tree nodes. */
1660 DEF_VEC_P(ira_loop_tree_node_t
);
1661 DEF_VEC_ALLOC_P(ira_loop_tree_node_t
, heap
);
1663 /* Vec containing references to all removed loop tree nodes. */
1664 static VEC(ira_loop_tree_node_t
,heap
) *removed_loop_vec
;
1666 /* Vec containing references to all children of loop tree nodes. */
1667 static VEC(ira_loop_tree_node_t
,heap
) *children_vec
;
1669 /* Remove subregions of NODE if their separate allocation will not
1670 improve the result. */
1672 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node
)
1676 ira_loop_tree_node_t subnode
;
1678 remove_p
= loop_node_to_be_removed_p (node
);
1680 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, node
);
1681 start
= VEC_length (ira_loop_tree_node_t
, children_vec
);
1682 for (subnode
= node
->children
; subnode
!= NULL
; subnode
= subnode
->next
)
1683 if (subnode
->bb
== NULL
)
1684 remove_uneccesary_loop_nodes_from_loop_tree (subnode
);
1686 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, subnode
);
1687 node
->children
= node
->subloops
= NULL
;
1690 VEC_safe_push (ira_loop_tree_node_t
, heap
, removed_loop_vec
, node
);
1693 while (VEC_length (ira_loop_tree_node_t
, children_vec
) > start
)
1695 subnode
= VEC_pop (ira_loop_tree_node_t
, children_vec
);
1696 subnode
->parent
= node
;
1697 subnode
->next
= node
->children
;
1698 node
->children
= subnode
;
1699 if (subnode
->bb
== NULL
)
1701 subnode
->subloop_next
= node
->subloops
;
1702 node
->subloops
= subnode
;
1707 /* Remove allocnos from loops removed from the allocation
1710 remove_unnecessary_allocnos (void)
1714 enum reg_class cover_class
;
1715 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
1716 ira_loop_tree_node_t a_node
, parent
;
1717 allocno_live_range_t r
;
1720 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
1721 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
1725 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
1726 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1727 if (! loop_node_to_be_removed_p (a_node
))
1731 for (parent
= a_node
->parent
;
1732 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
1733 && loop_node_to_be_removed_p (parent
);
1734 parent
= parent
->parent
)
1736 if (parent_a
== NULL
)
1738 /* There are no allocnos with the same regno in upper
1739 region -- just move the allocno to the upper
1742 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
1743 parent
->regno_allocno_map
[regno
] = a
;
1744 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
1748 /* Remove the allocno and update info of allocno in
1749 the upper region. */
1751 ira_regno_allocno_map
[regno
] = next_a
;
1753 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
1754 r
= ALLOCNO_LIVE_RANGES (a
);
1755 change_allocno_in_range_list (r
, parent_a
);
1756 ALLOCNO_LIVE_RANGES (parent_a
)
1757 = merge_ranges (r
, ALLOCNO_LIVE_RANGES (parent_a
));
1759 ALLOCNO_LIVE_RANGES (a
) = NULL
;
1760 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a
),
1761 ALLOCNO_CONFLICT_HARD_REGS (a
));
1763 if (ALLOCNO_NO_STACK_REG_P (a
))
1764 ALLOCNO_NO_STACK_REG_P (parent_a
) = true;
1766 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
1767 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
1768 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
1770 (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
1771 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1772 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
1773 += ALLOCNO_CALLS_CROSSED_NUM (a
);
1774 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
1775 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1777 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
1778 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
1780 cover_class
= ALLOCNO_COVER_CLASS (a
);
1781 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (parent_a
));
1782 ira_allocate_and_accumulate_costs
1783 (&ALLOCNO_HARD_REG_COSTS (parent_a
), cover_class
,
1784 ALLOCNO_HARD_REG_COSTS (a
));
1785 ira_allocate_and_accumulate_costs
1786 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
1788 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
1789 ALLOCNO_COVER_CLASS_COST (parent_a
)
1790 += ALLOCNO_COVER_CLASS_COST (a
);
1791 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
1792 ALLOCNO_UPDATED_MEMORY_COST (parent_a
)
1793 += ALLOCNO_UPDATED_MEMORY_COST (a
);
1799 ira_rebuild_start_finish_chains ();
1802 /* Remove loops from consideration. We remove loops for which a
1803 separate allocation will not improve the result. We have to do
1804 this after allocno creation and their costs and cover class
1805 evaluation because only after that the register pressure can be
1806 known and is calculated. */
1808 remove_unnecessary_regions (void)
1811 = VEC_alloc (ira_loop_tree_node_t
, heap
,
1812 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
1814 = VEC_alloc (ira_loop_tree_node_t
, heap
,
1815 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
1816 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
) ;
1817 VEC_free (ira_loop_tree_node_t
, heap
, children_vec
);
1818 remove_unnecessary_allocnos ();
1819 while (VEC_length (ira_loop_tree_node_t
, removed_loop_vec
) > 0)
1820 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t
, removed_loop_vec
));
1821 VEC_free (ira_loop_tree_node_t
, heap
, removed_loop_vec
);
1826 /* Set up minimal and maximal live range points for allocnos. */
1828 setup_min_max_allocno_live_range_point (void)
1831 ira_allocno_t a
, parent_a
, cap
;
1832 ira_allocno_iterator ai
;
1833 allocno_live_range_t r
;
1834 ira_loop_tree_node_t parent
;
1836 FOR_EACH_ALLOCNO (a
, ai
)
1838 r
= ALLOCNO_LIVE_RANGES (a
);
1841 ALLOCNO_MAX (a
) = r
->finish
;
1842 for (; r
->next
!= NULL
; r
= r
->next
)
1844 ALLOCNO_MIN (a
) = r
->start
;
1846 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
1847 for (a
= ira_regno_allocno_map
[i
];
1849 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
1851 if (ALLOCNO_MAX (a
) < 0)
1853 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
1854 /* Accumulation of range info. */
1855 if (ALLOCNO_CAP (a
) != NULL
)
1857 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
1859 if (ALLOCNO_MAX (cap
) < ALLOCNO_MAX (a
))
1860 ALLOCNO_MAX (cap
) = ALLOCNO_MAX (a
);
1861 if (ALLOCNO_MIN (cap
) > ALLOCNO_MIN (a
))
1862 ALLOCNO_MIN (cap
) = ALLOCNO_MIN (a
);
1866 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
1868 parent_a
= parent
->regno_allocno_map
[i
];
1869 if (ALLOCNO_MAX (parent_a
) < ALLOCNO_MAX (a
))
1870 ALLOCNO_MAX (parent_a
) = ALLOCNO_MAX (a
);
1871 if (ALLOCNO_MIN (parent_a
) > ALLOCNO_MIN (a
))
1872 ALLOCNO_MIN (parent_a
) = ALLOCNO_MIN (a
);
1874 #ifdef ENABLE_IRA_CHECKING
1875 FOR_EACH_ALLOCNO (a
, ai
)
1877 if ((0 <= ALLOCNO_MIN (a
) && ALLOCNO_MIN (a
) <= ira_max_point
)
1878 && (0 <= ALLOCNO_MAX (a
) && ALLOCNO_MAX (a
) <= ira_max_point
))
1885 /* Sort allocnos according to their live ranges. Allocnos with
1886 smaller cover class are put first. Allocnos with the same cove
1887 class are ordered according their start (min). Allocnos with the
1888 same start are ordered according their finish (max). */
1890 allocno_range_compare_func (const void *v1p
, const void *v2p
)
1893 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
1894 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
1896 if ((diff
= ALLOCNO_COVER_CLASS (a1
) - ALLOCNO_COVER_CLASS (a2
)) != 0)
1898 if ((diff
= ALLOCNO_MIN (a1
) - ALLOCNO_MIN (a2
)) != 0)
1900 if ((diff
= ALLOCNO_MAX (a1
) - ALLOCNO_MAX (a2
)) != 0)
1902 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
1905 /* Sort ira_conflict_id_allocno_map and set up conflict id of
1908 sort_conflict_id_allocno_map (void)
1912 ira_allocno_iterator ai
;
1915 FOR_EACH_ALLOCNO (a
, ai
)
1916 ira_conflict_id_allocno_map
[num
++] = a
;
1917 qsort (ira_conflict_id_allocno_map
, num
, sizeof (ira_allocno_t
),
1918 allocno_range_compare_func
);
1919 for (i
= 0; i
< num
; i
++)
1920 if ((a
= ira_conflict_id_allocno_map
[i
]) != NULL
)
1921 ALLOCNO_CONFLICT_ID (a
) = i
;
1922 for (i
= num
; i
< ira_allocnos_num
; i
++)
1923 ira_conflict_id_allocno_map
[i
] = NULL
;
1926 /* Set up minimal and maximal conflict ids of allocnos with which
1927 given allocno can conflict. */
1929 setup_min_max_conflict_allocno_ids (void)
1931 enum reg_class cover_class
;
1932 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
1933 int *live_range_min
, *last_lived
;
1936 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
1938 first_not_finished
= -1;
1939 for (i
= 0; i
< ira_allocnos_num
; i
++)
1941 a
= ira_conflict_id_allocno_map
[i
];
1944 if (cover_class
!= ALLOCNO_COVER_CLASS (a
))
1946 cover_class
= ALLOCNO_COVER_CLASS (a
);
1948 first_not_finished
= i
;
1952 start
= ALLOCNO_MIN (a
);
1953 /* If we skip an allocno, the allocno with smaller ids will
1954 be also skipped because of the secondary sorting the
1955 range finishes (see function
1956 allocno_range_compare_func). */
1957 while (first_not_finished
< i
1958 && start
> ALLOCNO_MAX (ira_conflict_id_allocno_map
1959 [first_not_finished
]))
1960 first_not_finished
++;
1961 min
= first_not_finished
;
1964 /* We could increase min further in this case but it is good
1967 live_range_min
[i
] = ALLOCNO_MIN (a
);
1968 ALLOCNO_MIN (a
) = min
;
1970 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
1972 filled_area_start
= -1;
1973 for (i
= ira_allocnos_num
- 1; i
>= 0; i
--)
1975 a
= ira_conflict_id_allocno_map
[i
];
1978 if (cover_class
!= ALLOCNO_COVER_CLASS (a
))
1980 cover_class
= ALLOCNO_COVER_CLASS (a
);
1981 for (j
= 0; j
< ira_max_point
; j
++)
1983 filled_area_start
= ira_max_point
;
1985 min
= live_range_min
[i
];
1986 finish
= ALLOCNO_MAX (a
);
1987 max
= last_lived
[finish
];
1989 /* We could decrease max further in this case but it is good
1991 max
= ALLOCNO_CONFLICT_ID (a
) - 1;
1992 ALLOCNO_MAX (a
) = max
;
1993 /* In filling, we can go further A range finish to recognize
1994 intersection quickly because if the finish of subsequently
1995 processed allocno (it has smaller conflict id) range is
1996 further A range finish than they are definitely intersected
1997 (the reason for this is the allocnos with bigger conflict id
1998 have their range starts not smaller than allocnos with
2000 for (j
= min
; j
< filled_area_start
; j
++)
2002 filled_area_start
= min
;
2004 ira_free (last_lived
);
2005 ira_free (live_range_min
);
2014 ira_allocno_iterator ai
;
2015 ira_loop_tree_node_t loop_tree_node
;
2017 FOR_EACH_ALLOCNO (a
, ai
)
2019 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2021 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2022 create_cap_allocno (a
);
2023 else if (ALLOCNO_CAP (a
) == NULL
)
2025 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2026 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2027 create_cap_allocno (a
);
2034 /* The page contains code transforming more one region internal
2035 representation (IR) to one region IR which is necessary for reload.
2036 This transformation is called IR flattening. We might just rebuild
2037 the IR for one region but we don't do it because it takes a lot of
2040 /* Map: regno -> allocnos which will finally represent the regno for
2041 IR with one region. */
2042 static ira_allocno_t
*regno_top_level_allocno_map
;
2044 /* Process all allocnos originated from pseudo REGNO and copy live
2045 ranges from low level allocnos to final allocnos which are
2046 destinations of removed stores at a loop exit. Return true if we
2047 copied live ranges. */
2049 copy_live_ranges_to_removed_store_destinations (int regno
)
2051 ira_allocno_t a
, parent_a
;
2052 ira_loop_tree_node_t parent
;
2053 allocno_live_range_t r
;
2057 for (a
= ira_regno_allocno_map
[regno
];
2059 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2061 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))])
2062 /* This allocno will be removed. */
2064 /* Caps will be removed. */
2065 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2066 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
2068 parent
= parent
->parent
)
2069 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2070 || (parent_a
== regno_top_level_allocno_map
[REGNO (ALLOCNO_REG
2072 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)))
2074 if (parent
== NULL
|| parent_a
== NULL
)
2076 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2080 " Coping ranges of a%dr%d to a%dr%d: ",
2081 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2082 ALLOCNO_NUM (parent_a
), REGNO (ALLOCNO_REG (parent_a
)));
2083 ira_print_live_range_list (ira_dump_file
,
2084 ALLOCNO_LIVE_RANGES (a
));
2086 r
= copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2087 change_allocno_in_range_list (r
, parent_a
);
2088 ALLOCNO_LIVE_RANGES (parent_a
)
2089 = merge_ranges (r
, ALLOCNO_LIVE_RANGES (parent_a
));
2095 /* Flatten the IR. In other words, this function transforms IR as if
2096 it were built with one region (without loops). We could make it
2097 much simpler by rebuilding IR with one region, but unfortunately it
2098 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
2099 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2100 IRA_MAX_POINT before emitting insns on the loop borders. */
2102 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
2105 bool stop_p
, keep_p
;
2107 bool new_pseudos_p
, merged_p
, mem_dest_p
;
2109 enum reg_class cover_class
;
2110 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
2112 ira_loop_tree_node_t parent
, node
;
2113 allocno_live_range_t r
;
2114 ira_allocno_iterator ai
;
2115 ira_copy_iterator ci
;
2116 sparseset allocnos_live
;
2118 regno_top_level_allocno_map
2119 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
2120 memset (regno_top_level_allocno_map
, 0,
2121 max_reg_num () * sizeof (ira_allocno_t
));
2122 new_pseudos_p
= merged_p
= false;
2123 FOR_EACH_ALLOCNO (a
, ai
)
2125 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2126 /* Caps are not in the regno allocno maps and they are never
2127 will be transformed into allocnos existing after IR
2130 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
2131 ALLOCNO_CONFLICT_HARD_REGS (a
));
2133 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
2136 /* Fix final allocno attributes. */
2137 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2140 for (a
= ira_regno_allocno_map
[i
];
2142 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2144 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2145 if (ALLOCNO_SOMEWHERE_RENAMED_P (a
))
2146 new_pseudos_p
= true;
2147 if (ALLOCNO_CAP (a
) != NULL
2148 || (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
2149 || ((parent_a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)])
2152 ALLOCNO_COPIES (a
) = NULL
;
2153 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2156 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
2158 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) != NULL
)
2160 if (REGNO (ALLOCNO_REG (a
)) == REGNO (ALLOCNO_REG (parent_a
)))
2162 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2163 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2165 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2166 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
2168 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2170 fprintf (ira_dump_file
,
2171 " Moving ranges of a%dr%d to a%dr%d: ",
2172 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2173 ALLOCNO_NUM (parent_a
),
2174 REGNO (ALLOCNO_REG (parent_a
)));
2175 ira_print_live_range_list (ira_dump_file
,
2176 ALLOCNO_LIVE_RANGES (a
));
2178 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a
), parent_a
);
2179 ALLOCNO_LIVE_RANGES (parent_a
)
2180 = merge_ranges (ALLOCNO_LIVE_RANGES (a
),
2181 ALLOCNO_LIVE_RANGES (parent_a
));
2183 ALLOCNO_LIVE_RANGES (a
) = NULL
;
2184 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2185 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2186 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
));
2189 new_pseudos_p
= true;
2190 first
= ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
? NULL
: a
;
2195 && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a
) != NULL
)
2197 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
2198 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
2200 && ALLOCNO_MEM_OPTIMIZED_DEST (first
) == parent_a
)
2204 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
2205 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2206 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
2207 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2208 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2210 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
2211 && ALLOCNO_NREFS (parent_a
) >= 0
2212 && ALLOCNO_FREQ (parent_a
) >= 0);
2213 cover_class
= ALLOCNO_COVER_CLASS (parent_a
);
2214 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
2215 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
2216 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
2217 for (j
= 0; j
< hard_regs_num
; j
++)
2218 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
2219 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
2220 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
2221 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
2222 for (j
= 0; j
< hard_regs_num
; j
++)
2223 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
2224 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
2225 ALLOCNO_COVER_CLASS_COST (parent_a
)
2226 -= ALLOCNO_COVER_CLASS_COST (a
);
2227 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
2228 if (ALLOCNO_CAP (parent_a
) != NULL
2230 = ALLOCNO_LOOP_TREE_NODE (parent_a
)->parent
) == NULL
2231 || (parent_a
= (parent
->regno_allocno_map
2232 [ALLOCNO_REGNO (parent_a
)])) == NULL
)
2235 ALLOCNO_COPIES (a
) = NULL
;
2236 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2238 if (mem_dest_p
&& copy_live_ranges_to_removed_store_destinations (i
))
2241 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
2242 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
2243 ira_rebuild_start_finish_chains ();
2246 /* Rebuild conflicts. */
2247 FOR_EACH_ALLOCNO (a
, ai
)
2249 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2250 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2252 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2253 ira_assert (r
->allocno
== a
);
2254 clear_allocno_conflicts (a
);
2256 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
2257 for (i
= 0; i
< ira_max_point
; i
++)
2259 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
2262 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2263 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2265 num
= ALLOCNO_NUM (a
);
2266 cover_class
= ALLOCNO_COVER_CLASS (a
);
2267 sparseset_set_bit (allocnos_live
, num
);
2268 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, n
)
2270 ira_allocno_t live_a
= ira_allocnos
[n
];
2272 if (cover_class
== ALLOCNO_COVER_CLASS (live_a
)
2273 /* Don't set up conflict for the allocno with itself. */
2275 ira_add_allocno_conflict (a
, live_a
);
2279 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
2280 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (r
->allocno
));
2282 sparseset_free (allocnos_live
);
2283 compress_conflict_vecs ();
2285 /* Mark some copies for removing and change allocnos in the rest
2287 FOR_EACH_COPY (cp
, ci
)
2289 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
2290 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
2292 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2294 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2295 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
2296 ALLOCNO_NUM (cp
->first
), REGNO (ALLOCNO_REG (cp
->first
)),
2297 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
2298 ALLOCNO_NUM (cp
->second
), REGNO (ALLOCNO_REG (cp
->second
)));
2299 cp
->loop_tree_node
= NULL
;
2302 first
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->first
))];
2303 second
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->second
))];
2304 node
= cp
->loop_tree_node
;
2306 keep_p
= true; /* It copy generated in ira-emit.c. */
2309 /* Check that the copy was not propagated from level on
2310 which we will have different pseudos. */
2311 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
2312 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
2313 keep_p
= ((REGNO (ALLOCNO_REG (first
))
2314 == REGNO (ALLOCNO_REG (node_first
)))
2315 && (REGNO (ALLOCNO_REG (second
))
2316 == REGNO (ALLOCNO_REG (node_second
))));
2320 cp
->loop_tree_node
= ira_loop_tree_root
;
2322 cp
->second
= second
;
2326 cp
->loop_tree_node
= NULL
;
2327 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2328 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
2329 cp
->num
, ALLOCNO_NUM (cp
->first
),
2330 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
2331 REGNO (ALLOCNO_REG (cp
->second
)));
2334 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2335 FOR_EACH_ALLOCNO (a
, ai
)
2337 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2338 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2340 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2341 fprintf (ira_dump_file
, " Remove a%dr%d\n",
2342 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
2346 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2347 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_REG (a
));
2348 ALLOCNO_CAP (a
) = NULL
;
2349 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
2350 if (! ALLOCNO_ASSIGNED_P (a
))
2351 ira_free_allocno_updated_costs (a
);
2352 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2353 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2355 /* Remove unnecessary copies. */
2356 FOR_EACH_COPY (cp
, ci
)
2358 if (cp
->loop_tree_node
== NULL
)
2360 ira_copies
[cp
->num
] = NULL
;
2365 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
2366 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
2367 ira_add_allocno_copy_to_list (cp
);
2368 ira_swap_allocno_copy_ends_if_necessary (cp
);
2370 rebuild_regno_allocno_maps ();
2371 if (ira_max_point
!= ira_max_point_before_emit
)
2372 ira_compress_allocno_live_ranges ();
2373 ira_free (regno_top_level_allocno_map
);
2378 #ifdef ENABLE_IRA_CHECKING
2379 /* Check creation of all allocnos. Allocnos on lower levels should
2380 have allocnos or caps on all upper levels. */
2382 check_allocno_creation (void)
2385 ira_allocno_iterator ai
;
2386 ira_loop_tree_node_t loop_tree_node
;
2388 FOR_EACH_ALLOCNO (a
, ai
)
2390 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2391 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
2393 if (loop_tree_node
== ira_loop_tree_root
)
2395 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2396 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2397 else if (ALLOCNO_CAP (a
) == NULL
)
2398 ira_assert (loop_tree_node
->parent
2399 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
2400 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
2406 /* Create a internal representation (IR) for IRA (allocnos, copies,
2407 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2408 the loops (except the root which corresponds the all function) and
2409 correspondingly allocnos for the loops will be not created. Such
2410 parameter value is used for Chaitin-Briggs coloring. The function
2411 returns TRUE if we generate loop structure (besides nodes
2412 representing all function and the basic blocks) for regional
2413 allocation. A true return means that we really need to flatten IR
2414 before the reload. */
2416 ira_build (bool loops_p
)
2420 initiate_cost_vectors ();
2421 initiate_allocnos ();
2423 create_loop_tree_nodes (loops_p
);
2427 ira_create_allocno_live_ranges ();
2428 remove_unnecessary_regions ();
2429 ira_compress_allocno_live_ranges ();
2430 loops_p
= more_one_region_p ();
2433 propagate_allocno_info ();
2436 ira_tune_allocno_costs_and_cover_classes ();
2437 #ifdef ENABLE_IRA_CHECKING
2438 check_allocno_creation ();
2440 setup_min_max_allocno_live_range_point ();
2441 sort_conflict_id_allocno_map ();
2442 setup_min_max_conflict_allocno_ids ();
2443 ira_build_conflicts ();
2444 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2445 print_copies (ira_dump_file
);
2446 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2450 allocno_live_range_t r
;
2451 ira_allocno_iterator ai
;
2454 FOR_EACH_ALLOCNO (a
, ai
)
2455 n
+= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
);
2457 FOR_EACH_ALLOCNO (a
, ai
)
2458 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2460 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
2461 VEC_length (loop_p
, ira_loops
.larray
), n_basic_blocks
,
2463 fprintf (ira_dump_file
,
2464 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2465 ira_allocnos_num
, ira_copies_num
, n
, nr
);
2470 /* Release the data created by function ira_build. */
2474 finish_loop_tree_nodes ();
2477 finish_cost_vectors ();
2478 ira_finish_allocno_live_ranges ();