gcc/tree-ssa-uncprop.c

   1 /* Routines for discovering and unpropagating edge equivalences.
   2    Copyright (C) 2005-2019 Free Software Foundation, Inc.
   3
   4 This file is part of GCC.
   5
   6 GCC is free software; you can redistribute it and/or modify
   7 it under the terms of the GNU General Public License as published by
   8 the Free Software Foundation; either version 3, or (at your option)
   9 any later version.
  10
  11 GCC is distributed in the hope that it will be useful,
  12 but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 GNU General Public License for more details.
  15
  16 You should have received a copy of the GNU General Public License
  17 along with GCC; see the file COPYING3.  If not see
  18 <http://www.gnu.org/licenses/>.  */
  19
  20 #include "config.h"
  21 #include "system.h"
  22 #include "coretypes.h"
  23 #include "backend.h"
  24 #include "tree.h"
  25 #include "gimple.h"
  26 #include "tree-pass.h"
  27 #include "ssa.h"
  28 #include "fold-const.h"
  29 #include "cfganal.h"
  30 #include "gimple-iterator.h"
  31 #include "tree-cfg.h"
  32 #include "domwalk.h"
  33 #include "tree-hash-traits.h"
  34 #include "tree-ssa-live.h"
  35 #include "tree-ssa-coalesce.h"
  36
  37 /* The basic structure describing an equivalency created by traversing
  38    an edge.  Traversing the edge effectively means that we can assume
  39    that we've seen an assignment LHS = RHS.  */
  40 struct edge_equivalency
  41 {
  42   tree rhs;
  43   tree lhs;
  44 };
  45
  46 /* This routine finds and records edge equivalences for every edge
  47    in the CFG.
  48
  49    When complete, each edge that creates an equivalency will have an
  50    EDGE_EQUIVALENCY structure hanging off the edge's AUX field.
  51    The caller is responsible for freeing the AUX fields.  */
  52
  53 static void
  54 associate_equivalences_with_edges (void)
  55 {
  56   basic_block bb;
  57
  58   /* Walk over each block.  If the block ends with a control statement,
  59      then it might create a useful equivalence.  */
  60   FOR_EACH_BB_FN (bb, cfun)
  61     {
  62       gimple_stmt_iterator gsi = gsi_last_bb (bb);
  63       gimple *stmt;
  64
  65       /* If the block does not end with a COND_EXPR or SWITCH_EXPR
  66          then there is nothing to do.  */
  67       if (gsi_end_p (gsi))
  68         continue;
  69
  70       stmt = gsi_stmt (gsi);
  71
  72       if (!stmt)
  73         continue;
  74
  75       /* A COND_EXPR may create an equivalency in a variety of different
  76          ways.  */
  77       if (gimple_code (stmt) == GIMPLE_COND)
  78         {
  79           edge true_edge;
  80           edge false_edge;
  81           struct edge_equivalency *equivalency;
  82           enum tree_code code = gimple_cond_code (stmt);
  83
  84           extract_true_false_edges_from_block (bb, &true_edge, &false_edge);
  85
  86           /* Equality tests may create one or two equivalences.  */
  87           if (code == EQ_EXPR || code == NE_EXPR)
  88             {
  89               tree op0 = gimple_cond_lhs (stmt);
  90               tree op1 = gimple_cond_rhs (stmt);
  91
  92               /* Special case comparing booleans against a constant as we
  93                  know the value of OP0 on both arms of the branch.  i.e., we
  94                  can record an equivalence for OP0 rather than COND.  */
  95               if (TREE_CODE (op0) == SSA_NAME
  96                   && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
  97                   && ssa_name_has_boolean_range (op0)
  98                   && is_gimple_min_invariant (op1)
  99                   && (integer_zerop (op1) || integer_onep (op1)))
 100                 {
 101                   tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
 102                   tree false_val = constant_boolean_node (false,
 103                                                           TREE_TYPE (op0));
 104                   if (code == EQ_EXPR)
 105                     {
 106                       equivalency = XNEW (struct edge_equivalency);
 107                       equivalency->lhs = op0;
 108                       equivalency->rhs = (integer_zerop (op1)
 109                                           ? false_val
 110                                           : true_val);
 111                       true_edge->aux = equivalency;
 112
 113                       equivalency = XNEW (struct edge_equivalency);
 114                       equivalency->lhs = op0;
 115                       equivalency->rhs = (integer_zerop (op1)
 116                                           ? true_val
 117                                           : false_val);
 118                       false_edge->aux = equivalency;
 119                     }
 120                   else
 121                     {
 122                       equivalency = XNEW (struct edge_equivalency);
 123                       equivalency->lhs = op0;
 124                       equivalency->rhs = (integer_zerop (op1)
 125                                           ? true_val
 126                                           : false_val);
 127                       true_edge->aux = equivalency;
 128
 129                       equivalency = XNEW (struct edge_equivalency);
 130                       equivalency->lhs = op0;
 131                       equivalency->rhs = (integer_zerop (op1)
 132                                           ? false_val
 133                                           : true_val);
 134                       false_edge->aux = equivalency;
 135                     }
 136                 }
 137
 138               else if (TREE_CODE (op0) == SSA_NAME
 139                        && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
 140                        && (is_gimple_min_invariant (op1)
 141                            || (TREE_CODE (op1) == SSA_NAME
 142                                && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
 143                 {
 144                   /* For IEEE, -0.0 == 0.0, so we don't necessarily know
 145                      the sign of a variable compared against zero.  If
 146                      we're honoring signed zeros, then we cannot record
 147                      this value unless we know that the value is nonzero.  */
 148                   if (HONOR_SIGNED_ZEROS (op0)
 149                       && (TREE_CODE (op1) != REAL_CST
 150                           || real_equal (&dconst0, &TREE_REAL_CST (op1))))
 151                     continue;
 152
 153                   equivalency = XNEW (struct edge_equivalency);
 154                   equivalency->lhs = op0;
 155                   equivalency->rhs = op1;
 156                   if (code == EQ_EXPR)
 157                     true_edge->aux = equivalency;
 158                   else
 159                     false_edge->aux = equivalency;
 160
 161                 }
 162             }
 163
 164           /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
 165         }
 166
 167       /* For a SWITCH_EXPR, a case label which represents a single
 168          value and which is the only case label which reaches the
 169          target block creates an equivalence.  */
 170       else if (gimple_code (stmt) == GIMPLE_SWITCH)
 171         {
 172           gswitch *switch_stmt = as_a <gswitch *> (stmt);
 173           tree cond = gimple_switch_index (switch_stmt);
 174
 175           if (TREE_CODE (cond) == SSA_NAME
 176               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
 177             {
 178               int i, n_labels = gimple_switch_num_labels (switch_stmt);
 179               tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
 180
 181               /* Walk over the case label vector.  Record blocks
 182                  which are reached by a single case label which represents
 183                  a single value.  */
 184               for (i = 0; i < n_labels; i++)
 185                 {
 186                   tree label = gimple_switch_label (switch_stmt, i);
 187                   basic_block bb = label_to_block (cfun, CASE_LABEL (label));
 188
 189                   if (CASE_HIGH (label)
 190                       || !CASE_LOW (label)
 191                       || info[bb->index])
 192                     info[bb->index] = error_mark_node;
 193                   else
 194                     info[bb->index] = label;
 195                 }
 196
 197               /* Now walk over the blocks to determine which ones were
 198                  marked as being reached by a useful case label.  */
 199               for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
 200                 {
 201                   tree node = info[i];
 202
 203                   if (node != NULL
 204                       && node != error_mark_node)
 205                     {
 206                       tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
 207                       struct edge_equivalency *equivalency;
 208
 209                       /* Record an equivalency on the edge from BB to basic
 210                          block I.  */
 211                       equivalency = XNEW (struct edge_equivalency);
 212                       equivalency->rhs = x;
 213                       equivalency->lhs = cond;
 214                       find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
 215                         equivalency;
 216                     }
 217                 }
 218               free (info);
 219             }
 220         }
 221
 222     }
 223 }
 224
 225
 226 /* Translating out of SSA sometimes requires inserting copies and
 227    constant initializations on edges to eliminate PHI nodes.
 228
 229    In some cases those copies and constant initializations are
 230    redundant because the target already has the value on the
 231    RHS of the assignment.
 232
 233    We previously tried to catch these cases after translating
 234    out of SSA form.  However, that code often missed cases.  Worse
 235    yet, the cases it missed were also often missed by the RTL
 236    optimizers.  Thus the resulting code had redundant instructions.
 237
 238    This pass attempts to detect these situations before translating
 239    out of SSA form.
 240
 241    The key concept that this pass is built upon is that these
 242    redundant copies and constant initializations often occur
 243    due to constant/copy propagating equivalences resulting from
 244    COND_EXPRs and SWITCH_EXPRs.
 245
 246    We want to do those propagations as they can sometimes allow
 247    the SSA optimizers to do a better job.  However, in the cases
 248    where such propagations do not result in further optimization,
 249    we would like to "undo" the propagation to avoid the redundant
 250    copies and constant initializations.
 251
 252    This pass works by first associating equivalences with edges in
 253    the CFG.  For example, the edge leading from a SWITCH_EXPR to
 254    its associated CASE_LABEL will have an equivalency between
 255    SWITCH_COND and the value in the case label.
 256
 257    Once we have found the edge equivalences, we proceed to walk
 258    the CFG in dominator order.  As we traverse edges we record
 259    equivalences associated with those edges we traverse.
 260
 261    When we encounter a PHI node, we walk its arguments to see if we
 262    have an equivalence for the PHI argument.  If so, then we replace
 263    the argument.
 264
 265    Equivalences are looked up based on their value (think of it as
 266    the RHS of an assignment).   A value may be an SSA_NAME or an
 267    invariant.  We may have several SSA_NAMEs with the same value,
 268    so with each value we have a list of SSA_NAMEs that have the
 269    same value.  */
 270
 271 typedef hash_map<tree_operand_hash, auto_vec<tree> > val_ssa_equiv_t;
 272
 273 /* Global hash table implementing a mapping from invariant values
 274    to a list of SSA_NAMEs which have the same value.  We might be
 275    able to reuse tree-vn for this code.  */
 276 val_ssa_equiv_t *val_ssa_equiv;
 277
 278 static void uncprop_into_successor_phis (basic_block);
 279
 280 /* Remove the most recently recorded equivalency for VALUE.  */
 281
 282 static void
 283 remove_equivalence (tree value)
 284 {
 285     val_ssa_equiv->get (value)->pop ();
 286 }
 287
 288 /* Record EQUIVALENCE = VALUE into our hash table.  */
 289
 290 static void
 291 record_equiv (tree value, tree equivalence)
 292 {
 293   val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
 294 }
 295
 296 class uncprop_dom_walker : public dom_walker
 297 {
 298 public:
 299   uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
 300
 301   virtual edge before_dom_children (basic_block);
 302   virtual void after_dom_children (basic_block);
 303
 304 private:
 305
 306   /* As we enter each block we record the value for any edge equivalency
 307      leading to this block.  If no such edge equivalency exists, then we
 308      record NULL.  These equivalences are live until we leave the dominator
 309      subtree rooted at the block where we record the equivalency.  */
 310   auto_vec<tree, 2> m_equiv_stack;
 311 };
 312
 313 /* We have finished processing the dominator children of BB, perform
 314    any finalization actions in preparation for leaving this node in
 315    the dominator tree.  */
 316
 317 void
 318 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
 319 {
 320   /* Pop the topmost value off the equiv stack.  */
 321   tree value = m_equiv_stack.pop ();
 322
 323   /* If that value was non-null, then pop the topmost equivalency off
 324      its equivalency stack.  */
 325   if (value != NULL)
 326     remove_equivalence (value);
 327 }
 328
 329 /* Unpropagate values from PHI nodes in successor blocks of BB.  */
 330
 331 static void
 332 uncprop_into_successor_phis (basic_block bb)
 333 {
 334   edge e;
 335   edge_iterator ei;
 336
 337   /* For each successor edge, first temporarily record any equivalence
 338      on that edge.  Then unpropagate values in any PHI nodes at the
 339      destination of the edge.  Then remove the temporary equivalence.  */
 340   FOR_EACH_EDGE (e, ei, bb->succs)
 341     {
 342       gimple_seq phis = phi_nodes (e->dest);
 343       gimple_stmt_iterator gsi;
 344
 345       /* If there are no PHI nodes in this destination, then there is
 346          no sense in recording any equivalences.  */
 347       if (gimple_seq_empty_p (phis))
 348         continue;
 349
 350       /* Record any equivalency associated with E.  */
 351       if (e->aux)
 352         {
 353           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 354           record_equiv (equiv->rhs, equiv->lhs);
 355         }
 356
 357       /* Walk over the PHI nodes, unpropagating values.  */
 358       for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
 359         {
 360           gimple *phi = gsi_stmt (gsi);
 361           tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 362           tree res = PHI_RESULT (phi);
 363
 364           /* If the argument is not an invariant and can be potentially
 365              coalesced with the result, then there's no point in
 366              un-propagating the argument.  */
 367           if (!is_gimple_min_invariant (arg)
 368               && gimple_can_coalesce_p (arg, res))
 369             continue;
 370
 371           /* Lookup this argument's value in the hash table.  */
 372           vec<tree> *equivalences = val_ssa_equiv->get (arg);
 373           if (equivalences)
 374             {
 375               /* Walk every equivalence with the same value.  If we find
 376                  one that can potentially coalesce with the PHI rsult,
 377                  then replace the value in the argument with its equivalent
 378                  SSA_NAME.  Use the most recent equivalence as hopefully
 379                  that results in shortest lifetimes.  */
 380               for (int j = equivalences->length () - 1; j >= 0; j--)
 381                 {
 382                   tree equiv = (*equivalences)[j];
 383
 384                   if (gimple_can_coalesce_p (equiv, res))
 385                     {
 386                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 387                       break;
 388                     }
 389                 }
 390             }
 391         }
 392
 393       /* If we had an equivalence associated with this edge, remove it.  */
 394       if (e->aux)
 395         {
 396           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 397           remove_equivalence (equiv->rhs);
 398         }
 399     }
 400 }
 401
 402 edge
 403 uncprop_dom_walker::before_dom_children (basic_block bb)
 404 {
 405   basic_block parent;
 406   bool recorded = false;
 407
 408   /* If this block is dominated by a single incoming edge and that edge
 409      has an equivalency, then record the equivalency and push the
 410      VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
 411   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 412   if (parent)
 413     {
 414       edge e = single_pred_edge_ignoring_loop_edges (bb, false);
 415
 416       if (e && e->src == parent && e->aux)
 417         {
 418           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 419
 420           record_equiv (equiv->rhs, equiv->lhs);
 421           m_equiv_stack.safe_push (equiv->rhs);
 422           recorded = true;
 423         }
 424     }
 425
 426   if (!recorded)
 427     m_equiv_stack.safe_push (NULL_TREE);
 428
 429   uncprop_into_successor_phis (bb);
 430   return NULL;
 431 }
 432
 433 namespace {
 434
 435 const pass_data pass_data_uncprop =
 436 {
 437   GIMPLE_PASS, /* type */
 438   "uncprop", /* name */
 439   OPTGROUP_NONE, /* optinfo_flags */
 440   TV_TREE_SSA_UNCPROP, /* tv_id */
 441   ( PROP_cfg | PROP_ssa ), /* properties_required */
 442   0, /* properties_provided */
 443   0, /* properties_destroyed */
 444   0, /* todo_flags_start */
 445   0, /* todo_flags_finish */
 446 };
 447
 448 class pass_uncprop : public gimple_opt_pass
 449 {
 450 public:
 451   pass_uncprop (gcc::context *ctxt)
 452     : gimple_opt_pass (pass_data_uncprop, ctxt)
 453   {}
 454
 455   /* opt_pass methods: */
 456   opt_pass * clone () { return new pass_uncprop (m_ctxt); }
 457   virtual bool gate (function *) { return flag_tree_dom != 0; }
 458   virtual unsigned int execute (function *);
 459
 460 }; // class pass_uncprop
 461
 462 unsigned int
 463 pass_uncprop::execute (function *fun)
 464 {
 465   basic_block bb;
 466
 467   associate_equivalences_with_edges ();
 468
 469   /* Create our global data structures.  */
 470   val_ssa_equiv = new val_ssa_equiv_t (1024);
 471
 472   /* We're going to do a dominator walk, so ensure that we have
 473      dominance information.  */
 474   calculate_dominance_info (CDI_DOMINATORS);
 475
 476   /* Recursively walk the dominator tree undoing unprofitable
 477      constant/copy propagations.  */
 478   uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
 479
 480   /* we just need to empty elements out of the hash table, and cleanup the
 481     AUX field on the edges.  */
 482   delete val_ssa_equiv;
 483   val_ssa_equiv = NULL;
 484   FOR_EACH_BB_FN (bb, fun)
 485     {
 486       edge e;
 487       edge_iterator ei;
 488
 489       FOR_EACH_EDGE (e, ei, bb->succs)
 490         {
 491           if (e->aux)
 492             {
 493               free (e->aux);
 494               e->aux = NULL;
 495             }
 496         }
 497     }
 498   return 0;
 499 }
 500
 501 } // anon namespace
 502
 503 gimple_opt_pass *
 504 make_pass_uncprop (gcc::context *ctxt)
 505 {
 506   return new pass_uncprop (ctxt);
 507 }