Line data Source code
1 : /* Integrated Register Allocator. Changing code and generating moves.
2 : Copyright (C) 2006-2026 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 1481483 : ira_initiate_emit_data (void)
102 : {
103 1481483 : ira_allocno_t a;
104 1481483 : ira_allocno_iterator ai;
105 :
106 1481483 : ira_allocno_emit_data
107 1481483 : = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 : * sizeof (struct ira_emit_data));
109 1481483 : memset (ira_allocno_emit_data, 0,
110 1481483 : ira_allocnos_num * sizeof (struct ira_emit_data));
111 38003518 : FOR_EACH_ALLOCNO (a, ai)
112 36522035 : ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
113 1481483 : new_allocno_emit_data_vec.create (50);
114 :
115 1481483 : }
116 :
117 : /* Free the emit data. */
118 : void
119 1481483 : ira_finish_emit_data (void)
120 : {
121 1481483 : void_p p;
122 1481483 : ira_allocno_t a;
123 1481483 : ira_allocno_iterator ai;
124 :
125 1481483 : ira_free (ira_allocno_emit_data);
126 38007859 : FOR_EACH_ALLOCNO (a, ai)
127 36526376 : ALLOCNO_ADD_DATA (a) = NULL;
128 1485824 : for (;new_allocno_emit_data_vec.length () != 0;)
129 : {
130 4341 : p = new_allocno_emit_data_vec.pop ();
131 4341 : ira_free (p);
132 : }
133 1481483 : new_allocno_emit_data_vec.release ();
134 1481483 : }
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 4341 : create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140 : {
141 4341 : ira_allocno_t a;
142 :
143 4341 : a = ira_create_allocno (regno, false, loop_tree_node);
144 4341 : ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 4341 : memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
146 4341 : new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
147 4341 : 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 2199795 : create_move (ira_allocno_t to, ira_allocno_t from)
189 : {
190 2199795 : move_t move;
191 :
192 2199795 : move = (move_t) ira_allocate (sizeof (struct move));
193 2199795 : move->deps = NULL;
194 2199795 : move->deps_num = 0;
195 2199795 : move->to = to;
196 2199795 : move->from = from;
197 2199795 : move->next = NULL;
198 2199795 : move->insn = NULL;
199 2199795 : move->visited_p = false;
200 2199795 : return move;
201 : }
202 :
203 : /* Free memory for MOVE and its dependencies. */
204 : static void
205 2199795 : free_move (move_t move)
206 : {
207 2199795 : if (move->deps != NULL)
208 2019252 : ira_free (move->deps);
209 2199795 : ira_free (move);
210 2199795 : }
211 :
212 : /* Free memory for list of the moves given by its HEAD. */
213 : static void
214 10669384 : free_move_list (move_t head)
215 : {
216 10669384 : move_t next;
217 :
218 12869179 : for (; head != NULL; head = next)
219 : {
220 2199795 : next = head->next;
221 2199795 : 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 2857561 : eq_move_lists_p (move_t list1, move_t list2)
229 : {
230 2986927 : for (; list1 != NULL && list2 != NULL;
231 129366 : list1 = list1->next, list2 = list2->next)
232 131612 : if (list1->from != list2->from || list1->to != list2->to)
233 : return false;
234 2855315 : 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 205659698 : change_regs (rtx *loc)
261 : {
262 205659698 : int i, regno, result = false;
263 205659698 : const char *fmt;
264 205659698 : enum rtx_code code;
265 205659698 : rtx reg;
266 :
267 205659698 : if (*loc == NULL_RTX)
268 : return false;
269 178819803 : code = GET_CODE (*loc);
270 178819803 : if (code == REG)
271 : {
272 44495388 : regno = REGNO (*loc);
273 44495388 : if (regno < FIRST_PSEUDO_REGISTER)
274 : return false;
275 24214417 : if (regno >= max_regno_before_changing)
276 : /* It is a shared register which was changed already. */
277 : return false;
278 24214305 : if (ira_curr_regno_allocno_map[regno] == NULL)
279 : return false;
280 24206654 : reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
281 24206654 : if (reg == *loc)
282 : return false;
283 3238423 : *loc = reg;
284 3238423 : return true;
285 : }
286 :
287 134324415 : fmt = GET_RTX_FORMAT (code);
288 489641067 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 : {
290 355316652 : if (fmt[i] == 'e')
291 182924053 : result = change_regs (&XEXP (*loc, i)) || result;
292 182463782 : else if (fmt[i] == 'E')
293 : {
294 3171609 : int j;
295 :
296 10010109 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 7377051 : result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 : }
299 : }
300 134324415 : return result;
301 : }
302 :
303 : static bool
304 25968328 : change_regs_in_insn (rtx_insn **insn_ptr)
305 : {
306 25968328 : rtx rtx = *insn_ptr;
307 25968328 : bool result = change_regs (&rtx);
308 25968328 : *insn_ptr = as_a <rtx_insn *> (rtx);
309 25968328 : 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 2195454 : add_to_edge_list (edge e, move_t move, bool head_p)
316 : {
317 2195454 : move_t last;
318 :
319 0 : if (head_p || e->aux == NULL)
320 : {
321 2195454 : 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 1244174 : ira_create_new_reg (rtx original_reg)
337 : {
338 1244174 : rtx new_reg;
339 :
340 1244174 : new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 1244174 : ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 1244174 : REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 1244174 : REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 1244174 : REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 1244174 : 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 1244174 : ira_expand_reg_equiv ();
349 1244174 : return new_reg;
350 : }
351 :
352 : /* Return TRUE if loop given by SUBNODE inside the loop given by
353 : NODE. */
354 : static bool
355 8173103 : subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356 : {
357 25895265 : for (; subnode != NULL; subnode = subnode->parent)
358 19532802 : 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 1171297 : set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 : {
368 1171297 : int regno;
369 1171297 : ira_allocno_t a;
370 1171297 : ira_loop_tree_node_t node;
371 :
372 1171297 : node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 1171297 : for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 9344400 : a != NULL;
375 8173103 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 16346206 : if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
377 1810640 : ALLOCNO_EMIT_DATA (a)->reg = reg;
378 1173955 : for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
379 2658 : ALLOCNO_EMIT_DATA (a)->reg = reg;
380 : regno = ALLOCNO_REGNO (allocno);
381 : for (a = allocno;;)
382 : {
383 2628331 : if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 : {
385 2326477 : node = node->parent;
386 2326477 : if (node == NULL)
387 : break;
388 1707946 : a = node->regno_allocno_map[regno];
389 : }
390 2009800 : if (a == NULL)
391 299298 : continue;
392 1710502 : if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
393 : break;
394 1157736 : ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 : }
396 1171297 : }
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 203556 : entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403 : {
404 203556 : ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 203556 : edge e;
406 203556 : edge_iterator ei;
407 :
408 203556 : for (bb_node = loop_node->children;
409 3084345 : bb_node != NULL;
410 2880789 : bb_node = bb_node->next)
411 2881442 : if (bb_node->bb != NULL)
412 : {
413 6842204 : FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
414 4129600 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
415 4129600 : && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 : {
417 483744 : for (parent = src_loop_node->parent;
418 627906 : parent != NULL;
419 144162 : parent = parent->parent)
420 437183 : if (parent == loop_node)
421 : break;
422 483744 : if (parent != NULL)
423 : /* That is an exit from a nested loop -- skip it. */
424 293021 : continue;
425 190723 : for (parent = loop_node->parent;
426 191999 : parent != NULL;
427 1276 : parent = parent->parent)
428 191346 : 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 35370 : setup_entered_from_non_parent_p (void)
440 : {
441 35370 : unsigned int i;
442 35370 : loop_p loop;
443 :
444 35370 : ira_assert (current_loops != NULL);
445 292155 : FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
446 221415 : if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 203556 : ira_loop_nodes[i].entered_from_non_parent_p
448 203556 : = entered_from_non_parent_p (&ira_loop_nodes[i]);
449 35370 : }
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 126625 : store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
458 : {
459 126625 : int regno, orig_regno;
460 126625 : ira_allocno_t a;
461 126625 : ira_loop_tree_node_t node;
462 :
463 126625 : ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 : && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 126625 : orig_regno = ALLOCNO_REGNO (src_allocno);
466 126625 : regno = REGNO (allocno_emit_reg (dest_allocno));
467 126625 : for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 178687 : node != NULL;
469 52062 : node = node->parent)
470 : {
471 178687 : a = node->regno_allocno_map[orig_regno];
472 178687 : ira_assert (a != NULL);
473 178687 : if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
474 : /* We achieved the destination and everything is ok. */
475 : return true;
476 154520 : else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 : return false;
478 52281 : 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 4095489 : generate_edge_moves (edge e)
498 : {
499 4095489 : ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 4095489 : unsigned int regno;
501 4095489 : bitmap_iterator bi;
502 4095489 : ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 4095489 : move_t move;
504 4095489 : bitmap regs_live_in_dest, regs_live_out_src;
505 :
506 4095489 : src_loop_node = IRA_BB_NODE (e->src)->parent;
507 4095489 : dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 4095489 : e->aux = NULL;
509 4095489 : if (src_loop_node == dest_loop_node)
510 3611262 : return;
511 484227 : src_map = src_loop_node->regno_allocno_map;
512 484227 : dest_map = dest_loop_node->regno_allocno_map;
513 484227 : regs_live_in_dest = df_get_live_in (e->dest);
514 484227 : regs_live_out_src = df_get_live_out (e->src);
515 7225607 : EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
516 : FIRST_PSEUDO_REGISTER, regno, bi)
517 6741380 : if (bitmap_bit_p (regs_live_out_src, regno))
518 : {
519 6741380 : src_allocno = src_map[regno];
520 6741380 : dest_allocno = dest_map[regno];
521 6741380 : if (REGNO (allocno_emit_reg (src_allocno))
522 6741380 : == REGNO (allocno_emit_reg (dest_allocno)))
523 4521759 : 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 2243788 : if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 126711 : && ALLOCNO_HARD_REGNO (src_allocno) >= 0
530 2346246 : && store_can_be_removed_p (src_allocno, dest_allocno))
531 : {
532 24167 : ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 24167 : ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
534 24167 : 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 24167 : continue;
539 : }
540 2195454 : move = create_move (dest_allocno, src_allocno);
541 2195454 : 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 2916991 : change_loop (ira_loop_tree_node_t node)
562 : {
563 2916991 : bitmap_iterator bi;
564 2916991 : unsigned int i;
565 2916991 : int regno;
566 2916991 : bool used_p;
567 2916991 : ira_allocno_t allocno, parent_allocno, *map;
568 2916991 : rtx_insn *insn;
569 2916991 : rtx original_reg;
570 2916991 : enum reg_class aclass, pclass;
571 2916991 : ira_loop_tree_node_t parent;
572 :
573 2916991 : if (node != ira_loop_tree_root)
574 : {
575 2881621 : ira_assert (current_loops != NULL);
576 :
577 2881621 : if (node->bb != NULL)
578 : {
579 33689077 : FOR_BB_INSNS (node->bb, insn)
580 30975642 : if (INSN_P (insn) && change_regs_in_insn (&insn))
581 : {
582 2220797 : df_insn_rescan (insn);
583 2220797 : df_notes_rescan (insn);
584 : }
585 2713435 : return;
586 : }
587 :
588 168186 : 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 168186 : parent = ira_curr_loop_tree_node->parent;
594 168186 : map = parent->regno_allocno_map;
595 3323640 : EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 : 0, i, bi)
597 : {
598 3155454 : allocno = ira_allocnos[i];
599 3155454 : regno = ALLOCNO_REGNO (allocno);
600 3155454 : aclass = ALLOCNO_CLASS (allocno);
601 3155454 : pclass = ira_pressure_class_translate[aclass];
602 3155454 : parent_allocno = map[regno];
603 3155454 : 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 5141431 : if (parent_allocno != NULL
611 3155454 : && (ALLOCNO_HARD_REGNO (allocno)
612 3155454 : == ALLOCNO_HARD_REGNO (parent_allocno))
613 6129510 : && (ALLOCNO_HARD_REGNO (allocno) < 0
614 1160502 : || (parent->reg_pressure[pclass] + 1
615 1160502 : <= ira_class_hard_regs_num[pclass])
616 1075035 : || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 1075035 : [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 1075035 : || ira_equiv_no_lvalue_p (regno)
623 996246 : || (pic_offset_table_rtx != NULL
624 100079 : && (ALLOCNO_REGNO (allocno)
625 100079 : == (int) REGNO (pic_offset_table_rtx)))))
626 1985977 : continue;
627 1169477 : original_reg = allocno_emit_reg (allocno);
628 1169477 : if (parent_allocno == NULL
629 1169477 : || (REGNO (allocno_emit_reg (parent_allocno))
630 1169477 : == REGNO (original_reg)))
631 : {
632 1169477 : 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 1169477 : 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 203556 : bitmap_and_compl (local_allocno_bitmap,
644 203556 : ira_curr_loop_tree_node->all_allocnos,
645 203556 : ira_curr_loop_tree_node->border_allocnos);
646 8631939 : EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 : {
648 8428383 : allocno = ira_allocnos[i];
649 8428383 : regno = ALLOCNO_REGNO (allocno);
650 8428383 : if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 3664032 : continue;
652 4764351 : used_p = !bitmap_set_bit (used_regno_bitmap, regno);
653 4764351 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
654 4764351 : if (! used_p)
655 4762531 : continue;
656 1820 : bitmap_set_bit (renamed_regno_bitmap, regno);
657 1820 : 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 35370 : set_allocno_somewhere_renamed_p (void)
664 : {
665 35370 : unsigned int regno;
666 35370 : ira_allocno_t allocno;
667 35370 : ira_allocno_iterator ai;
668 :
669 11619207 : FOR_EACH_ALLOCNO (allocno, ai)
670 : {
671 11583837 : regno = ALLOCNO_REGNO (allocno);
672 11583837 : if (bitmap_bit_p (renamed_regno_bitmap, regno)
673 11583837 : && REGNO (allocno_emit_reg (allocno)) == regno)
674 2744 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
675 : }
676 35370 : }
677 :
678 : /* Return TRUE if move lists on all edges given in vector VEC are
679 : equal. */
680 : static bool
681 5344776 : eq_edge_move_lists_p (vec<edge, va_gc> *vec)
682 : {
683 5344776 : move_t list;
684 5344776 : int i;
685 :
686 5344776 : list = (move_t) EDGE_I (vec, 0)->aux;
687 7888367 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 2857561 : 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 5426870 : unify_moves (basic_block bb, bool start_p)
698 : {
699 5426870 : int i;
700 5426870 : edge e;
701 5426870 : move_t list;
702 5426870 : vec<edge, va_gc> *vec;
703 :
704 5426870 : vec = (start_p ? bb->preds : bb->succs);
705 5426870 : if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 : return;
707 5030806 : e = EDGE_I (vec, 0);
708 5030806 : list = (move_t) e->aux;
709 5030806 : if (! start_p && control_flow_insn_p (BB_END (bb)))
710 : return;
711 2999246 : e->aux = NULL;
712 4108196 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 : {
714 1108950 : e = EDGE_I (vec, i);
715 1108950 : free_move_list ((move_t) e->aux);
716 1108950 : e->aux = NULL;
717 : }
718 2999246 : if (start_p)
719 2501859 : at_bb_start[bb->index] = list;
720 : else
721 497387 : 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 : /* Definition of vector of moves. */
733 :
734 : /* This vec contains moves sorted topologically (depth-first) on their
735 : dependency graph. */
736 : static vec<move_t> move_vec;
737 :
738 : /* The variable value is used to check correctness of values of
739 : elements of arrays `hard_regno_last_set'. */
740 : static int curr_tick;
741 :
742 : /* This recursive function traverses dependencies of MOVE and produces
743 : topological sorting (in depth-first order). */
744 : static void
745 2233201 : traverse_moves (move_t move)
746 : {
747 2233201 : int i;
748 :
749 2233201 : if (move->visited_p)
750 : return;
751 2162758 : move->visited_p = true;
752 2233201 : for (i = move->deps_num - 1; i >= 0; i--)
753 70443 : traverse_moves (move->deps[i]);
754 2162758 : move_vec.safe_push (move);
755 : }
756 :
757 : /* Remove unnecessary moves in the LIST, makes topological sorting,
758 : and removes cycles on hard reg dependencies by introducing new
759 : allocnos assigned to memory and additional moves. It returns the
760 : result move list. */
761 : static move_t
762 383166 : modify_move_list (move_t list)
763 : {
764 383166 : int i, n, nregs, hard_regno;
765 383166 : ira_allocno_t to, from;
766 383166 : move_t move, new_move, set_move, first, last;
767 :
768 383166 : if (list == NULL)
769 : return NULL;
770 : /* Create move deps. */
771 383166 : curr_tick++;
772 2545924 : for (move = list; move != NULL; move = move->next)
773 : {
774 2162758 : to = move->to;
775 2162758 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
776 101897 : continue;
777 2060861 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
778 4134595 : for (i = 0; i < nregs; i++)
779 : {
780 2073734 : hard_regno_last_set[hard_regno + i] = move;
781 2073734 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
782 : }
783 : }
784 2545924 : for (move = list; move != NULL; move = move->next)
785 : {
786 2162758 : from = move->from;
787 2162758 : to = move->to;
788 2162758 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
789 : {
790 2019252 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
791 4050115 : for (n = i = 0; i < nregs; i++)
792 2030863 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
793 1906179 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
794 1906179 : != ALLOCNO_REGNO (from)))
795 70443 : n++;
796 2019252 : move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
797 4050115 : for (n = i = 0; i < nregs; i++)
798 2030863 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
799 1906179 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
800 1906179 : != ALLOCNO_REGNO (from)))
801 70443 : move->deps[n++] = hard_regno_last_set[hard_regno + i];
802 2019252 : move->deps_num = n;
803 : }
804 : }
805 : /* Topological sorting: */
806 383166 : move_vec.truncate (0);
807 2929090 : for (move = list; move != NULL; move = move->next)
808 2162758 : traverse_moves (move);
809 383166 : last = NULL;
810 2929090 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
811 : {
812 2162758 : move = move_vec[i];
813 2162758 : move->next = NULL;
814 2162758 : if (last != NULL)
815 1779592 : last->next = move;
816 2162758 : last = move;
817 : }
818 383166 : first = move_vec.last ();
819 : /* Removing cycles: */
820 383166 : curr_tick++;
821 383166 : move_vec.truncate (0);
822 2545924 : for (move = first; move != NULL; move = move->next)
823 : {
824 2162758 : from = move->from;
825 2162758 : to = move->to;
826 2162758 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
827 : {
828 2019252 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
829 4050115 : for (i = 0; i < nregs; i++)
830 2030863 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
831 4341 : && ALLOCNO_HARD_REGNO
832 : (hard_regno_last_set[hard_regno + i]->to) >= 0)
833 : {
834 4341 : int n, j;
835 4341 : ira_allocno_t new_allocno;
836 :
837 4341 : set_move = hard_regno_last_set[hard_regno + i];
838 : /* It does not matter what loop_tree_node (of TO or
839 : FROM) to use for the new allocno because of
840 : subsequent IRA internal representation
841 : flattening. */
842 4341 : new_allocno
843 4341 : = create_new_allocno (ALLOCNO_REGNO (set_move->to),
844 : ALLOCNO_LOOP_TREE_NODE (set_move->to));
845 4341 : ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
846 4341 : ira_set_allocno_class (new_allocno,
847 4341 : ALLOCNO_CLASS (set_move->to));
848 4341 : ira_create_allocno_objects (new_allocno);
849 4341 : ALLOCNO_ASSIGNED_P (new_allocno) = true;
850 4341 : ALLOCNO_HARD_REGNO (new_allocno) = -1;
851 4341 : ALLOCNO_EMIT_DATA (new_allocno)->reg
852 4341 : = ira_create_new_reg (allocno_emit_reg (set_move->to));
853 :
854 : /* Make it possibly conflicting with all earlier
855 : created allocnos. Cases where temporary allocnos
856 : created to remove the cycles are quite rare. */
857 4341 : n = ALLOCNO_NUM_OBJECTS (new_allocno);
858 4341 : gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
859 8682 : for (j = 0; j < n; j++)
860 : {
861 4341 : ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
862 :
863 4341 : OBJECT_MIN (new_obj) = 0;
864 4341 : OBJECT_MAX (new_obj) = ira_objects_num - 1;
865 : }
866 :
867 4341 : new_move = create_move (set_move->to, new_allocno);
868 4341 : set_move->to = new_allocno;
869 4341 : move_vec.safe_push (new_move);
870 4341 : ira_move_loops_num++;
871 4341 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
872 0 : fprintf (ira_dump_file,
873 : " Creating temporary allocno a%dr%d\n",
874 : ALLOCNO_NUM (new_allocno),
875 0 : REGNO (allocno_emit_reg (new_allocno)));
876 : }
877 : }
878 2162758 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
879 101897 : continue;
880 2060861 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
881 4134595 : for (i = 0; i < nregs; i++)
882 : {
883 2073734 : hard_regno_last_set[hard_regno + i] = move;
884 2073734 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
885 : }
886 : }
887 770673 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
888 : {
889 4341 : move = move_vec[i];
890 4341 : move->next = NULL;
891 4341 : last->next = move;
892 4341 : last = move;
893 : }
894 : return first;
895 : }
896 :
897 : /* Generate RTX move insns from the move list LIST. This updates
898 : allocation cost using move execution frequency FREQ. */
899 : static rtx_insn *
900 383166 : emit_move_list (move_t list, int freq)
901 : {
902 383166 : rtx to, from, dest;
903 383166 : int to_regno, from_regno, cost, regno;
904 383166 : rtx_insn *result, *insn;
905 383166 : rtx set;
906 383166 : machine_mode mode;
907 383166 : enum reg_class aclass;
908 :
909 383166 : grow_reg_equivs ();
910 383166 : start_sequence ();
911 2933431 : for (; list != NULL; list = list->next)
912 : {
913 2167099 : start_sequence ();
914 2167099 : to = allocno_emit_reg (list->to);
915 2167099 : to_regno = REGNO (to);
916 2167099 : from = allocno_emit_reg (list->from);
917 2167099 : from_regno = REGNO (from);
918 2167099 : emit_move_insn (to, from);
919 2167099 : list->insn = end_sequence ();
920 4334198 : for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
921 : {
922 : /* The reload needs to have set up insn codes. If the
923 : reload sets up insn codes by itself, it may fail because
924 : insns will have hard registers instead of pseudos and
925 : there may be no machine insn with given hard
926 : registers. */
927 2167099 : recog_memoized (insn);
928 : /* Add insn to equiv init insn list if it is necessary.
929 : Otherwise reload will not remove this insn if it decides
930 : to use the equivalence. */
931 2167099 : if ((set = single_set (insn)) != NULL_RTX)
932 : {
933 2167099 : dest = SET_DEST (set);
934 2167099 : if (GET_CODE (dest) == SUBREG)
935 0 : dest = SUBREG_REG (dest);
936 2167099 : ira_assert (REG_P (dest));
937 2167099 : regno = REGNO (dest);
938 2167099 : if (regno >= ira_reg_equiv_len
939 2167099 : || (ira_reg_equiv[regno].invariant == NULL_RTX
940 2167073 : && ira_reg_equiv[regno].constant == NULL_RTX))
941 2167056 : continue; /* regno has no equivalence. */
942 43 : ira_assert ((int) reg_equivs->length () > regno);
943 43 : reg_equiv_init (regno)
944 86 : = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
945 : }
946 : }
947 2167099 : if (ira_use_lra_p)
948 2167099 : ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
949 2167099 : emit_insn (list->insn);
950 2167099 : mode = ALLOCNO_MODE (list->to);
951 2167099 : aclass = ALLOCNO_CLASS (list->to);
952 2167099 : cost = 0;
953 2167099 : if (ALLOCNO_HARD_REGNO (list->to) < 0)
954 : {
955 106238 : if (ALLOCNO_HARD_REGNO (list->from) >= 0)
956 : {
957 106153 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
958 106153 : ira_store_cost += cost;
959 : }
960 : }
961 2060861 : else if (ALLOCNO_HARD_REGNO (list->from) < 0)
962 : {
963 147762 : if (ALLOCNO_HARD_REGNO (list->to) >= 0)
964 : {
965 147762 : cost = ira_memory_move_cost[mode][aclass][1] * freq;
966 147762 : ira_load_cost += cost;
967 : }
968 : }
969 : else
970 : {
971 1913099 : ira_init_register_move_cost_if_necessary (mode);
972 1913099 : cost = ira_register_move_cost[mode][aclass][aclass] * freq;
973 1913099 : ira_shuffle_cost += cost;
974 : }
975 2167099 : ira_overall_cost += cost;
976 : }
977 383166 : result = end_sequence ();
978 383166 : return result;
979 : }
980 :
981 : /* Generate RTX move insns from move lists attached to basic blocks
982 : and edges. */
983 : static void
984 35370 : emit_moves (void)
985 : {
986 35370 : basic_block bb;
987 35370 : edge_iterator ei;
988 35370 : edge e;
989 35370 : rtx_insn *insns, *tmp, *next;
990 :
991 2748805 : FOR_EACH_BB_FN (bb, cfun)
992 : {
993 2713435 : if (at_bb_start[bb->index] != NULL)
994 : {
995 136043 : at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
996 136043 : insns
997 136043 : = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
998 136043 : tmp = BB_HEAD (bb);
999 136043 : if (LABEL_P (tmp))
1000 22865 : tmp = NEXT_INSN (tmp);
1001 136043 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1002 136043 : tmp = NEXT_INSN (tmp);
1003 : /* Make sure to put the location of TMP or a subsequent instruction
1004 : to avoid inheriting the location of the previous instruction. */
1005 136043 : next = tmp;
1006 280284 : while (next && !NONDEBUG_INSN_P (next))
1007 144241 : next = NEXT_INSN (next);
1008 136043 : if (next)
1009 136043 : set_insn_locations (insns, INSN_LOCATION (next));
1010 136043 : if (tmp == BB_HEAD (bb))
1011 0 : emit_insn_before (insns, tmp);
1012 136043 : else if (tmp)
1013 136043 : emit_insn_after (insns, PREV_INSN (tmp));
1014 : else
1015 0 : emit_insn_after (insns, get_last_insn ());
1016 : }
1017 :
1018 2713435 : if (at_bb_end[bb->index] != NULL)
1019 : {
1020 109329 : at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1021 109329 : insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1022 109329 : ira_assert (! control_flow_insn_p (BB_END (bb)));
1023 109329 : emit_insn_after (insns, BB_END (bb));
1024 : }
1025 :
1026 6846999 : FOR_EACH_EDGE (e, ei, bb->succs)
1027 : {
1028 4133564 : if (e->aux == NULL)
1029 3995770 : continue;
1030 137794 : ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1031 : || ! EDGE_CRITICAL_P (e));
1032 137794 : e->aux = modify_move_list ((move_t) e->aux);
1033 137794 : insert_insn_on_edge
1034 275507 : (emit_move_list ((move_t) e->aux,
1035 275507 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1036 : e);
1037 137794 : if (e->src->next_bb != e->dest)
1038 91199 : ira_additional_jumps_num++;
1039 : }
1040 : }
1041 35370 : }
1042 :
1043 : /* Update costs of A and corresponding allocnos on upper levels on the
1044 : loop tree from reading (if READ_P) or writing A on an execution
1045 : path with FREQ. */
1046 : static void
1047 4334198 : update_costs (ira_allocno_t a, bool read_p, int freq)
1048 : {
1049 10274711 : ira_loop_tree_node_t parent;
1050 :
1051 10274711 : for (;;)
1052 : {
1053 10274711 : ALLOCNO_NREFS (a)++;
1054 10274711 : ALLOCNO_FREQ (a) += freq;
1055 10274711 : ALLOCNO_MEMORY_COST (a)
1056 20549422 : += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1057 10274711 : [read_p ? 1 : 0] * freq);
1058 10274711 : if (ALLOCNO_CAP (a) != NULL)
1059 : a = ALLOCNO_CAP (a);
1060 8701491 : else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1061 8701491 : || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1062 : break;
1063 : }
1064 4334198 : }
1065 :
1066 : /* Process moves from LIST with execution FREQ to add ranges, copies,
1067 : and modify costs for allocnos involved in the moves. All regnos
1068 : living through the list is in LIVE_THROUGH, and the loop tree node
1069 : used to find corresponding allocnos is NODE. */
1070 : static void
1071 9560434 : add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1072 : bitmap live_through, int freq)
1073 : {
1074 9560434 : int start, n;
1075 9560434 : unsigned int regno;
1076 9560434 : move_t move;
1077 9560434 : ira_allocno_t a;
1078 9560434 : ira_copy_t cp;
1079 9560434 : live_range_t r;
1080 9560434 : bitmap_iterator bi;
1081 9560434 : HARD_REG_SET hard_regs_live;
1082 :
1083 9560434 : if (list == NULL)
1084 9177268 : return;
1085 383166 : n = 0;
1086 6734999 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1087 6351833 : n++;
1088 383166 : REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1089 : /* This is a trick to guarantee that new ranges is not merged with
1090 : the old ones. */
1091 383166 : ira_max_point++;
1092 383166 : start = ira_max_point;
1093 2550265 : for (move = list; move != NULL; move = move->next)
1094 : {
1095 2167099 : ira_allocno_t from = move->from;
1096 2167099 : ira_allocno_t to = move->to;
1097 2167099 : int nr, i;
1098 :
1099 2167099 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1100 2167099 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1101 :
1102 2167099 : nr = ALLOCNO_NUM_OBJECTS (to);
1103 4348258 : for (i = 0; i < nr; i++)
1104 : {
1105 2181159 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1106 2181159 : if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1107 : {
1108 4341 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1109 0 : fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1110 0 : ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1111 4341 : ira_allocate_object_conflicts (to_obj, n);
1112 : }
1113 : }
1114 2167099 : ior_hard_reg_conflicts (from, hard_regs_live);
1115 2167099 : ior_hard_reg_conflicts (to, hard_regs_live);
1116 :
1117 2167099 : update_costs (from, true, freq);
1118 2167099 : update_costs (to, false, freq);
1119 2167099 : cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1120 2167099 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1121 0 : fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1122 : cp->num, ALLOCNO_NUM (cp->first),
1123 0 : REGNO (allocno_emit_reg (cp->first)),
1124 : ALLOCNO_NUM (cp->second),
1125 0 : REGNO (allocno_emit_reg (cp->second)));
1126 :
1127 2167099 : nr = ALLOCNO_NUM_OBJECTS (from);
1128 4348258 : for (i = 0; i < nr; i++)
1129 : {
1130 2181159 : ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1131 2181159 : r = OBJECT_LIVE_RANGES (from_obj);
1132 2181159 : if (r == NULL || r->finish >= 0)
1133 : {
1134 2176818 : ira_add_live_range_to_object (from_obj, start, ira_max_point);
1135 2176818 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1136 0 : fprintf (ira_dump_file,
1137 : " Adding range [%d..%d] to allocno a%dr%d\n",
1138 : start, ira_max_point, ALLOCNO_NUM (from),
1139 0 : REGNO (allocno_emit_reg (from)));
1140 : }
1141 : else
1142 : {
1143 4341 : r->finish = ira_max_point;
1144 4341 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1145 0 : fprintf (ira_dump_file,
1146 : " Adding range [%d..%d] to allocno a%dr%d\n",
1147 : r->start, ira_max_point, ALLOCNO_NUM (from),
1148 0 : REGNO (allocno_emit_reg (from)));
1149 : }
1150 : }
1151 2167099 : ira_max_point++;
1152 2167099 : nr = ALLOCNO_NUM_OBJECTS (to);
1153 4348258 : for (i = 0; i < nr; i++)
1154 : {
1155 2181159 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1156 2181159 : ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1157 : }
1158 2167099 : ira_max_point++;
1159 : }
1160 2550265 : for (move = list; move != NULL; move = move->next)
1161 : {
1162 2167099 : int nr, i;
1163 2167099 : nr = ALLOCNO_NUM_OBJECTS (move->to);
1164 4348258 : for (i = 0; i < nr; i++)
1165 : {
1166 2181159 : ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1167 2181159 : r = OBJECT_LIVE_RANGES (to_obj);
1168 2181159 : if (r->finish < 0)
1169 : {
1170 2176818 : r->finish = ira_max_point - 1;
1171 2176818 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1172 0 : fprintf (ira_dump_file,
1173 : " Adding range [%d..%d] to allocno a%dr%d\n",
1174 : r->start, r->finish, ALLOCNO_NUM (move->to),
1175 0 : REGNO (allocno_emit_reg (move->to)));
1176 : }
1177 : }
1178 : }
1179 4572241 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1180 : {
1181 4189075 : ira_allocno_t to;
1182 4189075 : int nr, i;
1183 :
1184 4189075 : a = node->regno_allocno_map[regno];
1185 4189075 : if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1186 8930 : a = to;
1187 4189075 : nr = ALLOCNO_NUM_OBJECTS (a);
1188 8477305 : for (i = 0; i < nr; i++)
1189 : {
1190 4288230 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
1191 4288230 : ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1192 : }
1193 4189075 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1194 0 : fprintf
1195 0 : (ira_dump_file,
1196 : " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1197 : start, ira_max_point - 1,
1198 : to != NULL ? "upper level" : "",
1199 0 : ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1200 : }
1201 : }
1202 :
1203 : /* Process all move list to add ranges, conflicts, copies, and modify
1204 : costs for allocnos involved in the moves. */
1205 : static void
1206 35370 : add_ranges_and_copies (void)
1207 : {
1208 35370 : basic_block bb;
1209 35370 : edge_iterator ei;
1210 35370 : edge e;
1211 35370 : ira_loop_tree_node_t node;
1212 35370 : bitmap live_through;
1213 :
1214 35370 : live_through = ira_allocate_bitmap ();
1215 2748805 : FOR_EACH_BB_FN (bb, cfun)
1216 : {
1217 : /* It does not matter what loop_tree_node (of source or
1218 : destination block) to use for searching allocnos by their
1219 : regnos because of subsequent IR flattening. */
1220 2713435 : node = IRA_BB_NODE (bb)->parent;
1221 2713435 : bitmap_copy (live_through, df_get_live_in (bb));
1222 2713435 : add_range_and_copies_from_move_list
1223 2713435 : (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1224 2713435 : bitmap_copy (live_through, df_get_live_out (bb));
1225 2713435 : add_range_and_copies_from_move_list
1226 2713435 : (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1227 6846999 : FOR_EACH_EDGE (e, ei, bb->succs)
1228 : {
1229 4133564 : bitmap_and (live_through,
1230 4133564 : df_get_live_in (e->dest), df_get_live_out (bb));
1231 4133564 : add_range_and_copies_from_move_list
1232 8265106 : ((move_t) e->aux, node, live_through,
1233 12398670 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1234 : }
1235 : }
1236 35370 : ira_free_bitmap (live_through);
1237 35370 : }
1238 :
1239 : /* The entry function changes code and generates shuffling allocnos on
1240 : region borders for the regional (LOOPS_P is TRUE in this case)
1241 : register allocation. */
1242 : void
1243 1481483 : ira_emit (bool loops_p)
1244 : {
1245 1481483 : basic_block bb;
1246 1481483 : rtx_insn *insn;
1247 1481483 : edge_iterator ei;
1248 1481483 : edge e;
1249 1481483 : ira_allocno_t a;
1250 1481483 : ira_allocno_iterator ai;
1251 1481483 : size_t sz;
1252 :
1253 38003518 : FOR_EACH_ALLOCNO (a, ai)
1254 36522035 : ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1255 1481483 : if (! loops_p)
1256 1446113 : return;
1257 35370 : sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1258 35370 : at_bb_start = (move_t *) ira_allocate (sz);
1259 35370 : memset (at_bb_start, 0, sz);
1260 35370 : at_bb_end = (move_t *) ira_allocate (sz);
1261 35370 : memset (at_bb_end, 0, sz);
1262 35370 : local_allocno_bitmap = ira_allocate_bitmap ();
1263 35370 : used_regno_bitmap = ira_allocate_bitmap ();
1264 35370 : renamed_regno_bitmap = ira_allocate_bitmap ();
1265 35370 : max_regno_before_changing = max_reg_num ();
1266 35370 : ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1267 35370 : set_allocno_somewhere_renamed_p ();
1268 35370 : ira_free_bitmap (used_regno_bitmap);
1269 35370 : ira_free_bitmap (renamed_regno_bitmap);
1270 35370 : ira_free_bitmap (local_allocno_bitmap);
1271 35370 : setup_entered_from_non_parent_p ();
1272 2748805 : FOR_EACH_BB_FN (bb, cfun)
1273 : {
1274 2713435 : at_bb_start[bb->index] = NULL;
1275 2713435 : at_bb_end[bb->index] = NULL;
1276 6846999 : FOR_EACH_EDGE (e, ei, bb->succs)
1277 4133564 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1278 4095489 : generate_edge_moves (e);
1279 : }
1280 35370 : memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1281 35370 : curr_tick = 0;
1282 2748805 : FOR_EACH_BB_FN (bb, cfun)
1283 2713435 : unify_moves (bb, true);
1284 2748805 : FOR_EACH_BB_FN (bb, cfun)
1285 2713435 : unify_moves (bb, false);
1286 35370 : move_vec.create (ira_allocnos_num);
1287 35370 : emit_moves ();
1288 35370 : add_ranges_and_copies ();
1289 : /* Clean up: */
1290 2748805 : FOR_EACH_BB_FN (bb, cfun)
1291 : {
1292 2713435 : free_move_list (at_bb_start[bb->index]);
1293 2713435 : free_move_list (at_bb_end[bb->index]);
1294 6846999 : FOR_EACH_EDGE (e, ei, bb->succs)
1295 : {
1296 4133564 : free_move_list ((move_t) e->aux);
1297 4133564 : e->aux = NULL;
1298 : }
1299 : }
1300 35370 : move_vec.release ();
1301 35370 : commit_edge_insertions ();
1302 : /* Fix insn codes. It is necessary to do it before reload because
1303 : reload assumes initial insn codes defined. The insn codes can be
1304 : invalidated by CFG infrastructure for example in jump
1305 : redirection. */
1306 2854261 : FOR_EACH_BB_FN (bb, cfun)
1307 36157887 : FOR_BB_INSNS_REVERSE (bb, insn)
1308 33338996 : if (INSN_P (insn))
1309 28169927 : recog_memoized (insn);
1310 35370 : ira_free (at_bb_end);
1311 35370 : ira_free (at_bb_start);
1312 : }
|
