1 /* Building internal representation for IRA.
2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5 This file is part of GCC.
6
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.
11
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.
16
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/>. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "predict.h"
28 #include "df.h"
29 #include "insn-config.h"
30 #include "regs.h"
31 #include "memmodel.h"
32 #include "ira.h"
33 #include "ira-int.h"
34 #include "sparseset.h"
35 #include "cfgloop.h"
36
37 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
38 ira_loop_tree_node_t);
39
40 /* The root of the loop tree corresponding to the all function. */
41 ira_loop_tree_node_t ira_loop_tree_root;
42
43 /* Height of the loop tree. */
44 int ira_loop_tree_height;
45
46 /* All nodes representing basic blocks are referred through the
47 following array. We cannot use basic block member `aux' for this
48 because it is used for insertion of insns on edges. */
49 ira_loop_tree_node_t ira_bb_nodes;
50
51 /* All nodes representing loops are referred through the following
52 array. */
53 ira_loop_tree_node_t ira_loop_nodes;
54
55 /* And size of the ira_loop_nodes array. */
56 unsigned int ira_loop_nodes_count;
57
58 /* Map regno -> allocnos with given regno (see comments for
59 allocno member `next_regno_allocno'). */
60 ira_allocno_t *ira_regno_allocno_map;
61
62 /* Array of references to all allocnos. The order number of the
63 allocno corresponds to the index in the array. Removed allocnos
64 have NULL element value. */
65 ira_allocno_t *ira_allocnos;
66
67 /* Sizes of the previous array. */
68 int ira_allocnos_num;
69
70 /* Count of conflict record structures we've created, used when creating
71 a new conflict id. */
72 int ira_objects_num;
73
74 /* Map a conflict id to its conflict record. */
75 ira_object_t *ira_object_id_map;
76
77 /* Array of references to all allocno preferences. The order number
78 of the preference corresponds to the index in the array. */
79 ira_pref_t *ira_prefs;
80
81 /* Size of the previous array. */
82 int ira_prefs_num;
83
84 /* Array of references to all copies. The order number of the copy
85 corresponds to the index in the array. Removed copies have NULL
86 element value. */
87 ira_copy_t *ira_copies;
88
89 /* Size of the previous array. */
90 int ira_copies_num;
91
92
93
94 /* LAST_BASIC_BLOCK before generating additional insns because of live
95 range splitting. Emitting insns on a critical edge creates a new
96 basic block. */
97 static int last_basic_block_before_change;
98
99 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
100 the member loop_num. */
101 static void
init_loop_tree_node(struct ira_loop_tree_node * node,int loop_num)102 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
103 {
104 int max_regno = max_reg_num ();
105
106 node->regno_allocno_map
107 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
108 memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
109 memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
110 node->all_allocnos = ira_allocate_bitmap ();
111 node->modified_regnos = ira_allocate_bitmap ();
112 node->border_allocnos = ira_allocate_bitmap ();
113 node->local_copies = ira_allocate_bitmap ();
114 node->loop_num = loop_num;
115 node->children = NULL;
116 node->subloops = NULL;
117 }
118
119
120 /* The following function allocates the loop tree nodes. If
121 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
122 the root which corresponds the all function) will be not allocated
123 but nodes will still be allocated for basic blocks. */
124 static void
create_loop_tree_nodes(void)125 create_loop_tree_nodes (void)
126 {
127 unsigned int i, j;
128 bool skip_p;
129 edge_iterator ei;
130 edge e;
131 vec<edge> edges;
132 loop_p loop;
133
134 ira_bb_nodes
135 = ((struct ira_loop_tree_node *)
136 ira_allocate (sizeof (struct ira_loop_tree_node)
137 * last_basic_block_for_fn (cfun)));
138 last_basic_block_before_change = last_basic_block_for_fn (cfun);
139 for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
140 {
141 ira_bb_nodes[i].regno_allocno_map = NULL;
142 memset (ira_bb_nodes[i].reg_pressure, 0,
143 sizeof (ira_bb_nodes[i].reg_pressure));
144 ira_bb_nodes[i].all_allocnos = NULL;
145 ira_bb_nodes[i].modified_regnos = NULL;
146 ira_bb_nodes[i].border_allocnos = NULL;
147 ira_bb_nodes[i].local_copies = NULL;
148 }
149 if (current_loops == NULL)
150 {
151 ira_loop_nodes_count = 1;
152 ira_loop_nodes = ((struct ira_loop_tree_node *)
153 ira_allocate (sizeof (struct ira_loop_tree_node)));
154 init_loop_tree_node (ira_loop_nodes, 0);
155 return;
156 }
157 ira_loop_nodes_count = number_of_loops (cfun);
158 ira_loop_nodes = ((struct ira_loop_tree_node *)
159 ira_allocate (sizeof (struct ira_loop_tree_node)
160 * ira_loop_nodes_count));
161 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
162 {
163 if (loop_outer (loop) != NULL)
164 {
165 ira_loop_nodes[i].regno_allocno_map = NULL;
166 skip_p = false;
167 FOR_EACH_EDGE (e, ei, loop->header->preds)
168 if (e->src != loop->latch
169 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
170 {
171 skip_p = true;
172 break;
173 }
174 if (skip_p)
175 continue;
176 edges = get_loop_exit_edges (loop);
177 FOR_EACH_VEC_ELT (edges, j, e)
178 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
179 {
180 skip_p = true;
181 break;
182 }
183 edges.release ();
184 if (skip_p)
185 continue;
186 }
187 init_loop_tree_node (&ira_loop_nodes[i], loop->num);
188 }
189 }
190
191 /* The function returns TRUE if there are more one allocation
192 region. */
193 static bool
more_one_region_p(void)194 more_one_region_p (void)
195 {
196 unsigned int i;
197 loop_p loop;
198
199 if (current_loops != NULL)
200 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
201 if (ira_loop_nodes[i].regno_allocno_map != NULL
202 && ira_loop_tree_root != &ira_loop_nodes[i])
203 return true;
204 return false;
205 }
206
207 /* Free the loop tree node of a loop. */
208 static void
finish_loop_tree_node(ira_loop_tree_node_t loop)209 finish_loop_tree_node (ira_loop_tree_node_t loop)
210 {
211 if (loop->regno_allocno_map != NULL)
212 {
213 ira_assert (loop->bb == NULL);
214 ira_free_bitmap (loop->local_copies);
215 ira_free_bitmap (loop->border_allocnos);
216 ira_free_bitmap (loop->modified_regnos);
217 ira_free_bitmap (loop->all_allocnos);
218 ira_free (loop->regno_allocno_map);
219 loop->regno_allocno_map = NULL;
220 }
221 }
222
223 /* Free the loop tree nodes. */
224 static void
finish_loop_tree_nodes(void)225 finish_loop_tree_nodes (void)
226 {
227 unsigned int i;
228
229 for (i = 0; i < ira_loop_nodes_count; i++)
230 finish_loop_tree_node (&ira_loop_nodes[i]);
231 ira_free (ira_loop_nodes);
232 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
233 {
234 if (ira_bb_nodes[i].local_copies != NULL)
235 ira_free_bitmap (ira_bb_nodes[i].local_copies);
236 if (ira_bb_nodes[i].border_allocnos != NULL)
237 ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
238 if (ira_bb_nodes[i].modified_regnos != NULL)
239 ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
240 if (ira_bb_nodes[i].all_allocnos != NULL)
241 ira_free_bitmap (ira_bb_nodes[i].all_allocnos);
242 if (ira_bb_nodes[i].regno_allocno_map != NULL)
243 ira_free (ira_bb_nodes[i].regno_allocno_map);
244 }
245 ira_free (ira_bb_nodes);
246 }
247
248
249
250 /* The following recursive function adds LOOP to the loop tree
251 hierarchy. LOOP is added only once. If LOOP is NULL we adding
252 loop designating the whole function when CFG loops are not
253 built. */
254 static void
add_loop_to_tree(class loop * loop)255 add_loop_to_tree (class loop *loop)
256 {
257 int loop_num;
258 class loop *parent;
259 ira_loop_tree_node_t loop_node, parent_node;
260
261 /* We cannot use loop node access macros here because of potential
262 checking and because the nodes are not initialized enough
263 yet. */
264 if (loop != NULL && loop_outer (loop) != NULL)
265 add_loop_to_tree (loop_outer (loop));
266 loop_num = loop != NULL ? loop->num : 0;
267 if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
268 && ira_loop_nodes[loop_num].children == NULL)
269 {
270 /* We have not added loop node to the tree yet. */
271 loop_node = &ira_loop_nodes[loop_num];
272 loop_node->loop = loop;
273 loop_node->bb = NULL;
274 if (loop == NULL)
275 parent = NULL;
276 else
277 {
278 for (parent = loop_outer (loop);
279 parent != NULL;
280 parent = loop_outer (parent))
281 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
282 break;
283 }
284 if (parent == NULL)
285 {
286 loop_node->next = NULL;
287 loop_node->subloop_next = NULL;
288 loop_node->parent = NULL;
289 }
290 else
291 {
292 parent_node = &ira_loop_nodes[parent->num];
293 loop_node->next = parent_node->children;
294 parent_node->children = loop_node;
295 loop_node->subloop_next = parent_node->subloops;
296 parent_node->subloops = loop_node;
297 loop_node->parent = parent_node;
298 }
299 }
300 }
301
302 /* The following recursive function sets up levels of nodes of the
303 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
304 The function returns maximal value of level in the tree + 1. */
305 static int
setup_loop_tree_level(ira_loop_tree_node_t loop_node,int level)306 setup_loop_tree_level (ira_loop_tree_node_t loop_node, int level)
307 {
308 int height, max_height;
309 ira_loop_tree_node_t subloop_node;
310
311 ira_assert (loop_node->bb == NULL);
312 loop_node->level = level;
313 max_height = level + 1;
314 for (subloop_node = loop_node->subloops;
315 subloop_node != NULL;
316 subloop_node = subloop_node->subloop_next)
317 {
318 ira_assert (subloop_node->bb == NULL);
319 height = setup_loop_tree_level (subloop_node, level + 1);
320 if (height > max_height)
321 max_height = height;
322 }
323 return max_height;
324 }
325
326 /* Create the loop tree. The algorithm is designed to provide correct
327 order of loops (they are ordered by their last loop BB) and basic
328 blocks in the chain formed by member next. */
329 static void
form_loop_tree(void)330 form_loop_tree (void)
331 {
332 basic_block bb;
333 class loop *parent;
334 ira_loop_tree_node_t bb_node, loop_node;
335
336 /* We cannot use loop/bb node access macros because of potential
337 checking and because the nodes are not initialized enough
338 yet. */
339 FOR_EACH_BB_FN (bb, cfun)
340 {
341 bb_node = &ira_bb_nodes[bb->index];
342 bb_node->bb = bb;
343 bb_node->loop = NULL;
344 bb_node->subloops = NULL;
345 bb_node->children = NULL;
346 bb_node->subloop_next = NULL;
347 bb_node->next = NULL;
348 if (current_loops == NULL)
349 parent = NULL;
350 else
351 {
352 for (parent = bb->loop_father;
353 parent != NULL;
354 parent = loop_outer (parent))
355 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
356 break;
357 }
358 add_loop_to_tree (parent);
359 loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
360 bb_node->next = loop_node->children;
361 bb_node->parent = loop_node;
362 loop_node->children = bb_node;
363 }
364 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
365 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
366 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
367 }
368
369
370
371 /* Rebuild IRA_REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs of the loop
372 tree nodes. */
373 static void
rebuild_regno_allocno_maps(void)374 rebuild_regno_allocno_maps (void)
375 {
376 unsigned int l;
377 int max_regno, regno;
378 ira_allocno_t a;
379 ira_loop_tree_node_t loop_tree_node;
380 loop_p loop;
381 ira_allocno_iterator ai;
382
383 ira_assert (current_loops != NULL);
384 max_regno = max_reg_num ();
385 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
386 if (ira_loop_nodes[l].regno_allocno_map != NULL)
387 {
388 ira_free (ira_loop_nodes[l].regno_allocno_map);
389 ira_loop_nodes[l].regno_allocno_map
390 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
391 * max_regno);
392 memset (ira_loop_nodes[l].regno_allocno_map, 0,
393 sizeof (ira_allocno_t) * max_regno);
394 }
395 ira_free (ira_regno_allocno_map);
396 ira_regno_allocno_map
397 = (ira_allocno_t *) ira_allocate (max_regno * sizeof (ira_allocno_t));
398 memset (ira_regno_allocno_map, 0, max_regno * sizeof (ira_allocno_t));
399 FOR_EACH_ALLOCNO (a, ai)
400 {
401 if (ALLOCNO_CAP_MEMBER (a) != NULL)
402 /* Caps are not in the regno allocno maps. */
403 continue;
404 regno = ALLOCNO_REGNO (a);
405 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
406 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
407 ira_regno_allocno_map[regno] = a;
408 if (loop_tree_node->regno_allocno_map[regno] == NULL)
409 /* Remember that we can create temporary allocnos to break
410 cycles in register shuffle. */
411 loop_tree_node->regno_allocno_map[regno] = a;
412 }
413 }
414
415
416 /* Pools for allocnos, allocno live ranges and objects. */
417 static object_allocator<live_range> live_range_pool ("live ranges");
418 static object_allocator<ira_allocno> allocno_pool ("allocnos");
419 static object_allocator<ira_object> object_pool ("objects");
420
421 /* Vec containing references to all created allocnos. It is a
422 container of array allocnos. */
423 static vec<ira_allocno_t> allocno_vec;
424
425 /* Vec containing references to all created ira_objects. It is a
426 container of ira_object_id_map. */
427 static vec<ira_object_t> ira_object_id_map_vec;
428
429 /* Initialize data concerning allocnos. */
430 static void
initiate_allocnos(void)431 initiate_allocnos (void)
432 {
433 allocno_vec.create (max_reg_num () * 2);
434 ira_allocnos = NULL;
435 ira_allocnos_num = 0;
436 ira_objects_num = 0;
437 ira_object_id_map_vec.create (max_reg_num () * 2);
438 ira_object_id_map = NULL;
439 ira_regno_allocno_map
440 = (ira_allocno_t *) ira_allocate (max_reg_num ()
441 * sizeof (ira_allocno_t));
442 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
443 }
444
445 /* Create and return an object corresponding to a new allocno A. */
446 static ira_object_t
ira_create_object(ira_allocno_t a,int subword)447 ira_create_object (ira_allocno_t a, int subword)
448 {
449 enum reg_class aclass = ALLOCNO_CLASS (a);
450 ira_object_t obj = object_pool.allocate ();
451
452 OBJECT_ALLOCNO (obj) = a;
453 OBJECT_SUBWORD (obj) = subword;
454 OBJECT_CONFLICT_ID (obj) = ira_objects_num;
455 OBJECT_CONFLICT_VEC_P (obj) = false;
456 OBJECT_CONFLICT_ARRAY (obj) = NULL;
457 OBJECT_NUM_CONFLICTS (obj) = 0;
458 OBJECT_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
459 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) = ira_no_alloc_regs;
460 OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
461 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
462 OBJECT_MIN (obj) = INT_MAX;
463 OBJECT_MAX (obj) = -1;
464 OBJECT_LIVE_RANGES (obj) = NULL;
465
466 ira_object_id_map_vec.safe_push (obj);
467 ira_object_id_map
468 = ira_object_id_map_vec.address ();
469 ira_objects_num = ira_object_id_map_vec.length ();
470
471 return obj;
472 }
473
474 /* Create and return the allocno corresponding to REGNO in
475 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
476 same regno if CAP_P is FALSE. */
477 ira_allocno_t
ira_create_allocno(int regno,bool cap_p,ira_loop_tree_node_t loop_tree_node)478 ira_create_allocno (int regno, bool cap_p,
479 ira_loop_tree_node_t loop_tree_node)
480 {
481 ira_allocno_t a;
482
483 a = allocno_pool.allocate ();
484 ALLOCNO_REGNO (a) = regno;
485 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
486 if (! cap_p)
487 {
488 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
489 ira_regno_allocno_map[regno] = a;
490 if (loop_tree_node->regno_allocno_map[regno] == NULL)
491 /* Remember that we can create temporary allocnos to break
492 cycles in register shuffle on region borders (see
493 ira-emit.c). */
494 loop_tree_node->regno_allocno_map[regno] = a;
495 }
496 ALLOCNO_CAP (a) = NULL;
497 ALLOCNO_CAP_MEMBER (a) = NULL;
498 ALLOCNO_NUM (a) = ira_allocnos_num;
499 bitmap_set_bit (loop_tree_node->all_allocnos, ALLOCNO_NUM (a));
500 ALLOCNO_NREFS (a) = 0;
501 ALLOCNO_FREQ (a) = 0;
502 ALLOCNO_HARD_REGNO (a) = -1;
503 ALLOCNO_CALL_FREQ (a) = 0;
504 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
505 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
506 ALLOCNO_CROSSED_CALLS_ABIS (a) = 0;
507 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
508 #ifdef STACK_REGS
509 ALLOCNO_NO_STACK_REG_P (a) = false;
510 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
511 #endif
512 ALLOCNO_DONT_REASSIGN_P (a) = false;
513 ALLOCNO_BAD_SPILL_P (a) = false;
514 ALLOCNO_ASSIGNED_P (a) = false;
515 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
516 ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
517 ALLOCNO_PREFS (a) = NULL;
518 ALLOCNO_COPIES (a) = NULL;
519 ALLOCNO_HARD_REG_COSTS (a) = NULL;
520 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
521 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
522 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
523 ALLOCNO_CLASS (a) = NO_REGS;
524 ALLOCNO_UPDATED_CLASS_COST (a) = 0;
525 ALLOCNO_CLASS_COST (a) = 0;
526 ALLOCNO_MEMORY_COST (a) = 0;
527 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
528 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
529 ALLOCNO_NUM_OBJECTS (a) = 0;
530
531 ALLOCNO_ADD_DATA (a) = NULL;
532 allocno_vec.safe_push (a);
533 ira_allocnos = allocno_vec.address ();
534 ira_allocnos_num = allocno_vec.length ();
535
536 return a;
537 }
538
539 /* Set up register class for A and update its conflict hard
540 registers. */
541 void
ira_set_allocno_class(ira_allocno_t a,enum reg_class aclass)542 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
543 {
544 ira_allocno_object_iterator oi;
545 ira_object_t obj;
546
547 ALLOCNO_CLASS (a) = aclass;
548 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
549 {
550 OBJECT_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
551 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= ~reg_class_contents[aclass];
552 }
553 }
554
555 /* Determine the number of objects we should associate with allocno A
556 and allocate them. */
557 void
ira_create_allocno_objects(ira_allocno_t a)558 ira_create_allocno_objects (ira_allocno_t a)
559 {
560 machine_mode mode = ALLOCNO_MODE (a);
561 enum reg_class aclass = ALLOCNO_CLASS (a);
562 int n = ira_reg_class_max_nregs[aclass][mode];
563 int i;
564
565 if (n != 2 || maybe_ne (GET_MODE_SIZE (mode), n * UNITS_PER_WORD))
566 n = 1;
567
568 ALLOCNO_NUM_OBJECTS (a) = n;
569 for (i = 0; i < n; i++)
570 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
571 }
572
573 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
574 ALLOCNO_OBJECT structures. This must be called after the allocno
575 classes are known. */
576 static void
create_allocno_objects(void)577 create_allocno_objects (void)
578 {
579 ira_allocno_t a;
580 ira_allocno_iterator ai;
581
582 FOR_EACH_ALLOCNO (a, ai)
583 ira_create_allocno_objects (a);
584 }
585
586 /* Merge hard register conflict information for all objects associated with
587 allocno TO into the corresponding objects associated with FROM.
588 If TOTAL_ONLY is true, we only merge OBJECT_TOTAL_CONFLICT_HARD_REGS. */
589 static void
merge_hard_reg_conflicts(ira_allocno_t from,ira_allocno_t to,bool total_only)590 merge_hard_reg_conflicts (ira_allocno_t from, ira_allocno_t to,
591 bool total_only)
592 {
593 int i;
594 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
595 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
596 {
597 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
598 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
599
600 if (!total_only)
601 OBJECT_CONFLICT_HARD_REGS (to_obj)
602 |= OBJECT_CONFLICT_HARD_REGS (from_obj);
603 OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj)
604 |= OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj);
605 }
606 #ifdef STACK_REGS
607 if (!total_only && ALLOCNO_NO_STACK_REG_P (from))
608 ALLOCNO_NO_STACK_REG_P (to) = true;
609 if (ALLOCNO_TOTAL_NO_STACK_REG_P (from))
610 ALLOCNO_TOTAL_NO_STACK_REG_P (to) = true;
611 #endif
612 }
613
614 /* Update hard register conflict information for all objects associated with
615 A to include the regs in SET. */
616 void
ior_hard_reg_conflicts(ira_allocno_t a,const_hard_reg_set set)617 ior_hard_reg_conflicts (ira_allocno_t a, const_hard_reg_set set)
618 {
619 ira_allocno_object_iterator i;
620 ira_object_t obj;
621
622 FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
623 {
624 OBJECT_CONFLICT_HARD_REGS (obj) |= set;
625 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj) |= set;
626 }
627 }
628
629 /* Return TRUE if a conflict vector with NUM elements is more
630 profitable than a conflict bit vector for OBJ. */
631 bool
ira_conflict_vector_profitable_p(ira_object_t obj,int num)632 ira_conflict_vector_profitable_p (ira_object_t obj, int num)
633 {
634 int nw;
635 int max = OBJECT_MAX (obj);
636 int min = OBJECT_MIN (obj);
637
638 if (max < min)
639 /* We prefer a bit vector in such case because it does not result
640 in allocation. */
641 return false;
642
643 nw = (max - min + IRA_INT_BITS) / IRA_INT_BITS;
644 return (2 * sizeof (ira_object_t) * (num + 1)
645 < 3 * nw * sizeof (IRA_INT_TYPE));
646 }
647
648 /* Allocates and initialize the conflict vector of OBJ for NUM
649 conflicting objects. */
650 void
ira_allocate_conflict_vec(ira_object_t obj,int num)651 ira_allocate_conflict_vec (ira_object_t obj, int num)
652 {
653 int size;
654 ira_object_t *vec;
655
656 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
657 num++; /* for NULL end marker */
658 size = sizeof (ira_object_t) * num;
659 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
660 vec = (ira_object_t *) OBJECT_CONFLICT_ARRAY (obj);
661 vec[0] = NULL;
662 OBJECT_NUM_CONFLICTS (obj) = 0;
663 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
664 OBJECT_CONFLICT_VEC_P (obj) = true;
665 }
666
667 /* Allocate and initialize the conflict bit vector of OBJ. */
668 static void
allocate_conflict_bit_vec(ira_object_t obj)669 allocate_conflict_bit_vec (ira_object_t obj)
670 {
671 unsigned int size;
672
673 ira_assert (OBJECT_CONFLICT_ARRAY (obj) == NULL);
674 size = ((OBJECT_MAX (obj) - OBJECT_MIN (obj) + IRA_INT_BITS)
675 / IRA_INT_BITS * sizeof (IRA_INT_TYPE));
676 OBJECT_CONFLICT_ARRAY (obj) = ira_allocate (size);
677 memset (OBJECT_CONFLICT_ARRAY (obj), 0, size);
678 OBJECT_CONFLICT_ARRAY_SIZE (obj) = size;
679 OBJECT_CONFLICT_VEC_P (obj) = false;
680 }
681
682 /* Allocate and initialize the conflict vector or conflict bit vector
683 of OBJ for NUM conflicting allocnos whatever is more profitable. */
684 void
ira_allocate_object_conflicts(ira_object_t obj,int num)685 ira_allocate_object_conflicts (ira_object_t obj, int num)
686 {
687 if (ira_conflict_vector_profitable_p (obj, num))
688 ira_allocate_conflict_vec (obj, num);
689 else
690 allocate_conflict_bit_vec (obj);
691 }
692
693 /* Add OBJ2 to the conflicts of OBJ1. */
694 static void
add_to_conflicts(ira_object_t obj1,ira_object_t obj2)695 add_to_conflicts (ira_object_t obj1, ira_object_t obj2)
696 {
697 int num;
698 unsigned int size;
699
700 if (OBJECT_CONFLICT_VEC_P (obj1))
701 {
702 ira_object_t *vec = OBJECT_CONFLICT_VEC (obj1);
703 int curr_num = OBJECT_NUM_CONFLICTS (obj1);
704 num = curr_num + 2;
705 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < num * sizeof (ira_object_t))
706 {
707 ira_object_t *newvec;
708 size = (3 * num / 2 + 1) * sizeof (ira_allocno_t);
709 newvec = (ira_object_t *) ira_allocate (size);
710 memcpy (newvec, vec, curr_num * sizeof (ira_object_t));
711 ira_free (vec);
712 vec = newvec;
713 OBJECT_CONFLICT_ARRAY (obj1) = vec;
714 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
715 }
716 vec[num - 2] = obj2;
717 vec[num - 1] = NULL;
718 OBJECT_NUM_CONFLICTS (obj1)++;
719 }
720 else
721 {
722 int nw, added_head_nw, id;
723 IRA_INT_TYPE *vec = OBJECT_CONFLICT_BITVEC (obj1);
724
725 id = OBJECT_CONFLICT_ID (obj2);
726 if (OBJECT_MIN (obj1) > id)
727 {
728 /* Expand head of the bit vector. */
729 added_head_nw = (OBJECT_MIN (obj1) - id - 1) / IRA_INT_BITS + 1;
730 nw = (OBJECT_MAX (obj1) - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
731 size = (nw + added_head_nw) * sizeof (IRA_INT_TYPE);
732 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) >= size)
733 {
734 memmove ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
735 vec, nw * sizeof (IRA_INT_TYPE));
736 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
737 }
738 else
739 {
740 size
741 = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (IRA_INT_TYPE);
742 vec = (IRA_INT_TYPE *) ira_allocate (size);
743 memcpy ((char *) vec + added_head_nw * sizeof (IRA_INT_TYPE),
744 OBJECT_CONFLICT_ARRAY (obj1), nw * sizeof (IRA_INT_TYPE));
745 memset (vec, 0, added_head_nw * sizeof (IRA_INT_TYPE));
746 memset ((char *) vec
747 + (nw + added_head_nw) * sizeof (IRA_INT_TYPE),
748 0, size - (nw + added_head_nw) * sizeof (IRA_INT_TYPE));
749 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
750 OBJECT_CONFLICT_ARRAY (obj1) = vec;
751 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
752 }
753 OBJECT_MIN (obj1) -= added_head_nw * IRA_INT_BITS;
754 }
755 else if (OBJECT_MAX (obj1) < id)
756 {
757 nw = (id - OBJECT_MIN (obj1)) / IRA_INT_BITS + 1;
758 size = nw * sizeof (IRA_INT_TYPE);
759 if (OBJECT_CONFLICT_ARRAY_SIZE (obj1) < size)
760 {
761 /* Expand tail of the bit vector. */
762 size = (3 * nw / 2 + 1) * sizeof (IRA_INT_TYPE);
763 vec = (IRA_INT_TYPE *) ira_allocate (size);
764 memcpy (vec, OBJECT_CONFLICT_ARRAY (obj1), OBJECT_CONFLICT_ARRAY_SIZE (obj1));
765 memset ((char *) vec + OBJECT_CONFLICT_ARRAY_SIZE (obj1),
766 0, size - OBJECT_CONFLICT_ARRAY_SIZE (obj1));
767 ira_free (OBJECT_CONFLICT_ARRAY (obj1));
768 OBJECT_CONFLICT_ARRAY (obj1) = vec;
769 OBJECT_CONFLICT_ARRAY_SIZE (obj1) = size;
770 }
771 OBJECT_MAX (obj1) = id;
772 }
773 SET_MINMAX_SET_BIT (vec, id, OBJECT_MIN (obj1), OBJECT_MAX (obj1));
774 }
775 }
776
777 /* Add OBJ1 to the conflicts of OBJ2 and vice versa. */
778 static void
ira_add_conflict(ira_object_t obj1,ira_object_t obj2)779 ira_add_conflict (ira_object_t obj1, ira_object_t obj2)
780 {
781 add_to_conflicts (obj1, obj2);
782 add_to_conflicts (obj2, obj1);
783 }
784
785 /* Clear all conflicts of OBJ. */
786 static void
clear_conflicts(ira_object_t obj)787 clear_conflicts (ira_object_t obj)
788 {
789 if (OBJECT_CONFLICT_VEC_P (obj))
790 {
791 OBJECT_NUM_CONFLICTS (obj) = 0;
792 OBJECT_CONFLICT_VEC (obj)[0] = NULL;
793 }
794 else if (OBJECT_CONFLICT_ARRAY_SIZE (obj) != 0)
795 {
796 int nw;
797
798 nw = (OBJECT_MAX (obj) - OBJECT_MIN (obj)) / IRA_INT_BITS + 1;
799 memset (OBJECT_CONFLICT_BITVEC (obj), 0, nw * sizeof (IRA_INT_TYPE));
800 }
801 }
802
803 /* The array used to find duplications in conflict vectors of
804 allocnos. */
805 static int *conflict_check;
806
807 /* The value used to mark allocation presence in conflict vector of
808 the current allocno. */
809 static int curr_conflict_check_tick;
810
811 /* Remove duplications in conflict vector of OBJ. */
812 static void
compress_conflict_vec(ira_object_t obj)813 compress_conflict_vec (ira_object_t obj)
814 {
815 ira_object_t *vec, conflict_obj;
816 int i, j;
817
818 ira_assert (OBJECT_CONFLICT_VEC_P (obj));
819 vec = OBJECT_CONFLICT_VEC (obj);
820 curr_conflict_check_tick++;
821 for (i = j = 0; (conflict_obj = vec[i]) != NULL; i++)
822 {
823 int id = OBJECT_CONFLICT_ID (conflict_obj);
824 if (conflict_check[id] != curr_conflict_check_tick)
825 {
826 conflict_check[id] = curr_conflict_check_tick;
827 vec[j++] = conflict_obj;
828 }
829 }
830 OBJECT_NUM_CONFLICTS (obj) = j;
831 vec[j] = NULL;
832 }
833
834 /* Remove duplications in conflict vectors of all allocnos. */
835 static void
compress_conflict_vecs(void)836 compress_conflict_vecs (void)
837 {
838 ira_object_t obj;
839 ira_object_iterator oi;
840
841 conflict_check = (int *) ira_allocate (sizeof (int) * ira_objects_num);
842 memset (conflict_check, 0, sizeof (int) * ira_objects_num);
843 curr_conflict_check_tick = 0;
844 FOR_EACH_OBJECT (obj, oi)
845 {
846 if (OBJECT_CONFLICT_VEC_P (obj))
847 compress_conflict_vec (obj);
848 }
849 ira_free (conflict_check);
850 }
851
852 /* This recursive function outputs allocno A and if it is a cap the
853 function outputs its members. */
854 void
ira_print_expanded_allocno(ira_allocno_t a)855 ira_print_expanded_allocno (ira_allocno_t a)
856 {
857 basic_block bb;
858
859 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
860 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
861 fprintf (ira_dump_file, ",b%d", bb->index);
862 else
863 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
864 if (ALLOCNO_CAP_MEMBER (a) != NULL)
865 {
866 fprintf (ira_dump_file, ":");
867 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
868 }
869 fprintf (ira_dump_file, ")");
870 }
871
872 /* Create and return the cap representing allocno A in the
873 parent loop. */
874 static ira_allocno_t
create_cap_allocno(ira_allocno_t a)875 create_cap_allocno (ira_allocno_t a)
876 {
877 ira_allocno_t cap;
878 ira_loop_tree_node_t parent;
879 enum reg_class aclass;
880
881 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
882 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
883 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
884 ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
885 aclass = ALLOCNO_CLASS (a);
886 ira_set_allocno_class (cap, aclass);
887 ira_create_allocno_objects (cap);
888 ALLOCNO_CAP_MEMBER (cap) = a;
889 ALLOCNO_CAP (a) = cap;
890 ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
891 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
892 ira_allocate_and_copy_costs
893 (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
894 ira_allocate_and_copy_costs
895 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
896 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
897 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
898 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
899 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
900 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
901
902 merge_hard_reg_conflicts (a, cap, false);
903
904 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
905 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
906 ALLOCNO_CROSSED_CALLS_ABIS (cap) = ALLOCNO_CROSSED_CALLS_ABIS (a);
907 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap)
908 = ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
909 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
910 {
911 fprintf (ira_dump_file, " Creating cap ");
912 ira_print_expanded_allocno (cap);
913 fprintf (ira_dump_file, "\n");
914 }
915 return cap;
916 }
917
918 /* Create and return a live range for OBJECT with given attributes. */
919 live_range_t
ira_create_live_range(ira_object_t obj,int start,int finish,live_range_t next)920 ira_create_live_range (ira_object_t obj, int start, int finish,
921 live_range_t next)
922 {
923 live_range_t p;
924
925 p = live_range_pool.allocate ();
926 p->object = obj;
927 p->start = start;
928 p->finish = finish;
929 p->next = next;
930 return p;
931 }
932
933 /* Create a new live range for OBJECT and queue it at the head of its
934 live range list. */
935 void
ira_add_live_range_to_object(ira_object_t object,int start,int finish)936 ira_add_live_range_to_object (ira_object_t object, int start, int finish)
937 {
938 live_range_t p;
939 p = ira_create_live_range (object, start, finish,
940 OBJECT_LIVE_RANGES (object));
941 OBJECT_LIVE_RANGES (object) = p;
942 }
943
944 /* Copy allocno live range R and return the result. */
945 static live_range_t
copy_live_range(live_range_t r)946 copy_live_range (live_range_t r)
947 {
948 live_range_t p;
949
950 p = live_range_pool.allocate ();
951 *p = *r;
952 return p;
953 }
954
955 /* Copy allocno live range list given by its head R and return the
956 result. */
957 live_range_t
ira_copy_live_range_list(live_range_t r)958 ira_copy_live_range_list (live_range_t r)
959 {
960 live_range_t p, first, last;
961
962 if (r == NULL)
963 return NULL;
964 for (first = last = NULL; r != NULL; r = r->next)
965 {
966 p = copy_live_range (r);
967 if (first == NULL)
968 first = p;
969 else
970 last->next = p;
971 last = p;
972 }
973 return first;
974 }
975
976 /* Merge ranges R1 and R2 and returns the result. The function
977 maintains the order of ranges and tries to minimize number of the
978 result ranges. */
979 live_range_t
ira_merge_live_ranges(live_range_t r1,live_range_t r2)980 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
981 {
982 live_range_t first, last;
983
984 if (r1 == NULL)
985 return r2;
986 if (r2 == NULL)
987 return r1;
988 for (first = last = NULL; r1 != NULL && r2 != NULL;)
989 {
990 if (r1->start < r2->start)
991 std::swap (r1, r2);
992 if (r1->start <= r2->finish + 1)
993 {
994 /* Intersected ranges: merge r1 and r2 into r1. */
995 r1->start = r2->start;
996 if (r1->finish < r2->finish)
997 r1->finish = r2->finish;
998 live_range_t temp = r2;
999 r2 = r2->next;
1000 ira_finish_live_range (temp);
1001 if (r2 == NULL)
1002 {
1003 /* To try to merge with subsequent ranges in r1. */
1004 r2 = r1->next;
1005 r1->next = NULL;
1006 }
1007 }
1008 else
1009 {
1010 /* Add r1 to the result. */
1011 if (first == NULL)
1012 first = last = r1;
1013 else
1014 {
1015 last->next = r1;
1016 last = r1;
1017 }
1018 r1 = r1->next;
1019 if (r1 == NULL)
1020 {
1021 /* To try to merge with subsequent ranges in r2. */
1022 r1 = r2->next;
1023 r2->next = NULL;
1024 }
1025 }
1026 }
1027 if (r1 != NULL)
1028 {
1029 if (first == NULL)
1030 first = r1;
1031 else
1032 last->next = r1;
1033 ira_assert (r1->next == NULL);
1034 }
1035 else if (r2 != NULL)
1036 {
1037 if (first == NULL)
1038 first = r2;
1039 else
1040 last->next = r2;
1041 ira_assert (r2->next == NULL);
1042 }
1043 else
1044 {
1045 ira_assert (last->next == NULL);
1046 }
1047 return first;
1048 }
1049
1050 /* Return TRUE if live ranges R1 and R2 intersect. */
1051 bool
ira_live_ranges_intersect_p(live_range_t r1,live_range_t r2)1052 ira_live_ranges_intersect_p (live_range_t r1, live_range_t r2)
1053 {
1054 /* Remember the live ranges are always kept ordered. */
1055 while (r1 != NULL && r2 != NULL)
1056 {
1057 if (r1->start > r2->finish)
1058 r1 = r1->next;
1059 else if (r2->start > r1->finish)
1060 r2 = r2->next;
1061 else
1062 return true;
1063 }
1064 return false;
1065 }
1066
1067 /* Free allocno live range R. */
1068 void
ira_finish_live_range(live_range_t r)1069 ira_finish_live_range (live_range_t r)
1070 {
1071 live_range_pool.remove (r);
1072 }
1073
1074 /* Free list of allocno live ranges starting with R. */
1075 void
ira_finish_live_range_list(live_range_t r)1076 ira_finish_live_range_list (live_range_t r)
1077 {
1078 live_range_t next_r;
1079
1080 for (; r != NULL; r = next_r)
1081 {
1082 next_r = r->next;
1083 ira_finish_live_range (r);
1084 }
1085 }
1086
1087 /* Free updated register costs of allocno A. */
1088 void
ira_free_allocno_updated_costs(ira_allocno_t a)1089 ira_free_allocno_updated_costs (ira_allocno_t a)
1090 {
1091 enum reg_class aclass;
1092
1093 aclass = ALLOCNO_CLASS (a);
1094 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1095 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1096 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1097 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1098 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1099 aclass);
1100 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1101 }
1102
1103 /* Free and nullify all cost vectors allocated earlier for allocno
1104 A. */
1105 static void
ira_free_allocno_costs(ira_allocno_t a)1106 ira_free_allocno_costs (ira_allocno_t a)
1107 {
1108 enum reg_class aclass = ALLOCNO_CLASS (a);
1109 ira_object_t obj;
1110 ira_allocno_object_iterator oi;
1111
1112 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1113 {
1114 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1115 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1116 if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1117 ira_free (OBJECT_CONFLICT_ARRAY (obj));
1118 object_pool.remove (obj);
1119 }
1120
1121 ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1122 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1123 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1124 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1125 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1126 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1127 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1128 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1129 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1130 aclass);
1131 ALLOCNO_HARD_REG_COSTS (a) = NULL;
1132 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1133 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1134 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1135 }
1136
1137 /* Free the memory allocated for allocno A. */
1138 static void
finish_allocno(ira_allocno_t a)1139 finish_allocno (ira_allocno_t a)
1140 {
1141 ira_free_allocno_costs (a);
1142 allocno_pool.remove (a);
1143 }
1144
1145 /* Free the memory allocated for all allocnos. */
1146 static void
finish_allocnos(void)1147 finish_allocnos (void)
1148 {
1149 ira_allocno_t a;
1150 ira_allocno_iterator ai;
1151
1152 FOR_EACH_ALLOCNO (a, ai)
1153 finish_allocno (a);
1154 ira_free (ira_regno_allocno_map);
1155 ira_object_id_map_vec.release ();
1156 allocno_vec.release ();
1157 allocno_pool.release ();
1158 object_pool.release ();
1159 live_range_pool.release ();
1160 }
1161
1162
1163
1164 /* Pools for allocno preferences. */
1165 static object_allocator <ira_allocno_pref> pref_pool ("prefs");
1166
1167 /* Vec containing references to all created preferences. It is a
1168 container of array ira_prefs. */
1169 static vec<ira_pref_t> pref_vec;
1170
1171 /* The function initializes data concerning allocno prefs. */
1172 static void
initiate_prefs(void)1173 initiate_prefs (void)
1174 {
1175 pref_vec.create (get_max_uid ());
1176 ira_prefs = NULL;
1177 ira_prefs_num = 0;
1178 }
1179
1180 /* Return pref for A and HARD_REGNO if any. */
1181 static ira_pref_t
find_allocno_pref(ira_allocno_t a,int hard_regno)1182 find_allocno_pref (ira_allocno_t a, int hard_regno)
1183 {
1184 ira_pref_t pref;
1185
1186 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1187 if (pref->allocno == a && pref->hard_regno == hard_regno)
1188 return pref;
1189 return NULL;
1190 }
1191
1192 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1193 ira_pref_t
ira_create_pref(ira_allocno_t a,int hard_regno,int freq)1194 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1195 {
1196 ira_pref_t pref;
1197
1198 pref = pref_pool.allocate ();
1199 pref->num = ira_prefs_num;
1200 pref->allocno = a;
1201 pref->hard_regno = hard_regno;
1202 pref->freq = freq;
1203 pref_vec.safe_push (pref);
1204 ira_prefs = pref_vec.address ();
1205 ira_prefs_num = pref_vec.length ();
1206 return pref;
1207 }
1208
1209 /* Attach a pref PREF to the corresponding allocno. */
1210 static void
add_allocno_pref_to_list(ira_pref_t pref)1211 add_allocno_pref_to_list (ira_pref_t pref)
1212 {
1213 ira_allocno_t a = pref->allocno;
1214
1215 pref->next_pref = ALLOCNO_PREFS (a);
1216 ALLOCNO_PREFS (a) = pref;
1217 }
1218
1219 /* Create (or update frequency if the pref already exists) the pref of
1220 allocnos A preferring HARD_REGNO with frequency FREQ. */
1221 void
ira_add_allocno_pref(ira_allocno_t a,int hard_regno,int freq)1222 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1223 {
1224 ira_pref_t pref;
1225
1226 if (freq <= 0)
1227 return;
1228 if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1229 {
1230 pref->freq += freq;
1231 return;
1232 }
1233 pref = ira_create_pref (a, hard_regno, freq);
1234 ira_assert (a != NULL);
1235 add_allocno_pref_to_list (pref);
1236 }
1237
1238 /* Print info about PREF into file F. */
1239 static void
print_pref(FILE * f,ira_pref_t pref)1240 print_pref (FILE *f, ira_pref_t pref)
1241 {
1242 fprintf (f, " pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1243 ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1244 pref->hard_regno, pref->freq);
1245 }
1246
1247 /* Print info about PREF into stderr. */
1248 void
ira_debug_pref(ira_pref_t pref)1249 ira_debug_pref (ira_pref_t pref)
1250 {
1251 print_pref (stderr, pref);
1252 }
1253
1254 /* Print info about all prefs into file F. */
1255 static void
print_prefs(FILE * f)1256 print_prefs (FILE *f)
1257 {
1258 ira_pref_t pref;
1259 ira_pref_iterator pi;
1260
1261 FOR_EACH_PREF (pref, pi)
1262 print_pref (f, pref);
1263 }
1264
1265 /* Print info about all prefs into stderr. */
1266 void
ira_debug_prefs(void)1267 ira_debug_prefs (void)
1268 {
1269 print_prefs (stderr);
1270 }
1271
1272 /* Print info about prefs involving allocno A into file F. */
1273 static void
print_allocno_prefs(FILE * f,ira_allocno_t a)1274 print_allocno_prefs (FILE *f, ira_allocno_t a)
1275 {
1276 ira_pref_t pref;
1277
1278 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1279 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1280 fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1281 fprintf (f, "\n");
1282 }
1283
1284 /* Print info about prefs involving allocno A into stderr. */
1285 void
ira_debug_allocno_prefs(ira_allocno_t a)1286 ira_debug_allocno_prefs (ira_allocno_t a)
1287 {
1288 print_allocno_prefs (stderr, a);
1289 }
1290
1291 /* The function frees memory allocated for PREF. */
1292 static void
finish_pref(ira_pref_t pref)1293 finish_pref (ira_pref_t pref)
1294 {
1295 ira_prefs[pref->num] = NULL;
1296 pref_pool.remove (pref);
1297 }
1298
1299 /* Remove PREF from the list of allocno prefs and free memory for
1300 it. */
1301 void
ira_remove_pref(ira_pref_t pref)1302 ira_remove_pref (ira_pref_t pref)
1303 {
1304 ira_pref_t cpref, prev;
1305
1306 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1307 fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1308 pref->num, pref->hard_regno, pref->freq);
1309 for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1310 cpref != NULL;
1311 prev = cpref, cpref = cpref->next_pref)
1312 if (cpref == pref)
1313 break;
1314 ira_assert (cpref != NULL);
1315 if (prev == NULL)
1316 ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1317 else
1318 prev->next_pref = pref->next_pref;
1319 finish_pref (pref);
1320 }
1321
1322 /* Remove all prefs of allocno A. */
1323 void
ira_remove_allocno_prefs(ira_allocno_t a)1324 ira_remove_allocno_prefs (ira_allocno_t a)
1325 {
1326 ira_pref_t pref, next_pref;
1327
1328 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1329 {
1330 next_pref = pref->next_pref;
1331 finish_pref (pref);
1332 }
1333 ALLOCNO_PREFS (a) = NULL;
1334 }
1335
1336 /* Free memory allocated for all prefs. */
1337 static void
finish_prefs(void)1338 finish_prefs (void)
1339 {
1340 ira_pref_t pref;
1341 ira_pref_iterator pi;
1342
1343 FOR_EACH_PREF (pref, pi)
1344 finish_pref (pref);
1345 pref_vec.release ();
1346 pref_pool.release ();
1347 }
1348
1349
1350
1351 /* Pools for copies. */
1352 static object_allocator<ira_allocno_copy> copy_pool ("copies");
1353
1354 /* Vec containing references to all created copies. It is a
1355 container of array ira_copies. */
1356 static vec<ira_copy_t> copy_vec;
1357
1358 /* The function initializes data concerning allocno copies. */
1359 static void
initiate_copies(void)1360 initiate_copies (void)
1361 {
1362 copy_vec.create (get_max_uid ());
1363 ira_copies = NULL;
1364 ira_copies_num = 0;
1365 }
1366
1367 /* Return copy connecting A1 and A2 and originated from INSN of
1368 LOOP_TREE_NODE if any. */
1369 static ira_copy_t
find_allocno_copy(ira_allocno_t a1,ira_allocno_t a2,rtx_insn * insn,ira_loop_tree_node_t loop_tree_node)1370 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1371 ira_loop_tree_node_t loop_tree_node)
1372 {
1373 ira_copy_t cp, next_cp;
1374 ira_allocno_t another_a;
1375
1376 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1377 {
1378 if (cp->first == a1)
1379 {
1380 next_cp = cp->next_first_allocno_copy;
1381 another_a = cp->second;
1382 }
1383 else if (cp->second == a1)
1384 {
1385 next_cp = cp->next_second_allocno_copy;
1386 another_a = cp->first;
1387 }
1388 else
1389 gcc_unreachable ();
1390 if (another_a == a2 && cp->insn == insn
1391 && cp->loop_tree_node == loop_tree_node)
1392 return cp;
1393 }
1394 return NULL;
1395 }
1396
1397 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1398 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1399 ira_copy_t
ira_create_copy(ira_allocno_t first,ira_allocno_t second,int freq,bool constraint_p,rtx_insn * insn,ira_loop_tree_node_t loop_tree_node)1400 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1401 bool constraint_p, rtx_insn *insn,
1402 ira_loop_tree_node_t loop_tree_node)
1403 {
1404 ira_copy_t cp;
1405
1406 cp = copy_pool.allocate ();
1407 cp->num = ira_copies_num;
1408 cp->first = first;
1409 cp->second = second;
1410 cp->freq = freq;
1411 cp->constraint_p = constraint_p;
1412 cp->insn = insn;
1413 cp->loop_tree_node = loop_tree_node;
1414 copy_vec.safe_push (cp);
1415 ira_copies = copy_vec.address ();
1416 ira_copies_num = copy_vec.length ();
1417 return cp;
1418 }
1419
1420 /* Attach a copy CP to allocnos involved into the copy. */
1421 static void
add_allocno_copy_to_list(ira_copy_t cp)1422 add_allocno_copy_to_list (ira_copy_t cp)
1423 {
1424 ira_allocno_t first = cp->first, second = cp->second;
1425
1426 cp->prev_first_allocno_copy = NULL;
1427 cp->prev_second_allocno_copy = NULL;
1428 cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1429 if (cp->next_first_allocno_copy != NULL)
1430 {
1431 if (cp->next_first_allocno_copy->first == first)
1432 cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1433 else
1434 cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1435 }
1436 cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1437 if (cp->next_second_allocno_copy != NULL)
1438 {
1439 if (cp->next_second_allocno_copy->second == second)
1440 cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1441 else
1442 cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1443 }
1444 ALLOCNO_COPIES (first) = cp;
1445 ALLOCNO_COPIES (second) = cp;
1446 }
1447
1448 /* Make a copy CP a canonical copy where number of the
1449 first allocno is less than the second one. */
1450 static void
swap_allocno_copy_ends_if_necessary(ira_copy_t cp)1451 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1452 {
1453 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1454 return;
1455
1456 std::swap (cp->first, cp->second);
1457 std::swap (cp->prev_first_allocno_copy, cp->prev_second_allocno_copy);
1458 std::swap (cp->next_first_allocno_copy, cp->next_second_allocno_copy);
1459 }
1460
1461 /* Create (or update frequency if the copy already exists) and return
1462 the copy of allocnos FIRST and SECOND with frequency FREQ
1463 corresponding to move insn INSN (if any) and originated from
1464 LOOP_TREE_NODE. */
1465 ira_copy_t
ira_add_allocno_copy(ira_allocno_t first,ira_allocno_t second,int freq,bool constraint_p,rtx_insn * insn,ira_loop_tree_node_t loop_tree_node)1466 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1467 bool constraint_p, rtx_insn *insn,
1468 ira_loop_tree_node_t loop_tree_node)
1469 {
1470 ira_copy_t cp;
1471
1472 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1473 {
1474 cp->freq += freq;
1475 return cp;
1476 }
1477 cp = ira_create_copy (first, second, freq, constraint_p, insn,
1478 loop_tree_node);
1479 ira_assert (first != NULL && second != NULL);
1480 add_allocno_copy_to_list (cp);
1481 swap_allocno_copy_ends_if_necessary (cp);
1482 return cp;
1483 }
1484
1485 /* Print info about copy CP into file F. */
1486 static void
print_copy(FILE * f,ira_copy_t cp)1487 print_copy (FILE *f, ira_copy_t cp)
1488 {
1489 fprintf (f, " cp%d:a%d(r%d)<->a%d(r%d)@%d:%s\n", cp->num,
1490 ALLOCNO_NUM (cp->first), ALLOCNO_REGNO (cp->first),
1491 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1492 cp->insn != NULL
1493 ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1494 }
1495
1496 DEBUG_FUNCTION void
debug(ira_allocno_copy & ref)1497 debug (ira_allocno_copy &ref)
1498 {
1499 print_copy (stderr, &ref);
1500 }
1501
1502 DEBUG_FUNCTION void
debug(ira_allocno_copy * ptr)1503 debug (ira_allocno_copy *ptr)
1504 {
1505 if (ptr)
1506 debug (*ptr);
1507 else
1508 fprintf (stderr, "<nil>\n");
1509 }
1510
1511 /* Print info about copy CP into stderr. */
1512 void
ira_debug_copy(ira_copy_t cp)1513 ira_debug_copy (ira_copy_t cp)
1514 {
1515 print_copy (stderr, cp);
1516 }
1517
1518 /* Print info about all copies into file F. */
1519 static void
print_copies(FILE * f)1520 print_copies (FILE *f)
1521 {
1522 ira_copy_t cp;
1523 ira_copy_iterator ci;
1524
1525 FOR_EACH_COPY (cp, ci)
1526 print_copy (f, cp);
1527 }
1528
1529 /* Print info about all copies into stderr. */
1530 void
ira_debug_copies(void)1531 ira_debug_copies (void)
1532 {
1533 print_copies (stderr);
1534 }
1535
1536 /* Print info about copies involving allocno A into file F. */
1537 static void
print_allocno_copies(FILE * f,ira_allocno_t a)1538 print_allocno_copies (FILE *f, ira_allocno_t a)
1539 {
1540 ira_allocno_t another_a;
1541 ira_copy_t cp, next_cp;
1542
1543 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1544 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1545 {
1546 if (cp->first == a)
1547 {
1548 next_cp = cp->next_first_allocno_copy;
1549 another_a = cp->second;
1550 }
1551 else if (cp->second == a)
1552 {
1553 next_cp = cp->next_second_allocno_copy;
1554 another_a = cp->first;
1555 }
1556 else
1557 gcc_unreachable ();
1558 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1559 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1560 }
1561 fprintf (f, "\n");
1562 }
1563
1564 DEBUG_FUNCTION void
debug(ira_allocno & ref)1565 debug (ira_allocno &ref)
1566 {
1567 print_allocno_copies (stderr, &ref);
1568 }
1569
1570 DEBUG_FUNCTION void
debug(ira_allocno * ptr)1571 debug (ira_allocno *ptr)
1572 {
1573 if (ptr)
1574 debug (*ptr);
1575 else
1576 fprintf (stderr, "<nil>\n");
1577 }
1578
1579
1580 /* Print info about copies involving allocno A into stderr. */
1581 void
ira_debug_allocno_copies(ira_allocno_t a)1582 ira_debug_allocno_copies (ira_allocno_t a)
1583 {
1584 print_allocno_copies (stderr, a);
1585 }
1586
1587 /* The function frees memory allocated for copy CP. */
1588 static void
finish_copy(ira_copy_t cp)1589 finish_copy (ira_copy_t cp)
1590 {
1591 copy_pool.remove (cp);
1592 }
1593
1594
1595 /* Free memory allocated for all copies. */
1596 static void
finish_copies(void)1597 finish_copies (void)
1598 {
1599 ira_copy_t cp;
1600 ira_copy_iterator ci;
1601
1602 FOR_EACH_COPY (cp, ci)
1603 finish_copy (cp);
1604 copy_vec.release ();
1605 copy_pool.release ();
1606 }
1607
1608
1609
1610 /* Pools for cost vectors. It is defined only for allocno classes. */
1611 static pool_allocator *cost_vector_pool[N_REG_CLASSES];
1612
1613 /* The function initiates work with hard register cost vectors. It
1614 creates allocation pool for each allocno class. */
1615 static void
initiate_cost_vectors(void)1616 initiate_cost_vectors (void)
1617 {
1618 int i;
1619 enum reg_class aclass;
1620
1621 for (i = 0; i < ira_allocno_classes_num; i++)
1622 {
1623 aclass = ira_allocno_classes[i];
1624 cost_vector_pool[aclass] = new pool_allocator
1625 ("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
1626 }
1627 }
1628
1629 /* Allocate and return a cost vector VEC for ACLASS. */
1630 int *
ira_allocate_cost_vector(reg_class_t aclass)1631 ira_allocate_cost_vector (reg_class_t aclass)
1632 {
1633 return (int*) cost_vector_pool[(int) aclass]->allocate ();
1634 }
1635
1636 /* Free a cost vector VEC for ACLASS. */
1637 void
ira_free_cost_vector(int * vec,reg_class_t aclass)1638 ira_free_cost_vector (int *vec, reg_class_t aclass)
1639 {
1640 ira_assert (vec != NULL);
1641 cost_vector_pool[(int) aclass]->remove (vec);
1642 }
1643
1644 /* Finish work with hard register cost vectors. Release allocation
1645 pool for each allocno class. */
1646 static void
finish_cost_vectors(void)1647 finish_cost_vectors (void)
1648 {
1649 int i;
1650 enum reg_class aclass;
1651
1652 for (i = 0; i < ira_allocno_classes_num; i++)
1653 {
1654 aclass = ira_allocno_classes[i];
1655 delete cost_vector_pool[aclass];
1656 }
1657 }
1658
1659
1660
1661 /* Compute a post-ordering of the reverse control flow of the loop body
1662 designated by the children nodes of LOOP_NODE, whose body nodes in
1663 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1664 of the reverse loop body.
1665
1666 For the post-order of the reverse CFG, we visit the basic blocks in
1667 LOOP_PREORDER array in the reverse order of where they appear.
1668 This is important: We do not just want to compute a post-order of
1669 the reverse CFG, we want to make a best-guess for a visiting order that
1670 minimizes the number of chain elements per allocno live range. If the
1671 blocks would be visited in a different order, we would still compute a
1672 correct post-ordering but it would be less likely that two nodes
1673 connected by an edge in the CFG are neighbors in the topsort. */
1674
1675 static vec<ira_loop_tree_node_t>
ira_loop_tree_body_rev_postorder(ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,vec<ira_loop_tree_node_t> loop_preorder)1676 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1677 vec<ira_loop_tree_node_t> loop_preorder)
1678 {
1679 vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1680 unsigned int n_loop_preorder;
1681
1682 n_loop_preorder = loop_preorder.length ();
1683 if (n_loop_preorder != 0)
1684 {
1685 ira_loop_tree_node_t subloop_node;
1686 unsigned int i;
1687 auto_vec<ira_loop_tree_node_t> dfs_stack;
1688
1689 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1690 the flag to mark blocks we still have to visit to add them to
1691 our post-order. Define an alias to avoid confusion. */
1692 #define BB_TO_VISIT BB_VISITED
1693
1694 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1695 {
1696 gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1697 subloop_node->bb->flags |= BB_TO_VISIT;
1698 }
1699
1700 topsort_nodes.create (n_loop_preorder);
1701 dfs_stack.create (n_loop_preorder);
1702
1703 FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1704 {
1705 if (! (subloop_node->bb->flags & BB_TO_VISIT))
1706 continue;
1707
1708 subloop_node->bb->flags &= ~BB_TO_VISIT;
1709 dfs_stack.quick_push (subloop_node);
1710 while (! dfs_stack.is_empty ())
1711 {
1712 edge e;
1713 edge_iterator ei;
1714
1715 ira_loop_tree_node_t n = dfs_stack.last ();
1716 FOR_EACH_EDGE (e, ei, n->bb->preds)
1717 {
1718 ira_loop_tree_node_t pred_node;
1719 basic_block pred_bb = e->src;
1720
1721 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1722 continue;
1723
1724 pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1725 if (pred_node != n
1726 && (pred_node->bb->flags & BB_TO_VISIT))
1727 {
1728 pred_node->bb->flags &= ~BB_TO_VISIT;
1729 dfs_stack.quick_push (pred_node);
1730 }
1731 }
1732 if (n == dfs_stack.last ())
1733 {
1734 dfs_stack.pop ();
1735 topsort_nodes.quick_push (n);
1736 }
1737 }
1738 }
1739
1740 #undef BB_TO_VISIT
1741 }
1742
1743 gcc_assert (topsort_nodes.length () == n_loop_preorder);
1744 return topsort_nodes;
1745 }
1746
1747 /* The current loop tree node and its regno allocno map. */
1748 ira_loop_tree_node_t ira_curr_loop_tree_node;
1749 ira_allocno_t *ira_curr_regno_allocno_map;
1750
1751 /* This recursive function traverses loop tree with root LOOP_NODE
1752 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1753 correspondingly in preorder and postorder. The function sets up
1754 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1755 basic block nodes of LOOP_NODE is also processed (before its
1756 subloop nodes).
1757
1758 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1759 the loop are passed in the *reverse* post-order of the *reverse*
1760 CFG. This is only used by ira_create_allocno_live_ranges, which
1761 wants to visit basic blocks in this order to minimize the number
1762 of elements per live range chain.
1763 Note that the loop tree nodes are still visited in the normal,
1764 forward post-order of the loop tree. */
1765
1766 void
ira_traverse_loop_tree(bool bb_p,ira_loop_tree_node_t loop_node,void (* preorder_func)(ira_loop_tree_node_t),void (* postorder_func)(ira_loop_tree_node_t))1767 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1768 void (*preorder_func) (ira_loop_tree_node_t),
1769 void (*postorder_func) (ira_loop_tree_node_t))
1770 {
1771 ira_loop_tree_node_t subloop_node;
1772
1773 ira_assert (loop_node->bb == NULL);
1774 ira_curr_loop_tree_node = loop_node;
1775 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1776
1777 if (preorder_func != NULL)
1778 (*preorder_func) (loop_node);
1779
1780 if (bb_p)
1781 {
1782 auto_vec<ira_loop_tree_node_t> loop_preorder;
1783 unsigned int i;
1784
1785 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1786 is set up such that nodes in the loop body appear in a pre-order
1787 of their place in the CFG. */
1788 for (subloop_node = loop_node->children;
1789 subloop_node != NULL;
1790 subloop_node = subloop_node->next)
1791 if (subloop_node->bb != NULL)
1792 loop_preorder.safe_push (subloop_node);
1793
1794 if (preorder_func != NULL)
1795 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1796 (*preorder_func) (subloop_node);
1797
1798 if (postorder_func != NULL)
1799 {
1800 vec<ira_loop_tree_node_t> loop_rev_postorder =
1801 ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1802 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1803 (*postorder_func) (subloop_node);
1804 loop_rev_postorder.release ();
1805 }
1806 }
1807
1808 for (subloop_node = loop_node->subloops;
1809 subloop_node != NULL;
1810 subloop_node = subloop_node->subloop_next)
1811 {
1812 ira_assert (subloop_node->bb == NULL);
1813 ira_traverse_loop_tree (bb_p, subloop_node,
1814 preorder_func, postorder_func);
1815 }
1816
1817 ira_curr_loop_tree_node = loop_node;
1818 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1819
1820 if (postorder_func != NULL)
1821 (*postorder_func) (loop_node);
1822 }
1823
1824
1825
1826 /* The basic block currently being processed. */
1827 static basic_block curr_bb;
1828
1829 /* This recursive function creates allocnos corresponding to
1830 pseudo-registers containing in X. True OUTPUT_P means that X is
1831 an lvalue. PARENT corresponds to the parent expression of X. */
1832 static void
create_insn_allocnos(rtx x,rtx outer,bool output_p)1833 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1834 {
1835 int i, j;
1836 const char *fmt;
1837 enum rtx_code code = GET_CODE (x);
1838
1839 if (code == REG)
1840 {
1841 int regno;
1842
1843 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1844 {
1845 ira_allocno_t a;
1846
1847 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1848 {
1849 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1850 if (outer != NULL && GET_CODE (outer) == SUBREG)
1851 {
1852 machine_mode wmode = GET_MODE (outer);
1853 if (partial_subreg_p (ALLOCNO_WMODE (a), wmode))
1854 ALLOCNO_WMODE (a) = wmode;
1855 }
1856 }
1857
1858 ALLOCNO_NREFS (a)++;
1859 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1860 if (output_p)
1861 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1862 }
1863 return;
1864 }
1865 else if (code == SET)
1866 {
1867 create_insn_allocnos (SET_DEST (x), NULL, true);
1868 create_insn_allocnos (SET_SRC (x), NULL, false);
1869 return;
1870 }
1871 else if (code == CLOBBER)
1872 {
1873 create_insn_allocnos (XEXP (x, 0), NULL, true);
1874 return;
1875 }
1876 else if (code == MEM)
1877 {
1878 create_insn_allocnos (XEXP (x, 0), NULL, false);
1879 return;
1880 }
1881 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1882 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1883 {
1884 create_insn_allocnos (XEXP (x, 0), NULL, true);
1885 create_insn_allocnos (XEXP (x, 0), NULL, false);
1886 return;
1887 }
1888
1889 fmt = GET_RTX_FORMAT (code);
1890 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1891 {
1892 if (fmt[i] == 'e')
1893 create_insn_allocnos (XEXP (x, i), x, output_p);
1894 else if (fmt[i] == 'E')
1895 for (j = 0; j < XVECLEN (x, i); j++)
1896 create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1897 }
1898 }
1899
1900 /* Create allocnos corresponding to pseudo-registers living in the
1901 basic block represented by the corresponding loop tree node
1902 BB_NODE. */
1903 static void
create_bb_allocnos(ira_loop_tree_node_t bb_node)1904 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1905 {
1906 basic_block bb;
1907 rtx_insn *insn;
1908 unsigned int i;
1909 bitmap_iterator bi;
1910
1911 curr_bb = bb = bb_node->bb;
1912 ira_assert (bb != NULL);
1913 FOR_BB_INSNS_REVERSE (bb, insn)
1914 if (NONDEBUG_INSN_P (insn))
1915 create_insn_allocnos (PATTERN (insn), NULL, false);
1916 /* It might be a allocno living through from one subloop to
1917 another. */
1918 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1919 if (ira_curr_regno_allocno_map[i] == NULL)
1920 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1921 }
1922
1923 /* Create allocnos corresponding to pseudo-registers living on edge E
1924 (a loop entry or exit). Also mark the allocnos as living on the
1925 loop border. */
1926 static void
create_loop_allocnos(edge e)1927 create_loop_allocnos (edge e)
1928 {
1929 unsigned int i;
1930 bitmap live_in_regs, border_allocnos;
1931 bitmap_iterator bi;
1932 ira_loop_tree_node_t parent;
1933
1934 live_in_regs = df_get_live_in (e->dest);
1935 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1936 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1937 FIRST_PSEUDO_REGISTER, i, bi)
1938 if (bitmap_bit_p (live_in_regs, i))
1939 {
1940 if (ira_curr_regno_allocno_map[i] == NULL)
1941 {
1942 /* The order of creations is important for right
1943 ira_regno_allocno_map. */
1944 if ((parent = ira_curr_loop_tree_node->parent) != NULL
1945 && parent->regno_allocno_map[i] == NULL)
1946 ira_create_allocno (i, false, parent);
1947 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1948 }
1949 bitmap_set_bit (border_allocnos,
1950 ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1951 }
1952 }
1953
1954 /* Create allocnos corresponding to pseudo-registers living in loop
1955 represented by the corresponding loop tree node LOOP_NODE. This
1956 function is called by ira_traverse_loop_tree. */
1957 static void
create_loop_tree_node_allocnos(ira_loop_tree_node_t loop_node)1958 create_loop_tree_node_allocnos (ira_loop_tree_node_t loop_node)
1959 {
1960 if (loop_node->bb != NULL)
1961 create_bb_allocnos (loop_node);
1962 else if (loop_node != ira_loop_tree_root)
1963 {
1964 int i;
1965 edge_iterator ei;
1966 edge e;
1967 vec<edge> edges;
1968
1969 ira_assert (current_loops != NULL);
1970 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1971 if (e->src != loop_node->loop->latch)
1972 create_loop_allocnos (e);
1973
1974 edges = get_loop_exit_edges (loop_node->loop);
1975 FOR_EACH_VEC_ELT (edges, i, e)
1976 create_loop_allocnos (e);
1977 edges.release ();
1978 }
1979 }
1980
1981 /* Propagate information about allocnos modified inside the loop given
1982 by its LOOP_TREE_NODE to its parent. */
1983 static void
propagate_modified_regnos(ira_loop_tree_node_t loop_tree_node)1984 propagate_modified_regnos (ira_loop_tree_node_t loop_tree_node)
1985 {
1986 if (loop_tree_node == ira_loop_tree_root)
1987 return;
1988 ira_assert (loop_tree_node->bb == NULL);
1989 bitmap_ior_into (loop_tree_node->parent->modified_regnos,
1990 loop_tree_node->modified_regnos);
1991 }
1992
1993 /* Propagate new info about allocno A (see comments about accumulated
1994 info in allocno definition) to the corresponding allocno on upper
1995 loop tree level. So allocnos on upper levels accumulate
1996 information about the corresponding allocnos in nested regions.
1997 The new info means allocno info finally calculated in this
1998 file. */
1999 static void
propagate_allocno_info(void)2000 propagate_allocno_info (void)
2001 {
2002 int i;
2003 ira_allocno_t a, parent_a;
2004 ira_loop_tree_node_t parent;
2005 enum reg_class aclass;
2006
2007 if (flag_ira_region != IRA_REGION_ALL
2008 && flag_ira_region != IRA_REGION_MIXED)
2009 return;
2010 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2011 for (a = ira_regno_allocno_map[i];
2012 a != NULL;
2013 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2014 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
2015 && (parent_a = parent->regno_allocno_map[i]) != NULL
2016 /* There are no caps yet at this point. So use
2017 border_allocnos to find allocnos for the propagation. */
2018 && bitmap_bit_p (ALLOCNO_LOOP_TREE_NODE (a)->border_allocnos,
2019 ALLOCNO_NUM (a)))
2020 {
2021 if (! ALLOCNO_BAD_SPILL_P (a))
2022 ALLOCNO_BAD_SPILL_P (parent_a) = false;
2023 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
2024 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
2025 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2026 merge_hard_reg_conflicts (a, parent_a, true);
2027 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2028 += ALLOCNO_CALLS_CROSSED_NUM (a);
2029 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2030 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2031 ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
2032 |= ALLOCNO_CROSSED_CALLS_ABIS (a);
2033 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
2034 |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
2035 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2036 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2037 aclass = ALLOCNO_CLASS (a);
2038 ira_assert (aclass == ALLOCNO_CLASS (parent_a));
2039 ira_allocate_and_accumulate_costs
2040 (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
2041 ALLOCNO_HARD_REG_COSTS (a));
2042 ira_allocate_and_accumulate_costs
2043 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
2044 aclass,
2045 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
2046 ALLOCNO_CLASS_COST (parent_a)
2047 += ALLOCNO_CLASS_COST (a);
2048 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
2049 }
2050 }
2051
2052 /* Create allocnos corresponding to pseudo-registers in the current
2053 function. Traverse the loop tree for this. */
2054 static void
create_allocnos(void)2055 create_allocnos (void)
2056 {
2057 /* We need to process BB first to correctly link allocnos by member
2058 next_regno_allocno. */
2059 ira_traverse_loop_tree (true, ira_loop_tree_root,
2060 create_loop_tree_node_allocnos, NULL);
2061 if (optimize)
2062 ira_traverse_loop_tree (false, ira_loop_tree_root, NULL,
2063 propagate_modified_regnos);
2064 }
2065
2066
2067
2068 /* The page contains function to remove some regions from a separate
2069 register allocation. We remove regions whose separate allocation
2070 will hardly improve the result. As a result we speed up regional
2071 register allocation. */
2072
2073 /* The function changes the object in range list given by R to OBJ. */
2074 static void
change_object_in_range_list(live_range_t r,ira_object_t obj)2075 change_object_in_range_list (live_range_t r, ira_object_t obj)
2076 {
2077 for (; r != NULL; r = r->next)
2078 r->object = obj;
2079 }
2080
2081 /* Move all live ranges associated with allocno FROM to allocno TO. */
2082 static void
move_allocno_live_ranges(ira_allocno_t from,ira_allocno_t to)2083 move_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2084 {
2085 int i;
2086 int n = ALLOCNO_NUM_OBJECTS (from);
2087
2088 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2089
2090 for (i = 0; i < n; i++)
2091 {
2092 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2093 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2094 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2095
2096 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2097 {
2098 fprintf (ira_dump_file,
2099 " Moving ranges of a%dr%d to a%dr%d: ",
2100 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2101 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2102 ira_print_live_range_list (ira_dump_file, lr);
2103 }
2104 change_object_in_range_list (lr, to_obj);
2105 OBJECT_LIVE_RANGES (to_obj)
2106 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2107 OBJECT_LIVE_RANGES (from_obj) = NULL;
2108 }
2109 }
2110
2111 static void
copy_allocno_live_ranges(ira_allocno_t from,ira_allocno_t to)2112 copy_allocno_live_ranges (ira_allocno_t from, ira_allocno_t to)
2113 {
2114 int i;
2115 int n = ALLOCNO_NUM_OBJECTS (from);
2116
2117 gcc_assert (n == ALLOCNO_NUM_OBJECTS (to));
2118
2119 for (i = 0; i < n; i++)
2120 {
2121 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
2122 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
2123 live_range_t lr = OBJECT_LIVE_RANGES (from_obj);
2124
2125 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2126 {
2127 fprintf (ira_dump_file, " Copying ranges of a%dr%d to a%dr%d: ",
2128 ALLOCNO_NUM (from), ALLOCNO_REGNO (from),
2129 ALLOCNO_NUM (to), ALLOCNO_REGNO (to));
2130 ira_print_live_range_list (ira_dump_file, lr);
2131 }
2132 lr = ira_copy_live_range_list (lr);
2133 change_object_in_range_list (lr, to_obj);
2134 OBJECT_LIVE_RANGES (to_obj)
2135 = ira_merge_live_ranges (lr, OBJECT_LIVE_RANGES (to_obj));
2136 }
2137 }
2138
2139 /* Return TRUE if NODE represents a loop with low register
2140 pressure. */
2141 static bool
low_pressure_loop_node_p(ira_loop_tree_node_t node)2142 low_pressure_loop_node_p (ira_loop_tree_node_t node)
2143 {
2144 int i;
2145 enum reg_class pclass;
2146
2147 if (node->bb != NULL)
2148 return false;
2149
2150 for (i = 0; i < ira_pressure_classes_num; i++)
2151 {
2152 pclass = ira_pressure_classes[i];
2153 if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
2154 && ira_class_hard_regs_num[pclass] > 1)
2155 return false;
2156 }
2157 return true;
2158 }
2159
2160 #ifdef STACK_REGS
2161 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2162 form a region from such loop if the target use stack register
2163 because reg-stack.c cannot deal with such edges. */
2164 static bool
loop_with_complex_edge_p(class loop * loop)2165 loop_with_complex_edge_p (class loop *loop)
2166 {
2167 int i;
2168 edge_iterator ei;
2169 edge e;
2170 vec<edge> edges;
2171 bool res;
2172
2173 FOR_EACH_EDGE (e, ei, loop->header->preds)
2174 if (e->flags & EDGE_EH)
2175 return true;
2176 edges = get_loop_exit_edges (loop);
2177 res = false;
2178 FOR_EACH_VEC_ELT (edges, i, e)
2179 if (e->flags & EDGE_COMPLEX)
2180 {
2181 res = true;
2182 break;
2183 }
2184 edges.release ();
2185 return res;
2186 }
2187 #endif
2188
2189 /* Sort loops for marking them for removal. We put already marked
2190 loops first, then less frequent loops next, and then outer loops
2191 next. */
2192 static int
loop_compare_func(const void * v1p,const void * v2p)2193 loop_compare_func (const void *v1p, const void *v2p)
2194 {
2195 int diff;
2196 ira_loop_tree_node_t l1 = *(const ira_loop_tree_node_t *) v1p;
2197 ira_loop_tree_node_t l2 = *(const ira_loop_tree_node_t *) v2p;
2198
2199 ira_assert (l1->parent != NULL && l2->parent != NULL);
2200 if (l1->to_remove_p && ! l2->to_remove_p)
2201 return -1;
2202 if (! l1->to_remove_p && l2->to_remove_p)
2203 return 1;
2204 if ((diff = l1->loop->header->count.to_frequency (cfun)
2205 - l2->loop->header->count.to_frequency (cfun)) != 0)
2206 return diff;
2207 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
2208 return diff;
2209 /* Make sorting stable. */
2210 return l1->loop_num - l2->loop_num;
2211 }
2212
2213 /* Mark loops which should be removed from regional allocation. We
2214 remove a loop with low register pressure inside another loop with
2215 register pressure. In this case a separate allocation of the loop
2216 hardly helps (for irregular register file architecture it could
2217 help by choosing a better hard register in the loop but we prefer
2218 faster allocation even in this case). We also remove cheap loops
2219 if there are more than param_ira_max_loops_num of them. Loop with EH
2220 exit or enter edges are removed too because the allocation might
2221 require put pseudo moves on the EH edges (we could still do this
2222 for pseudos with caller saved hard registers in some cases but it
2223 is impossible to say here or during top-down allocation pass what
2224 hard register the pseudos get finally). */
2225 static void
mark_loops_for_removal(void)2226 mark_loops_for_removal (void)
2227 {
2228 int i, n;
2229 ira_loop_tree_node_t *sorted_loops;
2230 loop_p loop;
2231
2232 ira_assert (current_loops != NULL);
2233 sorted_loops
2234 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
2235 * number_of_loops (cfun));
2236 for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
2237 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2238 {
2239 if (ira_loop_nodes[i].parent == NULL)
2240 {
2241 /* Don't remove the root. */
2242 ira_loop_nodes[i].to_remove_p = false;
2243 continue;
2244 }
2245 sorted_loops[n++] = &ira_loop_nodes[i];
2246 ira_loop_nodes[i].to_remove_p
2247 = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
2248 && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2249 #ifdef STACK_REGS
2250 || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2251 #endif
2252 );
2253 }
2254 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
2255 for (i = 0; i < n - param_ira_max_loops_num; i++)
2256 {
2257 sorted_loops[i]->to_remove_p = true;
2258 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2259 fprintf
2260 (ira_dump_file,
2261 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
2262 sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
2263 sorted_loops[i]->loop->header->count.to_frequency (cfun),
2264 loop_depth (sorted_loops[i]->loop),
2265 low_pressure_loop_node_p (sorted_loops[i]->parent)
2266 && low_pressure_loop_node_p (sorted_loops[i])
2267 ? "low pressure" : "cheap loop");
2268 }
2269 ira_free (sorted_loops);
2270 }
2271
2272 /* Mark all loops but root for removing. */
2273 static void
mark_all_loops_for_removal(void)2274 mark_all_loops_for_removal (void)
2275 {
2276 int i;
2277 loop_p loop;
2278
2279 ira_assert (current_loops != NULL);
2280 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
2281 if (ira_loop_nodes[i].regno_allocno_map != NULL)
2282 {
2283 if (ira_loop_nodes[i].parent == NULL)
2284 {
2285 /* Don't remove the root. */
2286 ira_loop_nodes[i].to_remove_p = false;
2287 continue;
2288 }
2289 ira_loop_nodes[i].to_remove_p = true;
2290 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2291 fprintf
2292 (ira_dump_file,
2293 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
2294 ira_loop_nodes[i].loop_num,
2295 ira_loop_nodes[i].loop->header->index,
2296 ira_loop_nodes[i].loop->header->count.to_frequency (cfun),
2297 loop_depth (ira_loop_nodes[i].loop));
2298 }
2299 }
2300
2301 /* Definition of vector of loop tree nodes. */
2302
2303 /* Vec containing references to all removed loop tree nodes. */
2304 static vec<ira_loop_tree_node_t> removed_loop_vec;
2305
2306 /* Vec containing references to all children of loop tree nodes. */
2307 static vec<ira_loop_tree_node_t> children_vec;
2308
2309 /* Remove subregions of NODE if their separate allocation will not
2310 improve the result. */
2311 static void
remove_uneccesary_loop_nodes_from_loop_tree(ira_loop_tree_node_t node)2312 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
2313 {
2314 unsigned int start;
2315 bool remove_p;
2316 ira_loop_tree_node_t subnode;
2317
2318 remove_p = node->to_remove_p;
2319 if (! remove_p)
2320 children_vec.safe_push (node);
2321 start = children_vec.length ();
2322 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
2323 if (subnode->bb == NULL)
2324 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
2325 else
2326 children_vec.safe_push (subnode);
2327 node->children = node->subloops = NULL;
2328 if (remove_p)
2329 {
2330 removed_loop_vec.safe_push (node);
2331 return;
2332 }
2333 while (children_vec.length () > start)
2334 {
2335 subnode = children_vec.pop ();
2336 subnode->parent = node;
2337 subnode->next = node->children;
2338 node->children = subnode;
2339 if (subnode->bb == NULL)
2340 {
2341 subnode->subloop_next = node->subloops;
2342 node->subloops = subnode;
2343 }
2344 }
2345 }
2346
2347 /* Return TRUE if NODE is inside PARENT. */
2348 static bool
loop_is_inside_p(ira_loop_tree_node_t node,ira_loop_tree_node_t parent)2349 loop_is_inside_p (ira_loop_tree_node_t node, ira_loop_tree_node_t parent)
2350 {
2351 for (node = node->parent; node != NULL; node = node->parent)
2352 if (node == parent)
2353 return true;
2354 return false;
2355 }
2356
2357 /* Sort allocnos according to their order in regno allocno list. */
2358 static int
regno_allocno_order_compare_func(const void * v1p,const void * v2p)2359 regno_allocno_order_compare_func (const void *v1p, const void *v2p)
2360 {
2361 ira_allocno_t a1 = *(const ira_allocno_t *) v1p;
2362 ira_allocno_t a2 = *(const ira_allocno_t *) v2p;
2363 ira_loop_tree_node_t n1 = ALLOCNO_LOOP_TREE_NODE (a1);
2364 ira_loop_tree_node_t n2 = ALLOCNO_LOOP_TREE_NODE (a2);
2365
2366 if (loop_is_inside_p (n1, n2))
2367 return -1;
2368 else if (loop_is_inside_p (n2, n1))
2369 return 1;
2370 /* If allocnos are equally good, sort by allocno numbers, so that
2371 the results of qsort leave nothing to chance. We put allocnos
2372 with higher number first in the list because it is the original
2373 order for allocnos from loops on the same levels. */
2374 return ALLOCNO_NUM (a2) - ALLOCNO_NUM (a1);
2375 }
2376
2377 /* This array is used to sort allocnos to restore allocno order in
2378 the regno allocno list. */
2379 static ira_allocno_t *regno_allocnos;
2380
2381 /* Restore allocno order for REGNO in the regno allocno list. */
2382 static void
ira_rebuild_regno_allocno_list(int regno)2383 ira_rebuild_regno_allocno_list (int regno)
2384 {
2385 int i, n;
2386 ira_allocno_t a;
2387
2388 for (n = 0, a = ira_regno_allocno_map[regno];
2389 a != NULL;
2390 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2391 regno_allocnos[n++] = a;
2392 ira_assert (n > 0);
2393 qsort (regno_allocnos, n, sizeof (ira_allocno_t),
2394 regno_allocno_order_compare_func);
2395 for (i = 1; i < n; i++)
2396 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[i - 1]) = regno_allocnos[i];
2397 ALLOCNO_NEXT_REGNO_ALLOCNO (regno_allocnos[n - 1]) = NULL;
2398 ira_regno_allocno_map[regno] = regno_allocnos[0];
2399 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
2400 fprintf (ira_dump_file, " Rebuilding regno allocno list for %d\n", regno);
2401 }
2402
2403 /* Propagate info from allocno FROM_A to allocno A. */
2404 static void
propagate_some_info_from_allocno(ira_allocno_t a,ira_allocno_t from_a)2405 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2406 {
2407 enum reg_class aclass;
2408
2409 merge_hard_reg_conflicts (from_a, a, false);
2410 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2411 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2412 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2413 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2414 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2415 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2416 ALLOCNO_CROSSED_CALLS_ABIS (a) |= ALLOCNO_CROSSED_CALLS_ABIS (from_a);
2417 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a)
2418 |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a);
2419
2420 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2421 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2422 if (! ALLOCNO_BAD_SPILL_P (from_a))
2423 ALLOCNO_BAD_SPILL_P (a) = false;
2424 aclass = ALLOCNO_CLASS (from_a);
2425 ira_assert (aclass == ALLOCNO_CLASS (a));
2426 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2427 ALLOCNO_HARD_REG_COSTS (from_a));
2428 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2429 aclass,
2430 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2431 ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2432 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2433 }
2434
2435 /* Remove allocnos from loops removed from the allocation
2436 consideration. */
2437 static void
remove_unnecessary_allocnos(void)2438 remove_unnecessary_allocnos (void)
2439 {
2440 int regno;
2441 bool merged_p, rebuild_p;
2442 ira_allocno_t a, prev_a, next_a, parent_a;
2443 ira_loop_tree_node_t a_node, parent;
2444
2445 merged_p = false;
2446 regno_allocnos = NULL;
2447 for (regno = max_reg_num () - 1; regno >= FIRST_PSEUDO_REGISTER; regno--)
2448 {
2449 rebuild_p = false;
2450 for (prev_a = NULL, a = ira_regno_allocno_map[regno];
2451 a != NULL;
2452 a = next_a)
2453 {
2454 next_a = ALLOCNO_NEXT_REGNO_ALLOCNO (a);
2455 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2456 if (! a_node->to_remove_p)
2457 prev_a = a;
2458 else
2459 {
2460 for (parent = a_node->parent;
2461 (parent_a = parent->regno_allocno_map[regno]) == NULL
2462 && parent->to_remove_p;
2463 parent = parent->parent)
2464 ;
2465 if (parent_a == NULL)
2466 {
2467 /* There are no allocnos with the same regno in
2468 upper region -- just move the allocno to the
2469 upper region. */
2470 prev_a = a;
2471 ALLOCNO_LOOP_TREE_NODE (a) = parent;
2472 parent->regno_allocno_map[regno] = a;
2473 bitmap_set_bit (parent->all_allocnos, ALLOCNO_NUM (a));
2474 rebuild_p = true;
2475 }
2476 else
2477 {
2478 /* Remove the allocno and update info of allocno in
2479 the upper region. */
2480 if (prev_a == NULL)
2481 ira_regno_allocno_map[regno] = next_a;
2482 else
2483 ALLOCNO_NEXT_REGNO_ALLOCNO (prev_a) = next_a;
2484 move_allocno_live_ranges (a, parent_a);
2485 merged_p = true;
2486 propagate_some_info_from_allocno (parent_a, a);
2487 /* Remove it from the corresponding regno allocno
2488 map to avoid info propagation of subsequent
2489 allocno into this already removed allocno. */
2490 a_node->regno_allocno_map[regno] = NULL;
2491 ira_remove_allocno_prefs (a);
2492 finish_allocno (a);
2493 }
2494 }
2495 }
2496 if (rebuild_p)
2497 /* We need to restore the order in regno allocno list. */
2498 {
2499 if (regno_allocnos == NULL)
2500 regno_allocnos
2501 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
2502 * ira_allocnos_num);
2503 ira_rebuild_regno_allocno_list (regno);
2504 }
2505 }
2506 if (merged_p)
2507 ira_rebuild_start_finish_chains ();
2508 if (regno_allocnos != NULL)
2509 ira_free (regno_allocnos);
2510 }
2511
2512 /* Remove allocnos from all loops but the root. */
2513 static void
remove_low_level_allocnos(void)2514 remove_low_level_allocnos (void)
2515 {
2516 int regno;
2517 bool merged_p, propagate_p;
2518 ira_allocno_t a, top_a;
2519 ira_loop_tree_node_t a_node, parent;
2520 ira_allocno_iterator ai;
2521
2522 merged_p = false;
2523 FOR_EACH_ALLOCNO (a, ai)
2524 {
2525 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2526 if (a_node == ira_loop_tree_root || ALLOCNO_CAP_MEMBER (a) != NULL)
2527 continue;
2528 regno = ALLOCNO_REGNO (a);
2529 if ((top_a = ira_loop_tree_root->regno_allocno_map[regno]) == NULL)
2530 {
2531 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2532 ira_loop_tree_root->regno_allocno_map[regno] = a;
2533 continue;
2534 }
2535 propagate_p = a_node->parent->regno_allocno_map[regno] == NULL;
2536 /* Remove the allocno and update info of allocno in the upper
2537 region. */
2538 move_allocno_live_ranges (a, top_a);
2539 merged_p = true;
2540 if (propagate_p)
2541 propagate_some_info_from_allocno (top_a, a);
2542 }
2543 FOR_EACH_ALLOCNO (a, ai)
2544 {
2545 a_node = ALLOCNO_LOOP_TREE_NODE (a);
2546 if (a_node == ira_loop_tree_root)
2547 continue;
2548 parent = a_node->parent;
2549 regno = ALLOCNO_REGNO (a);
2550 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2551 ira_assert (ALLOCNO_CAP (a) != NULL);
2552 else if (ALLOCNO_CAP (a) == NULL)
2553 ira_assert (parent->regno_allocno_map[regno] != NULL);
2554 }
2555 FOR_EACH_ALLOCNO (a, ai)
2556 {
2557 regno = ALLOCNO_REGNO (a);
2558 if (ira_loop_tree_root->regno_allocno_map[regno] == a)
2559 {
2560 ira_object_t obj;
2561 ira_allocno_object_iterator oi;
2562
2563 ira_regno_allocno_map[regno] = a;
2564 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = NULL;
2565 ALLOCNO_CAP_MEMBER (a) = NULL;
2566 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2567 OBJECT_CONFLICT_HARD_REGS (obj)
2568 = OBJECT_TOTAL_CONFLICT_HARD_REGS (obj);
2569 #ifdef STACK_REGS
2570 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2571 ALLOCNO_NO_STACK_REG_P (a) = true;
2572 #endif
2573 }
2574 else
2575 {
2576 ira_remove_allocno_prefs (a);
2577 finish_allocno (a);
2578 }
2579 }
2580 if (merged_p)
2581 ira_rebuild_start_finish_chains ();
2582 }
2583
2584 /* Remove loops from consideration. We remove all loops except for
2585 root if ALL_P or loops for which a separate allocation will not
2586 improve the result. We have to do this after allocno creation and
2587 their costs and allocno class evaluation because only after that
2588 the register pressure can be known and is calculated. */
2589 static void
remove_unnecessary_regions(bool all_p)2590 remove_unnecessary_regions (bool all_p)
2591 {
2592 if (current_loops == NULL)
2593 return;
2594 if (all_p)
2595 mark_all_loops_for_removal ();
2596 else
2597 mark_loops_for_removal ();
2598 children_vec.create (last_basic_block_for_fn (cfun)
2599 + number_of_loops (cfun));
2600 removed_loop_vec.create (last_basic_block_for_fn (cfun)
2601 + number_of_loops (cfun));
2602 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2603 children_vec.release ();
2604 if (all_p)
2605 remove_low_level_allocnos ();
2606 else
2607 remove_unnecessary_allocnos ();
2608 while (removed_loop_vec.length () > 0)
2609 finish_loop_tree_node (removed_loop_vec.pop ());
2610 removed_loop_vec.release ();
2611 }
2612
2613
2614
2615 /* At this point true value of allocno attribute bad_spill_p means
2616 that there is an insn where allocno occurs and where the allocno
2617 cannot be used as memory. The function updates the attribute, now
2618 it can be true only for allocnos which cannot be used as memory in
2619 an insn and in whose live ranges there is other allocno deaths.
2620 Spilling allocnos with true value will not improve the code because
2621 it will not make other allocnos colorable and additional reloads
2622 for the corresponding pseudo will be generated in reload pass for
2623 each insn it occurs.
2624
2625 This is a trick mentioned in one classic article of Chaitin etc
2626 which is frequently omitted in other implementations of RA based on
2627 graph coloring. */
2628 static void
update_bad_spill_attribute(void)2629 update_bad_spill_attribute (void)
2630 {
2631 int i;
2632 ira_allocno_t a;
2633 ira_allocno_iterator ai;
2634 ira_allocno_object_iterator aoi;
2635 ira_object_t obj;
2636 live_range_t r;
2637 enum reg_class aclass;
2638 bitmap_head dead_points[N_REG_CLASSES];
2639
2640 for (i = 0; i < ira_allocno_classes_num; i++)
2641 {
2642 aclass = ira_allocno_classes[i];
2643 bitmap_initialize (&dead_points[aclass], ®_obstack);
2644 }
2645 FOR_EACH_ALLOCNO (a, ai)
2646 {
2647 aclass = ALLOCNO_CLASS (a);
2648 if (aclass == NO_REGS)
2649 continue;
2650 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2651 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2652 bitmap_set_bit (&dead_points[aclass], r->finish);
2653 }
2654 FOR_EACH_ALLOCNO (a, ai)
2655 {
2656 aclass = ALLOCNO_CLASS (a);
2657 if (aclass == NO_REGS)
2658 continue;
2659 if (! ALLOCNO_BAD_SPILL_P (a))
2660 continue;
2661 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2662 {
2663 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2664 {
2665 for (i = r->start + 1; i < r->finish; i++)
2666 if (bitmap_bit_p (&dead_points[aclass], i))
2667 break;
2668 if (i < r->finish)
2669 break;
2670 }
2671 if (r != NULL)
2672 {
2673 ALLOCNO_BAD_SPILL_P (a) = false;
2674 break;
2675 }
2676 }
2677 }
2678 for (i = 0; i < ira_allocno_classes_num; i++)
2679 {
2680 aclass = ira_allocno_classes[i];
2681 bitmap_clear (&dead_points[aclass]);
2682 }
2683 }
2684
2685
2686
2687 /* Set up minimal and maximal live range points for allocnos. */
2688 static void
setup_min_max_allocno_live_range_point(void)2689 setup_min_max_allocno_live_range_point (void)
2690 {
2691 int i;
2692 ira_allocno_t a, parent_a, cap;
2693 ira_allocno_iterator ai;
2694 #ifdef ENABLE_IRA_CHECKING
2695 ira_object_iterator oi;
2696 ira_object_t obj;
2697 #endif
2698 live_range_t r;
2699 ira_loop_tree_node_t parent;
2700
2701 FOR_EACH_ALLOCNO (a, ai)
2702 {
2703 int n = ALLOCNO_NUM_OBJECTS (a);
2704
2705 for (i = 0; i < n; i++)
2706 {
2707 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2708 r = OBJECT_LIVE_RANGES (obj);
2709 if (r == NULL)
2710 continue;
2711 OBJECT_MAX (obj) = r->finish;
2712 for (; r->next != NULL; r = r->next)
2713 ;
2714 OBJECT_MIN (obj) = r->start;
2715 }
2716 }
2717 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
2718 for (a = ira_regno_allocno_map[i];
2719 a != NULL;
2720 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2721 {
2722 int j;
2723 int n = ALLOCNO_NUM_OBJECTS (a);
2724
2725 for (j = 0; j < n; j++)
2726 {
2727 ira_object_t obj = ALLOCNO_OBJECT (a, j);
2728 ira_object_t parent_obj;
2729
2730 if (OBJECT_MAX (obj) < 0)
2731 {
2732 /* The object is not used and hence does not live. */
2733 ira_assert (OBJECT_LIVE_RANGES (obj) == NULL);
2734 OBJECT_MAX (obj) = 0;
2735 OBJECT_MIN (obj) = 1;
2736 continue;
2737 }
2738 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2739 /* Accumulation of range info. */
2740 if (ALLOCNO_CAP (a) != NULL)
2741 {
2742 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2743 {
2744 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2745 if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2746 OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2747 if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2748 OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2749 }
2750 continue;
2751 }
2752 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2753 continue;
2754 parent_a = parent->regno_allocno_map[i];
2755 parent_obj = ALLOCNO_OBJECT (parent_a, j);
2756 if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2757 OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2758 if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2759 OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2760 }
2761 }
2762 #ifdef ENABLE_IRA_CHECKING
2763 FOR_EACH_OBJECT (obj, oi)
2764 {
2765 if ((OBJECT_MIN (obj) >= 0 && OBJECT_MIN (obj) <= ira_max_point)
2766 && (OBJECT_MAX (obj) >= 0 && OBJECT_MAX (obj) <= ira_max_point))
2767 continue;
2768 gcc_unreachable ();
2769 }
2770 #endif
2771 }
2772
2773 /* Sort allocnos according to their live ranges. Allocnos with
2774 smaller allocno class are put first unless we use priority
2775 coloring. Allocnos with the same class are ordered according
2776 their start (min). Allocnos with the same start are ordered
2777 according their finish (max). */
2778 static int
object_range_compare_func(const void * v1p,const void * v2p)2779 object_range_compare_func (const void *v1p, const void *v2p)
2780 {
2781 int diff;
2782 ira_object_t obj1 = *(const ira_object_t *) v1p;
2783 ira_object_t obj2 = *(const ira_object_t *) v2p;
2784 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2785 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2786
2787 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2788 return diff;
2789 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2790 return diff;
2791 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2792 }
2793
2794 /* Sort ira_object_id_map and set up conflict id of allocnos. */
2795 static void
sort_conflict_id_map(void)2796 sort_conflict_id_map (void)
2797 {
2798 int i, num;
2799 ira_allocno_t a;
2800 ira_allocno_iterator ai;
2801
2802 num = 0;
2803 FOR_EACH_ALLOCNO (a, ai)
2804 {
2805 ira_allocno_object_iterator oi;
2806 ira_object_t obj;
2807
2808 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2809 ira_object_id_map[num++] = obj;
2810 }
2811 if (num > 1)
2812 qsort (ira_object_id_map, num, sizeof (ira_object_t),
2813 object_range_compare_func);
2814 for (i = 0; i < num; i++)
2815 {
2816 ira_object_t obj = ira_object_id_map[i];
2817
2818 gcc_assert (obj != NULL);
2819 OBJECT_CONFLICT_ID (obj) = i;
2820 }
2821 for (i = num; i < ira_objects_num; i++)
2822 ira_object_id_map[i] = NULL;
2823 }
2824
2825 /* Set up minimal and maximal conflict ids of allocnos with which
2826 given allocno can conflict. */
2827 static void
setup_min_max_conflict_allocno_ids(void)2828 setup_min_max_conflict_allocno_ids (void)
2829 {
2830 int aclass;
2831 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2832 int *live_range_min, *last_lived;
2833 int word0_min, word0_max;
2834 ira_allocno_t a;
2835 ira_allocno_iterator ai;
2836
2837 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2838 aclass = -1;
2839 first_not_finished = -1;
2840 for (i = 0; i < ira_objects_num; i++)
2841 {
2842 ira_object_t obj = ira_object_id_map[i];
2843
2844 if (obj == NULL)
2845 continue;
2846
2847 a = OBJECT_ALLOCNO (obj);
2848
2849 if (aclass < 0)
2850 {
2851 aclass = ALLOCNO_CLASS (a);
2852 min = i;
2853 first_not_finished = i;
2854 }
2855 else
2856 {
2857 start = OBJECT_MIN (obj);
2858 /* If we skip an allocno, the allocno with smaller ids will
2859 be also skipped because of the secondary sorting the
2860 range finishes (see function
2861 object_range_compare_func). */
2862 while (first_not_finished < i
2863 && start > OBJECT_MAX (ira_object_id_map
2864 [first_not_finished]))
2865 first_not_finished++;
2866 min = first_not_finished;
2867 }
2868 if (min == i)
2869 /* We could increase min further in this case but it is good
2870 enough. */
2871 min++;
2872 live_range_min[i] = OBJECT_MIN (obj);
2873 OBJECT_MIN (obj) = min;
2874 }
2875 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2876 aclass = -1;
2877 filled_area_start = -1;
2878 for (i = ira_objects_num - 1; i >= 0; i--)
2879 {
2880 ira_object_t obj = ira_object_id_map[i];
2881
2882 if (obj == NULL)
2883 continue;
2884
2885 a = OBJECT_ALLOCNO (obj);
2886 if (aclass < 0)
2887 {
2888 aclass = ALLOCNO_CLASS (a);
2889 for (j = 0; j < ira_max_point; j++)
2890 last_lived[j] = -1;
2891 filled_area_start = ira_max_point;
2892 }
2893 min = live_range_min[i];
2894 finish = OBJECT_MAX (obj);
2895 max = last_lived[finish];
2896 if (max < 0)
2897 /* We could decrease max further in this case but it is good
2898 enough. */
2899 max = OBJECT_CONFLICT_ID (obj) - 1;
2900 OBJECT_MAX (obj) = max;
2901 /* In filling, we can go further A range finish to recognize
2902 intersection quickly because if the finish of subsequently
2903 processed allocno (it has smaller conflict id) range is
2904 further A range finish than they are definitely intersected
2905 (the reason for this is the allocnos with bigger conflict id
2906 have their range starts not smaller than allocnos with
2907 smaller ids. */
2908 for (j = min; j < filled_area_start; j++)
2909 last_lived[j] = i;
2910 filled_area_start = min;
2911 }
2912 ira_free (last_lived);
2913 ira_free (live_range_min);
2914
2915 /* For allocnos with more than one object, we may later record extra conflicts in
2916 subobject 0 that we cannot really know about here.
2917 For now, simply widen the min/max range of these subobjects. */
2918
2919 word0_min = INT_MAX;
2920 word0_max = INT_MIN;
2921
2922 FOR_EACH_ALLOCNO (a, ai)
2923 {
2924 int n = ALLOCNO_NUM_OBJECTS (a);
2925 ira_object_t obj0;
2926
2927 if (n < 2)
2928 continue;
2929 obj0 = ALLOCNO_OBJECT (a, 0);
2930 if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2931 word0_min = OBJECT_CONFLICT_ID (obj0);
2932 if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2933 word0_max = OBJECT_CONFLICT_ID (obj0);
2934 }
2935 FOR_EACH_ALLOCNO (a, ai)
2936 {
2937 int n = ALLOCNO_NUM_OBJECTS (a);
2938 ira_object_t obj0;
2939
2940 if (n < 2)
2941 continue;
2942 obj0 = ALLOCNO_OBJECT (a, 0);
2943 if (OBJECT_MIN (obj0) > word0_min)
2944 OBJECT_MIN (obj0) = word0_min;
2945 if (OBJECT_MAX (obj0) < word0_max)
2946 OBJECT_MAX (obj0) = word0_max;
2947 }
2948 }
2949
2950
2951
2952 static void
create_caps(void)2953 create_caps (void)
2954 {
2955 ira_allocno_t a;
2956 ira_allocno_iterator ai;
2957 ira_loop_tree_node_t loop_tree_node;
2958
2959 FOR_EACH_ALLOCNO (a, ai)
2960 {
2961 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2962 continue;
2963 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2964 create_cap_allocno (a);
2965 else if (ALLOCNO_CAP (a) == NULL)
2966 {
2967 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2968 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2969 create_cap_allocno (a);
2970 }
2971 }
2972 }
2973
2974
2975
2976 /* The page contains code transforming more one region internal
2977 representation (IR) to one region IR which is necessary for reload.
2978 This transformation is called IR flattening. We might just rebuild
2979 the IR for one region but we don't do it because it takes a lot of
2980 time. */
2981
2982 /* Map: regno -> allocnos which will finally represent the regno for
2983 IR with one region. */
2984 static ira_allocno_t *regno_top_level_allocno_map;
2985
2986 /* Find the allocno that corresponds to A at a level one higher up in the
2987 loop tree. Returns NULL if A is a cap, or if it has no parent. */
2988 ira_allocno_t
ira_parent_allocno(ira_allocno_t a)2989 ira_parent_allocno (ira_allocno_t a)
2990 {
2991 ira_loop_tree_node_t parent;
2992
2993 if (ALLOCNO_CAP (a) != NULL)
2994 return NULL;
2995
2996 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2997 if (parent == NULL)
2998 return NULL;
2999
3000 return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
3001 }
3002
3003 /* Find the allocno that corresponds to A at a level one higher up in the
3004 loop tree. If ALLOCNO_CAP is set for A, return that. */
3005 ira_allocno_t
ira_parent_or_cap_allocno(ira_allocno_t a)3006 ira_parent_or_cap_allocno (ira_allocno_t a)
3007 {
3008 if (ALLOCNO_CAP (a) != NULL)
3009 return ALLOCNO_CAP (a);
3010
3011 return ira_parent_allocno (a);
3012 }
3013
3014 /* Process all allocnos originated from pseudo REGNO and copy live
3015 ranges, hard reg conflicts, and allocno stack reg attributes from
3016 low level allocnos to final allocnos which are destinations of
3017 removed stores at a loop exit. Return true if we copied live
3018 ranges. */
3019 static bool
copy_info_to_removed_store_destinations(int regno)3020 copy_info_to_removed_store_destinations (int regno)
3021 {
3022 ira_allocno_t a;
3023 ira_allocno_t parent_a = NULL;
3024 ira_loop_tree_node_t parent;
3025 bool merged_p;
3026
3027 merged_p = false;
3028 for (a = ira_regno_allocno_map[regno];
3029 a != NULL;
3030 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3031 {
3032 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3033 /* This allocno will be removed. */
3034 continue;
3035
3036 /* Caps will be removed. */
3037 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3038 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3039 parent != NULL;
3040 parent = parent->parent)
3041 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3042 || (parent_a
3043 == regno_top_level_allocno_map[REGNO
3044 (allocno_emit_reg (parent_a))]
3045 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3046 break;
3047 if (parent == NULL || parent_a == NULL)
3048 continue;
3049
3050 copy_allocno_live_ranges (a, parent_a);
3051 merge_hard_reg_conflicts (a, parent_a, true);
3052
3053 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3054 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3055 += ALLOCNO_CALLS_CROSSED_NUM (a);
3056 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3057 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3058 ALLOCNO_CROSSED_CALLS_ABIS (parent_a)
3059 |= ALLOCNO_CROSSED_CALLS_ABIS (a);
3060 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a)
3061 |= ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a);
3062 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3063 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3064 merged_p = true;
3065 }
3066 return merged_p;
3067 }
3068
3069 /* Flatten the IR. In other words, this function transforms IR as if
3070 it were built with one region (without loops). We could make it
3071 much simpler by rebuilding IR with one region, but unfortunately it
3072 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3073 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3074 IRA_MAX_POINT before emitting insns on the loop borders. */
3075 void
ira_flattening(int max_regno_before_emit,int ira_max_point_before_emit)3076 ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3077 {
3078 int i, j;
3079 bool keep_p;
3080 int hard_regs_num;
3081 bool new_pseudos_p, merged_p, mem_dest_p;
3082 unsigned int n;
3083 enum reg_class aclass;
3084 ira_allocno_t a, parent_a, first, second, node_first, node_second;
3085 ira_copy_t cp;
3086 ira_loop_tree_node_t node;
3087 live_range_t r;
3088 ira_allocno_iterator ai;
3089 ira_copy_iterator ci;
3090
3091 regno_top_level_allocno_map
3092 = (ira_allocno_t *) ira_allocate (max_reg_num ()
3093 * sizeof (ira_allocno_t));
3094 memset (regno_top_level_allocno_map, 0,
3095 max_reg_num () * sizeof (ira_allocno_t));
3096 new_pseudos_p = merged_p = false;
3097 FOR_EACH_ALLOCNO (a, ai)
3098 {
3099 ira_allocno_object_iterator oi;
3100 ira_object_t obj;
3101
3102 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3103 /* Caps are not in the regno allocno maps and they are never
3104 will be transformed into allocnos existing after IR
3105 flattening. */
3106 continue;
3107 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3108 OBJECT_TOTAL_CONFLICT_HARD_REGS (obj)
3109 = OBJECT_CONFLICT_HARD_REGS (obj);
3110 #ifdef STACK_REGS
3111 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3112 #endif
3113 }
3114 /* Fix final allocno attributes. */
3115 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3116 {
3117 mem_dest_p = false;
3118 for (a = ira_regno_allocno_map[i];
3119 a != NULL;
3120 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3121 {
3122 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3123
3124 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3125 if (data->somewhere_renamed_p)
3126 new_pseudos_p = true;
3127 parent_a = ira_parent_allocno (a);
3128 if (parent_a == NULL)
3129 {
3130 ALLOCNO_COPIES (a) = NULL;
3131 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3132 continue;
3133 }
3134 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3135
3136 if (data->mem_optimized_dest != NULL)
3137 mem_dest_p = true;
3138 parent_data = ALLOCNO_EMIT_DATA (parent_a);
3139 if (REGNO (data->reg) == REGNO (parent_data->reg))
3140 {
3141 merge_hard_reg_conflicts (a, parent_a, true);
3142 move_allocno_live_ranges (a, parent_a);
3143 merged_p = true;
3144 parent_data->mem_optimized_dest_p
3145 = (parent_data->mem_optimized_dest_p
3146 || data->mem_optimized_dest_p);
3147 continue;
3148 }
3149 new_pseudos_p = true;
3150 for (;;)
3151 {
3152 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3153 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3154 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3155 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3156 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3157 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3158 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3159 /* Assume that ALLOCNO_CROSSED_CALLS_ABIS and
3160 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS stay the same.
3161 We'd need to rebuild the IR to do better. */
3162 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3163 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3164 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3165 && ALLOCNO_NREFS (parent_a) >= 0
3166 && ALLOCNO_FREQ (parent_a) >= 0);
3167 aclass = ALLOCNO_CLASS (parent_a);
3168 hard_regs_num = ira_class_hard_regs_num[aclass];
3169 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3170 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3171 for (j = 0; j < hard_regs_num; j++)
3172 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3173 -= ALLOCNO_HARD_REG_COSTS (a)[j];
3174 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3175 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3176 for (j = 0; j < hard_regs_num; j++)
3177 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3178 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3179 ALLOCNO_CLASS_COST (parent_a)
3180 -= ALLOCNO_CLASS_COST (a);
3181 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3182 parent_a = ira_parent_allocno (parent_a);
3183 if (parent_a == NULL)
3184 break;
3185 }
3186 ALLOCNO_COPIES (a) = NULL;
3187 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3188 }
3189 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3190 merged_p = true;
3191 }
3192 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3193 if (merged_p || ira_max_point_before_emit != ira_max_point)
3194 ira_rebuild_start_finish_chains ();
3195 if (new_pseudos_p)
3196 {
3197 sparseset objects_live;
3198
3199 /* Rebuild conflicts. */
3200 FOR_EACH_ALLOCNO (a, ai)
3201 {
3202 ira_allocno_object_iterator oi;
3203 ira_object_t obj;
3204
3205 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3206 || ALLOCNO_CAP_MEMBER (a) != NULL)
3207 continue;
3208 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3209 {
3210 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3211 ira_assert (r->object == obj);
3212 clear_conflicts (obj);
3213 }
3214 }
3215 objects_live = sparseset_alloc (ira_objects_num);
3216 for (i = 0; i < ira_max_point; i++)
3217 {
3218 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3219 {
3220 ira_object_t obj = r->object;
3221
3222 a = OBJECT_ALLOCNO (obj);
3223 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3224 || ALLOCNO_CAP_MEMBER (a) != NULL)
3225 continue;
3226
3227 aclass = ALLOCNO_CLASS (a);
3228 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3229 {
3230 ira_object_t live_obj = ira_object_id_map[n];
3231 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3232 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3233
3234 if (ira_reg_classes_intersect_p[aclass][live_aclass]
3235 /* Don't set up conflict for the allocno with itself. */
3236 && live_a != a)
3237 ira_add_conflict (obj, live_obj);
3238 }
3239 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3240 }
3241
3242 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3243 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3244 }
3245 sparseset_free (objects_live);
3246 compress_conflict_vecs ();
3247 }
3248 /* Mark some copies for removing and change allocnos in the rest
3249 copies. */
3250 FOR_EACH_COPY (cp, ci)
3251 {
3252 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3253 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3254 {
3255 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3256 fprintf
3257 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3258 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3259 ALLOCNO_NUM (cp->first),
3260 REGNO (allocno_emit_reg (cp->first)),
3261 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3262 ALLOCNO_NUM (cp->second),
3263 REGNO (allocno_emit_reg (cp->second)));
3264 cp->loop_tree_node = NULL;
3265 continue;
3266 }
3267 first
3268 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3269 second
3270 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3271 node = cp->loop_tree_node;
3272 if (node == NULL)
3273 keep_p = true; /* It copy generated in ira-emit.c. */
3274 else
3275 {
3276 /* Check that the copy was not propagated from level on
3277 which we will have different pseudos. */
3278 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3279 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3280 keep_p = ((REGNO (allocno_emit_reg (first))
3281 == REGNO (allocno_emit_reg (node_first)))
3282 && (REGNO (allocno_emit_reg (second))
3283 == REGNO (allocno_emit_reg (node_second))));
3284 }
3285 if (keep_p)
3286 {
3287 cp->loop_tree_node = ira_loop_tree_root;
3288 cp->first = first;
3289 cp->second = second;
3290 }
3291 else
3292 {
3293 cp->loop_tree_node = NULL;
3294 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3295 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
3296 cp->num, ALLOCNO_NUM (cp->first),
3297 REGNO (allocno_emit_reg (cp->first)),
3298 ALLOCNO_NUM (cp->second),
3299 REGNO (allocno_emit_reg (cp->second)));
3300 }
3301 }
3302 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3303 FOR_EACH_ALLOCNO (a, ai)
3304 {
3305 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3306 || ALLOCNO_CAP_MEMBER (a) != NULL)
3307 {
3308 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3309 fprintf (ira_dump_file, " Remove a%dr%d\n",
3310 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3311 ira_remove_allocno_prefs (a);
3312 finish_allocno (a);
3313 continue;
3314 }
3315 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3316 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3317 ALLOCNO_CAP (a) = NULL;
3318 /* Restore updated costs for assignments from reload. */
3319 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3320 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3321 if (! ALLOCNO_ASSIGNED_P (a))
3322 ira_free_allocno_updated_costs (a);
3323 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3324 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3325 }
3326 /* Remove unnecessary copies. */
3327 FOR_EACH_COPY (cp, ci)
3328 {
3329 if (cp->loop_tree_node == NULL)
3330 {
3331 ira_copies[cp->num] = NULL;
3332 finish_copy (cp);
3333 continue;
3334 }
3335 ira_assert
3336 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3337 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3338 add_allocno_copy_to_list (cp);
3339 swap_allocno_copy_ends_if_necessary (cp);
3340 }
3341 rebuild_regno_allocno_maps ();
3342 if (ira_max_point != ira_max_point_before_emit)
3343 ira_compress_allocno_live_ranges ();
3344 ira_free (regno_top_level_allocno_map);
3345 }
3346
3347
3348
3349 #ifdef ENABLE_IRA_CHECKING
3350 /* Check creation of all allocnos. Allocnos on lower levels should
3351 have allocnos or caps on all upper levels. */
3352 static void
check_allocno_creation(void)3353 check_allocno_creation (void)
3354 {
3355 ira_allocno_t a;
3356 ira_allocno_iterator ai;
3357 ira_loop_tree_node_t loop_tree_node;
3358
3359 FOR_EACH_ALLOCNO (a, ai)
3360 {
3361 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3362 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3363 ALLOCNO_NUM (a)));
3364 if (loop_tree_node == ira_loop_tree_root)
3365 continue;
3366 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3367 ira_assert (ALLOCNO_CAP (a) != NULL);
3368 else if (ALLOCNO_CAP (a) == NULL)
3369 ira_assert (loop_tree_node->parent
3370 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3371 && bitmap_bit_p (loop_tree_node->border_allocnos,
3372 ALLOCNO_NUM (a)));
3373 }
3374 }
3375 #endif
3376
3377 /* Identify allocnos which prefer a register class with a single hard register.
3378 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3379 less likely to use the preferred singleton register. */
3380 static void
update_conflict_hard_reg_costs(void)3381 update_conflict_hard_reg_costs (void)
3382 {
3383 ira_allocno_t a;
3384 ira_allocno_iterator ai;
3385 int i, index, min;
3386
3387 FOR_EACH_ALLOCNO (a, ai)
3388 {
3389 reg_class_t aclass = ALLOCNO_CLASS (a);
3390 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3391 int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3392 if (singleton < 0)
3393 continue;
3394 index = ira_class_hard_reg_index[(int) aclass][singleton];
3395 if (index < 0)
3396 continue;
3397 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3398 || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3399 continue;
3400 min = INT_MAX;
3401 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3402 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3403 && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3404 min = ALLOCNO_HARD_REG_COSTS (a)[i];
3405 if (min == INT_MAX)
3406 continue;
3407 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3408 aclass, 0);
3409 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3410 -= min - ALLOCNO_CLASS_COST (a);
3411 }
3412 }
3413
3414 /* Create a internal representation (IR) for IRA (allocnos, copies,
3415 loop tree nodes). The function returns TRUE if we generate loop
3416 structure (besides nodes representing all function and the basic
3417 blocks) for regional allocation. A true return means that we
3418 really need to flatten IR before the reload. */
3419 bool
ira_build(void)3420 ira_build (void)
3421 {
3422 bool loops_p;
3423
3424 df_analyze ();
3425 initiate_cost_vectors ();
3426 initiate_allocnos ();
3427 initiate_prefs ();
3428 initiate_copies ();
3429 create_loop_tree_nodes ();
3430 form_loop_tree ();
3431 create_allocnos ();
3432 ira_costs ();
3433 create_allocno_objects ();
3434 ira_create_allocno_live_ranges ();
3435 remove_unnecessary_regions (false);
3436 ira_compress_allocno_live_ranges ();
3437 update_bad_spill_attribute ();
3438 loops_p = more_one_region_p ();
3439 if (loops_p)
3440 {
3441 propagate_allocno_info ();
3442 create_caps ();
3443 }
3444 ira_tune_allocno_costs ();
3445 #ifdef ENABLE_IRA_CHECKING
3446 check_allocno_creation ();
3447 #endif
3448 setup_min_max_allocno_live_range_point ();
3449 sort_conflict_id_map ();
3450 setup_min_max_conflict_allocno_ids ();
3451 ira_build_conflicts ();
3452 update_conflict_hard_reg_costs ();
3453 if (! ira_conflicts_p)
3454 {
3455 ira_allocno_t a;
3456 ira_allocno_iterator ai;
3457
3458 /* Remove all regions but root one. */
3459 if (loops_p)
3460 {
3461 remove_unnecessary_regions (true);
3462 loops_p = false;
3463 }
3464 /* We don't save hard registers around calls for fast allocation
3465 -- add caller clobbered registers as conflicting ones to
3466 allocno crossing calls. */
3467 FOR_EACH_ALLOCNO (a, ai)
3468 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3469 ior_hard_reg_conflicts (a, ira_need_caller_save_regs (a));
3470 }
3471 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3472 print_copies (ira_dump_file);
3473 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3474 print_prefs (ira_dump_file);
3475 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3476 {
3477 int n, nr, nr_big;
3478 ira_allocno_t a;
3479 live_range_t r;
3480 ira_allocno_iterator ai;
3481
3482 n = 0;
3483 nr = 0;
3484 nr_big = 0;
3485 FOR_EACH_ALLOCNO (a, ai)
3486 {
3487 int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3488
3489 if (nobj > 1)
3490 nr_big++;
3491 for (j = 0; j < nobj; j++)
3492 {
3493 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3494 n += OBJECT_NUM_CONFLICTS (obj);
3495 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3496 nr++;
3497 }
3498 }
3499 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
3500 current_loops == NULL ? 1 : number_of_loops (cfun),
3501 n_basic_blocks_for_fn (cfun), ira_max_point);
3502 fprintf (ira_dump_file,
3503 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3504 ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3505 }
3506 return loops_p;
3507 }
3508
3509 /* Release the data created by function ira_build. */
3510 void
ira_destroy(void)3511 ira_destroy (void)
3512 {
3513 finish_loop_tree_nodes ();
3514 finish_prefs ();
3515 finish_copies ();
3516 finish_allocnos ();
3517 finish_cost_vectors ();
3518 ira_finish_allocno_live_ranges ();
3519 }
3520