gcc/tree-outof-ssa.c

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