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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [flow.c] - Blame information for rev 820

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

Line No. Rev Author Line
1 38 julius
/* Data flow analysis for GNU compiler.
2
   Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3
   1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
4
   Free Software Foundation, Inc.
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify it under
9
the terms of the GNU General Public License as published by the Free
10
Software Foundation; either version 3, or (at your option) any later
11
version.
12
 
13
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14
WARRANTY; without even the implied warranty of MERCHANTABILITY or
15
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
16
for more details.
17
 
18
You should have received a copy of the GNU General Public License
19
along with GCC; see the file COPYING3.  If not see
20
<http://www.gnu.org/licenses/>.  */
21
 
22
/* This file contains the data flow analysis pass of the compiler.  It
23
   computes data flow information which tells combine_instructions
24
   which insns to consider combining and controls register allocation.
25
 
26
   Additional data flow information that is too bulky to record is
27
   generated during the analysis, and is used at that time to create
28
   autoincrement and autodecrement addressing.
29
 
30
   The first step is dividing the function into basic blocks.
31
   find_basic_blocks does this.  Then life_analysis determines
32
   where each register is live and where it is dead.
33
 
34
   ** find_basic_blocks **
35
 
36
   find_basic_blocks divides the current function's rtl into basic
37
   blocks and constructs the CFG.  The blocks are recorded in the
38
   basic_block_info array; the CFG exists in the edge structures
39
   referenced by the blocks.
40
 
41
   find_basic_blocks also finds any unreachable loops and deletes them.
42
 
43
   ** life_analysis **
44
 
45
   life_analysis is called immediately after find_basic_blocks.
46
   It uses the basic block information to determine where each
47
   hard or pseudo register is live.
48
 
49
   ** live-register info **
50
 
51
   The information about where each register is live is in two parts:
52
   the REG_NOTES of insns, and the vector basic_block->global_live_at_start.
53
 
54
   basic_block->global_live_at_start has an element for each basic
55
   block, and the element is a bit-vector with a bit for each hard or
56
   pseudo register.  The bit is 1 if the register is live at the
57
   beginning of the basic block.
58
 
59
   Two types of elements can be added to an insn's REG_NOTES.
60
   A REG_DEAD note is added to an insn's REG_NOTES for any register
61
   that meets both of two conditions:  The value in the register is not
62
   needed in subsequent insns and the insn does not replace the value in
63
   the register (in the case of multi-word hard registers, the value in
64
   each register must be replaced by the insn to avoid a REG_DEAD note).
65
 
66
   In the vast majority of cases, an object in a REG_DEAD note will be
67
   used somewhere in the insn.  The (rare) exception to this is if an
68
   insn uses a multi-word hard register and only some of the registers are
69
   needed in subsequent insns.  In that case, REG_DEAD notes will be
70
   provided for those hard registers that are not subsequently needed.
71
   Partial REG_DEAD notes of this type do not occur when an insn sets
72
   only some of the hard registers used in such a multi-word operand;
73
   omitting REG_DEAD notes for objects stored in an insn is optional and
74
   the desire to do so does not justify the complexity of the partial
75
   REG_DEAD notes.
76
 
77
   REG_UNUSED notes are added for each register that is set by the insn
78
   but is unused subsequently (if every register set by the insn is unused
79
   and the insn does not reference memory or have some other side-effect,
80
   the insn is deleted instead).  If only part of a multi-word hard
81
   register is used in a subsequent insn, REG_UNUSED notes are made for
82
   the parts that will not be used.
83
 
84
   To determine which registers are live after any insn, one can
85
   start from the beginning of the basic block and scan insns, noting
86
   which registers are set by each insn and which die there.
87
 
88
   ** Other actions of life_analysis **
89
 
90
   life_analysis sets up the LOG_LINKS fields of insns because the
91
   information needed to do so is readily available.
92
 
93
   life_analysis deletes insns whose only effect is to store a value
94
   that is never used.
95
 
96
   life_analysis notices cases where a reference to a register as
97
   a memory address can be combined with a preceding or following
98
   incrementation or decrementation of the register.  The separate
99
   instruction to increment or decrement is deleted and the address
100
   is changed to a POST_INC or similar rtx.
101
 
102
   Each time an incrementing or decrementing address is created,
103
   a REG_INC element is added to the insn's REG_NOTES list.
104
 
105
   life_analysis fills in certain vectors containing information about
106
   register usage: REG_N_REFS, REG_N_DEATHS, REG_N_SETS, REG_LIVE_LENGTH,
107
   REG_N_CALLS_CROSSED, REG_N_THROWING_CALLS_CROSSED and REG_BASIC_BLOCK.
108
 
109
   life_analysis sets current_function_sp_is_unchanging if the function
110
   doesn't modify the stack pointer.  */
111
 
112
/* TODO:
113
 
114
   Split out from life_analysis:
115
        - local property discovery
116
        - global property computation
117
        - log links creation
118
        - pre/post modify transformation
119
*/
120
 
121
#include "config.h"
122
#include "system.h"
123
#include "coretypes.h"
124
#include "tm.h"
125
#include "tree.h"
126
#include "rtl.h"
127
#include "tm_p.h"
128
#include "hard-reg-set.h"
129
#include "basic-block.h"
130
#include "insn-config.h"
131
#include "regs.h"
132
#include "flags.h"
133
#include "output.h"
134
#include "function.h"
135
#include "except.h"
136
#include "toplev.h"
137
#include "recog.h"
138
#include "expr.h"
139
#include "timevar.h"
140
 
141
#include "obstack.h"
142
#include "splay-tree.h"
143
#include "tree-pass.h"
144
#include "params.h"
145
 
146
#ifndef HAVE_epilogue
147
#define HAVE_epilogue 0
148
#endif
149
#ifndef HAVE_prologue
150
#define HAVE_prologue 0
151
#endif
152
#ifndef HAVE_sibcall_epilogue
153
#define HAVE_sibcall_epilogue 0
154
#endif
155
 
156
#ifndef EPILOGUE_USES
157
#define EPILOGUE_USES(REGNO)  0
158
#endif
159
#ifndef EH_USES
160
#define EH_USES(REGNO)  0
161
#endif
162
 
163
#ifdef HAVE_conditional_execution
164
#ifndef REVERSE_CONDEXEC_PREDICATES_P
165
#define REVERSE_CONDEXEC_PREDICATES_P(x, y) \
166
  (GET_CODE ((x)) == reversed_comparison_code ((y), NULL))
167
#endif
168
#endif
169
 
170
/* This is the maximum number of times we process any given block if the
171
   latest loop depth count is smaller than this number.  Only used for the
172
   failure strategy to avoid infinite loops in calculate_global_regs_live.  */
173
#define MAX_LIVENESS_ROUNDS 20
174
 
175
/* Nonzero if the second flow pass has completed.  */
176
int flow2_completed;
177
 
178
/* Maximum register number used in this function, plus one.  */
179
 
180
int max_regno;
181
 
182
/* Indexed by n, giving various register information */
183
 
184
VEC(reg_info_p,heap) *reg_n_info;
185
 
186
/* Regset of regs live when calls to `setjmp'-like functions happen.  */
187
/* ??? Does this exist only for the setjmp-clobbered warning message?  */
188
 
189
static regset regs_live_at_setjmp;
190
 
191
/* List made of EXPR_LIST rtx's which gives pairs of pseudo registers
192
   that have to go in the same hard reg.
193
   The first two regs in the list are a pair, and the next two
194
   are another pair, etc.  */
195
rtx regs_may_share;
196
 
197
/* Set of registers that may be eliminable.  These are handled specially
198
   in updating regs_ever_live.  */
199
 
200
static HARD_REG_SET elim_reg_set;
201
 
202
/* Holds information for tracking conditional register life information.  */
203
struct reg_cond_life_info
204
{
205
  /* A boolean expression of conditions under which a register is dead.  */
206
  rtx condition;
207
  /* Conditions under which a register is dead at the basic block end.  */
208
  rtx orig_condition;
209
 
210
  /* A boolean expression of conditions under which a register has been
211
     stored into.  */
212
  rtx stores;
213
 
214
  /* ??? Could store mask of bytes that are dead, so that we could finally
215
     track lifetimes of multi-word registers accessed via subregs.  */
216
};
217
 
218
/* For use in communicating between propagate_block and its subroutines.
219
   Holds all information needed to compute life and def-use information.  */
220
 
221
struct propagate_block_info
222
{
223
  /* The basic block we're considering.  */
224
  basic_block bb;
225
 
226
  /* Bit N is set if register N is conditionally or unconditionally live.  */
227
  regset reg_live;
228
 
229
  /* Bit N is set if register N is set this insn.  */
230
  regset new_set;
231
 
232
  /* Element N is the next insn that uses (hard or pseudo) register N
233
     within the current basic block; or zero, if there is no such insn.  */
234
  rtx *reg_next_use;
235
 
236
  /* Contains a list of all the MEMs we are tracking for dead store
237
     elimination.  */
238
  rtx mem_set_list;
239
 
240
  /* If non-null, record the set of registers set unconditionally in the
241
     basic block.  */
242
  regset local_set;
243
 
244
  /* If non-null, record the set of registers set conditionally in the
245
     basic block.  */
246
  regset cond_local_set;
247
 
248
#ifdef HAVE_conditional_execution
249
  /* Indexed by register number, holds a reg_cond_life_info for each
250
     register that is not unconditionally live or dead.  */
251
  splay_tree reg_cond_dead;
252
 
253
  /* Bit N is set if register N is in an expression in reg_cond_dead.  */
254
  regset reg_cond_reg;
255
#endif
256
 
257
  /* The length of mem_set_list.  */
258
  int mem_set_list_len;
259
 
260
  /* Nonzero if the value of CC0 is live.  */
261
  int cc0_live;
262
 
263
  /* Flags controlling the set of information propagate_block collects.  */
264
  int flags;
265
  /* Index of instruction being processed.  */
266
  int insn_num;
267
};
268
 
269
/* Number of dead insns removed.  */
270
static int ndead;
271
 
272
/* When PROP_REG_INFO set, array contains pbi->insn_num of instruction
273
   where given register died.  When the register is marked alive, we use the
274
   information to compute amount of instructions life range cross.
275
   (remember, we are walking backward).  This can be computed as current
276
   pbi->insn_num - reg_deaths[regno].
277
   At the end of processing each basic block, the remaining live registers
278
   are inspected and live ranges are increased same way so liverange of global
279
   registers are computed correctly.
280
 
281
   The array is maintained clear for dead registers, so it can be safely reused
282
   for next basic block without expensive memset of the whole array after
283
   reseting pbi->insn_num to 0.  */
284
 
285
static int *reg_deaths;
286
 
287
/* Forward declarations */
288
static int verify_wide_reg_1 (rtx *, void *);
289
static void verify_wide_reg (int, basic_block);
290
static void verify_local_live_at_start (regset, basic_block);
291
static void notice_stack_pointer_modification_1 (rtx, rtx, void *);
292
static void notice_stack_pointer_modification (void);
293
static void mark_reg (rtx, void *);
294
static void mark_regs_live_at_end (regset);
295
static void calculate_global_regs_live (sbitmap, sbitmap, int);
296
static void propagate_block_delete_insn (rtx);
297
static rtx propagate_block_delete_libcall (rtx, rtx);
298
static int insn_dead_p (struct propagate_block_info *, rtx, int, rtx);
299
static int libcall_dead_p (struct propagate_block_info *, rtx, rtx);
300
static void mark_set_regs (struct propagate_block_info *, rtx, rtx);
301
static void mark_set_1 (struct propagate_block_info *, enum rtx_code, rtx,
302
                        rtx, rtx, int);
303
static int find_regno_partial (rtx *, void *);
304
 
305
#ifdef HAVE_conditional_execution
306
static int mark_regno_cond_dead (struct propagate_block_info *, int, rtx);
307
static void free_reg_cond_life_info (splay_tree_value);
308
static int flush_reg_cond_reg_1 (splay_tree_node, void *);
309
static void flush_reg_cond_reg (struct propagate_block_info *, int);
310
static rtx elim_reg_cond (rtx, unsigned int);
311
static rtx ior_reg_cond (rtx, rtx, int);
312
static rtx not_reg_cond (rtx);
313
static rtx and_reg_cond (rtx, rtx, int);
314
#endif
315
#ifdef AUTO_INC_DEC
316
static void attempt_auto_inc (struct propagate_block_info *, rtx, rtx, rtx,
317
                              rtx, rtx);
318
static void find_auto_inc (struct propagate_block_info *, rtx, rtx);
319
static int try_pre_increment_1 (struct propagate_block_info *, rtx);
320
static int try_pre_increment (rtx, rtx, HOST_WIDE_INT);
321
#endif
322
static void mark_used_reg (struct propagate_block_info *, rtx, rtx, rtx);
323
static void mark_used_regs (struct propagate_block_info *, rtx, rtx, rtx);
324
void debug_flow_info (void);
325
static void add_to_mem_set_list (struct propagate_block_info *, rtx);
326
static int invalidate_mems_from_autoinc (rtx *, void *);
327
static void invalidate_mems_from_set (struct propagate_block_info *, rtx);
328
static void clear_log_links (sbitmap);
329
static int count_or_remove_death_notes_bb (basic_block, int);
330
static void allocate_bb_life_data (void);
331
 
332
/* Return the INSN immediately following the NOTE_INSN_BASIC_BLOCK
333
   note associated with the BLOCK.  */
334
 
335
rtx
336
first_insn_after_basic_block_note (basic_block block)
337
{
338
  rtx insn;
339
 
340
  /* Get the first instruction in the block.  */
341
  insn = BB_HEAD (block);
342
 
343
  if (insn == NULL_RTX)
344
    return NULL_RTX;
345
  if (LABEL_P (insn))
346
    insn = NEXT_INSN (insn);
347
  gcc_assert (NOTE_INSN_BASIC_BLOCK_P (insn));
348
 
349
  return NEXT_INSN (insn);
350
}
351
 
352
/* Perform data flow analysis for the whole control flow graph.
353
   FLAGS is a set of PROP_* flags to be used in accumulating flow info.  */
354
 
355
void
356
life_analysis (int flags)
357
{
358
#ifdef ELIMINABLE_REGS
359
  int i;
360
  static const struct {const int from, to; } eliminables[] = ELIMINABLE_REGS;
361
#endif
362
 
363
  /* Record which registers will be eliminated.  We use this in
364
     mark_used_regs.  */
365
 
366
  CLEAR_HARD_REG_SET (elim_reg_set);
367
 
368
#ifdef ELIMINABLE_REGS
369
  for (i = 0; i < (int) ARRAY_SIZE (eliminables); i++)
370
    SET_HARD_REG_BIT (elim_reg_set, eliminables[i].from);
371
#else
372
  SET_HARD_REG_BIT (elim_reg_set, FRAME_POINTER_REGNUM);
373
#endif
374
 
375
 
376
#ifdef CANNOT_CHANGE_MODE_CLASS
377
  if (flags & PROP_REG_INFO)
378
    init_subregs_of_mode ();
379
#endif
380
 
381
  if (! optimize)
382
    flags &= ~(PROP_LOG_LINKS | PROP_AUTOINC | PROP_ALLOW_CFG_CHANGES);
383
 
384
  /* The post-reload life analysis have (on a global basis) the same
385
     registers live as was computed by reload itself.  elimination
386
     Otherwise offsets and such may be incorrect.
387
 
388
     Reload will make some registers as live even though they do not
389
     appear in the rtl.
390
 
391
     We don't want to create new auto-incs after reload, since they
392
     are unlikely to be useful and can cause problems with shared
393
     stack slots.  */
394
  if (reload_completed)
395
    flags &= ~(PROP_REG_INFO | PROP_AUTOINC);
396
 
397
  /* We want alias analysis information for local dead store elimination.  */
398
  if (optimize && (flags & PROP_SCAN_DEAD_STORES))
399
    init_alias_analysis ();
400
 
401
  /* Always remove no-op moves.  Do this before other processing so
402
     that we don't have to keep re-scanning them.  */
403
  delete_noop_moves ();
404
 
405
  /* Some targets can emit simpler epilogues if they know that sp was
406
     not ever modified during the function.  After reload, of course,
407
     we've already emitted the epilogue so there's no sense searching.  */
408
  if (! reload_completed)
409
    notice_stack_pointer_modification ();
410
 
411
  /* Allocate and zero out data structures that will record the
412
     data from lifetime analysis.  */
413
  allocate_reg_life_data ();
414
  allocate_bb_life_data ();
415
 
416
  /* Find the set of registers live on function exit.  */
417
  mark_regs_live_at_end (EXIT_BLOCK_PTR->il.rtl->global_live_at_start);
418
 
419
  /* "Update" life info from zero.  It'd be nice to begin the
420
     relaxation with just the exit and noreturn blocks, but that set
421
     is not immediately handy.  */
422
 
423
  if (flags & PROP_REG_INFO)
424
    {
425
      memset (regs_ever_live, 0, sizeof (regs_ever_live));
426
      memset (regs_asm_clobbered, 0, sizeof (regs_asm_clobbered));
427
    }
428
  update_life_info (NULL, UPDATE_LIFE_GLOBAL, flags);
429
  if (reg_deaths)
430
    {
431
      free (reg_deaths);
432
      reg_deaths = NULL;
433
    }
434
 
435
  /* Clean up.  */
436
  if (optimize && (flags & PROP_SCAN_DEAD_STORES))
437
    end_alias_analysis ();
438
 
439
  if (dump_file)
440
    dump_flow_info (dump_file, dump_flags);
441
 
442
  /* Removing dead insns should have made jumptables really dead.  */
443
  delete_dead_jumptables ();
444
}
445
 
446
/* A subroutine of verify_wide_reg, called through for_each_rtx.
447
   Search for REGNO.  If found, return 2 if it is not wider than
448
   word_mode.  */
449
 
450
static int
451
verify_wide_reg_1 (rtx *px, void *pregno)
452
{
453
  rtx x = *px;
454
  unsigned int regno = *(int *) pregno;
455
 
456
  if (REG_P (x) && REGNO (x) == regno)
457
    {
458
      if (GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD)
459
        return 2;
460
      return 1;
461
    }
462
  return 0;
463
}
464
 
465
/* A subroutine of verify_local_live_at_start.  Search through insns
466
   of BB looking for register REGNO.  */
467
 
468
static void
469
verify_wide_reg (int regno, basic_block bb)
470
{
471
  rtx head = BB_HEAD (bb), end = BB_END (bb);
472
 
473
  while (1)
474
    {
475
      if (INSN_P (head))
476
        {
477
          int r = for_each_rtx (&PATTERN (head), verify_wide_reg_1, &regno);
478
          if (r == 1)
479
            return;
480
          if (r == 2)
481
            break;
482
        }
483
      if (head == end)
484
        break;
485
      head = NEXT_INSN (head);
486
    }
487
  if (dump_file)
488
    {
489
      fprintf (dump_file, "Register %d died unexpectedly.\n", regno);
490
      dump_bb (bb, dump_file, 0);
491
    }
492
  internal_error ("internal consistency failure");
493
}
494
 
495
/* A subroutine of update_life_info.  Verify that there are no untoward
496
   changes in live_at_start during a local update.  */
497
 
498
static void
499
verify_local_live_at_start (regset new_live_at_start, basic_block bb)
500
{
501
  if (reload_completed)
502
    {
503
      /* After reload, there are no pseudos, nor subregs of multi-word
504
         registers.  The regsets should exactly match.  */
505
      if (! REG_SET_EQUAL_P (new_live_at_start,
506
                             bb->il.rtl->global_live_at_start))
507
        {
508
          if (dump_file)
509
            {
510
              fprintf (dump_file,
511
                       "live_at_start mismatch in bb %d, aborting\nNew:\n",
512
                       bb->index);
513
              debug_bitmap_file (dump_file, new_live_at_start);
514
              fputs ("Old:\n", dump_file);
515
              dump_bb (bb, dump_file, 0);
516
            }
517
          internal_error ("internal consistency failure");
518
        }
519
    }
520
  else
521
    {
522
      unsigned i;
523
      reg_set_iterator rsi;
524
 
525
      /* Find the set of changed registers.  */
526
      XOR_REG_SET (new_live_at_start, bb->il.rtl->global_live_at_start);
527
 
528
      EXECUTE_IF_SET_IN_REG_SET (new_live_at_start, 0, i, rsi)
529
        {
530
          /* No registers should die.  */
531
          if (REGNO_REG_SET_P (bb->il.rtl->global_live_at_start, i))
532
            {
533
              if (dump_file)
534
                {
535
                  fprintf (dump_file,
536
                           "Register %d died unexpectedly.\n", i);
537
                  dump_bb (bb, dump_file, 0);
538
                }
539
              internal_error ("internal consistency failure");
540
            }
541
          /* Verify that the now-live register is wider than word_mode.  */
542
          verify_wide_reg (i, bb);
543
        }
544
    }
545
}
546
 
547
/* Updates life information starting with the basic blocks set in BLOCKS.
548
   If BLOCKS is null, consider it to be the universal set.
549
 
550
   If EXTENT is UPDATE_LIFE_LOCAL, such as after splitting or peepholing,
551
   we are only expecting local modifications to basic blocks.  If we find
552
   extra registers live at the beginning of a block, then we either killed
553
   useful data, or we have a broken split that wants data not provided.
554
   If we find registers removed from live_at_start, that means we have
555
   a broken peephole that is killing a register it shouldn't.
556
 
557
   ??? This is not true in one situation -- when a pre-reload splitter
558
   generates subregs of a multi-word pseudo, current life analysis will
559
   lose the kill.  So we _can_ have a pseudo go live.  How irritating.
560
 
561
   It is also not true when a peephole decides that it doesn't need one
562
   or more of the inputs.
563
 
564
   Including PROP_REG_INFO does not properly refresh regs_ever_live
565
   unless the caller resets it to zero.  */
566
 
567
int
568
update_life_info (sbitmap blocks, enum update_life_extent extent,
569
                  int prop_flags)
570
{
571
  regset tmp;
572
  unsigned i = 0;
573
  int stabilized_prop_flags = prop_flags;
574
  basic_block bb;
575
 
576
  tmp = ALLOC_REG_SET (&reg_obstack);
577
  ndead = 0;
578
 
579
  if ((prop_flags & PROP_REG_INFO) && !reg_deaths)
580
    reg_deaths = XCNEWVEC (int, max_regno);
581
 
582
  timevar_push ((extent == UPDATE_LIFE_LOCAL || blocks)
583
                ? TV_LIFE_UPDATE : TV_LIFE);
584
 
585
  /* Changes to the CFG are only allowed when
586
     doing a global update for the entire CFG.  */
587
  gcc_assert (!(prop_flags & PROP_ALLOW_CFG_CHANGES)
588
              || (extent != UPDATE_LIFE_LOCAL && !blocks));
589
 
590
  /* For a global update, we go through the relaxation process again.  */
591
  if (extent != UPDATE_LIFE_LOCAL)
592
    {
593
      for ( ; ; )
594
        {
595
          int changed = 0;
596
 
597
          calculate_global_regs_live (blocks, blocks,
598
                                prop_flags & (PROP_SCAN_DEAD_CODE
599
                                              | PROP_SCAN_DEAD_STORES
600
                                              | PROP_ALLOW_CFG_CHANGES));
601
 
602
          if ((prop_flags & (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
603
              != (PROP_KILL_DEAD_CODE | PROP_ALLOW_CFG_CHANGES))
604
            break;
605
 
606
          /* Removing dead code may allow the CFG to be simplified which
607
             in turn may allow for further dead code detection / removal.  */
608
          FOR_EACH_BB_REVERSE (bb)
609
            {
610
              COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end);
611
              changed |= propagate_block (bb, tmp, NULL, NULL,
612
                                prop_flags & (PROP_SCAN_DEAD_CODE
613
                                              | PROP_SCAN_DEAD_STORES
614
                                              | PROP_KILL_DEAD_CODE));
615
            }
616
 
617
          /* Don't pass PROP_SCAN_DEAD_CODE or PROP_KILL_DEAD_CODE to
618
             subsequent propagate_block calls, since removing or acting as
619
             removing dead code can affect global register liveness, which
620
             is supposed to be finalized for this call after this loop.  */
621
          stabilized_prop_flags
622
            &= ~(PROP_SCAN_DEAD_CODE | PROP_SCAN_DEAD_STORES
623
                 | PROP_KILL_DEAD_CODE);
624
 
625
          if (! changed)
626
            break;
627
 
628
          /* We repeat regardless of what cleanup_cfg says.  If there were
629
             instructions deleted above, that might have been only a
630
             partial improvement (see PARAM_MAX_FLOW_MEMORY_LOCATIONS  usage).
631
             Further improvement may be possible.  */
632
          cleanup_cfg (CLEANUP_EXPENSIVE);
633
 
634
          /* Zap the life information from the last round.  If we don't
635
             do this, we can wind up with registers that no longer appear
636
             in the code being marked live at entry.  */
637
          FOR_EACH_BB (bb)
638
            {
639
              CLEAR_REG_SET (bb->il.rtl->global_live_at_start);
640
              CLEAR_REG_SET (bb->il.rtl->global_live_at_end);
641
            }
642
        }
643
 
644
      /* If asked, remove notes from the blocks we'll update.  */
645
      if (extent == UPDATE_LIFE_GLOBAL_RM_NOTES)
646
        count_or_remove_death_notes (blocks,
647
                                     prop_flags & PROP_POST_REGSTACK ? -1 : 1);
648
    }
649
  else
650
    {
651
      /* FIXME: This can go when the dataflow branch has been merged in.  */
652
      /* For a local update, if we are creating new REG_DEAD notes, then we
653
         must delete the old ones first to avoid conflicts if they are
654
         different.  */
655
      if (prop_flags & PROP_DEATH_NOTES)
656
        count_or_remove_death_notes (blocks,
657
                                     prop_flags & PROP_POST_REGSTACK ? -1 : 1);
658
    }
659
 
660
 
661
  /* Clear log links in case we are asked to (re)compute them.  */
662
  if (prop_flags & PROP_LOG_LINKS)
663
    clear_log_links (blocks);
664
 
665
  if (blocks)
666
    {
667
      sbitmap_iterator sbi;
668
 
669
      EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi)
670
        {
671
          bb = BASIC_BLOCK (i);
672
          if (bb)
673
            {
674
              /* The bitmap may be flawed in that one of the basic
675
                 blocks may have been deleted before you get here.  */
676
              COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end);
677
              propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
678
 
679
              if (extent == UPDATE_LIFE_LOCAL)
680
                verify_local_live_at_start (tmp, bb);
681
            }
682
        };
683
    }
684
  else
685
    {
686
      FOR_EACH_BB_REVERSE (bb)
687
        {
688
          COPY_REG_SET (tmp, bb->il.rtl->global_live_at_end);
689
 
690
          propagate_block (bb, tmp, NULL, NULL, stabilized_prop_flags);
691
 
692
          if (extent == UPDATE_LIFE_LOCAL)
693
            verify_local_live_at_start (tmp, bb);
694
        }
695
    }
696
 
697
  FREE_REG_SET (tmp);
698
 
699
  if (prop_flags & PROP_REG_INFO)
700
    {
701
      reg_set_iterator rsi;
702
 
703
      /* The only pseudos that are live at the beginning of the function
704
         are those that were not set anywhere in the function.  local-alloc
705
         doesn't know how to handle these correctly, so mark them as not
706
         local to any one basic block.  */
707
      EXECUTE_IF_SET_IN_REG_SET (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end,
708
                                 FIRST_PSEUDO_REGISTER, i, rsi)
709
        REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
710
 
711
      /* We have a problem with any pseudoreg that lives across the setjmp.
712
         ANSI says that if a user variable does not change in value between
713
         the setjmp and the longjmp, then the longjmp preserves it.  This
714
         includes longjmp from a place where the pseudo appears dead.
715
         (In principle, the value still exists if it is in scope.)
716
         If the pseudo goes in a hard reg, some other value may occupy
717
         that hard reg where this pseudo is dead, thus clobbering the pseudo.
718
         Conclusion: such a pseudo must not go in a hard reg.  */
719
      EXECUTE_IF_SET_IN_REG_SET (regs_live_at_setjmp,
720
                                 FIRST_PSEUDO_REGISTER, i, rsi)
721
        {
722
          if (regno_reg_rtx[i] != 0)
723
            {
724
              REG_LIVE_LENGTH (i) = -1;
725
              REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
726
            }
727
        }
728
    }
729
  if (reg_deaths)
730
    {
731
      free (reg_deaths);
732
      reg_deaths = NULL;
733
    }
734
  timevar_pop ((extent == UPDATE_LIFE_LOCAL || blocks)
735
               ? TV_LIFE_UPDATE : TV_LIFE);
736
  if (ndead && dump_file)
737
    fprintf (dump_file, "deleted %i dead insns\n", ndead);
738
  return ndead;
739
}
740
 
741
/* Update life information in all blocks where BB_DIRTY is set.  */
742
 
743
int
744
update_life_info_in_dirty_blocks (enum update_life_extent extent, int prop_flags)
745
{
746
  sbitmap update_life_blocks = sbitmap_alloc (last_basic_block);
747
  int n = 0;
748
  basic_block bb;
749
  int retval = 0;
750
 
751
  sbitmap_zero (update_life_blocks);
752
  FOR_EACH_BB (bb)
753
    {
754
      if (bb->flags & BB_DIRTY)
755
        {
756
          SET_BIT (update_life_blocks, bb->index);
757
          n++;
758
        }
759
    }
760
 
761
  if (n)
762
    retval = update_life_info (update_life_blocks, extent, prop_flags);
763
 
764
  sbitmap_free (update_life_blocks);
765
  return retval;
766
}
767
 
768
/* Free the variables allocated by find_basic_blocks.  */
769
 
770
void
771
free_basic_block_vars (void)
772
{
773
  if (basic_block_info)
774
    {
775
      clear_edges ();
776
      basic_block_info = NULL;
777
    }
778
  n_basic_blocks = 0;
779
  last_basic_block = 0;
780
  n_edges = 0;
781
 
782
  label_to_block_map = NULL;
783
 
784
  ENTRY_BLOCK_PTR->aux = NULL;
785
  ENTRY_BLOCK_PTR->il.rtl->global_live_at_end = NULL;
786
  EXIT_BLOCK_PTR->aux = NULL;
787
  EXIT_BLOCK_PTR->il.rtl->global_live_at_start = NULL;
788
}
789
 
790
/* Delete any insns that copy a register to itself.  */
791
 
792
int
793
delete_noop_moves (void)
794
{
795
  rtx insn, next;
796
  basic_block bb;
797
  int nnoops = 0;
798
 
799
  FOR_EACH_BB (bb)
800
    {
801
      for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb)); insn = next)
802
        {
803
          next = NEXT_INSN (insn);
804
          if (INSN_P (insn) && noop_move_p (insn))
805
            {
806
              rtx note;
807
 
808
              /* If we're about to remove the first insn of a libcall
809
                 then move the libcall note to the next real insn and
810
                 update the retval note.  */
811
              if ((note = find_reg_note (insn, REG_LIBCALL, NULL_RTX))
812
                       && XEXP (note, 0) != insn)
813
                {
814
                  rtx new_libcall_insn = next_real_insn (insn);
815
                  rtx retval_note = find_reg_note (XEXP (note, 0),
816
                                                   REG_RETVAL, NULL_RTX);
817
                  REG_NOTES (new_libcall_insn)
818
                    = gen_rtx_INSN_LIST (REG_LIBCALL, XEXP (note, 0),
819
                                         REG_NOTES (new_libcall_insn));
820
                  XEXP (retval_note, 0) = new_libcall_insn;
821
                }
822
 
823
              delete_insn_and_edges (insn);
824
              nnoops++;
825
            }
826
        }
827
    }
828
 
829
  if (nnoops && dump_file)
830
    fprintf (dump_file, "deleted %i noop moves\n", nnoops);
831
 
832
  return nnoops;
833
}
834
 
835
/* Delete any jump tables never referenced.  We can't delete them at the
836
   time of removing tablejump insn as they are referenced by the preceding
837
   insns computing the destination, so we delay deleting and garbagecollect
838
   them once life information is computed.  */
839
void
840
delete_dead_jumptables (void)
841
{
842
  basic_block bb;
843
 
844
  /* A dead jump table does not belong to any basic block.  Scan insns
845
     between two adjacent basic blocks.  */
846
  FOR_EACH_BB (bb)
847
    {
848
      rtx insn, next;
849
 
850
      for (insn = NEXT_INSN (BB_END (bb));
851
           insn && !NOTE_INSN_BASIC_BLOCK_P (insn);
852
           insn = next)
853
        {
854
          next = NEXT_INSN (insn);
855
          if (LABEL_P (insn)
856
              && LABEL_NUSES (insn) == LABEL_PRESERVE_P (insn)
857
              && JUMP_P (next)
858
              && (GET_CODE (PATTERN (next)) == ADDR_VEC
859
                  || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
860
            {
861
              rtx label = insn, jump = next;
862
 
863
              if (dump_file)
864
                fprintf (dump_file, "Dead jumptable %i removed\n",
865
                         INSN_UID (insn));
866
 
867
              next = NEXT_INSN (next);
868
              delete_insn (jump);
869
              delete_insn (label);
870
            }
871
        }
872
    }
873
}
874
 
875
/* Determine if the stack pointer is constant over the life of the function.
876
   Only useful before prologues have been emitted.  */
877
 
878
static void
879
notice_stack_pointer_modification_1 (rtx x, rtx pat ATTRIBUTE_UNUSED,
880
                                     void *data ATTRIBUTE_UNUSED)
881
{
882
  if (x == stack_pointer_rtx
883
      /* The stack pointer is only modified indirectly as the result
884
         of a push until later in flow.  See the comments in rtl.texi
885
         regarding Embedded Side-Effects on Addresses.  */
886
      || (MEM_P (x)
887
          && GET_RTX_CLASS (GET_CODE (XEXP (x, 0))) == RTX_AUTOINC
888
          && XEXP (XEXP (x, 0), 0) == stack_pointer_rtx))
889
    current_function_sp_is_unchanging = 0;
890
}
891
 
892
static void
893
notice_stack_pointer_modification (void)
894
{
895
  basic_block bb;
896
  rtx insn;
897
 
898
  /* Assume that the stack pointer is unchanging if alloca hasn't
899
     been used.  */
900
  current_function_sp_is_unchanging = !current_function_calls_alloca;
901
  if (! current_function_sp_is_unchanging)
902
    return;
903
 
904
  FOR_EACH_BB (bb)
905
    FOR_BB_INSNS (bb, insn)
906
      {
907
        if (INSN_P (insn))
908
          {
909
            /* Check if insn modifies the stack pointer.  */
910
            note_stores (PATTERN (insn),
911
                         notice_stack_pointer_modification_1,
912
                         NULL);
913
            if (! current_function_sp_is_unchanging)
914
              return;
915
          }
916
      }
917
}
918
 
919
/* Mark a register in SET.  Hard registers in large modes get all
920
   of their component registers set as well.  */
921
 
922
static void
923
mark_reg (rtx reg, void *xset)
924
{
925
  regset set = (regset) xset;
926
  int regno = REGNO (reg);
927
 
928
  gcc_assert (GET_MODE (reg) != BLKmode);
929
 
930
  SET_REGNO_REG_SET (set, regno);
931
  if (regno < FIRST_PSEUDO_REGISTER)
932
    {
933
      int n = hard_regno_nregs[regno][GET_MODE (reg)];
934
      while (--n > 0)
935
        SET_REGNO_REG_SET (set, regno + n);
936
    }
937
}
938
 
939
/* Mark those regs which are needed at the end of the function as live
940
   at the end of the last basic block.  */
941
 
942
static void
943
mark_regs_live_at_end (regset set)
944
{
945
  unsigned int i;
946
 
947
  /* If exiting needs the right stack value, consider the stack pointer
948
     live at the end of the function.  */
949
  if ((HAVE_epilogue && epilogue_completed)
950
      || ! EXIT_IGNORE_STACK
951
      || (! FRAME_POINTER_REQUIRED
952
          && ! current_function_calls_alloca
953
          && flag_omit_frame_pointer)
954
      || current_function_sp_is_unchanging)
955
    {
956
      SET_REGNO_REG_SET (set, STACK_POINTER_REGNUM);
957
    }
958
 
959
  /* Mark the frame pointer if needed at the end of the function.  If
960
     we end up eliminating it, it will be removed from the live list
961
     of each basic block by reload.  */
962
 
963
  if (! reload_completed || frame_pointer_needed)
964
    {
965
      SET_REGNO_REG_SET (set, FRAME_POINTER_REGNUM);
966
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
967
      /* If they are different, also mark the hard frame pointer as live.  */
968
      if (! LOCAL_REGNO (HARD_FRAME_POINTER_REGNUM))
969
        SET_REGNO_REG_SET (set, HARD_FRAME_POINTER_REGNUM);
970
#endif
971
    }
972
 
973
#ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED
974
  /* Many architectures have a GP register even without flag_pic.
975
     Assume the pic register is not in use, or will be handled by
976
     other means, if it is not fixed.  */
977
  if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
978
      && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
979
    SET_REGNO_REG_SET (set, PIC_OFFSET_TABLE_REGNUM);
980
#endif
981
 
982
  /* Mark all global registers, and all registers used by the epilogue
983
     as being live at the end of the function since they may be
984
     referenced by our caller.  */
985
  for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
986
    if (global_regs[i] || EPILOGUE_USES (i))
987
      SET_REGNO_REG_SET (set, i);
988
 
989
  if (HAVE_epilogue && epilogue_completed)
990
    {
991
      /* Mark all call-saved registers that we actually used.  */
992
      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
993
        if (regs_ever_live[i] && ! LOCAL_REGNO (i)
994
            && ! TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
995
          SET_REGNO_REG_SET (set, i);
996
    }
997
 
998
#ifdef EH_RETURN_DATA_REGNO
999
  /* Mark the registers that will contain data for the handler.  */
1000
  if (reload_completed && current_function_calls_eh_return)
1001
    for (i = 0; ; ++i)
1002
      {
1003
        unsigned regno = EH_RETURN_DATA_REGNO(i);
1004
        if (regno == INVALID_REGNUM)
1005
          break;
1006
        SET_REGNO_REG_SET (set, regno);
1007
      }
1008
#endif
1009
#ifdef EH_RETURN_STACKADJ_RTX
1010
  if ((! HAVE_epilogue || ! epilogue_completed)
1011
      && current_function_calls_eh_return)
1012
    {
1013
      rtx tmp = EH_RETURN_STACKADJ_RTX;
1014
      if (tmp && REG_P (tmp))
1015
        mark_reg (tmp, set);
1016
    }
1017
#endif
1018
#ifdef EH_RETURN_HANDLER_RTX
1019
  if ((! HAVE_epilogue || ! epilogue_completed)
1020
      && current_function_calls_eh_return)
1021
    {
1022
      rtx tmp = EH_RETURN_HANDLER_RTX;
1023
      if (tmp && REG_P (tmp))
1024
        mark_reg (tmp, set);
1025
    }
1026
#endif
1027
 
1028
  /* Mark function return value.  */
1029
  diddle_return_value (mark_reg, set);
1030
}
1031
 
1032
/* Propagate global life info around the graph of basic blocks.  Begin
1033
   considering blocks with their corresponding bit set in BLOCKS_IN.
1034
   If BLOCKS_IN is null, consider it the universal set.
1035
 
1036
   BLOCKS_OUT is set for every block that was changed.  */
1037
 
1038
static void
1039
calculate_global_regs_live (sbitmap blocks_in, sbitmap blocks_out, int flags)
1040
{
1041
  basic_block *queue, *qhead, *qtail, *qend, bb;
1042
  regset tmp, new_live_at_end, invalidated_by_eh_edge;
1043
  regset registers_made_dead;
1044
  bool failure_strategy_required = false;
1045
  int *block_accesses;
1046
 
1047
  /* The registers that are modified within this in block.  */
1048
  regset *local_sets;
1049
 
1050
  /* The registers that are conditionally modified within this block.
1051
     In other words, regs that are set only as part of a COND_EXEC.  */
1052
  regset *cond_local_sets;
1053
 
1054
  unsigned int i;
1055
 
1056
  /* Some passes used to forget clear aux field of basic block causing
1057
     sick behavior here.  */
1058
#ifdef ENABLE_CHECKING
1059
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1060
    gcc_assert (!bb->aux);
1061
#endif
1062
 
1063
  tmp = ALLOC_REG_SET (&reg_obstack);
1064
  new_live_at_end = ALLOC_REG_SET (&reg_obstack);
1065
  invalidated_by_eh_edge = ALLOC_REG_SET (&reg_obstack);
1066
  registers_made_dead = ALLOC_REG_SET (&reg_obstack);
1067
 
1068
  /* Inconveniently, this is only readily available in hard reg set form.  */
1069
  for (i = 0; i < FIRST_PSEUDO_REGISTER; ++i)
1070
    if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
1071
      SET_REGNO_REG_SET (invalidated_by_eh_edge, i);
1072
 
1073
  /* The exception handling registers die at eh edges.  */
1074
#ifdef EH_RETURN_DATA_REGNO
1075
  for (i = 0; ; ++i)
1076
    {
1077
      unsigned regno = EH_RETURN_DATA_REGNO (i);
1078
      if (regno == INVALID_REGNUM)
1079
        break;
1080
      SET_REGNO_REG_SET (invalidated_by_eh_edge, regno);
1081
    }
1082
#endif
1083
 
1084
  /* Allocate space for the sets of local properties.  */
1085
  local_sets = XCNEWVEC (bitmap, last_basic_block);
1086
  cond_local_sets = XCNEWVEC (bitmap, last_basic_block);
1087
 
1088
  /* Create a worklist.  Allocate an extra slot for the `head == tail'
1089
     style test for an empty queue doesn't work with a full queue.  */
1090
  queue = XNEWVEC (basic_block, n_basic_blocks + 1);
1091
  qtail = queue;
1092
  qhead = qend = queue + n_basic_blocks;
1093
 
1094
  /* Queue the blocks set in the initial mask.  Do this in reverse block
1095
     number order so that we are more likely for the first round to do
1096
     useful work.  We use AUX non-null to flag that the block is queued.  */
1097
  if (blocks_in)
1098
    {
1099
      FOR_EACH_BB (bb)
1100
        if (TEST_BIT (blocks_in, bb->index))
1101
          {
1102
            *--qhead = bb;
1103
            bb->aux = bb;
1104
          }
1105
    }
1106
  else
1107
    {
1108
      FOR_EACH_BB (bb)
1109
        {
1110
          *--qhead = bb;
1111
          bb->aux = bb;
1112
        }
1113
    }
1114
 
1115
  block_accesses = XCNEWVEC (int, last_basic_block);
1116
 
1117
  /* We clean aux when we remove the initially-enqueued bbs, but we
1118
     don't enqueue ENTRY and EXIT initially, so clean them upfront and
1119
     unconditionally.  */
1120
  ENTRY_BLOCK_PTR->aux = EXIT_BLOCK_PTR->aux = NULL;
1121
 
1122
  if (blocks_out)
1123
    sbitmap_zero (blocks_out);
1124
 
1125
  /* We work through the queue until there are no more blocks.  What
1126
     is live at the end of this block is precisely the union of what
1127
     is live at the beginning of all its successors.  So, we set its
1128
     GLOBAL_LIVE_AT_END field based on the GLOBAL_LIVE_AT_START field
1129
     for its successors.  Then, we compute GLOBAL_LIVE_AT_START for
1130
     this block by walking through the instructions in this block in
1131
     reverse order and updating as we go.  If that changed
1132
     GLOBAL_LIVE_AT_START, we add the predecessors of the block to the
1133
     queue; they will now need to recalculate GLOBAL_LIVE_AT_END.
1134
 
1135
     We are guaranteed to terminate, because GLOBAL_LIVE_AT_START
1136
     never shrinks.  If a register appears in GLOBAL_LIVE_AT_START, it
1137
     must either be live at the end of the block, or used within the
1138
     block.  In the latter case, it will certainly never disappear
1139
     from GLOBAL_LIVE_AT_START.  In the former case, the register
1140
     could go away only if it disappeared from GLOBAL_LIVE_AT_START
1141
     for one of the successor blocks.  By induction, that cannot
1142
     occur.
1143
 
1144
     ??? This reasoning doesn't work if we start from non-empty initial
1145
     GLOBAL_LIVE_AT_START sets.  And there are actually two problems:
1146
       1) Updating may not terminate (endless oscillation).
1147
       2) Even if it does (and it usually does), the resulting information
1148
          may be inaccurate.  Consider for example the following case:
1149
 
1150
          a = ...;
1151
          while (...) {...}  -- 'a' not mentioned at all
1152
          ... = a;
1153
 
1154
          If the use of 'a' is deleted between two calculations of liveness
1155
          information and the initial sets are not cleared, the information
1156
          about a's liveness will get stuck inside the loop and the set will
1157
          appear not to be dead.
1158
 
1159
     We do not attempt to solve 2) -- the information is conservatively
1160
     correct (i.e. we never claim that something live is dead) and the
1161
     amount of optimization opportunities missed due to this problem is
1162
     not significant.
1163
 
1164
     1) is more serious.  In order to fix it, we monitor the number of times
1165
     each block is processed.  Once one of the blocks has been processed more
1166
     times than the maximum number of rounds, we use the following strategy:
1167
     When a register disappears from one of the sets, we add it to a MAKE_DEAD
1168
     set, remove all registers in this set from all GLOBAL_LIVE_AT_* sets and
1169
     add the blocks with changed sets into the queue.  Thus we are guaranteed
1170
     to terminate (the worst case corresponds to all registers in MADE_DEAD,
1171
     in which case the original reasoning above is valid), but in general we
1172
     only fix up a few offending registers.
1173
 
1174
     The maximum number of rounds for computing liveness is the largest of
1175
     MAX_LIVENESS_ROUNDS and the latest loop depth count for this function.  */
1176
 
1177
  while (qhead != qtail)
1178
    {
1179
      int rescan, changed;
1180
      basic_block bb;
1181
      edge e;
1182
      edge_iterator ei;
1183
 
1184
      bb = *qhead++;
1185
      if (qhead == qend)
1186
        qhead = queue;
1187
      bb->aux = NULL;
1188
 
1189
      /* Should we start using the failure strategy?  */
1190
      if (bb != ENTRY_BLOCK_PTR)
1191
        {
1192
          int max_liveness_rounds =
1193
            MAX (MAX_LIVENESS_ROUNDS, cfun->max_loop_depth);
1194
 
1195
          block_accesses[bb->index]++;
1196
          if (block_accesses[bb->index] > max_liveness_rounds)
1197
            failure_strategy_required = true;
1198
        }
1199
 
1200
      /* Begin by propagating live_at_start from the successor blocks.  */
1201
      CLEAR_REG_SET (new_live_at_end);
1202
 
1203
      if (EDGE_COUNT (bb->succs) > 0)
1204
        FOR_EACH_EDGE (e, ei, bb->succs)
1205
          {
1206
            basic_block sb = e->dest;
1207
 
1208
            /* Call-clobbered registers die across exception and
1209
               call edges.  */
1210
            /* ??? Abnormal call edges ignored for the moment, as this gets
1211
               confused by sibling call edges, which crashes reg-stack.  */
1212
            if (e->flags & EDGE_EH)
1213
              bitmap_ior_and_compl_into (new_live_at_end,
1214
                                         sb->il.rtl->global_live_at_start,
1215
                                         invalidated_by_eh_edge);
1216
            else
1217
              IOR_REG_SET (new_live_at_end, sb->il.rtl->global_live_at_start);
1218
 
1219
            /* If a target saves one register in another (instead of on
1220
               the stack) the save register will need to be live for EH.  */
1221
            if (e->flags & EDGE_EH)
1222
              for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1223
                if (EH_USES (i))
1224
                  SET_REGNO_REG_SET (new_live_at_end, i);
1225
          }
1226
      else
1227
        {
1228
          /* This might be a noreturn function that throws.  And
1229
             even if it isn't, getting the unwind info right helps
1230
             debugging.  */
1231
          for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1232
            if (EH_USES (i))
1233
              SET_REGNO_REG_SET (new_live_at_end, i);
1234
        }
1235
 
1236
      /* The all-important stack pointer must always be live.  */
1237
      SET_REGNO_REG_SET (new_live_at_end, STACK_POINTER_REGNUM);
1238
 
1239
      /* Before reload, there are a few registers that must be forced
1240
         live everywhere -- which might not already be the case for
1241
         blocks within infinite loops.  */
1242
      if (! reload_completed)
1243
        {
1244
          /* Any reference to any pseudo before reload is a potential
1245
             reference of the frame pointer.  */
1246
          SET_REGNO_REG_SET (new_live_at_end, FRAME_POINTER_REGNUM);
1247
 
1248
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
1249
          /* Pseudos with argument area equivalences may require
1250
             reloading via the argument pointer.  */
1251
          if (fixed_regs[ARG_POINTER_REGNUM])
1252
            SET_REGNO_REG_SET (new_live_at_end, ARG_POINTER_REGNUM);
1253
#endif
1254
 
1255
          /* Any constant, or pseudo with constant equivalences, may
1256
             require reloading from memory using the pic register.  */
1257
          if ((unsigned) PIC_OFFSET_TABLE_REGNUM != INVALID_REGNUM
1258
              && fixed_regs[PIC_OFFSET_TABLE_REGNUM])
1259
            SET_REGNO_REG_SET (new_live_at_end, PIC_OFFSET_TABLE_REGNUM);
1260
        }
1261
 
1262
      if (bb == ENTRY_BLOCK_PTR)
1263
        {
1264
          COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1265
          continue;
1266
        }
1267
 
1268
      /* On our first pass through this block, we'll go ahead and continue.
1269
         Recognize first pass by checking if local_set is NULL for this
1270
         basic block.  On subsequent passes, we get to skip out early if
1271
         live_at_end wouldn't have changed.  */
1272
 
1273
      if (local_sets[bb->index] == NULL)
1274
        {
1275
          local_sets[bb->index] = ALLOC_REG_SET (&reg_obstack);
1276
          cond_local_sets[bb->index] = ALLOC_REG_SET (&reg_obstack);
1277
          rescan = 1;
1278
        }
1279
      else
1280
        {
1281
          /* If any bits were removed from live_at_end, we'll have to
1282
             rescan the block.  This wouldn't be necessary if we had
1283
             precalculated local_live, however with PROP_SCAN_DEAD_CODE
1284
             local_live is really dependent on live_at_end.  */
1285
          rescan = bitmap_intersect_compl_p (bb->il.rtl->global_live_at_end,
1286
                                             new_live_at_end);
1287
 
1288
          if (!rescan)
1289
            {
1290
              regset cond_local_set;
1291
 
1292
               /* If any of the registers in the new live_at_end set are
1293
                  conditionally set in this basic block, we must rescan.
1294
                  This is because conditional lifetimes at the end of the
1295
                  block do not just take the live_at_end set into
1296
                  account, but also the liveness at the start of each
1297
                  successor block.  We can miss changes in those sets if
1298
                  we only compare the new live_at_end against the
1299
                  previous one.  */
1300
              cond_local_set = cond_local_sets[bb->index];
1301
              rescan = bitmap_intersect_p (new_live_at_end, cond_local_set);
1302
            }
1303
 
1304
          if (!rescan)
1305
            {
1306
              regset local_set;
1307
 
1308
              /* Find the set of changed bits.  Take this opportunity
1309
                 to notice that this set is empty and early out.  */
1310
              bitmap_xor (tmp, bb->il.rtl->global_live_at_end, new_live_at_end);
1311
              if (bitmap_empty_p (tmp))
1312
                continue;
1313
 
1314
              /* If any of the changed bits overlap with local_sets[bb],
1315
                 we'll have to rescan the block.  */
1316
              local_set = local_sets[bb->index];
1317
              rescan = bitmap_intersect_p (tmp, local_set);
1318
            }
1319
        }
1320
 
1321
      /* Let our caller know that BB changed enough to require its
1322
         death notes updated.  */
1323
      if (blocks_out)
1324
        SET_BIT (blocks_out, bb->index);
1325
 
1326
      if (! rescan)
1327
        {
1328
          /* Add to live_at_start the set of all registers in
1329
             new_live_at_end that aren't in the old live_at_end.  */
1330
 
1331
          changed = bitmap_ior_and_compl_into (bb->il.rtl->global_live_at_start,
1332
                                               new_live_at_end,
1333
                                               bb->il.rtl->global_live_at_end);
1334
          COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1335
          if (! changed)
1336
            continue;
1337
        }
1338
      else
1339
        {
1340
          COPY_REG_SET (bb->il.rtl->global_live_at_end, new_live_at_end);
1341
 
1342
          /* Rescan the block insn by insn to turn (a copy of) live_at_end
1343
             into live_at_start.  */
1344
          propagate_block (bb, new_live_at_end,
1345
                           local_sets[bb->index],
1346
                           cond_local_sets[bb->index],
1347
                           flags);
1348
 
1349
          /* If live_at start didn't change, no need to go farther.  */
1350
          if (REG_SET_EQUAL_P (bb->il.rtl->global_live_at_start,
1351
                               new_live_at_end))
1352
            continue;
1353
 
1354
          if (failure_strategy_required)
1355
            {
1356
              /* Get the list of registers that were removed from the
1357
                 bb->global_live_at_start set.  */
1358
              bitmap_and_compl (tmp, bb->il.rtl->global_live_at_start,
1359
                                new_live_at_end);
1360
              if (!bitmap_empty_p (tmp))
1361
                {
1362
                  bool pbb_changed;
1363
                  basic_block pbb;
1364
 
1365
                  /* It should not happen that one of registers we have
1366
                     removed last time is disappears again before any other
1367
                     register does.  */
1368
                  pbb_changed = bitmap_ior_into (registers_made_dead, tmp);
1369
                  gcc_assert (pbb_changed);
1370
 
1371
                  /* Now remove the registers from all sets.  */
1372
                  FOR_EACH_BB (pbb)
1373
                    {
1374
                      pbb_changed = false;
1375
 
1376
                      pbb_changed
1377
                        |= bitmap_and_compl_into
1378
                            (pbb->il.rtl->global_live_at_start,
1379
                             registers_made_dead);
1380
                      pbb_changed
1381
                        |= bitmap_and_compl_into
1382
                            (pbb->il.rtl->global_live_at_end,
1383
                             registers_made_dead);
1384
                      if (!pbb_changed)
1385
                        continue;
1386
 
1387
                      /* Note the (possible) change.  */
1388
                      if (blocks_out)
1389
                        SET_BIT (blocks_out, pbb->index);
1390
 
1391
                      /* Makes sure to really rescan the block.  */
1392
                      if (local_sets[pbb->index])
1393
                        {
1394
                          FREE_REG_SET (local_sets[pbb->index]);
1395
                          FREE_REG_SET (cond_local_sets[pbb->index]);
1396
                          local_sets[pbb->index] = 0;
1397
                        }
1398
 
1399
                      /* Add it to the queue.  */
1400
                      if (pbb->aux == NULL)
1401
                        {
1402
                          *qtail++ = pbb;
1403
                          if (qtail == qend)
1404
                            qtail = queue;
1405
                          pbb->aux = pbb;
1406
                        }
1407
                    }
1408
                  continue;
1409
                }
1410
            } /* end of failure_strategy_required */
1411
 
1412
          COPY_REG_SET (bb->il.rtl->global_live_at_start, new_live_at_end);
1413
        }
1414
 
1415
      /* Queue all predecessors of BB so that we may re-examine
1416
         their live_at_end.  */
1417
      FOR_EACH_EDGE (e, ei, bb->preds)
1418
        {
1419
          basic_block pb = e->src;
1420
 
1421
          gcc_assert ((e->flags & EDGE_FAKE) == 0);
1422
 
1423
          if (pb->aux == NULL)
1424
            {
1425
              *qtail++ = pb;
1426
              if (qtail == qend)
1427
                qtail = queue;
1428
              pb->aux = pb;
1429
            }
1430
        }
1431
    }
1432
 
1433
  FREE_REG_SET (tmp);
1434
  FREE_REG_SET (new_live_at_end);
1435
  FREE_REG_SET (invalidated_by_eh_edge);
1436
  FREE_REG_SET (registers_made_dead);
1437
 
1438
  if (blocks_out)
1439
    {
1440
      sbitmap_iterator sbi;
1441
 
1442
      EXECUTE_IF_SET_IN_SBITMAP (blocks_out, 0, i, sbi)
1443
        {
1444
          basic_block bb = BASIC_BLOCK (i);
1445
          FREE_REG_SET (local_sets[bb->index]);
1446
          FREE_REG_SET (cond_local_sets[bb->index]);
1447
        };
1448
    }
1449
  else
1450
    {
1451
      FOR_EACH_BB (bb)
1452
        {
1453
          FREE_REG_SET (local_sets[bb->index]);
1454
          FREE_REG_SET (cond_local_sets[bb->index]);
1455
        }
1456
    }
1457
 
1458
  free (block_accesses);
1459
  free (queue);
1460
  free (cond_local_sets);
1461
  free (local_sets);
1462
}
1463
 
1464
 
1465
/* This structure is used to pass parameters to and from the
1466
   the function find_regno_partial(). It is used to pass in the
1467
   register number we are looking, as well as to return any rtx
1468
   we find.  */
1469
 
1470
typedef struct {
1471
  unsigned regno_to_find;
1472
  rtx retval;
1473
} find_regno_partial_param;
1474
 
1475
 
1476
/* Find the rtx for the reg numbers specified in 'data' if it is
1477
   part of an expression which only uses part of the register.  Return
1478
   it in the structure passed in.  */
1479
static int
1480
find_regno_partial (rtx *ptr, void *data)
1481
{
1482
  find_regno_partial_param *param = (find_regno_partial_param *)data;
1483
  unsigned reg = param->regno_to_find;
1484
  param->retval = NULL_RTX;
1485
 
1486
  if (*ptr == NULL_RTX)
1487
    return 0;
1488
 
1489
  switch (GET_CODE (*ptr))
1490
    {
1491
    case ZERO_EXTRACT:
1492
    case SIGN_EXTRACT:
1493
    case STRICT_LOW_PART:
1494
      if (REG_P (XEXP (*ptr, 0)) && REGNO (XEXP (*ptr, 0)) == reg)
1495
        {
1496
          param->retval = XEXP (*ptr, 0);
1497
          return 1;
1498
        }
1499
      break;
1500
 
1501
    case SUBREG:
1502
      if (REG_P (SUBREG_REG (*ptr))
1503
          && REGNO (SUBREG_REG (*ptr)) == reg)
1504
        {
1505
          param->retval = SUBREG_REG (*ptr);
1506
          return 1;
1507
        }
1508
      break;
1509
 
1510
    default:
1511
      break;
1512
    }
1513
 
1514
  return 0;
1515
}
1516
 
1517
/* Process all immediate successors of the entry block looking for pseudo
1518
   registers which are live on entry. Find all of those whose first
1519
   instance is a partial register reference of some kind, and initialize
1520
   them to 0 after the entry block.  This will prevent bit sets within
1521
   registers whose value is unknown, and may contain some kind of sticky
1522
   bits we don't want.  */
1523
 
1524
static int
1525
initialize_uninitialized_subregs (void)
1526
{
1527
  rtx insn;
1528
  edge e;
1529
  unsigned reg, did_something = 0;
1530
  find_regno_partial_param param;
1531
  edge_iterator ei;
1532
 
1533
  FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
1534
    {
1535
      basic_block bb = e->dest;
1536
      regset map = bb->il.rtl->global_live_at_start;
1537
      reg_set_iterator rsi;
1538
 
1539
      EXECUTE_IF_SET_IN_REG_SET (map, FIRST_PSEUDO_REGISTER, reg, rsi)
1540
        {
1541
          int uid = REGNO_FIRST_UID (reg);
1542
          rtx i;
1543
 
1544
          /* Find an insn which mentions the register we are looking for.
1545
             Its preferable to have an instance of the register's rtl since
1546
             there may be various flags set which we need to duplicate.
1547
             If we can't find it, its probably an automatic whose initial
1548
             value doesn't matter, or hopefully something we don't care about.  */
1549
          for (i = get_insns (); i && INSN_UID (i) != uid; i = NEXT_INSN (i))
1550
            ;
1551
          if (i != NULL_RTX)
1552
            {
1553
              /* Found the insn, now get the REG rtx, if we can.  */
1554
              param.regno_to_find = reg;
1555
              for_each_rtx (&i, find_regno_partial, &param);
1556
              if (param.retval != NULL_RTX)
1557
                {
1558
                  start_sequence ();
1559
                  emit_move_insn (param.retval,
1560
                                  CONST0_RTX (GET_MODE (param.retval)));
1561
                  insn = get_insns ();
1562
                  end_sequence ();
1563
                  insert_insn_on_edge (insn, e);
1564
                  did_something = 1;
1565
                }
1566
            }
1567
        }
1568
    }
1569
 
1570
  if (did_something)
1571
    commit_edge_insertions ();
1572
  return did_something;
1573
}
1574
 
1575
 
1576
/* Subroutines of life analysis.  */
1577
 
1578
/* Allocate the permanent data structures that represent the results
1579
   of life analysis.  */
1580
 
1581
static void
1582
allocate_bb_life_data (void)
1583
{
1584
  basic_block bb;
1585
 
1586
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR, NULL, next_bb)
1587
    {
1588
      if (bb->il.rtl->global_live_at_start)
1589
        {
1590
          CLEAR_REG_SET (bb->il.rtl->global_live_at_start);
1591
          CLEAR_REG_SET (bb->il.rtl->global_live_at_end);
1592
        }
1593
      else
1594
        {
1595
          bb->il.rtl->global_live_at_start = ALLOC_REG_SET (&reg_obstack);
1596
          bb->il.rtl->global_live_at_end = ALLOC_REG_SET (&reg_obstack);
1597
        }
1598
    }
1599
 
1600
  regs_live_at_setjmp = ALLOC_REG_SET (&reg_obstack);
1601
}
1602
 
1603
void
1604
allocate_reg_life_data (void)
1605
{
1606
  int i;
1607
 
1608
  max_regno = max_reg_num ();
1609
  gcc_assert (!reg_deaths);
1610
  reg_deaths = XCNEWVEC (int, max_regno);
1611
 
1612
  /* Recalculate the register space, in case it has grown.  Old style
1613
     vector oriented regsets would set regset_{size,bytes} here also.  */
1614
  allocate_reg_info (max_regno, FALSE, FALSE);
1615
 
1616
  /* Reset all the data we'll collect in propagate_block and its
1617
     subroutines.  */
1618
  for (i = 0; i < max_regno; i++)
1619
    {
1620
      REG_N_SETS (i) = 0;
1621
      REG_N_REFS (i) = 0;
1622
      REG_N_DEATHS (i) = 0;
1623
      REG_N_CALLS_CROSSED (i) = 0;
1624
      REG_N_THROWING_CALLS_CROSSED (i) = 0;
1625
      REG_LIVE_LENGTH (i) = 0;
1626
      REG_FREQ (i) = 0;
1627
      REG_BASIC_BLOCK (i) = REG_BLOCK_UNKNOWN;
1628
    }
1629
}
1630
 
1631
/* Delete dead instructions for propagate_block.  */
1632
 
1633
static void
1634
propagate_block_delete_insn (rtx insn)
1635
{
1636
  rtx inote = find_reg_note (insn, REG_LABEL, NULL_RTX);
1637
 
1638
  /* If the insn referred to a label, and that label was attached to
1639
     an ADDR_VEC, it's safe to delete the ADDR_VEC.  In fact, it's
1640
     pretty much mandatory to delete it, because the ADDR_VEC may be
1641
     referencing labels that no longer exist.
1642
 
1643
     INSN may reference a deleted label, particularly when a jump
1644
     table has been optimized into a direct jump.  There's no
1645
     real good way to fix up the reference to the deleted label
1646
     when the label is deleted, so we just allow it here.  */
1647
 
1648
  if (inote && LABEL_P (inote))
1649
    {
1650
      rtx label = XEXP (inote, 0);
1651
      rtx next;
1652
 
1653
      /* The label may be forced if it has been put in the constant
1654
         pool.  If that is the only use we must discard the table
1655
         jump following it, but not the label itself.  */
1656
      if (LABEL_NUSES (label) == 1 + LABEL_PRESERVE_P (label)
1657
          && (next = next_nonnote_insn (label)) != NULL
1658
          && JUMP_P (next)
1659
          && (GET_CODE (PATTERN (next)) == ADDR_VEC
1660
              || GET_CODE (PATTERN (next)) == ADDR_DIFF_VEC))
1661
        {
1662
          rtx pat = PATTERN (next);
1663
          int diff_vec_p = GET_CODE (pat) == ADDR_DIFF_VEC;
1664
          int len = XVECLEN (pat, diff_vec_p);
1665
          int i;
1666
 
1667
          for (i = 0; i < len; i++)
1668
            LABEL_NUSES (XEXP (XVECEXP (pat, diff_vec_p, i), 0))--;
1669
 
1670
          delete_insn_and_edges (next);
1671
          ndead++;
1672
        }
1673
    }
1674
 
1675
  delete_insn_and_edges (insn);
1676
  ndead++;
1677
}
1678
 
1679
/* Delete dead libcalls for propagate_block.  Return the insn
1680
   before the libcall.  */
1681
 
1682
static rtx
1683
propagate_block_delete_libcall (rtx insn, rtx note)
1684
{
1685
  rtx first = XEXP (note, 0);
1686
  rtx before = PREV_INSN (first);
1687
 
1688
  delete_insn_chain_and_edges (first, insn);
1689
  ndead++;
1690
  return before;
1691
}
1692
 
1693
/* Update the life-status of regs for one insn.  Return the previous insn.  */
1694
 
1695
rtx
1696
propagate_one_insn (struct propagate_block_info *pbi, rtx insn)
1697
{
1698
  rtx prev = PREV_INSN (insn);
1699
  int flags = pbi->flags;
1700
  int insn_is_dead = 0;
1701
  int libcall_is_dead = 0;
1702
  rtx note;
1703
  unsigned i;
1704
 
1705
  if (! INSN_P (insn))
1706
    return prev;
1707
 
1708
  note = find_reg_note (insn, REG_RETVAL, NULL_RTX);
1709
  if (flags & PROP_SCAN_DEAD_CODE)
1710
    {
1711
      insn_is_dead = insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn));
1712
      libcall_is_dead = (insn_is_dead && note != 0
1713
                         && libcall_dead_p (pbi, note, insn));
1714
    }
1715
 
1716
  /* If an instruction consists of just dead store(s) on final pass,
1717
     delete it.  */
1718
  if ((flags & PROP_KILL_DEAD_CODE) && insn_is_dead)
1719
    {
1720
      /* If we're trying to delete a prologue or epilogue instruction
1721
         that isn't flagged as possibly being dead, something is wrong.
1722
         But if we are keeping the stack pointer depressed, we might well
1723
         be deleting insns that are used to compute the amount to update
1724
         it by, so they are fine.  */
1725
      if (reload_completed
1726
          && !(TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
1727
                && (TYPE_RETURNS_STACK_DEPRESSED
1728
                    (TREE_TYPE (current_function_decl))))
1729
          && (((HAVE_epilogue || HAVE_prologue)
1730
               && prologue_epilogue_contains (insn))
1731
              || (HAVE_sibcall_epilogue
1732
                  && sibcall_epilogue_contains (insn)))
1733
          && find_reg_note (insn, REG_MAYBE_DEAD, NULL_RTX) == 0)
1734
        fatal_insn ("Attempt to delete prologue/epilogue insn:", insn);
1735
 
1736
      /* Record sets.  Do this even for dead instructions, since they
1737
         would have killed the values if they hadn't been deleted.  To
1738
         be consistent, we also have to emit a clobber when we delete
1739
         an insn that clobbers a live register.  */
1740
      pbi->flags |= PROP_DEAD_INSN;
1741
      mark_set_regs (pbi, PATTERN (insn), insn);
1742
      pbi->flags &= ~PROP_DEAD_INSN;
1743
 
1744
      /* CC0 is now known to be dead.  Either this insn used it,
1745
         in which case it doesn't anymore, or clobbered it,
1746
         so the next insn can't use it.  */
1747
      pbi->cc0_live = 0;
1748
 
1749
      if (libcall_is_dead)
1750
        prev = propagate_block_delete_libcall (insn, note);
1751
      else
1752
        {
1753
 
1754
        /* If INSN contains a RETVAL note and is dead, but the libcall
1755
           as a whole is not dead, then we want to remove INSN, but
1756
           not the whole libcall sequence.
1757
 
1758
           However, we need to also remove the dangling REG_LIBCALL
1759
           note so that we do not have mis-matched LIBCALL/RETVAL
1760
           notes.  In theory we could find a new location for the
1761
           REG_RETVAL note, but it hardly seems worth the effort.
1762
 
1763
           NOTE at this point will be the RETVAL note if it exists.  */
1764
          if (note)
1765
            {
1766
              rtx libcall_note;
1767
 
1768
              libcall_note
1769
                = find_reg_note (XEXP (note, 0), REG_LIBCALL, NULL_RTX);
1770
              remove_note (XEXP (note, 0), libcall_note);
1771
            }
1772
 
1773
          /* Similarly if INSN contains a LIBCALL note, remove the
1774
             dangling REG_RETVAL note.  */
1775
          note = find_reg_note (insn, REG_LIBCALL, NULL_RTX);
1776
          if (note)
1777
            {
1778
              rtx retval_note;
1779
 
1780
              retval_note
1781
                = find_reg_note (XEXP (note, 0), REG_RETVAL, NULL_RTX);
1782
              remove_note (XEXP (note, 0), retval_note);
1783
            }
1784
 
1785
          /* Now delete INSN.  */
1786
          propagate_block_delete_insn (insn);
1787
        }
1788
 
1789
      return prev;
1790
    }
1791
 
1792
  /* See if this is an increment or decrement that can be merged into
1793
     a following memory address.  */
1794
#ifdef AUTO_INC_DEC
1795
  {
1796
    rtx x = single_set (insn);
1797
 
1798
    /* Does this instruction increment or decrement a register?  */
1799
    if ((flags & PROP_AUTOINC)
1800
        && x != 0
1801
        && REG_P (SET_DEST (x))
1802
        && (GET_CODE (SET_SRC (x)) == PLUS
1803
            || GET_CODE (SET_SRC (x)) == MINUS)
1804
        && XEXP (SET_SRC (x), 0) == SET_DEST (x)
1805
        && GET_CODE (XEXP (SET_SRC (x), 1)) == CONST_INT
1806
        /* Ok, look for a following memory ref we can combine with.
1807
           If one is found, change the memory ref to a PRE_INC
1808
           or PRE_DEC, cancel this insn, and return 1.
1809
           Return 0 if nothing has been done.  */
1810
        && try_pre_increment_1 (pbi, insn))
1811
      return prev;
1812
  }
1813
#endif /* AUTO_INC_DEC */
1814
 
1815
  CLEAR_REG_SET (pbi->new_set);
1816
 
1817
  /* If this is not the final pass, and this insn is copying the value of
1818
     a library call and it's dead, don't scan the insns that perform the
1819
     library call, so that the call's arguments are not marked live.  */
1820
  if (libcall_is_dead)
1821
    {
1822
      /* Record the death of the dest reg.  */
1823
      mark_set_regs (pbi, PATTERN (insn), insn);
1824
 
1825
      insn = XEXP (note, 0);
1826
      return PREV_INSN (insn);
1827
    }
1828
  else if (GET_CODE (PATTERN (insn)) == SET
1829
           && SET_DEST (PATTERN (insn)) == stack_pointer_rtx
1830
           && GET_CODE (SET_SRC (PATTERN (insn))) == PLUS
1831
           && XEXP (SET_SRC (PATTERN (insn)), 0) == stack_pointer_rtx
1832
           && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 1)) == CONST_INT)
1833
    {
1834
      /* We have an insn to pop a constant amount off the stack.
1835
         (Such insns use PLUS regardless of the direction of the stack,
1836
         and any insn to adjust the stack by a constant is always a pop
1837
         or part of a push.)
1838
         These insns, if not dead stores, have no effect on life, though
1839
         they do have an effect on the memory stores we are tracking.  */
1840
      invalidate_mems_from_set (pbi, stack_pointer_rtx);
1841
      /* Still, we need to update local_set, lest ifcvt.c:dead_or_predicable
1842
         concludes that the stack pointer is not modified.  */
1843
      mark_set_regs (pbi, PATTERN (insn), insn);
1844
    }
1845
  else
1846
    {
1847
      /* Any regs live at the time of a call instruction must not go
1848
         in a register clobbered by calls.  Find all regs now live and
1849
         record this for them.  */
1850
 
1851
      if (CALL_P (insn) && (flags & PROP_REG_INFO))
1852
        {
1853
          reg_set_iterator rsi;
1854
          EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
1855
            REG_N_CALLS_CROSSED (i)++;
1856
          if (can_throw_internal (insn))
1857
            EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
1858
              REG_N_THROWING_CALLS_CROSSED (i)++;
1859
        }
1860
 
1861
      /* Record sets.  Do this even for dead instructions, since they
1862
         would have killed the values if they hadn't been deleted.  */
1863
      mark_set_regs (pbi, PATTERN (insn), insn);
1864
 
1865
      if (CALL_P (insn))
1866
        {
1867
          regset live_at_end;
1868
          bool sibcall_p;
1869
          rtx note, cond;
1870
          int i;
1871
 
1872
          cond = NULL_RTX;
1873
          if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1874
            cond = COND_EXEC_TEST (PATTERN (insn));
1875
 
1876
          /* Non-constant calls clobber memory, constant calls do not
1877
             clobber memory, though they may clobber outgoing arguments
1878
             on the stack.  */
1879
          if (! CONST_OR_PURE_CALL_P (insn))
1880
            {
1881
              free_EXPR_LIST_list (&pbi->mem_set_list);
1882
              pbi->mem_set_list_len = 0;
1883
            }
1884
          else
1885
            invalidate_mems_from_set (pbi, stack_pointer_rtx);
1886
 
1887
          /* There may be extra registers to be clobbered.  */
1888
          for (note = CALL_INSN_FUNCTION_USAGE (insn);
1889
               note;
1890
               note = XEXP (note, 1))
1891
            if (GET_CODE (XEXP (note, 0)) == CLOBBER)
1892
              mark_set_1 (pbi, CLOBBER, XEXP (XEXP (note, 0), 0),
1893
                          cond, insn, pbi->flags);
1894
 
1895
          /* Calls change all call-used and global registers; sibcalls do not
1896
             clobber anything that must be preserved at end-of-function,
1897
             except for return values.  */
1898
 
1899
          sibcall_p = SIBLING_CALL_P (insn);
1900
          live_at_end = EXIT_BLOCK_PTR->il.rtl->global_live_at_start;
1901
          for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1902
            if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)
1903
                && ! (sibcall_p
1904
                      && REGNO_REG_SET_P (live_at_end, i)
1905
                      && ! refers_to_regno_p (i, i+1,
1906
                                              current_function_return_rtx,
1907
                                              (rtx *) 0)))
1908
              {
1909
                enum rtx_code code = global_regs[i] ? SET : CLOBBER;
1910
                /* We do not want REG_UNUSED notes for these registers.  */
1911
                mark_set_1 (pbi, code, regno_reg_rtx[i], cond, insn,
1912
                            pbi->flags & ~(PROP_DEATH_NOTES | PROP_REG_INFO));
1913
              }
1914
        }
1915
 
1916
      /* If an insn doesn't use CC0, it becomes dead since we assume
1917
         that every insn clobbers it.  So show it dead here;
1918
         mark_used_regs will set it live if it is referenced.  */
1919
      pbi->cc0_live = 0;
1920
 
1921
      /* Record uses.  */
1922
      if (! insn_is_dead)
1923
        mark_used_regs (pbi, PATTERN (insn), NULL_RTX, insn);
1924
 
1925
      /* Sometimes we may have inserted something before INSN (such as a move)
1926
         when we make an auto-inc.  So ensure we will scan those insns.  */
1927
#ifdef AUTO_INC_DEC
1928
      prev = PREV_INSN (insn);
1929
#endif
1930
 
1931
      if (! insn_is_dead && CALL_P (insn))
1932
        {
1933
          int i;
1934
          rtx note, cond;
1935
 
1936
          cond = NULL_RTX;
1937
          if (GET_CODE (PATTERN (insn)) == COND_EXEC)
1938
            cond = COND_EXEC_TEST (PATTERN (insn));
1939
 
1940
          /* Calls use their arguments, and may clobber memory which
1941
             address involves some register.  */
1942
          for (note = CALL_INSN_FUNCTION_USAGE (insn);
1943
               note;
1944
               note = XEXP (note, 1))
1945
            /* We find USE or CLOBBER entities in a FUNCTION_USAGE list: both
1946
               of which mark_used_regs knows how to handle.  */
1947
            mark_used_regs (pbi, XEXP (XEXP (note, 0), 0), cond, insn);
1948
 
1949
          /* The stack ptr is used (honorarily) by a CALL insn.  */
1950
          if ((flags & PROP_REG_INFO)
1951
              && !REGNO_REG_SET_P (pbi->reg_live, STACK_POINTER_REGNUM))
1952
            reg_deaths[STACK_POINTER_REGNUM] = pbi->insn_num;
1953
          SET_REGNO_REG_SET (pbi->reg_live, STACK_POINTER_REGNUM);
1954
 
1955
          /* Calls may also reference any of the global registers,
1956
             so they are made live.  */
1957
          for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
1958
            if (global_regs[i])
1959
              mark_used_reg (pbi, regno_reg_rtx[i], cond, insn);
1960
        }
1961
    }
1962
 
1963
  pbi->insn_num++;
1964
 
1965
  return prev;
1966
}
1967
 
1968
/* Initialize a propagate_block_info struct for public consumption.
1969
   Note that the structure itself is opaque to this file, but that
1970
   the user can use the regsets provided here.  */
1971
 
1972
struct propagate_block_info *
1973
init_propagate_block_info (basic_block bb, regset live, regset local_set,
1974
                           regset cond_local_set, int flags)
1975
{
1976
  struct propagate_block_info *pbi = XNEW (struct propagate_block_info);
1977
 
1978
  pbi->bb = bb;
1979
  pbi->reg_live = live;
1980
  pbi->mem_set_list = NULL_RTX;
1981
  pbi->mem_set_list_len = 0;
1982
  pbi->local_set = local_set;
1983
  pbi->cond_local_set = cond_local_set;
1984
  pbi->cc0_live = 0;
1985
  pbi->flags = flags;
1986
  pbi->insn_num = 0;
1987
 
1988
  if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
1989
    pbi->reg_next_use = XCNEWVEC (rtx, max_reg_num ());
1990
  else
1991
    pbi->reg_next_use = NULL;
1992
 
1993
  pbi->new_set = BITMAP_ALLOC (NULL);
1994
 
1995
#ifdef HAVE_conditional_execution
1996
  pbi->reg_cond_dead = splay_tree_new (splay_tree_compare_ints, NULL,
1997
                                       free_reg_cond_life_info);
1998
  pbi->reg_cond_reg = BITMAP_ALLOC (NULL);
1999
 
2000
  /* If this block ends in a conditional branch, for each register
2001
     live from one side of the branch and not the other, record the
2002
     register as conditionally dead.  */
2003
  if (JUMP_P (BB_END (bb))
2004
      && any_condjump_p (BB_END (bb)))
2005
    {
2006
      regset diff = ALLOC_REG_SET (&reg_obstack);
2007
      basic_block bb_true, bb_false;
2008
      unsigned i;
2009
 
2010
      /* Identify the successor blocks.  */
2011
      bb_true = EDGE_SUCC (bb, 0)->dest;
2012
      if (!single_succ_p (bb))
2013
        {
2014
          bb_false = EDGE_SUCC (bb, 1)->dest;
2015
 
2016
          if (EDGE_SUCC (bb, 0)->flags & EDGE_FALLTHRU)
2017
            {
2018
              basic_block t = bb_false;
2019
              bb_false = bb_true;
2020
              bb_true = t;
2021
            }
2022
          else
2023
            gcc_assert (EDGE_SUCC (bb, 1)->flags & EDGE_FALLTHRU);
2024
        }
2025
      else
2026
        {
2027
          /* This can happen with a conditional jump to the next insn.  */
2028
          gcc_assert (JUMP_LABEL (BB_END (bb)) == BB_HEAD (bb_true));
2029
 
2030
          /* Simplest way to do nothing.  */
2031
          bb_false = bb_true;
2032
        }
2033
 
2034
      /* Compute which register lead different lives in the successors.  */
2035
      bitmap_xor (diff, bb_true->il.rtl->global_live_at_start,
2036
                  bb_false->il.rtl->global_live_at_start);
2037
 
2038
      if (!bitmap_empty_p (diff))
2039
          {
2040
          /* Extract the condition from the branch.  */
2041
          rtx set_src = SET_SRC (pc_set (BB_END (bb)));
2042
          rtx cond_true = XEXP (set_src, 0);
2043
          rtx reg = XEXP (cond_true, 0);
2044
          enum rtx_code inv_cond;
2045
 
2046
          if (GET_CODE (reg) == SUBREG)
2047
            reg = SUBREG_REG (reg);
2048
 
2049
          /* We can only track conditional lifetimes if the condition is
2050
             in the form of a reversible comparison of a register against
2051
             zero.  If the condition is more complex than that, then it is
2052
             safe not to record any information.  */
2053
          inv_cond = reversed_comparison_code (cond_true, BB_END (bb));
2054
          if (inv_cond != UNKNOWN
2055
              && REG_P (reg)
2056
              && XEXP (cond_true, 1) == const0_rtx)
2057
            {
2058
              rtx cond_false
2059
                = gen_rtx_fmt_ee (inv_cond,
2060
                                  GET_MODE (cond_true), XEXP (cond_true, 0),
2061
                                  XEXP (cond_true, 1));
2062
              reg_set_iterator rsi;
2063
 
2064
              if (GET_CODE (XEXP (set_src, 1)) == PC)
2065
                {
2066
                  rtx t = cond_false;
2067
                  cond_false = cond_true;
2068
                  cond_true = t;
2069
                }
2070
 
2071
              SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (reg));
2072
 
2073
              /* For each such register, mark it conditionally dead.  */
2074
              EXECUTE_IF_SET_IN_REG_SET (diff, 0, i, rsi)
2075
                {
2076
                  struct reg_cond_life_info *rcli;
2077
                  rtx cond;
2078
 
2079
                  rcli = XNEW (struct reg_cond_life_info);
2080
 
2081
                  if (REGNO_REG_SET_P (bb_true->il.rtl->global_live_at_start,
2082
                                       i))
2083
                    cond = cond_false;
2084
                  else
2085
                    cond = cond_true;
2086
                  rcli->condition = cond;
2087
                  rcli->stores = const0_rtx;
2088
                  rcli->orig_condition = cond;
2089
 
2090
                  splay_tree_insert (pbi->reg_cond_dead, i,
2091
                                     (splay_tree_value) rcli);
2092
                }
2093
            }
2094
        }
2095
 
2096
      FREE_REG_SET (diff);
2097
    }
2098
#endif
2099
 
2100
  /* If this block has no successors, any stores to the frame that aren't
2101
     used later in the block are dead.  So make a pass over the block
2102
     recording any such that are made and show them dead at the end.  We do
2103
     a very conservative and simple job here.  */
2104
  if (optimize
2105
      && ! (TREE_CODE (TREE_TYPE (current_function_decl)) == FUNCTION_TYPE
2106
            && (TYPE_RETURNS_STACK_DEPRESSED
2107
                (TREE_TYPE (current_function_decl))))
2108
      && (flags & PROP_SCAN_DEAD_STORES)
2109
      && (EDGE_COUNT (bb->succs) == 0
2110
          || (single_succ_p (bb)
2111
              && single_succ (bb) == EXIT_BLOCK_PTR
2112
              && ! current_function_calls_eh_return)))
2113
    {
2114
      rtx insn, set;
2115
      for (insn = BB_END (bb); insn != BB_HEAD (bb); insn = PREV_INSN (insn))
2116
        if (NONJUMP_INSN_P (insn)
2117
            && (set = single_set (insn))
2118
            && MEM_P (SET_DEST (set)))
2119
          {
2120
            rtx mem = SET_DEST (set);
2121
            rtx canon_mem = canon_rtx (mem);
2122
 
2123
            if (XEXP (canon_mem, 0) == frame_pointer_rtx
2124
                || (GET_CODE (XEXP (canon_mem, 0)) == PLUS
2125
                    && XEXP (XEXP (canon_mem, 0), 0) == frame_pointer_rtx
2126
                    && GET_CODE (XEXP (XEXP (canon_mem, 0), 1)) == CONST_INT))
2127
              add_to_mem_set_list (pbi, canon_mem);
2128
          }
2129
    }
2130
 
2131
  return pbi;
2132
}
2133
 
2134
/* Release a propagate_block_info struct.  */
2135
 
2136
void
2137
free_propagate_block_info (struct propagate_block_info *pbi)
2138
{
2139
  free_EXPR_LIST_list (&pbi->mem_set_list);
2140
 
2141
  BITMAP_FREE (pbi->new_set);
2142
 
2143
#ifdef HAVE_conditional_execution
2144
  splay_tree_delete (pbi->reg_cond_dead);
2145
  BITMAP_FREE (pbi->reg_cond_reg);
2146
#endif
2147
 
2148
  if (pbi->flags & PROP_REG_INFO)
2149
    {
2150
      int num = pbi->insn_num;
2151
      unsigned i;
2152
      reg_set_iterator rsi;
2153
 
2154
      EXECUTE_IF_SET_IN_REG_SET (pbi->reg_live, 0, i, rsi)
2155
        {
2156
          REG_LIVE_LENGTH (i) += num - reg_deaths[i];
2157
          reg_deaths[i] = 0;
2158
        }
2159
    }
2160
  if (pbi->reg_next_use)
2161
    free (pbi->reg_next_use);
2162
 
2163
  free (pbi);
2164
}
2165
 
2166
/* Compute the registers live at the beginning of a basic block BB from
2167
   those live at the end.
2168
 
2169
   When called, REG_LIVE contains those live at the end.  On return, it
2170
   contains those live at the beginning.
2171
 
2172
   LOCAL_SET, if non-null, will be set with all registers killed
2173
   unconditionally by this basic block.
2174
   Likewise, COND_LOCAL_SET, if non-null, will be set with all registers
2175
   killed conditionally by this basic block.  If there is any unconditional
2176
   set of a register, then the corresponding bit will be set in LOCAL_SET
2177
   and cleared in COND_LOCAL_SET.
2178
   It is valid for LOCAL_SET and COND_LOCAL_SET to be the same set.  In this
2179
   case, the resulting set will be equal to the union of the two sets that
2180
   would otherwise be computed.
2181
 
2182
   Return nonzero if an INSN is deleted (i.e. by dead code removal).  */
2183
 
2184
int
2185
propagate_block (basic_block bb, regset live, regset local_set,
2186
                 regset cond_local_set, int flags)
2187
{
2188
  struct propagate_block_info *pbi;
2189
  rtx insn, prev;
2190
  int changed;
2191
 
2192
  pbi = init_propagate_block_info (bb, live, local_set, cond_local_set, flags);
2193
 
2194
  if (flags & PROP_REG_INFO)
2195
    {
2196
      unsigned i;
2197
      reg_set_iterator rsi;
2198
 
2199
      /* Process the regs live at the end of the block.
2200
         Mark them as not local to any one basic block.  */
2201
      EXECUTE_IF_SET_IN_REG_SET (live, 0, i, rsi)
2202
        REG_BASIC_BLOCK (i) = REG_BLOCK_GLOBAL;
2203
    }
2204
 
2205
  /* Scan the block an insn at a time from end to beginning.  */
2206
 
2207
  changed = 0;
2208
  for (insn = BB_END (bb); ; insn = prev)
2209
    {
2210
      /* If this is a call to `setjmp' et al, warn if any
2211
         non-volatile datum is live.  */
2212
      if ((flags & PROP_REG_INFO)
2213
          && CALL_P (insn)
2214
          && find_reg_note (insn, REG_SETJMP, NULL))
2215
        IOR_REG_SET (regs_live_at_setjmp, pbi->reg_live);
2216
 
2217
      prev = propagate_one_insn (pbi, insn);
2218
      if (!prev)
2219
        changed |= insn != get_insns ();
2220
      else
2221
        changed |= NEXT_INSN (prev) != insn;
2222
 
2223
      if (insn == BB_HEAD (bb))
2224
        break;
2225
    }
2226
 
2227
#ifdef EH_RETURN_DATA_REGNO
2228
  if (bb_has_eh_pred (bb))
2229
    {
2230
      unsigned int i;
2231
      for (i = 0; ; ++i)
2232
        {
2233
          unsigned regno = EH_RETURN_DATA_REGNO (i);
2234
          if (regno == INVALID_REGNUM)
2235
            break;
2236
          if (pbi->local_set)
2237
            {
2238
              CLEAR_REGNO_REG_SET (pbi->cond_local_set, regno);
2239
              SET_REGNO_REG_SET (pbi->local_set, regno);
2240
            }
2241
          if (REGNO_REG_SET_P (pbi->reg_live, regno))
2242
            SET_REGNO_REG_SET (pbi->new_set, regno);
2243
 
2244
          regs_ever_live[regno] = 1;
2245
        }
2246
    }
2247
#endif
2248
 
2249
  free_propagate_block_info (pbi);
2250
 
2251
  return changed;
2252
}
2253
 
2254
/* Return 1 if X (the body of an insn, or part of it) is just dead stores
2255
   (SET expressions whose destinations are registers dead after the insn).
2256
   NEEDED is the regset that says which regs are alive after the insn.
2257
 
2258
   Unless CALL_OK is nonzero, an insn is needed if it contains a CALL.
2259
 
2260
   If X is the entire body of an insn, NOTES contains the reg notes
2261
   pertaining to the insn.  */
2262
 
2263
static int
2264
insn_dead_p (struct propagate_block_info *pbi, rtx x, int call_ok,
2265
             rtx notes ATTRIBUTE_UNUSED)
2266
{
2267
  enum rtx_code code = GET_CODE (x);
2268
 
2269
  /* Don't eliminate insns that may trap.  */
2270
  if (flag_non_call_exceptions && may_trap_p (x))
2271
    return 0;
2272
 
2273
#ifdef AUTO_INC_DEC
2274
  /* As flow is invoked after combine, we must take existing AUTO_INC
2275
     expressions into account.  */
2276
  for (; notes; notes = XEXP (notes, 1))
2277
    {
2278
      if (REG_NOTE_KIND (notes) == REG_INC)
2279
        {
2280
          int regno = REGNO (XEXP (notes, 0));
2281
 
2282
          /* Don't delete insns to set global regs.  */
2283
          if ((regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2284
              || REGNO_REG_SET_P (pbi->reg_live, regno))
2285
            return 0;
2286
        }
2287
    }
2288
#endif
2289
 
2290
  /* If setting something that's a reg or part of one,
2291
     see if that register's altered value will be live.  */
2292
 
2293
  if (code == SET)
2294
    {
2295
      rtx r = SET_DEST (x);
2296
 
2297
#ifdef HAVE_cc0
2298
      if (GET_CODE (r) == CC0)
2299
        return ! pbi->cc0_live;
2300
#endif
2301
 
2302
      /* A SET that is a subroutine call cannot be dead.  */
2303
      if (GET_CODE (SET_SRC (x)) == CALL)
2304
        {
2305
          if (! call_ok)
2306
            return 0;
2307
        }
2308
 
2309
      /* Don't eliminate loads from volatile memory or volatile asms.  */
2310
      else if (volatile_refs_p (SET_SRC (x)))
2311
        return 0;
2312
 
2313
      if (MEM_P (r))
2314
        {
2315
          rtx temp, canon_r;
2316
 
2317
          if (MEM_VOLATILE_P (r) || GET_MODE (r) == BLKmode)
2318
            return 0;
2319
 
2320
          canon_r = canon_rtx (r);
2321
 
2322
          /* Walk the set of memory locations we are currently tracking
2323
             and see if one is an identical match to this memory location.
2324
             If so, this memory write is dead (remember, we're walking
2325
             backwards from the end of the block to the start).  Since
2326
             rtx_equal_p does not check the alias set or flags, we also
2327
             must have the potential for them to conflict (anti_dependence).  */
2328
          for (temp = pbi->mem_set_list; temp != 0; temp = XEXP (temp, 1))
2329
            if (anti_dependence (r, XEXP (temp, 0)))
2330
              {
2331
                rtx mem = XEXP (temp, 0);
2332
 
2333
                if (rtx_equal_p (XEXP (canon_r, 0), XEXP (mem, 0))
2334
                    && (GET_MODE_SIZE (GET_MODE (canon_r))
2335
                        <= GET_MODE_SIZE (GET_MODE (mem))))
2336
                  return 1;
2337
 
2338
#ifdef AUTO_INC_DEC
2339
                /* Check if memory reference matches an auto increment. Only
2340
                   post increment/decrement or modify are valid.  */
2341
                if (GET_MODE (mem) == GET_MODE (r)
2342
                    && (GET_CODE (XEXP (mem, 0)) == POST_DEC
2343
                        || GET_CODE (XEXP (mem, 0)) == POST_INC
2344
                        || GET_CODE (XEXP (mem, 0)) == POST_MODIFY)
2345
                    && GET_MODE (XEXP (mem, 0)) == GET_MODE (r)
2346
                    && rtx_equal_p (XEXP (XEXP (mem, 0), 0), XEXP (r, 0)))
2347
                  return 1;
2348
#endif
2349
              }
2350
        }
2351
      else
2352
        {
2353
          while (GET_CODE (r) == SUBREG
2354
                 || GET_CODE (r) == STRICT_LOW_PART
2355
                 || GET_CODE (r) == ZERO_EXTRACT)
2356
            r = XEXP (r, 0);
2357
 
2358
          if (REG_P (r))
2359
            {
2360
              int regno = REGNO (r);
2361
 
2362
              /* Obvious.  */
2363
              if (REGNO_REG_SET_P (pbi->reg_live, regno))
2364
                return 0;
2365
 
2366
              /* If this is a hard register, verify that subsequent
2367
                 words are not needed.  */
2368
              if (regno < FIRST_PSEUDO_REGISTER)
2369
                {
2370
                  int n = hard_regno_nregs[regno][GET_MODE (r)];
2371
 
2372
                  while (--n > 0)
2373
                    if (REGNO_REG_SET_P (pbi->reg_live, regno+n))
2374
                      return 0;
2375
                }
2376
 
2377
              /* Don't delete insns to set global regs.  */
2378
              if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno])
2379
                return 0;
2380
 
2381
              /* Make sure insns to set the stack pointer aren't deleted.  */
2382
              if (regno == STACK_POINTER_REGNUM)
2383
                return 0;
2384
 
2385
              /* ??? These bits might be redundant with the force live bits
2386
                 in calculate_global_regs_live.  We would delete from
2387
                 sequential sets; whether this actually affects real code
2388
                 for anything but the stack pointer I don't know.  */
2389
              /* Make sure insns to set the frame pointer aren't deleted.  */
2390
              if (regno == FRAME_POINTER_REGNUM
2391
                  && (! reload_completed || frame_pointer_needed))
2392
                return 0;
2393
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2394
              if (regno == HARD_FRAME_POINTER_REGNUM
2395
                  && (! reload_completed || frame_pointer_needed))
2396
                return 0;
2397
#endif
2398
 
2399
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2400
              /* Make sure insns to set arg pointer are never deleted
2401
                 (if the arg pointer isn't fixed, there will be a USE
2402
                 for it, so we can treat it normally).  */
2403
              if (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2404
                return 0;
2405
#endif
2406
 
2407
              /* Otherwise, the set is dead.  */
2408
              return 1;
2409
            }
2410
        }
2411
    }
2412
 
2413
  /* If performing several activities, insn is dead if each activity
2414
     is individually dead.  Also, CLOBBERs and USEs can be ignored; a
2415
     CLOBBER or USE that's inside a PARALLEL doesn't make the insn
2416
     worth keeping.  */
2417
  else if (code == PARALLEL)
2418
    {
2419
      int i = XVECLEN (x, 0);
2420
 
2421
      for (i--; i >= 0; i--)
2422
        if (GET_CODE (XVECEXP (x, 0, i)) != CLOBBER
2423
            && GET_CODE (XVECEXP (x, 0, i)) != USE
2424
            && ! insn_dead_p (pbi, XVECEXP (x, 0, i), call_ok, NULL_RTX))
2425
          return 0;
2426
 
2427
      return 1;
2428
    }
2429
 
2430
  /* A CLOBBER of a pseudo-register that is dead serves no purpose.  That
2431
     is not necessarily true for hard registers until after reload.  */
2432
  else if (code == CLOBBER)
2433
    {
2434
      if (REG_P (XEXP (x, 0))
2435
          && (REGNO (XEXP (x, 0)) >= FIRST_PSEUDO_REGISTER
2436
              || reload_completed)
2437
          && ! REGNO_REG_SET_P (pbi->reg_live, REGNO (XEXP (x, 0))))
2438
        return 1;
2439
    }
2440
 
2441
  /* ??? A base USE is a historical relic.  It ought not be needed anymore.
2442
     Instances where it is still used are either (1) temporary and the USE
2443
     escaped the pass, (2) cruft and the USE need not be emitted anymore,
2444
     or (3) hiding bugs elsewhere that are not properly representing data
2445
     flow.  */
2446
 
2447
  return 0;
2448
}
2449
 
2450
/* If INSN is the last insn in a libcall, and assuming INSN is dead,
2451
   return 1 if the entire library call is dead.
2452
   This is true if INSN copies a register (hard or pseudo)
2453
   and if the hard return reg of the call insn is dead.
2454
   (The caller should have tested the destination of the SET inside
2455
   INSN already for death.)
2456
 
2457
   If this insn doesn't just copy a register, then we don't
2458
   have an ordinary libcall.  In that case, cse could not have
2459
   managed to substitute the source for the dest later on,
2460
   so we can assume the libcall is dead.
2461
 
2462
   PBI is the block info giving pseudoregs live before this insn.
2463
   NOTE is the REG_RETVAL note of the insn.  */
2464
 
2465
static int
2466
libcall_dead_p (struct propagate_block_info *pbi, rtx note, rtx insn)
2467
{
2468
  rtx x = single_set (insn);
2469
 
2470
  if (x)
2471
    {
2472
      rtx r = SET_SRC (x);
2473
 
2474
      if (REG_P (r) || GET_CODE (r) == SUBREG)
2475
        {
2476
          rtx call = XEXP (note, 0);
2477
          rtx call_pat;
2478
          int i;
2479
 
2480
          /* Find the call insn.  */
2481
          while (call != insn && !CALL_P (call))
2482
            call = NEXT_INSN (call);
2483
 
2484
          /* If there is none, do nothing special,
2485
             since ordinary death handling can understand these insns.  */
2486
          if (call == insn)
2487
            return 0;
2488
 
2489
          /* See if the hard reg holding the value is dead.
2490
             If this is a PARALLEL, find the call within it.  */
2491
          call_pat = PATTERN (call);
2492
          if (GET_CODE (call_pat) == PARALLEL)
2493
            {
2494
              for (i = XVECLEN (call_pat, 0) - 1; i >= 0; i--)
2495
                if (GET_CODE (XVECEXP (call_pat, 0, i)) == SET
2496
                    && GET_CODE (SET_SRC (XVECEXP (call_pat, 0, i))) == CALL)
2497
                  break;
2498
 
2499
              /* This may be a library call that is returning a value
2500
                 via invisible pointer.  Do nothing special, since
2501
                 ordinary death handling can understand these insns.  */
2502
              if (i < 0)
2503
                return 0;
2504
 
2505
              call_pat = XVECEXP (call_pat, 0, i);
2506
            }
2507
 
2508
          if (! insn_dead_p (pbi, call_pat, 1, REG_NOTES (call)))
2509
            return 0;
2510
 
2511
          while ((insn = PREV_INSN (insn)) != call)
2512
            {
2513
              if (! INSN_P (insn))
2514
                continue;
2515
              if (! insn_dead_p (pbi, PATTERN (insn), 0, REG_NOTES (insn)))
2516
                return 0;
2517
            }
2518
          return 1;
2519
        }
2520
    }
2521
  return 0;
2522
}
2523
 
2524
/* 1 if register REGNO was alive at a place where `setjmp' was called
2525
   and was set more than once or is an argument.
2526
   Such regs may be clobbered by `longjmp'.  */
2527
 
2528
int
2529
regno_clobbered_at_setjmp (int regno)
2530
{
2531
  if (n_basic_blocks == NUM_FIXED_BLOCKS)
2532
    return 0;
2533
 
2534
  return ((REG_N_SETS (regno) > 1
2535
           || REGNO_REG_SET_P (ENTRY_BLOCK_PTR->il.rtl->global_live_at_end,
2536
                               regno))
2537
          && REGNO_REG_SET_P (regs_live_at_setjmp, regno));
2538
}
2539
 
2540
/* Add MEM to PBI->MEM_SET_LIST.  MEM should be canonical.  Respect the
2541
   maximal list size; look for overlaps in mode and select the largest.  */
2542
static void
2543
add_to_mem_set_list (struct propagate_block_info *pbi, rtx mem)
2544
{
2545
  rtx i;
2546
 
2547
  /* We don't know how large a BLKmode store is, so we must not
2548
     take them into consideration.  */
2549
  if (GET_MODE (mem) == BLKmode)
2550
    return;
2551
 
2552
  for (i = pbi->mem_set_list; i ; i = XEXP (i, 1))
2553
    {
2554
      rtx e = XEXP (i, 0);
2555
      if (rtx_equal_p (XEXP (mem, 0), XEXP (e, 0)))
2556
        {
2557
          if (GET_MODE_SIZE (GET_MODE (mem)) > GET_MODE_SIZE (GET_MODE (e)))
2558
            {
2559
#ifdef AUTO_INC_DEC
2560
              /* If we must store a copy of the mem, we can just modify
2561
                 the mode of the stored copy.  */
2562
              if (pbi->flags & PROP_AUTOINC)
2563
                PUT_MODE (e, GET_MODE (mem));
2564
              else
2565
#endif
2566
                XEXP (i, 0) = mem;
2567
            }
2568
          return;
2569
        }
2570
    }
2571
 
2572
  if (pbi->mem_set_list_len < PARAM_VALUE (PARAM_MAX_FLOW_MEMORY_LOCATIONS))
2573
    {
2574
#ifdef AUTO_INC_DEC
2575
      /* Store a copy of mem, otherwise the address may be
2576
         scrogged by find_auto_inc.  */
2577
      if (pbi->flags & PROP_AUTOINC)
2578
        mem = shallow_copy_rtx (mem);
2579
#endif
2580
      pbi->mem_set_list = alloc_EXPR_LIST (0, mem, pbi->mem_set_list);
2581
      pbi->mem_set_list_len++;
2582
    }
2583
}
2584
 
2585
/* INSN references memory, possibly using autoincrement addressing modes.
2586
   Find any entries on the mem_set_list that need to be invalidated due
2587
   to an address change.  */
2588
 
2589
static int
2590
invalidate_mems_from_autoinc (rtx *px, void *data)
2591
{
2592
  rtx x = *px;
2593
  struct propagate_block_info *pbi = data;
2594
 
2595
  if (GET_RTX_CLASS (GET_CODE (x)) == RTX_AUTOINC)
2596
    {
2597
      invalidate_mems_from_set (pbi, XEXP (x, 0));
2598
      return -1;
2599
    }
2600
 
2601
  return 0;
2602
}
2603
 
2604
/* EXP is a REG or MEM.  Remove any dependent entries from
2605
   pbi->mem_set_list.  */
2606
 
2607
static void
2608
invalidate_mems_from_set (struct propagate_block_info *pbi, rtx exp)
2609
{
2610
  rtx temp = pbi->mem_set_list;
2611
  rtx prev = NULL_RTX;
2612
  rtx next;
2613
 
2614
  while (temp)
2615
    {
2616
      next = XEXP (temp, 1);
2617
      if ((REG_P (exp) && reg_overlap_mentioned_p (exp, XEXP (temp, 0)))
2618
          /* When we get an EXP that is a mem here, we want to check if EXP
2619
             overlaps the *address* of any of the mems in the list (i.e. not
2620
             whether the mems actually overlap; that's done elsewhere).  */
2621
          || (MEM_P (exp)
2622
              && reg_overlap_mentioned_p (exp, XEXP (XEXP (temp, 0), 0))))
2623
        {
2624
          /* Splice this entry out of the list.  */
2625
          if (prev)
2626
            XEXP (prev, 1) = next;
2627
          else
2628
            pbi->mem_set_list = next;
2629
          free_EXPR_LIST_node (temp);
2630
          pbi->mem_set_list_len--;
2631
        }
2632
      else
2633
        prev = temp;
2634
      temp = next;
2635
    }
2636
}
2637
 
2638
/* Process the registers that are set within X.  Their bits are set to
2639
   1 in the regset DEAD, because they are dead prior to this insn.
2640
 
2641
   If INSN is nonzero, it is the insn being processed.
2642
 
2643
   FLAGS is the set of operations to perform.  */
2644
 
2645
static void
2646
mark_set_regs (struct propagate_block_info *pbi, rtx x, rtx insn)
2647
{
2648
  rtx cond = NULL_RTX;
2649
  rtx link;
2650
  enum rtx_code code;
2651
  int flags = pbi->flags;
2652
 
2653
  if (insn)
2654
    for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
2655
      {
2656
        if (REG_NOTE_KIND (link) == REG_INC)
2657
          mark_set_1 (pbi, SET, XEXP (link, 0),
2658
                      (GET_CODE (x) == COND_EXEC
2659
                       ? COND_EXEC_TEST (x) : NULL_RTX),
2660
                      insn, flags);
2661
      }
2662
 retry:
2663
  switch (code = GET_CODE (x))
2664
    {
2665
    case SET:
2666
      if (GET_CODE (XEXP (x, 1)) == ASM_OPERANDS)
2667
        flags |= PROP_ASM_SCAN;
2668
      /* Fall through */
2669
    case CLOBBER:
2670
      mark_set_1 (pbi, code, SET_DEST (x), cond, insn, flags);
2671
      return;
2672
 
2673
    case COND_EXEC:
2674
      cond = COND_EXEC_TEST (x);
2675
      x = COND_EXEC_CODE (x);
2676
      goto retry;
2677
 
2678
    case PARALLEL:
2679
      {
2680
        int i;
2681
 
2682
        /* We must scan forwards.  If we have an asm, we need to set
2683
           the PROP_ASM_SCAN flag before scanning the clobbers.  */
2684
        for (i = 0; i < XVECLEN (x, 0); i++)
2685
          {
2686
            rtx sub = XVECEXP (x, 0, i);
2687
            switch (code = GET_CODE (sub))
2688
              {
2689
              case COND_EXEC:
2690
                gcc_assert (!cond);
2691
 
2692
                cond = COND_EXEC_TEST (sub);
2693
                sub = COND_EXEC_CODE (sub);
2694
                if (GET_CODE (sub) == SET)
2695
                  goto mark_set;
2696
                if (GET_CODE (sub) == CLOBBER)
2697
                  goto mark_clob;
2698
                break;
2699
 
2700
              case SET:
2701
              mark_set:
2702
                if (GET_CODE (XEXP (sub, 1)) == ASM_OPERANDS)
2703
                  flags |= PROP_ASM_SCAN;
2704
                /* Fall through */
2705
              case CLOBBER:
2706
              mark_clob:
2707
                mark_set_1 (pbi, code, SET_DEST (sub), cond, insn, flags);
2708
                break;
2709
 
2710
              case ASM_OPERANDS:
2711
                flags |= PROP_ASM_SCAN;
2712
                break;
2713
 
2714
              default:
2715
                break;
2716
              }
2717
          }
2718
        break;
2719
      }
2720
 
2721
    default:
2722
      break;
2723
    }
2724
}
2725
 
2726
/* Process a single set, which appears in INSN.  REG (which may not
2727
   actually be a REG, it may also be a SUBREG, PARALLEL, etc.) is
2728
   being set using the CODE (which may be SET, CLOBBER, or COND_EXEC).
2729
   If the set is conditional (because it appear in a COND_EXEC), COND
2730
   will be the condition.  */
2731
 
2732
static void
2733
mark_set_1 (struct propagate_block_info *pbi, enum rtx_code code, rtx reg, rtx cond, rtx insn, int flags)
2734
{
2735
  int regno_first = -1, regno_last = -1;
2736
  unsigned long not_dead = 0;
2737
  int i;
2738
 
2739
  /* Modifying just one hardware register of a multi-reg value or just a
2740
     byte field of a register does not mean the value from before this insn
2741
     is now dead.  Of course, if it was dead after it's unused now.  */
2742
 
2743
  switch (GET_CODE (reg))
2744
    {
2745
    case PARALLEL:
2746
      /* Some targets place small structures in registers for return values of
2747
         functions.  We have to detect this case specially here to get correct
2748
         flow information.  */
2749
      for (i = XVECLEN (reg, 0) - 1; i >= 0; i--)
2750
        if (XEXP (XVECEXP (reg, 0, i), 0) != 0)
2751
          mark_set_1 (pbi, code, XEXP (XVECEXP (reg, 0, i), 0), cond, insn,
2752
                      flags);
2753
      return;
2754
 
2755
    case SIGN_EXTRACT:
2756
      /* SIGN_EXTRACT cannot be an lvalue.  */
2757
      gcc_unreachable ();
2758
 
2759
    case ZERO_EXTRACT:
2760
    case STRICT_LOW_PART:
2761
      /* ??? Assumes STRICT_LOW_PART not used on multi-word registers.  */
2762
      do
2763
        reg = XEXP (reg, 0);
2764
      while (GET_CODE (reg) == SUBREG
2765
             || GET_CODE (reg) == ZERO_EXTRACT
2766
             || GET_CODE (reg) == STRICT_LOW_PART);
2767
      if (MEM_P (reg))
2768
        break;
2769
      not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live, REGNO (reg));
2770
      /* Fall through.  */
2771
 
2772
    case REG:
2773
      regno_last = regno_first = REGNO (reg);
2774
      if (regno_first < FIRST_PSEUDO_REGISTER)
2775
        regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1;
2776
      break;
2777
 
2778
    case SUBREG:
2779
      if (REG_P (SUBREG_REG (reg)))
2780
        {
2781
          enum machine_mode outer_mode = GET_MODE (reg);
2782
          enum machine_mode inner_mode = GET_MODE (SUBREG_REG (reg));
2783
 
2784
          /* Identify the range of registers affected.  This is moderately
2785
             tricky for hard registers.  See alter_subreg.  */
2786
 
2787
          regno_last = regno_first = REGNO (SUBREG_REG (reg));
2788
          if (regno_first < FIRST_PSEUDO_REGISTER)
2789
            {
2790
              regno_first += subreg_regno_offset (regno_first, inner_mode,
2791
                                                  SUBREG_BYTE (reg),
2792
                                                  outer_mode);
2793
              regno_last = (regno_first
2794
                            + hard_regno_nregs[regno_first][outer_mode] - 1);
2795
 
2796
              /* Since we've just adjusted the register number ranges, make
2797
                 sure REG matches.  Otherwise some_was_live will be clear
2798
                 when it shouldn't have been, and we'll create incorrect
2799
                 REG_UNUSED notes.  */
2800
              reg = gen_rtx_REG (outer_mode, regno_first);
2801
            }
2802
          else
2803
            {
2804
              /* If the number of words in the subreg is less than the number
2805
                 of words in the full register, we have a well-defined partial
2806
                 set.  Otherwise the high bits are undefined.
2807
 
2808
                 This is only really applicable to pseudos, since we just took
2809
                 care of multi-word hard registers.  */
2810
              if (((GET_MODE_SIZE (outer_mode)
2811
                    + UNITS_PER_WORD - 1) / UNITS_PER_WORD)
2812
                  < ((GET_MODE_SIZE (inner_mode)
2813
                      + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
2814
                not_dead = (unsigned long) REGNO_REG_SET_P (pbi->reg_live,
2815
                                                            regno_first);
2816
 
2817
              reg = SUBREG_REG (reg);
2818
            }
2819
        }
2820
      else
2821
        reg = SUBREG_REG (reg);
2822
      break;
2823
 
2824
    default:
2825
      break;
2826
    }
2827
 
2828
  /* If this set is a MEM, then it kills any aliased writes and any
2829
     other MEMs which use it.
2830
     If this set is a REG, then it kills any MEMs which use the reg.  */
2831
  if (optimize && (flags & PROP_SCAN_DEAD_STORES))
2832
    {
2833
      if (REG_P (reg) || MEM_P (reg))
2834
        invalidate_mems_from_set (pbi, reg);
2835
 
2836
      /* If the memory reference had embedded side effects (autoincrement
2837
         address modes) then we may need to kill some entries on the
2838
         memory set list.  */
2839
      if (insn && MEM_P (reg))
2840
        for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi);
2841
 
2842
      if (MEM_P (reg) && ! side_effects_p (reg)
2843
          /* ??? With more effort we could track conditional memory life.  */
2844
          && ! cond)
2845
        add_to_mem_set_list (pbi, canon_rtx (reg));
2846
    }
2847
 
2848
  if (REG_P (reg)
2849
      && ! (regno_first == FRAME_POINTER_REGNUM
2850
            && (! reload_completed || frame_pointer_needed))
2851
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
2852
      && ! (regno_first == HARD_FRAME_POINTER_REGNUM
2853
            && (! reload_completed || frame_pointer_needed))
2854
#endif
2855
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
2856
      && ! (regno_first == ARG_POINTER_REGNUM && fixed_regs[regno_first])
2857
#endif
2858
      )
2859
    {
2860
      int some_was_live = 0, some_was_dead = 0;
2861
 
2862
      for (i = regno_first; i <= regno_last; ++i)
2863
        {
2864
          int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
2865
          if (pbi->local_set)
2866
            {
2867
              /* Order of the set operation matters here since both
2868
                 sets may be the same.  */
2869
              CLEAR_REGNO_REG_SET (pbi->cond_local_set, i);
2870
              if (cond != NULL_RTX
2871
                  && ! REGNO_REG_SET_P (pbi->local_set, i))
2872
                SET_REGNO_REG_SET (pbi->cond_local_set, i);
2873
              else
2874
                SET_REGNO_REG_SET (pbi->local_set, i);
2875
            }
2876
          if (code != CLOBBER || needed_regno)
2877
            SET_REGNO_REG_SET (pbi->new_set, i);
2878
 
2879
          some_was_live |= needed_regno;
2880
          some_was_dead |= ! needed_regno;
2881
        }
2882
 
2883
#ifdef HAVE_conditional_execution
2884
      /* Consider conditional death in deciding that the register needs
2885
         a death note.  */
2886
      if (some_was_live && ! not_dead
2887
          /* The stack pointer is never dead.  Well, not strictly true,
2888
             but it's very difficult to tell from here.  Hopefully
2889
             combine_stack_adjustments will fix up the most egregious
2890
             errors.  */
2891
          && regno_first != STACK_POINTER_REGNUM)
2892
        {
2893
          for (i = regno_first; i <= regno_last; ++i)
2894
            if (! mark_regno_cond_dead (pbi, i, cond))
2895
              not_dead |= ((unsigned long) 1) << (i - regno_first);
2896
        }
2897
#endif
2898
 
2899
      /* Additional data to record if this is the final pass.  */
2900
      if (flags & (PROP_LOG_LINKS | PROP_REG_INFO
2901
                   | PROP_DEATH_NOTES | PROP_AUTOINC))
2902
        {
2903
          rtx y;
2904
          int blocknum = pbi->bb->index;
2905
 
2906
          y = NULL_RTX;
2907
          if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
2908
            {
2909
              y = pbi->reg_next_use[regno_first];
2910
 
2911
              /* The next use is no longer next, since a store intervenes.  */
2912
              for (i = regno_first; i <= regno_last; ++i)
2913
                pbi->reg_next_use[i] = 0;
2914
            }
2915
 
2916
          if (flags & PROP_REG_INFO)
2917
            {
2918
              for (i = regno_first; i <= regno_last; ++i)
2919
                {
2920
                  /* Count (weighted) references, stores, etc.  This counts a
2921
                     register twice if it is modified, but that is correct.  */
2922
                  REG_N_SETS (i) += 1;
2923
                  REG_N_REFS (i) += 1;
2924
                  REG_FREQ (i) += REG_FREQ_FROM_BB (pbi->bb);
2925
 
2926
                  /* The insns where a reg is live are normally counted
2927
                     elsewhere, but we want the count to include the insn
2928
                     where the reg is set, and the normal counting mechanism
2929
                     would not count it.  */
2930
                  REG_LIVE_LENGTH (i) += 1;
2931
                }
2932
 
2933
              /* If this is a hard reg, record this function uses the reg.  */
2934
              if (regno_first < FIRST_PSEUDO_REGISTER)
2935
                {
2936
                  for (i = regno_first; i <= regno_last; i++)
2937
                    regs_ever_live[i] = 1;
2938
                  if (flags & PROP_ASM_SCAN)
2939
                    for (i = regno_first; i <= regno_last; i++)
2940
                      regs_asm_clobbered[i] = 1;
2941
                }
2942
              else
2943
                {
2944
                  /* Keep track of which basic blocks each reg appears in.  */
2945
                  if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
2946
                    REG_BASIC_BLOCK (regno_first) = blocknum;
2947
                  else if (REG_BASIC_BLOCK (regno_first) != blocknum)
2948
                    REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
2949
                }
2950
            }
2951
 
2952
          if (! some_was_dead)
2953
            {
2954
              if (flags & PROP_LOG_LINKS)
2955
                {
2956
                  /* Make a logical link from the next following insn
2957
                     that uses this register, back to this insn.
2958
                     The following insns have already been processed.
2959
 
2960
                     We don't build a LOG_LINK for hard registers containing
2961
                     in ASM_OPERANDs.  If these registers get replaced,
2962
                     we might wind up changing the semantics of the insn,
2963
                     even if reload can make what appear to be valid
2964
                     assignments later.
2965
 
2966
                     We don't build a LOG_LINK for global registers to
2967
                     or from a function call.  We don't want to let
2968
                     combine think that it knows what is going on with
2969
                     global registers.  */
2970
                  if (y && (BLOCK_NUM (y) == blocknum)
2971
                      && (regno_first >= FIRST_PSEUDO_REGISTER
2972
                          || (asm_noperands (PATTERN (y)) < 0
2973
                              && ! ((CALL_P (insn)
2974
                                     || CALL_P (y))
2975
                                    && global_regs[regno_first]))))
2976
                    LOG_LINKS (y) = alloc_INSN_LIST (insn, LOG_LINKS (y));
2977
                }
2978
            }
2979
          else if (not_dead)
2980
            ;
2981
          else if (! some_was_live)
2982
            {
2983
              if (flags & PROP_REG_INFO)
2984
                REG_N_DEATHS (regno_first) += 1;
2985
 
2986
              if (flags & PROP_DEATH_NOTES
2987
#ifdef STACK_REGS
2988
                  && (!(flags & PROP_POST_REGSTACK)
2989
                      || !IN_RANGE (REGNO (reg), FIRST_STACK_REG,
2990
                                    LAST_STACK_REG))
2991
#endif
2992
                  )
2993
                {
2994
                  /* Note that dead stores have already been deleted
2995
                     when possible.  If we get here, we have found a
2996
                     dead store that cannot be eliminated (because the
2997
                     same insn does something useful).  Indicate this
2998
                     by marking the reg being set as dying here.  */
2999
                  REG_NOTES (insn)
3000
                    = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
3001
                }
3002
            }
3003
          else
3004
            {
3005
              if (flags & PROP_DEATH_NOTES
3006
#ifdef STACK_REGS
3007
                  && (!(flags & PROP_POST_REGSTACK)
3008
                      || !IN_RANGE (REGNO (reg), FIRST_STACK_REG,
3009
                                    LAST_STACK_REG))
3010
#endif
3011
                  )
3012
                {
3013
                  /* This is a case where we have a multi-word hard register
3014
                     and some, but not all, of the words of the register are
3015
                     needed in subsequent insns.  Write REG_UNUSED notes
3016
                     for those parts that were not needed.  This case should
3017
                     be rare.  */
3018
 
3019
                  for (i = regno_first; i <= regno_last; ++i)
3020
                    if (! REGNO_REG_SET_P (pbi->reg_live, i))
3021
                      REG_NOTES (insn)
3022
                        = alloc_EXPR_LIST (REG_UNUSED,
3023
                                           regno_reg_rtx[i],
3024
                                           REG_NOTES (insn));
3025
                }
3026
            }
3027
        }
3028
 
3029
      /* Mark the register as being dead.  */
3030
      if (some_was_live
3031
          /* The stack pointer is never dead.  Well, not strictly true,
3032
             but it's very difficult to tell from here.  Hopefully
3033
             combine_stack_adjustments will fix up the most egregious
3034
             errors.  */
3035
          && regno_first != STACK_POINTER_REGNUM)
3036
        {
3037
          for (i = regno_first; i <= regno_last; ++i)
3038
            if (!(not_dead & (((unsigned long) 1) << (i - regno_first))))
3039
              {
3040
                if ((pbi->flags & PROP_REG_INFO)
3041
                    && REGNO_REG_SET_P (pbi->reg_live, i))
3042
                  {
3043
                    REG_LIVE_LENGTH (i) += pbi->insn_num - reg_deaths[i];
3044
                    reg_deaths[i] = 0;
3045
                  }
3046
                CLEAR_REGNO_REG_SET (pbi->reg_live, i);
3047
              }
3048
          if (flags & PROP_DEAD_INSN)
3049
            emit_insn_after (gen_rtx_CLOBBER (VOIDmode, reg), insn);
3050
        }
3051
    }
3052
  else if (REG_P (reg))
3053
    {
3054
      if (flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3055
        pbi->reg_next_use[regno_first] = 0;
3056
 
3057
      if ((flags & PROP_REG_INFO) != 0
3058
          && (flags & PROP_ASM_SCAN) != 0
3059
          &&  regno_first < FIRST_PSEUDO_REGISTER)
3060
        {
3061
          for (i = regno_first; i <= regno_last; i++)
3062
            regs_asm_clobbered[i] = 1;
3063
        }
3064
    }
3065
 
3066
  /* If this is the last pass and this is a SCRATCH, show it will be dying
3067
     here and count it.  */
3068
  else if (GET_CODE (reg) == SCRATCH)
3069
    {
3070
      if (flags & PROP_DEATH_NOTES
3071
#ifdef STACK_REGS
3072
          && (!(flags & PROP_POST_REGSTACK)
3073
              || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, LAST_STACK_REG))
3074
#endif
3075
          )
3076
        REG_NOTES (insn)
3077
          = alloc_EXPR_LIST (REG_UNUSED, reg, REG_NOTES (insn));
3078
    }
3079
}
3080
 
3081
#ifdef HAVE_conditional_execution
3082
/* Mark REGNO conditionally dead.
3083
   Return true if the register is now unconditionally dead.  */
3084
 
3085
static int
3086
mark_regno_cond_dead (struct propagate_block_info *pbi, int regno, rtx cond)
3087
{
3088
  /* If this is a store to a predicate register, the value of the
3089
     predicate is changing, we don't know that the predicate as seen
3090
     before is the same as that seen after.  Flush all dependent
3091
     conditions from reg_cond_dead.  This will make all such
3092
     conditionally live registers unconditionally live.  */
3093
  if (REGNO_REG_SET_P (pbi->reg_cond_reg, regno))
3094
    flush_reg_cond_reg (pbi, regno);
3095
 
3096
  /* If this is an unconditional store, remove any conditional
3097
     life that may have existed.  */
3098
  if (cond == NULL_RTX)
3099
    splay_tree_remove (pbi->reg_cond_dead, regno);
3100
  else
3101
    {
3102
      splay_tree_node node;
3103
      struct reg_cond_life_info *rcli;
3104
      rtx ncond;
3105
 
3106
      /* Otherwise this is a conditional set.  Record that fact.
3107
         It may have been conditionally used, or there may be a
3108
         subsequent set with a complementary condition.  */
3109
 
3110
      node = splay_tree_lookup (pbi->reg_cond_dead, regno);
3111
      if (node == NULL)
3112
        {
3113
          /* The register was unconditionally live previously.
3114
             Record the current condition as the condition under
3115
             which it is dead.  */
3116
          rcli = XNEW (struct reg_cond_life_info);
3117
          rcli->condition = cond;
3118
          rcli->stores = cond;
3119
          rcli->orig_condition = const0_rtx;
3120
          splay_tree_insert (pbi->reg_cond_dead, regno,
3121
                             (splay_tree_value) rcli);
3122
 
3123
          SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3124
 
3125
          /* Not unconditionally dead.  */
3126
          return 0;
3127
        }
3128
      else
3129
        {
3130
          /* The register was conditionally live previously.
3131
             Add the new condition to the old.  */
3132
          rcli = (struct reg_cond_life_info *) node->value;
3133
          ncond = rcli->condition;
3134
          ncond = ior_reg_cond (ncond, cond, 1);
3135
          if (rcli->stores == const0_rtx)
3136
            rcli->stores = cond;
3137
          else if (rcli->stores != const1_rtx)
3138
            rcli->stores = ior_reg_cond (rcli->stores, cond, 1);
3139
 
3140
          /* If the register is now unconditionally dead, remove the entry
3141
             in the splay_tree.  A register is unconditionally dead if the
3142
             dead condition ncond is true.  A register is also unconditionally
3143
             dead if the sum of all conditional stores is an unconditional
3144
             store (stores is true), and the dead condition is identically the
3145
             same as the original dead condition initialized at the end of
3146
             the block.  This is a pointer compare, not an rtx_equal_p
3147
             compare.  */
3148
          if (ncond == const1_rtx
3149
              || (ncond == rcli->orig_condition && rcli->stores == const1_rtx))
3150
            splay_tree_remove (pbi->reg_cond_dead, regno);
3151
          else
3152
            {
3153
              rcli->condition = ncond;
3154
 
3155
              SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3156
 
3157
              /* Not unconditionally dead.  */
3158
              return 0;
3159
            }
3160
        }
3161
    }
3162
 
3163
  return 1;
3164
}
3165
 
3166
/* Called from splay_tree_delete for pbi->reg_cond_life.  */
3167
 
3168
static void
3169
free_reg_cond_life_info (splay_tree_value value)
3170
{
3171
  struct reg_cond_life_info *rcli = (struct reg_cond_life_info *) value;
3172
  free (rcli);
3173
}
3174
 
3175
/* Helper function for flush_reg_cond_reg.  */
3176
 
3177
static int
3178
flush_reg_cond_reg_1 (splay_tree_node node, void *data)
3179
{
3180
  struct reg_cond_life_info *rcli;
3181
  int *xdata = (int *) data;
3182
  unsigned int regno = xdata[0];
3183
 
3184
  /* Don't need to search if last flushed value was farther on in
3185
     the in-order traversal.  */
3186
  if (xdata[1] >= (int) node->key)
3187
    return 0;
3188
 
3189
  /* Splice out portions of the expression that refer to regno.  */
3190
  rcli = (struct reg_cond_life_info *) node->value;
3191
  rcli->condition = elim_reg_cond (rcli->condition, regno);
3192
  if (rcli->stores != const0_rtx && rcli->stores != const1_rtx)
3193
    rcli->stores = elim_reg_cond (rcli->stores, regno);
3194
 
3195
  /* If the entire condition is now false, signal the node to be removed.  */
3196
  if (rcli->condition == const0_rtx)
3197
    {
3198
      xdata[1] = node->key;
3199
      return -1;
3200
    }
3201
  else
3202
    gcc_assert (rcli->condition != const1_rtx);
3203
 
3204
  return 0;
3205
}
3206
 
3207
/* Flush all (sub) expressions referring to REGNO from REG_COND_LIVE.  */
3208
 
3209
static void
3210
flush_reg_cond_reg (struct propagate_block_info *pbi, int regno)
3211
{
3212
  int pair[2];
3213
 
3214
  pair[0] = regno;
3215
  pair[1] = -1;
3216
  while (splay_tree_foreach (pbi->reg_cond_dead,
3217
                             flush_reg_cond_reg_1, pair) == -1)
3218
    splay_tree_remove (pbi->reg_cond_dead, pair[1]);
3219
 
3220
  CLEAR_REGNO_REG_SET (pbi->reg_cond_reg, regno);
3221
}
3222
 
3223
/* Logical arithmetic on predicate conditions.  IOR, NOT and AND.
3224
   For ior/and, the ADD flag determines whether we want to add the new
3225
   condition X to the old one unconditionally.  If it is zero, we will
3226
   only return a new expression if X allows us to simplify part of
3227
   OLD, otherwise we return NULL to the caller.
3228
   If ADD is nonzero, we will return a new condition in all cases.  The
3229
   toplevel caller of one of these functions should always pass 1 for
3230
   ADD.  */
3231
 
3232
static rtx
3233
ior_reg_cond (rtx old, rtx x, int add)
3234
{
3235
  rtx op0, op1;
3236
 
3237
  if (COMPARISON_P (old))
3238
    {
3239
      if (COMPARISON_P (x)
3240
          && REVERSE_CONDEXEC_PREDICATES_P (x, old)
3241
          && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3242
        return const1_rtx;
3243
      if (GET_CODE (x) == GET_CODE (old)
3244
          && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3245
        return old;
3246
      if (! add)
3247
        return NULL;
3248
      return gen_rtx_IOR (0, old, x);
3249
    }
3250
 
3251
  switch (GET_CODE (old))
3252
    {
3253
    case IOR:
3254
      op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3255
      op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3256
      if (op0 != NULL || op1 != NULL)
3257
        {
3258
          if (op0 == const0_rtx)
3259
            return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3260
          if (op1 == const0_rtx)
3261
            return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3262
          if (op0 == const1_rtx || op1 == const1_rtx)
3263
            return const1_rtx;
3264
          if (op0 == NULL)
3265
            op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3266
          else if (rtx_equal_p (x, op0))
3267
            /* (x | A) | x ~ (x | A).  */
3268
            return old;
3269
          if (op1 == NULL)
3270
            op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3271
          else if (rtx_equal_p (x, op1))
3272
            /* (A | x) | x ~ (A | x).  */
3273
            return old;
3274
          return gen_rtx_IOR (0, op0, op1);
3275
        }
3276
      if (! add)
3277
        return NULL;
3278
      return gen_rtx_IOR (0, old, x);
3279
 
3280
    case AND:
3281
      op0 = ior_reg_cond (XEXP (old, 0), x, 0);
3282
      op1 = ior_reg_cond (XEXP (old, 1), x, 0);
3283
      if (op0 != NULL || op1 != NULL)
3284
        {
3285
          if (op0 == const1_rtx)
3286
            return op1 ? op1 : gen_rtx_IOR (0, XEXP (old, 1), x);
3287
          if (op1 == const1_rtx)
3288
            return op0 ? op0 : gen_rtx_IOR (0, XEXP (old, 0), x);
3289
          if (op0 == const0_rtx || op1 == const0_rtx)
3290
            return const0_rtx;
3291
          if (op0 == NULL)
3292
            op0 = gen_rtx_IOR (0, XEXP (old, 0), x);
3293
          else if (rtx_equal_p (x, op0))
3294
            /* (x & A) | x ~ x.  */
3295
            return op0;
3296
          if (op1 == NULL)
3297
            op1 = gen_rtx_IOR (0, XEXP (old, 1), x);
3298
          else if (rtx_equal_p (x, op1))
3299
            /* (A & x) | x ~ x.  */
3300
            return op1;
3301
          return gen_rtx_AND (0, op0, op1);
3302
        }
3303
      if (! add)
3304
        return NULL;
3305
      return gen_rtx_IOR (0, old, x);
3306
 
3307
    case NOT:
3308
      op0 = and_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3309
      if (op0 != NULL)
3310
        return not_reg_cond (op0);
3311
      if (! add)
3312
        return NULL;
3313
      return gen_rtx_IOR (0, old, x);
3314
 
3315
    default:
3316
      gcc_unreachable ();
3317
    }
3318
}
3319
 
3320
static rtx
3321
not_reg_cond (rtx x)
3322
{
3323
  if (x == const0_rtx)
3324
    return const1_rtx;
3325
  else if (x == const1_rtx)
3326
    return const0_rtx;
3327
  if (GET_CODE (x) == NOT)
3328
    return XEXP (x, 0);
3329
  if (COMPARISON_P (x)
3330
      && REG_P (XEXP (x, 0)))
3331
    {
3332
      gcc_assert (XEXP (x, 1) == const0_rtx);
3333
 
3334
      return gen_rtx_fmt_ee (reversed_comparison_code (x, NULL),
3335
                             VOIDmode, XEXP (x, 0), const0_rtx);
3336
    }
3337
  return gen_rtx_NOT (0, x);
3338
}
3339
 
3340
static rtx
3341
and_reg_cond (rtx old, rtx x, int add)
3342
{
3343
  rtx op0, op1;
3344
 
3345
  if (COMPARISON_P (old))
3346
    {
3347
      if (COMPARISON_P (x)
3348
          && GET_CODE (x) == reversed_comparison_code (old, NULL)
3349
          && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3350
        return const0_rtx;
3351
      if (GET_CODE (x) == GET_CODE (old)
3352
          && REGNO (XEXP (x, 0)) == REGNO (XEXP (old, 0)))
3353
        return old;
3354
      if (! add)
3355
        return NULL;
3356
      return gen_rtx_AND (0, old, x);
3357
    }
3358
 
3359
  switch (GET_CODE (old))
3360
    {
3361
    case IOR:
3362
      op0 = and_reg_cond (XEXP (old, 0), x, 0);
3363
      op1 = and_reg_cond (XEXP (old, 1), x, 0);
3364
      if (op0 != NULL || op1 != NULL)
3365
        {
3366
          if (op0 == const0_rtx)
3367
            return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3368
          if (op1 == const0_rtx)
3369
            return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3370
          if (op0 == const1_rtx || op1 == const1_rtx)
3371
            return const1_rtx;
3372
          if (op0 == NULL)
3373
            op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3374
          else if (rtx_equal_p (x, op0))
3375
            /* (x | A) & x ~ x.  */
3376
            return op0;
3377
          if (op1 == NULL)
3378
            op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3379
          else if (rtx_equal_p (x, op1))
3380
            /* (A | x) & x ~ x.  */
3381
            return op1;
3382
          return gen_rtx_IOR (0, op0, op1);
3383
        }
3384
      if (! add)
3385
        return NULL;
3386
      return gen_rtx_AND (0, old, x);
3387
 
3388
    case AND:
3389
      op0 = and_reg_cond (XEXP (old, 0), x, 0);
3390
      op1 = and_reg_cond (XEXP (old, 1), x, 0);
3391
      if (op0 != NULL || op1 != NULL)
3392
        {
3393
          if (op0 == const1_rtx)
3394
            return op1 ? op1 : gen_rtx_AND (0, XEXP (old, 1), x);
3395
          if (op1 == const1_rtx)
3396
            return op0 ? op0 : gen_rtx_AND (0, XEXP (old, 0), x);
3397
          if (op0 == const0_rtx || op1 == const0_rtx)
3398
            return const0_rtx;
3399
          if (op0 == NULL)
3400
            op0 = gen_rtx_AND (0, XEXP (old, 0), x);
3401
          else if (rtx_equal_p (x, op0))
3402
            /* (x & A) & x ~ (x & A).  */
3403
            return old;
3404
          if (op1 == NULL)
3405
            op1 = gen_rtx_AND (0, XEXP (old, 1), x);
3406
          else if (rtx_equal_p (x, op1))
3407
            /* (A & x) & x ~ (A & x).  */
3408
            return old;
3409
          return gen_rtx_AND (0, op0, op1);
3410
        }
3411
      if (! add)
3412
        return NULL;
3413
      return gen_rtx_AND (0, old, x);
3414
 
3415
    case NOT:
3416
      op0 = ior_reg_cond (XEXP (old, 0), not_reg_cond (x), 0);
3417
      if (op0 != NULL)
3418
        return not_reg_cond (op0);
3419
      if (! add)
3420
        return NULL;
3421
      return gen_rtx_AND (0, old, x);
3422
 
3423
    default:
3424
      gcc_unreachable ();
3425
    }
3426
}
3427
 
3428
/* Given a condition X, remove references to reg REGNO and return the
3429
   new condition.  The removal will be done so that all conditions
3430
   involving REGNO are considered to evaluate to false.  This function
3431
   is used when the value of REGNO changes.  */
3432
 
3433
static rtx
3434
elim_reg_cond (rtx x, unsigned int regno)
3435
{
3436
  rtx op0, op1;
3437
 
3438
  if (COMPARISON_P (x))
3439
    {
3440
      if (REGNO (XEXP (x, 0)) == regno)
3441
        return const0_rtx;
3442
      return x;
3443
    }
3444
 
3445
  switch (GET_CODE (x))
3446
    {
3447
    case AND:
3448
      op0 = elim_reg_cond (XEXP (x, 0), regno);
3449
      op1 = elim_reg_cond (XEXP (x, 1), regno);
3450
      if (op0 == const0_rtx || op1 == const0_rtx)
3451
        return const0_rtx;
3452
      if (op0 == const1_rtx)
3453
        return op1;
3454
      if (op1 == const1_rtx)
3455
        return op0;
3456
      if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3457
        return x;
3458
      return gen_rtx_AND (0, op0, op1);
3459
 
3460
    case IOR:
3461
      op0 = elim_reg_cond (XEXP (x, 0), regno);
3462
      op1 = elim_reg_cond (XEXP (x, 1), regno);
3463
      if (op0 == const1_rtx || op1 == const1_rtx)
3464
        return const1_rtx;
3465
      if (op0 == const0_rtx)
3466
        return op1;
3467
      if (op1 == const0_rtx)
3468
        return op0;
3469
      if (op0 == XEXP (x, 0) && op1 == XEXP (x, 1))
3470
        return x;
3471
      return gen_rtx_IOR (0, op0, op1);
3472
 
3473
    case NOT:
3474
      op0 = elim_reg_cond (XEXP (x, 0), regno);
3475
      if (op0 == const0_rtx)
3476
        return const1_rtx;
3477
      if (op0 == const1_rtx)
3478
        return const0_rtx;
3479
      if (op0 != XEXP (x, 0))
3480
        return not_reg_cond (op0);
3481
      return x;
3482
 
3483
    default:
3484
      gcc_unreachable ();
3485
    }
3486
}
3487
#endif /* HAVE_conditional_execution */
3488
 
3489
#ifdef AUTO_INC_DEC
3490
 
3491
/* Try to substitute the auto-inc expression INC as the address inside
3492
   MEM which occurs in INSN.  Currently, the address of MEM is an expression
3493
   involving INCR_REG, and INCR is the next use of INCR_REG; it is an insn
3494
   that has a single set whose source is a PLUS of INCR_REG and something
3495
   else.  */
3496
 
3497
static void
3498
attempt_auto_inc (struct propagate_block_info *pbi, rtx inc, rtx insn,
3499
                  rtx mem, rtx incr, rtx incr_reg)
3500
{
3501
  int regno = REGNO (incr_reg);
3502
  rtx set = single_set (incr);
3503
  rtx q = SET_DEST (set);
3504
  rtx y = SET_SRC (set);
3505
  int opnum = XEXP (y, 0) == incr_reg ? 0 : 1;
3506
  int changed;
3507
 
3508
  /* Make sure this reg appears only once in this insn.  */
3509
  if (count_occurrences (PATTERN (insn), incr_reg, 1) != 1)
3510
    return;
3511
 
3512
  if (dead_or_set_p (incr, incr_reg)
3513
      /* Mustn't autoinc an eliminable register.  */
3514
      && (regno >= FIRST_PSEUDO_REGISTER
3515
          || ! TEST_HARD_REG_BIT (elim_reg_set, regno)))
3516
    {
3517
      /* This is the simple case.  Try to make the auto-inc.  If
3518
         we can't, we are done.  Otherwise, we will do any
3519
         needed updates below.  */
3520
      if (! validate_change (insn, &XEXP (mem, 0), inc, 0))
3521
        return;
3522
    }
3523
  else if (REG_P (q)
3524
           /* PREV_INSN used here to check the semi-open interval
3525
              [insn,incr).  */
3526
           && ! reg_used_between_p (q,  PREV_INSN (insn), incr)
3527
           /* We must also check for sets of q as q may be
3528
              a call clobbered hard register and there may
3529
              be a call between PREV_INSN (insn) and incr.  */
3530
           && ! reg_set_between_p (q,  PREV_INSN (insn), incr))
3531
    {
3532
      /* We have *p followed sometime later by q = p+size.
3533
         Both p and q must be live afterward,
3534
         and q is not used between INSN and its assignment.
3535
         Change it to q = p, ...*q..., q = q+size.
3536
         Then fall into the usual case.  */
3537
      rtx insns, temp;
3538
 
3539
      start_sequence ();
3540
      emit_move_insn (q, incr_reg);
3541
      insns = get_insns ();
3542
      end_sequence ();
3543
 
3544
      /* If we can't make the auto-inc, or can't make the
3545
         replacement into Y, exit.  There's no point in making
3546
         the change below if we can't do the auto-inc and doing
3547
         so is not correct in the pre-inc case.  */
3548
 
3549
      XEXP (inc, 0) = q;
3550
      validate_change (insn, &XEXP (mem, 0), inc, 1);
3551
      validate_change (incr, &XEXP (y, opnum), q, 1);
3552
      if (! apply_change_group ())
3553
        return;
3554
 
3555
      /* We now know we'll be doing this change, so emit the
3556
         new insn(s) and do the updates.  */
3557
      emit_insn_before (insns, insn);
3558
 
3559
      if (BB_HEAD (pbi->bb) == insn)
3560
        BB_HEAD (pbi->bb) = insns;
3561
 
3562
      /* INCR will become a NOTE and INSN won't contain a
3563
         use of INCR_REG.  If a use of INCR_REG was just placed in
3564
         the insn before INSN, make that the next use.
3565
         Otherwise, invalidate it.  */
3566
      if (NONJUMP_INSN_P (PREV_INSN (insn))
3567
          && GET_CODE (PATTERN (PREV_INSN (insn))) == SET
3568
          && SET_SRC (PATTERN (PREV_INSN (insn))) == incr_reg)
3569
        pbi->reg_next_use[regno] = PREV_INSN (insn);
3570
      else
3571
        pbi->reg_next_use[regno] = 0;
3572
 
3573
      incr_reg = q;
3574
      regno = REGNO (q);
3575
 
3576
      if ((pbi->flags & PROP_REG_INFO)
3577
          && !REGNO_REG_SET_P (pbi->reg_live, regno))
3578
        reg_deaths[regno] = pbi->insn_num;
3579
 
3580
      /* REGNO is now used in INCR which is below INSN, but
3581
         it previously wasn't live here.  If we don't mark
3582
         it as live, we'll put a REG_DEAD note for it
3583
         on this insn, which is incorrect.  */
3584
      SET_REGNO_REG_SET (pbi->reg_live, regno);
3585
 
3586
      /* If there are any calls between INSN and INCR, show
3587
         that REGNO now crosses them.  */
3588
      for (temp = insn; temp != incr; temp = NEXT_INSN (temp))
3589
        if (CALL_P (temp))
3590
          {
3591
            REG_N_CALLS_CROSSED (regno)++;
3592
            if (can_throw_internal (temp))
3593
              REG_N_THROWING_CALLS_CROSSED (regno)++;
3594
          }
3595
 
3596
      /* Invalidate alias info for Q since we just changed its value.  */
3597
      clear_reg_alias_info (q);
3598
    }
3599
  else
3600
    return;
3601
 
3602
  /* If we haven't returned, it means we were able to make the
3603
     auto-inc, so update the status.  First, record that this insn
3604
     has an implicit side effect.  */
3605
 
3606
  REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, incr_reg, REG_NOTES (insn));
3607
 
3608
  /* Modify the old increment-insn to simply copy
3609
     the already-incremented value of our register.  */
3610
  changed = validate_change (incr, &SET_SRC (set), incr_reg, 0);
3611
  gcc_assert (changed);
3612
 
3613
  /* If that makes it a no-op (copying the register into itself) delete
3614
     it so it won't appear to be a "use" and a "set" of this
3615
     register.  */
3616
  if (REGNO (SET_DEST (set)) == REGNO (incr_reg))
3617
    {
3618
      /* If the original source was dead, it's dead now.  */
3619
      rtx note;
3620
 
3621
      while ((note = find_reg_note (incr, REG_DEAD, NULL_RTX)) != NULL_RTX)
3622
        {
3623
          remove_note (incr, note);
3624
          if (XEXP (note, 0) != incr_reg)
3625
            {
3626
              unsigned int regno = REGNO (XEXP (note, 0));
3627
 
3628
              if ((pbi->flags & PROP_REG_INFO)
3629
                  && REGNO_REG_SET_P (pbi->reg_live, regno))
3630
                {
3631
                  REG_LIVE_LENGTH (regno) += pbi->insn_num - reg_deaths[regno];
3632
                  reg_deaths[regno] = 0;
3633
                }
3634
              CLEAR_REGNO_REG_SET (pbi->reg_live, REGNO (XEXP (note, 0)));
3635
            }
3636
        }
3637
 
3638
      SET_INSN_DELETED (incr);
3639
    }
3640
 
3641
  if (regno >= FIRST_PSEUDO_REGISTER)
3642
    {
3643
      /* Count an extra reference to the reg.  When a reg is
3644
         incremented, spilling it is worse, so we want to make
3645
         that less likely.  */
3646
      REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
3647
 
3648
      /* Count the increment as a setting of the register,
3649
         even though it isn't a SET in rtl.  */
3650
      REG_N_SETS (regno)++;
3651
    }
3652
}
3653
 
3654
/* X is a MEM found in INSN.  See if we can convert it into an auto-increment
3655
   reference.  */
3656
 
3657
static void
3658
find_auto_inc (struct propagate_block_info *pbi, rtx x, rtx insn)
3659
{
3660
  rtx addr = XEXP (x, 0);
3661
  HOST_WIDE_INT offset = 0;
3662
  rtx set, y, incr, inc_val;
3663
  int regno;
3664
  int size = GET_MODE_SIZE (GET_MODE (x));
3665
 
3666
  if (JUMP_P (insn))
3667
    return;
3668
 
3669
  /* Here we detect use of an index register which might be good for
3670
     postincrement, postdecrement, preincrement, or predecrement.  */
3671
 
3672
  if (GET_CODE (addr) == PLUS && GET_CODE (XEXP (addr, 1)) == CONST_INT)
3673
    offset = INTVAL (XEXP (addr, 1)), addr = XEXP (addr, 0);
3674
 
3675
  if (!REG_P (addr))
3676
    return;
3677
 
3678
  regno = REGNO (addr);
3679
 
3680
  /* Is the next use an increment that might make auto-increment? */
3681
  incr = pbi->reg_next_use[regno];
3682
  if (incr == 0 || BLOCK_NUM (incr) != BLOCK_NUM (insn))
3683
    return;
3684
  set = single_set (incr);
3685
  if (set == 0 || GET_CODE (set) != SET)
3686
    return;
3687
  y = SET_SRC (set);
3688
 
3689
  if (GET_CODE (y) != PLUS)
3690
    return;
3691
 
3692
  if (REG_P (XEXP (y, 0)) && REGNO (XEXP (y, 0)) == REGNO (addr))
3693
    inc_val = XEXP (y, 1);
3694
  else if (REG_P (XEXP (y, 1)) && REGNO (XEXP (y, 1)) == REGNO (addr))
3695
    inc_val = XEXP (y, 0);
3696
  else
3697
    return;
3698
 
3699
  if (GET_CODE (inc_val) == CONST_INT)
3700
    {
3701
      if (HAVE_POST_INCREMENT
3702
          && (INTVAL (inc_val) == size && offset == 0))
3703
        attempt_auto_inc (pbi, gen_rtx_POST_INC (Pmode, addr), insn, x,
3704
                          incr, addr);
3705
      else if (HAVE_POST_DECREMENT
3706
               && (INTVAL (inc_val) == -size && offset == 0))
3707
        attempt_auto_inc (pbi, gen_rtx_POST_DEC (Pmode, addr), insn, x,
3708
                          incr, addr);
3709
      else if (HAVE_PRE_INCREMENT
3710
               && (INTVAL (inc_val) == size && offset == size))
3711
        attempt_auto_inc (pbi, gen_rtx_PRE_INC (Pmode, addr), insn, x,
3712
                          incr, addr);
3713
      else if (HAVE_PRE_DECREMENT
3714
               && (INTVAL (inc_val) == -size && offset == -size))
3715
        attempt_auto_inc (pbi, gen_rtx_PRE_DEC (Pmode, addr), insn, x,
3716
                          incr, addr);
3717
      else if (HAVE_POST_MODIFY_DISP && offset == 0)
3718
        attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
3719
                                                    gen_rtx_PLUS (Pmode,
3720
                                                                  addr,
3721
                                                                  inc_val)),
3722
                          insn, x, incr, addr);
3723
      else if (HAVE_PRE_MODIFY_DISP && offset == INTVAL (inc_val))
3724
        attempt_auto_inc (pbi, gen_rtx_PRE_MODIFY (Pmode, addr,
3725
                                                    gen_rtx_PLUS (Pmode,
3726
                                                                  addr,
3727
                                                                  inc_val)),
3728
                          insn, x, incr, addr);
3729
    }
3730
  else if (REG_P (inc_val)
3731
           && ! reg_set_between_p (inc_val, PREV_INSN (insn),
3732
                                   NEXT_INSN (incr)))
3733
 
3734
    {
3735
      if (HAVE_POST_MODIFY_REG && offset == 0)
3736
        attempt_auto_inc (pbi, gen_rtx_POST_MODIFY (Pmode, addr,
3737
                                                    gen_rtx_PLUS (Pmode,
3738
                                                                  addr,
3739
                                                                  inc_val)),
3740
                          insn, x, incr, addr);
3741
    }
3742
}
3743
 
3744
#endif /* AUTO_INC_DEC */
3745
 
3746
static void
3747
mark_used_reg (struct propagate_block_info *pbi, rtx reg,
3748
               rtx cond ATTRIBUTE_UNUSED, rtx insn)
3749
{
3750
  unsigned int regno_first, regno_last, i;
3751
  int some_was_live, some_was_dead, some_not_set;
3752
 
3753
  regno_last = regno_first = REGNO (reg);
3754
  if (regno_first < FIRST_PSEUDO_REGISTER)
3755
    regno_last += hard_regno_nregs[regno_first][GET_MODE (reg)] - 1;
3756
 
3757
  /* Find out if any of this register is live after this instruction.  */
3758
  some_was_live = some_was_dead = 0;
3759
  for (i = regno_first; i <= regno_last; ++i)
3760
    {
3761
      int needed_regno = REGNO_REG_SET_P (pbi->reg_live, i);
3762
      some_was_live |= needed_regno;
3763
      some_was_dead |= ! needed_regno;
3764
    }
3765
 
3766
  /* Find out if any of the register was set this insn.  */
3767
  some_not_set = 0;
3768
  for (i = regno_first; i <= regno_last; ++i)
3769
    some_not_set |= ! REGNO_REG_SET_P (pbi->new_set, i);
3770
 
3771
  if (pbi->flags & (PROP_LOG_LINKS | PROP_AUTOINC))
3772
    {
3773
      /* Record where each reg is used, so when the reg is set we know
3774
         the next insn that uses it.  */
3775
      pbi->reg_next_use[regno_first] = insn;
3776
    }
3777
 
3778
  if (pbi->flags & PROP_REG_INFO)
3779
    {
3780
      if (regno_first < FIRST_PSEUDO_REGISTER)
3781
        {
3782
          /* If this is a register we are going to try to eliminate,
3783
             don't mark it live here.  If we are successful in
3784
             eliminating it, it need not be live unless it is used for
3785
             pseudos, in which case it will have been set live when it
3786
             was allocated to the pseudos.  If the register will not
3787
             be eliminated, reload will set it live at that point.
3788
 
3789
             Otherwise, record that this function uses this register.  */
3790
          /* ??? The PPC backend tries to "eliminate" on the pic
3791
             register to itself.  This should be fixed.  In the mean
3792
             time, hack around it.  */
3793
 
3794
          if (! (TEST_HARD_REG_BIT (elim_reg_set, regno_first)
3795
                 && (regno_first == FRAME_POINTER_REGNUM
3796
                     || regno_first == ARG_POINTER_REGNUM)))
3797
            for (i = regno_first; i <= regno_last; ++i)
3798
              regs_ever_live[i] = 1;
3799
        }
3800
      else
3801
        {
3802
          /* Keep track of which basic block each reg appears in.  */
3803
 
3804
          int blocknum = pbi->bb->index;
3805
          if (REG_BASIC_BLOCK (regno_first) == REG_BLOCK_UNKNOWN)
3806
            REG_BASIC_BLOCK (regno_first) = blocknum;
3807
          else if (REG_BASIC_BLOCK (regno_first) != blocknum)
3808
            REG_BASIC_BLOCK (regno_first) = REG_BLOCK_GLOBAL;
3809
 
3810
          /* Count (weighted) number of uses of each reg.  */
3811
          REG_FREQ (regno_first) += REG_FREQ_FROM_BB (pbi->bb);
3812
          REG_N_REFS (regno_first)++;
3813
        }
3814
      for (i = regno_first; i <= regno_last; ++i)
3815
        if (! REGNO_REG_SET_P (pbi->reg_live, i))
3816
          {
3817
            gcc_assert (!reg_deaths[i]);
3818
            reg_deaths[i] = pbi->insn_num;
3819
          }
3820
    }
3821
 
3822
  /* Record and count the insns in which a reg dies.  If it is used in
3823
     this insn and was dead below the insn then it dies in this insn.
3824
     If it was set in this insn, we do not make a REG_DEAD note;
3825
     likewise if we already made such a note.  */
3826
  if ((pbi->flags & (PROP_DEATH_NOTES | PROP_REG_INFO))
3827
      && some_was_dead
3828
      && some_not_set)
3829
    {
3830
      /* Check for the case where the register dying partially
3831
         overlaps the register set by this insn.  */
3832
      if (regno_first != regno_last)
3833
        for (i = regno_first; i <= regno_last; ++i)
3834
          some_was_live |= REGNO_REG_SET_P (pbi->new_set, i);
3835
 
3836
      /* If none of the words in X is needed, make a REG_DEAD note.
3837
         Otherwise, we must make partial REG_DEAD notes.  */
3838
      if (! some_was_live)
3839
        {
3840
          if ((pbi->flags & PROP_DEATH_NOTES)
3841
#ifdef STACK_REGS
3842
              && (!(pbi->flags & PROP_POST_REGSTACK)
3843
                  || !IN_RANGE (REGNO (reg), FIRST_STACK_REG, LAST_STACK_REG))
3844
#endif
3845
              && ! find_regno_note (insn, REG_DEAD, regno_first))
3846
            REG_NOTES (insn)
3847
              = alloc_EXPR_LIST (REG_DEAD, reg, REG_NOTES (insn));
3848
 
3849
          if (pbi->flags & PROP_REG_INFO)
3850
            REG_N_DEATHS (regno_first)++;
3851
        }
3852
      else
3853
        {
3854
          /* Don't make a REG_DEAD note for a part of a register
3855
             that is set in the insn.  */
3856
          for (i = regno_first; i <= regno_last; ++i)
3857
            if (! REGNO_REG_SET_P (pbi->reg_live, i)
3858
                && ! dead_or_set_regno_p (insn, i))
3859
              REG_NOTES (insn)
3860
                = alloc_EXPR_LIST (REG_DEAD,
3861
                                   regno_reg_rtx[i],
3862
                                   REG_NOTES (insn));
3863
        }
3864
    }
3865
 
3866
  /* Mark the register as being live.  */
3867
  for (i = regno_first; i <= regno_last; ++i)
3868
    {
3869
#ifdef HAVE_conditional_execution
3870
      int this_was_live = REGNO_REG_SET_P (pbi->reg_live, i);
3871
#endif
3872
 
3873
      SET_REGNO_REG_SET (pbi->reg_live, i);
3874
 
3875
#ifdef HAVE_conditional_execution
3876
      /* If this is a conditional use, record that fact.  If it is later
3877
         conditionally set, we'll know to kill the register.  */
3878
      if (cond != NULL_RTX)
3879
        {
3880
          splay_tree_node node;
3881
          struct reg_cond_life_info *rcli;
3882
          rtx ncond;
3883
 
3884
          if (this_was_live)
3885
            {
3886
              node = splay_tree_lookup (pbi->reg_cond_dead, i);
3887
              if (node == NULL)
3888
                {
3889
                  /* The register was unconditionally live previously.
3890
                     No need to do anything.  */
3891
                }
3892
              else
3893
                {
3894
                  /* The register was conditionally live previously.
3895
                     Subtract the new life cond from the old death cond.  */
3896
                  rcli = (struct reg_cond_life_info *) node->value;
3897
                  ncond = rcli->condition;
3898
                  ncond = and_reg_cond (ncond, not_reg_cond (cond), 1);
3899
 
3900
                  /* If the register is now unconditionally live,
3901
                     remove the entry in the splay_tree.  */
3902
                  if (ncond == const0_rtx)
3903
                    splay_tree_remove (pbi->reg_cond_dead, i);
3904
                  else
3905
                    {
3906
                      rcli->condition = ncond;
3907
                      SET_REGNO_REG_SET (pbi->reg_cond_reg,
3908
                                         REGNO (XEXP (cond, 0)));
3909
                    }
3910
                }
3911
            }
3912
          else
3913
            {
3914
              /* The register was not previously live at all.  Record
3915
                 the condition under which it is still dead.  */
3916
              rcli = XNEW (struct reg_cond_life_info);
3917
              rcli->condition = not_reg_cond (cond);
3918
              rcli->stores = const0_rtx;
3919
              rcli->orig_condition = const0_rtx;
3920
              splay_tree_insert (pbi->reg_cond_dead, i,
3921
                                 (splay_tree_value) rcli);
3922
 
3923
              SET_REGNO_REG_SET (pbi->reg_cond_reg, REGNO (XEXP (cond, 0)));
3924
            }
3925
        }
3926
      else if (this_was_live)
3927
        {
3928
          /* The register may have been conditionally live previously, but
3929
             is now unconditionally live.  Remove it from the conditionally
3930
             dead list, so that a conditional set won't cause us to think
3931
             it dead.  */
3932
          splay_tree_remove (pbi->reg_cond_dead, i);
3933
        }
3934
#endif
3935
    }
3936
}
3937
 
3938
/* Scan expression X for registers which have to be marked used in PBI.
3939
   X is considered to be the SET_DEST rtx of SET.  TRUE is returned if
3940
   X could be handled by this function.  */
3941
 
3942
static bool
3943
mark_used_dest_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn)
3944
{
3945
  int regno;
3946
  bool mark_dest = false;
3947
  rtx dest = x;
3948
 
3949
  /* On some platforms calls return values spread over several
3950
     locations.  These locations are wrapped in a EXPR_LIST rtx
3951
     together with a CONST_INT offset.  */
3952
  if (GET_CODE (x) == EXPR_LIST
3953
      && GET_CODE (XEXP (x, 1)) == CONST_INT)
3954
    x = XEXP (x, 0);
3955
 
3956
  if (x == NULL_RTX)
3957
    return false;
3958
 
3959
  /* If storing into MEM, don't show it as being used.  But do
3960
     show the address as being used.  */
3961
  if (MEM_P (x))
3962
    {
3963
#ifdef AUTO_INC_DEC
3964
      if (pbi->flags & PROP_AUTOINC)
3965
        find_auto_inc (pbi, x, insn);
3966
#endif
3967
      mark_used_regs (pbi, XEXP (x, 0), cond, insn);
3968
      return true;
3969
    }
3970
 
3971
  /* Storing in STRICT_LOW_PART is like storing in a reg
3972
     in that this SET might be dead, so ignore it in TESTREG.
3973
     but in some other ways it is like using the reg.
3974
 
3975
     Storing in a SUBREG or a bit field is like storing the entire
3976
     register in that if the register's value is not used
3977
               then this SET is not needed.  */
3978
  while (GET_CODE (x) == STRICT_LOW_PART
3979
         || GET_CODE (x) == ZERO_EXTRACT
3980
         || GET_CODE (x) == SUBREG)
3981
    {
3982
#ifdef CANNOT_CHANGE_MODE_CLASS
3983
      if ((pbi->flags & PROP_REG_INFO) && GET_CODE (x) == SUBREG)
3984
        record_subregs_of_mode (x);
3985
#endif
3986
 
3987
      /* Modifying a single register in an alternate mode
3988
         does not use any of the old value.  But these other
3989
         ways of storing in a register do use the old value.  */
3990
      if (GET_CODE (x) == SUBREG
3991
          && !((REG_BYTES (SUBREG_REG (x))
3992
                + UNITS_PER_WORD - 1) / UNITS_PER_WORD
3993
               > (REG_BYTES (x)
3994
                  + UNITS_PER_WORD - 1) / UNITS_PER_WORD))
3995
        ;
3996
      else
3997
        mark_dest = true;
3998
 
3999
      x = XEXP (x, 0);
4000
    }
4001
 
4002
  /* If this is a store into a register or group of registers,
4003
     recursively scan the value being stored.  */
4004
  if (REG_P (x)
4005
      && (regno = REGNO (x),
4006
          !(regno == FRAME_POINTER_REGNUM
4007
            && (!reload_completed || frame_pointer_needed)))
4008
#if FRAME_POINTER_REGNUM != HARD_FRAME_POINTER_REGNUM
4009
      && !(regno == HARD_FRAME_POINTER_REGNUM
4010
           && (!reload_completed || frame_pointer_needed))
4011
#endif
4012
#if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
4013
      && !(regno == ARG_POINTER_REGNUM && fixed_regs[regno])
4014
#endif
4015
      )
4016
    {
4017
      if (mark_dest)
4018
        mark_used_regs (pbi, dest, cond, insn);
4019
      return true;
4020
    }
4021
  return false;
4022
}
4023
 
4024
/* Scan expression X and store a 1-bit in NEW_LIVE for each reg it uses.
4025
   This is done assuming the registers needed from X are those that
4026
   have 1-bits in PBI->REG_LIVE.
4027
 
4028
   INSN is the containing instruction.  If INSN is dead, this function
4029
   is not called.  */
4030
 
4031
static void
4032
mark_used_regs (struct propagate_block_info *pbi, rtx x, rtx cond, rtx insn)
4033
{
4034
  RTX_CODE code;
4035
  int flags = pbi->flags;
4036
 
4037
 retry:
4038
  if (!x)
4039
    return;
4040
  code = GET_CODE (x);
4041
  switch (code)
4042
    {
4043
    case LABEL_REF:
4044
    case SYMBOL_REF:
4045
    case CONST_INT:
4046
    case CONST:
4047
    case CONST_DOUBLE:
4048
    case CONST_VECTOR:
4049
    case PC:
4050
    case ADDR_VEC:
4051
    case ADDR_DIFF_VEC:
4052
      return;
4053
 
4054
#ifdef HAVE_cc0
4055
    case CC0:
4056
      pbi->cc0_live = 1;
4057
      return;
4058
#endif
4059
 
4060
    case CLOBBER:
4061
      /* If we are clobbering a MEM, mark any registers inside the address
4062
         as being used.  */
4063
      if (MEM_P (XEXP (x, 0)))
4064
        mark_used_regs (pbi, XEXP (XEXP (x, 0), 0), cond, insn);
4065
      return;
4066
 
4067
    case MEM:
4068
      /* Don't bother watching stores to mems if this is not the
4069
         final pass.  We'll not be deleting dead stores this round.  */
4070
      if (optimize && (flags & PROP_SCAN_DEAD_STORES))
4071
        {
4072
          /* Invalidate the data for the last MEM stored, but only if MEM is
4073
             something that can be stored into.  */
4074
          if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
4075
              && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
4076
            /* Needn't clear the memory set list.  */
4077
            ;
4078
          else
4079
            {
4080
              rtx temp = pbi->mem_set_list;
4081
              rtx prev = NULL_RTX;
4082
              rtx next;
4083
 
4084
              while (temp)
4085
                {
4086
                  next = XEXP (temp, 1);
4087
                  if (anti_dependence (XEXP (temp, 0), x))
4088
                    {
4089
                      /* Splice temp out of the list.  */
4090
                      if (prev)
4091
                        XEXP (prev, 1) = next;
4092
                      else
4093
                        pbi->mem_set_list = next;
4094
                      free_EXPR_LIST_node (temp);
4095
                      pbi->mem_set_list_len--;
4096
                    }
4097
                  else
4098
                    prev = temp;
4099
                  temp = next;
4100
                }
4101
            }
4102
 
4103
          /* If the memory reference had embedded side effects (autoincrement
4104
             address modes.  Then we may need to kill some entries on the
4105
             memory set list.  */
4106
          if (insn)
4107
            for_each_rtx (&PATTERN (insn), invalidate_mems_from_autoinc, pbi);
4108
        }
4109
 
4110
#ifdef AUTO_INC_DEC
4111
      if (flags & PROP_AUTOINC)
4112
        find_auto_inc (pbi, x, insn);
4113
#endif
4114
      break;
4115
 
4116
    case SUBREG:
4117
#ifdef CANNOT_CHANGE_MODE_CLASS
4118
      if (flags & PROP_REG_INFO)
4119
        record_subregs_of_mode (x);
4120
#endif
4121
 
4122
      /* While we're here, optimize this case.  */
4123
      x = SUBREG_REG (x);
4124
      if (!REG_P (x))
4125
        goto retry;
4126
      /* Fall through.  */
4127
 
4128
    case REG:
4129
      /* See a register other than being set => mark it as needed.  */
4130
      mark_used_reg (pbi, x, cond, insn);
4131
      return;
4132
 
4133
    case SET:
4134
      {
4135
        rtx dest = SET_DEST (x);
4136
        int i;
4137
        bool ret = false;
4138
 
4139
        if (GET_CODE (dest) == PARALLEL)
4140
          for (i = 0; i < XVECLEN (dest, 0); i++)
4141
            ret |= mark_used_dest_regs (pbi, XVECEXP (dest, 0, i), cond, insn);
4142
        else
4143
          ret = mark_used_dest_regs (pbi, dest, cond, insn);
4144
 
4145
        if (ret)
4146
          {
4147
            mark_used_regs (pbi, SET_SRC (x), cond, insn);
4148
            return;
4149
          }
4150
      }
4151
      break;
4152
 
4153
    case ASM_OPERANDS:
4154
    case UNSPEC_VOLATILE:
4155
    case TRAP_IF:
4156
    case ASM_INPUT:
4157
      {
4158
        /* Traditional and volatile asm instructions must be considered to use
4159
           and clobber all hard registers, all pseudo-registers and all of
4160
           memory.  So must TRAP_IF and UNSPEC_VOLATILE operations.
4161
 
4162
           Consider for instance a volatile asm that changes the fpu rounding
4163
           mode.  An insn should not be moved across this even if it only uses
4164
           pseudo-regs because it might give an incorrectly rounded result.
4165
 
4166
           ?!? Unfortunately, marking all hard registers as live causes massive
4167
           problems for the register allocator and marking all pseudos as live
4168
           creates mountains of uninitialized variable warnings.
4169
 
4170
           So for now, just clear the memory set list and mark any regs
4171
           we can find in ASM_OPERANDS as used.  */
4172
        if (code != ASM_OPERANDS || MEM_VOLATILE_P (x))
4173
          {
4174
            free_EXPR_LIST_list (&pbi->mem_set_list);
4175
            pbi->mem_set_list_len = 0;
4176
          }
4177
 
4178
        /* For all ASM_OPERANDS, we must traverse the vector of input operands.
4179
           We can not just fall through here since then we would be confused
4180
           by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
4181
           traditional asms unlike their normal usage.  */
4182
        if (code == ASM_OPERANDS)
4183
          {
4184
            int j;
4185
 
4186
            for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++)
4187
              mark_used_regs (pbi, ASM_OPERANDS_INPUT (x, j), cond, insn);
4188
          }
4189
        break;
4190
      }
4191
 
4192
    case COND_EXEC:
4193
      gcc_assert (!cond);
4194
 
4195
      mark_used_regs (pbi, COND_EXEC_TEST (x), NULL_RTX, insn);
4196
 
4197
      cond = COND_EXEC_TEST (x);
4198
      x = COND_EXEC_CODE (x);
4199
      goto retry;
4200
 
4201
    default:
4202
      break;
4203
    }
4204
 
4205
  /* Recursively scan the operands of this expression.  */
4206
 
4207
  {
4208
    const char * const fmt = GET_RTX_FORMAT (code);
4209
    int i;
4210
 
4211
    for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4212
      {
4213
        if (fmt[i] == 'e')
4214
          {
4215
            /* Tail recursive case: save a function call level.  */
4216
            if (i == 0)
4217
              {
4218
                x = XEXP (x, 0);
4219
                goto retry;
4220
              }
4221
            mark_used_regs (pbi, XEXP (x, i), cond, insn);
4222
          }
4223
        else if (fmt[i] == 'E')
4224
          {
4225
            int j;
4226
            for (j = 0; j < XVECLEN (x, i); j++)
4227
              mark_used_regs (pbi, XVECEXP (x, i, j), cond, insn);
4228
          }
4229
      }
4230
  }
4231
}
4232
 
4233
#ifdef AUTO_INC_DEC
4234
 
4235
static int
4236
try_pre_increment_1 (struct propagate_block_info *pbi, rtx insn)
4237
{
4238
  /* Find the next use of this reg.  If in same basic block,
4239
     make it do pre-increment or pre-decrement if appropriate.  */
4240
  rtx x = single_set (insn);
4241
  HOST_WIDE_INT amount = ((GET_CODE (SET_SRC (x)) == PLUS ? 1 : -1)
4242
                          * INTVAL (XEXP (SET_SRC (x), 1)));
4243
  int regno = REGNO (SET_DEST (x));
4244
  rtx y = pbi->reg_next_use[regno];
4245
  if (y != 0
4246
      && SET_DEST (x) != stack_pointer_rtx
4247
      && BLOCK_NUM (y) == BLOCK_NUM (insn)
4248
      /* Don't do this if the reg dies, or gets set in y; a standard addressing
4249
         mode would be better.  */
4250
      && ! dead_or_set_p (y, SET_DEST (x))
4251
      && try_pre_increment (y, SET_DEST (x), amount))
4252
    {
4253
      /* We have found a suitable auto-increment and already changed
4254
         insn Y to do it.  So flush this increment instruction.  */
4255
      propagate_block_delete_insn (insn);
4256
 
4257
      /* Count a reference to this reg for the increment insn we are
4258
         deleting.  When a reg is incremented, spilling it is worse,
4259
         so we want to make that less likely.  */
4260
      if (regno >= FIRST_PSEUDO_REGISTER)
4261
        {
4262
          REG_FREQ (regno) += REG_FREQ_FROM_BB (pbi->bb);
4263
          REG_N_SETS (regno)++;
4264
        }
4265
 
4266
      /* Flush any remembered memories depending on the value of
4267
         the incremented register.  */
4268
      invalidate_mems_from_set (pbi, SET_DEST (x));
4269
 
4270
      return 1;
4271
    }
4272
  return 0;
4273
}
4274
 
4275
/* Try to change INSN so that it does pre-increment or pre-decrement
4276
   addressing on register REG in order to add AMOUNT to REG.
4277
   AMOUNT is negative for pre-decrement.
4278
   Returns 1 if the change could be made.
4279
   This checks all about the validity of the result of modifying INSN.  */
4280
 
4281
static int
4282
try_pre_increment (rtx insn, rtx reg, HOST_WIDE_INT amount)
4283
{
4284
  rtx use;
4285
 
4286
  /* Nonzero if we can try to make a pre-increment or pre-decrement.
4287
     For example, addl $4,r1; movl (r1),... can become movl +(r1),...  */
4288
  int pre_ok = 0;
4289
  /* Nonzero if we can try to make a post-increment or post-decrement.
4290
     For example, addl $4,r1; movl -4(r1),... can become movl (r1)+,...
4291
     It is possible for both PRE_OK and POST_OK to be nonzero if the machine
4292
     supports both pre-inc and post-inc, or both pre-dec and post-dec.  */
4293
  int post_ok = 0;
4294
 
4295
  /* Nonzero if the opportunity actually requires post-inc or post-dec.  */
4296
  int do_post = 0;
4297
 
4298
  /* From the sign of increment, see which possibilities are conceivable
4299
     on this target machine.  */
4300
  if (HAVE_PRE_INCREMENT && amount > 0)
4301
    pre_ok = 1;
4302
  if (HAVE_POST_INCREMENT && amount > 0)
4303
    post_ok = 1;
4304
 
4305
  if (HAVE_PRE_DECREMENT && amount < 0)
4306
    pre_ok = 1;
4307
  if (HAVE_POST_DECREMENT && amount < 0)
4308
    post_ok = 1;
4309
 
4310
  if (! (pre_ok || post_ok))
4311
    return 0;
4312
 
4313
  /* It is not safe to add a side effect to a jump insn
4314
     because if the incremented register is spilled and must be reloaded
4315
     there would be no way to store the incremented value back in memory.  */
4316
 
4317
  if (JUMP_P (insn))
4318
    return 0;
4319
 
4320
  use = 0;
4321
  if (pre_ok)
4322
    use = find_use_as_address (PATTERN (insn), reg, 0);
4323
  if (post_ok && (use == 0 || use == (rtx) (size_t) 1))
4324
    {
4325
      use = find_use_as_address (PATTERN (insn), reg, -amount);
4326
      do_post = 1;
4327
    }
4328
 
4329
  if (use == 0 || use == (rtx) (size_t) 1)
4330
    return 0;
4331
 
4332
  if (GET_MODE_SIZE (GET_MODE (use)) != (amount > 0 ? amount : - amount))
4333
    return 0;
4334
 
4335
  /* See if this combination of instruction and addressing mode exists.  */
4336
  if (! validate_change (insn, &XEXP (use, 0),
4337
                         gen_rtx_fmt_e (amount > 0
4338
                                        ? (do_post ? POST_INC : PRE_INC)
4339
                                        : (do_post ? POST_DEC : PRE_DEC),
4340
                                        Pmode, reg), 0))
4341
    return 0;
4342
 
4343
  /* Record that this insn now has an implicit side effect on X.  */
4344
  REG_NOTES (insn) = alloc_EXPR_LIST (REG_INC, reg, REG_NOTES (insn));
4345
  return 1;
4346
}
4347
 
4348
#endif /* AUTO_INC_DEC */
4349
 
4350
/* Find the place in the rtx X where REG is used as a memory address.
4351
   Return the MEM rtx that so uses it.
4352
   If PLUSCONST is nonzero, search instead for a memory address equivalent to
4353
   (plus REG (const_int PLUSCONST)).
4354
 
4355
   If such an address does not appear, return 0.
4356
   If REG appears more than once, or is used other than in such an address,
4357
   return (rtx) 1.  */
4358
 
4359
rtx
4360
find_use_as_address (rtx x, rtx reg, HOST_WIDE_INT plusconst)
4361
{
4362
  enum rtx_code code = GET_CODE (x);
4363
  const char * const fmt = GET_RTX_FORMAT (code);
4364
  int i;
4365
  rtx value = 0;
4366
  rtx tem;
4367
 
4368
  if (code == MEM && XEXP (x, 0) == reg && plusconst == 0)
4369
    return x;
4370
 
4371
  if (code == MEM && GET_CODE (XEXP (x, 0)) == PLUS
4372
      && XEXP (XEXP (x, 0), 0) == reg
4373
      && GET_CODE (XEXP (XEXP (x, 0), 1)) == CONST_INT
4374
      && INTVAL (XEXP (XEXP (x, 0), 1)) == plusconst)
4375
    return x;
4376
 
4377
  if (code == SIGN_EXTRACT || code == ZERO_EXTRACT)
4378
    {
4379
      /* If REG occurs inside a MEM used in a bit-field reference,
4380
         that is unacceptable.  */
4381
      if (find_use_as_address (XEXP (x, 0), reg, 0) != 0)
4382
        return (rtx) (size_t) 1;
4383
    }
4384
 
4385
  if (x == reg)
4386
    return (rtx) (size_t) 1;
4387
 
4388
  for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4389
    {
4390
      if (fmt[i] == 'e')
4391
        {
4392
          tem = find_use_as_address (XEXP (x, i), reg, plusconst);
4393
          if (value == 0)
4394
            value = tem;
4395
          else if (tem != 0)
4396
            return (rtx) (size_t) 1;
4397
        }
4398
      else if (fmt[i] == 'E')
4399
        {
4400
          int j;
4401
          for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4402
            {
4403
              tem = find_use_as_address (XVECEXP (x, i, j), reg, plusconst);
4404
              if (value == 0)
4405
                value = tem;
4406
              else if (tem != 0)
4407
                return (rtx) (size_t) 1;
4408
            }
4409
        }
4410
    }
4411
 
4412
  return value;
4413
}
4414
 
4415
/* Write information about registers and basic blocks into FILE.
4416
   This is part of making a debugging dump.  */
4417
 
4418
void
4419
dump_regset (regset r, FILE *outf)
4420
{
4421
  unsigned i;
4422
  reg_set_iterator rsi;
4423
 
4424
  if (r == NULL)
4425
    {
4426
      fputs (" (nil)", outf);
4427
      return;
4428
    }
4429
 
4430
  EXECUTE_IF_SET_IN_REG_SET (r, 0, i, rsi)
4431
    {
4432
      fprintf (outf, " %d", i);
4433
      if (i < FIRST_PSEUDO_REGISTER)
4434
        fprintf (outf, " [%s]",
4435
                 reg_names[i]);
4436
    }
4437
}
4438
 
4439
/* Print a human-readable representation of R on the standard error
4440
   stream.  This function is designed to be used from within the
4441
   debugger.  */
4442
 
4443
void
4444
debug_regset (regset r)
4445
{
4446
  dump_regset (r, stderr);
4447
  putc ('\n', stderr);
4448
}
4449
 
4450
/* Recompute register set/reference counts immediately prior to register
4451
   allocation.
4452
 
4453
   This avoids problems with set/reference counts changing to/from values
4454
   which have special meanings to the register allocators.
4455
 
4456
   Additionally, the reference counts are the primary component used by the
4457
   register allocators to prioritize pseudos for allocation to hard regs.
4458
   More accurate reference counts generally lead to better register allocation.
4459
 
4460
   It might be worthwhile to update REG_LIVE_LENGTH, REG_BASIC_BLOCK and
4461
   possibly other information which is used by the register allocators.  */
4462
 
4463
static unsigned int
4464
recompute_reg_usage (void)
4465
{
4466
  allocate_reg_life_data ();
4467
  /* distribute_notes in combiner fails to convert some of the
4468
     REG_UNUSED notes to REG_DEAD notes.  This causes CHECK_DEAD_NOTES
4469
     in sched1 to die.  To solve this update the DEATH_NOTES
4470
     here.  */
4471
  update_life_info (NULL, UPDATE_LIFE_LOCAL, PROP_REG_INFO | PROP_DEATH_NOTES);
4472
 
4473
  if (dump_file)
4474
    dump_flow_info (dump_file, dump_flags);
4475
  return 0;
4476
}
4477
 
4478
struct tree_opt_pass pass_recompute_reg_usage =
4479
{
4480
  "life2",                              /* name */
4481
  NULL,                                 /* gate */
4482
  recompute_reg_usage,                  /* execute */
4483
  NULL,                                 /* sub */
4484
  NULL,                                 /* next */
4485
  0,                                    /* static_pass_number */
4486
  0,                                    /* tv_id */
4487
  0,                                    /* properties_required */
4488
  0,                                    /* properties_provided */
4489
  0,                                    /* properties_destroyed */
4490
  0,                                    /* todo_flags_start */
4491
  TODO_dump_func,                       /* todo_flags_finish */
4492
  'f'                                   /* letter */
4493
};
4494
 
4495
/* Optionally removes all the REG_DEAD and REG_UNUSED notes from a set of
4496
   blocks.  If BLOCKS is NULL, assume the universal set.  Returns a count
4497
   of the number of registers that died.
4498
   If KILL is 1, remove old REG_DEAD / REG_UNUSED notes.  If it is 0, don't.
4499
   if it is -1, remove them unless they pertain to a stack reg.  */
4500
 
4501
int
4502
count_or_remove_death_notes (sbitmap blocks, int kill)
4503
{
4504
  int count = 0;
4505
  unsigned int i = 0;
4506
  basic_block bb;
4507
 
4508
  /* This used to be a loop over all the blocks with a membership test
4509
     inside the loop.  That can be amazingly expensive on a large CFG
4510
     when only a small number of bits are set in BLOCKs (for example,
4511
     the calls from the scheduler typically have very few bits set).
4512
 
4513
     For extra credit, someone should convert BLOCKS to a bitmap rather
4514
     than an sbitmap.  */
4515
  if (blocks)
4516
    {
4517
      sbitmap_iterator sbi;
4518
 
4519
      EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi)
4520
        {
4521
          basic_block bb = BASIC_BLOCK (i);
4522
          /* The bitmap may be flawed in that one of the basic blocks
4523
             may have been deleted before you get here.  */
4524
          if (bb)
4525
            count += count_or_remove_death_notes_bb (bb, kill);
4526
        };
4527
    }
4528
  else
4529
    {
4530
      FOR_EACH_BB (bb)
4531
        {
4532
          count += count_or_remove_death_notes_bb (bb, kill);
4533
        }
4534
    }
4535
 
4536
  return count;
4537
}
4538
 
4539
/* Optionally removes all the REG_DEAD and REG_UNUSED notes from basic
4540
   block BB.  Returns a count of the number of registers that died.  */
4541
 
4542
static int
4543
count_or_remove_death_notes_bb (basic_block bb, int kill)
4544
{
4545
  int count = 0;
4546
  rtx insn;
4547
 
4548
  for (insn = BB_HEAD (bb); ; insn = NEXT_INSN (insn))
4549
    {
4550
      if (INSN_P (insn))
4551
        {
4552
          rtx *pprev = &REG_NOTES (insn);
4553
          rtx link = *pprev;
4554
 
4555
          while (link)
4556
            {
4557
              switch (REG_NOTE_KIND (link))
4558
                {
4559
                case REG_DEAD:
4560
                  if (REG_P (XEXP (link, 0)))
4561
                    {
4562
                      rtx reg = XEXP (link, 0);
4563
                      int n;
4564
 
4565
                      if (REGNO (reg) >= FIRST_PSEUDO_REGISTER)
4566
                        n = 1;
4567
                      else
4568
                        n = hard_regno_nregs[REGNO (reg)][GET_MODE (reg)];
4569
                      count += n;
4570
                    }
4571
 
4572
                  /* Fall through.  */
4573
 
4574
                case REG_UNUSED:
4575
                  if (kill > 0
4576
                      || (kill
4577
#ifdef STACK_REGS
4578
                          && (!REG_P (XEXP (link, 0))
4579
                              || !IN_RANGE (REGNO (XEXP (link, 0)),
4580
                                            FIRST_STACK_REG, LAST_STACK_REG))
4581
#endif
4582
                          ))
4583
                    {
4584
                      rtx next = XEXP (link, 1);
4585
                      free_EXPR_LIST_node (link);
4586
                      *pprev = link = next;
4587
                      break;
4588
                    }
4589
                  /* Fall through.  */
4590
 
4591
                default:
4592
                  pprev = &XEXP (link, 1);
4593
                  link = *pprev;
4594
                  break;
4595
                }
4596
            }
4597
        }
4598
 
4599
      if (insn == BB_END (bb))
4600
        break;
4601
    }
4602
 
4603
  return count;
4604
}
4605
 
4606
/* Clear LOG_LINKS fields of insns in a selected blocks or whole chain
4607
   if blocks is NULL.  */
4608
 
4609
static void
4610
clear_log_links (sbitmap blocks)
4611
{
4612
  rtx insn;
4613
 
4614
  if (!blocks)
4615
    {
4616
      for (insn = get_insns (); insn; insn = NEXT_INSN (insn))
4617
        if (INSN_P (insn))
4618
          free_INSN_LIST_list (&LOG_LINKS (insn));
4619
    }
4620
  else
4621
    {
4622
      unsigned int i = 0;
4623
      sbitmap_iterator sbi;
4624
 
4625
      EXECUTE_IF_SET_IN_SBITMAP (blocks, 0, i, sbi)
4626
        {
4627
          basic_block bb = BASIC_BLOCK (i);
4628
 
4629
          for (insn = BB_HEAD (bb); insn != NEXT_INSN (BB_END (bb));
4630
               insn = NEXT_INSN (insn))
4631
            if (INSN_P (insn))
4632
              free_INSN_LIST_list (&LOG_LINKS (insn));
4633
        }
4634
    }
4635
}
4636
 
4637
/* Given a register bitmap, turn on the bits in a HARD_REG_SET that
4638
   correspond to the hard registers, if any, set in that map.  This
4639
   could be done far more efficiently by having all sorts of special-cases
4640
   with moving single words, but probably isn't worth the trouble.  */
4641
 
4642
void
4643
reg_set_to_hard_reg_set (HARD_REG_SET *to, bitmap from)
4644
{
4645
  unsigned i;
4646
  bitmap_iterator bi;
4647
 
4648
  EXECUTE_IF_SET_IN_BITMAP (from, 0, i, bi)
4649
    {
4650
      if (i >= FIRST_PSEUDO_REGISTER)
4651
        return;
4652
      SET_HARD_REG_BIT (*to, i);
4653
    }
4654
}
4655
 
4656
 
4657
static bool
4658
gate_remove_death_notes (void)
4659
{
4660
  return flag_profile_values;
4661
}
4662
 
4663
static unsigned int
4664
rest_of_handle_remove_death_notes (void)
4665
{
4666
  count_or_remove_death_notes (NULL, 1);
4667
  return 0;
4668
}
4669
 
4670
struct tree_opt_pass pass_remove_death_notes =
4671
{
4672
  "ednotes",                            /* name */
4673
  gate_remove_death_notes,              /* gate */
4674
  rest_of_handle_remove_death_notes,    /* execute */
4675
  NULL,                                 /* sub */
4676
  NULL,                                 /* next */
4677
  0,                                    /* static_pass_number */
4678
  0,                                    /* tv_id */
4679
  0,                                    /* properties_required */
4680
  0,                                    /* properties_provided */
4681
  0,                                    /* properties_destroyed */
4682
  0,                                    /* todo_flags_start */
4683
  0,                                    /* todo_flags_finish */
4684
 
4685
};
4686
 
4687
/* Perform life analysis.  */
4688
static unsigned int
4689
rest_of_handle_life (void)
4690
{
4691
  regclass_init ();
4692
 
4693
  life_analysis (PROP_FINAL);
4694
  if (optimize)
4695
    cleanup_cfg (CLEANUP_EXPENSIVE | CLEANUP_UPDATE_LIFE | CLEANUP_LOG_LINKS
4696
                 | (flag_thread_jumps ? CLEANUP_THREADING : 0));
4697
 
4698
  if (extra_warnings)
4699
    {
4700
      setjmp_vars_warning (DECL_INITIAL (current_function_decl));
4701
      setjmp_args_warning ();
4702
    }
4703
 
4704
  if (optimize)
4705
    {
4706
      if (initialize_uninitialized_subregs ())
4707
        {
4708
          /* Insns were inserted, and possibly pseudos created, so
4709
             things might look a bit different.  */
4710
          allocate_reg_life_data ();
4711
          update_life_info (NULL, UPDATE_LIFE_GLOBAL_RM_NOTES,
4712
                            PROP_LOG_LINKS | PROP_REG_INFO | PROP_DEATH_NOTES);
4713
        }
4714
    }
4715
 
4716
  no_new_pseudos = 1;
4717
  return 0;
4718
}
4719
 
4720
struct tree_opt_pass pass_life =
4721
{
4722
  "life1",                              /* name */
4723
  NULL,                                 /* gate */
4724
  rest_of_handle_life,                  /* execute */
4725
  NULL,                                 /* sub */
4726
  NULL,                                 /* next */
4727
  0,                                    /* static_pass_number */
4728
  TV_FLOW,                              /* tv_id */
4729
  0,                                    /* properties_required */
4730
  0,                                    /* properties_provided */
4731
  0,                                    /* properties_destroyed */
4732
  TODO_verify_flow,                     /* todo_flags_start */
4733
  TODO_dump_func |
4734
  TODO_ggc_collect,                     /* todo_flags_finish */
4735
  'f'                                   /* letter */
4736
};
4737
 
4738
static unsigned int
4739
rest_of_handle_flow2 (void)
4740
{
4741
  /* If optimizing, then go ahead and split insns now.  */
4742
#ifndef STACK_REGS
4743
  if (optimize > 0)
4744
#endif
4745
    split_all_insns (0);
4746
 
4747
  if (flag_branch_target_load_optimize)
4748
    branch_target_load_optimize (epilogue_completed);
4749
 
4750
  if (optimize)
4751
    cleanup_cfg (CLEANUP_EXPENSIVE);
4752
 
4753
  /* On some machines, the prologue and epilogue code, or parts thereof,
4754
     can be represented as RTL.  Doing so lets us schedule insns between
4755
     it and the rest of the code and also allows delayed branch
4756
     scheduling to operate in the epilogue.  */
4757
  thread_prologue_and_epilogue_insns (get_insns ());
4758
  epilogue_completed = 1;
4759
  flow2_completed = 1;
4760
  return 0;
4761
}
4762
 
4763
struct tree_opt_pass pass_flow2 =
4764
{
4765
  "flow2",                              /* name */
4766
  NULL,                                 /* gate */
4767
  rest_of_handle_flow2,                 /* execute */
4768
  NULL,                                 /* sub */
4769
  NULL,                                 /* next */
4770
  0,                                    /* static_pass_number */
4771
  TV_FLOW2,                             /* tv_id */
4772
  0,                                    /* properties_required */
4773
  0,                                    /* properties_provided */
4774
  0,                                    /* properties_destroyed */
4775
  TODO_verify_flow,                     /* todo_flags_start */
4776
  TODO_dump_func |
4777
  TODO_ggc_collect,                     /* todo_flags_finish */
4778
  'w'                                   /* letter */
4779
};
4780
 

powered by: WebSVN 2.1.0

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