1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2015 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"
38 #include "dominance.h"
40 #include "basic-block.h"
41 #include "insn-config.h"
43 #include "diagnostic-core.h"
47 #include "sparseset.h"
49 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
51 static ira_copy_t
find_allocno_copy (ira_allocno_t
, ira_allocno_t
, rtx_insn
*,
52 ira_loop_tree_node_t
);
54 /* The root of the loop tree corresponding to the all function. */
55 ira_loop_tree_node_t ira_loop_tree_root
;
57 /* Height of the loop tree. */
58 int ira_loop_tree_height
;
60 /* All nodes representing basic blocks are referred through the
61 following array. We can not use basic block member `aux' for this
62 because it is used for insertion of insns on edges. */
63 ira_loop_tree_node_t ira_bb_nodes
;
65 /* All nodes representing loops are referred through the following
67 ira_loop_tree_node_t ira_loop_nodes
;
69 /* And size of the ira_loop_nodes array. */
70 unsigned int ira_loop_nodes_count
;
72 /* Map regno -> allocnos with given regno (see comments for
73 allocno member `next_regno_allocno'). */
74 ira_allocno_t
*ira_regno_allocno_map
;
76 /* Array of references to all allocnos. The order number of the
77 allocno corresponds to the index in the array. Removed allocnos
78 have NULL element value. */
79 ira_allocno_t
*ira_allocnos
;
81 /* Sizes of the previous array. */
84 /* Count of conflict record structures we've created, used when creating
88 /* Map a conflict id to its conflict record. */
89 ira_object_t
*ira_object_id_map
;
91 /* Array of references to all allocno preferences. The order number
92 of the preference corresponds to the index in the array. */
93 ira_pref_t
*ira_prefs
;
95 /* Size of the previous array. */
98 /* Array of references to all copies. The order number of the copy
99 corresponds to the index in the array. Removed copies have NULL
101 ira_copy_t
*ira_copies
;
103 /* Size of the previous array. */
108 /* LAST_BASIC_BLOCK before generating additional insns because of live
109 range splitting. Emitting insns on a critical edge creates a new
111 static int last_basic_block_before_change
;
113 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
114 the member loop_num. */
116 init_loop_tree_node (struct ira_loop_tree_node
*node
, int loop_num
)
118 int max_regno
= max_reg_num ();
120 node
->regno_allocno_map
121 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
) * max_regno
);
122 memset (node
->regno_allocno_map
, 0, sizeof (ira_allocno_t
) * max_regno
);
123 memset (node
->reg_pressure
, 0, sizeof (node
->reg_pressure
));
124 node
->all_allocnos
= ira_allocate_bitmap ();
125 node
->modified_regnos
= ira_allocate_bitmap ();
126 node
->border_allocnos
= ira_allocate_bitmap ();
127 node
->local_copies
= ira_allocate_bitmap ();
128 node
->loop_num
= loop_num
;
129 node
->children
= NULL
;
130 node
->subloops
= NULL
;
134 /* The following function allocates the loop tree nodes. If
135 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
136 the root which corresponds the all function) will be not allocated
137 but nodes will still be allocated for basic blocks. */
139 create_loop_tree_nodes (void)
149 = ((struct ira_loop_tree_node
*)
150 ira_allocate (sizeof (struct ira_loop_tree_node
)
151 * last_basic_block_for_fn (cfun
)));
152 last_basic_block_before_change
= last_basic_block_for_fn (cfun
);
153 for (i
= 0; i
< (unsigned int) last_basic_block_for_fn (cfun
); i
++)
155 ira_bb_nodes
[i
].regno_allocno_map
= NULL
;
156 memset (ira_bb_nodes
[i
].reg_pressure
, 0,
157 sizeof (ira_bb_nodes
[i
].reg_pressure
));
158 ira_bb_nodes
[i
].all_allocnos
= NULL
;
159 ira_bb_nodes
[i
].modified_regnos
= NULL
;
160 ira_bb_nodes
[i
].border_allocnos
= NULL
;
161 ira_bb_nodes
[i
].local_copies
= NULL
;
163 if (current_loops
== NULL
)
165 ira_loop_nodes_count
= 1;
166 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
167 ira_allocate (sizeof (struct ira_loop_tree_node
)));
168 init_loop_tree_node (ira_loop_nodes
, 0);
171 ira_loop_nodes_count
= number_of_loops (cfun
);
172 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
173 ira_allocate (sizeof (struct ira_loop_tree_node
)
174 * ira_loop_nodes_count
));
175 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
177 if (loop_outer (loop
) != NULL
)
179 ira_loop_nodes
[i
].regno_allocno_map
= NULL
;
181 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
182 if (e
->src
!= loop
->latch
183 && (e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
190 edges
= get_loop_exit_edges (loop
);
191 FOR_EACH_VEC_ELT (edges
, j
, e
)
192 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
201 init_loop_tree_node (&ira_loop_nodes
[i
], loop
->num
);
205 /* The function returns TRUE if there are more one allocation
208 more_one_region_p (void)
213 if (current_loops
!= NULL
)
214 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
215 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
216 && ira_loop_tree_root
!= &ira_loop_nodes
[i
])
221 /* Free the loop tree node of a loop. */
223 finish_loop_tree_node (ira_loop_tree_node_t loop
)
225 if (loop
->regno_allocno_map
!= NULL
)
227 ira_assert (loop
->bb
== NULL
);
228 ira_free_bitmap (loop
->local_copies
);
229 ira_free_bitmap (loop
->border_allocnos
);
230 ira_free_bitmap (loop
->modified_regnos
);
231 ira_free_bitmap (loop
->all_allocnos
);
232 ira_free (loop
->regno_allocno_map
);
233 loop
->regno_allocno_map
= NULL
;
237 /* Free the loop tree nodes. */
239 finish_loop_tree_nodes (void)
243 for (i
= 0; i
< ira_loop_nodes_count
; i
++)
244 finish_loop_tree_node (&ira_loop_nodes
[i
]);
245 ira_free (ira_loop_nodes
);
246 for (i
= 0; i
< (unsigned int) last_basic_block_before_change
; i
++)
248 if (ira_bb_nodes
[i
].local_copies
!= NULL
)
249 ira_free_bitmap (ira_bb_nodes
[i
].local_copies
);
250 if (ira_bb_nodes
[i
].border_allocnos
!= NULL
)
251 ira_free_bitmap (ira_bb_nodes
[i
].border_allocnos
);
252 if (ira_bb_nodes
[i
].modified_regnos
!= NULL
)
253 ira_free_bitmap (ira_bb_nodes
[i
].modified_regnos
);
254 if (ira_bb_nodes
[i
].all_allocnos
!= NULL
)
255 ira_free_bitmap (ira_bb_nodes
[i
].all_allocnos
);
256 if (ira_bb_nodes
[i
].regno_allocno_map
!= NULL
)
257 ira_free (ira_bb_nodes
[i
].regno_allocno_map
);
259 ira_free (ira_bb_nodes
);
264 /* The following recursive function adds LOOP to the loop tree
265 hierarchy. LOOP is added only once. If LOOP is NULL we adding
266 loop designating the whole function when CFG loops are not
269 add_loop_to_tree (struct loop
*loop
)
273 ira_loop_tree_node_t loop_node
, parent_node
;
275 /* We can not use loop node access macros here because of potential
276 checking and because the nodes are not initialized enough
278 if (loop
!= NULL
&& loop_outer (loop
) != NULL
)
279 add_loop_to_tree (loop_outer (loop
));
280 loop_num
= loop
!= NULL
? loop
->num
: 0;
281 if (ira_loop_nodes
[loop_num
].regno_allocno_map
!= NULL
282 && ira_loop_nodes
[loop_num
].children
== NULL
)
284 /* We have not added loop node to the tree yet. */
285 loop_node
= &ira_loop_nodes
[loop_num
];
286 loop_node
->loop
= loop
;
287 loop_node
->bb
= NULL
;
292 for (parent
= loop_outer (loop
);
294 parent
= loop_outer (parent
))
295 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
300 loop_node
->next
= NULL
;
301 loop_node
->subloop_next
= NULL
;
302 loop_node
->parent
= NULL
;
306 parent_node
= &ira_loop_nodes
[parent
->num
];
307 loop_node
->next
= parent_node
->children
;
308 parent_node
->children
= loop_node
;
309 loop_node
->subloop_next
= parent_node
->subloops
;
310 parent_node
->subloops
= loop_node
;
311 loop_node
->parent
= parent_node
;
316 /* The following recursive function sets up levels of nodes of the
317 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
318 The function returns maximal value of level in the tree + 1. */
320 setup_loop_tree_level (ira_loop_tree_node_t loop_node
, int level
)
322 int height
, max_height
;
323 ira_loop_tree_node_t subloop_node
;
325 ira_assert (loop_node
->bb
== NULL
);
326 loop_node
->level
= level
;
327 max_height
= level
+ 1;
328 for (subloop_node
= loop_node
->subloops
;
329 subloop_node
!= NULL
;
330 subloop_node
= subloop_node
->subloop_next
)
332 ira_assert (subloop_node
->bb
== NULL
);
333 height
= setup_loop_tree_level (subloop_node
, level
+ 1);
334 if (height
> max_height
)
340 /* Create the loop tree. The algorithm is designed to provide correct
341 order of loops (they are ordered by their last loop BB) and basic
342 blocks in the chain formed by member next. */
344 form_loop_tree (void)
348 ira_loop_tree_node_t bb_node
, loop_node
;
350 /* We can not use loop/bb node access macros because of potential
351 checking and because the nodes are not initialized enough
353 FOR_EACH_BB_FN (bb
, cfun
)
355 bb_node
= &ira_bb_nodes
[bb
->index
];
357 bb_node
->loop
= NULL
;
358 bb_node
->subloops
= NULL
;
359 bb_node
->children
= NULL
;
360 bb_node
->subloop_next
= NULL
;
361 bb_node
->next
= NULL
;
362 if (current_loops
== NULL
)
366 for (parent
= bb
->loop_father
;
368 parent
= loop_outer (parent
))
369 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
372 add_loop_to_tree (parent
);
373 loop_node
= &ira_loop_nodes
[parent
== NULL
? 0 : parent
->num
];
374 bb_node
->next
= loop_node
->children
;
375 bb_node
->parent
= loop_node
;
376 loop_node
->children
= bb_node
;
378 ira_loop_tree_root
= IRA_LOOP_NODE_BY_INDEX (0);
379 ira_loop_tree_height
= setup_loop_tree_level (ira_loop_tree_root
, 0);
380 ira_assert (ira_loop_tree_root
->regno_allocno_map
!= NULL
);
385 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
388 rebuild_regno_allocno_maps (void)
391 int max_regno
, regno
;
393 ira_loop_tree_node_t loop_tree_node
;
395 ira_allocno_iterator ai
;
397 ira_assert (current_loops
!= NULL
);
398 max_regno
= max_reg_num ();
399 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), l
, loop
)
400 if (ira_loop_nodes
[l
].regno_allocno_map
!= NULL
)
402 ira_free (ira_loop_nodes
[l
].regno_allocno_map
);
403 ira_loop_nodes
[l
].regno_allocno_map
404 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
406 memset (ira_loop_nodes
[l
].regno_allocno_map
, 0,
407 sizeof (ira_allocno_t
) * max_regno
);
409 ira_free (ira_regno_allocno_map
);
410 ira_regno_allocno_map
411 = (ira_allocno_t
*) ira_allocate (max_regno
* sizeof (ira_allocno_t
));
412 memset (ira_regno_allocno_map
, 0, max_regno
* sizeof (ira_allocno_t
));
413 FOR_EACH_ALLOCNO (a
, ai
)
415 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
416 /* Caps are not in the regno allocno maps. */
418 regno
= ALLOCNO_REGNO (a
);
419 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
420 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
421 ira_regno_allocno_map
[regno
] = a
;
422 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
423 /* Remember that we can create temporary allocnos to break
424 cycles in register shuffle. */
425 loop_tree_node
->regno_allocno_map
[regno
] = a
;
430 /* Pools for allocnos, allocno live ranges and objects. */
431 static pool_allocator
<live_range
> live_range_pool ("live ranges", 100);
432 static pool_allocator
<ira_allocno
> allocno_pool ("allocnos", 100);
433 static pool_allocator
<ira_object
> object_pool ("objects", 100);
435 /* Vec containing references to all created allocnos. It is a
436 container of array allocnos. */
437 static vec
<ira_allocno_t
> allocno_vec
;
439 /* Vec containing references to all created ira_objects. It is a
440 container of ira_object_id_map. */
441 static vec
<ira_object_t
> ira_object_id_map_vec
;
443 /* Initialize data concerning allocnos. */
445 initiate_allocnos (void)
447 allocno_vec
.create (max_reg_num () * 2);
449 ira_allocnos_num
= 0;
451 ira_object_id_map_vec
.create (max_reg_num () * 2);
452 ira_object_id_map
= NULL
;
453 ira_regno_allocno_map
454 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
455 * sizeof (ira_allocno_t
));
456 memset (ira_regno_allocno_map
, 0, max_reg_num () * sizeof (ira_allocno_t
));
459 /* Create and return an object corresponding to a new allocno A. */
461 ira_create_object (ira_allocno_t a
, int subword
)
463 enum reg_class aclass
= ALLOCNO_CLASS (a
);
464 ira_object_t obj
= object_pool
.allocate ();
466 OBJECT_ALLOCNO (obj
) = a
;
467 OBJECT_SUBWORD (obj
) = subword
;
468 OBJECT_CONFLICT_ID (obj
) = ira_objects_num
;
469 OBJECT_CONFLICT_VEC_P (obj
) = false;
470 OBJECT_CONFLICT_ARRAY (obj
) = NULL
;
471 OBJECT_NUM_CONFLICTS (obj
) = 0;
472 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
473 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
474 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
475 reg_class_contents
[aclass
]);
476 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
477 reg_class_contents
[aclass
]);
478 OBJECT_MIN (obj
) = INT_MAX
;
479 OBJECT_MAX (obj
) = -1;
480 OBJECT_LIVE_RANGES (obj
) = NULL
;
482 ira_object_id_map_vec
.safe_push (obj
);
484 = ira_object_id_map_vec
.address ();
485 ira_objects_num
= ira_object_id_map_vec
.length ();
490 /* Create and return the allocno corresponding to REGNO in
491 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
492 same regno if CAP_P is FALSE. */
494 ira_create_allocno (int regno
, bool cap_p
,
495 ira_loop_tree_node_t loop_tree_node
)
499 a
= allocno_pool
.allocate ();
500 ALLOCNO_REGNO (a
) = regno
;
501 ALLOCNO_LOOP_TREE_NODE (a
) = loop_tree_node
;
504 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
505 ira_regno_allocno_map
[regno
] = a
;
506 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
507 /* Remember that we can create temporary allocnos to break
508 cycles in register shuffle on region borders (see
510 loop_tree_node
->regno_allocno_map
[regno
] = a
;
512 ALLOCNO_CAP (a
) = NULL
;
513 ALLOCNO_CAP_MEMBER (a
) = NULL
;
514 ALLOCNO_NUM (a
) = ira_allocnos_num
;
515 bitmap_set_bit (loop_tree_node
->all_allocnos
, ALLOCNO_NUM (a
));
516 ALLOCNO_NREFS (a
) = 0;
517 ALLOCNO_FREQ (a
) = 0;
518 ALLOCNO_HARD_REGNO (a
) = -1;
519 ALLOCNO_CALL_FREQ (a
) = 0;
520 ALLOCNO_CALLS_CROSSED_NUM (a
) = 0;
521 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
) = 0;
522 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
524 ALLOCNO_NO_STACK_REG_P (a
) = false;
525 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = false;
527 ALLOCNO_DONT_REASSIGN_P (a
) = false;
528 ALLOCNO_BAD_SPILL_P (a
) = false;
529 ALLOCNO_ASSIGNED_P (a
) = false;
530 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
531 ALLOCNO_WMODE (a
) = ALLOCNO_MODE (a
);
532 ALLOCNO_PREFS (a
) = NULL
;
533 ALLOCNO_COPIES (a
) = NULL
;
534 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
535 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
536 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
537 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
538 ALLOCNO_CLASS (a
) = NO_REGS
;
539 ALLOCNO_UPDATED_CLASS_COST (a
) = 0;
540 ALLOCNO_CLASS_COST (a
) = 0;
541 ALLOCNO_MEMORY_COST (a
) = 0;
542 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
543 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
544 ALLOCNO_NUM_OBJECTS (a
) = 0;
546 ALLOCNO_ADD_DATA (a
) = NULL
;
547 allocno_vec
.safe_push (a
);
548 ira_allocnos
= allocno_vec
.address ();
549 ira_allocnos_num
= allocno_vec
.length ();
554 /* Set up register class for A and update its conflict hard
557 ira_set_allocno_class (ira_allocno_t a
, enum reg_class aclass
)
559 ira_allocno_object_iterator oi
;
562 ALLOCNO_CLASS (a
) = aclass
;
563 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
565 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
566 reg_class_contents
[aclass
]);
567 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
568 reg_class_contents
[aclass
]);
572 /* Determine the number of objects we should associate with allocno A
573 and allocate them. */
575 ira_create_allocno_objects (ira_allocno_t a
)
577 machine_mode mode
= ALLOCNO_MODE (a
);
578 enum reg_class aclass
= ALLOCNO_CLASS (a
);
579 int n
= ira_reg_class_max_nregs
[aclass
][mode
];
582 if (GET_MODE_SIZE (mode
) != 2 * UNITS_PER_WORD
|| n
!= 2)
585 ALLOCNO_NUM_OBJECTS (a
) = n
;
586 for (i
= 0; i
< n
; i
++)
587 ALLOCNO_OBJECT (a
, i
) = ira_create_object (a
, i
);
590 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
591 ALLOCNO_OBJECT structures. This must be called after the allocno
592 classes are known. */
594 create_allocno_objects (void)
597 ira_allocno_iterator ai
;
599 FOR_EACH_ALLOCNO (a
, ai
)
600 ira_create_allocno_objects (a
);
603 /* Merge hard register conflict information for all objects associated with
604 allocno TO into the corresponding objects associated with FROM.
605 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
607 merge_hard_reg_conflicts (ira_allocno_t from
, ira_allocno_t to
,
611 gcc_assert (ALLOCNO_NUM_OBJECTS (to
) == ALLOCNO_NUM_OBJECTS (from
));
612 for (i
= 0; i
< ALLOCNO_NUM_OBJECTS (to
); i
++)
614 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
615 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
618 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj
),
619 OBJECT_CONFLICT_HARD_REGS (from_obj
));
620 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj
),
621 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj
));
624 if (!total_only
&& ALLOCNO_NO_STACK_REG_P (from
))
625 ALLOCNO_NO_STACK_REG_P (to
) = true;
626 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from
))
627 ALLOCNO_TOTAL_NO_STACK_REG_P (to
) = true;
631 /* Update hard register conflict information for all objects associated with
632 A to include the regs in SET. */
634 ior_hard_reg_conflicts (ira_allocno_t a
, HARD_REG_SET
*set
)
636 ira_allocno_object_iterator i
;
639 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, i
)
641 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), *set
);
642 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), *set
);
646 /* Return TRUE if a conflict vector with NUM elements is more
647 profitable than a conflict bit vector for OBJ. */
649 ira_conflict_vector_profitable_p (ira_object_t obj
, int num
)
652 int max
= OBJECT_MAX (obj
);
653 int min
= OBJECT_MIN (obj
);
656 /* We prefer a bit vector in such case because it does not result
660 nw
= (max
- min
+ IRA_INT_BITS
) / IRA_INT_BITS
;
661 return (2 * sizeof (ira_object_t
) * (num
+ 1)
662 < 3 * nw
* sizeof (IRA_INT_TYPE
));
665 /* Allocates and initialize the conflict vector of OBJ for NUM
666 conflicting objects. */
668 ira_allocate_conflict_vec (ira_object_t obj
, int num
)
673 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
674 num
++; /* for NULL end marker */
675 size
= sizeof (ira_object_t
) * num
;
676 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
677 vec
= (ira_object_t
*) OBJECT_CONFLICT_ARRAY (obj
);
679 OBJECT_NUM_CONFLICTS (obj
) = 0;
680 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
681 OBJECT_CONFLICT_VEC_P (obj
) = true;
684 /* Allocate and initialize the conflict bit vector of OBJ. */
686 allocate_conflict_bit_vec (ira_object_t obj
)
690 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
691 size
= ((OBJECT_MAX (obj
) - OBJECT_MIN (obj
) + IRA_INT_BITS
)
692 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
693 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
694 memset (OBJECT_CONFLICT_ARRAY (obj
), 0, size
);
695 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
696 OBJECT_CONFLICT_VEC_P (obj
) = false;
699 /* Allocate and initialize the conflict vector or conflict bit vector
700 of OBJ for NUM conflicting allocnos whatever is more profitable. */
702 ira_allocate_object_conflicts (ira_object_t obj
, int num
)
704 if (ira_conflict_vector_profitable_p (obj
, num
))
705 ira_allocate_conflict_vec (obj
, num
);
707 allocate_conflict_bit_vec (obj
);
710 /* Add OBJ2 to the conflicts of OBJ1. */
712 add_to_conflicts (ira_object_t obj1
, ira_object_t obj2
)
717 if (OBJECT_CONFLICT_VEC_P (obj1
))
719 ira_object_t
*vec
= OBJECT_CONFLICT_VEC (obj1
);
720 int curr_num
= OBJECT_NUM_CONFLICTS (obj1
);
722 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < num
* sizeof (ira_object_t
))
724 ira_object_t
*newvec
;
725 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
726 newvec
= (ira_object_t
*) ira_allocate (size
);
727 memcpy (newvec
, vec
, curr_num
* sizeof (ira_object_t
));
730 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
731 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
735 OBJECT_NUM_CONFLICTS (obj1
)++;
739 int nw
, added_head_nw
, id
;
740 IRA_INT_TYPE
*vec
= OBJECT_CONFLICT_BITVEC (obj1
);
742 id
= OBJECT_CONFLICT_ID (obj2
);
743 if (OBJECT_MIN (obj1
) > id
)
745 /* Expand head of the bit vector. */
746 added_head_nw
= (OBJECT_MIN (obj1
) - id
- 1) / IRA_INT_BITS
+ 1;
747 nw
= (OBJECT_MAX (obj1
) - OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
748 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
749 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) >= size
)
751 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
752 vec
, nw
* sizeof (IRA_INT_TYPE
));
753 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
758 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
759 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
760 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
761 OBJECT_CONFLICT_ARRAY (obj1
), nw
* sizeof (IRA_INT_TYPE
));
762 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
764 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
765 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
766 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
767 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
768 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
770 OBJECT_MIN (obj1
) -= added_head_nw
* IRA_INT_BITS
;
772 else if (OBJECT_MAX (obj1
) < id
)
774 nw
= (id
- OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
775 size
= nw
* sizeof (IRA_INT_TYPE
);
776 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < size
)
778 /* Expand tail of the bit vector. */
779 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
780 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
781 memcpy (vec
, OBJECT_CONFLICT_ARRAY (obj1
), OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
782 memset ((char *) vec
+ OBJECT_CONFLICT_ARRAY_SIZE (obj1
),
783 0, size
- OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
784 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
785 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
786 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
788 OBJECT_MAX (obj1
) = id
;
790 SET_MINMAX_SET_BIT (vec
, id
, OBJECT_MIN (obj1
), OBJECT_MAX (obj1
));
794 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
796 ira_add_conflict (ira_object_t obj1
, ira_object_t obj2
)
798 add_to_conflicts (obj1
, obj2
);
799 add_to_conflicts (obj2
, obj1
);
802 /* Clear all conflicts of OBJ. */
804 clear_conflicts (ira_object_t obj
)
806 if (OBJECT_CONFLICT_VEC_P (obj
))
808 OBJECT_NUM_CONFLICTS (obj
) = 0;
809 OBJECT_CONFLICT_VEC (obj
)[0] = NULL
;
811 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj
) != 0)
815 nw
= (OBJECT_MAX (obj
) - OBJECT_MIN (obj
)) / IRA_INT_BITS
+ 1;
816 memset (OBJECT_CONFLICT_BITVEC (obj
), 0, nw
* sizeof (IRA_INT_TYPE
));
820 /* The array used to find duplications in conflict vectors of
822 static int *conflict_check
;
824 /* The value used to mark allocation presence in conflict vector of
825 the current allocno. */
826 static int curr_conflict_check_tick
;
828 /* Remove duplications in conflict vector of OBJ. */
830 compress_conflict_vec (ira_object_t obj
)
832 ira_object_t
*vec
, conflict_obj
;
835 ira_assert (OBJECT_CONFLICT_VEC_P (obj
));
836 vec
= OBJECT_CONFLICT_VEC (obj
);
837 curr_conflict_check_tick
++;
838 for (i
= j
= 0; (conflict_obj
= vec
[i
]) != NULL
; i
++)
840 int id
= OBJECT_CONFLICT_ID (conflict_obj
);
841 if (conflict_check
[id
] != curr_conflict_check_tick
)
843 conflict_check
[id
] = curr_conflict_check_tick
;
844 vec
[j
++] = conflict_obj
;
847 OBJECT_NUM_CONFLICTS (obj
) = j
;
851 /* Remove duplications in conflict vectors of all allocnos. */
853 compress_conflict_vecs (void)
856 ira_object_iterator oi
;
858 conflict_check
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
859 memset (conflict_check
, 0, sizeof (int) * ira_objects_num
);
860 curr_conflict_check_tick
= 0;
861 FOR_EACH_OBJECT (obj
, oi
)
863 if (OBJECT_CONFLICT_VEC_P (obj
))
864 compress_conflict_vec (obj
);
866 ira_free (conflict_check
);
869 /* This recursive function outputs allocno A and if it is a cap the
870 function outputs its members. */
872 ira_print_expanded_allocno (ira_allocno_t a
)
876 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
877 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
878 fprintf (ira_dump_file
, ",b%d", bb
->index
);
880 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
881 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
883 fprintf (ira_dump_file
, ":");
884 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
886 fprintf (ira_dump_file
, ")");
889 /* Create and return the cap representing allocno A in the
892 create_cap_allocno (ira_allocno_t a
)
895 ira_loop_tree_node_t parent
;
896 enum reg_class aclass
;
898 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
899 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
900 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
901 ALLOCNO_WMODE (cap
) = ALLOCNO_WMODE (a
);
902 aclass
= ALLOCNO_CLASS (a
);
903 ira_set_allocno_class (cap
, aclass
);
904 ira_create_allocno_objects (cap
);
905 ALLOCNO_CAP_MEMBER (cap
) = a
;
906 ALLOCNO_CAP (a
) = cap
;
907 ALLOCNO_CLASS_COST (cap
) = ALLOCNO_CLASS_COST (a
);
908 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
909 ira_allocate_and_copy_costs
910 (&ALLOCNO_HARD_REG_COSTS (cap
), aclass
, ALLOCNO_HARD_REG_COSTS (a
));
911 ira_allocate_and_copy_costs
912 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), aclass
,
913 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
914 ALLOCNO_BAD_SPILL_P (cap
) = ALLOCNO_BAD_SPILL_P (a
);
915 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
916 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
917 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
919 merge_hard_reg_conflicts (a
, cap
, false);
921 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
922 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
923 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap
),
924 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
925 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
927 fprintf (ira_dump_file
, " Creating cap ");
928 ira_print_expanded_allocno (cap
);
929 fprintf (ira_dump_file
, "\n");
934 /* Create and return a live range for OBJECT with given attributes. */
936 ira_create_live_range (ira_object_t obj
, int start
, int finish
,
941 p
= live_range_pool
.allocate ();
949 /* Create a new live range for OBJECT and queue it at the head of its
952 ira_add_live_range_to_object (ira_object_t object
, int start
, int finish
)
955 p
= ira_create_live_range (object
, start
, finish
,
956 OBJECT_LIVE_RANGES (object
));
957 OBJECT_LIVE_RANGES (object
) = p
;
960 /* Copy allocno live range R and return the result. */
962 copy_live_range (live_range_t r
)
966 p
= live_range_pool
.allocate ();
971 /* Copy allocno live range list given by its head R and return the
974 ira_copy_live_range_list (live_range_t r
)
976 live_range_t p
, first
, last
;
980 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
982 p
= copy_live_range (r
);
992 /* Merge ranges R1 and R2 and returns the result. The function
993 maintains the order of ranges and tries to minimize number of the
996 ira_merge_live_ranges (live_range_t r1
, live_range_t r2
)
998 live_range_t first
, last
;
1004 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
1006 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
;
1014 live_range_t temp
= r2
;
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 live_range_pool
.remove (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 object_pool
.remove (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 allocno_pool
.remove (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 allocno_pool
.release ();
1174 object_pool
.release ();
1175 live_range_pool
.release ();
1180 /* Pools for allocno preferences. */
1181 static pool_allocator
<ira_allocno_pref
> pref_pool ("prefs", 100);
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)
1191 pref_vec
.create (get_max_uid ());
1196 /* Return pref for A and HARD_REGNO if any. */
1198 find_allocno_pref (ira_allocno_t a
, int hard_regno
)
1202 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1203 if (pref
->allocno
== a
&& pref
->hard_regno
== hard_regno
)
1208 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1210 ira_create_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1214 pref
= pref_pool
.allocate ();
1215 pref
->num
= ira_prefs_num
;
1217 pref
->hard_regno
= hard_regno
;
1219 pref_vec
.safe_push (pref
);
1220 ira_prefs
= pref_vec
.address ();
1221 ira_prefs_num
= pref_vec
.length ();
1225 /* Attach a pref PREF to the corresponding allocno. */
1227 add_allocno_pref_to_list (ira_pref_t pref
)
1229 ira_allocno_t a
= pref
->allocno
;
1231 pref
->next_pref
= ALLOCNO_PREFS (a
);
1232 ALLOCNO_PREFS (a
) = pref
;
1235 /* Create (or update frequency if the pref already exists) the pref of
1236 allocnos A preferring HARD_REGNO with frequency FREQ. */
1238 ira_add_allocno_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1244 if ((pref
= find_allocno_pref (a
, hard_regno
)) != NULL
)
1249 pref
= ira_create_pref (a
, hard_regno
, freq
);
1250 ira_assert (a
!= NULL
);
1251 add_allocno_pref_to_list (pref
);
1254 /* Print info about PREF into file F. */
1256 print_pref (FILE *f
, ira_pref_t pref
)
1258 fprintf (f
, " pref%d:a%d(r%d)<-hr%d@%d\n", pref
->num
,
1259 ALLOCNO_NUM (pref
->allocno
), ALLOCNO_REGNO (pref
->allocno
),
1260 pref
->hard_regno
, pref
->freq
);
1263 /* Print info about PREF into stderr. */
1265 ira_debug_pref (ira_pref_t pref
)
1267 print_pref (stderr
, pref
);
1270 /* Print info about all prefs into file F. */
1272 print_prefs (FILE *f
)
1275 ira_pref_iterator pi
;
1277 FOR_EACH_PREF (pref
, pi
)
1278 print_pref (f
, pref
);
1281 /* Print info about all prefs into stderr. */
1283 ira_debug_prefs (void)
1285 print_prefs (stderr
);
1288 /* Print info about prefs involving allocno A into file F. */
1290 print_allocno_prefs (FILE *f
, ira_allocno_t a
)
1294 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1295 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1296 fprintf (f
, " pref%d:hr%d@%d", pref
->num
, pref
->hard_regno
, pref
->freq
);
1300 /* Print info about prefs involving allocno A into stderr. */
1302 ira_debug_allocno_prefs (ira_allocno_t a
)
1304 print_allocno_prefs (stderr
, a
);
1307 /* The function frees memory allocated for PREF. */
1309 finish_pref (ira_pref_t pref
)
1311 ira_prefs
[pref
->num
] = NULL
;
1312 pref_pool
.remove (pref
);
1315 /* Remove PREF from the list of allocno prefs and free memory for
1318 ira_remove_pref (ira_pref_t pref
)
1320 ira_pref_t cpref
, prev
;
1322 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1323 fprintf (ira_dump_file
, " Removing pref%d:hr%d@%d\n",
1324 pref
->num
, pref
->hard_regno
, pref
->freq
);
1325 for (prev
= NULL
, cpref
= ALLOCNO_PREFS (pref
->allocno
);
1327 prev
= cpref
, cpref
= cpref
->next_pref
)
1330 ira_assert (cpref
!= NULL
);
1332 ALLOCNO_PREFS (pref
->allocno
) = pref
->next_pref
;
1334 prev
->next_pref
= pref
->next_pref
;
1338 /* Remove all prefs of allocno A. */
1340 ira_remove_allocno_prefs (ira_allocno_t a
)
1342 ira_pref_t pref
, next_pref
;
1344 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
1346 next_pref
= pref
->next_pref
;
1349 ALLOCNO_PREFS (a
) = NULL
;
1352 /* Free memory allocated for all prefs. */
1357 ira_pref_iterator pi
;
1359 FOR_EACH_PREF (pref
, pi
)
1361 pref_vec
.release ();
1362 pref_pool
.release ();
1367 /* Pools for copies. */
1368 static pool_allocator
<ira_allocno_copy
> copy_pool ("copies", 100);
1370 /* Vec containing references to all created copies. It is a
1371 container of array ira_copies. */
1372 static vec
<ira_copy_t
> copy_vec
;
1374 /* The function initializes data concerning allocno copies. */
1376 initiate_copies (void)
1378 copy_vec
.create (get_max_uid ());
1383 /* Return copy connecting A1 and A2 and originated from INSN of
1384 LOOP_TREE_NODE if any. */
1386 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx_insn
*insn
,
1387 ira_loop_tree_node_t loop_tree_node
)
1389 ira_copy_t cp
, next_cp
;
1390 ira_allocno_t another_a
;
1392 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
1394 if (cp
->first
== a1
)
1396 next_cp
= cp
->next_first_allocno_copy
;
1397 another_a
= cp
->second
;
1399 else if (cp
->second
== a1
)
1401 next_cp
= cp
->next_second_allocno_copy
;
1402 another_a
= cp
->first
;
1406 if (another_a
== a2
&& cp
->insn
== insn
1407 && cp
->loop_tree_node
== loop_tree_node
)
1413 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1414 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1416 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1417 bool constraint_p
, rtx_insn
*insn
,
1418 ira_loop_tree_node_t loop_tree_node
)
1422 cp
= copy_pool
.allocate ();
1423 cp
->num
= ira_copies_num
;
1425 cp
->second
= second
;
1427 cp
->constraint_p
= constraint_p
;
1429 cp
->loop_tree_node
= loop_tree_node
;
1430 copy_vec
.safe_push (cp
);
1431 ira_copies
= copy_vec
.address ();
1432 ira_copies_num
= copy_vec
.length ();
1436 /* Attach a copy CP to allocnos involved into the copy. */
1438 add_allocno_copy_to_list (ira_copy_t cp
)
1440 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1442 cp
->prev_first_allocno_copy
= NULL
;
1443 cp
->prev_second_allocno_copy
= NULL
;
1444 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
1445 if (cp
->next_first_allocno_copy
!= NULL
)
1447 if (cp
->next_first_allocno_copy
->first
== first
)
1448 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
1450 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1452 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1453 if (cp
->next_second_allocno_copy
!= NULL
)
1455 if (cp
->next_second_allocno_copy
->second
== second
)
1456 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1458 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1460 ALLOCNO_COPIES (first
) = cp
;
1461 ALLOCNO_COPIES (second
) = cp
;
1464 /* Make a copy CP a canonical copy where number of the
1465 first allocno is less than the second one. */
1467 swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1469 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1472 std::swap (cp
->first
, cp
->second
);
1473 std::swap (cp
->prev_first_allocno_copy
, cp
->prev_second_allocno_copy
);
1474 std::swap (cp
->next_first_allocno_copy
, cp
->next_second_allocno_copy
);
1477 /* Create (or update frequency if the copy already exists) and return
1478 the copy of allocnos FIRST and SECOND with frequency FREQ
1479 corresponding to move insn INSN (if any) and originated from
1482 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1483 bool constraint_p
, rtx_insn
*insn
,
1484 ira_loop_tree_node_t loop_tree_node
)
1488 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1493 cp
= ira_create_copy (first
, second
, freq
, constraint_p
, insn
,
1495 ira_assert (first
!= NULL
&& second
!= NULL
);
1496 add_allocno_copy_to_list (cp
);
1497 swap_allocno_copy_ends_if_necessary (cp
);
1501 /* Print info about copy CP into file F. */
1503 print_copy (FILE *f
, ira_copy_t cp
)
1505 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp
->num
,
1506 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1507 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
,
1509 ? "move" : cp
->constraint_p
? "constraint" : "shuffle");
1513 debug (ira_allocno_copy
&ref
)
1515 print_copy (stderr
, &ref
);
1519 debug (ira_allocno_copy
*ptr
)
1524 fprintf (stderr
, "<nil>\n");
1527 /* Print info about copy CP into stderr. */
1529 ira_debug_copy (ira_copy_t cp
)
1531 print_copy (stderr
, cp
);
1534 /* Print info about all copies into file F. */
1536 print_copies (FILE *f
)
1539 ira_copy_iterator ci
;
1541 FOR_EACH_COPY (cp
, ci
)
1545 /* Print info about all copies into stderr. */
1547 ira_debug_copies (void)
1549 print_copies (stderr
);
1552 /* Print info about copies involving allocno A into file F. */
1554 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1556 ira_allocno_t another_a
;
1557 ira_copy_t cp
, next_cp
;
1559 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1560 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1564 next_cp
= cp
->next_first_allocno_copy
;
1565 another_a
= cp
->second
;
1567 else if (cp
->second
== a
)
1569 next_cp
= cp
->next_second_allocno_copy
;
1570 another_a
= cp
->first
;
1574 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1575 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1581 debug (ira_allocno
&ref
)
1583 print_allocno_copies (stderr
, &ref
);
1587 debug (ira_allocno
*ptr
)
1592 fprintf (stderr
, "<nil>\n");
1596 /* Print info about copies involving allocno A into stderr. */
1598 ira_debug_allocno_copies (ira_allocno_t a
)
1600 print_allocno_copies (stderr
, a
);
1603 /* The function frees memory allocated for copy CP. */
1605 finish_copy (ira_copy_t cp
)
1607 copy_pool
.remove (cp
);
1611 /* Free memory allocated for all copies. */
1613 finish_copies (void)
1616 ira_copy_iterator ci
;
1618 FOR_EACH_COPY (cp
, ci
)
1620 copy_vec
.release ();
1621 copy_pool
.release ();
1626 /* Pools for cost vectors. It is defined only for allocno classes. */
1627 static pool_allocator
<int> * cost_vector_pool
[N_REG_CLASSES
];
1629 /* The function initiates work with hard register cost vectors. It
1630 creates allocation pool for each allocno class. */
1632 initiate_cost_vectors (void)
1635 enum reg_class aclass
;
1637 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1639 aclass
= ira_allocno_classes
[i
];
1640 cost_vector_pool
[aclass
] = new pool_allocator
<int>
1641 ("cost vectors", 100,
1642 sizeof (int) * (ira_class_hard_regs_num
[aclass
] - 1));
1646 /* Allocate and return a cost vector VEC for ACLASS. */
1648 ira_allocate_cost_vector (reg_class_t aclass
)
1650 return cost_vector_pool
[(int) aclass
]->allocate ();
1653 /* Free a cost vector VEC for ACLASS. */
1655 ira_free_cost_vector (int *vec
, reg_class_t aclass
)
1657 ira_assert (vec
!= NULL
);
1658 cost_vector_pool
[(int) aclass
]->remove (vec
);
1661 /* Finish work with hard register cost vectors. Release allocation
1662 pool for each allocno class. */
1664 finish_cost_vectors (void)
1667 enum reg_class aclass
;
1669 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1671 aclass
= ira_allocno_classes
[i
];
1672 delete cost_vector_pool
[aclass
];
1678 /* Compute a post-ordering of the reverse control flow of the loop body
1679 designated by the children nodes of LOOP_NODE, whose body nodes in
1680 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1681 of the reverse loop body.
1683 For the post-order of the reverse CFG, we visit the basic blocks in
1684 LOOP_PREORDER array in the reverse order of where they appear.
1685 This is important: We do not just want to compute a post-order of
1686 the reverse CFG, we want to make a best-guess for a visiting order that
1687 minimizes the number of chain elements per allocno live range. If the
1688 blocks would be visited in a different order, we would still compute a
1689 correct post-ordering but it would be less likely that two nodes
1690 connected by an edge in the CFG are neighbours in the topsort. */
1692 static vec
<ira_loop_tree_node_t
>
1693 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED
,
1694 vec
<ira_loop_tree_node_t
> loop_preorder
)
1696 vec
<ira_loop_tree_node_t
> topsort_nodes
= vNULL
;
1697 unsigned int n_loop_preorder
;
1699 n_loop_preorder
= loop_preorder
.length ();
1700 if (n_loop_preorder
!= 0)
1702 ira_loop_tree_node_t subloop_node
;
1704 auto_vec
<ira_loop_tree_node_t
> dfs_stack
;
1706 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1707 the flag to mark blocks we still have to visit to add them to
1708 our post-order. Define an alias to avoid confusion. */
1709 #define BB_TO_VISIT BB_VISITED
1711 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1713 gcc_checking_assert (! (subloop_node
->bb
->flags
& BB_TO_VISIT
));
1714 subloop_node
->bb
->flags
|= BB_TO_VISIT
;
1717 topsort_nodes
.create (n_loop_preorder
);
1718 dfs_stack
.create (n_loop_preorder
);
1720 FOR_EACH_VEC_ELT_REVERSE (loop_preorder
, i
, subloop_node
)
1722 if (! (subloop_node
->bb
->flags
& BB_TO_VISIT
))
1725 subloop_node
->bb
->flags
&= ~BB_TO_VISIT
;
1726 dfs_stack
.quick_push (subloop_node
);
1727 while (! dfs_stack
.is_empty ())
1732 ira_loop_tree_node_t n
= dfs_stack
.last ();
1733 FOR_EACH_EDGE (e
, ei
, n
->bb
->preds
)
1735 ira_loop_tree_node_t pred_node
;
1736 basic_block pred_bb
= e
->src
;
1738 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1741 pred_node
= IRA_BB_NODE_BY_INDEX (pred_bb
->index
);
1743 && (pred_node
->bb
->flags
& BB_TO_VISIT
))
1745 pred_node
->bb
->flags
&= ~BB_TO_VISIT
;
1746 dfs_stack
.quick_push (pred_node
);
1749 if (n
== dfs_stack
.last ())
1752 topsort_nodes
.quick_push (n
);
1760 gcc_assert (topsort_nodes
.length () == n_loop_preorder
);
1761 return topsort_nodes
;
1764 /* The current loop tree node and its regno allocno map. */
1765 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1766 ira_allocno_t
*ira_curr_regno_allocno_map
;
1768 /* This recursive function traverses loop tree with root LOOP_NODE
1769 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1770 correspondingly in preorder and postorder. The function sets up
1771 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1772 basic block nodes of LOOP_NODE is also processed (before its
1775 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1776 the loop are passed in the *reverse* post-order of the *reverse*
1777 CFG. This is only used by ira_create_allocno_live_ranges, which
1778 wants to visit basic blocks in this order to minimize the number
1779 of elements per live range chain.
1780 Note that the loop tree nodes are still visited in the normal,
1781 forward post-order of the loop tree. */
1784 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1785 void (*preorder_func
) (ira_loop_tree_node_t
),
1786 void (*postorder_func
) (ira_loop_tree_node_t
))
1788 ira_loop_tree_node_t subloop_node
;
1790 ira_assert (loop_node
->bb
== NULL
);
1791 ira_curr_loop_tree_node
= loop_node
;
1792 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1794 if (preorder_func
!= NULL
)
1795 (*preorder_func
) (loop_node
);
1799 auto_vec
<ira_loop_tree_node_t
> loop_preorder
;
1802 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1803 is set up such that nodes in the loop body appear in a pre-order
1804 of their place in the CFG. */
1805 for (subloop_node
= loop_node
->children
;
1806 subloop_node
!= NULL
;
1807 subloop_node
= subloop_node
->next
)
1808 if (subloop_node
->bb
!= NULL
)
1809 loop_preorder
.safe_push (subloop_node
);
1811 if (preorder_func
!= NULL
)
1812 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1813 (*preorder_func
) (subloop_node
);
1815 if (postorder_func
!= NULL
)
1817 vec
<ira_loop_tree_node_t
> loop_rev_postorder
=
1818 ira_loop_tree_body_rev_postorder (loop_node
, loop_preorder
);
1819 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder
, i
, subloop_node
)
1820 (*postorder_func
) (subloop_node
);
1821 loop_rev_postorder
.release ();
1825 for (subloop_node
= loop_node
->subloops
;
1826 subloop_node
!= NULL
;
1827 subloop_node
= subloop_node
->subloop_next
)
1829 ira_assert (subloop_node
->bb
== NULL
);
1830 ira_traverse_loop_tree (bb_p
, subloop_node
,
1831 preorder_func
, postorder_func
);
1834 ira_curr_loop_tree_node
= loop_node
;
1835 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1837 if (postorder_func
!= NULL
)
1838 (*postorder_func
) (loop_node
);
1843 /* The basic block currently being processed. */
1844 static basic_block curr_bb
;
1846 /* This recursive function creates allocnos corresponding to
1847 pseudo-registers containing in X. True OUTPUT_P means that X is
1848 an lvalue. PARENT corresponds to the parent expression of X. */
1850 create_insn_allocnos (rtx x
, rtx outer
, bool output_p
)
1854 enum rtx_code code
= GET_CODE (x
);
1860 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1864 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1866 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1867 if (outer
!= NULL
&& GET_CODE (outer
) == SUBREG
)
1869 machine_mode wmode
= GET_MODE (outer
);
1870 if (GET_MODE_SIZE (wmode
) > GET_MODE_SIZE (ALLOCNO_WMODE (a
)))
1871 ALLOCNO_WMODE (a
) = wmode
;
1875 ALLOCNO_NREFS (a
)++;
1876 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1878 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1882 else if (code
== SET
)
1884 create_insn_allocnos (SET_DEST (x
), NULL
, true);
1885 create_insn_allocnos (SET_SRC (x
), NULL
, false);
1888 else if (code
== CLOBBER
)
1890 create_insn_allocnos (XEXP (x
, 0), NULL
, true);
1893 else if (code
== MEM
)
1895 create_insn_allocnos (XEXP (x
, 0), NULL
, false);
1898 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1899 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1901 create_insn_allocnos (XEXP (x
, 0), NULL
, true);
1902 create_insn_allocnos (XEXP (x
, 0), NULL
, false);
1906 fmt
= GET_RTX_FORMAT (code
);
1907 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1910 create_insn_allocnos (XEXP (x
, i
), x
, output_p
);
1911 else if (fmt
[i
] == 'E')
1912 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1913 create_insn_allocnos (XVECEXP (x
, i
, j
), x
, output_p
);
1917 /* Create allocnos corresponding to pseudo-registers living in the
1918 basic block represented by the corresponding loop tree node
1921 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1928 curr_bb
= bb
= bb_node
->bb
;
1929 ira_assert (bb
!= NULL
);
1930 FOR_BB_INSNS_REVERSE (bb
, insn
)
1931 if (NONDEBUG_INSN_P (insn
))
1932 create_insn_allocnos (PATTERN (insn
), NULL
, false);
1933 /* It might be a allocno living through from one subloop to
1935 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1936 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1937 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1940 /* Create allocnos corresponding to pseudo-registers living on edge E
1941 (a loop entry or exit). Also mark the allocnos as living on the
1944 create_loop_allocnos (edge e
)
1947 bitmap live_in_regs
, border_allocnos
;
1949 ira_loop_tree_node_t parent
;
1951 live_in_regs
= df_get_live_in (e
->dest
);
1952 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1953 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e
->src
),
1954 FIRST_PSEUDO_REGISTER
, i
, bi
)
1955 if (bitmap_bit_p (live_in_regs
, i
))
1957 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1959 /* The order of creations is important for right
1960 ira_regno_allocno_map. */
1961 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1962 && parent
->regno_allocno_map
[i
] == NULL
)
1963 ira_create_allocno (i
, false, parent
);
1964 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1966 bitmap_set_bit (border_allocnos
,
1967 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1971 /* Create allocnos corresponding to pseudo-registers living in loop
1972 represented by the corresponding loop tree node LOOP_NODE. This
1973 function is called by ira_traverse_loop_tree. */
1975 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1977 if (loop_node
->bb
!= NULL
)
1978 create_bb_allocnos (loop_node
);
1979 else if (loop_node
!= ira_loop_tree_root
)
1986 ira_assert (current_loops
!= NULL
);
1987 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1988 if (e
->src
!= loop_node
->loop
->latch
)
1989 create_loop_allocnos (e
);
1991 edges
= get_loop_exit_edges (loop_node
->loop
);
1992 FOR_EACH_VEC_ELT (edges
, i
, e
)
1993 create_loop_allocnos (e
);
1998 /* Propagate information about allocnos modified inside the loop given
1999 by its LOOP_TREE_NODE to its parent. */
2001 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
2003 if (loop_tree_node
== ira_loop_tree_root
)
2005 ira_assert (loop_tree_node
->bb
== NULL
);
2006 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
2007 loop_tree_node
->modified_regnos
);
2010 /* Propagate new info about allocno A (see comments about accumulated
2011 info in allocno definition) to the corresponding allocno on upper
2012 loop tree level. So allocnos on upper levels accumulate
2013 information about the corresponding allocnos in nested regions.
2014 The new info means allocno info finally calculated in this
2017 propagate_allocno_info (void)
2020 ira_allocno_t a
, parent_a
;
2021 ira_loop_tree_node_t parent
;
2022 enum reg_class aclass
;
2024 if (flag_ira_region
!= IRA_REGION_ALL
2025 && flag_ira_region
!= IRA_REGION_MIXED
)
2027 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2028 for (a
= ira_regno_allocno_map
[i
];
2030 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2031 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
2032 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
2033 /* There are no caps yet at this point. So use
2034 border_allocnos to find allocnos for the propagation. */
2035 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
2038 if (! ALLOCNO_BAD_SPILL_P (a
))
2039 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
2040 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
2041 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
2042 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
2043 merge_hard_reg_conflicts (a
, parent_a
, true);
2044 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2045 += ALLOCNO_CALLS_CROSSED_NUM (a
);
2046 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
2047 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
2048 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a
),
2049 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
2050 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
2051 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
2052 aclass
= ALLOCNO_CLASS (a
);
2053 ira_assert (aclass
== ALLOCNO_CLASS (parent_a
));
2054 ira_allocate_and_accumulate_costs
2055 (&ALLOCNO_HARD_REG_COSTS (parent_a
), aclass
,
2056 ALLOCNO_HARD_REG_COSTS (a
));
2057 ira_allocate_and_accumulate_costs
2058 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
),
2060 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
2061 ALLOCNO_CLASS_COST (parent_a
)
2062 += ALLOCNO_CLASS_COST (a
);
2063 ALLOCNO_MEMORY_COST (parent_a
) += ALLOCNO_MEMORY_COST (a
);
2067 /* Create allocnos corresponding to pseudo-registers in the current
2068 function. Traverse the loop tree for this. */
2070 create_allocnos (void)
2072 /* We need to process BB first to correctly link allocnos by member
2073 next_regno_allocno. */
2074 ira_traverse_loop_tree (true, ira_loop_tree_root
,
2075 create_loop_tree_node_allocnos
, NULL
);
2077 ira_traverse_loop_tree (false, ira_loop_tree_root
, NULL
,
2078 propagate_modified_regnos
);
2083 /* The page contains function to remove some regions from a separate
2084 register allocation. We remove regions whose separate allocation
2085 will hardly improve the result. As a result we speed up regional
2086 register allocation. */
2088 /* The function changes the object in range list given by R to OBJ. */
2090 change_object_in_range_list (live_range_t r
, ira_object_t obj
)
2092 for (; r
!= NULL
; r
= r
->next
)
2096 /* Move all live ranges associated with allocno FROM to allocno TO. */
2098 move_allocno_live_ranges (ira_allocno_t from
, ira_allocno_t to
)
2101 int n
= ALLOCNO_NUM_OBJECTS (from
);
2103 gcc_assert (n
== ALLOCNO_NUM_OBJECTS (to
));
2105 for (i
= 0; i
< n
; i
++)
2107 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
2108 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
2109 live_range_t lr
= OBJECT_LIVE_RANGES (from_obj
);
2111 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2113 fprintf (ira_dump_file
,
2114 " Moving ranges of a%dr%d to a%dr%d: ",
2115 ALLOCNO_NUM (from
), ALLOCNO_REGNO (from
),
2116 ALLOCNO_NUM (to
), ALLOCNO_REGNO (to
));
2117 ira_print_live_range_list (ira_dump_file
, lr
);
2119 change_object_in_range_list (lr
, to_obj
);
2120 OBJECT_LIVE_RANGES (to_obj
)
2121 = ira_merge_live_ranges (lr
, OBJECT_LIVE_RANGES (to_obj
));
2122 OBJECT_LIVE_RANGES (from_obj
) = NULL
;
2127 copy_allocno_live_ranges (ira_allocno_t from
, ira_allocno_t to
)
2130 int n
= ALLOCNO_NUM_OBJECTS (from
);
2132 gcc_assert (n
== ALLOCNO_NUM_OBJECTS (to
));
2134 for (i
= 0; i
< n
; i
++)
2136 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
2137 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
2138 live_range_t lr
= OBJECT_LIVE_RANGES (from_obj
);
2140 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
2142 fprintf (ira_dump_file
, " Copying ranges of a%dr%d to a%dr%d: ",
2143 ALLOCNO_NUM (from
), ALLOCNO_REGNO (from
),
2144 ALLOCNO_NUM (to
), ALLOCNO_REGNO (to
));
2145 ira_print_live_range_list (ira_dump_file
, lr
);
2147 lr
= ira_copy_live_range_list (lr
);
2148 change_object_in_range_list (lr
, to_obj
);
2149 OBJECT_LIVE_RANGES (to_obj
)
2150 = ira_merge_live_ranges (lr
, OBJECT_LIVE_RANGES (to_obj
));
2154 /* Return TRUE if NODE represents a loop with low register
2157 low_pressure_loop_node_p (ira_loop_tree_node_t node
)
2160 enum reg_class pclass
;
2162 if (node
->bb
!= NULL
)
2165 for (i
= 0; i
< ira_pressure_classes_num
; i
++)
2167 pclass
= ira_pressure_classes
[i
];
2168 if (node
->reg_pressure
[pclass
] > ira_class_hard_regs_num
[pclass
]
2169 && ira_class_hard_regs_num
[pclass
] > 1)
2176 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2177 form a region from such loop if the target use stack register
2178 because reg-stack.c can not deal with such edges. */
2180 loop_with_complex_edge_p (struct loop
*loop
)
2188 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
2189 if (e
->flags
& EDGE_EH
)
2191 edges
= get_loop_exit_edges (loop
);
2193 FOR_EACH_VEC_ELT (edges
, i
, e
)
2194 if (e
->flags
& EDGE_COMPLEX
)
2204 /* Sort loops for marking them for removal. We put already marked
2205 loops first, then less frequent loops next, and then outer loops
2208 loop_compare_func (const void *v1p
, const void *v2p
)
2211 ira_loop_tree_node_t l1
= *(const ira_loop_tree_node_t
*) v1p
;
2212 ira_loop_tree_node_t l2
= *(const ira_loop_tree_node_t
*) v2p
;
2214 ira_assert (l1
->parent
!= NULL
&& l2
->parent
!= NULL
);
2215 if (l1
->to_remove_p
&& ! l2
->to_remove_p
)
2217 if (! l1
->to_remove_p
&& l2
->to_remove_p
)
2219 if ((diff
= l1
->loop
->header
->frequency
- l2
->loop
->header
->frequency
) != 0)
2221 if ((diff
= (int) loop_depth (l1
->loop
) - (int) loop_depth (l2
->loop
)) != 0)
2223 /* Make sorting stable. */
2224 return l1
->loop_num
- l2
->loop_num
;
2227 /* Mark loops which should be removed from regional allocation. We
2228 remove a loop with low register pressure inside another loop with
2229 register pressure. In this case a separate allocation of the loop
2230 hardly helps (for irregular register file architecture it could
2231 help by choosing a better hard register in the loop but we prefer
2232 faster allocation even in this case). We also remove cheap loops
2233 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH
2234 exit or enter edges are removed too because the allocation might
2235 require put pseudo moves on the EH edges (we could still do this
2236 for pseudos with caller saved hard registers in some cases but it
2237 is impossible to say here or during top-down allocation pass what
2238 hard register the pseudos get finally). */
2240 mark_loops_for_removal (void)
2243 ira_loop_tree_node_t
*sorted_loops
;
2246 ira_assert (current_loops
!= NULL
);
2248 = (ira_loop_tree_node_t
*) ira_allocate (sizeof (ira_loop_tree_node_t
)
2249 * number_of_loops (cfun
));
2250 for (n
= i
= 0; vec_safe_iterate (get_loops (cfun
), i
, &loop
); i
++)
2251 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
2253 if (ira_loop_nodes
[i
].parent
== NULL
)
2255 /* Don't remove the root. */
2256 ira_loop_nodes
[i
].to_remove_p
= false;
2259 sorted_loops
[n
++] = &ira_loop_nodes
[i
];
2260 ira_loop_nodes
[i
].to_remove_p
2261 = ((low_pressure_loop_node_p (ira_loop_nodes
[i
].parent
)
2262 && low_pressure_loop_node_p (&ira_loop_nodes
[i
]))
2264 || loop_with_complex_edge_p (ira_loop_nodes
[i
].loop
)
2268 qsort (sorted_loops
, n
, sizeof (ira_loop_tree_node_t
), loop_compare_func
);
2269 for (i
= 0; n
- i
+ 1 > IRA_MAX_LOOPS_NUM
; i
++)
2271 sorted_loops
[i
]->to_remove_p
= true;
2272 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2275 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2276 sorted_loops
[i
]->loop_num
, sorted_loops
[i
]->loop
->header
->index
,
2277 sorted_loops
[i
]->loop
->header
->frequency
,
2278 loop_depth (sorted_loops
[i
]->loop
),
2279 low_pressure_loop_node_p (sorted_loops
[i
]->parent
)
2280 && low_pressure_loop_node_p (sorted_loops
[i
])
2281 ? "low pressure" : "cheap loop");
2283 ira_free (sorted_loops
);
2286 /* Mark all loops but root for removing. */
2288 mark_all_loops_for_removal (void)
2293 ira_assert (current_loops
!= NULL
);
2294 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
2295 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
2297 if (ira_loop_nodes
[i
].parent
== NULL
)
2299 /* Don't remove the root. */
2300 ira_loop_nodes
[i
].to_remove_p
= false;
2303 ira_loop_nodes
[i
].to_remove_p
= true;
2304 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2307 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2308 ira_loop_nodes
[i
].loop_num
,
2309 ira_loop_nodes
[i
].loop
->header
->index
,
2310 ira_loop_nodes
[i
].loop
->header
->frequency
,
2311 loop_depth (ira_loop_nodes
[i
].loop
));
2315 /* Definition of vector of loop tree nodes. */
2317 /* Vec containing references to all removed loop tree nodes. */
2318 static vec
<ira_loop_tree_node_t
> removed_loop_vec
;
2320 /* Vec containing references to all children of loop tree nodes. */
2321 static vec
<ira_loop_tree_node_t
> children_vec
;
2323 /* Remove subregions of NODE if their separate allocation will not
2324 improve the result. */
2326 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node
)
2330 ira_loop_tree_node_t subnode
;
2332 remove_p
= node
->to_remove_p
;
2334 children_vec
.safe_push (node
);
2335 start
= children_vec
.length ();
2336 for (subnode
= node
->children
; subnode
!= NULL
; subnode
= subnode
->next
)
2337 if (subnode
->bb
== NULL
)
2338 remove_uneccesary_loop_nodes_from_loop_tree (subnode
);
2340 children_vec
.safe_push (subnode
);
2341 node
->children
= node
->subloops
= NULL
;
2344 removed_loop_vec
.safe_push (node
);
2347 while (children_vec
.length () > start
)
2349 subnode
= children_vec
.pop ();
2350 subnode
->parent
= node
;
2351 subnode
->next
= node
->children
;
2352 node
->children
= subnode
;
2353 if (subnode
->bb
== NULL
)
2355 subnode
->subloop_next
= node
->subloops
;
2356 node
->subloops
= subnode
;
2361 /* Return TRUE if NODE is inside PARENT. */
2363 loop_is_inside_p (ira_loop_tree_node_t node
, ira_loop_tree_node_t parent
)
2365 for (node
= node
->parent
; node
!= NULL
; node
= node
->parent
)
2371 /* Sort allocnos according to their order in regno allocno list. */
2373 regno_allocno_order_compare_func (const void *v1p
, const void *v2p
)
2375 ira_allocno_t a1
= *(const ira_allocno_t
*) v1p
;
2376 ira_allocno_t a2
= *(const ira_allocno_t
*) v2p
;
2377 ira_loop_tree_node_t n1
= ALLOCNO_LOOP_TREE_NODE (a1
);
2378 ira_loop_tree_node_t n2
= ALLOCNO_LOOP_TREE_NODE (a2
);
2380 if (loop_is_inside_p (n1
, n2
))
2382 else if (loop_is_inside_p (n2
, n1
))
2384 /* If allocnos are equally good, sort by allocno numbers, so that
2385 the results of qsort leave nothing to chance. We put allocnos
2386 with higher number first in the list because it is the original
2387 order for allocnos from loops on the same levels. */
2388 return ALLOCNO_NUM (a2
) - ALLOCNO_NUM (a1
);
2391 /* This array is used to sort allocnos to restore allocno order in
2392 the regno allocno list. */
2393 static ira_allocno_t
*regno_allocnos
;
2395 /* Restore allocno order for REGNO in the regno allocno list. */
2397 ira_rebuild_regno_allocno_list (int regno
)
2402 for (n
= 0, a
= ira_regno_allocno_map
[regno
];
2404 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2405 regno_allocnos
[n
++] = a
;
2407 qsort (regno_allocnos
, n
, sizeof (ira_allocno_t
),
2408 regno_allocno_order_compare_func
);
2409 for (i
= 1; i
< n
; i
++)
2410 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[i
- 1]) = regno_allocnos
[i
];
2411 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos
[n
- 1]) = NULL
;
2412 ira_regno_allocno_map
[regno
] = regno_allocnos
[0];
2413 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
2414 fprintf (ira_dump_file
, " Rebuilding regno allocno list for %d\n", regno
);
2417 /* Propagate info from allocno FROM_A to allocno A. */
2419 propagate_some_info_from_allocno (ira_allocno_t a
, ira_allocno_t from_a
)
2421 enum reg_class aclass
;
2423 merge_hard_reg_conflicts (from_a
, a
, false);
2424 ALLOCNO_NREFS (a
) += ALLOCNO_NREFS (from_a
);
2425 ALLOCNO_FREQ (a
) += ALLOCNO_FREQ (from_a
);
2426 ALLOCNO_CALL_FREQ (a
) += ALLOCNO_CALL_FREQ (from_a
);
2427 ALLOCNO_CALLS_CROSSED_NUM (a
) += ALLOCNO_CALLS_CROSSED_NUM (from_a
);
2428 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
)
2429 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a
);
2430 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
),
2431 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a
));
2433 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2434 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a
);
2435 if (! ALLOCNO_BAD_SPILL_P (from_a
))
2436 ALLOCNO_BAD_SPILL_P (a
) = false;
2437 aclass
= ALLOCNO_CLASS (from_a
);
2438 ira_assert (aclass
== ALLOCNO_CLASS (a
));
2439 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a
), aclass
,
2440 ALLOCNO_HARD_REG_COSTS (from_a
));
2441 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
2443 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a
));
2444 ALLOCNO_CLASS_COST (a
) += ALLOCNO_CLASS_COST (from_a
);
2445 ALLOCNO_MEMORY_COST (a
) += ALLOCNO_MEMORY_COST (from_a
);
2448 /* Remove allocnos from loops removed from the allocation
2451 remove_unnecessary_allocnos (void)
2454 bool merged_p
, rebuild_p
;
2455 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
2456 ira_loop_tree_node_t a_node
, parent
;
2459 regno_allocnos
= NULL
;
2460 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
2463 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
2467 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
2468 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2469 if (! a_node
->to_remove_p
)
2473 for (parent
= a_node
->parent
;
2474 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2475 && parent
->to_remove_p
;
2476 parent
= parent
->parent
)
2478 if (parent_a
== NULL
)
2480 /* There are no allocnos with the same regno in
2481 upper region -- just move the allocno to the
2484 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
2485 parent
->regno_allocno_map
[regno
] = a
;
2486 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
2491 /* Remove the allocno and update info of allocno in
2492 the upper region. */
2494 ira_regno_allocno_map
[regno
] = next_a
;
2496 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
2497 move_allocno_live_ranges (a
, parent_a
);
2499 propagate_some_info_from_allocno (parent_a
, a
);
2500 /* Remove it from the corresponding regno allocno
2501 map to avoid info propagation of subsequent
2502 allocno into this already removed allocno. */
2503 a_node
->regno_allocno_map
[regno
] = NULL
;
2504 ira_remove_allocno_prefs (a
);
2510 /* We need to restore the order in regno allocno list. */
2512 if (regno_allocnos
== NULL
)
2514 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2515 * ira_allocnos_num
);
2516 ira_rebuild_regno_allocno_list (regno
);
2520 ira_rebuild_start_finish_chains ();
2521 if (regno_allocnos
!= NULL
)
2522 ira_free (regno_allocnos
);
2525 /* Remove allocnos from all loops but the root. */
2527 remove_low_level_allocnos (void)
2530 bool merged_p
, propagate_p
;
2531 ira_allocno_t a
, top_a
;
2532 ira_loop_tree_node_t a_node
, parent
;
2533 ira_allocno_iterator ai
;
2536 FOR_EACH_ALLOCNO (a
, ai
)
2538 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2539 if (a_node
== ira_loop_tree_root
|| ALLOCNO_CAP_MEMBER (a
) != NULL
)
2541 regno
= ALLOCNO_REGNO (a
);
2542 if ((top_a
= ira_loop_tree_root
->regno_allocno_map
[regno
]) == NULL
)
2544 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2545 ira_loop_tree_root
->regno_allocno_map
[regno
] = a
;
2548 propagate_p
= a_node
->parent
->regno_allocno_map
[regno
] == NULL
;
2549 /* Remove the allocno and update info of allocno in the upper
2551 move_allocno_live_ranges (a
, top_a
);
2554 propagate_some_info_from_allocno (top_a
, a
);
2556 FOR_EACH_ALLOCNO (a
, ai
)
2558 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2559 if (a_node
== ira_loop_tree_root
)
2561 parent
= a_node
->parent
;
2562 regno
= ALLOCNO_REGNO (a
);
2563 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2564 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2565 else if (ALLOCNO_CAP (a
) == NULL
)
2566 ira_assert (parent
->regno_allocno_map
[regno
] != NULL
);
2568 FOR_EACH_ALLOCNO (a
, ai
)
2570 regno
= ALLOCNO_REGNO (a
);
2571 if (ira_loop_tree_root
->regno_allocno_map
[regno
] == a
)
2574 ira_allocno_object_iterator oi
;
2576 ira_regno_allocno_map
[regno
] = a
;
2577 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = NULL
;
2578 ALLOCNO_CAP_MEMBER (a
) = NULL
;
2579 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2580 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
2581 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
2583 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2584 ALLOCNO_NO_STACK_REG_P (a
) = true;
2589 ira_remove_allocno_prefs (a
);
2594 ira_rebuild_start_finish_chains ();
2597 /* Remove loops from consideration. We remove all loops except for
2598 root if ALL_P or loops for which a separate allocation will not
2599 improve the result. We have to do this after allocno creation and
2600 their costs and allocno class evaluation because only after that
2601 the register pressure can be known and is calculated. */
2603 remove_unnecessary_regions (bool all_p
)
2605 if (current_loops
== NULL
)
2608 mark_all_loops_for_removal ();
2610 mark_loops_for_removal ();
2611 children_vec
.create (last_basic_block_for_fn (cfun
)
2612 + number_of_loops (cfun
));
2613 removed_loop_vec
.create (last_basic_block_for_fn (cfun
)
2614 + number_of_loops (cfun
));
2615 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
);
2616 children_vec
.release ();
2618 remove_low_level_allocnos ();
2620 remove_unnecessary_allocnos ();
2621 while (removed_loop_vec
.length () > 0)
2622 finish_loop_tree_node (removed_loop_vec
.pop ());
2623 removed_loop_vec
.release ();
2628 /* At this point true value of allocno attribute bad_spill_p means
2629 that there is an insn where allocno occurs and where the allocno
2630 can not be used as memory. The function updates the attribute, now
2631 it can be true only for allocnos which can not be used as memory in
2632 an insn and in whose live ranges there is other allocno deaths.
2633 Spilling allocnos with true value will not improve the code because
2634 it will not make other allocnos colorable and additional reloads
2635 for the corresponding pseudo will be generated in reload pass for
2636 each insn it occurs.
2638 This is a trick mentioned in one classic article of Chaitin etc
2639 which is frequently omitted in other implementations of RA based on
2642 update_bad_spill_attribute (void)
2646 ira_allocno_iterator ai
;
2647 ira_allocno_object_iterator aoi
;
2650 enum reg_class aclass
;
2651 bitmap_head dead_points
[N_REG_CLASSES
];
2653 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2655 aclass
= ira_allocno_classes
[i
];
2656 bitmap_initialize (&dead_points
[aclass
], ®_obstack
);
2658 FOR_EACH_ALLOCNO (a
, ai
)
2660 aclass
= ALLOCNO_CLASS (a
);
2661 if (aclass
== NO_REGS
)
2663 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2664 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2665 bitmap_set_bit (&dead_points
[aclass
], r
->finish
);
2667 FOR_EACH_ALLOCNO (a
, ai
)
2669 aclass
= ALLOCNO_CLASS (a
);
2670 if (aclass
== NO_REGS
)
2672 if (! ALLOCNO_BAD_SPILL_P (a
))
2674 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2676 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2678 for (i
= r
->start
+ 1; i
< r
->finish
; i
++)
2679 if (bitmap_bit_p (&dead_points
[aclass
], i
))
2686 ALLOCNO_BAD_SPILL_P (a
) = false;
2691 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2693 aclass
= ira_allocno_classes
[i
];
2694 bitmap_clear (&dead_points
[aclass
]);
2700 /* Set up minimal and maximal live range points for allocnos. */
2702 setup_min_max_allocno_live_range_point (void)
2705 ira_allocno_t a
, parent_a
, cap
;
2706 ira_allocno_iterator ai
;
2707 #ifdef ENABLE_IRA_CHECKING
2708 ira_object_iterator oi
;
2712 ira_loop_tree_node_t parent
;
2714 FOR_EACH_ALLOCNO (a
, ai
)
2716 int n
= ALLOCNO_NUM_OBJECTS (a
);
2718 for (i
= 0; i
< n
; i
++)
2720 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2721 r
= OBJECT_LIVE_RANGES (obj
);
2724 OBJECT_MAX (obj
) = r
->finish
;
2725 for (; r
->next
!= NULL
; r
= r
->next
)
2727 OBJECT_MIN (obj
) = r
->start
;
2730 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2731 for (a
= ira_regno_allocno_map
[i
];
2733 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2736 int n
= ALLOCNO_NUM_OBJECTS (a
);
2738 for (j
= 0; j
< n
; j
++)
2740 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
2741 ira_object_t parent_obj
;
2743 if (OBJECT_MAX (obj
) < 0)
2745 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2746 /* Accumulation of range info. */
2747 if (ALLOCNO_CAP (a
) != NULL
)
2749 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
2751 ira_object_t cap_obj
= ALLOCNO_OBJECT (cap
, j
);
2752 if (OBJECT_MAX (cap_obj
) < OBJECT_MAX (obj
))
2753 OBJECT_MAX (cap_obj
) = OBJECT_MAX (obj
);
2754 if (OBJECT_MIN (cap_obj
) > OBJECT_MIN (obj
))
2755 OBJECT_MIN (cap_obj
) = OBJECT_MIN (obj
);
2759 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
2761 parent_a
= parent
->regno_allocno_map
[i
];
2762 parent_obj
= ALLOCNO_OBJECT (parent_a
, j
);
2763 if (OBJECT_MAX (parent_obj
) < OBJECT_MAX (obj
))
2764 OBJECT_MAX (parent_obj
) = OBJECT_MAX (obj
);
2765 if (OBJECT_MIN (parent_obj
) > OBJECT_MIN (obj
))
2766 OBJECT_MIN (parent_obj
) = OBJECT_MIN (obj
);
2769 #ifdef ENABLE_IRA_CHECKING
2770 FOR_EACH_OBJECT (obj
, oi
)
2772 if ((0 <= OBJECT_MIN (obj
) && OBJECT_MIN (obj
) <= ira_max_point
)
2773 && (0 <= OBJECT_MAX (obj
) && OBJECT_MAX (obj
) <= ira_max_point
))
2780 /* Sort allocnos according to their live ranges. Allocnos with
2781 smaller allocno class are put first unless we use priority
2782 coloring. Allocnos with the same class are ordered according
2783 their start (min). Allocnos with the same start are ordered
2784 according their finish (max). */
2786 object_range_compare_func (const void *v1p
, const void *v2p
)
2789 ira_object_t obj1
= *(const ira_object_t
*) v1p
;
2790 ira_object_t obj2
= *(const ira_object_t
*) v2p
;
2791 ira_allocno_t a1
= OBJECT_ALLOCNO (obj1
);
2792 ira_allocno_t a2
= OBJECT_ALLOCNO (obj2
);
2794 if ((diff
= OBJECT_MIN (obj1
) - OBJECT_MIN (obj2
)) != 0)
2796 if ((diff
= OBJECT_MAX (obj1
) - OBJECT_MAX (obj2
)) != 0)
2798 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2801 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2803 sort_conflict_id_map (void)
2807 ira_allocno_iterator ai
;
2810 FOR_EACH_ALLOCNO (a
, ai
)
2812 ira_allocno_object_iterator oi
;
2815 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2816 ira_object_id_map
[num
++] = obj
;
2819 qsort (ira_object_id_map
, num
, sizeof (ira_object_t
),
2820 object_range_compare_func
);
2821 for (i
= 0; i
< num
; i
++)
2823 ira_object_t obj
= ira_object_id_map
[i
];
2825 gcc_assert (obj
!= NULL
);
2826 OBJECT_CONFLICT_ID (obj
) = i
;
2828 for (i
= num
; i
< ira_objects_num
; i
++)
2829 ira_object_id_map
[i
] = NULL
;
2832 /* Set up minimal and maximal conflict ids of allocnos with which
2833 given allocno can conflict. */
2835 setup_min_max_conflict_allocno_ids (void)
2838 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
2839 int *live_range_min
, *last_lived
;
2840 int word0_min
, word0_max
;
2842 ira_allocno_iterator ai
;
2844 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
2846 first_not_finished
= -1;
2847 for (i
= 0; i
< ira_objects_num
; i
++)
2849 ira_object_t obj
= ira_object_id_map
[i
];
2854 a
= OBJECT_ALLOCNO (obj
);
2858 aclass
= ALLOCNO_CLASS (a
);
2860 first_not_finished
= i
;
2864 start
= OBJECT_MIN (obj
);
2865 /* If we skip an allocno, the allocno with smaller ids will
2866 be also skipped because of the secondary sorting the
2867 range finishes (see function
2868 object_range_compare_func). */
2869 while (first_not_finished
< i
2870 && start
> OBJECT_MAX (ira_object_id_map
2871 [first_not_finished
]))
2872 first_not_finished
++;
2873 min
= first_not_finished
;
2876 /* We could increase min further in this case but it is good
2879 live_range_min
[i
] = OBJECT_MIN (obj
);
2880 OBJECT_MIN (obj
) = min
;
2882 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
2884 filled_area_start
= -1;
2885 for (i
= ira_objects_num
- 1; i
>= 0; i
--)
2887 ira_object_t obj
= ira_object_id_map
[i
];
2892 a
= OBJECT_ALLOCNO (obj
);
2895 aclass
= ALLOCNO_CLASS (a
);
2896 for (j
= 0; j
< ira_max_point
; j
++)
2898 filled_area_start
= ira_max_point
;
2900 min
= live_range_min
[i
];
2901 finish
= OBJECT_MAX (obj
);
2902 max
= last_lived
[finish
];
2904 /* We could decrease max further in this case but it is good
2906 max
= OBJECT_CONFLICT_ID (obj
) - 1;
2907 OBJECT_MAX (obj
) = max
;
2908 /* In filling, we can go further A range finish to recognize
2909 intersection quickly because if the finish of subsequently
2910 processed allocno (it has smaller conflict id) range is
2911 further A range finish than they are definitely intersected
2912 (the reason for this is the allocnos with bigger conflict id
2913 have their range starts not smaller than allocnos with
2915 for (j
= min
; j
< filled_area_start
; j
++)
2917 filled_area_start
= min
;
2919 ira_free (last_lived
);
2920 ira_free (live_range_min
);
2922 /* For allocnos with more than one object, we may later record extra conflicts in
2923 subobject 0 that we cannot really know about here.
2924 For now, simply widen the min/max range of these subobjects. */
2926 word0_min
= INT_MAX
;
2927 word0_max
= INT_MIN
;
2929 FOR_EACH_ALLOCNO (a
, ai
)
2931 int n
= ALLOCNO_NUM_OBJECTS (a
);
2936 obj0
= ALLOCNO_OBJECT (a
, 0);
2937 if (OBJECT_CONFLICT_ID (obj0
) < word0_min
)
2938 word0_min
= OBJECT_CONFLICT_ID (obj0
);
2939 if (OBJECT_CONFLICT_ID (obj0
) > word0_max
)
2940 word0_max
= OBJECT_CONFLICT_ID (obj0
);
2942 FOR_EACH_ALLOCNO (a
, ai
)
2944 int n
= ALLOCNO_NUM_OBJECTS (a
);
2949 obj0
= ALLOCNO_OBJECT (a
, 0);
2950 if (OBJECT_MIN (obj0
) > word0_min
)
2951 OBJECT_MIN (obj0
) = word0_min
;
2952 if (OBJECT_MAX (obj0
) < word0_max
)
2953 OBJECT_MAX (obj0
) = word0_max
;
2963 ira_allocno_iterator ai
;
2964 ira_loop_tree_node_t loop_tree_node
;
2966 FOR_EACH_ALLOCNO (a
, ai
)
2968 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2970 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2971 create_cap_allocno (a
);
2972 else if (ALLOCNO_CAP (a
) == NULL
)
2974 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2975 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2976 create_cap_allocno (a
);
2983 /* The page contains code transforming more one region internal
2984 representation (IR) to one region IR which is necessary for reload.
2985 This transformation is called IR flattening. We might just rebuild
2986 the IR for one region but we don't do it because it takes a lot of
2989 /* Map: regno -> allocnos which will finally represent the regno for
2990 IR with one region. */
2991 static ira_allocno_t
*regno_top_level_allocno_map
;
2993 /* Find the allocno that corresponds to A at a level one higher up in the
2994 loop tree. Returns NULL if A is a cap, or if it has no parent. */
2996 ira_parent_allocno (ira_allocno_t a
)
2998 ira_loop_tree_node_t parent
;
3000 if (ALLOCNO_CAP (a
) != NULL
)
3003 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3007 return parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)];
3010 /* Find the allocno that corresponds to A at a level one higher up in the
3011 loop tree. If ALLOCNO_CAP is set for A, return that. */
3013 ira_parent_or_cap_allocno (ira_allocno_t a
)
3015 if (ALLOCNO_CAP (a
) != NULL
)
3016 return ALLOCNO_CAP (a
);
3018 return ira_parent_allocno (a
);
3021 /* Process all allocnos originated from pseudo REGNO and copy live
3022 ranges, hard reg conflicts, and allocno stack reg attributes from
3023 low level allocnos to final allocnos which are destinations of
3024 removed stores at a loop exit. Return true if we copied live
3027 copy_info_to_removed_store_destinations (int regno
)
3030 ira_allocno_t parent_a
= NULL
;
3031 ira_loop_tree_node_t parent
;
3035 for (a
= ira_regno_allocno_map
[regno
];
3037 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3039 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))])
3040 /* This allocno will be removed. */
3043 /* Caps will be removed. */
3044 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3045 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3047 parent
= parent
->parent
)
3048 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
3050 == regno_top_level_allocno_map
[REGNO
3051 (allocno_emit_reg (parent_a
))]
3052 && ALLOCNO_EMIT_DATA (parent_a
)->mem_optimized_dest_p
))
3054 if (parent
== NULL
|| parent_a
== NULL
)
3057 copy_allocno_live_ranges (a
, parent_a
);
3058 merge_hard_reg_conflicts (a
, parent_a
, true);
3060 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
3061 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3062 += ALLOCNO_CALLS_CROSSED_NUM (a
);
3063 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3064 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3065 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a
),
3066 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a
));
3067 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3068 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3074 /* Flatten the IR. In other words, this function transforms IR as if
3075 it were built with one region (without loops). We could make it
3076 much simpler by rebuilding IR with one region, but unfortunately it
3077 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3078 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3079 IRA_MAX_POINT before emitting insns on the loop borders. */
3081 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
3086 bool new_pseudos_p
, merged_p
, mem_dest_p
;
3088 enum reg_class aclass
;
3089 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
3091 ira_loop_tree_node_t node
;
3093 ira_allocno_iterator ai
;
3094 ira_copy_iterator ci
;
3096 regno_top_level_allocno_map
3097 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
3098 * sizeof (ira_allocno_t
));
3099 memset (regno_top_level_allocno_map
, 0,
3100 max_reg_num () * sizeof (ira_allocno_t
));
3101 new_pseudos_p
= merged_p
= false;
3102 FOR_EACH_ALLOCNO (a
, ai
)
3104 ira_allocno_object_iterator oi
;
3107 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3108 /* Caps are not in the regno allocno maps and they are never
3109 will be transformed into allocnos existing after IR
3112 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3113 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
3114 OBJECT_CONFLICT_HARD_REGS (obj
));
3116 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
3119 /* Fix final allocno attributes. */
3120 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
3123 for (a
= ira_regno_allocno_map
[i
];
3125 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3127 ira_emit_data_t parent_data
, data
= ALLOCNO_EMIT_DATA (a
);
3129 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3130 if (data
->somewhere_renamed_p
)
3131 new_pseudos_p
= true;
3132 parent_a
= ira_parent_allocno (a
);
3133 if (parent_a
== NULL
)
3135 ALLOCNO_COPIES (a
) = NULL
;
3136 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3139 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
3141 if (data
->mem_optimized_dest
!= NULL
)
3143 parent_data
= ALLOCNO_EMIT_DATA (parent_a
);
3144 if (REGNO (data
->reg
) == REGNO (parent_data
->reg
))
3146 merge_hard_reg_conflicts (a
, parent_a
, true);
3147 move_allocno_live_ranges (a
, parent_a
);
3149 parent_data
->mem_optimized_dest_p
3150 = (parent_data
->mem_optimized_dest_p
3151 || data
->mem_optimized_dest_p
);
3154 new_pseudos_p
= true;
3157 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
3158 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
3159 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
3160 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3161 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
3162 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3163 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3164 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3165 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3166 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
3167 && ALLOCNO_NREFS (parent_a
) >= 0
3168 && ALLOCNO_FREQ (parent_a
) >= 0);
3169 aclass
= ALLOCNO_CLASS (parent_a
);
3170 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
3171 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
3172 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
3173 for (j
= 0; j
< hard_regs_num
; j
++)
3174 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
3175 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
3176 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
3177 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
3178 for (j
= 0; j
< hard_regs_num
; j
++)
3179 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
3180 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
3181 ALLOCNO_CLASS_COST (parent_a
)
3182 -= ALLOCNO_CLASS_COST (a
);
3183 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
3184 parent_a
= ira_parent_allocno (parent_a
);
3185 if (parent_a
== NULL
)
3188 ALLOCNO_COPIES (a
) = NULL
;
3189 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3191 if (mem_dest_p
&& copy_info_to_removed_store_destinations (i
))
3194 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
3195 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
3196 ira_rebuild_start_finish_chains ();
3199 sparseset objects_live
;
3201 /* Rebuild conflicts. */
3202 FOR_EACH_ALLOCNO (a
, ai
)
3204 ira_allocno_object_iterator oi
;
3207 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3208 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3210 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3212 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3213 ira_assert (r
->object
== obj
);
3214 clear_conflicts (obj
);
3217 objects_live
= sparseset_alloc (ira_objects_num
);
3218 for (i
= 0; i
< ira_max_point
; i
++)
3220 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
3222 ira_object_t obj
= r
->object
;
3224 a
= OBJECT_ALLOCNO (obj
);
3225 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3226 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3229 aclass
= ALLOCNO_CLASS (a
);
3230 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, n
)
3232 ira_object_t live_obj
= ira_object_id_map
[n
];
3233 ira_allocno_t live_a
= OBJECT_ALLOCNO (live_obj
);
3234 enum reg_class live_aclass
= ALLOCNO_CLASS (live_a
);
3236 if (ira_reg_classes_intersect_p
[aclass
][live_aclass
]
3237 /* Don't set up conflict for the allocno with itself. */
3239 ira_add_conflict (obj
, live_obj
);
3241 sparseset_set_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
3244 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
3245 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (r
->object
));
3247 sparseset_free (objects_live
);
3248 compress_conflict_vecs ();
3250 /* Mark some copies for removing and change allocnos in the rest
3252 FOR_EACH_COPY (cp
, ci
)
3254 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
3255 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
3257 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3259 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3260 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
3261 ALLOCNO_NUM (cp
->first
),
3262 REGNO (allocno_emit_reg (cp
->first
)),
3263 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
3264 ALLOCNO_NUM (cp
->second
),
3265 REGNO (allocno_emit_reg (cp
->second
)));
3266 cp
->loop_tree_node
= NULL
;
3270 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->first
))];
3272 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->second
))];
3273 node
= cp
->loop_tree_node
;
3275 keep_p
= true; /* It copy generated in ira-emit.c. */
3278 /* Check that the copy was not propagated from level on
3279 which we will have different pseudos. */
3280 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
3281 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
3282 keep_p
= ((REGNO (allocno_emit_reg (first
))
3283 == REGNO (allocno_emit_reg (node_first
)))
3284 && (REGNO (allocno_emit_reg (second
))
3285 == REGNO (allocno_emit_reg (node_second
))));
3289 cp
->loop_tree_node
= ira_loop_tree_root
;
3291 cp
->second
= second
;
3295 cp
->loop_tree_node
= NULL
;
3296 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3297 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
3298 cp
->num
, ALLOCNO_NUM (cp
->first
),
3299 REGNO (allocno_emit_reg (cp
->first
)),
3300 ALLOCNO_NUM (cp
->second
),
3301 REGNO (allocno_emit_reg (cp
->second
)));
3304 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3305 FOR_EACH_ALLOCNO (a
, ai
)
3307 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3308 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3310 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3311 fprintf (ira_dump_file
, " Remove a%dr%d\n",
3312 ALLOCNO_NUM (a
), REGNO (allocno_emit_reg (a
)));
3313 ira_remove_allocno_prefs (a
);
3317 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
3318 ALLOCNO_REGNO (a
) = REGNO (allocno_emit_reg (a
));
3319 ALLOCNO_CAP (a
) = NULL
;
3320 /* Restore updated costs for assignments from reload. */
3321 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3322 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
3323 if (! ALLOCNO_ASSIGNED_P (a
))
3324 ira_free_allocno_updated_costs (a
);
3325 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3326 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3328 /* Remove unnecessary copies. */
3329 FOR_EACH_COPY (cp
, ci
)
3331 if (cp
->loop_tree_node
== NULL
)
3333 ira_copies
[cp
->num
] = NULL
;
3338 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
3339 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
3340 add_allocno_copy_to_list (cp
);
3341 swap_allocno_copy_ends_if_necessary (cp
);
3343 rebuild_regno_allocno_maps ();
3344 if (ira_max_point
!= ira_max_point_before_emit
)
3345 ira_compress_allocno_live_ranges ();
3346 ira_free (regno_top_level_allocno_map
);
3351 #ifdef ENABLE_IRA_CHECKING
3352 /* Check creation of all allocnos. Allocnos on lower levels should
3353 have allocnos or caps on all upper levels. */
3355 check_allocno_creation (void)
3358 ira_allocno_iterator ai
;
3359 ira_loop_tree_node_t loop_tree_node
;
3361 FOR_EACH_ALLOCNO (a
, ai
)
3363 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3364 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
3366 if (loop_tree_node
== ira_loop_tree_root
)
3368 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3369 ira_assert (ALLOCNO_CAP (a
) != NULL
);
3370 else if (ALLOCNO_CAP (a
) == NULL
)
3371 ira_assert (loop_tree_node
->parent
3372 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
3373 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
3379 /* Identify allocnos which prefer a register class with a single hard register.
3380 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3381 less likely to use the preferred singleton register. */
3383 update_conflict_hard_reg_costs (void)
3386 ira_allocno_iterator ai
;
3389 FOR_EACH_ALLOCNO (a
, ai
)
3391 reg_class_t aclass
= ALLOCNO_CLASS (a
);
3392 reg_class_t pref
= reg_preferred_class (ALLOCNO_REGNO (a
));
3393 int singleton
= ira_class_singleton
[pref
][ALLOCNO_MODE (a
)];
3396 index
= ira_class_hard_reg_index
[(int) aclass
][singleton
];
3399 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) == NULL
3400 || ALLOCNO_HARD_REG_COSTS (a
) == NULL
)
3403 for (i
= ira_class_hard_regs_num
[(int) aclass
] - 1; i
>= 0; i
--)
3404 if (ALLOCNO_HARD_REG_COSTS (a
)[i
] > ALLOCNO_CLASS_COST (a
)
3405 && min
> ALLOCNO_HARD_REG_COSTS (a
)[i
])
3406 min
= ALLOCNO_HARD_REG_COSTS (a
)[i
];
3409 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
3411 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[index
]
3412 -= min
- ALLOCNO_CLASS_COST (a
);
3416 /* Create a internal representation (IR) for IRA (allocnos, copies,
3417 loop tree nodes). The function returns TRUE if we generate loop
3418 structure (besides nodes representing all function and the basic
3419 blocks) for regional allocation. A true return means that we
3420 really need to flatten IR before the reload. */
3427 initiate_cost_vectors ();
3428 initiate_allocnos ();
3431 create_loop_tree_nodes ();
3435 create_allocno_objects ();
3436 ira_create_allocno_live_ranges ();
3437 remove_unnecessary_regions (false);
3438 ira_compress_allocno_live_ranges ();
3439 update_bad_spill_attribute ();
3440 loops_p
= more_one_region_p ();
3443 propagate_allocno_info ();
3446 ira_tune_allocno_costs ();
3447 #ifdef ENABLE_IRA_CHECKING
3448 check_allocno_creation ();
3450 setup_min_max_allocno_live_range_point ();
3451 sort_conflict_id_map ();
3452 setup_min_max_conflict_allocno_ids ();
3453 ira_build_conflicts ();
3454 update_conflict_hard_reg_costs ();
3455 if (! ira_conflicts_p
)
3458 ira_allocno_iterator ai
;
3460 /* Remove all regions but root one. */
3463 remove_unnecessary_regions (true);
3466 /* We don't save hard registers around calls for fast allocation
3467 -- add caller clobbered registers as conflicting ones to
3468 allocno crossing calls. */
3469 FOR_EACH_ALLOCNO (a
, ai
)
3470 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
3471 ior_hard_reg_conflicts (a
, &call_used_reg_set
);
3473 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3474 print_copies (ira_dump_file
);
3475 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3476 print_prefs (ira_dump_file
);
3477 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3482 ira_allocno_iterator ai
;
3487 FOR_EACH_ALLOCNO (a
, ai
)
3489 int j
, nobj
= ALLOCNO_NUM_OBJECTS (a
);
3493 for (j
= 0; j
< nobj
; j
++)
3495 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
3496 n
+= OBJECT_NUM_CONFLICTS (obj
);
3497 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3501 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
3502 current_loops
== NULL
? 1 : number_of_loops (cfun
),
3503 n_basic_blocks_for_fn (cfun
), ira_max_point
);
3504 fprintf (ira_dump_file
,
3505 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3506 ira_allocnos_num
, nr_big
, ira_copies_num
, n
, nr
);
3511 /* Release the data created by function ira_build. */
3515 finish_loop_tree_nodes ();
3519 finish_cost_vectors ();
3520 ira_finish_allocno_live_ranges ();