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   stmt_ann_t ann;
1448   vuse_optype vuseops;
1449   def_optype defs;
1450   use_optype uses;
1451   tree var, def;
1452   int num_use_ops, version;
1453   var_map map = tab->map;
1454   ssa_op_iter iter;
1455   tree call_expr;
1456
1457   if (TREE_CODE (stmt) != MODIFY_EXPR)
1458     return false;
1459
1460   ann = stmt_ann (stmt);
1461   defs = DEF_OPS (ann);
1462
1463   /* Punt if there is more than 1 def, or more than 1 use.  */
1464   if (NUM_DEFS (defs) != 1)
1465     return false;
1466   def = DEF_OP (defs, 0);
1467   if (version_ref_count (map, def) != 1)
1468     return false;
1469
1470   /* There must be no V_MAY_DEFS.  */
1471   if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) != 0)
1472     return false;
1473
1474   /* There must be no V_MUST_DEFS.  */
1475   if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) != 0)
1476     return false;
1477
1478   /* Float expressions must go through memory if float-store is on.  */
1479   if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1))))
1480     return false;
1481
1482   /* Calls to functions with side-effects cannot be replaced.  */
1483   if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE)
1484     {
1485       int call_flags = call_expr_flags (call_expr);
1486       if (TREE_SIDE_EFFECTS (call_expr)
1487           && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN)))
1488         return false;
1489     }
1490
1491   uses = USE_OPS (ann);
1492   num_use_ops = NUM_USES (uses);
1493   vuseops = VUSE_OPS (ann);
1494
1495   /* Any expression which has no virtual operands and no real operands
1496      should have been propagated if it's possible to do anything with them.
1497      If this happens here, it probably exists that way for a reason, so we
1498      won't touch it.   An example is:
1499          b_4 = &tab
1500      There are no virtual uses nor any real uses, so we just leave this
1501      alone to be safe.  */
1502
1503   if (num_use_ops == 0 && NUM_VUSES (vuseops) == 0)
1504     return false;
1505
1506   version = SSA_NAME_VERSION (def);
1507
1508   /* Add this expression to the dependency list for each use partition.  */
1509   FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE)
1510     {
1511       add_dependance (tab, version, var);
1512     }
1513
1514   /* If there are VUSES, add a dependence on virtual defs.  */
1515   if (NUM_VUSES (vuseops) != 0)
1516     {
1517       add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]),
1518                          VIRTUAL_PARTITION (tab));
1519       add_value_to_list (tab,
1520                          &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]),
1521                          version);
1522       bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab));
1523     }
1524
1525   return true;
1526 }
1527
1528
1529 /* This function will remove the expression for VERSION from replacement
1530    consideration.n table TAB  If 'replace' is true, it is marked as
1531    replaceable, otherwise not.  */
1532
1533 static void
1534 finish_expr (temp_expr_table_p tab, int version, bool replace)
1535 {
1536   value_expr_p info, tmp;
1537   int partition;
1538
1539   /* Remove this expression from its dependent lists.  The partition dependence
1540      list is retained and transfered later to whomever uses this version.  */
1541   for (info = (value_expr_p) tab->version_info[version]; info; info = tmp)
1542     {
1543       partition = info->value;
1544       gcc_assert (tab->partition_dep_list[partition]);
1545       tmp = remove_value_from_list (&(tab->partition_dep_list[partition]),
1546                                     version);
1547       gcc_assert (tmp);
1548       free_value_expr (tab, tmp);
1549       /* Only clear the bit when the dependency list is emptied via
1550          a replacement. Otherwise kill_expr will take care of it.  */
1551       if (!(tab->partition_dep_list[partition]) && replace)
1552         bitmap_clear_bit (tab->partition_in_use, partition);
1553       tmp = info->next;
1554       if (!replace)
1555         free_value_expr (tab, info);
1556     }
1557
1558   if (replace)
1559     {
1560       tab->saw_replaceable = true;
1561       bitmap_set_bit (tab->replaceable, version);
1562     }
1563   else
1564     {
1565       gcc_assert (!bitmap_bit_p (tab->replaceable, version));
1566       tab->version_info[version] = NULL;
1567     }
1568 }
1569
1570
1571 /* Mark the expression associated with VAR as replaceable, and enter
1572    the defining stmt into the version_info table TAB.  */
1573
1574 static void
1575 mark_replaceable (temp_expr_table_p tab, tree var)
1576 {
1577   value_expr_p info;
1578   int version = SSA_NAME_VERSION (var);
1579   finish_expr (tab, version, true);
1580
1581   /* Move the dependence list to the pending list.  */
1582   if (tab->version_info[version])
1583     {
1584       info = (value_expr_p) tab->version_info[version];
1585       for ( ; info->next; info = info->next)
1586         continue;
1587       info->next = tab->pending_dependence;
1588       tab->pending_dependence = (value_expr_p)tab->version_info[version];
1589     }
1590
1591   tab->version_info[version] = SSA_NAME_DEF_STMT (var);
1592 }
1593
1594
1595 /* This function marks any expression in TAB which is dependent on PARTITION
1596    as NOT replaceable.  CLEAR_BIT is used to determine whether partition_in_use
1597    should have its bit cleared.  Since this routine can be called within an
1598    EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared.  */
1599
1600 static inline void
1601 kill_expr (temp_expr_table_p tab, int partition, bool clear_bit)
1602 {
1603   value_expr_p ptr;
1604
1605   /* Mark every active expr dependent on this var as not replaceable.  */
1606   while ((ptr = tab->partition_dep_list[partition]) != NULL)
1607     finish_expr (tab, ptr->value, false);
1608
1609   if (clear_bit)
1610     bitmap_clear_bit (tab->partition_in_use, partition);
1611 }
1612
1613
1614 /* This function kills all expressions in TAB which are dependent on virtual
1615    DEFs.  CLEAR_BIT determines whether partition_in_use gets cleared.  */
1616
1617 static inline void
1618 kill_virtual_exprs (temp_expr_table_p tab, bool clear_bit)
1619 {
1620   kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit);
1621 }
1622
1623
1624 /* This function processes basic block BB, and looks for variables which can
1625    be replaced by their expressions.  Results are stored in TAB.  */
1626
1627 static void
1628 find_replaceable_in_bb (temp_expr_table_p tab, basic_block bb)
1629 {
1630   block_stmt_iterator bsi;
1631   tree stmt, def;
1632   stmt_ann_t ann;
1633   int partition;
1634   var_map map = tab->map;
1635   value_expr_p p;
1636   ssa_op_iter iter;
1637
1638   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1639     {
1640       stmt = bsi_stmt (bsi);
1641       ann = stmt_ann (stmt);
1642
1643       /* Determine if this stmt finishes an existing expression.  */
1644       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_USE)
1645         {
1646           if (tab->version_info[SSA_NAME_VERSION (def)])
1647             {
1648               bool same_root_var = false;
1649               tree def2;
1650               ssa_op_iter iter2;
1651
1652               /* See if the root variables are the same.  If they are, we
1653                  do not want to do the replacement to avoid problems with
1654                  code size, see PR tree-optimization/17549.  */
1655               FOR_EACH_SSA_TREE_OPERAND (def2, stmt, iter2, SSA_OP_DEF)
1656                 if (SSA_NAME_VAR (def) == SSA_NAME_VAR (def2))
1657                   {
1658                     same_root_var = true;
1659                     break;
1660                   }
1661
1662               /* Mark expression as replaceable unless stmt is volatile
1663                  or DEF sets the same root variable as STMT.  */
1664               if (!ann->has_volatile_ops && !same_root_var)
1665                 mark_replaceable (tab, def);
1666               else
1667                 finish_expr (tab, SSA_NAME_VERSION (def), false);
1668             }
1669         }
1670
1671       /* Next, see if this stmt kills off an active expression.  */
1672       FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
1673         {
1674           partition = var_to_partition (map, def);
1675           if (partition != NO_PARTITION && tab->partition_dep_list[partition])
1676             kill_expr (tab, partition, true);
1677         }
1678
1679       /* Now see if we are creating a new expression or not.  */
1680       if (!ann->has_volatile_ops)
1681         check_replaceable (tab, stmt);
1682
1683       /* Free any unused dependency lists.  */
1684       while ((p = tab->pending_dependence))
1685         {
1686           tab->pending_dependence = p->next;
1687           free_value_expr (tab, p);
1688         }
1689
1690       /* A V_MAY_DEF kills any expression using a virtual operand.  */
1691       if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) > 0)
1692         kill_virtual_exprs (tab, true);
1693
1694       /* A V_MUST_DEF kills any expression using a virtual operand.  */
1695       if (NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) > 0)
1696         kill_virtual_exprs (tab, true);
1697     }
1698 }
1699
1700
1701 /* This function is the driver routine for replacement of temporary expressions
1702    in the SSA->normal phase, operating on MAP.  If there are replaceable
1703    expressions, a table is returned which maps SSA versions to the
1704    expressions they should be replaced with.  A NULL_TREE indicates no
1705    replacement should take place.  If there are no replacements at all,
1706    NULL is returned by the function, otherwise an expression vector indexed
1707    by SSA_NAME version numbers.  */
1708
1709 static tree *
1710 find_replaceable_exprs (var_map map)
1711 {
1712   basic_block bb;
1713   unsigned i;
1714   temp_expr_table_p table;
1715   tree *ret;
1716
1717   table = new_temp_expr_table (map);
1718   FOR_EACH_BB (bb)
1719     {
1720       bitmap_iterator bi;
1721
1722       find_replaceable_in_bb (table, bb);
1723       EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi)
1724         {
1725           kill_expr (table, i, false);
1726         }
1727     }
1728
1729   ret = free_temp_expr_table (table);
1730   return ret;
1731 }
1732
1733
1734 /* Dump TER expression table EXPR to file F.  */
1735
1736 static void
1737 dump_replaceable_exprs (FILE *f, tree *expr)
1738 {
1739   tree stmt, var;
1740   int x;
1741   fprintf (f, "\nReplacing Expressions\n");
1742   for (x = 0; x < (int)num_ssa_names + 1; x++)
1743     if (expr[x])
1744       {
1745         stmt = expr[x];
1746         var = DEF_OP (STMT_DEF_OPS (stmt), 0);
1747         print_generic_expr (f, var, TDF_SLIM);
1748         fprintf (f, " replace with --> ");
1749         print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM);
1750         fprintf (f, "\n");
1751       }
1752   fprintf (f, "\n");
1753 }
1754
1755
1756 /* Helper function for discover_nonconstant_array_refs.
1757    Look for ARRAY_REF nodes with non-constant indexes and mark them
1758    addressable.  */
1759
1760 static tree
1761 discover_nonconstant_array_refs_r (tree * tp, int *walk_subtrees,
1762                                    void *data ATTRIBUTE_UNUSED)
1763 {
1764   tree t = *tp;
1765
1766   if (IS_TYPE_OR_DECL_P (t))
1767     *walk_subtrees = 0;
1768   else if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1769     {
1770       while (((TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1771               && is_gimple_min_invariant (TREE_OPERAND (t, 1))
1772               && (!TREE_OPERAND (t, 2)
1773                   || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1774              || (TREE_CODE (t) == COMPONENT_REF
1775                  && (!TREE_OPERAND (t,2)
1776                      || is_gimple_min_invariant (TREE_OPERAND (t, 2))))
1777              || TREE_CODE (t) == BIT_FIELD_REF
1778              || TREE_CODE (t) == REALPART_EXPR
1779              || TREE_CODE (t) == IMAGPART_EXPR
1780              || TREE_CODE (t) == VIEW_CONVERT_EXPR
1781              || TREE_CODE (t) == NOP_EXPR
1782              || TREE_CODE (t) == CONVERT_EXPR)
1783         t = TREE_OPERAND (t, 0);
1784
1785       if (TREE_CODE (t) == ARRAY_REF || TREE_CODE (t) == ARRAY_RANGE_REF)
1786         {
1787           t = get_base_address (t);
1788           if (t && DECL_P (t))
1789             TREE_ADDRESSABLE (t) = 1;
1790         }
1791
1792       *walk_subtrees = 0;
1793     }
1794
1795   return NULL_TREE;
1796 }
1797
1798
1799 /* RTL expansion is not able to compile array references with variable
1800    offsets for arrays stored in single register.  Discover such
1801    expressions and mark variables as addressable to avoid this
1802    scenario.  */
1803
1804 static void
1805 discover_nonconstant_array_refs (void)
1806 {
1807   basic_block bb;
1808   block_stmt_iterator bsi;
1809
1810   FOR_EACH_BB (bb)
1811     {
1812       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1813         walk_tree (bsi_stmt_ptr (bsi), discover_nonconstant_array_refs_r,
1814                    NULL , NULL);
1815     }
1816 }
1817
1818
1819 /* This function will rewrite the current program using the variable mapping
1820    found in MAP.  If the replacement vector VALUES is provided, any
1821    occurrences of partitions with non-null entries in the vector will be
1822    replaced with the expression in the vector instead of its mapped
1823    variable.  */
1824
1825 static void
1826 rewrite_trees (var_map map, tree *values)
1827 {
1828   elim_graph g;
1829   basic_block bb;
1830   block_stmt_iterator si;
1831   edge e;
1832   tree phi;
1833   bool changed;
1834
1835 #ifdef ENABLE_CHECKING
1836   /* Search for PHIs where the destination has no partition, but one
1837      or more arguments has a partition.  This should not happen and can
1838      create incorrect code.  */
1839   FOR_EACH_BB (bb)
1840     {
1841       tree phi;
1842
1843       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
1844         {
1845           tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi));
1846
1847           if (T0 == NULL_TREE)
1848             {
1849               int i;
1850
1851               for (i = 0; i < PHI_NUM_ARGS (phi); i++)
1852                 {
1853                   tree arg = PHI_ARG_DEF (phi, i);
1854
1855                   if (TREE_CODE (arg) == SSA_NAME
1856                       && var_to_partition (map, arg) != NO_PARTITION)
1857                     {
1858                       fprintf (stderr, "Argument of PHI is in a partition :(");
1859                       print_generic_expr (stderr, arg, TDF_SLIM);
1860                       fprintf (stderr, "), but the result is not :");
1861                       print_generic_stmt (stderr, phi, TDF_SLIM);
1862                       internal_error ("SSA corruption");
1863                     }
1864                 }
1865             }
1866         }
1867     }
1868 #endif
1869
1870   /* Replace PHI nodes with any required copies.  */
1871   g = new_elim_graph (map->num_partitions);
1872   g->map = map;
1873   FOR_EACH_BB (bb)
1874     {
1875       for (si = bsi_start (bb); !bsi_end_p (si); )
1876         {
1877           size_t num_uses, num_defs;
1878           use_optype uses;
1879           def_optype defs;
1880           tree stmt = bsi_stmt (si);
1881           use_operand_p use_p;
1882           def_operand_p def_p;
1883           int remove = 0, is_copy = 0;
1884           stmt_ann_t ann;
1885           ssa_op_iter iter;
1886
1887           ann = stmt_ann (stmt);
1888           changed = false;
1889
1890           if (TREE_CODE (stmt) == MODIFY_EXPR
1891               && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME))
1892             is_copy = 1;
1893
1894           uses = USE_OPS (ann);
1895           num_uses = NUM_USES (uses);
1896           FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
1897             {
1898               if (replace_use_variable (map, use_p, values))
1899                 changed = true;
1900             }
1901
1902           defs = DEF_OPS (ann);
1903           num_defs = NUM_DEFS (defs);
1904
1905           /* Mark this stmt for removal if it is the list of replaceable
1906              expressions.  */
1907           if (values && num_defs == 1)
1908             {
1909               tree def = DEF_OP (defs, 0);
1910               tree val;
1911               val = values[SSA_NAME_VERSION (def)];
1912               if (val)
1913                 remove = 1;
1914             }
1915           if (!remove)
1916             {
1917               FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF)
1918                 {
1919                   if (replace_def_variable (map, def_p, NULL))
1920                     changed = true;
1921
1922                   /* If both SSA_NAMEs coalesce to the same variable,
1923                      mark the now redundant copy for removal.  */
1924                   if (is_copy
1925                       && num_uses == 1
1926                       && (DEF_FROM_PTR (def_p) == USE_OP (uses, 0)))
1927                     remove = 1;
1928                 }
1929             }
1930
1931           /* Remove any stmts marked for removal.  */
1932           if (remove)
1933             bsi_remove (&si);
1934           else
1935             bsi_next (&si);
1936         }
1937
1938       phi = phi_nodes (bb);
1939       if (phi)
1940         {
1941           edge_iterator ei;
1942           FOR_EACH_EDGE (e, ei, bb->preds)
1943             eliminate_phi (e, g);
1944         }
1945     }
1946
1947   delete_elim_graph (g);
1948 }
1949
1950
1951 /* These are the local work structures used to determine the best place to
1952    insert the copies that were placed on edges by the SSA->normal pass..  */
1953 static varray_type edge_leader = NULL;
1954 static varray_type GTY(()) stmt_list = NULL;
1955 static bitmap leader_has_match = NULL;
1956 static edge leader_match = NULL;
1957
1958
1959 /* Pass this function to make_forwarder_block so that all the edges with
1960    matching PENDING_STMT lists to 'curr_stmt_list' get redirected.  */
1961 static bool
1962 same_stmt_list_p (edge e)
1963 {
1964   return (e->aux == (PTR) leader_match) ? true : false;
1965 }
1966
1967
1968 /* Return TRUE if S1 and S2 are equivalent copies.  */
1969 static inline bool
1970 identical_copies_p (tree s1, tree s2)
1971 {
1972 #ifdef ENABLE_CHECKING
1973   gcc_assert (TREE_CODE (s1) == MODIFY_EXPR);
1974   gcc_assert (TREE_CODE (s2) == MODIFY_EXPR);
1975   gcc_assert (DECL_P (TREE_OPERAND (s1, 0)));
1976   gcc_assert (DECL_P (TREE_OPERAND (s2, 0)));
1977 #endif
1978
1979   if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0))
1980     return false;
1981
1982   s1 = TREE_OPERAND (s1, 1);
1983   s2 = TREE_OPERAND (s2, 1);
1984
1985   if (s1 != s2)
1986     return false;
1987
1988   return true;
1989 }
1990
1991
1992 /* Compare the PENDING_STMT list for two edges, and return true if the lists
1993    contain the same sequence of copies.  */
1994
1995 static inline bool
1996 identical_stmt_lists_p (edge e1, edge e2)
1997 {
1998   tree t1 = PENDING_STMT (e1);
1999   tree t2 = PENDING_STMT (e2);
2000   tree_stmt_iterator tsi1, tsi2;
2001
2002   gcc_assert (TREE_CODE (t1) == STATEMENT_LIST);
2003   gcc_assert (TREE_CODE (t2) == STATEMENT_LIST);
2004
2005   for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2);
2006        !tsi_end_p (tsi1) && !tsi_end_p (tsi2);
2007        tsi_next (&tsi1), tsi_next (&tsi2))
2008     {
2009       if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2)))
2010         break;
2011     }
2012
2013   if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2))
2014     return false;
2015
2016   return true;
2017 }
2018
2019
2020 /* Look at all the incoming edges to block BB, and decide where the best place
2021    to insert the stmts on each edge are, and perform those insertions.   Output
2022    any debug information to DEBUG_FILE.  */
2023
2024 static void
2025 analyze_edges_for_bb (basic_block bb, FILE *debug_file)
2026 {
2027   edge e;
2028   edge_iterator ei;
2029   int count;
2030   unsigned int x;
2031   bool have_opportunity;
2032   block_stmt_iterator bsi;
2033   tree stmt;
2034   edge single_edge = NULL;
2035   bool is_label;
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   if (edge_leader == NULL)
2097     {
2098       VARRAY_EDGE_INIT (edge_leader, 25, "edge_leader");
2099       VARRAY_TREE_INIT (stmt_list, 25, "stmt_list");
2100       leader_has_match = BITMAP_ALLOC (NULL);
2101     }
2102   else
2103     {
2104 #ifdef ENABLE_CHECKING
2105       gcc_assert (VARRAY_ACTIVE_SIZE (edge_leader) == 0);
2106       gcc_assert (VARRAY_ACTIVE_SIZE (stmt_list) == 0);
2107       gcc_assert (bitmap_empty_p (leader_has_match));
2108 #endif
2109     }
2110
2111   /* Find the "leader" block for each set of unique stmt lists.  Preference is
2112      given to FALLTHRU blocks since they would need a GOTO to arrive at another
2113      block.  The leader edge destination is the block which all the other edges
2114      with the same stmt list will be redirected to.  */
2115   have_opportunity = false;
2116   FOR_EACH_EDGE (e, ei, bb->preds)
2117     {
2118       if (PENDING_STMT (e))
2119         {
2120           bool found = false;
2121
2122           /* Look for the same stmt list in edge leaders list.  */
2123           for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2124             {
2125               edge leader = VARRAY_EDGE (edge_leader, x);
2126               if (identical_stmt_lists_p (leader, e))
2127                 {
2128                   /* Give this edge the same stmt list pointer.  */
2129                   PENDING_STMT (e) = NULL;
2130                   e->aux = leader;
2131                   bitmap_set_bit (leader_has_match, x);
2132                   have_opportunity = found = true;
2133                   break;
2134                 }
2135             }
2136
2137           /* If no similar stmt list, add this edge to the leader list.  */
2138           if (!found)
2139             {
2140               VARRAY_PUSH_EDGE (edge_leader, e);
2141               VARRAY_PUSH_TREE (stmt_list, PENDING_STMT (e));
2142             }
2143         }
2144      }
2145
2146   /* If there are no similar lists, just issue the stmts.  */
2147   if (!have_opportunity)
2148     {
2149       for (x = 0; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2150         bsi_commit_one_edge_insert (VARRAY_EDGE (edge_leader, x), NULL);
2151       VARRAY_POP_ALL (edge_leader);
2152       VARRAY_POP_ALL (stmt_list);
2153       bitmap_clear (leader_has_match);
2154       return;
2155     }
2156
2157
2158   if (debug_file)
2159     fprintf (debug_file, "\nOpportunities in BB %d for stmt/block reduction:\n",
2160              bb->index);
2161
2162
2163   /* For each common list, create a forwarding block and issue the stmt's
2164      in that block.  */
2165   for (x = 0 ; x < VARRAY_ACTIVE_SIZE (edge_leader); x++)
2166     if (bitmap_bit_p (leader_has_match, x))
2167       {
2168         edge new_edge, leader_edge;
2169         block_stmt_iterator bsi;
2170         tree curr_stmt_list;
2171
2172         leader_match = leader_edge = VARRAY_EDGE (edge_leader, x);
2173
2174         /* The tree_* cfg manipulation routines use the PENDING_EDGE field
2175            for various PHI manipulations, so it gets cleared whhen calls are
2176            made to make_forwarder_block(). So make sure the edge is clear,
2177            and use the saved stmt list.  */
2178         PENDING_STMT (leader_edge) = NULL;
2179         leader_edge->aux = leader_edge;
2180         curr_stmt_list = VARRAY_TREE (stmt_list, x);
2181
2182         new_edge = make_forwarder_block (leader_edge->dest, same_stmt_list_p,
2183                                          NULL);
2184         bb = new_edge->dest;
2185         if (debug_file)
2186           {
2187             fprintf (debug_file, "Splitting BB %d for Common stmt list.  ",
2188                      leader_edge->dest->index);
2189             fprintf (debug_file, "Original block is now BB%d.\n", bb->index);
2190             print_generic_stmt (debug_file, curr_stmt_list, TDF_VOPS);
2191           }
2192
2193         FOR_EACH_EDGE (e, ei, new_edge->src->preds)
2194           {
2195             e->aux = NULL;
2196             if (debug_file)
2197               fprintf (debug_file, "  Edge (%d->%d) lands here.\n",
2198                        e->src->index, e->dest->index);
2199           }
2200
2201         bsi = bsi_last (leader_edge->dest);
2202         bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT);
2203
2204         leader_match = NULL;
2205         /* We should never get a new block now.  */
2206       }
2207     else
2208       {
2209         e = VARRAY_EDGE (edge_leader, x);
2210         PENDING_STMT (e) = VARRAY_TREE (stmt_list, x);
2211         bsi_commit_one_edge_insert (e, NULL);
2212       }
2213
2214
2215   /* Clear the working data structures.  */
2216   VARRAY_POP_ALL (edge_leader);
2217   VARRAY_POP_ALL (stmt_list);
2218   bitmap_clear (leader_has_match);
2219 }
2220
2221
2222 /* This function will analyze the insertions which were performed on edges,
2223    and decide whether they should be left on that edge, or whether it is more
2224    efficient to emit some subset of them in a single block.  All stmts are
2225    inserted somewhere, and if non-NULL, debug information is printed via
2226    DUMP_FILE.  */
2227
2228 static void
2229 perform_edge_inserts (FILE *dump_file)
2230 {
2231   basic_block bb;
2232
2233   if (dump_file)
2234     fprintf(dump_file, "Analyzing Edge Insertions.\n");
2235
2236   /* analyze_edges_for_bb calls make_forwarder_block, which tries to
2237      incrementally update the dominator information.  Since we don't
2238      need dominator information after this pass, go ahead and free the
2239      dominator information.  */
2240   free_dominance_info (CDI_DOMINATORS);
2241   free_dominance_info (CDI_POST_DOMINATORS);
2242
2243   FOR_EACH_BB (bb)
2244     analyze_edges_for_bb (bb, dump_file);
2245
2246   analyze_edges_for_bb (EXIT_BLOCK_PTR, dump_file);
2247
2248   /* Clear out any tables which were created.  */
2249   edge_leader = NULL;
2250   BITMAP_FREE (leader_has_match);
2251
2252 #ifdef ENABLE_CHECKING
2253   {
2254     edge_iterator ei;
2255     edge e;
2256     FOR_EACH_BB (bb)
2257       {
2258         FOR_EACH_EDGE (e, ei, bb->preds)
2259           {
2260             if (PENDING_STMT (e))
2261               error (" Pending stmts not issued on PRED edge (%d, %d)\n",
2262                      e->src->index, e->dest->index);
2263           }
2264         FOR_EACH_EDGE (e, ei, bb->succs)
2265           {
2266             if (PENDING_STMT (e))
2267               error (" Pending stmts not issued on SUCC edge (%d, %d)\n",
2268                      e->src->index, e->dest->index);
2269           }
2270       }
2271     FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
2272       {
2273         if (PENDING_STMT (e))
2274           error (" Pending stmts not issued on ENTRY edge (%d, %d)\n",
2275                  e->src->index, e->dest->index);
2276       }
2277     FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds)
2278       {
2279         if (PENDING_STMT (e))
2280           error (" Pending stmts not issued on EXIT edge (%d, %d)\n",
2281                  e->src->index, e->dest->index);
2282       }
2283   }
2284 #endif
2285 }
2286
2287
2288 /* Remove the variables specified in MAP from SSA form.  Any debug information
2289    is sent to DUMP.  FLAGS indicate what options should be used.  */
2290
2291 static void
2292 remove_ssa_form (FILE *dump, var_map map, int flags)
2293 {
2294   tree_live_info_p liveinfo;
2295   basic_block bb;
2296   tree phi, next;
2297   FILE *save;
2298   tree *values = NULL;
2299
2300   save = dump_file;
2301   dump_file = dump;
2302
2303   /* If we are not combining temps, don't calculate live ranges for variables
2304      with only one SSA version.  */
2305   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2306     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
2307   else
2308     compact_var_map (map, VARMAP_NORMAL);
2309
2310   if (dump_file && (dump_flags & TDF_DETAILS))
2311     dump_var_map (dump_file, map);
2312
2313   liveinfo = coalesce_ssa_name (map, flags);
2314
2315   /* Make sure even single occurrence variables are in the list now.  */
2316   if ((flags & SSANORM_COMBINE_TEMPS) == 0)
2317     compact_var_map (map, VARMAP_NORMAL);
2318
2319   if (dump_file && (dump_flags & TDF_DETAILS))
2320     {
2321       fprintf (dump_file, "After Coalescing:\n");
2322       dump_var_map (dump_file, map);
2323     }
2324
2325   if (flags & SSANORM_PERFORM_TER)
2326     {
2327       values = find_replaceable_exprs (map);
2328       if (values && dump_file && (dump_flags & TDF_DETAILS))
2329         dump_replaceable_exprs (dump_file, values);
2330     }
2331
2332   /* Assign real variables to the partitions now.  */
2333   assign_vars (map);
2334
2335   if (dump_file && (dump_flags & TDF_DETAILS))
2336     {
2337       fprintf (dump_file, "After Root variable replacement:\n");
2338       dump_var_map (dump_file, map);
2339     }
2340
2341   if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo)
2342     {
2343       coalesce_vars (map, liveinfo);
2344       if (dump_file && (dump_flags & TDF_DETAILS))
2345         {
2346           fprintf (dump_file, "After variable memory coalescing:\n");
2347           dump_var_map (dump_file, map);
2348         }
2349     }
2350
2351   if (liveinfo)
2352     delete_tree_live_info (liveinfo);
2353
2354   rewrite_trees (map, values);
2355
2356   if (values)
2357     free (values);
2358
2359   /* Remove phi nodes which have been translated back to real variables.  */
2360   FOR_EACH_BB (bb)
2361     {
2362       for (phi = phi_nodes (bb); phi; phi = next)
2363         {
2364           next = PHI_CHAIN (phi);
2365           remove_phi_node (phi, NULL_TREE);
2366         }
2367     }
2368
2369   /* we no longer maintain the SSA operand cache at this point.  */
2370   fini_ssa_operands ();
2371
2372   /* If any copies were inserted on edges, analyze and insert them now.  */
2373   perform_edge_inserts (dump_file);
2374
2375   dump_file = save;
2376 }
2377
2378 /* Search every PHI node for arguments associated with backedges which
2379    we can trivially determine will need a copy (the argument is either
2380    not an SSA_NAME or the argument has a different underlying variable
2381    than the PHI result).
2382
2383    Insert a copy from the PHI argument to a new destination at the
2384    end of the block with the backedge to the top of the loop.  Update
2385    the PHI argument to reference this new destination.  */
2386
2387 static void
2388 insert_backedge_copies (void)
2389 {
2390   basic_block bb;
2391
2392   FOR_EACH_BB (bb)
2393     {
2394       tree phi;
2395
2396       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
2397         {
2398           tree result = PHI_RESULT (phi);
2399           tree result_var;
2400           int i;
2401
2402           if (!is_gimple_reg (result))
2403             continue;
2404
2405           result_var = SSA_NAME_VAR (result);
2406           for (i = 0; i < PHI_NUM_ARGS (phi); i++)
2407             {
2408               tree arg = PHI_ARG_DEF (phi, i);
2409               edge e = PHI_ARG_EDGE (phi, i);
2410
2411               /* If the argument is not an SSA_NAME, then we will
2412                  need a constant initialization.  If the argument is
2413                  an SSA_NAME with a different underlying variable and
2414                  we are not combining temporaries, then we will
2415                  need a copy statement.  */
2416               if ((e->flags & EDGE_DFS_BACK)
2417                   && (TREE_CODE (arg) != SSA_NAME
2418                       || (!flag_tree_combine_temps
2419                           && SSA_NAME_VAR (arg) != result_var)))
2420                 {
2421                   tree stmt, name, last = NULL;
2422                   block_stmt_iterator bsi;
2423
2424                   bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src);
2425                   if (!bsi_end_p (bsi))
2426                     last = bsi_stmt (bsi);
2427
2428                   /* In theory the only way we ought to get back to the
2429                      start of a loop should be with a COND_EXPR or GOTO_EXPR.
2430                      However, better safe than sorry.
2431
2432                      If the block ends with a control statement or
2433                      something that might throw, then we have to
2434                      insert this assignment before the last
2435                      statement.  Else insert it after the last statement.  */
2436                   if (last && stmt_ends_bb_p (last))
2437                     {
2438                       /* If the last statement in the block is the definition
2439                          site of the PHI argument, then we can't insert
2440                          anything after it.  */
2441                       if (TREE_CODE (arg) == SSA_NAME
2442                           && SSA_NAME_DEF_STMT (arg) == last)
2443                         continue;
2444                     }
2445
2446                   /* Create a new instance of the underlying
2447                      variable of the PHI result.  */
2448                   stmt = build (MODIFY_EXPR, TREE_TYPE (result_var),
2449                                 NULL, PHI_ARG_DEF (phi, i));
2450                   name = make_ssa_name (result_var, stmt);
2451                   TREE_OPERAND (stmt, 0) = name;
2452
2453                   /* Insert the new statement into the block and update
2454                      the PHI node.  */
2455                   if (last && stmt_ends_bb_p (last))
2456                     bsi_insert_before (&bsi, stmt, BSI_NEW_STMT);
2457                   else
2458                     bsi_insert_after (&bsi, stmt, BSI_NEW_STMT);
2459                   SET_PHI_ARG_DEF (phi, i, name);
2460                 }
2461             }
2462         }
2463     }
2464 }
2465
2466 /* Take the current function out of SSA form, as described in
2467    R. Morgan, ``Building an Optimizing Compiler'',
2468    Butterworth-Heinemann, Boston, MA, 1998. pp 176-186.  */
2469
2470 static void
2471 rewrite_out_of_ssa (void)
2472 {
2473   var_map map;
2474   int var_flags = 0;
2475   int ssa_flags = 0;
2476
2477   /* If elimination of a PHI requires inserting a copy on a backedge,
2478      then we will have to split the backedge which has numerous
2479      undesirable performance effects.
2480
2481      A significant number of such cases can be handled here by inserting
2482      copies into the loop itself.  */
2483   insert_backedge_copies ();
2484
2485   if (!flag_tree_live_range_split)
2486     ssa_flags |= SSANORM_COALESCE_PARTITIONS;
2487
2488   eliminate_virtual_phis ();
2489
2490   if (dump_file && (dump_flags & TDF_DETAILS))
2491     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2492
2493   /* We cannot allow unssa to un-gimplify trees before we instrument them.  */
2494   if (flag_tree_ter && !flag_mudflap)
2495     var_flags = SSA_VAR_MAP_REF_COUNT;
2496
2497   map = create_ssa_var_map (var_flags);
2498
2499   if (flag_tree_combine_temps)
2500     ssa_flags |= SSANORM_COMBINE_TEMPS;
2501   if (flag_tree_ter && !flag_mudflap)
2502     ssa_flags |= SSANORM_PERFORM_TER;
2503
2504   remove_ssa_form (dump_file, map, ssa_flags);
2505
2506   if (dump_file && (dump_flags & TDF_DETAILS))
2507     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
2508
2509   /* Flush out flow graph and SSA data.  */
2510   delete_var_map (map);
2511
2512   /* Mark arrays indexed with non-constant indices with TREE_ADDRESSABLE.  */
2513   discover_nonconstant_array_refs ();
2514
2515   in_ssa_p = false;
2516 }
2517
2518
2519 /* Define the parameters of the out of SSA pass.  */
2520
2521 struct tree_opt_pass pass_del_ssa =
2522 {
2523   "optimized",                          /* name */
2524   NULL,                                 /* gate */
2525   rewrite_out_of_ssa,                   /* execute */
2526   NULL,                                 /* sub */
2527   NULL,                                 /* next */
2528   0,                                    /* static_pass_number */
2529   TV_TREE_SSA_TO_NORMAL,                /* tv_id */
2530   PROP_cfg | PROP_ssa | PROP_alias,     /* properties_required */
2531   0,                                    /* properties_provided */
2532   /* ??? If TER is enabled, we also kill gimple.  */
2533   PROP_ssa,                             /* properties_destroyed */
2534   TODO_verify_ssa | TODO_verify_flow
2535     | TODO_verify_stmts,                /* todo_flags_start */
2536   TODO_dump_func | TODO_ggc_collect,    /* todo_flags_finish */
2537   0                                     /* letter */
2538 };