gcc/tree-ssa-phiprop.c

   1 /* Backward propagation of indirect loads through PHIs.
   2    Copyright (C) 2007-2018 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_FROM_IMM_USE_STMT (ui2);
 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       source_location 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             && !stmt_can_throw_internal (use_stmt)))
 343         continue;
 344
 345       /* Check if we can move the loads.  The def stmt of the virtual use
 346          needs to be in a different basic block dominating bb.  When the
 347          def is an edge-inserted one we know it dominates us.  */
 348       vuse = gimple_vuse (use_stmt);
 349       def_stmt = SSA_NAME_DEF_STMT (vuse);
 350       if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
 351           && (gimple_bb (def_stmt) == bb
 352               || (gimple_bb (def_stmt)
 353                   && !dominated_by_p (CDI_DOMINATORS,
 354                                       bb, gimple_bb (def_stmt)))))
 355         goto next;
 356
 357       /* Found a proper dereference with an aggregate copy.  Just
 358          insert aggregate copies on the edges instead.  */
 359       if (!is_gimple_reg_type (TREE_TYPE (gimple_assign_lhs (use_stmt))))
 360         {
 361           if (!gimple_vdef (use_stmt))
 362             goto next;
 363
 364           /* As we replicate the lhs on each incoming edge all
 365              used SSA names have to be available there.  */
 366           if (! for_each_index (gimple_assign_lhs_ptr (use_stmt),
 367                                 chk_uses,
 368                                 get_immediate_dominator (CDI_DOMINATORS,
 369                                                          gimple_bb (phi))))
 370             goto next;
 371
 372           gimple *vuse_stmt;
 373           imm_use_iterator vui;
 374           use_operand_p vuse_p;
 375           /* In order to move the aggregate copies earlier, make sure
 376              there are no statements that could read from memory
 377              aliasing the lhs in between the start of bb and use_stmt.
 378              As we require use_stmt to have a VDEF above, loads after
 379              use_stmt will use a different virtual SSA_NAME.  */
 380           FOR_EACH_IMM_USE_FAST (vuse_p, vui, vuse)
 381             {
 382               vuse_stmt = USE_STMT (vuse_p);
 383               if (vuse_stmt == use_stmt)
 384                 continue;
 385               if (!dominated_by_p (CDI_DOMINATORS,
 386                                    gimple_bb (vuse_stmt), bb))
 387                 continue;
 388               if (ref_maybe_used_by_stmt_p (vuse_stmt,
 389                                             gimple_assign_lhs (use_stmt)))
 390                 goto next;
 391             }
 392
 393           phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 394
 395           /* Remove old stmt.  The phi is taken care of by DCE.  */
 396           gsi = gsi_for_stmt (use_stmt);
 397           /* Unlinking the VDEF here is fine as we are sure that we process
 398              stmts in execution order due to aggregate copies having VDEFs
 399              and we emit loads on the edges in the very same order.
 400              We get multiple copies (or intermediate register loads) handled
 401              only by walking PHIs or immediate uses in a lucky order though,
 402              so we could signal the caller to re-start iterating over PHIs
 403              when we come here which would make it quadratic in the number
 404              of PHIs.  */
 405           unlink_stmt_vdef (use_stmt);
 406           gsi_remove (&gsi, true);
 407
 408           changed = true;
 409         }
 410
 411       /* Found a proper dereference.  Insert a phi node if this
 412          is the first load transformation.  */
 413       else if (!phi_inserted)
 414         {
 415           res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 416           type = TREE_TYPE (res);
 417
 418           /* Remember the value we created for *ptr.  */
 419           phivn[SSA_NAME_VERSION (ptr)].value = res;
 420           phivn[SSA_NAME_VERSION (ptr)].vuse = vuse;
 421
 422           /* Remove old stmt.  The phi is taken care of by DCE, if we
 423              want to delete it here we also have to delete all intermediate
 424              copies.  */
 425           gsi = gsi_for_stmt (use_stmt);
 426           gsi_remove (&gsi, true);
 427
 428           phi_inserted = true;
 429           changed = true;
 430         }
 431       else
 432         {
 433           /* Further replacements are easy, just make a copy out of the
 434              load.  */
 435           gimple_assign_set_rhs1 (use_stmt, res);
 436           update_stmt (use_stmt);
 437           changed = true;
 438         }
 439
 440 next:;
 441       /* Continue searching for a proper dereference.  */
 442     }
 443
 444   return changed;
 445 }
 446
 447 /* Main entry for phiprop pass.  */
 448
 449 namespace {
 450
 451 const pass_data pass_data_phiprop =
 452 {
 453   GIMPLE_PASS, /* type */
 454   "phiprop", /* name */
 455   OPTGROUP_NONE, /* optinfo_flags */
 456   TV_TREE_PHIPROP, /* tv_id */
 457   ( PROP_cfg | PROP_ssa ), /* properties_required */
 458   0, /* properties_provided */
 459   0, /* properties_destroyed */
 460   0, /* todo_flags_start */
 461   TODO_update_ssa, /* todo_flags_finish */
 462 };
 463
 464 class pass_phiprop : public gimple_opt_pass
 465 {
 466 public:
 467   pass_phiprop (gcc::context *ctxt)
 468     : gimple_opt_pass (pass_data_phiprop, ctxt)
 469   {}
 470
 471   /* opt_pass methods: */
 472   virtual bool gate (function *) { return flag_tree_phiprop; }
 473   virtual unsigned int execute (function *);
 474
 475 }; // class pass_phiprop
 476
 477 unsigned int
 478 pass_phiprop::execute (function *fun)
 479 {
 480   vec<basic_block> bbs;
 481   struct phiprop_d *phivn;
 482   bool did_something = false;
 483   basic_block bb;
 484   gphi_iterator gsi;
 485   unsigned i;
 486   size_t n;
 487
 488   calculate_dominance_info (CDI_DOMINATORS);
 489   calculate_dominance_info (CDI_POST_DOMINATORS);
 490
 491   n = num_ssa_names;
 492   phivn = XCNEWVEC (struct phiprop_d, n);
 493
 494   /* Walk the dominator tree in preorder.  */
 495   bbs = get_all_dominated_blocks (CDI_DOMINATORS,
 496                                   single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
 497   FOR_EACH_VEC_ELT (bbs, i, bb)
 498     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 499       did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
 500
 501   if (did_something)
 502     gsi_commit_edge_inserts ();
 503
 504   bbs.release ();
 505   free (phivn);
 506
 507   free_dominance_info (CDI_POST_DOMINATORS);
 508
 509   return 0;
 510 }
 511
 512 } // anon namespace
 513
 514 gimple_opt_pass *
 515 make_pass_phiprop (gcc::context *ctxt)
 516 {
 517   return new pass_phiprop (ctxt);
 518 }