gcc/tree-outof-ssa.c

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