LCOV - code coverage report
Current view: top level - gcc - web.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 166 175 94.9 %
Date: 2020-04-04 11:58:09 Functions: 9 9 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Web construction code for GNU compiler.
       2                 :            :    Contributed by Jan Hubicka.
       3                 :            :    Copyright (C) 2001-2020 Free Software Foundation, Inc.
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify it under
       8                 :            : the terms of the GNU General Public License as published by the Free
       9                 :            : Software Foundation; either version 3, or (at your option) any later
      10                 :            : version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
      13                 :            : WARRANTY; without even the implied warranty of MERCHANTABILITY or
      14                 :            : FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
      15                 :            : for more details.
      16                 :            : 
      17                 :            : You should have received a copy of the GNU General Public License
      18                 :            : along with GCC; see the file COPYING3.  If not see
      19                 :            : <http://www.gnu.org/licenses/>.  */
      20                 :            : 
      21                 :            : /* Simple optimization pass that splits independent uses of each pseudo,
      22                 :            :    increasing effectiveness of other optimizations.  The optimization can
      23                 :            :    serve as an example of use for the dataflow module.
      24                 :            : 
      25                 :            :    TODO
      26                 :            :     - We may use profile information and ignore infrequent use for the
      27                 :            :       purpose of web unifying, inserting the compensation code later to
      28                 :            :       implement full induction variable expansion for loops (currently
      29                 :            :       we expand only if the induction variable is dead afterward, which
      30                 :            :       is often the case).  */
      31                 :            : 
      32                 :            : #include "config.h"
      33                 :            : #include "system.h"
      34                 :            : #include "coretypes.h"
      35                 :            : #include "backend.h"
      36                 :            : #include "rtl.h"
      37                 :            : #include "df.h"
      38                 :            : #include "insn-config.h"
      39                 :            : #include "recog.h"
      40                 :            : 
      41                 :            : #include "tree-pass.h"
      42                 :            : 
      43                 :            : 
      44                 :            : /* Find the root of unionfind tree (the representative of set).  */
      45                 :            : 
      46                 :            : web_entry_base *
      47                 :   11040000 : web_entry_base::unionfind_root ()
      48                 :            : {
      49                 :   11040000 :   web_entry_base *element = this, *element1 = this, *element2;
      50                 :            : 
      51                 :   19532100 :   while (element->pred ())
      52                 :            :     element = element->pred ();
      53                 :   19532100 :   while (element1->pred ())
      54                 :            :     {
      55                 :    8492100 :       element2 = element1->pred ();
      56                 :    8492100 :       element1->set_pred (element);
      57                 :    8492100 :       element1 = element2;
      58                 :            :     }
      59                 :   11040000 :   return element;
      60                 :            : }
      61                 :            : 
      62                 :            : /* Union sets.
      63                 :            :    Return true if FIRST and SECOND points to the same web entry structure and
      64                 :            :    nothing is done.  Otherwise, return false.  */
      65                 :            : 
      66                 :            : bool
      67                 :    3512740 : unionfind_union (web_entry_base *first, web_entry_base *second)
      68                 :            : {
      69                 :    3512740 :   first = first->unionfind_root ();
      70                 :    3512740 :   second = second->unionfind_root ();
      71                 :    3512740 :   if (first == second)
      72                 :            :     return true;
      73                 :    2871150 :   second->set_pred (first);
      74                 :    2871150 :   return false;
      75                 :            : }
      76                 :            : 
      77                 :            : struct web_entry : public web_entry_base
      78                 :            : {
      79                 :            :  private:
      80                 :            :   rtx reg_pvt;
      81                 :            : 
      82                 :            :  public:
      83                 :    4014520 :   rtx reg () { return reg_pvt; }
      84                 :    1143380 :   void set_reg (rtx r) { reg_pvt = r; }
      85                 :            : };
      86                 :            : 
      87                 :            : /* For INSN, union all defs and uses that are linked by match_dup.
      88                 :            :    FUN is the function that does the union.  */
      89                 :            : 
      90                 :            : static void
      91                 :    2541400 : union_match_dups (rtx_insn *insn, web_entry *def_entry, web_entry *use_entry,
      92                 :            :                   bool (*fun) (web_entry_base *, web_entry_base *))
      93                 :            : {
      94                 :    2541400 :   struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
      95                 :    2541400 :   df_ref use_link = DF_INSN_INFO_USES (insn_info);
      96                 :    2541400 :   df_ref def_link = DF_INSN_INFO_DEFS (insn_info);
      97                 :    2541400 :   struct web_entry *dup_entry;
      98                 :    2541400 :   int i;
      99                 :            : 
     100                 :    2541400 :   extract_insn (insn);
     101                 :            : 
     102                 :    2579880 :   for (i = 0; i < recog_data.n_dups; i++)
     103                 :            :     {
     104                 :      38481 :       int op = recog_data.dup_num[i];
     105                 :      38481 :       enum op_type type = recog_data.operand_type[op];
     106                 :      38481 :       df_ref ref, dupref;
     107                 :      38481 :       struct web_entry *entry;
     108                 :            : 
     109                 :      38481 :       dup_entry = use_entry;
     110                 :     128431 :       for (dupref = use_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
     111                 :     109583 :         if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
     112                 :            :           break;
     113                 :            : 
     114                 :      38481 :       if (dupref == NULL && type == OP_INOUT)
     115                 :            :         {
     116                 :      10953 :           dup_entry = def_entry;
     117                 :      10953 :           for (dupref = def_link; dupref; dupref = DF_REF_NEXT_LOC (dupref))
     118                 :       6669 :             if (DF_REF_LOC (dupref) == recog_data.dup_loc[i])
     119                 :            :               break;
     120                 :            :         }
     121                 :            :       /* ??? *DUPREF can still be zero, because when an operand matches
     122                 :            :          a memory, DF_REF_LOC (use_link[n]) points to the register part
     123                 :            :          of the address, whereas recog_data.dup_loc[m] points to the
     124                 :            :          entire memory ref, thus we fail to find the duplicate entry,
     125                 :            :          even though it is there.
     126                 :            :          Example: i686-pc-linux-gnu gcc.c-torture/compile/950607-1.c
     127                 :            :                   -O3 -fomit-frame-pointer -funroll-loops  */
     128                 :      38481 :       if (dupref == NULL
     129                 :      19633 :           || DF_REF_REGNO (dupref) < FIRST_PSEUDO_REGISTER)
     130                 :      18848 :         continue;
     131                 :            : 
     132                 :      19633 :       ref = type == OP_IN ? use_link : def_link;
     133                 :      19633 :       entry = type == OP_IN ? use_entry : def_entry;
     134                 :      52308 :       for (; ref; ref = DF_REF_NEXT_LOC (ref))
     135                 :            :         {
     136                 :      52308 :           rtx *l = DF_REF_LOC (ref);
     137                 :      52308 :           if (l == recog_data.operand_loc[op])
     138                 :            :             break;
     139                 :      32675 :           if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
     140                 :            :             break;
     141                 :            :         }
     142                 :            : 
     143                 :      19633 :       if (!ref && type == OP_INOUT)
     144                 :            :         {
     145                 :          0 :           entry = use_entry;
     146                 :          0 :           for (ref = use_link; ref; ref = DF_REF_NEXT_LOC (ref))
     147                 :            :             {
     148                 :          0 :               rtx *l = DF_REF_LOC (ref);
     149                 :          0 :               if (l == recog_data.operand_loc[op])
     150                 :            :                 break;
     151                 :          0 :               if (l && DF_REF_REAL_LOC (ref) == recog_data.operand_loc[op])
     152                 :            :                 break;
     153                 :            :             }
     154                 :            :         }
     155                 :            : 
     156                 :      19633 :       gcc_assert (ref);
     157                 :      19633 :       (*fun) (dup_entry + DF_REF_ID (dupref), entry + DF_REF_ID (ref));
     158                 :            :     }
     159                 :    2541400 : }
     160                 :            : 
     161                 :            : /* For each use, all possible defs reaching it must come in the same
     162                 :            :    register, union them.
     163                 :            :    FUN is the function that does the union.
     164                 :            : 
     165                 :            :    In USED, we keep the DF_REF_ID of the first uninitialized uses of a
     166                 :            :    register, so that all uninitialized uses of the register can be
     167                 :            :    combined into a single web.  We actually offset it by 2, because
     168                 :            :    the values 0 and 1 are reserved for use by entry_register.  */
     169                 :            : 
     170                 :            : void
     171                 :    2669130 : union_defs (df_ref use, web_entry *def_entry,
     172                 :            :             unsigned int *used, web_entry *use_entry,
     173                 :            :             bool (*fun) (web_entry_base *, web_entry_base *))
     174                 :            : {
     175                 :    2669130 :   struct df_insn_info *insn_info = DF_REF_INSN_INFO (use);
     176                 :    2669130 :   struct df_link *link = DF_REF_CHAIN (use);
     177                 :    2669130 :   rtx set;
     178                 :            : 
     179                 :    2669130 :   if (insn_info)
     180                 :            :     {
     181                 :    2669130 :       df_ref eq_use;
     182                 :            : 
     183                 :    2669130 :       set = single_set (insn_info->insn);
     184                 :    2855420 :       FOR_EACH_INSN_INFO_EQ_USE (eq_use, insn_info)
     185                 :     186291 :         if (use != eq_use
     186                 :     145970 :             && DF_REF_REAL_REG (use) == DF_REF_REAL_REG (eq_use))
     187                 :      29783 :           (*fun) (use_entry + DF_REF_ID (use), use_entry + DF_REF_ID (eq_use));
     188                 :            :     }
     189                 :            :   else
     190                 :            :     set = NULL;
     191                 :            : 
     192                 :            :   /* Union all occurrences of the same register in reg notes.  */
     193                 :            : 
     194                 :            :   /* Recognize trivial noop moves and attempt to keep them as noop.  */
     195                 :            : 
     196                 :    2669130 :   if (set
     197                 :    2659170 :       && SET_SRC (set) == DF_REF_REG (use)
     198                 :     400444 :       && SET_SRC (set) == SET_DEST (set))
     199                 :            :     {
     200                 :          0 :       df_ref def;
     201                 :            : 
     202                 :          0 :       FOR_EACH_INSN_INFO_DEF (def, insn_info)
     203                 :          0 :         if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
     204                 :          0 :           (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
     205                 :            :     }
     206                 :            : 
     207                 :            :   /* UD chains of uninitialized REGs are empty.  Keeping all uses of
     208                 :            :      the same uninitialized REG in a single web is not necessary for
     209                 :            :      correctness, since the uses are undefined, but it's wasteful to
     210                 :            :      allocate one register or slot for each reference.  Furthermore,
     211                 :            :      creating new pseudos for uninitialized references in debug insns
     212                 :            :      (see PR 42631) causes -fcompare-debug failures.  We record the
     213                 :            :      number of the first uninitialized reference we found, and merge
     214                 :            :      with it any other uninitialized references to the same
     215                 :            :      register.  */
     216                 :    2669130 :   if (!link)
     217                 :            :     {
     218                 :       9362 :       int regno = REGNO (DF_REF_REAL_REG (use));
     219                 :       9362 :       if (used[regno])
     220                 :       6447 :         (*fun) (use_entry + DF_REF_ID (use), use_entry + used[regno] - 2);
     221                 :            :       else
     222                 :       2915 :         used[regno] = DF_REF_ID (use) + 2;
     223                 :            :     }
     224                 :            : 
     225                 :    6121940 :   while (link)
     226                 :            :     {
     227                 :    3452810 :       (*fun) (use_entry + DF_REF_ID (use),
     228                 :    3452810 :               def_entry + DF_REF_ID (link->ref));
     229                 :    3452810 :       link = link->next;
     230                 :            :     }
     231                 :            : 
     232                 :            :   /* A READ_WRITE use requires the corresponding def to be in the same
     233                 :            :      register.  Find it and union.  */
     234                 :    2669130 :   if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
     235                 :       4062 :     if (insn_info)
     236                 :            :       {
     237                 :       4062 :         df_ref def;
     238                 :            : 
     239                 :       8125 :         FOR_EACH_INSN_INFO_DEF (def, insn_info)
     240                 :       4063 :           if (DF_REF_REAL_REG (use) == DF_REF_REAL_REG (def))
     241                 :       4062 :             (*fun) (use_entry + DF_REF_ID (use), def_entry + DF_REF_ID (def));
     242                 :            :       }
     243                 :    2669130 : }
     244                 :            : 
     245                 :            : /* Find the corresponding register for the given entry.  */
     246                 :            : 
     247                 :            : static rtx
     248                 :    4014520 : entry_register (web_entry *entry, df_ref ref, unsigned int *used)
     249                 :            : {
     250                 :    4014520 :   web_entry *root;
     251                 :    4014520 :   rtx reg, newreg;
     252                 :            : 
     253                 :            :   /* Find the corresponding web and see if it has been visited.  */
     254                 :    4014520 :   root = (web_entry *)entry->unionfind_root ();
     255                 :    4014520 :   if (root->reg ())
     256                 :            :     return root->reg ();
     257                 :            : 
     258                 :            :   /* We are seeing this web for the first time, do the assignment.  */
     259                 :    1143380 :   reg = DF_REF_REAL_REG (ref);
     260                 :            : 
     261                 :            :   /* In case the original register is already assigned, generate new
     262                 :            :      one.  Since we use USED to merge uninitialized refs into a single
     263                 :            :      web, we might found an element to be nonzero without our having
     264                 :            :      used it.  Test for 1, because union_defs saves it for our use,
     265                 :            :      and there won't be any use for the other values when we get to
     266                 :            :      this point.  */
     267                 :    1143380 :   if (used[REGNO (reg)] != 1)
     268                 :     835758 :     newreg = reg, used[REGNO (reg)] = 1;
     269                 :            :   else
     270                 :            :     {
     271                 :     307619 :       newreg = gen_reg_rtx (GET_MODE (reg));
     272                 :     307619 :       REG_USERVAR_P (newreg) = REG_USERVAR_P (reg);
     273                 :     307619 :       REG_POINTER (newreg) = REG_POINTER (reg);
     274                 :     307619 :       REG_ATTRS (newreg) = REG_ATTRS (reg);
     275                 :     307619 :       if (dump_file)
     276                 :        146 :         fprintf (dump_file, "Web oldreg=%i newreg=%i\n", REGNO (reg),
     277                 :            :                  REGNO (newreg));
     278                 :            :     }
     279                 :            : 
     280                 :    1143380 :   root->set_reg (newreg);
     281                 :    1143380 :   return newreg;
     282                 :            : }
     283                 :            : 
     284                 :            : /* Replace the reference by REG.  */
     285                 :            : 
     286                 :            : static void
     287                 :    4014520 : replace_ref (df_ref ref, rtx reg)
     288                 :            : {
     289                 :    4014520 :   rtx oldreg = DF_REF_REAL_REG (ref);
     290                 :    4014520 :   rtx *loc = DF_REF_REAL_LOC (ref);
     291                 :    4014520 :   unsigned int uid = DF_REF_INSN_UID (ref);
     292                 :            : 
     293                 :    4014520 :   if (oldreg == reg)
     294                 :            :     return;
     295                 :     830218 :   if (dump_file)
     296                 :        428 :     fprintf (dump_file, "Updating insn %i (%i->%i)\n",
     297                 :            :              uid, REGNO (oldreg), REGNO (reg));
     298                 :     830218 :   *loc = reg;
     299                 :     830218 :   df_insn_rescan (DF_REF_INSN (ref));
     300                 :            : }
     301                 :            : 
     302                 :            : 
     303                 :            : namespace {
     304                 :            : 
     305                 :            : const pass_data pass_data_web =
     306                 :            : {
     307                 :            :   RTL_PASS, /* type */
     308                 :            :   "web", /* name */
     309                 :            :   OPTGROUP_NONE, /* optinfo_flags */
     310                 :            :   TV_WEB, /* tv_id */
     311                 :            :   0, /* properties_required */
     312                 :            :   0, /* properties_provided */
     313                 :            :   0, /* properties_destroyed */
     314                 :            :   0, /* todo_flags_start */
     315                 :            :   TODO_df_finish, /* todo_flags_finish */
     316                 :            : };
     317                 :            : 
     318                 :            : class pass_web : public rtl_opt_pass
     319                 :            : {
     320                 :            : public:
     321                 :     200773 :   pass_web (gcc::context *ctxt)
     322                 :     401546 :     : rtl_opt_pass (pass_data_web, ctxt)
     323                 :            :   {}
     324                 :            : 
     325                 :            :   /* opt_pass methods: */
     326                 :     944101 :   virtual bool gate (function *) { return (optimize > 0 && flag_web); }
     327                 :            :   virtual unsigned int execute (function *);
     328                 :            : 
     329                 :            : }; // class pass_web
     330                 :            : 
     331                 :            : unsigned int
     332                 :      15795 : pass_web::execute (function *fun)
     333                 :            : {
     334                 :      15795 :   web_entry *def_entry;
     335                 :      15795 :   web_entry *use_entry;
     336                 :      15795 :   unsigned int max = max_reg_num ();
     337                 :      15795 :   unsigned int *used;
     338                 :      15795 :   basic_block bb;
     339                 :      15795 :   unsigned int uses_num = 0;
     340                 :      15795 :   rtx_insn *insn;
     341                 :            : 
     342                 :      15795 :   df_set_flags (DF_NO_HARD_REGS + DF_EQ_NOTES);
     343                 :      15795 :   df_set_flags (DF_RD_PRUNE_DEAD_DEFS);
     344                 :      15795 :   df_chain_add_problem (DF_UD_CHAIN);
     345                 :      15795 :   df_analyze ();
     346                 :      15795 :   df_set_flags (DF_DEFER_INSN_RESCAN);
     347                 :            : 
     348                 :            :   /* Assign ids to the uses.  */
     349                 :     392184 :   FOR_ALL_BB_FN (bb, fun)
     350                 :    7730690 :     FOR_BB_INSNS (bb, insn)
     351                 :            :     {
     352                 :    3677150 :       if (NONDEBUG_INSN_P (insn))
     353                 :            :         {
     354                 :    2541400 :           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
     355                 :    2541400 :           df_ref use;
     356                 :    6089340 :           FOR_EACH_INSN_INFO_USE (use, insn_info)
     357                 :    3547950 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     358                 :    2628800 :               DF_REF_ID (use) = uses_num++;
     359                 :    2635500 :           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
     360                 :      94102 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     361                 :      40321 :               DF_REF_ID (use) = uses_num++;
     362                 :            :         }
     363                 :            :     }
     364                 :            : 
     365                 :            :   /* Record the number of uses and defs at the beginning of the optimization.  */
     366                 :      15795 :   def_entry = XCNEWVEC (web_entry, DF_DEFS_TABLE_SIZE ());
     367                 :      15795 :   used = XCNEWVEC (unsigned, max);
     368                 :      15795 :   use_entry = XCNEWVEC (web_entry, uses_num);
     369                 :            : 
     370                 :            :   /* Produce the web.  */
     371                 :     392184 :   FOR_ALL_BB_FN (bb, fun)
     372                 :    7730690 :     FOR_BB_INSNS (bb, insn)
     373                 :    3677150 :       if (NONDEBUG_INSN_P (insn))
     374                 :            :         {
     375                 :    2541400 :           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
     376                 :    2541400 :           df_ref use;
     377                 :    2541400 :           union_match_dups (insn, def_entry, use_entry, unionfind_union);
     378                 :    6089340 :           FOR_EACH_INSN_INFO_USE (use, insn_info)
     379                 :    3547950 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     380                 :    2628800 :               union_defs (use, def_entry, used, use_entry, unionfind_union);
     381                 :    2635500 :           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
     382                 :      94102 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     383                 :      40321 :               union_defs (use, def_entry, used, use_entry, unionfind_union);
     384                 :            :         }
     385                 :            : 
     386                 :            :   /* Update the instruction stream, allocating new registers for split pseudos
     387                 :            :      in progress.  */
     388                 :     392184 :   FOR_ALL_BB_FN (bb, fun)
     389                 :    7730690 :     FOR_BB_INSNS (bb, insn)
     390                 :    3677150 :       if (NONDEBUG_INSN_P (insn)
     391                 :            :           /* Ignore naked clobber.  For example, reg 134 in the second insn
     392                 :            :              of the following sequence will not be replaced.
     393                 :            : 
     394                 :            :                (insn (clobber (reg:SI 134)))
     395                 :            : 
     396                 :            :                (insn (set (reg:SI 0 r0) (reg:SI 134)))
     397                 :            : 
     398                 :            :              Thus the later passes can optimize them away.  */
     399                 :    3677150 :           && GET_CODE (PATTERN (insn)) != CLOBBER)
     400                 :            :         {
     401                 :    2540500 :           struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
     402                 :    2540500 :           df_ref def, use;
     403                 :    6088330 :           FOR_EACH_INSN_INFO_USE (use, insn_info)
     404                 :    3547830 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     405                 :    2628800 :               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
     406                 :            :                                                 use, used));
     407                 :    2634600 :           FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
     408                 :      94102 :             if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER)
     409                 :      40321 :               replace_ref (use, entry_register (use_entry + DF_REF_ID (use),
     410                 :            :                                                 use, used));
     411                 :   11939600 :           FOR_EACH_INSN_INFO_DEF (def, insn_info)
     412                 :    9399080 :             if (DF_REF_REGNO (def) >= FIRST_PSEUDO_REGISTER)
     413                 :    1345400 :               replace_ref (def, entry_register (def_entry + DF_REF_ID (def),
     414                 :            :                                                 def, used));
     415                 :            :         }
     416                 :            : 
     417                 :      15795 :   free (def_entry);
     418                 :      15795 :   free (use_entry);
     419                 :      15795 :   free (used);
     420                 :      15795 :   return 0;
     421                 :            : }
     422                 :            : 
     423                 :            : } // anon namespace
     424                 :            : 
     425                 :            : rtl_opt_pass *
     426                 :     200773 : make_pass_web (gcc::context *ctxt)
     427                 :            : {
     428                 :     200773 :   return new pass_web (ctxt);
     429                 :            : }

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.