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 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
;
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
);
607 ALLOCNO_ASSIGNED_P (new_allocno
) = TRUE
;
608 ALLOCNO_HARD_REGNO (new_allocno
) = -1;
609 ALLOCNO_REG (new_allocno
)
610 = create_new_reg (ALLOCNO_REG (set_move
->to
));
611 new_move
= create_move (set_move
->to
, new_allocno
);
612 set_move
->to
= new_allocno
;
613 VARRAY_PUSH_GENERIC_PTR (move_varray
, new_move
);
615 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
616 fprintf (ira_dump_file
,
617 " Creating temporary allocno a%dr%d\n",
618 ALLOCNO_NUM (new_allocno
),
619 REGNO (ALLOCNO_REG (new_allocno
)));
622 if ((hard_regno
= ALLOCNO_HARD_REGNO (to
)) < 0)
624 nregs
= hard_regno_nregs
[hard_regno
] [ALLOCNO_MODE (to
)];
625 for (i
= 0; i
< nregs
; i
++)
627 hard_regno_last_set
[hard_regno
+ i
] = move
;
628 hard_regno_last_set_check
[hard_regno
+ i
] = curr_tick
;
631 for (i
= VARRAY_ACTIVE_SIZE (move_varray
) - 1; i
>= 0; i
--)
633 move
= VARRAY_GENERIC_PTR (move_varray
, i
);
641 /* The function generates rtx move insns from the move list LIST. It
642 updates allocation cost using move execution frequency FERQ. */
644 emit_move_list (struct move
*list
, int freq
)
648 enum machine_mode mode
;
649 enum reg_class cover_class
;
652 for (; list
!= NULL
; list
= list
->next
)
655 emit_move_insn (ALLOCNO_REG (list
->to
), ALLOCNO_REG (list
->from
));
656 list
->insn
= get_insns ();
658 /* The reload needs to have set up insn codes. If the reload
659 sets up insn codes by itself, it may fail because insns will
660 have hard registers instead of pseudos and there may be no
661 machine insn with given hard registers. */
662 for (insn
= list
->insn
; insn
!= NULL_RTX
; insn
= NEXT_INSN (insn
))
663 recog_memoized (insn
);
664 emit_insn (list
->insn
);
665 mode
= ALLOCNO_MODE (list
->to
);
666 cover_class
= ALLOCNO_COVER_CLASS (list
->to
);
668 if (ALLOCNO_HARD_REGNO (list
->to
) < 0)
670 if (ALLOCNO_HARD_REGNO (list
->from
) >= 0)
672 cost
= memory_move_cost
[mode
] [cover_class
] [0] * freq
;
676 else if (ALLOCNO_HARD_REGNO (list
->from
) < 0)
678 if (ALLOCNO_HARD_REGNO (list
->to
) >= 0)
680 cost
= memory_move_cost
[mode
] [cover_class
] [0] * freq
;
686 cost
= register_move_cost
[mode
] [cover_class
] [cover_class
] * freq
;
687 shuffle_cost
+= cost
;
689 overall_cost
+= cost
;
691 result
= get_insns ();
696 /* The function generates rtx move insns from move lists attached to
697 basic blocks and edges. */
708 if (at_bb_start
[bb
->index
] != NULL
)
710 at_bb_start
[bb
->index
] = modify_move_list (at_bb_start
[bb
->index
]);
711 insns
= emit_move_list (at_bb_start
[bb
->index
],
712 REG_FREQ_FROM_BB (bb
));
715 tmp
= NEXT_INSN (tmp
);
716 if (NOTE_INSN_BASIC_BLOCK_P (tmp
))
717 tmp
= NEXT_INSN (tmp
);
718 if (tmp
== BB_HEAD (bb
))
719 emit_insn_before (insns
, tmp
);
720 else if (tmp
!= NULL_RTX
)
721 emit_insn_after (insns
, PREV_INSN (tmp
));
723 emit_insn_after (insns
, get_last_insn ());
726 if (at_bb_end
[bb
->index
] != NULL
)
728 at_bb_end
[bb
->index
] = modify_move_list (at_bb_end
[bb
->index
]);
729 insns
= emit_move_list (at_bb_end
[bb
->index
],
730 REG_FREQ_FROM_BB (bb
));
731 ira_assert (! control_flow_insn_p (BB_END (bb
)));
732 emit_insn_after (insns
, BB_END (bb
));
735 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
739 ira_assert ((e
->flags
& EDGE_ABNORMAL
) == 0
740 || ! EDGE_CRITICAL_P (e
));
741 e
->aux
= modify_move_list (e
->aux
);
743 (emit_move_list (e
->aux
,
744 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
))),
746 if (e
->src
->next_bb
!= e
->dest
)
747 additional_jumps_num
++;
752 /* Update costs of A and its parents from reading (if READ_P) or
753 writing A on an execution path with FREQ. */
755 update_costs (allocno_t a
, int read_p
, int freq
)
757 loop_tree_node_t father
;
762 ALLOCNO_FREQ (a
) += freq
;
763 ALLOCNO_MEMORY_COST (a
)
764 += (memory_move_cost
[ALLOCNO_MODE (a
)] [ALLOCNO_COVER_CLASS (a
)]
765 [read_p
? 1 : 0] * freq
);
766 if ((father
= ALLOCNO_LOOP_TREE_NODE (a
)->father
) == NULL
767 || (a
= father
->regno_allocno_map
[ALLOCNO_REGNO (a
)]) == NULL
)
772 /* The function processes moves from LIST with execution FREQ to add
773 ranges, copies, and modify costs. All regnos living through the
774 list is in LIVE_THROUGH, and the loop tree node used to find
775 corresponding allocnos is NODE. */
777 add_range_and_copies_from_move_list (struct move
*list
, loop_tree_node_t node
,
778 bitmap live_through
, int freq
)
783 allocno_t to
, from
, a
;
785 allocno_live_range_t r
;
787 HARD_REG_SET hard_regs_live
;
792 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
794 REG_SET_TO_HARD_REG_SET (hard_regs_live
, live_through
);
795 /* This is a trick to guarantee that new ranges is not merged with
799 for (move
= list
; move
!= NULL
; move
= move
->next
)
803 if (ALLOCNO_CONFLICT_ALLOCNO_VEC (to
) == NULL
)
805 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
806 fprintf (ira_dump_file
,
807 " Allocate conflict vector of size %d for a%dr%d\n",
808 n
, ALLOCNO_NUM (to
), REGNO (ALLOCNO_REG (to
)));
809 allocate_allocno_conflicts (to
, n
);
811 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (from
));
812 bitmap_clear_bit (live_through
, ALLOCNO_REGNO (to
));
813 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (from
), hard_regs_live
);
814 IOR_HARD_REG_SET (ALLOCNO_CONFLICT_HARD_REGS (to
), hard_regs_live
);
815 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (from
),
817 IOR_HARD_REG_SET (ALLOCNO_TOTAL_CONFLICT_HARD_REGS (to
), hard_regs_live
);
818 update_costs (from
, TRUE
, freq
);
819 update_costs (to
, FALSE
, freq
);
820 cp
= add_allocno_copy (from
, to
, freq
, move
->insn
, NULL
);
821 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
822 fprintf (ira_dump_file
, " Adding cp%d:a%dr%d-a%dr%d\n",
823 cp
->num
, ALLOCNO_NUM (cp
->first
),
824 REGNO (ALLOCNO_REG (cp
->first
)), ALLOCNO_NUM (cp
->second
),
825 REGNO (ALLOCNO_REG (cp
->second
)));
826 r
= ALLOCNO_LIVE_RANGES (from
);
827 if (r
== NULL
|| r
->finish
>= 0)
829 ALLOCNO_LIVE_RANGES (from
)
830 = create_allocno_live_range (from
, start
, max_point
, r
);
831 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
832 fprintf (ira_dump_file
,
833 " Adding range [%d..%d] to allocno a%dr%d\n",
834 start
, max_point
, ALLOCNO_NUM (from
),
835 REGNO (ALLOCNO_REG (from
)));
838 r
->finish
= max_point
;
840 ALLOCNO_LIVE_RANGES (to
)
841 = create_allocno_live_range (to
, max_point
, -1,
842 ALLOCNO_LIVE_RANGES (to
));
845 for (move
= list
; move
!= NULL
; move
= move
->next
)
847 r
= ALLOCNO_LIVE_RANGES (move
->to
);
850 r
->finish
= max_point
- 1;
851 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
852 fprintf (ira_dump_file
,
853 " Adding range [%d..%d] to allocno a%dr%d\n",
854 r
->start
, r
->finish
, ALLOCNO_NUM (move
->to
),
855 REGNO (ALLOCNO_REG (move
->to
)));
858 EXECUTE_IF_SET_IN_BITMAP (live_through
, FIRST_PSEUDO_REGISTER
, regno
, bi
)
860 a
= node
->regno_allocno_map
[regno
];
861 if (ALLOCNO_MEM_OPTIMIZED_DEST (a
) == NULL
)
863 ALLOCNO_LIVE_RANGES (a
)
864 = create_allocno_live_range (a
, start
, max_point
- 1,
865 ALLOCNO_LIVE_RANGES (a
));
866 if (internal_flag_ira_verbose
> 2 && ira_dump_file
!= NULL
)
869 " Adding range [%d..%d] to live through allocno a%dr%d\n",
870 start
, max_point
- 1, ALLOCNO_NUM (a
), REGNO (ALLOCNO_REG (a
)));
875 /* The function processes all move list to add ranges, conflicts,
876 copies, and modify costs. */
878 add_ranges_and_copies (void)
883 loop_tree_node_t node
;
886 live_through
= ira_allocate_bitmap ();
889 /* It does not matter what loop_tree_node (of source or
890 destination block) to use for searching allocnos by their
891 regnos because of subsequent IR flattening. */
892 node
= IRA_BB_NODE (bb
)->father
;
893 bitmap_copy (live_through
, DF_LR_IN (bb
));
894 add_range_and_copies_from_move_list
895 (at_bb_start
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
896 bitmap_copy (live_through
, DF_LR_OUT (bb
));
897 add_range_and_copies_from_move_list
898 (at_bb_end
[bb
->index
], node
, live_through
, REG_FREQ_FROM_BB (bb
));
899 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
901 bitmap_and (live_through
, DF_LR_IN (e
->dest
), DF_LR_OUT (bb
));
902 add_range_and_copies_from_move_list
903 (e
->aux
, node
, live_through
,
904 REG_FREQ_FROM_EDGE_FREQ (EDGE_FREQUENCY (e
)));
907 ira_free_bitmap (live_through
);
910 /* Entry function changing code and generating allocno shuffling for
911 the regional (LOOPS_P is TRUE in this case) register allocation. */
913 ira_emit (int loops_p
)
920 for (i
= 0; i
< allocnos_num
; i
++)
921 ALLOCNO_REG (allocnos
[i
]) = regno_reg_rtx
[ALLOCNO_REGNO (allocnos
[i
])];
924 at_bb_start
= ira_allocate (sizeof (struct move
*) * last_basic_block
);
925 memset (at_bb_start
, 0, sizeof (struct move
*) * last_basic_block
);
926 at_bb_end
= ira_allocate (sizeof (struct move
*) * last_basic_block
);
927 memset (at_bb_end
, 0, sizeof (struct move
*) * last_basic_block
);
928 local_allocno_bitmap
= ira_allocate_bitmap ();
929 used_regno_bitmap
= ira_allocate_bitmap ();
930 max_regno_before_changing
= max_reg_num ();
931 traverse_loop_tree (FALSE
, ira_loop_tree_root
, change_loop
, NULL
);
932 ira_free_bitmap (used_regno_bitmap
);
933 ira_free_bitmap (local_allocno_bitmap
);
936 at_bb_start
[bb
->index
] = NULL
;
937 at_bb_end
[bb
->index
] = NULL
;
938 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
939 if (e
->dest
!= EXIT_BLOCK_PTR
)
940 generate_edge_moves (e
);
942 allocno_last_set
= ira_allocate (sizeof (struct move
*) * max_reg_num ());
943 allocno_last_set_check
= ira_allocate (sizeof (int) * max_reg_num ());
944 memset (allocno_last_set_check
, 0, sizeof (int) * max_reg_num ());
945 memset (hard_regno_last_set_check
, 0, sizeof (hard_regno_last_set_check
));
948 unify_moves (bb
, TRUE
);
950 unify_moves (bb
, FALSE
);
951 VARRAY_GENERIC_PTR_NOGC_INIT (move_varray
, allocnos_num
, "ordered moves");
953 add_ranges_and_copies ();
957 free_move_list (at_bb_start
[bb
->index
]);
958 free_move_list (at_bb_end
[bb
->index
]);
959 FOR_EACH_EDGE (e
, ei
, bb
->succs
)
961 free_move_list (e
->aux
);
965 VARRAY_FREE (move_varray
);
966 ira_free (allocno_last_set_check
);
967 ira_free (allocno_last_set
);
968 commit_edge_insertions ();
969 ira_free (at_bb_end
);
970 ira_free (at_bb_start
);