LCOV - code coverage report
Current view: top level - gcc - df-problems.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 1556 1883 82.6 %
Date: 2020-03-28 11:57:23 Functions: 121 146 82.9 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Standard problems for dataflow support routines.
       2                 :            :    Copyright (C) 1999-2020 Free Software Foundation, Inc.
       3                 :            :    Originally contributed by Michael P. Hayes
       4                 :            :              (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
       5                 :            :    Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
       6                 :            :              and Kenneth Zadeck (zadeck@naturalbridge.com).
       7                 :            : 
       8                 :            : This file is part of GCC.
       9                 :            : 
      10                 :            : GCC is free software; you can redistribute it and/or modify it under
      11                 :            : the terms of the GNU General Public License as published by the Free
      12                 :            : Software Foundation; either version 3, or (at your option) any later
      13                 :            : version.
      14                 :            : 
      15                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      16                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      17                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      18                 :            : for more details.
      19                 :            : 
      20                 :            : You should have received a copy of the GNU General Public License
      21                 :            : along with GCC; see the file COPYING3.  If not see
      22                 :            : <http://www.gnu.org/licenses/>.  */
      23                 :            : 
      24                 :            : #include "config.h"
      25                 :            : #include "system.h"
      26                 :            : #include "coretypes.h"
      27                 :            : #include "backend.h"
      28                 :            : #include "target.h"
      29                 :            : #include "rtl.h"
      30                 :            : #include "df.h"
      31                 :            : #include "memmodel.h"
      32                 :            : #include "tm_p.h"
      33                 :            : #include "insn-config.h"
      34                 :            : #include "cfganal.h"
      35                 :            : #include "dce.h"
      36                 :            : #include "valtrack.h"
      37                 :            : #include "dumpfile.h"
      38                 :            : #include "rtl-iter.h"
      39                 :            : #include "regs.h"
      40                 :            : #include "function-abi.h"
      41                 :            : 
      42                 :            : /* Note that turning REG_DEAD_DEBUGGING on will cause
      43                 :            :    gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
      44                 :            :    addresses in the dumps.  */
      45                 :            : #define REG_DEAD_DEBUGGING 0
      46                 :            : 
      47                 :            : #define DF_SPARSE_THRESHOLD 32
      48                 :            : 
      49                 :            : static bitmap_head seen_in_block;
      50                 :            : static bitmap_head seen_in_insn;
      51                 :            : 
      52                 :            : /*----------------------------------------------------------------------------
      53                 :            :    Utility functions.
      54                 :            : ----------------------------------------------------------------------------*/
      55                 :            : 
      56                 :            : /* Generic versions to get the void* version of the block info.  Only
      57                 :            :    used inside the problem instance vectors.  */
      58                 :            : 
      59                 :            : /* Dump a def-use or use-def chain for REF to FILE.  */
      60                 :            : 
      61                 :            : void
      62                 :      23383 : df_chain_dump (struct df_link *link, FILE *file)
      63                 :            : {
      64                 :      23383 :   fprintf (file, "{ ");
      65                 :      26253 :   for (; link; link = link->next)
      66                 :            :     {
      67                 :       2870 :       fprintf (file, "%c%d(bb %d insn %d) ",
      68                 :       2870 :                DF_REF_REG_DEF_P (link->ref)
      69                 :          0 :                ? 'd'
      70                 :          0 :                : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
      71                 :            :                DF_REF_ID (link->ref),
      72                 :       2870 :                DF_REF_BBNO (link->ref),
      73                 :       2870 :                DF_REF_IS_ARTIFICIAL (link->ref)
      74                 :       1330 :                ? -1 : DF_REF_INSN_UID (link->ref));
      75                 :            :     }
      76                 :      23383 :   fprintf (file, "}");
      77                 :      23383 : }
      78                 :            : 
      79                 :            : 
      80                 :            : /* Print some basic block info as part of df_dump.  */
      81                 :            : 
      82                 :            : void
      83                 :       3042 : df_print_bb_index (basic_block bb, FILE *file)
      84                 :            : {
      85                 :       3042 :   edge e;
      86                 :       3042 :   edge_iterator ei;
      87                 :            : 
      88                 :       3042 :   fprintf (file, "\n( ");
      89                 :       6839 :     FOR_EACH_EDGE (e, ei, bb->preds)
      90                 :            :     {
      91                 :       3797 :       basic_block pred = e->src;
      92                 :       7594 :       fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
      93                 :            :     }
      94                 :       3042 :   fprintf (file, ")->[%d]->( ", bb->index);
      95                 :       6839 :   FOR_EACH_EDGE (e, ei, bb->succs)
      96                 :            :     {
      97                 :       3797 :       basic_block succ = e->dest;
      98                 :       7594 :       fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
      99                 :            :     }
     100                 :       3042 :   fprintf (file, ")\n");
     101                 :       3042 : }
     102                 :            : 
     103                 :            : 
     104                 :            : /*----------------------------------------------------------------------------
     105                 :            :    REACHING DEFINITIONS
     106                 :            : 
     107                 :            :    Find the locations in the function where each definition site for a
     108                 :            :    pseudo reaches.  In and out bitvectors are built for each basic
     109                 :            :    block.  The id field in the ref is used to index into these sets.
     110                 :            :    See df.h for details.
     111                 :            : 
     112                 :            :    If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
     113                 :            :    existing uses are included in the global reaching DEFs set, or in other
     114                 :            :    words only DEFs that are still live.  This is a kind of pruned version
     115                 :            :    of the traditional reaching definitions problem that is much less
     116                 :            :    complex to compute and produces enough information to compute UD-chains.
     117                 :            :    In this context, live must be interpreted in the DF_LR sense: Uses that
     118                 :            :    are upward exposed but maybe not initialized on all paths through the
     119                 :            :    CFG.  For a USE that is not reached by a DEF on all paths, we still want
     120                 :            :    to make those DEFs that do reach the USE visible, and pruning based on
     121                 :            :    DF_LIVE would make that impossible.
     122                 :            :    ----------------------------------------------------------------------------*/
     123                 :            : 
     124                 :            : /* This problem plays a large number of games for the sake of
     125                 :            :    efficiency.
     126                 :            : 
     127                 :            :    1) The order of the bits in the bitvectors.  After the scanning
     128                 :            :    phase, all of the defs are sorted.  All of the defs for the reg 0
     129                 :            :    are first, followed by all defs for reg 1 and so on.
     130                 :            : 
     131                 :            :    2) There are two kill sets, one if the number of defs is less or
     132                 :            :    equal to DF_SPARSE_THRESHOLD and another if the number of defs is
     133                 :            :    greater.
     134                 :            : 
     135                 :            :    <= : Data is built directly in the kill set.
     136                 :            : 
     137                 :            :    > : One level of indirection is used to keep from generating long
     138                 :            :    strings of 1 bits in the kill sets.  Bitvectors that are indexed
     139                 :            :    by the regnum are used to represent that there is a killing def
     140                 :            :    for the register.  The confluence and transfer functions use
     141                 :            :    these along with the bitmap_clear_range call to remove ranges of
     142                 :            :    bits without actually generating a knockout vector.
     143                 :            : 
     144                 :            :    The kill and sparse_kill and the dense_invalidated_by_eh and
     145                 :            :    sparse_invalidated_by_eh both play this game.  */
     146                 :            : 
     147                 :            : /* Private data used to compute the solution for this problem.  These
     148                 :            :    data structures are not accessible outside of this module.  */
     149                 :            : class df_rd_problem_data
     150                 :            : {
     151                 :            : public:
     152                 :            :   /* The set of defs to regs invalidated by EH edges.  */
     153                 :            :   bitmap_head sparse_invalidated_by_eh;
     154                 :            :   bitmap_head dense_invalidated_by_eh;
     155                 :            :   /* An obstack for the bitmaps we need for this problem.  */
     156                 :            :   bitmap_obstack rd_bitmaps;
     157                 :            : };
     158                 :            : 
     159                 :            : 
     160                 :            : /* Free basic block info.  */
     161                 :            : 
     162                 :            : static void
     163                 :    1105280 : df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
     164                 :            :                     void *vbb_info)
     165                 :            : {
     166                 :    1105280 :   class df_rd_bb_info *bb_info = (class df_rd_bb_info *) vbb_info;
     167                 :    1105280 :   if (bb_info)
     168                 :            :     {
     169                 :    1105280 :       bitmap_clear (&bb_info->kill);
     170                 :    1105280 :       bitmap_clear (&bb_info->sparse_kill);
     171                 :    1105280 :       bitmap_clear (&bb_info->gen);
     172                 :    1105280 :       bitmap_clear (&bb_info->in);
     173                 :    1105280 :       bitmap_clear (&bb_info->out);
     174                 :            :     }
     175                 :    1105280 : }
     176                 :            : 
     177                 :            : 
     178                 :            : /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
     179                 :            :    not touched unless the block is new.  */
     180                 :            : 
     181                 :            : static void
     182                 :    2873100 : df_rd_alloc (bitmap all_blocks)
     183                 :            : {
     184                 :    2873100 :   unsigned int bb_index;
     185                 :    2873100 :   bitmap_iterator bi;
     186                 :    2873100 :   class df_rd_problem_data *problem_data;
     187                 :            : 
     188                 :    2873100 :   if (df_rd->problem_data)
     189                 :            :     {
     190                 :     246868 :       problem_data = (class df_rd_problem_data *) df_rd->problem_data;
     191                 :     246868 :       bitmap_clear (&problem_data->sparse_invalidated_by_eh);
     192                 :     246868 :       bitmap_clear (&problem_data->dense_invalidated_by_eh);
     193                 :            :     }
     194                 :            :   else
     195                 :            :     {
     196                 :    2626230 :       problem_data = XNEW (class df_rd_problem_data);
     197                 :    2626230 :       df_rd->problem_data = problem_data;
     198                 :            : 
     199                 :    2626230 :       bitmap_obstack_initialize (&problem_data->rd_bitmaps);
     200                 :    2626230 :       bitmap_initialize (&problem_data->sparse_invalidated_by_eh,
     201                 :            :                          &problem_data->rd_bitmaps);
     202                 :    2626230 :       bitmap_initialize (&problem_data->dense_invalidated_by_eh,
     203                 :            :                          &problem_data->rd_bitmaps);
     204                 :            :     }
     205                 :            : 
     206                 :    2873100 :   df_grow_bb_info (df_rd);
     207                 :            : 
     208                 :            :   /* Because of the clustering of all use sites for the same pseudo,
     209                 :            :      we have to process all of the blocks before doing the analysis.  */
     210                 :            : 
     211                 :   35089500 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     212                 :            :     {
     213                 :   32216400 :       class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
     214                 :            :       
     215                 :            :       /* When bitmaps are already initialized, just clear them.  */
     216                 :   32216400 :       if (bb_info->kill.obstack)
     217                 :            :         {
     218                 :     604437 :           bitmap_clear (&bb_info->kill);
     219                 :     604437 :           bitmap_clear (&bb_info->sparse_kill);
     220                 :     604437 :           bitmap_clear (&bb_info->gen);
     221                 :            :         }
     222                 :            :       else
     223                 :            :         {
     224                 :   31612000 :           bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
     225                 :   31612000 :           bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
     226                 :   31612000 :           bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
     227                 :   31612000 :           bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
     228                 :   32216400 :           bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
     229                 :            :         }
     230                 :            :     }
     231                 :    2873100 :   df_rd->optional_p = true;
     232                 :    2873100 : }
     233                 :            : 
     234                 :            : 
     235                 :            : /* Add the effect of the top artificial defs of BB to the reaching definitions
     236                 :            :    bitmap LOCAL_RD.  */
     237                 :            : 
     238                 :            : void
     239                 :   32216400 : df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
     240                 :            : {
     241                 :   32216400 :   int bb_index = bb->index;
     242                 :   32216400 :   df_ref def;
     243                 :  108977000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
     244                 :   44544500 :     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
     245                 :            :       {
     246                 :    1023690 :         unsigned int dregno = DF_REF_REGNO (def);
     247                 :    1023690 :         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
     248                 :    1023690 :           bitmap_clear_range (local_rd,
     249                 :    1023690 :                               DF_DEFS_BEGIN (dregno),
     250                 :    1023690 :                               DF_DEFS_COUNT (dregno));
     251                 :    1023690 :         bitmap_set_bit (local_rd, DF_REF_ID (def));
     252                 :            :       }
     253                 :   32216400 : }
     254                 :            : 
     255                 :            : /* Add the effect of the defs of INSN to the reaching definitions bitmap
     256                 :            :    LOCAL_RD.  */
     257                 :            : 
     258                 :            : void
     259                 :  269873000 : df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
     260                 :            :                          bitmap local_rd)
     261                 :            : {
     262                 :  269873000 :   df_ref def;
     263                 :            : 
     264                 : 1182390000 :   FOR_EACH_INSN_DEF (def, insn)
     265                 :            :     {
     266                 :  912513000 :       unsigned int dregno = DF_REF_REGNO (def);
     267                 :  912513000 :       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
     268                 :    9397260 :           || (dregno >= FIRST_PSEUDO_REGISTER))
     269                 :            :         {
     270                 :  904461000 :           if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
     271                 :  903978000 :             bitmap_clear_range (local_rd,
     272                 :  903978000 :                                 DF_DEFS_BEGIN (dregno),
     273                 :  903978000 :                                 DF_DEFS_COUNT (dregno));
     274                 :  904461000 :           if (!(DF_REF_FLAGS (def)
     275                 :            :                 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
     276                 :  108600000 :             bitmap_set_bit (local_rd, DF_REF_ID (def));
     277                 :            :         }
     278                 :            :     }
     279                 :  269873000 : }
     280                 :            : 
     281                 :            : /* Process a list of DEFs for df_rd_bb_local_compute.  This is a bit
     282                 :            :    more complicated than just simulating, because we must produce the
     283                 :            :    gen and kill sets and hence deal with the two possible representations
     284                 :            :    of kill sets.   */
     285                 :            : 
     286                 :            : static void
     287                 :  333555000 : df_rd_bb_local_compute_process_def (class df_rd_bb_info *bb_info,
     288                 :            :                                     df_ref def,
     289                 :            :                                     int top_flag)
     290                 :            : {
     291                 : 1334560000 :   for (; def; def = DF_REF_NEXT_LOC (def))
     292                 :            :     {
     293                 : 1001000000 :       if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
     294                 :            :         {
     295                 :  956758000 :           unsigned int regno = DF_REF_REGNO (def);
     296                 :  956758000 :           unsigned int begin = DF_DEFS_BEGIN (regno);
     297                 :  956758000 :           unsigned int n_defs = DF_DEFS_COUNT (regno);
     298                 :            : 
     299                 :  956758000 :           if ((!(df->changeable_flags & DF_NO_HARD_REGS))
     300                 :    9397260 :               || (regno >= FIRST_PSEUDO_REGISTER))
     301                 :            :             {
     302                 :            :               /* Only the last def(s) for a regno in the block has any
     303                 :            :                  effect.  */
     304                 :  948705000 :               if (!bitmap_bit_p (&seen_in_block, regno))
     305                 :            :                 {
     306                 :            :                   /* The first def for regno in insn gets to knock out the
     307                 :            :                      defs from other instructions.  */
     308                 :  679835000 :                   if ((!bitmap_bit_p (&seen_in_insn, regno))
     309                 :            :                       /* If the def is to only part of the reg, it does
     310                 :            :                          not kill the other defs that reach here.  */
     311                 :  679835000 :                       && (!(DF_REF_FLAGS (def) &
     312                 :            :                             (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
     313                 :            :                     {
     314                 :  119344000 :                       if (n_defs > DF_SPARSE_THRESHOLD)
     315                 :            :                         {
     316                 :   17446200 :                           bitmap_set_bit (&bb_info->sparse_kill, regno);
     317                 :   17446200 :                           bitmap_clear_range (&bb_info->gen, begin, n_defs);
     318                 :            :                         }
     319                 :            :                       else
     320                 :            :                         {
     321                 :  101897000 :                           bitmap_set_range (&bb_info->kill, begin, n_defs);
     322                 :  101897000 :                           bitmap_clear_range (&bb_info->gen, begin, n_defs);
     323                 :            :                         }
     324                 :            :                     }
     325                 :            : 
     326                 :  679835000 :                   bitmap_set_bit (&seen_in_insn, regno);
     327                 :            :                   /* All defs for regno in the instruction may be put into
     328                 :            :                      the gen set.  */
     329                 :  679835000 :                   if (!(DF_REF_FLAGS (def)
     330                 :            :                         & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
     331                 :  116581000 :                     bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
     332                 :            :                 }
     333                 :            :             }
     334                 :            :         }
     335                 :            :     }
     336                 :  333555000 : }
     337                 :            : 
     338                 :            : /* Compute local reaching def info for basic block BB.  */
     339                 :            : 
     340                 :            : static void
     341                 :   32216400 : df_rd_bb_local_compute (unsigned int bb_index)
     342                 :            : {
     343                 :   32216400 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
     344                 :   32216400 :   class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
     345                 :   32216400 :   rtx_insn *insn;
     346                 :            : 
     347                 :   32216400 :   bitmap_clear (&seen_in_block);
     348                 :   32216400 :   bitmap_clear (&seen_in_insn);
     349                 :            : 
     350                 :            :   /* Artificials are only hard regs.  */
     351                 :   32216400 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
     352                 :   63681900 :     df_rd_bb_local_compute_process_def (bb_info,
     353                 :            :                                         df_get_artificial_defs (bb_index),
     354                 :            :                                         0);
     355                 :            : 
     356                 :  670063000 :   FOR_BB_INSNS_REVERSE (bb, insn)
     357                 :            :     {
     358                 :  318923000 :       unsigned int uid = INSN_UID (insn);
     359                 :            : 
     360                 :  318923000 :       if (!INSN_P (insn))
     361                 :   49050700 :         continue;
     362                 :            : 
     363                 :  269873000 :       df_rd_bb_local_compute_process_def (bb_info,
     364                 :  269873000 :                                           DF_INSN_UID_DEFS (uid), 0);
     365                 :            : 
     366                 :            :       /* This complex dance with the two bitmaps is required because
     367                 :            :          instructions can assign twice to the same pseudo.  This
     368                 :            :          generally happens with calls that will have one def for the
     369                 :            :          result and another def for the clobber.  If only one vector
     370                 :            :          is used and the clobber goes first, the result will be
     371                 :            :          lost.  */
     372                 :  269873000 :       bitmap_ior_into (&seen_in_block, &seen_in_insn);
     373                 :  269873000 :       bitmap_clear (&seen_in_insn);
     374                 :            :     }
     375                 :            : 
     376                 :            :   /* Process the artificial defs at the top of the block last since we
     377                 :            :      are going backwards through the block and these are logically at
     378                 :            :      the start.  */
     379                 :   32216400 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
     380                 :   63681900 :     df_rd_bb_local_compute_process_def (bb_info,
     381                 :            :                                         df_get_artificial_defs (bb_index),
     382                 :            :                                         DF_REF_AT_TOP);
     383                 :   32216400 : }
     384                 :            : 
     385                 :            : 
     386                 :            : /* Compute local reaching def info for each basic block within BLOCKS.  */
     387                 :            : 
     388                 :            : static void
     389                 :    2873100 : df_rd_local_compute (bitmap all_blocks)
     390                 :            : {
     391                 :    2873100 :   unsigned int bb_index;
     392                 :    2873100 :   bitmap_iterator bi;
     393                 :    2873100 :   class df_rd_problem_data *problem_data
     394                 :    2873100 :     = (class df_rd_problem_data *) df_rd->problem_data;
     395                 :    2873100 :   bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
     396                 :    2873100 :   bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
     397                 :            : 
     398                 :    2873100 :   bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
     399                 :    2873100 :   bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
     400                 :            : 
     401                 :    2873100 :   df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
     402                 :            : 
     403                 :   35089500 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     404                 :            :     {
     405                 :   32216400 :       df_rd_bb_local_compute (bb_index);
     406                 :            :     }
     407                 :            : 
     408                 :            :   /* Set up the knockout bit vectors to be applied across EH_EDGES.
     409                 :            :      Conservatively treat partially-clobbered registers as surviving
     410                 :            :      across the EH edge, i.e. assume that definitions before the edge
     411                 :            :      is taken *might* reach uses after it has been taken.  */
     412                 :    2873100 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
     413                 :  220012000 :     for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
     414                 :  217154000 :       if (eh_edge_abi.clobbers_full_reg_p (regno))
     415                 :            :         {
     416                 :  191679000 :           if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
     417                 :    4588840 :             bitmap_set_bit (sparse_invalidated, regno);
     418                 :            :           else
     419                 :  187090000 :             bitmap_set_range (dense_invalidated,
     420                 :  187090000 :                               DF_DEFS_BEGIN (regno),
     421                 :            :                               DF_DEFS_COUNT (regno));
     422                 :            :         }
     423                 :            : 
     424                 :    2873100 :   bitmap_release (&seen_in_block);
     425                 :    2873100 :   bitmap_release (&seen_in_insn);
     426                 :    2873100 : }
     427                 :            : 
     428                 :            : 
     429                 :            : /* Initialize the solution bit vectors for problem.  */
     430                 :            : 
     431                 :            : static void
     432                 :    2873100 : df_rd_init_solution (bitmap all_blocks)
     433                 :            : {
     434                 :    2873100 :   unsigned int bb_index;
     435                 :    2873100 :   bitmap_iterator bi;
     436                 :            : 
     437                 :   35089500 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     438                 :            :     {
     439                 :   32216400 :       class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
     440                 :            : 
     441                 :   32216400 :       bitmap_copy (&bb_info->out, &bb_info->gen);
     442                 :   32216400 :       bitmap_clear (&bb_info->in);
     443                 :            :     }
     444                 :    2873100 : }
     445                 :            : 
     446                 :            : /* In of target gets or of out of source.  */
     447                 :            : 
     448                 :            : static bool
     449                 :   53373100 : df_rd_confluence_n (edge e)
     450                 :            : {
     451                 :   53373100 :   bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
     452                 :   53373100 :   bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
     453                 :   53373100 :   bool changed = false;
     454                 :            : 
     455                 :   53373100 :   if (e->flags & EDGE_FAKE)
     456                 :            :     return false;
     457                 :            : 
     458                 :   53373100 :   if (e->flags & EDGE_EH)
     459                 :            :     {
     460                 :    2116090 :       class df_rd_problem_data *problem_data
     461                 :            :         = (class df_rd_problem_data *) df_rd->problem_data;
     462                 :    2116090 :       bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
     463                 :    2116090 :       bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
     464                 :    2116090 :       bitmap_iterator bi;
     465                 :    2116090 :       unsigned int regno;
     466                 :            : 
     467                 :    4232170 :       auto_bitmap tmp (&df_bitmap_obstack);
     468                 :    2116090 :       bitmap_and_compl (tmp, op2, dense_invalidated);
     469                 :            : 
     470                 :   94308900 :       EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
     471                 :            :         {
     472                 :   92192800 :           bitmap_clear_range (tmp,
     473                 :   92192800 :                               DF_DEFS_BEGIN (regno),
     474                 :   92192800 :                               DF_DEFS_COUNT (regno));
     475                 :            :         }
     476                 :    2116090 :       changed |= bitmap_ior_into (op1, tmp);
     477                 :    2116090 :       return changed;
     478                 :            :     }
     479                 :            :   else
     480                 :   51257000 :     return bitmap_ior_into (op1, op2);
     481                 :            : }
     482                 :            : 
     483                 :            : 
     484                 :            : /* Transfer function.  */
     485                 :            : 
     486                 :            : static bool
     487                 :   38822200 : df_rd_transfer_function (int bb_index)
     488                 :            : {
     489                 :   38822200 :   class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
     490                 :   38822200 :   unsigned int regno;
     491                 :   38822200 :   bitmap_iterator bi;
     492                 :   38822200 :   bitmap in = &bb_info->in;
     493                 :   38822200 :   bitmap out = &bb_info->out;
     494                 :   38822200 :   bitmap gen = &bb_info->gen;
     495                 :   38822200 :   bitmap kill = &bb_info->kill;
     496                 :   38822200 :   bitmap sparse_kill = &bb_info->sparse_kill;
     497                 :   38822200 :   bool changed = false;
     498                 :            : 
     499                 :   38822200 :   if (bitmap_empty_p (sparse_kill))
     500                 :   23561900 :     changed = bitmap_ior_and_compl (out, gen, in, kill);
     501                 :            :   else
     502                 :            :     {
     503                 :   15260400 :       class df_rd_problem_data *problem_data;
     504                 :   15260400 :       bitmap_head tmp;
     505                 :            : 
     506                 :            :       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
     507                 :            :          OUT with TMP.  Therefore, allocate TMP in the RD bitmaps obstack.  */
     508                 :   15260400 :       problem_data = (class df_rd_problem_data *) df_rd->problem_data;
     509                 :   15260400 :       bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
     510                 :            : 
     511                 :   15260400 :       bitmap_and_compl (&tmp, in, kill);
     512                 :   37264100 :       EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
     513                 :            :         {
     514                 :   22003800 :           bitmap_clear_range (&tmp,
     515                 :   22003800 :                               DF_DEFS_BEGIN (regno),
     516                 :   22003800 :                               DF_DEFS_COUNT (regno));
     517                 :            :         }
     518                 :   15260400 :       bitmap_ior_into (&tmp, gen);
     519                 :   15260400 :       changed = !bitmap_equal_p (&tmp, out);
     520                 :   15260400 :       if (changed)
     521                 :   14759300 :         bitmap_move (out, &tmp);
     522                 :            :       else
     523                 :     501046 :         bitmap_clear (&tmp);
     524                 :            :     }
     525                 :            : 
     526                 :   38822200 :   if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
     527                 :            :     {
     528                 :            :       /* Create a mask of DEFs for all registers live at the end of this
     529                 :            :          basic block, and mask out DEFs of registers that are not live.
     530                 :            :          Computing the mask looks costly, but the benefit of the pruning
     531                 :            :          outweighs the cost.  */
     532                 :   22236600 :       class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
     533                 :   22236600 :       bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
     534                 :   22236600 :       bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
     535                 :   22236600 :       unsigned int regno;
     536                 :   22236600 :       bitmap_iterator bi;
     537                 :            : 
     538                 :  271704000 :       EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
     539                 :  249467000 :         bitmap_set_range (live_defs,
     540                 :  249467000 :                           DF_DEFS_BEGIN (regno),
     541                 :  249467000 :                           DF_DEFS_COUNT (regno));
     542                 :   22236600 :       changed |= bitmap_and_into (&bb_info->out, live_defs);
     543                 :   22236600 :       BITMAP_FREE (live_defs);
     544                 :            :     }
     545                 :            : 
     546                 :   38822200 :   return changed;
     547                 :            : }
     548                 :            : 
     549                 :            : /* Free all storage associated with the problem.  */
     550                 :            : 
     551                 :            : static void
     552                 :    2626230 : df_rd_free (void)
     553                 :            : {
     554                 :    2626230 :   class df_rd_problem_data *problem_data
     555                 :    2626230 :     = (class df_rd_problem_data *) df_rd->problem_data;
     556                 :            : 
     557                 :    2626230 :   if (problem_data)
     558                 :            :     {
     559                 :    2626230 :       bitmap_obstack_release (&problem_data->rd_bitmaps);
     560                 :            : 
     561                 :    2626230 :       df_rd->block_info_size = 0;
     562                 :    2626230 :       free (df_rd->block_info);
     563                 :    2626230 :       df_rd->block_info = NULL;
     564                 :    2626230 :       free (df_rd->problem_data);
     565                 :            :     }
     566                 :    2626230 :   free (df_rd);
     567                 :    2626230 : }
     568                 :            : 
     569                 :            : 
     570                 :            : /* Debugging info.  */
     571                 :            : 
     572                 :            : static void
     573                 :        230 : df_rd_start_dump (FILE *file)
     574                 :            : {
     575                 :        230 :   class df_rd_problem_data *problem_data
     576                 :        230 :     = (class df_rd_problem_data *) df_rd->problem_data;
     577                 :        230 :   unsigned int m = DF_REG_SIZE (df);
     578                 :        230 :   unsigned int regno;
     579                 :            : 
     580                 :        230 :   if (!df_rd->block_info)
     581                 :            :     return;
     582                 :            : 
     583                 :        230 :   fprintf (file, ";; Reaching defs:\n");
     584                 :            : 
     585                 :        230 :   fprintf (file, ";;  sparse invalidated \t");
     586                 :        230 :   dump_bitmap (file, &problem_data->sparse_invalidated_by_eh);
     587                 :        230 :   fprintf (file, ";;  dense invalidated \t");
     588                 :        230 :   dump_bitmap (file, &problem_data->dense_invalidated_by_eh);
     589                 :            : 
     590                 :        230 :   fprintf (file, ";;  reg->defs[] map:\t");
     591                 :      24904 :   for (regno = 0; regno < m; regno++)
     592                 :      24674 :     if (DF_DEFS_COUNT (regno))
     593                 :      13053 :       fprintf (file, "%d[%d,%d] ", regno,
     594                 :            :                DF_DEFS_BEGIN (regno),
     595                 :      13053 :                DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
     596                 :        230 :   fprintf (file, "\n");
     597                 :            : }
     598                 :            : 
     599                 :            : 
     600                 :            : static void
     601                 :       2600 : df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
     602                 :            : {
     603                 :       2600 :   bitmap_head tmp;
     604                 :       2600 :   unsigned int regno;
     605                 :       2600 :   unsigned int m = DF_REG_SIZE (df);
     606                 :       2600 :   bool first_reg = true;
     607                 :            : 
     608                 :       2600 :   fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
     609                 :            : 
     610                 :       2600 :   bitmap_initialize (&tmp, &df_bitmap_obstack);
     611                 :     339672 :   for (regno = 0; regno < m; regno++)
     612                 :            :     {
     613                 :     337072 :       if (HARD_REGISTER_NUM_P (regno)
     614                 :     197600 :           && (df->changeable_flags & DF_NO_HARD_REGS))
     615                 :          0 :         continue;
     616                 :     337072 :       bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
     617                 :     337072 :       bitmap_and_into (&tmp, defs_set);
     618                 :     337072 :       if (! bitmap_empty_p (&tmp))
     619                 :            :         {
     620                 :       8847 :           bitmap_iterator bi;
     621                 :       8847 :           unsigned int ix;
     622                 :       8847 :           bool first_def = true;
     623                 :            : 
     624                 :       8847 :           if (! first_reg)
     625                 :       6772 :             fprintf (file, ",");
     626                 :       8847 :           first_reg = false;
     627                 :            : 
     628                 :       8847 :           fprintf (file, "%u[", regno);
     629                 :      19019 :           EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
     630                 :            :             {
     631                 :      11497 :               fprintf (file, "%s%u", first_def ? "" : ",", ix);
     632                 :      10172 :               first_def = false;
     633                 :            :             }
     634                 :       8847 :           fprintf (file, "]");
     635                 :            :         }
     636                 :     337072 :       bitmap_clear (&tmp);
     637                 :            :     }
     638                 :            : 
     639                 :       2600 :   fprintf (file, "\n");
     640                 :       2600 :   bitmap_clear (&tmp);
     641                 :       2600 : }
     642                 :            : 
     643                 :            : /* Debugging info at top of bb.  */
     644                 :            : 
     645                 :            : static void
     646                 :        650 : df_rd_top_dump (basic_block bb, FILE *file)
     647                 :            : {
     648                 :        650 :   class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
     649                 :        650 :   if (!bb_info)
     650                 :            :     return;
     651                 :            : 
     652                 :        650 :   df_rd_dump_defs_set (&bb_info->in, ";; rd  in  ", file);
     653                 :        650 :   df_rd_dump_defs_set (&bb_info->gen, ";; rd  gen ", file);
     654                 :        650 :   df_rd_dump_defs_set (&bb_info->kill, ";; rd  kill", file);
     655                 :            : }
     656                 :            : 
     657                 :            : 
     658                 :            : /* Debugging info at bottom of bb.  */
     659                 :            : 
     660                 :            : static void
     661                 :        650 : df_rd_bottom_dump (basic_block bb, FILE *file)
     662                 :            : {
     663                 :        650 :   class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
     664                 :        650 :   if (!bb_info)
     665                 :            :     return;
     666                 :            : 
     667                 :        650 :   df_rd_dump_defs_set (&bb_info->out, ";; rd  out ", file);
     668                 :            : }
     669                 :            : 
     670                 :            : /* All of the information associated with every instance of the problem.  */
     671                 :            : 
     672                 :            : static const struct df_problem problem_RD =
     673                 :            : {
     674                 :            :   DF_RD,                      /* Problem id.  */
     675                 :            :   DF_FORWARD,                 /* Direction.  */
     676                 :            :   df_rd_alloc,                /* Allocate the problem specific data.  */
     677                 :            :   NULL,                       /* Reset global information.  */
     678                 :            :   df_rd_free_bb_info,         /* Free basic block info.  */
     679                 :            :   df_rd_local_compute,        /* Local compute function.  */
     680                 :            :   df_rd_init_solution,        /* Init the solution specific data.  */
     681                 :            :   df_worklist_dataflow,       /* Worklist solver.  */
     682                 :            :   NULL,                       /* Confluence operator 0.  */
     683                 :            :   df_rd_confluence_n,         /* Confluence operator n.  */
     684                 :            :   df_rd_transfer_function,    /* Transfer function.  */
     685                 :            :   NULL,                       /* Finalize function.  */
     686                 :            :   df_rd_free,                 /* Free all of the problem information.  */
     687                 :            :   df_rd_free,                 /* Remove this problem from the stack of dataflow problems.  */
     688                 :            :   df_rd_start_dump,           /* Debugging.  */
     689                 :            :   df_rd_top_dump,             /* Debugging start block.  */
     690                 :            :   df_rd_bottom_dump,          /* Debugging end block.  */
     691                 :            :   NULL,                       /* Debugging start insn.  */
     692                 :            :   NULL,                       /* Debugging end insn.  */
     693                 :            :   NULL,                       /* Incremental solution verify start.  */
     694                 :            :   NULL,                       /* Incremental solution verify end.  */
     695                 :            :   NULL,                       /* Dependent problem.  */
     696                 :            :   sizeof (class df_rd_bb_info),/* Size of entry of block_info array.  */
     697                 :            :   TV_DF_RD,                   /* Timing variable.  */
     698                 :            :   true                        /* Reset blocks on dropping out of blocks_to_analyze.  */
     699                 :            : };
     700                 :            : 
     701                 :            : 
     702                 :            : 
     703                 :            : /* Create a new RD instance and add it to the existing instance
     704                 :            :    of DF.  */
     705                 :            : 
     706                 :            : void
     707                 :        180 : df_rd_add_problem (void)
     708                 :            : {
     709                 :        180 :   df_add_problem (&problem_RD);
     710                 :        180 : }
     711                 :            : 
     712                 :            : 
     713                 :            : 
     714                 :            : /*----------------------------------------------------------------------------
     715                 :            :    LIVE REGISTERS
     716                 :            : 
     717                 :            :    Find the locations in the function where any use of a pseudo can
     718                 :            :    reach in the backwards direction.  In and out bitvectors are built
     719                 :            :    for each basic block.  The regno is used to index into these sets.
     720                 :            :    See df.h for details.
     721                 :            :    ----------------------------------------------------------------------------*/
     722                 :            : 
     723                 :            : /* Private data used to verify the solution for this problem.  */
     724                 :            : struct df_lr_problem_data
     725                 :            : {
     726                 :            :   bitmap_head *in;
     727                 :            :   bitmap_head *out;
     728                 :            :   /* An obstack for the bitmaps we need for this problem.  */
     729                 :            :   bitmap_obstack lr_bitmaps;
     730                 :            : };
     731                 :            : 
     732                 :            : /* Free basic block info.  */
     733                 :            : 
     734                 :            : static void
     735                 :    3857150 : df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
     736                 :            :                     void *vbb_info)
     737                 :            : {
     738                 :    3857150 :   class df_lr_bb_info *bb_info = (class df_lr_bb_info *) vbb_info;
     739                 :    3857150 :   if (bb_info)
     740                 :            :     {
     741                 :    3857150 :       bitmap_clear (&bb_info->use);
     742                 :    3857150 :       bitmap_clear (&bb_info->def);
     743                 :    3857150 :       bitmap_clear (&bb_info->in);
     744                 :    3857150 :       bitmap_clear (&bb_info->out);
     745                 :            :     }
     746                 :    3857150 : }
     747                 :            : 
     748                 :            : 
     749                 :            : /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
     750                 :            :    not touched unless the block is new.  */
     751                 :            : 
     752                 :            : static void
     753                 :    9144730 : df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
     754                 :            : {
     755                 :    9144730 :   unsigned int bb_index;
     756                 :    9144730 :   bitmap_iterator bi;
     757                 :    9144730 :   struct df_lr_problem_data *problem_data;
     758                 :            : 
     759                 :    9144730 :   df_grow_bb_info (df_lr);
     760                 :    9144730 :   if (df_lr->problem_data)
     761                 :            :     problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
     762                 :            :   else
     763                 :            :     {
     764                 :     942960 :       problem_data = XNEW (struct df_lr_problem_data);
     765                 :     942960 :       df_lr->problem_data = problem_data;
     766                 :            : 
     767                 :     942960 :       problem_data->out = NULL;
     768                 :     942960 :       problem_data->in = NULL;
     769                 :     942960 :       bitmap_obstack_initialize (&problem_data->lr_bitmaps);
     770                 :            :     }
     771                 :            : 
     772                 :   62246400 :   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
     773                 :            :     {
     774                 :   53101700 :       class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
     775                 :            :       
     776                 :            :       /* When bitmaps are already initialized, just clear them.  */
     777                 :   53101700 :       if (bb_info->use.obstack)
     778                 :            :         {
     779                 :   38969000 :           bitmap_clear (&bb_info->def);
     780                 :   38969000 :           bitmap_clear (&bb_info->use);
     781                 :            :         }
     782                 :            :       else
     783                 :            :         {
     784                 :   14132700 :           bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
     785                 :   14132700 :           bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
     786                 :   14132700 :           bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
     787                 :   53101700 :           bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
     788                 :            :         }
     789                 :            :     }
     790                 :            : 
     791                 :    9144730 :   df_lr->optional_p = false;
     792                 :    9144730 : }
     793                 :            : 
     794                 :            : 
     795                 :            : /* Reset the global solution for recalculation.  */
     796                 :            : 
     797                 :            : static void
     798                 :          0 : df_lr_reset (bitmap all_blocks)
     799                 :            : {
     800                 :          0 :   unsigned int bb_index;
     801                 :          0 :   bitmap_iterator bi;
     802                 :            : 
     803                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     804                 :            :     {
     805                 :          0 :       class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
     806                 :          0 :       gcc_assert (bb_info);
     807                 :          0 :       bitmap_clear (&bb_info->in);
     808                 :          0 :       bitmap_clear (&bb_info->out);
     809                 :            :     }
     810                 :          0 : }
     811                 :            : 
     812                 :            : 
     813                 :            : /* Compute local live register info for basic block BB.  */
     814                 :            : 
     815                 :            : static void
     816                 :   50890800 : df_lr_bb_local_compute (unsigned int bb_index)
     817                 :            : {
     818                 :   50890800 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
     819                 :   50890800 :   class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
     820                 :   50890800 :   rtx_insn *insn;
     821                 :   50890800 :   df_ref def, use;
     822                 :            : 
     823                 :            :   /* Process the registers set in an exception handler.  */
     824                 :  141118000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
     825                 :   39336300 :     if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
     826                 :            :       {
     827                 :   38088700 :         unsigned int dregno = DF_REF_REGNO (def);
     828                 :   38088700 :         bitmap_set_bit (&bb_info->def, dregno);
     829                 :   38088700 :         bitmap_clear_bit (&bb_info->use, dregno);
     830                 :            :       }
     831                 :            : 
     832                 :            :   /* Process the hardware registers that are always live.  */
     833                 :  243342000 :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
     834                 :            :     /* Add use to set of uses in this BB.  */
     835                 :  141560000 :     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
     836                 :  141560000 :       bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
     837                 :            : 
     838                 : 1368550000 :   FOR_BB_INSNS_REVERSE (bb, insn)
     839                 :            :     {
     840                 :  658832000 :       if (!NONDEBUG_INSN_P (insn))
     841                 :  304416000 :         continue;
     842                 :            : 
     843                 :  354416000 :       df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
     844                 : 2264780000 :       FOR_EACH_INSN_INFO_DEF (def, insn_info)
     845                 :            :         /* If the def is to only part of the reg, it does
     846                 :            :            not kill the other defs that reach here.  */
     847                 : 1910360000 :         if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
     848                 :            :           {
     849                 : 1908770000 :             unsigned int dregno = DF_REF_REGNO (def);
     850                 : 1908770000 :             bitmap_set_bit (&bb_info->def, dregno);
     851                 : 1908770000 :             bitmap_clear_bit (&bb_info->use, dregno);
     852                 :            :           }
     853                 :            : 
     854                 :  802887000 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
     855                 :            :         /* Add use to set of uses in this BB.  */
     856                 :  448471000 :         bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
     857                 :            :     }
     858                 :            : 
     859                 :            :   /* Process the registers set in an exception handler or the hard
     860                 :            :      frame pointer if this block is the target of a non local
     861                 :            :      goto.  */
     862                 :  141118000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
     863                 :   39336300 :     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
     864                 :            :       {
     865                 :    1247660 :         unsigned int dregno = DF_REF_REGNO (def);
     866                 :    1247660 :         bitmap_set_bit (&bb_info->def, dregno);
     867                 :    1247660 :         bitmap_clear_bit (&bb_info->use, dregno);
     868                 :            :       }
     869                 :            : 
     870                 :            : #ifdef EH_USES
     871                 :            :   /* Process the uses that are live into an exception handler.  */
     872                 :            :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
     873                 :            :     /* Add use to set of uses in this BB.  */
     874                 :            :     if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
     875                 :            :       bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
     876                 :            : #endif
     877                 :            : 
     878                 :            :   /* If the df_live problem is not defined, such as at -O0 and -O1, we
     879                 :            :      still need to keep the luids up to date.  This is normally done
     880                 :            :      in the df_live problem since this problem has a forwards
     881                 :            :      scan.  */
     882                 :   50890800 :   if (!df_live)
     883                 :    7949540 :     df_recompute_luids (bb);
     884                 :   50890800 : }
     885                 :            : 
     886                 :            : 
     887                 :            : /* Compute local live register info for each basic block within BLOCKS.  */
     888                 :            : 
     889                 :            : static void
     890                 :    9144730 : df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
     891                 :            : {
     892                 :    9144730 :   unsigned int bb_index, i;
     893                 :    9144730 :   bitmap_iterator bi;
     894                 :            : 
     895                 :    9144730 :   bitmap_clear (&df->hardware_regs_used);
     896                 :            : 
     897                 :            :   /* The all-important stack pointer must always be live.  */
     898                 :    9144730 :   bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
     899                 :            : 
     900                 :            :   /* Global regs are always live, too.  */
     901                 :  704144000 :   for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
     902                 :  695000000 :     if (global_regs[i])
     903                 :        432 :       bitmap_set_bit (&df->hardware_regs_used, i);
     904                 :            : 
     905                 :            :   /* Before reload, there are a few registers that must be forced
     906                 :            :      live everywhere -- which might not already be the case for
     907                 :            :      blocks within infinite loops.  */
     908                 :    9144730 :   if (!reload_completed)
     909                 :            :     {
     910                 :    5707240 :       unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
     911                 :            :       /* Any reference to any pseudo before reload is a potential
     912                 :            :          reference of the frame pointer.  */
     913                 :    5707240 :       bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
     914                 :            : 
     915                 :            :       /* Pseudos with argument area equivalences may require
     916                 :            :          reloading via the argument pointer.  */
     917                 :    5707240 :       if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
     918                 :    5707240 :           && fixed_regs[ARG_POINTER_REGNUM])
     919                 :    5707240 :         bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
     920                 :            : 
     921                 :            :       /* Any constant, or pseudo with constant equivalences, may
     922                 :            :          require reloading from memory using the pic register.  */
     923                 :    5707240 :       if (pic_offset_table_regnum != INVALID_REGNUM
     924                 :          0 :           && fixed_regs[pic_offset_table_regnum])
     925                 :          0 :         bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
     926                 :            :     }
     927                 :            : 
     928                 :   62246400 :   EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
     929                 :            :     {
     930                 :   53101700 :       if (bb_index == EXIT_BLOCK)
     931                 :            :         {
     932                 :            :           /* The exit block is special for this problem and its bits are
     933                 :            :              computed from thin air.  */
     934                 :    2210950 :           class df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
     935                 :    2210950 :           bitmap_copy (&bb_info->use, df->exit_block_uses);
     936                 :            :         }
     937                 :            :       else
     938                 :   50890800 :         df_lr_bb_local_compute (bb_index);
     939                 :            :     }
     940                 :            : 
     941                 :    9144730 :   bitmap_clear (df_lr->out_of_date_transfer_functions);
     942                 :    9144730 : }
     943                 :            : 
     944                 :            : 
     945                 :            : /* Initialize the solution vectors.  */
     946                 :            : 
     947                 :            : static void
     948                 :    9144730 : df_lr_init (bitmap all_blocks)
     949                 :            : {
     950                 :    9144730 :   unsigned int bb_index;
     951                 :    9144730 :   bitmap_iterator bi;
     952                 :            : 
     953                 :  196950000 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     954                 :            :     {
     955                 :  187806000 :       class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
     956                 :  187806000 :       bitmap_copy (&bb_info->in, &bb_info->use);
     957                 :  187806000 :       bitmap_clear (&bb_info->out);
     958                 :            :     }
     959                 :    9144730 : }
     960                 :            : 
     961                 :            : 
     962                 :            : /* Confluence function that processes infinite loops.  This might be a
     963                 :            :    noreturn function that throws.  And even if it isn't, getting the
     964                 :            :    unwind info right helps debugging.  */
     965                 :            : static void
     966                 :   16569700 : df_lr_confluence_0 (basic_block bb)
     967                 :            : {
     968                 :   16569700 :   bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
     969                 :   16569700 :   if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
     970                 :    7808770 :     bitmap_copy (op1, &df->hardware_regs_used);
     971                 :   16569700 : }
     972                 :            : 
     973                 :            : 
     974                 :            : /* Confluence function that ignores fake edges.  */
     975                 :            : 
     976                 :            : static bool
     977                 :  301560000 : df_lr_confluence_n (edge e)
     978                 :            : {
     979                 :  301560000 :   bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
     980                 :  301560000 :   bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
     981                 :  301560000 :   bool changed = false;
     982                 :            : 
     983                 :            :   /* Call-clobbered registers die across exception and call edges.
     984                 :            :      Conservatively treat partially-clobbered registers as surviving
     985                 :            :      across the edges; they might or might not, depending on what
     986                 :            :      mode they have.  */
     987                 :            :   /* ??? Abnormal call edges ignored for the moment, as this gets
     988                 :            :      confused by sibling call edges, which crashes reg-stack.  */
     989                 :  301560000 :   if (e->flags & EDGE_EH)
     990                 :            :     {
     991                 :   13581900 :       bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
     992                 :   13581900 :       changed = bitmap_ior_and_compl_into (op1, op2, eh_kills);
     993                 :            :     }
     994                 :            :   else
     995                 :  287978000 :     changed = bitmap_ior_into (op1, op2);
     996                 :            : 
     997                 :  301560000 :   changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
     998                 :  301560000 :   return changed;
     999                 :            : }
    1000                 :            : 
    1001                 :            : 
    1002                 :            : /* Transfer function.  */
    1003                 :            : 
    1004                 :            : static bool
    1005                 :  213662000 : df_lr_transfer_function (int bb_index)
    1006                 :            : {
    1007                 :  213662000 :   class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
    1008                 :  213662000 :   bitmap in = &bb_info->in;
    1009                 :  213662000 :   bitmap out = &bb_info->out;
    1010                 :  213662000 :   bitmap use = &bb_info->use;
    1011                 :  213662000 :   bitmap def = &bb_info->def;
    1012                 :            : 
    1013                 :  213662000 :   return bitmap_ior_and_compl (in, use, out, def);
    1014                 :            : }
    1015                 :            : 
    1016                 :            : 
    1017                 :            : /* Run the fast dce as a side effect of building LR.  */
    1018                 :            : 
    1019                 :            : static void
    1020                 :    9144730 : df_lr_finalize (bitmap all_blocks)
    1021                 :            : {
    1022                 :    9144730 :   df_lr->solutions_dirty = false;
    1023                 :    9144730 :   if (df->changeable_flags & DF_LR_RUN_DCE)
    1024                 :            :     {
    1025                 :    3773960 :       run_fast_df_dce ();
    1026                 :            : 
    1027                 :            :       /* If dce deletes some instructions, we need to recompute the lr
    1028                 :            :          solution before proceeding further.  The problem is that fast
    1029                 :            :          dce is a pessimestic dataflow algorithm.  In the case where
    1030                 :            :          it deletes a statement S inside of a loop, the uses inside of
    1031                 :            :          S may not be deleted from the dataflow solution because they
    1032                 :            :          were carried around the loop.  While it is conservatively
    1033                 :            :          correct to leave these extra bits, the standards of df
    1034                 :            :          require that we maintain the best possible (least fixed
    1035                 :            :          point) solution.  The only way to do that is to redo the
    1036                 :            :          iteration from the beginning.  See PR35805 for an
    1037                 :            :          example.  */
    1038                 :    3773960 :       if (df_lr->solutions_dirty)
    1039                 :            :         {
    1040                 :     400036 :           df_clear_flags (DF_LR_RUN_DCE);
    1041                 :     400036 :           df_lr_alloc (all_blocks);
    1042                 :     400036 :           df_lr_local_compute (all_blocks);
    1043                 :     400036 :           df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
    1044                 :     400036 :           df_lr_finalize (all_blocks);
    1045                 :     400036 :           df_set_flags (DF_LR_RUN_DCE);
    1046                 :            :         }
    1047                 :            :     }
    1048                 :    9144730 : }
    1049                 :            : 
    1050                 :            : 
    1051                 :            : /* Free all storage associated with the problem.  */
    1052                 :            : 
    1053                 :            : static void
    1054                 :     942962 : df_lr_free (void)
    1055                 :            : {
    1056                 :     942962 :   struct df_lr_problem_data *problem_data
    1057                 :     942962 :     = (struct df_lr_problem_data *) df_lr->problem_data;
    1058                 :     942962 :   if (df_lr->block_info)
    1059                 :            :     {
    1060                 :            : 
    1061                 :     942960 :       df_lr->block_info_size = 0;
    1062                 :     942960 :       free (df_lr->block_info);
    1063                 :     942960 :       df_lr->block_info = NULL;
    1064                 :     942960 :       bitmap_obstack_release (&problem_data->lr_bitmaps);
    1065                 :     942960 :       free (df_lr->problem_data);
    1066                 :     942960 :       df_lr->problem_data = NULL;
    1067                 :            :     }
    1068                 :            : 
    1069                 :     942962 :   BITMAP_FREE (df_lr->out_of_date_transfer_functions);
    1070                 :     942962 :   free (df_lr);
    1071                 :     942962 : }
    1072                 :            : 
    1073                 :            : 
    1074                 :            : /* Debugging info at top of bb.  */
    1075                 :            : 
    1076                 :            : static void
    1077                 :       3919 : df_lr_top_dump (basic_block bb, FILE *file)
    1078                 :            : {
    1079                 :       3919 :   class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
    1080                 :       3919 :   struct df_lr_problem_data *problem_data;
    1081                 :       3919 :   if (!bb_info)
    1082                 :            :     return;
    1083                 :            : 
    1084                 :       3919 :   fprintf (file, ";; lr  in  \t");
    1085                 :       3919 :   df_print_regset (file, &bb_info->in);
    1086                 :       3919 :   if (df_lr->problem_data)
    1087                 :            :     {
    1088                 :       3919 :       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
    1089                 :       3919 :       if (problem_data->in)
    1090                 :            :         {
    1091                 :          0 :           fprintf (file, ";;  old in  \t");
    1092                 :          0 :           df_print_regset (file, &problem_data->in[bb->index]);
    1093                 :            :         }
    1094                 :            :     }
    1095                 :       3919 :   fprintf (file, ";; lr  use \t");
    1096                 :       3919 :   df_print_regset (file, &bb_info->use);
    1097                 :       3919 :   fprintf (file, ";; lr  def \t");
    1098                 :       3919 :   df_print_regset (file, &bb_info->def);
    1099                 :            : }
    1100                 :            : 
    1101                 :            : 
    1102                 :            : /* Debugging info at bottom of bb.  */
    1103                 :            : 
    1104                 :            : static void
    1105                 :       3919 : df_lr_bottom_dump (basic_block bb, FILE *file)
    1106                 :            : {
    1107                 :       3919 :   class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
    1108                 :       3919 :   struct df_lr_problem_data *problem_data;
    1109                 :       3919 :   if (!bb_info)
    1110                 :            :     return;
    1111                 :            : 
    1112                 :       3919 :   fprintf (file, ";; lr  out \t");
    1113                 :       3919 :   df_print_regset (file, &bb_info->out);
    1114                 :       3919 :   if (df_lr->problem_data)
    1115                 :            :     {
    1116                 :       3919 :       problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
    1117                 :       3919 :       if (problem_data->out)
    1118                 :            :         {
    1119                 :          0 :           fprintf (file, ";;  old out  \t");
    1120                 :          0 :           df_print_regset (file, &problem_data->out[bb->index]);
    1121                 :            :         }
    1122                 :            :     }
    1123                 :            : }
    1124                 :            : 
    1125                 :            : 
    1126                 :            : /* Build the datastructure to verify that the solution to the dataflow
    1127                 :            :    equations is not dirty.  */
    1128                 :            : 
    1129                 :            : static void
    1130                 :          0 : df_lr_verify_solution_start (void)
    1131                 :            : {
    1132                 :          0 :   basic_block bb;
    1133                 :          0 :   struct df_lr_problem_data *problem_data;
    1134                 :          0 :   if (df_lr->solutions_dirty)
    1135                 :            :     return;
    1136                 :            : 
    1137                 :            :   /* Set it true so that the solution is recomputed.  */
    1138                 :          0 :   df_lr->solutions_dirty = true;
    1139                 :            : 
    1140                 :          0 :   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
    1141                 :          0 :   problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    1142                 :          0 :   problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    1143                 :            : 
    1144                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1145                 :            :     {
    1146                 :          0 :       bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
    1147                 :          0 :       bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
    1148                 :          0 :       bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
    1149                 :          0 :       bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
    1150                 :            :     }
    1151                 :            : }
    1152                 :            : 
    1153                 :            : 
    1154                 :            : /* Compare the saved datastructure and the new solution to the dataflow
    1155                 :            :    equations.  */
    1156                 :            : 
    1157                 :            : static void
    1158                 :          0 : df_lr_verify_solution_end (void)
    1159                 :            : {
    1160                 :          0 :   struct df_lr_problem_data *problem_data;
    1161                 :          0 :   basic_block bb;
    1162                 :            : 
    1163                 :          0 :   problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
    1164                 :            : 
    1165                 :          0 :   if (!problem_data->out)
    1166                 :            :     return;
    1167                 :            : 
    1168                 :          0 :   if (df_lr->solutions_dirty)
    1169                 :            :     /* Do not check if the solution is still dirty.  See the comment
    1170                 :            :        in df_lr_finalize for details.  */
    1171                 :          0 :     df_lr->solutions_dirty = false;
    1172                 :            :   else
    1173                 :          0 :     FOR_ALL_BB_FN (bb, cfun)
    1174                 :            :       {
    1175                 :          0 :         if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
    1176                 :          0 :             || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
    1177                 :            :           {
    1178                 :            :             /*df_dump (stderr);*/
    1179                 :          0 :             gcc_unreachable ();
    1180                 :            :           }
    1181                 :            :       }
    1182                 :            : 
    1183                 :            :   /* Cannot delete them immediately because you may want to dump them
    1184                 :            :      if the comparison fails.  */
    1185                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1186                 :            :     {
    1187                 :          0 :       bitmap_clear (&problem_data->in[bb->index]);
    1188                 :          0 :       bitmap_clear (&problem_data->out[bb->index]);
    1189                 :            :     }
    1190                 :            : 
    1191                 :          0 :   free (problem_data->in);
    1192                 :          0 :   free (problem_data->out);
    1193                 :          0 :   problem_data->in = NULL;
    1194                 :          0 :   problem_data->out = NULL;
    1195                 :            : }
    1196                 :            : 
    1197                 :            : 
    1198                 :            : /* All of the information associated with every instance of the problem.  */
    1199                 :            : 
    1200                 :            : static const struct df_problem problem_LR =
    1201                 :            : {
    1202                 :            :   DF_LR,                      /* Problem id.  */
    1203                 :            :   DF_BACKWARD,                /* Direction.  */
    1204                 :            :   df_lr_alloc,                /* Allocate the problem specific data.  */
    1205                 :            :   df_lr_reset,                /* Reset global information.  */
    1206                 :            :   df_lr_free_bb_info,         /* Free basic block info.  */
    1207                 :            :   df_lr_local_compute,        /* Local compute function.  */
    1208                 :            :   df_lr_init,                 /* Init the solution specific data.  */
    1209                 :            :   df_worklist_dataflow,       /* Worklist solver.  */
    1210                 :            :   df_lr_confluence_0,         /* Confluence operator 0.  */
    1211                 :            :   df_lr_confluence_n,         /* Confluence operator n.  */
    1212                 :            :   df_lr_transfer_function,    /* Transfer function.  */
    1213                 :            :   df_lr_finalize,             /* Finalize function.  */
    1214                 :            :   df_lr_free,                 /* Free all of the problem information.  */
    1215                 :            :   NULL,                       /* Remove this problem from the stack of dataflow problems.  */
    1216                 :            :   NULL,                       /* Debugging.  */
    1217                 :            :   df_lr_top_dump,             /* Debugging start block.  */
    1218                 :            :   df_lr_bottom_dump,          /* Debugging end block.  */
    1219                 :            :   NULL,                       /* Debugging start insn.  */
    1220                 :            :   NULL,                       /* Debugging end insn.  */
    1221                 :            :   df_lr_verify_solution_start,/* Incremental solution verify start.  */
    1222                 :            :   df_lr_verify_solution_end,  /* Incremental solution verify end.  */
    1223                 :            :   NULL,                       /* Dependent problem.  */
    1224                 :            :   sizeof (class df_lr_bb_info),/* Size of entry of block_info array.  */
    1225                 :            :   TV_DF_LR,                   /* Timing variable.  */
    1226                 :            :   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
    1227                 :            : };
    1228                 :            : 
    1229                 :            : 
    1230                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    1231                 :            :    of DF.  The returned structure is what is used to get at the
    1232                 :            :    solution.  */
    1233                 :            : 
    1234                 :            : void
    1235                 :     942962 : df_lr_add_problem (void)
    1236                 :            : {
    1237                 :     942962 :   df_add_problem (&problem_LR);
    1238                 :            :   /* These will be initialized when df_scan_blocks processes each
    1239                 :            :      block.  */
    1240                 :     942962 :   df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
    1241                 :     942962 : }
    1242                 :            : 
    1243                 :            : 
    1244                 :            : /* Verify that all of the lr related info is consistent and
    1245                 :            :    correct.  */
    1246                 :            : 
    1247                 :            : void
    1248                 :          0 : df_lr_verify_transfer_functions (void)
    1249                 :            : {
    1250                 :          0 :   basic_block bb;
    1251                 :          0 :   bitmap_head saved_def;
    1252                 :          0 :   bitmap_head saved_use;
    1253                 :          0 :   bitmap_head all_blocks;
    1254                 :            : 
    1255                 :          0 :   if (!df)
    1256                 :          0 :     return;
    1257                 :            : 
    1258                 :          0 :   bitmap_initialize (&saved_def, &bitmap_default_obstack); 
    1259                 :          0 :   bitmap_initialize (&saved_use, &bitmap_default_obstack);
    1260                 :          0 :   bitmap_initialize (&all_blocks, &bitmap_default_obstack);
    1261                 :            : 
    1262                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1263                 :            :     {
    1264                 :          0 :       class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
    1265                 :          0 :       bitmap_set_bit (&all_blocks, bb->index);
    1266                 :            : 
    1267                 :          0 :       if (bb_info)
    1268                 :            :         {
    1269                 :            :           /* Make a copy of the transfer functions and then compute
    1270                 :            :              new ones to see if the transfer functions have
    1271                 :            :              changed.  */
    1272                 :          0 :           if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
    1273                 :            :                              bb->index))
    1274                 :            :             {
    1275                 :          0 :               bitmap_copy (&saved_def, &bb_info->def);
    1276                 :          0 :               bitmap_copy (&saved_use, &bb_info->use);
    1277                 :          0 :               bitmap_clear (&bb_info->def);
    1278                 :          0 :               bitmap_clear (&bb_info->use);
    1279                 :            : 
    1280                 :          0 :               df_lr_bb_local_compute (bb->index);
    1281                 :          0 :               gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
    1282                 :          0 :               gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
    1283                 :            :             }
    1284                 :            :         }
    1285                 :            :       else
    1286                 :            :         {
    1287                 :            :           /* If we do not have basic block info, the block must be in
    1288                 :            :              the list of dirty blocks or else some one has added a
    1289                 :            :              block behind our backs. */
    1290                 :          0 :           gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
    1291                 :            :                                     bb->index));
    1292                 :            :         }
    1293                 :            :       /* Make sure no one created a block without following
    1294                 :            :          procedures.  */
    1295                 :          0 :       gcc_assert (df_scan_get_bb_info (bb->index));
    1296                 :            :     }
    1297                 :            : 
    1298                 :            :   /* Make sure there are no dirty bits in blocks that have been deleted.  */
    1299                 :          0 :   gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
    1300                 :            :                                          &all_blocks));
    1301                 :            : 
    1302                 :          0 :   bitmap_clear (&saved_def);
    1303                 :          0 :   bitmap_clear (&saved_use);
    1304                 :          0 :   bitmap_clear (&all_blocks);
    1305                 :            : }
    1306                 :            : 
    1307                 :            : 
    1308                 :            : 
    1309                 :            : /*----------------------------------------------------------------------------
    1310                 :            :    LIVE AND MAY-INITIALIZED REGISTERS.
    1311                 :            : 
    1312                 :            :    This problem first computes the IN and OUT bitvectors for the
    1313                 :            :    may-initialized registers problems, which is a forward problem.
    1314                 :            :    It gives the set of registers for which we MAY have an available
    1315                 :            :    definition, i.e. for which there is an available definition on
    1316                 :            :    at least one path from the entry block to the entry/exit of a
    1317                 :            :    basic block.  Sets generate a definition, while clobbers kill
    1318                 :            :    a definition.
    1319                 :            : 
    1320                 :            :    In and out bitvectors are built for each basic block and are indexed by
    1321                 :            :    regnum (see df.h for details).  In and out bitvectors in struct
    1322                 :            :    df_live_bb_info actually refers to the may-initialized problem;
    1323                 :            : 
    1324                 :            :    Then, the in and out sets for the LIVE problem itself are computed.
    1325                 :            :    These are the logical AND of the IN and OUT sets from the LR problem
    1326                 :            :    and the may-initialized problem.
    1327                 :            : ----------------------------------------------------------------------------*/
    1328                 :            : 
    1329                 :            : /* Private data used to verify the solution for this problem.  */
    1330                 :            : struct df_live_problem_data
    1331                 :            : {
    1332                 :            :   bitmap_head *in;
    1333                 :            :   bitmap_head *out;
    1334                 :            :   /* An obstack for the bitmaps we need for this problem.  */
    1335                 :            :   bitmap_obstack live_bitmaps;
    1336                 :            : };
    1337                 :            : 
    1338                 :            : /* Scratch var used by transfer functions.  This is used to implement
    1339                 :            :    an optimization to reduce the amount of space used to compute the
    1340                 :            :    combined lr and live analysis.  */
    1341                 :            : static bitmap_head df_live_scratch;
    1342                 :            : 
    1343                 :            : 
    1344                 :            : /* Free basic block info.  */
    1345                 :            : 
    1346                 :            : static void
    1347                 :    3609880 : df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
    1348                 :            :                     void *vbb_info)
    1349                 :            : {
    1350                 :    3609880 :   class df_live_bb_info *bb_info = (class df_live_bb_info *) vbb_info;
    1351                 :    3609880 :   if (bb_info)
    1352                 :            :     {
    1353                 :    3609880 :       bitmap_clear (&bb_info->gen);
    1354                 :    3609880 :       bitmap_clear (&bb_info->kill);
    1355                 :    3609880 :       bitmap_clear (&bb_info->in);
    1356                 :    3609880 :       bitmap_clear (&bb_info->out);
    1357                 :            :     }
    1358                 :    3609880 : }
    1359                 :            : 
    1360                 :            : 
    1361                 :            : /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
    1362                 :            :    not touched unless the block is new.  */
    1363                 :            : 
    1364                 :            : static void
    1365                 :    7718460 : df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
    1366                 :            : {
    1367                 :    7718460 :   unsigned int bb_index;
    1368                 :    7718460 :   bitmap_iterator bi;
    1369                 :    7718460 :   struct df_live_problem_data *problem_data;
    1370                 :            : 
    1371                 :    7718460 :   if (df_live->problem_data)
    1372                 :            :     problem_data = (struct df_live_problem_data *) df_live->problem_data;
    1373                 :            :   else
    1374                 :            :     {
    1375                 :    1462950 :       problem_data = XNEW (struct df_live_problem_data);
    1376                 :    1462950 :       df_live->problem_data = problem_data;
    1377                 :            : 
    1378                 :    1462950 :       problem_data->out = NULL;
    1379                 :    1462950 :       problem_data->in = NULL;
    1380                 :    1462950 :       bitmap_obstack_initialize (&problem_data->live_bitmaps);
    1381                 :    1462950 :       bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
    1382                 :            :     }
    1383                 :            : 
    1384                 :    7718460 :   df_grow_bb_info (df_live);
    1385                 :            : 
    1386                 :   56440600 :   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
    1387                 :            :     {
    1388                 :   48722100 :       class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
    1389                 :            :       
    1390                 :            :       /* When bitmaps are already initialized, just clear them.  */
    1391                 :   48722100 :       if (bb_info->kill.obstack)
    1392                 :            :         {
    1393                 :   28251900 :           bitmap_clear (&bb_info->kill);
    1394                 :   28251900 :           bitmap_clear (&bb_info->gen);
    1395                 :            :         }
    1396                 :            :       else
    1397                 :            :         {
    1398                 :   20470200 :           bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
    1399                 :   20470200 :           bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
    1400                 :   20470200 :           bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
    1401                 :   48722100 :           bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
    1402                 :            :         }
    1403                 :            :     }
    1404                 :    7718460 :   df_live->optional_p = (optimize <= 1);
    1405                 :    7718460 : }
    1406                 :            : 
    1407                 :            : 
    1408                 :            : /* Reset the global solution for recalculation.  */
    1409                 :            : 
    1410                 :            : static void
    1411                 :      15976 : df_live_reset (bitmap all_blocks)
    1412                 :            : {
    1413                 :      15976 :   unsigned int bb_index;
    1414                 :      15976 :   bitmap_iterator bi;
    1415                 :            : 
    1416                 :      96298 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    1417                 :            :     {
    1418                 :      80322 :       class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
    1419                 :      80322 :       gcc_assert (bb_info);
    1420                 :      80322 :       bitmap_clear (&bb_info->in);
    1421                 :      80322 :       bitmap_clear (&bb_info->out);
    1422                 :            :     }
    1423                 :      15976 : }
    1424                 :            : 
    1425                 :            : 
    1426                 :            : /* Compute local uninitialized register info for basic block BB.  */
    1427                 :            : 
    1428                 :            : static void
    1429                 :   48722100 : df_live_bb_local_compute (unsigned int bb_index)
    1430                 :            : {
    1431                 :   48722100 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    1432                 :   48722100 :   class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
    1433                 :   48722100 :   rtx_insn *insn;
    1434                 :   48722100 :   df_ref def;
    1435                 :   48722100 :   int luid = 0;
    1436                 :            : 
    1437                 : 1256890000 :   FOR_BB_INSNS (bb, insn)
    1438                 :            :     {
    1439                 :  604086000 :       unsigned int uid = INSN_UID (insn);
    1440                 :  604086000 :       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
    1441                 :            : 
    1442                 :            :       /* Inserting labels does not always trigger the incremental
    1443                 :            :          rescanning.  */
    1444                 :  604086000 :       if (!insn_info)
    1445                 :            :         {
    1446                 :    8077050 :           gcc_assert (!INSN_P (insn));
    1447                 :    8077050 :           insn_info = df_insn_create_insn_record (insn);
    1448                 :            :         }
    1449                 :            : 
    1450                 :  604086000 :       DF_INSN_INFO_LUID (insn_info) = luid;
    1451                 :  604086000 :       if (!INSN_P (insn))
    1452                 :   88702000 :         continue;
    1453                 :            : 
    1454                 :  515384000 :       luid++;
    1455                 : 2242530000 :       FOR_EACH_INSN_INFO_DEF (def, insn_info)
    1456                 :            :         {
    1457                 : 1727150000 :           unsigned int regno = DF_REF_REGNO (def);
    1458                 :            : 
    1459                 : 1727150000 :           if (DF_REF_FLAGS_IS_SET (def,
    1460                 :            :                                    DF_REF_PARTIAL | DF_REF_CONDITIONAL))
    1461                 :            :             /* All partial or conditional def
    1462                 :            :                seen are included in the gen set. */
    1463                 :    1353820 :             bitmap_set_bit (&bb_info->gen, regno);
    1464                 : 1725800000 :           else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
    1465                 :            :             /* Only must clobbers for the entire reg destroy the
    1466                 :            :                value.  */
    1467                 :   44590900 :             bitmap_set_bit (&bb_info->kill, regno);
    1468                 : 1681210000 :           else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
    1469                 :  227858000 :             bitmap_set_bit (&bb_info->gen, regno);
    1470                 :            :         }
    1471                 :            :     }
    1472                 :            : 
    1473                 :  131381000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    1474                 :   33936500 :     bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
    1475                 :   48722100 : }
    1476                 :            : 
    1477                 :            : 
    1478                 :            : /* Compute local uninitialized register info.  */
    1479                 :            : 
    1480                 :            : static void
    1481                 :    7718460 : df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
    1482                 :            : {
    1483                 :    7718460 :   unsigned int bb_index;
    1484                 :    7718460 :   bitmap_iterator bi;
    1485                 :            : 
    1486                 :    7718460 :   df_grow_insn_info ();
    1487                 :            : 
    1488                 :   56440600 :   EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
    1489                 :            :                             0, bb_index, bi)
    1490                 :            :     {
    1491                 :   48722100 :       df_live_bb_local_compute (bb_index);
    1492                 :            :     }
    1493                 :            : 
    1494                 :    7718460 :   bitmap_clear (df_live->out_of_date_transfer_functions);
    1495                 :    7718460 : }
    1496                 :            : 
    1497                 :            : 
    1498                 :            : /* Initialize the solution vectors.  */
    1499                 :            : 
    1500                 :            : static void
    1501                 :    7718460 : df_live_init (bitmap all_blocks)
    1502                 :            : {
    1503                 :    7718460 :   unsigned int bb_index;
    1504                 :    7718460 :   bitmap_iterator bi;
    1505                 :            : 
    1506                 :  159309000 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    1507                 :            :     {
    1508                 :  151590000 :       class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
    1509                 :  151590000 :       class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
    1510                 :            : 
    1511                 :            :       /* No register may reach a location where it is not used.  Thus
    1512                 :            :          we trim the rr result to the places where it is used.  */
    1513                 :  151590000 :       bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
    1514                 :  151590000 :       bitmap_clear (&bb_info->in);
    1515                 :            :     }
    1516                 :    7718460 : }
    1517                 :            : 
    1518                 :            : /* Forward confluence function that ignores fake edges.  */
    1519                 :            : 
    1520                 :            : static bool
    1521                 :  240210000 : df_live_confluence_n (edge e)
    1522                 :            : {
    1523                 :  240210000 :   bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
    1524                 :  240210000 :   bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
    1525                 :            : 
    1526                 :  240210000 :   if (e->flags & EDGE_FAKE)
    1527                 :            :     return false;
    1528                 :            : 
    1529                 :  240027000 :   return bitmap_ior_into (op1, op2);
    1530                 :            : }
    1531                 :            : 
    1532                 :            : 
    1533                 :            : /* Transfer function for the forwards may-initialized problem.  */
    1534                 :            : 
    1535                 :            : static bool
    1536                 :  170859000 : df_live_transfer_function (int bb_index)
    1537                 :            : {
    1538                 :  170859000 :   class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
    1539                 :  170859000 :   class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
    1540                 :  170859000 :   bitmap in = &bb_info->in;
    1541                 :  170859000 :   bitmap out = &bb_info->out;
    1542                 :  170859000 :   bitmap gen = &bb_info->gen;
    1543                 :  170859000 :   bitmap kill = &bb_info->kill;
    1544                 :            : 
    1545                 :            :   /* We need to use a scratch set here so that the value returned from this
    1546                 :            :      function invocation properly reflects whether the sets changed in a
    1547                 :            :      significant way; i.e. not just because the lr set was anded in.  */
    1548                 :  170859000 :   bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
    1549                 :            :   /* No register may reach a location where it is not used.  Thus
    1550                 :            :      we trim the rr result to the places where it is used.  */
    1551                 :  170859000 :   bitmap_and_into (in, &bb_lr_info->in);
    1552                 :            : 
    1553                 :  170859000 :   return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
    1554                 :            : }
    1555                 :            : 
    1556                 :            : 
    1557                 :            : /* And the LR info with the may-initialized registers to produce the LIVE info.  */
    1558                 :            : 
    1559                 :            : static void
    1560                 :    7718460 : df_live_finalize (bitmap all_blocks)
    1561                 :            : {
    1562                 :            : 
    1563                 :    7718460 :   if (df_live->solutions_dirty)
    1564                 :            :     {
    1565                 :    7718460 :       bitmap_iterator bi;
    1566                 :    7718460 :       unsigned int bb_index;
    1567                 :            : 
    1568                 :  159309000 :       EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    1569                 :            :         {
    1570                 :  151590000 :           class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
    1571                 :  151590000 :           class df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
    1572                 :            : 
    1573                 :            :           /* No register may reach a location where it is not used.  Thus
    1574                 :            :              we trim the rr result to the places where it is used.  */
    1575                 :  151590000 :           bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
    1576                 :  151590000 :           bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
    1577                 :            :         }
    1578                 :            : 
    1579                 :    7718460 :       df_live->solutions_dirty = false;
    1580                 :            :     }
    1581                 :    7718460 : }
    1582                 :            : 
    1583                 :            : 
    1584                 :            : /* Free all storage associated with the problem.  */
    1585                 :            : 
    1586                 :            : static void
    1587                 :    1464650 : df_live_free (void)
    1588                 :            : {
    1589                 :    1464650 :   struct df_live_problem_data *problem_data
    1590                 :    1464650 :     = (struct df_live_problem_data *) df_live->problem_data;
    1591                 :    1464650 :   if (df_live->block_info)
    1592                 :            :     {
    1593                 :    1462950 :       df_live->block_info_size = 0;
    1594                 :    1462950 :       free (df_live->block_info);
    1595                 :    1462950 :       df_live->block_info = NULL;
    1596                 :    1462950 :       bitmap_release (&df_live_scratch);
    1597                 :    1462950 :       bitmap_obstack_release (&problem_data->live_bitmaps);
    1598                 :    1462950 :       free (problem_data);
    1599                 :    1462950 :       df_live->problem_data = NULL;
    1600                 :            :     }
    1601                 :    1464650 :   BITMAP_FREE (df_live->out_of_date_transfer_functions);
    1602                 :    1464650 :   free (df_live);
    1603                 :    1464650 : }
    1604                 :            : 
    1605                 :            : 
    1606                 :            : /* Debugging info at top of bb.  */
    1607                 :            : 
    1608                 :            : static void
    1609                 :       2800 : df_live_top_dump (basic_block bb, FILE *file)
    1610                 :            : {
    1611                 :       2800 :   class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
    1612                 :       2800 :   struct df_live_problem_data *problem_data;
    1613                 :            : 
    1614                 :       2800 :   if (!bb_info)
    1615                 :            :     return;
    1616                 :            : 
    1617                 :       2800 :   fprintf (file, ";; live  in  \t");
    1618                 :       2800 :   df_print_regset (file, &bb_info->in);
    1619                 :       2800 :   if (df_live->problem_data)
    1620                 :            :     {
    1621                 :       2800 :       problem_data = (struct df_live_problem_data *)df_live->problem_data;
    1622                 :       2800 :       if (problem_data->in)
    1623                 :            :         {
    1624                 :          0 :           fprintf (file, ";;  old in  \t");
    1625                 :          0 :           df_print_regset (file, &problem_data->in[bb->index]);
    1626                 :            :         }
    1627                 :            :     }
    1628                 :       2800 :   fprintf (file, ";; live  gen \t");
    1629                 :       2800 :   df_print_regset (file, &bb_info->gen);
    1630                 :       2800 :   fprintf (file, ";; live  kill\t");
    1631                 :       2800 :   df_print_regset (file, &bb_info->kill);
    1632                 :            : }
    1633                 :            : 
    1634                 :            : 
    1635                 :            : /* Debugging info at bottom of bb.  */
    1636                 :            : 
    1637                 :            : static void
    1638                 :       2800 : df_live_bottom_dump (basic_block bb, FILE *file)
    1639                 :            : {
    1640                 :       2800 :   class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
    1641                 :       2800 :   struct df_live_problem_data *problem_data;
    1642                 :            : 
    1643                 :       2800 :   if (!bb_info)
    1644                 :            :     return;
    1645                 :            : 
    1646                 :       2800 :   fprintf (file, ";; live  out \t");
    1647                 :       2800 :   df_print_regset (file, &bb_info->out);
    1648                 :       2800 :   if (df_live->problem_data)
    1649                 :            :     {
    1650                 :       2800 :       problem_data = (struct df_live_problem_data *)df_live->problem_data;
    1651                 :       2800 :       if (problem_data->out)
    1652                 :            :         {
    1653                 :          0 :           fprintf (file, ";;  old out  \t");
    1654                 :          0 :           df_print_regset (file, &problem_data->out[bb->index]);
    1655                 :            :         }
    1656                 :            :     }
    1657                 :            : }
    1658                 :            : 
    1659                 :            : 
    1660                 :            : /* Build the datastructure to verify that the solution to the dataflow
    1661                 :            :    equations is not dirty.  */
    1662                 :            : 
    1663                 :            : static void
    1664                 :          0 : df_live_verify_solution_start (void)
    1665                 :            : {
    1666                 :          0 :   basic_block bb;
    1667                 :          0 :   struct df_live_problem_data *problem_data;
    1668                 :          0 :   if (df_live->solutions_dirty)
    1669                 :            :     return;
    1670                 :            : 
    1671                 :            :   /* Set it true so that the solution is recomputed.  */
    1672                 :          0 :   df_live->solutions_dirty = true;
    1673                 :            : 
    1674                 :          0 :   problem_data = (struct df_live_problem_data *)df_live->problem_data;
    1675                 :          0 :   problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    1676                 :          0 :   problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    1677                 :            : 
    1678                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1679                 :            :     {
    1680                 :          0 :       bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
    1681                 :          0 :       bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
    1682                 :          0 :       bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
    1683                 :          0 :       bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
    1684                 :            :     }
    1685                 :            : }
    1686                 :            : 
    1687                 :            : 
    1688                 :            : /* Compare the saved datastructure and the new solution to the dataflow
    1689                 :            :    equations.  */
    1690                 :            : 
    1691                 :            : static void
    1692                 :          0 : df_live_verify_solution_end (void)
    1693                 :            : {
    1694                 :          0 :   struct df_live_problem_data *problem_data;
    1695                 :          0 :   basic_block bb;
    1696                 :            : 
    1697                 :          0 :   problem_data = (struct df_live_problem_data *)df_live->problem_data;
    1698                 :          0 :   if (!problem_data->out)
    1699                 :            :     return;
    1700                 :            : 
    1701                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1702                 :            :     {
    1703                 :          0 :       if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
    1704                 :          0 :           || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
    1705                 :            :         {
    1706                 :            :           /*df_dump (stderr);*/
    1707                 :          0 :           gcc_unreachable ();
    1708                 :            :         }
    1709                 :            :     }
    1710                 :            : 
    1711                 :            :   /* Cannot delete them immediately because you may want to dump them
    1712                 :            :      if the comparison fails.  */
    1713                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1714                 :            :     {
    1715                 :          0 :       bitmap_clear (&problem_data->in[bb->index]);
    1716                 :          0 :       bitmap_clear (&problem_data->out[bb->index]);
    1717                 :            :     }
    1718                 :            : 
    1719                 :          0 :   free (problem_data->in);
    1720                 :          0 :   free (problem_data->out);
    1721                 :          0 :   free (problem_data);
    1722                 :          0 :   df_live->problem_data = NULL;
    1723                 :            : }
    1724                 :            : 
    1725                 :            : 
    1726                 :            : /* All of the information associated with every instance of the problem.  */
    1727                 :            : 
    1728                 :            : static const struct df_problem problem_LIVE =
    1729                 :            : {
    1730                 :            :   DF_LIVE,                      /* Problem id.  */
    1731                 :            :   DF_FORWARD,                   /* Direction.  */
    1732                 :            :   df_live_alloc,                /* Allocate the problem specific data.  */
    1733                 :            :   df_live_reset,                /* Reset global information.  */
    1734                 :            :   df_live_free_bb_info,         /* Free basic block info.  */
    1735                 :            :   df_live_local_compute,        /* Local compute function.  */
    1736                 :            :   df_live_init,                 /* Init the solution specific data.  */
    1737                 :            :   df_worklist_dataflow,         /* Worklist solver.  */
    1738                 :            :   NULL,                         /* Confluence operator 0.  */
    1739                 :            :   df_live_confluence_n,         /* Confluence operator n.  */
    1740                 :            :   df_live_transfer_function,    /* Transfer function.  */
    1741                 :            :   df_live_finalize,             /* Finalize function.  */
    1742                 :            :   df_live_free,                 /* Free all of the problem information.  */
    1743                 :            :   df_live_free,                 /* Remove this problem from the stack of dataflow problems.  */
    1744                 :            :   NULL,                         /* Debugging.  */
    1745                 :            :   df_live_top_dump,             /* Debugging start block.  */
    1746                 :            :   df_live_bottom_dump,          /* Debugging end block.  */
    1747                 :            :   NULL,                         /* Debugging start insn.  */
    1748                 :            :   NULL,                         /* Debugging end insn.  */
    1749                 :            :   df_live_verify_solution_start,/* Incremental solution verify start.  */
    1750                 :            :   df_live_verify_solution_end,  /* Incremental solution verify end.  */
    1751                 :            :   &problem_LR,                  /* Dependent problem.  */
    1752                 :            :   sizeof (class df_live_bb_info),/* Size of entry of block_info array.  */
    1753                 :            :   TV_DF_LIVE,                   /* Timing variable.  */
    1754                 :            :   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
    1755                 :            : };
    1756                 :            : 
    1757                 :            : 
    1758                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    1759                 :            :    of DF.  The returned structure is what is used to get at the
    1760                 :            :    solution.  */
    1761                 :            : 
    1762                 :            : void
    1763                 :    1464650 : df_live_add_problem (void)
    1764                 :            : {
    1765                 :    1464650 :   df_add_problem (&problem_LIVE);
    1766                 :            :   /* These will be initialized when df_scan_blocks processes each
    1767                 :            :      block.  */
    1768                 :    1464650 :   df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
    1769                 :    1464650 : }
    1770                 :            : 
    1771                 :            : 
    1772                 :            : /* Set all of the blocks as dirty.  This needs to be done if this
    1773                 :            :    problem is added after all of the insns have been scanned.  */
    1774                 :            : 
    1775                 :            : void
    1776                 :     969573 : df_live_set_all_dirty (void)
    1777                 :            : {
    1778                 :     969573 :   basic_block bb;
    1779                 :   14942000 :   FOR_ALL_BB_FN (bb, cfun)
    1780                 :   13972500 :     bitmap_set_bit (df_live->out_of_date_transfer_functions,
    1781                 :            :                     bb->index);
    1782                 :     969573 : }
    1783                 :            : 
    1784                 :            : 
    1785                 :            : /* Verify that all of the lr related info is consistent and
    1786                 :            :    correct.  */
    1787                 :            : 
    1788                 :            : void
    1789                 :          0 : df_live_verify_transfer_functions (void)
    1790                 :            : {
    1791                 :          0 :   basic_block bb;
    1792                 :          0 :   bitmap_head saved_gen;
    1793                 :          0 :   bitmap_head saved_kill;
    1794                 :          0 :   bitmap_head all_blocks;
    1795                 :            : 
    1796                 :          0 :   if (!df)
    1797                 :          0 :     return;
    1798                 :            : 
    1799                 :          0 :   bitmap_initialize (&saved_gen, &bitmap_default_obstack);
    1800                 :          0 :   bitmap_initialize (&saved_kill, &bitmap_default_obstack);
    1801                 :          0 :   bitmap_initialize (&all_blocks, &bitmap_default_obstack);
    1802                 :            : 
    1803                 :          0 :   df_grow_insn_info ();
    1804                 :            : 
    1805                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    1806                 :            :     {
    1807                 :          0 :       class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
    1808                 :          0 :       bitmap_set_bit (&all_blocks, bb->index);
    1809                 :            : 
    1810                 :          0 :       if (bb_info)
    1811                 :            :         {
    1812                 :            :           /* Make a copy of the transfer functions and then compute
    1813                 :            :              new ones to see if the transfer functions have
    1814                 :            :              changed.  */
    1815                 :          0 :           if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
    1816                 :            :                              bb->index))
    1817                 :            :             {
    1818                 :          0 :               bitmap_copy (&saved_gen, &bb_info->gen);
    1819                 :          0 :               bitmap_copy (&saved_kill, &bb_info->kill);
    1820                 :          0 :               bitmap_clear (&bb_info->gen);
    1821                 :          0 :               bitmap_clear (&bb_info->kill);
    1822                 :            : 
    1823                 :          0 :               df_live_bb_local_compute (bb->index);
    1824                 :          0 :               gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
    1825                 :          0 :               gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
    1826                 :            :             }
    1827                 :            :         }
    1828                 :            :       else
    1829                 :            :         {
    1830                 :            :           /* If we do not have basic block info, the block must be in
    1831                 :            :              the list of dirty blocks or else some one has added a
    1832                 :            :              block behind our backs. */
    1833                 :          0 :           gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
    1834                 :            :                                     bb->index));
    1835                 :            :         }
    1836                 :            :       /* Make sure no one created a block without following
    1837                 :            :          procedures.  */
    1838                 :          0 :       gcc_assert (df_scan_get_bb_info (bb->index));
    1839                 :            :     }
    1840                 :            : 
    1841                 :            :   /* Make sure there are no dirty bits in blocks that have been deleted.  */
    1842                 :          0 :   gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
    1843                 :            :                                          &all_blocks));
    1844                 :          0 :   bitmap_clear (&saved_gen);
    1845                 :          0 :   bitmap_clear (&saved_kill);
    1846                 :          0 :   bitmap_clear (&all_blocks);
    1847                 :            : }
    1848                 :            : 
    1849                 :            : /*----------------------------------------------------------------------------
    1850                 :            :    MUST-INITIALIZED REGISTERS.
    1851                 :            : ----------------------------------------------------------------------------*/
    1852                 :            : 
    1853                 :            : /* Private data used to verify the solution for this problem.  */
    1854                 :            : struct df_mir_problem_data
    1855                 :            : {
    1856                 :            :   bitmap_head *in;
    1857                 :            :   bitmap_head *out;
    1858                 :            :   /* An obstack for the bitmaps we need for this problem.  */
    1859                 :            :   bitmap_obstack mir_bitmaps;
    1860                 :            : };
    1861                 :            : 
    1862                 :            : 
    1863                 :            : /* Free basic block info.  */
    1864                 :            : 
    1865                 :            : static void
    1866                 :          0 : df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
    1867                 :            :                      void *vbb_info)
    1868                 :            : {
    1869                 :          0 :   class df_mir_bb_info *bb_info = (class df_mir_bb_info *) vbb_info;
    1870                 :          0 :   if (bb_info)
    1871                 :            :     {
    1872                 :          0 :       bitmap_clear (&bb_info->gen);
    1873                 :          0 :       bitmap_clear (&bb_info->kill);
    1874                 :          0 :       bitmap_clear (&bb_info->in);
    1875                 :          0 :       bitmap_clear (&bb_info->out);
    1876                 :            :     }
    1877                 :          0 : }
    1878                 :            : 
    1879                 :            : 
    1880                 :            : /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
    1881                 :            :    not touched unless the block is new.  */
    1882                 :            : 
    1883                 :            : static void
    1884                 :     644254 : df_mir_alloc (bitmap all_blocks)
    1885                 :            : {
    1886                 :     644254 :   unsigned int bb_index;
    1887                 :     644254 :   bitmap_iterator bi;
    1888                 :     644254 :   struct df_mir_problem_data *problem_data;
    1889                 :            : 
    1890                 :     644254 :   if (df_mir->problem_data)
    1891                 :            :     problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
    1892                 :            :   else
    1893                 :            :     {
    1894                 :     644254 :       problem_data = XNEW (struct df_mir_problem_data);
    1895                 :     644254 :       df_mir->problem_data = problem_data;
    1896                 :            : 
    1897                 :     644254 :       problem_data->out = NULL;
    1898                 :     644254 :       problem_data->in = NULL;
    1899                 :     644254 :       bitmap_obstack_initialize (&problem_data->mir_bitmaps);
    1900                 :            :     }
    1901                 :            : 
    1902                 :     644254 :   df_grow_bb_info (df_mir);
    1903                 :            : 
    1904                 :    8531010 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    1905                 :            :     {
    1906                 :    7886750 :       class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
    1907                 :            : 
    1908                 :            :       /* When bitmaps are already initialized, just clear them.  */
    1909                 :    7886750 :       if (bb_info->kill.obstack)
    1910                 :            :         {
    1911                 :          0 :           bitmap_clear (&bb_info->kill);
    1912                 :          0 :           bitmap_clear (&bb_info->gen);
    1913                 :            :         }
    1914                 :            :       else
    1915                 :            :         {
    1916                 :    7886750 :           bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
    1917                 :    7886750 :           bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
    1918                 :    7886750 :           bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
    1919                 :    7886750 :           bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
    1920                 :    7886750 :           bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
    1921                 :    7886750 :           bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
    1922                 :            :         }
    1923                 :            :     }
    1924                 :            : 
    1925                 :     644254 :   df_mir->optional_p = 1;
    1926                 :     644254 : }
    1927                 :            : 
    1928                 :            : 
    1929                 :            : /* Reset the global solution for recalculation.  */
    1930                 :            : 
    1931                 :            : static void
    1932                 :     644254 : df_mir_reset (bitmap all_blocks)
    1933                 :            : {
    1934                 :     644254 :   unsigned int bb_index;
    1935                 :     644254 :   bitmap_iterator bi;
    1936                 :            : 
    1937                 :    8531010 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    1938                 :            :     {
    1939                 :    7886750 :       class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
    1940                 :            : 
    1941                 :    7886750 :       gcc_assert (bb_info);
    1942                 :            : 
    1943                 :    7886750 :       bitmap_clear (&bb_info->in);
    1944                 :    7886750 :       bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
    1945                 :    7886750 :       bitmap_clear (&bb_info->out);
    1946                 :    7886750 :       bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
    1947                 :            :     }
    1948                 :     644254 : }
    1949                 :            : 
    1950                 :            : 
    1951                 :            : /* Compute local uninitialized register info for basic block BB.  */
    1952                 :            : 
    1953                 :            : static void
    1954                 :    7886750 : df_mir_bb_local_compute (unsigned int bb_index)
    1955                 :            : {
    1956                 :    7886750 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    1957                 :    7886750 :   class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
    1958                 :    7886750 :   rtx_insn *insn;
    1959                 :    7886750 :   int luid = 0;
    1960                 :            : 
    1961                 :            :   /* Ignoring artificial defs is intentional: these often pretend that some
    1962                 :            :      registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
    1963                 :            :      though they are not used for that.  As a result, conservatively assume
    1964                 :            :      they may be uninitialized.  */
    1965                 :            : 
    1966                 :  162645000 :   FOR_BB_INSNS (bb, insn)
    1967                 :            :     {
    1968                 :   77379100 :       unsigned int uid = INSN_UID (insn);
    1969                 :   77379100 :       struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
    1970                 :            : 
    1971                 :            :       /* Inserting labels does not always trigger the incremental
    1972                 :            :          rescanning.  */
    1973                 :   77379100 :       if (!insn_info)
    1974                 :            :         {
    1975                 :       2330 :           gcc_assert (!INSN_P (insn));
    1976                 :       2330 :           insn_info = df_insn_create_insn_record (insn);
    1977                 :            :         }
    1978                 :            : 
    1979                 :   77379100 :       DF_INSN_INFO_LUID (insn_info) = luid;
    1980                 :   77379100 :       if (!INSN_P (insn))
    1981                 :   14055700 :         continue;
    1982                 :            : 
    1983                 :   63323400 :       luid++;
    1984                 :   63323400 :       df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
    1985                 :            :     }
    1986                 :    7886750 : }
    1987                 :            : 
    1988                 :            : 
    1989                 :            : /* Compute local uninitialized register info.  */
    1990                 :            : 
    1991                 :            : static void
    1992                 :     644254 : df_mir_local_compute (bitmap all_blocks)
    1993                 :            : {
    1994                 :     644254 :   unsigned int bb_index;
    1995                 :     644254 :   bitmap_iterator bi;
    1996                 :            : 
    1997                 :     644254 :   df_grow_insn_info ();
    1998                 :            : 
    1999                 :    8531010 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    2000                 :            :     {
    2001                 :    7886750 :       df_mir_bb_local_compute (bb_index);
    2002                 :            :     }
    2003                 :     644254 : }
    2004                 :            : 
    2005                 :            : 
    2006                 :            : /* Initialize the solution vectors.  */
    2007                 :            : 
    2008                 :            : static void
    2009                 :     644254 : df_mir_init (bitmap all_blocks)
    2010                 :            : {
    2011                 :     644254 :   df_mir_reset (all_blocks);
    2012                 :     644254 : }
    2013                 :            : 
    2014                 :            : 
    2015                 :            : /* Initialize IN sets for blocks with no predecessors: when landing on such
    2016                 :            :    blocks, assume all registers are uninitialized.  */
    2017                 :            : 
    2018                 :            : static void
    2019                 :     661440 : df_mir_confluence_0 (basic_block bb)
    2020                 :            : {
    2021                 :     661440 :   class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
    2022                 :            : 
    2023                 :     661440 :   bitmap_clear (&bb_info->in);
    2024                 :     661440 : }
    2025                 :            : 
    2026                 :            : 
    2027                 :            : /* Forward confluence function that ignores fake edges.  */
    2028                 :            : 
    2029                 :            : static bool
    2030                 :   11232300 : df_mir_confluence_n (edge e)
    2031                 :            : {
    2032                 :   11232300 :   bitmap op1 = &df_mir_get_bb_info (e->dest->index)->in;
    2033                 :   11232300 :   bitmap op2 = &df_mir_get_bb_info (e->src->index)->out;
    2034                 :            : 
    2035                 :   11232300 :   if (e->flags & EDGE_FAKE)
    2036                 :            :     return false;
    2037                 :            : 
    2038                 :            :   /* A register is must-initialized at the entry of a basic block iff it is
    2039                 :            :      must-initialized at the exit of all the predecessors.  */
    2040                 :   11232300 :   return bitmap_and_into (op1, op2);
    2041                 :            : }
    2042                 :            : 
    2043                 :            : 
    2044                 :            : /* Transfer function for the forwards must-initialized problem.  */
    2045                 :            : 
    2046                 :            : static bool
    2047                 :    8406600 : df_mir_transfer_function (int bb_index)
    2048                 :            : {
    2049                 :    8406600 :   class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
    2050                 :    8406600 :   bitmap in = &bb_info->in;
    2051                 :    8406600 :   bitmap out = &bb_info->out;
    2052                 :    8406600 :   bitmap gen = &bb_info->gen;
    2053                 :    8406600 :   bitmap kill = &bb_info->kill;
    2054                 :            : 
    2055                 :    8406600 :   return bitmap_ior_and_compl (out, gen, in, kill);
    2056                 :            : }
    2057                 :            : 
    2058                 :            : 
    2059                 :            : /* Free all storage associated with the problem.  */
    2060                 :            : 
    2061                 :            : static void
    2062                 :     644254 : df_mir_free (void)
    2063                 :            : {
    2064                 :     644254 :   struct df_mir_problem_data *problem_data
    2065                 :     644254 :     = (struct df_mir_problem_data *) df_mir->problem_data;
    2066                 :     644254 :   if (df_mir->block_info)
    2067                 :            :     {
    2068                 :     644254 :       df_mir->block_info_size = 0;
    2069                 :     644254 :       free (df_mir->block_info);
    2070                 :     644254 :       df_mir->block_info = NULL;
    2071                 :     644254 :       bitmap_obstack_release (&problem_data->mir_bitmaps);
    2072                 :     644254 :       free (problem_data);
    2073                 :     644254 :       df_mir->problem_data = NULL;
    2074                 :            :     }
    2075                 :     644254 :   free (df_mir);
    2076                 :     644254 : }
    2077                 :            : 
    2078                 :            : 
    2079                 :            : /* Debugging info at top of bb.  */
    2080                 :            : 
    2081                 :            : static void
    2082                 :          0 : df_mir_top_dump (basic_block bb, FILE *file)
    2083                 :            : {
    2084                 :          0 :   class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
    2085                 :            : 
    2086                 :          0 :   if (!bb_info)
    2087                 :            :     return;
    2088                 :            : 
    2089                 :          0 :   fprintf (file, ";; mir   in  \t");
    2090                 :          0 :   df_print_regset (file, &bb_info->in);
    2091                 :          0 :   fprintf (file, ";; mir   kill\t");
    2092                 :          0 :   df_print_regset (file, &bb_info->kill);
    2093                 :          0 :   fprintf (file, ";; mir   gen \t");
    2094                 :          0 :   df_print_regset (file, &bb_info->gen);
    2095                 :            : }
    2096                 :            : 
    2097                 :            : /* Debugging info at bottom of bb.  */
    2098                 :            : 
    2099                 :            : static void
    2100                 :          0 : df_mir_bottom_dump (basic_block bb, FILE *file)
    2101                 :            : {
    2102                 :          0 :   class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
    2103                 :            : 
    2104                 :          0 :   if (!bb_info)
    2105                 :            :     return;
    2106                 :            : 
    2107                 :          0 :   fprintf (file, ";; mir   out \t");
    2108                 :          0 :   df_print_regset (file, &bb_info->out);
    2109                 :            : }
    2110                 :            : 
    2111                 :            : 
    2112                 :            : /* Build the datastructure to verify that the solution to the dataflow
    2113                 :            :    equations is not dirty.  */
    2114                 :            : 
    2115                 :            : static void
    2116                 :          0 : df_mir_verify_solution_start (void)
    2117                 :            : {
    2118                 :          0 :   basic_block bb;
    2119                 :          0 :   struct df_mir_problem_data *problem_data;
    2120                 :          0 :   if (df_mir->solutions_dirty)
    2121                 :            :     return;
    2122                 :            : 
    2123                 :            :   /* Set it true so that the solution is recomputed.  */
    2124                 :          0 :   df_mir->solutions_dirty = true;
    2125                 :            : 
    2126                 :          0 :   problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
    2127                 :          0 :   problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    2128                 :          0 :   problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    2129                 :          0 :   bitmap_obstack_initialize (&problem_data->mir_bitmaps);
    2130                 :            : 
    2131                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    2132                 :            :     {
    2133                 :          0 :       bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
    2134                 :          0 :       bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
    2135                 :          0 :       bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
    2136                 :          0 :       bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
    2137                 :            :     }
    2138                 :            : }
    2139                 :            : 
    2140                 :            : 
    2141                 :            : /* Compare the saved datastructure and the new solution to the dataflow
    2142                 :            :    equations.  */
    2143                 :            : 
    2144                 :            : static void
    2145                 :          0 : df_mir_verify_solution_end (void)
    2146                 :            : {
    2147                 :          0 :   struct df_mir_problem_data *problem_data;
    2148                 :          0 :   basic_block bb;
    2149                 :            : 
    2150                 :          0 :   problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
    2151                 :          0 :   if (!problem_data->out)
    2152                 :            :     return;
    2153                 :            : 
    2154                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    2155                 :            :     {
    2156                 :          0 :       if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
    2157                 :          0 :           || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
    2158                 :          0 :         gcc_unreachable ();
    2159                 :            :     }
    2160                 :            : 
    2161                 :            :   /* Cannot delete them immediately because you may want to dump them
    2162                 :            :      if the comparison fails.  */
    2163                 :          0 :   FOR_ALL_BB_FN (bb, cfun)
    2164                 :            :     {
    2165                 :          0 :       bitmap_clear (&problem_data->in[bb->index]);
    2166                 :          0 :       bitmap_clear (&problem_data->out[bb->index]);
    2167                 :            :     }
    2168                 :            : 
    2169                 :          0 :   free (problem_data->in);
    2170                 :          0 :   free (problem_data->out);
    2171                 :          0 :   bitmap_obstack_release (&problem_data->mir_bitmaps);
    2172                 :          0 :   free (problem_data);
    2173                 :          0 :   df_mir->problem_data = NULL;
    2174                 :            : }
    2175                 :            : 
    2176                 :            : 
    2177                 :            : /* All of the information associated with every instance of the problem.  */
    2178                 :            : 
    2179                 :            : static const struct df_problem problem_MIR =
    2180                 :            : {
    2181                 :            :   DF_MIR,                       /* Problem id.  */
    2182                 :            :   DF_FORWARD,                   /* Direction.  */
    2183                 :            :   df_mir_alloc,                 /* Allocate the problem specific data.  */
    2184                 :            :   df_mir_reset,                 /* Reset global information.  */
    2185                 :            :   df_mir_free_bb_info,          /* Free basic block info.  */
    2186                 :            :   df_mir_local_compute,         /* Local compute function.  */
    2187                 :            :   df_mir_init,                  /* Init the solution specific data.  */
    2188                 :            :   df_worklist_dataflow,         /* Worklist solver.  */
    2189                 :            :   df_mir_confluence_0,          /* Confluence operator 0.  */
    2190                 :            :   df_mir_confluence_n,          /* Confluence operator n.  */
    2191                 :            :   df_mir_transfer_function,     /* Transfer function.  */
    2192                 :            :   NULL,                         /* Finalize function.  */
    2193                 :            :   df_mir_free,                  /* Free all of the problem information.  */
    2194                 :            :   df_mir_free,                  /* Remove this problem from the stack of dataflow problems.  */
    2195                 :            :   NULL,                         /* Debugging.  */
    2196                 :            :   df_mir_top_dump,              /* Debugging start block.  */
    2197                 :            :   df_mir_bottom_dump,           /* Debugging end block.  */
    2198                 :            :   NULL,                         /* Debugging start insn.  */
    2199                 :            :   NULL,                         /* Debugging end insn.  */
    2200                 :            :   df_mir_verify_solution_start, /* Incremental solution verify start.  */
    2201                 :            :   df_mir_verify_solution_end,   /* Incremental solution verify end.  */
    2202                 :            :   NULL,                         /* Dependent problem.  */
    2203                 :            :   sizeof (class df_mir_bb_info),/* Size of entry of block_info array.  */
    2204                 :            :   TV_DF_MIR,                    /* Timing variable.  */
    2205                 :            :   false                         /* Reset blocks on dropping out of blocks_to_analyze.  */
    2206                 :            : };
    2207                 :            : 
    2208                 :            : 
    2209                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    2210                 :            :    of DF.  */
    2211                 :            : 
    2212                 :            : void
    2213                 :     644254 : df_mir_add_problem (void)
    2214                 :            : {
    2215                 :     644254 :   df_add_problem (&problem_MIR);
    2216                 :            :   /* These will be initialized when df_scan_blocks processes each
    2217                 :            :      block.  */
    2218                 :     644254 :   df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
    2219                 :     644254 : }
    2220                 :            : 
    2221                 :            : 
    2222                 :            : /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps.  */
    2223                 :            : 
    2224                 :            : void
    2225                 :   98886400 : df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
    2226                 :            :                           bitmap kill, bitmap gen)
    2227                 :            : {
    2228                 :   98886400 :   df_ref def;
    2229                 :            : 
    2230                 :  542905000 :   FOR_EACH_INSN_DEF (def, insn)
    2231                 :            :     {
    2232                 :  444018000 :       unsigned int regno = DF_REF_REGNO (def);
    2233                 :            : 
    2234                 :            :       /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
    2235                 :            :          previous gen is irrelevant (and reciprocally).  Also, claim that a
    2236                 :            :          register is GEN only if it is in all cases.  */
    2237                 :  444018000 :       if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
    2238                 :            :         {
    2239                 :  396094000 :           bitmap_set_bit (kill, regno);
    2240                 :  396094000 :           bitmap_clear_bit (gen, regno);
    2241                 :            :         }
    2242                 :            :       /* In the worst case, partial and conditional defs can leave bits
    2243                 :            :          uninitialized, so assume they do not change anything.  */
    2244                 :   47923700 :       else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
    2245                 :            :         {
    2246                 :   47902800 :           bitmap_set_bit (gen, regno);
    2247                 :   47902800 :           bitmap_clear_bit (kill, regno);
    2248                 :            :         }
    2249                 :            :     }
    2250                 :   98886400 : }
    2251                 :            : 
    2252                 :            : /*----------------------------------------------------------------------------
    2253                 :            :    CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
    2254                 :            : 
    2255                 :            :    Link either the defs to the uses and / or the uses to the defs.
    2256                 :            : 
    2257                 :            :    These problems are set up like the other dataflow problems so that
    2258                 :            :    they nicely fit into the framework.  They are much simpler and only
    2259                 :            :    involve a single traversal of instructions and an examination of
    2260                 :            :    the reaching defs information (the dependent problem).
    2261                 :            : ----------------------------------------------------------------------------*/
    2262                 :            : 
    2263                 :            : #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
    2264                 :            : 
    2265                 :            : /* Create a du or ud chain from SRC to DST and link it into SRC.   */
    2266                 :            : 
    2267                 :            : struct df_link *
    2268                 :  570719000 : df_chain_create (df_ref src, df_ref dst)
    2269                 :            : {
    2270                 :  570719000 :   struct df_link *head = DF_REF_CHAIN (src);
    2271                 :  570719000 :   struct df_link *link = df_chain->block_pool->allocate ();
    2272                 :            : 
    2273                 :  570719000 :   DF_REF_CHAIN (src) = link;
    2274                 :  570719000 :   link->next = head;
    2275                 :  570719000 :   link->ref = dst;
    2276                 :  570719000 :   return link;
    2277                 :            : }
    2278                 :            : 
    2279                 :            : 
    2280                 :            : /* Delete any du or ud chains that start at REF and point to
    2281                 :            :    TARGET.  */
    2282                 :            : static void
    2283                 :     208414 : df_chain_unlink_1 (df_ref ref, df_ref target)
    2284                 :            : {
    2285                 :     208414 :   struct df_link *chain = DF_REF_CHAIN (ref);
    2286                 :     208414 :   struct df_link *prev = NULL;
    2287                 :            : 
    2288                 :   19880900 :   while (chain)
    2289                 :            :     {
    2290                 :   19879000 :       if (chain->ref == target)
    2291                 :            :         {
    2292                 :     206571 :           if (prev)
    2293                 :     108557 :             prev->next = chain->next;
    2294                 :            :           else
    2295                 :      98014 :             DF_REF_CHAIN (ref) = chain->next;
    2296                 :     206571 :           df_chain->block_pool->remove (chain);
    2297                 :     206571 :           return;
    2298                 :            :         }
    2299                 :   19672500 :       prev = chain;
    2300                 :   19672500 :       chain = chain->next;
    2301                 :            :     }
    2302                 :            : }
    2303                 :            : 
    2304                 :            : 
    2305                 :            : /* Delete a du or ud chain that leave or point to REF.  */
    2306                 :            : 
    2307                 :            : void
    2308                 :     156114 : df_chain_unlink (df_ref ref)
    2309                 :            : {
    2310                 :     156114 :   struct df_link *chain = DF_REF_CHAIN (ref);
    2311                 :     364528 :   while (chain)
    2312                 :            :     {
    2313                 :     208414 :       struct df_link *next = chain->next;
    2314                 :            :       /* Delete the other side if it exists.  */
    2315                 :     208414 :       df_chain_unlink_1 (chain->ref, ref);
    2316                 :     208414 :       df_chain->block_pool->remove (chain);
    2317                 :     208414 :       chain = next;
    2318                 :            :     }
    2319                 :     156114 :   DF_REF_CHAIN (ref) = NULL;
    2320                 :     156114 : }
    2321                 :            : 
    2322                 :            : 
    2323                 :            : /* Copy the du or ud chain starting at FROM_REF and attach it to
    2324                 :            :    TO_REF.  */
    2325                 :            : 
    2326                 :            : void
    2327                 :          0 : df_chain_copy (df_ref to_ref,
    2328                 :            :                struct df_link *from_ref)
    2329                 :            : {
    2330                 :          0 :   while (from_ref)
    2331                 :            :     {
    2332                 :          0 :       df_chain_create (to_ref, from_ref->ref);
    2333                 :          0 :       from_ref = from_ref->next;
    2334                 :            :     }
    2335                 :          0 : }
    2336                 :            : 
    2337                 :            : 
    2338                 :            : /* Remove this problem from the stack of dataflow problems.  */
    2339                 :            : 
    2340                 :            : static void
    2341                 :    5746190 : df_chain_remove_problem (void)
    2342                 :            : {
    2343                 :    5746190 :   bitmap_iterator bi;
    2344                 :    5746190 :   unsigned int bb_index;
    2345                 :            : 
    2346                 :            :   /* Wholesale destruction of the old chains.  */
    2347                 :    5746190 :   if (df_chain->block_pool)
    2348                 :    5740470 :     delete df_chain->block_pool;
    2349                 :            : 
    2350                 :   38340300 :   EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
    2351                 :            :     {
    2352                 :   32594100 :       rtx_insn *insn;
    2353                 :   32594100 :       df_ref def, use;
    2354                 :   32594100 :       basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    2355                 :            : 
    2356                 :   32594100 :       if (df_chain_problem_p (DF_DU_CHAIN))
    2357                 :   75558800 :         FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    2358                 :   32354300 :           DF_REF_CHAIN (def) = NULL;
    2359                 :   32594100 :       if (df_chain_problem_p (DF_UD_CHAIN))
    2360                 :  164643000 :         FOR_EACH_ARTIFICIAL_USE (use, bb_index)
    2361                 :   99455200 :           DF_REF_CHAIN (use) = NULL;
    2362                 :            : 
    2363                 :  675786000 :       FOR_BB_INSNS (bb, insn)
    2364                 :  321596000 :         if (INSN_P (insn))
    2365                 :            :           {
    2366                 :  272002000 :             df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    2367                 :  272002000 :             if (df_chain_problem_p (DF_DU_CHAIN))
    2368                 :  801243000 :               FOR_EACH_INSN_INFO_DEF (def, insn_info)
    2369                 :  622828000 :                 DF_REF_CHAIN (def) = NULL;
    2370                 :  272002000 :             if (df_chain_problem_p (DF_UD_CHAIN))
    2371                 :            :               {
    2372                 :  490927000 :                 FOR_EACH_INSN_INFO_USE (use, insn_info)
    2373                 :  218925000 :                   DF_REF_CHAIN (use) = NULL;
    2374                 :  278529000 :                 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
    2375                 :    6526370 :                   DF_REF_CHAIN (use) = NULL;
    2376                 :            :               }
    2377                 :            :           }
    2378                 :            :     }
    2379                 :            : 
    2380                 :    5746190 :   bitmap_clear (df_chain->out_of_date_transfer_functions);
    2381                 :    5746190 :   df_chain->block_pool = NULL;
    2382                 :    5746190 : }
    2383                 :            : 
    2384                 :            : 
    2385                 :            : /* Remove the chain problem completely.  */
    2386                 :            : 
    2387                 :            : static void
    2388                 :    2873100 : df_chain_fully_remove_problem (void)
    2389                 :            : {
    2390                 :    2873100 :   df_chain_remove_problem ();
    2391                 :    2873100 :   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
    2392                 :    2873100 :   free (df_chain);
    2393                 :    2873100 : }
    2394                 :            : 
    2395                 :            : 
    2396                 :            : /* Create def-use or use-def chains.  */
    2397                 :            : 
    2398                 :            : static void
    2399                 :    2873100 : df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
    2400                 :            : {
    2401                 :    2873100 :   df_chain_remove_problem ();
    2402                 :    2873100 :   df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
    2403                 :    2873100 :   df_chain->optional_p = true;
    2404                 :    2873100 : }
    2405                 :            : 
    2406                 :            : 
    2407                 :            : /* Reset all of the chains when the set of basic blocks changes.  */
    2408                 :            : 
    2409                 :            : static void
    2410                 :          0 : df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
    2411                 :            : {
    2412                 :          0 :   df_chain_remove_problem ();
    2413                 :          0 : }
    2414                 :            : 
    2415                 :            : 
    2416                 :            : /* Create the chains for a list of USEs.  */
    2417                 :            : 
    2418                 :            : static void
    2419                 :  330040000 : df_chain_create_bb_process_use (bitmap local_rd,
    2420                 :            :                                 df_ref use,
    2421                 :            :                                 int top_flag)
    2422                 :            : {
    2423                 :  645117000 :   bitmap_iterator bi;
    2424                 :  645117000 :   unsigned int def_index;
    2425                 :            : 
    2426                 :  645117000 :   for (; use; use = DF_REF_NEXT_LOC (use))
    2427                 :            :     {
    2428                 :  315077000 :       unsigned int uregno = DF_REF_REGNO (use);
    2429                 :  315077000 :       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
    2430                 :    3782160 :           || (uregno >= FIRST_PSEUDO_REGISTER))
    2431                 :            :         {
    2432                 :            :           /* Do not want to go through this for an uninitialized var.  */
    2433                 :  314105000 :           int count = DF_DEFS_COUNT (uregno);
    2434                 :  314105000 :           if (count)
    2435                 :            :             {
    2436                 :  299315000 :               if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
    2437                 :            :                 {
    2438                 :  299315000 :                   unsigned int first_index = DF_DEFS_BEGIN (uregno);
    2439                 :  299315000 :                   unsigned int last_index = first_index + count - 1;
    2440                 :            : 
    2441                 :  643191000 :                   EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
    2442                 :            :                     {
    2443                 :  615637000 :                       df_ref def;
    2444                 :  615637000 :                       if (def_index > last_index)
    2445                 :            :                         break;
    2446                 :            : 
    2447                 :  343875000 :                       def = DF_DEFS_GET (def_index);
    2448                 :  343875000 :                       if (df_chain_problem_p (DF_DU_CHAIN))
    2449                 :  226843000 :                         df_chain_create (def, use);
    2450                 :  343875000 :                       if (df_chain_problem_p (DF_UD_CHAIN))
    2451                 :  343875000 :                         df_chain_create (use, def);
    2452                 :            :                     }
    2453                 :            :                 }
    2454                 :            :             }
    2455                 :            :         }
    2456                 :            :     }
    2457                 :  330040000 : }
    2458                 :            : 
    2459                 :            : 
    2460                 :            : /* Create chains from reaching defs bitmaps for basic block BB.  */
    2461                 :            : 
    2462                 :            : static void
    2463                 :   32216400 : df_chain_create_bb (unsigned int bb_index)
    2464                 :            : {
    2465                 :   32216400 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    2466                 :   32216400 :   class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
    2467                 :   32216400 :   rtx_insn *insn;
    2468                 :   32216400 :   bitmap_head cpy;
    2469                 :            : 
    2470                 :   32216400 :   bitmap_initialize (&cpy, &bitmap_default_obstack);
    2471                 :   32216400 :   bitmap_copy (&cpy, &bb_info->in);
    2472                 :   32216400 :   bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
    2473                 :            : 
    2474                 :            :   /* Since we are going forwards, process the artificial uses first
    2475                 :            :      then the artificial defs second.  */
    2476                 :            : 
    2477                 :            : #ifdef EH_USES
    2478                 :            :   /* Create the chains for the artificial uses from the EH_USES at the
    2479                 :            :      beginning of the block.  */
    2480                 :            : 
    2481                 :            :   /* Artificials are only hard regs.  */
    2482                 :            :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
    2483                 :            :     df_chain_create_bb_process_use (&cpy,
    2484                 :            :                                     df_get_artificial_uses (bb->index),
    2485                 :            :                                     DF_REF_AT_TOP);
    2486                 :            : #endif
    2487                 :            : 
    2488                 :   32216400 :   df_rd_simulate_artificial_defs_at_top (bb, &cpy);
    2489                 :            : 
    2490                 :            :   /* Process the regular instructions next.  */
    2491                 :  670063000 :   FOR_BB_INSNS (bb, insn)
    2492                 :  318923000 :     if (INSN_P (insn))
    2493                 :            :       {
    2494                 :  269873000 :         unsigned int uid = INSN_UID (insn);
    2495                 :            : 
    2496                 :            :         /* First scan the uses and link them up with the defs that remain
    2497                 :            :            in the cpy vector.  */
    2498                 :  269873000 :         df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
    2499                 :  269873000 :         if (df->changeable_flags & DF_EQ_NOTES)
    2500                 :   28326300 :           df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
    2501                 :            : 
    2502                 :            :         /* Since we are going forwards, process the defs second.  */
    2503                 :  269873000 :         df_rd_simulate_one_insn (bb, insn, &cpy);
    2504                 :            :       }
    2505                 :            : 
    2506                 :            :   /* Create the chains for the artificial uses of the hard registers
    2507                 :            :      at the end of the block.  */
    2508                 :   32216400 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
    2509                 :   31840900 :     df_chain_create_bb_process_use (&cpy,
    2510                 :   31840900 :                                     df_get_artificial_uses (bb->index),
    2511                 :            :                                     0);
    2512                 :            : 
    2513                 :   32216400 :   bitmap_clear (&cpy);
    2514                 :   32216400 : }
    2515                 :            : 
    2516                 :            : /* Create def-use chains from reaching use bitmaps for basic blocks
    2517                 :            :    in BLOCKS.  */
    2518                 :            : 
    2519                 :            : static void
    2520                 :    2873100 : df_chain_finalize (bitmap all_blocks)
    2521                 :            : {
    2522                 :    2873100 :   unsigned int bb_index;
    2523                 :    2873100 :   bitmap_iterator bi;
    2524                 :            : 
    2525                 :   35089500 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    2526                 :            :     {
    2527                 :   32216400 :       df_chain_create_bb (bb_index);
    2528                 :            :     }
    2529                 :    2873100 : }
    2530                 :            : 
    2531                 :            : 
    2532                 :            : /* Free all storage associated with the problem.  */
    2533                 :            : 
    2534                 :            : static void
    2535                 :          0 : df_chain_free (void)
    2536                 :            : {
    2537                 :          0 :   delete df_chain->block_pool;
    2538                 :          0 :   BITMAP_FREE (df_chain->out_of_date_transfer_functions);
    2539                 :          0 :   free (df_chain);
    2540                 :          0 : }
    2541                 :            : 
    2542                 :            : 
    2543                 :            : /* Debugging info.  */
    2544                 :            : 
    2545                 :            : static void
    2546                 :       1300 : df_chain_bb_dump (basic_block bb, FILE *file, bool top)
    2547                 :            : {
    2548                 :            :   /* Artificials are only hard regs.  */
    2549                 :       1300 :   if (df->changeable_flags & DF_NO_HARD_REGS)
    2550                 :            :     return;
    2551                 :       1300 :   if (df_chain_problem_p (DF_UD_CHAIN))
    2552                 :            :     {
    2553                 :       1300 :       df_ref use;
    2554                 :            : 
    2555                 :       1950 :       fprintf (file,
    2556                 :            :                ";;  UD chains for artificial uses at %s\n",
    2557                 :            :                top ? "top" : "bottom");
    2558                 :       7624 :       FOR_EACH_ARTIFICIAL_USE (use, bb->index)
    2559                 :       5024 :         if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
    2560                 :       5024 :             || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
    2561                 :            :           {
    2562                 :       2512 :             fprintf (file, ";;   reg %d ", DF_REF_REGNO (use));
    2563                 :       2512 :             df_chain_dump (DF_REF_CHAIN (use), file);
    2564                 :       2512 :             fprintf (file, "\n");
    2565                 :            :           }
    2566                 :            :     }
    2567                 :       1300 :   if (df_chain_problem_p (DF_DU_CHAIN))
    2568                 :            :     {
    2569                 :          0 :       df_ref def;
    2570                 :            : 
    2571                 :          0 :       fprintf (file,
    2572                 :            :                ";;  DU chains for artificial defs at %s\n",
    2573                 :            :                top ? "top" : "bottom");
    2574                 :          0 :       FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
    2575                 :          0 :         if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
    2576                 :          0 :             || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
    2577                 :            :           {
    2578                 :          0 :             fprintf (file, ";;   reg %d ", DF_REF_REGNO (def));
    2579                 :          0 :             df_chain_dump (DF_REF_CHAIN (def), file);
    2580                 :          0 :             fprintf (file, "\n");
    2581                 :            :           }
    2582                 :            :     }
    2583                 :            : }
    2584                 :            : 
    2585                 :            : static void
    2586                 :        650 : df_chain_top_dump (basic_block bb, FILE *file)
    2587                 :            : {
    2588                 :        650 :   df_chain_bb_dump (bb, file, /*top=*/true);
    2589                 :        650 : }
    2590                 :            : 
    2591                 :            : static void
    2592                 :        650 : df_chain_bottom_dump (basic_block bb, FILE *file)
    2593                 :            : {
    2594                 :        650 :   df_chain_bb_dump (bb, file, /*top=*/false);
    2595                 :        650 : }
    2596                 :            : 
    2597                 :            : static void
    2598                 :       2139 : df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
    2599                 :            : {
    2600                 :       2139 :   if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
    2601                 :            :     {
    2602                 :       1285 :       struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    2603                 :       1285 :       df_ref use;
    2604                 :            : 
    2605                 :       1285 :       fprintf (file, ";;   UD chains for insn luid %d uid %d\n",
    2606                 :            :                DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
    2607                 :       2884 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
    2608                 :       1599 :         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
    2609                 :        574 :             || !(df->changeable_flags & DF_NO_HARD_REGS))
    2610                 :            :           {
    2611                 :       1599 :             fprintf (file, ";;      reg %d ", DF_REF_REGNO (use));
    2612                 :       1599 :             if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
    2613                 :          0 :               fprintf (file, "read/write ");
    2614                 :       1599 :             df_chain_dump (DF_REF_CHAIN (use), file);
    2615                 :       1599 :             fprintf (file, "\n");
    2616                 :            :           }
    2617                 :       1338 :       FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
    2618                 :         53 :         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
    2619                 :          9 :             || !(df->changeable_flags & DF_NO_HARD_REGS))
    2620                 :            :           {
    2621                 :         53 :             fprintf (file, ";;   eq_note reg %d ", DF_REF_REGNO (use));
    2622                 :         53 :             df_chain_dump (DF_REF_CHAIN (use), file);
    2623                 :         53 :             fprintf (file, "\n");
    2624                 :            :           }
    2625                 :            :     }
    2626                 :       2139 : }
    2627                 :            : 
    2628                 :            : static void
    2629                 :       2139 : df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
    2630                 :            : {
    2631                 :       2139 :   if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
    2632                 :            :     {
    2633                 :          0 :       struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    2634                 :          0 :       df_ref def;
    2635                 :          0 :       fprintf (file, ";;   DU chains for insn luid %d uid %d\n",
    2636                 :            :                DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
    2637                 :          0 :       FOR_EACH_INSN_INFO_DEF (def, insn_info)
    2638                 :          0 :         if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
    2639                 :          0 :             || !(df->changeable_flags & DF_NO_HARD_REGS))
    2640                 :            :           {
    2641                 :          0 :             fprintf (file, ";;      reg %d ", DF_REF_REGNO (def));
    2642                 :          0 :             if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
    2643                 :          0 :               fprintf (file, "read/write ");
    2644                 :          0 :             df_chain_dump (DF_REF_CHAIN (def), file);
    2645                 :          0 :             fprintf (file, "\n");
    2646                 :            :           }
    2647                 :          0 :       fprintf (file, "\n");
    2648                 :            :     }
    2649                 :       2139 : }
    2650                 :            : 
    2651                 :            : static const struct df_problem problem_CHAIN =
    2652                 :            : {
    2653                 :            :   DF_CHAIN,                   /* Problem id.  */
    2654                 :            :   DF_NONE,                    /* Direction.  */
    2655                 :            :   df_chain_alloc,             /* Allocate the problem specific data.  */
    2656                 :            :   df_chain_reset,             /* Reset global information.  */
    2657                 :            :   NULL,                       /* Free basic block info.  */
    2658                 :            :   NULL,                       /* Local compute function.  */
    2659                 :            :   NULL,                       /* Init the solution specific data.  */
    2660                 :            :   NULL,                       /* Iterative solver.  */
    2661                 :            :   NULL,                       /* Confluence operator 0.  */
    2662                 :            :   NULL,                       /* Confluence operator n.  */
    2663                 :            :   NULL,                       /* Transfer function.  */
    2664                 :            :   df_chain_finalize,          /* Finalize function.  */
    2665                 :            :   df_chain_free,              /* Free all of the problem information.  */
    2666                 :            :   df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems.  */
    2667                 :            :   NULL,                       /* Debugging.  */
    2668                 :            :   df_chain_top_dump,          /* Debugging start block.  */
    2669                 :            :   df_chain_bottom_dump,       /* Debugging end block.  */
    2670                 :            :   df_chain_insn_top_dump,     /* Debugging start insn.  */
    2671                 :            :   df_chain_insn_bottom_dump,  /* Debugging end insn.  */
    2672                 :            :   NULL,                       /* Incremental solution verify start.  */
    2673                 :            :   NULL,                       /* Incremental solution verify end.  */
    2674                 :            :   &problem_RD,                /* Dependent problem.  */
    2675                 :            :   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
    2676                 :            :   TV_DF_CHAIN,                /* Timing variable.  */
    2677                 :            :   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
    2678                 :            : };
    2679                 :            : 
    2680                 :            : 
    2681                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    2682                 :            :    of DF.  The returned structure is what is used to get at the
    2683                 :            :    solution.  */
    2684                 :            : 
    2685                 :            : void
    2686                 :    2873100 : df_chain_add_problem (unsigned int chain_flags)
    2687                 :            : {
    2688                 :    2873100 :   df_add_problem (&problem_CHAIN);
    2689                 :    2873100 :   df_chain->local_flags = chain_flags;
    2690                 :    2873100 :   df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
    2691                 :    2873100 : }
    2692                 :            : 
    2693                 :            : #undef df_chain_problem_p
    2694                 :            : 
    2695                 :            : 
    2696                 :            : /*----------------------------------------------------------------------------
    2697                 :            :    WORD LEVEL LIVE REGISTERS
    2698                 :            : 
    2699                 :            :    Find the locations in the function where any use of a pseudo can
    2700                 :            :    reach in the backwards direction.  In and out bitvectors are built
    2701                 :            :    for each basic block.  We only track pseudo registers that have a
    2702                 :            :    size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
    2703                 :            :    contain two bits corresponding to each of the subwords.
    2704                 :            : 
    2705                 :            :    ----------------------------------------------------------------------------*/
    2706                 :            : 
    2707                 :            : /* Private data used to verify the solution for this problem.  */
    2708                 :            : struct df_word_lr_problem_data
    2709                 :            : {
    2710                 :            :   /* An obstack for the bitmaps we need for this problem.  */
    2711                 :            :   bitmap_obstack word_lr_bitmaps;
    2712                 :            : };
    2713                 :            : 
    2714                 :            : 
    2715                 :            : /* Free basic block info.  */
    2716                 :            : 
    2717                 :            : static void
    2718                 :          0 : df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
    2719                 :            :                          void *vbb_info)
    2720                 :            : {
    2721                 :          0 :   class df_word_lr_bb_info *bb_info = (class df_word_lr_bb_info *) vbb_info;
    2722                 :          0 :   if (bb_info)
    2723                 :            :     {
    2724                 :          0 :       bitmap_clear (&bb_info->use);
    2725                 :          0 :       bitmap_clear (&bb_info->def);
    2726                 :          0 :       bitmap_clear (&bb_info->in);
    2727                 :          0 :       bitmap_clear (&bb_info->out);
    2728                 :            :     }
    2729                 :          0 : }
    2730                 :            : 
    2731                 :            : 
    2732                 :            : /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
    2733                 :            :    not touched unless the block is new.  */
    2734                 :            : 
    2735                 :            : static void
    2736                 :      87735 : df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
    2737                 :            : {
    2738                 :      87735 :   unsigned int bb_index;
    2739                 :      87735 :   bitmap_iterator bi;
    2740                 :      87735 :   basic_block bb;
    2741                 :      87735 :   struct df_word_lr_problem_data *problem_data
    2742                 :      87735 :     = XNEW (struct df_word_lr_problem_data);
    2743                 :            : 
    2744                 :      87735 :   df_word_lr->problem_data = problem_data;
    2745                 :            : 
    2746                 :      87735 :   df_grow_bb_info (df_word_lr);
    2747                 :            : 
    2748                 :            :   /* Create the mapping from regnos to slots. This does not change
    2749                 :            :      unless the problem is destroyed and recreated.  In particular, if
    2750                 :            :      we end up deleting the only insn that used a subreg, we do not
    2751                 :            :      want to redo the mapping because this would invalidate everything
    2752                 :            :      else.  */
    2753                 :            : 
    2754                 :      87735 :   bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
    2755                 :            : 
    2756                 :    2235070 :   FOR_EACH_BB_FN (bb, cfun)
    2757                 :    2147330 :     bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
    2758                 :            : 
    2759                 :      87735 :   bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
    2760                 :      87735 :   bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
    2761                 :            : 
    2762                 :    2410540 :   EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
    2763                 :            :     {
    2764                 :    2322800 :       class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
    2765                 :            :       
    2766                 :            :       /* When bitmaps are already initialized, just clear them.  */
    2767                 :    2322800 :       if (bb_info->use.obstack)
    2768                 :            :         {
    2769                 :          0 :           bitmap_clear (&bb_info->def);
    2770                 :          0 :           bitmap_clear (&bb_info->use);
    2771                 :            :         }
    2772                 :            :       else
    2773                 :            :         {
    2774                 :    2322800 :           bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
    2775                 :    2322800 :           bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
    2776                 :    2322800 :           bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
    2777                 :    2322800 :           bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
    2778                 :            :         }
    2779                 :            :     }
    2780                 :            : 
    2781                 :      87735 :   df_word_lr->optional_p = true;
    2782                 :      87735 : }
    2783                 :            : 
    2784                 :            : 
    2785                 :            : /* Reset the global solution for recalculation.  */
    2786                 :            : 
    2787                 :            : static void
    2788                 :          0 : df_word_lr_reset (bitmap all_blocks)
    2789                 :            : {
    2790                 :          0 :   unsigned int bb_index;
    2791                 :          0 :   bitmap_iterator bi;
    2792                 :            : 
    2793                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    2794                 :            :     {
    2795                 :          0 :       class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
    2796                 :          0 :       gcc_assert (bb_info);
    2797                 :          0 :       bitmap_clear (&bb_info->in);
    2798                 :          0 :       bitmap_clear (&bb_info->out);
    2799                 :            :     }
    2800                 :          0 : }
    2801                 :            : 
    2802                 :            : /* Examine REF, and if it is for a reg we're interested in, set or
    2803                 :            :    clear the bits corresponding to its subwords from the bitmap
    2804                 :            :    according to IS_SET.  LIVE is the bitmap we should update.  We do
    2805                 :            :    not track hard regs or pseudos of any size other than 2 *
    2806                 :            :    UNITS_PER_WORD.
    2807                 :            :    We return true if we changed the bitmap, or if we encountered a register
    2808                 :            :    we're not tracking.  */
    2809                 :            : 
    2810                 :            : bool
    2811                 :  274718000 : df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
    2812                 :            : {
    2813                 :  274718000 :   rtx orig_reg = DF_REF_REG (ref);
    2814                 :  274718000 :   rtx reg = orig_reg;
    2815                 :  274718000 :   machine_mode reg_mode;
    2816                 :  274718000 :   unsigned regno;
    2817                 :            :   /* Left at -1 for whole accesses.  */
    2818                 :  274718000 :   int which_subword = -1;
    2819                 :  274718000 :   bool changed = false;
    2820                 :            : 
    2821                 :  274718000 :   if (GET_CODE (reg) == SUBREG)
    2822                 :    1813100 :     reg = SUBREG_REG (orig_reg);
    2823                 :  274718000 :   regno = REGNO (reg);
    2824                 :  274718000 :   reg_mode = GET_MODE (reg);
    2825                 :  274718000 :   if (regno < FIRST_PSEUDO_REGISTER
    2826                 :  316055000 :       || maybe_ne (GET_MODE_SIZE (reg_mode), 2 * UNITS_PER_WORD))
    2827                 :  269875000 :     return true;
    2828                 :            : 
    2829                 :    4842300 :   if (GET_CODE (orig_reg) == SUBREG
    2830                 :    4842300 :       && read_modify_subreg_p (orig_reg))
    2831                 :            :     {
    2832                 :    1056890 :       gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
    2833                 :    1056890 :       if (subreg_lowpart_p (orig_reg))
    2834                 :            :         which_subword = 0;
    2835                 :            :       else
    2836                 :     545996 :         which_subword = 1;
    2837                 :            :     }
    2838                 :    4842300 :   if (is_set)
    2839                 :            :     {
    2840                 :    3113900 :       if (which_subword != 1)
    2841                 :    2800960 :         changed |= bitmap_set_bit (live, regno * 2);
    2842                 :    3113900 :       if (which_subword != 0)
    2843                 :    2809580 :         changed |= bitmap_set_bit (live, regno * 2 + 1);
    2844                 :            :     }
    2845                 :            :   else
    2846                 :            :     {
    2847                 :    1728410 :       if (which_subword != 1)
    2848                 :    1495350 :         changed |= bitmap_clear_bit (live, regno * 2);
    2849                 :    1728410 :       if (which_subword != 0)
    2850                 :    1521830 :         changed |= bitmap_clear_bit (live, regno * 2 + 1);
    2851                 :            :     }
    2852                 :            :   return changed;
    2853                 :            : }
    2854                 :            : 
    2855                 :            : /* Compute local live register info for basic block BB.  */
    2856                 :            : 
    2857                 :            : static void
    2858                 :    2235070 : df_word_lr_bb_local_compute (unsigned int bb_index)
    2859                 :            : {
    2860                 :    2235070 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    2861                 :    2235070 :   class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
    2862                 :    2235070 :   rtx_insn *insn;
    2863                 :    2235070 :   df_ref def, use;
    2864                 :            : 
    2865                 :            :   /* Ensure that artificial refs don't contain references to pseudos.  */
    2866                 :    5995520 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    2867                 :    1525390 :     gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
    2868                 :            : 
    2869                 :   10824400 :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
    2870                 :    8589320 :     gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
    2871                 :            : 
    2872                 :   48776300 :   FOR_BB_INSNS_REVERSE (bb, insn)
    2873                 :            :     {
    2874                 :   23270600 :       if (!NONDEBUG_INSN_P (insn))
    2875                 :    9945520 :         continue;
    2876                 :            : 
    2877                 :   13325100 :       df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    2878                 :   93549000 :       FOR_EACH_INSN_INFO_DEF (def, insn_info)
    2879                 :            :         /* If the def is to only part of the reg, it does
    2880                 :            :            not kill the other defs that reach here.  */
    2881                 :   80223900 :         if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
    2882                 :            :           {
    2883                 :   80223900 :             df_word_lr_mark_ref (def, true, &bb_info->def);
    2884                 :   80223900 :             df_word_lr_mark_ref (def, false, &bb_info->use);
    2885                 :            :           }
    2886                 :   30349900 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
    2887                 :   17024800 :         df_word_lr_mark_ref (use, true, &bb_info->use);
    2888                 :            :     }
    2889                 :    2235070 : }
    2890                 :            : 
    2891                 :            : 
    2892                 :            : /* Compute local live register info for each basic block within BLOCKS.  */
    2893                 :            : 
    2894                 :            : static void
    2895                 :      87735 : df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
    2896                 :            : {
    2897                 :      87735 :   unsigned int bb_index;
    2898                 :      87735 :   bitmap_iterator bi;
    2899                 :            : 
    2900                 :    2410540 :   EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
    2901                 :            :     {
    2902                 :    2322800 :       if (bb_index == EXIT_BLOCK)
    2903                 :            :         {
    2904                 :      87735 :           unsigned regno;
    2905                 :      87735 :           bitmap_iterator bi;
    2906                 :      87735 :           EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
    2907                 :            :                                     regno, bi)
    2908                 :          0 :             gcc_unreachable ();
    2909                 :            :         }
    2910                 :            :       else
    2911                 :    2235070 :         df_word_lr_bb_local_compute (bb_index);
    2912                 :            :     }
    2913                 :            : 
    2914                 :      87735 :   bitmap_clear (df_word_lr->out_of_date_transfer_functions);
    2915                 :      87735 : }
    2916                 :            : 
    2917                 :            : 
    2918                 :            : /* Initialize the solution vectors.  */
    2919                 :            : 
    2920                 :            : static void
    2921                 :      87735 : df_word_lr_init (bitmap all_blocks)
    2922                 :            : {
    2923                 :      87735 :   unsigned int bb_index;
    2924                 :      87735 :   bitmap_iterator bi;
    2925                 :            : 
    2926                 :    2410540 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    2927                 :            :     {
    2928                 :    2322800 :       class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
    2929                 :    2322800 :       bitmap_copy (&bb_info->in, &bb_info->use);
    2930                 :    2322800 :       bitmap_clear (&bb_info->out);
    2931                 :            :     }
    2932                 :      87735 : }
    2933                 :            : 
    2934                 :            : 
    2935                 :            : /* Confluence function that ignores fake edges.  */
    2936                 :            : 
    2937                 :            : static bool
    2938                 :    3445140 : df_word_lr_confluence_n (edge e)
    2939                 :            : {
    2940                 :    3445140 :   bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
    2941                 :    3445140 :   bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
    2942                 :            : 
    2943                 :    3445140 :   return bitmap_ior_into (op1, op2);
    2944                 :            : }
    2945                 :            : 
    2946                 :            : 
    2947                 :            : /* Transfer function.  */
    2948                 :            : 
    2949                 :            : static bool
    2950                 :    2449260 : df_word_lr_transfer_function (int bb_index)
    2951                 :            : {
    2952                 :    2449260 :   class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
    2953                 :    2449260 :   bitmap in = &bb_info->in;
    2954                 :    2449260 :   bitmap out = &bb_info->out;
    2955                 :    2449260 :   bitmap use = &bb_info->use;
    2956                 :    2449260 :   bitmap def = &bb_info->def;
    2957                 :            : 
    2958                 :    2449260 :   return bitmap_ior_and_compl (in, use, out, def);
    2959                 :            : }
    2960                 :            : 
    2961                 :            : 
    2962                 :            : /* Free all storage associated with the problem.  */
    2963                 :            : 
    2964                 :            : static void
    2965                 :      87735 : df_word_lr_free (void)
    2966                 :            : {
    2967                 :      87735 :   struct df_word_lr_problem_data *problem_data
    2968                 :      87735 :     = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
    2969                 :            : 
    2970                 :      87735 :   if (df_word_lr->block_info)
    2971                 :            :     {
    2972                 :      87735 :       df_word_lr->block_info_size = 0;
    2973                 :      87735 :       free (df_word_lr->block_info);
    2974                 :      87735 :       df_word_lr->block_info = NULL;
    2975                 :            :     }
    2976                 :            : 
    2977                 :      87735 :   BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
    2978                 :      87735 :   bitmap_obstack_release (&problem_data->word_lr_bitmaps);
    2979                 :      87735 :   free (problem_data);
    2980                 :      87735 :   free (df_word_lr);
    2981                 :      87735 : }
    2982                 :            : 
    2983                 :            : 
    2984                 :            : /* Debugging info at top of bb.  */
    2985                 :            : 
    2986                 :            : static void
    2987                 :          0 : df_word_lr_top_dump (basic_block bb, FILE *file)
    2988                 :            : {
    2989                 :          0 :   class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
    2990                 :          0 :   if (!bb_info)
    2991                 :            :     return;
    2992                 :            : 
    2993                 :          0 :   fprintf (file, ";; blr  in  \t");
    2994                 :          0 :   df_print_word_regset (file, &bb_info->in);
    2995                 :          0 :   fprintf (file, ";; blr  use \t");
    2996                 :          0 :   df_print_word_regset (file, &bb_info->use);
    2997                 :          0 :   fprintf (file, ";; blr  def \t");
    2998                 :          0 :   df_print_word_regset (file, &bb_info->def);
    2999                 :            : }
    3000                 :            : 
    3001                 :            : 
    3002                 :            : /* Debugging info at bottom of bb.  */
    3003                 :            : 
    3004                 :            : static void
    3005                 :          0 : df_word_lr_bottom_dump (basic_block bb, FILE *file)
    3006                 :            : {
    3007                 :          0 :   class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
    3008                 :          0 :   if (!bb_info)
    3009                 :            :     return;
    3010                 :            : 
    3011                 :          0 :   fprintf (file, ";; blr  out \t");
    3012                 :          0 :   df_print_word_regset (file, &bb_info->out);
    3013                 :            : }
    3014                 :            : 
    3015                 :            : 
    3016                 :            : /* All of the information associated with every instance of the problem.  */
    3017                 :            : 
    3018                 :            : static const struct df_problem problem_WORD_LR =
    3019                 :            : {
    3020                 :            :   DF_WORD_LR,                      /* Problem id.  */
    3021                 :            :   DF_BACKWARD,                     /* Direction.  */
    3022                 :            :   df_word_lr_alloc,                /* Allocate the problem specific data.  */
    3023                 :            :   df_word_lr_reset,                /* Reset global information.  */
    3024                 :            :   df_word_lr_free_bb_info,         /* Free basic block info.  */
    3025                 :            :   df_word_lr_local_compute,        /* Local compute function.  */
    3026                 :            :   df_word_lr_init,                 /* Init the solution specific data.  */
    3027                 :            :   df_worklist_dataflow,            /* Worklist solver.  */
    3028                 :            :   NULL,                            /* Confluence operator 0.  */
    3029                 :            :   df_word_lr_confluence_n,         /* Confluence operator n.  */
    3030                 :            :   df_word_lr_transfer_function,    /* Transfer function.  */
    3031                 :            :   NULL,                            /* Finalize function.  */
    3032                 :            :   df_word_lr_free,                 /* Free all of the problem information.  */
    3033                 :            :   df_word_lr_free,                 /* Remove this problem from the stack of dataflow problems.  */
    3034                 :            :   NULL,                            /* Debugging.  */
    3035                 :            :   df_word_lr_top_dump,             /* Debugging start block.  */
    3036                 :            :   df_word_lr_bottom_dump,          /* Debugging end block.  */
    3037                 :            :   NULL,                            /* Debugging start insn.  */
    3038                 :            :   NULL,                            /* Debugging end insn.  */
    3039                 :            :   NULL,                            /* Incremental solution verify start.  */
    3040                 :            :   NULL,                            /* Incremental solution verify end.  */
    3041                 :            :   NULL,                            /* Dependent problem.  */
    3042                 :            :   sizeof (class df_word_lr_bb_info),/* Size of entry of block_info array.  */
    3043                 :            :   TV_DF_WORD_LR,                   /* Timing variable.  */
    3044                 :            :   false                            /* Reset blocks on dropping out of blocks_to_analyze.  */
    3045                 :            : };
    3046                 :            : 
    3047                 :            : 
    3048                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    3049                 :            :    of DF.  The returned structure is what is used to get at the
    3050                 :            :    solution.  */
    3051                 :            : 
    3052                 :            : void
    3053                 :      87735 : df_word_lr_add_problem (void)
    3054                 :            : {
    3055                 :      87735 :   df_add_problem (&problem_WORD_LR);
    3056                 :            :   /* These will be initialized when df_scan_blocks processes each
    3057                 :            :      block.  */
    3058                 :      87735 :   df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
    3059                 :      87735 : }
    3060                 :            : 
    3061                 :            : 
    3062                 :            : /* Simulate the effects of the defs of INSN on LIVE.  Return true if we changed
    3063                 :            :    any bits, which is used by the caller to determine whether a set is
    3064                 :            :    necessary.  We also return true if there are other reasons not to delete
    3065                 :            :    an insn.  */
    3066                 :            : 
    3067                 :            : bool
    3068                 :   13325100 : df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
    3069                 :            : {
    3070                 :   13325100 :   bool changed = false;
    3071                 :   13325100 :   df_ref def;
    3072                 :            : 
    3073                 :   93549000 :   FOR_EACH_INSN_DEF (def, insn)
    3074                 :   80223900 :     if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
    3075                 :            :       changed = true;
    3076                 :            :     else
    3077                 :   80223900 :       changed |= df_word_lr_mark_ref (def, false, live);
    3078                 :   13325100 :   return changed;
    3079                 :            : }
    3080                 :            : 
    3081                 :            : 
    3082                 :            : /* Simulate the effects of the uses of INSN on LIVE.  */
    3083                 :            : 
    3084                 :            : void
    3085                 :   13317900 : df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
    3086                 :            : {
    3087                 :   13317900 :   df_ref use;
    3088                 :            : 
    3089                 :   30339100 :   FOR_EACH_INSN_USE (use, insn)
    3090                 :   17021200 :     df_word_lr_mark_ref (use, true, live);
    3091                 :   13317900 : }
    3092                 :            : 
    3093                 :            : /*----------------------------------------------------------------------------
    3094                 :            :    This problem computes REG_DEAD and REG_UNUSED notes.
    3095                 :            :    ----------------------------------------------------------------------------*/
    3096                 :            : 
    3097                 :            : static void
    3098                 :   11322300 : df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
    3099                 :            : {
    3100                 :   11322300 :   df_note->optional_p = true;
    3101                 :   11322300 : }
    3102                 :            : 
    3103                 :            : /* This is only used if REG_DEAD_DEBUGGING is in effect.  */
    3104                 :            : static void
    3105                 :          0 : df_print_note (const char *prefix, rtx_insn *insn, rtx note)
    3106                 :            : {
    3107                 :          0 :   if (dump_file)
    3108                 :            :     {
    3109                 :          0 :       fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
    3110                 :          0 :       print_rtl (dump_file, note);
    3111                 :          0 :       fprintf (dump_file, "\n");
    3112                 :            :     }
    3113                 :          0 : }
    3114                 :            : 
    3115                 :            : 
    3116                 :            : /* After reg-stack, the x86 floating point stack regs are difficult to
    3117                 :            :    analyze because of all of the pushes, pops and rotations.  Thus, we
    3118                 :            :    just leave the notes alone. */
    3119                 :            : 
    3120                 :            : #ifdef STACK_REGS
    3121                 :            : static inline bool
    3122                 :  912973000 : df_ignore_stack_reg (int regno)
    3123                 :            : {
    3124                 :  912973000 :   return regstack_completed
    3125                 :  418566000 :     && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
    3126                 :            : }
    3127                 :            : #else
    3128                 :            : static inline bool
    3129                 :            : df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
    3130                 :            : {
    3131                 :            :   return false;
    3132                 :            : }
    3133                 :            : #endif
    3134                 :            : 
    3135                 :            : 
    3136                 :            : /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN.  */
    3137                 :            : 
    3138                 :            : static void
    3139                 : 1217770000 : df_remove_dead_and_unused_notes (rtx_insn *insn)
    3140                 :            : {
    3141                 : 1217770000 :   rtx *pprev = &REG_NOTES (insn);
    3142                 : 1217770000 :   rtx link = *pprev;
    3143                 :            : 
    3144                 : 1899980000 :   while (link)
    3145                 :            :     {
    3146                 :  682205000 :       switch (REG_NOTE_KIND (link))
    3147                 :            :         {
    3148                 :  330907000 :         case REG_DEAD:
    3149                 :            :           /* After reg-stack, we need to ignore any unused notes
    3150                 :            :              for the stack registers.  */
    3151                 :  330907000 :           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
    3152                 :            :             {
    3153                 :          0 :               pprev = &XEXP (link, 1);
    3154                 :          0 :               link = *pprev;
    3155                 :            :             }
    3156                 :            :           else
    3157                 :            :             {
    3158                 :  330907000 :               rtx next = XEXP (link, 1);
    3159                 :  330907000 :               if (REG_DEAD_DEBUGGING)
    3160                 :            :                 df_print_note ("deleting: ", insn, link);
    3161                 :  330907000 :               free_EXPR_LIST_node (link);
    3162                 :  330907000 :               *pprev = link = next;
    3163                 :            :             }
    3164                 :            :           break;
    3165                 :            : 
    3166                 :   87658400 :         case REG_UNUSED:
    3167                 :            :           /* After reg-stack, we need to ignore any unused notes
    3168                 :            :              for the stack registers.  */
    3169                 :   87658400 :           if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
    3170                 :            :             {
    3171                 :          0 :               pprev = &XEXP (link, 1);
    3172                 :          0 :               link = *pprev;
    3173                 :            :             }
    3174                 :            :           else
    3175                 :            :             {
    3176                 :   87658400 :               rtx next = XEXP (link, 1);
    3177                 :   87658400 :               if (REG_DEAD_DEBUGGING)
    3178                 :            :                 df_print_note ("deleting: ", insn, link);
    3179                 :   87658400 :               free_EXPR_LIST_node (link);
    3180                 :   87658400 :               *pprev = link = next;
    3181                 :            :             }
    3182                 :            :           break;
    3183                 :            : 
    3184                 :  263639000 :         default:
    3185                 :  263639000 :           pprev = &XEXP (link, 1);
    3186                 :  263639000 :           link = *pprev;
    3187                 :  263639000 :           break;
    3188                 :            :         }
    3189                 :            :     }
    3190                 : 1217770000 : }
    3191                 :            : 
    3192                 :            : /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
    3193                 :            :    as the bitmap of currently live registers.  */
    3194                 :            : 
    3195                 :            : static void
    3196                 : 1217770000 : df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
    3197                 :            : {
    3198                 : 1217770000 :   rtx *pprev = &REG_NOTES (insn);
    3199                 : 1217770000 :   rtx link = *pprev;
    3200                 :            : 
    3201                 : 1973930000 :   while (link)
    3202                 :            :     {
    3203                 :  756152000 :       switch (REG_NOTE_KIND (link))
    3204                 :            :         {
    3205                 :   44488100 :         case REG_EQUAL:
    3206                 :   44488100 :         case REG_EQUIV:
    3207                 :   44488100 :           {
    3208                 :            :             /* Remove the notes that refer to dead registers.  As we have at most
    3209                 :            :                one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
    3210                 :            :                so we need to purge the complete EQ_USES vector when removing
    3211                 :            :                the note using df_notes_rescan.  */
    3212                 :   44488100 :             df_ref use;
    3213                 :   44488100 :             bool deleted = false;
    3214                 :            : 
    3215                 :   77544000 :             FOR_EACH_INSN_EQ_USE (use, insn)
    3216                 :   33298200 :               if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
    3217                 :    6897330 :                   && DF_REF_LOC (use)
    3218                 :    6897330 :                   && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
    3219                 :    6897330 :                   && !bitmap_bit_p (live, DF_REF_REGNO (use))
    3220                 :   33541600 :                   && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
    3221                 :            :                 {
    3222                 :            :                   deleted = true;
    3223                 :            :                   break;
    3224                 :            :                 }
    3225                 :   44488100 :             if (deleted)
    3226                 :            :               {
    3227                 :     242276 :                 rtx next;
    3228                 :     242276 :                 if (REG_DEAD_DEBUGGING)
    3229                 :            :                   df_print_note ("deleting: ", insn, link);
    3230                 :     242276 :                 next = XEXP (link, 1);
    3231                 :     242276 :                 free_EXPR_LIST_node (link);
    3232                 :     242276 :                 *pprev = link = next;
    3233                 :     242276 :                 df_notes_rescan (insn);
    3234                 :            :               }
    3235                 :            :             else
    3236                 :            :               {
    3237                 :   44245800 :                 pprev = &XEXP (link, 1);
    3238                 :   44245800 :                 link = *pprev;
    3239                 :            :               }
    3240                 :            :             break;
    3241                 :            :           }
    3242                 :            : 
    3243                 :  711664000 :         default:
    3244                 :  711664000 :           pprev = &XEXP (link, 1);
    3245                 :  711664000 :           link = *pprev;
    3246                 :  711664000 :           break;
    3247                 :            :         }
    3248                 :            :     }
    3249                 : 1217770000 : }
    3250                 :            : 
    3251                 :            : /* Set a NOTE_TYPE note for REG in INSN.  */
    3252                 :            : 
    3253                 :            : static inline void
    3254                 :  492513000 : df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
    3255                 :            : {
    3256                 :  492513000 :   gcc_checking_assert (!DEBUG_INSN_P (insn));
    3257                 :  492513000 :   add_reg_note (insn, note_type, reg);
    3258                 :  492513000 : }
    3259                 :            : 
    3260                 :            : /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
    3261                 :            :    arguments.  Return true if the register value described by MWS's
    3262                 :            :    mw_reg is known to be completely unused, and if mw_reg can therefore
    3263                 :            :    be used in a REG_UNUSED note.  */
    3264                 :            : 
    3265                 :            : static bool
    3266                 :    1946350 : df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
    3267                 :            :                           bitmap live, bitmap artificial_uses)
    3268                 :            : {
    3269                 :    1946350 :   unsigned int r;
    3270                 :            : 
    3271                 :            :   /* If MWS describes a partial reference, create REG_UNUSED notes for
    3272                 :            :      individual hard registers.  */
    3273                 :    1946350 :   if (mws->flags & DF_REF_PARTIAL)
    3274                 :            :     return false;
    3275                 :            : 
    3276                 :            :   /* Likewise if some part of the register is used.  */
    3277                 :    2328550 :   for (r = mws->start_regno; r <= mws->end_regno; r++)
    3278                 :    2149430 :     if (bitmap_bit_p (live, r)
    3279                 :    2149430 :         || bitmap_bit_p (artificial_uses, r))
    3280                 :    1767230 :       return false;
    3281                 :            : 
    3282                 :     179120 :   gcc_assert (REG_P (mws->mw_reg));
    3283                 :            :   return true;
    3284                 :            : }
    3285                 :            : 
    3286                 :            : 
    3287                 :            : /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
    3288                 :            :    based on the bits in LIVE.  Do not generate notes for registers in
    3289                 :            :    artificial uses.  DO_NOT_GEN is updated so that REG_DEAD notes are
    3290                 :            :    not generated if the reg is both read and written by the
    3291                 :            :    instruction.
    3292                 :            : */
    3293                 :            : 
    3294                 :            : static void
    3295                 :    1946350 : df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
    3296                 :            :                             bitmap live, bitmap do_not_gen,
    3297                 :            :                             bitmap artificial_uses,
    3298                 :            :                             struct dead_debug_local *debug)
    3299                 :            : {
    3300                 :    1946350 :   unsigned int r;
    3301                 :            : 
    3302                 :    1946350 :   if (REG_DEAD_DEBUGGING && dump_file)
    3303                 :            :     fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
    3304                 :            :              mws->start_regno, mws->end_regno);
    3305                 :            : 
    3306                 :    1946350 :   if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
    3307                 :            :     {
    3308                 :     179120 :       unsigned int regno = mws->start_regno;
    3309                 :     179120 :       df_set_note (REG_UNUSED, insn, mws->mw_reg);
    3310                 :     179120 :       dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
    3311                 :            : 
    3312                 :     179120 :       if (REG_DEAD_DEBUGGING)
    3313                 :            :         df_print_note ("adding 1: ", insn, REG_NOTES (insn));
    3314                 :            : 
    3315                 :     179120 :       bitmap_set_bit (do_not_gen, regno);
    3316                 :            :       /* Only do this if the value is totally dead.  */
    3317                 :            :     }
    3318                 :            :   else
    3319                 :    5301680 :     for (r = mws->start_regno; r <= mws->end_regno; r++)
    3320                 :            :       {
    3321                 :    3534450 :         if (!bitmap_bit_p (live, r)
    3322                 :    3534450 :             && !bitmap_bit_p (artificial_uses, r))
    3323                 :            :           {
    3324                 :      73888 :             df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
    3325                 :      73888 :             dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
    3326                 :      73888 :             if (REG_DEAD_DEBUGGING)
    3327                 :            :               df_print_note ("adding 2: ", insn, REG_NOTES (insn));
    3328                 :            :           }
    3329                 :    3534450 :         bitmap_set_bit (do_not_gen, r);
    3330                 :            :       }
    3331                 :    1946350 : }
    3332                 :            : 
    3333                 :            : 
    3334                 :            : /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
    3335                 :            :    arguments.  Return true if the register value described by MWS's
    3336                 :            :    mw_reg is known to be completely dead, and if mw_reg can therefore
    3337                 :            :    be used in a REG_DEAD note.  */
    3338                 :            : 
    3339                 :            : static bool
    3340                 :    1581600 : df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
    3341                 :            :                         bitmap live, bitmap artificial_uses,
    3342                 :            :                         bitmap do_not_gen)
    3343                 :            : {
    3344                 :    1581600 :   unsigned int r;
    3345                 :            : 
    3346                 :            :   /* If MWS describes a partial reference, create REG_DEAD notes for
    3347                 :            :      individual hard registers.  */
    3348                 :    1581600 :   if (mws->flags & DF_REF_PARTIAL)
    3349                 :            :     return false;
    3350                 :            : 
    3351                 :            :   /* Likewise if some part of the register is not dead.  */
    3352                 :    3463120 :   for (r = mws->start_regno; r <= mws->end_regno; r++)
    3353                 :    2522990 :     if (bitmap_bit_p (live, r)
    3354                 :    2019700 :         || bitmap_bit_p (artificial_uses, r)
    3355                 :    4542690 :         || bitmap_bit_p (do_not_gen, r))
    3356                 :     640505 :       return false;
    3357                 :            : 
    3358                 :     940125 :   gcc_assert (REG_P (mws->mw_reg));
    3359                 :            :   return true;
    3360                 :            : }
    3361                 :            : 
    3362                 :            : /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
    3363                 :            :    on the bits in LIVE.  DO_NOT_GEN is used to keep REG_DEAD notes
    3364                 :            :    from being set if the instruction both reads and writes the
    3365                 :            :    register.  */
    3366                 :            : 
    3367                 :            : static void
    3368                 :    1581600 : df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
    3369                 :            :                           bitmap live, bitmap do_not_gen,
    3370                 :            :                           bitmap artificial_uses, bool *added_notes_p)
    3371                 :            : {
    3372                 :    1581600 :   unsigned int r;
    3373                 :    1581600 :   bool is_debug = *added_notes_p;
    3374                 :            : 
    3375                 :    1581600 :   *added_notes_p = false;
    3376                 :            : 
    3377                 :    1581600 :   if (REG_DEAD_DEBUGGING && dump_file)
    3378                 :            :     {
    3379                 :            :       fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n  do_not_gen =",
    3380                 :            :                mws->start_regno, mws->end_regno);
    3381                 :            :       df_print_regset (dump_file, do_not_gen);
    3382                 :            :       fprintf (dump_file, "  live =");
    3383                 :            :       df_print_regset (dump_file, live);
    3384                 :            :       fprintf (dump_file, "  artificial uses =");
    3385                 :            :       df_print_regset (dump_file, artificial_uses);
    3386                 :            :     }
    3387                 :            : 
    3388                 :    1581600 :   if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
    3389                 :            :     {
    3390                 :     940125 :       if (is_debug)
    3391                 :            :         {
    3392                 :        292 :           *added_notes_p = true;
    3393                 :        292 :           return;
    3394                 :            :         }
    3395                 :            :       /* Add a dead note for the entire multi word register.  */
    3396                 :     939833 :       df_set_note (REG_DEAD, insn, mws->mw_reg);
    3397                 :     939833 :       if (REG_DEAD_DEBUGGING)
    3398                 :            :         df_print_note ("adding 1: ", insn, REG_NOTES (insn));
    3399                 :            :     }
    3400                 :            :   else
    3401                 :            :     {
    3402                 :    1922740 :       for (r = mws->start_regno; r <= mws->end_regno; r++)
    3403                 :    1282500 :         if (!bitmap_bit_p (live, r)
    3404                 :     275688 :             && !bitmap_bit_p (artificial_uses, r)
    3405                 :    1558190 :             && !bitmap_bit_p (do_not_gen, r))
    3406                 :            :           {
    3407                 :      94209 :             if (is_debug)
    3408                 :            :               {
    3409                 :       1234 :                 *added_notes_p = true;
    3410                 :       1234 :                 return;
    3411                 :            :               }
    3412                 :      92975 :             df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
    3413                 :      92975 :             if (REG_DEAD_DEBUGGING)
    3414                 :            :               df_print_note ("adding 2: ", insn, REG_NOTES (insn));
    3415                 :            :           }
    3416                 :            :     }
    3417                 :            :   return;
    3418                 :            : }
    3419                 :            : 
    3420                 :            : 
    3421                 :            : /* Create a REG_UNUSED note if necessary for DEF in INSN updating
    3422                 :            :    LIVE.  Do not generate notes for registers in ARTIFICIAL_USES.  */
    3423                 :            : 
    3424                 :            : static void
    3425                 :  616813000 : df_create_unused_note (rtx_insn *insn, df_ref def,
    3426                 :            :                        bitmap live, bitmap artificial_uses,
    3427                 :            :                        struct dead_debug_local *debug)
    3428                 :            : {
    3429                 :  616813000 :   unsigned int dregno = DF_REF_REGNO (def);
    3430                 :            : 
    3431                 :  616813000 :   if (REG_DEAD_DEBUGGING && dump_file)
    3432                 :            :     {
    3433                 :            :       fprintf (dump_file, "  regular looking at def ");
    3434                 :            :       df_ref_debug (def, dump_file);
    3435                 :            :     }
    3436                 :            : 
    3437                 :  616813000 :   if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
    3438                 :  612920000 :         || bitmap_bit_p (live, dregno)
    3439                 :  106482000 :         || bitmap_bit_p (artificial_uses, dregno)
    3440                 :  106465000 :         || df_ignore_stack_reg (dregno)))
    3441                 :            :     {
    3442                 :  106465000 :       rtx reg = (DF_REF_LOC (def))
    3443                 :  106465000 :                 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
    3444                 :  106465000 :       df_set_note (REG_UNUSED, insn, reg);
    3445                 :  106465000 :       dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
    3446                 :  106465000 :       if (REG_DEAD_DEBUGGING)
    3447                 :            :         df_print_note ("adding 3: ", insn, REG_NOTES (insn));
    3448                 :            :     }
    3449                 :            : 
    3450                 :  616813000 :   return;
    3451                 :            : }
    3452                 :            : 
    3453                 :            : 
    3454                 :            : /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
    3455                 :            :    info: lifetime, bb, and number of defs and uses for basic block
    3456                 :            :    BB.  The three bitvectors are scratch regs used here.  */
    3457                 :            : 
    3458                 :            : static void
    3459                 :  148137000 : df_note_bb_compute (unsigned int bb_index,
    3460                 :            :                     bitmap live, bitmap do_not_gen, bitmap artificial_uses)
    3461                 :            : {
    3462                 :  148137000 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    3463                 :  148137000 :   rtx_insn *insn;
    3464                 :  148137000 :   df_ref def, use;
    3465                 :  148137000 :   struct dead_debug_local debug;
    3466                 :            : 
    3467                 :  148137000 :   dead_debug_local_init (&debug, NULL, NULL);
    3468                 :            : 
    3469                 :  148137000 :   bitmap_copy (live, df_get_live_out (bb));
    3470                 :  148137000 :   bitmap_clear (artificial_uses);
    3471                 :            : 
    3472                 :  148137000 :   if (REG_DEAD_DEBUGGING && dump_file)
    3473                 :            :     {
    3474                 :            :       fprintf (dump_file, "live at bottom ");
    3475                 :            :       df_print_regset (dump_file, live);
    3476                 :            :     }
    3477                 :            : 
    3478                 :            :   /* Process the artificial defs and uses at the bottom of the block
    3479                 :            :      to begin processing.  */
    3480                 :  498782000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    3481                 :            :     {
    3482                 :  202507000 :       if (REG_DEAD_DEBUGGING && dump_file)
    3483                 :            :         fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
    3484                 :            : 
    3485                 :  202507000 :       if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
    3486                 :  197716000 :         bitmap_clear_bit (live, DF_REF_REGNO (def));
    3487                 :            :     }
    3488                 :            : 
    3489                 :  698223000 :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
    3490                 :  401949000 :     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
    3491                 :            :       {
    3492                 :  401949000 :         unsigned int regno = DF_REF_REGNO (use);
    3493                 :  401949000 :         bitmap_set_bit (live, regno);
    3494                 :            : 
    3495                 :            :         /* Notes are not generated for any of the artificial registers
    3496                 :            :            at the bottom of the block.  */
    3497                 :  401949000 :         bitmap_set_bit (artificial_uses, regno);
    3498                 :            :       }
    3499                 :            : 
    3500                 :  148137000 :   if (REG_DEAD_DEBUGGING && dump_file)
    3501                 :            :     {
    3502                 :            :       fprintf (dump_file, "live before artificials out ");
    3503                 :            :       df_print_regset (dump_file, live);
    3504                 :            :     }
    3505                 :            : 
    3506                 : 3063200000 :   FOR_BB_INSNS_REVERSE (bb, insn)
    3507                 :            :     {
    3508                 : 1457530000 :       if (!INSN_P (insn))
    3509                 :  239757000 :         continue;
    3510                 :            : 
    3511                 : 1217770000 :       df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    3512                 : 1217770000 :       df_mw_hardreg *mw;
    3513                 : 1217770000 :       int debug_insn;
    3514                 :            : 
    3515                 : 1217770000 :       debug_insn = DEBUG_INSN_P (insn);
    3516                 :            : 
    3517                 : 1217770000 :       bitmap_clear (do_not_gen);
    3518                 : 1217770000 :       df_remove_dead_and_unused_notes (insn);
    3519                 :            : 
    3520                 :            :       /* Process the defs.  */
    3521                 : 1217770000 :       if (CALL_P (insn))
    3522                 :            :         {
    3523                 :   56526300 :           if (REG_DEAD_DEBUGGING && dump_file)
    3524                 :            :             {
    3525                 :            :               fprintf (dump_file, "processing call %d\n  live =",
    3526                 :            :                        INSN_UID (insn));
    3527                 :            :               df_print_regset (dump_file, live);
    3528                 :            :             }
    3529                 :            : 
    3530                 :            :           /* We only care about real sets for calls.  Clobbers cannot
    3531                 :            :              be depended on to really die.  */
    3532                 :   58694800 :           FOR_EACH_INSN_INFO_MW (mw, insn_info)
    3533                 :    2168540 :             if ((DF_MWS_REG_DEF_P (mw))
    3534                 :    3701130 :                 && !df_ignore_stack_reg (mw->start_regno))
    3535                 :    1532590 :               df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
    3536                 :            :                                           artificial_uses, &debug);
    3537                 :            : 
    3538                 :            :           /* All of the defs except the return value are some sort of
    3539                 :            :              clobber.  This code is for the return.  */
    3540                 : 3789890000 :           FOR_EACH_INSN_INFO_DEF (def, insn_info)
    3541                 :            :             {
    3542                 : 3733360000 :               unsigned int dregno = DF_REF_REGNO (def);
    3543                 : 3733360000 :               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
    3544                 :            :                 {
    3545                 :   25407600 :                   df_create_unused_note (insn,
    3546                 :            :                                          def, live, artificial_uses, &debug);
    3547                 :   25407600 :                   bitmap_set_bit (do_not_gen, dregno);
    3548                 :            :                 }
    3549                 :            : 
    3550                 : 3733360000 :               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
    3551                 : 3733360000 :                 bitmap_clear_bit (live, dregno);
    3552                 :            :             }
    3553                 :            :         }
    3554                 :            :       else
    3555                 :            :         {
    3556                 :            :           /* Regular insn.  */
    3557                 : 1162610000 :           FOR_EACH_INSN_INFO_MW (mw, insn_info)
    3558                 :    1359410 :             if (DF_MWS_REG_DEF_P (mw))
    3559                 :     413756 :               df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
    3560                 :            :                                           artificial_uses, &debug);
    3561                 :            : 
    3562                 : 1752650000 :           FOR_EACH_INSN_INFO_DEF (def, insn_info)
    3563                 :            :             {
    3564                 :  591405000 :               unsigned int dregno = DF_REF_REGNO (def);
    3565                 :  591405000 :               df_create_unused_note (insn,
    3566                 :            :                                      def, live, artificial_uses, &debug);
    3567                 :            : 
    3568                 :  591405000 :               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
    3569                 :  496996000 :                 bitmap_set_bit (do_not_gen, dregno);
    3570                 :            : 
    3571                 :  591405000 :               if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
    3572                 :  588855000 :                 bitmap_clear_bit (live, dregno);
    3573                 :            :             }
    3574                 :            :         }
    3575                 :            : 
    3576                 :            :       /* Process the uses.  */
    3577                 : 1221300000 :       FOR_EACH_INSN_INFO_MW (mw, insn_info)
    3578                 :    3527950 :         if (DF_MWS_REG_USE_P (mw)
    3579                 :    5109550 :             && !df_ignore_stack_reg (mw->start_regno))
    3580                 :            :           {
    3581                 :    1581600 :             bool really_add_notes = debug_insn != 0;
    3582                 :            : 
    3583                 :    1581600 :             df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
    3584                 :            :                                       artificial_uses,
    3585                 :            :                                       &really_add_notes);
    3586                 :            : 
    3587                 :    1581600 :             if (really_add_notes)
    3588                 :       1526 :               debug_insn = -1;
    3589                 :            :           }
    3590                 :            : 
    3591                 : 2227720000 :       FOR_EACH_INSN_INFO_USE (use, insn_info)
    3592                 :            :         {
    3593                 : 1009940000 :           unsigned int uregno = DF_REF_REGNO (use);
    3594                 :            : 
    3595                 : 1009940000 :           if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
    3596                 :            :             {
    3597                 :            :               fprintf (dump_file, "  regular looking at use ");
    3598                 :            :               df_ref_debug (use, dump_file);
    3599                 :            :             }
    3600                 :            : 
    3601                 : 1009940000 :           if (!bitmap_bit_p (live, uregno))
    3602                 :            :             {
    3603                 :  496035000 :               if (debug_insn)
    3604                 :            :                 {
    3605                 :      67479 :                   if (debug_insn > 0)
    3606                 :            :                     {
    3607                 :            :                       /* We won't add REG_UNUSED or REG_DEAD notes for
    3608                 :            :                          these, so we don't have to mess with them in
    3609                 :            :                          debug insns either.  */
    3610                 :      65955 :                       if (!bitmap_bit_p (artificial_uses, uregno)
    3611                 :      65955 :                           && !df_ignore_stack_reg (uregno))
    3612                 :      65955 :                         dead_debug_add (&debug, use, uregno);
    3613                 :      65955 :                       continue;
    3614                 :            :                     }
    3615                 :            :                   break;
    3616                 :            :                 }
    3617                 :            :               else
    3618                 :  495968000 :                 dead_debug_insert_temp (&debug, uregno, insn,
    3619                 :            :                                         DEBUG_TEMP_BEFORE_WITH_REG);
    3620                 :            : 
    3621                 :  495968000 :               if ( (!(DF_REF_FLAGS (use)
    3622                 :            :                       & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
    3623                 :  493803000 :                    && (!bitmap_bit_p (do_not_gen, uregno))
    3624                 :  385131000 :                    && (!bitmap_bit_p (artificial_uses, uregno))
    3625                 :  880730000 :                    && (!df_ignore_stack_reg (uregno)))
    3626                 :            :                 {
    3627                 :  384762000 :                   rtx reg = (DF_REF_LOC (use))
    3628                 :  384762000 :                             ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
    3629                 :  384762000 :                   df_set_note (REG_DEAD, insn, reg);
    3630                 :            : 
    3631                 :  384762000 :                   if (REG_DEAD_DEBUGGING)
    3632                 :            :                     df_print_note ("adding 4: ", insn, REG_NOTES (insn));
    3633                 :            :                 }
    3634                 :            :               /* This register is now live.  */
    3635                 :  495968000 :               bitmap_set_bit (live, uregno);
    3636                 :            :             }
    3637                 :            :         }
    3638                 :            : 
    3639                 : 1217770000 :       df_remove_dead_eq_notes (insn, live);
    3640                 :            : 
    3641                 : 1217770000 :       if (debug_insn == -1)
    3642                 :            :         {
    3643                 :            :           /* ??? We could probably do better here, replacing dead
    3644                 :            :              registers with their definitions.  */
    3645                 :       1524 :           INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
    3646                 :       1524 :           df_insn_rescan_debug_internal (insn);
    3647                 :            :         }
    3648                 :            :     }
    3649                 :            : 
    3650                 :  148137000 :   dead_debug_local_finish (&debug, NULL);
    3651                 :  148137000 : }
    3652                 :            : 
    3653                 :            : 
    3654                 :            : /* Compute register info: lifetime, bb, and number of defs and uses.  */
    3655                 :            : static void
    3656                 :   11322300 : df_note_compute (bitmap all_blocks)
    3657                 :            : {
    3658                 :   11322300 :   unsigned int bb_index;
    3659                 :   11322300 :   bitmap_iterator bi;
    3660                 :   11322300 :   bitmap_head live, do_not_gen, artificial_uses;
    3661                 :            : 
    3662                 :   11322300 :   bitmap_initialize (&live, &df_bitmap_obstack);
    3663                 :   11322300 :   bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
    3664                 :   11322300 :   bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
    3665                 :            : 
    3666                 :  159460000 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    3667                 :            :   {
    3668                 :            :     /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
    3669                 :            :        pseudos in debug insns because we don't always (re)visit blocks
    3670                 :            :        with death points after visiting dead uses.  Even changing this
    3671                 :            :        loop to postorder would still leave room for visiting a death
    3672                 :            :        point before visiting a subsequent debug use.  */
    3673                 :  148137000 :     df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
    3674                 :            :   }
    3675                 :            : 
    3676                 :   11322300 :   bitmap_clear (&live);
    3677                 :   11322300 :   bitmap_clear (&do_not_gen);
    3678                 :   11322300 :   bitmap_clear (&artificial_uses);
    3679                 :   11322300 : }
    3680                 :            : 
    3681                 :            : 
    3682                 :            : /* Free all storage associated with the problem.  */
    3683                 :            : 
    3684                 :            : static void
    3685                 :    8633340 : df_note_free (void)
    3686                 :            : {
    3687                 :    8633340 :   free (df_note);
    3688                 :    8633340 : }
    3689                 :            : 
    3690                 :            : 
    3691                 :            : /* All of the information associated every instance of the problem.  */
    3692                 :            : 
    3693                 :            : static const struct df_problem problem_NOTE =
    3694                 :            : {
    3695                 :            :   DF_NOTE,                    /* Problem id.  */
    3696                 :            :   DF_NONE,                    /* Direction.  */
    3697                 :            :   df_note_alloc,              /* Allocate the problem specific data.  */
    3698                 :            :   NULL,                       /* Reset global information.  */
    3699                 :            :   NULL,                       /* Free basic block info.  */
    3700                 :            :   df_note_compute,            /* Local compute function.  */
    3701                 :            :   NULL,                       /* Init the solution specific data.  */
    3702                 :            :   NULL,                       /* Iterative solver.  */
    3703                 :            :   NULL,                       /* Confluence operator 0.  */
    3704                 :            :   NULL,                       /* Confluence operator n.  */
    3705                 :            :   NULL,                       /* Transfer function.  */
    3706                 :            :   NULL,                       /* Finalize function.  */
    3707                 :            :   df_note_free,               /* Free all of the problem information.  */
    3708                 :            :   df_note_free,               /* Remove this problem from the stack of dataflow problems.  */
    3709                 :            :   NULL,                       /* Debugging.  */
    3710                 :            :   NULL,                       /* Debugging start block.  */
    3711                 :            :   NULL,                       /* Debugging end block.  */
    3712                 :            :   NULL,                       /* Debugging start insn.  */
    3713                 :            :   NULL,                       /* Debugging end insn.  */
    3714                 :            :   NULL,                       /* Incremental solution verify start.  */
    3715                 :            :   NULL,                       /* Incremental solution verify end.  */
    3716                 :            :   &problem_LR,                /* Dependent problem.  */
    3717                 :            :   sizeof (struct df_scan_bb_info),/* Size of entry of block_info array.  */
    3718                 :            :   TV_DF_NOTE,                 /* Timing variable.  */
    3719                 :            :   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
    3720                 :            : };
    3721                 :            : 
    3722                 :            : 
    3723                 :            : /* Create a new DATAFLOW instance and add it to an existing instance
    3724                 :            :    of DF.  The returned structure is what is used to get at the
    3725                 :            :    solution.  */
    3726                 :            : 
    3727                 :            : void
    3728                 :    8660370 : df_note_add_problem (void)
    3729                 :            : {
    3730                 :    8660370 :   df_add_problem (&problem_NOTE);
    3731                 :    8660370 : }
    3732                 :            : 
    3733                 :            : 
    3734                 :            : 
    3735                 :            : 
    3736                 :            : /*----------------------------------------------------------------------------
    3737                 :            :    Functions for simulating the effects of single insns.
    3738                 :            : 
    3739                 :            :    You can either simulate in the forwards direction, starting from
    3740                 :            :    the top of a block or the backwards direction from the end of the
    3741                 :            :    block.  If you go backwards, defs are examined first to clear bits,
    3742                 :            :    then uses are examined to set bits.  If you go forwards, defs are
    3743                 :            :    examined first to set bits, then REG_DEAD and REG_UNUSED notes
    3744                 :            :    are examined to clear bits.  In either case, the result of examining
    3745                 :            :    a def can be undone (respectively by a use or a REG_UNUSED note).
    3746                 :            : 
    3747                 :            :    If you start at the top of the block, use one of DF_LIVE_IN or
    3748                 :            :    DF_LR_IN.  If you start at the bottom of the block use one of
    3749                 :            :    DF_LIVE_OUT or DF_LR_OUT.  BE SURE TO PASS A COPY OF THESE SETS,
    3750                 :            :    THEY WILL BE DESTROYED.
    3751                 :            : ----------------------------------------------------------------------------*/
    3752                 :            : 
    3753                 :            : 
    3754                 :            : /* Find the set of DEFs for INSN.  */
    3755                 :            : 
    3756                 :            : void
    3757                 :    1186120 : df_simulate_find_defs (rtx_insn *insn, bitmap defs)
    3758                 :            : {
    3759                 :    1186120 :   df_ref def;
    3760                 :            : 
    3761                 :    2063860 :   FOR_EACH_INSN_DEF (def, insn)
    3762                 :     877743 :     bitmap_set_bit (defs, DF_REF_REGNO (def));
    3763                 :    1186120 : }
    3764                 :            : 
    3765                 :            : /* Find the set of uses for INSN.  This includes partial defs.  */
    3766                 :            : 
    3767                 :            : static void
    3768                 :     280915 : df_simulate_find_uses (rtx_insn *insn, bitmap uses)
    3769                 :            : {
    3770                 :     280915 :   df_ref def, use;
    3771                 :     280915 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
    3772                 :            : 
    3773                 :     600879 :   FOR_EACH_INSN_INFO_DEF (def, insn_info)
    3774                 :     319964 :     if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
    3775                 :        166 :       bitmap_set_bit (uses, DF_REF_REGNO (def));
    3776                 :     463339 :   FOR_EACH_INSN_INFO_USE (use, insn_info)
    3777                 :     182424 :     bitmap_set_bit (uses, DF_REF_REGNO (use));
    3778                 :     280915 : }
    3779                 :            : 
    3780                 :            : /* Find the set of real DEFs, which are not clobbers, for INSN.  */
    3781                 :            : 
    3782                 :            : void
    3783                 :  309199000 : df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
    3784                 :            : {
    3785                 :  309199000 :   df_ref def;
    3786                 :            : 
    3787                 : 1511980000 :   FOR_EACH_INSN_DEF (def, insn)
    3788                 : 1202780000 :     if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
    3789                 :  143154000 :       bitmap_set_bit (defs, DF_REF_REGNO (def));
    3790                 :  309199000 : }
    3791                 :            : 
    3792                 :            : 
    3793                 :            : /* Simulate the effects of the defs of INSN on LIVE.  */
    3794                 :            : 
    3795                 :            : void
    3796                 :  455604000 : df_simulate_defs (rtx_insn *insn, bitmap live)
    3797                 :            : {
    3798                 :  455604000 :   df_ref def;
    3799                 :            : 
    3800                 : 3142440000 :   FOR_EACH_INSN_DEF (def, insn)
    3801                 :            :     {
    3802                 : 2686840000 :       unsigned int dregno = DF_REF_REGNO (def);
    3803                 :            : 
    3804                 :            :       /* If the def is to only part of the reg, it does
    3805                 :            :          not kill the other defs that reach here.  */
    3806                 : 2686840000 :       if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
    3807                 : 2684910000 :         bitmap_clear_bit (live, dregno);
    3808                 :            :     }
    3809                 :  455604000 : }
    3810                 :            : 
    3811                 :            : 
    3812                 :            : /* Simulate the effects of the uses of INSN on LIVE.  */
    3813                 :            : 
    3814                 :            : void
    3815                 :  453320000 : df_simulate_uses (rtx_insn *insn, bitmap live)
    3816                 :            : {
    3817                 :  453320000 :   df_ref use;
    3818                 :            : 
    3819                 :  453320000 :   if (DEBUG_INSN_P (insn))
    3820                 :            :     return;
    3821                 :            : 
    3822                 : 1031580000 :   FOR_EACH_INSN_USE (use, insn)
    3823                 :            :     /* Add use to set of uses in this BB.  */
    3824                 :  578263000 :     bitmap_set_bit (live, DF_REF_REGNO (use));
    3825                 :            : }
    3826                 :            : 
    3827                 :            : 
    3828                 :            : /* Add back the always live regs in BB to LIVE.  */
    3829                 :            : 
    3830                 :            : static inline void
    3831                 :  313045000 : df_simulate_fixup_sets (basic_block bb, bitmap live)
    3832                 :            : {
    3833                 :            :   /* These regs are considered always live so if they end up dying
    3834                 :            :      because of some def, we need to bring the back again.  */
    3835                 :  313045000 :   if (bb_has_eh_pred (bb))
    3836                 :    1136170 :     bitmap_ior_into (live, &df->eh_block_artificial_uses);
    3837                 :            :   else
    3838                 :  311909000 :     bitmap_ior_into (live, &df->regular_block_artificial_uses);
    3839                 :  313045000 : }
    3840                 :            : 
    3841                 :            : 
    3842                 :            : /*----------------------------------------------------------------------------
    3843                 :            :    The following three functions are used only for BACKWARDS scanning:
    3844                 :            :    i.e. they process the defs before the uses.
    3845                 :            : 
    3846                 :            :    df_simulate_initialize_backwards should be called first with a
    3847                 :            :    bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT.  Then
    3848                 :            :    df_simulate_one_insn_backwards should be called for each insn in
    3849                 :            :    the block, starting with the last one.  Finally,
    3850                 :            :    df_simulate_finalize_backwards can be called to get a new value
    3851                 :            :    of the sets at the top of the block (this is rarely used).
    3852                 :            :    ----------------------------------------------------------------------------*/
    3853                 :            : 
    3854                 :            : /* Apply the artificial uses and defs at the end of BB in a backwards
    3855                 :            :    direction.  */
    3856                 :            : 
    3857                 :            : void
    3858                 :   82755900 : df_simulate_initialize_backwards (basic_block bb, bitmap live)
    3859                 :            : {
    3860                 :   82755900 :   df_ref def, use;
    3861                 :   82755900 :   int bb_index = bb->index;
    3862                 :            : 
    3863                 :  169019000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    3864                 :    3507160 :     if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
    3865                 :          0 :       bitmap_clear_bit (live, DF_REF_REGNO (def));
    3866                 :            : 
    3867                 :  418957000 :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
    3868                 :  253445000 :     if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
    3869                 :  253445000 :       bitmap_set_bit (live, DF_REF_REGNO (use));
    3870                 :   82755900 : }
    3871                 :            : 
    3872                 :            : 
    3873                 :            : /* Simulate the backwards effects of INSN on the bitmap LIVE.  */
    3874                 :            : 
    3875                 :            : void
    3876                 :    4095880 : df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
    3877                 :            : {
    3878                 :    4095880 :   if (!NONDEBUG_INSN_P (insn))
    3879                 :            :     return;
    3880                 :            : 
    3881                 :    3846380 :   df_simulate_defs (insn, live);
    3882                 :    3846380 :   df_simulate_uses (insn, live);
    3883                 :    3846380 :   df_simulate_fixup_sets (bb, live);
    3884                 :            : }
    3885                 :            : 
    3886                 :            : 
    3887                 :            : /* Apply the artificial uses and defs at the top of BB in a backwards
    3888                 :            :    direction.  */
    3889                 :            : 
    3890                 :            : void
    3891                 :   81703800 : df_simulate_finalize_backwards (basic_block bb, bitmap live)
    3892                 :            : {
    3893                 :   81703800 :   df_ref def;
    3894                 :            : #ifdef EH_USES
    3895                 :            :   df_ref use;
    3896                 :            : #endif
    3897                 :   81703800 :   int bb_index = bb->index;
    3898                 :            : 
    3899                 :  166915000 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    3900                 :    3507120 :     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
    3901                 :    3507120 :       bitmap_clear_bit (live, DF_REF_REGNO (def));
    3902                 :            : 
    3903                 :            : #ifdef EH_USES
    3904                 :            :   FOR_EACH_ARTIFICIAL_USE (use, bb_index)
    3905                 :            :     if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
    3906                 :            :       bitmap_set_bit (live, DF_REF_REGNO (use));
    3907                 :            : #endif
    3908                 :   81703800 : }
    3909                 :            : /*----------------------------------------------------------------------------
    3910                 :            :    The following three functions are used only for FORWARDS scanning:
    3911                 :            :    i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
    3912                 :            :    Thus it is important to add the DF_NOTES problem to the stack of
    3913                 :            :    problems computed before using these functions.
    3914                 :            : 
    3915                 :            :    df_simulate_initialize_forwards should be called first with a
    3916                 :            :    bitvector copyied from the DF_LIVE_IN or DF_LR_IN.  Then
    3917                 :            :    df_simulate_one_insn_forwards should be called for each insn in
    3918                 :            :    the block, starting with the first one.
    3919                 :            :    ----------------------------------------------------------------------------*/
    3920                 :            : 
    3921                 :            : /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
    3922                 :            :    DF_LR_IN for basic block BB, for forward scanning by marking artificial
    3923                 :            :    defs live.  */
    3924                 :            : 
    3925                 :            : void
    3926                 :   23528900 : df_simulate_initialize_forwards (basic_block bb, bitmap live)
    3927                 :            : {
    3928                 :   23528900 :   df_ref def;
    3929                 :   23528900 :   int bb_index = bb->index;
    3930                 :            : 
    3931                 :   71498100 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    3932                 :   24440300 :     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
    3933                 :     778092 :       bitmap_set_bit (live, DF_REF_REGNO (def));
    3934                 :   23528900 : }
    3935                 :            : 
    3936                 :            : /* Simulate the forwards effects of INSN on the bitmap LIVE.  */
    3937                 :            : 
    3938                 :            : void
    3939                 :  309199000 : df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
    3940                 :            : {
    3941                 :  309199000 :   rtx link;
    3942                 :  309199000 :   if (! INSN_P (insn))
    3943                 :            :     return;
    3944                 :            : 
    3945                 :            :   /* Make sure that DF_NOTE really is an active df problem.  */
    3946                 :  309199000 :   gcc_assert (df_note);
    3947                 :            : 
    3948                 :            :   /* Note that this is the opposite as how the problem is defined, because
    3949                 :            :      in the LR problem defs _kill_ liveness.  However, they do so backwards,
    3950                 :            :      while here the scan is performed forwards!  So, first assume that the
    3951                 :            :      def is live, and if this is not true REG_UNUSED notes will rectify the
    3952                 :            :      situation.  */
    3953                 :  309199000 :   df_simulate_find_noclobber_defs (insn, live);
    3954                 :            : 
    3955                 :            :   /* Clear all of the registers that go dead.  */
    3956                 :  516939000 :   for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
    3957                 :            :     {
    3958                 :  207740000 :       switch (REG_NOTE_KIND (link))
    3959                 :            :         {
    3960                 :  134636000 :         case REG_DEAD:
    3961                 :  134636000 :         case REG_UNUSED:
    3962                 :  134636000 :           {
    3963                 :  134636000 :             rtx reg = XEXP (link, 0);
    3964                 :  134636000 :             bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
    3965                 :            :           }
    3966                 :  134636000 :           break;
    3967                 :            :         default:
    3968                 :            :           break;
    3969                 :            :         }
    3970                 :            :     }
    3971                 :  309199000 :   df_simulate_fixup_sets (bb, live);
    3972                 :            : }
    3973                 :            : 
    3974                 :            : /* Used by the next two functions to encode information about the
    3975                 :            :    memory references we found.  */
    3976                 :            : #define MEMREF_NORMAL 1
    3977                 :            : #define MEMREF_VOLATILE 2
    3978                 :            : 
    3979                 :            : /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X.  */
    3980                 :            : 
    3981                 :            : static int
    3982                 :     993620 : find_memory (rtx_insn *insn)
    3983                 :            : {
    3984                 :     993620 :   int flags = 0;
    3985                 :     993620 :   subrtx_iterator::array_type array;
    3986                 :    7142240 :   FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
    3987                 :            :     {
    3988                 :    6148620 :       const_rtx x = *iter;
    3989                 :    6148620 :       if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
    3990                 :          0 :         flags |= MEMREF_VOLATILE;
    3991                 :    6148620 :       else if (MEM_P (x))
    3992                 :            :         {
    3993                 :     104176 :           if (MEM_VOLATILE_P (x))
    3994                 :        238 :             flags |= MEMREF_VOLATILE;
    3995                 :     103938 :           else if (!MEM_READONLY_P (x))
    3996                 :      97794 :             flags |= MEMREF_NORMAL;
    3997                 :            :         }
    3998                 :            :     }
    3999                 :     993620 :   return flags;
    4000                 :            : }
    4001                 :            : 
    4002                 :            : /* A subroutine of can_move_insns_across_p called through note_stores.
    4003                 :            :    DATA points to an integer in which we set either the bit for
    4004                 :            :    MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
    4005                 :            :    of either kind.  */
    4006                 :            : 
    4007                 :            : static void
    4008                 :    1034530 : find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
    4009                 :            :                     void *data ATTRIBUTE_UNUSED)
    4010                 :            : {
    4011                 :    1034530 :   int *pflags = (int *)data;
    4012                 :    1034530 :   if (GET_CODE (x) == SUBREG)
    4013                 :          0 :     x = XEXP (x, 0);
    4014                 :            :   /* Treat stores to SP as stores to memory, this will prevent problems
    4015                 :            :      when there are references to the stack frame.  */
    4016                 :    1034530 :   if (x == stack_pointer_rtx)
    4017                 :       2445 :     *pflags |= MEMREF_VOLATILE;
    4018                 :    1034530 :   if (!MEM_P (x))
    4019                 :            :     return;
    4020                 :      48378 :   *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
    4021                 :            : }
    4022                 :            : 
    4023                 :            : /* Scan BB backwards, using df_simulate functions to keep track of
    4024                 :            :    lifetimes, up to insn POINT.  The result is stored in LIVE.  */
    4025                 :            : 
    4026                 :            : void
    4027                 :     416412 : simulate_backwards_to_point (basic_block bb, regset live, rtx point)
    4028                 :            : {
    4029                 :     416412 :   rtx_insn *insn;
    4030                 :     416412 :   bitmap_copy (live, df_get_live_out (bb));
    4031                 :     416412 :   df_simulate_initialize_backwards (bb, live);
    4032                 :            : 
    4033                 :            :   /* Scan and update life information until we reach the point we're
    4034                 :            :      interested in.  */
    4035                 :    1762100 :   for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
    4036                 :     672845 :     df_simulate_one_insn_backwards (bb, insn, live);
    4037                 :     416412 : }
    4038                 :            : 
    4039                 :            : /* Return true if it is safe to move a group of insns, described by
    4040                 :            :    the range FROM to TO, backwards across another group of insns,
    4041                 :            :    described by ACROSS_FROM to ACROSS_TO.  It is assumed that there
    4042                 :            :    are no insns between ACROSS_TO and FROM, but they may be in
    4043                 :            :    different basic blocks; MERGE_BB is the block from which the
    4044                 :            :    insns will be moved.  The caller must pass in a regset MERGE_LIVE
    4045                 :            :    which specifies the registers live after TO.
    4046                 :            : 
    4047                 :            :    This function may be called in one of two cases: either we try to
    4048                 :            :    move identical instructions from all successor blocks into their
    4049                 :            :    predecessor, or we try to move from only one successor block.  If
    4050                 :            :    OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
    4051                 :            :    the second case.  It should contain a set of registers live at the
    4052                 :            :    end of ACROSS_TO which must not be clobbered by moving the insns.
    4053                 :            :    In that case, we're also more careful about moving memory references
    4054                 :            :    and trapping insns.
    4055                 :            : 
    4056                 :            :    We return false if it is not safe to move the entire group, but it
    4057                 :            :    may still be possible to move a subgroup.  PMOVE_UPTO, if nonnull,
    4058                 :            :    is set to point at the last moveable insn in such a case.  */
    4059                 :            : 
    4060                 :            : bool
    4061                 :     399254 : can_move_insns_across (rtx_insn *from, rtx_insn *to,
    4062                 :            :                        rtx_insn *across_from, rtx_insn *across_to,
    4063                 :            :                        basic_block merge_bb, regset merge_live,
    4064                 :            :                        regset other_branch_live, rtx_insn **pmove_upto)
    4065                 :            : {
    4066                 :     399254 :   rtx_insn *insn, *next, *max_to;
    4067                 :     399254 :   bitmap merge_set, merge_use, local_merge_live;
    4068                 :     399254 :   bitmap test_set, test_use;
    4069                 :     399254 :   unsigned i, fail = 0;
    4070                 :     399254 :   bitmap_iterator bi;
    4071                 :     399254 :   int memrefs_in_across = 0;
    4072                 :     399254 :   int mem_sets_in_across = 0;
    4073                 :     399254 :   bool trapping_insns_in_across = false;
    4074                 :            : 
    4075                 :     399254 :   if (pmove_upto != NULL)
    4076                 :      90128 :     *pmove_upto = NULL;
    4077                 :            : 
    4078                 :            :   /* Find real bounds, ignoring debug insns.  */
    4079                 :     403316 :   while (!NONDEBUG_INSN_P (from) && from != to)
    4080                 :       4062 :     from = NEXT_INSN (from);
    4081                 :     400385 :   while (!NONDEBUG_INSN_P (to) && from != to)
    4082                 :       1131 :     to = PREV_INSN (to);
    4083                 :            : 
    4084                 :            :   for (insn = across_to; ; insn = next)
    4085                 :            :     {
    4086                 :     766450 :       if (CALL_P (insn))
    4087                 :            :         {
    4088                 :        654 :           if (RTL_CONST_OR_PURE_CALL_P (insn))
    4089                 :            :             /* Pure functions can read from memory.  Const functions can
    4090                 :            :                read from arguments that the ABI has forced onto the stack.
    4091                 :            :                Neither sort of read can be volatile.  */
    4092                 :         42 :             memrefs_in_across |= MEMREF_NORMAL;
    4093                 :            :           else
    4094                 :            :             {
    4095                 :        612 :               memrefs_in_across |= MEMREF_VOLATILE;
    4096                 :        612 :               mem_sets_in_across |= MEMREF_VOLATILE;
    4097                 :            :             }
    4098                 :            :         }
    4099                 :     766450 :       if (NONDEBUG_INSN_P (insn))
    4100                 :            :         {
    4101                 :     761620 :           if (volatile_insn_p (PATTERN (insn)))
    4102                 :            :             return false;
    4103                 :     761620 :           memrefs_in_across |= find_memory (insn);
    4104                 :     761620 :           note_stores (insn, find_memory_stores, &mem_sets_in_across);
    4105                 :            :           /* This is used just to find sets of the stack pointer.  */
    4106                 :     761620 :           memrefs_in_across |= mem_sets_in_across;
    4107                 :     761620 :           trapping_insns_in_across |= may_trap_p (PATTERN (insn));
    4108                 :            :         }
    4109                 :     766450 :       next = PREV_INSN (insn);
    4110                 :     766450 :       if (insn == across_from)
    4111                 :            :         break;
    4112                 :            :     }
    4113                 :            : 
    4114                 :            :   /* Collect:
    4115                 :            :      MERGE_SET = set of registers set in MERGE_BB
    4116                 :            :      MERGE_USE = set of registers used in MERGE_BB and live at its top
    4117                 :            :      MERGE_LIVE = set of registers live at the point inside the MERGE
    4118                 :            :      range that we've reached during scanning
    4119                 :            :      TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
    4120                 :            :      TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
    4121                 :            :      and live before ACROSS_FROM.  */
    4122                 :            : 
    4123                 :     399254 :   merge_set = BITMAP_ALLOC (&reg_obstack);
    4124                 :     399254 :   merge_use = BITMAP_ALLOC (&reg_obstack);
    4125                 :     399254 :   local_merge_live = BITMAP_ALLOC (&reg_obstack);
    4126                 :     399254 :   test_set = BITMAP_ALLOC (&reg_obstack);
    4127                 :     399254 :   test_use = BITMAP_ALLOC (&reg_obstack);
    4128                 :            : 
    4129                 :            :   /* Compute the set of registers set and used in the ACROSS range.  */
    4130                 :     399254 :   if (other_branch_live != NULL)
    4131                 :     309126 :     bitmap_copy (test_use, other_branch_live);
    4132                 :     399254 :   df_simulate_initialize_backwards (merge_bb, test_use);
    4133                 :     399254 :   for (insn = across_to; ; insn = next)
    4134                 :            :     {
    4135                 :     766450 :       if (NONDEBUG_INSN_P (insn))
    4136                 :            :         {
    4137                 :     761620 :           df_simulate_find_defs (insn, test_set);
    4138                 :     761620 :           df_simulate_defs (insn, test_use);
    4139                 :     761620 :           df_simulate_uses (insn, test_use);
    4140                 :            :         }
    4141                 :     766450 :       next = PREV_INSN (insn);
    4142                 :     766450 :       if (insn == across_from)
    4143                 :            :         break;
    4144                 :            :     }
    4145                 :            : 
    4146                 :            :   /* Compute an upper bound for the amount of insns moved, by finding
    4147                 :            :      the first insn in MERGE that sets a register in TEST_USE, or uses
    4148                 :            :      a register in TEST_SET.  We also check for calls, trapping operations,
    4149                 :            :      and memory references.  */
    4150                 :            :   max_to = NULL;
    4151                 :            :   for (insn = from; ; insn = next)
    4152                 :            :     {
    4153                 :     438456 :       if (CALL_P (insn))
    4154                 :            :         break;
    4155                 :     429283 :       if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
    4156                 :            :         break;
    4157                 :     429283 :       if (NONDEBUG_INSN_P (insn))
    4158                 :            :         {
    4159                 :     423371 :           if (may_trap_or_fault_p (PATTERN (insn))
    4160                 :     423371 :               && (trapping_insns_in_across
    4161                 :     126107 :                   || other_branch_live != NULL
    4162                 :       9301 :                   || volatile_insn_p (PATTERN (insn))))
    4163                 :            :             break;
    4164                 :            : 
    4165                 :            :           /* We cannot move memory stores past each other, or move memory
    4166                 :            :              reads past stores, at least not without tracking them and
    4167                 :            :              calling true_dependence on every pair.
    4168                 :            : 
    4169                 :            :              If there is no other branch and no memory references or
    4170                 :            :              sets in the ACROSS range, we can move memory references
    4171                 :            :              freely, even volatile ones.
    4172                 :            : 
    4173                 :            :              Otherwise, the rules are as follows: volatile memory
    4174                 :            :              references and stores can't be moved at all, and any type
    4175                 :            :              of memory reference can't be moved if there are volatile
    4176                 :            :              accesses or stores in the ACROSS range.  That leaves
    4177                 :            :              normal reads, which can be moved, as the trapping case is
    4178                 :            :              dealt with elsewhere.  */
    4179                 :     305499 :           if (other_branch_live != NULL || memrefs_in_across != 0)
    4180                 :            :             {
    4181                 :     232000 :               int mem_ref_flags = 0;
    4182                 :     232000 :               int mem_set_flags = 0;
    4183                 :     232000 :               note_stores (insn, find_memory_stores, &mem_set_flags);
    4184                 :     232000 :               mem_ref_flags = find_memory (insn);
    4185                 :            :               /* Catch sets of the stack pointer.  */
    4186                 :     232000 :               mem_ref_flags |= mem_set_flags;
    4187                 :            : 
    4188                 :     232000 :               if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
    4189                 :            :                 break;
    4190                 :     229823 :               if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
    4191                 :            :                 break;
    4192                 :     229588 :               if (mem_set_flags != 0
    4193                 :     207454 :                   || (mem_sets_in_across != 0 && mem_ref_flags != 0))
    4194                 :            :                 break;
    4195                 :            :             }
    4196                 :     280915 :           df_simulate_find_uses (insn, merge_use);
    4197                 :            :           /* We're only interested in uses which use a value live at
    4198                 :            :              the top, not one previously set in this block.  */
    4199                 :     280915 :           bitmap_and_compl_into (merge_use, merge_set);
    4200                 :     280915 :           df_simulate_find_defs (insn, merge_set);
    4201                 :     280915 :           if (bitmap_intersect_p (merge_set, test_use)
    4202                 :     280915 :               || bitmap_intersect_p (merge_use, test_set))
    4203                 :            :             break;
    4204                 :            :           if (!HAVE_cc0 || !sets_cc0_p (insn))
    4205                 :            :             max_to = insn;
    4206                 :            :         }
    4207                 :     196930 :       next = NEXT_INSN (insn);
    4208                 :     196930 :       if (insn == to)
    4209                 :            :         break;
    4210                 :            :     }
    4211                 :     399254 :   if (max_to != to)
    4212                 :     241527 :     fail = 1;
    4213                 :            : 
    4214                 :     399254 :   if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
    4215                 :     239942 :     goto out;
    4216                 :            : 
    4217                 :            :   /* Now, lower this upper bound by also taking into account that
    4218                 :            :      a range of insns moved across ACROSS must not leave a register
    4219                 :            :      live at the end that will be clobbered in ACROSS.  We need to
    4220                 :            :      find a point where TEST_SET & LIVE == 0.
    4221                 :            : 
    4222                 :            :      Insns in the MERGE range that set registers which are also set
    4223                 :            :      in the ACROSS range may still be moved as long as we also move
    4224                 :            :      later insns which use the results of the set, and make the
    4225                 :            :      register dead again.  This is verified by the condition stated
    4226                 :            :      above.  We only need to test it for registers that are set in
    4227                 :            :      the moved region.
    4228                 :            : 
    4229                 :            :      MERGE_LIVE is provided by the caller and holds live registers after
    4230                 :            :      TO.  */
    4231                 :     159312 :   bitmap_copy (local_merge_live, merge_live);
    4232                 :     179012 :   for (insn = to; insn != max_to; insn = PREV_INSN (insn))
    4233                 :       9850 :     df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
    4234                 :            : 
    4235                 :            :   /* We're not interested in registers that aren't set in the moved
    4236                 :            :      region at all.  */
    4237                 :     159312 :   bitmap_and_into (local_merge_live, merge_set);
    4238                 :        798 :   for (;;)
    4239                 :            :     {
    4240                 :     160110 :       if (NONDEBUG_INSN_P (insn))
    4241                 :            :         {
    4242                 :     159979 :           if (!bitmap_intersect_p (test_set, local_merge_live)
    4243                 :            :               && (!HAVE_cc0 || !sets_cc0_p (insn)))
    4244                 :            :             {
    4245                 :     136392 :               max_to = insn;
    4246                 :     136392 :               break;
    4247                 :            :             }
    4248                 :            : 
    4249                 :      23587 :           df_simulate_one_insn_backwards (merge_bb, insn,
    4250                 :            :                                           local_merge_live);
    4251                 :            :         }
    4252                 :      23718 :       if (insn == from)
    4253                 :            :         {
    4254                 :      22920 :           fail = 1;
    4255                 :      22920 :           goto out;
    4256                 :            :         }
    4257                 :        798 :       insn = PREV_INSN (insn);
    4258                 :            :     }
    4259                 :            : 
    4260                 :     136392 :   if (max_to != to)
    4261                 :       2109 :     fail = 1;
    4262                 :            : 
    4263                 :     136392 :   if (pmove_upto)
    4264                 :      19528 :     *pmove_upto = max_to;
    4265                 :            : 
    4266                 :            :   /* For small register class machines, don't lengthen lifetimes of
    4267                 :            :      hard registers before reload.  */
    4268                 :     136392 :   if (! reload_completed
    4269                 :     136392 :       && targetm.small_register_classes_for_mode_p (VOIDmode))
    4270                 :            :     {
    4271                 :     223737 :       EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
    4272                 :            :         {
    4273                 :     123037 :           if (i < FIRST_PSEUDO_REGISTER
    4274                 :       7690 :               && ! fixed_regs[i]
    4275                 :          0 :               && ! global_regs[i])
    4276                 :            :             {
    4277                 :            :               fail = 1;
    4278                 :            :               break;
    4279                 :            :             }
    4280                 :            :         }
    4281                 :            :     }
    4282                 :            : 
    4283                 :     399254 :  out:
    4284                 :     399254 :   BITMAP_FREE (merge_set);
    4285                 :     399254 :   BITMAP_FREE (merge_use);
    4286                 :     399254 :   BITMAP_FREE (local_merge_live);
    4287                 :     399254 :   BITMAP_FREE (test_set);
    4288                 :     399254 :   BITMAP_FREE (test_use);
    4289                 :            : 
    4290                 :     399254 :   return !fail;
    4291                 :            : }
    4292                 :            : 
    4293                 :            : 
    4294                 :            : /*----------------------------------------------------------------------------
    4295                 :            :    MULTIPLE DEFINITIONS
    4296                 :            : 
    4297                 :            :    Find the locations in the function reached by multiple definition sites
    4298                 :            :    for a live pseudo.  In and out bitvectors are built for each basic
    4299                 :            :    block.  They are restricted for efficiency to live registers.
    4300                 :            : 
    4301                 :            :    The gen and kill sets for the problem are obvious.  Together they
    4302                 :            :    include all defined registers in a basic block; the gen set includes
    4303                 :            :    registers where a partial or conditional or may-clobber definition is
    4304                 :            :    last in the BB, while the kill set includes registers with a complete
    4305                 :            :    definition coming last.  However, the computation of the dataflow
    4306                 :            :    itself is interesting.
    4307                 :            : 
    4308                 :            :    The idea behind it comes from SSA form's iterated dominance frontier
    4309                 :            :    criterion for inserting PHI functions.  Just like in that case, we can use
    4310                 :            :    the dominance frontier to find places where multiple definitions meet;
    4311                 :            :    a register X defined in a basic block BB1 has multiple definitions in
    4312                 :            :    basic blocks in BB1's dominance frontier.
    4313                 :            : 
    4314                 :            :    So, the in-set of a basic block BB2 is not just the union of the
    4315                 :            :    out-sets of BB2's predecessors, but includes some more bits that come
    4316                 :            :    from the basic blocks of whose dominance frontier BB2 is part (BB1 in
    4317                 :            :    the previous paragraph).  I called this set the init-set of BB2.
    4318                 :            : 
    4319                 :            :       (Note: I actually use the kill-set only to build the init-set.
    4320                 :            :       gen bits are anyway propagated from BB1 to BB2 by dataflow).
    4321                 :            : 
    4322                 :            :     For example, if you have
    4323                 :            : 
    4324                 :            :        BB1 : r10 = 0
    4325                 :            :              r11 = 0
    4326                 :            :              if <...> goto BB2 else goto BB3;
    4327                 :            : 
    4328                 :            :        BB2 : r10 = 1
    4329                 :            :              r12 = 1
    4330                 :            :              goto BB3;
    4331                 :            : 
    4332                 :            :        BB3 :
    4333                 :            : 
    4334                 :            :     you have BB3 in BB2's dominance frontier but not in BB1's, so that the
    4335                 :            :     init-set of BB3 includes r10 and r12, but not r11.  Note that we do
    4336                 :            :     not need to iterate the dominance frontier, because we do not insert
    4337                 :            :     anything like PHI functions there!  Instead, dataflow will take care of
    4338                 :            :     propagating the information to BB3's successors.
    4339                 :            :    ---------------------------------------------------------------------------*/
    4340                 :            : 
    4341                 :            : /* Private data used to verify the solution for this problem.  */
    4342                 :            : struct df_md_problem_data
    4343                 :            : {
    4344                 :            :   /* An obstack for the bitmaps we need for this problem.  */
    4345                 :            :   bitmap_obstack md_bitmaps;
    4346                 :            : };
    4347                 :            : 
    4348                 :            : /* Scratch var used by transfer functions.  This is used to do md analysis
    4349                 :            :    only for live registers.  */
    4350                 :            : static bitmap_head df_md_scratch;
    4351                 :            : 
    4352                 :            : 
    4353                 :            : static void
    4354                 :       7699 : df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
    4355                 :            :                     void *vbb_info)
    4356                 :            : {
    4357                 :       7699 :   class df_md_bb_info *bb_info = (class df_md_bb_info *) vbb_info;
    4358                 :       7699 :   if (bb_info)
    4359                 :            :     {
    4360                 :       7699 :       bitmap_clear (&bb_info->kill);
    4361                 :       7699 :       bitmap_clear (&bb_info->gen);
    4362                 :       7699 :       bitmap_clear (&bb_info->init);
    4363                 :       7699 :       bitmap_clear (&bb_info->in);
    4364                 :       7699 :       bitmap_clear (&bb_info->out);
    4365                 :            :     }
    4366                 :       7699 : }
    4367                 :            : 
    4368                 :            : 
    4369                 :            : /* Allocate or reset bitmaps for DF_MD. The solution bits are
    4370                 :            :    not touched unless the block is new.  */
    4371                 :            : 
    4372                 :            : static void
    4373                 :    1375820 : df_md_alloc (bitmap all_blocks)
    4374                 :            : {
    4375                 :    1375820 :   unsigned int bb_index;
    4376                 :    1375820 :   bitmap_iterator bi;
    4377                 :    1375820 :   struct df_md_problem_data *problem_data;
    4378                 :            : 
    4379                 :    1375820 :   df_grow_bb_info (df_md);
    4380                 :    1375820 :   if (df_md->problem_data)
    4381                 :            :     problem_data = (struct df_md_problem_data *) df_md->problem_data;
    4382                 :            :   else
    4383                 :            :     {
    4384                 :    1375820 :       problem_data = XNEW (struct df_md_problem_data);
    4385                 :    1375820 :       df_md->problem_data = problem_data;
    4386                 :    1375820 :       bitmap_obstack_initialize (&problem_data->md_bitmaps);
    4387                 :            :     }
    4388                 :    1375820 :   bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
    4389                 :            : 
    4390                 :   17780300 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    4391                 :            :     {
    4392                 :   16404400 :       class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
    4393                 :            :       /* When bitmaps are already initialized, just clear them.  */
    4394                 :   16404400 :       if (bb_info->init.obstack)
    4395                 :            :         {
    4396                 :          0 :           bitmap_clear (&bb_info->init);
    4397                 :          0 :           bitmap_clear (&bb_info->gen);
    4398                 :          0 :           bitmap_clear (&bb_info->kill);
    4399                 :          0 :           bitmap_clear (&bb_info->in);
    4400                 :          0 :           bitmap_clear (&bb_info->out);
    4401                 :            :         }
    4402                 :            :       else
    4403                 :            :         {
    4404                 :   16404400 :           bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
    4405                 :   16404400 :           bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
    4406                 :   16404400 :           bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
    4407                 :   16404400 :           bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
    4408                 :   16404400 :           bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
    4409                 :            :         }
    4410                 :            :     }
    4411                 :            : 
    4412                 :    1375820 :   df_md->optional_p = true;
    4413                 :    1375820 : }
    4414                 :            : 
    4415                 :            : /* Add the effect of the top artificial defs of BB to the multiple definitions
    4416                 :            :    bitmap LOCAL_MD.  */
    4417                 :            : 
    4418                 :            : void
    4419                 :          0 : df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
    4420                 :            : {
    4421                 :          0 :   int bb_index = bb->index;
    4422                 :          0 :   df_ref def;
    4423                 :          0 :   FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
    4424                 :          0 :     if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
    4425                 :            :       {
    4426                 :          0 :         unsigned int dregno = DF_REF_REGNO (def);
    4427                 :          0 :         if (DF_REF_FLAGS (def)
    4428                 :            :             & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
    4429                 :          0 :           bitmap_set_bit (local_md, dregno);
    4430                 :            :         else
    4431                 :          0 :           bitmap_clear_bit (local_md, dregno);
    4432                 :            :       }
    4433                 :          0 : }
    4434                 :            : 
    4435                 :            : 
    4436                 :            : /* Add the effect of the defs of INSN to the reaching definitions bitmap
    4437                 :            :    LOCAL_MD.  */
    4438                 :            : 
    4439                 :            : void
    4440                 :          0 : df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
    4441                 :            :                          bitmap local_md)
    4442                 :            : {
    4443                 :          0 :   df_ref def;
    4444                 :            : 
    4445                 :          0 :   FOR_EACH_INSN_DEF (def, insn)
    4446                 :            :     {
    4447                 :          0 :       unsigned int dregno = DF_REF_REGNO (def);
    4448                 :          0 :       if ((!(df->changeable_flags & DF_NO_HARD_REGS))
    4449                 :          0 :           || (dregno >= FIRST_PSEUDO_REGISTER))
    4450                 :            :         {
    4451                 :          0 :           if (DF_REF_FLAGS (def)
    4452                 :            :               & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
    4453                 :          0 :            bitmap_set_bit (local_md, DF_REF_ID (def));
    4454                 :            :          else
    4455                 :          0 :            bitmap_clear_bit (local_md, DF_REF_ID (def));
    4456                 :            :         }
    4457                 :            :     }
    4458                 :          0 : }
    4459                 :            : 
    4460                 :            : static void
    4461                 :  169526000 : df_md_bb_local_compute_process_def (class df_md_bb_info *bb_info,
    4462                 :            :                                     df_ref def,
    4463                 :            :                                     int top_flag)
    4464                 :            : {
    4465                 :  169526000 :   bitmap_clear (&seen_in_insn);
    4466                 :            : 
    4467                 :  705329000 :   for (; def; def = DF_REF_NEXT_LOC (def))
    4468                 :            :     {
    4469                 :  535803000 :       unsigned int dregno = DF_REF_REGNO (def);
    4470                 :  535803000 :       if (((!(df->changeable_flags & DF_NO_HARD_REGS))
    4471                 :          0 :             || (dregno >= FIRST_PSEUDO_REGISTER))
    4472                 :  535803000 :           && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
    4473                 :            :         {
    4474                 :  510426000 :           if (!bitmap_bit_p (&seen_in_insn, dregno))
    4475                 :            :             {
    4476                 :  510426000 :               if (DF_REF_FLAGS (def)
    4477                 :            :                   & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
    4478                 :            :                 {
    4479                 :  413426000 :                   bitmap_set_bit (&bb_info->gen, dregno);
    4480                 :  413426000 :                   bitmap_clear_bit (&bb_info->kill, dregno);
    4481                 :            :                 }
    4482                 :            :               else
    4483                 :            :                 {
    4484                 :            :                   /* When we find a clobber and a regular def,
    4485                 :            :                      make sure the regular def wins.  */
    4486                 :   96999100 :                   bitmap_set_bit (&seen_in_insn, dregno);
    4487                 :   96999100 :                   bitmap_set_bit (&bb_info->kill, dregno);
    4488                 :   96999100 :                   bitmap_clear_bit (&bb_info->gen, dregno);
    4489                 :            :                 }
    4490                 :            :             }
    4491                 :            :         }
    4492                 :            :     }
    4493                 :  169526000 : }
    4494                 :            : 
    4495                 :            : 
    4496                 :            : /* Compute local multiple def info for basic block BB.  */
    4497                 :            : 
    4498                 :            : static void
    4499                 :   16404400 : df_md_bb_local_compute (unsigned int bb_index)
    4500                 :            : {
    4501                 :   16404400 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    4502                 :   16404400 :   class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
    4503                 :   16404400 :   rtx_insn *insn;
    4504                 :            : 
    4505                 :            :   /* Artificials are only hard regs.  */
    4506                 :   16404400 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
    4507                 :   32808900 :     df_md_bb_local_compute_process_def (bb_info,
    4508                 :            :                                         df_get_artificial_defs (bb_index),
    4509                 :            :                                         DF_REF_AT_TOP);
    4510                 :            : 
    4511                 :  333133000 :   FOR_BB_INSNS (bb, insn)
    4512                 :            :     {
    4513                 :  158364000 :       unsigned int uid = INSN_UID (insn);
    4514                 :  158364000 :       if (!INSN_P (insn))
    4515                 :   21647000 :         continue;
    4516                 :            : 
    4517                 :  136717000 :       df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
    4518                 :            :     }
    4519                 :            : 
    4520                 :   16404400 :   if (!(df->changeable_flags & DF_NO_HARD_REGS))
    4521                 :   32808900 :     df_md_bb_local_compute_process_def (bb_info,
    4522                 :            :                                         df_get_artificial_defs (bb_index),
    4523                 :            :                                         0);
    4524                 :   16404400 : }
    4525                 :            : 
    4526                 :            : /* Compute local reaching def info for each basic block within BLOCKS.  */
    4527                 :            : 
    4528                 :            : static void
    4529                 :    1375820 : df_md_local_compute (bitmap all_blocks)
    4530                 :            : {
    4531                 :    1375820 :   unsigned int bb_index, df_bb_index;
    4532                 :    1375820 :   bitmap_iterator bi1, bi2;
    4533                 :    1375820 :   basic_block bb;
    4534                 :    1375820 :   bitmap_head *frontiers;
    4535                 :            : 
    4536                 :    1375820 :   bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
    4537                 :            : 
    4538                 :   17780300 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
    4539                 :            :     {
    4540                 :   16404400 :       df_md_bb_local_compute (bb_index);
    4541                 :            :     }
    4542                 :            : 
    4543                 :    1375820 :   bitmap_release (&seen_in_insn);
    4544                 :            : 
    4545                 :    1375820 :   frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
    4546                 :   17780300 :   FOR_ALL_BB_FN (bb, cfun)
    4547                 :   16404400 :     bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
    4548                 :            : 
    4549                 :    1375820 :   compute_dominance_frontiers (frontiers);
    4550                 :            : 
    4551                 :            :   /* Add each basic block's kills to the nodes in the frontier of the BB.  */
    4552                 :   17780300 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
    4553                 :            :     {
    4554                 :   16404400 :       bitmap kill = &df_md_get_bb_info (bb_index)->kill;
    4555                 :   30589100 :       EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
    4556                 :            :         {
    4557                 :   14184700 :           basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
    4558                 :   14184700 :           if (bitmap_bit_p (all_blocks, df_bb_index))
    4559                 :   28369400 :             bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
    4560                 :   14184700 :                                  df_get_live_in (bb));
    4561                 :            :         }
    4562                 :            :     }
    4563                 :            : 
    4564                 :   17780300 :   FOR_ALL_BB_FN (bb, cfun)
    4565                 :   16404400 :     bitmap_clear (&frontiers[bb->index]);
    4566                 :    1375820 :   free (frontiers);
    4567                 :    1375820 : }
    4568                 :            : 
    4569                 :            : 
    4570                 :            : /* Reset the global solution for recalculation.  */
    4571                 :            : 
    4572                 :            : static void
    4573                 :          0 : df_md_reset (bitmap all_blocks)
    4574                 :            : {
    4575                 :          0 :   unsigned int bb_index;
    4576                 :          0 :   bitmap_iterator bi;
    4577                 :            : 
    4578                 :          0 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    4579                 :            :     {
    4580                 :          0 :       class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
    4581                 :          0 :       gcc_assert (bb_info);
    4582                 :          0 :       bitmap_clear (&bb_info->in);
    4583                 :          0 :       bitmap_clear (&bb_info->out);
    4584                 :            :     }
    4585                 :          0 : }
    4586                 :            : 
    4587                 :            : static bool
    4588                 :   33836100 : df_md_transfer_function (int bb_index)
    4589                 :            : {
    4590                 :   33836100 :   basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
    4591                 :   33836100 :   class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
    4592                 :   33836100 :   bitmap in = &bb_info->in;
    4593                 :   33836100 :   bitmap out = &bb_info->out;
    4594                 :   33836100 :   bitmap gen = &bb_info->gen;
    4595                 :   33836100 :   bitmap kill = &bb_info->kill;
    4596                 :            : 
    4597                 :            :   /* We need to use a scratch set here so that the value returned from this
    4598                 :            :      function invocation properly reflects whether the sets changed in a
    4599                 :            :      significant way; i.e. not just because the live set was anded in.  */
    4600                 :   33836100 :   bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
    4601                 :            : 
    4602                 :            :   /* Multiple definitions of a register are not relevant if it is not
    4603                 :            :      live.  Thus we trim the result to the places where it is live.  */
    4604                 :   33836100 :   bitmap_and_into (in, df_get_live_in (bb));
    4605                 :            : 
    4606                 :   33836100 :   return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
    4607                 :            : }
    4608                 :            : 
    4609                 :            : /* Initialize the solution bit vectors for problem.  */
    4610                 :            : 
    4611                 :            : static void
    4612                 :    1375820 : df_md_init (bitmap all_blocks)
    4613                 :            : {
    4614                 :    1375820 :   unsigned int bb_index;
    4615                 :    1375820 :   bitmap_iterator bi;
    4616                 :            : 
    4617                 :   17780300 :   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
    4618                 :            :     {
    4619                 :   16404400 :       class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
    4620                 :            : 
    4621                 :   16404400 :       bitmap_copy (&bb_info->in, &bb_info->init);
    4622                 :   16404400 :       df_md_transfer_function (bb_index);
    4623                 :            :     }
    4624                 :    1375820 : }
    4625                 :            : 
    4626                 :            : static void
    4627                 :    1414370 : df_md_confluence_0 (basic_block bb)
    4628                 :            : {
    4629                 :    1414370 :   class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
    4630                 :    1414370 :   bitmap_copy (&bb_info->in, &bb_info->init);
    4631                 :    1414370 : }
    4632                 :            : 
    4633                 :            : /* In of target gets or of out of source.  */
    4634                 :            : 
    4635                 :            : static bool
    4636                 :   22944400 : df_md_confluence_n (edge e)
    4637                 :            : {
    4638                 :   22944400 :   bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
    4639                 :   22944400 :   bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
    4640                 :            : 
    4641                 :   22944400 :   if (e->flags & EDGE_FAKE)
    4642                 :            :     return false;
    4643                 :            : 
    4644                 :   22944400 :   if (e->flags & EDGE_EH)
    4645                 :            :     {
    4646                 :            :       /* Conservatively treat partially-clobbered registers as surviving
    4647                 :            :          across the edge; they might or might not, depending on what mode
    4648                 :            :          they have.  */
    4649                 :     994271 :       bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
    4650                 :     994271 :       return bitmap_ior_and_compl_into (op1, op2, eh_kills);
    4651                 :            :     }
    4652                 :            :   else
    4653                 :   21950100 :     return bitmap_ior_into (op1, op2);
    4654                 :            : }
    4655                 :            : 
    4656                 :            : /* Free all storage associated with the problem.  */
    4657                 :            : 
    4658                 :            : static void
    4659                 :    1375820 : df_md_free (void)
    4660                 :            : {
    4661                 :    1375820 :   struct df_md_problem_data *problem_data
    4662                 :    1375820 :     = (struct df_md_problem_data *) df_md->problem_data;
    4663                 :            : 
    4664                 :    1375820 :   bitmap_release (&df_md_scratch);
    4665                 :    1375820 :   bitmap_obstack_release (&problem_data->md_bitmaps);
    4666                 :    1375820 :   free (problem_data);
    4667                 :    1375820 :   df_md->problem_data = NULL;
    4668                 :            : 
    4669                 :    1375820 :   df_md->block_info_size = 0;
    4670                 :    1375820 :   free (df_md->block_info);
    4671                 :    1375820 :   df_md->block_info = NULL;
    4672                 :    1375820 :   free (df_md);
    4673                 :    1375820 : }
    4674                 :            : 
    4675                 :            : 
    4676                 :            : /* Debugging info at top of bb.  */
    4677                 :            : 
    4678                 :            : static void
    4679                 :          0 : df_md_top_dump (basic_block bb, FILE *file)
    4680                 :            : {
    4681                 :          0 :   class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
    4682                 :          0 :   if (!bb_info)
    4683                 :            :     return;
    4684                 :            : 
    4685                 :          0 :   fprintf (file, ";; md  in  \t");
    4686                 :          0 :   df_print_regset (file, &bb_info->in);
    4687                 :          0 :   fprintf (file, ";; md  init  \t");
    4688                 :          0 :   df_print_regset (file, &bb_info->init);
    4689                 :          0 :   fprintf (file, ";; md  gen \t");
    4690                 :          0 :   df_print_regset (file, &bb_info->gen);
    4691                 :          0 :   fprintf (file, ";; md  kill \t");
    4692                 :          0 :   df_print_regset (file, &bb_info->kill);
    4693                 :            : }
    4694                 :            : 
    4695                 :            : /* Debugging info at bottom of bb.  */
    4696                 :            : 
    4697                 :            : static void
    4698                 :          0 : df_md_bottom_dump (basic_block bb, FILE *file)
    4699                 :            : {
    4700                 :          0 :   class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
    4701                 :          0 :   if (!bb_info)
    4702                 :            :     return;
    4703                 :            : 
    4704                 :          0 :   fprintf (file, ";; md  out \t");
    4705                 :          0 :   df_print_regset (file, &bb_info->out);
    4706                 :            : }
    4707                 :            : 
    4708                 :            : static const struct df_problem problem_MD =
    4709                 :            : {
    4710                 :            :   DF_MD,                      /* Problem id.  */
    4711                 :            :   DF_FORWARD,                 /* Direction.  */
    4712                 :            :   df_md_alloc,                /* Allocate the problem specific data.  */
    4713                 :            :   df_md_reset,                /* Reset global information.  */
    4714                 :            :   df_md_free_bb_info,         /* Free basic block info.  */
    4715                 :            :   df_md_local_compute,        /* Local compute function.  */
    4716                 :            :   df_md_init,                 /* Init the solution specific data.  */
    4717                 :            :   df_worklist_dataflow,       /* Worklist solver.  */
    4718                 :            :   df_md_confluence_0,         /* Confluence operator 0.  */
    4719                 :            :   df_md_confluence_n,         /* Confluence operator n.  */
    4720                 :            :   df_md_transfer_function,    /* Transfer function.  */
    4721                 :            :   NULL,                       /* Finalize function.  */
    4722                 :            :   df_md_free,                 /* Free all of the problem information.  */
    4723                 :            :   df_md_free,                 /* Remove this problem from the stack of dataflow problems.  */
    4724                 :            :   NULL,                       /* Debugging.  */
    4725                 :            :   df_md_top_dump,             /* Debugging start block.  */
    4726                 :            :   df_md_bottom_dump,          /* Debugging end block.  */
    4727                 :            :   NULL,                       /* Debugging start insn.  */
    4728                 :            :   NULL,                       /* Debugging end insn.  */
    4729                 :            :   NULL,                       /* Incremental solution verify start.  */
    4730                 :            :   NULL,                       /* Incremental solution verify end.  */
    4731                 :            :   NULL,                       /* Dependent problem.  */
    4732                 :            :   sizeof (class df_md_bb_info),/* Size of entry of block_info array.  */
    4733                 :            :   TV_DF_MD,                   /* Timing variable.  */
    4734                 :            :   false                       /* Reset blocks on dropping out of blocks_to_analyze.  */
    4735                 :            : };
    4736                 :            : 
    4737                 :            : /* Create a new MD instance and add it to the existing instance
    4738                 :            :    of DF.  */
    4739                 :            : 
    4740                 :            : void
    4741                 :    1375820 : df_md_add_problem (void)
    4742                 :            : {
    4743                 :    1375820 :   df_add_problem (&problem_MD);
    4744                 :    1375820 : }
    4745                 :            : 
    4746                 :            : 
    4747                 :            : 

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.