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 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 2, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, 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 78typedef 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. */ 106static tree create_temp (tree); 107static void insert_copy_on_edge (edge, tree, tree); 108static elim_graph new_elim_graph (int); 109static inline void delete_elim_graph (elim_graph); 110static inline void clear_elim_graph (elim_graph); 111static inline int elim_graph_size (elim_graph); 112static inline void elim_graph_add_node (elim_graph, tree); 113static inline void elim_graph_add_edge (elim_graph, int, int); 114static inline int elim_graph_remove_succ_edge (elim_graph, int); 115 116static inline void eliminate_name (elim_graph, tree); 117static void eliminate_build (elim_graph, basic_block); 118static void elim_forward (elim_graph, int); 119static int elim_unvisited_predecessor (elim_graph, int); 120static void elim_backward (elim_graph, int); 121static void elim_create (elim_graph, int); 122static void eliminate_phi (edge, elim_graph); 123static tree_live_info_p coalesce_ssa_name (var_map, int); 124static void assign_vars (var_map); 125static bool replace_use_variable (var_map, use_operand_p, tree *); 126static bool replace_def_variable (var_map, def_operand_p, tree *); 127static void eliminate_virtual_phis (void); 128static void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p); 129static void print_exprs (FILE *, const char *, tree, const char *, tree, 130 const char *); 131static 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 138static tree 139create_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 187static void 188insert_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 217static elim_graph 218new_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 235static inline void 236clear_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 245static inline void 246delete_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 259static inline int 260elim_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 268static inline void 269elim_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 283static inline void 284elim_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 294static inline int 295elim_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) \ 316do { \ 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) \ 335do { \ 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 351static inline void 352eliminate_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 361static void 362eliminate_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 410static void 411elim_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 426static int 427elim_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 440static void 441elim_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 460static void 461elim_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 495static void 496eliminate_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 548static void 549print_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 563static void 564print_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 578static void 579coalesce_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 679static void 680coalesce_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 721static void 722coalesce_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 748static void 749coalesce_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 812static tree_live_info_p 813coalesce_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 936static void 937assign_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 1022static inline bool 1023replace_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 1058static inline bool 1059replace_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 1091static void 1092eliminate_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 1135static void 1136coalesce_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 1288typedef 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 1297typedef 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 1314static temp_expr_table_p new_temp_expr_table (var_map); 1315static tree *free_temp_expr_table (temp_expr_table_p); 1316static inline value_expr_p new_value_expr (temp_expr_table_p); 1317static inline void free_value_expr (temp_expr_table_p, value_expr_p); 1318static inline value_expr_p find_value_in_list (value_expr_p, int, 1319 value_expr_p *); 1320static inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int); 1321static inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 1322 value_expr_p); 1323static value_expr_p remove_value_from_list (value_expr_p *, int); 1324static void add_dependence (temp_expr_table_p, int, tree); 1325static bool check_replaceable (temp_expr_table_p, tree); 1326static void finish_expr (temp_expr_table_p, int, bool); 1327static void mark_replaceable (temp_expr_table_p, tree); 1328static inline void kill_expr (temp_expr_table_p, int, bool); 1329static inline void kill_virtual_exprs (temp_expr_table_p, bool); 1330static void find_replaceable_in_bb (temp_expr_table_p, basic_block); 1331static tree *find_replaceable_exprs (var_map); 1332static void dump_replaceable_exprs (FILE *, tree *); 1333 1334 1335/* Create a new TER table for MAP. */ 1336 1337static temp_expr_table_p 1338new_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 1365static tree * 1366free_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 1406static inline value_expr_p 1407new_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 1424static inline void 1425free_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 1436static inline value_expr_p 1437find_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 1456static inline void 1457add_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 1474static inline void 1475add_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 1490static value_expr_p 1491remove_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 1512static void 1513add_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 1551static bool 1552check_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 1630static void 1631finish_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 1671static void 1672mark_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 1697static inline void 1698kill_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 1714static inline void 1715kill_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 1724static void 1725find_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 1806static tree * 1807find_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 1833static void 1834dump_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 1860static void 1861rewrite_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 1986DEF_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.. */ 1990static VEC(edge,heap) *edge_leader; 1991static VEC(tree,heap) *stmt_list; 1992static bitmap leader_has_match = NULL; 1993static 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. */ 1998static bool 1999same_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. */ 2006static inline bool 2007identical_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 2032static inline bool 2033identical_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 2059static void 2060init_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 2070static void 2071fini_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 2082static void 2083analyze_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 2275static void 2276perform_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 2340static void 2341remove_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 2430static void 2431insert_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 2513static unsigned int 2514rewrite_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 2562struct 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}; 2582