gcc/tree-ssa-phiprop.cc

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