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