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