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