1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2014 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "insn-config.h"
34 #include "diagnostic-core.h"
38 #include "sparseset.h"
40 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
42 static ira_copy_t
find_allocno_copy (ira_allocno_t
, ira_allocno_t
, rtx_insn
*,
43 ira_loop_tree_node_t
);
45 /* The root of the loop tree corresponding to the all function. */
46 ira_loop_tree_node_t ira_loop_tree_root
;
48 /* Height of the loop tree. */
49 int ira_loop_tree_height
;
51 /* All nodes representing basic blocks are referred through the
52 following array. We can not use basic block member `aux' for this
53 because it is used for insertion of insns on edges. */
54 ira_loop_tree_node_t ira_bb_nodes
;
56 /* All nodes representing loops are referred through the following
58 ira_loop_tree_node_t ira_loop_nodes
;
60 /* And size of the ira_loop_nodes array. */
61 unsigned int ira_loop_nodes_count
;
63 /* Map regno -> allocnos with given regno (see comments for
64 allocno member `next_regno_allocno'). */
65 ira_allocno_t
*ira_regno_allocno_map
;
67 /* Array of references to all allocnos. The order number of the
68 allocno corresponds to the index in the array. Removed allocnos
69 have NULL element value. */
70 ira_allocno_t
*ira_allocnos
;
72 /* Sizes of the previous array. */
75 /* Count of conflict record structures we've created, used when creating
79 /* Map a conflict id to its conflict record. */
80 ira_object_t
*ira_object_id_map
;
82 /* Array of references to all allocno preferences. The order number
83 of the preference corresponds to the index in the array. */
84 ira_pref_t
*ira_prefs
;
86 /* Size of the previous array. */
89 /* Array of references to all copies. The order number of the copy
90 corresponds to the index in the array. Removed copies have NULL
92 ira_copy_t
*ira_copies
;
94 /* Size of the previous array. */
99 /* LAST_BASIC_BLOCK before generating additional insns because of live
100 range splitting. Emitting insns on a critical edge creates a new
102 static int last_basic_block_before_change
;
104 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
105 the member loop_num. */
107 init_loop_tree_node (struct ira_loop_tree_node
*node
, int loop_num
)
109 int max_regno
= max_reg_num ();
111 node
->regno_allocno_map
112 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
) * max_regno
);
113 memset (node
->regno_allocno_map
, 0, sizeof (ira_allocno_t
) * max_regno
);
114 memset (node
->reg_pressure
, 0, sizeof (node
->reg_pressure
));
115 node
->all_allocnos
= ira_allocate_bitmap ();
116 node
->modified_regnos
= ira_allocate_bitmap ();
117 node
->border_allocnos
= ira_allocate_bitmap ();
118 node
->local_copies
= ira_allocate_bitmap ();
119 node
->loop_num
= loop_num
;
120 node
->children
= NULL
;
121 node
->subloops
= NULL
;
125 /* The following function allocates the loop tree nodes. If
126 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
127 the root which corresponds the all function) will be not allocated
128 but nodes will still be allocated for basic blocks. */
130 create_loop_tree_nodes (void)
140 = ((struct ira_loop_tree_node
*)
141 ira_allocate (sizeof (struct ira_loop_tree_node
)
142 * last_basic_block_for_fn (cfun
)));
143 last_basic_block_before_change
= last_basic_block_for_fn (cfun
);
144 for (i
= 0; i
< (unsigned int) last_basic_block_for_fn (cfun
); i
++)
146 ira_bb_nodes
[i
].regno_allocno_map
= NULL
;
147 memset (ira_bb_nodes
[i
].reg_pressure
, 0,
148 sizeof (ira_bb_nodes
[i
].reg_pressure
));
149 ira_bb_nodes
[i
].all_allocnos
= NULL
;
150 ira_bb_nodes
[i
].modified_regnos
= NULL
;
151 ira_bb_nodes
[i
].border_allocnos
= NULL
;
152 ira_bb_nodes
[i
].local_copies
= NULL
;
154 if (current_loops
== NULL
)
156 ira_loop_nodes_count
= 1;
157 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
158 ira_allocate (sizeof (struct ira_loop_tree_node
)));
159 init_loop_tree_node (ira_loop_nodes
, 0);
162 ira_loop_nodes_count
= number_of_loops (cfun
);
163 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
164 ira_allocate (sizeof (struct ira_loop_tree_node
)
165 * ira_loop_nodes_count
));
166 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
168 if (loop_outer (loop
) != NULL
)
170 ira_loop_nodes
[i
].regno_allocno_map
= NULL
;
172 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
173 if (e
->src
!= loop
->latch
174 && (e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
181 edges
= get_loop_exit_edges (loop
);
182 FOR_EACH_VEC_ELT (edges
, j
, e
)
183 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
192 init_loop_tree_node (&ira_loop_nodes
[i
], loop
->num
);
196 /* The function returns TRUE if there are more one allocation
199 more_one_region_p (void)
204 if (current_loops
!= NULL
)
205 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
206 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
207 && ira_loop_tree_root
!= &ira_loop_nodes
[i
])
212 /* Free the loop tree node of a loop. */
214 finish_loop_tree_node (ira_loop_tree_node_t loop
)
216 if (loop
->regno_allocno_map
!= NULL
)
218 ira_assert (loop
->bb
== NULL
);
219 ira_free_bitmap (loop
->local_copies
);
220 ira_free_bitmap (loop
->border_allocnos
);
221 ira_free_bitmap (loop
->modified_regnos
);
222 ira_free_bitmap (loop
->all_allocnos
);
223 ira_free (loop
->regno_allocno_map
);
224 loop
->regno_allocno_map
= NULL
;
228 /* Free the loop tree nodes. */
230 finish_loop_tree_nodes (void)
234 for (i
= 0; i
< ira_loop_nodes_count
; i
++)
235 finish_loop_tree_node (&ira_loop_nodes
[i
]);
236 ira_free (ira_loop_nodes
);
237 for (i
= 0; i
< (unsigned int) last_basic_block_before_change
; i
++)
239 if (ira_bb_nodes
[i
].local_copies
!= NULL
)
240 ira_free_bitmap (ira_bb_nodes
[i
].local_copies
);
241 if (ira_bb_nodes
[i
].border_allocnos
!= NULL
)
242 ira_free_bitmap (ira_bb_nodes
[i
].border_allocnos
);
243 if (ira_bb_nodes
[i
].modified_regnos
!= NULL
)
244 ira_free_bitmap (ira_bb_nodes
[i
].modified_regnos
);
245 if (ira_bb_nodes
[i
].all_allocnos
!= NULL
)
246 ira_free_bitmap (ira_bb_nodes
[i
].all_allocnos
);
247 if (ira_bb_nodes
[i
].regno_allocno_map
!= NULL
)
248 ira_free (ira_bb_nodes
[i
].regno_allocno_map
);
250 ira_free (ira_bb_nodes
);
255 /* The following recursive function adds LOOP to the loop tree
256 hierarchy. LOOP is added only once. If LOOP is NULL we adding
257 loop designating the whole function when CFG loops are not
260 add_loop_to_tree (struct loop
*loop
)
264 ira_loop_tree_node_t loop_node
, parent_node
;
266 /* We can not use loop node access macros here because of potential
267 checking and because the nodes are not initialized enough
269 if (loop
!= NULL
&& loop_outer (loop
) != NULL
)
270 add_loop_to_tree (loop_outer (loop
));
271 loop_num
= loop
!= NULL
? loop
->num
: 0;
272 if (ira_loop_nodes
[loop_num
].regno_allocno_map
!= NULL
273 && ira_loop_nodes
[loop_num
].children
== NULL
)
275 /* We have not added loop node to the tree yet. */
276 loop_node
= &ira_loop_nodes
[loop_num
];
277 loop_node
->loop
= loop
;
278 loop_node
->bb
= NULL
;
283 for (parent
= loop_outer (loop
);
285 parent
= loop_outer (parent
))
286 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
291 loop_node
->next
= NULL
;
292 loop_node
->subloop_next
= NULL
;
293 loop_node
->parent
= NULL
;
297 parent_node
= &ira_loop_nodes
[parent
->num
];
298 loop_node
->next
= parent_node
->children
;
299 parent_node
->children
= loop_node
;
300 loop_node
->subloop_next
= parent_node
->subloops
;
301 parent_node
->subloops
= loop_node
;
302 loop_node
->parent
= parent_node
;
307 /* The following recursive function sets up levels of nodes of the
308 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
309 The function returns maximal value of level in the tree + 1. */
311 setup_loop_tree_level (ira_loop_tree_node_t loop_node
, int level
)
313 int height
, max_height
;
314 ira_loop_tree_node_t subloop_node
;
316 ira_assert (loop_node
->bb
== NULL
);
317 loop_node
->level
= level
;
318 max_height
= level
+ 1;
319 for (subloop_node
= loop_node
->subloops
;
320 subloop_node
!= NULL
;
321 subloop_node
= subloop_node
->subloop_next
)
323 ira_assert (subloop_node
->bb
== NULL
);
324 height
= setup_loop_tree_level (subloop_node
, level
+ 1);
325 if (height
> max_height
)
331 /* Create the loop tree. The algorithm is designed to provide correct
332 order of loops (they are ordered by their last loop BB) and basic
333 blocks in the chain formed by member next. */
335 form_loop_tree (void)
339 ira_loop_tree_node_t bb_node
, loop_node
;
341 /* We can not use loop/bb node access macros because of potential
342 checking and because the nodes are not initialized enough
344 FOR_EACH_BB_FN (bb
, cfun
)
346 bb_node
= &ira_bb_nodes
[bb
->index
];
348 bb_node
->loop
= NULL
;
349 bb_node
->subloops
= NULL
;
350 bb_node
->children
= NULL
;
351 bb_node
->subloop_next
= NULL
;
352 bb_node
->next
= NULL
;
353 if (current_loops
== NULL
)
357 for (parent
= bb
->loop_father
;
359 parent
= loop_outer (parent
))
360 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
363 add_loop_to_tree (parent
);
364 loop_node
= &ira_loop_nodes
[parent
== NULL
? 0 : parent
->num
];
365 bb_node
->next
= loop_node
->children
;
366 bb_node
->parent
= loop_node
;
367 loop_node
->children
= bb_node
;
369 ira_loop_tree_root
= IRA_LOOP_NODE_BY_INDEX (0);
370 ira_loop_tree_height
= setup_loop_tree_level (ira_loop_tree_root
, 0);
371 ira_assert (ira_loop_tree_root
->regno_allocno_map
!= NULL
);
376 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
379 rebuild_regno_allocno_maps (void)
382 int max_regno
, regno
;
384 ira_loop_tree_node_t loop_tree_node
;
386 ira_allocno_iterator ai
;
388 ira_assert (current_loops
!= NULL
);
389 max_regno
= max_reg_num ();
390 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), l
, loop
)
391 if (ira_loop_nodes
[l
].regno_allocno_map
!= NULL
)
393 ira_free (ira_loop_nodes
[l
].regno_allocno_map
);
394 ira_loop_nodes
[l
].regno_allocno_map
395 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
397 memset (ira_loop_nodes
[l
].regno_allocno_map
, 0,
398 sizeof (ira_allocno_t
) * max_regno
);
400 ira_free (ira_regno_allocno_map
);
401 ira_regno_allocno_map
402 = (ira_allocno_t
*) ira_allocate (max_regno
* sizeof (ira_allocno_t
));
403 memset (ira_regno_allocno_map
, 0, max_regno
* sizeof (ira_allocno_t
));
404 FOR_EACH_ALLOCNO (a
, ai
)
406 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
407 /* Caps are not in the regno allocno maps. */
409 regno
= ALLOCNO_REGNO (a
);
410 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
411 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
412 ira_regno_allocno_map
[regno
] = a
;
413 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
414 /* Remember that we can create temporary allocnos to break
415 cycles in register shuffle. */
416 loop_tree_node
->regno_allocno_map
[regno
] = a
;
421 /* Pools for allocnos, allocno live ranges and objects. */
422 static alloc_pool allocno_pool
, live_range_pool
, object_pool
;
424 /* Vec containing references to all created allocnos. It is a
425 container of array allocnos. */
426 static vec
<ira_allocno_t
> allocno_vec
;
428 /* Vec containing references to all created ira_objects. It is a
429 container of ira_object_id_map. */
430 static vec
<ira_object_t
> ira_object_id_map_vec
;
432 /* Initialize data concerning allocnos. */
434 initiate_allocnos (void)
437 = create_alloc_pool ("live ranges",
438 sizeof (struct live_range
), 100);
440 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno
), 100);
442 = create_alloc_pool ("objects", sizeof (struct ira_object
), 100);
443 allocno_vec
.create (max_reg_num () * 2);
445 ira_allocnos_num
= 0;
447 ira_object_id_map_vec
.create (max_reg_num () * 2);
448 ira_object_id_map
= NULL
;
449 ira_regno_allocno_map
450 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
451 * sizeof (ira_allocno_t
));
452 memset (ira_regno_allocno_map
, 0, max_reg_num () * sizeof (ira_allocno_t
));
455 /* Create and return an object corresponding to a new allocno A. */
457 ira_create_object (ira_allocno_t a
, int subword
)
459 enum reg_class aclass
= ALLOCNO_CLASS (a
);
460 ira_object_t obj
= (ira_object_t
) pool_alloc (object_pool
);
462 OBJECT_ALLOCNO (obj
) = a
;
463 OBJECT_SUBWORD (obj
) = subword
;
464 OBJECT_CONFLICT_ID (obj
) = ira_objects_num
;
465 OBJECT_CONFLICT_VEC_P (obj
) = false;
466 OBJECT_CONFLICT_ARRAY (obj
) = NULL
;
467 OBJECT_NUM_CONFLICTS (obj
) = 0;
468 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
469 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
470 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
471 reg_class_contents
[aclass
]);
472 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
473 reg_class_contents
[aclass
]);
474 OBJECT_MIN (obj
) = INT_MAX
;
475 OBJECT_MAX (obj
) = -1;
476 OBJECT_LIVE_RANGES (obj
) = NULL
;
478 ira_object_id_map_vec
.safe_push (obj
);
480 = ira_object_id_map_vec
.address ();
481 ira_objects_num
= ira_object_id_map_vec
.length ();
486 /* Create and return the allocno corresponding to REGNO in
487 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
488 same regno if CAP_P is FALSE. */
490 ira_create_allocno (int regno
, bool cap_p
,
491 ira_loop_tree_node_t loop_tree_node
)
495 a
= (ira_allocno_t
) pool_alloc (allocno_pool
);
496 ALLOCNO_REGNO (a
) = regno
;
497 ALLOCNO_LOOP_TREE_NODE (a
) = loop_tree_node
;
500 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
501 ira_regno_allocno_map
[regno
] = a
;
502 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
503 /* Remember that we can create temporary allocnos to break
504 cycles in register shuffle on region borders (see
506 loop_tree_node
->regno_allocno_map
[regno
] = a
;
508 ALLOCNO_CAP (a
) = NULL
;
509 ALLOCNO_CAP_MEMBER (a
) = NULL
;
510 ALLOCNO_NUM (a
) = ira_allocnos_num
;
511 bitmap_set_bit (loop_tree_node
->all_allocnos
, ALLOCNO_NUM (a
));
512 ALLOCNO_NREFS (a
) = 0;
513 ALLOCNO_FREQ (a
) = 0;
514 ALLOCNO_HARD_REGNO (a
) = -1;
515 ALLOCNO_CALL_FREQ (a
) = 0;
516 ALLOCNO_CALLS_CROSSED_NUM (a
) = 0;
517 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
) = 0;
518 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
520 ALLOCNO_NO_STACK_REG_P (a
) = false;
521 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = false;
523 ALLOCNO_DONT_REASSIGN_P (a
) = false;
524 ALLOCNO_BAD_SPILL_P (a
) = false;
525 ALLOCNO_ASSIGNED_P (a
) = false;
526 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
527 ALLOCNO_WMODE (a
) = ALLOCNO_MODE (a
);
528 ALLOCNO_PREFS (a
) = NULL
;
529 ALLOCNO_COPIES (a
) = NULL
;
530 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
531 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
532 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
533 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
534 ALLOCNO_CLASS (a
) = NO_REGS
;
535 ALLOCNO_UPDATED_CLASS_COST (a
) = 0;
536 ALLOCNO_CLASS_COST (a
) = 0;
537 ALLOCNO_MEMORY_COST (a
) = 0;
538 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
539 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
540 ALLOCNO_NUM_OBJECTS (a
) = 0;
542 ALLOCNO_ADD_DATA (a
) = NULL
;
543 allocno_vec
.safe_push (a
);
544 ira_allocnos
= allocno_vec
.address ();
545 ira_allocnos_num
= allocno_vec
.length ();
550 /* Set up register class for A and update its conflict hard
553 ira_set_allocno_class (ira_allocno_t a
, enum reg_class aclass
)
555 ira_allocno_object_iterator oi
;
558 ALLOCNO_CLASS (a
) = aclass
;
559 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
561 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
562 reg_class_contents
[aclass
]);
563 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
564 reg_class_contents
[aclass
]);
568 /* Determine the number of objects we should associate with allocno A
569 and allocate them. */
571 ira_create_allocno_objects (ira_allocno_t a
)
573 enum machine_mode mode
= ALLOCNO_MODE (a
);
574 enum reg_class aclass
= ALLOCNO_CLASS (a
);
575 int n
= ira_reg_class_max_nregs
[aclass
][mode
];
578 if (GET_MODE_SIZE (mode
) != 2 * UNITS_PER_WORD
|| n
!= 2)
581 ALLOCNO_NUM_OBJECTS (a
) = n
;
582 for (i
= 0; i
< n
; i
++)
583 ALLOCNO_OBJECT (a
, i
) = ira_create_object (a
, i
);
586 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
587 ALLOCNO_OBJECT structures. This must be called after the allocno
588 classes are known. */
590 create_allocno_objects (void)
593 ira_allocno_iterator ai
;
595 FOR_EACH_ALLOCNO (a
, ai
)
596 ira_create_allocno_objects (a
);
599 /* Merge hard register conflict information for all objects associated with
600 allocno TO into the corresponding objects associated with FROM.
601 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
603 merge_hard_reg_conflicts (ira_allocno_t from
, ira_allocno_t to
,
607 gcc_assert (ALLOCNO_NUM_OBJECTS (to
) == ALLOCNO_NUM_OBJECTS (from
));
608 for (i
= 0; i
< ALLOCNO_NUM_OBJECTS (to
); i
++)
610 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
611 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
614 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj
),
615 OBJECT_CONFLICT_HARD_REGS (from_obj
));
616 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj
),
617 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj
));
620 if (!total_only
&& ALLOCNO_NO_STACK_REG_P (from
))
621 ALLOCNO_NO_STACK_REG_P (to
) = true;
622 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from
))
623 ALLOCNO_TOTAL_NO_STACK_REG_P (to
) = true;
627 /* Update hard register conflict information for all objects associated with
628 A to include the regs in SET. */
630 ior_hard_reg_conflicts (ira_allocno_t a
, HARD_REG_SET
*set
)
632 ira_allocno_object_iterator i
;
635 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, i
)
637 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), *set
);
638 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), *set
);
642 /* Return TRUE if a conflict vector with NUM elements is more
643 profitable than a conflict bit vector for OBJ. */
645 ira_conflict_vector_profitable_p (ira_object_t obj
, int num
)
648 int max
= OBJECT_MAX (obj
);
649 int min
= OBJECT_MIN (obj
);
652 /* We prefer a bit vector in such case because it does not result
656 nw
= (max
- min
+ IRA_INT_BITS
) / IRA_INT_BITS
;
657 return (2 * sizeof (ira_object_t
) * (num
+ 1)
658 < 3 * nw
* sizeof (IRA_INT_TYPE
));
661 /* Allocates and initialize the conflict vector of OBJ for NUM
662 conflicting objects. */
664 ira_allocate_conflict_vec (ira_object_t obj
, int num
)
669 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
670 num
++; /* for NULL end marker */
671 size
= sizeof (ira_object_t
) * num
;
672 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
673 vec
= (ira_object_t
*) OBJECT_CONFLICT_ARRAY (obj
);
675 OBJECT_NUM_CONFLICTS (obj
) = 0;
676 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
677 OBJECT_CONFLICT_VEC_P (obj
) = true;
680 /* Allocate and initialize the conflict bit vector of OBJ. */
682 allocate_conflict_bit_vec (ira_object_t obj
)
686 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
687 size
= ((OBJECT_MAX (obj
) - OBJECT_MIN (obj
) + IRA_INT_BITS
)
688 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
689 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
690 memset (OBJECT_CONFLICT_ARRAY (obj
), 0, size
);
691 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
692 OBJECT_CONFLICT_VEC_P (obj
) = false;
695 /* Allocate and initialize the conflict vector or conflict bit vector
696 of OBJ for NUM conflicting allocnos whatever is more profitable. */
698 ira_allocate_object_conflicts (ira_object_t obj
, int num
)
700 if (ira_conflict_vector_profitable_p (obj
, num
))
701 ira_allocate_conflict_vec (obj
, num
);
703 allocate_conflict_bit_vec (obj
);
706 /* Add OBJ2 to the conflicts of OBJ1. */
708 add_to_conflicts (ira_object_t obj1
, ira_object_t obj2
)
713 if (OBJECT_CONFLICT_VEC_P (obj1
))
715 ira_object_t
*vec
= OBJECT_CONFLICT_VEC (obj1
);
716 int curr_num
= OBJECT_NUM_CONFLICTS (obj1
);
718 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < num
* sizeof (ira_object_t
))
720 ira_object_t
*newvec
;
721 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
722 newvec
= (ira_object_t
*) ira_allocate (size
);
723 memcpy (newvec
, vec
, curr_num
* sizeof (ira_object_t
));
726 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
727 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
731 OBJECT_NUM_CONFLICTS (obj1
)++;
735 int nw
, added_head_nw
, id
;
736 IRA_INT_TYPE
*vec
= OBJECT_CONFLICT_BITVEC (obj1
);
738 id
= OBJECT_CONFLICT_ID (obj2
);
739 if (OBJECT_MIN (obj1
) > id
)
741 /* Expand head of the bit vector. */
742 added_head_nw
= (OBJECT_MIN (obj1
) - id
- 1) / IRA_INT_BITS
+ 1;
743 nw
= (OBJECT_MAX (obj1
) - OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
744 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
745 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) >= size
)
747 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
748 vec
, nw
* sizeof (IRA_INT_TYPE
));
749 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
754 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
755 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
756 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
757 OBJECT_CONFLICT_ARRAY (obj1
), nw
* sizeof (IRA_INT_TYPE
));
758 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
760 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
761 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
762 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
763 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
764 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
766 OBJECT_MIN (obj1
) -= added_head_nw
* IRA_INT_BITS
;
768 else if (OBJECT_MAX (obj1
) < id
)
770 nw
= (id
- OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
771 size
= nw
* sizeof (IRA_INT_TYPE
);
772 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < size
)
774 /* Expand tail of the bit vector. */
775 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
776 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
777 memcpy (vec
, OBJECT_CONFLICT_ARRAY (obj1
), OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
778 memset ((char *) vec
+ OBJECT_CONFLICT_ARRAY_SIZE (obj1
),
779 0, size
- OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
780 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
781 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
782 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
784 OBJECT_MAX (obj1
) = id
;
786 SET_MINMAX_SET_BIT (vec
, id
, OBJECT_MIN (obj1
), OBJECT_MAX (obj1
));
790 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
792 ira_add_conflict (ira_object_t obj1
, ira_object_t obj2
)
794 add_to_conflicts (obj1
, obj2
);
795 add_to_conflicts (obj2
, obj1
);
798 /* Clear all conflicts of OBJ. */
800 clear_conflicts (ira_object_t obj
)
802 if (OBJECT_CONFLICT_VEC_P (obj
))
804 OBJECT_NUM_CONFLICTS (obj
) = 0;
805 OBJECT_CONFLICT_VEC (obj
)[0] = NULL
;
807 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj
) != 0)
811 nw
= (OBJECT_MAX (obj
) - OBJECT_MIN (obj
)) / IRA_INT_BITS
+ 1;
812 memset (OBJECT_CONFLICT_BITVEC (obj
), 0, nw
* sizeof (IRA_INT_TYPE
));
816 /* The array used to find duplications in conflict vectors of
818 static int *conflict_check
;
820 /* The value used to mark allocation presence in conflict vector of
821 the current allocno. */
822 static int curr_conflict_check_tick
;
824 /* Remove duplications in conflict vector of OBJ. */
826 compress_conflict_vec (ira_object_t obj
)
828 ira_object_t
*vec
, conflict_obj
;
831 ira_assert (OBJECT_CONFLICT_VEC_P (obj
));
832 vec
= OBJECT_CONFLICT_VEC (obj
);
833 curr_conflict_check_tick
++;
834 for (i
= j
= 0; (conflict_obj
= vec
[i
]) != NULL
; i
++)
836 int id
= OBJECT_CONFLICT_ID (conflict_obj
);
837 if (conflict_check
[id
] != curr_conflict_check_tick
)
839 conflict_check
[id
] = curr_conflict_check_tick
;
840 vec
[j
++] = conflict_obj
;
843 OBJECT_NUM_CONFLICTS (obj
) = j
;
847 /* Remove duplications in conflict vectors of all allocnos. */
849 compress_conflict_vecs (void)
852 ira_object_iterator oi
;
854 conflict_check
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
855 memset (conflict_check
, 0, sizeof (int) * ira_objects_num
);
856 curr_conflict_check_tick
= 0;
857 FOR_EACH_OBJECT (obj
, oi
)
859 if (OBJECT_CONFLICT_VEC_P (obj
))
860 compress_conflict_vec (obj
);
862 ira_free (conflict_check
);
865 /* This recursive function outputs allocno A and if it is a cap the
866 function outputs its members. */
868 ira_print_expanded_allocno (ira_allocno_t a
)
872 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
873 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
874 fprintf (ira_dump_file
, ",b%d", bb
->index
);
876 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
877 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
879 fprintf (ira_dump_file
, ":");
880 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
882 fprintf (ira_dump_file
, ")");
885 /* Create and return the cap representing allocno A in the
888 create_cap_allocno (ira_allocno_t a
)
891 ira_loop_tree_node_t parent
;
892 enum reg_class aclass
;
894 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
895 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
896 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
897 ALLOCNO_WMODE (cap
) = ALLOCNO_WMODE (a
);
898 aclass
= ALLOCNO_CLASS (a
);
899 ira_set_allocno_class (cap
, aclass
);
900 ira_create_allocno_objects (cap
);
901 ALLOCNO_CAP_MEMBER (cap
) = a
;
902 ALLOCNO_CAP (a
) = cap
;
903 ALLOCNO_CLASS_COST (cap
) = ALLOCNO_CLASS_COST (a
);
904 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
905 ira_allocate_and_copy_costs
906 (&ALLOCNO_HARD_REG_COSTS (cap
), aclass
, ALLOCNO_HARD_REG_COSTS (a
));
907 ira_allocate_and_copy_costs
908 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), aclass
,
909 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
910 ALLOCNO_BAD_SPILL_P (cap
) = ALLOCNO_BAD_SPILL_P (a
);
911 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
912 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
913 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
915 merge_hard_reg_conflicts (a
, cap
, false);
917 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
918 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
919 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap
),
920 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
921 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
923 fprintf (ira_dump_file
, " Creating cap ");
924 ira_print_expanded_allocno (cap
);
925 fprintf (ira_dump_file
, "\n");
930 /* Create and return a live range for OBJECT with given attributes. */
932 ira_create_live_range (ira_object_t obj
, int start
, int finish
,
937 p
= (live_range_t
) pool_alloc (live_range_pool
);
945 /* Create a new live range for OBJECT and queue it at the head of its
948 ira_add_live_range_to_object (ira_object_t object
, int start
, int finish
)
951 p
= ira_create_live_range (object
, start
, finish
,
952 OBJECT_LIVE_RANGES (object
));
953 OBJECT_LIVE_RANGES (object
) = p
;
956 /* Copy allocno live range R and return the result. */
958 copy_live_range (live_range_t r
)
962 p
= (live_range_t
) pool_alloc (live_range_pool
);
967 /* Copy allocno live range list given by its head R and return the
970 ira_copy_live_range_list (live_range_t r
)
972 live_range_t p
, first
, last
;
976 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
978 p
= copy_live_range (r
);
988 /* Merge ranges R1 and R2 and returns the result. The function
989 maintains the order of ranges and tries to minimize number of the
992 ira_merge_live_ranges (live_range_t r1
, live_range_t r2
)
994 live_range_t first
, last
, temp
;
1000 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
1002 if (r1
->start
< r2
->start
)
1008 if (r1
->start
<= r2
->finish
+ 1)
1010 /* Intersected ranges: merge r1 and r2 into r1. */
1011 r1
->start
= r2
->start
;
1012 if (r1
->finish
< r2
->finish
)
1013 r1
->finish
= r2
->finish
;
1016 ira_finish_live_range (temp
);
1019 /* To try to merge with subsequent ranges in r1. */
1026 /* Add r1 to the result. */
1037 /* To try to merge with subsequent ranges in r2. */
1049 ira_assert (r1
->next
== NULL
);
1051 else if (r2
!= NULL
)
1057 ira_assert (r2
->next
== NULL
);
1061 ira_assert (last
->next
== NULL
);
1066 /* Return TRUE if live ranges R1 and R2 intersect. */
1068 ira_live_ranges_intersect_p (live_range_t r1
, live_range_t r2
)
1070 /* Remember the live ranges are always kept ordered. */
1071 while (r1
!= NULL
&& r2
!= NULL
)
1073 if (r1
->start
> r2
->finish
)
1075 else if (r2
->start
> r1
->finish
)
1083 /* Free allocno live range R. */
1085 ira_finish_live_range (live_range_t r
)
1087 pool_free (live_range_pool
, r
);
1090 /* Free list of allocno live ranges starting with R. */
1092 ira_finish_live_range_list (live_range_t r
)
1094 live_range_t next_r
;
1096 for (; r
!= NULL
; r
= next_r
)
1099 ira_finish_live_range (r
);
1103 /* Free updated register costs of allocno A. */
1105 ira_free_allocno_updated_costs (ira_allocno_t a
)
1107 enum reg_class aclass
;
1109 aclass
= ALLOCNO_CLASS (a
);
1110 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
1111 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
);
1112 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
1113 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1114 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1116 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1119 /* Free and nullify all cost vectors allocated earlier for allocno
1122 ira_free_allocno_costs (ira_allocno_t a
)
1124 enum reg_class aclass
= ALLOCNO_CLASS (a
);
1126 ira_allocno_object_iterator oi
;
1128 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
1130 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj
));
1131 ira_object_id_map
[OBJECT_CONFLICT_ID (obj
)] = NULL
;
1132 if (OBJECT_CONFLICT_ARRAY (obj
) != NULL
)
1133 ira_free (OBJECT_CONFLICT_ARRAY (obj
));
1134 pool_free (object_pool
, obj
);
1137 ira_allocnos
[ALLOCNO_NUM (a
)] = NULL
;
1138 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
1139 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a
), aclass
);
1140 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1141 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
), aclass
);
1142 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
1143 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
);
1144 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1145 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1147 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
1148 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1149 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
1150 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1153 /* Free the memory allocated for allocno A. */
1155 finish_allocno (ira_allocno_t a
)
1157 ira_free_allocno_costs (a
);
1158 pool_free (allocno_pool
, a
);
1161 /* Free the memory allocated for all allocnos. */
1163 finish_allocnos (void)
1166 ira_allocno_iterator ai
;
1168 FOR_EACH_ALLOCNO (a
, ai
)
1170 ira_free (ira_regno_allocno_map
);
1171 ira_object_id_map_vec
.release ();
1172 allocno_vec
.release ();
1173 free_alloc_pool (allocno_pool
);
1174 free_alloc_pool (object_pool
);
1175 free_alloc_pool (live_range_pool
);
1180 /* Pools for allocno preferences. */
1181 static alloc_pool pref_pool
;
1183 /* Vec containing references to all created preferences. It is a
1184 container of array ira_prefs. */
1185 static vec
<ira_pref_t
> pref_vec
;
1187 /* The function initializes data concerning allocno prefs. */
1189 initiate_prefs (void)
1192 = create_alloc_pool ("prefs", sizeof (struct ira_allocno_pref
), 100);
1193 pref_vec
.create (get_max_uid ());
1198 /* Return pref for A and HARD_REGNO if any. */
1200 find_allocno_pref (ira_allocno_t a
, int hard_regno
)
1204 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1205 if (pref
->allocno
== a
&& pref
->hard_regno
== hard_regno
)
1210 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1212 ira_create_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1216 pref
= (ira_pref_t
) pool_alloc (pref_pool
);
1217 pref
->num
= ira_prefs_num
;
1219 pref
->hard_regno
= hard_regno
;
1221 pref_vec
.safe_push (pref
);
1222 ira_prefs
= pref_vec
.address ();
1223 ira_prefs_num
= pref_vec
.length ();
1227 /* Attach a pref PREF to the corresponding allocno. */
1229 add_allocno_pref_to_list (ira_pref_t pref
)
1231 ira_allocno_t a
= pref
->allocno
;
1233 pref
->next_pref
= ALLOCNO_PREFS (a
);
1234 ALLOCNO_PREFS (a
) = pref
;
1237 /* Create (or update frequency if the pref already exists) the pref of
1238 allocnos A preferring HARD_REGNO with frequency FREQ. */
1240 ira_add_allocno_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1246 if ((pref
= find_allocno_pref (a
, hard_regno
)) != NULL
)
1251 pref
= ira_create_pref (a
, hard_regno
, freq
);
1252 ira_assert (a
!= NULL
);
1253 add_allocno_pref_to_list (pref
);
1256 /* Print info about PREF into file F. */
1258 print_pref (FILE *f
, ira_pref_t pref
)
1260 fprintf (f
, " pref%d:a%d(r%d)<-hr%d@%d\n", pref
->num
,
1261 ALLOCNO_NUM (pref
->allocno
), ALLOCNO_REGNO (pref
->allocno
),
1262 pref
->hard_regno
, pref
->freq
);
1265 /* Print info about PREF into stderr. */
1267 ira_debug_pref (ira_pref_t pref
)
1269 print_pref (stderr
, pref
);
1272 /* Print info about all prefs into file F. */
1274 print_prefs (FILE *f
)
1277 ira_pref_iterator pi
;
1279 FOR_EACH_PREF (pref
, pi
)
1280 print_pref (f
, pref
);
1283 /* Print info about all prefs into stderr. */
1285 ira_debug_prefs (void)
1287 print_prefs (stderr
);
1290 /* Print info about prefs involving allocno A into file F. */
1292 print_allocno_prefs (FILE *f
, ira_allocno_t a
)
1296 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1297 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1298 fprintf (f
, " pref%d:hr%d@%d", pref
->num
, pref
->hard_regno
, pref
->freq
);
1302 /* Print info about prefs involving allocno A into stderr. */
1304 ira_debug_allocno_prefs (ira_allocno_t a
)
1306 print_allocno_prefs (stderr
, a
);
1309 /* The function frees memory allocated for PREF. */
1311 finish_pref (ira_pref_t pref
)
1313 ira_prefs
[pref
->num
] = NULL
;
1314 pool_free (pref_pool
, pref
);
1317 /* Remove PREF from the list of allocno prefs and free memory for
1320 ira_remove_pref (ira_pref_t pref
)
1322 ira_pref_t cpref
, prev
;
1324 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1325 fprintf (ira_dump_file
, " Removing pref%d:hr%d@%d\n",
1326 pref
->num
, pref
->hard_regno
, pref
->freq
);
1327 for (prev
= NULL
, cpref
= ALLOCNO_PREFS (pref
->allocno
);
1329 prev
= cpref
, cpref
= cpref
->next_pref
)
1332 ira_assert (cpref
!= NULL
);
1334 ALLOCNO_PREFS (pref
->allocno
) = pref
->next_pref
;
1336 prev
->next_pref
= pref
->next_pref
;
1340 /* Remove all prefs of allocno A. */
1342 ira_remove_allocno_prefs (ira_allocno_t a
)
1344 ira_pref_t pref
, next_pref
;
1346 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
1348 next_pref
= pref
->next_pref
;
1351 ALLOCNO_PREFS (a
) = NULL
;
1354 /* Free memory allocated for all prefs. */
1359 ira_pref_iterator pi
;
1361 FOR_EACH_PREF (pref
, pi
)
1363 pref_vec
.release ();
1364 free_alloc_pool (pref_pool
);
1369 /* Pools for copies. */
1370 static alloc_pool copy_pool
;
1372 /* Vec containing references to all created copies. It is a
1373 container of array ira_copies. */
1374 static vec
<ira_copy_t
> copy_vec
;
1376 /* The function initializes data concerning allocno copies. */
1378 initiate_copies (void)
1381 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy
), 100);
1382 copy_vec
.create (get_max_uid ());
1387 /* Return copy connecting A1 and A2 and originated from INSN of
1388 LOOP_TREE_NODE if any. */
1390 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx_insn
*insn
,
1391 ira_loop_tree_node_t loop_tree_node
)
1393 ira_copy_t cp
, next_cp
;
1394 ira_allocno_t another_a
;
1396 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
1398 if (cp
->first
== a1
)
1400 next_cp
= cp
->next_first_allocno_copy
;
1401 another_a
= cp
->second
;
1403 else if (cp
->second
== a1
)
1405 next_cp
= cp
->next_second_allocno_copy
;
1406 another_a
= cp
->first
;
1410 if (another_a
== a2
&& cp
->insn
== insn
1411 && cp
->loop_tree_node
== loop_tree_node
)
1417 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1418 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1420 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1421 bool constraint_p
, rtx_insn
*insn
,
1422 ira_loop_tree_node_t loop_tree_node
)
1426 cp
= (ira_copy_t
) pool_alloc (copy_pool
);
1427 cp
->num
= ira_copies_num
;
1429 cp
->second
= second
;
1431 cp
->constraint_p
= constraint_p
;
1433 cp
->loop_tree_node
= loop_tree_node
;
1434 copy_vec
.safe_push (cp
);
1435 ira_copies
= copy_vec
.address ();
1436 ira_copies_num
= copy_vec
.length ();
1440 /* Attach a copy CP to allocnos involved into the copy. */
1442 add_allocno_copy_to_list (ira_copy_t cp
)
1444 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1446 cp
->prev_first_allocno_copy
= NULL
;
1447 cp
->prev_second_allocno_copy
= NULL
;
1448 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
1449 if (cp
->next_first_allocno_copy
!= NULL
)
1451 if (cp
->next_first_allocno_copy
->first
== first
)
1452 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
1454 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1456 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1457 if (cp
->next_second_allocno_copy
!= NULL
)
1459 if (cp
->next_second_allocno_copy
->second
== second
)
1460 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1462 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1464 ALLOCNO_COPIES (first
) = cp
;
1465 ALLOCNO_COPIES (second
) = cp
;
1468 /* Make a copy CP a canonical copy where number of the
1469 first allocno is less than the second one. */
1471 swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1476 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1480 cp
->first
= cp
->second
;
1483 temp_cp
= cp
->prev_first_allocno_copy
;
1484 cp
->prev_first_allocno_copy
= cp
->prev_second_allocno_copy
;
1485 cp
->prev_second_allocno_copy
= temp_cp
;
1487 temp_cp
= cp
->next_first_allocno_copy
;
1488 cp
->next_first_allocno_copy
= cp
->next_second_allocno_copy
;
1489 cp
->next_second_allocno_copy
= temp_cp
;
1492 /* Create (or update frequency if the copy already exists) and return
1493 the copy of allocnos FIRST and SECOND with frequency FREQ
1494 corresponding to move insn INSN (if any) and originated from
1497 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1498 bool constraint_p
, rtx_insn
*insn
,
1499 ira_loop_tree_node_t loop_tree_node
)
1503 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1508 cp
= ira_create_copy (first
, second
, freq
, constraint_p
, insn
,
1510 ira_assert (first
!= NULL
&& second
!= NULL
);
1511 add_allocno_copy_to_list (cp
);
1512 swap_allocno_copy_ends_if_necessary (cp
);
1516 /* Print info about copy CP into file F. */
1518 print_copy (FILE *f
, ira_copy_t cp
)
1520 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp
->num
,
1521 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1522 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
,
1524 ? "move" : cp
->constraint_p
? "constraint" : "shuffle");
1528 debug (ira_allocno_copy
&ref
)
1530 print_copy (stderr
, &ref
);
1534 debug (ira_allocno_copy
*ptr
)
1539 fprintf (stderr
, "<nil>\n");
1542 /* Print info about copy CP into stderr. */
1544 ira_debug_copy (ira_copy_t cp
)
1546 print_copy (stderr
, cp
);
1549 /* Print info about all copies into file F. */
1551 print_copies (FILE *f
)
1554 ira_copy_iterator ci
;
1556 FOR_EACH_COPY (cp
, ci
)
1560 /* Print info about all copies into stderr. */
1562 ira_debug_copies (void)
1564 print_copies (stderr
);
1567 /* Print info about copies involving allocno A into file F. */
1569 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1571 ira_allocno_t another_a
;
1572 ira_copy_t cp
, next_cp
;
1574 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1575 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1579 next_cp
= cp
->next_first_allocno_copy
;
1580 another_a
= cp
->second
;
1582 else if (cp
->second
== a
)
1584 next_cp
= cp
->next_second_allocno_copy
;
1585 another_a
= cp
->first
;
1589 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1590 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1596 debug (ira_allocno
&ref
)
1598 print_allocno_copies (stderr
, &ref
);
1602 debug (ira_allocno
*ptr
)
1607 fprintf (stderr
, "<nil>\n");
1611 /* Print info about copies involving allocno A into stderr. */
1613 ira_debug_allocno_copies (ira_allocno_t a
)
1615 print_allocno_copies (stderr
, a
);
1618 /* The function frees memory allocated for copy CP. */
1620 finish_copy (ira_copy_t cp
)
1622 pool_free (copy_pool
, cp
);
1626 /* Free memory allocated for all copies. */
1628 finish_copies (void)
1631 ira_copy_iterator ci
;
1633 FOR_EACH_COPY (cp
, ci
)
1635 copy_vec
.release ();
1636 free_alloc_pool (copy_pool
);
1641 /* Pools for cost vectors. It is defined only for allocno classes. */
1642 static alloc_pool cost_vector_pool
[N_REG_CLASSES
];
1644 /* The function initiates work with hard register cost vectors. It
1645 creates allocation pool for each allocno class. */
1647 initiate_cost_vectors (void)
1650 enum reg_class aclass
;
1652 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1654 aclass
= ira_allocno_classes
[i
];
1655 cost_vector_pool
[aclass
]
1656 = create_alloc_pool ("cost vectors",
1657 sizeof (int) * ira_class_hard_regs_num
[aclass
],
1662 /* Allocate and return a cost vector VEC for ACLASS. */
1664 ira_allocate_cost_vector (reg_class_t aclass
)
1666 return (int *) pool_alloc (cost_vector_pool
[(int) aclass
]);
1669 /* Free a cost vector VEC for ACLASS. */
1671 ira_free_cost_vector (int *vec
, reg_class_t aclass
)
1673 ira_assert (vec
!= NULL
);
1674 pool_free (cost_vector_pool
[(int) aclass
], vec
);
1677 /* Finish work with hard register cost vectors. Release allocation
1678 pool for each allocno class. */
1680 finish_cost_vectors (void)
1683 enum reg_class aclass
;
1685 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1687 aclass
= ira_allocno_classes
[i
];
1688 free_alloc_pool (cost_vector_pool
[aclass
]);
1694 /* Compute a post-ordering of the reverse control flow of the loop body
1695 designated by the children nodes of LOOP_NODE, whose body nodes in
1696 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1697 of the reverse loop body.
1699 For the post-order of the reverse CFG, we visit the basic blocks in
1700 LOOP_PREORDER array in the reverse order of where they appear.
1701 This is important: We do not just want to compute a post-order of
1702 the reverse CFG, we want to make a best-guess for a visiting order that
1703 minimizes the number of chain elements per allocno live range. If the
1704 blocks would be visited in a different order, we would still compute a
1705 correct post-ordering but it would be less likely that two nodes
1706 connected by an edge in the CFG are neighbours in the topsort. */
1708 static vec
<ira_loop_tree_node_t
>
1709 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED
,
1710 vec
<ira_loop_tree_node_t
> loop_preorder
)
1712 vec
<ira_loop_tree_node_t
> topsort_nodes
= vNULL
;
1713 unsigned int n_loop_preorder
;
1715 n_loop_preorder
= loop_preorder
.length ();
1716 if (n_loop_preorder
!= 0)
1718 ira_loop_tree_node_t subloop_node
;
1720 auto_vec
<ira_loop_tree_node_t
> dfs_stack
;
1722 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1723 the flag to mark blocks we still have to visit to add them to
1724 our post-order. Define an alias to avoid confusion. */
1725 #define BB_TO_VISIT BB_VISITED
1727 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1729 gcc_checking_assert (! (subloop_node
->bb
->flags
& BB_TO_VISIT
));
1730 subloop_node
->bb
->flags
|= BB_TO_VISIT
;
1733 topsort_nodes
.create (n_loop_preorder
);
1734 dfs_stack
.create (n_loop_preorder
);
1736 FOR_EACH_VEC_ELT_REVERSE (loop_preorder
, i
, subloop_node
)
1738 if (! (subloop_node
->bb
->flags
& BB_TO_VISIT
))
1741 subloop_node
->bb
->flags
&= ~BB_TO_VISIT
;
1742 dfs_stack
.quick_push (subloop_node
);
1743 while (! dfs_stack
.is_empty ())
1748 ira_loop_tree_node_t n
= dfs_stack
.last ();
1749 FOR_EACH_EDGE (e
, ei
, n
->bb
->preds
)
1751 ira_loop_tree_node_t pred_node
;
1752 basic_block pred_bb
= e
->src
;
1754 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1757 pred_node
= IRA_BB_NODE_BY_INDEX (pred_bb
->index
);
1759 && (pred_node
->bb
->flags
& BB_TO_VISIT
))
1761 pred_node
->bb
->flags
&= ~BB_TO_VISIT
;
1762 dfs_stack
.quick_push (pred_node
);
1765 if (n
== dfs_stack
.last ())
1768 topsort_nodes
.quick_push (n
);
1776 gcc_assert (topsort_nodes
.length () == n_loop_preorder
);
1777 return topsort_nodes
;
1780 /* The current loop tree node and its regno allocno map. */
1781 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1782 ira_allocno_t
*ira_curr_regno_allocno_map
;
1784 /* This recursive function traverses loop tree with root LOOP_NODE
1785 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1786 correspondingly in preorder and postorder. The function sets up
1787 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1788 basic block nodes of LOOP_NODE is also processed (before its
1791 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1792 the loop are passed in the *reverse* post-order of the *reverse*
1793 CFG. This is only used by ira_create_allocno_live_ranges, which
1794 wants to visit basic blocks in this order to minimize the number
1795 of elements per live range chain.
1796 Note that the loop tree nodes are still visited in the normal,
1797 forward post-order of the loop tree. */
1800 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1801 void (*preorder_func
) (ira_loop_tree_node_t
),
1802 void (*postorder_func
) (ira_loop_tree_node_t
))
1804 ira_loop_tree_node_t subloop_node
;
1806 ira_assert (loop_node
->bb
== NULL
);
1807 ira_curr_loop_tree_node
= loop_node
;
1808 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1810 if (preorder_func
!= NULL
)
1811 (*preorder_func
) (loop_node
);
1815 auto_vec
<ira_loop_tree_node_t
> loop_preorder
;
1818 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1819 is set up such that nodes in the loop body appear in a pre-order
1820 of their place in the CFG. */
1821 for (subloop_node
= loop_node
->children
;
1822 subloop_node
!= NULL
;
1823 subloop_node
= subloop_node
->next
)
1824 if (subloop_node
->bb
!= NULL
)
1825 loop_preorder
.safe_push (subloop_node
);
1827 if (preorder_func
!= NULL
)
1828 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1829 (*preorder_func
) (subloop_node
);
1831 if (postorder_func
!= NULL
)
1833 vec
<ira_loop_tree_node_t
> loop_rev_postorder
=
1834 ira_loop_tree_body_rev_postorder (loop_node
, loop_preorder
);
1835 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder
, i
, subloop_node
)
1836 (*postorder_func
) (subloop_node
);
1837 loop_rev_postorder
.release ();
1841 for (subloop_node
= loop_node
->subloops
;
1842 subloop_node
!= NULL
;
1843 subloop_node
= subloop_node
->subloop_next
)
1845 ira_assert (subloop_node
->bb
== NULL
);
1846 ira_traverse_loop_tree (bb_p
, subloop_node
,
1847 preorder_func
, postorder_func
);
1850 ira_curr_loop_tree_node
= loop_node
;
1851 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1853 if (postorder_func
!= NULL
)
1854 (*postorder_func
) (loop_node
);
1859 /* The basic block currently being processed. */
1860 static basic_block curr_bb
;
1862 /* This recursive function creates allocnos corresponding to
1863 pseudo-registers containing in X. True OUTPUT_P means that X is
1864 an lvalue. PARENT corresponds to the parent expression of X. */
1866 create_insn_allocnos (rtx x
, rtx outer
, bool output_p
)
1870 enum rtx_code code
= GET_CODE (x
);
1876 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1880 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1882 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1883 if (outer
!= NULL
&& GET_CODE (outer
) == SUBREG
)
1885 enum machine_mode wmode
= GET_MODE (outer
);
1886 if (GET_MODE_SIZE (wmode
) > GET_MODE_SIZE (ALLOCNO_WMODE (a
)))
1887 ALLOCNO_WMODE (a
) = wmode
;
1891 ALLOCNO_NREFS (a
)++;
1892 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1894 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1898 else if (code
== SET
)
1900 create_insn_allocnos (SET_DEST (x
), NULL
, true);
1901 create_insn_allocnos (SET_SRC (x
), NULL
, false);
1904 else if (code
== CLOBBER
)
1906 create_insn_allocnos (XEXP (x
, 0), NULL
, true);
1909 else if (code
== MEM
)
1911 create_insn_allocnos (XEXP (x
, 0), NULL
, false);
1914 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1915 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1917 create_insn_allocnos (XEXP (x
, 0), NULL
, true);
1918 create_insn_allocnos (XEXP (x
, 0), NULL
, false);
1922 fmt
= GET_RTX_FORMAT (code
);
1923 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1926 create_insn_allocnos (XEXP (x
, i
), x
, output_p
);
1927 else if (fmt
[i
] == 'E')
1928 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1929 create_insn_allocnos (XVECEXP (x
, i
, j
), x
, output_p
);
1933 /* Create allocnos corresponding to pseudo-registers living in the
1934 basic block represented by the corresponding loop tree node
1937 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1944 curr_bb
= bb
= bb_node
->bb
;
1945 ira_assert (bb
!= NULL
);
1946 FOR_BB_INSNS_REVERSE (bb
, insn
)
1947 if (NONDEBUG_INSN_P (insn
))
1948 create_insn_allocnos (PATTERN (insn
), NULL
, false);
1949 /* It might be a allocno living through from one subloop to
1951 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1952 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1953 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1956 /* Create allocnos corresponding to pseudo-registers living on edge E
1957 (a loop entry or exit). Also mark the allocnos as living on the
1960 create_loop_allocnos (edge e
)
1963 bitmap live_in_regs
, border_allocnos
;
1965 ira_loop_tree_node_t parent
;
1967 live_in_regs
= df_get_live_in (e
->dest
);
1968 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1969 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e
->src
),
1970 FIRST_PSEUDO_REGISTER
, i
, bi
)
1971 if (bitmap_bit_p (live_in_regs
, i
))
1973 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1975 /* The order of creations is important for right
1976 ira_regno_allocno_map. */
1977 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1978 && parent
->regno_allocno_map
[i
] == NULL
)
1979 ira_create_allocno (i
, false, parent
);
1980 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1982 bitmap_set_bit (border_allocnos
,
1983 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1987 /* Create allocnos corresponding to pseudo-registers living in loop
1988 represented by the corresponding loop tree node LOOP_NODE. This
1989 function is called by ira_traverse_loop_tree. */
1991 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1993 if (loop_node
->bb
!= NULL
)
1994 create_bb_allocnos (loop_node
);
1995 else if (loop_node
!= ira_loop_tree_root
)
2002 ira_assert (current_loops
!= NULL
);
2003 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
2004 if (e
->src
!= loop_node
->loop
->latch
)
2005 create_loop_allocnos (e
);
2007 edges
= get_loop_exit_edges (loop_node
->loop
);
2008 FOR_EACH_VEC_ELT (edges
, i
, e
)
2009 create_loop_allocnos (e
);
2014 /* Propagate information about allocnos modified inside the loop given
2015 by its LOOP_TREE_NODE to its parent. */
2017 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
2019 if (loop_tree_node
== ira_loop_tree_root
)
2021 ira_assert (loop_tree_node
->bb
== NULL
);
2022 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
2023 loop_tree_node
->modified_regnos
);
2026 /* Propagate new info about allocno A (see comments about accumulated
2027 info in allocno definition) to the corresponding allocno on upper
2028 loop tree level. So allocnos on upper levels accumulate
2029 information about the corresponding allocnos in nested regions.
2030 The new info means allocno info finally calculated in this
2033 propagate_allocno_info (void)
2036 ira_allocno_t a
, parent_a
;
2037 ira_loop_tree_node_t parent
;
2038 enum reg_class aclass
;
2040 if (flag_ira_region
!= IRA_REGION_ALL
2041 && flag_ira_region
!= IRA_REGION_MIXED
)
2043 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2044 for (a
= ira_regno_allocno_map
[i
];
2046 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2047 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
2048 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
2049 /* There are no caps yet at this point. So use
2050 border_allocnos to find allocnos for the propagation. */
2051 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
2054 if (! ALLOCNO_BAD_SPILL_P (a
))
2055 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
2056 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
2057 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
2058 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
2059 merge_hard_reg_conflicts (a
, parent_a
, true);
2060 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2061 += ALLOCNO_CALLS_CROSSED_NUM (a
);
2062 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
2063 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
2064 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a
),
2065 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
2066 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2067 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2068 aclass
= ALLOCNO_CLASS (a
);
2069 ira_assert (aclass
== ALLOCNO_CLASS (parent_a
));
2070 ira_allocate_and_accumulate_costs
2071 (&ALLOCNO_HARD_REG_COSTS (parent_a
), aclass
,
2072 ALLOCNO_HARD_REG_COSTS (a
));
2073 ira_allocate_and_accumulate_costs
2074 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
2076 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2077 ALLOCNO_CLASS_COST (parent_a
)
2078 += ALLOCNO_CLASS_COST (a
);
2079 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
2083 /* Create allocnos corresponding to pseudo-registers in the current
2084 function. Traverse the loop tree for this. */
2086 create_allocnos (void)
2088 /* We need to process BB first to correctly link allocnos by member
2089 next_regno_allocno. */
2090 ira_traverse_loop_tree (true, ira_loop_tree_root
,
2091 create_loop_tree_node_allocnos
, NULL
);
2093 ira_traverse_loop_tree (false, ira_loop_tree_root
, NULL
,
2094 propagate_modified_regnos
);
2099 /* The page contains function to remove some regions from a separate
2100 register allocation. We remove regions whose separate allocation
2101 will hardly improve the result. As a result we speed up regional
2102 register allocation. */
2104 /* The function changes the object in range list given by R to OBJ. */
2106 change_object_in_range_list (live_range_t r
, ira_object_t obj
)
2108 for (; r
!= NULL
; r
= r
->next
)
2112 /* Move all live ranges associated with allocno FROM to allocno TO. */
2114 move_allocno_live_ranges (ira_allocno_t from
, ira_allocno_t to
)
2117 int n
= ALLOCNO_NUM_OBJECTS (from
);
2119 gcc_assert (n
== ALLOCNO_NUM_OBJECTS (to
));
2121 for (i
= 0; i
< n
; i
++)
2123 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
2124 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
2125 live_range_t lr
= OBJECT_LIVE_RANGES (from_obj
);
2127 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2129 fprintf (ira_dump_file
,
2130 " Moving ranges of a%dr%d to a%dr%d: ",
2131 ALLOCNO_NUM (from
), ALLOCNO_REGNO (from
),
2132 ALLOCNO_NUM (to
), ALLOCNO_REGNO (to
));
2133 ira_print_live_range_list (ira_dump_file
, lr
);
2135 change_object_in_range_list (lr
, to_obj
);
2136 OBJECT_LIVE_RANGES (to_obj
)
2137 = ira_merge_live_ranges (lr
, OBJECT_LIVE_RANGES (to_obj
));
2138 OBJECT_LIVE_RANGES (from_obj
) = NULL
;
2143 copy_allocno_live_ranges (ira_allocno_t from
, ira_allocno_t to
)
2146 int n
= ALLOCNO_NUM_OBJECTS (from
);
2148 gcc_assert (n
== ALLOCNO_NUM_OBJECTS (to
));
2150 for (i
= 0; i
< n
; i
++)
2152 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
2153 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
2154 live_range_t lr
= OBJECT_LIVE_RANGES (from_obj
);
2156 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2158 fprintf (ira_dump_file
, " Copying ranges of a%dr%d to a%dr%d: ",
2159 ALLOCNO_NUM (from
), ALLOCNO_REGNO (from
),
2160 ALLOCNO_NUM (to
), ALLOCNO_REGNO (to
));
2161 ira_print_live_range_list (ira_dump_file
, lr
);
2163 lr
= ira_copy_live_range_list (lr
);
2164 change_object_in_range_list (lr
, to_obj
);
2165 OBJECT_LIVE_RANGES (to_obj
)
2166 = ira_merge_live_ranges (lr
, OBJECT_LIVE_RANGES (to_obj
));
2170 /* Return TRUE if NODE represents a loop with low register
2173 low_pressure_loop_node_p (ira_loop_tree_node_t node
)
2176 enum reg_class pclass
;
2178 if (node
->bb
!= NULL
)
2181 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2183 pclass
= ira_pressure_classes
[i
];
2184 if (node
->reg_pressure
[pclass
] > ira_class_hard_regs_num
[pclass
]
2185 && ira_class_hard_regs_num
[pclass
] > 1)
2192 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2193 form a region from such loop if the target use stack register
2194 because reg-stack.c can not deal with such edges. */
2196 loop_with_complex_edge_p (struct loop
*loop
)
2204 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
2205 if (e
->flags
& EDGE_EH
)
2207 edges
= get_loop_exit_edges (loop
);
2209 FOR_EACH_VEC_ELT (edges
, i
, e
)
2210 if (e
->flags
& EDGE_COMPLEX
)
2220 /* Sort loops for marking them for removal. We put already marked
2221 loops first, then less frequent loops next, and then outer loops
2224 loop_compare_func (const void *v1p
, const void *v2p
)
2227 ira_loop_tree_node_t l1
= *(const ira_loop_tree_node_t
*) v1p
;
2228 ira_loop_tree_node_t l2
= *(const ira_loop_tree_node_t
*) v2p
;
2230 ira_assert (l1
->parent
!= NULL
&& l2
->parent
!= NULL
);
2231 if (l1
->to_remove_p
&& ! l2
->to_remove_p
)
2233 if (! l1
->to_remove_p
&& l2
->to_remove_p
)
2235 if ((diff
= l1
->loop
->header
->frequency
- l2
->loop
->header
->frequency
) != 0)
2237 if ((diff
= (int) loop_depth (l1
->loop
) - (int) loop_depth (l2
->loop
)) != 0)
2239 /* Make sorting stable. */
2240 return l1
->loop_num
- l2
->loop_num
;
2243 /* Mark loops which should be removed from regional allocation. We
2244 remove a loop with low register pressure inside another loop with
2245 register pressure. In this case a separate allocation of the loop
2246 hardly helps (for irregular register file architecture it could
2247 help by choosing a better hard register in the loop but we prefer
2248 faster allocation even in this case). We also remove cheap loops
2249 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH
2250 exit or enter edges are removed too because the allocation might
2251 require put pseudo moves on the EH edges (we could still do this
2252 for pseudos with caller saved hard registers in some cases but it
2253 is impossible to say here or during top-down allocation pass what
2254 hard register the pseudos get finally). */
2256 mark_loops_for_removal (void)
2259 ira_loop_tree_node_t
*sorted_loops
;
2262 ira_assert (current_loops
!= NULL
);
2264 = (ira_loop_tree_node_t
*) ira_allocate (sizeof (ira_loop_tree_node_t
)
2265 * number_of_loops (cfun
));
2266 for (n
= i
= 0; vec_safe_iterate (get_loops (cfun
), i
, &loop
); i
++)
2267 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
2269 if (ira_loop_nodes
[i
].parent
== NULL
)
2271 /* Don't remove the root. */
2272 ira_loop_nodes
[i
].to_remove_p
= false;
2275 sorted_loops
[n
++] = &ira_loop_nodes
[i
];
2276 ira_loop_nodes
[i
].to_remove_p
2277 = ((low_pressure_loop_node_p (ira_loop_nodes
[i
].parent
)
2278 && low_pressure_loop_node_p (&ira_loop_nodes
[i
]))
2280 || loop_with_complex_edge_p (ira_loop_nodes
[i
].loop
)
2284 qsort (sorted_loops
, n
, sizeof (ira_loop_tree_node_t
), loop_compare_func
);
2285 for (i
= 0; n
- i
+ 1 > IRA_MAX_LOOPS_NUM
; i
++)
2287 sorted_loops
[i
]->to_remove_p
= true;
2288 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2291 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2292 sorted_loops
[i
]->loop_num
, sorted_loops
[i
]->loop
->header
->index
,
2293 sorted_loops
[i
]->loop
->header
->frequency
,
2294 loop_depth (sorted_loops
[i
]->loop
),
2295 low_pressure_loop_node_p (sorted_loops
[i
]->parent
)
2296 && low_pressure_loop_node_p (sorted_loops
[i
])
2297 ? "low pressure" : "cheap loop");
2299 ira_free (sorted_loops
);
2302 /* Mark all loops but root for removing. */
2304 mark_all_loops_for_removal (void)
2309 ira_assert (current_loops
!= NULL
);
2310 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
2311 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
2313 if (ira_loop_nodes
[i
].parent
== NULL
)
2315 /* Don't remove the root. */
2316 ira_loop_nodes
[i
].to_remove_p
= false;
2319 ira_loop_nodes
[i
].to_remove_p
= true;
2320 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2323 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2324 ira_loop_nodes
[i
].loop_num
,
2325 ira_loop_nodes
[i
].loop
->header
->index
,
2326 ira_loop_nodes
[i
].loop
->header
->frequency
,
2327 loop_depth (ira_loop_nodes
[i
].loop
));
2331 /* Definition of vector of loop tree nodes. */
2333 /* Vec containing references to all removed loop tree nodes. */
2334 static vec
<ira_loop_tree_node_t
> removed_loop_vec
;
2336 /* Vec containing references to all children of loop tree nodes. */
2337 static vec
<ira_loop_tree_node_t
> children_vec
;
2339 /* Remove subregions of NODE if their separate allocation will not
2340 improve the result. */
2342 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node
)
2346 ira_loop_tree_node_t subnode
;
2348 remove_p
= node
->to_remove_p
;
2350 children_vec
.safe_push (node
);
2351 start
= children_vec
.length ();
2352 for (subnode
= node
->children
; subnode
!= NULL
; subnode
= subnode
->next
)
2353 if (subnode
->bb
== NULL
)
2354 remove_uneccesary_loop_nodes_from_loop_tree (subnode
);
2356 children_vec
.safe_push (subnode
);
2357 node
->children
= node
->subloops
= NULL
;
2360 removed_loop_vec
.safe_push (node
);
2363 while (children_vec
.length () > start
)
2365 subnode
= children_vec
.pop ();
2366 subnode
->parent
= node
;
2367 subnode
->next
= node
->children
;
2368 node
->children
= subnode
;
2369 if (subnode
->bb
== NULL
)
2371 subnode
->subloop_next
= node
->subloops
;
2372 node
->subloops
= subnode
;
2377 /* Return TRUE if NODE is inside PARENT. */
2379 loop_is_inside_p (ira_loop_tree_node_t node
, ira_loop_tree_node_t parent
)
2381 for (node
= node
->parent
; node
!= NULL
; node
= node
->parent
)
2387 /* Sort allocnos according to their order in regno allocno list. */
2389 regno_allocno_order_compare_func (const void *v1p
, const void *v2p
)
2391 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2392 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2393 ira_loop_tree_node_t n1
= ALLOCNO_LOOP_TREE_NODE (a1
);
2394 ira_loop_tree_node_t n2
= ALLOCNO_LOOP_TREE_NODE (a2
);
2396 if (loop_is_inside_p (n1
, n2
))
2398 else if (loop_is_inside_p (n2
, n1
))
2400 /* If allocnos are equally good, sort by allocno numbers, so that
2401 the results of qsort leave nothing to chance. We put allocnos
2402 with higher number first in the list because it is the original
2403 order for allocnos from loops on the same levels. */
2404 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2407 /* This array is used to sort allocnos to restore allocno order in
2408 the regno allocno list. */
2409 static ira_allocno_t
*regno_allocnos
;
2411 /* Restore allocno order for REGNO in the regno allocno list. */
2413 ira_rebuild_regno_allocno_list (int regno
)
2418 for (n
= 0, a
= ira_regno_allocno_map
[regno
];
2420 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2421 regno_allocnos
[n
++] = a
;
2423 qsort (regno_allocnos
, n
, sizeof (ira_allocno_t
),
2424 regno_allocno_order_compare_func
);
2425 for (i
= 1; i
< n
; i
++)
2426 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[i
- 1]) = regno_allocnos
[i
];
2427 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[n
- 1]) = NULL
;
2428 ira_regno_allocno_map
[regno
] = regno_allocnos
[0];
2429 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2430 fprintf (ira_dump_file
, " Rebuilding regno allocno list for %d\n", regno
);
2433 /* Propagate info from allocno FROM_A to allocno A. */
2435 propagate_some_info_from_allocno (ira_allocno_t a
, ira_allocno_t from_a
)
2437 enum reg_class aclass
;
2439 merge_hard_reg_conflicts (from_a
, a
, false);
2440 ALLOCNO_NREFS (a
) += ALLOCNO_NREFS (from_a
);
2441 ALLOCNO_FREQ (a
) += ALLOCNO_FREQ (from_a
);
2442 ALLOCNO_CALL_FREQ (a
) += ALLOCNO_CALL_FREQ (from_a
);
2443 ALLOCNO_CALLS_CROSSED_NUM (a
) += ALLOCNO_CALLS_CROSSED_NUM (from_a
);
2444 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
)
2445 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a
);
2446 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
),
2447 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a
));
2449 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2450 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a
);
2451 if (! ALLOCNO_BAD_SPILL_P (from_a
))
2452 ALLOCNO_BAD_SPILL_P (a
) = false;
2453 aclass
= ALLOCNO_CLASS (from_a
);
2454 ira_assert (aclass
== ALLOCNO_CLASS (a
));
2455 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a
), aclass
,
2456 ALLOCNO_HARD_REG_COSTS (from_a
));
2457 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
2459 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a
));
2460 ALLOCNO_CLASS_COST (a
) += ALLOCNO_CLASS_COST (from_a
);
2461 ALLOCNO_MEMORY_COST (a
) += ALLOCNO_MEMORY_COST (from_a
);
2464 /* Remove allocnos from loops removed from the allocation
2467 remove_unnecessary_allocnos (void)
2470 bool merged_p
, rebuild_p
;
2471 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
2472 ira_loop_tree_node_t a_node
, parent
;
2475 regno_allocnos
= NULL
;
2476 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
2479 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
2483 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
2484 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2485 if (! a_node
->to_remove_p
)
2489 for (parent
= a_node
->parent
;
2490 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2491 && parent
->to_remove_p
;
2492 parent
= parent
->parent
)
2494 if (parent_a
== NULL
)
2496 /* There are no allocnos with the same regno in
2497 upper region -- just move the allocno to the
2500 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
2501 parent
->regno_allocno_map
[regno
] = a
;
2502 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
2507 /* Remove the allocno and update info of allocno in
2508 the upper region. */
2510 ira_regno_allocno_map
[regno
] = next_a
;
2512 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
2513 move_allocno_live_ranges (a
, parent_a
);
2515 propagate_some_info_from_allocno (parent_a
, a
);
2516 /* Remove it from the corresponding regno allocno
2517 map to avoid info propagation of subsequent
2518 allocno into this already removed allocno. */
2519 a_node
->regno_allocno_map
[regno
] = NULL
;
2520 ira_remove_allocno_prefs (a
);
2526 /* We need to restore the order in regno allocno list. */
2528 if (regno_allocnos
== NULL
)
2530 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2531 * ira_allocnos_num
);
2532 ira_rebuild_regno_allocno_list (regno
);
2536 ira_rebuild_start_finish_chains ();
2537 if (regno_allocnos
!= NULL
)
2538 ira_free (regno_allocnos
);
2541 /* Remove allocnos from all loops but the root. */
2543 remove_low_level_allocnos (void)
2546 bool merged_p
, propagate_p
;
2547 ira_allocno_t a
, top_a
;
2548 ira_loop_tree_node_t a_node
, parent
;
2549 ira_allocno_iterator ai
;
2552 FOR_EACH_ALLOCNO (a
, ai
)
2554 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2555 if (a_node
== ira_loop_tree_root
|| ALLOCNO_CAP_MEMBER (a
) != NULL
)
2557 regno
= ALLOCNO_REGNO (a
);
2558 if ((top_a
= ira_loop_tree_root
->regno_allocno_map
[regno
]) == NULL
)
2560 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2561 ira_loop_tree_root
->regno_allocno_map
[regno
] = a
;
2564 propagate_p
= a_node
->parent
->regno_allocno_map
[regno
] == NULL
;
2565 /* Remove the allocno and update info of allocno in the upper
2567 move_allocno_live_ranges (a
, top_a
);
2570 propagate_some_info_from_allocno (top_a
, a
);
2572 FOR_EACH_ALLOCNO (a
, ai
)
2574 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2575 if (a_node
== ira_loop_tree_root
)
2577 parent
= a_node
->parent
;
2578 regno
= ALLOCNO_REGNO (a
);
2579 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2580 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2581 else if (ALLOCNO_CAP (a
) == NULL
)
2582 ira_assert (parent
->regno_allocno_map
[regno
] != NULL
);
2584 FOR_EACH_ALLOCNO (a
, ai
)
2586 regno
= ALLOCNO_REGNO (a
);
2587 if (ira_loop_tree_root
->regno_allocno_map
[regno
] == a
)
2590 ira_allocno_object_iterator oi
;
2592 ira_regno_allocno_map
[regno
] = a
;
2593 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = NULL
;
2594 ALLOCNO_CAP_MEMBER (a
) = NULL
;
2595 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2596 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
2597 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
2599 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2600 ALLOCNO_NO_STACK_REG_P (a
) = true;
2605 ira_remove_allocno_prefs (a
);
2610 ira_rebuild_start_finish_chains ();
2613 /* Remove loops from consideration. We remove all loops except for
2614 root if ALL_P or loops for which a separate allocation will not
2615 improve the result. We have to do this after allocno creation and
2616 their costs and allocno class evaluation because only after that
2617 the register pressure can be known and is calculated. */
2619 remove_unnecessary_regions (bool all_p
)
2621 if (current_loops
== NULL
)
2624 mark_all_loops_for_removal ();
2626 mark_loops_for_removal ();
2627 children_vec
.create (last_basic_block_for_fn (cfun
)
2628 + number_of_loops (cfun
));
2629 removed_loop_vec
.create (last_basic_block_for_fn (cfun
)
2630 + number_of_loops (cfun
));
2631 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
);
2632 children_vec
.release ();
2634 remove_low_level_allocnos ();
2636 remove_unnecessary_allocnos ();
2637 while (removed_loop_vec
.length () > 0)
2638 finish_loop_tree_node (removed_loop_vec
.pop ());
2639 removed_loop_vec
.release ();
2644 /* At this point true value of allocno attribute bad_spill_p means
2645 that there is an insn where allocno occurs and where the allocno
2646 can not be used as memory. The function updates the attribute, now
2647 it can be true only for allocnos which can not be used as memory in
2648 an insn and in whose live ranges there is other allocno deaths.
2649 Spilling allocnos with true value will not improve the code because
2650 it will not make other allocnos colorable and additional reloads
2651 for the corresponding pseudo will be generated in reload pass for
2652 each insn it occurs.
2654 This is a trick mentioned in one classic article of Chaitin etc
2655 which is frequently omitted in other implementations of RA based on
2658 update_bad_spill_attribute (void)
2662 ira_allocno_iterator ai
;
2663 ira_allocno_object_iterator aoi
;
2666 enum reg_class aclass
;
2667 bitmap_head dead_points
[N_REG_CLASSES
];
2669 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2671 aclass
= ira_allocno_classes
[i
];
2672 bitmap_initialize (&dead_points
[aclass
], ®_obstack
);
2674 FOR_EACH_ALLOCNO (a
, ai
)
2676 aclass
= ALLOCNO_CLASS (a
);
2677 if (aclass
== NO_REGS
)
2679 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2680 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2681 bitmap_set_bit (&dead_points
[aclass
], r
->finish
);
2683 FOR_EACH_ALLOCNO (a
, ai
)
2685 aclass
= ALLOCNO_CLASS (a
);
2686 if (aclass
== NO_REGS
)
2688 if (! ALLOCNO_BAD_SPILL_P (a
))
2690 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2692 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2694 for (i
= r
->start
+ 1; i
< r
->finish
; i
++)
2695 if (bitmap_bit_p (&dead_points
[aclass
], i
))
2702 ALLOCNO_BAD_SPILL_P (a
) = false;
2707 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2709 aclass
= ira_allocno_classes
[i
];
2710 bitmap_clear (&dead_points
[aclass
]);
2716 /* Set up minimal and maximal live range points for allocnos. */
2718 setup_min_max_allocno_live_range_point (void)
2721 ira_allocno_t a
, parent_a
, cap
;
2722 ira_allocno_iterator ai
;
2723 #ifdef ENABLE_IRA_CHECKING
2724 ira_object_iterator oi
;
2728 ira_loop_tree_node_t parent
;
2730 FOR_EACH_ALLOCNO (a
, ai
)
2732 int n
= ALLOCNO_NUM_OBJECTS (a
);
2734 for (i
= 0; i
< n
; i
++)
2736 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2737 r
= OBJECT_LIVE_RANGES (obj
);
2740 OBJECT_MAX (obj
) = r
->finish
;
2741 for (; r
->next
!= NULL
; r
= r
->next
)
2743 OBJECT_MIN (obj
) = r
->start
;
2746 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2747 for (a
= ira_regno_allocno_map
[i
];
2749 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2752 int n
= ALLOCNO_NUM_OBJECTS (a
);
2754 for (j
= 0; j
< n
; j
++)
2756 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
2757 ira_object_t parent_obj
;
2759 if (OBJECT_MAX (obj
) < 0)
2761 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2762 /* Accumulation of range info. */
2763 if (ALLOCNO_CAP (a
) != NULL
)
2765 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
2767 ira_object_t cap_obj
= ALLOCNO_OBJECT (cap
, j
);
2768 if (OBJECT_MAX (cap_obj
) < OBJECT_MAX (obj
))
2769 OBJECT_MAX (cap_obj
) = OBJECT_MAX (obj
);
2770 if (OBJECT_MIN (cap_obj
) > OBJECT_MIN (obj
))
2771 OBJECT_MIN (cap_obj
) = OBJECT_MIN (obj
);
2775 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
2777 parent_a
= parent
->regno_allocno_map
[i
];
2778 parent_obj
= ALLOCNO_OBJECT (parent_a
, j
);
2779 if (OBJECT_MAX (parent_obj
) < OBJECT_MAX (obj
))
2780 OBJECT_MAX (parent_obj
) = OBJECT_MAX (obj
);
2781 if (OBJECT_MIN (parent_obj
) > OBJECT_MIN (obj
))
2782 OBJECT_MIN (parent_obj
) = OBJECT_MIN (obj
);
2785 #ifdef ENABLE_IRA_CHECKING
2786 FOR_EACH_OBJECT (obj
, oi
)
2788 if ((0 <= OBJECT_MIN (obj
) && OBJECT_MIN (obj
) <= ira_max_point
)
2789 && (0 <= OBJECT_MAX (obj
) && OBJECT_MAX (obj
) <= ira_max_point
))
2796 /* Sort allocnos according to their live ranges. Allocnos with
2797 smaller allocno class are put first unless we use priority
2798 coloring. Allocnos with the same class are ordered according
2799 their start (min). Allocnos with the same start are ordered
2800 according their finish (max). */
2802 object_range_compare_func (const void *v1p
, const void *v2p
)
2805 ira_object_t obj1
= *(const ira_object_t
*) v1p
;
2806 ira_object_t obj2
= *(const ira_object_t
*) v2p
;
2807 ira_allocno_t a1
= OBJECT_ALLOCNO (obj1
);
2808 ira_allocno_t a2
= OBJECT_ALLOCNO (obj2
);
2810 if ((diff
= OBJECT_MIN (obj1
) - OBJECT_MIN (obj2
)) != 0)
2812 if ((diff
= OBJECT_MAX (obj1
) - OBJECT_MAX (obj2
)) != 0)
2814 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2817 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2819 sort_conflict_id_map (void)
2823 ira_allocno_iterator ai
;
2826 FOR_EACH_ALLOCNO (a
, ai
)
2828 ira_allocno_object_iterator oi
;
2831 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2832 ira_object_id_map
[num
++] = obj
;
2835 qsort (ira_object_id_map
, num
, sizeof (ira_object_t
),
2836 object_range_compare_func
);
2837 for (i
= 0; i
< num
; i
++)
2839 ira_object_t obj
= ira_object_id_map
[i
];
2841 gcc_assert (obj
!= NULL
);
2842 OBJECT_CONFLICT_ID (obj
) = i
;
2844 for (i
= num
; i
< ira_objects_num
; i
++)
2845 ira_object_id_map
[i
] = NULL
;
2848 /* Set up minimal and maximal conflict ids of allocnos with which
2849 given allocno can conflict. */
2851 setup_min_max_conflict_allocno_ids (void)
2854 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
2855 int *live_range_min
, *last_lived
;
2856 int word0_min
, word0_max
;
2858 ira_allocno_iterator ai
;
2860 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
2862 first_not_finished
= -1;
2863 for (i
= 0; i
< ira_objects_num
; i
++)
2865 ira_object_t obj
= ira_object_id_map
[i
];
2870 a
= OBJECT_ALLOCNO (obj
);
2874 aclass
= ALLOCNO_CLASS (a
);
2876 first_not_finished
= i
;
2880 start
= OBJECT_MIN (obj
);
2881 /* If we skip an allocno, the allocno with smaller ids will
2882 be also skipped because of the secondary sorting the
2883 range finishes (see function
2884 object_range_compare_func). */
2885 while (first_not_finished
< i
2886 && start
> OBJECT_MAX (ira_object_id_map
2887 [first_not_finished
]))
2888 first_not_finished
++;
2889 min
= first_not_finished
;
2892 /* We could increase min further in this case but it is good
2895 live_range_min
[i
] = OBJECT_MIN (obj
);
2896 OBJECT_MIN (obj
) = min
;
2898 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
2900 filled_area_start
= -1;
2901 for (i
= ira_objects_num
- 1; i
>= 0; i
--)
2903 ira_object_t obj
= ira_object_id_map
[i
];
2908 a
= OBJECT_ALLOCNO (obj
);
2911 aclass
= ALLOCNO_CLASS (a
);
2912 for (j
= 0; j
< ira_max_point
; j
++)
2914 filled_area_start
= ira_max_point
;
2916 min
= live_range_min
[i
];
2917 finish
= OBJECT_MAX (obj
);
2918 max
= last_lived
[finish
];
2920 /* We could decrease max further in this case but it is good
2922 max
= OBJECT_CONFLICT_ID (obj
) - 1;
2923 OBJECT_MAX (obj
) = max
;
2924 /* In filling, we can go further A range finish to recognize
2925 intersection quickly because if the finish of subsequently
2926 processed allocno (it has smaller conflict id) range is
2927 further A range finish than they are definitely intersected
2928 (the reason for this is the allocnos with bigger conflict id
2929 have their range starts not smaller than allocnos with
2931 for (j
= min
; j
< filled_area_start
; j
++)
2933 filled_area_start
= min
;
2935 ira_free (last_lived
);
2936 ira_free (live_range_min
);
2938 /* For allocnos with more than one object, we may later record extra conflicts in
2939 subobject 0 that we cannot really know about here.
2940 For now, simply widen the min/max range of these subobjects. */
2942 word0_min
= INT_MAX
;
2943 word0_max
= INT_MIN
;
2945 FOR_EACH_ALLOCNO (a
, ai
)
2947 int n
= ALLOCNO_NUM_OBJECTS (a
);
2952 obj0
= ALLOCNO_OBJECT (a
, 0);
2953 if (OBJECT_CONFLICT_ID (obj0
) < word0_min
)
2954 word0_min
= OBJECT_CONFLICT_ID (obj0
);
2955 if (OBJECT_CONFLICT_ID (obj0
) > word0_max
)
2956 word0_max
= OBJECT_CONFLICT_ID (obj0
);
2958 FOR_EACH_ALLOCNO (a
, ai
)
2960 int n
= ALLOCNO_NUM_OBJECTS (a
);
2965 obj0
= ALLOCNO_OBJECT (a
, 0);
2966 if (OBJECT_MIN (obj0
) > word0_min
)
2967 OBJECT_MIN (obj0
) = word0_min
;
2968 if (OBJECT_MAX (obj0
) < word0_max
)
2969 OBJECT_MAX (obj0
) = word0_max
;
2979 ira_allocno_iterator ai
;
2980 ira_loop_tree_node_t loop_tree_node
;
2982 FOR_EACH_ALLOCNO (a
, ai
)
2984 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2986 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2987 create_cap_allocno (a
);
2988 else if (ALLOCNO_CAP (a
) == NULL
)
2990 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2991 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2992 create_cap_allocno (a
);
2999 /* The page contains code transforming more one region internal
3000 representation (IR) to one region IR which is necessary for reload.
3001 This transformation is called IR flattening. We might just rebuild
3002 the IR for one region but we don't do it because it takes a lot of
3005 /* Map: regno -> allocnos which will finally represent the regno for
3006 IR with one region. */
3007 static ira_allocno_t
*regno_top_level_allocno_map
;
3009 /* Find the allocno that corresponds to A at a level one higher up in the
3010 loop tree. Returns NULL if A is a cap, or if it has no parent. */
3012 ira_parent_allocno (ira_allocno_t a
)
3014 ira_loop_tree_node_t parent
;
3016 if (ALLOCNO_CAP (a
) != NULL
)
3019 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3023 return parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)];
3026 /* Find the allocno that corresponds to A at a level one higher up in the
3027 loop tree. If ALLOCNO_CAP is set for A, return that. */
3029 ira_parent_or_cap_allocno (ira_allocno_t a
)
3031 if (ALLOCNO_CAP (a
) != NULL
)
3032 return ALLOCNO_CAP (a
);
3034 return ira_parent_allocno (a
);
3037 /* Process all allocnos originated from pseudo REGNO and copy live
3038 ranges, hard reg conflicts, and allocno stack reg attributes from
3039 low level allocnos to final allocnos which are destinations of
3040 removed stores at a loop exit. Return true if we copied live
3043 copy_info_to_removed_store_destinations (int regno
)
3046 ira_allocno_t parent_a
= NULL
;
3047 ira_loop_tree_node_t parent
;
3051 for (a
= ira_regno_allocno_map
[regno
];
3053 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3055 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))])
3056 /* This allocno will be removed. */
3059 /* Caps will be removed. */
3060 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3061 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3063 parent
= parent
->parent
)
3064 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
3066 == regno_top_level_allocno_map
[REGNO
3067 (allocno_emit_reg (parent_a
))]
3068 && ALLOCNO_EMIT_DATA (parent_a
)->mem_optimized_dest_p
))
3070 if (parent
== NULL
|| parent_a
== NULL
)
3073 copy_allocno_live_ranges (a
, parent_a
);
3074 merge_hard_reg_conflicts (a
, parent_a
, true);
3076 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
3077 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3078 += ALLOCNO_CALLS_CROSSED_NUM (a
);
3079 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3080 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3081 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a
),
3082 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
3083 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3084 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3090 /* Flatten the IR. In other words, this function transforms IR as if
3091 it were built with one region (without loops). We could make it
3092 much simpler by rebuilding IR with one region, but unfortunately it
3093 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3094 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3095 IRA_MAX_POINT before emitting insns on the loop borders. */
3097 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
3102 bool new_pseudos_p
, merged_p
, mem_dest_p
;
3104 enum reg_class aclass
;
3105 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
3107 ira_loop_tree_node_t node
;
3109 ira_allocno_iterator ai
;
3110 ira_copy_iterator ci
;
3112 regno_top_level_allocno_map
3113 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
3114 * sizeof (ira_allocno_t
));
3115 memset (regno_top_level_allocno_map
, 0,
3116 max_reg_num () * sizeof (ira_allocno_t
));
3117 new_pseudos_p
= merged_p
= false;
3118 FOR_EACH_ALLOCNO (a
, ai
)
3120 ira_allocno_object_iterator oi
;
3123 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3124 /* Caps are not in the regno allocno maps and they are never
3125 will be transformed into allocnos existing after IR
3128 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3129 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
3130 OBJECT_CONFLICT_HARD_REGS (obj
));
3132 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
3135 /* Fix final allocno attributes. */
3136 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
3139 for (a
= ira_regno_allocno_map
[i
];
3141 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3143 ira_emit_data_t parent_data
, data
= ALLOCNO_EMIT_DATA (a
);
3145 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3146 if (data
->somewhere_renamed_p
)
3147 new_pseudos_p
= true;
3148 parent_a
= ira_parent_allocno (a
);
3149 if (parent_a
== NULL
)
3151 ALLOCNO_COPIES (a
) = NULL
;
3152 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3155 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
3157 if (data
->mem_optimized_dest
!= NULL
)
3159 parent_data
= ALLOCNO_EMIT_DATA (parent_a
);
3160 if (REGNO (data
->reg
) == REGNO (parent_data
->reg
))
3162 merge_hard_reg_conflicts (a
, parent_a
, true);
3163 move_allocno_live_ranges (a
, parent_a
);
3165 parent_data
->mem_optimized_dest_p
3166 = (parent_data
->mem_optimized_dest_p
3167 || data
->mem_optimized_dest_p
);
3170 new_pseudos_p
= true;
3173 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
3174 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
3175 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
3176 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3177 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
3178 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3179 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3180 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3181 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3182 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
3183 && ALLOCNO_NREFS (parent_a
) >= 0
3184 && ALLOCNO_FREQ (parent_a
) >= 0);
3185 aclass
= ALLOCNO_CLASS (parent_a
);
3186 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
3187 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
3188 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
3189 for (j
= 0; j
< hard_regs_num
; j
++)
3190 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
3191 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
3192 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
3193 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
3194 for (j
= 0; j
< hard_regs_num
; j
++)
3195 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
3196 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
3197 ALLOCNO_CLASS_COST (parent_a
)
3198 -= ALLOCNO_CLASS_COST (a
);
3199 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
3200 parent_a
= ira_parent_allocno (parent_a
);
3201 if (parent_a
== NULL
)
3204 ALLOCNO_COPIES (a
) = NULL
;
3205 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3207 if (mem_dest_p
&& copy_info_to_removed_store_destinations (i
))
3210 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
3211 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
3212 ira_rebuild_start_finish_chains ();
3215 sparseset objects_live
;
3217 /* Rebuild conflicts. */
3218 FOR_EACH_ALLOCNO (a
, ai
)
3220 ira_allocno_object_iterator oi
;
3223 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3224 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3226 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3228 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3229 ira_assert (r
->object
== obj
);
3230 clear_conflicts (obj
);
3233 objects_live
= sparseset_alloc (ira_objects_num
);
3234 for (i
= 0; i
< ira_max_point
; i
++)
3236 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
3238 ira_object_t obj
= r
->object
;
3240 a
= OBJECT_ALLOCNO (obj
);
3241 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3242 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3245 aclass
= ALLOCNO_CLASS (a
);
3246 sparseset_set_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
3247 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, n
)
3249 ira_object_t live_obj
= ira_object_id_map
[n
];
3250 ira_allocno_t live_a
= OBJECT_ALLOCNO (live_obj
);
3251 enum reg_class live_aclass
= ALLOCNO_CLASS (live_a
);
3253 if (ira_reg_classes_intersect_p
[aclass
][live_aclass
]
3254 /* Don't set up conflict for the allocno with itself. */
3256 ira_add_conflict (obj
, live_obj
);
3260 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
3261 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (r
->object
));
3263 sparseset_free (objects_live
);
3264 compress_conflict_vecs ();
3266 /* Mark some copies for removing and change allocnos in the rest
3268 FOR_EACH_COPY (cp
, ci
)
3270 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
3271 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
3273 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3275 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3276 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
3277 ALLOCNO_NUM (cp
->first
),
3278 REGNO (allocno_emit_reg (cp
->first
)),
3279 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
3280 ALLOCNO_NUM (cp
->second
),
3281 REGNO (allocno_emit_reg (cp
->second
)));
3282 cp
->loop_tree_node
= NULL
;
3286 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->first
))];
3288 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->second
))];
3289 node
= cp
->loop_tree_node
;
3291 keep_p
= true; /* It copy generated in ira-emit.c. */
3294 /* Check that the copy was not propagated from level on
3295 which we will have different pseudos. */
3296 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
3297 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
3298 keep_p
= ((REGNO (allocno_emit_reg (first
))
3299 == REGNO (allocno_emit_reg (node_first
)))
3300 && (REGNO (allocno_emit_reg (second
))
3301 == REGNO (allocno_emit_reg (node_second
))));
3305 cp
->loop_tree_node
= ira_loop_tree_root
;
3307 cp
->second
= second
;
3311 cp
->loop_tree_node
= NULL
;
3312 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3313 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
3314 cp
->num
, ALLOCNO_NUM (cp
->first
),
3315 REGNO (allocno_emit_reg (cp
->first
)),
3316 ALLOCNO_NUM (cp
->second
),
3317 REGNO (allocno_emit_reg (cp
->second
)));
3320 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3321 FOR_EACH_ALLOCNO (a
, ai
)
3323 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3324 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3326 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3327 fprintf (ira_dump_file
, " Remove a%dr%d\n",
3328 ALLOCNO_NUM (a
), REGNO (allocno_emit_reg (a
)));
3329 ira_remove_allocno_prefs (a
);
3333 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
3334 ALLOCNO_REGNO (a
) = REGNO (allocno_emit_reg (a
));
3335 ALLOCNO_CAP (a
) = NULL
;
3336 /* Restore updated costs for assignments from reload. */
3337 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3338 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
3339 if (! ALLOCNO_ASSIGNED_P (a
))
3340 ira_free_allocno_updated_costs (a
);
3341 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3342 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3344 /* Remove unnecessary copies. */
3345 FOR_EACH_COPY (cp
, ci
)
3347 if (cp
->loop_tree_node
== NULL
)
3349 ira_copies
[cp
->num
] = NULL
;
3354 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
3355 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
3356 add_allocno_copy_to_list (cp
);
3357 swap_allocno_copy_ends_if_necessary (cp
);
3359 rebuild_regno_allocno_maps ();
3360 if (ira_max_point
!= ira_max_point_before_emit
)
3361 ira_compress_allocno_live_ranges ();
3362 ira_free (regno_top_level_allocno_map
);
3367 #ifdef ENABLE_IRA_CHECKING
3368 /* Check creation of all allocnos. Allocnos on lower levels should
3369 have allocnos or caps on all upper levels. */
3371 check_allocno_creation (void)
3374 ira_allocno_iterator ai
;
3375 ira_loop_tree_node_t loop_tree_node
;
3377 FOR_EACH_ALLOCNO (a
, ai
)
3379 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3380 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
3382 if (loop_tree_node
== ira_loop_tree_root
)
3384 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3385 ira_assert (ALLOCNO_CAP (a
) != NULL
);
3386 else if (ALLOCNO_CAP (a
) == NULL
)
3387 ira_assert (loop_tree_node
->parent
3388 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
3389 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
3395 /* Identify allocnos which prefer a register class with a single hard register.
3396 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3397 less likely to use the preferred singleton register. */
3399 update_conflict_hard_reg_costs (void)
3402 ira_allocno_iterator ai
;
3405 FOR_EACH_ALLOCNO (a
, ai
)
3407 reg_class_t aclass
= ALLOCNO_CLASS (a
);
3408 reg_class_t pref
= reg_preferred_class (ALLOCNO_REGNO (a
));
3409 int singleton
= ira_class_singleton
[pref
][ALLOCNO_MODE (a
)];
3412 index
= ira_class_hard_reg_index
[(int) aclass
][singleton
];
3415 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) == NULL
3416 || ALLOCNO_HARD_REG_COSTS (a
) == NULL
)
3419 for (i
= ira_class_hard_regs_num
[(int) aclass
] - 1; i
>= 0; i
--)
3420 if (ALLOCNO_HARD_REG_COSTS (a
)[i
] > ALLOCNO_CLASS_COST (a
)
3421 && min
> ALLOCNO_HARD_REG_COSTS (a
)[i
])
3422 min
= ALLOCNO_HARD_REG_COSTS (a
)[i
];
3425 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
3427 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[index
]
3428 -= min
- ALLOCNO_CLASS_COST (a
);
3432 /* Create a internal representation (IR) for IRA (allocnos, copies,
3433 loop tree nodes). The function returns TRUE if we generate loop
3434 structure (besides nodes representing all function and the basic
3435 blocks) for regional allocation. A true return means that we
3436 really need to flatten IR before the reload. */
3443 initiate_cost_vectors ();
3444 initiate_allocnos ();
3447 create_loop_tree_nodes ();
3451 create_allocno_objects ();
3452 ira_create_allocno_live_ranges ();
3453 remove_unnecessary_regions (false);
3454 ira_compress_allocno_live_ranges ();
3455 update_bad_spill_attribute ();
3456 loops_p
= more_one_region_p ();
3459 propagate_allocno_info ();
3462 ira_tune_allocno_costs ();
3463 #ifdef ENABLE_IRA_CHECKING
3464 check_allocno_creation ();
3466 setup_min_max_allocno_live_range_point ();
3467 sort_conflict_id_map ();
3468 setup_min_max_conflict_allocno_ids ();
3469 ira_build_conflicts ();
3470 update_conflict_hard_reg_costs ();
3471 if (! ira_conflicts_p
)
3474 ira_allocno_iterator ai
;
3476 /* Remove all regions but root one. */
3479 remove_unnecessary_regions (true);
3482 /* We don't save hard registers around calls for fast allocation
3483 -- add caller clobbered registers as conflicting ones to
3484 allocno crossing calls. */
3485 FOR_EACH_ALLOCNO (a
, ai
)
3486 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
3487 ior_hard_reg_conflicts (a
, &call_used_reg_set
);
3489 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3490 print_copies (ira_dump_file
);
3491 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3492 print_prefs (ira_dump_file
);
3493 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3498 ira_allocno_iterator ai
;
3503 FOR_EACH_ALLOCNO (a
, ai
)
3505 int j
, nobj
= ALLOCNO_NUM_OBJECTS (a
);
3509 for (j
= 0; j
< nobj
; j
++)
3511 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
3512 n
+= OBJECT_NUM_CONFLICTS (obj
);
3513 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3517 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
3518 current_loops
== NULL
? 1 : number_of_loops (cfun
),
3519 n_basic_blocks_for_fn (cfun
), ira_max_point
);
3520 fprintf (ira_dump_file
,
3521 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3522 ira_allocnos_num
, nr_big
, ira_copies_num
, n
, nr
);
3527 /* Release the data created by function ira_build. */
3531 finish_loop_tree_nodes ();
3535 finish_cost_vectors ();
3536 ira_finish_allocno_live_ranges ();