gcc/tree-ssa-uncprop.c

   1 /* Routines for discovering and unpropagating edge equivalences.
   2    Copyright (C) 2005-2016 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 (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
 272 /* Main structure for recording equivalences into our hash table.  */
 273 struct equiv_hash_elt
 274 {
 275   /* The value/key of this entry.  */
 276   tree value;
 277
 278   /* List of SSA_NAMEs which have the same value/key.  */
 279   vec<tree> equivalences;
 280 };
 281
 282 /* Global hash table implementing a mapping from invariant values
 283    to a list of SSA_NAMEs which have the same value.  We might be
 284    able to reuse tree-vn for this code.  */
 285 static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
 286
 287 static void uncprop_into_successor_phis (basic_block);
 288
 289 /* Remove the most recently recorded equivalency for VALUE.  */
 290
 291 static void
 292 remove_equivalence (tree value)
 293 {
 294     val_ssa_equiv->get (value)->pop ();
 295 }
 296
 297 /* Record EQUIVALENCE = VALUE into our hash table.  */
 298
 299 static void
 300 record_equiv (tree value, tree equivalence)
 301 {
 302   val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
 303 }
 304
 305 class uncprop_dom_walker : public dom_walker
 306 {
 307 public:
 308   uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
 309
 310   virtual edge before_dom_children (basic_block);
 311   virtual void after_dom_children (basic_block);
 312
 313 private:
 314
 315   /* As we enter each block we record the value for any edge equivalency
 316      leading to this block.  If no such edge equivalency exists, then we
 317      record NULL.  These equivalences are live until we leave the dominator
 318      subtree rooted at the block where we record the equivalency.  */
 319   auto_vec<tree, 2> m_equiv_stack;
 320 };
 321
 322 /* We have finished processing the dominator children of BB, perform
 323    any finalization actions in preparation for leaving this node in
 324    the dominator tree.  */
 325
 326 void
 327 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
 328 {
 329   /* Pop the topmost value off the equiv stack.  */
 330   tree value = m_equiv_stack.pop ();
 331
 332   /* If that value was non-null, then pop the topmost equivalency off
 333      its equivalency stack.  */
 334   if (value != NULL)
 335     remove_equivalence (value);
 336 }
 337
 338 /* Unpropagate values from PHI nodes in successor blocks of BB.  */
 339
 340 static void
 341 uncprop_into_successor_phis (basic_block bb)
 342 {
 343   edge e;
 344   edge_iterator ei;
 345
 346   /* For each successor edge, first temporarily record any equivalence
 347      on that edge.  Then unpropagate values in any PHI nodes at the
 348      destination of the edge.  Then remove the temporary equivalence.  */
 349   FOR_EACH_EDGE (e, ei, bb->succs)
 350     {
 351       gimple_seq phis = phi_nodes (e->dest);
 352       gimple_stmt_iterator gsi;
 353
 354       /* If there are no PHI nodes in this destination, then there is
 355          no sense in recording any equivalences.  */
 356       if (gimple_seq_empty_p (phis))
 357         continue;
 358
 359       /* Record any equivalency associated with E.  */
 360       if (e->aux)
 361         {
 362           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 363           record_equiv (equiv->rhs, equiv->lhs);
 364         }
 365
 366       /* Walk over the PHI nodes, unpropagating values.  */
 367       for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
 368         {
 369           gimple *phi = gsi_stmt (gsi);
 370           tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 371           tree res = PHI_RESULT (phi);
 372
 373           /* If the argument is not an invariant and can be potentially
 374              coalesced with the result, then there's no point in
 375              un-propagating the argument.  */
 376           if (!is_gimple_min_invariant (arg)
 377               && gimple_can_coalesce_p (arg, res))
 378             continue;
 379
 380           /* Lookup this argument's value in the hash table.  */
 381           vec<tree> *equivalences = val_ssa_equiv->get (arg);
 382           if (equivalences)
 383             {
 384               /* Walk every equivalence with the same value.  If we find
 385                  one that can potentially coalesce with the PHI rsult,
 386                  then replace the value in the argument with its equivalent
 387                  SSA_NAME.  Use the most recent equivalence as hopefully
 388                  that results in shortest lifetimes.  */
 389               for (int j = equivalences->length () - 1; j >= 0; j--)
 390                 {
 391                   tree equiv = (*equivalences)[j];
 392
 393                   if (gimple_can_coalesce_p (equiv, res))
 394                     {
 395                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 396                       break;
 397                     }
 398                 }
 399             }
 400         }
 401
 402       /* If we had an equivalence associated with this edge, remove it.  */
 403       if (e->aux)
 404         {
 405           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 406           remove_equivalence (equiv->rhs);
 407         }
 408     }
 409 }
 410
 411 /* Ignoring loop backedges, if BB has precisely one incoming edge then
 412    return that edge.  Otherwise return NULL.  */
 413 static edge
 414 single_incoming_edge_ignoring_loop_edges (basic_block bb)
 415 {
 416   edge retval = NULL;
 417   edge e;
 418   edge_iterator ei;
 419
 420   FOR_EACH_EDGE (e, ei, bb->preds)
 421     {
 422       /* A loop back edge can be identified by the destination of
 423          the edge dominating the source of the edge.  */
 424       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
 425         continue;
 426
 427       /* If we have already seen a non-loop edge, then we must have
 428          multiple incoming non-loop edges and thus we return NULL.  */
 429       if (retval)
 430         return NULL;
 431
 432       /* This is the first non-loop incoming edge we have found.  Record
 433          it.  */
 434       retval = e;
 435     }
 436
 437   return retval;
 438 }
 439
 440 edge
 441 uncprop_dom_walker::before_dom_children (basic_block bb)
 442 {
 443   basic_block parent;
 444   edge e;
 445   bool recorded = false;
 446
 447   /* If this block is dominated by a single incoming edge and that edge
 448      has an equivalency, then record the equivalency and push the
 449      VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
 450   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 451   if (parent)
 452     {
 453       e = single_incoming_edge_ignoring_loop_edges (bb);
 454
 455       if (e && e->src == parent && e->aux)
 456         {
 457           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 458
 459           record_equiv (equiv->rhs, equiv->lhs);
 460           m_equiv_stack.safe_push (equiv->rhs);
 461           recorded = true;
 462         }
 463     }
 464
 465   if (!recorded)
 466     m_equiv_stack.safe_push (NULL_TREE);
 467
 468   uncprop_into_successor_phis (bb);
 469   return NULL;
 470 }
 471
 472 namespace {
 473
 474 const pass_data pass_data_uncprop =
 475 {
 476   GIMPLE_PASS, /* type */
 477   "uncprop", /* name */
 478   OPTGROUP_NONE, /* optinfo_flags */
 479   TV_TREE_SSA_UNCPROP, /* tv_id */
 480   ( PROP_cfg | PROP_ssa ), /* properties_required */
 481   0, /* properties_provided */
 482   0, /* properties_destroyed */
 483   0, /* todo_flags_start */
 484   0, /* todo_flags_finish */
 485 };
 486
 487 class pass_uncprop : public gimple_opt_pass
 488 {
 489 public:
 490   pass_uncprop (gcc::context *ctxt)
 491     : gimple_opt_pass (pass_data_uncprop, ctxt)
 492   {}
 493
 494   /* opt_pass methods: */
 495   opt_pass * clone () { return new pass_uncprop (m_ctxt); }
 496   virtual bool gate (function *) { return flag_tree_dom != 0; }
 497   virtual unsigned int execute (function *);
 498
 499 }; // class pass_uncprop
 500
 501 unsigned int
 502 pass_uncprop::execute (function *fun)
 503 {
 504   basic_block bb;
 505
 506   associate_equivalences_with_edges ();
 507
 508   /* Create our global data structures.  */
 509   val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
 510
 511   /* We're going to do a dominator walk, so ensure that we have
 512      dominance information.  */
 513   calculate_dominance_info (CDI_DOMINATORS);
 514
 515   /* Recursively walk the dominator tree undoing unprofitable
 516      constant/copy propagations.  */
 517   uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
 518
 519   /* we just need to empty elements out of the hash table, and cleanup the
 520     AUX field on the edges.  */
 521   delete val_ssa_equiv;
 522   val_ssa_equiv = NULL;
 523   FOR_EACH_BB_FN (bb, fun)
 524     {
 525       edge e;
 526       edge_iterator ei;
 527
 528       FOR_EACH_EDGE (e, ei, bb->succs)
 529         {
 530           if (e->aux)
 531             {
 532               free (e->aux);
 533               e->aux = NULL;
 534             }
 535         }
 536     }
 537   return 0;
 538 }
 539
 540 } // anon namespace
 541
 542 gimple_opt_pass *
 543 make_pass_uncprop (gcc::context *ctxt)
 544 {
 545   return new pass_uncprop (ctxt);
 546 }