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 1471362 : ira_initiate_emit_data (void)
102 : {
103 1471362 : ira_allocno_t a;
104 1471362 : ira_allocno_iterator ai;
105 :
106 1471362 : ira_allocno_emit_data
107 1471362 : = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 : * sizeof (struct ira_emit_data));
109 1471362 : memset (ira_allocno_emit_data, 0,
110 1471362 : ira_allocnos_num * sizeof (struct ira_emit_data));
111 37930378 : FOR_EACH_ALLOCNO (a, ai)
112 36459016 : ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
113 1471362 : new_allocno_emit_data_vec.create (50);
114 :
115 1471362 : }
116 :
117 : /* Free the emit data. */
118 : void
119 1471362 : ira_finish_emit_data (void)
120 : {
121 1471362 : void_p p;
122 1471362 : ira_allocno_t a;
123 1471362 : ira_allocno_iterator ai;
124 :
125 1471362 : ira_free (ira_allocno_emit_data);
126 37935239 : FOR_EACH_ALLOCNO (a, ai)
127 36463877 : ALLOCNO_ADD_DATA (a) = NULL;
128 1476223 : for (;new_allocno_emit_data_vec.length () != 0;)
129 : {
130 4861 : p = new_allocno_emit_data_vec.pop ();
131 4861 : ira_free (p);
132 : }
133 1471362 : new_allocno_emit_data_vec.release ();
134 1471362 : }
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 4861 : create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140 : {
141 4861 : ira_allocno_t a;
142 :
143 4861 : a = ira_create_allocno (regno, false, loop_tree_node);
144 4861 : ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 4861 : memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
146 4861 : new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
147 4861 : 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 2234062 : create_move (ira_allocno_t to, ira_allocno_t from)
189 : {
190 2234062 : move_t move;
191 :
192 2234062 : move = (move_t) ira_allocate (sizeof (struct move));
193 2234062 : move->deps = NULL;
194 2234062 : move->deps_num = 0;
195 2234062 : move->to = to;
196 2234062 : move->from = from;
197 2234062 : move->next = NULL;
198 2234062 : move->insn = NULL;
199 2234062 : move->visited_p = false;
200 2234062 : return move;
201 : }
202 :
203 : /* Free memory for MOVE and its dependencies. */
204 : static void
205 2234062 : free_move (move_t move)
206 : {
207 2234062 : if (move->deps != NULL)
208 2047025 : ira_free (move->deps);
209 2234062 : ira_free (move);
210 2234062 : }
211 :
212 : /* Free memory for list of the moves given by its HEAD. */
213 : static void
214 10863366 : free_move_list (move_t head)
215 : {
216 10863366 : move_t next;
217 :
218 13097428 : for (; head != NULL; head = next)
219 : {
220 2234062 : next = head->next;
221 2234062 : 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 2913165 : eq_move_lists_p (move_t list1, move_t list2)
229 : {
230 3043109 : for (; list1 != NULL && list2 != NULL;
231 129944 : list1 = list1->next, list2 = list2->next)
232 132728 : if (list1->from != list2->from || list1->to != list2->to)
233 : return false;
234 2910381 : 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 208563611 : change_regs (rtx *loc)
261 : {
262 208563611 : int i, regno, result = false;
263 208563611 : const char *fmt;
264 208563611 : enum rtx_code code;
265 208563611 : rtx reg;
266 :
267 208563611 : if (*loc == NULL_RTX)
268 : return false;
269 181319071 : code = GET_CODE (*loc);
270 181319071 : if (code == REG)
271 : {
272 45155971 : regno = REGNO (*loc);
273 45155971 : if (regno < FIRST_PSEUDO_REGISTER)
274 : return false;
275 24626448 : if (regno >= max_regno_before_changing)
276 : /* It is a shared register which was changed already. */
277 : return false;
278 24626336 : if (ira_curr_regno_allocno_map[regno] == NULL)
279 : return false;
280 24618939 : reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
281 24618939 : if (reg == *loc)
282 : return false;
283 3249536 : *loc = reg;
284 3249536 : return true;
285 : }
286 :
287 136163100 : fmt = GET_RTX_FORMAT (code);
288 496541676 : for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 : {
290 360378576 : if (fmt[i] == 'e')
291 185488418 : result = change_regs (&XEXP (*loc, i)) || result;
292 185040984 : else if (fmt[i] == 'E')
293 : {
294 3190358 : int j;
295 :
296 10053130 : for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 7411917 : result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 : }
299 : }
300 136163100 : return result;
301 : }
302 :
303 : static bool
304 26363247 : change_regs_in_insn (rtx_insn **insn_ptr)
305 : {
306 26363247 : rtx rtx = *insn_ptr;
307 26363247 : bool result = change_regs (&rtx);
308 26363247 : *insn_ptr = as_a <rtx_insn *> (rtx);
309 26363247 : 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 2229201 : add_to_edge_list (edge e, move_t move, bool head_p)
316 : {
317 2229201 : move_t last;
318 :
319 0 : if (head_p || e->aux == NULL)
320 : {
321 2229201 : 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 1239993 : ira_create_new_reg (rtx original_reg)
337 : {
338 1239993 : rtx new_reg;
339 :
340 1239993 : new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 1239993 : ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 1239993 : REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 1239993 : REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 1239993 : REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 1239993 : 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 1239993 : ira_expand_reg_equiv ();
349 1239993 : return new_reg;
350 : }
351 :
352 : /* Return TRUE if loop given by SUBNODE inside the loop given by
353 : NODE. */
354 : static bool
355 8026852 : subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356 : {
357 25303274 : for (; subnode != NULL; subnode = subnode->parent)
358 19083730 : 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 1165348 : set_allocno_reg (ira_allocno_t allocno, rtx reg)
367 : {
368 1165348 : int regno;
369 1165348 : ira_allocno_t a;
370 1165348 : ira_loop_tree_node_t node;
371 :
372 1165348 : node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 1165348 : for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 9192200 : a != NULL;
375 8026852 : a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 16053704 : if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
377 1807308 : ALLOCNO_EMIT_DATA (a)->reg = reg;
378 1167984 : for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
379 2636 : ALLOCNO_EMIT_DATA (a)->reg = reg;
380 : regno = ALLOCNO_REGNO (allocno);
381 : for (a = allocno;;)
382 : {
383 2621306 : if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 : {
385 2319501 : node = node->parent;
386 2319501 : if (node == NULL)
387 : break;
388 1700795 : a = node->regno_allocno_map[regno];
389 : }
390 2002600 : if (a == NULL)
391 299275 : continue;
392 1703325 : if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
393 : break;
394 1156683 : ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
395 : }
396 1165348 : }
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 203852 : entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403 : {
404 203852 : ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 203852 : edge e;
406 203852 : edge_iterator ei;
407 :
408 203852 : for (bb_node = loop_node->children;
409 3130681 : bb_node != NULL;
410 2926829 : bb_node = bb_node->next)
411 2927412 : if (bb_node->bb != NULL)
412 : {
413 6965991 : FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
414 4207414 : if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
415 4207414 : && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 : {
417 492481 : for (parent = src_loop_node->parent;
418 639393 : parent != NULL;
419 146912 : parent = parent->parent)
420 448772 : if (parent == loop_node)
421 : break;
422 492481 : if (parent != NULL)
423 : /* That is an exit from a nested loop -- skip it. */
424 301860 : continue;
425 190621 : for (parent = loop_node->parent;
426 191620 : parent != NULL;
427 999 : parent = parent->parent)
428 191037 : 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 35600 : setup_entered_from_non_parent_p (void)
440 : {
441 35600 : unsigned int i;
442 35600 : loop_p loop;
443 :
444 35600 : ira_assert (current_loops != NULL);
445 293072 : FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
446 221872 : if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 203852 : ira_loop_nodes[i].entered_from_non_parent_p
448 203852 : = entered_from_non_parent_p (&ira_loop_nodes[i]);
449 35600 : }
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 126001 : store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
458 : {
459 126001 : int regno, orig_regno;
460 126001 : ira_allocno_t a;
461 126001 : ira_loop_tree_node_t node;
462 :
463 126001 : ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 : && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 126001 : orig_regno = ALLOCNO_REGNO (src_allocno);
466 126001 : regno = REGNO (allocno_emit_reg (dest_allocno));
467 126001 : for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 179766 : node != NULL;
469 53765 : node = node->parent)
470 : {
471 179766 : a = node->regno_allocno_map[orig_regno];
472 179766 : ira_assert (a != NULL);
473 179766 : if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
474 : /* We achieved the destination and everything is ok. */
475 : return true;
476 154197 : else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 : return false;
478 53860 : 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 4172619 : generate_edge_moves (edge e)
498 : {
499 4172619 : ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 4172619 : unsigned int regno;
501 4172619 : bitmap_iterator bi;
502 4172619 : ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 4172619 : move_t move;
504 4172619 : bitmap regs_live_in_dest, regs_live_out_src;
505 :
506 4172619 : src_loop_node = IRA_BB_NODE (e->src)->parent;
507 4172619 : dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 4172619 : e->aux = NULL;
509 4172619 : if (src_loop_node == dest_loop_node)
510 3679922 : return;
511 492697 : src_map = src_loop_node->regno_allocno_map;
512 492697 : dest_map = dest_loop_node->regno_allocno_map;
513 492697 : regs_live_in_dest = df_get_live_in (e->dest);
514 492697 : regs_live_out_src = df_get_live_out (e->src);
515 7335957 : EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
516 : FIRST_PSEUDO_REGISTER, regno, bi)
517 6843260 : if (bitmap_bit_p (regs_live_out_src, regno))
518 : {
519 6843260 : src_allocno = src_map[regno];
520 6843260 : dest_allocno = dest_map[regno];
521 6843260 : if (REGNO (allocno_emit_reg (src_allocno))
522 6843260 : == REGNO (allocno_emit_reg (dest_allocno)))
523 4588490 : 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 2280339 : if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 126090 : && ALLOCNO_HARD_REGNO (src_allocno) >= 0
530 2380771 : && store_can_be_removed_p (src_allocno, dest_allocno))
531 : {
532 25569 : ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 25569 : ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
534 25569 : 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 25569 : continue;
539 : }
540 2229201 : move = create_move (dest_allocno, src_allocno);
541 2229201 : 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 2963143 : change_loop (ira_loop_tree_node_t node)
562 : {
563 2963143 : bitmap_iterator bi;
564 2963143 : unsigned int i;
565 2963143 : int regno;
566 2963143 : bool used_p;
567 2963143 : ira_allocno_t allocno, parent_allocno, *map;
568 2963143 : rtx_insn *insn;
569 2963143 : rtx original_reg;
570 2963143 : enum reg_class aclass, pclass;
571 2963143 : ira_loop_tree_node_t parent;
572 :
573 2963143 : if (node != ira_loop_tree_root)
574 : {
575 2927543 : ira_assert (current_loops != NULL);
576 :
577 2927543 : if (node->bb != NULL)
578 : {
579 34210311 : FOR_BB_INSNS (node->bb, insn)
580 31451020 : if (INSN_P (insn) && change_regs_in_insn (&insn))
581 : {
582 2242324 : df_insn_rescan (insn);
583 2242324 : df_notes_rescan (insn);
584 : }
585 2759291 : return;
586 : }
587 :
588 168252 : 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 168252 : parent = ira_curr_loop_tree_node->parent;
594 168252 : map = parent->regno_allocno_map;
595 3311800 : EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 : 0, i, bi)
597 : {
598 3143548 : allocno = ira_allocnos[i];
599 3143548 : regno = ALLOCNO_REGNO (allocno);
600 3143548 : aclass = ALLOCNO_CLASS (allocno);
601 3143548 : pclass = ira_pressure_class_translate[aclass];
602 3143548 : parent_allocno = map[regno];
603 3143548 : 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 5123537 : if (parent_allocno != NULL
611 3143548 : && (ALLOCNO_HARD_REGNO (allocno)
612 3143548 : == ALLOCNO_HARD_REGNO (parent_allocno))
613 6104239 : && (ALLOCNO_HARD_REGNO (allocno) < 0
614 1154715 : || (parent->reg_pressure[pclass] + 1
615 1154715 : <= ira_class_hard_regs_num[pclass])
616 1071293 : || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 1071293 : [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 1071293 : || ira_equiv_no_lvalue_p (regno)
623 988683 : || (pic_offset_table_rtx != NULL
624 98528 : && (ALLOCNO_REGNO (allocno)
625 98528 : == (int) REGNO (pic_offset_table_rtx)))))
626 1979989 : continue;
627 1163559 : original_reg = allocno_emit_reg (allocno);
628 1163559 : if (parent_allocno == NULL
629 1163559 : || (REGNO (allocno_emit_reg (parent_allocno))
630 1163559 : == REGNO (original_reg)))
631 : {
632 1163559 : 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 1163559 : 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 203852 : bitmap_and_compl (local_allocno_bitmap,
644 203852 : ira_curr_loop_tree_node->all_allocnos,
645 203852 : ira_curr_loop_tree_node->border_allocnos);
646 8742402 : EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 : {
648 8538550 : allocno = ira_allocnos[i];
649 8538550 : regno = ALLOCNO_REGNO (allocno);
650 8538550 : if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 3704601 : continue;
652 4833949 : used_p = !bitmap_set_bit (used_regno_bitmap, regno);
653 4833949 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
654 4833949 : if (! used_p)
655 4832160 : continue;
656 1789 : bitmap_set_bit (renamed_regno_bitmap, regno);
657 1789 : 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 35600 : set_allocno_somewhere_renamed_p (void)
664 : {
665 35600 : unsigned int regno;
666 35600 : ira_allocno_t allocno;
667 35600 : ira_allocno_iterator ai;
668 :
669 11717698 : FOR_EACH_ALLOCNO (allocno, ai)
670 : {
671 11682098 : regno = ALLOCNO_REGNO (allocno);
672 11682098 : if (bitmap_bit_p (renamed_regno_bitmap, regno)
673 11682098 : && REGNO (allocno_emit_reg (allocno)) == regno)
674 2734 : ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
675 : }
676 35600 : }
677 :
678 : /* Return TRUE if move lists on all edges given in vector VEC are
679 : equal. */
680 : static bool
681 5438067 : eq_edge_move_lists_p (vec<edge, va_gc> *vec)
682 : {
683 5438067 : move_t list;
684 5438067 : int i;
685 :
686 5438067 : list = (move_t) EDGE_I (vec, 0)->aux;
687 8033904 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 2913165 : 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 5518582 : unify_moves (basic_block bb, bool start_p)
698 : {
699 5518582 : int i;
700 5518582 : edge e;
701 5518582 : move_t list;
702 5518582 : vec<edge, va_gc> *vec;
703 :
704 5518582 : vec = (start_p ? bb->preds : bb->succs);
705 5518582 : if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 : return;
707 5120739 : e = EDGE_I (vec, 0);
708 5120739 : list = (move_t) e->aux;
709 5120739 : if (! start_p && control_flow_insn_p (BB_END (bb)))
710 : return;
711 3048046 : e->aux = NULL;
712 4181802 : for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 : {
714 1133756 : e = EDGE_I (vec, i);
715 1133756 : free_move_list ((move_t) e->aux);
716 1133756 : e->aux = NULL;
717 : }
718 3048046 : if (start_p)
719 2547748 : at_bb_start[bb->index] = list;
720 : else
721 500298 : at_bb_end[bb->index] = list;
722 : }
723 :
724 : /* Last move (in move sequence being processed) setting up the
725 : corresponding hard register. */
726 : static move_t hard_regno_last_set[FIRST_PSEUDO_REGISTER];
727 :
728 : /* If the element value is equal to CURR_TICK then the corresponding
729 : element in `hard_regno_last_set' is defined and correct. */
730 : static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
731 :
732 : /* Last move (in move sequence being processed) setting up the
733 : corresponding allocno. */
734 : static move_t *allocno_last_set;
735 :
736 : /* If the element value is equal to CURR_TICK then the corresponding
737 : element in . `allocno_last_set' is defined and correct. */
738 : static int *allocno_last_set_check;
739 :
740 : /* Definition of vector of moves. */
741 :
742 : /* This vec contains moves sorted topologically (depth-first) on their
743 : dependency graph. */
744 : static vec<move_t> move_vec;
745 :
746 : /* The variable value is used to check correctness of values of
747 : elements of arrays `hard_regno_last_set' and
748 : `allocno_last_set_check'. */
749 : static int curr_tick;
750 :
751 : /* This recursive function traverses dependencies of MOVE and produces
752 : topological sorting (in depth-first order). */
753 : static void
754 2267940 : traverse_moves (move_t move)
755 : {
756 2267940 : int i;
757 :
758 2267940 : if (move->visited_p)
759 : return;
760 2194417 : move->visited_p = true;
761 2267940 : for (i = move->deps_num - 1; i >= 0; i--)
762 73523 : traverse_moves (move->deps[i]);
763 2194417 : move_vec.safe_push (move);
764 : }
765 :
766 : /* Remove unnecessary moves in the LIST, makes topological sorting,
767 : and removes cycles on hard reg dependencies by introducing new
768 : allocnos assigned to memory and additional moves. It returns the
769 : result move list. */
770 : static move_t
771 390624 : modify_move_list (move_t list)
772 : {
773 390624 : int i, n, nregs, hard_regno;
774 390624 : ira_allocno_t to, from;
775 390624 : move_t move, new_move, set_move, first, last;
776 :
777 390624 : if (list == NULL)
778 : return NULL;
779 : /* Create move deps. */
780 390624 : curr_tick++;
781 2585041 : for (move = list; move != NULL; move = move->next)
782 : {
783 2194417 : to = move->to;
784 2194417 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
785 99826 : continue;
786 2094591 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
787 4203540 : for (i = 0; i < nregs; i++)
788 : {
789 2108949 : hard_regno_last_set[hard_regno + i] = move;
790 2108949 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
791 : }
792 : }
793 2585041 : for (move = list; move != NULL; move = move->next)
794 : {
795 2194417 : from = move->from;
796 2194417 : to = move->to;
797 2194417 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
798 : {
799 2047025 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
800 4106804 : for (n = i = 0; i < nregs; i++)
801 2059779 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
802 1935375 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
803 1935375 : != ALLOCNO_REGNO (from)))
804 73523 : n++;
805 2047025 : move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
806 4106804 : for (n = i = 0; i < nregs; i++)
807 2059779 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
808 1935375 : && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
809 1935375 : != ALLOCNO_REGNO (from)))
810 73523 : move->deps[n++] = hard_regno_last_set[hard_regno + i];
811 2047025 : move->deps_num = n;
812 : }
813 : }
814 : /* Topological sorting: */
815 390624 : move_vec.truncate (0);
816 2975665 : for (move = list; move != NULL; move = move->next)
817 2194417 : traverse_moves (move);
818 390624 : last = NULL;
819 2975665 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
820 : {
821 2194417 : move = move_vec[i];
822 2194417 : move->next = NULL;
823 2194417 : if (last != NULL)
824 1803793 : last->next = move;
825 2194417 : last = move;
826 : }
827 390624 : first = move_vec.last ();
828 : /* Removing cycles: */
829 390624 : curr_tick++;
830 390624 : move_vec.truncate (0);
831 2585041 : for (move = first; move != NULL; move = move->next)
832 : {
833 2194417 : from = move->from;
834 2194417 : to = move->to;
835 2194417 : if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
836 : {
837 2047025 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
838 4106804 : for (i = 0; i < nregs; i++)
839 2059779 : if (hard_regno_last_set_check[hard_regno + i] == curr_tick
840 4861 : && ALLOCNO_HARD_REGNO
841 : (hard_regno_last_set[hard_regno + i]->to) >= 0)
842 : {
843 4861 : int n, j;
844 4861 : ira_allocno_t new_allocno;
845 :
846 4861 : set_move = hard_regno_last_set[hard_regno + i];
847 : /* It does not matter what loop_tree_node (of TO or
848 : FROM) to use for the new allocno because of
849 : subsequent IRA internal representation
850 : flattening. */
851 4861 : new_allocno
852 4861 : = create_new_allocno (ALLOCNO_REGNO (set_move->to),
853 : ALLOCNO_LOOP_TREE_NODE (set_move->to));
854 4861 : ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
855 4861 : ira_set_allocno_class (new_allocno,
856 4861 : ALLOCNO_CLASS (set_move->to));
857 4861 : ira_create_allocno_objects (new_allocno);
858 4861 : ALLOCNO_ASSIGNED_P (new_allocno) = true;
859 4861 : ALLOCNO_HARD_REGNO (new_allocno) = -1;
860 4861 : ALLOCNO_EMIT_DATA (new_allocno)->reg
861 4861 : = ira_create_new_reg (allocno_emit_reg (set_move->to));
862 :
863 : /* Make it possibly conflicting with all earlier
864 : created allocnos. Cases where temporary allocnos
865 : created to remove the cycles are quite rare. */
866 4861 : n = ALLOCNO_NUM_OBJECTS (new_allocno);
867 4861 : gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
868 9722 : for (j = 0; j < n; j++)
869 : {
870 4861 : ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
871 :
872 4861 : OBJECT_MIN (new_obj) = 0;
873 4861 : OBJECT_MAX (new_obj) = ira_objects_num - 1;
874 : }
875 :
876 4861 : new_move = create_move (set_move->to, new_allocno);
877 4861 : set_move->to = new_allocno;
878 4861 : move_vec.safe_push (new_move);
879 4861 : ira_move_loops_num++;
880 4861 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
881 0 : fprintf (ira_dump_file,
882 : " Creating temporary allocno a%dr%d\n",
883 : ALLOCNO_NUM (new_allocno),
884 0 : REGNO (allocno_emit_reg (new_allocno)));
885 : }
886 : }
887 2194417 : if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
888 99826 : continue;
889 2094591 : nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
890 4203540 : for (i = 0; i < nregs; i++)
891 : {
892 2108949 : hard_regno_last_set[hard_regno + i] = move;
893 2108949 : hard_regno_last_set_check[hard_regno + i] = curr_tick;
894 : }
895 : }
896 786109 : for (i = (int) move_vec.length () - 1; i >= 0; i--)
897 : {
898 4861 : move = move_vec[i];
899 4861 : move->next = NULL;
900 4861 : last->next = move;
901 4861 : last = move;
902 : }
903 : return first;
904 : }
905 :
906 : /* Generate RTX move insns from the move list LIST. This updates
907 : allocation cost using move execution frequency FREQ. */
908 : static rtx_insn *
909 390624 : emit_move_list (move_t list, int freq)
910 : {
911 390624 : rtx to, from, dest;
912 390624 : int to_regno, from_regno, cost, regno;
913 390624 : rtx_insn *result, *insn;
914 390624 : rtx set;
915 390624 : machine_mode mode;
916 390624 : enum reg_class aclass;
917 :
918 390624 : grow_reg_equivs ();
919 390624 : start_sequence ();
920 2980526 : for (; list != NULL; list = list->next)
921 : {
922 2199278 : start_sequence ();
923 2199278 : to = allocno_emit_reg (list->to);
924 2199278 : to_regno = REGNO (to);
925 2199278 : from = allocno_emit_reg (list->from);
926 2199278 : from_regno = REGNO (from);
927 2199278 : emit_move_insn (to, from);
928 2199278 : list->insn = end_sequence ();
929 4398556 : for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
930 : {
931 : /* The reload needs to have set up insn codes. If the
932 : reload sets up insn codes by itself, it may fail because
933 : insns will have hard registers instead of pseudos and
934 : there may be no machine insn with given hard
935 : registers. */
936 2199278 : recog_memoized (insn);
937 : /* Add insn to equiv init insn list if it is necessary.
938 : Otherwise reload will not remove this insn if it decides
939 : to use the equivalence. */
940 2199278 : if ((set = single_set (insn)) != NULL_RTX)
941 : {
942 2199278 : dest = SET_DEST (set);
943 2199278 : if (GET_CODE (dest) == SUBREG)
944 0 : dest = SUBREG_REG (dest);
945 2199278 : ira_assert (REG_P (dest));
946 2199278 : regno = REGNO (dest);
947 2199278 : if (regno >= ira_reg_equiv_len
948 2199278 : || (ira_reg_equiv[regno].invariant == NULL_RTX
949 2199259 : && ira_reg_equiv[regno].constant == NULL_RTX))
950 2199242 : continue; /* regno has no equivalence. */
951 36 : ira_assert ((int) reg_equivs->length () > regno);
952 36 : reg_equiv_init (regno)
953 72 : = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
954 : }
955 : }
956 2199278 : if (ira_use_lra_p)
957 2199278 : ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
958 2199278 : emit_insn (list->insn);
959 2199278 : mode = ALLOCNO_MODE (list->to);
960 2199278 : aclass = ALLOCNO_CLASS (list->to);
961 2199278 : cost = 0;
962 2199278 : if (ALLOCNO_HARD_REGNO (list->to) < 0)
963 : {
964 104687 : if (ALLOCNO_HARD_REGNO (list->from) >= 0)
965 : {
966 104599 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
967 104599 : ira_store_cost += cost;
968 : }
969 : }
970 2094591 : else if (ALLOCNO_HARD_REGNO (list->from) < 0)
971 : {
972 152165 : if (ALLOCNO_HARD_REGNO (list->to) >= 0)
973 : {
974 152165 : cost = ira_memory_move_cost[mode][aclass][0] * freq;
975 152165 : ira_load_cost += cost;
976 : }
977 : }
978 : else
979 : {
980 1942426 : ira_init_register_move_cost_if_necessary (mode);
981 1942426 : cost = ira_register_move_cost[mode][aclass][aclass] * freq;
982 1942426 : ira_shuffle_cost += cost;
983 : }
984 2199278 : ira_overall_cost += cost;
985 : }
986 390624 : result = end_sequence ();
987 390624 : return result;
988 : }
989 :
990 : /* Generate RTX move insns from move lists attached to basic blocks
991 : and edges. */
992 : static void
993 35600 : emit_moves (void)
994 : {
995 35600 : basic_block bb;
996 35600 : edge_iterator ei;
997 35600 : edge e;
998 35600 : rtx_insn *insns, *tmp, *next;
999 :
1000 2794891 : FOR_EACH_BB_FN (bb, cfun)
1001 : {
1002 2759291 : if (at_bb_start[bb->index] != NULL)
1003 : {
1004 139680 : at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
1005 139680 : insns
1006 139680 : = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
1007 139680 : tmp = BB_HEAD (bb);
1008 139680 : if (LABEL_P (tmp))
1009 23530 : tmp = NEXT_INSN (tmp);
1010 139680 : if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1011 139680 : tmp = NEXT_INSN (tmp);
1012 : /* Make sure to put the location of TMP or a subsequent instruction
1013 : to avoid inheriting the location of the previous instruction. */
1014 139680 : next = tmp;
1015 277969 : while (next && !NONDEBUG_INSN_P (next))
1016 138289 : next = NEXT_INSN (next);
1017 139680 : if (next)
1018 139680 : set_insn_locations (insns, INSN_LOCATION (next));
1019 139680 : if (tmp == BB_HEAD (bb))
1020 0 : emit_insn_before (insns, tmp);
1021 139680 : else if (tmp)
1022 139680 : emit_insn_after (insns, PREV_INSN (tmp));
1023 : else
1024 0 : emit_insn_after (insns, get_last_insn ());
1025 : }
1026 :
1027 2759291 : if (at_bb_end[bb->index] != NULL)
1028 : {
1029 109287 : at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1030 109287 : insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1031 109287 : ira_assert (! control_flow_insn_p (BB_END (bb)));
1032 109287 : emit_insn_after (insns, BB_END (bb));
1033 : }
1034 :
1035 6970319 : FOR_EACH_EDGE (e, ei, bb->succs)
1036 : {
1037 4211028 : if (e->aux == NULL)
1038 4069371 : continue;
1039 141657 : ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1040 : || ! EDGE_CRITICAL_P (e));
1041 141657 : e->aux = modify_move_list ((move_t) e->aux);
1042 141657 : insert_insn_on_edge
1043 283233 : (emit_move_list ((move_t) e->aux,
1044 283233 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1045 : e);
1046 141657 : if (e->src->next_bb != e->dest)
1047 93954 : ira_additional_jumps_num++;
1048 : }
1049 : }
1050 35600 : }
1051 :
1052 : /* Update costs of A and corresponding allocnos on upper levels on the
1053 : loop tree from reading (if READ_P) or writing A on an execution
1054 : path with FREQ. */
1055 : static void
1056 4398556 : update_costs (ira_allocno_t a, bool read_p, int freq)
1057 : {
1058 10472982 : ira_loop_tree_node_t parent;
1059 :
1060 10472982 : for (;;)
1061 : {
1062 10472982 : ALLOCNO_NREFS (a)++;
1063 10472982 : ALLOCNO_FREQ (a) += freq;
1064 10472982 : ALLOCNO_MEMORY_COST (a)
1065 20945964 : += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
1066 10472982 : [read_p ? 1 : 0] * freq);
1067 10472982 : if (ALLOCNO_CAP (a) != NULL)
1068 : a = ALLOCNO_CAP (a);
1069 8931592 : else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1070 8931592 : || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1071 : break;
1072 : }
1073 4398556 : }
1074 :
1075 : /* Process moves from LIST with execution FREQ to add ranges, copies,
1076 : and modify costs for allocnos involved in the moves. All regnos
1077 : living through the list is in LIVE_THROUGH, and the loop tree node
1078 : used to find corresponding allocnos is NODE. */
1079 : static void
1080 9729610 : add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1081 : bitmap live_through, int freq)
1082 : {
1083 9729610 : int start, n;
1084 9729610 : unsigned int regno;
1085 9729610 : move_t move;
1086 9729610 : ira_allocno_t a;
1087 9729610 : ira_copy_t cp;
1088 9729610 : live_range_t r;
1089 9729610 : bitmap_iterator bi;
1090 9729610 : HARD_REG_SET hard_regs_live;
1091 :
1092 9729610 : if (list == NULL)
1093 9338986 : return;
1094 390624 : n = 0;
1095 6837149 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1096 6446525 : n++;
1097 390624 : REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1098 : /* This is a trick to guarantee that new ranges is not merged with
1099 : the old ones. */
1100 390624 : ira_max_point++;
1101 390624 : start = ira_max_point;
1102 2589902 : for (move = list; move != NULL; move = move->next)
1103 : {
1104 2199278 : ira_allocno_t from = move->from;
1105 2199278 : ira_allocno_t to = move->to;
1106 2199278 : int nr, i;
1107 :
1108 2199278 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1109 2199278 : bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
1110 :
1111 2199278 : nr = ALLOCNO_NUM_OBJECTS (to);
1112 4414268 : for (i = 0; i < nr; i++)
1113 : {
1114 2214990 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1115 2214990 : if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1116 : {
1117 4861 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1118 0 : fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1119 0 : ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
1120 4861 : ira_allocate_object_conflicts (to_obj, n);
1121 : }
1122 : }
1123 2199278 : ior_hard_reg_conflicts (from, hard_regs_live);
1124 2199278 : ior_hard_reg_conflicts (to, hard_regs_live);
1125 :
1126 2199278 : update_costs (from, true, freq);
1127 2199278 : update_costs (to, false, freq);
1128 2199278 : cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
1129 2199278 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1130 0 : fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1131 : cp->num, ALLOCNO_NUM (cp->first),
1132 0 : REGNO (allocno_emit_reg (cp->first)),
1133 : ALLOCNO_NUM (cp->second),
1134 0 : REGNO (allocno_emit_reg (cp->second)));
1135 :
1136 2199278 : nr = ALLOCNO_NUM_OBJECTS (from);
1137 4414268 : for (i = 0; i < nr; i++)
1138 : {
1139 2214990 : ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1140 2214990 : r = OBJECT_LIVE_RANGES (from_obj);
1141 2214990 : if (r == NULL || r->finish >= 0)
1142 : {
1143 2210129 : ira_add_live_range_to_object (from_obj, start, ira_max_point);
1144 2210129 : 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 : start, ira_max_point, ALLOCNO_NUM (from),
1148 0 : REGNO (allocno_emit_reg (from)));
1149 : }
1150 : else
1151 : {
1152 4861 : r->finish = ira_max_point;
1153 4861 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1154 0 : fprintf (ira_dump_file,
1155 : " Adding range [%d..%d] to allocno a%dr%d\n",
1156 : r->start, ira_max_point, ALLOCNO_NUM (from),
1157 0 : REGNO (allocno_emit_reg (from)));
1158 : }
1159 : }
1160 2199278 : ira_max_point++;
1161 2199278 : nr = ALLOCNO_NUM_OBJECTS (to);
1162 4414268 : for (i = 0; i < nr; i++)
1163 : {
1164 2214990 : ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1165 2214990 : ira_add_live_range_to_object (to_obj, ira_max_point, -1);
1166 : }
1167 2199278 : ira_max_point++;
1168 : }
1169 2589902 : for (move = list; move != NULL; move = move->next)
1170 : {
1171 2199278 : int nr, i;
1172 2199278 : nr = ALLOCNO_NUM_OBJECTS (move->to);
1173 4414268 : for (i = 0; i < nr; i++)
1174 : {
1175 2214990 : ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1176 2214990 : r = OBJECT_LIVE_RANGES (to_obj);
1177 2214990 : if (r->finish < 0)
1178 : {
1179 2210129 : r->finish = ira_max_point - 1;
1180 2210129 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1181 0 : fprintf (ira_dump_file,
1182 : " Adding range [%d..%d] to allocno a%dr%d\n",
1183 : r->start, r->finish, ALLOCNO_NUM (move->to),
1184 0 : REGNO (allocno_emit_reg (move->to)));
1185 : }
1186 : }
1187 : }
1188 4642732 : EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1189 : {
1190 4252108 : ira_allocno_t to;
1191 4252108 : int nr, i;
1192 :
1193 4252108 : a = node->regno_allocno_map[regno];
1194 4252108 : if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
1195 9406 : a = to;
1196 4252108 : nr = ALLOCNO_NUM_OBJECTS (a);
1197 8608043 : for (i = 0; i < nr; i++)
1198 : {
1199 4355935 : ira_object_t obj = ALLOCNO_OBJECT (a, i);
1200 4355935 : ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1201 : }
1202 4252108 : if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1203 0 : fprintf
1204 0 : (ira_dump_file,
1205 : " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1206 : start, ira_max_point - 1,
1207 : to != NULL ? "upper level" : "",
1208 0 : ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
1209 : }
1210 : }
1211 :
1212 : /* Process all move list to add ranges, conflicts, copies, and modify
1213 : costs for allocnos involved in the moves. */
1214 : static void
1215 35600 : add_ranges_and_copies (void)
1216 : {
1217 35600 : basic_block bb;
1218 35600 : edge_iterator ei;
1219 35600 : edge e;
1220 35600 : ira_loop_tree_node_t node;
1221 35600 : bitmap live_through;
1222 :
1223 35600 : live_through = ira_allocate_bitmap ();
1224 2794891 : FOR_EACH_BB_FN (bb, cfun)
1225 : {
1226 : /* It does not matter what loop_tree_node (of source or
1227 : destination block) to use for searching allocnos by their
1228 : regnos because of subsequent IR flattening. */
1229 2759291 : node = IRA_BB_NODE (bb)->parent;
1230 2759291 : bitmap_copy (live_through, df_get_live_in (bb));
1231 2759291 : add_range_and_copies_from_move_list
1232 2759291 : (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1233 2759291 : bitmap_copy (live_through, df_get_live_out (bb));
1234 2759291 : add_range_and_copies_from_move_list
1235 2759291 : (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1236 6970319 : FOR_EACH_EDGE (e, ei, bb->succs)
1237 : {
1238 4211028 : bitmap_and (live_through,
1239 4211028 : df_get_live_in (e->dest), df_get_live_out (bb));
1240 4211028 : add_range_and_copies_from_move_list
1241 8419987 : ((move_t) e->aux, node, live_through,
1242 12631015 : REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1243 : }
1244 : }
1245 35600 : ira_free_bitmap (live_through);
1246 35600 : }
1247 :
1248 : /* The entry function changes code and generates shuffling allocnos on
1249 : region borders for the regional (LOOPS_P is TRUE in this case)
1250 : register allocation. */
1251 : void
1252 1471362 : ira_emit (bool loops_p)
1253 : {
1254 1471362 : basic_block bb;
1255 1471362 : rtx_insn *insn;
1256 1471362 : edge_iterator ei;
1257 1471362 : edge e;
1258 1471362 : ira_allocno_t a;
1259 1471362 : ira_allocno_iterator ai;
1260 1471362 : size_t sz;
1261 :
1262 37930378 : FOR_EACH_ALLOCNO (a, ai)
1263 36459016 : ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
1264 1471362 : if (! loops_p)
1265 1435762 : return;
1266 35600 : sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1267 35600 : at_bb_start = (move_t *) ira_allocate (sz);
1268 35600 : memset (at_bb_start, 0, sz);
1269 35600 : at_bb_end = (move_t *) ira_allocate (sz);
1270 35600 : memset (at_bb_end, 0, sz);
1271 35600 : local_allocno_bitmap = ira_allocate_bitmap ();
1272 35600 : used_regno_bitmap = ira_allocate_bitmap ();
1273 35600 : renamed_regno_bitmap = ira_allocate_bitmap ();
1274 35600 : max_regno_before_changing = max_reg_num ();
1275 35600 : ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1276 35600 : set_allocno_somewhere_renamed_p ();
1277 35600 : ira_free_bitmap (used_regno_bitmap);
1278 35600 : ira_free_bitmap (renamed_regno_bitmap);
1279 35600 : ira_free_bitmap (local_allocno_bitmap);
1280 35600 : setup_entered_from_non_parent_p ();
1281 2794891 : FOR_EACH_BB_FN (bb, cfun)
1282 : {
1283 2759291 : at_bb_start[bb->index] = NULL;
1284 2759291 : at_bb_end[bb->index] = NULL;
1285 6970319 : FOR_EACH_EDGE (e, ei, bb->succs)
1286 4211028 : if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
1287 4172619 : generate_edge_moves (e);
1288 : }
1289 35600 : allocno_last_set
1290 35600 : = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1291 35600 : allocno_last_set_check
1292 35600 : = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1293 35600 : memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1294 35600 : memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1295 35600 : curr_tick = 0;
1296 2794891 : FOR_EACH_BB_FN (bb, cfun)
1297 2759291 : unify_moves (bb, true);
1298 2794891 : FOR_EACH_BB_FN (bb, cfun)
1299 2759291 : unify_moves (bb, false);
1300 35600 : move_vec.create (ira_allocnos_num);
1301 35600 : emit_moves ();
1302 35600 : add_ranges_and_copies ();
1303 : /* Clean up: */
1304 2794891 : FOR_EACH_BB_FN (bb, cfun)
1305 : {
1306 2759291 : free_move_list (at_bb_start[bb->index]);
1307 2759291 : free_move_list (at_bb_end[bb->index]);
1308 6970319 : FOR_EACH_EDGE (e, ei, bb->succs)
1309 : {
1310 4211028 : free_move_list ((move_t) e->aux);
1311 4211028 : e->aux = NULL;
1312 : }
1313 : }
1314 35600 : move_vec.release ();
1315 35600 : ira_free (allocno_last_set_check);
1316 35600 : ira_free (allocno_last_set);
1317 35600 : commit_edge_insertions ();
1318 : /* Fix insn codes. It is necessary to do it before reload because
1319 : reload assumes initial insn codes defined. The insn codes can be
1320 : invalidated by CFG infrastructure for example in jump
1321 : redirection. */
1322 2903520 : FOR_EACH_BB_FN (bb, cfun)
1323 36723589 : FOR_BB_INSNS_REVERSE (bb, insn)
1324 33855669 : if (INSN_P (insn))
1325 28600255 : recog_memoized (insn);
1326 35600 : ira_free (at_bb_end);
1327 35600 : ira_free (at_bb_start);
1328 : }
|
