gcc/tree-ssa-phiprop.cc

   1 /* Backward propagation of indirect loads through PHIs.
   2    Copyright (C) 2007-2022 Free Software Foundation, Inc.
   3    Contributed by Richard Guenther <rguenther@suse.de>
   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 "tree.h"
  26 #include "gimple.h"
  27 #include "tree-pass.h"
  28 #include "ssa.h"
  29 #include "gimple-pretty-print.h"
  30 #include "fold-const.h"
  31 #include "tree-eh.h"
  32 #include "gimplify.h"
  33 #include "gimple-iterator.h"
  34 #include "stor-layout.h"
  35 #include "tree-ssa-loop.h"
  36
  37 /* This pass propagates indirect loads through the PHI node for its
  38    address to make the load source possibly non-addressable and to
  39    allow for PHI optimization to trigger.
  40
  41    For example the pass changes
  42
  43      # addr_1 = PHI <&a, &b>
  44      tmp_1 = *addr_1;
  45
  46    to
  47
  48      # tmp_1 = PHI <a, b>
  49
  50    but also handles more complex scenarios like
  51
  52      D.2077_2 = &this_1(D)->a1;
  53      ...
  54
  55      # b_12 = PHI <&c(2), D.2077_2(3)>
  56      D.2114_13 = *b_12;
  57      ...
  58
  59      # b_15 = PHI <b_12(4), &b(5)>
  60      D.2080_5 = &this_1(D)->a0;
  61      ...
  62
  63      # b_18 = PHI <D.2080_5(6), &c(7)>
  64      ...
  65
  66      # b_21 = PHI <b_15(8), b_18(9)>
  67      D.2076_8 = *b_21;
  68
  69    where the addresses loaded are defined by PHIs itself.
  70    The above happens for
  71
  72      std::max(std::min(a0, c), std::min(std::max(a1, c), b))
  73
  74    where this pass transforms it to a form later PHI optimization
  75    recognizes and transforms it to the simple
  76
  77      D.2109_10 = this_1(D)->a1;
  78      D.2110_11 = c;
  79      D.2114_31 = MAX_EXPR <D.2109_10, D.2110_11>;
  80      D.2115_14 = b;
  81      D.2125_17 = MIN_EXPR <D.2115_14, D.2114_31>;
  82      D.2119_16 = this_1(D)->a0;
  83      D.2124_32 = MIN_EXPR <D.2110_11, D.2119_16>;
  84      D.2076_33 = MAX_EXPR <D.2125_17, D.2124_32>;
  85
  86    The pass does a dominator walk processing loads using a basic-block
  87    local analysis and stores the result for use by transformations on
  88    dominated basic-blocks.  */
  89
  90
  91 /* Structure to keep track of the value of a dereferenced PHI result
  92    and the virtual operand used for that dereference.  */
  93
  94 struct phiprop_d
  95 {
  96   tree value;
  97   tree vuse;
  98 };
  99
 100 /* Verify if the value recorded for NAME in PHIVN is still valid at
 101    the start of basic block BB.  */
 102
 103 static bool
 104 phivn_valid_p (struct phiprop_d *phivn, tree name, basic_block bb)
 105 {
 106   tree vuse = phivn[SSA_NAME_VERSION (name)].vuse;
 107   gimple *use_stmt;
 108   imm_use_iterator ui2;
 109   bool ok = true;
 110
 111   /* The def stmts of the virtual uses need to be dominated by bb.  */
 112   gcc_assert (vuse != NULL_TREE);
 113
 114   FOR_EACH_IMM_USE_STMT (use_stmt, ui2, vuse)
 115     {
 116       /* If BB does not dominate a VDEF, the value is invalid.  */
 117       if ((gimple_vdef (use_stmt) != NULL_TREE
 118            || gimple_code (use_stmt) == GIMPLE_PHI)
 119           && !dominated_by_p (CDI_DOMINATORS, gimple_bb (use_stmt), bb))
 120         {
 121           ok = false;
 122           break;
 123         }
 124     }
 125
 126   return ok;
 127 }
 128
 129 /* Insert a new phi node for the dereference of PHI at basic_block
 130    BB with the virtual operands from USE_STMT.  */
 131
 132 static tree
 133 phiprop_insert_phi (basic_block bb, gphi *phi, gimple *use_stmt,
 134                     struct phiprop_d *phivn, size_t n)
 135 {
 136   tree res;
 137   gphi *new_phi = NULL;
 138   edge_iterator ei;
 139   edge e;
 140
 141   gcc_assert (is_gimple_assign (use_stmt)
 142               && gimple_assign_rhs_code (use_stmt) == MEM_REF);
 143
 144   /* Build a new PHI node to replace the definition of
 145      the indirect reference lhs.  */
 146   res = gimple_assign_lhs (use_stmt);
 147   if (TREE_CODE (res) == SSA_NAME)
 148     new_phi = create_phi_node (res, bb);
 149
 150   if (dump_file && (dump_flags & TDF_DETAILS))
 151     {
 152       fprintf (dump_file, "Inserting PHI for result of load ");
 153       print_gimple_stmt (dump_file, use_stmt, 0);
 154     }
 155
 156   /* Add PHI arguments for each edge inserting loads of the
 157      addressable operands.  */
 158   FOR_EACH_EDGE (e, ei, bb->preds)
 159     {
 160       tree old_arg, new_var;
 161       gassign *tmp;
 162       location_t locus;
 163
 164       old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
 165       locus = gimple_phi_arg_location_from_edge (phi, e);
 166       while (TREE_CODE (old_arg) == SSA_NAME
 167              && (SSA_NAME_VERSION (old_arg) >= n
 168                  || phivn[SSA_NAME_VERSION (old_arg)].value == NULL_TREE))
 169         {
 170           gimple *def_stmt = SSA_NAME_DEF_STMT (old_arg);
 171           old_arg = gimple_assign_rhs1 (def_stmt);
 172           locus = gimple_location (def_stmt);
 173         }
 174
 175       if (TREE_CODE (old_arg) == SSA_NAME)
 176         {
 177           if (dump_file && (dump_flags & TDF_DETAILS))
 178             {
 179               fprintf (dump_file, "  for edge defining ");
 180               print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e));
 181               fprintf (dump_file, " reusing PHI result ");
 182               print_generic_expr (dump_file,
 183                                   phivn[SSA_NAME_VERSION (old_arg)].value);
 184               fprintf (dump_file, "\n");
 185             }
 186           /* Reuse a formerly created dereference.  */
 187           new_var = phivn[SSA_NAME_VERSION (old_arg)].value;
 188         }
 189       else
 190         {
 191           tree rhs = gimple_assign_rhs1 (use_stmt);
 192           gcc_assert (TREE_CODE (old_arg) == ADDR_EXPR);
 193           if (TREE_CODE (res) == SSA_NAME)
 194             new_var = make_ssa_name (TREE_TYPE (rhs));
 195           else
 196             new_var = unshare_expr (res);
 197           if (!is_gimple_min_invariant (old_arg))
 198             old_arg = PHI_ARG_DEF_FROM_EDGE (phi, e);
 199           else
 200             old_arg = unshare_expr (old_arg);
 201           tmp = gimple_build_assign (new_var,
 202                                      fold_build2 (MEM_REF, TREE_TYPE (rhs),
 203                                                   old_arg,
 204                                                   TREE_OPERAND (rhs, 1)));
 205           gimple_set_location (tmp, locus);
 206
 207           gsi_insert_on_edge (e, tmp);
 208           update_stmt (tmp);
 209
 210           if (dump_file && (dump_flags & TDF_DETAILS))
 211             {
 212               fprintf (dump_file, "  for edge defining ");
 213               print_generic_expr (dump_file, PHI_ARG_DEF_FROM_EDGE (phi, e));
 214               fprintf (dump_file, " inserting load ");
 215               print_gimple_stmt (dump_file, tmp, 0);
 216             }
 217         }
 218
 219       if (new_phi)
 220         add_phi_arg (new_phi, new_var, e, locus);
 221     }
 222
 223   if (new_phi)
 224     {
 225       update_stmt (new_phi);
 226
 227       if (dump_file && (dump_flags & TDF_DETAILS))
 228         print_gimple_stmt (dump_file, new_phi, 0);
 229     }
 230
 231   return res;
 232 }
 233
 234 /* Verify if *idx is available at *DATA.  */
 235
 236 static bool
 237 chk_uses (tree, tree *idx, void *data)
 238 {
 239   basic_block dom = (basic_block) data;
 240   if (TREE_CODE (*idx) == SSA_NAME)
 241     return (SSA_NAME_IS_DEFAULT_DEF (*idx)
 242             || ! dominated_by_p (CDI_DOMINATORS,
 243                                  gimple_bb (SSA_NAME_DEF_STMT (*idx)), dom));
 244   return true;
 245 }
 246
 247 /* Propagate between the phi node arguments of PHI in BB and phi result
 248    users.  For now this matches
 249         # p_2 = PHI <&x, &y>
 250       <Lx>:;
 251         p_3 = p_2;
 252         z_2 = *p_3;
 253    and converts it to
 254         # z_2 = PHI <x, y>
 255       <Lx>:;
 256    Returns true if a transformation was done and edge insertions
 257    need to be committed.  Global data PHIVN and N is used to track
 258    past transformation results.  We need to be especially careful here
 259    with aliasing issues as we are moving memory reads.  */
 260
 261 static bool
 262 propagate_with_phi (basic_block bb, gphi *phi, struct phiprop_d *phivn,
 263                     size_t n)
 264 {
 265   tree ptr = PHI_RESULT (phi);
 266   gimple *use_stmt;
 267   tree res = NULL_TREE;
 268   gimple_stmt_iterator gsi;
 269   imm_use_iterator ui;
 270   use_operand_p arg_p, use;
 271   ssa_op_iter i;
 272   bool phi_inserted;
 273   bool changed;
 274   tree type = NULL_TREE;
 275
 276   if (!POINTER_TYPE_P (TREE_TYPE (ptr))
 277       || (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr)))
 278           && TYPE_MODE (TREE_TYPE (TREE_TYPE (ptr))) == BLKmode))
 279     return false;
 280
 281   /* Check if we can "cheaply" dereference all phi arguments.  */
 282   FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
 283     {
 284       tree arg = USE_FROM_PTR (arg_p);
 285       /* Walk the ssa chain until we reach a ssa name we already
 286          created a value for or we reach a definition of the form
 287          ssa_name_n = &var;  */
 288       while (TREE_CODE (arg) == SSA_NAME
 289              && !SSA_NAME_IS_DEFAULT_DEF (arg)
 290              && (SSA_NAME_VERSION (arg) >= n
 291                  || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
 292         {
 293           gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
 294           if (!gimple_assign_single_p (def_stmt))
 295             return false;
 296           arg = gimple_assign_rhs1 (def_stmt);
 297         }
 298       if (TREE_CODE (arg) != ADDR_EXPR
 299           && !(TREE_CODE (arg) == SSA_NAME
 300                && SSA_NAME_VERSION (arg) < n
 301                && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
 302                && (!type
 303                    || types_compatible_p
 304                        (type, TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value)))
 305                && phivn_valid_p (phivn, arg, bb)))
 306         return false;
 307       if (!type
 308           && TREE_CODE (arg) == SSA_NAME)
 309         type = TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value);
 310     }
 311
 312   /* Find a dereferencing use.  First follow (single use) ssa
 313      copy chains for ptr.  */
 314   while (single_imm_use (ptr, &use, &use_stmt)
 315          && gimple_assign_ssa_name_copy_p (use_stmt))
 316     ptr = gimple_assign_lhs (use_stmt);
 317
 318   /* Replace the first dereference of *ptr if there is one and if we
 319      can move the loads to the place of the ptr phi node.  */
 320   phi_inserted = false;
 321   changed = false;
 322   FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
 323     {
 324       gimple *def_stmt;
 325       tree vuse;
 326
 327       /* Only replace loads in blocks that post-dominate the PHI node.  That
 328          makes sure we don't end up speculating loads.  */
 329       if (!dominated_by_p (CDI_POST_DOMINATORS,
 330                            bb, gimple_bb (use_stmt)))
 331         continue;
 332
 333       /* Check whether this is a load of *ptr.  */
 334       if (!(is_gimple_assign (use_stmt)
 335             && gimple_assign_rhs_code (use_stmt) == MEM_REF
 336             && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr
 337             && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1))
 338             && (!type
 339                 || types_compatible_p
 340                      (TREE_TYPE (gimple_assign_lhs (use_stmt)), type))
 341             /* We cannot replace a load that may throw or is volatile.
 342                For volatiles the transform can change the number of
 343                executions if the load is inside a loop but the address
 344                computations outside (PR91812).  We could relax this
 345                if we guard against that appropriately.  For loads that can
 346                throw we could relax things if the moved loads all are
 347                known to not throw.  */
 348             && !stmt_can_throw_internal (cfun, use_stmt)
 349             && !gimple_has_volatile_ops (use_stmt)))
 350         continue;
 351
 352       /* Check if we can move the loads.  The def stmt of the virtual use
 353          needs to be in a different basic block dominating bb.  When the
 354          def is an edge-inserted one we know it dominates us.  */
 355       vuse = gimple_vuse (use_stmt);
 356       def_stmt = SSA_NAME_DEF_STMT (vuse);
 357       if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
 358           && (gimple_bb (def_stmt) == bb
 359               || (gimple_bb (def_stmt)
 360                   && !dominated_by_p (CDI_DOMINATORS,
 361                                       bb, gimple_bb (def_stmt)))))
 362         goto next;
 363
 364       /* Found a proper dereference with an aggregate copy.  Just
 365          insert aggregate copies on the edges instead.  */
 366       if (!is_gimple_reg_type (TREE_TYPE (gimple_assign_lhs (use_stmt))))
 367         {
 368           if (!gimple_vdef (use_stmt))
 369             goto next;
 370
 371           /* As we replicate the lhs on each incoming edge all
 372              used SSA names have to be available there.  */
 373           if (! for_each_index (gimple_assign_lhs_ptr (use_stmt),
 374                                 chk_uses,
 375                                 get_immediate_dominator (CDI_DOMINATORS,
 376                                                          gimple_bb (phi))))
 377             goto next;
 378
 379           gimple *vuse_stmt;
 380           imm_use_iterator vui;
 381           use_operand_p vuse_p;
 382           /* In order to move the aggregate copies earlier, make sure
 383              there are no statements that could read from memory
 384              aliasing the lhs in between the start of bb and use_stmt.
 385              As we require use_stmt to have a VDEF above, loads after
 386              use_stmt will use a different virtual SSA_NAME.  */
 387           FOR_EACH_IMM_USE_FAST (vuse_p, vui, vuse)
 388             {
 389               vuse_stmt = USE_STMT (vuse_p);
 390               if (vuse_stmt == use_stmt)
 391                 continue;
 392               if (!dominated_by_p (CDI_DOMINATORS,
 393                                    gimple_bb (vuse_stmt), bb))
 394                 continue;
 395               if (ref_maybe_used_by_stmt_p (vuse_stmt,
 396                                             gimple_assign_lhs (use_stmt)))
 397                 goto next;
 398             }
 399
 400           phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 401
 402           /* Remove old stmt.  The phi is taken care of by DCE.  */
 403           gsi = gsi_for_stmt (use_stmt);
 404           /* Unlinking the VDEF here is fine as we are sure that we process
 405              stmts in execution order due to aggregate copies having VDEFs
 406              and we emit loads on the edges in the very same order.
 407              We get multiple copies (or intermediate register loads) handled
 408              only by walking PHIs or immediate uses in a lucky order though,
 409              so we could signal the caller to re-start iterating over PHIs
 410              when we come here which would make it quadratic in the number
 411              of PHIs.  */
 412           unlink_stmt_vdef (use_stmt);
 413           gsi_remove (&gsi, true);
 414
 415           changed = true;
 416         }
 417
 418       /* Found a proper dereference.  Insert a phi node if this
 419          is the first load transformation.  */
 420       else if (!phi_inserted)
 421         {
 422           res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 423           type = TREE_TYPE (res);
 424
 425           /* Remember the value we created for *ptr.  */
 426           phivn[SSA_NAME_VERSION (ptr)].value = res;
 427           phivn[SSA_NAME_VERSION (ptr)].vuse = vuse;
 428
 429           /* Remove old stmt.  The phi is taken care of by DCE, if we
 430              want to delete it here we also have to delete all intermediate
 431              copies.  */
 432           gsi = gsi_for_stmt (use_stmt);
 433           gsi_remove (&gsi, true);
 434
 435           phi_inserted = true;
 436           changed = true;
 437         }
 438       else
 439         {
 440           /* Further replacements are easy, just make a copy out of the
 441              load.  */
 442           gimple_assign_set_rhs1 (use_stmt, res);
 443           update_stmt (use_stmt);
 444           changed = true;
 445         }
 446
 447 next:;
 448       /* Continue searching for a proper dereference.  */
 449     }
 450
 451   return changed;
 452 }
 453
 454 /* Main entry for phiprop pass.  */
 455
 456 namespace {
 457
 458 const pass_data pass_data_phiprop =
 459 {
 460   GIMPLE_PASS, /* type */
 461   "phiprop", /* name */
 462   OPTGROUP_NONE, /* optinfo_flags */
 463   TV_TREE_PHIPROP, /* tv_id */
 464   ( PROP_cfg | PROP_ssa ), /* properties_required */
 465   0, /* properties_provided */
 466   0, /* properties_destroyed */
 467   0, /* todo_flags_start */
 468   TODO_update_ssa, /* todo_flags_finish */
 469 };
 470
 471 class pass_phiprop : public gimple_opt_pass
 472 {
 473 public:
 474   pass_phiprop (gcc::context *ctxt)
 475     : gimple_opt_pass (pass_data_phiprop, ctxt)
 476   {}
 477
 478   /* opt_pass methods: */
 479   bool gate (function *) final override { return flag_tree_phiprop; }
 480   unsigned int execute (function *) final override;
 481
 482 }; // class pass_phiprop
 483
 484 unsigned int
 485 pass_phiprop::execute (function *fun)
 486 {
 487   struct phiprop_d *phivn;
 488   bool did_something = false;
 489   basic_block bb;
 490   gphi_iterator gsi;
 491   unsigned i;
 492   size_t n;
 493
 494   calculate_dominance_info (CDI_DOMINATORS);
 495   calculate_dominance_info (CDI_POST_DOMINATORS);
 496
 497   n = num_ssa_names;
 498   phivn = XCNEWVEC (struct phiprop_d, n);
 499
 500   /* Walk the dominator tree in preorder.  */
 501   auto_vec<basic_block> bbs
 502   = get_all_dominated_blocks (CDI_DOMINATORS,
 503                               single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
 504   FOR_EACH_VEC_ELT (bbs, i, bb)
 505     {
 506       /* Since we're going to move dereferences across predecessor
 507          edges avoid blocks with abnormal predecessors.  */
 508       if (bb_has_abnormal_pred (bb))
 509         continue;
 510       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 511         did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
 512     }
 513
 514   if (did_something)
 515     gsi_commit_edge_inserts ();
 516
 517   free (phivn);
 518
 519   free_dominance_info (CDI_POST_DOMINATORS);
 520
 521   return 0;
 522 }
 523
 524 } // anon namespace
 525
 526 gimple_opt_pass *
 527 make_pass_phiprop (gcc::context *ctxt)
 528 {
 529   return new pass_phiprop (ctxt);
 530 }