xref: /openbsd-src/gnu/gcc/gcc/bt-load.c (revision 404b540a9034ac75a6199ad1a32d1bbc7a0d4210)
1 /* Perform branch target register load optimizations.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006
3    Free Software Foundation, Inc.
4 
5 This file is part of GCC.
6 
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 2, or (at your option) any later
10 version.
11 
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15 for more details.
16 
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING.  If not, write to the Free
19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA.  */
21 
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "hard-reg-set.h"
28 #include "regs.h"
29 #include "fibheap.h"
30 #include "output.h"
31 #include "target.h"
32 #include "expr.h"
33 #include "flags.h"
34 #include "insn-attr.h"
35 #include "function.h"
36 #include "except.h"
37 #include "tm_p.h"
38 #include "toplev.h"
39 #include "tree-pass.h"
40 
41 /* Target register optimizations - these are performed after reload.  */
42 
43 typedef struct btr_def_group_s
44 {
45   struct btr_def_group_s *next;
46   rtx src;
47   struct btr_def_s *members;
48 } *btr_def_group;
49 
50 typedef struct btr_user_s
51 {
52   struct btr_user_s *next;
53   basic_block bb;
54   int luid;
55   rtx insn;
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,
59      then USE is NULL.  */
60   rtx use;
61   int n_reaching_defs;
62   int first_reaching_def;
63   char other_use_this_block;
64 } *btr_user;
65 
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).  */
74 
75 typedef struct btr_def_s
76 {
77   struct btr_def_s *next_this_bb;
78   struct btr_def_s *next_this_group;
79   basic_block bb;
80   int luid;
81   rtx insn;
82   int btr;
83   int cost;
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.  */
88   btr_def_group group;
89   btr_user uses;
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
101      as appropriate.  */
102   char other_btr_uses_before_def;
103   char other_btr_uses_after_use;
104   /* We set own_end when we have moved a definition into a dominator.
105      Thus, when a later combination removes this definition again, we know
106      to clear out trs_live_at_end again.  */
107   char own_end;
108   bitmap live_range;
109 } *btr_def;
110 
111 static int issue_rate;
112 
113 static int basic_block_freq (basic_block);
114 static int insn_sets_btr_p (rtx, int, int *);
115 static rtx *find_btr_use (rtx);
116 static int btr_referenced_p (rtx, rtx *);
117 static int find_btr_reference (rtx *, void *);
118 static void find_btr_def_group (btr_def_group *, btr_def);
119 static btr_def add_btr_def (fibheap_t, basic_block, int, rtx,
120 			    unsigned int, int, btr_def_group *);
121 static btr_user new_btr_user (basic_block, int, rtx);
122 static void dump_hard_reg_set (HARD_REG_SET);
123 static void dump_btrs_live (int);
124 static void note_other_use_this_block (unsigned int, btr_user);
125 static void compute_defs_uses_and_gen (fibheap_t, btr_def *,btr_user *,
126 				       sbitmap *, sbitmap *, HARD_REG_SET *);
127 static void compute_kill (sbitmap *, sbitmap *, HARD_REG_SET *);
128 static void compute_out (sbitmap *bb_out, sbitmap *, sbitmap *, int);
129 static void link_btr_uses (btr_def *, btr_user *, sbitmap *, sbitmap *, int);
130 static void build_btr_def_use_webs (fibheap_t);
131 static int block_at_edge_of_live_range_p (int, btr_def);
132 static void clear_btr_from_live_range (btr_def def);
133 static void add_btr_to_live_range (btr_def, int);
134 static void augment_live_range (bitmap, HARD_REG_SET *, basic_block,
135 				basic_block, int);
136 static int choose_btr (HARD_REG_SET);
137 static void combine_btr_defs (btr_def, HARD_REG_SET *);
138 static void btr_def_live_range (btr_def, HARD_REG_SET *);
139 static void move_btr_def (basic_block, int, btr_def, bitmap, HARD_REG_SET *);
140 static int migrate_btr_def (btr_def, int);
141 static void migrate_btr_defs (enum reg_class, int);
142 static int can_move_up (basic_block, rtx, int);
143 static void note_btr_set (rtx, rtx, void *);
144 
145 /* The following code performs code motion of target load instructions
146    (instructions that set branch target registers), to move them
147    forward away from the branch instructions and out of loops (or,
148    more generally, from a more frequently executed place to a less
149    frequently executed place).
150    Moving target load instructions further in front of the branch
151    instruction that uses the target register value means that the hardware
152    has a better chance of preloading the instructions at the branch
153    target by the time the branch is reached.  This avoids bubbles
154    when a taken branch needs to flush out the pipeline.
155    Moving target load instructions out of loops means they are executed
156    less frequently.  */
157 
158 /* An obstack to hold the def-use web data structures built up for
159    migrating branch target load instructions.  */
160 static struct obstack migrate_btrl_obstack;
161 
162 /* Array indexed by basic block number, giving the set of registers
163    live in that block.  */
164 static HARD_REG_SET *btrs_live;
165 
166 /* Array indexed by basic block number, giving the set of registers live at
167   the end of that block, including any uses by a final jump insn, if any.  */
168 static HARD_REG_SET *btrs_live_at_end;
169 
170 /* Set of all target registers that we are willing to allocate.  */
171 static HARD_REG_SET all_btrs;
172 
173 /* Provide lower and upper bounds for target register numbers, so that
174    we don't need to search through all the hard registers all the time.  */
175 static int first_btr, last_btr;
176 
177 
178 
179 /* Return an estimate of the frequency of execution of block bb.  */
180 static int
basic_block_freq(basic_block bb)181 basic_block_freq (basic_block bb)
182 {
183   return bb->frequency;
184 }
185 
186 static rtx *btr_reference_found;
187 
188 /* A subroutine of btr_referenced_p, called through for_each_rtx.
189    PREG is a pointer to an rtx that is to be excluded from the
190    traversal.  If we find a reference to a target register anywhere
191    else, return 1, and put a pointer to it into btr_reference_found.  */
192 static int
find_btr_reference(rtx * px,void * preg)193 find_btr_reference (rtx *px, void *preg)
194 {
195   rtx x;
196   int regno, i;
197 
198   if (px == preg)
199     return -1;
200   x = *px;
201   if (!REG_P (x))
202     return 0;
203   regno = REGNO (x);
204   for (i = hard_regno_nregs[regno][GET_MODE (x)] - 1; i >= 0; i--)
205     if (TEST_HARD_REG_BIT (all_btrs, regno+i))
206       {
207 	btr_reference_found = px;
208 	return 1;
209       }
210   return -1;
211 }
212 
213 /* Return nonzero if X references (sets or reads) any branch target register.
214    If EXCLUDEP is set, disregard any references within the rtx pointed to
215    by it.  If returning nonzero, also set btr_reference_found as above.  */
216 static int
btr_referenced_p(rtx x,rtx * excludep)217 btr_referenced_p (rtx x, rtx *excludep)
218 {
219   return for_each_rtx (&x, find_btr_reference, excludep);
220 }
221 
222 /* Return true if insn is an instruction that sets a target register.
223    if CHECK_CONST is true, only return true if the source is constant.
224    If such a set is found and REGNO is nonzero, assign the register number
225    of the destination register to *REGNO.  */
226 static int
insn_sets_btr_p(rtx insn,int check_const,int * regno)227 insn_sets_btr_p (rtx insn, int check_const, int *regno)
228 {
229   rtx set;
230 
231   if (NONJUMP_INSN_P (insn)
232       && (set = single_set (insn)))
233     {
234       rtx dest = SET_DEST (set);
235       rtx src = SET_SRC (set);
236 
237       if (GET_CODE (dest) == SUBREG)
238 	dest = XEXP (dest, 0);
239 
240       if (REG_P (dest)
241 	  && TEST_HARD_REG_BIT (all_btrs, REGNO (dest)))
242 	{
243 	  gcc_assert (!btr_referenced_p (src, NULL));
244 
245 	  if (!check_const || CONSTANT_P (src))
246 	    {
247 	      if (regno)
248 		*regno = REGNO (dest);
249 	      return 1;
250 	    }
251 	}
252     }
253   return 0;
254 }
255 
256 /* Find and return a use of a target register within an instruction INSN.  */
257 static rtx *
find_btr_use(rtx insn)258 find_btr_use (rtx insn)
259 {
260   return btr_referenced_p (insn, NULL) ? btr_reference_found : NULL;
261 }
262 
263 /* Find the group that the target register definition DEF belongs
264    to in the list starting with *ALL_BTR_DEF_GROUPS.  If no such
265    group exists, create one.  Add def to the group.  */
266 static void
find_btr_def_group(btr_def_group * all_btr_def_groups,btr_def def)267 find_btr_def_group (btr_def_group *all_btr_def_groups, btr_def def)
268 {
269   if (insn_sets_btr_p (def->insn, 1, NULL))
270     {
271       btr_def_group this_group;
272       rtx def_src = SET_SRC (single_set (def->insn));
273 
274       /* ?? This linear search is an efficiency concern, particularly
275 	 as the search will almost always fail to find a match.  */
276       for (this_group = *all_btr_def_groups;
277 	   this_group != NULL;
278 	   this_group = this_group->next)
279 	if (rtx_equal_p (def_src, this_group->src))
280 	  break;
281 
282       if (!this_group)
283 	{
284 	  this_group = obstack_alloc (&migrate_btrl_obstack,
285 				      sizeof (struct btr_def_group_s));
286 	  this_group->src = def_src;
287 	  this_group->members = NULL;
288 	  this_group->next = *all_btr_def_groups;
289 	  *all_btr_def_groups = this_group;
290 	}
291       def->group = this_group;
292       def->next_this_group = this_group->members;
293       this_group->members = def;
294     }
295   else
296     def->group = NULL;
297 }
298 
299 /* Create a new target register definition structure, for a definition in
300    block BB, instruction INSN, and insert it into ALL_BTR_DEFS.  Return
301    the new definition.  */
302 static btr_def
add_btr_def(fibheap_t all_btr_defs,basic_block bb,int insn_luid,rtx insn,unsigned int dest_reg,int other_btr_uses_before_def,btr_def_group * all_btr_def_groups)303 add_btr_def (fibheap_t all_btr_defs, basic_block bb, int insn_luid, rtx insn,
304 	     unsigned int dest_reg, int other_btr_uses_before_def,
305 	     btr_def_group *all_btr_def_groups)
306 {
307   btr_def this
308     = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_def_s));
309   this->bb = bb;
310   this->luid = insn_luid;
311   this->insn = insn;
312   this->btr = dest_reg;
313   this->cost = basic_block_freq (bb);
314   this->has_ambiguous_use = 0;
315   this->other_btr_uses_before_def = other_btr_uses_before_def;
316   this->other_btr_uses_after_use = 0;
317   this->next_this_bb = NULL;
318   this->next_this_group = NULL;
319   this->uses = NULL;
320   this->live_range = NULL;
321   find_btr_def_group (all_btr_def_groups, this);
322 
323   fibheap_insert (all_btr_defs, -this->cost, this);
324 
325   if (dump_file)
326     fprintf (dump_file,
327       "Found target reg definition: sets %u { bb %d, insn %d }%s priority %d\n",
328       dest_reg, bb->index, INSN_UID (insn), (this->group ? "" : ":not const"),
329       this->cost);
330 
331   return this;
332 }
333 
334 /* Create a new target register user structure, for a use in block BB,
335    instruction INSN.  Return the new user.  */
336 static btr_user
new_btr_user(basic_block bb,int insn_luid,rtx insn)337 new_btr_user (basic_block bb, int insn_luid, rtx insn)
338 {
339   /* This instruction reads target registers.  We need
340      to decide whether we can replace all target register
341      uses easily.
342    */
343   rtx *usep = find_btr_use (PATTERN (insn));
344   rtx use;
345   btr_user user = NULL;
346 
347   if (usep)
348     {
349       int unambiguous_single_use;
350 
351       /* We want to ensure that USE is the only use of a target
352 	 register in INSN, so that we know that to rewrite INSN to use
353 	 a different target register, all we have to do is replace USE.  */
354       unambiguous_single_use = !btr_referenced_p (PATTERN (insn), usep);
355       if (!unambiguous_single_use)
356 	usep = NULL;
357     }
358   use = usep ? *usep : NULL_RTX;
359   user = obstack_alloc (&migrate_btrl_obstack, sizeof (struct btr_user_s));
360   user->bb = bb;
361   user->luid = insn_luid;
362   user->insn = insn;
363   user->use = use;
364   user->other_use_this_block = 0;
365   user->next = NULL;
366   user->n_reaching_defs = 0;
367   user->first_reaching_def = -1;
368 
369   if (dump_file)
370     {
371       fprintf (dump_file, "Uses target reg: { bb %d, insn %d }",
372 	       bb->index, INSN_UID (insn));
373 
374       if (user->use)
375 	fprintf (dump_file, ": unambiguous use of reg %d\n",
376 		 REGNO (user->use));
377     }
378 
379   return user;
380 }
381 
382 /* Write the contents of S to the dump file.  */
383 static void
dump_hard_reg_set(HARD_REG_SET s)384 dump_hard_reg_set (HARD_REG_SET s)
385 {
386   int reg;
387   for (reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
388     if (TEST_HARD_REG_BIT (s, reg))
389       fprintf (dump_file, " %d", reg);
390 }
391 
392 /* Write the set of target regs live in block BB to the dump file.  */
393 static void
dump_btrs_live(int bb)394 dump_btrs_live (int bb)
395 {
396   fprintf (dump_file, "BB%d live:", bb);
397   dump_hard_reg_set (btrs_live[bb]);
398   fprintf (dump_file, "\n");
399 }
400 
401 /* REGNO is the number of a branch target register that is being used or
402    set.  USERS_THIS_BB is a list of preceding branch target register users;
403    If any of them use the same register, set their other_use_this_block
404    flag.  */
405 static void
note_other_use_this_block(unsigned int regno,btr_user users_this_bb)406 note_other_use_this_block (unsigned int regno, btr_user users_this_bb)
407 {
408   btr_user user;
409 
410   for (user = users_this_bb; user != NULL; user = user->next)
411     if (user->use && REGNO (user->use) == regno)
412       user->other_use_this_block = 1;
413 }
414 
415 typedef struct {
416   btr_user users_this_bb;
417   HARD_REG_SET btrs_written_in_block;
418   HARD_REG_SET btrs_live_in_block;
419   sbitmap bb_gen;
420   sbitmap *btr_defset;
421 } defs_uses_info;
422 
423 /* Called via note_stores or directly to register stores into /
424    clobbers of a branch target register DEST that are not recognized as
425    straightforward definitions.  DATA points to information about the
426    current basic block that needs updating.  */
427 static void
note_btr_set(rtx dest,rtx set ATTRIBUTE_UNUSED,void * data)428 note_btr_set (rtx dest, rtx set ATTRIBUTE_UNUSED, void *data)
429 {
430   defs_uses_info *info = data;
431   int regno, end_regno;
432 
433   if (!REG_P (dest))
434     return;
435   regno = REGNO (dest);
436   end_regno = regno + hard_regno_nregs[regno][GET_MODE (dest)];
437   for (; regno < end_regno; regno++)
438     if (TEST_HARD_REG_BIT (all_btrs, regno))
439       {
440 	note_other_use_this_block (regno, info->users_this_bb);
441 	SET_HARD_REG_BIT (info->btrs_written_in_block, regno);
442 	SET_HARD_REG_BIT (info->btrs_live_in_block, regno);
443 	sbitmap_difference (info->bb_gen, info->bb_gen,
444 			    info->btr_defset[regno - first_btr]);
445       }
446 }
447 
448 static void
compute_defs_uses_and_gen(fibheap_t all_btr_defs,btr_def * def_array,btr_user * use_array,sbitmap * btr_defset,sbitmap * bb_gen,HARD_REG_SET * btrs_written)449 compute_defs_uses_and_gen (fibheap_t all_btr_defs, btr_def *def_array,
450 			   btr_user *use_array, sbitmap *btr_defset,
451 			   sbitmap *bb_gen, HARD_REG_SET *btrs_written)
452 {
453   /* Scan the code building up the set of all defs and all uses.
454      For each target register, build the set of defs of that register.
455      For each block, calculate the set of target registers
456      written in that block.
457      Also calculate the set of btrs ever live in that block.
458   */
459   int i;
460   int insn_luid = 0;
461   btr_def_group all_btr_def_groups = NULL;
462   defs_uses_info info;
463 
464   sbitmap_vector_zero (bb_gen, n_basic_blocks);
465   for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
466     {
467       basic_block bb = BASIC_BLOCK (i);
468       int reg;
469       btr_def defs_this_bb = NULL;
470       rtx insn;
471       rtx last;
472       int can_throw = 0;
473 
474       info.users_this_bb = NULL;
475       info.bb_gen = bb_gen[i];
476       info.btr_defset = btr_defset;
477 
478       CLEAR_HARD_REG_SET (info.btrs_live_in_block);
479       CLEAR_HARD_REG_SET (info.btrs_written_in_block);
480       for (reg = first_btr; reg <= last_btr; reg++)
481 	if (TEST_HARD_REG_BIT (all_btrs, reg)
482 	    && REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, reg))
483 	  SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
484 
485       for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
486 	   insn != last;
487 	   insn = NEXT_INSN (insn), insn_luid++)
488 	{
489 	  if (INSN_P (insn))
490 	    {
491 	      int regno;
492 	      int insn_uid = INSN_UID (insn);
493 
494 	      if (insn_sets_btr_p (insn, 0, &regno))
495 		{
496 		  btr_def def = add_btr_def (
497 		      all_btr_defs, bb, insn_luid, insn, regno,
498 		      TEST_HARD_REG_BIT (info.btrs_live_in_block, regno),
499 		      &all_btr_def_groups);
500 
501 		  def_array[insn_uid] = def;
502 		  SET_HARD_REG_BIT (info.btrs_written_in_block, regno);
503 		  SET_HARD_REG_BIT (info.btrs_live_in_block, regno);
504 		  sbitmap_difference (bb_gen[i], bb_gen[i],
505 				      btr_defset[regno - first_btr]);
506 		  SET_BIT (bb_gen[i], insn_uid);
507 		  def->next_this_bb = defs_this_bb;
508 		  defs_this_bb = def;
509 		  SET_BIT (btr_defset[regno - first_btr], insn_uid);
510 		  note_other_use_this_block (regno, info.users_this_bb);
511 		}
512 	      /* Check for the blockage emitted by expand_nl_goto_receiver.  */
513 	      else if (current_function_has_nonlocal_label
514 		       && GET_CODE (PATTERN (insn)) == ASM_INPUT)
515 		{
516 		  btr_user user;
517 
518 		  /* Do the equivalent of calling note_other_use_this_block
519 		     for every target register.  */
520 		  for (user = info.users_this_bb; user != NULL;
521 		       user = user->next)
522 		    if (user->use)
523 		      user->other_use_this_block = 1;
524 		  IOR_HARD_REG_SET (info.btrs_written_in_block, all_btrs);
525 		  IOR_HARD_REG_SET (info.btrs_live_in_block, all_btrs);
526 		  sbitmap_zero (info.bb_gen);
527 		}
528 	      else
529 		{
530 		  if (btr_referenced_p (PATTERN (insn), NULL))
531 		    {
532 		      btr_user user = new_btr_user (bb, insn_luid, insn);
533 
534 		      use_array[insn_uid] = user;
535 		      if (user->use)
536 			SET_HARD_REG_BIT (info.btrs_live_in_block,
537 					  REGNO (user->use));
538 		      else
539 			{
540 			  int reg;
541 			  for (reg = first_btr; reg <= last_btr; reg++)
542 			    if (TEST_HARD_REG_BIT (all_btrs, reg)
543 				&& refers_to_regno_p (reg, reg + 1, user->insn,
544 						      NULL))
545 			      {
546 				note_other_use_this_block (reg,
547 							   info.users_this_bb);
548 				SET_HARD_REG_BIT (info.btrs_live_in_block, reg);
549 			      }
550 			  note_stores (PATTERN (insn), note_btr_set, &info);
551 			}
552 		      user->next = info.users_this_bb;
553 		      info.users_this_bb = user;
554 		    }
555 		  if (CALL_P (insn))
556 		    {
557 		      HARD_REG_SET *clobbered = &call_used_reg_set;
558 		      HARD_REG_SET call_saved;
559 		      rtx pat = PATTERN (insn);
560 		      int i;
561 
562 		      /* Check for sibcall.  */
563 		      if (GET_CODE (pat) == PARALLEL)
564 			for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
565 			  if (GET_CODE (XVECEXP (pat, 0, i)) == RETURN)
566 			    {
567 			      COMPL_HARD_REG_SET (call_saved,
568 						  call_used_reg_set);
569 			      clobbered = &call_saved;
570 			    }
571 
572 		      for (regno = first_btr; regno <= last_btr; regno++)
573 			if (TEST_HARD_REG_BIT (*clobbered, regno))
574 			  note_btr_set (regno_reg_rtx[regno], NULL_RTX, &info);
575 		    }
576 		}
577 	    }
578 	}
579 
580       COPY_HARD_REG_SET (btrs_live[i], info.btrs_live_in_block);
581       COPY_HARD_REG_SET (btrs_written[i], info.btrs_written_in_block);
582 
583       REG_SET_TO_HARD_REG_SET (btrs_live_at_end[i], bb->il.rtl->global_live_at_end);
584       /* If this block ends in a jump insn, add any uses or even clobbers
585 	 of branch target registers that it might have.  */
586       for (insn = BB_END (bb); insn != BB_HEAD (bb) && ! INSN_P (insn); )
587 	insn = PREV_INSN (insn);
588       /* ??? for the fall-through edge, it would make sense to insert the
589 	 btr set on the edge, but that would require to split the block
590 	 early on so that we can distinguish between dominance from the fall
591 	 through edge - which can use the call-clobbered registers - from
592 	 dominance by the throw edge.  */
593       if (can_throw_internal (insn))
594 	{
595 	  HARD_REG_SET tmp;
596 
597 	  COPY_HARD_REG_SET (tmp, call_used_reg_set);
598 	  AND_HARD_REG_SET (tmp, all_btrs);
599 	  IOR_HARD_REG_SET (btrs_live_at_end[i], tmp);
600 	  can_throw = 1;
601 	}
602       if (can_throw || JUMP_P (insn))
603 	{
604 	  int regno;
605 
606 	  for (regno = first_btr; regno <= last_btr; regno++)
607 	    if (refers_to_regno_p (regno, regno+1, insn, NULL))
608 	      SET_HARD_REG_BIT (btrs_live_at_end[i], regno);
609 	}
610 
611       if (dump_file)
612 	dump_btrs_live(i);
613     }
614 }
615 
616 static void
compute_kill(sbitmap * bb_kill,sbitmap * btr_defset,HARD_REG_SET * btrs_written)617 compute_kill (sbitmap *bb_kill, sbitmap *btr_defset,
618 	      HARD_REG_SET *btrs_written)
619 {
620   int i;
621   int regno;
622 
623   /* For each basic block, form the set BB_KILL - the set
624      of definitions that the block kills.  */
625   sbitmap_vector_zero (bb_kill, n_basic_blocks);
626   for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
627     {
628       for (regno = first_btr; regno <= last_btr; regno++)
629 	if (TEST_HARD_REG_BIT (all_btrs, regno)
630 	    && TEST_HARD_REG_BIT (btrs_written[i], regno))
631 	  sbitmap_a_or_b (bb_kill[i], bb_kill[i],
632 			  btr_defset[regno - first_btr]);
633     }
634 }
635 
636 static void
compute_out(sbitmap * bb_out,sbitmap * bb_gen,sbitmap * bb_kill,int max_uid)637 compute_out (sbitmap *bb_out, sbitmap *bb_gen, sbitmap *bb_kill, int max_uid)
638 {
639   /* Perform iterative dataflow:
640       Initially, for all blocks, BB_OUT = BB_GEN.
641       For each block,
642 	BB_IN  = union over predecessors of BB_OUT(pred)
643 	BB_OUT = (BB_IN - BB_KILL) + BB_GEN
644      Iterate until the bb_out sets stop growing.  */
645   int i;
646   int changed;
647   sbitmap bb_in = sbitmap_alloc (max_uid);
648 
649   for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
650     sbitmap_copy (bb_out[i], bb_gen[i]);
651 
652   changed = 1;
653   while (changed)
654     {
655       changed = 0;
656       for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
657 	{
658 	  sbitmap_union_of_preds (bb_in, bb_out, i);
659 	  changed |= sbitmap_union_of_diff_cg (bb_out[i], bb_gen[i],
660 					       bb_in, bb_kill[i]);
661 	}
662     }
663   sbitmap_free (bb_in);
664 }
665 
666 static void
link_btr_uses(btr_def * def_array,btr_user * use_array,sbitmap * bb_out,sbitmap * btr_defset,int max_uid)667 link_btr_uses (btr_def *def_array, btr_user *use_array, sbitmap *bb_out,
668 	       sbitmap *btr_defset, int max_uid)
669 {
670   int i;
671   sbitmap reaching_defs = sbitmap_alloc (max_uid);
672 
673   /* Link uses to the uses lists of all of their reaching defs.
674      Count up the number of reaching defs of each use.  */
675   for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
676     {
677       basic_block bb = BASIC_BLOCK (i);
678       rtx insn;
679       rtx last;
680 
681       sbitmap_union_of_preds (reaching_defs, bb_out, i);
682       for (insn = BB_HEAD (bb), last = NEXT_INSN (BB_END (bb));
683 	   insn != last;
684 	   insn = NEXT_INSN (insn))
685 	{
686 	  if (INSN_P (insn))
687 	    {
688 	      int insn_uid = INSN_UID (insn);
689 
690 	      btr_def def   = def_array[insn_uid];
691 	      btr_user user = use_array[insn_uid];
692 	      if (def != NULL)
693 		{
694 		  /* Remove all reaching defs of regno except
695 		     for this one.  */
696 		  sbitmap_difference (reaching_defs, reaching_defs,
697 				      btr_defset[def->btr - first_btr]);
698 		  SET_BIT(reaching_defs, insn_uid);
699 		}
700 
701 	      if (user != NULL)
702 		{
703 		  /* Find all the reaching defs for this use.  */
704 		  sbitmap reaching_defs_of_reg = sbitmap_alloc(max_uid);
705 		  unsigned int uid = 0;
706 		  sbitmap_iterator sbi;
707 
708 		  if (user->use)
709 		    sbitmap_a_and_b (
710 		      reaching_defs_of_reg,
711 		      reaching_defs,
712 		      btr_defset[REGNO (user->use) - first_btr]);
713 		  else
714 		    {
715 		      int reg;
716 
717 		      sbitmap_zero (reaching_defs_of_reg);
718 		      for (reg = first_btr; reg <= last_btr; reg++)
719 			if (TEST_HARD_REG_BIT (all_btrs, reg)
720 			    && refers_to_regno_p (reg, reg + 1, user->insn,
721 						  NULL))
722 			  sbitmap_a_or_b_and_c (reaching_defs_of_reg,
723 			    reaching_defs_of_reg,
724 			    reaching_defs,
725 			    btr_defset[reg - first_btr]);
726 		    }
727 		  EXECUTE_IF_SET_IN_SBITMAP (reaching_defs_of_reg, 0, uid, sbi)
728 		    {
729 		      btr_def def = def_array[uid];
730 
731 		      /* We now know that def reaches user.  */
732 
733 		      if (dump_file)
734 			fprintf (dump_file,
735 			  "Def in insn %d reaches use in insn %d\n",
736 			  uid, insn_uid);
737 
738 		      user->n_reaching_defs++;
739 		      if (!user->use)
740 			def->has_ambiguous_use = 1;
741 		      if (user->first_reaching_def != -1)
742 			{ /* There is more than one reaching def.  This is
743 			     a rare case, so just give up on this def/use
744 			     web when it occurs.  */
745 			  def->has_ambiguous_use = 1;
746 			  def_array[user->first_reaching_def]
747 			    ->has_ambiguous_use = 1;
748 			  if (dump_file)
749 			    fprintf (dump_file,
750 				     "(use %d has multiple reaching defs)\n",
751 				     insn_uid);
752 			}
753 		      else
754 			user->first_reaching_def = uid;
755 		      if (user->other_use_this_block)
756 			def->other_btr_uses_after_use = 1;
757 		      user->next = def->uses;
758 		      def->uses = user;
759 		    }
760 		  sbitmap_free (reaching_defs_of_reg);
761 		}
762 
763 	      if (CALL_P (insn))
764 		{
765 		  int regno;
766 
767 		  for (regno = first_btr; regno <= last_btr; regno++)
768 		    if (TEST_HARD_REG_BIT (all_btrs, regno)
769 			&& TEST_HARD_REG_BIT (call_used_reg_set, regno))
770 		      sbitmap_difference (reaching_defs, reaching_defs,
771 					  btr_defset[regno - first_btr]);
772 		}
773 	    }
774 	}
775     }
776   sbitmap_free (reaching_defs);
777 }
778 
779 static void
build_btr_def_use_webs(fibheap_t all_btr_defs)780 build_btr_def_use_webs (fibheap_t all_btr_defs)
781 {
782   const int max_uid = get_max_uid ();
783   btr_def  *def_array   = XCNEWVEC (btr_def, max_uid);
784   btr_user *use_array   = XCNEWVEC (btr_user, max_uid);
785   sbitmap *btr_defset   = sbitmap_vector_alloc (
786 			   (last_btr - first_btr) + 1, max_uid);
787   sbitmap *bb_gen      = sbitmap_vector_alloc (n_basic_blocks, max_uid);
788   HARD_REG_SET *btrs_written = XCNEWVEC (HARD_REG_SET, n_basic_blocks);
789   sbitmap *bb_kill;
790   sbitmap *bb_out;
791 
792   sbitmap_vector_zero (btr_defset, (last_btr - first_btr) + 1);
793 
794   compute_defs_uses_and_gen (all_btr_defs, def_array, use_array, btr_defset,
795 			     bb_gen, btrs_written);
796 
797   bb_kill = sbitmap_vector_alloc (n_basic_blocks, max_uid);
798   compute_kill (bb_kill, btr_defset, btrs_written);
799   free (btrs_written);
800 
801   bb_out = sbitmap_vector_alloc (n_basic_blocks, max_uid);
802   compute_out (bb_out, bb_gen, bb_kill, max_uid);
803 
804   sbitmap_vector_free (bb_gen);
805   sbitmap_vector_free (bb_kill);
806 
807   link_btr_uses (def_array, use_array, bb_out, btr_defset, max_uid);
808 
809   sbitmap_vector_free (bb_out);
810   sbitmap_vector_free (btr_defset);
811   free (use_array);
812   free (def_array);
813 }
814 
815 /* Return true if basic block BB contains the start or end of the
816    live range of the definition DEF, AND there are other live
817    ranges of the same target register that include BB.  */
818 static int
block_at_edge_of_live_range_p(int bb,btr_def def)819 block_at_edge_of_live_range_p (int bb, btr_def def)
820 {
821   if (def->other_btr_uses_before_def && BASIC_BLOCK (bb) == def->bb)
822     return 1;
823   else if (def->other_btr_uses_after_use)
824     {
825       btr_user user;
826       for (user = def->uses; user != NULL; user = user->next)
827 	if (BASIC_BLOCK (bb) == user->bb)
828 	  return 1;
829     }
830   return 0;
831 }
832 
833 /* We are removing the def/use web DEF.  The target register
834    used in this web is therefore no longer live in the live range
835    of this web, so remove it from the live set of all basic blocks
836    in the live range of the web.
837    Blocks at the boundary of the live range may contain other live
838    ranges for the same target register, so we have to be careful
839    to remove the target register from the live set of these blocks
840    only if they do not contain other live ranges for the same register.  */
841 static void
clear_btr_from_live_range(btr_def def)842 clear_btr_from_live_range (btr_def def)
843 {
844   unsigned bb;
845   bitmap_iterator bi;
846 
847   EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
848     {
849       if ((!def->other_btr_uses_before_def
850 	   && !def->other_btr_uses_after_use)
851 	  || !block_at_edge_of_live_range_p (bb, def))
852 	{
853 	  CLEAR_HARD_REG_BIT (btrs_live[bb], def->btr);
854 	  CLEAR_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
855 	  if (dump_file)
856 	    dump_btrs_live (bb);
857 	}
858     }
859  if (def->own_end)
860    CLEAR_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
861 }
862 
863 
864 /* We are adding the def/use web DEF.  Add the target register used
865    in this web to the live set of all of the basic blocks that contain
866    the live range of the web.
867    If OWN_END is set, also show that the register is live from our
868    definitions at the end of the basic block where it is defined.  */
869 static void
add_btr_to_live_range(btr_def def,int own_end)870 add_btr_to_live_range (btr_def def, int own_end)
871 {
872   unsigned bb;
873   bitmap_iterator bi;
874 
875   EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
876     {
877       SET_HARD_REG_BIT (btrs_live[bb], def->btr);
878       SET_HARD_REG_BIT (btrs_live_at_end[bb], def->btr);
879       if (dump_file)
880 	dump_btrs_live (bb);
881     }
882   if (own_end)
883     {
884       SET_HARD_REG_BIT (btrs_live_at_end[def->bb->index], def->btr);
885       def->own_end = 1;
886     }
887 }
888 
889 /* Update a live range to contain the basic block NEW_BLOCK, and all
890    blocks on paths between the existing live range and NEW_BLOCK.
891    HEAD is a block contained in the existing live range that dominates
892    all other blocks in the existing live range.
893    Also add to the set BTRS_LIVE_IN_RANGE all target registers that
894    are live in the blocks that we add to the live range.
895    If FULL_RANGE is set, include the full live range of NEW_BB;
896    otherwise, if NEW_BB dominates HEAD_BB, only add registers that
897    are life at the end of NEW_BB for NEW_BB itself.
898    It is a precondition that either NEW_BLOCK dominates HEAD,or
899    HEAD dom NEW_BLOCK.  This is used to speed up the
900    implementation of this function.  */
901 static void
augment_live_range(bitmap live_range,HARD_REG_SET * btrs_live_in_range,basic_block head_bb,basic_block new_bb,int full_range)902 augment_live_range (bitmap live_range, HARD_REG_SET *btrs_live_in_range,
903 		    basic_block head_bb, basic_block new_bb, int full_range)
904 {
905   basic_block *worklist, *tos;
906 
907   tos = worklist = XNEWVEC (basic_block, n_basic_blocks + 1);
908 
909   if (dominated_by_p (CDI_DOMINATORS, new_bb, head_bb))
910     {
911       if (new_bb == head_bb)
912 	{
913 	  if (full_range)
914 	    IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_bb->index]);
915 	  free (tos);
916 	  return;
917 	}
918       *tos++ = new_bb;
919     }
920   else
921     {
922       edge e;
923       edge_iterator ei;
924       int new_block = new_bb->index;
925 
926       gcc_assert (dominated_by_p (CDI_DOMINATORS, head_bb, new_bb));
927 
928       IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[head_bb->index]);
929       bitmap_set_bit (live_range, new_block);
930       /* A previous btr migration could have caused a register to be
931 	live just at the end of new_block which we need in full, so
932 	use trs_live_at_end even if full_range is set.  */
933       IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live_at_end[new_block]);
934       if (full_range)
935 	IOR_HARD_REG_SET (*btrs_live_in_range, btrs_live[new_block]);
936       if (dump_file)
937 	{
938 	  fprintf (dump_file,
939 		   "Adding end of block %d and rest of %d to live range\n",
940 		   new_block, head_bb->index);
941 	  fprintf (dump_file,"Now live btrs are ");
942 	  dump_hard_reg_set (*btrs_live_in_range);
943 	  fprintf (dump_file, "\n");
944 	}
945       FOR_EACH_EDGE (e, ei, head_bb->preds)
946 	*tos++ = e->src;
947     }
948 
949   while (tos != worklist)
950     {
951       basic_block bb = *--tos;
952       if (!bitmap_bit_p (live_range, bb->index))
953 	{
954 	  edge e;
955 	  edge_iterator ei;
956 
957 	  bitmap_set_bit (live_range, bb->index);
958 	  IOR_HARD_REG_SET (*btrs_live_in_range,
959 	    btrs_live[bb->index]);
960 	  /* A previous btr migration could have caused a register to be
961 	     live just at the end of a block which we need in full.  */
962 	  IOR_HARD_REG_SET (*btrs_live_in_range,
963 	    btrs_live_at_end[bb->index]);
964 	  if (dump_file)
965 	    {
966 	      fprintf (dump_file,
967 		"Adding block %d to live range\n", bb->index);
968 	      fprintf (dump_file,"Now live btrs are ");
969 	      dump_hard_reg_set (*btrs_live_in_range);
970 	      fprintf (dump_file, "\n");
971 	    }
972 
973 	  FOR_EACH_EDGE (e, ei, bb->preds)
974 	    {
975 	      basic_block pred = e->src;
976 	      if (!bitmap_bit_p (live_range, pred->index))
977 		*tos++ = pred;
978 	    }
979 	}
980     }
981 
982   free (worklist);
983 }
984 
985 /*  Return the most desirable target register that is not in
986     the set USED_BTRS.  */
987 static int
choose_btr(HARD_REG_SET used_btrs)988 choose_btr (HARD_REG_SET used_btrs)
989 {
990   int i;
991   GO_IF_HARD_REG_SUBSET (all_btrs, used_btrs, give_up);
992 
993   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
994     {
995 #ifdef REG_ALLOC_ORDER
996       int regno = reg_alloc_order[i];
997 #else
998       int regno = i;
999 #endif
1000       if (TEST_HARD_REG_BIT (all_btrs, regno)
1001 	  && !TEST_HARD_REG_BIT (used_btrs, regno))
1002 	return regno;
1003     }
1004 give_up:
1005   return -1;
1006 }
1007 
1008 /* Calculate the set of basic blocks that contain the live range of
1009    the def/use web DEF.
1010    Also calculate the set of target registers that are live at time
1011    in this live range, but ignore the live range represented by DEF
1012    when calculating this set.  */
1013 static void
btr_def_live_range(btr_def def,HARD_REG_SET * btrs_live_in_range)1014 btr_def_live_range (btr_def def, HARD_REG_SET *btrs_live_in_range)
1015 {
1016   if (!def->live_range)
1017     {
1018       btr_user user;
1019 
1020       def->live_range = BITMAP_ALLOC (NULL);
1021 
1022       bitmap_set_bit (def->live_range, def->bb->index);
1023       COPY_HARD_REG_SET (*btrs_live_in_range,
1024 			 (flag_btr_bb_exclusive
1025 			  ? btrs_live : btrs_live_at_end)[def->bb->index]);
1026 
1027       for (user = def->uses; user != NULL; user = user->next)
1028 	augment_live_range (def->live_range, btrs_live_in_range,
1029 			    def->bb, user->bb,
1030 			    (flag_btr_bb_exclusive
1031 			     || user->insn != BB_END (def->bb)
1032 			     || !JUMP_P (user->insn)));
1033     }
1034   else
1035     {
1036       /* def->live_range is accurate, but we need to recompute
1037 	 the set of target registers live over it, because migration
1038 	 of other PT instructions may have affected it.
1039       */
1040       unsigned bb;
1041       unsigned def_bb = flag_btr_bb_exclusive ? -1 : def->bb->index;
1042       bitmap_iterator bi;
1043 
1044       CLEAR_HARD_REG_SET (*btrs_live_in_range);
1045       EXECUTE_IF_SET_IN_BITMAP (def->live_range, 0, bb, bi)
1046 	{
1047 	  IOR_HARD_REG_SET (*btrs_live_in_range,
1048 			    (def_bb == bb
1049 			     ? btrs_live_at_end : btrs_live) [bb]);
1050 	}
1051     }
1052   if (!def->other_btr_uses_before_def &&
1053       !def->other_btr_uses_after_use)
1054     CLEAR_HARD_REG_BIT (*btrs_live_in_range, def->btr);
1055 }
1056 
1057 /* Merge into the def/use web DEF any other def/use webs in the same
1058    group that are dominated by DEF, provided that there is a target
1059    register available to allocate to the merged web.  */
1060 static void
combine_btr_defs(btr_def def,HARD_REG_SET * btrs_live_in_range)1061 combine_btr_defs (btr_def def, HARD_REG_SET *btrs_live_in_range)
1062 {
1063   btr_def other_def;
1064 
1065   for (other_def = def->group->members;
1066        other_def != NULL;
1067        other_def = other_def->next_this_group)
1068     {
1069       if (other_def != def
1070 	  && other_def->uses != NULL
1071 	  && ! other_def->has_ambiguous_use
1072 	  && dominated_by_p (CDI_DOMINATORS, other_def->bb, def->bb))
1073 	{
1074 	  /* def->bb dominates the other def, so def and other_def could
1075 	     be combined.  */
1076 	  /* Merge their live ranges, and get the set of
1077 	     target registers live over the merged range.  */
1078 	  int btr;
1079 	  HARD_REG_SET combined_btrs_live;
1080 	  bitmap combined_live_range = BITMAP_ALLOC (NULL);
1081 	  btr_user user;
1082 
1083 	  if (other_def->live_range == NULL)
1084 	    {
1085 	      HARD_REG_SET dummy_btrs_live_in_range;
1086 	      btr_def_live_range (other_def, &dummy_btrs_live_in_range);
1087 	    }
1088 	  COPY_HARD_REG_SET (combined_btrs_live, *btrs_live_in_range);
1089 	  bitmap_copy (combined_live_range, def->live_range);
1090 
1091 	  for (user = other_def->uses; user != NULL; user = user->next)
1092 	    augment_live_range (combined_live_range, &combined_btrs_live,
1093 				def->bb, user->bb,
1094 				(flag_btr_bb_exclusive
1095 				 || user->insn != BB_END (def->bb)
1096 				 || !JUMP_P (user->insn)));
1097 
1098 	  btr = choose_btr (combined_btrs_live);
1099 	  if (btr != -1)
1100 	    {
1101 	      /* We can combine them.  */
1102 	      if (dump_file)
1103 		fprintf (dump_file,
1104 			 "Combining def in insn %d with def in insn %d\n",
1105 			 INSN_UID (other_def->insn), INSN_UID (def->insn));
1106 
1107 	      def->btr = btr;
1108 	      user = other_def->uses;
1109 	      while (user != NULL)
1110 		{
1111 		  btr_user next = user->next;
1112 
1113 		  user->next = def->uses;
1114 		  def->uses = user;
1115 		  user = next;
1116 		}
1117 	      /* Combining def/use webs can make target registers live
1118 		 after uses where they previously were not.  This means
1119 		 some REG_DEAD notes may no longer be correct.  We could
1120 		 be more precise about this if we looked at the combined
1121 		 live range, but here I just delete any REG_DEAD notes
1122 		 in case they are no longer correct.  */
1123 	      for (user = def->uses; user != NULL; user = user->next)
1124 		remove_note (user->insn,
1125 			     find_regno_note (user->insn, REG_DEAD,
1126 					      REGNO (user->use)));
1127 	      clear_btr_from_live_range (other_def);
1128 	      other_def->uses = NULL;
1129 	      bitmap_copy (def->live_range, combined_live_range);
1130 	      if (other_def->btr == btr && other_def->other_btr_uses_after_use)
1131 		def->other_btr_uses_after_use = 1;
1132 	      COPY_HARD_REG_SET (*btrs_live_in_range, combined_btrs_live);
1133 
1134 	      /* Delete the old target register initialization.  */
1135 	      delete_insn (other_def->insn);
1136 
1137 	    }
1138 	  BITMAP_FREE (combined_live_range);
1139 	}
1140     }
1141 }
1142 
1143 /* Move the definition DEF from its current position to basic
1144    block NEW_DEF_BB, and modify it to use branch target register BTR.
1145    Delete the old defining insn, and insert a new one in NEW_DEF_BB.
1146    Update all reaching uses of DEF in the RTL to use BTR.
1147    If this new position means that other defs in the
1148    same group can be combined with DEF then combine them.  */
1149 static void
move_btr_def(basic_block new_def_bb,int btr,btr_def def,bitmap live_range,HARD_REG_SET * btrs_live_in_range)1150 move_btr_def (basic_block new_def_bb, int btr, btr_def def, bitmap live_range,
1151 	     HARD_REG_SET *btrs_live_in_range)
1152 {
1153   /* We can move the instruction.
1154      Set a target register in block NEW_DEF_BB to the value
1155      needed for this target register definition.
1156      Replace all uses of the old target register definition by
1157      uses of the new definition.  Delete the old definition.  */
1158   basic_block b = new_def_bb;
1159   rtx insp = BB_HEAD (b);
1160   rtx old_insn = def->insn;
1161   rtx src;
1162   rtx btr_rtx;
1163   rtx new_insn;
1164   enum machine_mode btr_mode;
1165   btr_user user;
1166   rtx set;
1167 
1168   if (dump_file)
1169     fprintf(dump_file, "migrating to basic block %d, using reg %d\n",
1170 	    new_def_bb->index, btr);
1171 
1172   clear_btr_from_live_range (def);
1173   def->btr = btr;
1174   def->bb = new_def_bb;
1175   def->luid = 0;
1176   def->cost = basic_block_freq (new_def_bb);
1177   bitmap_copy (def->live_range, live_range);
1178   combine_btr_defs (def, btrs_live_in_range);
1179   btr = def->btr;
1180   def->other_btr_uses_before_def
1181     = TEST_HARD_REG_BIT (btrs_live[b->index], btr) ? 1 : 0;
1182   add_btr_to_live_range (def, 1);
1183   if (LABEL_P (insp))
1184     insp = NEXT_INSN (insp);
1185   /* N.B.: insp is expected to be NOTE_INSN_BASIC_BLOCK now.  Some
1186      optimizations can result in insp being both first and last insn of
1187      its basic block.  */
1188   /* ?? some assertions to check that insp is sensible? */
1189 
1190   if (def->other_btr_uses_before_def)
1191     {
1192       insp = BB_END (b);
1193       for (insp = BB_END (b); ! INSN_P (insp); insp = PREV_INSN (insp))
1194 	gcc_assert (insp != BB_HEAD (b));
1195 
1196       if (JUMP_P (insp) || can_throw_internal (insp))
1197 	insp = PREV_INSN (insp);
1198     }
1199 
1200   set = single_set (old_insn);
1201   src = SET_SRC (set);
1202   btr_mode = GET_MODE (SET_DEST (set));
1203   btr_rtx = gen_rtx_REG (btr_mode, btr);
1204 
1205   new_insn = gen_move_insn (btr_rtx, src);
1206 
1207   /* Insert target register initialization at head of basic block.  */
1208   def->insn = emit_insn_after (new_insn, insp);
1209 
1210   regs_ever_live[btr] = 1;
1211 
1212   if (dump_file)
1213     fprintf (dump_file, "New pt is insn %d, inserted after insn %d\n",
1214 	     INSN_UID (def->insn), INSN_UID (insp));
1215 
1216   /* Delete the old target register initialization.  */
1217   delete_insn (old_insn);
1218 
1219   /* Replace each use of the old target register by a use of the new target
1220      register.  */
1221   for (user = def->uses; user != NULL; user = user->next)
1222     {
1223       /* Some extra work here to ensure consistent modes, because
1224 	 it seems that a target register REG rtx can be given a different
1225 	 mode depending on the context (surely that should not be
1226 	 the case?).  */
1227       rtx replacement_rtx;
1228       if (GET_MODE (user->use) == GET_MODE (btr_rtx)
1229 	  || GET_MODE (user->use) == VOIDmode)
1230 	replacement_rtx = btr_rtx;
1231       else
1232 	replacement_rtx = gen_rtx_REG (GET_MODE (user->use), btr);
1233       replace_rtx (user->insn, user->use, replacement_rtx);
1234       user->use = replacement_rtx;
1235     }
1236 }
1237 
1238 /* We anticipate intra-block scheduling to be done.  See if INSN could move
1239    up within BB by N_INSNS.  */
1240 static int
can_move_up(basic_block bb,rtx insn,int n_insns)1241 can_move_up (basic_block bb, rtx insn, int n_insns)
1242 {
1243   while (insn != BB_HEAD (bb) && n_insns > 0)
1244     {
1245       insn = PREV_INSN (insn);
1246       /* ??? What if we have an anti-dependency that actually prevents the
1247 	 scheduler from doing the move?  We'd like to re-allocate the register,
1248 	 but not necessarily put the load into another basic block.  */
1249       if (INSN_P (insn))
1250 	n_insns--;
1251     }
1252   return n_insns <= 0;
1253 }
1254 
1255 /* Attempt to migrate the target register definition DEF to an
1256    earlier point in the flowgraph.
1257 
1258    It is a precondition of this function that DEF is migratable:
1259    i.e. it has a constant source, and all uses are unambiguous.
1260 
1261    Only migrations that reduce the cost of DEF will be made.
1262    MIN_COST is the lower bound on the cost of the DEF after migration.
1263    If we migrate DEF so that its cost falls below MIN_COST,
1264    then we do not attempt to migrate further.  The idea is that
1265    we migrate definitions in a priority order based on their cost,
1266    when the cost of this definition falls below MIN_COST, then
1267    there is another definition with cost == MIN_COST which now
1268    has a higher priority than this definition.
1269 
1270    Return nonzero if there may be benefit from attempting to
1271    migrate this DEF further (i.e. we have reduced the cost below
1272    MIN_COST, but we may be able to reduce it further).
1273    Return zero if no further migration is possible.  */
1274 static int
migrate_btr_def(btr_def def,int min_cost)1275 migrate_btr_def (btr_def def, int min_cost)
1276 {
1277   bitmap live_range;
1278   HARD_REG_SET btrs_live_in_range;
1279   int btr_used_near_def = 0;
1280   int def_basic_block_freq;
1281   basic_block try;
1282   int give_up = 0;
1283   int def_moved = 0;
1284   btr_user user;
1285   int def_latency;
1286 
1287   if (dump_file)
1288     fprintf (dump_file,
1289 	     "Attempting to migrate pt from insn %d (cost = %d, min_cost = %d) ... ",
1290 	     INSN_UID (def->insn), def->cost, min_cost);
1291 
1292   if (!def->group || def->has_ambiguous_use)
1293     /* These defs are not migratable.  */
1294     {
1295       if (dump_file)
1296 	fprintf (dump_file, "it's not migratable\n");
1297       return 0;
1298     }
1299 
1300   if (!def->uses)
1301     /* We have combined this def with another in the same group, so
1302        no need to consider it further.
1303     */
1304     {
1305       if (dump_file)
1306 	fprintf (dump_file, "it's already combined with another pt\n");
1307       return 0;
1308     }
1309 
1310   btr_def_live_range (def, &btrs_live_in_range);
1311   live_range = BITMAP_ALLOC (NULL);
1312   bitmap_copy (live_range, def->live_range);
1313 
1314 #ifdef INSN_SCHEDULING
1315   def_latency = insn_default_latency (def->insn) * issue_rate;
1316 #else
1317   def_latency = issue_rate;
1318 #endif
1319 
1320   for (user = def->uses; user != NULL; user = user->next)
1321     {
1322       if (user->bb == def->bb
1323 	  && user->luid > def->luid
1324 	  && (def->luid + def_latency) > user->luid
1325 	  && ! can_move_up (def->bb, def->insn,
1326 			    (def->luid + def_latency) - user->luid))
1327 	{
1328 	  btr_used_near_def = 1;
1329 	  break;
1330 	}
1331     }
1332 
1333   def_basic_block_freq = basic_block_freq (def->bb);
1334 
1335   for (try = get_immediate_dominator (CDI_DOMINATORS, def->bb);
1336        !give_up && try && try != ENTRY_BLOCK_PTR && def->cost >= min_cost;
1337        try = get_immediate_dominator (CDI_DOMINATORS, try))
1338     {
1339       /* Try to move the instruction that sets the target register into
1340 	 basic block TRY.  */
1341       int try_freq = basic_block_freq (try);
1342       edge_iterator ei;
1343       edge e;
1344 
1345       /* If TRY has abnormal edges, skip it.  */
1346       FOR_EACH_EDGE (e, ei, try->succs)
1347 	if (e->flags & EDGE_COMPLEX)
1348 	  break;
1349       if (e)
1350 	continue;
1351 
1352       if (dump_file)
1353 	fprintf (dump_file, "trying block %d ...", try->index);
1354 
1355       if (try_freq < def_basic_block_freq
1356 	  || (try_freq == def_basic_block_freq && btr_used_near_def))
1357 	{
1358 	  int btr;
1359 	  augment_live_range (live_range, &btrs_live_in_range, def->bb, try,
1360 			      flag_btr_bb_exclusive);
1361 	  if (dump_file)
1362 	    {
1363 	      fprintf (dump_file, "Now btrs live in range are: ");
1364 	      dump_hard_reg_set (btrs_live_in_range);
1365 	      fprintf (dump_file, "\n");
1366 	    }
1367 	  btr = choose_btr (btrs_live_in_range);
1368 	  if (btr != -1)
1369 	    {
1370 	      move_btr_def (try, btr, def, live_range, &btrs_live_in_range);
1371 	      bitmap_copy(live_range, def->live_range);
1372 	      btr_used_near_def = 0;
1373 	      def_moved = 1;
1374 	      def_basic_block_freq = basic_block_freq (def->bb);
1375 	    }
1376 	  else
1377 	    {
1378 	      /* There are no free target registers available to move
1379 		 this far forward, so give up */
1380 	      give_up = 1;
1381 	      if (dump_file)
1382 		fprintf (dump_file,
1383 			 "giving up because there are no free target registers\n");
1384 	    }
1385 
1386 	}
1387     }
1388   if (!def_moved)
1389     {
1390       give_up = 1;
1391       if (dump_file)
1392 	fprintf (dump_file, "failed to move\n");
1393     }
1394   BITMAP_FREE (live_range);
1395   return !give_up;
1396 }
1397 
1398 /* Attempt to move instructions that set target registers earlier
1399    in the flowgraph, away from their corresponding uses.  */
1400 static void
migrate_btr_defs(enum reg_class btr_class,int allow_callee_save)1401 migrate_btr_defs (enum reg_class btr_class, int allow_callee_save)
1402 {
1403   fibheap_t all_btr_defs = fibheap_new ();
1404   int reg;
1405 
1406   gcc_obstack_init (&migrate_btrl_obstack);
1407   if (dump_file)
1408     {
1409       int i;
1410 
1411       for (i = NUM_FIXED_BLOCKS; i < n_basic_blocks; i++)
1412 	{
1413 	  basic_block bb = BASIC_BLOCK (i);
1414 	  fprintf(dump_file,
1415 	    "Basic block %d: count = " HOST_WIDEST_INT_PRINT_DEC
1416 	    " loop-depth = %d idom = %d\n",
1417 	    i, (HOST_WIDEST_INT) bb->count, bb->loop_depth,
1418 	    get_immediate_dominator (CDI_DOMINATORS, bb)->index);
1419 	}
1420     }
1421 
1422   CLEAR_HARD_REG_SET (all_btrs);
1423   for (first_btr = -1, reg = 0; reg < FIRST_PSEUDO_REGISTER; reg++)
1424     if (TEST_HARD_REG_BIT (reg_class_contents[(int) btr_class], reg)
1425 	&& (allow_callee_save || call_used_regs[reg] || regs_ever_live[reg]))
1426       {
1427 	SET_HARD_REG_BIT (all_btrs, reg);
1428 	last_btr = reg;
1429 	if (first_btr < 0)
1430 	  first_btr = reg;
1431       }
1432 
1433   btrs_live = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1434   btrs_live_at_end = xcalloc (n_basic_blocks, sizeof (HARD_REG_SET));
1435 
1436   build_btr_def_use_webs (all_btr_defs);
1437 
1438   while (!fibheap_empty (all_btr_defs))
1439     {
1440       btr_def def = fibheap_extract_min (all_btr_defs);
1441       int min_cost = -fibheap_min_key (all_btr_defs);
1442       if (migrate_btr_def (def, min_cost))
1443 	{
1444 	  fibheap_insert (all_btr_defs, -def->cost, (void *) def);
1445 	  if (dump_file)
1446 	    {
1447 	      fprintf (dump_file,
1448 		"Putting insn %d back on queue with priority %d\n",
1449 		INSN_UID (def->insn), def->cost);
1450 	    }
1451 	}
1452       else
1453 	BITMAP_FREE (def->live_range);
1454     }
1455 
1456   free (btrs_live);
1457   free (btrs_live_at_end);
1458   obstack_free (&migrate_btrl_obstack, NULL);
1459   fibheap_delete (all_btr_defs);
1460 }
1461 
1462 void
branch_target_load_optimize(bool after_prologue_epilogue_gen)1463 branch_target_load_optimize (bool after_prologue_epilogue_gen)
1464 {
1465   enum reg_class class = targetm.branch_target_register_class ();
1466   if (class != NO_REGS)
1467     {
1468       /* Initialize issue_rate.  */
1469       if (targetm.sched.issue_rate)
1470 	issue_rate = targetm.sched.issue_rate ();
1471       else
1472 	issue_rate = 1;
1473 
1474       /* Build the CFG for migrate_btr_defs.  */
1475 #if 1
1476       /* This may or may not be needed, depending on where we
1477 	 run this phase.  */
1478       cleanup_cfg (optimize ? CLEANUP_EXPENSIVE : 0);
1479 #endif
1480 
1481       life_analysis (0);
1482 
1483       /* Dominator info is also needed for migrate_btr_def.  */
1484       calculate_dominance_info (CDI_DOMINATORS);
1485       migrate_btr_defs (class,
1486 		       (targetm.branch_target_register_callee_saved
1487 			(after_prologue_epilogue_gen)));
1488 
1489       free_dominance_info (CDI_DOMINATORS);
1490 
1491       update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
1492 			PROP_DEATH_NOTES | PROP_REG_INFO);
1493     }
1494 }
1495 
1496 static bool
gate_handle_branch_target_load_optimize(void)1497 gate_handle_branch_target_load_optimize (void)
1498 {
1499   return (optimize > 0 && flag_branch_target_load_optimize2);
1500 }
1501 
1502 
1503 static unsigned int
rest_of_handle_branch_target_load_optimize(void)1504 rest_of_handle_branch_target_load_optimize (void)
1505 {
1506   static int warned = 0;
1507 
1508   /* Leave this a warning for now so that it is possible to experiment
1509      with running this pass twice.  In 3.6, we should either make this
1510      an error, or use separate dump files.  */
1511   if (flag_branch_target_load_optimize
1512       && flag_branch_target_load_optimize2
1513       && !warned)
1514     {
1515       warning (0, "branch target register load optimization is not intended "
1516 		  "to be run twice");
1517 
1518       warned = 1;
1519     }
1520 
1521   branch_target_load_optimize (epilogue_completed);
1522   return 0;
1523 }
1524 
1525 struct tree_opt_pass pass_branch_target_load_optimize =
1526 {
1527   "btl",                               /* name */
1528   gate_handle_branch_target_load_optimize,      /* gate */
1529   rest_of_handle_branch_target_load_optimize,   /* execute */
1530   NULL,                                 /* sub */
1531   NULL,                                 /* next */
1532   0,                                    /* static_pass_number */
1533   0,					/* tv_id */
1534   0,                                    /* properties_required */
1535   0,                                    /* properties_provided */
1536   0,                                    /* properties_destroyed */
1537   0,                                    /* todo_flags_start */
1538   TODO_dump_func |
1539   TODO_ggc_collect,                     /* todo_flags_finish */
1540   'd'                                   /* letter */
1541 };
1542 
1543