1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006, 2007, 2008
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"
48 typedef struct move
*move_t
;
50 /* The structure represents an allocno move. Both allocnos have the
51 same origional regno but different allocation. */
54 /* The allocnos involved in the move. */
55 ira_allocno_t from
, to
;
56 /* The next move in the move sequence. */
58 /* Used for finding dependencies. */
60 /* The size of the following array. */
62 /* Moves on which given move depends on. Dependency can be cyclic.
63 It means we need a temporary to generates the moves. Sequence
64 A1->A2, B1->B2 where A1 and B2 are assigned to reg R1 and A2 and
65 B1 are assigned to reg R2 is an example of the cyclic
68 /* First insn generated for the move. */
72 /* Array of moves (indexed by BB index) which should be put at the
73 start/end of the corresponding basic blocks. */
74 static move_t
*at_bb_start
, *at_bb_end
;
76 /* Max regno before renaming some pseudo-registers. For example, the
77 same pseudo-register can be renamed in a loop if its allocation is
78 different outside the loop. */
79 static int max_regno_before_changing
;
81 /* Return new move of allocnos TO and FROM. */
83 create_move (ira_allocno_t to
, ira_allocno_t from
)
87 move
= (move_t
) ira_allocate (sizeof (struct move
));
93 move
->insn
= NULL_RTX
;
94 move
->visited_p
= false;
98 /* Free memory for MOVE and its dependencies. */
100 free_move (move_t move
)
102 if (move
->deps
!= NULL
)
103 ira_free (move
->deps
);
107 /* Free memory for list of the moves given by its HEAD. */
109 free_move_list (move_t head
)
113 for (; head
!= NULL
; head
= next
)
120 /* Return TRUE if the the move list LIST1 and LIST2 are equal (two
121 moves are equal if they involve the same allocnos). */
123 eq_move_lists_p (move_t list1
, move_t list2
)
125 for (; list1
!= NULL
&& list2
!= NULL
;
126 list1
= list1
->next
, list2
= list2
->next
)
127 if (list1
->from
!= list2
->from
|| list1
->to
!= list2
->to
)
129 return list1
== list2
;
132 /* This recursive function changes pseudo-registers in *LOC if it is
133 necessary. The function returns TRUE if a change was done. */
135 change_regs (rtx
*loc
)
137 int i
, regno
, result
= false;
142 if (*loc
== NULL_RTX
)
144 code
= GET_CODE (*loc
);
147 regno
= REGNO (*loc
);
148 if (regno
< FIRST_PSEUDO_REGISTER
)
150 if (regno
>= max_regno_before_changing
)
151 /* It is a shared register which was changed already. */
153 if (ira_curr_regno_allocno_map
[regno
] == NULL
)
155 reg
= ALLOCNO_REG (ira_curr_regno_allocno_map
[regno
]);
162 fmt
= GET_RTX_FORMAT (code
);
163 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
166 result
= change_regs (&XEXP (*loc
, i
)) || result
;
167 else if (fmt
[i
] == 'E')
171 for (j
= XVECLEN (*loc
, i
) - 1; j
>= 0; j
--)
172 result
= change_regs (&XVECEXP (*loc
, i
, j
)) || result
;
178 /* Attach MOVE to the edge E. The move is attached to the head of the
179 list if HEAD_P is TRUE. */
181 add_to_edge_list (edge e
, move_t move
, bool head_p
)
185 if (head_p
|| e
->aux
== NULL
)
187 move
->next
= (move_t
) e
->aux
;
192 for (last
= (move_t
) e
->aux
; last
->next
!= NULL
; last
= last
->next
)
199 /* Create and return new pseudo-register with the same attributes as
202 create_new_reg (rtx original_reg
)
206 new_reg
= gen_reg_rtx (GET_MODE (original_reg
));
207 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original_reg
);
208 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original_reg
);
209 REG_POINTER (new_reg
) = REG_POINTER (original_reg
);
210 REG_ATTRS (new_reg
) = REG_ATTRS (original_reg
);
211 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
212 fprintf (ira_dump_file
, " Creating newreg=%i from oldreg=%i\n",
213 REGNO (new_reg
), REGNO (original_reg
));
217 /* Return TRUE if loop given by SUBNODE inside the loop given by
220 subloop_tree_node_p (ira_loop_tree_node_t subnode
, ira_loop_tree_node_t node
)
222 for (; subnode
!= NULL
; subnode
= subnode
->parent
)
228 /* Set up member `reg' to REG for allocnos which has the same regno as
229 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
231 set_allocno_reg (ira_allocno_t allocno
, rtx reg
)
235 ira_loop_tree_node_t node
;
237 node
= ALLOCNO_LOOP_TREE_NODE (allocno
);
238 for (a
= ira_regno_allocno_map
[ALLOCNO_REGNO (allocno
)];
240 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
241 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a
), node
))
242 ALLOCNO_REG (a
) = reg
;
243 for (a
= ALLOCNO_CAP (allocno
); a
!= NULL
; a
= ALLOCNO_CAP (a
))
244 ALLOCNO_REG (a
) = reg
;
245 regno
= ALLOCNO_REGNO (allocno
);
248 if (a
== NULL
|| (a
= ALLOCNO_CAP (a
)) == NULL
)
253 a
= node
->regno_allocno_map
[regno
];
257 if (ALLOCNO_CHILD_RENAMED_P (a
))
259 ALLOCNO_CHILD_RENAMED_P (a
) = true;
263 /* Return true if there is an entry to given loop not from its parent
264 (or grandparent) block. For example, it is possible for two
265 adjacent loops inside another loop. */
267 entered_from_non_parent_p (ira_loop_tree_node_t loop_node
)
269 ira_loop_tree_node_t bb_node
, src_loop_node
, parent
;
273 for (bb_node
= loop_node
->children
; bb_node
!= NULL
; bb_node
= bb_node
->next
)
274 if (bb_node
->bb
!= NULL
)
276 FOR_EACH_EDGE (e
, ei
, bb_node
->bb
->preds
)
277 if (e
->src
!= ENTRY_BLOCK_PTR
278 && (src_loop_node
= IRA_BB_NODE (e
->src
)->parent
) != loop_node
)
280 for (parent
= src_loop_node
->parent
;
282 parent
= parent
->parent
)
283 if (parent
== loop_node
)
286 /* That is an exit from a nested loop -- skip it. */
288 for (parent
= loop_node
->parent
;
290 parent
= parent
->parent
)
291 if (src_loop_node
== parent
)
300 /* Set up ENTERED_FROM_NON_PARENT_P for each loop region. */
302 setup_entered_from_non_parent_p (void)
307 for (i
= 0; VEC_iterate (loop_p
, ira_loops
.larray
, i
, loop
); i
++)
308 if (ira_loop_nodes
[i
].regno_allocno_map
!= NULL
)
309 ira_loop_nodes
[i
].entered_from_non_parent_p
310 = entered_from_non_parent_p (&ira_loop_nodes
[i
]);
313 /* Return TRUE if move of SRC_ALLOCNO (assigned to hard register) to
314 DEST_ALLOCNO (assigned to memory) can be removed beacuse it does
315 not change value of the destination. One possible reason for this
316 is the situation when SRC_ALLOCNO is not modified in the
317 corresponding loop. */
319 store_can_be_removed_p (ira_allocno_t src_allocno
, ira_allocno_t dest_allocno
)
321 int regno
, orig_regno
;
323 ira_loop_tree_node_t node
;
325 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno
) == NULL
326 && ALLOCNO_CAP_MEMBER (dest_allocno
) == NULL
);
327 orig_regno
= ALLOCNO_REGNO (src_allocno
);
328 regno
= REGNO (ALLOCNO_REG (dest_allocno
));
329 for (node
= ALLOCNO_LOOP_TREE_NODE (src_allocno
);
333 a
= node
->regno_allocno_map
[orig_regno
];
334 ira_assert (a
!= NULL
);
335 if (REGNO (ALLOCNO_REG (a
)) == (unsigned) regno
)
336 /* We achieved the destination and everything is ok. */
338 else if (bitmap_bit_p (node
->modified_regnos
, orig_regno
))
340 else if (node
->entered_from_non_parent_p
)
341 /* If there is a path from a destination loop block to the
342 source loop header containing basic blocks of non-parents
343 (grandparents) of the source loop, we should have checked
344 modifications of the pseudo on this path too to decide
345 about possibility to remove the store. It could be done by
346 solving a data-flow problem. Unfortunately such global
347 solution would complicate IR flattening. Therefore we just
348 prohibit removal of the store in such complicated case. */
354 /* Generate and attach moves to the edge E. This looks at the final
355 regnos of allocnos living on the edge with the same original regno
356 to figure out when moves should be generated. */
358 generate_edge_moves (edge e
)
360 ira_loop_tree_node_t src_loop_node
, dest_loop_node
;
363 ira_allocno_t src_allocno
, dest_allocno
, *src_map
, *dest_map
;
366 src_loop_node
= IRA_BB_NODE (e
->src
)->parent
;
367 dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
;
369 if (src_loop_node
== dest_loop_node
)
371 src_map
= src_loop_node
->regno_allocno_map
;
372 dest_map
= dest_loop_node
->regno_allocno_map
;
373 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e
->dest
),
374 FIRST_PSEUDO_REGISTER
, regno
, bi
)
375 if (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
))
377 src_allocno
= src_map
[regno
];
378 dest_allocno
= dest_map
[regno
];
379 if (REGNO (ALLOCNO_REG (src_allocno
))
380 == REGNO (ALLOCNO_REG (dest_allocno
)))
382 /* Remove unnecessary stores at the region exit. We should do
383 this for readonly memory for sure and this is guaranteed by
384 that we never generate moves on region borders (see
385 checking ira_reg_equiv_invariant_p in function
387 if (ALLOCNO_HARD_REGNO (dest_allocno
) < 0
388 && ALLOCNO_HARD_REGNO (src_allocno
) >= 0
389 && store_can_be_removed_p (src_allocno
, dest_allocno
))
391 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno
) = dest_allocno
;
392 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno
) = true;
393 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
394 fprintf (ira_dump_file
, " Remove r%d:a%d->a%d(mem)\n",
395 regno
, ALLOCNO_NUM (src_allocno
),
396 ALLOCNO_NUM (dest_allocno
));
399 move
= create_move (dest_allocno
, src_allocno
);
400 add_to_edge_list (e
, move
, true);
404 /* Bitmap of allocnos local for the current loop. */
405 static bitmap local_allocno_bitmap
;
407 /* This bitmap is used to find that we need to generate and to use a
408 new pseudo-register when processing allocnos with the same original
410 static bitmap used_regno_bitmap
;
412 /* This bitmap contains regnos of allocnos which were renamed locally
413 because the allocnos correspond to disjoint live ranges in loops
414 with a common parent. */
415 static bitmap renamed_regno_bitmap
;
417 /* Change (if necessary) pseudo-registers inside loop given by loop
420 change_loop (ira_loop_tree_node_t node
)
426 ira_allocno_t allocno
, parent_allocno
, *map
;
427 rtx insn
, original_reg
;
428 enum reg_class cover_class
;
429 ira_loop_tree_node_t parent
;
431 if (node
!= ira_loop_tree_root
)
434 if (node
->bb
!= NULL
)
436 FOR_BB_INSNS (node
->bb
, insn
)
437 if (INSN_P (insn
) && change_regs (&insn
))
439 df_insn_rescan (insn
);
440 df_notes_rescan (insn
);
445 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
446 fprintf (ira_dump_file
,
447 " Changing RTL for loop %d (header bb%d)\n",
448 node
->loop
->num
, node
->loop
->header
->index
);
450 parent
= ira_curr_loop_tree_node
->parent
;
451 map
= parent
->regno_allocno_map
;
452 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node
->border_allocnos
,
455 allocno
= ira_allocnos
[i
];
456 regno
= ALLOCNO_REGNO (allocno
);
457 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
458 parent_allocno
= map
[regno
];
459 ira_assert (regno
< ira_reg_equiv_len
);
460 /* We generate the same hard register move because the
461 reload pass can put an allocno into memory in this case
462 we will have live range splitting. If it does not happen
463 such the same hard register moves will be removed. The
464 worst case when the both allocnos are put into memory by
465 the reload is very rare. */
466 if (parent_allocno
!= NULL
467 && (ALLOCNO_HARD_REGNO (allocno
)
468 == ALLOCNO_HARD_REGNO (parent_allocno
))
469 && (ALLOCNO_HARD_REGNO (allocno
) < 0
470 || (parent
->reg_pressure
[cover_class
] + 1
471 <= ira_available_class_regs
[cover_class
])
472 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
473 [ALLOCNO_MODE (allocno
)],
474 ALLOCNO_HARD_REGNO (allocno
))
475 /* don't create copies because reload can spill an
476 allocno set by copy although the allocno will not
478 || ira_reg_equiv_invariant_p
[regno
]
479 || ira_reg_equiv_const
[regno
] != NULL_RTX
))
481 original_reg
= ALLOCNO_REG (allocno
);
482 if (parent_allocno
== NULL
483 || REGNO (ALLOCNO_REG (parent_allocno
)) == REGNO (original_reg
))
485 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
486 fprintf (ira_dump_file
, " %i vs parent %i:",
487 ALLOCNO_HARD_REGNO (allocno
),
488 ALLOCNO_HARD_REGNO (parent_allocno
));
489 set_allocno_reg (allocno
, create_new_reg (original_reg
));
493 /* Rename locals: Local allocnos with same regno in different loops
494 might get the different hard register. So we need to change
496 bitmap_and_compl (local_allocno_bitmap
,
497 ira_curr_loop_tree_node
->all_allocnos
,
498 ira_curr_loop_tree_node
->border_allocnos
);
499 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap
, 0, i
, bi
)
501 allocno
= ira_allocnos
[i
];
502 regno
= ALLOCNO_REGNO (allocno
);
503 if (ALLOCNO_CAP_MEMBER (allocno
) != NULL
)
505 used_p
= bitmap_bit_p (used_regno_bitmap
, regno
);
506 bitmap_set_bit (used_regno_bitmap
, regno
);
507 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
510 bitmap_set_bit (renamed_regno_bitmap
, regno
);
511 set_allocno_reg (allocno
, create_new_reg (ALLOCNO_REG (allocno
)));
515 /* Process to set up flag somewhere_renamed_p. */
517 set_allocno_somewhere_renamed_p (void)
520 ira_allocno_t allocno
;
521 ira_allocno_iterator ai
;
523 FOR_EACH_ALLOCNO (allocno
, ai
)
525 regno
= ALLOCNO_REGNO (allocno
);
526 if (bitmap_bit_p (renamed_regno_bitmap
, regno
)
527 && REGNO (ALLOCNO_REG (allocno
)) == regno
)
528 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
532 /* Return TRUE if move lists on all edges given in vector VEC are
535 eq_edge_move_lists_p (VEC(edge
,gc
) *vec
)
540 list
= (move_t
) EDGE_I (vec
, 0)->aux
;
541 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
542 if (! eq_move_lists_p (list
, (move_t
) EDGE_I (vec
, i
)->aux
))
547 /* Look at all entry edges (if START_P) or exit edges of basic block
548 BB and put move lists at the BB start or end if it is possible. In
549 other words, this decreases code duplication of allocno moves. */
551 unify_moves (basic_block bb
, bool start_p
)
558 vec
= (start_p
? bb
->preds
: bb
->succs
);
559 if (EDGE_COUNT (vec
) == 0 || ! eq_edge_move_lists_p (vec
))
562 list
= (move_t
) e
->aux
;
563 if (! start_p
&& control_flow_insn_p (BB_END (bb
)))
566 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
569 free_move_list ((move_t
) e
->aux
);
573 at_bb_start
[bb
->index
] = list
;
575 at_bb_end
[bb
->index
] = list
;
578 /* Last move (in move sequence being processed) setting up the
579 corresponding hard register. */
580 static move_t hard_regno_last_set
[FIRST_PSEUDO_REGISTER
];
582 /* If the element value is equal to CURR_TICK then the corresponding
583 element in `hard_regno_last_set' is defined and correct. */
584 static int hard_regno_last_set_check
[FIRST_PSEUDO_REGISTER
];
586 /* Last move (in move sequence being processed) setting up the
587 corresponding allocno. */
588 static move_t
*allocno_last_set
;
590 /* If the element value is equal to CURR_TICK then the corresponding
591 element in . `allocno_last_set' is defined and correct. */
592 static int *allocno_last_set_check
;
594 /* Definition of vector of moves. */
596 DEF_VEC_ALLOC_P(move_t
, heap
);
598 /* This vec contains moves sorted topologically (depth-first) on their
600 static VEC(move_t
,heap
) *move_vec
;
602 /* The variable value is used to check correctness of values of
603 elements of arrays `hard_regno_last_set' and
604 `allocno_last_set_check'. */
605 static int curr_tick
;
607 /* This recursive function traverses dependencies of MOVE and produces
608 topological sorting (in depth-first order). */
610 traverse_moves (move_t move
)
616 move
->visited_p
= true;
617 for (i
= move
->deps_num
- 1; i
>= 0; i
--)
618 traverse_moves (move
->deps
[i
]);
619 VEC_safe_push (move_t
, heap
, move_vec
, move
);
622 /* Remove unnecessary moves in the LIST, makes topological sorting,
623 and removes cycles on hard reg dependencies by introducing new
624 allocnos assigned to memory and additional moves. It returns the
627 modify_move_list (move_t list
)
629 int i
, n
, nregs
, hard_regno
;
630 ira_allocno_t to
, from
, new_allocno
;
631 move_t move
, new_move
, set_move
, first
, last
;
635 /* Creat move deps. */
637 for (move
= list
; move
!= NULL
; move
= move
->next
)
640 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
642 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
643 for (i
= 0; i
< nregs
; i
++)
645 hard_regno_last_set
[hard_regno
+ i
] = move
;
646 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
649 for (move
= list
; move
!= NULL
; move
= move
->next
)
653 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
655 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
656 for (n
= i
= 0; i
< nregs
; i
++)
657 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
658 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
659 != ALLOCNO_REGNO (from
)))
661 move
->deps
= (move_t
*) ira_allocate (n
* sizeof (move_t
));
662 for (n
= i
= 0; i
< nregs
; i
++)
663 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
664 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
665 != ALLOCNO_REGNO (from
)))
666 move
->deps
[n
++] = hard_regno_last_set
[hard_regno
+ i
];
670 /* Toplogical sorting: */
671 VEC_truncate (move_t
, move_vec
, 0);
672 for (move
= list
; move
!= NULL
; move
= move
->next
)
673 traverse_moves (move
);
675 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
677 move
= VEC_index (move_t
, move_vec
, i
);
683 first
= VEC_last (move_t
, move_vec
);
684 /* Removing cycles: */
686 VEC_truncate (move_t
, move_vec
, 0);
687 for (move
= first
; move
!= NULL
; move
= move
->next
)
691 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
693 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
694 for (i
= 0; i
< nregs
; i
++)
695 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
696 && ALLOCNO_HARD_REGNO
697 (hard_regno_last_set
[hard_regno
+ i
]->to
) >= 0)
699 set_move
= hard_regno_last_set
[hard_regno
+ i
];
700 /* It does not matter what loop_tree_node (of TO or
701 FROM) to use for the new allocno because of
702 subsequent IRA internal representation
705 = ira_create_allocno (ALLOCNO_REGNO (set_move
->to
), false,
706 ALLOCNO_LOOP_TREE_NODE (set_move
->to
));
707 ALLOCNO_MODE (new_allocno
) = ALLOCNO_MODE (set_move
->to
);
708 ira_set_allocno_cover_class
709 (new_allocno
, ALLOCNO_COVER_CLASS (set_move
->to
));
710 ALLOCNO_ASSIGNED_P (new_allocno
) = true;
711 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
712 ALLOCNO_REG (new_allocno
)
713 = create_new_reg (ALLOCNO_REG (set_move
->to
));
714 ALLOCNO_CONFLICT_ID (new_allocno
) = ALLOCNO_NUM (new_allocno
);
715 /* Make it possibly conflicting with all earlier
716 created allocnos. Cases where temporary allocnos
717 created to remove the cycles are quite rare. */
718 ALLOCNO_MIN (new_allocno
) = 0;
719 ALLOCNO_MAX (new_allocno
) = ira_allocnos_num
- 1;
720 new_move
= create_move (set_move
->to
, new_allocno
);
721 set_move
->to
= new_allocno
;
722 VEC_safe_push (move_t
, heap
, move_vec
, new_move
);
723 ira_move_loops_num
++;
724 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
725 fprintf (ira_dump_file
,
726 " Creating temporary allocno a%dr%d\n",
727 ALLOCNO_NUM (new_allocno
),
728 REGNO (ALLOCNO_REG (new_allocno
)));
731 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
733 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
734 for (i
= 0; i
< nregs
; i
++)
736 hard_regno_last_set
[hard_regno
+ i
] = move
;
737 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
740 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
742 move
= VEC_index (move_t
, move_vec
, i
);
750 /* Generate RTX move insns from the move list LIST. This updates
751 allocation cost using move execution frequency FREQ. */
753 emit_move_list (move_t list
, int freq
)
757 enum machine_mode mode
;
758 enum reg_class cover_class
;
761 for (; list
!= NULL
; list
= list
->next
)
764 emit_move_insn (ALLOCNO_REG (list
->to
), ALLOCNO_REG (list
->from
));
765 list
->insn
= get_insns ();
767 /* The reload needs to have set up insn codes. If the reload
768 sets up insn codes by itself, it may fail because insns will
769 have hard registers instead of pseudos and there may be no
770 machine insn with given hard registers. */
771 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
772 recog_memoized (insn
);
773 emit_insn (list
->insn
);
774 mode
= ALLOCNO_MODE (list
->to
);
775 cover_class
= ALLOCNO_COVER_CLASS (list
->to
);
777 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
779 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
781 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
782 ira_store_cost
+= cost
;
785 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
787 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
789 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
790 ira_load_cost
+= cost
;
795 cost
= ira_register_move_cost
[mode
][cover_class
][cover_class
] * freq
;
796 ira_shuffle_cost
+= cost
;
798 ira_overall_cost
+= cost
;
800 result
= get_insns ();
805 /* Generate RTX move insns from move lists attached to basic blocks
817 if (at_bb_start
[bb
->index
] != NULL
)
819 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
820 insns
= emit_move_list (at_bb_start
[bb
->index
],
821 REG_FREQ_FROM_BB (bb
));
824 tmp
= NEXT_INSN (tmp
);
825 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
826 tmp
= NEXT_INSN (tmp
);
827 if (tmp
== BB_HEAD (bb
))
828 emit_insn_before (insns
, tmp
);
829 else if (tmp
!= NULL_RTX
)
830 emit_insn_after (insns
, PREV_INSN (tmp
));
832 emit_insn_after (insns
, get_last_insn ());
835 if (at_bb_end
[bb
->index
] != NULL
)
837 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
838 insns
= emit_move_list (at_bb_end
[bb
->index
], REG_FREQ_FROM_BB (bb
));
839 ira_assert (! control_flow_insn_p (BB_END (bb
)));
840 emit_insn_after (insns
, BB_END (bb
));
843 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
847 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
848 || ! EDGE_CRITICAL_P (e
));
849 e
->aux
= modify_move_list ((move_t
) e
->aux
);
851 (emit_move_list ((move_t
) e
->aux
,
852 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
854 if (e
->src
->next_bb
!= e
->dest
)
855 ira_additional_jumps_num
++;
860 /* Update costs of A and corresponding allocnos on upper levels on the
861 loop tree from reading (if READ_P) or writing A on an execution
864 update_costs (ira_allocno_t a
, bool read_p
, int freq
)
866 ira_loop_tree_node_t parent
;
871 ALLOCNO_FREQ (a
) += freq
;
872 ALLOCNO_MEMORY_COST (a
)
873 += (ira_memory_move_cost
[ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)]
874 [read_p
? 1 : 0] * freq
);
875 if (ALLOCNO_CAP (a
) != NULL
)
877 else if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
878 || (a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
883 /* Process moves from LIST with execution FREQ to add ranges, copies,
884 and modify costs for allocnos involved in the moves. All regnos
885 living through the list is in LIVE_THROUGH, and the loop tree node
886 used to find corresponding allocnos is NODE. */
888 add_range_and_copies_from_move_list (move_t list
, ira_loop_tree_node_t node
,
889 bitmap live_through
, int freq
)
894 ira_allocno_t to
, from
, a
;
896 allocno_live_range_t r
;
898 HARD_REG_SET hard_regs_live
;
903 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
905 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
906 /* This is a trick to guarantee that new ranges is not merged with
909 start
= ira_max_point
;
910 for (move
= list
; move
!= NULL
; move
= move
->next
)
914 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to
) == NULL
)
916 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
917 fprintf (ira_dump_file
, " Allocate conflicts for a%dr%d\n",
918 ALLOCNO_NUM (to
), REGNO (ALLOCNO_REG (to
)));
919 ira_allocate_allocno_conflicts (to
, n
);
921 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
922 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
923 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from
), hard_regs_live
);
924 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to
), hard_regs_live
);
925 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from
),
927 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to
), hard_regs_live
);
928 update_costs (from
, true, freq
);
929 update_costs (to
, false, freq
);
930 cp
= ira_add_allocno_copy (from
, to
, freq
, false, move
->insn
, NULL
);
931 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
932 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
933 cp
->num
, ALLOCNO_NUM (cp
->first
),
934 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
935 REGNO (ALLOCNO_REG (cp
->second
)));
936 r
= ALLOCNO_LIVE_RANGES (from
);
937 if (r
== NULL
|| r
->finish
>= 0)
939 ALLOCNO_LIVE_RANGES (from
)
940 = ira_create_allocno_live_range (from
, start
, ira_max_point
, r
);
941 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
942 fprintf (ira_dump_file
,
943 " Adding range [%d..%d] to allocno a%dr%d\n",
944 start
, ira_max_point
, ALLOCNO_NUM (from
),
945 REGNO (ALLOCNO_REG (from
)));
948 r
->finish
= ira_max_point
;
950 ALLOCNO_LIVE_RANGES (to
)
951 = ira_create_allocno_live_range (to
, ira_max_point
, -1,
952 ALLOCNO_LIVE_RANGES (to
));
955 for (move
= list
; move
!= NULL
; move
= move
->next
)
957 r
= ALLOCNO_LIVE_RANGES (move
->to
);
960 r
->finish
= ira_max_point
- 1;
961 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
962 fprintf (ira_dump_file
,
963 " Adding range [%d..%d] to allocno a%dr%d\n",
964 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
965 REGNO (ALLOCNO_REG (move
->to
)));
968 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
970 a
= node
->regno_allocno_map
[regno
];
971 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
)
973 ALLOCNO_LIVE_RANGES (a
)
974 = ira_create_allocno_live_range (a
, start
, ira_max_point
- 1,
975 ALLOCNO_LIVE_RANGES (a
));
976 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
979 " Adding range [%d..%d] to live through allocno a%dr%d\n",
980 start
, ira_max_point
- 1, ALLOCNO_NUM (a
),
981 REGNO (ALLOCNO_REG (a
)));
986 /* Process all move list to add ranges, conflicts, copies, and modify
987 costs for allocnos involved in the moves. */
989 add_ranges_and_copies (void)
994 ira_loop_tree_node_t node
;
997 live_through
= ira_allocate_bitmap ();
1000 /* It does not matter what loop_tree_node (of source or
1001 destination block) to use for searching allocnos by their
1002 regnos because of subsequent IR flattening. */
1003 node
= IRA_BB_NODE (bb
)->parent
;
1004 bitmap_copy (live_through
, DF_LR_IN (bb
));
1005 add_range_and_copies_from_move_list
1006 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1007 bitmap_copy (live_through
, DF_LR_OUT (bb
));
1008 add_range_and_copies_from_move_list
1009 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
1010 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1012 bitmap_and (live_through
, DF_LR_IN (e
->dest
), DF_LR_OUT (bb
));
1013 add_range_and_copies_from_move_list
1014 ((move_t
) e
->aux
, node
, live_through
,
1015 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
1018 ira_free_bitmap (live_through
);
1021 /* The entry function changes code and generates shuffling allocnos on
1022 region borders for the regional (LOOPS_P is TRUE in this case)
1023 register allocation. */
1025 ira_emit (bool loops_p
)
1032 ira_allocno_iterator ai
;
1034 FOR_EACH_ALLOCNO (a
, ai
)
1035 ALLOCNO_REG (a
) = regno_reg_rtx
[ALLOCNO_REGNO (a
)];
1038 at_bb_start
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
1039 memset (at_bb_start
, 0, sizeof (move_t
) * last_basic_block
);
1040 at_bb_end
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
1041 memset (at_bb_end
, 0, sizeof (move_t
) * last_basic_block
);
1042 local_allocno_bitmap
= ira_allocate_bitmap ();
1043 used_regno_bitmap
= ira_allocate_bitmap ();
1044 renamed_regno_bitmap
= ira_allocate_bitmap ();
1045 max_regno_before_changing
= max_reg_num ();
1046 ira_traverse_loop_tree (true, ira_loop_tree_root
, change_loop
, NULL
);
1047 set_allocno_somewhere_renamed_p ();
1048 ira_free_bitmap (used_regno_bitmap
);
1049 ira_free_bitmap (renamed_regno_bitmap
);
1050 ira_free_bitmap (local_allocno_bitmap
);
1051 setup_entered_from_non_parent_p ();
1054 at_bb_start
[bb
->index
] = NULL
;
1055 at_bb_end
[bb
->index
] = NULL
;
1056 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1057 if (e
->dest
!= EXIT_BLOCK_PTR
)
1058 generate_edge_moves (e
);
1061 = (move_t
*) ira_allocate (sizeof (move_t
) * max_reg_num ());
1062 allocno_last_set_check
1063 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
1064 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
1065 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
1068 unify_moves (bb
, true);
1070 unify_moves (bb
, false);
1071 move_vec
= VEC_alloc (move_t
, heap
, ira_allocnos_num
);
1073 add_ranges_and_copies ();
1077 free_move_list (at_bb_start
[bb
->index
]);
1078 free_move_list (at_bb_end
[bb
->index
]);
1079 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1081 free_move_list ((move_t
) e
->aux
);
1085 VEC_free (move_t
, heap
, move_vec
);
1086 ira_free (allocno_last_set_check
);
1087 ira_free (allocno_last_set
);
1088 commit_edge_insertions ();
1089 /* Fix insn codes. It is necessary to do it before reload because
1090 reload assumes initial insn codes defined. The insn codes can be
1091 invalidated by CFG infrastructure for example in jump
1094 FOR_BB_INSNS_REVERSE (bb
, insn
)
1096 recog_memoized (insn
);
1097 ira_free (at_bb_end
);
1098 ira_free (at_bb_start
);