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