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