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