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 1474414 : ira_initiate_emit_data (void)
102 : {
103 1474414 : ira_allocno_t a;
104 1474414 : ira_allocno_iterator ai;
105 :
106 1474414 : ira_allocno_emit_data
107 1474414 : = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 : * sizeof (struct ira_emit_data));
109 1474414 : memset (ira_allocno_emit_data, 0,
110 1474414 : ira_allocnos_num * sizeof (struct ira_emit_data));
111 37800071 : FOR_EACH_ALLOCNO (a, ai)
112 36325657 : ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
113 1474414 : new_allocno_emit_data_vec.create (50);
114 :
115 1474414 : }
116 :
117 : /* Free the emit data. */
118 : void
119 1474414 : ira_finish_emit_data (void)
120 : {
121 1474414 : void_p p;
122 1474414 : ira_allocno_t a;
123 1474414 : ira_allocno_iterator ai;
124 :
125 1474414 : ira_free (ira_allocno_emit_data);
126 37804738 : FOR_EACH_ALLOCNO (a, ai)
127 36330324 : ALLOCNO_ADD_DATA (a) = NULL;
128 1479081 : for (;new_allocno_emit_data_vec.length () != 0;)
129 : {
130 4667 : p = new_allocno_emit_data_vec.pop ();
131 4667 : ira_free (p);
132 : }
133 1474414 : new_allocno_emit_data_vec.release ();
134 1474414 : }
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 4667 : create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140 : {
141 4667 : ira_allocno_t a;
142 :
143 4667 : a = ira_create_allocno (regno, false, loop_tree_node);
144 4667 : ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 4667 : memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
146 4667 : new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
147 4667 : 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 2171455 : create_move (ira_allocno_t to, ira_allocno_t from)
189 : {
190 2171455 : move_t move;
191 :
192 2171455 : move = (move_t) ira_allocate (sizeof (struct move));
193 2171455 : move->deps = NULL;
194 2171455 : move->deps_num = 0;
195 2171455 : move->to = to;
196 2171455 : move->from = from;
197 2171455 : move->next = NULL;
198 2171455 : move->insn = NULL;
199 2171455 : move->visited_p = false;
200 2171455 : return move;
201 : }
202 :
203 : /* Free memory for MOVE and its dependencies. */
204 : static void
205 2171455 : free_move (move_t move)
206 : {
207 2171455 : if (move->deps != NULL)
208 1991222 : ira_free (move->deps);
209 2171455 : ira_free (move);
210 2171455 : }
211 :
212 : /* Free memory for list of the moves given by its HEAD. */
213 : static void
214 10557747 : free_move_list (move_t head)
215 : {
216 10557747 : move_t next;
217 :
218 12729202 : for (; head != NULL; head = next)
219 : {
220 2171455 : next = head->next;
221 2171455 : 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 2828242 : eq_move_lists_p (move_t list1, move_t list2)
229 : {
230 2954895 : for (; list1 != NULL && list2 != NULL;
231 126653 : list1 = list1->next, list2 = list2->next)
232 128901 : if (list1->from != list2->from || list1->to != list2->to)
233 : return false;
234 2825994 : 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 201768242 : change_regs (rtx *loc)
261 : {
262 201768242 : int i, regno, result = false;
263 201768242 : const char *fmt;
264 201768242 : enum rtx_code code;
265 201768242 : rtx reg;
266 :
267 201768242 : if (*loc == NULL_RTX)
268 : return false;
269 175590526 : code = GET_CODE (*loc);
270 175590526 : if (code == REG)
271 : {
272 43966664 : regno = REGNO (*loc);
273 43966664 : if (regno < FIRST_PSEUDO_REGISTER)
274 : return false;
275 23917820 : if (regno >= max_regno_before_changing)
276 : /* It is a shared register which was changed already. */
277 : return false;
278 23917708 : if (ira_curr_regno_allocno_map[regno] == NULL)
279 : return false;
280 23909902 : reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
281 23909902 : if (reg == *loc)
282 : return false;
283 3201952 : *loc = reg;
284 3201952 : return true;
285 : }
286 :
287 131623862 : fmt = GET_RTX_FORMAT (code);
288 479352288 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 : {
290 347728426 : if (fmt[i] == 'e')
291 179682378 : result = change_regs (&XEXP (*loc, i)) || result;
292 178004884 : else if (fmt[i] == 'E')
293 : {
294 3132691 : int j;
295 :
296 9862376 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 7262457 : result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 : }
299 : }
300 131623862 : return result;
301 : }
302 :
303 : static bool
304 25315015 : change_regs_in_insn (rtx_insn **insn_ptr)
305 : {
306 25315015 : rtx rtx = *insn_ptr;
307 25315015 : bool result = change_regs (&rtx);
308 25315015 : *insn_ptr = as_a <rtx_insn *> (rtx);
309 25315015 : 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 2166788 : add_to_edge_list (edge e, move_t move, bool head_p)
316 : {
317 2166788 : move_t last;
318 :
319 0 : if (head_p || e->aux == NULL)
320 : {
321 2166788 : 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 1227763 : ira_create_new_reg (rtx original_reg)
337 : {
338 1227763 : rtx new_reg;
339 :
340 1227763 : new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 1227763 : ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 1227763 : REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 1227763 : REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 1227763 : REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 1227763 : 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 1227763 : ira_expand_reg_equiv ();
349 1227763 : return new_reg;
350 : }
351 :
352 : /* Return TRUE if loop given by SUBNODE inside the loop given by
353 : NODE. */
354 : static bool
355 8089523 : subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356 : {
357 25665472 : for (; subnode != NULL; subnode = subnode->parent)
358 19368849 : 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 1155449 : set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 : {
368 1155449 : int regno;
369 1155449 : ira_allocno_t a;
370 1155449 : ira_loop_tree_node_t node;
371 :
372 1155449 : node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 1155449 : for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 9244972 : a != NULL;
375 8089523 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 16179046 : if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
377 1792900 : ALLOCNO_EMIT_DATA (a)->reg = reg;
378 1158047 : for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
379 2598 : ALLOCNO_EMIT_DATA (a)->reg = reg;
380 : regno = ALLOCNO_REGNO (allocno);
381 : for (a = allocno;;)
382 : {
383 2601471 : if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 : {
385 2300346 : node = node->parent;
386 2300346 : if (node == NULL)
387 : break;
388 1690697 : a = node->regno_allocno_map[regno];
389 : }
390 1991822 : if (a == NULL)
391 298625 : continue;
392 1693197 : if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
393 : break;
394 1147397 : ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 : }
396 1155449 : }
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 201919 : entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403 : {
404 201919 : ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 201919 : edge e;
406 201919 : edge_iterator ei;
407 :
408 201919 : for (bb_node = loop_node->children;
409 3052491 : bb_node != NULL;
410 2850572 : bb_node = bb_node->next)
411 2851289 : if (bb_node->bb != NULL)
412 : {
413 6770880 : FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
414 4087038 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
415 4087038 : && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 : {
417 478464 : for (parent = src_loop_node->parent;
418 622164 : parent != NULL;
419 143700 : parent = parent->parent)
420 433377 : if (parent == loop_node)
421 : break;
422 478464 : if (parent != NULL)
423 : /* That is an exit from a nested loop -- skip it. */
424 289677 : continue;
425 188787 : for (parent = loop_node->parent;
426 190111 : parent != NULL;
427 1324 : parent = parent->parent)
428 189394 : 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 35188 : setup_entered_from_non_parent_p (void)
440 : {
441 35188 : unsigned int i;
442 35188 : loop_p loop;
443 :
444 35188 : ira_assert (current_loops != NULL);
445 290065 : FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
446 219689 : if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 201919 : ira_loop_nodes[i].entered_from_non_parent_p
448 201919 : = entered_from_non_parent_p (&ira_loop_nodes[i]);
449 35188 : }
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 126176 : store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
458 : {
459 126176 : int regno, orig_regno;
460 126176 : ira_allocno_t a;
461 126176 : ira_loop_tree_node_t node;
462 :
463 126176 : ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 : && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 126176 : orig_regno = ALLOCNO_REGNO (src_allocno);
466 126176 : regno = REGNO (allocno_emit_reg (dest_allocno));
467 126176 : for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 178060 : node != NULL;
469 51884 : node = node->parent)
470 : {
471 178060 : a = node->regno_allocno_map[orig_regno];
472 178060 : ira_assert (a != NULL);
473 178060 : if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
474 : /* We achieved the destination and everything is ok. */
475 : return true;
476 153959 : else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 : return false;
478 52139 : 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 4053172 : generate_edge_moves (edge e)
498 : {
499 4053172 : ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 4053172 : unsigned int regno;
501 4053172 : bitmap_iterator bi;
502 4053172 : ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 4053172 : move_t move;
504 4053172 : bitmap regs_live_in_dest, regs_live_out_src;
505 :
506 4053172 : src_loop_node = IRA_BB_NODE (e->src)->parent;
507 4053172 : dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 4053172 : e->aux = NULL;
509 4053172 : if (src_loop_node == dest_loop_node)
510 3574155 : return;
511 479017 : src_map = src_loop_node->regno_allocno_map;
512 479017 : dest_map = dest_loop_node->regno_allocno_map;
513 479017 : regs_live_in_dest = df_get_live_in (e->dest);
514 479017 : regs_live_out_src = df_get_live_out (e->src);
515 7177266 : EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
516 : FIRST_PSEUDO_REGISTER, regno, bi)
517 6698249 : if (bitmap_bit_p (regs_live_out_src, regno))
518 : {
519 6698249 : src_allocno = src_map[regno];
520 6698249 : dest_allocno = dest_map[regno];
521 6698249 : if (REGNO (allocno_emit_reg (src_allocno))
522 6698249 : == REGNO (allocno_emit_reg (dest_allocno)))
523 4507360 : 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 2214990 : if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 126256 : && ALLOCNO_HARD_REGNO (src_allocno) >= 0
530 2317065 : && store_can_be_removed_p (src_allocno, dest_allocno))
531 : {
532 24101 : ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 24101 : ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
534 24101 : 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 24101 : continue;
539 : }
540 2166788 : move = create_move (dest_allocno, src_allocno);
541 2166788 : 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 2886655 : change_loop (ira_loop_tree_node_t node)
562 : {
563 2886655 : bitmap_iterator bi;
564 2886655 : unsigned int i;
565 2886655 : int regno;
566 2886655 : bool used_p;
567 2886655 : ira_allocno_t allocno, parent_allocno, *map;
568 2886655 : rtx_insn *insn;
569 2886655 : rtx original_reg;
570 2886655 : enum reg_class aclass, pclass;
571 2886655 : ira_loop_tree_node_t parent;
572 :
573 2886655 : if (node != ira_loop_tree_root)
574 : {
575 2851467 : ira_assert (current_loops != NULL);
576 :
577 2851467 : if (node->bb != NULL)
578 : {
579 32955932 : FOR_BB_INSNS (node->bb, insn)
580 30271196 : if (INSN_P (insn) && change_regs_in_insn (&insn))
581 : {
582 2199754 : df_insn_rescan (insn);
583 2199754 : df_notes_rescan (insn);
584 : }
585 2684736 : return;
586 : }
587 :
588 166731 : 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 166731 : parent = ira_curr_loop_tree_node->parent;
594 166731 : map = parent->regno_allocno_map;
595 3295821 : EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 : 0, i, bi)
597 : {
598 3129090 : allocno = ira_allocnos[i];
599 3129090 : regno = ALLOCNO_REGNO (allocno);
600 3129090 : aclass = ALLOCNO_CLASS (allocno);
601 3129090 : pclass = ira_pressure_class_translate[aclass];
602 3129090 : parent_allocno = map[regno];
603 3129090 : 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 5104517 : if (parent_allocno != NULL
611 3129090 : && (ALLOCNO_HARD_REGNO (allocno)
612 3129090 : == ALLOCNO_HARD_REGNO (parent_allocno))
613 6076622 : && (ALLOCNO_HARD_REGNO (allocno) < 0
614 1145638 : || (parent->reg_pressure[pclass] + 1
615 1145638 : <= ira_class_hard_regs_num[pclass])
616 1061218 : || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 1061218 : [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 1061218 : || ira_equiv_no_lvalue_p (regno)
623 980274 : || (pic_offset_table_rtx != NULL
624 99979 : && (ALLOCNO_REGNO (allocno)
625 99979 : == (int) REGNO (pic_offset_table_rtx)))))
626 1975427 : continue;
627 1153663 : original_reg = allocno_emit_reg (allocno);
628 1153663 : if (parent_allocno == NULL
629 1153663 : || (REGNO (allocno_emit_reg (parent_allocno))
630 1153663 : == REGNO (original_reg)))
631 : {
632 1153663 : 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 1153663 : 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 201919 : bitmap_and_compl (local_allocno_bitmap,
644 201919 : ira_curr_loop_tree_node->all_allocnos,
645 201919 : ira_curr_loop_tree_node->border_allocnos);
646 8562692 : EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 : {
648 8360773 : allocno = ira_allocnos[i];
649 8360773 : regno = ALLOCNO_REGNO (allocno);
650 8360773 : if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 3653325 : continue;
652 4707448 : used_p = !bitmap_set_bit (used_regno_bitmap, regno);
653 4707448 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
654 4707448 : if (! used_p)
655 4705662 : continue;
656 1786 : bitmap_set_bit (renamed_regno_bitmap, regno);
657 1786 : 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 35188 : set_allocno_somewhere_renamed_p (void)
664 : {
665 35188 : unsigned int regno;
666 35188 : ira_allocno_t allocno;
667 35188 : ira_allocno_iterator ai;
668 :
669 11525051 : FOR_EACH_ALLOCNO (allocno, ai)
670 : {
671 11489863 : regno = ALLOCNO_REGNO (allocno);
672 11489863 : if (bitmap_bit_p (renamed_regno_bitmap, regno)
673 11489863 : && REGNO (allocno_emit_reg (allocno)) == regno)
674 2679 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
675 : }
676 35188 : }
677 :
678 : /* Return TRUE if move lists on all edges given in vector VEC are
679 : equal. */
680 : static bool
681 5288843 : eq_edge_move_lists_p (vec<edge, va_gc> *vec)
682 : {
683 5288843 : move_t list;
684 5288843 : int i;
685 :
686 5288843 : list = (move_t) EDGE_I (vec, 0)->aux;
687 7806187 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 2828242 : 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 5369472 : unify_moves (basic_block bb, bool start_p)
698 : {
699 5369472 : int i;
700 5369472 : edge e;
701 5369472 : move_t list;
702 5369472 : vec<edge, va_gc> *vec;
703 :
704 5369472 : vec = (start_p ? bb->preds : bb->succs);
705 5369472 : if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 : return;
707 4977945 : e = EDGE_I (vec, 0);
708 4977945 : list = (move_t) e->aux;
709 4977945 : if (! start_p && control_flow_insn_p (BB_END (bb)))
710 : return;
711 2966300 : e->aux = NULL;
712 4063535 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 : {
714 1097235 : e = EDGE_I (vec, i);
715 1097235 : free_move_list ((move_t) e->aux);
716 1097235 : e->aux = NULL;
717 : }
718 2966300 : if (start_p)
719 2475074 : at_bb_start[bb->index] = list;
720 : else
721 491226 : 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 2204982 : traverse_moves (move_t move)
746 : {
747 2204982 : int i;
748 :
749 2204982 : if (move->visited_p)
750 : return;
751 2134044 : move->visited_p = true;
752 2204982 : for (i = move->deps_num - 1; i >= 0; i--)
753 70938 : traverse_moves (move->deps[i]);
754 2134044 : 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 379729 : modify_move_list (move_t list)
763 : {
764 379729 : int i, n, nregs, hard_regno;
765 379729 : ira_allocno_t to, from;
766 379729 : move_t move, new_move, set_move, first, last;
767 :
768 379729 : if (list == NULL)
769 : return NULL;
770 : /* Create move deps. */
771 379729 : curr_tick++;
772 2513773 : for (move = list; move != NULL; move = move->next)
773 : {
774 2134044 : to = move->to;
775 2134044 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
776 101504 : continue;
777 2032540 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
778 4078353 : for (i = 0; i < nregs; i++)
779 : {
780 2045813 : hard_regno_last_set[hard_regno + i] = move;
781 2045813 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
782 : }
783 : }
784 2513773 : for (move = list; move != NULL; move = move->next)
785 : {
786 2134044 : from = move->from;
787 2134044 : to = move->to;
788 2134044 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
789 : {
790 1991222 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
791 3994443 : for (n = i = 0; i < nregs; i++)
792 2003221 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
793 1878178 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
794 1878178 : != ALLOCNO_REGNO (from)))
795 70938 : n++;
796 1991222 : move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
797 3994443 : for (n = i = 0; i < nregs; i++)
798 2003221 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
799 1878178 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
800 1878178 : != ALLOCNO_REGNO (from)))
801 70938 : move->deps[n++] = hard_regno_last_set[hard_regno + i];
802 1991222 : move->deps_num = n;
803 : }
804 : }
805 : /* Topological sorting: */
806 379729 : move_vec.truncate (0);
807 2893502 : for (move = list; move != NULL; move = move->next)
808 2134044 : traverse_moves (move);
809 379729 : last = NULL;
810 2893502 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
811 : {
812 2134044 : move = move_vec[i];
813 2134044 : move->next = NULL;
814 2134044 : if (last != NULL)
815 1754315 : last->next = move;
816 2134044 : last = move;
817 : }
818 379729 : first = move_vec.last ();
819 : /* Removing cycles: */
820 379729 : curr_tick++;
821 379729 : move_vec.truncate (0);
822 2513773 : for (move = first; move != NULL; move = move->next)
823 : {
824 2134044 : from = move->from;
825 2134044 : to = move->to;
826 2134044 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
827 : {
828 1991222 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
829 3994443 : for (i = 0; i < nregs; i++)
830 2003221 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
831 4667 : && ALLOCNO_HARD_REGNO
832 : (hard_regno_last_set[hard_regno + i]->to) >= 0)
833 : {
834 4667 : int n, j;
835 4667 : ira_allocno_t new_allocno;
836 :
837 4667 : 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 4667 : new_allocno
843 4667 : = create_new_allocno (ALLOCNO_REGNO (set_move->to),
844 : ALLOCNO_LOOP_TREE_NODE (set_move->to));
845 4667 : ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
846 4667 : ira_set_allocno_class (new_allocno,
847 4667 : ALLOCNO_CLASS (set_move->to));
848 4667 : ira_create_allocno_objects (new_allocno);
849 4667 : ALLOCNO_ASSIGNED_P (new_allocno) = true;
850 4667 : ALLOCNO_HARD_REGNO (new_allocno) = -1;
851 4667 : ALLOCNO_EMIT_DATA (new_allocno)->reg
852 4667 : = 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 4667 : n = ALLOCNO_NUM_OBJECTS (new_allocno);
858 4667 : gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
859 9334 : for (j = 0; j < n; j++)
860 : {
861 4667 : ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
862 :
863 4667 : OBJECT_MIN (new_obj) = 0;
864 4667 : OBJECT_MAX (new_obj) = ira_objects_num - 1;
865 : }
866 :
867 4667 : new_move = create_move (set_move->to, new_allocno);
868 4667 : set_move->to = new_allocno;
869 4667 : move_vec.safe_push (new_move);
870 4667 : ira_move_loops_num++;
871 4667 : 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 2134044 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
879 101504 : continue;
880 2032540 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
881 4078353 : for (i = 0; i < nregs; i++)
882 : {
883 2045813 : hard_regno_last_set[hard_regno + i] = move;
884 2045813 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
885 : }
886 : }
887 764125 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
888 : {
889 4667 : move = move_vec[i];
890 4667 : move->next = NULL;
891 4667 : last->next = move;
892 4667 : 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 379729 : emit_move_list (move_t list, int freq)
901 : {
902 379729 : rtx to, from, dest;
903 379729 : int to_regno, from_regno, cost, regno;
904 379729 : rtx_insn *result, *insn;
905 379729 : rtx set;
906 379729 : machine_mode mode;
907 379729 : enum reg_class aclass;
908 :
909 379729 : grow_reg_equivs ();
910 379729 : start_sequence ();
911 2898169 : for (; list != NULL; list = list->next)
912 : {
913 2138711 : start_sequence ();
914 2138711 : to = allocno_emit_reg (list->to);
915 2138711 : to_regno = REGNO (to);
916 2138711 : from = allocno_emit_reg (list->from);
917 2138711 : from_regno = REGNO (from);
918 2138711 : emit_move_insn (to, from);
919 2138711 : list->insn = end_sequence ();
920 4277422 : 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 2138711 : 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 2138711 : if ((set = single_set (insn)) != NULL_RTX)
932 : {
933 2138711 : dest = SET_DEST (set);
934 2138711 : if (GET_CODE (dest) == SUBREG)
935 0 : dest = SUBREG_REG (dest);
936 2138711 : ira_assert (REG_P (dest));
937 2138711 : regno = REGNO (dest);
938 2138711 : if (regno >= ira_reg_equiv_len
939 2138711 : || (ira_reg_equiv[regno].invariant == NULL_RTX
940 2138685 : && ira_reg_equiv[regno].constant == NULL_RTX))
941 2138668 : 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 2138711 : if (ira_use_lra_p)
948 2138711 : ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
949 2138711 : emit_insn (list->insn);
950 2138711 : mode = ALLOCNO_MODE (list->to);
951 2138711 : aclass = ALLOCNO_CLASS (list->to);
952 2138711 : cost = 0;
953 2138711 : if (ALLOCNO_HARD_REGNO (list->to) < 0)
954 : {
955 106171 : if (ALLOCNO_HARD_REGNO (list->from) >= 0)
956 : {
957 106092 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
958 106092 : ira_store_cost += cost;
959 : }
960 : }
961 2032540 : else if (ALLOCNO_HARD_REGNO (list->from) < 0)
962 : {
963 147410 : if (ALLOCNO_HARD_REGNO (list->to) >= 0)
964 : {
965 147410 : cost = ira_memory_move_cost[mode][aclass][1] * freq;
966 147410 : ira_load_cost += cost;
967 : }
968 : }
969 : else
970 : {
971 1885130 : ira_init_register_move_cost_if_necessary (mode);
972 1885130 : cost = ira_register_move_cost[mode][aclass][aclass] * freq;
973 1885130 : ira_shuffle_cost += cost;
974 : }
975 2138711 : ira_overall_cost += cost;
976 : }
977 379729 : result = end_sequence ();
978 379729 : return result;
979 : }
980 :
981 : /* Generate RTX move insns from move lists attached to basic blocks
982 : and edges. */
983 : static void
984 35188 : emit_moves (void)
985 : {
986 35188 : basic_block bb;
987 35188 : edge_iterator ei;
988 35188 : edge e;
989 35188 : rtx_insn *insns, *tmp, *next;
990 :
991 2719924 : FOR_EACH_BB_FN (bb, cfun)
992 : {
993 2684736 : if (at_bb_start[bb->index] != NULL)
994 : {
995 134970 : at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
996 134970 : insns
997 134970 : = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
998 134970 : tmp = BB_HEAD (bb);
999 134970 : if (LABEL_P (tmp))
1000 22876 : tmp = NEXT_INSN (tmp);
1001 134970 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1002 134970 : 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 134970 : next = tmp;
1006 266445 : while (next && !NONDEBUG_INSN_P (next))
1007 131475 : next = NEXT_INSN (next);
1008 134970 : if (next)
1009 134970 : set_insn_locations (insns, INSN_LOCATION (next));
1010 134970 : if (tmp == BB_HEAD (bb))
1011 0 : emit_insn_before (insns, tmp);
1012 134970 : else if (tmp)
1013 134970 : emit_insn_after (insns, PREV_INSN (tmp));
1014 : else
1015 0 : emit_insn_after (insns, get_last_insn ());
1016 : }
1017 :
1018 2684736 : if (at_bb_end[bb->index] != NULL)
1019 : {
1020 108347 : at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1021 108347 : insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1022 108347 : ira_assert (! control_flow_insn_p (BB_END (bb)));
1023 108347 : emit_insn_after (insns, BB_END (bb));
1024 : }
1025 :
1026 6775776 : FOR_EACH_EDGE (e, ei, bb->succs)
1027 : {
1028 4091040 : if (e->aux == NULL)
1029 3954628 : continue;
1030 136412 : ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1031 : || ! EDGE_CRITICAL_P (e));
1032 136412 : e->aux = modify_move_list ((move_t) e->aux);
1033 136412 : insert_insn_on_edge
1034 272743 : (emit_move_list ((move_t) e->aux,
1035 272743 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1036 : e);
1037 136412 : if (e->src->next_bb != e->dest)
1038 90254 : ira_additional_jumps_num++;
1039 : }
1040 : }
1041 35188 : }
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 4277422 : update_costs (ira_allocno_t a, bool read_p, int freq)
1048 : {
1049 10178053 : ira_loop_tree_node_t parent;
1050 :
1051 10178053 : for (;;)
1052 : {
1053 10178053 : ALLOCNO_NREFS (a)++;
1054 10178053 : ALLOCNO_FREQ (a) += freq;
1055 10178053 : ALLOCNO_MEMORY_COST (a)
1056 20356106 : += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1057 10178053 : [read_p ? 1 : 0] * freq);
1058 10178053 : if (ALLOCNO_CAP (a) != NULL)
1059 : a = ALLOCNO_CAP (a);
1060 8608983 : else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1061 8608983 : || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1062 : break;
1063 : }
1064 4277422 : }
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 9460512 : add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1072 : bitmap live_through, int freq)
1073 : {
1074 9460512 : int start, n;
1075 9460512 : unsigned int regno;
1076 9460512 : move_t move;
1077 9460512 : ira_allocno_t a;
1078 9460512 : ira_copy_t cp;
1079 9460512 : live_range_t r;
1080 9460512 : bitmap_iterator bi;
1081 9460512 : HARD_REG_SET hard_regs_live;
1082 :
1083 9460512 : if (list == NULL)
1084 9080783 : return;
1085 379729 : n = 0;
1086 6687445 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1087 6307716 : n++;
1088 379729 : 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 379729 : ira_max_point++;
1092 379729 : start = ira_max_point;
1093 2518440 : for (move = list; move != NULL; move = move->next)
1094 : {
1095 2138711 : ira_allocno_t from = move->from;
1096 2138711 : ira_allocno_t to = move->to;
1097 2138711 : int nr, i;
1098 :
1099 2138711 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1100 2138711 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1101 :
1102 2138711 : nr = ALLOCNO_NUM_OBJECTS (to);
1103 4291902 : for (i = 0; i < nr; i++)
1104 : {
1105 2153191 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1106 2153191 : if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1107 : {
1108 4667 : 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 4667 : ira_allocate_object_conflicts (to_obj, n);
1112 : }
1113 : }
1114 2138711 : ior_hard_reg_conflicts (from, hard_regs_live);
1115 2138711 : ior_hard_reg_conflicts (to, hard_regs_live);
1116 :
1117 2138711 : update_costs (from, true, freq);
1118 2138711 : update_costs (to, false, freq);
1119 2138711 : cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1120 2138711 : 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 2138711 : nr = ALLOCNO_NUM_OBJECTS (from);
1128 4291902 : for (i = 0; i < nr; i++)
1129 : {
1130 2153191 : ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1131 2153191 : r = OBJECT_LIVE_RANGES (from_obj);
1132 2153191 : if (r == NULL || r->finish >= 0)
1133 : {
1134 2148524 : ira_add_live_range_to_object (from_obj, start, ira_max_point);
1135 2148524 : 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 4667 : r->finish = ira_max_point;
1144 4667 : 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 2138711 : ira_max_point++;
1152 2138711 : nr = ALLOCNO_NUM_OBJECTS (to);
1153 4291902 : for (i = 0; i < nr; i++)
1154 : {
1155 2153191 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1156 2153191 : ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1157 : }
1158 2138711 : ira_max_point++;
1159 : }
1160 2518440 : for (move = list; move != NULL; move = move->next)
1161 : {
1162 2138711 : int nr, i;
1163 2138711 : nr = ALLOCNO_NUM_OBJECTS (move->to);
1164 4291902 : for (i = 0; i < nr; i++)
1165 : {
1166 2153191 : ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1167 2153191 : r = OBJECT_LIVE_RANGES (to_obj);
1168 2153191 : if (r->finish < 0)
1169 : {
1170 2148524 : r->finish = ira_max_point - 1;
1171 2148524 : 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 4553401 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1180 : {
1181 4173672 : ira_allocno_t to;
1182 4173672 : int nr, i;
1183 :
1184 4173672 : a = node->regno_allocno_map[regno];
1185 4173672 : if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1186 8891 : a = to;
1187 4173672 : nr = ALLOCNO_NUM_OBJECTS (a);
1188 8447253 : for (i = 0; i < nr; i++)
1189 : {
1190 4273581 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
1191 4273581 : ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1192 : }
1193 4173672 : 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 35188 : add_ranges_and_copies (void)
1207 : {
1208 35188 : basic_block bb;
1209 35188 : edge_iterator ei;
1210 35188 : edge e;
1211 35188 : ira_loop_tree_node_t node;
1212 35188 : bitmap live_through;
1213 :
1214 35188 : live_through = ira_allocate_bitmap ();
1215 2719924 : 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 2684736 : node = IRA_BB_NODE (bb)->parent;
1221 2684736 : bitmap_copy (live_through, df_get_live_in (bb));
1222 2684736 : add_range_and_copies_from_move_list
1223 2684736 : (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1224 2684736 : bitmap_copy (live_through, df_get_live_out (bb));
1225 2684736 : add_range_and_copies_from_move_list
1226 2684736 : (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1227 6775776 : FOR_EACH_EDGE (e, ei, bb->succs)
1228 : {
1229 4091040 : bitmap_and (live_through,
1230 4091040 : df_get_live_in (e->dest), df_get_live_out (bb));
1231 4091040 : add_range_and_copies_from_move_list
1232 8179925 : ((move_t) e->aux, node, live_through,
1233 12270965 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1234 : }
1235 : }
1236 35188 : ira_free_bitmap (live_through);
1237 35188 : }
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 1474414 : ira_emit (bool loops_p)
1244 : {
1245 1474414 : basic_block bb;
1246 1474414 : rtx_insn *insn;
1247 1474414 : edge_iterator ei;
1248 1474414 : edge e;
1249 1474414 : ira_allocno_t a;
1250 1474414 : ira_allocno_iterator ai;
1251 1474414 : size_t sz;
1252 :
1253 37800071 : FOR_EACH_ALLOCNO (a, ai)
1254 36325657 : ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1255 1474414 : if (! loops_p)
1256 1439226 : return;
1257 35188 : sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1258 35188 : at_bb_start = (move_t *) ira_allocate (sz);
1259 35188 : memset (at_bb_start, 0, sz);
1260 35188 : at_bb_end = (move_t *) ira_allocate (sz);
1261 35188 : memset (at_bb_end, 0, sz);
1262 35188 : local_allocno_bitmap = ira_allocate_bitmap ();
1263 35188 : used_regno_bitmap = ira_allocate_bitmap ();
1264 35188 : renamed_regno_bitmap = ira_allocate_bitmap ();
1265 35188 : max_regno_before_changing = max_reg_num ();
1266 35188 : ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1267 35188 : set_allocno_somewhere_renamed_p ();
1268 35188 : ira_free_bitmap (used_regno_bitmap);
1269 35188 : ira_free_bitmap (renamed_regno_bitmap);
1270 35188 : ira_free_bitmap (local_allocno_bitmap);
1271 35188 : setup_entered_from_non_parent_p ();
1272 2719924 : FOR_EACH_BB_FN (bb, cfun)
1273 : {
1274 2684736 : at_bb_start[bb->index] = NULL;
1275 2684736 : at_bb_end[bb->index] = NULL;
1276 6775776 : FOR_EACH_EDGE (e, ei, bb->succs)
1277 4091040 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1278 4053172 : generate_edge_moves (e);
1279 : }
1280 35188 : memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1281 35188 : curr_tick = 0;
1282 2719924 : FOR_EACH_BB_FN (bb, cfun)
1283 2684736 : unify_moves (bb, true);
1284 2719924 : FOR_EACH_BB_FN (bb, cfun)
1285 2684736 : unify_moves (bb, false);
1286 35188 : move_vec.create (ira_allocnos_num);
1287 35188 : emit_moves ();
1288 35188 : add_ranges_and_copies ();
1289 : /* Clean up: */
1290 2719924 : FOR_EACH_BB_FN (bb, cfun)
1291 : {
1292 2684736 : free_move_list (at_bb_start[bb->index]);
1293 2684736 : free_move_list (at_bb_end[bb->index]);
1294 6775776 : FOR_EACH_EDGE (e, ei, bb->succs)
1295 : {
1296 4091040 : free_move_list ((move_t) e->aux);
1297 4091040 : e->aux = NULL;
1298 : }
1299 : }
1300 35188 : move_vec.release ();
1301 35188 : 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 2824209 : FOR_EACH_BB_FN (bb, cfun)
1307 35392885 : FOR_BB_INSNS_REVERSE (bb, insn)
1308 32603864 : if (INSN_P (insn))
1309 27487824 : recog_memoized (insn);
1310 35188 : ira_free (at_bb_end);
1311 35188 : ira_free (at_bb_start);
1312 : }
|
