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;
141 if (*loc
== NULL_RTX
)
143 code
= GET_CODE (*loc
);
146 regno
= REGNO (*loc
);
147 if (regno
< FIRST_PSEUDO_REGISTER
)
149 if (regno
>= max_regno_before_changing
)
150 /* It is a shared register which was changed already. */
152 if (ira_curr_regno_allocno_map
[regno
] == NULL
)
154 *loc
= ALLOCNO_REG (ira_curr_regno_allocno_map
[regno
]);
158 fmt
= GET_RTX_FORMAT (code
);
159 for (i
= GET_RTX_LENGTH (code
) - 1; i
>= 0; i
--)
162 result
= change_regs (&XEXP (*loc
, i
)) || result
;
163 else if (fmt
[i
] == 'E')
167 for (j
= XVECLEN (*loc
, i
) - 1; j
>= 0; j
--)
168 result
= change_regs (&XVECEXP (*loc
, i
, j
)) || result
;
174 /* Attach MOVE to the edge E. The move is attached to the head of the
175 list if HEAD_P is TRUE. */
177 add_to_edge_list (edge e
, move_t move
, bool head_p
)
181 if (head_p
|| e
->aux
== NULL
)
183 move
->next
= (move_t
) e
->aux
;
188 for (last
= (move_t
) e
->aux
; last
->next
!= NULL
; last
= last
->next
)
195 /* Create and return new pseudo-register with the same attributes as
198 create_new_reg (rtx original_reg
)
202 new_reg
= gen_reg_rtx (GET_MODE (original_reg
));
203 ORIGINAL_REGNO (new_reg
) = ORIGINAL_REGNO (original_reg
);
204 REG_USERVAR_P (new_reg
) = REG_USERVAR_P (original_reg
);
205 REG_POINTER (new_reg
) = REG_POINTER (original_reg
);
206 REG_ATTRS (new_reg
) = REG_ATTRS (original_reg
);
207 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
208 fprintf (ira_dump_file
, " Creating newreg=%i from oldreg=%i\n",
209 REGNO (new_reg
), REGNO (original_reg
));
213 /* Return TRUE if loop given by SUBNODE inside the loop given by
216 subloop_tree_node_p (ira_loop_tree_node_t subnode
, ira_loop_tree_node_t node
)
218 for (; subnode
!= NULL
; subnode
= subnode
->parent
)
224 /* Set up member `reg' to REG for allocnos which has the same regno as
225 ALLOCNO and which are inside the loop corresponding to ALLOCNO. */
227 set_allocno_reg (ira_allocno_t allocno
, rtx reg
)
231 ira_loop_tree_node_t node
;
233 node
= ALLOCNO_LOOP_TREE_NODE (allocno
);
234 for (a
= ira_regno_allocno_map
[ALLOCNO_REGNO (allocno
)];
236 a
= ALLOCNO_NEXT_REGNO_ALLOCNO (a
))
237 if (subloop_tree_node_p (ALLOCNO_LOOP_TREE_NODE (a
), node
))
238 ALLOCNO_REG (a
) = reg
;
239 for (a
= ALLOCNO_CAP (allocno
); a
!= NULL
; a
= ALLOCNO_CAP (a
))
240 ALLOCNO_REG (a
) = reg
;
241 regno
= ALLOCNO_REGNO (allocno
);
244 if (a
== NULL
|| (a
= ALLOCNO_CAP (a
)) == NULL
)
249 a
= node
->regno_allocno_map
[regno
];
253 if (ALLOCNO_CHILD_RENAMED_P (a
))
255 ALLOCNO_CHILD_RENAMED_P (a
) = true;
259 /* Return TRUE if move of SRC_ALLOCNO to DEST_ALLOCNO does not change
260 value of the destination. One possible reason for this is the
261 situation when SRC_ALLOCNO is not modified in the corresponding
264 not_modified_p (ira_allocno_t src_allocno
, ira_allocno_t dest_allocno
)
266 int regno
, orig_regno
;
268 ira_loop_tree_node_t node
;
270 ira_assert (ALLOCNO_CAP_MEMBER (src_allocno
) == NULL
271 && ALLOCNO_CAP_MEMBER (dest_allocno
) == NULL
);
272 orig_regno
= ALLOCNO_REGNO (src_allocno
);
273 regno
= REGNO (ALLOCNO_REG (dest_allocno
));
274 for (node
= ALLOCNO_LOOP_TREE_NODE (src_allocno
);
277 if ((a
= node
->regno_allocno_map
[orig_regno
]) == NULL
)
279 else if (REGNO (ALLOCNO_REG (a
)) == (unsigned) regno
)
281 else if (bitmap_bit_p (node
->modified_regnos
, orig_regno
))
286 /* Generate and attach moves to the edge E. This looks at the final
287 regnos of allocnos living on the edge with the same original regno
288 to figure out when moves should be generated. */
290 generate_edge_moves (edge e
)
292 ira_loop_tree_node_t src_loop_node
, dest_loop_node
;
295 ira_allocno_t src_allocno
, dest_allocno
, *src_map
, *dest_map
;
298 src_loop_node
= IRA_BB_NODE (e
->src
)->parent
;
299 dest_loop_node
= IRA_BB_NODE (e
->dest
)->parent
;
301 if (src_loop_node
== dest_loop_node
)
303 src_map
= src_loop_node
->regno_allocno_map
;
304 dest_map
= dest_loop_node
->regno_allocno_map
;
305 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e
->dest
),
306 FIRST_PSEUDO_REGISTER
, regno
, bi
)
307 if (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
))
309 src_allocno
= src_map
[regno
];
310 dest_allocno
= dest_map
[regno
];
311 if (REGNO (ALLOCNO_REG (src_allocno
))
312 == REGNO (ALLOCNO_REG (dest_allocno
)))
314 /* Remove unnecessary stores at the region exit. We should do
315 this for readonly memory for sure and this is guaranteed by
316 that we never generate moves on region borders (see
317 checking ira_reg_equiv_invariant_p in function
319 if (ALLOCNO_HARD_REGNO (dest_allocno
) < 0
320 && ALLOCNO_HARD_REGNO (src_allocno
) >= 0
321 && not_modified_p (src_allocno
, dest_allocno
))
323 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno
) = dest_allocno
;
324 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno
) = true;
325 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
326 fprintf (ira_dump_file
, " Remove r%d:a%d->a%d(mem)\n",
327 regno
, ALLOCNO_NUM (src_allocno
),
328 ALLOCNO_NUM (dest_allocno
));
331 move
= create_move (dest_allocno
, src_allocno
);
332 add_to_edge_list (e
, move
, true);
336 /* Bitmap of allocnos local for the current loop. */
337 static bitmap local_allocno_bitmap
;
339 /* This bitmap is used to find that we need to generate and to use a
340 new pseudo-register when processing allocnos with the same original
342 static bitmap used_regno_bitmap
;
344 /* This bitmap contains regnos of allocnos which were renamed locally
345 because the allocnos correspond to disjoint live ranges in loops
346 with a common parent. */
347 static bitmap renamed_regno_bitmap
;
349 /* Change (if necessary) pseudo-registers inside loop given by loop
352 change_loop (ira_loop_tree_node_t node
)
358 ira_allocno_t allocno
, parent_allocno
, *map
;
359 rtx insn
, original_reg
;
360 enum reg_class cover_class
;
361 ira_loop_tree_node_t parent
;
363 if (node
!= ira_loop_tree_root
)
366 if (node
->bb
!= NULL
)
368 FOR_BB_INSNS (node
->bb
, insn
)
369 if (INSN_P (insn
) && change_regs (&insn
))
371 df_insn_rescan (insn
);
372 df_notes_rescan (insn
);
377 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
378 fprintf (ira_dump_file
,
379 " Changing RTL for loop %d (header bb%d)\n",
380 node
->loop
->num
, node
->loop
->header
->index
);
382 parent
= ira_curr_loop_tree_node
->parent
;
383 map
= parent
->regno_allocno_map
;
384 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node
->border_allocnos
,
387 allocno
= ira_allocnos
[i
];
388 regno
= ALLOCNO_REGNO (allocno
);
389 cover_class
= ALLOCNO_COVER_CLASS (allocno
);
390 parent_allocno
= map
[regno
];
391 ira_assert (regno
< ira_reg_equiv_len
);
392 /* We generate the same hard register move because the
393 reload pass can put an allocno into memory in this case
394 we will have live range splitting. If it does not happen
395 such the same hard register moves will be removed. The
396 worst case when the both allocnos are put into memory by
397 the reload is very rare. */
398 if (parent_allocno
!= NULL
399 && (ALLOCNO_HARD_REGNO (allocno
)
400 == ALLOCNO_HARD_REGNO (parent_allocno
))
401 && (ALLOCNO_HARD_REGNO (allocno
) < 0
402 || (parent
->reg_pressure
[cover_class
] + 1
403 <= ira_available_class_regs
[cover_class
])
404 || TEST_HARD_REG_BIT (ira_prohibited_mode_move_regs
405 [ALLOCNO_MODE (allocno
)],
406 ALLOCNO_HARD_REGNO (allocno
))
407 /* don't create copies because reload can spill an
408 allocno set by copy although the allocno will not
410 || ira_reg_equiv_invariant_p
[regno
]
411 || ira_reg_equiv_const
[regno
] != NULL_RTX
))
413 original_reg
= ALLOCNO_REG (allocno
);
414 if (parent_allocno
== NULL
415 || REGNO (ALLOCNO_REG (parent_allocno
)) == REGNO (original_reg
))
417 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
418 fprintf (ira_dump_file
, " %i vs parent %i:",
419 ALLOCNO_HARD_REGNO (allocno
),
420 ALLOCNO_HARD_REGNO (parent_allocno
));
421 set_allocno_reg (allocno
, create_new_reg (original_reg
));
425 /* Rename locals: Local allocnos with same regno in different loops
426 might get the different hard register. So we need to change
428 bitmap_and_compl (local_allocno_bitmap
,
429 ira_curr_loop_tree_node
->all_allocnos
,
430 ira_curr_loop_tree_node
->border_allocnos
);
431 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap
, 0, i
, bi
)
433 allocno
= ira_allocnos
[i
];
434 regno
= ALLOCNO_REGNO (allocno
);
435 if (ALLOCNO_CAP_MEMBER (allocno
) != NULL
)
437 used_p
= bitmap_bit_p (used_regno_bitmap
, regno
);
438 bitmap_set_bit (used_regno_bitmap
, regno
);
439 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
442 bitmap_set_bit (renamed_regno_bitmap
, regno
);
443 set_allocno_reg (allocno
, create_new_reg (ALLOCNO_REG (allocno
)));
447 /* Process to set up flag somewhere_renamed_p. */
449 set_allocno_somewhere_renamed_p (void)
452 ira_allocno_t allocno
;
453 ira_allocno_iterator ai
;
455 FOR_EACH_ALLOCNO (allocno
, ai
)
457 regno
= ALLOCNO_REGNO (allocno
);
458 if (bitmap_bit_p (renamed_regno_bitmap
, regno
)
459 && REGNO (ALLOCNO_REG (allocno
)) == regno
)
460 ALLOCNO_SOMEWHERE_RENAMED_P (allocno
) = true;
464 /* Return TRUE if move lists on all edges given in vector VEC are
467 eq_edge_move_lists_p (VEC(edge
,gc
) *vec
)
472 list
= (move_t
) EDGE_I (vec
, 0)->aux
;
473 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
474 if (! eq_move_lists_p (list
, (move_t
) EDGE_I (vec
, i
)->aux
))
479 /* Look at all entry edges (if START_P) or exit edges of basic block
480 BB and put move lists at the BB start or end if it is possible. In
481 other words, this decreases code duplication of allocno moves. */
483 unify_moves (basic_block bb
, bool start_p
)
490 vec
= (start_p
? bb
->preds
: bb
->succs
);
491 if (EDGE_COUNT (vec
) == 0 || ! eq_edge_move_lists_p (vec
))
494 list
= (move_t
) e
->aux
;
495 if (! start_p
&& control_flow_insn_p (BB_END (bb
)))
498 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
501 free_move_list ((move_t
) e
->aux
);
505 at_bb_start
[bb
->index
] = list
;
507 at_bb_end
[bb
->index
] = list
;
510 /* Last move (in move sequence being processed) setting up the
511 corresponding hard register. */
512 static move_t hard_regno_last_set
[FIRST_PSEUDO_REGISTER
];
514 /* If the element value is equal to CURR_TICK then the corresponding
515 element in `hard_regno_last_set' is defined and correct. */
516 static int hard_regno_last_set_check
[FIRST_PSEUDO_REGISTER
];
518 /* Last move (in move sequence being processed) setting up the
519 corresponding allocno. */
520 static move_t
*allocno_last_set
;
522 /* If the element value is equal to CURR_TICK then the corresponding
523 element in . `allocno_last_set' is defined and correct. */
524 static int *allocno_last_set_check
;
526 /* Definition of vector of moves. */
528 DEF_VEC_ALLOC_P(move_t
, heap
);
530 /* This vec contains moves sorted topologically (depth-first) on their
532 static VEC(move_t
,heap
) *move_vec
;
534 /* The variable value is used to check correctness of values of
535 elements of arrays `hard_regno_last_set' and
536 `allocno_last_set_check'. */
537 static int curr_tick
;
539 /* This recursive function traverses dependencies of MOVE and produces
540 topological sorting (in depth-first order). */
542 traverse_moves (move_t move
)
548 move
->visited_p
= true;
549 for (i
= move
->deps_num
- 1; i
>= 0; i
--)
550 traverse_moves (move
->deps
[i
]);
551 VEC_safe_push (move_t
, heap
, move_vec
, move
);
554 /* Remove unnecessary moves in the LIST, makes topological sorting,
555 and removes cycles on hard reg dependencies by introducing new
556 allocnos assigned to memory and additional moves. It returns the
559 modify_move_list (move_t list
)
561 int i
, n
, nregs
, hard_regno
;
562 ira_allocno_t to
, from
, new_allocno
;
563 move_t move
, new_move
, set_move
, first
, last
;
567 /* Creat move deps. */
569 for (move
= list
; move
!= NULL
; move
= move
->next
)
572 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
574 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
575 for (i
= 0; i
< nregs
; i
++)
577 hard_regno_last_set
[hard_regno
+ i
] = move
;
578 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
581 for (move
= list
; move
!= NULL
; move
= move
->next
)
585 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
587 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
588 for (n
= i
= 0; i
< nregs
; i
++)
589 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
590 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
591 != ALLOCNO_REGNO (from
)))
593 move
->deps
= (move_t
*) ira_allocate (n
* sizeof (move_t
));
594 for (n
= i
= 0; i
< nregs
; i
++)
595 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
596 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
597 != ALLOCNO_REGNO (from
)))
598 move
->deps
[n
++] = hard_regno_last_set
[hard_regno
+ i
];
602 /* Toplogical sorting: */
603 VEC_truncate (move_t
, move_vec
, 0);
604 for (move
= list
; move
!= NULL
; move
= move
->next
)
605 traverse_moves (move
);
607 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
609 move
= VEC_index (move_t
, move_vec
, i
);
615 first
= VEC_last (move_t
, move_vec
);
616 /* Removing cycles: */
618 VEC_truncate (move_t
, move_vec
, 0);
619 for (move
= first
; move
!= NULL
; move
= move
->next
)
623 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
625 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (from
)];
626 for (i
= 0; i
< nregs
; i
++)
627 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
628 && ALLOCNO_HARD_REGNO
629 (hard_regno_last_set
[hard_regno
+ i
]->to
) >= 0)
631 set_move
= hard_regno_last_set
[hard_regno
+ i
];
632 /* It does not matter what loop_tree_node (of TO or
633 FROM) to use for the new allocno because of
634 subsequent IRA internal representation
637 = ira_create_allocno (ALLOCNO_REGNO (set_move
->to
), false,
638 ALLOCNO_LOOP_TREE_NODE (set_move
->to
));
639 ALLOCNO_MODE (new_allocno
) = ALLOCNO_MODE (set_move
->to
);
640 ira_set_allocno_cover_class
641 (new_allocno
, ALLOCNO_COVER_CLASS (set_move
->to
));
642 ALLOCNO_ASSIGNED_P (new_allocno
) = true;
643 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
644 ALLOCNO_REG (new_allocno
)
645 = create_new_reg (ALLOCNO_REG (set_move
->to
));
646 ALLOCNO_CONFLICT_ID (new_allocno
) = ALLOCNO_NUM (new_allocno
);
647 /* Make it possibly conflicting with all earlier
648 created allocnos. Cases where temporary allocnos
649 created to remove the cycles are quite rare. */
650 ALLOCNO_MIN (new_allocno
) = 0;
651 ALLOCNO_MAX (new_allocno
) = ira_allocnos_num
- 1;
652 new_move
= create_move (set_move
->to
, new_allocno
);
653 set_move
->to
= new_allocno
;
654 VEC_safe_push (move_t
, heap
, move_vec
, new_move
);
655 ira_move_loops_num
++;
656 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
657 fprintf (ira_dump_file
,
658 " Creating temporary allocno a%dr%d\n",
659 ALLOCNO_NUM (new_allocno
),
660 REGNO (ALLOCNO_REG (new_allocno
)));
663 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
665 nregs
= hard_regno_nregs
[hard_regno
][ALLOCNO_MODE (to
)];
666 for (i
= 0; i
< nregs
; i
++)
668 hard_regno_last_set
[hard_regno
+ i
] = move
;
669 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
672 for (i
= (int) VEC_length (move_t
, move_vec
) - 1; i
>= 0; i
--)
674 move
= VEC_index (move_t
, move_vec
, i
);
682 /* Generate RTX move insns from the move list LIST. This updates
683 allocation cost using move execution frequency FREQ. */
685 emit_move_list (move_t list
, int freq
)
689 enum machine_mode mode
;
690 enum reg_class cover_class
;
693 for (; list
!= NULL
; list
= list
->next
)
696 emit_move_insn (ALLOCNO_REG (list
->to
), ALLOCNO_REG (list
->from
));
697 list
->insn
= get_insns ();
699 /* The reload needs to have set up insn codes. If the reload
700 sets up insn codes by itself, it may fail because insns will
701 have hard registers instead of pseudos and there may be no
702 machine insn with given hard registers. */
703 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
704 recog_memoized (insn
);
705 emit_insn (list
->insn
);
706 mode
= ALLOCNO_MODE (list
->to
);
707 cover_class
= ALLOCNO_COVER_CLASS (list
->to
);
709 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
711 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
713 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
714 ira_store_cost
+= cost
;
717 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
719 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
721 cost
= ira_memory_move_cost
[mode
][cover_class
][0] * freq
;
722 ira_load_cost
+= cost
;
727 cost
= ira_register_move_cost
[mode
][cover_class
][cover_class
] * freq
;
728 ira_shuffle_cost
+= cost
;
730 ira_overall_cost
+= cost
;
732 result
= get_insns ();
737 /* Generate RTX move insns from move lists attached to basic blocks
749 if (at_bb_start
[bb
->index
] != NULL
)
751 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
752 insns
= emit_move_list (at_bb_start
[bb
->index
],
753 REG_FREQ_FROM_BB (bb
));
756 tmp
= NEXT_INSN (tmp
);
757 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
758 tmp
= NEXT_INSN (tmp
);
759 if (tmp
== BB_HEAD (bb
))
760 emit_insn_before (insns
, tmp
);
761 else if (tmp
!= NULL_RTX
)
762 emit_insn_after (insns
, PREV_INSN (tmp
));
764 emit_insn_after (insns
, get_last_insn ());
767 if (at_bb_end
[bb
->index
] != NULL
)
769 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
770 insns
= emit_move_list (at_bb_end
[bb
->index
], REG_FREQ_FROM_BB (bb
));
771 ira_assert (! control_flow_insn_p (BB_END (bb
)));
772 emit_insn_after (insns
, BB_END (bb
));
775 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
779 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
780 || ! EDGE_CRITICAL_P (e
));
781 e
->aux
= modify_move_list ((move_t
) e
->aux
);
783 (emit_move_list ((move_t
) e
->aux
,
784 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
786 if (e
->src
->next_bb
!= e
->dest
)
787 ira_additional_jumps_num
++;
792 /* Update costs of A and corresponding allocnos on upper levels on the
793 loop tree from reading (if READ_P) or writing A on an execution
796 update_costs (ira_allocno_t a
, bool read_p
, int freq
)
798 ira_loop_tree_node_t parent
;
803 ALLOCNO_FREQ (a
) += freq
;
804 ALLOCNO_MEMORY_COST (a
)
805 += (ira_memory_move_cost
[ALLOCNO_MODE (a
)][ALLOCNO_COVER_CLASS (a
)]
806 [read_p
? 1 : 0] * freq
);
807 if (ALLOCNO_CAP (a
) != NULL
)
809 else if ((parent
= ALLOCNO_LOOP_TREE_NODE (a
)->parent
) == NULL
810 || (a
= parent
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
815 /* Process moves from LIST with execution FREQ to add ranges, copies,
816 and modify costs for allocnos involved in the moves. All regnos
817 living through the list is in LIVE_THROUGH, and the loop tree node
818 used to find corresponding allocnos is NODE. */
820 add_range_and_copies_from_move_list (move_t list
, ira_loop_tree_node_t node
,
821 bitmap live_through
, int freq
)
826 ira_allocno_t to
, from
, a
;
828 allocno_live_range_t r
;
830 HARD_REG_SET hard_regs_live
;
835 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
837 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
838 /* This is a trick to guarantee that new ranges is not merged with
841 start
= ira_max_point
;
842 for (move
= list
; move
!= NULL
; move
= move
->next
)
846 if (ALLOCNO_CONFLICT_ALLOCNO_ARRAY (to
) == NULL
)
848 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
849 fprintf (ira_dump_file
, " Allocate conflicts for a%dr%d\n",
850 ALLOCNO_NUM (to
), REGNO (ALLOCNO_REG (to
)));
851 ira_allocate_allocno_conflicts (to
, n
);
853 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
854 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
855 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from
), hard_regs_live
);
856 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to
), hard_regs_live
);
857 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from
),
859 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to
), hard_regs_live
);
860 update_costs (from
, true, freq
);
861 update_costs (to
, false, freq
);
862 cp
= ira_add_allocno_copy (from
, to
, freq
, move
->insn
, NULL
);
863 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
864 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
865 cp
->num
, ALLOCNO_NUM (cp
->first
),
866 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
867 REGNO (ALLOCNO_REG (cp
->second
)));
868 r
= ALLOCNO_LIVE_RANGES (from
);
869 if (r
== NULL
|| r
->finish
>= 0)
871 ALLOCNO_LIVE_RANGES (from
)
872 = ira_create_allocno_live_range (from
, start
, ira_max_point
, r
);
873 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
874 fprintf (ira_dump_file
,
875 " Adding range [%d..%d] to allocno a%dr%d\n",
876 start
, ira_max_point
, ALLOCNO_NUM (from
),
877 REGNO (ALLOCNO_REG (from
)));
880 r
->finish
= ira_max_point
;
882 ALLOCNO_LIVE_RANGES (to
)
883 = ira_create_allocno_live_range (to
, ira_max_point
, -1,
884 ALLOCNO_LIVE_RANGES (to
));
887 for (move
= list
; move
!= NULL
; move
= move
->next
)
889 r
= ALLOCNO_LIVE_RANGES (move
->to
);
892 r
->finish
= ira_max_point
- 1;
893 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
894 fprintf (ira_dump_file
,
895 " Adding range [%d..%d] to allocno a%dr%d\n",
896 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
897 REGNO (ALLOCNO_REG (move
->to
)));
900 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
902 a
= node
->regno_allocno_map
[regno
];
903 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
)
905 ALLOCNO_LIVE_RANGES (a
)
906 = ira_create_allocno_live_range (a
, start
, ira_max_point
- 1,
907 ALLOCNO_LIVE_RANGES (a
));
908 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
911 " Adding range [%d..%d] to live through allocno a%dr%d\n",
912 start
, ira_max_point
- 1, ALLOCNO_NUM (a
),
913 REGNO (ALLOCNO_REG (a
)));
918 /* Process all move list to add ranges, conflicts, copies, and modify
919 costs for allocnos involved in the moves. */
921 add_ranges_and_copies (void)
926 ira_loop_tree_node_t node
;
929 live_through
= ira_allocate_bitmap ();
932 /* It does not matter what loop_tree_node (of source or
933 destination block) to use for searching allocnos by their
934 regnos because of subsequent IR flattening. */
935 node
= IRA_BB_NODE (bb
)->parent
;
936 bitmap_copy (live_through
, DF_LR_IN (bb
));
937 add_range_and_copies_from_move_list
938 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
939 bitmap_copy (live_through
, DF_LR_OUT (bb
));
940 add_range_and_copies_from_move_list
941 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
942 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
944 bitmap_and (live_through
, DF_LR_IN (e
->dest
), DF_LR_OUT (bb
));
945 add_range_and_copies_from_move_list
946 ((move_t
) e
->aux
, node
, live_through
,
947 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
950 ira_free_bitmap (live_through
);
953 /* The entry function changes code and generates shuffling allocnos on
954 region borders for the regional (LOOPS_P is TRUE in this case)
955 register allocation. */
957 ira_emit (bool loops_p
)
963 ira_allocno_iterator ai
;
965 FOR_EACH_ALLOCNO (a
, ai
)
966 ALLOCNO_REG (a
) = regno_reg_rtx
[ALLOCNO_REGNO (a
)];
969 at_bb_start
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
970 memset (at_bb_start
, 0, sizeof (move_t
) * last_basic_block
);
971 at_bb_end
= (move_t
*) ira_allocate (sizeof (move_t
) * last_basic_block
);
972 memset (at_bb_end
, 0, sizeof (move_t
) * last_basic_block
);
973 local_allocno_bitmap
= ira_allocate_bitmap ();
974 used_regno_bitmap
= ira_allocate_bitmap ();
975 renamed_regno_bitmap
= ira_allocate_bitmap ();
976 max_regno_before_changing
= max_reg_num ();
977 ira_traverse_loop_tree (true, ira_loop_tree_root
, change_loop
, NULL
);
978 set_allocno_somewhere_renamed_p ();
979 ira_free_bitmap (used_regno_bitmap
);
980 ira_free_bitmap (renamed_regno_bitmap
);
981 ira_free_bitmap (local_allocno_bitmap
);
984 at_bb_start
[bb
->index
] = NULL
;
985 at_bb_end
[bb
->index
] = NULL
;
986 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
987 if (e
->dest
!= EXIT_BLOCK_PTR
)
988 generate_edge_moves (e
);
991 = (move_t
*) ira_allocate (sizeof (move_t
) * max_reg_num ());
992 allocno_last_set_check
993 = (int *) ira_allocate (sizeof (int) * max_reg_num ());
994 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
995 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
998 unify_moves (bb
, true);
1000 unify_moves (bb
, false);
1001 move_vec
= VEC_alloc (move_t
, heap
, ira_allocnos_num
);
1003 add_ranges_and_copies ();
1007 free_move_list (at_bb_start
[bb
->index
]);
1008 free_move_list (at_bb_end
[bb
->index
]);
1009 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
1011 free_move_list ((move_t
) e
->aux
);
1015 VEC_free (move_t
, heap
, move_vec
);
1016 ira_free (allocno_last_set_check
);
1017 ira_free (allocno_last_set
);
1018 commit_edge_insertions ();
1019 ira_free (at_bb_end
);
1020 ira_free (at_bb_start
);