Branch data Line data Source code
1 : : /* Integrated Register Allocator. Changing code and generating moves.
2 : : Copyright (C) 2006-2025 Free Software Foundation, Inc.
3 : : Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4 : :
5 : : This file is part of GCC.
6 : :
7 : : GCC is free software; you can redistribute it and/or modify it under
8 : : the terms of the GNU General Public License as published by the Free
9 : : Software Foundation; either version 3, or (at your option) any later
10 : : version.
11 : :
12 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 : : for more details.
16 : :
17 : : You should have received a copy of the GNU General Public License
18 : : along with GCC; see the file COPYING3. If not see
19 : : <http://www.gnu.org/licenses/>. */
20 : :
21 : : /* When we have more one region, we need to change the original RTL
22 : : code after coloring. Let us consider two allocnos representing the
23 : : same pseudo-register outside and inside a region respectively.
24 : : They can get different hard-registers. The reload pass works on
25 : : pseudo registers basis and there is no way to say the reload that
26 : : pseudo could be in different registers and it is even more
27 : : difficult to say in what places of the code the pseudo should have
28 : : particular hard-registers. So in this case IRA has to create and
29 : : use a new pseudo-register inside the region and adds code to move
30 : : allocno values on the region's borders. This is done by the code
31 : : in this file.
32 : :
33 : : The code makes top-down traversal of the regions and generate new
34 : : pseudos and the move code on the region borders. In some
35 : : complicated cases IRA can create a new pseudo used temporarily to
36 : : move allocno values when a swap of values stored in two
37 : : hard-registers is needed (e.g. two allocnos representing different
38 : : pseudos outside region got respectively hard registers 1 and 2 and
39 : : the corresponding allocnos inside the region got respectively hard
40 : : registers 2 and 1). At this stage, the new pseudo is marked as
41 : : spilled.
42 : :
43 : : IRA still creates the pseudo-register and the moves on the region
44 : : borders even when the both corresponding allocnos were assigned to
45 : : the same hard-register. It is done because, if the reload pass for
46 : : some reason spills a pseudo-register representing the original
47 : : pseudo outside or inside the region, the effect will be smaller
48 : : because another pseudo will still be in the hard-register. In most
49 : : cases, this is better then spilling the original pseudo in its
50 : : whole live-range. If reload does not change the allocation for the
51 : : two pseudo-registers, the trivial move will be removed by
52 : : post-reload optimizations.
53 : :
54 : : IRA does not generate a new pseudo and moves for the allocno values
55 : : if the both allocnos representing an original pseudo inside and
56 : : outside region assigned to the same hard register when the register
57 : : pressure in the region for the corresponding pressure class is less
58 : : than number of available hard registers for given pressure class.
59 : :
60 : : IRA also does some optimizations to remove redundant moves which is
61 : : transformed into stores by the reload pass on CFG edges
62 : : representing exits from the region.
63 : :
64 : : IRA tries to reduce duplication of code generated on CFG edges
65 : : which are enters and exits to/from regions by moving some code to
66 : : the edge sources or destinations when it is possible. */
67 : :
68 : : #include "config.h"
69 : : #include "system.h"
70 : : #include "coretypes.h"
71 : : #include "backend.h"
72 : : #include "rtl.h"
73 : : #include "tree.h"
74 : : #include "predict.h"
75 : : #include "df.h"
76 : : #include "insn-config.h"
77 : : #include "regs.h"
78 : : #include "memmodel.h"
79 : : #include "ira.h"
80 : : #include "ira-int.h"
81 : : #include "cfgrtl.h"
82 : : #include "cfgbuild.h"
83 : : #include "expr.h"
84 : : #include "reload.h"
85 : : #include "cfgloop.h"
86 : :
87 : :
88 : : /* Data used to emit live range split insns and to flattening IR. */
89 : : ira_emit_data_t ira_allocno_emit_data;
90 : :
91 : : /* Definitions for vectors of pointers. */
92 : : typedef void *void_p;
93 : :
94 : : /* Pointers to data allocated for allocnos being created during
95 : : emitting. Usually there are quite few such allocnos because they
96 : : are created only for resolving loop in register shuffling. */
97 : : static vec<void_p> new_allocno_emit_data_vec;
98 : :
99 : : /* Allocate and initiate the emit data. */
100 : : void
101 : 1431622 : ira_initiate_emit_data (void)
102 : : {
103 : 1431622 : ira_allocno_t a;
104 : 1431622 : ira_allocno_iterator ai;
105 : :
106 : 1431622 : ira_allocno_emit_data
107 : 1431622 : = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 : : * sizeof (struct ira_emit_data));
109 : 1431622 : memset (ira_allocno_emit_data, 0,
110 : 1431622 : ira_allocnos_num * sizeof (struct ira_emit_data));
111 : 36497706 : FOR_EACH_ALLOCNO (a, ai)
112 : 35066084 : ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
113 : 1431622 : new_allocno_emit_data_vec.create (50);
114 : :
115 : 1431622 : }
116 : :
117 : : /* Free the emit data. */
118 : : void
119 : 1431622 : ira_finish_emit_data (void)
120 : : {
121 : 1431622 : void_p p;
122 : 1431622 : ira_allocno_t a;
123 : 1431622 : ira_allocno_iterator ai;
124 : :
125 : 1431622 : ira_free (ira_allocno_emit_data);
126 : 36501724 : FOR_EACH_ALLOCNO (a, ai)
127 : 35070102 : ALLOCNO_ADD_DATA (a) = NULL;
128 : 1435640 : for (;new_allocno_emit_data_vec.length () != 0;)
129 : : {
130 : 4018 : p = new_allocno_emit_data_vec.pop ();
131 : 4018 : ira_free (p);
132 : : }
133 : 1431622 : new_allocno_emit_data_vec.release ();
134 : 1431622 : }
135 : :
136 : : /* Create and return a new allocno with given REGNO and
137 : : LOOP_TREE_NODE. Allocate emit data for it. */
138 : : static ira_allocno_t
139 : 4018 : create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140 : : {
141 : 4018 : ira_allocno_t a;
142 : :
143 : 4018 : a = ira_create_allocno (regno, false, loop_tree_node);
144 : 4018 : ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 : 4018 : memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
146 : 4018 : new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
147 : 4018 : return a;
148 : : }
149 : :
150 : :
151 : :
152 : : /* See comments below. */
153 : : typedef struct move *move_t;
154 : :
155 : : /* The structure represents an allocno move. Both allocnos have the
156 : : same original regno but different allocation. */
157 : : struct move
158 : : {
159 : : /* The allocnos involved in the move. */
160 : : ira_allocno_t from, to;
161 : : /* The next move in the move sequence. */
162 : : move_t next;
163 : : /* Used for finding dependencies. */
164 : : bool visited_p;
165 : : /* The size of the following array. */
166 : : int deps_num;
167 : : /* Moves on which given move depends on. Dependency can be cyclic.
168 : : It means we need a temporary to generates the moves. Sequence
169 : : A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
170 : : B1 are assigned to reg R2 is an example of the cyclic
171 : : dependencies. */
172 : : move_t *deps;
173 : : /* First insn generated for the move. */
174 : : rtx_insn *insn;
175 : : };
176 : :
177 : : /* Array of moves (indexed by BB index) which should be put at the
178 : : start/end of the corresponding basic blocks. */
179 : : static move_t *at_bb_start, *at_bb_end;
180 : :
181 : : /* Max regno before renaming some pseudo-registers. For example, the
182 : : same pseudo-register can be renamed in a loop if its allocation is
183 : : different outside the loop. */
184 : : static int max_regno_before_changing;
185 : :
186 : : /* Return new move of allocnos TO and FROM. */
187 : : static move_t
188 : 2108551 : create_move (ira_allocno_t to, ira_allocno_t from)
189 : : {
190 : 2108551 : move_t move;
191 : :
192 : 2108551 : move = (move_t) ira_allocate (sizeof (struct move));
193 : 2108551 : move->deps = NULL;
194 : 2108551 : move->deps_num = 0;
195 : 2108551 : move->to = to;
196 : 2108551 : move->from = from;
197 : 2108551 : move->next = NULL;
198 : 2108551 : move->insn = NULL;
199 : 2108551 : move->visited_p = false;
200 : 2108551 : return move;
201 : : }
202 : :
203 : : /* Free memory for MOVE and its dependencies. */
204 : : static void
205 : 2108551 : free_move (move_t move)
206 : : {
207 : 2108551 : if (move->deps != NULL)
208 : 1945061 : ira_free (move->deps);
209 : 2108551 : ira_free (move);
210 : 2108551 : }
211 : :
212 : : /* Free memory for list of the moves given by its HEAD. */
213 : : static void
214 : 10548595 : free_move_list (move_t head)
215 : : {
216 : 10548595 : move_t next;
217 : :
218 : 12657146 : for (; head != NULL; head = next)
219 : : {
220 : 2108551 : next = head->next;
221 : 2108551 : free_move (head);
222 : : }
223 : 0 : }
224 : :
225 : : /* Return TRUE if the move list LIST1 and LIST2 are equal (two
226 : : moves are equal if they involve the same allocnos). */
227 : : static bool
228 : 2807168 : eq_move_lists_p (move_t list1, move_t list2)
229 : : {
230 : 2915672 : for (; list1 != NULL && list2 != NULL;
231 : 108504 : list1 = list1->next, list2 = list2->next)
232 : 110280 : if (list1->from != list2->from || list1->to != list2->to)
233 : : return false;
234 : 2805392 : return list1 == list2;
235 : : }
236 : :
237 : : /* Print move list LIST into file F. */
238 : : static void
239 : 0 : print_move_list (FILE *f, move_t list)
240 : : {
241 : 0 : for (; list != NULL; list = list->next)
242 : 0 : fprintf (f, " a%dr%d->a%dr%d",
243 : 0 : ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
244 : 0 : ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
245 : 0 : fprintf (f, "\n");
246 : 0 : }
247 : :
248 : : extern void ira_debug_move_list (move_t list);
249 : :
250 : : /* Print move list LIST into stderr. */
251 : : void
252 : 0 : ira_debug_move_list (move_t list)
253 : : {
254 : 0 : print_move_list (stderr, list);
255 : 0 : }
256 : :
257 : : /* This recursive function changes pseudo-registers in *LOC if it is
258 : : necessary. The function returns TRUE if a change was done. */
259 : : static bool
260 : 195825790 : change_regs (rtx *loc)
261 : : {
262 : 195825790 : int i, regno, result = false;
263 : 195825790 : const char *fmt;
264 : 195825790 : enum rtx_code code;
265 : 195825790 : rtx reg;
266 : :
267 : 195825790 : if (*loc == NULL_RTX)
268 : : return false;
269 : 170183869 : code = GET_CODE (*loc);
270 : 170183869 : if (code == REG)
271 : : {
272 : 42572074 : regno = REGNO (*loc);
273 : 42572074 : if (regno < FIRST_PSEUDO_REGISTER)
274 : : return false;
275 : 23066716 : if (regno >= max_regno_before_changing)
276 : : /* It is a shared register which was changed already. */
277 : : return false;
278 : 23066602 : if (ira_curr_regno_allocno_map[regno] == NULL)
279 : : return false;
280 : 23060751 : reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
281 : 23060751 : if (reg == *loc)
282 : : return false;
283 : 2970700 : *loc = reg;
284 : 2970700 : return true;
285 : : }
286 : :
287 : 127611795 : fmt = GET_RTX_FORMAT (code);
288 : 465608365 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 : : {
290 : 337996570 : if (fmt[i] == 'e')
291 : 173345393 : result = change_regs (&XEXP (*loc, i)) || result;
292 : 173819083 : else if (fmt[i] == 'E')
293 : : {
294 : 3131885 : int j;
295 : :
296 : 9999008 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 : 7379041 : result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 : : }
299 : : }
300 : 127611795 : return result;
301 : : }
302 : :
303 : : static bool
304 : 24781180 : change_regs_in_insn (rtx_insn **insn_ptr)
305 : : {
306 : 24781180 : rtx rtx = *insn_ptr;
307 : 24781180 : bool result = change_regs (&rtx);
308 : 24781180 : *insn_ptr = as_a <rtx_insn *> (rtx);
309 : 24781180 : return result;
310 : : }
311 : :
312 : : /* Attach MOVE to the edge E. The move is attached to the head of the
313 : : list if HEAD_P is TRUE. */
314 : : static void
315 : 2104533 : add_to_edge_list (edge e, move_t move, bool head_p)
316 : : {
317 : 2104533 : move_t last;
318 : :
319 : 0 : if (head_p || e->aux == NULL)
320 : : {
321 : 2104533 : move->next = (move_t) e->aux;
322 : 0 : e->aux = move;
323 : : }
324 : : else
325 : : {
326 : 0 : for (last = (move_t) e->aux; last->next != NULL; last = last->next)
327 : : ;
328 : 0 : last->next = move;
329 : 0 : move->next = NULL;
330 : : }
331 : 0 : }
332 : :
333 : : /* Create and return new pseudo-register with the same attributes as
334 : : ORIGINAL_REG. */
335 : : rtx
336 : 1192900 : ira_create_new_reg (rtx original_reg)
337 : : {
338 : 1192900 : rtx new_reg;
339 : :
340 : 1192900 : new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 : 1192900 : ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 : 1192900 : REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 : 1192900 : REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 : 1192900 : REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 : 1192900 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
346 : 2 : fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
347 : : REGNO (new_reg), REGNO (original_reg));
348 : 1192900 : ira_expand_reg_equiv ();
349 : 1192900 : return new_reg;
350 : : }
351 : :
352 : : /* Return TRUE if loop given by SUBNODE inside the loop given by
353 : : NODE. */
354 : : static bool
355 : 7685834 : subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356 : : {
357 : 24248167 : for (; subnode != NULL; subnode = subnode->parent)
358 : 18320798 : if (subnode == node)
359 : : return true;
360 : : return false;
361 : : }
362 : :
363 : : /* Set up member `reg' to REG for allocnos which has the same regno as
364 : : ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
365 : : static void
366 : 1124949 : set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 : : {
368 : 1124949 : int regno;
369 : 1124949 : ira_allocno_t a;
370 : 1124949 : ira_loop_tree_node_t node;
371 : :
372 : 1124949 : node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 : 1124949 : for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 : 8810783 : a != NULL;
375 : 7685834 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 : 15371668 : if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
377 : 1758465 : ALLOCNO_EMIT_DATA (a)->reg = reg;
378 : 1127243 : for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
379 : 2294 : ALLOCNO_EMIT_DATA (a)->reg = reg;
380 : : regno = ALLOCNO_REGNO (allocno);
381 : : for (a = allocno;;)
382 : : {
383 : 2528093 : if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 : : {
385 : 2237821 : node = node->parent;
386 : 2237821 : if (node == NULL)
387 : : break;
388 : 1650382 : a = node->regno_allocno_map[regno];
389 : : }
390 : 1940654 : if (a == NULL)
391 : 288071 : continue;
392 : 1652583 : if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
393 : : break;
394 : 1115073 : ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 : : }
396 : 1124949 : }
397 : :
398 : : /* Return true if there is an entry to given loop not from its parent
399 : : (or grandparent) block. For example, it is possible for two
400 : : adjacent loops inside another loop. */
401 : : static bool
402 : 195370 : entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403 : : {
404 : 195370 : ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 : 195370 : edge e;
406 : 195370 : edge_iterator ei;
407 : :
408 : 195370 : for (bb_node = loop_node->children;
409 : 3033589 : bb_node != NULL;
410 : 2838219 : bb_node = bb_node->next)
411 : 2838823 : if (bb_node->bb != NULL)
412 : : {
413 : 6741536 : FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
414 : 4063974 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
415 : 4063974 : && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 : : {
417 : 456571 : for (parent = src_loop_node->parent;
418 : 597045 : parent != NULL;
419 : 140474 : parent = parent->parent)
420 : 416293 : if (parent == loop_node)
421 : : break;
422 : 456571 : if (parent != NULL)
423 : : /* That is an exit from a nested loop -- skip it. */
424 : 275819 : continue;
425 : 180752 : for (parent = loop_node->parent;
426 : 181925 : parent != NULL;
427 : 1173 : parent = parent->parent)
428 : 181321 : if (src_loop_node == parent)
429 : : break;
430 : : if (parent == NULL)
431 : : return true;
432 : : }
433 : : }
434 : : return false;
435 : : }
436 : :
437 : : /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
438 : : static void
439 : 34710 : setup_entered_from_non_parent_p (void)
440 : : {
441 : 34710 : unsigned int i;
442 : 34710 : loop_p loop;
443 : :
444 : 34710 : ira_assert (current_loops != NULL);
445 : 282508 : FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
446 : 213088 : if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 : 195370 : ira_loop_nodes[i].entered_from_non_parent_p
448 : 195370 : = entered_from_non_parent_p (&ira_loop_nodes[i]);
449 : 34710 : }
450 : :
451 : : /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
452 : : DEST_ALLOCNO (assigned to memory) can be removed because it does
453 : : not change value of the destination. One possible reason for this
454 : : is the situation when SRC_ALLOCNO is not modified in the
455 : : corresponding loop. */
456 : : static bool
457 : 122931 : store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
458 : : {
459 : 122931 : int regno, orig_regno;
460 : 122931 : ira_allocno_t a;
461 : 122931 : ira_loop_tree_node_t node;
462 : :
463 : 122931 : ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 : : && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 : 122931 : orig_regno = ALLOCNO_REGNO (src_allocno);
466 : 122931 : regno = REGNO (allocno_emit_reg (dest_allocno));
467 : 122931 : for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 : 174993 : node != NULL;
469 : 52062 : node = node->parent)
470 : : {
471 : 174993 : a = node->regno_allocno_map[orig_regno];
472 : 174993 : ira_assert (a != NULL);
473 : 174993 : if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
474 : : /* We achieved the destination and everything is ok. */
475 : : return true;
476 : 150307 : else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 : : return false;
478 : 52290 : else if (node->entered_from_non_parent_p)
479 : : /* If there is a path from a destination loop block to the
480 : : source loop header containing basic blocks of non-parents
481 : : (grandparents) of the source loop, we should have checked
482 : : modifications of the pseudo on this path too to decide
483 : : about possibility to remove the store. It could be done by
484 : : solving a data-flow problem. Unfortunately such global
485 : : solution would complicate IR flattening. Therefore we just
486 : : prohibit removal of the store in such complicated case. */
487 : : return false;
488 : : }
489 : : /* It is actually a loop entry -- do not remove the store. */
490 : : return false;
491 : : }
492 : :
493 : : /* Generate and attach moves to the edge E. This looks at the final
494 : : regnos of allocnos living on the edge with the same original regno
495 : : to figure out when moves should be generated. */
496 : : static void
497 : 4030270 : generate_edge_moves (edge e)
498 : : {
499 : 4030270 : ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 : 4030270 : unsigned int regno;
501 : 4030270 : bitmap_iterator bi;
502 : 4030270 : ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 : 4030270 : move_t move;
504 : 4030270 : bitmap regs_live_in_dest, regs_live_out_src;
505 : :
506 : 4030270 : src_loop_node = IRA_BB_NODE (e->src)->parent;
507 : 4030270 : dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 : 4030270 : e->aux = NULL;
509 : 4030270 : if (src_loop_node == dest_loop_node)
510 : 3573170 : return;
511 : 457100 : src_map = src_loop_node->regno_allocno_map;
512 : 457100 : dest_map = dest_loop_node->regno_allocno_map;
513 : 457100 : regs_live_in_dest = df_get_live_in (e->dest);
514 : 457100 : regs_live_out_src = df_get_live_out (e->src);
515 : 6708059 : EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
516 : : FIRST_PSEUDO_REGISTER, regno, bi)
517 : 6250959 : if (bitmap_bit_p (regs_live_out_src, regno))
518 : : {
519 : 6250959 : src_allocno = src_map[regno];
520 : 6250959 : dest_allocno = dest_map[regno];
521 : 6250959 : if (REGNO (allocno_emit_reg (src_allocno))
522 : 6250959 : == REGNO (allocno_emit_reg (dest_allocno)))
523 : 4121740 : continue;
524 : : /* Remove unnecessary stores at the region exit. We should do
525 : : this for readonly memory for sure and this is guaranteed by
526 : : that we never generate moves on region borders (see
527 : : checking in function change_loop). */
528 : 2153905 : if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 : 123039 : && ALLOCNO_HARD_REGNO (src_allocno) >= 0
530 : 2252150 : && store_can_be_removed_p (src_allocno, dest_allocno))
531 : : {
532 : 24686 : ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 : 24686 : ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
534 : 24686 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
535 : 0 : fprintf (ira_dump_file, " Remove r%d:a%d->a%d(mem)\n",
536 : : regno, ALLOCNO_NUM (src_allocno),
537 : : ALLOCNO_NUM (dest_allocno));
538 : 24686 : continue;
539 : : }
540 : 2104533 : move = create_move (dest_allocno, src_allocno);
541 : 2104533 : add_to_edge_list (e, move, true);
542 : : }
543 : : }
544 : :
545 : : /* Bitmap of allocnos local for the current loop. */
546 : : static bitmap local_allocno_bitmap;
547 : :
548 : : /* This bitmap is used to find that we need to generate and to use a
549 : : new pseudo-register when processing allocnos with the same original
550 : : regno. */
551 : : static bitmap used_regno_bitmap;
552 : :
553 : : /* This bitmap contains regnos of allocnos which were renamed locally
554 : : because the allocnos correspond to disjoint live ranges in loops
555 : : with a common parent. */
556 : : static bitmap renamed_regno_bitmap;
557 : :
558 : : /* Change (if necessary) pseudo-registers inside loop given by loop
559 : : tree node NODE. */
560 : : static void
561 : 2873597 : change_loop (ira_loop_tree_node_t node)
562 : : {
563 : 2873597 : bitmap_iterator bi;
564 : 2873597 : unsigned int i;
565 : 2873597 : int regno;
566 : 2873597 : bool used_p;
567 : 2873597 : ira_allocno_t allocno, parent_allocno, *map;
568 : 2873597 : rtx_insn *insn;
569 : 2873597 : rtx original_reg;
570 : 2873597 : enum reg_class aclass, pclass;
571 : 2873597 : ira_loop_tree_node_t parent;
572 : :
573 : 2873597 : if (node != ira_loop_tree_root)
574 : : {
575 : 2838887 : ira_assert (current_loops != NULL);
576 : :
577 : 2838887 : if (node->bb != NULL)
578 : : {
579 : 32406935 : FOR_BB_INSNS (node->bb, insn)
580 : 29728708 : if (INSN_P (insn) && change_regs_in_insn (&insn))
581 : : {
582 : 2030370 : df_insn_rescan (insn);
583 : 2030370 : df_notes_rescan (insn);
584 : : }
585 : 2678227 : return;
586 : : }
587 : :
588 : 160660 : if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
589 : 0 : fprintf (ira_dump_file,
590 : : " Changing RTL for loop %d (header bb%d)\n",
591 : 0 : node->loop_num, node->loop->header->index);
592 : :
593 : 160660 : parent = ira_curr_loop_tree_node->parent;
594 : 160660 : map = parent->regno_allocno_map;
595 : 3086554 : EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 : : 0, i, bi)
597 : : {
598 : 2925894 : allocno = ira_allocnos[i];
599 : 2925894 : regno = ALLOCNO_REGNO (allocno);
600 : 2925894 : aclass = ALLOCNO_CLASS (allocno);
601 : 2925894 : pclass = ira_pressure_class_translate[aclass];
602 : 2925894 : parent_allocno = map[regno];
603 : 2925894 : ira_assert (regno < ira_reg_equiv_len);
604 : : /* We generate the same hard register move because the
605 : : reload pass can put an allocno into memory in this case
606 : : we will have live range splitting. If it does not happen
607 : : such the same hard register moves will be removed. The
608 : : worst case when the both allocnos are put into memory by
609 : : the reload is very rare. */
610 : 4728407 : if (parent_allocno != NULL
611 : 2925894 : && (ALLOCNO_HARD_REGNO (allocno)
612 : 2925894 : == ALLOCNO_HARD_REGNO (parent_allocno))
613 : 5672665 : && (ALLOCNO_HARD_REGNO (allocno) < 0
614 : 1095911 : || (parent->reg_pressure[pclass] + 1
615 : 1095911 : <= ira_class_hard_regs_num[pclass])
616 : 1022793 : || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 : 1022793 : [ALLOCNO_MODE (allocno)],
618 : : ALLOCNO_HARD_REGNO (allocno))
619 : : /* don't create copies because reload can spill an
620 : : allocno set by copy although the allocno will not
621 : : get memory slot. */
622 : 1022793 : || ira_equiv_no_lvalue_p (regno)
623 : 951809 : || (pic_offset_table_rtx != NULL
624 : 94964 : && (ALLOCNO_REGNO (allocno)
625 : 94964 : == (int) REGNO (pic_offset_table_rtx)))))
626 : 1802513 : continue;
627 : 1123381 : original_reg = allocno_emit_reg (allocno);
628 : 1123381 : if (parent_allocno == NULL
629 : 1123381 : || (REGNO (allocno_emit_reg (parent_allocno))
630 : 1123381 : == REGNO (original_reg)))
631 : : {
632 : 1123381 : if (internal_flag_ira_verbose > 3 && ira_dump_file)
633 : 0 : fprintf (ira_dump_file, " %i vs parent %i:",
634 : 0 : ALLOCNO_HARD_REGNO (allocno),
635 : 0 : ALLOCNO_HARD_REGNO (parent_allocno));
636 : 1123381 : set_allocno_reg (allocno, ira_create_new_reg (original_reg));
637 : : }
638 : : }
639 : : }
640 : : /* Rename locals: Local allocnos with same regno in different loops
641 : : might get the different hard register. So we need to change
642 : : ALLOCNO_REG. */
643 : 195370 : bitmap_and_compl (local_allocno_bitmap,
644 : 195370 : ira_curr_loop_tree_node->all_allocnos,
645 : 195370 : ira_curr_loop_tree_node->border_allocnos);
646 : 8331819 : EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 : : {
648 : 8136449 : allocno = ira_allocnos[i];
649 : 8136449 : regno = ALLOCNO_REGNO (allocno);
650 : 8136449 : if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 : 3545602 : continue;
652 : 4590847 : used_p = !bitmap_set_bit (used_regno_bitmap, regno);
653 : 4590847 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
654 : 4590847 : if (! used_p)
655 : 4589279 : continue;
656 : 1568 : bitmap_set_bit (renamed_regno_bitmap, regno);
657 : 1568 : set_allocno_reg (allocno, ira_create_new_reg (allocno_emit_reg (allocno)));
658 : : }
659 : : }
660 : :
661 : : /* Process to set up flag somewhere_renamed_p. */
662 : : static void
663 : 34710 : set_allocno_somewhere_renamed_p (void)
664 : : {
665 : 34710 : unsigned int regno;
666 : 34710 : ira_allocno_t allocno;
667 : 34710 : ira_allocno_iterator ai;
668 : :
669 : 11097053 : FOR_EACH_ALLOCNO (allocno, ai)
670 : : {
671 : 11062343 : regno = ALLOCNO_REGNO (allocno);
672 : 11062343 : if (bitmap_bit_p (renamed_regno_bitmap, regno)
673 : 11062343 : && REGNO (allocno_emit_reg (allocno)) == regno)
674 : 2258 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
675 : : }
676 : 34710 : }
677 : :
678 : : /* Return TRUE if move lists on all edges given in vector VEC are
679 : : equal. */
680 : : static bool
681 : 5278120 : eq_edge_move_lists_p (vec<edge, va_gc> *vec)
682 : : {
683 : 5278120 : move_t list;
684 : 5278120 : int i;
685 : :
686 : 5278120 : list = (move_t) EDGE_I (vec, 0)->aux;
687 : 7807668 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 : 2807168 : if (! eq_move_lists_p (list, (move_t) EDGE_I (vec, i)->aux))
689 : : return false;
690 : : return true;
691 : : }
692 : :
693 : : /* Look at all entry edges (if START_P) or exit edges of basic block
694 : : BB and put move lists at the BB start or end if it is possible. In
695 : : other words, this decreases code duplication of allocno moves. */
696 : : static void
697 : 5356454 : unify_moves (basic_block bb, bool start_p)
698 : : {
699 : 5356454 : int i;
700 : 5356454 : edge e;
701 : 5356454 : move_t list;
702 : 5356454 : vec<edge, va_gc> *vec;
703 : :
704 : 5356454 : vec = (start_p ? bb->preds : bb->succs);
705 : 5356454 : if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 : : return;
707 : 5000500 : e = EDGE_I (vec, 0);
708 : 5000500 : list = (move_t) e->aux;
709 : 5000500 : if (! start_p && control_flow_insn_p (BB_END (bb)))
710 : : return;
711 : 2964984 : e->aux = NULL;
712 : 4089503 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 : : {
714 : 1124519 : e = EDGE_I (vec, i);
715 : 1124519 : free_move_list ((move_t) e->aux);
716 : 1124519 : e->aux = NULL;
717 : : }
718 : 2964984 : if (start_p)
719 : 2488557 : at_bb_start[bb->index] = list;
720 : : else
721 : 476427 : at_bb_end[bb->index] = list;
722 : : }
723 : :
724 : : /* Last move (in move sequence being processed) setting up the
725 : : corresponding hard register. */
726 : : static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
727 : :
728 : : /* If the element value is equal to CURR_TICK then the corresponding
729 : : element in `hard_regno_last_set' is defined and correct. */
730 : : static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
731 : :
732 : : /* Last move (in move sequence being processed) setting up the
733 : : corresponding allocno. */
734 : : static move_t *allocno_last_set;
735 : :
736 : : /* If the element value is equal to CURR_TICK then the corresponding
737 : : element in . `allocno_last_set' is defined and correct. */
738 : : static int *allocno_last_set_check;
739 : :
740 : : /* Definition of vector of moves. */
741 : :
742 : : /* This vec contains moves sorted topologically (depth-first) on their
743 : : dependency graph. */
744 : : static vec<move_t> move_vec;
745 : :
746 : : /* The variable value is used to check correctness of values of
747 : : elements of arrays `hard_regno_last_set' and
748 : : `allocno_last_set_check'. */
749 : : static int curr_tick;
750 : :
751 : : /* This recursive function traverses dependencies of MOVE and produces
752 : : topological sorting (in depth-first order). */
753 : : static void
754 : 2146485 : traverse_moves (move_t move)
755 : : {
756 : 2146485 : int i;
757 : :
758 : 2146485 : if (move->visited_p)
759 : : return;
760 : 2080095 : move->visited_p = true;
761 : 2146485 : for (i = move->deps_num - 1; i >= 0; i--)
762 : 66390 : traverse_moves (move->deps[i]);
763 : 2080095 : move_vec.safe_push (move);
764 : : }
765 : :
766 : : /* Remove unnecessary moves in the LIST, makes topological sorting,
767 : : and removes cycles on hard reg dependencies by introducing new
768 : : allocnos assigned to memory and additional moves. It returns the
769 : : result move list. */
770 : : static move_t
771 : 363753 : modify_move_list (move_t list)
772 : : {
773 : 363753 : int i, n, nregs, hard_regno;
774 : 363753 : ira_allocno_t to, from;
775 : 363753 : move_t move, new_move, set_move, first, last;
776 : :
777 : 363753 : if (list == NULL)
778 : : return NULL;
779 : : /* Create move deps. */
780 : 363753 : curr_tick++;
781 : 2443848 : for (move = list; move != NULL; move = move->next)
782 : : {
783 : 2080095 : to = move->to;
784 : 2080095 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
785 : 97659 : continue;
786 : 1982436 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
787 : 3978600 : for (i = 0; i < nregs; i++)
788 : : {
789 : 1996164 : hard_regno_last_set[hard_regno + i] = move;
790 : 1996164 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
791 : : }
792 : : }
793 : 2443848 : for (move = list; move != NULL; move = move->next)
794 : : {
795 : 2080095 : from = move->from;
796 : 2080095 : to = move->to;
797 : 2080095 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
798 : : {
799 : 1945061 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
800 : 3901922 : for (n = i = 0; i < nregs; i++)
801 : 1956861 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
802 : 1835233 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
803 : 1835233 : != ALLOCNO_REGNO (from)))
804 : 66390 : n++;
805 : 1945061 : move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
806 : 3901922 : for (n = i = 0; i < nregs; i++)
807 : 1956861 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
808 : 1835233 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
809 : 1835233 : != ALLOCNO_REGNO (from)))
810 : 66390 : move->deps[n++] = hard_regno_last_set[hard_regno + i];
811 : 1945061 : move->deps_num = n;
812 : : }
813 : : }
814 : : /* Topological sorting: */
815 : 363753 : move_vec.truncate (0);
816 : 2807601 : for (move = list; move != NULL; move = move->next)
817 : 2080095 : traverse_moves (move);
818 : 363753 : last = NULL;
819 : 2807601 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
820 : : {
821 : 2080095 : move = move_vec[i];
822 : 2080095 : move->next = NULL;
823 : 2080095 : if (last != NULL)
824 : 1716342 : last->next = move;
825 : 2080095 : last = move;
826 : : }
827 : 363753 : first = move_vec.last ();
828 : : /* Removing cycles: */
829 : 363753 : curr_tick++;
830 : 363753 : move_vec.truncate (0);
831 : 2443848 : for (move = first; move != NULL; move = move->next)
832 : : {
833 : 2080095 : from = move->from;
834 : 2080095 : to = move->to;
835 : 2080095 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
836 : : {
837 : 1945061 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
838 : 3901922 : for (i = 0; i < nregs; i++)
839 : 1956861 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
840 : 4018 : && ALLOCNO_HARD_REGNO
841 : : (hard_regno_last_set[hard_regno + i]->to) >= 0)
842 : : {
843 : 4018 : int n, j;
844 : 4018 : ira_allocno_t new_allocno;
845 : :
846 : 4018 : set_move = hard_regno_last_set[hard_regno + i];
847 : : /* It does not matter what loop_tree_node (of TO or
848 : : FROM) to use for the new allocno because of
849 : : subsequent IRA internal representation
850 : : flattening. */
851 : 4018 : new_allocno
852 : 4018 : = create_new_allocno (ALLOCNO_REGNO (set_move->to),
853 : : ALLOCNO_LOOP_TREE_NODE (set_move->to));
854 : 4018 : ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
855 : 4018 : ira_set_allocno_class (new_allocno,
856 : 4018 : ALLOCNO_CLASS (set_move->to));
857 : 4018 : ira_create_allocno_objects (new_allocno);
858 : 4018 : ALLOCNO_ASSIGNED_P (new_allocno) = true;
859 : 4018 : ALLOCNO_HARD_REGNO (new_allocno) = -1;
860 : 4018 : ALLOCNO_EMIT_DATA (new_allocno)->reg
861 : 4018 : = ira_create_new_reg (allocno_emit_reg (set_move->to));
862 : :
863 : : /* Make it possibly conflicting with all earlier
864 : : created allocnos. Cases where temporary allocnos
865 : : created to remove the cycles are quite rare. */
866 : 4018 : n = ALLOCNO_NUM_OBJECTS (new_allocno);
867 : 4018 : gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
868 : 8036 : for (j = 0; j < n; j++)
869 : : {
870 : 4018 : ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
871 : :
872 : 4018 : OBJECT_MIN (new_obj) = 0;
873 : 4018 : OBJECT_MAX (new_obj) = ira_objects_num - 1;
874 : : }
875 : :
876 : 4018 : new_move = create_move (set_move->to, new_allocno);
877 : 4018 : set_move->to = new_allocno;
878 : 4018 : move_vec.safe_push (new_move);
879 : 4018 : ira_move_loops_num++;
880 : 4018 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
881 : 0 : fprintf (ira_dump_file,
882 : : " Creating temporary allocno a%dr%d\n",
883 : : ALLOCNO_NUM (new_allocno),
884 : 0 : REGNO (allocno_emit_reg (new_allocno)));
885 : : }
886 : : }
887 : 2080095 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
888 : 97659 : continue;
889 : 1982436 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
890 : 3978600 : for (i = 0; i < nregs; i++)
891 : : {
892 : 1996164 : hard_regno_last_set[hard_regno + i] = move;
893 : 1996164 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
894 : : }
895 : : }
896 : 731524 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
897 : : {
898 : 4018 : move = move_vec[i];
899 : 4018 : move->next = NULL;
900 : 4018 : last->next = move;
901 : 4018 : last = move;
902 : : }
903 : : return first;
904 : : }
905 : :
906 : : /* Generate RTX move insns from the move list LIST. This updates
907 : : allocation cost using move execution frequency FREQ. */
908 : : static rtx_insn *
909 : 363753 : emit_move_list (move_t list, int freq)
910 : : {
911 : 363753 : rtx to, from, dest;
912 : 363753 : int to_regno, from_regno, cost, regno;
913 : 363753 : rtx_insn *result, *insn;
914 : 363753 : rtx set;
915 : 363753 : machine_mode mode;
916 : 363753 : enum reg_class aclass;
917 : :
918 : 363753 : grow_reg_equivs ();
919 : 363753 : start_sequence ();
920 : 2811619 : for (; list != NULL; list = list->next)
921 : : {
922 : 2084113 : start_sequence ();
923 : 2084113 : to = allocno_emit_reg (list->to);
924 : 2084113 : to_regno = REGNO (to);
925 : 2084113 : from = allocno_emit_reg (list->from);
926 : 2084113 : from_regno = REGNO (from);
927 : 2084113 : emit_move_insn (to, from);
928 : 2084113 : list->insn = get_insns ();
929 : 2084113 : end_sequence ();
930 : 4168226 : for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
931 : : {
932 : : /* The reload needs to have set up insn codes. If the
933 : : reload sets up insn codes by itself, it may fail because
934 : : insns will have hard registers instead of pseudos and
935 : : there may be no machine insn with given hard
936 : : registers. */
937 : 2084113 : recog_memoized (insn);
938 : : /* Add insn to equiv init insn list if it is necessary.
939 : : Otherwise reload will not remove this insn if it decides
940 : : to use the equivalence. */
941 : 2084113 : if ((set = single_set (insn)) != NULL_RTX)
942 : : {
943 : 2084113 : dest = SET_DEST (set);
944 : 2084113 : if (GET_CODE (dest) == SUBREG)
945 : 0 : dest = SUBREG_REG (dest);
946 : 2084113 : ira_assert (REG_P (dest));
947 : 2084113 : regno = REGNO (dest);
948 : 2084113 : if (regno >= ira_reg_equiv_len
949 : 2084113 : || (ira_reg_equiv[regno].invariant == NULL_RTX
950 : 2084091 : && ira_reg_equiv[regno].constant == NULL_RTX))
951 : 2084080 : continue; /* regno has no equivalence. */
952 : 33 : ira_assert ((int) reg_equivs->length () > regno);
953 : 33 : reg_equiv_init (regno)
954 : 33 : = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
955 : : }
956 : : }
957 : 2084113 : if (ira_use_lra_p)
958 : 2084113 : ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
959 : 2084113 : emit_insn (list->insn);
960 : 2084113 : mode = ALLOCNO_MODE (list->to);
961 : 2084113 : aclass = ALLOCNO_CLASS (list->to);
962 : 2084113 : cost = 0;
963 : 2084113 : if (ALLOCNO_HARD_REGNO (list->to) < 0)
964 : : {
965 : 101677 : if (ALLOCNO_HARD_REGNO (list->from) >= 0)
966 : : {
967 : 101574 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
968 : 101574 : ira_store_cost += cost;
969 : : }
970 : : }
971 : 1982436 : else if (ALLOCNO_HARD_REGNO (list->from) < 0)
972 : : {
973 : 138949 : if (ALLOCNO_HARD_REGNO (list->to) >= 0)
974 : : {
975 : 138949 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
976 : 138949 : ira_load_cost += cost;
977 : : }
978 : : }
979 : : else
980 : : {
981 : 1843487 : ira_init_register_move_cost_if_necessary (mode);
982 : 1843487 : cost = ira_register_move_cost[mode][aclass][aclass] * freq;
983 : 1843487 : ira_shuffle_cost += cost;
984 : : }
985 : 2084113 : ira_overall_cost += cost;
986 : : }
987 : 363753 : result = get_insns ();
988 : 363753 : end_sequence ();
989 : 363753 : return result;
990 : : }
991 : :
992 : : /* Generate RTX move insns from move lists attached to basic blocks
993 : : and edges. */
994 : : static void
995 : 34710 : emit_moves (void)
996 : : {
997 : 34710 : basic_block bb;
998 : 34710 : edge_iterator ei;
999 : 34710 : edge e;
1000 : 34710 : rtx_insn *insns, *tmp, *next;
1001 : :
1002 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1003 : : {
1004 : 2678227 : if (at_bb_start[bb->index] != NULL)
1005 : : {
1006 : 143619 : at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
1007 : 143619 : insns
1008 : 143619 : = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
1009 : 143619 : tmp = BB_HEAD (bb);
1010 : 143619 : if (LABEL_P (tmp))
1011 : 23361 : tmp = NEXT_INSN (tmp);
1012 : 143619 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1013 : 143619 : tmp = NEXT_INSN (tmp);
1014 : : /* Make sure to put the location of TMP or a subsequent instruction
1015 : : to avoid inheriting the location of the previous instruction. */
1016 : 143619 : next = tmp;
1017 : 283444 : while (next && !NONDEBUG_INSN_P (next))
1018 : 139825 : next = NEXT_INSN (next);
1019 : 143619 : if (next)
1020 : 143619 : set_insn_locations (insns, INSN_LOCATION (next));
1021 : 143619 : if (tmp == BB_HEAD (bb))
1022 : 0 : emit_insn_before (insns, tmp);
1023 : 143619 : else if (tmp)
1024 : 143619 : emit_insn_after (insns, PREV_INSN (tmp));
1025 : : else
1026 : 0 : emit_insn_after (insns, get_last_insn ());
1027 : : }
1028 : :
1029 : 2678227 : if (at_bb_end[bb->index] != NULL)
1030 : : {
1031 : 97498 : at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1032 : 97498 : insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1033 : 97498 : ira_assert (! control_flow_insn_p (BB_END (bb)));
1034 : 97498 : emit_insn_after (insns, BB_END (bb));
1035 : : }
1036 : :
1037 : 6745849 : FOR_EACH_EDGE (e, ei, bb->succs)
1038 : : {
1039 : 4067622 : if (e->aux == NULL)
1040 : 3944986 : continue;
1041 : 122636 : ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1042 : : || ! EDGE_CRITICAL_P (e));
1043 : 122636 : e->aux = modify_move_list ((move_t) e->aux);
1044 : 122636 : insert_insn_on_edge
1045 : 245221 : (emit_move_list ((move_t) e->aux,
1046 : 245221 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1047 : : e);
1048 : 122636 : if (e->src->next_bb != e->dest)
1049 : 91999 : ira_additional_jumps_num++;
1050 : : }
1051 : : }
1052 : 34710 : }
1053 : :
1054 : : /* Update costs of A and corresponding allocnos on upper levels on the
1055 : : loop tree from reading (if READ_P) or writing A on an execution
1056 : : path with FREQ. */
1057 : : static void
1058 : 4168226 : update_costs (ira_allocno_t a, bool read_p, int freq)
1059 : : {
1060 : 10017548 : ira_loop_tree_node_t parent;
1061 : :
1062 : 10017548 : for (;;)
1063 : : {
1064 : 10017548 : ALLOCNO_NREFS (a)++;
1065 : 10017548 : ALLOCNO_FREQ (a) += freq;
1066 : 10017548 : ALLOCNO_MEMORY_COST (a)
1067 : 20035096 : += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1068 : 10017548 : [read_p ? 1 : 0] * freq);
1069 : 10017548 : if (ALLOCNO_CAP (a) != NULL)
1070 : : a = ALLOCNO_CAP (a);
1071 : 8486012 : else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1072 : 8486012 : || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1073 : : break;
1074 : : }
1075 : 4168226 : }
1076 : :
1077 : : /* Process moves from LIST with execution FREQ to add ranges, copies,
1078 : : and modify costs for allocnos involved in the moves. All regnos
1079 : : living through the list is in LIVE_THROUGH, and the loop tree node
1080 : : used to find corresponding allocnos is NODE. */
1081 : : static void
1082 : 9424076 : add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1083 : : bitmap live_through, int freq)
1084 : : {
1085 : 9424076 : int start, n;
1086 : 9424076 : unsigned int regno;
1087 : 9424076 : move_t move;
1088 : 9424076 : ira_allocno_t a;
1089 : 9424076 : ira_copy_t cp;
1090 : 9424076 : live_range_t r;
1091 : 9424076 : bitmap_iterator bi;
1092 : 9424076 : HARD_REG_SET hard_regs_live;
1093 : :
1094 : 9424076 : if (list == NULL)
1095 : 9060323 : return;
1096 : 363753 : n = 0;
1097 : 6317567 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1098 : 5953814 : n++;
1099 : 363753 : REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1100 : : /* This is a trick to guarantee that new ranges is not merged with
1101 : : the old ones. */
1102 : 363753 : ira_max_point++;
1103 : 363753 : start = ira_max_point;
1104 : 2447866 : for (move = list; move != NULL; move = move->next)
1105 : : {
1106 : 2084113 : ira_allocno_t from = move->from;
1107 : 2084113 : ira_allocno_t to = move->to;
1108 : 2084113 : int nr, i;
1109 : :
1110 : 2084113 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1111 : 2084113 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1112 : :
1113 : 2084113 : nr = ALLOCNO_NUM_OBJECTS (to);
1114 : 4183349 : for (i = 0; i < nr; i++)
1115 : : {
1116 : 2099236 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1117 : 2099236 : if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1118 : : {
1119 : 4018 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1120 : 0 : fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1121 : 0 : ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1122 : 4018 : ira_allocate_object_conflicts (to_obj, n);
1123 : : }
1124 : : }
1125 : 2084113 : ior_hard_reg_conflicts (from, hard_regs_live);
1126 : 2084113 : ior_hard_reg_conflicts (to, hard_regs_live);
1127 : :
1128 : 2084113 : update_costs (from, true, freq);
1129 : 2084113 : update_costs (to, false, freq);
1130 : 2084113 : cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1131 : 2084113 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1132 : 0 : fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1133 : : cp->num, ALLOCNO_NUM (cp->first),
1134 : 0 : REGNO (allocno_emit_reg (cp->first)),
1135 : : ALLOCNO_NUM (cp->second),
1136 : 0 : REGNO (allocno_emit_reg (cp->second)));
1137 : :
1138 : 2084113 : nr = ALLOCNO_NUM_OBJECTS (from);
1139 : 4183349 : for (i = 0; i < nr; i++)
1140 : : {
1141 : 2099236 : ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1142 : 2099236 : r = OBJECT_LIVE_RANGES (from_obj);
1143 : 2099236 : if (r == NULL || r->finish >= 0)
1144 : : {
1145 : 2095218 : ira_add_live_range_to_object (from_obj, start, ira_max_point);
1146 : 2095218 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1147 : 0 : fprintf (ira_dump_file,
1148 : : " Adding range [%d..%d] to allocno a%dr%d\n",
1149 : : start, ira_max_point, ALLOCNO_NUM (from),
1150 : 0 : REGNO (allocno_emit_reg (from)));
1151 : : }
1152 : : else
1153 : : {
1154 : 4018 : r->finish = ira_max_point;
1155 : 4018 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1156 : 0 : fprintf (ira_dump_file,
1157 : : " Adding range [%d..%d] to allocno a%dr%d\n",
1158 : : r->start, ira_max_point, ALLOCNO_NUM (from),
1159 : 0 : REGNO (allocno_emit_reg (from)));
1160 : : }
1161 : : }
1162 : 2084113 : ira_max_point++;
1163 : 2084113 : nr = ALLOCNO_NUM_OBJECTS (to);
1164 : 4183349 : for (i = 0; i < nr; i++)
1165 : : {
1166 : 2099236 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1167 : 2099236 : ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1168 : : }
1169 : 2084113 : ira_max_point++;
1170 : : }
1171 : 2447866 : for (move = list; move != NULL; move = move->next)
1172 : : {
1173 : 2084113 : int nr, i;
1174 : 2084113 : nr = ALLOCNO_NUM_OBJECTS (move->to);
1175 : 4183349 : for (i = 0; i < nr; i++)
1176 : : {
1177 : 2099236 : ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1178 : 2099236 : r = OBJECT_LIVE_RANGES (to_obj);
1179 : 2099236 : if (r->finish < 0)
1180 : : {
1181 : 2095218 : r->finish = ira_max_point - 1;
1182 : 2095218 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1183 : 0 : fprintf (ira_dump_file,
1184 : : " Adding range [%d..%d] to allocno a%dr%d\n",
1185 : : r->start, r->finish, ALLOCNO_NUM (move->to),
1186 : 0 : REGNO (allocno_emit_reg (move->to)));
1187 : : }
1188 : : }
1189 : : }
1190 : 4237472 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1191 : : {
1192 : 3873719 : ira_allocno_t to;
1193 : 3873719 : int nr, i;
1194 : :
1195 : 3873719 : a = node->regno_allocno_map[regno];
1196 : 3873719 : if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1197 : 6581 : a = to;
1198 : 3873719 : nr = ALLOCNO_NUM_OBJECTS (a);
1199 : 7839455 : for (i = 0; i < nr; i++)
1200 : : {
1201 : 3965736 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
1202 : 3965736 : ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1203 : : }
1204 : 3873719 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1205 : 0 : fprintf
1206 : 0 : (ira_dump_file,
1207 : : " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1208 : : start, ira_max_point - 1,
1209 : : to != NULL ? "upper level" : "",
1210 : 0 : ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1211 : : }
1212 : : }
1213 : :
1214 : : /* Process all move list to add ranges, conflicts, copies, and modify
1215 : : costs for allocnos involved in the moves. */
1216 : : static void
1217 : 34710 : add_ranges_and_copies (void)
1218 : : {
1219 : 34710 : basic_block bb;
1220 : 34710 : edge_iterator ei;
1221 : 34710 : edge e;
1222 : 34710 : ira_loop_tree_node_t node;
1223 : 34710 : bitmap live_through;
1224 : :
1225 : 34710 : live_through = ira_allocate_bitmap ();
1226 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1227 : : {
1228 : : /* It does not matter what loop_tree_node (of source or
1229 : : destination block) to use for searching allocnos by their
1230 : : regnos because of subsequent IR flattening. */
1231 : 2678227 : node = IRA_BB_NODE (bb)->parent;
1232 : 2678227 : bitmap_copy (live_through, df_get_live_in (bb));
1233 : 2678227 : add_range_and_copies_from_move_list
1234 : 2678227 : (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1235 : 2678227 : bitmap_copy (live_through, df_get_live_out (bb));
1236 : 2678227 : add_range_and_copies_from_move_list
1237 : 2678227 : (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1238 : 6745849 : FOR_EACH_EDGE (e, ei, bb->succs)
1239 : : {
1240 : 4067622 : bitmap_and (live_through,
1241 : 4067622 : df_get_live_in (e->dest), df_get_live_out (bb));
1242 : 4067622 : add_range_and_copies_from_move_list
1243 : 8133227 : ((move_t) e->aux, node, live_through,
1244 : 12200849 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1245 : : }
1246 : : }
1247 : 34710 : ira_free_bitmap (live_through);
1248 : 34710 : }
1249 : :
1250 : : /* The entry function changes code and generates shuffling allocnos on
1251 : : region borders for the regional (LOOPS_P is TRUE in this case)
1252 : : register allocation. */
1253 : : void
1254 : 1431622 : ira_emit (bool loops_p)
1255 : : {
1256 : 1431622 : basic_block bb;
1257 : 1431622 : rtx_insn *insn;
1258 : 1431622 : edge_iterator ei;
1259 : 1431622 : edge e;
1260 : 1431622 : ira_allocno_t a;
1261 : 1431622 : ira_allocno_iterator ai;
1262 : 1431622 : size_t sz;
1263 : :
1264 : 36497706 : FOR_EACH_ALLOCNO (a, ai)
1265 : 35066084 : ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1266 : 1431622 : if (! loops_p)
1267 : 1396912 : return;
1268 : 34710 : sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1269 : 34710 : at_bb_start = (move_t *) ira_allocate (sz);
1270 : 34710 : memset (at_bb_start, 0, sz);
1271 : 34710 : at_bb_end = (move_t *) ira_allocate (sz);
1272 : 34710 : memset (at_bb_end, 0, sz);
1273 : 34710 : local_allocno_bitmap = ira_allocate_bitmap ();
1274 : 34710 : used_regno_bitmap = ira_allocate_bitmap ();
1275 : 34710 : renamed_regno_bitmap = ira_allocate_bitmap ();
1276 : 34710 : max_regno_before_changing = max_reg_num ();
1277 : 34710 : ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1278 : 34710 : set_allocno_somewhere_renamed_p ();
1279 : 34710 : ira_free_bitmap (used_regno_bitmap);
1280 : 34710 : ira_free_bitmap (renamed_regno_bitmap);
1281 : 34710 : ira_free_bitmap (local_allocno_bitmap);
1282 : 34710 : setup_entered_from_non_parent_p ();
1283 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1284 : : {
1285 : 2678227 : at_bb_start[bb->index] = NULL;
1286 : 2678227 : at_bb_end[bb->index] = NULL;
1287 : 6745849 : FOR_EACH_EDGE (e, ei, bb->succs)
1288 : 4067622 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1289 : 4030270 : generate_edge_moves (e);
1290 : : }
1291 : 34710 : allocno_last_set
1292 : 34710 : = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1293 : 34710 : allocno_last_set_check
1294 : 34710 : = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1295 : 34710 : memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1296 : 34710 : memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1297 : 34710 : curr_tick = 0;
1298 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1299 : 2678227 : unify_moves (bb, true);
1300 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1301 : 2678227 : unify_moves (bb, false);
1302 : 34710 : move_vec.create (ira_allocnos_num);
1303 : 34710 : emit_moves ();
1304 : 34710 : add_ranges_and_copies ();
1305 : : /* Clean up: */
1306 : 2712937 : FOR_EACH_BB_FN (bb, cfun)
1307 : : {
1308 : 2678227 : free_move_list (at_bb_start[bb->index]);
1309 : 2678227 : free_move_list (at_bb_end[bb->index]);
1310 : 6745849 : FOR_EACH_EDGE (e, ei, bb->succs)
1311 : : {
1312 : 4067622 : free_move_list ((move_t) e->aux);
1313 : 4067622 : e->aux = NULL;
1314 : : }
1315 : : }
1316 : 34710 : move_vec.release ();
1317 : 34710 : ira_free (allocno_last_set_check);
1318 : 34710 : ira_free (allocno_last_set);
1319 : 34710 : commit_edge_insertions ();
1320 : : /* Fix insn codes. It is necessary to do it before reload because
1321 : : reload assumes initial insn codes defined. The insn codes can be
1322 : : invalidated by CFG infrastructure for example in jump
1323 : : redirection. */
1324 : 2803829 : FOR_EACH_BB_FN (bb, cfun)
1325 : 34761480 : FOR_BB_INSNS_REVERSE (bb, insn)
1326 : 31992361 : if (INSN_P (insn))
1327 : 26896222 : recog_memoized (insn);
1328 : 34710 : ira_free (at_bb_end);
1329 : 34710 : ira_free (at_bb_start);
1330 : : }
|
