gcc/tree-ssa-uncprop.c

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