1 /* Building internal representation for IRA.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
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"
42 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
44 static ira_copy_t
find_allocno_copy (ira_allocno_t
, ira_allocno_t
, rtx
,
45 ira_loop_tree_node_t
);
47 /* The root of the loop tree corresponding to the all function. */
48 ira_loop_tree_node_t ira_loop_tree_root
;
50 /* Height of the loop tree. */
51 int ira_loop_tree_height
;
53 /* All nodes representing basic blocks are referred through the
54 following array. We can not use basic block member `aux' for this
55 because it is used for insertion of insns on edges. */
56 ira_loop_tree_node_t ira_bb_nodes
;
58 /* All nodes representing loops are referred through the following
60 ira_loop_tree_node_t ira_loop_nodes
;
62 /* Map regno -> allocnos with given regno (see comments for
63 allocno member `next_regno_allocno'). */
64 ira_allocno_t
*ira_regno_allocno_map
;
66 /* Array of references to all allocnos. The order number of the
67 allocno corresponds to the index in the array. Removed allocnos
68 have NULL element value. */
69 ira_allocno_t
*ira_allocnos
;
71 /* Sizes of the previous array. */
74 /* Map conflict id -> allocno with given conflict id (see comments for
75 allocno member `conflict_id'). */
76 ira_allocno_t
*ira_conflict_id_allocno_map
;
78 /* Array of references to all copies. The order number of the copy
79 corresponds to the index in the array. Removed copies have NULL
81 ira_copy_t
*ira_copies
;
83 /* Size of the previous array. */
88 /* LAST_BASIC_BLOCK before generating additional insns because of live
89 range splitting. Emitting insns on a critical edge creates a new
91 static int last_basic_block_before_change
;
93 /* The following function allocates the loop tree nodes. If LOOPS_P
94 is FALSE, the nodes corresponding to the loops (except the root
95 which corresponds the all function) will be not allocated but nodes
96 will still be allocated for basic blocks. */
98 create_loop_tree_nodes (bool loops_p
)
105 VEC (edge
, heap
) *edges
;
109 = ((struct ira_loop_tree_node
*)
110 ira_allocate (sizeof (struct ira_loop_tree_node
) * last_basic_block
));
111 last_basic_block_before_change
= last_basic_block
;
112 for (i
= 0; i
< (unsigned int) last_basic_block
; i
++)
114 ira_bb_nodes
[i
].regno_allocno_map
= NULL
;
115 memset (ira_bb_nodes
[i
].reg_pressure
, 0,
116 sizeof (ira_bb_nodes
[i
].reg_pressure
));
117 ira_bb_nodes
[i
].all_allocnos
= NULL
;
118 ira_bb_nodes
[i
].modified_regnos
= NULL
;
119 ira_bb_nodes
[i
].border_allocnos
= NULL
;
120 ira_bb_nodes
[i
].local_copies
= NULL
;
122 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
123 ira_allocate (sizeof (struct ira_loop_tree_node
)
124 * VEC_length (loop_p
, ira_loops
.larray
)));
125 max_regno
= max_reg_num ();
126 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
128 if (loop
!= ira_loops
.tree_root
)
130 ira_loop_nodes
[i
].regno_allocno_map
= NULL
;
134 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
135 if (e
->src
!= loop
->latch
136 && (e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
143 edges
= get_loop_exit_edges (loop
);
144 for (j
= 0; VEC_iterate (edge
, edges
, j
, e
); j
++)
145 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
150 VEC_free (edge
, heap
, edges
);
154 ira_loop_nodes
[i
].regno_allocno_map
155 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
) * max_regno
);
156 memset (ira_loop_nodes
[i
].regno_allocno_map
, 0,
157 sizeof (ira_allocno_t
) * max_regno
);
158 memset (ira_loop_nodes
[i
].reg_pressure
, 0,
159 sizeof (ira_loop_nodes
[i
].reg_pressure
));
160 ira_loop_nodes
[i
].all_allocnos
= ira_allocate_bitmap ();
161 ira_loop_nodes
[i
].modified_regnos
= ira_allocate_bitmap ();
162 ira_loop_nodes
[i
].border_allocnos
= ira_allocate_bitmap ();
163 ira_loop_nodes
[i
].local_copies
= ira_allocate_bitmap ();
167 /* The function returns TRUE if there are more one allocation
170 more_one_region_p (void)
175 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
176 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
177 && ira_loop_tree_root
!= &ira_loop_nodes
[i
])
182 /* Free the loop tree node of a loop. */
184 finish_loop_tree_node (ira_loop_tree_node_t loop
)
186 if (loop
->regno_allocno_map
!= NULL
)
188 ira_assert (loop
->bb
== NULL
);
189 ira_free_bitmap (loop
->local_copies
);
190 ira_free_bitmap (loop
->border_allocnos
);
191 ira_free_bitmap (loop
->modified_regnos
);
192 ira_free_bitmap (loop
->all_allocnos
);
193 ira_free (loop
->regno_allocno_map
);
194 loop
->regno_allocno_map
= NULL
;
198 /* Free the loop tree nodes. */
200 finish_loop_tree_nodes (void)
205 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
206 finish_loop_tree_node (&ira_loop_nodes
[i
]);
207 ira_free (ira_loop_nodes
);
208 for (i
= 0; i
< (unsigned int) last_basic_block_before_change
; i
++)
210 if (ira_bb_nodes
[i
].local_copies
!= NULL
)
211 ira_free_bitmap (ira_bb_nodes
[i
].local_copies
);
212 if (ira_bb_nodes
[i
].border_allocnos
!= NULL
)
213 ira_free_bitmap (ira_bb_nodes
[i
].border_allocnos
);
214 if (ira_bb_nodes
[i
].modified_regnos
!= NULL
)
215 ira_free_bitmap (ira_bb_nodes
[i
].modified_regnos
);
216 if (ira_bb_nodes
[i
].all_allocnos
!= NULL
)
217 ira_free_bitmap (ira_bb_nodes
[i
].all_allocnos
);
218 if (ira_bb_nodes
[i
].regno_allocno_map
!= NULL
)
219 ira_free (ira_bb_nodes
[i
].regno_allocno_map
);
221 ira_free (ira_bb_nodes
);
226 /* The following recursive function adds LOOP to the loop tree
227 hierarchy. LOOP is added only once. */
229 add_loop_to_tree (struct loop
*loop
)
232 ira_loop_tree_node_t loop_node
, parent_node
;
234 /* We can not use loop node access macros here because of potential
235 checking and because the nodes are not initialized enough
237 if (loop_outer (loop
) != NULL
)
238 add_loop_to_tree (loop_outer (loop
));
239 if (ira_loop_nodes
[loop
->num
].regno_allocno_map
!= NULL
240 && ira_loop_nodes
[loop
->num
].children
== NULL
)
242 /* We have not added loop node to the tree yet. */
243 loop_node
= &ira_loop_nodes
[loop
->num
];
244 loop_node
->loop
= loop
;
245 loop_node
->bb
= NULL
;
246 for (parent
= loop_outer (loop
);
248 parent
= loop_outer (parent
))
249 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
253 loop_node
->next
= NULL
;
254 loop_node
->subloop_next
= NULL
;
255 loop_node
->parent
= NULL
;
259 parent_node
= &ira_loop_nodes
[parent
->num
];
260 loop_node
->next
= parent_node
->children
;
261 parent_node
->children
= loop_node
;
262 loop_node
->subloop_next
= parent_node
->subloops
;
263 parent_node
->subloops
= loop_node
;
264 loop_node
->parent
= parent_node
;
269 /* The following recursive function sets up levels of nodes of the
270 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
271 The function returns maximal value of level in the tree + 1. */
273 setup_loop_tree_level (ira_loop_tree_node_t loop_node
, int level
)
275 int height
, max_height
;
276 ira_loop_tree_node_t subloop_node
;
278 ira_assert (loop_node
->bb
== NULL
);
279 loop_node
->level
= level
;
280 max_height
= level
+ 1;
281 for (subloop_node
= loop_node
->subloops
;
282 subloop_node
!= NULL
;
283 subloop_node
= subloop_node
->subloop_next
)
285 ira_assert (subloop_node
->bb
== NULL
);
286 height
= setup_loop_tree_level (subloop_node
, level
+ 1);
287 if (height
> max_height
)
293 /* Create the loop tree. The algorithm is designed to provide correct
294 order of loops (they are ordered by their last loop BB) and basic
295 blocks in the chain formed by member next. */
297 form_loop_tree (void)
302 ira_loop_tree_node_t bb_node
, loop_node
;
305 /* We can not use loop/bb node access macros because of potential
306 checking and because the nodes are not initialized enough
308 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
309 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
311 ira_loop_nodes
[i
].children
= NULL
;
312 ira_loop_nodes
[i
].subloops
= NULL
;
316 bb_node
= &ira_bb_nodes
[bb
->index
];
318 bb_node
->loop
= NULL
;
319 bb_node
->subloops
= NULL
;
320 bb_node
->children
= NULL
;
321 bb_node
->subloop_next
= NULL
;
322 bb_node
->next
= NULL
;
323 for (parent
= bb
->loop_father
;
325 parent
= loop_outer (parent
))
326 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
328 add_loop_to_tree (parent
);
329 loop_node
= &ira_loop_nodes
[parent
->num
];
330 bb_node
->next
= loop_node
->children
;
331 bb_node
->parent
= loop_node
;
332 loop_node
->children
= bb_node
;
334 ira_loop_tree_root
= IRA_LOOP_NODE_BY_INDEX (ira_loops
.tree_root
->num
);
335 ira_loop_tree_height
= setup_loop_tree_level (ira_loop_tree_root
, 0);
336 ira_assert (ira_loop_tree_root
->regno_allocno_map
!= NULL
);
341 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
344 rebuild_regno_allocno_maps (void)
347 int max_regno
, regno
;
349 ira_loop_tree_node_t loop_tree_node
;
351 ira_allocno_iterator ai
;
353 max_regno
= max_reg_num ();
354 for (l
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, l
, loop
); l
++)
355 if (ira_loop_nodes
[l
].regno_allocno_map
!= NULL
)
357 ira_free (ira_loop_nodes
[l
].regno_allocno_map
);
358 ira_loop_nodes
[l
].regno_allocno_map
359 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
361 memset (ira_loop_nodes
[l
].regno_allocno_map
, 0,
362 sizeof (ira_allocno_t
) * max_regno
);
364 ira_free (ira_regno_allocno_map
);
365 ira_regno_allocno_map
366 = (ira_allocno_t
*) ira_allocate (max_regno
* sizeof (ira_allocno_t
));
367 memset (ira_regno_allocno_map
, 0, max_regno
* sizeof (ira_allocno_t
));
368 FOR_EACH_ALLOCNO (a
, ai
)
370 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
371 /* Caps are not in the regno allocno maps. */
373 regno
= ALLOCNO_REGNO (a
);
374 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
375 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
376 ira_regno_allocno_map
[regno
] = a
;
377 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
378 /* Remember that we can create temporary allocnos to break
379 cycles in register shuffle. */
380 loop_tree_node
->regno_allocno_map
[regno
] = a
;
386 /* Pools for allocnos and allocno live ranges. */
387 static alloc_pool allocno_pool
, allocno_live_range_pool
;
389 /* Vec containing references to all created allocnos. It is a
390 container of array allocnos. */
391 static VEC(ira_allocno_t
,heap
) *allocno_vec
;
393 /* Vec containing references to all created allocnos. It is a
394 container of ira_conflict_id_allocno_map. */
395 static VEC(ira_allocno_t
,heap
) *ira_conflict_id_allocno_map_vec
;
397 /* Initialize data concerning allocnos. */
399 initiate_allocnos (void)
401 allocno_live_range_pool
402 = create_alloc_pool ("allocno live ranges",
403 sizeof (struct ira_allocno_live_range
), 100);
405 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno
), 100);
406 allocno_vec
= VEC_alloc (ira_allocno_t
, heap
, max_reg_num () * 2);
408 ira_allocnos_num
= 0;
409 ira_conflict_id_allocno_map_vec
410 = VEC_alloc (ira_allocno_t
, heap
, max_reg_num () * 2);
411 ira_conflict_id_allocno_map
= NULL
;
412 ira_regno_allocno_map
413 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
414 memset (ira_regno_allocno_map
, 0, max_reg_num () * sizeof (ira_allocno_t
));
417 /* Create and return the allocno corresponding to REGNO in
418 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
419 same regno if CAP_P is FALSE. */
421 ira_create_allocno (int regno
, bool cap_p
, ira_loop_tree_node_t loop_tree_node
)
425 a
= (ira_allocno_t
) pool_alloc (allocno_pool
);
426 ALLOCNO_REGNO (a
) = regno
;
427 ALLOCNO_LOOP_TREE_NODE (a
) = loop_tree_node
;
430 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
431 ira_regno_allocno_map
[regno
] = a
;
432 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
433 /* Remember that we can create temporary allocnos to break
434 cycles in register shuffle on region borders (see
436 loop_tree_node
->regno_allocno_map
[regno
] = a
;
438 ALLOCNO_CAP (a
) = NULL
;
439 ALLOCNO_CAP_MEMBER (a
) = NULL
;
440 ALLOCNO_NUM (a
) = ira_allocnos_num
;
441 bitmap_set_bit (loop_tree_node
->all_allocnos
, ALLOCNO_NUM (a
));
442 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = NULL
;
443 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
444 COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
), ira_no_alloc_regs
);
445 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
), ira_no_alloc_regs
);
446 ALLOCNO_NREFS (a
) = 0;
447 ALLOCNO_FREQ (a
) = 0;
448 ALLOCNO_HARD_REGNO (a
) = -1;
449 ALLOCNO_CALL_FREQ (a
) = 0;
450 ALLOCNO_CALLS_CROSSED_NUM (a
) = 0;
452 ALLOCNO_NO_STACK_REG_P (a
) = false;
453 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = false;
455 ALLOCNO_MEM_OPTIMIZED_DEST (a
) = NULL
;
456 ALLOCNO_MEM_OPTIMIZED_DEST_P (a
) = false;
457 ALLOCNO_SOMEWHERE_RENAMED_P (a
) = false;
458 ALLOCNO_CHILD_RENAMED_P (a
) = false;
459 ALLOCNO_DONT_REASSIGN_P (a
) = false;
460 ALLOCNO_BAD_SPILL_P (a
) = false;
461 ALLOCNO_IN_GRAPH_P (a
) = false;
462 ALLOCNO_ASSIGNED_P (a
) = false;
463 ALLOCNO_MAY_BE_SPILLED_P (a
) = false;
464 ALLOCNO_SPLAY_REMOVED_P (a
) = false;
465 ALLOCNO_CONFLICT_VEC_P (a
) = false;
466 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
467 ALLOCNO_COPIES (a
) = NULL
;
468 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
469 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
470 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
471 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
472 ALLOCNO_LEFT_CONFLICTS_SIZE (a
) = -1;
473 ALLOCNO_COVER_CLASS (a
) = NO_REGS
;
474 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = 0;
475 ALLOCNO_COVER_CLASS_COST (a
) = 0;
476 ALLOCNO_MEMORY_COST (a
) = 0;
477 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
478 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
479 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = NULL
;
480 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
481 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
482 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
483 ALLOCNO_LIVE_RANGES (a
) = NULL
;
484 ALLOCNO_MIN (a
) = INT_MAX
;
485 ALLOCNO_MAX (a
) = -1;
486 ALLOCNO_CONFLICT_ID (a
) = ira_allocnos_num
;
487 VEC_safe_push (ira_allocno_t
, heap
, allocno_vec
, a
);
488 ira_allocnos
= VEC_address (ira_allocno_t
, allocno_vec
);
489 ira_allocnos_num
= VEC_length (ira_allocno_t
, allocno_vec
);
490 VEC_safe_push (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
, a
);
491 ira_conflict_id_allocno_map
492 = VEC_address (ira_allocno_t
, ira_conflict_id_allocno_map_vec
);
496 /* Set up cover class for A and update its conflict hard registers. */
498 ira_set_allocno_cover_class (ira_allocno_t a
, enum reg_class cover_class
)
500 ALLOCNO_COVER_CLASS (a
) = cover_class
;
501 IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
502 reg_class_contents
[cover_class
]);
503 IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
504 reg_class_contents
[cover_class
]);
507 /* Return TRUE if the conflict vector with NUM elements is more
508 profitable than conflict bit vector for A. */
510 ira_conflict_vector_profitable_p (ira_allocno_t a
, int num
)
514 if (ALLOCNO_MAX (a
) < ALLOCNO_MIN (a
))
515 /* We prefer bit vector in such case because it does not result in
519 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
) / IRA_INT_BITS
;
520 return (2 * sizeof (ira_allocno_t
) * (num
+ 1)
521 < 3 * nw
* sizeof (IRA_INT_TYPE
));
524 /* Allocates and initialize the conflict vector of A for NUM
525 conflicting allocnos. */
527 ira_allocate_allocno_conflict_vec (ira_allocno_t a
, int num
)
532 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
533 num
++; /* for NULL end marker */
534 size
= sizeof (ira_allocno_t
) * num
;
535 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
536 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
538 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
539 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
540 ALLOCNO_CONFLICT_VEC_P (a
) = true;
543 /* Allocate and initialize the conflict bit vector of A. */
545 allocate_allocno_conflict_bit_vec (ira_allocno_t a
)
549 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
550 size
= ((ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
)
551 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
552 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
553 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0, size
);
554 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
555 ALLOCNO_CONFLICT_VEC_P (a
) = false;
558 /* Allocate and initialize the conflict vector or conflict bit vector
559 of A for NUM conflicting allocnos whatever is more profitable. */
561 ira_allocate_allocno_conflicts (ira_allocno_t a
, int num
)
563 if (ira_conflict_vector_profitable_p (a
, num
))
564 ira_allocate_allocno_conflict_vec (a
, num
);
566 allocate_allocno_conflict_bit_vec (a
);
569 /* Add A2 to the conflicts of A1. */
571 add_to_allocno_conflicts (ira_allocno_t a1
, ira_allocno_t a2
)
576 if (ALLOCNO_CONFLICT_VEC_P (a1
))
580 num
= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
) + 2;
581 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
)
582 >= num
* sizeof (ira_allocno_t
))
583 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
586 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
587 vec
= (ira_allocno_t
*) ira_allocate (size
);
588 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
589 sizeof (ira_allocno_t
) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
));
590 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
591 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
592 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
596 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
)++;
600 int nw
, added_head_nw
, id
;
603 id
= ALLOCNO_CONFLICT_ID (a2
);
604 vec
= (IRA_INT_TYPE
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
605 if (ALLOCNO_MIN (a1
) > id
)
607 /* Expand head of the bit vector. */
608 added_head_nw
= (ALLOCNO_MIN (a1
) - id
- 1) / IRA_INT_BITS
+ 1;
609 nw
= (ALLOCNO_MAX (a1
) - ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
610 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
611 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) >= size
)
613 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
614 vec
, nw
* sizeof (IRA_INT_TYPE
));
615 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
620 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
621 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
622 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
623 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
624 nw
* sizeof (IRA_INT_TYPE
));
625 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
627 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
628 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
629 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
630 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
631 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
633 ALLOCNO_MIN (a1
) -= added_head_nw
* IRA_INT_BITS
;
635 else if (ALLOCNO_MAX (a1
) < id
)
637 nw
= (id
- ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
638 size
= nw
* sizeof (IRA_INT_TYPE
);
639 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) < size
)
641 /* Expand tail of the bit vector. */
642 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
643 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
644 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
645 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
646 memset ((char *) vec
+ ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
),
647 0, size
- ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
648 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
649 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
650 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
652 ALLOCNO_MAX (a1
) = id
;
654 SET_ALLOCNO_SET_BIT (vec
, id
, ALLOCNO_MIN (a1
), ALLOCNO_MAX (a1
));
658 /* Add A1 to the conflicts of A2 and vise versa. */
660 ira_add_allocno_conflict (ira_allocno_t a1
, ira_allocno_t a2
)
662 add_to_allocno_conflicts (a1
, a2
);
663 add_to_allocno_conflicts (a2
, a1
);
666 /* Clear all conflicts of allocno A. */
668 clear_allocno_conflicts (ira_allocno_t a
)
670 if (ALLOCNO_CONFLICT_VEC_P (a
))
672 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
673 ((ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
))[0] = NULL
;
675 else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) != 0)
679 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
)) / IRA_INT_BITS
+ 1;
680 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0,
681 nw
* sizeof (IRA_INT_TYPE
));
685 /* The array used to find duplications in conflict vectors of
687 static int *allocno_conflict_check
;
689 /* The value used to mark allocation presence in conflict vector of
690 the current allocno. */
691 static int curr_allocno_conflict_check_tick
;
693 /* Remove duplications in conflict vector of A. */
695 compress_allocno_conflict_vec (ira_allocno_t a
)
697 ira_allocno_t
*vec
, conflict_a
;
700 ira_assert (ALLOCNO_CONFLICT_VEC_P (a
));
701 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
702 curr_allocno_conflict_check_tick
++;
703 for (i
= j
= 0; (conflict_a
= vec
[i
]) != NULL
; i
++)
705 if (allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
706 != curr_allocno_conflict_check_tick
)
708 allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
709 = curr_allocno_conflict_check_tick
;
710 vec
[j
++] = conflict_a
;
713 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = j
;
717 /* Remove duplications in conflict vectors of all allocnos. */
719 compress_conflict_vecs (void)
722 ira_allocno_iterator ai
;
724 allocno_conflict_check
725 = (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
726 memset (allocno_conflict_check
, 0, sizeof (int) * ira_allocnos_num
);
727 curr_allocno_conflict_check_tick
= 0;
728 FOR_EACH_ALLOCNO (a
, ai
)
729 if (ALLOCNO_CONFLICT_VEC_P (a
))
730 compress_allocno_conflict_vec (a
);
731 ira_free (allocno_conflict_check
);
734 /* This recursive function outputs allocno A and if it is a cap the
735 function outputs its members. */
737 ira_print_expanded_allocno (ira_allocno_t a
)
741 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
742 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
743 fprintf (ira_dump_file
, ",b%d", bb
->index
);
745 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop
->num
);
746 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
748 fprintf (ira_dump_file
, ":");
749 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
751 fprintf (ira_dump_file
, ")");
754 /* Create and return the cap representing allocno A in the
757 create_cap_allocno (ira_allocno_t a
)
760 ira_loop_tree_node_t parent
;
761 enum reg_class cover_class
;
763 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
764 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) == a
);
765 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
766 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
767 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
768 cover_class
= ALLOCNO_COVER_CLASS (a
);
769 ira_set_allocno_cover_class (cap
, cover_class
);
770 ALLOCNO_AVAILABLE_REGS_NUM (cap
) = ALLOCNO_AVAILABLE_REGS_NUM (a
);
771 ALLOCNO_CAP_MEMBER (cap
) = a
;
772 ALLOCNO_CAP (a
) = cap
;
773 ALLOCNO_COVER_CLASS_COST (cap
) = ALLOCNO_COVER_CLASS_COST (a
);
774 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
775 ira_allocate_and_copy_costs
776 (&ALLOCNO_HARD_REG_COSTS (cap
), cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
777 ira_allocate_and_copy_costs
778 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), cover_class
,
779 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
780 ALLOCNO_BAD_SPILL_P (cap
) = ALLOCNO_BAD_SPILL_P (a
);
781 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
782 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
783 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
784 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap
),
785 ALLOCNO_CONFLICT_HARD_REGS (a
));
786 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap
),
787 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
788 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
790 ALLOCNO_NO_STACK_REG_P (cap
) = ALLOCNO_NO_STACK_REG_P (a
);
791 ALLOCNO_TOTAL_NO_STACK_REG_P (cap
) = ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
793 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
795 fprintf (ira_dump_file
, " Creating cap ");
796 ira_print_expanded_allocno (cap
);
797 fprintf (ira_dump_file
, "\n");
802 /* Create and return allocno live range with given attributes. */
804 ira_create_allocno_live_range (ira_allocno_t a
, int start
, int finish
,
805 allocno_live_range_t next
)
807 allocno_live_range_t p
;
809 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
817 /* Copy allocno live range R and return the result. */
818 static allocno_live_range_t
819 copy_allocno_live_range (allocno_live_range_t r
)
821 allocno_live_range_t p
;
823 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
828 /* Copy allocno live range list given by its head R and return the
831 ira_copy_allocno_live_range_list (allocno_live_range_t r
)
833 allocno_live_range_t p
, first
, last
;
837 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
839 p
= copy_allocno_live_range (r
);
849 /* Merge ranges R1 and R2 and returns the result. The function
850 maintains the order of ranges and tries to minimize number of the
853 ira_merge_allocno_live_ranges (allocno_live_range_t r1
,
854 allocno_live_range_t r2
)
856 allocno_live_range_t first
, last
, temp
;
862 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
864 if (r1
->start
< r2
->start
)
870 if (r1
->start
<= r2
->finish
+ 1)
872 /* Intersected ranges: merge r1 and r2 into r1. */
873 r1
->start
= r2
->start
;
874 if (r1
->finish
< r2
->finish
)
875 r1
->finish
= r2
->finish
;
878 ira_finish_allocno_live_range (temp
);
881 /* To try to merge with subsequent ranges in r1. */
888 /* Add r1 to the result. */
899 /* To try to merge with subsequent ranges in r2. */
911 ira_assert (r1
->next
== NULL
);
919 ira_assert (r2
->next
== NULL
);
923 ira_assert (last
->next
== NULL
);
928 /* Return TRUE if live ranges R1 and R2 intersect. */
930 ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1
,
931 allocno_live_range_t r2
)
933 /* Remember the live ranges are always kept ordered. */
934 while (r1
!= NULL
&& r2
!= NULL
)
936 if (r1
->start
> r2
->finish
)
938 else if (r2
->start
> r1
->finish
)
946 /* Free allocno live range R. */
948 ira_finish_allocno_live_range (allocno_live_range_t r
)
950 pool_free (allocno_live_range_pool
, r
);
953 /* Free list of allocno live ranges starting with R. */
955 ira_finish_allocno_live_range_list (allocno_live_range_t r
)
957 allocno_live_range_t next_r
;
959 for (; r
!= NULL
; r
= next_r
)
962 ira_finish_allocno_live_range (r
);
966 /* Free updated register costs of allocno A. */
968 ira_free_allocno_updated_costs (ira_allocno_t a
)
970 enum reg_class cover_class
;
972 cover_class
= ALLOCNO_COVER_CLASS (a
);
973 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
974 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
975 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
976 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
977 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
979 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
982 /* Free the memory allocated for allocno A. */
984 finish_allocno (ira_allocno_t a
)
986 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
988 ira_allocnos
[ALLOCNO_NUM (a
)] = NULL
;
989 ira_conflict_id_allocno_map
[ALLOCNO_CONFLICT_ID (a
)] = NULL
;
990 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) != NULL
)
991 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
));
992 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
993 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a
), cover_class
);
994 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
995 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
), cover_class
);
996 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
997 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
998 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
999 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1001 ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
1002 pool_free (allocno_pool
, a
);
1005 /* Free the memory allocated for all allocnos. */
1007 finish_allocnos (void)
1010 ira_allocno_iterator ai
;
1012 FOR_EACH_ALLOCNO (a
, ai
)
1014 ira_free (ira_regno_allocno_map
);
1015 VEC_free (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
);
1016 VEC_free (ira_allocno_t
, heap
, allocno_vec
);
1017 free_alloc_pool (allocno_pool
);
1018 free_alloc_pool (allocno_live_range_pool
);
1023 /* Pools for copies. */
1024 static alloc_pool copy_pool
;
1026 /* Vec containing references to all created copies. It is a
1027 container of array ira_copies. */
1028 static VEC(ira_copy_t
,heap
) *copy_vec
;
1030 /* The function initializes data concerning allocno copies. */
1032 initiate_copies (void)
1035 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy
), 100);
1036 copy_vec
= VEC_alloc (ira_copy_t
, heap
, get_max_uid ());
1041 /* Return copy connecting A1 and A2 and originated from INSN of
1042 LOOP_TREE_NODE if any. */
1044 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx insn
,
1045 ira_loop_tree_node_t loop_tree_node
)
1047 ira_copy_t cp
, next_cp
;
1048 ira_allocno_t another_a
;
1050 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
1052 if (cp
->first
== a1
)
1054 next_cp
= cp
->next_first_allocno_copy
;
1055 another_a
= cp
->second
;
1057 else if (cp
->second
== a1
)
1059 next_cp
= cp
->next_second_allocno_copy
;
1060 another_a
= cp
->first
;
1064 if (another_a
== a2
&& cp
->insn
== insn
1065 && cp
->loop_tree_node
== loop_tree_node
)
1071 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1072 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1074 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1075 bool constraint_p
, rtx insn
,
1076 ira_loop_tree_node_t loop_tree_node
)
1080 cp
= (ira_copy_t
) pool_alloc (copy_pool
);
1081 cp
->num
= ira_copies_num
;
1083 cp
->second
= second
;
1085 cp
->constraint_p
= constraint_p
;
1087 cp
->loop_tree_node
= loop_tree_node
;
1088 VEC_safe_push (ira_copy_t
, heap
, copy_vec
, cp
);
1089 ira_copies
= VEC_address (ira_copy_t
, copy_vec
);
1090 ira_copies_num
= VEC_length (ira_copy_t
, copy_vec
);
1094 /* Attach a copy CP to allocnos involved into the copy. */
1096 ira_add_allocno_copy_to_list (ira_copy_t cp
)
1098 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1100 cp
->prev_first_allocno_copy
= NULL
;
1101 cp
->prev_second_allocno_copy
= NULL
;
1102 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
1103 if (cp
->next_first_allocno_copy
!= NULL
)
1105 if (cp
->next_first_allocno_copy
->first
== first
)
1106 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
1108 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1110 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1111 if (cp
->next_second_allocno_copy
!= NULL
)
1113 if (cp
->next_second_allocno_copy
->second
== second
)
1114 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1116 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1118 ALLOCNO_COPIES (first
) = cp
;
1119 ALLOCNO_COPIES (second
) = cp
;
1122 /* Detach a copy CP from allocnos involved into the copy. */
1124 ira_remove_allocno_copy_from_list (ira_copy_t cp
)
1126 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1127 ira_copy_t prev
, next
;
1129 next
= cp
->next_first_allocno_copy
;
1130 prev
= cp
->prev_first_allocno_copy
;
1132 ALLOCNO_COPIES (first
) = next
;
1133 else if (prev
->first
== first
)
1134 prev
->next_first_allocno_copy
= next
;
1136 prev
->next_second_allocno_copy
= next
;
1139 if (next
->first
== first
)
1140 next
->prev_first_allocno_copy
= prev
;
1142 next
->prev_second_allocno_copy
= prev
;
1144 cp
->prev_first_allocno_copy
= cp
->next_first_allocno_copy
= NULL
;
1146 next
= cp
->next_second_allocno_copy
;
1147 prev
= cp
->prev_second_allocno_copy
;
1149 ALLOCNO_COPIES (second
) = next
;
1150 else if (prev
->second
== second
)
1151 prev
->next_second_allocno_copy
= next
;
1153 prev
->next_first_allocno_copy
= next
;
1156 if (next
->second
== second
)
1157 next
->prev_second_allocno_copy
= prev
;
1159 next
->prev_first_allocno_copy
= prev
;
1161 cp
->prev_second_allocno_copy
= cp
->next_second_allocno_copy
= NULL
;
1164 /* Make a copy CP a canonical copy where number of the
1165 first allocno is less than the second one. */
1167 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1172 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1176 cp
->first
= cp
->second
;
1179 temp_cp
= cp
->prev_first_allocno_copy
;
1180 cp
->prev_first_allocno_copy
= cp
->prev_second_allocno_copy
;
1181 cp
->prev_second_allocno_copy
= temp_cp
;
1183 temp_cp
= cp
->next_first_allocno_copy
;
1184 cp
->next_first_allocno_copy
= cp
->next_second_allocno_copy
;
1185 cp
->next_second_allocno_copy
= temp_cp
;
1188 /* Create (or update frequency if the copy already exists) and return
1189 the copy of allocnos FIRST and SECOND with frequency FREQ
1190 corresponding to move insn INSN (if any) and originated from
1193 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1194 bool constraint_p
, rtx insn
,
1195 ira_loop_tree_node_t loop_tree_node
)
1199 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1204 cp
= ira_create_copy (first
, second
, freq
, constraint_p
, insn
,
1206 ira_assert (first
!= NULL
&& second
!= NULL
);
1207 ira_add_allocno_copy_to_list (cp
);
1208 ira_swap_allocno_copy_ends_if_necessary (cp
);
1212 /* Print info about copy CP into file F. */
1214 print_copy (FILE *f
, ira_copy_t cp
)
1216 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp
->num
,
1217 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1218 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
,
1220 ? "move" : cp
->constraint_p
? "constraint" : "shuffle");
1223 /* Print info about copy CP into stderr. */
1225 ira_debug_copy (ira_copy_t cp
)
1227 print_copy (stderr
, cp
);
1230 /* Print info about all copies into file F. */
1232 print_copies (FILE *f
)
1235 ira_copy_iterator ci
;
1237 FOR_EACH_COPY (cp
, ci
)
1241 /* Print info about all copies into stderr. */
1243 ira_debug_copies (void)
1245 print_copies (stderr
);
1248 /* Print info about copies involving allocno A into file F. */
1250 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1252 ira_allocno_t another_a
;
1253 ira_copy_t cp
, next_cp
;
1255 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1256 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1260 next_cp
= cp
->next_first_allocno_copy
;
1261 another_a
= cp
->second
;
1263 else if (cp
->second
== a
)
1265 next_cp
= cp
->next_second_allocno_copy
;
1266 another_a
= cp
->first
;
1270 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1271 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1276 /* Print info about copies involving allocno A into stderr. */
1278 ira_debug_allocno_copies (ira_allocno_t a
)
1280 print_allocno_copies (stderr
, a
);
1283 /* The function frees memory allocated for copy CP. */
1285 finish_copy (ira_copy_t cp
)
1287 pool_free (copy_pool
, cp
);
1291 /* Free memory allocated for all copies. */
1293 finish_copies (void)
1296 ira_copy_iterator ci
;
1298 FOR_EACH_COPY (cp
, ci
)
1300 VEC_free (ira_copy_t
, heap
, copy_vec
);
1301 free_alloc_pool (copy_pool
);
1306 /* Pools for cost vectors. It is defined only for cover classes. */
1307 static alloc_pool cost_vector_pool
[N_REG_CLASSES
];
1309 /* The function initiates work with hard register cost vectors. It
1310 creates allocation pool for each cover class. */
1312 initiate_cost_vectors (void)
1315 enum reg_class cover_class
;
1317 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1319 cover_class
= ira_reg_class_cover
[i
];
1320 cost_vector_pool
[cover_class
]
1321 = create_alloc_pool ("cost vectors",
1323 * ira_class_hard_regs_num
[cover_class
],
1328 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1330 ira_allocate_cost_vector (enum reg_class cover_class
)
1332 return (int *) pool_alloc (cost_vector_pool
[cover_class
]);
1335 /* Free a cost vector VEC for COVER_CLASS. */
1337 ira_free_cost_vector (int *vec
, enum reg_class cover_class
)
1339 ira_assert (vec
!= NULL
);
1340 pool_free (cost_vector_pool
[cover_class
], vec
);
1343 /* Finish work with hard register cost vectors. Release allocation
1344 pool for each cover class. */
1346 finish_cost_vectors (void)
1349 enum reg_class cover_class
;
1351 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1353 cover_class
= ira_reg_class_cover
[i
];
1354 free_alloc_pool (cost_vector_pool
[cover_class
]);
1360 /* The current loop tree node and its regno allocno map. */
1361 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1362 ira_allocno_t
*ira_curr_regno_allocno_map
;
1364 /* This recursive function traverses loop tree with root LOOP_NODE
1365 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1366 correspondingly in preorder and postorder. The function sets up
1367 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1368 basic block nodes of LOOP_NODE is also processed (before its
1371 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1372 void (*preorder_func
) (ira_loop_tree_node_t
),
1373 void (*postorder_func
) (ira_loop_tree_node_t
))
1375 ira_loop_tree_node_t subloop_node
;
1377 ira_assert (loop_node
->bb
== NULL
);
1378 ira_curr_loop_tree_node
= loop_node
;
1379 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1381 if (preorder_func
!= NULL
)
1382 (*preorder_func
) (loop_node
);
1385 for (subloop_node
= loop_node
->children
;
1386 subloop_node
!= NULL
;
1387 subloop_node
= subloop_node
->next
)
1388 if (subloop_node
->bb
!= NULL
)
1390 if (preorder_func
!= NULL
)
1391 (*preorder_func
) (subloop_node
);
1393 if (postorder_func
!= NULL
)
1394 (*postorder_func
) (subloop_node
);
1397 for (subloop_node
= loop_node
->subloops
;
1398 subloop_node
!= NULL
;
1399 subloop_node
= subloop_node
->subloop_next
)
1401 ira_assert (subloop_node
->bb
== NULL
);
1402 ira_traverse_loop_tree (bb_p
, subloop_node
,
1403 preorder_func
, postorder_func
);
1406 ira_curr_loop_tree_node
= loop_node
;
1407 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1409 if (postorder_func
!= NULL
)
1410 (*postorder_func
) (loop_node
);
1415 /* The basic block currently being processed. */
1416 static basic_block curr_bb
;
1418 /* This recursive function creates allocnos corresponding to
1419 pseudo-registers containing in X. True OUTPUT_P means that X is
1422 create_insn_allocnos (rtx x
, bool output_p
)
1426 enum rtx_code code
= GET_CODE (x
);
1432 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1436 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1437 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1439 ALLOCNO_NREFS (a
)++;
1440 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1442 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1446 else if (code
== SET
)
1448 create_insn_allocnos (SET_DEST (x
), true);
1449 create_insn_allocnos (SET_SRC (x
), false);
1452 else if (code
== CLOBBER
)
1454 create_insn_allocnos (XEXP (x
, 0), true);
1457 else if (code
== MEM
)
1459 create_insn_allocnos (XEXP (x
, 0), false);
1462 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1463 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1465 create_insn_allocnos (XEXP (x
, 0), true);
1466 create_insn_allocnos (XEXP (x
, 0), false);
1470 fmt
= GET_RTX_FORMAT (code
);
1471 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1474 create_insn_allocnos (XEXP (x
, i
), output_p
);
1475 else if (fmt
[i
] == 'E')
1476 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1477 create_insn_allocnos (XVECEXP (x
, i
, j
), output_p
);
1481 /* Create allocnos corresponding to pseudo-registers living in the
1482 basic block represented by the corresponding loop tree node
1485 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1492 curr_bb
= bb
= bb_node
->bb
;
1493 ira_assert (bb
!= NULL
);
1494 FOR_BB_INSNS_REVERSE (bb
, insn
)
1495 if (NONDEBUG_INSN_P (insn
))
1496 create_insn_allocnos (PATTERN (insn
), false);
1497 /* It might be a allocno living through from one subloop to
1499 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1500 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1501 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1504 /* Create allocnos corresponding to pseudo-registers living on edge E
1505 (a loop entry or exit). Also mark the allocnos as living on the
1508 create_loop_allocnos (edge e
)
1511 bitmap live_in_regs
, border_allocnos
;
1513 ira_loop_tree_node_t parent
;
1515 live_in_regs
= DF_LR_IN (e
->dest
);
1516 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1517 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e
->src
),
1518 FIRST_PSEUDO_REGISTER
, i
, bi
)
1519 if (bitmap_bit_p (live_in_regs
, i
))
1521 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1523 /* The order of creations is important for right
1524 ira_regno_allocno_map. */
1525 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1526 && parent
->regno_allocno_map
[i
] == NULL
)
1527 ira_create_allocno (i
, false, parent
);
1528 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1530 bitmap_set_bit (border_allocnos
,
1531 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1535 /* Create allocnos corresponding to pseudo-registers living in loop
1536 represented by the corresponding loop tree node LOOP_NODE. This
1537 function is called by ira_traverse_loop_tree. */
1539 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1541 if (loop_node
->bb
!= NULL
)
1542 create_bb_allocnos (loop_node
);
1543 else if (loop_node
!= ira_loop_tree_root
)
1548 VEC (edge
, heap
) *edges
;
1550 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1551 if (e
->src
!= loop_node
->loop
->latch
)
1552 create_loop_allocnos (e
);
1554 edges
= get_loop_exit_edges (loop_node
->loop
);
1555 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1556 create_loop_allocnos (e
);
1557 VEC_free (edge
, heap
, edges
);
1561 /* Propagate information about allocnos modified inside the loop given
1562 by its LOOP_TREE_NODE to its parent. */
1564 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
1566 if (loop_tree_node
== ira_loop_tree_root
)
1568 ira_assert (loop_tree_node
->bb
== NULL
);
1569 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
1570 loop_tree_node
->modified_regnos
);
1573 /* Propagate new info about allocno A (see comments about accumulated
1574 info in allocno definition) to the corresponding allocno on upper
1575 loop tree level. So allocnos on upper levels accumulate
1576 information about the corresponding allocnos in nested regions.
1577 The new info means allocno info finally calculated in this
1580 propagate_allocno_info (void)
1583 ira_allocno_t a
, parent_a
;
1584 ira_loop_tree_node_t parent
;
1585 enum reg_class cover_class
;
1587 if (flag_ira_region
!= IRA_REGION_ALL
1588 && flag_ira_region
!= IRA_REGION_MIXED
)
1590 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
1591 for (a
= ira_regno_allocno_map
[i
];
1593 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
1594 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
1595 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
1596 /* There are no caps yet at this point. So use
1597 border_allocnos to find allocnos for the propagation. */
1598 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
1601 if (! ALLOCNO_BAD_SPILL_P (a
))
1602 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
1603 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
1604 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
1605 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
1607 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
1608 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
1610 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
1611 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1612 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
1613 += ALLOCNO_CALLS_CROSSED_NUM (a
);
1614 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
1615 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1616 cover_class
= ALLOCNO_COVER_CLASS (a
);
1617 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (parent_a
));
1618 ira_allocate_and_accumulate_costs
1619 (&ALLOCNO_HARD_REG_COSTS (parent_a
), cover_class
,
1620 ALLOCNO_HARD_REG_COSTS (a
));
1621 ira_allocate_and_accumulate_costs
1622 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
1624 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
1625 ALLOCNO_COVER_CLASS_COST (parent_a
)
1626 += ALLOCNO_COVER_CLASS_COST (a
);
1627 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
1631 /* Create allocnos corresponding to pseudo-registers in the current
1632 function. Traverse the loop tree for this. */
1634 create_allocnos (void)
1636 /* We need to process BB first to correctly link allocnos by member
1637 next_regno_allocno. */
1638 ira_traverse_loop_tree (true, ira_loop_tree_root
,
1639 create_loop_tree_node_allocnos
, NULL
);
1641 ira_traverse_loop_tree (false, ira_loop_tree_root
, NULL
,
1642 propagate_modified_regnos
);
1647 /* The page contains function to remove some regions from a separate
1648 register allocation. We remove regions whose separate allocation
1649 will hardly improve the result. As a result we speed up regional
1650 register allocation. */
1652 /* The function changes allocno in range list given by R onto A. */
1654 change_allocno_in_range_list (allocno_live_range_t r
, ira_allocno_t a
)
1656 for (; r
!= NULL
; r
= r
->next
)
1660 /* Return TRUE if NODE represents a loop with low register
1663 low_pressure_loop_node_p (ira_loop_tree_node_t node
)
1666 enum reg_class cover_class
;
1668 if (node
->bb
!= NULL
)
1671 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1673 cover_class
= ira_reg_class_cover
[i
];
1674 if (node
->reg_pressure
[cover_class
]
1675 > ira_available_class_regs
[cover_class
])
1681 /* Sort loops for marking them for removal. We put already marked
1682 loops first, then less frequent loops next, and then outer loops
1685 loop_compare_func (const void *v1p
, const void *v2p
)
1688 ira_loop_tree_node_t l1
= *(const ira_loop_tree_node_t
*) v1p
;
1689 ira_loop_tree_node_t l2
= *(const ira_loop_tree_node_t
*) v2p
;
1691 ira_assert (l1
->parent
!= NULL
&& l2
->parent
!= NULL
);
1692 if (l1
->to_remove_p
&& ! l2
->to_remove_p
)
1694 if (! l1
->to_remove_p
&& l2
->to_remove_p
)
1696 if ((diff
= l1
->loop
->header
->frequency
- l2
->loop
->header
->frequency
) != 0)
1698 if ((diff
= (int) loop_depth (l1
->loop
) - (int) loop_depth (l2
->loop
)) != 0)
1700 /* Make sorting stable. */
1701 return l1
->loop
->num
- l2
->loop
->num
;
1705 /* Mark loops which should be removed from regional allocation. We
1706 remove a loop with low register pressure inside another loop with
1707 register pressure. In this case a separate allocation of the loop
1708 hardly helps (for irregular register file architecture it could
1709 help by choosing a better hard register in the loop but we prefer
1710 faster allocation even in this case). We also remove cheap loops
1711 if there are more than IRA_MAX_LOOPS_NUM of them. */
1713 mark_loops_for_removal (void)
1716 ira_loop_tree_node_t
*sorted_loops
;
1720 = (ira_loop_tree_node_t
*) ira_allocate (sizeof (ira_loop_tree_node_t
)
1721 * VEC_length (loop_p
,
1723 for (n
= i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
1724 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
1726 if (ira_loop_nodes
[i
].parent
== NULL
)
1728 /* Don't remove the root. */
1729 ira_loop_nodes
[i
].to_remove_p
= false;
1732 sorted_loops
[n
++] = &ira_loop_nodes
[i
];
1733 ira_loop_nodes
[i
].to_remove_p
1734 = (low_pressure_loop_node_p (ira_loop_nodes
[i
].parent
)
1735 && low_pressure_loop_node_p (&ira_loop_nodes
[i
]));
1737 qsort (sorted_loops
, n
, sizeof (ira_loop_tree_node_t
), loop_compare_func
);
1738 for (i
= 0; n
- i
+ 1 > IRA_MAX_LOOPS_NUM
; i
++)
1740 sorted_loops
[i
]->to_remove_p
= true;
1741 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1744 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1745 sorted_loops
[i
]->loop
->num
, sorted_loops
[i
]->loop
->header
->index
,
1746 sorted_loops
[i
]->loop
->header
->frequency
,
1747 loop_depth (sorted_loops
[i
]->loop
),
1748 low_pressure_loop_node_p (sorted_loops
[i
]->parent
)
1749 && low_pressure_loop_node_p (sorted_loops
[i
])
1750 ? "low pressure" : "cheap loop");
1752 ira_free (sorted_loops
);
1755 /* Mark all loops but root for removing. */
1757 mark_all_loops_for_removal (void)
1762 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
1763 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
1765 if (ira_loop_nodes
[i
].parent
== NULL
)
1767 /* Don't remove the root. */
1768 ira_loop_nodes
[i
].to_remove_p
= false;
1771 ira_loop_nodes
[i
].to_remove_p
= true;
1772 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1775 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
1776 ira_loop_nodes
[i
].loop
->num
,
1777 ira_loop_nodes
[i
].loop
->header
->index
,
1778 ira_loop_nodes
[i
].loop
->header
->frequency
,
1779 loop_depth (ira_loop_nodes
[i
].loop
));
1783 /* Definition of vector of loop tree nodes. */
1784 DEF_VEC_P(ira_loop_tree_node_t
);
1785 DEF_VEC_ALLOC_P(ira_loop_tree_node_t
, heap
);
1787 /* Vec containing references to all removed loop tree nodes. */
1788 static VEC(ira_loop_tree_node_t
,heap
) *removed_loop_vec
;
1790 /* Vec containing references to all children of loop tree nodes. */
1791 static VEC(ira_loop_tree_node_t
,heap
) *children_vec
;
1793 /* Remove subregions of NODE if their separate allocation will not
1794 improve the result. */
1796 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node
)
1800 ira_loop_tree_node_t subnode
;
1802 remove_p
= node
->to_remove_p
;
1804 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, node
);
1805 start
= VEC_length (ira_loop_tree_node_t
, children_vec
);
1806 for (subnode
= node
->children
; subnode
!= NULL
; subnode
= subnode
->next
)
1807 if (subnode
->bb
== NULL
)
1808 remove_uneccesary_loop_nodes_from_loop_tree (subnode
);
1810 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, subnode
);
1811 node
->children
= node
->subloops
= NULL
;
1814 VEC_safe_push (ira_loop_tree_node_t
, heap
, removed_loop_vec
, node
);
1817 while (VEC_length (ira_loop_tree_node_t
, children_vec
) > start
)
1819 subnode
= VEC_pop (ira_loop_tree_node_t
, children_vec
);
1820 subnode
->parent
= node
;
1821 subnode
->next
= node
->children
;
1822 node
->children
= subnode
;
1823 if (subnode
->bb
== NULL
)
1825 subnode
->subloop_next
= node
->subloops
;
1826 node
->subloops
= subnode
;
1831 /* Return TRUE if NODE is inside PARENT. */
1833 loop_is_inside_p (ira_loop_tree_node_t node
, ira_loop_tree_node_t parent
)
1835 for (node
= node
->parent
; node
!= NULL
; node
= node
->parent
)
1841 /* Sort allocnos according to their order in regno allocno list. */
1843 regno_allocno_order_compare_func (const void *v1p
, const void *v2p
)
1845 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
1846 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
1847 ira_loop_tree_node_t n1
= ALLOCNO_LOOP_TREE_NODE (a1
);
1848 ira_loop_tree_node_t n2
= ALLOCNO_LOOP_TREE_NODE (a2
);
1850 if (loop_is_inside_p (n1
, n2
))
1852 else if (loop_is_inside_p (n2
, n1
))
1854 /* If allocnos are equally good, sort by allocno numbers, so that
1855 the results of qsort leave nothing to chance. We put allocnos
1856 with higher number first in the list because it is the original
1857 order for allocnos from loops on the same levels. */
1858 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
1861 /* This array is used to sort allocnos to restore allocno order in
1862 the regno allocno list. */
1863 static ira_allocno_t
*regno_allocnos
;
1865 /* Restore allocno order for REGNO in the regno allocno list. */
1867 ira_rebuild_regno_allocno_list (int regno
)
1872 for (n
= 0, a
= ira_regno_allocno_map
[regno
];
1874 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
1875 regno_allocnos
[n
++] = a
;
1877 qsort (regno_allocnos
, n
, sizeof (ira_allocno_t
),
1878 regno_allocno_order_compare_func
);
1879 for (i
= 1; i
< n
; i
++)
1880 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[i
- 1]) = regno_allocnos
[i
];
1881 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[n
- 1]) = NULL
;
1882 ira_regno_allocno_map
[regno
] = regno_allocnos
[0];
1883 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1884 fprintf (ira_dump_file
, " Rebuilding regno allocno list for %d\n", regno
);
1887 /* Propagate info from allocno FROM_A to allocno A. */
1889 propagate_some_info_from_allocno (ira_allocno_t a
, ira_allocno_t from_a
)
1891 enum reg_class cover_class
;
1893 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
1894 ALLOCNO_CONFLICT_HARD_REGS (from_a
));
1896 if (ALLOCNO_NO_STACK_REG_P (from_a
))
1897 ALLOCNO_NO_STACK_REG_P (a
) = true;
1899 ALLOCNO_NREFS (a
) += ALLOCNO_NREFS (from_a
);
1900 ALLOCNO_FREQ (a
) += ALLOCNO_FREQ (from_a
);
1901 ALLOCNO_CALL_FREQ (a
) += ALLOCNO_CALL_FREQ (from_a
);
1902 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
1903 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from_a
));
1904 ALLOCNO_CALLS_CROSSED_NUM (a
) += ALLOCNO_CALLS_CROSSED_NUM (from_a
);
1905 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
1906 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a
);
1907 if (! ALLOCNO_BAD_SPILL_P (from_a
))
1908 ALLOCNO_BAD_SPILL_P (a
) = false;
1910 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from_a
))
1911 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = true;
1913 cover_class
= ALLOCNO_COVER_CLASS (from_a
);
1914 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (a
));
1915 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a
), cover_class
,
1916 ALLOCNO_HARD_REG_COSTS (from_a
));
1917 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
1919 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a
));
1920 ALLOCNO_COVER_CLASS_COST (a
) += ALLOCNO_COVER_CLASS_COST (from_a
);
1921 ALLOCNO_MEMORY_COST (a
) += ALLOCNO_MEMORY_COST (from_a
);
1924 /* Remove allocnos from loops removed from the allocation
1927 remove_unnecessary_allocnos (void)
1930 bool merged_p
, rebuild_p
;
1931 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
1932 ira_loop_tree_node_t a_node
, parent
;
1933 allocno_live_range_t r
;
1936 regno_allocnos
= NULL
;
1937 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
1940 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
1944 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
1945 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1946 if (! a_node
->to_remove_p
)
1950 for (parent
= a_node
->parent
;
1951 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
1952 && parent
->to_remove_p
;
1953 parent
= parent
->parent
)
1955 if (parent_a
== NULL
)
1957 /* There are no allocnos with the same regno in
1958 upper region -- just move the allocno to the
1961 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
1962 parent
->regno_allocno_map
[regno
] = a
;
1963 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
1968 /* Remove the allocno and update info of allocno in
1969 the upper region. */
1971 ira_regno_allocno_map
[regno
] = next_a
;
1973 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
1974 r
= ALLOCNO_LIVE_RANGES (a
);
1975 change_allocno_in_range_list (r
, parent_a
);
1976 ALLOCNO_LIVE_RANGES (parent_a
)
1977 = ira_merge_allocno_live_ranges
1978 (r
, ALLOCNO_LIVE_RANGES (parent_a
));
1980 ALLOCNO_LIVE_RANGES (a
) = NULL
;
1981 propagate_some_info_from_allocno (parent_a
, a
);
1982 /* Remove it from the corresponding regno allocno
1983 map to avoid info propagation of subsequent
1984 allocno into this already removed allocno. */
1985 a_node
->regno_allocno_map
[regno
] = NULL
;
1991 /* We need to restore the order in regno allocno list. */
1993 if (regno_allocnos
== NULL
)
1995 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
1996 * ira_allocnos_num
);
1997 ira_rebuild_regno_allocno_list (regno
);
2001 ira_rebuild_start_finish_chains ();
2002 if (regno_allocnos
!= NULL
)
2003 ira_free (regno_allocnos
);
2006 /* Remove allocnos from all loops but the root. */
2008 remove_low_level_allocnos (void)
2011 bool merged_p
, propagate_p
;
2012 ira_allocno_t a
, top_a
;
2013 ira_loop_tree_node_t a_node
, parent
;
2014 allocno_live_range_t r
;
2015 ira_allocno_iterator ai
;
2018 FOR_EACH_ALLOCNO (a
, ai
)
2020 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2021 if (a_node
== ira_loop_tree_root
|| ALLOCNO_CAP_MEMBER (a
) != NULL
)
2023 regno
= ALLOCNO_REGNO (a
);
2024 if ((top_a
= ira_loop_tree_root
->regno_allocno_map
[regno
]) == NULL
)
2026 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2027 ira_loop_tree_root
->regno_allocno_map
[regno
] = a
;
2030 propagate_p
= a_node
->parent
->regno_allocno_map
[regno
] == NULL
;
2031 /* Remove the allocno and update info of allocno in the upper
2033 r
= ALLOCNO_LIVE_RANGES (a
);
2034 change_allocno_in_range_list (r
, top_a
);
2035 ALLOCNO_LIVE_RANGES (top_a
)
2036 = ira_merge_allocno_live_ranges (r
, ALLOCNO_LIVE_RANGES (top_a
));
2038 ALLOCNO_LIVE_RANGES (a
) = NULL
;
2040 propagate_some_info_from_allocno (top_a
, a
);
2042 FOR_EACH_ALLOCNO (a
, ai
)
2044 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2045 if (a_node
== ira_loop_tree_root
)
2047 parent
= a_node
->parent
;
2048 regno
= ALLOCNO_REGNO (a
);
2049 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2050 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2051 else if (ALLOCNO_CAP (a
) == NULL
)
2052 ira_assert (parent
->regno_allocno_map
[regno
] != NULL
);
2054 FOR_EACH_ALLOCNO (a
, ai
)
2056 regno
= ALLOCNO_REGNO (a
);
2057 if (ira_loop_tree_root
->regno_allocno_map
[regno
] == a
)
2059 ira_regno_allocno_map
[regno
] = a
;
2060 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = NULL
;
2061 ALLOCNO_CAP_MEMBER (a
) = NULL
;
2062 COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
2063 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2065 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2066 ALLOCNO_NO_STACK_REG_P (a
) = true;
2073 ira_rebuild_start_finish_chains ();
2076 /* Remove loops from consideration. We remove all loops except for
2077 root if ALL_P or loops for which a separate allocation will not
2078 improve the result. We have to do this after allocno creation and
2079 their costs and cover class evaluation because only after that the
2080 register pressure can be known and is calculated. */
2082 remove_unnecessary_regions (bool all_p
)
2085 mark_all_loops_for_removal ();
2087 mark_loops_for_removal ();
2089 = VEC_alloc (ira_loop_tree_node_t
, heap
,
2090 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
2092 = VEC_alloc (ira_loop_tree_node_t
, heap
,
2093 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
2094 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
) ;
2095 VEC_free (ira_loop_tree_node_t
, heap
, children_vec
);
2097 remove_low_level_allocnos ();
2099 remove_unnecessary_allocnos ();
2100 while (VEC_length (ira_loop_tree_node_t
, removed_loop_vec
) > 0)
2101 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t
, removed_loop_vec
));
2102 VEC_free (ira_loop_tree_node_t
, heap
, removed_loop_vec
);
2107 /* At this point true value of allocno attribute bad_spill_p means
2108 that there is an insn where allocno occurs and where the allocno
2109 can not be used as memory. The function updates the attribute, now
2110 it can be true only for allocnos which can not be used as memory in
2111 an insn and in whose live ranges there is other allocno deaths.
2112 Spilling allocnos with true value will not improve the code because
2113 it will not make other allocnos colorable and additional reloads
2114 for the corresponding pseudo will be generated in reload pass for
2115 each insn it occurs.
2117 This is a trick mentioned in one classic article of Chaitin etc
2118 which is frequently omitted in other implementations of RA based on
2121 update_bad_spill_attribute (void)
2125 ira_allocno_iterator ai
;
2126 allocno_live_range_t r
;
2127 enum reg_class cover_class
;
2128 bitmap_head dead_points
[N_REG_CLASSES
];
2130 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2132 cover_class
= ira_reg_class_cover
[i
];
2133 bitmap_initialize (&dead_points
[cover_class
], ®_obstack
);
2135 FOR_EACH_ALLOCNO (a
, ai
)
2137 cover_class
= ALLOCNO_COVER_CLASS (a
);
2138 if (cover_class
== NO_REGS
)
2140 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2141 bitmap_set_bit (&dead_points
[cover_class
], r
->finish
);
2143 FOR_EACH_ALLOCNO (a
, ai
)
2145 cover_class
= ALLOCNO_COVER_CLASS (a
);
2146 if (cover_class
== NO_REGS
)
2148 if (! ALLOCNO_BAD_SPILL_P (a
))
2150 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2152 for (i
= r
->start
+ 1; i
< r
->finish
; i
++)
2153 if (bitmap_bit_p (&dead_points
[cover_class
], i
))
2159 ALLOCNO_BAD_SPILL_P (a
) = false;
2161 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
2163 cover_class
= ira_reg_class_cover
[i
];
2164 bitmap_clear (&dead_points
[cover_class
]);
2170 /* Set up minimal and maximal live range points for allocnos. */
2172 setup_min_max_allocno_live_range_point (void)
2175 ira_allocno_t a
, parent_a
, cap
;
2176 ira_allocno_iterator ai
;
2177 allocno_live_range_t r
;
2178 ira_loop_tree_node_t parent
;
2180 FOR_EACH_ALLOCNO (a
, ai
)
2182 r
= ALLOCNO_LIVE_RANGES (a
);
2185 ALLOCNO_MAX (a
) = r
->finish
;
2186 for (; r
->next
!= NULL
; r
= r
->next
)
2188 ALLOCNO_MIN (a
) = r
->start
;
2190 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2191 for (a
= ira_regno_allocno_map
[i
];
2193 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2195 if (ALLOCNO_MAX (a
) < 0)
2197 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2198 /* Accumulation of range info. */
2199 if (ALLOCNO_CAP (a
) != NULL
)
2201 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
2203 if (ALLOCNO_MAX (cap
) < ALLOCNO_MAX (a
))
2204 ALLOCNO_MAX (cap
) = ALLOCNO_MAX (a
);
2205 if (ALLOCNO_MIN (cap
) > ALLOCNO_MIN (a
))
2206 ALLOCNO_MIN (cap
) = ALLOCNO_MIN (a
);
2210 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
2212 parent_a
= parent
->regno_allocno_map
[i
];
2213 if (ALLOCNO_MAX (parent_a
) < ALLOCNO_MAX (a
))
2214 ALLOCNO_MAX (parent_a
) = ALLOCNO_MAX (a
);
2215 if (ALLOCNO_MIN (parent_a
) > ALLOCNO_MIN (a
))
2216 ALLOCNO_MIN (parent_a
) = ALLOCNO_MIN (a
);
2218 #ifdef ENABLE_IRA_CHECKING
2219 FOR_EACH_ALLOCNO (a
, ai
)
2221 if ((0 <= ALLOCNO_MIN (a
) && ALLOCNO_MIN (a
) <= ira_max_point
)
2222 && (0 <= ALLOCNO_MAX (a
) && ALLOCNO_MAX (a
) <= ira_max_point
))
2229 /* Sort allocnos according to their live ranges. Allocnos with
2230 smaller cover class are put first unless we use priority coloring.
2231 Allocnos with the same cove class are ordered according their start
2232 (min). Allocnos with the same start are ordered according their
2235 allocno_range_compare_func (const void *v1p
, const void *v2p
)
2238 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2239 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2241 if (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
2242 && (diff
= ALLOCNO_COVER_CLASS (a1
) - ALLOCNO_COVER_CLASS (a2
)) != 0)
2244 if ((diff
= ALLOCNO_MIN (a1
) - ALLOCNO_MIN (a2
)) != 0)
2246 if ((diff
= ALLOCNO_MAX (a1
) - ALLOCNO_MAX (a2
)) != 0)
2248 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2251 /* Sort ira_conflict_id_allocno_map and set up conflict id of
2254 sort_conflict_id_allocno_map (void)
2258 ira_allocno_iterator ai
;
2261 FOR_EACH_ALLOCNO (a
, ai
)
2262 ira_conflict_id_allocno_map
[num
++] = a
;
2263 qsort (ira_conflict_id_allocno_map
, num
, sizeof (ira_allocno_t
),
2264 allocno_range_compare_func
);
2265 for (i
= 0; i
< num
; i
++)
2266 if ((a
= ira_conflict_id_allocno_map
[i
]) != NULL
)
2267 ALLOCNO_CONFLICT_ID (a
) = i
;
2268 for (i
= num
; i
< ira_allocnos_num
; i
++)
2269 ira_conflict_id_allocno_map
[i
] = NULL
;
2272 /* Set up minimal and maximal conflict ids of allocnos with which
2273 given allocno can conflict. */
2275 setup_min_max_conflict_allocno_ids (void)
2278 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
2279 int *live_range_min
, *last_lived
;
2282 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
2284 first_not_finished
= -1;
2285 for (i
= 0; i
< ira_allocnos_num
; i
++)
2287 a
= ira_conflict_id_allocno_map
[i
];
2291 || (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
2292 && cover_class
!= (int) ALLOCNO_COVER_CLASS (a
)))
2294 cover_class
= ALLOCNO_COVER_CLASS (a
);
2296 first_not_finished
= i
;
2300 start
= ALLOCNO_MIN (a
);
2301 /* If we skip an allocno, the allocno with smaller ids will
2302 be also skipped because of the secondary sorting the
2303 range finishes (see function
2304 allocno_range_compare_func). */
2305 while (first_not_finished
< i
2306 && start
> ALLOCNO_MAX (ira_conflict_id_allocno_map
2307 [first_not_finished
]))
2308 first_not_finished
++;
2309 min
= first_not_finished
;
2312 /* We could increase min further in this case but it is good
2315 live_range_min
[i
] = ALLOCNO_MIN (a
);
2316 ALLOCNO_MIN (a
) = min
;
2318 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
2320 filled_area_start
= -1;
2321 for (i
= ira_allocnos_num
- 1; i
>= 0; i
--)
2323 a
= ira_conflict_id_allocno_map
[i
];
2327 || (flag_ira_algorithm
!= IRA_ALGORITHM_PRIORITY
2328 && cover_class
!= (int) ALLOCNO_COVER_CLASS (a
)))
2330 cover_class
= ALLOCNO_COVER_CLASS (a
);
2331 for (j
= 0; j
< ira_max_point
; j
++)
2333 filled_area_start
= ira_max_point
;
2335 min
= live_range_min
[i
];
2336 finish
= ALLOCNO_MAX (a
);
2337 max
= last_lived
[finish
];
2339 /* We could decrease max further in this case but it is good
2341 max
= ALLOCNO_CONFLICT_ID (a
) - 1;
2342 ALLOCNO_MAX (a
) = max
;
2343 /* In filling, we can go further A range finish to recognize
2344 intersection quickly because if the finish of subsequently
2345 processed allocno (it has smaller conflict id) range is
2346 further A range finish than they are definitely intersected
2347 (the reason for this is the allocnos with bigger conflict id
2348 have their range starts not smaller than allocnos with
2350 for (j
= min
; j
< filled_area_start
; j
++)
2352 filled_area_start
= min
;
2354 ira_free (last_lived
);
2355 ira_free (live_range_min
);
2364 ira_allocno_iterator ai
;
2365 ira_loop_tree_node_t loop_tree_node
;
2367 FOR_EACH_ALLOCNO (a
, ai
)
2369 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2371 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2372 create_cap_allocno (a
);
2373 else if (ALLOCNO_CAP (a
) == NULL
)
2375 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2376 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2377 create_cap_allocno (a
);
2384 /* The page contains code transforming more one region internal
2385 representation (IR) to one region IR which is necessary for reload.
2386 This transformation is called IR flattening. We might just rebuild
2387 the IR for one region but we don't do it because it takes a lot of
2390 /* Map: regno -> allocnos which will finally represent the regno for
2391 IR with one region. */
2392 static ira_allocno_t
*regno_top_level_allocno_map
;
2394 /* Process all allocnos originated from pseudo REGNO and copy live
2395 ranges, hard reg conflicts, and allocno stack reg attributes from
2396 low level allocnos to final allocnos which are destinations of
2397 removed stores at a loop exit. Return true if we copied live
2400 copy_info_to_removed_store_destinations (int regno
)
2403 ira_allocno_t parent_a
= NULL
;
2404 ira_loop_tree_node_t parent
;
2405 allocno_live_range_t r
;
2409 for (a
= ira_regno_allocno_map
[regno
];
2411 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2413 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))])
2414 /* This allocno will be removed. */
2416 /* Caps will be removed. */
2417 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2418 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
2420 parent
= parent
->parent
)
2421 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2422 || (parent_a
== regno_top_level_allocno_map
[REGNO (ALLOCNO_REG
2424 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)))
2426 if (parent
== NULL
|| parent_a
== NULL
)
2428 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2432 " Coping ranges of a%dr%d to a%dr%d: ",
2433 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2434 ALLOCNO_NUM (parent_a
), REGNO (ALLOCNO_REG (parent_a
)));
2435 ira_print_live_range_list (ira_dump_file
,
2436 ALLOCNO_LIVE_RANGES (a
));
2438 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2439 change_allocno_in_range_list (r
, parent_a
);
2440 ALLOCNO_LIVE_RANGES (parent_a
)
2441 = ira_merge_allocno_live_ranges (r
, ALLOCNO_LIVE_RANGES (parent_a
));
2442 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2443 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2445 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2446 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
2448 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
2449 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2450 += ALLOCNO_CALLS_CROSSED_NUM (a
);
2451 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2452 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2458 /* Flatten the IR. In other words, this function transforms IR as if
2459 it were built with one region (without loops). We could make it
2460 much simpler by rebuilding IR with one region, but unfortunately it
2461 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
2462 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2463 IRA_MAX_POINT before emitting insns on the loop borders. */
2465 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
2470 bool new_pseudos_p
, merged_p
, mem_dest_p
;
2472 enum reg_class cover_class
;
2473 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
2475 ira_loop_tree_node_t parent
, node
;
2476 allocno_live_range_t r
;
2477 ira_allocno_iterator ai
;
2478 ira_copy_iterator ci
;
2479 sparseset allocnos_live
;
2481 regno_top_level_allocno_map
2482 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
2483 memset (regno_top_level_allocno_map
, 0,
2484 max_reg_num () * sizeof (ira_allocno_t
));
2485 new_pseudos_p
= merged_p
= false;
2486 FOR_EACH_ALLOCNO (a
, ai
)
2488 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2489 /* Caps are not in the regno allocno maps and they are never
2490 will be transformed into allocnos existing after IR
2493 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
2494 ALLOCNO_CONFLICT_HARD_REGS (a
));
2496 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
2499 /* Fix final allocno attributes. */
2500 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2503 for (a
= ira_regno_allocno_map
[i
];
2505 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2507 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2508 if (ALLOCNO_SOMEWHERE_RENAMED_P (a
))
2509 new_pseudos_p
= true;
2510 if (ALLOCNO_CAP (a
) != NULL
2511 || (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
2512 || ((parent_a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)])
2515 ALLOCNO_COPIES (a
) = NULL
;
2516 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2519 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
2521 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) != NULL
)
2523 if (REGNO (ALLOCNO_REG (a
)) == REGNO (ALLOCNO_REG (parent_a
)))
2525 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2526 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2528 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2529 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
2531 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2533 fprintf (ira_dump_file
,
2534 " Moving ranges of a%dr%d to a%dr%d: ",
2535 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2536 ALLOCNO_NUM (parent_a
),
2537 REGNO (ALLOCNO_REG (parent_a
)));
2538 ira_print_live_range_list (ira_dump_file
,
2539 ALLOCNO_LIVE_RANGES (a
));
2541 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a
), parent_a
);
2542 ALLOCNO_LIVE_RANGES (parent_a
)
2543 = ira_merge_allocno_live_ranges
2544 (ALLOCNO_LIVE_RANGES (a
), ALLOCNO_LIVE_RANGES (parent_a
));
2546 ALLOCNO_LIVE_RANGES (a
) = NULL
;
2547 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2548 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2549 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
));
2552 new_pseudos_p
= true;
2555 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
2556 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
2557 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
2558 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2559 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
2560 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2561 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2562 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
2563 && ALLOCNO_NREFS (parent_a
) >= 0
2564 && ALLOCNO_FREQ (parent_a
) >= 0);
2565 cover_class
= ALLOCNO_COVER_CLASS (parent_a
);
2566 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
2567 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
2568 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
2569 for (j
= 0; j
< hard_regs_num
; j
++)
2570 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
2571 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
2572 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
2573 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
2574 for (j
= 0; j
< hard_regs_num
; j
++)
2575 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
2576 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
2577 ALLOCNO_COVER_CLASS_COST (parent_a
)
2578 -= ALLOCNO_COVER_CLASS_COST (a
);
2579 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
2580 if (ALLOCNO_CAP (parent_a
) != NULL
2582 = ALLOCNO_LOOP_TREE_NODE (parent_a
)->parent
) == NULL
2583 || (parent_a
= (parent
->regno_allocno_map
2584 [ALLOCNO_REGNO (parent_a
)])) == NULL
)
2587 ALLOCNO_COPIES (a
) = NULL
;
2588 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2590 if (mem_dest_p
&& copy_info_to_removed_store_destinations (i
))
2593 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
2594 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
2595 ira_rebuild_start_finish_chains ();
2598 /* Rebuild conflicts. */
2599 FOR_EACH_ALLOCNO (a
, ai
)
2601 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2602 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2604 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2605 ira_assert (r
->allocno
== a
);
2606 clear_allocno_conflicts (a
);
2608 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
2609 for (i
= 0; i
< ira_max_point
; i
++)
2611 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
2614 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2615 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2617 num
= ALLOCNO_NUM (a
);
2618 cover_class
= ALLOCNO_COVER_CLASS (a
);
2619 sparseset_set_bit (allocnos_live
, num
);
2620 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, n
)
2622 ira_allocno_t live_a
= ira_allocnos
[n
];
2624 if (ira_reg_classes_intersect_p
2625 [cover_class
][ALLOCNO_COVER_CLASS (live_a
)]
2626 /* Don't set up conflict for the allocno with itself. */
2628 ira_add_allocno_conflict (a
, live_a
);
2632 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
2633 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (r
->allocno
));
2635 sparseset_free (allocnos_live
);
2636 compress_conflict_vecs ();
2638 /* Mark some copies for removing and change allocnos in the rest
2640 FOR_EACH_COPY (cp
, ci
)
2642 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
2643 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
2645 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2647 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2648 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
2649 ALLOCNO_NUM (cp
->first
), REGNO (ALLOCNO_REG (cp
->first
)),
2650 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
2651 ALLOCNO_NUM (cp
->second
), REGNO (ALLOCNO_REG (cp
->second
)));
2652 cp
->loop_tree_node
= NULL
;
2655 first
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->first
))];
2656 second
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->second
))];
2657 node
= cp
->loop_tree_node
;
2659 keep_p
= true; /* It copy generated in ira-emit.c. */
2662 /* Check that the copy was not propagated from level on
2663 which we will have different pseudos. */
2664 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
2665 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
2666 keep_p
= ((REGNO (ALLOCNO_REG (first
))
2667 == REGNO (ALLOCNO_REG (node_first
)))
2668 && (REGNO (ALLOCNO_REG (second
))
2669 == REGNO (ALLOCNO_REG (node_second
))));
2673 cp
->loop_tree_node
= ira_loop_tree_root
;
2675 cp
->second
= second
;
2679 cp
->loop_tree_node
= NULL
;
2680 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2681 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
2682 cp
->num
, ALLOCNO_NUM (cp
->first
),
2683 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
2684 REGNO (ALLOCNO_REG (cp
->second
)));
2687 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2688 FOR_EACH_ALLOCNO (a
, ai
)
2690 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2691 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2693 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2694 fprintf (ira_dump_file
, " Remove a%dr%d\n",
2695 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
2699 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2700 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_REG (a
));
2701 ALLOCNO_CAP (a
) = NULL
;
2702 /* Restore updated costs for assignments from reload. */
2703 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
2704 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);
2705 if (! ALLOCNO_ASSIGNED_P (a
))
2706 ira_free_allocno_updated_costs (a
);
2707 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2708 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2710 /* Remove unnecessary copies. */
2711 FOR_EACH_COPY (cp
, ci
)
2713 if (cp
->loop_tree_node
== NULL
)
2715 ira_copies
[cp
->num
] = NULL
;
2720 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
2721 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
2722 ira_add_allocno_copy_to_list (cp
);
2723 ira_swap_allocno_copy_ends_if_necessary (cp
);
2725 rebuild_regno_allocno_maps ();
2726 if (ira_max_point
!= ira_max_point_before_emit
)
2727 ira_compress_allocno_live_ranges ();
2728 ira_free (regno_top_level_allocno_map
);
2733 #ifdef ENABLE_IRA_CHECKING
2734 /* Check creation of all allocnos. Allocnos on lower levels should
2735 have allocnos or caps on all upper levels. */
2737 check_allocno_creation (void)
2740 ira_allocno_iterator ai
;
2741 ira_loop_tree_node_t loop_tree_node
;
2743 FOR_EACH_ALLOCNO (a
, ai
)
2745 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2746 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
2748 if (loop_tree_node
== ira_loop_tree_root
)
2750 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2751 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2752 else if (ALLOCNO_CAP (a
) == NULL
)
2753 ira_assert (loop_tree_node
->parent
2754 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
2755 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
2761 /* Identify allocnos which prefer a register class with a single hard register.
2762 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
2763 less likely to use the preferred singleton register. */
2765 update_conflict_hard_reg_costs (void)
2768 ira_allocno_iterator ai
;
2771 FOR_EACH_ALLOCNO (a
, ai
)
2773 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
2774 enum reg_class pref
= reg_preferred_class (ALLOCNO_REGNO (a
));
2776 if (reg_class_size
[pref
] != 1)
2778 index
= (ira_class_hard_reg_index
[cover_class
]
2779 [ira_class_hard_regs
[pref
][0]]);
2782 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) == NULL
2783 || ALLOCNO_HARD_REG_COSTS (a
) == NULL
)
2786 for (i
= ira_class_hard_regs_num
[cover_class
] - 1; i
>= 0; i
--)
2787 if (ALLOCNO_HARD_REG_COSTS (a
)[i
] > ALLOCNO_COVER_CLASS_COST (a
)
2788 && min
> ALLOCNO_HARD_REG_COSTS (a
)[i
])
2789 min
= ALLOCNO_HARD_REG_COSTS (a
)[i
];
2792 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
2794 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[index
]
2795 -= min
- ALLOCNO_COVER_CLASS_COST (a
);
2799 /* Create a internal representation (IR) for IRA (allocnos, copies,
2800 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2801 the loops (except the root which corresponds the all function) and
2802 correspondingly allocnos for the loops will be not created. Such
2803 parameter value is used for Chaitin-Briggs coloring. The function
2804 returns TRUE if we generate loop structure (besides nodes
2805 representing all function and the basic blocks) for regional
2806 allocation. A true return means that we really need to flatten IR
2807 before the reload. */
2809 ira_build (bool loops_p
)
2813 initiate_cost_vectors ();
2814 initiate_allocnos ();
2816 create_loop_tree_nodes (loops_p
);
2820 ira_create_allocno_live_ranges ();
2821 remove_unnecessary_regions (false);
2822 ira_compress_allocno_live_ranges ();
2823 update_bad_spill_attribute ();
2824 loops_p
= more_one_region_p ();
2827 propagate_allocno_info ();
2830 ira_tune_allocno_costs_and_cover_classes ();
2831 #ifdef ENABLE_IRA_CHECKING
2832 check_allocno_creation ();
2834 setup_min_max_allocno_live_range_point ();
2835 sort_conflict_id_allocno_map ();
2836 setup_min_max_conflict_allocno_ids ();
2837 ira_build_conflicts ();
2838 update_conflict_hard_reg_costs ();
2839 if (! ira_conflicts_p
)
2842 ira_allocno_iterator ai
;
2844 /* Remove all regions but root one. */
2847 remove_unnecessary_regions (true);
2850 /* We don't save hard registers around calls for fast allocation
2851 -- add caller clobbered registers as conflicting ones to
2852 allocno crossing calls. */
2853 FOR_EACH_ALLOCNO (a
, ai
)
2854 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
2856 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
2858 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
2862 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2863 print_copies (ira_dump_file
);
2864 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2868 allocno_live_range_t r
;
2869 ira_allocno_iterator ai
;
2872 FOR_EACH_ALLOCNO (a
, ai
)
2873 n
+= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
);
2875 FOR_EACH_ALLOCNO (a
, ai
)
2876 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2878 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
2879 VEC_length (loop_p
, ira_loops
.larray
), n_basic_blocks
,
2881 fprintf (ira_dump_file
,
2882 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2883 ira_allocnos_num
, ira_copies_num
, n
, nr
);
2888 /* Release the data created by function ira_build. */
2892 finish_loop_tree_nodes ();
2895 finish_cost_vectors ();
2896 ira_finish_allocno_live_ranges ();