gcc/tree-ssa-uncprop.c

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