]> git.ipfire.org Git - thirdparty/gcc.git/blame - gcc/ira-emit.c
[Ada] Improved support for aspect alignment in CCG
[thirdparty/gcc.git] / gcc / ira-emit.c
CommitLineData
058e97ec 1/* Integrated Register Allocator. Changing code and generating moves.
8d9254fc 2 Copyright (C) 2006-2020 Free Software Foundation, Inc.
058e97ec
VM
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
1756cb66
VM
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. */
058e97ec
VM
67
68#include "config.h"
69#include "system.h"
70#include "coretypes.h"
c7131fb2 71#include "backend.h"
058e97ec 72#include "rtl.h"
957060b5
AM
73#include "tree.h"
74#include "predict.h"
c7131fb2 75#include "df.h"
957060b5
AM
76#include "insn-config.h"
77#include "regs.h"
4d0cdd0c 78#include "memmodel.h"
957060b5
AM
79#include "ira.h"
80#include "ira-int.h"
60393bbc
AM
81#include "cfgrtl.h"
82#include "cfgbuild.h"
058e97ec 83#include "expr.h"
058e97ec 84#include "reload.h"
c7131fb2 85#include "cfgloop.h"
058e97ec
VM
86
87
1756cb66
VM
88/* Data used to emit live range split insns and to flattening IR. */
89ira_emit_data_t ira_allocno_emit_data;
90
91/* Definitions for vectors of pointers. */
92typedef void *void_p;
1756cb66
VM
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. */
9771b263 97static vec<void_p> new_allocno_emit_data_vec;
1756cb66
VM
98
99/* Allocate and initiate the emit data. */
100void
101ira_initiate_emit_data (void)
102{
103 ira_allocno_t a;
104 ira_allocno_iterator ai;
105
106 ira_allocno_emit_data
107 = (ira_emit_data_t) ira_allocate (ira_allocnos_num
108 * sizeof (struct ira_emit_data));
109 memset (ira_allocno_emit_data, 0,
110 ira_allocnos_num * sizeof (struct ira_emit_data));
111 FOR_EACH_ALLOCNO (a, ai)
112 ALLOCNO_ADD_DATA (a) = ira_allocno_emit_data + ALLOCNO_NUM (a);
9771b263 113 new_allocno_emit_data_vec.create (50);
1756cb66
VM
114
115}
116
117/* Free the emit data. */
118void
119ira_finish_emit_data (void)
120{
121 void_p p;
122 ira_allocno_t a;
123 ira_allocno_iterator ai;
124
125 ira_free (ira_allocno_emit_data);
126 FOR_EACH_ALLOCNO (a, ai)
127 ALLOCNO_ADD_DATA (a) = NULL;
9771b263 128 for (;new_allocno_emit_data_vec.length () != 0;)
1756cb66 129 {
9771b263 130 p = new_allocno_emit_data_vec.pop ();
1756cb66
VM
131 ira_free (p);
132 }
9771b263 133 new_allocno_emit_data_vec.release ();
1756cb66
VM
134}
135
136/* Create and return a new allocno with given REGNO and
137 LOOP_TREE_NODE. Allocate emit data for it. */
138static ira_allocno_t
139create_new_allocno (int regno, ira_loop_tree_node_t loop_tree_node)
140{
141 ira_allocno_t a;
142
143 a = ira_create_allocno (regno, false, loop_tree_node);
144 ALLOCNO_ADD_DATA (a) = ira_allocate (sizeof (struct ira_emit_data));
145 memset (ALLOCNO_ADD_DATA (a), 0, sizeof (struct ira_emit_data));
9771b263 146 new_allocno_emit_data_vec.safe_push (ALLOCNO_ADD_DATA (a));
1756cb66
VM
147 return a;
148}
149
150\f
151
152/* See comments below. */
058e97ec
VM
153typedef struct move *move_t;
154
155/* The structure represents an allocno move. Both allocnos have the
073a8998 156 same original regno but different allocation. */
058e97ec
VM
157struct 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. */
070a1983 174 rtx_insn *insn;
058e97ec
VM
175};
176
177/* Array of moves (indexed by BB index) which should be put at the
178 start/end of the corresponding basic blocks. */
179static 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. */
184static int max_regno_before_changing;
185
186/* Return new move of allocnos TO and FROM. */
187static move_t
188create_move (ira_allocno_t to, ira_allocno_t from)
189{
190 move_t move;
191
192 move = (move_t) ira_allocate (sizeof (struct move));
193 move->deps = NULL;
194 move->deps_num = 0;
195 move->to = to;
196 move->from = from;
197 move->next = NULL;
070a1983 198 move->insn = NULL;
058e97ec
VM
199 move->visited_p = false;
200 return move;
201}
202
203/* Free memory for MOVE and its dependencies. */
204static void
205free_move (move_t move)
206{
207 if (move->deps != NULL)
208 ira_free (move->deps);
209 ira_free (move);
210}
211
212/* Free memory for list of the moves given by its HEAD. */
213static void
214free_move_list (move_t head)
215{
216 move_t next;
b8698a0f 217
058e97ec
VM
218 for (; head != NULL; head = next)
219 {
220 next = head->next;
221 free_move (head);
222 }
223}
224
dd5a833e 225/* Return TRUE if the move list LIST1 and LIST2 are equal (two
058e97ec
VM
226 moves are equal if they involve the same allocnos). */
227static bool
228eq_move_lists_p (move_t list1, move_t list2)
229{
230 for (; list1 != NULL && list2 != NULL;
231 list1 = list1->next, list2 = list2->next)
232 if (list1->from != list2->from || list1->to != list2->to)
233 return false;
234 return list1 == list2;
235}
236
a174c19c
VM
237/* Print move list LIST into file F. */
238static void
239print_move_list (FILE *f, move_t list)
240{
241 for (; list != NULL; list = list->next)
242 fprintf (f, " a%dr%d->a%dr%d",
243 ALLOCNO_NUM (list->from), ALLOCNO_REGNO (list->from),
244 ALLOCNO_NUM (list->to), ALLOCNO_REGNO (list->to));
245 fprintf (f, "\n");
246}
247
248extern void ira_debug_move_list (move_t list);
249
250/* Print move list LIST into stderr. */
251void
252ira_debug_move_list (move_t list)
253{
254 print_move_list (stderr, list);
255}
256
058e97ec
VM
257/* This recursive function changes pseudo-registers in *LOC if it is
258 necessary. The function returns TRUE if a change was done. */
259static bool
260change_regs (rtx *loc)
261{
262 int i, regno, result = false;
263 const char *fmt;
264 enum rtx_code code;
c39a4ad7 265 rtx reg;
058e97ec
VM
266
267 if (*loc == NULL_RTX)
268 return false;
269 code = GET_CODE (*loc);
270 if (code == REG)
271 {
272 regno = REGNO (*loc);
273 if (regno < FIRST_PSEUDO_REGISTER)
274 return false;
275 if (regno >= max_regno_before_changing)
276 /* It is a shared register which was changed already. */
277 return false;
278 if (ira_curr_regno_allocno_map[regno] == NULL)
279 return false;
1756cb66 280 reg = allocno_emit_reg (ira_curr_regno_allocno_map[regno]);
c39a4ad7
JH
281 if (reg == *loc)
282 return false;
283 *loc = reg;
058e97ec
VM
284 return true;
285 }
286
287 fmt = GET_RTX_FORMAT (code);
288 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
289 {
290 if (fmt[i] == 'e')
291 result = change_regs (&XEXP (*loc, i)) || result;
292 else if (fmt[i] == 'E')
293 {
294 int j;
295
296 for (j = XVECLEN (*loc, i) - 1; j >= 0; j--)
297 result = change_regs (&XVECEXP (*loc, i, j)) || result;
298 }
299 }
300 return result;
301}
302
b2908ba6
DM
303static bool
304change_regs_in_insn (rtx_insn **insn_ptr)
305{
306 rtx rtx = *insn_ptr;
307 bool result = change_regs (&rtx);
308 *insn_ptr = as_a <rtx_insn *> (rtx);
309 return result;
310}
311
058e97ec
VM
312/* Attach MOVE to the edge E. The move is attached to the head of the
313 list if HEAD_P is TRUE. */
314static void
315add_to_edge_list (edge e, move_t move, bool head_p)
316{
317 move_t last;
318
319 if (head_p || e->aux == NULL)
320 {
321 move->next = (move_t) e->aux;
322 e->aux = move;
323 }
324 else
325 {
326 for (last = (move_t) e->aux; last->next != NULL; last = last->next)
327 ;
328 last->next = move;
329 move->next = NULL;
330 }
331}
332
333/* Create and return new pseudo-register with the same attributes as
334 ORIGINAL_REG. */
acf41a74
BS
335rtx
336ira_create_new_reg (rtx original_reg)
058e97ec
VM
337{
338 rtx new_reg;
339
340 new_reg = gen_reg_rtx (GET_MODE (original_reg));
341 ORIGINAL_REGNO (new_reg) = ORIGINAL_REGNO (original_reg);
342 REG_USERVAR_P (new_reg) = REG_USERVAR_P (original_reg);
343 REG_POINTER (new_reg) = REG_POINTER (original_reg);
344 REG_ATTRS (new_reg) = REG_ATTRS (original_reg);
345 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
346 fprintf (ira_dump_file, " Creating newreg=%i from oldreg=%i\n",
347 REGNO (new_reg), REGNO (original_reg));
55a2c322 348 ira_expand_reg_equiv ();
058e97ec
VM
349 return new_reg;
350}
351
352/* Return TRUE if loop given by SUBNODE inside the loop given by
353 NODE. */
354static bool
355subloop_tree_node_p (ira_loop_tree_node_t subnode, ira_loop_tree_node_t node)
356{
357 for (; subnode != NULL; subnode = subnode->parent)
358 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. */
365static void
366set_allocno_reg (ira_allocno_t allocno, rtx reg)
367{
368 int regno;
369 ira_allocno_t a;
370 ira_loop_tree_node_t node;
371
372 node = ALLOCNO_LOOP_TREE_NODE (allocno);
373 for (a = ira_regno_allocno_map[ALLOCNO_REGNO (allocno)];
374 a != NULL;
375 a = ALLOCNO_NEXT_REGNO_ALLOCNO (a))
376 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a), node))
1756cb66 377 ALLOCNO_EMIT_DATA (a)->reg = reg;
058e97ec 378 for (a = ALLOCNO_CAP (allocno); a != NULL; a = ALLOCNO_CAP (a))
1756cb66 379 ALLOCNO_EMIT_DATA (a)->reg = reg;
058e97ec
VM
380 regno = ALLOCNO_REGNO (allocno);
381 for (a = allocno;;)
382 {
383 if (a == NULL || (a = ALLOCNO_CAP (a)) == NULL)
384 {
385 node = node->parent;
386 if (node == NULL)
387 break;
388 a = node->regno_allocno_map[regno];
389 }
390 if (a == NULL)
391 continue;
1756cb66 392 if (ALLOCNO_EMIT_DATA (a)->child_renamed_p)
058e97ec 393 break;
1756cb66 394 ALLOCNO_EMIT_DATA (a)->child_renamed_p = true;
058e97ec
VM
395 }
396}
397
ea1c67e6
VM
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. */
058e97ec 401static bool
ea1c67e6
VM
402entered_from_non_parent_p (ira_loop_tree_node_t loop_node)
403{
404 ira_loop_tree_node_t bb_node, src_loop_node, parent;
405 edge e;
406 edge_iterator ei;
407
1756cb66
VM
408 for (bb_node = loop_node->children;
409 bb_node != NULL;
410 bb_node = bb_node->next)
ea1c67e6
VM
411 if (bb_node->bb != NULL)
412 {
413 FOR_EACH_EDGE (e, ei, bb_node->bb->preds)
fefa31b5 414 if (e->src != ENTRY_BLOCK_PTR_FOR_FN (cfun)
ea1c67e6
VM
415 && (src_loop_node = IRA_BB_NODE (e->src)->parent) != loop_node)
416 {
417 for (parent = src_loop_node->parent;
418 parent != NULL;
419 parent = parent->parent)
420 if (parent == loop_node)
421 break;
422 if (parent != NULL)
423 /* That is an exit from a nested loop -- skip it. */
424 continue;
425 for (parent = loop_node->parent;
426 parent != NULL;
427 parent = parent->parent)
428 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. */
438static void
439setup_entered_from_non_parent_p (void)
440{
441 unsigned int i;
442 loop_p loop;
443
2608d841 444 ira_assert (current_loops != NULL);
0fc822d0 445 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun), i, loop)
ea1c67e6
VM
446 if (ira_loop_nodes[i].regno_allocno_map != NULL)
447 ira_loop_nodes[i].entered_from_non_parent_p
448 = entered_from_non_parent_p (&ira_loop_nodes[i]);
449}
450
451/* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
073a8998 452 DEST_ALLOCNO (assigned to memory) can be removed because it does
ea1c67e6
VM
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. */
456static bool
457store_can_be_removed_p (ira_allocno_t src_allocno, ira_allocno_t dest_allocno)
058e97ec
VM
458{
459 int regno, orig_regno;
460 ira_allocno_t a;
461 ira_loop_tree_node_t node;
462
463 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno) == NULL
464 && ALLOCNO_CAP_MEMBER (dest_allocno) == NULL);
465 orig_regno = ALLOCNO_REGNO (src_allocno);
1756cb66 466 regno = REGNO (allocno_emit_reg (dest_allocno));
058e97ec
VM
467 for (node = ALLOCNO_LOOP_TREE_NODE (src_allocno);
468 node != NULL;
469 node = node->parent)
ea1c67e6
VM
470 {
471 a = node->regno_allocno_map[orig_regno];
472 ira_assert (a != NULL);
1756cb66 473 if (REGNO (allocno_emit_reg (a)) == (unsigned) regno)
ea1c67e6
VM
474 /* We achieved the destination and everything is ok. */
475 return true;
476 else if (bitmap_bit_p (node->modified_regnos, orig_regno))
477 return false;
478 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 }
51934590
VM
489 /* It is actually a loop entry -- do not remove the store. */
490 return false;
058e97ec
VM
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. */
496static void
497generate_edge_moves (edge e)
498{
499 ira_loop_tree_node_t src_loop_node, dest_loop_node;
500 unsigned int regno;
501 bitmap_iterator bi;
502 ira_allocno_t src_allocno, dest_allocno, *src_map, *dest_map;
503 move_t move;
bf744527 504 bitmap regs_live_in_dest, regs_live_out_src;
058e97ec
VM
505
506 src_loop_node = IRA_BB_NODE (e->src)->parent;
507 dest_loop_node = IRA_BB_NODE (e->dest)->parent;
508 e->aux = NULL;
509 if (src_loop_node == dest_loop_node)
510 return;
511 src_map = src_loop_node->regno_allocno_map;
512 dest_map = dest_loop_node->regno_allocno_map;
bf744527
SB
513 regs_live_in_dest = df_get_live_in (e->dest);
514 regs_live_out_src = df_get_live_out (e->src);
515 EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest,
058e97ec 516 FIRST_PSEUDO_REGISTER, regno, bi)
bf744527 517 if (bitmap_bit_p (regs_live_out_src, regno))
058e97ec
VM
518 {
519 src_allocno = src_map[regno];
520 dest_allocno = dest_map[regno];
1756cb66
VM
521 if (REGNO (allocno_emit_reg (src_allocno))
522 == REGNO (allocno_emit_reg (dest_allocno)))
058e97ec 523 continue;
82b33628
VM
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
55a2c322 527 checking in function change_loop). */
058e97ec
VM
528 if (ALLOCNO_HARD_REGNO (dest_allocno) < 0
529 && ALLOCNO_HARD_REGNO (src_allocno) >= 0
ea1c67e6 530 && store_can_be_removed_p (src_allocno, dest_allocno))
058e97ec 531 {
1756cb66
VM
532 ALLOCNO_EMIT_DATA (src_allocno)->mem_optimized_dest = dest_allocno;
533 ALLOCNO_EMIT_DATA (dest_allocno)->mem_optimized_dest_p = true;
058e97ec
VM
534 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
535 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 continue;
539 }
540 move = create_move (dest_allocno, src_allocno);
541 add_to_edge_list (e, move, true);
542 }
543}
544
545/* Bitmap of allocnos local for the current loop. */
546static 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. */
551static 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. */
556static bitmap renamed_regno_bitmap;
557
558/* Change (if necessary) pseudo-registers inside loop given by loop
559 tree node NODE. */
560static void
561change_loop (ira_loop_tree_node_t node)
562{
563 bitmap_iterator bi;
564 unsigned int i;
565 int regno;
566 bool used_p;
567 ira_allocno_t allocno, parent_allocno, *map;
b2908ba6
DM
568 rtx_insn *insn;
569 rtx original_reg;
1756cb66 570 enum reg_class aclass, pclass;
058e97ec
VM
571 ira_loop_tree_node_t parent;
572
573 if (node != ira_loop_tree_root)
574 {
2608d841
VM
575 ira_assert (current_loops != NULL);
576
058e97ec
VM
577 if (node->bb != NULL)
578 {
579 FOR_BB_INSNS (node->bb, insn)
b2908ba6 580 if (INSN_P (insn) && change_regs_in_insn (&insn))
058e97ec
VM
581 {
582 df_insn_rescan (insn);
583 df_notes_rescan (insn);
584 }
585 return;
586 }
b8698a0f 587
058e97ec
VM
588 if (internal_flag_ira_verbose > 3 && ira_dump_file != NULL)
589 fprintf (ira_dump_file,
590 " Changing RTL for loop %d (header bb%d)\n",
2608d841 591 node->loop_num, node->loop->header->index);
b8698a0f 592
058e97ec
VM
593 parent = ira_curr_loop_tree_node->parent;
594 map = parent->regno_allocno_map;
595 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node->border_allocnos,
596 0, i, bi)
597 {
598 allocno = ira_allocnos[i];
599 regno = ALLOCNO_REGNO (allocno);
1756cb66
VM
600 aclass = ALLOCNO_CLASS (allocno);
601 pclass = ira_pressure_class_translate[aclass];
058e97ec
VM
602 parent_allocno = map[regno];
603 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 if (parent_allocno != NULL
611 && (ALLOCNO_HARD_REGNO (allocno)
612 == ALLOCNO_HARD_REGNO (parent_allocno))
613 && (ALLOCNO_HARD_REGNO (allocno) < 0
1756cb66 614 || (parent->reg_pressure[pclass] + 1
f508f827 615 <= ira_class_hard_regs_num[pclass])
058e97ec
VM
616 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
617 [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. */
bcb21886
KY
622 || ira_equiv_no_lvalue_p (regno)
623 || (pic_offset_table_rtx != NULL
624 && (ALLOCNO_REGNO (allocno)
625 == (int) REGNO (pic_offset_table_rtx)))))
058e97ec 626 continue;
1756cb66 627 original_reg = allocno_emit_reg (allocno);
058e97ec 628 if (parent_allocno == NULL
1756cb66
VM
629 || (REGNO (allocno_emit_reg (parent_allocno))
630 == REGNO (original_reg)))
058e97ec
VM
631 {
632 if (internal_flag_ira_verbose > 3 && ira_dump_file)
633 fprintf (ira_dump_file, " %i vs parent %i:",
634 ALLOCNO_HARD_REGNO (allocno),
635 ALLOCNO_HARD_REGNO (parent_allocno));
acf41a74 636 set_allocno_reg (allocno, ira_create_new_reg (original_reg));
058e97ec
VM
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 bitmap_and_compl (local_allocno_bitmap,
49d988e7 644 ira_curr_loop_tree_node->all_allocnos,
058e97ec
VM
645 ira_curr_loop_tree_node->border_allocnos);
646 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap, 0, i, bi)
647 {
648 allocno = ira_allocnos[i];
649 regno = ALLOCNO_REGNO (allocno);
650 if (ALLOCNO_CAP_MEMBER (allocno) != NULL)
651 continue;
fcaa4ca4 652 used_p = !bitmap_set_bit (used_regno_bitmap, regno);
1756cb66 653 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
058e97ec
VM
654 if (! used_p)
655 continue;
656 bitmap_set_bit (renamed_regno_bitmap, regno);
acf41a74 657 set_allocno_reg (allocno, ira_create_new_reg (allocno_emit_reg (allocno)));
058e97ec
VM
658 }
659}
660
661/* Process to set up flag somewhere_renamed_p. */
662static void
663set_allocno_somewhere_renamed_p (void)
664{
665 unsigned int regno;
666 ira_allocno_t allocno;
667 ira_allocno_iterator ai;
668
669 FOR_EACH_ALLOCNO (allocno, ai)
670 {
671 regno = ALLOCNO_REGNO (allocno);
672 if (bitmap_bit_p (renamed_regno_bitmap, regno)
1756cb66
VM
673 && REGNO (allocno_emit_reg (allocno)) == regno)
674 ALLOCNO_EMIT_DATA (allocno)->somewhere_renamed_p = true;
058e97ec
VM
675 }
676}
677
678/* Return TRUE if move lists on all edges given in vector VEC are
679 equal. */
680static bool
9771b263 681eq_edge_move_lists_p (vec<edge, va_gc> *vec)
058e97ec
VM
682{
683 move_t list;
684 int i;
685
686 list = (move_t) EDGE_I (vec, 0)->aux;
687 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
688 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. */
696static void
697unify_moves (basic_block bb, bool start_p)
698{
699 int i;
700 edge e;
701 move_t list;
9771b263 702 vec<edge, va_gc> *vec;
058e97ec
VM
703
704 vec = (start_p ? bb->preds : bb->succs);
705 if (EDGE_COUNT (vec) == 0 || ! eq_edge_move_lists_p (vec))
706 return;
707 e = EDGE_I (vec, 0);
708 list = (move_t) e->aux;
709 if (! start_p && control_flow_insn_p (BB_END (bb)))
710 return;
711 e->aux = NULL;
712 for (i = EDGE_COUNT (vec) - 1; i > 0; i--)
713 {
714 e = EDGE_I (vec, i);
715 free_move_list ((move_t) e->aux);
716 e->aux = NULL;
717 }
718 if (start_p)
719 at_bb_start[bb->index] = list;
720 else
721 at_bb_end[bb->index] = list;
722}
723
724/* Last move (in move sequence being processed) setting up the
725 corresponding hard register. */
726static 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. */
730static int hard_regno_last_set_check[FIRST_PSEUDO_REGISTER];
731
732/* Last move (in move sequence being processed) setting up the
733 corresponding allocno. */
734static 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. */
738static int *allocno_last_set_check;
739
740/* Definition of vector of moves. */
058e97ec
VM
741
742/* This vec contains moves sorted topologically (depth-first) on their
743 dependency graph. */
9771b263 744static vec<move_t> move_vec;
058e97ec
VM
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'. */
749static int curr_tick;
750
751/* This recursive function traverses dependencies of MOVE and produces
752 topological sorting (in depth-first order). */
753static void
754traverse_moves (move_t move)
755{
756 int i;
757
758 if (move->visited_p)
759 return;
760 move->visited_p = true;
761 for (i = move->deps_num - 1; i >= 0; i--)
762 traverse_moves (move->deps[i]);
9771b263 763 move_vec.safe_push (move);
058e97ec
VM
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. */
770static move_t
771modify_move_list (move_t list)
772{
773 int i, n, nregs, hard_regno;
a49ae217 774 ira_allocno_t to, from;
058e97ec
VM
775 move_t move, new_move, set_move, first, last;
776
777 if (list == NULL)
778 return NULL;
df3e3493 779 /* Create move deps. */
058e97ec
VM
780 curr_tick++;
781 for (move = list; move != NULL; move = move->next)
782 {
783 to = move->to;
784 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
785 continue;
ad474626 786 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
058e97ec
VM
787 for (i = 0; i < nregs; i++)
788 {
789 hard_regno_last_set[hard_regno + i] = move;
790 hard_regno_last_set_check[hard_regno + i] = curr_tick;
791 }
792 }
793 for (move = list; move != NULL; move = move->next)
794 {
795 from = move->from;
796 to = move->to;
797 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
798 {
ad474626 799 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
058e97ec
VM
800 for (n = i = 0; i < nregs; i++)
801 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
802 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
803 != ALLOCNO_REGNO (from)))
804 n++;
805 move->deps = (move_t *) ira_allocate (n * sizeof (move_t));
806 for (n = i = 0; i < nregs; i++)
807 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
808 && (ALLOCNO_REGNO (hard_regno_last_set[hard_regno + i]->to)
809 != ALLOCNO_REGNO (from)))
810 move->deps[n++] = hard_regno_last_set[hard_regno + i];
811 move->deps_num = n;
812 }
813 }
df3e3493 814 /* Topological sorting: */
9771b263 815 move_vec.truncate (0);
058e97ec
VM
816 for (move = list; move != NULL; move = move->next)
817 traverse_moves (move);
818 last = NULL;
9771b263 819 for (i = (int) move_vec.length () - 1; i >= 0; i--)
058e97ec 820 {
9771b263 821 move = move_vec[i];
058e97ec
VM
822 move->next = NULL;
823 if (last != NULL)
824 last->next = move;
825 last = move;
826 }
9771b263 827 first = move_vec.last ();
058e97ec
VM
828 /* Removing cycles: */
829 curr_tick++;
9771b263 830 move_vec.truncate (0);
058e97ec
VM
831 for (move = first; move != NULL; move = move->next)
832 {
833 from = move->from;
834 to = move->to;
835 if ((hard_regno = ALLOCNO_HARD_REGNO (from)) >= 0)
836 {
ad474626 837 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (from));
058e97ec
VM
838 for (i = 0; i < nregs; i++)
839 if (hard_regno_last_set_check[hard_regno + i] == curr_tick
840 && ALLOCNO_HARD_REGNO
841 (hard_regno_last_set[hard_regno + i]->to) >= 0)
842 {
ac0ab4f7 843 int n, j;
a49ae217 844 ira_allocno_t new_allocno;
a49ae217 845
058e97ec
VM
846 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 new_allocno
1756cb66 852 = create_new_allocno (ALLOCNO_REGNO (set_move->to),
058e97ec
VM
853 ALLOCNO_LOOP_TREE_NODE (set_move->to));
854 ALLOCNO_MODE (new_allocno) = ALLOCNO_MODE (set_move->to);
1756cb66
VM
855 ira_set_allocno_class (new_allocno,
856 ALLOCNO_CLASS (set_move->to));
ac0ab4f7 857 ira_create_allocno_objects (new_allocno);
058e97ec
VM
858 ALLOCNO_ASSIGNED_P (new_allocno) = true;
859 ALLOCNO_HARD_REGNO (new_allocno) = -1;
1756cb66 860 ALLOCNO_EMIT_DATA (new_allocno)->reg
acf41a74 861 = ira_create_new_reg (allocno_emit_reg (set_move->to));
a49ae217 862
058e97ec
VM
863 /* Make it possibly conflicting with all earlier
864 created allocnos. Cases where temporary allocnos
865 created to remove the cycles are quite rare. */
ac0ab4f7
BS
866 n = ALLOCNO_NUM_OBJECTS (new_allocno);
867 gcc_assert (n == ALLOCNO_NUM_OBJECTS (set_move->to));
868 for (j = 0; j < n; j++)
869 {
870 ira_object_t new_obj = ALLOCNO_OBJECT (new_allocno, j);
871
872 OBJECT_MIN (new_obj) = 0;
873 OBJECT_MAX (new_obj) = ira_objects_num - 1;
874 }
875
058e97ec
VM
876 new_move = create_move (set_move->to, new_allocno);
877 set_move->to = new_allocno;
9771b263 878 move_vec.safe_push (new_move);
058e97ec
VM
879 ira_move_loops_num++;
880 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
881 fprintf (ira_dump_file,
882 " Creating temporary allocno a%dr%d\n",
883 ALLOCNO_NUM (new_allocno),
1756cb66 884 REGNO (allocno_emit_reg (new_allocno)));
058e97ec
VM
885 }
886 }
887 if ((hard_regno = ALLOCNO_HARD_REGNO (to)) < 0)
888 continue;
ad474626 889 nregs = hard_regno_nregs (hard_regno, ALLOCNO_MODE (to));
058e97ec
VM
890 for (i = 0; i < nregs; i++)
891 {
892 hard_regno_last_set[hard_regno + i] = move;
893 hard_regno_last_set_check[hard_regno + i] = curr_tick;
894 }
895 }
9771b263 896 for (i = (int) move_vec.length () - 1; i >= 0; i--)
058e97ec 897 {
9771b263 898 move = move_vec[i];
058e97ec
VM
899 move->next = NULL;
900 last->next = move;
901 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. */
070a1983 908static rtx_insn *
058e97ec
VM
909emit_move_list (move_t list, int freq)
910{
55a2c322
VM
911 rtx to, from, dest;
912 int to_regno, from_regno, cost, regno;
070a1983
DM
913 rtx_insn *result, *insn;
914 rtx set;
ef4bddc2 915 machine_mode mode;
1756cb66 916 enum reg_class aclass;
058e97ec 917
55a2c322 918 grow_reg_equivs ();
058e97ec
VM
919 start_sequence ();
920 for (; list != NULL; list = list->next)
921 {
922 start_sequence ();
55a2c322
VM
923 to = allocno_emit_reg (list->to);
924 to_regno = REGNO (to);
925 from = allocno_emit_reg (list->from);
926 from_regno = REGNO (from);
927 emit_move_insn (to, from);
058e97ec
VM
928 list->insn = get_insns ();
929 end_sequence ();
058e97ec 930 for (insn = list->insn; insn != NULL_RTX; insn = NEXT_INSN (insn))
e5b0e1ca
VM
931 {
932 /* The reload needs to have set up insn codes. If the
933 reload sets up insn codes by itself, it may fail because
934 insns will have hard registers instead of pseudos and
935 there may be no machine insn with given hard
936 registers. */
937 recog_memoized (insn);
938 /* Add insn to equiv init insn list if it is necessary.
939 Otherwise reload will not remove this insn if it decides
940 to use the equivalence. */
941 if ((set = single_set (insn)) != NULL_RTX)
942 {
55a2c322
VM
943 dest = SET_DEST (set);
944 if (GET_CODE (dest) == SUBREG)
945 dest = SUBREG_REG (dest);
946 ira_assert (REG_P (dest));
947 regno = REGNO (dest);
e5b0e1ca 948 if (regno >= ira_reg_equiv_len
55a2c322
VM
949 || (ira_reg_equiv[regno].invariant == NULL_RTX
950 && ira_reg_equiv[regno].constant == NULL_RTX))
e5b0e1ca 951 continue; /* regno has no equivalence. */
9771b263 952 ira_assert ((int) reg_equivs->length () > regno);
e5b0e1ca
VM
953 reg_equiv_init (regno)
954 = gen_rtx_INSN_LIST (VOIDmode, insn, reg_equiv_init (regno));
955 }
956 }
15652f68
VM
957 if (ira_use_lra_p)
958 ira_update_equiv_info_by_shuffle_insn (to_regno, from_regno, list->insn);
058e97ec
VM
959 emit_insn (list->insn);
960 mode = ALLOCNO_MODE (list->to);
1756cb66 961 aclass = ALLOCNO_CLASS (list->to);
058e97ec
VM
962 cost = 0;
963 if (ALLOCNO_HARD_REGNO (list->to) < 0)
964 {
965 if (ALLOCNO_HARD_REGNO (list->from) >= 0)
966 {
1756cb66 967 cost = ira_memory_move_cost[mode][aclass][0] * freq;
058e97ec
VM
968 ira_store_cost += cost;
969 }
970 }
971 else if (ALLOCNO_HARD_REGNO (list->from) < 0)
972 {
973 if (ALLOCNO_HARD_REGNO (list->to) >= 0)
974 {
1756cb66 975 cost = ira_memory_move_cost[mode][aclass][0] * freq;
058e97ec
VM
976 ira_load_cost += cost;
977 }
978 }
979 else
980 {
1756cb66
VM
981 ira_init_register_move_cost_if_necessary (mode);
982 cost = ira_register_move_cost[mode][aclass][aclass] * freq;
058e97ec
VM
983 ira_shuffle_cost += cost;
984 }
985 ira_overall_cost += cost;
986 }
987 result = get_insns ();
988 end_sequence ();
989 return result;
990}
991
992/* Generate RTX move insns from move lists attached to basic blocks
993 and edges. */
994static void
995emit_moves (void)
996{
997 basic_block bb;
998 edge_iterator ei;
999 edge e;
49507955 1000 rtx_insn *insns, *tmp, *next;
058e97ec 1001
11cd3bed 1002 FOR_EACH_BB_FN (bb, cfun)
058e97ec
VM
1003 {
1004 if (at_bb_start[bb->index] != NULL)
1005 {
1006 at_bb_start[bb->index] = modify_move_list (at_bb_start[bb->index]);
49507955
EB
1007 insns
1008 = emit_move_list (at_bb_start[bb->index], REG_FREQ_FROM_BB (bb));
058e97ec
VM
1009 tmp = BB_HEAD (bb);
1010 if (LABEL_P (tmp))
1011 tmp = NEXT_INSN (tmp);
1012 if (NOTE_INSN_BASIC_BLOCK_P (tmp))
1013 tmp = NEXT_INSN (tmp);
49507955
EB
1014 /* Make sure to put the location of TMP or a subsequent instruction
1015 to avoid inheriting the location of the previous instruction. */
1016 next = tmp;
1017 while (next && !NONDEBUG_INSN_P (next))
1018 next = NEXT_INSN (next);
1019 if (next)
1020 set_insn_locations (insns, INSN_LOCATION (next));
058e97ec
VM
1021 if (tmp == BB_HEAD (bb))
1022 emit_insn_before (insns, tmp);
49507955 1023 else if (tmp)
058e97ec
VM
1024 emit_insn_after (insns, PREV_INSN (tmp));
1025 else
1026 emit_insn_after (insns, get_last_insn ());
1027 }
1028
1029 if (at_bb_end[bb->index] != NULL)
1030 {
1031 at_bb_end[bb->index] = modify_move_list (at_bb_end[bb->index]);
1032 insns = emit_move_list (at_bb_end[bb->index], REG_FREQ_FROM_BB (bb));
1033 ira_assert (! control_flow_insn_p (BB_END (bb)));
1034 emit_insn_after (insns, BB_END (bb));
1035 }
1036
1037 FOR_EACH_EDGE (e, ei, bb->succs)
1038 {
1039 if (e->aux == NULL)
1040 continue;
1041 ira_assert ((e->flags & EDGE_ABNORMAL) == 0
1042 || ! EDGE_CRITICAL_P (e));
1043 e->aux = modify_move_list ((move_t) e->aux);
1044 insert_insn_on_edge
1045 (emit_move_list ((move_t) e->aux,
1046 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e))),
1047 e);
1048 if (e->src->next_bb != e->dest)
1049 ira_additional_jumps_num++;
1050 }
1051 }
1052}
1053
1054/* Update costs of A and corresponding allocnos on upper levels on the
1055 loop tree from reading (if READ_P) or writing A on an execution
1056 path with FREQ. */
1057static void
1058update_costs (ira_allocno_t a, bool read_p, int freq)
1059{
1060 ira_loop_tree_node_t parent;
1061
1062 for (;;)
1063 {
1064 ALLOCNO_NREFS (a)++;
1065 ALLOCNO_FREQ (a) += freq;
1066 ALLOCNO_MEMORY_COST (a)
1756cb66 1067 += (ira_memory_move_cost[ALLOCNO_MODE (a)][ALLOCNO_CLASS (a)]
058e97ec
VM
1068 [read_p ? 1 : 0] * freq);
1069 if (ALLOCNO_CAP (a) != NULL)
1070 a = ALLOCNO_CAP (a);
1071 else if ((parent = ALLOCNO_LOOP_TREE_NODE (a)->parent) == NULL
1072 || (a = parent->regno_allocno_map[ALLOCNO_REGNO (a)]) == NULL)
1073 break;
1074 }
1075}
1076
1077/* Process moves from LIST with execution FREQ to add ranges, copies,
1078 and modify costs for allocnos involved in the moves. All regnos
1079 living through the list is in LIVE_THROUGH, and the loop tree node
1080 used to find corresponding allocnos is NODE. */
1081static void
1082add_range_and_copies_from_move_list (move_t list, ira_loop_tree_node_t node,
1083 bitmap live_through, int freq)
1084{
1085 int start, n;
1086 unsigned int regno;
1087 move_t move;
a49ae217 1088 ira_allocno_t a;
058e97ec 1089 ira_copy_t cp;
b14151b5 1090 live_range_t r;
058e97ec
VM
1091 bitmap_iterator bi;
1092 HARD_REG_SET hard_regs_live;
1093
1094 if (list == NULL)
1095 return;
1096 n = 0;
1097 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1098 n++;
1099 REG_SET_TO_HARD_REG_SET (hard_regs_live, live_through);
1100 /* This is a trick to guarantee that new ranges is not merged with
1101 the old ones. */
1102 ira_max_point++;
1103 start = ira_max_point;
1104 for (move = list; move != NULL; move = move->next)
1105 {
a49ae217
BS
1106 ira_allocno_t from = move->from;
1107 ira_allocno_t to = move->to;
ac0ab4f7
BS
1108 int nr, i;
1109
058e97ec
VM
1110 bitmap_clear_bit (live_through, ALLOCNO_REGNO (from));
1111 bitmap_clear_bit (live_through, ALLOCNO_REGNO (to));
ac0ab4f7
BS
1112
1113 nr = ALLOCNO_NUM_OBJECTS (to);
1114 for (i = 0; i < nr; i++)
1115 {
1116 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1117 if (OBJECT_CONFLICT_ARRAY (to_obj) == NULL)
1118 {
1119 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1120 fprintf (ira_dump_file, " Allocate conflicts for a%dr%d\n",
1756cb66 1121 ALLOCNO_NUM (to), REGNO (allocno_emit_reg (to)));
ac0ab4f7
BS
1122 ira_allocate_object_conflicts (to_obj, n);
1123 }
1124 }
75f4e3a1
RS
1125 ior_hard_reg_conflicts (from, hard_regs_live);
1126 ior_hard_reg_conflicts (to, hard_regs_live);
ac0ab4f7 1127
058e97ec
VM
1128 update_costs (from, true, freq);
1129 update_costs (to, false, freq);
548a6322 1130 cp = ira_add_allocno_copy (from, to, freq, false, move->insn, NULL);
058e97ec
VM
1131 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1132 fprintf (ira_dump_file, " Adding cp%d:a%dr%d-a%dr%d\n",
1133 cp->num, ALLOCNO_NUM (cp->first),
1756cb66
VM
1134 REGNO (allocno_emit_reg (cp->first)),
1135 ALLOCNO_NUM (cp->second),
1136 REGNO (allocno_emit_reg (cp->second)));
ac0ab4f7
BS
1137
1138 nr = ALLOCNO_NUM_OBJECTS (from);
1139 for (i = 0; i < nr; i++)
058e97ec 1140 {
ac0ab4f7
BS
1141 ira_object_t from_obj = ALLOCNO_OBJECT (from, i);
1142 r = OBJECT_LIVE_RANGES (from_obj);
1143 if (r == NULL || r->finish >= 0)
1144 {
1145 ira_add_live_range_to_object (from_obj, start, ira_max_point);
1146 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1147 fprintf (ira_dump_file,
1148 " Adding range [%d..%d] to allocno a%dr%d\n",
1149 start, ira_max_point, ALLOCNO_NUM (from),
1756cb66 1150 REGNO (allocno_emit_reg (from)));
ac0ab4f7
BS
1151 }
1152 else
1153 {
1154 r->finish = ira_max_point;
1155 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1156 fprintf (ira_dump_file,
1157 " Adding range [%d..%d] to allocno a%dr%d\n",
1158 r->start, ira_max_point, ALLOCNO_NUM (from),
1756cb66 1159 REGNO (allocno_emit_reg (from)));
ac0ab4f7 1160 }
058e97ec 1161 }
ac0ab4f7
BS
1162 ira_max_point++;
1163 nr = ALLOCNO_NUM_OBJECTS (to);
1164 for (i = 0; i < nr; i++)
a174c19c 1165 {
ac0ab4f7
BS
1166 ira_object_t to_obj = ALLOCNO_OBJECT (to, i);
1167 ira_add_live_range_to_object (to_obj, ira_max_point, -1);
a174c19c 1168 }
058e97ec 1169 ira_max_point++;
058e97ec
VM
1170 }
1171 for (move = list; move != NULL; move = move->next)
1172 {
ac0ab4f7
BS
1173 int nr, i;
1174 nr = ALLOCNO_NUM_OBJECTS (move->to);
1175 for (i = 0; i < nr; i++)
058e97ec 1176 {
ac0ab4f7
BS
1177 ira_object_t to_obj = ALLOCNO_OBJECT (move->to, i);
1178 r = OBJECT_LIVE_RANGES (to_obj);
1179 if (r->finish < 0)
1180 {
1181 r->finish = ira_max_point - 1;
1182 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1183 fprintf (ira_dump_file,
1184 " Adding range [%d..%d] to allocno a%dr%d\n",
1185 r->start, r->finish, ALLOCNO_NUM (move->to),
1756cb66 1186 REGNO (allocno_emit_reg (move->to)));
ac0ab4f7 1187 }
058e97ec
VM
1188 }
1189 }
1190 EXECUTE_IF_SET_IN_BITMAP (live_through, FIRST_PSEUDO_REGISTER, regno, bi)
1191 {
a49ae217 1192 ira_allocno_t to;
ac0ab4f7
BS
1193 int nr, i;
1194
058e97ec 1195 a = node->regno_allocno_map[regno];
1756cb66 1196 if ((to = ALLOCNO_EMIT_DATA (a)->mem_optimized_dest) != NULL)
a174c19c 1197 a = to;
ac0ab4f7
BS
1198 nr = ALLOCNO_NUM_OBJECTS (a);
1199 for (i = 0; i < nr; i++)
1200 {
1201 ira_object_t obj = ALLOCNO_OBJECT (a, i);
1202 ira_add_live_range_to_object (obj, start, ira_max_point - 1);
1203 }
a174c19c
VM
1204 if (internal_flag_ira_verbose > 2 && ira_dump_file != NULL)
1205 fprintf
1206 (ira_dump_file,
1207 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1208 start, ira_max_point - 1,
1209 to != NULL ? "upper level" : "",
1756cb66 1210 ALLOCNO_NUM (a), REGNO (allocno_emit_reg (a)));
058e97ec
VM
1211 }
1212}
1213
1214/* Process all move list to add ranges, conflicts, copies, and modify
1215 costs for allocnos involved in the moves. */
1216static void
1217add_ranges_and_copies (void)
1218{
1219 basic_block bb;
1220 edge_iterator ei;
1221 edge e;
1222 ira_loop_tree_node_t node;
1223 bitmap live_through;
1224
1225 live_through = ira_allocate_bitmap ();
11cd3bed 1226 FOR_EACH_BB_FN (bb, cfun)
058e97ec
VM
1227 {
1228 /* It does not matter what loop_tree_node (of source or
1229 destination block) to use for searching allocnos by their
1230 regnos because of subsequent IR flattening. */
1231 node = IRA_BB_NODE (bb)->parent;
bf744527 1232 bitmap_copy (live_through, df_get_live_in (bb));
058e97ec
VM
1233 add_range_and_copies_from_move_list
1234 (at_bb_start[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
bf744527 1235 bitmap_copy (live_through, df_get_live_out (bb));
058e97ec
VM
1236 add_range_and_copies_from_move_list
1237 (at_bb_end[bb->index], node, live_through, REG_FREQ_FROM_BB (bb));
1238 FOR_EACH_EDGE (e, ei, bb->succs)
1239 {
bf744527
SB
1240 bitmap_and (live_through,
1241 df_get_live_in (e->dest), df_get_live_out (bb));
058e97ec
VM
1242 add_range_and_copies_from_move_list
1243 ((move_t) e->aux, node, live_through,
1244 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e)));
1245 }
1246 }
1247 ira_free_bitmap (live_through);
1248}
1249
1250/* The entry function changes code and generates shuffling allocnos on
1251 region borders for the regional (LOOPS_P is TRUE in this case)
1252 register allocation. */
1253void
1254ira_emit (bool loops_p)
1255{
1256 basic_block bb;
070a1983 1257 rtx_insn *insn;
058e97ec
VM
1258 edge_iterator ei;
1259 edge e;
1260 ira_allocno_t a;
1261 ira_allocno_iterator ai;
8b1c6fd7 1262 size_t sz;
058e97ec
VM
1263
1264 FOR_EACH_ALLOCNO (a, ai)
1756cb66 1265 ALLOCNO_EMIT_DATA (a)->reg = regno_reg_rtx[ALLOCNO_REGNO (a)];
058e97ec
VM
1266 if (! loops_p)
1267 return;
8b1c6fd7
DM
1268 sz = sizeof (move_t) * last_basic_block_for_fn (cfun);
1269 at_bb_start = (move_t *) ira_allocate (sz);
1270 memset (at_bb_start, 0, sz);
1271 at_bb_end = (move_t *) ira_allocate (sz);
1272 memset (at_bb_end, 0, sz);
058e97ec
VM
1273 local_allocno_bitmap = ira_allocate_bitmap ();
1274 used_regno_bitmap = ira_allocate_bitmap ();
1275 renamed_regno_bitmap = ira_allocate_bitmap ();
1276 max_regno_before_changing = max_reg_num ();
1277 ira_traverse_loop_tree (true, ira_loop_tree_root, change_loop, NULL);
1278 set_allocno_somewhere_renamed_p ();
1279 ira_free_bitmap (used_regno_bitmap);
1280 ira_free_bitmap (renamed_regno_bitmap);
1281 ira_free_bitmap (local_allocno_bitmap);
ea1c67e6 1282 setup_entered_from_non_parent_p ();
11cd3bed 1283 FOR_EACH_BB_FN (bb, cfun)
058e97ec
VM
1284 {
1285 at_bb_start[bb->index] = NULL;
1286 at_bb_end[bb->index] = NULL;
1287 FOR_EACH_EDGE (e, ei, bb->succs)
fefa31b5 1288 if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
058e97ec
VM
1289 generate_edge_moves (e);
1290 }
1291 allocno_last_set
1292 = (move_t *) ira_allocate (sizeof (move_t) * max_reg_num ());
1293 allocno_last_set_check
1294 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1295 memset (allocno_last_set_check, 0, sizeof (int) * max_reg_num ());
1296 memset (hard_regno_last_set_check, 0, sizeof (hard_regno_last_set_check));
1297 curr_tick = 0;
11cd3bed 1298 FOR_EACH_BB_FN (bb, cfun)
058e97ec 1299 unify_moves (bb, true);
11cd3bed 1300 FOR_EACH_BB_FN (bb, cfun)
058e97ec 1301 unify_moves (bb, false);
9771b263 1302 move_vec.create (ira_allocnos_num);
058e97ec
VM
1303 emit_moves ();
1304 add_ranges_and_copies ();
1305 /* Clean up: */
11cd3bed 1306 FOR_EACH_BB_FN (bb, cfun)
058e97ec
VM
1307 {
1308 free_move_list (at_bb_start[bb->index]);
1309 free_move_list (at_bb_end[bb->index]);
1310 FOR_EACH_EDGE (e, ei, bb->succs)
1311 {
1312 free_move_list ((move_t) e->aux);
1313 e->aux = NULL;
1314 }
1315 }
9771b263 1316 move_vec.release ();
058e97ec
VM
1317 ira_free (allocno_last_set_check);
1318 ira_free (allocno_last_set);
1319 commit_edge_insertions ();
7db7ed3c
VM
1320 /* Fix insn codes. It is necessary to do it before reload because
1321 reload assumes initial insn codes defined. The insn codes can be
1322 invalidated by CFG infrastructure for example in jump
1323 redirection. */
11cd3bed 1324 FOR_EACH_BB_FN (bb, cfun)
7db7ed3c
VM
1325 FOR_BB_INSNS_REVERSE (bb, insn)
1326 if (INSN_P (insn))
1327 recog_memoized (insn);
058e97ec
VM
1328 ira_free (at_bb_end);
1329 ira_free (at_bb_start);
1330}