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, 59 Temple Place - Suite 330,
  20 Boston, MA 02111-1307, 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, 0)) == 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   /* I don't want to get into the business of floating point
 439      reassociation.  */
 440   if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 441       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
 442     return false;
 443
 444   /* We want the greater ranked operand to be our "LHS" for simplicity
 445      sake.  There is no point in actually modifying the expression, as
 446      update_stmt will simply resort the operands anyway. */
 447   if (lhsrank < rhsrank)
 448     {
 449       tree temp;
 450       unsigned int temp1;
 451       temp = lhs;
 452       lhs = rhs;
 453       rhs = temp;
 454       temp1 = lhsrank;
 455       lhsrank = rhsrank;
 456       rhsrank = temp1;
 457     }
 458
 459   /* If the high ranked operand is an SSA_NAME, and the binary
 460      operator is not something we've already seen somewhere else
 461      (i.e., it may be redundant), attempt to reassociate it.
 462
 463      We can't reassociate expressions unless the expression we are
 464      going to reassociate with is only used in our current expression,
 465      or else we may screw up other computations, like so:
 466
 467      a = b + c
 468      e = a + d
 469
 470      g = a + f
 471
 472      We cannot reassociate and rewrite the "a = ..." ,
 473      because that would change the value of the computation of
 474      "g = a + f".  */
 475   if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))
 476     {
 477       lhsdef = SSA_NAME_DEF_STMT (lhs);
 478       if (TREE_CODE (lhsdef) == MODIFY_EXPR)
 479         {
 480           lhsi = TREE_OPERAND (lhsdef, 1);
 481           if (TREE_CODE (lhsi) == TREE_CODE (bexpr))
 482             {
 483               use_operand_p use;
 484               tree usestmt;
 485               if (single_imm_use (lhs, &use, &usestmt))
 486                 {
 487                   unsigned int takeop = 0;
 488                   unsigned int otherop = 1;
 489                   bool foundmatch = false;
 490                   bool foundrank = false;
 491
 492                   /* If we can easily transpose this into an operation
 493                      we've already seen, let's do that.
 494                      otherwise, let's try to expose low ranked ops to
 495                      CSE.  */
 496                   if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))
 497                     {
 498                       takeop = 0;
 499                       otherop = 1;
 500                       foundmatch = true;
 501                     }
 502                   else if (find_seen_binop (TREE_OPERAND (lhsi, 0),
 503                                             rhs))
 504                     {
 505                       takeop = 1;
 506                       otherop = 0;
 507                       foundmatch = true;
 508                     }
 509                   else if (should_transpose (rhs, rhsrank, lhsi,
 510                                              &takeop))
 511                     {
 512                       foundrank = true;
 513                     }
 514                   if (foundmatch || foundrank)
 515                     {
 516                       block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);
 517                       if (dump_file && (dump_flags & TDF_DETAILS))
 518                         {
 519                           fprintf (dump_file, "Reassociating by %s\n",
 520                                    foundmatch ? "match" : "rank");
 521                           fprintf (dump_file, "Before LHS:");
 522                           print_generic_stmt (dump_file, lhsi, 0);
 523                           fprintf (dump_file, "Before curr expr:");
 524                           print_generic_stmt (dump_file, bexpr, 0);
 525                         }
 526                       TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);
 527                       TREE_OPERAND (lhsi, takeop) = rhs;
 528                       TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);
 529                       if (dump_file && (dump_flags & TDF_DETAILS))
 530                         {
 531                           fprintf (dump_file, "After LHS:");
 532                           print_generic_stmt (dump_file, lhsi, 0);
 533                           fprintf (dump_file, "After curr expr:");
 534                           print_generic_stmt (dump_file, bexpr, 0);
 535                         }
 536                       bsi_move_before (&lhsbsi, currbsi);
 537                       update_stmt (lhsdef);
 538                       update_stmt (bsi_stmt (*currbsi));
 539                       lhsbsi = bsi_for_stmt (lhsdef);
 540                       update_stmt (bsi_stmt (lhsbsi));
 541
 542                       /* If update_stmt didn't reorder our operands,
 543                          we'd like to recurse on the expression we
 544                          just reassociated and reassociate it
 545                          top-down, exposing further opportunities.
 546                          Unfortunately, update_stmt does reorder them,
 547                          so we can't do this cheaply.  */
 548                       if (!foundmatch)
 549                         reassociate_stats.reassociated_by_rank++;
 550                       else
 551                         reassociate_stats.reassociated_by_match++;
 552                       return true;
 553                     }
 554                 }
 555             }
 556         }
 557     }
 558   return changed;
 559 }
 560
 561 /* Reassociate expressions in basic block BB and its dominator as
 562    children , return true if any
 563    expressions changed.  */
 564
 565 static bool
 566 reassociate_bb (basic_block bb)
 567 {
 568   bool changed = false;
 569   block_stmt_iterator bsi;
 570   basic_block son;
 571
 572   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 573     {
 574       tree stmt = bsi_stmt (bsi);
 575
 576       if (TREE_CODE (stmt) == MODIFY_EXPR)
 577         {
 578           tree rhs = TREE_OPERAND (stmt, 1);
 579           if (associative_tree_code (TREE_CODE (rhs)))
 580             {
 581               if (reassociate_expr (rhs, &bsi))
 582                 {
 583                   changed = true;
 584                   update_stmt (stmt);
 585                 }
 586               insert_seen_binop (TREE_OPERAND (rhs, 0),
 587                                  TREE_OPERAND (rhs, 1));
 588             }
 589         }
 590     }
 591   for (son = first_dom_son (CDI_DOMINATORS, bb);
 592        son;
 593        son = next_dom_son (CDI_DOMINATORS, son))
 594     {
 595       changed |= reassociate_bb (son);
 596     }
 597   return changed;
 598 }
 599
 600
 601 static bool
 602 do_reassoc (void)
 603 {
 604   bool changed = false;
 605
 606   changed = reassociate_bb (ENTRY_BLOCK_PTR);
 607
 608   return changed;
 609 }
 610
 611
 612 /* Gate and execute functions for Reassociation.  */
 613
 614 static void
 615 execute_reassoc (void)
 616 {
 617   init_reassoc ();
 618   do_reassoc ();
 619   fini_reassoc ();
 620 }
 621
 622 struct tree_opt_pass pass_reassoc =
 623 {
 624   "reassoc",                            /* name */
 625   NULL,                         /* gate */
 626   execute_reassoc,                              /* execute */
 627   NULL,                                 /* sub */
 628   NULL,                                 /* next */
 629   0,                                    /* static_pass_number */
 630   TV_TREE_REASSOC,                              /* tv_id */
 631   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 632   0,                                    /* properties_provided */
 633   0,                                    /* properties_destroyed */
 634   0,                                    /* todo_flags_start */
 635   TODO_update_ssa | TODO_dump_func
 636   | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
 637   0                                     /* letter */
 638 };