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