OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [bt-load.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.