gcc/tree-ssa-reassoc.c

   1 /* Reassociation for trees.
   2    Copyright (C) 2005 Free Software Foundation, Inc.
   3    Contributed by Daniel Berlin <dan@dberlin.org>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify
   8 it under the terms of the GNU General Public License as published by
   9 the Free Software Foundation; either version 2, or (at your option)
  10 any later version.
  11
  12 GCC is distributed in the hope that it will be useful,
  13 but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 GNU General Public License for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to
  19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  20 Boston, MA 02110-1301, USA.  */
  21
  22 #include "config.h"
  23 #include "system.h"
  24 #include "coretypes.h"
  25 #include "tm.h"
  26 #include "errors.h"
  27 #include "ggc.h"
  28 #include "tree.h"
  29 #include "basic-block.h"
  30 #include "diagnostic.h"
  31 #include "tree-inline.h"
  32 #include "tree-flow.h"
  33 #include "tree-gimple.h"
  34 #include "tree-dump.h"
  35 #include "timevar.h"
  36 #include "hashtab.h"
  37 #include "tree-iterator.h"
  38 #include "tree-pass.h"
  39
  40 /*  This is a simple global reassociation pass that uses a combination
  41     of heuristics and a hashtable to try to expose more operations to
  42     CSE.
  43
  44     The basic idea behind the heuristic is to rank expressions by
  45     depth of the computation tree and loop depth, and try to produce
  46     expressions consisting of small rank operations, as they are more
  47     likely to reoccur.  In addition, we use a hashtable to try to see
  48     if we can transpose an operation into something we have seen
  49     before.
  50
  51     Note that the way the hashtable is structured will sometimes find
  52     matches that will not expose additional redundancies, since it is
  53     not unwound as we traverse back up one branch of the dominator
  54     tree and down another.  However, the cost of improving this is
  55     probably not worth the additional benefits it will bring.  */
  56
  57 /* Statistics */
  58 static struct
  59 {
  60   int reassociated_by_rank;
  61   int reassociated_by_match;
  62 } reassociate_stats;
  63
  64
  65
  66 /* Seen binary operator hashtable.  */
  67 static htab_t seen_binops;
  68
  69 /* Binary operator struct. */
  70
  71 typedef struct seen_binop_d
  72 {
  73   tree op1;
  74   tree op2;
  75 } *seen_binop_t;
  76
  77 /* Return a SEEN_BINOP_T if we have seen an associative binary
  78    operator with OP1 and OP2 in it.  */
  79
  80 static seen_binop_t
  81 find_seen_binop (tree op1, tree op2)
  82 {
  83   void **slot;
  84   struct seen_binop_d sbd;
  85   sbd.op1 = op1;
  86   sbd.op2 = op2;
  87   slot = htab_find_slot (seen_binops, &sbd, NO_INSERT);
  88   if (!slot)
  89     return NULL;
  90   return ((seen_binop_t) *slot);
  91 }
  92
  93 /* Insert a binary operator consisting of OP1 and OP2 into the
  94    SEEN_BINOP table.  */
  95
  96 static void
  97 insert_seen_binop (tree op1, tree op2)
  98 {
  99   void **slot;
 100   seen_binop_t new_pair = xmalloc (sizeof (*new_pair));
 101   new_pair->op1 = op1;
 102   new_pair->op2 = op2;
 103   slot = htab_find_slot (seen_binops, new_pair, INSERT);
 104   if (*slot != NULL)
 105     free (*slot);
 106   *slot = new_pair;
 107 }
 108
 109 /* Return the hash value for a seen binop structure pointed to by P.
 110    Because all the binops we consider are associative, we just add the
 111    hash value for op1 and op2.  */
 112
 113 static hashval_t
 114 seen_binop_hash (const void *p)
 115 {
 116   const seen_binop_t sb = (seen_binop_t) p;
 117   return iterative_hash_expr (sb->op1, 0) + iterative_hash_expr (sb->op2, 0);
 118 }
 119
 120 /* Return true if two seen binop structures pointed to by P1 and P2 are equal.
 121    We have to check the operators both ways because we don't know what
 122    order they appear in the table.  */
 123
 124 static int
 125 seen_binop_eq (const void *p1, const void *p2)
 126 {
 127   const seen_binop_t sb1 = (seen_binop_t) p1;
 128   const seen_binop_t sb2 = (seen_binop_t) p2;
 129   return (sb1->op1 == sb2->op1 && sb1->op2 == sb2->op2)
 130     || (sb1->op2 == sb2->op1 && sb1->op1 == sb2->op2);
 131 }
 132
 133 /* Value rank structure.  */
 134
 135 typedef struct valrank_d
 136 {
 137   tree e;
 138   unsigned int rank;
 139 } *valrank_t;
 140
 141 /* Starting rank number for a given basic block, so that we can rank
 142    operations using unmovable instructions in that BB based on the bb
 143    depth.  */
 144 static unsigned int *bb_rank;
 145
 146 /* Value rank hashtable.  */
 147 static htab_t value_rank;
 148
 149
 150 /* Look up the value rank structure for expression E.  */
 151
 152 static valrank_t
 153 find_value_rank (tree e)
 154 {
 155   void **slot;
 156   struct valrank_d vrd;
 157   vrd.e = e;
 158   slot = htab_find_slot (value_rank, &vrd, NO_INSERT);
 159   if (!slot)
 160     return NULL;
 161   return ((valrank_t) *slot);
 162 }
 163
 164 /* Insert {E,RANK} into the value rank hashtable.  */
 165
 166 static void
 167 insert_value_rank (tree e, unsigned int rank)
 168 {
 169   void **slot;
 170   valrank_t new_pair = xmalloc (sizeof (*new_pair));
 171   new_pair->e = e;
 172   new_pair->rank = rank;
 173   slot = htab_find_slot (value_rank, new_pair, INSERT);
 174   gcc_assert (*slot == NULL);
 175   *slot = new_pair;
 176
 177 }
 178
 179
 180 /* Return the hash value for a value rank structure  */
 181
 182 static hashval_t
 183 valrank_hash (const void *p)
 184 {
 185   const valrank_t vr = (valrank_t) p;
 186   return iterative_hash_expr (vr->e, 0);
 187 }
 188
 189 /* Return true if two value rank structures are equal.  */
 190
 191 static int
 192 valrank_eq (const void *p1, const void *p2)
 193 {
 194   const valrank_t vr1 = (valrank_t) p1;
 195   const valrank_t vr2 = (valrank_t) p2;
 196   return vr1->e == vr2->e;
 197 }
 198
 199
 200 /* Initialize the reassociation pass.  */
 201
 202 static void
 203 init_reassoc (void)
 204 {
 205   int i;
 206   unsigned int rank = 2;
 207
 208   tree param;
 209   int *bbs = xmalloc ((last_basic_block + 1) * sizeof (int));
 210
 211   memset (&reassociate_stats, 0, sizeof (reassociate_stats));
 212
 213   /* Reverse RPO (Reverse Post Order) will give us something where
 214      deeper loops come later.  */
 215   flow_reverse_top_sort_order_compute (bbs);
 216   bb_rank = xcalloc (last_basic_block + 1, sizeof (unsigned int));
 217   value_rank = htab_create (511, valrank_hash,
 218                             valrank_eq, free);
 219   seen_binops = htab_create (511, seen_binop_hash,
 220                              seen_binop_eq, free);
 221
 222   /* Give each argument a distinct rank.   */
 223   for (param = DECL_ARGUMENTS (current_function_decl);
 224        param;
 225        param = TREE_CHAIN (param))
 226     {
 227       if (default_def (param) != NULL)
 228         {
 229           tree def = default_def (param);
 230           insert_value_rank (def, ++rank);
 231         }
 232     }
 233   /* Give the chain decl a distinct rank. */
 234   if (cfun->static_chain_decl != NULL)
 235     {
 236       tree def = default_def (cfun->static_chain_decl);
 237       if (def != NULL)
 238         insert_value_rank (def, ++rank);
 239     }
 240
 241   /* Set up rank for each BB  */
 242   for (i = 0; i < n_basic_blocks; i++)
 243     bb_rank[bbs[i]] = ++rank  << 16;
 244
 245   free (bbs);
 246   calculate_dominance_info (CDI_DOMINATORS);
 247
 248 }
 249
 250 /* Cleanup after the reassociation pass, and print stats if
 251    requested.  */
 252
 253 static void
 254 fini_reassoc (void)
 255 {
 256
 257   if (dump_file && (dump_flags & TDF_STATS))
 258     {
 259       fprintf (dump_file, "Reassociation stats:\n");
 260       fprintf (dump_file, "Reassociated by rank: %d\n", reassociate_stats.reassociated_by_rank);
 261       fprintf (dump_file, "Reassociated by match: %d\n", reassociate_stats.reassociated_by_match);
 262     }
 263   htab_delete (value_rank);
 264   htab_delete (seen_binops);
 265   free (bb_rank);
 266 }
 267
 268 /* Given an expression E, return the rank of the expression.  */
 269
 270 static unsigned int
 271 get_rank (tree e)
 272 {
 273   valrank_t vr;
 274
 275   /* Constants have rank 0.  */
 276   if (is_gimple_min_invariant (e))
 277     return 0;
 278
 279   /* SSA_NAME's have the rank of the expression they are the result
 280      of.
 281      For globals and uninitialized values, the rank is 0.
 282      For function arguments, use the pre-setup rank.
 283      For PHI nodes, stores, asm statements, etc, we use the rank of
 284      the BB.
 285      For simple operations, the rank is the maximum rank of any of
 286      its operands, or the bb_rank, whichever is less.
 287      I make no claims that this is optimal, however, it gives good
 288      results.  */
 289
 290   if (TREE_CODE (e) == SSA_NAME)
 291     {
 292       tree stmt;
 293       tree rhs;
 294       unsigned int rank, maxrank;
 295       int i;
 296
 297       if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
 298           && e == default_def (SSA_NAME_VAR (e)))
 299         return find_value_rank (e)->rank;
 300
 301       stmt = SSA_NAME_DEF_STMT (e);
 302       if (bb_for_stmt (stmt) == NULL)
 303         return 0;
 304
 305       if (TREE_CODE (stmt) != MODIFY_EXPR
 306           || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 307         return bb_rank[bb_for_stmt (stmt)->index];
 308
 309       /* If we already have a rank for this expression, use that.  */
 310       vr = find_value_rank (e);
 311       if (vr)
 312         return vr->rank;
 313
 314       /* Otherwise, find the maximum rank for the operands, or the bb
 315          rank, whichever is less.   */
 316       rank = 0;
 317       maxrank = bb_rank[bb_for_stmt(stmt)->index];
 318       rhs = TREE_OPERAND (stmt, 1);
 319       if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0)
 320         rank = MAX (rank, get_rank (rhs));
 321       else
 322         {
 323           for (i = 0;
 324                i < TREE_CODE_LENGTH (TREE_CODE (rhs))
 325                  && TREE_OPERAND (rhs, i)
 326                  && rank != maxrank; i++)
 327             rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
 328         }
 329
 330       if (dump_file && (dump_flags & TDF_DETAILS))
 331         {
 332           fprintf (dump_file, "Rank for ");
 333           print_generic_expr (dump_file, e, 0);
 334           fprintf (dump_file, " is %d\n", (rank + 1));
 335         }
 336
 337       /* Note the rank in the hashtable so we don't recompute it.  */
 338       insert_value_rank (e, (rank + 1));
 339       return (rank + 1);
 340     }
 341
 342   /* Globals, etc,  are rank 0 */
 343   return 0;
 344 }
 345
 346
 347 /* Decide whether we should transpose RHS and some operand of
 348    LHSDEFOP.
 349    If yes, then return true and set TAKEOP to the operand number of LHSDEFOP to
 350    switch RHS for.
 351    Otherwise, return false.  */
 352
 353 static bool
 354 should_transpose (tree rhs ATTRIBUTE_UNUSED,
 355                   unsigned int rhsrank,
 356                   tree lhsdefop, unsigned int *takeop)
 357 {
 358   /* Attempt to expose the low ranked
 359      arguments to CSE if we have something like:
 360      a = <rank 2> + c (rank 1)
 361      b = a (rank 3) + d (rank 1)
 362      We want to transform this into:
 363      a = c + d
 364      b = <rank 2> + <rank 3>
 365
 366      The op finding part wouldn't be necessary if
 367                          we could swap the operands above and not have
 368                          update_stmt change them back on us.
 369   */
 370   unsigned int lowrankop;
 371   unsigned int lowrank;
 372   unsigned int highrank;
 373   unsigned int highrankop;
 374   unsigned int temp;
 375
 376   lowrankop = 0;
 377   *takeop = 1;
 378   lowrank = get_rank (TREE_OPERAND (lhsdefop, 0));
 379   temp = get_rank (TREE_OPERAND (lhsdefop, 1));
 380   highrank = temp;
 381   highrankop = 1;
 382   if (temp < lowrank)
 383     {
 384       lowrankop = 1;
 385       highrankop = 0;
 386       *takeop = 0;
 387       highrank = lowrank;
 388       lowrank = temp;
 389     }
 390
 391   /* If highrank == lowrank, then we had something
 392      like:
 393      a = <rank 1> + <rank 1>
 394      already, so there is no guarantee that
 395      swapping our argument in is going to be
 396      better.
 397      If we run reassoc twice, we could probably
 398      have a flag that switches this behavior on,
 399      so that we try once without it, and once with
 400      it, so that redundancy elimination sees it
 401      both ways.
 402   */
 403
 404   if (lowrank == rhsrank && highrank != lowrank)
 405     return true;
 406
 407   /* Also, see if the LHS's high ranked op should be switched with our
 408      RHS simply because it is greater in rank than our current RHS.  */
 409   if (TREE_CODE (TREE_OPERAND (lhsdefop, highrankop)) == SSA_NAME)
 410     {
 411       tree iop = SSA_NAME_DEF_STMT (TREE_OPERAND (lhsdefop, highrankop));
 412       if (TREE_CODE (iop) == MODIFY_EXPR)
 413         iop = TREE_OPERAND (iop, 1);
 414       if (TREE_CODE (iop) == TREE_CODE (lhsdefop))
 415         *takeop = 1;
 416       if (rhsrank < get_rank (TREE_OPERAND (lhsdefop, *takeop)))
 417         return true;
 418     }
 419
 420   return false;
 421 }
 422
 423 /* Attempt to reassociate the associative binary operator BEXPR, which
 424    is in the statement pointed to by CURRBSI.  Return true if we
 425    changed the statement.  */
 426
 427 static bool
 428 reassociate_expr (tree bexpr, block_stmt_iterator *currbsi)
 429 {
 430   tree lhs = TREE_OPERAND (bexpr, 0);
 431   tree rhs = TREE_OPERAND (bexpr, 1);
 432   tree lhsdef;
 433   tree lhsi;
 434   bool changed = false;
 435   unsigned int lhsrank = get_rank (lhs);
 436   unsigned int rhsrank = get_rank (rhs);
 437
 438   /* If unsafe math optimizations we can do reassociation for non-integral
 439      types.  */
 440   if ((!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 441        || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
 442       && (!SCALAR_FLOAT_TYPE_P (TREE_TYPE (rhs))
 443           || !SCALAR_FLOAT_TYPE_P (TREE_TYPE(lhs))
 444           || !flag_unsafe_math_optimizations))
 445     return false;
 446
 447   /* We want the greater ranked operand to be our "LHS" for simplicity
 448      sake.  There is no point in actually modifying the expression, as
 449      update_stmt will simply resort the operands anyway. */
 450   if (lhsrank < rhsrank)
 451     {
 452       tree temp;
 453       unsigned int temp1;
 454       temp = lhs;
 455       lhs = rhs;
 456       rhs = temp;
 457       temp1 = lhsrank;
 458       lhsrank = rhsrank;
 459       rhsrank = temp1;
 460     }
 461
 462   /* If the high ranked operand is an SSA_NAME, and the binary
 463      operator is not something we've already seen somewhere else
 464      (i.e., it may be redundant), attempt to reassociate it.
 465
 466      We can't reassociate expressions unless the expression we are
 467      going to reassociate with is only used in our current expression,
 468      or else we may screw up other computations, like so:
 469
 470      a = b + c
 471      e = a + d
 472
 473      g = a + f
 474
 475      We cannot reassociate and rewrite the "a = ..." ,
 476      because that would change the value of the computation of
 477      "g = a + f".  */
 478   if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))
 479     {
 480       lhsdef = SSA_NAME_DEF_STMT (lhs);
 481       if (TREE_CODE (lhsdef) == MODIFY_EXPR)
 482         {
 483           lhsi = TREE_OPERAND (lhsdef, 1);
 484           if (TREE_CODE (lhsi) == TREE_CODE (bexpr))
 485             {
 486               use_operand_p use;
 487               tree usestmt;
 488               if (single_imm_use (lhs, &use, &usestmt))
 489                 {
 490                   unsigned int takeop = 0;
 491                   unsigned int otherop = 1;
 492                   bool foundmatch = false;
 493                   bool foundrank = false;
 494
 495                   /* If we can easily transpose this into an operation
 496                      we've already seen, let's do that.
 497                      otherwise, let's try to expose low ranked ops to
 498                      CSE.  */
 499                   if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))
 500                     {
 501                       takeop = 0;
 502                       otherop = 1;
 503                       foundmatch = true;
 504                     }
 505                   else if (find_seen_binop (TREE_OPERAND (lhsi, 0),
 506                                             rhs))
 507                     {
 508                       takeop = 1;
 509                       otherop = 0;
 510                       foundmatch = true;
 511                     }
 512                   else if (should_transpose (rhs, rhsrank, lhsi,
 513                                              &takeop))
 514                     {
 515                       foundrank = true;
 516                     }
 517                   if (foundmatch || foundrank)
 518                     {
 519                       block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);
 520                       if (dump_file && (dump_flags & TDF_DETAILS))
 521                         {
 522                           fprintf (dump_file, "Reassociating by %s\n",
 523                                    foundmatch ? "match" : "rank");
 524                           fprintf (dump_file, "Before LHS:");
 525                           print_generic_stmt (dump_file, lhsi, 0);
 526                           fprintf (dump_file, "Before curr expr:");
 527                           print_generic_stmt (dump_file, bexpr, 0);
 528                         }
 529                       TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);
 530                       TREE_OPERAND (lhsi, takeop) = rhs;
 531                       TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);
 532                       if (dump_file && (dump_flags & TDF_DETAILS))
 533                         {
 534                           fprintf (dump_file, "After LHS:");
 535                           print_generic_stmt (dump_file, lhsi, 0);
 536                           fprintf (dump_file, "After curr expr:");
 537                           print_generic_stmt (dump_file, bexpr, 0);
 538                         }
 539                       bsi_move_before (&lhsbsi, currbsi);
 540                       update_stmt (lhsdef);
 541                       update_stmt (bsi_stmt (*currbsi));
 542                       lhsbsi = bsi_for_stmt (lhsdef);
 543                       update_stmt (bsi_stmt (lhsbsi));
 544
 545                       /* If update_stmt didn't reorder our operands,
 546                          we'd like to recurse on the expression we
 547                          just reassociated and reassociate it
 548                          top-down, exposing further opportunities.
 549                          Unfortunately, update_stmt does reorder them,
 550                          so we can't do this cheaply.  */
 551                       if (!foundmatch)
 552                         reassociate_stats.reassociated_by_rank++;
 553                       else
 554                         reassociate_stats.reassociated_by_match++;
 555                       return true;
 556                     }
 557                 }
 558             }
 559         }
 560     }
 561   return changed;
 562 }
 563
 564 /* Reassociate expressions in basic block BB and its dominator as
 565    children , return true if any
 566    expressions changed.  */
 567
 568 static bool
 569 reassociate_bb (basic_block bb)
 570 {
 571   bool changed = false;
 572   block_stmt_iterator bsi;
 573   basic_block son;
 574
 575   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 576     {
 577       tree stmt = bsi_stmt (bsi);
 578
 579       if (TREE_CODE (stmt) == MODIFY_EXPR)
 580         {
 581           tree rhs = TREE_OPERAND (stmt, 1);
 582           if (associative_tree_code (TREE_CODE (rhs)))
 583             {
 584               if (reassociate_expr (rhs, &bsi))
 585                 {
 586                   changed = true;
 587                   update_stmt (stmt);
 588                 }
 589               insert_seen_binop (TREE_OPERAND (rhs, 0),
 590                                  TREE_OPERAND (rhs, 1));
 591             }
 592         }
 593     }
 594   for (son = first_dom_son (CDI_DOMINATORS, bb);
 595        son;
 596        son = next_dom_son (CDI_DOMINATORS, son))
 597     {
 598       changed |= reassociate_bb (son);
 599     }
 600   return changed;
 601 }
 602
 603
 604 static bool
 605 do_reassoc (void)
 606 {
 607   bool changed = false;
 608
 609   changed = reassociate_bb (ENTRY_BLOCK_PTR);
 610
 611   return changed;
 612 }
 613
 614
 615 /* Gate and execute functions for Reassociation.  */
 616
 617 static void
 618 execute_reassoc (void)
 619 {
 620   init_reassoc ();
 621   do_reassoc ();
 622   fini_reassoc ();
 623 }
 624
 625 struct tree_opt_pass pass_reassoc =
 626 {
 627   "reassoc",                            /* name */
 628   NULL,                         /* gate */
 629   execute_reassoc,                              /* execute */
 630   NULL,                                 /* sub */
 631   NULL,                                 /* next */
 632   0,                                    /* static_pass_number */
 633   TV_TREE_REASSOC,                              /* tv_id */
 634   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 635   0,                                    /* properties_provided */
 636   0,                                    /* properties_destroyed */
 637   0,                                    /* todo_flags_start */
 638   TODO_update_ssa | TODO_dump_func
 639   | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
 640   0                                     /* letter */
 641 };