gcc/tree-ssa-uncprop.c

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