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                 {
 100                   tree true_val = constant_boolean_node (true, TREE_TYPE (op0));
 101                   tree false_val = constant_boolean_node (false,
 102                                                           TREE_TYPE (op0));
 103                   if (code == EQ_EXPR)
 104                     {
 105                       equivalency = XNEW (struct edge_equivalency);
 106                       equivalency->lhs = op0;
 107                       equivalency->rhs = (integer_zerop (op1)
 108                                           ? false_val
 109                                           : true_val);
 110                       true_edge->aux = equivalency;
 111
 112                       equivalency = XNEW (struct edge_equivalency);
 113                       equivalency->lhs = op0;
 114                       equivalency->rhs = (integer_zerop (op1)
 115                                           ? true_val
 116                                           : false_val);
 117                       false_edge->aux = equivalency;
 118                     }
 119                   else
 120                     {
 121                       equivalency = XNEW (struct edge_equivalency);
 122                       equivalency->lhs = op0;
 123                       equivalency->rhs = (integer_zerop (op1)
 124                                           ? true_val
 125                                           : false_val);
 126                       true_edge->aux = equivalency;
 127
 128                       equivalency = XNEW (struct edge_equivalency);
 129                       equivalency->lhs = op0;
 130                       equivalency->rhs = (integer_zerop (op1)
 131                                           ? false_val
 132                                           : true_val);
 133                       false_edge->aux = equivalency;
 134                     }
 135                 }
 136
 137               else if (TREE_CODE (op0) == SSA_NAME
 138                        && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op0)
 139                        && (is_gimple_min_invariant (op1)
 140                            || (TREE_CODE (op1) == SSA_NAME
 141                                && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op1))))
 142                 {
 143                   /* For IEEE, -0.0 == 0.0, so we don't necessarily know
 144                      the sign of a variable compared against zero.  If
 145                      we're honoring signed zeros, then we cannot record
 146                      this value unless we know that the value is nonzero.  */
 147                   if (HONOR_SIGNED_ZEROS (op0)
 148                       && (TREE_CODE (op1) != REAL_CST
 149                           || real_equal (&dconst0, &TREE_REAL_CST (op1))))
 150                     continue;
 151
 152                   equivalency = XNEW (struct edge_equivalency);
 153                   equivalency->lhs = op0;
 154                   equivalency->rhs = op1;
 155                   if (code == EQ_EXPR)
 156                     true_edge->aux = equivalency;
 157                   else
 158                     false_edge->aux = equivalency;
 159
 160                 }
 161             }
 162
 163           /* ??? TRUTH_NOT_EXPR can create an equivalence too.  */
 164         }
 165
 166       /* For a SWITCH_EXPR, a case label which represents a single
 167          value and which is the only case label which reaches the
 168          target block creates an equivalence.  */
 169       else if (gimple_code (stmt) == GIMPLE_SWITCH)
 170         {
 171           gswitch *switch_stmt = as_a <gswitch *> (stmt);
 172           tree cond = gimple_switch_index (switch_stmt);
 173
 174           if (TREE_CODE (cond) == SSA_NAME
 175               && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (cond))
 176             {
 177               int i, n_labels = gimple_switch_num_labels (switch_stmt);
 178               tree *info = XCNEWVEC (tree, last_basic_block_for_fn (cfun));
 179
 180               /* Walk over the case label vector.  Record blocks
 181                  which are reached by a single case label which represents
 182                  a single value.  */
 183               for (i = 0; i < n_labels; i++)
 184                 {
 185                   tree label = gimple_switch_label (switch_stmt, i);
 186                   basic_block bb = label_to_block (CASE_LABEL (label));
 187
 188                   if (CASE_HIGH (label)
 189                       || !CASE_LOW (label)
 190                       || info[bb->index])
 191                     info[bb->index] = error_mark_node;
 192                   else
 193                     info[bb->index] = label;
 194                 }
 195
 196               /* Now walk over the blocks to determine which ones were
 197                  marked as being reached by a useful case label.  */
 198               for (i = 0; i < n_basic_blocks_for_fn (cfun); i++)
 199                 {
 200                   tree node = info[i];
 201
 202                   if (node != NULL
 203                       && node != error_mark_node)
 204                     {
 205                       tree x = fold_convert (TREE_TYPE (cond), CASE_LOW (node));
 206                       struct edge_equivalency *equivalency;
 207
 208                       /* Record an equivalency on the edge from BB to basic
 209                          block I.  */
 210                       equivalency = XNEW (struct edge_equivalency);
 211                       equivalency->rhs = x;
 212                       equivalency->lhs = cond;
 213                       find_edge (bb, BASIC_BLOCK_FOR_FN (cfun, i))->aux =
 214                         equivalency;
 215                     }
 216                 }
 217               free (info);
 218             }
 219         }
 220
 221     }
 222 }
 223
 224
 225 /* Translating out of SSA sometimes requires inserting copies and
 226    constant initializations on edges to eliminate PHI nodes.
 227
 228    In some cases those copies and constant initializations are
 229    redundant because the target already has the value on the
 230    RHS of the assignment.
 231
 232    We previously tried to catch these cases after translating
 233    out of SSA form.  However, that code often missed cases.  Worse
 234    yet, the cases it missed were also often missed by the RTL
 235    optimizers.  Thus the resulting code had redundant instructions.
 236
 237    This pass attempts to detect these situations before translating
 238    out of SSA form.
 239
 240    The key concept that this pass is built upon is that these
 241    redundant copies and constant initializations often occur
 242    due to constant/copy propagating equivalences resulting from
 243    COND_EXPRs and SWITCH_EXPRs.
 244
 245    We want to do those propagations as they can sometimes allow
 246    the SSA optimizers to do a better job.  However, in the cases
 247    where such propagations do not result in further optimization,
 248    we would like to "undo" the propagation to avoid the redundant
 249    copies and constant initializations.
 250
 251    This pass works by first associating equivalences with edges in
 252    the CFG.  For example, the edge leading from a SWITCH_EXPR to
 253    its associated CASE_LABEL will have an equivalency between
 254    SWITCH_COND and the value in the case label.
 255
 256    Once we have found the edge equivalences, we proceed to walk
 257    the CFG in dominator order.  As we traverse edges we record
 258    equivalences associated with those edges we traverse.
 259
 260    When we encounter a PHI node, we walk its arguments to see if we
 261    have an equivalence for the PHI argument.  If so, then we replace
 262    the argument.
 263
 264    Equivalences are looked up based on their value (think of it as
 265    the RHS of an assignment).   A value may be an SSA_NAME or an
 266    invariant.  We may have several SSA_NAMEs with the same value,
 267    so with each value we have a list of SSA_NAMEs that have the
 268    same value.  */
 269
 270
 271 /* Main structure for recording equivalences into our hash table.  */
 272 struct equiv_hash_elt
 273 {
 274   /* The value/key of this entry.  */
 275   tree value;
 276
 277   /* List of SSA_NAMEs which have the same value/key.  */
 278   vec<tree> equivalences;
 279 };
 280
 281 /* Global hash table implementing a mapping from invariant values
 282    to a list of SSA_NAMEs which have the same value.  We might be
 283    able to reuse tree-vn for this code.  */
 284 static hash_map<tree, auto_vec<tree> > *val_ssa_equiv;
 285
 286 static void uncprop_into_successor_phis (basic_block);
 287
 288 /* Remove the most recently recorded equivalency for VALUE.  */
 289
 290 static void
 291 remove_equivalence (tree value)
 292 {
 293     val_ssa_equiv->get (value)->pop ();
 294 }
 295
 296 /* Record EQUIVALENCE = VALUE into our hash table.  */
 297
 298 static void
 299 record_equiv (tree value, tree equivalence)
 300 {
 301   val_ssa_equiv->get_or_insert (value).safe_push (equivalence);
 302 }
 303
 304 class uncprop_dom_walker : public dom_walker
 305 {
 306 public:
 307   uncprop_dom_walker (cdi_direction direction) : dom_walker (direction) {}
 308
 309   virtual edge before_dom_children (basic_block);
 310   virtual void after_dom_children (basic_block);
 311
 312 private:
 313
 314   /* As we enter each block we record the value for any edge equivalency
 315      leading to this block.  If no such edge equivalency exists, then we
 316      record NULL.  These equivalences are live until we leave the dominator
 317      subtree rooted at the block where we record the equivalency.  */
 318   auto_vec<tree, 2> m_equiv_stack;
 319 };
 320
 321 /* We have finished processing the dominator children of BB, perform
 322    any finalization actions in preparation for leaving this node in
 323    the dominator tree.  */
 324
 325 void
 326 uncprop_dom_walker::after_dom_children (basic_block bb ATTRIBUTE_UNUSED)
 327 {
 328   /* Pop the topmost value off the equiv stack.  */
 329   tree value = m_equiv_stack.pop ();
 330
 331   /* If that value was non-null, then pop the topmost equivalency off
 332      its equivalency stack.  */
 333   if (value != NULL)
 334     remove_equivalence (value);
 335 }
 336
 337 /* Unpropagate values from PHI nodes in successor blocks of BB.  */
 338
 339 static void
 340 uncprop_into_successor_phis (basic_block bb)
 341 {
 342   edge e;
 343   edge_iterator ei;
 344
 345   /* For each successor edge, first temporarily record any equivalence
 346      on that edge.  Then unpropagate values in any PHI nodes at the
 347      destination of the edge.  Then remove the temporary equivalence.  */
 348   FOR_EACH_EDGE (e, ei, bb->succs)
 349     {
 350       gimple_seq phis = phi_nodes (e->dest);
 351       gimple_stmt_iterator gsi;
 352
 353       /* If there are no PHI nodes in this destination, then there is
 354          no sense in recording any equivalences.  */
 355       if (gimple_seq_empty_p (phis))
 356         continue;
 357
 358       /* Record any equivalency associated with E.  */
 359       if (e->aux)
 360         {
 361           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 362           record_equiv (equiv->rhs, equiv->lhs);
 363         }
 364
 365       /* Walk over the PHI nodes, unpropagating values.  */
 366       for (gsi = gsi_start (phis) ; !gsi_end_p (gsi); gsi_next (&gsi))
 367         {
 368           gimple *phi = gsi_stmt (gsi);
 369           tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 370           tree res = PHI_RESULT (phi);
 371
 372           /* If the argument is not an invariant and can be potentially
 373              coalesced with the result, then there's no point in
 374              un-propagating the argument.  */
 375           if (!is_gimple_min_invariant (arg)
 376               && gimple_can_coalesce_p (arg, res))
 377             continue;
 378
 379           /* Lookup this argument's value in the hash table.  */
 380           vec<tree> *equivalences = val_ssa_equiv->get (arg);
 381           if (equivalences)
 382             {
 383               /* Walk every equivalence with the same value.  If we find
 384                  one that can potentially coalesce with the PHI rsult,
 385                  then replace the value in the argument with its equivalent
 386                  SSA_NAME.  Use the most recent equivalence as hopefully
 387                  that results in shortest lifetimes.  */
 388               for (int j = equivalences->length () - 1; j >= 0; j--)
 389                 {
 390                   tree equiv = (*equivalences)[j];
 391
 392                   if (gimple_can_coalesce_p (equiv, res))
 393                     {
 394                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 395                       break;
 396                     }
 397                 }
 398             }
 399         }
 400
 401       /* If we had an equivalence associated with this edge, remove it.  */
 402       if (e->aux)
 403         {
 404           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 405           remove_equivalence (equiv->rhs);
 406         }
 407     }
 408 }
 409
 410 /* Ignoring loop backedges, if BB has precisely one incoming edge then
 411    return that edge.  Otherwise return NULL.  */
 412 static edge
 413 single_incoming_edge_ignoring_loop_edges (basic_block bb)
 414 {
 415   edge retval = NULL;
 416   edge e;
 417   edge_iterator ei;
 418
 419   FOR_EACH_EDGE (e, ei, bb->preds)
 420     {
 421       /* A loop back edge can be identified by the destination of
 422          the edge dominating the source of the edge.  */
 423       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
 424         continue;
 425
 426       /* If we have already seen a non-loop edge, then we must have
 427          multiple incoming non-loop edges and thus we return NULL.  */
 428       if (retval)
 429         return NULL;
 430
 431       /* This is the first non-loop incoming edge we have found.  Record
 432          it.  */
 433       retval = e;
 434     }
 435
 436   return retval;
 437 }
 438
 439 edge
 440 uncprop_dom_walker::before_dom_children (basic_block bb)
 441 {
 442   basic_block parent;
 443   edge e;
 444   bool recorded = false;
 445
 446   /* If this block is dominated by a single incoming edge and that edge
 447      has an equivalency, then record the equivalency and push the
 448      VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
 449   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 450   if (parent)
 451     {
 452       e = single_incoming_edge_ignoring_loop_edges (bb);
 453
 454       if (e && e->src == parent && e->aux)
 455         {
 456           struct edge_equivalency *equiv = (struct edge_equivalency *) e->aux;
 457
 458           record_equiv (equiv->rhs, equiv->lhs);
 459           m_equiv_stack.safe_push (equiv->rhs);
 460           recorded = true;
 461         }
 462     }
 463
 464   if (!recorded)
 465     m_equiv_stack.safe_push (NULL_TREE);
 466
 467   uncprop_into_successor_phis (bb);
 468   return NULL;
 469 }
 470
 471 namespace {
 472
 473 const pass_data pass_data_uncprop =
 474 {
 475   GIMPLE_PASS, /* type */
 476   "uncprop", /* name */
 477   OPTGROUP_NONE, /* optinfo_flags */
 478   TV_TREE_SSA_UNCPROP, /* tv_id */
 479   ( PROP_cfg | PROP_ssa ), /* properties_required */
 480   0, /* properties_provided */
 481   0, /* properties_destroyed */
 482   0, /* todo_flags_start */
 483   0, /* todo_flags_finish */
 484 };
 485
 486 class pass_uncprop : public gimple_opt_pass
 487 {
 488 public:
 489   pass_uncprop (gcc::context *ctxt)
 490     : gimple_opt_pass (pass_data_uncprop, ctxt)
 491   {}
 492
 493   /* opt_pass methods: */
 494   opt_pass * clone () { return new pass_uncprop (m_ctxt); }
 495   virtual bool gate (function *) { return flag_tree_dom != 0; }
 496   virtual unsigned int execute (function *);
 497
 498 }; // class pass_uncprop
 499
 500 unsigned int
 501 pass_uncprop::execute (function *fun)
 502 {
 503   basic_block bb;
 504
 505   associate_equivalences_with_edges ();
 506
 507   /* Create our global data structures.  */
 508   val_ssa_equiv = new hash_map<tree, auto_vec<tree> > (1024);
 509
 510   /* We're going to do a dominator walk, so ensure that we have
 511      dominance information.  */
 512   calculate_dominance_info (CDI_DOMINATORS);
 513
 514   /* Recursively walk the dominator tree undoing unprofitable
 515      constant/copy propagations.  */
 516   uncprop_dom_walker (CDI_DOMINATORS).walk (fun->cfg->x_entry_block_ptr);
 517
 518   /* we just need to empty elements out of the hash table, and cleanup the
 519     AUX field on the edges.  */
 520   delete val_ssa_equiv;
 521   val_ssa_equiv = NULL;
 522   FOR_EACH_BB_FN (bb, fun)
 523     {
 524       edge e;
 525       edge_iterator ei;
 526
 527       FOR_EACH_EDGE (e, ei, bb->succs)
 528         {
 529           if (e->aux)
 530             {
 531               free (e->aux);
 532               e->aux = NULL;
 533             }
 534         }
 535     }
 536   return 0;
 537 }
 538
 539 } // anon namespace
 540
 541 gimple_opt_pass *
 542 make_pass_uncprop (gcc::context *ctxt)
 543 {
 544   return new pass_uncprop (ctxt);
 545 }