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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [cprop.c] - Blame information for rev 709

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

Line No. Rev Author Line
1 684 jeremybenn
/* Global constant/copy propagation for RTL.
2
   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
3
   2006, 2007, 2008, 2009, 2010, 2011 Free Software Foundation, Inc.
4
 
5
This file is part of GCC.
6
 
7
GCC is free software; you can redistribute it and/or modify it under
8
the terms of the GNU General Public License as published by the Free
9
Software Foundation; either version 3, or (at your option) any later
10
version.
11
 
12
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13
WARRANTY; without even the implied warranty of MERCHANTABILITY or
14
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
15
for more details.
16
 
17
You should have received a copy of the GNU General Public License
18
along with GCC; see the file COPYING3.  If not see
19
<http://www.gnu.org/licenses/>.  */
20
 
21
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "diagnostic-core.h"
26
#include "toplev.h"
27
 
28
#include "rtl.h"
29
#include "tree.h"
30
#include "tm_p.h"
31
#include "regs.h"
32
#include "hard-reg-set.h"
33
#include "flags.h"
34
#include "insn-config.h"
35
#include "recog.h"
36
#include "basic-block.h"
37
#include "output.h"
38
#include "function.h"
39
#include "expr.h"
40
#include "except.h"
41
#include "params.h"
42
#include "cselib.h"
43
#include "intl.h"
44
#include "obstack.h"
45
#include "timevar.h"
46
#include "tree-pass.h"
47
#include "hashtab.h"
48
#include "df.h"
49
#include "dbgcnt.h"
50
#include "target.h"
51
 
52
 
53
/* An obstack for our working variables.  */
54
static struct obstack cprop_obstack;
55
 
56
/* Occurrence of an expression.
57
   There is one per basic block.  If a pattern appears more than once the
58
   last appearance is used.  */
59
 
60
struct occr
61
{
62
  /* Next occurrence of this expression.  */
63
  struct occr *next;
64
  /* The insn that computes the expression.  */
65
  rtx insn;
66
};
67
 
68
typedef struct occr *occr_t;
69
DEF_VEC_P (occr_t);
70
DEF_VEC_ALLOC_P (occr_t, heap);
71
 
72
/* Hash table entry for assignment expressions.  */
73
 
74
struct expr
75
{
76
  /* The expression (DEST := SRC).  */
77
  rtx dest;
78
  rtx src;
79
 
80
  /* Index in the available expression bitmaps.  */
81
  int bitmap_index;
82
  /* Next entry with the same hash.  */
83
  struct expr *next_same_hash;
84
  /* List of available occurrence in basic blocks in the function.
85
     An "available occurrence" is one that is the last occurrence in the
86
     basic block and whose operands are not modified by following statements
87
     in the basic block [including this insn].  */
88
  struct occr *avail_occr;
89
};
90
 
91
/* Hash table for copy propagation expressions.
92
   Each hash table is an array of buckets.
93
   ??? It is known that if it were an array of entries, structure elements
94
   `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
95
   not clear whether in the final analysis a sufficient amount of memory would
96
   be saved as the size of the available expression bitmaps would be larger
97
   [one could build a mapping table without holes afterwards though].
98
   Someday I'll perform the computation and figure it out.  */
99
 
100
struct hash_table_d
101
{
102
  /* The table itself.
103
     This is an array of `set_hash_table_size' elements.  */
104
  struct expr **table;
105
 
106
  /* Size of the hash table, in elements.  */
107
  unsigned int size;
108
 
109
  /* Number of hash table elements.  */
110
  unsigned int n_elems;
111
};
112
 
113
/* Copy propagation hash table.  */
114
static struct hash_table_d set_hash_table;
115
 
116
/* Array of implicit set patterns indexed by basic block index.  */
117
static rtx *implicit_sets;
118
 
119
/* Array of indexes of expressions for implicit set patterns indexed by basic
120
   block index.  In other words, implicit_set_indexes[i] is the bitmap_index
121
   of the expression whose RTX is implicit_sets[i].  */
122
static int *implicit_set_indexes;
123
 
124
/* Bitmap containing one bit for each register in the program.
125
   Used when performing GCSE to track which registers have been set since
126
   the start or end of the basic block while traversing that block.  */
127
static regset reg_set_bitmap;
128
 
129
/* Various variables for statistics gathering.  */
130
 
131
/* Memory used in a pass.
132
   This isn't intended to be absolutely precise.  Its intent is only
133
   to keep an eye on memory usage.  */
134
static int bytes_used;
135
 
136
/* Number of local constants propagated.  */
137
static int local_const_prop_count;
138
/* Number of local copies propagated.  */
139
static int local_copy_prop_count;
140
/* Number of global constants propagated.  */
141
static int global_const_prop_count;
142
/* Number of global copies propagated.  */
143
static int global_copy_prop_count;
144
 
145
#define GOBNEW(T)               ((T *) cprop_alloc (sizeof (T)))
146
#define GOBNEWVAR(T, S)         ((T *) cprop_alloc ((S)))
147
 
148
/* Cover function to obstack_alloc.  */
149
 
150
static void *
151
cprop_alloc (unsigned long size)
152
{
153
  bytes_used += size;
154
  return obstack_alloc (&cprop_obstack, size);
155
}
156
 
157
/* Return nonzero if register X is unchanged from INSN to the end
158
   of INSN's basic block.  */
159
 
160
static int
161
reg_available_p (const_rtx x, const_rtx insn ATTRIBUTE_UNUSED)
162
{
163
  return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
164
}
165
 
166
/* Hash a set of register REGNO.
167
 
168
   Sets are hashed on the register that is set.  This simplifies the PRE copy
169
   propagation code.
170
 
171
   ??? May need to make things more elaborate.  Later, as necessary.  */
172
 
173
static unsigned int
174
hash_set (int regno, int hash_table_size)
175
{
176
  unsigned int hash;
177
 
178
  hash = regno;
179
  return hash % hash_table_size;
180
}
181
 
182
/* Insert assignment DEST:=SET from INSN in the hash table.
183
   DEST is a register and SET is a register or a suitable constant.
184
   If the assignment is already present in the table, record it as
185
   the last occurrence in INSN's basic block.
186
   IMPLICIT is true if it's an implicit set, false otherwise.  */
187
 
188
static void
189
insert_set_in_table (rtx dest, rtx src, rtx insn, struct hash_table_d *table,
190
                     bool implicit)
191
{
192
  bool found = false;
193
  unsigned int hash;
194
  struct expr *cur_expr, *last_expr = NULL;
195
  struct occr *cur_occr;
196
 
197
  hash = hash_set (REGNO (dest), table->size);
198
 
199
  for (cur_expr = table->table[hash]; cur_expr;
200
       cur_expr = cur_expr->next_same_hash)
201
    {
202
      if (dest == cur_expr->dest
203
          && src == cur_expr->src)
204
        {
205
          found = true;
206
          break;
207
        }
208
      last_expr = cur_expr;
209
    }
210
 
211
  if (! found)
212
    {
213
      cur_expr = GOBNEW (struct expr);
214
      bytes_used += sizeof (struct expr);
215
      if (table->table[hash] == NULL)
216
        /* This is the first pattern that hashed to this index.  */
217
        table->table[hash] = cur_expr;
218
      else
219
        /* Add EXPR to end of this hash chain.  */
220
        last_expr->next_same_hash = cur_expr;
221
 
222
      /* Set the fields of the expr element.
223
         We must copy X because it can be modified when copy propagation is
224
         performed on its operands.  */
225
      cur_expr->dest = copy_rtx (dest);
226
      cur_expr->src = copy_rtx (src);
227
      cur_expr->bitmap_index = table->n_elems++;
228
      cur_expr->next_same_hash = NULL;
229
      cur_expr->avail_occr = NULL;
230
    }
231
 
232
  /* Now record the occurrence.  */
233
  cur_occr = cur_expr->avail_occr;
234
 
235
  if (cur_occr
236
      && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
237
    {
238
      /* Found another instance of the expression in the same basic block.
239
         Prefer this occurrence to the currently recorded one.  We want
240
         the last one in the block and the block is scanned from start
241
         to end.  */
242
      cur_occr->insn = insn;
243
    }
244
  else
245
    {
246
      /* First occurrence of this expression in this basic block.  */
247
      cur_occr = GOBNEW (struct occr);
248
      bytes_used += sizeof (struct occr);
249
      cur_occr->insn = insn;
250
      cur_occr->next = cur_expr->avail_occr;
251
      cur_expr->avail_occr = cur_occr;
252
    }
253
 
254
  /* Record bitmap_index of the implicit set in implicit_set_indexes.  */
255
  if (implicit)
256
    implicit_set_indexes[BLOCK_FOR_INSN(insn)->index] = cur_expr->bitmap_index;
257
}
258
 
259
/* Determine whether the rtx X should be treated as a constant for CPROP.
260
   Since X might be inserted more than once we have to take care that it
261
   is sharable.  */
262
 
263
static bool
264
cprop_constant_p (const_rtx x)
265
{
266
  return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
267
}
268
 
269
/* Scan SET present in INSN and add an entry to the hash TABLE.
270
   IMPLICIT is true if it's an implicit set, false otherwise.  */
271
 
272
static void
273
hash_scan_set (rtx set, rtx insn, struct hash_table_d *table, bool implicit)
274
{
275
  rtx src = SET_SRC (set);
276
  rtx dest = SET_DEST (set);
277
 
278
  if (REG_P (dest)
279
      && ! HARD_REGISTER_P (dest)
280
      && reg_available_p (dest, insn)
281
      && can_copy_p (GET_MODE (dest)))
282
    {
283
      /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
284
 
285
         This allows us to do a single CPROP pass and still eliminate
286
         redundant constants, addresses or other expressions that are
287
         constructed with multiple instructions.
288
 
289
         However, keep the original SRC if INSN is a simple reg-reg move.  In
290
         In this case, there will almost always be a REG_EQUAL note on the
291
         insn that sets SRC.  By recording the REG_EQUAL value here as SRC
292
         for INSN, we miss copy propagation opportunities.
293
 
294
         Note that this does not impede profitable constant propagations.  We
295
         "look through" reg-reg sets in lookup_set.  */
296
      rtx note = find_reg_equal_equiv_note (insn);
297
      if (note != 0
298
          && REG_NOTE_KIND (note) == REG_EQUAL
299
          && !REG_P (src)
300
          && cprop_constant_p (XEXP (note, 0)))
301
        src = XEXP (note, 0), set = gen_rtx_SET (VOIDmode, dest, src);
302
 
303
      /* Record sets for constant/copy propagation.  */
304
      if ((REG_P (src)
305
           && src != dest
306
           && ! HARD_REGISTER_P (src)
307
           && reg_available_p (src, insn))
308
          || cprop_constant_p (src))
309
        insert_set_in_table (dest, src, insn, table, implicit);
310
    }
311
}
312
 
313
/* Process INSN and add hash table entries as appropriate.  */
314
 
315
static void
316
hash_scan_insn (rtx insn, struct hash_table_d *table)
317
{
318
  rtx pat = PATTERN (insn);
319
  int i;
320
 
321
  /* Pick out the sets of INSN and for other forms of instructions record
322
     what's been modified.  */
323
 
324
  if (GET_CODE (pat) == SET)
325
    hash_scan_set (pat, insn, table, false);
326
  else if (GET_CODE (pat) == PARALLEL)
327
    for (i = 0; i < XVECLEN (pat, 0); i++)
328
      {
329
        rtx x = XVECEXP (pat, 0, i);
330
 
331
        if (GET_CODE (x) == SET)
332
          hash_scan_set (x, insn, table, false);
333
      }
334
}
335
 
336
/* Dump the hash table TABLE to file FILE under the name NAME.  */
337
 
338
static void
339
dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
340
{
341
  int i;
342
  /* Flattened out table, so it's printed in proper order.  */
343
  struct expr **flat_table;
344
  unsigned int *hash_val;
345
  struct expr *expr;
346
 
347
  flat_table = XCNEWVEC (struct expr *, table->n_elems);
348
  hash_val = XNEWVEC (unsigned int, table->n_elems);
349
 
350
  for (i = 0; i < (int) table->size; i++)
351
    for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
352
      {
353
        flat_table[expr->bitmap_index] = expr;
354
        hash_val[expr->bitmap_index] = i;
355
      }
356
 
357
  fprintf (file, "%s hash table (%d buckets, %d entries)\n",
358
           name, table->size, table->n_elems);
359
 
360
  for (i = 0; i < (int) table->n_elems; i++)
361
    if (flat_table[i] != 0)
362
      {
363
        expr = flat_table[i];
364
        fprintf (file, "Index %d (hash value %d)\n  ",
365
                 expr->bitmap_index, hash_val[i]);
366
        print_rtl (file, expr->dest);
367
        fprintf (file, " := ");
368
        print_rtl (file, expr->src);
369
        fprintf (file, "\n");
370
      }
371
 
372
  fprintf (file, "\n");
373
 
374
  free (flat_table);
375
  free (hash_val);
376
}
377
 
378
/* Record as unavailable all registers that are DEF operands of INSN.  */
379
 
380
static void
381
make_set_regs_unavailable (rtx insn)
382
{
383
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
384
  df_ref *def_rec;
385
 
386
  for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
387
    SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (*def_rec));
388
}
389
 
390
/* Top level function to create an assignment hash table.
391
 
392
   Assignment entries are placed in the hash table if
393
   - they are of the form (set (pseudo-reg) src),
394
   - src is something we want to perform const/copy propagation on,
395
   - none of the operands or target are subsequently modified in the block
396
 
397
   Currently src must be a pseudo-reg or a const_int.
398
 
399
   TABLE is the table computed.  */
400
 
401
static void
402
compute_hash_table_work (struct hash_table_d *table)
403
{
404
  basic_block bb;
405
 
406
  /* Allocate vars to track sets of regs.  */
407
  reg_set_bitmap = ALLOC_REG_SET (NULL);
408
 
409
  FOR_EACH_BB (bb)
410
    {
411
      rtx insn;
412
 
413
      /* Reset tables used to keep track of what's not yet invalid [since
414
         the end of the block].  */
415
      CLEAR_REG_SET (reg_set_bitmap);
416
 
417
      /* Go over all insns from the last to the first.  This is convenient
418
         for tracking available registers, i.e. not set between INSN and
419
         the end of the basic block BB.  */
420
      FOR_BB_INSNS_REVERSE (bb, insn)
421
        {
422
          /* Only real insns are interesting.  */
423
          if (!NONDEBUG_INSN_P (insn))
424
            continue;
425
 
426
          /* Record interesting sets from INSN in the hash table.  */
427
          hash_scan_insn (insn, table);
428
 
429
          /* Any registers set in INSN will make SETs above it not AVAIL.  */
430
          make_set_regs_unavailable (insn);
431
        }
432
 
433
      /* Insert implicit sets in the hash table, pretending they appear as
434
         insns at the head of the basic block.  */
435
      if (implicit_sets[bb->index] != NULL_RTX)
436
        hash_scan_set (implicit_sets[bb->index], BB_HEAD (bb), table, true);
437
    }
438
 
439
  FREE_REG_SET (reg_set_bitmap);
440
}
441
 
442
/* Allocate space for the set/expr hash TABLE.
443
   It is used to determine the number of buckets to use.  */
444
 
445
static void
446
alloc_hash_table (struct hash_table_d *table)
447
{
448
  int n;
449
 
450
  n = get_max_insn_count ();
451
 
452
  table->size = n / 4;
453
  if (table->size < 11)
454
    table->size = 11;
455
 
456
  /* Attempt to maintain efficient use of hash table.
457
     Making it an odd number is simplest for now.
458
     ??? Later take some measurements.  */
459
  table->size |= 1;
460
  n = table->size * sizeof (struct expr *);
461
  table->table = XNEWVAR (struct expr *, n);
462
}
463
 
464
/* Free things allocated by alloc_hash_table.  */
465
 
466
static void
467
free_hash_table (struct hash_table_d *table)
468
{
469
  free (table->table);
470
}
471
 
472
/* Compute the hash TABLE for doing copy/const propagation or
473
   expression hash table.  */
474
 
475
static void
476
compute_hash_table (struct hash_table_d *table)
477
{
478
  /* Initialize count of number of entries in hash table.  */
479
  table->n_elems = 0;
480
  memset (table->table, 0, table->size * sizeof (struct expr *));
481
 
482
  compute_hash_table_work (table);
483
}
484
 
485
/* Expression tracking support.  */
486
 
487
/* Lookup REGNO in the set TABLE.  The result is a pointer to the
488
   table entry, or NULL if not found.  */
489
 
490
static struct expr *
491
lookup_set (unsigned int regno, struct hash_table_d *table)
492
{
493
  unsigned int hash = hash_set (regno, table->size);
494
  struct expr *expr;
495
 
496
  expr = table->table[hash];
497
 
498
  while (expr && REGNO (expr->dest) != regno)
499
    expr = expr->next_same_hash;
500
 
501
  return expr;
502
}
503
 
504
/* Return the next entry for REGNO in list EXPR.  */
505
 
506
static struct expr *
507
next_set (unsigned int regno, struct expr *expr)
508
{
509
  do
510
    expr = expr->next_same_hash;
511
  while (expr && REGNO (expr->dest) != regno);
512
 
513
  return expr;
514
}
515
 
516
/* Reset tables used to keep track of what's still available [since the
517
   start of the block].  */
518
 
519
static void
520
reset_opr_set_tables (void)
521
{
522
  /* Maintain a bitmap of which regs have been set since beginning of
523
     the block.  */
524
  CLEAR_REG_SET (reg_set_bitmap);
525
}
526
 
527
/* Return nonzero if the register X has not been set yet [since the
528
   start of the basic block containing INSN].  */
529
 
530
static int
531
reg_not_set_p (const_rtx x, const_rtx insn ATTRIBUTE_UNUSED)
532
{
533
  return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
534
}
535
 
536
/* Record things set by INSN.
537
   This data is used by reg_not_set_p.  */
538
 
539
static void
540
mark_oprs_set (rtx insn)
541
{
542
  struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
543
  df_ref *def_rec;
544
 
545
  for (def_rec = DF_INSN_INFO_DEFS (insn_info); *def_rec; def_rec++)
546
    SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (*def_rec));
547
}
548
 
549
/* Compute copy/constant propagation working variables.  */
550
 
551
/* Local properties of assignments.  */
552
static sbitmap *cprop_avloc;
553
static sbitmap *cprop_kill;
554
 
555
/* Global properties of assignments (computed from the local properties).  */
556
static sbitmap *cprop_avin;
557
static sbitmap *cprop_avout;
558
 
559
/* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
560
   basic blocks.  N_SETS is the number of sets.  */
561
 
562
static void
563
alloc_cprop_mem (int n_blocks, int n_sets)
564
{
565
  cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
566
  cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
567
 
568
  cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
569
  cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
570
}
571
 
572
/* Free vars used by copy/const propagation.  */
573
 
574
static void
575
free_cprop_mem (void)
576
{
577
  sbitmap_vector_free (cprop_avloc);
578
  sbitmap_vector_free (cprop_kill);
579
  sbitmap_vector_free (cprop_avin);
580
  sbitmap_vector_free (cprop_avout);
581
}
582
 
583
/* Compute the local properties of each recorded expression.
584
 
585
   Local properties are those that are defined by the block, irrespective of
586
   other blocks.
587
 
588
   An expression is killed in a block if its operands, either DEST or SRC, are
589
   modified in the block.
590
 
591
   An expression is computed (locally available) in a block if it is computed
592
   at least once and expression would contain the same value if the
593
   computation was moved to the end of the block.
594
 
595
   KILL and COMP are destination sbitmaps for recording local properties.  */
596
 
597
static void
598
compute_local_properties (sbitmap *kill, sbitmap *comp,
599
                          struct hash_table_d *table)
600
{
601
  unsigned int i;
602
 
603
  /* Initialize the bitmaps that were passed in.  */
604
  sbitmap_vector_zero (kill, last_basic_block);
605
  sbitmap_vector_zero (comp, last_basic_block);
606
 
607
  for (i = 0; i < table->size; i++)
608
    {
609
      struct expr *expr;
610
 
611
      for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
612
        {
613
          int indx = expr->bitmap_index;
614
          df_ref def;
615
          struct occr *occr;
616
 
617
          /* For each definition of the destination pseudo-reg, the expression
618
             is killed in the block where the definition is.  */
619
          for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
620
               def; def = DF_REF_NEXT_REG (def))
621
            SET_BIT (kill[DF_REF_BB (def)->index], indx);
622
 
623
          /* If the source is a pseudo-reg, for each definition of the source,
624
             the expression is killed in the block where the definition is.  */
625
          if (REG_P (expr->src))
626
            for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
627
                 def; def = DF_REF_NEXT_REG (def))
628
              SET_BIT (kill[DF_REF_BB (def)->index], indx);
629
 
630
          /* The occurrences recorded in avail_occr are exactly those that
631
             are locally available in the block where they are.  */
632
          for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
633
            {
634
              SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
635
            }
636
        }
637
    }
638
}
639
 
640
/* Hash table support.  */
641
 
642
/* Top level routine to do the dataflow analysis needed by copy/const
643
   propagation.  */
644
 
645
static void
646
compute_cprop_data (void)
647
{
648
  basic_block bb;
649
 
650
  compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
651
  compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
652
 
653
  /* Merge implicit sets into CPROP_AVIN.  They are always available at the
654
     entry of their basic block.  We need to do this because 1) implicit sets
655
     aren't recorded for the local pass so they cannot be propagated within
656
     their basic block by this pass and 2) the global pass would otherwise
657
     propagate them only in the successors of their basic block.  */
658
  FOR_EACH_BB (bb)
659
    {
660
      int index = implicit_set_indexes[bb->index];
661
      if (index != -1)
662
        SET_BIT (cprop_avin[bb->index], index);
663
    }
664
}
665
 
666
/* Copy/constant propagation.  */
667
 
668
/* Maximum number of register uses in an insn that we handle.  */
669
#define MAX_USES 8
670
 
671
/* Table of uses (registers, both hard and pseudo) found in an insn.
672
   Allocated statically to avoid alloc/free complexity and overhead.  */
673
static rtx reg_use_table[MAX_USES];
674
 
675
/* Index into `reg_use_table' while building it.  */
676
static unsigned reg_use_count;
677
 
678
/* Set up a list of register numbers used in INSN.  The found uses are stored
679
   in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
680
   and contains the number of uses in the table upon exit.
681
 
682
   ??? If a register appears multiple times we will record it multiple times.
683
   This doesn't hurt anything but it will slow things down.  */
684
 
685
static void
686
find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
687
{
688
  int i, j;
689
  enum rtx_code code;
690
  const char *fmt;
691
  rtx x = *xptr;
692
 
693
  /* repeat is used to turn tail-recursion into iteration since GCC
694
     can't do it when there's no return value.  */
695
 repeat:
696
  if (x == 0)
697
    return;
698
 
699
  code = GET_CODE (x);
700
  if (REG_P (x))
701
    {
702
      if (reg_use_count == MAX_USES)
703
        return;
704
 
705
      reg_use_table[reg_use_count] = x;
706
      reg_use_count++;
707
    }
708
 
709
  /* Recursively scan the operands of this expression.  */
710
 
711
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
712
    {
713
      if (fmt[i] == 'e')
714
        {
715
          /* If we are about to do the last recursive call
716
             needed at this level, change it into iteration.
717
             This function is called enough to be worth it.  */
718
          if (i == 0)
719
            {
720
              x = XEXP (x, 0);
721
              goto repeat;
722
            }
723
 
724
          find_used_regs (&XEXP (x, i), data);
725
        }
726
      else if (fmt[i] == 'E')
727
        for (j = 0; j < XVECLEN (x, i); j++)
728
          find_used_regs (&XVECEXP (x, i, j), data);
729
    }
730
}
731
 
732
/* Try to replace all uses of FROM in INSN with TO.
733
   Return nonzero if successful.  */
734
 
735
static int
736
try_replace_reg (rtx from, rtx to, rtx insn)
737
{
738
  rtx note = find_reg_equal_equiv_note (insn);
739
  rtx src = 0;
740
  int success = 0;
741
  rtx set = single_set (insn);
742
 
743
  /* Usually we substitute easy stuff, so we won't copy everything.
744
     We however need to take care to not duplicate non-trivial CONST
745
     expressions.  */
746
  to = copy_rtx (to);
747
 
748
  validate_replace_src_group (from, to, insn);
749
  if (num_changes_pending () && apply_change_group ())
750
    success = 1;
751
 
752
  /* Try to simplify SET_SRC if we have substituted a constant.  */
753
  if (success && set && CONSTANT_P (to))
754
    {
755
      src = simplify_rtx (SET_SRC (set));
756
 
757
      if (src)
758
        validate_change (insn, &SET_SRC (set), src, 0);
759
    }
760
 
761
  /* If there is already a REG_EQUAL note, update the expression in it
762
     with our replacement.  */
763
  if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
764
    set_unique_reg_note (insn, REG_EQUAL,
765
                         simplify_replace_rtx (XEXP (note, 0), from, to));
766
  if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
767
    {
768
      /* If above failed and this is a single set, try to simplify the source
769
         of the set given our substitution.  We could perhaps try this for
770
         multiple SETs, but it probably won't buy us anything.  */
771
      src = simplify_replace_rtx (SET_SRC (set), from, to);
772
 
773
      if (!rtx_equal_p (src, SET_SRC (set))
774
          && validate_change (insn, &SET_SRC (set), src, 0))
775
        success = 1;
776
 
777
      /* If we've failed perform the replacement, have a single SET to
778
         a REG destination and don't yet have a note, add a REG_EQUAL note
779
         to not lose information.  */
780
      if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
781
        note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
782
    }
783
 
784
  if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
785
    {
786
      /* Registers can also appear as uses in SET_DEST if it is a MEM.
787
         We could perhaps try this for multiple SETs, but it probably
788
         won't buy us anything.  */
789
      rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
790
 
791
      if (!rtx_equal_p (dest, SET_DEST (set))
792
          && validate_change (insn, &SET_DEST (set), dest, 0))
793
        success = 1;
794
    }
795
 
796
  /* REG_EQUAL may get simplified into register.
797
     We don't allow that. Remove that note. This code ought
798
     not to happen, because previous code ought to synthesize
799
     reg-reg move, but be on the safe side.  */
800
  if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
801
    remove_note (insn, note);
802
 
803
  return success;
804
}
805
 
806
/* Find a set of REGNOs that are available on entry to INSN's block.  Return
807
   NULL no such set is found.  */
808
 
809
static struct expr *
810
find_avail_set (int regno, rtx insn)
811
{
812
  /* SET1 contains the last set found that can be returned to the caller for
813
     use in a substitution.  */
814
  struct expr *set1 = 0;
815
 
816
  /* Loops are not possible here.  To get a loop we would need two sets
817
     available at the start of the block containing INSN.  i.e. we would
818
     need two sets like this available at the start of the block:
819
 
820
       (set (reg X) (reg Y))
821
       (set (reg Y) (reg X))
822
 
823
     This can not happen since the set of (reg Y) would have killed the
824
     set of (reg X) making it unavailable at the start of this block.  */
825
  while (1)
826
    {
827
      rtx src;
828
      struct expr *set = lookup_set (regno, &set_hash_table);
829
 
830
      /* Find a set that is available at the start of the block
831
         which contains INSN.  */
832
      while (set)
833
        {
834
          if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index],
835
                        set->bitmap_index))
836
            break;
837
          set = next_set (regno, set);
838
        }
839
 
840
      /* If no available set was found we've reached the end of the
841
         (possibly empty) copy chain.  */
842
      if (set == 0)
843
        break;
844
 
845
      src = set->src;
846
 
847
      /* We know the set is available.
848
         Now check that SRC is locally anticipatable (i.e. none of the
849
         source operands have changed since the start of the block).
850
 
851
         If the source operand changed, we may still use it for the next
852
         iteration of this loop, but we may not use it for substitutions.  */
853
 
854
      if (cprop_constant_p (src) || reg_not_set_p (src, insn))
855
        set1 = set;
856
 
857
      /* If the source of the set is anything except a register, then
858
         we have reached the end of the copy chain.  */
859
      if (! REG_P (src))
860
        break;
861
 
862
      /* Follow the copy chain, i.e. start another iteration of the loop
863
         and see if we have an available copy into SRC.  */
864
      regno = REGNO (src);
865
    }
866
 
867
  /* SET1 holds the last set that was available and anticipatable at
868
     INSN.  */
869
  return set1;
870
}
871
 
872
/* Subroutine of cprop_insn that tries to propagate constants into
873
   JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
874
   it is the instruction that immediately precedes JUMP, and must be a
875
   single SET of a register.  FROM is what we will try to replace,
876
   SRC is the constant we will try to substitute for it.  Return nonzero
877
   if a change was made.  */
878
 
879
static int
880
cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
881
{
882
  rtx new_rtx, set_src, note_src;
883
  rtx set = pc_set (jump);
884
  rtx note = find_reg_equal_equiv_note (jump);
885
 
886
  if (note)
887
    {
888
      note_src = XEXP (note, 0);
889
      if (GET_CODE (note_src) == EXPR_LIST)
890
        note_src = NULL_RTX;
891
    }
892
  else note_src = NULL_RTX;
893
 
894
  /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
895
  set_src = note_src ? note_src : SET_SRC (set);
896
 
897
  /* First substitute the SETCC condition into the JUMP instruction,
898
     then substitute that given values into this expanded JUMP.  */
899
  if (setcc != NULL_RTX
900
      && !modified_between_p (from, setcc, jump)
901
      && !modified_between_p (src, setcc, jump))
902
    {
903
      rtx setcc_src;
904
      rtx setcc_set = single_set (setcc);
905
      rtx setcc_note = find_reg_equal_equiv_note (setcc);
906
      setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
907
                ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
908
      set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
909
                                      setcc_src);
910
    }
911
  else
912
    setcc = NULL_RTX;
913
 
914
  new_rtx = simplify_replace_rtx (set_src, from, src);
915
 
916
  /* If no simplification can be made, then try the next register.  */
917
  if (rtx_equal_p (new_rtx, SET_SRC (set)))
918
    return 0;
919
 
920
  /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
921
  if (new_rtx == pc_rtx)
922
    delete_insn (jump);
923
  else
924
    {
925
      /* Ensure the value computed inside the jump insn to be equivalent
926
         to one computed by setcc.  */
927
      if (setcc && modified_in_p (new_rtx, setcc))
928
        return 0;
929
      if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
930
        {
931
          /* When (some) constants are not valid in a comparison, and there
932
             are two registers to be replaced by constants before the entire
933
             comparison can be folded into a constant, we need to keep
934
             intermediate information in REG_EQUAL notes.  For targets with
935
             separate compare insns, such notes are added by try_replace_reg.
936
             When we have a combined compare-and-branch instruction, however,
937
             we need to attach a note to the branch itself to make this
938
             optimization work.  */
939
 
940
          if (!rtx_equal_p (new_rtx, note_src))
941
            set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
942
          return 0;
943
        }
944
 
945
      /* Remove REG_EQUAL note after simplification.  */
946
      if (note_src)
947
        remove_note (jump, note);
948
     }
949
 
950
#ifdef HAVE_cc0
951
  /* Delete the cc0 setter.  */
952
  if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
953
    delete_insn (setcc);
954
#endif
955
 
956
  global_const_prop_count++;
957
  if (dump_file != NULL)
958
    {
959
      fprintf (dump_file,
960
               "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with"
961
               "constant ", REGNO (from), INSN_UID (jump));
962
      print_rtl (dump_file, src);
963
      fprintf (dump_file, "\n");
964
    }
965
  purge_dead_edges (bb);
966
 
967
  /* If a conditional jump has been changed into unconditional jump, remove
968
     the jump and make the edge fallthru - this is always called in
969
     cfglayout mode.  */
970
  if (new_rtx != pc_rtx && simplejump_p (jump))
971
    {
972
      edge e;
973
      edge_iterator ei;
974
 
975
      FOR_EACH_EDGE (e, ei, bb->succs)
976
        if (e->dest != EXIT_BLOCK_PTR
977
            && BB_HEAD (e->dest) == JUMP_LABEL (jump))
978
          {
979
            e->flags |= EDGE_FALLTHRU;
980
            break;
981
          }
982
      delete_insn (jump);
983
    }
984
 
985
  return 1;
986
}
987
 
988
/* Subroutine of cprop_insn that tries to propagate constants.  FROM is what
989
   we will try to replace, SRC is the constant we will try to substitute for
990
   it and INSN is the instruction where this will be happening.  */
991
 
992
static int
993
constprop_register (rtx from, rtx src, rtx insn)
994
{
995
  rtx sset;
996
 
997
  /* Check for reg or cc0 setting instructions followed by
998
     conditional branch instructions first.  */
999
  if ((sset = single_set (insn)) != NULL
1000
      && NEXT_INSN (insn)
1001
      && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
1002
    {
1003
      rtx dest = SET_DEST (sset);
1004
      if ((REG_P (dest) || CC0_P (dest))
1005
          && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
1006
                         from, src))
1007
        return 1;
1008
    }
1009
 
1010
  /* Handle normal insns next.  */
1011
  if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
1012
    return 1;
1013
 
1014
  /* Try to propagate a CONST_INT into a conditional jump.
1015
     We're pretty specific about what we will handle in this
1016
     code, we can extend this as necessary over time.
1017
 
1018
     Right now the insn in question must look like
1019
     (set (pc) (if_then_else ...))  */
1020
  else if (any_condjump_p (insn) && onlyjump_p (insn))
1021
    return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
1022
  return 0;
1023
}
1024
 
1025
/* Perform constant and copy propagation on INSN.
1026
   Return nonzero if a change was made.  */
1027
 
1028
static int
1029
cprop_insn (rtx insn)
1030
{
1031
  unsigned i;
1032
  int changed = 0, changed_this_round;
1033
  rtx note;
1034
 
1035
retry:
1036
  changed_this_round = 0;
1037
  reg_use_count = 0;
1038
  note_uses (&PATTERN (insn), find_used_regs, NULL);
1039
 
1040
  /* We may win even when propagating constants into notes.  */
1041
  note = find_reg_equal_equiv_note (insn);
1042
  if (note)
1043
    find_used_regs (&XEXP (note, 0), NULL);
1044
 
1045
  for (i = 0; i < reg_use_count; i++)
1046
    {
1047
      rtx reg_used = reg_use_table[i];
1048
      unsigned int regno = REGNO (reg_used);
1049
      rtx src;
1050
      struct expr *set;
1051
 
1052
      /* If the register has already been set in this block, there's
1053
         nothing we can do.  */
1054
      if (! reg_not_set_p (reg_used, insn))
1055
        continue;
1056
 
1057
      /* Find an assignment that sets reg_used and is available
1058
         at the start of the block.  */
1059
      set = find_avail_set (regno, insn);
1060
      if (! set)
1061
        continue;
1062
 
1063
      src = set->src;
1064
 
1065
      /* Constant propagation.  */
1066
      if (cprop_constant_p (src))
1067
        {
1068
          if (constprop_register (reg_used, src, insn))
1069
            {
1070
              changed_this_round = changed = 1;
1071
              global_const_prop_count++;
1072
              if (dump_file != NULL)
1073
                {
1074
                  fprintf (dump_file,
1075
                           "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
1076
                  fprintf (dump_file, "insn %d with constant ",
1077
                           INSN_UID (insn));
1078
                  print_rtl (dump_file, src);
1079
                  fprintf (dump_file, "\n");
1080
                }
1081
              if (INSN_DELETED_P (insn))
1082
                return 1;
1083
            }
1084
        }
1085
      else if (REG_P (src)
1086
               && REGNO (src) >= FIRST_PSEUDO_REGISTER
1087
               && REGNO (src) != regno)
1088
        {
1089
          if (try_replace_reg (reg_used, src, insn))
1090
            {
1091
              changed_this_round = changed = 1;
1092
              global_copy_prop_count++;
1093
              if (dump_file != NULL)
1094
                {
1095
                  fprintf (dump_file,
1096
                           "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
1097
                           regno, INSN_UID (insn));
1098
                  fprintf (dump_file, " with reg %d\n", REGNO (src));
1099
                }
1100
 
1101
              /* The original insn setting reg_used may or may not now be
1102
                 deletable.  We leave the deletion to DCE.  */
1103
              /* FIXME: If it turns out that the insn isn't deletable,
1104
                 then we may have unnecessarily extended register lifetimes
1105
                 and made things worse.  */
1106
            }
1107
        }
1108
 
1109
      /* If try_replace_reg simplified the insn, the regs found
1110
         by find_used_regs may not be valid anymore.  Start over.  */
1111
      if (changed_this_round)
1112
        goto retry;
1113
    }
1114
 
1115
  if (changed && DEBUG_INSN_P (insn))
1116
    return 0;
1117
 
1118
  return changed;
1119
}
1120
 
1121
/* Like find_used_regs, but avoid recording uses that appear in
1122
   input-output contexts such as zero_extract or pre_dec.  This
1123
   restricts the cases we consider to those for which local cprop
1124
   can legitimately make replacements.  */
1125
 
1126
static void
1127
local_cprop_find_used_regs (rtx *xptr, void *data)
1128
{
1129
  rtx x = *xptr;
1130
 
1131
  if (x == 0)
1132
    return;
1133
 
1134
  switch (GET_CODE (x))
1135
    {
1136
    case ZERO_EXTRACT:
1137
    case SIGN_EXTRACT:
1138
    case STRICT_LOW_PART:
1139
      return;
1140
 
1141
    case PRE_DEC:
1142
    case PRE_INC:
1143
    case POST_DEC:
1144
    case POST_INC:
1145
    case PRE_MODIFY:
1146
    case POST_MODIFY:
1147
      /* Can only legitimately appear this early in the context of
1148
         stack pushes for function arguments, but handle all of the
1149
         codes nonetheless.  */
1150
      return;
1151
 
1152
    case SUBREG:
1153
      /* Setting a subreg of a register larger than word_mode leaves
1154
         the non-written words unchanged.  */
1155
      if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
1156
        return;
1157
      break;
1158
 
1159
    default:
1160
      break;
1161
    }
1162
 
1163
  find_used_regs (xptr, data);
1164
}
1165
 
1166
/* Try to perform local const/copy propagation on X in INSN.  */
1167
 
1168
static bool
1169
do_local_cprop (rtx x, rtx insn)
1170
{
1171
  rtx newreg = NULL, newcnst = NULL;
1172
 
1173
  /* Rule out USE instructions and ASM statements as we don't want to
1174
     change the hard registers mentioned.  */
1175
  if (REG_P (x)
1176
      && (REGNO (x) >= FIRST_PSEUDO_REGISTER
1177
          || (GET_CODE (PATTERN (insn)) != USE
1178
              && asm_noperands (PATTERN (insn)) < 0)))
1179
    {
1180
      cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
1181
      struct elt_loc_list *l;
1182
 
1183
      if (!val)
1184
        return false;
1185
      for (l = val->locs; l; l = l->next)
1186
        {
1187
          rtx this_rtx = l->loc;
1188
          rtx note;
1189
 
1190
          if (cprop_constant_p (this_rtx))
1191
            newcnst = this_rtx;
1192
          if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
1193
              /* Don't copy propagate if it has attached REG_EQUIV note.
1194
                 At this point this only function parameters should have
1195
                 REG_EQUIV notes and if the argument slot is used somewhere
1196
                 explicitly, it means address of parameter has been taken,
1197
                 so we should not extend the lifetime of the pseudo.  */
1198
              && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
1199
                  || ! MEM_P (XEXP (note, 0))))
1200
            newreg = this_rtx;
1201
        }
1202
      if (newcnst && constprop_register (x, newcnst, insn))
1203
        {
1204
          if (dump_file != NULL)
1205
            {
1206
              fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
1207
                       REGNO (x));
1208
              fprintf (dump_file, "insn %d with constant ",
1209
                       INSN_UID (insn));
1210
              print_rtl (dump_file, newcnst);
1211
              fprintf (dump_file, "\n");
1212
            }
1213
          local_const_prop_count++;
1214
          return true;
1215
        }
1216
      else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
1217
        {
1218
          if (dump_file != NULL)
1219
            {
1220
              fprintf (dump_file,
1221
                       "LOCAL COPY-PROP: Replacing reg %d in insn %d",
1222
                       REGNO (x), INSN_UID (insn));
1223
              fprintf (dump_file, " with reg %d\n", REGNO (newreg));
1224
            }
1225
          local_copy_prop_count++;
1226
          return true;
1227
        }
1228
    }
1229
  return false;
1230
}
1231
 
1232
/* Do local const/copy propagation (i.e. within each basic block).  */
1233
 
1234
static int
1235
local_cprop_pass (void)
1236
{
1237
  basic_block bb;
1238
  rtx insn;
1239
  bool changed = false;
1240
  unsigned i;
1241
 
1242
  cselib_init (0);
1243
  FOR_EACH_BB (bb)
1244
    {
1245
      FOR_BB_INSNS (bb, insn)
1246
        {
1247
          if (INSN_P (insn))
1248
            {
1249
              rtx note = find_reg_equal_equiv_note (insn);
1250
              do
1251
                {
1252
                  reg_use_count = 0;
1253
                  note_uses (&PATTERN (insn), local_cprop_find_used_regs,
1254
                             NULL);
1255
                  if (note)
1256
                    local_cprop_find_used_regs (&XEXP (note, 0), NULL);
1257
 
1258
                  for (i = 0; i < reg_use_count; i++)
1259
                    {
1260
                      if (do_local_cprop (reg_use_table[i], insn))
1261
                        {
1262
                          if (!DEBUG_INSN_P (insn))
1263
                            changed = true;
1264
                          break;
1265
                        }
1266
                    }
1267
                  if (INSN_DELETED_P (insn))
1268
                    break;
1269
                }
1270
              while (i < reg_use_count);
1271
            }
1272
          cselib_process_insn (insn);
1273
        }
1274
 
1275
      /* Forget everything at the end of a basic block.  */
1276
      cselib_clear_table ();
1277
    }
1278
 
1279
  cselib_finish ();
1280
 
1281
  return changed;
1282
}
1283
 
1284
/* Similar to get_condition, only the resulting condition must be
1285
   valid at JUMP, instead of at EARLIEST.
1286
 
1287
   This differs from noce_get_condition in ifcvt.c in that we prefer not to
1288
   settle for the condition variable in the jump instruction being integral.
1289
   We prefer to be able to record the value of a user variable, rather than
1290
   the value of a temporary used in a condition.  This could be solved by
1291
   recording the value of *every* register scanned by canonicalize_condition,
1292
   but this would require some code reorganization.  */
1293
 
1294
rtx
1295
fis_get_condition (rtx jump)
1296
{
1297
  return get_condition (jump, NULL, false, true);
1298
}
1299
 
1300
/* Check the comparison COND to see if we can safely form an implicit
1301
   set from it.  */
1302
 
1303
static bool
1304
implicit_set_cond_p (const_rtx cond)
1305
{
1306
  enum machine_mode mode;
1307
  rtx cst;
1308
 
1309
  /* COND must be either an EQ or NE comparison.  */
1310
  if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
1311
    return false;
1312
 
1313
  /* The first operand of COND must be a pseudo-reg.  */
1314
  if (! REG_P (XEXP (cond, 0))
1315
      || HARD_REGISTER_P (XEXP (cond, 0)))
1316
    return false;
1317
 
1318
  /* The second operand of COND must be a suitable constant.  */
1319
  mode = GET_MODE (XEXP (cond, 0));
1320
  cst = XEXP (cond, 1);
1321
 
1322
  /* We can't perform this optimization if either operand might be or might
1323
     contain a signed zero.  */
1324
  if (HONOR_SIGNED_ZEROS (mode))
1325
    {
1326
      /* It is sufficient to check if CST is or contains a zero.  We must
1327
         handle float, complex, and vector.  If any subpart is a zero, then
1328
         the optimization can't be performed.  */
1329
      /* ??? The complex and vector checks are not implemented yet.  We just
1330
         always return zero for them.  */
1331
      if (GET_CODE (cst) == CONST_DOUBLE)
1332
        {
1333
          REAL_VALUE_TYPE d;
1334
          REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
1335
          if (REAL_VALUES_EQUAL (d, dconst0))
1336
            return 0;
1337
        }
1338
      else
1339
        return 0;
1340
    }
1341
 
1342
  return cprop_constant_p (cst);
1343
}
1344
 
1345
/* Find the implicit sets of a function.  An "implicit set" is a constraint
1346
   on the value of a variable, implied by a conditional jump.  For example,
1347
   following "if (x == 2)", the then branch may be optimized as though the
1348
   conditional performed an "explicit set", in this example, "x = 2".  This
1349
   function records the set patterns that are implicit at the start of each
1350
   basic block.
1351
 
1352
   If an implicit set is found but the set is implicit on a critical edge,
1353
   this critical edge is split.
1354
 
1355
   Return true if the CFG was modified, false otherwise.  */
1356
 
1357
static bool
1358
find_implicit_sets (void)
1359
{
1360
  basic_block bb, dest;
1361
  rtx cond, new_rtx;
1362
  unsigned int count = 0;
1363
  bool edges_split = false;
1364
  size_t implicit_sets_size = last_basic_block + 10;
1365
 
1366
  implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
1367
 
1368
  FOR_EACH_BB (bb)
1369
    {
1370
      /* Check for more than one successor.  */
1371
      if (EDGE_COUNT (bb->succs) <= 1)
1372
        continue;
1373
 
1374
      cond = fis_get_condition (BB_END (bb));
1375
 
1376
      /* If no condition is found or if it isn't of a suitable form,
1377
         ignore it.  */
1378
      if (! cond || ! implicit_set_cond_p (cond))
1379
        continue;
1380
 
1381
      dest = GET_CODE (cond) == EQ
1382
        ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
1383
 
1384
      /* If DEST doesn't go anywhere, ignore it.  */
1385
      if (! dest || dest == EXIT_BLOCK_PTR)
1386
        continue;
1387
 
1388
      /* We have found a suitable implicit set.  Try to record it now as
1389
         a SET in DEST.  If DEST has more than one predecessor, the edge
1390
         between BB and DEST is a critical edge and we must split it,
1391
         because we can only record one implicit set per DEST basic block.  */
1392
      if (! single_pred_p (dest))
1393
        {
1394
          dest = split_edge (find_edge (bb, dest));
1395
          edges_split = true;
1396
        }
1397
 
1398
      if (implicit_sets_size <= (size_t) dest->index)
1399
      {
1400
        size_t old_implicit_sets_size = implicit_sets_size;
1401
        implicit_sets_size *= 2;
1402
        implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
1403
        memset (implicit_sets + old_implicit_sets_size, 0,
1404
                (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
1405
      }
1406
 
1407
      new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
1408
                             XEXP (cond, 1));
1409
      implicit_sets[dest->index] = new_rtx;
1410
      if (dump_file)
1411
        {
1412
          fprintf(dump_file, "Implicit set of reg %d in ",
1413
                  REGNO (XEXP (cond, 0)));
1414
          fprintf(dump_file, "basic block %d\n", dest->index);
1415
        }
1416
      count++;
1417
    }
1418
 
1419
  if (dump_file)
1420
    fprintf (dump_file, "Found %d implicit sets\n", count);
1421
 
1422
  /* Confess our sins.  */
1423
  return edges_split;
1424
}
1425
 
1426
/* Bypass conditional jumps.  */
1427
 
1428
/* The value of last_basic_block at the beginning of the jump_bypass
1429
   pass.  The use of redirect_edge_and_branch_force may introduce new
1430
   basic blocks, but the data flow analysis is only valid for basic
1431
   block indices less than bypass_last_basic_block.  */
1432
 
1433
static int bypass_last_basic_block;
1434
 
1435
/* Find a set of REGNO to a constant that is available at the end of basic
1436
   block BB.  Return NULL if no such set is found.  Based heavily upon
1437
   find_avail_set.  */
1438
 
1439
static struct expr *
1440
find_bypass_set (int regno, int bb)
1441
{
1442
  struct expr *result = 0;
1443
 
1444
  for (;;)
1445
    {
1446
      rtx src;
1447
      struct expr *set = lookup_set (regno, &set_hash_table);
1448
 
1449
      while (set)
1450
        {
1451
          if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
1452
            break;
1453
          set = next_set (regno, set);
1454
        }
1455
 
1456
      if (set == 0)
1457
        break;
1458
 
1459
      src = set->src;
1460
      if (cprop_constant_p (src))
1461
        result = set;
1462
 
1463
      if (! REG_P (src))
1464
        break;
1465
 
1466
      regno = REGNO (src);
1467
    }
1468
  return result;
1469
}
1470
 
1471
/* Subroutine of bypass_block that checks whether a pseudo is killed by
1472
   any of the instructions inserted on an edge.  Jump bypassing places
1473
   condition code setters on CFG edges using insert_insn_on_edge.  This
1474
   function is required to check that our data flow analysis is still
1475
   valid prior to commit_edge_insertions.  */
1476
 
1477
static bool
1478
reg_killed_on_edge (const_rtx reg, const_edge e)
1479
{
1480
  rtx insn;
1481
 
1482
  for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
1483
    if (INSN_P (insn) && reg_set_p (reg, insn))
1484
      return true;
1485
 
1486
  return false;
1487
}
1488
 
1489
/* Subroutine of bypass_conditional_jumps that attempts to bypass the given
1490
   basic block BB which has more than one predecessor.  If not NULL, SETCC
1491
   is the first instruction of BB, which is immediately followed by JUMP_INSN
1492
   JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
1493
   Returns nonzero if a change was made.
1494
 
1495
   During the jump bypassing pass, we may place copies of SETCC instructions
1496
   on CFG edges.  The following routine must be careful to pay attention to
1497
   these inserted insns when performing its transformations.  */
1498
 
1499
static int
1500
bypass_block (basic_block bb, rtx setcc, rtx jump)
1501
{
1502
  rtx insn, note;
1503
  edge e, edest;
1504
  int change;
1505
  int may_be_loop_header;
1506
  unsigned removed_p;
1507
  unsigned i;
1508
  edge_iterator ei;
1509
 
1510
  insn = (setcc != NULL) ? setcc : jump;
1511
 
1512
  /* Determine set of register uses in INSN.  */
1513
  reg_use_count = 0;
1514
  note_uses (&PATTERN (insn), find_used_regs, NULL);
1515
  note = find_reg_equal_equiv_note (insn);
1516
  if (note)
1517
    find_used_regs (&XEXP (note, 0), NULL);
1518
 
1519
  may_be_loop_header = false;
1520
  FOR_EACH_EDGE (e, ei, bb->preds)
1521
    if (e->flags & EDGE_DFS_BACK)
1522
      {
1523
        may_be_loop_header = true;
1524
        break;
1525
      }
1526
 
1527
  change = 0;
1528
  for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
1529
    {
1530
      removed_p = 0;
1531
 
1532
      if (e->flags & EDGE_COMPLEX)
1533
        {
1534
          ei_next (&ei);
1535
          continue;
1536
        }
1537
 
1538
      /* We can't redirect edges from new basic blocks.  */
1539
      if (e->src->index >= bypass_last_basic_block)
1540
        {
1541
          ei_next (&ei);
1542
          continue;
1543
        }
1544
 
1545
      /* The irreducible loops created by redirecting of edges entering the
1546
         loop from outside would decrease effectiveness of some of the
1547
         following optimizations, so prevent this.  */
1548
      if (may_be_loop_header
1549
          && !(e->flags & EDGE_DFS_BACK))
1550
        {
1551
          ei_next (&ei);
1552
          continue;
1553
        }
1554
 
1555
      for (i = 0; i < reg_use_count; i++)
1556
        {
1557
          rtx reg_used = reg_use_table[i];
1558
          unsigned int regno = REGNO (reg_used);
1559
          basic_block dest, old_dest;
1560
          struct expr *set;
1561
          rtx src, new_rtx;
1562
 
1563
          set = find_bypass_set (regno, e->src->index);
1564
 
1565
          if (! set)
1566
            continue;
1567
 
1568
          /* Check the data flow is valid after edge insertions.  */
1569
          if (e->insns.r && reg_killed_on_edge (reg_used, e))
1570
            continue;
1571
 
1572
          src = SET_SRC (pc_set (jump));
1573
 
1574
          if (setcc != NULL)
1575
            src = simplify_replace_rtx (src,
1576
                                        SET_DEST (PATTERN (setcc)),
1577
                                        SET_SRC (PATTERN (setcc)));
1578
 
1579
          new_rtx = simplify_replace_rtx (src, reg_used, set->src);
1580
 
1581
          /* Jump bypassing may have already placed instructions on
1582
             edges of the CFG.  We can't bypass an outgoing edge that
1583
             has instructions associated with it, as these insns won't
1584
             get executed if the incoming edge is redirected.  */
1585
          if (new_rtx == pc_rtx)
1586
            {
1587
              edest = FALLTHRU_EDGE (bb);
1588
              dest = edest->insns.r ? NULL : edest->dest;
1589
            }
1590
          else if (GET_CODE (new_rtx) == LABEL_REF)
1591
            {
1592
              dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
1593
              /* Don't bypass edges containing instructions.  */
1594
              edest = find_edge (bb, dest);
1595
              if (edest && edest->insns.r)
1596
                dest = NULL;
1597
            }
1598
          else
1599
            dest = NULL;
1600
 
1601
          /* Avoid unification of the edge with other edges from original
1602
             branch.  We would end up emitting the instruction on "both"
1603
             edges.  */
1604
          if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
1605
              && find_edge (e->src, dest))
1606
            dest = NULL;
1607
 
1608
          old_dest = e->dest;
1609
          if (dest != NULL
1610
              && dest != old_dest
1611
              && dest != EXIT_BLOCK_PTR)
1612
            {
1613
              redirect_edge_and_branch_force (e, dest);
1614
 
1615
              /* Copy the register setter to the redirected edge.
1616
                 Don't copy CC0 setters, as CC0 is dead after jump.  */
1617
              if (setcc)
1618
                {
1619
                  rtx pat = PATTERN (setcc);
1620
                  if (!CC0_P (SET_DEST (pat)))
1621
                    insert_insn_on_edge (copy_insn (pat), e);
1622
                }
1623
 
1624
              if (dump_file != NULL)
1625
                {
1626
                  fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
1627
                                      "in jump_insn %d equals constant ",
1628
                           regno, INSN_UID (jump));
1629
                  print_rtl (dump_file, set->src);
1630
                  fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
1631
                           e->src->index, old_dest->index, dest->index);
1632
                }
1633
              change = 1;
1634
              removed_p = 1;
1635
              break;
1636
            }
1637
        }
1638
      if (!removed_p)
1639
        ei_next (&ei);
1640
    }
1641
  return change;
1642
}
1643
 
1644
/* Find basic blocks with more than one predecessor that only contain a
1645
   single conditional jump.  If the result of the comparison is known at
1646
   compile-time from any incoming edge, redirect that edge to the
1647
   appropriate target.  Return nonzero if a change was made.
1648
 
1649
   This function is now mis-named, because we also handle indirect jumps.  */
1650
 
1651
static int
1652
bypass_conditional_jumps (void)
1653
{
1654
  basic_block bb;
1655
  int changed;
1656
  rtx setcc;
1657
  rtx insn;
1658
  rtx dest;
1659
 
1660
  /* Note we start at block 1.  */
1661
  if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
1662
    return 0;
1663
 
1664
  bypass_last_basic_block = last_basic_block;
1665
  mark_dfs_back_edges ();
1666
 
1667
  changed = 0;
1668
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
1669
                  EXIT_BLOCK_PTR, next_bb)
1670
    {
1671
      /* Check for more than one predecessor.  */
1672
      if (!single_pred_p (bb))
1673
        {
1674
          setcc = NULL_RTX;
1675
          FOR_BB_INSNS (bb, insn)
1676
            if (DEBUG_INSN_P (insn))
1677
              continue;
1678
            else if (NONJUMP_INSN_P (insn))
1679
              {
1680
                if (setcc)
1681
                  break;
1682
                if (GET_CODE (PATTERN (insn)) != SET)
1683
                  break;
1684
 
1685
                dest = SET_DEST (PATTERN (insn));
1686
                if (REG_P (dest) || CC0_P (dest))
1687
                  setcc = insn;
1688
                else
1689
                  break;
1690
              }
1691
            else if (JUMP_P (insn))
1692
              {
1693
                if ((any_condjump_p (insn) || computed_jump_p (insn))
1694
                    && onlyjump_p (insn))
1695
                  changed |= bypass_block (bb, setcc, insn);
1696
                break;
1697
              }
1698
            else if (INSN_P (insn))
1699
              break;
1700
        }
1701
    }
1702
 
1703
  /* If we bypassed any register setting insns, we inserted a
1704
     copy on the redirected edge.  These need to be committed.  */
1705
  if (changed)
1706
    commit_edge_insertions ();
1707
 
1708
  return changed;
1709
}
1710
 
1711
/* Return true if the graph is too expensive to optimize.  PASS is the
1712
   optimization about to be performed.  */
1713
 
1714
static bool
1715
is_too_expensive (const char *pass)
1716
{
1717
  /* Trying to perform global optimizations on flow graphs which have
1718
     a high connectivity will take a long time and is unlikely to be
1719
     particularly useful.
1720
 
1721
     In normal circumstances a cfg should have about twice as many
1722
     edges as blocks.  But we do not want to punish small functions
1723
     which have a couple switch statements.  Rather than simply
1724
     threshold the number of blocks, uses something with a more
1725
     graceful degradation.  */
1726
  if (n_edges > 20000 + n_basic_blocks * 4)
1727
    {
1728
      warning (OPT_Wdisabled_optimization,
1729
               "%s: %d basic blocks and %d edges/basic block",
1730
               pass, n_basic_blocks, n_edges / n_basic_blocks);
1731
 
1732
      return true;
1733
    }
1734
 
1735
  /* If allocating memory for the cprop bitmap would take up too much
1736
     storage it's better just to disable the optimization.  */
1737
  if ((n_basic_blocks
1738
       * SBITMAP_SET_SIZE (max_reg_num ())
1739
       * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
1740
    {
1741
      warning (OPT_Wdisabled_optimization,
1742
               "%s: %d basic blocks and %d registers",
1743
               pass, n_basic_blocks, max_reg_num ());
1744
 
1745
      return true;
1746
    }
1747
 
1748
  return false;
1749
}
1750
 
1751
/* Main function for the CPROP pass.  */
1752
 
1753
static int
1754
one_cprop_pass (void)
1755
{
1756
  int i;
1757
  int changed = 0;
1758
 
1759
  /* Return if there's nothing to do, or it is too expensive.  */
1760
  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
1761
      || is_too_expensive (_ ("const/copy propagation disabled")))
1762
    return 0;
1763
 
1764
  global_const_prop_count = local_const_prop_count = 0;
1765
  global_copy_prop_count = local_copy_prop_count = 0;
1766
 
1767
  bytes_used = 0;
1768
  gcc_obstack_init (&cprop_obstack);
1769
 
1770
  /* Do a local const/copy propagation pass first.  The global pass
1771
     only handles global opportunities.
1772
     If the local pass changes something, remove any unreachable blocks
1773
     because the CPROP global dataflow analysis may get into infinite
1774
     loops for CFGs with unreachable blocks.
1775
 
1776
     FIXME: This local pass should not be necessary after CSE (but for
1777
            some reason it still is).  It is also (proven) not necessary
1778
            to run the local pass right after FWPWOP.
1779
 
1780
     FIXME: The global analysis would not get into infinite loops if it
1781
            would use the DF solver (via df_simple_dataflow) instead of
1782
            the solver implemented in this file.  */
1783
  changed |= local_cprop_pass ();
1784
  if (changed)
1785
    delete_unreachable_blocks ();
1786
 
1787
  /* Determine implicit sets.  This may change the CFG (split critical
1788
     edges if that exposes an implicit set).
1789
     Note that find_implicit_sets() does not rely on up-to-date DF caches
1790
     so that we do not have to re-run df_analyze() even if local CPROP
1791
     changed something.
1792
     ??? This could run earlier so that any uncovered implicit sets
1793
         sets could be exploited in local_cprop_pass() also.  Later.  */
1794
  changed |= find_implicit_sets ();
1795
 
1796
  /* If local_cprop_pass() or find_implicit_sets() changed something,
1797
     run df_analyze() to bring all insn caches up-to-date, and to take
1798
     new basic blocks from edge splitting on the DF radar.
1799
     NB: This also runs the fast DCE pass, because execute_rtl_cprop
1800
     sets DF_LR_RUN_DCE.  */
1801
  if (changed)
1802
    df_analyze ();
1803
 
1804
  /* Initialize implicit_set_indexes array.  */
1805
  implicit_set_indexes = XNEWVEC (int, last_basic_block);
1806
  for (i = 0; i < last_basic_block; i++)
1807
    implicit_set_indexes[i] = -1;
1808
 
1809
  alloc_hash_table (&set_hash_table);
1810
  compute_hash_table (&set_hash_table);
1811
 
1812
  /* Free implicit_sets before peak usage.  */
1813
  free (implicit_sets);
1814
  implicit_sets = NULL;
1815
 
1816
  if (dump_file)
1817
    dump_hash_table (dump_file, "SET", &set_hash_table);
1818
  if (set_hash_table.n_elems > 0)
1819
    {
1820
      basic_block bb;
1821
      rtx insn;
1822
 
1823
      alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
1824
      compute_cprop_data ();
1825
 
1826
      free (implicit_set_indexes);
1827
      implicit_set_indexes = NULL;
1828
 
1829
      /* Allocate vars to track sets of regs.  */
1830
      reg_set_bitmap = ALLOC_REG_SET (NULL);
1831
 
1832
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR,
1833
                      next_bb)
1834
        {
1835
          /* Reset tables used to keep track of what's still valid [since
1836
             the start of the block].  */
1837
          reset_opr_set_tables ();
1838
 
1839
          FOR_BB_INSNS (bb, insn)
1840
            if (INSN_P (insn))
1841
              {
1842
                changed |= cprop_insn (insn);
1843
 
1844
                /* Keep track of everything modified by this insn.  */
1845
                /* ??? Need to be careful w.r.t. mods done to INSN.
1846
                       Don't call mark_oprs_set if we turned the
1847
                       insn into a NOTE, or deleted the insn.  */
1848
                if (! NOTE_P (insn) && ! INSN_DELETED_P (insn))
1849
                  mark_oprs_set (insn);
1850
              }
1851
        }
1852
 
1853
      changed |= bypass_conditional_jumps ();
1854
 
1855
      FREE_REG_SET (reg_set_bitmap);
1856
      free_cprop_mem ();
1857
    }
1858
  else
1859
    {
1860
      free (implicit_set_indexes);
1861
      implicit_set_indexes = NULL;
1862
    }
1863
 
1864
  free_hash_table (&set_hash_table);
1865
  obstack_free (&cprop_obstack, NULL);
1866
 
1867
  if (dump_file)
1868
    {
1869
      fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
1870
               current_function_name (), n_basic_blocks, bytes_used);
1871
      fprintf (dump_file, "%d local const props, %d local copy props, ",
1872
               local_const_prop_count, local_copy_prop_count);
1873
      fprintf (dump_file, "%d global const props, %d global copy props\n\n",
1874
               global_const_prop_count, global_copy_prop_count);
1875
    }
1876
 
1877
  return changed;
1878
}
1879
 
1880
/* All the passes implemented in this file.  Each pass has its
1881
   own gate and execute function, and at the end of the file a
1882
   pass definition for passes.c.
1883
 
1884
   We do not construct an accurate cfg in functions which call
1885
   setjmp, so none of these passes runs if the function calls
1886
   setjmp.
1887
   FIXME: Should just handle setjmp via REG_SETJMP notes.  */
1888
 
1889
static bool
1890
gate_rtl_cprop (void)
1891
{
1892
  return optimize > 0 && flag_gcse
1893
    && !cfun->calls_setjmp
1894
    && dbg_cnt (cprop);
1895
}
1896
 
1897
static unsigned int
1898
execute_rtl_cprop (void)
1899
{
1900
  int changed;
1901
  delete_unreachable_blocks ();
1902
  df_set_flags (DF_LR_RUN_DCE);
1903
  df_analyze ();
1904
  changed = one_cprop_pass ();
1905
  flag_rerun_cse_after_global_opts |= changed;
1906
  if (changed)
1907
    cleanup_cfg (0);
1908
  return 0;
1909
}
1910
 
1911
struct rtl_opt_pass pass_rtl_cprop =
1912
{
1913
 {
1914
  RTL_PASS,
1915
  "cprop",                              /* name */
1916
  gate_rtl_cprop,                       /* gate */
1917
  execute_rtl_cprop,                    /* execute */
1918
  NULL,                                 /* sub */
1919
  NULL,                                 /* next */
1920
  0,                                    /* static_pass_number */
1921
  TV_CPROP,                             /* tv_id */
1922
  PROP_cfglayout,                       /* properties_required */
1923
  0,                                    /* properties_provided */
1924
  0,                                    /* properties_destroyed */
1925
  0,                                    /* todo_flags_start */
1926
  TODO_df_finish | TODO_verify_rtl_sharing |
1927
  TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
1928
 }
1929
};

powered by: WebSVN 2.1.0

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