?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2008-06-26 Kenneth Zadeck <zadeck@naturalbridge.com>
[official-gcc.git] / gcc / ira-build.c
blob2d206ada42f2a0d11ff0065bc534239539554e63
1 /* Building internal representation for IRA.
2 Copyright (C) 2006, 2007, 2008
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 "toplev.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
43 static copy_t find_allocno_copy (allocno_t, allocno_t, rtx, loop_tree_node_t);
44
45 /* The root of the loop tree corresponding to the all function. */
46 loop_tree_node_t ira_loop_tree_root;
47
48 /* Height of the loop tree. */
49 int ira_loop_tree_height;
50
51 /* All nodes representing basic blocks are referred through the
52 following array. We can not use basic block member `aux' for this
53 because it is used for insertion of insns on edges. */
54 loop_tree_node_t ira_bb_nodes;
55
56 /* All nodes representing loops are referred through the following
57 array. */
58 loop_tree_node_t ira_loop_nodes;
59
60 /* Map regno -> allocnos with given regno (see comments for
61 allocno member `next_regno_allocno'). */
62 allocno_t *regno_allocno_map;
63
64 /* Array of references to all allocnos. The order number of the
65 allocno corresponds to the index in the array. Removed allocnos
66 have NULL element value. */
67 allocno_t *allocnos;
68
69 /* Sizes of the previous array. */
70 int allocnos_num;
71
72 /* Map conflict id -> allocno with given conflict id (see comments for
73 allocno member `conflict_id'). */
74 allocno_t *conflict_id_allocno_map;
75
76 /* Array of references to all copies. The order number of the copy
77 corresponds to the index in the array. Removed copies have NULL
78 element value. */
79 copy_t *copies;
80
81 /* Size of the previous array. */
82 int copies_num;
83
84 /* Bitmap of allocnos used for different purposes. */
85 static bitmap allocnos_bitmap;
86
87 \f
88
89 /* LAST_BASIC_BLOCK before generating additional insns because of live
90 range splitting. Emitting insns on a critical edge creates a new
91 basic block. */
92 static int last_basic_block_before_change;
93
94 /* The following function allocates the loop tree nodes. If LOOPS_P
95 is FALSE, the nodes corresponding to the loops (except the root
96 which corresponds the all function) will be not allocated but nodes
97 will still be allocated for basic blocks. */
98 static void
99 create_loop_tree_nodes (bool loops_p)
100 {
101 unsigned int i, j;
102 int max_regno;
103 bool skip_p;
104 edge_iterator ei;
105 edge e;
106 VEC (edge, heap) *edges;
107 loop_p loop;
108
109 ira_bb_nodes
110 = ira_allocate (sizeof (struct loop_tree_node) * last_basic_block);
111 last_basic_block_before_change = last_basic_block;
112 for (i = 0; i < (unsigned int) last_basic_block; i++)
113 {
114 ira_bb_nodes[i].regno_allocno_map = NULL;
115 memset (ira_bb_nodes[i].reg_pressure, 0,
116 sizeof (ira_bb_nodes[i].reg_pressure));
117 ira_bb_nodes[i].mentioned_allocnos = NULL;
118 ira_bb_nodes[i].modified_regnos = NULL;
119 ira_bb_nodes[i].border_allocnos = NULL;
120 ira_bb_nodes[i].local_copies = NULL;
121 }
122 ira_loop_nodes = ira_allocate (sizeof (struct loop_tree_node)
123 * VEC_length (loop_p, ira_loops.larray));
124 max_regno = max_reg_num ();
125 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
126 {
127 if (loop != ira_loops.tree_root)
128 {
129 ira_loop_nodes[i].regno_allocno_map = NULL;
130 if (! loops_p)
131 continue;
132 skip_p = false;
133 FOR_EACH_EDGE (e, ei, loop->header->preds)
134 if (e->src != loop->latch
135 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
136 {
137 skip_p = true;
138 break;
139 }
140 if (skip_p)
141 continue;
142 edges = get_loop_exit_edges (loop);
143 for (j = 0; VEC_iterate (edge, edges, j, e); j++)
144 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
145 {
146 skip_p = true;
147 break;
148 }
149 VEC_free (edge, heap, edges);
150 if (skip_p)
151 continue;
152 }
153 ira_loop_nodes[i].regno_allocno_map
154 = ira_allocate (sizeof (allocno_t) * max_regno);
155 memset (ira_loop_nodes[i].regno_allocno_map, 0,
156 sizeof (allocno_t) * max_regno);
157 memset (ira_loop_nodes[i].reg_pressure, 0,
158 sizeof (ira_loop_nodes[i].reg_pressure));
159 ira_loop_nodes[i].mentioned_allocnos = ira_allocate_bitmap ();
160 ira_loop_nodes[i].modified_regnos = ira_allocate_bitmap ();
161 ira_loop_nodes[i].border_allocnos = ira_allocate_bitmap ();
162 ira_loop_nodes[i].local_copies = ira_allocate_bitmap ();
163 }
164 }
165
166 /* Free the loop tree node of a loop. */
167 static void
168 finish_loop_tree_node (loop_tree_node_t loop)
169 {
170 if (loop->regno_allocno_map != NULL)
171 {
172 ira_assert (loop->bb == NULL);
173 ira_free_bitmap (loop->local_copies);
174 ira_free_bitmap (loop->border_allocnos);
175 ira_free_bitmap (loop->modified_regnos);
176 ira_free_bitmap (loop->mentioned_allocnos);
177 ira_free (loop->regno_allocno_map);
178 loop->regno_allocno_map = NULL;
179 }
180 }
181
182 /* Free the loop tree nodes. */
183 static void
184 finish_loop_tree_nodes (void)
185 {
186 unsigned int i;
187 loop_p loop;
188
189 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
190 finish_loop_tree_node (&ira_loop_nodes[i]);
191 ira_free (ira_loop_nodes);
192 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
193 {
194 if (ira_bb_nodes[i].local_copies != NULL)
195 ira_free_bitmap (ira_bb_nodes[i].local_copies);
196 if (ira_bb_nodes[i].border_allocnos != NULL)
197 ira_free_bitmap (ira_bb_nodes[i].border_allocnos);
198 if (ira_bb_nodes[i].modified_regnos != NULL)
199 ira_free_bitmap (ira_bb_nodes[i].modified_regnos);
200 if (ira_bb_nodes[i].mentioned_allocnos != NULL)
201 ira_free_bitmap (ira_bb_nodes[i].mentioned_allocnos);
202 if (ira_bb_nodes[i].regno_allocno_map != NULL)
203 ira_free (ira_bb_nodes[i].regno_allocno_map);
204 }
205 ira_free (ira_bb_nodes);
206 }
207
208 \f
209
210 /* The following recursive function adds LOOP to the loop tree
211 hierarchy. LOOP is added only once. */
212 static void
213 add_loop_to_tree (struct loop *loop)
214 {
215 struct loop *parent;
216 loop_tree_node_t loop_node, parent_node;
217
218 /* We can not use loop node access macros here because of potential
219 checking and because the nodes are not initialized enough
220 yet. */
221 if (loop_outer (loop) != NULL)
222 add_loop_to_tree (loop_outer (loop));
223 if (ira_loop_nodes[loop->num].regno_allocno_map != NULL
224 && ira_loop_nodes[loop->num].children == NULL)
225 {
226 /* We have not added loop node to the tree yet. */
227 loop_node = &ira_loop_nodes[loop->num];
228 loop_node->loop = loop;
229 loop_node->bb = NULL;
230 for (parent = loop_outer (loop);
231 parent != NULL;
232 parent = loop_outer (parent))
233 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
234 break;
235 if (parent == NULL)
236 {
237 loop_node->next = NULL;
238 loop_node->subloop_next = NULL;
239 loop_node->parent = NULL;
240 }
241 else
242 {
243 parent_node = &ira_loop_nodes[parent->num];
244 loop_node->next = parent_node->children;
245 parent_node->children = loop_node;
246 loop_node->subloop_next = parent_node->subloops;
247 parent_node->subloops = loop_node;
248 loop_node->parent = parent_node;
249 }
250 }
251 }
252
253 /* The following recursive function sets up levels of nodes of the
254 tree given its root LOOP_NODE. The enumeration starts with LEVEL.
255 The function returns maximal value of level in the tree + 1. */
256 static int
257 setup_loop_tree_level (loop_tree_node_t loop_node, int level)
258 {
259 int height, max_height;
260 loop_tree_node_t subloop_node;
261
262 ira_assert (loop_node->bb == NULL);
263 loop_node->level = level;
264 max_height = level + 1;
265 for (subloop_node = loop_node->subloops;
266 subloop_node != NULL;
267 subloop_node = subloop_node->subloop_next)
268 {
269 ira_assert (subloop_node->bb == NULL);
270 height = setup_loop_tree_level (subloop_node, level + 1);
271 if (height > max_height)
272 max_height = height;
273 }
274 return max_height;
275 }
276
277 /* Create the loop tree. The algorithm is designed to provide correct
278 order of loops (they are ordered by their last loop BB) and basic
279 blocks in the chain formed by member next. */
280 static void
281 form_loop_tree (void)
282 {
283 unsigned int i;
284 basic_block bb;
285 struct loop *parent;
286 loop_tree_node_t bb_node, loop_node;
287 loop_p loop;
288
289 /* We can not use loop/bb node access macros because of potential
290 checking and because the nodes are not initialized enough
291 yet. */
292 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
293 if (ira_loop_nodes[i].regno_allocno_map != NULL)
294 {
295 ira_loop_nodes[i].children = NULL;
296 ira_loop_nodes[i].subloops = NULL;
297 }
298 FOR_EACH_BB_REVERSE (bb)
299 {
300 bb_node = &ira_bb_nodes[bb->index];
301 bb_node->bb = bb;
302 bb_node->loop = NULL;
303 bb_node->subloops = NULL;
304 bb_node->children = NULL;
305 bb_node->subloop_next = NULL;
306 bb_node->next = NULL;
307 for (parent = bb->loop_father;
308 parent != NULL;
309 parent = loop_outer (parent))
310 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
311 break;
312 add_loop_to_tree (parent);
313 loop_node = &ira_loop_nodes[parent->num];
314 bb_node->next = loop_node->children;
315 bb_node->parent = loop_node;
316 loop_node->children = bb_node;
317 }
318 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num);
319 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
320 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
321 }
322
323 \f
324
325 /* Rebuild REGNO_ALLOCNO_MAP and REGNO_ALLOCNO_MAPs. */
326 static void
327 rebuild_regno_allocno_maps (void)
328 {
329 unsigned int l;
330 int max_regno, regno;
331 allocno_t a;
332 loop_tree_node_t loop_tree_node;
333 loop_p loop;
334 allocno_iterator ai;
335
336 max_regno = max_reg_num ();
337 for (l = 0; VEC_iterate (loop_p, ira_loops.larray, l, loop); l++)
338 if (ira_loop_nodes[l].regno_allocno_map != NULL)
339 {
340 ira_free (ira_loop_nodes[l].regno_allocno_map);
341 ira_loop_nodes[l].regno_allocno_map
342 = ira_allocate (sizeof (allocno_t) * max_regno);
343 memset (ira_loop_nodes[l].regno_allocno_map, 0,
344 sizeof (allocno_t) * max_regno);
345 }
346 ira_free (regno_allocno_map);
347 regno_allocno_map = ira_allocate (max_regno * sizeof (allocno_t));
348 memset (regno_allocno_map, 0, max_regno * sizeof (allocno_t));
349 FOR_EACH_ALLOCNO (a, ai)
350 {
351 if (ALLOCNO_CAP_MEMBER (a) != NULL)
352 /* Caps are not in the regno allocno maps. */
353 continue;
354 regno = ALLOCNO_REGNO (a);
355 loop_tree_node = ALLOCNO_LOOP_TREE_NODE (a);
356 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = regno_allocno_map[regno];
357 regno_allocno_map[regno] = a;
358 if (loop_tree_node->regno_allocno_map[regno] == NULL)
359 /* Remember that we can create temporary allocnos to break
360 cycles in register shuffle. */
361 loop_tree_node->regno_allocno_map[regno] = a;
362 }
363 }
364
365 \f
366
367 /* Array of vectors containing calls given pseudo-register lives
368 through. */
369 VEC(rtx, heap) **regno_calls;
370
371 /* The length of the previous array. */
372 static int regno_calls_num;
373
374 /* The function initializes array of vectors containing calls
375 intersected by live ranges of pseudo-registers. */
376 static void
377 initiate_calls (void)
378 {
379 regno_calls_num = max_reg_num () * 3 / 2;
380 regno_calls = ira_allocate (regno_calls_num * sizeof (VEC(rtx, heap) *));
381 memset (regno_calls, 0, regno_calls_num * sizeof (VEC(rtx, heap) *));
382 }
383
384 /* Expand the array of vectors containing calls for
385 pseudo-registers. */
386 static void
387 expand_calls (void)
388 {
389 int max_regno = max_reg_num ();
390
391 if (max_regno > regno_calls_num)
392 {
393 regno_calls = ira_reallocate (regno_calls,
394 max_regno * sizeof (VEC(rtx, heap) *));
395 memset (regno_calls + regno_calls_num, 0,
396 (max_regno - regno_calls_num) * sizeof (VEC(rtx, heap) *));
397 regno_calls_num = max_regno;
398 }
399 }
400
401 /* Remove NULL elements from vectors containing calls intersected by
402 live ranges of pseudo-registers. */
403 static void
404 compress_calls (void)
405 {
406 int regno, curr, length, last;
407 rtx *allocno_calls;
408
409 for (regno = 0; regno < regno_calls_num; regno++)
410 {
411 allocno_calls = VEC_address (rtx, regno_calls[regno]);
412 length = VEC_length (rtx, regno_calls[regno]);
413 for (last = curr = 0; curr < length; curr++)
414 if (allocno_calls[curr] != NULL_RTX)
415 allocno_calls[last++] = allocno_calls[curr];
416 VEC_truncate (rtx, regno_calls[regno], last);
417 }
418 }
419
420 /* Add CALLs to REGNO's vector of intersected calls and returns the
421 element index in the vector. */
422 int
423 add_regno_call (int regno, rtx call)
424 {
425 int result;
426
427 gcc_assert (regno < regno_calls_num);
428 if (regno_calls[regno] == NULL)
429 regno_calls[regno] = VEC_alloc (rtx, heap, 10);
430 result = VEC_length (rtx, regno_calls[regno]);
431 VEC_safe_push (rtx, heap, regno_calls[regno], call);
432 return result;
433 }
434
435 /* Free the array of vectors containing calls intersected by live
436 ranges of pseudo-registers. */
437 static void
438 finish_calls (void)
439 {
440 int i;
441
442 for (i = 0; i < regno_calls_num; i++)
443 VEC_free (rtx, heap, regno_calls[i]);
444 ira_free (regno_calls);
445 }
446
447 \f
448
449 /* Pools for allocnos and allocno live ranges. */
450 static alloc_pool allocno_pool, allocno_live_range_pool;
451
452 /* Vec containing references to all created allocnos. It is a
453 container of array allocnos. */
454 static VEC(allocno_t,heap) *allocno_vec;
455
456 /* Vec containing references to all created allocnos. It is a
457 container of conflict_id_allocno_map. */
458 static VEC(allocno_t,heap) *conflict_id_allocno_map_vec;
459
460 /* Initialize data concerning allocnos. */
461 static void
462 initiate_allocnos (void)
463 {
464 allocno_live_range_pool
465 = create_alloc_pool ("allocno live ranges",
466 sizeof (struct allocno_live_range), 100);
467 allocno_pool = create_alloc_pool ("allocnos", sizeof (struct allocno), 100);
468 allocno_vec = VEC_alloc (allocno_t, heap, max_reg_num () * 2);
469 allocnos = NULL;
470 allocnos_num = 0;
471 conflict_id_allocno_map_vec
472 = VEC_alloc (allocno_t, heap, max_reg_num () * 2);
473 conflict_id_allocno_map = NULL;
474 regno_allocno_map = ira_allocate (max_reg_num () * sizeof (allocno_t));
475 memset (regno_allocno_map, 0, max_reg_num () * sizeof (allocno_t));
476 }
477
478 /* Create and return the allocno corresponding to REGNO in
479 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
480 same regno if CAP_P is FALSE. */
481 allocno_t
482 create_allocno (int regno, bool cap_p, loop_tree_node_t loop_tree_node)
483 {
484 allocno_t a;
485
486 a = pool_alloc (allocno_pool);
487 ALLOCNO_REGNO (a) = regno;
488 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
489 if (! cap_p)
490 {
491 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = regno_allocno_map[regno];
492 regno_allocno_map[regno] = a;
493 if (loop_tree_node->regno_allocno_map[regno] == NULL)
494 /* Remember that we can create temporary allocnos to break
495 cycles in register shuffle on region borders (see
496 ira-emit.c). */
497 loop_tree_node->regno_allocno_map[regno] = a;
498 }
499 ALLOCNO_CAP (a) = NULL;
500 ALLOCNO_CAP_MEMBER (a) = NULL;
501 ALLOCNO_NUM (a) = allocnos_num;
502 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = NULL;
503 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
504 COPY_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a), no_alloc_regs);
505 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a), no_alloc_regs);
506 ALLOCNO_NREFS (a) = 0;
507 ALLOCNO_FREQ (a) = 1;
508 ALLOCNO_HARD_REGNO (a) = -1;
509 ALLOCNO_CALL_FREQ (a) = 0;
510 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
511 ALLOCNO_CALLS_CROSSED_START (a) = -1;
512 #ifdef STACK_REGS
513 ALLOCNO_NO_STACK_REG_P (a) = false;
514 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
515 #endif
516 ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
517 ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
518 ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
519 ALLOCNO_CHILD_RENAMED_P (a) = false;
520 ALLOCNO_DONT_REASSIGN_P (a) = false;
521 ALLOCNO_IN_GRAPH_P (a) = false;
522 ALLOCNO_ASSIGNED_P (a) = false;
523 ALLOCNO_MAY_BE_SPILLED_P (a) = false;
524 ALLOCNO_SPLAY_REMOVED_P (a) = false;
525 ALLOCNO_CONFLICT_VEC_P (a) = false;
526 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
527 ALLOCNO_COPIES (a) = NULL;
528 ALLOCNO_HARD_REG_COSTS (a) = NULL;
529 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
530 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
531 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
532 ALLOCNO_LEFT_CONFLICTS_NUM (a) = -1;
533 ALLOCNO_COVER_CLASS (a) = NO_REGS;
534 ALLOCNO_COVER_CLASS_COST (a) = 0;
535 ALLOCNO_MEMORY_COST (a) = 0;
536 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
537 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
538 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
539 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
540 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
541 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
542 ALLOCNO_LIVE_RANGES (a) = NULL;
543 ALLOCNO_MIN (a) = INT_MAX;
544 ALLOCNO_MAX (a) = -1;
545 ALLOCNO_CONFLICT_ID (a) = allocnos_num;
546 VEC_safe_push (allocno_t, heap, allocno_vec, a);
547 allocnos = VEC_address (allocno_t, allocno_vec);
548 allocnos_num = VEC_length (allocno_t, allocno_vec);
549 VEC_safe_push (allocno_t, heap, conflict_id_allocno_map_vec, a);
550 conflict_id_allocno_map
551 = VEC_address (allocno_t, conflict_id_allocno_map_vec);
552 return a;
553 }
554
555 /* Set up cover class for A and update its conflict hard registers. */
556 void
557 set_allocno_cover_class (allocno_t a, enum reg_class cover_class)
558 {
559 ALLOCNO_COVER_CLASS (a) = cover_class;
560 IOR_COMPL_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (a),
561 reg_class_contents[cover_class]);
562 IOR_COMPL_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a),
563 reg_class_contents[cover_class]);
564 }
565
566 /* Return TRUE if the conflict vector with NUM elements is more
567 profitable than conflict bit vector for A. */
568 bool
569 conflict_vector_profitable_p (allocno_t a, int num)
570 {
571 int nw;
572
573 if (ALLOCNO_MAX (a) < ALLOCNO_MIN (a))
574 /* We prefer bit vector in such case because it does not result in
575 allocation. */
576 return false;
577
578 nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + INT_BITS) / INT_BITS;
579 return 2 * sizeof (allocno_t) * (num + 1) < 3 * nw * sizeof (INT_TYPE);
580 }
581
582 /* Allocates and initialize the conflict vector of A for NUM
583 conflicting allocnos. */
584 void
585 allocate_allocno_conflict_vec (allocno_t a, int num)
586 {
587 int size;
588 allocno_t *vec;
589
590 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
591 num++; /* for NULL end marker */
592 size = sizeof (allocno_t) * num;
593 vec = ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
594 vec[0] = NULL;
595 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
596 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
597 ALLOCNO_CONFLICT_VEC_P (a) = true;
598 }
599
600 /* Allocate and initialize the conflict bit vector of A. */
601 static void
602 allocate_allocno_conflict_bit_vec (allocno_t a)
603 {
604 unsigned int size;
605
606 ira_assert (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) == NULL);
607 size = ((ALLOCNO_MAX (a) - ALLOCNO_MIN (a) + INT_BITS)
608 / INT_BITS * sizeof (INT_TYPE));
609 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) = ira_allocate (size);
610 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, size);
611 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) = size;
612 ALLOCNO_CONFLICT_VEC_P (a) = false;
613 }
614
615 /* Allocate and initialize the conflict vector or conflict bit vector
616 of A for NUM conflicting allocnos whatever is more profitable. */
617 void
618 allocate_allocno_conflicts (allocno_t a, int num)
619 {
620 if (conflict_vector_profitable_p (a, num))
621 allocate_allocno_conflict_vec (a, num);
622 else
623 allocate_allocno_conflict_bit_vec (a);
624 }
625
626 /* Add A2 to the conflicts of A1. */
627 static void
628 add_to_allocno_conflicts (allocno_t a1, allocno_t a2)
629 {
630 int num;
631 unsigned int size;
632
633 if (ALLOCNO_CONFLICT_VEC_P (a1))
634 {
635 allocno_t *vec;
636
637 num = ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1) + 2;
638 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1)
639 >= num * sizeof (allocno_t))
640 vec = ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
641 else
642 {
643 size = (3 * num / 2 + 1) * sizeof (allocno_t);
644 vec = ira_allocate (size);
645 memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
646 sizeof (allocno_t) * ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1));
647 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
648 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
649 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
650 }
651 vec[num - 2] = a2;
652 vec[num - 1] = NULL;
653 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a1)++;
654 }
655 else
656 {
657 int nw, added_head_nw, id;
658 INT_TYPE *vec;
659
660 id = ALLOCNO_CONFLICT_ID (a2);
661 vec = ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1);
662 if (ALLOCNO_MIN (a1) > id)
663 {
664 /* Expand head of the bit vector. */
665 added_head_nw = (ALLOCNO_MIN (a1) - id - 1) / INT_BITS + 1;
666 nw = (ALLOCNO_MAX (a1) - ALLOCNO_MIN (a1)) / INT_BITS + 1;
667 size = (nw + added_head_nw) * sizeof (INT_TYPE);
668 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) >= size)
669 {
670 memmove ((char *) vec + added_head_nw * sizeof (INT_TYPE),
671 vec, nw * sizeof (INT_TYPE));
672 memset (vec, 0, added_head_nw * sizeof (INT_TYPE));
673 }
674 else
675 {
676 size = (3 * (nw + added_head_nw) / 2 + 1) * sizeof (INT_TYPE);
677 vec = ira_allocate (size);
678 memcpy
679 ((char *) vec + added_head_nw * sizeof (INT_TYPE),
680 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1), nw * sizeof (INT_TYPE));
681 memset (vec, 0, added_head_nw * sizeof (INT_TYPE));
682 memset ((char *) vec + (nw + added_head_nw) * sizeof (INT_TYPE),
683 0, size - (nw + added_head_nw) * sizeof (INT_TYPE));
684 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
685 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
686 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
687 }
688 ALLOCNO_MIN (a1) -= added_head_nw * INT_BITS;
689 }
690 else if (ALLOCNO_MAX (a1) < id)
691 {
692 nw = (id - ALLOCNO_MIN (a1)) / INT_BITS + 1;
693 size = nw * sizeof (INT_TYPE);
694 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) < size)
695 {
696 /* Expand tail of the bit vector. */
697 size = (3 * nw / 2 + 1) * sizeof (INT_TYPE);
698 vec = ira_allocate (size);
699 memcpy (vec, ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1),
700 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
701 memset ((char *) vec + ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1),
702 0, size - ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1));
703 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1));
704 ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a1) = vec;
705 ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a1) = size;
706 }
707 ALLOCNO_MAX (a1) = id;
708 }
709 SET_ALLOCNO_SET_BIT (vec, id, ALLOCNO_MIN (a1), ALLOCNO_MAX (a1));
710 }
711 }
712
713 /* Add A1 to the conflicts of A2 and vise versa. */
714 void
715 add_allocno_conflict (allocno_t a1, allocno_t a2)
716 {
717 add_to_allocno_conflicts (a1, a2);
718 add_to_allocno_conflicts (a2, a1);
719 }
720
721 /* Clear all conflicts of allocno A. */
722 static void
723 clear_allocno_conflicts (allocno_t a)
724 {
725 if (ALLOCNO_CONFLICT_VEC_P (a))
726 {
727 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = 0;
728 ((allocno_t *) ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a))[0] = NULL;
729 }
730 else if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY_SIZE (a) != 0)
731 {
732 int nw;
733
734 nw = (ALLOCNO_MAX (a) - ALLOCNO_MIN (a)) / INT_BITS + 1;
735 memset (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a), 0, nw * sizeof (INT_TYPE));
736 }
737 }
738
739 /* The array used to find duplications in conflict vectors of
740 allocnos. */
741 static int *allocno_conflict_check;
742
743 /* The value used to mark allocation presence in conflict vector of
744 the current allocno. */
745 static int curr_allocno_conflict_check_tick;
746
747 /* Remove duplications in conflict vector of A. */
748 static void
749 compress_allocno_conflict_vec (allocno_t a)
750 {
751 allocno_t *vec, conflict_a;
752 int i, j;
753
754 ira_assert (ALLOCNO_CONFLICT_VEC_P (a));
755 vec = ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a);
756 curr_allocno_conflict_check_tick++;
757 for (i = j = 0; (conflict_a = vec[i]) != NULL; i++)
758 {
759 if (allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
760 != curr_allocno_conflict_check_tick)
761 {
762 allocno_conflict_check[ALLOCNO_NUM (conflict_a)]
763 = curr_allocno_conflict_check_tick;
764 vec[j++] = conflict_a;
765 }
766 }
767 ALLOCNO_CONFLICT_ALLOCNOS_NUM (a) = j;
768 vec[j] = NULL;
769 }
770
771 /* Remove duplications in conflict vectors of all allocnos. */
772 static void
773 compress_conflict_vecs (void)
774 {
775 allocno_t a;
776 allocno_iterator ai;
777
778 allocno_conflict_check = ira_allocate (sizeof (int) * allocnos_num);
779 memset (allocno_conflict_check, 0, sizeof (int) * allocnos_num);
780 curr_allocno_conflict_check_tick = 0;
781 FOR_EACH_ALLOCNO (a, ai)
782 if (ALLOCNO_CONFLICT_VEC_P (a))
783 compress_allocno_conflict_vec (a);
784 ira_free (allocno_conflict_check);
785 }
786
787 /* This recursive function outputs allocno A and if it is a cap the
788 function outputs its members. */
789 void
790 print_expanded_allocno (allocno_t a)
791 {
792 basic_block bb;
793
794 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
795 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
796 fprintf (ira_dump_file, ",b%d", bb->index);
797 else
798 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num);
799 if (ALLOCNO_CAP_MEMBER (a) != NULL)
800 {
801 fprintf (ira_dump_file, ":");
802 print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
803 }
804 fprintf (ira_dump_file, ")");
805 }
806
807 /* Create and return the cap representing allocno A in the
808 parent loop. */
809 static allocno_t
810 create_cap_allocno (allocno_t a)
811 {
812 allocno_t cap;
813 loop_tree_node_t parent;
814
815 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
816 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
817 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
818 cap = create_allocno (ALLOCNO_REGNO (a), true, parent);
819 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
820 set_allocno_cover_class (cap, ALLOCNO_COVER_CLASS (a));
821 ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
822 ALLOCNO_CAP_MEMBER (cap) = a;
823 bitmap_set_bit (parent->mentioned_allocnos, ALLOCNO_NUM (cap));
824 ALLOCNO_CAP (a) = cap;
825 ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a);
826 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
827 ALLOCNO_UPDATED_MEMORY_COST (cap) = ALLOCNO_UPDATED_MEMORY_COST (a);
828 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
829 {
830 fprintf (ira_dump_file, " Creating cap ");
831 print_expanded_allocno (cap);
832 fprintf (ira_dump_file, "\n");
833 }
834 return cap;
835 }
836
837 /* Propagates info to the CAP from its member. We must propagate info
838 which is not available at the cap creation time. */
839 static void
840 propagate_info_to_cap (allocno_t cap)
841 {
842 int regno, conflicts_num;
843 enum reg_class cover_class;
844 allocno_t a, conflict_allocno, conflict_parent_allocno;
845 allocno_t another_a, parent_a;
846 loop_tree_node_t parent;
847 copy_t cp, next_cp;
848 allocno_conflict_iterator aci;
849
850 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (cap) == cap
851 && ALLOCNO_NEXT_COALESCED_ALLOCNO (cap) == cap
852 && ALLOCNO_CONFLICT_ALLOCNO_ARRAY (cap) == NULL
853 && ALLOCNO_CALLS_CROSSED_NUM (cap) == 0);
854 a = ALLOCNO_CAP_MEMBER (cap);
855 parent = ALLOCNO_LOOP_TREE_NODE (cap);
856 cover_class = ALLOCNO_COVER_CLASS (cap);
857 allocate_and_copy_costs
858 (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a));
859 allocate_and_copy_costs
860 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class,
861 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
862 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
863 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
864 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
865 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (cap),
866 ALLOCNO_CONFLICT_HARD_REGS (a));
867 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (cap),
868 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
869 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
870 ALLOCNO_CALLS_CROSSED_START (cap) = ALLOCNO_CALLS_CROSSED_START (a);
871 #ifdef STACK_REGS
872 ALLOCNO_NO_STACK_REG_P (cap) = ALLOCNO_NO_STACK_REG_P (a);
873 ALLOCNO_TOTAL_NO_STACK_REG_P (cap) = ALLOCNO_TOTAL_NO_STACK_REG_P (a);
874 #endif
875 /* Add copies to the cap. */
876 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
877 {
878 if (cp->first == a)
879 {
880 next_cp = cp->next_first_allocno_copy;
881 another_a = cp->second;
882 }
883 else if (cp->second == a)
884 {
885 next_cp = cp->next_second_allocno_copy;
886 another_a = cp->first;
887 }
888 else
889 gcc_unreachable ();
890 parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (another_a)];
891 if (parent_a == NULL)
892 parent_a = ALLOCNO_CAP (another_a);
893 if (parent_a != NULL
894 && find_allocno_copy (cap, parent_a,
895 cp->insn, cp->loop_tree_node) == NULL)
896 /* Upper level allocno might be not existing because it is not
897 mentioned or lived on the region border. It is just living
898 on BB start of the loop. */
899 add_allocno_copy (cap, parent_a, cp->freq, cp->insn,
900 cp->loop_tree_node);
901 }
902 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
903 {
904 conflicts_num = 0;
905 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
906 conflicts_num++;
907 allocate_allocno_conflicts (cap, conflicts_num);
908 FOR_EACH_ALLOCNO_CONFLICT (a, conflict_allocno, aci)
909 {
910 regno = ALLOCNO_REGNO (conflict_allocno);
911 conflict_parent_allocno = parent->regno_allocno_map[regno];
912 if (conflict_parent_allocno == NULL)
913 conflict_parent_allocno = ALLOCNO_CAP (conflict_allocno);
914 if (conflict_parent_allocno != NULL
915 && (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (conflict_parent_allocno)
916 != NULL))
917 add_allocno_conflict (cap, conflict_parent_allocno);
918 }
919 }
920 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
921 {
922 fprintf (ira_dump_file, " Propagate info to cap ");
923 print_expanded_allocno (cap);
924 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (cap) != NULL)
925 {
926 fprintf (ira_dump_file, "\n Conflicts:");
927 FOR_EACH_ALLOCNO_CONFLICT (cap, conflict_allocno, aci)
928 {
929 fprintf (ira_dump_file, " a%d(r%d,",
930 ALLOCNO_NUM (conflict_allocno),
931 ALLOCNO_REGNO (conflict_allocno));
932 ira_assert
933 (ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->bb == NULL);
934 fprintf (ira_dump_file, "l%d)",
935 ALLOCNO_LOOP_TREE_NODE (conflict_allocno)->loop->num);
936 }
937 }
938 fprintf (ira_dump_file, "\n");
939 }
940 }
941
942
943 /* Create and return allocno live range with given attributes. */
944 allocno_live_range_t
945 create_allocno_live_range (allocno_t a, int start, int finish,
946 allocno_live_range_t next)
947 {
948 allocno_live_range_t p;
949
950 p = pool_alloc (allocno_live_range_pool);
951 p->allocno = a;
952 p->start = start;
953 p->finish = finish;
954 p->next = next;
955 return p;
956 }
957
958 /* Copy allocno live range R and return the result. */
959 static allocno_live_range_t
960 copy_allocno_live_range (allocno_live_range_t r)
961 {
962 allocno_live_range_t p;
963
964 p = pool_alloc (allocno_live_range_pool);
965 *p = *r;
966 return p;
967 }
968
969 /* Copy allocno live range list given by its head R and return the
970 result. */
971 static allocno_live_range_t
972 copy_allocno_live_range_list (allocno_live_range_t r)
973 {
974 allocno_live_range_t p, first, last;
975
976 if (r == NULL)
977 return NULL;
978 for (first = last = NULL; r != NULL; r = r->next)
979 {
980 p = copy_allocno_live_range (r);
981 if (first == NULL)
982 first = p;
983 else
984 last->next = p;
985 last = p;
986 }
987 return first;
988 }
989
990 /* Free allocno live range R. */
991 void
992 finish_allocno_live_range (allocno_live_range_t r)
993 {
994 pool_free (allocno_live_range_pool, r);
995 }
996
997 /* Free updated register costs of allocno A. */
998 void
999 free_allocno_updated_costs (allocno_t a)
1000 {
1001 enum reg_class cover_class;
1002
1003 cover_class = ALLOCNO_COVER_CLASS (a);
1004 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1005 free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
1006 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1007 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1008 free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1009 cover_class);
1010 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1011 }
1012
1013 /* Free the memory allocated for allocno A. */
1014 static void
1015 finish_allocno (allocno_t a)
1016 {
1017 allocno_live_range_t r, next_r;
1018 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a);
1019
1020 allocnos[ALLOCNO_NUM (a)] = NULL;
1021 conflict_id_allocno_map[ALLOCNO_CONFLICT_ID (a)] = NULL;
1022 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a) != NULL)
1023 ira_free (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (a));
1024 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1025 free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), cover_class);
1026 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1027 free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class);
1028 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1029 free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class);
1030 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1031 free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1032 cover_class);
1033 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = next_r)
1034 {
1035 next_r = r->next;
1036 finish_allocno_live_range (r);
1037 }
1038 pool_free (allocno_pool, a);
1039 }
1040
1041 /* Free the memory allocated for all allocnos. */
1042 static void
1043 finish_allocnos (void)
1044 {
1045 allocno_t a;
1046 allocno_iterator ai;
1047
1048 FOR_EACH_ALLOCNO (a, ai)
1049 finish_allocno (a);
1050 ira_free (regno_allocno_map);
1051 VEC_free (allocno_t, heap, conflict_id_allocno_map_vec);
1052 VEC_free (allocno_t, heap, allocno_vec);
1053 free_alloc_pool (allocno_pool);
1054 free_alloc_pool (allocno_live_range_pool);
1055 }
1056
1057 \f
1058
1059 /* Pools for copies. */
1060 static alloc_pool copy_pool;
1061
1062 /* Vec containing references to all created copies. It is a
1063 container of array copies. */
1064 static VEC(copy_t,heap) *copy_vec;
1065
1066 /* The function initializes data concerning allocno copies. */
1067 static void
1068 initiate_copies (void)
1069 {
1070 copy_pool = create_alloc_pool ("copies", sizeof (struct allocno_copy), 100);
1071 copy_vec = VEC_alloc (copy_t, heap, get_max_uid ());
1072 copies = NULL;
1073 copies_num = 0;
1074 }
1075
1076 /* Return copy connecting A1 and A2 and originated from INSN of
1077 LOOP_TREE_NODE if any. */
1078 static copy_t
1079 find_allocno_copy (allocno_t a1, allocno_t a2, rtx insn,
1080 loop_tree_node_t loop_tree_node)
1081 {
1082 copy_t cp, next_cp;
1083 allocno_t another_a;
1084
1085 for (cp = ALLOCNO_COPIES (a1); cp != NULL; cp = next_cp)
1086 {
1087 if (cp->first == a1)
1088 {
1089 next_cp = cp->next_first_allocno_copy;
1090 another_a = cp->second;
1091 }
1092 else if (cp->second == a1)
1093 {
1094 next_cp = cp->next_second_allocno_copy;
1095 another_a = cp->first;
1096 }
1097 else
1098 gcc_unreachable ();
1099 if (another_a == a2 && cp->insn == insn
1100 && cp->loop_tree_node == loop_tree_node)
1101 return cp;
1102 }
1103 return NULL;
1104 }
1105
1106 /* The function creates and returns created in LOOP_TREE_NODE copy of
1107 allocnos FIRST and SECOND with frequency FREQ, insn INSN. */
1108 copy_t
1109 create_copy (allocno_t first, allocno_t second, int freq, rtx insn,
1110 loop_tree_node_t loop_tree_node)
1111 {
1112 copy_t cp;
1113
1114 cp = pool_alloc (copy_pool);
1115 cp->num = copies_num;
1116 cp->first = first;
1117 cp->second = second;
1118 cp->freq = freq;
1119 cp->insn = insn;
1120 cp->loop_tree_node = loop_tree_node;
1121 VEC_safe_push (copy_t, heap, copy_vec, cp);
1122 copies = VEC_address (copy_t, copy_vec);
1123 copies_num = VEC_length (copy_t, copy_vec);
1124 return cp;
1125 }
1126
1127 /* Attach a copy CP to allocnos involved into the copy. */
1128 void
1129 add_allocno_copy_to_list (copy_t cp)
1130 {
1131 allocno_t first = cp->first, second = cp->second;
1132
1133 cp->prev_first_allocno_copy = NULL;
1134 cp->prev_second_allocno_copy = NULL;
1135 cp->next_first_allocno_copy = ALLOCNO_COPIES (first);
1136 if (cp->next_first_allocno_copy != NULL)
1137 {
1138 if (cp->next_first_allocno_copy->first == first)
1139 cp->next_first_allocno_copy->prev_first_allocno_copy = cp;
1140 else
1141 cp->next_first_allocno_copy->prev_second_allocno_copy = cp;
1142 }
1143 cp->next_second_allocno_copy = ALLOCNO_COPIES (second);
1144 if (cp->next_second_allocno_copy != NULL)
1145 {
1146 if (cp->next_second_allocno_copy->second == second)
1147 cp->next_second_allocno_copy->prev_second_allocno_copy = cp;
1148 else
1149 cp->next_second_allocno_copy->prev_first_allocno_copy = cp;
1150 }
1151 ALLOCNO_COPIES (first) = cp;
1152 ALLOCNO_COPIES (second) = cp;
1153 }
1154
1155 /* Detach a copy CP from allocnos involved into the copy. */
1156 void
1157 remove_allocno_copy_from_list (copy_t cp)
1158 {
1159 allocno_t first = cp->first, second = cp->second;
1160 copy_t prev, next;
1161
1162 next = cp->next_first_allocno_copy;
1163 prev = cp->prev_first_allocno_copy;
1164 if (prev == NULL)
1165 ALLOCNO_COPIES (first) = next;
1166 else if (prev->first == first)
1167 prev->next_first_allocno_copy = next;
1168 else
1169 prev->next_second_allocno_copy = next;
1170 if (next != NULL)
1171 {
1172 if (next->first == first)
1173 next->prev_first_allocno_copy = prev;
1174 else
1175 next->prev_second_allocno_copy = prev;
1176 }
1177 cp->prev_first_allocno_copy = cp->next_first_allocno_copy = NULL;
1178
1179 next = cp->next_second_allocno_copy;
1180 prev = cp->prev_second_allocno_copy;
1181 if (prev == NULL)
1182 ALLOCNO_COPIES (second) = next;
1183 else if (prev->second == second)
1184 prev->next_second_allocno_copy = next;
1185 else
1186 prev->next_first_allocno_copy = next;
1187 if (next != NULL)
1188 {
1189 if (next->second == second)
1190 next->prev_second_allocno_copy = prev;
1191 else
1192 next->prev_first_allocno_copy = prev;
1193 }
1194 cp->prev_second_allocno_copy = cp->next_second_allocno_copy = NULL;
1195 }
1196
1197 /* Make a copy CP a canonical copy where number of the
1198 first allocno is less than the second one. */
1199 void
1200 swap_allocno_copy_ends_if_necessary (copy_t cp)
1201 {
1202 allocno_t temp;
1203 copy_t temp_cp;
1204
1205 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1206 return;
1207
1208 temp = cp->first;
1209 cp->first = cp->second;
1210 cp->second = temp;
1211
1212 temp_cp = cp->prev_first_allocno_copy;
1213 cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1214 cp->prev_second_allocno_copy = temp_cp;
1215
1216 temp_cp = cp->next_first_allocno_copy;
1217 cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1218 cp->next_second_allocno_copy = temp_cp;
1219 }
1220
1221 /* Create (or update frequency if the copy already exists) and return
1222 the copy of allocnos FIRST and SECOND with frequency FREQ
1223 corresponding to move insn INSN (if any) and originated from
1224 LOOP_TREE_NODE. */
1225 copy_t
1226 add_allocno_copy (allocno_t first, allocno_t second, int freq, rtx insn,
1227 loop_tree_node_t loop_tree_node)
1228 {
1229 copy_t cp;
1230
1231 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1232 {
1233 cp->freq += freq;
1234 return cp;
1235 }
1236 cp = create_copy (first, second, freq, insn, loop_tree_node);
1237 ira_assert (first != NULL && second != NULL);
1238 add_allocno_copy_to_list (cp);
1239 swap_allocno_copy_ends_if_necessary (cp);
1240 return cp;
1241 }
1242
1243 /* Print info about copies involving allocno A into file F. */
1244 static void
1245 print_allocno_copies (FILE *f, allocno_t a)
1246 {
1247 allocno_t another_a;
1248 copy_t cp, next_cp;
1249
1250 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1251 for (cp = ALLOCNO_COPIES (a); cp != NULL; cp = next_cp)
1252 {
1253 if (cp->first == a)
1254 {
1255 next_cp = cp->next_first_allocno_copy;
1256 another_a = cp->second;
1257 }
1258 else if (cp->second == a)
1259 {
1260 next_cp = cp->next_second_allocno_copy;
1261 another_a = cp->first;
1262 }
1263 else
1264 gcc_unreachable ();
1265 fprintf (f, " cp%d:a%d(r%d)@%d", cp->num,
1266 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1267 }
1268 fprintf (f, "\n");
1269 }
1270
1271 /* Print info about copies involving allocno A into stderr. */
1272 void
1273 debug_allocno_copies (allocno_t a)
1274 {
1275 print_allocno_copies (stderr, a);
1276 }
1277
1278 /* The function frees memory allocated for copy CP. */
1279 static void
1280 finish_copy (copy_t cp)
1281 {
1282 pool_free (copy_pool, cp);
1283 }
1284
1285
1286 /* Free memory allocated for all copies. */
1287 static void
1288 finish_copies (void)
1289 {
1290 copy_t cp;
1291 copy_iterator ci;
1292
1293 FOR_EACH_COPY (cp, ci)
1294 finish_copy (cp);
1295 VEC_free (copy_t, heap, copy_vec);
1296 free_alloc_pool (copy_pool);
1297 }
1298
1299 \f
1300
1301 /* Pools for cost vectors. It is defined only for cover classes. */
1302 static alloc_pool cost_vector_pool[N_REG_CLASSES];
1303
1304 /* The function initiates work with hard register cost vectors. It
1305 creates allocation pool for each cover class. */
1306 static void
1307 initiate_cost_vectors (void)
1308 {
1309 int i;
1310 enum reg_class cover_class;
1311
1312 for (i = 0; i < reg_class_cover_size; i++)
1313 {
1314 cover_class = reg_class_cover[i];
1315 cost_vector_pool[cover_class]
1316 = create_alloc_pool ("cost vectors",
1317 sizeof (int) * class_hard_regs_num[cover_class],
1318 100);
1319 }
1320 }
1321
1322 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1323 int *
1324 allocate_cost_vector (enum reg_class cover_class)
1325 {
1326 return pool_alloc (cost_vector_pool[cover_class]);
1327 }
1328
1329 /* Free a cost vector VEC for COVER_CLASS. */
1330 void
1331 free_cost_vector (int *vec, enum reg_class cover_class)
1332 {
1333 ira_assert (vec != NULL);
1334 pool_free (cost_vector_pool[cover_class], vec);
1335 }
1336
1337 /* Finish work with hard register cost vectors. Release allocation
1338 pool for each cover class. */
1339 static void
1340 finish_cost_vectors (void)
1341 {
1342 int i;
1343 enum reg_class cover_class;
1344
1345 for (i = 0; i < reg_class_cover_size; i++)
1346 {
1347 cover_class = reg_class_cover[i];
1348 free_alloc_pool (cost_vector_pool[cover_class]);
1349 }
1350 }
1351
1352 \f
1353
1354 /* The current loop tree node and its regno allocno map. */
1355 loop_tree_node_t ira_curr_loop_tree_node;
1356 allocno_t *ira_curr_regno_allocno_map;
1357
1358 /* This recursive function traverses loop tree with root LOOP_NODE
1359 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1360 correspondingly in preorder and postorder. The function sets up
1361 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1362 basic block nodes of LOOP_NODE is also processed (before its
1363 subloop nodes). */
1364 void
1365 traverse_loop_tree (bool bb_p, loop_tree_node_t loop_node,
1366 void (*preorder_func) (loop_tree_node_t),
1367 void (*postorder_func) (loop_tree_node_t))
1368 {
1369 loop_tree_node_t subloop_node;
1370
1371 ira_assert (loop_node->bb == NULL);
1372 ira_curr_loop_tree_node = loop_node;
1373 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1374
1375 if (preorder_func != NULL)
1376 (*preorder_func) (loop_node);
1377
1378 if (bb_p)
1379 for (subloop_node = loop_node->children;
1380 subloop_node != NULL;
1381 subloop_node = subloop_node->next)
1382 if (subloop_node->bb != NULL)
1383 {
1384 if (preorder_func != NULL)
1385 (*preorder_func) (subloop_node);
1386
1387 if (postorder_func != NULL)
1388 (*postorder_func) (subloop_node);
1389 }
1390
1391 for (subloop_node = loop_node->subloops;
1392 subloop_node != NULL;
1393 subloop_node = subloop_node->subloop_next)
1394 {
1395 ira_assert (subloop_node->bb == NULL);
1396 traverse_loop_tree (bb_p, subloop_node,
1397 preorder_func, postorder_func);
1398 }
1399
1400 ira_curr_loop_tree_node = loop_node;
1401 ira_curr_regno_allocno_map = ira_curr_loop_tree_node->regno_allocno_map;
1402
1403 if (postorder_func != NULL)
1404 (*postorder_func) (loop_node);
1405 }
1406
1407 \f
1408
1409 /* The basic block currently being processed. */
1410 static basic_block curr_bb;
1411
1412 /* This recursive function creates allocnos corresponding to
1413 pseudo-registers containing in X. True OUTPUT_P means that X is
1414 a lvalue. */
1415 static void
1416 create_insn_allocnos (rtx x, bool output_p)
1417 {
1418 int i, j;
1419 const char *fmt;
1420 enum rtx_code code = GET_CODE (x);
1421
1422 if (code == REG)
1423 {
1424 int regno;
1425
1426 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1427 {
1428 allocno_t a;
1429
1430 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1431 a = create_allocno (regno, false, ira_curr_loop_tree_node);
1432
1433 ALLOCNO_NREFS (a)++;
1434 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1435 bitmap_set_bit (ira_curr_loop_tree_node->mentioned_allocnos,
1436 ALLOCNO_NUM (a));
1437 if (output_p)
1438 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1439 }
1440 return;
1441 }
1442 else if (code == SET)
1443 {
1444 create_insn_allocnos (SET_DEST (x), true);
1445 create_insn_allocnos (SET_SRC (x), false);
1446 return;
1447 }
1448 else if (code == CLOBBER)
1449 {
1450 create_insn_allocnos (XEXP (x, 0), true);
1451 return;
1452 }
1453 else if (code == MEM)
1454 {
1455 create_insn_allocnos (XEXP (x, 0), false);
1456 return;
1457 }
1458 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1459 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1460 {
1461 create_insn_allocnos (XEXP (x, 0), true);
1462 create_insn_allocnos (XEXP (x, 0), false);
1463 return;
1464 }
1465
1466 fmt = GET_RTX_FORMAT (code);
1467 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1468 {
1469 if (fmt[i] == 'e')
1470 create_insn_allocnos (XEXP (x, i), output_p);
1471 else if (fmt[i] == 'E')
1472 for (j = 0; j < XVECLEN (x, i); j++)
1473 create_insn_allocnos (XVECEXP (x, i, j), output_p);
1474 }
1475 }
1476
1477 /* Create allocnos corresponding to pseudo-registers living in the
1478 basic block represented by the corresponding loop tree node
1479 BB_NODE. */
1480 static void
1481 create_bb_allocnos (loop_tree_node_t bb_node)
1482 {
1483 basic_block bb;
1484 rtx insn;
1485 unsigned int i;
1486 bitmap_iterator bi;
1487
1488 curr_bb = bb = bb_node->bb;
1489 ira_assert (bb != NULL);
1490 FOR_BB_INSNS (bb, insn)
1491 if (INSN_P (insn))
1492 create_insn_allocnos (PATTERN (insn), false);
1493 /* It might be a allocno living through from one subloop to
1494 another. */
1495 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi)
1496 if (ira_curr_regno_allocno_map[i] == NULL)
1497 create_allocno (i, false, ira_curr_loop_tree_node);
1498 }
1499
1500 /* Create allocnos corresponding to pseudo-registers living on edge E
1501 (a loop entry or exit). Also mark the allocnos as living on the
1502 loop border. */
1503 static void
1504 create_loop_allocnos (edge e)
1505 {
1506 unsigned int i;
1507 bitmap live_in_regs, border_allocnos;
1508 bitmap_iterator bi;
1509
1510 live_in_regs = DF_LR_IN (e->dest);
1511 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1512 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src),
1513 FIRST_PSEUDO_REGISTER, i, bi)
1514 if (bitmap_bit_p (live_in_regs, i))
1515 {
1516 if (ira_curr_regno_allocno_map[i] == NULL)
1517 create_allocno (i, false, ira_curr_loop_tree_node);
1518 bitmap_set_bit (border_allocnos,
1519 ALLOCNO_NUM (ira_curr_regno_allocno_map[i]));
1520 }
1521 }
1522
1523 /* Create allocnos corresponding to pseudo-registers living in loop
1524 represented by the corresponding loop tree node LOOP_NODE. This
1525 function is called by traverse_loop_tree. */
1526 static void
1527 create_loop_tree_node_allocnos (loop_tree_node_t loop_node)
1528 {
1529 if (loop_node->bb != NULL)
1530 create_bb_allocnos (loop_node);
1531 else if (loop_node != ira_loop_tree_root)
1532 {
1533 int i;
1534 edge_iterator ei;
1535 edge e;
1536 VEC (edge, heap) *edges;
1537
1538 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1539 if (e->src != loop_node->loop->latch)
1540 create_loop_allocnos (e);
1541
1542 edges = get_loop_exit_edges (loop_node->loop);
1543 for (i = 0; VEC_iterate (edge, edges, i, e); i++)
1544 create_loop_allocnos (e);
1545 VEC_free (edge, heap, edges);
1546 }
1547 }
1548
1549 /* Create allocnos corresponding to pseudo-registers in the current
1550 function. Traverse the loop tree for this. */
1551 static void
1552 create_allocnos (void)
1553 {
1554 int i;
1555 allocno_t a, parent_a;
1556 loop_tree_node_t parent;
1557
1558 /* We need to process BB first to correctly link allocnos by member
1559 next_regno_allocno. */
1560 traverse_loop_tree (true, ira_loop_tree_root,
1561 create_loop_tree_node_allocnos, NULL);
1562 if (flag_ira_algorithm != IRA_ALGORITHM_REGIONAL
1563 && flag_ira_algorithm != IRA_ALGORITHM_MIXED)
1564 return;
1565 /* Propagate number of references and frequencies for regional
1566 register allocation. */
1567 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1568 for (a = regno_allocno_map[i];
1569 a != NULL;
1570 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1571 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) != NULL
1572 && (parent_a = parent->regno_allocno_map[i]) != NULL)
1573 {
1574 ALLOCNO_NREFS (parent_a) += ALLOCNO_NREFS (a);
1575 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1576 }
1577 }
1578
1579 \f
1580
1581 /* Set up minimal and maximal live range points for allocnos. */
1582 static void
1583 setup_min_max_allocno_live_range_point (void)
1584 {
1585 int i;
1586 allocno_t a, parent_a, cap;
1587 allocno_iterator ai;
1588 allocno_live_range_t r;
1589 loop_tree_node_t parent;
1590
1591 FOR_EACH_ALLOCNO (a, ai)
1592 {
1593 r = ALLOCNO_LIVE_RANGES (a);
1594 if (r == NULL)
1595 continue;
1596 ALLOCNO_MAX (a) = r->finish;
1597 for (; r->next != NULL; r = r->next)
1598 ;
1599 ALLOCNO_MIN (a) = r->start;
1600 }
1601 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1602 for (a = regno_allocno_map[i];
1603 a != NULL;
1604 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1605 {
1606 if (ALLOCNO_MAX (a) < 0)
1607 continue;
1608 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
1609 /* Accumulation of range info. */
1610 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1611 || (parent_a = parent->regno_allocno_map[i]) == NULL)
1612 {
1613 for (cap = ALLOCNO_CAP (a); cap != NULL; cap = ALLOCNO_CAP (cap))
1614 {
1615 if (ALLOCNO_MAX (cap) < ALLOCNO_MAX (a))
1616 ALLOCNO_MAX (cap) = ALLOCNO_MAX (a);
1617 if (ALLOCNO_MIN (cap) > ALLOCNO_MIN (a))
1618 ALLOCNO_MIN (cap) = ALLOCNO_MIN (a);
1619 }
1620 continue;
1621 }
1622 if (ALLOCNO_MAX (parent_a) < ALLOCNO_MAX (a))
1623 ALLOCNO_MAX (parent_a) = ALLOCNO_MAX (a);
1624 if (ALLOCNO_MIN (parent_a) > ALLOCNO_MIN (a))
1625 ALLOCNO_MIN (parent_a) = ALLOCNO_MIN (a);
1626 }
1627 #ifdef ENABLE_IRA_CHECKING
1628 FOR_EACH_ALLOCNO (a, ai)
1629 {
1630 if ((0 <= ALLOCNO_MIN (a) && ALLOCNO_MIN (a) <= max_point)
1631 && (0 <= ALLOCNO_MAX (a) && ALLOCNO_MAX (a) <= max_point))
1632 continue;
1633 gcc_unreachable ();
1634 }
1635 #endif
1636 }
1637
1638 /* Sort allocnos according to their live ranges. Allocnos with
1639 smaller cover class are put first. Allocnos with the same cove
1640 class are ordered according their start (min). Allocnos with the
1641 same start are ordered according their finish (max). */
1642 static int
1643 allocno_range_compare_func (const void *v1p, const void *v2p)
1644 {
1645 int diff;
1646 allocno_t a1 = *(const allocno_t *) v1p, a2 = *(const allocno_t *) v2p;
1647
1648 if ((diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
1649 return diff;
1650 if ((diff = ALLOCNO_MIN (a1) - ALLOCNO_MIN (a2)) != 0)
1651 return diff;
1652 if ((diff = ALLOCNO_MAX (a1) - ALLOCNO_MAX (a2)) != 0)
1653 return diff;
1654 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
1655 }
1656
1657 /* Sort conflict_id_allocno_map and set up conflict id of
1658 allocnos. */
1659 static void
1660 sort_conflict_id_allocno_map (void)
1661 {
1662 int i, num;
1663 allocno_t a;
1664 allocno_iterator ai;
1665
1666 num = 0;
1667 FOR_EACH_ALLOCNO (a, ai)
1668 conflict_id_allocno_map[num++] = a;
1669 qsort (conflict_id_allocno_map, num, sizeof (allocno_t),
1670 allocno_range_compare_func);
1671 for (i = 0; i < num; i++)
1672 if ((a = conflict_id_allocno_map[i]) != NULL)
1673 ALLOCNO_CONFLICT_ID (a) = i;
1674 for (i = num; i < allocnos_num; i++)
1675 conflict_id_allocno_map[i] = NULL;
1676 }
1677
1678 /* Set up minimal and maximal conflict ids of allocnos with which
1679 given allocno can conflict. */
1680 static void
1681 setup_min_max_conflict_allocno_ids (void)
1682 {
1683 enum reg_class cover_class;
1684 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
1685 int *live_range_min, *last_lived;
1686 allocno_t a;
1687
1688 live_range_min = ira_allocate (sizeof (int) * allocnos_num);
1689 cover_class = -1;
1690 first_not_finished = -1;
1691 for (i = 0; i < allocnos_num; i++)
1692 {
1693 a = conflict_id_allocno_map[i];
1694 if (a == NULL)
1695 continue;
1696 if (cover_class != ALLOCNO_COVER_CLASS (a))
1697 {
1698 cover_class = ALLOCNO_COVER_CLASS (a);
1699 min = i;
1700 first_not_finished = i;
1701 }
1702 else
1703 {
1704 start = ALLOCNO_MIN (a);
1705 /* If we skip an allocno, the allocno with smaller ids will
1706 be also skipped because of the secondary sorting the
1707 range finishes (see function
1708 allocno_range_compare_func). */
1709 while (first_not_finished < i
1710 && start
1711 > ALLOCNO_MAX (conflict_id_allocno_map[first_not_finished]))
1712 first_not_finished++;
1713 min = first_not_finished;
1714 }
1715 if (min == i)
1716 /* We could increase min further in this case but it is good
1717 enough. */
1718 min++;
1719 live_range_min[i] = ALLOCNO_MIN (a);
1720 ALLOCNO_MIN (a) = min;
1721 }
1722 last_lived = ira_allocate (sizeof (int) * max_point);
1723 cover_class = -1;
1724 filled_area_start = -1;
1725 for (i = allocnos_num - 1; i >= 0; i--)
1726 {
1727 a = conflict_id_allocno_map[i];
1728 if (a == NULL)
1729 continue;
1730 if (cover_class != ALLOCNO_COVER_CLASS (a))
1731 {
1732 cover_class = ALLOCNO_COVER_CLASS (a);
1733 for (j = 0; j < max_point; j++)
1734 last_lived[j] = -1;
1735 filled_area_start = max_point;
1736 }
1737 min = live_range_min[i];
1738 finish = ALLOCNO_MAX (a);
1739 max = last_lived[finish];
1740 if (max < 0)
1741 /* We could decrease max further in this case but it is good
1742 enough. */
1743 max = ALLOCNO_CONFLICT_ID (a) - 1;
1744 ALLOCNO_MAX (a) = max;
1745 /* In filling, we can go further A range finish to recognize
1746 intersection quickly because if the finish of subsequently
1747 processed allocno (it has smaller conflict id) range is
1748 further A range finish than they are definitely intersected
1749 (the reason for this is the allocnos with bigger conflict id
1750 have their range starts not smaller than allocnos with
1751 smaller ids. */
1752 for (j = min; j < filled_area_start; j++)
1753 last_lived[j] = i;
1754 filled_area_start = min;
1755 }
1756 ira_free (last_lived);
1757 ira_free (live_range_min);
1758 }
1759
1760 \f
1761
1762 /* Create caps representing allocnos living only inside the loop given
1763 by LOOP_NODE on higher loop level. */
1764 static void
1765 create_loop_tree_node_caps (loop_tree_node_t loop_node)
1766 {
1767 unsigned int i;
1768 bitmap_iterator bi;
1769 loop_tree_node_t parent;
1770
1771 if (loop_node == ira_loop_tree_root)
1772 return;
1773 ira_assert (loop_node->bb == NULL);
1774 bitmap_and_compl (allocnos_bitmap, loop_node->mentioned_allocnos,
1775 loop_node->border_allocnos);
1776 parent = loop_node->parent;
1777 EXECUTE_IF_SET_IN_BITMAP (allocnos_bitmap, 0, i, bi)
1778 if (parent->regno_allocno_map[ALLOCNO_REGNO (allocnos[i])] == NULL)
1779 create_cap_allocno (allocnos[i]);
1780 }
1781
1782 /* Propagate info (not available at the cap creation time) to caps
1783 mentioned in LOOP_NODE. */
1784 static void
1785 propagate_info_to_loop_tree_node_caps (loop_tree_node_t loop_node)
1786 {
1787 unsigned int i;
1788 bitmap_iterator bi;
1789 allocno_t a;
1790
1791 ira_assert (loop_node->bb == NULL);
1792 EXECUTE_IF_SET_IN_BITMAP (loop_node->mentioned_allocnos, 0, i, bi)
1793 {
1794 a = allocnos[i];
1795 if (ALLOCNO_CAP_MEMBER (a) != NULL)
1796 propagate_info_to_cap (a);
1797 }
1798 }
1799
1800 \f
1801
1802 /* The page contains code transforming more one region internal
1803 representation (IR) to one region IR which is necessary for reload.
1804 This transformation is called IR flattening. We might just rebuild
1805 the IR for one region but we don't do it because it takes a lot of
1806 time. */
1807
1808 /* Merge ranges R1 and R2 and returns the result. The function
1809 maintains the order of ranges and tries to minimize number of the
1810 result ranges. */
1811 static allocno_live_range_t
1812 merge_ranges (allocno_live_range_t r1, allocno_live_range_t r2)
1813 {
1814 allocno_live_range_t first, last, temp;
1815
1816 if (r1 == NULL)
1817 return r2;
1818 if (r2 == NULL)
1819 return r1;
1820 for (first = last = NULL; r1 != NULL && r2 != NULL;)
1821 {
1822 if (r1->start < r2->start)
1823 {
1824 temp = r1;
1825 r1 = r2;
1826 r2 = temp;
1827 }
1828 if (r1->start <= r2->finish + 1)
1829 {
1830 /* Intersected ranges: merge r1 and r2 into r1. */
1831 r1->start = r2->start;
1832 if (r1->finish < r2->finish)
1833 r1->finish = r2->finish;
1834 temp = r2;
1835 r2 = r2->next;
1836 finish_allocno_live_range (temp);
1837 if (r2 == NULL)
1838 {
1839 /* To try to merge with subsequent ranges in r1. */
1840 r2 = r1->next;
1841 r1->next = NULL;
1842 }
1843 }
1844 else
1845 {
1846 /* Add r1 to the result. */
1847 if (first == NULL)
1848 first = last = r1;
1849 else
1850 {
1851 last->next = r1;
1852 last = r1;
1853 }
1854 r1 = r1->next;
1855 if (r1 == NULL)
1856 {
1857 /* To try to merge with subsequent ranges in r2. */
1858 r1 = r2->next;
1859 r2->next = NULL;
1860 }
1861 }
1862 }
1863 if (r1 != NULL)
1864 {
1865 if (first == NULL)
1866 first = r1;
1867 else
1868 last->next = r1;
1869 ira_assert (r1->next == NULL);
1870 }
1871 else if (r2 != NULL)
1872 {
1873 if (first == NULL)
1874 first = r2;
1875 else
1876 last->next = r2;
1877 ira_assert (r2->next == NULL);
1878 }
1879 else
1880 {
1881 ira_assert (last->next == NULL);
1882 }
1883 return first;
1884 }
1885
1886 /* This recursive function returns immediate common dominator of two
1887 loop tree nodes N1 and N2. */
1888 static loop_tree_node_t
1889 common_loop_tree_node_dominator (loop_tree_node_t n1, loop_tree_node_t n2)
1890 {
1891 ira_assert (n1 != NULL && n2 != NULL);
1892 if (n1 == n2)
1893 return n1;
1894 if (n1->level < n2->level)
1895 return common_loop_tree_node_dominator (n1, n2->parent);
1896 else if (n1->level > n2->level)
1897 return common_loop_tree_node_dominator (n1->parent, n2);
1898 else
1899 return common_loop_tree_node_dominator (n1->parent, n2->parent);
1900 }
1901
1902 /* The function changes allocno in range list given by R onto A. */
1903 static void
1904 change_allocno_in_range_list (allocno_live_range_t r, allocno_t a)
1905 {
1906 for (; r != NULL; r = r->next)
1907 r->allocno = a;
1908 }
1909
1910 /* Flatten the IR. In other words, this function transforms IR as if
1911 it were built with one region (without loops). We could make it
1912 much simpler by rebuilding IR with one region, but unfortunately it
1913 takes a lot of time. MAX_REGNO_BEFORE_EMIT and
1914 MAX_POINT_BEFORE_EMIT are correspondingly MAX_REG_NUM () and
1915 MAX_POINT before emitting insns on the loop borders. */
1916 void
1917 ira_flattening (int max_regno_before_emit, int max_point_before_emit)
1918 {
1919 int i, j, num;
1920 bool propagate_p, stop_p, keep_p;
1921 int hard_regs_num;
1922 bool new_allocnos_p, renamed_p, merged_p;
1923 unsigned int n;
1924 enum reg_class cover_class;
1925 rtx call, *allocno_calls;
1926 allocno_t a, parent_a, first, second, node_first, node_second;
1927 allocno_t dominator_a;
1928 copy_t cp;
1929 loop_tree_node_t parent, node, dominator;
1930 allocno_live_range_t r;
1931 allocno_iterator ai;
1932 copy_iterator ci;
1933 sparseset allocnos_live;
1934 /* Map: regno -> allocnos which will finally represent the regno for
1935 IR with one region. */
1936 allocno_t *regno_top_level_allocno_map;
1937 bool *allocno_propagated_p;
1938
1939 regno_top_level_allocno_map
1940 = ira_allocate (max_reg_num () * sizeof (allocno_t));
1941 memset (regno_top_level_allocno_map, 0, max_reg_num () * sizeof (allocno_t));
1942 allocno_propagated_p = ira_allocate (allocnos_num * sizeof (bool));
1943 memset (allocno_propagated_p, 0, allocnos_num * sizeof (bool));
1944 expand_calls ();
1945 new_allocnos_p = renamed_p = merged_p = false;
1946 /* Fix final allocno attributes. */
1947 for (i = max_regno_before_emit - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1948 {
1949 propagate_p = false;
1950 for (a = regno_allocno_map[i];
1951 a != NULL;
1952 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
1953 {
1954 if (ALLOCNO_CAP_MEMBER (a) != NULL)
1955 continue;
1956 if (ALLOCNO_SOMEWHERE_RENAMED_P (a))
1957 renamed_p = true;
1958 if ((unsigned int) ALLOCNO_REGNO (a) != REGNO (ALLOCNO_REG (a))
1959 && ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
1960 {
1961 allocno_calls = (VEC_address (rtx,
1962 regno_calls[ALLOCNO_REGNO (a)])
1963 + ALLOCNO_CALLS_CROSSED_START (a));
1964 for (j = ALLOCNO_CALLS_CROSSED_NUM (a) - 1; j >= 0; j--)
1965 {
1966 call = allocno_calls[j];
1967 if (call == NULL_RTX)
1968 continue;
1969 add_regno_call (REGNO (ALLOCNO_REG (a)), call);
1970 allocno_calls[j] = NULL_RTX;
1971 }
1972 }
1973 if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1974 || ((parent_a = parent->regno_allocno_map[ALLOCNO_REGNO (a)])
1975 == NULL))
1976 {
1977 ALLOCNO_COPIES (a) = NULL;
1978 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
1979 continue;
1980 }
1981 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
1982 if (propagate_p)
1983 {
1984 if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
1985 COPY_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1986 ALLOCNO_CONFLICT_HARD_REGS (parent_a));
1987 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (parent_a),
1988 ALLOCNO_TOTAL_CONFLICT_HARD_REGS (a));
1989 #ifdef STACK_REGS
1990 if (!allocno_propagated_p [ALLOCNO_NUM (parent_a)])
1991 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
1992 = ALLOCNO_NO_STACK_REG_P (parent_a);
1993 ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
1994 = (ALLOCNO_TOTAL_NO_STACK_REG_P (parent_a)
1995 || ALLOCNO_TOTAL_NO_STACK_REG_P (a));
1996 #endif
1997 allocno_propagated_p [ALLOCNO_NUM (parent_a)] = true;
1998 }
1999 if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a)))
2000 {
2001 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2002 {
2003 fprintf (ira_dump_file,
2004 " Moving ranges of a%dr%d to a%dr%d: ",
2005 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)),
2006 ALLOCNO_NUM (parent_a),
2007 REGNO (ALLOCNO_REG (parent_a)));
2008 print_live_range_list (ira_dump_file,
2009 ALLOCNO_LIVE_RANGES (a));
2010 }
2011 change_allocno_in_range_list (ALLOCNO_LIVE_RANGES (a), parent_a);
2012 ALLOCNO_LIVE_RANGES (parent_a)
2013 = merge_ranges (ALLOCNO_LIVE_RANGES (a),
2014 ALLOCNO_LIVE_RANGES (parent_a));
2015 merged_p = true;
2016 ALLOCNO_LIVE_RANGES (a) = NULL;
2017 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2018 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a)
2019 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a));
2020 continue;
2021 }
2022 new_allocnos_p = true;
2023 propagate_p = true;
2024 first = ALLOCNO_MEM_OPTIMIZED_DEST (a) == NULL ? NULL : a;
2025 for (;;)
2026 {
2027 if (first == NULL
2028 && ALLOCNO_MEM_OPTIMIZED_DEST (parent_a) != NULL)
2029 first = parent_a;
2030 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2031 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2032 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2033 cover_class = ALLOCNO_COVER_CLASS (parent_a);
2034 hard_regs_num = class_hard_regs_num[cover_class];
2035 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2036 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2037 for (j = 0; j < hard_regs_num; j++)
2038 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2039 -= ALLOCNO_HARD_REG_COSTS (a)[j];
2040 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2041 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2042 for (j = 0; j < hard_regs_num; j++)
2043 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2044 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2045 ALLOCNO_COVER_CLASS_COST (parent_a)
2046 -= ALLOCNO_COVER_CLASS_COST (a);
2047 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2048 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2049 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2050 if ((parent = ALLOCNO_LOOP_TREE_NODE (parent_a)->parent) == NULL
2051 || (parent_a = (parent->regno_allocno_map
2052 [ALLOCNO_REGNO (parent_a)])) == NULL)
2053 break;
2054 }
2055 if (first != NULL)
2056 {
2057 parent_a = ALLOCNO_MEM_OPTIMIZED_DEST (first);
2058 dominator = common_loop_tree_node_dominator
2059 (ALLOCNO_LOOP_TREE_NODE (parent_a),
2060 ALLOCNO_LOOP_TREE_NODE (first));
2061 dominator_a = dominator->regno_allocno_map[ALLOCNO_REGNO (a)];
2062 ira_assert (parent_a != NULL);
2063 stop_p = first != a;
2064 /* Remember that exit can be to a grandparent (not only
2065 to a parent) or a child of the grandparent. */
2066 for (first = a;;)
2067 {
2068 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2069 {
2070 fprintf
2071 (ira_dump_file,
2072 " Coping ranges of a%dr%d to a%dr%d: ",
2073 ALLOCNO_NUM (first), REGNO (ALLOCNO_REG (first)),
2074 ALLOCNO_NUM (parent_a),
2075 REGNO (ALLOCNO_REG (parent_a)));
2076 print_live_range_list (ira_dump_file,
2077 ALLOCNO_LIVE_RANGES (first));
2078 }
2079 r = copy_allocno_live_range_list (ALLOCNO_LIVE_RANGES
2080 (first));
2081 change_allocno_in_range_list (r, parent_a);
2082 ALLOCNO_LIVE_RANGES (parent_a)
2083 = merge_ranges (r, ALLOCNO_LIVE_RANGES (parent_a));
2084 merged_p = true;
2085 if (stop_p)
2086 break;
2087 parent = ALLOCNO_LOOP_TREE_NODE (first)->parent;
2088 ira_assert (parent != NULL);
2089 first = parent->regno_allocno_map[ALLOCNO_REGNO (a)];
2090 ira_assert (first != NULL);
2091 if (first == dominator_a)
2092 break;
2093 }
2094 }
2095 ALLOCNO_COPIES (a) = NULL;
2096 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a;
2097 }
2098 }
2099 ira_free (allocno_propagated_p);
2100 ira_assert (new_allocnos_p || renamed_p
2101 || max_point_before_emit == max_point);
2102 if (new_allocnos_p)
2103 {
2104 /* Fix final allocnos attributes concerning calls. */
2105 compress_calls ();
2106 FOR_EACH_ALLOCNO (a, ai)
2107 {
2108 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2109 || ALLOCNO_CAP_MEMBER (a) != NULL)
2110 continue;
2111 ALLOCNO_CALLS_CROSSED_START (a) = 0;
2112 ALLOCNO_CALLS_CROSSED_NUM (a)
2113 = VEC_length (rtx, regno_calls[REGNO (ALLOCNO_REG (a))]);
2114 }
2115 }
2116 if (merged_p || max_point_before_emit != max_point)
2117 rebuild_start_finish_chains ();
2118 /* We should rebuild conflicts even if there are no new allocnos in
2119 situation when a pseudo used locally in loops and locally in the
2120 subloop because some allocnos are in conflict with the subloop
2121 allocno and they finally should be in conflict with the loop
2122 allocno. */
2123 if (new_allocnos_p || renamed_p)
2124 {
2125 /* Rebuild conflicts. */
2126 FOR_EACH_ALLOCNO (a, ai)
2127 {
2128 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2129 || ALLOCNO_CAP_MEMBER (a) != NULL)
2130 continue;
2131 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2132 ira_assert (r->allocno == a);
2133 clear_allocno_conflicts (a);
2134 }
2135 allocnos_live = sparseset_alloc (allocnos_num);
2136 for (i = 0; i < max_point; i++)
2137 {
2138 for (r = start_point_ranges[i]; r != NULL; r = r->start_next)
2139 {
2140 a = r->allocno;
2141 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2142 || ALLOCNO_CAP_MEMBER (a) != NULL)
2143 continue;
2144 num = ALLOCNO_NUM (a);
2145 cover_class = ALLOCNO_COVER_CLASS (a);
2146 sparseset_set_bit (allocnos_live, num);
2147 EXECUTE_IF_SET_IN_SPARSESET (allocnos_live, n)
2148 {
2149 allocno_t live_a = allocnos[n];
2150
2151 if (cover_class == ALLOCNO_COVER_CLASS (live_a)
2152 /* Don't set up conflict for the allocno with itself. */
2153 && num != (int) n)
2154 add_allocno_conflict (a, live_a);
2155 }
2156 }
2157
2158 for (r = finish_point_ranges[i]; r != NULL; r = r->finish_next)
2159 sparseset_clear_bit (allocnos_live, ALLOCNO_NUM (r->allocno));
2160 }
2161 sparseset_free (allocnos_live);
2162 compress_conflict_vecs ();
2163 }
2164 /* Mark some copies for removing and change allocnos in the rest
2165 copies. */
2166 FOR_EACH_COPY (cp, ci)
2167 {
2168 if (ALLOCNO_CAP_MEMBER (cp->first) != NULL
2169 || ALLOCNO_CAP_MEMBER (cp->second) != NULL)
2170 {
2171 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2172 fprintf
2173 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2174 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2175 ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)),
2176 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2177 ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second)));
2178 cp->loop_tree_node = NULL;
2179 continue;
2180 }
2181 first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))];
2182 second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))];
2183 node = cp->loop_tree_node;
2184 if (node == NULL)
2185 keep_p = true; /* It copy generated in ira-emit.c. */
2186 else
2187 {
2188 /* Check that the copy was not propagated from level on
2189 which we will have different pseudos. */
2190 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2191 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2192 keep_p = ((REGNO (ALLOCNO_REG (first))
2193 == REGNO (ALLOCNO_REG (node_first)))
2194 && (REGNO (ALLOCNO_REG (second))
2195 == REGNO (ALLOCNO_REG (node_second))));
2196 }
2197 if (keep_p)
2198 {
2199 cp->loop_tree_node = ira_loop_tree_root;
2200 cp->first = first;
2201 cp->second = second;
2202 }
2203 else
2204 {
2205 cp->loop_tree_node = NULL;
2206 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2207 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
2208 cp->num, ALLOCNO_NUM (cp->first),
2209 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second),
2210 REGNO (ALLOCNO_REG (cp->second)));
2211 }
2212 }
2213 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2214 FOR_EACH_ALLOCNO (a, ai)
2215 {
2216 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]
2217 || ALLOCNO_CAP_MEMBER (a) != NULL)
2218 {
2219 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2220 fprintf (ira_dump_file, " Remove a%dr%d\n",
2221 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a)));
2222 finish_allocno (a);
2223 continue;
2224 }
2225 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2226 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a));
2227 ALLOCNO_CAP (a) = NULL;
2228 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2229 if (! ALLOCNO_ASSIGNED_P (a))
2230 free_allocno_updated_costs (a);
2231 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2232 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2233 }
2234 /* Remove unnecessary copies. */
2235 FOR_EACH_COPY (cp, ci)
2236 {
2237 if (cp->loop_tree_node == NULL)
2238 {
2239 copies[cp->num] = NULL;
2240 finish_copy (cp);
2241 continue;
2242 }
2243 ira_assert
2244 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2245 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2246 add_allocno_copy_to_list (cp);
2247 swap_allocno_copy_ends_if_necessary (cp);
2248 }
2249 rebuild_regno_allocno_maps ();
2250 ira_free (regno_top_level_allocno_map);
2251 }
2252
2253 \f
2254
2255 #if 0
2256
2257 static int all_loops = 0, high_pressure_loops = 0;
2258
2259 static void
2260 calculate_high_pressure_loops (loop_tree_node_t loop_node,
2261 int *all_loops, int *high_pressure_loops)
2262 {
2263 loop_tree_node_t subloop_node;
2264 int i;
2265 enum reg_class class;
2266
2267 (*all_loops)++;
2268 for (i = 0; i < reg_class_cover_size; i++)
2269 {
2270 class = reg_class_cover[i];
2271 if (loop_node->reg_pressure[class] > available_class_regs[class]
2272 || (loop_node->parent != NULL
2273 && loop_node->parent->reg_pressure[class] > available_class_regs[class]))
2274 break;
2275 }
2276 if (i < reg_class_cover_size)
2277 (*high_pressure_loops)++;
2278 for (subloop_node = loop_node->subloops;
2279 subloop_node != NULL;
2280 subloop_node = subloop_node->subloop_next)
2281 {
2282 ira_assert (subloop_node->bb == NULL);
2283 calculate_high_pressure_loops (subloop_node,
2284 all_loops, high_pressure_loops);
2285 }
2286 }
2287 #endif
2288
2289 /* Create a internal representation (IR) for IRA (allocnos, copies,
2290 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to
2291 the loops (except the root which corresponds the all function) and
2292 correspondingly allocnos for the loops will be not created. Such
2293 parameter value is used for Chaitin-Briggs coloring. The function
2294 returns TRUE if we generate loop structure (besides nodes
2295 representing all function and the basic blocks) for regional
2296 allocation. A true return means that we really need to flatten IR
2297 before the reload. */
2298 bool
2299 ira_build (bool loops_p)
2300 {
2301 unsigned int i;
2302 loop_p loop;
2303
2304 df_analyze ();
2305
2306 allocnos_bitmap = ira_allocate_bitmap ();
2307 CLEAR_HARD_REG_SET (crtl->emit.call_used_regs);
2308 initiate_calls ();
2309 initiate_cost_vectors ();
2310 initiate_allocnos ();
2311 initiate_copies ();
2312 create_loop_tree_nodes (loops_p);
2313 form_loop_tree ();
2314 create_allocnos ();
2315 ira_costs ();
2316 create_allocno_live_ranges ();
2317
2318 if (optimize && (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
2319 || flag_ira_algorithm == IRA_ALGORITHM_MIXED))
2320 {
2321 bitmap_clear (allocnos_bitmap);
2322 traverse_loop_tree (false, ira_loop_tree_root, NULL,
2323 create_loop_tree_node_caps);
2324 }
2325 setup_min_max_allocno_live_range_point ();
2326 sort_conflict_id_allocno_map ();
2327 setup_min_max_conflict_allocno_ids ();
2328 ira_build_conflicts ();
2329 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
2330 {
2331 int n, nr;
2332 allocno_t a;
2333 allocno_live_range_t r;
2334 allocno_iterator ai;
2335
2336 n = 0;
2337 FOR_EACH_ALLOCNO (a, ai)
2338 n += ALLOCNO_CONFLICT_ALLOCNOS_NUM (a);
2339 nr = 0;
2340 FOR_EACH_ALLOCNO (a, ai)
2341 for (r = ALLOCNO_LIVE_RANGES (a); r != NULL; r = r->next)
2342 nr++;
2343 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
2344 VEC_length (loop_p, ira_loops.larray), n_basic_blocks,
2345 max_point);
2346 fprintf (ira_dump_file,
2347 " allocnos=%d, copies=%d, conflicts=%d, ranges=%d\n",
2348 allocnos_num, copies_num, n, nr);
2349 }
2350 if (optimize)
2351 {
2352 if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
2353 || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
2354 traverse_loop_tree (false, ira_loop_tree_root, NULL,
2355 propagate_info_to_loop_tree_node_caps);
2356 tune_allocno_costs_and_cover_classes ();
2357 if (flag_ira_algorithm == IRA_ALGORITHM_REGIONAL
2358 || flag_ira_algorithm == IRA_ALGORITHM_MIXED)
2359 {
2360 for (i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
2361 if (ira_loop_nodes[i].regno_allocno_map != NULL
2362 && ira_loop_tree_root != &ira_loop_nodes[i])
2363 return true;
2364 }
2365 }
2366 return false;
2367 }
2368
2369 /* Release the data created by function ira_build. */
2370 void
2371 ira_destroy (void)
2372 {
2373 finish_loop_tree_nodes ();
2374 finish_copies ();
2375 finish_allocnos ();
2376 finish_calls ();
2377 finish_cost_vectors ();
2378 finish_allocno_live_ranges ();
2379 ira_free_bitmap (allocnos_bitmap);
2380 }
Mirror of the offical gcc git repository hosted at gcc.gnu.org