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

Subversion Repositories openrisc_me

[/] [openrisc/] [trunk/] [gnu-src/] [gcc-4.5.1/] [gcc/] [gcse.c] - Blame information for rev 280

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 280 jeremybenn
/* Global common subexpression elimination/Partial redundancy elimination
2
   and global constant/copy propagation for GNU compiler.
3
   Copyright (C) 1997, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005,
4
   2006, 2007, 2008, 2009, 2010 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
/* TODO
23
   - reordering of memory allocation and freeing to be more space efficient
24
   - do rough calc of how many regs are needed in each block, and a rough
25
     calc of how many regs are available in each class and use that to
26
     throttle back the code in cases where RTX_COST is minimal.
27
   - a store to the same address as a load does not kill the load if the
28
     source of the store is also the destination of the load.  Handling this
29
     allows more load motion, particularly out of loops.
30
 
31
*/
32
 
33
/* References searched while implementing this.
34
 
35
   Compilers Principles, Techniques and Tools
36
   Aho, Sethi, Ullman
37
   Addison-Wesley, 1988
38
 
39
   Global Optimization by Suppression of Partial Redundancies
40
   E. Morel, C. Renvoise
41
   communications of the acm, Vol. 22, Num. 2, Feb. 1979
42
 
43
   A Portable Machine-Independent Global Optimizer - Design and Measurements
44
   Frederick Chow
45
   Stanford Ph.D. thesis, Dec. 1983
46
 
47
   A Fast Algorithm for Code Movement Optimization
48
   D.M. Dhamdhere
49
   SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
50
 
51
   A Solution to a Problem with Morel and Renvoise's
52
   Global Optimization by Suppression of Partial Redundancies
53
   K-H Drechsler, M.P. Stadel
54
   ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
55
 
56
   Practical Adaptation of the Global Optimization
57
   Algorithm of Morel and Renvoise
58
   D.M. Dhamdhere
59
   ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
60
 
61
   Efficiently Computing Static Single Assignment Form and the Control
62
   Dependence Graph
63
   R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
64
   ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
65
 
66
   Lazy Code Motion
67
   J. Knoop, O. Ruthing, B. Steffen
68
   ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
69
 
70
   What's In a Region?  Or Computing Control Dependence Regions in Near-Linear
71
   Time for Reducible Flow Control
72
   Thomas Ball
73
   ACM Letters on Programming Languages and Systems,
74
   Vol. 2, Num. 1-4, Mar-Dec 1993
75
 
76
   An Efficient Representation for Sparse Sets
77
   Preston Briggs, Linda Torczon
78
   ACM Letters on Programming Languages and Systems,
79
   Vol. 2, Num. 1-4, Mar-Dec 1993
80
 
81
   A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
82
   K-H Drechsler, M.P. Stadel
83
   ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
84
 
85
   Partial Dead Code Elimination
86
   J. Knoop, O. Ruthing, B. Steffen
87
   ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
88
 
89
   Effective Partial Redundancy Elimination
90
   P. Briggs, K.D. Cooper
91
   ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
92
 
93
   The Program Structure Tree: Computing Control Regions in Linear Time
94
   R. Johnson, D. Pearson, K. Pingali
95
   ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
96
 
97
   Optimal Code Motion: Theory and Practice
98
   J. Knoop, O. Ruthing, B. Steffen
99
   ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
100
 
101
   The power of assignment motion
102
   J. Knoop, O. Ruthing, B. Steffen
103
   ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
104
 
105
   Global code motion / global value numbering
106
   C. Click
107
   ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
108
 
109
   Value Driven Redundancy Elimination
110
   L.T. Simpson
111
   Rice University Ph.D. thesis, Apr. 1996
112
 
113
   Value Numbering
114
   L.T. Simpson
115
   Massively Scalar Compiler Project, Rice University, Sep. 1996
116
 
117
   High Performance Compilers for Parallel Computing
118
   Michael Wolfe
119
   Addison-Wesley, 1996
120
 
121
   Advanced Compiler Design and Implementation
122
   Steven Muchnick
123
   Morgan Kaufmann, 1997
124
 
125
   Building an Optimizing Compiler
126
   Robert Morgan
127
   Digital Press, 1998
128
 
129
   People wishing to speed up the code here should read:
130
     Elimination Algorithms for Data Flow Analysis
131
     B.G. Ryder, M.C. Paull
132
     ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
133
 
134
     How to Analyze Large Programs Efficiently and Informatively
135
     D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
136
     ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
137
 
138
   People wishing to do something different can find various possibilities
139
   in the above papers and elsewhere.
140
*/
141
 
142
#include "config.h"
143
#include "system.h"
144
#include "coretypes.h"
145
#include "tm.h"
146
#include "toplev.h"
147
 
148
#include "rtl.h"
149
#include "tree.h"
150
#include "tm_p.h"
151
#include "regs.h"
152
#include "hard-reg-set.h"
153
#include "flags.h"
154
#include "real.h"
155
#include "insn-config.h"
156
#include "recog.h"
157
#include "basic-block.h"
158
#include "output.h"
159
#include "function.h"
160
#include "expr.h"
161
#include "except.h"
162
#include "ggc.h"
163
#include "params.h"
164
#include "cselib.h"
165
#include "intl.h"
166
#include "obstack.h"
167
#include "timevar.h"
168
#include "tree-pass.h"
169
#include "hashtab.h"
170
#include "df.h"
171
#include "dbgcnt.h"
172
#include "target.h"
173
 
174
/* We support GCSE via Partial Redundancy Elimination.  PRE optimizations
175
   are a superset of those done by classic GCSE.
176
 
177
   We perform the following steps:
178
 
179
   1) Compute table of places where registers are set.
180
 
181
   2) Perform copy/constant propagation.
182
 
183
   3) Perform global cse using lazy code motion if not optimizing
184
      for size, or code hoisting if we are.
185
 
186
   4) Perform another pass of copy/constant propagation.  Try to bypass
187
      conditional jumps if the condition can be computed from a value of
188
      an incoming edge.
189
 
190
   Two passes of copy/constant propagation are done because the first one
191
   enables more GCSE and the second one helps to clean up the copies that
192
   GCSE creates.  This is needed more for PRE than for Classic because Classic
193
   GCSE will try to use an existing register containing the common
194
   subexpression rather than create a new one.  This is harder to do for PRE
195
   because of the code motion (which Classic GCSE doesn't do).
196
 
197
   Expressions we are interested in GCSE-ing are of the form
198
   (set (pseudo-reg) (expression)).
199
   Function want_to_gcse_p says what these are.
200
 
201
   In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
202
   This allows PRE to hoist expressions that are expressed in multiple insns,
203
   such as complex address calculations (e.g. for PIC code, or loads with a
204
   high part and a low part).
205
 
206
   PRE handles moving invariant expressions out of loops (by treating them as
207
   partially redundant).
208
 
209
   **********************
210
 
211
   We used to support multiple passes but there are diminishing returns in
212
   doing so.  The first pass usually makes 90% of the changes that are doable.
213
   A second pass can make a few more changes made possible by the first pass.
214
   Experiments show any further passes don't make enough changes to justify
215
   the expense.
216
 
217
   A study of spec92 using an unlimited number of passes:
218
   [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
219
   [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
220
   [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
221
 
222
   It was found doing copy propagation between each pass enables further
223
   substitutions.
224
 
225
   This study was done before expressions in REG_EQUAL notes were added as
226
   candidate expressions for optimization, and before the GIMPLE optimizers
227
   were added.  Probably, multiple passes is even less efficient now than
228
   at the time when the study was conducted.
229
 
230
   PRE is quite expensive in complicated functions because the DFA can take
231
   a while to converge.  Hence we only perform one pass.
232
 
233
   **********************
234
 
235
   The steps for PRE are:
236
 
237
   1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
238
 
239
   2) Perform the data flow analysis for PRE.
240
 
241
   3) Delete the redundant instructions
242
 
243
   4) Insert the required copies [if any] that make the partially
244
      redundant instructions fully redundant.
245
 
246
   5) For other reaching expressions, insert an instruction to copy the value
247
      to a newly created pseudo that will reach the redundant instruction.
248
 
249
   The deletion is done first so that when we do insertions we
250
   know which pseudo reg to use.
251
 
252
   Various papers have argued that PRE DFA is expensive (O(n^2)) and others
253
   argue it is not.  The number of iterations for the algorithm to converge
254
   is typically 2-4 so I don't view it as that expensive (relatively speaking).
255
 
256
   PRE GCSE depends heavily on the second CPROP pass to clean up the copies
257
   we create.  To make an expression reach the place where it's redundant,
258
   the result of the expression is copied to a new register, and the redundant
259
   expression is deleted by replacing it with this new register.  Classic GCSE
260
   doesn't have this problem as much as it computes the reaching defs of
261
   each register in each block and thus can try to use an existing
262
   register.  */
263
 
264
/* GCSE global vars.  */
265
 
266
/* Set to non-zero if CSE should run after all GCSE optimizations are done.  */
267
int flag_rerun_cse_after_global_opts;
268
 
269
/* An obstack for our working variables.  */
270
static struct obstack gcse_obstack;
271
 
272
struct reg_use {rtx reg_rtx; };
273
 
274
/* Hash table of expressions.  */
275
 
276
struct expr
277
{
278
  /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
279
  rtx expr;
280
  /* Index in the available expression bitmaps.  */
281
  int bitmap_index;
282
  /* Next entry with the same hash.  */
283
  struct expr *next_same_hash;
284
  /* List of anticipatable occurrences in basic blocks in the function.
285
     An "anticipatable occurrence" is one that is the first occurrence in the
286
     basic block, the operands are not modified in the basic block prior
287
     to the occurrence and the output is not used between the start of
288
     the block and the occurrence.  */
289
  struct occr *antic_occr;
290
  /* List of available occurrence in basic blocks in the function.
291
     An "available occurrence" is one that is the last occurrence in the
292
     basic block and the operands are not modified by following statements in
293
     the basic block [including this insn].  */
294
  struct occr *avail_occr;
295
  /* Non-null if the computation is PRE redundant.
296
     The value is the newly created pseudo-reg to record a copy of the
297
     expression in all the places that reach the redundant copy.  */
298
  rtx reaching_reg;
299
};
300
 
301
/* Occurrence of an expression.
302
   There is one per basic block.  If a pattern appears more than once the
303
   last appearance is used [or first for anticipatable expressions].  */
304
 
305
struct occr
306
{
307
  /* Next occurrence of this expression.  */
308
  struct occr *next;
309
  /* The insn that computes the expression.  */
310
  rtx insn;
311
  /* Nonzero if this [anticipatable] occurrence has been deleted.  */
312
  char deleted_p;
313
  /* Nonzero if this [available] occurrence has been copied to
314
     reaching_reg.  */
315
  /* ??? This is mutually exclusive with deleted_p, so they could share
316
     the same byte.  */
317
  char copied_p;
318
};
319
 
320
/* Expression and copy propagation hash tables.
321
   Each hash table is an array of buckets.
322
   ??? It is known that if it were an array of entries, structure elements
323
   `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
324
   not clear whether in the final analysis a sufficient amount of memory would
325
   be saved as the size of the available expression bitmaps would be larger
326
   [one could build a mapping table without holes afterwards though].
327
   Someday I'll perform the computation and figure it out.  */
328
 
329
struct hash_table_d
330
{
331
  /* The table itself.
332
     This is an array of `expr_hash_table_size' elements.  */
333
  struct expr **table;
334
 
335
  /* Size of the hash table, in elements.  */
336
  unsigned int size;
337
 
338
  /* Number of hash table elements.  */
339
  unsigned int n_elems;
340
 
341
  /* Whether the table is expression of copy propagation one.  */
342
  int set_p;
343
};
344
 
345
/* Expression hash table.  */
346
static struct hash_table_d expr_hash_table;
347
 
348
/* Copy propagation hash table.  */
349
static struct hash_table_d set_hash_table;
350
 
351
/* This is a list of expressions which are MEMs and will be used by load
352
   or store motion.
353
   Load motion tracks MEMs which aren't killed by
354
   anything except itself. (i.e., loads and stores to a single location).
355
   We can then allow movement of these MEM refs with a little special
356
   allowance. (all stores copy the same value to the reaching reg used
357
   for the loads).  This means all values used to store into memory must have
358
   no side effects so we can re-issue the setter value.
359
   Store Motion uses this structure as an expression table to track stores
360
   which look interesting, and might be moveable towards the exit block.  */
361
 
362
struct ls_expr
363
{
364
  struct expr * expr;           /* Gcse expression reference for LM.  */
365
  rtx pattern;                  /* Pattern of this mem.  */
366
  rtx pattern_regs;             /* List of registers mentioned by the mem.  */
367
  rtx loads;                    /* INSN list of loads seen.  */
368
  rtx stores;                   /* INSN list of stores seen.  */
369
  struct ls_expr * next;        /* Next in the list.  */
370
  int invalid;                  /* Invalid for some reason.  */
371
  int index;                    /* If it maps to a bitmap index.  */
372
  unsigned int hash_index;      /* Index when in a hash table.  */
373
  rtx reaching_reg;             /* Register to use when re-writing.  */
374
};
375
 
376
/* Array of implicit set patterns indexed by basic block index.  */
377
static rtx *implicit_sets;
378
 
379
/* Head of the list of load/store memory refs.  */
380
static struct ls_expr * pre_ldst_mems = NULL;
381
 
382
/* Hashtable for the load/store memory refs.  */
383
static htab_t pre_ldst_table = NULL;
384
 
385
/* Bitmap containing one bit for each register in the program.
386
   Used when performing GCSE to track which registers have been set since
387
   the start of the basic block.  */
388
static regset reg_set_bitmap;
389
 
390
/* Array, indexed by basic block number for a list of insns which modify
391
   memory within that block.  */
392
static rtx * modify_mem_list;
393
static bitmap modify_mem_list_set;
394
 
395
/* This array parallels modify_mem_list, but is kept canonicalized.  */
396
static rtx * canon_modify_mem_list;
397
 
398
/* Bitmap indexed by block numbers to record which blocks contain
399
   function calls.  */
400
static bitmap blocks_with_calls;
401
 
402
/* Various variables for statistics gathering.  */
403
 
404
/* Memory used in a pass.
405
   This isn't intended to be absolutely precise.  Its intent is only
406
   to keep an eye on memory usage.  */
407
static int bytes_used;
408
 
409
/* GCSE substitutions made.  */
410
static int gcse_subst_count;
411
/* Number of copy instructions created.  */
412
static int gcse_create_count;
413
/* Number of local constants propagated.  */
414
static int local_const_prop_count;
415
/* Number of local copies propagated.  */
416
static int local_copy_prop_count;
417
/* Number of global constants propagated.  */
418
static int global_const_prop_count;
419
/* Number of global copies propagated.  */
420
static int global_copy_prop_count;
421
 
422
/* For available exprs */
423
static sbitmap *ae_kill;
424
 
425
static void compute_can_copy (void);
426
static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
427
static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
428
static void *gcse_alloc (unsigned long);
429
static void alloc_gcse_mem (void);
430
static void free_gcse_mem (void);
431
static void hash_scan_insn (rtx, struct hash_table_d *);
432
static void hash_scan_set (rtx, rtx, struct hash_table_d *);
433
static void hash_scan_clobber (rtx, rtx, struct hash_table_d *);
434
static void hash_scan_call (rtx, rtx, struct hash_table_d *);
435
static int want_to_gcse_p (rtx);
436
static bool gcse_constant_p (const_rtx);
437
static int oprs_unchanged_p (const_rtx, const_rtx, int);
438
static int oprs_anticipatable_p (const_rtx, const_rtx);
439
static int oprs_available_p (const_rtx, const_rtx);
440
static void insert_expr_in_table (rtx, enum machine_mode, rtx, int, int,
441
                                  struct hash_table_d *);
442
static void insert_set_in_table (rtx, rtx, struct hash_table_d *);
443
static unsigned int hash_expr (const_rtx, enum machine_mode, int *, int);
444
static unsigned int hash_set (int, int);
445
static int expr_equiv_p (const_rtx, const_rtx);
446
static void record_last_reg_set_info (rtx, int);
447
static void record_last_mem_set_info (rtx);
448
static void record_last_set_info (rtx, const_rtx, void *);
449
static void compute_hash_table (struct hash_table_d *);
450
static void alloc_hash_table (struct hash_table_d *, int);
451
static void free_hash_table (struct hash_table_d *);
452
static void compute_hash_table_work (struct hash_table_d *);
453
static void dump_hash_table (FILE *, const char *, struct hash_table_d *);
454
static struct expr *lookup_set (unsigned int, struct hash_table_d *);
455
static struct expr *next_set (unsigned int, struct expr *);
456
static void reset_opr_set_tables (void);
457
static int oprs_not_set_p (const_rtx, const_rtx);
458
static void mark_call (rtx);
459
static void mark_set (rtx, rtx);
460
static void mark_clobber (rtx, rtx);
461
static void mark_oprs_set (rtx);
462
static void alloc_cprop_mem (int, int);
463
static void free_cprop_mem (void);
464
static void compute_transp (const_rtx, int, sbitmap *, int);
465
static void compute_transpout (void);
466
static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
467
                                      struct hash_table_d *);
468
static void compute_cprop_data (void);
469
static void find_used_regs (rtx *, void *);
470
static int try_replace_reg (rtx, rtx, rtx);
471
static struct expr *find_avail_set (int, rtx);
472
static int cprop_jump (basic_block, rtx, rtx, rtx, rtx);
473
static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
474
static int load_killed_in_block_p (const_basic_block, int, const_rtx, int);
475
static void canon_list_insert (rtx, const_rtx, void *);
476
static int cprop_insn (rtx);
477
static void find_implicit_sets (void);
478
static int one_cprop_pass (void);
479
static bool constprop_register (rtx, rtx, rtx);
480
static struct expr *find_bypass_set (int, int);
481
static bool reg_killed_on_edge (const_rtx, const_edge);
482
static int bypass_block (basic_block, rtx, rtx);
483
static int bypass_conditional_jumps (void);
484
static void alloc_pre_mem (int, int);
485
static void free_pre_mem (void);
486
static void compute_pre_data (void);
487
static int pre_expr_reaches_here_p (basic_block, struct expr *,
488
                                    basic_block);
489
static void insert_insn_end_basic_block (struct expr *, basic_block, int);
490
static void pre_insert_copy_insn (struct expr *, rtx);
491
static void pre_insert_copies (void);
492
static int pre_delete (void);
493
static int pre_gcse (void);
494
static int one_pre_gcse_pass (void);
495
static void add_label_notes (rtx, rtx);
496
static void alloc_code_hoist_mem (int, int);
497
static void free_code_hoist_mem (void);
498
static void compute_code_hoist_vbeinout (void);
499
static void compute_code_hoist_data (void);
500
static int hoist_expr_reaches_here_p (basic_block, int, basic_block, char *);
501
static int hoist_code (void);
502
static int one_code_hoisting_pass (void);
503
static rtx process_insert_insn (struct expr *);
504
static int pre_edge_insert (struct edge_list *, struct expr **);
505
static int pre_expr_reaches_here_p_work (basic_block, struct expr *,
506
                                         basic_block, char *);
507
static struct ls_expr * ldst_entry (rtx);
508
static void free_ldst_entry (struct ls_expr *);
509
static void free_ldst_mems (void);
510
static void print_ldst_list (FILE *);
511
static struct ls_expr * find_rtx_in_ldst (rtx);
512
static inline struct ls_expr * first_ls_expr (void);
513
static inline struct ls_expr * next_ls_expr (struct ls_expr *);
514
static int simple_mem (const_rtx);
515
static void invalidate_any_buried_refs (rtx);
516
static void compute_ld_motion_mems (void);
517
static void trim_ld_motion_mems (void);
518
static void update_ld_motion_stores (struct expr *);
519
static void free_insn_expr_list_list (rtx *);
520
static void clear_modify_mem_tables (void);
521
static void free_modify_mem_tables (void);
522
static rtx gcse_emit_move_after (rtx, rtx, rtx);
523
static void local_cprop_find_used_regs (rtx *, void *);
524
static bool do_local_cprop (rtx, rtx);
525
static int local_cprop_pass (void);
526
static bool is_too_expensive (const char *);
527
 
528
#define GNEW(T)                 ((T *) gmalloc (sizeof (T)))
529
#define GCNEW(T)                ((T *) gcalloc (1, sizeof (T)))
530
 
531
#define GNEWVEC(T, N)           ((T *) gmalloc (sizeof (T) * (N)))
532
#define GCNEWVEC(T, N)          ((T *) gcalloc ((N), sizeof (T)))
533
 
534
#define GNEWVAR(T, S)           ((T *) gmalloc ((S)))
535
#define GCNEWVAR(T, S)          ((T *) gcalloc (1, (S)))
536
 
537
#define GOBNEW(T)               ((T *) gcse_alloc (sizeof (T)))
538
#define GOBNEWVAR(T, S)         ((T *) gcse_alloc ((S)))
539
 
540
/* Misc. utilities.  */
541
 
542
/* Nonzero for each mode that supports (set (reg) (reg)).
543
   This is trivially true for integer and floating point values.
544
   It may or may not be true for condition codes.  */
545
static char can_copy[(int) NUM_MACHINE_MODES];
546
 
547
/* Compute which modes support reg/reg copy operations.  */
548
 
549
static void
550
compute_can_copy (void)
551
{
552
  int i;
553
#ifndef AVOID_CCMODE_COPIES
554
  rtx reg, insn;
555
#endif
556
  memset (can_copy, 0, NUM_MACHINE_MODES);
557
 
558
  start_sequence ();
559
  for (i = 0; i < NUM_MACHINE_MODES; i++)
560
    if (GET_MODE_CLASS (i) == MODE_CC)
561
      {
562
#ifdef AVOID_CCMODE_COPIES
563
        can_copy[i] = 0;
564
#else
565
        reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
566
        insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
567
        if (recog (PATTERN (insn), insn, NULL) >= 0)
568
          can_copy[i] = 1;
569
#endif
570
      }
571
    else
572
      can_copy[i] = 1;
573
 
574
  end_sequence ();
575
}
576
 
577
/* Returns whether the mode supports reg/reg copy operations.  */
578
 
579
bool
580
can_copy_p (enum machine_mode mode)
581
{
582
  static bool can_copy_init_p = false;
583
 
584
  if (! can_copy_init_p)
585
    {
586
      compute_can_copy ();
587
      can_copy_init_p = true;
588
    }
589
 
590
  return can_copy[mode] != 0;
591
}
592
 
593
 
594
/* Cover function to xmalloc to record bytes allocated.  */
595
 
596
static void *
597
gmalloc (size_t size)
598
{
599
  bytes_used += size;
600
  return xmalloc (size);
601
}
602
 
603
/* Cover function to xcalloc to record bytes allocated.  */
604
 
605
static void *
606
gcalloc (size_t nelem, size_t elsize)
607
{
608
  bytes_used += nelem * elsize;
609
  return xcalloc (nelem, elsize);
610
}
611
 
612
/* Cover function to obstack_alloc.  */
613
 
614
static void *
615
gcse_alloc (unsigned long size)
616
{
617
  bytes_used += size;
618
  return obstack_alloc (&gcse_obstack, size);
619
}
620
 
621
/* Allocate memory for the reg/memory set tracking tables.
622
   This is called at the start of each pass.  */
623
 
624
static void
625
alloc_gcse_mem (void)
626
{
627
  /* Allocate vars to track sets of regs.  */
628
  reg_set_bitmap = BITMAP_ALLOC (NULL);
629
 
630
  /* Allocate array to keep a list of insns which modify memory in each
631
     basic block.  */
632
  modify_mem_list = GCNEWVEC (rtx, last_basic_block);
633
  canon_modify_mem_list = GCNEWVEC (rtx, last_basic_block);
634
  modify_mem_list_set = BITMAP_ALLOC (NULL);
635
  blocks_with_calls = BITMAP_ALLOC (NULL);
636
}
637
 
638
/* Free memory allocated by alloc_gcse_mem.  */
639
 
640
static void
641
free_gcse_mem (void)
642
{
643
  free_modify_mem_tables ();
644
  BITMAP_FREE (modify_mem_list_set);
645
  BITMAP_FREE (blocks_with_calls);
646
}
647
 
648
/* Compute the local properties of each recorded expression.
649
 
650
   Local properties are those that are defined by the block, irrespective of
651
   other blocks.
652
 
653
   An expression is transparent in a block if its operands are not modified
654
   in the block.
655
 
656
   An expression is computed (locally available) in a block if it is computed
657
   at least once and expression would contain the same value if the
658
   computation was moved to the end of the block.
659
 
660
   An expression is locally anticipatable in a block if it is computed at
661
   least once and expression would contain the same value if the computation
662
   was moved to the beginning of the block.
663
 
664
   We call this routine for cprop, pre and code hoisting.  They all compute
665
   basically the same information and thus can easily share this code.
666
 
667
   TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
668
   properties.  If NULL, then it is not necessary to compute or record that
669
   particular property.
670
 
671
   TABLE controls which hash table to look at.  If it is  set hash table,
672
   additionally, TRANSP is computed as ~TRANSP, since this is really cprop's
673
   ABSALTERED.  */
674
 
675
static void
676
compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
677
                          struct hash_table_d *table)
678
{
679
  unsigned int i;
680
 
681
  /* Initialize any bitmaps that were passed in.  */
682
  if (transp)
683
    {
684
      if (table->set_p)
685
        sbitmap_vector_zero (transp, last_basic_block);
686
      else
687
        sbitmap_vector_ones (transp, last_basic_block);
688
    }
689
 
690
  if (comp)
691
    sbitmap_vector_zero (comp, last_basic_block);
692
  if (antloc)
693
    sbitmap_vector_zero (antloc, last_basic_block);
694
 
695
  for (i = 0; i < table->size; i++)
696
    {
697
      struct expr *expr;
698
 
699
      for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
700
        {
701
          int indx = expr->bitmap_index;
702
          struct occr *occr;
703
 
704
          /* The expression is transparent in this block if it is not killed.
705
             We start by assuming all are transparent [none are killed], and
706
             then reset the bits for those that are.  */
707
          if (transp)
708
            compute_transp (expr->expr, indx, transp, table->set_p);
709
 
710
          /* The occurrences recorded in antic_occr are exactly those that
711
             we want to set to nonzero in ANTLOC.  */
712
          if (antloc)
713
            for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
714
              {
715
                SET_BIT (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
716
 
717
                /* While we're scanning the table, this is a good place to
718
                   initialize this.  */
719
                occr->deleted_p = 0;
720
              }
721
 
722
          /* The occurrences recorded in avail_occr are exactly those that
723
             we want to set to nonzero in COMP.  */
724
          if (comp)
725
            for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
726
              {
727
                SET_BIT (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
728
 
729
                /* While we're scanning the table, this is a good place to
730
                   initialize this.  */
731
                occr->copied_p = 0;
732
              }
733
 
734
          /* While we're scanning the table, this is a good place to
735
             initialize this.  */
736
          expr->reaching_reg = 0;
737
        }
738
    }
739
}
740
 
741
/* Hash table support.  */
742
 
743
struct reg_avail_info
744
{
745
  basic_block last_bb;
746
  int first_set;
747
  int last_set;
748
};
749
 
750
static struct reg_avail_info *reg_avail_info;
751
static basic_block current_bb;
752
 
753
 
754
/* See whether X, the source of a set, is something we want to consider for
755
   GCSE.  */
756
 
757
static int
758
want_to_gcse_p (rtx x)
759
{
760
#ifdef STACK_REGS
761
  /* On register stack architectures, don't GCSE constants from the
762
     constant pool, as the benefits are often swamped by the overhead
763
     of shuffling the register stack between basic blocks.  */
764
  if (IS_STACK_MODE (GET_MODE (x)))
765
    x = avoid_constant_pool_reference (x);
766
#endif
767
 
768
  switch (GET_CODE (x))
769
    {
770
    case REG:
771
    case SUBREG:
772
    case CONST_INT:
773
    case CONST_DOUBLE:
774
    case CONST_FIXED:
775
    case CONST_VECTOR:
776
    case CALL:
777
      return 0;
778
 
779
    default:
780
      return can_assign_to_reg_without_clobbers_p (x);
781
    }
782
}
783
 
784
/* Used internally by can_assign_to_reg_without_clobbers_p.  */
785
 
786
static GTY(()) rtx test_insn;
787
 
788
/* Return true if we can assign X to a pseudo register such that the
789
   resulting insn does not result in clobbering a hard register as a
790
   side-effect.
791
 
792
   Additionally, if the target requires it, check that the resulting insn
793
   can be copied.  If it cannot, this means that X is special and probably
794
   has hidden side-effects we don't want to mess with.
795
 
796
   This function is typically used by code motion passes, to verify
797
   that it is safe to insert an insn without worrying about clobbering
798
   maybe live hard regs.  */
799
 
800
bool
801
can_assign_to_reg_without_clobbers_p (rtx x)
802
{
803
  int num_clobbers = 0;
804
  int icode;
805
 
806
  /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
807
  if (general_operand (x, GET_MODE (x)))
808
    return 1;
809
  else if (GET_MODE (x) == VOIDmode)
810
    return 0;
811
 
812
  /* Otherwise, check if we can make a valid insn from it.  First initialize
813
     our test insn if we haven't already.  */
814
  if (test_insn == 0)
815
    {
816
      test_insn
817
        = make_insn_raw (gen_rtx_SET (VOIDmode,
818
                                      gen_rtx_REG (word_mode,
819
                                                   FIRST_PSEUDO_REGISTER * 2),
820
                                      const0_rtx));
821
      NEXT_INSN (test_insn) = PREV_INSN (test_insn) = 0;
822
    }
823
 
824
  /* Now make an insn like the one we would make when GCSE'ing and see if
825
     valid.  */
826
  PUT_MODE (SET_DEST (PATTERN (test_insn)), GET_MODE (x));
827
  SET_SRC (PATTERN (test_insn)) = x;
828
 
829
  icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
830
  if (icode < 0)
831
    return false;
832
 
833
  if (num_clobbers > 0 && added_clobbers_hard_reg_p (icode))
834
    return false;
835
 
836
  if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (test_insn))
837
    return false;
838
 
839
  return true;
840
}
841
 
842
/* Return nonzero if the operands of expression X are unchanged from the
843
   start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
844
   or from INSN to the end of INSN's basic block (if AVAIL_P != 0).  */
845
 
846
static int
847
oprs_unchanged_p (const_rtx x, const_rtx insn, int avail_p)
848
{
849
  int i, j;
850
  enum rtx_code code;
851
  const char *fmt;
852
 
853
  if (x == 0)
854
    return 1;
855
 
856
  code = GET_CODE (x);
857
  switch (code)
858
    {
859
    case REG:
860
      {
861
        struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
862
 
863
        if (info->last_bb != current_bb)
864
          return 1;
865
        if (avail_p)
866
          return info->last_set < DF_INSN_LUID (insn);
867
        else
868
          return info->first_set >= DF_INSN_LUID (insn);
869
      }
870
 
871
    case MEM:
872
      if (load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
873
                                  x, avail_p))
874
        return 0;
875
      else
876
        return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
877
 
878
    case PRE_DEC:
879
    case PRE_INC:
880
    case POST_DEC:
881
    case POST_INC:
882
    case PRE_MODIFY:
883
    case POST_MODIFY:
884
      return 0;
885
 
886
    case PC:
887
    case CC0: /*FIXME*/
888
    case CONST:
889
    case CONST_INT:
890
    case CONST_DOUBLE:
891
    case CONST_FIXED:
892
    case CONST_VECTOR:
893
    case SYMBOL_REF:
894
    case LABEL_REF:
895
    case ADDR_VEC:
896
    case ADDR_DIFF_VEC:
897
      return 1;
898
 
899
    default:
900
      break;
901
    }
902
 
903
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
904
    {
905
      if (fmt[i] == 'e')
906
        {
907
          /* If we are about to do the last recursive call needed at this
908
             level, change it into iteration.  This function is called enough
909
             to be worth it.  */
910
          if (i == 0)
911
            return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
912
 
913
          else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
914
            return 0;
915
        }
916
      else if (fmt[i] == 'E')
917
        for (j = 0; j < XVECLEN (x, i); j++)
918
          if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
919
            return 0;
920
    }
921
 
922
  return 1;
923
}
924
 
925
/* Used for communication between mems_conflict_for_gcse_p and
926
   load_killed_in_block_p.  Nonzero if mems_conflict_for_gcse_p finds a
927
   conflict between two memory references.  */
928
static int gcse_mems_conflict_p;
929
 
930
/* Used for communication between mems_conflict_for_gcse_p and
931
   load_killed_in_block_p.  A memory reference for a load instruction,
932
   mems_conflict_for_gcse_p will see if a memory store conflicts with
933
   this memory load.  */
934
static const_rtx gcse_mem_operand;
935
 
936
/* DEST is the output of an instruction.  If it is a memory reference, and
937
   possibly conflicts with the load found in gcse_mem_operand, then set
938
   gcse_mems_conflict_p to a nonzero value.  */
939
 
940
static void
941
mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
942
                          void *data ATTRIBUTE_UNUSED)
943
{
944
  while (GET_CODE (dest) == SUBREG
945
         || GET_CODE (dest) == ZERO_EXTRACT
946
         || GET_CODE (dest) == STRICT_LOW_PART)
947
    dest = XEXP (dest, 0);
948
 
949
  /* If DEST is not a MEM, then it will not conflict with the load.  Note
950
     that function calls are assumed to clobber memory, but are handled
951
     elsewhere.  */
952
  if (! MEM_P (dest))
953
    return;
954
 
955
  /* If we are setting a MEM in our list of specially recognized MEMs,
956
     don't mark as killed this time.  */
957
 
958
  if (expr_equiv_p (dest, gcse_mem_operand) && pre_ldst_mems != NULL)
959
    {
960
      if (!find_rtx_in_ldst (dest))
961
        gcse_mems_conflict_p = 1;
962
      return;
963
    }
964
 
965
  if (true_dependence (dest, GET_MODE (dest), gcse_mem_operand,
966
                       rtx_addr_varies_p))
967
    gcse_mems_conflict_p = 1;
968
}
969
 
970
/* Return nonzero if the expression in X (a memory reference) is killed
971
   in block BB before or after the insn with the LUID in UID_LIMIT.
972
   AVAIL_P is nonzero for kills after UID_LIMIT, and zero for kills
973
   before UID_LIMIT.
974
 
975
   To check the entire block, set UID_LIMIT to max_uid + 1 and
976
   AVAIL_P to 0.  */
977
 
978
static int
979
load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x, int avail_p)
980
{
981
  rtx list_entry = modify_mem_list[bb->index];
982
 
983
  /* If this is a readonly then we aren't going to be changing it.  */
984
  if (MEM_READONLY_P (x))
985
    return 0;
986
 
987
  while (list_entry)
988
    {
989
      rtx setter;
990
      /* Ignore entries in the list that do not apply.  */
991
      if ((avail_p
992
           && DF_INSN_LUID (XEXP (list_entry, 0)) < uid_limit)
993
          || (! avail_p
994
              && DF_INSN_LUID (XEXP (list_entry, 0)) > uid_limit))
995
        {
996
          list_entry = XEXP (list_entry, 1);
997
          continue;
998
        }
999
 
1000
      setter = XEXP (list_entry, 0);
1001
 
1002
      /* If SETTER is a call everything is clobbered.  Note that calls
1003
         to pure functions are never put on the list, so we need not
1004
         worry about them.  */
1005
      if (CALL_P (setter))
1006
        return 1;
1007
 
1008
      /* SETTER must be an INSN of some kind that sets memory.  Call
1009
         note_stores to examine each hunk of memory that is modified.
1010
 
1011
         The note_stores interface is pretty limited, so we have to
1012
         communicate via global variables.  Yuk.  */
1013
      gcse_mem_operand = x;
1014
      gcse_mems_conflict_p = 0;
1015
      note_stores (PATTERN (setter), mems_conflict_for_gcse_p, NULL);
1016
      if (gcse_mems_conflict_p)
1017
        return 1;
1018
      list_entry = XEXP (list_entry, 1);
1019
    }
1020
  return 0;
1021
}
1022
 
1023
/* Return nonzero if the operands of expression X are unchanged from
1024
   the start of INSN's basic block up to but not including INSN.  */
1025
 
1026
static int
1027
oprs_anticipatable_p (const_rtx x, const_rtx insn)
1028
{
1029
  return oprs_unchanged_p (x, insn, 0);
1030
}
1031
 
1032
/* Return nonzero if the operands of expression X are unchanged from
1033
   INSN to the end of INSN's basic block.  */
1034
 
1035
static int
1036
oprs_available_p (const_rtx x, const_rtx insn)
1037
{
1038
  return oprs_unchanged_p (x, insn, 1);
1039
}
1040
 
1041
/* Hash expression X.
1042
 
1043
   MODE is only used if X is a CONST_INT.  DO_NOT_RECORD_P is a boolean
1044
   indicating if a volatile operand is found or if the expression contains
1045
   something we don't want to insert in the table.  HASH_TABLE_SIZE is
1046
   the current size of the hash table to be probed.  */
1047
 
1048
static unsigned int
1049
hash_expr (const_rtx x, enum machine_mode mode, int *do_not_record_p,
1050
           int hash_table_size)
1051
{
1052
  unsigned int hash;
1053
 
1054
  *do_not_record_p = 0;
1055
 
1056
  hash = hash_rtx (x, mode, do_not_record_p,
1057
                   NULL,  /*have_reg_qty=*/false);
1058
  return hash % hash_table_size;
1059
}
1060
 
1061
/* Hash a set of register REGNO.
1062
 
1063
   Sets are hashed on the register that is set.  This simplifies the PRE copy
1064
   propagation code.
1065
 
1066
   ??? May need to make things more elaborate.  Later, as necessary.  */
1067
 
1068
static unsigned int
1069
hash_set (int regno, int hash_table_size)
1070
{
1071
  unsigned int hash;
1072
 
1073
  hash = regno;
1074
  return hash % hash_table_size;
1075
}
1076
 
1077
/* Return nonzero if exp1 is equivalent to exp2.  */
1078
 
1079
static int
1080
expr_equiv_p (const_rtx x, const_rtx y)
1081
{
1082
  return exp_equiv_p (x, y, 0, true);
1083
}
1084
 
1085
/* Insert expression X in INSN in the hash TABLE.
1086
   If it is already present, record it as the last occurrence in INSN's
1087
   basic block.
1088
 
1089
   MODE is the mode of the value X is being stored into.
1090
   It is only used if X is a CONST_INT.
1091
 
1092
   ANTIC_P is nonzero if X is an anticipatable expression.
1093
   AVAIL_P is nonzero if X is an available expression.  */
1094
 
1095
static void
1096
insert_expr_in_table (rtx x, enum machine_mode mode, rtx insn, int antic_p,
1097
                      int avail_p, struct hash_table_d *table)
1098
{
1099
  int found, do_not_record_p;
1100
  unsigned int hash;
1101
  struct expr *cur_expr, *last_expr = NULL;
1102
  struct occr *antic_occr, *avail_occr;
1103
 
1104
  hash = hash_expr (x, mode, &do_not_record_p, table->size);
1105
 
1106
  /* Do not insert expression in table if it contains volatile operands,
1107
     or if hash_expr determines the expression is something we don't want
1108
     to or can't handle.  */
1109
  if (do_not_record_p)
1110
    return;
1111
 
1112
  cur_expr = table->table[hash];
1113
  found = 0;
1114
 
1115
  while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1116
    {
1117
      /* If the expression isn't found, save a pointer to the end of
1118
         the list.  */
1119
      last_expr = cur_expr;
1120
      cur_expr = cur_expr->next_same_hash;
1121
    }
1122
 
1123
  if (! found)
1124
    {
1125
      cur_expr = GOBNEW (struct expr);
1126
      bytes_used += sizeof (struct expr);
1127
      if (table->table[hash] == NULL)
1128
        /* This is the first pattern that hashed to this index.  */
1129
        table->table[hash] = cur_expr;
1130
      else
1131
        /* Add EXPR to end of this hash chain.  */
1132
        last_expr->next_same_hash = cur_expr;
1133
 
1134
      /* Set the fields of the expr element.  */
1135
      cur_expr->expr = x;
1136
      cur_expr->bitmap_index = table->n_elems++;
1137
      cur_expr->next_same_hash = NULL;
1138
      cur_expr->antic_occr = NULL;
1139
      cur_expr->avail_occr = NULL;
1140
    }
1141
 
1142
  /* Now record the occurrence(s).  */
1143
  if (antic_p)
1144
    {
1145
      antic_occr = cur_expr->antic_occr;
1146
 
1147
      if (antic_occr
1148
          && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
1149
        antic_occr = NULL;
1150
 
1151
      if (antic_occr)
1152
        /* Found another instance of the expression in the same basic block.
1153
           Prefer the currently recorded one.  We want the first one in the
1154
           block and the block is scanned from start to end.  */
1155
        ; /* nothing to do */
1156
      else
1157
        {
1158
          /* First occurrence of this expression in this basic block.  */
1159
          antic_occr = GOBNEW (struct occr);
1160
          bytes_used += sizeof (struct occr);
1161
          antic_occr->insn = insn;
1162
          antic_occr->next = cur_expr->antic_occr;
1163
          antic_occr->deleted_p = 0;
1164
          cur_expr->antic_occr = antic_occr;
1165
        }
1166
    }
1167
 
1168
  if (avail_p)
1169
    {
1170
      avail_occr = cur_expr->avail_occr;
1171
 
1172
      if (avail_occr
1173
          && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
1174
        {
1175
          /* Found another instance of the expression in the same basic block.
1176
             Prefer this occurrence to the currently recorded one.  We want
1177
             the last one in the block and the block is scanned from start
1178
             to end.  */
1179
          avail_occr->insn = insn;
1180
        }
1181
      else
1182
        {
1183
          /* First occurrence of this expression in this basic block.  */
1184
          avail_occr = GOBNEW (struct occr);
1185
          bytes_used += sizeof (struct occr);
1186
          avail_occr->insn = insn;
1187
          avail_occr->next = cur_expr->avail_occr;
1188
          avail_occr->deleted_p = 0;
1189
          cur_expr->avail_occr = avail_occr;
1190
        }
1191
    }
1192
}
1193
 
1194
/* Insert pattern X in INSN in the hash table.
1195
   X is a SET of a reg to either another reg or a constant.
1196
   If it is already present, record it as the last occurrence in INSN's
1197
   basic block.  */
1198
 
1199
static void
1200
insert_set_in_table (rtx x, rtx insn, struct hash_table_d *table)
1201
{
1202
  int found;
1203
  unsigned int hash;
1204
  struct expr *cur_expr, *last_expr = NULL;
1205
  struct occr *cur_occr;
1206
 
1207
  gcc_assert (GET_CODE (x) == SET && REG_P (SET_DEST (x)));
1208
 
1209
  hash = hash_set (REGNO (SET_DEST (x)), table->size);
1210
 
1211
  cur_expr = table->table[hash];
1212
  found = 0;
1213
 
1214
  while (cur_expr && 0 == (found = expr_equiv_p (cur_expr->expr, x)))
1215
    {
1216
      /* If the expression isn't found, save a pointer to the end of
1217
         the list.  */
1218
      last_expr = cur_expr;
1219
      cur_expr = cur_expr->next_same_hash;
1220
    }
1221
 
1222
  if (! found)
1223
    {
1224
      cur_expr = GOBNEW (struct expr);
1225
      bytes_used += sizeof (struct expr);
1226
      if (table->table[hash] == NULL)
1227
        /* This is the first pattern that hashed to this index.  */
1228
        table->table[hash] = cur_expr;
1229
      else
1230
        /* Add EXPR to end of this hash chain.  */
1231
        last_expr->next_same_hash = cur_expr;
1232
 
1233
      /* Set the fields of the expr element.
1234
         We must copy X because it can be modified when copy propagation is
1235
         performed on its operands.  */
1236
      cur_expr->expr = copy_rtx (x);
1237
      cur_expr->bitmap_index = table->n_elems++;
1238
      cur_expr->next_same_hash = NULL;
1239
      cur_expr->antic_occr = NULL;
1240
      cur_expr->avail_occr = NULL;
1241
    }
1242
 
1243
  /* Now record the occurrence.  */
1244
  cur_occr = cur_expr->avail_occr;
1245
 
1246
  if (cur_occr
1247
      && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
1248
    {
1249
      /* Found another instance of the expression in the same basic block.
1250
         Prefer this occurrence to the currently recorded one.  We want
1251
         the last one in the block and the block is scanned from start
1252
         to end.  */
1253
      cur_occr->insn = insn;
1254
    }
1255
  else
1256
    {
1257
      /* First occurrence of this expression in this basic block.  */
1258
      cur_occr = GOBNEW (struct occr);
1259
      bytes_used += sizeof (struct occr);
1260
      cur_occr->insn = insn;
1261
      cur_occr->next = cur_expr->avail_occr;
1262
      cur_occr->deleted_p = 0;
1263
      cur_expr->avail_occr = cur_occr;
1264
    }
1265
}
1266
 
1267
/* Determine whether the rtx X should be treated as a constant for
1268
   the purposes of GCSE's constant propagation.  */
1269
 
1270
static bool
1271
gcse_constant_p (const_rtx x)
1272
{
1273
  /* Consider a COMPARE of two integers constant.  */
1274
  if (GET_CODE (x) == COMPARE
1275
      && CONST_INT_P (XEXP (x, 0))
1276
      && CONST_INT_P (XEXP (x, 1)))
1277
    return true;
1278
 
1279
  /* Consider a COMPARE of the same registers is a constant
1280
     if they are not floating point registers.  */
1281
  if (GET_CODE(x) == COMPARE
1282
      && REG_P (XEXP (x, 0)) && REG_P (XEXP (x, 1))
1283
      && REGNO (XEXP (x, 0)) == REGNO (XEXP (x, 1))
1284
      && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 0)))
1285
      && ! FLOAT_MODE_P (GET_MODE (XEXP (x, 1))))
1286
    return true;
1287
 
1288
  /* Since X might be inserted more than once we have to take care that it
1289
     is sharable.  */
1290
  return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
1291
}
1292
 
1293
/* Scan pattern PAT of INSN and add an entry to the hash TABLE (set or
1294
   expression one).  */
1295
 
1296
static void
1297
hash_scan_set (rtx pat, rtx insn, struct hash_table_d *table)
1298
{
1299
  rtx src = SET_SRC (pat);
1300
  rtx dest = SET_DEST (pat);
1301
  rtx note;
1302
 
1303
  if (GET_CODE (src) == CALL)
1304
    hash_scan_call (src, insn, table);
1305
 
1306
  else if (REG_P (dest))
1307
    {
1308
      unsigned int regno = REGNO (dest);
1309
      rtx tmp;
1310
 
1311
      /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
1312
 
1313
         This allows us to do a single GCSE pass and still eliminate
1314
         redundant constants, addresses or other expressions that are
1315
         constructed with multiple instructions.
1316
 
1317
         However, keep the original SRC if INSN is a simple reg-reg move.  In
1318
         In this case, there will almost always be a REG_EQUAL note on the
1319
         insn that sets SRC.  By recording the REG_EQUAL value here as SRC
1320
         for INSN, we miss copy propagation opportunities and we perform the
1321
         same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
1322
         do more than one PRE GCSE pass.
1323
 
1324
         Note that this does not impede profitable constant propagations.  We
1325
         "look through" reg-reg sets in lookup_avail_set.  */
1326
      note = find_reg_equal_equiv_note (insn);
1327
      if (note != 0
1328
          && REG_NOTE_KIND (note) == REG_EQUAL
1329
          && !REG_P (src)
1330
          && (table->set_p
1331
              ? gcse_constant_p (XEXP (note, 0))
1332
              : want_to_gcse_p (XEXP (note, 0))))
1333
        src = XEXP (note, 0), pat = gen_rtx_SET (VOIDmode, dest, src);
1334
 
1335
      /* Only record sets of pseudo-regs in the hash table.  */
1336
      if (! table->set_p
1337
          && regno >= FIRST_PSEUDO_REGISTER
1338
          /* Don't GCSE something if we can't do a reg/reg copy.  */
1339
          && can_copy_p (GET_MODE (dest))
1340
          /* GCSE commonly inserts instruction after the insn.  We can't
1341
             do that easily for EH edges so disable GCSE on these for now.  */
1342
          /* ??? We can now easily create new EH landing pads at the
1343
             gimple level, for splitting edges; there's no reason we
1344
             can't do the same thing at the rtl level.  */
1345
          && !can_throw_internal (insn)
1346
          /* Is SET_SRC something we want to gcse?  */
1347
          && want_to_gcse_p (src)
1348
          /* Don't CSE a nop.  */
1349
          && ! set_noop_p (pat)
1350
          /* Don't GCSE if it has attached REG_EQUIV note.
1351
             At this point this only function parameters should have
1352
             REG_EQUIV notes and if the argument slot is used somewhere
1353
             explicitly, it means address of parameter has been taken,
1354
             so we should not extend the lifetime of the pseudo.  */
1355
          && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
1356
        {
1357
          /* An expression is not anticipatable if its operands are
1358
             modified before this insn or if this is not the only SET in
1359
             this insn.  The latter condition does not have to mean that
1360
             SRC itself is not anticipatable, but we just will not be
1361
             able to handle code motion of insns with multiple sets.  */
1362
          int antic_p = oprs_anticipatable_p (src, insn)
1363
                        && !multiple_sets (insn);
1364
          /* An expression is not available if its operands are
1365
             subsequently modified, including this insn.  It's also not
1366
             available if this is a branch, because we can't insert
1367
             a set after the branch.  */
1368
          int avail_p = (oprs_available_p (src, insn)
1369
                         && ! JUMP_P (insn));
1370
 
1371
          insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p, table);
1372
        }
1373
 
1374
      /* Record sets for constant/copy propagation.  */
1375
      else if (table->set_p
1376
               && regno >= FIRST_PSEUDO_REGISTER
1377
               && ((REG_P (src)
1378
                    && REGNO (src) >= FIRST_PSEUDO_REGISTER
1379
                    && can_copy_p (GET_MODE (dest))
1380
                    && REGNO (src) != regno)
1381
                   || gcse_constant_p (src))
1382
               /* A copy is not available if its src or dest is subsequently
1383
                  modified.  Here we want to search from INSN+1 on, but
1384
                  oprs_available_p searches from INSN on.  */
1385
               && (insn == BB_END (BLOCK_FOR_INSN (insn))
1386
                   || (tmp = next_nonnote_insn (insn)) == NULL_RTX
1387
                   || BLOCK_FOR_INSN (tmp) != BLOCK_FOR_INSN (insn)
1388
                   || oprs_available_p (pat, tmp)))
1389
        insert_set_in_table (pat, insn, table);
1390
    }
1391
  /* In case of store we want to consider the memory value as available in
1392
     the REG stored in that memory. This makes it possible to remove
1393
     redundant loads from due to stores to the same location.  */
1394
  else if (flag_gcse_las && REG_P (src) && MEM_P (dest))
1395
      {
1396
        unsigned int regno = REGNO (src);
1397
 
1398
        /* Do not do this for constant/copy propagation.  */
1399
        if (! table->set_p
1400
            /* Only record sets of pseudo-regs in the hash table.  */
1401
            && regno >= FIRST_PSEUDO_REGISTER
1402
           /* Don't GCSE something if we can't do a reg/reg copy.  */
1403
           && can_copy_p (GET_MODE (src))
1404
           /* GCSE commonly inserts instruction after the insn.  We can't
1405
              do that easily for EH edges so disable GCSE on these for now.  */
1406
           && !can_throw_internal (insn)
1407
           /* Is SET_DEST something we want to gcse?  */
1408
           && want_to_gcse_p (dest)
1409
           /* Don't CSE a nop.  */
1410
           && ! set_noop_p (pat)
1411
           /* Don't GCSE if it has attached REG_EQUIV note.
1412
              At this point this only function parameters should have
1413
              REG_EQUIV notes and if the argument slot is used somewhere
1414
              explicitly, it means address of parameter has been taken,
1415
              so we should not extend the lifetime of the pseudo.  */
1416
           && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
1417
               || ! MEM_P (XEXP (note, 0))))
1418
             {
1419
               /* Stores are never anticipatable.  */
1420
               int antic_p = 0;
1421
               /* An expression is not available if its operands are
1422
                  subsequently modified, including this insn.  It's also not
1423
                  available if this is a branch, because we can't insert
1424
                  a set after the branch.  */
1425
               int avail_p = oprs_available_p (dest, insn)
1426
                             && ! JUMP_P (insn);
1427
 
1428
               /* Record the memory expression (DEST) in the hash table.  */
1429
               insert_expr_in_table (dest, GET_MODE (dest), insn,
1430
                                     antic_p, avail_p, table);
1431
             }
1432
      }
1433
}
1434
 
1435
static void
1436
hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1437
                   struct hash_table_d *table ATTRIBUTE_UNUSED)
1438
{
1439
  /* Currently nothing to do.  */
1440
}
1441
 
1442
static void
1443
hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx insn ATTRIBUTE_UNUSED,
1444
                struct hash_table_d *table ATTRIBUTE_UNUSED)
1445
{
1446
  /* Currently nothing to do.  */
1447
}
1448
 
1449
/* Process INSN and add hash table entries as appropriate.
1450
 
1451
   Only available expressions that set a single pseudo-reg are recorded.
1452
 
1453
   Single sets in a PARALLEL could be handled, but it's an extra complication
1454
   that isn't dealt with right now.  The trick is handling the CLOBBERs that
1455
   are also in the PARALLEL.  Later.
1456
 
1457
   If SET_P is nonzero, this is for the assignment hash table,
1458
   otherwise it is for the expression hash table.  */
1459
 
1460
static void
1461
hash_scan_insn (rtx insn, struct hash_table_d *table)
1462
{
1463
  rtx pat = PATTERN (insn);
1464
  int i;
1465
 
1466
  /* Pick out the sets of INSN and for other forms of instructions record
1467
     what's been modified.  */
1468
 
1469
  if (GET_CODE (pat) == SET)
1470
    hash_scan_set (pat, insn, table);
1471
  else if (GET_CODE (pat) == PARALLEL)
1472
    for (i = 0; i < XVECLEN (pat, 0); i++)
1473
      {
1474
        rtx x = XVECEXP (pat, 0, i);
1475
 
1476
        if (GET_CODE (x) == SET)
1477
          hash_scan_set (x, insn, table);
1478
        else if (GET_CODE (x) == CLOBBER)
1479
          hash_scan_clobber (x, insn, table);
1480
        else if (GET_CODE (x) == CALL)
1481
          hash_scan_call (x, insn, table);
1482
      }
1483
 
1484
  else if (GET_CODE (pat) == CLOBBER)
1485
    hash_scan_clobber (pat, insn, table);
1486
  else if (GET_CODE (pat) == CALL)
1487
    hash_scan_call (pat, insn, table);
1488
}
1489
 
1490
static void
1491
dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
1492
{
1493
  int i;
1494
  /* Flattened out table, so it's printed in proper order.  */
1495
  struct expr **flat_table;
1496
  unsigned int *hash_val;
1497
  struct expr *expr;
1498
 
1499
  flat_table = XCNEWVEC (struct expr *, table->n_elems);
1500
  hash_val = XNEWVEC (unsigned int, table->n_elems);
1501
 
1502
  for (i = 0; i < (int) table->size; i++)
1503
    for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
1504
      {
1505
        flat_table[expr->bitmap_index] = expr;
1506
        hash_val[expr->bitmap_index] = i;
1507
      }
1508
 
1509
  fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1510
           name, table->size, table->n_elems);
1511
 
1512
  for (i = 0; i < (int) table->n_elems; i++)
1513
    if (flat_table[i] != 0)
1514
      {
1515
        expr = flat_table[i];
1516
        fprintf (file, "Index %d (hash value %d)\n  ",
1517
                 expr->bitmap_index, hash_val[i]);
1518
        print_rtl (file, expr->expr);
1519
        fprintf (file, "\n");
1520
      }
1521
 
1522
  fprintf (file, "\n");
1523
 
1524
  free (flat_table);
1525
  free (hash_val);
1526
}
1527
 
1528
/* Record register first/last/block set information for REGNO in INSN.
1529
 
1530
   first_set records the first place in the block where the register
1531
   is set and is used to compute "anticipatability".
1532
 
1533
   last_set records the last place in the block where the register
1534
   is set and is used to compute "availability".
1535
 
1536
   last_bb records the block for which first_set and last_set are
1537
   valid, as a quick test to invalidate them.  */
1538
 
1539
static void
1540
record_last_reg_set_info (rtx insn, int regno)
1541
{
1542
  struct reg_avail_info *info = &reg_avail_info[regno];
1543
  int luid = DF_INSN_LUID (insn);
1544
 
1545
  info->last_set = luid;
1546
  if (info->last_bb != current_bb)
1547
    {
1548
      info->last_bb = current_bb;
1549
      info->first_set = luid;
1550
    }
1551
}
1552
 
1553
 
1554
/* Record all of the canonicalized MEMs of record_last_mem_set_info's insn.
1555
   Note we store a pair of elements in the list, so they have to be
1556
   taken off pairwise.  */
1557
 
1558
static void
1559
canon_list_insert (rtx dest ATTRIBUTE_UNUSED, const_rtx unused1 ATTRIBUTE_UNUSED,
1560
                   void * v_insn)
1561
{
1562
  rtx dest_addr, insn;
1563
  int bb;
1564
 
1565
  while (GET_CODE (dest) == SUBREG
1566
      || GET_CODE (dest) == ZERO_EXTRACT
1567
      || GET_CODE (dest) == STRICT_LOW_PART)
1568
    dest = XEXP (dest, 0);
1569
 
1570
  /* If DEST is not a MEM, then it will not conflict with a load.  Note
1571
     that function calls are assumed to clobber memory, but are handled
1572
     elsewhere.  */
1573
 
1574
  if (! MEM_P (dest))
1575
    return;
1576
 
1577
  dest_addr = get_addr (XEXP (dest, 0));
1578
  dest_addr = canon_rtx (dest_addr);
1579
  insn = (rtx) v_insn;
1580
  bb = BLOCK_FOR_INSN (insn)->index;
1581
 
1582
  canon_modify_mem_list[bb] =
1583
    alloc_EXPR_LIST (VOIDmode, dest_addr, canon_modify_mem_list[bb]);
1584
  canon_modify_mem_list[bb] =
1585
    alloc_EXPR_LIST (VOIDmode, dest, canon_modify_mem_list[bb]);
1586
}
1587
 
1588
/* Record memory modification information for INSN.  We do not actually care
1589
   about the memory location(s) that are set, or even how they are set (consider
1590
   a CALL_INSN).  We merely need to record which insns modify memory.  */
1591
 
1592
static void
1593
record_last_mem_set_info (rtx insn)
1594
{
1595
  int bb = BLOCK_FOR_INSN (insn)->index;
1596
 
1597
  /* load_killed_in_block_p will handle the case of calls clobbering
1598
     everything.  */
1599
  modify_mem_list[bb] = alloc_INSN_LIST (insn, modify_mem_list[bb]);
1600
  bitmap_set_bit (modify_mem_list_set, bb);
1601
 
1602
  if (CALL_P (insn))
1603
    {
1604
      /* Note that traversals of this loop (other than for free-ing)
1605
         will break after encountering a CALL_INSN.  So, there's no
1606
         need to insert a pair of items, as canon_list_insert does.  */
1607
      canon_modify_mem_list[bb] =
1608
        alloc_INSN_LIST (insn, canon_modify_mem_list[bb]);
1609
      bitmap_set_bit (blocks_with_calls, bb);
1610
    }
1611
  else
1612
    note_stores (PATTERN (insn), canon_list_insert, (void*) insn);
1613
}
1614
 
1615
/* Called from compute_hash_table via note_stores to handle one
1616
   SET or CLOBBER in an insn.  DATA is really the instruction in which
1617
   the SET is taking place.  */
1618
 
1619
static void
1620
record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
1621
{
1622
  rtx last_set_insn = (rtx) data;
1623
 
1624
  if (GET_CODE (dest) == SUBREG)
1625
    dest = SUBREG_REG (dest);
1626
 
1627
  if (REG_P (dest))
1628
    record_last_reg_set_info (last_set_insn, REGNO (dest));
1629
  else if (MEM_P (dest)
1630
           /* Ignore pushes, they clobber nothing.  */
1631
           && ! push_operand (dest, GET_MODE (dest)))
1632
    record_last_mem_set_info (last_set_insn);
1633
}
1634
 
1635
/* Top level function to create an expression or assignment hash table.
1636
 
1637
   Expression entries are placed in the hash table if
1638
   - they are of the form (set (pseudo-reg) src),
1639
   - src is something we want to perform GCSE on,
1640
   - none of the operands are subsequently modified in the block
1641
 
1642
   Assignment entries are placed in the hash table if
1643
   - they are of the form (set (pseudo-reg) src),
1644
   - src is something we want to perform const/copy propagation on,
1645
   - none of the operands or target are subsequently modified in the block
1646
 
1647
   Currently src must be a pseudo-reg or a const_int.
1648
 
1649
   TABLE is the table computed.  */
1650
 
1651
static void
1652
compute_hash_table_work (struct hash_table_d *table)
1653
{
1654
  int i;
1655
 
1656
  /* re-Cache any INSN_LIST nodes we have allocated.  */
1657
  clear_modify_mem_tables ();
1658
  /* Some working arrays used to track first and last set in each block.  */
1659
  reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
1660
 
1661
  for (i = 0; i < max_reg_num (); ++i)
1662
    reg_avail_info[i].last_bb = NULL;
1663
 
1664
  FOR_EACH_BB (current_bb)
1665
    {
1666
      rtx insn;
1667
      unsigned int regno;
1668
 
1669
      /* First pass over the instructions records information used to
1670
         determine when registers and memory are first and last set.  */
1671
      FOR_BB_INSNS (current_bb, insn)
1672
        {
1673
          if (! INSN_P (insn))
1674
            continue;
1675
 
1676
          if (CALL_P (insn))
1677
            {
1678
              for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
1679
                if (TEST_HARD_REG_BIT (regs_invalidated_by_call, regno))
1680
                  record_last_reg_set_info (insn, regno);
1681
 
1682
              mark_call (insn);
1683
            }
1684
 
1685
          note_stores (PATTERN (insn), record_last_set_info, insn);
1686
        }
1687
 
1688
      /* Insert implicit sets in the hash table.  */
1689
      if (table->set_p
1690
          && implicit_sets[current_bb->index] != NULL_RTX)
1691
        hash_scan_set (implicit_sets[current_bb->index],
1692
                       BB_HEAD (current_bb), table);
1693
 
1694
      /* The next pass builds the hash table.  */
1695
      FOR_BB_INSNS (current_bb, insn)
1696
        if (INSN_P (insn))
1697
          hash_scan_insn (insn, table);
1698
    }
1699
 
1700
  free (reg_avail_info);
1701
  reg_avail_info = NULL;
1702
}
1703
 
1704
/* Allocate space for the set/expr hash TABLE.
1705
   It is used to determine the number of buckets to use.
1706
   SET_P determines whether set or expression table will
1707
   be created.  */
1708
 
1709
static void
1710
alloc_hash_table (struct hash_table_d *table, int set_p)
1711
{
1712
  int n;
1713
 
1714
  n = get_max_insn_count ();
1715
 
1716
  table->size = n / 4;
1717
  if (table->size < 11)
1718
    table->size = 11;
1719
 
1720
  /* Attempt to maintain efficient use of hash table.
1721
     Making it an odd number is simplest for now.
1722
     ??? Later take some measurements.  */
1723
  table->size |= 1;
1724
  n = table->size * sizeof (struct expr *);
1725
  table->table = GNEWVAR (struct expr *, n);
1726
  table->set_p = set_p;
1727
}
1728
 
1729
/* Free things allocated by alloc_hash_table.  */
1730
 
1731
static void
1732
free_hash_table (struct hash_table_d *table)
1733
{
1734
  free (table->table);
1735
}
1736
 
1737
/* Compute the hash TABLE for doing copy/const propagation or
1738
   expression hash table.  */
1739
 
1740
static void
1741
compute_hash_table (struct hash_table_d *table)
1742
{
1743
  /* Initialize count of number of entries in hash table.  */
1744
  table->n_elems = 0;
1745
  memset (table->table, 0, table->size * sizeof (struct expr *));
1746
 
1747
  compute_hash_table_work (table);
1748
}
1749
 
1750
/* Expression tracking support.  */
1751
 
1752
/* Lookup REGNO in the set TABLE.  The result is a pointer to the
1753
   table entry, or NULL if not found.  */
1754
 
1755
static struct expr *
1756
lookup_set (unsigned int regno, struct hash_table_d *table)
1757
{
1758
  unsigned int hash = hash_set (regno, table->size);
1759
  struct expr *expr;
1760
 
1761
  expr = table->table[hash];
1762
 
1763
  while (expr && REGNO (SET_DEST (expr->expr)) != regno)
1764
    expr = expr->next_same_hash;
1765
 
1766
  return expr;
1767
}
1768
 
1769
/* Return the next entry for REGNO in list EXPR.  */
1770
 
1771
static struct expr *
1772
next_set (unsigned int regno, struct expr *expr)
1773
{
1774
  do
1775
    expr = expr->next_same_hash;
1776
  while (expr && REGNO (SET_DEST (expr->expr)) != regno);
1777
 
1778
  return expr;
1779
}
1780
 
1781
/* Like free_INSN_LIST_list or free_EXPR_LIST_list, except that the node
1782
   types may be mixed.  */
1783
 
1784
static void
1785
free_insn_expr_list_list (rtx *listp)
1786
{
1787
  rtx list, next;
1788
 
1789
  for (list = *listp; list ; list = next)
1790
    {
1791
      next = XEXP (list, 1);
1792
      if (GET_CODE (list) == EXPR_LIST)
1793
        free_EXPR_LIST_node (list);
1794
      else
1795
        free_INSN_LIST_node (list);
1796
    }
1797
 
1798
  *listp = NULL;
1799
}
1800
 
1801
/* Clear canon_modify_mem_list and modify_mem_list tables.  */
1802
static void
1803
clear_modify_mem_tables (void)
1804
{
1805
  unsigned i;
1806
  bitmap_iterator bi;
1807
 
1808
  EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
1809
    {
1810
      free_INSN_LIST_list (modify_mem_list + i);
1811
      free_insn_expr_list_list (canon_modify_mem_list + i);
1812
    }
1813
  bitmap_clear (modify_mem_list_set);
1814
  bitmap_clear (blocks_with_calls);
1815
}
1816
 
1817
/* Release memory used by modify_mem_list_set.  */
1818
 
1819
static void
1820
free_modify_mem_tables (void)
1821
{
1822
  clear_modify_mem_tables ();
1823
  free (modify_mem_list);
1824
  free (canon_modify_mem_list);
1825
  modify_mem_list = 0;
1826
  canon_modify_mem_list = 0;
1827
}
1828
 
1829
/* Reset tables used to keep track of what's still available [since the
1830
   start of the block].  */
1831
 
1832
static void
1833
reset_opr_set_tables (void)
1834
{
1835
  /* Maintain a bitmap of which regs have been set since beginning of
1836
     the block.  */
1837
  CLEAR_REG_SET (reg_set_bitmap);
1838
 
1839
  /* Also keep a record of the last instruction to modify memory.
1840
     For now this is very trivial, we only record whether any memory
1841
     location has been modified.  */
1842
  clear_modify_mem_tables ();
1843
}
1844
 
1845
/* Return nonzero if the operands of X are not set before INSN in
1846
   INSN's basic block.  */
1847
 
1848
static int
1849
oprs_not_set_p (const_rtx x, const_rtx insn)
1850
{
1851
  int i, j;
1852
  enum rtx_code code;
1853
  const char *fmt;
1854
 
1855
  if (x == 0)
1856
    return 1;
1857
 
1858
  code = GET_CODE (x);
1859
  switch (code)
1860
    {
1861
    case PC:
1862
    case CC0:
1863
    case CONST:
1864
    case CONST_INT:
1865
    case CONST_DOUBLE:
1866
    case CONST_FIXED:
1867
    case CONST_VECTOR:
1868
    case SYMBOL_REF:
1869
    case LABEL_REF:
1870
    case ADDR_VEC:
1871
    case ADDR_DIFF_VEC:
1872
      return 1;
1873
 
1874
    case MEM:
1875
      if (load_killed_in_block_p (BLOCK_FOR_INSN (insn),
1876
                                  DF_INSN_LUID (insn), x, 0))
1877
        return 0;
1878
      else
1879
        return oprs_not_set_p (XEXP (x, 0), insn);
1880
 
1881
    case REG:
1882
      return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
1883
 
1884
    default:
1885
      break;
1886
    }
1887
 
1888
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
1889
    {
1890
      if (fmt[i] == 'e')
1891
        {
1892
          /* If we are about to do the last recursive call
1893
             needed at this level, change it into iteration.
1894
             This function is called enough to be worth it.  */
1895
          if (i == 0)
1896
            return oprs_not_set_p (XEXP (x, i), insn);
1897
 
1898
          if (! oprs_not_set_p (XEXP (x, i), insn))
1899
            return 0;
1900
        }
1901
      else if (fmt[i] == 'E')
1902
        for (j = 0; j < XVECLEN (x, i); j++)
1903
          if (! oprs_not_set_p (XVECEXP (x, i, j), insn))
1904
            return 0;
1905
    }
1906
 
1907
  return 1;
1908
}
1909
 
1910
/* Mark things set by a CALL.  */
1911
 
1912
static void
1913
mark_call (rtx insn)
1914
{
1915
  if (! RTL_CONST_OR_PURE_CALL_P (insn))
1916
    record_last_mem_set_info (insn);
1917
}
1918
 
1919
/* Mark things set by a SET.  */
1920
 
1921
static void
1922
mark_set (rtx pat, rtx insn)
1923
{
1924
  rtx dest = SET_DEST (pat);
1925
 
1926
  while (GET_CODE (dest) == SUBREG
1927
         || GET_CODE (dest) == ZERO_EXTRACT
1928
         || GET_CODE (dest) == STRICT_LOW_PART)
1929
    dest = XEXP (dest, 0);
1930
 
1931
  if (REG_P (dest))
1932
    SET_REGNO_REG_SET (reg_set_bitmap, REGNO (dest));
1933
  else if (MEM_P (dest))
1934
    record_last_mem_set_info (insn);
1935
 
1936
  if (GET_CODE (SET_SRC (pat)) == CALL)
1937
    mark_call (insn);
1938
}
1939
 
1940
/* Record things set by a CLOBBER.  */
1941
 
1942
static void
1943
mark_clobber (rtx pat, rtx insn)
1944
{
1945
  rtx clob = XEXP (pat, 0);
1946
 
1947
  while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
1948
    clob = XEXP (clob, 0);
1949
 
1950
  if (REG_P (clob))
1951
    SET_REGNO_REG_SET (reg_set_bitmap, REGNO (clob));
1952
  else
1953
    record_last_mem_set_info (insn);
1954
}
1955
 
1956
/* Record things set by INSN.
1957
   This data is used by oprs_not_set_p.  */
1958
 
1959
static void
1960
mark_oprs_set (rtx insn)
1961
{
1962
  rtx pat = PATTERN (insn);
1963
  int i;
1964
 
1965
  if (GET_CODE (pat) == SET)
1966
    mark_set (pat, insn);
1967
  else if (GET_CODE (pat) == PARALLEL)
1968
    for (i = 0; i < XVECLEN (pat, 0); i++)
1969
      {
1970
        rtx x = XVECEXP (pat, 0, i);
1971
 
1972
        if (GET_CODE (x) == SET)
1973
          mark_set (x, insn);
1974
        else if (GET_CODE (x) == CLOBBER)
1975
          mark_clobber (x, insn);
1976
        else if (GET_CODE (x) == CALL)
1977
          mark_call (insn);
1978
      }
1979
 
1980
  else if (GET_CODE (pat) == CLOBBER)
1981
    mark_clobber (pat, insn);
1982
  else if (GET_CODE (pat) == CALL)
1983
    mark_call (insn);
1984
}
1985
 
1986
 
1987
/* Compute copy/constant propagation working variables.  */
1988
 
1989
/* Local properties of assignments.  */
1990
static sbitmap *cprop_pavloc;
1991
static sbitmap *cprop_absaltered;
1992
 
1993
/* Global properties of assignments (computed from the local properties).  */
1994
static sbitmap *cprop_avin;
1995
static sbitmap *cprop_avout;
1996
 
1997
/* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
1998
   basic blocks.  N_SETS is the number of sets.  */
1999
 
2000
static void
2001
alloc_cprop_mem (int n_blocks, int n_sets)
2002
{
2003
  cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
2004
  cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
2005
 
2006
  cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
2007
  cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
2008
}
2009
 
2010
/* Free vars used by copy/const propagation.  */
2011
 
2012
static void
2013
free_cprop_mem (void)
2014
{
2015
  sbitmap_vector_free (cprop_pavloc);
2016
  sbitmap_vector_free (cprop_absaltered);
2017
  sbitmap_vector_free (cprop_avin);
2018
  sbitmap_vector_free (cprop_avout);
2019
}
2020
 
2021
/* For each block, compute whether X is transparent.  X is either an
2022
   expression or an assignment [though we don't care which, for this context
2023
   an assignment is treated as an expression].  For each block where an
2024
   element of X is modified, set (SET_P == 1) or reset (SET_P == 0) the INDX
2025
   bit in BMAP.  */
2026
 
2027
static void
2028
compute_transp (const_rtx x, int indx, sbitmap *bmap, int set_p)
2029
{
2030
  int i, j;
2031
  enum rtx_code code;
2032
  const char *fmt;
2033
 
2034
  /* repeat is used to turn tail-recursion into iteration since GCC
2035
     can't do it when there's no return value.  */
2036
 repeat:
2037
 
2038
  if (x == 0)
2039
    return;
2040
 
2041
  code = GET_CODE (x);
2042
  switch (code)
2043
    {
2044
    case REG:
2045
      if (set_p)
2046
        {
2047
          df_ref def;
2048
          for (def = DF_REG_DEF_CHAIN (REGNO (x));
2049
               def;
2050
               def = DF_REF_NEXT_REG (def))
2051
            SET_BIT (bmap[DF_REF_BB (def)->index], indx);
2052
        }
2053
      else
2054
        {
2055
          df_ref def;
2056
          for (def = DF_REG_DEF_CHAIN (REGNO (x));
2057
               def;
2058
               def = DF_REF_NEXT_REG (def))
2059
            RESET_BIT (bmap[DF_REF_BB (def)->index], indx);
2060
        }
2061
 
2062
      return;
2063
 
2064
    case MEM:
2065
      if (! MEM_READONLY_P (x))
2066
        {
2067
          bitmap_iterator bi;
2068
          unsigned bb_index;
2069
 
2070
          /* First handle all the blocks with calls.  We don't need to
2071
             do any list walking for them.  */
2072
          EXECUTE_IF_SET_IN_BITMAP (blocks_with_calls, 0, bb_index, bi)
2073
            {
2074
              if (set_p)
2075
                SET_BIT (bmap[bb_index], indx);
2076
              else
2077
                RESET_BIT (bmap[bb_index], indx);
2078
            }
2079
 
2080
            /* Now iterate over the blocks which have memory modifications
2081
               but which do not have any calls.  */
2082
            EXECUTE_IF_AND_COMPL_IN_BITMAP (modify_mem_list_set,
2083
                                            blocks_with_calls,
2084
                                            0, bb_index, bi)
2085
              {
2086
                rtx list_entry = canon_modify_mem_list[bb_index];
2087
 
2088
                while (list_entry)
2089
                  {
2090
                    rtx dest, dest_addr;
2091
 
2092
                    /* LIST_ENTRY must be an INSN of some kind that sets memory.
2093
                       Examine each hunk of memory that is modified.  */
2094
 
2095
                    dest = XEXP (list_entry, 0);
2096
                    list_entry = XEXP (list_entry, 1);
2097
                    dest_addr = XEXP (list_entry, 0);
2098
 
2099
                    if (canon_true_dependence (dest, GET_MODE (dest), dest_addr,
2100
                                               x, NULL_RTX, rtx_addr_varies_p))
2101
                      {
2102
                        if (set_p)
2103
                          SET_BIT (bmap[bb_index], indx);
2104
                        else
2105
                          RESET_BIT (bmap[bb_index], indx);
2106
                        break;
2107
                      }
2108
                    list_entry = XEXP (list_entry, 1);
2109
                  }
2110
              }
2111
        }
2112
 
2113
      x = XEXP (x, 0);
2114
      goto repeat;
2115
 
2116
    case PC:
2117
    case CC0: /*FIXME*/
2118
    case CONST:
2119
    case CONST_INT:
2120
    case CONST_DOUBLE:
2121
    case CONST_FIXED:
2122
    case CONST_VECTOR:
2123
    case SYMBOL_REF:
2124
    case LABEL_REF:
2125
    case ADDR_VEC:
2126
    case ADDR_DIFF_VEC:
2127
      return;
2128
 
2129
    default:
2130
      break;
2131
    }
2132
 
2133
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2134
    {
2135
      if (fmt[i] == 'e')
2136
        {
2137
          /* If we are about to do the last recursive call
2138
             needed at this level, change it into iteration.
2139
             This function is called enough to be worth it.  */
2140
          if (i == 0)
2141
            {
2142
              x = XEXP (x, i);
2143
              goto repeat;
2144
            }
2145
 
2146
          compute_transp (XEXP (x, i), indx, bmap, set_p);
2147
        }
2148
      else if (fmt[i] == 'E')
2149
        for (j = 0; j < XVECLEN (x, i); j++)
2150
          compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
2151
    }
2152
}
2153
 
2154
/* Top level routine to do the dataflow analysis needed by copy/const
2155
   propagation.  */
2156
 
2157
static void
2158
compute_cprop_data (void)
2159
{
2160
  compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, &set_hash_table);
2161
  compute_available (cprop_pavloc, cprop_absaltered,
2162
                     cprop_avout, cprop_avin);
2163
}
2164
 
2165
/* Copy/constant propagation.  */
2166
 
2167
/* Maximum number of register uses in an insn that we handle.  */
2168
#define MAX_USES 8
2169
 
2170
/* Table of uses found in an insn.
2171
   Allocated statically to avoid alloc/free complexity and overhead.  */
2172
static struct reg_use reg_use_table[MAX_USES];
2173
 
2174
/* Index into `reg_use_table' while building it.  */
2175
static int reg_use_count;
2176
 
2177
/* Set up a list of register numbers used in INSN.  The found uses are stored
2178
   in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
2179
   and contains the number of uses in the table upon exit.
2180
 
2181
   ??? If a register appears multiple times we will record it multiple times.
2182
   This doesn't hurt anything but it will slow things down.  */
2183
 
2184
static void
2185
find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
2186
{
2187
  int i, j;
2188
  enum rtx_code code;
2189
  const char *fmt;
2190
  rtx x = *xptr;
2191
 
2192
  /* repeat is used to turn tail-recursion into iteration since GCC
2193
     can't do it when there's no return value.  */
2194
 repeat:
2195
  if (x == 0)
2196
    return;
2197
 
2198
  code = GET_CODE (x);
2199
  if (REG_P (x))
2200
    {
2201
      if (reg_use_count == MAX_USES)
2202
        return;
2203
 
2204
      reg_use_table[reg_use_count].reg_rtx = x;
2205
      reg_use_count++;
2206
    }
2207
 
2208
  /* Recursively scan the operands of this expression.  */
2209
 
2210
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
2211
    {
2212
      if (fmt[i] == 'e')
2213
        {
2214
          /* If we are about to do the last recursive call
2215
             needed at this level, change it into iteration.
2216
             This function is called enough to be worth it.  */
2217
          if (i == 0)
2218
            {
2219
              x = XEXP (x, 0);
2220
              goto repeat;
2221
            }
2222
 
2223
          find_used_regs (&XEXP (x, i), data);
2224
        }
2225
      else if (fmt[i] == 'E')
2226
        for (j = 0; j < XVECLEN (x, i); j++)
2227
          find_used_regs (&XVECEXP (x, i, j), data);
2228
    }
2229
}
2230
 
2231
/* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
2232
   Returns nonzero is successful.  */
2233
 
2234
static int
2235
try_replace_reg (rtx from, rtx to, rtx insn)
2236
{
2237
  rtx note = find_reg_equal_equiv_note (insn);
2238
  rtx src = 0;
2239
  int success = 0;
2240
  rtx set = single_set (insn);
2241
 
2242
  /* Usually we substitute easy stuff, so we won't copy everything.
2243
     We however need to take care to not duplicate non-trivial CONST
2244
     expressions.  */
2245
  to = copy_rtx (to);
2246
 
2247
  validate_replace_src_group (from, to, insn);
2248
  if (num_changes_pending () && apply_change_group ())
2249
    success = 1;
2250
 
2251
  /* Try to simplify SET_SRC if we have substituted a constant.  */
2252
  if (success && set && CONSTANT_P (to))
2253
    {
2254
      src = simplify_rtx (SET_SRC (set));
2255
 
2256
      if (src)
2257
        validate_change (insn, &SET_SRC (set), src, 0);
2258
    }
2259
 
2260
  /* If there is already a REG_EQUAL note, update the expression in it
2261
     with our replacement.  */
2262
  if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
2263
    set_unique_reg_note (insn, REG_EQUAL,
2264
                         simplify_replace_rtx (XEXP (note, 0), from, to));
2265
  if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
2266
    {
2267
      /* If above failed and this is a single set, try to simplify the source of
2268
         the set given our substitution.  We could perhaps try this for multiple
2269
         SETs, but it probably won't buy us anything.  */
2270
      src = simplify_replace_rtx (SET_SRC (set), from, to);
2271
 
2272
      if (!rtx_equal_p (src, SET_SRC (set))
2273
          && validate_change (insn, &SET_SRC (set), src, 0))
2274
        success = 1;
2275
 
2276
      /* If we've failed to do replacement, have a single SET, don't already
2277
         have a note, and have no special SET, add a REG_EQUAL note to not
2278
         lose information.  */
2279
      if (!success && note == 0 && set != 0
2280
          && GET_CODE (SET_DEST (set)) != ZERO_EXTRACT
2281
          && GET_CODE (SET_DEST (set)) != STRICT_LOW_PART)
2282
        note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
2283
    }
2284
 
2285
  /* REG_EQUAL may get simplified into register.
2286
     We don't allow that. Remove that note. This code ought
2287
     not to happen, because previous code ought to synthesize
2288
     reg-reg move, but be on the safe side.  */
2289
  if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
2290
    remove_note (insn, note);
2291
 
2292
  return success;
2293
}
2294
 
2295
/* Find a set of REGNOs that are available on entry to INSN's block.  Returns
2296
   NULL no such set is found.  */
2297
 
2298
static struct expr *
2299
find_avail_set (int regno, rtx insn)
2300
{
2301
  /* SET1 contains the last set found that can be returned to the caller for
2302
     use in a substitution.  */
2303
  struct expr *set1 = 0;
2304
 
2305
  /* Loops are not possible here.  To get a loop we would need two sets
2306
     available at the start of the block containing INSN.  i.e. we would
2307
     need two sets like this available at the start of the block:
2308
 
2309
       (set (reg X) (reg Y))
2310
       (set (reg Y) (reg X))
2311
 
2312
     This can not happen since the set of (reg Y) would have killed the
2313
     set of (reg X) making it unavailable at the start of this block.  */
2314
  while (1)
2315
    {
2316
      rtx src;
2317
      struct expr *set = lookup_set (regno, &set_hash_table);
2318
 
2319
      /* Find a set that is available at the start of the block
2320
         which contains INSN.  */
2321
      while (set)
2322
        {
2323
          if (TEST_BIT (cprop_avin[BLOCK_FOR_INSN (insn)->index],
2324
                        set->bitmap_index))
2325
            break;
2326
          set = next_set (regno, set);
2327
        }
2328
 
2329
      /* If no available set was found we've reached the end of the
2330
         (possibly empty) copy chain.  */
2331
      if (set == 0)
2332
        break;
2333
 
2334
      gcc_assert (GET_CODE (set->expr) == SET);
2335
 
2336
      src = SET_SRC (set->expr);
2337
 
2338
      /* We know the set is available.
2339
         Now check that SRC is ANTLOC (i.e. none of the source operands
2340
         have changed since the start of the block).
2341
 
2342
         If the source operand changed, we may still use it for the next
2343
         iteration of this loop, but we may not use it for substitutions.  */
2344
 
2345
      if (gcse_constant_p (src) || oprs_not_set_p (src, insn))
2346
        set1 = set;
2347
 
2348
      /* If the source of the set is anything except a register, then
2349
         we have reached the end of the copy chain.  */
2350
      if (! REG_P (src))
2351
        break;
2352
 
2353
      /* Follow the copy chain, i.e. start another iteration of the loop
2354
         and see if we have an available copy into SRC.  */
2355
      regno = REGNO (src);
2356
    }
2357
 
2358
  /* SET1 holds the last set that was available and anticipatable at
2359
     INSN.  */
2360
  return set1;
2361
}
2362
 
2363
/* Subroutine of cprop_insn that tries to propagate constants into
2364
   JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
2365
   it is the instruction that immediately precedes JUMP, and must be a
2366
   single SET of a register.  FROM is what we will try to replace,
2367
   SRC is the constant we will try to substitute for it.  Returns nonzero
2368
   if a change was made.  */
2369
 
2370
static int
2371
cprop_jump (basic_block bb, rtx setcc, rtx jump, rtx from, rtx src)
2372
{
2373
  rtx new_rtx, set_src, note_src;
2374
  rtx set = pc_set (jump);
2375
  rtx note = find_reg_equal_equiv_note (jump);
2376
 
2377
  if (note)
2378
    {
2379
      note_src = XEXP (note, 0);
2380
      if (GET_CODE (note_src) == EXPR_LIST)
2381
        note_src = NULL_RTX;
2382
    }
2383
  else note_src = NULL_RTX;
2384
 
2385
  /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
2386
  set_src = note_src ? note_src : SET_SRC (set);
2387
 
2388
  /* First substitute the SETCC condition into the JUMP instruction,
2389
     then substitute that given values into this expanded JUMP.  */
2390
  if (setcc != NULL_RTX
2391
      && !modified_between_p (from, setcc, jump)
2392
      && !modified_between_p (src, setcc, jump))
2393
    {
2394
      rtx setcc_src;
2395
      rtx setcc_set = single_set (setcc);
2396
      rtx setcc_note = find_reg_equal_equiv_note (setcc);
2397
      setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
2398
                ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
2399
      set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
2400
                                      setcc_src);
2401
    }
2402
  else
2403
    setcc = NULL_RTX;
2404
 
2405
  new_rtx = simplify_replace_rtx (set_src, from, src);
2406
 
2407
  /* If no simplification can be made, then try the next register.  */
2408
  if (rtx_equal_p (new_rtx, SET_SRC (set)))
2409
    return 0;
2410
 
2411
  /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
2412
  if (new_rtx == pc_rtx)
2413
    delete_insn (jump);
2414
  else
2415
    {
2416
      /* Ensure the value computed inside the jump insn to be equivalent
2417
         to one computed by setcc.  */
2418
      if (setcc && modified_in_p (new_rtx, setcc))
2419
        return 0;
2420
      if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
2421
        {
2422
          /* When (some) constants are not valid in a comparison, and there
2423
             are two registers to be replaced by constants before the entire
2424
             comparison can be folded into a constant, we need to keep
2425
             intermediate information in REG_EQUAL notes.  For targets with
2426
             separate compare insns, such notes are added by try_replace_reg.
2427
             When we have a combined compare-and-branch instruction, however,
2428
             we need to attach a note to the branch itself to make this
2429
             optimization work.  */
2430
 
2431
          if (!rtx_equal_p (new_rtx, note_src))
2432
            set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
2433
          return 0;
2434
        }
2435
 
2436
      /* Remove REG_EQUAL note after simplification.  */
2437
      if (note_src)
2438
        remove_note (jump, note);
2439
     }
2440
 
2441
#ifdef HAVE_cc0
2442
  /* Delete the cc0 setter.  */
2443
  if (setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
2444
    delete_insn (setcc);
2445
#endif
2446
 
2447
  global_const_prop_count++;
2448
  if (dump_file != NULL)
2449
    {
2450
      fprintf (dump_file,
2451
               "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with constant ",
2452
               REGNO (from), INSN_UID (jump));
2453
      print_rtl (dump_file, src);
2454
      fprintf (dump_file, "\n");
2455
    }
2456
  purge_dead_edges (bb);
2457
 
2458
  /* If a conditional jump has been changed into unconditional jump, remove
2459
     the jump and make the edge fallthru - this is always called in
2460
     cfglayout mode.  */
2461
  if (new_rtx != pc_rtx && simplejump_p (jump))
2462
    {
2463
      edge e;
2464
      edge_iterator ei;
2465
 
2466
      for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei)); ei_next (&ei))
2467
        if (e->dest != EXIT_BLOCK_PTR
2468
            && BB_HEAD (e->dest) == JUMP_LABEL (jump))
2469
          {
2470
            e->flags |= EDGE_FALLTHRU;
2471
            break;
2472
          }
2473
      delete_insn (jump);
2474
    }
2475
 
2476
  return 1;
2477
}
2478
 
2479
static bool
2480
constprop_register (rtx insn, rtx from, rtx to)
2481
{
2482
  rtx sset;
2483
 
2484
  /* Check for reg or cc0 setting instructions followed by
2485
     conditional branch instructions first.  */
2486
  if ((sset = single_set (insn)) != NULL
2487
      && NEXT_INSN (insn)
2488
      && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
2489
    {
2490
      rtx dest = SET_DEST (sset);
2491
      if ((REG_P (dest) || CC0_P (dest))
2492
          && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn), from, to))
2493
        return 1;
2494
    }
2495
 
2496
  /* Handle normal insns next.  */
2497
  if (NONJUMP_INSN_P (insn)
2498
      && try_replace_reg (from, to, insn))
2499
    return 1;
2500
 
2501
  /* Try to propagate a CONST_INT into a conditional jump.
2502
     We're pretty specific about what we will handle in this
2503
     code, we can extend this as necessary over time.
2504
 
2505
     Right now the insn in question must look like
2506
     (set (pc) (if_then_else ...))  */
2507
  else if (any_condjump_p (insn) && onlyjump_p (insn))
2508
    return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, to);
2509
  return 0;
2510
}
2511
 
2512
/* Perform constant and copy propagation on INSN.
2513
   The result is nonzero if a change was made.  */
2514
 
2515
static int
2516
cprop_insn (rtx insn)
2517
{
2518
  struct reg_use *reg_used;
2519
  int changed = 0;
2520
  rtx note;
2521
 
2522
  if (!INSN_P (insn))
2523
    return 0;
2524
 
2525
  reg_use_count = 0;
2526
  note_uses (&PATTERN (insn), find_used_regs, NULL);
2527
 
2528
  note = find_reg_equal_equiv_note (insn);
2529
 
2530
  /* We may win even when propagating constants into notes.  */
2531
  if (note)
2532
    find_used_regs (&XEXP (note, 0), NULL);
2533
 
2534
  for (reg_used = &reg_use_table[0]; reg_use_count > 0;
2535
       reg_used++, reg_use_count--)
2536
    {
2537
      unsigned int regno = REGNO (reg_used->reg_rtx);
2538
      rtx pat, src;
2539
      struct expr *set;
2540
 
2541
      /* If the register has already been set in this block, there's
2542
         nothing we can do.  */
2543
      if (! oprs_not_set_p (reg_used->reg_rtx, insn))
2544
        continue;
2545
 
2546
      /* Find an assignment that sets reg_used and is available
2547
         at the start of the block.  */
2548
      set = find_avail_set (regno, insn);
2549
      if (! set)
2550
        continue;
2551
 
2552
      pat = set->expr;
2553
      /* ??? We might be able to handle PARALLELs.  Later.  */
2554
      gcc_assert (GET_CODE (pat) == SET);
2555
 
2556
      src = SET_SRC (pat);
2557
 
2558
      /* Constant propagation.  */
2559
      if (gcse_constant_p (src))
2560
        {
2561
          if (constprop_register (insn, reg_used->reg_rtx, src))
2562
            {
2563
              changed = 1;
2564
              global_const_prop_count++;
2565
              if (dump_file != NULL)
2566
                {
2567
                  fprintf (dump_file, "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
2568
                  fprintf (dump_file, "insn %d with constant ", INSN_UID (insn));
2569
                  print_rtl (dump_file, src);
2570
                  fprintf (dump_file, "\n");
2571
                }
2572
              if (INSN_DELETED_P (insn))
2573
                return 1;
2574
            }
2575
        }
2576
      else if (REG_P (src)
2577
               && REGNO (src) >= FIRST_PSEUDO_REGISTER
2578
               && REGNO (src) != regno)
2579
        {
2580
          if (try_replace_reg (reg_used->reg_rtx, src, insn))
2581
            {
2582
              changed = 1;
2583
              global_copy_prop_count++;
2584
              if (dump_file != NULL)
2585
                {
2586
                  fprintf (dump_file, "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
2587
                           regno, INSN_UID (insn));
2588
                  fprintf (dump_file, " with reg %d\n", REGNO (src));
2589
                }
2590
 
2591
              /* The original insn setting reg_used may or may not now be
2592
                 deletable.  We leave the deletion to flow.  */
2593
              /* FIXME: If it turns out that the insn isn't deletable,
2594
                 then we may have unnecessarily extended register lifetimes
2595
                 and made things worse.  */
2596
            }
2597
        }
2598
    }
2599
 
2600
  if (changed && DEBUG_INSN_P (insn))
2601
    return 0;
2602
 
2603
  return changed;
2604
}
2605
 
2606
/* Like find_used_regs, but avoid recording uses that appear in
2607
   input-output contexts such as zero_extract or pre_dec.  This
2608
   restricts the cases we consider to those for which local cprop
2609
   can legitimately make replacements.  */
2610
 
2611
static void
2612
local_cprop_find_used_regs (rtx *xptr, void *data)
2613
{
2614
  rtx x = *xptr;
2615
 
2616
  if (x == 0)
2617
    return;
2618
 
2619
  switch (GET_CODE (x))
2620
    {
2621
    case ZERO_EXTRACT:
2622
    case SIGN_EXTRACT:
2623
    case STRICT_LOW_PART:
2624
      return;
2625
 
2626
    case PRE_DEC:
2627
    case PRE_INC:
2628
    case POST_DEC:
2629
    case POST_INC:
2630
    case PRE_MODIFY:
2631
    case POST_MODIFY:
2632
      /* Can only legitimately appear this early in the context of
2633
         stack pushes for function arguments, but handle all of the
2634
         codes nonetheless.  */
2635
      return;
2636
 
2637
    case SUBREG:
2638
      /* Setting a subreg of a register larger than word_mode leaves
2639
         the non-written words unchanged.  */
2640
      if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) > BITS_PER_WORD)
2641
        return;
2642
      break;
2643
 
2644
    default:
2645
      break;
2646
    }
2647
 
2648
  find_used_regs (xptr, data);
2649
}
2650
 
2651
/* Try to perform local const/copy propagation on X in INSN.  */
2652
 
2653
static bool
2654
do_local_cprop (rtx x, rtx insn)
2655
{
2656
  rtx newreg = NULL, newcnst = NULL;
2657
 
2658
  /* Rule out USE instructions and ASM statements as we don't want to
2659
     change the hard registers mentioned.  */
2660
  if (REG_P (x)
2661
      && (REGNO (x) >= FIRST_PSEUDO_REGISTER
2662
          || (GET_CODE (PATTERN (insn)) != USE
2663
              && asm_noperands (PATTERN (insn)) < 0)))
2664
    {
2665
      cselib_val *val = cselib_lookup (x, GET_MODE (x), 0);
2666
      struct elt_loc_list *l;
2667
 
2668
      if (!val)
2669
        return false;
2670
      for (l = val->locs; l; l = l->next)
2671
        {
2672
          rtx this_rtx = l->loc;
2673
          rtx note;
2674
 
2675
          if (gcse_constant_p (this_rtx))
2676
            newcnst = this_rtx;
2677
          if (REG_P (this_rtx) && REGNO (this_rtx) >= FIRST_PSEUDO_REGISTER
2678
              /* Don't copy propagate if it has attached REG_EQUIV note.
2679
                 At this point this only function parameters should have
2680
                 REG_EQUIV notes and if the argument slot is used somewhere
2681
                 explicitly, it means address of parameter has been taken,
2682
                 so we should not extend the lifetime of the pseudo.  */
2683
              && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
2684
                  || ! MEM_P (XEXP (note, 0))))
2685
            newreg = this_rtx;
2686
        }
2687
      if (newcnst && constprop_register (insn, x, newcnst))
2688
        {
2689
          if (dump_file != NULL)
2690
            {
2691
              fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
2692
                       REGNO (x));
2693
              fprintf (dump_file, "insn %d with constant ",
2694
                       INSN_UID (insn));
2695
              print_rtl (dump_file, newcnst);
2696
              fprintf (dump_file, "\n");
2697
            }
2698
          local_const_prop_count++;
2699
          return true;
2700
        }
2701
      else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
2702
        {
2703
          if (dump_file != NULL)
2704
            {
2705
              fprintf (dump_file,
2706
                       "LOCAL COPY-PROP: Replacing reg %d in insn %d",
2707
                       REGNO (x), INSN_UID (insn));
2708
              fprintf (dump_file, " with reg %d\n", REGNO (newreg));
2709
            }
2710
          local_copy_prop_count++;
2711
          return true;
2712
        }
2713
    }
2714
  return false;
2715
}
2716
 
2717
/* Do local const/copy propagation (i.e. within each basic block).  */
2718
 
2719
static int
2720
local_cprop_pass (void)
2721
{
2722
  basic_block bb;
2723
  rtx insn;
2724
  struct reg_use *reg_used;
2725
  bool changed = false;
2726
 
2727
  cselib_init (0);
2728
  FOR_EACH_BB (bb)
2729
    {
2730
      FOR_BB_INSNS (bb, insn)
2731
        {
2732
          if (INSN_P (insn))
2733
            {
2734
              rtx note = find_reg_equal_equiv_note (insn);
2735
              do
2736
                {
2737
                  reg_use_count = 0;
2738
                  note_uses (&PATTERN (insn), local_cprop_find_used_regs,
2739
                             NULL);
2740
                  if (note)
2741
                    local_cprop_find_used_regs (&XEXP (note, 0), NULL);
2742
 
2743
                  for (reg_used = &reg_use_table[0]; reg_use_count > 0;
2744
                       reg_used++, reg_use_count--)
2745
                    {
2746
                      if (do_local_cprop (reg_used->reg_rtx, insn))
2747
                        {
2748
                          changed = true;
2749
                          break;
2750
                        }
2751
                    }
2752
                  if (INSN_DELETED_P (insn))
2753
                    break;
2754
                }
2755
              while (reg_use_count);
2756
            }
2757
          cselib_process_insn (insn);
2758
        }
2759
 
2760
      /* Forget everything at the end of a basic block.  */
2761
      cselib_clear_table ();
2762
    }
2763
 
2764
  cselib_finish ();
2765
 
2766
  return changed;
2767
}
2768
 
2769
/* Similar to get_condition, only the resulting condition must be
2770
   valid at JUMP, instead of at EARLIEST.
2771
 
2772
   This differs from noce_get_condition in ifcvt.c in that we prefer not to
2773
   settle for the condition variable in the jump instruction being integral.
2774
   We prefer to be able to record the value of a user variable, rather than
2775
   the value of a temporary used in a condition.  This could be solved by
2776
   recording the value of *every* register scanned by canonicalize_condition,
2777
   but this would require some code reorganization.  */
2778
 
2779
rtx
2780
fis_get_condition (rtx jump)
2781
{
2782
  return get_condition (jump, NULL, false, true);
2783
}
2784
 
2785
/* Check the comparison COND to see if we can safely form an implicit set from
2786
   it.  COND is either an EQ or NE comparison.  */
2787
 
2788
static bool
2789
implicit_set_cond_p (const_rtx cond)
2790
{
2791
  const enum machine_mode mode = GET_MODE (XEXP (cond, 0));
2792
  const_rtx cst = XEXP (cond, 1);
2793
 
2794
  /* We can't perform this optimization if either operand might be or might
2795
     contain a signed zero.  */
2796
  if (HONOR_SIGNED_ZEROS (mode))
2797
    {
2798
      /* It is sufficient to check if CST is or contains a zero.  We must
2799
         handle float, complex, and vector.  If any subpart is a zero, then
2800
         the optimization can't be performed.  */
2801
      /* ??? The complex and vector checks are not implemented yet.  We just
2802
         always return zero for them.  */
2803
      if (GET_CODE (cst) == CONST_DOUBLE)
2804
        {
2805
          REAL_VALUE_TYPE d;
2806
          REAL_VALUE_FROM_CONST_DOUBLE (d, cst);
2807
          if (REAL_VALUES_EQUAL (d, dconst0))
2808
            return 0;
2809
        }
2810
      else
2811
        return 0;
2812
    }
2813
 
2814
  return gcse_constant_p (cst);
2815
}
2816
 
2817
/* Find the implicit sets of a function.  An "implicit set" is a constraint
2818
   on the value of a variable, implied by a conditional jump.  For example,
2819
   following "if (x == 2)", the then branch may be optimized as though the
2820
   conditional performed an "explicit set", in this example, "x = 2".  This
2821
   function records the set patterns that are implicit at the start of each
2822
   basic block.
2823
 
2824
   FIXME: This would be more effective if critical edges are pre-split.  As
2825
          it is now, we can't record implicit sets for blocks that have
2826
          critical successor edges.  This results in missed optimizations
2827
          and in more (unnecessary) work in cfgcleanup.c:thread_jump().  */
2828
 
2829
static void
2830
find_implicit_sets (void)
2831
{
2832
  basic_block bb, dest;
2833
  unsigned int count;
2834
  rtx cond, new_rtx;
2835
 
2836
  count = 0;
2837
  FOR_EACH_BB (bb)
2838
    /* Check for more than one successor.  */
2839
    if (EDGE_COUNT (bb->succs) > 1)
2840
      {
2841
        cond = fis_get_condition (BB_END (bb));
2842
 
2843
        if (cond
2844
            && (GET_CODE (cond) == EQ || GET_CODE (cond) == NE)
2845
            && REG_P (XEXP (cond, 0))
2846
            && REGNO (XEXP (cond, 0)) >= FIRST_PSEUDO_REGISTER
2847
            && implicit_set_cond_p (cond))
2848
          {
2849
            dest = GET_CODE (cond) == EQ ? BRANCH_EDGE (bb)->dest
2850
                                         : FALLTHRU_EDGE (bb)->dest;
2851
 
2852
            if (dest
2853
                /* Record nothing for a critical edge.  */
2854
                && single_pred_p (dest)
2855
                && dest != EXIT_BLOCK_PTR)
2856
              {
2857
                new_rtx = gen_rtx_SET (VOIDmode, XEXP (cond, 0),
2858
                                             XEXP (cond, 1));
2859
                implicit_sets[dest->index] = new_rtx;
2860
                if (dump_file)
2861
                  {
2862
                    fprintf(dump_file, "Implicit set of reg %d in ",
2863
                            REGNO (XEXP (cond, 0)));
2864
                    fprintf(dump_file, "basic block %d\n", dest->index);
2865
                  }
2866
                count++;
2867
              }
2868
          }
2869
      }
2870
 
2871
  if (dump_file)
2872
    fprintf (dump_file, "Found %d implicit sets\n", count);
2873
}
2874
 
2875
/* Bypass conditional jumps.  */
2876
 
2877
/* The value of last_basic_block at the beginning of the jump_bypass
2878
   pass.  The use of redirect_edge_and_branch_force may introduce new
2879
   basic blocks, but the data flow analysis is only valid for basic
2880
   block indices less than bypass_last_basic_block.  */
2881
 
2882
static int bypass_last_basic_block;
2883
 
2884
/* Find a set of REGNO to a constant that is available at the end of basic
2885
   block BB.  Returns NULL if no such set is found.  Based heavily upon
2886
   find_avail_set.  */
2887
 
2888
static struct expr *
2889
find_bypass_set (int regno, int bb)
2890
{
2891
  struct expr *result = 0;
2892
 
2893
  for (;;)
2894
    {
2895
      rtx src;
2896
      struct expr *set = lookup_set (regno, &set_hash_table);
2897
 
2898
      while (set)
2899
        {
2900
          if (TEST_BIT (cprop_avout[bb], set->bitmap_index))
2901
            break;
2902
          set = next_set (regno, set);
2903
        }
2904
 
2905
      if (set == 0)
2906
        break;
2907
 
2908
      gcc_assert (GET_CODE (set->expr) == SET);
2909
 
2910
      src = SET_SRC (set->expr);
2911
      if (gcse_constant_p (src))
2912
        result = set;
2913
 
2914
      if (! REG_P (src))
2915
        break;
2916
 
2917
      regno = REGNO (src);
2918
    }
2919
  return result;
2920
}
2921
 
2922
 
2923
/* Subroutine of bypass_block that checks whether a pseudo is killed by
2924
   any of the instructions inserted on an edge.  Jump bypassing places
2925
   condition code setters on CFG edges using insert_insn_on_edge.  This
2926
   function is required to check that our data flow analysis is still
2927
   valid prior to commit_edge_insertions.  */
2928
 
2929
static bool
2930
reg_killed_on_edge (const_rtx reg, const_edge e)
2931
{
2932
  rtx insn;
2933
 
2934
  for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
2935
    if (INSN_P (insn) && reg_set_p (reg, insn))
2936
      return true;
2937
 
2938
  return false;
2939
}
2940
 
2941
/* Subroutine of bypass_conditional_jumps that attempts to bypass the given
2942
   basic block BB which has more than one predecessor.  If not NULL, SETCC
2943
   is the first instruction of BB, which is immediately followed by JUMP_INSN
2944
   JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
2945
   Returns nonzero if a change was made.
2946
 
2947
   During the jump bypassing pass, we may place copies of SETCC instructions
2948
   on CFG edges.  The following routine must be careful to pay attention to
2949
   these inserted insns when performing its transformations.  */
2950
 
2951
static int
2952
bypass_block (basic_block bb, rtx setcc, rtx jump)
2953
{
2954
  rtx insn, note;
2955
  edge e, edest;
2956
  int i, change;
2957
  int may_be_loop_header;
2958
  unsigned removed_p;
2959
  edge_iterator ei;
2960
 
2961
  insn = (setcc != NULL) ? setcc : jump;
2962
 
2963
  /* Determine set of register uses in INSN.  */
2964
  reg_use_count = 0;
2965
  note_uses (&PATTERN (insn), find_used_regs, NULL);
2966
  note = find_reg_equal_equiv_note (insn);
2967
  if (note)
2968
    find_used_regs (&XEXP (note, 0), NULL);
2969
 
2970
  may_be_loop_header = false;
2971
  FOR_EACH_EDGE (e, ei, bb->preds)
2972
    if (e->flags & EDGE_DFS_BACK)
2973
      {
2974
        may_be_loop_header = true;
2975
        break;
2976
      }
2977
 
2978
  change = 0;
2979
  for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
2980
    {
2981
      removed_p = 0;
2982
 
2983
      if (e->flags & EDGE_COMPLEX)
2984
        {
2985
          ei_next (&ei);
2986
          continue;
2987
        }
2988
 
2989
      /* We can't redirect edges from new basic blocks.  */
2990
      if (e->src->index >= bypass_last_basic_block)
2991
        {
2992
          ei_next (&ei);
2993
          continue;
2994
        }
2995
 
2996
      /* The irreducible loops created by redirecting of edges entering the
2997
         loop from outside would decrease effectiveness of some of the following
2998
         optimizations, so prevent this.  */
2999
      if (may_be_loop_header
3000
          && !(e->flags & EDGE_DFS_BACK))
3001
        {
3002
          ei_next (&ei);
3003
          continue;
3004
        }
3005
 
3006
      for (i = 0; i < reg_use_count; i++)
3007
        {
3008
          struct reg_use *reg_used = &reg_use_table[i];
3009
          unsigned int regno = REGNO (reg_used->reg_rtx);
3010
          basic_block dest, old_dest;
3011
          struct expr *set;
3012
          rtx src, new_rtx;
3013
 
3014
          set = find_bypass_set (regno, e->src->index);
3015
 
3016
          if (! set)
3017
            continue;
3018
 
3019
          /* Check the data flow is valid after edge insertions.  */
3020
          if (e->insns.r && reg_killed_on_edge (reg_used->reg_rtx, e))
3021
            continue;
3022
 
3023
          src = SET_SRC (pc_set (jump));
3024
 
3025
          if (setcc != NULL)
3026
            src = simplify_replace_rtx (src,
3027
                                        SET_DEST (PATTERN (setcc)),
3028
                                        SET_SRC (PATTERN (setcc)));
3029
 
3030
          new_rtx = simplify_replace_rtx (src, reg_used->reg_rtx,
3031
                                          SET_SRC (set->expr));
3032
 
3033
          /* Jump bypassing may have already placed instructions on
3034
             edges of the CFG.  We can't bypass an outgoing edge that
3035
             has instructions associated with it, as these insns won't
3036
             get executed if the incoming edge is redirected.  */
3037
 
3038
          if (new_rtx == pc_rtx)
3039
            {
3040
              edest = FALLTHRU_EDGE (bb);
3041
              dest = edest->insns.r ? NULL : edest->dest;
3042
            }
3043
          else if (GET_CODE (new_rtx) == LABEL_REF)
3044
            {
3045
              dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
3046
              /* Don't bypass edges containing instructions.  */
3047
              edest = find_edge (bb, dest);
3048
              if (edest && edest->insns.r)
3049
                dest = NULL;
3050
            }
3051
          else
3052
            dest = NULL;
3053
 
3054
          /* Avoid unification of the edge with other edges from original
3055
             branch.  We would end up emitting the instruction on "both"
3056
             edges.  */
3057
 
3058
          if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
3059
              && find_edge (e->src, dest))
3060
            dest = NULL;
3061
 
3062
          old_dest = e->dest;
3063
          if (dest != NULL
3064
              && dest != old_dest
3065
              && dest != EXIT_BLOCK_PTR)
3066
            {
3067
              redirect_edge_and_branch_force (e, dest);
3068
 
3069
              /* Copy the register setter to the redirected edge.
3070
                 Don't copy CC0 setters, as CC0 is dead after jump.  */
3071
              if (setcc)
3072
                {
3073
                  rtx pat = PATTERN (setcc);
3074
                  if (!CC0_P (SET_DEST (pat)))
3075
                    insert_insn_on_edge (copy_insn (pat), e);
3076
                }
3077
 
3078
              if (dump_file != NULL)
3079
                {
3080
                  fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
3081
                                      "in jump_insn %d equals constant ",
3082
                           regno, INSN_UID (jump));
3083
                  print_rtl (dump_file, SET_SRC (set->expr));
3084
                  fprintf (dump_file, "\nBypass edge from %d->%d to %d\n",
3085
                           e->src->index, old_dest->index, dest->index);
3086
                }
3087
              change = 1;
3088
              removed_p = 1;
3089
              break;
3090
            }
3091
        }
3092
      if (!removed_p)
3093
        ei_next (&ei);
3094
    }
3095
  return change;
3096
}
3097
 
3098
/* Find basic blocks with more than one predecessor that only contain a
3099
   single conditional jump.  If the result of the comparison is known at
3100
   compile-time from any incoming edge, redirect that edge to the
3101
   appropriate target.  Returns nonzero if a change was made.
3102
 
3103
   This function is now mis-named, because we also handle indirect jumps.  */
3104
 
3105
static int
3106
bypass_conditional_jumps (void)
3107
{
3108
  basic_block bb;
3109
  int changed;
3110
  rtx setcc;
3111
  rtx insn;
3112
  rtx dest;
3113
 
3114
  /* Note we start at block 1.  */
3115
  if (ENTRY_BLOCK_PTR->next_bb == EXIT_BLOCK_PTR)
3116
    return 0;
3117
 
3118
  bypass_last_basic_block = last_basic_block;
3119
  mark_dfs_back_edges ();
3120
 
3121
  changed = 0;
3122
  FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb,
3123
                  EXIT_BLOCK_PTR, next_bb)
3124
    {
3125
      /* Check for more than one predecessor.  */
3126
      if (!single_pred_p (bb))
3127
        {
3128
          setcc = NULL_RTX;
3129
          FOR_BB_INSNS (bb, insn)
3130
            if (DEBUG_INSN_P (insn))
3131
              continue;
3132
            else if (NONJUMP_INSN_P (insn))
3133
              {
3134
                if (setcc)
3135
                  break;
3136
                if (GET_CODE (PATTERN (insn)) != SET)
3137
                  break;
3138
 
3139
                dest = SET_DEST (PATTERN (insn));
3140
                if (REG_P (dest) || CC0_P (dest))
3141
                  setcc = insn;
3142
                else
3143
                  break;
3144
              }
3145
            else if (JUMP_P (insn))
3146
              {
3147
                if ((any_condjump_p (insn) || computed_jump_p (insn))
3148
                    && onlyjump_p (insn))
3149
                  changed |= bypass_block (bb, setcc, insn);
3150
                break;
3151
              }
3152
            else if (INSN_P (insn))
3153
              break;
3154
        }
3155
    }
3156
 
3157
  /* If we bypassed any register setting insns, we inserted a
3158
     copy on the redirected edge.  These need to be committed.  */
3159
  if (changed)
3160
    commit_edge_insertions ();
3161
 
3162
  return changed;
3163
}
3164
 
3165
/* Compute PRE+LCM working variables.  */
3166
 
3167
/* Local properties of expressions.  */
3168
/* Nonzero for expressions that are transparent in the block.  */
3169
static sbitmap *transp;
3170
 
3171
/* Nonzero for expressions that are transparent at the end of the block.
3172
   This is only zero for expressions killed by abnormal critical edge
3173
   created by a calls.  */
3174
static sbitmap *transpout;
3175
 
3176
/* Nonzero for expressions that are computed (available) in the block.  */
3177
static sbitmap *comp;
3178
 
3179
/* Nonzero for expressions that are locally anticipatable in the block.  */
3180
static sbitmap *antloc;
3181
 
3182
/* Nonzero for expressions where this block is an optimal computation
3183
   point.  */
3184
static sbitmap *pre_optimal;
3185
 
3186
/* Nonzero for expressions which are redundant in a particular block.  */
3187
static sbitmap *pre_redundant;
3188
 
3189
/* Nonzero for expressions which should be inserted on a specific edge.  */
3190
static sbitmap *pre_insert_map;
3191
 
3192
/* Nonzero for expressions which should be deleted in a specific block.  */
3193
static sbitmap *pre_delete_map;
3194
 
3195
/* Contains the edge_list returned by pre_edge_lcm.  */
3196
static struct edge_list *edge_list;
3197
 
3198
/* Allocate vars used for PRE analysis.  */
3199
 
3200
static void
3201
alloc_pre_mem (int n_blocks, int n_exprs)
3202
{
3203
  transp = sbitmap_vector_alloc (n_blocks, n_exprs);
3204
  comp = sbitmap_vector_alloc (n_blocks, n_exprs);
3205
  antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
3206
 
3207
  pre_optimal = NULL;
3208
  pre_redundant = NULL;
3209
  pre_insert_map = NULL;
3210
  pre_delete_map = NULL;
3211
  ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
3212
 
3213
  /* pre_insert and pre_delete are allocated later.  */
3214
}
3215
 
3216
/* Free vars used for PRE analysis.  */
3217
 
3218
static void
3219
free_pre_mem (void)
3220
{
3221
  sbitmap_vector_free (transp);
3222
  sbitmap_vector_free (comp);
3223
 
3224
  /* ANTLOC and AE_KILL are freed just after pre_lcm finishes.  */
3225
 
3226
  if (pre_optimal)
3227
    sbitmap_vector_free (pre_optimal);
3228
  if (pre_redundant)
3229
    sbitmap_vector_free (pre_redundant);
3230
  if (pre_insert_map)
3231
    sbitmap_vector_free (pre_insert_map);
3232
  if (pre_delete_map)
3233
    sbitmap_vector_free (pre_delete_map);
3234
 
3235
  transp = comp = NULL;
3236
  pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
3237
}
3238
 
3239
/* Top level routine to do the dataflow analysis needed by PRE.  */
3240
 
3241
static void
3242
compute_pre_data (void)
3243
{
3244
  sbitmap trapping_expr;
3245
  basic_block bb;
3246
  unsigned int ui;
3247
 
3248
  compute_local_properties (transp, comp, antloc, &expr_hash_table);
3249
  sbitmap_vector_zero (ae_kill, last_basic_block);
3250
 
3251
  /* Collect expressions which might trap.  */
3252
  trapping_expr = sbitmap_alloc (expr_hash_table.n_elems);
3253
  sbitmap_zero (trapping_expr);
3254
  for (ui = 0; ui < expr_hash_table.size; ui++)
3255
    {
3256
      struct expr *e;
3257
      for (e = expr_hash_table.table[ui]; e != NULL; e = e->next_same_hash)
3258
        if (may_trap_p (e->expr))
3259
          SET_BIT (trapping_expr, e->bitmap_index);
3260
    }
3261
 
3262
  /* Compute ae_kill for each basic block using:
3263
 
3264
     ~(TRANSP | COMP)
3265
  */
3266
 
3267
  FOR_EACH_BB (bb)
3268
    {
3269
      edge e;
3270
      edge_iterator ei;
3271
 
3272
      /* If the current block is the destination of an abnormal edge, we
3273
         kill all trapping expressions because we won't be able to properly
3274
         place the instruction on the edge.  So make them neither
3275
         anticipatable nor transparent.  This is fairly conservative.  */
3276
      FOR_EACH_EDGE (e, ei, bb->preds)
3277
        if (e->flags & EDGE_ABNORMAL)
3278
          {
3279
            sbitmap_difference (antloc[bb->index], antloc[bb->index], trapping_expr);
3280
            sbitmap_difference (transp[bb->index], transp[bb->index], trapping_expr);
3281
            break;
3282
          }
3283
 
3284
      sbitmap_a_or_b (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
3285
      sbitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
3286
    }
3287
 
3288
  edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc,
3289
                            ae_kill, &pre_insert_map, &pre_delete_map);
3290
  sbitmap_vector_free (antloc);
3291
  antloc = NULL;
3292
  sbitmap_vector_free (ae_kill);
3293
  ae_kill = NULL;
3294
  sbitmap_free (trapping_expr);
3295
}
3296
 
3297
/* PRE utilities */
3298
 
3299
/* Return nonzero if an occurrence of expression EXPR in OCCR_BB would reach
3300
   block BB.
3301
 
3302
   VISITED is a pointer to a working buffer for tracking which BB's have
3303
   been visited.  It is NULL for the top-level call.
3304
 
3305
   We treat reaching expressions that go through blocks containing the same
3306
   reaching expression as "not reaching".  E.g. if EXPR is generated in blocks
3307
   2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
3308
   2 as not reaching.  The intent is to improve the probability of finding
3309
   only one reaching expression and to reduce register lifetimes by picking
3310
   the closest such expression.  */
3311
 
3312
static int
3313
pre_expr_reaches_here_p_work (basic_block occr_bb, struct expr *expr, basic_block bb, char *visited)
3314
{
3315
  edge pred;
3316
  edge_iterator ei;
3317
 
3318
  FOR_EACH_EDGE (pred, ei, bb->preds)
3319
    {
3320
      basic_block pred_bb = pred->src;
3321
 
3322
      if (pred->src == ENTRY_BLOCK_PTR
3323
          /* Has predecessor has already been visited?  */
3324
          || visited[pred_bb->index])
3325
        ;/* Nothing to do.  */
3326
 
3327
      /* Does this predecessor generate this expression?  */
3328
      else if (TEST_BIT (comp[pred_bb->index], expr->bitmap_index))
3329
        {
3330
          /* Is this the occurrence we're looking for?
3331
             Note that there's only one generating occurrence per block
3332
             so we just need to check the block number.  */
3333
          if (occr_bb == pred_bb)
3334
            return 1;
3335
 
3336
          visited[pred_bb->index] = 1;
3337
        }
3338
      /* Ignore this predecessor if it kills the expression.  */
3339
      else if (! TEST_BIT (transp[pred_bb->index], expr->bitmap_index))
3340
        visited[pred_bb->index] = 1;
3341
 
3342
      /* Neither gen nor kill.  */
3343
      else
3344
        {
3345
          visited[pred_bb->index] = 1;
3346
          if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
3347
            return 1;
3348
        }
3349
    }
3350
 
3351
  /* All paths have been checked.  */
3352
  return 0;
3353
}
3354
 
3355
/* The wrapper for pre_expr_reaches_here_work that ensures that any
3356
   memory allocated for that function is returned.  */
3357
 
3358
static int
3359
pre_expr_reaches_here_p (basic_block occr_bb, struct expr *expr, basic_block bb)
3360
{
3361
  int rval;
3362
  char *visited = XCNEWVEC (char, last_basic_block);
3363
 
3364
  rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
3365
 
3366
  free (visited);
3367
  return rval;
3368
}
3369
 
3370
 
3371
/* Given an expr, generate RTL which we can insert at the end of a BB,
3372
   or on an edge.  Set the block number of any insns generated to
3373
   the value of BB.  */
3374
 
3375
static rtx
3376
process_insert_insn (struct expr *expr)
3377
{
3378
  rtx reg = expr->reaching_reg;
3379
  rtx exp = copy_rtx (expr->expr);
3380
  rtx pat;
3381
 
3382
  start_sequence ();
3383
 
3384
  /* If the expression is something that's an operand, like a constant,
3385
     just copy it to a register.  */
3386
  if (general_operand (exp, GET_MODE (reg)))
3387
    emit_move_insn (reg, exp);
3388
 
3389
  /* Otherwise, make a new insn to compute this expression and make sure the
3390
     insn will be recognized (this also adds any needed CLOBBERs).  Copy the
3391
     expression to make sure we don't have any sharing issues.  */
3392
  else
3393
    {
3394
      rtx insn = emit_insn (gen_rtx_SET (VOIDmode, reg, exp));
3395
 
3396
      if (insn_invalid_p (insn))
3397
        gcc_unreachable ();
3398
    }
3399
 
3400
 
3401
  pat = get_insns ();
3402
  end_sequence ();
3403
 
3404
  return pat;
3405
}
3406
 
3407
/* Add EXPR to the end of basic block BB.
3408
 
3409
   This is used by both the PRE and code hoisting.
3410
 
3411
   For PRE, we want to verify that the expr is either transparent
3412
   or locally anticipatable in the target block.  This check makes
3413
   no sense for code hoisting.  */
3414
 
3415
static void
3416
insert_insn_end_basic_block (struct expr *expr, basic_block bb, int pre)
3417
{
3418
  rtx insn = BB_END (bb);
3419
  rtx new_insn;
3420
  rtx reg = expr->reaching_reg;
3421
  int regno = REGNO (reg);
3422
  rtx pat, pat_end;
3423
 
3424
  pat = process_insert_insn (expr);
3425
  gcc_assert (pat && INSN_P (pat));
3426
 
3427
  pat_end = pat;
3428
  while (NEXT_INSN (pat_end) != NULL_RTX)
3429
    pat_end = NEXT_INSN (pat_end);
3430
 
3431
  /* If the last insn is a jump, insert EXPR in front [taking care to
3432
     handle cc0, etc. properly].  Similarly we need to care trapping
3433
     instructions in presence of non-call exceptions.  */
3434
 
3435
  if (JUMP_P (insn)
3436
      || (NONJUMP_INSN_P (insn)
3437
          && (!single_succ_p (bb)
3438
              || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
3439
    {
3440
#ifdef HAVE_cc0
3441
      rtx note;
3442
#endif
3443
      /* It should always be the case that we can put these instructions
3444
         anywhere in the basic block with performing PRE optimizations.
3445
         Check this.  */
3446
      gcc_assert (!NONJUMP_INSN_P (insn) || !pre
3447
                  || TEST_BIT (antloc[bb->index], expr->bitmap_index)
3448
                  || TEST_BIT (transp[bb->index], expr->bitmap_index));
3449
 
3450
      /* If this is a jump table, then we can't insert stuff here.  Since
3451
         we know the previous real insn must be the tablejump, we insert
3452
         the new instruction just before the tablejump.  */
3453
      if (GET_CODE (PATTERN (insn)) == ADDR_VEC
3454
          || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
3455
        insn = prev_real_insn (insn);
3456
 
3457
#ifdef HAVE_cc0
3458
      /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
3459
         if cc0 isn't set.  */
3460
      note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
3461
      if (note)
3462
        insn = XEXP (note, 0);
3463
      else
3464
        {
3465
          rtx maybe_cc0_setter = prev_nonnote_insn (insn);
3466
          if (maybe_cc0_setter
3467
              && INSN_P (maybe_cc0_setter)
3468
              && sets_cc0_p (PATTERN (maybe_cc0_setter)))
3469
            insn = maybe_cc0_setter;
3470
        }
3471
#endif
3472
      /* FIXME: What if something in cc0/jump uses value set in new insn?  */
3473
      new_insn = emit_insn_before_noloc (pat, insn, bb);
3474
    }
3475
 
3476
  /* Likewise if the last insn is a call, as will happen in the presence
3477
     of exception handling.  */
3478
  else if (CALL_P (insn)
3479
           && (!single_succ_p (bb)
3480
               || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
3481
    {
3482
      /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
3483
         we search backward and place the instructions before the first
3484
         parameter is loaded.  Do this for everyone for consistency and a
3485
         presumption that we'll get better code elsewhere as well.
3486
 
3487
         It should always be the case that we can put these instructions
3488
         anywhere in the basic block with performing PRE optimizations.
3489
         Check this.  */
3490
 
3491
      gcc_assert (!pre
3492
                  || TEST_BIT (antloc[bb->index], expr->bitmap_index)
3493
                  || TEST_BIT (transp[bb->index], expr->bitmap_index));
3494
 
3495
      /* Since different machines initialize their parameter registers
3496
         in different orders, assume nothing.  Collect the set of all
3497
         parameter registers.  */
3498
      insn = find_first_parameter_load (insn, BB_HEAD (bb));
3499
 
3500
      /* If we found all the parameter loads, then we want to insert
3501
         before the first parameter load.
3502
 
3503
         If we did not find all the parameter loads, then we might have
3504
         stopped on the head of the block, which could be a CODE_LABEL.
3505
         If we inserted before the CODE_LABEL, then we would be putting
3506
         the insn in the wrong basic block.  In that case, put the insn
3507
         after the CODE_LABEL.  Also, respect NOTE_INSN_BASIC_BLOCK.  */
3508
      while (LABEL_P (insn)
3509
             || NOTE_INSN_BASIC_BLOCK_P (insn))
3510
        insn = NEXT_INSN (insn);
3511
 
3512
      new_insn = emit_insn_before_noloc (pat, insn, bb);
3513
    }
3514
  else
3515
    new_insn = emit_insn_after_noloc (pat, insn, bb);
3516
 
3517
  while (1)
3518
    {
3519
      if (INSN_P (pat))
3520
        add_label_notes (PATTERN (pat), new_insn);
3521
      if (pat == pat_end)
3522
        break;
3523
      pat = NEXT_INSN (pat);
3524
    }
3525
 
3526
  gcse_create_count++;
3527
 
3528
  if (dump_file)
3529
    {
3530
      fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ",
3531
               bb->index, INSN_UID (new_insn));
3532
      fprintf (dump_file, "copying expression %d to reg %d\n",
3533
               expr->bitmap_index, regno);
3534
    }
3535
}
3536
 
3537
/* Insert partially redundant expressions on edges in the CFG to make
3538
   the expressions fully redundant.  */
3539
 
3540
static int
3541
pre_edge_insert (struct edge_list *edge_list, struct expr **index_map)
3542
{
3543
  int e, i, j, num_edges, set_size, did_insert = 0;
3544
  sbitmap *inserted;
3545
 
3546
  /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
3547
     if it reaches any of the deleted expressions.  */
3548
 
3549
  set_size = pre_insert_map[0]->size;
3550
  num_edges = NUM_EDGES (edge_list);
3551
  inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
3552
  sbitmap_vector_zero (inserted, num_edges);
3553
 
3554
  for (e = 0; e < num_edges; e++)
3555
    {
3556
      int indx;
3557
      basic_block bb = INDEX_EDGE_PRED_BB (edge_list, e);
3558
 
3559
      for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
3560
        {
3561
          SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
3562
 
3563
          for (j = indx; insert && j < (int) expr_hash_table.n_elems; j++, insert >>= 1)
3564
            if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
3565
              {
3566
                struct expr *expr = index_map[j];
3567
                struct occr *occr;
3568
 
3569
                /* Now look at each deleted occurrence of this expression.  */
3570
                for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
3571
                  {
3572
                    if (! occr->deleted_p)
3573
                      continue;
3574
 
3575
                    /* Insert this expression on this edge if it would
3576
                       reach the deleted occurrence in BB.  */
3577
                    if (!TEST_BIT (inserted[e], j))
3578
                      {
3579
                        rtx insn;
3580
                        edge eg = INDEX_EDGE (edge_list, e);
3581
 
3582
                        /* We can't insert anything on an abnormal and
3583
                           critical edge, so we insert the insn at the end of
3584
                           the previous block. There are several alternatives
3585
                           detailed in Morgans book P277 (sec 10.5) for
3586
                           handling this situation.  This one is easiest for
3587
                           now.  */
3588
 
3589
                        if (eg->flags & EDGE_ABNORMAL)
3590
                          insert_insn_end_basic_block (index_map[j], bb, 0);
3591
                        else
3592
                          {
3593
                            insn = process_insert_insn (index_map[j]);
3594
                            insert_insn_on_edge (insn, eg);
3595
                          }
3596
 
3597
                        if (dump_file)
3598
                          {
3599
                            fprintf (dump_file, "PRE: edge (%d,%d), ",
3600
                                     bb->index,
3601
                                     INDEX_EDGE_SUCC_BB (edge_list, e)->index);
3602
                            fprintf (dump_file, "copy expression %d\n",
3603
                                     expr->bitmap_index);
3604
                          }
3605
 
3606
                        update_ld_motion_stores (expr);
3607
                        SET_BIT (inserted[e], j);
3608
                        did_insert = 1;
3609
                        gcse_create_count++;
3610
                      }
3611
                  }
3612
              }
3613
        }
3614
    }
3615
 
3616
  sbitmap_vector_free (inserted);
3617
  return did_insert;
3618
}
3619
 
3620
/* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
3621
   Given "old_reg <- expr" (INSN), instead of adding after it
3622
     reaching_reg <- old_reg
3623
   it's better to do the following:
3624
     reaching_reg <- expr
3625
     old_reg      <- reaching_reg
3626
   because this way copy propagation can discover additional PRE
3627
   opportunities.  But if this fails, we try the old way.
3628
   When "expr" is a store, i.e.
3629
   given "MEM <- old_reg", instead of adding after it
3630
     reaching_reg <- old_reg
3631
   it's better to add it before as follows:
3632
     reaching_reg <- old_reg
3633
     MEM          <- reaching_reg.  */
3634
 
3635
static void
3636
pre_insert_copy_insn (struct expr *expr, rtx insn)
3637
{
3638
  rtx reg = expr->reaching_reg;
3639
  int regno = REGNO (reg);
3640
  int indx = expr->bitmap_index;
3641
  rtx pat = PATTERN (insn);
3642
  rtx set, first_set, new_insn;
3643
  rtx old_reg;
3644
  int i;
3645
 
3646
  /* This block matches the logic in hash_scan_insn.  */
3647
  switch (GET_CODE (pat))
3648
    {
3649
    case SET:
3650
      set = pat;
3651
      break;
3652
 
3653
    case PARALLEL:
3654
      /* Search through the parallel looking for the set whose
3655
         source was the expression that we're interested in.  */
3656
      first_set = NULL_RTX;
3657
      set = NULL_RTX;
3658
      for (i = 0; i < XVECLEN (pat, 0); i++)
3659
        {
3660
          rtx x = XVECEXP (pat, 0, i);
3661
          if (GET_CODE (x) == SET)
3662
            {
3663
              /* If the source was a REG_EQUAL or REG_EQUIV note, we
3664
                 may not find an equivalent expression, but in this
3665
                 case the PARALLEL will have a single set.  */
3666
              if (first_set == NULL_RTX)
3667
                first_set = x;
3668
              if (expr_equiv_p (SET_SRC (x), expr->expr))
3669
                {
3670
                  set = x;
3671
                  break;
3672
                }
3673
            }
3674
        }
3675
 
3676
      gcc_assert (first_set);
3677
      if (set == NULL_RTX)
3678
        set = first_set;
3679
      break;
3680
 
3681
    default:
3682
      gcc_unreachable ();
3683
    }
3684
 
3685
  if (REG_P (SET_DEST (set)))
3686
    {
3687
      old_reg = SET_DEST (set);
3688
      /* Check if we can modify the set destination in the original insn.  */
3689
      if (validate_change (insn, &SET_DEST (set), reg, 0))
3690
        {
3691
          new_insn = gen_move_insn (old_reg, reg);
3692
          new_insn = emit_insn_after (new_insn, insn);
3693
        }
3694
      else
3695
        {
3696
          new_insn = gen_move_insn (reg, old_reg);
3697
          new_insn = emit_insn_after (new_insn, insn);
3698
        }
3699
    }
3700
  else /* This is possible only in case of a store to memory.  */
3701
    {
3702
      old_reg = SET_SRC (set);
3703
      new_insn = gen_move_insn (reg, old_reg);
3704
 
3705
      /* Check if we can modify the set source in the original insn.  */
3706
      if (validate_change (insn, &SET_SRC (set), reg, 0))
3707
        new_insn = emit_insn_before (new_insn, insn);
3708
      else
3709
        new_insn = emit_insn_after (new_insn, insn);
3710
    }
3711
 
3712
  gcse_create_count++;
3713
 
3714
  if (dump_file)
3715
    fprintf (dump_file,
3716
             "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
3717
              BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
3718
              INSN_UID (insn), regno);
3719
}
3720
 
3721
/* Copy available expressions that reach the redundant expression
3722
   to `reaching_reg'.  */
3723
 
3724
static void
3725
pre_insert_copies (void)
3726
{
3727
  unsigned int i, added_copy;
3728
  struct expr *expr;
3729
  struct occr *occr;
3730
  struct occr *avail;
3731
 
3732
  /* For each available expression in the table, copy the result to
3733
     `reaching_reg' if the expression reaches a deleted one.
3734
 
3735
     ??? The current algorithm is rather brute force.
3736
     Need to do some profiling.  */
3737
 
3738
  for (i = 0; i < expr_hash_table.size; i++)
3739
    for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
3740
      {
3741
        /* If the basic block isn't reachable, PPOUT will be TRUE.  However,
3742
           we don't want to insert a copy here because the expression may not
3743
           really be redundant.  So only insert an insn if the expression was
3744
           deleted.  This test also avoids further processing if the
3745
           expression wasn't deleted anywhere.  */
3746
        if (expr->reaching_reg == NULL)
3747
          continue;
3748
 
3749
        /* Set when we add a copy for that expression.  */
3750
        added_copy = 0;
3751
 
3752
        for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
3753
          {
3754
            if (! occr->deleted_p)
3755
              continue;
3756
 
3757
            for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
3758
              {
3759
                rtx insn = avail->insn;
3760
 
3761
                /* No need to handle this one if handled already.  */
3762
                if (avail->copied_p)
3763
                  continue;
3764
 
3765
                /* Don't handle this one if it's a redundant one.  */
3766
                if (INSN_DELETED_P (insn))
3767
                  continue;
3768
 
3769
                /* Or if the expression doesn't reach the deleted one.  */
3770
                if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
3771
                                               expr,
3772
                                               BLOCK_FOR_INSN (occr->insn)))
3773
                  continue;
3774
 
3775
                added_copy = 1;
3776
 
3777
                /* Copy the result of avail to reaching_reg.  */
3778
                pre_insert_copy_insn (expr, insn);
3779
                avail->copied_p = 1;
3780
              }
3781
          }
3782
 
3783
          if (added_copy)
3784
            update_ld_motion_stores (expr);
3785
      }
3786
}
3787
 
3788
/* Emit move from SRC to DEST noting the equivalence with expression computed
3789
   in INSN.  */
3790
static rtx
3791
gcse_emit_move_after (rtx src, rtx dest, rtx insn)
3792
{
3793
  rtx new_rtx;
3794
  rtx set = single_set (insn), set2;
3795
  rtx note;
3796
  rtx eqv;
3797
 
3798
  /* This should never fail since we're creating a reg->reg copy
3799
     we've verified to be valid.  */
3800
 
3801
  new_rtx = emit_insn_after (gen_move_insn (dest, src), insn);
3802
 
3803
  /* Note the equivalence for local CSE pass.  */
3804
  set2 = single_set (new_rtx);
3805
  if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
3806
    return new_rtx;
3807
  if ((note = find_reg_equal_equiv_note (insn)))
3808
    eqv = XEXP (note, 0);
3809
  else
3810
    eqv = SET_SRC (set);
3811
 
3812
  set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv));
3813
 
3814
  return new_rtx;
3815
}
3816
 
3817
/* Delete redundant computations.
3818
   Deletion is done by changing the insn to copy the `reaching_reg' of
3819
   the expression into the result of the SET.  It is left to later passes
3820
   (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
3821
 
3822
   Returns nonzero if a change is made.  */
3823
 
3824
static int
3825
pre_delete (void)
3826
{
3827
  unsigned int i;
3828
  int changed;
3829
  struct expr *expr;
3830
  struct occr *occr;
3831
 
3832
  changed = 0;
3833
  for (i = 0; i < expr_hash_table.size; i++)
3834
    for (expr = expr_hash_table.table[i];
3835
         expr != NULL;
3836
         expr = expr->next_same_hash)
3837
      {
3838
        int indx = expr->bitmap_index;
3839
 
3840
        /* We only need to search antic_occr since we require
3841
           ANTLOC != 0.  */
3842
 
3843
        for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
3844
          {
3845
            rtx insn = occr->insn;
3846
            rtx set;
3847
            basic_block bb = BLOCK_FOR_INSN (insn);
3848
 
3849
            /* We only delete insns that have a single_set.  */
3850
            if (TEST_BIT (pre_delete_map[bb->index], indx)
3851
                && (set = single_set (insn)) != 0
3852
                && dbg_cnt (pre_insn))
3853
              {
3854
                /* Create a pseudo-reg to store the result of reaching
3855
                   expressions into.  Get the mode for the new pseudo from
3856
                   the mode of the original destination pseudo.  */
3857
                if (expr->reaching_reg == NULL)
3858
                  expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set));
3859
 
3860
                gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
3861
                delete_insn (insn);
3862
                occr->deleted_p = 1;
3863
                changed = 1;
3864
                gcse_subst_count++;
3865
 
3866
                if (dump_file)
3867
                  {
3868
                    fprintf (dump_file,
3869
                             "PRE: redundant insn %d (expression %d) in ",
3870
                               INSN_UID (insn), indx);
3871
                    fprintf (dump_file, "bb %d, reaching reg is %d\n",
3872
                             bb->index, REGNO (expr->reaching_reg));
3873
                  }
3874
              }
3875
          }
3876
      }
3877
 
3878
  return changed;
3879
}
3880
 
3881
/* Perform GCSE optimizations using PRE.
3882
   This is called by one_pre_gcse_pass after all the dataflow analysis
3883
   has been done.
3884
 
3885
   This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
3886
   lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
3887
   Compiler Design and Implementation.
3888
 
3889
   ??? A new pseudo reg is created to hold the reaching expression.  The nice
3890
   thing about the classical approach is that it would try to use an existing
3891
   reg.  If the register can't be adequately optimized [i.e. we introduce
3892
   reload problems], one could add a pass here to propagate the new register
3893
   through the block.
3894
 
3895
   ??? We don't handle single sets in PARALLELs because we're [currently] not
3896
   able to copy the rest of the parallel when we insert copies to create full
3897
   redundancies from partial redundancies.  However, there's no reason why we
3898
   can't handle PARALLELs in the cases where there are no partial
3899
   redundancies.  */
3900
 
3901
static int
3902
pre_gcse (void)
3903
{
3904
  unsigned int i;
3905
  int did_insert, changed;
3906
  struct expr **index_map;
3907
  struct expr *expr;
3908
 
3909
  /* Compute a mapping from expression number (`bitmap_index') to
3910
     hash table entry.  */
3911
 
3912
  index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems);
3913
  for (i = 0; i < expr_hash_table.size; i++)
3914
    for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
3915
      index_map[expr->bitmap_index] = expr;
3916
 
3917
  /* Delete the redundant insns first so that
3918
     - we know what register to use for the new insns and for the other
3919
       ones with reaching expressions
3920
     - we know which insns are redundant when we go to create copies  */
3921
 
3922
  changed = pre_delete ();
3923
  did_insert = pre_edge_insert (edge_list, index_map);
3924
 
3925
  /* In other places with reaching expressions, copy the expression to the
3926
     specially allocated pseudo-reg that reaches the redundant expr.  */
3927
  pre_insert_copies ();
3928
  if (did_insert)
3929
    {
3930
      commit_edge_insertions ();
3931
      changed = 1;
3932
    }
3933
 
3934
  free (index_map);
3935
  return changed;
3936
}
3937
 
3938
/* Top level routine to perform one PRE GCSE pass.
3939
 
3940
   Return nonzero if a change was made.  */
3941
 
3942
static int
3943
one_pre_gcse_pass (void)
3944
{
3945
  int changed = 0;
3946
 
3947
  gcse_subst_count = 0;
3948
  gcse_create_count = 0;
3949
 
3950
  /* Return if there's nothing to do, or it is too expensive.  */
3951
  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
3952
      || is_too_expensive (_("PRE disabled")))
3953
    return 0;
3954
 
3955
  /* We need alias.  */
3956
  init_alias_analysis ();
3957
 
3958
  bytes_used = 0;
3959
  gcc_obstack_init (&gcse_obstack);
3960
  alloc_gcse_mem ();
3961
 
3962
  alloc_hash_table (&expr_hash_table, 0);
3963
  add_noreturn_fake_exit_edges ();
3964
  if (flag_gcse_lm)
3965
    compute_ld_motion_mems ();
3966
 
3967
  compute_hash_table (&expr_hash_table);
3968
  trim_ld_motion_mems ();
3969
  if (dump_file)
3970
    dump_hash_table (dump_file, "Expression", &expr_hash_table);
3971
 
3972
  if (expr_hash_table.n_elems > 0)
3973
    {
3974
      alloc_pre_mem (last_basic_block, expr_hash_table.n_elems);
3975
      compute_pre_data ();
3976
      changed |= pre_gcse ();
3977
      free_edge_list (edge_list);
3978
      free_pre_mem ();
3979
    }
3980
 
3981
  free_ldst_mems ();
3982
  remove_fake_exit_edges ();
3983
  free_hash_table (&expr_hash_table);
3984
 
3985
  free_gcse_mem ();
3986
  obstack_free (&gcse_obstack, NULL);
3987
 
3988
  /* We are finished with alias.  */
3989
  end_alias_analysis ();
3990
 
3991
  if (dump_file)
3992
    {
3993
      fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
3994
               current_function_name (), n_basic_blocks, bytes_used);
3995
      fprintf (dump_file, "%d substs, %d insns created\n",
3996
               gcse_subst_count, gcse_create_count);
3997
    }
3998
 
3999
  return changed;
4000
}
4001
 
4002
/* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
4003
   to INSN.  If such notes are added to an insn which references a
4004
   CODE_LABEL, the LABEL_NUSES count is incremented.  We have to add
4005
   that note, because the following loop optimization pass requires
4006
   them.  */
4007
 
4008
/* ??? If there was a jump optimization pass after gcse and before loop,
4009
   then we would not need to do this here, because jump would add the
4010
   necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes.  */
4011
 
4012
static void
4013
add_label_notes (rtx x, rtx insn)
4014
{
4015
  enum rtx_code code = GET_CODE (x);
4016
  int i, j;
4017
  const char *fmt;
4018
 
4019
  if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
4020
    {
4021
      /* This code used to ignore labels that referred to dispatch tables to
4022
         avoid flow generating (slightly) worse code.
4023
 
4024
         We no longer ignore such label references (see LABEL_REF handling in
4025
         mark_jump_label for additional information).  */
4026
 
4027
      /* There's no reason for current users to emit jump-insns with
4028
         such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
4029
         notes.  */
4030
      gcc_assert (!JUMP_P (insn));
4031
      add_reg_note (insn, REG_LABEL_OPERAND, XEXP (x, 0));
4032
 
4033
      if (LABEL_P (XEXP (x, 0)))
4034
        LABEL_NUSES (XEXP (x, 0))++;
4035
 
4036
      return;
4037
    }
4038
 
4039
  for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
4040
    {
4041
      if (fmt[i] == 'e')
4042
        add_label_notes (XEXP (x, i), insn);
4043
      else if (fmt[i] == 'E')
4044
        for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4045
          add_label_notes (XVECEXP (x, i, j), insn);
4046
    }
4047
}
4048
 
4049
/* Compute transparent outgoing information for each block.
4050
 
4051
   An expression is transparent to an edge unless it is killed by
4052
   the edge itself.  This can only happen with abnormal control flow,
4053
   when the edge is traversed through a call.  This happens with
4054
   non-local labels and exceptions.
4055
 
4056
   This would not be necessary if we split the edge.  While this is
4057
   normally impossible for abnormal critical edges, with some effort
4058
   it should be possible with exception handling, since we still have
4059
   control over which handler should be invoked.  But due to increased
4060
   EH table sizes, this may not be worthwhile.  */
4061
 
4062
static void
4063
compute_transpout (void)
4064
{
4065
  basic_block bb;
4066
  unsigned int i;
4067
  struct expr *expr;
4068
 
4069
  sbitmap_vector_ones (transpout, last_basic_block);
4070
 
4071
  FOR_EACH_BB (bb)
4072
    {
4073
      /* Note that flow inserted a nop at the end of basic blocks that
4074
         end in call instructions for reasons other than abnormal
4075
         control flow.  */
4076
      if (! CALL_P (BB_END (bb)))
4077
        continue;
4078
 
4079
      for (i = 0; i < expr_hash_table.size; i++)
4080
        for (expr = expr_hash_table.table[i]; expr ; expr = expr->next_same_hash)
4081
          if (MEM_P (expr->expr))
4082
            {
4083
              if (GET_CODE (XEXP (expr->expr, 0)) == SYMBOL_REF
4084
                  && CONSTANT_POOL_ADDRESS_P (XEXP (expr->expr, 0)))
4085
                continue;
4086
 
4087
              /* ??? Optimally, we would use interprocedural alias
4088
                 analysis to determine if this mem is actually killed
4089
                 by this call.  */
4090
              RESET_BIT (transpout[bb->index], expr->bitmap_index);
4091
            }
4092
    }
4093
}
4094
 
4095
/* Code Hoisting variables and subroutines.  */
4096
 
4097
/* Very busy expressions.  */
4098
static sbitmap *hoist_vbein;
4099
static sbitmap *hoist_vbeout;
4100
 
4101
/* Hoistable expressions.  */
4102
static sbitmap *hoist_exprs;
4103
 
4104
/* ??? We could compute post dominators and run this algorithm in
4105
   reverse to perform tail merging, doing so would probably be
4106
   more effective than the tail merging code in jump.c.
4107
 
4108
   It's unclear if tail merging could be run in parallel with
4109
   code hoisting.  It would be nice.  */
4110
 
4111
/* Allocate vars used for code hoisting analysis.  */
4112
 
4113
static void
4114
alloc_code_hoist_mem (int n_blocks, int n_exprs)
4115
{
4116
  antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
4117
  transp = sbitmap_vector_alloc (n_blocks, n_exprs);
4118
  comp = sbitmap_vector_alloc (n_blocks, n_exprs);
4119
 
4120
  hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
4121
  hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
4122
  hoist_exprs = sbitmap_vector_alloc (n_blocks, n_exprs);
4123
  transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
4124
}
4125
 
4126
/* Free vars used for code hoisting analysis.  */
4127
 
4128
static void
4129
free_code_hoist_mem (void)
4130
{
4131
  sbitmap_vector_free (antloc);
4132
  sbitmap_vector_free (transp);
4133
  sbitmap_vector_free (comp);
4134
 
4135
  sbitmap_vector_free (hoist_vbein);
4136
  sbitmap_vector_free (hoist_vbeout);
4137
  sbitmap_vector_free (hoist_exprs);
4138
  sbitmap_vector_free (transpout);
4139
 
4140
  free_dominance_info (CDI_DOMINATORS);
4141
}
4142
 
4143
/* Compute the very busy expressions at entry/exit from each block.
4144
 
4145
   An expression is very busy if all paths from a given point
4146
   compute the expression.  */
4147
 
4148
static void
4149
compute_code_hoist_vbeinout (void)
4150
{
4151
  int changed, passes;
4152
  basic_block bb;
4153
 
4154
  sbitmap_vector_zero (hoist_vbeout, last_basic_block);
4155
  sbitmap_vector_zero (hoist_vbein, last_basic_block);
4156
 
4157
  passes = 0;
4158
  changed = 1;
4159
 
4160
  while (changed)
4161
    {
4162
      changed = 0;
4163
 
4164
      /* We scan the blocks in the reverse order to speed up
4165
         the convergence.  */
4166
      FOR_EACH_BB_REVERSE (bb)
4167
        {
4168
          if (bb->next_bb != EXIT_BLOCK_PTR)
4169
            sbitmap_intersection_of_succs (hoist_vbeout[bb->index],
4170
                                           hoist_vbein, bb->index);
4171
 
4172
          changed |= sbitmap_a_or_b_and_c_cg (hoist_vbein[bb->index],
4173
                                              antloc[bb->index],
4174
                                              hoist_vbeout[bb->index],
4175
                                              transp[bb->index]);
4176
        }
4177
 
4178
      passes++;
4179
    }
4180
 
4181
  if (dump_file)
4182
    fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
4183
}
4184
 
4185
/* Top level routine to do the dataflow analysis needed by code hoisting.  */
4186
 
4187
static void
4188
compute_code_hoist_data (void)
4189
{
4190
  compute_local_properties (transp, comp, antloc, &expr_hash_table);
4191
  compute_transpout ();
4192
  compute_code_hoist_vbeinout ();
4193
  calculate_dominance_info (CDI_DOMINATORS);
4194
  if (dump_file)
4195
    fprintf (dump_file, "\n");
4196
}
4197
 
4198
/* Determine if the expression identified by EXPR_INDEX would
4199
   reach BB unimpared if it was placed at the end of EXPR_BB.
4200
 
4201
   It's unclear exactly what Muchnick meant by "unimpared".  It seems
4202
   to me that the expression must either be computed or transparent in
4203
   *every* block in the path(s) from EXPR_BB to BB.  Any other definition
4204
   would allow the expression to be hoisted out of loops, even if
4205
   the expression wasn't a loop invariant.
4206
 
4207
   Contrast this to reachability for PRE where an expression is
4208
   considered reachable if *any* path reaches instead of *all*
4209
   paths.  */
4210
 
4211
static int
4212
hoist_expr_reaches_here_p (basic_block expr_bb, int expr_index, basic_block bb, char *visited)
4213
{
4214
  edge pred;
4215
  edge_iterator ei;
4216
  int visited_allocated_locally = 0;
4217
 
4218
 
4219
  if (visited == NULL)
4220
    {
4221
      visited_allocated_locally = 1;
4222
      visited = XCNEWVEC (char, last_basic_block);
4223
    }
4224
 
4225
  FOR_EACH_EDGE (pred, ei, bb->preds)
4226
    {
4227
      basic_block pred_bb = pred->src;
4228
 
4229
      if (pred->src == ENTRY_BLOCK_PTR)
4230
        break;
4231
      else if (pred_bb == expr_bb)
4232
        continue;
4233
      else if (visited[pred_bb->index])
4234
        continue;
4235
 
4236
      /* Does this predecessor generate this expression?  */
4237
      else if (TEST_BIT (comp[pred_bb->index], expr_index))
4238
        break;
4239
      else if (! TEST_BIT (transp[pred_bb->index], expr_index))
4240
        break;
4241
 
4242
      /* Not killed.  */
4243
      else
4244
        {
4245
          visited[pred_bb->index] = 1;
4246
          if (! hoist_expr_reaches_here_p (expr_bb, expr_index,
4247
                                           pred_bb, visited))
4248
            break;
4249
        }
4250
    }
4251
  if (visited_allocated_locally)
4252
    free (visited);
4253
 
4254
  return (pred == NULL);
4255
}
4256
 
4257
/* Actually perform code hoisting.  */
4258
 
4259
static int
4260
hoist_code (void)
4261
{
4262
  basic_block bb, dominated;
4263
  VEC (basic_block, heap) *domby;
4264
  unsigned int i,j;
4265
  struct expr **index_map;
4266
  struct expr *expr;
4267
  int changed = 0;
4268
 
4269
  sbitmap_vector_zero (hoist_exprs, last_basic_block);
4270
 
4271
  /* Compute a mapping from expression number (`bitmap_index') to
4272
     hash table entry.  */
4273
 
4274
  index_map = XCNEWVEC (struct expr *, expr_hash_table.n_elems);
4275
  for (i = 0; i < expr_hash_table.size; i++)
4276
    for (expr = expr_hash_table.table[i]; expr != NULL; expr = expr->next_same_hash)
4277
      index_map[expr->bitmap_index] = expr;
4278
 
4279
  /* Walk over each basic block looking for potentially hoistable
4280
     expressions, nothing gets hoisted from the entry block.  */
4281
  FOR_EACH_BB (bb)
4282
    {
4283
      int found = 0;
4284
      int insn_inserted_p;
4285
 
4286
      domby = get_dominated_by (CDI_DOMINATORS, bb);
4287
      /* Examine each expression that is very busy at the exit of this
4288
         block.  These are the potentially hoistable expressions.  */
4289
      for (i = 0; i < hoist_vbeout[bb->index]->n_bits; i++)
4290
        {
4291
          int hoistable = 0;
4292
 
4293
          if (TEST_BIT (hoist_vbeout[bb->index], i)
4294
              && TEST_BIT (transpout[bb->index], i))
4295
            {
4296
              /* We've found a potentially hoistable expression, now
4297
                 we look at every block BB dominates to see if it
4298
                 computes the expression.  */
4299
              for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
4300
                {
4301
                  /* Ignore self dominance.  */
4302
                  if (bb == dominated)
4303
                    continue;
4304
                  /* We've found a dominated block, now see if it computes
4305
                     the busy expression and whether or not moving that
4306
                     expression to the "beginning" of that block is safe.  */
4307
                  if (!TEST_BIT (antloc[dominated->index], i))
4308
                    continue;
4309
 
4310
                  /* Note if the expression would reach the dominated block
4311
                     unimpared if it was placed at the end of BB.
4312
 
4313
                     Keep track of how many times this expression is hoistable
4314
                     from a dominated block into BB.  */
4315
                  if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
4316
                    hoistable++;
4317
                }
4318
 
4319
              /* If we found more than one hoistable occurrence of this
4320
                 expression, then note it in the bitmap of expressions to
4321
                 hoist.  It makes no sense to hoist things which are computed
4322
                 in only one BB, and doing so tends to pessimize register
4323
                 allocation.  One could increase this value to try harder
4324
                 to avoid any possible code expansion due to register
4325
                 allocation issues; however experiments have shown that
4326
                 the vast majority of hoistable expressions are only movable
4327
                 from two successors, so raising this threshold is likely
4328
                 to nullify any benefit we get from code hoisting.  */
4329
              if (hoistable > 1)
4330
                {
4331
                  SET_BIT (hoist_exprs[bb->index], i);
4332
                  found = 1;
4333
                }
4334
            }
4335
        }
4336
      /* If we found nothing to hoist, then quit now.  */
4337
      if (! found)
4338
        {
4339
          VEC_free (basic_block, heap, domby);
4340
          continue;
4341
        }
4342
 
4343
      /* Loop over all the hoistable expressions.  */
4344
      for (i = 0; i < hoist_exprs[bb->index]->n_bits; i++)
4345
        {
4346
          /* We want to insert the expression into BB only once, so
4347
             note when we've inserted it.  */
4348
          insn_inserted_p = 0;
4349
 
4350
          /* These tests should be the same as the tests above.  */
4351
          if (TEST_BIT (hoist_exprs[bb->index], i))
4352
            {
4353
              /* We've found a potentially hoistable expression, now
4354
                 we look at every block BB dominates to see if it
4355
                 computes the expression.  */
4356
              for (j = 0; VEC_iterate (basic_block, domby, j, dominated); j++)
4357
                {
4358
                  /* Ignore self dominance.  */
4359
                  if (bb == dominated)
4360
                    continue;
4361
 
4362
                  /* We've found a dominated block, now see if it computes
4363
                     the busy expression and whether or not moving that
4364
                     expression to the "beginning" of that block is safe.  */
4365
                  if (!TEST_BIT (antloc[dominated->index], i))
4366
                    continue;
4367
 
4368
                  /* The expression is computed in the dominated block and
4369
                     it would be safe to compute it at the start of the
4370
                     dominated block.  Now we have to determine if the
4371
                     expression would reach the dominated block if it was
4372
                     placed at the end of BB.  */
4373
                  if (hoist_expr_reaches_here_p (bb, i, dominated, NULL))
4374
                    {
4375
                      struct expr *expr = index_map[i];
4376
                      struct occr *occr = expr->antic_occr;
4377
                      rtx insn;
4378
                      rtx set;
4379
 
4380
                      /* Find the right occurrence of this expression.  */
4381
                      while (BLOCK_FOR_INSN (occr->insn) != dominated && occr)
4382
                        occr = occr->next;
4383
 
4384
                      gcc_assert (occr);
4385
                      insn = occr->insn;
4386
                      set = single_set (insn);
4387
                      gcc_assert (set);
4388
 
4389
                      /* Create a pseudo-reg to store the result of reaching
4390
                         expressions into.  Get the mode for the new pseudo
4391
                         from the mode of the original destination pseudo.  */
4392
                      if (expr->reaching_reg == NULL)
4393
                        expr->reaching_reg
4394
                          = gen_reg_rtx_and_attrs (SET_DEST (set));
4395
 
4396
                      gcse_emit_move_after (expr->reaching_reg, SET_DEST (set), insn);
4397
                      delete_insn (insn);
4398
                      occr->deleted_p = 1;
4399
                      changed = 1;
4400
                      gcse_subst_count++;
4401
 
4402
                      if (!insn_inserted_p)
4403
                        {
4404
                          insert_insn_end_basic_block (index_map[i], bb, 0);
4405
                          insn_inserted_p = 1;
4406
                        }
4407
                    }
4408
                }
4409
            }
4410
        }
4411
      VEC_free (basic_block, heap, domby);
4412
    }
4413
 
4414
  free (index_map);
4415
 
4416
  return changed;
4417
}
4418
 
4419
/* Top level routine to perform one code hoisting (aka unification) pass
4420
 
4421
   Return nonzero if a change was made.  */
4422
 
4423
static int
4424
one_code_hoisting_pass (void)
4425
{
4426
  int changed = 0;
4427
 
4428
  gcse_subst_count = 0;
4429
  gcse_create_count = 0;
4430
 
4431
  /* Return if there's nothing to do, or it is too expensive.  */
4432
  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
4433
      || is_too_expensive (_("GCSE disabled")))
4434
    return 0;
4435
 
4436
  /* We need alias.  */
4437
  init_alias_analysis ();
4438
 
4439
  bytes_used = 0;
4440
  gcc_obstack_init (&gcse_obstack);
4441
  alloc_gcse_mem ();
4442
 
4443
  alloc_hash_table (&expr_hash_table, 0);
4444
  compute_hash_table (&expr_hash_table);
4445
  if (dump_file)
4446
    dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
4447
 
4448
  if (expr_hash_table.n_elems > 0)
4449
    {
4450
      alloc_code_hoist_mem (last_basic_block, expr_hash_table.n_elems);
4451
      compute_code_hoist_data ();
4452
      changed = hoist_code ();
4453
      free_code_hoist_mem ();
4454
    }
4455
 
4456
  free_hash_table (&expr_hash_table);
4457
  free_gcse_mem ();
4458
  obstack_free (&gcse_obstack, NULL);
4459
 
4460
  /* We are finished with alias.  */
4461
  end_alias_analysis ();
4462
 
4463
  if (dump_file)
4464
    {
4465
      fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
4466
               current_function_name (), n_basic_blocks, bytes_used);
4467
      fprintf (dump_file, "%d substs, %d insns created\n",
4468
               gcse_subst_count, gcse_create_count);
4469
    }
4470
 
4471
  return changed;
4472
}
4473
 
4474
/*  Here we provide the things required to do store motion towards
4475
    the exit. In order for this to be effective, gcse also needed to
4476
    be taught how to move a load when it is kill only by a store to itself.
4477
 
4478
            int i;
4479
            float a[10];
4480
 
4481
            void foo(float scale)
4482
            {
4483
              for (i=0; i<10; i++)
4484
                a[i] *= scale;
4485
            }
4486
 
4487
    'i' is both loaded and stored to in the loop. Normally, gcse cannot move
4488
    the load out since its live around the loop, and stored at the bottom
4489
    of the loop.
4490
 
4491
      The 'Load Motion' referred to and implemented in this file is
4492
    an enhancement to gcse which when using edge based lcm, recognizes
4493
    this situation and allows gcse to move the load out of the loop.
4494
 
4495
      Once gcse has hoisted the load, store motion can then push this
4496
    load towards the exit, and we end up with no loads or stores of 'i'
4497
    in the loop.  */
4498
 
4499
static hashval_t
4500
pre_ldst_expr_hash (const void *p)
4501
{
4502
  int do_not_record_p = 0;
4503
  const struct ls_expr *const x = (const struct ls_expr *) p;
4504
  return hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
4505
}
4506
 
4507
static int
4508
pre_ldst_expr_eq (const void *p1, const void *p2)
4509
{
4510
  const struct ls_expr *const ptr1 = (const struct ls_expr *) p1,
4511
    *const ptr2 = (const struct ls_expr *) p2;
4512
  return expr_equiv_p (ptr1->pattern, ptr2->pattern);
4513
}
4514
 
4515
/* This will search the ldst list for a matching expression. If it
4516
   doesn't find one, we create one and initialize it.  */
4517
 
4518
static struct ls_expr *
4519
ldst_entry (rtx x)
4520
{
4521
  int do_not_record_p = 0;
4522
  struct ls_expr * ptr;
4523
  unsigned int hash;
4524
  void **slot;
4525
  struct ls_expr e;
4526
 
4527
  hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
4528
                   NULL,  /*have_reg_qty=*/false);
4529
 
4530
  e.pattern = x;
4531
  slot = htab_find_slot_with_hash (pre_ldst_table, &e, hash, INSERT);
4532
  if (*slot)
4533
    return (struct ls_expr *)*slot;
4534
 
4535
  ptr = XNEW (struct ls_expr);
4536
 
4537
  ptr->next         = pre_ldst_mems;
4538
  ptr->expr         = NULL;
4539
  ptr->pattern      = x;
4540
  ptr->pattern_regs = NULL_RTX;
4541
  ptr->loads        = NULL_RTX;
4542
  ptr->stores       = NULL_RTX;
4543
  ptr->reaching_reg = NULL_RTX;
4544
  ptr->invalid      = 0;
4545
  ptr->index        = 0;
4546
  ptr->hash_index   = hash;
4547
  pre_ldst_mems     = ptr;
4548
  *slot = ptr;
4549
 
4550
  return ptr;
4551
}
4552
 
4553
/* Free up an individual ldst entry.  */
4554
 
4555
static void
4556
free_ldst_entry (struct ls_expr * ptr)
4557
{
4558
  free_INSN_LIST_list (& ptr->loads);
4559
  free_INSN_LIST_list (& ptr->stores);
4560
 
4561
  free (ptr);
4562
}
4563
 
4564
/* Free up all memory associated with the ldst list.  */
4565
 
4566
static void
4567
free_ldst_mems (void)
4568
{
4569
  if (pre_ldst_table)
4570
    htab_delete (pre_ldst_table);
4571
  pre_ldst_table = NULL;
4572
 
4573
  while (pre_ldst_mems)
4574
    {
4575
      struct ls_expr * tmp = pre_ldst_mems;
4576
 
4577
      pre_ldst_mems = pre_ldst_mems->next;
4578
 
4579
      free_ldst_entry (tmp);
4580
    }
4581
 
4582
  pre_ldst_mems = NULL;
4583
}
4584
 
4585
/* Dump debugging info about the ldst list.  */
4586
 
4587
static void
4588
print_ldst_list (FILE * file)
4589
{
4590
  struct ls_expr * ptr;
4591
 
4592
  fprintf (file, "LDST list: \n");
4593
 
4594
  for (ptr = first_ls_expr (); ptr != NULL; ptr = next_ls_expr (ptr))
4595
    {
4596
      fprintf (file, "  Pattern (%3d): ", ptr->index);
4597
 
4598
      print_rtl (file, ptr->pattern);
4599
 
4600
      fprintf (file, "\n         Loads : ");
4601
 
4602
      if (ptr->loads)
4603
        print_rtl (file, ptr->loads);
4604
      else
4605
        fprintf (file, "(nil)");
4606
 
4607
      fprintf (file, "\n        Stores : ");
4608
 
4609
      if (ptr->stores)
4610
        print_rtl (file, ptr->stores);
4611
      else
4612
        fprintf (file, "(nil)");
4613
 
4614
      fprintf (file, "\n\n");
4615
    }
4616
 
4617
  fprintf (file, "\n");
4618
}
4619
 
4620
/* Returns 1 if X is in the list of ldst only expressions.  */
4621
 
4622
static struct ls_expr *
4623
find_rtx_in_ldst (rtx x)
4624
{
4625
  struct ls_expr e;
4626
  void **slot;
4627
  if (!pre_ldst_table)
4628
    return NULL;
4629
  e.pattern = x;
4630
  slot = htab_find_slot (pre_ldst_table, &e, NO_INSERT);
4631
  if (!slot || ((struct ls_expr *)*slot)->invalid)
4632
    return NULL;
4633
  return (struct ls_expr *) *slot;
4634
}
4635
 
4636
/* Return first item in the list.  */
4637
 
4638
static inline struct ls_expr *
4639
first_ls_expr (void)
4640
{
4641
  return pre_ldst_mems;
4642
}
4643
 
4644
/* Return the next item in the list after the specified one.  */
4645
 
4646
static inline struct ls_expr *
4647
next_ls_expr (struct ls_expr * ptr)
4648
{
4649
  return ptr->next;
4650
}
4651
 
4652
/* Load Motion for loads which only kill themselves.  */
4653
 
4654
/* Return true if x is a simple MEM operation, with no registers or
4655
   side effects. These are the types of loads we consider for the
4656
   ld_motion list, otherwise we let the usual aliasing take care of it.  */
4657
 
4658
static int
4659
simple_mem (const_rtx x)
4660
{
4661
  if (! MEM_P (x))
4662
    return 0;
4663
 
4664
  if (MEM_VOLATILE_P (x))
4665
    return 0;
4666
 
4667
  if (GET_MODE (x) == BLKmode)
4668
    return 0;
4669
 
4670
  /* If we are handling exceptions, we must be careful with memory references
4671
     that may trap. If we are not, the behavior is undefined, so we may just
4672
     continue.  */
4673
  if (flag_non_call_exceptions && may_trap_p (x))
4674
    return 0;
4675
 
4676
  if (side_effects_p (x))
4677
    return 0;
4678
 
4679
  /* Do not consider function arguments passed on stack.  */
4680
  if (reg_mentioned_p (stack_pointer_rtx, x))
4681
    return 0;
4682
 
4683
  if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
4684
    return 0;
4685
 
4686
  return 1;
4687
}
4688
 
4689
/* Make sure there isn't a buried reference in this pattern anywhere.
4690
   If there is, invalidate the entry for it since we're not capable
4691
   of fixing it up just yet.. We have to be sure we know about ALL
4692
   loads since the aliasing code will allow all entries in the
4693
   ld_motion list to not-alias itself.  If we miss a load, we will get
4694
   the wrong value since gcse might common it and we won't know to
4695
   fix it up.  */
4696
 
4697
static void
4698
invalidate_any_buried_refs (rtx x)
4699
{
4700
  const char * fmt;
4701
  int i, j;
4702
  struct ls_expr * ptr;
4703
 
4704
  /* Invalidate it in the list.  */
4705
  if (MEM_P (x) && simple_mem (x))
4706
    {
4707
      ptr = ldst_entry (x);
4708
      ptr->invalid = 1;
4709
    }
4710
 
4711
  /* Recursively process the insn.  */
4712
  fmt = GET_RTX_FORMAT (GET_CODE (x));
4713
 
4714
  for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
4715
    {
4716
      if (fmt[i] == 'e')
4717
        invalidate_any_buried_refs (XEXP (x, i));
4718
      else if (fmt[i] == 'E')
4719
        for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4720
          invalidate_any_buried_refs (XVECEXP (x, i, j));
4721
    }
4722
}
4723
 
4724
/* Find all the 'simple' MEMs which are used in LOADs and STORES.  Simple
4725
   being defined as MEM loads and stores to symbols, with no side effects
4726
   and no registers in the expression.  For a MEM destination, we also
4727
   check that the insn is still valid if we replace the destination with a
4728
   REG, as is done in update_ld_motion_stores.  If there are any uses/defs
4729
   which don't match this criteria, they are invalidated and trimmed out
4730
   later.  */
4731
 
4732
static void
4733
compute_ld_motion_mems (void)
4734
{
4735
  struct ls_expr * ptr;
4736
  basic_block bb;
4737
  rtx insn;
4738
 
4739
  pre_ldst_mems = NULL;
4740
  pre_ldst_table = htab_create (13, pre_ldst_expr_hash,
4741
                                pre_ldst_expr_eq, NULL);
4742
 
4743
  FOR_EACH_BB (bb)
4744
    {
4745
      FOR_BB_INSNS (bb, insn)
4746
        {
4747
          if (NONDEBUG_INSN_P (insn))
4748
            {
4749
              if (GET_CODE (PATTERN (insn)) == SET)
4750
                {
4751
                  rtx src = SET_SRC (PATTERN (insn));
4752
                  rtx dest = SET_DEST (PATTERN (insn));
4753
 
4754
                  /* Check for a simple LOAD...  */
4755
                  if (MEM_P (src) && simple_mem (src))
4756
                    {
4757
                      ptr = ldst_entry (src);
4758
                      if (REG_P (dest))
4759
                        ptr->loads = alloc_INSN_LIST (insn, ptr->loads);
4760
                      else
4761
                        ptr->invalid = 1;
4762
                    }
4763
                  else
4764
                    {
4765
                      /* Make sure there isn't a buried load somewhere.  */
4766
                      invalidate_any_buried_refs (src);
4767
                    }
4768
 
4769
                  /* Check for stores. Don't worry about aliased ones, they
4770
                     will block any movement we might do later. We only care
4771
                     about this exact pattern since those are the only
4772
                     circumstance that we will ignore the aliasing info.  */
4773
                  if (MEM_P (dest) && simple_mem (dest))
4774
                    {
4775
                      ptr = ldst_entry (dest);
4776
 
4777
                      if (! MEM_P (src)
4778
                          && GET_CODE (src) != ASM_OPERANDS
4779
                          /* Check for REG manually since want_to_gcse_p
4780
                             returns 0 for all REGs.  */
4781
                          && can_assign_to_reg_without_clobbers_p (src))
4782
                        ptr->stores = alloc_INSN_LIST (insn, ptr->stores);
4783
                      else
4784
                        ptr->invalid = 1;
4785
                    }
4786
                }
4787
              else
4788
                invalidate_any_buried_refs (PATTERN (insn));
4789
            }
4790
        }
4791
    }
4792
}
4793
 
4794
/* Remove any references that have been either invalidated or are not in the
4795
   expression list for pre gcse.  */
4796
 
4797
static void
4798
trim_ld_motion_mems (void)
4799
{
4800
  struct ls_expr * * last = & pre_ldst_mems;
4801
  struct ls_expr * ptr = pre_ldst_mems;
4802
 
4803
  while (ptr != NULL)
4804
    {
4805
      struct expr * expr;
4806
 
4807
      /* Delete if entry has been made invalid.  */
4808
      if (! ptr->invalid)
4809
        {
4810
          /* Delete if we cannot find this mem in the expression list.  */
4811
          unsigned int hash = ptr->hash_index % expr_hash_table.size;
4812
 
4813
          for (expr = expr_hash_table.table[hash];
4814
               expr != NULL;
4815
               expr = expr->next_same_hash)
4816
            if (expr_equiv_p (expr->expr, ptr->pattern))
4817
              break;
4818
        }
4819
      else
4820
        expr = (struct expr *) 0;
4821
 
4822
      if (expr)
4823
        {
4824
          /* Set the expression field if we are keeping it.  */
4825
          ptr->expr = expr;
4826
          last = & ptr->next;
4827
          ptr = ptr->next;
4828
        }
4829
      else
4830
        {
4831
          *last = ptr->next;
4832
          htab_remove_elt_with_hash (pre_ldst_table, ptr, ptr->hash_index);
4833
          free_ldst_entry (ptr);
4834
          ptr = * last;
4835
        }
4836
    }
4837
 
4838
  /* Show the world what we've found.  */
4839
  if (dump_file && pre_ldst_mems != NULL)
4840
    print_ldst_list (dump_file);
4841
}
4842
 
4843
/* This routine will take an expression which we are replacing with
4844
   a reaching register, and update any stores that are needed if
4845
   that expression is in the ld_motion list.  Stores are updated by
4846
   copying their SRC to the reaching register, and then storing
4847
   the reaching register into the store location. These keeps the
4848
   correct value in the reaching register for the loads.  */
4849
 
4850
static void
4851
update_ld_motion_stores (struct expr * expr)
4852
{
4853
  struct ls_expr * mem_ptr;
4854
 
4855
  if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
4856
    {
4857
      /* We can try to find just the REACHED stores, but is shouldn't
4858
         matter to set the reaching reg everywhere...  some might be
4859
         dead and should be eliminated later.  */
4860
 
4861
      /* We replace (set mem expr) with (set reg expr) (set mem reg)
4862
         where reg is the reaching reg used in the load.  We checked in
4863
         compute_ld_motion_mems that we can replace (set mem expr) with
4864
         (set reg expr) in that insn.  */
4865
      rtx list = mem_ptr->stores;
4866
 
4867
      for ( ; list != NULL_RTX; list = XEXP (list, 1))
4868
        {
4869
          rtx insn = XEXP (list, 0);
4870
          rtx pat = PATTERN (insn);
4871
          rtx src = SET_SRC (pat);
4872
          rtx reg = expr->reaching_reg;
4873
          rtx copy;
4874
 
4875
          /* If we've already copied it, continue.  */
4876
          if (expr->reaching_reg == src)
4877
            continue;
4878
 
4879
          if (dump_file)
4880
            {
4881
              fprintf (dump_file, "PRE:  store updated with reaching reg ");
4882
              print_rtl (dump_file, expr->reaching_reg);
4883
              fprintf (dump_file, ":\n  ");
4884
              print_inline_rtx (dump_file, insn, 8);
4885
              fprintf (dump_file, "\n");
4886
            }
4887
 
4888
          copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
4889
          emit_insn_before (copy, insn);
4890
          SET_SRC (pat) = reg;
4891
          df_insn_rescan (insn);
4892
 
4893
          /* un-recognize this pattern since it's probably different now.  */
4894
          INSN_CODE (insn) = -1;
4895
          gcse_create_count++;
4896
        }
4897
    }
4898
}
4899
 
4900
/* Return true if the graph is too expensive to optimize. PASS is the
4901
   optimization about to be performed.  */
4902
 
4903
static bool
4904
is_too_expensive (const char *pass)
4905
{
4906
  /* Trying to perform global optimizations on flow graphs which have
4907
     a high connectivity will take a long time and is unlikely to be
4908
     particularly useful.
4909
 
4910
     In normal circumstances a cfg should have about twice as many
4911
     edges as blocks.  But we do not want to punish small functions
4912
     which have a couple switch statements.  Rather than simply
4913
     threshold the number of blocks, uses something with a more
4914
     graceful degradation.  */
4915
  if (n_edges > 20000 + n_basic_blocks * 4)
4916
    {
4917
      warning (OPT_Wdisabled_optimization,
4918
               "%s: %d basic blocks and %d edges/basic block",
4919
               pass, n_basic_blocks, n_edges / n_basic_blocks);
4920
 
4921
      return true;
4922
    }
4923
 
4924
  /* If allocating memory for the cprop bitmap would take up too much
4925
     storage it's better just to disable the optimization.  */
4926
  if ((n_basic_blocks
4927
       * SBITMAP_SET_SIZE (max_reg_num ())
4928
       * sizeof (SBITMAP_ELT_TYPE)) > MAX_GCSE_MEMORY)
4929
    {
4930
      warning (OPT_Wdisabled_optimization,
4931
               "%s: %d basic blocks and %d registers",
4932
               pass, n_basic_blocks, max_reg_num ());
4933
 
4934
      return true;
4935
    }
4936
 
4937
  return false;
4938
}
4939
 
4940
 
4941
/* Main function for the CPROP pass.  */
4942
 
4943
static int
4944
one_cprop_pass (void)
4945
{
4946
  int changed = 0;
4947
 
4948
  /* Return if there's nothing to do, or it is too expensive.  */
4949
  if (n_basic_blocks <= NUM_FIXED_BLOCKS + 1
4950
      || is_too_expensive (_ ("const/copy propagation disabled")))
4951
    return 0;
4952
 
4953
  global_const_prop_count = local_const_prop_count = 0;
4954
  global_copy_prop_count = local_copy_prop_count = 0;
4955
 
4956
  bytes_used = 0;
4957
  gcc_obstack_init (&gcse_obstack);
4958
  alloc_gcse_mem ();
4959
 
4960
  /* Do a local const/copy propagation pass first.  The global pass
4961
     only handles global opportunities.
4962
     If the local pass changes something, remove any unreachable blocks
4963
     because the CPROP global dataflow analysis may get into infinite
4964
     loops for CFGs with unreachable blocks.
4965
 
4966
     FIXME: This local pass should not be necessary after CSE (but for
4967
            some reason it still is).  It is also (proven) not necessary
4968
            to run the local pass right after FWPWOP.
4969
 
4970
     FIXME: The global analysis would not get into infinite loops if it
4971
            would use the DF solver (via df_simple_dataflow) instead of
4972
            the solver implemented in this file.  */
4973
  if (local_cprop_pass ())
4974
    {
4975
      delete_unreachable_blocks ();
4976
      df_analyze ();
4977
    }
4978
 
4979
  /* Determine implicit sets.  */
4980
  implicit_sets = XCNEWVEC (rtx, last_basic_block);
4981
  find_implicit_sets ();
4982
 
4983
  alloc_hash_table (&set_hash_table, 1);
4984
  compute_hash_table (&set_hash_table);
4985
 
4986
  /* Free implicit_sets before peak usage.  */
4987
  free (implicit_sets);
4988
  implicit_sets = NULL;
4989
 
4990
  if (dump_file)
4991
    dump_hash_table (dump_file, "SET", &set_hash_table);
4992
  if (set_hash_table.n_elems > 0)
4993
    {
4994
      basic_block bb;
4995
      rtx insn;
4996
 
4997
      alloc_cprop_mem (last_basic_block, set_hash_table.n_elems);
4998
      compute_cprop_data ();
4999
 
5000
      FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR->next_bb->next_bb, EXIT_BLOCK_PTR, next_bb)
5001
        {
5002
          /* Reset tables used to keep track of what's still valid [since
5003
             the start of the block].  */
5004
          reset_opr_set_tables ();
5005
 
5006
          FOR_BB_INSNS (bb, insn)
5007
            if (INSN_P (insn))
5008
              {
5009
                changed |= cprop_insn (insn);
5010
 
5011
                /* Keep track of everything modified by this insn.  */
5012
                /* ??? Need to be careful w.r.t. mods done to INSN.
5013
                       Don't call mark_oprs_set if we turned the
5014
                       insn into a NOTE.  */
5015
                if (! NOTE_P (insn))
5016
                  mark_oprs_set (insn);
5017
              }
5018
        }
5019
 
5020
      changed |= bypass_conditional_jumps ();
5021
      free_cprop_mem ();
5022
    }
5023
 
5024
  free_hash_table (&set_hash_table);
5025
  free_gcse_mem ();
5026
  obstack_free (&gcse_obstack, NULL);
5027
 
5028
  if (dump_file)
5029
    {
5030
      fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
5031
               current_function_name (), n_basic_blocks, bytes_used);
5032
      fprintf (dump_file, "%d local const props, %d local copy props, ",
5033
               local_const_prop_count, local_copy_prop_count);
5034
      fprintf (dump_file, "%d global const props, %d global copy props\n\n",
5035
               global_const_prop_count, global_copy_prop_count);
5036
    }
5037
 
5038
  return changed;
5039
}
5040
 
5041
 
5042
/* All the passes implemented in this file.  Each pass has its
5043
   own gate and execute function, and at the end of the file a
5044
   pass definition for passes.c.
5045
 
5046
   We do not construct an accurate cfg in functions which call
5047
   setjmp, so none of these passes runs if the function calls
5048
   setjmp.
5049
   FIXME: Should just handle setjmp via REG_SETJMP notes.  */
5050
 
5051
static bool
5052
gate_rtl_cprop (void)
5053
{
5054
  return optimize > 0 && flag_gcse
5055
    && !cfun->calls_setjmp
5056
    && dbg_cnt (cprop);
5057
}
5058
 
5059
static unsigned int
5060
execute_rtl_cprop (void)
5061
{
5062
  delete_unreachable_blocks ();
5063
  df_set_flags (DF_LR_RUN_DCE);
5064
  df_analyze ();
5065
  flag_rerun_cse_after_global_opts |= one_cprop_pass ();
5066
  return 0;
5067
}
5068
 
5069
static bool
5070
gate_rtl_pre (void)
5071
{
5072
  return optimize > 0 && flag_gcse
5073
    && !cfun->calls_setjmp
5074
    && optimize_function_for_speed_p (cfun)
5075
    && dbg_cnt (pre);
5076
}
5077
 
5078
static unsigned int
5079
execute_rtl_pre (void)
5080
{
5081
  delete_unreachable_blocks ();
5082
  df_analyze ();
5083
  flag_rerun_cse_after_global_opts |= one_pre_gcse_pass ();
5084
  return 0;
5085
}
5086
 
5087
static bool
5088
gate_rtl_hoist (void)
5089
{
5090
  return optimize > 0 && flag_gcse
5091
    && !cfun->calls_setjmp
5092
    /* It does not make sense to run code hoisting unless we are optimizing
5093
       for code size -- it rarely makes programs faster, and can make then
5094
       bigger if we did PRE (when optimizing for space, we don't run PRE).  */
5095
    && optimize_function_for_size_p (cfun)
5096
    && dbg_cnt (hoist);
5097
}
5098
 
5099
static unsigned int
5100
execute_rtl_hoist (void)
5101
{
5102
  delete_unreachable_blocks ();
5103
  df_analyze ();
5104
  flag_rerun_cse_after_global_opts |= one_code_hoisting_pass ();
5105
  return 0;
5106
}
5107
 
5108
struct rtl_opt_pass pass_rtl_cprop =
5109
{
5110
 {
5111
  RTL_PASS,
5112
  "cprop",                              /* name */
5113
  gate_rtl_cprop,                       /* gate */
5114
  execute_rtl_cprop,                    /* execute */
5115
  NULL,                                 /* sub */
5116
  NULL,                                 /* next */
5117
  0,                                    /* static_pass_number */
5118
  TV_CPROP,                             /* tv_id */
5119
  PROP_cfglayout,                       /* properties_required */
5120
  0,                                    /* properties_provided */
5121
  0,                                    /* properties_destroyed */
5122
  0,                                    /* todo_flags_start */
5123
  TODO_df_finish | TODO_verify_rtl_sharing |
5124
  TODO_dump_func |
5125
  TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
5126
 }
5127
};
5128
 
5129
struct rtl_opt_pass pass_rtl_pre =
5130
{
5131
 {
5132
  RTL_PASS,
5133
  "rtl pre",                            /* name */
5134
  gate_rtl_pre,                         /* gate */
5135
  execute_rtl_pre,                      /* execute */
5136
  NULL,                                 /* sub */
5137
  NULL,                                 /* next */
5138
  0,                                    /* static_pass_number */
5139
  TV_PRE,                               /* tv_id */
5140
  PROP_cfglayout,                       /* properties_required */
5141
  0,                                    /* properties_provided */
5142
  0,                                    /* properties_destroyed */
5143
  0,                                    /* todo_flags_start */
5144
  TODO_df_finish | TODO_verify_rtl_sharing |
5145
  TODO_dump_func |
5146
  TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
5147
 }
5148
};
5149
 
5150
struct rtl_opt_pass pass_rtl_hoist =
5151
{
5152
 {
5153
  RTL_PASS,
5154
  "hoist",                              /* name */
5155
  gate_rtl_hoist,                       /* gate */
5156
  execute_rtl_hoist,                    /* execute */
5157
  NULL,                                 /* sub */
5158
  NULL,                                 /* next */
5159
  0,                                    /* static_pass_number */
5160
  TV_HOIST,                             /* tv_id */
5161
  PROP_cfglayout,                       /* properties_required */
5162
  0,                                    /* properties_provided */
5163
  0,                                    /* properties_destroyed */
5164
  0,                                    /* todo_flags_start */
5165
  TODO_df_finish | TODO_verify_rtl_sharing |
5166
  TODO_dump_func |
5167
  TODO_verify_flow | TODO_ggc_collect   /* todo_flags_finish */
5168
 }
5169
};
5170
 
5171
#include "gt-gcse.h"

powered by: WebSVN 2.1.0

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