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