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 propagate_p
, 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
;
2117 bool *allocno_propagated_p
;
2119 regno_top_level_allocno_map
2120 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
2121 memset (regno_top_level_allocno_map
, 0,
2122 max_reg_num () * sizeof (ira_allocno_t
));
2123 allocno_propagated_p
2124 = (bool *) ira_allocate (ira_allocnos_num
* sizeof (bool));
2125 memset (allocno_propagated_p
, 0, ira_allocnos_num
* sizeof (bool));
2126 new_pseudos_p
= merged_p
= false;
2127 /* Fix final allocno attributes. */
2128 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2130 mem_dest_p
= propagate_p
= false;
2131 for (a
= ira_regno_allocno_map
[i
];
2133 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2135 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2136 if (ALLOCNO_SOMEWHERE_RENAMED_P (a
))
2137 new_pseudos_p
= true;
2138 if (ALLOCNO_CAP (a
) != NULL
2139 || (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
2140 || ((parent_a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)])
2143 ALLOCNO_COPIES (a
) = NULL
;
2144 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2147 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
2148 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) != NULL
)
2152 if (!allocno_propagated_p
[ALLOCNO_NUM (parent_a
)])
2153 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2154 ALLOCNO_CONFLICT_HARD_REGS (parent_a
));
2155 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2156 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2158 if (!allocno_propagated_p
[ALLOCNO_NUM (parent_a
)])
2159 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
)
2160 = ALLOCNO_NO_STACK_REG_P (parent_a
);
2161 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
)
2162 = (ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
)
2163 || ALLOCNO_TOTAL_NO_STACK_REG_P (a
));
2165 allocno_propagated_p
[ALLOCNO_NUM (parent_a
)] = true;
2167 if (REGNO (ALLOCNO_REG (a
)) == REGNO (ALLOCNO_REG (parent_a
)))
2169 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2171 fprintf (ira_dump_file
,
2172 " Moving ranges of a%dr%d to a%dr%d: ",
2173 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2174 ALLOCNO_NUM (parent_a
),
2175 REGNO (ALLOCNO_REG (parent_a
)));
2176 ira_print_live_range_list (ira_dump_file
,
2177 ALLOCNO_LIVE_RANGES (a
));
2179 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a
), parent_a
);
2180 ALLOCNO_LIVE_RANGES (parent_a
)
2181 = merge_ranges (ALLOCNO_LIVE_RANGES (a
),
2182 ALLOCNO_LIVE_RANGES (parent_a
));
2184 ALLOCNO_LIVE_RANGES (a
) = NULL
;
2185 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2186 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2187 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
));
2190 new_pseudos_p
= true;
2192 first
= ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
? NULL
: a
;
2197 && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a
) != NULL
)
2199 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
2200 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
2202 && ALLOCNO_MEM_OPTIMIZED_DEST (first
) == parent_a
)
2206 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
2207 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2208 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
2209 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2210 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2212 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
2213 && ALLOCNO_NREFS (parent_a
) >= 0
2214 && ALLOCNO_FREQ (parent_a
) >= 0);
2215 cover_class
= ALLOCNO_COVER_CLASS (parent_a
);
2216 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
2217 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
2218 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
2219 for (j
= 0; j
< hard_regs_num
; j
++)
2220 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
2221 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
2222 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
2223 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
2224 for (j
= 0; j
< hard_regs_num
; j
++)
2225 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
2226 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
2227 ALLOCNO_COVER_CLASS_COST (parent_a
)
2228 -= ALLOCNO_COVER_CLASS_COST (a
);
2229 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
2230 if (ALLOCNO_CAP (parent_a
) != NULL
2232 = ALLOCNO_LOOP_TREE_NODE (parent_a
)->parent
) == NULL
2233 || (parent_a
= (parent
->regno_allocno_map
2234 [ALLOCNO_REGNO (parent_a
)])) == NULL
)
2237 ALLOCNO_COPIES (a
) = NULL
;
2238 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2240 if (mem_dest_p
&& copy_live_ranges_to_removed_store_destinations (i
))
2243 ira_free (allocno_propagated_p
);
2244 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
2245 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
2246 ira_rebuild_start_finish_chains ();
2249 /* Rebuild conflicts. */
2250 FOR_EACH_ALLOCNO (a
, ai
)
2252 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2253 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2255 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2256 ira_assert (r
->allocno
== a
);
2257 clear_allocno_conflicts (a
);
2259 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
2260 for (i
= 0; i
< ira_max_point
; i
++)
2262 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
2265 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2266 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2268 num
= ALLOCNO_NUM (a
);
2269 cover_class
= ALLOCNO_COVER_CLASS (a
);
2270 sparseset_set_bit (allocnos_live
, num
);
2271 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, n
)
2273 ira_allocno_t live_a
= ira_allocnos
[n
];
2275 if (cover_class
== ALLOCNO_COVER_CLASS (live_a
)
2276 /* Don't set up conflict for the allocno with itself. */
2278 ira_add_allocno_conflict (a
, live_a
);
2282 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
2283 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (r
->allocno
));
2285 sparseset_free (allocnos_live
);
2286 compress_conflict_vecs ();
2288 /* Mark some copies for removing and change allocnos in the rest
2290 FOR_EACH_COPY (cp
, ci
)
2292 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
2293 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
2295 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2297 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2298 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
2299 ALLOCNO_NUM (cp
->first
), REGNO (ALLOCNO_REG (cp
->first
)),
2300 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
2301 ALLOCNO_NUM (cp
->second
), REGNO (ALLOCNO_REG (cp
->second
)));
2302 cp
->loop_tree_node
= NULL
;
2305 first
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->first
))];
2306 second
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->second
))];
2307 node
= cp
->loop_tree_node
;
2309 keep_p
= true; /* It copy generated in ira-emit.c. */
2312 /* Check that the copy was not propagated from level on
2313 which we will have different pseudos. */
2314 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
2315 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
2316 keep_p
= ((REGNO (ALLOCNO_REG (first
))
2317 == REGNO (ALLOCNO_REG (node_first
)))
2318 && (REGNO (ALLOCNO_REG (second
))
2319 == REGNO (ALLOCNO_REG (node_second
))));
2323 cp
->loop_tree_node
= ira_loop_tree_root
;
2325 cp
->second
= second
;
2329 cp
->loop_tree_node
= NULL
;
2330 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2331 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
2332 cp
->num
, ALLOCNO_NUM (cp
->first
),
2333 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
2334 REGNO (ALLOCNO_REG (cp
->second
)));
2337 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2338 FOR_EACH_ALLOCNO (a
, ai
)
2340 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2341 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2343 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2344 fprintf (ira_dump_file
, " Remove a%dr%d\n",
2345 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
2349 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2350 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_REG (a
));
2351 ALLOCNO_CAP (a
) = NULL
;
2352 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
2353 if (! ALLOCNO_ASSIGNED_P (a
))
2354 ira_free_allocno_updated_costs (a
);
2355 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2356 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2358 /* Remove unnecessary copies. */
2359 FOR_EACH_COPY (cp
, ci
)
2361 if (cp
->loop_tree_node
== NULL
)
2363 ira_copies
[cp
->num
] = NULL
;
2368 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
2369 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
2370 ira_add_allocno_copy_to_list (cp
);
2371 ira_swap_allocno_copy_ends_if_necessary (cp
);
2373 rebuild_regno_allocno_maps ();
2374 if (ira_max_point
!= ira_max_point_before_emit
)
2375 ira_compress_allocno_live_ranges ();
2376 ira_free (regno_top_level_allocno_map
);
2381 #ifdef ENABLE_IRA_CHECKING
2382 /* Check creation of all allocnos. Allocnos on lower levels should
2383 have allocnos or caps on all upper levels. */
2385 check_allocno_creation (void)
2388 ira_allocno_iterator ai
;
2389 ira_loop_tree_node_t loop_tree_node
;
2391 FOR_EACH_ALLOCNO (a
, ai
)
2393 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2394 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
2396 if (loop_tree_node
== ira_loop_tree_root
)
2398 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2399 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2400 else if (ALLOCNO_CAP (a
) == NULL
)
2401 ira_assert (loop_tree_node
->parent
2402 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
2403 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
2409 /* Create a internal representation (IR) for IRA (allocnos, copies,
2410 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2411 the loops (except the root which corresponds the all function) and
2412 correspondingly allocnos for the loops will be not created. Such
2413 parameter value is used for Chaitin-Briggs coloring. The function
2414 returns TRUE if we generate loop structure (besides nodes
2415 representing all function and the basic blocks) for regional
2416 allocation. A true return means that we really need to flatten IR
2417 before the reload. */
2419 ira_build (bool loops_p
)
2423 initiate_cost_vectors ();
2424 initiate_allocnos ();
2426 create_loop_tree_nodes (loops_p
);
2430 ira_create_allocno_live_ranges ();
2431 remove_unnecessary_regions ();
2432 ira_compress_allocno_live_ranges ();
2433 loops_p
= more_one_region_p ();
2436 propagate_allocno_info ();
2439 ira_tune_allocno_costs_and_cover_classes ();
2440 #ifdef ENABLE_IRA_CHECKING
2441 check_allocno_creation ();
2443 setup_min_max_allocno_live_range_point ();
2444 sort_conflict_id_allocno_map ();
2445 setup_min_max_conflict_allocno_ids ();
2446 ira_build_conflicts ();
2447 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2448 print_copies (ira_dump_file
);
2449 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2453 allocno_live_range_t r
;
2454 ira_allocno_iterator ai
;
2457 FOR_EACH_ALLOCNO (a
, ai
)
2458 n
+= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
);
2460 FOR_EACH_ALLOCNO (a
, ai
)
2461 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2463 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
2464 VEC_length (loop_p
, ira_loops
.larray
), n_basic_blocks
,
2466 fprintf (ira_dump_file
,
2467 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2468 ira_allocnos_num
, ira_copies_num
, n
, nr
);
2473 /* Release the data created by function ira_build. */
2477 finish_loop_tree_nodes ();
2480 finish_cost_vectors ();
2481 ira_finish_allocno_live_ranges ();