LCOV - code coverage report
Current view: top level - gcc - early-remat.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 6 1002 0.6 %
Date: 2020-04-04 11:58:09 Functions: 2 57 3.5 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Early (pre-RA) rematerialization
       2                 :            :    Copyright (C) 2017-2020 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                 :            : #include "config.h"
      21                 :            : #include "system.h"
      22                 :            : #include "coretypes.h"
      23                 :            : #include "backend.h"
      24                 :            : #include "rtl.h"
      25                 :            : #include "df.h"
      26                 :            : #include "tree-pass.h"
      27                 :            : #include "memmodel.h"
      28                 :            : #include "emit-rtl.h"
      29                 :            : #include "insn-config.h"
      30                 :            : #include "recog.h"
      31                 :            : /* FIXME: The next two are only needed for gen_move_insn.  */
      32                 :            : #include "tree.h"
      33                 :            : #include "expr.h"
      34                 :            : #include "target.h"
      35                 :            : #include "inchash.h"
      36                 :            : #include "rtlhash.h"
      37                 :            : #include "print-rtl.h"
      38                 :            : #include "rtl-iter.h"
      39                 :            : #include "regs.h"
      40                 :            : #include "function-abi.h"
      41                 :            : 
      42                 :            : /* This pass runs before register allocation and implements an aggressive
      43                 :            :    form of rematerialization.  It looks for pseudo registers R of mode M
      44                 :            :    for which:
      45                 :            : 
      46                 :            :      (a) there are no call-preserved registers of mode M; and
      47                 :            :      (b) spilling R to the stack is expensive.
      48                 :            : 
      49                 :            :    The assumption is that it's better to recompute R after each call instead
      50                 :            :    of spilling it, even if this extends the live ranges of other registers.
      51                 :            : 
      52                 :            :    The motivating example for which these conditions hold are AArch64 SVE
      53                 :            :    vectors and predicates.  Spilling them to the stack makes the frame
      54                 :            :    variable-sized, which we'd like to avoid if possible.  It's also very
      55                 :            :    rare for SVE values to be "naturally" live across a call: usually this
      56                 :            :    happens as a result of CSE or other code motion.
      57                 :            : 
      58                 :            :    The pass is split into the following phases:
      59                 :            : 
      60                 :            :    Collection phase
      61                 :            :    ================
      62                 :            : 
      63                 :            :    First we go through all pseudo registers looking for any that meet
      64                 :            :    the conditions above.  For each such register R, we go through each
      65                 :            :    instruction that defines R to see whether any of them are suitable
      66                 :            :    rematerialization candidates.  If at least one is, we treat all the
      67                 :            :    instructions that define R as candidates, but record which ones are
      68                 :            :    not in fact suitable.  These unsuitable candidates exist only for the
      69                 :            :    sake of calculating reaching definitions (see below).
      70                 :            : 
      71                 :            :    A "candidate" is a single instruction that we want to rematerialize
      72                 :            :    and a "candidate register" is a register that is set by at least one
      73                 :            :    candidate.
      74                 :            : 
      75                 :            :    Candidate sorting
      76                 :            :    =================
      77                 :            : 
      78                 :            :    Next we sort the candidates based on the cfg postorder, so that if
      79                 :            :    candidate C1 uses candidate C2, C1 has a lower index than C2.
      80                 :            :    This is useful when iterating through candidate bitmaps.
      81                 :            : 
      82                 :            :    Reaching definition calculation
      83                 :            :    ===============================
      84                 :            : 
      85                 :            :    We then compute standard reaching-definition sets for each candidate.
      86                 :            :    Each set specifies which candidates might provide the current definition
      87                 :            :    of a live candidate register.
      88                 :            : 
      89                 :            :    From here on, a candidate C is "live" at a point P if the candidate
      90                 :            :    register defined by C is live at P and if C's definition reaches P.
      91                 :            :    An instruction I "uses" a candidate C if I takes the register defined by
      92                 :            :    C as input and if C is one of the reaching definitions of that register.
      93                 :            : 
      94                 :            :    Candidate validation and value numbering
      95                 :            :    ========================================
      96                 :            : 
      97                 :            :    Next we simultaneously decide which candidates are valid and look
      98                 :            :    for candidates that are equivalent to each other, assigning numbers
      99                 :            :    to each unique candidate value.  A candidate C is invalid if:
     100                 :            : 
     101                 :            :      (a) C uses an invalid candidate;
     102                 :            : 
     103                 :            :      (b) there is a cycle of candidate uses involving C; or
     104                 :            : 
     105                 :            :      (c) C takes a candidate register R as input and the reaching
     106                 :            :          definitions of R do not have the same value number.
     107                 :            : 
     108                 :            :    We assign a "representative" candidate C to each value number and from
     109                 :            :    here on replace references to other candidates with that value number
     110                 :            :    with references to C.  It is then only possible to rematerialize a
     111                 :            :    register R at point P if (after this replacement) there is a single
     112                 :            :    reaching definition of R at P.
     113                 :            : 
     114                 :            :    Local phase
     115                 :            :    ===========
     116                 :            : 
     117                 :            :    During this phase we go through each block and look for cases in which:
     118                 :            : 
     119                 :            :      (a) an instruction I comes between two call instructions CI1 and CI2;
     120                 :            : 
     121                 :            :      (b) I uses a candidate register R;
     122                 :            : 
     123                 :            :      (c) a candidate C provides the only reaching definition of R; and
     124                 :            : 
     125                 :            :      (d) C does not come between CI1 and I.
     126                 :            : 
     127                 :            :    We then emit a copy of C after CI1, as well as the transitive closure
     128                 :            :    TC of the candidates used by C.  The copies of TC might use the original
     129                 :            :    candidate registers or new temporary registers, depending on circumstances.
     130                 :            : 
     131                 :            :    For example, if elsewhere we have:
     132                 :            : 
     133                 :            :        C3: R3 <- f3 (...)
     134                 :            :            ...
     135                 :            :        C2: R2 <- f2 (...)
     136                 :            :            ...
     137                 :            :        C1: R1 <- f1 (R2, R3, ...)  // uses C2 and C3
     138                 :            : 
     139                 :            :    then for a block containing:
     140                 :            : 
     141                 :            :       CI1: call
     142                 :            :            ...
     143                 :            :         I: use R1  // uses C1
     144                 :            :            ...
     145                 :            :       CI2: call
     146                 :            : 
     147                 :            :    we would emit:
     148                 :            : 
     149                 :            :       CI1: call
     150                 :            :       C3': R3' <- f3 (...)
     151                 :            :       C2': R2' <- f2 (...)
     152                 :            :       C1': R1 <- f1 (R2', R3', ...)
     153                 :            :            ...
     154                 :            :         I: use R1
     155                 :            :            ...
     156                 :            :       CI2: call
     157                 :            : 
     158                 :            :    where R2' and R3' might be fresh registers.  If instead we had:
     159                 :            : 
     160                 :            :       CI1: call
     161                 :            :            ...
     162                 :            :        I1: use R1  // uses C1
     163                 :            :            ...
     164                 :            :        I2: use R3  // uses C3
     165                 :            :            ...
     166                 :            :       CI2: call
     167                 :            : 
     168                 :            :    we would keep the original R3:
     169                 :            : 
     170                 :            :       CI1: call
     171                 :            :       C3': R3 <- f3 (...)
     172                 :            :       C2': R2' <- f2 (...)
     173                 :            :       C1': R1 <- f1 (R2', R3, ...)
     174                 :            :            ...
     175                 :            :        I1: use R1  // uses C1
     176                 :            :            ...
     177                 :            :        I2: use R3  // uses C3
     178                 :            :            ...
     179                 :            :       CI2: call
     180                 :            : 
     181                 :            :    We also record the last call in each block (if any) and compute:
     182                 :            : 
     183                 :            :      rd_after_call:
     184                 :            :        The set of candidates that either (a) are defined outside the block
     185                 :            :        and are live after the last call or (b) are defined within the block
     186                 :            :        and reach the end of the last call.  (We don't track whether the
     187                 :            :        latter values are live or not.)
     188                 :            : 
     189                 :            :      required_after_call:
     190                 :            :        The set of candidates that need to be rematerialized after the
     191                 :            :        last call in order to satisfy uses in the block itself.
     192                 :            : 
     193                 :            :      required_in:
     194                 :            :        The set of candidates that are live on entry to the block and are
     195                 :            :        used without an intervening call.
     196                 :            : 
     197                 :            :    In addition, we compute the initial values of the sets required by
     198                 :            :    the global phase below.
     199                 :            : 
     200                 :            :    Global phase
     201                 :            :    ============
     202                 :            : 
     203                 :            :    We next compute a maximal solution to the following availability
     204                 :            :    problem:
     205                 :            : 
     206                 :            :      available_in:
     207                 :            :        The set of candidates that are live on entry to a block and can
     208                 :            :        be used at that point without rematerialization.
     209                 :            : 
     210                 :            :      available_out:
     211                 :            :        The set of candidates that are live on exit from a block and can
     212                 :            :        be used at that point without rematerialization.
     213                 :            : 
     214                 :            :      available_locally:
     215                 :            :        The subset of available_out that is due to code in the block itself.
     216                 :            :        It contains candidates that are defined or used in the block and
     217                 :            :        not invalidated by a later call.
     218                 :            : 
     219                 :            :    We then go through each block B and look for an appropriate place
     220                 :            :    to insert copies of required_in - available_in.  Conceptually we
     221                 :            :    start by placing the copies at the head of B, but then move the
     222                 :            :    copy of a candidate C to predecessors if:
     223                 :            : 
     224                 :            :      (a) that seems cheaper;
     225                 :            : 
     226                 :            :      (b) there is more than one reaching definition of C's register at
     227                 :            :          the head of B; or
     228                 :            : 
     229                 :            :      (c) copying C would clobber a hard register that is live on entry to B.
     230                 :            : 
     231                 :            :    Moving a copy of C to a predecessor block PB involves:
     232                 :            : 
     233                 :            :      (1) adding C to PB's required_after_call, if PB contains a call; or
     234                 :            : 
     235                 :            :      (2) adding C PB's required_in otherwise.
     236                 :            : 
     237                 :            :    C is then available on output from each PB and on input to B.
     238                 :            : 
     239                 :            :    Once all this is done, we emit instructions for the final required_in
     240                 :            :    and required_after_call sets.  */
     241                 :            : 
     242                 :            : namespace {
     243                 :            : 
     244                 :            : /* An invalid candidate index, used to indicate that there is more than
     245                 :            :    one reaching definition.  */
     246                 :            : const unsigned int MULTIPLE_CANDIDATES = -1U;
     247                 :            : 
     248                 :            : /* Pass-specific information about one basic block.  */
     249                 :            : struct remat_block_info {
     250                 :            :   /* The last call instruction in the block.  */
     251                 :            :   rtx_insn *last_call;
     252                 :            : 
     253                 :            :   /* The set of candidates that are live on entry to the block.  NULL is
     254                 :            :      equivalent to an empty set.  */
     255                 :            :   bitmap rd_in;
     256                 :            : 
     257                 :            :   /* The set of candidates that are live on exit from the block.  This might
     258                 :            :      reuse rd_in.  NULL is equivalent to an empty set.  */
     259                 :            :   bitmap rd_out;
     260                 :            : 
     261                 :            :   /* The subset of RD_OUT that comes from local definitions.  NULL is
     262                 :            :      equivalent to an empty set.  */
     263                 :            :   bitmap rd_gen;
     264                 :            : 
     265                 :            :   /* The set of candidates that the block invalidates (because it defines
     266                 :            :      the register to something else, or because the register's value is
     267                 :            :      no longer important).  NULL is equivalent to an empty set.  */
     268                 :            :   bitmap rd_kill;
     269                 :            : 
     270                 :            :   /* The set of candidates that either (a) are defined outside the block
     271                 :            :      and are live after LAST_CALL or (b) are defined within the block
     272                 :            :      and reach the instruction after LAST_CALL.  (We don't track whether
     273                 :            :      the latter values are live or not.)
     274                 :            : 
     275                 :            :      Only used if LAST_CALL is nonnull.  NULL is equivalent to an
     276                 :            :      empty set.  */
     277                 :            :   bitmap rd_after_call;
     278                 :            : 
     279                 :            :   /* Candidates that are live and available without rematerialization
     280                 :            :      on entry to the block.  NULL is equivalent to an empty set.  */
     281                 :            :   bitmap available_in;
     282                 :            : 
     283                 :            :   /* Candidates that become available without rematerialization within the
     284                 :            :      block, and remain so on exit.  NULL is equivalent to an empty set.  */
     285                 :            :   bitmap available_locally;
     286                 :            : 
     287                 :            :   /* Candidates that are available without rematerialization on exit from
     288                 :            :      the block.  This might reuse available_in or available_locally.  */
     289                 :            :   bitmap available_out;
     290                 :            : 
     291                 :            :   /* Candidates that need to be rematerialized either at the start of the
     292                 :            :      block or before entering the block.  */
     293                 :            :   bitmap required_in;
     294                 :            : 
     295                 :            :   /* Candidates that need to be rematerialized after LAST_CALL.
     296                 :            :      Only used if LAST_CALL is nonnull.  */
     297                 :            :   bitmap required_after_call;
     298                 :            : 
     299                 :            :   /* The number of candidates in the block.  */
     300                 :            :   unsigned int num_candidates;
     301                 :            : 
     302                 :            :   /* The earliest candidate in the block (i.e. the one with the
     303                 :            :      highest index).  Only valid if NUM_CANDIDATES is nonzero.  */
     304                 :            :   unsigned int first_candidate;
     305                 :            : 
     306                 :            :   /* The best (lowest) execution frequency for rematerializing REQUIRED_IN.
     307                 :            :      This is the execution frequency of the block if LOCAL_REMAT_CHEAPER_P,
     308                 :            :      otherwise it is the sum of the execution frequencies of whichever
     309                 :            :      predecessor blocks would do the rematerialization.  */
     310                 :            :   int remat_frequency;
     311                 :            : 
     312                 :            :   /* True if the block ends with an abnormal call.  */
     313                 :            :   unsigned int abnormal_call_p : 1;
     314                 :            : 
     315                 :            :   /* Used to record whether a graph traversal has visited this block.  */
     316                 :            :   unsigned int visited_p : 1;
     317                 :            : 
     318                 :            :   /* True if we have calculated REMAT_FREQUENCY.  */
     319                 :            :   unsigned int remat_frequency_valid_p : 1;
     320                 :            : 
     321                 :            :   /* True if it is cheaper to rematerialize candidates at the start of
     322                 :            :      the block, rather than moving them to predecessor blocks.  */
     323                 :            :   unsigned int local_remat_cheaper_p : 1;
     324                 :            : };
     325                 :            : 
     326                 :            : /* Information about a group of candidates with the same value number.  */
     327                 :            : struct remat_equiv_class {
     328                 :            :   /* The candidates that have the same value number.  */
     329                 :            :   bitmap members;
     330                 :            : 
     331                 :            :   /* The candidate that was first added to MEMBERS.  */
     332                 :            :   unsigned int earliest;
     333                 :            : 
     334                 :            :   /* The candidate that represents the others.  This is always the one
     335                 :            :      with the highest index.  */
     336                 :            :   unsigned int representative;
     337                 :            : };
     338                 :            : 
     339                 :            : /* Information about an instruction that we might want to rematerialize.  */
     340                 :            : struct remat_candidate {
     341                 :            :   /* The pseudo register that the instruction sets.  */
     342                 :            :   unsigned int regno;
     343                 :            : 
     344                 :            :   /* A temporary register used when rematerializing uses of this candidate,
     345                 :            :      if REGNO doesn't have the right value or isn't worth using.  */
     346                 :            :   unsigned int copy_regno;
     347                 :            : 
     348                 :            :   /* True if we intend to rematerialize this instruction by emitting
     349                 :            :      a move of a constant into REGNO, false if we intend to emit a
     350                 :            :      copy of the original instruction.  */
     351                 :            :   unsigned int constant_p : 1;
     352                 :            : 
     353                 :            :   /* True if we still think it's possible to rematerialize INSN.  */
     354                 :            :   unsigned int can_copy_p : 1;
     355                 :            : 
     356                 :            :   /* Used to record whether a graph traversal has visited this candidate.  */
     357                 :            :   unsigned int visited_p : 1;
     358                 :            : 
     359                 :            :   /* True if we have verified that it's possible to rematerialize INSN.
     360                 :            :      Once this is true, both it and CAN_COPY_P remain true.  */
     361                 :            :   unsigned int validated_p : 1;
     362                 :            : 
     363                 :            :   /* True if we have "stabilized" INSN, i.e. ensured that all non-candidate
     364                 :            :      registers read by INSN will have the same value when rematerializing INSN.
     365                 :            :      Only ever true if CAN_COPY_P.  */
     366                 :            :   unsigned int stabilized_p : 1;
     367                 :            : 
     368                 :            :   /* Hash value used for value numbering.  */
     369                 :            :   hashval_t hash;
     370                 :            : 
     371                 :            :   /* The instruction that sets REGNO.  */
     372                 :            :   rtx_insn *insn;
     373                 :            : 
     374                 :            :   /* If CONSTANT_P, the value that should be moved into REGNO when
     375                 :            :      rematerializing, otherwise the pattern of the instruction that
     376                 :            :      should be used.  */
     377                 :            :   rtx remat_rtx;
     378                 :            : 
     379                 :            :   /* The set of candidates that INSN takes as input.  NULL is equivalent
     380                 :            :      to the empty set.  All candidates in this set have a higher index
     381                 :            :      than the current candidate.  */
     382                 :            :   bitmap uses;
     383                 :            : 
     384                 :            :   /* The set of hard registers that would be clobbered by rematerializing
     385                 :            :      the candidate, including (transitively) all those that would be
     386                 :            :      clobbered by rematerializing USES.  */
     387                 :            :   bitmap clobbers;
     388                 :            : 
     389                 :            :   /* The equivalence class to which the candidate belongs, or null if none.  */
     390                 :            :   remat_equiv_class *equiv_class;
     391                 :            : };
     392                 :            : 
     393                 :            : /* Hash functions used for value numbering.  */
     394                 :            : struct remat_candidate_hasher : nofree_ptr_hash <remat_candidate>
     395                 :            : {
     396                 :            :   typedef value_type compare_type;
     397                 :            :   static hashval_t hash (const remat_candidate *);
     398                 :            :   static bool equal (const remat_candidate *, const remat_candidate *);
     399                 :            : };
     400                 :            : 
     401                 :            : /* Main class for this pass.  */
     402                 :            : class early_remat {
     403                 :            : public:
     404                 :            :   early_remat (function *, sbitmap);
     405                 :            :   ~early_remat ();
     406                 :            : 
     407                 :            :   void run (void);
     408                 :            : 
     409                 :            : private:
     410                 :            :   bitmap alloc_bitmap (void);
     411                 :            :   bitmap get_bitmap (bitmap *);
     412                 :            :   void init_temp_bitmap (bitmap *);
     413                 :            :   void copy_temp_bitmap (bitmap *, bitmap *);
     414                 :            : 
     415                 :            :   void dump_insn_id (rtx_insn *);
     416                 :            :   void dump_candidate_bitmap (bitmap);
     417                 :            :   void dump_all_candidates (void);
     418                 :            :   void dump_edge_list (basic_block, bool);
     419                 :            :   void dump_block_info (basic_block);
     420                 :            :   void dump_all_blocks (void);
     421                 :            : 
     422                 :            :   bool interesting_regno_p (unsigned int);
     423                 :            :   remat_candidate *add_candidate (rtx_insn *, unsigned int, bool);
     424                 :            :   bool maybe_add_candidate (rtx_insn *, unsigned int);
     425                 :            :   bool collect_candidates (void);
     426                 :            :   void init_block_info (void);
     427                 :            :   void sort_candidates (void);
     428                 :            :   void finalize_candidate_indices (void);
     429                 :            :   void record_equiv_candidates (unsigned int, unsigned int);
     430                 :            :   static bool rd_confluence_n (edge);
     431                 :            :   static bool rd_transfer (int);
     432                 :            :   void compute_rd (void);
     433                 :            :   unsigned int canon_candidate (unsigned int);
     434                 :            :   void canon_bitmap (bitmap *);
     435                 :            :   unsigned int resolve_reaching_def (bitmap);
     436                 :            :   bool check_candidate_uses (unsigned int);
     437                 :            :   void compute_clobbers (unsigned int);
     438                 :            :   void assign_value_number (unsigned int);
     439                 :            :   void decide_candidate_validity (void);
     440                 :            :   void restrict_remat_for_unavail_regs (bitmap, const_bitmap);
     441                 :            :   void restrict_remat_for_call (bitmap, rtx_insn *);
     442                 :            :   bool stable_use_p (unsigned int);
     443                 :            :   void emit_copy_before (unsigned int, rtx, rtx);
     444                 :            :   void stabilize_pattern (unsigned int);
     445                 :            :   void replace_dest_with_copy (unsigned int);
     446                 :            :   void stabilize_candidate_uses (unsigned int, bitmap, bitmap, bitmap,
     447                 :            :                                  bitmap);
     448                 :            :   void emit_remat_insns (bitmap, bitmap, bitmap, rtx_insn *);
     449                 :            :   bool set_available_out (remat_block_info *);
     450                 :            :   void process_block (basic_block);
     451                 :            :   void local_phase (void);
     452                 :            :   static bool avail_confluence_n (edge);
     453                 :            :   static bool avail_transfer (int);
     454                 :            :   void compute_availability (void);
     455                 :            :   void unshare_available_sets (remat_block_info *);
     456                 :            :   bool can_move_across_edge_p (edge);
     457                 :            :   bool local_remat_cheaper_p (unsigned int);
     458                 :            :   bool need_to_move_candidate_p (unsigned int, unsigned int);
     459                 :            :   void compute_minimum_move_set (unsigned int, bitmap);
     460                 :            :   void move_to_predecessors (unsigned int, bitmap, bitmap);
     461                 :            :   void choose_rematerialization_points (void);
     462                 :            :   void emit_remat_insns_for_block (basic_block);
     463                 :            :   void global_phase (void);
     464                 :            : 
     465                 :            :   /* The function that we're optimizing.  */
     466                 :            :   function *m_fn;
     467                 :            : 
     468                 :            :   /* The modes that we want to rematerialize.  */
     469                 :            :   sbitmap m_selected_modes;
     470                 :            : 
     471                 :            :   /* All rematerialization candidates, identified by their index into the
     472                 :            :      vector.  */
     473                 :            :   auto_vec<remat_candidate> m_candidates;
     474                 :            : 
     475                 :            :   /* The set of candidate registers.  */
     476                 :            :   bitmap_head m_candidate_regnos;
     477                 :            : 
     478                 :            :   /* Temporary sets.  */
     479                 :            :   bitmap_head m_tmp_bitmap;
     480                 :            :   bitmap m_available;
     481                 :            :   bitmap m_required;
     482                 :            : 
     483                 :            :   /* Information about each basic block.  */
     484                 :            :   auto_vec<remat_block_info> m_block_info;
     485                 :            : 
     486                 :            :   /* A mapping from register numbers to the set of associated candidates.
     487                 :            :      Only valid for registers in M_CANDIDATE_REGNOS.  */
     488                 :            :   auto_vec<bitmap> m_regno_to_candidates;
     489                 :            : 
     490                 :            :   /* An obstack used for allocating bitmaps, so that we can free them all
     491                 :            :      in one go.  */
     492                 :            :   bitmap_obstack m_obstack;
     493                 :            : 
     494                 :            :   /* A hash table of candidates used for value numbering.  If a candidate
     495                 :            :      in the table is in an equivalence class, the candidate is marked as
     496                 :            :      the earliest member of the class.  */
     497                 :            :   hash_table<remat_candidate_hasher> m_value_table;
     498                 :            : 
     499                 :            :   /* Used temporarily by callback functions.  */
     500                 :            :   static early_remat *er;
     501                 :            : };
     502                 :            : 
     503                 :            : }
     504                 :            : 
     505                 :            : early_remat *early_remat::er;
     506                 :            : 
     507                 :            : /* rtx_equal_p_cb callback that treats any two SCRATCHes as equal.
     508                 :            :    This allows us to compare two copies of a pattern, even though their
     509                 :            :    SCRATCHes are always distinct.  */
     510                 :            : 
     511                 :            : static int
     512                 :          0 : scratch_equal (const_rtx *x, const_rtx *y, rtx *nx, rtx *ny)
     513                 :            : {
     514                 :          0 :   if (GET_CODE (*x) == SCRATCH && GET_CODE (*y) == SCRATCH)
     515                 :            :     {
     516                 :          0 :       *nx = const0_rtx;
     517                 :          0 :       *ny = const0_rtx;
     518                 :          0 :       return 1;
     519                 :            :     }
     520                 :            :   return 0;
     521                 :            : }
     522                 :            : 
     523                 :            : /* Hash callback functions for remat_candidate.  */
     524                 :            : 
     525                 :            : hashval_t
     526                 :          0 : remat_candidate_hasher::hash (const remat_candidate *cand)
     527                 :            : {
     528                 :          0 :   return cand->hash;
     529                 :            : }
     530                 :            : 
     531                 :            : bool
     532                 :          0 : remat_candidate_hasher::equal (const remat_candidate *cand1,
     533                 :            :                                const remat_candidate *cand2)
     534                 :            : {
     535                 :          0 :   return (cand1->regno == cand2->regno
     536                 :          0 :           && cand1->constant_p == cand2->constant_p
     537                 :          0 :           && (cand1->constant_p
     538                 :          0 :               ? rtx_equal_p (cand1->remat_rtx, cand2->remat_rtx)
     539                 :          0 :               : rtx_equal_p_cb (cand1->remat_rtx, cand2->remat_rtx,
     540                 :          0 :                                 scratch_equal))
     541                 :          0 :           && (!cand1->uses || bitmap_equal_p (cand1->uses, cand2->uses)));
     542                 :            : }
     543                 :            : 
     544                 :            : /* Return true if B is null or empty.  */
     545                 :            : 
     546                 :            : inline bool
     547                 :          0 : empty_p (bitmap b)
     548                 :            : {
     549                 :          0 :   return !b || bitmap_empty_p (b);
     550                 :            : }
     551                 :            : 
     552                 :            : /* Allocate a new bitmap.  It will be automatically freed at the end of
     553                 :            :    the pass.  */
     554                 :            : 
     555                 :            : inline bitmap
     556                 :          0 : early_remat::alloc_bitmap (void)
     557                 :            : {
     558                 :          0 :   return bitmap_alloc (&m_obstack);
     559                 :            : }
     560                 :            : 
     561                 :            : /* Initialize *PTR to an empty bitmap if it is currently null.  */
     562                 :            : 
     563                 :            : inline bitmap
     564                 :          0 : early_remat::get_bitmap (bitmap *ptr)
     565                 :            : {
     566                 :          0 :   if (!*ptr)
     567                 :          0 :     *ptr = alloc_bitmap ();
     568                 :          0 :   return *ptr;
     569                 :            : }
     570                 :            : 
     571                 :            : /* *PTR is either null or empty.  If it is null, initialize it to an
     572                 :            :    empty bitmap.  */
     573                 :            : 
     574                 :            : inline void
     575                 :          0 : early_remat::init_temp_bitmap (bitmap *ptr)
     576                 :            : {
     577                 :          0 :   if (!*ptr)
     578                 :          0 :     *ptr = alloc_bitmap ();
     579                 :            :   else
     580                 :          0 :     gcc_checking_assert (bitmap_empty_p (*ptr));
     581                 :          0 : }
     582                 :            : 
     583                 :            : /* Move *SRC to *DEST and leave *SRC empty.  */
     584                 :            : 
     585                 :            : inline void
     586                 :          0 : early_remat::copy_temp_bitmap (bitmap *dest, bitmap *src)
     587                 :            : {
     588                 :          0 :   if (!empty_p (*src))
     589                 :            :     {
     590                 :          0 :       *dest = *src;
     591                 :          0 :       *src = NULL;
     592                 :            :     }
     593                 :            :   else
     594                 :          0 :     *dest = NULL;
     595                 :            : }
     596                 :            : 
     597                 :            : /* Print INSN's identifier to the dump file.  */
     598                 :            : 
     599                 :            : void
     600                 :          0 : early_remat::dump_insn_id (rtx_insn *insn)
     601                 :            : {
     602                 :          0 :   fprintf (dump_file, "%d[bb:%d]", INSN_UID (insn),
     603                 :          0 :            BLOCK_FOR_INSN (insn)->index);
     604                 :          0 : }
     605                 :            : 
     606                 :            : /* Print candidate set CANDIDATES to the dump file, with a leading space.  */
     607                 :            : 
     608                 :            : void
     609                 :          0 : early_remat::dump_candidate_bitmap (bitmap candidates)
     610                 :            : {
     611                 :          0 :   if (empty_p (candidates))
     612                 :            :     {
     613                 :          0 :       fprintf (dump_file, " none");
     614                 :          0 :       return;
     615                 :            :     }
     616                 :            : 
     617                 :          0 :   unsigned int cand_index;
     618                 :          0 :   bitmap_iterator bi;
     619                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (candidates, 0, cand_index, bi)
     620                 :          0 :     fprintf (dump_file, " %d", cand_index);
     621                 :            : }
     622                 :            : 
     623                 :            : /* Print information about all candidates to the dump file.  */
     624                 :            : 
     625                 :            : void
     626                 :          0 : early_remat::dump_all_candidates (void)
     627                 :            : {
     628                 :          0 :   fprintf (dump_file, "\n;; Candidates:\n;;\n");
     629                 :          0 :   fprintf (dump_file, ";; %5s %5s %8s %s\n", "#", "reg", "mode", "insn");
     630                 :          0 :   fprintf (dump_file, ";; %5s %5s %8s %s\n", "=", "===", "====", "====");
     631                 :          0 :   unsigned int cand_index;
     632                 :          0 :   remat_candidate *cand;
     633                 :          0 :   FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
     634                 :            :     {
     635                 :          0 :       fprintf (dump_file, ";; %5d %5d %8s ", cand_index, cand->regno,
     636                 :          0 :                GET_MODE_NAME (GET_MODE (regno_reg_rtx[cand->regno])));
     637                 :          0 :       dump_insn_id (cand->insn);
     638                 :          0 :       if (!cand->can_copy_p)
     639                 :          0 :         fprintf (dump_file, "   -- can't copy");
     640                 :          0 :       fprintf (dump_file, "\n");
     641                 :            :     }
     642                 :            : 
     643                 :          0 :   fprintf (dump_file, "\n;; Register-to-candidate mapping:\n;;\n");
     644                 :          0 :   unsigned int regno;
     645                 :          0 :   bitmap_iterator bi;
     646                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos, 0, regno, bi)
     647                 :            :     {
     648                 :          0 :       fprintf (dump_file, ";; %5d:", regno);
     649                 :          0 :       dump_candidate_bitmap (m_regno_to_candidates[regno]);
     650                 :          0 :       fprintf (dump_file, "\n");
     651                 :            :     }
     652                 :          0 : }
     653                 :            : 
     654                 :            : /* Print the predecessors or successors of BB to the dump file, with a
     655                 :            :    leading space.  DO_SUCC is true to print successors and false to print
     656                 :            :    predecessors.  */
     657                 :            : 
     658                 :            : void
     659                 :          0 : early_remat::dump_edge_list (basic_block bb, bool do_succ)
     660                 :            : {
     661                 :          0 :   edge e;
     662                 :          0 :   edge_iterator ei;
     663                 :          0 :   FOR_EACH_EDGE (e, ei, do_succ ? bb->succs : bb->preds)
     664                 :          0 :     dump_edge_info (dump_file, e, TDF_NONE, do_succ);
     665                 :          0 : }
     666                 :            : 
     667                 :            : /* Print information about basic block BB to the dump file.  */
     668                 :            : 
     669                 :            : void
     670                 :          0 : early_remat::dump_block_info (basic_block bb)
     671                 :            : {
     672                 :          0 :   remat_block_info *info = &m_block_info[bb->index];
     673                 :          0 :   fprintf (dump_file, ";;\n;; Block %d:", bb->index);
     674                 :          0 :   int width = 25;
     675                 :            : 
     676                 :          0 :   fprintf (dump_file, "\n;;%*s:", width, "predecessors");
     677                 :          0 :   dump_edge_list (bb, false);
     678                 :            : 
     679                 :          0 :   fprintf (dump_file, "\n;;%*s:", width, "successors");
     680                 :          0 :   dump_edge_list (bb, true);
     681                 :            : 
     682                 :          0 :   fprintf (dump_file, "\n;;%*s: %d", width, "frequency",
     683                 :            :            bb->count.to_frequency (m_fn));
     684                 :            : 
     685                 :          0 :   if (info->last_call)
     686                 :          0 :     fprintf (dump_file, "\n;;%*s: %d", width, "last call",
     687                 :          0 :              INSN_UID (info->last_call));
     688                 :            : 
     689                 :          0 :   if (!empty_p (info->rd_in))
     690                 :            :     {
     691                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "RD in");
     692                 :          0 :       dump_candidate_bitmap (info->rd_in);
     693                 :            :     }
     694                 :          0 :   if (!empty_p (info->rd_kill))
     695                 :            :     {
     696                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "RD kill");
     697                 :          0 :       dump_candidate_bitmap (info->rd_kill);
     698                 :            :     }
     699                 :          0 :   if (!empty_p (info->rd_gen))
     700                 :            :     {
     701                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "RD gen");
     702                 :          0 :       dump_candidate_bitmap (info->rd_gen);
     703                 :            :     }
     704                 :          0 :   if (!empty_p (info->rd_after_call))
     705                 :            :     {
     706                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "RD after call");
     707                 :          0 :       dump_candidate_bitmap (info->rd_after_call);
     708                 :            :     }
     709                 :          0 :   if (!empty_p (info->rd_out))
     710                 :            :     {
     711                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "RD out");
     712                 :          0 :       if (info->rd_in == info->rd_out)
     713                 :          0 :         fprintf (dump_file, " RD in");
     714                 :            :       else
     715                 :          0 :         dump_candidate_bitmap (info->rd_out);
     716                 :            :     }
     717                 :          0 :   if (!empty_p (info->available_in))
     718                 :            :     {
     719                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "available in");
     720                 :          0 :       dump_candidate_bitmap (info->available_in);
     721                 :            :     }
     722                 :          0 :   if (!empty_p (info->available_locally))
     723                 :            :     {
     724                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "available locally");
     725                 :          0 :       dump_candidate_bitmap (info->available_locally);
     726                 :            :     }
     727                 :          0 :   if (!empty_p (info->available_out))
     728                 :            :     {
     729                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "available out");
     730                 :          0 :       if (info->available_in == info->available_out)
     731                 :          0 :         fprintf (dump_file, " available in");
     732                 :          0 :       else if (info->available_locally == info->available_out)
     733                 :          0 :         fprintf (dump_file, " available locally");
     734                 :            :       else
     735                 :          0 :         dump_candidate_bitmap (info->available_out);
     736                 :            :     }
     737                 :          0 :   if (!empty_p (info->required_in))
     738                 :            :     {
     739                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "required in");
     740                 :          0 :       dump_candidate_bitmap (info->required_in);
     741                 :            :     }
     742                 :          0 :   if (!empty_p (info->required_after_call))
     743                 :            :     {
     744                 :          0 :       fprintf (dump_file, "\n;;%*s:", width, "required after call");
     745                 :          0 :       dump_candidate_bitmap (info->required_after_call);
     746                 :            :     }
     747                 :          0 :   fprintf (dump_file, "\n");
     748                 :          0 : }
     749                 :            : 
     750                 :            : /* Print information about all basic blocks to the dump file.  */
     751                 :            : 
     752                 :            : void
     753                 :          0 : early_remat::dump_all_blocks (void)
     754                 :            : {
     755                 :          0 :   basic_block bb;
     756                 :          0 :   FOR_EACH_BB_FN (bb, m_fn)
     757                 :          0 :     dump_block_info (bb);
     758                 :          0 : }
     759                 :            : 
     760                 :            : /* Return true if REGNO is worth rematerializing.  */
     761                 :            : 
     762                 :            : bool
     763                 :          0 : early_remat::interesting_regno_p (unsigned int regno)
     764                 :            : {
     765                 :            :   /* Ignore unused registers.  */
     766                 :          0 :   rtx reg = regno_reg_rtx[regno];
     767                 :          0 :   if (!reg || DF_REG_DEF_COUNT (regno) == 0)
     768                 :            :     return false;
     769                 :            : 
     770                 :            :   /* Make sure the register has a mode that we want to rematerialize.  */
     771                 :          0 :   if (!bitmap_bit_p (m_selected_modes, GET_MODE (reg)))
     772                 :            :     return false;
     773                 :            : 
     774                 :            :   /* Ignore values that might sometimes be used uninitialized.  We could
     775                 :            :      instead add dummy candidates for the entry block definition, and so
     776                 :            :      handle uses that are definitely not uninitialized, but the combination
     777                 :            :      of the two should be rare in practice.  */
     778                 :          0 :   if (bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn)), regno))
     779                 :          0 :     return false;
     780                 :            : 
     781                 :            :   return true;
     782                 :            : }
     783                 :            : 
     784                 :            : /* Record the set of register REGNO in instruction INSN as a
     785                 :            :    rematerialization candidate.  CAN_COPY_P is true unless we already
     786                 :            :    know that rematerialization is impossible (in which case the candidate
     787                 :            :    only exists for the reaching definition calculation).
     788                 :            : 
     789                 :            :    The candidate's index is not fixed at this stage.  */
     790                 :            : 
     791                 :            : remat_candidate *
     792                 :          0 : early_remat::add_candidate (rtx_insn *insn, unsigned int regno,
     793                 :            :                             bool can_copy_p)
     794                 :            : {
     795                 :          0 :   remat_candidate cand;
     796                 :          0 :   memset (&cand, 0, sizeof (cand));
     797                 :          0 :   cand.regno = regno;
     798                 :          0 :   cand.insn = insn;
     799                 :          0 :   cand.remat_rtx = PATTERN (insn);
     800                 :          0 :   cand.can_copy_p = can_copy_p;
     801                 :          0 :   m_candidates.safe_push (cand);
     802                 :            : 
     803                 :          0 :   bitmap_set_bit (&m_candidate_regnos, regno);
     804                 :            : 
     805                 :          0 :   return &m_candidates.last ();
     806                 :            : }
     807                 :            : 
     808                 :            : /* Return true if we can rematerialize the set of register REGNO in
     809                 :            :    instruction INSN, and add it as a candidate if so.  When returning
     810                 :            :    false, print the reason to the dump file.  */
     811                 :            : 
     812                 :            : bool
     813                 :          0 : early_remat::maybe_add_candidate (rtx_insn *insn, unsigned int regno)
     814                 :            : {
     815                 :            : #define FAILURE_FORMAT ";; Can't rematerialize set of reg %d in %d[bb:%d]: "
     816                 :            : #define FAILURE_ARGS regno, INSN_UID (insn), BLOCK_FOR_INSN (insn)->index
     817                 :            : 
     818                 :            :   /* The definition must come from an ordinary instruction.  */
     819                 :          0 :   basic_block bb = BLOCK_FOR_INSN (insn);
     820                 :          0 :   if (!NONJUMP_INSN_P (insn)
     821                 :          0 :       || (insn == BB_END (bb)
     822                 :          0 :           && has_abnormal_or_eh_outgoing_edge_p (bb)))
     823                 :            :     {
     824                 :          0 :       if (dump_file)
     825                 :          0 :         fprintf (dump_file, FAILURE_FORMAT "insn alters control flow\n",
     826                 :          0 :                  FAILURE_ARGS);
     827                 :          0 :       return false;
     828                 :            :     }
     829                 :            : 
     830                 :            :   /* Prefer to rematerialize constants directly -- it's much easier.  */
     831                 :          0 :   machine_mode mode = GET_MODE (regno_reg_rtx[regno]);
     832                 :          0 :   if (rtx note = find_reg_equal_equiv_note (insn))
     833                 :            :     {
     834                 :          0 :       rtx val = XEXP (note, 0);
     835                 :          0 :       if (CONSTANT_P (val)
     836                 :          0 :           && targetm.legitimate_constant_p (mode, val))
     837                 :            :         {
     838                 :          0 :           remat_candidate *cand = add_candidate (insn, regno, true);
     839                 :          0 :           cand->constant_p = true;
     840                 :          0 :           cand->remat_rtx = val;
     841                 :          0 :           return true;
     842                 :            :         }
     843                 :            :     }
     844                 :            : 
     845                 :            :   /* See whether the target has reasons to prevent a copy.  */
     846                 :          0 :   if (targetm.cannot_copy_insn_p && targetm.cannot_copy_insn_p (insn))
     847                 :            :     {
     848                 :          0 :       if (dump_file)
     849                 :          0 :         fprintf (dump_file, FAILURE_FORMAT "target forbids copying\n",
     850                 :          0 :                  FAILURE_ARGS);
     851                 :          0 :       return false;
     852                 :            :     }
     853                 :            : 
     854                 :            :   /* We can't copy trapping instructions.  */
     855                 :          0 :   rtx pat = PATTERN (insn);
     856                 :          0 :   if (may_trap_p (pat))
     857                 :            :     {
     858                 :          0 :       if (dump_file)
     859                 :          0 :         fprintf (dump_file, FAILURE_FORMAT "insn might trap\n", FAILURE_ARGS);
     860                 :          0 :       return false;
     861                 :            :     }
     862                 :            : 
     863                 :            :   /* We can't copy instructions that read memory, unless we know that
     864                 :            :      the contents never change.  */
     865                 :          0 :   subrtx_iterator::array_type array;
     866                 :          0 :   FOR_EACH_SUBRTX (iter, array, pat, ALL)
     867                 :          0 :     if (MEM_P (*iter) && !MEM_READONLY_P (*iter))
     868                 :            :       {
     869                 :          0 :         if (dump_file)
     870                 :          0 :           fprintf (dump_file, FAILURE_FORMAT "insn references non-constant"
     871                 :          0 :                    " memory\n", FAILURE_ARGS);
     872                 :          0 :         return false;
     873                 :            :       }
     874                 :            : 
     875                 :            :   /* Check each defined register.  */
     876                 :          0 :   df_ref ref;
     877                 :          0 :   FOR_EACH_INSN_DEF (ref, insn)
     878                 :            :     {
     879                 :          0 :       unsigned int def_regno = DF_REF_REGNO (ref);
     880                 :          0 :       if (def_regno == regno)
     881                 :            :         {
     882                 :            :           /* Make sure the definition is write-only.  (Partial definitions,
     883                 :            :              such as setting the low part and clobbering the high part,
     884                 :            :              are otherwise OK.)  */
     885                 :          0 :           if (DF_REF_FLAGS_IS_SET (ref, DF_REF_READ_WRITE))
     886                 :            :             {
     887                 :          0 :               if (dump_file)
     888                 :          0 :                 fprintf (dump_file, FAILURE_FORMAT "destination is"
     889                 :          0 :                          " read-modify-write\n", FAILURE_ARGS);
     890                 :          0 :               return false;
     891                 :            :             }
     892                 :            :         }
     893                 :            :       else
     894                 :            :         {
     895                 :            :           /* The instruction can set additional registers, provided that
     896                 :            :              they're hard registers.  This is useful for instructions
     897                 :            :              that alter the condition codes.  */
     898                 :          0 :           if (!HARD_REGISTER_NUM_P (def_regno))
     899                 :            :             {
     900                 :          0 :               if (dump_file)
     901                 :          0 :                 fprintf (dump_file, FAILURE_FORMAT "insn also sets"
     902                 :          0 :                          " pseudo reg %d\n", FAILURE_ARGS, def_regno);
     903                 :          0 :               return false;
     904                 :            :             }
     905                 :            :         }
     906                 :            :     }
     907                 :            : 
     908                 :            :   /* If the instruction uses fixed hard registers, check that those
     909                 :            :      registers have the same value throughout the function.  If the
     910                 :            :      instruction uses non-fixed hard registers, check that we can
     911                 :            :      replace them with pseudos.  */
     912                 :          0 :   FOR_EACH_INSN_USE (ref, insn)
     913                 :            :     {
     914                 :          0 :       unsigned int use_regno = DF_REF_REGNO (ref);
     915                 :          0 :       if (HARD_REGISTER_NUM_P (use_regno) && fixed_regs[use_regno])
     916                 :            :         {
     917                 :          0 :           if (rtx_unstable_p (DF_REF_REAL_REG (ref)))
     918                 :            :             {
     919                 :          0 :               if (dump_file)
     920                 :          0 :                 fprintf (dump_file, FAILURE_FORMAT "insn uses fixed hard reg"
     921                 :          0 :                          " %d\n", FAILURE_ARGS, use_regno);
     922                 :          0 :               return false;
     923                 :            :             }
     924                 :            :         }
     925                 :          0 :       else if (HARD_REGISTER_NUM_P (use_regno))
     926                 :            :         {
     927                 :            :           /* Allocate a dummy pseudo register and temporarily install it.
     928                 :            :              Make the register number depend on the mode, which should
     929                 :            :              provide enough sharing for match_dup while also weeding
     930                 :            :              out cases in which operands with different modes are
     931                 :            :              explicitly tied.  */
     932                 :          0 :           rtx *loc = DF_REF_REAL_LOC (ref);
     933                 :          0 :           unsigned int size = RTX_CODE_SIZE (REG);
     934                 :          0 :           rtx new_reg = (rtx) alloca (size);
     935                 :          0 :           memset (new_reg, 0, size);
     936                 :          0 :           PUT_CODE (new_reg, REG);
     937                 :          0 :           set_mode_and_regno (new_reg, GET_MODE (*loc),
     938                 :          0 :                               LAST_VIRTUAL_REGISTER + 1 + GET_MODE (*loc));
     939                 :          0 :           validate_change (insn, loc, new_reg, 1);
     940                 :            :         }
     941                 :            :     }
     942                 :          0 :   bool ok_p = verify_changes (0);
     943                 :          0 :   cancel_changes (0);
     944                 :          0 :   if (!ok_p)
     945                 :            :     {
     946                 :          0 :       if (dump_file)
     947                 :          0 :         fprintf (dump_file, FAILURE_FORMAT "insn does not allow hard"
     948                 :          0 :                  " register inputs to be replaced\n", FAILURE_ARGS);
     949                 :          0 :       return false;
     950                 :            :     }
     951                 :            : 
     952                 :            : #undef FAILURE_ARGS
     953                 :            : #undef FAILURE_FORMAT
     954                 :            : 
     955                 :          0 :   add_candidate (insn, regno, true);
     956                 :          0 :   return true;
     957                 :            : }
     958                 :            : 
     959                 :            : /* Calculate the set of rematerialization candidates.  Return true if
     960                 :            :    we find at least one.  */
     961                 :            : 
     962                 :            : bool
     963                 :          0 : early_remat::collect_candidates (void)
     964                 :            : {
     965                 :          0 :   unsigned int nregs = DF_REG_SIZE (df);
     966                 :          0 :   for (unsigned int regno = FIRST_PSEUDO_REGISTER; regno < nregs; ++regno)
     967                 :          0 :     if (interesting_regno_p (regno))
     968                 :            :       {
     969                 :            :         /* Create candidates for all suitable definitions.  */
     970                 :          0 :         bitmap_clear (&m_tmp_bitmap);
     971                 :          0 :         unsigned int bad = 0;
     972                 :          0 :         unsigned int id = 0;
     973                 :          0 :         for (df_ref ref = DF_REG_DEF_CHAIN (regno); ref;
     974                 :          0 :              ref = DF_REF_NEXT_REG (ref))
     975                 :            :           {
     976                 :          0 :             rtx_insn *insn = DF_REF_INSN (ref);
     977                 :          0 :             if (maybe_add_candidate (insn, regno))
     978                 :          0 :               bitmap_set_bit (&m_tmp_bitmap, id);
     979                 :            :             else
     980                 :          0 :               bad += 1;
     981                 :          0 :             id += 1;
     982                 :            :           }
     983                 :            : 
     984                 :            :         /* If we found at least one suitable definition, add dummy
     985                 :            :            candidates for the rest, so that we can see which definitions
     986                 :            :            are live where.  */
     987                 :          0 :         if (!bitmap_empty_p (&m_tmp_bitmap) && bad)
     988                 :            :           {
     989                 :          0 :             id = 0;
     990                 :          0 :             for (df_ref ref = DF_REG_DEF_CHAIN (regno); ref;
     991                 :          0 :                  ref = DF_REF_NEXT_REG (ref))
     992                 :            :               {
     993                 :          0 :                 if (!bitmap_bit_p (&m_tmp_bitmap, id))
     994                 :          0 :                   add_candidate (DF_REF_INSN (ref), regno, false);
     995                 :          0 :                 id += 1;
     996                 :            :               }
     997                 :            :           }
     998                 :            :       }
     999                 :            : 
    1000                 :            : 
    1001                 :          0 :   return !m_candidates.is_empty ();
    1002                 :            : }
    1003                 :            : 
    1004                 :            : /* Initialize the m_block_info array.  */
    1005                 :            : 
    1006                 :            : void
    1007                 :          0 : early_remat::init_block_info (void)
    1008                 :            : {
    1009                 :          0 :   unsigned int n_blocks = last_basic_block_for_fn (m_fn);
    1010                 :          0 :   m_block_info.safe_grow_cleared (n_blocks);
    1011                 :          0 : }
    1012                 :            : 
    1013                 :            : /* Maps basic block indices to their position in the post order.  */
    1014                 :            : static unsigned int *postorder_index;
    1015                 :            : 
    1016                 :            : /* Order remat_candidates X_IN and Y_IN according to the cfg postorder.  */
    1017                 :            : 
    1018                 :            : static int
    1019                 :          0 : compare_candidates (const void *x_in, const void *y_in)
    1020                 :            : {
    1021                 :          0 :   const remat_candidate *x = (const remat_candidate *) x_in;
    1022                 :          0 :   const remat_candidate *y = (const remat_candidate *) y_in;
    1023                 :          0 :   basic_block x_bb = BLOCK_FOR_INSN (x->insn);
    1024                 :          0 :   basic_block y_bb = BLOCK_FOR_INSN (y->insn);
    1025                 :          0 :   if (x_bb != y_bb)
    1026                 :            :     /* Make X and Y follow block postorder.  */
    1027                 :          0 :     return postorder_index[x_bb->index] - postorder_index[y_bb->index];
    1028                 :            : 
    1029                 :            :   /* Make X and Y follow a backward traversal of the containing block.  */
    1030                 :          0 :   return DF_INSN_LUID (y->insn) - DF_INSN_LUID (x->insn);
    1031                 :            : }
    1032                 :            : 
    1033                 :            : /* Sort the collected rematerialization candidates so that they follow
    1034                 :            :    cfg postorder.  */
    1035                 :            : 
    1036                 :            : void
    1037                 :          0 : early_remat::sort_candidates (void)
    1038                 :            : {
    1039                 :            :   /* Make sure the DF LUIDs are up-to-date for all the blocks we
    1040                 :            :      care about.  */
    1041                 :          0 :   bitmap_clear (&m_tmp_bitmap);
    1042                 :          0 :   unsigned int cand_index;
    1043                 :          0 :   remat_candidate *cand;
    1044                 :          0 :   FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
    1045                 :            :     {
    1046                 :          0 :       basic_block bb = BLOCK_FOR_INSN (cand->insn);
    1047                 :          0 :       if (bitmap_set_bit (&m_tmp_bitmap, bb->index))
    1048                 :          0 :         df_recompute_luids (bb);
    1049                 :            :     }
    1050                 :            : 
    1051                 :            :   /* Create a mapping from block numbers to their position in the
    1052                 :            :      postorder.  */
    1053                 :          0 :   unsigned int n_blocks = last_basic_block_for_fn (m_fn);
    1054                 :          0 :   int *postorder = df_get_postorder (DF_BACKWARD);
    1055                 :          0 :   unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
    1056                 :          0 :   postorder_index = new unsigned int[n_blocks];
    1057                 :          0 :   for (unsigned int i = 0; i < postorder_len; ++i)
    1058                 :          0 :     postorder_index[postorder[i]] = i;
    1059                 :            : 
    1060                 :          0 :   m_candidates.qsort (compare_candidates);
    1061                 :            : 
    1062                 :          0 :   delete postorder_index;
    1063                 :          0 : }
    1064                 :            : 
    1065                 :            : /* Commit to the current candidate indices and initialize cross-references.  */
    1066                 :            : 
    1067                 :            : void
    1068                 :          0 : early_remat::finalize_candidate_indices (void)
    1069                 :            : {
    1070                 :            :   /* Create a bitmap for each candidate register.  */
    1071                 :          0 :   m_regno_to_candidates.safe_grow (max_reg_num ());
    1072                 :          0 :   unsigned int regno;
    1073                 :          0 :   bitmap_iterator bi;
    1074                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (&m_candidate_regnos, 0, regno, bi)
    1075                 :          0 :     m_regno_to_candidates[regno] = alloc_bitmap ();
    1076                 :            : 
    1077                 :            :   /* Go through each candidate and record its index.  */
    1078                 :            :   unsigned int cand_index;
    1079                 :            :   remat_candidate *cand;
    1080                 :          0 :   FOR_EACH_VEC_ELT (m_candidates, cand_index, cand)
    1081                 :            :     {
    1082                 :          0 :       basic_block bb = BLOCK_FOR_INSN (cand->insn);
    1083                 :          0 :       remat_block_info *info = &m_block_info[bb->index];
    1084                 :          0 :       info->num_candidates += 1;
    1085                 :          0 :       info->first_candidate = cand_index;
    1086                 :          0 :       bitmap_set_bit (m_regno_to_candidates[cand->regno], cand_index);
    1087                 :            :     }
    1088                 :          0 : }
    1089                 :            : 
    1090                 :            : /* Record that candidates CAND1_INDEX and CAND2_INDEX are equivalent.
    1091                 :            :    CAND1_INDEX might already have an equivalence class, but CAND2_INDEX
    1092                 :            :    doesn't.  */
    1093                 :            : 
    1094                 :            : void
    1095                 :          0 : early_remat::record_equiv_candidates (unsigned int cand1_index,
    1096                 :            :                                       unsigned int cand2_index)
    1097                 :            : {
    1098                 :          0 :   if (dump_file)
    1099                 :          0 :     fprintf (dump_file, ";; Candidate %d is equivalent to candidate %d\n",
    1100                 :            :              cand2_index, cand1_index);
    1101                 :            : 
    1102                 :          0 :   remat_candidate *cand1 = &m_candidates[cand1_index];
    1103                 :          0 :   remat_candidate *cand2 = &m_candidates[cand2_index];
    1104                 :          0 :   gcc_checking_assert (!cand2->equiv_class);
    1105                 :            : 
    1106                 :          0 :   remat_equiv_class *ec = cand1->equiv_class;
    1107                 :          0 :   if (!ec)
    1108                 :            :     {
    1109                 :          0 :       ec = XOBNEW (&m_obstack.obstack, remat_equiv_class);
    1110                 :          0 :       ec->members = alloc_bitmap ();
    1111                 :          0 :       bitmap_set_bit (ec->members, cand1_index);
    1112                 :          0 :       ec->earliest = cand1_index;
    1113                 :          0 :       ec->representative = cand1_index;
    1114                 :          0 :       cand1->equiv_class = ec;
    1115                 :            :     }
    1116                 :          0 :   cand2->equiv_class = ec;
    1117                 :          0 :   bitmap_set_bit (ec->members, cand2_index);
    1118                 :          0 :   if (cand2_index > ec->representative)
    1119                 :          0 :     ec->representative = cand2_index;
    1120                 :          0 : }
    1121                 :            : 
    1122                 :            : /* Propagate information from the rd_out set of E->src to the rd_in set
    1123                 :            :    of E->dest, when computing global reaching definitions.  Return true
    1124                 :            :    if something changed.  */
    1125                 :            : 
    1126                 :            : bool
    1127                 :          0 : early_remat::rd_confluence_n (edge e)
    1128                 :            : {
    1129                 :          0 :   remat_block_info *src = &er->m_block_info[e->src->index];
    1130                 :          0 :   remat_block_info *dest = &er->m_block_info[e->dest->index];
    1131                 :            : 
    1132                 :            :   /* available_in temporarily contains the set of candidates whose
    1133                 :            :      registers are live on entry.  */
    1134                 :          0 :   if (empty_p (src->rd_out) || empty_p (dest->available_in))
    1135                 :            :     return false;
    1136                 :            : 
    1137                 :          0 :   return bitmap_ior_and_into (er->get_bitmap (&dest->rd_in),
    1138                 :          0 :                               src->rd_out, dest->available_in);
    1139                 :            : }
    1140                 :            : 
    1141                 :            : /* Propagate information from the rd_in set of block BB_INDEX to rd_out.
    1142                 :            :    Return true if something changed.  */
    1143                 :            : 
    1144                 :            : bool
    1145                 :          0 : early_remat::rd_transfer (int bb_index)
    1146                 :            : {
    1147                 :          0 :   remat_block_info *info = &er->m_block_info[bb_index];
    1148                 :            : 
    1149                 :          0 :   if (empty_p (info->rd_in))
    1150                 :            :     return false;
    1151                 :            : 
    1152                 :          0 :   if (empty_p (info->rd_kill))
    1153                 :            :     {
    1154                 :          0 :       gcc_checking_assert (empty_p (info->rd_gen));
    1155                 :          0 :       if (!info->rd_out)
    1156                 :          0 :         info->rd_out = info->rd_in;
    1157                 :            :       else
    1158                 :          0 :         gcc_checking_assert (info->rd_out == info->rd_in);
    1159                 :            :       /* Assume that we only get called if something changed.  */
    1160                 :          0 :       return true;
    1161                 :            :     }
    1162                 :            : 
    1163                 :          0 :   if (empty_p (info->rd_gen))
    1164                 :          0 :     return bitmap_and_compl (er->get_bitmap (&info->rd_out),
    1165                 :          0 :                              info->rd_in, info->rd_kill);
    1166                 :            : 
    1167                 :          0 :   return bitmap_ior_and_compl (er->get_bitmap (&info->rd_out), info->rd_gen,
    1168                 :          0 :                                info->rd_in, info->rd_kill);
    1169                 :            : }
    1170                 :            : 
    1171                 :            : /* Calculate the rd_* sets for each block.  */
    1172                 :            : 
    1173                 :            : void
    1174                 :          0 : early_remat::compute_rd (void)
    1175                 :            : {
    1176                 :            :   /* First calculate the rd_kill and rd_gen sets, using the fact
    1177                 :            :      that m_candidates is sorted in order of decreasing LUID.  */
    1178                 :          0 :   unsigned int cand_index;
    1179                 :          0 :   remat_candidate *cand;
    1180                 :          0 :   FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand_index, cand)
    1181                 :            :     {
    1182                 :          0 :       rtx_insn *insn = cand->insn;
    1183                 :          0 :       basic_block bb = BLOCK_FOR_INSN (insn);
    1184                 :          0 :       remat_block_info *info = &m_block_info[bb->index];
    1185                 :          0 :       bitmap kill = m_regno_to_candidates[cand->regno];
    1186                 :          0 :       bitmap_ior_into (get_bitmap (&info->rd_kill), kill);
    1187                 :          0 :       if (bitmap_bit_p (DF_LR_OUT (bb), cand->regno))
    1188                 :            :         {
    1189                 :          0 :           bitmap_and_compl_into (get_bitmap (&info->rd_gen), kill);
    1190                 :          0 :           bitmap_set_bit (info->rd_gen, cand_index);
    1191                 :            :         }
    1192                 :            :     }
    1193                 :            : 
    1194                 :            :   /* Set up the initial values of the other sets.  */
    1195                 :          0 :   basic_block bb;
    1196                 :          0 :   FOR_EACH_BB_FN (bb, m_fn)
    1197                 :            :     {
    1198                 :          0 :       remat_block_info *info = &m_block_info[bb->index];
    1199                 :          0 :       unsigned int regno;
    1200                 :          0 :       bitmap_iterator bi;
    1201                 :          0 :       EXECUTE_IF_AND_IN_BITMAP (DF_LR_IN (bb), &m_candidate_regnos,
    1202                 :            :                                 0, regno, bi)
    1203                 :            :         {
    1204                 :            :           /* Use available_in to record the set of candidates whose
    1205                 :            :              registers are live on entry (i.e. a maximum bound on rd_in).  */
    1206                 :          0 :           bitmap_ior_into (get_bitmap (&info->available_in),
    1207                 :          0 :                            m_regno_to_candidates[regno]);
    1208                 :            : 
    1209                 :            :           /* Add registers that die in a block to the block's kill set,
    1210                 :            :              so that we don't needlessly propagate them through the rest
    1211                 :            :              of the function.  */
    1212                 :          0 :           if (!bitmap_bit_p (DF_LR_OUT (bb), regno))
    1213                 :          0 :             bitmap_ior_into (get_bitmap (&info->rd_kill),
    1214                 :          0 :                              m_regno_to_candidates[regno]);
    1215                 :            :         }
    1216                 :            : 
    1217                 :            :       /* Initialize each block's rd_out to the minimal set (the set of
    1218                 :            :          local definitions).  */
    1219                 :          0 :       if (!empty_p (info->rd_gen))
    1220                 :          0 :         bitmap_copy (get_bitmap (&info->rd_out), info->rd_gen);
    1221                 :            :     }
    1222                 :            : 
    1223                 :            :   /* Iterate until we reach a fixed point.  */
    1224                 :          0 :   er = this;
    1225                 :          0 :   bitmap_clear (&m_tmp_bitmap);
    1226                 :          0 :   bitmap_set_range (&m_tmp_bitmap, 0, last_basic_block_for_fn (m_fn));
    1227                 :          0 :   df_simple_dataflow (DF_FORWARD, NULL, NULL, rd_confluence_n, rd_transfer,
    1228                 :            :                       &m_tmp_bitmap, df_get_postorder (DF_FORWARD),
    1229                 :            :                       df_get_n_blocks (DF_FORWARD));
    1230                 :          0 :   er = 0;
    1231                 :            : 
    1232                 :            :   /* Work out which definitions reach which candidates, again taking
    1233                 :            :      advantage of the candidate order.  */
    1234                 :          0 :   bitmap_head reaching;
    1235                 :          0 :   bitmap_initialize (&reaching, &m_obstack);
    1236                 :          0 :   basic_block old_bb = NULL;
    1237                 :          0 :   FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand_index, cand)
    1238                 :            :     {
    1239                 :          0 :       bb = BLOCK_FOR_INSN (cand->insn);
    1240                 :          0 :       if (bb != old_bb)
    1241                 :            :         {
    1242                 :            :           /* Get the definitions that reach the start of the new block.  */
    1243                 :          0 :           remat_block_info *info = &m_block_info[bb->index];
    1244                 :          0 :           if (info->rd_in)
    1245                 :          0 :             bitmap_copy (&reaching, info->rd_in);
    1246                 :            :           else
    1247                 :          0 :             bitmap_clear (&reaching);
    1248                 :            :           old_bb = bb;
    1249                 :            :         }
    1250                 :            :       else
    1251                 :            :         {
    1252                 :            :           /* Process the definitions of the previous instruction.  */
    1253                 :          0 :           bitmap kill = m_regno_to_candidates[cand[1].regno];
    1254                 :          0 :           bitmap_and_compl_into (&reaching, kill);
    1255                 :          0 :           bitmap_set_bit (&reaching, cand_index + 1);
    1256                 :            :         }
    1257                 :            : 
    1258                 :          0 :       if (cand->can_copy_p && !cand->constant_p)
    1259                 :            :         {
    1260                 :          0 :           df_ref ref;
    1261                 :          0 :           FOR_EACH_INSN_USE (ref, cand->insn)
    1262                 :            :             {
    1263                 :          0 :               unsigned int regno = DF_REF_REGNO (ref);
    1264                 :          0 :               if (bitmap_bit_p (&m_candidate_regnos, regno))
    1265                 :            :                 {
    1266                 :          0 :                   bitmap defs = m_regno_to_candidates[regno];
    1267                 :          0 :                   bitmap_and (&m_tmp_bitmap, defs, &reaching);
    1268                 :          0 :                   bitmap_ior_into (get_bitmap (&cand->uses), &m_tmp_bitmap);
    1269                 :            :                 }
    1270                 :            :             }
    1271                 :            :         }
    1272                 :            :     }
    1273                 :          0 :   bitmap_clear (&reaching);
    1274                 :          0 : }
    1275                 :            : 
    1276                 :            : /* If CAND_INDEX is in an equivalence class, return the representative
    1277                 :            :    of the class, otherwise return CAND_INDEX.  */
    1278                 :            : 
    1279                 :            : inline unsigned int
    1280                 :          0 : early_remat::canon_candidate (unsigned int cand_index)
    1281                 :            : {
    1282                 :          0 :   if (remat_equiv_class *ec = m_candidates[cand_index].equiv_class)
    1283                 :          0 :     return ec->representative;
    1284                 :            :   return cand_index;
    1285                 :            : }
    1286                 :            : 
    1287                 :            : /* Make candidate set *PTR refer to candidates using the representative
    1288                 :            :    of each equivalence class.  */
    1289                 :            : 
    1290                 :            : void
    1291                 :          0 : early_remat::canon_bitmap (bitmap *ptr)
    1292                 :            : {
    1293                 :          0 :   bitmap old_set = *ptr;
    1294                 :          0 :   if (empty_p (old_set))
    1295                 :          0 :     return;
    1296                 :            : 
    1297                 :          0 :   bitmap new_set = NULL;
    1298                 :          0 :   unsigned int old_index;
    1299                 :          0 :   bitmap_iterator bi;
    1300                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (old_set, 0, old_index, bi)
    1301                 :            :     {
    1302                 :          0 :       unsigned int new_index = canon_candidate (old_index);
    1303                 :          0 :       if (old_index != new_index)
    1304                 :            :         {
    1305                 :          0 :           if (!new_set)
    1306                 :            :             {
    1307                 :          0 :               new_set = alloc_bitmap ();
    1308                 :          0 :               bitmap_copy (new_set, old_set);
    1309                 :            :             }
    1310                 :          0 :           bitmap_clear_bit (new_set, old_index);
    1311                 :          0 :           bitmap_set_bit (new_set, new_index);
    1312                 :            :         }
    1313                 :            :     }
    1314                 :          0 :   if (new_set)
    1315                 :            :     {
    1316                 :          0 :       BITMAP_FREE (*ptr);
    1317                 :          0 :       *ptr = new_set;
    1318                 :            :     }
    1319                 :            : }
    1320                 :            : 
    1321                 :            : /* If the candidates in REACHING all have the same value, return the
    1322                 :            :    earliest instance of that value (i.e. the first one to be added
    1323                 :            :    to m_value_table), otherwise return MULTIPLE_CANDIDATES.  */
    1324                 :            : 
    1325                 :            : unsigned int
    1326                 :          0 : early_remat::resolve_reaching_def (bitmap reaching)
    1327                 :            : {
    1328                 :          0 :   unsigned int cand_index = bitmap_first_set_bit (reaching);
    1329                 :          0 :   if (remat_equiv_class *ec = m_candidates[cand_index].equiv_class)
    1330                 :            :     {
    1331                 :          0 :       if (!bitmap_intersect_compl_p (reaching, ec->members))
    1332                 :          0 :         return ec->earliest;
    1333                 :            :     }
    1334                 :          0 :   else if (bitmap_single_bit_set_p (reaching))
    1335                 :          0 :     return cand_index;
    1336                 :            : 
    1337                 :            :   return MULTIPLE_CANDIDATES;
    1338                 :            : }
    1339                 :            : 
    1340                 :            : /* Check whether all candidate registers used by candidate CAND_INDEX have
    1341                 :            :    unique definitions.  Return true if so, replacing the candidate's uses
    1342                 :            :    set with the appropriate form for value numbering.  */
    1343                 :            : 
    1344                 :            : bool
    1345                 :          0 : early_remat::check_candidate_uses (unsigned int cand_index)
    1346                 :            : {
    1347                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1348                 :            : 
    1349                 :            :   /* Process the uses for each register in turn.  */
    1350                 :          0 :   bitmap_head uses;
    1351                 :          0 :   bitmap_initialize (&uses, &m_obstack);
    1352                 :          0 :   bitmap_copy (&uses, cand->uses);
    1353                 :          0 :   bitmap uses_ec = alloc_bitmap ();
    1354                 :          0 :   while (!bitmap_empty_p (&uses))
    1355                 :            :     {
    1356                 :            :       /* Get the register for the lowest-indexed candidate remaining,
    1357                 :            :          and the reaching definitions of that register.  */
    1358                 :          0 :       unsigned int first = bitmap_first_set_bit (&uses);
    1359                 :          0 :       unsigned int regno = m_candidates[first].regno;
    1360                 :          0 :       bitmap_and (&m_tmp_bitmap, &uses, m_regno_to_candidates[regno]);
    1361                 :            : 
    1362                 :            :       /* See whether all reaching definitions have the same value and if
    1363                 :            :          so get the index of the first candidate we saw with that value.  */
    1364                 :          0 :       unsigned int def = resolve_reaching_def (&m_tmp_bitmap);
    1365                 :          0 :       if (def == MULTIPLE_CANDIDATES)
    1366                 :            :         {
    1367                 :          0 :           if (dump_file)
    1368                 :          0 :             fprintf (dump_file, ";; Removing candidate %d because there is"
    1369                 :            :                      " more than one reaching definition of reg %d\n",
    1370                 :            :                      cand_index, regno);
    1371                 :          0 :           cand->can_copy_p = false;
    1372                 :          0 :           break;
    1373                 :            :         }
    1374                 :          0 :       bitmap_set_bit (uses_ec, def);
    1375                 :          0 :       bitmap_and_compl_into (&uses, &m_tmp_bitmap);
    1376                 :            :     }
    1377                 :          0 :   BITMAP_FREE (cand->uses);
    1378                 :          0 :   cand->uses = uses_ec;
    1379                 :          0 :   return cand->can_copy_p;
    1380                 :            : }
    1381                 :            : 
    1382                 :            : /* Calculate the set of hard registers that would be clobbered by
    1383                 :            :    rematerializing candidate CAND_INDEX.  At this point the candidate's
    1384                 :            :    set of uses is final.  */
    1385                 :            : 
    1386                 :            : void
    1387                 :          0 : early_remat::compute_clobbers (unsigned int cand_index)
    1388                 :            : {
    1389                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1390                 :          0 :   if (cand->uses)
    1391                 :            :     {
    1392                 :          0 :       unsigned int use_index;
    1393                 :          0 :       bitmap_iterator bi;
    1394                 :          0 :       EXECUTE_IF_SET_IN_BITMAP (cand->uses, 0, use_index, bi)
    1395                 :          0 :         if (bitmap clobbers = m_candidates[use_index].clobbers)
    1396                 :          0 :           bitmap_ior_into (get_bitmap (&cand->clobbers), clobbers);
    1397                 :            :     }
    1398                 :            : 
    1399                 :          0 :   df_ref ref;
    1400                 :          0 :   FOR_EACH_INSN_DEF (ref, cand->insn)
    1401                 :            :     {
    1402                 :          0 :       unsigned int def_regno = DF_REF_REGNO (ref);
    1403                 :          0 :       if (def_regno != cand->regno)
    1404                 :          0 :         bitmap_set_bit (get_bitmap (&cand->clobbers), def_regno);
    1405                 :            :     }
    1406                 :          0 : }
    1407                 :            : 
    1408                 :            : /* Mark candidate CAND_INDEX as validated and add it to the value table.  */
    1409                 :            : 
    1410                 :            : void
    1411                 :          0 : early_remat::assign_value_number (unsigned int cand_index)
    1412                 :            : {
    1413                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1414                 :          0 :   gcc_checking_assert (cand->can_copy_p && !cand->validated_p);
    1415                 :            : 
    1416                 :          0 :   compute_clobbers (cand_index);
    1417                 :          0 :   cand->validated_p = true;
    1418                 :            : 
    1419                 :          0 :   inchash::hash h;
    1420                 :          0 :   h.add_int (cand->regno);
    1421                 :          0 :   inchash::add_rtx (cand->remat_rtx, h);
    1422                 :          0 :   cand->hash = h.end ();
    1423                 :            : 
    1424                 :          0 :   remat_candidate **slot
    1425                 :          0 :     = m_value_table.find_slot_with_hash (cand, cand->hash, INSERT);
    1426                 :          0 :   if (!*slot)
    1427                 :            :     {
    1428                 :          0 :       *slot = cand;
    1429                 :          0 :       if (dump_file)
    1430                 :          0 :         fprintf (dump_file, ";; Candidate %d is not equivalent to"
    1431                 :            :                  " others seen so far\n", cand_index);
    1432                 :            :     }
    1433                 :            :   else
    1434                 :          0 :     record_equiv_candidates (*slot - m_candidates.address (), cand_index);
    1435                 :          0 : }
    1436                 :            : 
    1437                 :            : /* Make a final decision about which candidates are valid and assign
    1438                 :            :    value numbers to those that are.  */
    1439                 :            : 
    1440                 :            : void
    1441                 :          0 : early_remat::decide_candidate_validity (void)
    1442                 :            : {
    1443                 :          0 :   auto_vec<unsigned int, 16> stack;
    1444                 :          0 :   unsigned int cand1_index;
    1445                 :          0 :   remat_candidate *cand1;
    1446                 :          0 :   FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand1_index, cand1)
    1447                 :            :     {
    1448                 :          0 :       if (!cand1->can_copy_p || cand1->validated_p)
    1449                 :          0 :         continue;
    1450                 :            : 
    1451                 :          0 :       if (empty_p (cand1->uses))
    1452                 :            :         {
    1453                 :          0 :           assign_value_number (cand1_index);
    1454                 :          0 :           continue;
    1455                 :            :         }
    1456                 :            : 
    1457                 :          0 :       stack.safe_push (cand1_index);
    1458                 :          0 :       while (!stack.is_empty ())
    1459                 :            :         {
    1460                 :          0 :           unsigned int cand2_index = stack.last ();
    1461                 :          0 :           unsigned int watermark = stack.length ();
    1462                 :          0 :           remat_candidate *cand2 = &m_candidates[cand2_index];
    1463                 :          0 :           if (!cand2->can_copy_p || cand2->validated_p)
    1464                 :            :             {
    1465                 :          0 :               stack.pop ();
    1466                 :          0 :               continue;
    1467                 :            :             }
    1468                 :          0 :           cand2->visited_p = true;
    1469                 :          0 :           unsigned int cand3_index;
    1470                 :          0 :           bitmap_iterator bi;
    1471                 :          0 :           EXECUTE_IF_SET_IN_BITMAP (cand2->uses, 0, cand3_index, bi)
    1472                 :            :             {
    1473                 :          0 :               remat_candidate *cand3 = &m_candidates[cand3_index];
    1474                 :          0 :               if (!cand3->can_copy_p)
    1475                 :            :                 {
    1476                 :          0 :                   if (dump_file)
    1477                 :          0 :                     fprintf (dump_file, ";; Removing candidate %d because"
    1478                 :            :                              " it uses removed candidate %d\n", cand2_index,
    1479                 :            :                              cand3_index);
    1480                 :          0 :                   cand2->can_copy_p = false;
    1481                 :          0 :                   break;
    1482                 :            :                 }
    1483                 :          0 :               if (!cand3->validated_p)
    1484                 :            :                 {
    1485                 :          0 :                   if (empty_p (cand3->uses))
    1486                 :          0 :                     assign_value_number (cand3_index);
    1487                 :          0 :                   else if (cand3->visited_p)
    1488                 :            :                     {
    1489                 :          0 :                       if (dump_file)
    1490                 :          0 :                         fprintf (dump_file, ";; Removing candidate %d"
    1491                 :            :                                  " because its definition is cyclic\n",
    1492                 :            :                                  cand2_index);
    1493                 :          0 :                       cand2->can_copy_p = false;
    1494                 :          0 :                       break;
    1495                 :            :                     }
    1496                 :            :                   else
    1497                 :          0 :                     stack.safe_push (cand3_index);
    1498                 :            :                 }
    1499                 :            :             }
    1500                 :          0 :           if (!cand2->can_copy_p)
    1501                 :            :             {
    1502                 :          0 :               cand2->visited_p = false;
    1503                 :          0 :               stack.truncate (watermark - 1);
    1504                 :            :             }
    1505                 :          0 :           else if (watermark == stack.length ())
    1506                 :            :             {
    1507                 :          0 :               cand2->visited_p = false;
    1508                 :          0 :               if (check_candidate_uses (cand2_index))
    1509                 :          0 :                 assign_value_number (cand2_index);
    1510                 :          0 :               stack.pop ();
    1511                 :            :             }
    1512                 :            :         }
    1513                 :            :     }
    1514                 :            : 
    1515                 :            :   /* Ensure that the candidates always use the same candidate index
    1516                 :            :      to refer to an equivalence class.  */
    1517                 :          0 :   FOR_EACH_VEC_ELT_REVERSE (m_candidates, cand1_index, cand1)
    1518                 :          0 :     if (cand1->can_copy_p && !empty_p (cand1->uses))
    1519                 :            :       {
    1520                 :          0 :         canon_bitmap (&cand1->uses);
    1521                 :          0 :         gcc_checking_assert (bitmap_first_set_bit (cand1->uses) > cand1_index);
    1522                 :            :       }
    1523                 :          0 : }
    1524                 :            : 
    1525                 :            : /* Remove any candidates in CANDIDATES that would clobber a register in
    1526                 :            :    UNAVAIL_REGS.  */
    1527                 :            : 
    1528                 :            : void
    1529                 :          0 : early_remat::restrict_remat_for_unavail_regs (bitmap candidates,
    1530                 :            :                                               const_bitmap unavail_regs)
    1531                 :            : {
    1532                 :          0 :   bitmap_clear (&m_tmp_bitmap);
    1533                 :          0 :   unsigned int cand_index;
    1534                 :          0 :   bitmap_iterator bi;
    1535                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (candidates, 0, cand_index, bi)
    1536                 :            :     {
    1537                 :          0 :       remat_candidate *cand = &m_candidates[cand_index];
    1538                 :          0 :       if (cand->clobbers
    1539                 :          0 :           && bitmap_intersect_p (cand->clobbers, unavail_regs))
    1540                 :          0 :         bitmap_set_bit (&m_tmp_bitmap, cand_index);
    1541                 :            :     }
    1542                 :          0 :   bitmap_and_compl_into (candidates, &m_tmp_bitmap);
    1543                 :          0 : }
    1544                 :            : 
    1545                 :            : /* Remove any candidates in CANDIDATES that would clobber a register
    1546                 :            :    that is potentially live across CALL.  */
    1547                 :            : 
    1548                 :            : void
    1549                 :          0 : early_remat::restrict_remat_for_call (bitmap candidates, rtx_insn *call)
    1550                 :            : {
    1551                 :            :   /* We don't know whether partially-clobbered registers are live
    1552                 :            :      across the call or not, so assume that they are.  */
    1553                 :          0 :   bitmap_view<HARD_REG_SET> call_preserved_regs
    1554                 :          0 :     (~insn_callee_abi (call).full_reg_clobbers ());
    1555                 :          0 :   restrict_remat_for_unavail_regs (candidates, call_preserved_regs);
    1556                 :          0 : }
    1557                 :            : 
    1558                 :            : /* Assuming that every path reaching a point P contains a copy of a
    1559                 :            :    use U of REGNO, return true if another copy of U at P would have
    1560                 :            :    access to the same value of REGNO.  */
    1561                 :            : 
    1562                 :            : bool
    1563                 :          0 : early_remat::stable_use_p (unsigned int regno)
    1564                 :            : {
    1565                 :            :   /* Conservatively assume not for hard registers.  */
    1566                 :          0 :   if (HARD_REGISTER_NUM_P (regno))
    1567                 :            :     return false;
    1568                 :            : 
    1569                 :            :   /* See if REGNO has a single definition and is never used uninitialized.
    1570                 :            :      In this case the definition of REGNO dominates the common dominator
    1571                 :            :      of the uses U, which in turn dominates P.  */
    1572                 :          0 :   if (DF_REG_DEF_COUNT (regno) == 1
    1573                 :          0 :       && !bitmap_bit_p (DF_LR_OUT (ENTRY_BLOCK_PTR_FOR_FN (m_fn)), regno))
    1574                 :          0 :     return true;
    1575                 :            : 
    1576                 :            :   return false;
    1577                 :            : }
    1578                 :            : 
    1579                 :            : /* Emit a copy from register DEST to register SRC before candidate
    1580                 :            :    CAND_INDEX's instruction.  */
    1581                 :            : 
    1582                 :            : void
    1583                 :          0 : early_remat::emit_copy_before (unsigned int cand_index, rtx dest, rtx src)
    1584                 :            : {
    1585                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1586                 :          0 :   if (dump_file)
    1587                 :            :     {
    1588                 :          0 :       fprintf (dump_file, ";; Stabilizing insn ");
    1589                 :          0 :       dump_insn_id (cand->insn);
    1590                 :          0 :       fprintf (dump_file, " by copying source reg %d:%s to temporary reg %d\n",
    1591                 :          0 :                REGNO (src), GET_MODE_NAME (GET_MODE (src)), REGNO (dest));
    1592                 :            :     }
    1593                 :          0 :   emit_insn_before (gen_move_insn (dest, src), cand->insn);
    1594                 :          0 : }
    1595                 :            : 
    1596                 :            : /* Check whether any inputs to candidate CAND_INDEX's instruction could
    1597                 :            :    change at rematerialization points and replace them with new pseudo
    1598                 :            :    registers if so.  */
    1599                 :            : 
    1600                 :            : void
    1601                 :          0 : early_remat::stabilize_pattern (unsigned int cand_index)
    1602                 :            : {
    1603                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1604                 :          0 :   if (cand->stabilized_p)
    1605                 :          0 :     return;
    1606                 :            : 
    1607                 :          0 :   remat_equiv_class *ec = cand->equiv_class;
    1608                 :          0 :   gcc_checking_assert (!ec || cand_index == ec->representative);
    1609                 :            : 
    1610                 :            :   /* Record the replacements we've made so far, so that we don't
    1611                 :            :      create two separate registers for match_dups.  Lookup is O(n),
    1612                 :            :      but the n is very small.  */
    1613                 :          0 :   typedef std::pair<rtx, rtx> reg_pair;
    1614                 :          0 :   auto_vec<reg_pair, 16> reg_map;
    1615                 :            : 
    1616                 :          0 :   rtx_insn *insn = cand->insn;
    1617                 :          0 :   df_ref ref;
    1618                 :          0 :   FOR_EACH_INSN_USE (ref, insn)
    1619                 :            :     {
    1620                 :          0 :       unsigned int old_regno = DF_REF_REGNO (ref);
    1621                 :          0 :       rtx *loc = DF_REF_REAL_LOC (ref);
    1622                 :            : 
    1623                 :          0 :       if (HARD_REGISTER_NUM_P (old_regno) && fixed_regs[old_regno])
    1624                 :            :         {
    1625                 :            :           /* We checked when adding the candidate that the value is stable.  */
    1626                 :          0 :           gcc_checking_assert (!rtx_unstable_p (*loc));
    1627                 :          0 :           continue;
    1628                 :            :         }
    1629                 :            : 
    1630                 :          0 :       if (bitmap_bit_p (&m_candidate_regnos, old_regno))
    1631                 :            :         /* We already know which candidate provides the definition
    1632                 :            :            and will handle it during copying.  */
    1633                 :          0 :         continue;
    1634                 :            : 
    1635                 :          0 :       if (stable_use_p (old_regno))
    1636                 :            :         /* We can continue to use the existing register.  */
    1637                 :          0 :         continue;
    1638                 :            : 
    1639                 :            :       /* We need to replace the register.  See whether we've already
    1640                 :            :          created a suitable copy.  */
    1641                 :          0 :       rtx old_reg = *loc;
    1642                 :          0 :       rtx new_reg = NULL_RTX;
    1643                 :          0 :       machine_mode mode = GET_MODE (old_reg);
    1644                 :          0 :       reg_pair *p;
    1645                 :          0 :       unsigned int pi;
    1646                 :          0 :       FOR_EACH_VEC_ELT (reg_map, pi, p)
    1647                 :          0 :         if (REGNO (p->first) == old_regno
    1648                 :          0 :             && GET_MODE (p->first) == mode)
    1649                 :            :           {
    1650                 :          0 :             new_reg = p->second;
    1651                 :          0 :             break;
    1652                 :            :           }
    1653                 :            : 
    1654                 :          0 :       if (!new_reg)
    1655                 :            :         {
    1656                 :            :           /* Create a new register and initialize it just before
    1657                 :            :              the instruction.  */
    1658                 :          0 :           new_reg = gen_reg_rtx (mode);
    1659                 :          0 :           reg_map.safe_push (reg_pair (old_reg, new_reg));
    1660                 :          0 :           if (ec)
    1661                 :            :             {
    1662                 :          0 :               unsigned int member_index;
    1663                 :          0 :               bitmap_iterator bi;
    1664                 :          0 :               EXECUTE_IF_SET_IN_BITMAP (ec->members, 0, member_index, bi)
    1665                 :          0 :                 emit_copy_before (member_index, new_reg, old_reg);
    1666                 :            :             }
    1667                 :            :           else
    1668                 :          0 :             emit_copy_before (cand_index, new_reg, old_reg);
    1669                 :            :         }
    1670                 :          0 :       validate_change (insn, loc, new_reg, true);
    1671                 :            :     }
    1672                 :          0 :   if (num_changes_pending ())
    1673                 :            :     {
    1674                 :          0 :       if (!apply_change_group ())
    1675                 :            :         /* We checked when adding the candidates that the pattern allows
    1676                 :            :            hard registers to be replaced.  Nothing else should make the
    1677                 :            :            changes invalid.  */
    1678                 :          0 :         gcc_unreachable ();
    1679                 :            : 
    1680                 :          0 :       if (ec)
    1681                 :            :         {
    1682                 :            :           /* Copy the new pattern to other members of the equivalence
    1683                 :            :              class.  */
    1684                 :          0 :           unsigned int member_index;
    1685                 :          0 :           bitmap_iterator bi;
    1686                 :          0 :           EXECUTE_IF_SET_IN_BITMAP (ec->members, 0, member_index, bi)
    1687                 :          0 :             if (cand_index != member_index)
    1688                 :            :               {
    1689                 :          0 :                 rtx_insn *other_insn = m_candidates[member_index].insn;
    1690                 :          0 :                 if (!validate_change (other_insn, &PATTERN (other_insn),
    1691                 :          0 :                                       copy_insn (PATTERN (insn)), 0))
    1692                 :            :                   /* If the original instruction was valid then the copy
    1693                 :            :                      should be too.  */
    1694                 :          0 :                   gcc_unreachable ();
    1695                 :            :               }
    1696                 :            :         }
    1697                 :            :     }
    1698                 :            : 
    1699                 :          0 :   cand->stabilized_p = true;
    1700                 :            : }
    1701                 :            : 
    1702                 :            : /* Change CAND's instruction so that it sets CAND->copy_regno instead
    1703                 :            :    of CAND->regno.  */
    1704                 :            : 
    1705                 :            : void
    1706                 :          0 : early_remat::replace_dest_with_copy (unsigned int cand_index)
    1707                 :            : {
    1708                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1709                 :          0 :   df_ref def;
    1710                 :          0 :   FOR_EACH_INSN_DEF (def, cand->insn)
    1711                 :          0 :     if (DF_REF_REGNO (def) == cand->regno)
    1712                 :          0 :       validate_change (cand->insn, DF_REF_REAL_LOC (def),
    1713                 :          0 :                        regno_reg_rtx[cand->copy_regno], 1);
    1714                 :          0 : }
    1715                 :            : 
    1716                 :            : /* Make sure that the candidates used by candidate CAND_INDEX are available.
    1717                 :            :    There are two ways of doing this for an input candidate I:
    1718                 :            : 
    1719                 :            :    (1) Using the existing register number and ensuring that I is available.
    1720                 :            : 
    1721                 :            :    (2) Using a new register number (recorded in copy_regno) and adding I
    1722                 :            :        to VIA_COPY.  This guarantees that making I available does not
    1723                 :            :        conflict with other uses of the original register.
    1724                 :            : 
    1725                 :            :    REQUIRED is the set of candidates that are required but not available
    1726                 :            :    before the copy of CAND_INDEX.  AVAILABLE is the set of candidates
    1727                 :            :    that are already available before the copy of CAND_INDEX.  REACHING
    1728                 :            :    is the set of candidates that reach the copy of CAND_INDEX.  VIA_COPY
    1729                 :            :    is the set of candidates that will use new register numbers recorded
    1730                 :            :    in copy_regno instead of the original ones.  */
    1731                 :            : 
    1732                 :            : void
    1733                 :          0 : early_remat::stabilize_candidate_uses (unsigned int cand_index,
    1734                 :            :                                        bitmap required, bitmap available,
    1735                 :            :                                        bitmap reaching, bitmap via_copy)
    1736                 :            : {
    1737                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    1738                 :          0 :   df_ref use;
    1739                 :          0 :   FOR_EACH_INSN_USE (use, cand->insn)
    1740                 :            :     {
    1741                 :          0 :       unsigned int regno = DF_REF_REGNO (use);
    1742                 :          0 :       if (!bitmap_bit_p (&m_candidate_regnos, regno))
    1743                 :          0 :         continue;
    1744                 :            : 
    1745                 :            :       /* Work out which candidate provides the definition.  */
    1746                 :          0 :       bitmap defs = m_regno_to_candidates[regno];
    1747                 :          0 :       bitmap_and (&m_tmp_bitmap, cand->uses, defs);
    1748                 :          0 :       gcc_checking_assert (bitmap_single_bit_set_p (&m_tmp_bitmap));
    1749                 :          0 :       unsigned int def_index = bitmap_first_set_bit (&m_tmp_bitmap);
    1750                 :            : 
    1751                 :            :       /* First see if DEF_INDEX is the only reaching definition of REGNO
    1752                 :            :          at this point too and if it is or will become available.  We can
    1753                 :            :          continue to use REGNO if so.  */
    1754                 :          0 :       bitmap_and (&m_tmp_bitmap, reaching, defs);
    1755                 :          0 :       if (bitmap_single_bit_set_p (&m_tmp_bitmap)
    1756                 :          0 :           && bitmap_first_set_bit (&m_tmp_bitmap) == def_index
    1757                 :          0 :           && ((available && bitmap_bit_p (available, def_index))
    1758                 :          0 :               || bitmap_bit_p (required, def_index)))
    1759                 :            :         {
    1760                 :          0 :           if (dump_file)
    1761                 :          0 :             fprintf (dump_file, ";; Keeping reg %d for use of candidate %d"
    1762                 :            :                      " in candidate %d\n", regno, def_index, cand_index);
    1763                 :          0 :           continue;
    1764                 :            :         }
    1765                 :            : 
    1766                 :            :       /* Otherwise fall back to using a copy.  There are other cases
    1767                 :            :          in which we *could* continue to use REGNO, but there's not
    1768                 :            :          really much point.  Using a separate register ought to make
    1769                 :            :          things easier for the register allocator.  */
    1770                 :          0 :       remat_candidate *def_cand = &m_candidates[def_index];
    1771                 :          0 :       rtx *loc = DF_REF_REAL_LOC (use);
    1772                 :          0 :       rtx new_reg;
    1773                 :          0 :       if (bitmap_set_bit (via_copy, def_index))
    1774                 :            :         {
    1775                 :          0 :           new_reg = gen_reg_rtx (GET_MODE (*loc));
    1776                 :          0 :           def_cand->copy_regno = REGNO (new_reg);
    1777                 :          0 :           if (dump_file)
    1778                 :          0 :             fprintf (dump_file, ";; Creating reg %d for use of candidate %d"
    1779                 :            :                      " in candidate %d\n", REGNO (new_reg), def_index,
    1780                 :            :                      cand_index);
    1781                 :            :         }
    1782                 :            :       else
    1783                 :          0 :         new_reg = regno_reg_rtx[def_cand->copy_regno];
    1784                 :          0 :       validate_change (cand->insn, loc, new_reg, 1);
    1785                 :            :     }
    1786                 :          0 : }
    1787                 :            : 
    1788                 :            : /* Rematerialize the candidates in REQUIRED after instruction INSN,
    1789                 :            :    given that the candidates in AVAILABLE are already available
    1790                 :            :    and that REACHING is the set of candidates live after INSN.
    1791                 :            :    REQUIRED and AVAILABLE are disjoint on entry.
    1792                 :            : 
    1793                 :            :    Clear REQUIRED on exit.  */
    1794                 :            : 
    1795                 :            : void
    1796                 :          0 : early_remat::emit_remat_insns (bitmap required, bitmap available,
    1797                 :            :                                bitmap reaching, rtx_insn *insn)
    1798                 :            : {
    1799                 :            :   /* Quick exit if there's nothing to do.  */
    1800                 :          0 :   if (empty_p (required))
    1801                 :          0 :     return;
    1802                 :            : 
    1803                 :            :   /* Only reaching definitions should be available or required.  */
    1804                 :          0 :   gcc_checking_assert (!bitmap_intersect_compl_p (required, reaching));
    1805                 :          0 :   if (available)
    1806                 :          0 :     gcc_checking_assert (!bitmap_intersect_compl_p (available, reaching));
    1807                 :            : 
    1808                 :          0 :   bitmap_head via_copy;
    1809                 :          0 :   bitmap_initialize (&via_copy, &m_obstack);
    1810                 :          0 :   while (!bitmap_empty_p (required) || !bitmap_empty_p (&via_copy))
    1811                 :            :     {
    1812                 :            :       /* Pick the lowest-indexed candidate left.  */
    1813                 :          0 :       unsigned int required_index = (bitmap_empty_p (required)
    1814                 :          0 :                                      ? ~0U : bitmap_first_set_bit (required));
    1815                 :          0 :       unsigned int via_copy_index = (bitmap_empty_p (&via_copy)
    1816                 :          0 :                                      ? ~0U : bitmap_first_set_bit (&via_copy));
    1817                 :          0 :       unsigned int cand_index = MIN (required_index, via_copy_index);
    1818                 :          0 :       remat_candidate *cand = &m_candidates[cand_index];
    1819                 :            : 
    1820                 :          0 :       bool via_copy_p = (cand_index == via_copy_index);
    1821                 :          0 :       if (via_copy_p)
    1822                 :          0 :         bitmap_clear_bit (&via_copy, cand_index);
    1823                 :            :       else
    1824                 :            :         {
    1825                 :            :           /* Remove all candidates for the same register from REQUIRED.  */
    1826                 :          0 :           bitmap_and (&m_tmp_bitmap, reaching,
    1827                 :          0 :                       m_regno_to_candidates[cand->regno]);
    1828                 :          0 :           bitmap_and_compl_into (required, &m_tmp_bitmap);
    1829                 :          0 :           gcc_checking_assert (!bitmap_bit_p (required, cand_index));
    1830                 :            : 
    1831                 :            :           /* Only rematerialize if we have a single reaching definition
    1832                 :            :              of the register.  */
    1833                 :          0 :           if (!bitmap_single_bit_set_p (&m_tmp_bitmap))
    1834                 :            :             {
    1835                 :          0 :               if (dump_file)
    1836                 :            :                 {
    1837                 :          0 :                   fprintf (dump_file, ";; Can't rematerialize reg %d after ",
    1838                 :            :                            cand->regno);
    1839                 :          0 :                   dump_insn_id (insn);
    1840                 :          0 :                   fprintf (dump_file, ": more than one reaching definition\n");
    1841                 :            :                 }
    1842                 :          0 :               continue;
    1843                 :            :             }
    1844                 :            : 
    1845                 :            :           /* Skip candidates that can't be rematerialized.  */
    1846                 :          0 :           if (!cand->can_copy_p)
    1847                 :          0 :             continue;
    1848                 :            : 
    1849                 :            :           /* Check the function precondition.  */
    1850                 :          0 :           gcc_checking_assert (!available
    1851                 :            :                                || !bitmap_bit_p (available, cand_index));
    1852                 :            :         }
    1853                 :            : 
    1854                 :            :       /* Invalid candidates should have been weeded out by now.  */
    1855                 :          0 :       gcc_assert (cand->can_copy_p);
    1856                 :            : 
    1857                 :          0 :       rtx new_pattern;
    1858                 :          0 :       if (cand->constant_p)
    1859                 :            :         {
    1860                 :            :           /* Emit a simple move.  */
    1861                 :          0 :           unsigned int regno = via_copy_p ? cand->copy_regno : cand->regno;
    1862                 :          0 :           new_pattern = gen_move_insn (regno_reg_rtx[regno], cand->remat_rtx);
    1863                 :            :         }
    1864                 :            :       else
    1865                 :            :         {
    1866                 :            :           /* If this is the first time we've copied the instruction, make
    1867                 :            :              sure that any inputs will have the same value after INSN.  */
    1868                 :          0 :           stabilize_pattern (cand_index);
    1869                 :            : 
    1870                 :            :           /* Temporarily adjust the original instruction so that it has
    1871                 :            :              the right form for the copy.  */
    1872                 :          0 :           if (via_copy_p)
    1873                 :          0 :             replace_dest_with_copy (cand_index);
    1874                 :          0 :           if (cand->uses)
    1875                 :          0 :             stabilize_candidate_uses (cand_index, required, available,
    1876                 :            :                                       reaching, &via_copy);
    1877                 :            : 
    1878                 :            :           /* Get the new instruction pattern.  */
    1879                 :          0 :           new_pattern = copy_insn (cand->remat_rtx);
    1880                 :            : 
    1881                 :            :           /* Undo the temporary changes.  */
    1882                 :          0 :           cancel_changes (0);
    1883                 :            :         }
    1884                 :            : 
    1885                 :            :       /* Emit the new instruction.  */
    1886                 :          0 :       rtx_insn *new_insn = emit_insn_after (new_pattern, insn);
    1887                 :            : 
    1888                 :          0 :       if (dump_file)
    1889                 :            :         {
    1890                 :          0 :           fprintf (dump_file, ";; Rematerializing candidate %d after ",
    1891                 :            :                    cand_index);
    1892                 :          0 :           dump_insn_id (insn);
    1893                 :          0 :           if (via_copy_p)
    1894                 :          0 :             fprintf (dump_file, " with new destination reg %d",
    1895                 :            :                      cand->copy_regno);
    1896                 :          0 :           fprintf (dump_file, ":\n\n");
    1897                 :          0 :           print_rtl_single (dump_file, new_insn);
    1898                 :          0 :           fprintf (dump_file, "\n");
    1899                 :            :         }
    1900                 :            :     }
    1901                 :            : }
    1902                 :            : 
    1903                 :            : /* Recompute INFO's available_out set, given that it's distinct from
    1904                 :            :    available_in and available_locally.  */
    1905                 :            : 
    1906                 :            : bool
    1907                 :          0 : early_remat::set_available_out (remat_block_info *info)
    1908                 :            : {
    1909                 :          0 :   if (empty_p (info->available_locally))
    1910                 :          0 :     return bitmap_and_compl (get_bitmap (&info->available_out),
    1911                 :          0 :                              info->available_in, info->rd_kill);
    1912                 :            : 
    1913                 :          0 :   if (empty_p (info->rd_kill))
    1914                 :          0 :     return bitmap_ior (get_bitmap (&info->available_out),
    1915                 :          0 :                        info->available_locally, info->available_in);
    1916                 :            : 
    1917                 :          0 :   return bitmap_ior_and_compl (get_bitmap (&info->available_out),
    1918                 :          0 :                                info->available_locally, info->available_in,
    1919                 :          0 :                                info->rd_kill);
    1920                 :            : }
    1921                 :            : 
    1922                 :            : /* If BB has more than one call, decide which candidates should be
    1923                 :            :    rematerialized after the non-final calls and emit the associated
    1924                 :            :    instructions.  Record other information about the block in preparation
    1925                 :            :    for the global phase.  */
    1926                 :            : 
    1927                 :            : void
    1928                 :          0 : early_remat::process_block (basic_block bb)
    1929                 :            : {
    1930                 :          0 :   remat_block_info *info = &m_block_info[bb->index];
    1931                 :          0 :   rtx_insn *last_call = NULL;
    1932                 :          0 :   rtx_insn *insn;
    1933                 :            : 
    1934                 :            :   /* Ensure that we always use the same candidate index to refer to an
    1935                 :            :      equivalence class.  */
    1936                 :          0 :   if (info->rd_out == info->rd_in)
    1937                 :            :     {
    1938                 :          0 :       canon_bitmap (&info->rd_in);
    1939                 :          0 :       info->rd_out = info->rd_in;
    1940                 :            :     }
    1941                 :            :   else
    1942                 :            :     {
    1943                 :          0 :       canon_bitmap (&info->rd_in);
    1944                 :          0 :       canon_bitmap (&info->rd_out);
    1945                 :            :     }
    1946                 :          0 :   canon_bitmap (&info->rd_kill);
    1947                 :          0 :   canon_bitmap (&info->rd_gen);
    1948                 :            : 
    1949                 :            :   /* The set of candidates that should be rematerialized on entry to the
    1950                 :            :      block or after the previous call (whichever is more recent).  */
    1951                 :          0 :   init_temp_bitmap (&m_required);
    1952                 :            : 
    1953                 :            :   /* The set of candidates that reach the current instruction (i.e. are
    1954                 :            :      live just before the instruction).  */
    1955                 :          0 :   bitmap_head reaching;
    1956                 :          0 :   bitmap_initialize (&reaching, &m_obstack);
    1957                 :          0 :   if (info->rd_in)
    1958                 :          0 :     bitmap_copy (&reaching, info->rd_in);
    1959                 :            : 
    1960                 :            :   /* The set of candidates that are live and available without
    1961                 :            :      rematerialization just before the current instruction.  This only
    1962                 :            :      accounts for earlier candidates in the block, or those that become
    1963                 :            :      available by being added to M_REQUIRED.  */
    1964                 :          0 :   init_temp_bitmap (&m_available);
    1965                 :            : 
    1966                 :            :   /* Get the range of candidates in the block.  */
    1967                 :          0 :   unsigned int next_candidate = info->first_candidate;
    1968                 :          0 :   unsigned int num_candidates = info->num_candidates;
    1969                 :          0 :   remat_candidate *next_def = (num_candidates > 0
    1970                 :          0 :                                ? &m_candidates[next_candidate]
    1971                 :          0 :                                : NULL);
    1972                 :            : 
    1973                 :          0 :   FOR_BB_INSNS (bb, insn)
    1974                 :            :     {
    1975                 :          0 :       if (!NONDEBUG_INSN_P (insn))
    1976                 :          0 :         continue;
    1977                 :            : 
    1978                 :            :       /* First process uses, since this is a forward walk.  */
    1979                 :          0 :       df_ref ref;
    1980                 :          0 :       FOR_EACH_INSN_USE (ref, insn)
    1981                 :            :         {
    1982                 :          0 :           unsigned int regno = DF_REF_REGNO (ref);
    1983                 :          0 :           if (bitmap_bit_p (&m_candidate_regnos, regno))
    1984                 :            :             {
    1985                 :          0 :               bitmap defs = m_regno_to_candidates[regno];
    1986                 :          0 :               bitmap_and (&m_tmp_bitmap, defs, &reaching);
    1987                 :          0 :               gcc_checking_assert (!bitmap_empty_p (&m_tmp_bitmap));
    1988                 :          0 :               if (!bitmap_intersect_p (defs, m_available))
    1989                 :            :                 {
    1990                 :            :                   /* There has been no definition of the register since
    1991                 :            :                      the last call or the start of the block (whichever
    1992                 :            :                      is most recent).  Mark the reaching definitions
    1993                 :            :                      as required at that point and thus available here.  */
    1994                 :          0 :                   bitmap_ior_into (m_required, &m_tmp_bitmap);
    1995                 :          0 :                   bitmap_ior_into (m_available, &m_tmp_bitmap);
    1996                 :            :                 }
    1997                 :            :             }
    1998                 :            :         }
    1999                 :            : 
    2000                 :          0 :       if (CALL_P (insn))
    2001                 :            :         {
    2002                 :          0 :           if (!last_call)
    2003                 :            :             {
    2004                 :            :               /* The first call in the block.  Record which candidates are
    2005                 :            :                  required at the start of the block.  */
    2006                 :          0 :               copy_temp_bitmap (&info->required_in, &m_required);
    2007                 :          0 :               init_temp_bitmap (&m_required);
    2008                 :            :             }
    2009                 :            :           else
    2010                 :            :             {
    2011                 :            :               /* The fully-local case: candidates that need to be
    2012                 :            :                  rematerialized after a previous call in the block.  */
    2013                 :          0 :               restrict_remat_for_call (m_required, last_call);
    2014                 :          0 :               emit_remat_insns (m_required, NULL, info->rd_after_call,
    2015                 :            :                                 last_call);
    2016                 :            :             }
    2017                 :          0 :           last_call = insn;
    2018                 :          0 :           bitmap_clear (m_available);
    2019                 :          0 :           gcc_checking_assert (empty_p (m_required));
    2020                 :            :         }
    2021                 :            : 
    2022                 :            :       /* Now process definitions.  */
    2023                 :          0 :       if (next_def && insn == next_def->insn)
    2024                 :            :         {
    2025                 :          0 :           unsigned int gen = canon_candidate (next_candidate);
    2026                 :            : 
    2027                 :            :           /* Other candidates with the same regno are not available
    2028                 :            :              any more.  */
    2029                 :          0 :           bitmap kill = m_regno_to_candidates[next_def->regno];
    2030                 :          0 :           bitmap_and_compl_into (m_available, kill);
    2031                 :          0 :           bitmap_and_compl_into (&reaching, kill);
    2032                 :            : 
    2033                 :            :           /* Record that this candidate is available without
    2034                 :            :              rematerialization.  */
    2035                 :          0 :           bitmap_set_bit (m_available, gen);
    2036                 :          0 :           bitmap_set_bit (&reaching, gen);
    2037                 :            : 
    2038                 :            :           /* Find the next candidate in the block.  */
    2039                 :          0 :           num_candidates -= 1;
    2040                 :          0 :           next_candidate -= 1;
    2041                 :          0 :           if (num_candidates > 0)
    2042                 :          0 :             next_def -= 1;
    2043                 :            :           else
    2044                 :            :             next_def = NULL;
    2045                 :            :         }
    2046                 :            : 
    2047                 :          0 :       if (insn == last_call)
    2048                 :          0 :         bitmap_copy (get_bitmap (&info->rd_after_call), &reaching);
    2049                 :            :     }
    2050                 :          0 :   bitmap_clear (&reaching);
    2051                 :          0 :   gcc_checking_assert (num_candidates == 0);
    2052                 :            : 
    2053                 :            :   /* Remove values from the available set if they aren't live (and so
    2054                 :            :      aren't interesting to successor blocks).  */
    2055                 :          0 :   if (info->rd_out)
    2056                 :          0 :     bitmap_and_into (m_available, info->rd_out);
    2057                 :            : 
    2058                 :            :   /* Record the accumulated information.  */
    2059                 :          0 :   info->last_call = last_call;
    2060                 :          0 :   info->abnormal_call_p = (last_call
    2061                 :          0 :                            && last_call == BB_END (bb)
    2062                 :          0 :                            && has_abnormal_or_eh_outgoing_edge_p (bb));
    2063                 :          0 :   copy_temp_bitmap (&info->available_locally, &m_available);
    2064                 :          0 :   if (last_call)
    2065                 :          0 :     copy_temp_bitmap (&info->required_after_call, &m_required);
    2066                 :            :   else
    2067                 :          0 :     copy_temp_bitmap (&info->required_in, &m_required);
    2068                 :            : 
    2069                 :            :   /* Assume at first that all live-in values are available without
    2070                 :            :      rematerialization (i.e. start with the most optimistic assumption).  */
    2071                 :          0 :   if (info->available_in)
    2072                 :            :     {
    2073                 :          0 :       if (info->rd_in)
    2074                 :          0 :         bitmap_copy (info->available_in, info->rd_in);
    2075                 :            :       else
    2076                 :          0 :         BITMAP_FREE (info->available_in);
    2077                 :            :     }
    2078                 :            : 
    2079                 :          0 :   if (last_call || empty_p (info->available_in))
    2080                 :            :     /* The values available on exit from the block are exactly those that
    2081                 :            :        are available locally.  This set doesn't change.  */
    2082                 :          0 :     info->available_out = info->available_locally;
    2083                 :          0 :   else if (empty_p (info->available_locally) && empty_p (info->rd_kill))
    2084                 :            :     /* The values available on exit are the same as those available on entry.
    2085                 :            :        Updating one updates the other.  */
    2086                 :          0 :     info->available_out = info->available_in;
    2087                 :            :   else
    2088                 :          0 :     set_available_out (info);
    2089                 :          0 : }
    2090                 :            : 
    2091                 :            : /* Process each block as for process_block, visiting dominators before
    2092                 :            :    the blocks they dominate.  */
    2093                 :            : 
    2094                 :            : void
    2095                 :          0 : early_remat::local_phase (void)
    2096                 :            : {
    2097                 :          0 :   if (dump_file)
    2098                 :          0 :     fprintf (dump_file, "\n;; Local phase:\n");
    2099                 :            : 
    2100                 :          0 :   int *postorder = df_get_postorder (DF_BACKWARD);
    2101                 :          0 :   unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
    2102                 :          0 :   for (unsigned int i = postorder_len; i-- > 0; )
    2103                 :          0 :     if (postorder[i] >= NUM_FIXED_BLOCKS)
    2104                 :          0 :       process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i]));
    2105                 :          0 : }
    2106                 :            : 
    2107                 :            : /* Return true if available values survive across edge E.  */
    2108                 :            : 
    2109                 :            : static inline bool
    2110                 :          0 : available_across_edge_p (edge e)
    2111                 :            : {
    2112                 :          0 :   return (e->flags & EDGE_EH) == 0;
    2113                 :            : }
    2114                 :            : 
    2115                 :            : /* Propagate information from the available_out set of E->src to the
    2116                 :            :    available_in set of E->dest, when computing global availability.
    2117                 :            :    Return true if something changed.  */
    2118                 :            : 
    2119                 :            : bool
    2120                 :          0 : early_remat::avail_confluence_n (edge e)
    2121                 :            : {
    2122                 :          0 :   remat_block_info *src = &er->m_block_info[e->src->index];
    2123                 :          0 :   remat_block_info *dest = &er->m_block_info[e->dest->index];
    2124                 :            : 
    2125                 :          0 :   if (!available_across_edge_p (e))
    2126                 :            :     return false;
    2127                 :            : 
    2128                 :          0 :   if (empty_p (dest->available_in))
    2129                 :            :     return false;
    2130                 :            : 
    2131                 :          0 :   if (!src->available_out)
    2132                 :            :     {
    2133                 :          0 :       bitmap_clear (dest->available_in);
    2134                 :          0 :       return true;
    2135                 :            :     }
    2136                 :            : 
    2137                 :          0 :   return bitmap_and_into (dest->available_in, src->available_out);
    2138                 :            : }
    2139                 :            : 
    2140                 :            : /* Propagate information from the available_in set of block BB_INDEX
    2141                 :            :    to available_out.  Return true if something changed.  */
    2142                 :            : 
    2143                 :            : bool
    2144                 :          0 : early_remat::avail_transfer (int bb_index)
    2145                 :            : {
    2146                 :          0 :   remat_block_info *info = &er->m_block_info[bb_index];
    2147                 :            : 
    2148                 :          0 :   if (info->available_out == info->available_locally)
    2149                 :            :     return false;
    2150                 :            : 
    2151                 :          0 :   if (info->available_out == info->available_in)
    2152                 :            :     /* Assume that we are only called if the input changed.  */
    2153                 :            :     return true;
    2154                 :            : 
    2155                 :          0 :   return er->set_available_out (info);
    2156                 :            : }
    2157                 :            : 
    2158                 :            : /* Compute global availability for the function, starting with the local
    2159                 :            :    information computed by local_phase.  */
    2160                 :            : 
    2161                 :            : void
    2162                 :          0 : early_remat::compute_availability (void)
    2163                 :            : {
    2164                 :            :   /* We use df_simple_dataflow instead of the lcm routines for three reasons:
    2165                 :            : 
    2166                 :            :      (1) it avoids recomputing the traversal order;
    2167                 :            :      (2) many of the sets are likely to be sparse, so we don't necessarily
    2168                 :            :          want to use sbitmaps; and
    2169                 :            :      (3) it means we can avoid creating an explicit kill set for the call.  */
    2170                 :          0 :   er = this;
    2171                 :          0 :   bitmap_clear (&m_tmp_bitmap);
    2172                 :          0 :   bitmap_set_range (&m_tmp_bitmap, 0, last_basic_block_for_fn (m_fn));
    2173                 :          0 :   df_simple_dataflow (DF_FORWARD, NULL, NULL,
    2174                 :            :                       avail_confluence_n, avail_transfer,
    2175                 :            :                       &m_tmp_bitmap, df_get_postorder (DF_FORWARD),
    2176                 :            :                       df_get_n_blocks (DF_FORWARD));
    2177                 :          0 :   er = 0;
    2178                 :            : 
    2179                 :            :   /* Restrict the required_in sets to values that aren't available.  */
    2180                 :          0 :   basic_block bb;
    2181                 :          0 :   FOR_EACH_BB_FN (bb, m_fn)
    2182                 :            :     {
    2183                 :          0 :       remat_block_info *info = &m_block_info[bb->index];
    2184                 :          0 :       if (info->required_in && info->available_in)
    2185                 :          0 :         bitmap_and_compl_into (info->required_in, info->available_in);
    2186                 :            :     }
    2187                 :          0 : }
    2188                 :            : 
    2189                 :            : /* Make sure that INFO's available_out and available_in sets are unique.  */
    2190                 :            : 
    2191                 :            : inline void
    2192                 :            : early_remat::unshare_available_sets (remat_block_info *info)
    2193                 :            : {
    2194                 :            :   if (info->available_in && info->available_in == info->available_out)
    2195                 :            :     {
    2196                 :            :       info->available_in = alloc_bitmap ();
    2197                 :            :       bitmap_copy (info->available_in, info->available_out);
    2198                 :            :     }
    2199                 :            : }
    2200                 :            : 
    2201                 :            : /* Return true if it is possible to move rematerializations from the
    2202                 :            :    destination of E to the source of E.  */
    2203                 :            : 
    2204                 :            : inline bool
    2205                 :          0 : early_remat::can_move_across_edge_p (edge e)
    2206                 :            : {
    2207                 :          0 :   return (available_across_edge_p (e)
    2208                 :          0 :           && !m_block_info[e->src->index].abnormal_call_p);
    2209                 :            : }
    2210                 :            : 
    2211                 :            : /* Return true if it is cheaper to rematerialize values at the head of
    2212                 :            :    block QUERY_BB_INDEX instead of rematerializing in its predecessors.  */
    2213                 :            : 
    2214                 :            : bool
    2215                 :          0 : early_remat::local_remat_cheaper_p (unsigned int query_bb_index)
    2216                 :            : {
    2217                 :          0 :   if (m_block_info[query_bb_index].remat_frequency_valid_p)
    2218                 :          0 :     return m_block_info[query_bb_index].local_remat_cheaper_p;
    2219                 :            : 
    2220                 :            :   /* Iteratively compute the cost of rematerializing values in the
    2221                 :            :      predecessor blocks, then compare that with the cost of
    2222                 :            :      rematerializing at the head of the block.
    2223                 :            : 
    2224                 :            :      A cycle indicates that there is no call on that execution path,
    2225                 :            :      so it isn't necessary to rematerialize on that path.  */
    2226                 :          0 :   auto_vec<basic_block, 16> stack;
    2227                 :          0 :   stack.quick_push (BASIC_BLOCK_FOR_FN (m_fn, query_bb_index));
    2228                 :          0 :   while (!stack.is_empty ())
    2229                 :            :     {
    2230                 :          0 :       basic_block bb = stack.last ();
    2231                 :          0 :       remat_block_info *info = &m_block_info[bb->index];
    2232                 :          0 :       if (info->remat_frequency_valid_p)
    2233                 :            :         {
    2234                 :          0 :           stack.pop ();
    2235                 :          0 :           continue;
    2236                 :            :         }
    2237                 :            : 
    2238                 :          0 :       info->visited_p = true;
    2239                 :          0 :       int frequency = 0;
    2240                 :          0 :       bool can_move_p = true;
    2241                 :          0 :       edge e;
    2242                 :          0 :       edge_iterator ei;
    2243                 :          0 :       FOR_EACH_EDGE (e, ei, bb->preds)
    2244                 :          0 :         if (!can_move_across_edge_p (e))
    2245                 :            :           {
    2246                 :            :             can_move_p = false;
    2247                 :            :             break;
    2248                 :            :           }
    2249                 :          0 :         else if (m_block_info[e->src->index].last_call)
    2250                 :            :           /* We'll rematerialize after the call.  */
    2251                 :          0 :           frequency += e->src->count.to_frequency (m_fn);
    2252                 :          0 :         else if (m_block_info[e->src->index].remat_frequency_valid_p)
    2253                 :            :           /* Add the cost of rematerializing at the head of E->src
    2254                 :            :              or in its predecessors (whichever is cheaper).  */
    2255                 :          0 :           frequency += m_block_info[e->src->index].remat_frequency;
    2256                 :          0 :         else if (!m_block_info[e->src->index].visited_p)
    2257                 :            :           /* Queue E->src and then revisit this block again.  */
    2258                 :          0 :           stack.safe_push (e->src);
    2259                 :            : 
    2260                 :            :       /* Come back to this block later if we need to process some of
    2261                 :            :          its predecessors.  */
    2262                 :          0 :       if (stack.last () != bb)
    2263                 :          0 :         continue;
    2264                 :            : 
    2265                 :            :       /* If rematerializing in and before the block have equal cost, prefer
    2266                 :            :          rematerializing in the block.  This should shorten the live range.  */
    2267                 :          0 :       int bb_frequency = bb->count.to_frequency (m_fn);
    2268                 :          0 :       if (!can_move_p || frequency >= bb_frequency)
    2269                 :            :         {
    2270                 :          0 :           info->local_remat_cheaper_p = true;
    2271                 :          0 :           info->remat_frequency = bb_frequency;
    2272                 :            :         }
    2273                 :            :       else
    2274                 :          0 :         info->remat_frequency = frequency;
    2275                 :          0 :       info->remat_frequency_valid_p = true;
    2276                 :          0 :       info->visited_p = false;
    2277                 :          0 :       if (dump_file)
    2278                 :            :         {
    2279                 :          0 :           if (!can_move_p)
    2280                 :          0 :             fprintf (dump_file, ";; Need to rematerialize at the head of"
    2281                 :            :                      " block %d; cannot move to predecessors.\n", bb->index);
    2282                 :            :           else
    2283                 :            :             {
    2284                 :          0 :               fprintf (dump_file, ";; Block %d has frequency %d,"
    2285                 :            :                        " rematerializing in predecessors has frequency %d",
    2286                 :            :                        bb->index, bb_frequency, frequency);
    2287                 :          0 :               if (info->local_remat_cheaper_p)
    2288                 :          0 :                 fprintf (dump_file, "; prefer to rematerialize"
    2289                 :            :                          " in the block\n");
    2290                 :            :               else
    2291                 :          0 :                 fprintf (dump_file, "; prefer to rematerialize"
    2292                 :            :                          " in predecessors\n");
    2293                 :            :             }
    2294                 :            :         }
    2295                 :          0 :       stack.pop ();
    2296                 :            :     }
    2297                 :          0 :   return m_block_info[query_bb_index].local_remat_cheaper_p;
    2298                 :            : }
    2299                 :            : 
    2300                 :            : /* Return true if we cannot rematerialize candidate CAND_INDEX at the head of
    2301                 :            :    block BB_INDEX.  */
    2302                 :            : 
    2303                 :            : bool
    2304                 :          0 : early_remat::need_to_move_candidate_p (unsigned int bb_index,
    2305                 :            :                                        unsigned int cand_index)
    2306                 :            : {
    2307                 :          0 :   remat_block_info *info = &m_block_info[bb_index];
    2308                 :          0 :   remat_candidate *cand = &m_candidates[cand_index];
    2309                 :          0 :   basic_block bb = BASIC_BLOCK_FOR_FN (m_fn, bb_index);
    2310                 :            : 
    2311                 :            :   /* If there is more than one reaching definition of REGNO,
    2312                 :            :      we'll need to rematerialize in predecessors instead.  */
    2313                 :          0 :   bitmap_and (&m_tmp_bitmap, info->rd_in, m_regno_to_candidates[cand->regno]);
    2314                 :          0 :   if (!bitmap_single_bit_set_p (&m_tmp_bitmap))
    2315                 :            :     {
    2316                 :          0 :       if (dump_file)
    2317                 :          0 :         fprintf (dump_file, ";; Cannot rematerialize %d at the"
    2318                 :            :                  " head of block %d because there is more than one"
    2319                 :            :                  " reaching definition of reg %d\n", cand_index,
    2320                 :            :                  bb_index, cand->regno);
    2321                 :          0 :       return true;
    2322                 :            :     }
    2323                 :            : 
    2324                 :            :   /* Likewise if rematerializing CAND here would clobber a live register.  */
    2325                 :          0 :   if (cand->clobbers
    2326                 :          0 :       && bitmap_intersect_p (cand->clobbers, DF_LR_IN (bb)))
    2327                 :            :     {
    2328                 :          0 :       if (dump_file)
    2329                 :          0 :         fprintf (dump_file, ";; Cannot rematerialize %d at the"
    2330                 :            :                  " head of block %d because it would clobber live"
    2331                 :            :                  " registers\n", cand_index, bb_index);
    2332                 :          0 :       return true;
    2333                 :            :     }
    2334                 :            : 
    2335                 :            :   return false;
    2336                 :            : }
    2337                 :            : 
    2338                 :            : /* Set REQUIRED to the minimum set of candidates that must be rematerialized
    2339                 :            :    in predecessors of block BB_INDEX instead of at the start of the block.  */
    2340                 :            : 
    2341                 :            : void
    2342                 :          0 : early_remat::compute_minimum_move_set (unsigned int bb_index,
    2343                 :            :                                        bitmap required)
    2344                 :            : {
    2345                 :          0 :   remat_block_info *info = &m_block_info[bb_index];
    2346                 :          0 :   bitmap_head remaining;
    2347                 :            : 
    2348                 :          0 :   bitmap_clear (required);
    2349                 :          0 :   bitmap_initialize (&remaining, &m_obstack);
    2350                 :          0 :   bitmap_copy (&remaining, info->required_in);
    2351                 :          0 :   while (!bitmap_empty_p (&remaining))
    2352                 :            :     {
    2353                 :          0 :       unsigned int cand_index = bitmap_first_set_bit (&remaining);
    2354                 :          0 :       remat_candidate *cand = &m_candidates[cand_index];
    2355                 :          0 :       bitmap_clear_bit (&remaining, cand_index);
    2356                 :            : 
    2357                 :            :       /* Leave invalid candidates where they are.  */
    2358                 :          0 :       if (!cand->can_copy_p)
    2359                 :          0 :         continue;
    2360                 :            : 
    2361                 :            :       /* Decide whether to move this candidate.  */
    2362                 :          0 :       if (!bitmap_bit_p (required, cand_index))
    2363                 :            :         {
    2364                 :          0 :           if (!need_to_move_candidate_p (bb_index, cand_index))
    2365                 :          0 :             continue;
    2366                 :          0 :           bitmap_set_bit (required, cand_index);
    2367                 :            :         }
    2368                 :            : 
    2369                 :            :       /* Also move values used by the candidate, so that we don't
    2370                 :            :          rematerialize them twice.  */
    2371                 :          0 :       if (cand->uses)
    2372                 :            :         {
    2373                 :          0 :           bitmap_ior_and_into (required, cand->uses, info->required_in);
    2374                 :          0 :           bitmap_ior_and_into (&remaining, cand->uses, info->required_in);
    2375                 :            :         }
    2376                 :            :     }
    2377                 :          0 : }
    2378                 :            : 
    2379                 :            : /* Make the predecessors of BB_INDEX rematerialize the candidates in
    2380                 :            :    REQUIRED.  Add any blocks whose required_in set changes to
    2381                 :            :    PENDING_BLOCKS.  */
    2382                 :            : 
    2383                 :            : void
    2384                 :          0 : early_remat::move_to_predecessors (unsigned int bb_index, bitmap required,
    2385                 :            :                                    bitmap pending_blocks)
    2386                 :            : {
    2387                 :          0 :   if (empty_p (required))
    2388                 :          0 :     return;
    2389                 :          0 :   remat_block_info *dest_info = &m_block_info[bb_index];
    2390                 :          0 :   basic_block bb = BASIC_BLOCK_FOR_FN (m_fn, bb_index);
    2391                 :          0 :   edge e;
    2392                 :          0 :   edge_iterator ei;
    2393                 :          0 :   FOR_EACH_EDGE (e, ei, bb->preds)
    2394                 :            :     {
    2395                 :          0 :       remat_block_info *src_info = &m_block_info[e->src->index];
    2396                 :            : 
    2397                 :            :       /* Restrict the set we add to the reaching definitions.  */
    2398                 :          0 :       bitmap_and (&m_tmp_bitmap, required, src_info->rd_out);
    2399                 :          0 :       if (bitmap_empty_p (&m_tmp_bitmap))
    2400                 :          0 :         continue;
    2401                 :            : 
    2402                 :          0 :       if (!can_move_across_edge_p (e))
    2403                 :            :         {
    2404                 :            :           /* We can't move the rematerialization and we can't do it at
    2405                 :            :              the start of the block either.  In this case we just give up
    2406                 :            :              and rely on spilling to make the values available across E.  */
    2407                 :          0 :           if (dump_file)
    2408                 :            :             {
    2409                 :          0 :               fprintf (dump_file, ";; Cannot rematerialize the following"
    2410                 :          0 :                        " candidates in block %d:", e->src->index);
    2411                 :          0 :               dump_candidate_bitmap (required);
    2412                 :          0 :               fprintf (dump_file, "\n");
    2413                 :            :             }
    2414                 :          0 :           continue;
    2415                 :            :         }
    2416                 :            : 
    2417                 :            :       /* Remove candidates that are already available.  */
    2418                 :          0 :       if (src_info->available_out)
    2419                 :            :         {
    2420                 :          0 :           bitmap_and_compl_into (&m_tmp_bitmap, src_info->available_out);
    2421                 :          0 :           if (bitmap_empty_p (&m_tmp_bitmap))
    2422                 :          0 :             continue;
    2423                 :            :         }
    2424                 :            : 
    2425                 :            :       /* Add the remaining candidates to the appropriate required set.  */
    2426                 :          0 :       if (dump_file)
    2427                 :            :         {
    2428                 :          0 :           fprintf (dump_file, ";; Moving this set from block %d"
    2429                 :          0 :                    " to block %d:", bb_index, e->src->index);
    2430                 :          0 :           dump_candidate_bitmap (&m_tmp_bitmap);
    2431                 :          0 :           fprintf (dump_file, "\n");
    2432                 :            :         }
    2433                 :            :       /* If the source block contains a call, we want to rematerialize
    2434                 :            :          after the call, otherwise we want to rematerialize at the start
    2435                 :            :          of the block.  */
    2436                 :          0 :       bitmap src_required = get_bitmap (src_info->last_call
    2437                 :            :                                         ? &src_info->required_after_call
    2438                 :            :                                         : &src_info->required_in);
    2439                 :          0 :       if (bitmap_ior_into (src_required, &m_tmp_bitmap))
    2440                 :            :         {
    2441                 :          0 :           if (!src_info->last_call)
    2442                 :          0 :             bitmap_set_bit (pending_blocks, e->src->index);
    2443                 :          0 :           unshare_available_sets (src_info);
    2444                 :          0 :           bitmap_ior_into (get_bitmap (&src_info->available_out),
    2445                 :            :                            &m_tmp_bitmap);
    2446                 :            :         }
    2447                 :            :     }
    2448                 :            : 
    2449                 :            :   /* The candidates are now available on entry to the block.  */
    2450                 :          0 :   bitmap_and_compl_into (dest_info->required_in, required);
    2451                 :          0 :   unshare_available_sets (dest_info);
    2452                 :          0 :   bitmap_ior_into (get_bitmap (&dest_info->available_in), required);
    2453                 :            : }
    2454                 :            : 
    2455                 :            : /* Go through the candidates that are currently marked as being
    2456                 :            :    rematerialized at the beginning of a block.  Decide in each case
    2457                 :            :    whether that's valid and profitable; if it isn't, move the
    2458                 :            :    rematerialization to predecessor blocks instead.  */
    2459                 :            : 
    2460                 :            : void
    2461                 :          0 : early_remat::choose_rematerialization_points (void)
    2462                 :            : {
    2463                 :          0 :   bitmap_head required;
    2464                 :          0 :   bitmap_head pending_blocks;
    2465                 :            : 
    2466                 :          0 :   int *postorder = df_get_postorder (DF_BACKWARD);
    2467                 :          0 :   unsigned int postorder_len = df_get_n_blocks (DF_BACKWARD);
    2468                 :          0 :   bitmap_initialize (&required, &m_obstack);
    2469                 :          0 :   bitmap_initialize (&pending_blocks, &m_obstack);
    2470                 :          0 :   do
    2471                 :            :     /* Process the blocks in postorder, to reduce the number of iterations
    2472                 :            :        of the outer loop.  */
    2473                 :          0 :     for (unsigned int i = 0; i < postorder_len; ++i)
    2474                 :            :       {
    2475                 :          0 :         unsigned int bb_index = postorder[i];
    2476                 :          0 :         remat_block_info *info = &m_block_info[bb_index];
    2477                 :          0 :         bitmap_clear_bit (&pending_blocks, bb_index);
    2478                 :            : 
    2479                 :          0 :         if (empty_p (info->required_in))
    2480                 :          0 :           continue;
    2481                 :            : 
    2482                 :          0 :         if (info->available_in)
    2483                 :          0 :           gcc_checking_assert (!bitmap_intersect_p (info->required_in,
    2484                 :            :                                                     info->available_in));
    2485                 :            : 
    2486                 :          0 :         if (local_remat_cheaper_p (bb_index))
    2487                 :            :           {
    2488                 :            :             /* We'd prefer to rematerialize at the head of the block.
    2489                 :            :                Only move candidates if we need to.  */
    2490                 :          0 :             compute_minimum_move_set (bb_index, &required);
    2491                 :          0 :             move_to_predecessors (bb_index, &required, &pending_blocks);
    2492                 :            :           }
    2493                 :            :         else
    2494                 :          0 :           move_to_predecessors (bb_index, info->required_in,
    2495                 :            :                                 &pending_blocks);
    2496                 :            :       }
    2497                 :          0 :   while (!bitmap_empty_p (&pending_blocks));
    2498                 :          0 :   bitmap_clear (&required);
    2499                 :          0 : }
    2500                 :            : 
    2501                 :            : /* Emit all rematerialization instructions queued for BB.  */
    2502                 :            : 
    2503                 :            : void
    2504                 :          0 : early_remat::emit_remat_insns_for_block (basic_block bb)
    2505                 :            : {
    2506                 :          0 :   remat_block_info *info = &m_block_info[bb->index];
    2507                 :            : 
    2508                 :          0 :   if (info->last_call && !empty_p (info->required_after_call))
    2509                 :            :     {
    2510                 :          0 :       restrict_remat_for_call (info->required_after_call, info->last_call);
    2511                 :          0 :       emit_remat_insns (info->required_after_call, NULL,
    2512                 :            :                         info->rd_after_call, info->last_call);
    2513                 :            :     }
    2514                 :            : 
    2515                 :          0 :   if (!empty_p (info->required_in))
    2516                 :            :     {
    2517                 :          0 :       rtx_insn *insn = BB_HEAD (bb);
    2518                 :          0 :       while (insn != BB_END (bb)
    2519                 :          0 :              && !INSN_P (NEXT_INSN (insn)))
    2520                 :          0 :         insn = NEXT_INSN (insn);
    2521                 :          0 :       restrict_remat_for_unavail_regs (info->required_in, DF_LR_IN (bb));
    2522                 :          0 :       emit_remat_insns (info->required_in, info->available_in,
    2523                 :            :                         info->rd_in, insn);
    2524                 :            :     }
    2525                 :          0 : }
    2526                 :            : 
    2527                 :            : /* Decide which candidates in each block's REQUIRED_IN set need to be
    2528                 :            :    rematerialized and decide where the rematerialization instructions
    2529                 :            :    should go.  Emit queued rematerialization instructions at the start
    2530                 :            :    of blocks and after the last calls in blocks.  */
    2531                 :            : 
    2532                 :            : void
    2533                 :          0 : early_remat::global_phase (void)
    2534                 :            : {
    2535                 :          0 :   compute_availability ();
    2536                 :          0 :   if (dump_file)
    2537                 :            :     {
    2538                 :          0 :       fprintf (dump_file, "\n;; Blocks after computing global"
    2539                 :            :                " availability:\n");
    2540                 :          0 :       dump_all_blocks ();
    2541                 :            :     }
    2542                 :            : 
    2543                 :          0 :   choose_rematerialization_points ();
    2544                 :          0 :   if (dump_file)
    2545                 :            :     {
    2546                 :          0 :       fprintf (dump_file, "\n;; Blocks after choosing rematerialization"
    2547                 :            :                " points:\n");
    2548                 :          0 :       dump_all_blocks ();
    2549                 :            :     }
    2550                 :            : 
    2551                 :          0 :   basic_block bb;
    2552                 :          0 :   FOR_EACH_BB_FN (bb, m_fn)
    2553                 :          0 :     emit_remat_insns_for_block (bb);
    2554                 :          0 : }
    2555                 :            : 
    2556                 :            : /* Main function for the pass.  */
    2557                 :            : 
    2558                 :            : void
    2559                 :          0 : early_remat::run (void)
    2560                 :            : {
    2561                 :          0 :   df_analyze ();
    2562                 :            : 
    2563                 :          0 :   if (!collect_candidates ())
    2564                 :            :     return;
    2565                 :            : 
    2566                 :          0 :   init_block_info ();
    2567                 :          0 :   sort_candidates ();
    2568                 :          0 :   finalize_candidate_indices ();
    2569                 :          0 :   if (dump_file)
    2570                 :          0 :     dump_all_candidates ();
    2571                 :            : 
    2572                 :          0 :   compute_rd ();
    2573                 :          0 :   decide_candidate_validity ();
    2574                 :          0 :   local_phase ();
    2575                 :          0 :   global_phase ();
    2576                 :            : }
    2577                 :            : 
    2578                 :          0 : early_remat::early_remat (function *fn, sbitmap selected_modes)
    2579                 :            :   : m_fn (fn),
    2580                 :            :     m_selected_modes (selected_modes),
    2581                 :            :     m_available (0),
    2582                 :            :     m_required (0),
    2583                 :          0 :     m_value_table (63)
    2584                 :            : {
    2585                 :          0 :   bitmap_obstack_initialize (&m_obstack);
    2586                 :          0 :   bitmap_initialize (&m_candidate_regnos, &m_obstack);
    2587                 :          0 :   bitmap_initialize (&m_tmp_bitmap, &m_obstack);
    2588                 :          0 : }
    2589                 :            : 
    2590                 :          0 : early_remat::~early_remat ()
    2591                 :            : {
    2592                 :          0 :   bitmap_obstack_release (&m_obstack);
    2593                 :          0 : }
    2594                 :            : 
    2595                 :            : namespace {
    2596                 :            : 
    2597                 :            : const pass_data pass_data_early_remat =
    2598                 :            : {
    2599                 :            :   RTL_PASS, /* type */
    2600                 :            :   "early_remat", /* name */
    2601                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    2602                 :            :   TV_EARLY_REMAT, /* tv_id */
    2603                 :            :   0, /* properties_required */
    2604                 :            :   0, /* properties_provided */
    2605                 :            :   0, /* properties_destroyed */
    2606                 :            :   0, /* todo_flags_start */
    2607                 :            :   TODO_df_finish, /* todo_flags_finish */
    2608                 :            : };
    2609                 :            : 
    2610                 :            : class pass_early_remat : public rtl_opt_pass
    2611                 :            : {
    2612                 :            : public:
    2613                 :     200773 :   pass_early_remat (gcc::context *ctxt)
    2614                 :     401546 :     : rtl_opt_pass (pass_data_early_remat, ctxt)
    2615                 :            :   {}
    2616                 :            : 
    2617                 :            :   /* opt_pass methods: */
    2618                 :     944101 :   virtual bool gate (function *)
    2619                 :            :   {
    2620                 :     944101 :     return optimize > 1 && NUM_POLY_INT_COEFFS > 1;
    2621                 :            :   }
    2622                 :            : 
    2623                 :          0 :   virtual unsigned int execute (function *f)
    2624                 :            :   {
    2625                 :          0 :     auto_sbitmap selected_modes (NUM_MACHINE_MODES);
    2626                 :          0 :     bitmap_clear (selected_modes);
    2627                 :          0 :     targetm.select_early_remat_modes (selected_modes);
    2628                 :          0 :     if (!bitmap_empty_p (selected_modes))
    2629                 :          0 :       early_remat (f, selected_modes).run ();
    2630                 :          0 :     return 0;
    2631                 :            :   }
    2632                 :            : }; // class pass_early_remat
    2633                 :            : 
    2634                 :            : } // anon namespace
    2635                 :            : 
    2636                 :            : rtl_opt_pass *
    2637                 :     200773 : make_pass_early_remat (gcc::context *ctxt)
    2638                 :            : {
    2639                 :     200773 :   return new pass_early_remat (ctxt);
    2640                 :            : }

Generated by: LCOV version 1.0

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 --enable-host-shared. GCC test suite is run with the built compiler.