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             tmp = PHI_ARG_DEF (phi, e->dest_idx);
 594 #ifdef ENABLE_CHECKING
 595             if (!phi_ssa_name_p (tmp))
 596               {
 597                 print_exprs_edge (stderr, e,
 598                                   "\nConstant argument in PHI. Can't insert :",
 599                                   var, " = ", tmp);
 600                 internal_error ("SSA corruption");
 601               }
 602 #else
 603             gcc_assert (phi_ssa_name_p (tmp));
 604 #endif
 605             y = var_to_partition (map, tmp);
 606             gcc_assert (x != NO_PARTITION);
 607             gcc_assert (y != NO_PARTITION);
 608 #ifdef ENABLE_CHECKING
 609             if (root_var_find (rv, x) != root_var_find (rv, y))
 610               {
 611                 print_exprs_edge (stderr, e, "\nDifferent root vars: ",
 612                                   root_var (rv, root_var_find (rv, x)),
 613                                   " and ",
 614                                   root_var (rv, root_var_find (rv, y)));
 615                 internal_error ("SSA corruption");
 616               }
 617 #else
 618             gcc_assert (root_var_find (rv, x) == root_var_find (rv, y));
 619 #endif
 620
 621             if (x != y)
 622               {
 623 #ifdef ENABLE_CHECKING
 624                 if (conflict_graph_conflict_p (graph, x, y))
 625                   {
 626                     print_exprs_edge (stderr, e, "\n Conflict ",
 627                                       partition_to_var (map, x),
 628                                       " and ", partition_to_var (map, y));
 629                     internal_error ("SSA corruption");
 630                   }
 631 #else
 632                 gcc_assert (!conflict_graph_conflict_p (graph, x, y));
 633 #endif
 634
 635                 /* Now map the partitions back to their real variables.  */
 636                 var = partition_to_var (map, x);
 637                 tmp = partition_to_var (map, y);
 638                 if (dump_file && (dump_flags & TDF_DETAILS))
 639                   {
 640                     print_exprs_edge (dump_file, e,
 641                                       "ABNORMAL: Coalescing ",
 642                                       var, " and ", tmp);
 643                   }
 644 #ifdef ENABLE_CHECKING
 645                 if (var_union (map, var, tmp) == NO_PARTITION)
 646                   {
 647                     print_exprs_edge (stderr, e, "\nUnable to coalesce",
 648                                       partition_to_var (map, x), " and ",
 649                                       partition_to_var (map, y));
 650                     internal_error ("SSA corruption");
 651                   }
 652 #else
 653                 gcc_assert (var_union (map, var, tmp) != NO_PARTITION);
 654 #endif
 655                 conflict_graph_merge_regs (graph, x, y);
 656               }
 657           }
 658 }
 659
 660
 661 /* Reduce the number of live ranges in MAP.  Live range information is
 662    returned if FLAGS indicates that we are combining temporaries, otherwise
 663    NULL is returned.  The only partitions which are associated with actual
 664    variables at this point are those which are forced to be coalesced for
 665    various reason. (live on entry, live across abnormal edges, etc.).  */
 666
 667 static tree_live_info_p
 668 coalesce_ssa_name (var_map map, int flags)
 669 {
 670   unsigned num, x, i;
 671   sbitmap live;
 672   tree var, phi;
 673   root_var_p rv;
 674   tree_live_info_p liveinfo;
 675   var_ann_t ann;
 676   conflict_graph graph;
 677   basic_block bb;
 678   coalesce_list_p cl = NULL;
 679
 680   if (num_var_partitions (map) <= 1)
 681     return NULL;
 682
 683   /* If no preference given, use cheap coalescing of all partitions.  */
 684   if ((flags & (SSANORM_COALESCE_PARTITIONS | SSANORM_USE_COALESCE_LIST)) == 0)
 685     flags |= SSANORM_COALESCE_PARTITIONS;
 686
 687   liveinfo = calculate_live_on_entry (map);
 688   calculate_live_on_exit (liveinfo);
 689   rv = root_var_init (map);
 690
 691   /* Remove single element variable from the list.  */
 692   root_var_compact (rv);
 693
 694   if (flags & SSANORM_USE_COALESCE_LIST)
 695     {
 696       cl = create_coalesce_list (map);
 697
 698       /* Add all potential copies via PHI arguments to the list.  */
 699       FOR_EACH_BB (bb)
 700         {
 701           for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
 702             {
 703               tree res = PHI_RESULT (phi);
 704               int p = var_to_partition (map, res);
 705               if (p == NO_PARTITION)
 706                 continue;
 707               for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
 708                 {
 709                   tree arg = PHI_ARG_DEF (phi, x);
 710                   int p2;
 711
 712                   if (TREE_CODE (arg) != SSA_NAME)
 713                     continue;
 714                   if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg))
 715                     continue;
 716                   p2 = var_to_partition (map, PHI_ARG_DEF (phi, x));
 717                   if (p2 != NO_PARTITION)
 718                     add_coalesce (cl, p, p2, 1);
 719                 }
 720             }
 721         }
 722
 723       /* Coalesce all the result decls together.  */
 724       var = NULL_TREE;
 725       i = 0;
 726       for (x = 0; x < num_var_partitions (map); x++)
 727         {
 728           tree p = partition_to_var (map, x);
 729           if (TREE_CODE (SSA_NAME_VAR(p)) == RESULT_DECL)
 730             {
 731               if (var == NULL_TREE)
 732                 {
 733                   var = p;
 734                   i = x;
 735                 }
 736               else
 737                 add_coalesce (cl, i, x, 1);
 738             }
 739         }
 740     }
 741
 742   /* Build a conflict graph.  */
 743   graph = build_tree_conflict_graph (liveinfo, rv, cl);
 744
 745   if (cl)
 746     {
 747       if (dump_file && (dump_flags & TDF_DETAILS))
 748         {
 749           fprintf (dump_file, "Before sorting:\n");
 750           dump_coalesce_list (dump_file, cl);
 751         }
 752
 753       sort_coalesce_list (cl);
 754
 755       if (dump_file && (dump_flags & TDF_DETAILS))
 756         {
 757           fprintf (dump_file, "\nAfter sorting:\n");
 758           dump_coalesce_list (dump_file, cl);
 759         }
 760     }
 761
 762   /* Put the single element variables back in.  */
 763   root_var_decompact (rv);
 764
 765   /* First, coalesce all live on entry variables to their root variable.
 766      This will ensure the first use is coming from the correct location.  */
 767
 768   live = sbitmap_alloc (num_var_partitions (map));
 769   sbitmap_zero (live);
 770
 771   /* Set 'live' vector to indicate live on entry partitions.  */
 772   num = num_var_partitions (map);
 773   for (x = 0 ; x < num; x++)
 774     {
 775       var = partition_to_var (map, x);
 776       if (default_def (SSA_NAME_VAR (var)) == var)
 777         SET_BIT (live, x);
 778     }
 779
 780   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
 781     {
 782       delete_tree_live_info (liveinfo);
 783       liveinfo = NULL;
 784     }
 785
 786   /* Assign root variable as partition representative for each live on entry
 787      partition.  */
 788   EXECUTE_IF_SET_IN_SBITMAP (live, 0, x,
 789     {
 790       var = root_var (rv, root_var_find (rv, x));
 791       ann = var_ann (var);
 792       /* If these aren't already coalesced...  */
 793       if (partition_to_var (map, x) != var)
 794         {
 795           /* This root variable should have not already been assigned
 796              to another partition which is not coalesced with this one.  */
 797           gcc_assert (!ann->out_of_ssa_tag);
 798
 799           if (dump_file && (dump_flags & TDF_DETAILS))
 800             {
 801               print_exprs (dump_file, "Must coalesce ",
 802                            partition_to_var (map, x),
 803                            " with the root variable ", var, ".\n");
 804             }
 805
 806           change_partition_var (map, var, x);
 807         }
 808     });
 809
 810   sbitmap_free (live);
 811
 812   /* Coalesce partitions live across abnormal edges.  */
 813   coalesce_abnormal_edges (map, graph, rv);
 814
 815   if (dump_file && (dump_flags & TDF_DETAILS))
 816     dump_var_map (dump_file, map);
 817
 818   /* Coalesce partitions.  */
 819   if (flags & SSANORM_USE_COALESCE_LIST)
 820     coalesce_tpa_members (rv, graph, map, cl,
 821                           ((dump_flags & TDF_DETAILS) ? dump_file
 822                                                            : NULL));
 823
 824
 825   if (flags & SSANORM_COALESCE_PARTITIONS)
 826     coalesce_tpa_members (rv, graph, map, NULL,
 827                           ((dump_flags & TDF_DETAILS) ? dump_file
 828                                                            : NULL));
 829   if (cl)
 830     delete_coalesce_list (cl);
 831   root_var_delete (rv);
 832   conflict_graph_delete (graph);
 833
 834   return liveinfo;
 835 }
 836
 837
 838 /* Take the ssa-name var_map MAP, and assign real variables to each
 839    partition.  */
 840
 841 static void
 842 assign_vars (var_map map)
 843 {
 844   int x, i, num, rep;
 845   tree t, var;
 846   var_ann_t ann;
 847   root_var_p rv;
 848
 849   rv = root_var_init (map);
 850   if (!rv)
 851     return;
 852
 853   /* Coalescing may already have forced some partitions to their root
 854      variable. Find these and tag them.  */
 855
 856   num = num_var_partitions (map);
 857   for (x = 0; x < num; x++)
 858     {
 859       var = partition_to_var (map, x);
 860       if (TREE_CODE (var) != SSA_NAME)
 861         {
 862           /* Coalescing will already have verified that more than one
 863              partition doesn't have the same root variable. Simply marked
 864              the variable as assigned.  */
 865           ann = var_ann (var);
 866           ann->out_of_ssa_tag = 1;
 867           if (dump_file && (dump_flags & TDF_DETAILS))
 868             {
 869               fprintf (dump_file, "partition %d has variable ", x);
 870               print_generic_expr (dump_file, var, TDF_SLIM);
 871               fprintf (dump_file, " assigned to it.\n");
 872             }
 873
 874         }
 875     }
 876
 877   num = root_var_num (rv);
 878   for (x = 0; x < num; x++)
 879     {
 880       var = root_var (rv, x);
 881       ann = var_ann (var);
 882       for (i = root_var_first_partition (rv, x);
 883            i != ROOT_VAR_NONE;
 884            i = root_var_next_partition (rv, i))
 885         {
 886           t = partition_to_var (map, i);
 887
 888           if (t == var || TREE_CODE (t) != SSA_NAME)
 889             continue;
 890
 891           rep = var_to_partition (map, t);
 892
 893           if (!ann->out_of_ssa_tag)
 894             {
 895               if (dump_file && (dump_flags & TDF_DETAILS))
 896                 print_exprs (dump_file, "", t, "  --> ", var, "\n");
 897               change_partition_var (map, var, rep);
 898               continue;
 899             }
 900
 901           if (dump_file && (dump_flags & TDF_DETAILS))
 902             print_exprs (dump_file, "", t, " not coalesced with ", var,
 903                          "");
 904
 905           var = create_temp (t);
 906           change_partition_var (map, var, rep);
 907           ann = var_ann (var);
 908
 909           if (dump_file && (dump_flags & TDF_DETAILS))
 910             {
 911               fprintf (dump_file, " -->  New temp:  '");
 912               print_generic_expr (dump_file, var, TDF_SLIM);
 913               fprintf (dump_file, "'\n");
 914             }
 915         }
 916     }
 917
 918   root_var_delete (rv);
 919 }
 920
 921
 922 /* Replace use operand P with whatever variable it has been rewritten to based
 923    on the partitions in MAP.  EXPR is an optional expression vector over SSA
 924    versions which is used to replace P with an expression instead of a variable.
 925    If the stmt is changed, return true.  */
 926
 927 static inline bool
 928 replace_use_variable (var_map map, use_operand_p p, tree *expr)
 929 {
 930   tree new_var;
 931   tree var = USE_FROM_PTR (p);
 932
 933   /* Check if we are replacing this variable with an expression.  */
 934   if (expr)
 935     {
 936       int version = SSA_NAME_VERSION (var);
 937       if (expr[version])
 938         {
 939           tree new_expr = TREE_OPERAND (expr[version], 1);
 940           SET_USE (p, new_expr);
 941           /* Clear the stmt's RHS, or GC might bite us.  */
 942           TREE_OPERAND (expr[version], 1) = NULL_TREE;
 943           return true;
 944         }
 945     }
 946
 947   new_var = var_to_partition_to_var (map, var);
 948   if (new_var)
 949     {
 950       SET_USE (p, new_var);
 951       set_is_used (new_var);
 952       return true;
 953     }
 954   return false;
 955 }
 956
 957
 958 /* Replace def operand DEF_P with whatever variable it has been rewritten to
 959    based on the partitions in MAP.  EXPR is an optional expression vector over
 960    SSA versions which is used to replace DEF_P with an expression instead of a
 961    variable.  If the stmt is changed, return true.  */
 962
 963 static inline bool
 964 replace_def_variable (var_map map, def_operand_p def_p, tree *expr)
 965 {
 966   tree new_var;
 967   tree var = DEF_FROM_PTR (def_p);
 968
 969   /* Check if we are replacing this variable with an expression.  */
 970   if (expr)
 971     {
 972       int version = SSA_NAME_VERSION (var);
 973       if (expr[version])
 974         {
 975           tree new_expr = TREE_OPERAND (expr[version], 1);
 976           SET_DEF (def_p, new_expr);
 977           /* Clear the stmt's RHS, or GC might bite us.  */
 978           TREE_OPERAND (expr[version], 1) = NULL_TREE;
 979           return true;
 980         }
 981     }
 982
 983   new_var = var_to_partition_to_var (map, var);
 984   if (new_var)
 985     {
 986       SET_DEF (def_p, new_var);
 987       set_is_used (new_var);
 988       return true;
 989     }
 990   return false;
 991 }
 992
 993
 994 /* Remove any PHI node which is a virtual PHI.  */
 995
 996 static void
 997 eliminate_virtual_phis (void)
 998 {
 999   basic_block bb;
1000   tree phi, next;
1001
1002   FOR_EACH_BB (bb)
1003     {
1004       for (phi = phi_nodes (bb); phi; phi = next)
1005         {
1006           next = PHI_CHAIN (phi);
1007           if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi))))
1008             {
1009 #ifdef ENABLE_CHECKING
1010               int i;
1011               /* There should be no arguments of this PHI which are in
1012                  the partition list, or we get incorrect results.  */
1013               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1014                 {
1015                   tree arg = PHI_ARG_DEF (phi, i);
1016                   if (TREE_CODE (arg) == SSA_NAME
1017                       && is_gimple_reg (SSA_NAME_VAR (arg)))
1018                     {
1019                       fprintf (stderr, "Argument of PHI is not virtual (");
1020                       print_generic_expr (stderr, arg, TDF_SLIM);
1021                       fprintf (stderr, "), but the result is :");
1022                       print_generic_stmt (stderr, phi, TDF_SLIM);
1023                       internal_error ("SSA corruption");
1024                     }
1025                 }
1026 #endif
1027               remove_phi_node (phi, NULL_TREE, bb);
1028             }
1029         }
1030     }
1031 }
1032
1033
1034 /* This routine will coalesce variables in MAP of the same type which do not
1035    interfere with each other. LIVEINFO is the live range info for variables
1036    of interest.  This will both reduce the memory footprint of the stack, and
1037    allow us to coalesce together local copies of globals and scalarized
1038    component refs.  */
1039
1040 static void
1041 coalesce_vars (var_map map, tree_live_info_p liveinfo)
1042 {
1043   basic_block bb;
1044   type_var_p tv;
1045   tree var;
1046   unsigned x, p, p2;
1047   coalesce_list_p cl;
1048   conflict_graph graph;
1049
1050   cl = create_coalesce_list (map);
1051
1052   /* Merge all the live on entry vectors for coalesced partitions.  */
1053   for (x = 0; x < num_var_partitions (map); x++)
1054     {
1055       var = partition_to_var (map, x);
1056       p = var_to_partition (map, var);
1057       if (p != x)
1058         live_merge_and_clear (liveinfo, p, x);
1059     }
1060
1061   /* When PHI nodes are turned into copies, the result of each PHI node
1062      becomes live on entry to the block. Mark these now.  */
1063   FOR_EACH_BB (bb)
1064     {
1065       tree phi, arg;
1066       unsigned p;
1067
1068       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1069         {
1070           p = var_to_partition (map, PHI_RESULT (phi));
1071
1072           /* Skip virtual PHI nodes.  */
1073           if (p == (unsigned)NO_PARTITION)
1074             continue;
1075
1076           make_live_on_entry (liveinfo, bb, p);
1077
1078           /* Each argument is a potential copy operation. Add any arguments
1079              which are not coalesced to the result to the coalesce list.  */
1080           for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++)
1081             {
1082               arg = PHI_ARG_DEF (phi, x);
1083               if (!phi_ssa_name_p (arg))
1084                 continue;
1085               p2 = var_to_partition (map, arg);
1086               if (p2 == (unsigned)NO_PARTITION)
1087                 continue;
1088               if (p != p2)
1089                 add_coalesce (cl, p, p2, 1);
1090             }
1091         }
1092    }
1093
1094
1095   /* Re-calculate live on exit info.  */
1096   calculate_live_on_exit (liveinfo);
1097
1098   if (dump_file && (dump_flags & TDF_DETAILS))
1099     {
1100       fprintf (dump_file, "Live range info for variable memory coalescing.\n");
1101       dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL);
1102
1103       fprintf (dump_file, "Coalesce list from phi nodes:\n");
1104       dump_coalesce_list (dump_file, cl);
1105     }
1106
1107
1108   tv = type_var_init (map);
1109   if (dump_file)
1110     type_var_dump (dump_file, tv);
1111   type_var_compact (tv);
1112   if (dump_file)
1113     type_var_dump (dump_file, tv);
1114
1115   graph = build_tree_conflict_graph (liveinfo, tv, cl);
1116
1117   type_var_decompact (tv);
1118   if (dump_file && (dump_flags & TDF_DETAILS))
1119     {
1120       fprintf (dump_file, "type var list now looks like:n");
1121       type_var_dump (dump_file, tv);
1122
1123       fprintf (dump_file, "Coalesce list after conflict graph build:\n");
1124       dump_coalesce_list (dump_file, cl);
1125     }
1126
1127   sort_coalesce_list (cl);
1128   if (dump_file && (dump_flags & TDF_DETAILS))
1129     {
1130       fprintf (dump_file, "Coalesce list after sorting:\n");
1131       dump_coalesce_list (dump_file, cl);
1132     }
1133
1134   coalesce_tpa_members (tv, graph, map, cl,
1135                         ((dump_flags & TDF_DETAILS) ? dump_file : NULL));
1136
1137   type_var_delete (tv);
1138   delete_coalesce_list (cl);
1139 }
1140
1141
1142 /* Temporary Expression Replacement (TER)
1143
1144    Replace SSA version variables during out-of-ssa with their defining
1145    expression if there is only one use of the variable.
1146
1147    A pass is made through the function, one block at a time.  No cross block
1148    information is tracked.
1149
1150    Variables which only have one use, and whose defining stmt is considered
1151    a replaceable expression (see check_replaceable) are entered into
1152    consideration by adding a list of dependent partitions to the version_info
1153    vector for that ssa_name_version.  This information comes from the partition
1154    mapping for each USE.  At the same time, the partition_dep_list vector for
1155    these partitions have this version number entered into their lists.
1156
1157    When the use of a replaceable ssa_variable is encountered, the dependence
1158    list in version_info[] is moved to the "pending_dependence" list in case
1159    the current expression is also replaceable. (To be determined later in
1160    processing this stmt.) version_info[] for the version is then updated to
1161    point to the defining stmt and the 'replaceable' bit is set.
1162
1163    Any partition which is defined by a statement 'kills' any expression which
1164    is dependent on this partition.  Every ssa version in the partitions'
1165    dependence list is removed from future consideration.
1166
1167    All virtual references are lumped together.  Any expression which is
1168    dependent on any virtual variable (via a VUSE) has a dependence added
1169    to the special partition defined by VIRTUAL_PARTITION.
1170
1171    Whenever a V_MAY_DEF is seen, all expressions dependent this
1172    VIRTUAL_PARTITION are removed from consideration.
1173
1174    At the end of a basic block, all expression are removed from consideration
1175    in preparation for the next block.
1176
1177    The end result is a vector over SSA_NAME_VERSION which is passed back to
1178    rewrite_out_of_ssa.  As the SSA variables are being rewritten, instead of
1179    replacing the SSA_NAME tree element with the partition it was assigned,
1180    it is replaced with the RHS of the defining expression.  */
1181
1182
1183 /* Dependency list element.  This can contain either a partition index or a
1184    version number, depending on which list it is in.  */
1185
1186 typedef struct value_expr_d
1187 {
1188   int value;
1189   struct value_expr_d *next;
1190 } *value_expr_p;
1191
1192
1193 /* Temporary Expression Replacement (TER) table information.  */
1194
1195 typedef struct temp_expr_table_d
1196 {
1197   var_map map;
1198   void **version_info;
1199   value_expr_p *partition_dep_list;
1200   bitmap replaceable;
1201   bool saw_replaceable;
1202   int virtual_partition;
1203   bitmap partition_in_use;
1204   value_expr_p free_list;
1205   value_expr_p pending_dependence;
1206 } *temp_expr_table_p;
1207
1208 /* Used to indicate a dependency on V_MAY_DEFs.  */
1209 #define VIRTUAL_PARTITION(table)        (table->virtual_partition)
1210
1211 static temp_expr_table_p new_temp_expr_table (var_map);
1212 static tree *free_temp_expr_table (temp_expr_table_p);
1213 static inline value_expr_p new_value_expr (temp_expr_table_p);
1214 static inline void free_value_expr (temp_expr_table_p, value_expr_p);
1215 static inline value_expr_p find_value_in_list (value_expr_p, int,
1216                                                value_expr_p *);
1217 static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int);
1218 static inline void add_info_to_list (temp_expr_table_p, value_expr_p *,
1219                                      value_expr_p);
1220 static value_expr_p remove_value_from_list (value_expr_p *, int);
1221 static void add_dependance (temp_expr_table_p, int, tree);
1222 static bool check_replaceable (temp_expr_table_p, tree);
1223 static void finish_expr (temp_expr_table_p, int, bool);
1224 static void mark_replaceable (temp_expr_table_p, tree);
1225 static inline void kill_expr (temp_expr_table_p, int, bool);
1226 static inline void kill_virtual_exprs (temp_expr_table_p, bool);
1227 static void find_replaceable_in_bb (temp_expr_table_p, basic_block);
1228 static tree *find_replaceable_exprs (var_map);
1229 static void dump_replaceable_exprs (FILE *, tree *);
1230
1231
1232 /* Create a new TER table for MAP.  */
1233
1234 static temp_expr_table_p
1235 new_temp_expr_table (var_map map)
1236 {
1237   temp_expr_table_p t;
1238
1239   t = (temp_expr_table_p) xmalloc (sizeof (struct temp_expr_table_d));
1240   t->map = map;
1241
1242   t->version_info = xcalloc (num_ssa_names + 1, sizeof (void *));
1243   t->partition_dep_list = xcalloc (num_var_partitions (map) + 1,
1244                                    sizeof (value_expr_p));
1245
1246   t->replaceable = BITMAP_XMALLOC ();
1247   t->partition_in_use = BITMAP_XMALLOC ();
1248
1249   t->saw_replaceable = false;
1250   t->virtual_partition = num_var_partitions (map);
1251   t->free_list = NULL;
1252   t->pending_dependence = NULL;
1253
1254   return t;
1255 }
1256
1257
1258 /* Free TER table T.  If there are valid replacements, return the expression
1259    vector.  */
1260
1261 static tree *
1262 free_temp_expr_table (temp_expr_table_p t)
1263 {
1264   value_expr_p p;
1265   tree *ret = NULL;
1266
1267 #ifdef ENABLE_CHECKING
1268   unsigned x;
1269   for (x = 0; x <= num_var_partitions (t->map); x++)
1270     gcc_assert (!t->partition_dep_list[x]);
1271 #endif
1272
1273   while ((p = t->free_list))
1274     {
1275       t->free_list = p->next;
1276       free (p);
1277     }
1278
1279   BITMAP_XFREE (t->partition_in_use);
1280   BITMAP_XFREE (t->replaceable);
1281
1282   free (t->partition_dep_list);
1283   if (t->saw_replaceable)
1284     ret = (tree *)t->version_info;
1285   else
1286     free (t->version_info);
1287
1288   free (t);
1289   return ret;
1290 }
1291
1292
1293 /* Allocate a new value list node. Take it from the free list in TABLE if
1294    possible.  */
1295
1296 static inline value_expr_p
1297 new_value_expr (temp_expr_table_p table)
1298 {
1299   value_expr_p p;
1300   if (table->free_list)
1301     {
1302       p = table->free_list;
1303       table->free_list = p->next;
1304     }
1305   else
1306     p = (value_expr_p) xmalloc (sizeof (struct value_expr_d));
1307
1308   return p;
1309 }
1310
1311
1312 /* Add value list node P to the free list in TABLE.  */
1313
1314 static inline void
1315 free_value_expr (temp_expr_table_p table, value_expr_p p)
1316 {
1317   p->next = table->free_list;
1318   table->free_list = p;
1319 }
1320
1321
1322 /* Find VALUE if it's in LIST.  Return a pointer to the list object if found,
1323    else return NULL.  If LAST_PTR is provided, it will point to the previous
1324    item upon return, or NULL if this is the first item in the list.  */
1325
1326 static inline value_expr_p
1327 find_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr)
1328 {
1329   value_expr_p curr;
1330   value_expr_p last = NULL;
1331
1332   for (curr = list; curr; last = curr, curr = curr->next)
1333     {
1334       if (curr->value == value)
1335         break;
1336     }
1337   if (last_ptr)
1338     *last_ptr = last;
1339   return curr;
1340 }
1341
1342
1343 /* Add VALUE to LIST, if it isn't already present.  TAB is the expression
1344    table */
1345
1346 static inline void
1347 add_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value)
1348 {
1349   value_expr_p info;
1350
1351   if (!find_value_in_list (*list, value, NULL))
1352     {
1353       info = new_value_expr (tab);
1354       info->value = value;
1355       info->next = *list;
1356       *list = info;
1357     }
1358 }
1359
1360
1361 /* Add value node INFO if it's value isn't already in LIST.  Free INFO if
1362    it is already in the list. TAB is the expression table.  */
1363
1364 static inline void
1365 add_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info)
1366 {
1367   if (find_value_in_list (*list, info->value, NULL))
1368     free_value_expr (tab, info);
1369   else
1370     {
1371       info->next = *list;
1372       *list = info;
1373     }
1374 }
1375
1376
1377 /* Look for VALUE in LIST.  If found, remove it from the list and return it's
1378    pointer.  */
1379
1380 static value_expr_p
1381 remove_value_from_list (value_expr_p *list, int value)
1382 {
1383   value_expr_p info, last;
1384
1385   info = find_value_in_list (*list, value, &last);
1386   if (!info)
1387     return NULL;
1388   if (!last)
1389     *list = info->next;
1390   else
1391     last->next = info->next;
1392
1393   return info;
1394 }
1395
1396
1397 /* Add a dependency between the def of ssa VERSION and VAR.  If VAR is
1398    replaceable by an expression, add a dependence each of the elements of the
1399    expression.  These are contained in the pending list.  TAB is the
1400    expression table.  */
1401
1402 static void
1403 add_dependance (temp_expr_table_p tab, int version, tree var)
1404 {
1405   int i, x;
1406   value_expr_p info;
1407
1408   i = SSA_NAME_VERSION (var);
1409   if (bitmap_bit_p (tab->replaceable, i))
1410     {
1411       /* This variable is being substituted, so use whatever dependences
1412          were queued up when we marked this as replaceable earlier.  */
1413       while ((info = tab->pending_dependence))
1414         {
1415           tab->pending_dependence = info->next;
1416           /* Get the partition this variable was dependent on. Reuse this
1417              object to represent the current  expression instead.  */
1418           x = info->value;
1419           info->value = version;
1420           add_info_to_list (tab, &(tab->partition_dep_list[x]), info);
1421           add_value_to_list (tab,
1422                              (value_expr_p *)&(tab->version_info[version]), x);
1423           bitmap_set_bit (tab->partition_in_use, x);
1424         }
1425     }
1426   else
1427     {
1428       i = var_to_partition (tab->map, var);
1429       gcc_assert (i != NO_PARTITION);
1430       add_value_to_list (tab, &(tab->partition_dep_list[i]), version);
1431       add_value_to_list (tab,
1432                          (value_expr_p *)&(tab->version_info[version]), i);
1433       bitmap_set_bit (tab->partition_in_use, i);
1434     }
1435 }
1436
1437
1438 /* Check if expression STMT is suitable for replacement in table TAB.  If so,
1439    create an expression entry.  Return true if this stmt is replaceable.  */
1440
1441 static bool
1442 check_replaceable (temp_expr_table_p tab, tree stmt)
1443 {
1444   stmt_ann_t ann;
1445   vuse_optype vuseops;
1446   def_optype defs;
1447   use_optype uses;
1448   tree var, def;
1449   int num_use_ops, version;
1450   var_map map = tab->map;
1451   ssa_op_iter iter;
1452
1453   if (TREE_CODE (stmt) != MODIFY_EXPR)
1454     return false;
1455
1456   ann = stmt_ann (stmt);
1457   defs = DEF_OPS (ann);
1458
1459   /* Punt if there is more than 1 def, or more than 1 use.  */
1460   if (NUM_DEFS (defs) != 1)
1461     return false;
1462   def = DEF_OP (defs, 0);
1463   if (version_ref_count (map, def) != 1)
1464     return false;
1465
1466   /* There must be no V_MAY_DEFS.  */
1467   if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
1468     return false;
1469
1470   /* There must be no V_MUST_DEFS.  */
1471   if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
1472     return false;
1473
1474   /* Float expressions must go through memory if float-store is on.  */
1475   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1476     return false;
1477
1478   uses = USE_OPS (ann);
1479   num_use_ops = NUM_USES (uses);
1480   vuseops = VUSE_OPS (ann);
1481
1482   /* Any expression which has no virtual operands and no real operands
1483      should have been propagated if it's possible to do anything with them.
1484      If this happens here, it probably exists that way for a reason, so we
1485      won't touch it.   An example is:
1486          b_4 = &tab
1487      There are no virtual uses nor any real uses, so we just leave this
1488      alone to be safe.  */
1489
1490   if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
1491     return false;
1492
1493   version = SSA_NAME_VERSION (def);
1494
1495   /* Add this expression to the dependency list for each use partition.  */
1496   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1497     {
1498       add_dependance (tab, version, var);
1499     }
1500
1501   /* If there are VUSES, add a dependence on virtual defs.  */
1502   if (NUM_VUSES (vuseops) != 0)
1503     {
1504       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1505                          VIRTUAL_PARTITION (tab));
1506       add_value_to_list (tab,
1507                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1508                          version);
1509       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1510     }
1511
1512   return true;
1513 }
1514
1515
1516 /* This function will remove the expression for VERSION from replacement
1517    consideration.n table TAB  If 'replace' is true, it is marked as
1518    replaceable, otherwise not.  */
1519
1520 static void
1521 finish_expr (temp_expr_table_p tab, int version, bool replace)
1522 {
1523   value_expr_p info, tmp;
1524   int partition;
1525
1526   /* Remove this expression from its dependent lists.  The partition dependence
1527      list is retained and transfered later to whomever uses this version.  */
1528   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1529     {
1530       partition = info->value;
1531       gcc_assert (tab->partition_dep_list[partition]);
1532       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1533                                     version);
1534       gcc_assert (tmp);
1535       free_value_expr (tab, tmp);
1536       /* Only clear the bit when the dependency list is emptied via
1537          a replacement. Otherwise kill_expr will take care of it.  */
1538       if (!(tab->partition_dep_list[partition]) && replace)
1539         bitmap_clear_bit (tab->partition_in_use, partition);
1540       tmp = info->next;
1541       if (!replace)
1542         free_value_expr (tab, info);
1543     }
1544
1545   if (replace)
1546     {
1547       tab->saw_replaceable = true;
1548       bitmap_set_bit (tab->replaceable, version);
1549     }
1550   else
1551     {
1552       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1553       tab->version_info[version] = NULL;
1554     }
1555 }
1556
1557
1558 /* Mark the expression associated with VAR as replaceable, and enter
1559    the defining stmt into the version_info table TAB.  */
1560
1561 static void
1562 mark_replaceable (temp_expr_table_p tab, tree var)
1563 {
1564   value_expr_p info;
1565   int version = SSA_NAME_VERSION (var);
1566   finish_expr (tab, version, true);
1567
1568   /* Move the dependence list to the pending list.  */
1569   if (tab->version_info[version])
1570     {
1571       info = (value_expr_p) tab->version_info[version];
1572       for ( ; info->next; info = info->next)
1573         continue;
1574       info->next = tab->pending_dependence;
1575       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1576     }
1577
1578   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1579 }
1580
1581
1582 /* This function marks any expression in TAB which is dependent on PARTITION
1583    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1584    should have its bit cleared.  Since this routine can be called within an
1585    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1586
1587 static inline void
1588 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1589 {
1590   value_expr_p ptr;
1591
1592   /* Mark every active expr dependent on this var as not replaceable.  */
1593   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1594     finish_expr (tab, ptr->value, false);
1595
1596   if (clear_bit)
1597     bitmap_clear_bit (tab->partition_in_use, partition);
1598 }
1599
1600
1601 /* This function kills all expressions in TAB which are dependent on virtual
1602    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1603
1604 static inline void
1605 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1606 {
1607   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1608 }
1609
1610
1611 /* This function processes basic block BB, and looks for variables which can
1612    be replaced by their expressions.  Results are stored in TAB.  */
1613
1614 static void
1615 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1616 {
1617   block_stmt_iterator bsi;
1618   tree stmt, def;
1619   stmt_ann_t ann;
1620   int partition;
1621   var_map map = tab->map;
1622   value_expr_p p;
1623   ssa_op_iter iter;
1624
1625   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1626     {
1627       stmt = bsi_stmt (bsi);
1628       ann = stmt_ann (stmt);
1629
1630       /* Determine if this stmt finishes an existing expression.  */
1631       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1632         {
1633           if (tab->version_info[SSA_NAME_VERSION (def)])
1634             {
1635               /* Mark expression as replaceable unless stmt is volatile.  */
1636               if (!ann->has_volatile_ops)
1637                 mark_replaceable (tab, def);
1638               else
1639                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1640             }
1641         }
1642
1643       /* Next, see if this stmt kills off an active expression.  */
1644       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1645         {
1646           partition = var_to_partition (map, def);
1647           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1648             kill_expr (tab, partition, true);
1649         }
1650
1651       /* Now see if we are creating a new expression or not.  */
1652       if (!ann->has_volatile_ops)
1653         check_replaceable (tab, stmt);
1654
1655       /* Free any unused dependency lists.  */
1656       while ((p = tab->pending_dependence))
1657         {
1658           tab->pending_dependence = p->next;
1659           free_value_expr (tab, p);
1660         }
1661
1662       /* A V_MAY_DEF kills any expression using a virtual operand.  */
1663       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
1664         kill_virtual_exprs (tab, true);
1665
1666       /* A V_MUST_DEF kills any expression using a virtual operand.  */
1667       if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
1668         kill_virtual_exprs (tab, true);
1669     }
1670 }
1671
1672
1673 /* This function is the driver routine for replacement of temporary expressions
1674    in the SSA->normal phase, operating on MAP.  If there are replaceable
1675    expressions, a table is returned which maps SSA versions to the
1676    expressions they should be replaced with.  A NULL_TREE indicates no
1677    replacement should take place.  If there are no replacements at all,
1678    NULL is returned by the function, otherwise an expression vector indexed
1679    by SSA_NAME version numbers.  */
1680
1681 static tree *
1682 find_replaceable_exprs (var_map map)
1683 {
1684   basic_block bb;
1685   unsigned i;
1686   temp_expr_table_p table;
1687   tree *ret;
1688
1689   table = new_temp_expr_table (map);
1690   FOR_EACH_BB (bb)
1691     {
1692       bitmap_iterator bi;
1693
1694       find_replaceable_in_bb (table, bb);
1695       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1696         {
1697           kill_expr (table, i, false);
1698         }
1699     }
1700
1701   ret = free_temp_expr_table (table);
1702   return ret;
1703 }
1704
1705
1706 /* Dump TER expression table EXPR to file F.  */
1707
1708 static void
1709 dump_replaceable_exprs (FILE *f, tree *expr)
1710 {
1711   tree stmt, var;
1712   int x;
1713   fprintf (f, "\nReplacing Expressions\n");
1714   for (x = 0; x < (int)num_ssa_names + 1; x++)
1715     if (expr[x])
1716       {
1717         stmt = expr[x];
1718         var = DEF_OP (STMT_DEF_OPS (stmt), 0);
1719         print_generic_expr (f, var, TDF_SLIM);
1720         fprintf (f, " replace with --> ");
1721         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1722         fprintf (f, "\n");
1723       }
1724   fprintf (f, "\n");
1725 }
1726
1727
1728 /* Helper function for discover_nonconstant_array_refs.
1729    Look for ARRAY_REF nodes with non-constant indexes and mark them
1730    addressable.  */
1731
1732 static tree
1733 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1734                                    void *data ATTRIBUTE_UNUSED)
1735 {
1736   tree t = *tp;
1737
1738   if (IS_TYPE_OR_DECL_P (t))
1739     *walk_subtrees = 0;
1740   else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1741     {
1742       while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1743               && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1744               && (!TREE_OPERAND (t, 2)
1745                   || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1746              || (TREE_CODE (t) == COMPONENT_REF
1747                  && (!TREE_OPERAND (t,2)
1748                      || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1749              || TREE_CODE (t) == BIT_FIELD_REF
1750              || TREE_CODE (t) == REALPART_EXPR
1751              || TREE_CODE (t) == IMAGPART_EXPR
1752              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1753              || TREE_CODE (t) == NOP_EXPR
1754              || TREE_CODE (t) == CONVERT_EXPR)
1755         t = TREE_OPERAND (t, 0);
1756
1757       if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1758         {
1759           t = get_base_address (t);
1760           if (t && DECL_P (t))
1761             TREE_ADDRESSABLE (t) = 1;
1762         }
1763
1764       *walk_subtrees = 0;
1765     }
1766
1767   return NULL_TREE;
1768 }
1769
1770
1771 /* RTL expansion is not able to compile array references with variable
1772    offsets for arrays stored in single register.  Discover such
1773    expressions and mark variables as addressable to avoid this
1774    scenario.  */
1775
1776 static void
1777 discover_nonconstant_array_refs (void)
1778 {
1779   basic_block bb;
1780   block_stmt_iterator bsi;
1781
1782   FOR_EACH_BB (bb)
1783     {
1784       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1785         walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1786                    NULL , NULL);
1787     }
1788 }
1789
1790
1791 /* This function will rewrite the current program using the variable mapping
1792    found in MAP.  If the replacement vector VALUES is provided, any
1793    occurrences of partitions with non-null entries in the vector will be
1794    replaced with the expression in the vector instead of its mapped
1795    variable.  */
1796
1797 static void
1798 rewrite_trees (var_map map, tree *values)
1799 {
1800   elim_graph g;
1801   basic_block bb;
1802   block_stmt_iterator si;
1803   edge e;
1804   tree phi;
1805   bool changed;
1806
1807 #ifdef ENABLE_CHECKING
1808   /* Search for PHIs where the destination has no partition, but one
1809      or more arguments has a partition.  This should not happen and can
1810      create incorrect code.  */
1811   FOR_EACH_BB (bb)
1812     {
1813       tree phi;
1814
1815       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1816         {
1817           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1818
1819           if (T0 == NULL_TREE)
1820             {
1821               int i;
1822
1823               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1824                 {
1825                   tree arg = PHI_ARG_DEF (phi, i);
1826
1827                   if (TREE_CODE (arg) == SSA_NAME
1828                       && var_to_partition (map, arg) != NO_PARTITION)
1829                     {
1830                       fprintf (stderr, "Argument of PHI is in a partition :(");
1831                       print_generic_expr (stderr, arg, TDF_SLIM);
1832                       fprintf (stderr, "), but the result is not :");
1833                       print_generic_stmt (stderr, phi, TDF_SLIM);
1834                       internal_error ("SSA corruption");
1835                     }
1836                 }
1837             }
1838         }
1839     }
1840 #endif
1841
1842   /* Replace PHI nodes with any required copies.  */
1843   g = new_elim_graph (map->num_partitions);
1844   g->map = map;
1845   FOR_EACH_BB (bb)
1846     {
1847       for (si = bsi_start (bb); !bsi_end_p (si); )
1848         {
1849           size_t num_uses, num_defs;
1850           use_optype uses;
1851           def_optype defs;
1852           tree stmt = bsi_stmt (si);
1853           use_operand_p use_p;
1854           def_operand_p def_p;
1855           int remove = 0, is_copy = 0;
1856           stmt_ann_t ann;
1857           ssa_op_iter iter;
1858
1859           get_stmt_operands (stmt);
1860           ann = stmt_ann (stmt);
1861           changed = false;
1862
1863           if (TREE_CODE (stmt) == MODIFY_EXPR
1864               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1865             is_copy = 1;
1866
1867           uses = USE_OPS (ann);
1868           num_uses = NUM_USES (uses);
1869           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1870             {
1871               if (replace_use_variable (map, use_p, values))
1872                 changed = true;
1873             }
1874
1875           defs = DEF_OPS (ann);
1876           num_defs = NUM_DEFS (defs);
1877
1878           /* Mark this stmt for removal if it is the list of replaceable
1879              expressions.  */
1880           if (values && num_defs == 1)
1881             {
1882               tree def = DEF_OP (defs, 0);
1883               tree val;
1884               val = values[SSA_NAME_VERSION (def)];
1885               if (val)
1886                 remove = 1;
1887             }
1888           if (!remove)
1889             {
1890               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1891                 {
1892                   if (replace_def_variable (map, def_p, NULL))
1893                     changed = true;
1894
1895                   /* If both SSA_NAMEs coalesce to the same variable,
1896                      mark the now redundant copy for removal.  */
1897                   if (is_copy
1898                       && num_uses == 1
1899                       && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
1900                     remove = 1;
1901                 }
1902               if (changed & !remove)
1903                 modify_stmt (stmt);
1904             }
1905
1906           /* Remove any stmts marked for removal.  */
1907           if (remove)
1908             bsi_remove (&si);
1909           else
1910             bsi_next (&si);
1911         }
1912
1913       phi = phi_nodes (bb);
1914       if (phi)
1915         {
1916           edge_iterator ei;
1917           FOR_EACH_EDGE (e, ei, bb->preds)
1918             eliminate_phi (e, g);
1919         }
1920     }
1921
1922   delete_elim_graph (g);
1923 }
1924
1925
1926 /* These are the local work structures used to determine the best place to
1927    insert the copies that were placed on edges by the SSA->normal pass..  */
1928 static varray_type edge_leader = NULL;
1929 static varray_type GTY(()) stmt_list = NULL;
1930 static bitmap leader_has_match = NULL;
1931 static edge leader_match = NULL;
1932
1933
1934 /* Pass this function to make_forwarder_block so that all the edges with
1935    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1936 static bool
1937 same_stmt_list_p (edge e)
1938 {
1939   return (e->aux == (PTR) leader_match) ? true : false;
1940 }
1941
1942
1943 /* Return TRUE if S1 and S2 are equivalent copies.  */
1944 static inline bool
1945 identical_copies_p (tree s1, tree s2)
1946 {
1947 #ifdef ENABLE_CHECKING
1948   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1949   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1950   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1951   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1952 #endif
1953
1954   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1955     return false;
1956
1957   s1 = TREE_OPERAND (s1, 1);
1958   s2 = TREE_OPERAND (s2, 1);
1959
1960   if (s1 != s2)
1961     return false;
1962
1963   return true;
1964 }
1965
1966
1967 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1968    contain the same sequence of copies.  */
1969
1970 static inline bool
1971 identical_stmt_lists_p (edge e1, edge e2)
1972 {
1973   tree t1 = PENDING_STMT (e1);
1974   tree t2 = PENDING_STMT (e2);
1975   tree_stmt_iterator tsi1, tsi2;
1976
1977   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
1978   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
1979
1980   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
1981        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
1982        tsi_next (&tsi1), tsi_next (&tsi2))
1983     {
1984       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
1985         break;
1986     }
1987
1988   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
1989     return false;
1990
1991   return true;
1992 }
1993
1994
1995 /* Look at all the incoming edges to block BB, and decide where the best place
1996    to insert the stmts on each edge are, and perform those insertions.   Output
1997    any debug information to DEBUG_FILE.  Return true if anything other than a
1998    standard edge insertion is done.  */
1999
2000 static bool
2001 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2002 {
2003   edge e;
2004   edge_iterator ei;
2005   int count;
2006   unsigned int x;
2007   bool have_opportunity;
2008   block_stmt_iterator bsi;
2009   tree stmt;
2010   edge single_edge = NULL;
2011   bool is_label;
2012
2013   count = 0;
2014
2015   /* Blocks which contain at least one abnormal edge cannot use
2016      make_forwarder_block.  Look for these blocks, and commit any PENDING_STMTs
2017      found on edges in these block.  */
2018   have_opportunity = true;
2019   FOR_EACH_EDGE (e, ei, bb->preds)
2020     if (e->flags & EDGE_ABNORMAL)
2021       {
2022         have_opportunity = false;
2023         break;
2024       }
2025
2026   if (!have_opportunity)
2027     {
2028       FOR_EACH_EDGE (e, ei, bb->preds)
2029         if (PENDING_STMT (e))
2030           bsi_commit_one_edge_insert (e, NULL);
2031       return false;
2032     }
2033   /* Find out how many edges there are with interesting pending stmts on them.
2034      Commit the stmts on edges we are not interested in.  */
2035   FOR_EACH_EDGE (e, ei, bb->preds)
2036     {
2037       if (PENDING_STMT (e))
2038         {
2039           gcc_assert (!(e->flags & EDGE_ABNORMAL));
2040           if (e->flags & EDGE_FALLTHRU)
2041             {
2042               bsi = bsi_start (e->src);
2043               if (!bsi_end_p (bsi))
2044                 {
2045                   stmt = bsi_stmt (bsi);
2046                   bsi_next (&bsi);
2047                   gcc_assert (stmt != NULL_TREE);
2048                   is_label = (TREE_CODE (stmt) == LABEL_EXPR);
2049                   /* Punt if it has non-label stmts, or isn't local.  */
2050                   if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0))
2051                       || !bsi_end_p (bsi))
2052                     {
2053                       bsi_commit_one_edge_insert (e, NULL);
2054                       continue;
2055                     }
2056                 }
2057             }
2058           single_edge = e;
2059           count++;
2060         }
2061     }
2062
2063   /* If there aren't at least 2 edges, no sharing will happen.  */
2064   if (count < 2)
2065     {
2066       if (single_edge)
2067         bsi_commit_one_edge_insert (single_edge, NULL);
2068       return false;
2069     }
2070
2071   /* Ensure that we have empty worklists.  */
2072   if (edge_leader == NULL)
2073     {
2074       VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
2075       VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
2076       leader_has_match = BITMAP_XMALLOC ();
2077     }
2078   else
2079     {
2080 #ifdef ENABLE_CHECKING
2081       gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
2082       gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
2083       gcc_assert (bitmap_empty_p (leader_has_match));
2084 #endif
2085     }
2086
2087   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2088      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2089      block.  The leader edge destination is the block which all the other edges
2090      with the same stmt list will be redirected to.  */
2091   have_opportunity = false;
2092   FOR_EACH_EDGE (e, ei, bb->preds)
2093     {
2094       if (PENDING_STMT (e))
2095         {
2096           bool found = false;
2097
2098           /* Look for the same stmt list in edge leaders list.  */
2099           for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2100             {
2101               edge leader = VARRAY_EDGE (edge_leader, x);
2102               if (identical_stmt_lists_p (leader, e))
2103                 {
2104                   /* Give this edge the same stmt list pointer.  */
2105                   PENDING_STMT (e) = NULL;
2106                   e->aux = leader;
2107                   bitmap_set_bit (leader_has_match, x);
2108                   have_opportunity = found = true;
2109                   break;
2110                 }
2111             }
2112
2113           /* If no similar stmt list, add this edge to the leader list.  */
2114           if (!found)
2115             {
2116               VARRAY_PUSH_EDGE (edge_leader, e);
2117               VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
2118             }
2119         }
2120      }
2121
2122   /* If there are no similar lists, just issue the stmts.  */
2123   if (!have_opportunity)
2124     {
2125       for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2126         bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
2127       VARRAY_POP_ALL (edge_leader);
2128       VARRAY_POP_ALL (stmt_list);
2129       bitmap_clear (leader_has_match);
2130       return false;
2131     }
2132
2133
2134   if (debug_file)
2135     fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2136              bb->index);
2137
2138
2139   /* For each common list, create a forwarding block and issue the stmt's
2140      in that block.  */
2141   for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2142     if (bitmap_bit_p (leader_has_match, x))
2143       {
2144         edge new_edge, leader_edge;
2145         block_stmt_iterator bsi;
2146         tree curr_stmt_list;
2147
2148         leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
2149
2150         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2151            for various PHI manipulations, so it gets cleared whhen calls are
2152            made to make_forwarder_block(). So make sure the edge is clear,
2153            and use the saved stmt list.  */
2154         PENDING_STMT (leader_edge) = NULL;
2155         leader_edge->aux = leader_edge;
2156         curr_stmt_list = VARRAY_TREE (stmt_list, x);
2157
2158         new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p,
2159                                          NULL);
2160         bb = new_edge->dest;
2161         if (debug_file)
2162           {
2163             fprintf (debug_file, "Splitting BB %d for Common stmt list.  ",
2164                      leader_edge->dest->index);
2165             fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2166             print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2167           }
2168
2169         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2170           {
2171             e->aux = NULL;
2172             if (debug_file)
2173               fprintf (debug_file, "  Edge (%d->%d) lands here.\n",
2174                        e->src->index, e->dest->index);
2175           }
2176
2177         bsi = bsi_last (leader_edge->dest);
2178         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2179
2180         leader_match = NULL;
2181         /* We should never get a new block now.  */
2182       }
2183     else
2184       {
2185         e = VARRAY_EDGE (edge_leader, x);
2186         PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
2187         bsi_commit_one_edge_insert (e, NULL);
2188       }
2189
2190
2191   /* Clear the working data structures.  */
2192   VARRAY_POP_ALL (edge_leader);
2193   VARRAY_POP_ALL (stmt_list);
2194   bitmap_clear (leader_has_match);
2195
2196   return true;
2197 }
2198
2199
2200 /* This function will analyze the insertions which were performed on edges,
2201    and decide whether they should be left on that edge, or whether it is more
2202    efficient to emit some subset of them in a single block.  All stmts are
2203    inserted somewhere, and if non-NULL, debug information is printed via
2204    DUMP_FILE.  */
2205
2206 static void
2207 perform_edge_inserts (FILE *dump_file)
2208 {
2209   basic_block bb;
2210   bool changed = false;
2211
2212   if (dump_file)
2213     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2214
2215   FOR_EACH_BB (bb)
2216     changed |= analyze_edges_for_bb (bb, dump_file);
2217
2218   changed |= analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2219
2220   /* Clear out any tables which were created.  */
2221   edge_leader = NULL;
2222   BITMAP_XFREE (leader_has_match);
2223
2224   if (changed)
2225     {
2226       free_dominance_info (CDI_DOMINATORS);
2227       free_dominance_info (CDI_POST_DOMINATORS);
2228     }
2229
2230 #ifdef ENABLE_CHECKING
2231   {
2232     edge_iterator ei;
2233     edge e;
2234     FOR_EACH_BB (bb)
2235       {
2236         FOR_EACH_EDGE (e, ei, bb->preds)
2237           {
2238             if (PENDING_STMT (e))
2239               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2240                      e->src->index, e->dest->index);
2241           }
2242         FOR_EACH_EDGE (e, ei, bb->succs)
2243           {
2244             if (PENDING_STMT (e))
2245               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2246                      e->src->index, e->dest->index);
2247           }
2248       }
2249     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2250       {
2251         if (PENDING_STMT (e))
2252           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2253                  e->src->index, e->dest->index);
2254       }
2255     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2256       {
2257         if (PENDING_STMT (e))
2258           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2259                  e->src->index, e->dest->index);
2260       }
2261   }
2262 #endif
2263 }
2264
2265
2266 /* Remove the variables specified in MAP from SSA form.  Any debug information
2267    is sent to DUMP.  FLAGS indicate what options should be used.  */
2268
2269 static void
2270 remove_ssa_form (FILE *dump, var_map map, int flags)
2271 {
2272   tree_live_info_p liveinfo;
2273   basic_block bb;
2274   tree phi, next;
2275   FILE *save;
2276   tree *values = NULL;
2277
2278   save = dump_file;
2279   dump_file = dump;
2280
2281   /* If we are not combining temps, don't calculate live ranges for variables
2282      with only one SSA version.  */
2283   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2284     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2285   else
2286     compact_var_map (map, VARMAP_NORMAL);
2287
2288   if (dump_file && (dump_flags & TDF_DETAILS))
2289     dump_var_map (dump_file, map);
2290
2291   liveinfo = coalesce_ssa_name (map, flags);
2292
2293   /* Make sure even single occurrence variables are in the list now.  */
2294   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2295     compact_var_map (map, VARMAP_NORMAL);
2296
2297   if (dump_file && (dump_flags & TDF_DETAILS))
2298     {
2299       fprintf (dump_file, "After Coalescing:\n");
2300       dump_var_map (dump_file, map);
2301     }
2302
2303   if (flags & SSANORM_PERFORM_TER)
2304     {
2305       values = find_replaceable_exprs (map);
2306       if (values && dump_file && (dump_flags & TDF_DETAILS))
2307         dump_replaceable_exprs (dump_file, values);
2308     }
2309
2310   /* Assign real variables to the partitions now.  */
2311   assign_vars (map);
2312
2313   if (dump_file && (dump_flags & TDF_DETAILS))
2314     {
2315       fprintf (dump_file, "After Root variable replacement:\n");
2316       dump_var_map (dump_file, map);
2317     }
2318
2319   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2320     {
2321       coalesce_vars (map, liveinfo);
2322       if (dump_file && (dump_flags & TDF_DETAILS))
2323         {
2324           fprintf (dump_file, "After variable memory coalescing:\n");
2325           dump_var_map (dump_file, map);
2326         }
2327     }
2328
2329   if (liveinfo)
2330     delete_tree_live_info (liveinfo);
2331
2332   rewrite_trees (map, values);
2333
2334   if (values)
2335     free (values);
2336
2337   /* Remove phi nodes which have been translated back to real variables.  */
2338   FOR_EACH_BB (bb)
2339     {
2340       for (phi = phi_nodes (bb); phi; phi = next)
2341         {
2342           next = PHI_CHAIN (phi);
2343           if ((flags & SSANORM_REMOVE_ALL_PHIS)
2344               || var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
2345             remove_phi_node (phi, NULL_TREE, bb);
2346         }
2347     }
2348
2349   /* If any copies were inserted on edges, analyze and insert them now.  */
2350   perform_edge_inserts (dump_file);
2351
2352   dump_file = save;
2353 }
2354
2355 /* Take the current function out of SSA form, as described in
2356    R. Morgan, ``Building an Optimizing Compiler'',
2357    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2358
2359 static void
2360 rewrite_out_of_ssa (void)
2361 {
2362   var_map map;
2363   int var_flags = 0;
2364   int ssa_flags = (SSANORM_REMOVE_ALL_PHIS | SSANORM_USE_COALESCE_LIST);
2365
2366   if (!flag_tree_live_range_split)
2367     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2368
2369   eliminate_virtual_phis ();
2370
2371   if (dump_file && (dump_flags & TDF_DETAILS))
2372     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2373
2374   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2375   if (flag_tree_ter && !flag_mudflap)
2376     var_flags = SSA_VAR_MAP_REF_COUNT;
2377
2378   map = create_ssa_var_map (var_flags);
2379
2380   if (flag_tree_combine_temps)
2381     ssa_flags |= SSANORM_COMBINE_TEMPS;
2382   if (flag_tree_ter && !flag_mudflap)
2383     ssa_flags |= SSANORM_PERFORM_TER;
2384
2385   remove_ssa_form (dump_file, map, ssa_flags);
2386
2387   if (dump_file && (dump_flags & TDF_DETAILS))
2388     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2389
2390   /* Do some cleanups which reduce the amount of data the
2391      tree->rtl expanders deal with.  */
2392   cfg_remove_useless_stmts ();
2393
2394   /* Flush out flow graph and SSA data.  */
2395   delete_var_map (map);
2396
2397   /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE.  */
2398   discover_nonconstant_array_refs ();
2399 }
2400
2401
2402 /* Define the parameters of the out of SSA pass.  */
2403
2404 struct tree_opt_pass pass_del_ssa =
2405 {
2406   "optimized",                          /* name */
2407   NULL,                                 /* gate */
2408   rewrite_out_of_ssa,                   /* execute */
2409   NULL,                                 /* sub */
2410   NULL,                                 /* next */
2411   0,                                    /* static_pass_number */
2412   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2413   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2414   0,                                    /* properties_provided */
2415   /* ??? If TER is enabled, we also kill gimple.  */
2416   PROP_ssa,                             /* properties_destroyed */
2417   TODO_verify_ssa | TODO_verify_flow
2418     | TODO_verify_stmts,                /* todo_flags_start */
2419   TODO_dump_func | TODO_ggc_collect,    /* todo_flags_finish */
2420   0                                     /* letter */
2421 };