1/* Building internal representation for IRA.
2 Copyright (C) 2006-2017 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along 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
38static 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. */
42ira_loop_tree_node_t ira_loop_tree_root;
43
44/* Height of the loop tree. */
45int 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. */
50ira_loop_tree_node_t ira_bb_nodes;
51
52/* All nodes representing loops are referred through the following
53 array. */
54ira_loop_tree_node_t ira_loop_nodes;
55
56/* And size of the ira_loop_nodes array. */
57unsigned int ira_loop_nodes_count;
58
59/* Map regno -> allocnos with given regno (see comments for
60 allocno member `next_regno_allocno'). */
61ira_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. */
66ira_allocno_t *ira_allocnos;
67
68/* Sizes of the previous array. */
69int ira_allocnos_num;
70
71/* Count of conflict record structures we've created, used when creating
72 a new conflict id. */
73int ira_objects_num;
74
75/* Map a conflict id to its conflict record. */
76ira_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. */
80ira_pref_t *ira_prefs;
81
82/* Size of the previous array. */
83int 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. */
88ira_copy_t *ira_copies;
89
90/* Size of the previous array. */
91int 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. */
98static 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. */
102static void
103init_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. */
125static void
126create_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. */
194static bool
195more_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. */
209static void
210finish_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. */
225static void
226finish_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. */
255static void
256add_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. */
306static int
307setup_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. */
330static void
331form_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. */
374static void
375rebuild_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. */
418static object_allocator<live_range> live_range_pool ("live ranges");
419static object_allocator<ira_allocno> allocno_pool ("allocnos");
420static object_allocator<ira_object> object_pool ("objects");
421
422/* Vec containing references to all created allocnos. It is a
423 container of array allocnos. */
424static 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. */
428static vec<ira_object_t> ira_object_id_map_vec;
429
430/* Initialize data concerning allocnos. */
431static void
432initiate_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. */
447static ira_object_t
448ira_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. */
480ira_allocno_t
481ira_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. */
543void
544ira_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. */
561void
562ira_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 (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
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. */
580static void
581create_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. */
593static void
594merge_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. */
620void
621ior_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. */
635bool
636ira_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. */
654void
655ira_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. */
672static void
673allocate_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. */
688void
689ira_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. */
698static void
699add_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. */
782static void
783ira_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. */
790static void
791clear_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. */
809static int *conflict_check;
810
811/* The value used to mark allocation presence in conflict vector of
812 the current allocno. */
813static int curr_conflict_check_tick;
814
815/* Remove duplications in conflict vector of OBJ. */
816static void
817compress_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. */
839static void
840compress_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. */
858void
859ira_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. */
878static ira_allocno_t
879create_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. */
922live_range_t
923ira_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. */
938void
939ira_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. */
948static live_range_t
949copy_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. */
960live_range_t
961ira_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. */
982live_range_t
983ira_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. */
1054bool
1055ira_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. */
1071void
1072ira_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. */
1078void
1079ira_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. */
1091void
1092ira_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. */
1108static void
1109ira_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. */
1141static void
1142finish_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. */
1149static void
1150finish_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. */
1168static 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. */
1172static vec<ira_pref_t> pref_vec;
1173
1174/* The function initializes data concerning allocno prefs. */
1175static void
1176initiate_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. */
1184static ira_pref_t
1185find_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. */
1196ira_pref_t
1197ira_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. */
1213static void
1214add_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. */
1224void
1225ira_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. */
1242static void
1243print_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. */
1251void
1252ira_debug_pref (ira_pref_t pref)
1253{
1254 print_pref (stderr, pref);
1255}
1256
1257/* Print info about all prefs into file F. */
1258static void
1259print_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. */
1269void
1270ira_debug_prefs (void)
1271{
1272 print_prefs (stderr);
1273}
1274
1275/* Print info about prefs involving allocno A into file F. */
1276static void
1277print_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. */
1288void
1289ira_debug_allocno_prefs (ira_allocno_t a)
1290{
1291 print_allocno_prefs (stderr, a);
1292}
1293
1294/* The function frees memory allocated for PREF. */
1295static void
1296finish_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. */
1304void
1305ira_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. */
1326void
1327ira_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. */
1340static void
1341finish_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. */
1355static 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. */
1359static vec<ira_copy_t> copy_vec;
1360
1361/* The function initializes data concerning allocno copies. */
1362static void
1363initiate_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. */
1372static ira_copy_t
1373find_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. */
1402ira_copy_t
1403ira_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. */
1424static void
1425add_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. */
1453static void
1454swap_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. */
1468ira_copy_t
1469ira_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. */
1489static void
1490print_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
1499DEBUG_FUNCTION void
1500debug (ira_allocno_copy &ref)
1501{
1502 print_copy (stderr, &ref);
1503}
1504
1505DEBUG_FUNCTION void
1506debug (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. */
1515void
1516ira_debug_copy (ira_copy_t cp)
1517{
1518 print_copy (stderr, cp);
1519}
1520
1521/* Print info about all copies into file F. */
1522static void
1523print_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. */
1533void
1534ira_debug_copies (void)
1535{
1536 print_copies (stderr);
1537}
1538
1539/* Print info about copies involving allocno A into file F. */
1540static void
1541print_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
1567DEBUG_FUNCTION void
1568debug (ira_allocno &ref)
1569{
1570 print_allocno_copies (stderr, &ref);
1571}
1572
1573DEBUG_FUNCTION void
1574debug (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. */
1584void
1585ira_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. */
1591static void
1592finish_copy (ira_copy_t cp)
1593{
1594 copy_pool.remove (cp);
1595}
1596
1597
1598/* Free memory allocated for all copies. */
1599static void
1600finish_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. */
1614static 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. */
1618static void
1619initiate_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. */
1633int *
1634ira_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. */
1640void
1641ira_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. */
1649static void
1650finish_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
1678static vec<ira_loop_tree_node_t>
1679ira_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. */
1751ira_loop_tree_node_t ira_curr_loop_tree_node;
1752ira_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
1769void
1770ira_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. */
1830static 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. */
1835static void
1836create_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. */
1906static void
1907create_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. */
1929static void
1930create_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. */
1960static void
1961create_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. */
1986static void
1987propagate_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. */
2002static void
2003propagate_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. */
2055static void
2056create_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. */
2075static void
2076change_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. */
2083static void
2084move_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
2112static void
2113copy_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. */
2142static bool
2143low_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. */
2165static bool
2166loop_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. */
2193static int
2194loop_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). */
2226static void
2227mark_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. */
2274static void
2275mark_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. */
2305static vec<ira_loop_tree_node_t> removed_loop_vec;
2306
2307/* Vec containing references to all children of loop tree nodes. */
2308static vec<ira_loop_tree_node_t> children_vec;
2309
2310/* Remove subregions of NODE if their separate allocation will not
2311 improve the result. */
2312static void
2313remove_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. */
2349static bool
2350loop_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. */
2359static int
2360regno_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. */
2380static ira_allocno_t *regno_allocnos;
2381
2382/* Restore allocno order for REGNO in the regno allocno list. */
2383static void
2384ira_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. */
2405static void
2406propagate_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. */
2437static void
2438remove_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. */
2513static void
2514remove_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. */
2589static void
2590remove_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. */
2628static void
2629update_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], &reg_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. */
2688static void
2689setup_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 continue;
2732 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2733 /* Accumulation of range info. */
2734 if (ALLOCNO_CAP (a) != NULL)
2735 {
2736 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
2737 {
2738 ira_object_t cap_obj = ALLOCNO_OBJECT (cap, j);
2739 if (OBJECT_MAX (cap_obj) < OBJECT_MAX (obj))
2740 OBJECT_MAX (cap_obj) = OBJECT_MAX (obj);
2741 if (OBJECT_MIN (cap_obj) > OBJECT_MIN (obj))
2742 OBJECT_MIN (cap_obj) = OBJECT_MIN (obj);
2743 }
2744 continue;
2745 }
2746 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL)
2747 continue;
2748 parent_a = parent->regno_allocno_map[i];
2749 parent_obj = ALLOCNO_OBJECT (parent_a, j);
2750 if (OBJECT_MAX (parent_obj) < OBJECT_MAX (obj))
2751 OBJECT_MAX (parent_obj) = OBJECT_MAX (obj);
2752 if (OBJECT_MIN (parent_obj) > OBJECT_MIN (obj))
2753 OBJECT_MIN (parent_obj) = OBJECT_MIN (obj);
2754 }
2755 }
2756#ifdef ENABLE_IRA_CHECKING
2757 FOR_EACH_OBJECT (obj, oi)
2758 {
2759 if ((0 <= OBJECT_MIN (obj) && OBJECT_MIN (obj) <= ira_max_point)
2760 && (0 <= OBJECT_MAX (obj) && OBJECT_MAX (obj) <= ira_max_point))
2761 continue;
2762 gcc_unreachable ();
2763 }
2764#endif
2765}
2766
2767/* Sort allocnos according to their live ranges. Allocnos with
2768 smaller allocno class are put first unless we use priority
2769 coloring. Allocnos with the same class are ordered according
2770 their start (min). Allocnos with the same start are ordered
2771 according their finish (max). */
2772static int
2773object_range_compare_func (const void *v1p, const void *v2p)
2774{
2775 int diff;
2776 ira_object_t obj1 = *(const ira_object_t *) v1p;
2777 ira_object_t obj2 = *(const ira_object_t *) v2p;
2778 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2779 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2780
2781 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2782 return diff;
2783 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2784 return diff;
2785 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2786}
2787
2788/* Sort ira_object_id_map and set up conflict id of allocnos. */
2789static void
2790sort_conflict_id_map (void)
2791{
2792 int i, num;
2793 ira_allocno_t a;
2794 ira_allocno_iterator ai;
2795
2796 num = 0;
2797 FOR_EACH_ALLOCNO (a, ai)
2798 {
2799 ira_allocno_object_iterator oi;
2800 ira_object_t obj;
2801
2802 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2803 ira_object_id_map[num++] = obj;
2804 }
2805 if (num > 1)
2806 qsort (ira_object_id_map, num, sizeof (ira_object_t),
2807 object_range_compare_func);
2808 for (i = 0; i < num; i++)
2809 {
2810 ira_object_t obj = ira_object_id_map[i];
2811
2812 gcc_assert (obj != NULL);
2813 OBJECT_CONFLICT_ID (obj) = i;
2814 }
2815 for (i = num; i < ira_objects_num; i++)
2816 ira_object_id_map[i] = NULL;
2817}
2818
2819/* Set up minimal and maximal conflict ids of allocnos with which
2820 given allocno can conflict. */
2821static void
2822setup_min_max_conflict_allocno_ids (void)
2823{
2824 int aclass;
2825 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2826 int *live_range_min, *last_lived;
2827 int word0_min, word0_max;
2828 ira_allocno_t a;
2829 ira_allocno_iterator ai;
2830
2831 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2832 aclass = -1;
2833 first_not_finished = -1;
2834 for (i = 0; i < ira_objects_num; i++)
2835 {
2836 ira_object_t obj = ira_object_id_map[i];
2837
2838 if (obj == NULL)
2839 continue;
2840
2841 a = OBJECT_ALLOCNO (obj);
2842
2843 if (aclass < 0)
2844 {
2845 aclass = ALLOCNO_CLASS (a);
2846 min = i;
2847 first_not_finished = i;
2848 }
2849 else
2850 {
2851 start = OBJECT_MIN (obj);
2852 /* If we skip an allocno, the allocno with smaller ids will
2853 be also skipped because of the secondary sorting the
2854 range finishes (see function
2855 object_range_compare_func). */
2856 while (first_not_finished < i
2857 && start > OBJECT_MAX (ira_object_id_map
2858 [first_not_finished]))
2859 first_not_finished++;
2860 min = first_not_finished;
2861 }
2862 if (min == i)
2863 /* We could increase min further in this case but it is good
2864 enough. */
2865 min++;
2866 live_range_min[i] = OBJECT_MIN (obj);
2867 OBJECT_MIN (obj) = min;
2868 }
2869 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2870 aclass = -1;
2871 filled_area_start = -1;
2872 for (i = ira_objects_num - 1; i >= 0; i--)
2873 {
2874 ira_object_t obj = ira_object_id_map[i];
2875
2876 if (obj == NULL)
2877 continue;
2878
2879 a = OBJECT_ALLOCNO (obj);
2880 if (aclass < 0)
2881 {
2882 aclass = ALLOCNO_CLASS (a);
2883 for (j = 0; j < ira_max_point; j++)
2884 last_lived[j] = -1;
2885 filled_area_start = ira_max_point;
2886 }
2887 min = live_range_min[i];
2888 finish = OBJECT_MAX (obj);
2889 max = last_lived[finish];
2890 if (max < 0)
2891 /* We could decrease max further in this case but it is good
2892 enough. */
2893 max = OBJECT_CONFLICT_ID (obj) - 1;
2894 OBJECT_MAX (obj) = max;
2895 /* In filling, we can go further A range finish to recognize
2896 intersection quickly because if the finish of subsequently
2897 processed allocno (it has smaller conflict id) range is
2898 further A range finish than they are definitely intersected
2899 (the reason for this is the allocnos with bigger conflict id
2900 have their range starts not smaller than allocnos with
2901 smaller ids. */
2902 for (j = min; j < filled_area_start; j++)
2903 last_lived[j] = i;
2904 filled_area_start = min;
2905 }
2906 ira_free (last_lived);
2907 ira_free (live_range_min);
2908
2909 /* For allocnos with more than one object, we may later record extra conflicts in
2910 subobject 0 that we cannot really know about here.
2911 For now, simply widen the min/max range of these subobjects. */
2912
2913 word0_min = INT_MAX;
2914 word0_max = INT_MIN;
2915
2916 FOR_EACH_ALLOCNO (a, ai)
2917 {
2918 int n = ALLOCNO_NUM_OBJECTS (a);
2919 ira_object_t obj0;
2920
2921 if (n < 2)
2922 continue;
2923 obj0 = ALLOCNO_OBJECT (a, 0);
2924 if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2925 word0_min = OBJECT_CONFLICT_ID (obj0);
2926 if (OBJECT_CONFLICT_ID (obj0) > word0_max)
2927 word0_max = OBJECT_CONFLICT_ID (obj0);
2928 }
2929 FOR_EACH_ALLOCNO (a, ai)
2930 {
2931 int n = ALLOCNO_NUM_OBJECTS (a);
2932 ira_object_t obj0;
2933
2934 if (n < 2)
2935 continue;
2936 obj0 = ALLOCNO_OBJECT (a, 0);
2937 if (OBJECT_MIN (obj0) > word0_min)
2938 OBJECT_MIN (obj0) = word0_min;
2939 if (OBJECT_MAX (obj0) < word0_max)
2940 OBJECT_MAX (obj0) = word0_max;
2941 }
2942}
2943
2944
2945
2946static void
2947create_caps (void)
2948{
2949 ira_allocno_t a;
2950 ira_allocno_iterator ai;
2951 ira_loop_tree_node_t loop_tree_node;
2952
2953 FOR_EACH_ALLOCNO (a, ai)
2954 {
2955 if (ALLOCNO_LOOP_TREE_NODE (a) == ira_loop_tree_root)
2956 continue;
2957 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2958 create_cap_allocno (a);
2959 else if (ALLOCNO_CAP (a) == NULL)
2960 {
2961 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
2962 if (!bitmap_bit_p (loop_tree_node->border_allocnos, ALLOCNO_NUM (a)))
2963 create_cap_allocno (a);
2964 }
2965 }
2966}
2967
2968
2969
2970/* The page contains code transforming more one region internal
2971 representation (IR) to one region IR which is necessary for reload.
2972 This transformation is called IR flattening. We might just rebuild
2973 the IR for one region but we don't do it because it takes a lot of
2974 time. */
2975
2976/* Map: regno -> allocnos which will finally represent the regno for
2977 IR with one region. */
2978static ira_allocno_t *regno_top_level_allocno_map;
2979
2980/* Find the allocno that corresponds to A at a level one higher up in the
2981 loop tree. Returns NULL if A is a cap, or if it has no parent. */
2982ira_allocno_t
2983ira_parent_allocno (ira_allocno_t a)
2984{
2985 ira_loop_tree_node_t parent;
2986
2987 if (ALLOCNO_CAP (a) != NULL)
2988 return NULL;
2989
2990 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2991 if (parent == NULL)
2992 return NULL;
2993
2994 return parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2995}
2996
2997/* Find the allocno that corresponds to A at a level one higher up in the
2998 loop tree. If ALLOCNO_CAP is set for A, return that. */
2999ira_allocno_t
3000ira_parent_or_cap_allocno (ira_allocno_t a)
3001{
3002 if (ALLOCNO_CAP (a) != NULL)
3003 return ALLOCNO_CAP (a);
3004
3005 return ira_parent_allocno (a);
3006}
3007
3008/* Process all allocnos originated from pseudo REGNO and copy live
3009 ranges, hard reg conflicts, and allocno stack reg attributes from
3010 low level allocnos to final allocnos which are destinations of
3011 removed stores at a loop exit. Return true if we copied live
3012 ranges. */
3013static bool
3014copy_info_to_removed_store_destinations (int regno)
3015{
3016 ira_allocno_t a;
3017 ira_allocno_t parent_a = NULL;
3018 ira_loop_tree_node_t parent;
3019 bool merged_p;
3020
3021 merged_p = false;
3022 for (a = ira_regno_allocno_map[regno];
3023 a != NULL;
3024 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3025 {
3026 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
3027 /* This allocno will be removed. */
3028 continue;
3029
3030 /* Caps will be removed. */
3031 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3032 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
3033 parent != NULL;
3034 parent = parent->parent)
3035 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
3036 || (parent_a
3037 == regno_top_level_allocno_map[REGNO
3038 (allocno_emit_reg (parent_a))]
3039 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
3040 break;
3041 if (parent == NULL || parent_a == NULL)
3042 continue;
3043
3044 copy_allocno_live_ranges (a, parent_a);
3045 merge_hard_reg_conflicts (a, parent_a, true);
3046
3047 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
3048 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3049 += ALLOCNO_CALLS_CROSSED_NUM (a);
3050 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3051 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3052 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
3053 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
3054 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3055 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3056 merged_p = true;
3057 }
3058 return merged_p;
3059}
3060
3061/* Flatten the IR. In other words, this function transforms IR as if
3062 it were built with one region (without loops). We could make it
3063 much simpler by rebuilding IR with one region, but unfortunately it
3064 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
3065 IRA_MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
3066 IRA_MAX_POINT before emitting insns on the loop borders. */
3067void
3068ira_flattening (int max_regno_before_emit, int ira_max_point_before_emit)
3069{
3070 int i, j;
3071 bool keep_p;
3072 int hard_regs_num;
3073 bool new_pseudos_p, merged_p, mem_dest_p;
3074 unsigned int n;
3075 enum reg_class aclass;
3076 ira_allocno_t a, parent_a, first, second, node_first, node_second;
3077 ira_copy_t cp;
3078 ira_loop_tree_node_t node;
3079 live_range_t r;
3080 ira_allocno_iterator ai;
3081 ira_copy_iterator ci;
3082
3083 regno_top_level_allocno_map
3084 = (ira_allocno_t *) ira_allocate (max_reg_num ()
3085 * sizeof (ira_allocno_t));
3086 memset (regno_top_level_allocno_map, 0,
3087 max_reg_num () * sizeof (ira_allocno_t));
3088 new_pseudos_p = merged_p = false;
3089 FOR_EACH_ALLOCNO (a, ai)
3090 {
3091 ira_allocno_object_iterator oi;
3092 ira_object_t obj;
3093
3094 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3095 /* Caps are not in the regno allocno maps and they are never
3096 will be transformed into allocnos existing after IR
3097 flattening. */
3098 continue;
3099 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3100 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
3101 OBJECT_CONFLICT_HARD_REGS (obj));
3102#ifdef STACK_REGS
3103 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = ALLOCNO_NO_STACK_REG_P (a);
3104#endif
3105 }
3106 /* Fix final allocno attributes. */
3107 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
3108 {
3109 mem_dest_p = false;
3110 for (a = ira_regno_allocno_map[i];
3111 a != NULL;
3112 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
3113 {
3114 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3115
3116 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
3117 if (data->somewhere_renamed_p)
3118 new_pseudos_p = true;
3119 parent_a = ira_parent_allocno (a);
3120 if (parent_a == NULL)
3121 {
3122 ALLOCNO_COPIES (a) = NULL;
3123 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3124 continue;
3125 }
3126 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
3127
3128 if (data->mem_optimized_dest != NULL)
3129 mem_dest_p = true;
3130 parent_data = ALLOCNO_EMIT_DATA (parent_a);
3131 if (REGNO (data->reg) == REGNO (parent_data->reg))
3132 {
3133 merge_hard_reg_conflicts (a, parent_a, true);
3134 move_allocno_live_ranges (a, parent_a);
3135 merged_p = true;
3136 parent_data->mem_optimized_dest_p
3137 = (parent_data->mem_optimized_dest_p
3138 || data->mem_optimized_dest_p);
3139 continue;
3140 }
3141 new_pseudos_p = true;
3142 for (;;)
3143 {
3144 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
3145 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
3146 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
3147 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
3148 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3149 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3150 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3151 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
3152 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
3153 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
3154 && ALLOCNO_NREFS (parent_a) >= 0
3155 && ALLOCNO_FREQ (parent_a) >= 0);
3156 aclass = ALLOCNO_CLASS (parent_a);
3157 hard_regs_num = ira_class_hard_regs_num[aclass];
3158 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
3159 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
3160 for (j = 0; j < hard_regs_num; j++)
3161 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
3162 -= ALLOCNO_HARD_REG_COSTS (a)[j];
3163 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
3164 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
3165 for (j = 0; j < hard_regs_num; j++)
3166 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
3167 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
3168 ALLOCNO_CLASS_COST (parent_a)
3169 -= ALLOCNO_CLASS_COST (a);
3170 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
3171 parent_a = ira_parent_allocno (parent_a);
3172 if (parent_a == NULL)
3173 break;
3174 }
3175 ALLOCNO_COPIES (a) = NULL;
3176 regno_top_level_allocno_map[REGNO (data->reg)] = a;
3177 }
3178 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
3179 merged_p = true;
3180 }
3181 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
3182 if (merged_p || ira_max_point_before_emit != ira_max_point)
3183 ira_rebuild_start_finish_chains ();
3184 if (new_pseudos_p)
3185 {
3186 sparseset objects_live;
3187
3188 /* Rebuild conflicts. */
3189 FOR_EACH_ALLOCNO (a, ai)
3190 {
3191 ira_allocno_object_iterator oi;
3192 ira_object_t obj;
3193
3194 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3195 || ALLOCNO_CAP_MEMBER (a) != NULL)
3196 continue;
3197 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
3198 {
3199 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3200 ira_assert (r->object == obj);
3201 clear_conflicts (obj);
3202 }
3203 }
3204 objects_live = sparseset_alloc (ira_objects_num);
3205 for (i = 0; i < ira_max_point; i++)
3206 {
3207 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
3208 {
3209 ira_object_t obj = r->object;
3210
3211 a = OBJECT_ALLOCNO (obj);
3212 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3213 || ALLOCNO_CAP_MEMBER (a) != NULL)
3214 continue;
3215
3216 aclass = ALLOCNO_CLASS (a);
3217 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
3218 {
3219 ira_object_t live_obj = ira_object_id_map[n];
3220 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
3221 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
3222
3223 if (ira_reg_classes_intersect_p[aclass][live_aclass]
3224 /* Don't set up conflict for the allocno with itself. */
3225 && live_a != a)
3226 ira_add_conflict (obj, live_obj);
3227 }
3228 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
3229 }
3230
3231 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
3232 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
3233 }
3234 sparseset_free (objects_live);
3235 compress_conflict_vecs ();
3236 }
3237 /* Mark some copies for removing and change allocnos in the rest
3238 copies. */
3239 FOR_EACH_COPY (cp, ci)
3240 {
3241 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
3242 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
3243 {
3244 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3245 fprintf
3246 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
3247 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
3248 ALLOCNO_NUM (cp->first),
3249 REGNO (allocno_emit_reg (cp->first)),
3250 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
3251 ALLOCNO_NUM (cp->second),
3252 REGNO (allocno_emit_reg (cp->second)));
3253 cp->loop_tree_node = NULL;
3254 continue;
3255 }
3256 first
3257 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3258 second
3259 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
3260 node = cp->loop_tree_node;
3261 if (node == NULL)
3262 keep_p = true; /* It copy generated in ira-emit.c. */
3263 else
3264 {
3265 /* Check that the copy was not propagated from level on
3266 which we will have different pseudos. */
3267 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
3268 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
3269 keep_p = ((REGNO (allocno_emit_reg (first))
3270 == REGNO (allocno_emit_reg (node_first)))
3271 && (REGNO (allocno_emit_reg (second))
3272 == REGNO (allocno_emit_reg (node_second))));
3273 }
3274 if (keep_p)
3275 {
3276 cp->loop_tree_node = ira_loop_tree_root;
3277 cp->first = first;
3278 cp->second = second;
3279 }
3280 else
3281 {
3282 cp->loop_tree_node = NULL;
3283 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3284 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
3285 cp->num, ALLOCNO_NUM (cp->first),
3286 REGNO (allocno_emit_reg (cp->first)),
3287 ALLOCNO_NUM (cp->second),
3288 REGNO (allocno_emit_reg (cp->second)));
3289 }
3290 }
3291 /* Remove unnecessary allocnos on lower levels of the loop tree. */
3292 FOR_EACH_ALLOCNO (a, ai)
3293 {
3294 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
3295 || ALLOCNO_CAP_MEMBER (a) != NULL)
3296 {
3297 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
3298 fprintf (ira_dump_file, " Remove a%dr%d\n",
3299 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3300 ira_remove_allocno_prefs (a);
3301 finish_allocno (a);
3302 continue;
3303 }
3304 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
3305 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
3306 ALLOCNO_CAP (a) = NULL;
3307 /* Restore updated costs for assignments from reload. */
3308 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
3309 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
3310 if (! ALLOCNO_ASSIGNED_P (a))
3311 ira_free_allocno_updated_costs (a);
3312 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
3313 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
3314 }
3315 /* Remove unnecessary copies. */
3316 FOR_EACH_COPY (cp, ci)
3317 {
3318 if (cp->loop_tree_node == NULL)
3319 {
3320 ira_copies[cp->num] = NULL;
3321 finish_copy (cp);
3322 continue;
3323 }
3324 ira_assert
3325 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
3326 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
3327 add_allocno_copy_to_list (cp);
3328 swap_allocno_copy_ends_if_necessary (cp);
3329 }
3330 rebuild_regno_allocno_maps ();
3331 if (ira_max_point != ira_max_point_before_emit)
3332 ira_compress_allocno_live_ranges ();
3333 ira_free (regno_top_level_allocno_map);
3334}
3335
3336
3337
3338#ifdef ENABLE_IRA_CHECKING
3339/* Check creation of all allocnos. Allocnos on lower levels should
3340 have allocnos or caps on all upper levels. */
3341static void
3342check_allocno_creation (void)
3343{
3344 ira_allocno_t a;
3345 ira_allocno_iterator ai;
3346 ira_loop_tree_node_t loop_tree_node;
3347
3348 FOR_EACH_ALLOCNO (a, ai)
3349 {
3350 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
3351 ira_assert (bitmap_bit_p (loop_tree_node->all_allocnos,
3352 ALLOCNO_NUM (a)));
3353 if (loop_tree_node == ira_loop_tree_root)
3354 continue;
3355 if (ALLOCNO_CAP_MEMBER (a) != NULL)
3356 ira_assert (ALLOCNO_CAP (a) != NULL);
3357 else if (ALLOCNO_CAP (a) == NULL)
3358 ira_assert (loop_tree_node->parent
3359 ->regno_allocno_map[ALLOCNO_REGNO (a)] != NULL
3360 && bitmap_bit_p (loop_tree_node->border_allocnos,
3361 ALLOCNO_NUM (a)));
3362 }
3363}
3364#endif
3365
3366/* Identify allocnos which prefer a register class with a single hard register.
3367 Adjust ALLOCNO_CONFLICT_HARD_REG_COSTS so that conflicting allocnos are
3368 less likely to use the preferred singleton register. */
3369static void
3370update_conflict_hard_reg_costs (void)
3371{
3372 ira_allocno_t a;
3373 ira_allocno_iterator ai;
3374 int i, index, min;
3375
3376 FOR_EACH_ALLOCNO (a, ai)
3377 {
3378 reg_class_t aclass = ALLOCNO_CLASS (a);
3379 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
3380 int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
3381 if (singleton < 0)
3382 continue;
3383 index = ira_class_hard_reg_index[(int) aclass][singleton];
3384 if (index < 0)
3385 continue;
3386 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
3387 || ALLOCNO_HARD_REG_COSTS (a) == NULL)
3388 continue;
3389 min = INT_MAX;
3390 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
3391 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
3392 && min > ALLOCNO_HARD_REG_COSTS (a)[i])
3393 min = ALLOCNO_HARD_REG_COSTS (a)[i];
3394 if (min == INT_MAX)
3395 continue;
3396 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
3397 aclass, 0);
3398 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
3399 -= min - ALLOCNO_CLASS_COST (a);
3400 }
3401}
3402
3403/* Create a internal representation (IR) for IRA (allocnos, copies,
3404 loop tree nodes). The function returns TRUE if we generate loop
3405 structure (besides nodes representing all function and the basic
3406 blocks) for regional allocation. A true return means that we
3407 really need to flatten IR before the reload. */
3408bool
3409ira_build (void)
3410{
3411 bool loops_p;
3412
3413 df_analyze ();
3414 initiate_cost_vectors ();
3415 initiate_allocnos ();
3416 initiate_prefs ();
3417 initiate_copies ();
3418 create_loop_tree_nodes ();
3419 form_loop_tree ();
3420 create_allocnos ();
3421 ira_costs ();
3422 create_allocno_objects ();
3423 ira_create_allocno_live_ranges ();
3424 remove_unnecessary_regions (false);
3425 ira_compress_allocno_live_ranges ();
3426 update_bad_spill_attribute ();
3427 loops_p = more_one_region_p ();
3428 if (loops_p)
3429 {
3430 propagate_allocno_info ();
3431 create_caps ();
3432 }
3433 ira_tune_allocno_costs ();
3434#ifdef ENABLE_IRA_CHECKING
3435 check_allocno_creation ();
3436#endif
3437 setup_min_max_allocno_live_range_point ();
3438 sort_conflict_id_map ();
3439 setup_min_max_conflict_allocno_ids ();
3440 ira_build_conflicts ();
3441 update_conflict_hard_reg_costs ();
3442 if (! ira_conflicts_p)
3443 {
3444 ira_allocno_t a;
3445 ira_allocno_iterator ai;
3446
3447 /* Remove all regions but root one. */
3448 if (loops_p)
3449 {
3450 remove_unnecessary_regions (true);
3451 loops_p = false;
3452 }
3453 /* We don't save hard registers around calls for fast allocation
3454 -- add caller clobbered registers as conflicting ones to
3455 allocno crossing calls. */
3456 FOR_EACH_ALLOCNO (a, ai)
3457 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3458 ior_hard_reg_conflicts (a, &call_used_reg_set);
3459 }
3460 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3461 print_copies (ira_dump_file);
3462 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3463 print_prefs (ira_dump_file);
3464 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3465 {
3466 int n, nr, nr_big;
3467 ira_allocno_t a;
3468 live_range_t r;
3469 ira_allocno_iterator ai;
3470
3471 n = 0;
3472 nr = 0;
3473 nr_big = 0;
3474 FOR_EACH_ALLOCNO (a, ai)
3475 {
3476 int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3477
3478 if (nobj > 1)
3479 nr_big++;
3480 for (j = 0; j < nobj; j++)
3481 {
3482 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3483 n += OBJECT_NUM_CONFLICTS (obj);
3484 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3485 nr++;
3486 }
3487 }
3488 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
3489 current_loops == NULL ? 1 : number_of_loops (cfun),
3490 n_basic_blocks_for_fn (cfun), ira_max_point);
3491 fprintf (ira_dump_file,
3492 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3493 ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3494 }
3495 return loops_p;
3496}
3497
3498/* Release the data created by function ira_build. */
3499void
3500ira_destroy (void)
3501{
3502 finish_loop_tree_nodes ();
3503 finish_prefs ();
3504 finish_copies ();
3505 finish_allocnos ();
3506 finish_cost_vectors ();
3507 ira_finish_allocno_live_ranges ();
3508}
3509