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 1515921 : ira_initiate_emit_data (void)
102 : {
103 1515921 : ira_allocno_t a;
104 1515921 : ira_allocno_iterator ai;
105 :
106 1515921 : ira_allocno_emit_data
107 1515921 : = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 : * sizeof (struct ira_emit_data));
109 1515921 : memset (ira_allocno_emit_data, 0,
110 1515921 : ira_allocnos_num * sizeof (struct ira_emit_data));
111 38972296 : FOR_EACH_ALLOCNO (a, ai)
112 37456375 : ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
113 1515921 : new_allocno_emit_data_vec.create (50);
114 :
115 1515921 : }
116 :
117 : /* Free the emit data. */
118 : void
119 1515921 : ira_finish_emit_data (void)
120 : {
121 1515921 : void_p p;
122 1515921 : ira_allocno_t a;
123 1515921 : ira_allocno_iterator ai;
124 :
125 1515921 : ira_free (ira_allocno_emit_data);
126 38977819 : FOR_EACH_ALLOCNO (a, ai)
127 37461898 : ALLOCNO_ADD_DATA (a) = NULL;
128 1521444 : for (;new_allocno_emit_data_vec.length () != 0;)
129 : {
130 5523 : p = new_allocno_emit_data_vec.pop ();
131 5523 : ira_free (p);
132 : }
133 1515921 : new_allocno_emit_data_vec.release ();
134 1515921 : }
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 5523 : create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140 : {
141 5523 : ira_allocno_t a;
142 :
143 5523 : a = ira_create_allocno (regno, false, loop_tree_node);
144 5523 : ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 5523 : memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
146 5523 : new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
147 5523 : 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 2222952 : create_move (ira_allocno_t to, ira_allocno_t from)
189 : {
190 2222952 : move_t move;
191 :
192 2222952 : move = (move_t) ira_allocate (sizeof (struct move));
193 2222952 : move->deps = NULL;
194 2222952 : move->deps_num = 0;
195 2222952 : move->to = to;
196 2222952 : move->from = from;
197 2222952 : move->next = NULL;
198 2222952 : move->insn = NULL;
199 2222952 : move->visited_p = false;
200 2222952 : return move;
201 : }
202 :
203 : /* Free memory for MOVE and its dependencies. */
204 : static void
205 2222952 : free_move (move_t move)
206 : {
207 2222952 : if (move->deps != NULL)
208 2038590 : ira_free (move->deps);
209 2222952 : ira_free (move);
210 2222952 : }
211 :
212 : /* Free memory for list of the moves given by its HEAD. */
213 : static void
214 11122228 : free_move_list (move_t head)
215 : {
216 11122228 : move_t next;
217 :
218 13345180 : for (; head != NULL; head = next)
219 : {
220 2222952 : next = head->next;
221 2222952 : 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 2983958 : eq_move_lists_p (move_t list1, move_t list2)
229 : {
230 3111350 : for (; list1 != NULL && list2 != NULL;
231 127392 : list1 = list1->next, list2 = list2->next)
232 129948 : if (list1->from != list2->from || list1->to != list2->to)
233 : return false;
234 2981402 : 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 217305794 : change_regs (rtx *loc)
261 : {
262 217305794 : int i, regno, result = false;
263 217305794 : const char *fmt;
264 217305794 : enum rtx_code code;
265 217305794 : rtx reg;
266 :
267 217305794 : if (*loc == NULL_RTX)
268 : return false;
269 188474525 : code = GET_CODE (*loc);
270 188474525 : if (code == REG)
271 : {
272 46219168 : regno = REGNO (*loc);
273 46219168 : if (regno < FIRST_PSEUDO_REGISTER)
274 : return false;
275 25051580 : if (regno >= max_regno_before_changing)
276 : /* It is a shared register which was changed already. */
277 : return false;
278 25051468 : if (ira_curr_regno_allocno_map[regno] == NULL)
279 : return false;
280 25043191 : reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
281 25043191 : if (reg == *loc)
282 : return false;
283 3321643 : *loc = reg;
284 3321643 : return true;
285 : }
286 :
287 142255357 : fmt = GET_RTX_FORMAT (code);
288 521058082 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 : {
290 378802725 : if (fmt[i] == 'e')
291 192550606 : result = change_regs (&XEXP (*loc, i)) || result;
292 196523378 : else if (fmt[i] == 'E')
293 : {
294 3287583 : int j;
295 :
296 10405549 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 7668612 : result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 : }
299 : }
300 142255357 : return result;
301 : }
302 :
303 : static bool
304 27908481 : change_regs_in_insn (rtx_insn **insn_ptr)
305 : {
306 27908481 : rtx rtx = *insn_ptr;
307 27908481 : bool result = change_regs (&rtx);
308 27908481 : *insn_ptr = as_a <rtx_insn *> (rtx);
309 27908481 : 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 2217429 : add_to_edge_list (edge e, move_t move, bool head_p)
316 : {
317 2217429 : move_t last;
318 :
319 0 : if (head_p || e->aux == NULL)
320 : {
321 2217429 : 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 1253925 : ira_create_new_reg (rtx original_reg)
337 : {
338 1253925 : rtx new_reg;
339 :
340 1253925 : new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 1253925 : ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 1253925 : REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 1253925 : REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 1253925 : REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 1253925 : 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 1253925 : ira_expand_reg_equiv ();
349 1253925 : return new_reg;
350 : }
351 :
352 : /* Return TRUE if loop given by SUBNODE inside the loop given by
353 : NODE. */
354 : static bool
355 7952158 : subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356 : {
357 25260306 : for (; subnode != NULL; subnode = subnode->parent)
358 19142463 : 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 1178004 : set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 : {
368 1178004 : int regno;
369 1178004 : ira_allocno_t a;
370 1178004 : ira_loop_tree_node_t node;
371 :
372 1178004 : node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 1178004 : for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 9130162 : a != NULL;
375 7952158 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 15904316 : if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
377 1834315 : ALLOCNO_EMIT_DATA (a)->reg = reg;
378 1180980 : for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
379 2976 : ALLOCNO_EMIT_DATA (a)->reg = reg;
380 : regno = ALLOCNO_REGNO (allocno);
381 : for (a = allocno;;)
382 : {
383 2662262 : if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 : {
385 2353254 : node = node->parent;
386 2353254 : if (node == NULL)
387 : break;
388 1727156 : a = node->regno_allocno_map[regno];
389 : }
390 2036164 : if (a == NULL)
391 306186 : continue;
392 1729978 : if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
393 : break;
394 1178072 : ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 : }
396 1178004 : }
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 204619 : entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403 : {
404 204619 : ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 204619 : edge e;
406 204619 : edge_iterator ei;
407 :
408 204619 : for (bb_node = loop_node->children;
409 3193038 : bb_node != NULL;
410 2988419 : bb_node = bb_node->next)
411 2989251 : if (bb_node->bb != NULL)
412 : {
413 7117651 : FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
414 4297769 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
415 4297769 : && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 : {
417 490219 : for (parent = src_loop_node->parent;
418 639567 : parent != NULL;
419 149348 : parent = parent->parent)
420 448617 : if (parent == loop_node)
421 : break;
422 490219 : if (parent != NULL)
423 : /* That is an exit from a nested loop -- skip it. */
424 299269 : continue;
425 190950 : for (parent = loop_node->parent;
426 192509 : parent != NULL;
427 1559 : parent = parent->parent)
428 191677 : 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 36077 : setup_entered_from_non_parent_p (void)
440 : {
441 36077 : unsigned int i;
442 36077 : loop_p loop;
443 :
444 36077 : ira_assert (current_loops != NULL);
445 260117 : FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
446 224040 : if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 204619 : ira_loop_nodes[i].entered_from_non_parent_p
448 204619 : = entered_from_non_parent_p (&ira_loop_nodes[i]);
449 36077 : }
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 126062 : store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
458 : {
459 126062 : int regno, orig_regno;
460 126062 : ira_allocno_t a;
461 126062 : ira_loop_tree_node_t node;
462 :
463 126062 : ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 : && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 126062 : orig_regno = ALLOCNO_REGNO (src_allocno);
466 126062 : regno = REGNO (allocno_emit_reg (dest_allocno));
467 126062 : for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 174296 : node != NULL;
469 48234 : node = node->parent)
470 : {
471 174296 : a = node->regno_allocno_map[orig_regno];
472 174296 : ira_assert (a != NULL);
473 174296 : if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
474 : /* We achieved the destination and everything is ok. */
475 : return true;
476 153115 : else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 : return false;
478 48610 : 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 4263534 : generate_edge_moves (edge e)
498 : {
499 4263534 : ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 4263534 : unsigned int regno;
501 4263534 : bitmap_iterator bi;
502 4263534 : ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 4263534 : move_t move;
504 4263534 : bitmap regs_live_in_dest, regs_live_out_src;
505 :
506 4263534 : src_loop_node = IRA_BB_NODE (e->src)->parent;
507 4263534 : dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 4263534 : e->aux = NULL;
509 4263534 : if (src_loop_node == dest_loop_node)
510 3772633 : return;
511 490901 : src_map = src_loop_node->regno_allocno_map;
512 490901 : dest_map = dest_loop_node->regno_allocno_map;
513 490901 : regs_live_in_dest = df_get_live_in (e->dest);
514 490901 : regs_live_out_src = df_get_live_out (e->src);
515 7405339 : EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
516 : FIRST_PSEUDO_REGISTER, regno, bi)
517 6914438 : if (bitmap_bit_p (regs_live_out_src, regno))
518 : {
519 6914438 : src_allocno = src_map[regno];
520 6914438 : dest_allocno = dest_map[regno];
521 6914438 : if (REGNO (allocno_emit_reg (src_allocno))
522 6914438 : == REGNO (allocno_emit_reg (dest_allocno)))
523 4675828 : 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 2259791 : if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 126154 : && ALLOCNO_HARD_REGNO (src_allocno) >= 0
530 2364672 : && store_can_be_removed_p (src_allocno, dest_allocno))
531 : {
532 21181 : ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 21181 : ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
534 21181 : 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 21181 : continue;
539 : }
540 2217429 : move = create_move (dest_allocno, src_allocno);
541 2217429 : 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 3025679 : change_loop (ira_loop_tree_node_t node)
562 : {
563 3025679 : bitmap_iterator bi;
564 3025679 : unsigned int i;
565 3025679 : int regno;
566 3025679 : bool used_p;
567 3025679 : ira_allocno_t allocno, parent_allocno, *map;
568 3025679 : rtx_insn *insn;
569 3025679 : rtx original_reg;
570 3025679 : enum reg_class aclass, pclass;
571 3025679 : ira_loop_tree_node_t parent;
572 :
573 3025679 : if (node != ira_loop_tree_root)
574 : {
575 2989602 : ira_assert (current_loops != NULL);
576 :
577 2989602 : if (node->bb != NULL)
578 : {
579 35901415 : FOR_BB_INSNS (node->bb, insn)
580 33080355 : if (INSN_P (insn) && change_regs_in_insn (&insn))
581 : {
582 2275361 : df_insn_rescan (insn);
583 2275361 : df_notes_rescan (insn);
584 : }
585 2821060 : return;
586 : }
587 :
588 168542 : 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 168542 : parent = ira_curr_loop_tree_node->parent;
594 168542 : map = parent->regno_allocno_map;
595 3375605 : EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 : 0, i, bi)
597 : {
598 3207063 : allocno = ira_allocnos[i];
599 3207063 : regno = ALLOCNO_REGNO (allocno);
600 3207063 : aclass = ALLOCNO_CLASS (allocno);
601 3207063 : pclass = ira_pressure_class_translate[aclass];
602 3207063 : parent_allocno = map[regno];
603 3207063 : 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 5238121 : if (parent_allocno != NULL
611 3207063 : && (ALLOCNO_HARD_REGNO (allocno)
612 3207063 : == ALLOCNO_HARD_REGNO (parent_allocno))
613 6225751 : && (ALLOCNO_HARD_REGNO (allocno) < 0
614 1154984 : || (parent->reg_pressure[pclass] + 1
615 1154984 : <= ira_class_hard_regs_num[pclass])
616 1067869 : || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 1067869 : [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 1067869 : || ira_equiv_no_lvalue_p (regno)
623 995744 : || (pic_offset_table_rtx != NULL
624 100843 : && (ALLOCNO_REGNO (allocno)
625 100843 : == (int) REGNO (pic_offset_table_rtx)))))
626 2031058 : continue;
627 1176005 : original_reg = allocno_emit_reg (allocno);
628 1176005 : if (parent_allocno == NULL
629 1176005 : || (REGNO (allocno_emit_reg (parent_allocno))
630 1176005 : == REGNO (original_reg)))
631 : {
632 1176005 : 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 1176005 : 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 204619 : bitmap_and_compl (local_allocno_bitmap,
644 204619 : ira_curr_loop_tree_node->all_allocnos,
645 204619 : ira_curr_loop_tree_node->border_allocnos);
646 8818901 : EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 : {
648 8614282 : allocno = ira_allocnos[i];
649 8614282 : regno = ALLOCNO_REGNO (allocno);
650 8614282 : if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 3699687 : continue;
652 4914595 : used_p = !bitmap_set_bit (used_regno_bitmap, regno);
653 4914595 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
654 4914595 : if (! used_p)
655 4912596 : continue;
656 1999 : bitmap_set_bit (renamed_regno_bitmap, regno);
657 1999 : 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 36077 : set_allocno_somewhere_renamed_p (void)
664 : {
665 36077 : unsigned int regno;
666 36077 : ira_allocno_t allocno;
667 36077 : ira_allocno_iterator ai;
668 :
669 11857422 : FOR_EACH_ALLOCNO (allocno, ai)
670 : {
671 11821345 : regno = ALLOCNO_REGNO (allocno);
672 11821345 : if (bitmap_bit_p (renamed_regno_bitmap, regno)
673 11821345 : && REGNO (allocno_emit_reg (allocno)) == regno)
674 2950 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
675 : }
676 36077 : }
677 :
678 : /* Return TRUE if move lists on all edges given in vector VEC are
679 : equal. */
680 : static bool
681 5555903 : eq_edge_move_lists_p (vec<edge, va_gc> *vec)
682 : {
683 5555903 : move_t list;
684 5555903 : int i;
685 :
686 5555903 : list = (move_t) EDGE_I (vec, 0)->aux;
687 8227760 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 2983958 : 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 5642120 : unify_moves (basic_block bb, bool start_p)
698 : {
699 5642120 : int i;
700 5642120 : edge e;
701 5642120 : move_t list;
702 5642120 : vec<edge, va_gc> *vec;
703 :
704 5642120 : vec = (start_p ? bb->preds : bb->succs);
705 5642120 : if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 : return;
707 5243802 : e = EDGE_I (vec, 0);
708 5243802 : list = (move_t) e->aux;
709 5243802 : if (! start_p && control_flow_insn_p (BB_END (bb)))
710 : return;
711 3121405 : e->aux = NULL;
712 4299351 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 : {
714 1177946 : e = EDGE_I (vec, i);
715 1177946 : free_move_list ((move_t) e->aux);
716 1177946 : e->aux = NULL;
717 : }
718 3121405 : if (start_p)
719 2610818 : at_bb_start[bb->index] = list;
720 : else
721 510587 : 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 2259701 : traverse_moves (move_t move)
746 : {
747 2259701 : int i;
748 :
749 2259701 : if (move->visited_p)
750 : return;
751 2185699 : move->visited_p = true;
752 2259701 : for (i = move->deps_num - 1; i >= 0; i--)
753 74002 : traverse_moves (move->deps[i]);
754 2185699 : 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 388035 : modify_move_list (move_t list)
763 : {
764 388035 : int i, n, nregs, hard_regno;
765 388035 : ira_allocno_t to, from;
766 388035 : move_t move, new_move, set_move, first, last;
767 :
768 388035 : if (list == NULL)
769 : return NULL;
770 : /* Create move deps. */
771 388035 : curr_tick++;
772 2573734 : for (move = list; move != NULL; move = move->next)
773 : {
774 2185699 : to = move->to;
775 2185699 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
776 104217 : continue;
777 2081482 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
778 4176174 : for (i = 0; i < nregs; i++)
779 : {
780 2094692 : hard_regno_last_set[hard_regno + i] = move;
781 2094692 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
782 : }
783 : }
784 2573734 : for (move = list; move != NULL; move = move->next)
785 : {
786 2185699 : from = move->from;
787 2185699 : to = move->to;
788 2185699 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
789 : {
790 2038590 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
791 4089095 : for (n = i = 0; i < nregs; i++)
792 2050505 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
793 1914225 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
794 1914225 : != ALLOCNO_REGNO (from)))
795 74002 : n++;
796 2038590 : move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
797 4089095 : for (n = i = 0; i < nregs; i++)
798 2050505 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
799 1914225 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
800 1914225 : != ALLOCNO_REGNO (from)))
801 74002 : move->deps[n++] = hard_regno_last_set[hard_regno + i];
802 2038590 : move->deps_num = n;
803 : }
804 : }
805 : /* Topological sorting: */
806 388035 : move_vec.truncate (0);
807 2961769 : for (move = list; move != NULL; move = move->next)
808 2185699 : traverse_moves (move);
809 388035 : last = NULL;
810 2961769 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
811 : {
812 2185699 : move = move_vec[i];
813 2185699 : move->next = NULL;
814 2185699 : if (last != NULL)
815 1797664 : last->next = move;
816 2185699 : last = move;
817 : }
818 388035 : first = move_vec.last ();
819 : /* Removing cycles: */
820 388035 : curr_tick++;
821 388035 : move_vec.truncate (0);
822 2961769 : for (move = first; move != NULL; move = move->next)
823 : {
824 2185699 : from = move->from;
825 2185699 : to = move->to;
826 2185699 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
827 : {
828 2038590 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
829 4089095 : for (i = 0; i < nregs; i++)
830 2050505 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
831 5523 : && ALLOCNO_HARD_REGNO
832 : (hard_regno_last_set[hard_regno + i]->to) >= 0)
833 : {
834 5523 : int n, j;
835 5523 : ira_allocno_t new_allocno;
836 :
837 5523 : 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 5523 : new_allocno
843 5523 : = create_new_allocno (ALLOCNO_REGNO (set_move->to),
844 : ALLOCNO_LOOP_TREE_NODE (set_move->to));
845 5523 : ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
846 5523 : ira_set_allocno_class (new_allocno,
847 5523 : ALLOCNO_CLASS (set_move->to));
848 5523 : ira_create_allocno_objects (new_allocno);
849 5523 : ALLOCNO_ASSIGNED_P (new_allocno) = true;
850 5523 : ALLOCNO_HARD_REGNO (new_allocno) = -1;
851 5523 : ALLOCNO_EMIT_DATA (new_allocno)->reg
852 5523 : = 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 5523 : n = ALLOCNO_NUM_OBJECTS (new_allocno);
858 5523 : gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
859 11046 : for (j = 0; j < n; j++)
860 : {
861 5523 : ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
862 :
863 5523 : OBJECT_MIN (new_obj) = 0;
864 5523 : OBJECT_MAX (new_obj) = ira_objects_num - 1;
865 : }
866 :
867 5523 : new_move = create_move (set_move->to, new_allocno);
868 5523 : set_move->to = new_allocno;
869 5523 : move_vec.safe_push (new_move);
870 5523 : ira_move_loops_num++;
871 5523 : 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 2185699 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
879 104217 : continue;
880 2081482 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
881 4176174 : for (i = 0; i < nregs; i++)
882 : {
883 2094692 : hard_regno_last_set[hard_regno + i] = move;
884 2094692 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
885 : }
886 : }
887 781593 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
888 : {
889 5523 : move = move_vec[i];
890 5523 : move->next = NULL;
891 5523 : last->next = move;
892 5523 : 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 388035 : emit_move_list (move_t list, int freq)
901 : {
902 388035 : rtx to, from, dest;
903 388035 : int to_regno, from_regno, cost, regno;
904 388035 : rtx_insn *result, *insn;
905 388035 : rtx set;
906 388035 : machine_mode mode;
907 388035 : enum reg_class aclass;
908 :
909 388035 : grow_reg_equivs ();
910 388035 : start_sequence ();
911 2967292 : for (; list != NULL; list = list->next)
912 : {
913 2191222 : start_sequence ();
914 2191222 : to = allocno_emit_reg (list->to);
915 2191222 : to_regno = REGNO (to);
916 2191222 : from = allocno_emit_reg (list->from);
917 2191222 : from_regno = REGNO (from);
918 2191222 : emit_move_insn (to, from);
919 2191222 : list->insn = end_sequence ();
920 4382444 : 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 2191222 : 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 2191222 : if ((set = single_set (insn)) != NULL_RTX)
932 : {
933 2191222 : dest = SET_DEST (set);
934 2191222 : if (GET_CODE (dest) == SUBREG)
935 0 : dest = SUBREG_REG (dest);
936 2191222 : ira_assert (REG_P (dest));
937 2191222 : regno = REGNO (dest);
938 2191222 : if (regno >= ira_reg_equiv_len
939 2191222 : || (ira_reg_equiv[regno].invariant == NULL_RTX
940 2191203 : && ira_reg_equiv[regno].constant == NULL_RTX))
941 2191149 : continue; /* regno has no equivalence. */
942 73 : ira_assert ((int) reg_equivs->length () > regno);
943 73 : reg_equiv_init (regno)
944 146 : = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
945 : }
946 : }
947 2191222 : if (ira_use_lra_p)
948 2191222 : ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
949 2191222 : emit_insn (list->insn);
950 2191222 : mode = ALLOCNO_MODE (list->to);
951 2191222 : aclass = ALLOCNO_CLASS (list->to);
952 2191222 : cost = 0;
953 2191222 : if (ALLOCNO_HARD_REGNO (list->to) < 0)
954 : {
955 109740 : if (ALLOCNO_HARD_REGNO (list->from) >= 0)
956 : {
957 109652 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
958 109652 : ira_store_cost += cost;
959 : }
960 : }
961 2081482 : else if (ALLOCNO_HARD_REGNO (list->from) < 0)
962 : {
963 152544 : if (ALLOCNO_HARD_REGNO (list->to) >= 0)
964 : {
965 152544 : cost = ira_memory_move_cost[mode][aclass][1] * freq;
966 152544 : ira_load_cost += cost;
967 : }
968 : }
969 : else
970 : {
971 1928938 : ira_init_register_move_cost_if_necessary (mode);
972 1928938 : cost = ira_register_move_cost[mode][aclass][aclass] * freq;
973 1928938 : ira_shuffle_cost += cost;
974 : }
975 2191222 : ira_overall_cost += cost;
976 : }
977 388035 : result = end_sequence ();
978 388035 : return result;
979 : }
980 :
981 : /* Generate RTX move insns from move lists attached to basic blocks
982 : and edges. */
983 : static void
984 36077 : emit_moves (void)
985 : {
986 36077 : basic_block bb;
987 36077 : edge_iterator ei;
988 36077 : edge e;
989 36077 : rtx_insn *insns, *tmp, *next;
990 :
991 2857137 : FOR_EACH_BB_FN (bb, cfun)
992 : {
993 2821060 : if (at_bb_start[bb->index] != NULL)
994 : {
995 141320 : at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
996 141320 : insns
997 141320 : = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
998 141320 : tmp = BB_HEAD (bb);
999 141320 : if (LABEL_P (tmp))
1000 25269 : tmp = NEXT_INSN (tmp);
1001 141320 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1002 141320 : 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 141320 : next = tmp;
1006 329340 : while (next && !NONDEBUG_INSN_P (next))
1007 188020 : next = NEXT_INSN (next);
1008 141320 : if (next)
1009 141320 : set_insn_locations (insns, INSN_LOCATION (next));
1010 141320 : if (tmp == BB_HEAD (bb))
1011 0 : emit_insn_before (insns, tmp);
1012 141320 : else if (tmp)
1013 141320 : emit_insn_after (insns, PREV_INSN (tmp));
1014 : else
1015 0 : emit_insn_after (insns, get_last_insn ());
1016 : }
1017 :
1018 2821060 : if (at_bb_end[bb->index] != NULL)
1019 : {
1020 107989 : at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1021 107989 : insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1022 107989 : ira_assert (! control_flow_insn_p (BB_END (bb)));
1023 107989 : emit_insn_after (insns, BB_END (bb));
1024 : }
1025 :
1026 7123222 : FOR_EACH_EDGE (e, ei, bb->succs)
1027 : {
1028 4302162 : if (e->aux == NULL)
1029 4163436 : continue;
1030 138726 : ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1031 : || ! EDGE_CRITICAL_P (e));
1032 138726 : e->aux = modify_move_list ((move_t) e->aux);
1033 138726 : insert_insn_on_edge
1034 277371 : (emit_move_list ((move_t) e->aux,
1035 277371 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1036 : e);
1037 138726 : if (e->src->next_bb != e->dest)
1038 94641 : ira_additional_jumps_num++;
1039 : }
1040 : }
1041 36077 : }
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 4382444 : update_costs (ira_allocno_t a, bool read_p, int freq)
1048 : {
1049 10462699 : ira_loop_tree_node_t parent;
1050 :
1051 10462699 : for (;;)
1052 : {
1053 10462699 : ALLOCNO_NREFS (a)++;
1054 10462699 : ALLOCNO_FREQ (a) += freq;
1055 10462699 : ALLOCNO_MEMORY_COST (a)
1056 20925398 : += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1057 10462699 : [read_p ? 1 : 0] * freq);
1058 10462699 : if (ALLOCNO_CAP (a) != NULL)
1059 : a = ALLOCNO_CAP (a);
1060 8843233 : else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1061 8843233 : || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1062 : break;
1063 : }
1064 4382444 : }
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 9944282 : add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1072 : bitmap live_through, int freq)
1073 : {
1074 9944282 : int start, n;
1075 9944282 : unsigned int regno;
1076 9944282 : move_t move;
1077 9944282 : ira_allocno_t a;
1078 9944282 : ira_copy_t cp;
1079 9944282 : live_range_t r;
1080 9944282 : bitmap_iterator bi;
1081 9944282 : HARD_REG_SET hard_regs_live;
1082 :
1083 9944282 : if (list == NULL)
1084 9556247 : return;
1085 388035 : n = 0;
1086 6941369 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1087 6553334 : n++;
1088 388035 : 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 388035 : ira_max_point++;
1092 388035 : start = ira_max_point;
1093 2579257 : for (move = list; move != NULL; move = move->next)
1094 : {
1095 2191222 : ira_allocno_t from = move->from;
1096 2191222 : ira_allocno_t to = move->to;
1097 2191222 : int nr, i;
1098 :
1099 2191222 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1100 2191222 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1101 :
1102 2191222 : nr = ALLOCNO_NUM_OBJECTS (to);
1103 4396991 : for (i = 0; i < nr; i++)
1104 : {
1105 2205769 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1106 2205769 : if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1107 : {
1108 5523 : 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 5523 : ira_allocate_object_conflicts (to_obj, n);
1112 : }
1113 : }
1114 2191222 : ior_hard_reg_conflicts (from, hard_regs_live);
1115 2191222 : ior_hard_reg_conflicts (to, hard_regs_live);
1116 :
1117 2191222 : update_costs (from, true, freq);
1118 2191222 : update_costs (to, false, freq);
1119 2191222 : cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1120 2191222 : 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 2191222 : nr = ALLOCNO_NUM_OBJECTS (from);
1128 4396991 : for (i = 0; i < nr; i++)
1129 : {
1130 2205769 : ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1131 2205769 : r = OBJECT_LIVE_RANGES (from_obj);
1132 2205769 : if (r == NULL || r->finish >= 0)
1133 : {
1134 2200246 : ira_add_live_range_to_object (from_obj, start, ira_max_point);
1135 2200246 : 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 5523 : r->finish = ira_max_point;
1144 5523 : 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 2191222 : ira_max_point++;
1152 2191222 : nr = ALLOCNO_NUM_OBJECTS (to);
1153 4396991 : for (i = 0; i < nr; i++)
1154 : {
1155 2205769 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1156 2205769 : ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1157 : }
1158 2191222 : ira_max_point++;
1159 : }
1160 2579257 : for (move = list; move != NULL; move = move->next)
1161 : {
1162 2191222 : int nr, i;
1163 2191222 : nr = ALLOCNO_NUM_OBJECTS (move->to);
1164 4396991 : for (i = 0; i < nr; i++)
1165 : {
1166 2205769 : ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1167 2205769 : r = OBJECT_LIVE_RANGES (to_obj);
1168 2205769 : if (r->finish < 0)
1169 : {
1170 2200246 : r->finish = ira_max_point - 1;
1171 2200246 : 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 4755670 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1180 : {
1181 4367635 : ira_allocno_t to;
1182 4367635 : int nr, i;
1183 :
1184 4367635 : a = node->regno_allocno_map[regno];
1185 4367635 : if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1186 8014 : a = to;
1187 4367635 : nr = ALLOCNO_NUM_OBJECTS (a);
1188 8840075 : for (i = 0; i < nr; i++)
1189 : {
1190 4472440 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
1191 4472440 : ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1192 : }
1193 4367635 : 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 36077 : add_ranges_and_copies (void)
1207 : {
1208 36077 : basic_block bb;
1209 36077 : edge_iterator ei;
1210 36077 : edge e;
1211 36077 : ira_loop_tree_node_t node;
1212 36077 : bitmap live_through;
1213 :
1214 36077 : live_through = ira_allocate_bitmap ();
1215 2857137 : 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 2821060 : node = IRA_BB_NODE (bb)->parent;
1221 2821060 : bitmap_copy (live_through, df_get_live_in (bb));
1222 2821060 : add_range_and_copies_from_move_list
1223 2821060 : (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1224 2821060 : bitmap_copy (live_through, df_get_live_out (bb));
1225 2821060 : add_range_and_copies_from_move_list
1226 2821060 : (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1227 7123222 : FOR_EACH_EDGE (e, ei, bb->succs)
1228 : {
1229 4302162 : bitmap_and (live_through,
1230 4302162 : df_get_live_in (e->dest), df_get_live_out (bb));
1231 4302162 : add_range_and_copies_from_move_list
1232 8602416 : ((move_t) e->aux, node, live_through,
1233 12904578 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1234 : }
1235 : }
1236 36077 : ira_free_bitmap (live_through);
1237 36077 : }
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 1515921 : ira_emit (bool loops_p)
1244 : {
1245 1515921 : basic_block bb;
1246 1515921 : rtx_insn *insn;
1247 1515921 : edge_iterator ei;
1248 1515921 : edge e;
1249 1515921 : ira_allocno_t a;
1250 1515921 : ira_allocno_iterator ai;
1251 1515921 : size_t sz;
1252 :
1253 38972296 : FOR_EACH_ALLOCNO (a, ai)
1254 37456375 : ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1255 1515921 : if (! loops_p)
1256 1479844 : return;
1257 36077 : sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1258 36077 : at_bb_start = (move_t *) ira_allocate (sz);
1259 36077 : memset (at_bb_start, 0, sz);
1260 36077 : at_bb_end = (move_t *) ira_allocate (sz);
1261 36077 : memset (at_bb_end, 0, sz);
1262 36077 : local_allocno_bitmap = ira_allocate_bitmap ();
1263 36077 : used_regno_bitmap = ira_allocate_bitmap ();
1264 36077 : renamed_regno_bitmap = ira_allocate_bitmap ();
1265 36077 : max_regno_before_changing = max_reg_num ();
1266 36077 : ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1267 36077 : set_allocno_somewhere_renamed_p ();
1268 36077 : ira_free_bitmap (used_regno_bitmap);
1269 36077 : ira_free_bitmap (renamed_regno_bitmap);
1270 36077 : ira_free_bitmap (local_allocno_bitmap);
1271 36077 : setup_entered_from_non_parent_p ();
1272 2857137 : FOR_EACH_BB_FN (bb, cfun)
1273 : {
1274 2821060 : at_bb_start[bb->index] = NULL;
1275 2821060 : at_bb_end[bb->index] = NULL;
1276 7123222 : FOR_EACH_EDGE (e, ei, bb->succs)
1277 4302162 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1278 4263534 : generate_edge_moves (e);
1279 : }
1280 36077 : memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1281 36077 : curr_tick = 0;
1282 2857137 : FOR_EACH_BB_FN (bb, cfun)
1283 2821060 : unify_moves (bb, true);
1284 2857137 : FOR_EACH_BB_FN (bb, cfun)
1285 2821060 : unify_moves (bb, false);
1286 36077 : move_vec.create (ira_allocnos_num);
1287 36077 : emit_moves ();
1288 36077 : add_ranges_and_copies ();
1289 : /* Clean up: */
1290 2857137 : FOR_EACH_BB_FN (bb, cfun)
1291 : {
1292 2821060 : free_move_list (at_bb_start[bb->index]);
1293 2821060 : free_move_list (at_bb_end[bb->index]);
1294 7123222 : FOR_EACH_EDGE (e, ei, bb->succs)
1295 : {
1296 4302162 : free_move_list ((move_t) e->aux);
1297 4302162 : e->aux = NULL;
1298 : }
1299 : }
1300 36077 : move_vec.release ();
1301 36077 : 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 2962210 : FOR_EACH_BB_FN (bb, cfun)
1307 38396146 : FOR_BB_INSNS_REVERSE (bb, insn)
1308 35470013 : if (INSN_P (insn))
1309 30134809 : recog_memoized (insn);
1310 36077 : ira_free (at_bb_end);
1311 36077 : ira_free (at_bb_start);
1312 : }
|
