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