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