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