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