gcc/tree-ssa-uncprop.c

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