1 /* Perform branch target register load optimizations.
2 Copyright (C) 2001, 2002, 2003 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 2, or (at your option) any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING. If not, write to the Free
18 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
37 #include "insn-attr.h"
41 /* Target register optimizations - these are performed after reload. */
43 typedef struct btr_def_group_s
45 struct btr_def_group_s
*next
;
47 struct btr_def_s
*members
;
50 typedef struct btr_user_s
52 struct btr_user_s
*next
;
56 /* If INSN has a single use of a single branch register, then
57 USE points to it within INSN. If there is more than
58 one branch register use, or the use is in some way ambiguous,
62 int first_reaching_def
;
63 char other_use_this_block
;
66 /* btr_def structs appear on three lists:
67 1. A list of all btr_def structures (head is
68 ALL_BTR_DEFS, linked by the NEXT field).
69 2. A list of branch reg definitions per basic block (head is
70 BB_BTR_DEFS[i], linked by the NEXT_THIS_BB field).
71 3. A list of all branch reg definitions belonging to the same
72 group (head is in a BTR_DEF_GROUP struct, linked by
73 NEXT_THIS_GROUP field). */
75 typedef struct btr_def_s
77 struct btr_def_s
*next_this_bb
;
78 struct btr_def_s
*next_this_group
;
84 /* For a branch register setting insn that has a constant
85 source (i.e. a label), group links together all the
86 insns with the same source. For other branch register
87 setting insns, group is NULL. */
90 /* If this def has a reaching use which is not a simple use
91 in a branch instruction, then has_ambiguous_use will be true,
92 and we will not attempt to migrate this definition. */
93 char has_ambiguous_use
;
94 /* live_range is an approximation to the true live range for this
95 def/use web, because it records the set of blocks that contain
96 the live range. There could be other live ranges for the same
97 branch register in that set of blocks, either in the block
98 containing the def (before the def), or in a block containing
99 a use (after the use). If there are such other live ranges, then
100 other_btr_uses_before_def or other_btr_uses_after_use must be set true
102 char other_btr_uses_before_def
;
103 char other_btr_uses_after_use
;
107 static int issue_rate
;
109 static int basic_block_freq (basic_block
);
110 static int insn_sets_btr_p (rtx
, int, int *);
111 static rtx
*find_btr_use (rtx
);
112 static int btr_referenced_p (rtx
, rtx
*);
113 static int find_btr_reference (rtx
*, void *);
114 static void find_btr_def_group (btr_def_group
*, btr_def
);
115 static btr_def
add_btr_def (fibheap_t
, basic_block
, int, rtx
,
116 unsigned int, int, btr_def_group
*);
117 static btr_user
new_btr_user (basic_block
, int, rtx
);
118 static void dump_hard_reg_set (HARD_REG_SET
);
119 static void dump_btrs_live (int);
120 static void note_other_use_this_block (unsigned int, btr_user
);
121 static void compute_defs_uses_and_gen (fibheap_t
, btr_def
*,btr_user
*,
122 sbitmap
*, sbitmap
*, HARD_REG_SET
*);
123 static void compute_kill (sbitmap
*, sbitmap
*, HARD_REG_SET
*);
124 static void compute_out (sbitmap
*bb_out
, sbitmap
*, sbitmap
*, int);
125 static void link_btr_uses (btr_def
*, btr_user
*, sbitmap
*, sbitmap
*, int);
126 static void build_btr_def_use_webs (fibheap_t
);
127 static int block_at_edge_of_live_range_p (int, btr_def
);
128 static void clear_btr_from_live_range (btr_def def
);
129 static void add_btr_to_live_range (btr_def
);
130 static void augment_live_range (bitmap
, HARD_REG_SET
*, basic_block
,
132 static int choose_btr (HARD_REG_SET
);
133 static void combine_btr_defs (btr_def
, HARD_REG_SET
*);
134 static void btr_def_live_range (btr_def
, HARD_REG_SET
*);
135 static void move_btr_def (basic_block
, int, btr_def
, bitmap
, HARD_REG_SET
*);
136 static int migrate_btr_def (btr_def
, int);
137 static void migrate_btr_defs (enum reg_class
, int);
138 static int can_move_up (basic_block
, rtx
, int);
139 static void note_btr_set (rtx
, rtx
, void *);
141 /* The following code performs code motion of target load instructions
142 (instructions that set branch target registers), to move them
143 forward away from the branch instructions and out of loops (or,
144 more generally, from a more frequently executed place to a less
145 frequently executed place).
146 Moving target load instructions further in front of the branch
147 instruction that uses the target register value means that the hardware
148 has a better chance of preloading the instructions at the branch
149 target by the time the branch is reached. This avoids bubbles
150 when a taken branch needs to flush out the pipeline.
151 Moving target load instructions out of loops means they are executed
154 /* An obstack to hold the def-use web data structures built up for
155 migrating branch target load instructions. */
156 static struct obstack migrate_btrl_obstack
;
158 /* Array indexed by basic block number, giving the set of registers
159 live in that block. */
160 static HARD_REG_SET
*btrs_live
;
162 /* Set of all target registers that we are willing to allocate. */
163 static HARD_REG_SET all_btrs
;
165 /* Provide lower and upper bounds for target register numbers, so that
166 we don't need to search through all the hard registers all the time. */
167 static int first_btr
, last_btr
;
171 /* Return an estimate of the frequency of execution of block bb.
172 If we have a profiling count available, we could use it here. */
174 basic_block_freq (basic_block bb
)
176 return bb
->frequency
;
179 static rtx
*btr_reference_found
;
181 /* A subroutine of btr_referenced_p, called through for_each_rtx.
182 PREG is a pointer to an rtx that is to be excluded from the
183 traversal. If we find a reference to a target register anywhere
184 else, return 1, and put a pointer to it into btr_reference_found. */
186 find_btr_reference (rtx
*px
, void *preg
)
194 if (GET_CODE (x
) != REG
)
197 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1; i
>= 0; i
--)
198 if (TEST_HARD_REG_BIT (all_btrs
, regno
+i
))
200 btr_reference_found
= px
;
206 /* Return nonzero if X references (sets or reads) any branch target register.
207 If EXCLUDEP is set, disregard any references within the rtx pointed to
208 by it. If returning nonzero, also set btr_reference_found as above. */
210 btr_referenced_p (rtx x
, rtx
*excludep
)
212 return for_each_rtx (&x
, find_btr_reference
, excludep
);
215 /* Return true if insn is an instruction that sets a target register.
216 if CHECK_CONST is true, only return true if the source is constant.
217 If such a set is found and REGNO is nonzero, assign the register number
218 of the destination register to *REGNO. */
220 insn_sets_btr_p (rtx insn
, int check_const
, int *regno
)
224 if (GET_CODE (insn
) == INSN
225 && (set
= single_set (insn
)))
227 rtx dest
= SET_DEST (set
);
228 rtx src
= SET_SRC (set
);
230 if (GET_CODE (dest
) == SUBREG
)
231 dest
= XEXP (dest
, 0);
233 if (GET_CODE (dest
) == REG
234 && TEST_HARD_REG_BIT (all_btrs
, REGNO (dest
)))
236 if (btr_referenced_p (src
, NULL
))
238 if (!check_const
|| CONSTANT_P (src
))
241 *regno
= REGNO (dest
);
249 /* Find and return a use of a target register within an instruction INSN. */
251 find_btr_use (rtx insn
)
253 return btr_referenced_p (insn
, NULL
) ? btr_reference_found
: NULL
;
256 /* Find the group that the target register definition DEF belongs
257 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
258 group exists, create one. Add def to the group. */
260 find_btr_def_group (btr_def_group
*all_btr_def_groups
, btr_def def
)
262 if (insn_sets_btr_p (def
->insn
, 1, NULL
))
264 btr_def_group this_group
;
265 rtx def_src
= SET_SRC (single_set (def
->insn
));
267 /* ?? This linear search is an efficiency concern, particularly
268 as the search will almost always fail to find a match. */
269 for (this_group
= *all_btr_def_groups
;
271 this_group
= this_group
->next
)
272 if (rtx_equal_p (def_src
, this_group
->src
))
277 this_group
= obstack_alloc (&migrate_btrl_obstack
,
278 sizeof (struct btr_def_group_s
));
279 this_group
->src
= def_src
;
280 this_group
->members
= NULL
;
281 this_group
->next
= *all_btr_def_groups
;
282 *all_btr_def_groups
= this_group
;
284 def
->group
= this_group
;
285 def
->next_this_group
= this_group
->members
;
286 this_group
->members
= def
;
292 /* Create a new target register definition structure, for a definition in
293 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
294 the new definition. */
296 add_btr_def (fibheap_t all_btr_defs
, basic_block bb
, int insn_luid
, rtx insn
,
297 unsigned int dest_reg
, int other_btr_uses_before_def
,
298 btr_def_group
*all_btr_def_groups
)
301 = obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_def_s
));
303 this->luid
= insn_luid
;
305 this->btr
= dest_reg
;
306 this->cost
= basic_block_freq (bb
);
307 this->has_ambiguous_use
= 0;
308 this->other_btr_uses_before_def
= other_btr_uses_before_def
;
309 this->other_btr_uses_after_use
= 0;
310 this->next_this_bb
= NULL
;
311 this->next_this_group
= NULL
;
313 this->live_range
= NULL
;
314 find_btr_def_group (all_btr_def_groups
, this);
316 fibheap_insert (all_btr_defs
, -this->cost
, this);
319 fprintf (rtl_dump_file
,
320 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
321 dest_reg
, bb
->index
, INSN_UID (insn
), (this->group
? "" : ":not const"),
327 /* Create a new target register user structure, for a use in block BB,
328 instruction INSN. Return the new user. */
330 new_btr_user (basic_block bb
, int insn_luid
, rtx insn
)
332 /* This instruction reads target registers. We need
333 to decide whether we can replace all target register
336 rtx
*usep
= find_btr_use (PATTERN (insn
));
338 btr_user user
= NULL
;
342 int unambiguous_single_use
;
344 /* We want to ensure that USE is the only use of a target
345 register in INSN, so that we know that to rewrite INSN to use
346 a different target register, all we have to do is replace USE. */
347 unambiguous_single_use
= !btr_referenced_p (PATTERN (insn
), usep
);
348 if (!unambiguous_single_use
)
351 use
= usep
? *usep
: NULL_RTX
;
352 user
= obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_user_s
));
354 user
->luid
= insn_luid
;
357 user
->other_use_this_block
= 0;
359 user
->n_reaching_defs
= 0;
360 user
->first_reaching_def
= -1;
364 fprintf (rtl_dump_file
, "Uses target reg: { bb %d, insn %d }",
365 bb
->index
, INSN_UID (insn
));
368 fprintf (rtl_dump_file
, ": unambiguous use of reg %d\n",
375 /* Write the contents of S to the dump file. */
377 dump_hard_reg_set (HARD_REG_SET s
)
380 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
381 if (TEST_HARD_REG_BIT (s
, reg
))
382 fprintf (rtl_dump_file
, " %d", reg
);
385 /* Write the set of target regs live in block BB to the dump file. */
387 dump_btrs_live (int bb
)
389 fprintf (rtl_dump_file
, "BB%d live:", bb
);
390 dump_hard_reg_set (btrs_live
[bb
]);
391 fprintf (rtl_dump_file
, "\n");
394 /* REGNO is the number of a branch target register that is being used or
395 set. USERS_THIS_BB is a list of preceding branch target register users;
396 If any of them use the same register, set their other_use_this_block
399 note_other_use_this_block (unsigned int regno
, btr_user users_this_bb
)
403 for (user
= users_this_bb
; user
!= NULL
; user
= user
->next
)
404 if (user
->use
&& REGNO (user
->use
) == regno
)
405 user
->other_use_this_block
= 1;
409 btr_user users_this_bb
;
410 HARD_REG_SET btrs_written_in_block
;
411 HARD_REG_SET btrs_live_in_block
;
416 /* Called via note_stores or directly to register stores into /
417 clobbers of a branch target register DEST that are not recognized as
418 straightforward definitions. DATA points to information about the
419 current basic block that needs updating. */
421 note_btr_set (rtx dest
, rtx set ATTRIBUTE_UNUSED
, void *data
)
423 defs_uses_info
*info
= data
;
424 int regno
, end_regno
;
426 if (GET_CODE (dest
) != REG
)
428 regno
= REGNO (dest
);
429 end_regno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
430 for (; regno
< end_regno
; regno
++)
431 if (TEST_HARD_REG_BIT (all_btrs
, regno
))
433 note_other_use_this_block (regno
, info
->users_this_bb
);
434 SET_HARD_REG_BIT (info
->btrs_written_in_block
, regno
);
435 SET_HARD_REG_BIT (info
->btrs_live_in_block
, regno
);
436 sbitmap_difference (info
->bb_gen
, info
->bb_gen
,
437 info
->btr_defset
[regno
- first_btr
]);
442 compute_defs_uses_and_gen (fibheap_t all_btr_defs
, btr_def
*def_array
,
443 btr_user
*use_array
, sbitmap
*btr_defset
,
444 sbitmap
*bb_gen
, HARD_REG_SET
*btrs_written
)
446 /* Scan the code building up the set of all defs and all uses.
447 For each target register, build the set of defs of that register.
448 For each block, calculate the set of target registers
449 written in that block.
450 Also calculate the set of btrs ever live in that block.
454 btr_def_group all_btr_def_groups
= NULL
;
457 sbitmap_vector_zero (bb_gen
, n_basic_blocks
);
458 for (i
= 0; i
< n_basic_blocks
; i
++)
460 basic_block bb
= BASIC_BLOCK (i
);
462 btr_def defs_this_bb
= NULL
;
466 info
.users_this_bb
= NULL
;
467 info
.bb_gen
= bb_gen
[i
];
468 info
.btr_defset
= btr_defset
;
470 CLEAR_HARD_REG_SET (info
.btrs_live_in_block
);
471 CLEAR_HARD_REG_SET (info
.btrs_written_in_block
);
472 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
473 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
474 && REGNO_REG_SET_P (bb
->global_live_at_start
, reg
))
475 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
477 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
));
479 insn
= NEXT_INSN (insn
), insn_luid
++)
484 int insn_uid
= INSN_UID (insn
);
486 if (insn_sets_btr_p (insn
, 0, ®no
))
488 btr_def def
= add_btr_def (
489 all_btr_defs
, bb
, insn_luid
, insn
, regno
,
490 TEST_HARD_REG_BIT (info
.btrs_live_in_block
, regno
),
491 &all_btr_def_groups
);
493 def_array
[insn_uid
] = def
;
494 SET_HARD_REG_BIT (info
.btrs_written_in_block
, regno
);
495 SET_HARD_REG_BIT (info
.btrs_live_in_block
, regno
);
496 sbitmap_difference (bb_gen
[i
], bb_gen
[i
],
497 btr_defset
[regno
- first_btr
]);
498 SET_BIT (bb_gen
[i
], insn_uid
);
499 def
->next_this_bb
= defs_this_bb
;
501 SET_BIT (btr_defset
[regno
- first_btr
], insn_uid
);
502 note_other_use_this_block (regno
, info
.users_this_bb
);
506 if (btr_referenced_p (PATTERN (insn
), NULL
))
508 btr_user user
= new_btr_user (bb
, insn_luid
, insn
);
510 use_array
[insn_uid
] = user
;
512 SET_HARD_REG_BIT (info
.btrs_live_in_block
,
517 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
518 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
519 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
522 note_other_use_this_block (reg
,
524 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
526 note_stores (PATTERN (insn
), note_btr_set
, &info
);
528 user
->next
= info
.users_this_bb
;
529 info
.users_this_bb
= user
;
531 if (GET_CODE (insn
) == CALL_INSN
)
533 HARD_REG_SET
*clobbered
= &call_used_reg_set
;
534 HARD_REG_SET call_saved
;
535 rtx pat
= PATTERN (insn
);
538 /* Check for sibcall. */
539 if (GET_CODE (pat
) == PARALLEL
)
540 for (i
= XVECLEN (pat
, 0) - 1; i
>= 0; i
--)
541 if (GET_CODE (XVECEXP (pat
, 0, i
)) == RETURN
)
543 COMPL_HARD_REG_SET (call_saved
,
545 clobbered
= &call_saved
;
548 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
549 if (TEST_HARD_REG_BIT (*clobbered
, regno
))
550 note_btr_set (regno_reg_rtx
[regno
], NULL_RTX
, &info
);
556 COPY_HARD_REG_SET (btrs_live
[i
], info
.btrs_live_in_block
);
557 COPY_HARD_REG_SET (btrs_written
[i
], info
.btrs_written_in_block
);
564 compute_kill (sbitmap
*bb_kill
, sbitmap
*btr_defset
,
565 HARD_REG_SET
*btrs_written
)
570 /* For each basic block, form the set BB_KILL - the set
571 of definitions that the block kills. */
572 sbitmap_vector_zero (bb_kill
, n_basic_blocks
);
573 for (i
= 0; i
< n_basic_blocks
; i
++)
575 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
576 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
577 && TEST_HARD_REG_BIT (btrs_written
[i
], regno
))
578 sbitmap_a_or_b (bb_kill
[i
], bb_kill
[i
],
579 btr_defset
[regno
- first_btr
]);
584 compute_out (sbitmap
*bb_out
, sbitmap
*bb_gen
, sbitmap
*bb_kill
, int max_uid
)
586 /* Perform iterative dataflow:
587 Initially, for all blocks, BB_OUT = BB_GEN.
589 BB_IN = union over predecessors of BB_OUT(pred)
590 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
591 Iterate until the bb_out sets stop growing. */
594 sbitmap bb_in
= sbitmap_alloc (max_uid
);
596 for (i
= 0; i
< n_basic_blocks
; i
++)
597 sbitmap_copy (bb_out
[i
], bb_gen
[i
]);
603 for (i
= 0; i
< n_basic_blocks
; i
++)
605 sbitmap_union_of_preds (bb_in
, bb_out
, i
);
606 changed
|= sbitmap_union_of_diff_cg (bb_out
[i
], bb_gen
[i
],
610 sbitmap_free (bb_in
);
614 link_btr_uses (btr_def
*def_array
, btr_user
*use_array
, sbitmap
*bb_out
,
615 sbitmap
*btr_defset
, int max_uid
)
618 sbitmap reaching_defs
= sbitmap_alloc (max_uid
);
620 /* Link uses to the uses lists of all of their reaching defs.
621 Count up the number of reaching defs of each use. */
622 for (i
= 0; i
< n_basic_blocks
; i
++)
624 basic_block bb
= BASIC_BLOCK (i
);
628 sbitmap_union_of_preds (reaching_defs
, bb_out
, i
);
629 for (insn
= BB_HEAD (bb
), last
= NEXT_INSN (BB_END (bb
));
631 insn
= NEXT_INSN (insn
))
635 int insn_uid
= INSN_UID (insn
);
637 btr_def def
= def_array
[insn_uid
];
638 btr_user user
= use_array
[insn_uid
];
641 /* Remove all reaching defs of regno except
643 sbitmap_difference (reaching_defs
, reaching_defs
,
644 btr_defset
[def
->btr
- first_btr
]);
645 SET_BIT(reaching_defs
, insn_uid
);
650 /* Find all the reaching defs for this use. */
651 sbitmap reaching_defs_of_reg
= sbitmap_alloc(max_uid
);
656 reaching_defs_of_reg
,
658 btr_defset
[REGNO (user
->use
) - first_btr
]);
663 sbitmap_zero (reaching_defs_of_reg
);
664 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
665 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
666 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
668 sbitmap_a_or_b_and_c (reaching_defs_of_reg
,
669 reaching_defs_of_reg
,
671 btr_defset
[reg
- first_btr
]);
673 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg
, 0, uid
,
675 btr_def def
= def_array
[uid
];
677 /* We now know that def reaches user. */
680 fprintf (rtl_dump_file
,
681 "Def in insn %d reaches use in insn %d\n",
684 user
->n_reaching_defs
++;
686 def
->has_ambiguous_use
= 1;
687 if (user
->first_reaching_def
!= -1)
688 { /* There is more than one reaching def. This is
689 a rare case, so just give up on this def/use
690 web when it occurs. */
691 def
->has_ambiguous_use
= 1;
692 def_array
[user
->first_reaching_def
]
693 ->has_ambiguous_use
= 1;
695 fprintf (rtl_dump_file
,
696 "(use %d has multiple reaching defs)\n",
700 user
->first_reaching_def
= uid
;
701 if (user
->other_use_this_block
)
702 def
->other_btr_uses_after_use
= 1;
703 user
->next
= def
->uses
;
706 sbitmap_free (reaching_defs_of_reg
);
709 if (GET_CODE (insn
) == CALL_INSN
)
713 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
714 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
715 && TEST_HARD_REG_BIT (call_used_reg_set
, regno
))
716 sbitmap_difference (reaching_defs
, reaching_defs
,
717 btr_defset
[regno
- first_btr
]);
722 sbitmap_free (reaching_defs
);
726 build_btr_def_use_webs (fibheap_t all_btr_defs
)
728 const int max_uid
= get_max_uid ();
729 btr_def
*def_array
= xcalloc (max_uid
, sizeof (btr_def
));
730 btr_user
*use_array
= xcalloc (max_uid
, sizeof (btr_user
));
731 sbitmap
*btr_defset
= sbitmap_vector_alloc (
732 (last_btr
- first_btr
) + 1, max_uid
);
733 sbitmap
*bb_gen
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
734 HARD_REG_SET
*btrs_written
= xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
738 sbitmap_vector_zero (btr_defset
, (last_btr
- first_btr
) + 1);
740 compute_defs_uses_and_gen (all_btr_defs
, def_array
, use_array
, btr_defset
,
741 bb_gen
, btrs_written
);
743 bb_kill
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
744 compute_kill (bb_kill
, btr_defset
, btrs_written
);
747 bb_out
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
748 compute_out (bb_out
, bb_gen
, bb_kill
, max_uid
);
750 sbitmap_vector_free (bb_gen
);
751 sbitmap_vector_free (bb_kill
);
753 link_btr_uses (def_array
, use_array
, bb_out
, btr_defset
, max_uid
);
755 sbitmap_vector_free (bb_out
);
756 sbitmap_vector_free (btr_defset
);
761 /* Return true if basic block BB contains the start or end of the
762 live range of the definition DEF, AND there are other live
763 ranges of the same target register that include BB. */
765 block_at_edge_of_live_range_p (int bb
, btr_def def
)
767 if (def
->other_btr_uses_before_def
&& BASIC_BLOCK (bb
) == def
->bb
)
769 else if (def
->other_btr_uses_after_use
)
772 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
773 if (BASIC_BLOCK (bb
) == user
->bb
)
779 /* We are removing the def/use web DEF. The target register
780 used in this web is therefore no longer live in the live range
781 of this web, so remove it from the live set of all basic blocks
782 in the live range of the web.
783 Blocks at the boundary of the live range may contain other live
784 ranges for the same target register, so we have to be careful
785 to remove the target register from the live set of these blocks
786 only if they do not contain other live ranges for the same register. */
788 clear_btr_from_live_range (btr_def def
)
792 EXECUTE_IF_SET_IN_BITMAP
793 (def
->live_range
, 0, bb
,
795 if ((!def
->other_btr_uses_before_def
796 && !def
->other_btr_uses_after_use
)
797 || !block_at_edge_of_live_range_p (bb
, def
))
799 CLEAR_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
807 /* We are adding the def/use web DEF. Add the target register used
808 in this web to the live set of all of the basic blocks that contain
809 the live range of the web. */
811 add_btr_to_live_range (btr_def def
)
814 EXECUTE_IF_SET_IN_BITMAP
815 (def
->live_range
, 0, bb
,
817 SET_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
823 /* Update a live range to contain the basic block NEW_BLOCK, and all
824 blocks on paths between the existing live range and NEW_BLOCK.
825 HEAD is a block contained in the existing live range that dominates
826 all other blocks in the existing live range.
827 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
828 are live in the blocks that we add to the live range.
829 It is a precondition that either NEW_BLOCK dominates HEAD,or
830 HEAD dom NEW_BLOCK. This is used to speed up the
831 implementation of this function. */
833 augment_live_range (bitmap live_range
, HARD_REG_SET
*btrs_live_in_range
,
834 basic_block head_bb
, basic_block new_bb
)
836 basic_block
*worklist
, *tos
;
838 tos
= worklist
= xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
840 if (dominated_by_p (CDI_DOMINATORS
, new_bb
, head_bb
))
842 else if (dominated_by_p (CDI_DOMINATORS
, head_bb
, new_bb
))
845 int new_block
= new_bb
->index
;
847 bitmap_set_bit (live_range
, new_block
);
848 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[new_block
]);
851 fprintf (rtl_dump_file
,
852 "Adding block %d to live range\n", new_block
);
853 fprintf (rtl_dump_file
,"Now live btrs are ");
854 dump_hard_reg_set (*btrs_live_in_range
);
855 fprintf (rtl_dump_file
, "\n");
857 for (e
= head_bb
->pred
; e
; e
= e
->pred_next
)
863 while (tos
!= worklist
)
865 basic_block bb
= *--tos
;
866 if (!bitmap_bit_p (live_range
, bb
->index
))
870 bitmap_set_bit (live_range
, bb
->index
);
871 IOR_HARD_REG_SET (*btrs_live_in_range
,
872 btrs_live
[bb
->index
]);
875 fprintf (rtl_dump_file
,
876 "Adding block %d to live range\n", bb
->index
);
877 fprintf (rtl_dump_file
,"Now live btrs are ");
878 dump_hard_reg_set (*btrs_live_in_range
);
879 fprintf (rtl_dump_file
, "\n");
882 for (e
= bb
->pred
; e
!= NULL
; e
= e
->pred_next
)
884 basic_block pred
= e
->src
;
885 if (!bitmap_bit_p (live_range
, pred
->index
))
894 /* Return the most desirable target register that is not in
895 the set USED_BTRS. */
897 choose_btr (HARD_REG_SET used_btrs
)
900 GO_IF_HARD_REG_SUBSET (all_btrs
, used_btrs
, give_up
);
902 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
904 #ifdef REG_ALLOC_ORDER
905 int regno
= reg_alloc_order
[i
];
909 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
910 && !TEST_HARD_REG_BIT (used_btrs
, regno
))
917 /* Calculate the set of basic blocks that contain the live range of
919 Also calculate the set of target registers that are live at time
920 in this live range, but ignore the live range represented by DEF
921 when calculating this set. */
923 btr_def_live_range (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
925 if (!def
->live_range
)
929 def
->live_range
= BITMAP_XMALLOC ();
931 bitmap_set_bit (def
->live_range
, def
->bb
->index
);
932 COPY_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[def
->bb
->index
]);
934 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
935 augment_live_range (def
->live_range
, btrs_live_in_range
,
940 /* def->live_range is accurate, but we need to recompute
941 the set of target registers live over it, because migration
942 of other PT instructions may have affected it.
946 CLEAR_HARD_REG_SET (*btrs_live_in_range
);
947 EXECUTE_IF_SET_IN_BITMAP
948 (def
->live_range
, 0, bb
,
950 IOR_HARD_REG_SET (*btrs_live_in_range
,
954 if (!def
->other_btr_uses_before_def
&&
955 !def
->other_btr_uses_after_use
)
956 CLEAR_HARD_REG_BIT (*btrs_live_in_range
, def
->btr
);
959 /* Merge into the def/use web DEF any other def/use webs in the same
960 group that are dominated by DEF, provided that there is a target
961 register available to allocate to the merged web. */
963 combine_btr_defs (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
967 for (other_def
= def
->group
->members
;
969 other_def
= other_def
->next_this_group
)
972 && other_def
->uses
!= NULL
973 && ! other_def
->has_ambiguous_use
974 && dominated_by_p (CDI_DOMINATORS
, other_def
->bb
, def
->bb
))
976 /* def->bb dominates the other def, so def and other_def could
978 /* Merge their live ranges, and get the set of
979 target registers live over the merged range. */
981 HARD_REG_SET combined_btrs_live
;
982 bitmap combined_live_range
= BITMAP_XMALLOC ();
985 if (other_def
->live_range
== NULL
)
987 HARD_REG_SET dummy_btrs_live_in_range
;
988 btr_def_live_range (other_def
, &dummy_btrs_live_in_range
);
990 COPY_HARD_REG_SET (combined_btrs_live
, *btrs_live_in_range
);
991 bitmap_copy (combined_live_range
, def
->live_range
);
993 for (user
= other_def
->uses
; user
!= NULL
; user
= user
->next
)
994 augment_live_range (combined_live_range
, &combined_btrs_live
,
997 btr
= choose_btr (combined_btrs_live
);
1000 /* We can combine them. */
1002 fprintf (rtl_dump_file
,
1003 "Combining def in insn %d with def in insn %d\n",
1004 INSN_UID (other_def
->insn
), INSN_UID (def
->insn
));
1007 user
= other_def
->uses
;
1008 while (user
!= NULL
)
1010 btr_user next
= user
->next
;
1012 user
->next
= def
->uses
;
1016 /* Combining def/use webs can make target registers live
1017 after uses where they previously were not. This means
1018 some REG_DEAD notes may no longer be correct. We could
1019 be more precise about this if we looked at the combined
1020 live range, but here I just delete any REG_DEAD notes
1021 in case they are no longer correct. */
1022 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1023 remove_note (user
->insn
,
1024 find_regno_note (user
->insn
, REG_DEAD
,
1025 REGNO (user
->use
)));
1026 clear_btr_from_live_range (other_def
);
1027 other_def
->uses
= NULL
;
1028 bitmap_copy (def
->live_range
, combined_live_range
);
1029 if (other_def
->other_btr_uses_after_use
)
1030 def
->other_btr_uses_after_use
= 1;
1031 COPY_HARD_REG_SET (*btrs_live_in_range
, combined_btrs_live
);
1033 /* Delete the old target register initialization. */
1034 delete_insn (other_def
->insn
);
1037 BITMAP_XFREE (combined_live_range
);
1042 /* Move the definition DEF from its current position to basic
1043 block NEW_DEF_BB, and modify it to use branch target register BTR.
1044 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1045 Update all reaching uses of DEF in the RTL to use BTR.
1046 If this new position means that other defs in the
1047 same group can be combined with DEF then combine them. */
1049 move_btr_def (basic_block new_def_bb
, int btr
, btr_def def
, bitmap live_range
,
1050 HARD_REG_SET
*btrs_live_in_range
)
1052 /* We can move the instruction.
1053 Set a target register in block NEW_DEF_BB to the value
1054 needed for this target register definition.
1055 Replace all uses of the old target register definition by
1056 uses of the new definition. Delete the old definition. */
1057 basic_block b
= new_def_bb
;
1058 rtx insp
= BB_HEAD (b
);
1059 rtx old_insn
= def
->insn
;
1063 enum machine_mode btr_mode
;
1068 fprintf(rtl_dump_file
, "migrating to basic block %d, using reg %d\n",
1069 new_def_bb
->index
, btr
);
1071 clear_btr_from_live_range (def
);
1073 def
->bb
= new_def_bb
;
1075 def
->cost
= basic_block_freq (new_def_bb
);
1076 def
->other_btr_uses_before_def
= 0;
1077 bitmap_copy (def
->live_range
, live_range
);
1078 combine_btr_defs (def
, btrs_live_in_range
);
1080 add_btr_to_live_range (def
);
1081 if (GET_CODE (insp
) == CODE_LABEL
)
1082 insp
= NEXT_INSN (insp
);
1083 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1084 optimizations can result in insp being both first and last insn of
1086 /* ?? some assertions to check that insp is sensible? */
1088 set
= single_set (old_insn
);
1089 src
= SET_SRC (set
);
1090 btr_mode
= GET_MODE (SET_DEST (set
));
1091 btr_rtx
= gen_rtx (REG
, btr_mode
, btr
);
1093 new_insn
= gen_move_insn (btr_rtx
, src
);
1095 /* Insert target register initialization at head of basic block. */
1096 def
->insn
= emit_insn_after (new_insn
, insp
);
1098 regs_ever_live
[btr
] = 1;
1101 fprintf (rtl_dump_file
, "New pt is insn %d, inserted after insn %d\n",
1102 INSN_UID (def
->insn
), INSN_UID (insp
));
1104 /* Delete the old target register initialization. */
1105 delete_insn (old_insn
);
1107 /* Replace each use of the old target register by a use of the new target
1109 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1111 /* Some extra work here to ensure consistent modes, because
1112 it seems that a target register REG rtx can be given a different
1113 mode depending on the context (surely that should not be
1115 rtx replacement_rtx
;
1116 if (GET_MODE (user
->use
) == GET_MODE (btr_rtx
)
1117 || GET_MODE (user
->use
) == VOIDmode
)
1118 replacement_rtx
= btr_rtx
;
1120 replacement_rtx
= gen_rtx (REG
, GET_MODE (user
->use
), btr
);
1121 replace_rtx (user
->insn
, user
->use
, replacement_rtx
);
1122 user
->use
= replacement_rtx
;
1126 /* We anticipate intra-block scheduling to be done. See if INSN could move
1127 up within BB by N_INSNS. */
1129 can_move_up (basic_block bb
, rtx insn
, int n_insns
)
1131 while (insn
!= BB_HEAD (bb
) && n_insns
> 0)
1133 insn
= PREV_INSN (insn
);
1134 /* ??? What if we have an anti-dependency that actually prevents the
1135 scheduler from doing the move? We'd like to re-allocate the register,
1136 but not necessarily put the load into another basic block. */
1140 return n_insns
<= 0;
1143 /* Attempt to migrate the target register definition DEF to an
1144 earlier point in the flowgraph.
1146 It is a precondition of this function that DEF is migratable:
1147 i.e. it has a constant source, and all uses are unambiguous.
1149 Only migrations that reduce the cost of DEF will be made.
1150 MIN_COST is the lower bound on the cost of the DEF after migration.
1151 If we migrate DEF so that its cost falls below MIN_COST,
1152 then we do not attempt to migrate further. The idea is that
1153 we migrate definitions in a priority order based on their cost,
1154 when the cost of this definition falls below MIN_COST, then
1155 there is another definition with cost == MIN_COST which now
1156 has a higher priority than this definition.
1158 Return nonzero if there may be benefit from attempting to
1159 migrate this DEF further (i.e. we have reduced the cost below
1160 MIN_COST, but we may be able to reduce it further).
1161 Return zero if no further migration is possible. */
1163 migrate_btr_def (btr_def def
, int min_cost
)
1166 HARD_REG_SET btrs_live_in_range
;
1167 int btr_used_near_def
= 0;
1168 int def_basic_block_freq
;
1173 int def_latency
= 1;
1176 fprintf (rtl_dump_file
,
1177 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1178 INSN_UID (def
->insn
), def
->cost
, min_cost
);
1180 if (!def
->group
|| def
->has_ambiguous_use
)
1181 /* These defs are not migratable. */
1184 fprintf (rtl_dump_file
, "it's not migratable\n");
1189 /* We have combined this def with another in the same group, so
1190 no need to consider it further.
1194 fprintf (rtl_dump_file
, "it's already combined with another pt\n");
1198 btr_def_live_range (def
, &btrs_live_in_range
);
1199 live_range
= BITMAP_XMALLOC ();
1200 bitmap_copy (live_range
, def
->live_range
);
1202 #ifdef INSN_SCHEDULING
1203 if ((*targetm
.sched
.use_dfa_pipeline_interface
) ())
1204 def_latency
= insn_default_latency (def
->insn
);
1206 def_latency
= result_ready_cost (def
->insn
);
1209 def_latency
*= issue_rate
;
1211 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1213 if (user
->bb
== def
->bb
1214 && user
->luid
> def
->luid
1215 && (def
->luid
+ def_latency
) > user
->luid
1216 && ! can_move_up (def
->bb
, def
->insn
,
1217 (def
->luid
+ def_latency
) - user
->luid
))
1219 btr_used_near_def
= 1;
1224 def_basic_block_freq
= basic_block_freq (def
->bb
);
1226 for (try = get_immediate_dominator (CDI_DOMINATORS
, def
->bb
);
1227 !give_up
&& try && try != ENTRY_BLOCK_PTR
&& def
->cost
>= min_cost
;
1228 try = get_immediate_dominator (CDI_DOMINATORS
, try))
1230 /* Try to move the instruction that sets the target register into
1232 int try_freq
= basic_block_freq (try);
1235 fprintf (rtl_dump_file
, "trying block %d ...", try->index
);
1237 if (try_freq
< def_basic_block_freq
1238 || (try_freq
== def_basic_block_freq
&& btr_used_near_def
))
1241 augment_live_range (live_range
, &btrs_live_in_range
, def
->bb
, try);
1244 fprintf (rtl_dump_file
, "Now btrs live in range are: ");
1245 dump_hard_reg_set (btrs_live_in_range
);
1246 fprintf (rtl_dump_file
, "\n");
1248 btr
= choose_btr (btrs_live_in_range
);
1251 move_btr_def (try, btr
, def
, live_range
, &btrs_live_in_range
);
1252 bitmap_copy(live_range
, def
->live_range
);
1253 btr_used_near_def
= 0;
1255 def_basic_block_freq
= basic_block_freq (def
->bb
);
1259 /* There are no free target registers available to move
1260 this far forward, so give up */
1263 fprintf (rtl_dump_file
,
1264 "giving up because there are no free target registers\n");
1273 fprintf (rtl_dump_file
, "failed to move\n");
1275 BITMAP_XFREE (live_range
);
1279 /* Attempt to move instructions that set target registers earlier
1280 in the flowgraph, away from their corresponding uses. */
1282 migrate_btr_defs (enum reg_class btr_class
, int allow_callee_save
)
1284 fibheap_t all_btr_defs
= fibheap_new ();
1287 gcc_obstack_init (&migrate_btrl_obstack
);
1292 for (i
= 0; i
< n_basic_blocks
; i
++)
1294 basic_block bb
= BASIC_BLOCK (i
);
1295 fprintf(rtl_dump_file
,
1296 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1297 " loop-depth = %d idom = %d\n",
1298 i
, (HOST_WIDEST_INT
) bb
->count
, bb
->loop_depth
,
1299 get_immediate_dominator (CDI_DOMINATORS
, bb
)->index
);
1303 CLEAR_HARD_REG_SET (all_btrs
);
1304 for (first_btr
= -1, reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
1305 if (TEST_HARD_REG_BIT (reg_class_contents
[(int) btr_class
], reg
)
1306 && (allow_callee_save
|| call_used_regs
[reg
] || regs_ever_live
[reg
]))
1308 SET_HARD_REG_BIT (all_btrs
, reg
);
1314 btrs_live
= xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
1316 build_btr_def_use_webs (all_btr_defs
);
1318 while (!fibheap_empty (all_btr_defs
))
1321 (btr_def
) fibheap_extract_min (all_btr_defs
);
1322 int min_cost
= -fibheap_min_key (all_btr_defs
);
1323 if (migrate_btr_def (def
, min_cost
))
1325 fibheap_insert (all_btr_defs
, -def
->cost
, (void *) def
);
1328 fprintf (rtl_dump_file
,
1329 "Putting insn %d back on queue with priority %d\n",
1330 INSN_UID (def
->insn
), def
->cost
);
1335 if (def
->live_range
)
1336 BITMAP_XFREE (def
->live_range
);
1341 obstack_free (&migrate_btrl_obstack
, NULL
);
1342 fibheap_delete (all_btr_defs
);
1346 branch_target_load_optimize (rtx insns
, bool after_prologue_epilogue_gen
)
1348 enum reg_class
class = (*targetm
.branch_target_register_class
) ();
1349 if (class != NO_REGS
)
1351 /* Initialize issue_rate. */
1352 if (targetm
.sched
.issue_rate
)
1353 issue_rate
= (*targetm
.sched
.issue_rate
) ();
1357 /* Build the CFG for migrate_btr_defs. */
1359 /* This may or may not be needed, depending on where we
1361 cleanup_cfg (optimize
? CLEANUP_EXPENSIVE
: 0);
1364 life_analysis (insns
, NULL
, 0);
1366 /* Dominator info is also needed for migrate_btr_def. */
1367 calculate_dominance_info (CDI_DOMINATORS
);
1368 migrate_btr_defs (class,
1369 ((*targetm
.branch_target_register_callee_saved
)
1370 (after_prologue_epilogue_gen
)));
1372 free_dominance_info (CDI_DOMINATORS
);
1374 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1375 PROP_DEATH_NOTES
| PROP_REG_INFO
);