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