gcc/tree-ssa-phionlycprop.c

   1 /* Const/Copy propagation originating from degenerate PHIs
   2    Copyright (C) 2001-2017 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "cfghooks.h"
  25 #include "tree.h"
  26 #include "gimple.h"
  27 #include "ssa.h"
  28 #include "fold-const.h"
  29 #include "cfgloop.h"
  30 #include "gimple-pretty-print.h"
  31 #include "gimple-fold.h"
  32 #include "tree-eh.h"
  33 #include "gimple-iterator.h"
  34 #include "tree-cfg.h"
  35 #include "tree-pass.h"
  36 #include "tree-ssa-propagate.h"
  37
  38
  39 /* PHI-ONLY copy and constant propagation.  This pass is meant to clean
  40    up degenerate PHIs created by or exposed by jump threading.  */
  41
  42 /* Given a statement STMT, which is either a PHI node or an assignment,
  43    remove it from the IL.  */
  44
  45 static void
  46 remove_stmt_or_phi (gimple *stmt)
  47 {
  48   gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
  49
  50   if (gimple_code (stmt) == GIMPLE_PHI)
  51     remove_phi_node (&gsi, true);
  52   else
  53     {
  54       gsi_remove (&gsi, true);
  55       release_defs (stmt);
  56     }
  57 }
  58
  59 /* Given a statement STMT, which is either a PHI node or an assignment,
  60    return the "rhs" of the node, in the case of a non-degenerate
  61    phi, NULL is returned.  */
  62
  63 static tree
  64 get_rhs_or_phi_arg (gimple *stmt)
  65 {
  66   if (gimple_code (stmt) == GIMPLE_PHI)
  67     return degenerate_phi_result (as_a <gphi *> (stmt));
  68   else if (gimple_assign_single_p (stmt))
  69     return gimple_assign_rhs1 (stmt);
  70   else
  71     gcc_unreachable ();
  72 }
  73
  74
  75 /* Given a statement STMT, which is either a PHI node or an assignment,
  76    return the "lhs" of the node.  */
  77
  78 static tree
  79 get_lhs_or_phi_result (gimple *stmt)
  80 {
  81   if (gimple_code (stmt) == GIMPLE_PHI)
  82     return gimple_phi_result (stmt);
  83   else if (is_gimple_assign (stmt))
  84     return gimple_assign_lhs (stmt);
  85   else
  86     gcc_unreachable ();
  87 }
  88
  89 /* Propagate RHS into all uses of LHS (when possible).
  90
  91    RHS and LHS are derived from STMT, which is passed in solely so
  92    that we can remove it if propagation is successful.
  93
  94    When propagating into a PHI node or into a statement which turns
  95    into a trivial copy or constant initialization, set the
  96    appropriate bit in INTERESTING_NAMEs so that we will visit those
  97    nodes as well in an effort to pick up secondary optimization
  98    opportunities.
  99
 100    NEED_EH_CLEANUP tracks blocks that need their EH information
 101    cleaned up after changing EH information on a statement.  */
 102
 103 static bool
 104 propagate_rhs_into_lhs (gimple *stmt, tree lhs, tree rhs,
 105                         bitmap interesting_names, bitmap need_eh_cleanup)
 106 {
 107   bool cfg_altered = false;
 108
 109   /* First verify that propagation is valid.  */
 110   if (may_propagate_copy (lhs, rhs))
 111     {
 112       use_operand_p use_p;
 113       imm_use_iterator iter;
 114       gimple *use_stmt;
 115       bool all = true;
 116
 117       /* Dump details.  */
 118       if (dump_file && (dump_flags & TDF_DETAILS))
 119         {
 120           fprintf (dump_file, "  Replacing '");
 121           print_generic_expr (dump_file, lhs, dump_flags);
 122           fprintf (dump_file, "' with %s '",
 123                    (TREE_CODE (rhs) != SSA_NAME ? "constant" : "variable"));
 124                    print_generic_expr (dump_file, rhs, dump_flags);
 125           fprintf (dump_file, "'\n");
 126         }
 127
 128       /* Walk over every use of LHS and try to replace the use with RHS.
 129          At this point the only reason why such a propagation would not
 130          be successful would be if the use occurs in an ASM_EXPR.  */
 131       FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
 132         {
 133           /* Leave debug stmts alone.  If we succeed in propagating
 134              all non-debug uses, we'll drop the DEF, and propagation
 135              into debug stmts will occur then.  */
 136           if (gimple_debug_bind_p (use_stmt))
 137             continue;
 138
 139           /* It's not always safe to propagate into an ASM_EXPR.  */
 140           if (gimple_code (use_stmt) == GIMPLE_ASM
 141               && ! may_propagate_copy_into_asm (lhs))
 142             {
 143               all = false;
 144               continue;
 145             }
 146
 147           /* It's not ok to propagate into the definition stmt of RHS.
 148                 <bb 9>:
 149                   # prephitmp.12_36 = PHI <g_67.1_6(9)>
 150                   g_67.1_6 = prephitmp.12_36;
 151                   goto <bb 9>;
 152              While this is strictly all dead code we do not want to
 153              deal with this here.  */
 154           if (TREE_CODE (rhs) == SSA_NAME
 155               && SSA_NAME_DEF_STMT (rhs) == use_stmt)
 156             {
 157               all = false;
 158               continue;
 159             }
 160
 161           /* Dump details.  */
 162           if (dump_file && (dump_flags & TDF_DETAILS))
 163             {
 164               fprintf (dump_file, "    Original statement:");
 165               print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
 166             }
 167
 168           /* Propagate the RHS into this use of the LHS.  */
 169           FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 170             propagate_value (use_p, rhs);
 171
 172           /* Special cases to avoid useless calls into the folding
 173              routines, operand scanning, etc.
 174
 175              Propagation into a PHI may cause the PHI to become
 176              a degenerate, so mark the PHI as interesting.  No other
 177              actions are necessary.  */
 178           if (gimple_code (use_stmt) == GIMPLE_PHI)
 179             {
 180               tree result;
 181
 182               /* Dump details.  */
 183               if (dump_file && (dump_flags & TDF_DETAILS))
 184                 {
 185                   fprintf (dump_file, "    Updated statement:");
 186                   print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
 187                 }
 188
 189               result = get_lhs_or_phi_result (use_stmt);
 190               bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
 191               continue;
 192             }
 193
 194           /* From this point onward we are propagating into a
 195              real statement.  Folding may (or may not) be possible,
 196              we may expose new operands, expose dead EH edges,
 197              etc.  */
 198           /* NOTE tuples. In the tuples world, fold_stmt_inplace
 199              cannot fold a call that simplifies to a constant,
 200              because the GIMPLE_CALL must be replaced by a
 201              GIMPLE_ASSIGN, and there is no way to effect such a
 202              transformation in-place.  We might want to consider
 203              using the more general fold_stmt here.  */
 204             {
 205               gimple_stmt_iterator gsi = gsi_for_stmt (use_stmt);
 206               fold_stmt_inplace (&gsi);
 207             }
 208
 209           /* Sometimes propagation can expose new operands to the
 210              renamer.  */
 211           update_stmt (use_stmt);
 212
 213           /* Dump details.  */
 214           if (dump_file && (dump_flags & TDF_DETAILS))
 215             {
 216               fprintf (dump_file, "    Updated statement:");
 217               print_gimple_stmt (dump_file, use_stmt, 0, dump_flags);
 218             }
 219
 220           /* If we replaced a variable index with a constant, then
 221              we would need to update the invariant flag for ADDR_EXPRs.  */
 222           if (gimple_assign_single_p (use_stmt)
 223               && TREE_CODE (gimple_assign_rhs1 (use_stmt)) == ADDR_EXPR)
 224             recompute_tree_invariant_for_addr_expr
 225                 (gimple_assign_rhs1 (use_stmt));
 226
 227           /* If we cleaned up EH information from the statement,
 228              mark its containing block as needing EH cleanups.  */
 229           if (maybe_clean_or_replace_eh_stmt (use_stmt, use_stmt))
 230             {
 231               bitmap_set_bit (need_eh_cleanup, gimple_bb (use_stmt)->index);
 232               if (dump_file && (dump_flags & TDF_DETAILS))
 233                 fprintf (dump_file, "  Flagged to clear EH edges.\n");
 234             }
 235
 236           /* Propagation may expose new trivial copy/constant propagation
 237              opportunities.  */
 238           if (gimple_assign_single_p (use_stmt)
 239               && TREE_CODE (gimple_assign_lhs (use_stmt)) == SSA_NAME
 240               && (TREE_CODE (gimple_assign_rhs1 (use_stmt)) == SSA_NAME
 241                   || is_gimple_min_invariant (gimple_assign_rhs1 (use_stmt))))
 242             {
 243               tree result = get_lhs_or_phi_result (use_stmt);
 244               bitmap_set_bit (interesting_names, SSA_NAME_VERSION (result));
 245             }
 246
 247           /* Propagation into these nodes may make certain edges in
 248              the CFG unexecutable.  We want to identify them as PHI nodes
 249              at the destination of those unexecutable edges may become
 250              degenerates.  */
 251           else if (gimple_code (use_stmt) == GIMPLE_COND
 252                    || gimple_code (use_stmt) == GIMPLE_SWITCH
 253                    || gimple_code (use_stmt) == GIMPLE_GOTO)
 254             {
 255               tree val;
 256
 257               if (gimple_code (use_stmt) == GIMPLE_COND)
 258                 val = fold_binary_loc (gimple_location (use_stmt),
 259                                    gimple_cond_code (use_stmt),
 260                                    boolean_type_node,
 261                                    gimple_cond_lhs (use_stmt),
 262                                    gimple_cond_rhs (use_stmt));
 263               else if (gimple_code (use_stmt) == GIMPLE_SWITCH)
 264                 val = gimple_switch_index (as_a <gswitch *> (use_stmt));
 265               else
 266                 val = gimple_goto_dest  (use_stmt);
 267
 268               if (val && is_gimple_min_invariant (val))
 269                 {
 270                   basic_block bb = gimple_bb (use_stmt);
 271                   edge te = find_taken_edge (bb, val);
 272                   if (!te)
 273                     continue;
 274
 275                   edge_iterator ei;
 276                   edge e;
 277                   gimple_stmt_iterator gsi;
 278                   gphi_iterator psi;
 279
 280                   /* Remove all outgoing edges except TE.  */
 281                   for (ei = ei_start (bb->succs); (e = ei_safe_edge (ei));)
 282                     {
 283                       if (e != te)
 284                         {
 285                           /* Mark all the PHI nodes at the destination of
 286                              the unexecutable edge as interesting.  */
 287                           for (psi = gsi_start_phis (e->dest);
 288                                !gsi_end_p (psi);
 289                                gsi_next (&psi))
 290                             {
 291                               gphi *phi = psi.phi ();
 292
 293                               tree result = gimple_phi_result (phi);
 294                               int version = SSA_NAME_VERSION (result);
 295
 296                               bitmap_set_bit (interesting_names, version);
 297                             }
 298
 299                           te->probability += e->probability;
 300
 301                           remove_edge (e);
 302                           cfg_altered = true;
 303                         }
 304                       else
 305                         ei_next (&ei);
 306                     }
 307
 308                   gsi = gsi_last_bb (gimple_bb (use_stmt));
 309                   gsi_remove (&gsi, true);
 310
 311                   /* And fixup the flags on the single remaining edge.  */
 312                   te->flags &= ~(EDGE_TRUE_VALUE | EDGE_FALSE_VALUE);
 313                   te->flags &= ~EDGE_ABNORMAL;
 314                   te->flags |= EDGE_FALLTHRU;
 315                 }
 316             }
 317         }
 318
 319       /* Ensure there is nothing else to do. */
 320       gcc_assert (!all || has_zero_uses (lhs));
 321
 322       /* If we were able to propagate away all uses of LHS, then
 323          we can remove STMT.  */
 324       if (all)
 325         remove_stmt_or_phi (stmt);
 326     }
 327   return cfg_altered;
 328 }
 329
 330 /* STMT is either a PHI node (potentially a degenerate PHI node) or
 331    a statement that is a trivial copy or constant initialization.
 332
 333    Attempt to eliminate STMT by propagating its RHS into all uses of
 334    its LHS.  This may in turn set new bits in INTERESTING_NAMES
 335    for nodes we want to revisit later.
 336
 337    All exit paths should clear INTERESTING_NAMES for the result
 338    of STMT.
 339
 340    NEED_EH_CLEANUP tracks blocks that need their EH information
 341    cleaned up after changing EH information on a statement.  It is
 342    not set or queried here, but passed along to children.  */
 343
 344 static bool
 345 eliminate_const_or_copy (gimple *stmt, bitmap interesting_names,
 346                          bitmap need_eh_cleanup)
 347 {
 348   tree lhs = get_lhs_or_phi_result (stmt);
 349   tree rhs;
 350   int version = SSA_NAME_VERSION (lhs);
 351   bool cfg_altered = false;
 352
 353   /* If the LHS of this statement or PHI has no uses, then we can
 354      just eliminate it.  This can occur if, for example, the PHI
 355      was created by block duplication due to threading and its only
 356      use was in the conditional at the end of the block which was
 357      deleted.  */
 358   if (has_zero_uses (lhs))
 359     {
 360       bitmap_clear_bit (interesting_names, version);
 361       remove_stmt_or_phi (stmt);
 362       return cfg_altered;
 363     }
 364
 365   /* Get the RHS of the assignment or PHI node if the PHI is a
 366      degenerate.  */
 367   rhs = get_rhs_or_phi_arg (stmt);
 368   if (!rhs)
 369     {
 370       bitmap_clear_bit (interesting_names, version);
 371       return cfg_altered;
 372     }
 373
 374   if (!virtual_operand_p (lhs))
 375     cfg_altered = propagate_rhs_into_lhs (stmt, lhs, rhs,
 376                                           interesting_names, need_eh_cleanup);
 377   else
 378     {
 379       gimple *use_stmt;
 380       imm_use_iterator iter;
 381       use_operand_p use_p;
 382       /* For virtual operands we have to propagate into all uses as
 383          otherwise we will create overlapping life-ranges.  */
 384       FOR_EACH_IMM_USE_STMT (use_stmt, iter, lhs)
 385         FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
 386           SET_USE (use_p, rhs);
 387       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs))
 388         SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rhs) = 1;
 389       remove_stmt_or_phi (stmt);
 390     }
 391
 392   /* Note that STMT may well have been deleted by now, so do
 393      not access it, instead use the saved version # to clear
 394      T's entry in the worklist.  */
 395   bitmap_clear_bit (interesting_names, version);
 396   return cfg_altered;
 397 }
 398
 399 /* The first phase in degenerate PHI elimination.
 400
 401    Eliminate the degenerate PHIs in BB, then recurse on the
 402    dominator children of BB.
 403
 404    INTERESTING_NAMES tracks SSA_NAMEs that we may want to revisit
 405    in the future.  It is not set or queried here, but passed along
 406    to children.
 407
 408    NEED_EH_CLEANUP tracks blocks that need their EH information
 409    cleaned up after changing EH information on a statement.  It is
 410    not set or queried here, but passed along to children.  */
 411
 412 static bool
 413 eliminate_degenerate_phis_1 (basic_block bb, bitmap interesting_names,
 414                              bitmap need_eh_cleanup)
 415 {
 416   gphi_iterator gsi;
 417   basic_block son;
 418   bool cfg_altered = false;
 419
 420   for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi);)
 421     {
 422       gphi *phi = gsi.phi ();
 423       /* We might end up removing PHI so advance the iterator now.  */
 424       gsi_next (&gsi);
 425       cfg_altered |= eliminate_const_or_copy (phi, interesting_names,
 426                                               need_eh_cleanup);
 427     }
 428
 429   /* Recurse into the dominator children of BB.  */
 430   for (son = first_dom_son (CDI_DOMINATORS, bb);
 431        son;
 432        son = next_dom_son (CDI_DOMINATORS, son))
 433     cfg_altered |= eliminate_degenerate_phis_1 (son, interesting_names,
 434                                                 need_eh_cleanup);
 435
 436   return cfg_altered;
 437 }
 438
 439
 440 /* A very simple pass to eliminate degenerate PHI nodes from the
 441    IL.  This is meant to be fast enough to be able to be run several
 442    times in the optimization pipeline.
 443
 444    Certain optimizations, particularly those which duplicate blocks
 445    or remove edges from the CFG can create or expose PHIs which are
 446    trivial copies or constant initializations.
 447
 448    While we could pick up these optimizations in DOM or with the
 449    combination of copy-prop and CCP, those solutions are far too
 450    heavy-weight for our needs.
 451
 452    This implementation has two phases so that we can efficiently
 453    eliminate the first order degenerate PHIs and second order
 454    degenerate PHIs.
 455
 456    The first phase performs a dominator walk to identify and eliminate
 457    the vast majority of the degenerate PHIs.  When a degenerate PHI
 458    is identified and eliminated any affected statements or PHIs
 459    are put on a worklist.
 460
 461    The second phase eliminates degenerate PHIs and trivial copies
 462    or constant initializations using the worklist.  This is how we
 463    pick up the secondary optimization opportunities with minimal
 464    cost.  */
 465
 466 namespace {
 467
 468 const pass_data pass_data_phi_only_cprop =
 469 {
 470   GIMPLE_PASS, /* type */
 471   "phicprop", /* name */
 472   OPTGROUP_NONE, /* optinfo_flags */
 473   TV_TREE_PHI_CPROP, /* tv_id */
 474   ( PROP_cfg | PROP_ssa ), /* properties_required */
 475   0, /* properties_provided */
 476   0, /* properties_destroyed */
 477   0, /* todo_flags_start */
 478   ( TODO_cleanup_cfg | TODO_update_ssa ), /* todo_flags_finish */
 479 };
 480
 481 class pass_phi_only_cprop : public gimple_opt_pass
 482 {
 483 public:
 484   pass_phi_only_cprop (gcc::context *ctxt)
 485     : gimple_opt_pass (pass_data_phi_only_cprop, ctxt)
 486   {}
 487
 488   /* opt_pass methods: */
 489   opt_pass * clone () { return new pass_phi_only_cprop (m_ctxt); }
 490   virtual bool gate (function *) { return flag_tree_dom != 0; }
 491   virtual unsigned int execute (function *);
 492
 493 }; // class pass_phi_only_cprop
 494
 495 unsigned int
 496 pass_phi_only_cprop::execute (function *fun)
 497 {
 498   bool cfg_altered = false;
 499
 500   /* Bitmap of blocks which need EH information updated.  We can not
 501      update it on-the-fly as doing so invalidates the dominator tree.  */
 502   auto_bitmap need_eh_cleanup;
 503
 504   /* INTERESTING_NAMES is effectively our worklist, indexed by
 505      SSA_NAME_VERSION.
 506
 507      A set bit indicates that the statement or PHI node which
 508      defines the SSA_NAME should be (re)examined to determine if
 509      it has become a degenerate PHI or trivial const/copy propagation
 510      opportunity.
 511
 512      Experiments have show we generally get better compilation
 513      time behavior with bitmaps rather than sbitmaps.  */
 514   auto_bitmap interesting_names;
 515   auto_bitmap interesting_names1;
 516
 517   calculate_dominance_info (CDI_DOMINATORS);
 518   cfg_altered = false;
 519
 520   /* First phase.  Eliminate degenerate PHIs via a dominator
 521      walk of the CFG.
 522
 523      Experiments have indicated that we generally get better
 524      compile-time behavior by visiting blocks in the first
 525      phase in dominator order.  Presumably this is because walking
 526      in dominator order leaves fewer PHIs for later examination
 527      by the worklist phase.  */
 528   cfg_altered = eliminate_degenerate_phis_1 (ENTRY_BLOCK_PTR_FOR_FN (fun),
 529                                              interesting_names,
 530                                              need_eh_cleanup);
 531
 532   /* Second phase.  Eliminate second order degenerate PHIs as well
 533      as trivial copies or constant initializations identified by
 534      the first phase or this phase.  Basically we keep iterating
 535      until our set of INTERESTING_NAMEs is empty.   */
 536   while (!bitmap_empty_p (interesting_names))
 537     {
 538       unsigned int i;
 539       bitmap_iterator bi;
 540
 541       /* EXECUTE_IF_SET_IN_BITMAP does not like its bitmap
 542          changed during the loop.  Copy it to another bitmap and
 543          use that.  */
 544       bitmap_copy (interesting_names1, interesting_names);
 545
 546       EXECUTE_IF_SET_IN_BITMAP (interesting_names1, 0, i, bi)
 547         {
 548           tree name = ssa_name (i);
 549
 550           /* Ignore SSA_NAMEs that have been released because
 551              their defining statement was deleted (unreachable).  */
 552           if (name)
 553             cfg_altered
 554               |= eliminate_const_or_copy (SSA_NAME_DEF_STMT (ssa_name (i)),
 555                                           interesting_names, need_eh_cleanup);
 556         }
 557     }
 558
 559   if (cfg_altered)
 560     {
 561       free_dominance_info (CDI_DOMINATORS);
 562       /* If we changed the CFG schedule loops for fixup by cfgcleanup.  */
 563       loops_state_set (LOOPS_NEED_FIXUP);
 564     }
 565
 566   /* Propagation of const and copies may make some EH edges dead.  Purge
 567      such edges from the CFG as needed.  */
 568   if (!bitmap_empty_p (need_eh_cleanup))
 569     gimple_purge_all_dead_eh_edges (need_eh_cleanup);
 570
 571   return 0;
 572 }
 573
 574 } // anon namespace
 575
 576 gimple_opt_pass *
 577 make_pass_phi_only_cprop (gcc::context *ctxt)
 578 {
 579   return new pass_phi_only_cprop (ctxt);
 580 }