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_BAD_SPILL_P (a
) = false;
460 ALLOCNO_IN_GRAPH_P (a
) = false;
461 ALLOCNO_ASSIGNED_P (a
) = false;
462 ALLOCNO_MAY_BE_SPILLED_P (a
) = false;
463 ALLOCNO_SPLAY_REMOVED_P (a
) = false;
464 ALLOCNO_CONFLICT_VEC_P (a
) = false;
465 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
466 ALLOCNO_COPIES (a
) = NULL
;
467 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
468 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
469 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
470 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
471 ALLOCNO_LEFT_CONFLICTS_NUM (a
) = -1;
472 ALLOCNO_COVER_CLASS (a
) = NO_REGS
;
473 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = 0;
474 ALLOCNO_COVER_CLASS_COST (a
) = 0;
475 ALLOCNO_MEMORY_COST (a
) = 0;
476 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
477 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
478 ALLOCNO_NEXT_BUCKET_ALLOCNO (a
) = NULL
;
479 ALLOCNO_PREV_BUCKET_ALLOCNO (a
) = NULL
;
480 ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) = a
;
481 ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) = a
;
482 ALLOCNO_LIVE_RANGES (a
) = NULL
;
483 ALLOCNO_MIN (a
) = INT_MAX
;
484 ALLOCNO_MAX (a
) = -1;
485 ALLOCNO_CONFLICT_ID (a
) = ira_allocnos_num
;
486 VEC_safe_push (ira_allocno_t
, heap
, allocno_vec
, a
);
487 ira_allocnos
= VEC_address (ira_allocno_t
, allocno_vec
);
488 ira_allocnos_num
= VEC_length (ira_allocno_t
, allocno_vec
);
489 VEC_safe_push (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
, a
);
490 ira_conflict_id_allocno_map
491 = VEC_address (ira_allocno_t
, ira_conflict_id_allocno_map_vec
);
495 /* Set up cover class for A and update its conflict hard registers. */
497 ira_set_allocno_cover_class (ira_allocno_t a
, enum reg_class cover_class
)
499 ALLOCNO_COVER_CLASS (a
) = cover_class
;
500 IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a
),
501 reg_class_contents
[cover_class
]);
502 IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
503 reg_class_contents
[cover_class
]);
506 /* Return TRUE if the conflict vector with NUM elements is more
507 profitable than conflict bit vector for A. */
509 ira_conflict_vector_profitable_p (ira_allocno_t a
, int num
)
513 if (ALLOCNO_MAX (a
) < ALLOCNO_MIN (a
))
514 /* We prefer bit vector in such case because it does not result in
518 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
) / IRA_INT_BITS
;
519 return (2 * sizeof (ira_allocno_t
) * (num
+ 1)
520 < 3 * nw
* sizeof (IRA_INT_TYPE
));
523 /* Allocates and initialize the conflict vector of A for NUM
524 conflicting allocnos. */
526 ira_allocate_allocno_conflict_vec (ira_allocno_t a
, int num
)
531 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
532 num
++; /* for NULL end marker */
533 size
= sizeof (ira_allocno_t
) * num
;
534 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
535 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
537 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
538 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
539 ALLOCNO_CONFLICT_VEC_P (a
) = true;
542 /* Allocate and initialize the conflict bit vector of A. */
544 allocate_allocno_conflict_bit_vec (ira_allocno_t a
)
548 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) == NULL
);
549 size
= ((ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
) + IRA_INT_BITS
)
550 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
551 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) = ira_allocate (size
);
552 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0, size
);
553 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) = size
;
554 ALLOCNO_CONFLICT_VEC_P (a
) = false;
557 /* Allocate and initialize the conflict vector or conflict bit vector
558 of A for NUM conflicting allocnos whatever is more profitable. */
560 ira_allocate_allocno_conflicts (ira_allocno_t a
, int num
)
562 if (ira_conflict_vector_profitable_p (a
, num
))
563 ira_allocate_allocno_conflict_vec (a
, num
);
565 allocate_allocno_conflict_bit_vec (a
);
568 /* Add A2 to the conflicts of A1. */
570 add_to_allocno_conflicts (ira_allocno_t a1
, ira_allocno_t a2
)
575 if (ALLOCNO_CONFLICT_VEC_P (a1
))
579 num
= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
) + 2;
580 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
)
581 >= num
* sizeof (ira_allocno_t
))
582 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
585 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
586 vec
= (ira_allocno_t
*) ira_allocate (size
);
587 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
588 sizeof (ira_allocno_t
) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
));
589 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
590 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
591 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
595 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1
)++;
599 int nw
, added_head_nw
, id
;
602 id
= ALLOCNO_CONFLICT_ID (a2
);
603 vec
= (IRA_INT_TYPE
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
);
604 if (ALLOCNO_MIN (a1
) > id
)
606 /* Expand head of the bit vector. */
607 added_head_nw
= (ALLOCNO_MIN (a1
) - id
- 1) / IRA_INT_BITS
+ 1;
608 nw
= (ALLOCNO_MAX (a1
) - ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
609 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
610 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) >= size
)
612 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
613 vec
, nw
* sizeof (IRA_INT_TYPE
));
614 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
619 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
620 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
621 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
622 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
623 nw
* sizeof (IRA_INT_TYPE
));
624 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
626 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
627 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
628 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
629 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
630 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
632 ALLOCNO_MIN (a1
) -= added_head_nw
* IRA_INT_BITS
;
634 else if (ALLOCNO_MAX (a1
) < id
)
636 nw
= (id
- ALLOCNO_MIN (a1
)) / IRA_INT_BITS
+ 1;
637 size
= nw
* sizeof (IRA_INT_TYPE
);
638 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) < size
)
640 /* Expand tail of the bit vector. */
641 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
642 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
643 memcpy (vec
, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
),
644 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
645 memset ((char *) vec
+ ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
),
646 0, size
- ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
));
647 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
));
648 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1
) = vec
;
649 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1
) = size
;
651 ALLOCNO_MAX (a1
) = id
;
653 SET_ALLOCNO_SET_BIT (vec
, id
, ALLOCNO_MIN (a1
), ALLOCNO_MAX (a1
));
657 /* Add A1 to the conflicts of A2 and vise versa. */
659 ira_add_allocno_conflict (ira_allocno_t a1
, ira_allocno_t a2
)
661 add_to_allocno_conflicts (a1
, a2
);
662 add_to_allocno_conflicts (a2
, a1
);
665 /* Clear all conflicts of allocno A. */
667 clear_allocno_conflicts (ira_allocno_t a
)
669 if (ALLOCNO_CONFLICT_VEC_P (a
))
671 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = 0;
672 ((ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
))[0] = NULL
;
674 else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a
) != 0)
678 nw
= (ALLOCNO_MAX (a
) - ALLOCNO_MIN (a
)) / IRA_INT_BITS
+ 1;
679 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
), 0,
680 nw
* sizeof (IRA_INT_TYPE
));
684 /* The array used to find duplications in conflict vectors of
686 static int *allocno_conflict_check
;
688 /* The value used to mark allocation presence in conflict vector of
689 the current allocno. */
690 static int curr_allocno_conflict_check_tick
;
692 /* Remove duplications in conflict vector of A. */
694 compress_allocno_conflict_vec (ira_allocno_t a
)
696 ira_allocno_t
*vec
, conflict_a
;
699 ira_assert (ALLOCNO_CONFLICT_VEC_P (a
));
700 vec
= (ira_allocno_t
*) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
);
701 curr_allocno_conflict_check_tick
++;
702 for (i
= j
= 0; (conflict_a
= vec
[i
]) != NULL
; i
++)
704 if (allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
705 != curr_allocno_conflict_check_tick
)
707 allocno_conflict_check
[ALLOCNO_NUM (conflict_a
)]
708 = curr_allocno_conflict_check_tick
;
709 vec
[j
++] = conflict_a
;
712 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
) = j
;
716 /* Remove duplications in conflict vectors of all allocnos. */
718 compress_conflict_vecs (void)
721 ira_allocno_iterator ai
;
723 allocno_conflict_check
724 = (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
725 memset (allocno_conflict_check
, 0, sizeof (int) * ira_allocnos_num
);
726 curr_allocno_conflict_check_tick
= 0;
727 FOR_EACH_ALLOCNO (a
, ai
)
728 if (ALLOCNO_CONFLICT_VEC_P (a
))
729 compress_allocno_conflict_vec (a
);
730 ira_free (allocno_conflict_check
);
733 /* This recursive function outputs allocno A and if it is a cap the
734 function outputs its members. */
736 ira_print_expanded_allocno (ira_allocno_t a
)
740 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
741 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
742 fprintf (ira_dump_file
, ",b%d", bb
->index
);
744 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop
->num
);
745 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
747 fprintf (ira_dump_file
, ":");
748 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
750 fprintf (ira_dump_file
, ")");
753 /* Create and return the cap representing allocno A in the
756 create_cap_allocno (ira_allocno_t a
)
759 ira_loop_tree_node_t parent
;
760 enum reg_class cover_class
;
762 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a
) == a
763 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a
) == a
);
764 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
765 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
766 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
767 cover_class
= ALLOCNO_COVER_CLASS (a
);
768 ira_set_allocno_cover_class (cap
, cover_class
);
769 ALLOCNO_AVAILABLE_REGS_NUM (cap
) = ALLOCNO_AVAILABLE_REGS_NUM (a
);
770 ALLOCNO_CAP_MEMBER (cap
) = a
;
771 ALLOCNO_CAP (a
) = cap
;
772 ALLOCNO_COVER_CLASS_COST (cap
) = ALLOCNO_COVER_CLASS_COST (a
);
773 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
774 ira_allocate_and_copy_costs
775 (&ALLOCNO_HARD_REG_COSTS (cap
), cover_class
, ALLOCNO_HARD_REG_COSTS (a
));
776 ira_allocate_and_copy_costs
777 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), cover_class
,
778 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
779 ALLOCNO_BAD_SPILL_P (cap
) = ALLOCNO_BAD_SPILL_P (a
);
780 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
781 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
782 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
783 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap
),
784 ALLOCNO_CONFLICT_HARD_REGS (a
));
785 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap
),
786 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
787 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
789 ALLOCNO_NO_STACK_REG_P (cap
) = ALLOCNO_NO_STACK_REG_P (a
);
790 ALLOCNO_TOTAL_NO_STACK_REG_P (cap
) = ALLOCNO_TOTAL_NO_STACK_REG_P (a
);
792 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
794 fprintf (ira_dump_file
, " Creating cap ");
795 ira_print_expanded_allocno (cap
);
796 fprintf (ira_dump_file
, "\n");
801 /* Create and return allocno live range with given attributes. */
803 ira_create_allocno_live_range (ira_allocno_t a
, int start
, int finish
,
804 allocno_live_range_t next
)
806 allocno_live_range_t p
;
808 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
816 /* Copy allocno live range R and return the result. */
817 static allocno_live_range_t
818 copy_allocno_live_range (allocno_live_range_t r
)
820 allocno_live_range_t p
;
822 p
= (allocno_live_range_t
) pool_alloc (allocno_live_range_pool
);
827 /* Copy allocno live range list given by its head R and return the
830 ira_copy_allocno_live_range_list (allocno_live_range_t r
)
832 allocno_live_range_t p
, first
, last
;
836 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
838 p
= copy_allocno_live_range (r
);
848 /* Merge ranges R1 and R2 and returns the result. The function
849 maintains the order of ranges and tries to minimize number of the
852 ira_merge_allocno_live_ranges (allocno_live_range_t r1
,
853 allocno_live_range_t r2
)
855 allocno_live_range_t first
, last
, temp
;
861 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
863 if (r1
->start
< r2
->start
)
869 if (r1
->start
<= r2
->finish
+ 1)
871 /* Intersected ranges: merge r1 and r2 into r1. */
872 r1
->start
= r2
->start
;
873 if (r1
->finish
< r2
->finish
)
874 r1
->finish
= r2
->finish
;
877 ira_finish_allocno_live_range (temp
);
880 /* To try to merge with subsequent ranges in r1. */
887 /* Add r1 to the result. */
898 /* To try to merge with subsequent ranges in r2. */
910 ira_assert (r1
->next
== NULL
);
918 ira_assert (r2
->next
== NULL
);
922 ira_assert (last
->next
== NULL
);
927 /* Return TRUE if live ranges R1 and R2 intersect. */
929 ira_allocno_live_ranges_intersect_p (allocno_live_range_t r1
,
930 allocno_live_range_t r2
)
932 /* Remember the live ranges are always kept ordered. */
933 while (r1
!= NULL
&& r2
!= NULL
)
935 if (r1
->start
> r2
->finish
)
937 else if (r2
->start
> r1
->finish
)
945 /* Free allocno live range R. */
947 ira_finish_allocno_live_range (allocno_live_range_t r
)
949 pool_free (allocno_live_range_pool
, r
);
952 /* Free list of allocno live ranges starting with R. */
954 ira_finish_allocno_live_range_list (allocno_live_range_t r
)
956 allocno_live_range_t next_r
;
958 for (; r
!= NULL
; r
= next_r
)
961 ira_finish_allocno_live_range (r
);
965 /* Free updated register costs of allocno A. */
967 ira_free_allocno_updated_costs (ira_allocno_t a
)
969 enum reg_class cover_class
;
971 cover_class
= ALLOCNO_COVER_CLASS (a
);
972 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
973 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
974 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
975 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
976 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
978 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
981 /* Free the memory allocated for allocno A. */
983 finish_allocno (ira_allocno_t a
)
985 enum reg_class cover_class
= ALLOCNO_COVER_CLASS (a
);
987 ira_allocnos
[ALLOCNO_NUM (a
)] = NULL
;
988 ira_conflict_id_allocno_map
[ALLOCNO_CONFLICT_ID (a
)] = NULL
;
989 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
) != NULL
)
990 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a
));
991 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
992 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a
), cover_class
);
993 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
994 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
), cover_class
);
995 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
996 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), cover_class
);
997 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
998 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1000 ira_finish_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
1001 pool_free (allocno_pool
, a
);
1004 /* Free the memory allocated for all allocnos. */
1006 finish_allocnos (void)
1009 ira_allocno_iterator ai
;
1011 FOR_EACH_ALLOCNO (a
, ai
)
1013 ira_free (ira_regno_allocno_map
);
1014 VEC_free (ira_allocno_t
, heap
, ira_conflict_id_allocno_map_vec
);
1015 VEC_free (ira_allocno_t
, heap
, allocno_vec
);
1016 free_alloc_pool (allocno_pool
);
1017 free_alloc_pool (allocno_live_range_pool
);
1022 /* Pools for copies. */
1023 static alloc_pool copy_pool
;
1025 /* Vec containing references to all created copies. It is a
1026 container of array ira_copies. */
1027 static VEC(ira_copy_t
,heap
) *copy_vec
;
1029 /* The function initializes data concerning allocno copies. */
1031 initiate_copies (void)
1034 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy
), 100);
1035 copy_vec
= VEC_alloc (ira_copy_t
, heap
, get_max_uid ());
1040 /* Return copy connecting A1 and A2 and originated from INSN of
1041 LOOP_TREE_NODE if any. */
1043 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx insn
,
1044 ira_loop_tree_node_t loop_tree_node
)
1046 ira_copy_t cp
, next_cp
;
1047 ira_allocno_t another_a
;
1049 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
1051 if (cp
->first
== a1
)
1053 next_cp
= cp
->next_first_allocno_copy
;
1054 another_a
= cp
->second
;
1056 else if (cp
->second
== a1
)
1058 next_cp
= cp
->next_second_allocno_copy
;
1059 another_a
= cp
->first
;
1063 if (another_a
== a2
&& cp
->insn
== insn
1064 && cp
->loop_tree_node
== loop_tree_node
)
1070 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1071 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1073 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1074 bool constraint_p
, rtx insn
,
1075 ira_loop_tree_node_t loop_tree_node
)
1079 cp
= (ira_copy_t
) pool_alloc (copy_pool
);
1080 cp
->num
= ira_copies_num
;
1082 cp
->second
= second
;
1084 cp
->constraint_p
= constraint_p
;
1086 cp
->loop_tree_node
= loop_tree_node
;
1087 VEC_safe_push (ira_copy_t
, heap
, copy_vec
, cp
);
1088 ira_copies
= VEC_address (ira_copy_t
, copy_vec
);
1089 ira_copies_num
= VEC_length (ira_copy_t
, copy_vec
);
1093 /* Attach a copy CP to allocnos involved into the copy. */
1095 ira_add_allocno_copy_to_list (ira_copy_t cp
)
1097 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1099 cp
->prev_first_allocno_copy
= NULL
;
1100 cp
->prev_second_allocno_copy
= NULL
;
1101 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
1102 if (cp
->next_first_allocno_copy
!= NULL
)
1104 if (cp
->next_first_allocno_copy
->first
== first
)
1105 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
1107 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1109 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1110 if (cp
->next_second_allocno_copy
!= NULL
)
1112 if (cp
->next_second_allocno_copy
->second
== second
)
1113 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1115 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1117 ALLOCNO_COPIES (first
) = cp
;
1118 ALLOCNO_COPIES (second
) = cp
;
1121 /* Detach a copy CP from allocnos involved into the copy. */
1123 ira_remove_allocno_copy_from_list (ira_copy_t cp
)
1125 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1126 ira_copy_t prev
, next
;
1128 next
= cp
->next_first_allocno_copy
;
1129 prev
= cp
->prev_first_allocno_copy
;
1131 ALLOCNO_COPIES (first
) = next
;
1132 else if (prev
->first
== first
)
1133 prev
->next_first_allocno_copy
= next
;
1135 prev
->next_second_allocno_copy
= next
;
1138 if (next
->first
== first
)
1139 next
->prev_first_allocno_copy
= prev
;
1141 next
->prev_second_allocno_copy
= prev
;
1143 cp
->prev_first_allocno_copy
= cp
->next_first_allocno_copy
= NULL
;
1145 next
= cp
->next_second_allocno_copy
;
1146 prev
= cp
->prev_second_allocno_copy
;
1148 ALLOCNO_COPIES (second
) = next
;
1149 else if (prev
->second
== second
)
1150 prev
->next_second_allocno_copy
= next
;
1152 prev
->next_first_allocno_copy
= next
;
1155 if (next
->second
== second
)
1156 next
->prev_second_allocno_copy
= prev
;
1158 next
->prev_first_allocno_copy
= prev
;
1160 cp
->prev_second_allocno_copy
= cp
->next_second_allocno_copy
= NULL
;
1163 /* Make a copy CP a canonical copy where number of the
1164 first allocno is less than the second one. */
1166 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1171 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1175 cp
->first
= cp
->second
;
1178 temp_cp
= cp
->prev_first_allocno_copy
;
1179 cp
->prev_first_allocno_copy
= cp
->prev_second_allocno_copy
;
1180 cp
->prev_second_allocno_copy
= temp_cp
;
1182 temp_cp
= cp
->next_first_allocno_copy
;
1183 cp
->next_first_allocno_copy
= cp
->next_second_allocno_copy
;
1184 cp
->next_second_allocno_copy
= temp_cp
;
1187 /* Create (or update frequency if the copy already exists) and return
1188 the copy of allocnos FIRST and SECOND with frequency FREQ
1189 corresponding to move insn INSN (if any) and originated from
1192 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1193 bool constraint_p
, rtx insn
,
1194 ira_loop_tree_node_t loop_tree_node
)
1198 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1203 cp
= ira_create_copy (first
, second
, freq
, constraint_p
, insn
,
1205 ira_assert (first
!= NULL
&& second
!= NULL
);
1206 ira_add_allocno_copy_to_list (cp
);
1207 ira_swap_allocno_copy_ends_if_necessary (cp
);
1211 /* Print info about copy CP into file F. */
1213 print_copy (FILE *f
, ira_copy_t cp
)
1215 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp
->num
,
1216 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1217 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
,
1219 ? "move" : cp
->constraint_p
? "constraint" : "shuffle");
1222 /* Print info about copy CP into stderr. */
1224 ira_debug_copy (ira_copy_t cp
)
1226 print_copy (stderr
, cp
);
1229 /* Print info about all copies into file F. */
1231 print_copies (FILE *f
)
1234 ira_copy_iterator ci
;
1236 FOR_EACH_COPY (cp
, ci
)
1240 /* Print info about all copies into stderr. */
1242 ira_debug_copies (void)
1244 print_copies (stderr
);
1247 /* Print info about copies involving allocno A into file F. */
1249 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1251 ira_allocno_t another_a
;
1252 ira_copy_t cp
, next_cp
;
1254 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1255 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1259 next_cp
= cp
->next_first_allocno_copy
;
1260 another_a
= cp
->second
;
1262 else if (cp
->second
== a
)
1264 next_cp
= cp
->next_second_allocno_copy
;
1265 another_a
= cp
->first
;
1269 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1270 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1275 /* Print info about copies involving allocno A into stderr. */
1277 ira_debug_allocno_copies (ira_allocno_t a
)
1279 print_allocno_copies (stderr
, a
);
1282 /* The function frees memory allocated for copy CP. */
1284 finish_copy (ira_copy_t cp
)
1286 pool_free (copy_pool
, cp
);
1290 /* Free memory allocated for all copies. */
1292 finish_copies (void)
1295 ira_copy_iterator ci
;
1297 FOR_EACH_COPY (cp
, ci
)
1299 VEC_free (ira_copy_t
, heap
, copy_vec
);
1300 free_alloc_pool (copy_pool
);
1305 /* Pools for cost vectors. It is defined only for cover classes. */
1306 static alloc_pool cost_vector_pool
[N_REG_CLASSES
];
1308 /* The function initiates work with hard register cost vectors. It
1309 creates allocation pool for each cover class. */
1311 initiate_cost_vectors (void)
1314 enum reg_class cover_class
;
1316 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1318 cover_class
= ira_reg_class_cover
[i
];
1319 cost_vector_pool
[cover_class
]
1320 = create_alloc_pool ("cost vectors",
1322 * ira_class_hard_regs_num
[cover_class
],
1327 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1329 ira_allocate_cost_vector (enum reg_class cover_class
)
1331 return (int *) pool_alloc (cost_vector_pool
[cover_class
]);
1334 /* Free a cost vector VEC for COVER_CLASS. */
1336 ira_free_cost_vector (int *vec
, enum reg_class cover_class
)
1338 ira_assert (vec
!= NULL
);
1339 pool_free (cost_vector_pool
[cover_class
], vec
);
1342 /* Finish work with hard register cost vectors. Release allocation
1343 pool for each cover class. */
1345 finish_cost_vectors (void)
1348 enum reg_class cover_class
;
1350 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1352 cover_class
= ira_reg_class_cover
[i
];
1353 free_alloc_pool (cost_vector_pool
[cover_class
]);
1359 /* The current loop tree node and its regno allocno map. */
1360 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1361 ira_allocno_t
*ira_curr_regno_allocno_map
;
1363 /* This recursive function traverses loop tree with root LOOP_NODE
1364 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1365 correspondingly in preorder and postorder. The function sets up
1366 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1367 basic block nodes of LOOP_NODE is also processed (before its
1370 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1371 void (*preorder_func
) (ira_loop_tree_node_t
),
1372 void (*postorder_func
) (ira_loop_tree_node_t
))
1374 ira_loop_tree_node_t subloop_node
;
1376 ira_assert (loop_node
->bb
== NULL
);
1377 ira_curr_loop_tree_node
= loop_node
;
1378 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1380 if (preorder_func
!= NULL
)
1381 (*preorder_func
) (loop_node
);
1384 for (subloop_node
= loop_node
->children
;
1385 subloop_node
!= NULL
;
1386 subloop_node
= subloop_node
->next
)
1387 if (subloop_node
->bb
!= NULL
)
1389 if (preorder_func
!= NULL
)
1390 (*preorder_func
) (subloop_node
);
1392 if (postorder_func
!= NULL
)
1393 (*postorder_func
) (subloop_node
);
1396 for (subloop_node
= loop_node
->subloops
;
1397 subloop_node
!= NULL
;
1398 subloop_node
= subloop_node
->subloop_next
)
1400 ira_assert (subloop_node
->bb
== NULL
);
1401 ira_traverse_loop_tree (bb_p
, subloop_node
,
1402 preorder_func
, postorder_func
);
1405 ira_curr_loop_tree_node
= loop_node
;
1406 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1408 if (postorder_func
!= NULL
)
1409 (*postorder_func
) (loop_node
);
1414 /* The basic block currently being processed. */
1415 static basic_block curr_bb
;
1417 /* This recursive function creates allocnos corresponding to
1418 pseudo-registers containing in X. True OUTPUT_P means that X is
1421 create_insn_allocnos (rtx x
, bool output_p
)
1425 enum rtx_code code
= GET_CODE (x
);
1431 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1435 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1436 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1438 ALLOCNO_NREFS (a
)++;
1439 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1441 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1445 else if (code
== SET
)
1447 create_insn_allocnos (SET_DEST (x
), true);
1448 create_insn_allocnos (SET_SRC (x
), false);
1451 else if (code
== CLOBBER
)
1453 create_insn_allocnos (XEXP (x
, 0), true);
1456 else if (code
== MEM
)
1458 create_insn_allocnos (XEXP (x
, 0), false);
1461 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1462 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1464 create_insn_allocnos (XEXP (x
, 0), true);
1465 create_insn_allocnos (XEXP (x
, 0), false);
1469 fmt
= GET_RTX_FORMAT (code
);
1470 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1473 create_insn_allocnos (XEXP (x
, i
), output_p
);
1474 else if (fmt
[i
] == 'E')
1475 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1476 create_insn_allocnos (XVECEXP (x
, i
, j
), output_p
);
1480 /* Create allocnos corresponding to pseudo-registers living in the
1481 basic block represented by the corresponding loop tree node
1484 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1491 curr_bb
= bb
= bb_node
->bb
;
1492 ira_assert (bb
!= NULL
);
1493 FOR_BB_INSNS_REVERSE (bb
, insn
)
1495 create_insn_allocnos (PATTERN (insn
), false);
1496 /* It might be a allocno living through from one subloop to
1498 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1499 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1500 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1503 /* Create allocnos corresponding to pseudo-registers living on edge E
1504 (a loop entry or exit). Also mark the allocnos as living on the
1507 create_loop_allocnos (edge e
)
1510 bitmap live_in_regs
, border_allocnos
;
1512 ira_loop_tree_node_t parent
;
1514 live_in_regs
= DF_LR_IN (e
->dest
);
1515 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1516 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e
->src
),
1517 FIRST_PSEUDO_REGISTER
, i
, bi
)
1518 if (bitmap_bit_p (live_in_regs
, i
))
1520 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1522 /* The order of creations is important for right
1523 ira_regno_allocno_map. */
1524 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1525 && parent
->regno_allocno_map
[i
] == NULL
)
1526 ira_create_allocno (i
, false, parent
);
1527 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1529 bitmap_set_bit (border_allocnos
,
1530 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1534 /* Create allocnos corresponding to pseudo-registers living in loop
1535 represented by the corresponding loop tree node LOOP_NODE. This
1536 function is called by ira_traverse_loop_tree. */
1538 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1540 if (loop_node
->bb
!= NULL
)
1541 create_bb_allocnos (loop_node
);
1542 else if (loop_node
!= ira_loop_tree_root
)
1547 VEC (edge
, heap
) *edges
;
1549 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1550 if (e
->src
!= loop_node
->loop
->latch
)
1551 create_loop_allocnos (e
);
1553 edges
= get_loop_exit_edges (loop_node
->loop
);
1554 for (i
= 0; VEC_iterate (edge
, edges
, i
, e
); i
++)
1555 create_loop_allocnos (e
);
1556 VEC_free (edge
, heap
, edges
);
1560 /* Propagate information about allocnos modified inside the loop given
1561 by its LOOP_TREE_NODE to its parent. */
1563 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
1565 if (loop_tree_node
== ira_loop_tree_root
)
1567 ira_assert (loop_tree_node
->bb
== NULL
);
1568 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
1569 loop_tree_node
->modified_regnos
);
1572 /* Propagate new info about allocno A (see comments about accumulated
1573 info in allocno definition) to the corresponding allocno on upper
1574 loop tree level. So allocnos on upper levels accumulate
1575 information about the corresponding allocnos in nested regions.
1576 The new info means allocno info finally calculated in this
1579 propagate_allocno_info (void)
1582 ira_allocno_t a
, parent_a
;
1583 ira_loop_tree_node_t parent
;
1584 enum reg_class cover_class
;
1586 if (flag_ira_algorithm
!= IRA_ALGORITHM_REGIONAL
1587 && flag_ira_algorithm
!= IRA_ALGORITHM_MIXED
)
1589 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
1590 for (a
= ira_regno_allocno_map
[i
];
1592 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
1593 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
1594 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
1595 /* There are no caps yet at this point. So use
1596 border_allocnos to find allocnos for the propagation. */
1597 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
1600 if (! ALLOCNO_BAD_SPILL_P (a
))
1601 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
1602 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
1603 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
1604 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
1606 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
1607 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
1609 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
1610 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1611 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
1612 += ALLOCNO_CALLS_CROSSED_NUM (a
);
1613 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
1614 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1615 cover_class
= ALLOCNO_COVER_CLASS (a
);
1616 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (parent_a
));
1617 ira_allocate_and_accumulate_costs
1618 (&ALLOCNO_HARD_REG_COSTS (parent_a
), cover_class
,
1619 ALLOCNO_HARD_REG_COSTS (a
));
1620 ira_allocate_and_accumulate_costs
1621 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
1623 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
1624 ALLOCNO_COVER_CLASS_COST (parent_a
)
1625 += ALLOCNO_COVER_CLASS_COST (a
);
1626 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
1630 /* Create allocnos corresponding to pseudo-registers in the current
1631 function. Traverse the loop tree for this. */
1633 create_allocnos (void)
1635 /* We need to process BB first to correctly link allocnos by member
1636 next_regno_allocno. */
1637 ira_traverse_loop_tree (true, ira_loop_tree_root
,
1638 create_loop_tree_node_allocnos
, NULL
);
1640 ira_traverse_loop_tree (false, ira_loop_tree_root
, NULL
,
1641 propagate_modified_regnos
);
1646 /* The page contains function to remove some regions from a separate
1647 register allocation. We remove regions whose separate allocation
1648 will hardly improve the result. As a result we speed up regional
1649 register allocation. */
1651 /* The function changes allocno in range list given by R onto A. */
1653 change_allocno_in_range_list (allocno_live_range_t r
, ira_allocno_t a
)
1655 for (; r
!= NULL
; r
= r
->next
)
1659 /* Return TRUE if NODE represents a loop with low register
1662 low_pressure_loop_node_p (ira_loop_tree_node_t node
)
1665 enum reg_class cover_class
;
1667 if (node
->bb
!= NULL
)
1670 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1672 cover_class
= ira_reg_class_cover
[i
];
1673 if (node
->reg_pressure
[cover_class
]
1674 > ira_available_class_regs
[cover_class
])
1680 /* Sort loops for marking them for removal. We put already marked
1681 loops first, then less frequent loops next, and then outer loops
1684 loop_compare_func (const void *v1p
, const void *v2p
)
1687 ira_loop_tree_node_t l1
= *(const ira_loop_tree_node_t
*) v1p
;
1688 ira_loop_tree_node_t l2
= *(const ira_loop_tree_node_t
*) v2p
;
1690 ira_assert (l1
->parent
!= NULL
&& l2
->parent
!= NULL
);
1691 if (l1
->to_remove_p
&& ! l2
->to_remove_p
)
1693 if (! l1
->to_remove_p
&& l2
->to_remove_p
)
1695 if ((diff
= l1
->loop
->header
->frequency
- l2
->loop
->header
->frequency
) != 0)
1697 if ((diff
= (int) loop_depth (l1
->loop
) - (int) loop_depth (l2
->loop
)) != 0)
1699 /* Make sorting stable. */
1700 return l1
->loop
->num
- l2
->loop
->num
;
1704 /* Mark loops which should be removed from regional allocation. We
1705 remove a loop with low register pressure inside another loop with
1706 register pressure. In this case a separate allocation of the loop
1707 hardly helps (for irregular register file architecture it could
1708 help by choosing a better hard register in the loop but we prefer
1709 faster allocation even in this case). We also remove cheap loops
1710 if there are more than IRA_MAX_LOOPS_NUM of them. */
1712 mark_loops_for_removal (void)
1715 ira_loop_tree_node_t
*sorted_loops
;
1719 = (ira_loop_tree_node_t
*) ira_allocate (sizeof (ira_loop_tree_node_t
)
1720 * VEC_length (loop_p
,
1722 for (n
= i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
1723 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
1725 if (ira_loop_nodes
[i
].parent
== NULL
)
1727 /* Don't remove the root. */
1728 ira_loop_nodes
[i
].to_remove_p
= false;
1731 sorted_loops
[n
++] = &ira_loop_nodes
[i
];
1732 ira_loop_nodes
[i
].to_remove_p
1733 = (low_pressure_loop_node_p (ira_loop_nodes
[i
].parent
)
1734 && low_pressure_loop_node_p (&ira_loop_nodes
[i
]));
1736 qsort (sorted_loops
, n
, sizeof (ira_loop_tree_node_t
), loop_compare_func
);
1737 for (i
= 0; n
- i
+ 1 > IRA_MAX_LOOPS_NUM
; i
++)
1739 sorted_loops
[i
]->to_remove_p
= true;
1740 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1743 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1744 sorted_loops
[i
]->loop
->num
, sorted_loops
[i
]->loop
->header
->index
,
1745 sorted_loops
[i
]->loop
->header
->frequency
,
1746 loop_depth (sorted_loops
[i
]->loop
),
1747 low_pressure_loop_node_p (sorted_loops
[i
]->parent
)
1748 && low_pressure_loop_node_p (sorted_loops
[i
])
1749 ? "low pressure" : "cheap loop");
1751 ira_free (sorted_loops
);
1755 /* Definition of vector of loop tree nodes. */
1756 DEF_VEC_P(ira_loop_tree_node_t
);
1757 DEF_VEC_ALLOC_P(ira_loop_tree_node_t
, heap
);
1759 /* Vec containing references to all removed loop tree nodes. */
1760 static VEC(ira_loop_tree_node_t
,heap
) *removed_loop_vec
;
1762 /* Vec containing references to all children of loop tree nodes. */
1763 static VEC(ira_loop_tree_node_t
,heap
) *children_vec
;
1765 /* Remove subregions of NODE if their separate allocation will not
1766 improve the result. */
1768 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node
)
1772 ira_loop_tree_node_t subnode
;
1774 remove_p
= node
->to_remove_p
;
1776 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, node
);
1777 start
= VEC_length (ira_loop_tree_node_t
, children_vec
);
1778 for (subnode
= node
->children
; subnode
!= NULL
; subnode
= subnode
->next
)
1779 if (subnode
->bb
== NULL
)
1780 remove_uneccesary_loop_nodes_from_loop_tree (subnode
);
1782 VEC_safe_push (ira_loop_tree_node_t
, heap
, children_vec
, subnode
);
1783 node
->children
= node
->subloops
= NULL
;
1786 VEC_safe_push (ira_loop_tree_node_t
, heap
, removed_loop_vec
, node
);
1789 while (VEC_length (ira_loop_tree_node_t
, children_vec
) > start
)
1791 subnode
= VEC_pop (ira_loop_tree_node_t
, children_vec
);
1792 subnode
->parent
= node
;
1793 subnode
->next
= node
->children
;
1794 node
->children
= subnode
;
1795 if (subnode
->bb
== NULL
)
1797 subnode
->subloop_next
= node
->subloops
;
1798 node
->subloops
= subnode
;
1803 /* Remove allocnos from loops removed from the allocation
1806 remove_unnecessary_allocnos (void)
1810 enum reg_class cover_class
;
1811 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
1812 ira_loop_tree_node_t a_node
, parent
;
1813 allocno_live_range_t r
;
1816 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
1817 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
1821 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
1822 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
1823 if (! a_node
->to_remove_p
)
1827 for (parent
= a_node
->parent
;
1828 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
1829 && parent
->to_remove_p
;
1830 parent
= parent
->parent
)
1832 if (parent_a
== NULL
)
1834 /* There are no allocnos with the same regno in upper
1835 region -- just move the allocno to the upper
1838 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
1839 parent
->regno_allocno_map
[regno
] = a
;
1840 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
1844 /* Remove the allocno and update info of allocno in
1845 the upper region. */
1847 ira_regno_allocno_map
[regno
] = next_a
;
1849 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
1850 r
= ALLOCNO_LIVE_RANGES (a
);
1851 change_allocno_in_range_list (r
, parent_a
);
1852 ALLOCNO_LIVE_RANGES (parent_a
)
1853 = ira_merge_allocno_live_ranges
1854 (r
, ALLOCNO_LIVE_RANGES (parent_a
));
1856 ALLOCNO_LIVE_RANGES (a
) = NULL
;
1857 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (parent_a
),
1858 ALLOCNO_CONFLICT_HARD_REGS (a
));
1860 if (ALLOCNO_NO_STACK_REG_P (a
))
1861 ALLOCNO_NO_STACK_REG_P (parent_a
) = true;
1863 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
1864 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
1865 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
1867 (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
1868 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
1869 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
1870 += ALLOCNO_CALLS_CROSSED_NUM (a
);
1871 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
1872 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
1873 if (! ALLOCNO_BAD_SPILL_P (a
))
1874 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
1876 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
1877 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
1879 cover_class
= ALLOCNO_COVER_CLASS (a
);
1880 ira_assert (cover_class
== ALLOCNO_COVER_CLASS (parent_a
));
1881 ira_allocate_and_accumulate_costs
1882 (&ALLOCNO_HARD_REG_COSTS (parent_a
), cover_class
,
1883 ALLOCNO_HARD_REG_COSTS (a
));
1884 ira_allocate_and_accumulate_costs
1885 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
1887 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
1888 ALLOCNO_COVER_CLASS_COST (parent_a
)
1889 += ALLOCNO_COVER_CLASS_COST (a
);
1890 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
1896 ira_rebuild_start_finish_chains ();
1899 /* Remove loops from consideration. We remove loops for which a
1900 separate allocation will not improve the result. We have to do
1901 this after allocno creation and their costs and cover class
1902 evaluation because only after that the register pressure can be
1903 known and is calculated. */
1905 remove_unnecessary_regions (void)
1907 mark_loops_for_removal ();
1909 = VEC_alloc (ira_loop_tree_node_t
, heap
,
1910 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
1912 = VEC_alloc (ira_loop_tree_node_t
, heap
,
1913 last_basic_block
+ VEC_length (loop_p
, ira_loops
.larray
));
1914 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
) ;
1915 VEC_free (ira_loop_tree_node_t
, heap
, children_vec
);
1916 remove_unnecessary_allocnos ();
1917 while (VEC_length (ira_loop_tree_node_t
, removed_loop_vec
) > 0)
1918 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t
, removed_loop_vec
));
1919 VEC_free (ira_loop_tree_node_t
, heap
, removed_loop_vec
);
1924 /* At this point true value of allocno attribute bad_spill_p means
1925 that there is an insn where allocno occurs and where the allocno
1926 can not be used as memory. The function updates the attribute, now
1927 it can be true only for allocnos which can not be used as memory in
1928 an insn and in whose live ranges there is other allocno deaths.
1929 Spilling allocnos with true value will not improve the code because
1930 it will not make other allocnos colorable and additional reloads
1931 for the corresponding pseudo will be generated in reload pass for
1932 each insn it occurs.
1934 This is a trick mentioned in one classic article of Chaitin etc
1935 which is frequently omitted in other implementations of RA based on
1938 update_bad_spill_attribute (void)
1942 ira_allocno_iterator ai
;
1943 allocno_live_range_t r
;
1944 enum reg_class cover_class
;
1945 bitmap_head dead_points
[N_REG_CLASSES
];
1947 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1949 cover_class
= ira_reg_class_cover
[i
];
1950 bitmap_initialize (&dead_points
[cover_class
], ®_obstack
);
1952 FOR_EACH_ALLOCNO (a
, ai
)
1954 cover_class
= ALLOCNO_COVER_CLASS (a
);
1955 if (cover_class
== NO_REGS
)
1957 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1958 bitmap_set_bit (&dead_points
[cover_class
], r
->finish
);
1960 FOR_EACH_ALLOCNO (a
, ai
)
1962 cover_class
= ALLOCNO_COVER_CLASS (a
);
1963 if (cover_class
== NO_REGS
)
1965 if (! ALLOCNO_BAD_SPILL_P (a
))
1967 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
1969 for (i
= r
->start
+ 1; i
< r
->finish
; i
++)
1970 if (bitmap_bit_p (&dead_points
[cover_class
], i
))
1976 ALLOCNO_BAD_SPILL_P (a
) = false;
1978 for (i
= 0; i
< ira_reg_class_cover_size
; i
++)
1980 cover_class
= ira_reg_class_cover
[i
];
1981 bitmap_clear (&dead_points
[cover_class
]);
1987 /* Set up minimal and maximal live range points for allocnos. */
1989 setup_min_max_allocno_live_range_point (void)
1992 ira_allocno_t a
, parent_a
, cap
;
1993 ira_allocno_iterator ai
;
1994 allocno_live_range_t r
;
1995 ira_loop_tree_node_t parent
;
1997 FOR_EACH_ALLOCNO (a
, ai
)
1999 r
= ALLOCNO_LIVE_RANGES (a
);
2002 ALLOCNO_MAX (a
) = r
->finish
;
2003 for (; r
->next
!= NULL
; r
= r
->next
)
2005 ALLOCNO_MIN (a
) = r
->start
;
2007 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2008 for (a
= ira_regno_allocno_map
[i
];
2010 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2012 if (ALLOCNO_MAX (a
) < 0)
2014 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2015 /* Accumulation of range info. */
2016 if (ALLOCNO_CAP (a
) != NULL
)
2018 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
2020 if (ALLOCNO_MAX (cap
) < ALLOCNO_MAX (a
))
2021 ALLOCNO_MAX (cap
) = ALLOCNO_MAX (a
);
2022 if (ALLOCNO_MIN (cap
) > ALLOCNO_MIN (a
))
2023 ALLOCNO_MIN (cap
) = ALLOCNO_MIN (a
);
2027 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
2029 parent_a
= parent
->regno_allocno_map
[i
];
2030 if (ALLOCNO_MAX (parent_a
) < ALLOCNO_MAX (a
))
2031 ALLOCNO_MAX (parent_a
) = ALLOCNO_MAX (a
);
2032 if (ALLOCNO_MIN (parent_a
) > ALLOCNO_MIN (a
))
2033 ALLOCNO_MIN (parent_a
) = ALLOCNO_MIN (a
);
2035 #ifdef ENABLE_IRA_CHECKING
2036 FOR_EACH_ALLOCNO (a
, ai
)
2038 if ((0 <= ALLOCNO_MIN (a
) && ALLOCNO_MIN (a
) <= ira_max_point
)
2039 && (0 <= ALLOCNO_MAX (a
) && ALLOCNO_MAX (a
) <= ira_max_point
))
2046 /* Sort allocnos according to their live ranges. Allocnos with
2047 smaller cover class are put first. Allocnos with the same cove
2048 class are ordered according their start (min). Allocnos with the
2049 same start are ordered according their finish (max). */
2051 allocno_range_compare_func (const void *v1p
, const void *v2p
)
2054 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2055 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2057 if ((diff
= ALLOCNO_COVER_CLASS (a1
) - ALLOCNO_COVER_CLASS (a2
)) != 0)
2059 if ((diff
= ALLOCNO_MIN (a1
) - ALLOCNO_MIN (a2
)) != 0)
2061 if ((diff
= ALLOCNO_MAX (a1
) - ALLOCNO_MAX (a2
)) != 0)
2063 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2066 /* Sort ira_conflict_id_allocno_map and set up conflict id of
2069 sort_conflict_id_allocno_map (void)
2073 ira_allocno_iterator ai
;
2076 FOR_EACH_ALLOCNO (a
, ai
)
2077 ira_conflict_id_allocno_map
[num
++] = a
;
2078 qsort (ira_conflict_id_allocno_map
, num
, sizeof (ira_allocno_t
),
2079 allocno_range_compare_func
);
2080 for (i
= 0; i
< num
; i
++)
2081 if ((a
= ira_conflict_id_allocno_map
[i
]) != NULL
)
2082 ALLOCNO_CONFLICT_ID (a
) = i
;
2083 for (i
= num
; i
< ira_allocnos_num
; i
++)
2084 ira_conflict_id_allocno_map
[i
] = NULL
;
2087 /* Set up minimal and maximal conflict ids of allocnos with which
2088 given allocno can conflict. */
2090 setup_min_max_conflict_allocno_ids (void)
2092 enum reg_class cover_class
;
2093 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
2094 int *live_range_min
, *last_lived
;
2097 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_allocnos_num
);
2099 first_not_finished
= -1;
2100 for (i
= 0; i
< ira_allocnos_num
; i
++)
2102 a
= ira_conflict_id_allocno_map
[i
];
2105 if (cover_class
!= ALLOCNO_COVER_CLASS (a
))
2107 cover_class
= ALLOCNO_COVER_CLASS (a
);
2109 first_not_finished
= i
;
2113 start
= ALLOCNO_MIN (a
);
2114 /* If we skip an allocno, the allocno with smaller ids will
2115 be also skipped because of the secondary sorting the
2116 range finishes (see function
2117 allocno_range_compare_func). */
2118 while (first_not_finished
< i
2119 && start
> ALLOCNO_MAX (ira_conflict_id_allocno_map
2120 [first_not_finished
]))
2121 first_not_finished
++;
2122 min
= first_not_finished
;
2125 /* We could increase min further in this case but it is good
2128 live_range_min
[i
] = ALLOCNO_MIN (a
);
2129 ALLOCNO_MIN (a
) = min
;
2131 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
2133 filled_area_start
= -1;
2134 for (i
= ira_allocnos_num
- 1; i
>= 0; i
--)
2136 a
= ira_conflict_id_allocno_map
[i
];
2139 if (cover_class
!= ALLOCNO_COVER_CLASS (a
))
2141 cover_class
= ALLOCNO_COVER_CLASS (a
);
2142 for (j
= 0; j
< ira_max_point
; j
++)
2144 filled_area_start
= ira_max_point
;
2146 min
= live_range_min
[i
];
2147 finish
= ALLOCNO_MAX (a
);
2148 max
= last_lived
[finish
];
2150 /* We could decrease max further in this case but it is good
2152 max
= ALLOCNO_CONFLICT_ID (a
) - 1;
2153 ALLOCNO_MAX (a
) = max
;
2154 /* In filling, we can go further A range finish to recognize
2155 intersection quickly because if the finish of subsequently
2156 processed allocno (it has smaller conflict id) range is
2157 further A range finish than they are definitely intersected
2158 (the reason for this is the allocnos with bigger conflict id
2159 have their range starts not smaller than allocnos with
2161 for (j
= min
; j
< filled_area_start
; j
++)
2163 filled_area_start
= min
;
2165 ira_free (last_lived
);
2166 ira_free (live_range_min
);
2175 ira_allocno_iterator ai
;
2176 ira_loop_tree_node_t loop_tree_node
;
2178 FOR_EACH_ALLOCNO (a
, ai
)
2180 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2182 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2183 create_cap_allocno (a
);
2184 else if (ALLOCNO_CAP (a
) == NULL
)
2186 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2187 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2188 create_cap_allocno (a
);
2195 /* The page contains code transforming more one region internal
2196 representation (IR) to one region IR which is necessary for reload.
2197 This transformation is called IR flattening. We might just rebuild
2198 the IR for one region but we don't do it because it takes a lot of
2201 /* Map: regno -> allocnos which will finally represent the regno for
2202 IR with one region. */
2203 static ira_allocno_t
*regno_top_level_allocno_map
;
2205 /* Process all allocnos originated from pseudo REGNO and copy live
2206 ranges, hard reg conflicts, and allocno stack reg attributes from
2207 low level allocnos to final allocnos which are destinations of
2208 removed stores at a loop exit. Return true if we copied live
2211 copy_info_to_removed_store_destinations (int regno
)
2213 ira_allocno_t a
, parent_a
;
2214 ira_loop_tree_node_t parent
;
2215 allocno_live_range_t r
;
2219 for (a
= ira_regno_allocno_map
[regno
];
2221 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2223 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))])
2224 /* This allocno will be removed. */
2226 /* Caps will be removed. */
2227 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2228 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
2230 parent
= parent
->parent
)
2231 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2232 || (parent_a
== regno_top_level_allocno_map
[REGNO (ALLOCNO_REG
2234 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)))
2236 if (parent
== NULL
|| parent_a
== NULL
)
2238 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2242 " Coping ranges of a%dr%d to a%dr%d: ",
2243 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2244 ALLOCNO_NUM (parent_a
), REGNO (ALLOCNO_REG (parent_a
)));
2245 ira_print_live_range_list (ira_dump_file
,
2246 ALLOCNO_LIVE_RANGES (a
));
2248 r
= ira_copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES (a
));
2249 change_allocno_in_range_list (r
, parent_a
);
2250 ALLOCNO_LIVE_RANGES (parent_a
)
2251 = ira_merge_allocno_live_ranges (r
, ALLOCNO_LIVE_RANGES (parent_a
));
2252 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2253 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2255 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2256 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
2258 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
2259 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2260 += ALLOCNO_CALLS_CROSSED_NUM (a
);
2261 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2262 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2268 /* Flatten the IR. In other words, this function transforms IR as if
2269 it were built with one region (without loops). We could make it
2270 much simpler by rebuilding IR with one region, but unfortunately it
2271 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
2272 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
2273 IRA_MAX_POINT before emitting insns on the loop borders. */
2275 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
2280 bool new_pseudos_p
, merged_p
, mem_dest_p
;
2282 enum reg_class cover_class
;
2283 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
2285 ira_loop_tree_node_t parent
, node
;
2286 allocno_live_range_t r
;
2287 ira_allocno_iterator ai
;
2288 ira_copy_iterator ci
;
2289 sparseset allocnos_live
;
2291 regno_top_level_allocno_map
2292 = (ira_allocno_t
*) ira_allocate (max_reg_num () * sizeof (ira_allocno_t
));
2293 memset (regno_top_level_allocno_map
, 0,
2294 max_reg_num () * sizeof (ira_allocno_t
));
2295 new_pseudos_p
= merged_p
= false;
2296 FOR_EACH_ALLOCNO (a
, ai
)
2298 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2299 /* Caps are not in the regno allocno maps and they are never
2300 will be transformed into allocnos existing after IR
2303 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
),
2304 ALLOCNO_CONFLICT_HARD_REGS (a
));
2306 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
2309 /* Fix final allocno attributes. */
2310 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2313 for (a
= ira_regno_allocno_map
[i
];
2315 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2317 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2318 if (ALLOCNO_SOMEWHERE_RENAMED_P (a
))
2319 new_pseudos_p
= true;
2320 if (ALLOCNO_CAP (a
) != NULL
2321 || (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
2322 || ((parent_a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)])
2325 ALLOCNO_COPIES (a
) = NULL
;
2326 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2329 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
2331 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) != NULL
)
2333 if (REGNO (ALLOCNO_REG (a
)) == REGNO (ALLOCNO_REG (parent_a
)))
2335 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a
),
2336 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a
));
2338 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2339 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a
) = true;
2341 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2343 fprintf (ira_dump_file
,
2344 " Moving ranges of a%dr%d to a%dr%d: ",
2345 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)),
2346 ALLOCNO_NUM (parent_a
),
2347 REGNO (ALLOCNO_REG (parent_a
)));
2348 ira_print_live_range_list (ira_dump_file
,
2349 ALLOCNO_LIVE_RANGES (a
));
2351 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a
), parent_a
);
2352 ALLOCNO_LIVE_RANGES (parent_a
)
2353 = ira_merge_allocno_live_ranges
2354 (ALLOCNO_LIVE_RANGES (a
), ALLOCNO_LIVE_RANGES (parent_a
));
2356 ALLOCNO_LIVE_RANGES (a
) = NULL
;
2357 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2358 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a
)
2359 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a
));
2362 new_pseudos_p
= true;
2365 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
2366 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
2367 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
2368 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2369 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
2370 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2371 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2372 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
2373 && ALLOCNO_NREFS (parent_a
) >= 0
2374 && ALLOCNO_FREQ (parent_a
) >= 0);
2375 cover_class
= ALLOCNO_COVER_CLASS (parent_a
);
2376 hard_regs_num
= ira_class_hard_regs_num
[cover_class
];
2377 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
2378 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
2379 for (j
= 0; j
< hard_regs_num
; j
++)
2380 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
2381 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
2382 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
2383 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
2384 for (j
= 0; j
< hard_regs_num
; j
++)
2385 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
2386 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
2387 ALLOCNO_COVER_CLASS_COST (parent_a
)
2388 -= ALLOCNO_COVER_CLASS_COST (a
);
2389 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
2390 if (ALLOCNO_CAP (parent_a
) != NULL
2392 = ALLOCNO_LOOP_TREE_NODE (parent_a
)->parent
) == NULL
2393 || (parent_a
= (parent
->regno_allocno_map
2394 [ALLOCNO_REGNO (parent_a
)])) == NULL
)
2397 ALLOCNO_COPIES (a
) = NULL
;
2398 regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))] = a
;
2400 if (mem_dest_p
&& copy_info_to_removed_store_destinations (i
))
2403 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
2404 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
2405 ira_rebuild_start_finish_chains ();
2408 /* Rebuild conflicts. */
2409 FOR_EACH_ALLOCNO (a
, ai
)
2411 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2412 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2414 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2415 ira_assert (r
->allocno
== a
);
2416 clear_allocno_conflicts (a
);
2418 allocnos_live
= sparseset_alloc (ira_allocnos_num
);
2419 for (i
= 0; i
< ira_max_point
; i
++)
2421 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
2424 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2425 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2427 num
= ALLOCNO_NUM (a
);
2428 cover_class
= ALLOCNO_COVER_CLASS (a
);
2429 sparseset_set_bit (allocnos_live
, num
);
2430 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live
, n
)
2432 ira_allocno_t live_a
= ira_allocnos
[n
];
2434 if (cover_class
== ALLOCNO_COVER_CLASS (live_a
)
2435 /* Don't set up conflict for the allocno with itself. */
2437 ira_add_allocno_conflict (a
, live_a
);
2441 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
2442 sparseset_clear_bit (allocnos_live
, ALLOCNO_NUM (r
->allocno
));
2444 sparseset_free (allocnos_live
);
2445 compress_conflict_vecs ();
2447 /* Mark some copies for removing and change allocnos in the rest
2449 FOR_EACH_COPY (cp
, ci
)
2451 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
2452 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
2454 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2456 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2457 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
2458 ALLOCNO_NUM (cp
->first
), REGNO (ALLOCNO_REG (cp
->first
)),
2459 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
2460 ALLOCNO_NUM (cp
->second
), REGNO (ALLOCNO_REG (cp
->second
)));
2461 cp
->loop_tree_node
= NULL
;
2464 first
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->first
))];
2465 second
= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (cp
->second
))];
2466 node
= cp
->loop_tree_node
;
2468 keep_p
= true; /* It copy generated in ira-emit.c. */
2471 /* Check that the copy was not propagated from level on
2472 which we will have different pseudos. */
2473 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
2474 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
2475 keep_p
= ((REGNO (ALLOCNO_REG (first
))
2476 == REGNO (ALLOCNO_REG (node_first
)))
2477 && (REGNO (ALLOCNO_REG (second
))
2478 == REGNO (ALLOCNO_REG (node_second
))));
2482 cp
->loop_tree_node
= ira_loop_tree_root
;
2484 cp
->second
= second
;
2488 cp
->loop_tree_node
= NULL
;
2489 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2490 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
2491 cp
->num
, ALLOCNO_NUM (cp
->first
),
2492 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
2493 REGNO (ALLOCNO_REG (cp
->second
)));
2496 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2497 FOR_EACH_ALLOCNO (a
, ai
)
2499 if (a
!= regno_top_level_allocno_map
[REGNO (ALLOCNO_REG (a
))]
2500 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
2502 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2503 fprintf (ira_dump_file
, " Remove a%dr%d\n",
2504 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
2508 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2509 ALLOCNO_REGNO (a
) = REGNO (ALLOCNO_REG (a
));
2510 ALLOCNO_CAP (a
) = NULL
;
2511 /* Restore updated costs for assignments from reload. */
2512 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
2513 ALLOCNO_UPDATED_COVER_CLASS_COST (a
) = ALLOCNO_COVER_CLASS_COST (a
);
2514 if (! ALLOCNO_ASSIGNED_P (a
))
2515 ira_free_allocno_updated_costs (a
);
2516 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
2517 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
2519 /* Remove unnecessary copies. */
2520 FOR_EACH_COPY (cp
, ci
)
2522 if (cp
->loop_tree_node
== NULL
)
2524 ira_copies
[cp
->num
] = NULL
;
2529 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
2530 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
2531 ira_add_allocno_copy_to_list (cp
);
2532 ira_swap_allocno_copy_ends_if_necessary (cp
);
2534 rebuild_regno_allocno_maps ();
2535 if (ira_max_point
!= ira_max_point_before_emit
)
2536 ira_compress_allocno_live_ranges ();
2537 ira_free (regno_top_level_allocno_map
);
2542 #ifdef ENABLE_IRA_CHECKING
2543 /* Check creation of all allocnos. Allocnos on lower levels should
2544 have allocnos or caps on all upper levels. */
2546 check_allocno_creation (void)
2549 ira_allocno_iterator ai
;
2550 ira_loop_tree_node_t loop_tree_node
;
2552 FOR_EACH_ALLOCNO (a
, ai
)
2554 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2555 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
2557 if (loop_tree_node
== ira_loop_tree_root
)
2559 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2560 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2561 else if (ALLOCNO_CAP (a
) == NULL
)
2562 ira_assert (loop_tree_node
->parent
2563 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
2564 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
2570 /* Create a internal representation (IR) for IRA (allocnos, copies,
2571 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2572 the loops (except the root which corresponds the all function) and
2573 correspondingly allocnos for the loops will be not created. Such
2574 parameter value is used for Chaitin-Briggs coloring. The function
2575 returns TRUE if we generate loop structure (besides nodes
2576 representing all function and the basic blocks) for regional
2577 allocation. A true return means that we really need to flatten IR
2578 before the reload. */
2580 ira_build (bool loops_p
)
2584 initiate_cost_vectors ();
2585 initiate_allocnos ();
2587 create_loop_tree_nodes (loops_p
);
2591 ira_create_allocno_live_ranges ();
2592 remove_unnecessary_regions ();
2593 ira_compress_allocno_live_ranges ();
2594 update_bad_spill_attribute ();
2595 loops_p
= more_one_region_p ();
2598 propagate_allocno_info ();
2601 ira_tune_allocno_costs_and_cover_classes ();
2602 #ifdef ENABLE_IRA_CHECKING
2603 check_allocno_creation ();
2605 setup_min_max_allocno_live_range_point ();
2606 sort_conflict_id_allocno_map ();
2607 setup_min_max_conflict_allocno_ids ();
2608 ira_build_conflicts ();
2609 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
2610 print_copies (ira_dump_file
);
2611 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
2615 allocno_live_range_t r
;
2616 ira_allocno_iterator ai
;
2619 FOR_EACH_ALLOCNO (a
, ai
)
2620 n
+= ALLOCNO_CONFLICT_ALLOCNOS_NUM (a
);
2622 FOR_EACH_ALLOCNO (a
, ai
)
2623 for (r
= ALLOCNO_LIVE_RANGES (a
); r
!= NULL
; r
= r
->next
)
2625 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
2626 VEC_length (loop_p
, ira_loops
.larray
), n_basic_blocks
,
2628 fprintf (ira_dump_file
,
2629 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2630 ira_allocnos_num
, ira_copies_num
, n
, nr
);
2635 /* Release the data created by function ira_build. */
2639 finish_loop_tree_nodes ();
2642 finish_cost_vectors ();
2643 ira_finish_allocno_live_ranges ();