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