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