1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Vladimir Makarov <vmakarov@redhat.com>.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
25 #include "coretypes.h"
34 #include "hard-reg-set.h"
35 #include "basic-block.h"
40 #include "tree-pass.h"
47 typedef struct move
*move_t
;
49 /* The structure represents an allocno move. Both allocnos have the
50 same origional regno but different allocation. */
53 /* The allocnos involved in the move. */
54 ira_allocno_t from
, to
;
55 /* The next move in the move sequence. */
57 /* Used for finding dependencies. */
59 /* The size of the following array. */
61 /* Moves on which given move depends on. Dependency can be cyclic.
62 It means we need a temporary to generates the moves. Sequence
63 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
64 B1 are assigned to reg R2 is an example of the cyclic
67 /* First insn generated for the move. */
71 /* Array of moves (indexed by BB index) which should be put at the
72 start/end of the corresponding basic blocks. */
73 static move_t
*at_bb_start
, *at_bb_end
;
75 /* Max regno before renaming some pseudo-registers. For example, the
76 same pseudo-register can be renamed in a loop if its allocation is
77 different outside the loop. */
78 static int max_regno_before_changing
;
80 /* Return new move of allocnos TO and FROM. */
82 create_move (ira_allocno_t to
, ira_allocno_t from
)
86 move
= (move_t
) ira_allocate (sizeof (struct move
));
92 move
->insn
= NULL_RTX
;
93 move
->visited_p
= false;
97 /* Free memory for MOVE and its dependencies. */
99 free_move (move_t move
)
101 if (move
->deps
!= NULL
)
102 ira_free (move
->deps
);
106 /* Free memory for list of the moves given by its HEAD. */
108 free_move_list (move_t head
)
112 for (; head
!= NULL
; head
= next
)
119 /* Return TRUE if the the move list LIST1 and LIST2 are equal (two
120 moves are equal if they involve the same allocnos). */
122 eq_move_lists_p (move_t list1
, move_t list2
)
124 for (; list1
!= NULL
&& list2
!= NULL
;
125 list1
= list1
->next
, list2
= list2
->next
)
126 if (list1
->from
!= list2
->from
|| list1
->to
!= list2
->to
)
128 return list1
== list2
;
131 /* Print move list LIST into file F. */
133 print_move_list (FILE *f
, move_t list
)
135 for (; list
!= NULL
; list
= list
->next
)
136 fprintf (f
, " a%dr%d->a%dr%d",
137 ALLOCNO_NUM (list
->from
), ALLOCNO_REGNO (list
->from
),
138 ALLOCNO_NUM (list
->to
), ALLOCNO_REGNO (list
->to
));
142 extern void ira_debug_move_list (move_t list
);
144 /* Print move list LIST into stderr. */
146 ira_debug_move_list (move_t list
)
148 print_move_list (stderr
, list
);
151 /* This recursive function changes pseudo-registers in *LOC if it is
152 necessary. The function returns TRUE if a change was done. */
154 change_regs (rtx
*loc
)
156 int i
, regno
, result
= false;
161 if (*loc
== NULL_RTX
)
163 code
= GET_CODE (*loc
);
166 regno
= REGNO (*loc
);
167 if (regno
< FIRST_PSEUDO_REGISTER
)
169 if (regno
>= max_regno_before_changing
)
170 /* It is a shared register which was changed already. */
172 if (ira_curr_regno_allocno_map
[regno
] == NULL
)
174 reg
= ALLOCNO_REG (ira_curr_regno_allocno_map
[regno
]);
181 fmt
= GET_RTX_FORMAT (code
);
182 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
185 result
= change_regs (&XEXP (*loc
, i
)) || result
;
186 else if (fmt
[i
] == 'E')
190 for (j
= XVECLEN (*loc
, i
) - 1; j
>= 0; j
--)
191 result
= change_regs (&XVECEXP (*loc
, i
, j
)) || result
;
197 /* Attach MOVE to the edge E. The move is attached to the head of the
198 list if HEAD_P is TRUE. */
200 add_to_edge_list (edge e
, move_t move
, bool head_p
)
204 if (head_p
|| e
->aux
== NULL
)
206 move
->next
= (move_t
) e
->aux
;
211 for (last
= (move_t
) e
->aux
; last
->next
!= NULL
; last
= last
->next
)
218 /* Create and return new pseudo-register with the same attributes as
221 create_new_reg (rtx original_reg
)
225 new_reg
= gen_reg_rtx (GET_MODE (original_reg
));
226 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original_reg
);
227 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original_reg
);
228 REG_POINTER (new_reg
) = REG_POINTER (original_reg
);
229 REG_ATTRS (new_reg
) = REG_ATTRS (original_reg
);
230 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
231 fprintf (ira_dump_file
, " Creating newreg=%i from oldreg=%i\n",
232 REGNO (new_reg
), REGNO (original_reg
));
236 /* Return TRUE if loop given by SUBNODE inside the loop given by
239 subloop_tree_node_p (ira_loop_tree_node_t subnode
, ira_loop_tree_node_t node
)
241 for (; subnode
!= NULL
; subnode
= subnode
->parent
)
247 /* Set up member `reg' to REG for allocnos which has the same regno as
248 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
250 set_allocno_reg (ira_allocno_t allocno
, rtx reg
)
254 ira_loop_tree_node_t node
;
256 node
= ALLOCNO_LOOP_TREE_NODE (allocno
);
257 for (a
= ira_regno_allocno_map
[ALLOCNO_REGNO (allocno
)];
259 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
260 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a
), node
))
261 ALLOCNO_REG (a
) = reg
;
262 for (a
= ALLOCNO_CAP (allocno
); a
!= NULL
; a
= ALLOCNO_CAP (a
))
263 ALLOCNO_REG (a
) = reg
;
264 regno
= ALLOCNO_REGNO (allocno
);
267 if (a
== NULL
|| (a
= ALLOCNO_CAP (a
)) == NULL
)
272 a
= node
->regno_allocno_map
[regno
];
276 if (ALLOCNO_CHILD_RENAMED_P (a
))
278 ALLOCNO_CHILD_RENAMED_P (a
) = true;
282 /* Return true if there is an entry to given loop not from its parent
283 (or grandparent) block. For example, it is possible for two
284 adjacent loops inside another loop. */
286 entered_from_non_parent_p (ira_loop_tree_node_t loop_node
)
288 ira_loop_tree_node_t bb_node
, src_loop_node
, parent
;
292 for (bb_node
= loop_node
->children
; bb_node
!= NULL
; bb_node
= bb_node
->next
)
293 if (bb_node
->bb
!= NULL
)
295 FOR_EACH_EDGE (e
, ei
, bb_node
->bb
->preds
)
296 if (e
->src
!= ENTRY_BLOCK_PTR
297 && (src_loop_node
= IRA_BB_NODE (e
->src
)->parent
) != loop_node
)
299 for (parent
= src_loop_node
->parent
;
301 parent
= parent
->parent
)
302 if (parent
== loop_node
)
305 /* That is an exit from a nested loop -- skip it. */
307 for (parent
= loop_node
->parent
;
309 parent
= parent
->parent
)
310 if (src_loop_node
== parent
)
319 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
321 setup_entered_from_non_parent_p (void)
326 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
327 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
328 ira_loop_nodes
[i
].entered_from_non_parent_p
329 = entered_from_non_parent_p (&ira_loop_nodes
[i
]);
332 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
333 DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
334 not change value of the destination. One possible reason for this
335 is the situation when SRC_ALLOCNO is not modified in the
336 corresponding loop. */
338 store_can_be_removed_p (ira_allocno_t src_allocno
, ira_allocno_t dest_allocno
)
340 int regno
, orig_regno
;
342 ira_loop_tree_node_t node
;
344 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno
) == NULL
345 && ALLOCNO_CAP_MEMBER (dest_allocno
) == NULL
);
346 orig_regno
= ALLOCNO_REGNO (src_allocno
);
347 regno
= REGNO (ALLOCNO_REG (dest_allocno
));
348 for (node
= ALLOCNO_LOOP_TREE_NODE (src_allocno
);
352 a
= node
->regno_allocno_map
[orig_regno
];
353 ira_assert (a
!= NULL
);
354 if (REGNO (ALLOCNO_REG (a
)) == (unsigned) regno
)
355 /* We achieved the destination and everything is ok. */
357 else if (bitmap_bit_p (node
->modified_regnos
, orig_regno
))
359 else if (node
->entered_from_non_parent_p
)
360 /* If there is a path from a destination loop block to the
361 source loop header containing basic blocks of non-parents
362 (grandparents) of the source loop, we should have checked
363 modifications of the pseudo on this path too to decide
364 about possibility to remove the store. It could be done by
365 solving a data-flow problem. Unfortunately such global
366 solution would complicate IR flattening. Therefore we just
367 prohibit removal of the store in such complicated case. */
373 /* Generate and attach moves to the edge E. This looks at the final
374 regnos of allocnos living on the edge with the same original regno
375 to figure out when moves should be generated. */
377 generate_edge_moves (edge e
)
379 ira_loop_tree_node_t src_loop_node
, dest_loop_node
;
382 ira_allocno_t src_allocno
, dest_allocno
, *src_map
, *dest_map
;
385 src_loop_node
= IRA_BB_NODE (e
->src
)->parent
;
386 dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
;
388 if (src_loop_node
== dest_loop_node
)
390 src_map
= src_loop_node
->regno_allocno_map
;
391 dest_map
= dest_loop_node
->regno_allocno_map
;
392 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e
->dest
),
393 FIRST_PSEUDO_REGISTER
, regno
, bi
)
394 if (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
))
396 src_allocno
= src_map
[regno
];
397 dest_allocno
= dest_map
[regno
];
398 if (REGNO (ALLOCNO_REG (src_allocno
))
399 == REGNO (ALLOCNO_REG (dest_allocno
)))
401 /* Remove unnecessary stores at the region exit. We should do
402 this for readonly memory for sure and this is guaranteed by
403 that we never generate moves on region borders (see
404 checking ira_reg_equiv_invariant_p in function
406 if (ALLOCNO_HARD_REGNO (dest_allocno
) < 0
407 && ALLOCNO_HARD_REGNO (src_allocno
) >= 0
408 && store_can_be_removed_p (src_allocno
, dest_allocno
))
410 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno
) = dest_allocno
;
411 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno
) = true;
412 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
413 fprintf (ira_dump_file
, " Remove r%d:a%d->a%d(mem)\n",
414 regno
, ALLOCNO_NUM (src_allocno
),
415 ALLOCNO_NUM (dest_allocno
));
418 move
= create_move (dest_allocno
, src_allocno
);
419 add_to_edge_list (e
, move
, true);
423 /* Bitmap of allocnos local for the current loop. */
424 static bitmap local_allocno_bitmap
;
426 /* This bitmap is used to find that we need to generate and to use a
427 new pseudo-register when processing allocnos with the same original
429 static bitmap used_regno_bitmap
;
431 /* This bitmap contains regnos of allocnos which were renamed locally
432 because the allocnos correspond to disjoint live ranges in loops
433 with a common parent. */
434 static bitmap renamed_regno_bitmap
;
436 /* Change (if necessary) pseudo-registers inside loop given by loop
439 change_loop (ira_loop_tree_node_t node
)
445 ira_allocno_t allocno
, parent_allocno
, *map
;
446 rtx insn
, original_reg
;
447 enum reg_class cover_class
;
448 ira_loop_tree_node_t parent
;
450 if (node
!= ira_loop_tree_root
)
453 if (node
->bb
!= NULL
)
455 FOR_BB_INSNS (node
->bb
, insn
)
456 if (INSN_P (insn
) && change_regs (&insn
))
458 df_insn_rescan (insn
);
459 df_notes_rescan (insn
);
464 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
465 fprintf (ira_dump_file
,
466 " Changing RTL for loop %d (header bb%d)\n",
467 node
->loop
->num
, node
->loop
->header
->index
);
469 parent
= ira_curr_loop_tree_node
->parent
;
470 map
= parent
->regno_allocno_map
;
471 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node
->border_allocnos
,
474 allocno
= ira_allocnos
[i
];
475 regno
= ALLOCNO_REGNO (allocno
);
476 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
477 parent_allocno
= map
[regno
];
478 ira_assert (regno
< ira_reg_equiv_len
);
479 /* We generate the same hard register move because the
480 reload pass can put an allocno into memory in this case
481 we will have live range splitting. If it does not happen
482 such the same hard register moves will be removed. The
483 worst case when the both allocnos are put into memory by
484 the reload is very rare. */
485 if (parent_allocno
!= NULL
486 && (ALLOCNO_HARD_REGNO (allocno
)
487 == ALLOCNO_HARD_REGNO (parent_allocno
))
488 && (ALLOCNO_HARD_REGNO (allocno
) < 0
489 || (parent
->reg_pressure
[cover_class
] + 1
490 <= ira_available_class_regs
[cover_class
])
491 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
492 [ALLOCNO_MODE (allocno
)],
493 ALLOCNO_HARD_REGNO (allocno
))
494 /* don't create copies because reload can spill an
495 allocno set by copy although the allocno will not
497 || ira_reg_equiv_invariant_p
[regno
]
498 || ira_reg_equiv_const
[regno
] != NULL_RTX
))
500 original_reg
= ALLOCNO_REG (allocno
);
501 if (parent_allocno
== NULL
502 || REGNO (ALLOCNO_REG (parent_allocno
)) == REGNO (original_reg
))
504 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
505 fprintf (ira_dump_file
, " %i vs parent %i:",
506 ALLOCNO_HARD_REGNO (allocno
),
507 ALLOCNO_HARD_REGNO (parent_allocno
));
508 set_allocno_reg (allocno
, create_new_reg (original_reg
));
512 /* Rename locals: Local allocnos with same regno in different loops
513 might get the different hard register. So we need to change
515 bitmap_and_compl (local_allocno_bitmap
,
516 ira_curr_loop_tree_node
->all_allocnos
,
517 ira_curr_loop_tree_node
->border_allocnos
);
518 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap
, 0, i
, bi
)
520 allocno
= ira_allocnos
[i
];
521 regno
= ALLOCNO_REGNO (allocno
);
522 if (ALLOCNO_CAP_MEMBER (allocno
) != NULL
)
524 used_p
= bitmap_bit_p (used_regno_bitmap
, regno
);
525 bitmap_set_bit (used_regno_bitmap
, regno
);
526 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
529 bitmap_set_bit (renamed_regno_bitmap
, regno
);
530 set_allocno_reg (allocno
, create_new_reg (ALLOCNO_REG (allocno
)));
534 /* Process to set up flag somewhere_renamed_p. */
536 set_allocno_somewhere_renamed_p (void)
539 ira_allocno_t allocno
;
540 ira_allocno_iterator ai
;
542 FOR_EACH_ALLOCNO (allocno
, ai
)
544 regno
= ALLOCNO_REGNO (allocno
);
545 if (bitmap_bit_p (renamed_regno_bitmap
, regno
)
546 && REGNO (ALLOCNO_REG (allocno
)) == regno
)
547 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
551 /* Return TRUE if move lists on all edges given in vector VEC are
554 eq_edge_move_lists_p (VEC(edge
,gc
) *vec
)
559 list
= (move_t
) EDGE_I (vec
, 0)->aux
;
560 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
561 if (! eq_move_lists_p (list
, (move_t
) EDGE_I (vec
, i
)->aux
))
566 /* Look at all entry edges (if START_P) or exit edges of basic block
567 BB and put move lists at the BB start or end if it is possible. In
568 other words, this decreases code duplication of allocno moves. */
570 unify_moves (basic_block bb
, bool start_p
)
577 vec
= (start_p
? bb
->preds
: bb
->succs
);
578 if (EDGE_COUNT (vec
) == 0 || ! eq_edge_move_lists_p (vec
))
581 list
= (move_t
) e
->aux
;
582 if (! start_p
&& control_flow_insn_p (BB_END (bb
)))
585 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
588 free_move_list ((move_t
) e
->aux
);
592 at_bb_start
[bb
->index
] = list
;
594 at_bb_end
[bb
->index
] = list
;
597 /* Last move (in move sequence being processed) setting up the
598 corresponding hard register. */
599 static move_t hard_regno_last_set
[FIRST_PSEUDO_REGISTER
];
601 /* If the element value is equal to CURR_TICK then the corresponding
602 element in `hard_regno_last_set' is defined and correct. */
603 static int hard_regno_last_set_check
[FIRST_PSEUDO_REGISTER
];
605 /* Last move (in move sequence being processed) setting up the
606 corresponding allocno. */
607 static move_t
*allocno_last_set
;
609 /* If the element value is equal to CURR_TICK then the corresponding
610 element in . `allocno_last_set' is defined and correct. */
611 static int *allocno_last_set_check
;
613 /* Definition of vector of moves. */
615 DEF_VEC_ALLOC_P(move_t
, heap
);
617 /* This vec contains moves sorted topologically (depth-first) on their
619 static VEC(move_t
,heap
) *move_vec
;
621 /* The variable value is used to check correctness of values of
622 elements of arrays `hard_regno_last_set' and
623 `allocno_last_set_check'. */
624 static int curr_tick
;
626 /* This recursive function traverses dependencies of MOVE and produces
627 topological sorting (in depth-first order). */
629 traverse_moves (move_t move
)
635 move
->visited_p
= true;
636 for (i
= move
->deps_num
- 1; i
>= 0; i
--)
637 traverse_moves (move
->deps
[i
]);
638 VEC_safe_push (move_t
, heap
, move_vec
, move
);
641 /* Remove unnecessary moves in the LIST, makes topological sorting,
642 and removes cycles on hard reg dependencies by introducing new
643 allocnos assigned to memory and additional moves. It returns the
646 modify_move_list (move_t list
)
648 int i
, n
, nregs
, hard_regno
;
649 ira_allocno_t to
, from
;
650 move_t move
, new_move
, set_move
, first
, last
;
654 /* Creat move deps. */
656 for (move
= list
; move
!= NULL
; move
= move
->next
)
659 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
661 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
662 for (i
= 0; i
< nregs
; i
++)
664 hard_regno_last_set
[hard_regno
+ i
] = move
;
665 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
668 for (move
= list
; move
!= NULL
; move
= move
->next
)
672 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
674 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
675 for (n
= i
= 0; i
< nregs
; i
++)
676 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
677 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
678 != ALLOCNO_REGNO (from
)))
680 move
->deps
= (move_t
*) ira_allocate (n
* sizeof (move_t
));
681 for (n
= i
= 0; i
< nregs
; i
++)
682 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
683 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
684 != ALLOCNO_REGNO (from
)))
685 move
->deps
[n
++] = hard_regno_last_set
[hard_regno
+ i
];
689 /* Toplogical sorting: */
690 VEC_truncate (move_t
, move_vec
, 0);
691 for (move
= list
; move
!= NULL
; move
= move
->next
)
692 traverse_moves (move
);
694 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
696 move
= VEC_index (move_t
, move_vec
, i
);
702 first
= VEC_last (move_t
, move_vec
);
703 /* Removing cycles: */
705 VEC_truncate (move_t
, move_vec
, 0);
706 for (move
= first
; move
!= NULL
; move
= move
->next
)
710 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
712 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
713 for (i
= 0; i
< nregs
; i
++)
714 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
715 && ALLOCNO_HARD_REGNO
716 (hard_regno_last_set
[hard_regno
+ i
]->to
) >= 0)
718 ira_allocno_t new_allocno
;
719 ira_object_t new_obj
;
721 set_move
= hard_regno_last_set
[hard_regno
+ i
];
722 /* It does not matter what loop_tree_node (of TO or
723 FROM) to use for the new allocno because of
724 subsequent IRA internal representation
727 = ira_create_allocno (ALLOCNO_REGNO (set_move
->to
), false,
728 ALLOCNO_LOOP_TREE_NODE (set_move
->to
));
729 ALLOCNO_MODE (new_allocno
) = ALLOCNO_MODE (set_move
->to
);
730 ira_set_allocno_cover_class
731 (new_allocno
, ALLOCNO_COVER_CLASS (set_move
->to
));
732 ira_create_allocno_object (new_allocno
);
733 ALLOCNO_ASSIGNED_P (new_allocno
) = true;
734 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
735 ALLOCNO_REG (new_allocno
)
736 = create_new_reg (ALLOCNO_REG (set_move
->to
));
738 new_obj
= ALLOCNO_OBJECT (new_allocno
);
740 /* Make it possibly conflicting with all earlier
741 created allocnos. Cases where temporary allocnos
742 created to remove the cycles are quite rare. */
743 OBJECT_MIN (new_obj
) = 0;
744 OBJECT_MAX (new_obj
) = ira_objects_num
- 1;
745 new_move
= create_move (set_move
->to
, new_allocno
);
746 set_move
->to
= new_allocno
;
747 VEC_safe_push (move_t
, heap
, move_vec
, new_move
);
748 ira_move_loops_num
++;
749 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
750 fprintf (ira_dump_file
,
751 " Creating temporary allocno a%dr%d\n",
752 ALLOCNO_NUM (new_allocno
),
753 REGNO (ALLOCNO_REG (new_allocno
)));
756 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
758 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
759 for (i
= 0; i
< nregs
; i
++)
761 hard_regno_last_set
[hard_regno
+ i
] = move
;
762 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
765 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
767 move
= VEC_index (move_t
, move_vec
, i
);
775 /* Generate RTX move insns from the move list LIST. This updates
776 allocation cost using move execution frequency FREQ. */
778 emit_move_list (move_t list
, int freq
)
782 enum machine_mode mode
;
783 enum reg_class cover_class
;
786 for (; list
!= NULL
; list
= list
->next
)
789 emit_move_insn (ALLOCNO_REG (list
->to
), ALLOCNO_REG (list
->from
));
790 list
->insn
= get_insns ();
792 /* The reload needs to have set up insn codes. If the reload
793 sets up insn codes by itself, it may fail because insns will
794 have hard registers instead of pseudos and there may be no
795 machine insn with given hard registers. */
796 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
797 recog_memoized (insn
);
798 emit_insn (list
->insn
);
799 mode
= ALLOCNO_MODE (list
->to
);
800 cover_class
= ALLOCNO_COVER_CLASS (list
->to
);
802 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
804 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
806 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
807 ira_store_cost
+= cost
;
810 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
812 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
814 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
815 ira_load_cost
+= cost
;
820 cost
= (ira_get_register_move_cost (mode
, cover_class
, cover_class
)
822 ira_shuffle_cost
+= cost
;
824 ira_overall_cost
+= cost
;
826 result
= get_insns ();
831 /* Generate RTX move insns from move lists attached to basic blocks
843 if (at_bb_start
[bb
->index
] != NULL
)
845 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
846 insns
= emit_move_list (at_bb_start
[bb
->index
],
847 REG_FREQ_FROM_BB (bb
));
850 tmp
= NEXT_INSN (tmp
);
851 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
852 tmp
= NEXT_INSN (tmp
);
853 if (tmp
== BB_HEAD (bb
))
854 emit_insn_before (insns
, tmp
);
855 else if (tmp
!= NULL_RTX
)
856 emit_insn_after (insns
, PREV_INSN (tmp
));
858 emit_insn_after (insns
, get_last_insn ());
861 if (at_bb_end
[bb
->index
] != NULL
)
863 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
864 insns
= emit_move_list (at_bb_end
[bb
->index
], REG_FREQ_FROM_BB (bb
));
865 ira_assert (! control_flow_insn_p (BB_END (bb
)));
866 emit_insn_after (insns
, BB_END (bb
));
869 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
873 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
874 || ! EDGE_CRITICAL_P (e
));
875 e
->aux
= modify_move_list ((move_t
) e
->aux
);
877 (emit_move_list ((move_t
) e
->aux
,
878 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
880 if (e
->src
->next_bb
!= e
->dest
)
881 ira_additional_jumps_num
++;
886 /* Update costs of A and corresponding allocnos on upper levels on the
887 loop tree from reading (if READ_P) or writing A on an execution
890 update_costs (ira_allocno_t a
, bool read_p
, int freq
)
892 ira_loop_tree_node_t parent
;
897 ALLOCNO_FREQ (a
) += freq
;
898 ALLOCNO_MEMORY_COST (a
)
899 += (ira_memory_move_cost
[ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)]
900 [read_p
? 1 : 0] * freq
);
901 if (ALLOCNO_CAP (a
) != NULL
)
903 else if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
904 || (a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
909 /* Process moves from LIST with execution FREQ to add ranges, copies,
910 and modify costs for allocnos involved in the moves. All regnos
911 living through the list is in LIVE_THROUGH, and the loop tree node
912 used to find corresponding allocnos is NODE. */
914 add_range_and_copies_from_move_list (move_t list
, ira_loop_tree_node_t node
,
915 bitmap live_through
, int freq
)
924 HARD_REG_SET hard_regs_live
;
929 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
931 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
932 /* This is a trick to guarantee that new ranges is not merged with
935 start
= ira_max_point
;
936 for (move
= list
; move
!= NULL
; move
= move
->next
)
938 ira_allocno_t from
= move
->from
;
939 ira_allocno_t to
= move
->to
;
940 ira_object_t from_obj
= ALLOCNO_OBJECT (from
);
941 ira_object_t to_obj
= ALLOCNO_OBJECT (to
);
942 if (OBJECT_CONFLICT_ARRAY (to_obj
) == NULL
)
944 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
945 fprintf (ira_dump_file
, " Allocate conflicts for a%dr%d\n",
946 ALLOCNO_NUM (to
), REGNO (ALLOCNO_REG (to
)));
947 ira_allocate_object_conflicts (to_obj
, n
);
949 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
950 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
951 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (from_obj
), hard_regs_live
);
952 IOR_HARD_REG_SET (OBJECT_CONFLICT_HARD_REGS (to_obj
), hard_regs_live
);
953 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (from_obj
), hard_regs_live
);
954 IOR_HARD_REG_SET (OBJECT_TOTAL_CONFLICT_HARD_REGS (to_obj
), hard_regs_live
);
955 update_costs (from
, true, freq
);
956 update_costs (to
, false, freq
);
957 cp
= ira_add_allocno_copy (from
, to
, freq
, false, move
->insn
, NULL
);
958 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
959 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
960 cp
->num
, ALLOCNO_NUM (cp
->first
),
961 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
962 REGNO (ALLOCNO_REG (cp
->second
)));
963 r
= ALLOCNO_LIVE_RANGES (from
);
964 if (r
== NULL
|| r
->finish
>= 0)
966 ALLOCNO_LIVE_RANGES (from
)
967 = ira_create_allocno_live_range (from
, start
, ira_max_point
, r
);
968 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
969 fprintf (ira_dump_file
,
970 " Adding range [%d..%d] to allocno a%dr%d\n",
971 start
, ira_max_point
, ALLOCNO_NUM (from
),
972 REGNO (ALLOCNO_REG (from
)));
976 r
->finish
= ira_max_point
;
977 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
978 fprintf (ira_dump_file
,
979 " Adding range [%d..%d] to allocno a%dr%d\n",
980 r
->start
, ira_max_point
, ALLOCNO_NUM (from
),
981 REGNO (ALLOCNO_REG (from
)));
984 ALLOCNO_LIVE_RANGES (to
)
985 = ira_create_allocno_live_range (to
, ira_max_point
, -1,
986 ALLOCNO_LIVE_RANGES (to
));
989 for (move
= list
; move
!= NULL
; move
= move
->next
)
991 r
= ALLOCNO_LIVE_RANGES (move
->to
);
994 r
->finish
= ira_max_point
- 1;
995 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
996 fprintf (ira_dump_file
,
997 " Adding range [%d..%d] to allocno a%dr%d\n",
998 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
999 REGNO (ALLOCNO_REG (move
->to
)));
1002 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
1005 a
= node
->regno_allocno_map
[regno
];
1006 if ((to
= ALLOCNO_MEM_OPTIMIZED_DEST (a
)) != NULL
)
1008 ALLOCNO_LIVE_RANGES (a
)
1009 = ira_create_allocno_live_range (a
, start
, ira_max_point
- 1,
1010 ALLOCNO_LIVE_RANGES (a
));
1011 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
1014 " Adding range [%d..%d] to live through %s allocno a%dr%d\n",
1015 start
, ira_max_point
- 1,
1016 to
!= NULL
? "upper level" : "",
1017 ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
1021 /* Process all move list to add ranges, conflicts, copies, and modify
1022 costs for allocnos involved in the moves. */
1024 add_ranges_and_copies (void)
1029 ira_loop_tree_node_t node
;
1030 bitmap live_through
;
1032 live_through
= ira_allocate_bitmap ();
1035 /* It does not matter what loop_tree_node (of source or
1036 destination block) to use for searching allocnos by their
1037 regnos because of subsequent IR flattening. */
1038 node
= IRA_BB_NODE (bb
)->parent
;
1039 bitmap_copy (live_through
, DF_LR_IN (bb
));
1040 add_range_and_copies_from_move_list
1041 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1042 bitmap_copy (live_through
, DF_LR_OUT (bb
));
1043 add_range_and_copies_from_move_list
1044 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1045 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1047 bitmap_and (live_through
, DF_LR_IN (e
->dest
), DF_LR_OUT (bb
));
1048 add_range_and_copies_from_move_list
1049 ((move_t
) e
->aux
, node
, live_through
,
1050 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
1053 ira_free_bitmap (live_through
);
1056 /* The entry function changes code and generates shuffling allocnos on
1057 region borders for the regional (LOOPS_P is TRUE in this case)
1058 register allocation. */
1060 ira_emit (bool loops_p
)
1067 ira_allocno_iterator ai
;
1069 FOR_EACH_ALLOCNO (a
, ai
)
1070 ALLOCNO_REG (a
) = regno_reg_rtx
[ALLOCNO_REGNO (a
)];
1073 at_bb_start
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
1074 memset (at_bb_start
, 0, sizeof (move_t
) * last_basic_block
);
1075 at_bb_end
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
1076 memset (at_bb_end
, 0, sizeof (move_t
) * last_basic_block
);
1077 local_allocno_bitmap
= ira_allocate_bitmap ();
1078 used_regno_bitmap
= ira_allocate_bitmap ();
1079 renamed_regno_bitmap
= ira_allocate_bitmap ();
1080 max_regno_before_changing
= max_reg_num ();
1081 ira_traverse_loop_tree (true, ira_loop_tree_root
, change_loop
, NULL
);
1082 set_allocno_somewhere_renamed_p ();
1083 ira_free_bitmap (used_regno_bitmap
);
1084 ira_free_bitmap (renamed_regno_bitmap
);
1085 ira_free_bitmap (local_allocno_bitmap
);
1086 setup_entered_from_non_parent_p ();
1089 at_bb_start
[bb
->index
] = NULL
;
1090 at_bb_end
[bb
->index
] = NULL
;
1091 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1092 if (e
->dest
!= EXIT_BLOCK_PTR
)
1093 generate_edge_moves (e
);
1096 = (move_t
*) ira_allocate (sizeof (move_t
) * max_reg_num ());
1097 allocno_last_set_check
1098 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1099 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
1100 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
1103 unify_moves (bb
, true);
1105 unify_moves (bb
, false);
1106 move_vec
= VEC_alloc (move_t
, heap
, ira_allocnos_num
);
1108 add_ranges_and_copies ();
1112 free_move_list (at_bb_start
[bb
->index
]);
1113 free_move_list (at_bb_end
[bb
->index
]);
1114 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1116 free_move_list ((move_t
) e
->aux
);
1120 VEC_free (move_t
, heap
, move_vec
);
1121 ira_free (allocno_last_set_check
);
1122 ira_free (allocno_last_set
);
1123 commit_edge_insertions ();
1124 /* Fix insn codes. It is necessary to do it before reload because
1125 reload assumes initial insn codes defined. The insn codes can be
1126 invalidated by CFG infrastructure for example in jump
1129 FOR_BB_INSNS_REVERSE (bb
, insn
)
1131 recog_memoized (insn
);
1132 ira_free (at_bb_end
);
1133 ira_free (at_bb_start
);