gcc/tree-ssa-uncprop.c

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