comparison gcc/ira-build.c @ 16:04ced10e8804

gcc 7
author kono
date Fri, 27 Oct 2017 22:46:09 +0900
parents f6334be47118
children 84e7813d76e9
comparison
equal deleted inserted replaced
15:561a7518be6b 16:04ced10e8804
1 /* Building internal representation for IRA. 1 /* Building internal representation for IRA.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010 2 Copyright (C) 2006-2017 Free Software Foundation, Inc.
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>. 3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 4
6 This file is part of GCC. 5 This file is part of GCC.
7 6
8 GCC is free software; you can redistribute it and/or modify it under 7 GCC is free software; you can redistribute it and/or modify it under
20 <http://www.gnu.org/licenses/>. */ 19 <http://www.gnu.org/licenses/>. */
21 20
22 #include "config.h" 21 #include "config.h"
23 #include "system.h" 22 #include "system.h"
24 #include "coretypes.h" 23 #include "coretypes.h"
25 #include "tm.h" 24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h" 26 #include "rtl.h"
27 #include "tm_p.h" 27 #include "predict.h"
28 #include "target.h" 28 #include "df.h"
29 #include "insn-config.h"
29 #include "regs.h" 30 #include "regs.h"
30 #include "flags.h" 31 #include "memmodel.h"
31 #include "hard-reg-set.h" 32 #include "ira.h"
32 #include "basic-block.h" 33 #include "ira-int.h"
33 #include "insn-config.h"
34 #include "recog.h"
35 #include "diagnostic-core.h"
36 #include "params.h" 34 #include "params.h"
37 #include "df.h"
38 #include "output.h"
39 #include "reload.h"
40 #include "sparseset.h" 35 #include "sparseset.h"
41 #include "ira-int.h" 36 #include "cfgloop.h"
42 #include "emit-rtl.h" /* FIXME: Can go away once crtl is moved to rtl.h. */ 37
43 38 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx_insn *,
44 static ira_copy_t find_allocno_copy (ira_allocno_t, ira_allocno_t, rtx,
45 ira_loop_tree_node_t); 39 ira_loop_tree_node_t);
46 40
47 /* The root of the loop tree corresponding to the all function. */ 41 /* The root of the loop tree corresponding to the all function. */
48 ira_loop_tree_node_t ira_loop_tree_root; 42 ira_loop_tree_node_t ira_loop_tree_root;
49 43
57 51
58 /* All nodes representing loops are referred through the following 52 /* All nodes representing loops are referred through the following
59 array. */ 53 array. */
60 ira_loop_tree_node_t ira_loop_nodes; 54 ira_loop_tree_node_t ira_loop_nodes;
61 55
56 /* And size of the ira_loop_nodes array. */
57 unsigned int ira_loop_nodes_count;
58
62 /* Map regno -> allocnos with given regno (see comments for 59 /* Map regno -> allocnos with given regno (see comments for
63 allocno member `next_regno_allocno'). */ 60 allocno member `next_regno_allocno'). */
64 ira_allocno_t *ira_regno_allocno_map; 61 ira_allocno_t *ira_regno_allocno_map;
65 62
66 /* Array of references to all allocnos. The order number of the 63 /* Array of references to all allocnos. The order number of the
76 int ira_objects_num; 73 int ira_objects_num;
77 74
78 /* Map a conflict id to its conflict record. */ 75 /* Map a conflict id to its conflict record. */
79 ira_object_t *ira_object_id_map; 76 ira_object_t *ira_object_id_map;
80 77
78 /* Array of references to all allocno preferences. The order number
79 of the preference corresponds to the index in the array. */
80 ira_pref_t *ira_prefs;
81
82 /* Size of the previous array. */
83 int ira_prefs_num;
84
81 /* Array of references to all copies. The order number of the copy 85 /* Array of references to all copies. The order number of the copy
82 corresponds to the index in the array. Removed copies have NULL 86 corresponds to the index in the array. Removed copies have NULL
83 element value. */ 87 element value. */
84 ira_copy_t *ira_copies; 88 ira_copy_t *ira_copies;
85 89
91 /* LAST_BASIC_BLOCK before generating additional insns because of live 95 /* LAST_BASIC_BLOCK before generating additional insns because of live
92 range splitting. Emitting insns on a critical edge creates a new 96 range splitting. Emitting insns on a critical edge creates a new
93 basic block. */ 97 basic block. */
94 static int last_basic_block_before_change; 98 static int last_basic_block_before_change;
95 99
96 /* The following function allocates the loop tree nodes. If LOOPS_P 100 /* Initialize some members in loop tree node NODE. Use LOOP_NUM for
97 is FALSE, the nodes corresponding to the loops (except the root 101 the member loop_num. */
98 which corresponds the all function) will be not allocated but nodes 102 static void
99 will still be allocated for basic blocks. */ 103 init_loop_tree_node (struct ira_loop_tree_node *node, int loop_num)
100 static void 104 {
101 create_loop_tree_nodes (bool loops_p) 105 int max_regno = max_reg_num ();
106
107 node->regno_allocno_map
108 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
109 memset (node->regno_allocno_map, 0, sizeof (ira_allocno_t) * max_regno);
110 memset (node->reg_pressure, 0, sizeof (node->reg_pressure));
111 node->all_allocnos = ira_allocate_bitmap ();
112 node->modified_regnos = ira_allocate_bitmap ();
113 node->border_allocnos = ira_allocate_bitmap ();
114 node->local_copies = ira_allocate_bitmap ();
115 node->loop_num = loop_num;
116 node->children = NULL;
117 node->subloops = NULL;
118 }
119
120
121 /* The following function allocates the loop tree nodes. If
122 CURRENT_LOOPS is NULL, the nodes corresponding to the loops (except
123 the root which corresponds the all function) will be not allocated
124 but nodes will still be allocated for basic blocks. */
125 static void
126 create_loop_tree_nodes (void)
102 { 127 {
103 unsigned int i, j; 128 unsigned int i, j;
104 int max_regno;
105 bool skip_p; 129 bool skip_p;
106 edge_iterator ei; 130 edge_iterator ei;
107 edge e; 131 edge e;
108 VEC (edge, heap) *edges; 132 vec<edge> edges;
109 loop_p loop; 133 loop_p loop;
110 134
111 ira_bb_nodes 135 ira_bb_nodes
112 = ((struct ira_loop_tree_node *) 136 = ((struct ira_loop_tree_node *)
113 ira_allocate (sizeof (struct ira_loop_tree_node) * last_basic_block)); 137 ira_allocate (sizeof (struct ira_loop_tree_node)
114 last_basic_block_before_change = last_basic_block; 138 * last_basic_block_for_fn (cfun)));
115 for (i = 0; i < (unsigned int) last_basic_block; i++) 139 last_basic_block_before_change = last_basic_block_for_fn (cfun);
140 for (i = 0; i < (unsigned int) last_basic_block_for_fn (cfun); i++)
116 { 141 {
117 ira_bb_nodes[i].regno_allocno_map = NULL; 142 ira_bb_nodes[i].regno_allocno_map = NULL;
118 memset (ira_bb_nodes[i].reg_pressure, 0, 143 memset (ira_bb_nodes[i].reg_pressure, 0,
119 sizeof (ira_bb_nodes[i].reg_pressure)); 144 sizeof (ira_bb_nodes[i].reg_pressure));
120 ira_bb_nodes[i].all_allocnos = NULL; 145 ira_bb_nodes[i].all_allocnos = NULL;
121 ira_bb_nodes[i].modified_regnos = NULL; 146 ira_bb_nodes[i].modified_regnos = NULL;
122 ira_bb_nodes[i].border_allocnos = NULL; 147 ira_bb_nodes[i].border_allocnos = NULL;
123 ira_bb_nodes[i].local_copies = NULL; 148 ira_bb_nodes[i].local_copies = NULL;
124 } 149 }
150 if (current_loops == NULL)
151 {
152 ira_loop_nodes_count = 1;
153 ira_loop_nodes = ((struct ira_loop_tree_node *)
154 ira_allocate (sizeof (struct ira_loop_tree_node)));
155 init_loop_tree_node (ira_loop_nodes, 0);
156 return;
157 }
158 ira_loop_nodes_count = number_of_loops (cfun);
125 ira_loop_nodes = ((struct ira_loop_tree_node *) 159 ira_loop_nodes = ((struct ira_loop_tree_node *)
126 ira_allocate (sizeof (struct ira_loop_tree_node) 160 ira_allocate (sizeof (struct ira_loop_tree_node)
127 * VEC_length (loop_p, ira_loops.larray))); 161 * ira_loop_nodes_count));
128 max_regno = max_reg_num (); 162 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
129 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 163 {
130 { 164 if (loop_outer (loop) != NULL)
131 if (loop != ira_loops.tree_root)
132 { 165 {
133 ira_loop_nodes[i].regno_allocno_map = NULL; 166 ira_loop_nodes[i].regno_allocno_map = NULL;
134 if (! loops_p)
135 continue;
136 skip_p = false; 167 skip_p = false;
137 FOR_EACH_EDGE (e, ei, loop->header->preds) 168 FOR_EACH_EDGE (e, ei, loop->header->preds)
138 if (e->src != loop->latch 169 if (e->src != loop->latch
139 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) 170 && (e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
140 { 171 {
142 break; 173 break;
143 } 174 }
144 if (skip_p) 175 if (skip_p)
145 continue; 176 continue;
146 edges = get_loop_exit_edges (loop); 177 edges = get_loop_exit_edges (loop);
147 FOR_EACH_VEC_ELT (edge, edges, j, e) 178 FOR_EACH_VEC_ELT (edges, j, e)
148 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) 179 if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e))
149 { 180 {
150 skip_p = true; 181 skip_p = true;
151 break; 182 break;
152 } 183 }
153 VEC_free (edge, heap, edges); 184 edges.release ();
154 if (skip_p) 185 if (skip_p)
155 continue; 186 continue;
156 } 187 }
157 ira_loop_nodes[i].regno_allocno_map 188 init_loop_tree_node (&ira_loop_nodes[i], loop->num);
158 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) * max_regno);
159 memset (ira_loop_nodes[i].regno_allocno_map, 0,
160 sizeof (ira_allocno_t) * max_regno);
161 memset (ira_loop_nodes[i].reg_pressure, 0,
162 sizeof (ira_loop_nodes[i].reg_pressure));
163 ira_loop_nodes[i].all_allocnos = ira_allocate_bitmap ();
164 ira_loop_nodes[i].modified_regnos = ira_allocate_bitmap ();
165 ira_loop_nodes[i].border_allocnos = ira_allocate_bitmap ();
166 ira_loop_nodes[i].local_copies = ira_allocate_bitmap ();
167 } 189 }
168 } 190 }
169 191
170 /* The function returns TRUE if there are more one allocation 192 /* The function returns TRUE if there are more one allocation
171 region. */ 193 region. */
173 more_one_region_p (void) 195 more_one_region_p (void)
174 { 196 {
175 unsigned int i; 197 unsigned int i;
176 loop_p loop; 198 loop_p loop;
177 199
178 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 200 if (current_loops != NULL)
179 if (ira_loop_nodes[i].regno_allocno_map != NULL 201 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
180 && ira_loop_tree_root != &ira_loop_nodes[i]) 202 if (ira_loop_nodes[i].regno_allocno_map != NULL
181 return true; 203 && ira_loop_tree_root != &ira_loop_nodes[i])
204 return true;
182 return false; 205 return false;
183 } 206 }
184 207
185 /* Free the loop tree node of a loop. */ 208 /* Free the loop tree node of a loop. */
186 static void 209 static void
201 /* Free the loop tree nodes. */ 224 /* Free the loop tree nodes. */
202 static void 225 static void
203 finish_loop_tree_nodes (void) 226 finish_loop_tree_nodes (void)
204 { 227 {
205 unsigned int i; 228 unsigned int i;
206 loop_p loop; 229
207 230 for (i = 0; i < ira_loop_nodes_count; i++)
208 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop)
209 finish_loop_tree_node (&ira_loop_nodes[i]); 231 finish_loop_tree_node (&ira_loop_nodes[i]);
210 ira_free (ira_loop_nodes); 232 ira_free (ira_loop_nodes);
211 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++) 233 for (i = 0; i < (unsigned int) last_basic_block_before_change; i++)
212 { 234 {
213 if (ira_bb_nodes[i].local_copies != NULL) 235 if (ira_bb_nodes[i].local_copies != NULL)
225 } 247 }
226 248
227 249
228 250
229 /* The following recursive function adds LOOP to the loop tree 251 /* The following recursive function adds LOOP to the loop tree
230 hierarchy. LOOP is added only once. */ 252 hierarchy. LOOP is added only once. If LOOP is NULL we adding
253 loop designating the whole function when CFG loops are not
254 built. */
231 static void 255 static void
232 add_loop_to_tree (struct loop *loop) 256 add_loop_to_tree (struct loop *loop)
233 { 257 {
258 int loop_num;
234 struct loop *parent; 259 struct loop *parent;
235 ira_loop_tree_node_t loop_node, parent_node; 260 ira_loop_tree_node_t loop_node, parent_node;
236 261
237 /* We can not use loop node access macros here because of potential 262 /* We can not use loop node access macros here because of potential
238 checking and because the nodes are not initialized enough 263 checking and because the nodes are not initialized enough
239 yet. */ 264 yet. */
240 if (loop_outer (loop) != NULL) 265 if (loop != NULL && loop_outer (loop) != NULL)
241 add_loop_to_tree (loop_outer (loop)); 266 add_loop_to_tree (loop_outer (loop));
242 if (ira_loop_nodes[loop->num].regno_allocno_map != NULL 267 loop_num = loop != NULL ? loop->num : 0;
243 && ira_loop_nodes[loop->num].children == NULL) 268 if (ira_loop_nodes[loop_num].regno_allocno_map != NULL
269 && ira_loop_nodes[loop_num].children == NULL)
244 { 270 {
245 /* We have not added loop node to the tree yet. */ 271 /* We have not added loop node to the tree yet. */
246 loop_node = &ira_loop_nodes[loop->num]; 272 loop_node = &ira_loop_nodes[loop_num];
247 loop_node->loop = loop; 273 loop_node->loop = loop;
248 loop_node->bb = NULL; 274 loop_node->bb = NULL;
249 for (parent = loop_outer (loop); 275 if (loop == NULL)
250 parent != NULL; 276 parent = NULL;
251 parent = loop_outer (parent)) 277 else
252 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL) 278 {
253 break; 279 for (parent = loop_outer (loop);
280 parent != NULL;
281 parent = loop_outer (parent))
282 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
283 break;
284 }
254 if (parent == NULL) 285 if (parent == NULL)
255 { 286 {
256 loop_node->next = NULL; 287 loop_node->next = NULL;
257 loop_node->subloop_next = NULL; 288 loop_node->subloop_next = NULL;
258 loop_node->parent = NULL; 289 loop_node->parent = NULL;
297 order of loops (they are ordered by their last loop BB) and basic 328 order of loops (they are ordered by their last loop BB) and basic
298 blocks in the chain formed by member next. */ 329 blocks in the chain formed by member next. */
299 static void 330 static void
300 form_loop_tree (void) 331 form_loop_tree (void)
301 { 332 {
302 unsigned int i;
303 basic_block bb; 333 basic_block bb;
304 struct loop *parent; 334 struct loop *parent;
305 ira_loop_tree_node_t bb_node, loop_node; 335 ira_loop_tree_node_t bb_node, loop_node;
306 loop_p loop;
307 336
308 /* We can not use loop/bb node access macros because of potential 337 /* We can not use loop/bb node access macros because of potential
309 checking and because the nodes are not initialized enough 338 checking and because the nodes are not initialized enough
310 yet. */ 339 yet. */
311 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 340 FOR_EACH_BB_FN (bb, cfun)
312 if (ira_loop_nodes[i].regno_allocno_map != NULL)
313 {
314 ira_loop_nodes[i].children = NULL;
315 ira_loop_nodes[i].subloops = NULL;
316 }
317 FOR_EACH_BB (bb)
318 { 341 {
319 bb_node = &ira_bb_nodes[bb->index]; 342 bb_node = &ira_bb_nodes[bb->index];
320 bb_node->bb = bb; 343 bb_node->bb = bb;
321 bb_node->loop = NULL; 344 bb_node->loop = NULL;
322 bb_node->subloops = NULL; 345 bb_node->subloops = NULL;
323 bb_node->children = NULL; 346 bb_node->children = NULL;
324 bb_node->subloop_next = NULL; 347 bb_node->subloop_next = NULL;
325 bb_node->next = NULL; 348 bb_node->next = NULL;
326 for (parent = bb->loop_father; 349 if (current_loops == NULL)
327 parent != NULL; 350 parent = NULL;
328 parent = loop_outer (parent)) 351 else
329 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL) 352 {
330 break; 353 for (parent = bb->loop_father;
354 parent != NULL;
355 parent = loop_outer (parent))
356 if (ira_loop_nodes[parent->num].regno_allocno_map != NULL)
357 break;
358 }
331 add_loop_to_tree (parent); 359 add_loop_to_tree (parent);
332 loop_node = &ira_loop_nodes[parent->num]; 360 loop_node = &ira_loop_nodes[parent == NULL ? 0 : parent->num];
333 bb_node->next = loop_node->children; 361 bb_node->next = loop_node->children;
334 bb_node->parent = loop_node; 362 bb_node->parent = loop_node;
335 loop_node->children = bb_node; 363 loop_node->children = bb_node;
336 } 364 }
337 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (ira_loops.tree_root->num); 365 ira_loop_tree_root = IRA_LOOP_NODE_BY_INDEX (0);
338 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0); 366 ira_loop_tree_height = setup_loop_tree_level (ira_loop_tree_root, 0);
339 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL); 367 ira_assert (ira_loop_tree_root->regno_allocno_map != NULL);
340 } 368 }
341 369
342 370
351 ira_allocno_t a; 379 ira_allocno_t a;
352 ira_loop_tree_node_t loop_tree_node; 380 ira_loop_tree_node_t loop_tree_node;
353 loop_p loop; 381 loop_p loop;
354 ira_allocno_iterator ai; 382 ira_allocno_iterator ai;
355 383
384 ira_assert (current_loops != NULL);
356 max_regno = max_reg_num (); 385 max_regno = max_reg_num ();
357 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, l, loop) 386 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), l, loop)
358 if (ira_loop_nodes[l].regno_allocno_map != NULL) 387 if (ira_loop_nodes[l].regno_allocno_map != NULL)
359 { 388 {
360 ira_free (ira_loop_nodes[l].regno_allocno_map); 389 ira_free (ira_loop_nodes[l].regno_allocno_map);
361 ira_loop_nodes[l].regno_allocno_map 390 ira_loop_nodes[l].regno_allocno_map
362 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t) 391 = (ira_allocno_t *) ira_allocate (sizeof (ira_allocno_t)
384 } 413 }
385 } 414 }
386 415
387 416
388 /* Pools for allocnos, allocno live ranges and objects. */ 417 /* Pools for allocnos, allocno live ranges and objects. */
389 static alloc_pool allocno_pool, live_range_pool, object_pool; 418 static object_allocator<live_range> live_range_pool ("live ranges");
419 static object_allocator<ira_allocno> allocno_pool ("allocnos");
420 static object_allocator<ira_object> object_pool ("objects");
390 421
391 /* Vec containing references to all created allocnos. It is a 422 /* Vec containing references to all created allocnos. It is a
392 container of array allocnos. */ 423 container of array allocnos. */
393 static VEC(ira_allocno_t,heap) *allocno_vec; 424 static vec<ira_allocno_t> allocno_vec;
394 425
395 /* Vec containing references to all created ira_objects. It is a 426 /* Vec containing references to all created ira_objects. It is a
396 container of ira_object_id_map. */ 427 container of ira_object_id_map. */
397 static VEC(ira_object_t,heap) *ira_object_id_map_vec; 428 static vec<ira_object_t> ira_object_id_map_vec;
398 429
399 /* Initialize data concerning allocnos. */ 430 /* Initialize data concerning allocnos. */
400 static void 431 static void
401 initiate_allocnos (void) 432 initiate_allocnos (void)
402 { 433 {
403 live_range_pool 434 allocno_vec.create (max_reg_num () * 2);
404 = create_alloc_pool ("live ranges",
405 sizeof (struct live_range), 100);
406 allocno_pool
407 = create_alloc_pool ("allocnos", sizeof (struct ira_allocno), 100);
408 object_pool
409 = create_alloc_pool ("objects", sizeof (struct ira_object), 100);
410 allocno_vec = VEC_alloc (ira_allocno_t, heap, max_reg_num () * 2);
411 ira_allocnos = NULL; 435 ira_allocnos = NULL;
412 ira_allocnos_num = 0; 436 ira_allocnos_num = 0;
413 ira_objects_num = 0; 437 ira_objects_num = 0;
414 ira_object_id_map_vec 438 ira_object_id_map_vec.create (max_reg_num () * 2);
415 = VEC_alloc (ira_object_t, heap, max_reg_num () * 2);
416 ira_object_id_map = NULL; 439 ira_object_id_map = NULL;
417 ira_regno_allocno_map 440 ira_regno_allocno_map
418 = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t)); 441 = (ira_allocno_t *) ira_allocate (max_reg_num ()
442 * sizeof (ira_allocno_t));
419 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t)); 443 memset (ira_regno_allocno_map, 0, max_reg_num () * sizeof (ira_allocno_t));
420 } 444 }
421 445
422 /* Create and return an object corresponding to a new allocno A. */ 446 /* Create and return an object corresponding to a new allocno A. */
423 static ira_object_t 447 static ira_object_t
424 ira_create_object (ira_allocno_t a, int subword) 448 ira_create_object (ira_allocno_t a, int subword)
425 { 449 {
426 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a); 450 enum reg_class aclass = ALLOCNO_CLASS (a);
427 ira_object_t obj = (ira_object_t) pool_alloc (object_pool); 451 ira_object_t obj = object_pool.allocate ();
428 452
429 OBJECT_ALLOCNO (obj) = a; 453 OBJECT_ALLOCNO (obj) = a;
430 OBJECT_SUBWORD (obj) = subword; 454 OBJECT_SUBWORD (obj) = subword;
431 OBJECT_CONFLICT_ID (obj) = ira_objects_num; 455 OBJECT_CONFLICT_ID (obj) = ira_objects_num;
432 OBJECT_CONFLICT_VEC_P (obj) = false; 456 OBJECT_CONFLICT_VEC_P (obj) = false;
433 OBJECT_CONFLICT_ARRAY (obj) = NULL; 457 OBJECT_CONFLICT_ARRAY (obj) = NULL;
434 OBJECT_NUM_CONFLICTS (obj) = 0; 458 OBJECT_NUM_CONFLICTS (obj) = 0;
435 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs); 459 COPY_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
436 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs); 460 COPY_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), ira_no_alloc_regs);
437 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), 461 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
438 reg_class_contents[cover_class]); 462 reg_class_contents[aclass]);
439 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), 463 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
440 reg_class_contents[cover_class]); 464 reg_class_contents[aclass]);
441 OBJECT_MIN (obj) = INT_MAX; 465 OBJECT_MIN (obj) = INT_MAX;
442 OBJECT_MAX (obj) = -1; 466 OBJECT_MAX (obj) = -1;
443 OBJECT_LIVE_RANGES (obj) = NULL; 467 OBJECT_LIVE_RANGES (obj) = NULL;
444 468
445 VEC_safe_push (ira_object_t, heap, ira_object_id_map_vec, obj); 469 ira_object_id_map_vec.safe_push (obj);
446 ira_object_id_map 470 ira_object_id_map
447 = VEC_address (ira_object_t, ira_object_id_map_vec); 471 = ira_object_id_map_vec.address ();
448 ira_objects_num = VEC_length (ira_object_t, ira_object_id_map_vec); 472 ira_objects_num = ira_object_id_map_vec.length ();
449 473
450 return obj; 474 return obj;
451 } 475 }
452 476
453 /* Create and return the allocno corresponding to REGNO in 477 /* Create and return the allocno corresponding to REGNO in
454 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the 478 LOOP_TREE_NODE. Add the allocno to the list of allocnos with the
455 same regno if CAP_P is FALSE. */ 479 same regno if CAP_P is FALSE. */
456 ira_allocno_t 480 ira_allocno_t
457 ira_create_allocno (int regno, bool cap_p, ira_loop_tree_node_t loop_tree_node) 481 ira_create_allocno (int regno, bool cap_p,
482 ira_loop_tree_node_t loop_tree_node)
458 { 483 {
459 ira_allocno_t a; 484 ira_allocno_t a;
460 485
461 a = (ira_allocno_t) pool_alloc (allocno_pool); 486 a = allocno_pool.allocate ();
462 ALLOCNO_REGNO (a) = regno; 487 ALLOCNO_REGNO (a) = regno;
463 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node; 488 ALLOCNO_LOOP_TREE_NODE (a) = loop_tree_node;
464 if (! cap_p) 489 if (! cap_p)
465 { 490 {
466 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno]; 491 ALLOCNO_NEXT_REGNO_ALLOCNO (a) = ira_regno_allocno_map[regno];
478 ALLOCNO_NREFS (a) = 0; 503 ALLOCNO_NREFS (a) = 0;
479 ALLOCNO_FREQ (a) = 0; 504 ALLOCNO_FREQ (a) = 0;
480 ALLOCNO_HARD_REGNO (a) = -1; 505 ALLOCNO_HARD_REGNO (a) = -1;
481 ALLOCNO_CALL_FREQ (a) = 0; 506 ALLOCNO_CALL_FREQ (a) = 0;
482 ALLOCNO_CALLS_CROSSED_NUM (a) = 0; 507 ALLOCNO_CALLS_CROSSED_NUM (a) = 0;
508 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a) = 0;
509 CLEAR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
483 #ifdef STACK_REGS 510 #ifdef STACK_REGS
484 ALLOCNO_NO_STACK_REG_P (a) = false; 511 ALLOCNO_NO_STACK_REG_P (a) = false;
485 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false; 512 ALLOCNO_TOTAL_NO_STACK_REG_P (a) = false;
486 #endif 513 #endif
487 ALLOCNO_MEM_OPTIMIZED_DEST (a) = NULL;
488 ALLOCNO_MEM_OPTIMIZED_DEST_P (a) = false;
489 ALLOCNO_SOMEWHERE_RENAMED_P (a) = false;
490 ALLOCNO_CHILD_RENAMED_P (a) = false;
491 ALLOCNO_DONT_REASSIGN_P (a) = false; 514 ALLOCNO_DONT_REASSIGN_P (a) = false;
492 ALLOCNO_BAD_SPILL_P (a) = false; 515 ALLOCNO_BAD_SPILL_P (a) = false;
493 ALLOCNO_IN_GRAPH_P (a) = false;
494 ALLOCNO_ASSIGNED_P (a) = false; 516 ALLOCNO_ASSIGNED_P (a) = false;
495 ALLOCNO_MAY_BE_SPILLED_P (a) = false;
496 ALLOCNO_SPLAY_REMOVED_P (a) = false;
497 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno)); 517 ALLOCNO_MODE (a) = (regno < 0 ? VOIDmode : PSEUDO_REGNO_MODE (regno));
518 ALLOCNO_WMODE (a) = ALLOCNO_MODE (a);
519 ALLOCNO_PREFS (a) = NULL;
498 ALLOCNO_COPIES (a) = NULL; 520 ALLOCNO_COPIES (a) = NULL;
499 ALLOCNO_HARD_REG_COSTS (a) = NULL; 521 ALLOCNO_HARD_REG_COSTS (a) = NULL;
500 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL; 522 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
501 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL; 523 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
502 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL; 524 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
503 ALLOCNO_LEFT_CONFLICTS_SIZE (a) = -1; 525 ALLOCNO_CLASS (a) = NO_REGS;
504 ALLOCNO_COVER_CLASS (a) = NO_REGS; 526 ALLOCNO_UPDATED_CLASS_COST (a) = 0;
505 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = 0; 527 ALLOCNO_CLASS_COST (a) = 0;
506 ALLOCNO_COVER_CLASS_COST (a) = 0;
507 ALLOCNO_MEMORY_COST (a) = 0; 528 ALLOCNO_MEMORY_COST (a) = 0;
508 ALLOCNO_UPDATED_MEMORY_COST (a) = 0; 529 ALLOCNO_UPDATED_MEMORY_COST (a) = 0;
509 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0; 530 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) = 0;
510 ALLOCNO_NEXT_BUCKET_ALLOCNO (a) = NULL;
511 ALLOCNO_PREV_BUCKET_ALLOCNO (a) = NULL;
512 ALLOCNO_FIRST_COALESCED_ALLOCNO (a) = a;
513 ALLOCNO_NEXT_COALESCED_ALLOCNO (a) = a;
514 ALLOCNO_NUM_OBJECTS (a) = 0; 531 ALLOCNO_NUM_OBJECTS (a) = 0;
515 532
516 VEC_safe_push (ira_allocno_t, heap, allocno_vec, a); 533 ALLOCNO_ADD_DATA (a) = NULL;
517 ira_allocnos = VEC_address (ira_allocno_t, allocno_vec); 534 allocno_vec.safe_push (a);
518 ira_allocnos_num = VEC_length (ira_allocno_t, allocno_vec); 535 ira_allocnos = allocno_vec.address ();
536 ira_allocnos_num = allocno_vec.length ();
519 537
520 return a; 538 return a;
521 } 539 }
522 540
523 /* Set up cover class for A and update its conflict hard registers. */ 541 /* Set up register class for A and update its conflict hard
542 registers. */
524 void 543 void
525 ira_set_allocno_cover_class (ira_allocno_t a, enum reg_class cover_class) 544 ira_set_allocno_class (ira_allocno_t a, enum reg_class aclass)
526 { 545 {
527 ALLOCNO_COVER_CLASS (a) = cover_class; 546 ira_allocno_object_iterator oi;
547 ira_object_t obj;
548
549 ALLOCNO_CLASS (a) = aclass;
550 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
551 {
552 IOR_COMPL_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj),
553 reg_class_contents[aclass]);
554 IOR_COMPL_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj),
555 reg_class_contents[aclass]);
556 }
528 } 557 }
529 558
530 /* Determine the number of objects we should associate with allocno A 559 /* Determine the number of objects we should associate with allocno A
531 and allocate them. */ 560 and allocate them. */
532 void 561 void
533 ira_create_allocno_objects (ira_allocno_t a) 562 ira_create_allocno_objects (ira_allocno_t a)
534 { 563 {
535 enum machine_mode mode = ALLOCNO_MODE (a); 564 machine_mode mode = ALLOCNO_MODE (a);
536 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a); 565 enum reg_class aclass = ALLOCNO_CLASS (a);
537 int n = ira_reg_class_nregs[cover_class][mode]; 566 int n = ira_reg_class_max_nregs[aclass][mode];
538 int i; 567 int i;
539 568
540 if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2) 569 if (GET_MODE_SIZE (mode) != 2 * UNITS_PER_WORD || n != 2)
541 n = 1; 570 n = 1;
542 571
544 for (i = 0; i < n; i++) 573 for (i = 0; i < n; i++)
545 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i); 574 ALLOCNO_OBJECT (a, i) = ira_create_object (a, i);
546 } 575 }
547 576
548 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the 577 /* For each allocno, set ALLOCNO_NUM_OBJECTS and create the
549 ALLOCNO_OBJECT structures. This must be called after the cover 578 ALLOCNO_OBJECT structures. This must be called after the allocno
550 classes are known. */ 579 classes are known. */
551 static void 580 static void
552 create_allocno_objects (void) 581 create_allocno_objects (void)
553 { 582 {
554 ira_allocno_t a; 583 ira_allocno_t a;
569 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from)); 598 gcc_assert (ALLOCNO_NUM_OBJECTS (to) == ALLOCNO_NUM_OBJECTS (from));
570 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++) 599 for (i = 0; i < ALLOCNO_NUM_OBJECTS (to); i++)
571 { 600 {
572 ira_object_t from_obj = ALLOCNO_OBJECT (from, i); 601 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
573 ira_object_t to_obj = ALLOCNO_OBJECT (to, i); 602 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
603
574 if (!total_only) 604 if (!total_only)
575 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj), 605 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj),
576 OBJECT_CONFLICT_HARD_REGS (from_obj)); 606 OBJECT_CONFLICT_HARD_REGS (from_obj));
577 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj), 607 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj),
578 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj)); 608 OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj));
590 void 620 void
591 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set) 621 ior_hard_reg_conflicts (ira_allocno_t a, HARD_REG_SET *set)
592 { 622 {
593 ira_allocno_object_iterator i; 623 ira_allocno_object_iterator i;
594 ira_object_t obj; 624 ira_object_t obj;
625
595 FOR_EACH_ALLOCNO_OBJECT (a, obj, i) 626 FOR_EACH_ALLOCNO_OBJECT (a, obj, i)
596 { 627 {
597 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set); 628 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (obj), *set);
598 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set); 629 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (obj), *set);
599 } 630 }
831 862
832 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a)); 863 fprintf (ira_dump_file, " a%d(r%d", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
833 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL) 864 if ((bb = ALLOCNO_LOOP_TREE_NODE (a)->bb) != NULL)
834 fprintf (ira_dump_file, ",b%d", bb->index); 865 fprintf (ira_dump_file, ",b%d", bb->index);
835 else 866 else
836 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop->num); 867 fprintf (ira_dump_file, ",l%d", ALLOCNO_LOOP_TREE_NODE (a)->loop_num);
837 if (ALLOCNO_CAP_MEMBER (a) != NULL) 868 if (ALLOCNO_CAP_MEMBER (a) != NULL)
838 { 869 {
839 fprintf (ira_dump_file, ":"); 870 fprintf (ira_dump_file, ":");
840 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a)); 871 ira_print_expanded_allocno (ALLOCNO_CAP_MEMBER (a));
841 } 872 }
847 static ira_allocno_t 878 static ira_allocno_t
848 create_cap_allocno (ira_allocno_t a) 879 create_cap_allocno (ira_allocno_t a)
849 { 880 {
850 ira_allocno_t cap; 881 ira_allocno_t cap;
851 ira_loop_tree_node_t parent; 882 ira_loop_tree_node_t parent;
852 enum reg_class cover_class; 883 enum reg_class aclass;
853 884
854 ira_assert (ALLOCNO_FIRST_COALESCED_ALLOCNO (a) == a
855 && ALLOCNO_NEXT_COALESCED_ALLOCNO (a) == a);
856 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent; 885 parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
857 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent); 886 cap = ira_create_allocno (ALLOCNO_REGNO (a), true, parent);
858 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a); 887 ALLOCNO_MODE (cap) = ALLOCNO_MODE (a);
859 cover_class = ALLOCNO_COVER_CLASS (a); 888 ALLOCNO_WMODE (cap) = ALLOCNO_WMODE (a);
860 ira_set_allocno_cover_class (cap, cover_class); 889 aclass = ALLOCNO_CLASS (a);
890 ira_set_allocno_class (cap, aclass);
861 ira_create_allocno_objects (cap); 891 ira_create_allocno_objects (cap);
862 ALLOCNO_AVAILABLE_REGS_NUM (cap) = ALLOCNO_AVAILABLE_REGS_NUM (a);
863 ALLOCNO_CAP_MEMBER (cap) = a; 892 ALLOCNO_CAP_MEMBER (cap) = a;
864 ALLOCNO_CAP (a) = cap; 893 ALLOCNO_CAP (a) = cap;
865 ALLOCNO_COVER_CLASS_COST (cap) = ALLOCNO_COVER_CLASS_COST (a); 894 ALLOCNO_CLASS_COST (cap) = ALLOCNO_CLASS_COST (a);
866 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a); 895 ALLOCNO_MEMORY_COST (cap) = ALLOCNO_MEMORY_COST (a);
867 ira_allocate_and_copy_costs 896 ira_allocate_and_copy_costs
868 (&ALLOCNO_HARD_REG_COSTS (cap), cover_class, ALLOCNO_HARD_REG_COSTS (a)); 897 (&ALLOCNO_HARD_REG_COSTS (cap), aclass, ALLOCNO_HARD_REG_COSTS (a));
869 ira_allocate_and_copy_costs 898 ira_allocate_and_copy_costs
870 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), cover_class, 899 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (cap), aclass,
871 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); 900 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
872 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a); 901 ALLOCNO_BAD_SPILL_P (cap) = ALLOCNO_BAD_SPILL_P (a);
873 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a); 902 ALLOCNO_NREFS (cap) = ALLOCNO_NREFS (a);
874 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a); 903 ALLOCNO_FREQ (cap) = ALLOCNO_FREQ (a);
875 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a); 904 ALLOCNO_CALL_FREQ (cap) = ALLOCNO_CALL_FREQ (a);
876 905
877 merge_hard_reg_conflicts (a, cap, false); 906 merge_hard_reg_conflicts (a, cap, false);
878 907
879 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a); 908 ALLOCNO_CALLS_CROSSED_NUM (cap) = ALLOCNO_CALLS_CROSSED_NUM (a);
909 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (cap) = ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
910 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (cap),
911 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
880 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 912 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
881 { 913 {
882 fprintf (ira_dump_file, " Creating cap "); 914 fprintf (ira_dump_file, " Creating cap ");
883 ira_print_expanded_allocno (cap); 915 ira_print_expanded_allocno (cap);
884 fprintf (ira_dump_file, "\n"); 916 fprintf (ira_dump_file, "\n");
891 ira_create_live_range (ira_object_t obj, int start, int finish, 923 ira_create_live_range (ira_object_t obj, int start, int finish,
892 live_range_t next) 924 live_range_t next)
893 { 925 {
894 live_range_t p; 926 live_range_t p;
895 927
896 p = (live_range_t) pool_alloc (live_range_pool); 928 p = live_range_pool.allocate ();
897 p->object = obj; 929 p->object = obj;
898 p->start = start; 930 p->start = start;
899 p->finish = finish; 931 p->finish = finish;
900 p->next = next; 932 p->next = next;
901 return p; 933 return p;
916 static live_range_t 948 static live_range_t
917 copy_live_range (live_range_t r) 949 copy_live_range (live_range_t r)
918 { 950 {
919 live_range_t p; 951 live_range_t p;
920 952
921 p = (live_range_t) pool_alloc (live_range_pool); 953 p = live_range_pool.allocate ();
922 *p = *r; 954 *p = *r;
923 return p; 955 return p;
924 } 956 }
925 957
926 /* Copy allocno live range list given by its head R and return the 958 /* Copy allocno live range list given by its head R and return the
948 maintains the order of ranges and tries to minimize number of the 980 maintains the order of ranges and tries to minimize number of the
949 result ranges. */ 981 result ranges. */
950 live_range_t 982 live_range_t
951 ira_merge_live_ranges (live_range_t r1, live_range_t r2) 983 ira_merge_live_ranges (live_range_t r1, live_range_t r2)
952 { 984 {
953 live_range_t first, last, temp; 985 live_range_t first, last;
954 986
955 if (r1 == NULL) 987 if (r1 == NULL)
956 return r2; 988 return r2;
957 if (r2 == NULL) 989 if (r2 == NULL)
958 return r1; 990 return r1;
959 for (first = last = NULL; r1 != NULL && r2 != NULL;) 991 for (first = last = NULL; r1 != NULL && r2 != NULL;)
960 { 992 {
961 if (r1->start < r2->start) 993 if (r1->start < r2->start)
962 { 994 std::swap (r1, r2);
963 temp = r1;
964 r1 = r2;
965 r2 = temp;
966 }
967 if (r1->start <= r2->finish + 1) 995 if (r1->start <= r2->finish + 1)
968 { 996 {
969 /* Intersected ranges: merge r1 and r2 into r1. */ 997 /* Intersected ranges: merge r1 and r2 into r1. */
970 r1->start = r2->start; 998 r1->start = r2->start;
971 if (r1->finish < r2->finish) 999 if (r1->finish < r2->finish)
972 r1->finish = r2->finish; 1000 r1->finish = r2->finish;
973 temp = r2; 1001 live_range_t temp = r2;
974 r2 = r2->next; 1002 r2 = r2->next;
975 ira_finish_live_range (temp); 1003 ira_finish_live_range (temp);
976 if (r2 == NULL) 1004 if (r2 == NULL)
977 { 1005 {
978 /* To try to merge with subsequent ranges in r1. */ 1006 /* To try to merge with subsequent ranges in r1. */
1041 1069
1042 /* Free allocno live range R. */ 1070 /* Free allocno live range R. */
1043 void 1071 void
1044 ira_finish_live_range (live_range_t r) 1072 ira_finish_live_range (live_range_t r)
1045 { 1073 {
1046 pool_free (live_range_pool, r); 1074 live_range_pool.remove (r);
1047 } 1075 }
1048 1076
1049 /* Free list of allocno live ranges starting with R. */ 1077 /* Free list of allocno live ranges starting with R. */
1050 void 1078 void
1051 ira_finish_live_range_list (live_range_t r) 1079 ira_finish_live_range_list (live_range_t r)
1061 1089
1062 /* Free updated register costs of allocno A. */ 1090 /* Free updated register costs of allocno A. */
1063 void 1091 void
1064 ira_free_allocno_updated_costs (ira_allocno_t a) 1092 ira_free_allocno_updated_costs (ira_allocno_t a)
1065 { 1093 {
1066 enum reg_class cover_class; 1094 enum reg_class aclass;
1067 1095
1068 cover_class = ALLOCNO_COVER_CLASS (a); 1096 aclass = ALLOCNO_CLASS (a);
1069 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL) 1097 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1070 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class); 1098 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1071 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL; 1099 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1072 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL) 1100 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1073 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), 1101 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1074 cover_class); 1102 aclass);
1075 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL; 1103 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1076 } 1104 }
1077 1105
1078 /* Free the memory allocated for allocno A. */ 1106 /* Free and nullify all cost vectors allocated earlier for allocno
1079 static void 1107 A. */
1080 finish_allocno (ira_allocno_t a) 1108 static void
1081 { 1109 ira_free_allocno_costs (ira_allocno_t a)
1082 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a); 1110 {
1111 enum reg_class aclass = ALLOCNO_CLASS (a);
1083 ira_object_t obj; 1112 ira_object_t obj;
1084 ira_allocno_object_iterator oi; 1113 ira_allocno_object_iterator oi;
1085 1114
1086 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 1115 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
1087 { 1116 {
1088 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj)); 1117 ira_finish_live_range_list (OBJECT_LIVE_RANGES (obj));
1089 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL; 1118 ira_object_id_map[OBJECT_CONFLICT_ID (obj)] = NULL;
1090 if (OBJECT_CONFLICT_ARRAY (obj) != NULL) 1119 if (OBJECT_CONFLICT_ARRAY (obj) != NULL)
1091 ira_free (OBJECT_CONFLICT_ARRAY (obj)); 1120 ira_free (OBJECT_CONFLICT_ARRAY (obj));
1092 pool_free (object_pool, obj); 1121 object_pool.remove (obj);
1093 } 1122 }
1094 1123
1095 ira_allocnos[ALLOCNO_NUM (a)] = NULL; 1124 ira_allocnos[ALLOCNO_NUM (a)] = NULL;
1096 if (ALLOCNO_HARD_REG_COSTS (a) != NULL) 1125 if (ALLOCNO_HARD_REG_COSTS (a) != NULL)
1097 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), cover_class); 1126 ira_free_cost_vector (ALLOCNO_HARD_REG_COSTS (a), aclass);
1098 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL) 1127 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL)
1099 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), cover_class); 1128 ira_free_cost_vector (ALLOCNO_CONFLICT_HARD_REG_COSTS (a), aclass);
1100 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL) 1129 if (ALLOCNO_UPDATED_HARD_REG_COSTS (a) != NULL)
1101 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), cover_class); 1130 ira_free_cost_vector (ALLOCNO_UPDATED_HARD_REG_COSTS (a), aclass);
1102 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL) 1131 if (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) != NULL)
1103 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a), 1132 ira_free_cost_vector (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a),
1104 cover_class); 1133 aclass);
1105 pool_free (allocno_pool, a); 1134 ALLOCNO_HARD_REG_COSTS (a) = NULL;
1135 ALLOCNO_CONFLICT_HARD_REG_COSTS (a) = NULL;
1136 ALLOCNO_UPDATED_HARD_REG_COSTS (a) = NULL;
1137 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) = NULL;
1138 }
1139
1140 /* Free the memory allocated for allocno A. */
1141 static void
1142 finish_allocno (ira_allocno_t a)
1143 {
1144 ira_free_allocno_costs (a);
1145 allocno_pool.remove (a);
1106 } 1146 }
1107 1147
1108 /* Free the memory allocated for all allocnos. */ 1148 /* Free the memory allocated for all allocnos. */
1109 static void 1149 static void
1110 finish_allocnos (void) 1150 finish_allocnos (void)
1113 ira_allocno_iterator ai; 1153 ira_allocno_iterator ai;
1114 1154
1115 FOR_EACH_ALLOCNO (a, ai) 1155 FOR_EACH_ALLOCNO (a, ai)
1116 finish_allocno (a); 1156 finish_allocno (a);
1117 ira_free (ira_regno_allocno_map); 1157 ira_free (ira_regno_allocno_map);
1118 VEC_free (ira_object_t, heap, ira_object_id_map_vec); 1158 ira_object_id_map_vec.release ();
1119 VEC_free (ira_allocno_t, heap, allocno_vec); 1159 allocno_vec.release ();
1120 free_alloc_pool (allocno_pool); 1160 allocno_pool.release ();
1121 free_alloc_pool (object_pool); 1161 object_pool.release ();
1122 free_alloc_pool (live_range_pool); 1162 live_range_pool.release ();
1123 } 1163 }
1124 1164
1125 1165
1126 1166
1167 /* Pools for allocno preferences. */
1168 static object_allocator <ira_allocno_pref> pref_pool ("prefs");
1169
1170 /* Vec containing references to all created preferences. It is a
1171 container of array ira_prefs. */
1172 static vec<ira_pref_t> pref_vec;
1173
1174 /* The function initializes data concerning allocno prefs. */
1175 static void
1176 initiate_prefs (void)
1177 {
1178 pref_vec.create (get_max_uid ());
1179 ira_prefs = NULL;
1180 ira_prefs_num = 0;
1181 }
1182
1183 /* Return pref for A and HARD_REGNO if any. */
1184 static ira_pref_t
1185 find_allocno_pref (ira_allocno_t a, int hard_regno)
1186 {
1187 ira_pref_t pref;
1188
1189 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1190 if (pref->allocno == a && pref->hard_regno == hard_regno)
1191 return pref;
1192 return NULL;
1193 }
1194
1195 /* Create and return pref with given attributes A, HARD_REGNO, and FREQ. */
1196 ira_pref_t
1197 ira_create_pref (ira_allocno_t a, int hard_regno, int freq)
1198 {
1199 ira_pref_t pref;
1200
1201 pref = pref_pool.allocate ();
1202 pref->num = ira_prefs_num;
1203 pref->allocno = a;
1204 pref->hard_regno = hard_regno;
1205 pref->freq = freq;
1206 pref_vec.safe_push (pref);
1207 ira_prefs = pref_vec.address ();
1208 ira_prefs_num = pref_vec.length ();
1209 return pref;
1210 }
1211
1212 /* Attach a pref PREF to the corresponding allocno. */
1213 static void
1214 add_allocno_pref_to_list (ira_pref_t pref)
1215 {
1216 ira_allocno_t a = pref->allocno;
1217
1218 pref->next_pref = ALLOCNO_PREFS (a);
1219 ALLOCNO_PREFS (a) = pref;
1220 }
1221
1222 /* Create (or update frequency if the pref already exists) the pref of
1223 allocnos A preferring HARD_REGNO with frequency FREQ. */
1224 void
1225 ira_add_allocno_pref (ira_allocno_t a, int hard_regno, int freq)
1226 {
1227 ira_pref_t pref;
1228
1229 if (freq <= 0)
1230 return;
1231 if ((pref = find_allocno_pref (a, hard_regno)) != NULL)
1232 {
1233 pref->freq += freq;
1234 return;
1235 }
1236 pref = ira_create_pref (a, hard_regno, freq);
1237 ira_assert (a != NULL);
1238 add_allocno_pref_to_list (pref);
1239 }
1240
1241 /* Print info about PREF into file F. */
1242 static void
1243 print_pref (FILE *f, ira_pref_t pref)
1244 {
1245 fprintf (f, " pref%d:a%d(r%d)<-hr%d@%d\n", pref->num,
1246 ALLOCNO_NUM (pref->allocno), ALLOCNO_REGNO (pref->allocno),
1247 pref->hard_regno, pref->freq);
1248 }
1249
1250 /* Print info about PREF into stderr. */
1251 void
1252 ira_debug_pref (ira_pref_t pref)
1253 {
1254 print_pref (stderr, pref);
1255 }
1256
1257 /* Print info about all prefs into file F. */
1258 static void
1259 print_prefs (FILE *f)
1260 {
1261 ira_pref_t pref;
1262 ira_pref_iterator pi;
1263
1264 FOR_EACH_PREF (pref, pi)
1265 print_pref (f, pref);
1266 }
1267
1268 /* Print info about all prefs into stderr. */
1269 void
1270 ira_debug_prefs (void)
1271 {
1272 print_prefs (stderr);
1273 }
1274
1275 /* Print info about prefs involving allocno A into file F. */
1276 static void
1277 print_allocno_prefs (FILE *f, ira_allocno_t a)
1278 {
1279 ira_pref_t pref;
1280
1281 fprintf (f, " a%d(r%d):", ALLOCNO_NUM (a), ALLOCNO_REGNO (a));
1282 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = pref->next_pref)
1283 fprintf (f, " pref%d:hr%d@%d", pref->num, pref->hard_regno, pref->freq);
1284 fprintf (f, "\n");
1285 }
1286
1287 /* Print info about prefs involving allocno A into stderr. */
1288 void
1289 ira_debug_allocno_prefs (ira_allocno_t a)
1290 {
1291 print_allocno_prefs (stderr, a);
1292 }
1293
1294 /* The function frees memory allocated for PREF. */
1295 static void
1296 finish_pref (ira_pref_t pref)
1297 {
1298 ira_prefs[pref->num] = NULL;
1299 pref_pool.remove (pref);
1300 }
1301
1302 /* Remove PREF from the list of allocno prefs and free memory for
1303 it. */
1304 void
1305 ira_remove_pref (ira_pref_t pref)
1306 {
1307 ira_pref_t cpref, prev;
1308
1309 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1310 fprintf (ira_dump_file, " Removing pref%d:hr%d@%d\n",
1311 pref->num, pref->hard_regno, pref->freq);
1312 for (prev = NULL, cpref = ALLOCNO_PREFS (pref->allocno);
1313 cpref != NULL;
1314 prev = cpref, cpref = cpref->next_pref)
1315 if (cpref == pref)
1316 break;
1317 ira_assert (cpref != NULL);
1318 if (prev == NULL)
1319 ALLOCNO_PREFS (pref->allocno) = pref->next_pref;
1320 else
1321 prev->next_pref = pref->next_pref;
1322 finish_pref (pref);
1323 }
1324
1325 /* Remove all prefs of allocno A. */
1326 void
1327 ira_remove_allocno_prefs (ira_allocno_t a)
1328 {
1329 ira_pref_t pref, next_pref;
1330
1331 for (pref = ALLOCNO_PREFS (a); pref != NULL; pref = next_pref)
1332 {
1333 next_pref = pref->next_pref;
1334 finish_pref (pref);
1335 }
1336 ALLOCNO_PREFS (a) = NULL;
1337 }
1338
1339 /* Free memory allocated for all prefs. */
1340 static void
1341 finish_prefs (void)
1342 {
1343 ira_pref_t pref;
1344 ira_pref_iterator pi;
1345
1346 FOR_EACH_PREF (pref, pi)
1347 finish_pref (pref);
1348 pref_vec.release ();
1349 pref_pool.release ();
1350 }
1351
1352
1353
1127 /* Pools for copies. */ 1354 /* Pools for copies. */
1128 static alloc_pool copy_pool; 1355 static object_allocator<ira_allocno_copy> copy_pool ("copies");
1129 1356
1130 /* Vec containing references to all created copies. It is a 1357 /* Vec containing references to all created copies. It is a
1131 container of array ira_copies. */ 1358 container of array ira_copies. */
1132 static VEC(ira_copy_t,heap) *copy_vec; 1359 static vec<ira_copy_t> copy_vec;
1133 1360
1134 /* The function initializes data concerning allocno copies. */ 1361 /* The function initializes data concerning allocno copies. */
1135 static void 1362 static void
1136 initiate_copies (void) 1363 initiate_copies (void)
1137 { 1364 {
1138 copy_pool 1365 copy_vec.create (get_max_uid ());
1139 = create_alloc_pool ("copies", sizeof (struct ira_allocno_copy), 100);
1140 copy_vec = VEC_alloc (ira_copy_t, heap, get_max_uid ());
1141 ira_copies = NULL; 1366 ira_copies = NULL;
1142 ira_copies_num = 0; 1367 ira_copies_num = 0;
1143 } 1368 }
1144 1369
1145 /* Return copy connecting A1 and A2 and originated from INSN of 1370 /* Return copy connecting A1 and A2 and originated from INSN of
1146 LOOP_TREE_NODE if any. */ 1371 LOOP_TREE_NODE if any. */
1147 static ira_copy_t 1372 static ira_copy_t
1148 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx insn, 1373 find_allocno_copy (ira_allocno_t a1, ira_allocno_t a2, rtx_insn *insn,
1149 ira_loop_tree_node_t loop_tree_node) 1374 ira_loop_tree_node_t loop_tree_node)
1150 { 1375 {
1151 ira_copy_t cp, next_cp; 1376 ira_copy_t cp, next_cp;
1152 ira_allocno_t another_a; 1377 ira_allocno_t another_a;
1153 1378
1174 1399
1175 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST, 1400 /* Create and return copy with given attributes LOOP_TREE_NODE, FIRST,
1176 SECOND, FREQ, CONSTRAINT_P, and INSN. */ 1401 SECOND, FREQ, CONSTRAINT_P, and INSN. */
1177 ira_copy_t 1402 ira_copy_t
1178 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq, 1403 ira_create_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1179 bool constraint_p, rtx insn, 1404 bool constraint_p, rtx_insn *insn,
1180 ira_loop_tree_node_t loop_tree_node) 1405 ira_loop_tree_node_t loop_tree_node)
1181 { 1406 {
1182 ira_copy_t cp; 1407 ira_copy_t cp;
1183 1408
1184 cp = (ira_copy_t) pool_alloc (copy_pool); 1409 cp = copy_pool.allocate ();
1185 cp->num = ira_copies_num; 1410 cp->num = ira_copies_num;
1186 cp->first = first; 1411 cp->first = first;
1187 cp->second = second; 1412 cp->second = second;
1188 cp->freq = freq; 1413 cp->freq = freq;
1189 cp->constraint_p = constraint_p; 1414 cp->constraint_p = constraint_p;
1190 cp->insn = insn; 1415 cp->insn = insn;
1191 cp->loop_tree_node = loop_tree_node; 1416 cp->loop_tree_node = loop_tree_node;
1192 VEC_safe_push (ira_copy_t, heap, copy_vec, cp); 1417 copy_vec.safe_push (cp);
1193 ira_copies = VEC_address (ira_copy_t, copy_vec); 1418 ira_copies = copy_vec.address ();
1194 ira_copies_num = VEC_length (ira_copy_t, copy_vec); 1419 ira_copies_num = copy_vec.length ();
1195 return cp; 1420 return cp;
1196 } 1421 }
1197 1422
1198 /* Attach a copy CP to allocnos involved into the copy. */ 1423 /* Attach a copy CP to allocnos involved into the copy. */
1199 void 1424 static void
1200 ira_add_allocno_copy_to_list (ira_copy_t cp) 1425 add_allocno_copy_to_list (ira_copy_t cp)
1201 { 1426 {
1202 ira_allocno_t first = cp->first, second = cp->second; 1427 ira_allocno_t first = cp->first, second = cp->second;
1203 1428
1204 cp->prev_first_allocno_copy = NULL; 1429 cp->prev_first_allocno_copy = NULL;
1205 cp->prev_second_allocno_copy = NULL; 1430 cp->prev_second_allocno_copy = NULL;
1223 ALLOCNO_COPIES (second) = cp; 1448 ALLOCNO_COPIES (second) = cp;
1224 } 1449 }
1225 1450
1226 /* Make a copy CP a canonical copy where number of the 1451 /* Make a copy CP a canonical copy where number of the
1227 first allocno is less than the second one. */ 1452 first allocno is less than the second one. */
1228 void 1453 static void
1229 ira_swap_allocno_copy_ends_if_necessary (ira_copy_t cp) 1454 swap_allocno_copy_ends_if_necessary (ira_copy_t cp)
1230 { 1455 {
1231 ira_allocno_t temp;
1232 ira_copy_t temp_cp;
1233
1234 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second)) 1456 if (ALLOCNO_NUM (cp->first) <= ALLOCNO_NUM (cp->second))
1235 return; 1457 return;
1236 1458
1237 temp = cp->first; 1459 std::swap (cp->first, cp->second);
1238 cp->first = cp->second; 1460 std::swap (cp->prev_first_allocno_copy, cp->prev_second_allocno_copy);
1239 cp->second = temp; 1461 std::swap (cp->next_first_allocno_copy, cp->next_second_allocno_copy);
1240
1241 temp_cp = cp->prev_first_allocno_copy;
1242 cp->prev_first_allocno_copy = cp->prev_second_allocno_copy;
1243 cp->prev_second_allocno_copy = temp_cp;
1244
1245 temp_cp = cp->next_first_allocno_copy;
1246 cp->next_first_allocno_copy = cp->next_second_allocno_copy;
1247 cp->next_second_allocno_copy = temp_cp;
1248 } 1462 }
1249 1463
1250 /* Create (or update frequency if the copy already exists) and return 1464 /* Create (or update frequency if the copy already exists) and return
1251 the copy of allocnos FIRST and SECOND with frequency FREQ 1465 the copy of allocnos FIRST and SECOND with frequency FREQ
1252 corresponding to move insn INSN (if any) and originated from 1466 corresponding to move insn INSN (if any) and originated from
1253 LOOP_TREE_NODE. */ 1467 LOOP_TREE_NODE. */
1254 ira_copy_t 1468 ira_copy_t
1255 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq, 1469 ira_add_allocno_copy (ira_allocno_t first, ira_allocno_t second, int freq,
1256 bool constraint_p, rtx insn, 1470 bool constraint_p, rtx_insn *insn,
1257 ira_loop_tree_node_t loop_tree_node) 1471 ira_loop_tree_node_t loop_tree_node)
1258 { 1472 {
1259 ira_copy_t cp; 1473 ira_copy_t cp;
1260 1474
1261 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL) 1475 if ((cp = find_allocno_copy (first, second, insn, loop_tree_node)) != NULL)
1264 return cp; 1478 return cp;
1265 } 1479 }
1266 cp = ira_create_copy (first, second, freq, constraint_p, insn, 1480 cp = ira_create_copy (first, second, freq, constraint_p, insn,
1267 loop_tree_node); 1481 loop_tree_node);
1268 ira_assert (first != NULL && second != NULL); 1482 ira_assert (first != NULL && second != NULL);
1269 ira_add_allocno_copy_to_list (cp); 1483 add_allocno_copy_to_list (cp);
1270 ira_swap_allocno_copy_ends_if_necessary (cp); 1484 swap_allocno_copy_ends_if_necessary (cp);
1271 return cp; 1485 return cp;
1272 } 1486 }
1273 1487
1274 /* Print info about copy CP into file F. */ 1488 /* Print info about copy CP into file F. */
1275 static void 1489 static void
1280 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq, 1494 ALLOCNO_NUM (cp->second), ALLOCNO_REGNO (cp->second), cp->freq,
1281 cp->insn != NULL 1495 cp->insn != NULL
1282 ? "move" : cp->constraint_p ? "constraint" : "shuffle"); 1496 ? "move" : cp->constraint_p ? "constraint" : "shuffle");
1283 } 1497 }
1284 1498
1499 DEBUG_FUNCTION void
1500 debug (ira_allocno_copy &ref)
1501 {
1502 print_copy (stderr, &ref);
1503 }
1504
1505 DEBUG_FUNCTION void
1506 debug (ira_allocno_copy *ptr)
1507 {
1508 if (ptr)
1509 debug (*ptr);
1510 else
1511 fprintf (stderr, "<nil>\n");
1512 }
1513
1285 /* Print info about copy CP into stderr. */ 1514 /* Print info about copy CP into stderr. */
1286 void 1515 void
1287 ira_debug_copy (ira_copy_t cp) 1516 ira_debug_copy (ira_copy_t cp)
1288 { 1517 {
1289 print_copy (stderr, cp); 1518 print_copy (stderr, cp);
1333 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq); 1562 ALLOCNO_NUM (another_a), ALLOCNO_REGNO (another_a), cp->freq);
1334 } 1563 }
1335 fprintf (f, "\n"); 1564 fprintf (f, "\n");
1336 } 1565 }
1337 1566
1567 DEBUG_FUNCTION void
1568 debug (ira_allocno &ref)
1569 {
1570 print_allocno_copies (stderr, &ref);
1571 }
1572
1573 DEBUG_FUNCTION void
1574 debug (ira_allocno *ptr)
1575 {
1576 if (ptr)
1577 debug (*ptr);
1578 else
1579 fprintf (stderr, "<nil>\n");
1580 }
1581
1582
1338 /* Print info about copies involving allocno A into stderr. */ 1583 /* Print info about copies involving allocno A into stderr. */
1339 void 1584 void
1340 ira_debug_allocno_copies (ira_allocno_t a) 1585 ira_debug_allocno_copies (ira_allocno_t a)
1341 { 1586 {
1342 print_allocno_copies (stderr, a); 1587 print_allocno_copies (stderr, a);
1344 1589
1345 /* The function frees memory allocated for copy CP. */ 1590 /* The function frees memory allocated for copy CP. */
1346 static void 1591 static void
1347 finish_copy (ira_copy_t cp) 1592 finish_copy (ira_copy_t cp)
1348 { 1593 {
1349 pool_free (copy_pool, cp); 1594 copy_pool.remove (cp);
1350 } 1595 }
1351 1596
1352 1597
1353 /* Free memory allocated for all copies. */ 1598 /* Free memory allocated for all copies. */
1354 static void 1599 static void
1357 ira_copy_t cp; 1602 ira_copy_t cp;
1358 ira_copy_iterator ci; 1603 ira_copy_iterator ci;
1359 1604
1360 FOR_EACH_COPY (cp, ci) 1605 FOR_EACH_COPY (cp, ci)
1361 finish_copy (cp); 1606 finish_copy (cp);
1362 VEC_free (ira_copy_t, heap, copy_vec); 1607 copy_vec.release ();
1363 free_alloc_pool (copy_pool); 1608 copy_pool.release ();
1364 } 1609 }
1365 1610
1366 1611
1367 1612
1368 /* Pools for cost vectors. It is defined only for cover classes. */ 1613 /* Pools for cost vectors. It is defined only for allocno classes. */
1369 static alloc_pool cost_vector_pool[N_REG_CLASSES]; 1614 static pool_allocator *cost_vector_pool[N_REG_CLASSES];
1370 1615
1371 /* The function initiates work with hard register cost vectors. It 1616 /* The function initiates work with hard register cost vectors. It
1372 creates allocation pool for each cover class. */ 1617 creates allocation pool for each allocno class. */
1373 static void 1618 static void
1374 initiate_cost_vectors (void) 1619 initiate_cost_vectors (void)
1375 { 1620 {
1376 int i; 1621 int i;
1377 enum reg_class cover_class; 1622 enum reg_class aclass;
1378 1623
1379 for (i = 0; i < ira_reg_class_cover_size; i++) 1624 for (i = 0; i < ira_allocno_classes_num; i++)
1380 { 1625 {
1381 cover_class = ira_reg_class_cover[i]; 1626 aclass = ira_allocno_classes[i];
1382 cost_vector_pool[cover_class] 1627 cost_vector_pool[aclass] = new pool_allocator
1383 = create_alloc_pool ("cost vectors", 1628 ("cost vectors", sizeof (int) * (ira_class_hard_regs_num[aclass]));
1384 sizeof (int) 1629 }
1385 * ira_class_hard_regs_num[cover_class], 1630 }
1386 100); 1631
1387 } 1632 /* Allocate and return a cost vector VEC for ACLASS. */
1388 }
1389
1390 /* Allocate and return a cost vector VEC for COVER_CLASS. */
1391 int * 1633 int *
1392 ira_allocate_cost_vector (enum reg_class cover_class) 1634 ira_allocate_cost_vector (reg_class_t aclass)
1393 { 1635 {
1394 return (int *) pool_alloc (cost_vector_pool[cover_class]); 1636 return (int*) cost_vector_pool[(int) aclass]->allocate ();
1395 } 1637 }
1396 1638
1397 /* Free a cost vector VEC for COVER_CLASS. */ 1639 /* Free a cost vector VEC for ACLASS. */
1398 void 1640 void
1399 ira_free_cost_vector (int *vec, enum reg_class cover_class) 1641 ira_free_cost_vector (int *vec, reg_class_t aclass)
1400 { 1642 {
1401 ira_assert (vec != NULL); 1643 ira_assert (vec != NULL);
1402 pool_free (cost_vector_pool[cover_class], vec); 1644 cost_vector_pool[(int) aclass]->remove (vec);
1403 } 1645 }
1404 1646
1405 /* Finish work with hard register cost vectors. Release allocation 1647 /* Finish work with hard register cost vectors. Release allocation
1406 pool for each cover class. */ 1648 pool for each allocno class. */
1407 static void 1649 static void
1408 finish_cost_vectors (void) 1650 finish_cost_vectors (void)
1409 { 1651 {
1410 int i; 1652 int i;
1411 enum reg_class cover_class; 1653 enum reg_class aclass;
1412 1654
1413 for (i = 0; i < ira_reg_class_cover_size; i++) 1655 for (i = 0; i < ira_allocno_classes_num; i++)
1414 { 1656 {
1415 cover_class = ira_reg_class_cover[i]; 1657 aclass = ira_allocno_classes[i];
1416 free_alloc_pool (cost_vector_pool[cover_class]); 1658 delete cost_vector_pool[aclass];
1417 } 1659 }
1418 } 1660 }
1419 1661
1420 1662
1663
1664 /* Compute a post-ordering of the reverse control flow of the loop body
1665 designated by the children nodes of LOOP_NODE, whose body nodes in
1666 pre-order are input as LOOP_PREORDER. Return a VEC with a post-order
1667 of the reverse loop body.
1668
1669 For the post-order of the reverse CFG, we visit the basic blocks in
1670 LOOP_PREORDER array in the reverse order of where they appear.
1671 This is important: We do not just want to compute a post-order of
1672 the reverse CFG, we want to make a best-guess for a visiting order that
1673 minimizes the number of chain elements per allocno live range. If the
1674 blocks would be visited in a different order, we would still compute a
1675 correct post-ordering but it would be less likely that two nodes
1676 connected by an edge in the CFG are neighbors in the topsort. */
1677
1678 static vec<ira_loop_tree_node_t>
1679 ira_loop_tree_body_rev_postorder (ira_loop_tree_node_t loop_node ATTRIBUTE_UNUSED,
1680 vec<ira_loop_tree_node_t> loop_preorder)
1681 {
1682 vec<ira_loop_tree_node_t> topsort_nodes = vNULL;
1683 unsigned int n_loop_preorder;
1684
1685 n_loop_preorder = loop_preorder.length ();
1686 if (n_loop_preorder != 0)
1687 {
1688 ira_loop_tree_node_t subloop_node;
1689 unsigned int i;
1690 auto_vec<ira_loop_tree_node_t> dfs_stack;
1691
1692 /* This is a bit of strange abuse of the BB_VISITED flag: We use
1693 the flag to mark blocks we still have to visit to add them to
1694 our post-order. Define an alias to avoid confusion. */
1695 #define BB_TO_VISIT BB_VISITED
1696
1697 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1698 {
1699 gcc_checking_assert (! (subloop_node->bb->flags & BB_TO_VISIT));
1700 subloop_node->bb->flags |= BB_TO_VISIT;
1701 }
1702
1703 topsort_nodes.create (n_loop_preorder);
1704 dfs_stack.create (n_loop_preorder);
1705
1706 FOR_EACH_VEC_ELT_REVERSE (loop_preorder, i, subloop_node)
1707 {
1708 if (! (subloop_node->bb->flags & BB_TO_VISIT))
1709 continue;
1710
1711 subloop_node->bb->flags &= ~BB_TO_VISIT;
1712 dfs_stack.quick_push (subloop_node);
1713 while (! dfs_stack.is_empty ())
1714 {
1715 edge e;
1716 edge_iterator ei;
1717
1718 ira_loop_tree_node_t n = dfs_stack.last ();
1719 FOR_EACH_EDGE (e, ei, n->bb->preds)
1720 {
1721 ira_loop_tree_node_t pred_node;
1722 basic_block pred_bb = e->src;
1723
1724 if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
1725 continue;
1726
1727 pred_node = IRA_BB_NODE_BY_INDEX (pred_bb->index);
1728 if (pred_node != n
1729 && (pred_node->bb->flags & BB_TO_VISIT))
1730 {
1731 pred_node->bb->flags &= ~BB_TO_VISIT;
1732 dfs_stack.quick_push (pred_node);
1733 }
1734 }
1735 if (n == dfs_stack.last ())
1736 {
1737 dfs_stack.pop ();
1738 topsort_nodes.quick_push (n);
1739 }
1740 }
1741 }
1742
1743 #undef BB_TO_VISIT
1744 }
1745
1746 gcc_assert (topsort_nodes.length () == n_loop_preorder);
1747 return topsort_nodes;
1748 }
1421 1749
1422 /* The current loop tree node and its regno allocno map. */ 1750 /* The current loop tree node and its regno allocno map. */
1423 ira_loop_tree_node_t ira_curr_loop_tree_node; 1751 ira_loop_tree_node_t ira_curr_loop_tree_node;
1424 ira_allocno_t *ira_curr_regno_allocno_map; 1752 ira_allocno_t *ira_curr_regno_allocno_map;
1425 1753
1426 /* This recursive function traverses loop tree with root LOOP_NODE 1754 /* This recursive function traverses loop tree with root LOOP_NODE
1427 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC 1755 calling non-null functions PREORDER_FUNC and POSTORDER_FUNC
1428 correspondingly in preorder and postorder. The function sets up 1756 correspondingly in preorder and postorder. The function sets up
1429 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P, 1757 IRA_CURR_LOOP_TREE_NODE and IRA_CURR_REGNO_ALLOCNO_MAP. If BB_P,
1430 basic block nodes of LOOP_NODE is also processed (before its 1758 basic block nodes of LOOP_NODE is also processed (before its
1431 subloop nodes). */ 1759 subloop nodes).
1760
1761 If BB_P is set and POSTORDER_FUNC is given, the basic blocks in
1762 the loop are passed in the *reverse* post-order of the *reverse*
1763 CFG. This is only used by ira_create_allocno_live_ranges, which
1764 wants to visit basic blocks in this order to minimize the number
1765 of elements per live range chain.
1766 Note that the loop tree nodes are still visited in the normal,
1767 forward post-order of the loop tree. */
1768
1432 void 1769 void
1433 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node, 1770 ira_traverse_loop_tree (bool bb_p, ira_loop_tree_node_t loop_node,
1434 void (*preorder_func) (ira_loop_tree_node_t), 1771 void (*preorder_func) (ira_loop_tree_node_t),
1435 void (*postorder_func) (ira_loop_tree_node_t)) 1772 void (*postorder_func) (ira_loop_tree_node_t))
1436 { 1773 {
1442 1779
1443 if (preorder_func != NULL) 1780 if (preorder_func != NULL)
1444 (*preorder_func) (loop_node); 1781 (*preorder_func) (loop_node);
1445 1782
1446 if (bb_p) 1783 if (bb_p)
1447 for (subloop_node = loop_node->children; 1784 {
1448 subloop_node != NULL; 1785 auto_vec<ira_loop_tree_node_t> loop_preorder;
1449 subloop_node = subloop_node->next) 1786 unsigned int i;
1450 if (subloop_node->bb != NULL) 1787
1451 { 1788 /* Add all nodes to the set of nodes to visit. The IRA loop tree
1452 if (preorder_func != NULL) 1789 is set up such that nodes in the loop body appear in a pre-order
1453 (*preorder_func) (subloop_node); 1790 of their place in the CFG. */
1454 1791 for (subloop_node = loop_node->children;
1455 if (postorder_func != NULL) 1792 subloop_node != NULL;
1793 subloop_node = subloop_node->next)
1794 if (subloop_node->bb != NULL)
1795 loop_preorder.safe_push (subloop_node);
1796
1797 if (preorder_func != NULL)
1798 FOR_EACH_VEC_ELT (loop_preorder, i, subloop_node)
1799 (*preorder_func) (subloop_node);
1800
1801 if (postorder_func != NULL)
1802 {
1803 vec<ira_loop_tree_node_t> loop_rev_postorder =
1804 ira_loop_tree_body_rev_postorder (loop_node, loop_preorder);
1805 FOR_EACH_VEC_ELT_REVERSE (loop_rev_postorder, i, subloop_node)
1456 (*postorder_func) (subloop_node); 1806 (*postorder_func) (subloop_node);
1457 } 1807 loop_rev_postorder.release ();
1808 }
1809 }
1458 1810
1459 for (subloop_node = loop_node->subloops; 1811 for (subloop_node = loop_node->subloops;
1460 subloop_node != NULL; 1812 subloop_node != NULL;
1461 subloop_node = subloop_node->subloop_next) 1813 subloop_node = subloop_node->subloop_next)
1462 { 1814 {
1477 /* The basic block currently being processed. */ 1829 /* The basic block currently being processed. */
1478 static basic_block curr_bb; 1830 static basic_block curr_bb;
1479 1831
1480 /* This recursive function creates allocnos corresponding to 1832 /* This recursive function creates allocnos corresponding to
1481 pseudo-registers containing in X. True OUTPUT_P means that X is 1833 pseudo-registers containing in X. True OUTPUT_P means that X is
1482 a lvalue. */ 1834 an lvalue. PARENT corresponds to the parent expression of X. */
1483 static void 1835 static void
1484 create_insn_allocnos (rtx x, bool output_p) 1836 create_insn_allocnos (rtx x, rtx outer, bool output_p)
1485 { 1837 {
1486 int i, j; 1838 int i, j;
1487 const char *fmt; 1839 const char *fmt;
1488 enum rtx_code code = GET_CODE (x); 1840 enum rtx_code code = GET_CODE (x);
1489 1841
1494 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER) 1846 if ((regno = REGNO (x)) >= FIRST_PSEUDO_REGISTER)
1495 { 1847 {
1496 ira_allocno_t a; 1848 ira_allocno_t a;
1497 1849
1498 if ((a = ira_curr_regno_allocno_map[regno]) == NULL) 1850 if ((a = ira_curr_regno_allocno_map[regno]) == NULL)
1499 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node); 1851 {
1852 a = ira_create_allocno (regno, false, ira_curr_loop_tree_node);
1853 if (outer != NULL && GET_CODE (outer) == SUBREG)
1854 {
1855 machine_mode wmode = GET_MODE (outer);
1856 if (partial_subreg_p (ALLOCNO_WMODE (a), wmode))
1857 ALLOCNO_WMODE (a) = wmode;
1858 }
1859 }
1500 1860
1501 ALLOCNO_NREFS (a)++; 1861 ALLOCNO_NREFS (a)++;
1502 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb); 1862 ALLOCNO_FREQ (a) += REG_FREQ_FROM_BB (curr_bb);
1503 if (output_p) 1863 if (output_p)
1504 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno); 1864 bitmap_set_bit (ira_curr_loop_tree_node->modified_regnos, regno);
1505 } 1865 }
1506 return; 1866 return;
1507 } 1867 }
1508 else if (code == SET) 1868 else if (code == SET)
1509 { 1869 {
1510 create_insn_allocnos (SET_DEST (x), true); 1870 create_insn_allocnos (SET_DEST (x), NULL, true);
1511 create_insn_allocnos (SET_SRC (x), false); 1871 create_insn_allocnos (SET_SRC (x), NULL, false);
1512 return; 1872 return;
1513 } 1873 }
1514 else if (code == CLOBBER) 1874 else if (code == CLOBBER)
1515 { 1875 {
1516 create_insn_allocnos (XEXP (x, 0), true); 1876 create_insn_allocnos (XEXP (x, 0), NULL, true);
1517 return; 1877 return;
1518 } 1878 }
1519 else if (code == MEM) 1879 else if (code == MEM)
1520 { 1880 {
1521 create_insn_allocnos (XEXP (x, 0), false); 1881 create_insn_allocnos (XEXP (x, 0), NULL, false);
1522 return; 1882 return;
1523 } 1883 }
1524 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC || 1884 else if (code == PRE_DEC || code == POST_DEC || code == PRE_INC ||
1525 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY) 1885 code == POST_INC || code == POST_MODIFY || code == PRE_MODIFY)
1526 { 1886 {
1527 create_insn_allocnos (XEXP (x, 0), true); 1887 create_insn_allocnos (XEXP (x, 0), NULL, true);
1528 create_insn_allocnos (XEXP (x, 0), false); 1888 create_insn_allocnos (XEXP (x, 0), NULL, false);
1529 return; 1889 return;
1530 } 1890 }
1531 1891
1532 fmt = GET_RTX_FORMAT (code); 1892 fmt = GET_RTX_FORMAT (code);
1533 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 1893 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1534 { 1894 {
1535 if (fmt[i] == 'e') 1895 if (fmt[i] == 'e')
1536 create_insn_allocnos (XEXP (x, i), output_p); 1896 create_insn_allocnos (XEXP (x, i), x, output_p);
1537 else if (fmt[i] == 'E') 1897 else if (fmt[i] == 'E')
1538 for (j = 0; j < XVECLEN (x, i); j++) 1898 for (j = 0; j < XVECLEN (x, i); j++)
1539 create_insn_allocnos (XVECEXP (x, i, j), output_p); 1899 create_insn_allocnos (XVECEXP (x, i, j), x, output_p);
1540 } 1900 }
1541 } 1901 }
1542 1902
1543 /* Create allocnos corresponding to pseudo-registers living in the 1903 /* Create allocnos corresponding to pseudo-registers living in the
1544 basic block represented by the corresponding loop tree node 1904 basic block represented by the corresponding loop tree node
1545 BB_NODE. */ 1905 BB_NODE. */
1546 static void 1906 static void
1547 create_bb_allocnos (ira_loop_tree_node_t bb_node) 1907 create_bb_allocnos (ira_loop_tree_node_t bb_node)
1548 { 1908 {
1549 basic_block bb; 1909 basic_block bb;
1550 rtx insn; 1910 rtx_insn *insn;
1551 unsigned int i; 1911 unsigned int i;
1552 bitmap_iterator bi; 1912 bitmap_iterator bi;
1553 1913
1554 curr_bb = bb = bb_node->bb; 1914 curr_bb = bb = bb_node->bb;
1555 ira_assert (bb != NULL); 1915 ira_assert (bb != NULL);
1556 FOR_BB_INSNS_REVERSE (bb, insn) 1916 FOR_BB_INSNS_REVERSE (bb, insn)
1557 if (NONDEBUG_INSN_P (insn)) 1917 if (NONDEBUG_INSN_P (insn))
1558 create_insn_allocnos (PATTERN (insn), false); 1918 create_insn_allocnos (PATTERN (insn), NULL, false);
1559 /* It might be a allocno living through from one subloop to 1919 /* It might be a allocno living through from one subloop to
1560 another. */ 1920 another. */
1561 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (bb), FIRST_PSEUDO_REGISTER, i, bi) 1921 EXECUTE_IF_SET_IN_REG_SET (df_get_live_in (bb), FIRST_PSEUDO_REGISTER, i, bi)
1562 if (ira_curr_regno_allocno_map[i] == NULL) 1922 if (ira_curr_regno_allocno_map[i] == NULL)
1563 ira_create_allocno (i, false, ira_curr_loop_tree_node); 1923 ira_create_allocno (i, false, ira_curr_loop_tree_node);
1564 } 1924 }
1565 1925
1566 /* Create allocnos corresponding to pseudo-registers living on edge E 1926 /* Create allocnos corresponding to pseudo-registers living on edge E
1572 unsigned int i; 1932 unsigned int i;
1573 bitmap live_in_regs, border_allocnos; 1933 bitmap live_in_regs, border_allocnos;
1574 bitmap_iterator bi; 1934 bitmap_iterator bi;
1575 ira_loop_tree_node_t parent; 1935 ira_loop_tree_node_t parent;
1576 1936
1577 live_in_regs = DF_LR_IN (e->dest); 1937 live_in_regs = df_get_live_in (e->dest);
1578 border_allocnos = ira_curr_loop_tree_node->border_allocnos; 1938 border_allocnos = ira_curr_loop_tree_node->border_allocnos;
1579 EXECUTE_IF_SET_IN_REG_SET (DF_LR_OUT (e->src), 1939 EXECUTE_IF_SET_IN_REG_SET (df_get_live_out (e->src),
1580 FIRST_PSEUDO_REGISTER, i, bi) 1940 FIRST_PSEUDO_REGISTER, i, bi)
1581 if (bitmap_bit_p (live_in_regs, i)) 1941 if (bitmap_bit_p (live_in_regs, i))
1582 { 1942 {
1583 if (ira_curr_regno_allocno_map[i] == NULL) 1943 if (ira_curr_regno_allocno_map[i] == NULL)
1584 { 1944 {
1605 else if (loop_node != ira_loop_tree_root) 1965 else if (loop_node != ira_loop_tree_root)
1606 { 1966 {
1607 int i; 1967 int i;
1608 edge_iterator ei; 1968 edge_iterator ei;
1609 edge e; 1969 edge e;
1610 VEC (edge, heap) *edges; 1970 vec<edge> edges;
1611 1971
1972 ira_assert (current_loops != NULL);
1612 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds) 1973 FOR_EACH_EDGE (e, ei, loop_node->loop->header->preds)
1613 if (e->src != loop_node->loop->latch) 1974 if (e->src != loop_node->loop->latch)
1614 create_loop_allocnos (e); 1975 create_loop_allocnos (e);
1615 1976
1616 edges = get_loop_exit_edges (loop_node->loop); 1977 edges = get_loop_exit_edges (loop_node->loop);
1617 FOR_EACH_VEC_ELT (edge, edges, i, e) 1978 FOR_EACH_VEC_ELT (edges, i, e)
1618 create_loop_allocnos (e); 1979 create_loop_allocnos (e);
1619 VEC_free (edge, heap, edges); 1980 edges.release ();
1620 } 1981 }
1621 } 1982 }
1622 1983
1623 /* Propagate information about allocnos modified inside the loop given 1984 /* Propagate information about allocnos modified inside the loop given
1624 by its LOOP_TREE_NODE to its parent. */ 1985 by its LOOP_TREE_NODE to its parent. */
1642 propagate_allocno_info (void) 2003 propagate_allocno_info (void)
1643 { 2004 {
1644 int i; 2005 int i;
1645 ira_allocno_t a, parent_a; 2006 ira_allocno_t a, parent_a;
1646 ira_loop_tree_node_t parent; 2007 ira_loop_tree_node_t parent;
1647 enum reg_class cover_class; 2008 enum reg_class aclass;
1648 2009
1649 if (flag_ira_region != IRA_REGION_ALL 2010 if (flag_ira_region != IRA_REGION_ALL
1650 && flag_ira_region != IRA_REGION_MIXED) 2011 && flag_ira_region != IRA_REGION_MIXED)
1651 return; 2012 return;
1652 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--) 2013 for (i = max_reg_num () - 1; i >= FIRST_PSEUDO_REGISTER; i--)
1666 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a); 2027 ALLOCNO_FREQ (parent_a) += ALLOCNO_FREQ (a);
1667 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a); 2028 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
1668 merge_hard_reg_conflicts (a, parent_a, true); 2029 merge_hard_reg_conflicts (a, parent_a, true);
1669 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 2030 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
1670 += ALLOCNO_CALLS_CROSSED_NUM (a); 2031 += ALLOCNO_CALLS_CROSSED_NUM (a);
2032 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
2033 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2034 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
2035 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
1671 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 2036 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
1672 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 2037 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
1673 cover_class = ALLOCNO_COVER_CLASS (a); 2038 aclass = ALLOCNO_CLASS (a);
1674 ira_assert (cover_class == ALLOCNO_COVER_CLASS (parent_a)); 2039 ira_assert (aclass == ALLOCNO_CLASS (parent_a));
1675 ira_allocate_and_accumulate_costs 2040 ira_allocate_and_accumulate_costs
1676 (&ALLOCNO_HARD_REG_COSTS (parent_a), cover_class, 2041 (&ALLOCNO_HARD_REG_COSTS (parent_a), aclass,
1677 ALLOCNO_HARD_REG_COSTS (a)); 2042 ALLOCNO_HARD_REG_COSTS (a));
1678 ira_allocate_and_accumulate_costs 2043 ira_allocate_and_accumulate_costs
1679 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a), 2044 (&ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a),
1680 cover_class, 2045 aclass,
1681 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)); 2046 ALLOCNO_CONFLICT_HARD_REG_COSTS (a));
1682 ALLOCNO_COVER_CLASS_COST (parent_a) 2047 ALLOCNO_CLASS_COST (parent_a)
1683 += ALLOCNO_COVER_CLASS_COST (a); 2048 += ALLOCNO_CLASS_COST (a);
1684 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a); 2049 ALLOCNO_MEMORY_COST (parent_a) += ALLOCNO_MEMORY_COST (a);
1685 } 2050 }
1686 } 2051 }
1687 2052
1688 /* Create allocnos corresponding to pseudo-registers in the current 2053 /* Create allocnos corresponding to pseudo-registers in the current
1776 pressure. */ 2141 pressure. */
1777 static bool 2142 static bool
1778 low_pressure_loop_node_p (ira_loop_tree_node_t node) 2143 low_pressure_loop_node_p (ira_loop_tree_node_t node)
1779 { 2144 {
1780 int i; 2145 int i;
1781 enum reg_class cover_class; 2146 enum reg_class pclass;
1782 2147
1783 if (node->bb != NULL) 2148 if (node->bb != NULL)
1784 return false; 2149 return false;
1785 2150
1786 for (i = 0; i < ira_reg_class_cover_size; i++) 2151 for (i = 0; i < ira_pressure_classes_num; i++)
1787 { 2152 {
1788 cover_class = ira_reg_class_cover[i]; 2153 pclass = ira_pressure_classes[i];
1789 if (node->reg_pressure[cover_class] 2154 if (node->reg_pressure[pclass] > ira_class_hard_regs_num[pclass]
1790 > ira_available_class_regs[cover_class]) 2155 && ira_class_hard_regs_num[pclass] > 1)
1791 return false; 2156 return false;
1792 } 2157 }
1793 return true; 2158 return true;
1794 } 2159 }
2160
2161 #ifdef STACK_REGS
2162 /* Return TRUE if LOOP has a complex enter or exit edge. We don't
2163 form a region from such loop if the target use stack register
2164 because reg-stack.c can not deal with such edges. */
2165 static bool
2166 loop_with_complex_edge_p (struct loop *loop)
2167 {
2168 int i;
2169 edge_iterator ei;
2170 edge e;
2171 vec<edge> edges;
2172 bool res;
2173
2174 FOR_EACH_EDGE (e, ei, loop->header->preds)
2175 if (e->flags & EDGE_EH)
2176 return true;
2177 edges = get_loop_exit_edges (loop);
2178 res = false;
2179 FOR_EACH_VEC_ELT (edges, i, e)
2180 if (e->flags & EDGE_COMPLEX)
2181 {
2182 res = true;
2183 break;
2184 }
2185 edges.release ();
2186 return res;
2187 }
2188 #endif
1795 2189
1796 /* Sort loops for marking them for removal. We put already marked 2190 /* Sort loops for marking them for removal. We put already marked
1797 loops first, then less frequent loops next, and then outer loops 2191 loops first, then less frequent loops next, and then outer loops
1798 next. */ 2192 next. */
1799 static int 2193 static int
1811 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0) 2205 if ((diff = l1->loop->header->frequency - l2->loop->header->frequency) != 0)
1812 return diff; 2206 return diff;
1813 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0) 2207 if ((diff = (int) loop_depth (l1->loop) - (int) loop_depth (l2->loop)) != 0)
1814 return diff; 2208 return diff;
1815 /* Make sorting stable. */ 2209 /* Make sorting stable. */
1816 return l1->loop->num - l2->loop->num; 2210 return l1->loop_num - l2->loop_num;
1817 } 2211 }
1818
1819 2212
1820 /* Mark loops which should be removed from regional allocation. We 2213 /* Mark loops which should be removed from regional allocation. We
1821 remove a loop with low register pressure inside another loop with 2214 remove a loop with low register pressure inside another loop with
1822 register pressure. In this case a separate allocation of the loop 2215 register pressure. In this case a separate allocation of the loop
1823 hardly helps (for irregular register file architecture it could 2216 hardly helps (for irregular register file architecture it could
1824 help by choosing a better hard register in the loop but we prefer 2217 help by choosing a better hard register in the loop but we prefer
1825 faster allocation even in this case). We also remove cheap loops 2218 faster allocation even in this case). We also remove cheap loops
1826 if there are more than IRA_MAX_LOOPS_NUM of them. */ 2219 if there are more than IRA_MAX_LOOPS_NUM of them. Loop with EH
2220 exit or enter edges are removed too because the allocation might
2221 require put pseudo moves on the EH edges (we could still do this
2222 for pseudos with caller saved hard registers in some cases but it
2223 is impossible to say here or during top-down allocation pass what
2224 hard register the pseudos get finally). */
1827 static void 2225 static void
1828 mark_loops_for_removal (void) 2226 mark_loops_for_removal (void)
1829 { 2227 {
1830 int i, n; 2228 int i, n;
1831 ira_loop_tree_node_t *sorted_loops; 2229 ira_loop_tree_node_t *sorted_loops;
1832 loop_p loop; 2230 loop_p loop;
1833 2231
2232 ira_assert (current_loops != NULL);
1834 sorted_loops 2233 sorted_loops
1835 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t) 2234 = (ira_loop_tree_node_t *) ira_allocate (sizeof (ira_loop_tree_node_t)
1836 * VEC_length (loop_p, 2235 * number_of_loops (cfun));
1837 ira_loops.larray)); 2236 for (n = i = 0; vec_safe_iterate (get_loops (cfun), i, &loop); i++)
1838 for (n = i = 0; VEC_iterate (loop_p, ira_loops.larray, i, loop); i++)
1839 if (ira_loop_nodes[i].regno_allocno_map != NULL) 2237 if (ira_loop_nodes[i].regno_allocno_map != NULL)
1840 { 2238 {
1841 if (ira_loop_nodes[i].parent == NULL) 2239 if (ira_loop_nodes[i].parent == NULL)
1842 { 2240 {
1843 /* Don't remove the root. */ 2241 /* Don't remove the root. */
1844 ira_loop_nodes[i].to_remove_p = false; 2242 ira_loop_nodes[i].to_remove_p = false;
1845 continue; 2243 continue;
1846 } 2244 }
1847 sorted_loops[n++] = &ira_loop_nodes[i]; 2245 sorted_loops[n++] = &ira_loop_nodes[i];
1848 ira_loop_nodes[i].to_remove_p 2246 ira_loop_nodes[i].to_remove_p
1849 = (low_pressure_loop_node_p (ira_loop_nodes[i].parent) 2247 = ((low_pressure_loop_node_p (ira_loop_nodes[i].parent)
1850 && low_pressure_loop_node_p (&ira_loop_nodes[i])); 2248 && low_pressure_loop_node_p (&ira_loop_nodes[i]))
2249 #ifdef STACK_REGS
2250 || loop_with_complex_edge_p (ira_loop_nodes[i].loop)
2251 #endif
2252 );
1851 } 2253 }
1852 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func); 2254 qsort (sorted_loops, n, sizeof (ira_loop_tree_node_t), loop_compare_func);
1853 for (i = 0; n - i + 1 > IRA_MAX_LOOPS_NUM; i++) 2255 for (i = 0; i < n - IRA_MAX_LOOPS_NUM; i++)
1854 { 2256 {
1855 sorted_loops[i]->to_remove_p = true; 2257 sorted_loops[i]->to_remove_p = true;
1856 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 2258 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1857 fprintf 2259 fprintf
1858 (ira_dump_file, 2260 (ira_dump_file,
1859 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n", 2261 " Mark loop %d (header %d, freq %d, depth %d) for removal (%s)\n",
1860 sorted_loops[i]->loop->num, sorted_loops[i]->loop->header->index, 2262 sorted_loops[i]->loop_num, sorted_loops[i]->loop->header->index,
1861 sorted_loops[i]->loop->header->frequency, 2263 sorted_loops[i]->loop->header->frequency,
1862 loop_depth (sorted_loops[i]->loop), 2264 loop_depth (sorted_loops[i]->loop),
1863 low_pressure_loop_node_p (sorted_loops[i]->parent) 2265 low_pressure_loop_node_p (sorted_loops[i]->parent)
1864 && low_pressure_loop_node_p (sorted_loops[i]) 2266 && low_pressure_loop_node_p (sorted_loops[i])
1865 ? "low pressure" : "cheap loop"); 2267 ? "low pressure" : "cheap loop");
1872 mark_all_loops_for_removal (void) 2274 mark_all_loops_for_removal (void)
1873 { 2275 {
1874 int i; 2276 int i;
1875 loop_p loop; 2277 loop_p loop;
1876 2278
1877 FOR_EACH_VEC_ELT (loop_p, ira_loops.larray, i, loop) 2279 ira_assert (current_loops != NULL);
2280 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
1878 if (ira_loop_nodes[i].regno_allocno_map != NULL) 2281 if (ira_loop_nodes[i].regno_allocno_map != NULL)
1879 { 2282 {
1880 if (ira_loop_nodes[i].parent == NULL) 2283 if (ira_loop_nodes[i].parent == NULL)
1881 { 2284 {
1882 /* Don't remove the root. */ 2285 /* Don't remove the root. */
1886 ira_loop_nodes[i].to_remove_p = true; 2289 ira_loop_nodes[i].to_remove_p = true;
1887 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL) 2290 if (internal_flag_ira_verbose > 1 && ira_dump_file != NULL)
1888 fprintf 2291 fprintf
1889 (ira_dump_file, 2292 (ira_dump_file,
1890 " Mark loop %d (header %d, freq %d, depth %d) for removal\n", 2293 " Mark loop %d (header %d, freq %d, depth %d) for removal\n",
1891 ira_loop_nodes[i].loop->num, 2294 ira_loop_nodes[i].loop_num,
1892 ira_loop_nodes[i].loop->header->index, 2295 ira_loop_nodes[i].loop->header->index,
1893 ira_loop_nodes[i].loop->header->frequency, 2296 ira_loop_nodes[i].loop->header->frequency,
1894 loop_depth (ira_loop_nodes[i].loop)); 2297 loop_depth (ira_loop_nodes[i].loop));
1895 } 2298 }
1896 } 2299 }
1897 2300
1898 /* Definition of vector of loop tree nodes. */ 2301 /* Definition of vector of loop tree nodes. */
1899 DEF_VEC_P(ira_loop_tree_node_t);
1900 DEF_VEC_ALLOC_P(ira_loop_tree_node_t, heap);
1901 2302
1902 /* Vec containing references to all removed loop tree nodes. */ 2303 /* Vec containing references to all removed loop tree nodes. */
1903 static VEC(ira_loop_tree_node_t,heap) *removed_loop_vec; 2304 static vec<ira_loop_tree_node_t> removed_loop_vec;
1904 2305
1905 /* Vec containing references to all children of loop tree nodes. */ 2306 /* Vec containing references to all children of loop tree nodes. */
1906 static VEC(ira_loop_tree_node_t,heap) *children_vec; 2307 static vec<ira_loop_tree_node_t> children_vec;
1907 2308
1908 /* Remove subregions of NODE if their separate allocation will not 2309 /* Remove subregions of NODE if their separate allocation will not
1909 improve the result. */ 2310 improve the result. */
1910 static void 2311 static void
1911 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node) 2312 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_node_t node)
1914 bool remove_p; 2315 bool remove_p;
1915 ira_loop_tree_node_t subnode; 2316 ira_loop_tree_node_t subnode;
1916 2317
1917 remove_p = node->to_remove_p; 2318 remove_p = node->to_remove_p;
1918 if (! remove_p) 2319 if (! remove_p)
1919 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, node); 2320 children_vec.safe_push (node);
1920 start = VEC_length (ira_loop_tree_node_t, children_vec); 2321 start = children_vec.length ();
1921 for (subnode = node->children; subnode != NULL; subnode = subnode->next) 2322 for (subnode = node->children; subnode != NULL; subnode = subnode->next)
1922 if (subnode->bb == NULL) 2323 if (subnode->bb == NULL)
1923 remove_uneccesary_loop_nodes_from_loop_tree (subnode); 2324 remove_uneccesary_loop_nodes_from_loop_tree (subnode);
1924 else 2325 else
1925 VEC_safe_push (ira_loop_tree_node_t, heap, children_vec, subnode); 2326 children_vec.safe_push (subnode);
1926 node->children = node->subloops = NULL; 2327 node->children = node->subloops = NULL;
1927 if (remove_p) 2328 if (remove_p)
1928 { 2329 {
1929 VEC_safe_push (ira_loop_tree_node_t, heap, removed_loop_vec, node); 2330 removed_loop_vec.safe_push (node);
1930 return; 2331 return;
1931 } 2332 }
1932 while (VEC_length (ira_loop_tree_node_t, children_vec) > start) 2333 while (children_vec.length () > start)
1933 { 2334 {
1934 subnode = VEC_pop (ira_loop_tree_node_t, children_vec); 2335 subnode = children_vec.pop ();
1935 subnode->parent = node; 2336 subnode->parent = node;
1936 subnode->next = node->children; 2337 subnode->next = node->children;
1937 node->children = subnode; 2338 node->children = subnode;
1938 if (subnode->bb == NULL) 2339 if (subnode->bb == NULL)
1939 { 2340 {
2001 2402
2002 /* Propagate info from allocno FROM_A to allocno A. */ 2403 /* Propagate info from allocno FROM_A to allocno A. */
2003 static void 2404 static void
2004 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a) 2405 propagate_some_info_from_allocno (ira_allocno_t a, ira_allocno_t from_a)
2005 { 2406 {
2006 enum reg_class cover_class; 2407 enum reg_class aclass;
2007 2408
2008 merge_hard_reg_conflicts (from_a, a, false); 2409 merge_hard_reg_conflicts (from_a, a, false);
2009 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a); 2410 ALLOCNO_NREFS (a) += ALLOCNO_NREFS (from_a);
2010 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a); 2411 ALLOCNO_FREQ (a) += ALLOCNO_FREQ (from_a);
2011 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a); 2412 ALLOCNO_CALL_FREQ (a) += ALLOCNO_CALL_FREQ (from_a);
2012 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a); 2413 ALLOCNO_CALLS_CROSSED_NUM (a) += ALLOCNO_CALLS_CROSSED_NUM (from_a);
2414 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a)
2415 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (from_a);
2416 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a),
2417 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (from_a));
2418
2013 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a) 2419 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a)
2014 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a); 2420 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (from_a);
2015 if (! ALLOCNO_BAD_SPILL_P (from_a)) 2421 if (! ALLOCNO_BAD_SPILL_P (from_a))
2016 ALLOCNO_BAD_SPILL_P (a) = false; 2422 ALLOCNO_BAD_SPILL_P (a) = false;
2017 cover_class = ALLOCNO_COVER_CLASS (from_a); 2423 aclass = ALLOCNO_CLASS (from_a);
2018 ira_assert (cover_class == ALLOCNO_COVER_CLASS (a)); 2424 ira_assert (aclass == ALLOCNO_CLASS (a));
2019 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), cover_class, 2425 ira_allocate_and_accumulate_costs (&ALLOCNO_HARD_REG_COSTS (a), aclass,
2020 ALLOCNO_HARD_REG_COSTS (from_a)); 2426 ALLOCNO_HARD_REG_COSTS (from_a));
2021 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), 2427 ira_allocate_and_accumulate_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2022 cover_class, 2428 aclass,
2023 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a)); 2429 ALLOCNO_CONFLICT_HARD_REG_COSTS (from_a));
2024 ALLOCNO_COVER_CLASS_COST (a) += ALLOCNO_COVER_CLASS_COST (from_a); 2430 ALLOCNO_CLASS_COST (a) += ALLOCNO_CLASS_COST (from_a);
2025 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a); 2431 ALLOCNO_MEMORY_COST (a) += ALLOCNO_MEMORY_COST (from_a);
2026 } 2432 }
2027 2433
2028 /* Remove allocnos from loops removed from the allocation 2434 /* Remove allocnos from loops removed from the allocation
2029 consideration. */ 2435 consideration. */
2079 propagate_some_info_from_allocno (parent_a, a); 2485 propagate_some_info_from_allocno (parent_a, a);
2080 /* Remove it from the corresponding regno allocno 2486 /* Remove it from the corresponding regno allocno
2081 map to avoid info propagation of subsequent 2487 map to avoid info propagation of subsequent
2082 allocno into this already removed allocno. */ 2488 allocno into this already removed allocno. */
2083 a_node->regno_allocno_map[regno] = NULL; 2489 a_node->regno_allocno_map[regno] = NULL;
2490 ira_remove_allocno_prefs (a);
2084 finish_allocno (a); 2491 finish_allocno (a);
2085 } 2492 }
2086 } 2493 }
2087 } 2494 }
2088 if (rebuild_p) 2495 if (rebuild_p)
2162 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a)) 2569 if (ALLOCNO_TOTAL_NO_STACK_REG_P (a))
2163 ALLOCNO_NO_STACK_REG_P (a) = true; 2570 ALLOCNO_NO_STACK_REG_P (a) = true;
2164 #endif 2571 #endif
2165 } 2572 }
2166 else 2573 else
2167 finish_allocno (a); 2574 {
2575 ira_remove_allocno_prefs (a);
2576 finish_allocno (a);
2577 }
2168 } 2578 }
2169 if (merged_p) 2579 if (merged_p)
2170 ira_rebuild_start_finish_chains (); 2580 ira_rebuild_start_finish_chains ();
2171 } 2581 }
2172 2582
2173 /* Remove loops from consideration. We remove all loops except for 2583 /* Remove loops from consideration. We remove all loops except for
2174 root if ALL_P or loops for which a separate allocation will not 2584 root if ALL_P or loops for which a separate allocation will not
2175 improve the result. We have to do this after allocno creation and 2585 improve the result. We have to do this after allocno creation and
2176 their costs and cover class evaluation because only after that the 2586 their costs and allocno class evaluation because only after that
2177 register pressure can be known and is calculated. */ 2587 the register pressure can be known and is calculated. */
2178 static void 2588 static void
2179 remove_unnecessary_regions (bool all_p) 2589 remove_unnecessary_regions (bool all_p)
2180 { 2590 {
2591 if (current_loops == NULL)
2592 return;
2181 if (all_p) 2593 if (all_p)
2182 mark_all_loops_for_removal (); 2594 mark_all_loops_for_removal ();
2183 else 2595 else
2184 mark_loops_for_removal (); 2596 mark_loops_for_removal ();
2185 children_vec 2597 children_vec.create (last_basic_block_for_fn (cfun)
2186 = VEC_alloc (ira_loop_tree_node_t, heap, 2598 + number_of_loops (cfun));
2187 last_basic_block + VEC_length (loop_p, ira_loops.larray)); 2599 removed_loop_vec.create (last_basic_block_for_fn (cfun)
2188 removed_loop_vec 2600 + number_of_loops (cfun));
2189 = VEC_alloc (ira_loop_tree_node_t, heap, 2601 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root);
2190 last_basic_block + VEC_length (loop_p, ira_loops.larray)); 2602 children_vec.release ();
2191 remove_uneccesary_loop_nodes_from_loop_tree (ira_loop_tree_root) ;
2192 VEC_free (ira_loop_tree_node_t, heap, children_vec);
2193 if (all_p) 2603 if (all_p)
2194 remove_low_level_allocnos (); 2604 remove_low_level_allocnos ();
2195 else 2605 else
2196 remove_unnecessary_allocnos (); 2606 remove_unnecessary_allocnos ();
2197 while (VEC_length (ira_loop_tree_node_t, removed_loop_vec) > 0) 2607 while (removed_loop_vec.length () > 0)
2198 finish_loop_tree_node (VEC_pop (ira_loop_tree_node_t, removed_loop_vec)); 2608 finish_loop_tree_node (removed_loop_vec.pop ());
2199 VEC_free (ira_loop_tree_node_t, heap, removed_loop_vec); 2609 removed_loop_vec.release ();
2200 } 2610 }
2201 2611
2202 2612
2203 2613
2204 /* At this point true value of allocno attribute bad_spill_p means 2614 /* At this point true value of allocno attribute bad_spill_p means
2221 ira_allocno_t a; 2631 ira_allocno_t a;
2222 ira_allocno_iterator ai; 2632 ira_allocno_iterator ai;
2223 ira_allocno_object_iterator aoi; 2633 ira_allocno_object_iterator aoi;
2224 ira_object_t obj; 2634 ira_object_t obj;
2225 live_range_t r; 2635 live_range_t r;
2226 enum reg_class cover_class; 2636 enum reg_class aclass;
2227 bitmap_head dead_points[N_REG_CLASSES]; 2637 bitmap_head dead_points[N_REG_CLASSES];
2228 2638
2229 for (i = 0; i < ira_reg_class_cover_size; i++) 2639 for (i = 0; i < ira_allocno_classes_num; i++)
2230 { 2640 {
2231 cover_class = ira_reg_class_cover[i]; 2641 aclass = ira_allocno_classes[i];
2232 bitmap_initialize (&dead_points[cover_class], &reg_obstack); 2642 bitmap_initialize (&dead_points[aclass], &reg_obstack);
2233 } 2643 }
2234 FOR_EACH_ALLOCNO (a, ai) 2644 FOR_EACH_ALLOCNO (a, ai)
2235 { 2645 {
2236 cover_class = ALLOCNO_COVER_CLASS (a); 2646 aclass = ALLOCNO_CLASS (a);
2237 if (cover_class == NO_REGS) 2647 if (aclass == NO_REGS)
2238 continue; 2648 continue;
2239 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi) 2649 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2240 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 2650 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2241 bitmap_set_bit (&dead_points[cover_class], r->finish); 2651 bitmap_set_bit (&dead_points[aclass], r->finish);
2242 } 2652 }
2243 FOR_EACH_ALLOCNO (a, ai) 2653 FOR_EACH_ALLOCNO (a, ai)
2244 { 2654 {
2245 cover_class = ALLOCNO_COVER_CLASS (a); 2655 aclass = ALLOCNO_CLASS (a);
2246 if (cover_class == NO_REGS) 2656 if (aclass == NO_REGS)
2247 continue; 2657 continue;
2248 if (! ALLOCNO_BAD_SPILL_P (a)) 2658 if (! ALLOCNO_BAD_SPILL_P (a))
2249 continue; 2659 continue;
2250 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi) 2660 FOR_EACH_ALLOCNO_OBJECT (a, obj, aoi)
2251 { 2661 {
2252 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 2662 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2253 { 2663 {
2254 for (i = r->start + 1; i < r->finish; i++) 2664 for (i = r->start + 1; i < r->finish; i++)
2255 if (bitmap_bit_p (&dead_points[cover_class], i)) 2665 if (bitmap_bit_p (&dead_points[aclass], i))
2256 break; 2666 break;
2257 if (i < r->finish) 2667 if (i < r->finish)
2258 break; 2668 break;
2259 } 2669 }
2260 if (r != NULL) 2670 if (r != NULL)
2262 ALLOCNO_BAD_SPILL_P (a) = false; 2672 ALLOCNO_BAD_SPILL_P (a) = false;
2263 break; 2673 break;
2264 } 2674 }
2265 } 2675 }
2266 } 2676 }
2267 for (i = 0; i < ira_reg_class_cover_size; i++) 2677 for (i = 0; i < ira_allocno_classes_num; i++)
2268 { 2678 {
2269 cover_class = ira_reg_class_cover[i]; 2679 aclass = ira_allocno_classes[i];
2270 bitmap_clear (&dead_points[cover_class]); 2680 bitmap_clear (&dead_points[aclass]);
2271 } 2681 }
2272 } 2682 }
2273 2683
2274 2684
2275 2685
2288 ira_loop_tree_node_t parent; 2698 ira_loop_tree_node_t parent;
2289 2699
2290 FOR_EACH_ALLOCNO (a, ai) 2700 FOR_EACH_ALLOCNO (a, ai)
2291 { 2701 {
2292 int n = ALLOCNO_NUM_OBJECTS (a); 2702 int n = ALLOCNO_NUM_OBJECTS (a);
2703
2293 for (i = 0; i < n; i++) 2704 for (i = 0; i < n; i++)
2294 { 2705 {
2295 ira_object_t obj = ALLOCNO_OBJECT (a, i); 2706 ira_object_t obj = ALLOCNO_OBJECT (a, i);
2296 r = OBJECT_LIVE_RANGES (obj); 2707 r = OBJECT_LIVE_RANGES (obj);
2297 if (r == NULL) 2708 if (r == NULL)
2307 a != NULL; 2718 a != NULL;
2308 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 2719 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2309 { 2720 {
2310 int j; 2721 int j;
2311 int n = ALLOCNO_NUM_OBJECTS (a); 2722 int n = ALLOCNO_NUM_OBJECTS (a);
2723
2312 for (j = 0; j < n; j++) 2724 for (j = 0; j < n; j++)
2313 { 2725 {
2314 ira_object_t obj = ALLOCNO_OBJECT (a, j); 2726 ira_object_t obj = ALLOCNO_OBJECT (a, j);
2315 ira_object_t parent_obj; 2727 ira_object_t parent_obj;
2316 2728
2350 } 2762 }
2351 #endif 2763 #endif
2352 } 2764 }
2353 2765
2354 /* Sort allocnos according to their live ranges. Allocnos with 2766 /* Sort allocnos according to their live ranges. Allocnos with
2355 smaller cover class are put first unless we use priority coloring. 2767 smaller allocno class are put first unless we use priority
2356 Allocnos with the same cover class are ordered according their start 2768 coloring. Allocnos with the same class are ordered according
2357 (min). Allocnos with the same start are ordered according their 2769 their start (min). Allocnos with the same start are ordered
2358 finish (max). */ 2770 according their finish (max). */
2359 static int 2771 static int
2360 object_range_compare_func (const void *v1p, const void *v2p) 2772 object_range_compare_func (const void *v1p, const void *v2p)
2361 { 2773 {
2362 int diff; 2774 int diff;
2363 ira_object_t obj1 = *(const ira_object_t *) v1p; 2775 ira_object_t obj1 = *(const ira_object_t *) v1p;
2364 ira_object_t obj2 = *(const ira_object_t *) v2p; 2776 ira_object_t obj2 = *(const ira_object_t *) v2p;
2365 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1); 2777 ira_allocno_t a1 = OBJECT_ALLOCNO (obj1);
2366 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2); 2778 ira_allocno_t a2 = OBJECT_ALLOCNO (obj2);
2367 2779
2368 if (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY
2369 && (diff = ALLOCNO_COVER_CLASS (a1) - ALLOCNO_COVER_CLASS (a2)) != 0)
2370 return diff;
2371 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0) 2780 if ((diff = OBJECT_MIN (obj1) - OBJECT_MIN (obj2)) != 0)
2372 return diff; 2781 return diff;
2373 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0) 2782 if ((diff = OBJECT_MAX (obj1) - OBJECT_MAX (obj2)) != 0)
2374 return diff; 2783 return diff;
2375 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2); 2784 return ALLOCNO_NUM (a1) - ALLOCNO_NUM (a2);
2390 ira_object_t obj; 2799 ira_object_t obj;
2391 2800
2392 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 2801 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2393 ira_object_id_map[num++] = obj; 2802 ira_object_id_map[num++] = obj;
2394 } 2803 }
2395 qsort (ira_object_id_map, num, sizeof (ira_object_t), 2804 if (num > 1)
2396 object_range_compare_func); 2805 qsort (ira_object_id_map, num, sizeof (ira_object_t),
2806 object_range_compare_func);
2397 for (i = 0; i < num; i++) 2807 for (i = 0; i < num; i++)
2398 { 2808 {
2399 ira_object_t obj = ira_object_id_map[i]; 2809 ira_object_t obj = ira_object_id_map[i];
2810
2400 gcc_assert (obj != NULL); 2811 gcc_assert (obj != NULL);
2401 OBJECT_CONFLICT_ID (obj) = i; 2812 OBJECT_CONFLICT_ID (obj) = i;
2402 } 2813 }
2403 for (i = num; i < ira_objects_num; i++) 2814 for (i = num; i < ira_objects_num; i++)
2404 ira_object_id_map[i] = NULL; 2815 ira_object_id_map[i] = NULL;
2407 /* Set up minimal and maximal conflict ids of allocnos with which 2818 /* Set up minimal and maximal conflict ids of allocnos with which
2408 given allocno can conflict. */ 2819 given allocno can conflict. */
2409 static void 2820 static void
2410 setup_min_max_conflict_allocno_ids (void) 2821 setup_min_max_conflict_allocno_ids (void)
2411 { 2822 {
2412 int cover_class; 2823 int aclass;
2413 int i, j, min, max, start, finish, first_not_finished, filled_area_start; 2824 int i, j, min, max, start, finish, first_not_finished, filled_area_start;
2414 int *live_range_min, *last_lived; 2825 int *live_range_min, *last_lived;
2415 int word0_min, word0_max; 2826 int word0_min, word0_max;
2416 ira_allocno_t a; 2827 ira_allocno_t a;
2417 ira_allocno_iterator ai; 2828 ira_allocno_iterator ai;
2418 2829
2419 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num); 2830 live_range_min = (int *) ira_allocate (sizeof (int) * ira_objects_num);
2420 cover_class = -1; 2831 aclass = -1;
2421 first_not_finished = -1; 2832 first_not_finished = -1;
2422 for (i = 0; i < ira_objects_num; i++) 2833 for (i = 0; i < ira_objects_num; i++)
2423 { 2834 {
2424 ira_object_t obj = ira_object_id_map[i]; 2835 ira_object_t obj = ira_object_id_map[i];
2836
2425 if (obj == NULL) 2837 if (obj == NULL)
2426 continue; 2838 continue;
2427 2839
2428 a = OBJECT_ALLOCNO (obj); 2840 a = OBJECT_ALLOCNO (obj);
2429 2841
2430 if (cover_class < 0 2842 if (aclass < 0)
2431 || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY 2843 {
2432 && cover_class != (int) ALLOCNO_COVER_CLASS (a))) 2844 aclass = ALLOCNO_CLASS (a);
2433 {
2434 cover_class = ALLOCNO_COVER_CLASS (a);
2435 min = i; 2845 min = i;
2436 first_not_finished = i; 2846 first_not_finished = i;
2437 } 2847 }
2438 else 2848 else
2439 { 2849 {
2454 min++; 2864 min++;
2455 live_range_min[i] = OBJECT_MIN (obj); 2865 live_range_min[i] = OBJECT_MIN (obj);
2456 OBJECT_MIN (obj) = min; 2866 OBJECT_MIN (obj) = min;
2457 } 2867 }
2458 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point); 2868 last_lived = (int *) ira_allocate (sizeof (int) * ira_max_point);
2459 cover_class = -1; 2869 aclass = -1;
2460 filled_area_start = -1; 2870 filled_area_start = -1;
2461 for (i = ira_objects_num - 1; i >= 0; i--) 2871 for (i = ira_objects_num - 1; i >= 0; i--)
2462 { 2872 {
2463 ira_object_t obj = ira_object_id_map[i]; 2873 ira_object_t obj = ira_object_id_map[i];
2874
2464 if (obj == NULL) 2875 if (obj == NULL)
2465 continue; 2876 continue;
2466 2877
2467 a = OBJECT_ALLOCNO (obj); 2878 a = OBJECT_ALLOCNO (obj);
2468 if (cover_class < 0 2879 if (aclass < 0)
2469 || (flag_ira_algorithm != IRA_ALGORITHM_PRIORITY 2880 {
2470 && cover_class != (int) ALLOCNO_COVER_CLASS (a))) 2881 aclass = ALLOCNO_CLASS (a);
2471 {
2472 cover_class = ALLOCNO_COVER_CLASS (a);
2473 for (j = 0; j < ira_max_point; j++) 2882 for (j = 0; j < ira_max_point; j++)
2474 last_lived[j] = -1; 2883 last_lived[j] = -1;
2475 filled_area_start = ira_max_point; 2884 filled_area_start = ira_max_point;
2476 } 2885 }
2477 min = live_range_min[i]; 2886 min = live_range_min[i];
2505 2914
2506 FOR_EACH_ALLOCNO (a, ai) 2915 FOR_EACH_ALLOCNO (a, ai)
2507 { 2916 {
2508 int n = ALLOCNO_NUM_OBJECTS (a); 2917 int n = ALLOCNO_NUM_OBJECTS (a);
2509 ira_object_t obj0; 2918 ira_object_t obj0;
2919
2510 if (n < 2) 2920 if (n < 2)
2511 continue; 2921 continue;
2512 obj0 = ALLOCNO_OBJECT (a, 0); 2922 obj0 = ALLOCNO_OBJECT (a, 0);
2513 if (OBJECT_CONFLICT_ID (obj0) < word0_min) 2923 if (OBJECT_CONFLICT_ID (obj0) < word0_min)
2514 word0_min = OBJECT_CONFLICT_ID (obj0); 2924 word0_min = OBJECT_CONFLICT_ID (obj0);
2517 } 2927 }
2518 FOR_EACH_ALLOCNO (a, ai) 2928 FOR_EACH_ALLOCNO (a, ai)
2519 { 2929 {
2520 int n = ALLOCNO_NUM_OBJECTS (a); 2930 int n = ALLOCNO_NUM_OBJECTS (a);
2521 ira_object_t obj0; 2931 ira_object_t obj0;
2932
2522 if (n < 2) 2933 if (n < 2)
2523 continue; 2934 continue;
2524 obj0 = ALLOCNO_OBJECT (a, 0); 2935 obj0 = ALLOCNO_OBJECT (a, 0);
2525 if (OBJECT_MIN (obj0) > word0_min) 2936 if (OBJECT_MIN (obj0) > word0_min)
2526 OBJECT_MIN (obj0) = word0_min; 2937 OBJECT_MIN (obj0) = word0_min;
2609 merged_p = false; 3020 merged_p = false;
2610 for (a = ira_regno_allocno_map[regno]; 3021 for (a = ira_regno_allocno_map[regno];
2611 a != NULL; 3022 a != NULL;
2612 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 3023 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2613 { 3024 {
2614 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))]) 3025 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))])
2615 /* This allocno will be removed. */ 3026 /* This allocno will be removed. */
2616 continue; 3027 continue;
2617 3028
2618 /* Caps will be removed. */ 3029 /* Caps will be removed. */
2619 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 3030 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2620 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent; 3031 for (parent = ALLOCNO_LOOP_TREE_NODE (a)->parent;
2621 parent != NULL; 3032 parent != NULL;
2622 parent = parent->parent) 3033 parent = parent->parent)
2623 if ((parent_a = parent->regno_allocno_map[regno]) == NULL 3034 if ((parent_a = parent->regno_allocno_map[regno]) == NULL
2624 || (parent_a == regno_top_level_allocno_map[REGNO (ALLOCNO_REG 3035 || (parent_a
2625 (parent_a))] 3036 == regno_top_level_allocno_map[REGNO
2626 && ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a))) 3037 (allocno_emit_reg (parent_a))]
3038 && ALLOCNO_EMIT_DATA (parent_a)->mem_optimized_dest_p))
2627 break; 3039 break;
2628 if (parent == NULL || parent_a == NULL) 3040 if (parent == NULL || parent_a == NULL)
2629 continue; 3041 continue;
2630 3042
2631 copy_allocno_live_ranges (a, parent_a); 3043 copy_allocno_live_ranges (a, parent_a);
2632 merge_hard_reg_conflicts (a, parent_a, true); 3044 merge_hard_reg_conflicts (a, parent_a, true);
2633 3045
2634 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a); 3046 ALLOCNO_CALL_FREQ (parent_a) += ALLOCNO_CALL_FREQ (a);
2635 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 3047 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2636 += ALLOCNO_CALLS_CROSSED_NUM (a); 3048 += ALLOCNO_CALLS_CROSSED_NUM (a);
3049 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3050 += ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
3051 IOR_HARD_REG_SET (ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (parent_a),
3052 ALLOCNO_CROSSED_CALLS_CLOBBERED_REGS (a));
2637 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 3053 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2638 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 3054 += ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2639 merged_p = true; 3055 merged_p = true;
2640 } 3056 }
2641 return merged_p; 3057 return merged_p;
2653 int i, j; 3069 int i, j;
2654 bool keep_p; 3070 bool keep_p;
2655 int hard_regs_num; 3071 int hard_regs_num;
2656 bool new_pseudos_p, merged_p, mem_dest_p; 3072 bool new_pseudos_p, merged_p, mem_dest_p;
2657 unsigned int n; 3073 unsigned int n;
2658 enum reg_class cover_class; 3074 enum reg_class aclass;
2659 ira_allocno_t a, parent_a, first, second, node_first, node_second; 3075 ira_allocno_t a, parent_a, first, second, node_first, node_second;
2660 ira_copy_t cp; 3076 ira_copy_t cp;
2661 ira_loop_tree_node_t node; 3077 ira_loop_tree_node_t node;
2662 live_range_t r; 3078 live_range_t r;
2663 ira_allocno_iterator ai; 3079 ira_allocno_iterator ai;
2664 ira_copy_iterator ci; 3080 ira_copy_iterator ci;
2665 3081
2666 regno_top_level_allocno_map 3082 regno_top_level_allocno_map
2667 = (ira_allocno_t *) ira_allocate (max_reg_num () * sizeof (ira_allocno_t)); 3083 = (ira_allocno_t *) ira_allocate (max_reg_num ()
3084 * sizeof (ira_allocno_t));
2668 memset (regno_top_level_allocno_map, 0, 3085 memset (regno_top_level_allocno_map, 0,
2669 max_reg_num () * sizeof (ira_allocno_t)); 3086 max_reg_num () * sizeof (ira_allocno_t));
2670 new_pseudos_p = merged_p = false; 3087 new_pseudos_p = merged_p = false;
2671 FOR_EACH_ALLOCNO (a, ai) 3088 FOR_EACH_ALLOCNO (a, ai)
2672 { 3089 {
2673 ira_allocno_object_iterator oi; 3090 ira_allocno_object_iterator oi;
2674 ira_object_t obj; 3091 ira_object_t obj;
3092
2675 if (ALLOCNO_CAP_MEMBER (a) != NULL) 3093 if (ALLOCNO_CAP_MEMBER (a) != NULL)
2676 /* Caps are not in the regno allocno maps and they are never 3094 /* Caps are not in the regno allocno maps and they are never
2677 will be transformed into allocnos existing after IR 3095 will be transformed into allocnos existing after IR
2678 flattening. */ 3096 flattening. */
2679 continue; 3097 continue;
2690 mem_dest_p = false; 3108 mem_dest_p = false;
2691 for (a = ira_regno_allocno_map[i]; 3109 for (a = ira_regno_allocno_map[i];
2692 a != NULL; 3110 a != NULL;
2693 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a)) 3111 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
2694 { 3112 {
3113 ira_emit_data_t parent_data, data = ALLOCNO_EMIT_DATA (a);
3114
2695 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL); 3115 ira_assert (ALLOCNO_CAP_MEMBER (a) == NULL);
2696 if (ALLOCNO_SOMEWHERE_RENAMED_P (a)) 3116 if (data->somewhere_renamed_p)
2697 new_pseudos_p = true; 3117 new_pseudos_p = true;
2698 parent_a = ira_parent_allocno (a); 3118 parent_a = ira_parent_allocno (a);
2699 if (parent_a == NULL) 3119 if (parent_a == NULL)
2700 { 3120 {
2701 ALLOCNO_COPIES (a) = NULL; 3121 ALLOCNO_COPIES (a) = NULL;
2702 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a; 3122 regno_top_level_allocno_map[REGNO (data->reg)] = a;
2703 continue; 3123 continue;
2704 } 3124 }
2705 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL); 3125 ira_assert (ALLOCNO_CAP_MEMBER (parent_a) == NULL);
2706 3126
2707 if (ALLOCNO_MEM_OPTIMIZED_DEST (a) != NULL) 3127 if (data->mem_optimized_dest != NULL)
2708 mem_dest_p = true; 3128 mem_dest_p = true;
2709 if (REGNO (ALLOCNO_REG (a)) == REGNO (ALLOCNO_REG (parent_a))) 3129 parent_data = ALLOCNO_EMIT_DATA (parent_a);
3130 if (REGNO (data->reg) == REGNO (parent_data->reg))
2710 { 3131 {
2711 merge_hard_reg_conflicts (a, parent_a, true); 3132 merge_hard_reg_conflicts (a, parent_a, true);
2712 move_allocno_live_ranges (a, parent_a); 3133 move_allocno_live_ranges (a, parent_a);
2713 merged_p = true; 3134 merged_p = true;
2714 ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a) 3135 parent_data->mem_optimized_dest_p
2715 = (ALLOCNO_MEM_OPTIMIZED_DEST_P (parent_a) 3136 = (parent_data->mem_optimized_dest_p
2716 || ALLOCNO_MEM_OPTIMIZED_DEST_P (a)); 3137 || data->mem_optimized_dest_p);
2717 continue; 3138 continue;
2718 } 3139 }
2719 new_pseudos_p = true; 3140 new_pseudos_p = true;
2720 for (;;) 3141 for (;;)
2721 { 3142 {
2722 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a); 3143 ALLOCNO_NREFS (parent_a) -= ALLOCNO_NREFS (a);
2723 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a); 3144 ALLOCNO_FREQ (parent_a) -= ALLOCNO_FREQ (a);
2724 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a); 3145 ALLOCNO_CALL_FREQ (parent_a) -= ALLOCNO_CALL_FREQ (a);
2725 ALLOCNO_CALLS_CROSSED_NUM (parent_a) 3146 ALLOCNO_CALLS_CROSSED_NUM (parent_a)
2726 -= ALLOCNO_CALLS_CROSSED_NUM (a); 3147 -= ALLOCNO_CALLS_CROSSED_NUM (a);
3148 ALLOCNO_CHEAP_CALLS_CROSSED_NUM (parent_a)
3149 -= ALLOCNO_CHEAP_CALLS_CROSSED_NUM (a);
2727 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a) 3150 ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (parent_a)
2728 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a); 3151 -= ALLOCNO_EXCESS_PRESSURE_POINTS_NUM (a);
2729 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0 3152 ira_assert (ALLOCNO_CALLS_CROSSED_NUM (parent_a) >= 0
2730 && ALLOCNO_NREFS (parent_a) >= 0 3153 && ALLOCNO_NREFS (parent_a) >= 0
2731 && ALLOCNO_FREQ (parent_a) >= 0); 3154 && ALLOCNO_FREQ (parent_a) >= 0);
2732 cover_class = ALLOCNO_COVER_CLASS (parent_a); 3155 aclass = ALLOCNO_CLASS (parent_a);
2733 hard_regs_num = ira_class_hard_regs_num[cover_class]; 3156 hard_regs_num = ira_class_hard_regs_num[aclass];
2734 if (ALLOCNO_HARD_REG_COSTS (a) != NULL 3157 if (ALLOCNO_HARD_REG_COSTS (a) != NULL
2735 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL) 3158 && ALLOCNO_HARD_REG_COSTS (parent_a) != NULL)
2736 for (j = 0; j < hard_regs_num; j++) 3159 for (j = 0; j < hard_regs_num; j++)
2737 ALLOCNO_HARD_REG_COSTS (parent_a)[j] 3160 ALLOCNO_HARD_REG_COSTS (parent_a)[j]
2738 -= ALLOCNO_HARD_REG_COSTS (a)[j]; 3161 -= ALLOCNO_HARD_REG_COSTS (a)[j];
2739 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL 3162 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) != NULL
2740 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL) 3163 && ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a) != NULL)
2741 for (j = 0; j < hard_regs_num; j++) 3164 for (j = 0; j < hard_regs_num; j++)
2742 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j] 3165 ALLOCNO_CONFLICT_HARD_REG_COSTS (parent_a)[j]
2743 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j]; 3166 -= ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[j];
2744 ALLOCNO_COVER_CLASS_COST (parent_a) 3167 ALLOCNO_CLASS_COST (parent_a)
2745 -= ALLOCNO_COVER_CLASS_COST (a); 3168 -= ALLOCNO_CLASS_COST (a);
2746 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a); 3169 ALLOCNO_MEMORY_COST (parent_a) -= ALLOCNO_MEMORY_COST (a);
2747 parent_a = ira_parent_allocno (parent_a); 3170 parent_a = ira_parent_allocno (parent_a);
2748 if (parent_a == NULL) 3171 if (parent_a == NULL)
2749 break; 3172 break;
2750 } 3173 }
2751 ALLOCNO_COPIES (a) = NULL; 3174 ALLOCNO_COPIES (a) = NULL;
2752 regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] = a; 3175 regno_top_level_allocno_map[REGNO (data->reg)] = a;
2753 } 3176 }
2754 if (mem_dest_p && copy_info_to_removed_store_destinations (i)) 3177 if (mem_dest_p && copy_info_to_removed_store_destinations (i))
2755 merged_p = true; 3178 merged_p = true;
2756 } 3179 }
2757 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point); 3180 ira_assert (new_pseudos_p || ira_max_point_before_emit == ira_max_point);
2764 /* Rebuild conflicts. */ 3187 /* Rebuild conflicts. */
2765 FOR_EACH_ALLOCNO (a, ai) 3188 FOR_EACH_ALLOCNO (a, ai)
2766 { 3189 {
2767 ira_allocno_object_iterator oi; 3190 ira_allocno_object_iterator oi;
2768 ira_object_t obj; 3191 ira_object_t obj;
2769 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] 3192
3193 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2770 || ALLOCNO_CAP_MEMBER (a) != NULL) 3194 || ALLOCNO_CAP_MEMBER (a) != NULL)
2771 continue; 3195 continue;
2772 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi) 3196 FOR_EACH_ALLOCNO_OBJECT (a, obj, oi)
2773 { 3197 {
2774 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 3198 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
2780 for (i = 0; i < ira_max_point; i++) 3204 for (i = 0; i < ira_max_point; i++)
2781 { 3205 {
2782 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next) 3206 for (r = ira_start_point_ranges[i]; r != NULL; r = r->start_next)
2783 { 3207 {
2784 ira_object_t obj = r->object; 3208 ira_object_t obj = r->object;
3209
2785 a = OBJECT_ALLOCNO (obj); 3210 a = OBJECT_ALLOCNO (obj);
2786 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] 3211 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2787 || ALLOCNO_CAP_MEMBER (a) != NULL) 3212 || ALLOCNO_CAP_MEMBER (a) != NULL)
2788 continue; 3213 continue;
2789 3214
2790 cover_class = ALLOCNO_COVER_CLASS (a); 3215 aclass = ALLOCNO_CLASS (a);
2791 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
2792 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n) 3216 EXECUTE_IF_SET_IN_SPARSESET (objects_live, n)
2793 { 3217 {
2794 ira_object_t live_obj = ira_object_id_map[n]; 3218 ira_object_t live_obj = ira_object_id_map[n];
2795 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj); 3219 ira_allocno_t live_a = OBJECT_ALLOCNO (live_obj);
2796 enum reg_class live_cover = ALLOCNO_COVER_CLASS (live_a); 3220 enum reg_class live_aclass = ALLOCNO_CLASS (live_a);
2797 if (ira_reg_classes_intersect_p[cover_class][live_cover] 3221
3222 if (ira_reg_classes_intersect_p[aclass][live_aclass]
2798 /* Don't set up conflict for the allocno with itself. */ 3223 /* Don't set up conflict for the allocno with itself. */
2799 && live_a != a) 3224 && live_a != a)
2800 ira_add_conflict (obj, live_obj); 3225 ira_add_conflict (obj, live_obj);
2801 } 3226 }
3227 sparseset_set_bit (objects_live, OBJECT_CONFLICT_ID (obj));
2802 } 3228 }
2803 3229
2804 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next) 3230 for (r = ira_finish_point_ranges[i]; r != NULL; r = r->finish_next)
2805 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object)); 3231 sparseset_clear_bit (objects_live, OBJECT_CONFLICT_ID (r->object));
2806 } 3232 }
2816 { 3242 {
2817 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 3243 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2818 fprintf 3244 fprintf
2819 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n", 3245 (ira_dump_file, " Remove cp%d:%c%dr%d-%c%dr%d\n",
2820 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a', 3246 cp->num, ALLOCNO_CAP_MEMBER (cp->first) != NULL ? 'c' : 'a',
2821 ALLOCNO_NUM (cp->first), REGNO (ALLOCNO_REG (cp->first)), 3247 ALLOCNO_NUM (cp->first),
3248 REGNO (allocno_emit_reg (cp->first)),
2822 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a', 3249 ALLOCNO_CAP_MEMBER (cp->second) != NULL ? 'c' : 'a',
2823 ALLOCNO_NUM (cp->second), REGNO (ALLOCNO_REG (cp->second))); 3250 ALLOCNO_NUM (cp->second),
3251 REGNO (allocno_emit_reg (cp->second)));
2824 cp->loop_tree_node = NULL; 3252 cp->loop_tree_node = NULL;
2825 continue; 3253 continue;
2826 } 3254 }
2827 first = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->first))]; 3255 first
2828 second = regno_top_level_allocno_map[REGNO (ALLOCNO_REG (cp->second))]; 3256 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->first))];
3257 second
3258 = regno_top_level_allocno_map[REGNO (allocno_emit_reg (cp->second))];
2829 node = cp->loop_tree_node; 3259 node = cp->loop_tree_node;
2830 if (node == NULL) 3260 if (node == NULL)
2831 keep_p = true; /* It copy generated in ira-emit.c. */ 3261 keep_p = true; /* It copy generated in ira-emit.c. */
2832 else 3262 else
2833 { 3263 {
2834 /* Check that the copy was not propagated from level on 3264 /* Check that the copy was not propagated from level on
2835 which we will have different pseudos. */ 3265 which we will have different pseudos. */
2836 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)]; 3266 node_first = node->regno_allocno_map[ALLOCNO_REGNO (cp->first)];
2837 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)]; 3267 node_second = node->regno_allocno_map[ALLOCNO_REGNO (cp->second)];
2838 keep_p = ((REGNO (ALLOCNO_REG (first)) 3268 keep_p = ((REGNO (allocno_emit_reg (first))
2839 == REGNO (ALLOCNO_REG (node_first))) 3269 == REGNO (allocno_emit_reg (node_first)))
2840 && (REGNO (ALLOCNO_REG (second)) 3270 && (REGNO (allocno_emit_reg (second))
2841 == REGNO (ALLOCNO_REG (node_second)))); 3271 == REGNO (allocno_emit_reg (node_second))));
2842 } 3272 }
2843 if (keep_p) 3273 if (keep_p)
2844 { 3274 {
2845 cp->loop_tree_node = ira_loop_tree_root; 3275 cp->loop_tree_node = ira_loop_tree_root;
2846 cp->first = first; 3276 cp->first = first;
2850 { 3280 {
2851 cp->loop_tree_node = NULL; 3281 cp->loop_tree_node = NULL;
2852 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 3282 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2853 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n", 3283 fprintf (ira_dump_file, " Remove cp%d:a%dr%d-a%dr%d\n",
2854 cp->num, ALLOCNO_NUM (cp->first), 3284 cp->num, ALLOCNO_NUM (cp->first),
2855 REGNO (ALLOCNO_REG (cp->first)), ALLOCNO_NUM (cp->second), 3285 REGNO (allocno_emit_reg (cp->first)),
2856 REGNO (ALLOCNO_REG (cp->second))); 3286 ALLOCNO_NUM (cp->second),
3287 REGNO (allocno_emit_reg (cp->second)));
2857 } 3288 }
2858 } 3289 }
2859 /* Remove unnecessary allocnos on lower levels of the loop tree. */ 3290 /* Remove unnecessary allocnos on lower levels of the loop tree. */
2860 FOR_EACH_ALLOCNO (a, ai) 3291 FOR_EACH_ALLOCNO (a, ai)
2861 { 3292 {
2862 if (a != regno_top_level_allocno_map[REGNO (ALLOCNO_REG (a))] 3293 if (a != regno_top_level_allocno_map[REGNO (allocno_emit_reg (a))]
2863 || ALLOCNO_CAP_MEMBER (a) != NULL) 3294 || ALLOCNO_CAP_MEMBER (a) != NULL)
2864 { 3295 {
2865 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL) 3296 if (internal_flag_ira_verbose > 4 && ira_dump_file != NULL)
2866 fprintf (ira_dump_file, " Remove a%dr%d\n", 3297 fprintf (ira_dump_file, " Remove a%dr%d\n",
2867 ALLOCNO_NUM (a), REGNO (ALLOCNO_REG (a))); 3298 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
3299 ira_remove_allocno_prefs (a);
2868 finish_allocno (a); 3300 finish_allocno (a);
2869 continue; 3301 continue;
2870 } 3302 }
2871 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root; 3303 ALLOCNO_LOOP_TREE_NODE (a) = ira_loop_tree_root;
2872 ALLOCNO_REGNO (a) = REGNO (ALLOCNO_REG (a)); 3304 ALLOCNO_REGNO (a) = REGNO (allocno_emit_reg (a));
2873 ALLOCNO_CAP (a) = NULL; 3305 ALLOCNO_CAP (a) = NULL;
2874 /* Restore updated costs for assignments from reload. */ 3306 /* Restore updated costs for assignments from reload. */
2875 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a); 3307 ALLOCNO_UPDATED_MEMORY_COST (a) = ALLOCNO_MEMORY_COST (a);
2876 ALLOCNO_UPDATED_COVER_CLASS_COST (a) = ALLOCNO_COVER_CLASS_COST (a); 3308 ALLOCNO_UPDATED_CLASS_COST (a) = ALLOCNO_CLASS_COST (a);
2877 if (! ALLOCNO_ASSIGNED_P (a)) 3309 if (! ALLOCNO_ASSIGNED_P (a))
2878 ira_free_allocno_updated_costs (a); 3310 ira_free_allocno_updated_costs (a);
2879 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL); 3311 ira_assert (ALLOCNO_UPDATED_HARD_REG_COSTS (a) == NULL);
2880 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL); 3312 ira_assert (ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (a) == NULL);
2881 } 3313 }
2889 continue; 3321 continue;
2890 } 3322 }
2891 ira_assert 3323 ira_assert
2892 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root 3324 (ALLOCNO_LOOP_TREE_NODE (cp->first) == ira_loop_tree_root
2893 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root); 3325 && ALLOCNO_LOOP_TREE_NODE (cp->second) == ira_loop_tree_root);
2894 ira_add_allocno_copy_to_list (cp); 3326 add_allocno_copy_to_list (cp);
2895 ira_swap_allocno_copy_ends_if_necessary (cp); 3327 swap_allocno_copy_ends_if_necessary (cp);
2896 } 3328 }
2897 rebuild_regno_allocno_maps (); 3329 rebuild_regno_allocno_maps ();
2898 if (ira_max_point != ira_max_point_before_emit) 3330 if (ira_max_point != ira_max_point_before_emit)
2899 ira_compress_allocno_live_ranges (); 3331 ira_compress_allocno_live_ranges ();
2900 ira_free (regno_top_level_allocno_map); 3332 ira_free (regno_top_level_allocno_map);
2940 ira_allocno_iterator ai; 3372 ira_allocno_iterator ai;
2941 int i, index, min; 3373 int i, index, min;
2942 3374
2943 FOR_EACH_ALLOCNO (a, ai) 3375 FOR_EACH_ALLOCNO (a, ai)
2944 { 3376 {
2945 enum reg_class cover_class = ALLOCNO_COVER_CLASS (a); 3377 reg_class_t aclass = ALLOCNO_CLASS (a);
2946 enum reg_class pref = reg_preferred_class (ALLOCNO_REGNO (a)); 3378 reg_class_t pref = reg_preferred_class (ALLOCNO_REGNO (a));
2947 3379 int singleton = ira_class_singleton[pref][ALLOCNO_MODE (a)];
2948 if (reg_class_size[pref] != 1) 3380 if (singleton < 0)
2949 continue; 3381 continue;
2950 index = (ira_class_hard_reg_index[cover_class] 3382 index = ira_class_hard_reg_index[(int) aclass][singleton];
2951 [ira_class_hard_regs[pref][0]]);
2952 if (index < 0) 3383 if (index < 0)
2953 continue; 3384 continue;
2954 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL 3385 if (ALLOCNO_CONFLICT_HARD_REG_COSTS (a) == NULL
2955 || ALLOCNO_HARD_REG_COSTS (a) == NULL) 3386 || ALLOCNO_HARD_REG_COSTS (a) == NULL)
2956 continue; 3387 continue;
2957 min = INT_MAX; 3388 min = INT_MAX;
2958 for (i = ira_class_hard_regs_num[cover_class] - 1; i >= 0; i--) 3389 for (i = ira_class_hard_regs_num[(int) aclass] - 1; i >= 0; i--)
2959 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_COVER_CLASS_COST (a) 3390 if (ALLOCNO_HARD_REG_COSTS (a)[i] > ALLOCNO_CLASS_COST (a)
2960 && min > ALLOCNO_HARD_REG_COSTS (a)[i]) 3391 && min > ALLOCNO_HARD_REG_COSTS (a)[i])
2961 min = ALLOCNO_HARD_REG_COSTS (a)[i]; 3392 min = ALLOCNO_HARD_REG_COSTS (a)[i];
2962 if (min == INT_MAX) 3393 if (min == INT_MAX)
2963 continue; 3394 continue;
2964 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a), 3395 ira_allocate_and_set_costs (&ALLOCNO_CONFLICT_HARD_REG_COSTS (a),
2965 cover_class, 0); 3396 aclass, 0);
2966 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index] 3397 ALLOCNO_CONFLICT_HARD_REG_COSTS (a)[index]
2967 -= min - ALLOCNO_COVER_CLASS_COST (a); 3398 -= min - ALLOCNO_CLASS_COST (a);
2968 } 3399 }
2969 } 3400 }
2970 3401
2971 /* Create a internal representation (IR) for IRA (allocnos, copies, 3402 /* Create a internal representation (IR) for IRA (allocnos, copies,
2972 loop tree nodes). If LOOPS_P is FALSE the nodes corresponding to 3403 loop tree nodes). The function returns TRUE if we generate loop
2973 the loops (except the root which corresponds the all function) and 3404 structure (besides nodes representing all function and the basic
2974 correspondingly allocnos for the loops will be not created. Such 3405 blocks) for regional allocation. A true return means that we
2975 parameter value is used for Chaitin-Briggs coloring. The function 3406 really need to flatten IR before the reload. */
2976 returns TRUE if we generate loop structure (besides nodes
2977 representing all function and the basic blocks) for regional
2978 allocation. A true return means that we really need to flatten IR
2979 before the reload. */
2980 bool 3407 bool
2981 ira_build (bool loops_p) 3408 ira_build (void)
2982 { 3409 {
3410 bool loops_p;
3411
2983 df_analyze (); 3412 df_analyze ();
2984
2985 initiate_cost_vectors (); 3413 initiate_cost_vectors ();
2986 initiate_allocnos (); 3414 initiate_allocnos ();
3415 initiate_prefs ();
2987 initiate_copies (); 3416 initiate_copies ();
2988 create_loop_tree_nodes (loops_p); 3417 create_loop_tree_nodes ();
2989 form_loop_tree (); 3418 form_loop_tree ();
2990 create_allocnos (); 3419 create_allocnos ();
2991 ira_costs (); 3420 ira_costs ();
2992 create_allocno_objects (); 3421 create_allocno_objects ();
2993 ira_create_allocno_live_ranges (); 3422 ira_create_allocno_live_ranges ();
2998 if (loops_p) 3427 if (loops_p)
2999 { 3428 {
3000 propagate_allocno_info (); 3429 propagate_allocno_info ();
3001 create_caps (); 3430 create_caps ();
3002 } 3431 }
3003 ira_tune_allocno_costs_and_cover_classes (); 3432 ira_tune_allocno_costs ();
3004 #ifdef ENABLE_IRA_CHECKING 3433 #ifdef ENABLE_IRA_CHECKING
3005 check_allocno_creation (); 3434 check_allocno_creation ();
3006 #endif 3435 #endif
3007 setup_min_max_allocno_live_range_point (); 3436 setup_min_max_allocno_live_range_point ();
3008 sort_conflict_id_map (); 3437 sort_conflict_id_map ();
3027 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0) 3456 if (ALLOCNO_CALLS_CROSSED_NUM (a) != 0)
3028 ior_hard_reg_conflicts (a, &call_used_reg_set); 3457 ior_hard_reg_conflicts (a, &call_used_reg_set);
3029 } 3458 }
3030 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL) 3459 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3031 print_copies (ira_dump_file); 3460 print_copies (ira_dump_file);
3461 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
3462 print_prefs (ira_dump_file);
3032 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL) 3463 if (internal_flag_ira_verbose > 0 && ira_dump_file != NULL)
3033 { 3464 {
3034 int n, nr, nr_big; 3465 int n, nr, nr_big;
3035 ira_allocno_t a; 3466 ira_allocno_t a;
3036 live_range_t r; 3467 live_range_t r;
3040 nr = 0; 3471 nr = 0;
3041 nr_big = 0; 3472 nr_big = 0;
3042 FOR_EACH_ALLOCNO (a, ai) 3473 FOR_EACH_ALLOCNO (a, ai)
3043 { 3474 {
3044 int j, nobj = ALLOCNO_NUM_OBJECTS (a); 3475 int j, nobj = ALLOCNO_NUM_OBJECTS (a);
3476
3045 if (nobj > 1) 3477 if (nobj > 1)
3046 nr_big++; 3478 nr_big++;
3047 for (j = 0; j < nobj; j++) 3479 for (j = 0; j < nobj; j++)
3048 { 3480 {
3049 ira_object_t obj = ALLOCNO_OBJECT (a, j); 3481 ira_object_t obj = ALLOCNO_OBJECT (a, j);
3051 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next) 3483 for (r = OBJECT_LIVE_RANGES (obj); r != NULL; r = r->next)
3052 nr++; 3484 nr++;
3053 } 3485 }
3054 } 3486 }
3055 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n", 3487 fprintf (ira_dump_file, " regions=%d, blocks=%d, points=%d\n",
3056 VEC_length (loop_p, ira_loops.larray), n_basic_blocks, 3488 current_loops == NULL ? 1 : number_of_loops (cfun),
3057 ira_max_point); 3489 n_basic_blocks_for_fn (cfun), ira_max_point);
3058 fprintf (ira_dump_file, 3490 fprintf (ira_dump_file,
3059 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n", 3491 " allocnos=%d (big %d), copies=%d, conflicts=%d, ranges=%d\n",
3060 ira_allocnos_num, nr_big, ira_copies_num, n, nr); 3492 ira_allocnos_num, nr_big, ira_copies_num, n, nr);
3061 } 3493 }
3062 return loops_p; 3494 return loops_p;
3065 /* Release the data created by function ira_build. */ 3497 /* Release the data created by function ira_build. */
3066 void 3498 void
3067 ira_destroy (void) 3499 ira_destroy (void)
3068 { 3500 {
3069 finish_loop_tree_nodes (); 3501 finish_loop_tree_nodes ();
3502 finish_prefs ();
3070 finish_copies (); 3503 finish_copies ();
3071 finish_allocnos (); 3504 finish_allocnos ();
3072 finish_cost_vectors (); 3505 finish_cost_vectors ();
3073 ira_finish_allocno_live_ranges (); 3506 ira_finish_allocno_live_ranges ();
3074 } 3507 }