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