LCOV - code coverage report
Current view: top level - gcc - tree-outof-ssa.c (source / functions) Hit Total Coverage
Test: gcc.info Lines: 485 520 93.3 %
Date: 2020-04-04 11:58:09 Functions: 34 35 97.1 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 0 0 -

           Branch data     Line data    Source code
       1                 :            : /* Convert a program in SSA form into Normal form.
       2                 :            :    Copyright (C) 2004-2020 Free Software Foundation, Inc.
       3                 :            :    Contributed by Andrew Macleod <amacleod@redhat.com>
       4                 :            : 
       5                 :            : This file is part of GCC.
       6                 :            : 
       7                 :            : GCC is free software; you can redistribute it and/or modify
       8                 :            : it under the terms of the GNU General Public License as published by
       9                 :            : the Free Software Foundation; either version 3, or (at your option)
      10                 :            : any later version.
      11                 :            : 
      12                 :            : GCC is distributed in the hope that it will be useful,
      13                 :            : but WITHOUT ANY WARRANTY; without even the implied warranty of
      14                 :            : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
      15                 :            : GNU General Public License 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                 :            : #include "config.h"
      22                 :            : #include "system.h"
      23                 :            : #include "coretypes.h"
      24                 :            : #include "backend.h"
      25                 :            : #include "rtl.h"
      26                 :            : #include "tree.h"
      27                 :            : #include "gimple.h"
      28                 :            : #include "cfghooks.h"
      29                 :            : #include "ssa.h"
      30                 :            : #include "tree-ssa.h"
      31                 :            : #include "memmodel.h"
      32                 :            : #include "emit-rtl.h"
      33                 :            : #include "gimple-pretty-print.h"
      34                 :            : #include "diagnostic-core.h"
      35                 :            : #include "tree-dfa.h"
      36                 :            : #include "stor-layout.h"
      37                 :            : #include "cfgrtl.h"
      38                 :            : #include "cfganal.h"
      39                 :            : #include "tree-eh.h"
      40                 :            : #include "gimple-iterator.h"
      41                 :            : #include "tree-cfg.h"
      42                 :            : #include "dumpfile.h"
      43                 :            : #include "tree-ssa-live.h"
      44                 :            : #include "tree-ssa-ter.h"
      45                 :            : #include "tree-ssa-coalesce.h"
      46                 :            : #include "tree-outof-ssa.h"
      47                 :            : #include "dojump.h"
      48                 :            : 
      49                 :            : /* FIXME: A lot of code here deals with expanding to RTL.  All that code
      50                 :            :    should be in cfgexpand.c.  */
      51                 :            : #include "explow.h"
      52                 :            : #include "expr.h"
      53                 :            : 
      54                 :            : /* Return TRUE if expression STMT is suitable for replacement.  */
      55                 :            : 
      56                 :            : bool
      57                 :   27910100 : ssa_is_replaceable_p (gimple *stmt)
      58                 :            : {
      59                 :   27910100 :   use_operand_p use_p;
      60                 :   27910100 :   tree def;
      61                 :   27910100 :   gimple *use_stmt;
      62                 :            : 
      63                 :            :   /* Only consider modify stmts.  */
      64                 :   27910100 :   if (!is_gimple_assign (stmt))
      65                 :            :     return false;
      66                 :            : 
      67                 :            :   /* If the statement may throw an exception, it cannot be replaced.  */
      68                 :   20614000 :   if (stmt_could_throw_p (cfun, stmt))
      69                 :            :     return false;
      70                 :            : 
      71                 :            :   /* Punt if there is more than 1 def.  */
      72                 :   19828500 :   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
      73                 :   19828500 :   if (!def)
      74                 :            :     return false;
      75                 :            : 
      76                 :            :   /* Only consider definitions which have a single use.  */
      77                 :   14597800 :   if (!single_imm_use (def, &use_p, &use_stmt))
      78                 :            :     return false;
      79                 :            : 
      80                 :            :   /* Used in this block, but at the TOP of the block, not the end.  */
      81                 :   12536500 :   if (gimple_code (use_stmt) == GIMPLE_PHI)
      82                 :            :     return false;
      83                 :            : 
      84                 :            :   /* There must be no VDEFs.  */
      85                 :   23513700 :   if (gimple_vdef (stmt))
      86                 :            :     return false;
      87                 :            : 
      88                 :            :   /* Float expressions must go through memory if float-store is on.  */
      89                 :   11756800 :   if (flag_float_store
      90                 :   11756800 :       && FLOAT_TYPE_P (gimple_expr_type (stmt)))
      91                 :        331 :     return false;
      92                 :            : 
      93                 :            :   /* An assignment with a register variable on the RHS is not
      94                 :            :      replaceable.  */
      95                 :   11756500 :   if (gimple_assign_rhs_code (stmt) == VAR_DECL
      96                 :   12347400 :       && DECL_HARD_REGISTER (gimple_assign_rhs1 (stmt)))
      97                 :            :     return false;
      98                 :            : 
      99                 :            :   /* No function calls can be replaced.  */
     100                 :   11756100 :   if (is_gimple_call (stmt))
     101                 :            :     return false;
     102                 :            : 
     103                 :            :   /* Leave any stmt with volatile operands alone as well.  */
     104                 :   23512200 :   if (gimple_has_volatile_ops (stmt))
     105                 :     238318 :     return false;
     106                 :            : 
     107                 :            :   return true;
     108                 :            : }
     109                 :            : 
     110                 :            : 
     111                 :            : /* Used to hold all the components required to do SSA PHI elimination.
     112                 :            :    The node and pred/succ list is a simple linear list of nodes and
     113                 :            :    edges represented as pairs of nodes.
     114                 :            : 
     115                 :            :    The predecessor and successor list:  Nodes are entered in pairs, where
     116                 :            :    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
     117                 :            :    predecessors, all the odd elements are successors.
     118                 :            : 
     119                 :            :    Rationale:
     120                 :            :    When implemented as bitmaps, very large programs SSA->Normal times were
     121                 :            :    being dominated by clearing the interference graph.
     122                 :            : 
     123                 :            :    Typically this list of edges is extremely small since it only includes
     124                 :            :    PHI results and uses from a single edge which have not coalesced with
     125                 :            :    each other.  This means that no virtual PHI nodes are included, and
     126                 :            :    empirical evidence suggests that the number of edges rarely exceed
     127                 :            :    3, and in a bootstrap of GCC, the maximum size encountered was 7.
     128                 :            :    This also limits the number of possible nodes that are involved to
     129                 :            :    rarely more than 6, and in the bootstrap of gcc, the maximum number
     130                 :            :    of nodes encountered was 12.  */
     131                 :            : 
     132                 :            : class elim_graph
     133                 :            : {
     134                 :            : public:
     135                 :            :   elim_graph (var_map map);
     136                 :            : 
     137                 :            :   /* Size of the elimination vectors.  */
     138                 :            :   int size;
     139                 :            : 
     140                 :            :   /* List of nodes in the elimination graph.  */
     141                 :            :   auto_vec<int> nodes;
     142                 :            : 
     143                 :            :   /*  The predecessor and successor edge list.  */
     144                 :            :   auto_vec<int> edge_list;
     145                 :            : 
     146                 :            :   /* Source locus on each edge */
     147                 :            :   auto_vec<location_t> edge_locus;
     148                 :            : 
     149                 :            :   /* Visited vector.  */
     150                 :            :   auto_sbitmap visited;
     151                 :            : 
     152                 :            :   /* Stack for visited nodes.  */
     153                 :            :   auto_vec<int> stack;
     154                 :            : 
     155                 :            :   /* The variable partition map.  */
     156                 :            :   var_map map;
     157                 :            : 
     158                 :            :   /* Edge being eliminated by this graph.  */
     159                 :            :   edge e;
     160                 :            : 
     161                 :            :   /* List of constant copies to emit.  These are pushed on in pairs.  */
     162                 :            :   auto_vec<int> const_dests;
     163                 :            :   auto_vec<tree> const_copies;
     164                 :            : 
     165                 :            :   /* Source locations for any constant copies.  */
     166                 :            :   auto_vec<location_t> copy_locus;
     167                 :            : };
     168                 :            : 
     169                 :            : 
     170                 :            : /* For an edge E find out a good source location to associate with
     171                 :            :    instructions inserted on edge E.  If E has an implicit goto set,
     172                 :            :    use its location.  Otherwise search instructions in predecessors
     173                 :            :    of E for a location, and use that one.  That makes sense because
     174                 :            :    we insert on edges for PHI nodes, and effects of PHIs happen on
     175                 :            :    the end of the predecessor conceptually.  An exception is made
     176                 :            :    for EH edges because we don't want to drag the source location
     177                 :            :    of unrelated statements at the beginning of handlers; they would
     178                 :            :    be further reused for various EH constructs, which would damage
     179                 :            :    the coverage information.  */
     180                 :            : 
     181                 :            : static void
     182                 :     883513 : set_location_for_edge (edge e)
     183                 :            : {
     184                 :     883513 :   if (e->goto_locus)
     185                 :     323181 :     set_curr_insn_location (e->goto_locus);
     186                 :     560332 :   else if (e->flags & EDGE_EH)
     187                 :            :     {
     188                 :      19453 :       basic_block bb = e->dest;
     189                 :      19548 :       gimple_stmt_iterator gsi;
     190                 :            : 
     191                 :      19548 :       do
     192                 :            :         {
     193                 :     337264 :           for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     194                 :            :             {
     195                 :     317621 :               gimple *stmt = gsi_stmt (gsi);
     196                 :     317621 :               if (is_gimple_debug (stmt))
     197                 :     149040 :                 continue;
     198                 :     196706 :               if (gimple_has_location (stmt) || gimple_block (stmt))
     199                 :            :                 {
     200                 :      19453 :                   set_curr_insn_location (gimple_location (stmt));
     201                 :      19453 :                   return;
     202                 :            :                 }
     203                 :            :             }
     204                 :            :           /* Nothing found in this basic block.  Make a half-assed attempt
     205                 :            :              to continue with another block.  */
     206                 :         95 :           if (single_succ_p (bb))
     207                 :         95 :             bb = single_succ (bb);
     208                 :            :           else
     209                 :          0 :             bb = e->dest;
     210                 :            :         }
     211                 :         95 :       while (bb != e->dest);
     212                 :            :     }
     213                 :            :   else
     214                 :            :     {
     215                 :     540879 :       basic_block bb = e->src;
     216                 :     740884 :       gimple_stmt_iterator gsi;
     217                 :            : 
     218                 :     740884 :       do
     219                 :            :         {
     220                 :    4618620 :           for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi); gsi_prev (&gsi))
     221                 :            :             {
     222                 :    2020880 :               gimple *stmt = gsi_stmt (gsi);
     223                 :    2020880 :               if (is_gimple_debug (stmt))
     224                 :     571032 :                 continue;
     225                 :    1914010 :               if (gimple_has_location (stmt) || gimple_block (stmt))
     226                 :            :                 {
     227                 :     452458 :                   set_curr_insn_location (gimple_location (stmt));
     228                 :     452458 :                   return;
     229                 :            :                 }
     230                 :            :             }
     231                 :            :           /* Nothing found in this basic block.  Make a half-assed attempt
     232                 :            :              to continue with another block.  */
     233                 :     288426 :           if (single_pred_p (bb))
     234                 :     200005 :             bb = single_pred (bb);
     235                 :            :           else
     236                 :      88421 :             bb = e->src;
     237                 :            :         }
     238                 :     288426 :       while (bb != e->src);
     239                 :            :     }
     240                 :            : }
     241                 :            : 
     242                 :            : /* Emit insns to copy SRC into DEST converting SRC if necessary.  As
     243                 :            :    SRC/DEST might be BLKmode memory locations SIZEEXP is a tree from
     244                 :            :    which we deduce the size to copy in that case.  */
     245                 :            : 
     246                 :            : static inline rtx_insn *
     247                 :     239351 : emit_partition_copy (rtx dest, rtx src, int unsignedsrcp, tree sizeexp)
     248                 :            : {
     249                 :     239351 :   start_sequence ();
     250                 :            : 
     251                 :     239351 :   if (GET_MODE (src) != VOIDmode && GET_MODE (src) != GET_MODE (dest))
     252                 :          0 :     src = convert_to_mode (GET_MODE (dest), src, unsignedsrcp);
     253                 :     239351 :   if (GET_MODE (src) == BLKmode)
     254                 :            :     {
     255                 :         11 :       gcc_assert (GET_MODE (dest) == BLKmode);
     256                 :         11 :       emit_block_move (dest, src, expr_size (sizeexp), BLOCK_OP_NORMAL);
     257                 :            :     }
     258                 :            :   else
     259                 :     239340 :     emit_move_insn (dest, src);
     260                 :     239351 :   do_pending_stack_adjust ();
     261                 :            : 
     262                 :     239351 :   rtx_insn *seq = get_insns ();
     263                 :     239351 :   end_sequence ();
     264                 :            : 
     265                 :     239351 :   return seq;
     266                 :            : }
     267                 :            : 
     268                 :            : /* Insert a copy instruction from partition SRC to DEST onto edge E.  */
     269                 :            : 
     270                 :            : static void
     271                 :     236031 : insert_partition_copy_on_edge (edge e, int dest, int src, location_t locus)
     272                 :            : {
     273                 :     236031 :   tree var;
     274                 :     236031 :   if (dump_file && (dump_flags & TDF_DETAILS))
     275                 :            :     {
     276                 :          0 :       fprintf (dump_file,
     277                 :            :                "Inserting a partition copy on edge BB%d->BB%d : "
     278                 :            :                "PART.%d = PART.%d",
     279                 :          0 :                e->src->index,
     280                 :          0 :                e->dest->index, dest, src);
     281                 :          0 :       fprintf (dump_file, "\n");
     282                 :            :     }
     283                 :            : 
     284                 :     236031 :   gcc_assert (SA.partition_to_pseudo[dest]);
     285                 :     236031 :   gcc_assert (SA.partition_to_pseudo[src]);
     286                 :            : 
     287                 :     236031 :   set_location_for_edge (e);
     288                 :            :   /* If a locus is provided, override the default.  */
     289                 :     236031 :   if (locus)
     290                 :      73944 :     set_curr_insn_location (locus);
     291                 :            : 
     292                 :     236031 :   var = partition_to_var (SA.map, src);
     293                 :     472062 :   rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]),
     294                 :     236031 :                                        copy_rtx (SA.partition_to_pseudo[src]),
     295                 :     236031 :                                        TYPE_UNSIGNED (TREE_TYPE (var)),
     296                 :            :                                        var);
     297                 :            : 
     298                 :     236031 :   insert_insn_on_edge (seq, e);
     299                 :     236031 : }
     300                 :            : 
     301                 :            : /* Insert a copy instruction from expression SRC to partition DEST
     302                 :            :    onto edge E.  */
     303                 :            : 
     304                 :            : static void
     305                 :     644162 : insert_value_copy_on_edge (edge e, int dest, tree src, location_t locus)
     306                 :            : {
     307                 :     644162 :   rtx dest_rtx, seq, x;
     308                 :     644162 :   machine_mode dest_mode, src_mode;
     309                 :     644162 :   int unsignedp;
     310                 :            : 
     311                 :     644162 :   if (dump_file && (dump_flags & TDF_DETAILS))
     312                 :            :     {
     313                 :         10 :       fprintf (dump_file,
     314                 :            :                "Inserting a value copy on edge BB%d->BB%d : PART.%d = ",
     315                 :         10 :                e->src->index,
     316                 :         10 :                e->dest->index, dest);
     317                 :         10 :       print_generic_expr (dump_file, src, TDF_SLIM);
     318                 :         10 :       fprintf (dump_file, "\n");
     319                 :            :     }
     320                 :            : 
     321                 :     644162 :   dest_rtx = copy_rtx (SA.partition_to_pseudo[dest]);
     322                 :     644162 :   gcc_assert (dest_rtx);
     323                 :            : 
     324                 :     644162 :   set_location_for_edge (e);
     325                 :            :   /* If a locus is provided, override the default.  */
     326                 :     644162 :   if (locus)
     327                 :     384684 :     set_curr_insn_location (locus);
     328                 :            : 
     329                 :     644162 :   start_sequence ();
     330                 :            : 
     331                 :     644162 :   tree name = partition_to_var (SA.map, dest);
     332                 :     644162 :   src_mode = TYPE_MODE (TREE_TYPE (src));
     333                 :     644162 :   dest_mode = GET_MODE (dest_rtx);
     334                 :     644162 :   gcc_assert (src_mode == TYPE_MODE (TREE_TYPE (name)));
     335                 :     644162 :   gcc_assert (!REG_P (dest_rtx)
     336                 :            :               || dest_mode == promote_ssa_mode (name, &unsignedp));
     337                 :            : 
     338                 :     644162 :   if (src_mode != dest_mode)
     339                 :            :     {
     340                 :          0 :       x = expand_expr (src, NULL, src_mode, EXPAND_NORMAL);
     341                 :          0 :       x = convert_modes (dest_mode, src_mode, x, unsignedp);
     342                 :            :     }
     343                 :     644162 :   else if (src_mode == BLKmode)
     344                 :            :     {
     345                 :         74 :       x = dest_rtx;
     346                 :         74 :       store_expr (src, x, 0, false, false);
     347                 :            :     }
     348                 :            :   else
     349                 :     644088 :     x = expand_expr (src, dest_rtx, dest_mode, EXPAND_NORMAL);
     350                 :            : 
     351                 :     644162 :   if (x != dest_rtx)
     352                 :     628104 :     emit_move_insn (dest_rtx, x);
     353                 :     644162 :   do_pending_stack_adjust ();
     354                 :            : 
     355                 :     644162 :   seq = get_insns ();
     356                 :     644162 :   end_sequence ();
     357                 :            : 
     358                 :     644162 :   insert_insn_on_edge (seq, e);
     359                 :     644162 : }
     360                 :            : 
     361                 :            : /* Insert a copy instruction from RTL expression SRC to partition DEST
     362                 :            :    onto edge E.  */
     363                 :            : 
     364                 :            : static void
     365                 :       1660 : insert_rtx_to_part_on_edge (edge e, int dest, rtx src, int unsignedsrcp,
     366                 :            :                             location_t locus)
     367                 :            : {
     368                 :       1660 :   if (dump_file && (dump_flags & TDF_DETAILS))
     369                 :            :     {
     370                 :          0 :       fprintf (dump_file,
     371                 :            :                "Inserting a temp copy on edge BB%d->BB%d : PART.%d = ",
     372                 :          0 :                e->src->index,
     373                 :          0 :                e->dest->index, dest);
     374                 :          0 :       print_simple_rtl (dump_file, src);
     375                 :          0 :       fprintf (dump_file, "\n");
     376                 :            :     }
     377                 :            : 
     378                 :       1660 :   gcc_assert (SA.partition_to_pseudo[dest]);
     379                 :            : 
     380                 :       1660 :   set_location_for_edge (e);
     381                 :            :   /* If a locus is provided, override the default.  */
     382                 :       1660 :   if (locus)
     383                 :        889 :     set_curr_insn_location (locus);
     384                 :            : 
     385                 :            :   /* We give the destination as sizeexp in case src/dest are BLKmode
     386                 :            :      mems.  Usually we give the source.  As we result from SSA names
     387                 :            :      the left and right size should be the same (and no WITH_SIZE_EXPR
     388                 :            :      involved), so it doesn't matter.  */
     389                 :       1660 :   rtx_insn *seq = emit_partition_copy (copy_rtx (SA.partition_to_pseudo[dest]),
     390                 :            :                                        src, unsignedsrcp,
     391                 :            :                                        partition_to_var (SA.map, dest));
     392                 :            : 
     393                 :       1660 :   insert_insn_on_edge (seq, e);
     394                 :       1660 : }
     395                 :            : 
     396                 :            : /* Insert a copy instruction from partition SRC to RTL lvalue DEST
     397                 :            :    onto edge E.  */
     398                 :            : 
     399                 :            : static void
     400                 :       1660 : insert_part_to_rtx_on_edge (edge e, rtx dest, int src, location_t locus)
     401                 :            : {
     402                 :       1660 :   tree var;
     403                 :       1660 :   if (dump_file && (dump_flags & TDF_DETAILS))
     404                 :            :     {
     405                 :          0 :       fprintf (dump_file,
     406                 :            :                "Inserting a temp copy on edge BB%d->BB%d : ",
     407                 :          0 :                e->src->index,
     408                 :          0 :                e->dest->index);
     409                 :          0 :       print_simple_rtl (dump_file, dest);
     410                 :          0 :       fprintf (dump_file, "= PART.%d\n", src);
     411                 :            :     }
     412                 :            : 
     413                 :       1660 :   gcc_assert (SA.partition_to_pseudo[src]);
     414                 :            : 
     415                 :       1660 :   set_location_for_edge (e);
     416                 :            :   /* If a locus is provided, override the default.  */
     417                 :       1660 :   if (locus)
     418                 :          0 :     set_curr_insn_location (locus);
     419                 :            : 
     420                 :       1660 :   var = partition_to_var (SA.map, src);
     421                 :       3320 :   rtx_insn *seq = emit_partition_copy (dest,
     422                 :       1660 :                                        copy_rtx (SA.partition_to_pseudo[src]),
     423                 :       1660 :                                        TYPE_UNSIGNED (TREE_TYPE (var)),
     424                 :            :                                        var);
     425                 :            : 
     426                 :       1660 :   insert_insn_on_edge (seq, e);
     427                 :       1660 : }
     428                 :            : 
     429                 :            : 
     430                 :            : /* Create an elimination graph for map.  */
     431                 :            : 
     432                 :     944512 : elim_graph::elim_graph (var_map map) :
     433                 :            :   nodes (30), edge_list (20), edge_locus (10), visited (map->num_partitions),
     434                 :     944512 :   stack (30), map (map), const_dests (20), const_copies (20), copy_locus (10)
     435                 :            : {
     436                 :     944512 : }
     437                 :            : 
     438                 :            : 
     439                 :            : /* Empty elimination graph G.  */
     440                 :            : 
     441                 :            : static inline void
     442                 :    2067500 : clear_elim_graph (elim_graph *g)
     443                 :            : {
     444                 :    2067500 :   g->nodes.truncate (0);
     445                 :    2067500 :   g->edge_list.truncate (0);
     446                 :    2067500 :   g->edge_locus.truncate (0);
     447                 :    2067500 : }
     448                 :            : 
     449                 :            : 
     450                 :            : /* Return the number of nodes in graph G.  */
     451                 :            : 
     452                 :            : static inline int
     453                 :    2067500 : elim_graph_size (elim_graph *g)
     454                 :            : {
     455                 :    2067500 :   return g->nodes.length ();
     456                 :            : }
     457                 :            : 
     458                 :            : 
     459                 :            : /* Add NODE to graph G, if it doesn't exist already.  */
     460                 :            : 
     461                 :            : static inline void
     462                 :     475382 : elim_graph_add_node (elim_graph *g, int node)
     463                 :            : {
     464                 :     475382 :   int x;
     465                 :     475382 :   int t;
     466                 :            : 
     467                 :     963645 :   FOR_EACH_VEC_ELT (g->nodes, x, t)
     468                 :     505150 :     if (t == node)
     469                 :     475382 :       return;
     470                 :     458495 :   g->nodes.safe_push (node);
     471                 :            : }
     472                 :            : 
     473                 :            : 
     474                 :            : /* Add the edge PRED->SUCC to graph G.  */
     475                 :            : 
     476                 :            : static inline void
     477                 :     237691 : elim_graph_add_edge (elim_graph *g, int pred, int succ, location_t locus)
     478                 :            : {
     479                 :     237691 :   g->edge_list.safe_push (pred);
     480                 :     237691 :   g->edge_list.safe_push (succ);
     481                 :     237691 :   g->edge_locus.safe_push (locus);
     482                 :     237691 : }
     483                 :            : 
     484                 :            : 
     485                 :            : /* Remove an edge from graph G for which NODE is the predecessor, and
     486                 :            :    return the successor node.  -1 is returned if there is no such edge.  */
     487                 :            : 
     488                 :            : static inline int
     489                 :     455173 : elim_graph_remove_succ_edge (elim_graph *g, int node, location_t *locus)
     490                 :            : {
     491                 :     455173 :   int y;
     492                 :     455173 :   unsigned x;
     493                 :    1738360 :   for (x = 0; x < g->edge_list.length (); x += 2)
     494                 :     648376 :     if (g->edge_list[x] == node)
     495                 :            :       {
     496                 :     234369 :         g->edge_list[x] = -1;
     497                 :     234369 :         y = g->edge_list[x + 1];
     498                 :     234369 :         g->edge_list[x + 1] = -1;
     499                 :     234369 :         *locus = g->edge_locus[x / 2];
     500                 :     234369 :         g->edge_locus[x / 2] = UNKNOWN_LOCATION;
     501                 :     234369 :         return y;
     502                 :            :       }
     503                 :     220804 :   *locus = UNKNOWN_LOCATION;
     504                 :     220804 :   return -1;
     505                 :            : }
     506                 :            : 
     507                 :            : 
     508                 :            : /* Find all the nodes in GRAPH which are successors to NODE in the
     509                 :            :    edge list.  VAR will hold the partition number found.  CODE is the
     510                 :            :    code fragment executed for every node found.  */
     511                 :            : 
     512                 :            : #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, LOCUS, CODE)         \
     513                 :            : do {                                                                    \
     514                 :            :   unsigned x_;                                                          \
     515                 :            :   int y_;                                                               \
     516                 :            :   for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2)        \
     517                 :            :     {                                                                   \
     518                 :            :       y_ = (GRAPH)->edge_list[x_];                                   \
     519                 :            :       if (y_ != (NODE))                                                 \
     520                 :            :         continue;                                                       \
     521                 :            :       (void) ((VAR) = (GRAPH)->edge_list[x_ + 1]);                   \
     522                 :            :       (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]);                        \
     523                 :            :       CODE;                                                             \
     524                 :            :     }                                                                   \
     525                 :            : } while (0)
     526                 :            : 
     527                 :            : 
     528                 :            : /* Find all the nodes which are predecessors of NODE in the edge list for
     529                 :            :    GRAPH.  VAR will hold the partition number found.  CODE is the
     530                 :            :    code fragment executed for every node found.  */
     531                 :            : 
     532                 :            : #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, LOCUS, CODE)         \
     533                 :            : do {                                                                    \
     534                 :            :   unsigned x_;                                                          \
     535                 :            :   int y_;                                                               \
     536                 :            :   for (x_ = 0; x_ < (GRAPH)->edge_list.length (); x_ += 2)        \
     537                 :            :     {                                                                   \
     538                 :            :       y_ = (GRAPH)->edge_list[x_ + 1];                                       \
     539                 :            :       if (y_ != (NODE))                                                 \
     540                 :            :         continue;                                                       \
     541                 :            :       (void) ((VAR) = (GRAPH)->edge_list[x_]);                               \
     542                 :            :       (void) ((LOCUS) = (GRAPH)->edge_locus[x_ / 2]);                        \
     543                 :            :       CODE;                                                             \
     544                 :            :     }                                                                   \
     545                 :            : } while (0)
     546                 :            : 
     547                 :            : 
     548                 :            : /* Add T to elimination graph G.  */
     549                 :            : 
     550                 :            : static inline void
     551                 :     475382 : eliminate_name (elim_graph *g, int T)
     552                 :            : {
     553                 :     475382 :   elim_graph_add_node (g, T);
     554                 :            : }
     555                 :            : 
     556                 :            : /* Return true if this phi argument T should have a copy queued when using
     557                 :            :    var_map MAP.  PHI nodes should contain only ssa_names and invariants.  A
     558                 :            :    test for ssa_name is definitely simpler, but don't let invalid contents
     559                 :            :    slip through in the meantime.  */
     560                 :            : 
     561                 :            : static inline bool
     562                 :    3647460 : queue_phi_copy_p (var_map map, tree t)
     563                 :            : {
     564                 :    3647460 :   if (TREE_CODE (t) == SSA_NAME)
     565                 :            :     { 
     566                 :    3003300 :       if (var_to_partition (map, t) == NO_PARTITION)
     567                 :            :         return true;
     568                 :    3003300 :       return false;
     569                 :            :     }
     570                 :     644162 :   gcc_checking_assert (is_gimple_min_invariant (t));
     571                 :            :   return true;
     572                 :            : }
     573                 :            : 
     574                 :            : /* Build elimination graph G for basic block BB on incoming PHI edge
     575                 :            :    G->e.  */
     576                 :            : 
     577                 :            : static void
     578                 :    2067500 : eliminate_build (elim_graph *g)
     579                 :            : {
     580                 :    2067500 :   tree Ti;
     581                 :    2067500 :   int p0, pi;
     582                 :    2067500 :   gphi_iterator gsi;
     583                 :            : 
     584                 :    2067500 :   clear_elim_graph (g);
     585                 :            : 
     586                 :    5714960 :   for (gsi = gsi_start_phis (g->e->dest); !gsi_end_p (gsi); gsi_next (&gsi))
     587                 :            :     {
     588                 :    3647460 :       gphi *phi = gsi.phi ();
     589                 :    3647460 :       location_t locus;
     590                 :            : 
     591                 :    3647460 :       p0 = var_to_partition (g->map, gimple_phi_result (phi));
     592                 :            :       /* Ignore results which are not in partitions.  */
     593                 :    3647460 :       if (p0 == NO_PARTITION)
     594                 :          0 :         continue;
     595                 :            : 
     596                 :    3647460 :       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
     597                 :            :       /* See set_location_for_edge for the rationale.  */
     598                 :    3647460 :       if (g->e->flags & EDGE_EH)
     599                 :      45731 :         locus = UNKNOWN_LOCATION;
     600                 :            :       else
     601                 :    3601730 :         locus = gimple_phi_arg_location_from_edge (phi, g->e);
     602                 :            : 
     603                 :            :       /* If this argument is a constant, or a SSA_NAME which is being
     604                 :            :          left in SSA form, just queue a copy to be emitted on this
     605                 :            :          edge.  */
     606                 :    3647460 :       if (queue_phi_copy_p (g->map, Ti))
     607                 :            :         {
     608                 :            :           /* Save constant copies until all other copies have been emitted
     609                 :            :              on this edge.  */
     610                 :     644162 :           g->const_dests.safe_push (p0);
     611                 :     644162 :           g->const_copies.safe_push (Ti);
     612                 :     644162 :           g->copy_locus.safe_push (locus);
     613                 :            :         }
     614                 :            :       else
     615                 :            :         {
     616                 :    3003300 :           pi = var_to_partition (g->map, Ti);
     617                 :    3003300 :           if (p0 != pi)
     618                 :            :             {
     619                 :     237691 :               eliminate_name (g, p0);
     620                 :     237691 :               eliminate_name (g, pi);
     621                 :     237691 :               elim_graph_add_edge (g, p0, pi, locus);
     622                 :            :             }
     623                 :            :         }
     624                 :            :     }
     625                 :    2067500 : }
     626                 :            : 
     627                 :            : 
     628                 :            : /* Push successors of T onto the elimination stack for G.  */
     629                 :            : 
     630                 :            : static void
     631                 :     458495 : elim_forward (elim_graph *g, int T)
     632                 :            : {
     633                 :     458495 :   int S;
     634                 :     458495 :   location_t locus;
     635                 :            : 
     636                 :     458495 :   bitmap_set_bit (g->visited, T);
     637                 :    1652270 :   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, locus,
     638                 :            :     {
     639                 :            :       if (!bitmap_bit_p (g->visited, S))
     640                 :            :         elim_forward (g, S);
     641                 :            :     });
     642                 :     458495 :   g->stack.safe_push (T);
     643                 :     458495 : }
     644                 :            : 
     645                 :            : 
     646                 :            : /* Return 1 if there unvisited predecessors of T in graph G.  */
     647                 :            : 
     648                 :            : static int
     649                 :     456833 : elim_unvisited_predecessor (elim_graph *g, int T)
     650                 :            : {
     651                 :     456833 :   int P;
     652                 :     456833 :   location_t locus;
     653                 :            : 
     654                 :    1636340 :   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
     655                 :            :     {
     656                 :            :       if (!bitmap_bit_p (g->visited, P))
     657                 :            :         return 1;
     658                 :            :     });
     659                 :            :   return 0;
     660                 :            : }
     661                 :            : 
     662                 :            : /* Process predecessors first, and insert a copy.  */
     663                 :            : 
     664                 :            : static void
     665                 :       3322 : elim_backward (elim_graph *g, int T)
     666                 :            : {
     667                 :       3322 :   int P;
     668                 :       3322 :   location_t locus;
     669                 :            : 
     670                 :       3322 :   bitmap_set_bit (g->visited, T);
     671                 :      22882 :   FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
     672                 :            :     {
     673                 :            :       if (!bitmap_bit_p (g->visited, P))
     674                 :            :         {
     675                 :            :           elim_backward (g, P);
     676                 :            :           insert_partition_copy_on_edge (g->e, P, T, locus);
     677                 :            :         }
     678                 :            :     });
     679                 :       3322 : }
     680                 :            : 
     681                 :            : /* Allocate a new pseudo register usable for storing values sitting
     682                 :            :    in NAME (a decl or SSA name), i.e. with matching mode and attributes.  */
     683                 :            : 
     684                 :            : static rtx
     685                 :       1660 : get_temp_reg (tree name)
     686                 :            : {
     687                 :       1660 :   tree type = TREE_TYPE (name);
     688                 :       1660 :   int unsignedp;
     689                 :       1660 :   machine_mode reg_mode = promote_ssa_mode (name, &unsignedp);
     690                 :       1660 :   if (reg_mode == BLKmode)
     691                 :          1 :     return assign_temp (type, 0, 0);
     692                 :       1659 :   rtx x = gen_reg_rtx (reg_mode);
     693                 :       1659 :   if (POINTER_TYPE_P (type))
     694                 :        227 :     mark_reg_pointer (x, TYPE_ALIGN (TREE_TYPE (type)));
     695                 :            :   return x;
     696                 :            : }
     697                 :            : 
     698                 :            : /* Insert required copies for T in graph G.  Check for a strongly connected
     699                 :            :    region, and create a temporary to break the cycle if one is found.  */
     700                 :            : 
     701                 :            : static void
     702                 :     456833 : elim_create (elim_graph *g, int T)
     703                 :            : {
     704                 :     456833 :   int P, S;
     705                 :     456833 :   location_t locus;
     706                 :            : 
     707                 :     456833 :   if (elim_unvisited_predecessor (g, T))
     708                 :            :     {
     709                 :       1660 :       tree var = partition_to_var (g->map, T);
     710                 :       1660 :       rtx U = get_temp_reg (var);
     711                 :       1660 :       int unsignedsrcp = TYPE_UNSIGNED (TREE_TYPE (var));
     712                 :            : 
     713                 :       1660 :       insert_part_to_rtx_on_edge (g->e, U, T, UNKNOWN_LOCATION);
     714                 :      11436 :       FOR_EACH_ELIM_GRAPH_PRED (g, T, P, locus,
     715                 :            :         {
     716                 :            :           if (!bitmap_bit_p (g->visited, P))
     717                 :            :             {
     718                 :            :               elim_backward (g, P);
     719                 :            :               insert_rtx_to_part_on_edge (g->e, P, U, unsignedsrcp, locus);
     720                 :            :             }
     721                 :            :         });
     722                 :            :     }
     723                 :            :   else
     724                 :            :     {
     725                 :     455173 :       S = elim_graph_remove_succ_edge (g, T, &locus);
     726                 :     455173 :       if (S != -1)
     727                 :            :         {
     728                 :     234369 :           bitmap_set_bit (g->visited, T);
     729                 :     234369 :           insert_partition_copy_on_edge (g->e, T, S, locus);
     730                 :            :         }
     731                 :            :     }
     732                 :     456833 : }
     733                 :            : 
     734                 :            : 
     735                 :            : /* Eliminate all the phi nodes on edge E in graph G.  */
     736                 :            : 
     737                 :            : static void
     738                 :    2070840 : eliminate_phi (edge e, elim_graph *g)
     739                 :            : {
     740                 :    2070840 :   int x;
     741                 :            : 
     742                 :    2070840 :   gcc_assert (g->const_copies.length () == 0);
     743                 :    2070840 :   gcc_assert (g->copy_locus.length () == 0);
     744                 :            : 
     745                 :            :   /* Abnormal edges already have everything coalesced.  */
     746                 :    2070840 :   if (e->flags & EDGE_ABNORMAL)
     747                 :            :     return;
     748                 :            : 
     749                 :    2067500 :   g->e = e;
     750                 :            : 
     751                 :    2067500 :   eliminate_build (g);
     752                 :            : 
     753                 :    2067500 :   if (elim_graph_size (g) != 0)
     754                 :            :     {
     755                 :     189191 :       int part;
     756                 :            : 
     757                 :     189191 :       bitmap_clear (g->visited);
     758                 :     189191 :       g->stack.truncate (0);
     759                 :            : 
     760                 :     647686 :       FOR_EACH_VEC_ELT (g->nodes, x, part)
     761                 :            :         {
     762                 :     458495 :           if (!bitmap_bit_p (g->visited, part))
     763                 :     232072 :             elim_forward (g, part);
     764                 :            :         }
     765                 :            : 
     766                 :     189191 :       bitmap_clear (g->visited);
     767                 :     647686 :       while (g->stack.length () > 0)
     768                 :            :         {
     769                 :     458495 :           x = g->stack.pop ();
     770                 :     458495 :           if (!bitmap_bit_p (g->visited, x))
     771                 :     456833 :             elim_create (g, x);
     772                 :            :         }
     773                 :            :     }
     774                 :            : 
     775                 :            :   /* If there are any pending constant copies, issue them now.  */
     776                 :    2711670 :   while (g->const_copies.length () > 0)
     777                 :            :     {
     778                 :     644162 :       int dest;
     779                 :     644162 :       tree src;
     780                 :     644162 :       location_t locus;
     781                 :            : 
     782                 :     644162 :       src = g->const_copies.pop ();
     783                 :     644162 :       dest = g->const_dests.pop ();
     784                 :     644162 :       locus = g->copy_locus.pop ();
     785                 :     644162 :       insert_value_copy_on_edge (e, dest, src, locus);
     786                 :            :     }
     787                 :            : }
     788                 :            : 
     789                 :            : 
     790                 :            : /* Remove each argument from PHI.  If an arg was the last use of an SSA_NAME,
     791                 :            :    check to see if this allows another PHI node to be removed.  */
     792                 :            : 
     793                 :            : static void
     794                 :         60 : remove_gimple_phi_args (gphi *phi)
     795                 :            : {
     796                 :         60 :   use_operand_p arg_p;
     797                 :         60 :   ssa_op_iter iter;
     798                 :            : 
     799                 :         60 :   if (dump_file && (dump_flags & TDF_DETAILS))
     800                 :            :     {
     801                 :          0 :       fprintf (dump_file, "Removing Dead PHI definition: ");
     802                 :          0 :       print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
     803                 :            :     }
     804                 :            : 
     805                 :        184 :   FOR_EACH_PHI_ARG (arg_p, phi, iter, SSA_OP_USE)
     806                 :            :     {
     807                 :        124 :       tree arg = USE_FROM_PTR (arg_p);
     808                 :        124 :       if (TREE_CODE (arg) == SSA_NAME)
     809                 :            :         {
     810                 :            :           /* Remove the reference to the existing argument.  */
     811                 :        111 :           SET_USE (arg_p, NULL_TREE);
     812                 :        111 :           if (has_zero_uses (arg))
     813                 :            :             {
     814                 :         64 :               gimple *stmt;
     815                 :         64 :               gimple_stmt_iterator gsi;
     816                 :            : 
     817                 :         64 :               stmt = SSA_NAME_DEF_STMT (arg);
     818                 :            : 
     819                 :            :               /* Also remove the def if it is a PHI node.  */
     820                 :         64 :               if (gimple_code (stmt) == GIMPLE_PHI)
     821                 :            :                 {
     822                 :          4 :                   remove_gimple_phi_args (as_a <gphi *> (stmt));
     823                 :          4 :                   gsi = gsi_for_stmt (stmt);
     824                 :          4 :                   remove_phi_node (&gsi, true);
     825                 :            :                 }
     826                 :            : 
     827                 :            :             }
     828                 :            :         }
     829                 :            :     }
     830                 :         60 : }
     831                 :            : 
     832                 :            : /* Remove any PHI node which is a virtual PHI, or a PHI with no uses.  */
     833                 :            : 
     834                 :            : static void
     835                 :     944512 : eliminate_useless_phis (void)
     836                 :            : {
     837                 :     944512 :   basic_block bb;
     838                 :     944512 :   gphi_iterator gsi;
     839                 :     944512 :   tree result;
     840                 :            : 
     841                 :    8912700 :   FOR_EACH_BB_FN (bb, cfun)
     842                 :            :     {
     843                 :   11358900 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); )
     844                 :            :         {
     845                 :    3390740 :           gphi *phi = gsi.phi ();
     846                 :    3390740 :           result = gimple_phi_result (phi);
     847                 :    6781470 :           if (virtual_operand_p (result))
     848                 :    1803640 :             remove_phi_node (&gsi, true);
     849                 :            :           else
     850                 :            :             {
     851                 :            :               /* Also remove real PHIs with no uses.  */
     852                 :    1587090 :               if (has_zero_uses (result))
     853                 :            :                 {
     854                 :         56 :                   remove_gimple_phi_args (phi);
     855                 :         56 :                   remove_phi_node (&gsi, true);
     856                 :            :                 }
     857                 :            :               else
     858                 :    1587040 :                 gsi_next (&gsi);
     859                 :            :             }
     860                 :            :         }
     861                 :            :     }
     862                 :     944512 : }
     863                 :            : 
     864                 :            : 
     865                 :            : /* This function will rewrite the current program using the variable mapping
     866                 :            :    found in MAP.  If the replacement vector VALUES is provided, any
     867                 :            :    occurrences of partitions with non-null entries in the vector will be
     868                 :            :    replaced with the expression in the vector instead of its mapped
     869                 :            :    variable.  */
     870                 :            : 
     871                 :            : static void
     872                 :     944512 : rewrite_trees (var_map map)
     873                 :            : {
     874                 :     944512 :   if (!flag_checking)
     875                 :            :     return;
     876                 :            : 
     877                 :     944500 :   basic_block bb;
     878                 :            :   /* Search for PHIs where the destination has no partition, but one
     879                 :            :      or more arguments has a partition.  This should not happen and can
     880                 :            :      create incorrect code.  */
     881                 :    8912620 :   FOR_EACH_BB_FN (bb, cfun)
     882                 :            :     {
     883                 :    7968120 :       gphi_iterator gsi;
     884                 :    9555120 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
     885                 :            :         {
     886                 :    1586990 :           gphi *phi = gsi.phi ();
     887                 :    1586990 :           tree T0 = var_to_partition_to_var (map, gimple_phi_result (phi));
     888                 :    1586990 :           if (T0 == NULL_TREE)
     889                 :            :             {
     890                 :            :               size_t i;
     891                 :          0 :               for (i = 0; i < gimple_phi_num_args (phi); i++)
     892                 :            :                 {
     893                 :          0 :                   tree arg = PHI_ARG_DEF (phi, i);
     894                 :            : 
     895                 :          0 :                   if (TREE_CODE (arg) == SSA_NAME
     896                 :          0 :                       && var_to_partition (map, arg) != NO_PARTITION)
     897                 :            :                     {
     898                 :          0 :                       fprintf (stderr, "Argument of PHI is in a partition :(");
     899                 :          0 :                       print_generic_expr (stderr, arg, TDF_SLIM);
     900                 :          0 :                       fprintf (stderr, "), but the result is not :");
     901                 :          0 :                       print_gimple_stmt (stderr, phi, 0, TDF_SLIM);
     902                 :          0 :                       internal_error ("SSA corruption");
     903                 :            :                     }
     904                 :            :                 }
     905                 :            :             }
     906                 :            :         }
     907                 :            :     }
     908                 :            : }
     909                 :            : 
     910                 :            : /* Create a default def for VAR.  */
     911                 :            : 
     912                 :            : static void
     913                 :    2479220 : create_default_def (tree var, void *arg ATTRIBUTE_UNUSED)
     914                 :            : {
     915                 :    2479220 :   if (!is_gimple_reg (var))
     916                 :            :     return;
     917                 :            : 
     918                 :    2279940 :   tree ssa = get_or_create_ssa_default_def (cfun, var);
     919                 :    2279940 :   gcc_assert (ssa);
     920                 :            : }
     921                 :            : 
     922                 :            : /* Call CALLBACK for all PARM_DECLs and RESULT_DECLs for which
     923                 :            :    assign_parms may ask for a default partition.  */
     924                 :            : 
     925                 :            : static void
     926                 :    1889020 : for_all_parms (void (*callback)(tree var, void *arg), void *arg)
     927                 :            : {
     928                 :    9747710 :   for (tree var = DECL_ARGUMENTS (current_function_decl); var;
     929                 :    3929340 :        var = DECL_CHAIN (var))
     930                 :    3929340 :     callback (var, arg);
     931                 :    1889020 :   if (!VOID_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
     932                 :    1000520 :     callback (DECL_RESULT (current_function_decl), arg);
     933                 :    1889020 :   if (cfun->static_chain_decl)
     934                 :      28584 :     callback (cfun->static_chain_decl, arg);
     935                 :    1889020 : }
     936                 :            : 
     937                 :            : /* We need to pass two arguments to set_parm_default_def_partition,
     938                 :            :    but for_all_parms only supports one.  Use a pair.  */
     939                 :            : 
     940                 :            : typedef std::pair<var_map, bitmap> parm_default_def_partition_arg;
     941                 :            : 
     942                 :            : /* Set in ARG's PARTS bitmap the bit corresponding to the partition in
     943                 :            :    ARG's MAP containing VAR's default def.  */
     944                 :            : 
     945                 :            : static void
     946                 :    2479220 : set_parm_default_def_partition (tree var, void *arg_)
     947                 :            : {
     948                 :    2479220 :   parm_default_def_partition_arg *arg = (parm_default_def_partition_arg *)arg_;
     949                 :    2479220 :   var_map map = arg->first;
     950                 :    2479220 :   bitmap parts = arg->second;
     951                 :            : 
     952                 :    2479220 :   if (!is_gimple_reg (var))
     953                 :            :     return;
     954                 :            : 
     955                 :    2279940 :   tree ssa = ssa_default_def (cfun, var);
     956                 :    2279940 :   gcc_assert (ssa);
     957                 :            : 
     958                 :    2279940 :   int version = var_to_partition (map, ssa);
     959                 :    2279940 :   gcc_assert (version != NO_PARTITION);
     960                 :            : 
     961                 :    2279940 :   bool changed = bitmap_set_bit (parts, version);
     962                 :    2279940 :   gcc_assert (changed);
     963                 :            : }
     964                 :            : 
     965                 :            : /* Allocate and return a bitmap that has a bit set for each partition
     966                 :            :    that contains a default def for a parameter.  */
     967                 :            : 
     968                 :            : static bitmap
     969                 :     944512 : get_parm_default_def_partitions (var_map map)
     970                 :            : {
     971                 :     944512 :   bitmap parm_default_def_parts = BITMAP_ALLOC (NULL);
     972                 :            : 
     973                 :     944512 :   parm_default_def_partition_arg
     974                 :     944512 :     arg = std::make_pair (map, parm_default_def_parts);
     975                 :            : 
     976                 :     944512 :   for_all_parms (set_parm_default_def_partition, &arg);
     977                 :            : 
     978                 :     944512 :   return parm_default_def_parts;
     979                 :            : }
     980                 :            : 
     981                 :            : /* Allocate and return a bitmap that has a bit set for each partition
     982                 :            :    that contains an undefined value.  */
     983                 :            : 
     984                 :            : static bitmap
     985                 :     944512 : get_undefined_value_partitions (var_map map)
     986                 :            : {
     987                 :     944512 :   bitmap undefined_value_parts = BITMAP_ALLOC (NULL);
     988                 :            : 
     989                 :   89154300 :   for (unsigned int i = 1; i < num_ssa_names; i++)
     990                 :            :     {
     991                 :   43632600 :       tree var = ssa_name (i);
     992                 :   43632600 :       if (var
     993                 :   30776800 :           && !virtual_operand_p (var)
     994                 :   18764000 :           && !has_zero_uses (var)
     995                 :   60852300 :           && ssa_undefined_value_p (var))
     996                 :            :         {
     997                 :      34279 :           const int p = var_to_partition (map, var);
     998                 :      34279 :           if (p != NO_PARTITION)
     999                 :      34279 :             bitmap_set_bit (undefined_value_parts, p);
    1000                 :            :         }
    1001                 :            :     }
    1002                 :            : 
    1003                 :     944512 :   return undefined_value_parts;
    1004                 :            : }
    1005                 :            : 
    1006                 :            : /* Given the out-of-ssa info object SA (with prepared partitions)
    1007                 :            :    eliminate all phi nodes in all basic blocks.  Afterwards no
    1008                 :            :    basic block will have phi nodes anymore and there are possibly
    1009                 :            :    some RTL instructions inserted on edges.  */
    1010                 :            : 
    1011                 :            : void
    1012                 :     944512 : expand_phi_nodes (struct ssaexpand *sa)
    1013                 :            : {
    1014                 :     944512 :   basic_block bb;
    1015                 :    1889020 :   elim_graph g (sa->map);
    1016                 :            : 
    1017                 :    8912720 :   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun)->next_bb,
    1018                 :            :                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
    1019                 :    7968200 :     if (!gimple_seq_empty_p (phi_nodes (bb)))
    1020                 :            :       {
    1021                 :     877967 :         edge e;
    1022                 :     877967 :         edge_iterator ei;
    1023                 :    2948810 :         FOR_EACH_EDGE (e, ei, bb->preds)
    1024                 :    2070840 :           eliminate_phi (e, &g);
    1025                 :     877967 :         set_phi_nodes (bb, NULL);
    1026                 :            :         /* We can't redirect EH edges in RTL land, so we need to do this
    1027                 :            :            here.  Redirection happens only when splitting is necessary,
    1028                 :            :            which it is only for critical edges, normally.  For EH edges
    1029                 :            :            it might also be necessary when the successor has more than
    1030                 :            :            one predecessor.  In that case the edge is either required to
    1031                 :            :            be fallthru (which EH edges aren't), or the predecessor needs
    1032                 :            :            to end with a jump (which again, isn't the case with EH edges).
    1033                 :            :            Hence, split all EH edges on which we inserted instructions
    1034                 :            :            and whose successor has multiple predecessors.  */
    1035                 :    2960460 :         for (ei = ei_start (bb->preds); (e = ei_safe_edge (ei)); )
    1036                 :            :           {
    1037                 :     672320 :             if (e->insns.r && (e->flags & EDGE_EH)
    1038                 :    2094140 :                 && !single_pred_p (e->dest))
    1039                 :            :               {
    1040                 :      11649 :                 rtx_insn *insns = e->insns.r;
    1041                 :      11649 :                 basic_block bb;
    1042                 :      11649 :                 e->insns.r = NULL;
    1043                 :      11649 :                 bb = split_edge (e);
    1044                 :      11649 :                 single_pred_edge (bb)->insns.r = insns;
    1045                 :            :               }
    1046                 :            :             else
    1047                 :    2070840 :               ei_next (&ei);
    1048                 :            :           }
    1049                 :            :       }
    1050                 :     944512 : }
    1051                 :            : 
    1052                 :            : 
    1053                 :            : /* Remove the ssa-names in the current function and translate them into normal
    1054                 :            :    compiler variables.  PERFORM_TER is true if Temporary Expression Replacement
    1055                 :            :    should also be used.  */
    1056                 :            : 
    1057                 :            : static void
    1058                 :     944512 : remove_ssa_form (bool perform_ter, struct ssaexpand *sa)
    1059                 :            : {
    1060                 :     944512 :   bitmap values = NULL;
    1061                 :     944512 :   var_map map;
    1062                 :            : 
    1063                 :     944512 :   for_all_parms (create_default_def, NULL);
    1064                 :    1889020 :   map = init_var_map (num_ssa_names);
    1065                 :     944512 :   coalesce_ssa_name (map);
    1066                 :            : 
    1067                 :            :   /* Return to viewing the variable list as just all reference variables after
    1068                 :            :      coalescing has been performed.  */
    1069                 :     944512 :   partition_view_normal (map);
    1070                 :            : 
    1071                 :     944512 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1072                 :            :     {
    1073                 :         39 :       fprintf (dump_file, "After Coalescing:\n");
    1074                 :         39 :       dump_var_map (dump_file, map);
    1075                 :            :     }
    1076                 :            : 
    1077                 :     944512 :   if (perform_ter)
    1078                 :            :     {
    1079                 :     688749 :       values = find_replaceable_exprs (map);
    1080                 :     688749 :       if (values && dump_file && (dump_flags & TDF_DETAILS))
    1081                 :          6 :         dump_replaceable_exprs (dump_file, values);
    1082                 :            :     }
    1083                 :            : 
    1084                 :     944512 :   rewrite_trees (map);
    1085                 :            : 
    1086                 :     944512 :   sa->map = map;
    1087                 :     944512 :   sa->values = values;
    1088                 :     944512 :   sa->partitions_for_parm_default_defs = get_parm_default_def_partitions (map);
    1089                 :     944512 :   sa->partitions_for_undefined_values = get_undefined_value_partitions (map);
    1090                 :     944512 : }
    1091                 :            : 
    1092                 :            : 
    1093                 :            : /* If not already done so for basic block BB, assign increasing uids
    1094                 :            :    to each of its instructions.  */
    1095                 :            : 
    1096                 :            : static void
    1097                 :     427164 : maybe_renumber_stmts_bb (basic_block bb)
    1098                 :            : {
    1099                 :     427164 :   unsigned i = 0;
    1100                 :     427164 :   gimple_stmt_iterator gsi;
    1101                 :            : 
    1102                 :      86293 :   if (!bb->aux)
    1103                 :          0 :     return;
    1104                 :     116547 :   bb->aux = NULL;
    1105                 :    2159690 :   for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1106                 :            :     {
    1107                 :    1926590 :       gimple *stmt = gsi_stmt (gsi);
    1108                 :    1926590 :       gimple_set_uid (stmt, i);
    1109                 :    1926590 :       i++;
    1110                 :            :     }
    1111                 :            : }
    1112                 :            : 
    1113                 :            : 
    1114                 :            : /* Return true if we can determine that the SSA_NAMEs RESULT (a result
    1115                 :            :    of a PHI node) and ARG (one of its arguments) conflict.  Return false
    1116                 :            :    otherwise, also when we simply aren't sure.  */
    1117                 :            : 
    1118                 :            : static bool
    1119                 :     689830 : trivially_conflicts_p (basic_block bb, tree result, tree arg)
    1120                 :            : {
    1121                 :     689830 :   use_operand_p use;
    1122                 :     689830 :   imm_use_iterator imm_iter;
    1123                 :     689830 :   gimple *defa = SSA_NAME_DEF_STMT (arg);
    1124                 :            : 
    1125                 :            :   /* If ARG isn't defined in the same block it's too complicated for
    1126                 :            :      our little mind.  */
    1127                 :     689830 :   if (gimple_bb (defa) != bb)
    1128                 :            :     return false;
    1129                 :            : 
    1130                 :     640205 :   FOR_EACH_IMM_USE_FAST (use, imm_iter, result)
    1131                 :            :     {
    1132                 :     476356 :       gimple *use_stmt = USE_STMT (use);
    1133                 :     476356 :       if (is_gimple_debug (use_stmt))
    1134                 :      91750 :         continue;
    1135                 :            :       /* Now, if there's a use of RESULT that lies outside this basic block,
    1136                 :            :          then there surely is a conflict with ARG.  */
    1137                 :     384606 :       if (gimple_bb (use_stmt) != bb)
    1138                 :            :         return true;
    1139                 :     342225 :       if (gimple_code (use_stmt) == GIMPLE_PHI)
    1140                 :        406 :         continue;
    1141                 :            :       /* The use now is in a real stmt of BB, so if ARG was defined
    1142                 :            :          in a PHI node (like RESULT) both conflict.  */
    1143                 :     341819 :       if (gimple_code (defa) == GIMPLE_PHI)
    1144                 :            :         return true;
    1145                 :     340871 :       maybe_renumber_stmts_bb (bb);
    1146                 :            :       /* If the use of RESULT occurs after the definition of ARG,
    1147                 :            :          the two conflict too.  */
    1148                 :     340871 :       if (gimple_uid (defa) < gimple_uid (use_stmt))
    1149                 :            :         return true;
    1150                 :            :     }
    1151                 :            : 
    1152                 :            :   return false;
    1153                 :            : }
    1154                 :            : 
    1155                 :            : 
    1156                 :            : /* Search every PHI node for arguments associated with backedges which
    1157                 :            :    we can trivially determine will need a copy (the argument is either
    1158                 :            :    not an SSA_NAME or the argument has a different underlying variable
    1159                 :            :    than the PHI result).
    1160                 :            : 
    1161                 :            :    Insert a copy from the PHI argument to a new destination at the
    1162                 :            :    end of the block with the backedge to the top of the loop.  Update
    1163                 :            :    the PHI argument to reference this new destination.  */
    1164                 :            : 
    1165                 :            : static void
    1166                 :     944512 : insert_backedge_copies (void)
    1167                 :            : {
    1168                 :     944512 :   basic_block bb;
    1169                 :     944512 :   gphi_iterator gsi;
    1170                 :            : 
    1171                 :     944512 :   mark_dfs_back_edges ();
    1172                 :            : 
    1173                 :    8912700 :   FOR_EACH_BB_FN (bb, cfun)
    1174                 :            :     {
    1175                 :            :       /* Mark block as possibly needing calculation of UIDs.  */
    1176                 :    7968190 :       bb->aux = &bb->aux;
    1177                 :            : 
    1178                 :   11358900 :       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
    1179                 :            :         {
    1180                 :    3390740 :           gphi *phi = gsi.phi ();
    1181                 :    3390740 :           tree result = gimple_phi_result (phi);
    1182                 :    3390740 :           size_t i;
    1183                 :            : 
    1184                 :    6781480 :           if (virtual_operand_p (result))
    1185                 :    1803640 :             continue;
    1186                 :            : 
    1187                 :    5427380 :           for (i = 0; i < gimple_phi_num_args (phi); i++)
    1188                 :            :             {
    1189                 :    3840280 :               tree arg = gimple_phi_arg_def (phi, i);
    1190                 :    3840280 :               edge e = gimple_phi_arg_edge (phi, i);
    1191                 :            :               /* We are only interested in copies emitted on critical
    1192                 :            :                  backedges.  */
    1193                 :    7094580 :               if (!(e->flags & EDGE_DFS_BACK)
    1194                 :    3840280 :                   || !EDGE_CRITICAL_P (e))
    1195                 :    3254300 :                 continue;
    1196                 :            : 
    1197                 :            :               /* If the argument is not an SSA_NAME, then we will need a
    1198                 :            :                  constant initialization.  If the argument is an SSA_NAME then
    1199                 :            :                  a copy statement may be needed.  First handle the case
    1200                 :            :                  where we cannot insert before the argument definition.  */
    1201                 :     585987 :               if (TREE_CODE (arg) != SSA_NAME
    1202                 :     585987 :                   || (gimple_code (SSA_NAME_DEF_STMT (arg)) == GIMPLE_PHI
    1203                 :     139340 :                       && trivially_conflicts_p (bb, result, arg)))
    1204                 :            :                 {
    1205                 :      35497 :                   tree name;
    1206                 :      35497 :                   gassign *stmt;
    1207                 :      35497 :                   gimple *last = NULL;
    1208                 :      35497 :                   gimple_stmt_iterator gsi2;
    1209                 :            : 
    1210                 :      35497 :                   gsi2 = gsi_last_bb (gimple_phi_arg_edge (phi, i)->src);
    1211                 :      35497 :                   if (!gsi_end_p (gsi2))
    1212                 :      35497 :                     last = gsi_stmt (gsi2);
    1213                 :            : 
    1214                 :            :                   /* In theory the only way we ought to get back to the
    1215                 :            :                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
    1216                 :            :                      However, better safe than sorry.
    1217                 :            :                      If the block ends with a control statement or
    1218                 :            :                      something that might throw, then we have to
    1219                 :            :                      insert this assignment before the last
    1220                 :            :                      statement.  Else insert it after the last statement.  */
    1221                 :      35497 :                   if (last && stmt_ends_bb_p (last))
    1222                 :            :                     {
    1223                 :            :                       /* If the last statement in the block is the definition
    1224                 :            :                          site of the PHI argument, then we can't insert
    1225                 :            :                          anything after it.  */
    1226                 :      35497 :                       if (TREE_CODE (arg) == SSA_NAME
    1227                 :      35497 :                           && SSA_NAME_DEF_STMT (arg) == last)
    1228                 :          0 :                         continue;
    1229                 :            :                     }
    1230                 :            : 
    1231                 :            :                   /* Create a new instance of the underlying variable of the
    1232                 :            :                      PHI result.  */
    1233                 :      35497 :                   name = copy_ssa_name (result);
    1234                 :      35497 :                   stmt = gimple_build_assign (name,
    1235                 :            :                                               gimple_phi_arg_def (phi, i));
    1236                 :            : 
    1237                 :            :                   /* copy location if present.  */
    1238                 :      35497 :                   if (gimple_phi_arg_has_location (phi, i))
    1239                 :        728 :                     gimple_set_location (stmt,
    1240                 :            :                                          gimple_phi_arg_location (phi, i));
    1241                 :            : 
    1242                 :            :                   /* Insert the new statement into the block and update
    1243                 :            :                      the PHI node.  */
    1244                 :      35497 :                   if (last && stmt_ends_bb_p (last))
    1245                 :      35497 :                     gsi_insert_before (&gsi2, stmt, GSI_NEW_STMT);
    1246                 :            :                   else
    1247                 :          0 :                     gsi_insert_after (&gsi2, stmt, GSI_NEW_STMT);
    1248                 :      35497 :                   SET_PHI_ARG_DEF (phi, i, name);
    1249                 :            :                 }
    1250                 :            :               /* Insert a copy before the definition of the backedge value
    1251                 :            :                  and adjust all conflicting uses.  */
    1252                 :     550490 :               else if (trivially_conflicts_p (bb, result, arg))
    1253                 :            :                 {
    1254                 :      21722 :                   gimple *def = SSA_NAME_DEF_STMT (arg);
    1255                 :      21722 :                   if (gimple_nop_p (def)
    1256                 :      21722 :                       || gimple_code (def) == GIMPLE_PHI)
    1257                 :          0 :                     continue;
    1258                 :      21722 :                   tree name = copy_ssa_name (result);
    1259                 :      21722 :                   gimple *stmt = gimple_build_assign (name, result);
    1260                 :      21722 :                   imm_use_iterator imm_iter;
    1261                 :      21722 :                   gimple *use_stmt;
    1262                 :            :                   /* The following matches trivially_conflicts_p.  */
    1263                 :     137372 :                   FOR_EACH_IMM_USE_STMT (use_stmt, imm_iter, result)
    1264                 :            :                     {
    1265                 :     115650 :                       if (gimple_bb (use_stmt) != bb
    1266                 :     115650 :                           || (gimple_code (use_stmt) != GIMPLE_PHI
    1267                 :      86293 :                               && (maybe_renumber_stmts_bb (bb), true)
    1268                 :      86293 :                               && gimple_uid (use_stmt) > gimple_uid (def)))
    1269                 :            :                         {
    1270                 :      67279 :                           use_operand_p use;
    1271                 :     202807 :                           FOR_EACH_IMM_USE_ON_STMT (use, imm_iter)
    1272                 :      67764 :                             SET_USE (use, name);
    1273                 :            :                         }
    1274                 :            :                     }
    1275                 :      21722 :                   gimple_stmt_iterator gsi = gsi_for_stmt (def);
    1276                 :      21722 :                   gsi_insert_before (&gsi, stmt, GSI_SAME_STMT);
    1277                 :            :                 }
    1278                 :            :             }
    1279                 :            :         }
    1280                 :            : 
    1281                 :            :       /* Unmark this block again.  */
    1282                 :    7968190 :       bb->aux = NULL;
    1283                 :            :     }
    1284                 :     944512 : }
    1285                 :            : 
    1286                 :            : /* Free all memory associated with going out of SSA form.  SA is
    1287                 :            :    the outof-SSA info object.  */
    1288                 :            : 
    1289                 :            : void
    1290                 :     944512 : finish_out_of_ssa (struct ssaexpand *sa)
    1291                 :            : {
    1292                 :     944512 :   free (sa->partition_to_pseudo);
    1293                 :     944512 :   if (sa->values)
    1294                 :     465151 :     BITMAP_FREE (sa->values);
    1295                 :     944512 :   delete_var_map (sa->map);
    1296                 :     944512 :   BITMAP_FREE (sa->partitions_for_parm_default_defs);
    1297                 :     944512 :   BITMAP_FREE (sa->partitions_for_undefined_values);
    1298                 :     944512 :   memset (sa, 0, sizeof *sa);
    1299                 :     944512 : }
    1300                 :            : 
    1301                 :            : /* Take the current function out of SSA form, translating PHIs as described in
    1302                 :            :    R. Morgan, ``Building an Optimizing Compiler'',
    1303                 :            :    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
    1304                 :            : 
    1305                 :            : unsigned int
    1306                 :     944512 : rewrite_out_of_ssa (struct ssaexpand *sa)
    1307                 :            : {
    1308                 :            :   /* If elimination of a PHI requires inserting a copy on a backedge,
    1309                 :            :      then we will have to split the backedge which has numerous
    1310                 :            :      undesirable performance effects.
    1311                 :            : 
    1312                 :            :      A significant number of such cases can be handled here by inserting
    1313                 :            :      copies into the loop itself.  */
    1314                 :     944512 :   insert_backedge_copies ();
    1315                 :            : 
    1316                 :            : 
    1317                 :            :   /* Eliminate PHIs which are of no use, such as virtual or dead phis.  */
    1318                 :     944512 :   eliminate_useless_phis ();
    1319                 :            : 
    1320                 :     944512 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1321                 :         39 :     gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
    1322                 :            : 
    1323                 :     944512 :   remove_ssa_form (flag_tree_ter, sa);
    1324                 :            : 
    1325                 :     944512 :   if (dump_file && (dump_flags & TDF_DETAILS))
    1326                 :         39 :     gimple_dump_cfg (dump_file, dump_flags & ~TDF_DETAILS);
    1327                 :            : 
    1328                 :     944512 :   return 0;
    1329                 :            : }

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.