LCOV - code coverage report
Current view: top level - gcc - gcse.cc (source / functions) Coverage Total Hit
Test: gcc.info Lines: 92.5 % 1501 1389
Test Date: 2026-11-14 16:39:50 Functions: 91.6 % 95 87
Legend: Lines:     hit not hit

            Line data    Source code
       1              : /* Partial redundancy elimination / Hoisting for RTL.
       2              :    Copyright (C) 1997-2026 Free Software Foundation, Inc.
       3              : 
       4              : This file is part of GCC.
       5              : 
       6              : GCC is free software; you can redistribute it and/or modify it under
       7              : the terms of the GNU General Public License as published by the Free
       8              : Software Foundation; either version 3, or (at your option) any later
       9              : version.
      10              : 
      11              : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      12              : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      13              : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      14              : for more details.
      15              : 
      16              : You should have received a copy of the GNU General Public License
      17              : along with GCC; see the file COPYING3.  If not see
      18              : <http://www.gnu.org/licenses/>.  */
      19              : 
      20              : /* TODO
      21              :    - reordering of memory allocation and freeing to be more space efficient
      22              :    - calc rough register pressure information and use the info to drive all
      23              :      kinds of code motion (including code hoisting) in a unified way.
      24              : */
      25              : 
      26              : /* References searched while implementing this.
      27              : 
      28              :    Compilers Principles, Techniques and Tools
      29              :    Aho, Sethi, Ullman
      30              :    Addison-Wesley, 1988
      31              : 
      32              :    Global Optimization by Suppression of Partial Redundancies
      33              :    E. Morel, C. Renvoise
      34              :    communications of the acm, Vol. 22, Num. 2, Feb. 1979
      35              : 
      36              :    A Portable Machine-Independent Global Optimizer - Design and Measurements
      37              :    Frederick Chow
      38              :    Stanford Ph.D. thesis, Dec. 1983
      39              : 
      40              :    A Fast Algorithm for Code Movement Optimization
      41              :    D.M. Dhamdhere
      42              :    SIGPLAN Notices, Vol. 23, Num. 10, Oct. 1988
      43              : 
      44              :    A Solution to a Problem with Morel and Renvoise's
      45              :    Global Optimization by Suppression of Partial Redundancies
      46              :    K-H Drechsler, M.P. Stadel
      47              :    ACM TOPLAS, Vol. 10, Num. 4, Oct. 1988
      48              : 
      49              :    Practical Adaptation of the Global Optimization
      50              :    Algorithm of Morel and Renvoise
      51              :    D.M. Dhamdhere
      52              :    ACM TOPLAS, Vol. 13, Num. 2. Apr. 1991
      53              : 
      54              :    Efficiently Computing Static Single Assignment Form and the Control
      55              :    Dependence Graph
      56              :    R. Cytron, J. Ferrante, B.K. Rosen, M.N. Wegman, and F.K. Zadeck
      57              :    ACM TOPLAS, Vol. 13, Num. 4, Oct. 1991
      58              : 
      59              :    Lazy Code Motion
      60              :    J. Knoop, O. Ruthing, B. Steffen
      61              :    ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
      62              : 
      63              :    What's In a Region?  Or Computing Control Dependence Regions in Near-Linear
      64              :    Time for Reducible Flow Control
      65              :    Thomas Ball
      66              :    ACM Letters on Programming Languages and Systems,
      67              :    Vol. 2, Num. 1-4, Mar-Dec 1993
      68              : 
      69              :    An Efficient Representation for Sparse Sets
      70              :    Preston Briggs, Linda Torczon
      71              :    ACM Letters on Programming Languages and Systems,
      72              :    Vol. 2, Num. 1-4, Mar-Dec 1993
      73              : 
      74              :    A Variation of Knoop, Ruthing, and Steffen's Lazy Code Motion
      75              :    K-H Drechsler, M.P. Stadel
      76              :    ACM SIGPLAN Notices, Vol. 28, Num. 5, May 1993
      77              : 
      78              :    Partial Dead Code Elimination
      79              :    J. Knoop, O. Ruthing, B. Steffen
      80              :    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
      81              : 
      82              :    Effective Partial Redundancy Elimination
      83              :    P. Briggs, K.D. Cooper
      84              :    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
      85              : 
      86              :    The Program Structure Tree: Computing Control Regions in Linear Time
      87              :    R. Johnson, D. Pearson, K. Pingali
      88              :    ACM SIGPLAN Notices, Vol. 29, Num. 6, Jun. 1994
      89              : 
      90              :    Optimal Code Motion: Theory and Practice
      91              :    J. Knoop, O. Ruthing, B. Steffen
      92              :    ACM TOPLAS, Vol. 16, Num. 4, Jul. 1994
      93              : 
      94              :    The power of assignment motion
      95              :    J. Knoop, O. Ruthing, B. Steffen
      96              :    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
      97              : 
      98              :    Global code motion / global value numbering
      99              :    C. Click
     100              :    ACM SIGPLAN Notices Vol. 30, Num. 6, Jun. 1995, '95 Conference on PLDI
     101              : 
     102              :    Value Driven Redundancy Elimination
     103              :    L.T. Simpson
     104              :    Rice University Ph.D. thesis, Apr. 1996
     105              : 
     106              :    Value Numbering
     107              :    L.T. Simpson
     108              :    Massively Scalar Compiler Project, Rice University, Sep. 1996
     109              : 
     110              :    High Performance Compilers for Parallel Computing
     111              :    Michael Wolfe
     112              :    Addison-Wesley, 1996
     113              : 
     114              :    Advanced Compiler Design and Implementation
     115              :    Steven Muchnick
     116              :    Morgan Kaufmann, 1997
     117              : 
     118              :    Building an Optimizing Compiler
     119              :    Robert Morgan
     120              :    Digital Press, 1998
     121              : 
     122              :    People wishing to speed up the code here should read:
     123              :      Elimination Algorithms for Data Flow Analysis
     124              :      B.G. Ryder, M.C. Paull
     125              :      ACM Computing Surveys, Vol. 18, Num. 3, Sep. 1986
     126              : 
     127              :      How to Analyze Large Programs Efficiently and Informatively
     128              :      D.M. Dhamdhere, B.K. Rosen, F.K. Zadeck
     129              :      ACM SIGPLAN Notices Vol. 27, Num. 7, Jul. 1992, '92 Conference on PLDI
     130              : 
     131              :    People wishing to do something different can find various possibilities
     132              :    in the above papers and elsewhere.
     133              : */
     134              : 
     135              : #include "config.h"
     136              : #include "system.h"
     137              : #include "coretypes.h"
     138              : #include "backend.h"
     139              : #include "target.h"
     140              : #include "rtl.h"
     141              : #include "tree.h"
     142              : #include "predict.h"
     143              : #include "df.h"
     144              : #include "memmodel.h"
     145              : #include "tm_p.h"
     146              : #include "insn-config.h"
     147              : #include "print-rtl.h"
     148              : #include "regs.h"
     149              : #include "ira.h"
     150              : #include "recog.h"
     151              : #include "diagnostic-core.h"
     152              : #include "cfgrtl.h"
     153              : #include "cfganal.h"
     154              : #include "lcm.h"
     155              : #include "cfgcleanup.h"
     156              : #include "expr.h"
     157              : #include "intl.h"
     158              : #include "tree-pass.h"
     159              : #include "dbgcnt.h"
     160              : #include "gcse.h"
     161              : #include "gcse-common.h"
     162              : #include "function-abi.h"
     163              : 
     164              : /* We support GCSE via Partial Redundancy Elimination.  PRE optimizations
     165              :    are a superset of those done by classic GCSE.
     166              : 
     167              :    Two passes of copy/constant propagation are done around PRE or hoisting
     168              :    because the first one enables more GCSE and the second one helps to clean
     169              :    up the copies that PRE and HOIST create.  This is needed more for PRE than
     170              :    for HOIST because code hoisting will try to use an existing register
     171              :    containing the common subexpression rather than create a new one.  This is
     172              :    harder to do for PRE because of the code motion (which HOIST doesn't do).
     173              : 
     174              :    Expressions we are interested in GCSE-ing are of the form
     175              :    (set (pseudo-reg) (expression)).
     176              :    Function want_to_gcse_p says what these are.
     177              : 
     178              :    In addition, expressions in REG_EQUAL notes are candidates for GCSE-ing.
     179              :    This allows PRE to hoist expressions that are expressed in multiple insns,
     180              :    such as complex address calculations (e.g. for PIC code, or loads with a
     181              :    high part and a low part).
     182              : 
     183              :    PRE handles moving invariant expressions out of loops (by treating them as
     184              :    partially redundant).
     185              : 
     186              :    **********************
     187              : 
     188              :    We used to support multiple passes but there are diminishing returns in
     189              :    doing so.  The first pass usually makes 90% of the changes that are doable.
     190              :    A second pass can make a few more changes made possible by the first pass.
     191              :    Experiments show any further passes don't make enough changes to justify
     192              :    the expense.
     193              : 
     194              :    A study of spec92 using an unlimited number of passes:
     195              :    [1 pass] = 1208 substitutions, [2] = 577, [3] = 202, [4] = 192, [5] = 83,
     196              :    [6] = 34, [7] = 17, [8] = 9, [9] = 4, [10] = 4, [11] = 2,
     197              :    [12] = 2, [13] = 1, [15] = 1, [16] = 2, [41] = 1
     198              : 
     199              :    It was found doing copy propagation between each pass enables further
     200              :    substitutions.
     201              : 
     202              :    This study was done before expressions in REG_EQUAL notes were added as
     203              :    candidate expressions for optimization, and before the GIMPLE optimizers
     204              :    were added.  Probably, multiple passes is even less efficient now than
     205              :    at the time when the study was conducted.
     206              : 
     207              :    PRE is quite expensive in complicated functions because the DFA can take
     208              :    a while to converge.  Hence we only perform one pass.
     209              : 
     210              :    **********************
     211              : 
     212              :    The steps for PRE are:
     213              : 
     214              :    1) Build the hash table of expressions we wish to GCSE (expr_hash_table).
     215              : 
     216              :    2) Perform the data flow analysis for PRE.
     217              : 
     218              :    3) Delete the redundant instructions
     219              : 
     220              :    4) Insert the required copies [if any] that make the partially
     221              :       redundant instructions fully redundant.
     222              : 
     223              :    5) For other reaching expressions, insert an instruction to copy the value
     224              :       to a newly created pseudo that will reach the redundant instruction.
     225              : 
     226              :    The deletion is done first so that when we do insertions we
     227              :    know which pseudo reg to use.
     228              : 
     229              :    Various papers have argued that PRE DFA is expensive (O(n^2)) and others
     230              :    argue it is not.  The number of iterations for the algorithm to converge
     231              :    is typically 2-4 so I don't view it as that expensive (relatively speaking).
     232              : 
     233              :    PRE GCSE depends heavily on the second CPROP pass to clean up the copies
     234              :    we create.  To make an expression reach the place where it's redundant,
     235              :    the result of the expression is copied to a new register, and the redundant
     236              :    expression is deleted by replacing it with this new register.  Classic GCSE
     237              :    doesn't have this problem as much as it computes the reaching defs of
     238              :    each register in each block and thus can try to use an existing
     239              :    register.  */
     240              : 
     241              : /* GCSE global vars.  */
     242              : 
     243              : struct target_gcse default_target_gcse;
     244              : #if SWITCHABLE_TARGET
     245              : struct target_gcse *this_target_gcse = &default_target_gcse;
     246              : #endif
     247              : 
     248              : /* Set to non-zero if CSE should run after all GCSE optimizations are done.  */
     249              : int flag_rerun_cse_after_global_opts;
     250              : 
     251              : /* An obstack for our working variables.  */
     252              : static struct obstack gcse_obstack;
     253              : 
     254              : /* Hash table of expressions.  */
     255              : 
     256              : struct gcse_expr
     257              : {
     258              :   /* The expression.  */
     259              :   rtx expr;
     260              :   /* Index in the available expression bitmaps.  */
     261              :   int bitmap_index;
     262              :   /* Next entry with the same hash.  */
     263              :   struct gcse_expr *next_same_hash;
     264              :   /* List of anticipatable occurrences in basic blocks in the function.
     265              :      An "anticipatable occurrence" is one that is the first occurrence in the
     266              :      basic block, the operands are not modified in the basic block prior
     267              :      to the occurrence and the output is not used between the start of
     268              :      the block and the occurrence.  */
     269              :   struct gcse_occr *antic_occr;
     270              :   /* List of available occurrence in basic blocks in the function.
     271              :      An "available occurrence" is one that is the last occurrence in the
     272              :      basic block and the operands are not modified by following statements in
     273              :      the basic block [including this insn].  */
     274              :   struct gcse_occr *avail_occr;
     275              :   /* Non-null if the computation is PRE redundant.
     276              :      The value is the newly created pseudo-reg to record a copy of the
     277              :      expression in all the places that reach the redundant copy.  */
     278              :   rtx reaching_reg;
     279              :   /* Maximum distance in instructions this expression can travel.
     280              :      We avoid moving simple expressions for more than a few instructions
     281              :      to keep register pressure under control.
     282              :      A value of "0" removes restrictions on how far the expression can
     283              :      travel.  */
     284              :   HOST_WIDE_INT max_distance;
     285              : };
     286              : 
     287              : /* Occurrence of an expression.
     288              :    There is one per basic block.  If a pattern appears more than once the
     289              :    last appearance is used [or first for anticipatable expressions].  */
     290              : 
     291              : struct gcse_occr
     292              : {
     293              :   /* Next occurrence of this expression.  */
     294              :   struct gcse_occr *next;
     295              :   /* The insn that computes the expression.  */
     296              :   rtx_insn *insn;
     297              :   /* Nonzero if this [anticipatable] occurrence has been deleted.  */
     298              :   char deleted_p;
     299              :   /* Nonzero if this [available] occurrence has been copied to
     300              :      reaching_reg.  */
     301              :   /* ??? This is mutually exclusive with deleted_p, so they could share
     302              :      the same byte.  */
     303              :   char copied_p;
     304              : };
     305              : 
     306              : typedef struct gcse_occr *occr_t;
     307              : 
     308              : /* Expression hash tables.
     309              :    Each hash table is an array of buckets.
     310              :    ??? It is known that if it were an array of entries, structure elements
     311              :    `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
     312              :    not clear whether in the final analysis a sufficient amount of memory would
     313              :    be saved as the size of the available expression bitmaps would be larger
     314              :    [one could build a mapping table without holes afterwards though].
     315              :    Someday I'll perform the computation and figure it out.  */
     316              : 
     317              : struct gcse_hash_table_d
     318              : {
     319              :   /* The table itself.
     320              :      This is an array of `expr_hash_table_size' elements.  */
     321              :   struct gcse_expr **table;
     322              : 
     323              :   /* Size of the hash table, in elements.  */
     324              :   unsigned int size;
     325              : 
     326              :   /* Number of hash table elements.  */
     327              :   unsigned int n_elems;
     328              : };
     329              : 
     330              : /* Expression hash table.  */
     331              : static struct gcse_hash_table_d expr_hash_table;
     332              : 
     333              : /* This is a list of expressions which are MEMs and will be used by load
     334              :    or store motion.
     335              :    Load motion tracks MEMs which aren't killed by anything except itself,
     336              :    i.e. loads and stores to a single location.
     337              :    We can then allow movement of these MEM refs with a little special
     338              :    allowance. (all stores copy the same value to the reaching reg used
     339              :    for the loads).  This means all values used to store into memory must have
     340              :    no side effects so we can re-issue the setter value.  */
     341              : 
     342              : struct ls_expr
     343              : {
     344              :   struct gcse_expr * expr;      /* Gcse expression reference for LM.  */
     345              :   rtx pattern;                  /* Pattern of this mem.  */
     346              :   rtx pattern_regs;             /* List of registers mentioned by the mem.  */
     347              :   vec<rtx_insn *> stores; /* INSN list of stores seen.  */
     348              :   struct ls_expr * next;        /* Next in the list.  */
     349              :   int invalid;                  /* Invalid for some reason.  */
     350              :   int index;                    /* If it maps to a bitmap index.  */
     351              :   unsigned int hash_index;      /* Index when in a hash table.  */
     352              :   rtx reaching_reg;             /* Register to use when re-writing.  */
     353              : };
     354              : 
     355              : /* Head of the list of load/store memory refs.  */
     356              : static struct ls_expr * pre_ldst_mems = NULL;
     357              : 
     358              : struct pre_ldst_expr_hasher : nofree_ptr_hash <ls_expr>
     359              : {
     360              :   typedef value_type compare_type;
     361              :   static inline hashval_t hash (const ls_expr *);
     362              :   static inline bool equal (const ls_expr *, const ls_expr *);
     363              : };
     364              : 
     365              : /* Hashtable helpers.  */
     366              : inline hashval_t
     367    104227976 : pre_ldst_expr_hasher::hash (const ls_expr *x)
     368              : {
     369    104227976 :   int do_not_record_p = 0;
     370    104227976 :   return
     371    104227976 :     hash_rtx (x->pattern, GET_MODE (x->pattern), &do_not_record_p, NULL, false);
     372              : }
     373              : 
     374              : static bool expr_equiv_p (const_rtx, const_rtx);
     375              : 
     376              : inline bool
     377    124058320 : pre_ldst_expr_hasher::equal (const ls_expr *ptr1,
     378              :                              const ls_expr *ptr2)
     379              : {
     380    124058320 :   return expr_equiv_p (ptr1->pattern, ptr2->pattern);
     381              : }
     382              : 
     383              : /* Hashtable for the load/store memory refs.  */
     384              : static hash_table<pre_ldst_expr_hasher> *pre_ldst_table;
     385              : 
     386              : /* Bitmap containing one bit for each register in the program.
     387              :    Used when performing GCSE to track which registers have been set since
     388              :    the start of the basic block.  */
     389              : static regset reg_set_bitmap;
     390              : 
     391              : /* Array, indexed by basic block number for a list of insns which modify
     392              :    memory within that block.  */
     393              : static vec<rtx_insn *> *modify_mem_list;
     394              : static bitmap modify_mem_list_set;
     395              : 
     396              : /* This array parallels modify_mem_list, except that it stores MEMs
     397              :    being set and their canonicalized memory addresses.  */
     398              : static vec<modify_pair> *canon_modify_mem_list;
     399              : 
     400              : /* Bitmap indexed by block numbers to record which blocks contain
     401              :    function calls.  */
     402              : static bitmap blocks_with_calls;
     403              : 
     404              : /* Various variables for statistics gathering.  */
     405              : 
     406              : /* Memory used in a pass.
     407              :    This isn't intended to be absolutely precise.  Its intent is only
     408              :    to keep an eye on memory usage.  */
     409              : static int bytes_used;
     410              : 
     411              : /* GCSE substitutions made.  */
     412              : static int gcse_subst_count;
     413              : /* Number of copy instructions created.  */
     414              : static int gcse_create_count;
     415              : 
     416              : /* Doing code hoisting.  */
     417              : static bool doing_code_hoisting_p = false;
     418              : 
     419              : /* Doing hardreg_pre.  */
     420              : static bool doing_hardreg_pre_p = false;
     421              : 
     422              : inline bool
     423     23050923 : do_load_motion ()
     424              : {
     425     23050881 :   return flag_gcse_lm && !doing_hardreg_pre_p;
     426              : }
     427              : 
     428              : static unsigned int current_hardreg_regno;
     429              : 
     430              : /* For available exprs */
     431              : static sbitmap *ae_kill;
     432              : 
     433              : /* Data stored for each basic block.  */
     434              : struct bb_data
     435              : {
     436              :   /* Maximal register pressure inside basic block for given register class
     437              :      (defined only for the pressure classes).  */
     438              :   int max_reg_pressure[N_REG_CLASSES];
     439              :   /* Recorded register pressure of basic block before trying to hoist
     440              :      an expression.  Will be used to restore the register pressure
     441              :      if the expression should not be hoisted.  */
     442              :   int old_pressure;
     443              :   /* Recorded register live_in info of basic block during code hoisting
     444              :      process.  BACKUP is used to record live_in info before trying to
     445              :      hoist an expression, and will be used to restore LIVE_IN if the
     446              :      expression should not be hoisted.  */
     447              :   bitmap live_in, backup;
     448              : };
     449              : 
     450              : #define BB_DATA(bb) ((struct bb_data *) (bb)->aux)
     451              : 
     452              : static basic_block curr_bb;
     453              : 
     454              : /* Current register pressure for each pressure class.  */
     455              : static int curr_reg_pressure[N_REG_CLASSES];
     456              : 
     457              : 
     458              : static void compute_can_copy (void);
     459              : static void *gmalloc (size_t) ATTRIBUTE_MALLOC;
     460              : static void *gcalloc (size_t, size_t) ATTRIBUTE_MALLOC;
     461              : static void *gcse_alloc (unsigned long);
     462              : static void alloc_gcse_mem (void);
     463              : static void free_gcse_mem (void);
     464              : static void hash_scan_insn (rtx_insn *, struct gcse_hash_table_d *);
     465              : static void hash_scan_set (rtx, rtx_insn *, struct gcse_hash_table_d *);
     466              : static void hash_scan_clobber (rtx, rtx_insn *, struct gcse_hash_table_d *);
     467              : static void hash_scan_call (rtx, rtx_insn *, struct gcse_hash_table_d *);
     468              : static bool oprs_unchanged_p (const_rtx, const rtx_insn *, bool);
     469              : static bool oprs_anticipatable_p (const_rtx, const rtx_insn *);
     470              : static bool oprs_available_p (const_rtx, const rtx_insn *);
     471              : static void insert_expr_in_table (rtx, machine_mode, rtx_insn *, bool, bool,
     472              :                                   HOST_WIDE_INT, struct gcse_hash_table_d *);
     473              : static unsigned int hash_expr (const_rtx, machine_mode, int *, int);
     474              : static void record_last_reg_set_info (rtx_insn *, int);
     475              : static void record_last_mem_set_info (rtx_insn *);
     476              : static void record_last_set_info (rtx, const_rtx, void *);
     477              : static void compute_hash_table (struct gcse_hash_table_d *);
     478              : static void alloc_hash_table (struct gcse_hash_table_d *);
     479              : static void free_hash_table (struct gcse_hash_table_d *);
     480              : static void compute_hash_table_work (struct gcse_hash_table_d *);
     481              : static void dump_hash_table (FILE *, const char *, struct gcse_hash_table_d *);
     482              : static void compute_local_properties (sbitmap *, sbitmap *, sbitmap *,
     483              :                                       struct gcse_hash_table_d *);
     484              : static void mems_conflict_for_gcse_p (rtx, const_rtx, void *);
     485              : static bool load_killed_in_block_p (const_basic_block, int, const_rtx, bool);
     486              : static void alloc_pre_mem (int, int);
     487              : static void free_pre_mem (void);
     488              : static struct edge_list *compute_pre_data (void);
     489              : static bool pre_expr_reaches_here_p (basic_block, struct gcse_expr *,
     490              :                                      basic_block);
     491              : static void insert_insn_end_basic_block (struct gcse_expr *, basic_block);
     492              : static void pre_insert_copy_insn (struct gcse_expr *, rtx_insn *);
     493              : static void pre_insert_copies (void);
     494              : static bool pre_delete (void);
     495              : static bool pre_gcse (struct edge_list *);
     496              : static bool one_pre_gcse_pass (void);
     497              : static void add_label_notes (rtx, rtx_insn *);
     498              : static void alloc_code_hoist_mem (int, int);
     499              : static void free_code_hoist_mem (void);
     500              : static void compute_code_hoist_vbeinout (void);
     501              : static void compute_code_hoist_data (void);
     502              : static bool should_hoist_expr_to_dom (basic_block, struct gcse_expr *,
     503              :                                       basic_block,
     504              :                                       sbitmap, HOST_WIDE_INT, int *,
     505              :                                       enum reg_class,
     506              :                                       int *, bitmap, rtx_insn *);
     507              : static bool hoist_code (void);
     508              : static enum reg_class get_regno_pressure_class (int regno, int *nregs);
     509              : static enum reg_class get_pressure_class_and_nregs (rtx_insn *insn, int *nregs);
     510              : static bool one_code_hoisting_pass (void);
     511              : static rtx_insn *process_insert_insn (struct gcse_expr *);
     512              : static bool pre_edge_insert (struct edge_list *, struct gcse_expr **);
     513              : static bool pre_expr_reaches_here_p_work (basic_block, struct gcse_expr *,
     514              :                                           basic_block, char *);
     515              : static struct ls_expr * ldst_entry (rtx);
     516              : static void free_ldst_entry (struct ls_expr *);
     517              : static void free_ld_motion_mems (void);
     518              : static void print_ldst_list (FILE *);
     519              : static struct ls_expr * find_rtx_in_ldst (rtx);
     520              : static bool simple_mem (const_rtx);
     521              : static void invalidate_any_buried_refs (rtx);
     522              : static void compute_ld_motion_mems (void);
     523              : static void trim_ld_motion_mems (void);
     524              : static void update_ld_motion_stores (struct gcse_expr *);
     525              : static void clear_modify_mem_tables (void);
     526              : static void free_modify_mem_tables (void);
     527              : 
     528              : #define GNEW(T)                 ((T *) gmalloc (sizeof (T)))
     529              : #define GCNEW(T)                ((T *) gcalloc (1, sizeof (T)))
     530              : 
     531              : #define GNEWVEC(T, N)           ((T *) gmalloc (sizeof (T) * (N)))
     532              : #define GCNEWVEC(T, N)          ((T *) gcalloc ((N), sizeof (T)))
     533              : 
     534              : #define GNEWVAR(T, S)           ((T *) gmalloc ((S)))
     535              : #define GCNEWVAR(T, S)          ((T *) gcalloc (1, (S)))
     536              : 
     537              : #define GOBNEW(T)               ((T *) gcse_alloc (sizeof (T)))
     538              : #define GOBNEWVAR(T, S)         ((T *) gcse_alloc ((S)))
     539              : 
     540              : /* Misc. utilities.  */
     541              : 
     542              : #define can_copy \
     543              :   (this_target_gcse->x_can_copy)
     544              : #define can_copy_init_p \
     545              :   (this_target_gcse->x_can_copy_init_p)
     546              : 
     547              : /* Compute which modes support reg/reg copy operations.  */
     548              : 
     549              : static void
     550        89890 : compute_can_copy (void)
     551              : {
     552        89890 :   int i;
     553              : #ifndef AVOID_CCMODE_COPIES
     554              :   rtx reg;
     555              :  rtx_insn *insn;
     556              : #endif
     557        89890 :   memset (can_copy, 0, NUM_MACHINE_MODES);
     558              : 
     559        89890 :   start_sequence ();
     560     11326140 :   for (i = 0; i < NUM_MACHINE_MODES; i++)
     561     11146360 :     if (GET_MODE_CLASS (i) == MODE_CC)
     562              :       {
     563              : #ifdef AVOID_CCMODE_COPIES
     564      1078680 :         can_copy[i] = 0;
     565              : #else
     566              :         reg = gen_rtx_REG ((machine_mode) i, LAST_VIRTUAL_REGISTER + 1);
     567              :         insn = emit_insn (gen_rtx_SET (reg, reg));
     568              :         if (recog (PATTERN (insn), insn, NULL) >= 0)
     569              :           can_copy[i] = 1;
     570              : #endif
     571              :       }
     572              :     else
     573     10067680 :       can_copy[i] = 1;
     574              : 
     575        89890 :   end_sequence ();
     576        89890 : }
     577              : 
     578              : /* Returns whether the mode supports reg/reg copy operations.  */
     579              : 
     580              : bool
     581    103218792 : can_copy_p (machine_mode mode)
     582              : {
     583    103218792 :   if (! can_copy_init_p)
     584              :     {
     585        89890 :       compute_can_copy ();
     586        89890 :       can_copy_init_p = true;
     587              :     }
     588              : 
     589    103218792 :   return can_copy[mode] != 0;
     590              : }
     591              : 
     592              : /* Cover function to xmalloc to record bytes allocated.  */
     593              : 
     594              : static void *
     595      1034556 : gmalloc (size_t size)
     596              : {
     597      1034556 :   bytes_used += size;
     598            0 :   return xmalloc (size);
     599              : }
     600              : 
     601              : /* Cover function to xcalloc to record bytes allocated.  */
     602              : 
     603              : static void *
     604      1885006 : gcalloc (size_t nelem, size_t elsize)
     605              : {
     606      1885006 :   bytes_used += nelem * elsize;
     607      1885006 :   return xcalloc (nelem, elsize);
     608              : }
     609              : 
     610              : /* Cover function to obstack_alloc.  */
     611              : 
     612              : static void *
     613     26804398 : gcse_alloc (unsigned long size)
     614              : {
     615     26804398 :   bytes_used += size;
     616     26804398 :   return obstack_alloc (&gcse_obstack, size);
     617              : }
     618              : 
     619              : /* Allocate memory for the reg/memory set tracking tables.
     620              :    This is called at the start of each pass.  */
     621              : 
     622              : static void
     623       517278 : alloc_gcse_mem (void)
     624              : {
     625              :   /* Allocate vars to track sets of regs.  */
     626       517278 :   reg_set_bitmap = ALLOC_REG_SET (NULL);
     627              : 
     628              :   /* Allocate array to keep a list of insns which modify memory in each
     629              :      basic block.  The two typedefs are needed to work around the
     630              :      pre-processor limitation with template types in macro arguments.  */
     631       517278 :   typedef vec<rtx_insn *> vec_rtx_heap;
     632       517278 :   typedef vec<modify_pair> vec_modify_pair_heap;
     633       517278 :   modify_mem_list = GCNEWVEC (vec_rtx_heap, last_basic_block_for_fn (cfun));
     634       517278 :   canon_modify_mem_list = GCNEWVEC (vec_modify_pair_heap,
     635              :                                     last_basic_block_for_fn (cfun));
     636       517278 :   modify_mem_list_set = BITMAP_ALLOC (NULL);
     637       517278 :   blocks_with_calls = BITMAP_ALLOC (NULL);
     638       517278 : }
     639              : 
     640              : /* Free memory allocated by alloc_gcse_mem.  */
     641              : 
     642              : static void
     643       517278 : free_gcse_mem (void)
     644              : {
     645       517278 :   FREE_REG_SET (reg_set_bitmap);
     646              : 
     647       517278 :   free_modify_mem_tables ();
     648       517278 :   BITMAP_FREE (modify_mem_list_set);
     649       517278 :   BITMAP_FREE (blocks_with_calls);
     650       517278 : }
     651              : 
     652              : /* Compute the local properties of each recorded expression.
     653              : 
     654              :    Local properties are those that are defined by the block, irrespective of
     655              :    other blocks.
     656              : 
     657              :    An expression is transparent in a block if its operands are not modified
     658              :    in the block.
     659              : 
     660              :    An expression is computed (locally available) in a block if it is computed
     661              :    at least once and expression would contain the same value if the
     662              :    computation was moved to the end of the block.
     663              : 
     664              :    An expression is locally anticipatable in a block if it is computed at
     665              :    least once and expression would contain the same value if the computation
     666              :    was moved to the beginning of the block.
     667              : 
     668              :    We call this routine for pre and code hoisting.  They all compute
     669              :    basically the same information and thus can easily share this code.
     670              : 
     671              :    TRANSP, COMP, and ANTLOC are destination sbitmaps for recording local
     672              :    properties.  If NULL, then it is not necessary to compute or record that
     673              :    particular property.
     674              : 
     675              :    TABLE controls which hash table to look at.  */
     676              : 
     677              : static void
     678       452420 : compute_local_properties (sbitmap *transp, sbitmap *comp, sbitmap *antloc,
     679              :                           struct gcse_hash_table_d *table)
     680              : {
     681       452420 :   unsigned int i;
     682              : 
     683              :   /* Initialize any bitmaps that were passed in.  */
     684       452420 :   if (transp)
     685              :     {
     686       452420 :       bitmap_vector_ones (transp, last_basic_block_for_fn (cfun));
     687              :     }
     688              : 
     689       452420 :   if (comp)
     690       452420 :     bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
     691       452420 :   if (antloc)
     692       452420 :     bitmap_vector_clear (antloc, last_basic_block_for_fn (cfun));
     693              : 
     694     21739640 :   for (i = 0; i < table->size; i++)
     695              :     {
     696     21287220 :       struct gcse_expr *expr;
     697              : 
     698     31472592 :       for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
     699              :         {
     700     10185372 :           int indx = expr->bitmap_index;
     701     10185372 :           struct gcse_occr *occr;
     702              : 
     703              :           /* In most cases, the expression is transparent in the block if it is
     704              :              not killed.  The exception to this is during hardreg PRE, in which
     705              :              uses of the hardreg prevent transparency but do not kill the
     706              :              expression.
     707              : 
     708              :              We start by assuming all expressions are transparent [none are
     709              :              killed], and then reset the bits for those that are.  */
     710     10185372 :           if (transp)
     711              :             {
     712     10185372 :               compute_transp (expr->expr, indx, transp,
     713              :                               blocks_with_calls,
     714              :                               modify_mem_list_set,
     715              :                               canon_modify_mem_list);
     716              : 
     717     10185372 :               if (doing_hardreg_pre_p)
     718              :                 {
     719              :                   /* We also need to check whether the destination hardreg is
     720              :                      set or call-clobbered in each BB.  We'll check for hardreg
     721              :                      uses later.  */
     722            0 :                   df_ref def;
     723            0 :                   for (def = DF_REG_DEF_CHAIN (current_hardreg_regno);
     724            0 :                        def;
     725            0 :                        def = DF_REF_NEXT_REG (def))
     726            0 :                     bitmap_clear_bit (transp[DF_REF_BB (def)->index], indx);
     727              :                 }
     728              :             }
     729              : 
     730              :           /* The occurrences recorded in antic_occr are exactly those that
     731              :              we want to set to nonzero in ANTLOC.  */
     732     10185372 :           if (antloc)
     733     17507936 :             for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
     734              :               {
     735      7322564 :                 bitmap_set_bit (antloc[BLOCK_FOR_INSN (occr->insn)->index], indx);
     736              : 
     737              :                 /* While we're scanning the table, this is a good place to
     738              :                    initialize this.  */
     739      7322564 :                 occr->deleted_p = 0;
     740              :               }
     741              : 
     742              :           /* The occurrences recorded in avail_occr are exactly those that
     743              :              we want to set to nonzero in COMP.  */
     744     10185372 :           if (comp)
     745     19481834 :             for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
     746              :               {
     747      9296462 :                 bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
     748              : 
     749              :                 /* While we're scanning the table, this is a good place to
     750              :                    initialize this.  */
     751      9296462 :                 occr->copied_p = 0;
     752              :               }
     753              : 
     754              :           /* While we're scanning the table, this is a good place to
     755              :              initialize this.  */
     756     10185372 :           expr->reaching_reg = 0;
     757              :         }
     758              :     }
     759       452420 : }
     760              : 
     761              : /* A hardreg set is not transparent in a block if there are any uses of that
     762              :    hardreg.  This filters the results of compute_local_properties, after the
     763              :    result of that function has been used to define the kills bitmap.
     764              : 
     765              :    TRANSP is the destination sbitmap to be updated.
     766              : 
     767              :    TABLE controls which hash table to look at.  */
     768              : 
     769              : static void
     770            0 : prune_hardreg_uses (sbitmap *transp, struct gcse_hash_table_d *table)
     771              : {
     772            0 :   unsigned int i;
     773            0 :   gcc_assert (doing_hardreg_pre_p);
     774              : 
     775            0 :   for (i = 0; i < table->size; i++)
     776              :     {
     777            0 :       struct gcse_expr *expr;
     778              : 
     779            0 :       for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
     780              :         {
     781            0 :           int indx = expr->bitmap_index;
     782            0 :           df_ref def;
     783              : 
     784            0 :           for (def = DF_REG_USE_CHAIN (current_hardreg_regno);
     785            0 :                def;
     786            0 :                def = DF_REF_NEXT_REG (def))
     787            0 :             bitmap_clear_bit (transp[DF_REF_BB (def)->index], indx);
     788              :         }
     789              :     }
     790            0 : }
     791              : 
     792              : /* Hash table support.  */
     793              : 
     794              : struct reg_avail_info
     795              : {
     796              :   basic_block last_bb;
     797              :   int first_set;
     798              :   int last_set;
     799              : };
     800              : 
     801              : static struct reg_avail_info *reg_avail_info;
     802              : static basic_block current_bb;
     803              : 
     804              : /* See whether X, the source of a set, is something we want to consider for
     805              :    GCSE.  */
     806              : 
     807              : static bool
     808     22198014 : want_to_gcse_p (rtx x, machine_mode mode, HOST_WIDE_INT *max_distance_ptr)
     809              : {
     810              : #ifdef STACK_REGS
     811              :   /* On register stack architectures, don't GCSE constants from the
     812              :      constant pool, as the benefits are often swamped by the overhead
     813              :      of shuffling the register stack between basic blocks.  */
     814     22198014 :   if (IS_STACK_MODE (GET_MODE (x)))
     815       272632 :     x = avoid_constant_pool_reference (x);
     816              : #endif
     817              : 
     818              :   /* GCSE'ing constants:
     819              : 
     820              :      We do not specifically distinguish between constant and non-constant
     821              :      expressions in PRE and Hoist.  We use set_src_cost below to limit
     822              :      the maximum distance simple expressions can travel.
     823              : 
     824              :      Nevertheless, constants are much easier to GCSE, and, hence,
     825              :      it is easy to overdo the optimizations.  Usually, excessive PRE and
     826              :      Hoisting of constant leads to increased register pressure.
     827              : 
     828              :      RA can deal with this by rematerialing some of the constants.
     829              :      Therefore, it is important that the back-end generates sets of constants
     830              :      in a way that allows reload rematerialize them under high register
     831              :      pressure, i.e., a pseudo register with REG_EQUAL to constant
     832              :      is set only once.  Failing to do so will result in IRA/reload
     833              :      spilling such constants under high register pressure instead of
     834              :      rematerializing them.
     835              : 
     836              :      For hardreg PRE, register pressure is not a concern, and we also want to
     837              :      apply GCSE to simple moves.  */
     838              : 
     839     22198014 :   switch (GET_CODE (x))
     840              :     {
     841      3340324 :     case REG:
     842      3340324 :     case SUBREG:
     843      3340324 :       return doing_hardreg_pre_p;
     844              : 
     845              :     case CALL:
     846              :       return false;
     847              : 
     848      2533447 :     CASE_CONST_ANY:
     849      2533447 :       if (doing_hardreg_pre_p)
     850              :         return true;
     851      2533447 :       else if (!doing_code_hoisting_p)
     852              :         /* Do not PRE constants.  */
     853              :         return false;
     854              : 
     855              :       /* FALLTHRU */
     856              : 
     857     16463220 :     default:
     858     16463220 :       if (doing_code_hoisting_p)
     859              :         /* PRE doesn't implement max_distance restriction.  */
     860              :         {
     861       677031 :           int cost;
     862       677031 :           HOST_WIDE_INT max_distance;
     863              : 
     864       677031 :           gcc_assert (!optimize_function_for_speed_p (cfun)
     865              :                       && optimize_function_for_size_p (cfun));
     866       677031 :           cost = set_src_cost (x, mode, 0);
     867              : 
     868       677031 :           if (cost < COSTS_N_INSNS (param_gcse_unrestricted_cost))
     869              :             {
     870       641411 :               max_distance
     871       641411 :                 = ((HOST_WIDE_INT)param_gcse_cost_distance_ratio * cost) / 10;
     872       641411 :               if (max_distance == 0)
     873              :                 return false;
     874              : 
     875       573891 :               gcc_assert (max_distance > 0);
     876              :             }
     877              :           else
     878              :             max_distance = 0;
     879              : 
     880       609511 :           if (max_distance_ptr)
     881       548302 :             *max_distance_ptr = max_distance;
     882              :         }
     883              : 
     884     16395700 :       return can_assign_to_reg_without_clobbers_p (x, mode);
     885              :     }
     886              : }
     887              : 
     888              : /* Used internally by can_assign_to_reg_without_clobbers_p.  */
     889              : 
     890              : static GTY(()) rtx_insn *test_insn;
     891              : 
     892              : /* Return true if we can assign X to a pseudo register of mode MODE
     893              :    such that the resulting insn does not result in clobbering a hard
     894              :    register as a side-effect.
     895              : 
     896              :    Additionally, if the target requires it, check that the resulting insn
     897              :    can be copied.  If it cannot, this means that X is special and probably
     898              :    has hidden side-effects we don't want to mess with.
     899              : 
     900              :    This function is typically used by code motion passes, to verify
     901              :    that it is safe to insert an insn without worrying about clobbering
     902              :    maybe live hard regs.  */
     903              : 
     904              : bool
     905     21096975 : can_assign_to_reg_without_clobbers_p (rtx x, machine_mode mode)
     906              : {
     907     21096975 :   int num_clobbers = 0;
     908     21096975 :   int icode;
     909     21096975 :   bool can_assign = false;
     910              : 
     911              :   /* If this is a valid operand, we are OK.  If it's VOIDmode, we aren't.  */
     912     21096975 :   if (general_operand (x, mode))
     913              :     return true;
     914     10076285 :   else if (GET_MODE (x) == VOIDmode)
     915              :     return false;
     916              : 
     917              :   /* Otherwise, check if we can make a valid insn from it.  First initialize
     918              :      our test insn if we haven't already.  */
     919     10076285 :   if (test_insn == 0)
     920              :     {
     921        72198 :       test_insn
     922        72198 :         = make_insn_raw (gen_rtx_SET (gen_rtx_REG (word_mode,
     923              :                                                    FIRST_PSEUDO_REGISTER * 2),
     924              :                                       const0_rtx));
     925        72198 :       SET_NEXT_INSN (test_insn) = SET_PREV_INSN (test_insn) = 0;
     926        72198 :       INSN_LOCATION (test_insn) = UNKNOWN_LOCATION;
     927              :     }
     928              : 
     929              :   /* Now make an insn like the one we would make when GCSE'ing and see if
     930              :      valid.  */
     931     10076285 :   PUT_MODE (SET_DEST (PATTERN (test_insn)), mode);
     932     10076285 :   SET_SRC (PATTERN (test_insn)) = x;
     933              : 
     934     10076285 :   icode = recog (PATTERN (test_insn), test_insn, &num_clobbers);
     935              : 
     936              :   /* If the test insn is valid and doesn't need clobbers, and the target also
     937              :      has no objections, we're good.  */
     938     10076285 :   if (icode >= 0
     939      9096842 :       && (num_clobbers == 0 || !added_clobbers_hard_reg_p (icode))
     940     17136608 :       && ! (targetm.cannot_copy_insn_p
     941            0 :             && targetm.cannot_copy_insn_p (test_insn)))
     942              :     can_assign = true;
     943              : 
     944              :   /* Make sure test_insn doesn't have any pointers into GC space.  */
     945     10076285 :   SET_SRC (PATTERN (test_insn)) = NULL_RTX;
     946              : 
     947     10076285 :   return can_assign;
     948              : }
     949              : 
     950              : /* Return true if the operands of expression X are unchanged from the
     951              :    start of INSN's basic block up to but not including INSN
     952              :    (if AVAIL_P == false), or from INSN to the end of INSN's basic block
     953              :    (if AVAIL_P == true).  */
     954              : 
     955              : static bool
     956     46845047 : oprs_unchanged_p (const_rtx x, const rtx_insn *insn, bool avail_p)
     957              : {
     958     75214879 :   int i, j;
     959     75214879 :   enum rtx_code code;
     960     75214879 :   const char *fmt;
     961              : 
     962     75214879 :   if (x == 0)
     963              :     return true;
     964              : 
     965     75214879 :   code = GET_CODE (x);
     966     75214879 :   switch (code)
     967              :     {
     968     23355493 :     case REG:
     969     23355493 :       {
     970     23355493 :         struct reg_avail_info *info = &reg_avail_info[REGNO (x)];
     971              : 
     972     23355493 :         if (info->last_bb != current_bb)
     973              :           return true;
     974     11391614 :         if (avail_p)
     975      6050598 :           return info->last_set < DF_INSN_LUID (insn);
     976              :         else
     977      5341016 :           return info->first_set >= DF_INSN_LUID (insn);
     978              :       }
     979              : 
     980     12055771 :     case MEM:
     981     12055771 :       if (! do_load_motion ()
     982     12055749 :           || load_killed_in_block_p (current_bb, DF_INSN_LUID (insn),
     983              :                                      x, avail_p))
     984              :         return false;
     985              :       else
     986      8475194 :         return oprs_unchanged_p (XEXP (x, 0), insn, avail_p);
     987              : 
     988              :     case PRE_DEC:
     989              :     case PRE_INC:
     990              :     case POST_DEC:
     991              :     case POST_INC:
     992              :     case PRE_MODIFY:
     993              :     case POST_MODIFY:
     994              :       return false;
     995              : 
     996              :     case PC:
     997              :     case CONST:
     998              :     CASE_CONST_ANY:
     999              :     case SYMBOL_REF:
    1000              :     case LABEL_REF:
    1001              :     case ADDR_VEC:
    1002              :     case ADDR_DIFF_VEC:
    1003              :       return true;
    1004              : 
    1005     21977954 :     default:
    1006     21977954 :       break;
    1007              :     }
    1008              : 
    1009     40377602 :   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
    1010              :     {
    1011     39884071 :       if (fmt[i] == 'e')
    1012              :         {
    1013              :           /* If we are about to do the last recursive call needed at this
    1014              :              level, change it into iteration.  This function is called enough
    1015              :              to be worth it.  */
    1016     38572950 :           if (i == 0)
    1017     19894638 :             return oprs_unchanged_p (XEXP (x, i), insn, avail_p);
    1018              : 
    1019     18678312 :           else if (! oprs_unchanged_p (XEXP (x, i), insn, avail_p))
    1020              :             return false;
    1021              :         }
    1022      1311121 :       else if (fmt[i] == 'E')
    1023      2237193 :         for (j = 0; j < XVECLEN (x, i); j++)
    1024      1743707 :           if (! oprs_unchanged_p (XVECEXP (x, i, j), insn, avail_p))
    1025              :             return false;
    1026              :     }
    1027              : 
    1028              :   return true;
    1029              : }
    1030              : 
    1031              : /* Info passed from load_killed_in_block_p to mems_conflict_for_gcse_p.  */
    1032              : 
    1033              : struct mem_conflict_info
    1034              : {
    1035              :   /* A memory reference for a load instruction, mems_conflict_for_gcse_p will
    1036              :      see if a memory store conflicts with this memory load.  */
    1037              :   const_rtx mem;
    1038              : 
    1039              :   /* True if mems_conflict_for_gcse_p finds a conflict between two memory
    1040              :      references.  */
    1041              :   bool conflict;
    1042              : };
    1043              : 
    1044              : /* DEST is the output of an instruction.  If it is a memory reference and
    1045              :    possibly conflicts with the load found in DATA, then communicate this
    1046              :    information back through DATA.  */
    1047              : 
    1048              : static void
    1049     13267055 : mems_conflict_for_gcse_p (rtx dest, const_rtx setter ATTRIBUTE_UNUSED,
    1050              :                           void *data)
    1051              : {
    1052     13267055 :   struct mem_conflict_info *mci = (struct mem_conflict_info *) data;
    1053              : 
    1054     13267055 :   while (GET_CODE (dest) == SUBREG
    1055     13267055 :          || GET_CODE (dest) == ZERO_EXTRACT
    1056     26534110 :          || GET_CODE (dest) == STRICT_LOW_PART)
    1057            0 :     dest = XEXP (dest, 0);
    1058              : 
    1059              :   /* If DEST is not a MEM, then it will not conflict with the load.  Note
    1060              :      that function calls are assumed to clobber memory, but are handled
    1061              :      elsewhere.  */
    1062     13267055 :   if (! MEM_P (dest))
    1063              :     return;
    1064              : 
    1065              :   /* If we are setting a MEM in our list of specially recognized MEMs,
    1066              :      don't mark as killed this time.  */
    1067     25899080 :   if (pre_ldst_mems != NULL && expr_equiv_p (dest, mci->mem))
    1068              :     {
    1069       109887 :       if (!find_rtx_in_ldst (dest))
    1070        40492 :         mci->conflict = true;
    1071              :       return;
    1072              :     }
    1073              : 
    1074     13042457 :   if (true_dependence (dest, GET_MODE (dest), mci->mem))
    1075      1479657 :     mci->conflict = true;
    1076              : }
    1077              : 
    1078              : /* Return true if the expression in X (a memory reference) is killed
    1079              :    in block BB before or after the insn with the LUID in UID_LIMIT.
    1080              :    AVAIL_P is true for kills after UID_LIMIT, and zero for kills
    1081              :    before UID_LIMIT.
    1082              : 
    1083              :    To check the entire block, set UID_LIMIT to max_uid + 1 and
    1084              :    AVAIL_P to false.  */
    1085              : 
    1086              : static bool
    1087     12055749 : load_killed_in_block_p (const_basic_block bb, int uid_limit, const_rtx x,
    1088              :                         bool avail_p)
    1089              : {
    1090     12055749 :   vec<rtx_insn *> list = modify_mem_list[bb->index];
    1091     12055749 :   rtx_insn *setter;
    1092     12055749 :   unsigned ix;
    1093              : 
    1094              :   /* If this is a readonly then we aren't going to be changing it.  */
    1095     12055749 :   if (MEM_READONLY_P (x))
    1096              :     return false;
    1097              : 
    1098     52579728 :   FOR_EACH_VEC_ELT_REVERSE (list, ix, setter)
    1099              :     {
    1100     38556695 :       struct mem_conflict_info mci;
    1101              : 
    1102              :       /* Ignore entries in the list that do not apply.  */
    1103     61900697 :       if ((avail_p
    1104     15899581 :            && DF_INSN_LUID (setter) < uid_limit)
    1105     38556695 :           || (! avail_p
    1106     22657114 :               && DF_INSN_LUID (setter) > uid_limit))
    1107     23344002 :         continue;
    1108              : 
    1109              :       /* If SETTER is a call everything is clobbered.  Note that calls
    1110              :          to pure functions are never put on the list, so we need not
    1111              :          worry about them.  */
    1112     15212693 :       if (CALL_P (setter))
    1113      3580555 :         return true;
    1114              : 
    1115              :       /* SETTER must be an INSN of some kind that sets memory.  Call
    1116              :          note_stores to examine each hunk of memory that is modified.  */
    1117     13152284 :       mci.mem = x;
    1118     13152284 :       mci.conflict = false;
    1119     13152284 :       note_stores (setter, mems_conflict_for_gcse_p, &mci);
    1120     13152284 :       if (mci.conflict)
    1121              :         return true;
    1122              :     }
    1123              :   return false;
    1124              : }
    1125              : 
    1126              : /* Return true if the operands of expression X are unchanged from
    1127              :    the start of INSN's basic block up to but not including INSN.  */
    1128              : 
    1129              : static bool
    1130     13211459 : oprs_anticipatable_p (const_rtx x, const rtx_insn *insn)
    1131              : {
    1132            0 :   return oprs_unchanged_p (x, insn, false);
    1133              : }
    1134              : 
    1135              : /* Return true if the operands of expression X are unchanged from
    1136              :    INSN to the end of INSN's basic block.  */
    1137              : 
    1138              : static bool
    1139     13211569 : oprs_available_p (const_rtx x, const rtx_insn *insn)
    1140              : {
    1141            0 :   return oprs_unchanged_p (x, insn, true);
    1142              : }
    1143              : 
    1144              : /* Hash expression X.
    1145              : 
    1146              :    MODE is only used if X is a CONST_INT.  DO_NOT_RECORD_P is a boolean
    1147              :    indicating if a volatile operand is found or if the expression contains
    1148              :    something we don't want to insert in the table.  HASH_TABLE_SIZE is
    1149              :    the current size of the hash table to be probed.  */
    1150              : 
    1151              : static unsigned int
    1152     13211569 : hash_expr (const_rtx x, machine_mode mode, int *do_not_record_p,
    1153              :            int hash_table_size)
    1154              : {
    1155     13211569 :   unsigned int hash;
    1156              : 
    1157     13211569 :   *do_not_record_p = 0;
    1158              : 
    1159     13211569 :   hash = hash_rtx (x, mode, do_not_record_p, NULL, /*have_reg_qty=*/false);
    1160     13211569 :   return hash % hash_table_size;
    1161              : }
    1162              : 
    1163              : /* Return true if exp1 is equivalent to exp2.  */
    1164              : 
    1165              : static bool
    1166    150698073 : expr_equiv_p (const_rtx x, const_rtx y)
    1167              : {
    1168    136805056 :   return exp_equiv_p (x, y, 0, true);
    1169              : }
    1170              : 
    1171              : /* Insert expression X in INSN in the hash TABLE.
    1172              :    If it is already present, record it as the last occurrence in INSN's
    1173              :    basic block.
    1174              : 
    1175              :    MODE is the mode of the value X is being stored into.
    1176              :    It is only used if X is a CONST_INT.
    1177              : 
    1178              :    ANTIC_P is true if X is an anticipatable expression.
    1179              :    AVAIL_P is true if X is an available expression.
    1180              : 
    1181              :    MAX_DISTANCE is the maximum distance in instructions this expression can
    1182              :    be moved.  */
    1183              : 
    1184              : static void
    1185     13211569 : insert_expr_in_table (rtx x, machine_mode mode, rtx_insn *insn,
    1186              :                       bool antic_p, bool avail_p, HOST_WIDE_INT max_distance,
    1187              :                       struct gcse_hash_table_d *table)
    1188              : {
    1189     13211569 :   bool found;
    1190     13211569 :   int do_not_record_p;
    1191     13211569 :   unsigned int hash;
    1192     13211569 :   struct gcse_expr *cur_expr, *last_expr = NULL;
    1193     13211569 :   struct gcse_occr *antic_occr, *avail_occr;
    1194              : 
    1195     13211569 :   hash = hash_expr (x, mode, &do_not_record_p, table->size);
    1196              : 
    1197              :   /* Do not insert expression in table if it contains volatile operands,
    1198              :      or if hash_expr determines the expression is something we don't want
    1199              :      to or can't handle.  */
    1200     13211569 :   if (do_not_record_p)
    1201       308110 :     return;
    1202              : 
    1203     12903459 :   cur_expr = table->table[hash];
    1204     12903459 :   found = false;
    1205              : 
    1206     17076217 :   while (cur_expr && (found = expr_equiv_p (cur_expr->expr, x)) == 0)
    1207              :     {
    1208              :       /* If the expression isn't found, save a pointer to the end of
    1209              :          the list.  */
    1210      4172758 :       last_expr = cur_expr;
    1211      4172758 :       cur_expr = cur_expr->next_same_hash;
    1212              :     }
    1213              : 
    1214     12903459 :   if (! found)
    1215              :     {
    1216     10185372 :       cur_expr = GOBNEW (struct gcse_expr);
    1217     10185372 :       bytes_used += sizeof (struct gcse_expr);
    1218     10185372 :       if (table->table[hash] == NULL)
    1219              :         /* This is the first pattern that hashed to this index.  */
    1220      7518260 :         table->table[hash] = cur_expr;
    1221              :       else
    1222              :         /* Add EXPR to end of this hash chain.  */
    1223      2667112 :         last_expr->next_same_hash = cur_expr;
    1224              : 
    1225              :       /* Set the fields of the expr element.  */
    1226     10185372 :       cur_expr->expr = x;
    1227     10185372 :       cur_expr->bitmap_index = table->n_elems++;
    1228     10185372 :       cur_expr->next_same_hash = NULL;
    1229     10185372 :       cur_expr->antic_occr = NULL;
    1230     10185372 :       cur_expr->avail_occr = NULL;
    1231     10185372 :       gcc_assert (max_distance >= 0);
    1232     10185372 :       cur_expr->max_distance = max_distance;
    1233              :     }
    1234              :   else
    1235      2718087 :     gcc_assert (cur_expr->max_distance == max_distance);
    1236              : 
    1237              :   /* Now record the occurrence(s).  */
    1238     12903459 :   if (antic_p)
    1239              :     {
    1240      7331651 :       antic_occr = cur_expr->antic_occr;
    1241              : 
    1242      7331651 :       if (antic_occr
    1243      7331651 :           && BLOCK_FOR_INSN (antic_occr->insn) != BLOCK_FOR_INSN (insn))
    1244              :         antic_occr = NULL;
    1245              : 
    1246      5293769 :       if (antic_occr)
    1247              :         /* Found another instance of the expression in the same basic block.
    1248              :            Prefer the currently recorded one.  We want the first one in the
    1249              :            block and the block is scanned from start to end.  */
    1250              :         ; /* nothing to do */
    1251              :       else
    1252              :         {
    1253              :           /* First occurrence of this expression in this basic block.  */
    1254      7322564 :           antic_occr = GOBNEW (struct gcse_occr);
    1255      7322564 :           bytes_used += sizeof (struct gcse_occr);
    1256      7322564 :           antic_occr->insn = insn;
    1257      7322564 :           antic_occr->next = cur_expr->antic_occr;
    1258      7322564 :           antic_occr->deleted_p = 0;
    1259      7322564 :           cur_expr->antic_occr = antic_occr;
    1260              :         }
    1261              :     }
    1262              : 
    1263     12903459 :   if (avail_p)
    1264              :     {
    1265      9306739 :       avail_occr = cur_expr->avail_occr;
    1266              : 
    1267      9306739 :       if (avail_occr
    1268      9306739 :           && BLOCK_FOR_INSN (avail_occr->insn) == BLOCK_FOR_INSN (insn))
    1269              :         {
    1270              :           /* Found another instance of the expression in the same basic block.
    1271              :              Prefer this occurrence to the currently recorded one.  We want
    1272              :              the last one in the block and the block is scanned from start
    1273              :              to end.  */
    1274        10277 :           avail_occr->insn = insn;
    1275              :         }
    1276              :       else
    1277              :         {
    1278              :           /* First occurrence of this expression in this basic block.  */
    1279      9296462 :           avail_occr = GOBNEW (struct gcse_occr);
    1280      9296462 :           bytes_used += sizeof (struct gcse_occr);
    1281      9296462 :           avail_occr->insn = insn;
    1282      9296462 :           avail_occr->next = cur_expr->avail_occr;
    1283      9296462 :           avail_occr->deleted_p = 0;
    1284      9296462 :           cur_expr->avail_occr = avail_occr;
    1285              :         }
    1286              :     }
    1287              : }
    1288              : 
    1289              : /* Scan SET present in INSN and add an entry to the hash TABLE.  */
    1290              : 
    1291              : static void
    1292     48509766 : hash_scan_set (rtx set, rtx_insn *insn, struct gcse_hash_table_d *table)
    1293              : {
    1294     48509766 :   rtx src = SET_SRC (set);
    1295     48509766 :   rtx dest = SET_DEST (set);
    1296     48509766 :   rtx note;
    1297              : 
    1298     48509766 :   if (GET_CODE (src) == CALL)
    1299              :     hash_scan_call (src, insn, table);
    1300              : 
    1301     46829101 :   else if (REG_P (dest))
    1302              :     {
    1303     34553939 :       unsigned int regno = REGNO (dest);
    1304     34553939 :       HOST_WIDE_INT max_distance = 0;
    1305              : 
    1306              :       /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
    1307              : 
    1308              :          This allows us to do a single GCSE pass and still eliminate
    1309              :          redundant constants, addresses or other expressions that are
    1310              :          constructed with multiple instructions.
    1311              : 
    1312              :          However, keep the original SRC if INSN is a simple reg-reg move.
    1313              :          In this case, there will almost always be a REG_EQUAL note on the
    1314              :          insn that sets SRC.  By recording the REG_EQUAL value here as SRC
    1315              :          for INSN, we miss copy propagation opportunities and we perform the
    1316              :          same PRE GCSE operation repeatedly on the same REG_EQUAL value if we
    1317              :          do more than one PRE GCSE pass.
    1318              : 
    1319              :          Note that this does not impede profitable constant propagations.  We
    1320              :          "look through" reg-reg sets in lookup_avail_set.  */
    1321     34553939 :       note = find_reg_equal_equiv_note (insn);
    1322     34553939 :       if (note != 0
    1323      2934489 :           && REG_NOTE_KIND (note) == REG_EQUAL
    1324      2787898 :           && !REG_P (src)
    1325     36106063 :           && want_to_gcse_p (XEXP (note, 0), GET_MODE (dest), NULL))
    1326        36743 :         src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
    1327              : 
    1328              :       /* Only record sets of pseudo-regs in the hash table, unless we're
    1329              :          currently doing hardreg switching.  */
    1330     34553939 :       if ((doing_hardreg_pre_p ? regno == current_hardreg_regno
    1331              :                                      : regno >= FIRST_PSEUDO_REGISTER)
    1332              :           /* Don't GCSE something if we can't do a reg/reg copy.  */
    1333     20725661 :           && can_copy_p (GET_MODE (dest))
    1334              :           /* GCSE commonly inserts instruction after the insn.  We can't
    1335              :              do that easily for EH edges so disable GCSE on these for now.  */
    1336              :           /* ??? We can now easily create new EH landing pads at the
    1337              :              gimple level, for splitting edges; there's no reason we
    1338              :              can't do the same thing at the rtl level.  */
    1339     20725661 :           && !can_throw_internal (insn)
    1340              :           /* Is SET_SRC something we want to gcse?  */
    1341     20645780 :           && want_to_gcse_p (src, GET_MODE (dest), &max_distance)
    1342              :           /* Don't CSE a nop.  */
    1343     13351305 :           && ! set_noop_p (set)
    1344              :           /* Don't GCSE if it has attached REG_EQUIV note.
    1345              :              At this point this only function parameters should have
    1346              :              REG_EQUIV notes and if the argument slot is used somewhere
    1347              :              explicitly, it means address of parameter has been taken,
    1348              :              so we should not extend the lifetime of the pseudo.  */
    1349     47905244 :           && (note == NULL_RTX || ! MEM_P (XEXP (note, 0))))
    1350              :         {
    1351              :           /* An expression is not anticipatable if its operands are
    1352              :              modified before this insn or if this is not the only SET in
    1353              :              this insn.  The latter condition does not have to mean that
    1354              :              SRC itself is not anticipatable, but we just will not be
    1355              :              able to handle code motion of insns with multiple sets.  */
    1356     13211459 :           bool antic_p = (oprs_anticipatable_p (src, insn)
    1357     13211459 :                           && !multiple_sets (insn));
    1358     13211459 :           if (doing_hardreg_pre_p)
    1359              :             {
    1360              :               /* An hardreg assignment is anticipatable only if the hardreg is
    1361              :                  neither set nor used prior to this assignment.  */
    1362            0 :               auto info = reg_avail_info[current_hardreg_regno];
    1363            0 :               if ((info.last_bb == current_bb
    1364            0 :                    && info.first_set < DF_INSN_LUID (insn))
    1365            0 :                   || bitmap_bit_p (DF_LR_IN (current_bb),
    1366              :                                    current_hardreg_regno))
    1367              :                 antic_p = false;
    1368              :             }
    1369              : 
    1370              :           /* An expression is not available if its operands are
    1371              :              subsequently modified, including this insn.  It's also not
    1372              :              available if this is a branch, because we can't insert
    1373              :              a set after the branch.  */
    1374     13211459 :           bool avail_p = (oprs_available_p (src, insn)
    1375     13211459 :                           && ! JUMP_P (insn));
    1376     13211459 :           if (doing_hardreg_pre_p)
    1377              :             {
    1378              :               /* An hardreg assignment is only available if the hardreg is
    1379              :                  not set later in the BB.  Uses of the hardreg are allowed. */
    1380            0 :               auto info = reg_avail_info[current_hardreg_regno];
    1381            0 :               if (info.last_bb == current_bb
    1382            0 :                   && info.last_set > DF_INSN_LUID (insn))
    1383              :                 avail_p = false;
    1384              :             }
    1385              : 
    1386     13211459 :           insert_expr_in_table (src, GET_MODE (dest), insn, antic_p, avail_p,
    1387              :                                 max_distance, table);
    1388              :         }
    1389              :     }
    1390              :   /* In case of store we want to consider the memory value as available in
    1391              :      the REG stored in that memory. This makes it possible to remove
    1392              :      redundant loads from due to stores to the same location.  */
    1393     12275162 :   else if (flag_gcse_las
    1394          130 :            && !doing_hardreg_pre_p
    1395          130 :            && REG_P (src)
    1396          110 :            && MEM_P (dest))
    1397              :     {
    1398          110 :       unsigned int regno = REGNO (src);
    1399          110 :       HOST_WIDE_INT max_distance = 0;
    1400              : 
    1401              :       /* Only record sets of pseudo-regs in the hash table.  */
    1402          110 :       if (regno >= FIRST_PSEUDO_REGISTER
    1403              :           /* Don't GCSE something if we can't do a reg/reg copy.  */
    1404          110 :           && can_copy_p (GET_MODE (src))
    1405              :           /* GCSE commonly inserts instruction after the insn.  We can't
    1406              :              do that easily for EH edges so disable GCSE on these for now.  */
    1407          110 :           && !can_throw_internal (insn)
    1408              :           /* Is SET_DEST something we want to gcse?  */
    1409          110 :           && want_to_gcse_p (dest, GET_MODE (dest), &max_distance)
    1410              :           /* Don't CSE a nop.  */
    1411          110 :           && ! set_noop_p (set)
    1412              :           /* Don't GCSE if it has attached REG_EQUIV note.
    1413              :              At this point this only function parameters should have
    1414              :              REG_EQUIV notes and if the argument slot is used somewhere
    1415              :              explicitly, it means address of parameter has been taken,
    1416              :              so we should not extend the lifetime of the pseudo.  */
    1417          220 :           && ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) == 0
    1418            0 :               || ! MEM_P (XEXP (note, 0))))
    1419              :         {
    1420              :           /* Stores are never anticipatable.  */
    1421          110 :           bool antic_p = 0;
    1422              :           /* An expression is not available if its operands are
    1423              :              subsequently modified, including this insn.  It's also not
    1424              :              available if this is a branch, because we can't insert
    1425              :              a set after the branch.  */
    1426          110 :           bool avail_p = oprs_available_p (dest, insn) && ! JUMP_P (insn);
    1427              : 
    1428              :           /* Record the memory expression (DEST) in the hash table.  */
    1429          110 :           insert_expr_in_table (dest, GET_MODE (dest), insn,
    1430              :                                 antic_p, avail_p, max_distance, table);
    1431              :         }
    1432              :     }
    1433     48509766 : }
    1434              : 
    1435              : static void
    1436            0 : hash_scan_clobber (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
    1437              :                    struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
    1438              : {
    1439              :   /* Currently nothing to do.  */
    1440            0 : }
    1441              : 
    1442              : static void
    1443            0 : hash_scan_call (rtx x ATTRIBUTE_UNUSED, rtx_insn *insn ATTRIBUTE_UNUSED,
    1444              :                 struct gcse_hash_table_d *table ATTRIBUTE_UNUSED)
    1445              : {
    1446              :   /* Currently nothing to do.  */
    1447            0 : }
    1448              : 
    1449              : /* Process INSN and add hash table entries as appropriate.  */
    1450              : 
    1451              : static void
    1452     50898372 : hash_scan_insn (rtx_insn *insn, struct gcse_hash_table_d *table)
    1453              : {
    1454     50898372 :   rtx pat = PATTERN (insn);
    1455     50898372 :   int i;
    1456              : 
    1457              :   /* Pick out the sets of INSN and for other forms of instructions record
    1458              :      what's been modified.  */
    1459              : 
    1460     50898372 :   if (GET_CODE (pat) == SET)
    1461     39982438 :     hash_scan_set (pat, insn, table);
    1462              : 
    1463     10915934 :   else if (GET_CODE (pat) == CLOBBER)
    1464              :     hash_scan_clobber (pat, insn, table);
    1465              : 
    1466     10899863 :   else if (GET_CODE (pat) == CALL)
    1467              :     hash_scan_call (pat, insn, table);
    1468              : 
    1469      8707702 :   else if (GET_CODE (pat) == PARALLEL)
    1470     25198647 :     for (i = 0; i < XVECLEN (pat, 0); i++)
    1471              :       {
    1472     16911087 :         rtx x = XVECEXP (pat, 0, i);
    1473              : 
    1474     16911087 :         if (GET_CODE (x) == SET)
    1475      8527328 :           hash_scan_set (x, insn, table);
    1476              :         else if (GET_CODE (x) == CLOBBER)
    1477              :           hash_scan_clobber (x, insn, table);
    1478              :         else if (GET_CODE (x) == CALL)
    1479              :           hash_scan_call (x, insn, table);
    1480              :       }
    1481     50898372 : }
    1482              : 
    1483              : /* Dump the hash table TABLE to file FILE under the name NAME.  */
    1484              : 
    1485              : static void
    1486           24 : dump_hash_table (FILE *file, const char *name, struct gcse_hash_table_d *table)
    1487              : {
    1488           24 :   int i;
    1489              :   /* Flattened out table, so it's printed in proper order.  */
    1490           24 :   struct gcse_expr **flat_table;
    1491           24 :   unsigned int *hash_val;
    1492           24 :   struct gcse_expr *expr;
    1493              : 
    1494           24 :   flat_table = XCNEWVEC (struct gcse_expr *, table->n_elems);
    1495           24 :   hash_val = XNEWVEC (unsigned int, table->n_elems);
    1496              : 
    1497          416 :   for (i = 0; i < (int) table->size; i++)
    1498          628 :     for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
    1499              :       {
    1500          260 :         flat_table[expr->bitmap_index] = expr;
    1501          260 :         hash_val[expr->bitmap_index] = i;
    1502              :       }
    1503              : 
    1504           24 :   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
    1505              :            name, table->size, table->n_elems);
    1506              : 
    1507          308 :   for (i = 0; i < (int) table->n_elems; i++)
    1508          260 :     if (flat_table[i] != 0)
    1509              :       {
    1510          260 :         expr = flat_table[i];
    1511          260 :         fprintf (file, "Index %d (hash value %d; max distance "
    1512              :                  HOST_WIDE_INT_PRINT_DEC ")\n  ",
    1513          260 :                  expr->bitmap_index, hash_val[i], expr->max_distance);
    1514          260 :         print_rtl (file, expr->expr);
    1515          260 :         fprintf (file, "\n");
    1516              :       }
    1517              : 
    1518           24 :   fprintf (file, "\n");
    1519              : 
    1520           24 :   free (flat_table);
    1521           24 :   free (hash_val);
    1522           24 : }
    1523              : 
    1524              : /* Record register first/last/block set information for REGNO in INSN.
    1525              : 
    1526              :    first_set records the first place in the block where the register
    1527              :    is set and is used to compute "anticipatability".
    1528              : 
    1529              :    last_set records the last place in the block where the register
    1530              :    is set and is used to compute "availability".
    1531              : 
    1532              :    last_bb records the block for which first_set and last_set are
    1533              :    valid, as a quick test to invalidate them.  */
    1534              : 
    1535              : static void
    1536    378092727 : record_last_reg_set_info (rtx_insn *insn, int regno)
    1537              : {
    1538    378092727 :   struct reg_avail_info *info = &reg_avail_info[regno];
    1539    378092727 :   int luid = DF_INSN_LUID (insn);
    1540              : 
    1541    378092727 :   info->last_set = luid;
    1542    378092727 :   if (info->last_bb != current_bb)
    1543              :     {
    1544    282902758 :       info->last_bb = current_bb;
    1545    282902758 :       info->first_set = luid;
    1546              :     }
    1547    378092727 : }
    1548              : 
    1549              : /* Record memory modification information for INSN.  We do not actually care
    1550              :    about the memory location(s) that are set, or even how they are set (consider
    1551              :    a CALL_INSN).  We merely need to record which insns modify memory.  */
    1552              : 
    1553              : static void
    1554      9535526 : record_last_mem_set_info (rtx_insn *insn)
    1555              : {
    1556      9535526 :   if (! do_load_motion ())
    1557              :     return;
    1558              : 
    1559      9535512 :   record_last_mem_set_info_common (insn, modify_mem_list,
    1560              :                                    canon_modify_mem_list,
    1561              :                                    modify_mem_list_set,
    1562              :                                    blocks_with_calls);
    1563              : }
    1564              : 
    1565              : /* Called from compute_hash_table via note_stores to handle one
    1566              :    SET or CLOBBER in an insn.  DATA is really the instruction in which
    1567              :    the SET is taking place.  */
    1568              : 
    1569              : static void
    1570     56714194 : record_last_set_info (rtx dest, const_rtx setter ATTRIBUTE_UNUSED, void *data)
    1571              : {
    1572     56714194 :   rtx_insn *last_set_insn = (rtx_insn *) data;
    1573              : 
    1574     56714194 :   if (GET_CODE (dest) == SUBREG)
    1575            0 :     dest = SUBREG_REG (dest);
    1576              : 
    1577     56714194 :   if (REG_P (dest))
    1578     44644874 :     record_last_reg_set_info (last_set_insn, REGNO (dest));
    1579     12069320 :   else if (MEM_P (dest)
    1580              :            /* Ignore pushes, they clobber nothing.  */
    1581     12069320 :            && ! push_operand (dest, GET_MODE (dest)))
    1582      5909911 :     record_last_mem_set_info (last_set_insn);
    1583     56714194 : }
    1584              : 
    1585              : /* Top level function to create an expression hash table.
    1586              : 
    1587              :    Expression entries are placed in the hash table if
    1588              :    - they are of the form (set (pseudo-reg) src),
    1589              :    - src is something we want to perform GCSE on,
    1590              :    - none of the operands are subsequently modified in the block
    1591              : 
    1592              :    Currently src must be a pseudo-reg or a const_int.
    1593              : 
    1594              :    TABLE is the table computed.  */
    1595              : 
    1596              : static void
    1597       517278 : compute_hash_table_work (struct gcse_hash_table_d *table)
    1598              : {
    1599       517278 :   int i;
    1600              : 
    1601              :   /* re-Cache any INSN_LIST nodes we have allocated.  */
    1602       517278 :   clear_modify_mem_tables ();
    1603              :   /* Some working arrays used to track first and last set in each block.  */
    1604       517278 :   reg_avail_info = GNEWVEC (struct reg_avail_info, max_reg_num ());
    1605              : 
    1606     84785689 :   for (i = 0; i < max_reg_num (); ++i)
    1607     84268411 :     reg_avail_info[i].last_bb = NULL;
    1608              : 
    1609     10411638 :   FOR_EACH_BB_FN (current_bb, cfun)
    1610              :     {
    1611      9894360 :       rtx_insn *insn;
    1612      9894360 :       unsigned int regno;
    1613              : 
    1614              :       /* First pass over the instructions records information used to
    1615              :          determine when registers and memory are first and last set.  */
    1616    126841747 :       FOR_BB_INSNS (current_bb, insn)
    1617              :         {
    1618    116947387 :           if (!NONDEBUG_INSN_P (insn))
    1619     66049015 :             continue;
    1620              : 
    1621     50898372 :           if (auto call = dyn_cast<rtx_call_insn *> (insn))
    1622              :             {
    1623      3993563 :               hard_reg_set_iterator hrsi;
    1624              : 
    1625              :               /* We don't track modes of hard registers, so we need
    1626              :                  to be conservative and assume that partial kills
    1627              :                  are full kills.  */
    1628      3993563 :               HARD_REG_SET callee_clobbers
    1629      3993563 :                 = insn_callee_abi (call).full_and_partial_reg_clobbers ();
    1630    337441416 :               EXECUTE_IF_SET_IN_HARD_REG_SET (callee_clobbers, 0, regno, hrsi)
    1631    333447853 :                 record_last_reg_set_info (call, regno);
    1632              : 
    1633      7854324 :               if (! RTL_CONST_OR_PURE_CALL_P (call)
    1634       394122 :                   || RTL_LOOPING_CONST_OR_PURE_CALL_P (call)
    1635      4363041 :                   || can_throw_external (call))
    1636      3625615 :                 record_last_mem_set_info (call);
    1637              :             }
    1638              : 
    1639     50898372 :           note_stores (insn, record_last_set_info, insn);
    1640              :         }
    1641              : 
    1642              :       /* The next pass builds the hash table.  */
    1643    126841747 :       FOR_BB_INSNS (current_bb, insn)
    1644    116947387 :         if (NONDEBUG_INSN_P (insn))
    1645     50898372 :           hash_scan_insn (insn, table);
    1646              :     }
    1647              : 
    1648       517278 :   free (reg_avail_info);
    1649       517278 :   reg_avail_info = NULL;
    1650       517278 : }
    1651              : 
    1652              : /* Allocate space for the set/expr hash TABLE.
    1653              :    It is used to determine the number of buckets to use.  */
    1654              : 
    1655              : static void
    1656       517278 : alloc_hash_table (struct gcse_hash_table_d *table)
    1657              : {
    1658       517278 :   int n;
    1659              : 
    1660       517278 :   n = get_max_insn_count ();
    1661              : 
    1662       517278 :   table->size = n / 4;
    1663       517278 :   if (table->size < 11)
    1664       200310 :     table->size = 11;
    1665              : 
    1666              :   /* Attempt to maintain efficient use of hash table.
    1667              :      Making it an odd number is simplest for now.
    1668              :      ??? Later take some measurements.  */
    1669       517278 :   table->size |= 1;
    1670       517278 :   n = table->size * sizeof (struct gcse_expr *);
    1671       517278 :   table->table = GNEWVAR (struct gcse_expr *, n);
    1672       517278 : }
    1673              : 
    1674              : /* Free things allocated by alloc_hash_table.  */
    1675              : 
    1676              : static void
    1677       517278 : free_hash_table (struct gcse_hash_table_d *table)
    1678              : {
    1679       517278 :   free (table->table);
    1680            0 : }
    1681              : 
    1682              : /* Compute the expression hash table TABLE.  */
    1683              : 
    1684              : static void
    1685       517278 : compute_hash_table (struct gcse_hash_table_d *table)
    1686              : {
    1687              :   /* Initialize count of number of entries in hash table.  */
    1688       517278 :   table->n_elems = 0;
    1689       517278 :   memset (table->table, 0, table->size * sizeof (struct gcse_expr *));
    1690              : 
    1691       517278 :   compute_hash_table_work (table);
    1692       517278 : }
    1693              : 
    1694              : /* Expression tracking support.  */
    1695              : 
    1696              : /* Clear canon_modify_mem_list and modify_mem_list tables.  */
    1697              : static void
    1698      1034556 : clear_modify_mem_tables (void)
    1699              : {
    1700      1034556 :   unsigned i;
    1701      1034556 :   bitmap_iterator bi;
    1702              : 
    1703      5181622 :   EXECUTE_IF_SET_IN_BITMAP (modify_mem_list_set, 0, i, bi)
    1704              :     {
    1705      4147066 :       modify_mem_list[i].release ();
    1706      4147066 :       canon_modify_mem_list[i].release ();
    1707              :     }
    1708      1034556 :   bitmap_clear (modify_mem_list_set);
    1709      1034556 :   bitmap_clear (blocks_with_calls);
    1710      1034556 : }
    1711              : 
    1712              : /* Release memory used by modify_mem_list_set.  */
    1713              : 
    1714              : static void
    1715       517278 : free_modify_mem_tables (void)
    1716              : {
    1717       517278 :   clear_modify_mem_tables ();
    1718       517278 :   free (modify_mem_list);
    1719       517278 :   free (canon_modify_mem_list);
    1720       517278 :   modify_mem_list = 0;
    1721       517278 :   canon_modify_mem_list = 0;
    1722       517278 : }
    1723              : 
    1724              : /* Compute PRE+LCM working variables.  */
    1725              : 
    1726              : /* Local properties of expressions.  */
    1727              : 
    1728              : /* Nonzero for expressions that are transparent in the block.  */
    1729              : static sbitmap *transp;
    1730              : 
    1731              : /* Nonzero for expressions that are computed (available) in the block.  */
    1732              : static sbitmap *comp;
    1733              : 
    1734              : /* Nonzero for expressions that are locally anticipatable in the block.  */
    1735              : static sbitmap *antloc;
    1736              : 
    1737              : /* Nonzero for expressions where this block is an optimal computation
    1738              :    point.  */
    1739              : static sbitmap *pre_optimal;
    1740              : 
    1741              : /* Nonzero for expressions which are redundant in a particular block.  */
    1742              : static sbitmap *pre_redundant;
    1743              : 
    1744              : /* Nonzero for expressions which should be inserted on a specific edge.  */
    1745              : static sbitmap *pre_insert_map;
    1746              : 
    1747              : /* Nonzero for expressions which should be deleted in a specific block.  */
    1748              : static sbitmap *pre_delete_map;
    1749              : 
    1750              : /* Allocate vars used for PRE analysis.  */
    1751              : 
    1752              : static void
    1753       425225 : alloc_pre_mem (int n_blocks, int n_exprs)
    1754              : {
    1755       425225 :   transp = sbitmap_vector_alloc (n_blocks, n_exprs);
    1756       425225 :   comp = sbitmap_vector_alloc (n_blocks, n_exprs);
    1757       425225 :   antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
    1758              : 
    1759       425225 :   pre_optimal = NULL;
    1760       425225 :   pre_redundant = NULL;
    1761       425225 :   pre_insert_map = NULL;
    1762       425225 :   pre_delete_map = NULL;
    1763       425225 :   ae_kill = sbitmap_vector_alloc (n_blocks, n_exprs);
    1764              : 
    1765              :   /* pre_insert and pre_delete are allocated later.  */
    1766       425225 : }
    1767              : 
    1768              : /* Free vars used for PRE analysis.  */
    1769              : 
    1770              : static void
    1771       425225 : free_pre_mem (void)
    1772              : {
    1773       425225 :   sbitmap_vector_free (transp);
    1774       425225 :   sbitmap_vector_free (comp);
    1775              : 
    1776              :   /* ANTLOC and AE_KILL are freed just after pre_lcm finishes.  */
    1777              : 
    1778       425225 :   if (pre_optimal)
    1779            0 :     sbitmap_vector_free (pre_optimal);
    1780       425225 :   if (pre_redundant)
    1781            0 :     sbitmap_vector_free (pre_redundant);
    1782       425225 :   if (pre_insert_map)
    1783       425225 :     sbitmap_vector_free (pre_insert_map);
    1784       425225 :   if (pre_delete_map)
    1785       425225 :     sbitmap_vector_free (pre_delete_map);
    1786              : 
    1787       425225 :   transp = comp = NULL;
    1788       425225 :   pre_optimal = pre_redundant = pre_insert_map = pre_delete_map = NULL;
    1789       425225 : }
    1790              : 
    1791              : /* Remove certain expressions from anticipatable and transparent
    1792              :    sets of basic blocks that have incoming abnormal edge.
    1793              :    For PRE remove potentially trapping expressions to avoid placing
    1794              :    them on abnormal edges.  For hoisting remove memory references that
    1795              :    can be clobbered by calls.  */
    1796              : 
    1797              : static void
    1798       452420 : prune_expressions (bool pre_p)
    1799              : {
    1800       452420 :   struct gcse_expr *expr;
    1801       452420 :   unsigned int ui;
    1802       452420 :   basic_block bb;
    1803              : 
    1804       452420 :   auto_sbitmap prune_exprs (expr_hash_table.n_elems);
    1805       452420 :   bitmap_clear (prune_exprs);
    1806     22192060 :   for (ui = 0; ui < expr_hash_table.size; ui++)
    1807              :     {
    1808     31472592 :       for (expr = expr_hash_table.table[ui]; expr; expr = expr->next_same_hash)
    1809              :         {
    1810              :           /* Note potentially trapping expressions.  */
    1811     10185372 :           if (may_trap_p (expr->expr))
    1812              :             {
    1813      2550304 :               bitmap_set_bit (prune_exprs, expr->bitmap_index);
    1814      2550304 :               continue;
    1815              :             }
    1816              : 
    1817      7635068 :           if (!pre_p && contains_mem_rtx_p (expr->expr))
    1818              :             /* Note memory references that can be clobbered by a call.
    1819              :                We do not split abnormal edges in hoisting, so would
    1820              :                a memory reference get hoisted along an abnormal edge,
    1821              :                it would be placed /before/ the call.  Therefore, only
    1822              :                constant memory references can be hoisted along abnormal
    1823              :                edges.  */
    1824              :             {
    1825        46999 :               rtx x = expr->expr;
    1826              : 
    1827              :               /* Common cases where we might find the MEM which may allow us
    1828              :                  to avoid pruning the expression.  */
    1829        47913 :               while (GET_CODE (x) == ZERO_EXTEND || GET_CODE (x) == SIGN_EXTEND)
    1830          914 :                 x = XEXP (x, 0);
    1831              : 
    1832              :               /* If we found the MEM, go ahead and look at it to see if it has
    1833              :                  properties that allow us to avoid pruning its expression out
    1834              :                  of the tables.  */
    1835        46999 :               if (MEM_P (x))
    1836              :                 {
    1837        47697 :                   if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF
    1838        46920 :                       && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0)))
    1839          777 :                     continue;
    1840              : 
    1841        47869 :                   if (MEM_READONLY_P (x)
    1842         1753 :                       && !MEM_VOLATILE_P (x)
    1843        47896 :                       && MEM_NOTRAP_P (x))
    1844              :                     /* Constant memory reference, e.g., a PIC address.  */
    1845         1726 :                     continue;
    1846              :                 }
    1847              : 
    1848              :               /* ??? Optimally, we would use interprocedural alias
    1849              :                  analysis to determine if this mem is actually killed
    1850              :                  by this call.  */
    1851              : 
    1852        44496 :               bitmap_set_bit (prune_exprs, expr->bitmap_index);
    1853              :             }
    1854              :         }
    1855              :     }
    1856              : 
    1857     10041314 :   FOR_EACH_BB_FN (bb, cfun)
    1858              :     {
    1859      9588894 :       edge e;
    1860      9588894 :       edge_iterator ei;
    1861              : 
    1862              :       /* If the current block is the destination of an abnormal edge, we
    1863              :          kill all trapping (for PRE) and memory (for hoist) expressions
    1864              :          because we won't be able to properly place the instruction on
    1865              :          the edge.  So make them neither anticipatable nor transparent.
    1866              :          This is fairly conservative.
    1867              : 
    1868              :          ??? For hoisting it may be necessary to check for set-and-jump
    1869              :          instructions here, not just for abnormal edges.  The general problem
    1870              :          is that when an expression cannot not be placed right at the end of
    1871              :          a basic block we should account for any side-effects of a subsequent
    1872              :          jump instructions that could clobber the expression.  It would
    1873              :          be best to implement this check along the lines of
    1874              :          should_hoist_expr_to_dom where the target block is already known
    1875              :          and, hence, there's no need to conservatively prune expressions on
    1876              :          "intermediate" set-and-jump instructions.  */
    1877     23199726 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1878     13800465 :         if ((e->flags & EDGE_ABNORMAL)
    1879       189756 :             && (pre_p || CALL_P (BB_END (e->src))))
    1880              :           {
    1881       189633 :             bitmap_and_compl (antloc[bb->index],
    1882       189633 :                                 antloc[bb->index], prune_exprs);
    1883       189633 :             bitmap_and_compl (transp[bb->index],
    1884       189633 :                                 transp[bb->index], prune_exprs);
    1885       189633 :             break;
    1886              :           }
    1887              :     }
    1888       452420 : }
    1889              : 
    1890              : /* It may be necessary to insert a large number of insns on edges to
    1891              :    make the existing occurrences of expressions fully redundant.  This
    1892              :    routine examines the set of insertions and deletions and if the ratio
    1893              :    of insertions to deletions is too high for a particular expression, then
    1894              :    the expression is removed from the insertion/deletion sets.
    1895              : 
    1896              :    N_ELEMS is the number of elements in the hash table.  */
    1897              : 
    1898              : static void
    1899       425225 : prune_insertions_deletions (int n_elems)
    1900              : {
    1901       425225 :   sbitmap_iterator sbi;
    1902              : 
    1903              :   /* We always use I to iterate over blocks/edges and J to iterate over
    1904              :      expressions.  */
    1905       425225 :   unsigned int i, j;
    1906              : 
    1907              :   /* Counts for the number of times an expression needs to be inserted and
    1908              :      number of times an expression can be removed as a result.  */
    1909       425225 :   int *insertions = GCNEWVEC (int, n_elems);
    1910       425225 :   int *deletions = GCNEWVEC (int, n_elems);
    1911              : 
    1912              :   /* Set of expressions which require too many insertions relative to
    1913              :      the number of deletions achieved.  We will prune these out of the
    1914              :      insertion/deletion sets.  */
    1915       425225 :   auto_sbitmap prune_exprs (n_elems);
    1916       425225 :   bitmap_clear (prune_exprs);
    1917              : 
    1918              :   /* Iterate over the edges counting the number of times each expression
    1919              :      needs to be inserted.  */
    1920     15543905 :   for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
    1921              :     {
    1922     29688118 :       EXECUTE_IF_SET_IN_BITMAP (pre_insert_map[i], 0, j, sbi)
    1923       301208 :         insertions[j]++;
    1924              :     }
    1925              : 
    1926              :   /* Similarly for deletions, but those occur in blocks rather than on
    1927              :      edges.  */
    1928     11443806 :   for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
    1929              :     {
    1930     23009554 :       EXECUTE_IF_SET_IN_BITMAP (pre_delete_map[i], 0, j, sbi)
    1931       972392 :         deletions[j]++;
    1932              :     }
    1933              : 
    1934              :   /* Now that we have accurate counts, iterate over the elements in the
    1935              :      hash table and see if any need too many insertions relative to the
    1936              :      number of evaluations that can be removed.  If so, mark them in
    1937              :      PRUNE_EXPRS.  */
    1938     10294662 :   for (j = 0; j < (unsigned) n_elems; j++)
    1939      9869437 :     if (deletions[j]
    1940       364211 :         && (insertions[j] / deletions[j]) > param_max_gcse_insertion_ratio)
    1941          254 :       bitmap_set_bit (prune_exprs, j);
    1942              : 
    1943              :   /* Now prune PRE_INSERT_MAP and PRE_DELETE_MAP based on PRUNE_EXPRS.  */
    1944       850704 :   EXECUTE_IF_SET_IN_BITMAP (prune_exprs, 0, j, sbi)
    1945              :     {
    1946       251479 :       for (i = 0; i < (unsigned) n_edges_for_fn (cfun); i++)
    1947       251225 :         bitmap_clear_bit (pre_insert_map[i], j);
    1948              : 
    1949       167892 :       for (i = 0; i < (unsigned) last_basic_block_for_fn (cfun); i++)
    1950       167638 :         bitmap_clear_bit (pre_delete_map[i], j);
    1951              :     }
    1952              : 
    1953       425225 :   free (insertions);
    1954       425225 :   free (deletions);
    1955       425225 : }
    1956              : 
    1957              : /* Top level routine to do the dataflow analysis needed by PRE.  */
    1958              : 
    1959              : static struct edge_list *
    1960       425225 : compute_pre_data (void)
    1961              : {
    1962       425225 :   struct edge_list *edge_list;
    1963       425225 :   basic_block bb;
    1964              : 
    1965       425225 :   compute_local_properties (transp, comp, antloc, &expr_hash_table);
    1966       425225 :   prune_expressions (true);
    1967       425225 :   bitmap_vector_clear (ae_kill, last_basic_block_for_fn (cfun));
    1968              : 
    1969              :   /* Compute ae_kill for each basic block using:
    1970              : 
    1971              :      ~(TRANSP | COMP)
    1972              :   */
    1973              : 
    1974      9681829 :   FOR_EACH_BB_FN (bb, cfun)
    1975              :     {
    1976      9256604 :       bitmap_ior (ae_kill[bb->index], transp[bb->index], comp[bb->index]);
    1977      9256604 :       bitmap_not (ae_kill[bb->index], ae_kill[bb->index]);
    1978              :     }
    1979              : 
    1980       425225 :   if (doing_hardreg_pre_p)
    1981            0 :     prune_hardreg_uses (transp, &expr_hash_table);
    1982              : 
    1983       425225 :   edge_list = pre_edge_lcm (expr_hash_table.n_elems, transp, comp, antloc,
    1984              :                             ae_kill, &pre_insert_map, &pre_delete_map);
    1985       425225 :   sbitmap_vector_free (antloc);
    1986       425225 :   antloc = NULL;
    1987       425225 :   sbitmap_vector_free (ae_kill);
    1988       425225 :   ae_kill = NULL;
    1989              : 
    1990       425225 :   prune_insertions_deletions (expr_hash_table.n_elems);
    1991              : 
    1992       425225 :   return edge_list;
    1993              : }
    1994              : 
    1995              : /* PRE utilities */
    1996              : 
    1997              : /* Return true if an occurrence of expression EXPR in OCCR_BB would reach
    1998              :    block BB.
    1999              : 
    2000              :    VISITED is a pointer to a working buffer for tracking which BB's have
    2001              :    been visited.  It is NULL for the top-level call.
    2002              : 
    2003              :    We treat reaching expressions that go through blocks containing the same
    2004              :    reaching expression as "not reaching".  E.g. if EXPR is generated in blocks
    2005              :    2 and 3, INSN is in block 4, and 2->3->4, we treat the expression in block
    2006              :    2 as not reaching.  The intent is to improve the probability of finding
    2007              :    only one reaching expression and to reduce register lifetimes by picking
    2008              :    the closest such expression.  */
    2009              : 
    2010              : static bool
    2011     20104677 : pre_expr_reaches_here_p_work (basic_block occr_bb, struct gcse_expr *expr,
    2012              :                               basic_block bb, char *visited)
    2013              : {
    2014     20104677 :   edge pred;
    2015     20104677 :   edge_iterator ei;
    2016              : 
    2017     42866710 :   FOR_EACH_EDGE (pred, ei, bb->preds)
    2018              :     {
    2019     25510135 :       basic_block pred_bb = pred->src;
    2020              : 
    2021     25510135 :       if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)
    2022              :           /* Has predecessor has already been visited?  */
    2023     25186860 :           || visited[pred_bb->index])
    2024              :         ;/* Nothing to do.  */
    2025              : 
    2026              :       /* Does this predecessor generate this expression?  */
    2027     21096386 :       else if (bitmap_bit_p (comp[pred_bb->index], expr->bitmap_index))
    2028              :         {
    2029              :           /* Is this the occurrence we're looking for?
    2030              :              Note that there's only one generating occurrence per block
    2031              :              so we just need to check the block number.  */
    2032      2424381 :           if (occr_bb == pred_bb)
    2033              :             return true;
    2034              : 
    2035      2121764 :           visited[pred_bb->index] = 1;
    2036              :         }
    2037              :       /* Ignore this predecessor if it kills the expression.
    2038              : 
    2039              :          If this were used for hardreg pre, then it would need to use the kills
    2040              :          bitmap.  */
    2041     18672005 :       else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
    2042       183211 :         visited[pred_bb->index] = 1;
    2043              : 
    2044              :       /* Neither gen nor kill.  */
    2045              :       else
    2046              :         {
    2047     18488794 :           visited[pred_bb->index] = 1;
    2048     18488794 :           if (pre_expr_reaches_here_p_work (occr_bb, expr, pred_bb, visited))
    2049              :             return true;
    2050              :         }
    2051              :     }
    2052              : 
    2053              :   /* All paths have been checked.  */
    2054              :   return false;
    2055              : }
    2056              : 
    2057              : /* The wrapper for pre_expr_reaches_here_work that ensures that any
    2058              :    memory allocated for that function is returned.  */
    2059              : 
    2060              : static bool
    2061      1615883 : pre_expr_reaches_here_p (basic_block occr_bb, struct gcse_expr *expr,
    2062              :                          basic_block bb)
    2063              : {
    2064      1615883 :   bool rval;
    2065      1615883 :   char *visited = XCNEWVEC (char, last_basic_block_for_fn (cfun));
    2066              : 
    2067      1615883 :   rval = pre_expr_reaches_here_p_work (occr_bb, expr, bb, visited);
    2068              : 
    2069      1615883 :   free (visited);
    2070      1615883 :   return rval;
    2071              : }
    2072              : 
    2073              : /* Generate RTL to copy an EXP to REG and return it.  */
    2074              : 
    2075              : rtx_insn *
    2076       294638 : prepare_copy_insn (rtx reg, rtx exp)
    2077              : {
    2078       294638 :   rtx_insn *pat;
    2079              : 
    2080       294638 :   start_sequence ();
    2081              : 
    2082              :   /* If the expression is something that's an operand, like a constant,
    2083              :      just copy it to a register.  */
    2084       294638 :   if (general_operand (exp, GET_MODE (reg)))
    2085        92681 :     emit_move_insn (reg, exp);
    2086              : 
    2087              :   /* Otherwise, make a new insn to compute this expression and make sure the
    2088              :      insn will be recognized (this also adds any needed CLOBBERs).  */
    2089              :   else
    2090              :     {
    2091       201957 :       rtx_insn *insn = emit_insn (gen_rtx_SET (reg, exp));
    2092              : 
    2093       201957 :       if (insn_invalid_p (insn, false))
    2094            0 :         gcc_unreachable ();
    2095              :     }
    2096              : 
    2097       294638 :   pat = end_sequence ();
    2098              : 
    2099       294638 :   return pat;
    2100              : }
    2101              : 
    2102              : /* Generate RTL to copy an EXPR to its `reaching_reg' and return it.  */
    2103              : 
    2104              : static rtx_insn *
    2105       294627 : process_insert_insn (struct gcse_expr *expr)
    2106              : {
    2107       294627 :   rtx reg = expr->reaching_reg;
    2108              :   /* Copy the expression to make sure we don't have any sharing issues.  */
    2109       294627 :   rtx exp = copy_rtx (expr->expr);
    2110              : 
    2111       294627 :   return prepare_copy_insn (reg, exp);
    2112              : }
    2113              : 
    2114              : /* Return the INSN which is added at the end of the block BB with
    2115              :    same instruction pattern with PAT.  */
    2116              : 
    2117              : rtx_insn *
    2118        69256 : insert_insn_end_basic_block (rtx_insn *pat, basic_block bb)
    2119              : {
    2120        69256 :   rtx_insn *insn = BB_END (bb);
    2121        69256 :   rtx_insn *new_insn;
    2122        69256 :   rtx_insn *pat_end;
    2123              : 
    2124        69256 :   gcc_assert (pat && INSN_P (pat));
    2125              : 
    2126              :   pat_end = pat;
    2127        69798 :   while (NEXT_INSN (pat_end) != NULL_RTX)
    2128              :     pat_end = NEXT_INSN (pat_end);
    2129              : 
    2130              :   /* If the last insn is a jump, insert EXPR in front.  Similarly we need to
    2131              :      take care of trapping instructions in presence of non-call exceptions.  */
    2132              : 
    2133        69256 :   if (JUMP_P (insn)
    2134        69256 :       || (NONJUMP_INSN_P (insn)
    2135        18560 :           && (!single_succ_p (bb)
    2136         3510 :               || single_succ_edge (bb)->flags & EDGE_ABNORMAL)))
    2137              :     {
    2138              :       /* FIXME: What if something in jump uses value set in new insn?  */
    2139        24345 :       new_insn = emit_insn_before_noloc (pat, insn, bb);
    2140              :     }
    2141              : 
    2142              :   /* Likewise if the last insn is a call, as will happen in the presence
    2143              :      of exception handling.  */
    2144        44911 :   else if (CALL_P (insn)
    2145        86310 :            && (!single_succ_p (bb)
    2146         4921 :                || single_succ_edge (bb)->flags & EDGE_ABNORMAL))
    2147              :     {
    2148              :       /* Keeping in mind targets with small register classes and parameters
    2149              :          in registers, we search backward and place the instructions before
    2150              :          the first parameter is loaded.  Do this for everyone for consistency
    2151              :          and a presumption that we'll get better code elsewhere as well.  */
    2152              : 
    2153              :       /* Since different machines initialize their parameter registers
    2154              :          in different orders, assume nothing.  Collect the set of all
    2155              :          parameter registers.  */
    2156        41313 :       insn = find_first_parameter_load (as_a<rtx_call_insn *> (insn),
    2157              :                                         BB_HEAD (bb));
    2158              : 
    2159              :       /* If we found all the parameter loads, then we want to insert
    2160              :          before the first parameter load.
    2161              : 
    2162              :          If we did not find all the parameter loads, then we might have
    2163              :          stopped on the head of the block, which could be a CODE_LABEL.
    2164              :          If we inserted before the CODE_LABEL, then we would be putting
    2165              :          the insn in the wrong basic block.  In that case, put the insn
    2166              :          after the CODE_LABEL.  Also, respect NOTE_INSN_BASIC_BLOCK.  */
    2167        41313 :       while (LABEL_P (insn)
    2168        41313 :              || NOTE_INSN_BASIC_BLOCK_P (insn))
    2169            0 :         insn = NEXT_INSN (insn);
    2170              : 
    2171        41313 :       new_insn = emit_insn_before_noloc (pat, insn, bb);
    2172              :     }
    2173              :   else
    2174         3598 :     new_insn = emit_insn_after_noloc (pat, insn, bb);
    2175              : 
    2176          542 :   while (1)
    2177              :     {
    2178        69798 :       if (INSN_P (pat))
    2179        69798 :         add_label_notes (PATTERN (pat), new_insn);
    2180        69798 :       if (pat == pat_end)
    2181              :         break;
    2182          542 :       pat = NEXT_INSN (pat);
    2183              :     }
    2184        69256 :   return new_insn;
    2185              : }
    2186              : 
    2187              : /* Add EXPR to the end of basic block BB.
    2188              : 
    2189              :    This is used by both the PRE and code hoisting.  */
    2190              : 
    2191              : static void
    2192        69256 : insert_insn_end_basic_block (struct gcse_expr *expr, basic_block bb)
    2193              : {
    2194        69256 :   rtx reg = expr->reaching_reg;
    2195        69256 :   int regno = REGNO (reg);
    2196              : 
    2197        69256 :   rtx_insn *insn = process_insert_insn (expr);
    2198        69256 :   rtx_insn *new_insn = insert_insn_end_basic_block (insn, bb);
    2199              : 
    2200        69256 :   gcse_create_count++;
    2201              : 
    2202        69256 :   if (dump_file)
    2203              :     {
    2204            3 :       fprintf (dump_file, "PRE/HOIST: end of bb %d, insn %d, ",
    2205            3 :                bb->index, INSN_UID (new_insn));
    2206            3 :       fprintf (dump_file, "copying expression %d to reg %d\n",
    2207              :                expr->bitmap_index, regno);
    2208              :     }
    2209        69256 : }
    2210              : 
    2211              : /* Return the INSN which is added at the start of the block BB with
    2212              :    same instruction pattern with PAT.  */
    2213              : 
    2214              : rtx_insn *
    2215            0 : insert_insn_start_basic_block (rtx_insn *pat, basic_block bb)
    2216              : {
    2217            0 :   rtx_insn *insn = BB_HEAD (bb);
    2218            0 :   rtx_insn *next_insn;
    2219              : 
    2220            0 :   gcc_assert (pat && INSN_P (pat));
    2221              : 
    2222              :   /* Insert after the last initial CODE_LABEL or NOTE_INSN_BASIC_BLOCK, before
    2223              :      any other instructions.  */
    2224            0 :   while ((next_insn = NEXT_INSN (insn))
    2225            0 :          && (LABEL_P (next_insn) || NOTE_INSN_BASIC_BLOCK_P (insn)))
    2226              :     insn = next_insn;
    2227              : 
    2228            0 :   rtx_insn *new_insn = emit_insn_after_noloc (pat, insn, bb);
    2229              : 
    2230            0 :   while (pat != NULL_RTX)
    2231              :     {
    2232            0 :       if (INSN_P (pat))
    2233            0 :         add_label_notes (PATTERN (pat), new_insn);
    2234            0 :       pat = NEXT_INSN (pat);
    2235              :     }
    2236              : 
    2237            0 :   return new_insn;
    2238              : }
    2239              : 
    2240              : /* Add EXPR to the start of basic block BB.
    2241              : 
    2242              :    This is used by hardreg PRE.  */
    2243              : 
    2244              : static void
    2245            0 : insert_insn_start_basic_block (struct gcse_expr *expr, basic_block bb)
    2246              : {
    2247            0 :   rtx reg = expr->reaching_reg;
    2248            0 :   int regno = REGNO (reg);
    2249              : 
    2250            0 :   rtx_insn *insn = process_insert_insn (expr);
    2251            0 :   rtx_insn *new_insn = insert_insn_start_basic_block (insn, bb);
    2252              : 
    2253            0 :   gcse_create_count++;
    2254              : 
    2255            0 :   if (dump_file)
    2256              :     {
    2257            0 :       fprintf (dump_file, "hardreg PRE: start of bb %d, insn %d, ",
    2258            0 :                bb->index, INSN_UID (new_insn));
    2259            0 :       fprintf (dump_file, "copying expression %d to reg %d\n",
    2260              :                expr->bitmap_index, regno);
    2261              :     }
    2262            0 : }
    2263              : 
    2264              : /* Insert partially redundant expressions on edges in the CFG to make
    2265              :    the expressions fully redundant.  */
    2266              : 
    2267              : static bool
    2268       425225 : pre_edge_insert (struct edge_list *edge_list, struct gcse_expr **index_map)
    2269              : {
    2270       425225 :   int e, i, j, num_edges, set_size;
    2271       425225 :   bool did_insert = false;
    2272       425225 :   sbitmap *inserted;
    2273              : 
    2274              :   /* Where PRE_INSERT_MAP is nonzero, we add the expression on that edge
    2275              :      if it reaches any of the deleted expressions.  */
    2276              : 
    2277       425225 :   set_size = pre_insert_map[0]->size;
    2278       425225 :   num_edges = NUM_EDGES (edge_list);
    2279       425225 :   inserted = sbitmap_vector_alloc (num_edges, expr_hash_table.n_elems);
    2280       425225 :   bitmap_vector_clear (inserted, num_edges);
    2281              : 
    2282     15543905 :   for (e = 0; e < num_edges; e++)
    2283              :     {
    2284     14693455 :       int indx;
    2285     14693455 :       basic_block pred_bb = INDEX_EDGE_PRED_BB (edge_list, e);
    2286     14693455 :       basic_block succ_bb = INDEX_EDGE_SUCC_BB (edge_list, e);
    2287              : 
    2288     53524290 :       for (i = indx = 0; i < set_size; i++, indx += SBITMAP_ELT_BITS)
    2289              :         {
    2290     38830835 :           SBITMAP_ELT_TYPE insert = pre_insert_map[e]->elms[i];
    2291              : 
    2292     38830835 :           for (j = indx;
    2293     43239795 :                insert && j < (int) expr_hash_table.n_elems;
    2294      4408960 :                j++, insert >>= 1)
    2295      4408960 :             if ((insert & 1) != 0 && index_map[j]->reaching_reg != NULL_RTX)
    2296              :               {
    2297       281426 :                 struct gcse_expr *expr = index_map[j];
    2298       281426 :                 struct gcse_occr *occr;
    2299              : 
    2300              :                 /* Now look at each deleted occurrence of this expression.  */
    2301      1916271 :                 for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
    2302              :                   {
    2303      1634845 :                     if (! occr->deleted_p)
    2304       602476 :                       continue;
    2305              : 
    2306              :                     /* Insert this expression on this edge if it would
    2307              :                        reach the deleted occurrence in BB.  */
    2308      1032369 :                     if (!bitmap_bit_p (inserted[e], j))
    2309              :                       {
    2310       281426 :                         rtx_insn *insn;
    2311       281426 :                         edge eg = INDEX_EDGE (edge_list, e);
    2312              : 
    2313              :                         /* We can't insert anything on an abnormal and
    2314              :                            critical edge, so we insert the insn at the end of
    2315              :                            the previous block.  There are several alternatives
    2316              :                            detailed in Morgans book P277 (sec 10.5) for
    2317              :                            handling this situation.  This one is easiest for
    2318              :                            now.
    2319              : 
    2320              :                            For hardreg PRE  this would add an unwanted clobber
    2321              :                            of the hardreg, so we instead insert in the
    2322              :                            successor block. This may be partially redundant,
    2323              :                            but it is at least correct.  */
    2324       281426 :                         if (eg->flags & EDGE_ABNORMAL)
    2325              :                           {
    2326        56055 :                             if (doing_hardreg_pre_p)
    2327            0 :                               insert_insn_start_basic_block (index_map[j],
    2328              :                                                              succ_bb);
    2329              :                             else
    2330        56055 :                               insert_insn_end_basic_block (index_map[j],
    2331              :                                                            pred_bb);
    2332              :                           }
    2333              :                         else
    2334              :                           {
    2335       225371 :                             insn = process_insert_insn (index_map[j]);
    2336       225371 :                             insert_insn_on_edge (insn, eg);
    2337              :                           }
    2338              : 
    2339       281426 :                         if (dump_file)
    2340              :                           {
    2341            8 :                             fprintf (dump_file, "PRE: edge (%d,%d), ",
    2342              :                                      pred_bb->index,
    2343              :                                      succ_bb->index);
    2344            8 :                             fprintf (dump_file, "copy expression %d\n",
    2345              :                                      expr->bitmap_index);
    2346              :                           }
    2347              : 
    2348       281426 :                         update_ld_motion_stores (expr);
    2349       281426 :                         bitmap_set_bit (inserted[e], j);
    2350       281426 :                         did_insert = true;
    2351       281426 :                         gcse_create_count++;
    2352              :                       }
    2353              :                   }
    2354              :               }
    2355              :         }
    2356              :     }
    2357              : 
    2358       425225 :   sbitmap_vector_free (inserted);
    2359       425225 :   return did_insert;
    2360              : }
    2361              : 
    2362              : /* Copy the result of EXPR->EXPR generated by INSN to EXPR->REACHING_REG.
    2363              :    Given "old_reg <- expr" (INSN), instead of adding after it
    2364              :      reaching_reg <- old_reg
    2365              :    it's better to do the following:
    2366              :      reaching_reg <- expr
    2367              :      old_reg      <- reaching_reg
    2368              :    because this way copy propagation can discover additional PRE
    2369              :    opportunities.  But if this fails, we try the old way.
    2370              :    When "expr" is a store, i.e.
    2371              :    given "MEM <- old_reg", instead of adding after it
    2372              :      reaching_reg <- old_reg
    2373              :    it's better to add it before as follows:
    2374              :      reaching_reg <- old_reg
    2375              :      MEM          <- reaching_reg.  */
    2376              : 
    2377              : static void
    2378       302617 : pre_insert_copy_insn (struct gcse_expr *expr, rtx_insn *insn)
    2379              : {
    2380       302617 :   rtx reg = expr->reaching_reg;
    2381       302617 :   int regno = REGNO (reg);
    2382       302617 :   int indx = expr->bitmap_index;
    2383       302617 :   rtx pat = PATTERN (insn);
    2384       302617 :   rtx set, first_set;
    2385       302617 :   rtx_insn *new_insn;
    2386       302617 :   rtx old_reg;
    2387       302617 :   int i;
    2388              : 
    2389              :   /* This block matches the logic in hash_scan_insn.  */
    2390       302617 :   switch (GET_CODE (pat))
    2391              :     {
    2392              :     case SET:
    2393              :       set = pat;
    2394              :       break;
    2395              : 
    2396              :     case PARALLEL:
    2397              :       /* Search through the parallel looking for the set whose
    2398              :          source was the expression that we're interested in.  */
    2399              :       first_set = NULL_RTX;
    2400       204724 :       set = NULL_RTX;
    2401       204724 :       for (i = 0; i < XVECLEN (pat, 0); i++)
    2402              :         {
    2403       204636 :           rtx x = XVECEXP (pat, 0, i);
    2404       204636 :           if (GET_CODE (x) == SET)
    2405              :             {
    2406              :               /* If the source was a REG_EQUAL or REG_EQUIV note, we
    2407              :                  may not find an equivalent expression, but in this
    2408              :                  case the PARALLEL will have a single set.  */
    2409       204548 :               if (first_set == NULL_RTX)
    2410       204394 :                 first_set = x;
    2411       204548 :               if (expr_equiv_p (SET_SRC (x), expr->expr))
    2412              :                 {
    2413              :                   set = x;
    2414              :                   break;
    2415              :                 }
    2416              :             }
    2417              :         }
    2418              : 
    2419       204394 :       gcc_assert (first_set);
    2420       204394 :       if (set == NULL_RTX)
    2421           88 :         set = first_set;
    2422              :       break;
    2423              : 
    2424            0 :     default:
    2425            0 :       gcc_unreachable ();
    2426              :     }
    2427              : 
    2428       302617 :   if (REG_P (SET_DEST (set)))
    2429              :     {
    2430       302564 :       old_reg = SET_DEST (set);
    2431              :       /* Check if we can modify the set destination in the original insn.  */
    2432       302564 :       if (validate_change (insn, &SET_DEST (set), reg, 0))
    2433              :         {
    2434       302564 :           new_insn = gen_move_insn (old_reg, reg);
    2435       302564 :           new_insn = emit_insn_after (new_insn, insn);
    2436              :         }
    2437              :       else
    2438              :         {
    2439            0 :           new_insn = gen_move_insn (reg, old_reg);
    2440            0 :           new_insn = emit_insn_after (new_insn, insn);
    2441              :         }
    2442              :     }
    2443              :   else /* This is possible only in case of a store to memory.  */
    2444              :     {
    2445           53 :       old_reg = SET_SRC (set);
    2446           53 :       new_insn = gen_move_insn (reg, old_reg);
    2447              : 
    2448              :       /* Check if we can modify the set source in the original insn.  */
    2449           53 :       if (validate_change (insn, &SET_SRC (set), reg, 0))
    2450           53 :         new_insn = emit_insn_before (new_insn, insn);
    2451              :       else
    2452            0 :         new_insn = emit_insn_after (new_insn, insn);
    2453              :     }
    2454              : 
    2455       302617 :   gcse_create_count++;
    2456              : 
    2457       302617 :   if (dump_file)
    2458           24 :     fprintf (dump_file,
    2459              :              "PRE: bb %d, insn %d, copy expression %d in insn %d to reg %d\n",
    2460            8 :               BLOCK_FOR_INSN (insn)->index, INSN_UID (new_insn), indx,
    2461            8 :               INSN_UID (insn), regno);
    2462       302617 : }
    2463              : 
    2464              : /* Copy available expressions that reach the redundant expression
    2465              :    to `reaching_reg'.  */
    2466              : 
    2467              : static void
    2468       425225 : pre_insert_copies (void)
    2469              : {
    2470       425225 :   unsigned int i;
    2471       425225 :   bool added_copy;
    2472       425225 :   struct gcse_expr *expr;
    2473       425225 :   struct gcse_occr *occr;
    2474       425225 :   struct gcse_occr *avail;
    2475              : 
    2476              :   /* For each available expression in the table, copy the result to
    2477              :      `reaching_reg' if the expression reaches a deleted one.
    2478              : 
    2479              :      ??? The current algorithm is rather brute force.
    2480              :      Need to do some profiling.  */
    2481              : 
    2482     20870278 :   for (i = 0; i < expr_hash_table.size; i++)
    2483     30314490 :     for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
    2484              :       {
    2485              :         /* If the basic block isn't reachable, PPOUT will be TRUE.  However,
    2486              :            we don't want to insert a copy here because the expression may not
    2487              :            really be redundant.  So only insert an insn if the expression was
    2488              :            deleted.  This test also avoids further processing if the
    2489              :            expression wasn't deleted anywhere.  */
    2490      9869437 :         if (expr->reaching_reg == NULL)
    2491      9505481 :           continue;
    2492              : 
    2493              :         /* Set when we add a copy for that expression.  */
    2494       363956 :         added_copy = false;
    2495              : 
    2496      1699102 :         for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
    2497              :           {
    2498      1335146 :             if (! occr->deleted_p)
    2499       363293 :               continue;
    2500              : 
    2501     16506217 :             for (avail = expr->avail_occr; avail != NULL; avail = avail->next)
    2502              :               {
    2503     15534364 :                 rtx_insn *insn = avail->insn;
    2504              : 
    2505              :                 /* No need to handle this one if handled already.  */
    2506     15534364 :                 if (avail->copied_p)
    2507       385501 :                   continue;
    2508              : 
    2509              :                 /* Don't handle this one if it's a redundant one.  */
    2510     15148863 :                 if (insn->deleted ())
    2511     13532980 :                   continue;
    2512              : 
    2513              :                 /* Or if the expression doesn't reach the deleted one.  */
    2514      1615883 :                 if (! pre_expr_reaches_here_p (BLOCK_FOR_INSN (avail->insn),
    2515              :                                                expr,
    2516      1615883 :                                                BLOCK_FOR_INSN (occr->insn)))
    2517      1313266 :                   continue;
    2518              : 
    2519       302617 :                 added_copy = true;
    2520              : 
    2521              :                 /* Copy the result of avail to reaching_reg.  */
    2522       302617 :                 pre_insert_copy_insn (expr, insn);
    2523       302617 :                 avail->copied_p = 1;
    2524              :               }
    2525              :           }
    2526              : 
    2527       363956 :           if (added_copy)
    2528       250705 :             update_ld_motion_stores (expr);
    2529              :       }
    2530       425225 : }
    2531              : 
    2532              : struct set_data
    2533              : {
    2534              :   rtx_insn *insn;
    2535              :   const_rtx set;
    2536              :   int nsets;
    2537              : };
    2538              : 
    2539              : /* Increment number of sets and record set in DATA.  */
    2540              : 
    2541              : static void
    2542      1787924 : record_set_data (rtx dest, const_rtx set, void *data)
    2543              : {
    2544      1787924 :   struct set_data *s = (struct set_data *)data;
    2545              : 
    2546      1787924 :   if (GET_CODE (set) == SET)
    2547              :     {
    2548              :       /* We allow insns having multiple sets, where all but one are
    2549              :          dead as single set insns.  In the common case only a single
    2550              :          set is present, so we want to avoid checking for REG_UNUSED
    2551              :          notes unless necessary.  */
    2552       893962 :       if (s->nsets == 1
    2553            0 :           && find_reg_note (s->insn, REG_UNUSED, SET_DEST (s->set))
    2554       893962 :           && !side_effects_p (s->set))
    2555            0 :         s->nsets = 0;
    2556              : 
    2557       893962 :       if (!s->nsets)
    2558              :         {
    2559              :           /* Record this set.  */
    2560       893962 :           s->nsets += 1;
    2561       893962 :           s->set = set;
    2562              :         }
    2563            0 :       else if (!find_reg_note (s->insn, REG_UNUSED, dest)
    2564            0 :                || side_effects_p (set))
    2565            0 :         s->nsets += 1;
    2566              :     }
    2567      1787924 : }
    2568              : 
    2569              : static const_rtx
    2570      1744518 : single_set_gcse (rtx_insn *insn)
    2571              : {
    2572      1744518 :   struct set_data s;
    2573      1744518 :   rtx pattern;
    2574              : 
    2575      1744518 :   gcc_assert (INSN_P (insn));
    2576              : 
    2577              :   /* Optimize common case.  */
    2578      1744518 :   pattern = PATTERN (insn);
    2579      1744518 :   if (GET_CODE (pattern) == SET)
    2580              :     return pattern;
    2581              : 
    2582       893962 :   s.insn = insn;
    2583       893962 :   s.nsets = 0;
    2584       893962 :   note_pattern_stores (pattern, record_set_data, &s);
    2585              : 
    2586              :   /* Considered invariant insns have exactly one set.  */
    2587       893962 :   gcc_assert (s.nsets == 1);
    2588       893962 :   return s.set;
    2589              : }
    2590              : 
    2591              : /* Emit move from SRC to DEST noting the equivalence with expression computed
    2592              :    in INSN.  */
    2593              : 
    2594              : static rtx_insn *
    2595      1006213 : gcse_emit_move_after (rtx dest, rtx src, rtx_insn *insn)
    2596              : {
    2597      1006213 :   rtx_insn *new_rtx;
    2598      1006213 :   const_rtx set = single_set_gcse (insn);
    2599      1006213 :   rtx set2;
    2600      1006213 :   rtx note;
    2601      1006213 :   rtx eqv = NULL_RTX;
    2602              : 
    2603              :   /* This should never fail since we're creating a reg->reg copy
    2604              :      we've verified to be valid.  */
    2605              : 
    2606      1006213 :   new_rtx = emit_insn_after (gen_move_insn (dest, src), insn);
    2607              : 
    2608              :   /* Note the equivalence for local CSE pass.  Take the note from the old
    2609              :      set if there was one.  Otherwise record the SET_SRC from the old set
    2610              :      unless DEST is also an operand of the SET_SRC.  */
    2611      1006213 :   set2 = single_set (new_rtx);
    2612      1006213 :   if (!set2 || !rtx_equal_p (SET_DEST (set2), dest))
    2613              :     return new_rtx;
    2614      1006213 :   if ((note = find_reg_equal_equiv_note (insn)))
    2615       181771 :     eqv = XEXP (note, 0);
    2616       824442 :   else if (! REG_P (dest)
    2617       824442 :            || ! reg_mentioned_p (dest, SET_SRC (set)))
    2618       821629 :     eqv = SET_SRC (set);
    2619              : 
    2620      1003400 :   if (eqv != NULL_RTX)
    2621      1003400 :     set_unique_reg_note (new_rtx, REG_EQUAL, copy_insn_1 (eqv));
    2622              : 
    2623              :   return new_rtx;
    2624              : }
    2625              : 
    2626              : /* Delete redundant computations.
    2627              :    Deletion is done by changing the insn to copy the `reaching_reg' of
    2628              :    the expression into the result of the SET.  It is left to later passes
    2629              :    to propagate the copy or eliminate it.
    2630              : 
    2631              :    Return true if a change is made.  */
    2632              : 
    2633              : static bool
    2634       425225 : pre_delete (void)
    2635              : {
    2636       425225 :   unsigned int i;
    2637       425225 :   bool changed = false;
    2638       425225 :   struct gcse_expr *expr;
    2639       425225 :   struct gcse_occr *occr;
    2640              : 
    2641     20870278 :   for (i = 0; i < expr_hash_table.size; i++)
    2642     30314490 :     for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
    2643              :       {
    2644      9869437 :         int indx = expr->bitmap_index;
    2645              : 
    2646              :         /* We only need to search antic_occr since we require ANTLOC != 0.  */
    2647     16958035 :         for (occr = expr->antic_occr; occr != NULL; occr = occr->next)
    2648              :           {
    2649      7088598 :             rtx_insn *insn = occr->insn;
    2650      7088598 :             rtx set;
    2651      7088598 :             basic_block bb = BLOCK_FOR_INSN (insn);
    2652              : 
    2653              :             /* We only delete insns that have a single_set.  */
    2654      7088598 :             if (bitmap_bit_p (pre_delete_map[bb->index], indx)
    2655       971854 :                 && (set = single_set (insn)) != 0
    2656      8060451 :                 && dbg_cnt (pre_insn))
    2657              :               {
    2658       971853 :                 rtx dest = SET_DEST (set);
    2659       971853 :                 if (expr->reaching_reg == NULL)
    2660              :                   {
    2661       363956 :                     if (doing_hardreg_pre_p)
    2662              :                       /* Use the hardreg as the reaching register.  The
    2663              :                          deleted sets will be replaced with noop moves.
    2664              : 
    2665              :                          This may change the value of the hardreg in some debug
    2666              :                          instructions, so we will need to reset any debug uses
    2667              :                          of the hardreg.  */
    2668            0 :                       expr->reaching_reg = dest;
    2669              :                     else
    2670              :                       /* Create a pseudo-reg to store the result of reaching
    2671              :                          expressions into.  Get the mode for the new pseudo from
    2672              :                          the mode of the original destination pseudo.  */
    2673       363956 :                       expr->reaching_reg = gen_reg_rtx_and_attrs (SET_DEST (set));
    2674              :                   }
    2675              : 
    2676       971853 :                 gcse_emit_move_after (dest, expr->reaching_reg, insn);
    2677       971853 :                 delete_insn (insn);
    2678       971853 :                 occr->deleted_p = 1;
    2679       971853 :                 changed = true;
    2680       971853 :                 gcse_subst_count++;
    2681              : 
    2682       971853 :                 if (dump_file)
    2683              :                   {
    2684            8 :                     fprintf (dump_file,
    2685              :                              "PRE: redundant insn %d (expression %d) in ",
    2686            8 :                                INSN_UID (insn), indx);
    2687            8 :                     fprintf (dump_file, "bb %d, reaching reg is %d\n",
    2688            8 :                              bb->index, REGNO (expr->reaching_reg));
    2689              :                   }
    2690              :               }
    2691              :           }
    2692              :       }
    2693              : 
    2694       425225 :   return changed;
    2695              : }
    2696              : 
    2697              : /* Since hardreg PRE reuses the hardreg as the reaching register, we need to
    2698              :    eliminate any existing uses in debug insns.  This is overly conservative,
    2699              :    but there's currently no benefit to preserving the debug insns, so there's
    2700              :    no point doing the work to retain them.  */
    2701              : 
    2702              : static void
    2703            0 : reset_hardreg_debug_uses ()
    2704              : {
    2705            0 :   df_ref def;
    2706            0 :   for (def = DF_REG_USE_CHAIN (current_hardreg_regno);
    2707            0 :        def;
    2708            0 :        def = DF_REF_NEXT_REG (def))
    2709              :     {
    2710            0 :       rtx_insn *insn = DF_REF_INSN (def);
    2711            0 :       if (DEBUG_INSN_P (insn))
    2712            0 :         delete_insn (insn);
    2713              :     }
    2714            0 : }
    2715              : 
    2716              : /* Perform GCSE optimizations using PRE.
    2717              :    This is called by one_pre_gcse_pass after all the dataflow analysis
    2718              :    has been done.
    2719              : 
    2720              :    This is based on the original Morel-Renvoise paper Fred Chow's thesis, and
    2721              :    lazy code motion from Knoop, Ruthing and Steffen as described in Advanced
    2722              :    Compiler Design and Implementation.
    2723              : 
    2724              :    ??? A new pseudo reg is created to hold the reaching expression.  The nice
    2725              :    thing about the classical approach is that it would try to use an existing
    2726              :    reg.  If the register can't be adequately optimized [i.e. we introduce
    2727              :    reload problems], one could add a pass here to propagate the new register
    2728              :    through the block.
    2729              : 
    2730              :    ??? We don't handle single sets in PARALLELs because we're [currently] not
    2731              :    able to copy the rest of the parallel when we insert copies to create full
    2732              :    redundancies from partial redundancies.  However, there's no reason why we
    2733              :    can't handle PARALLELs in the cases where there are no partial
    2734              :    redundancies.  */
    2735              : 
    2736              : static bool
    2737       425225 : pre_gcse (struct edge_list *edge_list)
    2738              : {
    2739       425225 :   unsigned int i;
    2740       425225 :   bool did_insert, changed;
    2741       425225 :   struct gcse_expr **index_map;
    2742       425225 :   struct gcse_expr *expr;
    2743              : 
    2744              :   /* Compute a mapping from expression number (`bitmap_index') to
    2745              :      hash table entry.  */
    2746              : 
    2747       425225 :   index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
    2748     21295503 :   for (i = 0; i < expr_hash_table.size; i++)
    2749     30314490 :     for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
    2750      9869437 :       index_map[expr->bitmap_index] = expr;
    2751              : 
    2752              :   /* Delete the redundant insns first so that
    2753              :      - we know what register to use for the new insns and for the other
    2754              :        ones with reaching expressions
    2755              :      - we know which insns are redundant when we go to create copies  */
    2756              : 
    2757       425225 :   changed = pre_delete ();
    2758       425225 :   did_insert = pre_edge_insert (edge_list, index_map);
    2759              :   /* In other places with reaching expressions, copy the expression to the
    2760              :      specially allocated pseudo-reg that reaches the redundant expr.  This
    2761              :      isn't needed for hardreg PRE.  */
    2762       425225 :   if (!doing_hardreg_pre_p)
    2763       425225 :     pre_insert_copies ();
    2764              : 
    2765       425225 :   if (did_insert)
    2766              :     {
    2767        72765 :       if (doing_hardreg_pre_p)
    2768            0 :         reset_hardreg_debug_uses ();
    2769        72765 :       commit_edge_insertions ();
    2770        72765 :       changed = true;
    2771              :     }
    2772              : 
    2773       425225 :   free (index_map);
    2774       425225 :   return changed;
    2775              : }
    2776              : 
    2777              : /* Top level routine to perform one PRE GCSE pass.
    2778              : 
    2779              :    Return true if a change was made.  */
    2780              : 
    2781              : static bool
    2782       915747 : one_pre_gcse_pass (void)
    2783              : {
    2784       915747 :   bool changed = false;
    2785              : 
    2786       915747 :   gcse_subst_count = 0;
    2787       915747 :   gcse_create_count = 0;
    2788              : 
    2789              :   /* Return if there's nothing to do, or it is too expensive.  */
    2790       915747 :   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
    2791       915747 :       || gcse_or_cprop_is_too_expensive (_("PRE disabled")))
    2792              :     return false;
    2793              : 
    2794              :   /* We need alias.  */
    2795       486542 :   init_alias_analysis ();
    2796              : 
    2797       486542 :   bytes_used = 0;
    2798       486542 :   gcc_obstack_init (&gcse_obstack);
    2799       486542 :   alloc_gcse_mem ();
    2800              : 
    2801       486542 :   alloc_hash_table (&expr_hash_table);
    2802       486542 :   add_noreturn_fake_exit_edges ();
    2803       486542 :   if (do_load_motion ())
    2804       486540 :     compute_ld_motion_mems ();
    2805              : 
    2806       486542 :   compute_hash_table (&expr_hash_table);
    2807       486542 :   if (do_load_motion ())
    2808       486540 :     trim_ld_motion_mems ();
    2809       486542 :   if (dump_file)
    2810           17 :     dump_hash_table (dump_file, "Expression", &expr_hash_table);
    2811              : 
    2812       486542 :   if (expr_hash_table.n_elems > 0)
    2813              :     {
    2814       425225 :       struct edge_list *edge_list;
    2815       425225 :       alloc_pre_mem (last_basic_block_for_fn (cfun), expr_hash_table.n_elems);
    2816       425225 :       edge_list = compute_pre_data ();
    2817       425225 :       if (pre_gcse (edge_list))
    2818              :         changed = true;
    2819       425225 :       free_edge_list (edge_list);
    2820       425225 :       free_pre_mem ();
    2821              :     }
    2822              : 
    2823       486542 :   if (do_load_motion ())
    2824       486540 :     free_ld_motion_mems ();
    2825       486542 :   remove_fake_exit_edges ();
    2826       486542 :   free_hash_table (&expr_hash_table);
    2827              : 
    2828       486542 :   free_gcse_mem ();
    2829       486542 :   obstack_free (&gcse_obstack, NULL);
    2830              : 
    2831              :   /* We are finished with alias.  */
    2832       486542 :   end_alias_analysis ();
    2833              : 
    2834       486542 :   if (dump_file)
    2835              :     {
    2836           17 :       fprintf (dump_file, "PRE GCSE of %s, %d basic blocks, %d bytes needed, ",
    2837           17 :                current_function_name (), n_basic_blocks_for_fn (cfun),
    2838              :                bytes_used);
    2839           17 :       fprintf (dump_file, "%d substs, %d insns created\n",
    2840              :                gcse_subst_count, gcse_create_count);
    2841              :     }
    2842              : 
    2843              :   return changed;
    2844              : }
    2845              : 
    2846              : /* If X contains any LABEL_REF's, add REG_LABEL_OPERAND notes for them
    2847              :    to INSN.  If such notes are added to an insn which references a
    2848              :    CODE_LABEL, the LABEL_NUSES count is incremented.  We have to add
    2849              :    that note, because the following loop optimization pass requires
    2850              :    them.  */
    2851              : 
    2852              : /* ??? If there was a jump optimization pass after gcse and before loop,
    2853              :    then we would not need to do this here, because jump would add the
    2854              :    necessary REG_LABEL_OPERAND and REG_LABEL_TARGET notes.  */
    2855              : 
    2856              : static void
    2857       343692 : add_label_notes (rtx x, rtx_insn *insn)
    2858              : {
    2859       343692 :   enum rtx_code code = GET_CODE (x);
    2860       343692 :   int i, j;
    2861       343692 :   const char *fmt;
    2862              : 
    2863       343692 :   if (code == LABEL_REF && !LABEL_REF_NONLOCAL_P (x))
    2864              :     {
    2865              :       /* This code used to ignore labels that referred to dispatch tables to
    2866              :          avoid flow generating (slightly) worse code.
    2867              : 
    2868              :          We no longer ignore such label references (see LABEL_REF handling in
    2869              :          mark_jump_label for additional information).  */
    2870              : 
    2871              :       /* There's no reason for current users to emit jump-insns with
    2872              :          such a LABEL_REF, so we don't have to handle REG_LABEL_TARGET
    2873              :          notes.  */
    2874            0 :       gcc_assert (!JUMP_P (insn));
    2875            0 :       add_reg_note (insn, REG_LABEL_OPERAND, label_ref_label (x));
    2876              : 
    2877            0 :       if (LABEL_P (label_ref_label (x)))
    2878            0 :         LABEL_NUSES (label_ref_label (x))++;
    2879              : 
    2880              :       return;
    2881              :     }
    2882              : 
    2883       831717 :   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
    2884              :     {
    2885       488025 :       if (fmt[i] == 'e')
    2886       273840 :         add_label_notes (XEXP (x, i), insn);
    2887       214185 :       else if (fmt[i] == 'E')
    2888           81 :         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
    2889           54 :           add_label_notes (XVECEXP (x, i, j), insn);
    2890              :     }
    2891              : }
    2892              : 
    2893              : /* Code Hoisting variables and subroutines.  */
    2894              : 
    2895              : /* Very busy expressions.  */
    2896              : static sbitmap *hoist_vbein;
    2897              : static sbitmap *hoist_vbeout;
    2898              : 
    2899              : /* ??? We could compute post dominators and run this algorithm in
    2900              :    reverse to perform tail merging, doing so would probably be
    2901              :    more effective than the tail merging code in jump.cc.
    2902              : 
    2903              :    It's unclear if tail merging could be run in parallel with
    2904              :    code hoisting.  It would be nice.  */
    2905              : 
    2906              : /* Allocate vars used for code hoisting analysis.  */
    2907              : 
    2908              : static void
    2909        27195 : alloc_code_hoist_mem (int n_blocks, int n_exprs)
    2910              : {
    2911        27195 :   antloc = sbitmap_vector_alloc (n_blocks, n_exprs);
    2912        27195 :   transp = sbitmap_vector_alloc (n_blocks, n_exprs);
    2913        27195 :   comp = sbitmap_vector_alloc (n_blocks, n_exprs);
    2914              : 
    2915        27195 :   hoist_vbein = sbitmap_vector_alloc (n_blocks, n_exprs);
    2916        27195 :   hoist_vbeout = sbitmap_vector_alloc (n_blocks, n_exprs);
    2917        27195 : }
    2918              : 
    2919              : /* Free vars used for code hoisting analysis.  */
    2920              : 
    2921              : static void
    2922        27195 : free_code_hoist_mem (void)
    2923              : {
    2924        27195 :   sbitmap_vector_free (antloc);
    2925        27195 :   sbitmap_vector_free (transp);
    2926        27195 :   sbitmap_vector_free (comp);
    2927              : 
    2928        27195 :   sbitmap_vector_free (hoist_vbein);
    2929        27195 :   sbitmap_vector_free (hoist_vbeout);
    2930              : 
    2931        27195 :   free_dominance_info (CDI_DOMINATORS);
    2932        27195 : }
    2933              : 
    2934              : /* Compute the very busy expressions at entry/exit from each block.
    2935              : 
    2936              :    An expression is very busy if all paths from a given point
    2937              :    compute the expression.  */
    2938              : 
    2939              : static void
    2940        27195 : compute_code_hoist_vbeinout (void)
    2941              : {
    2942        27195 :   int changed, passes;
    2943        27195 :   basic_block bb;
    2944              : 
    2945        27195 :   bitmap_vector_clear (hoist_vbeout, last_basic_block_for_fn (cfun));
    2946        27195 :   bitmap_vector_clear (hoist_vbein, last_basic_block_for_fn (cfun));
    2947              : 
    2948        27195 :   passes = 0;
    2949        27195 :   changed = 1;
    2950              : 
    2951       111245 :   while (changed)
    2952              :     {
    2953        56855 :       changed = 0;
    2954              : 
    2955              :       /* We scan the blocks in the reverse order to speed up
    2956              :          the convergence.  */
    2957       909275 :       FOR_EACH_BB_REVERSE_FN (bb, cfun)
    2958              :         {
    2959       852420 :           if (bb->next_bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
    2960              :             {
    2961       795565 :               bitmap_intersection_of_succs (hoist_vbeout[bb->index],
    2962              :                                             hoist_vbein, bb);
    2963              : 
    2964              :               /* Include expressions in VBEout that are calculated
    2965              :                  in BB and available at its end.  */
    2966       795565 :               bitmap_ior (hoist_vbeout[bb->index],
    2967       795565 :                               hoist_vbeout[bb->index], comp[bb->index]);
    2968              :             }
    2969              : 
    2970       852420 :           changed |= bitmap_or_and (hoist_vbein[bb->index],
    2971       852420 :                                               antloc[bb->index],
    2972       852420 :                                               hoist_vbeout[bb->index],
    2973       852420 :                                               transp[bb->index]);
    2974              :         }
    2975              : 
    2976        56855 :       passes++;
    2977              :     }
    2978              : 
    2979        27195 :   if (dump_file)
    2980              :     {
    2981            7 :       fprintf (dump_file, "hoisting vbeinout computation: %d passes\n", passes);
    2982              : 
    2983           35 :       FOR_EACH_BB_FN (bb, cfun)
    2984              :         {
    2985           28 :           fprintf (dump_file, "vbein (%d): ", bb->index);
    2986           28 :           dump_bitmap_file (dump_file, hoist_vbein[bb->index]);
    2987           28 :           fprintf (dump_file, "vbeout(%d): ", bb->index);
    2988           28 :           dump_bitmap_file (dump_file, hoist_vbeout[bb->index]);
    2989              :         }
    2990              :     }
    2991        27195 : }
    2992              : 
    2993              : /* Top level routine to do the dataflow analysis needed by code hoisting.  */
    2994              : 
    2995              : static void
    2996        27195 : compute_code_hoist_data (void)
    2997              : {
    2998        27195 :   compute_local_properties (transp, comp, antloc, &expr_hash_table);
    2999        27195 :   prune_expressions (false);
    3000        27195 :   compute_code_hoist_vbeinout ();
    3001        27195 :   calculate_dominance_info (CDI_DOMINATORS);
    3002        27195 :   if (dump_file)
    3003            7 :     fprintf (dump_file, "\n");
    3004        27195 : }
    3005              : 
    3006              : /* Update register pressure for BB when hoisting an expression from
    3007              :    instruction FROM, if live ranges of inputs are shrunk.  Also
    3008              :    maintain live_in information if live range of register referred
    3009              :    in FROM is shrunk.
    3010              : 
    3011              :    Return 0 if register pressure doesn't change, otherwise return
    3012              :    the number by which register pressure is decreased.
    3013              : 
    3014              :    NOTE: Register pressure won't be increased in this function.  */
    3015              : 
    3016              : static int
    3017     12200040 : update_bb_reg_pressure (basic_block bb, rtx_insn *from)
    3018              : {
    3019     12200040 :   rtx dreg;
    3020     12200040 :   rtx_insn *insn;
    3021     12200040 :   basic_block succ_bb;
    3022     12200040 :   df_ref use, op_ref;
    3023     12200040 :   edge succ;
    3024     12200040 :   edge_iterator ei;
    3025     12200040 :   int decreased_pressure = 0;
    3026     12200040 :   int nregs;
    3027     12200040 :   enum reg_class pressure_class;
    3028              : 
    3029     14889962 :   FOR_EACH_INSN_USE (use, from)
    3030              :     {
    3031      2689922 :       dreg = DF_REF_REAL_REG (use);
    3032              :       /* The live range of register is shrunk only if it isn't:
    3033              :          1. referred on any path from the end of this block to EXIT, or
    3034              :          2. referred by insns other than FROM in this block.  */
    3035      3766895 :       FOR_EACH_EDGE (succ, ei, bb->succs)
    3036              :         {
    3037      3203079 :           succ_bb = succ->dest;
    3038      3203079 :           if (succ_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    3039         4259 :             continue;
    3040              : 
    3041      3198820 :           if (bitmap_bit_p (BB_DATA (succ_bb)->live_in, REGNO (dreg)))
    3042              :             break;
    3043              :         }
    3044      2689922 :       if (succ != NULL)
    3045      2126106 :         continue;
    3046              : 
    3047       563816 :       op_ref = DF_REG_USE_CHAIN (REGNO (dreg));
    3048      1799164 :       for (; op_ref; op_ref = DF_REF_NEXT_REG (op_ref))
    3049              :         {
    3050      1249073 :           if (!DF_REF_INSN_INFO (op_ref))
    3051       172584 :             continue;
    3052              : 
    3053      1076489 :           insn = DF_REF_INSN (op_ref);
    3054      1076489 :           if (BLOCK_FOR_INSN (insn) == bb
    3055      1076489 :               && NONDEBUG_INSN_P (insn) && insn != from)
    3056              :             break;
    3057              :         }
    3058              : 
    3059       563816 :       pressure_class = get_regno_pressure_class (REGNO (dreg), &nregs);
    3060              :       /* Decrease register pressure and update live_in information for
    3061              :          this block.  */
    3062       563816 :       if (!op_ref && pressure_class != NO_REGS)
    3063              :         {
    3064       549367 :           decreased_pressure += nregs;
    3065       549367 :           BB_DATA (bb)->max_reg_pressure[pressure_class] -= nregs;
    3066       549367 :           bitmap_clear_bit (BB_DATA (bb)->live_in, REGNO (dreg));
    3067              :         }
    3068              :     }
    3069     12200040 :   return decreased_pressure;
    3070              : }
    3071              : 
    3072              : /* Determine if the expression EXPR should be hoisted to EXPR_BB up in
    3073              :    flow graph, if it can reach BB unimpared.  Stop the search if the
    3074              :    expression would need to be moved more than DISTANCE instructions.
    3075              : 
    3076              :    DISTANCE is the number of instructions through which EXPR can be
    3077              :    hoisted up in flow graph.
    3078              : 
    3079              :    BB_SIZE points to an array which contains the number of instructions
    3080              :    for each basic block.
    3081              : 
    3082              :    PRESSURE_CLASS and NREGS are register class and number of hard registers
    3083              :    for storing EXPR.
    3084              : 
    3085              :    HOISTED_BBS points to a bitmap indicating basic blocks through which
    3086              :    EXPR is hoisted.
    3087              : 
    3088              :    FROM is the instruction from which EXPR is hoisted.
    3089              : 
    3090              :    It's unclear exactly what Muchnick meant by "unimpared".  It seems
    3091              :    to me that the expression must either be computed or transparent in
    3092              :    *every* block in the path(s) from EXPR_BB to BB.  Any other definition
    3093              :    would allow the expression to be hoisted out of loops, even if
    3094              :    the expression wasn't a loop invariant.
    3095              : 
    3096              :    Contrast this to reachability for PRE where an expression is
    3097              :    considered reachable if *any* path reaches instead of *all*
    3098              :    paths.  */
    3099              : 
    3100              : static bool
    3101     12200040 : should_hoist_expr_to_dom (basic_block expr_bb, struct gcse_expr *expr,
    3102              :                           basic_block bb, sbitmap visited,
    3103              :                           HOST_WIDE_INT distance,
    3104              :                           int *bb_size, enum reg_class pressure_class,
    3105              :                           int *nregs, bitmap hoisted_bbs, rtx_insn *from)
    3106              : {
    3107     12200040 :   unsigned int i;
    3108     12200040 :   edge pred;
    3109     12200040 :   edge_iterator ei;
    3110     12200040 :   sbitmap_iterator sbi;
    3111     12200040 :   bool visited_allocated_locally = false;
    3112     12200040 :   int decreased_pressure = 0;
    3113              : 
    3114     12200040 :   if (flag_ira_hoist_pressure)
    3115              :     {
    3116              :       /* Record old information of basic block BB when it is visited
    3117              :          at the first time.  */
    3118     12200040 :       if (!bitmap_bit_p (hoisted_bbs, bb->index))
    3119              :         {
    3120      6773800 :           struct bb_data *data = BB_DATA (bb);
    3121      6773800 :           bitmap_copy (data->backup, data->live_in);
    3122      6773800 :           data->old_pressure = data->max_reg_pressure[pressure_class];
    3123              :         }
    3124     12200040 :       decreased_pressure = update_bb_reg_pressure (bb, from);
    3125              :     }
    3126              :   /* Terminate the search if distance, for which EXPR is allowed to move,
    3127              :      is exhausted.  */
    3128     12200040 :   if (distance > 0)
    3129              :     {
    3130     12196859 :       if (flag_ira_hoist_pressure)
    3131              :         {
    3132              :           /* Prefer to hoist EXPR if register pressure is decreased.  */
    3133     12196859 :           if (decreased_pressure > *nregs)
    3134         2079 :             distance += bb_size[bb->index];
    3135              :           /* Let EXPR be hoisted through basic block at no cost if one
    3136              :              of following conditions is satisfied:
    3137              : 
    3138              :              1. The basic block has low register pressure.
    3139              :              2. Register pressure won't be increases after hoisting EXPR.
    3140              : 
    3141              :              Constant expressions is handled conservatively, because
    3142              :              hoisting constant expression aggressively results in worse
    3143              :              code.  This decision is made by the observation of CSiBE
    3144              :              on ARM target, while it has no obvious effect on other
    3145              :              targets like x86, x86_64, mips and powerpc.  */
    3146     12194780 :           else if (CONST_INT_P (expr->expr)
    3147     12013425 :                    || (BB_DATA (bb)->max_reg_pressure[pressure_class]
    3148     12013425 :                          >= ira_class_hard_regs_num[pressure_class]
    3149       156114 :                        && decreased_pressure < *nregs))
    3150       334616 :             distance -= bb_size[bb->index];
    3151              :         }
    3152              :       else
    3153            0 :         distance -= bb_size[bb->index];
    3154              : 
    3155     12196859 :       if (distance <= 0)
    3156              :         return 0;
    3157              :     }
    3158              :   else
    3159         3181 :     gcc_assert (distance == 0);
    3160              : 
    3161     12000222 :   if (visited == NULL)
    3162              :     {
    3163       618901 :       visited_allocated_locally = true;
    3164       618901 :       visited = sbitmap_alloc (last_basic_block_for_fn (cfun));
    3165       618901 :       bitmap_clear (visited);
    3166              :     }
    3167              : 
    3168     26976770 :   FOR_EACH_EDGE (pred, ei, bb->preds)
    3169              :     {
    3170     15970005 :       basic_block pred_bb = pred->src;
    3171              : 
    3172     15970005 :       if (pred->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
    3173              :         break;
    3174     15970005 :       else if (pred_bb == expr_bb)
    3175       615682 :         continue;
    3176     15354323 :       else if (bitmap_bit_p (visited, pred_bb->index))
    3177      3818466 :         continue;
    3178     11535857 :       else if (! bitmap_bit_p (transp[pred_bb->index], expr->bitmap_index))
    3179              :         break;
    3180              :       /* Not killed.  */
    3181              :       else
    3182              :         {
    3183     11496095 :           bitmap_set_bit (visited, pred_bb->index);
    3184     11496095 :           if (! should_hoist_expr_to_dom (expr_bb, expr, pred_bb,
    3185              :                                           visited, distance, bb_size,
    3186              :                                           pressure_class, nregs,
    3187              :                                           hoisted_bbs, from))
    3188              :             break;
    3189              :         }
    3190              :     }
    3191     12000222 :   if (visited_allocated_locally)
    3192              :     {
    3193              :       /* If EXPR can be hoisted to expr_bb, record basic blocks through
    3194              :          which EXPR is hoisted in hoisted_bbs.  */
    3195       618901 :       if (flag_ira_hoist_pressure && !pred)
    3196              :         {
    3197              :           /* Record the basic block from which EXPR is hoisted.  */
    3198       464365 :           bitmap_set_bit (visited, bb->index);
    3199     11886119 :           EXECUTE_IF_SET_IN_BITMAP (visited, 0, i, sbi)
    3200     10957389 :             bitmap_set_bit (hoisted_bbs, i);
    3201              :         }
    3202       618901 :       sbitmap_free (visited);
    3203              :     }
    3204              : 
    3205     12000222 :   return (pred == NULL);
    3206              : }
    3207              : 
    3208              : /* Find occurrence in BB.  */
    3209              : 
    3210              : static struct gcse_occr *
    3211      1256428 : find_occr_in_bb (struct gcse_occr *occr, basic_block bb)
    3212              : {
    3213              :   /* Find the right occurrence of this expression.  */
    3214     16414297 :   while (occr && BLOCK_FOR_INSN (occr->insn) != bb)
    3215     15157869 :     occr = occr->next;
    3216              : 
    3217      1256428 :   return occr;
    3218              : }
    3219              : 
    3220              : /* Actually perform code hoisting.
    3221              : 
    3222              :    The code hoisting pass can hoist multiple computations of the same
    3223              :    expression along dominated path to a dominating basic block, like
    3224              :    from b2/b3 to b1 as depicted below:
    3225              : 
    3226              :           b1      ------
    3227              :           /\         |
    3228              :          /  \        |
    3229              :         bx   by   distance
    3230              :        /      \      |
    3231              :       /        \     |
    3232              :      b2        b3 ------
    3233              : 
    3234              :    Unfortunately code hoisting generally extends the live range of an
    3235              :    output pseudo register, which increases register pressure and hurts
    3236              :    register allocation.  To address this issue, an attribute MAX_DISTANCE
    3237              :    is computed and attached to each expression.  The attribute is computed
    3238              :    from rtx cost of the corresponding expression and it's used to control
    3239              :    how long the expression can be hoisted up in flow graph.  As the
    3240              :    expression is hoisted up in flow graph, GCC decreases its DISTANCE
    3241              :    and stops the hoist if DISTANCE reaches 0.  Code hoisting can decrease
    3242              :    register pressure if live ranges of inputs are shrunk.
    3243              : 
    3244              :    Option "-fira-hoist-pressure" implements register pressure directed
    3245              :    hoist based on upper method.  The rationale is:
    3246              :      1. Calculate register pressure for each basic block by reusing IRA
    3247              :         facility.
    3248              :      2. When expression is hoisted through one basic block, GCC checks
    3249              :         the change of live ranges for inputs/output.  The basic block's
    3250              :         register pressure will be increased because of extended live
    3251              :         range of output.  However, register pressure will be decreased
    3252              :         if the live ranges of inputs are shrunk.
    3253              :      3. After knowing how hoisting affects register pressure, GCC prefers
    3254              :         to hoist the expression if it can decrease register pressure, by
    3255              :         increasing DISTANCE of the corresponding expression.
    3256              :      4. If hoisting the expression increases register pressure, GCC checks
    3257              :         register pressure of the basic block and decrease DISTANCE only if
    3258              :         the register pressure is high.  In other words, expression will be
    3259              :         hoisted through at no cost if the basic block has low register
    3260              :         pressure.
    3261              :      5. Update register pressure information for basic blocks through
    3262              :         which expression is hoisted.  */
    3263              : 
    3264              : static bool
    3265        27195 : hoist_code (void)
    3266              : {
    3267        27195 :   basic_block bb, dominated;
    3268        27195 :   unsigned int dom_tree_walk_index;
    3269        27195 :   unsigned int i, j, k;
    3270        27195 :   struct gcse_expr **index_map;
    3271        27195 :   struct gcse_expr *expr;
    3272        27195 :   int *to_bb_head;
    3273        27195 :   int *bb_size;
    3274        27195 :   bool changed = false;
    3275        27195 :   struct bb_data *data;
    3276              :   /* Basic blocks that have occurrences reachable from BB.  */
    3277        27195 :   bitmap from_bbs;
    3278              :   /* Basic blocks through which expr is hoisted.  */
    3279        27195 :   bitmap hoisted_bbs = NULL;
    3280        27195 :   bitmap_iterator bi;
    3281              : 
    3282              :   /* Compute a mapping from expression number (`bitmap_index') to
    3283              :      hash table entry.  */
    3284              : 
    3285        27195 :   index_map = XCNEWVEC (struct gcse_expr *, expr_hash_table.n_elems);
    3286       896557 :   for (i = 0; i < expr_hash_table.size; i++)
    3287      1158102 :     for (expr = expr_hash_table.table[i]; expr; expr = expr->next_same_hash)
    3288       315935 :       index_map[expr->bitmap_index] = expr;
    3289              : 
    3290              :   /* Calculate sizes of basic blocks and note how far
    3291              :      each instruction is from the start of its block.  We then use this
    3292              :      data to restrict distance an expression can travel.  */
    3293              : 
    3294        27195 :   to_bb_head = XCNEWVEC (int, get_max_uid ());
    3295        27195 :   bb_size = XCNEWVEC (int, last_basic_block_for_fn (cfun));
    3296              : 
    3297       359485 :   FOR_EACH_BB_FN (bb, cfun)
    3298              :     {
    3299       332290 :       rtx_insn *insn;
    3300       332290 :       int to_head;
    3301              : 
    3302       332290 :       to_head = 0;
    3303      2905847 :       FOR_BB_INSNS (bb, insn)
    3304              :         {
    3305              :           /* Don't count debug instructions to avoid them affecting
    3306              :              decision choices.  */
    3307      2573557 :           if (NONDEBUG_INSN_P (insn))
    3308      1913896 :             to_bb_head[INSN_UID (insn)] = to_head++;
    3309              :         }
    3310              : 
    3311       332290 :       bb_size[bb->index] = to_head;
    3312              :     }
    3313              : 
    3314        27195 :   gcc_assert (EDGE_COUNT (ENTRY_BLOCK_PTR_FOR_FN (cfun)->succs) == 1
    3315              :               && (EDGE_SUCC (ENTRY_BLOCK_PTR_FOR_FN (cfun), 0)->dest
    3316              :                   == ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb));
    3317              : 
    3318        27195 :   from_bbs = BITMAP_ALLOC (NULL);
    3319        27195 :   if (flag_ira_hoist_pressure)
    3320        27195 :     hoisted_bbs = BITMAP_ALLOC (NULL);
    3321              : 
    3322        27195 :   auto_vec<basic_block> dom_tree_walk
    3323              :   = get_all_dominated_blocks (CDI_DOMINATORS,
    3324        27195 :                               ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb);
    3325              : 
    3326              :   /* Walk over each basic block looking for potentially hoistable
    3327              :      expressions, nothing gets hoisted from the entry block.  */
    3328       386680 :   FOR_EACH_VEC_ELT (dom_tree_walk, dom_tree_walk_index, bb)
    3329              :     {
    3330       332290 :       auto_vec<basic_block> domby
    3331       332290 :         = get_dominated_to_depth (CDI_DOMINATORS, bb, param_max_hoist_depth);
    3332              : 
    3333       332290 :       if (domby.length () == 0)
    3334            0 :         continue;
    3335              : 
    3336              :       /* Examine each expression that is very busy at the exit of this
    3337              :          block.  These are the potentially hoistable expressions.  */
    3338     45975124 :       for (i = 0; i < SBITMAP_SIZE (hoist_vbeout[bb->index]); i++)
    3339              :         {
    3340     45642834 :           if (bitmap_bit_p (hoist_vbeout[bb->index], i))
    3341              :             {
    3342      3752711 :               int nregs = 0;
    3343      3752711 :               enum reg_class pressure_class = NO_REGS;
    3344              :               /* Current expression.  */
    3345      3752711 :               struct gcse_expr *expr = index_map[i];
    3346              :               /* Number of occurrences of EXPR that can be hoisted to BB.  */
    3347      3752711 :               int hoistable = 0;
    3348              :               /* Occurrences reachable from BB.  */
    3349      3752711 :               vec<occr_t> occrs_to_hoist = vNULL;
    3350              :               /* We want to insert the expression into BB only once, so
    3351              :                  note when we've inserted it.  */
    3352      3752711 :               int insn_inserted_p;
    3353      3752711 :               occr_t occr;
    3354              : 
    3355              :               /* If an expression is computed in BB and is available at end of
    3356              :                  BB, hoist all occurrences dominated by BB to BB.  */
    3357      3752711 :               if (bitmap_bit_p (comp[bb->index], i))
    3358              :                 {
    3359       278845 :                   occr = find_occr_in_bb (expr->antic_occr, bb);
    3360              : 
    3361       278845 :                   if (occr)
    3362              :                     {
    3363              :                       /* An occurrence might've been already deleted
    3364              :                          while processing a dominator of BB.  */
    3365       163133 :                       if (!occr->deleted_p)
    3366              :                         {
    3367       129635 :                           gcc_assert (NONDEBUG_INSN_P (occr->insn));
    3368              :                           hoistable++;
    3369              :                         }
    3370              :                     }
    3371              :                   else
    3372              :                     hoistable++;
    3373              :                 }
    3374              : 
    3375              :               /* We've found a potentially hoistable expression, now
    3376              :                  we look at every block BB dominates to see if it
    3377              :                  computes the expression.  */
    3378     47176268 :               FOR_EACH_VEC_ELT (domby, j, dominated)
    3379              :                 {
    3380     43423557 :                   HOST_WIDE_INT max_distance;
    3381              : 
    3382              :                   /* Ignore self dominance.  */
    3383     43423557 :                   if (bb == dominated)
    3384      3752711 :                     continue;
    3385              :                   /* We've found a dominated block, now see if it computes
    3386              :                      the busy expression and whether or not moving that
    3387              :                      expression to the "beginning" of that block is safe.  */
    3388     39670846 :                   if (!bitmap_bit_p (antloc[dominated->index], i))
    3389     38693263 :                     continue;
    3390              : 
    3391       977583 :                   occr = find_occr_in_bb (expr->antic_occr, dominated);
    3392       977583 :                   gcc_assert (occr);
    3393              : 
    3394              :                   /* An occurrence might've been already deleted
    3395              :                      while processing a dominator of BB.  */
    3396       977583 :                   if (occr->deleted_p)
    3397       273638 :                     continue;
    3398       703945 :                   gcc_assert (NONDEBUG_INSN_P (occr->insn));
    3399              : 
    3400       703945 :                   max_distance = expr->max_distance;
    3401       703945 :                   if (max_distance > 0)
    3402              :                     /* Adjust MAX_DISTANCE to account for the fact that
    3403              :                        OCCR won't have to travel all of DOMINATED, but
    3404              :                        only part of it.  */
    3405      1405504 :                     max_distance += (bb_size[dominated->index]
    3406       702752 :                                      - to_bb_head[INSN_UID (occr->insn)]);
    3407              : 
    3408       703945 :                   pressure_class = get_pressure_class_and_nregs (occr->insn,
    3409              :                                                                  &nregs);
    3410              : 
    3411              :                   /* Note if the expression should be hoisted from the dominated
    3412              :                      block to BB if it can reach DOMINATED unimpared.
    3413              : 
    3414              :                      Keep track of how many times this expression is hoistable
    3415              :                      from a dominated block into BB.  */
    3416       703945 :                   if (should_hoist_expr_to_dom (bb, expr, dominated, NULL,
    3417              :                                                 max_distance, bb_size,
    3418              :                                                 pressure_class, &nregs,
    3419              :                                                 hoisted_bbs, occr->insn))
    3420              :                     {
    3421       464365 :                       hoistable++;
    3422       464365 :                       occrs_to_hoist.safe_push (occr);
    3423       464365 :                       bitmap_set_bit (from_bbs, dominated->index);
    3424              :                     }
    3425              :                 }
    3426              : 
    3427              :               /* If we found more than one hoistable occurrence of this
    3428              :                  expression, then note it in the vector of expressions to
    3429              :                  hoist.  It makes no sense to hoist things which are computed
    3430              :                  in only one BB, and doing so tends to pessimize register
    3431              :                  allocation.  One could increase this value to try harder
    3432              :                  to avoid any possible code expansion due to register
    3433              :                  allocation issues; however experiments have shown that
    3434              :                  the vast majority of hoistable expressions are only movable
    3435              :                  from two successors, so raising this threshold is likely
    3436              :                  to nullify any benefit we get from code hoisting.  */
    3437      3752711 :               if (hoistable > 1 && dbg_cnt (hoist_insn))
    3438              :                 {
    3439              :                   /* If (hoistable != vec::length), then there is
    3440              :                      an occurrence of EXPR in BB itself.  Don't waste
    3441              :                      time looking for LCA in this case.  */
    3442       190910 :                   if ((unsigned) hoistable == occrs_to_hoist.length ())
    3443              :                     {
    3444        83348 :                       basic_block lca;
    3445              : 
    3446        83348 :                       lca = nearest_common_dominator_for_set (CDI_DOMINATORS,
    3447              :                                                               from_bbs);
    3448        83348 :                       if (lca != bb)
    3449              :                         /* Punt, it's better to hoist these occurrences to
    3450              :                            LCA.  */
    3451        82254 :                         occrs_to_hoist.release ();
    3452              :                     }
    3453              :                 }
    3454              :               else
    3455              :                 /* Punt, no point hoisting a single occurrence.  */
    3456      3657256 :                 occrs_to_hoist.release ();
    3457              : 
    3458      3752711 :               if (flag_ira_hoist_pressure
    3459      3752711 :                   && !occrs_to_hoist.is_empty ())
    3460              :                 {
    3461              :                   /* Increase register pressure of basic blocks to which
    3462              :                      expr is hoisted because of extended live range of
    3463              :                      output.  */
    3464        13201 :                   data = BB_DATA (bb);
    3465        13201 :                   data->max_reg_pressure[pressure_class] += nregs;
    3466       286098 :                   EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
    3467              :                     {
    3468       272897 :                       data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
    3469       272897 :                       data->max_reg_pressure[pressure_class] += nregs;
    3470              :                     }
    3471              :                 }
    3472      3739510 :               else if (flag_ira_hoist_pressure)
    3473              :                 {
    3474              :                   /* Restore register pressure and live_in info for basic
    3475              :                      blocks recorded in hoisted_bbs when expr will not be
    3476              :                      hoisted.  */
    3477      9010409 :                   EXECUTE_IF_SET_IN_BITMAP (hoisted_bbs, 0, k, bi)
    3478              :                     {
    3479      5270899 :                       data = BB_DATA (BASIC_BLOCK_FOR_FN (cfun, k));
    3480      5270899 :                       bitmap_copy (data->live_in, data->backup);
    3481      5270899 :                       data->max_reg_pressure[pressure_class]
    3482      5270899 :                           = data->old_pressure;
    3483              :                     }
    3484              :                 }
    3485              : 
    3486      3752711 :               if (flag_ira_hoist_pressure)
    3487      3752711 :                 bitmap_clear (hoisted_bbs);
    3488              : 
    3489      3752711 :               insn_inserted_p = 0;
    3490              : 
    3491              :               /* Walk through occurrences of I'th expressions we want
    3492              :                  to hoist to BB and make the transformations.  */
    3493      3800272 :               FOR_EACH_VEC_ELT (occrs_to_hoist, j, occr)
    3494              :                 {
    3495        34360 :                   rtx_insn *insn;
    3496        34360 :                   const_rtx set;
    3497              : 
    3498        34360 :                   gcc_assert (!occr->deleted_p);
    3499              : 
    3500        34360 :                   insn = occr->insn;
    3501        34360 :                   set = single_set_gcse (insn);
    3502              : 
    3503              :                   /* Create a pseudo-reg to store the result of reaching
    3504              :                      expressions into.  Get the mode for the new pseudo
    3505              :                      from the mode of the original destination pseudo.
    3506              : 
    3507              :                      It is important to use new pseudos whenever we
    3508              :                      emit a set.  This will allow reload to use
    3509              :                      rematerialization for such registers.  */
    3510        34360 :                   if (!insn_inserted_p)
    3511        13201 :                     expr->reaching_reg
    3512        13201 :                       = gen_reg_rtx_and_attrs (SET_DEST (set));
    3513              : 
    3514        34360 :                   gcse_emit_move_after (SET_DEST (set), expr->reaching_reg,
    3515              :                                         insn);
    3516        34360 :                   delete_insn (insn);
    3517        34360 :                   occr->deleted_p = 1;
    3518        34360 :                   changed = true;
    3519        34360 :                   gcse_subst_count++;
    3520              : 
    3521        34360 :                   if (!insn_inserted_p)
    3522              :                     {
    3523        13201 :                       insert_insn_end_basic_block (expr, bb);
    3524        13201 :                       insn_inserted_p = 1;
    3525              :                     }
    3526              :                 }
    3527              : 
    3528      3752711 :               occrs_to_hoist.release ();
    3529      3752711 :               bitmap_clear (from_bbs);
    3530              :             }
    3531              :         }
    3532       332290 :     }
    3533              : 
    3534        27195 :   BITMAP_FREE (from_bbs);
    3535        27195 :   if (flag_ira_hoist_pressure)
    3536        27195 :     BITMAP_FREE (hoisted_bbs);
    3537              : 
    3538        27195 :   free (bb_size);
    3539        27195 :   free (to_bb_head);
    3540        27195 :   free (index_map);
    3541              : 
    3542        27195 :   return changed;
    3543        27195 : }
    3544              : 
    3545              : /* Return pressure class and number of needed hard registers (through
    3546              :    *NREGS) of register REGNO.  */
    3547              : static enum reg_class
    3548      5970527 : get_regno_pressure_class (int regno, int *nregs)
    3549              : {
    3550      5970527 :   if (regno >= FIRST_PSEUDO_REGISTER)
    3551              :     {
    3552      3298442 :       enum reg_class pressure_class;
    3553              : 
    3554      3298442 :       pressure_class = reg_allocno_class (regno);
    3555      3298442 :       pressure_class = ira_pressure_class_translate[pressure_class];
    3556      3298442 :       *nregs
    3557      3298442 :         = ira_reg_class_max_nregs[pressure_class][PSEUDO_REGNO_MODE (regno)];
    3558      3298442 :       return pressure_class;
    3559              :     }
    3560      2672085 :   else if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)
    3561      2672085 :            && ! TEST_HARD_REG_BIT (eliminable_regset, regno))
    3562              :     {
    3563       822394 :       *nregs = 1;
    3564       822394 :       return ira_pressure_class_translate[REGNO_REG_CLASS (regno)];
    3565              :     }
    3566              :   else
    3567              :     {
    3568      1849691 :       *nregs = 0;
    3569      1849691 :       return NO_REGS;
    3570              :     }
    3571              : }
    3572              : 
    3573              : /* Return pressure class and number of hard registers (through *NREGS)
    3574              :    for destination of INSN. */
    3575              : static enum reg_class
    3576       703945 : get_pressure_class_and_nregs (rtx_insn *insn, int *nregs)
    3577              : {
    3578       703945 :   rtx reg;
    3579       703945 :   enum reg_class pressure_class;
    3580       703945 :   const_rtx set = single_set_gcse (insn);
    3581              : 
    3582       703945 :   reg = SET_DEST (set);
    3583       703945 :   if (GET_CODE (reg) == SUBREG)
    3584            0 :     reg = SUBREG_REG (reg);
    3585       703945 :   if (MEM_P (reg))
    3586              :     {
    3587            0 :       *nregs = 0;
    3588            0 :       pressure_class = NO_REGS;
    3589              :     }
    3590              :   else
    3591              :     {
    3592       703945 :       gcc_assert (REG_P (reg));
    3593       703945 :       pressure_class = reg_allocno_class (REGNO (reg));
    3594       703945 :       pressure_class = ira_pressure_class_translate[pressure_class];
    3595       703945 :       *nregs
    3596       703945 :         = ira_reg_class_max_nregs[pressure_class][GET_MODE (SET_SRC (set))];
    3597              :     }
    3598       703945 :   return pressure_class;
    3599              : }
    3600              : 
    3601              : /* Increase (if INCR_P) or decrease current register pressure for
    3602              :    register REGNO.  */
    3603              : static void
    3604      5406711 : change_pressure (int regno, bool incr_p)
    3605              : {
    3606      5406711 :   int nregs;
    3607      5406711 :   enum reg_class pressure_class;
    3608              : 
    3609      5406711 :   pressure_class = get_regno_pressure_class (regno, &nregs);
    3610      5406711 :   if (! incr_p)
    3611      1328252 :     curr_reg_pressure[pressure_class] -= nregs;
    3612              :   else
    3613              :     {
    3614      4078459 :       curr_reg_pressure[pressure_class] += nregs;
    3615      4078459 :       if (BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
    3616              :           < curr_reg_pressure[pressure_class])
    3617      1832906 :         BB_DATA (curr_bb)->max_reg_pressure[pressure_class]
    3618      1832906 :           = curr_reg_pressure[pressure_class];
    3619              :     }
    3620      5406711 : }
    3621              : 
    3622              : /* Calculate register pressure for each basic block by walking insns
    3623              :    from last to first.  */
    3624              : static void
    3625        30736 : calculate_bb_reg_pressure (void)
    3626              : {
    3627        30736 :   int i;
    3628        30736 :   unsigned int j;
    3629        30736 :   rtx_insn *insn;
    3630        30736 :   basic_block bb;
    3631        30736 :   bitmap curr_regs_live;
    3632        30736 :   bitmap_iterator bi;
    3633              : 
    3634              : 
    3635        30736 :   ira_setup_eliminable_regset ();
    3636        30736 :   curr_regs_live = BITMAP_ALLOC (&reg_obstack);
    3637       379778 :   FOR_EACH_BB_FN (bb, cfun)
    3638              :     {
    3639       349042 :       curr_bb = bb;
    3640       349042 :       BB_DATA (bb)->live_in = BITMAP_ALLOC (NULL);
    3641       349042 :       BB_DATA (bb)->backup = BITMAP_ALLOC (NULL);
    3642       349042 :       bitmap_copy (BB_DATA (bb)->live_in, df_get_live_in (bb));
    3643       349042 :       bitmap_copy (curr_regs_live, df_get_live_out (bb));
    3644      2096372 :       for (i = 0; i < ira_pressure_classes_num; i++)
    3645      1398288 :         curr_reg_pressure[ira_pressure_classes[i]] = 0;
    3646      3143853 :       EXECUTE_IF_SET_IN_BITMAP (curr_regs_live, 0, j, bi)
    3647      2794811 :         change_pressure (j, true);
    3648              : 
    3649      3010988 :       FOR_BB_INSNS_REVERSE (bb, insn)
    3650              :         {
    3651      2661946 :           rtx dreg;
    3652      2661946 :           int regno;
    3653      2661946 :           df_ref def, use;
    3654              : 
    3655      2661946 :           if (! NONDEBUG_INSN_P (insn))
    3656       692425 :             continue;
    3657              : 
    3658     17417137 :           FOR_EACH_INSN_DEF (def, insn)
    3659              :             {
    3660     15447616 :               dreg = DF_REF_REAL_REG (def);
    3661     15447616 :               gcc_assert (REG_P (dreg));
    3662     15447616 :               regno = REGNO (dreg);
    3663     15447616 :               if (!(DF_REF_FLAGS (def)
    3664              :                     & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
    3665              :                 {
    3666     15445255 :                   if (bitmap_clear_bit (curr_regs_live, regno))
    3667      1328252 :                     change_pressure (regno, false);
    3668              :                 }
    3669              :             }
    3670              : 
    3671      4272858 :           FOR_EACH_INSN_USE (use, insn)
    3672              :             {
    3673      2303337 :               dreg = DF_REF_REAL_REG (use);
    3674      2303337 :               gcc_assert (REG_P (dreg));
    3675      2303337 :               regno = REGNO (dreg);
    3676      2303337 :               if (bitmap_set_bit (curr_regs_live, regno))
    3677      1283648 :                 change_pressure (regno, true);
    3678              :             }
    3679              :         }
    3680              :     }
    3681        30736 :   BITMAP_FREE (curr_regs_live);
    3682              : 
    3683        30736 :   if (dump_file == NULL)
    3684        30729 :     return;
    3685              : 
    3686            7 :   fprintf (dump_file, "\nRegister Pressure: \n");
    3687           35 :   FOR_EACH_BB_FN (bb, cfun)
    3688              :     {
    3689           28 :       fprintf (dump_file, "  Basic block %d: \n", bb->index);
    3690          168 :       for (i = 0; (int) i < ira_pressure_classes_num; i++)
    3691              :         {
    3692          112 :           enum reg_class pressure_class;
    3693              : 
    3694          112 :           pressure_class = ira_pressure_classes[i];
    3695          112 :           if (BB_DATA (bb)->max_reg_pressure[pressure_class] == 0)
    3696           84 :             continue;
    3697              : 
    3698           28 :           fprintf (dump_file, "    %s=%d\n", reg_class_names[pressure_class],
    3699              :                    BB_DATA (bb)->max_reg_pressure[pressure_class]);
    3700              :         }
    3701              :     }
    3702            7 :   fprintf (dump_file, "\n");
    3703              : }
    3704              : 
    3705              : /* Top level routine to perform one code hoisting (aka unification) pass
    3706              : 
    3707              :    Return true if a change was made.  */
    3708              : 
    3709              : static bool
    3710        66184 : one_code_hoisting_pass (void)
    3711              : {
    3712        66184 :   bool changed = false;
    3713              : 
    3714        66184 :   gcse_subst_count = 0;
    3715        66184 :   gcse_create_count = 0;
    3716              : 
    3717              :   /* Return if there's nothing to do, or it is too expensive.  */
    3718        66184 :   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
    3719        66184 :       || gcse_or_cprop_is_too_expensive (_("GCSE disabled")))
    3720              :     return false;
    3721              : 
    3722        30736 :   doing_code_hoisting_p = true;
    3723              : 
    3724              :   /* Calculate register pressure for each basic block.  */
    3725        30736 :   if (flag_ira_hoist_pressure)
    3726              :     {
    3727        30736 :       regstat_init_n_sets_and_refs ();
    3728        30736 :       ira_set_pseudo_classes (false, dump_file);
    3729        30736 :       alloc_aux_for_blocks (sizeof (struct bb_data));
    3730        30736 :       calculate_bb_reg_pressure ();
    3731        30736 :       regstat_free_n_sets_and_refs ();
    3732              :     }
    3733              : 
    3734              :   /* We need alias.  */
    3735        30736 :   init_alias_analysis ();
    3736              : 
    3737        30736 :   bytes_used = 0;
    3738        30736 :   gcc_obstack_init (&gcse_obstack);
    3739        30736 :   alloc_gcse_mem ();
    3740              : 
    3741        30736 :   alloc_hash_table (&expr_hash_table);
    3742        30736 :   compute_hash_table (&expr_hash_table);
    3743        30736 :   if (dump_file)
    3744            7 :     dump_hash_table (dump_file, "Code Hosting Expressions", &expr_hash_table);
    3745              : 
    3746        30736 :   if (expr_hash_table.n_elems > 0)
    3747              :     {
    3748        27195 :       alloc_code_hoist_mem (last_basic_block_for_fn (cfun),
    3749              :                             expr_hash_table.n_elems);
    3750        27195 :       compute_code_hoist_data ();
    3751        27195 :       changed = hoist_code ();
    3752        27195 :       free_code_hoist_mem ();
    3753              :     }
    3754              : 
    3755        30736 :   if (flag_ira_hoist_pressure)
    3756              :     {
    3757        30736 :       free_aux_for_blocks ();
    3758        30736 :       free_reg_info ();
    3759              :     }
    3760        30736 :   free_hash_table (&expr_hash_table);
    3761        30736 :   free_gcse_mem ();
    3762        30736 :   obstack_free (&gcse_obstack, NULL);
    3763              : 
    3764              :   /* We are finished with alias.  */
    3765        30736 :   end_alias_analysis ();
    3766              : 
    3767        30736 :   if (dump_file)
    3768              :     {
    3769            7 :       fprintf (dump_file, "HOIST of %s, %d basic blocks, %d bytes needed, ",
    3770            7 :                current_function_name (), n_basic_blocks_for_fn (cfun),
    3771              :                bytes_used);
    3772            7 :       fprintf (dump_file, "%d substs, %d insns created\n",
    3773              :                gcse_subst_count, gcse_create_count);
    3774              :     }
    3775              : 
    3776        30736 :   doing_code_hoisting_p = false;
    3777              : 
    3778        30736 :   return changed;
    3779              : }
    3780              : 
    3781              : /*  Here we provide the things required to do store motion towards the exit.
    3782              :     In order for this to be effective, gcse also needed to be taught how to
    3783              :     move a load when it is killed only by a store to itself.
    3784              : 
    3785              :             int i;
    3786              :             float a[10];
    3787              : 
    3788              :             void foo(float scale)
    3789              :             {
    3790              :               for (i=0; i<10; i++)
    3791              :                 a[i] *= scale;
    3792              :             }
    3793              : 
    3794              :     'i' is both loaded and stored to in the loop. Normally, gcse cannot move
    3795              :     the load out since its live around the loop, and stored at the bottom
    3796              :     of the loop.
    3797              : 
    3798              :       The 'Load Motion' referred to and implemented in this file is
    3799              :     an enhancement to gcse which when using edge based LCM, recognizes
    3800              :     this situation and allows gcse to move the load out of the loop.
    3801              : 
    3802              :       Once gcse has hoisted the load, store motion can then push this
    3803              :     load towards the exit, and we end up with no loads or stores of 'i'
    3804              :     in the loop.  */
    3805              : 
    3806              : /* This will search the ldst list for a matching expression. If it
    3807              :    doesn't find one, we create one and initialize it.  */
    3808              : 
    3809              : static struct ls_expr *
    3810     14756239 : ldst_entry (rtx x)
    3811              : {
    3812     14756239 :   int do_not_record_p = 0;
    3813     14756239 :   struct ls_expr * ptr;
    3814     14756239 :   unsigned int hash;
    3815     14756239 :   ls_expr **slot;
    3816     14756239 :   struct ls_expr e;
    3817              : 
    3818     14756239 :   hash = hash_rtx (x, GET_MODE (x), &do_not_record_p,
    3819              :                    NULL,  /*have_reg_qty=*/false);
    3820              : 
    3821     14756239 :   e.pattern = x;
    3822     14756239 :   slot = pre_ldst_table->find_slot_with_hash (&e, hash, INSERT);
    3823     14756239 :   if (*slot)
    3824              :     return *slot;
    3825              : 
    3826      9711332 :   ptr = XNEW (struct ls_expr);
    3827              : 
    3828      9711332 :   ptr->next         = pre_ldst_mems;
    3829      9711332 :   ptr->expr         = NULL;
    3830      9711332 :   ptr->pattern      = x;
    3831      9711332 :   ptr->pattern_regs = NULL_RTX;
    3832      9711332 :   ptr->stores.create (0);
    3833      9711332 :   ptr->reaching_reg = NULL_RTX;
    3834      9711332 :   ptr->invalid      = 0;
    3835      9711332 :   ptr->index        = 0;
    3836      9711332 :   ptr->hash_index   = hash;
    3837      9711332 :   pre_ldst_mems     = ptr;
    3838      9711332 :   *slot = ptr;
    3839              : 
    3840      9711332 :   return ptr;
    3841              : }
    3842              : 
    3843              : /* Free up an individual ldst entry.  */
    3844              : 
    3845              : static void
    3846      9711332 : free_ldst_entry (struct ls_expr * ptr)
    3847              : {
    3848            0 :   ptr->stores.release ();
    3849              : 
    3850      9711332 :   free (ptr);
    3851            0 : }
    3852              : 
    3853              : /* Free up all memory associated with the ldst list.  */
    3854              : 
    3855              : static void
    3856       486540 : free_ld_motion_mems (void)
    3857              : {
    3858       486540 :   delete pre_ldst_table;
    3859       486540 :   pre_ldst_table = NULL;
    3860              : 
    3861      3706005 :   while (pre_ldst_mems)
    3862              :     {
    3863      3219465 :       struct ls_expr * tmp = pre_ldst_mems;
    3864              : 
    3865      3219465 :       pre_ldst_mems = pre_ldst_mems->next;
    3866              : 
    3867      3219465 :       free_ldst_entry (tmp);
    3868              :     }
    3869              : 
    3870       486540 :   pre_ldst_mems = NULL;
    3871       486540 : }
    3872              : 
    3873              : /* Dump debugging info about the ldst list.  */
    3874              : 
    3875              : static void
    3876           16 : print_ldst_list (FILE * file)
    3877              : {
    3878           16 :   struct ls_expr * ptr;
    3879              : 
    3880           16 :   fprintf (file, "LDST list: \n");
    3881              : 
    3882           56 :   for (ptr = pre_ldst_mems; ptr != NULL; ptr = ptr->next)
    3883              :     {
    3884           40 :       fprintf (file, "  Pattern (%3d): ", ptr->index);
    3885              : 
    3886           40 :       print_rtl (file, ptr->pattern);
    3887              : 
    3888           40 :       fprintf (file, "\n   Stores : ");
    3889           40 :       print_rtx_insn_vec (file, ptr->stores);
    3890              : 
    3891           40 :       fprintf (file, "\n\n");
    3892              :     }
    3893              : 
    3894           16 :   fprintf (file, "\n");
    3895           16 : }
    3896              : 
    3897              : /* Returns 1 if X is in the list of ldst only expressions.  */
    3898              : 
    3899              : static struct ls_expr *
    3900       642018 : find_rtx_in_ldst (rtx x)
    3901              : {
    3902       642018 :   struct ls_expr e;
    3903       642018 :   ls_expr **slot;
    3904       642018 :   if (!pre_ldst_table)
    3905              :     return NULL;
    3906       642018 :   e.pattern = x;
    3907       642018 :   slot = pre_ldst_table->find_slot (&e, NO_INSERT);
    3908       642018 :   if (!slot || (*slot)->invalid)
    3909       467452 :     return NULL;
    3910              :   return *slot;
    3911              : }
    3912              : 
    3913              : /* Load Motion for loads which only kill themselves.  */
    3914              : 
    3915              : /* Return true if x, a MEM, is a simple access with no side effects.
    3916              :    These are the types of loads we consider for the ld_motion list,
    3917              :    otherwise we let the usual aliasing take care of it.  */
    3918              : 
    3919              : static bool
    3920     19580855 : simple_mem (const_rtx x)
    3921              : {
    3922     19580855 :   if (MEM_VOLATILE_P (x))
    3923              :     return false;
    3924              : 
    3925     18664737 :   if (GET_MODE (x) == BLKmode)
    3926              :     return false;
    3927              : 
    3928              :   /* If we are handling exceptions, we must be careful with memory references
    3929              :      that may trap.  If we are not, the behavior is undefined, so we may just
    3930              :      continue.  */
    3931     18622927 :   if (cfun->can_throw_non_call_exceptions && may_trap_p (x))
    3932              :     return false;
    3933              : 
    3934     16447491 :   if (side_effects_p (x))
    3935              :     return false;
    3936              : 
    3937              :   /* Do not consider function arguments passed on stack.  */
    3938     15000273 :   if (reg_mentioned_p (stack_pointer_rtx, x))
    3939              :     return false;
    3940              : 
    3941     14758298 :   if (flag_float_store && FLOAT_MODE_P (GET_MODE (x)))
    3942         2058 :     return false;
    3943              : 
    3944              :   return true;
    3945              : }
    3946              : 
    3947              : /* Make sure there isn't a buried reference in this pattern anywhere.
    3948              :    If there is, invalidate the entry for it since we're not capable
    3949              :    of fixing it up just yet.. We have to be sure we know about ALL
    3950              :    loads since the aliasing code will allow all entries in the
    3951              :    ld_motion list to not-alias itself.  If we miss a load, we will get
    3952              :    the wrong value since gcse might common it and we won't know to
    3953              :    fix it up.  */
    3954              : 
    3955              : static void
    3956    168842631 : invalidate_any_buried_refs (rtx x)
    3957              : {
    3958    168842631 :   const char * fmt;
    3959    168842631 :   int i, j;
    3960    168842631 :   struct ls_expr * ptr;
    3961              : 
    3962              :   /* Invalidate it in the list.  */
    3963    168842631 :   if (MEM_P (x) && simple_mem (x))
    3964              :     {
    3965      5175802 :       ptr = ldst_entry (x);
    3966      5175802 :       ptr->invalid = 1;
    3967              :     }
    3968              : 
    3969              :   /* Recursively process the insn.  */
    3970    168842631 :   fmt = GET_RTX_FORMAT (GET_CODE (x));
    3971              : 
    3972    395343217 :   for (i = GET_RTX_LENGTH (GET_CODE (x)) - 1; i >= 0; i--)
    3973              :     {
    3974    226500586 :       if (fmt[i] == 'e')
    3975    101417337 :         invalidate_any_buried_refs (XEXP (x, i));
    3976    125083249 :       else if (fmt[i] == 'E')
    3977     30364718 :         for (j = XVECLEN (x, i) - 1; j >= 0; j--)
    3978     20714698 :           invalidate_any_buried_refs (XVECEXP (x, i, j));
    3979              :     }
    3980    168842631 : }
    3981              : 
    3982              : /* Find all the 'simple' MEMs which are used in LOADs and STORES.  Simple
    3983              :    being defined as MEM loads and stores to symbols, with no side effects
    3984              :    and no registers in the expression.  For a MEM destination, we also
    3985              :    check that the insn is still valid if we replace the destination with a
    3986              :    REG, as is done in update_ld_motion_stores.  If there are any uses/defs
    3987              :    which don't match this criteria, they are invalidated and trimmed out
    3988              :    later.  */
    3989              : 
    3990              : static void
    3991       486540 : compute_ld_motion_mems (void)
    3992              : {
    3993       486540 :   struct ls_expr * ptr;
    3994       486540 :   basic_block bb;
    3995       486540 :   rtx_insn *insn;
    3996              : 
    3997       486540 :   pre_ldst_mems = NULL;
    3998       486540 :   pre_ldst_table = new hash_table<pre_ldst_expr_hasher> (13);
    3999              : 
    4000     10031830 :   FOR_EACH_BB_FN (bb, cfun)
    4001              :     {
    4002    123830569 :       FOR_BB_INSNS (bb, insn)
    4003              :         {
    4004    114285279 :           if (NONDEBUG_INSN_P (insn))
    4005              :             {
    4006     48928755 :               if (GET_CODE (PATTERN (insn)) == SET)
    4007              :                 {
    4008     38415874 :                   rtx src = SET_SRC (PATTERN (insn));
    4009     38415874 :                   rtx dest = SET_DEST (PATTERN (insn));
    4010              : 
    4011              :                   /* Check for a simple load.  */
    4012     38415874 :                   if (MEM_P (src) && simple_mem (src))
    4013              :                     {
    4014      4879339 :                       ptr = ldst_entry (src);
    4015      4879339 :                       if (!REG_P (dest))
    4016        35096 :                         ptr->invalid = 1;
    4017              :                     }
    4018              :                   else
    4019              :                     {
    4020              :                       /* Make sure there isn't a buried load somewhere.  */
    4021     33536535 :                       invalidate_any_buried_refs (src);
    4022              :                     }
    4023              : 
    4024              :                   /* Check for a simple load through a REG_EQUAL note.  */
    4025     38415874 :                   rtx note = find_reg_equal_equiv_note (insn), src_eq;
    4026     38415874 :                   if (note
    4027      2308753 :                       && REG_NOTE_KIND (note) == REG_EQUAL
    4028      2166982 :                       && (src_eq = XEXP (note, 0))
    4029     40582856 :                       && !(MEM_P (src_eq) && simple_mem (src_eq)))
    4030      2166981 :                     invalidate_any_buried_refs (src_eq);
    4031              : 
    4032              :                   /* Check for stores. Don't worry about aliased ones, they
    4033              :                      will block any movement we might do later. We only care
    4034              :                      about this exact pattern since those are the only
    4035              :                      circumstance that we will ignore the aliasing info.  */
    4036     38415874 :                   if (MEM_P (dest) && simple_mem (dest))
    4037              :                     {
    4038      4701098 :                       ptr = ldst_entry (dest);
    4039      4701098 :                       machine_mode src_mode = GET_MODE (src);
    4040      4701098 :                       if (! MEM_P (src)
    4041      4701098 :                           && GET_CODE (src) != ASM_OPERANDS
    4042              :                           /* Check for REG manually since want_to_gcse_p
    4043              :                              returns 0 for all REGs.  */
    4044      9402196 :                           && can_assign_to_reg_without_clobbers_p (src,
    4045              :                                                                     src_mode))
    4046      4692679 :                         ptr->stores.safe_push (insn);
    4047              :                       else
    4048         8419 :                         ptr->invalid = 1;
    4049              :                     }
    4050              :                 }
    4051              :               else
    4052              :                 {
    4053              :                   /* Invalidate all MEMs in the pattern and...  */
    4054     10512881 :                   invalidate_any_buried_refs (PATTERN (insn));
    4055              : 
    4056              :                   /* ...in REG_EQUAL notes for PARALLELs with single SET.  */
    4057     10512881 :                   rtx note = find_reg_equal_equiv_note (insn), src_eq;
    4058     10512881 :                   if (note
    4059       494199 :                       && REG_NOTE_KIND (note) == REG_EQUAL
    4060     11007080 :                       && (src_eq = XEXP (note, 0)))
    4061       494199 :                     invalidate_any_buried_refs (src_eq);
    4062              :                 }
    4063              :             }
    4064              :         }
    4065              :     }
    4066       486540 : }
    4067              : 
    4068              : /* Remove any references that have been either invalidated or are not in the
    4069              :    expression list for pre gcse.  */
    4070              : 
    4071              : static void
    4072       486540 : trim_ld_motion_mems (void)
    4073              : {
    4074       486540 :   struct ls_expr * * last = & pre_ldst_mems;
    4075       486540 :   struct ls_expr * ptr = pre_ldst_mems;
    4076              : 
    4077     10197872 :   while (ptr != NULL)
    4078              :     {
    4079      9711332 :       struct gcse_expr * expr;
    4080              : 
    4081              :       /* Delete if entry has been made invalid.  */
    4082      9711332 :       if (! ptr->invalid)
    4083              :         {
    4084              :           /* Delete if we cannot find this mem in the expression list.  */
    4085      6942336 :           unsigned int hash = ptr->hash_index % expr_hash_table.size;
    4086              : 
    4087      6942336 :           for (expr = expr_hash_table.table[hash];
    4088     10520495 :                expr != NULL;
    4089      3578159 :                expr = expr->next_same_hash)
    4090      6797624 :             if (expr_equiv_p (expr->expr, ptr->pattern))
    4091              :               break;
    4092              :         }
    4093              :       else
    4094              :         expr = (struct gcse_expr *) 0;
    4095              : 
    4096      6942336 :       if (expr)
    4097              :         {
    4098              :           /* Set the expression field if we are keeping it.  */
    4099      3219465 :           ptr->expr = expr;
    4100      3219465 :           last = & ptr->next;
    4101      3219465 :           ptr = ptr->next;
    4102              :         }
    4103              :       else
    4104              :         {
    4105      6491867 :           *last = ptr->next;
    4106      6491867 :           pre_ldst_table->remove_elt_with_hash (ptr, ptr->hash_index);
    4107      6491867 :           free_ldst_entry (ptr);
    4108      6491867 :           ptr = * last;
    4109              :         }
    4110              :     }
    4111              : 
    4112              :   /* Show the world what we've found.  */
    4113       486540 :   if (dump_file && pre_ldst_mems != NULL)
    4114           16 :     print_ldst_list (dump_file);
    4115       486540 : }
    4116              : 
    4117              : /* This routine will take an expression which we are replacing with
    4118              :    a reaching register, and update any stores that are needed if
    4119              :    that expression is in the ld_motion list.  Stores are updated by
    4120              :    copying their SRC to the reaching register, and then storing
    4121              :    the reaching register into the store location. These keeps the
    4122              :    correct value in the reaching register for the loads.  */
    4123              : 
    4124              : static void
    4125       532131 : update_ld_motion_stores (struct gcse_expr * expr)
    4126              : {
    4127       532131 :   struct ls_expr * mem_ptr;
    4128              : 
    4129       532131 :   if ((mem_ptr = find_rtx_in_ldst (expr->expr)))
    4130              :     {
    4131              :       /* We can try to find just the REACHED stores, but is shouldn't
    4132              :          matter to set the reaching reg everywhere...  some might be
    4133              :          dead and should be eliminated later.  */
    4134              : 
    4135              :       /* We replace (set mem expr) with (set reg expr) (set mem reg)
    4136              :          where reg is the reaching reg used in the load.  We checked in
    4137              :          compute_ld_motion_mems that we can replace (set mem expr) with
    4138              :          (set reg expr) in that insn.  */
    4139       105171 :       rtx_insn *insn;
    4140       105171 :       unsigned int i;
    4141       148906 :       FOR_EACH_VEC_ELT_REVERSE (mem_ptr->stores, i, insn)
    4142              :         {
    4143        35700 :           rtx pat = PATTERN (insn);
    4144        35700 :           rtx src = SET_SRC (pat);
    4145        35700 :           rtx reg = expr->reaching_reg;
    4146              : 
    4147              :           /* If we've already copied it, continue.  */
    4148        35700 :           if (expr->reaching_reg == src)
    4149        27203 :             continue;
    4150              : 
    4151         8497 :           if (dump_file)
    4152              :             {
    4153            0 :               fprintf (dump_file, "PRE:  store updated with reaching reg ");
    4154            0 :               print_rtl (dump_file, reg);
    4155            0 :               fprintf (dump_file, ":\n     ");
    4156            0 :               print_inline_rtx (dump_file, insn, 8);
    4157            0 :               fprintf (dump_file, "\n");
    4158              :             }
    4159              : 
    4160         8497 :           rtx_insn *copy = gen_move_insn (reg, copy_rtx (SET_SRC (pat)));
    4161         8497 :           emit_insn_before (copy, insn);
    4162         8497 :           SET_SRC (pat) = reg;
    4163         8497 :           df_insn_rescan (insn);
    4164              : 
    4165              :           /* un-recognize this pattern since it's probably different now.  */
    4166         8497 :           INSN_CODE (insn) = -1;
    4167         8497 :           gcse_create_count++;
    4168              :         }
    4169              :     }
    4170       532131 : }
    4171              : 
    4172              : /* Return true if the graph is too expensive to optimize. PASS is the
    4173              :    optimization about to be performed.  */
    4174              : 
    4175              : bool
    4176      2154743 : gcse_or_cprop_is_too_expensive (const char *pass)
    4177              : {
    4178      2154743 :   unsigned HOST_WIDE_INT memory_request
    4179      2154743 :     = ((unsigned HOST_WIDE_INT)n_basic_blocks_for_fn (cfun)
    4180      2154743 :        * SBITMAP_SET_SIZE (max_reg_num ()) * sizeof (SBITMAP_ELT_TYPE));
    4181              : 
    4182              :   /* Trying to perform global optimizations on flow graphs which have
    4183              :      a high connectivity will take a long time and is unlikely to be
    4184              :      particularly useful.
    4185              : 
    4186              :      In normal circumstances a cfg should have about twice as many
    4187              :      edges as blocks.  But we do not want to punish small functions
    4188              :      which have a couple switch statements.  Rather than simply
    4189              :      threshold the number of blocks, uses something with a more
    4190              :      graceful degradation.  */
    4191      2154743 :   if (n_edges_for_fn (cfun) > 20000 + n_basic_blocks_for_fn (cfun) * 4)
    4192              :     {
    4193            0 :       warning (OPT_Wdisabled_optimization,
    4194              :                "%s: %d basic blocks and %d edges/basic block",
    4195              :                pass, n_basic_blocks_for_fn (cfun),
    4196              :                n_edges_for_fn (cfun) / n_basic_blocks_for_fn (cfun));
    4197              : 
    4198            0 :       return true;
    4199              :     }
    4200              : 
    4201              :   /* If allocating memory for the dataflow bitmaps would take up too much
    4202              :      storage it's better just to disable the optimization.  */
    4203      2154743 :   if (memory_request / 1024 > (unsigned HOST_WIDE_INT)param_max_gcse_memory)
    4204              :     {
    4205            0 :       warning (OPT_Wdisabled_optimization,
    4206              :                "%s: %d basic blocks and %d registers; "
    4207              :                "increase %<--param max-gcse-memory%> above %wu",
    4208            0 :                pass, n_basic_blocks_for_fn (cfun), max_reg_num (),
    4209              :                memory_request / 1024);
    4210              : 
    4211            0 :       return true;
    4212              :     }
    4213              : 
    4214              :   return false;
    4215              : }
    4216              : 
    4217              : static unsigned int
    4218       915747 : execute_rtl_pre (void)
    4219              : {
    4220       915747 :   int changed;
    4221       915747 :   delete_unreachable_blocks ();
    4222       915747 :   df_analyze ();
    4223       915747 :   changed = one_pre_gcse_pass ();
    4224       915747 :   flag_rerun_cse_after_global_opts |= changed;
    4225       915747 :   if (changed)
    4226       115772 :     cleanup_cfg (0);
    4227       915747 :   return 0;
    4228              : }
    4229              : 
    4230              : static unsigned int
    4231            0 : execute_hardreg_pre (void)
    4232              : {
    4233              : #ifdef HARDREG_PRE_REGNOS
    4234              :   doing_hardreg_pre_p = true;
    4235              :   unsigned int regnos[] = HARDREG_PRE_REGNOS;
    4236              :   /* It's possible to avoid this loop, but it isn't worth doing so until
    4237              :      hardreg PRE is used for multiple hardregs.  */
    4238              :   for (int i = 0; regnos[i] != 0; i++)
    4239              :     {
    4240              :       int changed;
    4241              :       current_hardreg_regno = regnos[i];
    4242              :       if (!df_regs_ever_live_p (current_hardreg_regno))
    4243              :         {
    4244              :           if (dump_file)
    4245              :             fprintf (dump_file, "Skipping hardreg PRE for regno %d, which is never live\n",
    4246              :                      current_hardreg_regno);
    4247              :           continue;
    4248              :         }
    4249              :       if (dump_file)
    4250              :         fprintf (dump_file, "Entering hardreg PRE for regno %d\n",
    4251              :                 current_hardreg_regno);
    4252              :       delete_unreachable_blocks ();
    4253              :       df_analyze ();
    4254              :       changed = one_pre_gcse_pass ();
    4255              :       if (changed)
    4256              :         cleanup_cfg (0);
    4257              :     }
    4258              :   doing_hardreg_pre_p = false;
    4259              : #endif
    4260            0 :   return 0;
    4261              : }
    4262              : 
    4263              : static unsigned int
    4264        66184 : execute_rtl_hoist (void)
    4265              : {
    4266        66184 :   int changed;
    4267        66184 :   delete_unreachable_blocks ();
    4268        66184 :   df_analyze ();
    4269        66184 :   changed = one_code_hoisting_pass ();
    4270        66184 :   flag_rerun_cse_after_global_opts |= changed;
    4271        66184 :   if (changed)
    4272         3187 :     cleanup_cfg (0);
    4273        66184 :   return 0;
    4274              : }
    4275              : 
    4276              : namespace {
    4277              : 
    4278              : const pass_data pass_data_rtl_pre =
    4279              : {
    4280              :   RTL_PASS, /* type */
    4281              :   "rtl pre", /* name */
    4282              :   OPTGROUP_NONE, /* optinfo_flags */
    4283              :   TV_PRE, /* tv_id */
    4284              :   PROP_cfglayout, /* properties_required */
    4285              :   0, /* properties_provided */
    4286              :   0, /* properties_destroyed */
    4287              :   0, /* todo_flags_start */
    4288              :   TODO_df_finish, /* todo_flags_finish */
    4289              : };
    4290              : 
    4291              : class pass_rtl_pre : public rtl_opt_pass
    4292              : {
    4293              : public:
    4294       297180 :   pass_rtl_pre (gcc::context *ctxt)
    4295       594360 :     : rtl_opt_pass (pass_data_rtl_pre, ctxt)
    4296              :   {}
    4297              : 
    4298              :   /* opt_pass methods: */
    4299              :   bool gate (function *) final override;
    4300       915747 :   unsigned int execute (function *)  final override
    4301              :   {
    4302       915747 :     return execute_rtl_pre ();
    4303              :   }
    4304              : 
    4305              : }; // class pass_rtl_pre
    4306              : 
    4307              : /* We do not construct an accurate cfg in functions which call
    4308              :    setjmp, so none of these passes runs if the function calls
    4309              :    setjmp.
    4310              :    FIXME: Should just handle setjmp via REG_SETJMP notes.  */
    4311              : 
    4312              : bool
    4313      1517135 : pass_rtl_pre::gate (function *fun)
    4314              : {
    4315      1064964 :   return optimize > 0 && flag_gcse
    4316       982673 :     && !fun->calls_setjmp
    4317       981932 :     && optimize_function_for_speed_p (fun)
    4318      2432883 :     && dbg_cnt (pre);
    4319              : }
    4320              : 
    4321              : } // anon namespace
    4322              : 
    4323              : rtl_opt_pass *
    4324       297180 : make_pass_rtl_pre (gcc::context *ctxt)
    4325              : {
    4326       297180 :   return new pass_rtl_pre (ctxt);
    4327              : }
    4328              : 
    4329              : namespace {
    4330              : 
    4331              : const pass_data pass_data_hardreg_pre =
    4332              : {
    4333              :   RTL_PASS, /* type */
    4334              :   "hardreg_pre", /* name */
    4335              :   OPTGROUP_NONE, /* optinfo_flags */
    4336              :   TV_PRE, /* tv_id */
    4337              :   PROP_cfglayout, /* properties_required */
    4338              :   0, /* properties_provided */
    4339              :   0, /* properties_destroyed */
    4340              :   0, /* todo_flags_start */
    4341              :   TODO_df_finish, /* todo_flags_finish */
    4342              : };
    4343              : 
    4344              : class pass_hardreg_pre : public rtl_opt_pass
    4345              : {
    4346              : public:
    4347       297180 :   pass_hardreg_pre (gcc::context *ctxt)
    4348       594360 :     : rtl_opt_pass (pass_data_hardreg_pre, ctxt)
    4349              :   {}
    4350              : 
    4351              :   /* opt_pass methods: */
    4352              :   bool gate (function *) final override;
    4353            0 :   unsigned int execute (function *)  final override
    4354              :   {
    4355            0 :     return execute_hardreg_pre ();
    4356              :   }
    4357              : 
    4358              : }; // class pass_rtl_pre
    4359              : 
    4360              : bool
    4361      1517135 : pass_hardreg_pre::gate (function * ARG_UNUSED (fun))
    4362              : {
    4363              : #ifdef HARDREG_PRE_REGNOS
    4364              :   return optimize > 0
    4365              :     && !fun->calls_setjmp;
    4366              : #else
    4367      1517135 :   return false;
    4368              : #endif
    4369              : }
    4370              : 
    4371              : } // anon namespace
    4372              : 
    4373              : rtl_opt_pass *
    4374       297180 : make_pass_hardreg_pre (gcc::context *ctxt)
    4375              : {
    4376       297180 :   return new pass_hardreg_pre (ctxt);
    4377              : }
    4378              : 
    4379              : namespace {
    4380              : 
    4381              : const pass_data pass_data_rtl_hoist =
    4382              : {
    4383              :   RTL_PASS, /* type */
    4384              :   "hoist", /* name */
    4385              :   OPTGROUP_NONE, /* optinfo_flags */
    4386              :   TV_HOIST, /* tv_id */
    4387              :   PROP_cfglayout, /* properties_required */
    4388              :   0, /* properties_provided */
    4389              :   0, /* properties_destroyed */
    4390              :   0, /* todo_flags_start */
    4391              :   TODO_df_finish, /* todo_flags_finish */
    4392              : };
    4393              : 
    4394              : class pass_rtl_hoist : public rtl_opt_pass
    4395              : {
    4396              : public:
    4397       297180 :   pass_rtl_hoist (gcc::context *ctxt)
    4398       594360 :     : rtl_opt_pass (pass_data_rtl_hoist, ctxt)
    4399              :   {}
    4400              : 
    4401              :   /* opt_pass methods: */
    4402              :   bool gate (function *) final override;
    4403        66184 :   unsigned int execute (function *) final override
    4404              :   {
    4405        66184 :     return execute_rtl_hoist ();
    4406              :   }
    4407              : 
    4408              : }; // class pass_rtl_hoist
    4409              : 
    4410              : bool
    4411      1517135 : pass_rtl_hoist::gate (function *)
    4412              : {
    4413      1064964 :   return optimize > 0 && flag_gcse
    4414       982673 :     && !cfun->calls_setjmp
    4415              :     /* It does not make sense to run code hoisting unless we are optimizing
    4416              :        for code size -- it rarely makes programs faster, and can make then
    4417              :        bigger if we did PRE (when optimizing for space, we don't run PRE).  */
    4418       981932 :     && optimize_function_for_size_p (cfun)
    4419      1583319 :     && dbg_cnt (hoist);
    4420              : }
    4421              : 
    4422              : } // anon namespace
    4423              : 
    4424              : rtl_opt_pass *
    4425       297180 : make_pass_rtl_hoist (gcc::context *ctxt)
    4426              : {
    4427       297180 :   return new pass_rtl_hoist (ctxt);
    4428              : }
    4429              : 
    4430              : /* Reset all state within gcse.cc so that we can rerun the compiler
    4431              :    within the same process.  For use by toplev::finalize.  */
    4432              : 
    4433              : void
    4434       266934 : gcse_cc_finalize (void)
    4435              : {
    4436       266934 :   test_insn = NULL;
    4437       266934 : }
    4438              : 
    4439              : #include "gt-gcse.h"
        

Generated by: LCOV version 2.5.0-beta

LCOV profile is generated on x86_64 machine using following configure options: configure --disable-bootstrap --enable-coverage=opt --enable-languages=c,c++,fortran,go,jit,lto,rust,m2 --enable-host-shared. GCC test suite is run with the built compiler.