LCOV - code coverage report
Current view: top level - gcc - cprop.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 675 726 93.0 %
Date: 2020-03-28 11:57:23 Functions: 37 45 82.2 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Global constant/copy propagation for RTL.
       2                 :            :    Copyright (C) 1997-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 "cfghooks.h"
      26                 :            : #include "df.h"
      27                 :            : #include "insn-config.h"
      28                 :            : #include "memmodel.h"
      29                 :            : #include "emit-rtl.h"
      30                 :            : #include "recog.h"
      31                 :            : #include "diagnostic-core.h"
      32                 :            : #include "toplev.h"
      33                 :            : #include "cfgrtl.h"
      34                 :            : #include "cfganal.h"
      35                 :            : #include "lcm.h"
      36                 :            : #include "cfgcleanup.h"
      37                 :            : #include "cselib.h"
      38                 :            : #include "intl.h"
      39                 :            : #include "tree-pass.h"
      40                 :            : #include "dbgcnt.h"
      41                 :            : #include "cfgloop.h"
      42                 :            : #include "gcse.h"
      43                 :            : 
      44                 :            : 
      45                 :            : /* An obstack for our working variables.  */
      46                 :            : static struct obstack cprop_obstack;
      47                 :            : 
      48                 :            : /* Occurrence of an expression.
      49                 :            :    There is one per basic block.  If a pattern appears more than once the
      50                 :            :    last appearance is used.  */
      51                 :            : 
      52                 :            : struct cprop_occr
      53                 :            : {
      54                 :            :   /* Next occurrence of this expression.  */
      55                 :            :   struct cprop_occr *next;
      56                 :            :   /* The insn that computes the expression.  */
      57                 :            :   rtx_insn *insn;
      58                 :            : };
      59                 :            : 
      60                 :            : /* Hash table entry for assignment expressions.  */
      61                 :            : 
      62                 :            : struct cprop_expr
      63                 :            : {
      64                 :            :   /* The expression (DEST := SRC).  */
      65                 :            :   rtx dest;
      66                 :            :   rtx src;
      67                 :            : 
      68                 :            :   /* Index in the available expression bitmaps.  */
      69                 :            :   int bitmap_index;
      70                 :            :   /* Next entry with the same hash.  */
      71                 :            :   struct cprop_expr *next_same_hash;
      72                 :            :   /* List of available occurrence in basic blocks in the function.
      73                 :            :      An "available occurrence" is one that is the last occurrence in the
      74                 :            :      basic block and whose operands are not modified by following statements
      75                 :            :      in the basic block [including this insn].  */
      76                 :            :   struct cprop_occr *avail_occr;
      77                 :            : };
      78                 :            : 
      79                 :            : /* Hash table for copy propagation expressions.
      80                 :            :    Each hash table is an array of buckets.
      81                 :            :    ??? It is known that if it were an array of entries, structure elements
      82                 :            :    `next_same_hash' and `bitmap_index' wouldn't be necessary.  However, it is
      83                 :            :    not clear whether in the final analysis a sufficient amount of memory would
      84                 :            :    be saved as the size of the available expression bitmaps would be larger
      85                 :            :    [one could build a mapping table without holes afterwards though].
      86                 :            :    Someday I'll perform the computation and figure it out.  */
      87                 :            : 
      88                 :            : struct hash_table_d
      89                 :            : {
      90                 :            :   /* The table itself.
      91                 :            :      This is an array of `set_hash_table_size' elements.  */
      92                 :            :   struct cprop_expr **table;
      93                 :            : 
      94                 :            :   /* Size of the hash table, in elements.  */
      95                 :            :   unsigned int size;
      96                 :            : 
      97                 :            :   /* Number of hash table elements.  */
      98                 :            :   unsigned int n_elems;
      99                 :            : };
     100                 :            : 
     101                 :            : /* Copy propagation hash table.  */
     102                 :            : static struct hash_table_d set_hash_table;
     103                 :            : 
     104                 :            : /* Array of implicit set patterns indexed by basic block index.  */
     105                 :            : static rtx *implicit_sets;
     106                 :            : 
     107                 :            : /* Array of indexes of expressions for implicit set patterns indexed by basic
     108                 :            :    block index.  In other words, implicit_set_indexes[i] is the bitmap_index
     109                 :            :    of the expression whose RTX is implicit_sets[i].  */
     110                 :            : static int *implicit_set_indexes;
     111                 :            : 
     112                 :            : /* Bitmap containing one bit for each register in the program.
     113                 :            :    Used when performing GCSE to track which registers have been set since
     114                 :            :    the start or end of the basic block while traversing that block.  */
     115                 :            : static regset reg_set_bitmap;
     116                 :            : 
     117                 :            : /* Various variables for statistics gathering.  */
     118                 :            : 
     119                 :            : /* Memory used in a pass.
     120                 :            :    This isn't intended to be absolutely precise.  Its intent is only
     121                 :            :    to keep an eye on memory usage.  */
     122                 :            : static int bytes_used;
     123                 :            : 
     124                 :            : /* Number of local constants propagated.  */
     125                 :            : static int local_const_prop_count;
     126                 :            : /* Number of local copies propagated.  */
     127                 :            : static int local_copy_prop_count;
     128                 :            : /* Number of global constants propagated.  */
     129                 :            : static int global_const_prop_count;
     130                 :            : /* Number of global copies propagated.  */
     131                 :            : static int global_copy_prop_count;
     132                 :            : 
     133                 :            : #define GOBNEW(T)               ((T *) cprop_alloc (sizeof (T)))
     134                 :            : #define GOBNEWVAR(T, S)         ((T *) cprop_alloc ((S)))
     135                 :            : 
     136                 :            : /* Cover function to obstack_alloc.  */
     137                 :            : 
     138                 :            : static void *
     139                 :   17244400 : cprop_alloc (unsigned long size)
     140                 :            : {
     141                 :   17244400 :   bytes_used += size;
     142                 :   17244400 :   return obstack_alloc (&cprop_obstack, size);
     143                 :            : }
     144                 :            : 
     145                 :            : /* Return nonzero if register X is unchanged from INSN to the end
     146                 :            :    of INSN's basic block.  */
     147                 :            : 
     148                 :            : static int
     149                 :   42187600 : reg_available_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
     150                 :            : {
     151                 :    1682380 :   return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
     152                 :            : }
     153                 :            : 
     154                 :            : /* Hash a set of register REGNO.
     155                 :            : 
     156                 :            :    Sets are hashed on the register that is set.  This simplifies the PRE copy
     157                 :            :    propagation code.
     158                 :            : 
     159                 :            :    ??? May need to make things more elaborate.  Later, as necessary.  */
     160                 :            : 
     161                 :            : static unsigned int
     162                 :   69636700 : hash_mod (int regno, int hash_table_size)
     163                 :            : {
     164                 :   69636700 :   return (unsigned) regno % hash_table_size;
     165                 :            : }
     166                 :            : 
     167                 :            : /* Insert assignment DEST:=SET from INSN in the hash table.
     168                 :            :    DEST is a register and SET is a register or a suitable constant.
     169                 :            :    If the assignment is already present in the table, record it as
     170                 :            :    the last occurrence in INSN's basic block.
     171                 :            :    IMPLICIT is true if it's an implicit set, false otherwise.  */
     172                 :            : 
     173                 :            : static void
     174                 :    9082760 : insert_set_in_table (rtx dest, rtx src, rtx_insn *insn,
     175                 :            :                      struct hash_table_d *table, bool implicit)
     176                 :            : {
     177                 :    9082760 :   bool found = false;
     178                 :    9082760 :   unsigned int hash;
     179                 :    9082760 :   struct cprop_expr *cur_expr, *last_expr = NULL;
     180                 :    9082760 :   struct cprop_occr *cur_occr;
     181                 :            : 
     182                 :    9082760 :   hash = hash_mod (REGNO (dest), table->size);
     183                 :            : 
     184                 :   12600200 :   for (cur_expr = table->table[hash]; cur_expr;
     185                 :    3517410 :        cur_expr = cur_expr->next_same_hash)
     186                 :            :     {
     187                 :    4438510 :       if (dest == cur_expr->dest
     188                 :    4143310 :           && src == cur_expr->src)
     189                 :            :         {
     190                 :            :           found = true;
     191                 :            :           break;
     192                 :            :         }
     193                 :    3517410 :       last_expr = cur_expr;
     194                 :            :     }
     195                 :            : 
     196                 :    9082760 :   if (! found)
     197                 :            :     {
     198                 :    8161660 :       cur_expr = GOBNEW (struct cprop_expr);
     199                 :    8161660 :       bytes_used += sizeof (struct cprop_expr);
     200                 :    8161660 :       if (table->table[hash] == NULL)
     201                 :            :         /* This is the first pattern that hashed to this index.  */
     202                 :    6536490 :         table->table[hash] = cur_expr;
     203                 :            :       else
     204                 :            :         /* Add EXPR to end of this hash chain.  */
     205                 :    1625170 :         last_expr->next_same_hash = cur_expr;
     206                 :            : 
     207                 :            :       /* Set the fields of the expr element.
     208                 :            :          We must copy X because it can be modified when copy propagation is
     209                 :            :          performed on its operands.  */
     210                 :    8161660 :       cur_expr->dest = copy_rtx (dest);
     211                 :    8161660 :       cur_expr->src = copy_rtx (src);
     212                 :    8161660 :       cur_expr->bitmap_index = table->n_elems++;
     213                 :    8161660 :       cur_expr->next_same_hash = NULL;
     214                 :    8161660 :       cur_expr->avail_occr = NULL;
     215                 :            :     }
     216                 :            : 
     217                 :            :   /* Now record the occurrence.  */
     218                 :    9082760 :   cur_occr = cur_expr->avail_occr;
     219                 :            : 
     220                 :    9082760 :   if (cur_occr
     221                 :    9082760 :       && BLOCK_FOR_INSN (cur_occr->insn) == BLOCK_FOR_INSN (insn))
     222                 :            :     {
     223                 :            :       /* Found another instance of the expression in the same basic block.
     224                 :            :          Prefer this occurrence to the currently recorded one.  We want
     225                 :            :          the last one in the block and the block is scanned from start
     226                 :            :          to end.  */
     227                 :          0 :       cur_occr->insn = insn;
     228                 :            :     }
     229                 :            :   else
     230                 :            :     {
     231                 :            :       /* First occurrence of this expression in this basic block.  */
     232                 :    9082760 :       cur_occr = GOBNEW (struct cprop_occr);
     233                 :    9082760 :       bytes_used += sizeof (struct cprop_occr);
     234                 :    9082760 :       cur_occr->insn = insn;
     235                 :    9082760 :       cur_occr->next = cur_expr->avail_occr;
     236                 :    9082760 :       cur_expr->avail_occr = cur_occr;
     237                 :            :     }
     238                 :            : 
     239                 :            :   /* Record bitmap_index of the implicit set in implicit_set_indexes.  */
     240                 :    9082760 :   if (implicit)
     241                 :    3754980 :     implicit_set_indexes[BLOCK_FOR_INSN (insn)->index]
     242                 :    3754980 :       = cur_expr->bitmap_index;
     243                 :    9082760 : }
     244                 :            : 
     245                 :            : /* Determine whether the rtx X should be treated as a constant for CPROP.
     246                 :            :    Since X might be inserted more than once we have to take care that it
     247                 :            :    is sharable.  */
     248                 :            : 
     249                 :            : static bool
     250                 :  131003000 : cprop_constant_p (const_rtx x)
     251                 :            : {
     252                 :  131003000 :   return CONSTANT_P (x) && (GET_CODE (x) != CONST || shared_const_p (x));
     253                 :            : }
     254                 :            : 
     255                 :            : /* Determine whether the rtx X should be treated as a register that can
     256                 :            :    be propagated.  Any pseudo-register is fine.  */
     257                 :            : 
     258                 :            : static bool
     259                 :  343520000 : cprop_reg_p (const_rtx x)
     260                 :            : {
     261                 :  252193000 :   return REG_P (x) && !HARD_REGISTER_P (x);
     262                 :            : }
     263                 :            : 
     264                 :            : /* Scan SET present in INSN and add an entry to the hash TABLE.
     265                 :            :    IMPLICIT is true if it's an implicit set, false otherwise.  */
     266                 :            : 
     267                 :            : static void
     268                 :   96543600 : hash_scan_set (rtx set, rtx_insn *insn, struct hash_table_d *table,
     269                 :            :                bool implicit)
     270                 :            : {
     271                 :   96543600 :   rtx src = SET_SRC (set);
     272                 :   96543600 :   rtx dest = SET_DEST (set);
     273                 :            : 
     274                 :  137049000 :   if (cprop_reg_p (dest)
     275                 :   40505200 :       && reg_available_p (dest, insn)
     276                 :   40104800 :       && can_copy_p (GET_MODE (dest)))
     277                 :            :     {
     278                 :            :       /* See if a REG_EQUAL note shows this equivalent to a simpler expression.
     279                 :            : 
     280                 :            :          This allows us to do a single CPROP pass and still eliminate
     281                 :            :          redundant constants, addresses or other expressions that are
     282                 :            :          constructed with multiple instructions.
     283                 :            : 
     284                 :            :          However, keep the original SRC if INSN is a simple reg-reg move.  In
     285                 :            :          In this case, there will almost always be a REG_EQUAL note on the
     286                 :            :          insn that sets SRC.  By recording the REG_EQUAL value here as SRC
     287                 :            :          for INSN, we miss copy propagation opportunities.
     288                 :            : 
     289                 :            :          Note that this does not impede profitable constant propagations.  We
     290                 :            :          "look through" reg-reg sets in lookup_set.  */
     291                 :   40104800 :       rtx note = find_reg_equal_equiv_note (insn);
     292                 :   40104800 :       if (note != 0
     293                 :    2432440 :           && REG_NOTE_KIND (note) == REG_EQUAL
     294                 :    2075890 :           && !REG_P (src)
     295                 :   41976000 :           && cprop_constant_p (XEXP (note, 0)))
     296                 :     735784 :         src = XEXP (note, 0), set = gen_rtx_SET (dest, src);
     297                 :            : 
     298                 :            :       /* Record sets for constant/copy propagation.  */
     299                 :   40104800 :       if ((cprop_reg_p (src)
     300                 :    1682390 :            && src != dest
     301                 :    1682380 :            && reg_available_p (src, insn))
     302                 :   38521100 :           || cprop_constant_p (src))
     303                 :    9082760 :         insert_set_in_table (dest, src, insn, table, implicit);
     304                 :            :     }
     305                 :   96543600 : }
     306                 :            : 
     307                 :            : /* Process INSN and add hash table entries as appropriate.  */
     308                 :            : 
     309                 :            : static void
     310                 :   97650700 : hash_scan_insn (rtx_insn *insn, struct hash_table_d *table)
     311                 :            : {
     312                 :   97650700 :   rtx pat = PATTERN (insn);
     313                 :   97650700 :   int i;
     314                 :            : 
     315                 :            :   /* Pick out the sets of INSN and for other forms of instructions record
     316                 :            :      what's been modified.  */
     317                 :            : 
     318                 :   97650700 :   if (GET_CODE (pat) == SET)
     319                 :   76952800 :     hash_scan_set (pat, insn, table, false);
     320                 :   20697900 :   else if (GET_CODE (pat) == PARALLEL)
     321                 :   46318900 :     for (i = 0; i < XVECLEN (pat, 0); i++)
     322                 :            :       {
     323                 :   31190500 :         rtx x = XVECEXP (pat, 0, i);
     324                 :            : 
     325                 :   31190500 :         if (GET_CODE (x) == SET)
     326                 :   15767100 :           hash_scan_set (x, insn, table, false);
     327                 :            :       }
     328                 :   97650700 : }
     329                 :            : 
     330                 :            : /* Dump the hash table TABLE to file FILE under the name NAME.  */
     331                 :            : 
     332                 :            : static void
     333                 :         63 : dump_hash_table (FILE *file, const char *name, struct hash_table_d *table)
     334                 :            : {
     335                 :         63 :   int i;
     336                 :            :   /* Flattened out table, so it's printed in proper order.  */
     337                 :         63 :   struct cprop_expr **flat_table;
     338                 :         63 :   unsigned int *hash_val;
     339                 :         63 :   struct cprop_expr *expr;
     340                 :            : 
     341                 :         63 :   flat_table = XCNEWVEC (struct cprop_expr *, table->n_elems);
     342                 :         63 :   hash_val = XNEWVEC (unsigned int, table->n_elems);
     343                 :            : 
     344                 :       1316 :   for (i = 0; i < (int) table->size; i++)
     345                 :       1392 :     for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
     346                 :            :       {
     347                 :        139 :         flat_table[expr->bitmap_index] = expr;
     348                 :        139 :         hash_val[expr->bitmap_index] = i;
     349                 :            :       }
     350                 :            : 
     351                 :         63 :   fprintf (file, "%s hash table (%d buckets, %d entries)\n",
     352                 :            :            name, table->size, table->n_elems);
     353                 :            : 
     354                 :        202 :   for (i = 0; i < (int) table->n_elems; i++)
     355                 :        139 :     if (flat_table[i] != 0)
     356                 :            :       {
     357                 :        139 :         expr = flat_table[i];
     358                 :        139 :         fprintf (file, "Index %d (hash value %d)\n  ",
     359                 :        139 :                  expr->bitmap_index, hash_val[i]);
     360                 :        139 :         print_rtl (file, expr->dest);
     361                 :        139 :         fprintf (file, " := ");
     362                 :        139 :         print_rtl (file, expr->src);
     363                 :        139 :         fprintf (file, "\n");
     364                 :            :       }
     365                 :            : 
     366                 :         63 :   fprintf (file, "\n");
     367                 :            : 
     368                 :         63 :   free (flat_table);
     369                 :         63 :   free (hash_val);
     370                 :         63 : }
     371                 :            : 
     372                 :            : /* Record as unavailable all registers that are DEF operands of INSN.  */
     373                 :            : 
     374                 :            : static void
     375                 :   97650700 : make_set_regs_unavailable (rtx_insn *insn)
     376                 :            : {
     377                 :   97650700 :   df_ref def;
     378                 :            : 
     379                 :  702686000 :   FOR_EACH_INSN_DEF (def, insn)
     380                 :  605036000 :     SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
     381                 :   97650700 : }
     382                 :            : 
     383                 :            : /* Top level function to create an assignment hash table.
     384                 :            : 
     385                 :            :    Assignment entries are placed in the hash table if
     386                 :            :    - they are of the form (set (pseudo-reg) src),
     387                 :            :    - src is something we want to perform const/copy propagation on,
     388                 :            :    - none of the operands or target are subsequently modified in the block
     389                 :            : 
     390                 :            :    Currently src must be a pseudo-reg or a const_int.
     391                 :            : 
     392                 :            :    TABLE is the table computed.  */
     393                 :            : 
     394                 :            : static void
     395                 :    1105620 : compute_hash_table_work (struct hash_table_d *table)
     396                 :            : {
     397                 :    1105620 :   basic_block bb;
     398                 :            : 
     399                 :            :   /* Allocate vars to track sets of regs.  */
     400                 :    1105620 :   reg_set_bitmap = ALLOC_REG_SET (NULL);
     401                 :            : 
     402                 :   21267100 :   FOR_EACH_BB_FN (bb, cfun)
     403                 :            :     {
     404                 :   20161400 :       rtx_insn *insn;
     405                 :            : 
     406                 :            :       /* Reset tables used to keep track of what's not yet invalid [since
     407                 :            :          the end of the block].  */
     408                 :   20161400 :       CLEAR_REG_SET (reg_set_bitmap);
     409                 :            : 
     410                 :            :       /* Go over all insns from the last to the first.  This is convenient
     411                 :            :          for tracking available registers, i.e. not set between INSN and
     412                 :            :          the end of the basic block BB.  */
     413                 :  437849000 :       FOR_BB_INSNS_REVERSE (bb, insn)
     414                 :            :         {
     415                 :            :           /* Only real insns are interesting.  */
     416                 :  208844000 :           if (!NONDEBUG_INSN_P (insn))
     417                 :  111193000 :             continue;
     418                 :            : 
     419                 :            :           /* Record interesting sets from INSN in the hash table.  */
     420                 :   97650700 :           hash_scan_insn (insn, table);
     421                 :            : 
     422                 :            :           /* Any registers set in INSN will make SETs above it not AVAIL.  */
     423                 :   97650700 :           make_set_regs_unavailable (insn);
     424                 :            :         }
     425                 :            : 
     426                 :            :       /* Insert implicit sets in the hash table, pretending they appear as
     427                 :            :          insns at the head of the basic block.  */
     428                 :   20161400 :       if (implicit_sets[bb->index] != NULL_RTX)
     429                 :    3823690 :         hash_scan_set (implicit_sets[bb->index], BB_HEAD (bb), table, true);
     430                 :            :     }
     431                 :            : 
     432                 :    1105620 :   FREE_REG_SET (reg_set_bitmap);
     433                 :    1105620 : }
     434                 :            : 
     435                 :            : /* Allocate space for the set/expr hash TABLE.
     436                 :            :    It is used to determine the number of buckets to use.  */
     437                 :            : 
     438                 :            : static void
     439                 :    1105620 : alloc_hash_table (struct hash_table_d *table)
     440                 :            : {
     441                 :    1105620 :   int n;
     442                 :            : 
     443                 :    1105620 :   n = get_max_insn_count ();
     444                 :            : 
     445                 :    1105620 :   table->size = n / 4;
     446                 :    1105620 :   if (table->size < 11)
     447                 :     410116 :     table->size = 11;
     448                 :            : 
     449                 :            :   /* Attempt to maintain efficient use of hash table.
     450                 :            :      Making it an odd number is simplest for now.
     451                 :            :      ??? Later take some measurements.  */
     452                 :    1105620 :   table->size |= 1;
     453                 :    1105620 :   n = table->size * sizeof (struct cprop_expr *);
     454                 :    1105620 :   table->table = XNEWVAR (struct cprop_expr *, n);
     455                 :    1105620 : }
     456                 :            : 
     457                 :            : /* Free things allocated by alloc_hash_table.  */
     458                 :            : 
     459                 :            : static void
     460                 :    1105620 : free_hash_table (struct hash_table_d *table)
     461                 :            : {
     462                 :    1105620 :   free (table->table);
     463                 :          0 : }
     464                 :            : 
     465                 :            : /* Compute the hash TABLE for doing copy/const propagation or
     466                 :            :    expression hash table.  */
     467                 :            : 
     468                 :            : static void
     469                 :    1105620 : compute_hash_table (struct hash_table_d *table)
     470                 :            : {
     471                 :            :   /* Initialize count of number of entries in hash table.  */
     472                 :    1105620 :   table->n_elems = 0;
     473                 :    1105620 :   memset (table->table, 0, table->size * sizeof (struct cprop_expr *));
     474                 :            : 
     475                 :    1105620 :   compute_hash_table_work (table);
     476                 :    1105620 : }
     477                 :            : 
     478                 :            : /* Expression tracking support.  */
     479                 :            : 
     480                 :            : /* Lookup REGNO in the set TABLE.  The result is a pointer to the
     481                 :            :    table entry, or NULL if not found.  */
     482                 :            : 
     483                 :            : static struct cprop_expr *
     484                 :   60553900 : lookup_set (unsigned int regno, struct hash_table_d *table)
     485                 :            : {
     486                 :   60553900 :   unsigned int hash = hash_mod (regno, table->size);
     487                 :   60553900 :   struct cprop_expr *expr;
     488                 :            : 
     489                 :          0 :   expr = table->table[hash];
     490                 :            : 
     491                 :   64844500 :   while (expr && REGNO (expr->dest) != regno)
     492                 :    4290580 :     expr = expr->next_same_hash;
     493                 :            : 
     494                 :          0 :   return expr;
     495                 :            : }
     496                 :            : 
     497                 :            : /* Return the next entry for REGNO in list EXPR.  */
     498                 :            : 
     499                 :            : static struct cprop_expr *
     500                 :          0 : next_set (unsigned int regno, struct cprop_expr *expr)
     501                 :            : {
     502                 :   22499000 :   do
     503                 :   22499000 :     expr = expr->next_same_hash;
     504                 :    8836640 :   while (expr && REGNO (expr->dest) != regno);
     505                 :            : 
     506                 :          0 :   return expr;
     507                 :            : }
     508                 :            : 
     509                 :            : /* Reset tables used to keep track of what's still available [since the
     510                 :            :    start of the block].  */
     511                 :            : 
     512                 :            : static void
     513                 :   18606300 : reset_opr_set_tables (void)
     514                 :            : {
     515                 :            :   /* Maintain a bitmap of which regs have been set since beginning of
     516                 :            :      the block.  */
     517                 :          0 :   CLEAR_REG_SET (reg_set_bitmap);
     518                 :          0 : }
     519                 :            : 
     520                 :            : /* Return nonzero if the register X has not been set yet [since the
     521                 :            :    start of the basic block containing INSN].  */
     522                 :            : 
     523                 :            : static int
     524                 :  106946000 : reg_not_set_p (const_rtx x, const rtx_insn *insn ATTRIBUTE_UNUSED)
     525                 :            : {
     526                 :          0 :   return ! REGNO_REG_SET_P (reg_set_bitmap, REGNO (x));
     527                 :            : }
     528                 :            : 
     529                 :            : /* Record things set by INSN.
     530                 :            :    This data is used by reg_not_set_p.  */
     531                 :            : 
     532                 :            : static void
     533                 :  156359000 : mark_oprs_set (rtx_insn *insn)
     534                 :            : {
     535                 :  156359000 :   df_ref def;
     536                 :            : 
     537                 :  686173000 :   FOR_EACH_INSN_DEF (def, insn)
     538                 :  529815000 :     SET_REGNO_REG_SET (reg_set_bitmap, DF_REF_REGNO (def));
     539                 :  156359000 : }
     540                 :            : 
     541                 :            : /* Compute copy/constant propagation working variables.  */
     542                 :            : 
     543                 :            : /* Local properties of assignments.  */
     544                 :            : static sbitmap *cprop_avloc;
     545                 :            : static sbitmap *cprop_kill;
     546                 :            : 
     547                 :            : /* Global properties of assignments (computed from the local properties).  */
     548                 :            : static sbitmap *cprop_avin;
     549                 :            : static sbitmap *cprop_avout;
     550                 :            : 
     551                 :            : /* Allocate vars used for copy/const propagation.  N_BLOCKS is the number of
     552                 :            :    basic blocks.  N_SETS is the number of sets.  */
     553                 :            : 
     554                 :            : static void
     555                 :     993124 : alloc_cprop_mem (int n_blocks, int n_sets)
     556                 :            : {
     557                 :     993124 :   cprop_avloc = sbitmap_vector_alloc (n_blocks, n_sets);
     558                 :     993124 :   cprop_kill = sbitmap_vector_alloc (n_blocks, n_sets);
     559                 :            : 
     560                 :     993124 :   cprop_avin = sbitmap_vector_alloc (n_blocks, n_sets);
     561                 :     993124 :   cprop_avout = sbitmap_vector_alloc (n_blocks, n_sets);
     562                 :     993124 : }
     563                 :            : 
     564                 :            : /* Free vars used by copy/const propagation.  */
     565                 :            : 
     566                 :            : static void
     567                 :     993124 : free_cprop_mem (void)
     568                 :            : {
     569                 :     993124 :   sbitmap_vector_free (cprop_avloc);
     570                 :     993124 :   sbitmap_vector_free (cprop_kill);
     571                 :     993124 :   sbitmap_vector_free (cprop_avin);
     572                 :     993124 :   sbitmap_vector_free (cprop_avout);
     573                 :     993124 : }
     574                 :            : 
     575                 :            : /* Compute the local properties of each recorded expression.
     576                 :            : 
     577                 :            :    Local properties are those that are defined by the block, irrespective of
     578                 :            :    other blocks.
     579                 :            : 
     580                 :            :    An expression is killed in a block if its operands, either DEST or SRC, are
     581                 :            :    modified in the block.
     582                 :            : 
     583                 :            :    An expression is computed (locally available) in a block if it is computed
     584                 :            :    at least once and expression would contain the same value if the
     585                 :            :    computation was moved to the end of the block.
     586                 :            : 
     587                 :            :    KILL and COMP are destination sbitmaps for recording local properties.  */
     588                 :            : 
     589                 :            : static void
     590                 :     993124 : compute_local_properties (sbitmap *kill, sbitmap *comp,
     591                 :            :                           struct hash_table_d *table)
     592                 :            : {
     593                 :     993124 :   unsigned int i;
     594                 :            : 
     595                 :            :   /* Initialize the bitmaps that were passed in.  */
     596                 :     993124 :   bitmap_vector_clear (kill, last_basic_block_for_fn (cfun));
     597                 :     993124 :   bitmap_vector_clear (comp, last_basic_block_for_fn (cfun));
     598                 :            : 
     599                 :   44390500 :   for (i = 0; i < table->size; i++)
     600                 :            :     {
     601                 :   43397300 :       struct cprop_expr *expr;
     602                 :            : 
     603                 :   51559000 :       for (expr = table->table[i]; expr != NULL; expr = expr->next_same_hash)
     604                 :            :         {
     605                 :    8161660 :           int indx = expr->bitmap_index;
     606                 :    8161660 :           df_ref def;
     607                 :    8161660 :           struct cprop_occr *occr;
     608                 :            : 
     609                 :            :           /* For each definition of the destination pseudo-reg, the expression
     610                 :            :              is killed in the block where the definition is.  */
     611                 :    8161660 :           for (def = DF_REG_DEF_CHAIN (REGNO (expr->dest));
     612                 :   24691200 :                def; def = DF_REF_NEXT_REG (def))
     613                 :   16529600 :             bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
     614                 :            : 
     615                 :            :           /* If the source is a pseudo-reg, for each definition of the source,
     616                 :            :              the expression is killed in the block where the definition is.  */
     617                 :    8161660 :           if (REG_P (expr->src))
     618                 :    1473800 :             for (def = DF_REG_DEF_CHAIN (REGNO (expr->src));
     619                 :    3762810 :                  def; def = DF_REF_NEXT_REG (def))
     620                 :    2289020 :               bitmap_set_bit (kill[DF_REF_BB (def)->index], indx);
     621                 :            : 
     622                 :            :           /* The occurrences recorded in avail_occr are exactly those that
     623                 :            :              are locally available in the block where they are.  */
     624                 :   17244400 :           for (occr = expr->avail_occr; occr != NULL; occr = occr->next)
     625                 :            :             {
     626                 :    9082760 :               bitmap_set_bit (comp[BLOCK_FOR_INSN (occr->insn)->index], indx);
     627                 :            :             }
     628                 :            :         }
     629                 :            :     }
     630                 :     993124 : }
     631                 :            : 
     632                 :            : /* Hash table support.  */
     633                 :            : 
     634                 :            : /* Top level routine to do the dataflow analysis needed by copy/const
     635                 :            :    propagation.  */
     636                 :            : 
     637                 :            : static void
     638                 :     993124 : compute_cprop_data (void)
     639                 :            : {
     640                 :     993124 :   basic_block bb;
     641                 :            : 
     642                 :     993124 :   compute_local_properties (cprop_kill, cprop_avloc, &set_hash_table);
     643                 :     993124 :   compute_available (cprop_avloc, cprop_kill, cprop_avout, cprop_avin);
     644                 :            : 
     645                 :            :   /* Merge implicit sets into CPROP_AVIN.  They are always available at the
     646                 :            :      entry of their basic block.  We need to do this because 1) implicit sets
     647                 :            :      aren't recorded for the local pass so they cannot be propagated within
     648                 :            :      their basic block by this pass and 2) the global pass would otherwise
     649                 :            :      propagate them only in the successors of their basic block.  */
     650                 :   20592600 :   FOR_EACH_BB_FN (bb, cfun)
     651                 :            :     {
     652                 :   19599500 :       int index = implicit_set_indexes[bb->index];
     653                 :   19599500 :       if (index != -1)
     654                 :   23354400 :         bitmap_set_bit (cprop_avin[bb->index], index);
     655                 :            :     }
     656                 :     993124 : }
     657                 :            : 
     658                 :            : /* Copy/constant propagation.  */
     659                 :            : 
     660                 :            : /* Maximum number of register uses in an insn that we handle.  */
     661                 :            : #define MAX_USES 8
     662                 :            : 
     663                 :            : /* Table of uses (registers, both hard and pseudo) found in an insn.
     664                 :            :    Allocated statically to avoid alloc/free complexity and overhead.  */
     665                 :            : static rtx reg_use_table[MAX_USES];
     666                 :            : 
     667                 :            : /* Index into `reg_use_table' while building it.  */
     668                 :            : static unsigned reg_use_count;
     669                 :            : 
     670                 :            : /* Set up a list of register numbers used in INSN.  The found uses are stored
     671                 :            :    in `reg_use_table'.  `reg_use_count' is initialized to zero before entry,
     672                 :            :    and contains the number of uses in the table upon exit.
     673                 :            : 
     674                 :            :    ??? If a register appears multiple times we will record it multiple times.
     675                 :            :    This doesn't hurt anything but it will slow things down.  */
     676                 :            : 
     677                 :            : static void
     678                 :  690388000 : find_used_regs (rtx *xptr, void *data ATTRIBUTE_UNUSED)
     679                 :            : {
     680                 :  690388000 :   int i, j;
     681                 :  690388000 :   enum rtx_code code;
     682                 :  690388000 :   const char *fmt;
     683                 :  690388000 :   rtx x = *xptr;
     684                 :            : 
     685                 :            :   /* repeat is used to turn tail-recursion into iteration since GCC
     686                 :            :      can't do it when there's no return value.  */
     687                 :  978372000 :  repeat:
     688                 :  978372000 :   if (x == 0)
     689                 :            :     return;
     690                 :            : 
     691                 :  978372000 :   code = GET_CODE (x);
     692                 :  978372000 :   if (REG_P (x))
     693                 :            :     {
     694                 :  225770000 :       if (reg_use_count == MAX_USES)
     695                 :            :         return;
     696                 :            : 
     697                 :  225747000 :       reg_use_table[reg_use_count] = x;
     698                 :  225747000 :       reg_use_count++;
     699                 :            :     }
     700                 :            : 
     701                 :            :   /* Recursively scan the operands of this expression.  */
     702                 :            : 
     703                 : 2018240000 :   for (i = GET_RTX_LENGTH (code) - 1, fmt = GET_RTX_FORMAT (code); i >= 0; i--)
     704                 :            :     {
     705                 : 1327870000 :       if (fmt[i] == 'e')
     706                 :            :         {
     707                 :            :           /* If we are about to do the last recursive call
     708                 :            :              needed at this level, change it into iteration.
     709                 :            :              This function is called enough to be worth it.  */
     710                 :  590871000 :           if (i == 0)
     711                 :            :             {
     712                 :  287984000 :               x = XEXP (x, 0);
     713                 :  287984000 :               goto repeat;
     714                 :            :             }
     715                 :            : 
     716                 :  302887000 :           find_used_regs (&XEXP (x, i), data);
     717                 :            :         }
     718                 :  736999000 :       else if (fmt[i] == 'E')
     719                 :   15928500 :         for (j = 0; j < XVECLEN (x, i); j++)
     720                 :   10428000 :           find_used_regs (&XVECEXP (x, i, j), data);
     721                 :            :     }
     722                 :            : }
     723                 :            : 
     724                 :            : /* Try to replace all uses of FROM in INSN with TO.
     725                 :            :    Return nonzero if successful.  */
     726                 :            : 
     727                 :            : static int
     728                 :    4892810 : try_replace_reg (rtx from, rtx to, rtx_insn *insn)
     729                 :            : {
     730                 :    4892810 :   rtx note = find_reg_equal_equiv_note (insn);
     731                 :    4892810 :   rtx src = 0;
     732                 :    4892810 :   int success = 0;
     733                 :    4892810 :   rtx set = single_set (insn);
     734                 :            : 
     735                 :    4892810 :   bool check_rtx_costs = true;
     736                 :    4892810 :   bool speed = optimize_bb_for_speed_p (BLOCK_FOR_INSN (insn));
     737                 :    4892810 :   int old_cost = set ? set_rtx_cost (set, speed) : 0;
     738                 :            : 
     739                 :    4892810 :   if (!set
     740                 :    4724000 :       || CONSTANT_P (SET_SRC (set))
     741                 :    4579690 :       || (note != 0
     742                 :    1484620 :           && REG_NOTE_KIND (note) == REG_EQUAL
     743                 :    1484620 :           && (GET_CODE (XEXP (note, 0)) == CONST
     744                 :    1482340 :               || CONSTANT_P (XEXP (note, 0)))))
     745                 :     587685 :     check_rtx_costs = false;
     746                 :            : 
     747                 :            :   /* Usually we substitute easy stuff, so we won't copy everything.
     748                 :            :      We however need to take care to not duplicate non-trivial CONST
     749                 :            :      expressions.  */
     750                 :    4892810 :   to = copy_rtx (to);
     751                 :            : 
     752                 :    4892810 :   validate_replace_src_group (from, to, insn);
     753                 :            : 
     754                 :            :   /* If TO is a constant, check the cost of the set after propagation
     755                 :            :      to the cost of the set before the propagation.  If the cost is
     756                 :            :      higher, then do not replace FROM with TO.  */
     757                 :            : 
     758                 :    4892810 :   if (check_rtx_costs
     759                 :    4305120 :       && CONSTANT_P (to)
     760                 :    7801090 :       && set_rtx_cost (set, speed) > old_cost)
     761                 :            :     {
     762                 :    1633840 :       cancel_changes (0);
     763                 :    1633840 :       return false;
     764                 :            :     }
     765                 :            : 
     766                 :            : 
     767                 :    3258970 :   if (num_changes_pending () && apply_change_group ())
     768                 :            :     success = 1;
     769                 :            : 
     770                 :            :   /* Try to simplify SET_SRC if we have substituted a constant.  */
     771                 :    3258970 :   if (success && set && CONSTANT_P (to))
     772                 :            :     {
     773                 :     238388 :       src = simplify_rtx (SET_SRC (set));
     774                 :            : 
     775                 :     238388 :       if (src)
     776                 :       4271 :         validate_change (insn, &SET_SRC (set), src, 0);
     777                 :            :     }
     778                 :            : 
     779                 :            :   /* If there is already a REG_EQUAL note, update the expression in it
     780                 :            :      with our replacement.  */
     781                 :    3258970 :   if (note != 0 && REG_NOTE_KIND (note) == REG_EQUAL)
     782                 :    1222580 :     set_unique_reg_note (insn, REG_EQUAL,
     783                 :            :                          simplify_replace_rtx (XEXP (note, 0), from, to));
     784                 :    3258970 :   if (!success && set && reg_mentioned_p (from, SET_SRC (set)))
     785                 :            :     {
     786                 :            :       /* If above failed and this is a single set, try to simplify the source
     787                 :            :          of the set given our substitution.  We could perhaps try this for
     788                 :            :          multiple SETs, but it probably won't buy us anything.  */
     789                 :    1101130 :       src = simplify_replace_rtx (SET_SRC (set), from, to);
     790                 :            : 
     791                 :    1101130 :       if (!rtx_equal_p (src, SET_SRC (set))
     792                 :    1101130 :           && validate_change (insn, &SET_SRC (set), src, 0))
     793                 :            :         success = 1;
     794                 :            : 
     795                 :            :       /* If we've failed perform the replacement, have a single SET to
     796                 :            :          a REG destination and don't yet have a note, add a REG_EQUAL note
     797                 :            :          to not lose information.  */
     798                 :    1101130 :       if (!success && note == 0 && set != 0 && REG_P (SET_DEST (set)))
     799                 :     379557 :         note = set_unique_reg_note (insn, REG_EQUAL, copy_rtx (src));
     800                 :            :     }
     801                 :            : 
     802                 :    3258970 :   if (set && MEM_P (SET_DEST (set)) && reg_mentioned_p (from, SET_DEST (set)))
     803                 :            :     {
     804                 :            :       /* Registers can also appear as uses in SET_DEST if it is a MEM.
     805                 :            :          We could perhaps try this for multiple SETs, but it probably
     806                 :            :          won't buy us anything.  */
     807                 :       9993 :       rtx dest = simplify_replace_rtx (SET_DEST (set), from, to);
     808                 :            : 
     809                 :       9993 :       if (!rtx_equal_p (dest, SET_DEST (set))
     810                 :       9993 :           && validate_change (insn, &SET_DEST (set), dest, 0))
     811                 :            :         success = 1;
     812                 :            :     }
     813                 :            : 
     814                 :            :   /* REG_EQUAL may get simplified into register.
     815                 :            :      We don't allow that. Remove that note. This code ought
     816                 :            :      not to happen, because previous code ought to synthesize
     817                 :            :      reg-reg move, but be on the safe side.  */
     818                 :    3258970 :   if (note && REG_NOTE_KIND (note) == REG_EQUAL && REG_P (XEXP (note, 0)))
     819                 :          0 :     remove_note (insn, note);
     820                 :            : 
     821                 :            :   return success;
     822                 :            : }
     823                 :            : 
     824                 :            : /* Find a set of REGNOs that are available on entry to INSN's block.  If found,
     825                 :            :    SET_RET[0] will be assigned a set with a register source and SET_RET[1] a
     826                 :            :    set with a constant source.  If not found the corresponding entry is set to
     827                 :            :    NULL.  */
     828                 :            : 
     829                 :            : static void
     830                 :   58699000 : find_avail_set (int regno, rtx_insn *insn, struct cprop_expr *set_ret[2])
     831                 :            : {
     832                 :   58699000 :   set_ret[0] = set_ret[1] = NULL;
     833                 :            : 
     834                 :            :   /* Loops are not possible here.  To get a loop we would need two sets
     835                 :            :      available at the start of the block containing INSN.  i.e. we would
     836                 :            :      need two sets like this available at the start of the block:
     837                 :            : 
     838                 :            :        (set (reg X) (reg Y))
     839                 :            :        (set (reg Y) (reg X))
     840                 :            : 
     841                 :            :      This cannot happen since the set of (reg Y) would have killed the
     842                 :            :      set of (reg X) making it unavailable at the start of this block.  */
     843                 :   59619200 :   while (1)
     844                 :            :     {
     845                 :   59159100 :       rtx src;
     846                 :   59159100 :       struct cprop_expr *set = lookup_set (regno, &set_hash_table);
     847                 :            : 
     848                 :            :       /* Find a set that is available at the start of the block
     849                 :            :          which contains INSN.  */
     850                 :   79791000 :       while (set)
     851                 :            :         {
     852                 :   22389800 :           if (bitmap_bit_p (cprop_avin[BLOCK_FOR_INSN (insn)->index],
     853                 :            :                         set->bitmap_index))
     854                 :            :             break;
     855                 :  100846000 :           set = next_set (regno, set);
     856                 :            :         }
     857                 :            : 
     858                 :            :       /* If no available set was found we've reached the end of the
     859                 :            :          (possibly empty) copy chain.  */
     860                 :   59159100 :       if (set == 0)
     861                 :            :         break;
     862                 :            : 
     863                 :    1757920 :       src = set->src;
     864                 :            : 
     865                 :            :       /* We know the set is available.
     866                 :            :          Now check that SRC is locally anticipatable (i.e. none of the
     867                 :            :          source operands have changed since the start of the block).
     868                 :            : 
     869                 :            :          If the source operand changed, we may still use it for the next
     870                 :            :          iteration of this loop, but we may not use it for substitutions.  */
     871                 :            : 
     872                 :    1757920 :       if (cprop_constant_p (src))
     873                 :    1297820 :         set_ret[1] = set;
     874                 :     460094 :       else if (reg_not_set_p (src, insn))
     875                 :     456336 :         set_ret[0] = set;
     876                 :            : 
     877                 :            :       /* If the source of the set is anything except a register, then
     878                 :            :          we have reached the end of the copy chain.  */
     879                 :    1757920 :       if (! REG_P (src))
     880                 :            :         break;
     881                 :            : 
     882                 :            :       /* Follow the copy chain, i.e. start another iteration of the loop
     883                 :            :          and see if we have an available copy into SRC.  */
     884                 :     460094 :       regno = REGNO (src);
     885                 :     460094 :     }
     886                 :   58699000 : }
     887                 :            : 
     888                 :            : /* Subroutine of cprop_insn that tries to propagate constants into
     889                 :            :    JUMP_INSNS.  JUMP must be a conditional jump.  If SETCC is non-NULL
     890                 :            :    it is the instruction that immediately precedes JUMP, and must be a
     891                 :            :    single SET of a register.  FROM is what we will try to replace,
     892                 :            :    SRC is the constant we will try to substitute for it.  Return nonzero
     893                 :            :    if a change was made.  */
     894                 :            : 
     895                 :            : static int
     896                 :     595433 : cprop_jump (basic_block bb, rtx_insn *setcc, rtx_insn *jump, rtx from, rtx src)
     897                 :            : {
     898                 :     595433 :   rtx new_rtx, set_src, note_src;
     899                 :     595433 :   rtx set = pc_set (jump);
     900                 :     595433 :   rtx note = find_reg_equal_equiv_note (jump);
     901                 :            : 
     902                 :     595433 :   if (note)
     903                 :            :     {
     904                 :          0 :       note_src = XEXP (note, 0);
     905                 :          0 :       if (GET_CODE (note_src) == EXPR_LIST)
     906                 :            :         note_src = NULL_RTX;
     907                 :            :     }
     908                 :            :   else note_src = NULL_RTX;
     909                 :            : 
     910                 :            :   /* Prefer REG_EQUAL notes except those containing EXPR_LISTs.  */
     911                 :     595433 :   set_src = note_src ? note_src : SET_SRC (set);
     912                 :            : 
     913                 :            :   /* First substitute the SETCC condition into the JUMP instruction,
     914                 :            :      then substitute that given values into this expanded JUMP.  */
     915                 :     595433 :   if (setcc != NULL_RTX
     916                 :     595433 :       && !modified_between_p (from, setcc, jump)
     917                 :    1190870 :       && !modified_between_p (src, setcc, jump))
     918                 :            :     {
     919                 :     595433 :       rtx setcc_src;
     920                 :     595433 :       rtx setcc_set = single_set (setcc);
     921                 :     595433 :       rtx setcc_note = find_reg_equal_equiv_note (setcc);
     922                 :     145087 :       setcc_src = (setcc_note && GET_CODE (XEXP (setcc_note, 0)) != EXPR_LIST)
     923                 :     595433 :                 ? XEXP (setcc_note, 0) : SET_SRC (setcc_set);
     924                 :     595433 :       set_src = simplify_replace_rtx (set_src, SET_DEST (setcc_set),
     925                 :            :                                       setcc_src);
     926                 :            :     }
     927                 :            :   else
     928                 :            :     setcc = NULL;
     929                 :            : 
     930                 :     595433 :   new_rtx = simplify_replace_rtx (set_src, from, src);
     931                 :            : 
     932                 :            :   /* If no simplification can be made, then try the next register.  */
     933                 :     595433 :   if (rtx_equal_p (new_rtx, SET_SRC (set)))
     934                 :            :     return 0;
     935                 :            : 
     936                 :            :   /* If this is now a no-op delete it, otherwise this must be a valid insn.  */
     937                 :     591432 :   if (new_rtx == pc_rtx)
     938                 :        810 :     delete_insn (jump);
     939                 :            :   else
     940                 :            :     {
     941                 :            :       /* Ensure the value computed inside the jump insn to be equivalent
     942                 :            :          to one computed by setcc.  */
     943                 :     590622 :       if (setcc && modified_in_p (new_rtx, setcc))
     944                 :            :         return 0;
     945                 :       1890 :       if (! validate_unshare_change (jump, &SET_SRC (set), new_rtx, 0))
     946                 :            :         {
     947                 :            :           /* When (some) constants are not valid in a comparison, and there
     948                 :            :              are two registers to be replaced by constants before the entire
     949                 :            :              comparison can be folded into a constant, we need to keep
     950                 :            :              intermediate information in REG_EQUAL notes.  For targets with
     951                 :            :              separate compare insns, such notes are added by try_replace_reg.
     952                 :            :              When we have a combined compare-and-branch instruction, however,
     953                 :            :              we need to attach a note to the branch itself to make this
     954                 :            :              optimization work.  */
     955                 :            : 
     956                 :          0 :           if (!rtx_equal_p (new_rtx, note_src))
     957                 :          0 :             set_unique_reg_note (jump, REG_EQUAL, copy_rtx (new_rtx));
     958                 :          0 :           return 0;
     959                 :            :         }
     960                 :            : 
     961                 :            :       /* Remove REG_EQUAL note after simplification.  */
     962                 :       1890 :       if (note_src)
     963                 :          0 :         remove_note (jump, note);
     964                 :            :      }
     965                 :            : 
     966                 :            :   /* Delete the cc0 setter.  */
     967                 :       2700 :   if (HAVE_cc0 && setcc != NULL && CC0_P (SET_DEST (single_set (setcc))))
     968                 :            :     delete_insn (setcc);
     969                 :            : 
     970                 :       2700 :   global_const_prop_count++;
     971                 :       2700 :   if (dump_file != NULL)
     972                 :            :     {
     973                 :          0 :       fprintf (dump_file,
     974                 :            :                "GLOBAL CONST-PROP: Replacing reg %d in jump_insn %d with "
     975                 :          0 :                "constant ", REGNO (from), INSN_UID (jump));
     976                 :          0 :       print_rtl (dump_file, src);
     977                 :          0 :       fprintf (dump_file, "\n");
     978                 :            :     }
     979                 :       2700 :   purge_dead_edges (bb);
     980                 :            : 
     981                 :            :   /* If a conditional jump has been changed into unconditional jump, remove
     982                 :            :      the jump and make the edge fallthru - this is always called in
     983                 :            :      cfglayout mode.  */
     984                 :       2700 :   if (new_rtx != pc_rtx && simplejump_p (jump))
     985                 :            :     {
     986                 :       1890 :       edge e;
     987                 :       1890 :       edge_iterator ei;
     988                 :            : 
     989                 :       1890 :       FOR_EACH_EDGE (e, ei, bb->succs)
     990                 :       1890 :         if (e->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)
     991                 :       1890 :             && BB_HEAD (e->dest) == JUMP_LABEL (jump))
     992                 :            :           {
     993                 :       1890 :             e->flags |= EDGE_FALLTHRU;
     994                 :       1890 :             break;
     995                 :            :           }
     996                 :       1890 :       delete_insn (jump);
     997                 :            :     }
     998                 :            : 
     999                 :            :   return 1;
    1000                 :            : }
    1001                 :            : 
    1002                 :            : /* Subroutine of cprop_insn that tries to propagate constants.  FROM is what
    1003                 :            :    we will try to replace, SRC is the constant we will try to substitute for
    1004                 :            :    it and INSN is the instruction where this will be happening.  */
    1005                 :            : 
    1006                 :            : static int
    1007                 :    3404170 : constprop_register (rtx from, rtx src, rtx_insn *insn)
    1008                 :            : {
    1009                 :    3404170 :   rtx sset;
    1010                 :            : 
    1011                 :            :   /* Check for reg or cc0 setting instructions followed by
    1012                 :            :      conditional branch instructions first.  */
    1013                 :    3404170 :   if ((sset = single_set (insn)) != NULL
    1014                 :    3272010 :       && NEXT_INSN (insn)
    1015                 :    6675650 :       && any_condjump_p (NEXT_INSN (insn)) && onlyjump_p (NEXT_INSN (insn)))
    1016                 :            :     {
    1017                 :     595433 :       rtx dest = SET_DEST (sset);
    1018                 :     595433 :       if ((REG_P (dest) || CC0_P (dest))
    1019                 :     595433 :           && cprop_jump (BLOCK_FOR_INSN (insn), insn, NEXT_INSN (insn),
    1020                 :            :                          from, src))
    1021                 :            :         return 1;
    1022                 :            :     }
    1023                 :            : 
    1024                 :            :   /* Handle normal insns next.  */
    1025                 :    3401470 :   if (NONJUMP_INSN_P (insn) && try_replace_reg (from, src, insn))
    1026                 :            :     return 1;
    1027                 :            : 
    1028                 :            :   /* Try to propagate a CONST_INT into a conditional jump.
    1029                 :            :      We're pretty specific about what we will handle in this
    1030                 :            :      code, we can extend this as necessary over time.
    1031                 :            : 
    1032                 :            :      Right now the insn in question must look like
    1033                 :            :      (set (pc) (if_then_else ...))  */
    1034                 :    3155970 :   else if (any_condjump_p (insn) && onlyjump_p (insn))
    1035                 :          0 :     return cprop_jump (BLOCK_FOR_INSN (insn), NULL, insn, from, src);
    1036                 :            :   return 0;
    1037                 :            : }
    1038                 :            : 
    1039                 :            : /* Perform constant and copy propagation on INSN.
    1040                 :            :    Return nonzero if a change was made.  */
    1041                 :            : 
    1042                 :            : static int
    1043                 :  156359000 : cprop_insn (rtx_insn *insn)
    1044                 :            : {
    1045                 :  156359000 :   unsigned i;
    1046                 :  156359000 :   int changed = 0, changed_this_round;
    1047                 :  156880000 :   rtx note;
    1048                 :            : 
    1049                 :  156880000 :   do
    1050                 :            :     {
    1051                 :  156880000 :       changed_this_round = 0;
    1052                 :  156880000 :       reg_use_count = 0;
    1053                 :  156880000 :       note_uses (&PATTERN (insn), find_used_regs, NULL);
    1054                 :            : 
    1055                 :            :       /* We may win even when propagating constants into notes.  */
    1056                 :  156880000 :       note = find_reg_equal_equiv_note (insn);
    1057                 :  156880000 :       if (note)
    1058                 :    4187310 :         find_used_regs (&XEXP (note, 0), NULL);
    1059                 :            : 
    1060                 :  263365000 :       for (i = 0; i < reg_use_count; i++)
    1061                 :            :         {
    1062                 :  106486000 :           rtx reg_used = reg_use_table[i];
    1063                 :  106486000 :           unsigned int regno = REGNO (reg_used);
    1064                 :  106486000 :           rtx src_cst = NULL, src_reg = NULL;
    1065                 :  106486000 :           struct cprop_expr *set[2];
    1066                 :            : 
    1067                 :            :           /* If the register has already been set in this block, there's
    1068                 :            :              nothing we can do.  */
    1069                 :  106486000 :           if (! reg_not_set_p (reg_used, insn))
    1070                 :   47786600 :             continue;
    1071                 :            : 
    1072                 :            :           /* Find an assignment that sets reg_used and is available
    1073                 :            :              at the start of the block.  */
    1074                 :   58699000 :           find_avail_set (regno, insn, set);
    1075                 :   58699000 :           if (set[0])
    1076                 :     455805 :             src_reg = set[0]->src;
    1077                 :   58699000 :           if (set[1])
    1078                 :    1297820 :             src_cst = set[1]->src;
    1079                 :            : 
    1080                 :            :           /* Constant propagation.  */
    1081                 :    1297820 :           if (src_cst && cprop_constant_p (src_cst)
    1082                 :    2595650 :               && constprop_register (reg_used, src_cst, insn))
    1083                 :            :             {
    1084                 :      91426 :               changed_this_round = changed = 1;
    1085                 :      91426 :               global_const_prop_count++;
    1086                 :      91426 :               if (dump_file != NULL)
    1087                 :            :                 {
    1088                 :          6 :                   fprintf (dump_file,
    1089                 :            :                            "GLOBAL CONST-PROP: Replacing reg %d in ", regno);
    1090                 :          6 :                   fprintf (dump_file, "insn %d with constant ",
    1091                 :          6 :                            INSN_UID (insn));
    1092                 :          6 :                   print_rtl (dump_file, src_cst);
    1093                 :          6 :                   fprintf (dump_file, "\n");
    1094                 :            :                 }
    1095                 :      91426 :               if (insn->deleted ())
    1096                 :          0 :                 return 1;
    1097                 :            :             }
    1098                 :            :           /* Copy propagation.  */
    1099                 :   58699000 :           else if (src_reg && cprop_reg_p (src_reg)
    1100                 :     455388 :                    && REGNO (src_reg) != regno
    1101                 :   59062900 :                    && try_replace_reg (reg_used, src_reg, insn))
    1102                 :            :             {
    1103                 :     443846 :               changed_this_round = changed = 1;
    1104                 :     443846 :               global_copy_prop_count++;
    1105                 :     443846 :               if (dump_file != NULL)
    1106                 :            :                 {
    1107                 :          0 :                   fprintf (dump_file,
    1108                 :            :                            "GLOBAL COPY-PROP: Replacing reg %d in insn %d",
    1109                 :          0 :                            regno, INSN_UID (insn));
    1110                 :          0 :                   fprintf (dump_file, " with reg %d\n", REGNO (src_reg));
    1111                 :            :                 }
    1112                 :            : 
    1113                 :            :               /* The original insn setting reg_used may or may not now be
    1114                 :            :                  deletable.  We leave the deletion to DCE.  */
    1115                 :            :               /* FIXME: If it turns out that the insn isn't deletable,
    1116                 :            :                  then we may have unnecessarily extended register lifetimes
    1117                 :            :                  and made things worse.  */
    1118                 :            :             }
    1119                 :            :         }
    1120                 :            :     }
    1121                 :            :   /* If try_replace_reg simplified the insn, the regs found by find_used_regs
    1122                 :            :      may not be valid anymore.  Start over.  */
    1123                 :  156880000 :   while (changed_this_round);
    1124                 :            : 
    1125                 :  156359000 :   if (changed && DEBUG_INSN_P (insn))
    1126                 :      16160 :     return 0;
    1127                 :            : 
    1128                 :            :   return changed;
    1129                 :            : }
    1130                 :            : 
    1131                 :            : /* Like find_used_regs, but avoid recording uses that appear in
    1132                 :            :    input-output contexts such as zero_extract or pre_dec.  This
    1133                 :            :    restricts the cases we consider to those for which local cprop
    1134                 :            :    can legitimately make replacements.  */
    1135                 :            : 
    1136                 :            : static void
    1137                 :  204011000 : local_cprop_find_used_regs (rtx *xptr, void *data)
    1138                 :            : {
    1139                 :  204011000 :   rtx x = *xptr;
    1140                 :            : 
    1141                 :  204011000 :   if (x == 0)
    1142                 :            :     return;
    1143                 :            : 
    1144                 :  204011000 :   switch (GET_CODE (x))
    1145                 :            :     {
    1146                 :            :     case ZERO_EXTRACT:
    1147                 :            :     case SIGN_EXTRACT:
    1148                 :            :     case STRICT_LOW_PART:
    1149                 :            :       return;
    1150                 :            : 
    1151                 :            :     case PRE_DEC:
    1152                 :            :     case PRE_INC:
    1153                 :            :     case POST_DEC:
    1154                 :            :     case POST_INC:
    1155                 :            :     case PRE_MODIFY:
    1156                 :            :     case POST_MODIFY:
    1157                 :            :       /* Can only legitimately appear this early in the context of
    1158                 :            :          stack pushes for function arguments, but handle all of the
    1159                 :            :          codes nonetheless.  */
    1160                 :            :       return;
    1161                 :            : 
    1162                 :     560255 :     case SUBREG:
    1163                 :     560255 :       if (read_modify_subreg_p (x))
    1164                 :            :         return;
    1165                 :            :       break;
    1166                 :            : 
    1167                 :            :     default:
    1168                 :            :       break;
    1169                 :            :     }
    1170                 :            : 
    1171                 :  199221000 :   find_used_regs (xptr, data);
    1172                 :            : }
    1173                 :            : 
    1174                 :            : /* Try to perform local const/copy propagation on X in INSN.  */
    1175                 :            : 
    1176                 :            : static bool
    1177                 :  117727000 : do_local_cprop (rtx x, rtx_insn *insn)
    1178                 :            : {
    1179                 :  117727000 :   rtx newreg = NULL, newcnst = NULL;
    1180                 :            : 
    1181                 :            :   /* Rule out USE instructions and ASM statements as we don't want to
    1182                 :            :      change the hard registers mentioned.  */
    1183                 :  117727000 :   if (REG_P (x)
    1184                 :  158308000 :       && (cprop_reg_p (x)
    1185                 :   40580700 :           || (GET_CODE (PATTERN (insn)) != USE
    1186                 :   40035900 :               && asm_noperands (PATTERN (insn)) < 0)))
    1187                 :            :     {
    1188                 :  117179000 :       cselib_val *val = cselib_lookup (x, GET_MODE (x), 0, VOIDmode);
    1189                 :  117179000 :       struct elt_loc_list *l;
    1190                 :            : 
    1191                 :  117179000 :       if (!val)
    1192                 :            :         return false;
    1193                 :  127703000 :       for (l = val->locs; l; l = l->next)
    1194                 :            :         {
    1195                 :   82261000 :           rtx this_rtx = l->loc;
    1196                 :   82261000 :           rtx note;
    1197                 :            : 
    1198                 :   82261000 :           if (cprop_constant_p (this_rtx))
    1199                 :    2106340 :             newcnst = this_rtx;
    1200                 :  135328000 :           if (cprop_reg_p (this_rtx)
    1201                 :            :               /* Don't copy propagate if it has attached REG_EQUIV note.
    1202                 :            :                  At this point this only function parameters should have
    1203                 :            :                  REG_EQUIV notes and if the argument slot is used somewhere
    1204                 :            :                  explicitly, it means address of parameter has been taken,
    1205                 :            :                  so we should not extend the lifetime of the pseudo.  */
    1206                 :   31792200 :               && (!(note = find_reg_note (l->setting_insn, REG_EQUIV, NULL_RTX))
    1207                 :       3111 :                   || ! MEM_P (XEXP (note, 0))))
    1208                 :            :             newreg = this_rtx;
    1209                 :            :         }
    1210                 :   45442500 :       if (newcnst && constprop_register (x, newcnst, insn))
    1211                 :            :         {
    1212                 :     156769 :           if (dump_file != NULL)
    1213                 :            :             {
    1214                 :          2 :               fprintf (dump_file, "LOCAL CONST-PROP: Replacing reg %d in ",
    1215                 :            :                        REGNO (x));
    1216                 :          2 :               fprintf (dump_file, "insn %d with constant ",
    1217                 :          2 :                        INSN_UID (insn));
    1218                 :          2 :               print_rtl (dump_file, newcnst);
    1219                 :          2 :               fprintf (dump_file, "\n");
    1220                 :            :             }
    1221                 :     156769 :           local_const_prop_count++;
    1222                 :     156769 :           return true;
    1223                 :            :         }
    1224                 :   45285700 :       else if (newreg && newreg != x && try_replace_reg (x, newreg, insn))
    1225                 :            :         {
    1226                 :    1045040 :           if (dump_file != NULL)
    1227                 :            :             {
    1228                 :         10 :               fprintf (dump_file,
    1229                 :            :                        "LOCAL COPY-PROP: Replacing reg %d in insn %d",
    1230                 :         10 :                        REGNO (x), INSN_UID (insn));
    1231                 :         10 :               fprintf (dump_file, " with reg %d\n", REGNO (newreg));
    1232                 :            :             }
    1233                 :    1045040 :           local_copy_prop_count++;
    1234                 :    1045040 :           return true;
    1235                 :            :         }
    1236                 :            :     }
    1237                 :            :   return false;
    1238                 :            : }
    1239                 :            : 
    1240                 :            : /* Do local const/copy propagation (i.e. within each basic block).  */
    1241                 :            : 
    1242                 :            : static int
    1243                 :    1105620 : local_cprop_pass (void)
    1244                 :            : {
    1245                 :    1105620 :   basic_block bb;
    1246                 :    1105620 :   rtx_insn *insn;
    1247                 :    1105620 :   bool changed = false;
    1248                 :    1105620 :   unsigned i;
    1249                 :            : 
    1250                 :    1105620 :   auto_vec<rtx_insn *> uncond_traps;
    1251                 :            : 
    1252                 :    1105620 :   cselib_init (0);
    1253                 :   19726400 :   FOR_EACH_BB_FN (bb, cfun)
    1254                 :            :     {
    1255                 :  225735000 :       FOR_BB_INSNS (bb, insn)
    1256                 :            :         {
    1257                 :  207114000 :           if (INSN_P (insn))
    1258                 :            :             {
    1259                 :  178004000 :               bool was_uncond_trap
    1260                 :  178004000 :                 = (GET_CODE (PATTERN (insn)) == TRAP_IF
    1261                 :  178004000 :                    && XEXP (PATTERN (insn), 0) == const1_rtx);
    1262                 :  178004000 :               rtx note = find_reg_equal_equiv_note (insn);
    1263                 :  179206000 :               do
    1264                 :            :                 {
    1265                 :  179206000 :                   reg_use_count = 0;
    1266                 :  179206000 :                   note_uses (&PATTERN (insn), local_cprop_find_used_regs,
    1267                 :            :                              NULL);
    1268                 :  179206000 :                   if (note)
    1269                 :    5868350 :                     local_cprop_find_used_regs (&XEXP (note, 0), NULL);
    1270                 :            : 
    1271                 :  295731000 :                   for (i = 0; i < reg_use_count; i++)
    1272                 :            :                     {
    1273                 :  117727000 :                       if (do_local_cprop (reg_use_table[i], insn))
    1274                 :            :                         {
    1275                 :    1201800 :                           if (!DEBUG_INSN_P (insn))
    1276                 :    1184370 :                             changed = true;
    1277                 :            :                           break;
    1278                 :            :                         }
    1279                 :            :                     }
    1280                 :  179206000 :                   if (!was_uncond_trap
    1281                 :  179196000 :                       && GET_CODE (PATTERN (insn)) == TRAP_IF
    1282                 :  179206000 :                       && XEXP (PATTERN (insn), 0) == const1_rtx)
    1283                 :            :                     {
    1284                 :          0 :                       uncond_traps.safe_push (insn);
    1285                 :          0 :                       break;
    1286                 :            :                     }
    1287                 :  179206000 :                   if (insn->deleted ())
    1288                 :            :                     break;
    1289                 :            :                 }
    1290                 :  179206000 :               while (i < reg_use_count);
    1291                 :            :             }
    1292                 :  207114000 :           cselib_process_insn (insn);
    1293                 :            :         }
    1294                 :            : 
    1295                 :            :       /* Forget everything at the end of a basic block.  */
    1296                 :   18620800 :       cselib_clear_table ();
    1297                 :            :     }
    1298                 :            : 
    1299                 :    1105620 :   cselib_finish ();
    1300                 :            : 
    1301                 :    1105620 :   while (!uncond_traps.is_empty ())
    1302                 :            :     {
    1303                 :          0 :       rtx_insn *insn = uncond_traps.pop ();
    1304                 :          0 :       basic_block to_split = BLOCK_FOR_INSN (insn);
    1305                 :          0 :       remove_edge (split_block (to_split, insn));
    1306                 :          0 :       emit_barrier_after_bb (to_split);
    1307                 :            :     }
    1308                 :            : 
    1309                 :    1105620 :   return changed;
    1310                 :            : }
    1311                 :            : 
    1312                 :            : /* Similar to get_condition, only the resulting condition must be
    1313                 :            :    valid at JUMP, instead of at EARLIEST.
    1314                 :            : 
    1315                 :            :    This differs from noce_get_condition in ifcvt.c in that we prefer not to
    1316                 :            :    settle for the condition variable in the jump instruction being integral.
    1317                 :            :    We prefer to be able to record the value of a user variable, rather than
    1318                 :            :    the value of a temporary used in a condition.  This could be solved by
    1319                 :            :    recording the value of *every* register scanned by canonicalize_condition,
    1320                 :            :    but this would require some code reorganization.  */
    1321                 :            : 
    1322                 :            : rtx
    1323                 :   12916600 : fis_get_condition (rtx_insn *jump)
    1324                 :            : {
    1325                 :   12916600 :   return get_condition (jump, NULL, false, true);
    1326                 :            : }
    1327                 :            : 
    1328                 :            : /* Check the comparison COND to see if we can safely form an implicit
    1329                 :            :    set from it.  */
    1330                 :            : 
    1331                 :            : static bool
    1332                 :    8247270 : implicit_set_cond_p (const_rtx cond)
    1333                 :            : {
    1334                 :    8247270 :   machine_mode mode;
    1335                 :    8247270 :   rtx cst;
    1336                 :            : 
    1337                 :            :   /* COND must be either an EQ or NE comparison.  */
    1338                 :    8247270 :   if (GET_CODE (cond) != EQ && GET_CODE (cond) != NE)
    1339                 :            :     return false;
    1340                 :            : 
    1341                 :            :   /* The first operand of COND must be a register we can propagate.  */
    1342                 :    6428170 :   if (!cprop_reg_p (XEXP (cond, 0)))
    1343                 :            :     return false;
    1344                 :            : 
    1345                 :            :   /* The second operand of COND must be a suitable constant.  */
    1346                 :    5068250 :   mode = GET_MODE (XEXP (cond, 0));
    1347                 :    5068250 :   cst = XEXP (cond, 1);
    1348                 :            : 
    1349                 :            :   /* We can't perform this optimization if either operand might be or might
    1350                 :            :      contain a signed zero.  */
    1351                 :    5068250 :   if (HONOR_SIGNED_ZEROS (mode))
    1352                 :            :     {
    1353                 :            :       /* It is sufficient to check if CST is or contains a zero.  We must
    1354                 :            :          handle float, complex, and vector.  If any subpart is a zero, then
    1355                 :            :          the optimization can't be performed.  */
    1356                 :            :       /* ??? The complex and vector checks are not implemented yet.  We just
    1357                 :            :          always return zero for them.  */
    1358                 :          0 :       if (CONST_DOUBLE_AS_FLOAT_P (cst)
    1359                 :          0 :           && real_equal (CONST_DOUBLE_REAL_VALUE (cst), &dconst0))
    1360                 :            :         return 0;
    1361                 :            :       else
    1362                 :          0 :         return 0;
    1363                 :            :     }
    1364                 :            : 
    1365                 :    5068250 :   return cprop_constant_p (cst);
    1366                 :            : }
    1367                 :            : 
    1368                 :            : /* Find the implicit sets of a function.  An "implicit set" is a constraint
    1369                 :            :    on the value of a variable, implied by a conditional jump.  For example,
    1370                 :            :    following "if (x == 2)", the then branch may be optimized as though the
    1371                 :            :    conditional performed an "explicit set", in this example, "x = 2".  This
    1372                 :            :    function records the set patterns that are implicit at the start of each
    1373                 :            :    basic block.
    1374                 :            : 
    1375                 :            :    If an implicit set is found but the set is implicit on a critical edge,
    1376                 :            :    this critical edge is split.
    1377                 :            : 
    1378                 :            :    Return true if the CFG was modified, false otherwise.  */
    1379                 :            : 
    1380                 :            : static bool
    1381                 :    1105620 : find_implicit_sets (void)
    1382                 :            : {
    1383                 :    1105620 :   basic_block bb, dest;
    1384                 :    1105620 :   rtx cond, new_rtx;
    1385                 :    1105620 :   unsigned int count = 0;
    1386                 :    1105620 :   bool edges_split = false;
    1387                 :    1105620 :   size_t implicit_sets_size = last_basic_block_for_fn (cfun) + 10;
    1388                 :            : 
    1389                 :    1105620 :   implicit_sets = XCNEWVEC (rtx, implicit_sets_size);
    1390                 :            : 
    1391                 :   21267100 :   FOR_EACH_BB_FN (bb, cfun)
    1392                 :            :     {
    1393                 :            :       /* Check for more than one successor.  */
    1394                 :   20161400 :       if (EDGE_COUNT (bb->succs) <= 1)
    1395                 :   10254100 :         continue;
    1396                 :            : 
    1397                 :    9907340 :       cond = fis_get_condition (BB_END (bb));
    1398                 :            : 
    1399                 :            :       /* If no condition is found or if it isn't of a suitable form,
    1400                 :            :          ignore it.  */
    1401                 :    9907340 :       if (! cond || ! implicit_set_cond_p (cond))
    1402                 :    6083650 :         continue;
    1403                 :            : 
    1404                 :    7647370 :       dest = GET_CODE (cond) == EQ
    1405                 :    3823690 :         ? BRANCH_EDGE (bb)->dest : FALLTHRU_EDGE (bb)->dest;
    1406                 :            : 
    1407                 :            :       /* If DEST doesn't go anywhere, ignore it.  */
    1408                 :    3823690 :       if (! dest || dest == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1409                 :          0 :         continue;
    1410                 :            : 
    1411                 :            :       /* We have found a suitable implicit set.  Try to record it now as
    1412                 :            :          a SET in DEST.  If DEST has more than one predecessor, the edge
    1413                 :            :          between BB and DEST is a critical edge and we must split it,
    1414                 :            :          because we can only record one implicit set per DEST basic block.  */
    1415                 :    3823690 :       if (! single_pred_p (dest))
    1416                 :            :         {
    1417                 :    1542450 :           dest = split_edge (find_edge (bb, dest));
    1418                 :    1542450 :           edges_split = true;
    1419                 :            :         }
    1420                 :            : 
    1421                 :    3823690 :       if (implicit_sets_size <= (size_t) dest->index)
    1422                 :            :       {
    1423                 :      24829 :         size_t old_implicit_sets_size = implicit_sets_size;
    1424                 :      24829 :         implicit_sets_size *= 2;
    1425                 :      24829 :         implicit_sets = XRESIZEVEC (rtx, implicit_sets, implicit_sets_size);
    1426                 :      24829 :         memset (implicit_sets + old_implicit_sets_size, 0,
    1427                 :      24829 :                 (implicit_sets_size - old_implicit_sets_size) * sizeof (rtx));
    1428                 :            :       }
    1429                 :            : 
    1430                 :    3823690 :       new_rtx = gen_rtx_SET (XEXP (cond, 0), XEXP (cond, 1));
    1431                 :    3823690 :       implicit_sets[dest->index] = new_rtx;
    1432                 :    3823690 :       if (dump_file)
    1433                 :            :         {
    1434                 :         54 :           fprintf (dump_file, "Implicit set of reg %d in ",
    1435                 :         54 :                    REGNO (XEXP (cond, 0)));
    1436                 :         54 :           fprintf (dump_file, "basic block %d\n", dest->index);
    1437                 :            :         }
    1438                 :    3823690 :       count++;
    1439                 :            :     }
    1440                 :            : 
    1441                 :    1105620 :   if (dump_file)
    1442                 :         63 :     fprintf (dump_file, "Found %d implicit sets\n", count);
    1443                 :            : 
    1444                 :            :   /* Confess our sins.  */
    1445                 :    1105620 :   return edges_split;
    1446                 :            : }
    1447                 :            : 
    1448                 :            : /* Bypass conditional jumps.  */
    1449                 :            : 
    1450                 :            : /* The value of last_basic_block at the beginning of the jump_bypass
    1451                 :            :    pass.  The use of redirect_edge_and_branch_force may introduce new
    1452                 :            :    basic blocks, but the data flow analysis is only valid for basic
    1453                 :            :    block indices less than bypass_last_basic_block.  */
    1454                 :            : 
    1455                 :            : static int bypass_last_basic_block;
    1456                 :            : 
    1457                 :            : /* Find a set of REGNO to a constant that is available at the end of basic
    1458                 :            :    block BB.  Return NULL if no such set is found.  Based heavily upon
    1459                 :            :    find_avail_set.  */
    1460                 :            : 
    1461                 :            : static struct cprop_expr *
    1462                 :    1315840 : find_bypass_set (int regno, int bb)
    1463                 :            : {
    1464                 :    1315840 :   struct cprop_expr *result = 0;
    1465                 :            : 
    1466                 :    1473880 :   for (;;)
    1467                 :            :     {
    1468                 :    1394860 :       rtx src;
    1469                 :    1394860 :       struct cprop_expr *set = lookup_set (regno, &set_hash_table);
    1470                 :            : 
    1471                 :    2820580 :       while (set)
    1472                 :            :         {
    1473                 :    1651540 :           if (bitmap_bit_p (cprop_avout[bb], set->bitmap_index))
    1474                 :            :             break;
    1475                 :    4264930 :           set = next_set (regno, set);
    1476                 :            :         }
    1477                 :            : 
    1478                 :    1394860 :       if (set == 0)
    1479                 :            :         break;
    1480                 :            : 
    1481                 :     225825 :       src = set->src;
    1482                 :     225825 :       if (cprop_constant_p (src))
    1483                 :     146805 :         result = set;
    1484                 :            : 
    1485                 :     225825 :       if (! REG_P (src))
    1486                 :            :         break;
    1487                 :            : 
    1488                 :      79020 :       regno = REGNO (src);
    1489                 :      79020 :     }
    1490                 :    1315840 :   return result;
    1491                 :            : }
    1492                 :            : 
    1493                 :            : /* Subroutine of bypass_block that checks whether a pseudo is killed by
    1494                 :            :    any of the instructions inserted on an edge.  Jump bypassing places
    1495                 :            :    condition code setters on CFG edges using insert_insn_on_edge.  This
    1496                 :            :    function is required to check that our data flow analysis is still
    1497                 :            :    valid prior to commit_edge_insertions.  */
    1498                 :            : 
    1499                 :            : static bool
    1500                 :       1883 : reg_killed_on_edge (const_rtx reg, const_edge e)
    1501                 :            : {
    1502                 :       1883 :   rtx_insn *insn;
    1503                 :            : 
    1504                 :      13441 :   for (insn = e->insns.r; insn; insn = NEXT_INSN (insn))
    1505                 :       5779 :     if (INSN_P (insn) && reg_set_p (reg, insn))
    1506                 :            :       return true;
    1507                 :            : 
    1508                 :            :   return false;
    1509                 :            : }
    1510                 :            : 
    1511                 :            : /* Subroutine of bypass_conditional_jumps that attempts to bypass the given
    1512                 :            :    basic block BB which has more than one predecessor.  If not NULL, SETCC
    1513                 :            :    is the first instruction of BB, which is immediately followed by JUMP_INSN
    1514                 :            :    JUMP.  Otherwise, SETCC is NULL, and JUMP is the first insn of BB.
    1515                 :            :    Returns nonzero if a change was made.
    1516                 :            : 
    1517                 :            :    During the jump bypassing pass, we may place copies of SETCC instructions
    1518                 :            :    on CFG edges.  The following routine must be careful to pay attention to
    1519                 :            :    these inserted insns when performing its transformations.  */
    1520                 :            : 
    1521                 :            : static int
    1522                 :     548503 : bypass_block (basic_block bb, rtx_insn *setcc, rtx_insn *jump)
    1523                 :            : {
    1524                 :     548503 :   rtx_insn *insn;
    1525                 :     548503 :   rtx note;
    1526                 :     548503 :   edge e, edest;
    1527                 :     548503 :   int change;
    1528                 :     548503 :   int may_be_loop_header = false;
    1529                 :     548503 :   unsigned removed_p;
    1530                 :     548503 :   unsigned i;
    1531                 :     548503 :   edge_iterator ei;
    1532                 :            : 
    1533                 :     548503 :   insn = (setcc != NULL) ? setcc : jump;
    1534                 :            : 
    1535                 :            :   /* Determine set of register uses in INSN.  */
    1536                 :     548503 :   reg_use_count = 0;
    1537                 :     548503 :   note_uses (&PATTERN (insn), find_used_regs, NULL);
    1538                 :     548503 :   note = find_reg_equal_equiv_note (insn);
    1539                 :     548503 :   if (note)
    1540                 :       2963 :     find_used_regs (&XEXP (note, 0), NULL);
    1541                 :            : 
    1542                 :     548503 :   if (current_loops)
    1543                 :            :     {
    1544                 :            :       /* If we are to preserve loop structure then do not bypass
    1545                 :            :          a loop header.  This will either rotate the loop, create
    1546                 :            :          multiple entry loops or even irreducible regions.  */
    1547                 :     386690 :       if (bb == bb->loop_father->header)
    1548                 :            :         return 0;
    1549                 :            :     }
    1550                 :            :   else
    1551                 :            :     {
    1552                 :     494876 :       FOR_EACH_EDGE (e, ei, bb->preds)
    1553                 :     370470 :         if (e->flags & EDGE_DFS_BACK)
    1554                 :            :           {
    1555                 :            :             may_be_loop_header = true;
    1556                 :            :             break;
    1557                 :            :           }
    1558                 :            :     }
    1559                 :            : 
    1560                 :     475482 :   change = 0;
    1561                 :    1605580 :   for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
    1562                 :            :     {
    1563                 :    1130100 :       removed_p = 0;
    1564                 :            : 
    1565                 :    1130100 :       if (e->flags & EDGE_COMPLEX)
    1566                 :            :         {
    1567                 :       3269 :           ei_next (&ei);
    1568                 :       3269 :           continue;
    1569                 :            :         }
    1570                 :            : 
    1571                 :            :       /* We can't redirect edges from new basic blocks.  */
    1572                 :    1126830 :       if (e->src->index >= bypass_last_basic_block)
    1573                 :            :         {
    1574                 :          0 :           ei_next (&ei);
    1575                 :          0 :           continue;
    1576                 :            :         }
    1577                 :            : 
    1578                 :            :       /* The irreducible loops created by redirecting of edges entering the
    1579                 :            :          loop from outside would decrease effectiveness of some of the
    1580                 :            :          following optimizations, so prevent this.  */
    1581                 :    1126830 :       if (may_be_loop_header
    1582                 :      80349 :           && !(e->flags & EDGE_DFS_BACK))
    1583                 :            :         {
    1584                 :      39408 :           ei_next (&ei);
    1585                 :      39408 :           continue;
    1586                 :            :         }
    1587                 :            : 
    1588                 :    2301520 :       for (i = 0; i < reg_use_count; i++)
    1589                 :            :         {
    1590                 :    1315840 :           rtx reg_used = reg_use_table[i];
    1591                 :    1315840 :           unsigned int regno = REGNO (reg_used);
    1592                 :    1315840 :           basic_block dest, old_dest;
    1593                 :    1315840 :           struct cprop_expr *set;
    1594                 :    1315840 :           rtx src, new_rtx;
    1595                 :            : 
    1596                 :    1315840 :           set = find_bypass_set (regno, e->src->index);
    1597                 :            : 
    1598                 :    1315840 :           if (! set)
    1599                 :    1169040 :             continue;
    1600                 :            : 
    1601                 :            :           /* Check the data flow is valid after edge insertions.  */
    1602                 :     146805 :           if (e->insns.r && reg_killed_on_edge (reg_used, e))
    1603                 :          0 :             continue;
    1604                 :            : 
    1605                 :     146805 :           src = SET_SRC (pc_set (jump));
    1606                 :            : 
    1607                 :     146805 :           if (setcc != NULL)
    1608                 :     146777 :             src = simplify_replace_rtx (src,
    1609                 :     146777 :                                         SET_DEST (PATTERN (setcc)),
    1610                 :     146777 :                                         SET_SRC (PATTERN (setcc)));
    1611                 :            : 
    1612                 :     146805 :           new_rtx = simplify_replace_rtx (src, reg_used, set->src);
    1613                 :            : 
    1614                 :            :           /* Jump bypassing may have already placed instructions on
    1615                 :            :              edges of the CFG.  We can't bypass an outgoing edge that
    1616                 :            :              has instructions associated with it, as these insns won't
    1617                 :            :              get executed if the incoming edge is redirected.  */
    1618                 :     146805 :           if (new_rtx == pc_rtx)
    1619                 :            :             {
    1620                 :      52326 :               edest = FALLTHRU_EDGE (bb);
    1621                 :      52326 :               dest = edest->insns.r ? NULL : edest->dest;
    1622                 :            :             }
    1623                 :      94479 :           else if (GET_CODE (new_rtx) == LABEL_REF)
    1624                 :            :             {
    1625                 :      49427 :               dest = BLOCK_FOR_INSN (XEXP (new_rtx, 0));
    1626                 :            :               /* Don't bypass edges containing instructions.  */
    1627                 :      49427 :               edest = find_edge (bb, dest);
    1628                 :      49427 :               if (edest && edest->insns.r)
    1629                 :          1 :                 dest = NULL;
    1630                 :            :             }
    1631                 :            :           else
    1632                 :            :             dest = NULL;
    1633                 :            : 
    1634                 :            :           /* Avoid unification of the edge with other edges from original
    1635                 :            :              branch.  We would end up emitting the instruction on "both"
    1636                 :            :              edges.  */
    1637                 :     248545 :           if (dest && setcc && !CC0_P (SET_DEST (PATTERN (setcc)))
    1638                 :     146805 :               && find_edge (e->src, dest))
    1639                 :            :             dest = NULL;
    1640                 :            : 
    1641                 :     146805 :           old_dest = e->dest;
    1642                 :     146805 :           if (dest != NULL
    1643                 :     146805 :               && dest != old_dest
    1644                 :     101743 :               && dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
    1645                 :            :             {
    1646                 :     101743 :               redirect_edge_and_branch_force (e, dest);
    1647                 :            : 
    1648                 :            :               /* Copy the register setter to the redirected edge.
    1649                 :            :                  Don't copy CC0 setters, as CC0 is dead after jump.  */
    1650                 :     101743 :               if (setcc)
    1651                 :            :                 {
    1652                 :     101731 :                   rtx pat = PATTERN (setcc);
    1653                 :     101731 :                   if (!CC0_P (SET_DEST (pat)))
    1654                 :     101731 :                     insert_insn_on_edge (copy_insn (pat), e);
    1655                 :            :                 }
    1656                 :            : 
    1657                 :     101743 :               if (dump_file != NULL)
    1658                 :            :                 {
    1659                 :          0 :                   fprintf (dump_file, "JUMP-BYPASS: Proved reg %d "
    1660                 :            :                                       "in jump_insn %d equals constant ",
    1661                 :          0 :                            regno, INSN_UID (jump));
    1662                 :          0 :                   print_rtl (dump_file, set->src);
    1663                 :          0 :                   fprintf (dump_file, "\n\t     when BB %d is entered from "
    1664                 :            :                                       "BB %d.  Redirect edge %d->%d to %d.\n",
    1665                 :          0 :                            old_dest->index, e->src->index, e->src->index,
    1666                 :            :                            old_dest->index, dest->index);
    1667                 :            :                 }
    1668                 :            :               change = 1;
    1669                 :            :               removed_p = 1;
    1670                 :            :               break;
    1671                 :            :             }
    1672                 :            :         }
    1673                 :     985682 :       if (!removed_p)
    1674                 :     985682 :         ei_next (&ei);
    1675                 :            :     }
    1676                 :            :   return change;
    1677                 :            : }
    1678                 :            : 
    1679                 :            : /* Find basic blocks with more than one predecessor that only contain a
    1680                 :            :    single conditional jump.  If the result of the comparison is known at
    1681                 :            :    compile-time from any incoming edge, redirect that edge to the
    1682                 :            :    appropriate target.  Return nonzero if a change was made.
    1683                 :            : 
    1684                 :            :    This function is now mis-named, because we also handle indirect jumps.  */
    1685                 :            : 
    1686                 :            : static int
    1687                 :     993124 : bypass_conditional_jumps (void)
    1688                 :            : {
    1689                 :     993124 :   basic_block bb;
    1690                 :     993124 :   int changed;
    1691                 :     993124 :   rtx_insn *setcc;
    1692                 :     993124 :   rtx_insn *insn;
    1693                 :     993124 :   rtx dest;
    1694                 :            : 
    1695                 :            :   /* Note we start at block 1.  */
    1696                 :     993124 :   if (ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb == EXIT_BLOCK_PTR_FOR_FN (cfun))
    1697                 :            :     return 0;
    1698                 :            : 
    1699                 :     993124 :   mark_dfs_back_edges ();
    1700                 :            : 
    1701                 :     993124 :   changed = 0;
    1702                 :   19599500 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
    1703                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
    1704                 :            :     {
    1705                 :            :       /* Check for more than one predecessor.  */
    1706                 :   18606300 :       if (!single_pred_p (bb))
    1707                 :            :         {
    1708                 :    5009300 :           setcc = NULL;
    1709                 :   70358500 :           FOR_BB_INSNS (bb, insn)
    1710                 :   37254800 :             if (DEBUG_INSN_P (insn))
    1711                 :   19794600 :               continue;
    1712                 :   17460200 :             else if (NONJUMP_INSN_P (insn))
    1713                 :            :               {
    1714                 :    6499730 :                 if (setcc)
    1715                 :            :                   break;
    1716                 :    4626360 :                 if (GET_CODE (PATTERN (insn)) != SET)
    1717                 :            :                   break;
    1718                 :            : 
    1719                 :    3555540 :                 dest = SET_DEST (PATTERN (insn));
    1720                 :    3555540 :                 if (REG_P (dest) || CC0_P (dest))
    1721                 :            :                   setcc = insn;
    1722                 :            :                 else
    1723                 :            :                   break;
    1724                 :            :               }
    1725                 :   10960400 :             else if (JUMP_P (insn))
    1726                 :            :               {
    1727                 :     548721 :                 if ((any_condjump_p (insn) || computed_jump_p (insn))
    1728                 :     548694 :                     && onlyjump_p (insn))
    1729                 :     548503 :                   changed |= bypass_block (bb, setcc, insn);
    1730                 :            :                 break;
    1731                 :            :               }
    1732                 :   10411900 :             else if (INSN_P (insn))
    1733                 :            :               break;
    1734                 :            :         }
    1735                 :            :     }
    1736                 :            : 
    1737                 :            :   /* If we bypassed any register setting insns, we inserted a
    1738                 :            :      copy on the redirected edge.  These need to be committed.  */
    1739                 :     993124 :   if (changed)
    1740                 :      38586 :     commit_edge_insertions ();
    1741                 :            : 
    1742                 :            :   return changed;
    1743                 :            : }
    1744                 :            : 
    1745                 :            : /* Main function for the CPROP pass.  */
    1746                 :            : 
    1747                 :            : static int
    1748                 :    1931380 : one_cprop_pass (void)
    1749                 :            : {
    1750                 :    1931380 :   int i;
    1751                 :    1931380 :   int changed = 0;
    1752                 :            : 
    1753                 :            :   /* Return if there's nothing to do, or it is too expensive.  */
    1754                 :    1931380 :   if (n_basic_blocks_for_fn (cfun) <= NUM_FIXED_BLOCKS + 1
    1755                 :    1931380 :       || gcse_or_cprop_is_too_expensive (_ ("const/copy propagation disabled")))
    1756                 :     825759 :     return 0;
    1757                 :            : 
    1758                 :    1105620 :   global_const_prop_count = local_const_prop_count = 0;
    1759                 :    1105620 :   global_copy_prop_count = local_copy_prop_count = 0;
    1760                 :            : 
    1761                 :    1105620 :   bytes_used = 0;
    1762                 :    1105620 :   gcc_obstack_init (&cprop_obstack);
    1763                 :            : 
    1764                 :            :   /* Do a local const/copy propagation pass first.  The global pass
    1765                 :            :      only handles global opportunities.
    1766                 :            :      If the local pass changes something, remove any unreachable blocks
    1767                 :            :      because the CPROP global dataflow analysis may get into infinite
    1768                 :            :      loops for CFGs with unreachable blocks.
    1769                 :            : 
    1770                 :            :      FIXME: This local pass should not be necessary after CSE (but for
    1771                 :            :             some reason it still is).  It is also (proven) not necessary
    1772                 :            :             to run the local pass right after FWPWOP.
    1773                 :            : 
    1774                 :            :      FIXME: The global analysis would not get into infinite loops if it
    1775                 :            :             would use the DF solver (via df_simple_dataflow) instead of
    1776                 :            :             the solver implemented in this file.  */
    1777                 :    1105620 :   changed |= local_cprop_pass ();
    1778                 :    1105620 :   if (changed)
    1779                 :     149764 :     delete_unreachable_blocks ();
    1780                 :            : 
    1781                 :            :   /* Determine implicit sets.  This may change the CFG (split critical
    1782                 :            :      edges if that exposes an implicit set).
    1783                 :            :      Note that find_implicit_sets() does not rely on up-to-date DF caches
    1784                 :            :      so that we do not have to re-run df_analyze() even if local CPROP
    1785                 :            :      changed something.
    1786                 :            :      ??? This could run earlier so that any uncovered implicit sets
    1787                 :            :          sets could be exploited in local_cprop_pass() also.  Later.  */
    1788                 :    1105620 :   changed |= find_implicit_sets ();
    1789                 :            : 
    1790                 :            :   /* If local_cprop_pass() or find_implicit_sets() changed something,
    1791                 :            :      run df_analyze() to bring all insn caches up-to-date, and to take
    1792                 :            :      new basic blocks from edge splitting on the DF radar.
    1793                 :            :      NB: This also runs the fast DCE pass, because execute_rtl_cprop
    1794                 :            :      sets DF_LR_RUN_DCE.  */
    1795                 :    1105620 :   if (changed)
    1796                 :     484176 :     df_analyze ();
    1797                 :            : 
    1798                 :            :   /* Initialize implicit_set_indexes array.  */
    1799                 :    1105620 :   implicit_set_indexes = XNEWVEC (int, last_basic_block_for_fn (cfun));
    1800                 :   24257800 :   for (i = 0; i < last_basic_block_for_fn (cfun); i++)
    1801                 :   23152200 :     implicit_set_indexes[i] = -1;
    1802                 :            : 
    1803                 :    1105620 :   alloc_hash_table (&set_hash_table);
    1804                 :    1105620 :   compute_hash_table (&set_hash_table);
    1805                 :            : 
    1806                 :            :   /* Free implicit_sets before peak usage.  */
    1807                 :    1105620 :   free (implicit_sets);
    1808                 :    1105620 :   implicit_sets = NULL;
    1809                 :            : 
    1810                 :    1105620 :   if (dump_file)
    1811                 :         63 :     dump_hash_table (dump_file, "SET", &set_hash_table);
    1812                 :    1105620 :   if (set_hash_table.n_elems > 0)
    1813                 :            :     {
    1814                 :     993124 :       basic_block bb;
    1815                 :    1986250 :       auto_vec<rtx_insn *> uncond_traps;
    1816                 :            : 
    1817                 :     993124 :       alloc_cprop_mem (last_basic_block_for_fn (cfun),
    1818                 :            :                        set_hash_table.n_elems);
    1819                 :     993124 :       compute_cprop_data ();
    1820                 :            : 
    1821                 :     993124 :       free (implicit_set_indexes);
    1822                 :     993124 :       implicit_set_indexes = NULL;
    1823                 :            : 
    1824                 :            :       /* Allocate vars to track sets of regs.  */
    1825                 :     993124 :       reg_set_bitmap = ALLOC_REG_SET (NULL);
    1826                 :            : 
    1827                 :   19599500 :       FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb->next_bb,
    1828                 :            :                       EXIT_BLOCK_PTR_FOR_FN (cfun),
    1829                 :            :                       next_bb)
    1830                 :            :         {
    1831                 :   18606300 :           bool seen_uncond_trap = false;
    1832                 :   18606300 :           rtx_insn *insn;
    1833                 :            : 
    1834                 :            :           /* Reset tables used to keep track of what's still valid [since
    1835                 :            :              the start of the block].  */
    1836                 :   18606300 :           reset_opr_set_tables ();
    1837                 :            : 
    1838                 :  203820000 :           FOR_BB_INSNS (bb, insn)
    1839                 :  185213000 :             if (INSN_P (insn))
    1840                 :            :               {
    1841                 :  156359000 :                 bool was_uncond_trap
    1842                 :  156359000 :                   = (GET_CODE (PATTERN (insn)) == TRAP_IF
    1843                 :  156359000 :                      && XEXP (PATTERN (insn), 0) == const1_rtx);
    1844                 :            : 
    1845                 :  156359000 :                 changed |= cprop_insn (insn);
    1846                 :            : 
    1847                 :            :                 /* Keep track of everything modified by this insn.  */
    1848                 :            :                 /* ??? Need to be careful w.r.t. mods done to INSN.
    1849                 :            :                        Don't call mark_oprs_set if we turned the
    1850                 :            :                        insn into a NOTE, or deleted the insn.  */
    1851                 :  156359000 :                 if (! NOTE_P (insn) && ! insn->deleted ())
    1852                 :  156359000 :                   mark_oprs_set (insn);
    1853                 :            : 
    1854                 :  156359000 :                 if (!was_uncond_trap
    1855                 :  156350000 :                     && GET_CODE (PATTERN (insn)) == TRAP_IF
    1856                 :  156359000 :                     && XEXP (PATTERN (insn), 0) == const1_rtx)
    1857                 :            :                   {
    1858                 :            :                     /* If we have already seen an unconditional trap
    1859                 :            :                        earlier, the rest of the bb is going to be removed
    1860                 :            :                        as unreachable.  Just turn it into a note, so that
    1861                 :            :                        RTL verification doesn't complain about it before
    1862                 :            :                        it is finally removed.  */
    1863                 :          0 :                     if (seen_uncond_trap)
    1864                 :          0 :                       set_insn_deleted (insn);
    1865                 :            :                     else
    1866                 :            :                       {
    1867                 :          0 :                         seen_uncond_trap = true;
    1868                 :          0 :                         uncond_traps.safe_push (insn);
    1869                 :            :                       }
    1870                 :            :                   }
    1871                 :            :               }
    1872                 :            :         }
    1873                 :            : 
    1874                 :            :       /* Make sure bypass_conditional_jumps will ignore not just its new
    1875                 :            :          basic blocks, but also the ones after unconditional traps (those are
    1876                 :            :          unreachable and will be eventually removed as such).  */
    1877                 :     993124 :       bypass_last_basic_block = last_basic_block_for_fn (cfun);
    1878                 :            : 
    1879                 :     993124 :       while (!uncond_traps.is_empty ())
    1880                 :            :         {
    1881                 :          0 :           rtx_insn *insn = uncond_traps.pop ();
    1882                 :          0 :           basic_block to_split = BLOCK_FOR_INSN (insn);
    1883                 :          0 :           remove_edge (split_block (to_split, insn));
    1884                 :          0 :           emit_barrier_after_bb (to_split);
    1885                 :            :         }
    1886                 :            : 
    1887                 :     993124 :       changed |= bypass_conditional_jumps ();
    1888                 :            : 
    1889                 :     993124 :       FREE_REG_SET (reg_set_bitmap);
    1890                 :     993124 :       free_cprop_mem ();
    1891                 :            :     }
    1892                 :            :   else
    1893                 :            :     {
    1894                 :     112493 :       free (implicit_set_indexes);
    1895                 :     112493 :       implicit_set_indexes = NULL;
    1896                 :            :     }
    1897                 :            : 
    1898                 :    1105620 :   free_hash_table (&set_hash_table);
    1899                 :    1105620 :   obstack_free (&cprop_obstack, NULL);
    1900                 :            : 
    1901                 :    1105620 :   if (dump_file)
    1902                 :            :     {
    1903                 :         63 :       fprintf (dump_file, "CPROP of %s, %d basic blocks, %d bytes needed, ",
    1904                 :         63 :                current_function_name (), n_basic_blocks_for_fn (cfun),
    1905                 :            :                bytes_used);
    1906                 :         63 :       fprintf (dump_file, "%d local const props, %d local copy props, ",
    1907                 :            :                local_const_prop_count, local_copy_prop_count);
    1908                 :         63 :       fprintf (dump_file, "%d global const props, %d global copy props\n\n",
    1909                 :            :                global_const_prop_count, global_copy_prop_count);
    1910                 :            :     }
    1911                 :            : 
    1912                 :            :   return changed;
    1913                 :            : }
    1914                 :            : 
    1915                 :            : /* All the passes implemented in this file.  Each pass has its
    1916                 :            :    own gate and execute function, and at the end of the file a
    1917                 :            :    pass definition for passes.c.
    1918                 :            : 
    1919                 :            :    We do not construct an accurate cfg in functions which call
    1920                 :            :    setjmp, so none of these passes runs if the function calls
    1921                 :            :    setjmp.
    1922                 :            :    FIXME: Should just handle setjmp via REG_SETJMP notes.  */
    1923                 :            : 
    1924                 :            : static unsigned int
    1925                 :    1931380 : execute_rtl_cprop (void)
    1926                 :            : {
    1927                 :    1931380 :   int changed;
    1928                 :    1931380 :   delete_unreachable_blocks ();
    1929                 :    1931380 :   df_set_flags (DF_LR_RUN_DCE);
    1930                 :    1931380 :   df_analyze ();
    1931                 :    1931380 :   changed = one_cprop_pass ();
    1932                 :    1931380 :   flag_rerun_cse_after_global_opts |= changed;
    1933                 :    1931380 :   if (changed)
    1934                 :     509504 :     cleanup_cfg (CLEANUP_CFG_CHANGED);
    1935                 :    1931380 :   return 0;
    1936                 :            : }
    1937                 :            : 
    1938                 :            : namespace {
    1939                 :            : 
    1940                 :            : const pass_data pass_data_rtl_cprop =
    1941                 :            : {
    1942                 :            :   RTL_PASS, /* type */
    1943                 :            :   "cprop", /* name */
    1944                 :            :   OPTGROUP_NONE, /* optinfo_flags */
    1945                 :            :   TV_CPROP, /* tv_id */
    1946                 :            :   PROP_cfglayout, /* properties_required */
    1947                 :            :   0, /* properties_provided */
    1948                 :            :   0, /* properties_destroyed */
    1949                 :            :   0, /* todo_flags_start */
    1950                 :            :   TODO_df_finish, /* todo_flags_finish */
    1951                 :            : };
    1952                 :            : 
    1953                 :            : class pass_rtl_cprop : public rtl_opt_pass
    1954                 :            : {
    1955                 :            : public:
    1956                 :     601620 :   pass_rtl_cprop (gcc::context *ctxt)
    1957                 :    1203240 :     : rtl_opt_pass (pass_data_rtl_cprop, ctxt)
    1958                 :            :   {}
    1959                 :            : 
    1960                 :            :   /* opt_pass methods: */
    1961                 :     401080 :   opt_pass * clone () { return new pass_rtl_cprop (m_ctxt); }
    1962                 :    2828890 :   virtual bool gate (function *fun)
    1963                 :            :     {
    1964                 :    2062280 :       return optimize > 0 && flag_gcse
    1965                 :    1932660 :         && !fun->calls_setjmp
    1966                 :    4760270 :         && dbg_cnt (cprop);
    1967                 :            :     }
    1968                 :            : 
    1969                 :    1931380 :   virtual unsigned int execute (function *) { return execute_rtl_cprop (); }
    1970                 :            : 
    1971                 :            : }; // class pass_rtl_cprop
    1972                 :            : 
    1973                 :            : } // anon namespace
    1974                 :            : 
    1975                 :            : rtl_opt_pass *
    1976                 :     200540 : make_pass_rtl_cprop (gcc::context *ctxt)
    1977                 :            : {
    1978                 :     200540 :   return new pass_rtl_cprop (ctxt);
    1979                 :            : }

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.