gcc/tree-phinodes.c

   1 /* Generic routines for manipulating PHIs
   2    Copyright (C) 2003 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 "rtl.h"
  27 #include "varray.h"
  28 #include "ggc.h"
  29 #include "basic-block.h"
  30 #include "tree-flow.h"
  31 #include "toplev.h"
  32
  33 /* Rewriting a function into SSA form can create a huge number of PHIs
  34    many of which may be thrown away shortly after their creation if jumps
  35    were threaded through PHI nodes.
  36
  37    While our garbage collection mechanisms will handle this situation, it
  38    is extremely wasteful to create nodes and throw them away, especially
  39    when the nodes can be reused.
  40
  41    For PR 8361, we can significantly reduce the number of nodes allocated
  42    and thus the total amount of memory allocated by managing PHIs a
  43    little.  This additionally helps reduce the amount of work done by the
  44    garbage collector.  Similar results have been seen on a wider variety
  45    of tests (such as the compiler itself).
  46
  47    Right now we maintain our free list on a per-function basis.  It may
  48    or may not make sense to maintain the free list for the duration of
  49    a compilation unit.
  50
  51    We could also use a zone allocator for these objects since they have
  52    a very well defined lifetime.  If someone wants to experiment with that
  53    this is the place to try it.
  54
  55    PHI nodes have different sizes, so we can't have a single list of all
  56    the PHI nodes as it would be too expensive to walk down that list to
  57    find a PHI of a suitable size.
  58
  59    Instead we have an array of lists of free PHI nodes.  The array is
  60    indexed by the number of PHI alternatives that PHI node can hold.
  61    Except for the last array member, which holds all remaining PHI
  62    nodes.
  63
  64    So to find a free PHI node, we compute its index into the free PHI
  65    node array and see if there are any elements with an exact match.
  66    If so, then we are done.  Otherwise, we test the next larger size
  67    up and continue until we are in the last array element.
  68
  69    We do not actually walk members of the last array element.  While it
  70    might allow us to pick up a few reusable PHI nodes, it could potentially
  71    be very expensive if the program has released a bunch of large PHI nodes,
  72    but keeps asking for even larger PHI nodes.  Experiments have shown that
  73    walking the elements of the last array entry would result in finding less
  74    than .1% additional reusable PHI nodes.
  75
  76    Note that we can never have less than two PHI argument slots.  Thus,
  77    the -2 on all the calculations below.  */
  78
  79 #define NUM_BUCKETS 10
  80 static GTY ((deletable (""))) tree free_phinodes[NUM_BUCKETS - 2];
  81 static unsigned long free_phinode_count;
  82
  83 static int ideal_phi_node_len (int);
  84 static void resize_phi_node (tree *, int);
  85
  86 #ifdef GATHER_STATISTICS
  87 unsigned int phi_nodes_reused;
  88 unsigned int phi_nodes_created;
  89 #endif
  90
  91 /* Initialize management of PHIs.  */
  92
  93 void
  94 init_phinodes (void)
  95 {
  96   int i;
  97
  98   for (i = 0; i < NUM_BUCKETS - 2; i++)
  99     free_phinodes[i] = NULL;
 100   free_phinode_count = 0;
 101 }
 102
 103 /* Finalize management of PHIs.  */
 104
 105 void
 106 fini_phinodes (void)
 107 {
 108   int i;
 109
 110   for (i = 0; i < NUM_BUCKETS - 2; i++)
 111     free_phinodes[i] = NULL;
 112   free_phinode_count = 0;
 113 }
 114
 115 /* Dump some simple statistics regarding the re-use of PHI nodes.  */
 116
 117 #ifdef GATHER_STATISTICS
 118 void
 119 phinodes_print_statistics (void)
 120 {
 121   fprintf (stderr, "PHI nodes allocated: %u\n", phi_nodes_created);
 122   fprintf (stderr, "PHI nodes reused: %u\n", phi_nodes_reused);
 123 }
 124 #endif
 125
 126 /* Given LEN, the original number of requested PHI arguments, return
 127    a new, "ideal" length for the PHI node.  The "ideal" length rounds
 128    the total size of the PHI node up to the next power of two bytes.
 129
 130    Rounding up will not result in wasting any memory since the size request
 131    will be rounded up by the GC system anyway.  [ Note this is not entirely
 132    true since the original length might have fit on one of the special
 133    GC pages. ]  By rounding up, we may avoid the need to reallocate the
 134    PHI node later if we increase the number of arguments for the PHI.  */
 135
 136 static int
 137 ideal_phi_node_len (int len)
 138 {
 139   size_t size, new_size;
 140   int log2, new_len;
 141
 142   /* We do not support allocations of less than two PHI argument slots.  */
 143   if (len < 2)
 144     len = 2;
 145
 146   /* Compute the number of bytes of the original request.  */
 147   size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
 148
 149   /* Round it up to the next power of two.  */
 150   log2 = ceil_log2 (size);
 151   new_size = 1 << log2;
 152
 153   /* Now compute and return the number of PHI argument slots given an
 154      ideal size allocation.  */
 155   new_len = len + (new_size - size) / sizeof (struct phi_arg_d);
 156   return new_len;
 157 }
 158
 159 /* Return a PHI node for variable VAR defined in statement STMT.
 160    STMT may be an empty statement for artificial references (e.g., default
 161    definitions created when a variable is used without a preceding
 162    definition).  */
 163
 164 tree
 165 make_phi_node (tree var, int len)
 166 {
 167   tree phi;
 168   int size;
 169   int bucket = NUM_BUCKETS - 2;
 170
 171   len = ideal_phi_node_len (len);
 172
 173   size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
 174
 175   if (free_phinode_count)
 176     for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
 177       if (free_phinodes[bucket])
 178         break;
 179
 180   /* If our free list has an element, then use it.  */
 181   if (bucket < NUM_BUCKETS - 2
 182       && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len)
 183     {
 184       free_phinode_count--;
 185       phi = free_phinodes[bucket];
 186       free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]);
 187 #ifdef GATHER_STATISTICS
 188       phi_nodes_reused++;
 189 #endif
 190     }
 191   else
 192     {
 193       phi = ggc_alloc (size);
 194 #ifdef GATHER_STATISTICS
 195       phi_nodes_created++;
 196       tree_node_counts[(int) phi_kind]++;
 197       tree_node_sizes[(int) phi_kind] += size;
 198 #endif
 199
 200     }
 201
 202   memset (phi, 0, size);
 203   TREE_SET_CODE (phi, PHI_NODE);
 204   PHI_ARG_CAPACITY (phi) = len;
 205   TREE_TYPE (phi) = TREE_TYPE (var);
 206   if (TREE_CODE (var) == SSA_NAME)
 207     SET_PHI_RESULT (phi, var);
 208   else
 209     SET_PHI_RESULT (phi, make_ssa_name (var, phi));
 210
 211   return phi;
 212 }
 213
 214 /* We no longer need PHI, release it so that it may be reused.  */
 215
 216 void
 217 release_phi_node (tree phi)
 218 {
 219   int bucket;
 220   int len = PHI_ARG_CAPACITY (phi);
 221
 222   bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
 223   bucket -= 2;
 224   PHI_CHAIN (phi) = free_phinodes[bucket];
 225   free_phinodes[bucket] = phi;
 226   free_phinode_count++;
 227 }
 228
 229 /* Resize an existing PHI node.  The only way is up.  Return the
 230    possibly relocated phi.  */
 231
 232 static void
 233 resize_phi_node (tree *phi, int len)
 234 {
 235   int size, old_size;
 236   tree new_phi;
 237   int i, old_len, bucket = NUM_BUCKETS - 2;
 238
 239 #ifdef ENABLE_CHECKING
 240   if (len < PHI_ARG_CAPACITY (*phi))
 241     abort ();
 242 #endif
 243
 244   /* Note that OLD_SIZE is guaranteed to be smaller than SIZE.  */
 245   old_size = (sizeof (struct tree_phi_node)
 246              + (PHI_ARG_CAPACITY (*phi) - 1) * sizeof (struct phi_arg_d));
 247   size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
 248
 249   if (free_phinode_count)
 250     for (bucket = len - 2; bucket < NUM_BUCKETS - 2; bucket++)
 251       if (free_phinodes[bucket])
 252         break;
 253
 254   /* If our free list has an element, then use it.  */
 255   if (bucket < NUM_BUCKETS - 2
 256       && PHI_ARG_CAPACITY (free_phinodes[bucket]) >= len)
 257     {
 258       free_phinode_count--;
 259       new_phi = free_phinodes[bucket];
 260       free_phinodes[bucket] = PHI_CHAIN (free_phinodes[bucket]);
 261 #ifdef GATHER_STATISTICS
 262       phi_nodes_reused++;
 263 #endif
 264     }
 265   else
 266     {
 267       new_phi = ggc_alloc (size);
 268 #ifdef GATHER_STATISTICS
 269       phi_nodes_created++;
 270       tree_node_counts[(int) phi_kind]++;
 271       tree_node_sizes[(int) phi_kind] += size;
 272 #endif
 273     }
 274
 275   memcpy (new_phi, *phi, old_size);
 276
 277   old_len = PHI_ARG_CAPACITY (new_phi);
 278   PHI_ARG_CAPACITY (new_phi) = len;
 279
 280   for (i = old_len; i < len; i++)
 281     {
 282       SET_PHI_ARG_DEF (new_phi, i, NULL_TREE);
 283       PHI_ARG_EDGE (new_phi, i) = NULL;
 284       PHI_ARG_NONZERO (new_phi, i) = false;
 285     }
 286
 287   *phi = new_phi;
 288 }
 289
 290 /* Create a new PHI node for variable VAR at basic block BB.  */
 291
 292 tree
 293 create_phi_node (tree var, basic_block bb)
 294 {
 295   tree phi;
 296
 297   phi = make_phi_node (var, bb_ann (bb)->num_preds);
 298
 299   /* This is a new phi node, so note that is has not yet been
 300      rewritten.  */
 301   PHI_REWRITTEN (phi) = 0;
 302
 303   /* Add the new PHI node to the list of PHI nodes for block BB.  */
 304   PHI_CHAIN (phi) = phi_nodes (bb);
 305   bb_ann (bb)->phi_nodes = phi;
 306
 307   /* Associate BB to the PHI node.  */
 308   set_bb_for_stmt (phi, bb);
 309
 310   return phi;
 311 }
 312
 313 /* Add a new argument to PHI node PHI.  DEF is the incoming reaching
 314    definition and E is the edge through which DEF reaches PHI.  The new
 315    argument is added at the end of the argument list.
 316    If PHI has reached its maximum capacity, add a few slots.  In this case,
 317    PHI points to the reallocated phi node when we return.  */
 318
 319 void
 320 add_phi_arg (tree *phi, tree def, edge e)
 321 {
 322   int i = PHI_NUM_ARGS (*phi);
 323
 324   if (i >= PHI_ARG_CAPACITY (*phi))
 325     {
 326       tree old_phi = *phi;
 327
 328       /* Resize the phi.  Unfortunately, this may also relocate it.  */
 329       resize_phi_node (phi, ideal_phi_node_len (i + 4));
 330
 331       /* The result of the phi is defined by this phi node.  */
 332       SSA_NAME_DEF_STMT (PHI_RESULT (*phi)) = *phi;
 333
 334       /* If the PHI was relocated, update the PHI chains appropriately and
 335          release the old PHI node.  */
 336       if (*phi != old_phi)
 337         {
 338           /* Extract the basic block for the PHI from the PHI's annotation
 339              rather than the edge.  This works better as the edge's
 340              destination may not currently be the block with the PHI
 341              node if we are in the process of threading the edge to
 342              a new destination.  */
 343           basic_block bb = bb_for_stmt (*phi);
 344
 345           release_phi_node (old_phi);
 346
 347           /* Update the list head if replacing the first listed phi.  */
 348           if (phi_nodes (bb) == old_phi)
 349             bb_ann (bb)->phi_nodes = *phi;
 350           else
 351             {
 352               /* Traverse the list looking for the phi node to chain to.  */
 353               tree p;
 354
 355               for (p = phi_nodes (bb);
 356                    p && PHI_CHAIN (p) != old_phi;
 357                    p = PHI_CHAIN (p))
 358                 ;
 359
 360               if (!p)
 361                 abort ();
 362
 363               PHI_CHAIN (p) = *phi;
 364             }
 365         }
 366     }
 367
 368   /* Copy propagation needs to know what object occur in abnormal
 369      PHI nodes.  This is a convenient place to record such information.  */
 370   if (e->flags & EDGE_ABNORMAL)
 371     {
 372       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def) = 1;
 373       SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
 374     }
 375
 376   SET_PHI_ARG_DEF (*phi, i, def);
 377   PHI_ARG_EDGE (*phi, i) = e;
 378   PHI_ARG_NONZERO (*phi, i) = false;
 379   PHI_NUM_ARGS (*phi)++;
 380 }
 381
 382 /* Remove a PHI argument from PHI.  BLOCK is the predecessor block where
 383    the PHI argument is coming from.  */
 384
 385 void
 386 remove_phi_arg (tree phi, basic_block block)
 387 {
 388   int i, num_elem = PHI_NUM_ARGS (phi);
 389
 390   for (i = 0; i < num_elem; i++)
 391     {
 392       basic_block src_bb;
 393
 394       src_bb = PHI_ARG_EDGE (phi, i)->src;
 395
 396       if (src_bb == block)
 397         {
 398           remove_phi_arg_num (phi, i);
 399           return;
 400         }
 401     }
 402 }
 403
 404
 405 /* Remove the Ith argument from PHI's argument list.  This routine assumes
 406    ordering of alternatives in the vector is not important and implements
 407    removal by swapping the last alternative with the alternative we want to
 408    delete, then shrinking the vector.  */
 409
 410 void
 411 remove_phi_arg_num (tree phi, int i)
 412 {
 413   int num_elem = PHI_NUM_ARGS (phi);
 414
 415   /* If we are not at the last element, switch the last element
 416      with the element we want to delete.  */
 417   if (i != num_elem - 1)
 418     {
 419       SET_PHI_ARG_DEF (phi, i, PHI_ARG_DEF (phi, num_elem - 1));
 420       PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
 421       PHI_ARG_NONZERO (phi, i) = PHI_ARG_NONZERO (phi, num_elem - 1);
 422     }
 423
 424   /* Shrink the vector and return.  */
 425   SET_PHI_ARG_DEF (phi, num_elem - 1, NULL_TREE);
 426   PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
 427   PHI_ARG_NONZERO (phi, num_elem - 1) = false;
 428   PHI_NUM_ARGS (phi)--;
 429
 430   /* If we removed the last PHI argument, then go ahead and
 431      remove the PHI node.  */
 432   if (PHI_NUM_ARGS (phi) == 0)
 433     remove_phi_node (phi, NULL, bb_for_stmt (phi));
 434 }
 435
 436 /* Remove PHI node PHI from basic block BB.  If PREV is non-NULL, it is
 437    used as the node immediately before PHI in the linked list.  */
 438
 439 void
 440 remove_phi_node (tree phi, tree prev, basic_block bb)
 441 {
 442   if (prev)
 443     {
 444       /* Rewire the list if we are given a PREV pointer.  */
 445       PHI_CHAIN (prev) = PHI_CHAIN (phi);
 446
 447       /* If we are deleting the PHI node, then we should release the
 448          SSA_NAME node so that it can be reused.  */
 449       release_ssa_name (PHI_RESULT (phi));
 450       release_phi_node (phi);
 451     }
 452   else if (phi == phi_nodes (bb))
 453     {
 454       /* Update the list head if removing the first element.  */
 455       bb_ann (bb)->phi_nodes = PHI_CHAIN (phi);
 456
 457       /* If we are deleting the PHI node, then we should release the
 458          SSA_NAME node so that it can be reused.  */
 459       release_ssa_name (PHI_RESULT (phi));
 460       release_phi_node (phi);
 461     }
 462   else
 463     {
 464       /* Traverse the list looking for the node to remove.  */
 465       tree prev, t;
 466       prev = NULL_TREE;
 467       for (t = phi_nodes (bb); t && t != phi; t = PHI_CHAIN (t))
 468         prev = t;
 469       if (t)
 470         remove_phi_node (t, prev, bb);
 471     }
 472 }
 473
 474
 475 /* Remove all the PHI nodes for variables in the VARS bitmap.  */
 476
 477 void
 478 remove_all_phi_nodes_for (bitmap vars)
 479 {
 480   basic_block bb;
 481
 482   FOR_EACH_BB (bb)
 483     {
 484       /* Build a new PHI list for BB without variables in VARS.  */
 485       tree phi, new_phi_list, last_phi, next;
 486
 487       last_phi = new_phi_list = NULL_TREE;
 488       for (phi = phi_nodes (bb), next = NULL; phi; phi = next)
 489         {
 490           tree var = SSA_NAME_VAR (PHI_RESULT (phi));
 491
 492           next = PHI_CHAIN (phi);
 493           /* Only add PHI nodes for variables not in VARS.  */
 494           if (!bitmap_bit_p (vars, var_ann (var)->uid))
 495             {
 496               /* If we're not removing this PHI node, then it must have
 497                  been rewritten by a previous call into the SSA rewriter.
 498                  Note that fact in PHI_REWRITTEN.  */
 499               PHI_REWRITTEN (phi) = 1;
 500
 501               if (new_phi_list == NULL_TREE)
 502                 new_phi_list = last_phi = phi;
 503               else
 504                 {
 505                   PHI_CHAIN (last_phi) = phi;
 506                   last_phi = phi;
 507                 }
 508             }
 509           else
 510             {
 511               /* If we are deleting the PHI node, then we should release the
 512                  SSA_NAME node so that it can be reused.  */
 513               release_ssa_name (PHI_RESULT (phi));
 514               release_phi_node (phi);
 515             }
 516         }
 517
 518       /* Make sure the last node in the new list has no successors.  */
 519       if (last_phi)
 520         PHI_CHAIN (last_phi) = NULL_TREE;
 521       bb_ann (bb)->phi_nodes = new_phi_list;
 522
 523 #if defined ENABLE_CHECKING
 524       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 525         {
 526           tree var = SSA_NAME_VAR (PHI_RESULT (phi));
 527           if (bitmap_bit_p (vars, var_ann (var)->uid))
 528             abort ();
 529         }
 530 #endif
 531     }
 532 }
 533
 534
 535 #include "gt-tree-phinodes.h"
 536