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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [loop-invariant.c] - Blame information for rev 778

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

Line No. Rev Author Line
1 684 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 pressure 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_EACH_VEC_ELT (invariant_p, invariants, i, inv)
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 = set_rtx_cost (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 = set_src_cost (SET_SRC (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 pressure class and number of hard registers (through *NREGS)
1016
   for destination of INSN. */
1017
static enum reg_class
1018
get_pressure_class_and_nregs (rtx insn, int *nregs)
1019
{
1020
  rtx reg;
1021
  enum reg_class pressure_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
      pressure_class = NO_REGS;
1033
    }
1034
  else
1035
    {
1036
      if (! REG_P (reg))
1037
        reg = NULL_RTX;
1038
      if (reg == NULL_RTX)
1039
        pressure_class = GENERAL_REGS;
1040
      else
1041
        {
1042
          pressure_class = reg_allocno_class (REGNO (reg));
1043
          pressure_class = ira_pressure_class_translate[pressure_class];
1044
        }
1045
      *nregs
1046
        = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
1047
    }
1048
  return pressure_class;
1049
}
1050
 
1051
/* Calculates cost and number of registers needed for moving invariant INV
1052
   out of the loop and stores them to *COST and *REGS_NEEDED.  */
1053
 
1054
static void
1055
get_inv_cost (struct invariant *inv, int *comp_cost, unsigned *regs_needed)
1056
{
1057
  int i, acomp_cost;
1058
  unsigned aregs_needed[N_REG_CLASSES];
1059
  unsigned depno;
1060
  struct invariant *dep;
1061
  bitmap_iterator bi;
1062
 
1063
  /* Find the representative of the class of the equivalent invariants.  */
1064
  inv = VEC_index (invariant_p, invariants, inv->eqto);
1065
 
1066
  *comp_cost = 0;
1067
  if (! flag_ira_loop_pressure)
1068
    regs_needed[0] = 0;
1069
  else
1070
    {
1071
      for (i = 0; i < ira_pressure_classes_num; i++)
1072
        regs_needed[ira_pressure_classes[i]] = 0;
1073
    }
1074
 
1075
  if (inv->move
1076
      || inv->stamp == actual_stamp)
1077
    return;
1078
  inv->stamp = actual_stamp;
1079
 
1080
  if (! flag_ira_loop_pressure)
1081
    regs_needed[0]++;
1082
  else
1083
    {
1084
      int nregs;
1085
      enum reg_class pressure_class;
1086
 
1087
      pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1088
      regs_needed[pressure_class] += nregs;
1089
    }
1090
 
1091
  if (!inv->cheap_address
1092
      || inv->def->n_addr_uses < inv->def->n_uses)
1093
    (*comp_cost) += inv->cost;
1094
 
1095
#ifdef STACK_REGS
1096
  {
1097
    /* Hoisting constant pool constants into stack regs may cost more than
1098
       just single register.  On x87, the balance is affected both by the
1099
       small number of FP registers, and by its register stack organization,
1100
       that forces us to add compensation code in and around the loop to
1101
       shuffle the operands to the top of stack before use, and pop them
1102
       from the stack after the loop finishes.
1103
 
1104
       To model this effect, we increase the number of registers needed for
1105
       stack registers by two: one register push, and one register pop.
1106
       This usually has the effect that FP constant loads from the constant
1107
       pool are not moved out of the loop.
1108
 
1109
       Note that this also means that dependent invariants can not be moved.
1110
       However, the primary purpose of this pass is to move loop invariant
1111
       address arithmetic out of loops, and address arithmetic that depends
1112
       on floating point constants is unlikely to ever occur.  */
1113
    rtx set = single_set (inv->insn);
1114
    if (set
1115
        && IS_STACK_MODE (GET_MODE (SET_SRC (set)))
1116
        && constant_pool_constant_p (SET_SRC (set)))
1117
      {
1118
        if (flag_ira_loop_pressure)
1119
          regs_needed[ira_stack_reg_pressure_class] += 2;
1120
        else
1121
          regs_needed[0] += 2;
1122
      }
1123
  }
1124
#endif
1125
 
1126
  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, depno, bi)
1127
    {
1128
      bool check_p;
1129
 
1130
      dep = VEC_index (invariant_p, invariants, depno);
1131
 
1132
      get_inv_cost (dep, &acomp_cost, aregs_needed);
1133
 
1134
      if (! flag_ira_loop_pressure)
1135
        check_p = aregs_needed[0] != 0;
1136
      else
1137
        {
1138
          for (i = 0; i < ira_pressure_classes_num; i++)
1139
            if (aregs_needed[ira_pressure_classes[i]] != 0)
1140
              break;
1141
          check_p = i < ira_pressure_classes_num;
1142
        }
1143
      if (check_p
1144
          /* We need to check always_executed, since if the original value of
1145
             the invariant may be preserved, we may need to keep it in a
1146
             separate register.  TODO check whether the register has an
1147
             use outside of the loop.  */
1148
          && dep->always_executed
1149
          && !dep->def->uses->next)
1150
        {
1151
          /* If this is a single use, after moving the dependency we will not
1152
             need a new register.  */
1153
          if (! flag_ira_loop_pressure)
1154
            aregs_needed[0]--;
1155
          else
1156
            {
1157
              int nregs;
1158
              enum reg_class pressure_class;
1159
 
1160
              pressure_class = get_pressure_class_and_nregs (inv->insn, &nregs);
1161
              aregs_needed[pressure_class] -= nregs;
1162
            }
1163
        }
1164
 
1165
      if (! flag_ira_loop_pressure)
1166
        regs_needed[0] += aregs_needed[0];
1167
      else
1168
        {
1169
          for (i = 0; i < ira_pressure_classes_num; i++)
1170
            regs_needed[ira_pressure_classes[i]]
1171
              += aregs_needed[ira_pressure_classes[i]];
1172
        }
1173
      (*comp_cost) += acomp_cost;
1174
    }
1175
}
1176
 
1177
/* Calculates gain for eliminating invariant INV.  REGS_USED is the number
1178
   of registers used in the loop, NEW_REGS is the number of new variables
1179
   already added due to the invariant motion.  The number of registers needed
1180
   for it is stored in *REGS_NEEDED.  SPEED and CALL_P are flags passed
1181
   through to estimate_reg_pressure_cost. */
1182
 
1183
static int
1184
gain_for_invariant (struct invariant *inv, unsigned *regs_needed,
1185
                    unsigned *new_regs, unsigned regs_used,
1186
                    bool speed, bool call_p)
1187
{
1188
  int comp_cost, size_cost;
1189
 
1190
  actual_stamp++;
1191
 
1192
  get_inv_cost (inv, &comp_cost, regs_needed);
1193
 
1194
  if (! flag_ira_loop_pressure)
1195
    {
1196
      size_cost = (estimate_reg_pressure_cost (new_regs[0] + regs_needed[0],
1197
                                               regs_used, speed, call_p)
1198
                   - estimate_reg_pressure_cost (new_regs[0],
1199
                                                 regs_used, speed, call_p));
1200
    }
1201
  else
1202
    {
1203
      int i;
1204
      enum reg_class pressure_class;
1205
 
1206
      for (i = 0; i < ira_pressure_classes_num; i++)
1207
        {
1208
          pressure_class = ira_pressure_classes[i];
1209
          if ((int) new_regs[pressure_class]
1210
              + (int) regs_needed[pressure_class]
1211
              + LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1212
              + IRA_LOOP_RESERVED_REGS
1213
              > ira_available_class_regs[pressure_class])
1214
            break;
1215
        }
1216
      if (i < ira_pressure_classes_num)
1217
        /* There will be register pressure excess and we want not to
1218
           make this loop invariant motion.  All loop invariants with
1219
           non-positive gains will be rejected in function
1220
           find_invariants_to_move.  Therefore we return the negative
1221
           number here.
1222
 
1223
           One could think that this rejects also expensive loop
1224
           invariant motions and this will hurt code performance.
1225
           However numerous experiments with different heuristics
1226
           taking invariant cost into account did not confirm this
1227
           assumption.  There are possible explanations for this
1228
           result:
1229
           o probably all expensive invariants were already moved out
1230
             of the loop by PRE and gimple invariant motion pass.
1231
           o expensive invariant execution will be hidden by insn
1232
             scheduling or OOO processor hardware because usually such
1233
             invariants have a lot of freedom to be executed
1234
             out-of-order.
1235
           Another reason for ignoring invariant cost vs spilling cost
1236
           heuristics is also in difficulties to evaluate accurately
1237
           spill cost at this stage.  */
1238
        return -1;
1239
      else
1240
        size_cost = 0;
1241
    }
1242
 
1243
  return comp_cost - size_cost;
1244
}
1245
 
1246
/* Finds invariant with best gain for moving.  Returns the gain, stores
1247
   the invariant in *BEST and number of registers needed for it to
1248
   *REGS_NEEDED.  REGS_USED is the number of registers used in the loop.
1249
   NEW_REGS is the number of new variables already added due to invariant
1250
   motion.  */
1251
 
1252
static int
1253
best_gain_for_invariant (struct invariant **best, unsigned *regs_needed,
1254
                         unsigned *new_regs, unsigned regs_used,
1255
                         bool speed, bool call_p)
1256
{
1257
  struct invariant *inv;
1258
  int i, gain = 0, again;
1259
  unsigned aregs_needed[N_REG_CLASSES], invno;
1260
 
1261
  FOR_EACH_VEC_ELT (invariant_p, invariants, invno, inv)
1262
    {
1263
      if (inv->move)
1264
        continue;
1265
 
1266
      /* Only consider the "representatives" of equivalent invariants.  */
1267
      if (inv->eqto != inv->invno)
1268
        continue;
1269
 
1270
      again = gain_for_invariant (inv, aregs_needed, new_regs, regs_used,
1271
                                  speed, call_p);
1272
      if (again > gain)
1273
        {
1274
          gain = again;
1275
          *best = inv;
1276
          if (! flag_ira_loop_pressure)
1277
            regs_needed[0] = aregs_needed[0];
1278
          else
1279
            {
1280
              for (i = 0; i < ira_pressure_classes_num; i++)
1281
                regs_needed[ira_pressure_classes[i]]
1282
                  = aregs_needed[ira_pressure_classes[i]];
1283
            }
1284
        }
1285
    }
1286
 
1287
  return gain;
1288
}
1289
 
1290
/* Marks invariant INVNO and all its dependencies for moving.  */
1291
 
1292
static void
1293
set_move_mark (unsigned invno, int gain)
1294
{
1295
  struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1296
  bitmap_iterator bi;
1297
 
1298
  /* Find the representative of the class of the equivalent invariants.  */
1299
  inv = VEC_index (invariant_p, invariants, inv->eqto);
1300
 
1301
  if (inv->move)
1302
    return;
1303
  inv->move = true;
1304
 
1305
  if (dump_file)
1306
    {
1307
      if (gain >= 0)
1308
        fprintf (dump_file, "Decided to move invariant %d -- gain %d\n",
1309
                 invno, gain);
1310
      else
1311
        fprintf (dump_file, "Decided to move dependent invariant %d\n",
1312
                 invno);
1313
    };
1314
 
1315
  EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, invno, bi)
1316
    {
1317
      set_move_mark (invno, -1);
1318
    }
1319
}
1320
 
1321
/* Determines which invariants to move.  */
1322
 
1323
static void
1324
find_invariants_to_move (bool speed, bool call_p)
1325
{
1326
  int gain;
1327
  unsigned i, regs_used, regs_needed[N_REG_CLASSES], new_regs[N_REG_CLASSES];
1328
  struct invariant *inv = NULL;
1329
 
1330
  if (!VEC_length (invariant_p, invariants))
1331
    return;
1332
 
1333
  if (flag_ira_loop_pressure)
1334
    /* REGS_USED is actually never used when the flag is on.  */
1335
    regs_used = 0;
1336
  else
1337
    /* We do not really do a good job in estimating number of
1338
       registers used; we put some initial bound here to stand for
1339
       induction variables etc.  that we do not detect.  */
1340
    {
1341
      unsigned int n_regs = DF_REG_SIZE (df);
1342
 
1343
      regs_used = 2;
1344
 
1345
      for (i = 0; i < n_regs; i++)
1346
        {
1347
          if (!DF_REGNO_FIRST_DEF (i) && DF_REGNO_LAST_USE (i))
1348
            {
1349
              /* This is a value that is used but not changed inside loop.  */
1350
              regs_used++;
1351
            }
1352
        }
1353
    }
1354
 
1355
  if (! flag_ira_loop_pressure)
1356
    new_regs[0] = regs_needed[0] = 0;
1357
  else
1358
    {
1359
      for (i = 0; (int) i < ira_pressure_classes_num; i++)
1360
        new_regs[ira_pressure_classes[i]] = 0;
1361
    }
1362
  while ((gain = best_gain_for_invariant (&inv, regs_needed,
1363
                                          new_regs, regs_used,
1364
                                          speed, call_p)) > 0)
1365
    {
1366
      set_move_mark (inv->invno, gain);
1367
      if (! flag_ira_loop_pressure)
1368
        new_regs[0] += regs_needed[0];
1369
      else
1370
        {
1371
          for (i = 0; (int) i < ira_pressure_classes_num; i++)
1372
            new_regs[ira_pressure_classes[i]]
1373
              += regs_needed[ira_pressure_classes[i]];
1374
        }
1375
    }
1376
}
1377
 
1378
/* Replace the uses, reached by the definition of invariant INV, by REG.
1379
 
1380
   IN_GROUP is nonzero if this is part of a group of changes that must be
1381
   performed as a group.  In that case, the changes will be stored.  The
1382
   function `apply_change_group' will validate and apply the changes.  */
1383
 
1384
static int
1385
replace_uses (struct invariant *inv, rtx reg, bool in_group)
1386
{
1387
  /* Replace the uses we know to be dominated.  It saves work for copy
1388
     propagation, and also it is necessary so that dependent invariants
1389
     are computed right.  */
1390
  if (inv->def)
1391
    {
1392
      struct use *use;
1393
      for (use = inv->def->uses; use; use = use->next)
1394
        validate_change (use->insn, use->pos, reg, true);
1395
 
1396
      /* If we aren't part of a larger group, apply the changes now.  */
1397
      if (!in_group)
1398
        return apply_change_group ();
1399
    }
1400
 
1401
  return 1;
1402
}
1403
 
1404
/* Move invariant INVNO out of the LOOP.  Returns true if this succeeds, false
1405
   otherwise.  */
1406
 
1407
static bool
1408
move_invariant_reg (struct loop *loop, unsigned invno)
1409
{
1410
  struct invariant *inv = VEC_index (invariant_p, invariants, invno);
1411
  struct invariant *repr = VEC_index (invariant_p, invariants, inv->eqto);
1412
  unsigned i;
1413
  basic_block preheader = loop_preheader_edge (loop)->src;
1414
  rtx reg, set, dest, note;
1415
  bitmap_iterator bi;
1416
  int regno = -1;
1417
 
1418
  if (inv->reg)
1419
    return true;
1420
  if (!repr->move)
1421
    return false;
1422
 
1423
  /* If this is a representative of the class of equivalent invariants,
1424
     really move the invariant.  Otherwise just replace its use with
1425
     the register used for the representative.  */
1426
  if (inv == repr)
1427
    {
1428
      if (inv->depends_on)
1429
        {
1430
          EXECUTE_IF_SET_IN_BITMAP (inv->depends_on, 0, i, bi)
1431
            {
1432
              if (!move_invariant_reg (loop, i))
1433
                goto fail;
1434
            }
1435
        }
1436
 
1437
      /* Move the set out of the loop.  If the set is always executed (we could
1438
         omit this condition if we know that the register is unused outside of
1439
         the loop, but it does not seem worth finding out) and it has no uses
1440
         that would not be dominated by it, we may just move it (TODO).
1441
         Otherwise we need to create a temporary register.  */
1442
      set = single_set (inv->insn);
1443
      reg = dest = SET_DEST (set);
1444
      if (GET_CODE (reg) == SUBREG)
1445
        reg = SUBREG_REG (reg);
1446
      if (REG_P (reg))
1447
        regno = REGNO (reg);
1448
 
1449
      reg = gen_reg_rtx_and_attrs (dest);
1450
 
1451
      /* Try replacing the destination by a new pseudoregister.  */
1452
      validate_change (inv->insn, &SET_DEST (set), reg, true);
1453
 
1454
      /* As well as all the dominated uses.  */
1455
      replace_uses (inv, reg, true);
1456
 
1457
      /* And validate all the changes.  */
1458
      if (!apply_change_group ())
1459
        goto fail;
1460
 
1461
      emit_insn_after (gen_move_insn (dest, reg), inv->insn);
1462
      reorder_insns (inv->insn, inv->insn, BB_END (preheader));
1463
 
1464
      /* If there is a REG_EQUAL note on the insn we just moved, and the
1465
         insn is in a basic block that is not always executed or the note
1466
         contains something for which we don't know the invariant status,
1467
         the note may no longer be valid after we move the insn.  Note that
1468
         uses in REG_EQUAL notes are taken into account in the computation
1469
         of invariants, so it is safe to retain the note even if it contains
1470
         register references for which we know the invariant status.  */
1471
      if ((note = find_reg_note (inv->insn, REG_EQUAL, NULL_RTX))
1472
          && (!inv->always_executed
1473
              || !check_maybe_invariant (XEXP (note, 0))))
1474
        remove_note (inv->insn, note);
1475
    }
1476
  else
1477
    {
1478
      if (!move_invariant_reg (loop, repr->invno))
1479
        goto fail;
1480
      reg = repr->reg;
1481
      regno = repr->orig_regno;
1482
      if (!replace_uses (inv, reg, false))
1483
        goto fail;
1484
      set = single_set (inv->insn);
1485
      emit_insn_after (gen_move_insn (SET_DEST (set), reg), inv->insn);
1486
      delete_insn (inv->insn);
1487
    }
1488
 
1489
  inv->reg = reg;
1490
  inv->orig_regno = regno;
1491
 
1492
  return true;
1493
 
1494
fail:
1495
  /* If we failed, clear move flag, so that we do not try to move inv
1496
     again.  */
1497
  if (dump_file)
1498
    fprintf (dump_file, "Failed to move invariant %d\n", invno);
1499
  inv->move = false;
1500
  inv->reg = NULL_RTX;
1501
  inv->orig_regno = -1;
1502
 
1503
  return false;
1504
}
1505
 
1506
/* Move selected invariant out of the LOOP.  Newly created regs are marked
1507
   in TEMPORARY_REGS.  */
1508
 
1509
static void
1510
move_invariants (struct loop *loop)
1511
{
1512
  struct invariant *inv;
1513
  unsigned i;
1514
 
1515
  FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv)
1516
    move_invariant_reg (loop, i);
1517
  if (flag_ira_loop_pressure && resize_reg_info ())
1518
    {
1519
      FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv)
1520
        if (inv->reg != NULL_RTX)
1521
          {
1522
            if (inv->orig_regno >= 0)
1523
              setup_reg_classes (REGNO (inv->reg),
1524
                                 reg_preferred_class (inv->orig_regno),
1525
                                 reg_alternate_class (inv->orig_regno),
1526
                                 reg_allocno_class (inv->orig_regno));
1527
            else
1528
              setup_reg_classes (REGNO (inv->reg),
1529
                                 GENERAL_REGS, NO_REGS, GENERAL_REGS);
1530
          }
1531
    }
1532
}
1533
 
1534
/* Initializes invariant motion data.  */
1535
 
1536
static void
1537
init_inv_motion_data (void)
1538
{
1539
  actual_stamp = 1;
1540
 
1541
  invariants = VEC_alloc (invariant_p, heap, 100);
1542
}
1543
 
1544
/* Frees the data allocated by invariant motion.  */
1545
 
1546
static void
1547
free_inv_motion_data (void)
1548
{
1549
  unsigned i;
1550
  struct def *def;
1551
  struct invariant *inv;
1552
 
1553
  check_invariant_table_size ();
1554
  for (i = 0; i < DF_DEFS_TABLE_SIZE (); i++)
1555
    {
1556
      inv = invariant_table[i];
1557
      if (inv)
1558
        {
1559
          def = inv->def;
1560
          gcc_assert (def != NULL);
1561
 
1562
          free_use_list (def->uses);
1563
          free (def);
1564
          invariant_table[i] = NULL;
1565
        }
1566
    }
1567
 
1568
  FOR_EACH_VEC_ELT (invariant_p, invariants, i, inv)
1569
    {
1570
      BITMAP_FREE (inv->depends_on);
1571
      free (inv);
1572
    }
1573
  VEC_free (invariant_p, heap, invariants);
1574
}
1575
 
1576
/* Move the invariants out of the LOOP.  */
1577
 
1578
static void
1579
move_single_loop_invariants (struct loop *loop)
1580
{
1581
  init_inv_motion_data ();
1582
 
1583
  find_invariants (loop);
1584
  find_invariants_to_move (optimize_loop_for_speed_p (loop),
1585
                           LOOP_DATA (loop)->has_call);
1586
  move_invariants (loop);
1587
 
1588
  free_inv_motion_data ();
1589
}
1590
 
1591
/* Releases the auxiliary data for LOOP.  */
1592
 
1593
static void
1594
free_loop_data (struct loop *loop)
1595
{
1596
  struct loop_data *data = LOOP_DATA (loop);
1597
  if (!data)
1598
    return;
1599
 
1600
  bitmap_clear (&LOOP_DATA (loop)->regs_ref);
1601
  bitmap_clear (&LOOP_DATA (loop)->regs_live);
1602
  free (data);
1603
  loop->aux = NULL;
1604
}
1605
 
1606
 
1607
 
1608
/* Registers currently living.  */
1609
static bitmap_head curr_regs_live;
1610
 
1611
/* Current reg pressure for each pressure class.  */
1612
static int curr_reg_pressure[N_REG_CLASSES];
1613
 
1614
/* Record all regs that are set in any one insn.  Communication from
1615
   mark_reg_{store,clobber} and global_conflicts.  Asm can refer to
1616
   all hard-registers.  */
1617
static rtx regs_set[(FIRST_PSEUDO_REGISTER > MAX_RECOG_OPERANDS
1618
                     ? FIRST_PSEUDO_REGISTER : MAX_RECOG_OPERANDS) * 2];
1619
/* Number of regs stored in the previous array.  */
1620
static int n_regs_set;
1621
 
1622
/* Return pressure class and number of needed hard registers (through
1623
   *NREGS) of register REGNO.  */
1624
static enum reg_class
1625
get_regno_pressure_class (int regno, int *nregs)
1626
{
1627
  if (regno >= FIRST_PSEUDO_REGISTER)
1628
    {
1629
      enum reg_class pressure_class;
1630
 
1631
      pressure_class = reg_allocno_class (regno);
1632
      pressure_class = ira_pressure_class_translate[pressure_class];
1633
      *nregs
1634
        = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
1635
      return pressure_class;
1636
    }
1637
  else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
1638
           && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
1639
    {
1640
      *nregs = 1;
1641
      return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
1642
    }
1643
  else
1644
    {
1645
      *nregs = 0;
1646
      return NO_REGS;
1647
    }
1648
}
1649
 
1650
/* Increase (if INCR_P) or decrease current register pressure for
1651
   register REGNO.  */
1652
static void
1653
change_pressure (int regno, bool incr_p)
1654
{
1655
  int nregs;
1656
  enum reg_class pressure_class;
1657
 
1658
  pressure_class = get_regno_pressure_class (regno, &nregs);
1659
  if (! incr_p)
1660
    curr_reg_pressure[pressure_class] -= nregs;
1661
  else
1662
    {
1663
      curr_reg_pressure[pressure_class] += nregs;
1664
      if (LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1665
          < curr_reg_pressure[pressure_class])
1666
        LOOP_DATA (curr_loop)->max_reg_pressure[pressure_class]
1667
          = curr_reg_pressure[pressure_class];
1668
    }
1669
}
1670
 
1671
/* Mark REGNO birth.  */
1672
static void
1673
mark_regno_live (int regno)
1674
{
1675
  struct loop *loop;
1676
 
1677
  for (loop = curr_loop;
1678
       loop != current_loops->tree_root;
1679
       loop = loop_outer (loop))
1680
    bitmap_set_bit (&LOOP_DATA (loop)->regs_live, regno);
1681
  if (!bitmap_set_bit (&curr_regs_live, regno))
1682
    return;
1683
  change_pressure (regno, true);
1684
}
1685
 
1686
/* Mark REGNO death.  */
1687
static void
1688
mark_regno_death (int regno)
1689
{
1690
  if (! bitmap_clear_bit (&curr_regs_live, regno))
1691
    return;
1692
  change_pressure (regno, false);
1693
}
1694
 
1695
/* Mark setting register REG.  */
1696
static void
1697
mark_reg_store (rtx reg, const_rtx setter ATTRIBUTE_UNUSED,
1698
                void *data ATTRIBUTE_UNUSED)
1699
{
1700
  int regno;
1701
 
1702
  if (GET_CODE (reg) == SUBREG)
1703
    reg = SUBREG_REG (reg);
1704
 
1705
  if (! REG_P (reg))
1706
    return;
1707
 
1708
  regs_set[n_regs_set++] = reg;
1709
 
1710
  regno = REGNO (reg);
1711
 
1712
  if (regno >= FIRST_PSEUDO_REGISTER)
1713
    mark_regno_live (regno);
1714
  else
1715
    {
1716
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1717
 
1718
      while (regno < last)
1719
        {
1720
          mark_regno_live (regno);
1721
          regno++;
1722
        }
1723
    }
1724
}
1725
 
1726
/* Mark clobbering register REG.  */
1727
static void
1728
mark_reg_clobber (rtx reg, const_rtx setter, void *data)
1729
{
1730
  if (GET_CODE (setter) == CLOBBER)
1731
    mark_reg_store (reg, setter, data);
1732
}
1733
 
1734
/* Mark register REG death.  */
1735
static void
1736
mark_reg_death (rtx reg)
1737
{
1738
  int regno = REGNO (reg);
1739
 
1740
  if (regno >= FIRST_PSEUDO_REGISTER)
1741
    mark_regno_death (regno);
1742
  else
1743
    {
1744
      int last = regno + hard_regno_nregs[regno][GET_MODE (reg)];
1745
 
1746
      while (regno < last)
1747
        {
1748
          mark_regno_death (regno);
1749
          regno++;
1750
        }
1751
    }
1752
}
1753
 
1754
/* Mark occurrence of registers in X for the current loop.  */
1755
static void
1756
mark_ref_regs (rtx x)
1757
{
1758
  RTX_CODE code;
1759
  int i;
1760
  const char *fmt;
1761
 
1762
  if (!x)
1763
    return;
1764
 
1765
  code = GET_CODE (x);
1766
  if (code == REG)
1767
    {
1768
      struct loop *loop;
1769
 
1770
      for (loop = curr_loop;
1771
           loop != current_loops->tree_root;
1772
           loop = loop_outer (loop))
1773
        bitmap_set_bit (&LOOP_DATA (loop)->regs_ref, REGNO (x));
1774
      return;
1775
    }
1776
 
1777
  fmt = GET_RTX_FORMAT (code);
1778
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1779
    if (fmt[i] == 'e')
1780
      mark_ref_regs (XEXP (x, i));
1781
    else if (fmt[i] == 'E')
1782
      {
1783
        int j;
1784
 
1785
        for (j = 0; j < XVECLEN (x, i); j++)
1786
          mark_ref_regs (XVECEXP (x, i, j));
1787
      }
1788
}
1789
 
1790
/* Calculate register pressure in the loops.  */
1791
static void
1792
calculate_loop_reg_pressure (void)
1793
{
1794
  int i;
1795
  unsigned int j;
1796
  bitmap_iterator bi;
1797
  basic_block bb;
1798
  rtx insn, link;
1799
  struct loop *loop, *parent;
1800
  loop_iterator li;
1801
 
1802
  FOR_EACH_LOOP (li, loop, 0)
1803
    if (loop->aux == NULL)
1804
      {
1805
        loop->aux = xcalloc (1, sizeof (struct loop_data));
1806
        bitmap_initialize (&LOOP_DATA (loop)->regs_ref, &reg_obstack);
1807
        bitmap_initialize (&LOOP_DATA (loop)->regs_live, &reg_obstack);
1808
      }
1809
  ira_setup_eliminable_regset ();
1810
  bitmap_initialize (&curr_regs_live, &reg_obstack);
1811
  FOR_EACH_BB (bb)
1812
    {
1813
      curr_loop = bb->loop_father;
1814
      if (curr_loop == current_loops->tree_root)
1815
        continue;
1816
 
1817
      for (loop = curr_loop;
1818
           loop != current_loops->tree_root;
1819
           loop = loop_outer (loop))
1820
        bitmap_ior_into (&LOOP_DATA (loop)->regs_live, DF_LR_IN (bb));
1821
 
1822
      bitmap_copy (&curr_regs_live, DF_LR_IN (bb));
1823
      for (i = 0; i < ira_pressure_classes_num; i++)
1824
        curr_reg_pressure[ira_pressure_classes[i]] = 0;
1825
      EXECUTE_IF_SET_IN_BITMAP (&curr_regs_live, 0, j, bi)
1826
        change_pressure (j, true);
1827
 
1828
      FOR_BB_INSNS (bb, insn)
1829
        {
1830
          if (! NONDEBUG_INSN_P (insn))
1831
            continue;
1832
 
1833
          mark_ref_regs (PATTERN (insn));
1834
          n_regs_set = 0;
1835
          note_stores (PATTERN (insn), mark_reg_clobber, NULL);
1836
 
1837
          /* Mark any registers dead after INSN as dead now.  */
1838
 
1839
          for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1840
            if (REG_NOTE_KIND (link) == REG_DEAD)
1841
              mark_reg_death (XEXP (link, 0));
1842
 
1843
          /* Mark any registers set in INSN as live,
1844
             and mark them as conflicting with all other live regs.
1845
             Clobbers are processed again, so they conflict with
1846
             the registers that are set.  */
1847
 
1848
          note_stores (PATTERN (insn), mark_reg_store, NULL);
1849
 
1850
#ifdef AUTO_INC_DEC
1851
          for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
1852
            if (REG_NOTE_KIND (link) == REG_INC)
1853
              mark_reg_store (XEXP (link, 0), NULL_RTX, NULL);
1854
#endif
1855
          while (n_regs_set-- > 0)
1856
            {
1857
              rtx note = find_regno_note (insn, REG_UNUSED,
1858
                                          REGNO (regs_set[n_regs_set]));
1859
              if (! note)
1860
                continue;
1861
 
1862
              mark_reg_death (XEXP (note, 0));
1863
            }
1864
        }
1865
    }
1866
  bitmap_clear (&curr_regs_live);
1867
  if (flag_ira_region == IRA_REGION_MIXED
1868
      || flag_ira_region == IRA_REGION_ALL)
1869
    FOR_EACH_LOOP (li, loop, 0)
1870
      {
1871
        EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1872
          if (! bitmap_bit_p (&LOOP_DATA (loop)->regs_ref, j))
1873
            {
1874
              enum reg_class pressure_class;
1875
              int nregs;
1876
 
1877
              pressure_class = get_regno_pressure_class (j, &nregs);
1878
              LOOP_DATA (loop)->max_reg_pressure[pressure_class] -= nregs;
1879
            }
1880
      }
1881
  if (dump_file == NULL)
1882
    return;
1883
  FOR_EACH_LOOP (li, loop, 0)
1884
    {
1885
      parent = loop_outer (loop);
1886
      fprintf (dump_file, "\n  Loop %d (parent %d, header bb%d, depth %d)\n",
1887
               loop->num, (parent == NULL ? -1 : parent->num),
1888
               loop->header->index, loop_depth (loop));
1889
      fprintf (dump_file, "\n    ref. regnos:");
1890
      EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_ref, 0, j, bi)
1891
        fprintf (dump_file, " %d", j);
1892
      fprintf (dump_file, "\n    live regnos:");
1893
      EXECUTE_IF_SET_IN_BITMAP (&LOOP_DATA (loop)->regs_live, 0, j, bi)
1894
        fprintf (dump_file, " %d", j);
1895
      fprintf (dump_file, "\n    Pressure:");
1896
      for (i = 0; (int) i < ira_pressure_classes_num; i++)
1897
        {
1898
          enum reg_class pressure_class;
1899
 
1900
          pressure_class = ira_pressure_classes[i];
1901
          if (LOOP_DATA (loop)->max_reg_pressure[pressure_class] == 0)
1902
            continue;
1903
          fprintf (dump_file, " %s=%d", reg_class_names[pressure_class],
1904
                   LOOP_DATA (loop)->max_reg_pressure[pressure_class]);
1905
        }
1906
      fprintf (dump_file, "\n");
1907
    }
1908
}
1909
 
1910
 
1911
 
1912
/* Move the invariants out of the loops.  */
1913
 
1914
void
1915
move_loop_invariants (void)
1916
{
1917
  struct loop *loop;
1918
  loop_iterator li;
1919
 
1920
  if (flag_ira_loop_pressure)
1921
    {
1922
      df_analyze ();
1923
      regstat_init_n_sets_and_refs ();
1924
      ira_set_pseudo_classes (dump_file);
1925
      calculate_loop_reg_pressure ();
1926
      regstat_free_n_sets_and_refs ();
1927
    }
1928
  df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
1929
  /* Process the loops, innermost first.  */
1930
  FOR_EACH_LOOP (li, loop, LI_FROM_INNERMOST)
1931
    {
1932
      curr_loop = loop;
1933
      /* move_single_loop_invariants for very large loops
1934
         is time consuming and might need a lot of memory.  */
1935
      if (loop->num_nodes <= (unsigned) LOOP_INVARIANT_MAX_BBS_IN_LOOP)
1936
        move_single_loop_invariants (loop);
1937
    }
1938
 
1939
  FOR_EACH_LOOP (li, loop, 0)
1940
    {
1941
      free_loop_data (loop);
1942
    }
1943
 
1944
  if (flag_ira_loop_pressure)
1945
    /* There is no sense to keep this info because it was most
1946
       probably outdated by subsequent passes.  */
1947
    free_reg_info ();
1948
  free (invariant_table);
1949
  invariant_table = NULL;
1950
  invariant_table_size = 0;
1951
 
1952
#ifdef ENABLE_CHECKING
1953
  verify_flow_info ();
1954
#endif
1955
}

powered by: WebSVN 2.1.0

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