gcc/tree-outof-ssa.c

   1 /* Convert a program in SSA form into Normal form.
   2    Copyright (C) 2004, 2005 Free Software Foundation, Inc.
   3    Contributed by Andrew Macleod <amacleod@redhat.com>
   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 "tree.h"
  27 #include "flags.h"
  28 #include "rtl.h"
  29 #include "tm_p.h"
  30 #include "ggc.h"
  31 #include "langhooks.h"
  32 #include "hard-reg-set.h"
  33 #include "basic-block.h"
  34 #include "output.h"
  35 #include "expr.h"
  36 #include "function.h"
  37 #include "diagnostic.h"
  38 #include "bitmap.h"
  39 #include "tree-flow.h"
  40 #include "tree-gimple.h"
  41 #include "tree-inline.h"
  42 #include "varray.h"
  43 #include "timevar.h"
  44 #include "hashtab.h"
  45 #include "tree-dump.h"
  46 #include "tree-ssa-live.h"
  47 #include "tree-pass.h"
  48 #include "toplev.h"
  49
  50 /* Flags to pass to remove_ssa_form.  */
  51
  52 #define SSANORM_PERFORM_TER             0x1
  53 #define SSANORM_COMBINE_TEMPS           0x2
  54 #define SSANORM_COALESCE_PARTITIONS     0x4
  55
  56 DEF_VEC_I(int);
  57 DEF_VEC_ALLOC_I(int,heap);
  58
  59 /* Used to hold all the components required to do SSA PHI elimination.
  60    The node and pred/succ list is a simple linear list of nodes and
  61    edges represented as pairs of nodes.
  62
  63    The predecessor and successor list:  Nodes are entered in pairs, where
  64    [0] ->PRED, [1]->SUCC.  All the even indexes in the array represent
  65    predecessors, all the odd elements are successors.
  66
  67    Rationale:
  68    When implemented as bitmaps, very large programs SSA->Normal times were
  69    being dominated by clearing the interference graph.
  70
  71    Typically this list of edges is extremely small since it only includes
  72    PHI results and uses from a single edge which have not coalesced with
  73    each other.  This means that no virtual PHI nodes are included, and
  74    empirical evidence suggests that the number of edges rarely exceed
  75    3, and in a bootstrap of GCC, the maximum size encountered was 7.
  76    This also limits the number of possible nodes that are involved to
  77    rarely more than 6, and in the bootstrap of gcc, the maximum number
  78    of nodes encountered was 12.  */
  79
  80 typedef struct _elim_graph {
  81   /* Size of the elimination vectors.  */
  82   int size;
  83
  84   /* List of nodes in the elimination graph.  */
  85   VEC(tree,heap) *nodes;
  86
  87   /*  The predecessor and successor edge list.  */
  88   VEC(int,heap) *edge_list;
  89
  90   /* Visited vector.  */
  91   sbitmap visited;
  92
  93   /* Stack for visited nodes.  */
  94   VEC(int,heap) *stack;
  95
  96   /* The variable partition map.  */
  97   var_map map;
  98
  99   /* Edge being eliminated by this graph.  */
 100   edge e;
 101
 102   /* List of constant copies to emit.  These are pushed on in pairs.  */
 103   VEC(tree,heap) *const_copies;
 104 } *elim_graph;
 105
 106
 107 /* Local functions.  */
 108 static tree create_temp (tree);
 109 static void insert_copy_on_edge (edge, tree, tree);
 110 static elim_graph new_elim_graph (int);
 111 static inline void delete_elim_graph (elim_graph);
 112 static inline void clear_elim_graph (elim_graph);
 113 static inline int elim_graph_size (elim_graph);
 114 static inline void elim_graph_add_node (elim_graph, tree);
 115 static inline void elim_graph_add_edge (elim_graph, int, int);
 116 static inline int elim_graph_remove_succ_edge (elim_graph, int);
 117
 118 static inline void eliminate_name (elim_graph, tree);
 119 static void eliminate_build (elim_graph, basic_block);
 120 static void elim_forward (elim_graph, int);
 121 static int elim_unvisited_predecessor (elim_graph, int);
 122 static void elim_backward (elim_graph, int);
 123 static void elim_create (elim_graph, int);
 124 static void eliminate_phi (edge, elim_graph);
 125 static tree_live_info_p coalesce_ssa_name (var_map, int);
 126 static void assign_vars (var_map);
 127 static bool replace_use_variable (var_map, use_operand_p, tree *);
 128 static bool replace_def_variable (var_map, def_operand_p, tree *);
 129 static void eliminate_virtual_phis (void);
 130 static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p);
 131 static void print_exprs (FILE *, const char *, tree, const char *, tree,
 132                          const char *);
 133 static void print_exprs_edge (FILE *, edge, const char *, tree, const char *,
 134                               tree);
 135
 136
 137 /* Create a temporary variable based on the type of variable T.  Use T's name
 138    as the prefix.  */
 139
 140 static tree
 141 create_temp (tree t)
 142 {
 143   tree tmp;
 144   const char *name = NULL;
 145   tree type;
 146
 147   if (TREE_CODE (t) == SSA_NAME)
 148     t = SSA_NAME_VAR (t);
 149
 150   gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL);
 151
 152   type = TREE_TYPE (t);
 153   tmp = DECL_NAME (t);
 154   if (tmp)
 155     name = IDENTIFIER_POINTER (tmp);
 156
 157   if (name == NULL)
 158     name = "temp";
 159   tmp = create_tmp_var (type, name);
 160
 161   if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t))
 162     {
 163       SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t));
 164       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 165     }
 166   else if (!DECL_IGNORED_P (t))
 167     {
 168       SET_DECL_DEBUG_EXPR (tmp, t);
 169       DECL_DEBUG_EXPR_IS_FROM (tmp) = 1;
 170     }
 171   DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t);
 172   DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t);
 173   add_referenced_tmp_var (tmp);
 174
 175   /* add_referenced_tmp_var will create the annotation and set up some
 176      of the flags in the annotation.  However, some flags we need to
 177      inherit from our original variable.  */
 178   var_ann (tmp)->type_mem_tag = var_ann (t)->type_mem_tag;
 179   if (is_call_clobbered (t))
 180     mark_call_clobbered (tmp);
 181
 182   return tmp;
 183 }
 184
 185
 186 /* This helper function fill insert a copy from a constant or variable SRC to
 187    variable DEST on edge E.  */
 188
 189 static void
 190 insert_copy_on_edge (edge e, tree dest, tree src)
 191 {
 192   tree copy;
 193
 194   copy = build2 (MODIFY_EXPR, TREE_TYPE (dest), dest, src);
 195   set_is_used (dest);
 196
 197   if (TREE_CODE (src) == ADDR_EXPR)
 198     src = TREE_OPERAND (src, 0);
 199   if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL)
 200     set_is_used (src);
 201
 202   if (dump_file && (dump_flags & TDF_DETAILS))
 203     {
 204       fprintf (dump_file,
 205                "Inserting a copy on edge BB%d->BB%d :",
 206                e->src->index,
 207                e->dest->index);
 208       print_generic_expr (dump_file, copy, dump_flags);
 209       fprintf (dump_file, "\n");
 210     }
 211
 212   bsi_insert_on_edge (e, copy);
 213 }
 214
 215
 216 /* Create an elimination graph with SIZE nodes and associated data
 217    structures.  */
 218
 219 static elim_graph
 220 new_elim_graph (int size)
 221 {
 222   elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph));
 223
 224   g->nodes = VEC_alloc (tree, heap, 30);
 225   g->const_copies = VEC_alloc (tree, heap, 20);
 226   g->edge_list = VEC_alloc (int, heap, 20);
 227   g->stack = VEC_alloc (int, heap, 30);
 228
 229   g->visited = sbitmap_alloc (size);
 230
 231   return g;
 232 }
 233
 234
 235 /* Empty elimination graph G.  */
 236
 237 static inline void
 238 clear_elim_graph (elim_graph g)
 239 {
 240   VEC_truncate (tree, g->nodes, 0);
 241   VEC_truncate (int, g->edge_list, 0);
 242 }
 243
 244
 245 /* Delete elimination graph G.  */
 246
 247 static inline void
 248 delete_elim_graph (elim_graph g)
 249 {
 250   sbitmap_free (g->visited);
 251   VEC_free (int, heap, g->stack);
 252   VEC_free (int, heap, g->edge_list);
 253   VEC_free (tree, heap, g->const_copies);
 254   VEC_free (tree, heap, g->nodes);
 255   free (g);
 256 }
 257
 258
 259 /* Return the number of nodes in graph G.  */
 260
 261 static inline int
 262 elim_graph_size (elim_graph g)
 263 {
 264   return VEC_length (tree, g->nodes);
 265 }
 266
 267
 268 /* Add NODE to graph G, if it doesn't exist already.  */
 269
 270 static inline void
 271 elim_graph_add_node (elim_graph g, tree node)
 272 {
 273   int x;
 274   tree t;
 275
 276   for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++)
 277     if (t == node)
 278       return;
 279   VEC_safe_push (tree, heap, g->nodes, node);
 280 }
 281
 282
 283 /* Add the edge PRED->SUCC to graph G.  */
 284
 285 static inline void
 286 elim_graph_add_edge (elim_graph g, int pred, int succ)
 287 {
 288   VEC_safe_push (int, heap, g->edge_list, pred);
 289   VEC_safe_push (int, heap, g->edge_list, succ);
 290 }
 291
 292
 293 /* Remove an edge from graph G for which NODE is the predecessor, and
 294    return the successor node.  -1 is returned if there is no such edge.  */
 295
 296 static inline int
 297 elim_graph_remove_succ_edge (elim_graph g, int node)
 298 {
 299   int y;
 300   unsigned x;
 301   for (x = 0; x < VEC_length (int, g->edge_list); x += 2)
 302     if (VEC_index (int, g->edge_list, x) == node)
 303       {
 304         VEC_replace (int, g->edge_list, x, -1);
 305         y = VEC_index (int, g->edge_list, x + 1);
 306         VEC_replace (int, g->edge_list, x + 1, -1);
 307         return y;
 308       }
 309   return -1;
 310 }
 311
 312
 313 /* Find all the nodes in GRAPH which are successors to NODE in the
 314    edge list.  VAR will hold the partition number found.  CODE is the
 315    code fragment executed for every node found.  */
 316
 317 #define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE)                \
 318 do {                                                                    \
 319   unsigned x_;                                                          \
 320   int y_;                                                               \
 321   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 322     {                                                                   \
 323       y_ = VEC_index (int, (GRAPH)->edge_list, x_);                     \
 324       if (y_ != (NODE))                                                 \
 325         continue;                                                       \
 326       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1);              \
 327       CODE;                                                             \
 328     }                                                                   \
 329 } while (0)
 330
 331
 332 /* Find all the nodes which are predecessors of NODE in the edge list for
 333    GRAPH.  VAR will hold the partition number found.  CODE is the
 334    code fragment executed for every node found.  */
 335
 336 #define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE)                \
 337 do {                                                                    \
 338   unsigned x_;                                                          \
 339   int y_;                                                               \
 340   for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2)      \
 341     {                                                                   \
 342       y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1);                 \
 343       if (y_ != (NODE))                                                 \
 344         continue;                                                       \
 345       (VAR) = VEC_index (int, (GRAPH)->edge_list, x_);                  \
 346       CODE;                                                             \
 347     }                                                                   \
 348 } while (0)
 349
 350
 351 /* Add T to elimination graph G.  */
 352
 353 static inline void
 354 eliminate_name (elim_graph g, tree T)
 355 {
 356   elim_graph_add_node (g, T);
 357 }
 358
 359
 360 /* Build elimination graph G for basic block BB on incoming PHI edge
 361    G->e.  */
 362
 363 static void
 364 eliminate_build (elim_graph g, basic_block B)
 365 {
 366   tree phi;
 367   tree T0, Ti;
 368   int p0, pi;
 369
 370   clear_elim_graph (g);
 371
 372   for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi))
 373     {
 374       T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi));
 375
 376       /* Ignore results which are not in partitions.  */
 377       if (T0 == NULL_TREE)
 378         continue;
 379
 380       Ti = PHI_ARG_DEF (phi, g->e->dest_idx);
 381
 382       /* If this argument is a constant, or a SSA_NAME which is being
 383          left in SSA form, just queue a copy to be emitted on this
 384          edge.  */
 385       if (!phi_ssa_name_p (Ti)
 386           || (TREE_CODE (Ti) == SSA_NAME
 387               && var_to_partition (g->map, Ti) == NO_PARTITION))
 388         {
 389           /* Save constant copies until all other copies have been emitted
 390              on this edge.  */
 391           VEC_safe_push (tree, heap, g->const_copies, T0);
 392           VEC_safe_push (tree, heap, g->const_copies, Ti);
 393         }
 394       else
 395         {
 396           Ti = var_to_partition_to_var (g->map, Ti);
 397           if (T0 != Ti)
 398             {
 399               eliminate_name (g, T0);
 400               eliminate_name (g, Ti);
 401               p0 = var_to_partition (g->map, T0);
 402               pi = var_to_partition (g->map, Ti);
 403               elim_graph_add_edge (g, p0, pi);
 404             }
 405         }
 406     }
 407 }
 408
 409
 410 /* Push successors of T onto the elimination stack for G.  */
 411
 412 static void
 413 elim_forward (elim_graph g, int T)
 414 {
 415   int S;
 416   SET_BIT (g->visited, T);
 417   FOR_EACH_ELIM_GRAPH_SUCC (g, T, S,
 418     {
 419       if (!TEST_BIT (g->visited, S))
 420         elim_forward (g, S);
 421     });
 422   VEC_safe_push (int, heap, g->stack, T);
 423 }
 424
 425
 426 /* Return 1 if there unvisited predecessors of T in graph G.  */
 427
 428 static int
 429 elim_unvisited_predecessor (elim_graph g, int T)
 430 {
 431   int P;
 432   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 433     {
 434       if (!TEST_BIT (g->visited, P))
 435         return 1;
 436     });
 437   return 0;
 438 }
 439
 440 /* Process predecessors first, and insert a copy.  */
 441
 442 static void
 443 elim_backward (elim_graph g, int T)
 444 {
 445   int P;
 446   SET_BIT (g->visited, T);
 447   FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 448     {
 449       if (!TEST_BIT (g->visited, P))
 450         {
 451           elim_backward (g, P);
 452           insert_copy_on_edge (g->e,
 453                                partition_to_var (g->map, P),
 454                                partition_to_var (g->map, T));
 455         }
 456     });
 457 }
 458
 459 /* Insert required copies for T in graph G.  Check for a strongly connected
 460    region, and create a temporary to break the cycle if one is found.  */
 461
 462 static void
 463 elim_create (elim_graph g, int T)
 464 {
 465   tree U;
 466   int P, S;
 467
 468   if (elim_unvisited_predecessor (g, T))
 469     {
 470       U = create_temp (partition_to_var (g->map, T));
 471       insert_copy_on_edge (g->e, U, partition_to_var (g->map, T));
 472       FOR_EACH_ELIM_GRAPH_PRED (g, T, P,
 473         {
 474           if (!TEST_BIT (g->visited, P))
 475             {
 476               elim_backward (g, P);
 477               insert_copy_on_edge (g->e, partition_to_var (g->map, P), U);
 478             }
 479         });
 480     }
 481   else
 482     {
 483       S = elim_graph_remove_succ_edge (g, T);
 484       if (S != -1)
 485         {
 486           SET_BIT (g->visited, T);
 487           insert_copy_on_edge (g->e,
 488                                partition_to_var (g->map, T),
 489                                partition_to_var (g->map, S));
 490         }
 491     }
 492
 493 }
 494
 495 /* Eliminate all the phi nodes on edge E in graph G.  */
 496
 497 static void
 498 eliminate_phi (edge e, elim_graph g)
 499 {
 500   int x;
 501   basic_block B = e->dest;
 502
 503   gcc_assert (VEC_length (tree, g->const_copies) == 0);
 504
 505   /* Abnormal edges already have everything coalesced.  */
 506   if (e->flags & EDGE_ABNORMAL)
 507     return;
 508
 509   g->e = e;
 510
 511   eliminate_build (g, B);
 512
 513   if (elim_graph_size (g) != 0)
 514     {
 515       tree var;
 516
 517       sbitmap_zero (g->visited);
 518       VEC_truncate (int, g->stack, 0);
 519
 520       for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++)
 521         {
 522           int p = var_to_partition (g->map, var);
 523           if (!TEST_BIT (g->visited, p))
 524             elim_forward (g, p);
 525         }
 526
 527       sbitmap_zero (g->visited);
 528       while (VEC_length (int, g->stack) > 0)
 529         {
 530           x = VEC_pop (int, g->stack);
 531           if (!TEST_BIT (g->visited, x))
 532             elim_create (g, x);
 533         }
 534     }
 535
 536   /* If there are any pending constant copies, issue them now.  */
 537   while (VEC_length (tree, g->const_copies) > 0)
 538     {
 539       tree src, dest;
 540       src = VEC_pop (tree, g->const_copies);
 541       dest = VEC_pop (tree, g->const_copies);
 542       insert_copy_on_edge (e, dest, src);
 543     }
 544 }
 545
 546
 547 /* Shortcut routine to print messages to file F of the form:
 548    "STR1 EXPR1 STR2 EXPR2 STR3."  */
 549
 550 static void
 551 print_exprs (FILE *f, const char *str1, tree expr1, const char *str2,
 552              tree expr2, const char *str3)
 553 {
 554   fprintf (f, "%s", str1);
 555   print_generic_expr (f, expr1, TDF_SLIM);
 556   fprintf (f, "%s", str2);
 557   print_generic_expr (f, expr2, TDF_SLIM);
 558   fprintf (f, "%s", str3);
 559 }
 560
 561
 562 /* Shortcut routine to print abnormal edge messages to file F of the form:
 563    "STR1 EXPR1 STR2 EXPR2 across edge E.  */
 564
 565 static void
 566 print_exprs_edge (FILE *f, edge e, const char *str1, tree expr1,
 567                   const char *str2, tree expr2)
 568 {
 569   print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge");
 570   fprintf (f, " from BB%d->BB%d\n", e->src->index,
 571                e->dest->index);
 572 }
 573
 574
 575 /* Coalesce partitions in MAP which are live across abnormal edges in GRAPH.
 576    RV is the root variable groupings of the partitions in MAP.  Since code
 577    cannot be inserted on these edges, failure to coalesce something across
 578    an abnormal edge is an error.  */
 579
 580 static void
 581 coalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv)
 582 {
 583   basic_block bb;
 584   edge e;
 585   tree phi, var, tmp;
 586   int x, y, z;
 587   edge_iterator ei;
 588
 589   /* Code cannot be inserted on abnormal edges. Look for all abnormal
 590      edges, and coalesce any PHI results with their arguments across
 591      that edge.  */
 592
 593   FOR_EACH_BB (bb)
 594     FOR_EACH_EDGE (e, ei, bb->succs)
 595       if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL)
 596         for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi))
 597           {
 598             /* Visit each PHI on the destination side of this abnormal
 599                edge, and attempt to coalesce the argument with the result.  */
 600             var = PHI_RESULT (phi);
 601             x = var_to_partition (map, var);
 602
 603             /* Ignore results which are not relevant.  */
 604             if (x == NO_PARTITION)
 605               continue;
 606
 607             tmp = PHI_ARG_DEF (phi, e->dest_idx);
 608 #ifdef ENABLE_CHECKING
 609             if (!phi_ssa_name_p (tmp))
 610               {
 611                 print_exprs_edge (stderr, e,
 612                                   "\nConstant argument in PHI. Can't insert :",
 613                                   var, " = ", tmp);
 614                 internal_error ("SSA corruption");
 615               }
 616 #else
 617             gcc_assert (phi_ssa_name_p (tmp));
 618 #endif
 619             y = var_to_partition (map, tmp);
 620             gcc_assert (x != NO_PARTITION);
 621             gcc_assert (y != NO_PARTITION);
 622 #ifdef ENABLE_CHECKING
 623             if (root_var_find (rv, x) != root_var_find (rv, y))
 624               {
 625                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
 626                                   root_var (rv, root_var_find (rv, x)),
 627                                   " and ",
 628                                   root_var (rv, root_var_find (rv, y)));
 629                 internal_error ("SSA corruption");
 630               }
 631 #else
 632             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
 633 #endif
 634
 635             if (x != y)
 636               {
 637 #ifdef ENABLE_CHECKING
 638                 if (conflict_graph_conflict_p (graph, x, y))
 639                   {
 640                     print_exprs_edge (stderr, e, "\n Conflict ",
 641                                       partition_to_var (map, x),
 642                                       " and ", partition_to_var (map, y));
 643                     internal_error ("SSA corruption");
 644                   }
 645 #else
 646                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
 647 #endif
 648
 649                 /* Now map the partitions back to their real variables.  */
 650                 var = partition_to_var (map, x);
 651                 tmp = partition_to_var (map, y);
 652                 if (dump_file && (dump_flags & TDF_DETAILS))
 653                   {
 654                     print_exprs_edge (dump_file, e,
 655                                       "ABNORMAL: Coalescing ",
 656                                       var, " and ", tmp);
 657                   }
 658                 z = var_union (map, var, tmp);
 659 #ifdef ENABLE_CHECKING
 660                 if (z == NO_PARTITION)
 661                   {
 662                     print_exprs_edge (stderr, e, "\nUnable to coalesce",
 663                                       partition_to_var (map, x), " and ",
 664                                       partition_to_var (map, y));
 665                     internal_error ("SSA corruption");
 666                   }
 667 #else
 668                 gcc_assert (z != NO_PARTITION);
 669 #endif
 670                 gcc_assert (z == x || z == y);
 671                 if (z == x)
 672                   conflict_graph_merge_regs (graph, x, y);
 673                 else
 674                   conflict_graph_merge_regs (graph, y, x);
 675               }
 676           }
 677 }
 678
 679 /* Coalesce potential copies via PHI arguments.  */
 680
 681 static void
 682 coalesce_phi_operands (var_map map, coalesce_list_p cl)
 683 {
 684   basic_block bb;
 685   tree phi;
 686
 687   FOR_EACH_BB (bb)
 688     {
 689       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 690         {
 691           tree res = PHI_RESULT (phi);
 692           int p = var_to_partition (map, res);
 693           int x;
 694
 695           if (p == NO_PARTITION)
 696             continue;
 697
 698           for (x = 0; x < PHI_NUM_ARGS (phi); x++)
 699             {
 700               tree arg = PHI_ARG_DEF (phi, x);
 701               int p2;
 702
 703               if (TREE_CODE (arg) != SSA_NAME)
 704                 continue;
 705               if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
 706                 continue;
 707               p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
 708               if (p2 != NO_PARTITION)
 709                 {
 710                   edge e = PHI_ARG_EDGE (phi, x);
 711                   add_coalesce (cl, p, p2,
 712                                 coalesce_cost (EDGE_FREQUENCY (e),
 713                                                maybe_hot_bb_p (bb),
 714                                                EDGE_CRITICAL_P (e)));
 715                 }
 716             }
 717         }
 718     }
 719 }
 720
 721 /* Coalesce all the result decls together.  */
 722
 723 static void
 724 coalesce_result_decls (var_map map, coalesce_list_p cl)
 725 {
 726   unsigned int i, x;
 727   tree var = NULL;
 728
 729   for (i = x = 0; x < num_var_partitions (map); x++)
 730     {
 731       tree p = partition_to_var (map, x);
 732       if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL)
 733         {
 734           if (var == NULL_TREE)
 735             {
 736               var = p;
 737               i = x;
 738             }
 739           else
 740             add_coalesce (cl, i, x,
 741                           coalesce_cost (EXIT_BLOCK_PTR->frequency,
 742                                          maybe_hot_bb_p (EXIT_BLOCK_PTR),
 743                                          false));
 744         }
 745     }
 746 }
 747
 748 /* Coalesce matching constraints in asms.  */
 749
 750 static void
 751 coalesce_asm_operands (var_map map, coalesce_list_p cl)
 752 {
 753   basic_block bb;
 754
 755   FOR_EACH_BB (bb)
 756     {
 757       block_stmt_iterator bsi;
 758       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
 759         {
 760           tree stmt = bsi_stmt (bsi);
 761           unsigned long noutputs, i;
 762           tree *outputs, link;
 763
 764           if (TREE_CODE (stmt) != ASM_EXPR)
 765             continue;
 766
 767           noutputs = list_length (ASM_OUTPUTS (stmt));
 768           outputs = (tree *) alloca (noutputs * sizeof (tree));
 769           for (i = 0, link = ASM_OUTPUTS (stmt); link;
 770                ++i, link = TREE_CHAIN (link))
 771             outputs[i] = TREE_VALUE (link);
 772
 773           for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link))
 774             {
 775               const char *constraint
 776                 = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link)));
 777               tree input = TREE_VALUE (link);
 778               char *end;
 779               unsigned long match;
 780               int p1, p2;
 781
 782               if (TREE_CODE (input) != SSA_NAME && !DECL_P (input))
 783                 continue;
 784
 785               match = strtoul (constraint, &end, 10);
 786               if (match >= noutputs || end == constraint)
 787                 continue;
 788
 789               if (TREE_CODE (outputs[match]) != SSA_NAME
 790                   && !DECL_P (outputs[match]))
 791                 continue;
 792
 793               p1 = var_to_partition (map, outputs[match]);
 794               if (p1 == NO_PARTITION)
 795                 continue;
 796               p2 = var_to_partition (map, input);
 797               if (p2 == NO_PARTITION)
 798                 continue;
 799
 800               add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE,
 801                                                        maybe_hot_bb_p (bb),
 802                                                        false));
 803             }
 804         }
 805     }
 806 }
 807
 808 /* Reduce the number of live ranges in MAP.  Live range information is
 809    returned if FLAGS indicates that we are combining temporaries, otherwise
 810    NULL is returned.  The only partitions which are associated with actual
 811    variables at this point are those which are forced to be coalesced for
 812    various reason. (live on entry, live across abnormal edges, etc.).  */
 813
 814 static tree_live_info_p
 815 coalesce_ssa_name (var_map map, int flags)
 816 {
 817   unsigned num, x;
 818   sbitmap live;
 819   root_var_p rv;
 820   tree_live_info_p liveinfo;
 821   conflict_graph graph;
 822   coalesce_list_p cl = NULL;
 823   sbitmap_iterator sbi;
 824
 825   if (num_var_partitions (map) <= 1)
 826     return NULL;
 827
 828   liveinfo = calculate_live_on_entry (map);
 829   calculate_live_on_exit (liveinfo);
 830   rv = root_var_init (map);
 831
 832   /* Remove single element variable from the list.  */
 833   root_var_compact (rv);
 834
 835   cl = create_coalesce_list (map);
 836
 837   coalesce_phi_operands (map, cl);
 838   coalesce_result_decls (map, cl);
 839   coalesce_asm_operands (map, cl);
 840
 841   /* Build a conflict graph.  */
 842   graph = build_tree_conflict_graph (liveinfo, rv, cl);
 843
 844   if (cl)
 845     {
 846       if (dump_file && (dump_flags & TDF_DETAILS))
 847         {
 848           fprintf (dump_file, "Before sorting:\n");
 849           dump_coalesce_list (dump_file, cl);
 850         }
 851
 852       sort_coalesce_list (cl);
 853
 854       if (dump_file && (dump_flags & TDF_DETAILS))
 855         {
 856           fprintf (dump_file, "\nAfter sorting:\n");
 857           dump_coalesce_list (dump_file, cl);
 858         }
 859     }
 860
 861   /* Put the single element variables back in.  */
 862   root_var_decompact (rv);
 863
 864   /* First, coalesce all live on entry variables to their root variable.
 865      This will ensure the first use is coming from the correct location.  */
 866
 867   num = num_var_partitions (map);
 868   live = sbitmap_alloc (num);
 869   sbitmap_zero (live);
 870
 871   /* Set 'live' vector to indicate live on entry partitions.  */
 872   for (x = 0 ; x < num; x++)
 873     {
 874       tree var = partition_to_var (map, x);
 875       if (default_def (SSA_NAME_VAR (var)) == var)
 876         SET_BIT (live, x);
 877     }
 878
 879   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
 880     {
 881       delete_tree_live_info (liveinfo);
 882       liveinfo = NULL;
 883     }
 884
 885   /* Assign root variable as partition representative for each live on entry
 886      partition.  */
 887   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi)
 888     {
 889       tree var = root_var (rv, root_var_find (rv, x));
 890       var_ann_t ann = var_ann (var);
 891       /* If these aren't already coalesced...  */
 892       if (partition_to_var (map, x) != var)
 893         {
 894           /* This root variable should have not already been assigned
 895              to another partition which is not coalesced with this one.  */
 896           gcc_assert (!ann->out_of_ssa_tag);
 897
 898           if (dump_file && (dump_flags & TDF_DETAILS))
 899             {
 900               print_exprs (dump_file, "Must coalesce ",
 901                            partition_to_var (map, x),
 902                            " with the root variable ", var, ".\n");
 903             }
 904
 905           change_partition_var (map, var, x);
 906         }
 907     }
 908
 909   sbitmap_free (live);
 910
 911   /* Coalesce partitions live across abnormal edges.  */
 912   coalesce_abnormal_edges (map, graph, rv);
 913
 914   if (dump_file && (dump_flags & TDF_DETAILS))
 915     dump_var_map (dump_file, map);
 916
 917   /* Coalesce partitions.  */
 918   coalesce_tpa_members (rv, graph, map, cl,
 919                         ((dump_flags & TDF_DETAILS) ? dump_file
 920                          : NULL));
 921
 922   if (flags & SSANORM_COALESCE_PARTITIONS)
 923     coalesce_tpa_members (rv, graph, map, NULL,
 924                           ((dump_flags & TDF_DETAILS) ? dump_file
 925                            : NULL));
 926   if (cl)
 927     delete_coalesce_list (cl);
 928   root_var_delete (rv);
 929   conflict_graph_delete (graph);
 930
 931   return liveinfo;
 932 }
 933
 934
 935 /* Take the ssa-name var_map MAP, and assign real variables to each
 936    partition.  */
 937
 938 static void
 939 assign_vars (var_map map)
 940 {
 941   int x, i, num, rep;
 942   tree t, var;
 943   var_ann_t ann;
 944   root_var_p rv;
 945
 946   rv = root_var_init (map);
 947   if (!rv)
 948     return;
 949
 950   /* Coalescing may already have forced some partitions to their root
 951      variable. Find these and tag them.  */
 952
 953   num = num_var_partitions (map);
 954   for (x = 0; x < num; x++)
 955     {
 956       var = partition_to_var (map, x);
 957       if (TREE_CODE (var) != SSA_NAME)
 958         {
 959           /* Coalescing will already have verified that more than one
 960              partition doesn't have the same root variable. Simply marked
 961              the variable as assigned.  */
 962           ann = var_ann (var);
 963           ann->out_of_ssa_tag = 1;
 964           if (dump_file && (dump_flags & TDF_DETAILS))
 965             {
 966               fprintf (dump_file, "partition %d has variable ", x);
 967               print_generic_expr (dump_file, var, TDF_SLIM);
 968               fprintf (dump_file, " assigned to it.\n");
 969             }
 970
 971         }
 972     }
 973
 974   num = root_var_num (rv);
 975   for (x = 0; x < num; x++)
 976     {
 977       var = root_var (rv, x);
 978       ann = var_ann (var);
 979       for (i = root_var_first_partition (rv, x);
 980            i != ROOT_VAR_NONE;
 981            i = root_var_next_partition (rv, i))
 982         {
 983           t = partition_to_var (map, i);
 984
 985           if (t == var || TREE_CODE (t) != SSA_NAME)
 986             continue;
 987
 988           rep = var_to_partition (map, t);
 989
 990           if (!ann->out_of_ssa_tag)
 991             {
 992               if (dump_file && (dump_flags & TDF_DETAILS))
 993                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
 994               change_partition_var (map, var, rep);
 995               continue;
 996             }
 997
 998           if (dump_file && (dump_flags & TDF_DETAILS))
 999             print_exprs (dump_file, "", t, " not coalesced with ", var,
1000                          "");
1001
1002           var = create_temp (t);
1003           change_partition_var (map, var, rep);
1004           ann = var_ann (var);
1005
1006           if (dump_file && (dump_flags & TDF_DETAILS))
1007             {
1008               fprintf (dump_file, " -->  New temp:  '");
1009               print_generic_expr (dump_file, var, TDF_SLIM);
1010               fprintf (dump_file, "'\n");
1011             }
1012         }
1013     }
1014
1015   root_var_delete (rv);
1016 }
1017
1018
1019 /* Replace use operand P with whatever variable it has been rewritten to based
1020    on the partitions in MAP.  EXPR is an optional expression vector over SSA
1021    versions which is used to replace P with an expression instead of a variable.
1022    If the stmt is changed, return true.  */
1023
1024 static inline bool
1025 replace_use_variable (var_map map, use_operand_p p, tree *expr)
1026 {
1027   tree new_var;
1028   tree var = USE_FROM_PTR (p);
1029
1030   /* Check if we are replacing this variable with an expression.  */
1031   if (expr)
1032     {
1033       int version = SSA_NAME_VERSION (var);
1034       if (expr[version])
1035         {
1036           tree new_expr = TREE_OPERAND (expr[version], 1);
1037           SET_USE (p, new_expr);
1038           /* Clear the stmt's RHS, or GC might bite us.  */
1039           TREE_OPERAND (expr[version], 1) = NULL_TREE;
1040           return true;
1041         }
1042     }
1043
1044   new_var = var_to_partition_to_var (map, var);
1045   if (new_var)
1046     {
1047       SET_USE (p, new_var);
1048       set_is_used (new_var);
1049       return true;
1050     }
1051   return false;
1052 }
1053
1054
1055 /* Replace def operand DEF_P with whatever variable it has been rewritten to
1056    based on the partitions in MAP.  EXPR is an optional expression vector over
1057    SSA versions which is used to replace DEF_P with an expression instead of a
1058    variable.  If the stmt is changed, return true.  */
1059
1060 static inline bool
1061 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
1062 {
1063   tree new_var;
1064   tree var = DEF_FROM_PTR (def_p);
1065
1066   /* Check if we are replacing this variable with an expression.  */
1067   if (expr)
1068     {
1069       int version = SSA_NAME_VERSION (var);
1070       if (expr[version])
1071         {
1072           tree new_expr = TREE_OPERAND (expr[version], 1);
1073           SET_DEF (def_p, new_expr);
1074           /* Clear the stmt's RHS, or GC might bite us.  */
1075           TREE_OPERAND (expr[version], 1) = NULL_TREE;
1076           return true;
1077         }
1078     }
1079
1080   new_var = var_to_partition_to_var (map, var);
1081   if (new_var)
1082     {
1083       SET_DEF (def_p, new_var);
1084       set_is_used (new_var);
1085       return true;
1086     }
1087   return false;
1088 }
1089
1090
1091 /* Remove any PHI node which is a virtual PHI.  */
1092
1093 static void
1094 eliminate_virtual_phis (void)
1095 {
1096   basic_block bb;
1097   tree phi, next;
1098
1099   FOR_EACH_BB (bb)
1100     {
1101       for (phi = phi_nodes (bb); phi; phi = next)
1102         {
1103           next = PHI_CHAIN (phi);
1104           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1105             {
1106 #ifdef ENABLE_CHECKING
1107               int i;
1108               /* There should be no arguments of this PHI which are in
1109                  the partition list, or we get incorrect results.  */
1110               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1111                 {
1112                   tree arg = PHI_ARG_DEF (phi, i);
1113                   if (TREE_CODE (arg) == SSA_NAME
1114                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1115                     {
1116                       fprintf (stderr, "Argument of PHI is not virtual (");
1117                       print_generic_expr (stderr, arg, TDF_SLIM);
1118                       fprintf (stderr, "), but the result is :");
1119                       print_generic_stmt (stderr, phi, TDF_SLIM);
1120                       internal_error ("SSA corruption");
1121                     }
1122                 }
1123 #endif
1124               remove_phi_node (phi, NULL_TREE);
1125             }
1126         }
1127     }
1128 }
1129
1130
1131 /* This routine will coalesce variables in MAP of the same type which do not
1132    interfere with each other. LIVEINFO is the live range info for variables
1133    of interest.  This will both reduce the memory footprint of the stack, and
1134    allow us to coalesce together local copies of globals and scalarized
1135    component refs.  */
1136
1137 static void
1138 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1139 {
1140   basic_block bb;
1141   type_var_p tv;
1142   tree var;
1143   unsigned x, p, p2;
1144   coalesce_list_p cl;
1145   conflict_graph graph;
1146
1147   cl = create_coalesce_list (map);
1148
1149   /* Merge all the live on entry vectors for coalesced partitions.  */
1150   for (x = 0; x < num_var_partitions (map); x++)
1151     {
1152       var = partition_to_var (map, x);
1153       p = var_to_partition (map, var);
1154       if (p != x)
1155         live_merge_and_clear (liveinfo, p, x);
1156     }
1157
1158   /* When PHI nodes are turned into copies, the result of each PHI node
1159      becomes live on entry to the block. Mark these now.  */
1160   FOR_EACH_BB (bb)
1161     {
1162       tree phi, arg;
1163       unsigned p;
1164
1165       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1166         {
1167           p = var_to_partition (map, PHI_RESULT (phi));
1168
1169           /* Skip virtual PHI nodes.  */
1170           if (p == (unsigned)NO_PARTITION)
1171             continue;
1172
1173           make_live_on_entry (liveinfo, bb, p);
1174
1175           /* Each argument is a potential copy operation. Add any arguments
1176              which are not coalesced to the result to the coalesce list.  */
1177           for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
1178             {
1179               arg = PHI_ARG_DEF (phi, x);
1180               if (!phi_ssa_name_p (arg))
1181                 continue;
1182               p2 = var_to_partition (map, arg);
1183               if (p2 == (unsigned)NO_PARTITION)
1184                 continue;
1185               if (p != p2)
1186                 {
1187                   edge e = PHI_ARG_EDGE (phi, x);
1188
1189                   add_coalesce (cl, p, p2,
1190                                 coalesce_cost (EDGE_FREQUENCY (e),
1191                                                maybe_hot_bb_p (bb),
1192                                                EDGE_CRITICAL_P (e)));
1193                 }
1194             }
1195         }
1196    }
1197
1198
1199   /* Re-calculate live on exit info.  */
1200   calculate_live_on_exit (liveinfo);
1201
1202   if (dump_file && (dump_flags & TDF_DETAILS))
1203     {
1204       fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1205       dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1206
1207       fprintf (dump_file, "Coalesce list from phi nodes:\n");
1208       dump_coalesce_list (dump_file, cl);
1209     }
1210
1211
1212   tv = type_var_init (map);
1213   if (dump_file)
1214     type_var_dump (dump_file, tv);
1215   type_var_compact (tv);
1216   if (dump_file)
1217     type_var_dump (dump_file, tv);
1218
1219   graph = build_tree_conflict_graph (liveinfo, tv, cl);
1220
1221   type_var_decompact (tv);
1222   if (dump_file && (dump_flags & TDF_DETAILS))
1223     {
1224       fprintf (dump_file, "type var list now looks like:n");
1225       type_var_dump (dump_file, tv);
1226
1227       fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1228       dump_coalesce_list (dump_file, cl);
1229     }
1230
1231   sort_coalesce_list (cl);
1232   if (dump_file && (dump_flags & TDF_DETAILS))
1233     {
1234       fprintf (dump_file, "Coalesce list after sorting:\n");
1235       dump_coalesce_list (dump_file, cl);
1236     }
1237
1238   coalesce_tpa_members (tv, graph, map, cl,
1239                         ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1240
1241   type_var_delete (tv);
1242   delete_coalesce_list (cl);
1243 }
1244
1245
1246 /* Temporary Expression Replacement (TER)
1247
1248    Replace SSA version variables during out-of-ssa with their defining
1249    expression if there is only one use of the variable.
1250
1251    A pass is made through the function, one block at a time.  No cross block
1252    information is tracked.
1253
1254    Variables which only have one use, and whose defining stmt is considered
1255    a replaceable expression (see check_replaceable) are entered into
1256    consideration by adding a list of dependent partitions to the version_info
1257    vector for that ssa_name_version.  This information comes from the partition
1258    mapping for each USE.  At the same time, the partition_dep_list vector for
1259    these partitions have this version number entered into their lists.
1260
1261    When the use of a replaceable ssa_variable is encountered, the dependence
1262    list in version_info[] is moved to the "pending_dependence" list in case
1263    the current expression is also replaceable. (To be determined later in
1264    processing this stmt.) version_info[] for the version is then updated to
1265    point to the defining stmt and the 'replaceable' bit is set.
1266
1267    Any partition which is defined by a statement 'kills' any expression which
1268    is dependent on this partition.  Every ssa version in the partitions'
1269    dependence list is removed from future consideration.
1270
1271    All virtual references are lumped together.  Any expression which is
1272    dependent on any virtual variable (via a VUSE) has a dependence added
1273    to the special partition defined by VIRTUAL_PARTITION.
1274
1275    Whenever a V_MAY_DEF is seen, all expressions dependent this
1276    VIRTUAL_PARTITION are removed from consideration.
1277
1278    At the end of a basic block, all expression are removed from consideration
1279    in preparation for the next block.
1280
1281    The end result is a vector over SSA_NAME_VERSION which is passed back to
1282    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1283    replacing the SSA_NAME tree element with the partition it was assigned,
1284    it is replaced with the RHS of the defining expression.  */
1285
1286
1287 /* Dependency list element.  This can contain either a partition index or a
1288    version number, depending on which list it is in.  */
1289
1290 typedef struct value_expr_d
1291 {
1292   int value;
1293   struct value_expr_d *next;
1294 } *value_expr_p;
1295
1296
1297 /* Temporary Expression Replacement (TER) table information.  */
1298
1299 typedef struct temp_expr_table_d
1300 {
1301   var_map map;
1302   void **version_info;
1303   value_expr_p *partition_dep_list;
1304   bitmap replaceable;
1305   bool saw_replaceable;
1306   int virtual_partition;
1307   bitmap partition_in_use;
1308   value_expr_p free_list;
1309   value_expr_p pending_dependence;
1310 } *temp_expr_table_p;
1311
1312 /* Used to indicate a dependency on V_MAY_DEFs.  */
1313 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1314
1315 static temp_expr_table_p new_temp_expr_table (var_map);
1316 static tree *free_temp_expr_table (temp_expr_table_p);
1317 static inline value_expr_p new_value_expr (temp_expr_table_p);
1318 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1319 static inline value_expr_p find_value_in_list (value_expr_p, int,
1320                                                value_expr_p *);
1321 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1322 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
1323                                      value_expr_p);
1324 static value_expr_p remove_value_from_list (value_expr_p *, int);
1325 static void add_dependance (temp_expr_table_p, int, tree);
1326 static bool check_replaceable (temp_expr_table_p, tree);
1327 static void finish_expr (temp_expr_table_p, int, bool);
1328 static void mark_replaceable (temp_expr_table_p, tree);
1329 static inline void kill_expr (temp_expr_table_p, int, bool);
1330 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1331 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1332 static tree *find_replaceable_exprs (var_map);
1333 static void dump_replaceable_exprs (FILE *, tree *);
1334
1335
1336 /* Create a new TER table for MAP.  */
1337
1338 static temp_expr_table_p
1339 new_temp_expr_table (var_map map)
1340 {
1341   temp_expr_table_p t;
1342
1343   t = XNEW (struct temp_expr_table_d);
1344   t->map = map;
1345
1346   t->version_info = XCNEWVEC (void *, num_ssa_names + 1);
1347   t->partition_dep_list = XCNEWVEC (value_expr_p,
1348                                     num_var_partitions (map) + 1);
1349
1350   t->replaceable = BITMAP_ALLOC (NULL);
1351   t->partition_in_use = BITMAP_ALLOC (NULL);
1352
1353   t->saw_replaceable = false;
1354   t->virtual_partition = num_var_partitions (map);
1355   t->free_list = NULL;
1356   t->pending_dependence = NULL;
1357
1358   return t;
1359 }
1360
1361
1362 /* Free TER table T.  If there are valid replacements, return the expression
1363    vector.  */
1364
1365 static tree *
1366 free_temp_expr_table (temp_expr_table_p t)
1367 {
1368   value_expr_p p;
1369   tree *ret = NULL;
1370
1371 #ifdef ENABLE_CHECKING
1372   unsigned x;
1373   for (x = 0; x <= num_var_partitions (t->map); x++)
1374     gcc_assert (!t->partition_dep_list[x]);
1375 #endif
1376
1377   while ((p = t->free_list))
1378     {
1379       t->free_list = p->next;
1380       free (p);
1381     }
1382
1383   BITMAP_FREE (t->partition_in_use);
1384   BITMAP_FREE (t->replaceable);
1385
1386   free (t->partition_dep_list);
1387   if (t->saw_replaceable)
1388     ret = (tree *)t->version_info;
1389   else
1390     free (t->version_info);
1391
1392   free (t);
1393   return ret;
1394 }
1395
1396
1397 /* Allocate a new value list node. Take it from the free list in TABLE if
1398    possible.  */
1399
1400 static inline value_expr_p
1401 new_value_expr (temp_expr_table_p table)
1402 {
1403   value_expr_p p;
1404   if (table->free_list)
1405     {
1406       p = table->free_list;
1407       table->free_list = p->next;
1408     }
1409   else
1410     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1411
1412   return p;
1413 }
1414
1415
1416 /* Add value list node P to the free list in TABLE.  */
1417
1418 static inline void
1419 free_value_expr (temp_expr_table_p table, value_expr_p p)
1420 {
1421   p->next = table->free_list;
1422   table->free_list = p;
1423 }
1424
1425
1426 /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,
1427    else return NULL.  If LAST_PTR is provided, it will point to the previous
1428    item upon return, or NULL if this is the first item in the list.  */
1429
1430 static inline value_expr_p
1431 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1432 {
1433   value_expr_p curr;
1434   value_expr_p last = NULL;
1435
1436   for (curr = list; curr; last = curr, curr = curr->next)
1437     {
1438       if (curr->value == value)
1439         break;
1440     }
1441   if (last_ptr)
1442     *last_ptr = last;
1443   return curr;
1444 }
1445
1446
1447 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression
1448    table */
1449
1450 static inline void
1451 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1452 {
1453   value_expr_p info;
1454
1455   if (!find_value_in_list (*list, value, NULL))
1456     {
1457       info = new_value_expr (tab);
1458       info->value = value;
1459       info->next = *list;
1460       *list = info;
1461     }
1462 }
1463
1464
1465 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1466    it is already in the list. TAB is the expression table.  */
1467
1468 static inline void
1469 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1470 {
1471   if (find_value_in_list (*list, info->value, NULL))
1472     free_value_expr (tab, info);
1473   else
1474     {
1475       info->next = *list;
1476       *list = info;
1477     }
1478 }
1479
1480
1481 /* Look for VALUE in LIST.  If found, remove it from the list and return it's
1482    pointer.  */
1483
1484 static value_expr_p
1485 remove_value_from_list (value_expr_p *list, int value)
1486 {
1487   value_expr_p info, last;
1488
1489   info = find_value_in_list (*list, value, &last);
1490   if (!info)
1491     return NULL;
1492   if (!last)
1493     *list = info->next;
1494   else
1495     last->next = info->next;
1496
1497   return info;
1498 }
1499
1500
1501 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
1502    replaceable by an expression, add a dependence each of the elements of the
1503    expression.  These are contained in the pending list.  TAB is the
1504    expression table.  */
1505
1506 static void
1507 add_dependance (temp_expr_table_p tab, int version, tree var)
1508 {
1509   int i, x;
1510   value_expr_p info;
1511
1512   i = SSA_NAME_VERSION (var);
1513   if (bitmap_bit_p (tab->replaceable, i))
1514     {
1515       /* This variable is being substituted, so use whatever dependences
1516          were queued up when we marked this as replaceable earlier.  */
1517       while ((info = tab->pending_dependence))
1518         {
1519           tab->pending_dependence = info->next;
1520           /* Get the partition this variable was dependent on. Reuse this
1521              object to represent the current  expression instead.  */
1522           x = info->value;
1523           info->value = version;
1524           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1525           add_value_to_list (tab,
1526                              (value_expr_p *)&(tab->version_info[version]), x);
1527           bitmap_set_bit (tab->partition_in_use, x);
1528         }
1529     }
1530   else
1531     {
1532       i = var_to_partition (tab->map, var);
1533       gcc_assert (i != NO_PARTITION);
1534       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1535       add_value_to_list (tab,
1536                          (value_expr_p *)&(tab->version_info[version]), i);
1537       bitmap_set_bit (tab->partition_in_use, i);
1538     }
1539 }
1540
1541
1542 /* Check if expression STMT is suitable for replacement in table TAB.  If so,
1543    create an expression entry.  Return true if this stmt is replaceable.  */
1544
1545 static bool
1546 check_replaceable (temp_expr_table_p tab, tree stmt)
1547 {
1548   tree var, def;
1549   int version;
1550   var_map map = tab->map;
1551   ssa_op_iter iter;
1552   tree call_expr;
1553
1554   if (TREE_CODE (stmt) != MODIFY_EXPR)
1555     return false;
1556
1557   /* Punt if there is more than 1 def, or more than 1 use.  */
1558   def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1559   if (!def)
1560     return false;
1561
1562   if (version_ref_count (map, def) != 1)
1563     return false;
1564
1565   /* There must be no V_MAY_DEFS or V_MUST_DEFS.  */
1566   if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF))))
1567     return false;
1568
1569   /* Float expressions must go through memory if float-store is on.  */
1570   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1571     return false;
1572
1573   /* Calls to functions with side-effects cannot be replaced.  */
1574   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1575     {
1576       int call_flags = call_expr_flags (call_expr);
1577       if (TREE_SIDE_EFFECTS (call_expr)
1578           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1579         return false;
1580     }
1581
1582   version = SSA_NAME_VERSION (def);
1583
1584   /* Add this expression to the dependency list for each use partition.  */
1585   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1586     {
1587       add_dependance (tab, version, var);
1588     }
1589
1590   /* If there are VUSES, add a dependence on virtual defs.  */
1591   if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE))
1592     {
1593       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1594                          VIRTUAL_PARTITION (tab));
1595       add_value_to_list (tab,
1596                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1597                          version);
1598       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1599     }
1600
1601   return true;
1602 }
1603
1604
1605 /* This function will remove the expression for VERSION from replacement
1606    consideration.n table TAB  If 'replace' is true, it is marked as
1607    replaceable, otherwise not.  */
1608
1609 static void
1610 finish_expr (temp_expr_table_p tab, int version, bool replace)
1611 {
1612   value_expr_p info, tmp;
1613   int partition;
1614
1615   /* Remove this expression from its dependent lists.  The partition dependence
1616      list is retained and transfered later to whomever uses this version.  */
1617   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1618     {
1619       partition = info->value;
1620       gcc_assert (tab->partition_dep_list[partition]);
1621       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1622                                     version);
1623       gcc_assert (tmp);
1624       free_value_expr (tab, tmp);
1625       /* Only clear the bit when the dependency list is emptied via
1626          a replacement. Otherwise kill_expr will take care of it.  */
1627       if (!(tab->partition_dep_list[partition]) && replace)
1628         bitmap_clear_bit (tab->partition_in_use, partition);
1629       tmp = info->next;
1630       if (!replace)
1631         free_value_expr (tab, info);
1632     }
1633
1634   if (replace)
1635     {
1636       tab->saw_replaceable = true;
1637       bitmap_set_bit (tab->replaceable, version);
1638     }
1639   else
1640     {
1641       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1642       tab->version_info[version] = NULL;
1643     }
1644 }
1645
1646
1647 /* Mark the expression associated with VAR as replaceable, and enter
1648    the defining stmt into the version_info table TAB.  */
1649
1650 static void
1651 mark_replaceable (temp_expr_table_p tab, tree var)
1652 {
1653   value_expr_p info;
1654   int version = SSA_NAME_VERSION (var);
1655   finish_expr (tab, version, true);
1656
1657   /* Move the dependence list to the pending list.  */
1658   if (tab->version_info[version])
1659     {
1660       info = (value_expr_p) tab->version_info[version];
1661       for ( ; info->next; info = info->next)
1662         continue;
1663       info->next = tab->pending_dependence;
1664       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1665     }
1666
1667   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1668 }
1669
1670
1671 /* This function marks any expression in TAB which is dependent on PARTITION
1672    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1673    should have its bit cleared.  Since this routine can be called within an
1674    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1675
1676 static inline void
1677 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1678 {
1679   value_expr_p ptr;
1680
1681   /* Mark every active expr dependent on this var as not replaceable.  */
1682   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1683     finish_expr (tab, ptr->value, false);
1684
1685   if (clear_bit)
1686     bitmap_clear_bit (tab->partition_in_use, partition);
1687 }
1688
1689
1690 /* This function kills all expressions in TAB which are dependent on virtual
1691    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1692
1693 static inline void
1694 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1695 {
1696   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1697 }
1698
1699
1700 /* This function processes basic block BB, and looks for variables which can
1701    be replaced by their expressions.  Results are stored in TAB.  */
1702
1703 static void
1704 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1705 {
1706   block_stmt_iterator bsi;
1707   tree stmt, def;
1708   stmt_ann_t ann;
1709   int partition;
1710   var_map map = tab->map;
1711   value_expr_p p;
1712   ssa_op_iter iter;
1713
1714   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1715     {
1716       stmt = bsi_stmt (bsi);
1717       ann = stmt_ann (stmt);
1718
1719       /* Determine if this stmt finishes an existing expression.  */
1720       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1721         {
1722           if (tab->version_info[SSA_NAME_VERSION (def)])
1723             {
1724               bool same_root_var = false;
1725               tree def2;
1726               ssa_op_iter iter2;
1727
1728               /* See if the root variables are the same.  If they are, we
1729                  do not want to do the replacement to avoid problems with
1730                  code size, see PR tree-optimization/17549.  */
1731               FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF)
1732                 if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2))
1733                   {
1734                     same_root_var = true;
1735                     break;
1736                   }
1737
1738               /* Mark expression as replaceable unless stmt is volatile
1739                  or DEF sets the same root variable as STMT.  */
1740               if (!ann->has_volatile_ops && !same_root_var)
1741                 mark_replaceable (tab, def);
1742               else
1743                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1744             }
1745         }
1746
1747       /* Next, see if this stmt kills off an active expression.  */
1748       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1749         {
1750           partition = var_to_partition (map, def);
1751           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1752             kill_expr (tab, partition, true);
1753         }
1754
1755       /* Now see if we are creating a new expression or not.  */
1756       if (!ann->has_volatile_ops)
1757         check_replaceable (tab, stmt);
1758
1759       /* Free any unused dependency lists.  */
1760       while ((p = tab->pending_dependence))
1761         {
1762           tab->pending_dependence = p->next;
1763           free_value_expr (tab, p);
1764         }
1765
1766       /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand.  */
1767       if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS))
1768         kill_virtual_exprs (tab, true);
1769     }
1770 }
1771
1772
1773 /* This function is the driver routine for replacement of temporary expressions
1774    in the SSA->normal phase, operating on MAP.  If there are replaceable
1775    expressions, a table is returned which maps SSA versions to the
1776    expressions they should be replaced with.  A NULL_TREE indicates no
1777    replacement should take place.  If there are no replacements at all,
1778    NULL is returned by the function, otherwise an expression vector indexed
1779    by SSA_NAME version numbers.  */
1780
1781 static tree *
1782 find_replaceable_exprs (var_map map)
1783 {
1784   basic_block bb;
1785   unsigned i;
1786   temp_expr_table_p table;
1787   tree *ret;
1788
1789   table = new_temp_expr_table (map);
1790   FOR_EACH_BB (bb)
1791     {
1792       bitmap_iterator bi;
1793
1794       find_replaceable_in_bb (table, bb);
1795       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1796         {
1797           kill_expr (table, i, false);
1798         }
1799     }
1800
1801   ret = free_temp_expr_table (table);
1802   return ret;
1803 }
1804
1805
1806 /* Dump TER expression table EXPR to file F.  */
1807
1808 static void
1809 dump_replaceable_exprs (FILE *f, tree *expr)
1810 {
1811   tree stmt, var;
1812   int x;
1813   fprintf (f, "\nReplacing Expressions\n");
1814   for (x = 0; x < (int)num_ssa_names + 1; x++)
1815     if (expr[x])
1816       {
1817         stmt = expr[x];
1818         var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF);
1819         gcc_assert (var != NULL_TREE);
1820         print_generic_expr (f, var, TDF_SLIM);
1821         fprintf (f, " replace with --> ");
1822         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1823         fprintf (f, "\n");
1824       }
1825   fprintf (f, "\n");
1826 }
1827
1828
1829 /* This function will rewrite the current program using the variable mapping
1830    found in MAP.  If the replacement vector VALUES is provided, any
1831    occurrences of partitions with non-null entries in the vector will be
1832    replaced with the expression in the vector instead of its mapped
1833    variable.  */
1834
1835 static void
1836 rewrite_trees (var_map map, tree *values)
1837 {
1838   elim_graph g;
1839   basic_block bb;
1840   block_stmt_iterator si;
1841   edge e;
1842   tree phi;
1843   bool changed;
1844
1845 #ifdef ENABLE_CHECKING
1846   /* Search for PHIs where the destination has no partition, but one
1847      or more arguments has a partition.  This should not happen and can
1848      create incorrect code.  */
1849   FOR_EACH_BB (bb)
1850     {
1851       tree phi;
1852
1853       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1854         {
1855           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1856
1857           if (T0 == NULL_TREE)
1858             {
1859               int i;
1860
1861               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1862                 {
1863                   tree arg = PHI_ARG_DEF (phi, i);
1864
1865                   if (TREE_CODE (arg) == SSA_NAME
1866                       && var_to_partition (map, arg) != NO_PARTITION)
1867                     {
1868                       fprintf (stderr, "Argument of PHI is in a partition :(");
1869                       print_generic_expr (stderr, arg, TDF_SLIM);
1870                       fprintf (stderr, "), but the result is not :");
1871                       print_generic_stmt (stderr, phi, TDF_SLIM);
1872                       internal_error ("SSA corruption");
1873                     }
1874                 }
1875             }
1876         }
1877     }
1878 #endif
1879
1880   /* Replace PHI nodes with any required copies.  */
1881   g = new_elim_graph (map->num_partitions);
1882   g->map = map;
1883   FOR_EACH_BB (bb)
1884     {
1885       for (si = bsi_start (bb); !bsi_end_p (si); )
1886         {
1887           tree stmt = bsi_stmt (si);
1888           use_operand_p use_p, copy_use_p;
1889           def_operand_p def_p;
1890           bool remove = false, is_copy = false;
1891           int num_uses = 0;
1892           stmt_ann_t ann;
1893           ssa_op_iter iter;
1894
1895           ann = stmt_ann (stmt);
1896           changed = false;
1897
1898           if (TREE_CODE (stmt) == MODIFY_EXPR
1899               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1900             is_copy = true;
1901
1902           copy_use_p = NULL_USE_OPERAND_P;
1903           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1904             {
1905               if (replace_use_variable (map, use_p, values))
1906                 changed = true;
1907               copy_use_p = use_p;
1908               num_uses++;
1909             }
1910
1911           if (num_uses != 1)
1912             is_copy = false;
1913
1914           def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF);
1915
1916           if (def_p != NULL)
1917             {
1918               /* Mark this stmt for removal if it is the list of replaceable
1919                  expressions.  */
1920               if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))])
1921                 remove = true;
1922               else
1923                 {
1924                   if (replace_def_variable (map, def_p, NULL))
1925                     changed = true;
1926                   /* If both SSA_NAMEs coalesce to the same variable,
1927                      mark the now redundant copy for removal.  */
1928                   if (is_copy)
1929                     {
1930                       gcc_assert (copy_use_p != NULL_USE_OPERAND_P);
1931                       if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p))
1932                         remove = true;
1933                     }
1934                 }
1935             }
1936           else
1937             FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1938               if (replace_def_variable (map, def_p, NULL))
1939                 changed = true;
1940
1941           /* Remove any stmts marked for removal.  */
1942           if (remove)
1943             bsi_remove (&si, true);
1944           else
1945             bsi_next (&si);
1946         }
1947
1948       phi = phi_nodes (bb);
1949       if (phi)
1950         {
1951           edge_iterator ei;
1952           FOR_EACH_EDGE (e, ei, bb->preds)
1953             eliminate_phi (e, g);
1954         }
1955     }
1956
1957   delete_elim_graph (g);
1958 }
1959
1960
1961 DEF_VEC_ALLOC_P(edge,heap);
1962
1963 /* These are the local work structures used to determine the best place to
1964    insert the copies that were placed on edges by the SSA->normal pass..  */
1965 static VEC(edge,heap) *edge_leader;
1966 static VEC(tree,heap) *stmt_list;
1967 static bitmap leader_has_match = NULL;
1968 static edge leader_match = NULL;
1969
1970
1971 /* Pass this function to make_forwarder_block so that all the edges with
1972    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1973 static bool
1974 same_stmt_list_p (edge e)
1975 {
1976   return (e->aux == (PTR) leader_match) ? true : false;
1977 }
1978
1979
1980 /* Return TRUE if S1 and S2 are equivalent copies.  */
1981 static inline bool
1982 identical_copies_p (tree s1, tree s2)
1983 {
1984 #ifdef ENABLE_CHECKING
1985   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1986   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1987   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1988   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1989 #endif
1990
1991   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1992     return false;
1993
1994   s1 = TREE_OPERAND (s1, 1);
1995   s2 = TREE_OPERAND (s2, 1);
1996
1997   if (s1 != s2)
1998     return false;
1999
2000   return true;
2001 }
2002
2003
2004 /* Compare the PENDING_STMT list for two edges, and return true if the lists
2005    contain the same sequence of copies.  */
2006
2007 static inline bool
2008 identical_stmt_lists_p (edge e1, edge e2)
2009 {
2010   tree t1 = PENDING_STMT (e1);
2011   tree t2 = PENDING_STMT (e2);
2012   tree_stmt_iterator tsi1, tsi2;
2013
2014   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
2015   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
2016
2017   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
2018        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
2019        tsi_next (&tsi1), tsi_next (&tsi2))
2020     {
2021       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
2022         break;
2023     }
2024
2025   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
2026     return false;
2027
2028   return true;
2029 }
2030
2031
2032 /* Allocate data structures used in analyze_edges_for_bb.   */
2033
2034 static void
2035 init_analyze_edges_for_bb (void)
2036 {
2037   edge_leader = VEC_alloc (edge, heap, 25);
2038   stmt_list = VEC_alloc (tree, heap, 25);
2039   leader_has_match = BITMAP_ALLOC (NULL);
2040 }
2041
2042
2043 /* Free data structures used in analyze_edges_for_bb.   */
2044
2045 static void
2046 fini_analyze_edges_for_bb (void)
2047 {
2048   VEC_free (edge, heap, edge_leader);
2049   VEC_free (tree, heap, stmt_list);
2050   BITMAP_FREE (leader_has_match);
2051 }
2052
2053
2054 /* Look at all the incoming edges to block BB, and decide where the best place
2055    to insert the stmts on each edge are, and perform those insertions.   Output
2056    any debug information to DEBUG_FILE.  */
2057
2058 static void
2059 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2060 {
2061   edge e;
2062   edge_iterator ei;
2063   int count;
2064   unsigned int x;
2065   bool have_opportunity;
2066   block_stmt_iterator bsi;
2067   tree stmt;
2068   edge single_edge = NULL;
2069   bool is_label;
2070   edge leader;
2071
2072   count = 0;
2073
2074   /* Blocks which contain at least one abnormal edge cannot use
2075      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
2076      found on edges in these block.  */
2077   have_opportunity = true;
2078   FOR_EACH_EDGE (e, ei, bb->preds)
2079     if (e->flags & EDGE_ABNORMAL)
2080       {
2081         have_opportunity = false;
2082         break;
2083       }
2084
2085   if (!have_opportunity)
2086     {
2087       FOR_EACH_EDGE (e, ei, bb->preds)
2088         if (PENDING_STMT (e))
2089           bsi_commit_one_edge_insert (e, NULL);
2090       return;
2091     }
2092   /* Find out how many edges there are with interesting pending stmts on them.
2093      Commit the stmts on edges we are not interested in.  */
2094   FOR_EACH_EDGE (e, ei, bb->preds)
2095     {
2096       if (PENDING_STMT (e))
2097         {
2098           gcc_assert (!(e->flags & EDGE_ABNORMAL));
2099           if (e->flags & EDGE_FALLTHRU)
2100             {
2101               bsi = bsi_start (e->src);
2102               if (!bsi_end_p (bsi))
2103                 {
2104                   stmt = bsi_stmt (bsi);
2105                   bsi_next (&bsi);
2106                   gcc_assert (stmt != NULL_TREE);
2107                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2108                   /* Punt if it has non-label stmts, or isn't local.  */
2109                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2110                       || !bsi_end_p (bsi))
2111                     {
2112                       bsi_commit_one_edge_insert (e, NULL);
2113                       continue;
2114                     }
2115                 }
2116             }
2117           single_edge = e;
2118           count++;
2119         }
2120     }
2121
2122   /* If there aren't at least 2 edges, no sharing will happen.  */
2123   if (count < 2)
2124     {
2125       if (single_edge)
2126         bsi_commit_one_edge_insert (single_edge, NULL);
2127       return;
2128     }
2129
2130   /* Ensure that we have empty worklists.  */
2131 #ifdef ENABLE_CHECKING
2132   gcc_assert (VEC_length (edge, edge_leader) == 0);
2133   gcc_assert (VEC_length (tree, stmt_list) == 0);
2134   gcc_assert (bitmap_empty_p (leader_has_match));
2135 #endif
2136
2137   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2138      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2139      block.  The leader edge destination is the block which all the other edges
2140      with the same stmt list will be redirected to.  */
2141   have_opportunity = false;
2142   FOR_EACH_EDGE (e, ei, bb->preds)
2143     {
2144       if (PENDING_STMT (e))
2145         {
2146           bool found = false;
2147
2148           /* Look for the same stmt list in edge leaders list.  */
2149           for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2150             {
2151               if (identical_stmt_lists_p (leader, e))
2152                 {
2153                   /* Give this edge the same stmt list pointer.  */
2154                   PENDING_STMT (e) = NULL;
2155                   e->aux = leader;
2156                   bitmap_set_bit (leader_has_match, x);
2157                   have_opportunity = found = true;
2158                   break;
2159                 }
2160             }
2161
2162           /* If no similar stmt list, add this edge to the leader list.  */
2163           if (!found)
2164             {
2165               VEC_safe_push (edge, heap, edge_leader, e);
2166               VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e));
2167             }
2168         }
2169      }
2170
2171   /* If there are no similar lists, just issue the stmts.  */
2172   if (!have_opportunity)
2173     {
2174       for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2175         bsi_commit_one_edge_insert (leader, NULL);
2176       VEC_truncate (edge, edge_leader, 0);
2177       VEC_truncate (tree, stmt_list, 0);
2178       bitmap_clear (leader_has_match);
2179       return;
2180     }
2181
2182
2183   if (debug_file)
2184     fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2185              bb->index);
2186
2187
2188   /* For each common list, create a forwarding block and issue the stmt's
2189      in that block.  */
2190   for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++)
2191     if (bitmap_bit_p (leader_has_match, x))
2192       {
2193         edge new_edge;
2194         block_stmt_iterator bsi;
2195         tree curr_stmt_list;
2196
2197         leader_match = leader;
2198
2199         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2200            for various PHI manipulations, so it gets cleared whhen calls are
2201            made to make_forwarder_block(). So make sure the edge is clear,
2202            and use the saved stmt list.  */
2203         PENDING_STMT (leader) = NULL;
2204         leader->aux = leader;
2205         curr_stmt_list = VEC_index (tree, stmt_list, x);
2206
2207         new_edge = make_forwarder_block (leader->dest, same_stmt_list_p,
2208                                          NULL);
2209         bb = new_edge->dest;
2210         if (debug_file)
2211           {
2212             fprintf (debug_file, "Splitting BB %d for Common stmt list.  ",
2213                      leader->dest->index);
2214             fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2215             print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2216           }
2217
2218         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2219           {
2220             e->aux = NULL;
2221             if (debug_file)
2222               fprintf (debug_file, "  Edge (%d->%d) lands here.\n",
2223                        e->src->index, e->dest->index);
2224           }
2225
2226         bsi = bsi_last (leader->dest);
2227         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2228
2229         leader_match = NULL;
2230         /* We should never get a new block now.  */
2231       }
2232     else
2233       {
2234         PENDING_STMT (leader) = VEC_index (tree, stmt_list, x);
2235         bsi_commit_one_edge_insert (leader, NULL);
2236       }
2237
2238
2239   /* Clear the working data structures.  */
2240   VEC_truncate (edge, edge_leader, 0);
2241   VEC_truncate (tree, stmt_list, 0);
2242   bitmap_clear (leader_has_match);
2243 }
2244
2245
2246 /* This function will analyze the insertions which were performed on edges,
2247    and decide whether they should be left on that edge, or whether it is more
2248    efficient to emit some subset of them in a single block.  All stmts are
2249    inserted somewhere, and if non-NULL, debug information is printed via
2250    DUMP_FILE.  */
2251
2252 static void
2253 perform_edge_inserts (FILE *dump_file)
2254 {
2255   basic_block bb;
2256
2257   if (dump_file)
2258     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2259
2260   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
2261      incrementally update the dominator information.  Since we don't
2262      need dominator information after this pass, go ahead and free the
2263      dominator information.  */
2264   free_dominance_info (CDI_DOMINATORS);
2265   free_dominance_info (CDI_POST_DOMINATORS);
2266
2267   /* Allocate data structures used in analyze_edges_for_bb.   */
2268   init_analyze_edges_for_bb ();
2269
2270   FOR_EACH_BB (bb)
2271     analyze_edges_for_bb (bb, dump_file);
2272
2273   analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2274
2275   /* Free data structures used in analyze_edges_for_bb.   */
2276   fini_analyze_edges_for_bb ();
2277
2278 #ifdef ENABLE_CHECKING
2279   {
2280     edge_iterator ei;
2281     edge e;
2282     FOR_EACH_BB (bb)
2283       {
2284         FOR_EACH_EDGE (e, ei, bb->preds)
2285           {
2286             if (PENDING_STMT (e))
2287               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2288                      e->src->index, e->dest->index);
2289           }
2290         FOR_EACH_EDGE (e, ei, bb->succs)
2291           {
2292             if (PENDING_STMT (e))
2293               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2294                      e->src->index, e->dest->index);
2295           }
2296       }
2297     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2298       {
2299         if (PENDING_STMT (e))
2300           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2301                  e->src->index, e->dest->index);
2302       }
2303     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2304       {
2305         if (PENDING_STMT (e))
2306           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2307                  e->src->index, e->dest->index);
2308       }
2309   }
2310 #endif
2311 }
2312
2313
2314 /* Remove the variables specified in MAP from SSA form.  Any debug information
2315    is sent to DUMP.  FLAGS indicate what options should be used.  */
2316
2317 static void
2318 remove_ssa_form (FILE *dump, var_map map, int flags)
2319 {
2320   tree_live_info_p liveinfo;
2321   basic_block bb;
2322   tree phi, next;
2323   FILE *save;
2324   tree *values = NULL;
2325
2326   save = dump_file;
2327   dump_file = dump;
2328
2329   /* If we are not combining temps, don't calculate live ranges for variables
2330      with only one SSA version.  */
2331   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2332     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2333   else
2334     compact_var_map (map, VARMAP_NORMAL);
2335
2336   if (dump_file && (dump_flags & TDF_DETAILS))
2337     dump_var_map (dump_file, map);
2338
2339   liveinfo = coalesce_ssa_name (map, flags);
2340
2341   /* Make sure even single occurrence variables are in the list now.  */
2342   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2343     compact_var_map (map, VARMAP_NORMAL);
2344
2345   if (dump_file && (dump_flags & TDF_DETAILS))
2346     {
2347       fprintf (dump_file, "After Coalescing:\n");
2348       dump_var_map (dump_file, map);
2349     }
2350
2351   if (flags & SSANORM_PERFORM_TER)
2352     {
2353       values = find_replaceable_exprs (map);
2354       if (values && dump_file && (dump_flags & TDF_DETAILS))
2355         dump_replaceable_exprs (dump_file, values);
2356     }
2357
2358   /* Assign real variables to the partitions now.  */
2359   assign_vars (map);
2360
2361   if (dump_file && (dump_flags & TDF_DETAILS))
2362     {
2363       fprintf (dump_file, "After Root variable replacement:\n");
2364       dump_var_map (dump_file, map);
2365     }
2366
2367   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2368     {
2369       coalesce_vars (map, liveinfo);
2370       if (dump_file && (dump_flags & TDF_DETAILS))
2371         {
2372           fprintf (dump_file, "After variable memory coalescing:\n");
2373           dump_var_map (dump_file, map);
2374         }
2375     }
2376
2377   if (liveinfo)
2378     delete_tree_live_info (liveinfo);
2379
2380   rewrite_trees (map, values);
2381
2382   if (values)
2383     free (values);
2384
2385   /* Remove phi nodes which have been translated back to real variables.  */
2386   FOR_EACH_BB (bb)
2387     {
2388       for (phi = phi_nodes (bb); phi; phi = next)
2389         {
2390           next = PHI_CHAIN (phi);
2391           remove_phi_node (phi, NULL_TREE);
2392         }
2393     }
2394
2395   /* we no longer maintain the SSA operand cache at this point.  */
2396   fini_ssa_operands ();
2397
2398   /* If any copies were inserted on edges, analyze and insert them now.  */
2399   perform_edge_inserts (dump_file);
2400
2401   dump_file = save;
2402 }
2403
2404 /* Search every PHI node for arguments associated with backedges which
2405    we can trivially determine will need a copy (the argument is either
2406    not an SSA_NAME or the argument has a different underlying variable
2407    than the PHI result).
2408
2409    Insert a copy from the PHI argument to a new destination at the
2410    end of the block with the backedge to the top of the loop.  Update
2411    the PHI argument to reference this new destination.  */
2412
2413 static void
2414 insert_backedge_copies (void)
2415 {
2416   basic_block bb;
2417
2418   FOR_EACH_BB (bb)
2419     {
2420       tree phi;
2421
2422       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2423         {
2424           tree result = PHI_RESULT (phi);
2425           tree result_var;
2426           int i;
2427
2428           if (!is_gimple_reg (result))
2429             continue;
2430
2431           result_var = SSA_NAME_VAR (result);
2432           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2433             {
2434               tree arg = PHI_ARG_DEF (phi, i);
2435               edge e = PHI_ARG_EDGE (phi, i);
2436
2437               /* If the argument is not an SSA_NAME, then we will
2438                  need a constant initialization.  If the argument is
2439                  an SSA_NAME with a different underlying variable and
2440                  we are not combining temporaries, then we will
2441                  need a copy statement.  */
2442               if ((e->flags & EDGE_DFS_BACK)
2443                   && (TREE_CODE (arg) != SSA_NAME
2444                       || (!flag_tree_combine_temps
2445                           && SSA_NAME_VAR (arg) != result_var)))
2446                 {
2447                   tree stmt, name, last = NULL;
2448                   block_stmt_iterator bsi;
2449
2450                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2451                   if (!bsi_end_p (bsi))
2452                     last = bsi_stmt (bsi);
2453
2454                   /* In theory the only way we ought to get back to the
2455                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2456                      However, better safe than sorry.
2457
2458                      If the block ends with a control statement or
2459                      something that might throw, then we have to
2460                      insert this assignment before the last
2461                      statement.  Else insert it after the last statement.  */
2462                   if (last && stmt_ends_bb_p (last))
2463                     {
2464                       /* If the last statement in the block is the definition
2465                          site of the PHI argument, then we can't insert
2466                          anything after it.  */
2467                       if (TREE_CODE (arg) == SSA_NAME
2468                           && SSA_NAME_DEF_STMT (arg) == last)
2469                         continue;
2470                     }
2471
2472                   /* Create a new instance of the underlying
2473                      variable of the PHI result.  */
2474                   stmt = build2 (MODIFY_EXPR, TREE_TYPE (result_var),
2475                                  NULL_TREE, PHI_ARG_DEF (phi, i));
2476                   name = make_ssa_name (result_var, stmt);
2477                   TREE_OPERAND (stmt, 0) = name;
2478
2479                   /* Insert the new statement into the block and update
2480                      the PHI node.  */
2481                   if (last && stmt_ends_bb_p (last))
2482                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2483                   else
2484                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2485                   SET_PHI_ARG_DEF (phi, i, name);
2486                 }
2487             }
2488         }
2489     }
2490 }
2491
2492 /* Take the current function out of SSA form, as described in
2493    R. Morgan, ``Building an Optimizing Compiler'',
2494    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2495
2496 static void
2497 rewrite_out_of_ssa (void)
2498 {
2499   var_map map;
2500   int var_flags = 0;
2501   int ssa_flags = 0;
2502
2503   /* If elimination of a PHI requires inserting a copy on a backedge,
2504      then we will have to split the backedge which has numerous
2505      undesirable performance effects.
2506
2507      A significant number of such cases can be handled here by inserting
2508      copies into the loop itself.  */
2509   insert_backedge_copies ();
2510
2511   if (!flag_tree_live_range_split)
2512     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2513
2514   eliminate_virtual_phis ();
2515
2516   if (dump_file && (dump_flags & TDF_DETAILS))
2517     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2518
2519   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2520   if (flag_tree_ter && !flag_mudflap)
2521     var_flags = SSA_VAR_MAP_REF_COUNT;
2522
2523   map = create_ssa_var_map (var_flags);
2524
2525   if (flag_tree_combine_temps)
2526     ssa_flags |= SSANORM_COMBINE_TEMPS;
2527   if (flag_tree_ter && !flag_mudflap)
2528     ssa_flags |= SSANORM_PERFORM_TER;
2529
2530   remove_ssa_form (dump_file, map, ssa_flags);
2531
2532   if (dump_file && (dump_flags & TDF_DETAILS))
2533     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2534
2535   /* Flush out flow graph and SSA data.  */
2536   delete_var_map (map);
2537
2538   in_ssa_p = false;
2539 }
2540
2541
2542 /* Define the parameters of the out of SSA pass.  */
2543
2544 struct tree_opt_pass pass_del_ssa =
2545 {
2546   "optimized",                          /* name */
2547   NULL,                                 /* gate */
2548   rewrite_out_of_ssa,                   /* execute */
2549   NULL,                                 /* sub */
2550   NULL,                                 /* next */
2551   0,                                    /* static_pass_number */
2552   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2553   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2554   0,                                    /* properties_provided */
2555   /* ??? If TER is enabled, we also kill gimple.  */
2556   PROP_ssa,                             /* properties_destroyed */
2557   TODO_verify_ssa | TODO_verify_flow
2558     | TODO_verify_stmts,                /* todo_flags_start */
2559   TODO_dump_func
2560   | TODO_ggc_collect
2561   | TODO_remove_unused_locals,          /* todo_flags_finish */
2562   0                                     /* letter */
2563 };