gcc/tree-ssa-phiprop.c

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