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
 234   /* Set up rank for each BB  */
 235   for (i = 0; i < n_basic_blocks; i++)
 236     bb_rank[bbs[i]] = ++rank  << 16;
 237
 238   free (bbs);
 239   calculate_dominance_info (CDI_DOMINATORS);
 240
 241 }
 242
 243 /* Cleanup after the reassociation pass, and print stats if
 244    requested.  */
 245
 246 static void
 247 fini_reassoc (void)
 248 {
 249
 250   if (dump_file && (dump_flags & TDF_STATS))
 251     {
 252       fprintf (dump_file, "Reassociation stats:\n");
 253       fprintf (dump_file, "Reassociated by rank: %d\n", reassociate_stats.reassociated_by_rank);
 254       fprintf (dump_file, "Reassociated by match: %d\n", reassociate_stats.reassociated_by_match);
 255     }
 256   htab_delete (value_rank);
 257   htab_delete (seen_binops);
 258   free (bb_rank);
 259 }
 260
 261 /* Given an expression E, return the rank of the expression.  */
 262
 263 static unsigned int
 264 get_rank (tree e)
 265 {
 266   valrank_t vr;
 267
 268   /* Constants have rank 0.  */
 269   if (is_gimple_min_invariant (e))
 270     return 0;
 271
 272   /* SSA_NAME's have the rank of the expression they are the result
 273      of.
 274      For globals and uninitialized values, the rank is 0.
 275      For function arguments, use the pre-setup rank.
 276      For PHI nodes, stores, asm statements, etc, we use the rank of
 277      the BB.
 278      For simple operations, the rank is the maximum rank of any of
 279      its operands, or the bb_rank, whichever is less.
 280      I make no claims that this is optimal, however, it gives good
 281      results.  */
 282
 283   if (TREE_CODE (e) == SSA_NAME)
 284     {
 285       tree stmt;
 286       tree rhs;
 287       unsigned int rank, maxrank;
 288       int i;
 289
 290       if (TREE_CODE (SSA_NAME_VAR (e)) == PARM_DECL
 291           && e == default_def (SSA_NAME_VAR (e)))
 292         return find_value_rank (e)->rank;
 293
 294       stmt = SSA_NAME_DEF_STMT (e);
 295       if (bb_for_stmt (stmt) == NULL)
 296         return 0;
 297
 298       if (TREE_CODE (stmt) != MODIFY_EXPR
 299           || !ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
 300         return bb_rank[bb_for_stmt (stmt)->index];
 301
 302       /* If we already have a rank for this expression, use that.  */
 303       vr = find_value_rank (e);
 304       if (vr)
 305         return vr->rank;
 306
 307       /* Otherwise, find the maximum rank for the operands, or the bb
 308          rank, whichever is less.   */
 309       rank = 0;
 310       maxrank = bb_rank[bb_for_stmt(stmt)->index];
 311       rhs = TREE_OPERAND (stmt, 1);
 312       if (TREE_CODE_LENGTH (TREE_CODE (rhs)) == 0)
 313         rank = MAX (rank, get_rank (rhs));
 314       else
 315         {
 316           for (i = 0;
 317                i < TREE_CODE_LENGTH (TREE_CODE (rhs))
 318                  && TREE_OPERAND (rhs, i)
 319                  && rank != maxrank; i++)
 320             rank = MAX(rank, get_rank (TREE_OPERAND (rhs, i)));
 321         }
 322
 323       if (dump_file && (dump_flags & TDF_DETAILS))
 324         {
 325           fprintf (dump_file, "Rank for ");
 326           print_generic_expr (dump_file, e, 0);
 327           fprintf (dump_file, " is %d\n", (rank + 1));
 328         }
 329
 330       /* Note the rank in the hashtable so we don't recompute it.  */
 331       insert_value_rank (e, (rank + 1));
 332       return (rank + 1);
 333     }
 334
 335   /* Globals, etc,  are rank 0 */
 336   return 0;
 337 }
 338
 339
 340 /* Decide whether we should transpose RHS and some operand of
 341    LHSDEFOP.
 342    If yes, then return true and set TAKEOP to the operand number of LHSDEFOP to
 343    switch RHS for.
 344    Otherwise, return false.  */
 345
 346 static bool
 347 should_transpose (tree rhs ATTRIBUTE_UNUSED,
 348                   unsigned int rhsrank,
 349                   tree lhsdefop, unsigned int *takeop)
 350 {
 351   /* Attempt to expose the low ranked
 352      arguments to CSE if we have something like:
 353      a = <rank 2> + c (rank 1)
 354      b = a (rank 3) + d (rank 1)
 355      We want to transform this into:
 356      a = c + d
 357      b = <rank 2> + <rank 3>
 358
 359      The op finding part wouldn't be necessary if
 360                          we could swap the operands above and not have
 361                          update_stmt change them back on us.
 362   */
 363   unsigned int lowrankop;
 364   unsigned int lowrank;
 365   unsigned int highrank;
 366   unsigned int highrankop;
 367   unsigned int temp;
 368
 369   lowrankop = 0;
 370   *takeop = 1;
 371   lowrank = get_rank (TREE_OPERAND (lhsdefop, 0));
 372   temp = get_rank (TREE_OPERAND (lhsdefop, 1));
 373   highrank = temp;
 374   highrankop = 1;
 375   if (temp < lowrank)
 376     {
 377       lowrankop = 1;
 378       highrankop = 0;
 379       *takeop = 0;
 380       highrank = lowrank;
 381       lowrank = temp;
 382     }
 383
 384   /* If highrank == lowrank, then we had something
 385      like:
 386      a = <rank 1> + <rank 1>
 387      already, so there is no guarantee that
 388      swapping our argument in is going to be
 389      better.
 390      If we run reassoc twice, we could probably
 391      have a flag that switches this behavior on,
 392      so that we try once without it, and once with
 393      it, so that redundancy elimination sees it
 394      both ways.
 395   */
 396
 397   if (lowrank == rhsrank && highrank != lowrank)
 398     return true;
 399
 400   /* Also, see if the LHS's high ranked op should be switched with our
 401      RHS simply because it is greater in rank than our current RHS.  */
 402   if (TREE_CODE (TREE_OPERAND (lhsdefop, 0)) == SSA_NAME)
 403     {
 404       tree iop = SSA_NAME_DEF_STMT (TREE_OPERAND (lhsdefop, highrankop));
 405       if (TREE_CODE (iop) == MODIFY_EXPR)
 406         iop = TREE_OPERAND (iop, 1);
 407       if (TREE_CODE (iop) == TREE_CODE (lhsdefop))
 408         *takeop = 1;
 409       if (rhsrank < get_rank (TREE_OPERAND (lhsdefop, *takeop)))
 410         return true;
 411     }
 412
 413   return false;
 414 }
 415
 416 /* Attempt to reassociate the associative binary operator BEXPR, which
 417    is in the statement pointed to by CURRBSI.  Return true if we
 418    changed the statement.  */
 419
 420 static bool
 421 reassociate_expr (tree bexpr, block_stmt_iterator *currbsi)
 422 {
 423   tree lhs = TREE_OPERAND (bexpr, 0);
 424   tree rhs = TREE_OPERAND (bexpr, 1);
 425   tree lhsdef;
 426   tree lhsi;
 427   bool changed = false;
 428   unsigned int lhsrank = get_rank (lhs);
 429   unsigned int rhsrank = get_rank (rhs);
 430
 431   /* I don't want to get into the business of floating point
 432      reassociation.  */
 433   if (!INTEGRAL_TYPE_P (TREE_TYPE (lhs))
 434       || !INTEGRAL_TYPE_P (TREE_TYPE (rhs)))
 435     return false;
 436
 437   /* We want the greater ranked operand to be our "LHS" for simplicity
 438      sake.  There is no point in actually modifying the expression, as
 439      update_stmt will simply resort the operands anyway. */
 440   if (lhsrank < rhsrank)
 441     {
 442       tree temp;
 443       unsigned int temp1;
 444       temp = lhs;
 445       lhs = rhs;
 446       rhs = temp;
 447       temp1 = lhsrank;
 448       lhsrank = rhsrank;
 449       rhsrank = temp1;
 450     }
 451
 452   /* If the high ranked operand is an SSA_NAME, and the binary
 453      operator is not something we've already seen somewhere else
 454      (i.e., it may be redundant), attempt to reassociate it.
 455
 456      We can't reassociate expressions unless the expression we are
 457      going to reassociate with is only used in our current expression,
 458      or else we may screw up other computations, like so:
 459
 460      a = b + c
 461      e = a + d
 462
 463      g = a + f
 464
 465      We cannot reassociate and rewrite the "a = ..." ,
 466      because that would change the value of the computation of
 467      "g = a + f".  */
 468   if (TREE_CODE (lhs) == SSA_NAME && !find_seen_binop (lhs, rhs))
 469     {
 470       lhsdef = SSA_NAME_DEF_STMT (lhs);
 471       if (TREE_CODE (lhsdef) == MODIFY_EXPR)
 472         {
 473           lhsi = TREE_OPERAND (lhsdef, 1);
 474           if (TREE_CODE (lhsi) == TREE_CODE (bexpr))
 475             {
 476               use_operand_p use;
 477               tree usestmt;
 478               if (single_imm_use (lhs, &use, &usestmt))
 479                 {
 480                   unsigned int takeop = 0;
 481                   unsigned int otherop = 1;
 482                   bool foundmatch = false;
 483                   bool foundrank = false;
 484
 485                   /* If we can easily transpose this into an operation
 486                      we've already seen, let's do that.
 487                      otherwise, let's try to expose low ranked ops to
 488                      CSE.  */
 489                   if (find_seen_binop (TREE_OPERAND (lhsi, 1), rhs))
 490                     {
 491                       takeop = 0;
 492                       otherop = 1;
 493                       foundmatch = true;
 494                     }
 495                   else if (find_seen_binop (TREE_OPERAND (lhsi, 0),
 496                                             rhs))
 497                     {
 498                       takeop = 1;
 499                       otherop = 0;
 500                       foundmatch = true;
 501                     }
 502                   else if (should_transpose (rhs, rhsrank, lhsi,
 503                                              &takeop))
 504                     {
 505                       foundrank = true;
 506                     }
 507                   if (foundmatch || foundrank)
 508                     {
 509                       block_stmt_iterator lhsbsi = bsi_for_stmt (lhsdef);
 510                       if (dump_file && (dump_flags & TDF_DETAILS))
 511                         {
 512                           fprintf (dump_file, "Reassociating by %s\n",
 513                                    foundmatch ? "match" : "rank");
 514                           fprintf (dump_file, "Before LHS:");
 515                           print_generic_stmt (dump_file, lhsi, 0);
 516                           fprintf (dump_file, "Before curr expr:");
 517                           print_generic_stmt (dump_file, bexpr, 0);
 518                         }
 519                       TREE_OPERAND (bexpr, 0) = TREE_OPERAND (lhsi, takeop);
 520                       TREE_OPERAND (lhsi, takeop) = rhs;
 521                       TREE_OPERAND (bexpr, 1) = TREE_OPERAND (lhsdef, 0);
 522                       if (dump_file && (dump_flags & TDF_DETAILS))
 523                         {
 524                           fprintf (dump_file, "After LHS:");
 525                           print_generic_stmt (dump_file, lhsi, 0);
 526                           fprintf (dump_file, "After curr expr:");
 527                           print_generic_stmt (dump_file, bexpr, 0);
 528                         }
 529                       bsi_move_before (&lhsbsi, currbsi);
 530                       update_stmt (lhsdef);
 531                       update_stmt (bsi_stmt (*currbsi));
 532                       lhsbsi = bsi_for_stmt (lhsdef);
 533                       update_stmt (bsi_stmt (lhsbsi));
 534
 535                       /* If update_stmt didn't reorder our operands,
 536                          we'd like to recurse on the expression we
 537                          just reassociated and reassociate it
 538                          top-down, exposing further opportunities.
 539                          Unfortunately, update_stmt does reorder them,
 540                          so we can't do this cheaply.  */
 541                       if (!foundmatch)
 542                         reassociate_stats.reassociated_by_rank++;
 543                       else
 544                         reassociate_stats.reassociated_by_match++;
 545                       return true;
 546                     }
 547                 }
 548             }
 549         }
 550     }
 551   return changed;
 552 }
 553
 554 /* Reassociate expressions in basic block BB and its dominator as
 555    children , return true if any
 556    expressions changed.  */
 557
 558 static bool
 559 reassociate_bb (basic_block bb)
 560 {
 561   bool changed = false;
 562   block_stmt_iterator bsi;
 563   basic_block son;
 564
 565   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 566     {
 567       tree stmt = bsi_stmt (bsi);
 568
 569       if (TREE_CODE (stmt) == MODIFY_EXPR)
 570         {
 571           tree rhs = TREE_OPERAND (stmt, 1);
 572           if (associative_tree_code (TREE_CODE (rhs)))
 573             {
 574               if (reassociate_expr (rhs, &bsi))
 575                 {
 576                   changed = true;
 577                   update_stmt (stmt);
 578                 }
 579               insert_seen_binop (TREE_OPERAND (rhs, 0),
 580                                  TREE_OPERAND (rhs, 1));
 581             }
 582         }
 583     }
 584   for (son = first_dom_son (CDI_DOMINATORS, bb);
 585        son;
 586        son = next_dom_son (CDI_DOMINATORS, son))
 587     {
 588       changed |= reassociate_bb (son);
 589     }
 590   return changed;
 591 }
 592
 593
 594 static bool
 595 do_reassoc (void)
 596 {
 597   bool changed = false;
 598
 599   changed = reassociate_bb (ENTRY_BLOCK_PTR);
 600
 601   return changed;
 602 }
 603
 604
 605 /* Gate and execute functions for Reassociation.  */
 606
 607 static void
 608 execute_reassoc (void)
 609 {
 610   init_reassoc ();
 611   do_reassoc ();
 612   fini_reassoc ();
 613 }
 614
 615 struct tree_opt_pass pass_reassoc =
 616 {
 617   "reassoc",                            /* name */
 618   NULL,                         /* gate */
 619   execute_reassoc,                              /* execute */
 620   NULL,                                 /* sub */
 621   NULL,                                 /* next */
 622   0,                                    /* static_pass_number */
 623   TV_TREE_REASSOC,                              /* tv_id */
 624   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
 625   0,                                    /* properties_provided */
 626   0,                                    /* properties_destroyed */
 627   0,                                    /* todo_flags_start */
 628   TODO_update_ssa | TODO_dump_func
 629   | TODO_ggc_collect | TODO_verify_ssa, /* todo_flags_finish */
 630   0                                     /* letter */
 631 };