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