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