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 /* Basic block dominator information used when migrating PT instructions */
159 static dominance_info dom
;
161 /* Array indexed by basic block number, giving the set of registers
162 live in that block. */
163 static HARD_REG_SET
*btrs_live
;
165 /* Set of all target registers that we are willing to allocate. */
166 static HARD_REG_SET all_btrs
;
168 /* Provide lower and upper bounds for target register numbers, so that
169 we don't need to search through all the hard registers all the time. */
170 static int first_btr
, last_btr
;
174 /* Return an estimate of the frequency of execution of block bb.
175 If we have a profiling count available, we could use it here. */
177 basic_block_freq (basic_block bb
)
179 return bb
->frequency
;
182 static rtx
*btr_reference_found
;
184 /* A subroutine of btr_referenced_p, called through for_each_rtx.
185 PREG is a pointer to an rtx that is to be excluded from the
186 traversal. If we find a reference to a target register anywhere
187 else, return 1, and put a pointer to it into btr_reference_found. */
189 find_btr_reference (rtx
*px
, void *preg
)
197 if (GET_CODE (x
) != REG
)
200 for (i
= HARD_REGNO_NREGS (regno
, GET_MODE (x
)) - 1; i
>= 0; i
--)
201 if (TEST_HARD_REG_BIT (all_btrs
, regno
+i
))
203 btr_reference_found
= px
;
209 /* Return nonzero if X references (sets or reads) any branch target register.
210 If EXCLUDEP is set, disregard any references within the rtx pointed to
211 by it. If returning nonzero, also set btr_reference_found as above. */
213 btr_referenced_p (rtx x
, rtx
*excludep
)
215 return for_each_rtx (&x
, find_btr_reference
, excludep
);
218 /* Return true if insn is an instruction that sets a target register.
219 if CHECK_CONST is true, only return true if the source is constant.
220 If such a set is found and REGNO is nonzero, assign the register number
221 of the destination register to *REGNO. */
223 insn_sets_btr_p (rtx insn
, int check_const
, int *regno
)
227 if (GET_CODE (insn
) == INSN
228 && (set
= single_set (insn
)))
230 rtx dest
= SET_DEST (set
);
231 rtx src
= SET_SRC (set
);
233 if (GET_CODE (dest
) == SUBREG
)
234 dest
= XEXP (dest
, 0);
236 if (GET_CODE (dest
) == REG
237 && TEST_HARD_REG_BIT (all_btrs
, REGNO (dest
)))
239 if (btr_referenced_p (src
, NULL
))
241 if (!check_const
|| CONSTANT_P (src
))
244 *regno
= REGNO (dest
);
252 /* Find and return a use of a target register within an instruction INSN. */
254 find_btr_use (rtx insn
)
256 return btr_referenced_p (insn
, NULL
) ? btr_reference_found
: NULL
;
259 /* Find the group that the target register definition DEF belongs
260 to in the list starting with *ALL_BTR_DEF_GROUPS. If no such
261 group exists, create one. Add def to the group. */
263 find_btr_def_group (btr_def_group
*all_btr_def_groups
, btr_def def
)
265 if (insn_sets_btr_p (def
->insn
, 1, NULL
))
267 btr_def_group this_group
;
268 rtx def_src
= SET_SRC (single_set (def
->insn
));
270 /* ?? This linear search is an efficiency concern, particularly
271 as the search will almost always fail to find a match. */
272 for (this_group
= *all_btr_def_groups
;
274 this_group
= this_group
->next
)
275 if (rtx_equal_p (def_src
, this_group
->src
))
280 this_group
= (btr_def_group
)
281 obstack_alloc (&migrate_btrl_obstack
,
282 sizeof (struct btr_def_group_s
));
283 this_group
->src
= def_src
;
284 this_group
->members
= NULL
;
285 this_group
->next
= *all_btr_def_groups
;
286 *all_btr_def_groups
= this_group
;
288 def
->group
= this_group
;
289 def
->next_this_group
= this_group
->members
;
290 this_group
->members
= def
;
296 /* Create a new target register definition structure, for a definition in
297 block BB, instruction INSN, and insert it into ALL_BTR_DEFS. Return
298 the new definition. */
300 add_btr_def (fibheap_t all_btr_defs
, basic_block bb
, int insn_luid
, rtx insn
,
301 unsigned int dest_reg
, int other_btr_uses_before_def
,
302 btr_def_group
*all_btr_def_groups
)
304 btr_def
this = (btr_def
)
305 obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_def_s
));
307 this->luid
= insn_luid
;
309 this->btr
= dest_reg
;
310 this->cost
= basic_block_freq (bb
);
311 this->has_ambiguous_use
= 0;
312 this->other_btr_uses_before_def
= other_btr_uses_before_def
;
313 this->other_btr_uses_after_use
= 0;
314 this->next_this_bb
= NULL
;
315 this->next_this_group
= NULL
;
317 this->live_range
= NULL
;
318 find_btr_def_group (all_btr_def_groups
, this);
320 fibheap_insert (all_btr_defs
, -this->cost
, this);
323 fprintf (rtl_dump_file
,
324 "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
325 dest_reg
, bb
->index
, INSN_UID (insn
), (this->group
? "" : ":not const"),
331 /* Create a new target register user structure, for a use in block BB,
332 instruction INSN. Return the new user. */
334 new_btr_user (basic_block bb
, int insn_luid
, rtx insn
)
336 /* This instruction reads target registers. We need
337 to decide whether we can replace all target register
340 rtx
*usep
= find_btr_use (PATTERN (insn
));
342 btr_user user
= NULL
;
346 int unambiguous_single_use
;
348 /* We want to ensure that USE is the only use of a target
349 register in INSN, so that we know that to rewrite INSN to use
350 a different target register, all we have to do is replace USE. */
351 unambiguous_single_use
= !btr_referenced_p (PATTERN (insn
), usep
);
352 if (!unambiguous_single_use
)
355 use
= usep
? *usep
: NULL_RTX
;
357 obstack_alloc (&migrate_btrl_obstack
, sizeof (struct btr_user_s
));
359 user
->luid
= insn_luid
;
362 user
->other_use_this_block
= 0;
364 user
->n_reaching_defs
= 0;
365 user
->first_reaching_def
= -1;
369 fprintf (rtl_dump_file
, "Uses target reg: { bb %d, insn %d }",
370 bb
->index
, INSN_UID (insn
));
373 fprintf (rtl_dump_file
, ": unambiguous use of reg %d\n",
380 /* Write the contents of S to the dump file. */
382 dump_hard_reg_set (HARD_REG_SET s
)
385 for (reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
386 if (TEST_HARD_REG_BIT (s
, reg
))
387 fprintf (rtl_dump_file
, " %d", reg
);
390 /* Write the set of target regs live in block BB to the dump file. */
392 dump_btrs_live (int bb
)
394 fprintf (rtl_dump_file
, "BB%d live:", bb
);
395 dump_hard_reg_set (btrs_live
[bb
]);
396 fprintf (rtl_dump_file
, "\n");
399 /* REGNO is the number of a branch target register that is being used or
400 set. USERS_THIS_BB is a list of preceding branch target register users;
401 If any of them use the same register, set their other_use_this_block
404 note_other_use_this_block (unsigned int regno
, btr_user users_this_bb
)
408 for (user
= users_this_bb
; user
!= NULL
; user
= user
->next
)
409 if (user
->use
&& REGNO (user
->use
) == regno
)
410 user
->other_use_this_block
= 1;
414 btr_user users_this_bb
;
415 HARD_REG_SET btrs_written_in_block
;
416 HARD_REG_SET btrs_live_in_block
;
421 /* Called via note_stores or directly to register stores into /
422 clobbers of a branch target register DEST that are not recognized as
423 straightforward definitions. DATA points to information about the
424 current basic block that needs updating. */
426 note_btr_set (rtx dest
, rtx set ATTRIBUTE_UNUSED
, void *data
)
428 defs_uses_info
*info
= data
;
429 int regno
, end_regno
;
431 if (GET_CODE (dest
) != REG
)
433 regno
= REGNO (dest
);
434 end_regno
= regno
+ HARD_REGNO_NREGS (regno
, GET_MODE (dest
));
435 for (; regno
< end_regno
; regno
++)
436 if (TEST_HARD_REG_BIT (all_btrs
, regno
))
438 note_other_use_this_block (regno
, info
->users_this_bb
);
439 SET_HARD_REG_BIT (info
->btrs_written_in_block
, regno
);
440 SET_HARD_REG_BIT (info
->btrs_live_in_block
, regno
);
441 sbitmap_difference (info
->bb_gen
, info
->bb_gen
,
442 info
->btr_defset
[regno
- first_btr
]);
447 compute_defs_uses_and_gen (fibheap_t all_btr_defs
, btr_def
*def_array
,
448 btr_user
*use_array
, sbitmap
*btr_defset
,
449 sbitmap
*bb_gen
, HARD_REG_SET
*btrs_written
)
451 /* Scan the code building up the set of all defs and all uses.
452 For each target register, build the set of defs of that register.
453 For each block, calculate the set of target registers
454 written in that block.
455 Also calculate the set of btrs ever live in that block.
459 btr_def_group all_btr_def_groups
= NULL
;
462 sbitmap_vector_zero (bb_gen
, n_basic_blocks
);
463 for (i
= 0; i
< n_basic_blocks
; i
++)
465 basic_block bb
= BASIC_BLOCK (i
);
467 btr_def defs_this_bb
= NULL
;
471 info
.users_this_bb
= NULL
;
472 info
.bb_gen
= bb_gen
[i
];
473 info
.btr_defset
= btr_defset
;
475 CLEAR_HARD_REG_SET (info
.btrs_live_in_block
);
476 CLEAR_HARD_REG_SET (info
.btrs_written_in_block
);
477 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
478 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
479 && REGNO_REG_SET_P (bb
->global_live_at_start
, reg
))
480 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
482 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
);
484 insn
= NEXT_INSN (insn
), insn_luid
++)
489 int insn_uid
= INSN_UID (insn
);
491 if (insn_sets_btr_p (insn
, 0, ®no
))
493 btr_def def
= add_btr_def (
494 all_btr_defs
, bb
, insn_luid
, insn
, regno
,
495 TEST_HARD_REG_BIT (info
.btrs_live_in_block
, regno
),
496 &all_btr_def_groups
);
498 def_array
[insn_uid
] = def
;
499 SET_HARD_REG_BIT (info
.btrs_written_in_block
, regno
);
500 SET_HARD_REG_BIT (info
.btrs_live_in_block
, regno
);
501 sbitmap_difference (bb_gen
[i
], bb_gen
[i
],
502 btr_defset
[regno
- first_btr
]);
503 SET_BIT (bb_gen
[i
], insn_uid
);
504 def
->next_this_bb
= defs_this_bb
;
506 SET_BIT (btr_defset
[regno
- first_btr
], insn_uid
);
507 note_other_use_this_block (regno
, info
.users_this_bb
);
511 if (btr_referenced_p (PATTERN (insn
), NULL
))
513 btr_user user
= new_btr_user (bb
, insn_luid
, insn
);
515 use_array
[insn_uid
] = user
;
517 SET_HARD_REG_BIT (info
.btrs_live_in_block
,
522 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
523 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
524 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
527 note_other_use_this_block (reg
,
529 SET_HARD_REG_BIT (info
.btrs_live_in_block
, reg
);
531 note_stores (PATTERN (insn
), note_btr_set
, &info
);
533 user
->next
= info
.users_this_bb
;
534 info
.users_this_bb
= user
;
536 if (GET_CODE (insn
) == CALL_INSN
)
538 HARD_REG_SET
*clobbered
= &call_used_reg_set
;
539 HARD_REG_SET call_saved
;
540 rtx pat
= PATTERN (insn
);
543 /* Check for sibcall. */
544 if (GET_CODE (pat
) == PARALLEL
)
545 for (i
= XVECLEN (pat
, 0) - 1; i
>= 0; i
--)
546 if (GET_CODE (XVECEXP (pat
, 0, i
)) == RETURN
)
548 COMPL_HARD_REG_SET (call_saved
,
550 clobbered
= &call_saved
;
553 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
554 if (TEST_HARD_REG_BIT (*clobbered
, regno
))
555 note_btr_set (regno_reg_rtx
[regno
], NULL_RTX
, &info
);
561 COPY_HARD_REG_SET (btrs_live
[i
], info
.btrs_live_in_block
);
562 COPY_HARD_REG_SET (btrs_written
[i
], info
.btrs_written_in_block
);
569 compute_kill (sbitmap
*bb_kill
, sbitmap
*btr_defset
,
570 HARD_REG_SET
*btrs_written
)
575 /* For each basic block, form the set BB_KILL - the set
576 of definitions that the block kills. */
577 sbitmap_vector_zero (bb_kill
, n_basic_blocks
);
578 for (i
= 0; i
< n_basic_blocks
; i
++)
580 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
581 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
582 && TEST_HARD_REG_BIT (btrs_written
[i
], regno
))
583 sbitmap_a_or_b (bb_kill
[i
], bb_kill
[i
],
584 btr_defset
[regno
- first_btr
]);
589 compute_out (sbitmap
*bb_out
, sbitmap
*bb_gen
, sbitmap
*bb_kill
, int max_uid
)
591 /* Perform iterative dataflow:
592 Initially, for all blocks, BB_OUT = BB_GEN.
594 BB_IN = union over predecessors of BB_OUT(pred)
595 BB_OUT = (BB_IN - BB_KILL) + BB_GEN
596 Iterate until the bb_out sets stop growing. */
599 sbitmap bb_in
= sbitmap_alloc (max_uid
);
601 for (i
= 0; i
< n_basic_blocks
; i
++)
602 sbitmap_copy (bb_out
[i
], bb_gen
[i
]);
608 for (i
= 0; i
< n_basic_blocks
; i
++)
610 sbitmap_union_of_preds (bb_in
, bb_out
, i
);
611 changed
|= sbitmap_union_of_diff_cg (bb_out
[i
], bb_gen
[i
],
615 sbitmap_free (bb_in
);
619 link_btr_uses (btr_def
*def_array
, btr_user
*use_array
, sbitmap
*bb_out
,
620 sbitmap
*btr_defset
, int max_uid
)
623 sbitmap reaching_defs
= sbitmap_alloc (max_uid
);
625 /* Link uses to the uses lists of all of their reaching defs.
626 Count up the number of reaching defs of each use. */
627 for (i
= 0; i
< n_basic_blocks
; i
++)
629 basic_block bb
= BASIC_BLOCK (i
);
633 sbitmap_union_of_preds (reaching_defs
, bb_out
, i
);
634 for (insn
= bb
->head
, last
= NEXT_INSN (bb
->end
);
636 insn
= NEXT_INSN (insn
))
640 int insn_uid
= INSN_UID (insn
);
642 btr_def def
= def_array
[insn_uid
];
643 btr_user user
= use_array
[insn_uid
];
646 /* Remove all reaching defs of regno except
648 sbitmap_difference (reaching_defs
, reaching_defs
,
649 btr_defset
[def
->btr
- first_btr
]);
650 SET_BIT(reaching_defs
, insn_uid
);
655 /* Find all the reaching defs for this use. */
656 sbitmap reaching_defs_of_reg
= sbitmap_alloc(max_uid
);
661 reaching_defs_of_reg
,
663 btr_defset
[REGNO (user
->use
) - first_btr
]);
668 sbitmap_zero (reaching_defs_of_reg
);
669 for (reg
= first_btr
; reg
<= last_btr
; reg
++)
670 if (TEST_HARD_REG_BIT (all_btrs
, reg
)
671 && refers_to_regno_p (reg
, reg
+ 1, user
->insn
,
673 sbitmap_a_or_b_and_c (reaching_defs_of_reg
,
674 reaching_defs_of_reg
,
676 btr_defset
[reg
- first_btr
]);
678 EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg
, 0, uid
,
680 btr_def def
= def_array
[uid
];
682 /* We now know that def reaches user. */
685 fprintf (rtl_dump_file
,
686 "Def in insn %d reaches use in insn %d\n",
689 user
->n_reaching_defs
++;
691 def
->has_ambiguous_use
= 1;
692 if (user
->first_reaching_def
!= -1)
693 { /* There is more than one reaching def. This is
694 a rare case, so just give up on this def/use
695 web when it occurs. */
696 def
->has_ambiguous_use
= 1;
697 def_array
[user
->first_reaching_def
]
698 ->has_ambiguous_use
= 1;
700 fprintf (rtl_dump_file
,
701 "(use %d has multiple reaching defs)\n",
705 user
->first_reaching_def
= uid
;
706 if (user
->other_use_this_block
)
707 def
->other_btr_uses_after_use
= 1;
708 user
->next
= def
->uses
;
711 sbitmap_free (reaching_defs_of_reg
);
714 if (GET_CODE (insn
) == CALL_INSN
)
718 for (regno
= first_btr
; regno
<= last_btr
; regno
++)
719 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
720 && TEST_HARD_REG_BIT (call_used_reg_set
, regno
))
721 sbitmap_difference (reaching_defs
, reaching_defs
,
722 btr_defset
[regno
- first_btr
]);
727 sbitmap_free (reaching_defs
);
731 build_btr_def_use_webs (fibheap_t all_btr_defs
)
733 const int max_uid
= get_max_uid ();
734 btr_def
*def_array
= xcalloc (max_uid
, sizeof (btr_def
));
735 btr_user
*use_array
= xcalloc (max_uid
, sizeof (btr_user
));
736 sbitmap
*btr_defset
= sbitmap_vector_alloc (
737 (last_btr
- first_btr
) + 1, max_uid
);
738 sbitmap
*bb_gen
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
739 HARD_REG_SET
*btrs_written
= (HARD_REG_SET
*) xcalloc (
740 n_basic_blocks
, sizeof (HARD_REG_SET
));
744 sbitmap_vector_zero (btr_defset
, (last_btr
- first_btr
) + 1);
746 compute_defs_uses_and_gen (all_btr_defs
, def_array
, use_array
, btr_defset
,
747 bb_gen
, btrs_written
);
749 bb_kill
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
750 compute_kill (bb_kill
, btr_defset
, btrs_written
);
753 bb_out
= sbitmap_vector_alloc (n_basic_blocks
, max_uid
);
754 compute_out (bb_out
, bb_gen
, bb_kill
, max_uid
);
756 sbitmap_vector_free (bb_gen
);
757 sbitmap_vector_free (bb_kill
);
759 link_btr_uses (def_array
, use_array
, bb_out
, btr_defset
, max_uid
);
761 sbitmap_vector_free (bb_out
);
762 sbitmap_vector_free (btr_defset
);
767 /* Return true if basic block BB contains the start or end of the
768 live range of the definition DEF, AND there are other live
769 ranges of the same target register that include BB. */
771 block_at_edge_of_live_range_p (int bb
, btr_def def
)
773 if (def
->other_btr_uses_before_def
&& BASIC_BLOCK (bb
) == def
->bb
)
775 else if (def
->other_btr_uses_after_use
)
778 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
779 if (BASIC_BLOCK (bb
) == user
->bb
)
785 /* We are removing the def/use web DEF. The target register
786 used in this web is therefore no longer live in the live range
787 of this web, so remove it from the live set of all basic blocks
788 in the live range of the web.
789 Blocks at the boundary of the live range may contain other live
790 ranges for the same target register, so we have to be careful
791 to remove the target register from the live set of these blocks
792 only if they do not contain other live ranges for the same register. */
794 clear_btr_from_live_range (btr_def def
)
798 EXECUTE_IF_SET_IN_BITMAP
799 (def
->live_range
, 0, bb
,
801 if ((!def
->other_btr_uses_before_def
802 && !def
->other_btr_uses_after_use
)
803 || !block_at_edge_of_live_range_p (bb
, def
))
805 CLEAR_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
813 /* We are adding the def/use web DEF. Add the target register used
814 in this web to the live set of all of the basic blocks that contain
815 the live range of the web. */
817 add_btr_to_live_range (btr_def def
)
820 EXECUTE_IF_SET_IN_BITMAP
821 (def
->live_range
, 0, bb
,
823 SET_HARD_REG_BIT (btrs_live
[bb
], def
->btr
);
829 /* Update a live range to contain the basic block NEW_BLOCK, and all
830 blocks on paths between the existing live range and NEW_BLOCK.
831 HEAD is a block contained in the existing live range that dominates
832 all other blocks in the existing live range.
833 Also add to the set BTRS_LIVE_IN_RANGE all target registers that
834 are live in the blocks that we add to the live range.
835 It is a precondition that either NEW_BLOCK dominates HEAD,or
836 HEAD dom NEW_BLOCK. This is used to speed up the
837 implementation of this function. */
839 augment_live_range (bitmap live_range
, HARD_REG_SET
*btrs_live_in_range
,
840 basic_block head_bb
, basic_block new_bb
)
842 basic_block
*worklist
, *tos
;
845 (basic_block
*) xmalloc (sizeof (basic_block
) * (n_basic_blocks
+ 1));
847 if (dominated_by_p (dom
, new_bb
, head_bb
))
849 else if (dominated_by_p (dom
, head_bb
, new_bb
))
852 int new_block
= new_bb
->index
;
854 bitmap_set_bit (live_range
, new_block
);
855 IOR_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[new_block
]);
858 fprintf (rtl_dump_file
,
859 "Adding block %d to live range\n", new_block
);
860 fprintf (rtl_dump_file
,"Now live btrs are ");
861 dump_hard_reg_set (*btrs_live_in_range
);
862 fprintf (rtl_dump_file
, "\n");
864 for (e
= head_bb
->pred
; e
; e
= e
->pred_next
)
870 while (tos
!= worklist
)
872 basic_block bb
= *--tos
;
873 if (!bitmap_bit_p (live_range
, bb
->index
))
877 bitmap_set_bit (live_range
, bb
->index
);
878 IOR_HARD_REG_SET (*btrs_live_in_range
,
879 btrs_live
[bb
->index
]);
882 fprintf (rtl_dump_file
,
883 "Adding block %d to live range\n", bb
->index
);
884 fprintf (rtl_dump_file
,"Now live btrs are ");
885 dump_hard_reg_set (*btrs_live_in_range
);
886 fprintf (rtl_dump_file
, "\n");
889 for (e
= bb
->pred
; e
!= NULL
; e
= e
->pred_next
)
891 basic_block pred
= e
->src
;
892 if (!bitmap_bit_p (live_range
, pred
->index
))
901 /* Return the most desirable target register that is not in
902 the set USED_BTRS. */
904 choose_btr (HARD_REG_SET used_btrs
)
907 GO_IF_HARD_REG_SUBSET (all_btrs
, used_btrs
, give_up
);
909 for (i
= 0; i
< FIRST_PSEUDO_REGISTER
; i
++)
911 #ifdef REG_ALLOC_ORDER
912 int regno
= reg_alloc_order
[i
];
916 if (TEST_HARD_REG_BIT (all_btrs
, regno
)
917 && !TEST_HARD_REG_BIT (used_btrs
, regno
))
924 /* Calculate the set of basic blocks that contain the live range of
926 Also calculate the set of target registers that are live at time
927 in this live range, but ignore the live range represented by DEF
928 when calculating this set. */
930 btr_def_live_range (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
932 if (!def
->live_range
)
936 def
->live_range
= BITMAP_XMALLOC ();
938 bitmap_set_bit (def
->live_range
, def
->bb
->index
);
939 COPY_HARD_REG_SET (*btrs_live_in_range
, btrs_live
[def
->bb
->index
]);
941 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
942 augment_live_range (def
->live_range
, btrs_live_in_range
,
947 /* def->live_range is accurate, but we need to recompute
948 the set of target registers live over it, because migration
949 of other PT instructions may have affected it.
953 CLEAR_HARD_REG_SET (*btrs_live_in_range
);
954 EXECUTE_IF_SET_IN_BITMAP
955 (def
->live_range
, 0, bb
,
957 IOR_HARD_REG_SET (*btrs_live_in_range
,
961 if (!def
->other_btr_uses_before_def
&&
962 !def
->other_btr_uses_after_use
)
963 CLEAR_HARD_REG_BIT (*btrs_live_in_range
, def
->btr
);
966 /* Merge into the def/use web DEF any other def/use webs in the same
967 group that are dominated by DEF, provided that there is a target
968 register available to allocate to the merged web. */
970 combine_btr_defs (btr_def def
, HARD_REG_SET
*btrs_live_in_range
)
974 for (other_def
= def
->group
->members
;
976 other_def
= other_def
->next_this_group
)
979 && other_def
->uses
!= NULL
980 && ! other_def
->has_ambiguous_use
981 && dominated_by_p (dom
, other_def
->bb
, def
->bb
))
983 /* def->bb dominates the other def, so def and other_def could
985 /* Merge their live ranges, and get the set of
986 target registers live over the merged range. */
988 HARD_REG_SET combined_btrs_live
;
989 bitmap combined_live_range
= BITMAP_XMALLOC ();
992 if (other_def
->live_range
== NULL
)
994 HARD_REG_SET dummy_btrs_live_in_range
;
995 btr_def_live_range (other_def
, &dummy_btrs_live_in_range
);
997 COPY_HARD_REG_SET (combined_btrs_live
, *btrs_live_in_range
);
998 bitmap_copy (combined_live_range
, def
->live_range
);
1000 for (user
= other_def
->uses
; user
!= NULL
; user
= user
->next
)
1001 augment_live_range (combined_live_range
, &combined_btrs_live
,
1004 btr
= choose_btr (combined_btrs_live
);
1007 /* We can combine them. */
1009 fprintf (rtl_dump_file
,
1010 "Combining def in insn %d with def in insn %d\n",
1011 INSN_UID (other_def
->insn
), INSN_UID (def
->insn
));
1014 user
= other_def
->uses
;
1015 while (user
!= NULL
)
1017 btr_user next
= user
->next
;
1019 user
->next
= def
->uses
;
1023 /* Combining def/use webs can make target registers live
1024 after uses where they previously were not. This means
1025 some REG_DEAD notes may no longer be correct. We could
1026 be more precise about this if we looked at the combined
1027 live range, but here I just delete any REG_DEAD notes
1028 in case they are no longer correct. */
1029 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1030 remove_note (user
->insn
,
1031 find_regno_note (user
->insn
, REG_DEAD
,
1032 REGNO (user
->use
)));
1033 clear_btr_from_live_range (other_def
);
1034 other_def
->uses
= NULL
;
1035 bitmap_copy (def
->live_range
, combined_live_range
);
1036 if (other_def
->other_btr_uses_after_use
)
1037 def
->other_btr_uses_after_use
= 1;
1038 COPY_HARD_REG_SET (*btrs_live_in_range
, combined_btrs_live
);
1040 /* Delete the old target register initialization. */
1041 delete_insn (other_def
->insn
);
1044 BITMAP_XFREE (combined_live_range
);
1049 /* Move the definition DEF from its current position to basic
1050 block NEW_DEF_BB, and modify it to use branch target register BTR.
1051 Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1052 Update all reaching uses of DEF in the RTL to use BTR.
1053 If this new position means that other defs in the
1054 same group can be combined with DEF then combine them. */
1056 move_btr_def (basic_block new_def_bb
, int btr
, btr_def def
, bitmap live_range
,
1057 HARD_REG_SET
*btrs_live_in_range
)
1059 /* We can move the instruction.
1060 Set a target register in block NEW_DEF_BB to the value
1061 needed for this target register definition.
1062 Replace all uses of the old target register definition by
1063 uses of the new definition. Delete the old definition. */
1064 basic_block b
= new_def_bb
;
1066 rtx old_insn
= def
->insn
;
1070 enum machine_mode btr_mode
;
1075 fprintf(rtl_dump_file
, "migrating to basic block %d, using reg %d\n",
1076 new_def_bb
->index
, btr
);
1078 clear_btr_from_live_range (def
);
1080 def
->bb
= new_def_bb
;
1082 def
->cost
= basic_block_freq (new_def_bb
);
1083 def
->other_btr_uses_before_def
= 0;
1084 bitmap_copy (def
->live_range
, live_range
);
1085 combine_btr_defs (def
, btrs_live_in_range
);
1087 add_btr_to_live_range (def
);
1088 if (GET_CODE (insp
) == CODE_LABEL
)
1089 insp
= NEXT_INSN (insp
);
1090 /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now. Some
1091 optimizations can result in insp being both first and last insn of
1093 /* ?? some assertions to check that insp is sensible? */
1095 set
= single_set (old_insn
);
1096 src
= SET_SRC (set
);
1097 btr_mode
= GET_MODE (SET_DEST (set
));
1098 btr_rtx
= gen_rtx (REG
, btr_mode
, btr
);
1100 new_insn
= gen_move_insn (btr_rtx
, src
);
1102 /* Insert target register initialization at head of basic block. */
1103 def
->insn
= emit_insn_after (new_insn
, insp
);
1105 regs_ever_live
[btr
] = 1;
1108 fprintf (rtl_dump_file
, "New pt is insn %d, inserted after insn %d\n",
1109 INSN_UID (def
->insn
), INSN_UID (insp
));
1111 /* Delete the old target register initialization. */
1112 delete_insn (old_insn
);
1114 /* Replace each use of the old target register by a use of the new target
1116 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1118 /* Some extra work here to ensure consistent modes, because
1119 it seems that a target register REG rtx can be given a different
1120 mode depending on the context (surely that should not be
1122 rtx replacement_rtx
;
1123 if (GET_MODE (user
->use
) == GET_MODE (btr_rtx
)
1124 || GET_MODE (user
->use
) == VOIDmode
)
1125 replacement_rtx
= btr_rtx
;
1127 replacement_rtx
= gen_rtx (REG
, GET_MODE (user
->use
), btr
);
1128 replace_rtx (user
->insn
, user
->use
, replacement_rtx
);
1129 user
->use
= replacement_rtx
;
1133 /* We anticipate intra-block scheduling to be done. See if INSN could move
1134 up within BB by N_INSNS. */
1136 can_move_up (basic_block bb
, rtx insn
, int n_insns
)
1138 while (insn
!= bb
->head
&& n_insns
> 0)
1140 insn
= PREV_INSN (insn
);
1141 /* ??? What if we have an anti-dependency that actually prevents the
1142 scheduler from doing the move? We'd like to re-allocate the register,
1143 but not necessarily put the load into another basic block. */
1147 return n_insns
<= 0;
1150 /* Attempt to migrate the target register definition DEF to an
1151 earlier point in the flowgraph.
1153 It is a precondition of this function that DEF is migratable:
1154 i.e. it has a constant source, and all uses are unambiguous.
1156 Only migrations that reduce the cost of DEF will be made.
1157 MIN_COST is the lower bound on the cost of the DEF after migration.
1158 If we migrate DEF so that its cost falls below MIN_COST,
1159 then we do not attempt to migrate further. The idea is that
1160 we migrate definitions in a priority order based on their cost,
1161 when the cost of this definition falls below MIN_COST, then
1162 there is another definition with cost == MIN_COST which now
1163 has a higher priority than this definition.
1165 Return nonzero if there may be benefit from attempting to
1166 migrate this DEF further (i.e. we have reduced the cost below
1167 MIN_COST, but we may be able to reduce it further).
1168 Return zero if no further migration is possible. */
1170 migrate_btr_def (btr_def def
, int min_cost
)
1173 HARD_REG_SET btrs_live_in_range
;
1174 int btr_used_near_def
= 0;
1175 int def_basic_block_freq
;
1180 int def_latency
= 1;
1183 fprintf (rtl_dump_file
,
1184 "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1185 INSN_UID (def
->insn
), def
->cost
, min_cost
);
1187 if (!def
->group
|| def
->has_ambiguous_use
)
1188 /* These defs are not migratable. */
1191 fprintf (rtl_dump_file
, "it's not migratable\n");
1196 /* We have combined this def with another in the same group, so
1197 no need to consider it further.
1201 fprintf (rtl_dump_file
, "it's already combined with another pt\n");
1205 btr_def_live_range (def
, &btrs_live_in_range
);
1206 live_range
= BITMAP_XMALLOC ();
1207 bitmap_copy (live_range
, def
->live_range
);
1209 #ifdef INSN_SCHEDULING
1210 if ((*targetm
.sched
.use_dfa_pipeline_interface
) ())
1211 def_latency
= insn_default_latency (def
->insn
);
1213 def_latency
= result_ready_cost (def
->insn
);
1216 def_latency
*= issue_rate
;
1218 for (user
= def
->uses
; user
!= NULL
; user
= user
->next
)
1220 if (user
->bb
== def
->bb
1221 && user
->luid
> def
->luid
1222 && (def
->luid
+ def_latency
) > user
->luid
1223 && ! can_move_up (def
->bb
, def
->insn
,
1224 (def
->luid
+ def_latency
) - user
->luid
))
1226 btr_used_near_def
= 1;
1231 def_basic_block_freq
= basic_block_freq (def
->bb
);
1233 for (try = get_immediate_dominator (dom
, def
->bb
);
1234 !give_up
&& try && try != ENTRY_BLOCK_PTR
&& def
->cost
>= min_cost
;
1235 try = get_immediate_dominator (dom
, try))
1237 /* Try to move the instruction that sets the target register into
1239 int try_freq
= basic_block_freq (try);
1242 fprintf (rtl_dump_file
, "trying block %d ...", try->index
);
1244 if (try_freq
< def_basic_block_freq
1245 || (try_freq
== def_basic_block_freq
&& btr_used_near_def
))
1248 augment_live_range (live_range
, &btrs_live_in_range
, def
->bb
, try);
1251 fprintf (rtl_dump_file
, "Now btrs live in range are: ");
1252 dump_hard_reg_set (btrs_live_in_range
);
1253 fprintf (rtl_dump_file
, "\n");
1255 btr
= choose_btr (btrs_live_in_range
);
1258 move_btr_def (try, btr
, def
, live_range
, &btrs_live_in_range
);
1259 bitmap_copy(live_range
, def
->live_range
);
1260 btr_used_near_def
= 0;
1262 def_basic_block_freq
= basic_block_freq (def
->bb
);
1266 /* There are no free target registers available to move
1267 this far forward, so give up */
1270 fprintf (rtl_dump_file
,
1271 "giving up because there are no free target registers\n");
1280 fprintf (rtl_dump_file
, "failed to move\n");
1282 BITMAP_XFREE (live_range
);
1286 /* Attempt to move instructions that set target registers earlier
1287 in the flowgraph, away from their corresponding uses. */
1289 migrate_btr_defs (enum reg_class btr_class
, int allow_callee_save
)
1291 fibheap_t all_btr_defs
= fibheap_new ();
1294 gcc_obstack_init (&migrate_btrl_obstack
);
1299 for (i
= 0; i
< n_basic_blocks
; i
++)
1301 basic_block bb
= BASIC_BLOCK (i
);
1302 fprintf(rtl_dump_file
,
1303 "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1304 " loop-depth = %d idom = %d\n",
1305 i
, (HOST_WIDEST_INT
) bb
->count
, bb
->loop_depth
,
1306 get_immediate_dominator (dom
, bb
)->index
);
1310 CLEAR_HARD_REG_SET (all_btrs
);
1311 for (first_btr
= -1, reg
= 0; reg
< FIRST_PSEUDO_REGISTER
; reg
++)
1312 if (TEST_HARD_REG_BIT (reg_class_contents
[(int) btr_class
], reg
)
1313 && (allow_callee_save
|| call_used_regs
[reg
] || regs_ever_live
[reg
]))
1315 SET_HARD_REG_BIT (all_btrs
, reg
);
1322 (HARD_REG_SET
*) xcalloc (n_basic_blocks
, sizeof (HARD_REG_SET
));
1324 build_btr_def_use_webs (all_btr_defs
);
1326 while (!fibheap_empty (all_btr_defs
))
1329 (btr_def
) fibheap_extract_min (all_btr_defs
);
1330 int min_cost
= -fibheap_min_key (all_btr_defs
);
1331 if (migrate_btr_def (def
, min_cost
))
1333 fibheap_insert (all_btr_defs
, -def
->cost
, (void *) def
);
1336 fprintf (rtl_dump_file
,
1337 "Putting insn %d back on queue with priority %d\n",
1338 INSN_UID (def
->insn
), def
->cost
);
1343 if (def
->live_range
)
1344 BITMAP_XFREE (def
->live_range
);
1349 obstack_free (&migrate_btrl_obstack
, NULL
);
1350 fibheap_delete (all_btr_defs
);
1354 branch_target_load_optimize (rtx insns
, bool after_prologue_epilogue_gen
)
1356 enum reg_class
class = (*targetm
.branch_target_register_class
) ();
1357 if (class != NO_REGS
)
1359 /* Initialize issue_rate. */
1360 if (targetm
.sched
.issue_rate
)
1361 issue_rate
= (*targetm
.sched
.issue_rate
) ();
1365 /* Build the CFG for migrate_btr_defs. */
1367 /* This may or may not be needed, depending on where we
1369 cleanup_cfg (optimize
? CLEANUP_EXPENSIVE
: 0);
1372 life_analysis (insns
, NULL
, 0);
1374 /* Dominator info is also needed for migrate_btr_def. */
1375 dom
= calculate_dominance_info (CDI_DOMINATORS
);
1376 migrate_btr_defs (class,
1377 ((*targetm
.branch_target_register_callee_saved
)
1378 (after_prologue_epilogue_gen
)));
1380 free_dominance_info (dom
);
1382 update_life_info (NULL
, UPDATE_LIFE_GLOBAL_RM_NOTES
,
1383 PROP_DEATH_NOTES
| PROP_REG_INFO
);