gcc/gcse.c

   1 /* Global common subexpression elimination/Partial redundancy elimination
   2    and global constant/copy propagation for GNU compiler.
   3    Copyright (C) 1997, 1998, 1999 Free Software Foundation, Inc.
   4
   5 This file is part of GNU CC.
   6
   7 GNU CC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GNU CC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GNU CC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, USA.  */
  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    - dead store elimination
  28    - a store to the same address as a load does not kill the load if the
  29      source of the store is also the destination of the load.  Handling this
  30      allows more load motion, particularly out of loops.
  31    - ability to realloc sbitmap vectors would allow one initial computation
  32      of reg_set_in_block with only subsequent additions, rather than
  33      recomputing it for each pass
  34
  35 */
  36
  37 /* References searched while implementing this.
  38
  39    Compilers Principles, Techniques and Tools
  40    Aho, Sethi, Ullman
  41    Addison-Wesley, 1988
  42
  43    Global Optimization by Suppression of Partial Redundancies
  44    E. Morel, C. Renvoise
  45    communications of the acm, Vol. 22, Num. 2, Feb. 1979
  46
  47    A Portable Machine-Independent Global Optimizer - Design and Measurements
  48    Frederick Chow
  49    Stanford Ph.D. thesis, Dec. 1983
  50
  51    A Fast Algorithm for Code Movement Optimization
  52    D.M. Dhamdhere
  53    SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
  54
  55    A Solution to a Problem with Morel and Renvoise's
  56    Global Optimization by Suppression of Partial Redundancies
  57    K-H Drechsler, M.P. Stadel
  58    ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
  59
  60    Practical Adaptation of the Global Optimization
  61    Algorithm of Morel and Renvoise
  62    D.M. Dhamdhere
  63    ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
  64
  65    Efficiently Computing Static Single Assignment Form and the Control
  66    Dependence Graph
  67    R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
  68    ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
  69
  70    Lazy Code Motion
  71    J. Knoop, O. Ruthing, B. Steffen
  72    ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
  73
  74    What's In a Region?  Or Computing Control Dependence Regions in Near-Linear
  75    Time for Reducible Flow Control
  76    Thomas Ball
  77    ACM Letters on Programming Languages and Systems,
  78    Vol. 2, Num. 1-4, Mar-Dec 1993
  79
  80    An Efficient Representation for Sparse Sets
  81    Preston Briggs, Linda Torczon
  82    ACM Letters on Programming Languages and Systems,
  83    Vol. 2, Num. 1-4, Mar-Dec 1993
  84
  85    A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
  86    K-H Drechsler, M.P. Stadel
  87    ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
  88
  89    Partial Dead Code Elimination
  90    J. Knoop, O. Ruthing, B. Steffen
  91    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
  92
  93    Effective Partial Redundancy Elimination
  94    P. Briggs, K.D. Cooper
  95    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
  96
  97    The Program Structure Tree: Computing Control Regions in Linear Time
  98    R. Johnson, D. Pearson, K. Pingali
  99    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
 100
 101    Optimal Code Motion: Theory and Practice
 102    J. Knoop, O. Ruthing, B. Steffen
 103    ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
 104
 105    The power of assignment motion
 106    J. Knoop, O. Ruthing, B. Steffen
 107    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
 108
 109    Global code motion / global value numbering
 110    C. Click
 111    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
 112
 113    Value Driven Redundancy Elimination
 114    L.T. Simpson
 115    Rice University Ph.D. thesis, Apr. 1996
 116
 117    Value Numbering
 118    L.T. Simpson
 119    Massively Scalar Compiler Project, Rice University, Sep. 1996
 120
 121    High Performance Compilers for Parallel Computing
 122    Michael Wolfe
 123    Addison-Wesley, 1996
 124
 125    Advanced Compiler Design and Implementation
 126    Steven Muchnick
 127    Morgan Kaufmann, 1997
 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 "toplev.h"
 145
 146 #include "rtl.h"
 147 #include "regs.h"
 148 #include "hard-reg-set.h"
 149 #include "flags.h"
 150 #include "real.h"
 151 #include "insn-config.h"
 152 #include "recog.h"
 153 #include "basic-block.h"
 154 #include "output.h"
 155 #include "function.h"
 156 #include "expr.h"
 157
 158 #include "obstack.h"
 159 #define obstack_chunk_alloc gmalloc
 160 #define obstack_chunk_free free
 161
 162 /* Maximum number of passes to perform.  */
 163 #define MAX_PASSES 1
 164
 165 /* Propagate flow information through back edges and thus enable PRE's
 166    moving loop invariant calculations out of loops.
 167
 168    Originally this tended to create worse overall code, but several
 169    improvements during the development of PRE seem to have made following
 170    back edges generally a win.
 171
 172    Note much of the loop invariant code motion done here would normally
 173    be done by loop.c, which has more heuristics for when to move invariants
 174    out of loops.  At some point we might need to move some of those
 175    heuristics into gcse.c.  */
 176 #define FOLLOW_BACK_EDGES 1
 177
 178 /* We support GCSE via Partial Redundancy Elimination.  PRE optimizations
 179    are a superset of those done by GCSE.
 180
 181    We perform the following steps:
 182
 183    1) Compute basic block information.
 184
 185    2) Compute table of places where registers are set.
 186
 187    3) Perform copy/constant propagation.
 188
 189    4) Perform global cse.
 190
 191    5) Perform another pass of copy/constant propagation.
 192
 193    Two passes of copy/constant propagation are done because the first one
 194    enables more GCSE and the second one helps to clean up the copies that
 195    GCSE creates.  This is needed more for PRE than for Classic because Classic
 196    GCSE will try to use an existing register containing the common
 197    subexpression rather than create a new one.  This is harder to do for PRE
 198    because of the code motion (which Classic GCSE doesn't do).
 199
 200    Expressions we are interested in GCSE-ing are of the form
 201    (set (pseudo-reg) (expression)).
 202    Function want_to_gcse_p says what these are.
 203
 204    PRE handles moving invariant expressions out of loops (by treating them as
 205    partially redundant).
 206
 207    Eventually it would be nice to replace cse.c/gcse.c with SSA (static single
 208    assignment) based GVN (global value numbering).  L. T. Simpson's paper
 209    (Rice University) on value numbering is a useful reference for this.
 210
 211    **********************
 212
 213    We used to support multiple passes but there are diminishing returns in
 214    doing so.  The first pass usually makes 90% of the changes that are doable.
 215    A second pass can make a few more changes made possible by the first pass.
 216    Experiments show any further passes don't make enough changes to justify
 217    the expense.
 218
 219    A study of spec92 using an unlimited number of passes:
 220    [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
 221    [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
 222    [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
 223
 224    It was found doing copy propagation between each pass enables further
 225    substitutions.
 226
 227    PRE is quite expensive in complicated functions because the DFA can take
 228    awhile to converge.  Hence we only perform one pass.  Macro MAX_PASSES can
 229    be modified if one wants to experiment.
 230
 231    **********************
 232
 233    The steps for PRE are:
 234
 235    1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
 236
 237    2) Perform the data flow analysis for PRE.
 238
 239    3) Delete the redundant instructions
 240
 241    4) Insert the required copies [if any] that make the partially
 242       redundant instructions fully redundant.
 243
 244    5) For other reaching expressions, insert an instruction to copy the value
 245       to a newly created pseudo that will reach the redundant instruction.
 246
 247    The deletion is done first so that when we do insertions we
 248    know which pseudo reg to use.
 249
 250    Various papers have argued that PRE DFA is expensive (O(n^2)) and others
 251    argue it is not.  The number of iterations for the algorithm to converge
 252    is typically 2-4 so I don't view it as that expensive (relatively speaking).
 253
 254    PRE GCSE depends heavily on the second CSE pass to clean up the copies
 255    we create.  To make an expression reach the place where it's redundant,
 256    the result of the expression is copied to a new register, and the redundant
 257    expression is deleted by replacing it with this new register.  Classic GCSE
 258    doesn't have this problem as much as it computes the reaching defs of
 259    each register in each block and thus can try to use an existing register.
 260
 261    **********************
 262
 263    A fair bit of simplicity is created by creating small functions for simple
 264    tasks, even when the function is only called in one place.  This may
 265    measurably slow things down [or may not] by creating more function call
 266    overhead than is necessary.  The source is laid out so that it's trivial
 267    to make the affected functions inline so that one can measure what speed
 268    up, if any, can be achieved, and maybe later when things settle things can
 269    be rearranged.
 270
 271    Help stamp out big monolithic functions!  */
 272 \f
 273 /* GCSE global vars.  */
 274
 275 /* -dG dump file.  */
 276 static FILE *gcse_file;
 277
 278 /* Note whether or not we should run jump optimization after gcse.  We
 279    want to do this for two cases.
 280
 281     * If we changed any jumps via cprop.
 282
 283     * If we added any labels via edge splitting.  */
 284
 285 static int run_jump_opt_after_gcse;
 286
 287 /* Element I is a list of I's predecessors/successors.  */
 288 static int_list_ptr *s_preds;
 289 static int_list_ptr *s_succs;
 290
 291 /* Element I is the number of predecessors/successors of basic block I.  */
 292 static int *num_preds;
 293 static int *num_succs;
 294
 295 /* Bitmaps are normally not included in debugging dumps.
 296    However it's useful to be able to print them from GDB.
 297    We could create special functions for this, but it's simpler to
 298    just allow passing stderr to the dump_foo fns.  Since stderr can
 299    be a macro, we store a copy here.  */
 300 static FILE *debug_stderr;
 301
 302 /* An obstack for our working variables.  */
 303 static struct obstack gcse_obstack;
 304
 305 /* Non-zero for each mode that supports (set (reg) (reg)).
 306    This is trivially true for integer and floating point values.
 307    It may or may not be true for condition codes.  */
 308 static char can_copy_p[(int) NUM_MACHINE_MODES];
 309
 310 /* Non-zero if can_copy_p has been initialized.  */
 311 static int can_copy_init_p;
 312
 313 struct reg_use {
 314   rtx reg_rtx;
 315 };
 316
 317 /* Hash table of expressions.  */
 318
 319 struct expr
 320 {
 321   /* The expression (SET_SRC for expressions, PATTERN for assignments).  */
 322   rtx expr;
 323   /* Index in the available expression bitmaps.  */
 324   int bitmap_index;
 325   /* Next entry with the same hash.  */
 326   struct expr *next_same_hash;
 327   /* List of anticipatable occurrences in basic blocks in the function.
 328      An "anticipatable occurrence" is one that is the first occurrence in the
 329      basic block, the operands are not modified in the basic block prior
 330      to the occurrence and the output is not used between the start of
 331      the block and the occurrence.  */
 332   struct occr *antic_occr;
 333   /* List of available occurrence in basic blocks in the function.
 334      An "available occurrence" is one that is the last occurrence in the
 335      basic block and the operands are not modified by following statements in
 336      the basic block [including this insn].  */
 337   struct occr *avail_occr;
 338   /* Non-null if the computation is PRE redundant.
 339      The value is the newly created pseudo-reg to record a copy of the
 340      expression in all the places that reach the redundant copy.  */
 341   rtx reaching_reg;
 342 };
 343
 344 /* Occurrence of an expression.
 345    There is one per basic block.  If a pattern appears more than once the
 346    last appearance is used [or first for anticipatable expressions].  */
 347
 348 struct occr
 349 {
 350   /* Next occurrence of this expression.  */
 351   struct occr *next;
 352   /* The insn that computes the expression.  */
 353   rtx insn;
 354   /* Non-zero if this [anticipatable] occurrence has been deleted.  */
 355   char deleted_p;
 356   /* Non-zero if this [available] occurrence has been copied to
 357      reaching_reg.  */
 358   /* ??? This is mutually exclusive with deleted_p, so they could share
 359      the same byte.  */
 360   char copied_p;
 361 };
 362
 363 /* Expression and copy propagation hash tables.
 364    Each hash table is an array of buckets.
 365    ??? It is known that if it were an array of entries, structure elements
 366    `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
 367    not clear whether in the final analysis a sufficient amount of memory would
 368    be saved as the size of the available expression bitmaps would be larger
 369    [one could build a mapping table without holes afterwards though].
 370    Someday I'll perform the computation and figure it out.
 371 */
 372
 373 /* Total size of the expression hash table, in elements.  */
 374 static int expr_hash_table_size;
 375 /* The table itself.
 376    This is an array of `expr_hash_table_size' elements.  */
 377 static struct expr **expr_hash_table;
 378
 379 /* Total size of the copy propagation hash table, in elements.  */
 380 static int set_hash_table_size;
 381 /* The table itself.
 382    This is an array of `set_hash_table_size' elements.  */
 383 static struct expr **set_hash_table;
 384
 385 /* Mapping of uids to cuids.
 386    Only real insns get cuids.  */
 387 static int *uid_cuid;
 388
 389 /* Highest UID in UID_CUID.  */
 390 static int max_uid;
 391
 392 /* Get the cuid of an insn.  */
 393 #define INSN_CUID(INSN) (uid_cuid[INSN_UID (INSN)])
 394
 395 /* Number of cuids.  */
 396 static int max_cuid;
 397
 398 /* Mapping of cuids to insns.  */
 399 static rtx *cuid_insn;
 400
 401 /* Get insn from cuid.  */
 402 #define CUID_INSN(CUID) (cuid_insn[CUID])
 403
 404 /* Maximum register number in function prior to doing gcse + 1.
 405    Registers created during this pass have regno >= max_gcse_regno.
 406    This is named with "gcse" to not collide with global of same name.  */
 407 static int max_gcse_regno;
 408
 409 /* Maximum number of cse-able expressions found.  */
 410 static int n_exprs;
 411 /* Maximum number of assignments for copy propagation found.  */
 412 static int n_sets;
 413
 414 /* Table of registers that are modified.
 415    For each register, each element is a list of places where the pseudo-reg
 416    is set.
 417
 418    For simplicity, GCSE is done on sets of pseudo-regs only.  PRE GCSE only
 419    requires knowledge of which blocks kill which regs [and thus could use
 420    a bitmap instead of the lists `reg_set_table' uses].
 421
 422    `reg_set_table' and could be turned into an array of bitmaps
 423    (num-bbs x num-regs)
 424    [however perhaps it may be useful to keep the data as is].
 425    One advantage of recording things this way is that `reg_set_table' is
 426    fairly sparse with respect to pseudo regs but for hard regs could be
 427    fairly dense [relatively speaking].
 428    And recording sets of pseudo-regs in lists speeds
 429    up functions like compute_transp since in the case of pseudo-regs we only
 430    need to iterate over the number of times a pseudo-reg is set, not over the
 431    number of basic blocks [clearly there is a bit of a slow down in the cases
 432    where a pseudo is set more than once in a block, however it is believed
 433    that the net effect is to speed things up].  This isn't done for hard-regs
 434    because recording call-clobbered hard-regs in `reg_set_table' at each
 435    function call can consume a fair bit of memory, and iterating over hard-regs
 436    stored this way in compute_transp will be more expensive.  */
 437
 438 typedef struct reg_set {
 439   /* The next setting of this register.  */
 440   struct reg_set *next;
 441   /* The insn where it was set.  */
 442   rtx insn;
 443 } reg_set;
 444 static reg_set **reg_set_table;
 445 /* Size of `reg_set_table'.
 446    The table starts out at max_gcse_regno + slop, and is enlarged as
 447    necessary.  */
 448 static int reg_set_table_size;
 449 /* Amount to grow `reg_set_table' by when it's full.  */
 450 #define REG_SET_TABLE_SLOP 100
 451
 452 /* Bitmap containing one bit for each register in the program.
 453    Used when performing GCSE to track which registers have been set since
 454    the start of the basic block.  */
 455 static sbitmap reg_set_bitmap;
 456
 457 /* For each block, a bitmap of registers set in the block.
 458    This is used by expr_killed_p and compute_transp.
 459    It is computed during hash table computation and not by compute_sets
 460    as it includes registers added since the last pass (or between cprop and
 461    gcse) and it's currently not easy to realloc sbitmap vectors.  */
 462 static sbitmap *reg_set_in_block;
 463
 464 /* For each block, non-zero if memory is set in that block.
 465    This is computed during hash table computation and is used by
 466    expr_killed_p and compute_transp.
 467    ??? Handling of memory is very simple, we don't make any attempt
 468    to optimize things (later).
 469    ??? This can be computed by compute_sets since the information
 470    doesn't change.  */
 471 static char *mem_set_in_block;
 472
 473 /* Various variables for statistics gathering.  */
 474
 475 /* Memory used in a pass.
 476    This isn't intended to be absolutely precise.  Its intent is only
 477    to keep an eye on memory usage.  */
 478 static int bytes_used;
 479 /* GCSE substitutions made.  */
 480 static int gcse_subst_count;
 481 /* Number of copy instructions created.  */
 482 static int gcse_create_count;
 483 /* Number of constants propagated.  */
 484 static int const_prop_count;
 485 /* Number of copys propagated.  */
 486 static int copy_prop_count;
 487 \f
 488 /* These variables are used by classic GCSE.
 489    Normally they'd be defined a bit later, but `rd_gen' needs to
 490    be declared sooner.  */
 491
 492 /* A bitmap of all ones for implementing the algorithm for available
 493    expressions and reaching definitions.  */
 494 /* ??? Available expression bitmaps have a different size than reaching
 495    definition bitmaps.  This should be the larger of the two, however, it
 496    is not currently used for reaching definitions.  */
 497 static sbitmap u_bitmap;
 498
 499 /* Each block has a bitmap of each type.
 500    The length of each blocks bitmap is:
 501
 502        max_cuid  - for reaching definitions
 503        n_exprs - for available expressions
 504
 505    Thus we view the bitmaps as 2 dimensional arrays.  i.e.
 506    rd_kill[block_num][cuid_num]
 507    ae_kill[block_num][expr_num]
 508 */
 509
 510 /* For reaching defs */
 511 static sbitmap *rd_kill, *rd_gen, *reaching_defs, *rd_out;
 512
 513 /* for available exprs */
 514 static sbitmap *ae_kill, *ae_gen, *ae_in, *ae_out;
 515
 516 \f
 517 static void compute_can_copy      PROTO ((void));
 518
 519 static char *gmalloc              PROTO ((unsigned int));
 520 static char *grealloc            PROTO ((char *, unsigned int));
 521 static char *gcse_alloc        PROTO ((unsigned long));
 522 static void alloc_gcse_mem          PROTO ((rtx));
 523 static void free_gcse_mem            PROTO ((void));
 524 static void alloc_reg_set_mem    PROTO ((int));
 525 static void free_reg_set_mem      PROTO ((void));
 526 static void record_one_set          PROTO ((int, rtx));
 527 static void record_set_info        PROTO ((rtx, rtx));
 528 static void compute_sets              PROTO ((rtx));
 529
 530 static void hash_scan_insn          PROTO ((rtx, int, int));
 531 static void hash_scan_set            PROTO ((rtx, rtx, int));
 532 static void hash_scan_clobber    PROTO ((rtx, rtx));
 533 static void hash_scan_call          PROTO ((rtx, rtx));
 534 static int want_to_gcse_p            PROTO ((rtx));
 535 static int oprs_unchanged_p        PROTO ((rtx, rtx, int));
 536 static int oprs_anticipatable_p       PROTO ((rtx, rtx));
 537 static int oprs_available_p        PROTO ((rtx, rtx));
 538 static void insert_expr_in_table      PROTO ((rtx, enum machine_mode,
 539                                               rtx, int, int));
 540 static void insert_set_in_table       PROTO ((rtx, rtx));
 541 static unsigned int hash_expr    PROTO ((rtx, enum machine_mode,
 542                                          int *, int));
 543 static unsigned int hash_expr_1       PROTO ((rtx, enum machine_mode, int *));
 544 static unsigned int hash_set      PROTO ((int, int));
 545 static int expr_equiv_p        PROTO ((rtx, rtx));
 546 static void record_last_reg_set_info  PROTO ((rtx, int));
 547 static void record_last_mem_set_info  PROTO ((rtx));
 548 static void record_last_set_info      PROTO ((rtx, rtx));
 549 static void compute_hash_table  PROTO ((int));
 550 static void alloc_set_hash_table      PROTO ((int));
 551 static void free_set_hash_table       PROTO ((void));
 552 static void compute_set_hash_table    PROTO ((void));
 553 static void alloc_expr_hash_table     PROTO ((int));
 554 static void free_expr_hash_table      PROTO ((void));
 555 static void compute_expr_hash_table   PROTO ((void));
 556 static void dump_hash_table        PROTO ((FILE *, const char *, struct expr **,
 557                                            int, int));
 558 static struct expr *lookup_expr       PROTO ((rtx));
 559 static struct expr *lookup_set  PROTO ((int, rtx));
 560 static struct expr *next_set      PROTO ((int, struct expr *));
 561 static void reset_opr_set_tables      PROTO ((void));
 562 static int oprs_not_set_p            PROTO ((rtx, rtx));
 563 static void mark_call            PROTO ((rtx));
 564 static void mark_set              PROTO ((rtx, rtx));
 565 static void mark_clobber              PROTO ((rtx, rtx));
 566 static void mark_oprs_set            PROTO ((rtx));
 567
 568 static void alloc_cprop_mem        PROTO ((int, int));
 569 static void free_cprop_mem          PROTO ((void));
 570 static void compute_transp          PROTO ((rtx, int, sbitmap *, int));
 571 static void compute_transpout       PROTO ((void));
 572 static void compute_local_properties  PROTO ((sbitmap *, sbitmap *,
 573                                               sbitmap *, int));
 574 static void compute_cprop_avinout     PROTO ((void));
 575 static void compute_cprop_data  PROTO ((void));
 576 static void find_used_regs          PROTO ((rtx));
 577 static int try_replace_reg          PROTO ((rtx, rtx, rtx));
 578 static struct expr *find_avail_set    PROTO ((int, rtx));
 579 static int cprop_jump                   PROTO((rtx, rtx, struct reg_use *, rtx));
 580 static int cprop_cc0_jump               PROTO((rtx, struct reg_use *, rtx));
 581 static int cprop_insn            PROTO ((rtx, int));
 582 static int cprop                      PROTO ((int));
 583 static int one_cprop_pass            PROTO ((int, int));
 584
 585 static void alloc_pre_mem            PROTO ((int, int));
 586 static void free_pre_mem              PROTO ((void));
 587 static void compute_pre_data      PROTO ((void));
 588 static int pre_expr_reaches_here_p    PROTO ((int, struct expr *,
 589                                               int, int, char *));
 590 static void insert_insn_end_bb  PROTO ((struct expr *, int, int));
 591 static void pre_insert          PROTO ((struct expr **));
 592 static void pre_insert_copy_insn      PROTO ((struct expr *, rtx));
 593 static void pre_insert_copies    PROTO ((void));
 594 static int pre_delete            PROTO ((void));
 595 static int pre_gcse                PROTO ((void));
 596 static int one_pre_gcse_pass      PROTO ((int));
 597
 598 static void add_label_notes           PROTO ((rtx, rtx));
 599
 600 static void alloc_rd_mem              PROTO ((int, int));
 601 static void free_rd_mem        PROTO ((void));
 602 static void handle_rd_kill_set  PROTO ((rtx, int, int));
 603 static void compute_kill_rd        PROTO ((void));
 604 static void compute_rd          PROTO ((void));
 605 static void alloc_avail_expr_mem      PROTO ((int, int));
 606 static void free_avail_expr_mem       PROTO ((void));
 607 static void compute_ae_gen          PROTO ((void));
 608 static int expr_killed_p              PROTO ((rtx, int));
 609 static void compute_ae_kill        PROTO ((void));
 610 static void compute_available    PROTO ((void));
 611 static int expr_reaches_here_p  PROTO ((struct occr *, struct expr *,
 612                                               int, int, char *));
 613 static rtx computing_insn            PROTO ((struct expr *, rtx));
 614 static int def_reaches_here_p    PROTO ((rtx, rtx));
 615 static int can_disregard_other_sets   PROTO ((struct reg_set **, rtx, int));
 616 static int handle_avail_expr      PROTO ((rtx, struct expr *));
 617 static int classic_gcse        PROTO ((void));
 618 static int one_classic_gcse_pass      PROTO ((int));
 619
 620 \f
 621 /* Entry point for global common subexpression elimination.
 622    F is the first instruction in the function.  */
 623
 624 int
 625 gcse_main (f, file)
 626      rtx f;
 627      FILE *file;
 628 {
 629   int changed, pass;
 630   /* Bytes used at start of pass.  */
 631   int initial_bytes_used;
 632   /* Maximum number of bytes used by a pass.  */
 633   int max_pass_bytes;
 634   /* Point to release obstack data from for each pass.  */
 635   char *gcse_obstack_bottom;
 636
 637   /* We do not construct an accurate cfg in functions which call
 638      setjmp, so just punt to be safe.  */
 639   if (current_function_calls_setjmp)
 640     return 0;
 641
 642   /* Assume that we do not need to run jump optimizations after gcse.  */
 643   run_jump_opt_after_gcse = 0;
 644
 645   /* For calling dump_foo fns from gdb.  */
 646   debug_stderr = stderr;
 647   gcse_file = file;
 648
 649   /* Identify the basic block information for this function, including
 650      successors and predecessors.  */
 651   max_gcse_regno = max_reg_num ();
 652   find_basic_blocks (f, max_gcse_regno, file, 1);
 653
 654   /* Return if there's nothing to do.  */
 655   if (n_basic_blocks <= 1)
 656     {
 657       /* Free storage allocated by find_basic_blocks.  */
 658       free_basic_block_vars (0);
 659       return 0;
 660     }
 661
 662   /* See what modes support reg/reg copy operations.  */
 663   if (! can_copy_init_p)
 664     {
 665       compute_can_copy ();
 666       can_copy_init_p = 1;
 667     }
 668
 669   gcc_obstack_init (&gcse_obstack);
 670
 671   /* Allocate and compute predecessors/successors.  */
 672
 673   s_preds = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
 674   s_succs = (int_list_ptr *) alloca (n_basic_blocks * sizeof (int_list_ptr));
 675   num_preds = (int *) alloca (n_basic_blocks * sizeof (int));
 676   num_succs = (int *) alloca (n_basic_blocks * sizeof (int));
 677   bytes_used = 4 * n_basic_blocks * sizeof (int_list_ptr);
 678   compute_preds_succs (s_preds, s_succs, num_preds, num_succs);
 679
 680   if (file)
 681     dump_bb_data (file, s_preds, s_succs, 0);
 682
 683   /* Record where pseudo-registers are set.
 684      This data is kept accurate during each pass.
 685      ??? We could also record hard-reg information here
 686      [since it's unchanging], however it is currently done during
 687      hash table computation.
 688
 689      It may be tempting to compute MEM set information here too, but MEM
 690      sets will be subject to code motion one day and thus we need to compute
 691      information about memory sets when we build the hash tables.  */
 692
 693   alloc_reg_set_mem (max_gcse_regno);
 694   compute_sets (f);
 695
 696   pass = 0;
 697   initial_bytes_used = bytes_used;
 698   max_pass_bytes = 0;
 699   gcse_obstack_bottom = gcse_alloc (1);
 700   changed = 1;
 701   while (changed && pass < MAX_PASSES)
 702     {
 703       changed = 0;
 704       if (file)
 705         fprintf (file, "GCSE pass %d\n\n", pass + 1);
 706
 707       /* Initialize bytes_used to the space for the pred/succ lists,
 708          and the reg_set_table data.  */
 709       bytes_used = initial_bytes_used;
 710
 711       /* Each pass may create new registers, so recalculate each time.  */
 712       max_gcse_regno = max_reg_num ();
 713
 714       alloc_gcse_mem (f);
 715
 716       /* Don't allow constant propagation to modify jumps
 717          during this pass.  */
 718       changed = one_cprop_pass (pass + 1, 0);
 719
 720       if (optimize_size)
 721         changed |= one_classic_gcse_pass (pass + 1);
 722       else
 723         changed |= one_pre_gcse_pass (pass + 1);
 724
 725       if (max_pass_bytes < bytes_used)
 726         max_pass_bytes = bytes_used;
 727
 728       free_gcse_mem ();
 729
 730       if (file)
 731         {
 732           fprintf (file, "\n");
 733           fflush (file);
 734         }
 735       obstack_free (&gcse_obstack, gcse_obstack_bottom);
 736       pass++;
 737     }
 738
 739   /* Do one last pass of copy propagation, including cprop into
 740      conditional jumps.  */
 741
 742   max_gcse_regno = max_reg_num ();
 743   alloc_gcse_mem (f);
 744   /* This time, go ahead and allow cprop to alter jumps.  */
 745   one_cprop_pass (pass + 1, 1);
 746   free_gcse_mem ();
 747
 748   if (file)
 749     {
 750       fprintf (file, "GCSE of %s: %d basic blocks, ",
 751                current_function_name, n_basic_blocks);
 752       fprintf (file, "%d pass%s, %d bytes\n\n",
 753                pass, pass > 1 ? "es" : "", max_pass_bytes);
 754     }
 755
 756   /* Free our obstack.  */
 757   obstack_free (&gcse_obstack, NULL_PTR);
 758   /* Free reg_set_table.  */
 759   free_reg_set_mem ();
 760   /* Free storage used to record predecessor/successor data.  */
 761   free_bb_mem ();
 762   /* Free storage allocated by find_basic_blocks.  */
 763   free_basic_block_vars (0);
 764   return run_jump_opt_after_gcse;
 765 }
 766 \f
 767 /* Misc. utilities.  */
 768
 769 /* Compute which modes support reg/reg copy operations.  */
 770
 771 static void
 772 compute_can_copy ()
 773 {
 774   int i;
 775 #ifndef AVOID_CCMODE_COPIES
 776   rtx reg,insn;
 777 #endif
 778   char *free_point = (char *) oballoc (1);
 779
 780   bzero (can_copy_p, NUM_MACHINE_MODES);
 781
 782   start_sequence ();
 783   for (i = 0; i < NUM_MACHINE_MODES; i++)
 784     {
 785       switch (GET_MODE_CLASS (i))
 786         {
 787         case MODE_CC :
 788 #ifdef AVOID_CCMODE_COPIES
 789           can_copy_p[i] = 0;
 790 #else
 791           reg = gen_rtx_REG ((enum machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
 792           insn = emit_insn (gen_rtx_SET (VOIDmode, reg, reg));
 793           if (recog (PATTERN (insn), insn, NULL_PTR) >= 0)
 794             can_copy_p[i] = 1;
 795 #endif
 796           break;
 797         default :
 798           can_copy_p[i] = 1;
 799           break;
 800         }
 801     }
 802   end_sequence ();
 803
 804   /* Free the objects we just allocated.  */
 805   obfree (free_point);
 806 }
 807 \f
 808 /* Cover function to xmalloc to record bytes allocated.  */
 809
 810 static char *
 811 gmalloc (size)
 812      unsigned int size;
 813 {
 814   bytes_used += size;
 815   return xmalloc (size);
 816 }
 817
 818 /* Cover function to xrealloc.
 819    We don't record the additional size since we don't know it.
 820    It won't affect memory usage stats much anyway.  */
 821
 822 static char *
 823 grealloc (ptr, size)
 824      char *ptr;
 825      unsigned int size;
 826 {
 827   return xrealloc (ptr, size);
 828 }
 829
 830 /* Cover function to obstack_alloc.
 831    We don't need to record the bytes allocated here since
 832    obstack_chunk_alloc is set to gmalloc.  */
 833
 834 static char *
 835 gcse_alloc (size)
 836      unsigned long size;
 837 {
 838   return (char *) obstack_alloc (&gcse_obstack, size);
 839 }
 840
 841 /* Allocate memory for the cuid mapping array,
 842    and reg/memory set tracking tables.
 843
 844    This is called at the start of each pass.  */
 845
 846 static void
 847 alloc_gcse_mem (f)
 848      rtx f;
 849 {
 850   int i,n;
 851   rtx insn;
 852
 853   /* Find the largest UID and create a mapping from UIDs to CUIDs.
 854      CUIDs are like UIDs except they increase monotonically, have no gaps,
 855      and only apply to real insns.  */
 856
 857   max_uid = get_max_uid ();
 858   n = (max_uid + 1) * sizeof (int);
 859   uid_cuid = (int *) gmalloc (n);
 860   bzero ((char *) uid_cuid, n);
 861   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 862     {
 863       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 864         INSN_CUID (insn) = i++;
 865       else
 866         INSN_CUID (insn) = i;
 867     }
 868
 869   /* Create a table mapping cuids to insns.  */
 870
 871   max_cuid = i;
 872   n = (max_cuid + 1) * sizeof (rtx);
 873   cuid_insn = (rtx *) gmalloc (n);
 874   bzero ((char *) cuid_insn, n);
 875   for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
 876     {
 877       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
 878         {
 879           CUID_INSN (i) = insn;
 880           i++;
 881         }
 882     }
 883
 884   /* Allocate vars to track sets of regs.  */
 885
 886   reg_set_bitmap = (sbitmap) sbitmap_alloc (max_gcse_regno);
 887
 888   /* Allocate vars to track sets of regs, memory per block.  */
 889
 890   reg_set_in_block = (sbitmap *) sbitmap_vector_alloc (n_basic_blocks,
 891                                                        max_gcse_regno);
 892   mem_set_in_block = (char *) gmalloc (n_basic_blocks);
 893 }
 894
 895 /* Free memory allocated by alloc_gcse_mem.  */
 896
 897 static void
 898 free_gcse_mem ()
 899 {
 900   free (uid_cuid);
 901   free (cuid_insn);
 902
 903   free (reg_set_bitmap);
 904
 905   free (reg_set_in_block);
 906   free (mem_set_in_block);
 907 }
 908
 909 \f
 910 /* Compute the local properties of each recorded expression.
 911    Local properties are those that are defined by the block, irrespective
 912    of other blocks.
 913
 914    An expression is transparent in a block if its operands are not modified
 915    in the block.
 916
 917    An expression is computed (locally available) in a block if it is computed
 918    at least once and expression would contain the same value if the
 919    computation was moved to the end of the block.
 920
 921    An expression is locally anticipatable in a block if it is computed at
 922    least once and expression would contain the same value if the computation
 923    was moved to the beginning of the block.
 924
 925    We call this routine for cprop, pre and code hoisting.  They all
 926    compute basically the same information and thus can easily share
 927    this code.
 928
 929    TRANSP, COMP, and ANTLOC are destination sbitmaps for recording
 930    local properties.  If NULL, then it is not necessary to compute
 931    or record that particular property.
 932
 933    SETP controls which hash table to look at.  If zero, this routine
 934    looks at the expr hash table; if nonzero this routine looks at
 935    the set hash table.  Additionally, TRANSP is computed as ~TRANSP,
 936    since this is really cprop's ABSALTERED.  */
 937
 938 static void
 939 compute_local_properties (transp, comp, antloc, setp)
 940      sbitmap *transp;
 941      sbitmap *comp;
 942      sbitmap *antloc;
 943      int setp;
 944 {
 945   int i, hash_table_size;
 946   struct expr **hash_table;
 947
 948   /* Initialize any bitmaps that were passed in.  */
 949   if (transp)
 950     {
 951       if (setp)
 952         sbitmap_vector_zero (transp, n_basic_blocks);
 953       else
 954         sbitmap_vector_ones (transp, n_basic_blocks);
 955     }
 956   if (comp)
 957     sbitmap_vector_zero (comp, n_basic_blocks);
 958   if (antloc)
 959     sbitmap_vector_zero (antloc, n_basic_blocks);
 960
 961   /* We use the same code for cprop, pre and hoisting.  For cprop
 962      we care about the set hash table, for pre and hoisting we
 963      care about the expr hash table.  */
 964   hash_table_size = setp ? set_hash_table_size : expr_hash_table_size;
 965   hash_table = setp ? set_hash_table : expr_hash_table;
 966
 967   for (i = 0; i < hash_table_size; i++)
 968     {
 969       struct expr *expr;
 970
 971       for (expr = hash_table[i]; expr != NULL; expr = expr->next_same_hash)
 972         {
 973           struct occr *occr;
 974           int indx = expr->bitmap_index;
 975
 976           /* The expression is transparent in this block if it is not killed.
 977              We start by assuming all are transparent [none are killed], and
 978              then reset the bits for those that are.  */
 979
 980           if (transp)
 981             compute_transp (expr->expr, indx, transp, setp);
 982
 983           /* The occurrences recorded in antic_occr are exactly those that
 984              we want to set to non-zero in ANTLOC.  */
 985
 986           if (antloc)
 987             {
 988               for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
 989                 {
 990                   int bb = BLOCK_NUM (occr->insn);
 991                   SET_BIT (antloc[bb], indx);
 992
 993                   /* While we're scanning the table, this is a good place to
 994                      initialize this.  */
 995                   occr->deleted_p = 0;
 996                 }
 997             }
 998
 999           /* The occurrences recorded in avail_occr are exactly those that
1000              we want to set to non-zero in COMP.  */
1001           if (comp)
1002             {
1003
1004               for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
1005                 {
1006                   int bb = BLOCK_NUM (occr->insn);
1007                   SET_BIT (comp[bb], indx);
1008
1009                   /* While we're scanning the table, this is a good place to
1010                      initialize this.  */
1011                   occr->copied_p = 0;
1012                 }
1013             }
1014
1015           /* While we're scanning the table, this is a good place to
1016              initialize this.  */
1017           expr->reaching_reg = 0;
1018         }
1019     }
1020 }
1021
1022 \f
1023 /* Register set information.
1024
1025    `reg_set_table' records where each register is set or otherwise
1026    modified.  */
1027
1028 static struct obstack reg_set_obstack;
1029
1030 static void
1031 alloc_reg_set_mem (n_regs)
1032      int n_regs;
1033 {
1034   int n;
1035
1036   reg_set_table_size = n_regs + REG_SET_TABLE_SLOP;
1037   n = reg_set_table_size * sizeof (struct reg_set *);
1038   reg_set_table = (struct reg_set **) gmalloc (n);
1039   bzero ((char *) reg_set_table, n);
1040
1041   gcc_obstack_init (&reg_set_obstack);
1042 }
1043
1044 static void
1045 free_reg_set_mem ()
1046 {
1047   free (reg_set_table);
1048   obstack_free (&reg_set_obstack, NULL_PTR);
1049 }
1050
1051 /* Record REGNO in the reg_set table.  */
1052
1053 static void
1054 record_one_set (regno, insn)
1055      int regno;
1056      rtx insn;
1057 {
1058   /* allocate a new reg_set element and link it onto the list */
1059   struct reg_set *new_reg_info, *reg_info_ptr1, *reg_info_ptr2;
1060
1061   /* If the table isn't big enough, enlarge it.  */
1062   if (regno >= reg_set_table_size)
1063     {
1064       int new_size = regno + REG_SET_TABLE_SLOP;
1065       reg_set_table = (struct reg_set **)
1066         grealloc ((char *) reg_set_table,
1067                   new_size * sizeof (struct reg_set *));
1068       bzero ((char *) (reg_set_table + reg_set_table_size),
1069              (new_size - reg_set_table_size) * sizeof (struct reg_set *));
1070       reg_set_table_size = new_size;
1071     }
1072
1073   new_reg_info = (struct reg_set *) obstack_alloc (&reg_set_obstack,
1074                                                    sizeof (struct reg_set));
1075   bytes_used += sizeof (struct reg_set);
1076   new_reg_info->insn = insn;
1077   new_reg_info->next = NULL;
1078   if (reg_set_table[regno] == NULL)
1079     reg_set_table[regno] = new_reg_info;
1080   else
1081     {
1082       reg_info_ptr1 = reg_info_ptr2 = reg_set_table[regno];
1083       /* ??? One could keep a "last" pointer to speed this up.  */
1084       while (reg_info_ptr1 != NULL)
1085         {
1086           reg_info_ptr2 = reg_info_ptr1;
1087           reg_info_ptr1 = reg_info_ptr1->next;
1088         }
1089       reg_info_ptr2->next = new_reg_info;
1090     }
1091 }
1092
1093 /* For communication between next two functions (via note_stores).  */
1094 static rtx record_set_insn;
1095
1096 /* Called from compute_sets via note_stores to handle one
1097    SET or CLOBBER in an insn.  */
1098
1099 static void
1100 record_set_info (dest, setter)
1101      rtx dest, setter ATTRIBUTE_UNUSED;
1102 {
1103   if (GET_CODE (dest) == SUBREG)
1104     dest = SUBREG_REG (dest);
1105
1106   if (GET_CODE (dest) == REG)
1107     {
1108       if (REGNO (dest) >= FIRST_PSEUDO_REGISTER)
1109         record_one_set (REGNO (dest), record_set_insn);
1110     }
1111 }
1112
1113 /* Scan the function and record each set of each pseudo-register.
1114
1115    This is called once, at the start of the gcse pass.
1116    See the comments for `reg_set_table' for further docs.  */
1117
1118 static void
1119 compute_sets (f)
1120      rtx f;
1121 {
1122   rtx insn = f;
1123
1124   while (insn)
1125     {
1126       if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
1127         {
1128           record_set_insn = insn;
1129           note_stores (PATTERN (insn), record_set_info);
1130         }
1131       insn = NEXT_INSN (insn);
1132     }
1133 }
1134 \f
1135 /* Hash table support.  */
1136
1137 #define NEVER_SET -1
1138
1139 /* For each register, the cuid of the first/last insn in the block to set it,
1140    or -1 if not set.  */
1141 static int *reg_first_set;
1142 static int *reg_last_set;
1143
1144 /* While computing "first/last set" info, this is the CUID of first/last insn
1145    to set memory or -1 if not set.  `mem_last_set' is also used when
1146    performing GCSE to record whether memory has been set since the beginning
1147    of the block.
1148    Note that handling of memory is very simple, we don't make any attempt
1149    to optimize things (later).  */
1150 static int mem_first_set;
1151 static int mem_last_set;
1152
1153 /* Perform a quick check whether X, the source of a set, is something
1154    we want to consider for GCSE.  */
1155
1156 static int
1157 want_to_gcse_p (x)
1158      rtx x;
1159 {
1160   enum rtx_code code = GET_CODE (x);
1161
1162   switch (code)
1163     {
1164     case REG:
1165     case SUBREG:
1166     case CONST_INT:
1167     case CONST_DOUBLE:
1168     case CALL:
1169       return 0;
1170
1171     default:
1172       break;
1173     }
1174
1175   return 1;
1176 }
1177
1178 /* Return non-zero if the operands of expression X are unchanged from the
1179    start of INSN's basic block up to but not including INSN (if AVAIL_P == 0),
1180    or from INSN to the end of INSN's basic block (if AVAIL_P != 0).  */
1181
1182 static int
1183 oprs_unchanged_p (x, insn, avail_p)
1184      rtx x, insn;
1185      int avail_p;
1186 {
1187   int i;
1188   enum rtx_code code;
1189   const char *fmt;
1190
1191   /* repeat is used to turn tail-recursion into iteration.  */
1192  repeat:
1193
1194   if (x == 0)
1195     return 1;
1196
1197   code = GET_CODE (x);
1198   switch (code)
1199     {
1200     case REG:
1201       if (avail_p)
1202         return (reg_last_set[REGNO (x)] == NEVER_SET
1203                 || reg_last_set[REGNO (x)] < INSN_CUID (insn));
1204       else
1205         return (reg_first_set[REGNO (x)] == NEVER_SET
1206                 || reg_first_set[REGNO (x)] >= INSN_CUID (insn));
1207
1208     case MEM:
1209       if (avail_p)
1210         {
1211           if (mem_last_set != NEVER_SET
1212               && mem_last_set >= INSN_CUID (insn))
1213             return 0;
1214         }
1215       else
1216         {
1217           if (mem_first_set != NEVER_SET
1218               && mem_first_set < INSN_CUID (insn))
1219             return 0;
1220         }
1221       x = XEXP (x, 0);
1222       goto repeat;
1223
1224     case PRE_DEC:
1225     case PRE_INC:
1226     case POST_DEC:
1227     case POST_INC:
1228       return 0;
1229
1230     case PC:
1231     case CC0: /*FIXME*/
1232     case CONST:
1233     case CONST_INT:
1234     case CONST_DOUBLE:
1235     case SYMBOL_REF:
1236     case LABEL_REF:
1237     case ADDR_VEC:
1238     case ADDR_DIFF_VEC:
1239       return 1;
1240
1241     default:
1242       break;
1243     }
1244
1245   i = GET_RTX_LENGTH (code) - 1;
1246   fmt = GET_RTX_FORMAT (code);
1247   for (; i >= 0; i--)
1248     {
1249       if (fmt[i] == 'e')
1250         {
1251           rtx tem = XEXP (x, i);
1252
1253           /* If we are about to do the last recursive call
1254              needed at this level, change it into iteration.
1255              This function is called enough to be worth it.  */
1256           if (i == 0)
1257             {
1258               x = tem;
1259               goto repeat;
1260             }
1261           if (! oprs_unchanged_p (tem, insn, avail_p))
1262             return 0;
1263         }
1264       else if (fmt[i] == 'E')
1265         {
1266           int j;
1267           for (j = 0; j < XVECLEN (x, i); j++)
1268             {
1269               if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
1270                 return 0;
1271             }
1272         }
1273     }
1274
1275   return 1;
1276 }
1277
1278 /* Return non-zero if the operands of expression X are unchanged from
1279    the start of INSN's basic block up to but not including INSN.  */
1280
1281 static int
1282 oprs_anticipatable_p (x, insn)
1283      rtx x, insn;
1284 {
1285   return oprs_unchanged_p (x, insn, 0);
1286 }
1287
1288 /* Return non-zero if the operands of expression X are unchanged from
1289    INSN to the end of INSN's basic block.  */
1290
1291 static int
1292 oprs_available_p (x, insn)
1293      rtx x, insn;
1294 {
1295   return oprs_unchanged_p (x, insn, 1);
1296 }
1297
1298 /* Hash expression X.
1299    MODE is only used if X is a CONST_INT.
1300    A boolean indicating if a volatile operand is found or if the expression
1301    contains something we don't want to insert in the table is stored in
1302    DO_NOT_RECORD_P.
1303
1304    ??? One might want to merge this with canon_hash.  Later.  */
1305
1306 static unsigned int
1307 hash_expr (x, mode, do_not_record_p, hash_table_size)
1308      rtx x;
1309      enum machine_mode mode;
1310      int *do_not_record_p;
1311      int hash_table_size;
1312 {
1313   unsigned int hash;
1314
1315   *do_not_record_p = 0;
1316
1317   hash = hash_expr_1 (x, mode, do_not_record_p);
1318   return hash % hash_table_size;
1319 }
1320
1321 /* Subroutine of hash_expr to do the actual work.  */
1322
1323 static unsigned int
1324 hash_expr_1 (x, mode, do_not_record_p)
1325      rtx x;
1326      enum machine_mode mode;
1327      int *do_not_record_p;
1328 {
1329   int i, j;
1330   unsigned hash = 0;
1331   enum rtx_code code;
1332   const char *fmt;
1333
1334   /* repeat is used to turn tail-recursion into iteration.  */
1335  repeat:
1336
1337   if (x == 0)
1338     return hash;
1339
1340   code = GET_CODE (x);
1341   switch (code)
1342     {
1343     case REG:
1344       {
1345         register int regno = REGNO (x);
1346         hash += ((unsigned) REG << 7) + regno;
1347         return hash;
1348       }
1349
1350     case CONST_INT:
1351       {
1352         unsigned HOST_WIDE_INT tem = INTVAL (x);
1353         hash += ((unsigned) CONST_INT << 7) + (unsigned) mode + tem;
1354         return hash;
1355       }
1356
1357     case CONST_DOUBLE:
1358       /* This is like the general case, except that it only counts
1359          the integers representing the constant.  */
1360       hash += (unsigned) code + (unsigned) GET_MODE (x);
1361       if (GET_MODE (x) != VOIDmode)
1362         for (i = 2; i < GET_RTX_LENGTH (CONST_DOUBLE); i++)
1363           {
1364             unsigned tem = XINT (x, i);
1365             hash += tem;
1366           }
1367       else
1368         hash += ((unsigned) CONST_DOUBLE_LOW (x)
1369                  + (unsigned) CONST_DOUBLE_HIGH (x));
1370       return hash;
1371
1372       /* Assume there is only one rtx object for any given label.  */
1373     case LABEL_REF:
1374       /* We don't hash on the address of the CODE_LABEL to avoid bootstrap
1375          differences and differences between each stage's debugging dumps.  */
1376       hash += ((unsigned) LABEL_REF << 7) + CODE_LABEL_NUMBER (XEXP (x, 0));
1377       return hash;
1378
1379     case SYMBOL_REF:
1380       {
1381         /* Don't hash on the symbol's address to avoid bootstrap differences.
1382            Different hash values may cause expressions to be recorded in
1383            different orders and thus different registers to be used in the
1384            final assembler.  This also avoids differences in the dump files
1385            between various stages.  */
1386         unsigned int h = 0;
1387         unsigned char *p = (unsigned char *) XSTR (x, 0);
1388         while (*p)
1389           h += (h << 7) + *p++; /* ??? revisit */
1390         hash += ((unsigned) SYMBOL_REF << 7) + h;
1391         return hash;
1392       }
1393
1394     case MEM:
1395       if (MEM_VOLATILE_P (x))
1396         {
1397           *do_not_record_p = 1;
1398           return 0;
1399         }
1400       hash += (unsigned) MEM;
1401       x = XEXP (x, 0);
1402       goto repeat;
1403
1404     case PRE_DEC:
1405     case PRE_INC:
1406     case POST_DEC:
1407     case POST_INC:
1408     case PC:
1409     case CC0:
1410     case CALL:
1411     case UNSPEC_VOLATILE:
1412       *do_not_record_p = 1;
1413       return 0;
1414
1415     case ASM_OPERANDS:
1416       if (MEM_VOLATILE_P (x))
1417         {
1418           *do_not_record_p = 1;
1419           return 0;
1420         }
1421
1422     default:
1423       break;
1424     }
1425
1426   i = GET_RTX_LENGTH (code) - 1;
1427   hash += (unsigned) code + (unsigned) GET_MODE (x);
1428   fmt = GET_RTX_FORMAT (code);
1429   for (; i >= 0; i--)
1430     {
1431       if (fmt[i] == 'e')
1432         {
1433           rtx tem = XEXP (x, i);
1434
1435           /* If we are about to do the last recursive call
1436              needed at this level, change it into iteration.
1437              This function is called enough to be worth it.  */
1438           if (i == 0)
1439             {
1440               x = tem;
1441               goto repeat;
1442             }
1443           hash += hash_expr_1 (tem, 0, do_not_record_p);
1444           if (*do_not_record_p)
1445             return 0;
1446         }
1447       else if (fmt[i] == 'E')
1448         for (j = 0; j < XVECLEN (x, i); j++)
1449           {
1450             hash += hash_expr_1 (XVECEXP (x, i, j), 0, do_not_record_p);
1451             if (*do_not_record_p)
1452               return 0;
1453           }
1454       else if (fmt[i] == 's')
1455         {
1456           register unsigned char *p = (unsigned char *) XSTR (x, i);
1457           if (p)
1458             while (*p)
1459               hash += *p++;
1460         }
1461       else if (fmt[i] == 'i')
1462         {
1463           register unsigned tem = XINT (x, i);
1464           hash += tem;
1465         }
1466       else
1467         abort ();
1468     }
1469
1470   return hash;
1471 }
1472
1473 /* Hash a set of register REGNO.
1474
1475    Sets are hashed on the register that is set.
1476    This simplifies the PRE copy propagation code.
1477
1478    ??? May need to make things more elaborate.  Later, as necessary.  */
1479
1480 static unsigned int
1481 hash_set (regno, hash_table_size)
1482      int regno;
1483      int hash_table_size;
1484 {
1485   unsigned int hash;
1486
1487   hash = regno;
1488   return hash % hash_table_size;
1489 }
1490
1491 /* Return non-zero if exp1 is equivalent to exp2.
1492    ??? Borrowed from cse.c.  Might want to remerge with cse.c.  Later.  */
1493
1494 static int
1495 expr_equiv_p (x, y)
1496      rtx x, y;
1497 {
1498   register int i, j;
1499   register enum rtx_code code;
1500   register const char *fmt;
1501
1502   if (x == y)
1503     return 1;
1504   if (x == 0 || y == 0)
1505     return x == y;
1506
1507   code = GET_CODE (x);
1508   if (code != GET_CODE (y))
1509     return 0;
1510
1511   /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent.  */
1512   if (GET_MODE (x) != GET_MODE (y))
1513     return 0;
1514
1515   switch (code)
1516     {
1517     case PC:
1518     case CC0:
1519       return x == y;
1520
1521     case CONST_INT:
1522       return INTVAL (x) == INTVAL (y);
1523
1524     case LABEL_REF:
1525       return XEXP (x, 0) == XEXP (y, 0);
1526
1527     case SYMBOL_REF:
1528       return XSTR (x, 0) == XSTR (y, 0);
1529
1530     case REG:
1531       return REGNO (x) == REGNO (y);
1532
1533     /*  For commutative operations, check both orders.  */
1534     case PLUS:
1535     case MULT:
1536     case AND:
1537     case IOR:
1538     case XOR:
1539     case NE:
1540     case EQ:
1541       return ((expr_equiv_p (XEXP (x, 0), XEXP (y, 0))
1542                && expr_equiv_p (XEXP (x, 1), XEXP (y, 1)))
1543               || (expr_equiv_p (XEXP (x, 0), XEXP (y, 1))
1544                   && expr_equiv_p (XEXP (x, 1), XEXP (y, 0))));
1545
1546     default:
1547       break;
1548     }
1549
1550   /* Compare the elements.  If any pair of corresponding elements
1551      fail to match, return 0 for the whole thing.  */
1552
1553   fmt = GET_RTX_FORMAT (code);
1554   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1555     {
1556       switch (fmt[i])
1557         {
1558         case 'e':
1559           if (! expr_equiv_p (XEXP (x, i), XEXP (y, i)))
1560             return 0;
1561           break;
1562
1563         case 'E':
1564           if (XVECLEN (x, i) != XVECLEN (y, i))
1565             return 0;
1566           for (j = 0; j < XVECLEN (x, i); j++)
1567             if (! expr_equiv_p (XVECEXP (x, i, j), XVECEXP (y, i, j)))
1568               return 0;
1569           break;
1570
1571         case 's':
1572           if (strcmp (XSTR (x, i), XSTR (y, i)))
1573             return 0;
1574           break;
1575
1576         case 'i':
1577           if (XINT (x, i) != XINT (y, i))
1578             return 0;
1579           break;
1580
1581         case 'w':
1582           if (XWINT (x, i) != XWINT (y, i))
1583             return 0;
1584         break;
1585
1586         case '0':
1587           break;
1588
1589         default:
1590           abort ();
1591         }
1592       }
1593
1594   return 1;
1595 }
1596
1597 /* Insert expression X in INSN in the hash table.
1598    If it is already present, record it as the last occurrence in INSN's
1599    basic block.
1600
1601    MODE is the mode of the value X is being stored into.
1602    It is only used if X is a CONST_INT.
1603
1604    ANTIC_P is non-zero if X is an anticipatable expression.
1605    AVAIL_P is non-zero if X is an available expression.  */
1606
1607 static void
1608 insert_expr_in_table (x, mode, insn, antic_p, avail_p)
1609      rtx x;
1610      enum machine_mode mode;
1611      rtx insn;
1612      int antic_p, avail_p;
1613 {
1614   int found, do_not_record_p;
1615   unsigned int hash;
1616   struct expr *cur_expr, *last_expr = NULL;
1617   struct occr *antic_occr, *avail_occr;
1618   struct occr *last_occr = NULL;
1619
1620   hash = hash_expr (x, mode, &do_not_record_p, expr_hash_table_size);
1621
1622   /* Do not insert expression in table if it contains volatile operands,
1623      or if hash_expr determines the expression is something we don't want
1624      to or can't handle.  */
1625   if (do_not_record_p)
1626     return;
1627
1628   cur_expr = expr_hash_table[hash];
1629   found = 0;
1630
1631   while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
1632     {
1633       /* If the expression isn't found, save a pointer to the end of
1634          the list.  */
1635       last_expr = cur_expr;
1636       cur_expr = cur_expr->next_same_hash;
1637     }
1638
1639   if (! found)
1640     {
1641       cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
1642       bytes_used += sizeof (struct expr);
1643       if (expr_hash_table[hash] == NULL)
1644         {
1645           /* This is the first pattern that hashed to this index.  */
1646           expr_hash_table[hash] = cur_expr;
1647         }
1648       else
1649         {
1650           /* Add EXPR to end of this hash chain.  */
1651           last_expr->next_same_hash = cur_expr;
1652         }
1653       /* Set the fields of the expr element.  */
1654       cur_expr->expr = x;
1655       cur_expr->bitmap_index = n_exprs++;
1656       cur_expr->next_same_hash = NULL;
1657       cur_expr->antic_occr = NULL;
1658       cur_expr->avail_occr = NULL;
1659     }
1660
1661   /* Now record the occurrence(s).  */
1662
1663   if (antic_p)
1664     {
1665       antic_occr = cur_expr->antic_occr;
1666
1667       /* Search for another occurrence in the same basic block.  */
1668       while (antic_occr && BLOCK_NUM (antic_occr->insn) != BLOCK_NUM (insn))
1669         {
1670           /* If an occurrence isn't found, save a pointer to the end of
1671              the list.  */
1672           last_occr = antic_occr;
1673           antic_occr = antic_occr->next;
1674         }
1675
1676       if (antic_occr)
1677         {
1678           /* Found another instance of the expression in the same basic block.
1679              Prefer the currently recorded one.  We want the first one in the
1680              block and the block is scanned from start to end.  */
1681           ; /* nothing to do */
1682         }
1683       else
1684         {
1685           /* First occurrence of this expression in this basic block.  */
1686           antic_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1687           bytes_used += sizeof (struct occr);
1688           /* First occurrence of this expression in any block?  */
1689           if (cur_expr->antic_occr == NULL)
1690             cur_expr->antic_occr = antic_occr;
1691           else
1692             last_occr->next = antic_occr;
1693           antic_occr->insn = insn;
1694           antic_occr->next = NULL;
1695         }
1696     }
1697
1698   if (avail_p)
1699     {
1700       avail_occr = cur_expr->avail_occr;
1701
1702       /* Search for another occurrence in the same basic block.  */
1703       while (avail_occr && BLOCK_NUM (avail_occr->insn) != BLOCK_NUM (insn))
1704         {
1705           /* If an occurrence isn't found, save a pointer to the end of
1706              the list.  */
1707           last_occr = avail_occr;
1708           avail_occr = avail_occr->next;
1709         }
1710
1711       if (avail_occr)
1712         {
1713           /* Found another instance of the expression in the same basic block.
1714              Prefer this occurrence to the currently recorded one.  We want
1715              the last one in the block and the block is scanned from start
1716              to end.  */
1717           avail_occr->insn = insn;
1718         }
1719       else
1720         {
1721           /* First occurrence of this expression in this basic block.  */
1722           avail_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1723           bytes_used += sizeof (struct occr);
1724           /* First occurrence of this expression in any block?  */
1725           if (cur_expr->avail_occr == NULL)
1726             cur_expr->avail_occr = avail_occr;
1727           else
1728             last_occr->next = avail_occr;
1729           avail_occr->insn = insn;
1730           avail_occr->next = NULL;
1731         }
1732     }
1733 }
1734
1735 /* Insert pattern X in INSN in the hash table.
1736    X is a SET of a reg to either another reg or a constant.
1737    If it is already present, record it as the last occurrence in INSN's
1738    basic block.  */
1739
1740 static void
1741 insert_set_in_table (x, insn)
1742      rtx x;
1743      rtx insn;
1744 {
1745   int found;
1746   unsigned int hash;
1747   struct expr *cur_expr, *last_expr = NULL;
1748   struct occr *cur_occr, *last_occr = NULL;
1749
1750   if (GET_CODE (x) != SET
1751       || GET_CODE (SET_DEST (x)) != REG)
1752     abort ();
1753
1754   hash = hash_set (REGNO (SET_DEST (x)), set_hash_table_size);
1755
1756   cur_expr = set_hash_table[hash];
1757   found = 0;
1758
1759   while (cur_expr && ! (found = expr_equiv_p (cur_expr->expr, x)))
1760     {
1761       /* If the expression isn't found, save a pointer to the end of
1762          the list.  */
1763       last_expr = cur_expr;
1764       cur_expr = cur_expr->next_same_hash;
1765     }
1766
1767   if (! found)
1768     {
1769       cur_expr = (struct expr *) gcse_alloc (sizeof (struct expr));
1770       bytes_used += sizeof (struct expr);
1771       if (set_hash_table[hash] == NULL)
1772         {
1773           /* This is the first pattern that hashed to this index.  */
1774           set_hash_table[hash] = cur_expr;
1775         }
1776       else
1777         {
1778           /* Add EXPR to end of this hash chain.  */
1779           last_expr->next_same_hash = cur_expr;
1780         }
1781       /* Set the fields of the expr element.
1782          We must copy X because it can be modified when copy propagation is
1783          performed on its operands.  */
1784       /* ??? Should this go in a different obstack?  */
1785       cur_expr->expr = copy_rtx (x);
1786       cur_expr->bitmap_index = n_sets++;
1787       cur_expr->next_same_hash = NULL;
1788       cur_expr->antic_occr = NULL;
1789       cur_expr->avail_occr = NULL;
1790     }
1791
1792   /* Now record the occurrence.  */
1793
1794   cur_occr = cur_expr->avail_occr;
1795
1796   /* Search for another occurrence in the same basic block.  */
1797   while (cur_occr && BLOCK_NUM (cur_occr->insn) != BLOCK_NUM (insn))
1798     {
1799       /* If an occurrence isn't found, save a pointer to the end of
1800          the list.  */
1801       last_occr = cur_occr;
1802       cur_occr = cur_occr->next;
1803     }
1804
1805   if (cur_occr)
1806     {
1807       /* Found another instance of the expression in the same basic block.
1808          Prefer this occurrence to the currently recorded one.  We want
1809          the last one in the block and the block is scanned from start
1810          to end.  */
1811       cur_occr->insn = insn;
1812     }
1813   else
1814     {
1815       /* First occurrence of this expression in this basic block.  */
1816       cur_occr = (struct occr *) gcse_alloc (sizeof (struct occr));
1817       bytes_used += sizeof (struct occr);
1818       /* First occurrence of this expression in any block?  */
1819       if (cur_expr->avail_occr == NULL)
1820         cur_expr->avail_occr = cur_occr;
1821       else
1822         last_occr->next = cur_occr;
1823       cur_occr->insn = insn;
1824       cur_occr->next = NULL;
1825     }
1826 }
1827
1828 /* Scan pattern PAT of INSN and add an entry to the hash table.
1829    If SET_P is non-zero, this is for the assignment hash table,
1830    otherwise it is for the expression hash table.  */
1831
1832 static void
1833 hash_scan_set (pat, insn, set_p)
1834      rtx pat, insn;
1835      int set_p;
1836 {
1837   rtx src = SET_SRC (pat);
1838   rtx dest = SET_DEST (pat);
1839
1840   if (GET_CODE (src) == CALL)
1841     hash_scan_call (src, insn);
1842
1843   if (GET_CODE (dest) == REG)
1844     {
1845       int regno = REGNO (dest);
1846       rtx tmp;
1847
1848       /* Only record sets of pseudo-regs in the hash table.  */
1849       if (! set_p
1850           && regno >= FIRST_PSEUDO_REGISTER
1851           /* Don't GCSE something if we can't do a reg/reg copy.  */
1852           && can_copy_p [GET_MODE (dest)]
1853           /* Is SET_SRC something we want to gcse?  */
1854           && want_to_gcse_p (src))
1855         {
1856           /* An expression is not anticipatable if its operands are
1857              modified before this insn.  */
1858           int antic_p = ! optimize_size && oprs_anticipatable_p (src, insn);
1859           /* An expression is not available if its operands are
1860              subsequently modified, including this insn.  */
1861           int avail_p = oprs_available_p (src, insn);
1862           insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p);
1863         }
1864       /* Record sets for constant/copy propagation.  */
1865       else if (set_p
1866                && regno >= FIRST_PSEUDO_REGISTER
1867                && ((GET_CODE (src) == REG
1868                     && REGNO (src) >= FIRST_PSEUDO_REGISTER
1869                     && can_copy_p [GET_MODE (dest)])
1870                    || GET_CODE (src) == CONST_INT
1871                    || GET_CODE (src) == SYMBOL_REF
1872                    || GET_CODE (src) == CONST_DOUBLE)
1873                /* A copy is not available if its src or dest is subsequently
1874                   modified.  Here we want to search from INSN+1 on, but
1875                   oprs_available_p searches from INSN on.  */
1876                && (insn == BLOCK_END (BLOCK_NUM (insn))
1877                    || ((tmp = next_nonnote_insn (insn)) != NULL_RTX
1878                        && oprs_available_p (pat, tmp))))
1879         insert_set_in_table (pat, insn);
1880     }
1881 }
1882
1883 static void
1884 hash_scan_clobber (x, insn)
1885      rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
1886 {
1887   /* Currently nothing to do.  */
1888 }
1889
1890 static void
1891 hash_scan_call (x, insn)
1892      rtx x ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
1893 {
1894   /* Currently nothing to do.  */
1895 }
1896
1897 /* Process INSN and add hash table entries as appropriate.
1898
1899    Only available expressions that set a single pseudo-reg are recorded.
1900
1901    Single sets in a PARALLEL could be handled, but it's an extra complication
1902    that isn't dealt with right now.  The trick is handling the CLOBBERs that
1903    are also in the PARALLEL.  Later.
1904
1905    If SET_P is non-zero, this is for the assignment hash table,
1906    otherwise it is for the expression hash table.
1907    If IN_LIBCALL_BLOCK nonzero, we are in a libcall block, and should
1908    not record any expressions.  */
1909
1910 static void
1911 hash_scan_insn (insn, set_p, in_libcall_block)
1912      rtx insn;
1913      int set_p;
1914      int in_libcall_block;
1915 {
1916   rtx pat = PATTERN (insn);
1917
1918   /* Pick out the sets of INSN and for other forms of instructions record
1919      what's been modified.  */
1920
1921   if (GET_CODE (pat) == SET && ! in_libcall_block)
1922     hash_scan_set (pat, insn, set_p);
1923   else if (GET_CODE (pat) == PARALLEL)
1924     {
1925       int i;
1926
1927       for (i = 0; i < XVECLEN (pat, 0); i++)
1928         {
1929           rtx x = XVECEXP (pat, 0, i);
1930
1931           if (GET_CODE (x) == SET)
1932             {
1933               if (GET_CODE (SET_SRC (x)) == CALL)
1934                 hash_scan_call (SET_SRC (x), insn);
1935             }
1936           else if (GET_CODE (x) == CLOBBER)
1937             hash_scan_clobber (x, insn);
1938           else if (GET_CODE (x) == CALL)
1939             hash_scan_call (x, insn);
1940         }
1941     }
1942   else if (GET_CODE (pat) == CLOBBER)
1943     hash_scan_clobber (pat, insn);
1944   else if (GET_CODE (pat) == CALL)
1945     hash_scan_call (pat, insn);
1946 }
1947
1948 static void
1949 dump_hash_table (file, name, table, table_size, total_size)
1950      FILE *file;
1951      const char *name;
1952      struct expr **table;
1953      int table_size, total_size;
1954 {
1955   int i;
1956   /* Flattened out table, so it's printed in proper order.  */
1957   struct expr **flat_table = (struct expr **) alloca (total_size * sizeof (struct expr *));
1958   unsigned int *hash_val = (unsigned int *) alloca (total_size * sizeof (unsigned int));
1959
1960   bzero ((char *) flat_table, total_size * sizeof (struct expr *));
1961   for (i = 0; i < table_size; i++)
1962     {
1963       struct expr *expr;
1964
1965       for (expr = table[i]; expr != NULL; expr = expr->next_same_hash)
1966         {
1967           flat_table[expr->bitmap_index] = expr;
1968           hash_val[expr->bitmap_index] = i;
1969         }
1970     }
1971
1972   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
1973            name, table_size, total_size);
1974
1975   for (i = 0; i < total_size; i++)
1976     {
1977       struct expr *expr = flat_table[i];
1978
1979       fprintf (file, "Index %d (hash value %d)\n  ",
1980                expr->bitmap_index, hash_val[i]);
1981       print_rtl (file, expr->expr);
1982       fprintf (file, "\n");
1983     }
1984
1985   fprintf (file, "\n");
1986 }
1987
1988 /* Record register first/last/block set information for REGNO in INSN.
1989    reg_first_set records the first place in the block where the register
1990    is set and is used to compute "anticipatability".
1991    reg_last_set records the last place in the block where the register
1992    is set and is used to compute "availability".
1993    reg_set_in_block records whether the register is set in the block
1994    and is used to compute "transparency".  */
1995
1996 static void
1997 record_last_reg_set_info (insn, regno)
1998      rtx insn;
1999      int regno;
2000 {
2001   if (reg_first_set[regno] == NEVER_SET)
2002     reg_first_set[regno] = INSN_CUID (insn);
2003   reg_last_set[regno] = INSN_CUID (insn);
2004   SET_BIT (reg_set_in_block[BLOCK_NUM (insn)], regno);
2005 }
2006
2007 /* Record memory first/last/block set information for INSN.  */
2008
2009 static void
2010 record_last_mem_set_info (insn)
2011      rtx insn;
2012 {
2013   if (mem_first_set == NEVER_SET)
2014     mem_first_set = INSN_CUID (insn);
2015   mem_last_set = INSN_CUID (insn);
2016   mem_set_in_block[BLOCK_NUM (insn)] = 1;
2017 }
2018
2019 /* Used for communicating between next two routines.  */
2020 static rtx last_set_insn;
2021
2022 /* Called from compute_hash_table via note_stores to handle one
2023    SET or CLOBBER in an insn.  */
2024
2025 static void
2026 record_last_set_info (dest, setter)
2027      rtx dest, setter ATTRIBUTE_UNUSED;
2028 {
2029   if (GET_CODE (dest) == SUBREG)
2030     dest = SUBREG_REG (dest);
2031
2032   if (GET_CODE (dest) == REG)
2033     record_last_reg_set_info (last_set_insn, REGNO (dest));
2034   else if (GET_CODE (dest) == MEM
2035            /* Ignore pushes, they clobber nothing.  */
2036            && ! push_operand (dest, GET_MODE (dest)))
2037     record_last_mem_set_info (last_set_insn);
2038 }
2039
2040 /* Top level function to create an expression or assignment hash table.
2041
2042    Expression entries are placed in the hash table if
2043    - they are of the form (set (pseudo-reg) src),
2044    - src is something we want to perform GCSE on,
2045    - none of the operands are subsequently modified in the block
2046
2047    Assignment entries are placed in the hash table if
2048    - they are of the form (set (pseudo-reg) src),
2049    - src is something we want to perform const/copy propagation on,
2050    - none of the operands or target are subsequently modified in the block
2051    Currently src must be a pseudo-reg or a const_int.
2052
2053    F is the first insn.
2054    SET_P is non-zero for computing the assignment hash table.  */
2055
2056 static void
2057 compute_hash_table (set_p)
2058      int set_p;
2059 {
2060   int bb;
2061
2062   /* While we compute the hash table we also compute a bit array of which
2063      registers are set in which blocks.
2064      We also compute which blocks set memory, in the absence of aliasing
2065      support [which is TODO].
2066      ??? This isn't needed during const/copy propagation, but it's cheap to
2067      compute.  Later.  */
2068   sbitmap_vector_zero (reg_set_in_block, n_basic_blocks);
2069   bzero ((char *) mem_set_in_block, n_basic_blocks);
2070
2071   /* Some working arrays used to track first and last set in each block.  */
2072   /* ??? One could use alloca here, but at some size a threshold is crossed
2073      beyond which one should use malloc.  Are we at that threshold here?  */
2074   reg_first_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
2075   reg_last_set = (int *) gmalloc (max_gcse_regno * sizeof (int));
2076
2077   for (bb = 0; bb < n_basic_blocks; bb++)
2078     {
2079       rtx insn;
2080       int regno;
2081       int in_libcall_block;
2082       int i;
2083
2084       /* First pass over the instructions records information used to
2085          determine when registers and memory are first and last set.
2086          ??? The mem_set_in_block and hard-reg reg_set_in_block computation
2087          could be moved to compute_sets since they currently don't change.  */
2088
2089       for (i = 0; i < max_gcse_regno; i++)
2090         reg_first_set[i] = reg_last_set[i] = NEVER_SET;
2091       mem_first_set = NEVER_SET;
2092       mem_last_set = NEVER_SET;
2093
2094       for (insn = BLOCK_HEAD (bb);
2095            insn && insn != NEXT_INSN (BLOCK_END (bb));
2096            insn = NEXT_INSN (insn))
2097         {
2098 #ifdef NON_SAVING_SETJMP
2099           if (NON_SAVING_SETJMP && GET_CODE (insn) == NOTE
2100               && NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP)
2101             {
2102               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2103                 record_last_reg_set_info (insn, regno);
2104               continue;
2105             }
2106 #endif
2107
2108           if (GET_RTX_CLASS (GET_CODE (insn)) != 'i')
2109             continue;
2110
2111           if (GET_CODE (insn) == CALL_INSN)
2112             {
2113               for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2114                 if ((call_used_regs[regno]
2115                      && regno != STACK_POINTER_REGNUM
2116 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2117                      && regno != HARD_FRAME_POINTER_REGNUM
2118 #endif
2119 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2120                      && ! (regno == ARG_POINTER_REGNUM && fixed_regs[regno])
2121 #endif
2122 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2123                      && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2124 #endif
2125
2126                      && regno != FRAME_POINTER_REGNUM)
2127                     || global_regs[regno])
2128                   record_last_reg_set_info (insn, regno);
2129               if (! CONST_CALL_P (insn))
2130                 record_last_mem_set_info (insn);
2131             }
2132
2133           last_set_insn = insn;
2134           note_stores (PATTERN (insn), record_last_set_info);
2135         }
2136
2137       /* The next pass builds the hash table.  */
2138
2139       for (insn = BLOCK_HEAD (bb), in_libcall_block = 0;
2140            insn && insn != NEXT_INSN (BLOCK_END (bb));
2141            insn = NEXT_INSN (insn))
2142         {
2143           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
2144             {
2145               if (find_reg_note (insn, REG_LIBCALL, NULL_RTX))
2146                 in_libcall_block = 1;
2147               else if (find_reg_note (insn, REG_RETVAL, NULL_RTX))
2148                 in_libcall_block = 0;
2149               hash_scan_insn (insn, set_p, in_libcall_block);
2150             }
2151         }
2152     }
2153
2154   free (reg_first_set);
2155   free (reg_last_set);
2156   /* Catch bugs early.  */
2157   reg_first_set = reg_last_set = 0;
2158 }
2159
2160 /* Allocate space for the set hash table.
2161    N_INSNS is the number of instructions in the function.
2162    It is used to determine the number of buckets to use.  */
2163
2164 static void
2165 alloc_set_hash_table (n_insns)
2166      int n_insns;
2167 {
2168   int n;
2169
2170   set_hash_table_size = n_insns / 4;
2171   if (set_hash_table_size < 11)
2172     set_hash_table_size = 11;
2173   /* Attempt to maintain efficient use of hash table.
2174      Making it an odd number is simplest for now.
2175      ??? Later take some measurements.  */
2176   set_hash_table_size |= 1;
2177   n = set_hash_table_size * sizeof (struct expr *);
2178   set_hash_table = (struct expr **) gmalloc (n);
2179 }
2180
2181 /* Free things allocated by alloc_set_hash_table.  */
2182
2183 static void
2184 free_set_hash_table ()
2185 {
2186   free (set_hash_table);
2187 }
2188
2189 /* Compute the hash table for doing copy/const propagation.  */
2190
2191 static void
2192 compute_set_hash_table ()
2193 {
2194   /* Initialize count of number of entries in hash table.  */
2195   n_sets = 0;
2196   bzero ((char *) set_hash_table, set_hash_table_size * sizeof (struct expr *));
2197
2198   compute_hash_table (1);
2199 }
2200
2201 /* Allocate space for the expression hash table.
2202    N_INSNS is the number of instructions in the function.
2203    It is used to determine the number of buckets to use.  */
2204
2205 static void
2206 alloc_expr_hash_table (n_insns)
2207      int n_insns;
2208 {
2209   int n;
2210
2211   expr_hash_table_size = n_insns / 2;
2212   /* Make sure the amount is usable.  */
2213   if (expr_hash_table_size < 11)
2214     expr_hash_table_size = 11;
2215   /* Attempt to maintain efficient use of hash table.
2216      Making it an odd number is simplest for now.
2217      ??? Later take some measurements.  */
2218   expr_hash_table_size |= 1;
2219   n = expr_hash_table_size * sizeof (struct expr *);
2220   expr_hash_table = (struct expr **) gmalloc (n);
2221 }
2222
2223 /* Free things allocated by alloc_expr_hash_table.  */
2224
2225 static void
2226 free_expr_hash_table ()
2227 {
2228   free (expr_hash_table);
2229 }
2230
2231 /* Compute the hash table for doing GCSE.  */
2232
2233 static void
2234 compute_expr_hash_table ()
2235 {
2236   /* Initialize count of number of entries in hash table.  */
2237   n_exprs = 0;
2238   bzero ((char *) expr_hash_table, expr_hash_table_size * sizeof (struct expr *));
2239
2240   compute_hash_table (0);
2241 }
2242 \f
2243 /* Expression tracking support.  */
2244
2245 /* Lookup pattern PAT in the expression table.
2246    The result is a pointer to the table entry, or NULL if not found.  */
2247
2248 static struct expr *
2249 lookup_expr (pat)
2250      rtx pat;
2251 {
2252   int do_not_record_p;
2253   unsigned int hash = hash_expr (pat, GET_MODE (pat), &do_not_record_p,
2254                                  expr_hash_table_size);
2255   struct expr *expr;
2256
2257   if (do_not_record_p)
2258     return NULL;
2259
2260   expr = expr_hash_table[hash];
2261
2262   while (expr && ! expr_equiv_p (expr->expr, pat))
2263     expr = expr->next_same_hash;
2264
2265   return expr;
2266 }
2267
2268 /* Lookup REGNO in the set table.
2269    If PAT is non-NULL look for the entry that matches it, otherwise return
2270    the first entry for REGNO.
2271    The result is a pointer to the table entry, or NULL if not found.  */
2272
2273 static struct expr *
2274 lookup_set (regno, pat)
2275      int regno;
2276      rtx pat;
2277 {
2278   unsigned int hash = hash_set (regno, set_hash_table_size);
2279   struct expr *expr;
2280
2281   expr = set_hash_table[hash];
2282
2283   if (pat)
2284     {
2285       while (expr && ! expr_equiv_p (expr->expr, pat))
2286         expr = expr->next_same_hash;
2287     }
2288   else
2289     {
2290       while (expr && REGNO (SET_DEST (expr->expr)) != regno)
2291         expr = expr->next_same_hash;
2292     }
2293
2294   return expr;
2295 }
2296
2297 /* Return the next entry for REGNO in list EXPR.  */
2298
2299 static struct expr *
2300 next_set (regno, expr)
2301      int regno;
2302      struct expr *expr;
2303 {
2304   do
2305     expr = expr->next_same_hash;
2306   while (expr && REGNO (SET_DEST (expr->expr)) != regno);
2307   return expr;
2308 }
2309
2310 /* Reset tables used to keep track of what's still available [since the
2311    start of the block].  */
2312
2313 static void
2314 reset_opr_set_tables ()
2315 {
2316   /* Maintain a bitmap of which regs have been set since beginning of
2317      the block.  */
2318   sbitmap_zero (reg_set_bitmap);
2319   /* Also keep a record of the last instruction to modify memory.
2320      For now this is very trivial, we only record whether any memory
2321      location has been modified.  */
2322   mem_last_set = 0;
2323 }
2324
2325 /* Return non-zero if the operands of X are not set before INSN in
2326    INSN's basic block.  */
2327
2328 static int
2329 oprs_not_set_p (x, insn)
2330      rtx x, insn;
2331 {
2332   int i;
2333   enum rtx_code code;
2334   const char *fmt;
2335
2336   /* repeat is used to turn tail-recursion into iteration.  */
2337 repeat:
2338
2339   if (x == 0)
2340     return 1;
2341
2342   code = GET_CODE (x);
2343   switch (code)
2344     {
2345     case PC:
2346     case CC0:
2347     case CONST:
2348     case CONST_INT:
2349     case CONST_DOUBLE:
2350     case SYMBOL_REF:
2351     case LABEL_REF:
2352     case ADDR_VEC:
2353     case ADDR_DIFF_VEC:
2354       return 1;
2355
2356     case MEM:
2357       if (mem_last_set != 0)
2358         return 0;
2359       x = XEXP (x, 0);
2360       goto repeat;
2361
2362     case REG:
2363       return ! TEST_BIT (reg_set_bitmap, REGNO (x));
2364
2365     default:
2366       break;
2367     }
2368
2369   fmt = GET_RTX_FORMAT (code);
2370   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
2371     {
2372       if (fmt[i] == 'e')
2373         {
2374           int not_set_p;
2375           /* If we are about to do the last recursive call
2376              needed at this level, change it into iteration.
2377              This function is called enough to be worth it.  */
2378           if (i == 0)
2379             {
2380               x = XEXP (x, 0);
2381               goto repeat;
2382             }
2383           not_set_p = oprs_not_set_p (XEXP (x, i), insn);
2384           if (! not_set_p)
2385             return 0;
2386         }
2387       else if (fmt[i] == 'E')
2388         {
2389           int j;
2390           for (j = 0; j < XVECLEN (x, i); j++)
2391             {
2392               int not_set_p = oprs_not_set_p (XVECEXP (x, i, j), insn);
2393               if (! not_set_p)
2394                 return 0;
2395             }
2396         }
2397     }
2398
2399   return 1;
2400 }
2401
2402 /* Mark things set by a CALL.  */
2403
2404 static void
2405 mark_call (insn)
2406      rtx insn;
2407 {
2408   mem_last_set = INSN_CUID (insn);
2409 }
2410
2411 /* Mark things set by a SET.  */
2412
2413 static void
2414 mark_set (pat, insn)
2415      rtx pat, insn;
2416 {
2417   rtx dest = SET_DEST (pat);
2418
2419   while (GET_CODE (dest) == SUBREG
2420          || GET_CODE (dest) == ZERO_EXTRACT
2421          || GET_CODE (dest) == SIGN_EXTRACT
2422          || GET_CODE (dest) == STRICT_LOW_PART)
2423     dest = XEXP (dest, 0);
2424
2425   if (GET_CODE (dest) == REG)
2426     SET_BIT (reg_set_bitmap, REGNO (dest));
2427   else if (GET_CODE (dest) == MEM)
2428     mem_last_set = INSN_CUID (insn);
2429
2430   if (GET_CODE (SET_SRC (pat)) == CALL)
2431     mark_call (insn);
2432 }
2433
2434 /* Record things set by a CLOBBER.  */
2435
2436 static void
2437 mark_clobber (pat, insn)
2438      rtx pat, insn;
2439 {
2440   rtx clob = XEXP (pat, 0);
2441
2442   while (GET_CODE (clob) == SUBREG || GET_CODE (clob) == STRICT_LOW_PART)
2443     clob = XEXP (clob, 0);
2444
2445   if (GET_CODE (clob) == REG)
2446     SET_BIT (reg_set_bitmap, REGNO (clob));
2447   else
2448     mem_last_set = INSN_CUID (insn);
2449 }
2450
2451 /* Record things set by INSN.
2452    This data is used by oprs_not_set_p.  */
2453
2454 static void
2455 mark_oprs_set (insn)
2456      rtx insn;
2457 {
2458   rtx pat = PATTERN (insn);
2459
2460   if (GET_CODE (pat) == SET)
2461     mark_set (pat, insn);
2462   else if (GET_CODE (pat) == PARALLEL)
2463     {
2464       int i;
2465
2466       for (i = 0; i < XVECLEN (pat, 0); i++)
2467         {
2468           rtx x = XVECEXP (pat, 0, i);
2469
2470           if (GET_CODE (x) == SET)
2471             mark_set (x, insn);
2472           else if (GET_CODE (x) == CLOBBER)
2473             mark_clobber (x, insn);
2474           else if (GET_CODE (x) == CALL)
2475             mark_call (insn);
2476         }
2477     }
2478   else if (GET_CODE (pat) == CLOBBER)
2479     mark_clobber (pat, insn);
2480   else if (GET_CODE (pat) == CALL)
2481     mark_call (insn);
2482 }
2483
2484 \f
2485 /* Classic GCSE reaching definition support.  */
2486
2487 /* Allocate reaching def variables.  */
2488
2489 static void
2490 alloc_rd_mem (n_blocks, n_insns)
2491      int n_blocks, n_insns;
2492 {
2493   rd_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2494   sbitmap_vector_zero (rd_kill, n_basic_blocks);
2495
2496   rd_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2497   sbitmap_vector_zero (rd_gen, n_basic_blocks);
2498
2499   reaching_defs = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2500   sbitmap_vector_zero (reaching_defs, n_basic_blocks);
2501
2502   rd_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_insns);
2503   sbitmap_vector_zero (rd_out, n_basic_blocks);
2504 }
2505
2506 /* Free reaching def variables.  */
2507
2508 static void
2509 free_rd_mem ()
2510 {
2511   free (rd_kill);
2512   free (rd_gen);
2513   free (reaching_defs);
2514   free (rd_out);
2515 }
2516
2517 /* Add INSN to the kills of BB.
2518    REGNO, set in BB, is killed by INSN.  */
2519
2520 static void
2521 handle_rd_kill_set (insn, regno, bb)
2522      rtx insn;
2523      int regno, bb;
2524 {
2525   struct reg_set *this_reg = reg_set_table[regno];
2526
2527   while (this_reg)
2528     {
2529       if (BLOCK_NUM (this_reg->insn) != BLOCK_NUM (insn))
2530         SET_BIT (rd_kill[bb], INSN_CUID (this_reg->insn));
2531       this_reg = this_reg->next;
2532     }
2533 }
2534
2535 /* Compute the set of kill's for reaching definitions.  */
2536
2537 static void
2538 compute_kill_rd ()
2539 {
2540   int bb,cuid;
2541
2542   /* For each block
2543        For each set bit in `gen' of the block (i.e each insn which
2544            generates a definition in the block)
2545          Call the reg set by the insn corresponding to that bit regx
2546          Look at the linked list starting at reg_set_table[regx]
2547          For each setting of regx in the linked list, which is not in
2548              this block
2549            Set the bit in `kill' corresponding to that insn
2550     */
2551
2552   for (bb = 0; bb < n_basic_blocks; bb++)
2553     {
2554       for (cuid = 0; cuid < max_cuid; cuid++)
2555         {
2556           if (TEST_BIT (rd_gen[bb], cuid))
2557             {
2558               rtx insn = CUID_INSN (cuid);
2559               rtx pat = PATTERN (insn);
2560
2561               if (GET_CODE (insn) == CALL_INSN)
2562                 {
2563                   int regno;
2564
2565                   for (regno = 0; regno < FIRST_PSEUDO_REGISTER; regno++)
2566                     {
2567                       if ((call_used_regs[regno]
2568                            && regno != STACK_POINTER_REGNUM
2569 #if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM
2570                            && regno != HARD_FRAME_POINTER_REGNUM
2571 #endif
2572 #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2573                            && ! (regno == ARG_POINTER_REGNUM
2574                                  && fixed_regs[regno])
2575 #endif
2576 #if defined (PIC_OFFSET_TABLE_REGNUM) && !defined (PIC_OFFSET_TABLE_REG_CALL_CLOBBERED)
2577                            && ! (regno == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2578 #endif
2579                            && regno != FRAME_POINTER_REGNUM)
2580                           || global_regs[regno])
2581                         handle_rd_kill_set (insn, regno, bb);
2582                     }
2583                 }
2584
2585               if (GET_CODE (pat) == PARALLEL)
2586                 {
2587                   int i;
2588
2589                   /* We work backwards because ... */
2590                   for (i = XVECLEN (pat, 0) - 1; i >= 0; i--)
2591                     {
2592                       enum rtx_code code = GET_CODE (XVECEXP (pat, 0, i));
2593                       if ((code == SET || code == CLOBBER)
2594                           && GET_CODE (XEXP (XVECEXP (pat, 0, i), 0)) == REG)
2595                         handle_rd_kill_set (insn,
2596                                             REGNO (XEXP (XVECEXP (pat, 0, i), 0)),
2597                                             bb);
2598                     }
2599                 }
2600               else if (GET_CODE (pat) == SET)
2601                 {
2602                   if (GET_CODE (SET_DEST (pat)) == REG)
2603                     {
2604                       /* Each setting of this register outside of this block
2605                          must be marked in the set of kills in this block.  */
2606                       handle_rd_kill_set (insn, REGNO (SET_DEST (pat)), bb);
2607                     }
2608                 }
2609               /* FIXME: CLOBBER? */
2610             }
2611         }
2612     }
2613 }
2614
2615 /* Compute the reaching definitions as in
2616    Compilers Principles, Techniques, and Tools. Aho, Sethi, Ullman,
2617    Chapter 10.  It is the same algorithm as used for computing available
2618    expressions but applied to the gens and kills of reaching definitions.  */
2619
2620 static void
2621 compute_rd ()
2622 {
2623   int bb, changed, passes;
2624
2625   for (bb = 0; bb < n_basic_blocks; bb++)
2626     sbitmap_copy (rd_out[bb] /*dst*/, rd_gen[bb] /*src*/);
2627
2628   passes = 0;
2629   changed = 1;
2630   while (changed)
2631     {
2632       changed = 0;
2633       for (bb = 0; bb < n_basic_blocks; bb++)
2634         {
2635           sbitmap_union_of_predecessors (reaching_defs[bb], rd_out,
2636                                          bb, s_preds);
2637           changed |= sbitmap_union_of_diff (rd_out[bb], rd_gen[bb],
2638                                             reaching_defs[bb], rd_kill[bb]);
2639         }
2640       passes++;
2641     }
2642
2643   if (gcse_file)
2644     fprintf (gcse_file, "reaching def computation: %d passes\n", passes);
2645 }
2646 \f
2647 /* Classic GCSE available expression support.  */
2648
2649 /* Allocate memory for available expression computation.  */
2650
2651 static void
2652 alloc_avail_expr_mem (n_blocks, n_exprs)
2653      int n_blocks, n_exprs;
2654 {
2655   ae_kill = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2656   sbitmap_vector_zero (ae_kill, n_basic_blocks);
2657
2658   ae_gen = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2659   sbitmap_vector_zero (ae_gen, n_basic_blocks);
2660
2661   ae_in = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2662   sbitmap_vector_zero (ae_in, n_basic_blocks);
2663
2664   ae_out = (sbitmap *) sbitmap_vector_alloc (n_blocks, n_exprs);
2665   sbitmap_vector_zero (ae_out, n_basic_blocks);
2666
2667   u_bitmap = (sbitmap) sbitmap_alloc (n_exprs);
2668   sbitmap_ones (u_bitmap);
2669 }
2670
2671 static void
2672 free_avail_expr_mem ()
2673 {
2674   free (ae_kill);
2675   free (ae_gen);
2676   free (ae_in);
2677   free (ae_out);
2678   free (u_bitmap);
2679 }
2680
2681 /* Compute the set of available expressions generated in each basic block.  */
2682
2683 static void
2684 compute_ae_gen ()
2685 {
2686   int i;
2687
2688   /* For each recorded occurrence of each expression, set ae_gen[bb][expr].
2689      This is all we have to do because an expression is not recorded if it
2690      is not available, and the only expressions we want to work with are the
2691      ones that are recorded.  */
2692
2693   for (i = 0; i < expr_hash_table_size; i++)
2694     {
2695       struct expr *expr = expr_hash_table[i];
2696       while (expr != NULL)
2697         {
2698           struct occr *occr = expr->avail_occr;
2699           while (occr != NULL)
2700             {
2701               SET_BIT (ae_gen[BLOCK_NUM (occr->insn)], expr->bitmap_index);
2702               occr = occr->next;
2703             }
2704           expr = expr->next_same_hash;
2705         }
2706     }
2707 }
2708
2709 /* Return non-zero if expression X is killed in BB.  */
2710
2711 static int
2712 expr_killed_p (x, bb)
2713      rtx x;
2714      int bb;
2715 {
2716   int i;
2717   enum rtx_code code;
2718   const char *fmt;
2719
2720   /* repeat is used to turn tail-recursion into iteration.  */
2721  repeat:
2722
2723   if (x == 0)
2724     return 1;
2725
2726   code = GET_CODE (x);
2727   switch (code)
2728     {
2729     case REG:
2730       return TEST_BIT (reg_set_in_block[bb], REGNO (x));
2731
2732     case MEM:
2733       if (mem_set_in_block[bb])
2734         return 1;
2735       x = XEXP (x, 0);
2736       goto repeat;
2737
2738     case PC:
2739     case CC0: /*FIXME*/
2740     case CONST:
2741     case CONST_INT:
2742     case CONST_DOUBLE:
2743     case SYMBOL_REF:
2744     case LABEL_REF:
2745     case ADDR_VEC:
2746     case ADDR_DIFF_VEC:
2747       return 0;
2748
2749     default:
2750       break;
2751     }
2752
2753   i = GET_RTX_LENGTH (code) - 1;
2754   fmt = GET_RTX_FORMAT (code);
2755   for (; i >= 0; i--)
2756     {
2757       if (fmt[i] == 'e')
2758         {
2759           rtx tem = XEXP (x, i);
2760
2761           /* If we are about to do the last recursive call
2762              needed at this level, change it into iteration.
2763              This function is called enough to be worth it.  */
2764           if (i == 0)
2765             {
2766               x = tem;
2767               goto repeat;
2768             }
2769           if (expr_killed_p (tem, bb))
2770             return 1;
2771         }
2772       else if (fmt[i] == 'E')
2773         {
2774           int j;
2775           for (j = 0; j < XVECLEN (x, i); j++)
2776             {
2777               if (expr_killed_p (XVECEXP (x, i, j), bb))
2778                 return 1;
2779             }
2780         }
2781     }
2782
2783   return 0;
2784 }
2785
2786 /* Compute the set of available expressions killed in each basic block.  */
2787
2788 static void
2789 compute_ae_kill ()
2790 {
2791   int bb,i;
2792
2793   for (bb = 0; bb < n_basic_blocks; bb++)
2794     {
2795       for (i = 0; i < expr_hash_table_size; i++)
2796         {
2797           struct expr *expr = expr_hash_table[i];
2798
2799           for ( ; expr != NULL; expr = expr->next_same_hash)
2800             {
2801               /* Skip EXPR if generated in this block.  */
2802               if (TEST_BIT (ae_gen[bb], expr->bitmap_index))
2803                 continue;
2804
2805               if (expr_killed_p (expr->expr, bb))
2806                 SET_BIT (ae_kill[bb], expr->bitmap_index);
2807             }
2808         }
2809     }
2810 }
2811
2812 /* Compute available expressions.
2813
2814    Implement the algorithm to find available expressions
2815    as given in the Aho Sethi Ullman book, pages 627-631.  */
2816
2817 static void
2818 compute_available ()
2819 {
2820   int bb, changed, passes;
2821
2822   sbitmap_zero (ae_in[0]);
2823
2824   sbitmap_copy (ae_out[0] /*dst*/, ae_gen[0] /*src*/);
2825
2826   for (bb = 1; bb < n_basic_blocks; bb++)
2827     sbitmap_difference (ae_out[bb], u_bitmap, ae_kill[bb]);
2828
2829   passes = 0;
2830   changed = 1;
2831   while (changed)
2832     {
2833       changed = 0;
2834       for (bb = 1; bb < n_basic_blocks; bb++)
2835         {
2836           sbitmap_intersect_of_predecessors (ae_in[bb], ae_out, bb, s_preds);
2837           changed |= sbitmap_union_of_diff (ae_out[bb], ae_gen[bb],
2838                                             ae_in[bb], ae_kill[bb]);
2839         }
2840       passes++;
2841     }
2842
2843   if (gcse_file)
2844     fprintf (gcse_file, "avail expr computation: %d passes\n", passes);
2845 }
2846 \f
2847 /* Actually perform the Classic GCSE optimizations.  */
2848
2849 /* Return non-zero if occurrence OCCR of expression EXPR reaches block BB.
2850
2851    CHECK_SELF_LOOP is non-zero if we should consider a block reaching itself
2852    as a positive reach.  We want to do this when there are two computations
2853    of the expression in the block.
2854
2855    VISITED is a pointer to a working buffer for tracking which BB's have
2856    been visited.  It is NULL for the top-level call.
2857
2858    We treat reaching expressions that go through blocks containing the same
2859    reaching expression as "not reaching".  E.g. if EXPR is generated in blocks
2860    2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
2861    2 as not reaching.  The intent is to improve the probability of finding
2862    only one reaching expression and to reduce register lifetimes by picking
2863    the closest such expression.  */
2864
2865 static int
2866 expr_reaches_here_p (occr, expr, bb, check_self_loop, visited)
2867      struct occr *occr;
2868      struct expr *expr;
2869      int bb;
2870      int check_self_loop;
2871      char *visited;
2872 {
2873   int_list_ptr pred;
2874
2875   if (visited == NULL)
2876     {
2877       visited = (char *) alloca (n_basic_blocks);
2878       bzero (visited, n_basic_blocks);
2879     }
2880
2881   for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
2882     {
2883       int pred_bb = INT_LIST_VAL (pred);
2884
2885       if (visited[pred_bb])
2886         {
2887           /* This predecessor has already been visited.
2888              Nothing to do.  */
2889           ;
2890         }
2891       else if (pred_bb == bb)
2892         {
2893           /* BB loops on itself.  */
2894           if (check_self_loop
2895               && TEST_BIT (ae_gen[pred_bb], expr->bitmap_index)
2896               && BLOCK_NUM (occr->insn) == pred_bb)
2897             return 1;
2898           visited[pred_bb] = 1;
2899         }
2900       /* Ignore this predecessor if it kills the expression.  */
2901       else if (TEST_BIT (ae_kill[pred_bb], expr->bitmap_index))
2902         visited[pred_bb] = 1;
2903       /* Does this predecessor generate this expression?  */
2904       else if (TEST_BIT (ae_gen[pred_bb], expr->bitmap_index))
2905         {
2906           /* Is this the occurrence we're looking for?
2907              Note that there's only one generating occurrence per block
2908              so we just need to check the block number.  */
2909           if (BLOCK_NUM (occr->insn) == pred_bb)
2910             return 1;
2911           visited[pred_bb] = 1;
2912         }
2913       /* Neither gen nor kill.  */
2914       else
2915         {
2916           visited[pred_bb] = 1;
2917           if (expr_reaches_here_p (occr, expr, pred_bb, check_self_loop, visited))
2918             return 1;
2919         }
2920     }
2921
2922   /* All paths have been checked.  */
2923   return 0;
2924 }
2925
2926 /* Return the instruction that computes EXPR that reaches INSN's basic block.
2927    If there is more than one such instruction, return NULL.
2928
2929    Called only by handle_avail_expr.  */
2930
2931 static rtx
2932 computing_insn (expr, insn)
2933      struct expr *expr;
2934      rtx insn;
2935 {
2936   int bb = BLOCK_NUM (insn);
2937
2938   if (expr->avail_occr->next == NULL)
2939     {
2940       if (BLOCK_NUM (expr->avail_occr->insn) == bb)
2941         {
2942           /* The available expression is actually itself
2943              (i.e. a loop in the flow graph) so do nothing.  */
2944           return NULL;
2945         }
2946       /* (FIXME) Case that we found a pattern that was created by
2947          a substitution that took place.  */
2948       return expr->avail_occr->insn;
2949     }
2950   else
2951     {
2952       /* Pattern is computed more than once.
2953          Search backwards from this insn to see how many of these
2954          computations actually reach this insn.  */
2955       struct occr *occr;
2956       rtx insn_computes_expr = NULL;
2957       int can_reach = 0;
2958
2959       for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
2960         {
2961           if (BLOCK_NUM (occr->insn) == bb)
2962             {
2963               /* The expression is generated in this block.
2964                  The only time we care about this is when the expression
2965                  is generated later in the block [and thus there's a loop].
2966                  We let the normal cse pass handle the other cases.  */
2967               if (INSN_CUID (insn) < INSN_CUID (occr->insn))
2968                 {
2969                   if (expr_reaches_here_p (occr, expr, bb, 1, NULL))
2970                     {
2971                       can_reach++;
2972                       if (can_reach > 1)
2973                         return NULL;
2974                       insn_computes_expr = occr->insn;
2975                     }
2976                 }
2977             }
2978           else /* Computation of the pattern outside this block.  */
2979             {
2980               if (expr_reaches_here_p (occr, expr, bb, 0, NULL))
2981                 {
2982                   can_reach++;
2983                   if (can_reach > 1)
2984                     return NULL;
2985                   insn_computes_expr = occr->insn;
2986                 }
2987             }
2988         }
2989
2990       if (insn_computes_expr == NULL)
2991         abort ();
2992       return insn_computes_expr;
2993     }
2994 }
2995
2996 /* Return non-zero if the definition in DEF_INSN can reach INSN.
2997    Only called by can_disregard_other_sets.  */
2998
2999 static int
3000 def_reaches_here_p (insn, def_insn)
3001      rtx insn, def_insn;
3002 {
3003   rtx reg;
3004
3005   if (TEST_BIT (reaching_defs[BLOCK_NUM (insn)], INSN_CUID (def_insn)))
3006     return 1;
3007
3008   if (BLOCK_NUM (insn) == BLOCK_NUM (def_insn))
3009     {
3010       if (INSN_CUID (def_insn) < INSN_CUID (insn))
3011         {
3012           if (GET_CODE (PATTERN (def_insn)) == PARALLEL)
3013             return 1;
3014           if (GET_CODE (PATTERN (def_insn)) == CLOBBER)
3015             reg = XEXP (PATTERN (def_insn), 0);
3016           else if (GET_CODE (PATTERN (def_insn)) == SET)
3017             reg = SET_DEST (PATTERN (def_insn));
3018           else
3019             abort ();
3020           return ! reg_set_between_p (reg, NEXT_INSN (def_insn), insn);
3021         }
3022       else
3023         return 0;
3024     }
3025
3026   return 0;
3027 }
3028
3029 /* Return non-zero if *ADDR_THIS_REG can only have one value at INSN.
3030    The value returned is the number of definitions that reach INSN.
3031    Returning a value of zero means that [maybe] more than one definition
3032    reaches INSN and the caller can't perform whatever optimization it is
3033    trying.  i.e. it is always safe to return zero.  */
3034
3035 static int
3036 can_disregard_other_sets (addr_this_reg, insn, for_combine)
3037      struct reg_set **addr_this_reg;
3038      rtx insn;
3039      int for_combine;
3040 {
3041   int number_of_reaching_defs = 0;
3042   struct reg_set *this_reg = *addr_this_reg;
3043
3044   while (this_reg)
3045     {
3046       if (def_reaches_here_p (insn, this_reg->insn))
3047         {
3048           number_of_reaching_defs++;
3049           /* Ignore parallels for now.  */
3050           if (GET_CODE (PATTERN (this_reg->insn)) == PARALLEL)
3051             return 0;
3052           if (!for_combine
3053               && (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER
3054                   || ! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3055                                     SET_SRC (PATTERN (insn)))))
3056             {
3057               /* A setting of the reg to a different value reaches INSN.  */
3058               return 0;
3059             }
3060           if (number_of_reaching_defs > 1)
3061             {
3062               /* If in this setting the value the register is being
3063                  set to is equal to the previous value the register
3064                  was set to and this setting reaches the insn we are
3065                  trying to do the substitution on then we are ok.  */
3066
3067               if (GET_CODE (PATTERN (this_reg->insn)) == CLOBBER)
3068                 return 0;
3069               if (! rtx_equal_p (SET_SRC (PATTERN (this_reg->insn)),
3070                                  SET_SRC (PATTERN (insn))))
3071                 return 0;
3072             }
3073           *addr_this_reg = this_reg;
3074         }
3075
3076       /* prev_this_reg = this_reg; */
3077       this_reg = this_reg->next;
3078     }
3079
3080   return number_of_reaching_defs;
3081 }
3082
3083 /* Expression computed by insn is available and the substitution is legal,
3084    so try to perform the substitution.
3085
3086    The result is non-zero if any changes were made.  */
3087
3088 static int
3089 handle_avail_expr (insn, expr)
3090      rtx insn;
3091      struct expr *expr;
3092 {
3093   rtx pat, insn_computes_expr;
3094   rtx to;
3095   struct reg_set *this_reg;
3096   int found_setting, use_src;
3097   int changed = 0;
3098
3099   /* We only handle the case where one computation of the expression
3100      reaches this instruction.  */
3101   insn_computes_expr = computing_insn (expr, insn);
3102   if (insn_computes_expr == NULL)
3103     return 0;
3104
3105   found_setting = 0;
3106   use_src = 0;
3107
3108   /* At this point we know only one computation of EXPR outside of this
3109      block reaches this insn.  Now try to find a register that the
3110      expression is computed into.  */
3111
3112   if (GET_CODE (SET_SRC (PATTERN (insn_computes_expr))) == REG)
3113     {
3114       /* This is the case when the available expression that reaches
3115          here has already been handled as an available expression.  */
3116       int regnum_for_replacing = REGNO (SET_SRC (PATTERN (insn_computes_expr)));
3117       /* If the register was created by GCSE we can't use `reg_set_table',
3118          however we know it's set only once.  */
3119       if (regnum_for_replacing >= max_gcse_regno
3120           /* If the register the expression is computed into is set only once,
3121              or only one set reaches this insn, we can use it.  */
3122           || (((this_reg = reg_set_table[regnum_for_replacing]),
3123                this_reg->next == NULL)
3124               || can_disregard_other_sets (&this_reg, insn, 0)))
3125        {
3126          use_src = 1;
3127          found_setting = 1;
3128        }
3129     }
3130
3131   if (!found_setting)
3132     {
3133       int regnum_for_replacing = REGNO (SET_DEST (PATTERN (insn_computes_expr)));
3134       /* This shouldn't happen.  */
3135       if (regnum_for_replacing >= max_gcse_regno)
3136         abort ();
3137       this_reg = reg_set_table[regnum_for_replacing];
3138       /* If the register the expression is computed into is set only once,
3139          or only one set reaches this insn, use it.  */
3140       if (this_reg->next == NULL
3141           || can_disregard_other_sets (&this_reg, insn, 0))
3142         found_setting = 1;
3143     }
3144
3145   if (found_setting)
3146     {
3147       pat = PATTERN (insn);
3148       if (use_src)
3149         to = SET_SRC (PATTERN (insn_computes_expr));
3150       else
3151         to = SET_DEST (PATTERN (insn_computes_expr));
3152       changed = validate_change (insn, &SET_SRC (pat), to, 0);
3153
3154       /* We should be able to ignore the return code from validate_change but
3155          to play it safe we check.  */
3156       if (changed)
3157         {
3158           gcse_subst_count++;
3159           if (gcse_file != NULL)
3160             {
3161               fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d %s insn %d\n",
3162                        INSN_UID (insn), REGNO (to),
3163                        use_src ? "from" : "set in",
3164                        INSN_UID (insn_computes_expr));
3165             }
3166
3167         }
3168     }
3169   /* The register that the expr is computed into is set more than once.  */
3170   else if (1 /*expensive_op(this_pattrn->op) && do_expensive_gcse)*/)
3171     {
3172       /* Insert an insn after insnx that copies the reg set in insnx
3173          into a new pseudo register call this new register REGN.
3174          From insnb until end of basic block or until REGB is set
3175          replace all uses of REGB with REGN.  */
3176       rtx new_insn;
3177
3178       to = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (insn_computes_expr))));
3179
3180       /* Generate the new insn.  */
3181       /* ??? If the change fails, we return 0, even though we created
3182          an insn.  I think this is ok.  */
3183       new_insn
3184         = emit_insn_after (gen_rtx_SET (VOIDmode, to,
3185                                         SET_DEST (PATTERN (insn_computes_expr))),
3186                                   insn_computes_expr);
3187       /* Keep block number table up to date.  */
3188       set_block_num (new_insn, BLOCK_NUM (insn_computes_expr));
3189       /* Keep register set table up to date.  */
3190       record_one_set (REGNO (to), new_insn);
3191
3192       gcse_create_count++;
3193       if (gcse_file != NULL)
3194         {
3195           fprintf (gcse_file, "GCSE: Creating insn %d to copy value of reg %d, computed in insn %d,\n",
3196                    INSN_UID (NEXT_INSN (insn_computes_expr)),
3197                    REGNO (SET_SRC (PATTERN (NEXT_INSN (insn_computes_expr)))),
3198                    INSN_UID (insn_computes_expr));
3199           fprintf (gcse_file, "      into newly allocated reg %d\n", REGNO (to));
3200         }
3201
3202       pat = PATTERN (insn);
3203
3204       /* Do register replacement for INSN.  */
3205       changed = validate_change (insn, &SET_SRC (pat),
3206                                  SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr))),
3207                                  0);
3208
3209       /* We should be able to ignore the return code from validate_change but
3210          to play it safe we check.  */
3211       if (changed)
3212         {
3213           gcse_subst_count++;
3214           if (gcse_file != NULL)
3215             {
3216               fprintf (gcse_file, "GCSE: Replacing the source in insn %d with reg %d set in insn %d\n",
3217                        INSN_UID (insn),
3218                        REGNO (SET_DEST (PATTERN (NEXT_INSN (insn_computes_expr)))),
3219                        INSN_UID (insn_computes_expr));
3220             }
3221
3222         }
3223     }
3224
3225   return changed;
3226 }
3227
3228 /* Perform classic GCSE.
3229    This is called by one_classic_gcse_pass after all the dataflow analysis
3230    has been done.
3231
3232    The result is non-zero if a change was made.  */
3233
3234 static int
3235 classic_gcse ()
3236 {
3237   int bb, changed;
3238   rtx insn;
3239
3240   /* Note we start at block 1.  */
3241
3242   changed = 0;
3243   for (bb = 1; bb < n_basic_blocks; bb++)
3244     {
3245       /* Reset tables used to keep track of what's still valid [since the
3246          start of the block].  */
3247       reset_opr_set_tables ();
3248
3249       for (insn = BLOCK_HEAD (bb);
3250            insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
3251            insn = NEXT_INSN (insn))
3252         {
3253           /* Is insn of form (set (pseudo-reg) ...)?  */
3254
3255           if (GET_CODE (insn) == INSN
3256               && GET_CODE (PATTERN (insn)) == SET
3257               && GET_CODE (SET_DEST (PATTERN (insn))) == REG
3258               && REGNO (SET_DEST (PATTERN (insn))) >= FIRST_PSEUDO_REGISTER)
3259             {
3260               rtx pat = PATTERN (insn);
3261               rtx src = SET_SRC (pat);
3262               struct expr *expr;
3263
3264               if (want_to_gcse_p (src)
3265                   /* Is the expression recorded?  */
3266                   && ((expr = lookup_expr (src)) != NULL)
3267                   /* Is the expression available [at the start of the
3268                      block]?  */
3269                   && TEST_BIT (ae_in[bb], expr->bitmap_index)
3270                   /* Are the operands unchanged since the start of the
3271                      block?  */
3272                   && oprs_not_set_p (src, insn))
3273                 changed |= handle_avail_expr (insn, expr);
3274             }
3275
3276           /* Keep track of everything modified by this insn.  */
3277           /* ??? Need to be careful w.r.t. mods done to INSN.  */
3278           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3279             mark_oprs_set (insn);
3280         }
3281     }
3282
3283   return changed;
3284 }
3285
3286 /* Top level routine to perform one classic GCSE pass.
3287
3288    Return non-zero if a change was made.  */
3289
3290 static int
3291 one_classic_gcse_pass (pass)
3292      int pass;
3293 {
3294   int changed = 0;
3295
3296   gcse_subst_count = 0;
3297   gcse_create_count = 0;
3298
3299   alloc_expr_hash_table (max_cuid);
3300   alloc_rd_mem (n_basic_blocks, max_cuid);
3301   compute_expr_hash_table ();
3302   if (gcse_file)
3303     dump_hash_table (gcse_file, "Expression", expr_hash_table,
3304                      expr_hash_table_size, n_exprs);
3305   if (n_exprs > 0)
3306     {
3307       compute_kill_rd ();
3308       compute_rd ();
3309       alloc_avail_expr_mem (n_basic_blocks, n_exprs);
3310       compute_ae_gen ();
3311       compute_ae_kill ();
3312       compute_available ();
3313       changed = classic_gcse ();
3314       free_avail_expr_mem ();
3315     }
3316   free_rd_mem ();
3317   free_expr_hash_table ();
3318
3319   if (gcse_file)
3320     {
3321       fprintf (gcse_file, "\n");
3322       fprintf (gcse_file, "GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
3323                current_function_name, pass,
3324                bytes_used, gcse_subst_count, gcse_create_count);
3325     }
3326
3327   return changed;
3328 }
3329 \f
3330 /* Compute copy/constant propagation working variables.  */
3331
3332 /* Local properties of assignments.  */
3333
3334 static sbitmap *cprop_pavloc;
3335 static sbitmap *cprop_absaltered;
3336
3337 /* Global properties of assignments (computed from the local properties).  */
3338
3339 static sbitmap *cprop_avin;
3340 static sbitmap *cprop_avout;
3341
3342 /* Allocate vars used for copy/const propagation.
3343    N_BLOCKS is the number of basic blocks.
3344    N_SETS is the number of sets.  */
3345
3346 static void
3347 alloc_cprop_mem (n_blocks, n_sets)
3348      int n_blocks, n_sets;
3349 {
3350   cprop_pavloc = sbitmap_vector_alloc (n_blocks, n_sets);
3351   cprop_absaltered = sbitmap_vector_alloc (n_blocks, n_sets);
3352
3353   cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
3354   cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
3355 }
3356
3357 /* Free vars used by copy/const propagation.  */
3358
3359 static void
3360 free_cprop_mem ()
3361 {
3362   free (cprop_pavloc);
3363   free (cprop_absaltered);
3364   free (cprop_avin);
3365   free (cprop_avout);
3366 }
3367
3368 /* For each block, compute whether X is transparent.
3369    X is either an expression or an assignment [though we don't care which,
3370    for this context an assignment is treated as an expression].
3371    For each block where an element of X is modified, set (SET_P == 1) or reset
3372    (SET_P == 0) the INDX bit in BMAP.  */
3373
3374 static void
3375 compute_transp (x, indx, bmap, set_p)
3376      rtx x;
3377      int indx;
3378      sbitmap *bmap;
3379      int set_p;
3380 {
3381   int bb,i;
3382   enum rtx_code code;
3383   const char *fmt;
3384
3385   /* repeat is used to turn tail-recursion into iteration.  */
3386  repeat:
3387
3388   if (x == 0)
3389     return;
3390
3391   code = GET_CODE (x);
3392   switch (code)
3393     {
3394     case REG:
3395       {
3396         reg_set *r;
3397         int regno = REGNO (x);
3398
3399         if (set_p)
3400           {
3401             if (regno < FIRST_PSEUDO_REGISTER)
3402               {
3403                 for (bb = 0; bb < n_basic_blocks; bb++)
3404                   if (TEST_BIT (reg_set_in_block[bb], regno))
3405                     SET_BIT (bmap[bb], indx);
3406               }
3407             else
3408               {
3409                 for (r = reg_set_table[regno]; r != NULL; r = r->next)
3410                   {
3411                     bb = BLOCK_NUM (r->insn);
3412                     SET_BIT (bmap[bb], indx);
3413                   }
3414               }
3415           }
3416         else
3417           {
3418             if (regno < FIRST_PSEUDO_REGISTER)
3419               {
3420                 for (bb = 0; bb < n_basic_blocks; bb++)
3421                   if (TEST_BIT (reg_set_in_block[bb], regno))
3422                     RESET_BIT (bmap[bb], indx);
3423               }
3424             else
3425               {
3426                 for (r = reg_set_table[regno]; r != NULL; r = r->next)
3427                   {
3428                     bb = BLOCK_NUM (r->insn);
3429                     RESET_BIT (bmap[bb], indx);
3430                   }
3431               }
3432           }
3433         return;
3434       }
3435
3436     case MEM:
3437       if (set_p)
3438         {
3439           for (bb = 0; bb < n_basic_blocks; bb++)
3440             if (mem_set_in_block[bb])
3441               SET_BIT (bmap[bb], indx);
3442         }
3443       else
3444         {
3445           for (bb = 0; bb < n_basic_blocks; bb++)
3446             if (mem_set_in_block[bb])
3447               RESET_BIT (bmap[bb], indx);
3448         }
3449       x = XEXP (x, 0);
3450       goto repeat;
3451
3452     case PC:
3453     case CC0: /*FIXME*/
3454     case CONST:
3455     case CONST_INT:
3456     case CONST_DOUBLE:
3457     case SYMBOL_REF:
3458     case LABEL_REF:
3459     case ADDR_VEC:
3460     case ADDR_DIFF_VEC:
3461       return;
3462
3463     default:
3464       break;
3465     }
3466
3467   i = GET_RTX_LENGTH (code) - 1;
3468   fmt = GET_RTX_FORMAT (code);
3469   for (; i >= 0; i--)
3470     {
3471       if (fmt[i] == 'e')
3472         {
3473           rtx tem = XEXP (x, i);
3474
3475           /* If we are about to do the last recursive call
3476              needed at this level, change it into iteration.
3477              This function is called enough to be worth it.  */
3478           if (i == 0)
3479             {
3480               x = tem;
3481               goto repeat;
3482             }
3483           compute_transp (tem, indx, bmap, set_p);
3484         }
3485       else if (fmt[i] == 'E')
3486         {
3487           int j;
3488           for (j = 0; j < XVECLEN (x, i); j++)
3489             compute_transp (XVECEXP (x, i, j), indx, bmap, set_p);
3490         }
3491     }
3492 }
3493
3494 /* Compute the available expressions at the start and end of each
3495    basic block for cprop.  This particular dataflow equation is
3496    used often enough that we might want to generalize it and make
3497    as a subroutine for other global optimizations that need available
3498    in/out information.  */
3499 static void
3500 compute_cprop_avinout ()
3501 {
3502   int bb, changed, passes;
3503
3504   sbitmap_zero (cprop_avin[0]);
3505   sbitmap_vector_ones (cprop_avout, n_basic_blocks);
3506
3507   passes = 0;
3508   changed = 1;
3509   while (changed)
3510     {
3511       changed = 0;
3512       for (bb = 0; bb < n_basic_blocks; bb++)
3513         {
3514           if (bb != 0)
3515             sbitmap_intersect_of_predecessors (cprop_avin[bb],
3516                                                cprop_avout, bb, s_preds);
3517           changed |= sbitmap_union_of_diff (cprop_avout[bb],
3518                                             cprop_pavloc[bb],
3519                                             cprop_avin[bb],
3520                                             cprop_absaltered[bb]);
3521         }
3522       passes++;
3523     }
3524
3525   if (gcse_file)
3526     fprintf (gcse_file, "cprop avail expr computation: %d passes\n", passes);
3527 }
3528
3529 /* Top level routine to do the dataflow analysis needed by copy/const
3530    propagation.  */
3531
3532 static void
3533 compute_cprop_data ()
3534 {
3535   compute_local_properties (cprop_absaltered, cprop_pavloc, NULL, 1);
3536   compute_cprop_avinout ();
3537 }
3538 \f
3539 /* Copy/constant propagation.  */
3540
3541 /* Maximum number of register uses in an insn that we handle.  */
3542 #define MAX_USES 8
3543
3544 /* Table of uses found in an insn.
3545    Allocated statically to avoid alloc/free complexity and overhead.  */
3546 static struct reg_use reg_use_table[MAX_USES];
3547
3548 /* Index into `reg_use_table' while building it.  */
3549 static int reg_use_count;
3550
3551 /* Set up a list of register numbers used in INSN.
3552    The found uses are stored in `reg_use_table'.
3553    `reg_use_count' is initialized to zero before entry, and
3554    contains the number of uses in the table upon exit.
3555
3556    ??? If a register appears multiple times we will record it multiple
3557    times.  This doesn't hurt anything but it will slow things down.  */
3558
3559 static void
3560 find_used_regs (x)
3561      rtx x;
3562 {
3563   int i;
3564   enum rtx_code code;
3565   const char *fmt;
3566
3567   /* repeat is used to turn tail-recursion into iteration.  */
3568  repeat:
3569
3570   if (x == 0)
3571     return;
3572
3573   code = GET_CODE (x);
3574   switch (code)
3575     {
3576     case REG:
3577       if (reg_use_count == MAX_USES)
3578         return;
3579       reg_use_table[reg_use_count].reg_rtx = x;
3580       reg_use_count++;
3581       return;
3582
3583     case MEM:
3584       x = XEXP (x, 0);
3585       goto repeat;
3586
3587     case PC:
3588     case CC0:
3589     case CONST:
3590     case CONST_INT:
3591     case CONST_DOUBLE:
3592     case SYMBOL_REF:
3593     case LABEL_REF:
3594     case CLOBBER:
3595     case ADDR_VEC:
3596     case ADDR_DIFF_VEC:
3597     case ASM_INPUT: /*FIXME*/
3598       return;
3599
3600     case SET:
3601       if (GET_CODE (SET_DEST (x)) == MEM)
3602         find_used_regs (SET_DEST (x));
3603       x = SET_SRC (x);
3604       goto repeat;
3605
3606     default:
3607       break;
3608     }
3609
3610   /* Recursively scan the operands of this expression.  */
3611
3612   fmt = GET_RTX_FORMAT (code);
3613   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
3614     {
3615       if (fmt[i] == 'e')
3616         {
3617           /* If we are about to do the last recursive call
3618              needed at this level, change it into iteration.
3619              This function is called enough to be worth it.  */
3620           if (i == 0)
3621             {
3622               x = XEXP (x, 0);
3623               goto repeat;
3624             }
3625           find_used_regs (XEXP (x, i));
3626         }
3627       else if (fmt[i] == 'E')
3628         {
3629           int j;
3630           for (j = 0; j < XVECLEN (x, i); j++)
3631             find_used_regs (XVECEXP (x, i, j));
3632         }
3633     }
3634 }
3635
3636 /* Try to replace all non-SET_DEST occurrences of FROM in INSN with TO.
3637    Returns non-zero is successful.  */
3638
3639 static int
3640 try_replace_reg (from, to, insn)
3641      rtx from, to, insn;
3642 {
3643   /* If this fails we could try to simplify the result of the
3644      replacement and attempt to recognize the simplified insn.
3645
3646      But we need a general simplify_rtx that doesn't have pass
3647      specific state variables.  I'm not aware of one at the moment.  */
3648   return validate_replace_src (from, to, insn);
3649 }
3650
3651 /* Find a set of REGNO that is available on entry to INSN's block.
3652    Returns NULL if not found.  */
3653
3654 static struct expr *
3655 find_avail_set (regno, insn)
3656      int regno;
3657      rtx insn;
3658 {
3659   /* SET1 contains the last set found that can be returned to the caller for
3660      use in a substitution.  */
3661   struct expr *set1 = 0;
3662
3663   /* Loops are not possible here.  To get a loop we would need two sets
3664      available at the start of the block containing INSN.  ie we would
3665      need two sets like this available at the start of the block:
3666
3667        (set (reg X) (reg Y))
3668        (set (reg Y) (reg X))
3669
3670      This can not happen since the set of (reg Y) would have killed the
3671      set of (reg X) making it unavailable at the start of this block.  */
3672   while (1)
3673      {
3674       rtx src;
3675       struct expr *set = lookup_set (regno, NULL_RTX);
3676
3677       /* Find a set that is available at the start of the block
3678          which contains INSN.  */
3679       while (set)
3680         {
3681           if (TEST_BIT (cprop_avin[BLOCK_NUM (insn)], set->bitmap_index))
3682             break;
3683           set = next_set (regno, set);
3684         }
3685
3686       /* If no available set was found we've reached the end of the
3687          (possibly empty) copy chain.  */
3688       if (set == 0)
3689         break;
3690
3691       if (GET_CODE (set->expr) != SET)
3692         abort ();
3693
3694       src = SET_SRC (set->expr);
3695
3696       /* We know the set is available.
3697          Now check that SRC is ANTLOC (i.e. none of the source operands
3698          have changed since the start of the block).
3699
3700          If the source operand changed, we may still use it for the next
3701          iteration of this loop, but we may not use it for substitutions.  */
3702       if (CONSTANT_P (src) || oprs_not_set_p (src, insn))
3703         set1 = set;
3704
3705       /* If the source of the set is anything except a register, then
3706          we have reached the end of the copy chain.  */
3707       if (GET_CODE (src) != REG)
3708         break;
3709
3710       /* Follow the copy chain, ie start another iteration of the loop
3711          and see if we have an available copy into SRC.  */
3712       regno = REGNO (src);
3713      }
3714
3715   /* SET1 holds the last set that was available and anticipatable at
3716      INSN.  */
3717   return set1;
3718 }
3719
3720 /* Subroutine of cprop_insn that tries to propagate constants into
3721    JUMP_INSNS.  INSN must be a conditional jump; COPY is a copy of it
3722    that we can use for substitutions.
3723    REG_USED is the use we will try to replace, SRC is the constant we
3724    will try to substitute for it.
3725    Returns nonzero if a change was made.  */
3726 static int
3727 cprop_jump (insn, copy, reg_used, src)
3728      rtx insn, copy;
3729      struct reg_use *reg_used;
3730      rtx src;
3731 {
3732   rtx set = PATTERN (copy);
3733   rtx temp;
3734
3735   /* Replace the register with the appropriate constant.  */
3736   replace_rtx (SET_SRC (set), reg_used->reg_rtx, src);
3737
3738   temp = simplify_ternary_operation (GET_CODE (SET_SRC (set)),
3739                                      GET_MODE (SET_SRC (set)),
3740                                      GET_MODE (XEXP (SET_SRC (set), 0)),
3741                                      XEXP (SET_SRC (set), 0),
3742                                      XEXP (SET_SRC (set), 1),
3743                                      XEXP (SET_SRC (set), 2));
3744
3745   /* If no simplification can be made, then try the next
3746      register.  */
3747   if (temp == 0)
3748     return 0;
3749
3750   SET_SRC (set) = temp;
3751
3752   /* That may have changed the structure of TEMP, so
3753      force it to be rerecognized if it has not turned
3754      into a nop or unconditional jump.  */
3755
3756   INSN_CODE (copy) = -1;
3757   if ((SET_DEST (set) == pc_rtx
3758        && (SET_SRC (set) == pc_rtx
3759            || GET_CODE (SET_SRC (set)) == LABEL_REF))
3760       || recog (PATTERN (copy), copy, NULL) >= 0)
3761     {
3762       /* This has either become an unconditional jump
3763          or a nop-jump.  We'd like to delete nop jumps
3764          here, but doing so confuses gcse.  So we just
3765          make the replacement and let later passes
3766          sort things out.  */
3767       PATTERN (insn) = set;
3768       INSN_CODE (insn) = -1;
3769
3770       /* One less use of the label this insn used to jump to
3771          if we turned this into a NOP jump.  */
3772       if (SET_SRC (set) == pc_rtx && JUMP_LABEL (insn) != 0)
3773         --LABEL_NUSES (JUMP_LABEL (insn));
3774
3775       /* If this has turned into an unconditional jump,
3776          then put a barrier after it so that the unreachable
3777          code will be deleted.  */
3778       if (GET_CODE (SET_SRC (set)) == LABEL_REF)
3779         emit_barrier_after (insn);
3780
3781       run_jump_opt_after_gcse = 1;
3782
3783       const_prop_count++;
3784       if (gcse_file != NULL)
3785         {
3786           int regno = REGNO (reg_used->reg_rtx);
3787           fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
3788                    regno, INSN_UID (insn));
3789           print_rtl (gcse_file, src);
3790           fprintf (gcse_file, "\n");
3791         }
3792       return 1;
3793     }
3794   return 0;
3795 }
3796
3797 #ifdef HAVE_cc0
3798 /* Subroutine of cprop_insn that tries to propagate constants into
3799    JUMP_INSNS for machines that have CC0.  INSN is a single set that
3800    stores into CC0; the insn following it is a conditional jump.
3801    REG_USED is the use we will try to replace, SRC is the constant we
3802    will try to substitute for it.
3803    Returns nonzero if a change was made.  */
3804 static int
3805 cprop_cc0_jump (insn, reg_used, src)
3806      rtx insn;
3807      struct reg_use *reg_used;
3808      rtx src;
3809 {
3810   rtx jump = NEXT_INSN (insn);
3811   rtx copy = copy_rtx (jump);
3812   rtx set = PATTERN (copy);
3813
3814   /* We need to copy the source of the cc0 setter, as cprop_jump is going to
3815      substitute into it.  */
3816   replace_rtx (SET_SRC (set), cc0_rtx, copy_rtx (SET_SRC (PATTERN (insn))));
3817   if (! cprop_jump (jump, copy, reg_used, src))
3818     return 0;
3819
3820   /* If we succeeded, delete the cc0 setter.  */
3821   PUT_CODE (insn, NOTE);
3822   NOTE_LINE_NUMBER (insn) = NOTE_INSN_DELETED;
3823   NOTE_SOURCE_FILE (insn) = 0;
3824   return 1;
3825  }
3826 #endif
3827
3828 /* Perform constant and copy propagation on INSN.
3829    The result is non-zero if a change was made.  */
3830
3831 static int
3832 cprop_insn (insn, alter_jumps)
3833      rtx insn;
3834      int alter_jumps;
3835 {
3836   struct reg_use *reg_used;
3837   int changed = 0;
3838
3839   /* Only propagate into SETs.  Note that a conditional jump is a
3840      SET with pc_rtx as the destination.  */
3841   if ((GET_CODE (insn) != INSN
3842        && GET_CODE (insn) != JUMP_INSN)
3843       || GET_CODE (PATTERN (insn)) != SET)
3844     return 0;
3845
3846   reg_use_count = 0;
3847   find_used_regs (PATTERN (insn));
3848
3849   reg_used = &reg_use_table[0];
3850   for ( ; reg_use_count > 0; reg_used++, reg_use_count--)
3851     {
3852       rtx pat, src;
3853       struct expr *set;
3854       int regno = REGNO (reg_used->reg_rtx);
3855
3856       /* Ignore registers created by GCSE.
3857          We do this because ... */
3858       if (regno >= max_gcse_regno)
3859         continue;
3860
3861       /* If the register has already been set in this block, there's
3862          nothing we can do.  */
3863       if (! oprs_not_set_p (reg_used->reg_rtx, insn))
3864         continue;
3865
3866       /* Find an assignment that sets reg_used and is available
3867          at the start of the block.  */
3868       set = find_avail_set (regno, insn);
3869       if (! set)
3870         continue;
3871
3872       pat = set->expr;
3873       /* ??? We might be able to handle PARALLELs.  Later.  */
3874       if (GET_CODE (pat) != SET)
3875         abort ();
3876       src = SET_SRC (pat);
3877
3878       /* Constant propagation.  */
3879       if (GET_CODE (src) == CONST_INT || GET_CODE (src) == CONST_DOUBLE
3880           || GET_CODE (src) == SYMBOL_REF)
3881         {
3882           /* Handle normal insns first.  */
3883           if (GET_CODE (insn) == INSN
3884               && try_replace_reg (reg_used->reg_rtx, src, insn))
3885             {
3886               changed = 1;
3887               const_prop_count++;
3888               if (gcse_file != NULL)
3889                 {
3890                   fprintf (gcse_file, "CONST-PROP: Replacing reg %d in insn %d with constant ",
3891                            regno, INSN_UID (insn));
3892                   print_rtl (gcse_file, src);
3893                   fprintf (gcse_file, "\n");
3894                 }
3895
3896               /* The original insn setting reg_used may or may not now be
3897                  deletable.  We leave the deletion to flow.  */
3898             }
3899
3900           /* Try to propagate a CONST_INT into a conditional jump.
3901              We're pretty specific about what we will handle in this
3902              code, we can extend this as necessary over time.
3903
3904              Right now the insn in question must look like
3905              (set (pc) (if_then_else ...))  */
3906           else if (alter_jumps
3907                    && GET_CODE (insn) == JUMP_INSN
3908                    && condjump_p (insn)
3909                    && ! simplejump_p (insn))
3910             changed |= cprop_jump (insn, copy_rtx (insn), reg_used, src);
3911 #ifdef HAVE_cc0
3912           /* Similar code for machines that use a pair of CC0 setter and
3913              conditional jump insn.  */
3914           else if (alter_jumps
3915                    && GET_CODE (PATTERN (insn)) == SET
3916                    && SET_DEST (PATTERN (insn)) == cc0_rtx
3917                    && GET_CODE (NEXT_INSN (insn)) == JUMP_INSN
3918                    && condjump_p (NEXT_INSN (insn))
3919                    && ! simplejump_p (NEXT_INSN (insn)))
3920             changed |= cprop_cc0_jump (insn, reg_used, src);
3921 #endif
3922         }
3923       else if (GET_CODE (src) == REG
3924                && REGNO (src) >= FIRST_PSEUDO_REGISTER
3925                && REGNO (src) != regno)
3926         {
3927           if (try_replace_reg (reg_used->reg_rtx, src, insn))
3928             {
3929               changed = 1;
3930               copy_prop_count++;
3931               if (gcse_file != NULL)
3932                 {
3933                   fprintf (gcse_file, "COPY-PROP: Replacing reg %d in insn %d with reg %d\n",
3934                            regno, INSN_UID (insn), REGNO (src));
3935                 }
3936
3937               /* The original insn setting reg_used may or may not now be
3938                  deletable.  We leave the deletion to flow.  */
3939               /* FIXME: If it turns out that the insn isn't deletable,
3940                  then we may have unnecessarily extended register lifetimes
3941                  and made things worse.  */
3942             }
3943         }
3944     }
3945
3946   return changed;
3947 }
3948
3949 /* Forward propagate copies.
3950    This includes copies and constants.
3951    Return non-zero if a change was made.  */
3952
3953 static int
3954 cprop (alter_jumps)
3955      int alter_jumps;
3956 {
3957   int bb, changed;
3958   rtx insn;
3959
3960   /* Note we start at block 1.  */
3961
3962   changed = 0;
3963   for (bb = 1; bb < n_basic_blocks; bb++)
3964     {
3965       /* Reset tables used to keep track of what's still valid [since the
3966          start of the block].  */
3967       reset_opr_set_tables ();
3968
3969       for (insn = BLOCK_HEAD (bb);
3970            insn != NULL && insn != NEXT_INSN (BLOCK_END (bb));
3971            insn = NEXT_INSN (insn))
3972         {
3973           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
3974             {
3975               changed |= cprop_insn (insn, alter_jumps);
3976
3977               /* Keep track of everything modified by this insn.  */
3978               /* ??? Need to be careful w.r.t. mods done to INSN.  Don't
3979                  call mark_oprs_set if we turned the insn into a NOTE.  */
3980               if (GET_CODE (insn) != NOTE)
3981                 mark_oprs_set (insn);
3982             }
3983         }
3984     }
3985
3986   if (gcse_file != NULL)
3987     fprintf (gcse_file, "\n");
3988
3989   return changed;
3990 }
3991
3992 /* Perform one copy/constant propagation pass.
3993    F is the first insn in the function.
3994    PASS is the pass count.  */
3995
3996 static int
3997 one_cprop_pass (pass, alter_jumps)
3998      int pass;
3999      int alter_jumps;
4000 {
4001   int changed = 0;
4002
4003   const_prop_count = 0;
4004   copy_prop_count = 0;
4005
4006   alloc_set_hash_table (max_cuid);
4007   compute_set_hash_table ();
4008   if (gcse_file)
4009     dump_hash_table (gcse_file, "SET", set_hash_table, set_hash_table_size,
4010                      n_sets);
4011   if (n_sets > 0)
4012     {
4013       alloc_cprop_mem (n_basic_blocks, n_sets);
4014       compute_cprop_data ();
4015       changed = cprop (alter_jumps);
4016       free_cprop_mem ();
4017     }
4018   free_set_hash_table ();
4019
4020   if (gcse_file)
4021     {
4022       fprintf (gcse_file, "CPROP of %s, pass %d: %d bytes needed, %d const props, %d copy props\n",
4023                current_function_name, pass,
4024                bytes_used, const_prop_count, copy_prop_count);
4025       fprintf (gcse_file, "\n");
4026     }
4027
4028   return changed;
4029 }
4030 \f
4031 /* Compute PRE+LCM working variables.  */
4032
4033 /* Local properties of expressions.  */
4034 /* Nonzero for expressions that are transparent in the block.  */
4035 static sbitmap *transp;
4036
4037 /* Nonzero for expressions that are transparent at the end of the block.
4038    This is only zero for expressions killed by abnormal critical edge
4039    created by a calls.  */
4040 static sbitmap *transpout;
4041
4042 /* Nonzero for expressions that are computed (available) in the block.  */
4043 static sbitmap *comp;
4044
4045 /* Nonzero for expressions that are locally anticipatable in the block.  */
4046 static sbitmap *antloc;
4047
4048 /* Nonzero for expressions where this block is an optimal computation
4049    point.  */
4050 static sbitmap *pre_optimal;
4051
4052 /* Nonzero for expressions which are redundant in a particular block.  */
4053 static sbitmap *pre_redundant;
4054
4055 static sbitmap *temp_bitmap;
4056
4057 /* Redundant insns.  */
4058 static sbitmap pre_redundant_insns;
4059
4060 /* Allocate vars used for PRE analysis.  */
4061
4062 static void
4063 alloc_pre_mem (n_blocks, n_exprs)
4064      int n_blocks, n_exprs;
4065 {
4066   transp = sbitmap_vector_alloc (n_blocks, n_exprs);
4067   comp = sbitmap_vector_alloc (n_blocks, n_exprs);
4068   antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
4069
4070   temp_bitmap = sbitmap_vector_alloc (n_blocks, n_exprs);
4071   pre_optimal = sbitmap_vector_alloc (n_blocks, n_exprs);
4072   pre_redundant = sbitmap_vector_alloc (n_blocks, n_exprs);
4073   transpout = sbitmap_vector_alloc (n_blocks, n_exprs);
4074 }
4075
4076 /* Free vars used for PRE analysis.  */
4077
4078 static void
4079 free_pre_mem ()
4080 {
4081   free (transp);
4082   free (comp);
4083   free (antloc);
4084
4085   free (pre_optimal);
4086   free (pre_redundant);
4087   free (transpout);
4088 }
4089
4090 /* Top level routine to do the dataflow analysis needed by PRE.  */
4091
4092 static void
4093 compute_pre_data ()
4094 {
4095   compute_local_properties (transp, comp, antloc, 0);
4096   compute_transpout ();
4097   pre_lcm (n_basic_blocks, n_exprs, s_preds, s_succs, transp,
4098            antloc, pre_redundant, pre_optimal);
4099 }
4100
4101 \f
4102 /* PRE utilities */
4103
4104 /* Return non-zero if an occurrence of expression EXPR in OCCR_BB would reach
4105    block BB.
4106
4107    VISITED is a pointer to a working buffer for tracking which BB's have
4108    been visited.  It is NULL for the top-level call.
4109
4110    CHECK_PRE_COMP controls whether or not we check for a computation of
4111    EXPR in OCCR_BB.
4112
4113    We treat reaching expressions that go through blocks containing the same
4114    reaching expression as "not reaching".  E.g. if EXPR is generated in blocks
4115    2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
4116    2 as not reaching.  The intent is to improve the probability of finding
4117    only one reaching expression and to reduce register lifetimes by picking
4118    the closest such expression.  */
4119
4120 static int
4121 pre_expr_reaches_here_p (occr_bb, expr, bb, check_pre_comp, visited)
4122      int occr_bb;
4123      struct expr *expr;
4124      int bb;
4125      int check_pre_comp;
4126      char *visited;
4127 {
4128   int_list_ptr pred;
4129
4130   if (visited == NULL)
4131     {
4132       visited = (char *) alloca (n_basic_blocks);
4133       bzero (visited, n_basic_blocks);
4134     }
4135
4136   for (pred = s_preds[bb]; pred != NULL; pred = pred->next)
4137     {
4138       int pred_bb = INT_LIST_VAL (pred);
4139
4140       if (pred_bb == ENTRY_BLOCK
4141           /* Has predecessor has already been visited?  */
4142           || visited[pred_bb])
4143         {
4144           /* Nothing to do.  */
4145         }
4146       /* Does this predecessor generate this expression?  */
4147       else if ((!check_pre_comp && occr_bb == pred_bb)
4148                || TEST_BIT (comp[pred_bb], expr->bitmap_index))
4149         {
4150           /* Is this the occurrence we're looking for?
4151              Note that there's only one generating occurrence per block
4152              so we just need to check the block number.  */
4153           if (occr_bb == pred_bb)
4154             return 1;
4155           visited[pred_bb] = 1;
4156         }
4157       /* Ignore this predecessor if it kills the expression.  */
4158       else if (! TEST_BIT (transp[pred_bb], expr->bitmap_index))
4159         visited[pred_bb] = 1;
4160       /* Neither gen nor kill.  */
4161       else
4162         {
4163           visited[pred_bb] = 1;
4164           if (pre_expr_reaches_here_p (occr_bb, expr, pred_bb,
4165                                        check_pre_comp, visited))
4166             return 1;
4167         }
4168     }
4169
4170   /* All paths have been checked.  */
4171   return 0;
4172 }
4173 \f
4174 /* Add EXPR to the end of basic block BB.
4175
4176    This is used by both the PRE and code hoisting.
4177
4178    For PRE, we want to verify that the expr is either transparent
4179    or locally anticipatable in the target block.  This check makes
4180    no sense for code hoisting.  */
4181
4182 static void
4183 insert_insn_end_bb (expr, bb, pre)
4184      struct expr *expr;
4185      int bb;
4186      int pre;
4187 {
4188   rtx insn = BLOCK_END (bb);
4189   rtx new_insn;
4190   rtx reg = expr->reaching_reg;
4191   int regno = REGNO (reg);
4192   rtx pat, copied_expr;
4193   rtx first_new_insn;
4194
4195   start_sequence ();
4196   copied_expr = copy_rtx (expr->expr);
4197   emit_move_insn (reg, copied_expr);
4198   first_new_insn = get_insns ();
4199   pat = gen_sequence ();
4200   end_sequence ();
4201
4202   /* If the last insn is a jump, insert EXPR in front [taking care to
4203      handle cc0, etc. properly].  */
4204
4205   if (GET_CODE (insn) == JUMP_INSN)
4206     {
4207 #ifdef HAVE_cc0
4208       rtx note;
4209 #endif
4210
4211       /* If this is a jump table, then we can't insert stuff here.  Since
4212          we know the previous real insn must be the tablejump, we insert
4213          the new instruction just before the tablejump.  */
4214       if (GET_CODE (PATTERN (insn)) == ADDR_VEC
4215           || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC)
4216         insn = prev_real_insn (insn);
4217
4218 #ifdef HAVE_cc0
4219       /* FIXME: 'twould be nice to call prev_cc0_setter here but it aborts
4220          if cc0 isn't set.  */
4221       note = find_reg_note (insn, REG_CC_SETTER, NULL_RTX);
4222       if (note)
4223         insn = XEXP (note, 0);
4224       else
4225         {
4226           rtx maybe_cc0_setter = prev_nonnote_insn (insn);
4227           if (maybe_cc0_setter
4228               && GET_RTX_CLASS (GET_CODE (maybe_cc0_setter)) == 'i'
4229               && sets_cc0_p (PATTERN (maybe_cc0_setter)))
4230             insn = maybe_cc0_setter;
4231         }
4232 #endif
4233       /* FIXME: What if something in cc0/jump uses value set in new insn?  */
4234       new_insn = emit_insn_before (pat, insn);
4235       if (BLOCK_HEAD (bb) == insn)
4236         BLOCK_HEAD (bb) = new_insn;
4237     }
4238   /* Likewise if the last insn is a call, as will happen in the presence
4239      of exception handling.  */
4240   else if (GET_CODE (insn) == CALL_INSN)
4241     {
4242       HARD_REG_SET parm_regs;
4243       int nparm_regs;
4244       rtx p;
4245
4246       /* Keeping in mind SMALL_REGISTER_CLASSES and parameters in registers,
4247          we search backward and place the instructions before the first
4248          parameter is loaded.  Do this for everyone for consistency and a
4249          presumtion that we'll get better code elsewhere as well.  */
4250
4251       /* It should always be the case that we can put these instructions
4252          anywhere in the basic block with performing PRE optimizations.
4253          Check this.  */
4254       if (pre
4255           && !TEST_BIT (antloc[bb], expr->bitmap_index)
4256           && !TEST_BIT (transp[bb], expr->bitmap_index))
4257         abort ();
4258
4259       /* Since different machines initialize their parameter registers
4260          in different orders, assume nothing.  Collect the set of all
4261          parameter registers.  */
4262       CLEAR_HARD_REG_SET (parm_regs);
4263       nparm_regs = 0;
4264       for (p = CALL_INSN_FUNCTION_USAGE (insn); p ; p = XEXP (p, 1))
4265         if (GET_CODE (XEXP (p, 0)) == USE
4266             && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG)
4267           {
4268             int regno = REGNO (XEXP (XEXP (p, 0), 0));
4269             if (regno >= FIRST_PSEUDO_REGISTER)
4270               abort ();
4271             SET_HARD_REG_BIT (parm_regs, regno);
4272             nparm_regs++;
4273           }
4274
4275       /* Search backward for the first set of a register in this set.  */
4276       while (nparm_regs && BLOCK_HEAD (bb) != insn)
4277         {
4278           insn = PREV_INSN (insn);
4279           p = single_set (insn);
4280           if (p && GET_CODE (SET_DEST (p)) == REG
4281               && REGNO (SET_DEST (p)) < FIRST_PSEUDO_REGISTER
4282               && TEST_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p))))
4283             {
4284               CLEAR_HARD_REG_BIT (parm_regs, REGNO (SET_DEST (p)));
4285               nparm_regs--;
4286             }
4287         }
4288
4289       /* If we found all the parameter loads, then we want to insert
4290          before the first parameter load.
4291
4292          If we did not find all the parameter loads, then we might have
4293          stopped on the head of the block, which could be a CODE_LABEL.
4294          If we inserted before the CODE_LABEL, then we would be putting
4295          the insn in the wrong basic block.  In that case, put the insn
4296          after the CODE_LABEL.
4297
4298          ?!? Do we need to account for NOTE_INSN_BASIC_BLOCK here?  */
4299       if (GET_CODE (insn) != CODE_LABEL)
4300         {
4301           new_insn = emit_insn_before (pat, insn);
4302           if (BLOCK_HEAD (bb) == insn)
4303             BLOCK_HEAD (bb) = new_insn;
4304         }
4305       else
4306         {
4307           new_insn = emit_insn_after (pat, insn);
4308         }
4309     }
4310   else
4311     {
4312       new_insn = emit_insn_after (pat, insn);
4313       BLOCK_END (bb) = new_insn;
4314     }
4315
4316   /* Keep block number table up to date.
4317      Note, PAT could be a multiple insn sequence, we have to make
4318      sure that each insn in the sequence is handled.  */
4319   if (GET_CODE (pat) == SEQUENCE)
4320     {
4321       int i;
4322
4323       for (i = 0; i < XVECLEN (pat, 0); i++)
4324         {
4325           rtx insn = XVECEXP (pat, 0, i);
4326           set_block_num (insn, bb);
4327           if (GET_RTX_CLASS (GET_CODE (insn)) == 'i')
4328             add_label_notes (PATTERN (insn), new_insn);
4329           record_set_insn = insn;
4330           note_stores (PATTERN (insn), record_set_info);
4331         }
4332     }
4333   else
4334     {
4335       add_label_notes (SET_SRC (pat), new_insn);
4336       set_block_num (new_insn, bb);
4337       /* Keep register set table up to date.  */
4338       record_one_set (regno, new_insn);
4339     }
4340
4341   gcse_create_count++;
4342
4343   if (gcse_file)
4344     {
4345       fprintf (gcse_file, "PRE/HOIST: end of bb %d, insn %d, copying expression %d to reg %d\n",
4346                bb, INSN_UID (new_insn), expr->bitmap_index, regno);
4347     }
4348 }
4349
4350 /* Insert partially redundant expressions at the ends of appropriate basic
4351    blocks making them fully redundant.  */
4352
4353 static void
4354 pre_insert (index_map)
4355      struct expr **index_map;
4356 {
4357   int bb, i, set_size;
4358   sbitmap *inserted;
4359
4360   /* Compute INSERT = PRE_OPTIMAL & ~PRE_REDUNDANT.
4361      Where INSERT is nonzero, we add the expression at the end of the basic
4362      block if it reaches any of the deleted expressions.  */
4363
4364   set_size = pre_optimal[0]->size;
4365   inserted = sbitmap_vector_alloc (n_basic_blocks, n_exprs);
4366   sbitmap_vector_zero (inserted, n_basic_blocks);
4367
4368   for (bb = 0; bb < n_basic_blocks; bb++)
4369     {
4370       int indx;
4371
4372       /* This computes the number of potential insertions we need.  */
4373       sbitmap_not (temp_bitmap[bb], pre_redundant[bb]);
4374       sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_optimal[bb]);
4375
4376       /* TEMP_BITMAP[bb] now contains a bitmap of the expressions that we need
4377          to insert at the end of this basic block.  */
4378       for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
4379         {
4380           SBITMAP_ELT_TYPE insert = temp_bitmap[bb]->elms[i];
4381           int j;
4382
4383           for (j = indx; insert && j < n_exprs; j++, insert >>= 1)
4384             {
4385               if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
4386                 {
4387                   struct expr *expr = index_map[j];
4388                   struct occr *occr;
4389
4390                   /* Now look at each deleted occurence of this expression.  */
4391                   for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4392                     {
4393                       if (! occr->deleted_p)
4394                         continue;
4395
4396                       /* Insert this expression at the end of BB if it would
4397                          reach the deleted occurence.  */
4398                       if (!TEST_BIT (inserted[bb], j)
4399                           && pre_expr_reaches_here_p (bb, expr,
4400                                                    BLOCK_NUM (occr->insn), 0,
4401                                                    NULL))
4402                         {
4403                           SET_BIT (inserted[bb], j);
4404                           insert_insn_end_bb (index_map[j], bb, 1);
4405                         }
4406                     }
4407                 }
4408             }
4409         }
4410     }
4411 }
4412
4413 /* Copy the result of INSN to REG.
4414    INDX is the expression number.  */
4415
4416 static void
4417 pre_insert_copy_insn (expr, insn)
4418      struct expr *expr;
4419      rtx insn;
4420 {
4421   rtx reg = expr->reaching_reg;
4422   int regno = REGNO (reg);
4423   int indx = expr->bitmap_index;
4424   rtx set = single_set (insn);
4425   rtx new_insn;
4426
4427   if (!set)
4428     abort ();
4429   new_insn = emit_insn_after (gen_rtx_SET (VOIDmode, reg, SET_DEST (set)),
4430                               insn);
4431   /* Keep block number table up to date.  */
4432   set_block_num (new_insn, BLOCK_NUM (insn));
4433   /* Keep register set table up to date.  */
4434   record_one_set (regno, new_insn);
4435
4436   gcse_create_count++;
4437
4438   if (gcse_file)
4439     {
4440       fprintf (gcse_file, "PRE: bb %d, insn %d, copying expression %d in insn %d to reg %d\n",
4441                BLOCK_NUM (insn), INSN_UID (new_insn), indx, INSN_UID (insn), regno);
4442     }
4443 }
4444
4445 /* Copy available expressions that reach the redundant expression
4446    to `reaching_reg'.  */
4447
4448 static void
4449 pre_insert_copies ()
4450 {
4451   int i, bb;
4452
4453   for (bb = 0; bb < n_basic_blocks; bb++)
4454     {
4455       sbitmap_a_and_b (temp_bitmap[bb], pre_optimal[bb], pre_redundant[bb]);
4456     }
4457
4458   /* For each available expression in the table, copy the result to
4459      `reaching_reg' if the expression reaches a deleted one.
4460
4461      ??? The current algorithm is rather brute force.
4462      Need to do some profiling.  */
4463
4464   for (i = 0; i < expr_hash_table_size; i++)
4465     {
4466       struct expr *expr;
4467
4468       for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4469         {
4470           struct occr *occr;
4471
4472           /* If the basic block isn't reachable, PPOUT will be TRUE.
4473              However, we don't want to insert a copy here because the
4474              expression may not really be redundant.  So only insert
4475              an insn if the expression was deleted.
4476              This test also avoids further processing if the expression
4477              wasn't deleted anywhere.  */
4478           if (expr->reaching_reg == NULL)
4479             continue;
4480
4481           for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4482             {
4483               struct occr *avail;
4484
4485               if (! occr->deleted_p)
4486                 continue;
4487
4488               for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
4489                 {
4490                   rtx insn = avail->insn;
4491                   int bb = BLOCK_NUM (insn);
4492
4493                   if (!TEST_BIT (temp_bitmap[bb], expr->bitmap_index))
4494                     continue;
4495
4496                   /* No need to handle this one if handled already.  */
4497                   if (avail->copied_p)
4498                     continue;
4499                   /* Don't handle this one if it's a redundant one.  */
4500                   if (TEST_BIT (pre_redundant_insns, INSN_CUID (insn)))
4501                     continue;
4502                   /* Or if the expression doesn't reach the deleted one.  */
4503                   if (! pre_expr_reaches_here_p (BLOCK_NUM (avail->insn), expr,
4504                                                  BLOCK_NUM (occr->insn),
4505                                                  1, NULL))
4506                     continue;
4507
4508                   /* Copy the result of avail to reaching_reg.  */
4509                   pre_insert_copy_insn (expr, insn);
4510                   avail->copied_p = 1;
4511                 }
4512             }
4513         }
4514     }
4515 }
4516
4517 /* Delete redundant computations.
4518    Deletion is done by changing the insn to copy the `reaching_reg' of
4519    the expression into the result of the SET.  It is left to later passes
4520    (cprop, cse2, flow, combine, regmove) to propagate the copy or eliminate it.
4521
4522    Returns non-zero if a change is made.  */
4523
4524 static int
4525 pre_delete ()
4526 {
4527   int i, bb, changed;
4528
4529   /* Compute the expressions which are redundant and need to be replaced by
4530      copies from the reaching reg to the target reg.  */
4531   for (bb = 0; bb < n_basic_blocks; bb++)
4532     {
4533       sbitmap_not (temp_bitmap[bb], pre_optimal[bb]);
4534       sbitmap_a_and_b (temp_bitmap[bb], temp_bitmap[bb], pre_redundant[bb]);
4535     }
4536
4537   changed = 0;
4538   for (i = 0; i < expr_hash_table_size; i++)
4539     {
4540       struct expr *expr;
4541
4542       for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4543         {
4544           struct occr *occr;
4545           int indx = expr->bitmap_index;
4546
4547           /* We only need to search antic_occr since we require
4548              ANTLOC != 0.  */
4549
4550           for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
4551             {
4552               rtx insn = occr->insn;
4553               rtx set;
4554               int bb = BLOCK_NUM (insn);
4555
4556               if (TEST_BIT (temp_bitmap[bb], indx))
4557                 {
4558                   set = single_set (insn);
4559                   if (! set)
4560                     abort ();
4561
4562                   /* Create a pseudo-reg to store the result of reaching
4563                      expressions into.  Get the mode for the new pseudo
4564                      from the mode of the original destination pseudo.  */
4565                   if (expr->reaching_reg == NULL)
4566                     expr->reaching_reg
4567                       = gen_reg_rtx (GET_MODE (SET_DEST (set)));
4568
4569                   /* In theory this should never fail since we're creating
4570                      a reg->reg copy.
4571
4572                      However, on the x86 some of the movXX patterns actually
4573                      contain clobbers of scratch regs.  This may cause the
4574                      insn created by validate_change to not match any pattern
4575                      and thus cause validate_change to fail.   */
4576                   if (validate_change (insn, &SET_SRC (set),
4577                                        expr->reaching_reg, 0))
4578                     {
4579                       occr->deleted_p = 1;
4580                       SET_BIT (pre_redundant_insns, INSN_CUID (insn));
4581                       changed = 1;
4582                       gcse_subst_count++;
4583                     }
4584
4585                   if (gcse_file)
4586                     {
4587                       fprintf (gcse_file,
4588                                "PRE: redundant insn %d (expression %d) in bb %d, reaching reg is %d\n",
4589                                INSN_UID (insn), indx, bb, REGNO (expr->reaching_reg));
4590                     }
4591                 }
4592             }
4593         }
4594     }
4595
4596   return changed;
4597 }
4598
4599 /* Perform GCSE optimizations using PRE.
4600    This is called by one_pre_gcse_pass after all the dataflow analysis
4601    has been done.
4602
4603    This is based on the original Morel-Renvoise paper Fred Chow's thesis,
4604    and lazy code motion from Knoop, Ruthing and Steffen as described in
4605    Advanced Compiler Design and Implementation.
4606
4607    ??? A new pseudo reg is created to hold the reaching expression.
4608    The nice thing about the classical approach is that it would try to
4609    use an existing reg.  If the register can't be adequately optimized
4610    [i.e. we introduce reload problems], one could add a pass here to
4611    propagate the new register through the block.
4612
4613    ??? We don't handle single sets in PARALLELs because we're [currently]
4614    not able to copy the rest of the parallel when we insert copies to create
4615    full redundancies from partial redundancies.  However, there's no reason
4616    why we can't handle PARALLELs in the cases where there are no partial
4617    redundancies.  */
4618
4619 static int
4620 pre_gcse ()
4621 {
4622   int i;
4623   int changed;
4624   struct expr **index_map;
4625
4626   /* Compute a mapping from expression number (`bitmap_index') to
4627      hash table entry.  */
4628
4629   index_map = (struct expr **) alloca (n_exprs * sizeof (struct expr *));
4630   bzero ((char *) index_map, n_exprs * sizeof (struct expr *));
4631   for (i = 0; i < expr_hash_table_size; i++)
4632     {
4633       struct expr *expr;
4634
4635       for (expr = expr_hash_table[i]; expr != NULL; expr = expr->next_same_hash)
4636         index_map[expr->bitmap_index] = expr;
4637     }
4638
4639   /* Reset bitmap used to track which insns are redundant.  */
4640   pre_redundant_insns = sbitmap_alloc (max_cuid);
4641   sbitmap_zero (pre_redundant_insns);
4642
4643   /* Delete the redundant insns first so that
4644      - we know what register to use for the new insns and for the other
4645        ones with reaching expressions
4646      - we know which insns are redundant when we go to create copies  */
4647   changed = pre_delete ();
4648
4649   /* Insert insns in places that make partially redundant expressions
4650      fully redundant.  */
4651   pre_insert (index_map);
4652
4653   /* In other places with reaching expressions, copy the expression to the
4654      specially allocated pseudo-reg that reaches the redundant expression.  */
4655   pre_insert_copies ();
4656
4657   free (pre_redundant_insns);
4658
4659   return changed;
4660 }
4661
4662 /* Top level routine to perform one PRE GCSE pass.
4663
4664    Return non-zero if a change was made.  */
4665
4666 static int
4667 one_pre_gcse_pass (pass)
4668      int pass;
4669 {
4670   int changed = 0;
4671
4672   gcse_subst_count = 0;
4673   gcse_create_count = 0;
4674
4675   alloc_expr_hash_table (max_cuid);
4676   compute_expr_hash_table ();
4677   if (gcse_file)
4678     dump_hash_table (gcse_file, "Expression", expr_hash_table,
4679                      expr_hash_table_size, n_exprs);
4680   if (n_exprs > 0)
4681     {
4682       alloc_pre_mem (n_basic_blocks, n_exprs);
4683       compute_pre_data ();
4684       changed |= pre_gcse ();
4685       free_pre_mem ();
4686     }
4687   free_expr_hash_table ();
4688
4689   if (gcse_file)
4690     {
4691       fprintf (gcse_file, "\n");
4692       fprintf (gcse_file, "PRE GCSE of %s, pass %d: %d bytes needed, %d substs, %d insns created\n",
4693                current_function_name, pass,
4694                bytes_used, gcse_subst_count, gcse_create_count);
4695     }
4696
4697   return changed;
4698 }
4699 \f
4700 /* If X contains any LABEL_REF's, add REG_LABEL notes for them to INSN.
4701    We have to add REG_LABEL notes, because the following loop optimization
4702    pass requires them.  */
4703
4704 /* ??? This is very similar to the loop.c add_label_notes function.  We
4705    could probably share code here.  */
4706
4707 /* ??? If there was a jump optimization pass after gcse and before loop,
4708    then we would not need to do this here, because jump would add the
4709    necessary REG_LABEL notes.  */
4710
4711 static void
4712 add_label_notes (x, insn)
4713      rtx x;
4714      rtx insn;
4715 {
4716   enum rtx_code code = GET_CODE (x);
4717   int i, j;
4718   const char *fmt;
4719
4720   if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
4721     {
4722       /* This code used to ignore labels that referred to dispatch tables to
4723          avoid flow generating (slighly) worse code.
4724
4725          We no longer ignore such label references (see LABEL_REF handling in
4726          mark_jump_label for additional information).  */
4727       REG_NOTES (insn) = gen_rtx_EXPR_LIST (REG_LABEL, XEXP (x, 0),
4728                                             REG_NOTES (insn));
4729       return;
4730     }
4731
4732   fmt = GET_RTX_FORMAT (code);
4733   for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
4734     {
4735       if (fmt[i] == 'e')
4736         add_label_notes (XEXP (x, i), insn);
4737       else if (fmt[i] == 'E')
4738         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
4739           add_label_notes (XVECEXP (x, i, j), insn);
4740     }
4741 }
4742
4743 /* Compute transparent outgoing information for each block.
4744
4745    An expression is transparent to an edge unless it is killed by
4746    the edge itself.  This can only happen with abnormal control flow,
4747    when the edge is traversed through a call.  This happens with
4748    non-local labels and exceptions.
4749
4750    This would not be necessary if we split the edge.  While this is
4751    normally impossible for abnormal critical edges, with some effort
4752    it should be possible with exception handling, since we still have
4753    control over which handler should be invoked.  But due to increased
4754    EH table sizes, this may not be worthwhile.  */
4755
4756 static void
4757 compute_transpout ()
4758 {
4759   int bb;
4760
4761   sbitmap_vector_ones (transpout, n_basic_blocks);
4762
4763   for (bb = 0; bb < n_basic_blocks; ++bb)
4764     {
4765       int i;
4766
4767       /* Note that flow inserted a nop a the end of basic blocks that
4768          end in call instructions for reasons other than abnormal
4769          control flow.  */
4770       if (GET_CODE (BLOCK_END (bb)) != CALL_INSN)
4771         continue;
4772
4773       for (i = 0; i < expr_hash_table_size; i++)
4774         {
4775           struct expr *expr;
4776           for (expr = expr_hash_table[i]; expr ; expr = expr->next_same_hash)
4777             if (GET_CODE (expr->expr) == MEM)
4778               {
4779                 rtx addr = XEXP (expr->expr, 0);
4780
4781                 if (GET_CODE (addr) == SYMBOL_REF
4782                     && CONSTANT_POOL_ADDRESS_P (addr))
4783                   continue;
4784
4785                 /* ??? Optimally, we would use interprocedural alias
4786                    analysis to determine if this mem is actually killed
4787                    by this call.  */
4788                 RESET_BIT (transpout[bb], expr->bitmap_index);
4789               }
4790         }
4791     }
4792 }