1 /* Integrated Register Allocator. Changing code and generating moves.
2 Copyright (C) 2006, 2007
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 2, 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 COPYING. If not, write to the Free
20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
26 #include "coretypes.h"
35 #include "hard-reg-set.h"
36 #include "basic-block.h"
41 #include "tree-pass.h"
50 static struct move
*create_move (allocno_t
, allocno_t
);
51 static void free_move (struct move
*);
52 static void free_move_list (struct move
*);
53 static int eq_move_lists_p (struct move
*, struct move
*);
54 static int change_regs (rtx
*);
55 static void add_to_edge_list (edge
, struct move
*, int);
56 static rtx
create_new_reg (rtx
);
57 static int subloop_tree_node_p (loop_tree_node_t
, loop_tree_node_t
);
58 static void set_allocno_reg (allocno_t
, rtx
);
59 static int not_modified_p (allocno_t
, allocno_t
);
60 static void generate_edge_moves (edge
);
61 static void change_loop (loop_tree_node_t
);
62 static int eq_edge_move_lists_p (VEC(edge
,gc
) *);
63 static void unify_moves (basic_block
, int);
64 static void traverse_moves (struct move
*);
65 static struct move
*modify_move_list (struct move
*);
66 static rtx
emit_move_list (struct move
*, int);
67 static void emit_moves (void);
68 static void update_costs (allocno_t
, int, int);
69 static void add_range_and_copies_from_move_list (struct move
*,
72 static void add_ranges_and_copies (void);
74 /* The structure represents allocno shuffling. */
77 /* The shuffled allocnos. */
79 /* The next move in the sequence. */
81 /* Use for finding dependencies. */
83 /* The size of the following array. */
85 /* Moves on which given move depends on. Dependency can be cyclic.
86 It means we need a temporary to generates the moves. */
88 /* First insn generated for the move. */
92 /* Array of moves (indexed by BB index) which should be put at the
93 start/end of the corresponding blocks. */
94 static struct move
**at_bb_start
, **at_bb_end
;
96 /* Max regno before renaming some pseudo-registers. For example, the
97 same pseudo-register can be renamed in loop if its allocation is
98 different outside the loop. */
99 static int max_regno_before_changing
;
101 /* The function returns new move of allocnos TO and FROM. */
103 create_move (allocno_t to
, allocno_t from
)
107 move
= ira_allocate (sizeof (struct move
));
113 move
->insn
= NULL_RTX
;
114 move
->visited_p
= FALSE
;
118 /* The function frees memory for MOVE and its dependencies. */
120 free_move (struct move
*move
)
122 if (move
->deps
!= NULL
)
123 ira_free (move
->deps
);
127 /* The function frees memory for list of the moves given by its
130 free_move_list (struct move
*head
)
134 for (; head
!= NULL
; head
= next
)
141 /* The function returns nonzero if the the move list LIST1 and LIST2
142 are equal (two moves are equal if they shuffles the same
145 eq_move_lists_p (struct move
*list1
, struct move
*list2
)
147 for (; list1
!= NULL
&& list2
!= NULL
;
148 list1
= list1
->next
, list2
= list2
->next
)
149 if (list1
->from
!= list2
->from
|| list1
->to
!= list2
->to
)
151 return list1
== list2
;
154 /* This recursive function changes pseudo-registers in *LOC if it is
155 necessary. The function returns non-zero if a change was done. */
157 change_regs (rtx
*loc
)
159 int i
, regno
, result
= 0;
163 if (*loc
== NULL_RTX
)
165 code
= GET_CODE (*loc
);
168 regno
= REGNO (*loc
);
169 if (regno
< FIRST_PSEUDO_REGISTER
)
171 if (regno
>= max_regno_before_changing
)
172 /* It is a shared register which was changed already. */
174 /* ??? That is for reg_equal. */
175 if (ira_curr_loop_tree_node
->regno_allocno_map
[regno
] == NULL
)
177 *loc
= ALLOCNO_REG (ira_curr_loop_tree_node
->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 /* The function attaches MOVE to the edge E. The move is attached to
198 the head of the list if HEAD_P is nonzero. */
200 add_to_edge_list (edge e
, struct move
*move
, int head_p
)
204 if (head_p
|| e
->aux
== NULL
)
211 for (last
= e
->aux
; last
->next
!= NULL
; last
= last
->next
)
218 /* The function creates and returns new pseudo-register with the same
219 attributes as ORIGINAL_REG. */
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 /* The function returns non-zero if loop given by SUBNODE inside the
237 loop given by NODE. */
239 subloop_tree_node_p (loop_tree_node_t subnode
, loop_tree_node_t node
)
241 for (; subnode
!= NULL
; subnode
= subnode
->father
)
247 /* The function sets up field `reg' to REG for allocnos which has the
248 same regno as ALLOCNO and which are inside the loop corresponding to
251 set_allocno_reg (allocno_t allocno
, rtx reg
)
254 loop_tree_node_t node
;
256 node
= ALLOCNO_LOOP_TREE_NODE (allocno
);
257 for (a
= 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
;
264 /* The following function returns nonzero if move insn of SRC_ALLOCNO
265 to DEST_ALLOCNO does not change value of the destination. */
267 not_modified_p (allocno_t src_allocno
, allocno_t dest_allocno
)
269 int regno
, orig_regno
;
271 loop_tree_node_t node
;
273 orig_regno
= ALLOCNO_REGNO (src_allocno
);
274 regno
= REGNO (ALLOCNO_REG (dest_allocno
));
275 for (node
= ALLOCNO_LOOP_TREE_NODE (src_allocno
);
278 if ((a
= node
->regno_allocno_map
[orig_regno
]) == NULL
)
280 else if (REGNO (ALLOCNO_REG (a
)) == (unsigned) regno
)
282 else if (bitmap_bit_p (node
->modified_regnos
, orig_regno
))
287 /* The function generates and attaches moves to the edge E. It looks
288 at the final regnos of allocnos living on the edge with the same
289 original regno to find what moves should be generated. */
291 generate_edge_moves (edge e
)
293 loop_tree_node_t src_loop_node
, dest_loop_node
;
296 allocno_t src_allocno
, dest_allocno
, *src_map
, *dest_map
;
299 src_loop_node
= IRA_BB_NODE (e
->src
)->father
;
300 dest_loop_node
= IRA_BB_NODE (e
->dest
)->father
;
302 if (src_loop_node
== dest_loop_node
)
304 src_map
= src_loop_node
->regno_allocno_map
;
305 dest_map
= dest_loop_node
->regno_allocno_map
;
306 EXECUTE_IF_SET_IN_REG_SET (DF_LR_IN (e
->dest
),
307 FIRST_PSEUDO_REGISTER
, regno
, bi
)
308 if (bitmap_bit_p (DF_LR_OUT (e
->src
), regno
))
310 src_allocno
= src_map
[regno
];
311 dest_allocno
= dest_map
[regno
];
312 if (REGNO (ALLOCNO_REG (src_allocno
))
313 == REGNO (ALLOCNO_REG (dest_allocno
)))
315 /* Actually it is not a optimization we need this code because
316 the memory (remember about equivalent memory) might be ROM
317 (or placed in read only section). */
318 if (ALLOCNO_HARD_REGNO (dest_allocno
) < 0
319 && ALLOCNO_HARD_REGNO (src_allocno
) >= 0
320 && not_modified_p (src_allocno
, dest_allocno
))
322 ALLOCNO_MEM_OPTIMIZED_DEST (src_allocno
) = dest_allocno
;
323 ALLOCNO_MEM_OPTIMIZED_DEST_P (dest_allocno
) = TRUE
;
324 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
325 fprintf (ira_dump_file
, " Remove r%d:a%d->a%d(mem)\n",
326 regno
, ALLOCNO_NUM (src_allocno
),
327 ALLOCNO_NUM (dest_allocno
));
330 move
= create_move (dest_allocno
, src_allocno
);
331 add_to_edge_list (e
, move
, TRUE
);
335 /* Bitmap of allocnos local for the current loop. */
336 static bitmap local_allocno_bitmap
;
338 /* This bitmap is used to find that we need to generate and use a new
339 pseudo-register when processing allocnos with the same original
341 static bitmap used_regno_bitmap
;
343 /* The following function changes (if necessary) pseudo-registers
344 inside loop given by loop tree node NODE. */
346 change_loop (loop_tree_node_t node
)
351 allocno_t allocno
, father_allocno
, *map
;
352 rtx insn
, original_reg
;
354 if (node
!= ira_loop_tree_root
)
357 if (node
->bb
!= NULL
)
359 FOR_BB_INSNS (node
->bb
, insn
)
360 if (INSN_P (insn
) && change_regs (&insn
))
362 df_insn_rescan (insn
);
363 df_notes_rescan (insn
);
368 if (internal_flag_ira_verbose
> 3 && ira_dump_file
!= NULL
)
369 fprintf (ira_dump_file
,
370 " Changing RTL for loop %d (header bb%d)\n",
371 node
->loop
->num
, node
->loop
->header
->index
);
373 map
= ira_curr_loop_tree_node
->father
->regno_allocno_map
;
374 EXECUTE_IF_SET_IN_REG_SET (ira_curr_loop_tree_node
->border_allocnos
,
377 allocno
= allocnos
[i
];
378 regno
= ALLOCNO_REGNO (allocno
);
379 father_allocno
= map
[regno
];
380 /* We generate the same register move because the reload can
381 put a allocno into memory in this case we will have live
382 range splitting. If it does not happen such the same
383 hard register moves will be removed. The worst case when
384 the both allocnos are put into memory by the reload is
386 if (father_allocno
!= NULL
387 && (ALLOCNO_HARD_REGNO (allocno
)
388 == ALLOCNO_HARD_REGNO (father_allocno
))
389 && (ALLOCNO_HARD_REGNO (allocno
) < 0
390 || TEST_HARD_REG_BIT (prohibited_mode_move_regs
391 [ALLOCNO_MODE (allocno
)],
392 ALLOCNO_HARD_REGNO (allocno
))
393 /* don't create copies because reload can spill a
394 allocno set by copy although allocno will not get
396 || reg_equiv_invariant_p
[regno
]
397 || reg_equiv_const
[regno
] != NULL_RTX
))
399 original_reg
= ALLOCNO_REG (allocno
);
400 if (father_allocno
== NULL
401 || REGNO (ALLOCNO_REG (father_allocno
)) == REGNO (original_reg
))
403 if (internal_flag_ira_verbose
> 3 && ira_dump_file
)
404 fprintf (ira_dump_file
, " %i vs father %i:",
405 ALLOCNO_HARD_REGNO (allocno
),
406 ALLOCNO_HARD_REGNO (father_allocno
));
407 set_allocno_reg (allocno
, create_new_reg (original_reg
));
411 /* Rename locals: Local allocnos with same regno in different loops
412 might get the different hard register. So we need to change
414 bitmap_and_compl (local_allocno_bitmap
,
415 ira_curr_loop_tree_node
->mentioned_allocnos
,
416 ira_curr_loop_tree_node
->border_allocnos
);
417 EXECUTE_IF_SET_IN_REG_SET (local_allocno_bitmap
, 0, i
, bi
)
419 allocno
= allocnos
[i
];
420 regno
= ALLOCNO_REGNO (allocno
);
421 if (ALLOCNO_CAP_MEMBER (allocno
) != NULL
)
423 used_p
= bitmap_bit_p (used_regno_bitmap
, regno
);
424 bitmap_set_bit (used_regno_bitmap
, regno
);
427 set_allocno_reg (allocno
, create_new_reg (ALLOCNO_REG (allocno
)));
431 /* The function returns nonzero if move lists on all edges in vector
434 eq_edge_move_lists_p (VEC(edge
,gc
) *vec
)
439 list
= EDGE_I (vec
, 0)->aux
;
440 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
441 if (! eq_move_lists_p (list
, EDGE_I (vec
, i
)->aux
))
446 /* The function looks at all enter edges (if START_P) or exit edges of
447 basic block BB and puts move lists at the BB start or end if it is
448 possible. In other words, it decreases code duplication of
449 shuffling allocnos. */
451 unify_moves (basic_block bb
, int start_p
)
458 vec
= (start_p
? bb
->preds
: bb
->succs
);
459 if (EDGE_COUNT (vec
) == 0 || ! eq_edge_move_lists_p (vec
))
463 if (! start_p
&& control_flow_insn_p (BB_END (bb
)))
466 for (i
= EDGE_COUNT (vec
) - 1; i
> 0; i
--)
469 free_move_list (e
->aux
);
473 at_bb_start
[bb
->index
] = list
;
475 at_bb_end
[bb
->index
] = list
;
478 /* Last move (in move sequence being processed) setting up the
479 corresponding hard register. */
480 static struct move
*hard_regno_last_set
[FIRST_PSEUDO_REGISTER
];
482 /* If the element value is equal to CURR_TICK then the corresponding
483 element in `hard_regno_last_set' is defined and correct. */
484 static int hard_regno_last_set_check
[FIRST_PSEUDO_REGISTER
];
486 /* Last move (in move sequence being processed) setting up the
487 corresponding allocno. */
488 static struct move
**allocno_last_set
;
490 /* If the element value is equal to CURR_TICK then the corresponding
491 element in . `allocno_last_set' is defined and correct. */
492 static int *allocno_last_set_check
;
494 /* This array contains moves sorted topologically (depth-first) on
495 their dependency graph. */
496 static varray_type move_varray
;
498 /* The variable value is used to check correctness of values of
499 elements of arrays `hard_regno_last_set' and
500 `allocno_last_set_check'. */
501 static int curr_tick
;
503 /* This recursive function traverses dependecies of MOVE and do
504 toplogical sorting (in depth-first order). */
506 traverse_moves (struct move
*move
)
512 move
->visited_p
= TRUE
;
513 for (i
= move
->deps_num
- 1; i
>= 0; i
--)
514 traverse_moves (move
->deps
[i
]);
515 VARRAY_PUSH_GENERIC_PTR (move_varray
, move
);
518 /* The function removes unnecessary moves in the LIST, makes
519 topological sorting, and removes cycles on hard reg dependencies by
520 introducing new allocnos assigned to memory and additional moves.
521 It returns the result move list. */
523 modify_move_list (struct move
*list
)
525 int i
, n
, nregs
, hard_regno
, hard_regs_num
;
526 allocno_t to
, from
, new_allocno
;
527 struct move
*move
, *new_move
, *set_move
, *first
, *last
;
531 /* Creat move deps. */
533 for (move
= list
; move
!= NULL
; move
= move
->next
)
536 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
538 nregs
= hard_regno_nregs
[hard_regno
] [ALLOCNO_MODE (to
)];
539 for (i
= 0; i
< nregs
; i
++)
541 hard_regno_last_set
[hard_regno
+ i
] = move
;
542 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
545 for (move
= list
; move
!= NULL
; move
= move
->next
)
549 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
551 nregs
= hard_regno_nregs
[hard_regno
] [ALLOCNO_MODE (from
)];
552 for (n
= i
= 0; i
< nregs
; i
++)
553 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
554 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
555 != ALLOCNO_REGNO (from
)))
557 move
->deps
= ira_allocate (n
* sizeof (struct move
*));
558 for (n
= i
= 0; i
< nregs
; i
++)
559 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
560 && (ALLOCNO_REGNO (hard_regno_last_set
[hard_regno
+ i
]->to
)
561 != ALLOCNO_REGNO (from
)))
562 move
->deps
[n
++] = hard_regno_last_set
[hard_regno
+ i
];
566 /* Toplogical sorting: */
567 VARRAY_POP_ALL (move_varray
);
568 for (move
= list
; move
!= NULL
; move
= move
->next
)
569 traverse_moves (move
);
571 for (i
= VARRAY_ACTIVE_SIZE (move_varray
) - 1; i
>= 0; i
--)
573 move
= VARRAY_GENERIC_PTR (move_varray
, i
);
579 first
= VARRAY_TOP_GENERIC_PTR (move_varray
);
580 /* Removing cycles: */
582 VARRAY_POP_ALL (move_varray
);
583 for (move
= first
; move
!= NULL
; move
= move
->next
)
587 if ((hard_regno
= ALLOCNO_HARD_REGNO (from
)) >= 0)
589 nregs
= hard_regno_nregs
[hard_regno
] [ALLOCNO_MODE (from
)];
590 for (i
= 0; i
< nregs
; i
++)
591 if (hard_regno_last_set_check
[hard_regno
+ i
] == curr_tick
592 && ALLOCNO_HARD_REGNO (hard_regno_last_set
593 [hard_regno
+ i
]->to
) >= 0)
595 set_move
= hard_regno_last_set
[hard_regno
+ i
];
596 /* It does not matter what loop_tree_node (of TO or
597 FROM) to use for the new allocno because of
598 subsequent IR flattening. */
600 = create_allocno (ALLOCNO_REGNO (set_move
->to
), FALSE
,
601 ALLOCNO_LOOP_TREE_NODE (set_move
->to
));
602 ALLOCNO_MODE (new_allocno
) = ALLOCNO_MODE (set_move
->to
);
603 ALLOCNO_COVER_CLASS (new_allocno
)
604 = ALLOCNO_COVER_CLASS (set_move
->to
);
605 ALLOCNO_BEST_CLASS (new_allocno
)
606 = ALLOCNO_COVER_CLASS (new_allocno
);
608 = class_hard_regs_num
[ALLOCNO_COVER_CLASS (new_allocno
)];
609 ALLOCNO_HARD_REG_COSTS (new_allocno
)
610 = ira_allocate (hard_regs_num
* sizeof (int));
611 memset (ALLOCNO_HARD_REG_COSTS (new_allocno
), 0,
612 hard_regs_num
* sizeof (int));
613 ALLOCNO_CONFLICT_HARD_REG_COSTS (new_allocno
)
614 = ira_allocate (hard_regs_num
* sizeof (int));
615 memset (ALLOCNO_CONFLICT_HARD_REG_COSTS (new_allocno
), 0,
616 hard_regs_num
* sizeof (int));
617 ALLOCNO_UPDATED_HARD_REG_COSTS (new_allocno
)
618 = ira_allocate (hard_regs_num
* sizeof (int));
619 ALLOCNO_UPDATED_CONFLICT_HARD_REG_COSTS (new_allocno
)
620 = ira_allocate (hard_regs_num
* sizeof (int));
621 ALLOCNO_ASSIGNED_P (new_allocno
) = TRUE
;
622 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
623 ALLOCNO_REG (new_allocno
)
624 = create_new_reg (ALLOCNO_REG (set_move
->to
));
625 new_move
= create_move (set_move
->to
, new_allocno
);
626 set_move
->to
= new_allocno
;
627 VARRAY_PUSH_GENERIC_PTR (move_varray
, new_move
);
629 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
630 fprintf (ira_dump_file
,
631 " Creating temporary allocno a%dr%d\n",
632 ALLOCNO_NUM (new_allocno
),
633 REGNO (ALLOCNO_REG (new_allocno
)));
636 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
638 nregs
= hard_regno_nregs
[hard_regno
] [ALLOCNO_MODE (to
)];
639 for (i
= 0; i
< nregs
; i
++)
641 hard_regno_last_set
[hard_regno
+ i
] = move
;
642 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
645 for (i
= VARRAY_ACTIVE_SIZE (move_varray
) - 1; i
>= 0; i
--)
647 move
= VARRAY_GENERIC_PTR (move_varray
, i
);
655 /* The function generates rtx move insns from the move list LIST. It
656 updates allocation cost using move execution frequency FERQ. */
658 emit_move_list (struct move
*list
, int freq
)
662 enum machine_mode mode
;
663 enum reg_class cover_class
;
666 for (; list
!= NULL
; list
= list
->next
)
669 emit_move_insn (ALLOCNO_REG (list
->to
), ALLOCNO_REG (list
->from
));
670 list
->insn
= get_insns ();
672 /* The reload needs to have set up insn codes. If the reload
673 sets up insn codes by itself, it may fail because insns will
674 have hard registers instead of pseudos and there may be no
675 machine insn with given hard registers. */
676 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
677 recog_memoized (insn
);
678 emit_insn (list
->insn
);
679 mode
= ALLOCNO_MODE (list
->to
);
680 cover_class
= ALLOCNO_COVER_CLASS (list
->to
);
682 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
684 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
686 cost
= memory_move_cost
[mode
] [cover_class
] [0] * freq
;
690 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
692 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
694 cost
= memory_move_cost
[mode
] [cover_class
] [0] * freq
;
700 cost
= register_move_cost
[mode
] [cover_class
] [cover_class
] * freq
;
701 shuffle_cost
+= cost
;
703 overall_cost
+= cost
;
705 result
= get_insns ();
710 /* The function generates rtx move insns from move lists attached to
711 basic blocks and edges. */
722 if (at_bb_start
[bb
->index
] != NULL
)
724 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
725 insns
= emit_move_list (at_bb_start
[bb
->index
],
726 REG_FREQ_FROM_BB (bb
));
729 tmp
= NEXT_INSN (tmp
);
730 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
731 tmp
= NEXT_INSN (tmp
);
732 if (tmp
== BB_HEAD (bb
))
733 emit_insn_before (insns
, tmp
);
734 else if (tmp
!= NULL_RTX
)
735 emit_insn_after (insns
, PREV_INSN (tmp
));
737 emit_insn_after (insns
, get_last_insn ());
740 if (at_bb_end
[bb
->index
] != NULL
)
742 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
743 insns
= emit_move_list (at_bb_end
[bb
->index
],
744 REG_FREQ_FROM_BB (bb
));
745 ira_assert (! control_flow_insn_p (BB_END (bb
)));
746 emit_insn_after (insns
, BB_END (bb
));
749 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
753 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
754 || ! EDGE_CRITICAL_P (e
));
755 e
->aux
= modify_move_list (e
->aux
);
757 (emit_move_list (e
->aux
,
758 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
760 if (e
->src
->next_bb
!= e
->dest
)
761 additional_jumps_num
++;
766 /* Update costs of A and its parents from reading (if READ_P) or
767 writing A on an execution path with FREQ. */
769 update_costs (allocno_t a
, int read_p
, int freq
)
771 loop_tree_node_t father
;
776 ALLOCNO_FREQ (a
) += freq
;
777 ALLOCNO_MEMORY_COST (a
)
778 += (memory_move_cost
[ALLOCNO_MODE (a
)] [ALLOCNO_COVER_CLASS (a
)]
779 [read_p
? 1 : 0] * freq
);
780 if ((father
= ALLOCNO_LOOP_TREE_NODE (a
)->father
) == NULL
781 || (a
= father
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
786 /* The function processes moves from LIST with execution FREQ to add
787 ranges, copies, and modify costs. All regnos living through the
788 list is in LIVE_THROUGH, and the loop tree node used to find
789 corresponding allocnos is NODE. */
791 add_range_and_copies_from_move_list (struct move
*list
, loop_tree_node_t node
,
792 bitmap live_through
, int freq
)
797 allocno_t to
, from
, a
;
799 allocno_live_range_t r
;
801 HARD_REG_SET hard_regs_live
;
806 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
808 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
809 /* This is a trick to guarantee that new ranges is not merged with
813 for (move
= list
; move
!= NULL
; move
= move
->next
)
817 if (ALLOCNO_CONFLICT_ALLOCNO_VEC (to
) == NULL
)
819 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
820 fprintf (ira_dump_file
,
821 " Allocate conflict vector of size %d for a%dr%d\n",
822 n
, ALLOCNO_NUM (to
), REGNO (ALLOCNO_REG (to
)));
823 allocate_allocno_conflicts (to
, n
);
825 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
826 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
827 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from
), hard_regs_live
);
828 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to
), hard_regs_live
);
829 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from
),
831 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to
), hard_regs_live
);
832 update_costs (from
, TRUE
, freq
);
833 update_costs (to
, FALSE
, freq
);
834 cp
= add_allocno_copy (from
, to
, freq
, move
->insn
, NULL
);
835 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
836 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
837 cp
->num
, ALLOCNO_NUM (cp
->first
),
838 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
839 REGNO (ALLOCNO_REG (cp
->second
)));
840 r
= ALLOCNO_LIVE_RANGES (from
);
841 if (r
== NULL
|| r
->finish
>= 0)
843 ALLOCNO_LIVE_RANGES (from
)
844 = create_allocno_live_range (from
, start
, max_point
, r
);
845 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
846 fprintf (ira_dump_file
,
847 " Adding range [%d..%d] to allocno a%dr%d\n",
848 start
, max_point
, ALLOCNO_NUM (from
),
849 REGNO (ALLOCNO_REG (from
)));
852 r
->finish
= max_point
;
854 ALLOCNO_LIVE_RANGES (to
)
855 = create_allocno_live_range (to
, max_point
, -1,
856 ALLOCNO_LIVE_RANGES (to
));
859 for (move
= list
; move
!= NULL
; move
= move
->next
)
861 r
= ALLOCNO_LIVE_RANGES (move
->to
);
864 r
->finish
= max_point
- 1;
865 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
866 fprintf (ira_dump_file
,
867 " Adding range [%d..%d] to allocno a%dr%d\n",
868 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
869 REGNO (ALLOCNO_REG (move
->to
)));
872 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
874 a
= node
->regno_allocno_map
[regno
];
875 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
)
877 ALLOCNO_LIVE_RANGES (a
)
878 = create_allocno_live_range (a
, start
, max_point
- 1,
879 ALLOCNO_LIVE_RANGES (a
));
880 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
883 " Adding range [%d..%d] to live through allocno a%dr%d\n",
884 start
, max_point
- 1, ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
889 /* The function processes all move list to add ranges, conflicts,
890 copies, and modify costs. */
892 add_ranges_and_copies (void)
897 loop_tree_node_t node
;
900 live_through
= ira_allocate_bitmap ();
903 /* It does not matter what loop_tree_node (of source or
904 destination block) to use for searching allocnos by their
905 regnos because of subsequent IR flattening. */
906 node
= IRA_BB_NODE (bb
)->father
;
907 bitmap_copy (live_through
, DF_LR_IN (bb
));
908 add_range_and_copies_from_move_list
909 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
910 bitmap_copy (live_through
, DF_LR_OUT (bb
));
911 add_range_and_copies_from_move_list
912 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
913 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
915 bitmap_and (live_through
, DF_LR_IN (e
->dest
), DF_LR_OUT (bb
));
916 add_range_and_copies_from_move_list
917 (e
->aux
, node
, live_through
,
918 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
921 ira_free_bitmap (live_through
);
924 /* Entry function changing code and generating allocno shuffling for
925 the regional (LOOPS_P is TRUE in this case) register allocation. */
927 ira_emit (int loops_p
)
934 for (i
= 0; i
< allocnos_num
; i
++)
935 ALLOCNO_REG (allocnos
[i
]) = regno_reg_rtx
[ALLOCNO_REGNO (allocnos
[i
])];
938 at_bb_start
= ira_allocate (sizeof (struct move
*) * last_basic_block
);
939 memset (at_bb_start
, 0, sizeof (struct move
*) * last_basic_block
);
940 at_bb_end
= ira_allocate (sizeof (struct move
*) * last_basic_block
);
941 memset (at_bb_end
, 0, sizeof (struct move
*) * last_basic_block
);
942 local_allocno_bitmap
= ira_allocate_bitmap ();
943 used_regno_bitmap
= ira_allocate_bitmap ();
944 max_regno_before_changing
= max_reg_num ();
945 traverse_loop_tree (FALSE
, ira_loop_tree_root
, change_loop
, NULL
);
946 ira_free_bitmap (used_regno_bitmap
);
947 ira_free_bitmap (local_allocno_bitmap
);
950 at_bb_start
[bb
->index
] = NULL
;
951 at_bb_end
[bb
->index
] = NULL
;
952 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
953 if (e
->dest
!= EXIT_BLOCK_PTR
)
954 generate_edge_moves (e
);
956 allocno_last_set
= ira_allocate (sizeof (struct move
*) * max_reg_num ());
957 allocno_last_set_check
= ira_allocate (sizeof (int) * max_reg_num ());
958 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
959 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
962 unify_moves (bb
, TRUE
);
964 unify_moves (bb
, FALSE
);
965 VARRAY_GENERIC_PTR_NOGC_INIT (move_varray
, allocnos_num
, "ordered moves");
967 add_ranges_and_copies ();
971 free_move_list (at_bb_start
[bb
->index
]);
972 free_move_list (at_bb_end
[bb
->index
]);
973 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
975 free_move_list (e
->aux
);
979 VARRAY_FREE (move_varray
);
980 ira_free (allocno_last_set_check
);
981 ira_free (allocno_last_set
);
982 commit_edge_insertions ();
983 ira_free (at_bb_end
);
984 ira_free (at_bb_start
);