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