PR sanitizer/65400
[official-gcc.git] / gcc / ira-build.c
blob189f340800aacf29b031e784d44816f1fa841d39
1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
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
15 for more details.
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/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "tm_p.h"
27 #include "target.h"
28 #include "regs.h"
29 #include "flags.h"
30 #include "hard-reg-set.h"
31 #include "predict.h"
32 #include "vec.h"
33 #include "hashtab.h"
34 #include "hash-set.h"
35 #include "machmode.h"
36 #include "input.h"
37 #include "function.h"
38 #include "dominance.h"
39 #include "cfg.h"
40 #include "basic-block.h"
41 #include "insn-config.h"
42 #include "recog.h"
43 #include "diagnostic-core.h"
44 #include "params.h"
45 #include "df.h"
46 #include "reload.h"
47 #include "sparseset.h"
48 #include "ira-int.h"
49 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */
51 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
52 ira_loop_tree_node_t);
54 /* The root of the loop tree corresponding to the all function. */
55 ira_loop_tree_node_t ira_loop_tree_root;
57 /* Height of the loop tree. */
58 int ira_loop_tree_height;
60 /* All nodes representing basic blocks are referred through the
61 following array. We can not use basic block member `aux' for this
62 because it is used for insertion of insns on edges. */
63 ira_loop_tree_node_t ira_bb_nodes;
65 /* All nodes representing loops are referred through the following
66 array. */
67 ira_loop_tree_node_t ira_loop_nodes;
69 /* And size of the ira_loop_nodes array. */
70 unsigned int ira_loop_nodes_count;
72 /* Map regno -> allocnos with given regno (see comments for
73 allocno member `next_regno_allocno'). */
74 ira_allocno_t *ira_regno_allocno_map;
76 /* Array of references to all allocnos. The order number of the
77 allocno corresponds to the index in the array. Removed allocnos
78 have NULL element value. */
79 ira_allocno_t *ira_allocnos;
81 /* Sizes of the previous array. */
82 int ira_allocnos_num;
84 /* Count of conflict record structures we've created, used when creating
85 a new conflict id. */
86 int ira_objects_num;
88 /* Map a conflict id to its conflict record. */
89 ira_object_t *ira_object_id_map;
91 /* Array of references to all allocno preferences. The order number
92 of the preference corresponds to the index in the array. */
93 ira_pref_t *ira_prefs;
95 /* Size of the previous array. */
96 int ira_prefs_num;
98 /* Array of references to all copies. The order number of the copy
99 corresponds to the index in the array. Removed copies have NULL
100 element value. */
101 ira_copy_t *ira_copies;
103 /* Size of the previous array. */
104 int ira_copies_num;
108 /* LAST_BASIC_BLOCK before generating additional insns because of live
109 range splitting. Emitting insns on a critical edge creates a new
110 basic block. */
111 static int last_basic_block_before_change;
113 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
114 the member loop_num. */
115 static void
116 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
118 int max_regno = max_reg_num ();
120 node->regno_allocno_map
121 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
122 memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
123 memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
124 node->all_allocnos = ira_allocate_bitmap ();
125 node->modified_regnos = ira_allocate_bitmap ();
126 node->border_allocnos = ira_allocate_bitmap ();
127 node->local_copies = ira_allocate_bitmap ();
128 node->loop_num = loop_num;
129 node->children = NULL;
130 node->subloops = NULL;
134 /* The following function allocates the loop tree nodes. If
135 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
136 the root which corresponds the all function) will be not allocated
137 but nodes will still be allocated for basic blocks. */
138 static void
139 create_loop_tree_nodes (void)
141 unsigned int i, j;
142 bool skip_p;
143 edge_iterator ei;
144 edge e;
145 vec<edge> edges;
146 loop_p loop;
148 ira_bb_nodes
149 = ((struct ira_loop_tree_node *)
150 ira_allocate (sizeof (struct ira_loop_tree_node)
151 * last_basic_block_for_fn (cfun)));
152 last_basic_block_before_change = last_basic_block_for_fn (cfun);
153 for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
155 ira_bb_nodes[i].regno_allocno_map = NULL;
156 memset (ira_bb_nodes[i].reg_pressure, 0,
157 sizeof (ira_bb_nodes[i].reg_pressure));
158 ira_bb_nodes[i].all_allocnos = NULL;
159 ira_bb_nodes[i].modified_regnos = NULL;
160 ira_bb_nodes[i].border_allocnos = NULL;
161 ira_bb_nodes[i].local_copies = NULL;
163 if (current_loops == NULL)
165 ira_loop_nodes_count = 1;
166 ira_loop_nodes = ((struct ira_loop_tree_node *)
167 ira_allocate (sizeof (struct ira_loop_tree_node)));
168 init_loop_tree_node (ira_loop_nodes, 0);
169 return;
171 ira_loop_nodes_count = number_of_loops (cfun);
172 ira_loop_nodes = ((struct ira_loop_tree_node *)
173 ira_allocate (sizeof (struct ira_loop_tree_node)
174 * ira_loop_nodes_count));
175 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
177 if (loop_outer (loop) != NULL)
179 ira_loop_nodes[i].regno_allocno_map = NULL;
180 skip_p = false;
181 FOR_EACH_EDGE (e, ei, loop->header->preds)
182 if (e->src != loop->latch
183 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
185 skip_p = true;
186 break;
188 if (skip_p)
189 continue;
190 edges = get_loop_exit_edges (loop);
191 FOR_EACH_VEC_ELT (edges, j, e)
192 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
194 skip_p = true;
195 break;
197 edges.release ();
198 if (skip_p)
199 continue;
201 init_loop_tree_node (&ira_loop_nodes[i], loop->num);
205 /* The function returns TRUE if there are more one allocation
206 region. */
207 static bool
208 more_one_region_p (void)
210 unsigned int i;
211 loop_p loop;
213 if (current_loops != NULL)
214 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
215 if (ira_loop_nodes[i].regno_allocno_map != NULL
216 && ira_loop_tree_root != &ira_loop_nodes[i])
217 return true;
218 return false;
221 /* Free the loop tree node of a loop. */
222 static void
223 finish_loop_tree_node (ira_loop_tree_node_t loop)
225 if (loop->regno_allocno_map != NULL)
227 ira_assert (loop->bb == NULL);
228 ira_free_bitmap (loop->local_copies);
229 ira_free_bitmap (loop->border_allocnos);
230 ira_free_bitmap (loop->modified_regnos);
231 ira_free_bitmap (loop->all_allocnos);
232 ira_free (loop->regno_allocno_map);
233 loop->regno_allocno_map = NULL;
237 /* Free the loop tree nodes. */
238 static void
239 finish_loop_tree_nodes (void)
241 unsigned int i;
243 for (i = 0; i < ira_loop_nodes_count; i++)
244 finish_loop_tree_node (&ira_loop_nodes[i]);
245 ira_free (ira_loop_nodes);
246 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
248 if (ira_bb_nodes[i].local_copies != NULL)
249 ira_free_bitmap (ira_bb_nodes[i].local_copies);
250 if (ira_bb_nodes[i].border_allocnos != NULL)
251 ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
252 if (ira_bb_nodes[i].modified_regnos != NULL)
253 ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
254 if (ira_bb_nodes[i].all_allocnos != NULL)
255 ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
256 if (ira_bb_nodes[i].regno_allocno_map != NULL)
257 ira_free (ira_bb_nodes[i].regno_allocno_map);
259 ira_free (ira_bb_nodes);
264 /* The following recursive function adds LOOP to the loop tree
265 hierarchy. LOOP is added only once. If LOOP is NULL we adding
266 loop designating the whole function when CFG loops are not
267 built. */
268 static void
269 add_loop_to_tree (struct loop *loop)
271 int loop_num;
272 struct loop *parent;
273 ira_loop_tree_node_t loop_node, parent_node;
275 /* We can not use loop node access macros here because of potential
276 checking and because the nodes are not initialized enough
277 yet. */
278 if (loop != NULL && loop_outer (loop) != NULL)
279 add_loop_to_tree (loop_outer (loop));
280 loop_num = loop != NULL ? loop->num : 0;
281 if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
282 && ira_loop_nodes[loop_num].children == NULL)
284 /* We have not added loop node to the tree yet. */
285 loop_node = &ira_loop_nodes[loop_num];
286 loop_node->loop = loop;
287 loop_node->bb = NULL;
288 if (loop == NULL)
289 parent = NULL;
290 else
292 for (parent = loop_outer (loop);
293 parent != NULL;
294 parent = loop_outer (parent))
295 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
296 break;
298 if (parent == NULL)
300 loop_node->next = NULL;
301 loop_node->subloop_next = NULL;
302 loop_node->parent = NULL;
304 else
306 parent_node = &ira_loop_nodes[parent->num];
307 loop_node->next = parent_node->children;
308 parent_node->children = loop_node;
309 loop_node->subloop_next = parent_node->subloops;
310 parent_node->subloops = loop_node;
311 loop_node->parent = parent_node;
316 /* The following recursive function sets up levels of nodes of the
317 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
318 The function returns maximal value of level in the tree + 1. */
319 static int
320 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
322 int height, max_height;
323 ira_loop_tree_node_t subloop_node;
325 ira_assert (loop_node->bb == NULL);
326 loop_node->level = level;
327 max_height = level + 1;
328 for (subloop_node = loop_node->subloops;
329 subloop_node != NULL;
330 subloop_node = subloop_node->subloop_next)
332 ira_assert (subloop_node->bb == NULL);
333 height = setup_loop_tree_level (subloop_node, level + 1);
334 if (height > max_height)
335 max_height = height;
337 return max_height;
340 /* Create the loop tree. The algorithm is designed to provide correct
341 order of loops (they are ordered by their last loop BB) and basic
342 blocks in the chain formed by member next. */
343 static void
344 form_loop_tree (void)
346 basic_block bb;
347 struct loop *parent;
348 ira_loop_tree_node_t bb_node, loop_node;
350 /* We can not use loop/bb node access macros because of potential
351 checking and because the nodes are not initialized enough
352 yet. */
353 FOR_EACH_BB_FN (bb, cfun)
355 bb_node = &ira_bb_nodes[bb->index];
356 bb_node->bb = bb;
357 bb_node->loop = NULL;
358 bb_node->subloops = NULL;
359 bb_node->children = NULL;
360 bb_node->subloop_next = NULL;
361 bb_node->next = NULL;
362 if (current_loops == NULL)
363 parent = NULL;
364 else
366 for (parent = bb->loop_father;
367 parent != NULL;
368 parent = loop_outer (parent))
369 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
370 break;
372 add_loop_to_tree (parent);
373 loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
374 bb_node->next = loop_node->children;
375 bb_node->parent = loop_node;
376 loop_node->children = bb_node;
378 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
379 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
380 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
385 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
386 tree nodes. */
387 static void
388 rebuild_regno_allocno_maps (void)
390 unsigned int l;
391 int max_regno, regno;
392 ira_allocno_t a;
393 ira_loop_tree_node_t loop_tree_node;
394 loop_p loop;
395 ira_allocno_iterator ai;
397 ira_assert (current_loops != NULL);
398 max_regno = max_reg_num ();
399 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
400 if (ira_loop_nodes[l].regno_allocno_map != NULL)
402 ira_free (ira_loop_nodes[l].regno_allocno_map);
403 ira_loop_nodes[l].regno_allocno_map
404 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
405 * max_regno);
406 memset (ira_loop_nodes[l].regno_allocno_map, 0,
407 sizeof (ira_allocno_t) * max_regno);
409 ira_free (ira_regno_allocno_map);
410 ira_regno_allocno_map
411 = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
412 memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
413 FOR_EACH_ALLOCNO (a, ai)
415 if (ALLOCNO_CAP_MEMBER (a) != NULL)
416 /* Caps are not in the regno allocno maps. */
417 continue;
418 regno = ALLOCNO_REGNO (a);
419 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
420 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
421 ira_regno_allocno_map[regno] = a;
422 if (loop_tree_node->regno_allocno_map[regno] == NULL)
423 /* Remember that we can create temporary allocnos to break
424 cycles in register shuffle. */
425 loop_tree_node->regno_allocno_map[regno] = a;
430 /* Pools for allocnos, allocno live ranges and objects. */
431 static alloc_pool allocno_pool, live_range_pool, object_pool;
433 /* Vec containing references to all created allocnos. It is a
434 container of array allocnos. */
435 static vec<ira_allocno_t> allocno_vec;
437 /* Vec containing references to all created ira_objects. It is a
438 container of ira_object_id_map. */
439 static vec<ira_object_t> ira_object_id_map_vec;
441 /* Initialize data concerning allocnos. */
442 static void
443 initiate_allocnos (void)
445 live_range_pool
446 = create_alloc_pool ("live ranges",
447 sizeof (struct live_range), 100);
448 allocno_pool
449 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
450 object_pool
451 = create_alloc_pool ("objects", sizeof (struct ira_object), 100);
452 allocno_vec.create (max_reg_num () * 2);
453 ira_allocnos = NULL;
454 ira_allocnos_num = 0;
455 ira_objects_num = 0;
456 ira_object_id_map_vec.create (max_reg_num () * 2);
457 ira_object_id_map = NULL;
458 ira_regno_allocno_map
459 = (ira_allocno_t *) ira_allocate (max_reg_num ()
460 * sizeof (ira_allocno_t));
461 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
464 /* Create and return an object corresponding to a new allocno A. */
465 static ira_object_t
466 ira_create_object (ira_allocno_t a, int subword)
468 enum reg_class aclass = ALLOCNO_CLASS (a);
469 ira_object_t obj = (ira_object_t) pool_alloc (object_pool);
471 OBJECT_ALLOCNO (obj) = a;
472 OBJECT_SUBWORD (obj) = subword;
473 OBJECT_CONFLICT_ID (obj) = ira_objects_num;
474 OBJECT_CONFLICT_VEC_P (obj) = false;
475 OBJECT_CONFLICT_ARRAY (obj) = NULL;
476 OBJECT_NUM_CONFLICTS (obj) = 0;
477 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
478 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
479 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
480 reg_class_contents[aclass]);
481 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
482 reg_class_contents[aclass]);
483 OBJECT_MIN (obj) = INT_MAX;
484 OBJECT_MAX (obj) = -1;
485 OBJECT_LIVE_RANGES (obj) = NULL;
487 ira_object_id_map_vec.safe_push (obj);
488 ira_object_id_map
489 = ira_object_id_map_vec.address ();
490 ira_objects_num = ira_object_id_map_vec.length ();
492 return obj;
495 /* Create and return the allocno corresponding to REGNO in
496 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
497 same regno if CAP_P is FALSE. */
498 ira_allocno_t
499 ira_create_allocno (int regno, bool cap_p,
500 ira_loop_tree_node_t loop_tree_node)
502 ira_allocno_t a;
504 a = (ira_allocno_t) pool_alloc (allocno_pool);
505 ALLOCNO_REGNO (a) = regno;
506 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
507 if (! cap_p)
509 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
510 ira_regno_allocno_map[regno] = a;
511 if (loop_tree_node->regno_allocno_map[regno] == NULL)
512 /* Remember that we can create temporary allocnos to break
513 cycles in register shuffle on region borders (see
514 ira-emit.c). */
515 loop_tree_node->regno_allocno_map[regno] = a;
517 ALLOCNO_CAP (a) = NULL;
518 ALLOCNO_CAP_MEMBER (a) = NULL;
519 ALLOCNO_NUM (a) = ira_allocnos_num;
520 bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
521 ALLOCNO_NREFS (a) = 0;
522 ALLOCNO_FREQ (a) = 0;
523 ALLOCNO_HARD_REGNO (a) = -1;
524 ALLOCNO_CALL_FREQ (a) = 0;
525 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
526 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
527 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
528 #ifdef STACK_REGS
529 ALLOCNO_NO_STACK_REG_P (a) = false;
530 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
531 #endif
532 ALLOCNO_DONT_REASSIGN_P (a) = false;
533 ALLOCNO_BAD_SPILL_P (a) = false;
534 ALLOCNO_ASSIGNED_P (a) = false;
535 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
536 ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
537 ALLOCNO_PREFS (a) = NULL;
538 ALLOCNO_COPIES (a) = NULL;
539 ALLOCNO_HARD_REG_COSTS (a) = NULL;
540 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
541 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
542 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
543 ALLOCNO_CLASS (a) = NO_REGS;
544 ALLOCNO_UPDATED_CLASS_COST (a) = 0;
545 ALLOCNO_CLASS_COST (a) = 0;
546 ALLOCNO_MEMORY_COST (a) = 0;
547 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
548 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
549 ALLOCNO_NUM_OBJECTS (a) = 0;
551 ALLOCNO_ADD_DATA (a) = NULL;
552 allocno_vec.safe_push (a);
553 ira_allocnos = allocno_vec.address ();
554 ira_allocnos_num = allocno_vec.length ();
556 return a;
559 /* Set up register class for A and update its conflict hard
560 registers. */
561 void
562 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
564 ira_allocno_object_iterator oi;
565 ira_object_t obj;
567 ALLOCNO_CLASS (a) = aclass;
568 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
570 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
571 reg_class_contents[aclass]);
572 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
573 reg_class_contents[aclass]);
577 /* Determine the number of objects we should associate with allocno A
578 and allocate them. */
579 void
580 ira_create_allocno_objects (ira_allocno_t a)
582 machine_mode mode = ALLOCNO_MODE (a);
583 enum reg_class aclass = ALLOCNO_CLASS (a);
584 int n = ira_reg_class_max_nregs[aclass][mode];
585 int i;
587 if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
588 n = 1;
590 ALLOCNO_NUM_OBJECTS (a) = n;
591 for (i = 0; i < n; i++)
592 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
595 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
596 ALLOCNO_OBJECT structures. This must be called after the allocno
597 classes are known. */
598 static void
599 create_allocno_objects (void)
601 ira_allocno_t a;
602 ira_allocno_iterator ai;
604 FOR_EACH_ALLOCNO (a, ai)
605 ira_create_allocno_objects (a);
608 /* Merge hard register conflict information for all objects associated with
609 allocno TO into the corresponding objects associated with FROM.
610 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
611 static void
612 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
613 bool total_only)
615 int i;
616 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
617 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
619 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
620 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
622 if (!total_only)
623 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj),
624 OBJECT_CONFLICT_HARD_REGS (from_obj));
625 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj),
626 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj));
628 #ifdef STACK_REGS
629 if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
630 ALLOCNO_NO_STACK_REG_P (to) = true;
631 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
632 ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
633 #endif
636 /* Update hard register conflict information for all objects associated with
637 A to include the regs in SET. */
638 void
639 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set)
641 ira_allocno_object_iterator i;
642 ira_object_t obj;
644 FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
646 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set);
647 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set);
651 /* Return TRUE if a conflict vector with NUM elements is more
652 profitable than a conflict bit vector for OBJ. */
653 bool
654 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
656 int nw;
657 int max = OBJECT_MAX (obj);
658 int min = OBJECT_MIN (obj);
660 if (max < min)
661 /* We prefer a bit vector in such case because it does not result
662 in allocation. */
663 return false;
665 nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
666 return (2 * sizeof (ira_object_t) * (num + 1)
667 < 3 * nw * sizeof (IRA_INT_TYPE));
670 /* Allocates and initialize the conflict vector of OBJ for NUM
671 conflicting objects. */
672 void
673 ira_allocate_conflict_vec (ira_object_t obj, int num)
675 int size;
676 ira_object_t *vec;
678 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
679 num++; /* for NULL end marker */
680 size = sizeof (ira_object_t) * num;
681 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
682 vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
683 vec[0] = NULL;
684 OBJECT_NUM_CONFLICTS (obj) = 0;
685 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
686 OBJECT_CONFLICT_VEC_P (obj) = true;
689 /* Allocate and initialize the conflict bit vector of OBJ. */
690 static void
691 allocate_conflict_bit_vec (ira_object_t obj)
693 unsigned int size;
695 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
696 size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
697 / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
698 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
699 memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
700 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
701 OBJECT_CONFLICT_VEC_P (obj) = false;
704 /* Allocate and initialize the conflict vector or conflict bit vector
705 of OBJ for NUM conflicting allocnos whatever is more profitable. */
706 void
707 ira_allocate_object_conflicts (ira_object_t obj, int num)
709 if (ira_conflict_vector_profitable_p (obj, num))
710 ira_allocate_conflict_vec (obj, num);
711 else
712 allocate_conflict_bit_vec (obj);
715 /* Add OBJ2 to the conflicts of OBJ1. */
716 static void
717 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
719 int num;
720 unsigned int size;
722 if (OBJECT_CONFLICT_VEC_P (obj1))
724 ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
725 int curr_num = OBJECT_NUM_CONFLICTS (obj1);
726 num = curr_num + 2;
727 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
729 ira_object_t *newvec;
730 size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
731 newvec = (ira_object_t *) ira_allocate (size);
732 memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
733 ira_free (vec);
734 vec = newvec;
735 OBJECT_CONFLICT_ARRAY (obj1) = vec;
736 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
738 vec[num - 2] = obj2;
739 vec[num - 1] = NULL;
740 OBJECT_NUM_CONFLICTS (obj1)++;
742 else
744 int nw, added_head_nw, id;
745 IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
747 id = OBJECT_CONFLICT_ID (obj2);
748 if (OBJECT_MIN (obj1) > id)
750 /* Expand head of the bit vector. */
751 added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
752 nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
753 size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
754 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
756 memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
757 vec, nw * sizeof (IRA_INT_TYPE));
758 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
760 else
762 size
763 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
764 vec = (IRA_INT_TYPE *) ira_allocate (size);
765 memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
766 OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
767 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
768 memset ((char *) vec
769 + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
770 0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
771 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
772 OBJECT_CONFLICT_ARRAY (obj1) = vec;
773 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
775 OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
777 else if (OBJECT_MAX (obj1) < id)
779 nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
780 size = nw * sizeof (IRA_INT_TYPE);
781 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
783 /* Expand tail of the bit vector. */
784 size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
785 vec = (IRA_INT_TYPE *) ira_allocate (size);
786 memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
787 memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
788 0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
789 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
790 OBJECT_CONFLICT_ARRAY (obj1) = vec;
791 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
793 OBJECT_MAX (obj1) = id;
795 SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
799 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
800 static void
801 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
803 add_to_conflicts (obj1, obj2);
804 add_to_conflicts (obj2, obj1);
807 /* Clear all conflicts of OBJ. */
808 static void
809 clear_conflicts (ira_object_t obj)
811 if (OBJECT_CONFLICT_VEC_P (obj))
813 OBJECT_NUM_CONFLICTS (obj) = 0;
814 OBJECT_CONFLICT_VEC (obj)[0] = NULL;
816 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
818 int nw;
820 nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
821 memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
825 /* The array used to find duplications in conflict vectors of
826 allocnos. */
827 static int *conflict_check;
829 /* The value used to mark allocation presence in conflict vector of
830 the current allocno. */
831 static int curr_conflict_check_tick;
833 /* Remove duplications in conflict vector of OBJ. */
834 static void
835 compress_conflict_vec (ira_object_t obj)
837 ira_object_t *vec, conflict_obj;
838 int i, j;
840 ira_assert (OBJECT_CONFLICT_VEC_P (obj));
841 vec = OBJECT_CONFLICT_VEC (obj);
842 curr_conflict_check_tick++;
843 for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
845 int id = OBJECT_CONFLICT_ID (conflict_obj);
846 if (conflict_check[id] != curr_conflict_check_tick)
848 conflict_check[id] = curr_conflict_check_tick;
849 vec[j++] = conflict_obj;
852 OBJECT_NUM_CONFLICTS (obj) = j;
853 vec[j] = NULL;
856 /* Remove duplications in conflict vectors of all allocnos. */
857 static void
858 compress_conflict_vecs (void)
860 ira_object_t obj;
861 ira_object_iterator oi;
863 conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
864 memset (conflict_check, 0, sizeof (int) * ira_objects_num);
865 curr_conflict_check_tick = 0;
866 FOR_EACH_OBJECT (obj, oi)
868 if (OBJECT_CONFLICT_VEC_P (obj))
869 compress_conflict_vec (obj);
871 ira_free (conflict_check);
874 /* This recursive function outputs allocno A and if it is a cap the
875 function outputs its members. */
876 void
877 ira_print_expanded_allocno (ira_allocno_t a)
879 basic_block bb;
881 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
882 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
883 fprintf (ira_dump_file, ",b%d", bb->index);
884 else
885 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
886 if (ALLOCNO_CAP_MEMBER (a) != NULL)
888 fprintf (ira_dump_file, ":");
889 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
891 fprintf (ira_dump_file, ")");
894 /* Create and return the cap representing allocno A in the
895 parent loop. */
896 static ira_allocno_t
897 create_cap_allocno (ira_allocno_t a)
899 ira_allocno_t cap;
900 ira_loop_tree_node_t parent;
901 enum reg_class aclass;
903 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
904 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
905 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
906 ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
907 aclass = ALLOCNO_CLASS (a);
908 ira_set_allocno_class (cap, aclass);
909 ira_create_allocno_objects (cap);
910 ALLOCNO_CAP_MEMBER (cap) = a;
911 ALLOCNO_CAP (a) = cap;
912 ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
913 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
914 ira_allocate_and_copy_costs
915 (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
916 ira_allocate_and_copy_costs
917 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
918 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
919 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
920 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
921 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
922 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
924 merge_hard_reg_conflicts (a, cap, false);
926 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
927 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
928 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap),
929 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
930 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
932 fprintf (ira_dump_file, " Creating cap ");
933 ira_print_expanded_allocno (cap);
934 fprintf (ira_dump_file, "\n");
936 return cap;
939 /* Create and return a live range for OBJECT with given attributes. */
940 live_range_t
941 ira_create_live_range (ira_object_t obj, int start, int finish,
942 live_range_t next)
944 live_range_t p;
946 p = (live_range_t) pool_alloc (live_range_pool);
947 p->object = obj;
948 p->start = start;
949 p->finish = finish;
950 p->next = next;
951 return p;
954 /* Create a new live range for OBJECT and queue it at the head of its
955 live range list. */
956 void
957 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
959 live_range_t p;
960 p = ira_create_live_range (object, start, finish,
961 OBJECT_LIVE_RANGES (object));
962 OBJECT_LIVE_RANGES (object) = p;
965 /* Copy allocno live range R and return the result. */
966 static live_range_t
967 copy_live_range (live_range_t r)
969 live_range_t p;
971 p = (live_range_t) pool_alloc (live_range_pool);
972 *p = *r;
973 return p;
976 /* Copy allocno live range list given by its head R and return the
977 result. */
978 live_range_t
979 ira_copy_live_range_list (live_range_t r)
981 live_range_t p, first, last;
983 if (r == NULL)
984 return NULL;
985 for (first = last = NULL; r != NULL; r = r->next)
987 p = copy_live_range (r);
988 if (first == NULL)
989 first = p;
990 else
991 last->next = p;
992 last = p;
994 return first;
997 /* Merge ranges R1 and R2 and returns the result. The function
998 maintains the order of ranges and tries to minimize number of the
999 result ranges. */
1000 live_range_t
1001 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
1003 live_range_t first, last, temp;
1005 if (r1 == NULL)
1006 return r2;
1007 if (r2 == NULL)
1008 return r1;
1009 for (first = last = NULL; r1 != NULL && r2 != NULL;)
1011 if (r1->start < r2->start)
1013 temp = r1;
1014 r1 = r2;
1015 r2 = temp;
1017 if (r1->start <= r2->finish + 1)
1019 /* Intersected ranges: merge r1 and r2 into r1. */
1020 r1->start = r2->start;
1021 if (r1->finish < r2->finish)
1022 r1->finish = r2->finish;
1023 temp = r2;
1024 r2 = r2->next;
1025 ira_finish_live_range (temp);
1026 if (r2 == NULL)
1028 /* To try to merge with subsequent ranges in r1. */
1029 r2 = r1->next;
1030 r1->next = NULL;
1033 else
1035 /* Add r1 to the result. */
1036 if (first == NULL)
1037 first = last = r1;
1038 else
1040 last->next = r1;
1041 last = r1;
1043 r1 = r1->next;
1044 if (r1 == NULL)
1046 /* To try to merge with subsequent ranges in r2. */
1047 r1 = r2->next;
1048 r2->next = NULL;
1052 if (r1 != NULL)
1054 if (first == NULL)
1055 first = r1;
1056 else
1057 last->next = r1;
1058 ira_assert (r1->next == NULL);
1060 else if (r2 != NULL)
1062 if (first == NULL)
1063 first = r2;
1064 else
1065 last->next = r2;
1066 ira_assert (r2->next == NULL);
1068 else
1070 ira_assert (last->next == NULL);
1072 return first;
1075 /* Return TRUE if live ranges R1 and R2 intersect. */
1076 bool
1077 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1079 /* Remember the live ranges are always kept ordered. */
1080 while (r1 != NULL && r2 != NULL)
1082 if (r1->start > r2->finish)
1083 r1 = r1->next;
1084 else if (r2->start > r1->finish)
1085 r2 = r2->next;
1086 else
1087 return true;
1089 return false;
1092 /* Free allocno live range R. */
1093 void
1094 ira_finish_live_range (live_range_t r)
1096 pool_free (live_range_pool, r);
1099 /* Free list of allocno live ranges starting with R. */
1100 void
1101 ira_finish_live_range_list (live_range_t r)
1103 live_range_t next_r;
1105 for (; r != NULL; r = next_r)
1107 next_r = r->next;
1108 ira_finish_live_range (r);
1112 /* Free updated register costs of allocno A. */
1113 void
1114 ira_free_allocno_updated_costs (ira_allocno_t a)
1116 enum reg_class aclass;
1118 aclass = ALLOCNO_CLASS (a);
1119 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1120 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1121 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1122 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1123 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1124 aclass);
1125 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1128 /* Free and nullify all cost vectors allocated earlier for allocno
1129 A. */
1130 static void
1131 ira_free_allocno_costs (ira_allocno_t a)
1133 enum reg_class aclass = ALLOCNO_CLASS (a);
1134 ira_object_t obj;
1135 ira_allocno_object_iterator oi;
1137 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1139 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1140 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1141 if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1142 ira_free (OBJECT_CONFLICT_ARRAY (obj));
1143 pool_free (object_pool, obj);
1146 ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1147 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1148 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1149 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1150 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1151 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1152 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1153 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1154 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1155 aclass);
1156 ALLOCNO_HARD_REG_COSTS (a) = NULL;
1157 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1158 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1159 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1162 /* Free the memory allocated for allocno A. */
1163 static void
1164 finish_allocno (ira_allocno_t a)
1166 ira_free_allocno_costs (a);
1167 pool_free (allocno_pool, a);
1170 /* Free the memory allocated for all allocnos. */
1171 static void
1172 finish_allocnos (void)
1174 ira_allocno_t a;
1175 ira_allocno_iterator ai;
1177 FOR_EACH_ALLOCNO (a, ai)
1178 finish_allocno (a);
1179 ira_free (ira_regno_allocno_map);
1180 ira_object_id_map_vec.release ();
1181 allocno_vec.release ();
1182 free_alloc_pool (allocno_pool);
1183 free_alloc_pool (object_pool);
1184 free_alloc_pool (live_range_pool);
1189 /* Pools for allocno preferences. */
1190 static alloc_pool pref_pool;
1192 /* Vec containing references to all created preferences. It is a
1193 container of array ira_prefs. */
1194 static vec<ira_pref_t> pref_vec;
1196 /* The function initializes data concerning allocno prefs. */
1197 static void
1198 initiate_prefs (void)
1200 pref_pool
1201 = create_alloc_pool ("prefs", sizeof (struct ira_allocno_pref), 100);
1202 pref_vec.create (get_max_uid ());
1203 ira_prefs = NULL;
1204 ira_prefs_num = 0;
1207 /* Return pref for A and HARD_REGNO if any. */
1208 static ira_pref_t
1209 find_allocno_pref (ira_allocno_t a, int hard_regno)
1211 ira_pref_t pref;
1213 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1214 if (pref->allocno == a && pref->hard_regno == hard_regno)
1215 return pref;
1216 return NULL;
1219 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1220 ira_pref_t
1221 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1223 ira_pref_t pref;
1225 pref = (ira_pref_t) pool_alloc (pref_pool);
1226 pref->num = ira_prefs_num;
1227 pref->allocno = a;
1228 pref->hard_regno = hard_regno;
1229 pref->freq = freq;
1230 pref_vec.safe_push (pref);
1231 ira_prefs = pref_vec.address ();
1232 ira_prefs_num = pref_vec.length ();
1233 return pref;
1236 /* Attach a pref PREF to the corresponding allocno. */
1237 static void
1238 add_allocno_pref_to_list (ira_pref_t pref)
1240 ira_allocno_t a = pref->allocno;
1242 pref->next_pref = ALLOCNO_PREFS (a);
1243 ALLOCNO_PREFS (a) = pref;
1246 /* Create (or update frequency if the pref already exists) the pref of
1247 allocnos A preferring HARD_REGNO with frequency FREQ. */
1248 void
1249 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1251 ira_pref_t pref;
1253 if (freq <= 0)
1254 return;
1255 if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1257 pref->freq += freq;
1258 return;
1260 pref = ira_create_pref (a, hard_regno, freq);
1261 ira_assert (a != NULL);
1262 add_allocno_pref_to_list (pref);
1265 /* Print info about PREF into file F. */
1266 static void
1267 print_pref (FILE *f, ira_pref_t pref)
1269 fprintf (f, " pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1270 ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1271 pref->hard_regno, pref->freq);
1274 /* Print info about PREF into stderr. */
1275 void
1276 ira_debug_pref (ira_pref_t pref)
1278 print_pref (stderr, pref);
1281 /* Print info about all prefs into file F. */
1282 static void
1283 print_prefs (FILE *f)
1285 ira_pref_t pref;
1286 ira_pref_iterator pi;
1288 FOR_EACH_PREF (pref, pi)
1289 print_pref (f, pref);
1292 /* Print info about all prefs into stderr. */
1293 void
1294 ira_debug_prefs (void)
1296 print_prefs (stderr);
1299 /* Print info about prefs involving allocno A into file F. */
1300 static void
1301 print_allocno_prefs (FILE *f, ira_allocno_t a)
1303 ira_pref_t pref;
1305 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1306 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1307 fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1308 fprintf (f, "\n");
1311 /* Print info about prefs involving allocno A into stderr. */
1312 void
1313 ira_debug_allocno_prefs (ira_allocno_t a)
1315 print_allocno_prefs (stderr, a);
1318 /* The function frees memory allocated for PREF. */
1319 static void
1320 finish_pref (ira_pref_t pref)
1322 ira_prefs[pref->num] = NULL;
1323 pool_free (pref_pool, pref);
1326 /* Remove PREF from the list of allocno prefs and free memory for
1327 it. */
1328 void
1329 ira_remove_pref (ira_pref_t pref)
1331 ira_pref_t cpref, prev;
1333 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1334 fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1335 pref->num, pref->hard_regno, pref->freq);
1336 for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1337 cpref != NULL;
1338 prev = cpref, cpref = cpref->next_pref)
1339 if (cpref == pref)
1340 break;
1341 ira_assert (cpref != NULL);
1342 if (prev == NULL)
1343 ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1344 else
1345 prev->next_pref = pref->next_pref;
1346 finish_pref (pref);
1349 /* Remove all prefs of allocno A. */
1350 void
1351 ira_remove_allocno_prefs (ira_allocno_t a)
1353 ira_pref_t pref, next_pref;
1355 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1357 next_pref = pref->next_pref;
1358 finish_pref (pref);
1360 ALLOCNO_PREFS (a) = NULL;
1363 /* Free memory allocated for all prefs. */
1364 static void
1365 finish_prefs (void)
1367 ira_pref_t pref;
1368 ira_pref_iterator pi;
1370 FOR_EACH_PREF (pref, pi)
1371 finish_pref (pref);
1372 pref_vec.release ();
1373 free_alloc_pool (pref_pool);
1378 /* Pools for copies. */
1379 static alloc_pool copy_pool;
1381 /* Vec containing references to all created copies. It is a
1382 container of array ira_copies. */
1383 static vec<ira_copy_t> copy_vec;
1385 /* The function initializes data concerning allocno copies. */
1386 static void
1387 initiate_copies (void)
1389 copy_pool
1390 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1391 copy_vec.create (get_max_uid ());
1392 ira_copies = NULL;
1393 ira_copies_num = 0;
1396 /* Return copy connecting A1 and A2 and originated from INSN of
1397 LOOP_TREE_NODE if any. */
1398 static ira_copy_t
1399 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1400 ira_loop_tree_node_t loop_tree_node)
1402 ira_copy_t cp, next_cp;
1403 ira_allocno_t another_a;
1405 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1407 if (cp->first == a1)
1409 next_cp = cp->next_first_allocno_copy;
1410 another_a = cp->second;
1412 else if (cp->second == a1)
1414 next_cp = cp->next_second_allocno_copy;
1415 another_a = cp->first;
1417 else
1418 gcc_unreachable ();
1419 if (another_a == a2 && cp->insn == insn
1420 && cp->loop_tree_node == loop_tree_node)
1421 return cp;
1423 return NULL;
1426 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1427 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1428 ira_copy_t
1429 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1430 bool constraint_p, rtx_insn *insn,
1431 ira_loop_tree_node_t loop_tree_node)
1433 ira_copy_t cp;
1435 cp = (ira_copy_t) pool_alloc (copy_pool);
1436 cp->num = ira_copies_num;
1437 cp->first = first;
1438 cp->second = second;
1439 cp->freq = freq;
1440 cp->constraint_p = constraint_p;
1441 cp->insn = insn;
1442 cp->loop_tree_node = loop_tree_node;
1443 copy_vec.safe_push (cp);
1444 ira_copies = copy_vec.address ();
1445 ira_copies_num = copy_vec.length ();
1446 return cp;
1449 /* Attach a copy CP to allocnos involved into the copy. */
1450 static void
1451 add_allocno_copy_to_list (ira_copy_t cp)
1453 ira_allocno_t first = cp->first, second = cp->second;
1455 cp->prev_first_allocno_copy = NULL;
1456 cp->prev_second_allocno_copy = NULL;
1457 cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1458 if (cp->next_first_allocno_copy != NULL)
1460 if (cp->next_first_allocno_copy->first == first)
1461 cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1462 else
1463 cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1465 cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1466 if (cp->next_second_allocno_copy != NULL)
1468 if (cp->next_second_allocno_copy->second == second)
1469 cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1470 else
1471 cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1473 ALLOCNO_COPIES (first) = cp;
1474 ALLOCNO_COPIES (second) = cp;
1477 /* Make a copy CP a canonical copy where number of the
1478 first allocno is less than the second one. */
1479 static void
1480 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1482 ira_allocno_t temp;
1483 ira_copy_t temp_cp;
1485 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1486 return;
1488 temp = cp->first;
1489 cp->first = cp->second;
1490 cp->second = temp;
1492 temp_cp = cp->prev_first_allocno_copy;
1493 cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1494 cp->prev_second_allocno_copy = temp_cp;
1496 temp_cp = cp->next_first_allocno_copy;
1497 cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1498 cp->next_second_allocno_copy = temp_cp;
1501 /* Create (or update frequency if the copy already exists) and return
1502 the copy of allocnos FIRST and SECOND with frequency FREQ
1503 corresponding to move insn INSN (if any) and originated from
1504 LOOP_TREE_NODE. */
1505 ira_copy_t
1506 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1507 bool constraint_p, rtx_insn *insn,
1508 ira_loop_tree_node_t loop_tree_node)
1510 ira_copy_t cp;
1512 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1514 cp->freq += freq;
1515 return cp;
1517 cp = ira_create_copy (first, second, freq, constraint_p, insn,
1518 loop_tree_node);
1519 ira_assert (first != NULL && second != NULL);
1520 add_allocno_copy_to_list (cp);
1521 swap_allocno_copy_ends_if_necessary (cp);
1522 return cp;
1525 /* Print info about copy CP into file F. */
1526 static void
1527 print_copy (FILE *f, ira_copy_t cp)
1529 fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1530 ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1531 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1532 cp->insn != NULL
1533 ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1536 DEBUG_FUNCTION void
1537 debug (ira_allocno_copy &ref)
1539 print_copy (stderr, &ref);
1542 DEBUG_FUNCTION void
1543 debug (ira_allocno_copy *ptr)
1545 if (ptr)
1546 debug (*ptr);
1547 else
1548 fprintf (stderr, "<nil>\n");
1551 /* Print info about copy CP into stderr. */
1552 void
1553 ira_debug_copy (ira_copy_t cp)
1555 print_copy (stderr, cp);
1558 /* Print info about all copies into file F. */
1559 static void
1560 print_copies (FILE *f)
1562 ira_copy_t cp;
1563 ira_copy_iterator ci;
1565 FOR_EACH_COPY (cp, ci)
1566 print_copy (f, cp);
1569 /* Print info about all copies into stderr. */
1570 void
1571 ira_debug_copies (void)
1573 print_copies (stderr);
1576 /* Print info about copies involving allocno A into file F. */
1577 static void
1578 print_allocno_copies (FILE *f, ira_allocno_t a)
1580 ira_allocno_t another_a;
1581 ira_copy_t cp, next_cp;
1583 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1584 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1586 if (cp->first == a)
1588 next_cp = cp->next_first_allocno_copy;
1589 another_a = cp->second;
1591 else if (cp->second == a)
1593 next_cp = cp->next_second_allocno_copy;
1594 another_a = cp->first;
1596 else
1597 gcc_unreachable ();
1598 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1599 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1601 fprintf (f, "\n");
1604 DEBUG_FUNCTION void
1605 debug (ira_allocno &ref)
1607 print_allocno_copies (stderr, &ref);
1610 DEBUG_FUNCTION void
1611 debug (ira_allocno *ptr)
1613 if (ptr)
1614 debug (*ptr);
1615 else
1616 fprintf (stderr, "<nil>\n");
1620 /* Print info about copies involving allocno A into stderr. */
1621 void
1622 ira_debug_allocno_copies (ira_allocno_t a)
1624 print_allocno_copies (stderr, a);
1627 /* The function frees memory allocated for copy CP. */
1628 static void
1629 finish_copy (ira_copy_t cp)
1631 pool_free (copy_pool, cp);
1635 /* Free memory allocated for all copies. */
1636 static void
1637 finish_copies (void)
1639 ira_copy_t cp;
1640 ira_copy_iterator ci;
1642 FOR_EACH_COPY (cp, ci)
1643 finish_copy (cp);
1644 copy_vec.release ();
1645 free_alloc_pool (copy_pool);
1650 /* Pools for cost vectors. It is defined only for allocno classes. */
1651 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1653 /* The function initiates work with hard register cost vectors. It
1654 creates allocation pool for each allocno class. */
1655 static void
1656 initiate_cost_vectors (void)
1658 int i;
1659 enum reg_class aclass;
1661 for (i = 0; i < ira_allocno_classes_num; i++)
1663 aclass = ira_allocno_classes[i];
1664 cost_vector_pool[aclass]
1665 = create_alloc_pool ("cost vectors",
1666 sizeof (int) * ira_class_hard_regs_num[aclass],
1667 100);
1671 /* Allocate and return a cost vector VEC for ACLASS. */
1672 int *
1673 ira_allocate_cost_vector (reg_class_t aclass)
1675 return (int *) pool_alloc (cost_vector_pool[(int) aclass]);
1678 /* Free a cost vector VEC for ACLASS. */
1679 void
1680 ira_free_cost_vector (int *vec, reg_class_t aclass)
1682 ira_assert (vec != NULL);
1683 pool_free (cost_vector_pool[(int) aclass], vec);
1686 /* Finish work with hard register cost vectors. Release allocation
1687 pool for each allocno class. */
1688 static void
1689 finish_cost_vectors (void)
1691 int i;
1692 enum reg_class aclass;
1694 for (i = 0; i < ira_allocno_classes_num; i++)
1696 aclass = ira_allocno_classes[i];
1697 free_alloc_pool (cost_vector_pool[aclass]);
1703 /* Compute a post-ordering of the reverse control flow of the loop body
1704 designated by the children nodes of LOOP_NODE, whose body nodes in
1705 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1706 of the reverse loop body.
1708 For the post-order of the reverse CFG, we visit the basic blocks in
1709 LOOP_PREORDER array in the reverse order of where they appear.
1710 This is important: We do not just want to compute a post-order of
1711 the reverse CFG, we want to make a best-guess for a visiting order that
1712 minimizes the number of chain elements per allocno live range. If the
1713 blocks would be visited in a different order, we would still compute a
1714 correct post-ordering but it would be less likely that two nodes
1715 connected by an edge in the CFG are neighbours in the topsort. */
1717 static vec<ira_loop_tree_node_t>
1718 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1719 vec<ira_loop_tree_node_t> loop_preorder)
1721 vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1722 unsigned int n_loop_preorder;
1724 n_loop_preorder = loop_preorder.length ();
1725 if (n_loop_preorder != 0)
1727 ira_loop_tree_node_t subloop_node;
1728 unsigned int i;
1729 auto_vec<ira_loop_tree_node_t> dfs_stack;
1731 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1732 the flag to mark blocks we still have to visit to add them to
1733 our post-order. Define an alias to avoid confusion. */
1734 #define BB_TO_VISIT BB_VISITED
1736 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1738 gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1739 subloop_node->bb->flags |= BB_TO_VISIT;
1742 topsort_nodes.create (n_loop_preorder);
1743 dfs_stack.create (n_loop_preorder);
1745 FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1747 if (! (subloop_node->bb->flags & BB_TO_VISIT))
1748 continue;
1750 subloop_node->bb->flags &= ~BB_TO_VISIT;
1751 dfs_stack.quick_push (subloop_node);
1752 while (! dfs_stack.is_empty ())
1754 edge e;
1755 edge_iterator ei;
1757 ira_loop_tree_node_t n = dfs_stack.last ();
1758 FOR_EACH_EDGE (e, ei, n->bb->preds)
1760 ira_loop_tree_node_t pred_node;
1761 basic_block pred_bb = e->src;
1763 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1764 continue;
1766 pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1767 if (pred_node != n
1768 && (pred_node->bb->flags & BB_TO_VISIT))
1770 pred_node->bb->flags &= ~BB_TO_VISIT;
1771 dfs_stack.quick_push (pred_node);
1774 if (n == dfs_stack.last ())
1776 dfs_stack.pop ();
1777 topsort_nodes.quick_push (n);
1782 #undef BB_TO_VISIT
1785 gcc_assert (topsort_nodes.length () == n_loop_preorder);
1786 return topsort_nodes;
1789 /* The current loop tree node and its regno allocno map. */
1790 ira_loop_tree_node_t ira_curr_loop_tree_node;
1791 ira_allocno_t *ira_curr_regno_allocno_map;
1793 /* This recursive function traverses loop tree with root LOOP_NODE
1794 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1795 correspondingly in preorder and postorder. The function sets up
1796 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1797 basic block nodes of LOOP_NODE is also processed (before its
1798 subloop nodes).
1800 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1801 the loop are passed in the *reverse* post-order of the *reverse*
1802 CFG. This is only used by ira_create_allocno_live_ranges, which
1803 wants to visit basic blocks in this order to minimize the number
1804 of elements per live range chain.
1805 Note that the loop tree nodes are still visited in the normal,
1806 forward post-order of the loop tree. */
1808 void
1809 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1810 void (*preorder_func) (ira_loop_tree_node_t),
1811 void (*postorder_func) (ira_loop_tree_node_t))
1813 ira_loop_tree_node_t subloop_node;
1815 ira_assert (loop_node->bb == NULL);
1816 ira_curr_loop_tree_node = loop_node;
1817 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1819 if (preorder_func != NULL)
1820 (*preorder_func) (loop_node);
1822 if (bb_p)
1824 auto_vec<ira_loop_tree_node_t> loop_preorder;
1825 unsigned int i;
1827 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1828 is set up such that nodes in the loop body appear in a pre-order
1829 of their place in the CFG. */
1830 for (subloop_node = loop_node->children;
1831 subloop_node != NULL;
1832 subloop_node = subloop_node->next)
1833 if (subloop_node->bb != NULL)
1834 loop_preorder.safe_push (subloop_node);
1836 if (preorder_func != NULL)
1837 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1838 (*preorder_func) (subloop_node);
1840 if (postorder_func != NULL)
1842 vec<ira_loop_tree_node_t> loop_rev_postorder =
1843 ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1844 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1845 (*postorder_func) (subloop_node);
1846 loop_rev_postorder.release ();
1850 for (subloop_node = loop_node->subloops;
1851 subloop_node != NULL;
1852 subloop_node = subloop_node->subloop_next)
1854 ira_assert (subloop_node->bb == NULL);
1855 ira_traverse_loop_tree (bb_p, subloop_node,
1856 preorder_func, postorder_func);
1859 ira_curr_loop_tree_node = loop_node;
1860 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1862 if (postorder_func != NULL)
1863 (*postorder_func) (loop_node);
1868 /* The basic block currently being processed. */
1869 static basic_block curr_bb;
1871 /* This recursive function creates allocnos corresponding to
1872 pseudo-registers containing in X. True OUTPUT_P means that X is
1873 an lvalue. PARENT corresponds to the parent expression of X. */
1874 static void
1875 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1877 int i, j;
1878 const char *fmt;
1879 enum rtx_code code = GET_CODE (x);
1881 if (code == REG)
1883 int regno;
1885 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1887 ira_allocno_t a;
1889 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1891 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1892 if (outer != NULL && GET_CODE (outer) == SUBREG)
1894 machine_mode wmode = GET_MODE (outer);
1895 if (GET_MODE_SIZE (wmode) > GET_MODE_SIZE (ALLOCNO_WMODE (a)))
1896 ALLOCNO_WMODE (a) = wmode;
1900 ALLOCNO_NREFS (a)++;
1901 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1902 if (output_p)
1903 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1905 return;
1907 else if (code == SET)
1909 create_insn_allocnos (SET_DEST (x), NULL, true);
1910 create_insn_allocnos (SET_SRC (x), NULL, false);
1911 return;
1913 else if (code == CLOBBER)
1915 create_insn_allocnos (XEXP (x, 0), NULL, true);
1916 return;
1918 else if (code == MEM)
1920 create_insn_allocnos (XEXP (x, 0), NULL, false);
1921 return;
1923 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1924 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1926 create_insn_allocnos (XEXP (x, 0), NULL, true);
1927 create_insn_allocnos (XEXP (x, 0), NULL, false);
1928 return;
1931 fmt = GET_RTX_FORMAT (code);
1932 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1934 if (fmt[i] == 'e')
1935 create_insn_allocnos (XEXP (x, i), x, output_p);
1936 else if (fmt[i] == 'E')
1937 for (j = 0; j < XVECLEN (x, i); j++)
1938 create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1942 /* Create allocnos corresponding to pseudo-registers living in the
1943 basic block represented by the corresponding loop tree node
1944 BB_NODE. */
1945 static void
1946 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1948 basic_block bb;
1949 rtx_insn *insn;
1950 unsigned int i;
1951 bitmap_iterator bi;
1953 curr_bb = bb = bb_node->bb;
1954 ira_assert (bb != NULL);
1955 FOR_BB_INSNS_REVERSE (bb, insn)
1956 if (NONDEBUG_INSN_P (insn))
1957 create_insn_allocnos (PATTERN (insn), NULL, false);
1958 /* It might be a allocno living through from one subloop to
1959 another. */
1960 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1961 if (ira_curr_regno_allocno_map[i] == NULL)
1962 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1965 /* Create allocnos corresponding to pseudo-registers living on edge E
1966 (a loop entry or exit). Also mark the allocnos as living on the
1967 loop border. */
1968 static void
1969 create_loop_allocnos (edge e)
1971 unsigned int i;
1972 bitmap live_in_regs, border_allocnos;
1973 bitmap_iterator bi;
1974 ira_loop_tree_node_t parent;
1976 live_in_regs = df_get_live_in (e->dest);
1977 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1978 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1979 FIRST_PSEUDO_REGISTER, i, bi)
1980 if (bitmap_bit_p (live_in_regs, i))
1982 if (ira_curr_regno_allocno_map[i] == NULL)
1984 /* The order of creations is important for right
1985 ira_regno_allocno_map. */
1986 if ((parent = ira_curr_loop_tree_node->parent) != NULL
1987 && parent->regno_allocno_map[i] == NULL)
1988 ira_create_allocno (i, false, parent);
1989 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1991 bitmap_set_bit (border_allocnos,
1992 ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1996 /* Create allocnos corresponding to pseudo-registers living in loop
1997 represented by the corresponding loop tree node LOOP_NODE. This
1998 function is called by ira_traverse_loop_tree. */
1999 static void
2000 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
2002 if (loop_node->bb != NULL)
2003 create_bb_allocnos (loop_node);
2004 else if (loop_node != ira_loop_tree_root)
2006 int i;
2007 edge_iterator ei;
2008 edge e;
2009 vec<edge> edges;
2011 ira_assert (current_loops != NULL);
2012 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
2013 if (e->src != loop_node->loop->latch)
2014 create_loop_allocnos (e);
2016 edges = get_loop_exit_edges (loop_node->loop);
2017 FOR_EACH_VEC_ELT (edges, i, e)
2018 create_loop_allocnos (e);
2019 edges.release ();
2023 /* Propagate information about allocnos modified inside the loop given
2024 by its LOOP_TREE_NODE to its parent. */
2025 static void
2026 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
2028 if (loop_tree_node == ira_loop_tree_root)
2029 return;
2030 ira_assert (loop_tree_node->bb == NULL);
2031 bitmap_ior_into (loop_tree_node->parent->modified_regnos,
2032 loop_tree_node->modified_regnos);
2035 /* Propagate new info about allocno A (see comments about accumulated
2036 info in allocno definition) to the corresponding allocno on upper
2037 loop tree level. So allocnos on upper levels accumulate
2038 information about the corresponding allocnos in nested regions.
2039 The new info means allocno info finally calculated in this
2040 file. */
2041 static void
2042 propagate_allocno_info (void)
2044 int i;
2045 ira_allocno_t a, parent_a;
2046 ira_loop_tree_node_t parent;
2047 enum reg_class aclass;
2049 if (flag_ira_region != IRA_REGION_ALL
2050 && flag_ira_region != IRA_REGION_MIXED)
2051 return;
2052 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2053 for (a = ira_regno_allocno_map[i];
2054 a != NULL;
2055 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2056 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2057 && (parent_a = parent->regno_allocno_map[i]) != NULL
2058 /* There are no caps yet at this point. So use
2059 border_allocnos to find allocnos for the propagation. */
2060 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2061 ALLOCNO_NUM (a)))
2063 if (! ALLOCNO_BAD_SPILL_P (a))
2064 ALLOCNO_BAD_SPILL_P (parent_a) = false;
2065 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2066 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2067 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2068 merge_hard_reg_conflicts (a, parent_a, true);
2069 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2070 += ALLOCNO_CALLS_CROSSED_NUM (a);
2071 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2072 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2073 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
2074 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2075 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2076 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2077 aclass = ALLOCNO_CLASS (a);
2078 ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2079 ira_allocate_and_accumulate_costs
2080 (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
2081 ALLOCNO_HARD_REG_COSTS (a));
2082 ira_allocate_and_accumulate_costs
2083 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2084 aclass,
2085 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2086 ALLOCNO_CLASS_COST (parent_a)
2087 += ALLOCNO_CLASS_COST (a);
2088 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2092 /* Create allocnos corresponding to pseudo-registers in the current
2093 function. Traverse the loop tree for this. */
2094 static void
2095 create_allocnos (void)
2097 /* We need to process BB first to correctly link allocnos by member
2098 next_regno_allocno. */
2099 ira_traverse_loop_tree (true, ira_loop_tree_root,
2100 create_loop_tree_node_allocnos, NULL);
2101 if (optimize)
2102 ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
2103 propagate_modified_regnos);
2108 /* The page contains function to remove some regions from a separate
2109 register allocation. We remove regions whose separate allocation
2110 will hardly improve the result. As a result we speed up regional
2111 register allocation. */
2113 /* The function changes the object in range list given by R to OBJ. */
2114 static void
2115 change_object_in_range_list (live_range_t r, ira_object_t obj)
2117 for (; r != NULL; r = r->next)
2118 r->object = obj;
2121 /* Move all live ranges associated with allocno FROM to allocno TO. */
2122 static void
2123 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2125 int i;
2126 int n = ALLOCNO_NUM_OBJECTS (from);
2128 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2130 for (i = 0; i < n; i++)
2132 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2133 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2134 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2136 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2138 fprintf (ira_dump_file,
2139 " Moving ranges of a%dr%d to a%dr%d: ",
2140 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2141 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2142 ira_print_live_range_list (ira_dump_file, lr);
2144 change_object_in_range_list (lr, to_obj);
2145 OBJECT_LIVE_RANGES (to_obj)
2146 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2147 OBJECT_LIVE_RANGES (from_obj) = NULL;
2151 static void
2152 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2154 int i;
2155 int n = ALLOCNO_NUM_OBJECTS (from);
2157 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2159 for (i = 0; i < n; i++)
2161 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2162 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2163 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2165 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2167 fprintf (ira_dump_file, " Copying ranges of a%dr%d to a%dr%d: ",
2168 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2169 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2170 ira_print_live_range_list (ira_dump_file, lr);
2172 lr = ira_copy_live_range_list (lr);
2173 change_object_in_range_list (lr, to_obj);
2174 OBJECT_LIVE_RANGES (to_obj)
2175 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2179 /* Return TRUE if NODE represents a loop with low register
2180 pressure. */
2181 static bool
2182 low_pressure_loop_node_p (ira_loop_tree_node_t node)
2184 int i;
2185 enum reg_class pclass;
2187 if (node->bb != NULL)
2188 return false;
2190 for (i = 0; i < ira_pressure_classes_num; i++)
2192 pclass = ira_pressure_classes[i];
2193 if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2194 && ira_class_hard_regs_num[pclass] > 1)
2195 return false;
2197 return true;
2200 #ifdef STACK_REGS
2201 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2202 form a region from such loop if the target use stack register
2203 because reg-stack.c can not deal with such edges. */
2204 static bool
2205 loop_with_complex_edge_p (struct loop *loop)
2207 int i;
2208 edge_iterator ei;
2209 edge e;
2210 vec<edge> edges;
2211 bool res;
2213 FOR_EACH_EDGE (e, ei, loop->header->preds)
2214 if (e->flags & EDGE_EH)
2215 return true;
2216 edges = get_loop_exit_edges (loop);
2217 res = false;
2218 FOR_EACH_VEC_ELT (edges, i, e)
2219 if (e->flags & EDGE_COMPLEX)
2221 res = true;
2222 break;
2224 edges.release ();
2225 return res;
2227 #endif
2229 /* Sort loops for marking them for removal. We put already marked
2230 loops first, then less frequent loops next, and then outer loops
2231 next. */
2232 static int
2233 loop_compare_func (const void *v1p, const void *v2p)
2235 int diff;
2236 ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2237 ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2239 ira_assert (l1->parent != NULL && l2->parent != NULL);
2240 if (l1->to_remove_p && ! l2->to_remove_p)
2241 return -1;
2242 if (! l1->to_remove_p && l2->to_remove_p)
2243 return 1;
2244 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
2245 return diff;
2246 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2247 return diff;
2248 /* Make sorting stable. */
2249 return l1->loop_num - l2->loop_num;
2252 /* Mark loops which should be removed from regional allocation. We
2253 remove a loop with low register pressure inside another loop with
2254 register pressure. In this case a separate allocation of the loop
2255 hardly helps (for irregular register file architecture it could
2256 help by choosing a better hard register in the loop but we prefer
2257 faster allocation even in this case). We also remove cheap loops
2258 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH
2259 exit or enter edges are removed too because the allocation might
2260 require put pseudo moves on the EH edges (we could still do this
2261 for pseudos with caller saved hard registers in some cases but it
2262 is impossible to say here or during top-down allocation pass what
2263 hard register the pseudos get finally). */
2264 static void
2265 mark_loops_for_removal (void)
2267 int i, n;
2268 ira_loop_tree_node_t *sorted_loops;
2269 loop_p loop;
2271 ira_assert (current_loops != NULL);
2272 sorted_loops
2273 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2274 * number_of_loops (cfun));
2275 for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2276 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2278 if (ira_loop_nodes[i].parent == NULL)
2280 /* Don't remove the root. */
2281 ira_loop_nodes[i].to_remove_p = false;
2282 continue;
2284 sorted_loops[n++] = &ira_loop_nodes[i];
2285 ira_loop_nodes[i].to_remove_p
2286 = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2287 && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2288 #ifdef STACK_REGS
2289 || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2290 #endif
2293 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2294 for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++)
2296 sorted_loops[i]->to_remove_p = true;
2297 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2298 fprintf
2299 (ira_dump_file,
2300 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2301 sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2302 sorted_loops[i]->loop->header->frequency,
2303 loop_depth (sorted_loops[i]->loop),
2304 low_pressure_loop_node_p (sorted_loops[i]->parent)
2305 && low_pressure_loop_node_p (sorted_loops[i])
2306 ? "low pressure" : "cheap loop");
2308 ira_free (sorted_loops);
2311 /* Mark all loops but root for removing. */
2312 static void
2313 mark_all_loops_for_removal (void)
2315 int i;
2316 loop_p loop;
2318 ira_assert (current_loops != NULL);
2319 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2320 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2322 if (ira_loop_nodes[i].parent == NULL)
2324 /* Don't remove the root. */
2325 ira_loop_nodes[i].to_remove_p = false;
2326 continue;
2328 ira_loop_nodes[i].to_remove_p = true;
2329 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2330 fprintf
2331 (ira_dump_file,
2332 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2333 ira_loop_nodes[i].loop_num,
2334 ira_loop_nodes[i].loop->header->index,
2335 ira_loop_nodes[i].loop->header->frequency,
2336 loop_depth (ira_loop_nodes[i].loop));
2340 /* Definition of vector of loop tree nodes. */
2342 /* Vec containing references to all removed loop tree nodes. */
2343 static vec<ira_loop_tree_node_t> removed_loop_vec;
2345 /* Vec containing references to all children of loop tree nodes. */
2346 static vec<ira_loop_tree_node_t> children_vec;
2348 /* Remove subregions of NODE if their separate allocation will not
2349 improve the result. */
2350 static void
2351 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2353 unsigned int start;
2354 bool remove_p;
2355 ira_loop_tree_node_t subnode;
2357 remove_p = node->to_remove_p;
2358 if (! remove_p)
2359 children_vec.safe_push (node);
2360 start = children_vec.length ();
2361 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2362 if (subnode->bb == NULL)
2363 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2364 else
2365 children_vec.safe_push (subnode);
2366 node->children = node->subloops = NULL;
2367 if (remove_p)
2369 removed_loop_vec.safe_push (node);
2370 return;
2372 while (children_vec.length () > start)
2374 subnode = children_vec.pop ();
2375 subnode->parent = node;
2376 subnode->next = node->children;
2377 node->children = subnode;
2378 if (subnode->bb == NULL)
2380 subnode->subloop_next = node->subloops;
2381 node->subloops = subnode;
2386 /* Return TRUE if NODE is inside PARENT. */
2387 static bool
2388 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2390 for (node = node->parent; node != NULL; node = node->parent)
2391 if (node == parent)
2392 return true;
2393 return false;
2396 /* Sort allocnos according to their order in regno allocno list. */
2397 static int
2398 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2400 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2401 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2402 ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2403 ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2405 if (loop_is_inside_p (n1, n2))
2406 return -1;
2407 else if (loop_is_inside_p (n2, n1))
2408 return 1;
2409 /* If allocnos are equally good, sort by allocno numbers, so that
2410 the results of qsort leave nothing to chance. We put allocnos
2411 with higher number first in the list because it is the original
2412 order for allocnos from loops on the same levels. */
2413 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2416 /* This array is used to sort allocnos to restore allocno order in
2417 the regno allocno list. */
2418 static ira_allocno_t *regno_allocnos;
2420 /* Restore allocno order for REGNO in the regno allocno list. */
2421 static void
2422 ira_rebuild_regno_allocno_list (int regno)
2424 int i, n;
2425 ira_allocno_t a;
2427 for (n = 0, a = ira_regno_allocno_map[regno];
2428 a != NULL;
2429 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2430 regno_allocnos[n++] = a;
2431 ira_assert (n > 0);
2432 qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2433 regno_allocno_order_compare_func);
2434 for (i = 1; i < n; i++)
2435 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2436 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2437 ira_regno_allocno_map[regno] = regno_allocnos[0];
2438 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2439 fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2442 /* Propagate info from allocno FROM_A to allocno A. */
2443 static void
2444 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2446 enum reg_class aclass;
2448 merge_hard_reg_conflicts (from_a, a, false);
2449 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2450 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2451 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2452 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2453 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2454 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2455 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a),
2456 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a));
2458 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2459 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2460 if (! ALLOCNO_BAD_SPILL_P (from_a))
2461 ALLOCNO_BAD_SPILL_P (a) = false;
2462 aclass = ALLOCNO_CLASS (from_a);
2463 ira_assert (aclass == ALLOCNO_CLASS (a));
2464 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2465 ALLOCNO_HARD_REG_COSTS (from_a));
2466 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2467 aclass,
2468 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2469 ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2470 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2473 /* Remove allocnos from loops removed from the allocation
2474 consideration. */
2475 static void
2476 remove_unnecessary_allocnos (void)
2478 int regno;
2479 bool merged_p, rebuild_p;
2480 ira_allocno_t a, prev_a, next_a, parent_a;
2481 ira_loop_tree_node_t a_node, parent;
2483 merged_p = false;
2484 regno_allocnos = NULL;
2485 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2487 rebuild_p = false;
2488 for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2489 a != NULL;
2490 a = next_a)
2492 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2493 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2494 if (! a_node->to_remove_p)
2495 prev_a = a;
2496 else
2498 for (parent = a_node->parent;
2499 (parent_a = parent->regno_allocno_map[regno]) == NULL
2500 && parent->to_remove_p;
2501 parent = parent->parent)
2503 if (parent_a == NULL)
2505 /* There are no allocnos with the same regno in
2506 upper region -- just move the allocno to the
2507 upper region. */
2508 prev_a = a;
2509 ALLOCNO_LOOP_TREE_NODE (a) = parent;
2510 parent->regno_allocno_map[regno] = a;
2511 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2512 rebuild_p = true;
2514 else
2516 /* Remove the allocno and update info of allocno in
2517 the upper region. */
2518 if (prev_a == NULL)
2519 ira_regno_allocno_map[regno] = next_a;
2520 else
2521 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2522 move_allocno_live_ranges (a, parent_a);
2523 merged_p = true;
2524 propagate_some_info_from_allocno (parent_a, a);
2525 /* Remove it from the corresponding regno allocno
2526 map to avoid info propagation of subsequent
2527 allocno into this already removed allocno. */
2528 a_node->regno_allocno_map[regno] = NULL;
2529 ira_remove_allocno_prefs (a);
2530 finish_allocno (a);
2534 if (rebuild_p)
2535 /* We need to restore the order in regno allocno list. */
2537 if (regno_allocnos == NULL)
2538 regno_allocnos
2539 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2540 * ira_allocnos_num);
2541 ira_rebuild_regno_allocno_list (regno);
2544 if (merged_p)
2545 ira_rebuild_start_finish_chains ();
2546 if (regno_allocnos != NULL)
2547 ira_free (regno_allocnos);
2550 /* Remove allocnos from all loops but the root. */
2551 static void
2552 remove_low_level_allocnos (void)
2554 int regno;
2555 bool merged_p, propagate_p;
2556 ira_allocno_t a, top_a;
2557 ira_loop_tree_node_t a_node, parent;
2558 ira_allocno_iterator ai;
2560 merged_p = false;
2561 FOR_EACH_ALLOCNO (a, ai)
2563 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2564 if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2565 continue;
2566 regno = ALLOCNO_REGNO (a);
2567 if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2569 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2570 ira_loop_tree_root->regno_allocno_map[regno] = a;
2571 continue;
2573 propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2574 /* Remove the allocno and update info of allocno in the upper
2575 region. */
2576 move_allocno_live_ranges (a, top_a);
2577 merged_p = true;
2578 if (propagate_p)
2579 propagate_some_info_from_allocno (top_a, a);
2581 FOR_EACH_ALLOCNO (a, ai)
2583 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2584 if (a_node == ira_loop_tree_root)
2585 continue;
2586 parent = a_node->parent;
2587 regno = ALLOCNO_REGNO (a);
2588 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2589 ira_assert (ALLOCNO_CAP (a) != NULL);
2590 else if (ALLOCNO_CAP (a) == NULL)
2591 ira_assert (parent->regno_allocno_map[regno] != NULL);
2593 FOR_EACH_ALLOCNO (a, ai)
2595 regno = ALLOCNO_REGNO (a);
2596 if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2598 ira_object_t obj;
2599 ira_allocno_object_iterator oi;
2601 ira_regno_allocno_map[regno] = a;
2602 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2603 ALLOCNO_CAP_MEMBER (a) = NULL;
2604 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2605 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
2606 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj));
2607 #ifdef STACK_REGS
2608 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2609 ALLOCNO_NO_STACK_REG_P (a) = true;
2610 #endif
2612 else
2614 ira_remove_allocno_prefs (a);
2615 finish_allocno (a);
2618 if (merged_p)
2619 ira_rebuild_start_finish_chains ();
2622 /* Remove loops from consideration. We remove all loops except for
2623 root if ALL_P or loops for which a separate allocation will not
2624 improve the result. We have to do this after allocno creation and
2625 their costs and allocno class evaluation because only after that
2626 the register pressure can be known and is calculated. */
2627 static void
2628 remove_unnecessary_regions (bool all_p)
2630 if (current_loops == NULL)
2631 return;
2632 if (all_p)
2633 mark_all_loops_for_removal ();
2634 else
2635 mark_loops_for_removal ();
2636 children_vec.create (last_basic_block_for_fn (cfun)
2637 + number_of_loops (cfun));
2638 removed_loop_vec.create (last_basic_block_for_fn (cfun)
2639 + number_of_loops (cfun));
2640 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2641 children_vec.release ();
2642 if (all_p)
2643 remove_low_level_allocnos ();
2644 else
2645 remove_unnecessary_allocnos ();
2646 while (removed_loop_vec.length () > 0)
2647 finish_loop_tree_node (removed_loop_vec.pop ());
2648 removed_loop_vec.release ();
2653 /* At this point true value of allocno attribute bad_spill_p means
2654 that there is an insn where allocno occurs and where the allocno
2655 can not be used as memory. The function updates the attribute, now
2656 it can be true only for allocnos which can not be used as memory in
2657 an insn and in whose live ranges there is other allocno deaths.
2658 Spilling allocnos with true value will not improve the code because
2659 it will not make other allocnos colorable and additional reloads
2660 for the corresponding pseudo will be generated in reload pass for
2661 each insn it occurs.
2663 This is a trick mentioned in one classic article of Chaitin etc
2664 which is frequently omitted in other implementations of RA based on
2665 graph coloring. */
2666 static void
2667 update_bad_spill_attribute (void)
2669 int i;
2670 ira_allocno_t a;
2671 ira_allocno_iterator ai;
2672 ira_allocno_object_iterator aoi;
2673 ira_object_t obj;
2674 live_range_t r;
2675 enum reg_class aclass;
2676 bitmap_head dead_points[N_REG_CLASSES];
2678 for (i = 0; i < ira_allocno_classes_num; i++)
2680 aclass = ira_allocno_classes[i];
2681 bitmap_initialize (&dead_points[aclass], &reg_obstack);
2683 FOR_EACH_ALLOCNO (a, ai)
2685 aclass = ALLOCNO_CLASS (a);
2686 if (aclass == NO_REGS)
2687 continue;
2688 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2689 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2690 bitmap_set_bit (&dead_points[aclass], r->finish);
2692 FOR_EACH_ALLOCNO (a, ai)
2694 aclass = ALLOCNO_CLASS (a);
2695 if (aclass == NO_REGS)
2696 continue;
2697 if (! ALLOCNO_BAD_SPILL_P (a))
2698 continue;
2699 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2701 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2703 for (i = r->start + 1; i < r->finish; i++)
2704 if (bitmap_bit_p (&dead_points[aclass], i))
2705 break;
2706 if (i < r->finish)
2707 break;
2709 if (r != NULL)
2711 ALLOCNO_BAD_SPILL_P (a) = false;
2712 break;
2716 for (i = 0; i < ira_allocno_classes_num; i++)
2718 aclass = ira_allocno_classes[i];
2719 bitmap_clear (&dead_points[aclass]);
2725 /* Set up minimal and maximal live range points for allocnos. */
2726 static void
2727 setup_min_max_allocno_live_range_point (void)
2729 int i;
2730 ira_allocno_t a, parent_a, cap;
2731 ira_allocno_iterator ai;
2732 #ifdef ENABLE_IRA_CHECKING
2733 ira_object_iterator oi;
2734 ira_object_t obj;
2735 #endif
2736 live_range_t r;
2737 ira_loop_tree_node_t parent;
2739 FOR_EACH_ALLOCNO (a, ai)
2741 int n = ALLOCNO_NUM_OBJECTS (a);
2743 for (i = 0; i < n; i++)
2745 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2746 r = OBJECT_LIVE_RANGES (obj);
2747 if (r == NULL)
2748 continue;
2749 OBJECT_MAX (obj) = r->finish;
2750 for (; r->next != NULL; r = r->next)
2752 OBJECT_MIN (obj) = r->start;
2755 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2756 for (a = ira_regno_allocno_map[i];
2757 a != NULL;
2758 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2760 int j;
2761 int n = ALLOCNO_NUM_OBJECTS (a);
2763 for (j = 0; j < n; j++)
2765 ira_object_t obj = ALLOCNO_OBJECT (a, j);
2766 ira_object_t parent_obj;
2768 if (OBJECT_MAX (obj) < 0)
2769 continue;
2770 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2771 /* Accumulation of range info. */
2772 if (ALLOCNO_CAP (a) != NULL)
2774 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2776 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2777 if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2778 OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2779 if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2780 OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2782 continue;
2784 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2785 continue;
2786 parent_a = parent->regno_allocno_map[i];
2787 parent_obj = ALLOCNO_OBJECT (parent_a, j);
2788 if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2789 OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2790 if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2791 OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2794 #ifdef ENABLE_IRA_CHECKING
2795 FOR_EACH_OBJECT (obj, oi)
2797 if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2798 && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2799 continue;
2800 gcc_unreachable ();
2802 #endif
2805 /* Sort allocnos according to their live ranges. Allocnos with
2806 smaller allocno class are put first unless we use priority
2807 coloring. Allocnos with the same class are ordered according
2808 their start (min). Allocnos with the same start are ordered
2809 according their finish (max). */
2810 static int
2811 object_range_compare_func (const void *v1p, const void *v2p)
2813 int diff;
2814 ira_object_t obj1 = *(const ira_object_t *) v1p;
2815 ira_object_t obj2 = *(const ira_object_t *) v2p;
2816 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2817 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2819 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2820 return diff;
2821 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2822 return diff;
2823 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2826 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2827 static void
2828 sort_conflict_id_map (void)
2830 int i, num;
2831 ira_allocno_t a;
2832 ira_allocno_iterator ai;
2834 num = 0;
2835 FOR_EACH_ALLOCNO (a, ai)
2837 ira_allocno_object_iterator oi;
2838 ira_object_t obj;
2840 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2841 ira_object_id_map[num++] = obj;
2843 if (num > 1)
2844 qsort (ira_object_id_map, num, sizeof (ira_object_t),
2845 object_range_compare_func);
2846 for (i = 0; i < num; i++)
2848 ira_object_t obj = ira_object_id_map[i];
2850 gcc_assert (obj != NULL);
2851 OBJECT_CONFLICT_ID (obj) = i;
2853 for (i = num; i < ira_objects_num; i++)
2854 ira_object_id_map[i] = NULL;
2857 /* Set up minimal and maximal conflict ids of allocnos with which
2858 given allocno can conflict. */
2859 static void
2860 setup_min_max_conflict_allocno_ids (void)
2862 int aclass;
2863 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2864 int *live_range_min, *last_lived;
2865 int word0_min, word0_max;
2866 ira_allocno_t a;
2867 ira_allocno_iterator ai;
2869 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2870 aclass = -1;
2871 first_not_finished = -1;
2872 for (i = 0; i < ira_objects_num; i++)
2874 ira_object_t obj = ira_object_id_map[i];
2876 if (obj == NULL)
2877 continue;
2879 a = OBJECT_ALLOCNO (obj);
2881 if (aclass < 0)
2883 aclass = ALLOCNO_CLASS (a);
2884 min = i;
2885 first_not_finished = i;
2887 else
2889 start = OBJECT_MIN (obj);
2890 /* If we skip an allocno, the allocno with smaller ids will
2891 be also skipped because of the secondary sorting the
2892 range finishes (see function
2893 object_range_compare_func). */
2894 while (first_not_finished < i
2895 && start > OBJECT_MAX (ira_object_id_map
2896 [first_not_finished]))
2897 first_not_finished++;
2898 min = first_not_finished;
2900 if (min == i)
2901 /* We could increase min further in this case but it is good
2902 enough. */
2903 min++;
2904 live_range_min[i] = OBJECT_MIN (obj);
2905 OBJECT_MIN (obj) = min;
2907 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2908 aclass = -1;
2909 filled_area_start = -1;
2910 for (i = ira_objects_num - 1; i >= 0; i--)
2912 ira_object_t obj = ira_object_id_map[i];
2914 if (obj == NULL)
2915 continue;
2917 a = OBJECT_ALLOCNO (obj);
2918 if (aclass < 0)
2920 aclass = ALLOCNO_CLASS (a);
2921 for (j = 0; j < ira_max_point; j++)
2922 last_lived[j] = -1;
2923 filled_area_start = ira_max_point;
2925 min = live_range_min[i];
2926 finish = OBJECT_MAX (obj);
2927 max = last_lived[finish];
2928 if (max < 0)
2929 /* We could decrease max further in this case but it is good
2930 enough. */
2931 max = OBJECT_CONFLICT_ID (obj) - 1;
2932 OBJECT_MAX (obj) = max;
2933 /* In filling, we can go further A range finish to recognize
2934 intersection quickly because if the finish of subsequently
2935 processed allocno (it has smaller conflict id) range is
2936 further A range finish than they are definitely intersected
2937 (the reason for this is the allocnos with bigger conflict id
2938 have their range starts not smaller than allocnos with
2939 smaller ids. */
2940 for (j = min; j < filled_area_start; j++)
2941 last_lived[j] = i;
2942 filled_area_start = min;
2944 ira_free (last_lived);
2945 ira_free (live_range_min);
2947 /* For allocnos with more than one object, we may later record extra conflicts in
2948 subobject 0 that we cannot really know about here.
2949 For now, simply widen the min/max range of these subobjects. */
2951 word0_min = INT_MAX;
2952 word0_max = INT_MIN;
2954 FOR_EACH_ALLOCNO (a, ai)
2956 int n = ALLOCNO_NUM_OBJECTS (a);
2957 ira_object_t obj0;
2959 if (n < 2)
2960 continue;
2961 obj0 = ALLOCNO_OBJECT (a, 0);
2962 if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2963 word0_min = OBJECT_CONFLICT_ID (obj0);
2964 if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2965 word0_max = OBJECT_CONFLICT_ID (obj0);
2967 FOR_EACH_ALLOCNO (a, ai)
2969 int n = ALLOCNO_NUM_OBJECTS (a);
2970 ira_object_t obj0;
2972 if (n < 2)
2973 continue;
2974 obj0 = ALLOCNO_OBJECT (a, 0);
2975 if (OBJECT_MIN (obj0) > word0_min)
2976 OBJECT_MIN (obj0) = word0_min;
2977 if (OBJECT_MAX (obj0) < word0_max)
2978 OBJECT_MAX (obj0) = word0_max;
2984 static void
2985 create_caps (void)
2987 ira_allocno_t a;
2988 ira_allocno_iterator ai;
2989 ira_loop_tree_node_t loop_tree_node;
2991 FOR_EACH_ALLOCNO (a, ai)
2993 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2994 continue;
2995 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2996 create_cap_allocno (a);
2997 else if (ALLOCNO_CAP (a) == NULL)
2999 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3000 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
3001 create_cap_allocno (a);
3008 /* The page contains code transforming more one region internal
3009 representation (IR) to one region IR which is necessary for reload.
3010 This transformation is called IR flattening. We might just rebuild
3011 the IR for one region but we don't do it because it takes a lot of
3012 time. */
3014 /* Map: regno -> allocnos which will finally represent the regno for
3015 IR with one region. */
3016 static ira_allocno_t *regno_top_level_allocno_map;
3018 /* Find the allocno that corresponds to A at a level one higher up in the
3019 loop tree. Returns NULL if A is a cap, or if it has no parent. */
3020 ira_allocno_t
3021 ira_parent_allocno (ira_allocno_t a)
3023 ira_loop_tree_node_t parent;
3025 if (ALLOCNO_CAP (a) != NULL)
3026 return NULL;
3028 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3029 if (parent == NULL)
3030 return NULL;
3032 return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3035 /* Find the allocno that corresponds to A at a level one higher up in the
3036 loop tree. If ALLOCNO_CAP is set for A, return that. */
3037 ira_allocno_t
3038 ira_parent_or_cap_allocno (ira_allocno_t a)
3040 if (ALLOCNO_CAP (a) != NULL)
3041 return ALLOCNO_CAP (a);
3043 return ira_parent_allocno (a);
3046 /* Process all allocnos originated from pseudo REGNO and copy live
3047 ranges, hard reg conflicts, and allocno stack reg attributes from
3048 low level allocnos to final allocnos which are destinations of
3049 removed stores at a loop exit. Return true if we copied live
3050 ranges. */
3051 static bool
3052 copy_info_to_removed_store_destinations (int regno)
3054 ira_allocno_t a;
3055 ira_allocno_t parent_a = NULL;
3056 ira_loop_tree_node_t parent;
3057 bool merged_p;
3059 merged_p = false;
3060 for (a = ira_regno_allocno_map[regno];
3061 a != NULL;
3062 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3064 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3065 /* This allocno will be removed. */
3066 continue;
3068 /* Caps will be removed. */
3069 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3070 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3071 parent != NULL;
3072 parent = parent->parent)
3073 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3074 || (parent_a
3075 == regno_top_level_allocno_map[REGNO
3076 (allocno_emit_reg (parent_a))]
3077 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3078 break;
3079 if (parent == NULL || parent_a == NULL)
3080 continue;
3082 copy_allocno_live_ranges (a, parent_a);
3083 merge_hard_reg_conflicts (a, parent_a, true);
3085 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3086 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3087 += ALLOCNO_CALLS_CROSSED_NUM (a);
3088 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3089 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3090 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
3091 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
3092 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3093 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3094 merged_p = true;
3096 return merged_p;
3099 /* Flatten the IR. In other words, this function transforms IR as if
3100 it were built with one region (without loops). We could make it
3101 much simpler by rebuilding IR with one region, but unfortunately it
3102 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3103 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3104 IRA_MAX_POINT before emitting insns on the loop borders. */
3105 void
3106 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3108 int i, j;
3109 bool keep_p;
3110 int hard_regs_num;
3111 bool new_pseudos_p, merged_p, mem_dest_p;
3112 unsigned int n;
3113 enum reg_class aclass;
3114 ira_allocno_t a, parent_a, first, second, node_first, node_second;
3115 ira_copy_t cp;
3116 ira_loop_tree_node_t node;
3117 live_range_t r;
3118 ira_allocno_iterator ai;
3119 ira_copy_iterator ci;
3121 regno_top_level_allocno_map
3122 = (ira_allocno_t *) ira_allocate (max_reg_num ()
3123 * sizeof (ira_allocno_t));
3124 memset (regno_top_level_allocno_map, 0,
3125 max_reg_num () * sizeof (ira_allocno_t));
3126 new_pseudos_p = merged_p = false;
3127 FOR_EACH_ALLOCNO (a, ai)
3129 ira_allocno_object_iterator oi;
3130 ira_object_t obj;
3132 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3133 /* Caps are not in the regno allocno maps and they are never
3134 will be transformed into allocnos existing after IR
3135 flattening. */
3136 continue;
3137 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3138 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3139 OBJECT_CONFLICT_HARD_REGS (obj));
3140 #ifdef STACK_REGS
3141 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3142 #endif
3144 /* Fix final allocno attributes. */
3145 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3147 mem_dest_p = false;
3148 for (a = ira_regno_allocno_map[i];
3149 a != NULL;
3150 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3152 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3154 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3155 if (data->somewhere_renamed_p)
3156 new_pseudos_p = true;
3157 parent_a = ira_parent_allocno (a);
3158 if (parent_a == NULL)
3160 ALLOCNO_COPIES (a) = NULL;
3161 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3162 continue;
3164 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3166 if (data->mem_optimized_dest != NULL)
3167 mem_dest_p = true;
3168 parent_data = ALLOCNO_EMIT_DATA (parent_a);
3169 if (REGNO (data->reg) == REGNO (parent_data->reg))
3171 merge_hard_reg_conflicts (a, parent_a, true);
3172 move_allocno_live_ranges (a, parent_a);
3173 merged_p = true;
3174 parent_data->mem_optimized_dest_p
3175 = (parent_data->mem_optimized_dest_p
3176 || data->mem_optimized_dest_p);
3177 continue;
3179 new_pseudos_p = true;
3180 for (;;)
3182 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3183 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3184 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3185 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3186 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3187 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3188 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3189 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3190 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3191 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3192 && ALLOCNO_NREFS (parent_a) >= 0
3193 && ALLOCNO_FREQ (parent_a) >= 0);
3194 aclass = ALLOCNO_CLASS (parent_a);
3195 hard_regs_num = ira_class_hard_regs_num[aclass];
3196 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3197 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3198 for (j = 0; j < hard_regs_num; j++)
3199 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3200 -= ALLOCNO_HARD_REG_COSTS (a)[j];
3201 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3202 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3203 for (j = 0; j < hard_regs_num; j++)
3204 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3205 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3206 ALLOCNO_CLASS_COST (parent_a)
3207 -= ALLOCNO_CLASS_COST (a);
3208 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3209 parent_a = ira_parent_allocno (parent_a);
3210 if (parent_a == NULL)
3211 break;
3213 ALLOCNO_COPIES (a) = NULL;
3214 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3216 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3217 merged_p = true;
3219 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3220 if (merged_p || ira_max_point_before_emit != ira_max_point)
3221 ira_rebuild_start_finish_chains ();
3222 if (new_pseudos_p)
3224 sparseset objects_live;
3226 /* Rebuild conflicts. */
3227 FOR_EACH_ALLOCNO (a, ai)
3229 ira_allocno_object_iterator oi;
3230 ira_object_t obj;
3232 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3233 || ALLOCNO_CAP_MEMBER (a) != NULL)
3234 continue;
3235 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3237 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3238 ira_assert (r->object == obj);
3239 clear_conflicts (obj);
3242 objects_live = sparseset_alloc (ira_objects_num);
3243 for (i = 0; i < ira_max_point; i++)
3245 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3247 ira_object_t obj = r->object;
3249 a = OBJECT_ALLOCNO (obj);
3250 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3251 || ALLOCNO_CAP_MEMBER (a) != NULL)
3252 continue;
3254 aclass = ALLOCNO_CLASS (a);
3255 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3257 ira_object_t live_obj = ira_object_id_map[n];
3258 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3259 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3261 if (ira_reg_classes_intersect_p[aclass][live_aclass]
3262 /* Don't set up conflict for the allocno with itself. */
3263 && live_a != a)
3264 ira_add_conflict (obj, live_obj);
3266 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3269 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3270 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3272 sparseset_free (objects_live);
3273 compress_conflict_vecs ();
3275 /* Mark some copies for removing and change allocnos in the rest
3276 copies. */
3277 FOR_EACH_COPY (cp, ci)
3279 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3280 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3282 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3283 fprintf
3284 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3285 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3286 ALLOCNO_NUM (cp->first),
3287 REGNO (allocno_emit_reg (cp->first)),
3288 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3289 ALLOCNO_NUM (cp->second),
3290 REGNO (allocno_emit_reg (cp->second)));
3291 cp->loop_tree_node = NULL;
3292 continue;
3294 first
3295 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3296 second
3297 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3298 node = cp->loop_tree_node;
3299 if (node == NULL)
3300 keep_p = true; /* It copy generated in ira-emit.c. */
3301 else
3303 /* Check that the copy was not propagated from level on
3304 which we will have different pseudos. */
3305 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3306 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3307 keep_p = ((REGNO (allocno_emit_reg (first))
3308 == REGNO (allocno_emit_reg (node_first)))
3309 && (REGNO (allocno_emit_reg (second))
3310 == REGNO (allocno_emit_reg (node_second))));
3312 if (keep_p)
3314 cp->loop_tree_node = ira_loop_tree_root;
3315 cp->first = first;
3316 cp->second = second;
3318 else
3320 cp->loop_tree_node = NULL;
3321 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3322 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
3323 cp->num, ALLOCNO_NUM (cp->first),
3324 REGNO (allocno_emit_reg (cp->first)),
3325 ALLOCNO_NUM (cp->second),
3326 REGNO (allocno_emit_reg (cp->second)));
3329 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3330 FOR_EACH_ALLOCNO (a, ai)
3332 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3333 || ALLOCNO_CAP_MEMBER (a) != NULL)
3335 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3336 fprintf (ira_dump_file, " Remove a%dr%d\n",
3337 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3338 ira_remove_allocno_prefs (a);
3339 finish_allocno (a);
3340 continue;
3342 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3343 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3344 ALLOCNO_CAP (a) = NULL;
3345 /* Restore updated costs for assignments from reload. */
3346 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3347 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3348 if (! ALLOCNO_ASSIGNED_P (a))
3349 ira_free_allocno_updated_costs (a);
3350 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3351 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3353 /* Remove unnecessary copies. */
3354 FOR_EACH_COPY (cp, ci)
3356 if (cp->loop_tree_node == NULL)
3358 ira_copies[cp->num] = NULL;
3359 finish_copy (cp);
3360 continue;
3362 ira_assert
3363 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3364 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3365 add_allocno_copy_to_list (cp);
3366 swap_allocno_copy_ends_if_necessary (cp);
3368 rebuild_regno_allocno_maps ();
3369 if (ira_max_point != ira_max_point_before_emit)
3370 ira_compress_allocno_live_ranges ();
3371 ira_free (regno_top_level_allocno_map);
3376 #ifdef ENABLE_IRA_CHECKING
3377 /* Check creation of all allocnos. Allocnos on lower levels should
3378 have allocnos or caps on all upper levels. */
3379 static void
3380 check_allocno_creation (void)
3382 ira_allocno_t a;
3383 ira_allocno_iterator ai;
3384 ira_loop_tree_node_t loop_tree_node;
3386 FOR_EACH_ALLOCNO (a, ai)
3388 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3389 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3390 ALLOCNO_NUM (a)));
3391 if (loop_tree_node == ira_loop_tree_root)
3392 continue;
3393 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3394 ira_assert (ALLOCNO_CAP (a) != NULL);
3395 else if (ALLOCNO_CAP (a) == NULL)
3396 ira_assert (loop_tree_node->parent
3397 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3398 && bitmap_bit_p (loop_tree_node->border_allocnos,
3399 ALLOCNO_NUM (a)));
3402 #endif
3404 /* Identify allocnos which prefer a register class with a single hard register.
3405 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3406 less likely to use the preferred singleton register. */
3407 static void
3408 update_conflict_hard_reg_costs (void)
3410 ira_allocno_t a;
3411 ira_allocno_iterator ai;
3412 int i, index, min;
3414 FOR_EACH_ALLOCNO (a, ai)
3416 reg_class_t aclass = ALLOCNO_CLASS (a);
3417 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3418 int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3419 if (singleton < 0)
3420 continue;
3421 index = ira_class_hard_reg_index[(int) aclass][singleton];
3422 if (index < 0)
3423 continue;
3424 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3425 || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3426 continue;
3427 min = INT_MAX;
3428 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3429 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3430 && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3431 min = ALLOCNO_HARD_REG_COSTS (a)[i];
3432 if (min == INT_MAX)
3433 continue;
3434 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3435 aclass, 0);
3436 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3437 -= min - ALLOCNO_CLASS_COST (a);
3441 /* Create a internal representation (IR) for IRA (allocnos, copies,
3442 loop tree nodes). The function returns TRUE if we generate loop
3443 structure (besides nodes representing all function and the basic
3444 blocks) for regional allocation. A true return means that we
3445 really need to flatten IR before the reload. */
3446 bool
3447 ira_build (void)
3449 bool loops_p;
3451 df_analyze ();
3452 initiate_cost_vectors ();
3453 initiate_allocnos ();
3454 initiate_prefs ();
3455 initiate_copies ();
3456 create_loop_tree_nodes ();
3457 form_loop_tree ();
3458 create_allocnos ();
3459 ira_costs ();
3460 create_allocno_objects ();
3461 ira_create_allocno_live_ranges ();
3462 remove_unnecessary_regions (false);
3463 ira_compress_allocno_live_ranges ();
3464 update_bad_spill_attribute ();
3465 loops_p = more_one_region_p ();
3466 if (loops_p)
3468 propagate_allocno_info ();
3469 create_caps ();
3471 ira_tune_allocno_costs ();
3472 #ifdef ENABLE_IRA_CHECKING
3473 check_allocno_creation ();
3474 #endif
3475 setup_min_max_allocno_live_range_point ();
3476 sort_conflict_id_map ();
3477 setup_min_max_conflict_allocno_ids ();
3478 ira_build_conflicts ();
3479 update_conflict_hard_reg_costs ();
3480 if (! ira_conflicts_p)
3482 ira_allocno_t a;
3483 ira_allocno_iterator ai;
3485 /* Remove all regions but root one. */
3486 if (loops_p)
3488 remove_unnecessary_regions (true);
3489 loops_p = false;
3491 /* We don't save hard registers around calls for fast allocation
3492 -- add caller clobbered registers as conflicting ones to
3493 allocno crossing calls. */
3494 FOR_EACH_ALLOCNO (a, ai)
3495 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3496 ior_hard_reg_conflicts (a, &call_used_reg_set);
3498 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3499 print_copies (ira_dump_file);
3500 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3501 print_prefs (ira_dump_file);
3502 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3504 int n, nr, nr_big;
3505 ira_allocno_t a;
3506 live_range_t r;
3507 ira_allocno_iterator ai;
3509 n = 0;
3510 nr = 0;
3511 nr_big = 0;
3512 FOR_EACH_ALLOCNO (a, ai)
3514 int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3516 if (nobj > 1)
3517 nr_big++;
3518 for (j = 0; j < nobj; j++)
3520 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3521 n += OBJECT_NUM_CONFLICTS (obj);
3522 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3523 nr++;
3526 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
3527 current_loops == NULL ? 1 : number_of_loops (cfun),
3528 n_basic_blocks_for_fn (cfun), ira_max_point);
3529 fprintf (ira_dump_file,
3530 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3531 ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3533 return loops_p;
3536 /* Release the data created by function ira_build. */
3537 void
3538 ira_destroy (void)
3540 finish_loop_tree_nodes ();
3541 finish_prefs ();
3542 finish_copies ();
3543 finish_allocnos ();
3544 finish_cost_vectors ();
3545 ira_finish_allocno_live_ranges ();