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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [loop-invariant.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
/* RTL-level loop invariant motion.
2
   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010
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
8
under the terms of the GNU General Public License as published by the
9
Free Software Foundation; either version 3, or (at your option) any
10
later version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT
13
ANY 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
/* This implements the loop invariant motion pass.  It is very simple
22
   (no calls, no loads/stores, etc.).  This should be sufficient to cleanup
23
   things like address arithmetics -- other more complicated invariants should
24
   be eliminated on GIMPLE either in tree-ssa-loop-im.c or in tree-ssa-pre.c.
25
 
26
   We proceed loop by loop -- it is simpler than trying to handle things
27
   globally and should not lose much.  First we inspect all sets inside loop
28
   and create a dependency graph on insns (saying "to move this insn, you must
29
   also move the following insns").
30
 
31
   We then need to determine what to move.  We estimate the number of registers
32
   used and move as many invariants as possible while we still have enough free
33
   registers.  We prefer the expensive invariants.
34
 
35
   Then we move the selected invariants out of the loop, creating a new
36
   temporaries for them if necessary.  */
37
 
38
#include "config.h"
39
#include "system.h"
40
#include "coretypes.h"
41
#include "tm.h"
42
#include "hard-reg-set.h"
43
#include "rtl.h"
44
#include "tm_p.h"
45
#include "obstack.h"
46
#include "basic-block.h"
47
#include "cfgloop.h"
48
#include "expr.h"
49
#include "recog.h"
50
#include "output.h"
51
#include "function.h"
52
#include "flags.h"
53
#include "df.h"
54
#include "hashtab.h"
55
#include "except.h"
56
#include "params.h"
57
#include "regs.h"
58
#include "ira.h"
59
 
60
/* The data stored for the loop.  */
61
 
62
struct loop_data
63
{
64
  struct loop *outermost_exit;  /* The outermost exit of the loop.  */
65
  bool has_call;                /* True if the loop contains a call.  */
66
  /* Maximal register pressure inside loop for given register class
67
     (defined only for the cover classes).  */
68
  int max_reg_pressure[N_REG_CLASSES];
69
  /* Loop regs referenced and live pseudo-registers.  */
70
  bitmap_head regs_ref;
71
  bitmap_head regs_live;
72
};
73
 
74
#define LOOP_DATA(LOOP) ((struct loop_data *) (LOOP)->aux)
75
 
76
/* The description of an use.  */
77
 
78
struct use
79
{
80
  rtx *pos;                     /* Position of the use.  */
81
  rtx insn;                     /* The insn in that the use occurs.  */
82
  unsigned addr_use_p;          /* Whether the use occurs in an address.  */
83
  struct use *next;             /* Next use in the list.  */
84
};
85
 
86
/* The description of a def.  */
87
 
88
struct def
89
{
90
  struct use *uses;             /* The list of uses that are uniquely reached
91
                                   by it.  */
92
  unsigned n_uses;              /* Number of such uses.  */
93
  unsigned n_addr_uses;         /* Number of uses in addresses.  */
94
  unsigned invno;               /* The corresponding invariant.  */
95
};
96
 
97
/* The data stored for each invariant.  */
98
 
99
struct invariant
100
{
101
  /* The number of the invariant.  */
102
  unsigned invno;
103
 
104
  /* The number of the invariant with the same value.  */
105
  unsigned eqto;
106
 
107
  /* If we moved the invariant out of the loop, the register that contains its
108
     value.  */
109
  rtx reg;
110
 
111
  /* If we moved the invariant out of the loop, the original regno
112
     that contained its value.  */
113
  int orig_regno;
114
 
115
  /* The definition of the invariant.  */
116
  struct def *def;
117
 
118
  /* The insn in that it is defined.  */
119
  rtx insn;
120
 
121
  /* Whether it is always executed.  */
122
  bool always_executed;
123
 
124
  /* Whether to move the invariant.  */
125
  bool move;
126
 
127
  /* Whether the invariant is cheap when used as an address.  */
128
  bool cheap_address;
129
 
130
  /* Cost of the invariant.  */
131
  unsigned cost;
132
 
133
  /* The invariants it depends on.  */
134
  bitmap depends_on;
135
 
136
  /* Used for detecting already visited invariants during determining
137
     costs of movements.  */
138
  unsigned stamp;
139
};
140
 
141
/* Currently processed loop.  */
142
static struct loop *curr_loop;
143
 
144
/* Table of invariants indexed by the df_ref uid field.  */
145
 
146
static unsigned int invariant_table_size = 0;
147
static struct invariant ** invariant_table;
148
 
149
/* Entry for hash table of invariant expressions.  */
150
 
151
struct invariant_expr_entry
152
{
153
  /* The invariant.  */
154
  struct invariant *inv;
155
 
156
  /* Its value.  */
157
  rtx expr;
158
 
159
  /* Its mode.  */
160
  enum machine_mode mode;
161
 
162
  /* Its hash.  */
163
  hashval_t hash;
164
};
165
 
166
/* The actual stamp for marking already visited invariants during determining
167
   costs of movements.  */
168
 
169
static unsigned actual_stamp;
170
 
171
typedef struct invariant *invariant_p;
172
 
173
DEF_VEC_P(invariant_p);
174
DEF_VEC_ALLOC_P(invariant_p, heap);
175
 
176
/* The invariants.  */
177
 
178
static VEC(invariant_p,heap) *invariants;
179
 
180
/* Check the size of the invariant table and realloc if necessary.  */
181
 
182
static void
183
check_invariant_table_size (void)
184
{
185
  if (invariant_table_size < DF_DEFS_TABLE_SIZE())
186
    {
187
      unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
188
      invariant_table = XRESIZEVEC (struct invariant *, invariant_table, new_size);
189
      memset (&invariant_table[invariant_table_size], 0,
190
              (new_size - invariant_table_size) * sizeof (struct rtx_iv *));
191
      invariant_table_size = new_size;
192
    }
193
}
194
 
195
/* Test for possibility of invariantness of X.  */
196
 
197
static bool
198
check_maybe_invariant (rtx x)
199
{
200
  enum rtx_code code = GET_CODE (x);
201
  int i, j;
202
  const char *fmt;
203
 
204
  switch (code)
205
    {
206
    case CONST_INT:
207
    case CONST_DOUBLE:
208
    case CONST_FIXED:
209
    case SYMBOL_REF:
210
    case CONST:
211
    case LABEL_REF:
212
      return true;
213
 
214
    case PC:
215
    case CC0:
216
    case UNSPEC_VOLATILE:
217
    case CALL:
218
      return false;
219
 
220
    case REG:
221
      return true;
222
 
223
    case MEM:
224
      /* Load/store motion is done elsewhere.  ??? Perhaps also add it here?
225
         It should not be hard, and might be faster than "elsewhere".  */
226
 
227
      /* Just handle the most trivial case where we load from an unchanging
228
         location (most importantly, pic tables).  */
229
      if (MEM_READONLY_P (x) && !MEM_VOLATILE_P (x))
230
        break;
231
 
232
      return false;
233
 
234
    case ASM_OPERANDS:
235
      /* Don't mess with insns declared volatile.  */
236
      if (MEM_VOLATILE_P (x))
237
        return false;
238
      break;
239
 
240
    default:
241
      break;
242
    }
243
 
244
  fmt = GET_RTX_FORMAT (code);
245
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
246
    {
247
      if (fmt[i] == 'e')
248
        {
249
          if (!check_maybe_invariant (XEXP (x, i)))
250
            return false;
251
        }
252
      else if (fmt[i] == 'E')
253
        {
254
          for (j = 0; j < XVECLEN (x, i); j++)
255
            if (!check_maybe_invariant (XVECEXP (x, i, j)))
256
              return false;
257
        }
258
    }
259
 
260
  return true;
261
}
262
 
263
/* Returns the invariant definition for USE, or NULL if USE is not
264
   invariant.  */
265
 
266
static struct invariant *
267
invariant_for_use (df_ref use)
268
{
269
  struct df_link *defs;
270
  df_ref def;
271
  basic_block bb = DF_REF_BB (use), def_bb;
272
 
273
  if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
274
    return NULL;
275
 
276
  defs = DF_REF_CHAIN (use);
277
  if (!defs || defs->next)
278
    return NULL;
279
  def = defs->ref;
280
  check_invariant_table_size ();
281
  if (!invariant_table[DF_REF_ID(def)])
282
    return NULL;
283
 
284
  def_bb = DF_REF_BB (def);
285
  if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
286
    return NULL;
287
  return invariant_table[DF_REF_ID(def)];
288
}
289
 
290
/* Computes hash value for invariant expression X in INSN.  */
291
 
292
static hashval_t
293
hash_invariant_expr_1 (rtx insn, rtx x)
294
{
295
  enum rtx_code code = GET_CODE (x);
296
  int i, j;
297
  const char *fmt;
298
  hashval_t val = code;
299
  int do_not_record_p;
300
  df_ref use;
301
  struct invariant *inv;
302
 
303
  switch (code)
304
    {
305
    case CONST_INT:
306
    case CONST_DOUBLE:
307
    case CONST_FIXED:
308
    case SYMBOL_REF:
309
    case CONST:
310
    case LABEL_REF:
311
      return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
312
 
313
    case REG:
314
      use = df_find_use (insn, x);
315
      if (!use)
316
        return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
317
      inv = invariant_for_use (use);
318
      if (!inv)
319
        return hash_rtx (x, GET_MODE (x), &do_not_record_p, NULL, false);
320
 
321
      gcc_assert (inv->eqto != ~0u);
322
      return inv->eqto;
323
 
324
    default:
325
      break;
326
    }
327
 
328
  fmt = GET_RTX_FORMAT (code);
329
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
330
    {
331
      if (fmt[i] == 'e')
332
        val ^= hash_invariant_expr_1 (insn, XEXP (x, i));
333
      else if (fmt[i] == 'E')
334
        {
335
          for (j = 0; j < XVECLEN (x, i); j++)
336
            val ^= hash_invariant_expr_1 (insn, XVECEXP (x, i, j));
337
        }
338
      else if (fmt[i] == 'i' || fmt[i] == 'n')
339
        val ^= XINT (x, i);
340
    }
341
 
342
  return val;
343
}
344
 
345
/* Returns true if the invariant expressions E1 and E2 used in insns INSN1
346
   and INSN2 have always the same value.  */
347
 
348
static bool
349
invariant_expr_equal_p (rtx insn1, rtx e1, rtx insn2, rtx e2)
350
{
351
  enum rtx_code code = GET_CODE (e1);
352
  int i, j;
353
  const char *fmt;
354
  df_ref use1, use2;
355
  struct invariant *inv1 = NULL, *inv2 = NULL;
356
  rtx sub1, sub2;
357
 
358
  /* If mode of only one of the operands is VOIDmode, it is not equivalent to
359
     the other one.  If both are VOIDmode, we rely on the caller of this
360
     function to verify that their modes are the same.  */
361
  if (code != GET_CODE (e2) || GET_MODE (e1) != GET_MODE (e2))
362
    return false;
363
 
364
  switch (code)
365
    {
366
    case CONST_INT:
367
    case CONST_DOUBLE:
368
    case CONST_FIXED:
369
    case SYMBOL_REF:
370
    case CONST:
371
    case LABEL_REF:
372
      return rtx_equal_p (e1, e2);
373
 
374
    case REG:
375
      use1 = df_find_use (insn1, e1);
376
      use2 = df_find_use (insn2, e2);
377
      if (use1)
378
        inv1 = invariant_for_use (use1);
379
      if (use2)
380
        inv2 = invariant_for_use (use2);
381
 
382
      if (!inv1 && !inv2)
383
        return rtx_equal_p (e1, e2);
384
 
385
      if (!inv1 || !inv2)
386
        return false;
387
 
388
      gcc_assert (inv1->eqto != ~0u);
389
      gcc_assert (inv2->eqto != ~0u);
390
      return inv1->eqto == inv2->eqto;
391
 
392
    default:
393
      break;
394
    }
395
 
396
  fmt = GET_RTX_FORMAT (code);
397
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
398
    {
399
      if (fmt[i] == 'e')
400
        {
401
          sub1 = XEXP (e1, i);
402
          sub2 = XEXP (e2, i);
403
 
404
          if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
405
            return false;
406
        }
407
 
408
      else if (fmt[i] == 'E')
409
        {
410
          if (XVECLEN (e1, i) != XVECLEN (e2, i))
411
            return false;
412
 
413
          for (j = 0; j < XVECLEN (e1, i); j++)
414
            {
415
              sub1 = XVECEXP (e1, i, j);
416
              sub2 = XVECEXP (e2, i, j);
417
 
418
              if (!invariant_expr_equal_p (insn1, sub1, insn2, sub2))
419
                return false;
420
            }
421
        }
422
      else if (fmt[i] == 'i' || fmt[i] == 'n')
423
        {
424
          if (XINT (e1, i) != XINT (e2, i))
425
            return false;
426
        }
427
      /* Unhandled type of subexpression, we fail conservatively.  */
428
      else
429
        return false;
430
    }
431
 
432
  return true;
433
}
434
 
435
/* Returns hash value for invariant expression entry E.  */
436
 
437
static hashval_t
438
hash_invariant_expr (const void *e)
439
{
440
  const struct invariant_expr_entry *const entry =
441
    (const struct invariant_expr_entry *) e;
442
 
443
  return entry->hash;
444
}
445
 
446
/* Compares invariant expression entries E1 and E2.  */
447
 
448
static int
449
eq_invariant_expr (const void *e1, const void *e2)
450
{
451
  const struct invariant_expr_entry *const entry1 =
452
    (const struct invariant_expr_entry *) e1;
453
  const struct invariant_expr_entry *const entry2 =
454
    (const struct invariant_expr_entry *) e2;
455
 
456
  if (entry1->mode != entry2->mode)
457
    return 0;
458
 
459
  return invariant_expr_equal_p (entry1->inv->insn, entry1->expr,
460
                                 entry2->inv->insn, entry2->expr);
461
}
462
 
463
/* Checks whether invariant with value EXPR in machine mode MODE is
464
   recorded in EQ.  If this is the case, return the invariant.  Otherwise
465
   insert INV to the table for this expression and return INV.  */
466
 
467
static struct invariant *
468
find_or_insert_inv (htab_t eq, rtx expr, enum machine_mode mode,
469
                    struct invariant *inv)
470
{
471
  hashval_t hash = hash_invariant_expr_1 (inv->insn, expr);
472
  struct invariant_expr_entry *entry;
473
  struct invariant_expr_entry pentry;
474
  PTR *slot;
475
 
476
  pentry.expr = expr;
477
  pentry.inv = inv;
478
  pentry.mode = mode;
479
  slot = htab_find_slot_with_hash (eq, &pentry, hash, INSERT);
480
  entry = (struct invariant_expr_entry *) *slot;
481
 
482
  if (entry)
483
    return entry->inv;
484
 
485
  entry = XNEW (struct invariant_expr_entry);
486
  entry->inv = inv;
487
  entry->expr = expr;
488
  entry->mode = mode;
489
  entry->hash = hash;
490
  *slot = entry;
491
 
492
  return inv;
493
}
494
 
495
/* Finds invariants identical to INV and records the equivalence.  EQ is the
496
   hash table of the invariants.  */
497
 
498
static void
499
find_identical_invariants (htab_t eq, struct invariant *inv)
500
{
501
  unsigned depno;
502
  bitmap_iterator bi;
503
  struct invariant *dep;
504
  rtx expr, set;
505
  enum machine_mode mode;
506
 
507
  if (inv->eqto != ~0u)
508
    return;
509
 
510
  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
511
    {
512
      dep = VEC_index (invariant_p, invariants, depno);
513
      find_identical_invariants (eq, dep);
514
    }
515
 
516
  set = single_set (inv->insn);
517
  expr = SET_SRC (set);
518
  mode = GET_MODE (expr);
519
  if (mode == VOIDmode)
520
    mode = GET_MODE (SET_DEST (set));
521
  inv->eqto = find_or_insert_inv (eq, expr, mode, inv)->invno;
522
 
523
  if (dump_file && inv->eqto != inv->invno)
524
    fprintf (dump_file,
525
             "Invariant %d is equivalent to invariant %d.\n",
526
             inv->invno, inv->eqto);
527
}
528
 
529
/* Find invariants with the same value and record the equivalences.  */
530
 
531
static void
532
merge_identical_invariants (void)
533
{
534
  unsigned i;
535
  struct invariant *inv;
536
  htab_t eq = htab_create (VEC_length (invariant_p, invariants),
537
                           hash_invariant_expr, eq_invariant_expr, free);
538
 
539
  for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
540
    find_identical_invariants (eq, inv);
541
 
542
  htab_delete (eq);
543
}
544
 
545
/* Determines the basic blocks inside LOOP that are always executed and
546
   stores their bitmap to ALWAYS_REACHED.  MAY_EXIT is a bitmap of
547
   basic blocks that may either exit the loop, or contain the call that
548
   does not have to return.  BODY is body of the loop obtained by
549
   get_loop_body_in_dom_order.  */
550
 
551
static void
552
compute_always_reached (struct loop *loop, basic_block *body,
553
                        bitmap may_exit, bitmap always_reached)
554
{
555
  unsigned i;
556
 
557
  for (i = 0; i < loop->num_nodes; i++)
558
    {
559
      if (dominated_by_p (CDI_DOMINATORS, loop->latch, body[i]))
560
        bitmap_set_bit (always_reached, i);
561
 
562
      if (bitmap_bit_p (may_exit, i))
563
        return;
564
    }
565
}
566
 
567
/* Finds exits out of the LOOP with body BODY.  Marks blocks in that we may
568
   exit the loop by cfg edge to HAS_EXIT and MAY_EXIT.  In MAY_EXIT
569
   additionally mark blocks that may exit due to a call.  */
570
 
571
static void
572
find_exits (struct loop *loop, basic_block *body,
573
            bitmap may_exit, bitmap has_exit)
574
{
575
  unsigned i;
576
  edge_iterator ei;
577
  edge e;
578
  struct loop *outermost_exit = loop, *aexit;
579
  bool has_call = false;
580
  rtx insn;
581
 
582
  for (i = 0; i < loop->num_nodes; i++)
583
    {
584
      if (body[i]->loop_father == loop)
585
        {
586
          FOR_BB_INSNS (body[i], insn)
587
            {
588
              if (CALL_P (insn)
589
                  && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
590
                      || !RTL_CONST_OR_PURE_CALL_P (insn)))
591
                {
592
                  has_call = true;
593
                  bitmap_set_bit (may_exit, i);
594
                  break;
595
                }
596
            }
597
 
598
          FOR_EACH_EDGE (e, ei, body[i]->succs)
599
            {
600
              if (flow_bb_inside_loop_p (loop, e->dest))
601
                continue;
602
 
603
              bitmap_set_bit (may_exit, i);
604
              bitmap_set_bit (has_exit, i);
605
              outermost_exit = find_common_loop (outermost_exit,
606
                                                 e->dest->loop_father);
607
            }
608
          continue;
609
        }
610
 
611
      /* Use the data stored for the subloop to decide whether we may exit
612
         through it.  It is sufficient to do this for header of the loop,
613
         as other basic blocks inside it must be dominated by it.  */
614
      if (body[i]->loop_father->header != body[i])
615
        continue;
616
 
617
      if (LOOP_DATA (body[i]->loop_father)->has_call)
618
        {
619
          has_call = true;
620
          bitmap_set_bit (may_exit, i);
621
        }
622
      aexit = LOOP_DATA (body[i]->loop_father)->outermost_exit;
623
      if (aexit != loop)
624
        {
625
          bitmap_set_bit (may_exit, i);
626
          bitmap_set_bit (has_exit, i);
627
 
628
          if (flow_loop_nested_p (aexit, outermost_exit))
629
            outermost_exit = aexit;
630
        }
631
    }
632
 
633
  if (loop->aux == NULL)
634
    {
635
      loop->aux = xcalloc (1, sizeof (struct loop_data));
636
      bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
637
      bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
638
    }
639
  LOOP_DATA (loop)->outermost_exit = outermost_exit;
640
  LOOP_DATA (loop)->has_call = has_call;
641
}
642
 
643
/* Check whether we may assign a value to X from a register.  */
644
 
645
static bool
646
may_assign_reg_p (rtx x)
647
{
648
  return (GET_MODE (x) != VOIDmode
649
          && GET_MODE (x) != BLKmode
650
          && can_copy_p (GET_MODE (x))
651
          && (!REG_P (x)
652
              || !HARD_REGISTER_P (x)
653
              || REGNO_REG_CLASS (REGNO (x)) != NO_REGS));
654
}
655
 
656
/* Finds definitions that may correspond to invariants in LOOP with body
657
   BODY.  */
658
 
659
static void
660
find_defs (struct loop *loop, basic_block *body)
661
{
662
  unsigned i;
663
  bitmap blocks = BITMAP_ALLOC (NULL);
664
 
665
  for (i = 0; i < loop->num_nodes; i++)
666
    bitmap_set_bit (blocks, body[i]->index);
667
 
668
  df_remove_problem (df_chain);
669
  df_process_deferred_rescans ();
670
  df_chain_add_problem (DF_UD_CHAIN);
671
  df_set_blocks (blocks);
672
  df_analyze ();
673
 
674
  if (dump_file)
675
    {
676
      df_dump_region (dump_file);
677
      fprintf (dump_file, "*****starting processing of loop  ******\n");
678
      print_rtl_with_bb (dump_file, get_insns ());
679
      fprintf (dump_file, "*****ending processing of loop  ******\n");
680
    }
681
  check_invariant_table_size ();
682
 
683
  BITMAP_FREE (blocks);
684
}
685
 
686
/* Creates a new invariant for definition DEF in INSN, depending on invariants
687
   in DEPENDS_ON.  ALWAYS_EXECUTED is true if the insn is always executed,
688
   unless the program ends due to a function call.  The newly created invariant
689
   is returned.  */
690
 
691
static struct invariant *
692
create_new_invariant (struct def *def, rtx insn, bitmap depends_on,
693
                      bool always_executed)
694
{
695
  struct invariant *inv = XNEW (struct invariant);
696
  rtx set = single_set (insn);
697
  bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
698
 
699
  inv->def = def;
700
  inv->always_executed = always_executed;
701
  inv->depends_on = depends_on;
702
 
703
  /* If the set is simple, usually by moving it we move the whole store out of
704
     the loop.  Otherwise we save only cost of the computation.  */
705
  if (def)
706
    {
707
      inv->cost = rtx_cost (set, SET, speed);
708
      /* ??? Try to determine cheapness of address computation.  Unfortunately
709
         the address cost is only a relative measure, we can't really compare
710
         it with any absolute number, but only with other address costs.
711
         But here we don't have any other addresses, so compare with a magic
712
         number anyway.  It has to be large enough to not regress PR33928
713
         (by avoiding to move reg+8,reg+16,reg+24 invariants), but small
714
         enough to not regress 410.bwaves either (by still moving reg+reg
715
         invariants).
716
         See http://gcc.gnu.org/ml/gcc-patches/2009-10/msg01210.html .  */
717
      inv->cheap_address = address_cost (SET_SRC (set), word_mode,
718
                                         ADDR_SPACE_GENERIC, speed) < 3;
719
    }
720
  else
721
    {
722
      inv->cost = rtx_cost (SET_SRC (set), SET, speed);
723
      inv->cheap_address = false;
724
    }
725
 
726
  inv->move = false;
727
  inv->reg = NULL_RTX;
728
  inv->orig_regno = -1;
729
  inv->stamp = 0;
730
  inv->insn = insn;
731
 
732
  inv->invno = VEC_length (invariant_p, invariants);
733
  inv->eqto = ~0u;
734
  if (def)
735
    def->invno = inv->invno;
736
  VEC_safe_push (invariant_p, heap, invariants, inv);
737
 
738
  if (dump_file)
739
    {
740
      fprintf (dump_file,
741
               "Set in insn %d is invariant (%d), cost %d, depends on ",
742
               INSN_UID (insn), inv->invno, inv->cost);
743
      dump_bitmap (dump_file, inv->depends_on);
744
    }
745
 
746
  return inv;
747
}
748
 
749
/* Record USE at DEF.  */
750
 
751
static void
752
record_use (struct def *def, df_ref use)
753
{
754
  struct use *u = XNEW (struct use);
755
 
756
  u->pos = DF_REF_REAL_LOC (use);
757
  u->insn = DF_REF_INSN (use);
758
  u->addr_use_p = (DF_REF_TYPE (use) == DF_REF_REG_MEM_LOAD
759
                   || DF_REF_TYPE (use) == DF_REF_REG_MEM_STORE);
760
  u->next = def->uses;
761
  def->uses = u;
762
  def->n_uses++;
763
  if (u->addr_use_p)
764
    def->n_addr_uses++;
765
}
766
 
767
/* Finds the invariants USE depends on and store them to the DEPENDS_ON
768
   bitmap.  Returns true if all dependencies of USE are known to be
769
   loop invariants, false otherwise.  */
770
 
771
static bool
772
check_dependency (basic_block bb, df_ref use, bitmap depends_on)
773
{
774
  df_ref def;
775
  basic_block def_bb;
776
  struct df_link *defs;
777
  struct def *def_data;
778
  struct invariant *inv;
779
 
780
  if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
781
    return false;
782
 
783
  defs = DF_REF_CHAIN (use);
784
  if (!defs)
785
    return true;
786
 
787
  if (defs->next)
788
    return false;
789
 
790
  def = defs->ref;
791
  check_invariant_table_size ();
792
  inv = invariant_table[DF_REF_ID(def)];
793
  if (!inv)
794
    return false;
795
 
796
  def_data = inv->def;
797
  gcc_assert (def_data != NULL);
798
 
799
  def_bb = DF_REF_BB (def);
800
  /* Note that in case bb == def_bb, we know that the definition
801
     dominates insn, because def has invariant_table[DF_REF_ID(def)]
802
     defined and we process the insns in the basic block bb
803
     sequentially.  */
804
  if (!dominated_by_p (CDI_DOMINATORS, bb, def_bb))
805
    return false;
806
 
807
  bitmap_set_bit (depends_on, def_data->invno);
808
  return true;
809
}
810
 
811
 
812
/* Finds the invariants INSN depends on and store them to the DEPENDS_ON
813
   bitmap.  Returns true if all dependencies of INSN are known to be
814
   loop invariants, false otherwise.  */
815
 
816
static bool
817
check_dependencies (rtx insn, bitmap depends_on)
818
{
819
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
820
  df_ref *use_rec;
821
  basic_block bb = BLOCK_FOR_INSN (insn);
822
 
823
  for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
824
    if (!check_dependency (bb, *use_rec, depends_on))
825
      return false;
826
  for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
827
    if (!check_dependency (bb, *use_rec, depends_on))
828
      return false;
829
 
830
  return true;
831
}
832
 
833
/* Finds invariant in INSN.  ALWAYS_REACHED is true if the insn is always
834
   executed.  ALWAYS_EXECUTED is true if the insn is always executed,
835
   unless the program ends due to a function call.  */
836
 
837
static void
838
find_invariant_insn (rtx insn, bool always_reached, bool always_executed)
839
{
840
  df_ref ref;
841
  struct def *def;
842
  bitmap depends_on;
843
  rtx set, dest;
844
  bool simple = true;
845
  struct invariant *inv;
846
 
847
#ifdef HAVE_cc0
848
  /* We can't move a CC0 setter without the user.  */
849
  if (sets_cc0_p (insn))
850
    return;
851
#endif
852
 
853
  set = single_set (insn);
854
  if (!set)
855
    return;
856
  dest = SET_DEST (set);
857
 
858
  if (!REG_P (dest)
859
      || HARD_REGISTER_P (dest))
860
    simple = false;
861
 
862
  if (!may_assign_reg_p (SET_DEST (set))
863
      || !check_maybe_invariant (SET_SRC (set)))
864
    return;
865
 
866
  /* If the insn can throw exception, we cannot move it at all without changing
867
     cfg.  */
868
  if (can_throw_internal (insn))
869
    return;
870
 
871
  /* We cannot make trapping insn executed, unless it was executed before.  */
872
  if (may_trap_or_fault_p (PATTERN (insn)) && !always_reached)
873
    return;
874
 
875
  depends_on = BITMAP_ALLOC (NULL);
876
  if (!check_dependencies (insn, depends_on))
877
    {
878
      BITMAP_FREE (depends_on);
879
      return;
880
    }
881
 
882
  if (simple)
883
    def = XCNEW (struct def);
884
  else
885
    def = NULL;
886
 
887
  inv = create_new_invariant (def, insn, depends_on, always_executed);
888
 
889
  if (simple)
890
    {
891
      ref = df_find_def (insn, dest);
892
      check_invariant_table_size ();
893
      invariant_table[DF_REF_ID(ref)] = inv;
894
    }
895
}
896
 
897
/* Record registers used in INSN that have a unique invariant definition.  */
898
 
899
static void
900
record_uses (rtx insn)
901
{
902
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
903
  df_ref *use_rec;
904
  struct invariant *inv;
905
 
906
  for (use_rec = DF_INSN_INFO_USES (insn_info); *use_rec; use_rec++)
907
    {
908
      df_ref use = *use_rec;
909
      inv = invariant_for_use (use);
910
      if (inv)
911
        record_use (inv->def, use);
912
    }
913
  for (use_rec = DF_INSN_INFO_EQ_USES (insn_info); *use_rec; use_rec++)
914
    {
915
      df_ref use = *use_rec;
916
      inv = invariant_for_use (use);
917
      if (inv)
918
        record_use (inv->def, use);
919
    }
920
}
921
 
922
/* Finds invariants in INSN.  ALWAYS_REACHED is true if the insn is always
923
   executed.  ALWAYS_EXECUTED is true if the insn is always executed,
924
   unless the program ends due to a function call.  */
925
 
926
static void
927
find_invariants_insn (rtx insn, bool always_reached, bool always_executed)
928
{
929
  find_invariant_insn (insn, always_reached, always_executed);
930
  record_uses (insn);
931
}
932
 
933
/* Finds invariants in basic block BB.  ALWAYS_REACHED is true if the
934
   basic block is always executed.  ALWAYS_EXECUTED is true if the basic
935
   block is always executed, unless the program ends due to a function
936
   call.  */
937
 
938
static void
939
find_invariants_bb (basic_block bb, bool always_reached, bool always_executed)
940
{
941
  rtx insn;
942
 
943
  FOR_BB_INSNS (bb, insn)
944
    {
945
      if (!NONDEBUG_INSN_P (insn))
946
        continue;
947
 
948
      find_invariants_insn (insn, always_reached, always_executed);
949
 
950
      if (always_reached
951
          && CALL_P (insn)
952
          && (RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)
953
              || ! RTL_CONST_OR_PURE_CALL_P (insn)))
954
        always_reached = false;
955
    }
956
}
957
 
958
/* Finds invariants in LOOP with body BODY.  ALWAYS_REACHED is the bitmap of
959
   basic blocks in BODY that are always executed.  ALWAYS_EXECUTED is the
960
   bitmap of basic blocks in BODY that are always executed unless the program
961
   ends due to a function call.  */
962
 
963
static void
964
find_invariants_body (struct loop *loop, basic_block *body,
965
                      bitmap always_reached, bitmap always_executed)
966
{
967
  unsigned i;
968
 
969
  for (i = 0; i < loop->num_nodes; i++)
970
    find_invariants_bb (body[i],
971
                        bitmap_bit_p (always_reached, i),
972
                        bitmap_bit_p (always_executed, i));
973
}
974
 
975
/* Finds invariants in LOOP.  */
976
 
977
static void
978
find_invariants (struct loop *loop)
979
{
980
  bitmap may_exit = BITMAP_ALLOC (NULL);
981
  bitmap always_reached = BITMAP_ALLOC (NULL);
982
  bitmap has_exit = BITMAP_ALLOC (NULL);
983
  bitmap always_executed = BITMAP_ALLOC (NULL);
984
  basic_block *body = get_loop_body_in_dom_order (loop);
985
 
986
  find_exits (loop, body, may_exit, has_exit);
987
  compute_always_reached (loop, body, may_exit, always_reached);
988
  compute_always_reached (loop, body, has_exit, always_executed);
989
 
990
  find_defs (loop, body);
991
  find_invariants_body (loop, body, always_reached, always_executed);
992
  merge_identical_invariants ();
993
 
994
  BITMAP_FREE (always_reached);
995
  BITMAP_FREE (always_executed);
996
  BITMAP_FREE (may_exit);
997
  BITMAP_FREE (has_exit);
998
  free (body);
999
}
1000
 
1001
/* Frees a list of uses USE.  */
1002
 
1003
static void
1004
free_use_list (struct use *use)
1005
{
1006
  struct use *next;
1007
 
1008
  for (; use; use = next)
1009
    {
1010
      next = use->next;
1011
      free (use);
1012
    }
1013
}
1014
 
1015
/* Return cover class and number of hard registers (through *NREGS)
1016
   for destination of INSN. */
1017
static enum reg_class
1018
get_cover_class_and_nregs (rtx insn, int *nregs)
1019
{
1020
  rtx reg;
1021
  enum reg_class cover_class;
1022
  rtx set = single_set (insn);
1023
 
1024
  /* Considered invariant insns have only one set.  */
1025
  gcc_assert (set != NULL_RTX);
1026
  reg = SET_DEST (set);
1027
  if (GET_CODE (reg) == SUBREG)
1028
    reg = SUBREG_REG (reg);
1029
  if (MEM_P (reg))
1030
    {
1031
      *nregs = 0;
1032
      cover_class = NO_REGS;
1033
    }
1034
  else
1035
    {
1036
      if (! REG_P (reg))
1037
        reg = NULL_RTX;
1038
      if (reg == NULL_RTX)
1039
        cover_class = GENERAL_REGS;
1040
      else
1041
        cover_class = reg_cover_class (REGNO (reg));
1042
      *nregs = ira_reg_class_nregs[cover_class][GET_MODE (SET_SRC (set))];
1043
    }
1044
  return cover_class;
1045
}
1046
 
1047
/* Calculates cost and number of registers needed for moving invariant INV
1048
   out of the loop and stores them to *COST and *REGS_NEEDED.  */
1049
 
1050
static void
1051
get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
1052
{
1053
  int i, acomp_cost;
1054
  unsigned aregs_needed[N_REG_CLASSES];
1055
  unsigned depno;
1056
  struct invariant *dep;
1057
  bitmap_iterator bi;
1058
 
1059
  /* Find the representative of the class of the equivalent invariants.  */
1060
  inv = VEC_index (invariant_p, invariants, inv->eqto);
1061
 
1062
  *comp_cost = 0;
1063
  if (! flag_ira_loop_pressure)
1064
    regs_needed[0] = 0;
1065
  else
1066
    {
1067
      for (i = 0; i < ira_reg_class_cover_size; i++)
1068
        regs_needed[ira_reg_class_cover[i]] = 0;
1069
    }
1070
 
1071
  if (inv->move
1072
      || inv->stamp == actual_stamp)
1073
    return;
1074
  inv->stamp = actual_stamp;
1075
 
1076
  if (! flag_ira_loop_pressure)
1077
    regs_needed[0]++;
1078
  else
1079
    {
1080
      int nregs;
1081
      enum reg_class cover_class;
1082
 
1083
      cover_class = get_cover_class_and_nregs (inv->insn, &nregs);
1084
      regs_needed[cover_class] += nregs;
1085
    }
1086
 
1087
  if (!inv->cheap_address
1088
      || inv->def->n_addr_uses < inv->def->n_uses)
1089
    (*comp_cost) += inv->cost;
1090
 
1091
#ifdef STACK_REGS
1092
  {
1093
    /* Hoisting constant pool constants into stack regs may cost more than
1094
       just single register.  On x87, the balance is affected both by the
1095
       small number of FP registers, and by its register stack organization,
1096
       that forces us to add compensation code in and around the loop to
1097
       shuffle the operands to the top of stack before use, and pop them
1098
       from the stack after the loop finishes.
1099
 
1100
       To model this effect, we increase the number of registers needed for
1101
       stack registers by two: one register push, and one register pop.
1102
       This usually has the effect that FP constant loads from the constant
1103
       pool are not moved out of the loop.
1104
 
1105
       Note that this also means that dependent invariants can not be moved.
1106
       However, the primary purpose of this pass is to move loop invariant
1107
       address arithmetic out of loops, and address arithmetic that depends
1108
       on floating point constants is unlikely to ever occur.  */
1109
    rtx set = single_set (inv->insn);
1110
    if (set
1111
        && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1112
        && constant_pool_constant_p (SET_SRC (set)))
1113
      {
1114
        if (flag_ira_loop_pressure)
1115
          regs_needed[STACK_REG_COVER_CLASS] += 2;
1116
        else
1117
          regs_needed[0] += 2;
1118
      }
1119
  }
1120
#endif
1121
 
1122
  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1123
    {
1124
      bool check_p;
1125
 
1126
      dep = VEC_index (invariant_p, invariants, depno);
1127
 
1128
      get_inv_cost (dep, &acomp_cost, aregs_needed);
1129
 
1130
      if (! flag_ira_loop_pressure)
1131
        check_p = aregs_needed[0] != 0;
1132
      else
1133
        {
1134
          for (i = 0; i < ira_reg_class_cover_size; i++)
1135
            if (aregs_needed[ira_reg_class_cover[i]] != 0)
1136
              break;
1137
          check_p = i < ira_reg_class_cover_size;
1138
        }
1139
      if (check_p
1140
          /* We need to check always_executed, since if the original value of
1141
             the invariant may be preserved, we may need to keep it in a
1142
             separate register.  TODO check whether the register has an
1143
             use outside of the loop.  */
1144
          && dep->always_executed
1145
          && !dep->def->uses->next)
1146
        {
1147
          /* If this is a single use, after moving the dependency we will not
1148
             need a new register.  */
1149
          if (! flag_ira_loop_pressure)
1150
            aregs_needed[0]--;
1151
          else
1152
            {
1153
              int nregs;
1154
              enum reg_class cover_class;
1155
 
1156
              cover_class = get_cover_class_and_nregs (inv->insn, &nregs);
1157
              aregs_needed[cover_class] -= nregs;
1158
            }
1159
        }
1160
 
1161
      if (! flag_ira_loop_pressure)
1162
        regs_needed[0] += aregs_needed[0];
1163
      else
1164
        {
1165
          for (i = 0; i < ira_reg_class_cover_size; i++)
1166
            regs_needed[ira_reg_class_cover[i]]
1167
              += aregs_needed[ira_reg_class_cover[i]];
1168
        }
1169
      (*comp_cost) += acomp_cost;
1170
    }
1171
}
1172
 
1173
/* Calculates gain for eliminating invariant INV.  REGS_USED is the number
1174
   of registers used in the loop, NEW_REGS is the number of new variables
1175
   already added due to the invariant motion.  The number of registers needed
1176
   for it is stored in *REGS_NEEDED.  */
1177
 
1178
static int
1179
gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1180
                    unsigned *new_regs, unsigned regs_used, bool speed)
1181
{
1182
  int comp_cost, size_cost;
1183
 
1184
  actual_stamp++;
1185
 
1186
  get_inv_cost (inv, &comp_cost, regs_needed);
1187
 
1188
  if (! flag_ira_loop_pressure)
1189
    {
1190
      size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1191
                                               regs_used, speed)
1192
                   - estimate_reg_pressure_cost (new_regs[0],
1193
                                                 regs_used, speed));
1194
    }
1195
  else
1196
    {
1197
      int i;
1198
      enum reg_class cover_class;
1199
 
1200
      for (i = 0; i < ira_reg_class_cover_size; i++)
1201
        {
1202
          cover_class = ira_reg_class_cover[i];
1203
          if ((int) new_regs[cover_class]
1204
              + (int) regs_needed[cover_class]
1205
              + LOOP_DATA (curr_loop)->max_reg_pressure[cover_class]
1206
              + IRA_LOOP_RESERVED_REGS
1207
              > ira_available_class_regs[cover_class])
1208
            break;
1209
        }
1210
      if (i < ira_reg_class_cover_size)
1211
        /* There will be register pressure excess and we want not to
1212
           make this loop invariant motion.  All loop invariants with
1213
           non-positive gains will be rejected in function
1214
           find_invariants_to_move.  Therefore we return the negative
1215
           number here.
1216
 
1217
           One could think that this rejects also expensive loop
1218
           invariant motions and this will hurt code performance.
1219
           However numerous experiments with different heuristics
1220
           taking invariant cost into account did not confirm this
1221
           assumption.  There are possible explanations for this
1222
           result:
1223
           o probably all expensive invariants were already moved out
1224
             of the loop by PRE and gimple invariant motion pass.
1225
           o expensive invariant execution will be hidden by insn
1226
             scheduling or OOO processor hardware because usually such
1227
             invariants have a lot of freedom to be executed
1228
             out-of-order.
1229
           Another reason for ignoring invariant cost vs spilling cost
1230
           heuristics is also in difficulties to evaluate accurately
1231
           spill cost at this stage.  */
1232
        return -1;
1233
      else
1234
        size_cost = 0;
1235
    }
1236
 
1237
  return comp_cost - size_cost;
1238
}
1239
 
1240
/* Finds invariant with best gain for moving.  Returns the gain, stores
1241
   the invariant in *BEST and number of registers needed for it to
1242
   *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
1243
   NEW_REGS is the number of new variables already added due to invariant
1244
   motion.  */
1245
 
1246
static int
1247
best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1248
                         unsigned *new_regs, unsigned regs_used, bool speed)
1249
{
1250
  struct invariant *inv;
1251
  int i, gain = 0, again;
1252
  unsigned aregs_needed[N_REG_CLASSES], invno;
1253
 
1254
  for (invno = 0; VEC_iterate (invariant_p, invariants, invno, inv); invno++)
1255
    {
1256
      if (inv->move)
1257
        continue;
1258
 
1259
      /* Only consider the "representatives" of equivalent invariants.  */
1260
      if (inv->eqto != inv->invno)
1261
        continue;
1262
 
1263
      again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1264
                                  speed);
1265
      if (again > gain)
1266
        {
1267
          gain = again;
1268
          *best = inv;
1269
          if (! flag_ira_loop_pressure)
1270
            regs_needed[0] = aregs_needed[0];
1271
          else
1272
            {
1273
              for (i = 0; i < ira_reg_class_cover_size; i++)
1274
                regs_needed[ira_reg_class_cover[i]]
1275
                  = aregs_needed[ira_reg_class_cover[i]];
1276
            }
1277
        }
1278
    }
1279
 
1280
  return gain;
1281
}
1282
 
1283
/* Marks invariant INVNO and all its dependencies for moving.  */
1284
 
1285
static void
1286
set_move_mark (unsigned invno, int gain)
1287
{
1288
  struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1289
  bitmap_iterator bi;
1290
 
1291
  /* Find the representative of the class of the equivalent invariants.  */
1292
  inv = VEC_index (invariant_p, invariants, inv->eqto);
1293
 
1294
  if (inv->move)
1295
    return;
1296
  inv->move = true;
1297
 
1298
  if (dump_file)
1299
    {
1300
      if (gain >= 0)
1301
        fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1302
                 invno, gain);
1303
      else
1304
        fprintf (dump_file, "Decided to move dependent invariant %d\n",
1305
                 invno);
1306
    };
1307
 
1308
  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1309
    {
1310
      set_move_mark (invno, -1);
1311
    }
1312
}
1313
 
1314
/* Determines which invariants to move.  */
1315
 
1316
static void
1317
find_invariants_to_move (bool speed)
1318
{
1319
  int gain;
1320
  unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1321
  struct invariant *inv = NULL;
1322
 
1323
  if (!VEC_length (invariant_p, invariants))
1324
    return;
1325
 
1326
  if (flag_ira_loop_pressure)
1327
    /* REGS_USED is actually never used when the flag is on.  */
1328
    regs_used = 0;
1329
  else
1330
    /* We do not really do a good job in estimating number of
1331
       registers used; we put some initial bound here to stand for
1332
       induction variables etc.  that we do not detect.  */
1333
    {
1334
      unsigned int n_regs = DF_REG_SIZE (df);
1335
 
1336
      regs_used = 2;
1337
 
1338
      for (i = 0; i < n_regs; i++)
1339
        {
1340
          if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1341
            {
1342
              /* This is a value that is used but not changed inside loop.  */
1343
              regs_used++;
1344
            }
1345
        }
1346
    }
1347
 
1348
  if (! flag_ira_loop_pressure)
1349
    new_regs[0] = regs_needed[0] = 0;
1350
  else
1351
    {
1352
      for (i = 0; (int) i < ira_reg_class_cover_size; i++)
1353
        new_regs[ira_reg_class_cover[i]] = 0;
1354
    }
1355
  while ((gain = best_gain_for_invariant (&inv, regs_needed,
1356
                                          new_regs, regs_used, speed)) > 0)
1357
    {
1358
      set_move_mark (inv->invno, gain);
1359
      if (! flag_ira_loop_pressure)
1360
        new_regs[0] += regs_needed[0];
1361
      else
1362
        {
1363
          for (i = 0; (int) i < ira_reg_class_cover_size; i++)
1364
            new_regs[ira_reg_class_cover[i]]
1365
              += regs_needed[ira_reg_class_cover[i]];
1366
        }
1367
    }
1368
}
1369
 
1370
/* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1371
   otherwise.  */
1372
 
1373
static bool
1374
move_invariant_reg (struct loop *loop, unsigned invno)
1375
{
1376
  struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1377
  struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1378
  unsigned i;
1379
  basic_block preheader = loop_preheader_edge (loop)->src;
1380
  rtx reg, set, dest, note;
1381
  struct use *use;
1382
  bitmap_iterator bi;
1383
  int regno;
1384
 
1385
  if (inv->reg)
1386
    return true;
1387
  if (!repr->move)
1388
    return false;
1389
  regno = -1;
1390
  /* If this is a representative of the class of equivalent invariants,
1391
     really move the invariant.  Otherwise just replace its use with
1392
     the register used for the representative.  */
1393
  if (inv == repr)
1394
    {
1395
      if (inv->depends_on)
1396
        {
1397
          EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1398
            {
1399
              if (!move_invariant_reg (loop, i))
1400
                goto fail;
1401
            }
1402
        }
1403
 
1404
      /* Move the set out of the loop.  If the set is always executed (we could
1405
         omit this condition if we know that the register is unused outside of the
1406
         loop, but it does not seem worth finding out) and it has no uses that
1407
         would not be dominated by it, we may just move it (TODO).  Otherwise we
1408
         need to create a temporary register.  */
1409
      set = single_set (inv->insn);
1410
      reg = dest = SET_DEST (set);
1411
      if (GET_CODE (reg) == SUBREG)
1412
        reg = SUBREG_REG (reg);
1413
      if (REG_P (reg))
1414
        regno = REGNO (reg);
1415
 
1416
      reg = gen_reg_rtx_and_attrs (dest);
1417
 
1418
      /* Try replacing the destination by a new pseudoregister.  */
1419
      if (!validate_change (inv->insn, &SET_DEST (set), reg, false))
1420
        goto fail;
1421
      df_insn_rescan (inv->insn);
1422
 
1423
      emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1424
      reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1425
 
1426
      /* If there is a REG_EQUAL note on the insn we just moved, and the
1427
         insn is in a basic block that is not always executed or the note
1428
         contains something for which we don't know the invariant status,
1429
         the note may no longer be valid after we move the insn.  Note that
1430
         uses in REG_EQUAL notes are taken into account in the computation
1431
         of invariants, so it is safe to retain the note even if it contains
1432
         register references for which we know the invariant status.  */
1433
      if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1434
          && (!inv->always_executed
1435
              || !check_maybe_invariant (XEXP (note, 0))))
1436
        remove_note (inv->insn, note);
1437
    }
1438
  else
1439
    {
1440
      if (!move_invariant_reg (loop, repr->invno))
1441
        goto fail;
1442
      reg = repr->reg;
1443
      regno = repr->orig_regno;
1444
      set = single_set (inv->insn);
1445
      emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1446
      delete_insn (inv->insn);
1447
    }
1448
 
1449
 
1450
  inv->reg = reg;
1451
  inv->orig_regno = regno;
1452
 
1453
  /* Replace the uses we know to be dominated.  It saves work for copy
1454
     propagation, and also it is necessary so that dependent invariants
1455
     are computed right.  */
1456
  if (inv->def)
1457
    {
1458
      for (use = inv->def->uses; use; use = use->next)
1459
        {
1460
          *use->pos = reg;
1461
          df_insn_rescan (use->insn);
1462
        }
1463
    }
1464
 
1465
  return true;
1466
 
1467
fail:
1468
  /* If we failed, clear move flag, so that we do not try to move inv
1469
     again.  */
1470
  if (dump_file)
1471
    fprintf (dump_file, "Failed to move invariant %d\n", invno);
1472
  inv->move = false;
1473
  inv->reg = NULL_RTX;
1474
  inv->orig_regno = -1;
1475
 
1476
  return false;
1477
}
1478
 
1479
/* Move selected invariant out of the LOOP.  Newly created regs are marked
1480
   in TEMPORARY_REGS.  */
1481
 
1482
static void
1483
move_invariants (struct loop *loop)
1484
{
1485
  struct invariant *inv;
1486
  unsigned i;
1487
 
1488
  for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1489
    move_invariant_reg (loop, i);
1490
  if (flag_ira_loop_pressure && resize_reg_info ())
1491
    {
1492
      for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1493
        if (inv->reg != NULL_RTX)
1494
          {
1495
            if (inv->orig_regno >= 0)
1496
              setup_reg_classes (REGNO (inv->reg),
1497
                                 reg_preferred_class (inv->orig_regno),
1498
                                 reg_alternate_class (inv->orig_regno),
1499
                                 reg_cover_class (inv->orig_regno));
1500
            else
1501
              setup_reg_classes (REGNO (inv->reg),
1502
                                 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1503
          }
1504
    }
1505
}
1506
 
1507
/* Initializes invariant motion data.  */
1508
 
1509
static void
1510
init_inv_motion_data (void)
1511
{
1512
  actual_stamp = 1;
1513
 
1514
  invariants = VEC_alloc (invariant_p, heap, 100);
1515
}
1516
 
1517
/* Frees the data allocated by invariant motion.  */
1518
 
1519
static void
1520
free_inv_motion_data (void)
1521
{
1522
  unsigned i;
1523
  struct def *def;
1524
  struct invariant *inv;
1525
 
1526
  check_invariant_table_size ();
1527
  for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1528
    {
1529
      inv = invariant_table[i];
1530
      if (inv)
1531
        {
1532
          def = inv->def;
1533
          gcc_assert (def != NULL);
1534
 
1535
          free_use_list (def->uses);
1536
          free (def);
1537
          invariant_table[i] = NULL;
1538
        }
1539
    }
1540
 
1541
  for (i = 0; VEC_iterate (invariant_p, invariants, i, inv); i++)
1542
    {
1543
      BITMAP_FREE (inv->depends_on);
1544
      free (inv);
1545
    }
1546
  VEC_free (invariant_p, heap, invariants);
1547
}
1548
 
1549
/* Move the invariants out of the LOOP.  */
1550
 
1551
static void
1552
move_single_loop_invariants (struct loop *loop)
1553
{
1554
  init_inv_motion_data ();
1555
 
1556
  find_invariants (loop);
1557
  find_invariants_to_move (optimize_loop_for_speed_p (loop));
1558
  move_invariants (loop);
1559
 
1560
  free_inv_motion_data ();
1561
}
1562
 
1563
/* Releases the auxiliary data for LOOP.  */
1564
 
1565
static void
1566
free_loop_data (struct loop *loop)
1567
{
1568
  struct loop_data *data = LOOP_DATA (loop);
1569
  if (!data)
1570
    return;
1571
 
1572
  bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1573
  bitmap_clear (&LOOP_DATA (loop)->regs_live);
1574
  free (data);
1575
  loop->aux = NULL;
1576
}
1577
 
1578
 
1579
 
1580
/* Registers currently living.  */
1581
static bitmap_head curr_regs_live;
1582
 
1583
/* Current reg pressure for each cover class.  */
1584
static int curr_reg_pressure[N_REG_CLASSES];
1585
 
1586
/* Record all regs that are set in any one insn.  Communication from
1587
   mark_reg_{store,clobber} and global_conflicts.  Asm can refer to
1588
   all hard-registers.  */
1589
static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1590
                     ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1591
/* Number of regs stored in the previous array.  */
1592
static int n_regs_set;
1593
 
1594
/* Return cover class and number of needed hard registers (through
1595
   *NREGS) of register REGNO.  */
1596
static enum reg_class
1597
get_regno_cover_class (int regno, int *nregs)
1598
{
1599
  if (regno >= FIRST_PSEUDO_REGISTER)
1600
    {
1601
      enum reg_class cover_class = reg_cover_class (regno);
1602
 
1603
      *nregs = ira_reg_class_nregs[cover_class][PSEUDO_REGNO_MODE (regno)];
1604
      return cover_class;
1605
    }
1606
  else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1607
           && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1608
    {
1609
      *nregs = 1;
1610
      return ira_class_translate[REGNO_REG_CLASS (regno)];
1611
    }
1612
  else
1613
    {
1614
      *nregs = 0;
1615
      return NO_REGS;
1616
    }
1617
}
1618
 
1619
/* Increase (if INCR_P) or decrease current register pressure for
1620
   register REGNO.  */
1621
static void
1622
change_pressure (int regno, bool incr_p)
1623
{
1624
  int nregs;
1625
  enum reg_class cover_class;
1626
 
1627
  cover_class = get_regno_cover_class (regno, &nregs);
1628
  if (! incr_p)
1629
    curr_reg_pressure[cover_class] -= nregs;
1630
  else
1631
    {
1632
      curr_reg_pressure[cover_class] += nregs;
1633
      if (LOOP_DATA (curr_loop)->max_reg_pressure[cover_class]
1634
          < curr_reg_pressure[cover_class])
1635
        LOOP_DATA (curr_loop)->max_reg_pressure[cover_class]
1636
          = curr_reg_pressure[cover_class];
1637
    }
1638
}
1639
 
1640
/* Mark REGNO birth.  */
1641
static void
1642
mark_regno_live (int regno)
1643
{
1644
  struct loop *loop;
1645
 
1646
  for (loop = curr_loop;
1647
       loop != current_loops->tree_root;
1648
       loop = loop_outer (loop))
1649
    bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
1650
  if (bitmap_bit_p (&curr_regs_live, regno))
1651
    return;
1652
  bitmap_set_bit (&curr_regs_live, regno);
1653
  change_pressure (regno, true);
1654
}
1655
 
1656
/* Mark REGNO death.  */
1657
static void
1658
mark_regno_death (int regno)
1659
{
1660
  if (! bitmap_bit_p (&curr_regs_live, regno))
1661
    return;
1662
  bitmap_clear_bit (&curr_regs_live, regno);
1663
  change_pressure (regno, false);
1664
}
1665
 
1666
/* Mark setting register REG.  */
1667
static void
1668
mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1669
                void *data ATTRIBUTE_UNUSED)
1670
{
1671
  int regno;
1672
 
1673
  if (GET_CODE (reg) == SUBREG)
1674
    reg = SUBREG_REG (reg);
1675
 
1676
  if (! REG_P (reg))
1677
    return;
1678
 
1679
  regs_set[n_regs_set++] = reg;
1680
 
1681
  regno = REGNO (reg);
1682
 
1683
  if (regno >= FIRST_PSEUDO_REGISTER)
1684
    mark_regno_live (regno);
1685
  else
1686
    {
1687
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1688
 
1689
      while (regno < last)
1690
        {
1691
          mark_regno_live (regno);
1692
          regno++;
1693
        }
1694
    }
1695
}
1696
 
1697
/* Mark clobbering register REG.  */
1698
static void
1699
mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1700
{
1701
  if (GET_CODE (setter) == CLOBBER)
1702
    mark_reg_store (reg, setter, data);
1703
}
1704
 
1705
/* Mark register REG death.  */
1706
static void
1707
mark_reg_death (rtx reg)
1708
{
1709
  int regno = REGNO (reg);
1710
 
1711
  if (regno >= FIRST_PSEUDO_REGISTER)
1712
    mark_regno_death (regno);
1713
  else
1714
    {
1715
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1716
 
1717
      while (regno < last)
1718
        {
1719
          mark_regno_death (regno);
1720
          regno++;
1721
        }
1722
    }
1723
}
1724
 
1725
/* Mark occurrence of registers in X for the current loop.  */
1726
static void
1727
mark_ref_regs (rtx x)
1728
{
1729
  RTX_CODE code;
1730
  int i;
1731
  const char *fmt;
1732
 
1733
  if (!x)
1734
    return;
1735
 
1736
  code = GET_CODE (x);
1737
  if (code == REG)
1738
    {
1739
      struct loop *loop;
1740
 
1741
      for (loop = curr_loop;
1742
           loop != current_loops->tree_root;
1743
           loop = loop_outer (loop))
1744
        bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
1745
      return;
1746
    }
1747
 
1748
  fmt = GET_RTX_FORMAT (code);
1749
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1750
    if (fmt[i] == 'e')
1751
      mark_ref_regs (XEXP (x, i));
1752
    else if (fmt[i] == 'E')
1753
      {
1754
        int j;
1755
 
1756
        for (j = 0; j < XVECLEN (x, i); j++)
1757
          mark_ref_regs (XVECEXP (x, i, j));
1758
      }
1759
}
1760
 
1761
/* Calculate register pressure in the loops.  */
1762
static void
1763
calculate_loop_reg_pressure (void)
1764
{
1765
  int i;
1766
  unsigned int j;
1767
  bitmap_iterator bi;
1768
  basic_block bb;
1769
  rtx insn, link;
1770
  struct loop *loop, *parent;
1771
  loop_iterator li;
1772
 
1773
  FOR_EACH_LOOP (li, loop, 0)
1774
    if (loop->aux == NULL)
1775
      {
1776
        loop->aux = xcalloc (1, sizeof (struct loop_data));
1777
        bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1778
        bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1779
      }
1780
  ira_setup_eliminable_regset ();
1781
  bitmap_initialize (&curr_regs_live, &reg_obstack);
1782
  FOR_EACH_BB (bb)
1783
    {
1784
      curr_loop = bb->loop_father;
1785
      if (curr_loop == current_loops->tree_root)
1786
        continue;
1787
 
1788
      for (loop = curr_loop;
1789
           loop != current_loops->tree_root;
1790
           loop = loop_outer (loop))
1791
        bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1792
 
1793
      bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1794
      for (i = 0; i < ira_reg_class_cover_size; i++)
1795
        curr_reg_pressure[ira_reg_class_cover[i]] = 0;
1796
      EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1797
        change_pressure (j, true);
1798
 
1799
      FOR_BB_INSNS (bb, insn)
1800
        {
1801
          if (! NONDEBUG_INSN_P (insn))
1802
            continue;
1803
 
1804
          mark_ref_regs (PATTERN (insn));
1805
          n_regs_set = 0;
1806
          note_stores (PATTERN (insn), mark_reg_clobber, NULL);
1807
 
1808
          /* Mark any registers dead after INSN as dead now.  */
1809
 
1810
          for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1811
            if (REG_NOTE_KIND (link) == REG_DEAD)
1812
              mark_reg_death (XEXP (link, 0));
1813
 
1814
          /* Mark any registers set in INSN as live,
1815
             and mark them as conflicting with all other live regs.
1816
             Clobbers are processed again, so they conflict with
1817
             the registers that are set.  */
1818
 
1819
          note_stores (PATTERN (insn), mark_reg_store, NULL);
1820
 
1821
#ifdef AUTO_INC_DEC
1822
          for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1823
            if (REG_NOTE_KIND (link) == REG_INC)
1824
              mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1825
#endif
1826
          while (n_regs_set-- > 0)
1827
            {
1828
              rtx note = find_regno_note (insn, REG_UNUSED,
1829
                                          REGNO (regs_set[n_regs_set]));
1830
              if (! note)
1831
                continue;
1832
 
1833
              mark_reg_death (XEXP (note, 0));
1834
            }
1835
        }
1836
    }
1837
  bitmap_clear (&curr_regs_live);
1838
  if (flag_ira_region == IRA_REGION_MIXED
1839
      || flag_ira_region == IRA_REGION_ALL)
1840
    FOR_EACH_LOOP (li, loop, 0)
1841
      {
1842
        EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1843
          if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1844
            {
1845
              enum reg_class cover_class;
1846
              int nregs;
1847
 
1848
              cover_class = get_regno_cover_class (j, &nregs);
1849
              LOOP_DATA (loop)->max_reg_pressure[cover_class] -= nregs;
1850
            }
1851
      }
1852
  if (dump_file == NULL)
1853
    return;
1854
  FOR_EACH_LOOP (li, loop, 0)
1855
    {
1856
      parent = loop_outer (loop);
1857
      fprintf (dump_file, "\n  Loop %d (parent %d, header bb%d, depth %d)\n",
1858
               loop->num, (parent == NULL ? -1 : parent->num),
1859
               loop->header->index, loop_depth (loop));
1860
      fprintf (dump_file, "\n    ref. regnos:");
1861
      EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
1862
        fprintf (dump_file, " %d", j);
1863
      fprintf (dump_file, "\n    live regnos:");
1864
      EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1865
        fprintf (dump_file, " %d", j);
1866
      fprintf (dump_file, "\n    Pressure:");
1867
      for (i = 0; (int) i < ira_reg_class_cover_size; i++)
1868
        {
1869
          enum reg_class cover_class;
1870
 
1871
          cover_class = ira_reg_class_cover[i];
1872
          if (LOOP_DATA (loop)->max_reg_pressure[cover_class] == 0)
1873
            continue;
1874
          fprintf (dump_file, " %s=%d", reg_class_names[cover_class],
1875
                   LOOP_DATA (loop)->max_reg_pressure[cover_class]);
1876
        }
1877
      fprintf (dump_file, "\n");
1878
    }
1879
}
1880
 
1881
 
1882
 
1883
/* Move the invariants out of the loops.  */
1884
 
1885
void
1886
move_loop_invariants (void)
1887
{
1888
  struct loop *loop;
1889
  loop_iterator li;
1890
 
1891
  if (flag_ira_loop_pressure)
1892
    {
1893
      df_analyze ();
1894
      ira_set_pseudo_classes (dump_file);
1895
      calculate_loop_reg_pressure ();
1896
    }
1897
  df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1898
  /* Process the loops, innermost first.  */
1899
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1900
    {
1901
      curr_loop = loop;
1902
      /* move_single_loop_invariants for very large loops
1903
         is time consuming and might need a lot of memory.  */
1904
      if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
1905
        move_single_loop_invariants (loop);
1906
    }
1907
 
1908
  FOR_EACH_LOOP (li, loop, 0)
1909
    {
1910
      free_loop_data (loop);
1911
    }
1912
 
1913
  if (flag_ira_loop_pressure)
1914
    /* There is no sense to keep this info because it was most
1915
       probably outdated by subsequent passes.  */
1916
    free_reg_info ();
1917
  free (invariant_table);
1918
  invariant_table = NULL;
1919
  invariant_table_size = 0;
1920
 
1921
#ifdef ENABLE_CHECKING
1922
  verify_flow_info ();
1923
#endif
1924
}

powered by: WebSVN 2.1.0

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