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