gcc/tree-ssa-uncprop.c

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