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 VEC(tree,heap) *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   VEC(tree,heap) *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 /* Free an instance of equiv_hash_elt.  */
 329
 330 static void
 331 equiv_free (void *p)
 332 {
 333   struct equiv_hash_elt *elt = (struct equiv_hash_elt *) p;
 334   VEC_free (tree, heap, elt->equivalences);
 335   free (elt);
 336 }
 337
 338 /* Remove the most recently recorded equivalency for VALUE.  */
 339
 340 static void
 341 remove_equivalence (tree value)
 342 {
 343   struct equiv_hash_elt equiv_hash_elt, *equiv_hash_elt_p;
 344   void **slot;
 345
 346   equiv_hash_elt.value = value;
 347   equiv_hash_elt.equivalences = NULL;
 348
 349   slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
 350
 351   equiv_hash_elt_p = (struct equiv_hash_elt *) *slot;
 352   VEC_pop (tree, equiv_hash_elt_p->equivalences);
 353 }
 354
 355 /* Record EQUIVALENCE = VALUE into our hash table.  */
 356
 357 static void
 358 record_equiv (tree value, tree equivalence)
 359 {
 360   struct equiv_hash_elt *equiv_hash_elt;
 361   void **slot;
 362
 363   equiv_hash_elt = xmalloc (sizeof (struct equiv_hash_elt));
 364   equiv_hash_elt->value = value;
 365   equiv_hash_elt->equivalences = NULL;
 366
 367   slot = htab_find_slot (equiv, equiv_hash_elt, INSERT);
 368
 369   if (*slot == NULL)
 370     *slot = (void *) equiv_hash_elt;
 371   else
 372      free (equiv_hash_elt);
 373
 374   equiv_hash_elt = (struct equiv_hash_elt *) *slot;
 375
 376   VEC_safe_push (tree, heap, equiv_hash_elt->equivalences, equivalence);
 377 }
 378
 379 /* Main driver for un-cprop.  */
 380
 381 static void
 382 tree_ssa_uncprop (void)
 383 {
 384   struct dom_walk_data walk_data;
 385   basic_block bb;
 386
 387   associate_equivalences_with_edges ();
 388
 389   /* Create our global data structures.  */
 390   equiv = htab_create (1024, equiv_hash, equiv_eq, equiv_free);
 391   equiv_stack = VEC_alloc (tree, heap, 2);
 392
 393   /* We're going to do a dominator walk, so ensure that we have
 394      dominance information.  */
 395   calculate_dominance_info (CDI_DOMINATORS);
 396
 397   /* Setup callbacks for the generic dominator tree walker.  */
 398   walk_data.walk_stmts_backward = false;
 399   walk_data.dom_direction = CDI_DOMINATORS;
 400   walk_data.initialize_block_local_data = NULL;
 401   walk_data.before_dom_children_before_stmts = uncprop_initialize_block;
 402   walk_data.before_dom_children_walk_stmts = NULL;
 403   walk_data.before_dom_children_after_stmts = uncprop_into_successor_phis;
 404   walk_data.after_dom_children_before_stmts = NULL;
 405   walk_data.after_dom_children_walk_stmts = NULL;
 406   walk_data.after_dom_children_after_stmts = uncprop_finalize_block;
 407   walk_data.global_data = NULL;
 408   walk_data.block_local_data_size = 0;
 409   walk_data.interesting_blocks = NULL;
 410
 411   /* Now initialize the dominator walker.  */
 412   init_walk_dominator_tree (&walk_data);
 413
 414   /* Recursively walk the dominator tree undoing unprofitable
 415      constant/copy propagations.  */
 416   walk_dominator_tree (&walk_data, ENTRY_BLOCK_PTR);
 417
 418   /* Finalize and clean up.  */
 419   fini_walk_dominator_tree (&walk_data);
 420
 421   /* EQUIV_STACK should already be empty at this point, so we just
 422      need to empty elements out of the hash table, free EQUIV_STACK,
 423      and cleanup the AUX field on the edges.  */
 424   htab_delete (equiv);
 425   VEC_free (tree, heap, equiv_stack);
 426   FOR_EACH_BB (bb)
 427     {
 428       edge e;
 429       edge_iterator ei;
 430
 431       FOR_EACH_EDGE (e, ei, bb->succs)
 432         {
 433           if (e->aux)
 434             {
 435               free (e->aux);
 436               e->aux = NULL;
 437             }
 438         }
 439     }
 440
 441 }
 442
 443
 444 /* We have finished processing the dominator children of BB, perform
 445    any finalization actions in preparation for leaving this node in
 446    the dominator tree.  */
 447
 448 static void
 449 uncprop_finalize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 450                         basic_block bb ATTRIBUTE_UNUSED)
 451 {
 452   /* Pop the topmost value off the equiv stack.  */
 453   tree value = VEC_pop (tree, equiv_stack);
 454
 455   /* If that value was non-null, then pop the topmost equivalency off
 456      its equivalency stack.  */
 457   if (value != NULL)
 458     remove_equivalence (value);
 459 }
 460
 461 /* Unpropagate values from PHI nodes in successor blocks of BB.  */
 462
 463 static void
 464 uncprop_into_successor_phis (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 465                              basic_block bb)
 466 {
 467   edge e;
 468   edge_iterator ei;
 469
 470   /* For each successor edge, first temporarily record any equivalence
 471      on that edge.  Then unpropagate values in any PHI nodes at the
 472      destination of the edge.  Then remove the temporary equivalence.  */
 473   FOR_EACH_EDGE (e, ei, bb->succs)
 474     {
 475       tree phi = phi_nodes (e->dest);
 476
 477       /* If there are no PHI nodes in this destination, then there is
 478          no sense in recording any equivalences.  */
 479       if (!phi)
 480         continue;
 481
 482       /* Record any equivalency associated with E.  */
 483       if (e->aux)
 484         {
 485           struct edge_equivalency *equiv = e->aux;
 486           record_equiv (equiv->rhs, equiv->lhs);
 487         }
 488
 489       /* Walk over the PHI nodes, unpropagating values.  */
 490       for ( ; phi; phi = PHI_CHAIN (phi))
 491         {
 492           /* Sigh.  We'll have more efficient access to this one day.  */
 493           tree arg = PHI_ARG_DEF (phi, e->dest_idx);
 494           struct equiv_hash_elt equiv_hash_elt;
 495           void **slot;
 496
 497           /* If the argument is not an invariant, or refers to the same
 498              underlying variable as the PHI result, then there's no
 499              point in un-propagating the argument.  */
 500           if (!is_gimple_min_invariant (arg)
 501               && SSA_NAME_VAR (arg) != SSA_NAME_VAR (PHI_RESULT (phi)))
 502             continue;
 503
 504           /* Lookup this argument's value in the hash table.  */
 505           equiv_hash_elt.value = arg;
 506           equiv_hash_elt.equivalences = NULL;
 507           slot = htab_find_slot (equiv, &equiv_hash_elt, NO_INSERT);
 508
 509           if (slot)
 510             {
 511               struct equiv_hash_elt *elt = *slot;
 512               int j;
 513
 514               /* Walk every equivalence with the same value.  If we find
 515                  one with the same underlying variable as the PHI result,
 516                  then replace the value in the argument with its equivalent
 517                  SSA_NAME.  Use the most recent equivalence as hopefully
 518                  that results in shortest lifetimes.  */
 519               for (j = VEC_length (tree, elt->equivalences) - 1; j >= 0; j--)
 520                 {
 521                   tree equiv = VEC_index (tree, elt->equivalences, j);
 522
 523                   if (SSA_NAME_VAR (equiv) == SSA_NAME_VAR (PHI_RESULT (phi)))
 524                     {
 525                       SET_PHI_ARG_DEF (phi, e->dest_idx, equiv);
 526                       break;
 527                     }
 528                 }
 529             }
 530         }
 531
 532       /* If we had an equivalence associated with this edge, remove it.  */
 533       if (e->aux)
 534         {
 535           struct edge_equivalency *equiv = e->aux;
 536           remove_equivalence (equiv->rhs);
 537         }
 538     }
 539 }
 540
 541 /* Ignoring loop backedges, if BB has precisely one incoming edge then
 542    return that edge.  Otherwise return NULL.  */
 543 static edge
 544 single_incoming_edge_ignoring_loop_edges (basic_block bb)
 545 {
 546   edge retval = NULL;
 547   edge e;
 548   edge_iterator ei;
 549
 550   FOR_EACH_EDGE (e, ei, bb->preds)
 551     {
 552       /* A loop back edge can be identified by the destination of
 553          the edge dominating the source of the edge.  */
 554       if (dominated_by_p (CDI_DOMINATORS, e->src, e->dest))
 555         continue;
 556
 557       /* If we have already seen a non-loop edge, then we must have
 558          multiple incoming non-loop edges and thus we return NULL.  */
 559       if (retval)
 560         return NULL;
 561
 562       /* This is the first non-loop incoming edge we have found.  Record
 563          it.  */
 564       retval = e;
 565     }
 566
 567   return retval;
 568 }
 569
 570 static void
 571 uncprop_initialize_block (struct dom_walk_data *walk_data ATTRIBUTE_UNUSED,
 572                           basic_block bb)
 573 {
 574   basic_block parent;
 575   edge e;
 576   bool recorded = false;
 577
 578   /* If this block is dominated by a single incoming edge and that edge
 579      has an equivalency, then record the equivalency and push the
 580      VALUE onto EQUIV_STACK.  Else push a NULL entry on EQUIV_STACK.  */
 581   parent = get_immediate_dominator (CDI_DOMINATORS, bb);
 582   if (parent)
 583     {
 584       e = single_incoming_edge_ignoring_loop_edges (bb);
 585
 586       if (e && e->src == parent && e->aux)
 587         {
 588           struct edge_equivalency *equiv = e->aux;
 589
 590           record_equiv (equiv->rhs, equiv->lhs);
 591           VEC_safe_push (tree, heap, equiv_stack, equiv->rhs);
 592           recorded = true;
 593         }
 594     }
 595
 596   if (!recorded)
 597     VEC_safe_push (tree, heap, equiv_stack, NULL_TREE);
 598 }
 599
 600 static bool
 601 gate_uncprop (void)
 602 {
 603   return flag_tree_dom != 0;
 604 }
 605
 606 struct tree_opt_pass pass_uncprop =
 607 {
 608   "uncprop",                            /* name */
 609   gate_uncprop,                         /* gate */
 610   tree_ssa_uncprop,                     /* execute */
 611   NULL,                                 /* sub */
 612   NULL,                                 /* next */
 613   0,                                    /* static_pass_number */
 614   TV_TREE_SSA_UNCPROP,                  /* tv_id */
 615   PROP_cfg | PROP_ssa,                  /* properties_required */
 616   0,                                    /* properties_provided */
 617   0,                                    /* properties_destroyed */
 618   0,                                    /* todo_flags_start */
 619   TODO_dump_func | TODO_verify_ssa,     /* todo_flags_finish */
 620   0                                     /* letter */
 621 };