gcc/tree-ssa-phiprop.c

   1 /* Backward propagation of indirect loads through PHIs.
   2    Copyright (C) 2007-2017 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   tree type = NULL_TREE;
 274
 275   if (!POINTER_TYPE_P (TREE_TYPE (ptr))
 276       || (!is_gimple_reg_type (TREE_TYPE (TREE_TYPE (ptr)))
 277           && TYPE_MODE (TREE_TYPE (TREE_TYPE (ptr))) == BLKmode))
 278     return false;
 279
 280   /* Check if we can "cheaply" dereference all phi arguments.  */
 281   FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
 282     {
 283       tree arg = USE_FROM_PTR (arg_p);
 284       /* Walk the ssa chain until we reach a ssa name we already
 285          created a value for or we reach a definition of the form
 286          ssa_name_n = &var;  */
 287       while (TREE_CODE (arg) == SSA_NAME
 288              && !SSA_NAME_IS_DEFAULT_DEF (arg)
 289              && (SSA_NAME_VERSION (arg) >= n
 290                  || phivn[SSA_NAME_VERSION (arg)].value == NULL_TREE))
 291         {
 292           gimple *def_stmt = SSA_NAME_DEF_STMT (arg);
 293           if (!gimple_assign_single_p (def_stmt))
 294             return false;
 295           arg = gimple_assign_rhs1 (def_stmt);
 296         }
 297       if (TREE_CODE (arg) != ADDR_EXPR
 298           && !(TREE_CODE (arg) == SSA_NAME
 299                && SSA_NAME_VERSION (arg) < n
 300                && phivn[SSA_NAME_VERSION (arg)].value != NULL_TREE
 301                && (!type
 302                    || types_compatible_p
 303                        (type, TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value)))
 304                && phivn_valid_p (phivn, arg, bb)))
 305         return false;
 306       if (!type
 307           && TREE_CODE (arg) == SSA_NAME)
 308         type = TREE_TYPE (phivn[SSA_NAME_VERSION (arg)].value);
 309     }
 310
 311   /* Find a dereferencing use.  First follow (single use) ssa
 312      copy chains for ptr.  */
 313   while (single_imm_use (ptr, &use, &use_stmt)
 314          && gimple_assign_ssa_name_copy_p (use_stmt))
 315     ptr = gimple_assign_lhs (use_stmt);
 316
 317   /* Replace the first dereference of *ptr if there is one and if we
 318      can move the loads to the place of the ptr phi node.  */
 319   phi_inserted = false;
 320   FOR_EACH_IMM_USE_STMT (use_stmt, ui, ptr)
 321     {
 322       gimple *def_stmt;
 323       tree vuse;
 324
 325       /* Only replace loads in blocks that post-dominate the PHI node.  That
 326          makes sure we don't end up speculating loads.  */
 327       if (!dominated_by_p (CDI_POST_DOMINATORS,
 328                            bb, gimple_bb (use_stmt)))
 329         continue;
 330
 331       /* Check whether this is a load of *ptr.  */
 332       if (!(is_gimple_assign (use_stmt)
 333             && gimple_assign_rhs_code (use_stmt) == MEM_REF
 334             && TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 0) == ptr
 335             && integer_zerop (TREE_OPERAND (gimple_assign_rhs1 (use_stmt), 1))
 336             && (!type
 337                 || types_compatible_p
 338                      (TREE_TYPE (gimple_assign_lhs (use_stmt)), type))
 339             /* We cannot replace a load that may throw or is volatile.  */
 340             && !stmt_can_throw_internal (use_stmt)))
 341         continue;
 342
 343       /* Check if we can move the loads.  The def stmt of the virtual use
 344          needs to be in a different basic block dominating bb.  When the
 345          def is an edge-inserted one we know it dominates us.  */
 346       vuse = gimple_vuse (use_stmt);
 347       def_stmt = SSA_NAME_DEF_STMT (vuse);
 348       if (!SSA_NAME_IS_DEFAULT_DEF (vuse)
 349           && (gimple_bb (def_stmt) == bb
 350               || (gimple_bb (def_stmt)
 351                   && !dominated_by_p (CDI_DOMINATORS,
 352                                       bb, gimple_bb (def_stmt)))))
 353         goto next;
 354
 355       /* Found a proper dereference with an aggregate copy.  Just
 356          insert aggregate copies on the edges instead.  */
 357       if (!is_gimple_reg_type (TREE_TYPE (gimple_assign_lhs (use_stmt))))
 358         {
 359           if (!gimple_vdef (use_stmt))
 360             goto next;
 361
 362           /* As we replicate the lhs on each incoming edge all
 363              used SSA names have to be available there.  */
 364           if (! for_each_index (gimple_assign_lhs_ptr (use_stmt),
 365                                 chk_uses,
 366                                 get_immediate_dominator (CDI_DOMINATORS,
 367                                                          gimple_bb (phi))))
 368             goto next;
 369
 370           gimple *vuse_stmt;
 371           imm_use_iterator vui;
 372           use_operand_p vuse_p;
 373           /* In order to move the aggregate copies earlier, make sure
 374              there are no statements that could read from memory
 375              aliasing the lhs in between the start of bb and use_stmt.
 376              As we require use_stmt to have a VDEF above, loads after
 377              use_stmt will use a different virtual SSA_NAME.  */
 378           FOR_EACH_IMM_USE_FAST (vuse_p, vui, vuse)
 379             {
 380               vuse_stmt = USE_STMT (vuse_p);
 381               if (vuse_stmt == use_stmt)
 382                 continue;
 383               if (!dominated_by_p (CDI_DOMINATORS,
 384                                    gimple_bb (vuse_stmt), bb))
 385                 continue;
 386               if (ref_maybe_used_by_stmt_p (vuse_stmt,
 387                                             gimple_assign_lhs (use_stmt)))
 388                 goto next;
 389             }
 390
 391           phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 392
 393           /* Remove old stmt.  The phi is taken care of by DCE.  */
 394           gsi = gsi_for_stmt (use_stmt);
 395           /* Unlinking the VDEF here is fine as we are sure that we process
 396              stmts in execution order due to aggregate copies having VDEFs
 397              and we emit loads on the edges in the very same order.
 398              We get multiple copies (or intermediate register loads) handled
 399              only by walking PHIs or immediate uses in a lucky order though,
 400              so we could signal the caller to re-start iterating over PHIs
 401              when we come here which would make it quadratic in the number
 402              of PHIs.  */
 403           unlink_stmt_vdef (use_stmt);
 404           gsi_remove (&gsi, true);
 405
 406           phi_inserted = true;
 407         }
 408
 409       /* Found a proper dereference.  Insert a phi node if this
 410          is the first load transformation.  */
 411       else if (!phi_inserted)
 412         {
 413           res = phiprop_insert_phi (bb, phi, use_stmt, phivn, n);
 414           type = TREE_TYPE (res);
 415
 416           /* Remember the value we created for *ptr.  */
 417           phivn[SSA_NAME_VERSION (ptr)].value = res;
 418           phivn[SSA_NAME_VERSION (ptr)].vuse = vuse;
 419
 420           /* Remove old stmt.  The phi is taken care of by DCE, if we
 421              want to delete it here we also have to delete all intermediate
 422              copies.  */
 423           gsi = gsi_for_stmt (use_stmt);
 424           gsi_remove (&gsi, true);
 425
 426           phi_inserted = true;
 427         }
 428       else
 429         {
 430           /* Further replacements are easy, just make a copy out of the
 431              load.  */
 432           gimple_assign_set_rhs1 (use_stmt, res);
 433           update_stmt (use_stmt);
 434         }
 435
 436 next:;
 437       /* Continue searching for a proper dereference.  */
 438     }
 439
 440   return phi_inserted;
 441 }
 442
 443 /* Main entry for phiprop pass.  */
 444
 445 namespace {
 446
 447 const pass_data pass_data_phiprop =
 448 {
 449   GIMPLE_PASS, /* type */
 450   "phiprop", /* name */
 451   OPTGROUP_NONE, /* optinfo_flags */
 452   TV_TREE_PHIPROP, /* tv_id */
 453   ( PROP_cfg | PROP_ssa ), /* properties_required */
 454   0, /* properties_provided */
 455   0, /* properties_destroyed */
 456   0, /* todo_flags_start */
 457   TODO_update_ssa, /* todo_flags_finish */
 458 };
 459
 460 class pass_phiprop : public gimple_opt_pass
 461 {
 462 public:
 463   pass_phiprop (gcc::context *ctxt)
 464     : gimple_opt_pass (pass_data_phiprop, ctxt)
 465   {}
 466
 467   /* opt_pass methods: */
 468   virtual bool gate (function *) { return flag_tree_phiprop; }
 469   virtual unsigned int execute (function *);
 470
 471 }; // class pass_phiprop
 472
 473 unsigned int
 474 pass_phiprop::execute (function *fun)
 475 {
 476   vec<basic_block> bbs;
 477   struct phiprop_d *phivn;
 478   bool did_something = false;
 479   basic_block bb;
 480   gphi_iterator gsi;
 481   unsigned i;
 482   size_t n;
 483
 484   calculate_dominance_info (CDI_DOMINATORS);
 485   calculate_dominance_info (CDI_POST_DOMINATORS);
 486
 487   n = num_ssa_names;
 488   phivn = XCNEWVEC (struct phiprop_d, n);
 489
 490   /* Walk the dominator tree in preorder.  */
 491   bbs = get_all_dominated_blocks (CDI_DOMINATORS,
 492                                   single_succ (ENTRY_BLOCK_PTR_FOR_FN (fun)));
 493   FOR_EACH_VEC_ELT (bbs, i, bb)
 494     for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
 495       did_something |= propagate_with_phi (bb, gsi.phi (), phivn, n);
 496
 497   if (did_something)
 498     gsi_commit_edge_inserts ();
 499
 500   bbs.release ();
 501   free (phivn);
 502
 503   free_dominance_info (CDI_POST_DOMINATORS);
 504
 505   return 0;
 506 }
 507
 508 } // anon namespace
 509
 510 gimple_opt_pass *
 511 make_pass_phiprop (gcc::context *ctxt)
 512 {
 513   return new pass_phiprop (ctxt);
 514 }