1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2013 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "insn-config.h"
34 #include "diagnostic-core.h"
38 #include "sparseset.h"
40 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
42 static ira_copy_t
find_allocno_copy (ira_allocno_t
, ira_allocno_t
, rtx
,
43 ira_loop_tree_node_t
);
45 /* The root of the loop tree corresponding to the all function. */
46 ira_loop_tree_node_t ira_loop_tree_root
;
48 /* Height of the loop tree. */
49 int ira_loop_tree_height
;
51 /* All nodes representing basic blocks are referred through the
52 following array. We can not use basic block member `aux' for this
53 because it is used for insertion of insns on edges. */
54 ira_loop_tree_node_t ira_bb_nodes
;
56 /* All nodes representing loops are referred through the following
58 ira_loop_tree_node_t ira_loop_nodes
;
60 /* And size of the ira_loop_nodes array. */
61 unsigned int ira_loop_nodes_count
;
63 /* Map regno -> allocnos with given regno (see comments for
64 allocno member `next_regno_allocno'). */
65 ira_allocno_t
*ira_regno_allocno_map
;
67 /* Array of references to all allocnos. The order number of the
68 allocno corresponds to the index in the array. Removed allocnos
69 have NULL element value. */
70 ira_allocno_t
*ira_allocnos
;
72 /* Sizes of the previous array. */
75 /* Count of conflict record structures we've created, used when creating
79 /* Map a conflict id to its conflict record. */
80 ira_object_t
*ira_object_id_map
;
82 /* Array of references to all allocno preferences. The order number
83 of the preference corresponds to the index in the array. */
84 ira_pref_t
*ira_prefs
;
86 /* Size of the previous array. */
89 /* Array of references to all copies. The order number of the copy
90 corresponds to the index in the array. Removed copies have NULL
92 ira_copy_t
*ira_copies
;
94 /* Size of the previous array. */
99 /* LAST_BASIC_BLOCK before generating additional insns because of live
100 range splitting. Emitting insns on a critical edge creates a new
102 static int last_basic_block_before_change
;
104 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
105 the member loop_num. */
107 init_loop_tree_node (struct ira_loop_tree_node
*node
, int loop_num
)
109 int max_regno
= max_reg_num ();
111 node
->regno_allocno_map
112 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
) * max_regno
);
113 memset (node
->regno_allocno_map
, 0, sizeof (ira_allocno_t
) * max_regno
);
114 memset (node
->reg_pressure
, 0, sizeof (node
->reg_pressure
));
115 node
->all_allocnos
= ira_allocate_bitmap ();
116 node
->modified_regnos
= ira_allocate_bitmap ();
117 node
->border_allocnos
= ira_allocate_bitmap ();
118 node
->local_copies
= ira_allocate_bitmap ();
119 node
->loop_num
= loop_num
;
120 node
->children
= NULL
;
121 node
->subloops
= NULL
;
125 /* The following function allocates the loop tree nodes. If
126 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
127 the root which corresponds the all function) will be not allocated
128 but nodes will still be allocated for basic blocks. */
130 create_loop_tree_nodes (void)
140 = ((struct ira_loop_tree_node
*)
141 ira_allocate (sizeof (struct ira_loop_tree_node
) * last_basic_block
));
142 last_basic_block_before_change
= last_basic_block
;
143 for (i
= 0; i
< (unsigned int) last_basic_block
; i
++)
145 ira_bb_nodes
[i
].regno_allocno_map
= NULL
;
146 memset (ira_bb_nodes
[i
].reg_pressure
, 0,
147 sizeof (ira_bb_nodes
[i
].reg_pressure
));
148 ira_bb_nodes
[i
].all_allocnos
= NULL
;
149 ira_bb_nodes
[i
].modified_regnos
= NULL
;
150 ira_bb_nodes
[i
].border_allocnos
= NULL
;
151 ira_bb_nodes
[i
].local_copies
= NULL
;
153 if (current_loops
== NULL
)
155 ira_loop_nodes_count
= 1;
156 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
157 ira_allocate (sizeof (struct ira_loop_tree_node
)));
158 init_loop_tree_node (ira_loop_nodes
, 0);
161 ira_loop_nodes_count
= number_of_loops (cfun
);
162 ira_loop_nodes
= ((struct ira_loop_tree_node
*)
163 ira_allocate (sizeof (struct ira_loop_tree_node
)
164 * ira_loop_nodes_count
));
165 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
167 if (loop_outer (loop
) != NULL
)
169 ira_loop_nodes
[i
].regno_allocno_map
= NULL
;
171 FOR_EACH_EDGE (e
, ei
, loop
->header
->preds
)
172 if (e
->src
!= loop
->latch
173 && (e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
180 edges
= get_loop_exit_edges (loop
);
181 FOR_EACH_VEC_ELT (edges
, j
, e
)
182 if ((e
->flags
& EDGE_ABNORMAL
) && EDGE_CRITICAL_P (e
))
191 init_loop_tree_node (&ira_loop_nodes
[i
], loop
->num
);
195 /* The function returns TRUE if there are more one allocation
198 more_one_region_p (void)
203 if (current_loops
!= NULL
)
204 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
205 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
206 && ira_loop_tree_root
!= &ira_loop_nodes
[i
])
211 /* Free the loop tree node of a loop. */
213 finish_loop_tree_node (ira_loop_tree_node_t loop
)
215 if (loop
->regno_allocno_map
!= NULL
)
217 ira_assert (loop
->bb
== NULL
);
218 ira_free_bitmap (loop
->local_copies
);
219 ira_free_bitmap (loop
->border_allocnos
);
220 ira_free_bitmap (loop
->modified_regnos
);
221 ira_free_bitmap (loop
->all_allocnos
);
222 ira_free (loop
->regno_allocno_map
);
223 loop
->regno_allocno_map
= NULL
;
227 /* Free the loop tree nodes. */
229 finish_loop_tree_nodes (void)
233 for (i
= 0; i
< ira_loop_nodes_count
; i
++)
234 finish_loop_tree_node (&ira_loop_nodes
[i
]);
235 ira_free (ira_loop_nodes
);
236 for (i
= 0; i
< (unsigned int) last_basic_block_before_change
; i
++)
238 if (ira_bb_nodes
[i
].local_copies
!= NULL
)
239 ira_free_bitmap (ira_bb_nodes
[i
].local_copies
);
240 if (ira_bb_nodes
[i
].border_allocnos
!= NULL
)
241 ira_free_bitmap (ira_bb_nodes
[i
].border_allocnos
);
242 if (ira_bb_nodes
[i
].modified_regnos
!= NULL
)
243 ira_free_bitmap (ira_bb_nodes
[i
].modified_regnos
);
244 if (ira_bb_nodes
[i
].all_allocnos
!= NULL
)
245 ira_free_bitmap (ira_bb_nodes
[i
].all_allocnos
);
246 if (ira_bb_nodes
[i
].regno_allocno_map
!= NULL
)
247 ira_free (ira_bb_nodes
[i
].regno_allocno_map
);
249 ira_free (ira_bb_nodes
);
254 /* The following recursive function adds LOOP to the loop tree
255 hierarchy. LOOP is added only once. If LOOP is NULL we adding
256 loop designating the whole function when CFG loops are not
259 add_loop_to_tree (struct loop
*loop
)
263 ira_loop_tree_node_t loop_node
, parent_node
;
265 /* We can not use loop node access macros here because of potential
266 checking and because the nodes are not initialized enough
268 if (loop
!= NULL
&& loop_outer (loop
) != NULL
)
269 add_loop_to_tree (loop_outer (loop
));
270 loop_num
= loop
!= NULL
? loop
->num
: 0;
271 if (ira_loop_nodes
[loop_num
].regno_allocno_map
!= NULL
272 && ira_loop_nodes
[loop_num
].children
== NULL
)
274 /* We have not added loop node to the tree yet. */
275 loop_node
= &ira_loop_nodes
[loop_num
];
276 loop_node
->loop
= loop
;
277 loop_node
->bb
= NULL
;
282 for (parent
= loop_outer (loop
);
284 parent
= loop_outer (parent
))
285 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
290 loop_node
->next
= NULL
;
291 loop_node
->subloop_next
= NULL
;
292 loop_node
->parent
= NULL
;
296 parent_node
= &ira_loop_nodes
[parent
->num
];
297 loop_node
->next
= parent_node
->children
;
298 parent_node
->children
= loop_node
;
299 loop_node
->subloop_next
= parent_node
->subloops
;
300 parent_node
->subloops
= loop_node
;
301 loop_node
->parent
= parent_node
;
306 /* The following recursive function sets up levels of nodes of the
307 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
308 The function returns maximal value of level in the tree + 1. */
310 setup_loop_tree_level (ira_loop_tree_node_t loop_node
, int level
)
312 int height
, max_height
;
313 ira_loop_tree_node_t subloop_node
;
315 ira_assert (loop_node
->bb
== NULL
);
316 loop_node
->level
= level
;
317 max_height
= level
+ 1;
318 for (subloop_node
= loop_node
->subloops
;
319 subloop_node
!= NULL
;
320 subloop_node
= subloop_node
->subloop_next
)
322 ira_assert (subloop_node
->bb
== NULL
);
323 height
= setup_loop_tree_level (subloop_node
, level
+ 1);
324 if (height
> max_height
)
330 /* Create the loop tree. The algorithm is designed to provide correct
331 order of loops (they are ordered by their last loop BB) and basic
332 blocks in the chain formed by member next. */
334 form_loop_tree (void)
338 ira_loop_tree_node_t bb_node
, loop_node
;
340 /* We can not use loop/bb node access macros because of potential
341 checking and because the nodes are not initialized enough
345 bb_node
= &ira_bb_nodes
[bb
->index
];
347 bb_node
->loop
= NULL
;
348 bb_node
->subloops
= NULL
;
349 bb_node
->children
= NULL
;
350 bb_node
->subloop_next
= NULL
;
351 bb_node
->next
= NULL
;
352 if (current_loops
== NULL
)
356 for (parent
= bb
->loop_father
;
358 parent
= loop_outer (parent
))
359 if (ira_loop_nodes
[parent
->num
].regno_allocno_map
!= NULL
)
362 add_loop_to_tree (parent
);
363 loop_node
= &ira_loop_nodes
[parent
== NULL
? 0 : parent
->num
];
364 bb_node
->next
= loop_node
->children
;
365 bb_node
->parent
= loop_node
;
366 loop_node
->children
= bb_node
;
368 ira_loop_tree_root
= IRA_LOOP_NODE_BY_INDEX (0);
369 ira_loop_tree_height
= setup_loop_tree_level (ira_loop_tree_root
, 0);
370 ira_assert (ira_loop_tree_root
->regno_allocno_map
!= NULL
);
375 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
378 rebuild_regno_allocno_maps (void)
381 int max_regno
, regno
;
383 ira_loop_tree_node_t loop_tree_node
;
385 ira_allocno_iterator ai
;
387 ira_assert (current_loops
!= NULL
);
388 max_regno
= max_reg_num ();
389 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), l
, loop
)
390 if (ira_loop_nodes
[l
].regno_allocno_map
!= NULL
)
392 ira_free (ira_loop_nodes
[l
].regno_allocno_map
);
393 ira_loop_nodes
[l
].regno_allocno_map
394 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
396 memset (ira_loop_nodes
[l
].regno_allocno_map
, 0,
397 sizeof (ira_allocno_t
) * max_regno
);
399 ira_free (ira_regno_allocno_map
);
400 ira_regno_allocno_map
401 = (ira_allocno_t
*) ira_allocate (max_regno
* sizeof (ira_allocno_t
));
402 memset (ira_regno_allocno_map
, 0, max_regno
* sizeof (ira_allocno_t
));
403 FOR_EACH_ALLOCNO (a
, ai
)
405 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
406 /* Caps are not in the regno allocno maps. */
408 regno
= ALLOCNO_REGNO (a
);
409 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
410 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
411 ira_regno_allocno_map
[regno
] = a
;
412 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
413 /* Remember that we can create temporary allocnos to break
414 cycles in register shuffle. */
415 loop_tree_node
->regno_allocno_map
[regno
] = a
;
420 /* Pools for allocnos, allocno live ranges and objects. */
421 static alloc_pool allocno_pool
, live_range_pool
, object_pool
;
423 /* Vec containing references to all created allocnos. It is a
424 container of array allocnos. */
425 static vec
<ira_allocno_t
> allocno_vec
;
427 /* Vec containing references to all created ira_objects. It is a
428 container of ira_object_id_map. */
429 static vec
<ira_object_t
> ira_object_id_map_vec
;
431 /* Initialize data concerning allocnos. */
433 initiate_allocnos (void)
436 = create_alloc_pool ("live ranges",
437 sizeof (struct live_range
), 100);
439 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno
), 100);
441 = create_alloc_pool ("objects", sizeof (struct ira_object
), 100);
442 allocno_vec
.create (max_reg_num () * 2);
444 ira_allocnos_num
= 0;
446 ira_object_id_map_vec
.create (max_reg_num () * 2);
447 ira_object_id_map
= NULL
;
448 ira_regno_allocno_map
449 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
450 * sizeof (ira_allocno_t
));
451 memset (ira_regno_allocno_map
, 0, max_reg_num () * sizeof (ira_allocno_t
));
454 /* Create and return an object corresponding to a new allocno A. */
456 ira_create_object (ira_allocno_t a
, int subword
)
458 enum reg_class aclass
= ALLOCNO_CLASS (a
);
459 ira_object_t obj
= (ira_object_t
) pool_alloc (object_pool
);
461 OBJECT_ALLOCNO (obj
) = a
;
462 OBJECT_SUBWORD (obj
) = subword
;
463 OBJECT_CONFLICT_ID (obj
) = ira_objects_num
;
464 OBJECT_CONFLICT_VEC_P (obj
) = false;
465 OBJECT_CONFLICT_ARRAY (obj
) = NULL
;
466 OBJECT_NUM_CONFLICTS (obj
) = 0;
467 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
468 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), ira_no_alloc_regs
);
469 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
470 reg_class_contents
[aclass
]);
471 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
472 reg_class_contents
[aclass
]);
473 OBJECT_MIN (obj
) = INT_MAX
;
474 OBJECT_MAX (obj
) = -1;
475 OBJECT_LIVE_RANGES (obj
) = NULL
;
477 ira_object_id_map_vec
.safe_push (obj
);
479 = ira_object_id_map_vec
.address ();
480 ira_objects_num
= ira_object_id_map_vec
.length ();
485 /* Create and return the allocno corresponding to REGNO in
486 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
487 same regno if CAP_P is FALSE. */
489 ira_create_allocno (int regno
, bool cap_p
,
490 ira_loop_tree_node_t loop_tree_node
)
494 a
= (ira_allocno_t
) pool_alloc (allocno_pool
);
495 ALLOCNO_REGNO (a
) = regno
;
496 ALLOCNO_LOOP_TREE_NODE (a
) = loop_tree_node
;
499 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = ira_regno_allocno_map
[regno
];
500 ira_regno_allocno_map
[regno
] = a
;
501 if (loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
502 /* Remember that we can create temporary allocnos to break
503 cycles in register shuffle on region borders (see
505 loop_tree_node
->regno_allocno_map
[regno
] = a
;
507 ALLOCNO_CAP (a
) = NULL
;
508 ALLOCNO_CAP_MEMBER (a
) = NULL
;
509 ALLOCNO_NUM (a
) = ira_allocnos_num
;
510 bitmap_set_bit (loop_tree_node
->all_allocnos
, ALLOCNO_NUM (a
));
511 ALLOCNO_NREFS (a
) = 0;
512 ALLOCNO_FREQ (a
) = 0;
513 ALLOCNO_HARD_REGNO (a
) = -1;
514 ALLOCNO_CALL_FREQ (a
) = 0;
515 ALLOCNO_CALLS_CROSSED_NUM (a
) = 0;
516 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
) = 0;
518 ALLOCNO_NO_STACK_REG_P (a
) = false;
519 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = false;
521 ALLOCNO_DONT_REASSIGN_P (a
) = false;
522 ALLOCNO_BAD_SPILL_P (a
) = false;
523 ALLOCNO_ASSIGNED_P (a
) = false;
524 ALLOCNO_MODE (a
) = (regno
< 0 ? VOIDmode
: PSEUDO_REGNO_MODE (regno
));
525 ALLOCNO_PREFS (a
) = NULL
;
526 ALLOCNO_COPIES (a
) = NULL
;
527 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
528 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
529 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
530 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
531 ALLOCNO_CLASS (a
) = NO_REGS
;
532 ALLOCNO_UPDATED_CLASS_COST (a
) = 0;
533 ALLOCNO_CLASS_COST (a
) = 0;
534 ALLOCNO_MEMORY_COST (a
) = 0;
535 ALLOCNO_UPDATED_MEMORY_COST (a
) = 0;
536 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
) = 0;
537 ALLOCNO_NUM_OBJECTS (a
) = 0;
539 ALLOCNO_ADD_DATA (a
) = NULL
;
540 allocno_vec
.safe_push (a
);
541 ira_allocnos
= allocno_vec
.address ();
542 ira_allocnos_num
= allocno_vec
.length ();
547 /* Set up register class for A and update its conflict hard
550 ira_set_allocno_class (ira_allocno_t a
, enum reg_class aclass
)
552 ira_allocno_object_iterator oi
;
555 ALLOCNO_CLASS (a
) = aclass
;
556 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
558 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
559 reg_class_contents
[aclass
]);
560 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
561 reg_class_contents
[aclass
]);
565 /* Determine the number of objects we should associate with allocno A
566 and allocate them. */
568 ira_create_allocno_objects (ira_allocno_t a
)
570 enum machine_mode mode
= ALLOCNO_MODE (a
);
571 enum reg_class aclass
= ALLOCNO_CLASS (a
);
572 int n
= ira_reg_class_max_nregs
[aclass
][mode
];
575 if (GET_MODE_SIZE (mode
) != 2 * UNITS_PER_WORD
|| n
!= 2)
578 ALLOCNO_NUM_OBJECTS (a
) = n
;
579 for (i
= 0; i
< n
; i
++)
580 ALLOCNO_OBJECT (a
, i
) = ira_create_object (a
, i
);
583 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
584 ALLOCNO_OBJECT structures. This must be called after the allocno
585 classes are known. */
587 create_allocno_objects (void)
590 ira_allocno_iterator ai
;
592 FOR_EACH_ALLOCNO (a
, ai
)
593 ira_create_allocno_objects (a
);
596 /* Merge hard register conflict information for all objects associated with
597 allocno TO into the corresponding objects associated with FROM.
598 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
600 merge_hard_reg_conflicts (ira_allocno_t from
, ira_allocno_t to
,
604 gcc_assert (ALLOCNO_NUM_OBJECTS (to
) == ALLOCNO_NUM_OBJECTS (from
));
605 for (i
= 0; i
< ALLOCNO_NUM_OBJECTS (to
); i
++)
607 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
608 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
611 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj
),
612 OBJECT_CONFLICT_HARD_REGS (from_obj
));
613 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj
),
614 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj
));
617 if (!total_only
&& ALLOCNO_NO_STACK_REG_P (from
))
618 ALLOCNO_NO_STACK_REG_P (to
) = true;
619 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from
))
620 ALLOCNO_TOTAL_NO_STACK_REG_P (to
) = true;
624 /* Update hard register conflict information for all objects associated with
625 A to include the regs in SET. */
627 ior_hard_reg_conflicts (ira_allocno_t a
, HARD_REG_SET
*set
)
629 ira_allocno_object_iterator i
;
632 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, i
)
634 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
), *set
);
635 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
), *set
);
639 /* Return TRUE if a conflict vector with NUM elements is more
640 profitable than a conflict bit vector for OBJ. */
642 ira_conflict_vector_profitable_p (ira_object_t obj
, int num
)
645 int max
= OBJECT_MAX (obj
);
646 int min
= OBJECT_MIN (obj
);
649 /* We prefer a bit vector in such case because it does not result
653 nw
= (max
- min
+ IRA_INT_BITS
) / IRA_INT_BITS
;
654 return (2 * sizeof (ira_object_t
) * (num
+ 1)
655 < 3 * nw
* sizeof (IRA_INT_TYPE
));
658 /* Allocates and initialize the conflict vector of OBJ for NUM
659 conflicting objects. */
661 ira_allocate_conflict_vec (ira_object_t obj
, int num
)
666 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
667 num
++; /* for NULL end marker */
668 size
= sizeof (ira_object_t
) * num
;
669 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
670 vec
= (ira_object_t
*) OBJECT_CONFLICT_ARRAY (obj
);
672 OBJECT_NUM_CONFLICTS (obj
) = 0;
673 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
674 OBJECT_CONFLICT_VEC_P (obj
) = true;
677 /* Allocate and initialize the conflict bit vector of OBJ. */
679 allocate_conflict_bit_vec (ira_object_t obj
)
683 ira_assert (OBJECT_CONFLICT_ARRAY (obj
) == NULL
);
684 size
= ((OBJECT_MAX (obj
) - OBJECT_MIN (obj
) + IRA_INT_BITS
)
685 / IRA_INT_BITS
* sizeof (IRA_INT_TYPE
));
686 OBJECT_CONFLICT_ARRAY (obj
) = ira_allocate (size
);
687 memset (OBJECT_CONFLICT_ARRAY (obj
), 0, size
);
688 OBJECT_CONFLICT_ARRAY_SIZE (obj
) = size
;
689 OBJECT_CONFLICT_VEC_P (obj
) = false;
692 /* Allocate and initialize the conflict vector or conflict bit vector
693 of OBJ for NUM conflicting allocnos whatever is more profitable. */
695 ira_allocate_object_conflicts (ira_object_t obj
, int num
)
697 if (ira_conflict_vector_profitable_p (obj
, num
))
698 ira_allocate_conflict_vec (obj
, num
);
700 allocate_conflict_bit_vec (obj
);
703 /* Add OBJ2 to the conflicts of OBJ1. */
705 add_to_conflicts (ira_object_t obj1
, ira_object_t obj2
)
710 if (OBJECT_CONFLICT_VEC_P (obj1
))
712 ira_object_t
*vec
= OBJECT_CONFLICT_VEC (obj1
);
713 int curr_num
= OBJECT_NUM_CONFLICTS (obj1
);
715 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < num
* sizeof (ira_object_t
))
717 ira_object_t
*newvec
;
718 size
= (3 * num
/ 2 + 1) * sizeof (ira_allocno_t
);
719 newvec
= (ira_object_t
*) ira_allocate (size
);
720 memcpy (newvec
, vec
, curr_num
* sizeof (ira_object_t
));
723 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
724 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
728 OBJECT_NUM_CONFLICTS (obj1
)++;
732 int nw
, added_head_nw
, id
;
733 IRA_INT_TYPE
*vec
= OBJECT_CONFLICT_BITVEC (obj1
);
735 id
= OBJECT_CONFLICT_ID (obj2
);
736 if (OBJECT_MIN (obj1
) > id
)
738 /* Expand head of the bit vector. */
739 added_head_nw
= (OBJECT_MIN (obj1
) - id
- 1) / IRA_INT_BITS
+ 1;
740 nw
= (OBJECT_MAX (obj1
) - OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
741 size
= (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
);
742 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) >= size
)
744 memmove ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
745 vec
, nw
* sizeof (IRA_INT_TYPE
));
746 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
751 = (3 * (nw
+ added_head_nw
) / 2 + 1) * sizeof (IRA_INT_TYPE
);
752 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
753 memcpy ((char *) vec
+ added_head_nw
* sizeof (IRA_INT_TYPE
),
754 OBJECT_CONFLICT_ARRAY (obj1
), nw
* sizeof (IRA_INT_TYPE
));
755 memset (vec
, 0, added_head_nw
* sizeof (IRA_INT_TYPE
));
757 + (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
),
758 0, size
- (nw
+ added_head_nw
) * sizeof (IRA_INT_TYPE
));
759 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
760 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
761 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
763 OBJECT_MIN (obj1
) -= added_head_nw
* IRA_INT_BITS
;
765 else if (OBJECT_MAX (obj1
) < id
)
767 nw
= (id
- OBJECT_MIN (obj1
)) / IRA_INT_BITS
+ 1;
768 size
= nw
* sizeof (IRA_INT_TYPE
);
769 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1
) < size
)
771 /* Expand tail of the bit vector. */
772 size
= (3 * nw
/ 2 + 1) * sizeof (IRA_INT_TYPE
);
773 vec
= (IRA_INT_TYPE
*) ira_allocate (size
);
774 memcpy (vec
, OBJECT_CONFLICT_ARRAY (obj1
), OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
775 memset ((char *) vec
+ OBJECT_CONFLICT_ARRAY_SIZE (obj1
),
776 0, size
- OBJECT_CONFLICT_ARRAY_SIZE (obj1
));
777 ira_free (OBJECT_CONFLICT_ARRAY (obj1
));
778 OBJECT_CONFLICT_ARRAY (obj1
) = vec
;
779 OBJECT_CONFLICT_ARRAY_SIZE (obj1
) = size
;
781 OBJECT_MAX (obj1
) = id
;
783 SET_MINMAX_SET_BIT (vec
, id
, OBJECT_MIN (obj1
), OBJECT_MAX (obj1
));
787 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
789 ira_add_conflict (ira_object_t obj1
, ira_object_t obj2
)
791 add_to_conflicts (obj1
, obj2
);
792 add_to_conflicts (obj2
, obj1
);
795 /* Clear all conflicts of OBJ. */
797 clear_conflicts (ira_object_t obj
)
799 if (OBJECT_CONFLICT_VEC_P (obj
))
801 OBJECT_NUM_CONFLICTS (obj
) = 0;
802 OBJECT_CONFLICT_VEC (obj
)[0] = NULL
;
804 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj
) != 0)
808 nw
= (OBJECT_MAX (obj
) - OBJECT_MIN (obj
)) / IRA_INT_BITS
+ 1;
809 memset (OBJECT_CONFLICT_BITVEC (obj
), 0, nw
* sizeof (IRA_INT_TYPE
));
813 /* The array used to find duplications in conflict vectors of
815 static int *conflict_check
;
817 /* The value used to mark allocation presence in conflict vector of
818 the current allocno. */
819 static int curr_conflict_check_tick
;
821 /* Remove duplications in conflict vector of OBJ. */
823 compress_conflict_vec (ira_object_t obj
)
825 ira_object_t
*vec
, conflict_obj
;
828 ira_assert (OBJECT_CONFLICT_VEC_P (obj
));
829 vec
= OBJECT_CONFLICT_VEC (obj
);
830 curr_conflict_check_tick
++;
831 for (i
= j
= 0; (conflict_obj
= vec
[i
]) != NULL
; i
++)
833 int id
= OBJECT_CONFLICT_ID (conflict_obj
);
834 if (conflict_check
[id
] != curr_conflict_check_tick
)
836 conflict_check
[id
] = curr_conflict_check_tick
;
837 vec
[j
++] = conflict_obj
;
840 OBJECT_NUM_CONFLICTS (obj
) = j
;
844 /* Remove duplications in conflict vectors of all allocnos. */
846 compress_conflict_vecs (void)
849 ira_object_iterator oi
;
851 conflict_check
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
852 memset (conflict_check
, 0, sizeof (int) * ira_objects_num
);
853 curr_conflict_check_tick
= 0;
854 FOR_EACH_OBJECT (obj
, oi
)
856 if (OBJECT_CONFLICT_VEC_P (obj
))
857 compress_conflict_vec (obj
);
859 ira_free (conflict_check
);
862 /* This recursive function outputs allocno A and if it is a cap the
863 function outputs its members. */
865 ira_print_expanded_allocno (ira_allocno_t a
)
869 fprintf (ira_dump_file
, " a%d(r%d", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
870 if ((bb
= ALLOCNO_LOOP_TREE_NODE (a
)->bb
) != NULL
)
871 fprintf (ira_dump_file
, ",b%d", bb
->index
);
873 fprintf (ira_dump_file
, ",l%d", ALLOCNO_LOOP_TREE_NODE (a
)->loop_num
);
874 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
876 fprintf (ira_dump_file
, ":");
877 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a
));
879 fprintf (ira_dump_file
, ")");
882 /* Create and return the cap representing allocno A in the
885 create_cap_allocno (ira_allocno_t a
)
888 ira_loop_tree_node_t parent
;
889 enum reg_class aclass
;
891 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
892 cap
= ira_create_allocno (ALLOCNO_REGNO (a
), true, parent
);
893 ALLOCNO_MODE (cap
) = ALLOCNO_MODE (a
);
894 aclass
= ALLOCNO_CLASS (a
);
895 ira_set_allocno_class (cap
, aclass
);
896 ira_create_allocno_objects (cap
);
897 ALLOCNO_CAP_MEMBER (cap
) = a
;
898 ALLOCNO_CAP (a
) = cap
;
899 ALLOCNO_CLASS_COST (cap
) = ALLOCNO_CLASS_COST (a
);
900 ALLOCNO_MEMORY_COST (cap
) = ALLOCNO_MEMORY_COST (a
);
901 ira_allocate_and_copy_costs
902 (&ALLOCNO_HARD_REG_COSTS (cap
), aclass
, ALLOCNO_HARD_REG_COSTS (a
));
903 ira_allocate_and_copy_costs
904 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap
), aclass
,
905 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
));
906 ALLOCNO_BAD_SPILL_P (cap
) = ALLOCNO_BAD_SPILL_P (a
);
907 ALLOCNO_NREFS (cap
) = ALLOCNO_NREFS (a
);
908 ALLOCNO_FREQ (cap
) = ALLOCNO_FREQ (a
);
909 ALLOCNO_CALL_FREQ (cap
) = ALLOCNO_CALL_FREQ (a
);
911 merge_hard_reg_conflicts (a
, cap
, false);
913 ALLOCNO_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CALLS_CROSSED_NUM (a
);
914 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap
) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
915 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
917 fprintf (ira_dump_file
, " Creating cap ");
918 ira_print_expanded_allocno (cap
);
919 fprintf (ira_dump_file
, "\n");
924 /* Create and return a live range for OBJECT with given attributes. */
926 ira_create_live_range (ira_object_t obj
, int start
, int finish
,
931 p
= (live_range_t
) pool_alloc (live_range_pool
);
939 /* Create a new live range for OBJECT and queue it at the head of its
942 ira_add_live_range_to_object (ira_object_t object
, int start
, int finish
)
945 p
= ira_create_live_range (object
, start
, finish
,
946 OBJECT_LIVE_RANGES (object
));
947 OBJECT_LIVE_RANGES (object
) = p
;
950 /* Copy allocno live range R and return the result. */
952 copy_live_range (live_range_t r
)
956 p
= (live_range_t
) pool_alloc (live_range_pool
);
961 /* Copy allocno live range list given by its head R and return the
964 ira_copy_live_range_list (live_range_t r
)
966 live_range_t p
, first
, last
;
970 for (first
= last
= NULL
; r
!= NULL
; r
= r
->next
)
972 p
= copy_live_range (r
);
982 /* Merge ranges R1 and R2 and returns the result. The function
983 maintains the order of ranges and tries to minimize number of the
986 ira_merge_live_ranges (live_range_t r1
, live_range_t r2
)
988 live_range_t first
, last
, temp
;
994 for (first
= last
= NULL
; r1
!= NULL
&& r2
!= NULL
;)
996 if (r1
->start
< r2
->start
)
1002 if (r1
->start
<= r2
->finish
+ 1)
1004 /* Intersected ranges: merge r1 and r2 into r1. */
1005 r1
->start
= r2
->start
;
1006 if (r1
->finish
< r2
->finish
)
1007 r1
->finish
= r2
->finish
;
1010 ira_finish_live_range (temp
);
1013 /* To try to merge with subsequent ranges in r1. */
1020 /* Add r1 to the result. */
1031 /* To try to merge with subsequent ranges in r2. */
1043 ira_assert (r1
->next
== NULL
);
1045 else if (r2
!= NULL
)
1051 ira_assert (r2
->next
== NULL
);
1055 ira_assert (last
->next
== NULL
);
1060 /* Return TRUE if live ranges R1 and R2 intersect. */
1062 ira_live_ranges_intersect_p (live_range_t r1
, live_range_t r2
)
1064 /* Remember the live ranges are always kept ordered. */
1065 while (r1
!= NULL
&& r2
!= NULL
)
1067 if (r1
->start
> r2
->finish
)
1069 else if (r2
->start
> r1
->finish
)
1077 /* Free allocno live range R. */
1079 ira_finish_live_range (live_range_t r
)
1081 pool_free (live_range_pool
, r
);
1084 /* Free list of allocno live ranges starting with R. */
1086 ira_finish_live_range_list (live_range_t r
)
1088 live_range_t next_r
;
1090 for (; r
!= NULL
; r
= next_r
)
1093 ira_finish_live_range (r
);
1097 /* Free updated register costs of allocno A. */
1099 ira_free_allocno_updated_costs (ira_allocno_t a
)
1101 enum reg_class aclass
;
1103 aclass
= ALLOCNO_CLASS (a
);
1104 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
1105 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
);
1106 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
1107 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1108 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1110 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1113 /* Free and nullify all cost vectors allocated earlier for allocno
1116 ira_free_allocno_costs (ira_allocno_t a
)
1118 enum reg_class aclass
= ALLOCNO_CLASS (a
);
1120 ira_allocno_object_iterator oi
;
1122 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
1124 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj
));
1125 ira_object_id_map
[OBJECT_CONFLICT_ID (obj
)] = NULL
;
1126 if (OBJECT_CONFLICT_ARRAY (obj
) != NULL
)
1127 ira_free (OBJECT_CONFLICT_ARRAY (obj
));
1128 pool_free (object_pool
, obj
);
1131 ira_allocnos
[ALLOCNO_NUM (a
)] = NULL
;
1132 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
)
1133 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a
), aclass
);
1134 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1135 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
), aclass
);
1136 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) != NULL
)
1137 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a
), aclass
);
1138 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) != NULL
)
1139 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
),
1141 ALLOCNO_HARD_REG_COSTS (a
) = NULL
;
1142 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1143 ALLOCNO_UPDATED_HARD_REG_COSTS (a
) = NULL
;
1144 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) = NULL
;
1147 /* Free the memory allocated for allocno A. */
1149 finish_allocno (ira_allocno_t a
)
1151 ira_free_allocno_costs (a
);
1152 pool_free (allocno_pool
, a
);
1155 /* Free the memory allocated for all allocnos. */
1157 finish_allocnos (void)
1160 ira_allocno_iterator ai
;
1162 FOR_EACH_ALLOCNO (a
, ai
)
1164 ira_free (ira_regno_allocno_map
);
1165 ira_object_id_map_vec
.release ();
1166 allocno_vec
.release ();
1167 free_alloc_pool (allocno_pool
);
1168 free_alloc_pool (object_pool
);
1169 free_alloc_pool (live_range_pool
);
1174 /* Pools for allocno preferences. */
1175 static alloc_pool pref_pool
;
1177 /* Vec containing references to all created preferences. It is a
1178 container of array ira_prefs. */
1179 static vec
<ira_pref_t
> pref_vec
;
1181 /* The function initializes data concerning allocno prefs. */
1183 initiate_prefs (void)
1186 = create_alloc_pool ("prefs", sizeof (struct ira_allocno_pref
), 100);
1187 pref_vec
.create (get_max_uid ());
1192 /* Return pref for A and HARD_REGNO if any. */
1194 find_allocno_pref (ira_allocno_t a
, int hard_regno
)
1198 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1199 if (pref
->allocno
== a
&& pref
->hard_regno
== hard_regno
)
1204 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1206 ira_create_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1210 pref
= (ira_pref_t
) pool_alloc (pref_pool
);
1211 pref
->num
= ira_prefs_num
;
1213 pref
->hard_regno
= hard_regno
;
1215 pref_vec
.safe_push (pref
);
1216 ira_prefs
= pref_vec
.address ();
1217 ira_prefs_num
= pref_vec
.length ();
1221 /* Attach a pref PREF to the cooresponding allocno. */
1223 add_allocno_pref_to_list (ira_pref_t pref
)
1225 ira_allocno_t a
= pref
->allocno
;
1227 pref
->next_pref
= ALLOCNO_PREFS (a
);
1228 ALLOCNO_PREFS (a
) = pref
;
1231 /* Create (or update frequency if the pref already exists) the pref of
1232 allocnos A preferring HARD_REGNO with frequency FREQ. */
1234 ira_add_allocno_pref (ira_allocno_t a
, int hard_regno
, int freq
)
1240 if ((pref
= find_allocno_pref (a
, hard_regno
)) != NULL
)
1245 pref
= ira_create_pref (a
, hard_regno
, freq
);
1246 ira_assert (a
!= NULL
);
1247 add_allocno_pref_to_list (pref
);
1250 /* Print info about PREF into file F. */
1252 print_pref (FILE *f
, ira_pref_t pref
)
1254 fprintf (f
, " pref%d:a%d(r%d)<-hr%d@%d\n", pref
->num
,
1255 ALLOCNO_NUM (pref
->allocno
), ALLOCNO_REGNO (pref
->allocno
),
1256 pref
->hard_regno
, pref
->freq
);
1259 /* Print info about PREF into stderr. */
1261 ira_debug_pref (ira_pref_t pref
)
1263 print_pref (stderr
, pref
);
1266 /* Print info about all prefs into file F. */
1268 print_prefs (FILE *f
)
1271 ira_pref_iterator pi
;
1273 FOR_EACH_PREF (pref
, pi
)
1274 print_pref (f
, pref
);
1277 /* Print info about all prefs into stderr. */
1279 ira_debug_prefs (void)
1281 print_prefs (stderr
);
1284 /* Print info about prefs involving allocno A into file F. */
1286 print_allocno_prefs (FILE *f
, ira_allocno_t a
)
1290 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1291 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= pref
->next_pref
)
1292 fprintf (f
, " pref%d:hr%d@%d", pref
->num
, pref
->hard_regno
, pref
->freq
);
1296 /* Print info about prefs involving allocno A into stderr. */
1298 ira_debug_allocno_prefs (ira_allocno_t a
)
1300 print_allocno_prefs (stderr
, a
);
1303 /* The function frees memory allocated for PREF. */
1305 finish_pref (ira_pref_t pref
)
1307 ira_prefs
[pref
->num
] = NULL
;
1308 pool_free (pref_pool
, pref
);
1311 /* Remove PREF from the list of allocno prefs and free memory for
1314 ira_remove_pref (ira_pref_t pref
)
1316 ira_pref_t cpref
, prev
;
1318 if (internal_flag_ira_verbose
> 1 && ira_dump_file
!= NULL
)
1319 fprintf (ira_dump_file
, " Removing pref%d:hr%d@%d\n",
1320 pref
->num
, pref
->hard_regno
, pref
->freq
);
1321 for (prev
= NULL
, cpref
= ALLOCNO_PREFS (pref
->allocno
);
1323 prev
= cpref
, cpref
= cpref
->next_pref
)
1326 ira_assert (cpref
!= NULL
);
1328 ALLOCNO_PREFS (pref
->allocno
) = pref
->next_pref
;
1330 prev
->next_pref
= pref
->next_pref
;
1334 /* Remove all prefs of allocno A. */
1336 ira_remove_allocno_prefs (ira_allocno_t a
)
1338 ira_pref_t pref
, next_pref
;
1340 for (pref
= ALLOCNO_PREFS (a
); pref
!= NULL
; pref
= next_pref
)
1342 next_pref
= pref
->next_pref
;
1345 ALLOCNO_PREFS (a
) = NULL
;
1348 /* Free memory allocated for all prefs. */
1353 ira_pref_iterator pi
;
1355 FOR_EACH_PREF (pref
, pi
)
1357 pref_vec
.release ();
1358 free_alloc_pool (pref_pool
);
1363 /* Pools for copies. */
1364 static alloc_pool copy_pool
;
1366 /* Vec containing references to all created copies. It is a
1367 container of array ira_copies. */
1368 static vec
<ira_copy_t
> copy_vec
;
1370 /* The function initializes data concerning allocno copies. */
1372 initiate_copies (void)
1375 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy
), 100);
1376 copy_vec
.create (get_max_uid ());
1381 /* Return copy connecting A1 and A2 and originated from INSN of
1382 LOOP_TREE_NODE if any. */
1384 find_allocno_copy (ira_allocno_t a1
, ira_allocno_t a2
, rtx insn
,
1385 ira_loop_tree_node_t loop_tree_node
)
1387 ira_copy_t cp
, next_cp
;
1388 ira_allocno_t another_a
;
1390 for (cp
= ALLOCNO_COPIES (a1
); cp
!= NULL
; cp
= next_cp
)
1392 if (cp
->first
== a1
)
1394 next_cp
= cp
->next_first_allocno_copy
;
1395 another_a
= cp
->second
;
1397 else if (cp
->second
== a1
)
1399 next_cp
= cp
->next_second_allocno_copy
;
1400 another_a
= cp
->first
;
1404 if (another_a
== a2
&& cp
->insn
== insn
1405 && cp
->loop_tree_node
== loop_tree_node
)
1411 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1412 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1414 ira_create_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1415 bool constraint_p
, rtx insn
,
1416 ira_loop_tree_node_t loop_tree_node
)
1420 cp
= (ira_copy_t
) pool_alloc (copy_pool
);
1421 cp
->num
= ira_copies_num
;
1423 cp
->second
= second
;
1425 cp
->constraint_p
= constraint_p
;
1427 cp
->loop_tree_node
= loop_tree_node
;
1428 copy_vec
.safe_push (cp
);
1429 ira_copies
= copy_vec
.address ();
1430 ira_copies_num
= copy_vec
.length ();
1434 /* Attach a copy CP to allocnos involved into the copy. */
1436 add_allocno_copy_to_list (ira_copy_t cp
)
1438 ira_allocno_t first
= cp
->first
, second
= cp
->second
;
1440 cp
->prev_first_allocno_copy
= NULL
;
1441 cp
->prev_second_allocno_copy
= NULL
;
1442 cp
->next_first_allocno_copy
= ALLOCNO_COPIES (first
);
1443 if (cp
->next_first_allocno_copy
!= NULL
)
1445 if (cp
->next_first_allocno_copy
->first
== first
)
1446 cp
->next_first_allocno_copy
->prev_first_allocno_copy
= cp
;
1448 cp
->next_first_allocno_copy
->prev_second_allocno_copy
= cp
;
1450 cp
->next_second_allocno_copy
= ALLOCNO_COPIES (second
);
1451 if (cp
->next_second_allocno_copy
!= NULL
)
1453 if (cp
->next_second_allocno_copy
->second
== second
)
1454 cp
->next_second_allocno_copy
->prev_second_allocno_copy
= cp
;
1456 cp
->next_second_allocno_copy
->prev_first_allocno_copy
= cp
;
1458 ALLOCNO_COPIES (first
) = cp
;
1459 ALLOCNO_COPIES (second
) = cp
;
1462 /* Make a copy CP a canonical copy where number of the
1463 first allocno is less than the second one. */
1465 swap_allocno_copy_ends_if_necessary (ira_copy_t cp
)
1470 if (ALLOCNO_NUM (cp
->first
) <= ALLOCNO_NUM (cp
->second
))
1474 cp
->first
= cp
->second
;
1477 temp_cp
= cp
->prev_first_allocno_copy
;
1478 cp
->prev_first_allocno_copy
= cp
->prev_second_allocno_copy
;
1479 cp
->prev_second_allocno_copy
= temp_cp
;
1481 temp_cp
= cp
->next_first_allocno_copy
;
1482 cp
->next_first_allocno_copy
= cp
->next_second_allocno_copy
;
1483 cp
->next_second_allocno_copy
= temp_cp
;
1486 /* Create (or update frequency if the copy already exists) and return
1487 the copy of allocnos FIRST and SECOND with frequency FREQ
1488 corresponding to move insn INSN (if any) and originated from
1491 ira_add_allocno_copy (ira_allocno_t first
, ira_allocno_t second
, int freq
,
1492 bool constraint_p
, rtx insn
,
1493 ira_loop_tree_node_t loop_tree_node
)
1497 if ((cp
= find_allocno_copy (first
, second
, insn
, loop_tree_node
)) != NULL
)
1502 cp
= ira_create_copy (first
, second
, freq
, constraint_p
, insn
,
1504 ira_assert (first
!= NULL
&& second
!= NULL
);
1505 add_allocno_copy_to_list (cp
);
1506 swap_allocno_copy_ends_if_necessary (cp
);
1510 /* Print info about copy CP into file F. */
1512 print_copy (FILE *f
, ira_copy_t cp
)
1514 fprintf (f
, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp
->num
,
1515 ALLOCNO_NUM (cp
->first
), ALLOCNO_REGNO (cp
->first
),
1516 ALLOCNO_NUM (cp
->second
), ALLOCNO_REGNO (cp
->second
), cp
->freq
,
1518 ? "move" : cp
->constraint_p
? "constraint" : "shuffle");
1522 debug (ira_allocno_copy
&ref
)
1524 print_copy (stderr
, &ref
);
1528 debug (ira_allocno_copy
*ptr
)
1533 fprintf (stderr
, "<nil>\n");
1536 /* Print info about copy CP into stderr. */
1538 ira_debug_copy (ira_copy_t cp
)
1540 print_copy (stderr
, cp
);
1543 /* Print info about all copies into file F. */
1545 print_copies (FILE *f
)
1548 ira_copy_iterator ci
;
1550 FOR_EACH_COPY (cp
, ci
)
1554 /* Print info about all copies into stderr. */
1556 ira_debug_copies (void)
1558 print_copies (stderr
);
1561 /* Print info about copies involving allocno A into file F. */
1563 print_allocno_copies (FILE *f
, ira_allocno_t a
)
1565 ira_allocno_t another_a
;
1566 ira_copy_t cp
, next_cp
;
1568 fprintf (f
, " a%d(r%d):", ALLOCNO_NUM (a
), ALLOCNO_REGNO (a
));
1569 for (cp
= ALLOCNO_COPIES (a
); cp
!= NULL
; cp
= next_cp
)
1573 next_cp
= cp
->next_first_allocno_copy
;
1574 another_a
= cp
->second
;
1576 else if (cp
->second
== a
)
1578 next_cp
= cp
->next_second_allocno_copy
;
1579 another_a
= cp
->first
;
1583 fprintf (f
, " cp%d:a%d(r%d)@%d", cp
->num
,
1584 ALLOCNO_NUM (another_a
), ALLOCNO_REGNO (another_a
), cp
->freq
);
1590 debug (ira_allocno
&ref
)
1592 print_allocno_copies (stderr
, &ref
);
1596 debug (ira_allocno
*ptr
)
1601 fprintf (stderr
, "<nil>\n");
1605 /* Print info about copies involving allocno A into stderr. */
1607 ira_debug_allocno_copies (ira_allocno_t a
)
1609 print_allocno_copies (stderr
, a
);
1612 /* The function frees memory allocated for copy CP. */
1614 finish_copy (ira_copy_t cp
)
1616 pool_free (copy_pool
, cp
);
1620 /* Free memory allocated for all copies. */
1622 finish_copies (void)
1625 ira_copy_iterator ci
;
1627 FOR_EACH_COPY (cp
, ci
)
1629 copy_vec
.release ();
1630 free_alloc_pool (copy_pool
);
1635 /* Pools for cost vectors. It is defined only for allocno classes. */
1636 static alloc_pool cost_vector_pool
[N_REG_CLASSES
];
1638 /* The function initiates work with hard register cost vectors. It
1639 creates allocation pool for each allocno class. */
1641 initiate_cost_vectors (void)
1644 enum reg_class aclass
;
1646 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1648 aclass
= ira_allocno_classes
[i
];
1649 cost_vector_pool
[aclass
]
1650 = create_alloc_pool ("cost vectors",
1651 sizeof (int) * ira_class_hard_regs_num
[aclass
],
1656 /* Allocate and return a cost vector VEC for ACLASS. */
1658 ira_allocate_cost_vector (reg_class_t aclass
)
1660 return (int *) pool_alloc (cost_vector_pool
[(int) aclass
]);
1663 /* Free a cost vector VEC for ACLASS. */
1665 ira_free_cost_vector (int *vec
, reg_class_t aclass
)
1667 ira_assert (vec
!= NULL
);
1668 pool_free (cost_vector_pool
[(int) aclass
], vec
);
1671 /* Finish work with hard register cost vectors. Release allocation
1672 pool for each allocno class. */
1674 finish_cost_vectors (void)
1677 enum reg_class aclass
;
1679 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
1681 aclass
= ira_allocno_classes
[i
];
1682 free_alloc_pool (cost_vector_pool
[aclass
]);
1688 /* Compute a post-ordering of the reverse control flow of the loop body
1689 designated by the children nodes of LOOP_NODE, whose body nodes in
1690 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1691 of the reverse loop body.
1693 For the post-order of the reverse CFG, we visit the basic blocks in
1694 LOOP_PREORDER array in the reverse order of where they appear.
1695 This is important: We do not just want to compute a post-order of
1696 the reverse CFG, we want to make a best-guess for a visiting order that
1697 minimizes the number of chain elements per allocno live range. If the
1698 blocks would be visited in a different order, we would still compute a
1699 correct post-ordering but it would be less likely that two nodes
1700 connected by an edge in the CFG are neighbours in the topsort. */
1702 static vec
<ira_loop_tree_node_t
>
1703 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED
,
1704 vec
<ira_loop_tree_node_t
> loop_preorder
)
1706 vec
<ira_loop_tree_node_t
> topsort_nodes
= vNULL
;
1707 unsigned int n_loop_preorder
;
1709 n_loop_preorder
= loop_preorder
.length ();
1710 if (n_loop_preorder
!= 0)
1712 ira_loop_tree_node_t subloop_node
;
1714 auto_vec
<ira_loop_tree_node_t
> dfs_stack
;
1716 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1717 the flag to mark blocks we still have to visit to add them to
1718 our post-order. Define an alias to avoid confusion. */
1719 #define BB_TO_VISIT BB_VISITED
1721 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1723 gcc_checking_assert (! (subloop_node
->bb
->flags
& BB_TO_VISIT
));
1724 subloop_node
->bb
->flags
|= BB_TO_VISIT
;
1727 topsort_nodes
.create (n_loop_preorder
);
1728 dfs_stack
.create (n_loop_preorder
);
1730 FOR_EACH_VEC_ELT_REVERSE (loop_preorder
, i
, subloop_node
)
1732 if (! (subloop_node
->bb
->flags
& BB_TO_VISIT
))
1735 subloop_node
->bb
->flags
&= ~BB_TO_VISIT
;
1736 dfs_stack
.quick_push (subloop_node
);
1737 while (! dfs_stack
.is_empty ())
1742 ira_loop_tree_node_t n
= dfs_stack
.last ();
1743 FOR_EACH_EDGE (e
, ei
, n
->bb
->preds
)
1745 ira_loop_tree_node_t pred_node
;
1746 basic_block pred_bb
= e
->src
;
1748 if (e
->src
== ENTRY_BLOCK_PTR_FOR_FN (cfun
))
1751 pred_node
= IRA_BB_NODE_BY_INDEX (pred_bb
->index
);
1753 && (pred_node
->bb
->flags
& BB_TO_VISIT
))
1755 pred_node
->bb
->flags
&= ~BB_TO_VISIT
;
1756 dfs_stack
.quick_push (pred_node
);
1759 if (n
== dfs_stack
.last ())
1762 topsort_nodes
.quick_push (n
);
1770 gcc_assert (topsort_nodes
.length () == n_loop_preorder
);
1771 return topsort_nodes
;
1774 /* The current loop tree node and its regno allocno map. */
1775 ira_loop_tree_node_t ira_curr_loop_tree_node
;
1776 ira_allocno_t
*ira_curr_regno_allocno_map
;
1778 /* This recursive function traverses loop tree with root LOOP_NODE
1779 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1780 correspondingly in preorder and postorder. The function sets up
1781 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1782 basic block nodes of LOOP_NODE is also processed (before its
1785 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1786 the loop are passed in the *reverse* post-order of the *reverse*
1787 CFG. This is only used by ira_create_allocno_live_ranges, which
1788 wants to visit basic blocks in this order to minimize the number
1789 of elements per live range chain.
1790 Note that the loop tree nodes are still visited in the normal,
1791 forward post-order of the loop tree. */
1794 ira_traverse_loop_tree (bool bb_p
, ira_loop_tree_node_t loop_node
,
1795 void (*preorder_func
) (ira_loop_tree_node_t
),
1796 void (*postorder_func
) (ira_loop_tree_node_t
))
1798 ira_loop_tree_node_t subloop_node
;
1800 ira_assert (loop_node
->bb
== NULL
);
1801 ira_curr_loop_tree_node
= loop_node
;
1802 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1804 if (preorder_func
!= NULL
)
1805 (*preorder_func
) (loop_node
);
1809 auto_vec
<ira_loop_tree_node_t
> loop_preorder
;
1812 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1813 is set up such that nodes in the loop body appear in a pre-order
1814 of their place in the CFG. */
1815 for (subloop_node
= loop_node
->children
;
1816 subloop_node
!= NULL
;
1817 subloop_node
= subloop_node
->next
)
1818 if (subloop_node
->bb
!= NULL
)
1819 loop_preorder
.safe_push (subloop_node
);
1821 if (preorder_func
!= NULL
)
1822 FOR_EACH_VEC_ELT (loop_preorder
, i
, subloop_node
)
1823 (*preorder_func
) (subloop_node
);
1825 if (postorder_func
!= NULL
)
1827 vec
<ira_loop_tree_node_t
> loop_rev_postorder
=
1828 ira_loop_tree_body_rev_postorder (loop_node
, loop_preorder
);
1829 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder
, i
, subloop_node
)
1830 (*postorder_func
) (subloop_node
);
1831 loop_rev_postorder
.release ();
1835 for (subloop_node
= loop_node
->subloops
;
1836 subloop_node
!= NULL
;
1837 subloop_node
= subloop_node
->subloop_next
)
1839 ira_assert (subloop_node
->bb
== NULL
);
1840 ira_traverse_loop_tree (bb_p
, subloop_node
,
1841 preorder_func
, postorder_func
);
1844 ira_curr_loop_tree_node
= loop_node
;
1845 ira_curr_regno_allocno_map
= ira_curr_loop_tree_node
->regno_allocno_map
;
1847 if (postorder_func
!= NULL
)
1848 (*postorder_func
) (loop_node
);
1853 /* The basic block currently being processed. */
1854 static basic_block curr_bb
;
1856 /* This recursive function creates allocnos corresponding to
1857 pseudo-registers containing in X. True OUTPUT_P means that X is
1860 create_insn_allocnos (rtx x
, bool output_p
)
1864 enum rtx_code code
= GET_CODE (x
);
1870 if ((regno
= REGNO (x
)) >= FIRST_PSEUDO_REGISTER
)
1874 if ((a
= ira_curr_regno_allocno_map
[regno
]) == NULL
)
1875 a
= ira_create_allocno (regno
, false, ira_curr_loop_tree_node
);
1877 ALLOCNO_NREFS (a
)++;
1878 ALLOCNO_FREQ (a
) += REG_FREQ_FROM_BB (curr_bb
);
1880 bitmap_set_bit (ira_curr_loop_tree_node
->modified_regnos
, regno
);
1884 else if (code
== SET
)
1886 create_insn_allocnos (SET_DEST (x
), true);
1887 create_insn_allocnos (SET_SRC (x
), false);
1890 else if (code
== CLOBBER
)
1892 create_insn_allocnos (XEXP (x
, 0), true);
1895 else if (code
== MEM
)
1897 create_insn_allocnos (XEXP (x
, 0), false);
1900 else if (code
== PRE_DEC
|| code
== POST_DEC
|| code
== PRE_INC
||
1901 code
== POST_INC
|| code
== POST_MODIFY
|| code
== PRE_MODIFY
)
1903 create_insn_allocnos (XEXP (x
, 0), true);
1904 create_insn_allocnos (XEXP (x
, 0), false);
1908 fmt
= GET_RTX_FORMAT (code
);
1909 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
1912 create_insn_allocnos (XEXP (x
, i
), output_p
);
1913 else if (fmt
[i
] == 'E')
1914 for (j
= 0; j
< XVECLEN (x
, i
); j
++)
1915 create_insn_allocnos (XVECEXP (x
, i
, j
), output_p
);
1919 /* Create allocnos corresponding to pseudo-registers living in the
1920 basic block represented by the corresponding loop tree node
1923 create_bb_allocnos (ira_loop_tree_node_t bb_node
)
1930 curr_bb
= bb
= bb_node
->bb
;
1931 ira_assert (bb
!= NULL
);
1932 FOR_BB_INSNS_REVERSE (bb
, insn
)
1933 if (NONDEBUG_INSN_P (insn
))
1934 create_insn_allocnos (PATTERN (insn
), false);
1935 /* It might be a allocno living through from one subloop to
1937 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb
), FIRST_PSEUDO_REGISTER
, i
, bi
)
1938 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1939 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1942 /* Create allocnos corresponding to pseudo-registers living on edge E
1943 (a loop entry or exit). Also mark the allocnos as living on the
1946 create_loop_allocnos (edge e
)
1949 bitmap live_in_regs
, border_allocnos
;
1951 ira_loop_tree_node_t parent
;
1953 live_in_regs
= df_get_live_in (e
->dest
);
1954 border_allocnos
= ira_curr_loop_tree_node
->border_allocnos
;
1955 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e
->src
),
1956 FIRST_PSEUDO_REGISTER
, i
, bi
)
1957 if (bitmap_bit_p (live_in_regs
, i
))
1959 if (ira_curr_regno_allocno_map
[i
] == NULL
)
1961 /* The order of creations is important for right
1962 ira_regno_allocno_map. */
1963 if ((parent
= ira_curr_loop_tree_node
->parent
) != NULL
1964 && parent
->regno_allocno_map
[i
] == NULL
)
1965 ira_create_allocno (i
, false, parent
);
1966 ira_create_allocno (i
, false, ira_curr_loop_tree_node
);
1968 bitmap_set_bit (border_allocnos
,
1969 ALLOCNO_NUM (ira_curr_regno_allocno_map
[i
]));
1973 /* Create allocnos corresponding to pseudo-registers living in loop
1974 represented by the corresponding loop tree node LOOP_NODE. This
1975 function is called by ira_traverse_loop_tree. */
1977 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node
)
1979 if (loop_node
->bb
!= NULL
)
1980 create_bb_allocnos (loop_node
);
1981 else if (loop_node
!= ira_loop_tree_root
)
1988 ira_assert (current_loops
!= NULL
);
1989 FOR_EACH_EDGE (e
, ei
, loop_node
->loop
->header
->preds
)
1990 if (e
->src
!= loop_node
->loop
->latch
)
1991 create_loop_allocnos (e
);
1993 edges
= get_loop_exit_edges (loop_node
->loop
);
1994 FOR_EACH_VEC_ELT (edges
, i
, e
)
1995 create_loop_allocnos (e
);
2000 /* Propagate information about allocnos modified inside the loop given
2001 by its LOOP_TREE_NODE to its parent. */
2003 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node
)
2005 if (loop_tree_node
== ira_loop_tree_root
)
2007 ira_assert (loop_tree_node
->bb
== NULL
);
2008 bitmap_ior_into (loop_tree_node
->parent
->modified_regnos
,
2009 loop_tree_node
->modified_regnos
);
2012 /* Propagate new info about allocno A (see comments about accumulated
2013 info in allocno definition) to the corresponding allocno on upper
2014 loop tree level. So allocnos on upper levels accumulate
2015 information about the corresponding allocnos in nested regions.
2016 The new info means allocno info finally calculated in this
2019 propagate_allocno_info (void)
2022 ira_allocno_t a
, parent_a
;
2023 ira_loop_tree_node_t parent
;
2024 enum reg_class aclass
;
2026 if (flag_ira_region
!= IRA_REGION_ALL
2027 && flag_ira_region
!= IRA_REGION_MIXED
)
2029 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2030 for (a
= ira_regno_allocno_map
[i
];
2032 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2033 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) != NULL
2034 && (parent_a
= parent
->regno_allocno_map
[i
]) != NULL
2035 /* There are no caps yet at this point. So use
2036 border_allocnos to find allocnos for the propagation. */
2037 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a
)->border_allocnos
,
2040 if (! ALLOCNO_BAD_SPILL_P (a
))
2041 ALLOCNO_BAD_SPILL_P (parent_a
) = false;
2042 ALLOCNO_NREFS (parent_a
) += ALLOCNO_NREFS (a
);
2043 ALLOCNO_FREQ (parent_a
) += ALLOCNO_FREQ (a
);
2044 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
2045 merge_hard_reg_conflicts (a
, parent_a
, true);
2046 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
2047 += ALLOCNO_CALLS_CROSSED_NUM (a
);
2048 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
2049 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (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 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
)
2431 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a
);
2432 if (! ALLOCNO_BAD_SPILL_P (from_a
))
2433 ALLOCNO_BAD_SPILL_P (a
) = false;
2434 aclass
= ALLOCNO_CLASS (from_a
);
2435 ira_assert (aclass
== ALLOCNO_CLASS (a
));
2436 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a
), aclass
,
2437 ALLOCNO_HARD_REG_COSTS (from_a
));
2438 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
2440 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a
));
2441 ALLOCNO_CLASS_COST (a
) += ALLOCNO_CLASS_COST (from_a
);
2442 ALLOCNO_MEMORY_COST (a
) += ALLOCNO_MEMORY_COST (from_a
);
2445 /* Remove allocnos from loops removed from the allocation
2448 remove_unnecessary_allocnos (void)
2451 bool merged_p
, rebuild_p
;
2452 ira_allocno_t a
, prev_a
, next_a
, parent_a
;
2453 ira_loop_tree_node_t a_node
, parent
;
2456 regno_allocnos
= NULL
;
2457 for (regno
= max_reg_num () - 1; regno
>= FIRST_PSEUDO_REGISTER
; regno
--)
2460 for (prev_a
= NULL
, a
= ira_regno_allocno_map
[regno
];
2464 next_a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
);
2465 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2466 if (! a_node
->to_remove_p
)
2470 for (parent
= a_node
->parent
;
2471 (parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
2472 && parent
->to_remove_p
;
2473 parent
= parent
->parent
)
2475 if (parent_a
== NULL
)
2477 /* There are no allocnos with the same regno in
2478 upper region -- just move the allocno to the
2481 ALLOCNO_LOOP_TREE_NODE (a
) = parent
;
2482 parent
->regno_allocno_map
[regno
] = a
;
2483 bitmap_set_bit (parent
->all_allocnos
, ALLOCNO_NUM (a
));
2488 /* Remove the allocno and update info of allocno in
2489 the upper region. */
2491 ira_regno_allocno_map
[regno
] = next_a
;
2493 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a
) = next_a
;
2494 move_allocno_live_ranges (a
, parent_a
);
2496 propagate_some_info_from_allocno (parent_a
, a
);
2497 /* Remove it from the corresponding regno allocno
2498 map to avoid info propagation of subsequent
2499 allocno into this already removed allocno. */
2500 a_node
->regno_allocno_map
[regno
] = NULL
;
2501 ira_remove_allocno_prefs (a
);
2507 /* We need to restore the order in regno allocno list. */
2509 if (regno_allocnos
== NULL
)
2511 = (ira_allocno_t
*) ira_allocate (sizeof (ira_allocno_t
)
2512 * ira_allocnos_num
);
2513 ira_rebuild_regno_allocno_list (regno
);
2517 ira_rebuild_start_finish_chains ();
2518 if (regno_allocnos
!= NULL
)
2519 ira_free (regno_allocnos
);
2522 /* Remove allocnos from all loops but the root. */
2524 remove_low_level_allocnos (void)
2527 bool merged_p
, propagate_p
;
2528 ira_allocno_t a
, top_a
;
2529 ira_loop_tree_node_t a_node
, parent
;
2530 ira_allocno_iterator ai
;
2533 FOR_EACH_ALLOCNO (a
, ai
)
2535 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2536 if (a_node
== ira_loop_tree_root
|| ALLOCNO_CAP_MEMBER (a
) != NULL
)
2538 regno
= ALLOCNO_REGNO (a
);
2539 if ((top_a
= ira_loop_tree_root
->regno_allocno_map
[regno
]) == NULL
)
2541 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
2542 ira_loop_tree_root
->regno_allocno_map
[regno
] = a
;
2545 propagate_p
= a_node
->parent
->regno_allocno_map
[regno
] == NULL
;
2546 /* Remove the allocno and update info of allocno in the upper
2548 move_allocno_live_ranges (a
, top_a
);
2551 propagate_some_info_from_allocno (top_a
, a
);
2553 FOR_EACH_ALLOCNO (a
, ai
)
2555 a_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2556 if (a_node
== ira_loop_tree_root
)
2558 parent
= a_node
->parent
;
2559 regno
= ALLOCNO_REGNO (a
);
2560 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2561 ira_assert (ALLOCNO_CAP (a
) != NULL
);
2562 else if (ALLOCNO_CAP (a
) == NULL
)
2563 ira_assert (parent
->regno_allocno_map
[regno
] != NULL
);
2565 FOR_EACH_ALLOCNO (a
, ai
)
2567 regno
= ALLOCNO_REGNO (a
);
2568 if (ira_loop_tree_root
->regno_allocno_map
[regno
] == a
)
2571 ira_allocno_object_iterator oi
;
2573 ira_regno_allocno_map
[regno
] = a
;
2574 ALLOCNO_NEXT_REGNO_ALLOCNO (a
) = NULL
;
2575 ALLOCNO_CAP_MEMBER (a
) = NULL
;
2576 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2577 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj
),
2578 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
));
2580 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a
))
2581 ALLOCNO_NO_STACK_REG_P (a
) = true;
2586 ira_remove_allocno_prefs (a
);
2591 ira_rebuild_start_finish_chains ();
2594 /* Remove loops from consideration. We remove all loops except for
2595 root if ALL_P or loops for which a separate allocation will not
2596 improve the result. We have to do this after allocno creation and
2597 their costs and allocno class evaluation because only after that
2598 the register pressure can be known and is calculated. */
2600 remove_unnecessary_regions (bool all_p
)
2602 if (current_loops
== NULL
)
2605 mark_all_loops_for_removal ();
2607 mark_loops_for_removal ();
2608 children_vec
.create (last_basic_block
+ number_of_loops (cfun
));
2609 removed_loop_vec
.create (last_basic_block
+ number_of_loops (cfun
));
2610 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root
);
2611 children_vec
.release ();
2613 remove_low_level_allocnos ();
2615 remove_unnecessary_allocnos ();
2616 while (removed_loop_vec
.length () > 0)
2617 finish_loop_tree_node (removed_loop_vec
.pop ());
2618 removed_loop_vec
.release ();
2623 /* At this point true value of allocno attribute bad_spill_p means
2624 that there is an insn where allocno occurs and where the allocno
2625 can not be used as memory. The function updates the attribute, now
2626 it can be true only for allocnos which can not be used as memory in
2627 an insn and in whose live ranges there is other allocno deaths.
2628 Spilling allocnos with true value will not improve the code because
2629 it will not make other allocnos colorable and additional reloads
2630 for the corresponding pseudo will be generated in reload pass for
2631 each insn it occurs.
2633 This is a trick mentioned in one classic article of Chaitin etc
2634 which is frequently omitted in other implementations of RA based on
2637 update_bad_spill_attribute (void)
2641 ira_allocno_iterator ai
;
2642 ira_allocno_object_iterator aoi
;
2645 enum reg_class aclass
;
2646 bitmap_head dead_points
[N_REG_CLASSES
];
2648 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2650 aclass
= ira_allocno_classes
[i
];
2651 bitmap_initialize (&dead_points
[aclass
], ®_obstack
);
2653 FOR_EACH_ALLOCNO (a
, ai
)
2655 aclass
= ALLOCNO_CLASS (a
);
2656 if (aclass
== NO_REGS
)
2658 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2659 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2660 bitmap_set_bit (&dead_points
[aclass
], r
->finish
);
2662 FOR_EACH_ALLOCNO (a
, ai
)
2664 aclass
= ALLOCNO_CLASS (a
);
2665 if (aclass
== NO_REGS
)
2667 if (! ALLOCNO_BAD_SPILL_P (a
))
2669 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, aoi
)
2671 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
2673 for (i
= r
->start
+ 1; i
< r
->finish
; i
++)
2674 if (bitmap_bit_p (&dead_points
[aclass
], i
))
2681 ALLOCNO_BAD_SPILL_P (a
) = false;
2686 for (i
= 0; i
< ira_allocno_classes_num
; i
++)
2688 aclass
= ira_allocno_classes
[i
];
2689 bitmap_clear (&dead_points
[aclass
]);
2695 /* Set up minimal and maximal live range points for allocnos. */
2697 setup_min_max_allocno_live_range_point (void)
2700 ira_allocno_t a
, parent_a
, cap
;
2701 ira_allocno_iterator ai
;
2702 #ifdef ENABLE_IRA_CHECKING
2703 ira_object_iterator oi
;
2707 ira_loop_tree_node_t parent
;
2709 FOR_EACH_ALLOCNO (a
, ai
)
2711 int n
= ALLOCNO_NUM_OBJECTS (a
);
2713 for (i
= 0; i
< n
; i
++)
2715 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
2716 r
= OBJECT_LIVE_RANGES (obj
);
2719 OBJECT_MAX (obj
) = r
->finish
;
2720 for (; r
->next
!= NULL
; r
= r
->next
)
2722 OBJECT_MIN (obj
) = r
->start
;
2725 for (i
= max_reg_num () - 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
2726 for (a
= ira_regno_allocno_map
[i
];
2728 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
2731 int n
= ALLOCNO_NUM_OBJECTS (a
);
2733 for (j
= 0; j
< n
; j
++)
2735 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
2736 ira_object_t parent_obj
;
2738 if (OBJECT_MAX (obj
) < 0)
2740 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
2741 /* Accumulation of range info. */
2742 if (ALLOCNO_CAP (a
) != NULL
)
2744 for (cap
= ALLOCNO_CAP (a
); cap
!= NULL
; cap
= ALLOCNO_CAP (cap
))
2746 ira_object_t cap_obj
= ALLOCNO_OBJECT (cap
, j
);
2747 if (OBJECT_MAX (cap_obj
) < OBJECT_MAX (obj
))
2748 OBJECT_MAX (cap_obj
) = OBJECT_MAX (obj
);
2749 if (OBJECT_MIN (cap_obj
) > OBJECT_MIN (obj
))
2750 OBJECT_MIN (cap_obj
) = OBJECT_MIN (obj
);
2754 if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
)
2756 parent_a
= parent
->regno_allocno_map
[i
];
2757 parent_obj
= ALLOCNO_OBJECT (parent_a
, j
);
2758 if (OBJECT_MAX (parent_obj
) < OBJECT_MAX (obj
))
2759 OBJECT_MAX (parent_obj
) = OBJECT_MAX (obj
);
2760 if (OBJECT_MIN (parent_obj
) > OBJECT_MIN (obj
))
2761 OBJECT_MIN (parent_obj
) = OBJECT_MIN (obj
);
2764 #ifdef ENABLE_IRA_CHECKING
2765 FOR_EACH_OBJECT (obj
, oi
)
2767 if ((0 <= OBJECT_MIN (obj
) && OBJECT_MIN (obj
) <= ira_max_point
)
2768 && (0 <= OBJECT_MAX (obj
) && OBJECT_MAX (obj
) <= ira_max_point
))
2775 /* Sort allocnos according to their live ranges. Allocnos with
2776 smaller allocno class are put first unless we use priority
2777 coloring. Allocnos with the same class are ordered according
2778 their start (min). Allocnos with the same start are ordered
2779 according their finish (max). */
2781 object_range_compare_func (const void *v1p
, const void *v2p
)
2784 ira_object_t obj1
= *(const ira_object_t
*) v1p
;
2785 ira_object_t obj2
= *(const ira_object_t
*) v2p
;
2786 ira_allocno_t a1
= OBJECT_ALLOCNO (obj1
);
2787 ira_allocno_t a2
= OBJECT_ALLOCNO (obj2
);
2789 if ((diff
= OBJECT_MIN (obj1
) - OBJECT_MIN (obj2
)) != 0)
2791 if ((diff
= OBJECT_MAX (obj1
) - OBJECT_MAX (obj2
)) != 0)
2793 return ALLOCNO_NUM (a1
) - ALLOCNO_NUM (a2
);
2796 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2798 sort_conflict_id_map (void)
2802 ira_allocno_iterator ai
;
2805 FOR_EACH_ALLOCNO (a
, ai
)
2807 ira_allocno_object_iterator oi
;
2810 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
2811 ira_object_id_map
[num
++] = obj
;
2813 qsort (ira_object_id_map
, num
, sizeof (ira_object_t
),
2814 object_range_compare_func
);
2815 for (i
= 0; i
< num
; i
++)
2817 ira_object_t obj
= ira_object_id_map
[i
];
2819 gcc_assert (obj
!= NULL
);
2820 OBJECT_CONFLICT_ID (obj
) = i
;
2822 for (i
= num
; i
< ira_objects_num
; i
++)
2823 ira_object_id_map
[i
] = NULL
;
2826 /* Set up minimal and maximal conflict ids of allocnos with which
2827 given allocno can conflict. */
2829 setup_min_max_conflict_allocno_ids (void)
2832 int i
, j
, min
, max
, start
, finish
, first_not_finished
, filled_area_start
;
2833 int *live_range_min
, *last_lived
;
2834 int word0_min
, word0_max
;
2836 ira_allocno_iterator ai
;
2838 live_range_min
= (int *) ira_allocate (sizeof (int) * ira_objects_num
);
2840 first_not_finished
= -1;
2841 for (i
= 0; i
< ira_objects_num
; i
++)
2843 ira_object_t obj
= ira_object_id_map
[i
];
2848 a
= OBJECT_ALLOCNO (obj
);
2852 aclass
= ALLOCNO_CLASS (a
);
2854 first_not_finished
= i
;
2858 start
= OBJECT_MIN (obj
);
2859 /* If we skip an allocno, the allocno with smaller ids will
2860 be also skipped because of the secondary sorting the
2861 range finishes (see function
2862 object_range_compare_func). */
2863 while (first_not_finished
< i
2864 && start
> OBJECT_MAX (ira_object_id_map
2865 [first_not_finished
]))
2866 first_not_finished
++;
2867 min
= first_not_finished
;
2870 /* We could increase min further in this case but it is good
2873 live_range_min
[i
] = OBJECT_MIN (obj
);
2874 OBJECT_MIN (obj
) = min
;
2876 last_lived
= (int *) ira_allocate (sizeof (int) * ira_max_point
);
2878 filled_area_start
= -1;
2879 for (i
= ira_objects_num
- 1; i
>= 0; i
--)
2881 ira_object_t obj
= ira_object_id_map
[i
];
2886 a
= OBJECT_ALLOCNO (obj
);
2889 aclass
= ALLOCNO_CLASS (a
);
2890 for (j
= 0; j
< ira_max_point
; j
++)
2892 filled_area_start
= ira_max_point
;
2894 min
= live_range_min
[i
];
2895 finish
= OBJECT_MAX (obj
);
2896 max
= last_lived
[finish
];
2898 /* We could decrease max further in this case but it is good
2900 max
= OBJECT_CONFLICT_ID (obj
) - 1;
2901 OBJECT_MAX (obj
) = max
;
2902 /* In filling, we can go further A range finish to recognize
2903 intersection quickly because if the finish of subsequently
2904 processed allocno (it has smaller conflict id) range is
2905 further A range finish than they are definitely intersected
2906 (the reason for this is the allocnos with bigger conflict id
2907 have their range starts not smaller than allocnos with
2909 for (j
= min
; j
< filled_area_start
; j
++)
2911 filled_area_start
= min
;
2913 ira_free (last_lived
);
2914 ira_free (live_range_min
);
2916 /* For allocnos with more than one object, we may later record extra conflicts in
2917 subobject 0 that we cannot really know about here.
2918 For now, simply widen the min/max range of these subobjects. */
2920 word0_min
= INT_MAX
;
2921 word0_max
= INT_MIN
;
2923 FOR_EACH_ALLOCNO (a
, ai
)
2925 int n
= ALLOCNO_NUM_OBJECTS (a
);
2930 obj0
= ALLOCNO_OBJECT (a
, 0);
2931 if (OBJECT_CONFLICT_ID (obj0
) < word0_min
)
2932 word0_min
= OBJECT_CONFLICT_ID (obj0
);
2933 if (OBJECT_CONFLICT_ID (obj0
) > word0_max
)
2934 word0_max
= OBJECT_CONFLICT_ID (obj0
);
2936 FOR_EACH_ALLOCNO (a
, ai
)
2938 int n
= ALLOCNO_NUM_OBJECTS (a
);
2943 obj0
= ALLOCNO_OBJECT (a
, 0);
2944 if (OBJECT_MIN (obj0
) > word0_min
)
2945 OBJECT_MIN (obj0
) = word0_min
;
2946 if (OBJECT_MAX (obj0
) < word0_max
)
2947 OBJECT_MAX (obj0
) = word0_max
;
2957 ira_allocno_iterator ai
;
2958 ira_loop_tree_node_t loop_tree_node
;
2960 FOR_EACH_ALLOCNO (a
, ai
)
2962 if (ALLOCNO_LOOP_TREE_NODE (a
) == ira_loop_tree_root
)
2964 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
2965 create_cap_allocno (a
);
2966 else if (ALLOCNO_CAP (a
) == NULL
)
2968 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
2969 if (!bitmap_bit_p (loop_tree_node
->border_allocnos
, ALLOCNO_NUM (a
)))
2970 create_cap_allocno (a
);
2977 /* The page contains code transforming more one region internal
2978 representation (IR) to one region IR which is necessary for reload.
2979 This transformation is called IR flattening. We might just rebuild
2980 the IR for one region but we don't do it because it takes a lot of
2983 /* Map: regno -> allocnos which will finally represent the regno for
2984 IR with one region. */
2985 static ira_allocno_t
*regno_top_level_allocno_map
;
2987 /* Find the allocno that corresponds to A at a level one higher up in the
2988 loop tree. Returns NULL if A is a cap, or if it has no parent. */
2990 ira_parent_allocno (ira_allocno_t a
)
2992 ira_loop_tree_node_t parent
;
2994 if (ALLOCNO_CAP (a
) != NULL
)
2997 parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3001 return parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)];
3004 /* Find the allocno that corresponds to A at a level one higher up in the
3005 loop tree. If ALLOCNO_CAP is set for A, return that. */
3007 ira_parent_or_cap_allocno (ira_allocno_t a
)
3009 if (ALLOCNO_CAP (a
) != NULL
)
3010 return ALLOCNO_CAP (a
);
3012 return ira_parent_allocno (a
);
3015 /* Process all allocnos originated from pseudo REGNO and copy live
3016 ranges, hard reg conflicts, and allocno stack reg attributes from
3017 low level allocnos to final allocnos which are destinations of
3018 removed stores at a loop exit. Return true if we copied live
3021 copy_info_to_removed_store_destinations (int regno
)
3024 ira_allocno_t parent_a
= NULL
;
3025 ira_loop_tree_node_t parent
;
3029 for (a
= ira_regno_allocno_map
[regno
];
3031 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3033 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))])
3034 /* This allocno will be removed. */
3037 /* Caps will be removed. */
3038 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3039 for (parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
;
3041 parent
= parent
->parent
)
3042 if ((parent_a
= parent
->regno_allocno_map
[regno
]) == NULL
3044 == regno_top_level_allocno_map
[REGNO
3045 (allocno_emit_reg (parent_a
))]
3046 && ALLOCNO_EMIT_DATA (parent_a
)->mem_optimized_dest_p
))
3048 if (parent
== NULL
|| parent_a
== NULL
)
3051 copy_allocno_live_ranges (a
, parent_a
);
3052 merge_hard_reg_conflicts (a
, parent_a
, true);
3054 ALLOCNO_CALL_FREQ (parent_a
) += ALLOCNO_CALL_FREQ (a
);
3055 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3056 += ALLOCNO_CALLS_CROSSED_NUM (a
);
3057 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3058 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3059 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3060 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3066 /* Flatten the IR. In other words, this function transforms IR as if
3067 it were built with one region (without loops). We could make it
3068 much simpler by rebuilding IR with one region, but unfortunately it
3069 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3070 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3071 IRA_MAX_POINT before emitting insns on the loop borders. */
3073 ira_flattening (int max_regno_before_emit
, int ira_max_point_before_emit
)
3078 bool new_pseudos_p
, merged_p
, mem_dest_p
;
3080 enum reg_class aclass
;
3081 ira_allocno_t a
, parent_a
, first
, second
, node_first
, node_second
;
3083 ira_loop_tree_node_t node
;
3085 ira_allocno_iterator ai
;
3086 ira_copy_iterator ci
;
3088 regno_top_level_allocno_map
3089 = (ira_allocno_t
*) ira_allocate (max_reg_num ()
3090 * sizeof (ira_allocno_t
));
3091 memset (regno_top_level_allocno_map
, 0,
3092 max_reg_num () * sizeof (ira_allocno_t
));
3093 new_pseudos_p
= merged_p
= false;
3094 FOR_EACH_ALLOCNO (a
, ai
)
3096 ira_allocno_object_iterator oi
;
3099 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3100 /* Caps are not in the regno allocno maps and they are never
3101 will be transformed into allocnos existing after IR
3104 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3105 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj
),
3106 OBJECT_CONFLICT_HARD_REGS (obj
));
3108 ALLOCNO_TOTAL_NO_STACK_REG_P (a
) = ALLOCNO_NO_STACK_REG_P (a
);
3111 /* Fix final allocno attributes. */
3112 for (i
= max_regno_before_emit
- 1; i
>= FIRST_PSEUDO_REGISTER
; i
--)
3115 for (a
= ira_regno_allocno_map
[i
];
3117 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
3119 ira_emit_data_t parent_data
, data
= ALLOCNO_EMIT_DATA (a
);
3121 ira_assert (ALLOCNO_CAP_MEMBER (a
) == NULL
);
3122 if (data
->somewhere_renamed_p
)
3123 new_pseudos_p
= true;
3124 parent_a
= ira_parent_allocno (a
);
3125 if (parent_a
== NULL
)
3127 ALLOCNO_COPIES (a
) = NULL
;
3128 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3131 ira_assert (ALLOCNO_CAP_MEMBER (parent_a
) == NULL
);
3133 if (data
->mem_optimized_dest
!= NULL
)
3135 parent_data
= ALLOCNO_EMIT_DATA (parent_a
);
3136 if (REGNO (data
->reg
) == REGNO (parent_data
->reg
))
3138 merge_hard_reg_conflicts (a
, parent_a
, true);
3139 move_allocno_live_ranges (a
, parent_a
);
3141 parent_data
->mem_optimized_dest_p
3142 = (parent_data
->mem_optimized_dest_p
3143 || data
->mem_optimized_dest_p
);
3146 new_pseudos_p
= true;
3149 ALLOCNO_NREFS (parent_a
) -= ALLOCNO_NREFS (a
);
3150 ALLOCNO_FREQ (parent_a
) -= ALLOCNO_FREQ (a
);
3151 ALLOCNO_CALL_FREQ (parent_a
) -= ALLOCNO_CALL_FREQ (a
);
3152 ALLOCNO_CALLS_CROSSED_NUM (parent_a
)
3153 -= ALLOCNO_CALLS_CROSSED_NUM (a
);
3154 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a
)
3155 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a
);
3156 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a
)
3157 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a
);
3158 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a
) >= 0
3159 && ALLOCNO_NREFS (parent_a
) >= 0
3160 && ALLOCNO_FREQ (parent_a
) >= 0);
3161 aclass
= ALLOCNO_CLASS (parent_a
);
3162 hard_regs_num
= ira_class_hard_regs_num
[aclass
];
3163 if (ALLOCNO_HARD_REG_COSTS (a
) != NULL
3164 && ALLOCNO_HARD_REG_COSTS (parent_a
) != NULL
)
3165 for (j
= 0; j
< hard_regs_num
; j
++)
3166 ALLOCNO_HARD_REG_COSTS (parent_a
)[j
]
3167 -= ALLOCNO_HARD_REG_COSTS (a
)[j
];
3168 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) != NULL
3169 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
) != NULL
)
3170 for (j
= 0; j
< hard_regs_num
; j
++)
3171 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a
)[j
]
3172 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[j
];
3173 ALLOCNO_CLASS_COST (parent_a
)
3174 -= ALLOCNO_CLASS_COST (a
);
3175 ALLOCNO_MEMORY_COST (parent_a
) -= ALLOCNO_MEMORY_COST (a
);
3176 parent_a
= ira_parent_allocno (parent_a
);
3177 if (parent_a
== NULL
)
3180 ALLOCNO_COPIES (a
) = NULL
;
3181 regno_top_level_allocno_map
[REGNO (data
->reg
)] = a
;
3183 if (mem_dest_p
&& copy_info_to_removed_store_destinations (i
))
3186 ira_assert (new_pseudos_p
|| ira_max_point_before_emit
== ira_max_point
);
3187 if (merged_p
|| ira_max_point_before_emit
!= ira_max_point
)
3188 ira_rebuild_start_finish_chains ();
3191 sparseset objects_live
;
3193 /* Rebuild conflicts. */
3194 FOR_EACH_ALLOCNO (a
, ai
)
3196 ira_allocno_object_iterator oi
;
3199 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3200 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3202 FOR_EACH_ALLOCNO_OBJECT (a
, obj
, oi
)
3204 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3205 ira_assert (r
->object
== obj
);
3206 clear_conflicts (obj
);
3209 objects_live
= sparseset_alloc (ira_objects_num
);
3210 for (i
= 0; i
< ira_max_point
; i
++)
3212 for (r
= ira_start_point_ranges
[i
]; r
!= NULL
; r
= r
->start_next
)
3214 ira_object_t obj
= r
->object
;
3216 a
= OBJECT_ALLOCNO (obj
);
3217 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3218 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3221 aclass
= ALLOCNO_CLASS (a
);
3222 sparseset_set_bit (objects_live
, OBJECT_CONFLICT_ID (obj
));
3223 EXECUTE_IF_SET_IN_SPARSESET (objects_live
, n
)
3225 ira_object_t live_obj
= ira_object_id_map
[n
];
3226 ira_allocno_t live_a
= OBJECT_ALLOCNO (live_obj
);
3227 enum reg_class live_aclass
= ALLOCNO_CLASS (live_a
);
3229 if (ira_reg_classes_intersect_p
[aclass
][live_aclass
]
3230 /* Don't set up conflict for the allocno with itself. */
3232 ira_add_conflict (obj
, live_obj
);
3236 for (r
= ira_finish_point_ranges
[i
]; r
!= NULL
; r
= r
->finish_next
)
3237 sparseset_clear_bit (objects_live
, OBJECT_CONFLICT_ID (r
->object
));
3239 sparseset_free (objects_live
);
3240 compress_conflict_vecs ();
3242 /* Mark some copies for removing and change allocnos in the rest
3244 FOR_EACH_COPY (cp
, ci
)
3246 if (ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
3247 || ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
)
3249 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3251 (ira_dump_file
, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3252 cp
->num
, ALLOCNO_CAP_MEMBER (cp
->first
) != NULL
? 'c' : 'a',
3253 ALLOCNO_NUM (cp
->first
),
3254 REGNO (allocno_emit_reg (cp
->first
)),
3255 ALLOCNO_CAP_MEMBER (cp
->second
) != NULL
? 'c' : 'a',
3256 ALLOCNO_NUM (cp
->second
),
3257 REGNO (allocno_emit_reg (cp
->second
)));
3258 cp
->loop_tree_node
= NULL
;
3262 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->first
))];
3264 = regno_top_level_allocno_map
[REGNO (allocno_emit_reg (cp
->second
))];
3265 node
= cp
->loop_tree_node
;
3267 keep_p
= true; /* It copy generated in ira-emit.c. */
3270 /* Check that the copy was not propagated from level on
3271 which we will have different pseudos. */
3272 node_first
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->first
)];
3273 node_second
= node
->regno_allocno_map
[ALLOCNO_REGNO (cp
->second
)];
3274 keep_p
= ((REGNO (allocno_emit_reg (first
))
3275 == REGNO (allocno_emit_reg (node_first
)))
3276 && (REGNO (allocno_emit_reg (second
))
3277 == REGNO (allocno_emit_reg (node_second
))));
3281 cp
->loop_tree_node
= ira_loop_tree_root
;
3283 cp
->second
= second
;
3287 cp
->loop_tree_node
= NULL
;
3288 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3289 fprintf (ira_dump_file
, " Remove cp%d:a%dr%d-a%dr%d\n",
3290 cp
->num
, ALLOCNO_NUM (cp
->first
),
3291 REGNO (allocno_emit_reg (cp
->first
)),
3292 ALLOCNO_NUM (cp
->second
),
3293 REGNO (allocno_emit_reg (cp
->second
)));
3296 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3297 FOR_EACH_ALLOCNO (a
, ai
)
3299 if (a
!= regno_top_level_allocno_map
[REGNO (allocno_emit_reg (a
))]
3300 || ALLOCNO_CAP_MEMBER (a
) != NULL
)
3302 if (internal_flag_ira_verbose
> 4 && ira_dump_file
!= NULL
)
3303 fprintf (ira_dump_file
, " Remove a%dr%d\n",
3304 ALLOCNO_NUM (a
), REGNO (allocno_emit_reg (a
)));
3305 ira_remove_allocno_prefs (a
);
3309 ALLOCNO_LOOP_TREE_NODE (a
) = ira_loop_tree_root
;
3310 ALLOCNO_REGNO (a
) = REGNO (allocno_emit_reg (a
));
3311 ALLOCNO_CAP (a
) = NULL
;
3312 /* Restore updated costs for assignments from reload. */
3313 ALLOCNO_UPDATED_MEMORY_COST (a
) = ALLOCNO_MEMORY_COST (a
);
3314 ALLOCNO_UPDATED_CLASS_COST (a
) = ALLOCNO_CLASS_COST (a
);
3315 if (! ALLOCNO_ASSIGNED_P (a
))
3316 ira_free_allocno_updated_costs (a
);
3317 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a
) == NULL
);
3318 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a
) == NULL
);
3320 /* Remove unnecessary copies. */
3321 FOR_EACH_COPY (cp
, ci
)
3323 if (cp
->loop_tree_node
== NULL
)
3325 ira_copies
[cp
->num
] = NULL
;
3330 (ALLOCNO_LOOP_TREE_NODE (cp
->first
) == ira_loop_tree_root
3331 && ALLOCNO_LOOP_TREE_NODE (cp
->second
) == ira_loop_tree_root
);
3332 add_allocno_copy_to_list (cp
);
3333 swap_allocno_copy_ends_if_necessary (cp
);
3335 rebuild_regno_allocno_maps ();
3336 if (ira_max_point
!= ira_max_point_before_emit
)
3337 ira_compress_allocno_live_ranges ();
3338 ira_free (regno_top_level_allocno_map
);
3343 #ifdef ENABLE_IRA_CHECKING
3344 /* Check creation of all allocnos. Allocnos on lower levels should
3345 have allocnos or caps on all upper levels. */
3347 check_allocno_creation (void)
3350 ira_allocno_iterator ai
;
3351 ira_loop_tree_node_t loop_tree_node
;
3353 FOR_EACH_ALLOCNO (a
, ai
)
3355 loop_tree_node
= ALLOCNO_LOOP_TREE_NODE (a
);
3356 ira_assert (bitmap_bit_p (loop_tree_node
->all_allocnos
,
3358 if (loop_tree_node
== ira_loop_tree_root
)
3360 if (ALLOCNO_CAP_MEMBER (a
) != NULL
)
3361 ira_assert (ALLOCNO_CAP (a
) != NULL
);
3362 else if (ALLOCNO_CAP (a
) == NULL
)
3363 ira_assert (loop_tree_node
->parent
3364 ->regno_allocno_map
[ALLOCNO_REGNO (a
)] != NULL
3365 && bitmap_bit_p (loop_tree_node
->border_allocnos
,
3371 /* Identify allocnos which prefer a register class with a single hard register.
3372 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3373 less likely to use the preferred singleton register. */
3375 update_conflict_hard_reg_costs (void)
3378 ira_allocno_iterator ai
;
3381 FOR_EACH_ALLOCNO (a
, ai
)
3383 reg_class_t aclass
= ALLOCNO_CLASS (a
);
3384 reg_class_t pref
= reg_preferred_class (ALLOCNO_REGNO (a
));
3385 int singleton
= ira_class_singleton
[pref
][ALLOCNO_MODE (a
)];
3388 index
= ira_class_hard_reg_index
[(int) aclass
][singleton
];
3391 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a
) == NULL
3392 || ALLOCNO_HARD_REG_COSTS (a
) == NULL
)
3395 for (i
= ira_class_hard_regs_num
[(int) aclass
] - 1; i
>= 0; i
--)
3396 if (ALLOCNO_HARD_REG_COSTS (a
)[i
] > ALLOCNO_CLASS_COST (a
)
3397 && min
> ALLOCNO_HARD_REG_COSTS (a
)[i
])
3398 min
= ALLOCNO_HARD_REG_COSTS (a
)[i
];
3401 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a
),
3403 ALLOCNO_CONFLICT_HARD_REG_COSTS (a
)[index
]
3404 -= min
- ALLOCNO_CLASS_COST (a
);
3408 /* Create a internal representation (IR) for IRA (allocnos, copies,
3409 loop tree nodes). The function returns TRUE if we generate loop
3410 structure (besides nodes representing all function and the basic
3411 blocks) for regional allocation. A true return means that we
3412 really need to flatten IR before the reload. */
3419 initiate_cost_vectors ();
3420 initiate_allocnos ();
3423 create_loop_tree_nodes ();
3427 create_allocno_objects ();
3428 ira_create_allocno_live_ranges ();
3429 remove_unnecessary_regions (false);
3430 ira_compress_allocno_live_ranges ();
3431 update_bad_spill_attribute ();
3432 loops_p
= more_one_region_p ();
3435 propagate_allocno_info ();
3438 ira_tune_allocno_costs ();
3439 #ifdef ENABLE_IRA_CHECKING
3440 check_allocno_creation ();
3442 setup_min_max_allocno_live_range_point ();
3443 sort_conflict_id_map ();
3444 setup_min_max_conflict_allocno_ids ();
3445 ira_build_conflicts ();
3446 update_conflict_hard_reg_costs ();
3447 if (! ira_conflicts_p
)
3450 ira_allocno_iterator ai
;
3452 /* Remove all regions but root one. */
3455 remove_unnecessary_regions (true);
3458 /* We don't save hard registers around calls for fast allocation
3459 -- add caller clobbered registers as conflicting ones to
3460 allocno crossing calls. */
3461 FOR_EACH_ALLOCNO (a
, ai
)
3462 if (ALLOCNO_CALLS_CROSSED_NUM (a
) != 0)
3463 ior_hard_reg_conflicts (a
, &call_used_reg_set
);
3465 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3466 print_copies (ira_dump_file
);
3467 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
3468 print_prefs (ira_dump_file
);
3469 if (internal_flag_ira_verbose
> 0 && ira_dump_file
!= NULL
)
3474 ira_allocno_iterator ai
;
3479 FOR_EACH_ALLOCNO (a
, ai
)
3481 int j
, nobj
= ALLOCNO_NUM_OBJECTS (a
);
3485 for (j
= 0; j
< nobj
; j
++)
3487 ira_object_t obj
= ALLOCNO_OBJECT (a
, j
);
3488 n
+= OBJECT_NUM_CONFLICTS (obj
);
3489 for (r
= OBJECT_LIVE_RANGES (obj
); r
!= NULL
; r
= r
->next
)
3493 fprintf (ira_dump_file
, " regions=%d, blocks=%d, points=%d\n",
3494 current_loops
== NULL
? 1 : number_of_loops (cfun
),
3495 n_basic_blocks_for_fn (cfun
), ira_max_point
);
3496 fprintf (ira_dump_file
,
3497 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3498 ira_allocnos_num
, nr_big
, ira_copies_num
, n
, nr
);
3503 /* Release the data created by function ira_build. */
3507 finish_loop_tree_nodes ();
3511 finish_cost_vectors ();
3512 ira_finish_allocno_live_ranges ();