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