gcc/tree-outof-ssa.c

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