gcc/tree-ssa-uncprop.c

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