1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006-2015 Free Software Foundation, Inc.
3 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
5 This file is part of GCC.
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
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
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/>. */
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
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
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.
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.
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.
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. */
70 #include "coretypes.h"
79 #include "hard-reg-set.h"
87 #include "dominance.h"
91 #include "basic-block.h"
100 /* Data used to emit live range split insns and to flattening IR. */
101 ira_emit_data_t ira_allocno_emit_data
;
103 /* Definitions for vectors of pointers. */
104 typedef void *void_p
;
106 /* Pointers to data allocated for allocnos being created during
107 emitting. Usually there are quite few such allocnos because they
108 are created only for resolving loop in register shuffling. */
109 static vec
<void_p
> new_allocno_emit_data_vec
;
111 /* Allocate and initiate the emit data. */
113 ira_initiate_emit_data (void)
116 ira_allocno_iterator ai
;
118 ira_allocno_emit_data
119 = (ira_emit_data_t
) ira_allocate (ira_allocnos_num
120 * sizeof (struct ira_emit_data
));
121 memset (ira_allocno_emit_data
, 0,
122 ira_allocnos_num
* sizeof (struct ira_emit_data
));
123 FOR_EACH_ALLOCNO (a
, ai
)
124 ALLOCNO_ADD_DATA (a
) = ira_allocno_emit_data
+ ALLOCNO_NUM (a
);
125 new_allocno_emit_data_vec
.create (50);
129 /* Free the emit data. */
131 ira_finish_emit_data (void)
135 ira_allocno_iterator ai
;
137 ira_free (ira_allocno_emit_data
);
138 FOR_EACH_ALLOCNO (a
, ai
)
139 ALLOCNO_ADD_DATA (a
) = NULL
;
140 for (;new_allocno_emit_data_vec
.length () != 0;)
142 p
= new_allocno_emit_data_vec
.pop ();
145 new_allocno_emit_data_vec
.release ();
148 /* Create and return a new allocno with given REGNO and
149 LOOP_TREE_NODE. Allocate emit data for it. */
151 create_new_allocno (int regno
, ira_loop_tree_node_t loop_tree_node
)
155 a
= ira_create_allocno (regno
, false, loop_tree_node
);
156 ALLOCNO_ADD_DATA (a
) = ira_allocate (sizeof (struct ira_emit_data
));
157 memset (ALLOCNO_ADD_DATA (a
), 0, sizeof (struct ira_emit_data
));
158 new_allocno_emit_data_vec
.safe_push (ALLOCNO_ADD_DATA (a
));
164 /* See comments below. */
165 typedef struct move
*move_t
;
167 /* The structure represents an allocno move. Both allocnos have the
168 same original regno but different allocation. */
171 /* The allocnos involved in the move. */
172 ira_allocno_t from
, to
;
173 /* The next move in the move sequence. */
175 /* Used for finding dependencies. */
177 /* The size of the following array. */
179 /* Moves on which given move depends on. Dependency can be cyclic.
180 It means we need a temporary to generates the moves. Sequence
181 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
182 B1 are assigned to reg R2 is an example of the cyclic
185 /* First insn generated for the move. */
189 /* Array of moves (indexed by BB index) which should be put at the
190 start/end of the corresponding basic blocks. */
191 static move_t
*at_bb_start
, *at_bb_end
;
193 /* Max regno before renaming some pseudo-registers. For example, the
194 same pseudo-register can be renamed in a loop if its allocation is
195 different outside the loop. */
196 static int max_regno_before_changing
;
198 /* Return new move of allocnos TO and FROM. */
200 create_move (ira_allocno_t to
, ira_allocno_t from
)
204 move
= (move_t
) ira_allocate (sizeof (struct move
));
211 move
->visited_p
= false;
215 /* Free memory for MOVE and its dependencies. */
217 free_move (move_t move
)
219 if (move
->deps
!= NULL
)
220 ira_free (move
->deps
);
224 /* Free memory for list of the moves given by its HEAD. */
226 free_move_list (move_t head
)
230 for (; head
!= NULL
; head
= next
)
237 /* Return TRUE if the move list LIST1 and LIST2 are equal (two
238 moves are equal if they involve the same allocnos). */
240 eq_move_lists_p (move_t list1
, move_t list2
)
242 for (; list1
!= NULL
&& list2
!= NULL
;
243 list1
= list1
->next
, list2
= list2
->next
)
244 if (list1
->from
!= list2
->from
|| list1
->to
!= list2
->to
)
246 return list1
== list2
;
249 /* Print move list LIST into file F. */
251 print_move_list (FILE *f
, move_t list
)
253 for (; list
!= NULL
; list
= list
->next
)
254 fprintf (f
, " a%dr%d->a%dr%d",
255 ALLOCNO_NUM (list
->from
), ALLOCNO_REGNO (list
->from
),
256 ALLOCNO_NUM (list
->to
), ALLOCNO_REGNO (list
->to
));
260 extern void ira_debug_move_list (move_t list
);
262 /* Print move list LIST into stderr. */
264 ira_debug_move_list (move_t list
)
266 print_move_list (stderr
, list
);
269 /* This recursive function changes pseudo-registers in *LOC if it is
270 necessary. The function returns TRUE if a change was done. */
272 change_regs (rtx
*loc
)
274 int i
, regno
, result
= false;
279 if (*loc
== NULL_RTX
)
281 code
= GET_CODE (*loc
);
284 regno
= REGNO (*loc
);
285 if (regno
< FIRST_PSEUDO_REGISTER
)
287 if (regno
>= max_regno_before_changing
)
288 /* It is a shared register which was changed already. */
290 if (ira_curr_regno_allocno_map
[regno
] == NULL
)
292 reg
= allocno_emit_reg (ira_curr_regno_allocno_map
[regno
]);
299 fmt
= GET_RTX_FORMAT (code
);
300 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
303 result
= change_regs (&XEXP (*loc
, i
)) || result
;
304 else if (fmt
[i
] == 'E')
308 for (j
= XVECLEN (*loc
, i
) - 1; j
>= 0; j
--)
309 result
= change_regs (&XVECEXP (*loc
, i
, j
)) || result
;
316 change_regs_in_insn (rtx_insn
**insn_ptr
)
319 bool result
= change_regs (&rtx
);
320 *insn_ptr
= as_a
<rtx_insn
*> (rtx
);
324 /* Attach MOVE to the edge E. The move is attached to the head of the
325 list if HEAD_P is TRUE. */
327 add_to_edge_list (edge e
, move_t move
, bool head_p
)
331 if (head_p
|| e
->aux
== NULL
)
333 move
->next
= (move_t
) e
->aux
;
338 for (last
= (move_t
) e
->aux
; last
->next
!= NULL
; last
= last
->next
)
345 /* Create and return new pseudo-register with the same attributes as
348 ira_create_new_reg (rtx original_reg
)
352 new_reg
= gen_reg_rtx (GET_MODE (original_reg
));
353 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original_reg
);
354 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original_reg
);
355 REG_POINTER (new_reg
) = REG_POINTER (original_reg
);
356 REG_ATTRS (new_reg
) = REG_ATTRS (original_reg
);
357 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
358 fprintf (ira_dump_file
, " Creating newreg=%i from oldreg=%i\n",
359 REGNO (new_reg
), REGNO (original_reg
));
360 ira_expand_reg_equiv ();
364 /* Return TRUE if loop given by SUBNODE inside the loop given by
367 subloop_tree_node_p (ira_loop_tree_node_t subnode
, ira_loop_tree_node_t node
)
369 for (; subnode
!= NULL
; subnode
= subnode
->parent
)
375 /* Set up member `reg' to REG for allocnos which has the same regno as
376 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
378 set_allocno_reg (ira_allocno_t allocno
, rtx reg
)
382 ira_loop_tree_node_t node
;
384 node
= ALLOCNO_LOOP_TREE_NODE (allocno
);
385 for (a
= ira_regno_allocno_map
[ALLOCNO_REGNO (allocno
)];
387 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
388 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a
), node
))
389 ALLOCNO_EMIT_DATA (a
)->reg
= reg
;
390 for (a
= ALLOCNO_CAP (allocno
); a
!= NULL
; a
= ALLOCNO_CAP (a
))
391 ALLOCNO_EMIT_DATA (a
)->reg
= reg
;
392 regno
= ALLOCNO_REGNO (allocno
);
395 if (a
== NULL
|| (a
= ALLOCNO_CAP (a
)) == NULL
)
400 a
= node
->regno_allocno_map
[regno
];
404 if (ALLOCNO_EMIT_DATA (a
)->child_renamed_p
)
406 ALLOCNO_EMIT_DATA (a
)->child_renamed_p
= true;
410 /* Return true if there is an entry to given loop not from its parent
411 (or grandparent) block. For example, it is possible for two
412 adjacent loops inside another loop. */
414 entered_from_non_parent_p (ira_loop_tree_node_t loop_node
)
416 ira_loop_tree_node_t bb_node
, src_loop_node
, parent
;
420 for (bb_node
= loop_node
->children
;
422 bb_node
= bb_node
->next
)
423 if (bb_node
->bb
!= NULL
)
425 FOR_EACH_EDGE (e
, ei
, bb_node
->bb
->preds
)
426 if (e
->src
!= ENTRY_BLOCK_PTR_FOR_FN (cfun
)
427 && (src_loop_node
= IRA_BB_NODE (e
->src
)->parent
) != loop_node
)
429 for (parent
= src_loop_node
->parent
;
431 parent
= parent
->parent
)
432 if (parent
== loop_node
)
435 /* That is an exit from a nested loop -- skip it. */
437 for (parent
= loop_node
->parent
;
439 parent
= parent
->parent
)
440 if (src_loop_node
== parent
)
449 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
451 setup_entered_from_non_parent_p (void)
456 ira_assert (current_loops
!= NULL
);
457 FOR_EACH_VEC_SAFE_ELT (get_loops (cfun
), i
, loop
)
458 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
459 ira_loop_nodes
[i
].entered_from_non_parent_p
460 = entered_from_non_parent_p (&ira_loop_nodes
[i
]);
463 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
464 DEST_ALLOCNO (assigned to memory) can be removed because it does
465 not change value of the destination. One possible reason for this
466 is the situation when SRC_ALLOCNO is not modified in the
467 corresponding loop. */
469 store_can_be_removed_p (ira_allocno_t src_allocno
, ira_allocno_t dest_allocno
)
471 int regno
, orig_regno
;
473 ira_loop_tree_node_t node
;
475 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno
) == NULL
476 && ALLOCNO_CAP_MEMBER (dest_allocno
) == NULL
);
477 orig_regno
= ALLOCNO_REGNO (src_allocno
);
478 regno
= REGNO (allocno_emit_reg (dest_allocno
));
479 for (node
= ALLOCNO_LOOP_TREE_NODE (src_allocno
);
483 a
= node
->regno_allocno_map
[orig_regno
];
484 ira_assert (a
!= NULL
);
485 if (REGNO (allocno_emit_reg (a
)) == (unsigned) regno
)
486 /* We achieved the destination and everything is ok. */
488 else if (bitmap_bit_p (node
->modified_regnos
, orig_regno
))
490 else if (node
->entered_from_non_parent_p
)
491 /* If there is a path from a destination loop block to the
492 source loop header containing basic blocks of non-parents
493 (grandparents) of the source loop, we should have checked
494 modifications of the pseudo on this path too to decide
495 about possibility to remove the store. It could be done by
496 solving a data-flow problem. Unfortunately such global
497 solution would complicate IR flattening. Therefore we just
498 prohibit removal of the store in such complicated case. */
501 /* It is actually a loop entry -- do not remove the store. */
505 /* Generate and attach moves to the edge E. This looks at the final
506 regnos of allocnos living on the edge with the same original regno
507 to figure out when moves should be generated. */
509 generate_edge_moves (edge e
)
511 ira_loop_tree_node_t src_loop_node
, dest_loop_node
;
514 ira_allocno_t src_allocno
, dest_allocno
, *src_map
, *dest_map
;
516 bitmap regs_live_in_dest
, regs_live_out_src
;
518 src_loop_node
= IRA_BB_NODE (e
->src
)->parent
;
519 dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
;
521 if (src_loop_node
== dest_loop_node
)
523 src_map
= src_loop_node
->regno_allocno_map
;
524 dest_map
= dest_loop_node
->regno_allocno_map
;
525 regs_live_in_dest
= df_get_live_in (e
->dest
);
526 regs_live_out_src
= df_get_live_out (e
->src
);
527 EXECUTE_IF_SET_IN_REG_SET (regs_live_in_dest
,
528 FIRST_PSEUDO_REGISTER
, regno
, bi
)
529 if (bitmap_bit_p (regs_live_out_src
, regno
))
531 src_allocno
= src_map
[regno
];
532 dest_allocno
= dest_map
[regno
];
533 if (REGNO (allocno_emit_reg (src_allocno
))
534 == REGNO (allocno_emit_reg (dest_allocno
)))
536 /* Remove unnecessary stores at the region exit. We should do
537 this for readonly memory for sure and this is guaranteed by
538 that we never generate moves on region borders (see
539 checking in function change_loop). */
540 if (ALLOCNO_HARD_REGNO (dest_allocno
) < 0
541 && ALLOCNO_HARD_REGNO (src_allocno
) >= 0
542 && store_can_be_removed_p (src_allocno
, dest_allocno
))
544 ALLOCNO_EMIT_DATA (src_allocno
)->mem_optimized_dest
= dest_allocno
;
545 ALLOCNO_EMIT_DATA (dest_allocno
)->mem_optimized_dest_p
= true;
546 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
547 fprintf (ira_dump_file
, " Remove r%d:a%d->a%d(mem)\n",
548 regno
, ALLOCNO_NUM (src_allocno
),
549 ALLOCNO_NUM (dest_allocno
));
552 move
= create_move (dest_allocno
, src_allocno
);
553 add_to_edge_list (e
, move
, true);
557 /* Bitmap of allocnos local for the current loop. */
558 static bitmap local_allocno_bitmap
;
560 /* This bitmap is used to find that we need to generate and to use a
561 new pseudo-register when processing allocnos with the same original
563 static bitmap used_regno_bitmap
;
565 /* This bitmap contains regnos of allocnos which were renamed locally
566 because the allocnos correspond to disjoint live ranges in loops
567 with a common parent. */
568 static bitmap renamed_regno_bitmap
;
570 /* Change (if necessary) pseudo-registers inside loop given by loop
573 change_loop (ira_loop_tree_node_t node
)
579 ira_allocno_t allocno
, parent_allocno
, *map
;
582 enum reg_class aclass
, pclass
;
583 ira_loop_tree_node_t parent
;
585 if (node
!= ira_loop_tree_root
)
587 ira_assert (current_loops
!= NULL
);
589 if (node
->bb
!= NULL
)
591 FOR_BB_INSNS (node
->bb
, insn
)
592 if (INSN_P (insn
) && change_regs_in_insn (&insn
))
594 df_insn_rescan (insn
);
595 df_notes_rescan (insn
);
600 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
601 fprintf (ira_dump_file
,
602 " Changing RTL for loop %d (header bb%d)\n",
603 node
->loop_num
, node
->loop
->header
->index
);
605 parent
= ira_curr_loop_tree_node
->parent
;
606 map
= parent
->regno_allocno_map
;
607 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node
->border_allocnos
,
610 allocno
= ira_allocnos
[i
];
611 regno
= ALLOCNO_REGNO (allocno
);
612 aclass
= ALLOCNO_CLASS (allocno
);
613 pclass
= ira_pressure_class_translate
[aclass
];
614 parent_allocno
= map
[regno
];
615 ira_assert (regno
< ira_reg_equiv_len
);
616 /* We generate the same hard register move because the
617 reload pass can put an allocno into memory in this case
618 we will have live range splitting. If it does not happen
619 such the same hard register moves will be removed. The
620 worst case when the both allocnos are put into memory by
621 the reload is very rare. */
622 if (parent_allocno
!= NULL
623 && (ALLOCNO_HARD_REGNO (allocno
)
624 == ALLOCNO_HARD_REGNO (parent_allocno
))
625 && (ALLOCNO_HARD_REGNO (allocno
) < 0
626 || (parent
->reg_pressure
[pclass
] + 1
627 <= ira_class_hard_regs_num
[pclass
])
628 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
629 [ALLOCNO_MODE (allocno
)],
630 ALLOCNO_HARD_REGNO (allocno
))
631 /* don't create copies because reload can spill an
632 allocno set by copy although the allocno will not
634 || ira_equiv_no_lvalue_p (regno
)
635 || (pic_offset_table_rtx
!= NULL
636 && (ALLOCNO_REGNO (allocno
)
637 == (int) REGNO (pic_offset_table_rtx
)))))
639 original_reg
= allocno_emit_reg (allocno
);
640 if (parent_allocno
== NULL
641 || (REGNO (allocno_emit_reg (parent_allocno
))
642 == REGNO (original_reg
)))
644 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
645 fprintf (ira_dump_file
, " %i vs parent %i:",
646 ALLOCNO_HARD_REGNO (allocno
),
647 ALLOCNO_HARD_REGNO (parent_allocno
));
648 set_allocno_reg (allocno
, ira_create_new_reg (original_reg
));
652 /* Rename locals: Local allocnos with same regno in different loops
653 might get the different hard register. So we need to change
655 bitmap_and_compl (local_allocno_bitmap
,
656 ira_curr_loop_tree_node
->all_allocnos
,
657 ira_curr_loop_tree_node
->border_allocnos
);
658 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap
, 0, i
, bi
)
660 allocno
= ira_allocnos
[i
];
661 regno
= ALLOCNO_REGNO (allocno
);
662 if (ALLOCNO_CAP_MEMBER (allocno
) != NULL
)
664 used_p
= !bitmap_set_bit (used_regno_bitmap
, regno
);
665 ALLOCNO_EMIT_DATA (allocno
)->somewhere_renamed_p
= true;
668 bitmap_set_bit (renamed_regno_bitmap
, regno
);
669 set_allocno_reg (allocno
, ira_create_new_reg (allocno_emit_reg (allocno
)));
673 /* Process to set up flag somewhere_renamed_p. */
675 set_allocno_somewhere_renamed_p (void)
678 ira_allocno_t allocno
;
679 ira_allocno_iterator ai
;
681 FOR_EACH_ALLOCNO (allocno
, ai
)
683 regno
= ALLOCNO_REGNO (allocno
);
684 if (bitmap_bit_p (renamed_regno_bitmap
, regno
)
685 && REGNO (allocno_emit_reg (allocno
)) == regno
)
686 ALLOCNO_EMIT_DATA (allocno
)->somewhere_renamed_p
= true;
690 /* Return TRUE if move lists on all edges given in vector VEC are
693 eq_edge_move_lists_p (vec
<edge
, va_gc
> *vec
)
698 list
= (move_t
) EDGE_I (vec
, 0)->aux
;
699 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
700 if (! eq_move_lists_p (list
, (move_t
) EDGE_I (vec
, i
)->aux
))
705 /* Look at all entry edges (if START_P) or exit edges of basic block
706 BB and put move lists at the BB start or end if it is possible. In
707 other words, this decreases code duplication of allocno moves. */
709 unify_moves (basic_block bb
, bool start_p
)
714 vec
<edge
, va_gc
> *vec
;
716 vec
= (start_p
? bb
->preds
: bb
->succs
);
717 if (EDGE_COUNT (vec
) == 0 || ! eq_edge_move_lists_p (vec
))
720 list
= (move_t
) e
->aux
;
721 if (! start_p
&& control_flow_insn_p (BB_END (bb
)))
724 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
727 free_move_list ((move_t
) e
->aux
);
731 at_bb_start
[bb
->index
] = list
;
733 at_bb_end
[bb
->index
] = list
;
736 /* Last move (in move sequence being processed) setting up the
737 corresponding hard register. */
738 static move_t hard_regno_last_set
[FIRST_PSEUDO_REGISTER
];
740 /* If the element value is equal to CURR_TICK then the corresponding
741 element in `hard_regno_last_set' is defined and correct. */
742 static int hard_regno_last_set_check
[FIRST_PSEUDO_REGISTER
];
744 /* Last move (in move sequence being processed) setting up the
745 corresponding allocno. */
746 static move_t
*allocno_last_set
;
748 /* If the element value is equal to CURR_TICK then the corresponding
749 element in . `allocno_last_set' is defined and correct. */
750 static int *allocno_last_set_check
;
752 /* Definition of vector of moves. */
754 /* This vec contains moves sorted topologically (depth-first) on their
756 static vec
<move_t
> move_vec
;
758 /* The variable value is used to check correctness of values of
759 elements of arrays `hard_regno_last_set' and
760 `allocno_last_set_check'. */
761 static int curr_tick
;
763 /* This recursive function traverses dependencies of MOVE and produces
764 topological sorting (in depth-first order). */
766 traverse_moves (move_t move
)
772 move
->visited_p
= true;
773 for (i
= move
->deps_num
- 1; i
>= 0; i
--)
774 traverse_moves (move
->deps
[i
]);
775 move_vec
.safe_push (move
);
778 /* Remove unnecessary moves in the LIST, makes topological sorting,
779 and removes cycles on hard reg dependencies by introducing new
780 allocnos assigned to memory and additional moves. It returns the
783 modify_move_list (move_t list
)
785 int i
, n
, nregs
, hard_regno
;
786 ira_allocno_t to
, from
;
787 move_t move
, new_move
, set_move
, first
, last
;
791 /* Create move deps. */
793 for (move
= list
; move
!= NULL
; move
= move
->next
)
796 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
798 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
799 for (i
= 0; i
< nregs
; i
++)
801 hard_regno_last_set
[hard_regno
+ i
] = move
;
802 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
805 for (move
= list
; move
!= NULL
; move
= move
->next
)
809 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
811 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
812 for (n
= i
= 0; i
< nregs
; i
++)
813 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
814 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
815 != ALLOCNO_REGNO (from
)))
817 move
->deps
= (move_t
*) ira_allocate (n
* sizeof (move_t
));
818 for (n
= i
= 0; i
< nregs
; i
++)
819 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
820 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
821 != ALLOCNO_REGNO (from
)))
822 move
->deps
[n
++] = hard_regno_last_set
[hard_regno
+ i
];
826 /* Topological sorting: */
827 move_vec
.truncate (0);
828 for (move
= list
; move
!= NULL
; move
= move
->next
)
829 traverse_moves (move
);
831 for (i
= (int) move_vec
.length () - 1; i
>= 0; i
--)
839 first
= move_vec
.last ();
840 /* Removing cycles: */
842 move_vec
.truncate (0);
843 for (move
= first
; move
!= NULL
; move
= move
->next
)
847 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
849 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
850 for (i
= 0; i
< nregs
; i
++)
851 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
852 && ALLOCNO_HARD_REGNO
853 (hard_regno_last_set
[hard_regno
+ i
]->to
) >= 0)
856 ira_allocno_t new_allocno
;
858 set_move
= hard_regno_last_set
[hard_regno
+ i
];
859 /* It does not matter what loop_tree_node (of TO or
860 FROM) to use for the new allocno because of
861 subsequent IRA internal representation
864 = create_new_allocno (ALLOCNO_REGNO (set_move
->to
),
865 ALLOCNO_LOOP_TREE_NODE (set_move
->to
));
866 ALLOCNO_MODE (new_allocno
) = ALLOCNO_MODE (set_move
->to
);
867 ira_set_allocno_class (new_allocno
,
868 ALLOCNO_CLASS (set_move
->to
));
869 ira_create_allocno_objects (new_allocno
);
870 ALLOCNO_ASSIGNED_P (new_allocno
) = true;
871 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
872 ALLOCNO_EMIT_DATA (new_allocno
)->reg
873 = ira_create_new_reg (allocno_emit_reg (set_move
->to
));
875 /* Make it possibly conflicting with all earlier
876 created allocnos. Cases where temporary allocnos
877 created to remove the cycles are quite rare. */
878 n
= ALLOCNO_NUM_OBJECTS (new_allocno
);
879 gcc_assert (n
== ALLOCNO_NUM_OBJECTS (set_move
->to
));
880 for (j
= 0; j
< n
; j
++)
882 ira_object_t new_obj
= ALLOCNO_OBJECT (new_allocno
, j
);
884 OBJECT_MIN (new_obj
) = 0;
885 OBJECT_MAX (new_obj
) = ira_objects_num
- 1;
888 new_move
= create_move (set_move
->to
, new_allocno
);
889 set_move
->to
= new_allocno
;
890 move_vec
.safe_push (new_move
);
891 ira_move_loops_num
++;
892 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
893 fprintf (ira_dump_file
,
894 " Creating temporary allocno a%dr%d\n",
895 ALLOCNO_NUM (new_allocno
),
896 REGNO (allocno_emit_reg (new_allocno
)));
899 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
901 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
902 for (i
= 0; i
< nregs
; i
++)
904 hard_regno_last_set
[hard_regno
+ i
] = move
;
905 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
908 for (i
= (int) move_vec
.length () - 1; i
>= 0; i
--)
918 /* Generate RTX move insns from the move list LIST. This updates
919 allocation cost using move execution frequency FREQ. */
921 emit_move_list (move_t list
, int freq
)
924 int to_regno
, from_regno
, cost
, regno
;
925 rtx_insn
*result
, *insn
;
928 enum reg_class aclass
;
932 for (; list
!= NULL
; list
= list
->next
)
935 to
= allocno_emit_reg (list
->to
);
936 to_regno
= REGNO (to
);
937 from
= allocno_emit_reg (list
->from
);
938 from_regno
= REGNO (from
);
939 emit_move_insn (to
, from
);
940 list
->insn
= get_insns ();
942 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
944 /* The reload needs to have set up insn codes. If the
945 reload sets up insn codes by itself, it may fail because
946 insns will have hard registers instead of pseudos and
947 there may be no machine insn with given hard
949 recog_memoized (insn
);
950 /* Add insn to equiv init insn list if it is necessary.
951 Otherwise reload will not remove this insn if it decides
952 to use the equivalence. */
953 if ((set
= single_set (insn
)) != NULL_RTX
)
955 dest
= SET_DEST (set
);
956 if (GET_CODE (dest
) == SUBREG
)
957 dest
= SUBREG_REG (dest
);
958 ira_assert (REG_P (dest
));
959 regno
= REGNO (dest
);
960 if (regno
>= ira_reg_equiv_len
961 || (ira_reg_equiv
[regno
].invariant
== NULL_RTX
962 && ira_reg_equiv
[regno
].constant
== NULL_RTX
))
963 continue; /* regno has no equivalence. */
964 ira_assert ((int) reg_equivs
->length () > regno
);
965 reg_equiv_init (regno
)
966 = gen_rtx_INSN_LIST (VOIDmode
, insn
, reg_equiv_init (regno
));
970 ira_update_equiv_info_by_shuffle_insn (to_regno
, from_regno
, list
->insn
);
971 emit_insn (list
->insn
);
972 mode
= ALLOCNO_MODE (list
->to
);
973 aclass
= ALLOCNO_CLASS (list
->to
);
975 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
977 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
979 cost
= ira_memory_move_cost
[mode
][aclass
][0] * freq
;
980 ira_store_cost
+= cost
;
983 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
985 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
987 cost
= ira_memory_move_cost
[mode
][aclass
][0] * freq
;
988 ira_load_cost
+= cost
;
993 ira_init_register_move_cost_if_necessary (mode
);
994 cost
= ira_register_move_cost
[mode
][aclass
][aclass
] * freq
;
995 ira_shuffle_cost
+= cost
;
997 ira_overall_cost
+= cost
;
999 result
= get_insns ();
1004 /* Generate RTX move insns from move lists attached to basic blocks
1012 rtx_insn
*insns
, *tmp
;
1014 FOR_EACH_BB_FN (bb
, cfun
)
1016 if (at_bb_start
[bb
->index
] != NULL
)
1018 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
1019 insns
= emit_move_list (at_bb_start
[bb
->index
],
1020 REG_FREQ_FROM_BB (bb
));
1023 tmp
= NEXT_INSN (tmp
);
1024 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
1025 tmp
= NEXT_INSN (tmp
);
1026 if (tmp
== BB_HEAD (bb
))
1027 emit_insn_before (insns
, tmp
);
1028 else if (tmp
!= NULL_RTX
)
1029 emit_insn_after (insns
, PREV_INSN (tmp
));
1031 emit_insn_after (insns
, get_last_insn ());
1034 if (at_bb_end
[bb
->index
] != NULL
)
1036 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
1037 insns
= emit_move_list (at_bb_end
[bb
->index
], REG_FREQ_FROM_BB (bb
));
1038 ira_assert (! control_flow_insn_p (BB_END (bb
)));
1039 emit_insn_after (insns
, BB_END (bb
));
1042 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1046 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
1047 || ! EDGE_CRITICAL_P (e
));
1048 e
->aux
= modify_move_list ((move_t
) e
->aux
);
1050 (emit_move_list ((move_t
) e
->aux
,
1051 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
1053 if (e
->src
->next_bb
!= e
->dest
)
1054 ira_additional_jumps_num
++;
1059 /* Update costs of A and corresponding allocnos on upper levels on the
1060 loop tree from reading (if READ_P) or writing A on an execution
1063 update_costs (ira_allocno_t a
, bool read_p
, int freq
)
1065 ira_loop_tree_node_t parent
;
1069 ALLOCNO_NREFS (a
)++;
1070 ALLOCNO_FREQ (a
) += freq
;
1071 ALLOCNO_MEMORY_COST (a
)
1072 += (ira_memory_move_cost
[ALLOCNO_MODE (a
)][ALLOCNO_CLASS (a
)]
1073 [read_p
? 1 : 0] * freq
);
1074 if (ALLOCNO_CAP (a
) != NULL
)
1075 a
= ALLOCNO_CAP (a
);
1076 else if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
1077 || (a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
1082 /* Process moves from LIST with execution FREQ to add ranges, copies,
1083 and modify costs for allocnos involved in the moves. All regnos
1084 living through the list is in LIVE_THROUGH, and the loop tree node
1085 used to find corresponding allocnos is NODE. */
1087 add_range_and_copies_from_move_list (move_t list
, ira_loop_tree_node_t node
,
1088 bitmap live_through
, int freq
)
1097 HARD_REG_SET hard_regs_live
;
1102 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
1104 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
1105 /* This is a trick to guarantee that new ranges is not merged with
1108 start
= ira_max_point
;
1109 for (move
= list
; move
!= NULL
; move
= move
->next
)
1111 ira_allocno_t from
= move
->from
;
1112 ira_allocno_t to
= move
->to
;
1115 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
1116 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
1118 nr
= ALLOCNO_NUM_OBJECTS (to
);
1119 for (i
= 0; i
< nr
; i
++)
1121 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
1122 if (OBJECT_CONFLICT_ARRAY (to_obj
) == NULL
)
1124 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1125 fprintf (ira_dump_file
, " Allocate conflicts for a%dr%d\n",
1126 ALLOCNO_NUM (to
), REGNO (allocno_emit_reg (to
)));
1127 ira_allocate_object_conflicts (to_obj
, n
);
1130 ior_hard_reg_conflicts (from
, &hard_regs_live
);
1131 ior_hard_reg_conflicts (to
, &hard_regs_live
);
1133 update_costs (from
, true, freq
);
1134 update_costs (to
, false, freq
);
1135 cp
= ira_add_allocno_copy (from
, to
, freq
, false, move
->insn
, NULL
);
1136 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1137 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
1138 cp
->num
, ALLOCNO_NUM (cp
->first
),
1139 REGNO (allocno_emit_reg (cp
->first
)),
1140 ALLOCNO_NUM (cp
->second
),
1141 REGNO (allocno_emit_reg (cp
->second
)));
1143 nr
= ALLOCNO_NUM_OBJECTS (from
);
1144 for (i
= 0; i
< nr
; i
++)
1146 ira_object_t from_obj
= ALLOCNO_OBJECT (from
, i
);
1147 r
= OBJECT_LIVE_RANGES (from_obj
);
1148 if (r
== NULL
|| r
->finish
>= 0)
1150 ira_add_live_range_to_object (from_obj
, start
, ira_max_point
);
1151 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1152 fprintf (ira_dump_file
,
1153 " Adding range [%d..%d] to allocno a%dr%d\n",
1154 start
, ira_max_point
, ALLOCNO_NUM (from
),
1155 REGNO (allocno_emit_reg (from
)));
1159 r
->finish
= ira_max_point
;
1160 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1161 fprintf (ira_dump_file
,
1162 " Adding range [%d..%d] to allocno a%dr%d\n",
1163 r
->start
, ira_max_point
, ALLOCNO_NUM (from
),
1164 REGNO (allocno_emit_reg (from
)));
1168 nr
= ALLOCNO_NUM_OBJECTS (to
);
1169 for (i
= 0; i
< nr
; i
++)
1171 ira_object_t to_obj
= ALLOCNO_OBJECT (to
, i
);
1172 ira_add_live_range_to_object (to_obj
, ira_max_point
, -1);
1176 for (move
= list
; move
!= NULL
; move
= move
->next
)
1179 nr
= ALLOCNO_NUM_OBJECTS (move
->to
);
1180 for (i
= 0; i
< nr
; i
++)
1182 ira_object_t to_obj
= ALLOCNO_OBJECT (move
->to
, i
);
1183 r
= OBJECT_LIVE_RANGES (to_obj
);
1186 r
->finish
= ira_max_point
- 1;
1187 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1188 fprintf (ira_dump_file
,
1189 " Adding range [%d..%d] to allocno a%dr%d\n",
1190 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
1191 REGNO (allocno_emit_reg (move
->to
)));
1195 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
1200 a
= node
->regno_allocno_map
[regno
];
1201 if ((to
= ALLOCNO_EMIT_DATA (a
)->mem_optimized_dest
) != NULL
)
1203 nr
= ALLOCNO_NUM_OBJECTS (a
);
1204 for (i
= 0; i
< nr
; i
++)
1206 ira_object_t obj
= ALLOCNO_OBJECT (a
, i
);
1207 ira_add_live_range_to_object (obj
, start
, ira_max_point
- 1);
1209 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1212 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1213 start
, ira_max_point
- 1,
1214 to
!= NULL
? "upper level" : "",
1215 ALLOCNO_NUM (a
), REGNO (allocno_emit_reg (a
)));
1219 /* Process all move list to add ranges, conflicts, copies, and modify
1220 costs for allocnos involved in the moves. */
1222 add_ranges_and_copies (void)
1227 ira_loop_tree_node_t node
;
1228 bitmap live_through
;
1230 live_through
= ira_allocate_bitmap ();
1231 FOR_EACH_BB_FN (bb
, cfun
)
1233 /* It does not matter what loop_tree_node (of source or
1234 destination block) to use for searching allocnos by their
1235 regnos because of subsequent IR flattening. */
1236 node
= IRA_BB_NODE (bb
)->parent
;
1237 bitmap_copy (live_through
, df_get_live_in (bb
));
1238 add_range_and_copies_from_move_list
1239 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1240 bitmap_copy (live_through
, df_get_live_out (bb
));
1241 add_range_and_copies_from_move_list
1242 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1243 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1245 bitmap_and (live_through
,
1246 df_get_live_in (e
->dest
), df_get_live_out (bb
));
1247 add_range_and_copies_from_move_list
1248 ((move_t
) e
->aux
, node
, live_through
,
1249 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
1252 ira_free_bitmap (live_through
);
1255 /* The entry function changes code and generates shuffling allocnos on
1256 region borders for the regional (LOOPS_P is TRUE in this case)
1257 register allocation. */
1259 ira_emit (bool loops_p
)
1266 ira_allocno_iterator ai
;
1269 FOR_EACH_ALLOCNO (a
, ai
)
1270 ALLOCNO_EMIT_DATA (a
)->reg
= regno_reg_rtx
[ALLOCNO_REGNO (a
)];
1273 sz
= sizeof (move_t
) * last_basic_block_for_fn (cfun
);
1274 at_bb_start
= (move_t
*) ira_allocate (sz
);
1275 memset (at_bb_start
, 0, sz
);
1276 at_bb_end
= (move_t
*) ira_allocate (sz
);
1277 memset (at_bb_end
, 0, sz
);
1278 local_allocno_bitmap
= ira_allocate_bitmap ();
1279 used_regno_bitmap
= ira_allocate_bitmap ();
1280 renamed_regno_bitmap
= ira_allocate_bitmap ();
1281 max_regno_before_changing
= max_reg_num ();
1282 ira_traverse_loop_tree (true, ira_loop_tree_root
, change_loop
, NULL
);
1283 set_allocno_somewhere_renamed_p ();
1284 ira_free_bitmap (used_regno_bitmap
);
1285 ira_free_bitmap (renamed_regno_bitmap
);
1286 ira_free_bitmap (local_allocno_bitmap
);
1287 setup_entered_from_non_parent_p ();
1288 FOR_EACH_BB_FN (bb
, cfun
)
1290 at_bb_start
[bb
->index
] = NULL
;
1291 at_bb_end
[bb
->index
] = NULL
;
1292 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1293 if (e
->dest
!= EXIT_BLOCK_PTR_FOR_FN (cfun
))
1294 generate_edge_moves (e
);
1297 = (move_t
*) ira_allocate (sizeof (move_t
) * max_reg_num ());
1298 allocno_last_set_check
1299 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1300 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
1301 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
1303 FOR_EACH_BB_FN (bb
, cfun
)
1304 unify_moves (bb
, true);
1305 FOR_EACH_BB_FN (bb
, cfun
)
1306 unify_moves (bb
, false);
1307 move_vec
.create (ira_allocnos_num
);
1309 add_ranges_and_copies ();
1311 FOR_EACH_BB_FN (bb
, cfun
)
1313 free_move_list (at_bb_start
[bb
->index
]);
1314 free_move_list (at_bb_end
[bb
->index
]);
1315 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1317 free_move_list ((move_t
) e
->aux
);
1321 move_vec
.release ();
1322 ira_free (allocno_last_set_check
);
1323 ira_free (allocno_last_set
);
1324 commit_edge_insertions ();
1325 /* Fix insn codes. It is necessary to do it before reload because
1326 reload assumes initial insn codes defined. The insn codes can be
1327 invalidated by CFG infrastructure for example in jump
1329 FOR_EACH_BB_FN (bb
, cfun
)
1330 FOR_BB_INSNS_REVERSE (bb
, insn
)
1332 recog_memoized (insn
);
1333 ira_free (at_bb_end
);
1334 ira_free (at_bb_start
);