1169689Skan/* Convert a program in SSA form into Normal form. 2169689Skan Copyright (C) 2004, 2005 Free Software Foundation, Inc. 3169689Skan Contributed by Andrew Macleod <amacleod@redhat.com> 4169689Skan 5169689SkanThis file is part of GCC. 6169689Skan 7169689SkanGCC is free software; you can redistribute it and/or modify 8169689Skanit under the terms of the GNU General Public License as published by 9169689Skanthe Free Software Foundation; either version 2, or (at your option) 10169689Skanany later version. 11169689Skan 12169689SkanGCC is distributed in the hope that it will be useful, 13169689Skanbut WITHOUT ANY WARRANTY; without even the implied warranty of 14169689SkanMERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15169689SkanGNU General Public License for more details. 16169689Skan 17169689SkanYou should have received a copy of the GNU General Public License 18169689Skanalong with GCC; see the file COPYING. If not, write to 19169689Skanthe Free Software Foundation, 51 Franklin Street, Fifth Floor, 20169689SkanBoston, MA 02110-1301, USA. */ 21169689Skan 22169689Skan#include "config.h" 23169689Skan#include "system.h" 24169689Skan#include "coretypes.h" 25169689Skan#include "tm.h" 26169689Skan#include "tree.h" 27169689Skan#include "flags.h" 28169689Skan#include "rtl.h" 29169689Skan#include "tm_p.h" 30169689Skan#include "ggc.h" 31169689Skan#include "langhooks.h" 32169689Skan#include "hard-reg-set.h" 33169689Skan#include "basic-block.h" 34169689Skan#include "output.h" 35169689Skan#include "expr.h" 36169689Skan#include "function.h" 37169689Skan#include "diagnostic.h" 38169689Skan#include "bitmap.h" 39169689Skan#include "tree-flow.h" 40169689Skan#include "tree-gimple.h" 41169689Skan#include "tree-inline.h" 42169689Skan#include "varray.h" 43169689Skan#include "timevar.h" 44169689Skan#include "hashtab.h" 45169689Skan#include "tree-dump.h" 46169689Skan#include "tree-ssa-live.h" 47169689Skan#include "tree-pass.h" 48169689Skan#include "toplev.h" 49169689Skan#include "vecprim.h" 50169689Skan 51169689Skan/* Flags to pass to remove_ssa_form. */ 52169689Skan 53169689Skan#define SSANORM_PERFORM_TER 0x1 54169689Skan#define SSANORM_COMBINE_TEMPS 0x2 55169689Skan#define SSANORM_COALESCE_PARTITIONS 0x4 56169689Skan 57169689Skan/* Used to hold all the components required to do SSA PHI elimination. 58169689Skan The node and pred/succ list is a simple linear list of nodes and 59169689Skan edges represented as pairs of nodes. 60169689Skan 61169689Skan The predecessor and successor list: Nodes are entered in pairs, where 62169689Skan [0] ->PRED, [1]->SUCC. All the even indexes in the array represent 63169689Skan predecessors, all the odd elements are successors. 64169689Skan 65169689Skan Rationale: 66169689Skan When implemented as bitmaps, very large programs SSA->Normal times were 67169689Skan being dominated by clearing the interference graph. 68169689Skan 69169689Skan Typically this list of edges is extremely small since it only includes 70169689Skan PHI results and uses from a single edge which have not coalesced with 71169689Skan each other. This means that no virtual PHI nodes are included, and 72169689Skan empirical evidence suggests that the number of edges rarely exceed 73169689Skan 3, and in a bootstrap of GCC, the maximum size encountered was 7. 74169689Skan This also limits the number of possible nodes that are involved to 75169689Skan rarely more than 6, and in the bootstrap of gcc, the maximum number 76169689Skan of nodes encountered was 12. */ 77169689Skan 78169689Skantypedef struct _elim_graph { 79169689Skan /* Size of the elimination vectors. */ 80169689Skan int size; 81169689Skan 82169689Skan /* List of nodes in the elimination graph. */ 83169689Skan VEC(tree,heap) *nodes; 84169689Skan 85169689Skan /* The predecessor and successor edge list. */ 86169689Skan VEC(int,heap) *edge_list; 87169689Skan 88169689Skan /* Visited vector. */ 89169689Skan sbitmap visited; 90169689Skan 91169689Skan /* Stack for visited nodes. */ 92169689Skan VEC(int,heap) *stack; 93169689Skan 94169689Skan /* The variable partition map. */ 95169689Skan var_map map; 96169689Skan 97169689Skan /* Edge being eliminated by this graph. */ 98169689Skan edge e; 99169689Skan 100169689Skan /* List of constant copies to emit. These are pushed on in pairs. */ 101169689Skan VEC(tree,heap) *const_copies; 102169689Skan} *elim_graph; 103169689Skan 104169689Skan 105169689Skan/* Local functions. */ 106169689Skanstatic tree create_temp (tree); 107169689Skanstatic void insert_copy_on_edge (edge, tree, tree); 108169689Skanstatic elim_graph new_elim_graph (int); 109169689Skanstatic inline void delete_elim_graph (elim_graph); 110169689Skanstatic inline void clear_elim_graph (elim_graph); 111169689Skanstatic inline int elim_graph_size (elim_graph); 112169689Skanstatic inline void elim_graph_add_node (elim_graph, tree); 113169689Skanstatic inline void elim_graph_add_edge (elim_graph, int, int); 114169689Skanstatic inline int elim_graph_remove_succ_edge (elim_graph, int); 115169689Skan 116169689Skanstatic inline void eliminate_name (elim_graph, tree); 117169689Skanstatic void eliminate_build (elim_graph, basic_block); 118169689Skanstatic void elim_forward (elim_graph, int); 119169689Skanstatic int elim_unvisited_predecessor (elim_graph, int); 120169689Skanstatic void elim_backward (elim_graph, int); 121169689Skanstatic void elim_create (elim_graph, int); 122169689Skanstatic void eliminate_phi (edge, elim_graph); 123169689Skanstatic tree_live_info_p coalesce_ssa_name (var_map, int); 124169689Skanstatic void assign_vars (var_map); 125169689Skanstatic bool replace_use_variable (var_map, use_operand_p, tree *); 126169689Skanstatic bool replace_def_variable (var_map, def_operand_p, tree *); 127169689Skanstatic void eliminate_virtual_phis (void); 128169689Skanstatic void coalesce_abnormal_edges (var_map, conflict_graph, root_var_p); 129169689Skanstatic void print_exprs (FILE *, const char *, tree, const char *, tree, 130169689Skan const char *); 131169689Skanstatic void print_exprs_edge (FILE *, edge, const char *, tree, const char *, 132169689Skan tree); 133169689Skan 134169689Skan 135169689Skan/* Create a temporary variable based on the type of variable T. Use T's name 136169689Skan as the prefix. */ 137169689Skan 138169689Skanstatic tree 139169689Skancreate_temp (tree t) 140169689Skan{ 141169689Skan tree tmp; 142169689Skan const char *name = NULL; 143169689Skan tree type; 144169689Skan 145169689Skan if (TREE_CODE (t) == SSA_NAME) 146169689Skan t = SSA_NAME_VAR (t); 147169689Skan 148169689Skan gcc_assert (TREE_CODE (t) == VAR_DECL || TREE_CODE (t) == PARM_DECL); 149169689Skan 150169689Skan type = TREE_TYPE (t); 151169689Skan tmp = DECL_NAME (t); 152169689Skan if (tmp) 153169689Skan name = IDENTIFIER_POINTER (tmp); 154169689Skan 155169689Skan if (name == NULL) 156169689Skan name = "temp"; 157169689Skan tmp = create_tmp_var (type, name); 158169689Skan 159169689Skan if (DECL_DEBUG_EXPR_IS_FROM (t) && DECL_DEBUG_EXPR (t)) 160169689Skan { 161169689Skan SET_DECL_DEBUG_EXPR (tmp, DECL_DEBUG_EXPR (t)); 162169689Skan DECL_DEBUG_EXPR_IS_FROM (tmp) = 1; 163169689Skan } 164169689Skan else if (!DECL_IGNORED_P (t)) 165169689Skan { 166169689Skan SET_DECL_DEBUG_EXPR (tmp, t); 167169689Skan DECL_DEBUG_EXPR_IS_FROM (tmp) = 1; 168169689Skan } 169169689Skan DECL_ARTIFICIAL (tmp) = DECL_ARTIFICIAL (t); 170169689Skan DECL_IGNORED_P (tmp) = DECL_IGNORED_P (t); 171169689Skan add_referenced_var (tmp); 172169689Skan 173169689Skan /* add_referenced_var will create the annotation and set up some 174169689Skan of the flags in the annotation. However, some flags we need to 175169689Skan inherit from our original variable. */ 176169689Skan var_ann (tmp)->symbol_mem_tag = var_ann (t)->symbol_mem_tag; 177169689Skan if (is_call_clobbered (t)) 178169689Skan mark_call_clobbered (tmp, var_ann (t)->escape_mask); 179169689Skan 180169689Skan return tmp; 181169689Skan} 182169689Skan 183169689Skan 184169689Skan/* This helper function fill insert a copy from a constant or variable SRC to 185169689Skan variable DEST on edge E. */ 186169689Skan 187169689Skanstatic void 188169689Skaninsert_copy_on_edge (edge e, tree dest, tree src) 189169689Skan{ 190169689Skan tree copy; 191169689Skan 192169689Skan copy = build2 (MODIFY_EXPR, TREE_TYPE (dest), dest, src); 193169689Skan set_is_used (dest); 194169689Skan 195169689Skan if (TREE_CODE (src) == ADDR_EXPR) 196169689Skan src = TREE_OPERAND (src, 0); 197169689Skan if (TREE_CODE (src) == VAR_DECL || TREE_CODE (src) == PARM_DECL) 198169689Skan set_is_used (src); 199169689Skan 200169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 201169689Skan { 202169689Skan fprintf (dump_file, 203169689Skan "Inserting a copy on edge BB%d->BB%d :", 204169689Skan e->src->index, 205169689Skan e->dest->index); 206169689Skan print_generic_expr (dump_file, copy, dump_flags); 207169689Skan fprintf (dump_file, "\n"); 208169689Skan } 209169689Skan 210169689Skan bsi_insert_on_edge (e, copy); 211169689Skan} 212169689Skan 213169689Skan 214169689Skan/* Create an elimination graph with SIZE nodes and associated data 215169689Skan structures. */ 216169689Skan 217169689Skanstatic elim_graph 218169689Skannew_elim_graph (int size) 219169689Skan{ 220169689Skan elim_graph g = (elim_graph) xmalloc (sizeof (struct _elim_graph)); 221169689Skan 222169689Skan g->nodes = VEC_alloc (tree, heap, 30); 223169689Skan g->const_copies = VEC_alloc (tree, heap, 20); 224169689Skan g->edge_list = VEC_alloc (int, heap, 20); 225169689Skan g->stack = VEC_alloc (int, heap, 30); 226169689Skan 227169689Skan g->visited = sbitmap_alloc (size); 228169689Skan 229169689Skan return g; 230169689Skan} 231169689Skan 232169689Skan 233169689Skan/* Empty elimination graph G. */ 234169689Skan 235169689Skanstatic inline void 236169689Skanclear_elim_graph (elim_graph g) 237169689Skan{ 238169689Skan VEC_truncate (tree, g->nodes, 0); 239169689Skan VEC_truncate (int, g->edge_list, 0); 240169689Skan} 241169689Skan 242169689Skan 243169689Skan/* Delete elimination graph G. */ 244169689Skan 245169689Skanstatic inline void 246169689Skandelete_elim_graph (elim_graph g) 247169689Skan{ 248169689Skan sbitmap_free (g->visited); 249169689Skan VEC_free (int, heap, g->stack); 250169689Skan VEC_free (int, heap, g->edge_list); 251169689Skan VEC_free (tree, heap, g->const_copies); 252169689Skan VEC_free (tree, heap, g->nodes); 253169689Skan free (g); 254169689Skan} 255169689Skan 256169689Skan 257169689Skan/* Return the number of nodes in graph G. */ 258169689Skan 259169689Skanstatic inline int 260169689Skanelim_graph_size (elim_graph g) 261169689Skan{ 262169689Skan return VEC_length (tree, g->nodes); 263169689Skan} 264169689Skan 265169689Skan 266169689Skan/* Add NODE to graph G, if it doesn't exist already. */ 267169689Skan 268169689Skanstatic inline void 269169689Skanelim_graph_add_node (elim_graph g, tree node) 270169689Skan{ 271169689Skan int x; 272169689Skan tree t; 273169689Skan 274169689Skan for (x = 0; VEC_iterate (tree, g->nodes, x, t); x++) 275169689Skan if (t == node) 276169689Skan return; 277169689Skan VEC_safe_push (tree, heap, g->nodes, node); 278169689Skan} 279169689Skan 280169689Skan 281169689Skan/* Add the edge PRED->SUCC to graph G. */ 282169689Skan 283169689Skanstatic inline void 284169689Skanelim_graph_add_edge (elim_graph g, int pred, int succ) 285169689Skan{ 286169689Skan VEC_safe_push (int, heap, g->edge_list, pred); 287169689Skan VEC_safe_push (int, heap, g->edge_list, succ); 288169689Skan} 289169689Skan 290169689Skan 291169689Skan/* Remove an edge from graph G for which NODE is the predecessor, and 292169689Skan return the successor node. -1 is returned if there is no such edge. */ 293169689Skan 294169689Skanstatic inline int 295169689Skanelim_graph_remove_succ_edge (elim_graph g, int node) 296169689Skan{ 297169689Skan int y; 298169689Skan unsigned x; 299169689Skan for (x = 0; x < VEC_length (int, g->edge_list); x += 2) 300169689Skan if (VEC_index (int, g->edge_list, x) == node) 301169689Skan { 302169689Skan VEC_replace (int, g->edge_list, x, -1); 303169689Skan y = VEC_index (int, g->edge_list, x + 1); 304169689Skan VEC_replace (int, g->edge_list, x + 1, -1); 305169689Skan return y; 306169689Skan } 307169689Skan return -1; 308169689Skan} 309169689Skan 310169689Skan 311169689Skan/* Find all the nodes in GRAPH which are successors to NODE in the 312169689Skan edge list. VAR will hold the partition number found. CODE is the 313169689Skan code fragment executed for every node found. */ 314169689Skan 315169689Skan#define FOR_EACH_ELIM_GRAPH_SUCC(GRAPH, NODE, VAR, CODE) \ 316169689Skando { \ 317169689Skan unsigned x_; \ 318169689Skan int y_; \ 319169689Skan for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \ 320169689Skan { \ 321169689Skan y_ = VEC_index (int, (GRAPH)->edge_list, x_); \ 322169689Skan if (y_ != (NODE)) \ 323169689Skan continue; \ 324169689Skan (VAR) = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \ 325169689Skan CODE; \ 326169689Skan } \ 327169689Skan} while (0) 328169689Skan 329169689Skan 330169689Skan/* Find all the nodes which are predecessors of NODE in the edge list for 331169689Skan GRAPH. VAR will hold the partition number found. CODE is the 332169689Skan code fragment executed for every node found. */ 333169689Skan 334169689Skan#define FOR_EACH_ELIM_GRAPH_PRED(GRAPH, NODE, VAR, CODE) \ 335169689Skando { \ 336169689Skan unsigned x_; \ 337169689Skan int y_; \ 338169689Skan for (x_ = 0; x_ < VEC_length (int, (GRAPH)->edge_list); x_ += 2) \ 339169689Skan { \ 340169689Skan y_ = VEC_index (int, (GRAPH)->edge_list, x_ + 1); \ 341169689Skan if (y_ != (NODE)) \ 342169689Skan continue; \ 343169689Skan (VAR) = VEC_index (int, (GRAPH)->edge_list, x_); \ 344169689Skan CODE; \ 345169689Skan } \ 346169689Skan} while (0) 347169689Skan 348169689Skan 349169689Skan/* Add T to elimination graph G. */ 350169689Skan 351169689Skanstatic inline void 352169689Skaneliminate_name (elim_graph g, tree T) 353169689Skan{ 354169689Skan elim_graph_add_node (g, T); 355169689Skan} 356169689Skan 357169689Skan 358169689Skan/* Build elimination graph G for basic block BB on incoming PHI edge 359169689Skan G->e. */ 360169689Skan 361169689Skanstatic void 362169689Skaneliminate_build (elim_graph g, basic_block B) 363169689Skan{ 364169689Skan tree phi; 365169689Skan tree T0, Ti; 366169689Skan int p0, pi; 367169689Skan 368169689Skan clear_elim_graph (g); 369169689Skan 370169689Skan for (phi = phi_nodes (B); phi; phi = PHI_CHAIN (phi)) 371169689Skan { 372169689Skan T0 = var_to_partition_to_var (g->map, PHI_RESULT (phi)); 373169689Skan 374169689Skan /* Ignore results which are not in partitions. */ 375169689Skan if (T0 == NULL_TREE) 376169689Skan continue; 377169689Skan 378169689Skan Ti = PHI_ARG_DEF (phi, g->e->dest_idx); 379169689Skan 380169689Skan /* If this argument is a constant, or a SSA_NAME which is being 381169689Skan left in SSA form, just queue a copy to be emitted on this 382169689Skan edge. */ 383169689Skan if (!phi_ssa_name_p (Ti) 384169689Skan || (TREE_CODE (Ti) == SSA_NAME 385169689Skan && var_to_partition (g->map, Ti) == NO_PARTITION)) 386169689Skan { 387169689Skan /* Save constant copies until all other copies have been emitted 388169689Skan on this edge. */ 389169689Skan VEC_safe_push (tree, heap, g->const_copies, T0); 390169689Skan VEC_safe_push (tree, heap, g->const_copies, Ti); 391169689Skan } 392169689Skan else 393169689Skan { 394169689Skan Ti = var_to_partition_to_var (g->map, Ti); 395169689Skan if (T0 != Ti) 396169689Skan { 397169689Skan eliminate_name (g, T0); 398169689Skan eliminate_name (g, Ti); 399169689Skan p0 = var_to_partition (g->map, T0); 400169689Skan pi = var_to_partition (g->map, Ti); 401169689Skan elim_graph_add_edge (g, p0, pi); 402169689Skan } 403169689Skan } 404169689Skan } 405169689Skan} 406169689Skan 407169689Skan 408169689Skan/* Push successors of T onto the elimination stack for G. */ 409169689Skan 410169689Skanstatic void 411169689Skanelim_forward (elim_graph g, int T) 412169689Skan{ 413169689Skan int S; 414169689Skan SET_BIT (g->visited, T); 415169689Skan FOR_EACH_ELIM_GRAPH_SUCC (g, T, S, 416169689Skan { 417169689Skan if (!TEST_BIT (g->visited, S)) 418169689Skan elim_forward (g, S); 419169689Skan }); 420169689Skan VEC_safe_push (int, heap, g->stack, T); 421169689Skan} 422169689Skan 423169689Skan 424169689Skan/* Return 1 if there unvisited predecessors of T in graph G. */ 425169689Skan 426169689Skanstatic int 427169689Skanelim_unvisited_predecessor (elim_graph g, int T) 428169689Skan{ 429169689Skan int P; 430169689Skan FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 431169689Skan { 432169689Skan if (!TEST_BIT (g->visited, P)) 433169689Skan return 1; 434169689Skan }); 435169689Skan return 0; 436169689Skan} 437169689Skan 438169689Skan/* Process predecessors first, and insert a copy. */ 439169689Skan 440169689Skanstatic void 441169689Skanelim_backward (elim_graph g, int T) 442169689Skan{ 443169689Skan int P; 444169689Skan SET_BIT (g->visited, T); 445169689Skan FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 446169689Skan { 447169689Skan if (!TEST_BIT (g->visited, P)) 448169689Skan { 449169689Skan elim_backward (g, P); 450169689Skan insert_copy_on_edge (g->e, 451169689Skan partition_to_var (g->map, P), 452169689Skan partition_to_var (g->map, T)); 453169689Skan } 454169689Skan }); 455169689Skan} 456169689Skan 457169689Skan/* Insert required copies for T in graph G. Check for a strongly connected 458169689Skan region, and create a temporary to break the cycle if one is found. */ 459169689Skan 460169689Skanstatic void 461169689Skanelim_create (elim_graph g, int T) 462169689Skan{ 463169689Skan tree U; 464169689Skan int P, S; 465169689Skan 466169689Skan if (elim_unvisited_predecessor (g, T)) 467169689Skan { 468169689Skan U = create_temp (partition_to_var (g->map, T)); 469169689Skan insert_copy_on_edge (g->e, U, partition_to_var (g->map, T)); 470169689Skan FOR_EACH_ELIM_GRAPH_PRED (g, T, P, 471169689Skan { 472169689Skan if (!TEST_BIT (g->visited, P)) 473169689Skan { 474169689Skan elim_backward (g, P); 475169689Skan insert_copy_on_edge (g->e, partition_to_var (g->map, P), U); 476169689Skan } 477169689Skan }); 478169689Skan } 479169689Skan else 480169689Skan { 481169689Skan S = elim_graph_remove_succ_edge (g, T); 482169689Skan if (S != -1) 483169689Skan { 484169689Skan SET_BIT (g->visited, T); 485169689Skan insert_copy_on_edge (g->e, 486169689Skan partition_to_var (g->map, T), 487169689Skan partition_to_var (g->map, S)); 488169689Skan } 489169689Skan } 490169689Skan 491169689Skan} 492169689Skan 493169689Skan/* Eliminate all the phi nodes on edge E in graph G. */ 494169689Skan 495169689Skanstatic void 496169689Skaneliminate_phi (edge e, elim_graph g) 497169689Skan{ 498169689Skan int x; 499169689Skan basic_block B = e->dest; 500169689Skan 501169689Skan gcc_assert (VEC_length (tree, g->const_copies) == 0); 502169689Skan 503169689Skan /* Abnormal edges already have everything coalesced. */ 504169689Skan if (e->flags & EDGE_ABNORMAL) 505169689Skan return; 506169689Skan 507169689Skan g->e = e; 508169689Skan 509169689Skan eliminate_build (g, B); 510169689Skan 511169689Skan if (elim_graph_size (g) != 0) 512169689Skan { 513169689Skan tree var; 514169689Skan 515169689Skan sbitmap_zero (g->visited); 516169689Skan VEC_truncate (int, g->stack, 0); 517169689Skan 518169689Skan for (x = 0; VEC_iterate (tree, g->nodes, x, var); x++) 519169689Skan { 520169689Skan int p = var_to_partition (g->map, var); 521169689Skan if (!TEST_BIT (g->visited, p)) 522169689Skan elim_forward (g, p); 523169689Skan } 524169689Skan 525169689Skan sbitmap_zero (g->visited); 526169689Skan while (VEC_length (int, g->stack) > 0) 527169689Skan { 528169689Skan x = VEC_pop (int, g->stack); 529169689Skan if (!TEST_BIT (g->visited, x)) 530169689Skan elim_create (g, x); 531169689Skan } 532169689Skan } 533169689Skan 534169689Skan /* If there are any pending constant copies, issue them now. */ 535169689Skan while (VEC_length (tree, g->const_copies) > 0) 536169689Skan { 537169689Skan tree src, dest; 538169689Skan src = VEC_pop (tree, g->const_copies); 539169689Skan dest = VEC_pop (tree, g->const_copies); 540169689Skan insert_copy_on_edge (e, dest, src); 541169689Skan } 542169689Skan} 543169689Skan 544169689Skan 545169689Skan/* Shortcut routine to print messages to file F of the form: 546169689Skan "STR1 EXPR1 STR2 EXPR2 STR3." */ 547169689Skan 548169689Skanstatic void 549169689Skanprint_exprs (FILE *f, const char *str1, tree expr1, const char *str2, 550169689Skan tree expr2, const char *str3) 551169689Skan{ 552169689Skan fprintf (f, "%s", str1); 553169689Skan print_generic_expr (f, expr1, TDF_SLIM); 554169689Skan fprintf (f, "%s", str2); 555169689Skan print_generic_expr (f, expr2, TDF_SLIM); 556169689Skan fprintf (f, "%s", str3); 557169689Skan} 558169689Skan 559169689Skan 560169689Skan/* Shortcut routine to print abnormal edge messages to file F of the form: 561169689Skan "STR1 EXPR1 STR2 EXPR2 across edge E. */ 562169689Skan 563169689Skanstatic void 564169689Skanprint_exprs_edge (FILE *f, edge e, const char *str1, tree expr1, 565169689Skan const char *str2, tree expr2) 566169689Skan{ 567169689Skan print_exprs (f, str1, expr1, str2, expr2, " across an abnormal edge"); 568169689Skan fprintf (f, " from BB%d->BB%d\n", e->src->index, 569169689Skan e->dest->index); 570169689Skan} 571169689Skan 572169689Skan 573169689Skan/* Coalesce partitions in MAP which are live across abnormal edges in GRAPH. 574169689Skan RV is the root variable groupings of the partitions in MAP. Since code 575169689Skan cannot be inserted on these edges, failure to coalesce something across 576169689Skan an abnormal edge is an error. */ 577169689Skan 578169689Skanstatic void 579169689Skancoalesce_abnormal_edges (var_map map, conflict_graph graph, root_var_p rv) 580169689Skan{ 581169689Skan basic_block bb; 582169689Skan edge e; 583169689Skan tree phi, var, tmp; 584169689Skan int x, y, z; 585169689Skan edge_iterator ei; 586169689Skan 587169689Skan /* Code cannot be inserted on abnormal edges. Look for all abnormal 588169689Skan edges, and coalesce any PHI results with their arguments across 589169689Skan that edge. */ 590169689Skan 591169689Skan FOR_EACH_BB (bb) 592169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 593169689Skan if (e->dest != EXIT_BLOCK_PTR && e->flags & EDGE_ABNORMAL) 594169689Skan for (phi = phi_nodes (e->dest); phi; phi = PHI_CHAIN (phi)) 595169689Skan { 596169689Skan /* Visit each PHI on the destination side of this abnormal 597169689Skan edge, and attempt to coalesce the argument with the result. */ 598169689Skan var = PHI_RESULT (phi); 599169689Skan x = var_to_partition (map, var); 600169689Skan 601169689Skan /* Ignore results which are not relevant. */ 602169689Skan if (x == NO_PARTITION) 603169689Skan continue; 604169689Skan 605169689Skan tmp = PHI_ARG_DEF (phi, e->dest_idx); 606169689Skan#ifdef ENABLE_CHECKING 607169689Skan if (!phi_ssa_name_p (tmp)) 608169689Skan { 609169689Skan print_exprs_edge (stderr, e, 610169689Skan "\nConstant argument in PHI. Can't insert :", 611169689Skan var, " = ", tmp); 612169689Skan internal_error ("SSA corruption"); 613169689Skan } 614169689Skan#else 615169689Skan gcc_assert (phi_ssa_name_p (tmp)); 616169689Skan#endif 617169689Skan y = var_to_partition (map, tmp); 618169689Skan gcc_assert (x != NO_PARTITION); 619169689Skan gcc_assert (y != NO_PARTITION); 620169689Skan#ifdef ENABLE_CHECKING 621169689Skan if (root_var_find (rv, x) != root_var_find (rv, y)) 622169689Skan { 623169689Skan print_exprs_edge (stderr, e, "\nDifferent root vars: ", 624169689Skan root_var (rv, root_var_find (rv, x)), 625169689Skan " and ", 626169689Skan root_var (rv, root_var_find (rv, y))); 627169689Skan internal_error ("SSA corruption"); 628169689Skan } 629169689Skan#else 630169689Skan gcc_assert (root_var_find (rv, x) == root_var_find (rv, y)); 631169689Skan#endif 632169689Skan 633169689Skan if (x != y) 634169689Skan { 635169689Skan#ifdef ENABLE_CHECKING 636169689Skan if (conflict_graph_conflict_p (graph, x, y)) 637169689Skan { 638169689Skan print_exprs_edge (stderr, e, "\n Conflict ", 639169689Skan partition_to_var (map, x), 640169689Skan " and ", partition_to_var (map, y)); 641169689Skan internal_error ("SSA corruption"); 642169689Skan } 643169689Skan#else 644169689Skan gcc_assert (!conflict_graph_conflict_p (graph, x, y)); 645169689Skan#endif 646169689Skan 647169689Skan /* Now map the partitions back to their real variables. */ 648169689Skan var = partition_to_var (map, x); 649169689Skan tmp = partition_to_var (map, y); 650169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 651169689Skan { 652169689Skan print_exprs_edge (dump_file, e, 653169689Skan "ABNORMAL: Coalescing ", 654169689Skan var, " and ", tmp); 655169689Skan } 656169689Skan z = var_union (map, var, tmp); 657169689Skan#ifdef ENABLE_CHECKING 658169689Skan if (z == NO_PARTITION) 659169689Skan { 660169689Skan print_exprs_edge (stderr, e, "\nUnable to coalesce", 661169689Skan partition_to_var (map, x), " and ", 662169689Skan partition_to_var (map, y)); 663169689Skan internal_error ("SSA corruption"); 664169689Skan } 665169689Skan#else 666169689Skan gcc_assert (z != NO_PARTITION); 667169689Skan#endif 668169689Skan gcc_assert (z == x || z == y); 669169689Skan if (z == x) 670169689Skan conflict_graph_merge_regs (graph, x, y); 671169689Skan else 672169689Skan conflict_graph_merge_regs (graph, y, x); 673169689Skan } 674169689Skan } 675169689Skan} 676169689Skan 677169689Skan/* Coalesce potential copies via PHI arguments. */ 678169689Skan 679169689Skanstatic void 680169689Skancoalesce_phi_operands (var_map map, coalesce_list_p cl) 681169689Skan{ 682169689Skan basic_block bb; 683169689Skan tree phi; 684169689Skan 685169689Skan FOR_EACH_BB (bb) 686169689Skan { 687169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 688169689Skan { 689169689Skan tree res = PHI_RESULT (phi); 690169689Skan int p = var_to_partition (map, res); 691169689Skan int x; 692169689Skan 693169689Skan if (p == NO_PARTITION) 694169689Skan continue; 695169689Skan 696169689Skan for (x = 0; x < PHI_NUM_ARGS (phi); x++) 697169689Skan { 698169689Skan tree arg = PHI_ARG_DEF (phi, x); 699169689Skan int p2; 700169689Skan 701169689Skan if (TREE_CODE (arg) != SSA_NAME) 702169689Skan continue; 703169689Skan if (SSA_NAME_VAR (res) != SSA_NAME_VAR (arg)) 704169689Skan continue; 705169689Skan p2 = var_to_partition (map, PHI_ARG_DEF (phi, x)); 706169689Skan if (p2 != NO_PARTITION) 707169689Skan { 708169689Skan edge e = PHI_ARG_EDGE (phi, x); 709169689Skan add_coalesce (cl, p, p2, 710169689Skan coalesce_cost (EDGE_FREQUENCY (e), 711169689Skan maybe_hot_bb_p (bb), 712169689Skan EDGE_CRITICAL_P (e))); 713169689Skan } 714169689Skan } 715169689Skan } 716169689Skan } 717169689Skan} 718169689Skan 719169689Skan/* Coalesce all the result decls together. */ 720169689Skan 721169689Skanstatic void 722169689Skancoalesce_result_decls (var_map map, coalesce_list_p cl) 723169689Skan{ 724169689Skan unsigned int i, x; 725169689Skan tree var = NULL; 726169689Skan 727169689Skan for (i = x = 0; x < num_var_partitions (map); x++) 728169689Skan { 729169689Skan tree p = partition_to_var (map, x); 730169689Skan if (TREE_CODE (SSA_NAME_VAR (p)) == RESULT_DECL) 731169689Skan { 732169689Skan if (var == NULL_TREE) 733169689Skan { 734169689Skan var = p; 735169689Skan i = x; 736169689Skan } 737169689Skan else 738169689Skan add_coalesce (cl, i, x, 739169689Skan coalesce_cost (EXIT_BLOCK_PTR->frequency, 740169689Skan maybe_hot_bb_p (EXIT_BLOCK_PTR), 741169689Skan false)); 742169689Skan } 743169689Skan } 744169689Skan} 745169689Skan 746169689Skan/* Coalesce matching constraints in asms. */ 747169689Skan 748169689Skanstatic void 749169689Skancoalesce_asm_operands (var_map map, coalesce_list_p cl) 750169689Skan{ 751169689Skan basic_block bb; 752169689Skan 753169689Skan FOR_EACH_BB (bb) 754169689Skan { 755169689Skan block_stmt_iterator bsi; 756169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 757169689Skan { 758169689Skan tree stmt = bsi_stmt (bsi); 759169689Skan unsigned long noutputs, i; 760169689Skan tree *outputs, link; 761169689Skan 762169689Skan if (TREE_CODE (stmt) != ASM_EXPR) 763169689Skan continue; 764169689Skan 765169689Skan noutputs = list_length (ASM_OUTPUTS (stmt)); 766169689Skan outputs = (tree *) alloca (noutputs * sizeof (tree)); 767169689Skan for (i = 0, link = ASM_OUTPUTS (stmt); link; 768169689Skan ++i, link = TREE_CHAIN (link)) 769169689Skan outputs[i] = TREE_VALUE (link); 770169689Skan 771169689Skan for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) 772169689Skan { 773169689Skan const char *constraint 774169689Skan = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); 775169689Skan tree input = TREE_VALUE (link); 776169689Skan char *end; 777169689Skan unsigned long match; 778169689Skan int p1, p2; 779169689Skan 780169689Skan if (TREE_CODE (input) != SSA_NAME && !DECL_P (input)) 781169689Skan continue; 782169689Skan 783169689Skan match = strtoul (constraint, &end, 10); 784169689Skan if (match >= noutputs || end == constraint) 785169689Skan continue; 786169689Skan 787169689Skan if (TREE_CODE (outputs[match]) != SSA_NAME 788169689Skan && !DECL_P (outputs[match])) 789169689Skan continue; 790169689Skan 791169689Skan p1 = var_to_partition (map, outputs[match]); 792169689Skan if (p1 == NO_PARTITION) 793169689Skan continue; 794169689Skan p2 = var_to_partition (map, input); 795169689Skan if (p2 == NO_PARTITION) 796169689Skan continue; 797169689Skan 798169689Skan add_coalesce (cl, p1, p2, coalesce_cost (REG_BR_PROB_BASE, 799169689Skan maybe_hot_bb_p (bb), 800169689Skan false)); 801169689Skan } 802169689Skan } 803169689Skan } 804169689Skan} 805169689Skan 806169689Skan/* Reduce the number of live ranges in MAP. Live range information is 807169689Skan returned if FLAGS indicates that we are combining temporaries, otherwise 808169689Skan NULL is returned. The only partitions which are associated with actual 809169689Skan variables at this point are those which are forced to be coalesced for 810169689Skan various reason. (live on entry, live across abnormal edges, etc.). */ 811169689Skan 812169689Skanstatic tree_live_info_p 813169689Skancoalesce_ssa_name (var_map map, int flags) 814169689Skan{ 815169689Skan unsigned num, x; 816169689Skan sbitmap live; 817169689Skan root_var_p rv; 818169689Skan tree_live_info_p liveinfo; 819169689Skan conflict_graph graph; 820169689Skan coalesce_list_p cl = NULL; 821169689Skan sbitmap_iterator sbi; 822169689Skan 823169689Skan if (num_var_partitions (map) <= 1) 824169689Skan return NULL; 825169689Skan 826169689Skan liveinfo = calculate_live_on_entry (map); 827169689Skan calculate_live_on_exit (liveinfo); 828169689Skan rv = root_var_init (map); 829169689Skan 830169689Skan /* Remove single element variable from the list. */ 831169689Skan root_var_compact (rv); 832169689Skan 833169689Skan cl = create_coalesce_list (map); 834169689Skan 835169689Skan coalesce_phi_operands (map, cl); 836169689Skan coalesce_result_decls (map, cl); 837169689Skan coalesce_asm_operands (map, cl); 838169689Skan 839169689Skan /* Build a conflict graph. */ 840169689Skan graph = build_tree_conflict_graph (liveinfo, rv, cl); 841169689Skan 842169689Skan if (cl) 843169689Skan { 844169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 845169689Skan { 846169689Skan fprintf (dump_file, "Before sorting:\n"); 847169689Skan dump_coalesce_list (dump_file, cl); 848169689Skan } 849169689Skan 850169689Skan sort_coalesce_list (cl); 851169689Skan 852169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 853169689Skan { 854169689Skan fprintf (dump_file, "\nAfter sorting:\n"); 855169689Skan dump_coalesce_list (dump_file, cl); 856169689Skan } 857169689Skan } 858169689Skan 859169689Skan /* Put the single element variables back in. */ 860169689Skan root_var_decompact (rv); 861169689Skan 862169689Skan /* First, coalesce all live on entry variables to their root variable. 863169689Skan This will ensure the first use is coming from the correct location. */ 864169689Skan 865169689Skan num = num_var_partitions (map); 866169689Skan live = sbitmap_alloc (num); 867169689Skan sbitmap_zero (live); 868169689Skan 869169689Skan /* Set 'live' vector to indicate live on entry partitions. */ 870169689Skan for (x = 0 ; x < num; x++) 871169689Skan { 872169689Skan tree var = partition_to_var (map, x); 873169689Skan if (default_def (SSA_NAME_VAR (var)) == var) 874169689Skan SET_BIT (live, x); 875169689Skan } 876169689Skan 877169689Skan if ((flags & SSANORM_COMBINE_TEMPS) == 0) 878169689Skan { 879169689Skan delete_tree_live_info (liveinfo); 880169689Skan liveinfo = NULL; 881169689Skan } 882169689Skan 883169689Skan /* Assign root variable as partition representative for each live on entry 884169689Skan partition. */ 885169689Skan EXECUTE_IF_SET_IN_SBITMAP (live, 0, x, sbi) 886169689Skan { 887169689Skan tree var = root_var (rv, root_var_find (rv, x)); 888169689Skan var_ann_t ann = var_ann (var); 889169689Skan /* If these aren't already coalesced... */ 890169689Skan if (partition_to_var (map, x) != var) 891169689Skan { 892169689Skan /* This root variable should have not already been assigned 893169689Skan to another partition which is not coalesced with this one. */ 894169689Skan gcc_assert (!ann->out_of_ssa_tag); 895169689Skan 896169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 897169689Skan { 898169689Skan print_exprs (dump_file, "Must coalesce ", 899169689Skan partition_to_var (map, x), 900169689Skan " with the root variable ", var, ".\n"); 901169689Skan } 902169689Skan 903169689Skan change_partition_var (map, var, x); 904169689Skan } 905169689Skan } 906169689Skan 907169689Skan sbitmap_free (live); 908169689Skan 909169689Skan /* Coalesce partitions live across abnormal edges. */ 910169689Skan coalesce_abnormal_edges (map, graph, rv); 911169689Skan 912169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 913169689Skan dump_var_map (dump_file, map); 914169689Skan 915169689Skan /* Coalesce partitions. */ 916169689Skan coalesce_tpa_members (rv, graph, map, cl, 917169689Skan ((dump_flags & TDF_DETAILS) ? dump_file 918169689Skan : NULL)); 919169689Skan 920169689Skan if (flags & SSANORM_COALESCE_PARTITIONS) 921169689Skan coalesce_tpa_members (rv, graph, map, NULL, 922169689Skan ((dump_flags & TDF_DETAILS) ? dump_file 923169689Skan : NULL)); 924169689Skan if (cl) 925169689Skan delete_coalesce_list (cl); 926169689Skan root_var_delete (rv); 927169689Skan conflict_graph_delete (graph); 928169689Skan 929169689Skan return liveinfo; 930169689Skan} 931169689Skan 932169689Skan 933169689Skan/* Take the ssa-name var_map MAP, and assign real variables to each 934169689Skan partition. */ 935169689Skan 936169689Skanstatic void 937169689Skanassign_vars (var_map map) 938169689Skan{ 939169689Skan int x, i, num, rep; 940169689Skan tree t, var; 941169689Skan var_ann_t ann; 942169689Skan root_var_p rv; 943169689Skan 944169689Skan rv = root_var_init (map); 945169689Skan if (!rv) 946169689Skan return; 947169689Skan 948169689Skan /* Coalescing may already have forced some partitions to their root 949169689Skan variable. Find these and tag them. */ 950169689Skan 951169689Skan num = num_var_partitions (map); 952169689Skan for (x = 0; x < num; x++) 953169689Skan { 954169689Skan var = partition_to_var (map, x); 955169689Skan if (TREE_CODE (var) != SSA_NAME) 956169689Skan { 957169689Skan /* Coalescing will already have verified that more than one 958169689Skan partition doesn't have the same root variable. Simply marked 959169689Skan the variable as assigned. */ 960169689Skan ann = var_ann (var); 961169689Skan ann->out_of_ssa_tag = 1; 962169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 963169689Skan { 964169689Skan fprintf (dump_file, "partition %d has variable ", x); 965169689Skan print_generic_expr (dump_file, var, TDF_SLIM); 966169689Skan fprintf (dump_file, " assigned to it.\n"); 967169689Skan } 968169689Skan 969169689Skan } 970169689Skan } 971169689Skan 972169689Skan num = root_var_num (rv); 973169689Skan for (x = 0; x < num; x++) 974169689Skan { 975169689Skan var = root_var (rv, x); 976169689Skan ann = var_ann (var); 977169689Skan for (i = root_var_first_partition (rv, x); 978169689Skan i != ROOT_VAR_NONE; 979169689Skan i = root_var_next_partition (rv, i)) 980169689Skan { 981169689Skan t = partition_to_var (map, i); 982169689Skan 983169689Skan if (t == var || TREE_CODE (t) != SSA_NAME) 984169689Skan continue; 985169689Skan 986169689Skan rep = var_to_partition (map, t); 987169689Skan 988169689Skan if (!ann->out_of_ssa_tag) 989169689Skan { 990169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 991169689Skan print_exprs (dump_file, "", t, " --> ", var, "\n"); 992169689Skan change_partition_var (map, var, rep); 993169689Skan continue; 994169689Skan } 995169689Skan 996169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 997169689Skan print_exprs (dump_file, "", t, " not coalesced with ", var, 998169689Skan ""); 999169689Skan 1000169689Skan var = create_temp (t); 1001169689Skan change_partition_var (map, var, rep); 1002169689Skan ann = var_ann (var); 1003169689Skan 1004169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1005169689Skan { 1006169689Skan fprintf (dump_file, " --> New temp: '"); 1007169689Skan print_generic_expr (dump_file, var, TDF_SLIM); 1008169689Skan fprintf (dump_file, "'\n"); 1009169689Skan } 1010169689Skan } 1011169689Skan } 1012169689Skan 1013169689Skan root_var_delete (rv); 1014169689Skan} 1015169689Skan 1016169689Skan 1017169689Skan/* Replace use operand P with whatever variable it has been rewritten to based 1018169689Skan on the partitions in MAP. EXPR is an optional expression vector over SSA 1019169689Skan versions which is used to replace P with an expression instead of a variable. 1020169689Skan If the stmt is changed, return true. */ 1021169689Skan 1022169689Skanstatic inline bool 1023169689Skanreplace_use_variable (var_map map, use_operand_p p, tree *expr) 1024169689Skan{ 1025169689Skan tree new_var; 1026169689Skan tree var = USE_FROM_PTR (p); 1027169689Skan 1028169689Skan /* Check if we are replacing this variable with an expression. */ 1029169689Skan if (expr) 1030169689Skan { 1031169689Skan int version = SSA_NAME_VERSION (var); 1032169689Skan if (expr[version]) 1033169689Skan { 1034169689Skan tree new_expr = TREE_OPERAND (expr[version], 1); 1035169689Skan SET_USE (p, new_expr); 1036169689Skan /* Clear the stmt's RHS, or GC might bite us. */ 1037169689Skan TREE_OPERAND (expr[version], 1) = NULL_TREE; 1038169689Skan return true; 1039169689Skan } 1040169689Skan } 1041169689Skan 1042169689Skan new_var = var_to_partition_to_var (map, var); 1043169689Skan if (new_var) 1044169689Skan { 1045169689Skan SET_USE (p, new_var); 1046169689Skan set_is_used (new_var); 1047169689Skan return true; 1048169689Skan } 1049169689Skan return false; 1050169689Skan} 1051169689Skan 1052169689Skan 1053169689Skan/* Replace def operand DEF_P with whatever variable it has been rewritten to 1054169689Skan based on the partitions in MAP. EXPR is an optional expression vector over 1055169689Skan SSA versions which is used to replace DEF_P with an expression instead of a 1056169689Skan variable. If the stmt is changed, return true. */ 1057169689Skan 1058169689Skanstatic inline bool 1059169689Skanreplace_def_variable (var_map map, def_operand_p def_p, tree *expr) 1060169689Skan{ 1061169689Skan tree new_var; 1062169689Skan tree var = DEF_FROM_PTR (def_p); 1063169689Skan 1064169689Skan /* Check if we are replacing this variable with an expression. */ 1065169689Skan if (expr) 1066169689Skan { 1067169689Skan int version = SSA_NAME_VERSION (var); 1068169689Skan if (expr[version]) 1069169689Skan { 1070169689Skan tree new_expr = TREE_OPERAND (expr[version], 1); 1071169689Skan SET_DEF (def_p, new_expr); 1072169689Skan /* Clear the stmt's RHS, or GC might bite us. */ 1073169689Skan TREE_OPERAND (expr[version], 1) = NULL_TREE; 1074169689Skan return true; 1075169689Skan } 1076169689Skan } 1077169689Skan 1078169689Skan new_var = var_to_partition_to_var (map, var); 1079169689Skan if (new_var) 1080169689Skan { 1081169689Skan SET_DEF (def_p, new_var); 1082169689Skan set_is_used (new_var); 1083169689Skan return true; 1084169689Skan } 1085169689Skan return false; 1086169689Skan} 1087169689Skan 1088169689Skan 1089169689Skan/* Remove any PHI node which is a virtual PHI. */ 1090169689Skan 1091169689Skanstatic void 1092169689Skaneliminate_virtual_phis (void) 1093169689Skan{ 1094169689Skan basic_block bb; 1095169689Skan tree phi, next; 1096169689Skan 1097169689Skan FOR_EACH_BB (bb) 1098169689Skan { 1099169689Skan for (phi = phi_nodes (bb); phi; phi = next) 1100169689Skan { 1101169689Skan next = PHI_CHAIN (phi); 1102169689Skan if (!is_gimple_reg (SSA_NAME_VAR (PHI_RESULT (phi)))) 1103169689Skan { 1104169689Skan#ifdef ENABLE_CHECKING 1105169689Skan int i; 1106169689Skan /* There should be no arguments of this PHI which are in 1107169689Skan the partition list, or we get incorrect results. */ 1108169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 1109169689Skan { 1110169689Skan tree arg = PHI_ARG_DEF (phi, i); 1111169689Skan if (TREE_CODE (arg) == SSA_NAME 1112169689Skan && is_gimple_reg (SSA_NAME_VAR (arg))) 1113169689Skan { 1114169689Skan fprintf (stderr, "Argument of PHI is not virtual ("); 1115169689Skan print_generic_expr (stderr, arg, TDF_SLIM); 1116169689Skan fprintf (stderr, "), but the result is :"); 1117169689Skan print_generic_stmt (stderr, phi, TDF_SLIM); 1118169689Skan internal_error ("SSA corruption"); 1119169689Skan } 1120169689Skan } 1121169689Skan#endif 1122169689Skan remove_phi_node (phi, NULL_TREE); 1123169689Skan } 1124169689Skan } 1125169689Skan } 1126169689Skan} 1127169689Skan 1128169689Skan 1129169689Skan/* This routine will coalesce variables in MAP of the same type which do not 1130169689Skan interfere with each other. LIVEINFO is the live range info for variables 1131169689Skan of interest. This will both reduce the memory footprint of the stack, and 1132169689Skan allow us to coalesce together local copies of globals and scalarized 1133169689Skan component refs. */ 1134169689Skan 1135169689Skanstatic void 1136169689Skancoalesce_vars (var_map map, tree_live_info_p liveinfo) 1137169689Skan{ 1138169689Skan basic_block bb; 1139169689Skan type_var_p tv; 1140169689Skan tree var; 1141169689Skan unsigned x, p, p2; 1142169689Skan coalesce_list_p cl; 1143169689Skan conflict_graph graph; 1144169689Skan 1145169689Skan cl = create_coalesce_list (map); 1146169689Skan 1147169689Skan /* Merge all the live on entry vectors for coalesced partitions. */ 1148169689Skan for (x = 0; x < num_var_partitions (map); x++) 1149169689Skan { 1150169689Skan var = partition_to_var (map, x); 1151169689Skan p = var_to_partition (map, var); 1152169689Skan if (p != x) 1153169689Skan live_merge_and_clear (liveinfo, p, x); 1154169689Skan } 1155169689Skan 1156169689Skan /* When PHI nodes are turned into copies, the result of each PHI node 1157169689Skan becomes live on entry to the block. Mark these now. */ 1158169689Skan FOR_EACH_BB (bb) 1159169689Skan { 1160169689Skan tree phi, arg; 1161169689Skan unsigned p; 1162169689Skan 1163169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1164169689Skan { 1165169689Skan p = var_to_partition (map, PHI_RESULT (phi)); 1166169689Skan 1167169689Skan /* Skip virtual PHI nodes. */ 1168169689Skan if (p == (unsigned)NO_PARTITION) 1169169689Skan continue; 1170169689Skan 1171169689Skan make_live_on_entry (liveinfo, bb, p); 1172169689Skan 1173169689Skan /* Each argument is a potential copy operation. Add any arguments 1174169689Skan which are not coalesced to the result to the coalesce list. */ 1175169689Skan for (x = 0; x < (unsigned)PHI_NUM_ARGS (phi); x++) 1176169689Skan { 1177169689Skan arg = PHI_ARG_DEF (phi, x); 1178169689Skan if (!phi_ssa_name_p (arg)) 1179169689Skan continue; 1180169689Skan p2 = var_to_partition (map, arg); 1181169689Skan if (p2 == (unsigned)NO_PARTITION) 1182169689Skan continue; 1183169689Skan if (p != p2) 1184169689Skan { 1185169689Skan edge e = PHI_ARG_EDGE (phi, x); 1186169689Skan 1187169689Skan add_coalesce (cl, p, p2, 1188169689Skan coalesce_cost (EDGE_FREQUENCY (e), 1189169689Skan maybe_hot_bb_p (bb), 1190169689Skan EDGE_CRITICAL_P (e))); 1191169689Skan } 1192169689Skan } 1193169689Skan } 1194169689Skan } 1195169689Skan 1196169689Skan 1197169689Skan /* Re-calculate live on exit info. */ 1198169689Skan calculate_live_on_exit (liveinfo); 1199169689Skan 1200169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1201169689Skan { 1202169689Skan fprintf (dump_file, "Live range info for variable memory coalescing.\n"); 1203169689Skan dump_live_info (dump_file, liveinfo, LIVEDUMP_ALL); 1204169689Skan 1205169689Skan fprintf (dump_file, "Coalesce list from phi nodes:\n"); 1206169689Skan dump_coalesce_list (dump_file, cl); 1207169689Skan } 1208169689Skan 1209169689Skan 1210169689Skan tv = type_var_init (map); 1211169689Skan if (dump_file) 1212169689Skan type_var_dump (dump_file, tv); 1213169689Skan type_var_compact (tv); 1214169689Skan if (dump_file) 1215169689Skan type_var_dump (dump_file, tv); 1216169689Skan 1217169689Skan graph = build_tree_conflict_graph (liveinfo, tv, cl); 1218169689Skan 1219169689Skan type_var_decompact (tv); 1220169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1221169689Skan { 1222169689Skan fprintf (dump_file, "type var list now looks like:n"); 1223169689Skan type_var_dump (dump_file, tv); 1224169689Skan 1225169689Skan fprintf (dump_file, "Coalesce list after conflict graph build:\n"); 1226169689Skan dump_coalesce_list (dump_file, cl); 1227169689Skan } 1228169689Skan 1229169689Skan sort_coalesce_list (cl); 1230169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1231169689Skan { 1232169689Skan fprintf (dump_file, "Coalesce list after sorting:\n"); 1233169689Skan dump_coalesce_list (dump_file, cl); 1234169689Skan } 1235169689Skan 1236169689Skan coalesce_tpa_members (tv, graph, map, cl, 1237169689Skan ((dump_flags & TDF_DETAILS) ? dump_file : NULL)); 1238169689Skan 1239169689Skan type_var_delete (tv); 1240169689Skan delete_coalesce_list (cl); 1241169689Skan} 1242169689Skan 1243169689Skan 1244169689Skan/* Temporary Expression Replacement (TER) 1245169689Skan 1246169689Skan Replace SSA version variables during out-of-ssa with their defining 1247169689Skan expression if there is only one use of the variable. 1248169689Skan 1249169689Skan A pass is made through the function, one block at a time. No cross block 1250169689Skan information is tracked. 1251169689Skan 1252169689Skan Variables which only have one use, and whose defining stmt is considered 1253169689Skan a replaceable expression (see check_replaceable) are entered into 1254169689Skan consideration by adding a list of dependent partitions to the version_info 1255169689Skan vector for that ssa_name_version. This information comes from the partition 1256169689Skan mapping for each USE. At the same time, the partition_dep_list vector for 1257169689Skan these partitions have this version number entered into their lists. 1258169689Skan 1259169689Skan When the use of a replaceable ssa_variable is encountered, the dependence 1260169689Skan list in version_info[] is moved to the "pending_dependence" list in case 1261169689Skan the current expression is also replaceable. (To be determined later in 1262169689Skan processing this stmt.) version_info[] for the version is then updated to 1263169689Skan point to the defining stmt and the 'replaceable' bit is set. 1264169689Skan 1265169689Skan Any partition which is defined by a statement 'kills' any expression which 1266169689Skan is dependent on this partition. Every ssa version in the partitions' 1267169689Skan dependence list is removed from future consideration. 1268169689Skan 1269169689Skan All virtual references are lumped together. Any expression which is 1270169689Skan dependent on any virtual variable (via a VUSE) has a dependence added 1271169689Skan to the special partition defined by VIRTUAL_PARTITION. 1272169689Skan 1273169689Skan Whenever a V_MAY_DEF is seen, all expressions dependent this 1274169689Skan VIRTUAL_PARTITION are removed from consideration. 1275169689Skan 1276169689Skan At the end of a basic block, all expression are removed from consideration 1277169689Skan in preparation for the next block. 1278169689Skan 1279169689Skan The end result is a vector over SSA_NAME_VERSION which is passed back to 1280169689Skan rewrite_out_of_ssa. As the SSA variables are being rewritten, instead of 1281169689Skan replacing the SSA_NAME tree element with the partition it was assigned, 1282169689Skan it is replaced with the RHS of the defining expression. */ 1283169689Skan 1284169689Skan 1285169689Skan/* Dependency list element. This can contain either a partition index or a 1286169689Skan version number, depending on which list it is in. */ 1287169689Skan 1288169689Skantypedef struct value_expr_d 1289169689Skan{ 1290169689Skan int value; 1291169689Skan struct value_expr_d *next; 1292169689Skan} *value_expr_p; 1293169689Skan 1294169689Skan 1295169689Skan/* Temporary Expression Replacement (TER) table information. */ 1296169689Skan 1297169689Skantypedef struct temp_expr_table_d 1298169689Skan{ 1299169689Skan var_map map; 1300169689Skan void **version_info; 1301169689Skan bitmap *expr_vars; 1302169689Skan value_expr_p *partition_dep_list; 1303169689Skan bitmap replaceable; 1304169689Skan bool saw_replaceable; 1305169689Skan int virtual_partition; 1306169689Skan bitmap partition_in_use; 1307169689Skan value_expr_p free_list; 1308169689Skan value_expr_p pending_dependence; 1309169689Skan} *temp_expr_table_p; 1310169689Skan 1311169689Skan/* Used to indicate a dependency on V_MAY_DEFs. */ 1312169689Skan#define VIRTUAL_PARTITION(table) (table->virtual_partition) 1313169689Skan 1314169689Skanstatic temp_expr_table_p new_temp_expr_table (var_map); 1315169689Skanstatic tree *free_temp_expr_table (temp_expr_table_p); 1316169689Skanstatic inline value_expr_p new_value_expr (temp_expr_table_p); 1317169689Skanstatic inline void free_value_expr (temp_expr_table_p, value_expr_p); 1318169689Skanstatic inline value_expr_p find_value_in_list (value_expr_p, int, 1319169689Skan value_expr_p *); 1320169689Skanstatic inline void add_value_to_list (temp_expr_table_p, value_expr_p *, int); 1321169689Skanstatic inline void add_info_to_list (temp_expr_table_p, value_expr_p *, 1322169689Skan value_expr_p); 1323169689Skanstatic value_expr_p remove_value_from_list (value_expr_p *, int); 1324169689Skanstatic void add_dependence (temp_expr_table_p, int, tree); 1325169689Skanstatic bool check_replaceable (temp_expr_table_p, tree); 1326169689Skanstatic void finish_expr (temp_expr_table_p, int, bool); 1327169689Skanstatic void mark_replaceable (temp_expr_table_p, tree); 1328169689Skanstatic inline void kill_expr (temp_expr_table_p, int, bool); 1329169689Skanstatic inline void kill_virtual_exprs (temp_expr_table_p, bool); 1330169689Skanstatic void find_replaceable_in_bb (temp_expr_table_p, basic_block); 1331169689Skanstatic tree *find_replaceable_exprs (var_map); 1332169689Skanstatic void dump_replaceable_exprs (FILE *, tree *); 1333169689Skan 1334169689Skan 1335169689Skan/* Create a new TER table for MAP. */ 1336169689Skan 1337169689Skanstatic temp_expr_table_p 1338169689Skannew_temp_expr_table (var_map map) 1339169689Skan{ 1340169689Skan temp_expr_table_p t; 1341169689Skan 1342169689Skan t = XNEW (struct temp_expr_table_d); 1343169689Skan t->map = map; 1344169689Skan 1345169689Skan t->version_info = XCNEWVEC (void *, num_ssa_names + 1); 1346169689Skan t->expr_vars = XCNEWVEC (bitmap, num_ssa_names + 1); 1347169689Skan t->partition_dep_list = XCNEWVEC (value_expr_p, 1348169689Skan num_var_partitions (map) + 1); 1349169689Skan 1350169689Skan t->replaceable = BITMAP_ALLOC (NULL); 1351169689Skan t->partition_in_use = BITMAP_ALLOC (NULL); 1352169689Skan 1353169689Skan t->saw_replaceable = false; 1354169689Skan t->virtual_partition = num_var_partitions (map); 1355169689Skan t->free_list = NULL; 1356169689Skan t->pending_dependence = NULL; 1357169689Skan 1358169689Skan return t; 1359169689Skan} 1360169689Skan 1361169689Skan 1362169689Skan/* Free TER table T. If there are valid replacements, return the expression 1363169689Skan vector. */ 1364169689Skan 1365169689Skanstatic tree * 1366169689Skanfree_temp_expr_table (temp_expr_table_p t) 1367169689Skan{ 1368169689Skan value_expr_p p; 1369169689Skan tree *ret = NULL; 1370169689Skan unsigned i; 1371169689Skan 1372169689Skan#ifdef ENABLE_CHECKING 1373169689Skan unsigned x; 1374169689Skan for (x = 0; x <= num_var_partitions (t->map); x++) 1375169689Skan gcc_assert (!t->partition_dep_list[x]); 1376169689Skan#endif 1377169689Skan 1378169689Skan while ((p = t->free_list)) 1379169689Skan { 1380169689Skan t->free_list = p->next; 1381169689Skan free (p); 1382169689Skan } 1383169689Skan 1384169689Skan BITMAP_FREE (t->partition_in_use); 1385169689Skan BITMAP_FREE (t->replaceable); 1386169689Skan 1387169689Skan for (i = 0; i <= num_ssa_names; i++) 1388169689Skan if (t->expr_vars[i]) 1389169689Skan BITMAP_FREE (t->expr_vars[i]); 1390169689Skan free (t->expr_vars); 1391169689Skan 1392169689Skan free (t->partition_dep_list); 1393169689Skan if (t->saw_replaceable) 1394169689Skan ret = (tree *)t->version_info; 1395169689Skan else 1396169689Skan free (t->version_info); 1397169689Skan 1398169689Skan free (t); 1399169689Skan return ret; 1400169689Skan} 1401169689Skan 1402169689Skan 1403169689Skan/* Allocate a new value list node. Take it from the free list in TABLE if 1404169689Skan possible. */ 1405169689Skan 1406169689Skanstatic inline value_expr_p 1407169689Skannew_value_expr (temp_expr_table_p table) 1408169689Skan{ 1409169689Skan value_expr_p p; 1410169689Skan if (table->free_list) 1411169689Skan { 1412169689Skan p = table->free_list; 1413169689Skan table->free_list = p->next; 1414169689Skan } 1415169689Skan else 1416169689Skan p = (value_expr_p) xmalloc (sizeof (struct value_expr_d)); 1417169689Skan 1418169689Skan return p; 1419169689Skan} 1420169689Skan 1421169689Skan 1422169689Skan/* Add value list node P to the free list in TABLE. */ 1423169689Skan 1424169689Skanstatic inline void 1425169689Skanfree_value_expr (temp_expr_table_p table, value_expr_p p) 1426169689Skan{ 1427169689Skan p->next = table->free_list; 1428169689Skan table->free_list = p; 1429169689Skan} 1430169689Skan 1431169689Skan 1432169689Skan/* Find VALUE if it's in LIST. Return a pointer to the list object if found, 1433169689Skan else return NULL. If LAST_PTR is provided, it will point to the previous 1434169689Skan item upon return, or NULL if this is the first item in the list. */ 1435169689Skan 1436169689Skanstatic inline value_expr_p 1437169689Skanfind_value_in_list (value_expr_p list, int value, value_expr_p *last_ptr) 1438169689Skan{ 1439169689Skan value_expr_p curr; 1440169689Skan value_expr_p last = NULL; 1441169689Skan 1442169689Skan for (curr = list; curr; last = curr, curr = curr->next) 1443169689Skan { 1444169689Skan if (curr->value == value) 1445169689Skan break; 1446169689Skan } 1447169689Skan if (last_ptr) 1448169689Skan *last_ptr = last; 1449169689Skan return curr; 1450169689Skan} 1451169689Skan 1452169689Skan 1453169689Skan/* Add VALUE to LIST, if it isn't already present. TAB is the expression 1454169689Skan table */ 1455169689Skan 1456169689Skanstatic inline void 1457169689Skanadd_value_to_list (temp_expr_table_p tab, value_expr_p *list, int value) 1458169689Skan{ 1459169689Skan value_expr_p info; 1460169689Skan 1461169689Skan if (!find_value_in_list (*list, value, NULL)) 1462169689Skan { 1463169689Skan info = new_value_expr (tab); 1464169689Skan info->value = value; 1465169689Skan info->next = *list; 1466169689Skan *list = info; 1467169689Skan } 1468169689Skan} 1469169689Skan 1470169689Skan 1471169689Skan/* Add value node INFO if it's value isn't already in LIST. Free INFO if 1472169689Skan it is already in the list. TAB is the expression table. */ 1473169689Skan 1474169689Skanstatic inline void 1475169689Skanadd_info_to_list (temp_expr_table_p tab, value_expr_p *list, value_expr_p info) 1476169689Skan{ 1477169689Skan if (find_value_in_list (*list, info->value, NULL)) 1478169689Skan free_value_expr (tab, info); 1479169689Skan else 1480169689Skan { 1481169689Skan info->next = *list; 1482169689Skan *list = info; 1483169689Skan } 1484169689Skan} 1485169689Skan 1486169689Skan 1487169689Skan/* Look for VALUE in LIST. If found, remove it from the list and return it's 1488169689Skan pointer. */ 1489169689Skan 1490169689Skanstatic value_expr_p 1491169689Skanremove_value_from_list (value_expr_p *list, int value) 1492169689Skan{ 1493169689Skan value_expr_p info, last; 1494169689Skan 1495169689Skan info = find_value_in_list (*list, value, &last); 1496169689Skan if (!info) 1497169689Skan return NULL; 1498169689Skan if (!last) 1499169689Skan *list = info->next; 1500169689Skan else 1501169689Skan last->next = info->next; 1502169689Skan 1503169689Skan return info; 1504169689Skan} 1505169689Skan 1506169689Skan 1507169689Skan/* Add a dependency between the def of ssa VERSION and VAR. If VAR is 1508169689Skan replaceable by an expression, add a dependence each of the elements of the 1509169689Skan expression. These are contained in the pending list. TAB is the 1510169689Skan expression table. */ 1511169689Skan 1512169689Skanstatic void 1513169689Skanadd_dependence (temp_expr_table_p tab, int version, tree var) 1514169689Skan{ 1515169689Skan int i, x; 1516169689Skan value_expr_p info; 1517169689Skan 1518169689Skan i = SSA_NAME_VERSION (var); 1519169689Skan if (bitmap_bit_p (tab->replaceable, i)) 1520169689Skan { 1521169689Skan /* This variable is being substituted, so use whatever dependences 1522169689Skan were queued up when we marked this as replaceable earlier. */ 1523169689Skan while ((info = tab->pending_dependence)) 1524169689Skan { 1525169689Skan tab->pending_dependence = info->next; 1526169689Skan /* Get the partition this variable was dependent on. Reuse this 1527169689Skan object to represent the current expression instead. */ 1528169689Skan x = info->value; 1529169689Skan info->value = version; 1530169689Skan add_info_to_list (tab, &(tab->partition_dep_list[x]), info); 1531169689Skan add_value_to_list (tab, 1532169689Skan (value_expr_p *)&(tab->version_info[version]), x); 1533169689Skan bitmap_set_bit (tab->partition_in_use, x); 1534169689Skan } 1535169689Skan } 1536169689Skan else 1537169689Skan { 1538169689Skan i = var_to_partition (tab->map, var); 1539169689Skan gcc_assert (i != NO_PARTITION); 1540169689Skan add_value_to_list (tab, &(tab->partition_dep_list[i]), version); 1541169689Skan add_value_to_list (tab, 1542169689Skan (value_expr_p *)&(tab->version_info[version]), i); 1543169689Skan bitmap_set_bit (tab->partition_in_use, i); 1544169689Skan } 1545169689Skan} 1546169689Skan 1547169689Skan 1548169689Skan/* Check if expression STMT is suitable for replacement in table TAB. If so, 1549169689Skan create an expression entry. Return true if this stmt is replaceable. */ 1550169689Skan 1551169689Skanstatic bool 1552169689Skancheck_replaceable (temp_expr_table_p tab, tree stmt) 1553169689Skan{ 1554169689Skan tree var, def, basevar; 1555169689Skan int version; 1556169689Skan var_map map = tab->map; 1557169689Skan ssa_op_iter iter; 1558169689Skan tree call_expr; 1559169689Skan bitmap def_vars, use_vars; 1560169689Skan 1561169689Skan if (TREE_CODE (stmt) != MODIFY_EXPR) 1562169689Skan return false; 1563169689Skan 1564169689Skan /* Punt if there is more than 1 def, or more than 1 use. */ 1565169689Skan def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); 1566169689Skan if (!def) 1567169689Skan return false; 1568169689Skan 1569169689Skan if (version_ref_count (map, def) != 1) 1570169689Skan return false; 1571169689Skan 1572169689Skan /* There must be no V_MAY_DEFS or V_MUST_DEFS. */ 1573169689Skan if (!(ZERO_SSA_OPERANDS (stmt, (SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)))) 1574169689Skan return false; 1575169689Skan 1576169689Skan /* Float expressions must go through memory if float-store is on. */ 1577169689Skan if (flag_float_store && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (stmt, 1)))) 1578169689Skan return false; 1579169689Skan 1580169689Skan /* An assignment with a register variable on the RHS is not 1581169689Skan replaceable. */ 1582169689Skan if (TREE_CODE (TREE_OPERAND (stmt, 1)) == VAR_DECL 1583169689Skan && DECL_HARD_REGISTER (TREE_OPERAND (stmt, 1))) 1584169689Skan return false; 1585169689Skan 1586169689Skan /* Calls to functions with side-effects cannot be replaced. */ 1587169689Skan if ((call_expr = get_call_expr_in (stmt)) != NULL_TREE) 1588169689Skan { 1589169689Skan int call_flags = call_expr_flags (call_expr); 1590169689Skan if (TREE_SIDE_EFFECTS (call_expr) 1591169689Skan && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN))) 1592169689Skan return false; 1593169689Skan } 1594169689Skan 1595169689Skan version = SSA_NAME_VERSION (def); 1596169689Skan basevar = SSA_NAME_VAR (def); 1597169689Skan def_vars = BITMAP_ALLOC (NULL); 1598169689Skan bitmap_set_bit (def_vars, DECL_UID (basevar)); 1599169689Skan 1600169689Skan /* Add this expression to the dependency list for each use partition. */ 1601169689Skan FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) 1602169689Skan { 1603169689Skan add_dependence (tab, version, var); 1604169689Skan 1605169689Skan use_vars = tab->expr_vars[SSA_NAME_VERSION (var)]; 1606169689Skan if (use_vars) 1607169689Skan bitmap_ior_into (def_vars, use_vars); 1608169689Skan } 1609169689Skan tab->expr_vars[version] = def_vars; 1610169689Skan 1611169689Skan /* If there are VUSES, add a dependence on virtual defs. */ 1612169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) 1613169689Skan { 1614169689Skan add_value_to_list (tab, (value_expr_p *)&(tab->version_info[version]), 1615169689Skan VIRTUAL_PARTITION (tab)); 1616169689Skan add_value_to_list (tab, 1617169689Skan &(tab->partition_dep_list[VIRTUAL_PARTITION (tab)]), 1618169689Skan version); 1619169689Skan bitmap_set_bit (tab->partition_in_use, VIRTUAL_PARTITION (tab)); 1620169689Skan } 1621169689Skan 1622169689Skan return true; 1623169689Skan} 1624169689Skan 1625169689Skan 1626169689Skan/* This function will remove the expression for VERSION from replacement 1627169689Skan consideration.n table TAB If 'replace' is true, it is marked as 1628169689Skan replaceable, otherwise not. */ 1629169689Skan 1630169689Skanstatic void 1631169689Skanfinish_expr (temp_expr_table_p tab, int version, bool replace) 1632169689Skan{ 1633169689Skan value_expr_p info, tmp; 1634169689Skan int partition; 1635169689Skan 1636169689Skan /* Remove this expression from its dependent lists. The partition dependence 1637169689Skan list is retained and transfered later to whomever uses this version. */ 1638169689Skan for (info = (value_expr_p) tab->version_info[version]; info; info = tmp) 1639169689Skan { 1640169689Skan partition = info->value; 1641169689Skan gcc_assert (tab->partition_dep_list[partition]); 1642169689Skan tmp = remove_value_from_list (&(tab->partition_dep_list[partition]), 1643169689Skan version); 1644169689Skan gcc_assert (tmp); 1645169689Skan free_value_expr (tab, tmp); 1646169689Skan /* Only clear the bit when the dependency list is emptied via 1647169689Skan a replacement. Otherwise kill_expr will take care of it. */ 1648169689Skan if (!(tab->partition_dep_list[partition]) && replace) 1649169689Skan bitmap_clear_bit (tab->partition_in_use, partition); 1650169689Skan tmp = info->next; 1651169689Skan if (!replace) 1652169689Skan free_value_expr (tab, info); 1653169689Skan } 1654169689Skan 1655169689Skan if (replace) 1656169689Skan { 1657169689Skan tab->saw_replaceable = true; 1658169689Skan bitmap_set_bit (tab->replaceable, version); 1659169689Skan } 1660169689Skan else 1661169689Skan { 1662169689Skan gcc_assert (!bitmap_bit_p (tab->replaceable, version)); 1663169689Skan tab->version_info[version] = NULL; 1664169689Skan } 1665169689Skan} 1666169689Skan 1667169689Skan 1668169689Skan/* Mark the expression associated with VAR as replaceable, and enter 1669169689Skan the defining stmt into the version_info table TAB. */ 1670169689Skan 1671169689Skanstatic void 1672169689Skanmark_replaceable (temp_expr_table_p tab, tree var) 1673169689Skan{ 1674169689Skan value_expr_p info; 1675169689Skan int version = SSA_NAME_VERSION (var); 1676169689Skan finish_expr (tab, version, true); 1677169689Skan 1678169689Skan /* Move the dependence list to the pending list. */ 1679169689Skan if (tab->version_info[version]) 1680169689Skan { 1681169689Skan info = (value_expr_p) tab->version_info[version]; 1682169689Skan for ( ; info->next; info = info->next) 1683169689Skan continue; 1684169689Skan info->next = tab->pending_dependence; 1685169689Skan tab->pending_dependence = (value_expr_p)tab->version_info[version]; 1686169689Skan } 1687169689Skan 1688169689Skan tab->version_info[version] = SSA_NAME_DEF_STMT (var); 1689169689Skan} 1690169689Skan 1691169689Skan 1692169689Skan/* This function marks any expression in TAB which is dependent on PARTITION 1693169689Skan as NOT replaceable. CLEAR_BIT is used to determine whether partition_in_use 1694169689Skan should have its bit cleared. Since this routine can be called within an 1695169689Skan EXECUTE_IF_SET_IN_BITMAP, the bit can't always be cleared. */ 1696169689Skan 1697169689Skanstatic inline void 1698169689Skankill_expr (temp_expr_table_p tab, int partition, bool clear_bit) 1699169689Skan{ 1700169689Skan value_expr_p ptr; 1701169689Skan 1702169689Skan /* Mark every active expr dependent on this var as not replaceable. */ 1703169689Skan while ((ptr = tab->partition_dep_list[partition]) != NULL) 1704169689Skan finish_expr (tab, ptr->value, false); 1705169689Skan 1706169689Skan if (clear_bit) 1707169689Skan bitmap_clear_bit (tab->partition_in_use, partition); 1708169689Skan} 1709169689Skan 1710169689Skan 1711169689Skan/* This function kills all expressions in TAB which are dependent on virtual 1712169689Skan DEFs. CLEAR_BIT determines whether partition_in_use gets cleared. */ 1713169689Skan 1714169689Skanstatic inline void 1715169689Skankill_virtual_exprs (temp_expr_table_p tab, bool clear_bit) 1716169689Skan{ 1717169689Skan kill_expr (tab, VIRTUAL_PARTITION (tab), clear_bit); 1718169689Skan} 1719169689Skan 1720169689Skan 1721169689Skan/* This function processes basic block BB, and looks for variables which can 1722169689Skan be replaced by their expressions. Results are stored in TAB. */ 1723169689Skan 1724169689Skanstatic void 1725169689Skanfind_replaceable_in_bb (temp_expr_table_p tab, basic_block bb) 1726169689Skan{ 1727169689Skan block_stmt_iterator bsi; 1728169689Skan tree stmt, def, use; 1729169689Skan stmt_ann_t ann; 1730169689Skan int partition; 1731169689Skan var_map map = tab->map; 1732169689Skan value_expr_p p; 1733169689Skan ssa_op_iter iter; 1734169689Skan 1735169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 1736169689Skan { 1737169689Skan stmt = bsi_stmt (bsi); 1738169689Skan ann = stmt_ann (stmt); 1739169689Skan 1740169689Skan /* Determine if this stmt finishes an existing expression. */ 1741169689Skan FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) 1742169689Skan { 1743169689Skan unsigned ver = SSA_NAME_VERSION (use); 1744169689Skan 1745169689Skan if (tab->version_info[ver]) 1746169689Skan { 1747169689Skan bool same_root_var = false; 1748169689Skan ssa_op_iter iter2; 1749169689Skan bitmap vars = tab->expr_vars[ver]; 1750169689Skan 1751169689Skan /* See if the root variables are the same. If they are, we 1752169689Skan do not want to do the replacement to avoid problems with 1753169689Skan code size, see PR tree-optimization/17549. */ 1754169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter2, SSA_OP_DEF) 1755169689Skan { 1756169689Skan if (bitmap_bit_p (vars, DECL_UID (SSA_NAME_VAR (def)))) 1757169689Skan { 1758169689Skan same_root_var = true; 1759169689Skan break; 1760169689Skan } 1761169689Skan } 1762169689Skan 1763169689Skan /* Mark expression as replaceable unless stmt is volatile 1764169689Skan or DEF sets the same root variable as STMT. */ 1765169689Skan if (!ann->has_volatile_ops && !same_root_var) 1766169689Skan mark_replaceable (tab, use); 1767169689Skan else 1768169689Skan finish_expr (tab, ver, false); 1769169689Skan } 1770169689Skan } 1771169689Skan 1772169689Skan /* Next, see if this stmt kills off an active expression. */ 1773169689Skan FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF) 1774169689Skan { 1775169689Skan partition = var_to_partition (map, def); 1776169689Skan if (partition != NO_PARTITION && tab->partition_dep_list[partition]) 1777169689Skan kill_expr (tab, partition, true); 1778169689Skan } 1779169689Skan 1780169689Skan /* Now see if we are creating a new expression or not. */ 1781169689Skan if (!ann->has_volatile_ops) 1782169689Skan check_replaceable (tab, stmt); 1783169689Skan 1784169689Skan /* Free any unused dependency lists. */ 1785169689Skan while ((p = tab->pending_dependence)) 1786169689Skan { 1787169689Skan tab->pending_dependence = p->next; 1788169689Skan free_value_expr (tab, p); 1789169689Skan } 1790169689Skan 1791169689Skan /* A V_{MAY,MUST}_DEF kills any expression using a virtual operand. */ 1792169689Skan if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_DEFS)) 1793169689Skan kill_virtual_exprs (tab, true); 1794169689Skan } 1795169689Skan} 1796169689Skan 1797169689Skan 1798169689Skan/* This function is the driver routine for replacement of temporary expressions 1799169689Skan in the SSA->normal phase, operating on MAP. If there are replaceable 1800169689Skan expressions, a table is returned which maps SSA versions to the 1801169689Skan expressions they should be replaced with. A NULL_TREE indicates no 1802169689Skan replacement should take place. If there are no replacements at all, 1803169689Skan NULL is returned by the function, otherwise an expression vector indexed 1804169689Skan by SSA_NAME version numbers. */ 1805169689Skan 1806169689Skanstatic tree * 1807169689Skanfind_replaceable_exprs (var_map map) 1808169689Skan{ 1809169689Skan basic_block bb; 1810169689Skan unsigned i; 1811169689Skan temp_expr_table_p table; 1812169689Skan tree *ret; 1813169689Skan 1814169689Skan table = new_temp_expr_table (map); 1815169689Skan FOR_EACH_BB (bb) 1816169689Skan { 1817169689Skan bitmap_iterator bi; 1818169689Skan 1819169689Skan find_replaceable_in_bb (table, bb); 1820169689Skan EXECUTE_IF_SET_IN_BITMAP ((table->partition_in_use), 0, i, bi) 1821169689Skan { 1822169689Skan kill_expr (table, i, false); 1823169689Skan } 1824169689Skan } 1825169689Skan 1826169689Skan ret = free_temp_expr_table (table); 1827169689Skan return ret; 1828169689Skan} 1829169689Skan 1830169689Skan 1831169689Skan/* Dump TER expression table EXPR to file F. */ 1832169689Skan 1833169689Skanstatic void 1834169689Skandump_replaceable_exprs (FILE *f, tree *expr) 1835169689Skan{ 1836169689Skan tree stmt, var; 1837169689Skan int x; 1838169689Skan fprintf (f, "\nReplacing Expressions\n"); 1839169689Skan for (x = 0; x < (int)num_ssa_names + 1; x++) 1840169689Skan if (expr[x]) 1841169689Skan { 1842169689Skan stmt = expr[x]; 1843169689Skan var = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF); 1844169689Skan gcc_assert (var != NULL_TREE); 1845169689Skan print_generic_expr (f, var, TDF_SLIM); 1846169689Skan fprintf (f, " replace with --> "); 1847169689Skan print_generic_expr (f, TREE_OPERAND (stmt, 1), TDF_SLIM); 1848169689Skan fprintf (f, "\n"); 1849169689Skan } 1850169689Skan fprintf (f, "\n"); 1851169689Skan} 1852169689Skan 1853169689Skan 1854169689Skan/* This function will rewrite the current program using the variable mapping 1855169689Skan found in MAP. If the replacement vector VALUES is provided, any 1856169689Skan occurrences of partitions with non-null entries in the vector will be 1857169689Skan replaced with the expression in the vector instead of its mapped 1858169689Skan variable. */ 1859169689Skan 1860169689Skanstatic void 1861169689Skanrewrite_trees (var_map map, tree *values) 1862169689Skan{ 1863169689Skan elim_graph g; 1864169689Skan basic_block bb; 1865169689Skan block_stmt_iterator si; 1866169689Skan edge e; 1867169689Skan tree phi; 1868169689Skan bool changed; 1869169689Skan 1870169689Skan#ifdef ENABLE_CHECKING 1871169689Skan /* Search for PHIs where the destination has no partition, but one 1872169689Skan or more arguments has a partition. This should not happen and can 1873169689Skan create incorrect code. */ 1874169689Skan FOR_EACH_BB (bb) 1875169689Skan { 1876169689Skan tree phi; 1877169689Skan 1878169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 1879169689Skan { 1880169689Skan tree T0 = var_to_partition_to_var (map, PHI_RESULT (phi)); 1881169689Skan 1882169689Skan if (T0 == NULL_TREE) 1883169689Skan { 1884169689Skan int i; 1885169689Skan 1886169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 1887169689Skan { 1888169689Skan tree arg = PHI_ARG_DEF (phi, i); 1889169689Skan 1890169689Skan if (TREE_CODE (arg) == SSA_NAME 1891169689Skan && var_to_partition (map, arg) != NO_PARTITION) 1892169689Skan { 1893169689Skan fprintf (stderr, "Argument of PHI is in a partition :("); 1894169689Skan print_generic_expr (stderr, arg, TDF_SLIM); 1895169689Skan fprintf (stderr, "), but the result is not :"); 1896169689Skan print_generic_stmt (stderr, phi, TDF_SLIM); 1897169689Skan internal_error ("SSA corruption"); 1898169689Skan } 1899169689Skan } 1900169689Skan } 1901169689Skan } 1902169689Skan } 1903169689Skan#endif 1904169689Skan 1905169689Skan /* Replace PHI nodes with any required copies. */ 1906169689Skan g = new_elim_graph (map->num_partitions); 1907169689Skan g->map = map; 1908169689Skan FOR_EACH_BB (bb) 1909169689Skan { 1910169689Skan for (si = bsi_start (bb); !bsi_end_p (si); ) 1911169689Skan { 1912169689Skan tree stmt = bsi_stmt (si); 1913169689Skan use_operand_p use_p, copy_use_p; 1914169689Skan def_operand_p def_p; 1915169689Skan bool remove = false, is_copy = false; 1916169689Skan int num_uses = 0; 1917169689Skan stmt_ann_t ann; 1918169689Skan ssa_op_iter iter; 1919169689Skan 1920169689Skan ann = stmt_ann (stmt); 1921169689Skan changed = false; 1922169689Skan 1923169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR 1924169689Skan && (TREE_CODE (TREE_OPERAND (stmt, 1)) == SSA_NAME)) 1925169689Skan is_copy = true; 1926169689Skan 1927169689Skan copy_use_p = NULL_USE_OPERAND_P; 1928169689Skan FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE) 1929169689Skan { 1930169689Skan if (replace_use_variable (map, use_p, values)) 1931169689Skan changed = true; 1932169689Skan copy_use_p = use_p; 1933169689Skan num_uses++; 1934169689Skan } 1935169689Skan 1936169689Skan if (num_uses != 1) 1937169689Skan is_copy = false; 1938169689Skan 1939169689Skan def_p = SINGLE_SSA_DEF_OPERAND (stmt, SSA_OP_DEF); 1940169689Skan 1941169689Skan if (def_p != NULL) 1942169689Skan { 1943169689Skan /* Mark this stmt for removal if it is the list of replaceable 1944169689Skan expressions. */ 1945169689Skan if (values && values[SSA_NAME_VERSION (DEF_FROM_PTR (def_p))]) 1946169689Skan remove = true; 1947169689Skan else 1948169689Skan { 1949169689Skan if (replace_def_variable (map, def_p, NULL)) 1950169689Skan changed = true; 1951169689Skan /* If both SSA_NAMEs coalesce to the same variable, 1952169689Skan mark the now redundant copy for removal. */ 1953169689Skan if (is_copy) 1954169689Skan { 1955169689Skan gcc_assert (copy_use_p != NULL_USE_OPERAND_P); 1956169689Skan if (DEF_FROM_PTR (def_p) == USE_FROM_PTR (copy_use_p)) 1957169689Skan remove = true; 1958169689Skan } 1959169689Skan } 1960169689Skan } 1961169689Skan else 1962169689Skan FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_DEF) 1963169689Skan if (replace_def_variable (map, def_p, NULL)) 1964169689Skan changed = true; 1965169689Skan 1966169689Skan /* Remove any stmts marked for removal. */ 1967169689Skan if (remove) 1968169689Skan bsi_remove (&si, true); 1969169689Skan else 1970169689Skan bsi_next (&si); 1971169689Skan } 1972169689Skan 1973169689Skan phi = phi_nodes (bb); 1974169689Skan if (phi) 1975169689Skan { 1976169689Skan edge_iterator ei; 1977169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 1978169689Skan eliminate_phi (e, g); 1979169689Skan } 1980169689Skan } 1981169689Skan 1982169689Skan delete_elim_graph (g); 1983169689Skan} 1984169689Skan 1985169689Skan 1986169689SkanDEF_VEC_ALLOC_P(edge,heap); 1987169689Skan 1988169689Skan/* These are the local work structures used to determine the best place to 1989169689Skan insert the copies that were placed on edges by the SSA->normal pass.. */ 1990169689Skanstatic VEC(edge,heap) *edge_leader; 1991169689Skanstatic VEC(tree,heap) *stmt_list; 1992169689Skanstatic bitmap leader_has_match = NULL; 1993169689Skanstatic edge leader_match = NULL; 1994169689Skan 1995169689Skan 1996169689Skan/* Pass this function to make_forwarder_block so that all the edges with 1997169689Skan matching PENDING_STMT lists to 'curr_stmt_list' get redirected. */ 1998169689Skanstatic bool 1999169689Skansame_stmt_list_p (edge e) 2000169689Skan{ 2001169689Skan return (e->aux == (PTR) leader_match) ? true : false; 2002169689Skan} 2003169689Skan 2004169689Skan 2005169689Skan/* Return TRUE if S1 and S2 are equivalent copies. */ 2006169689Skanstatic inline bool 2007169689Skanidentical_copies_p (tree s1, tree s2) 2008169689Skan{ 2009169689Skan#ifdef ENABLE_CHECKING 2010169689Skan gcc_assert (TREE_CODE (s1) == MODIFY_EXPR); 2011169689Skan gcc_assert (TREE_CODE (s2) == MODIFY_EXPR); 2012169689Skan gcc_assert (DECL_P (TREE_OPERAND (s1, 0))); 2013169689Skan gcc_assert (DECL_P (TREE_OPERAND (s2, 0))); 2014169689Skan#endif 2015169689Skan 2016169689Skan if (TREE_OPERAND (s1, 0) != TREE_OPERAND (s2, 0)) 2017169689Skan return false; 2018169689Skan 2019169689Skan s1 = TREE_OPERAND (s1, 1); 2020169689Skan s2 = TREE_OPERAND (s2, 1); 2021169689Skan 2022169689Skan if (s1 != s2) 2023169689Skan return false; 2024169689Skan 2025169689Skan return true; 2026169689Skan} 2027169689Skan 2028169689Skan 2029169689Skan/* Compare the PENDING_STMT list for two edges, and return true if the lists 2030169689Skan contain the same sequence of copies. */ 2031169689Skan 2032169689Skanstatic inline bool 2033169689Skanidentical_stmt_lists_p (edge e1, edge e2) 2034169689Skan{ 2035169689Skan tree t1 = PENDING_STMT (e1); 2036169689Skan tree t2 = PENDING_STMT (e2); 2037169689Skan tree_stmt_iterator tsi1, tsi2; 2038169689Skan 2039169689Skan gcc_assert (TREE_CODE (t1) == STATEMENT_LIST); 2040169689Skan gcc_assert (TREE_CODE (t2) == STATEMENT_LIST); 2041169689Skan 2042169689Skan for (tsi1 = tsi_start (t1), tsi2 = tsi_start (t2); 2043169689Skan !tsi_end_p (tsi1) && !tsi_end_p (tsi2); 2044169689Skan tsi_next (&tsi1), tsi_next (&tsi2)) 2045169689Skan { 2046169689Skan if (!identical_copies_p (tsi_stmt (tsi1), tsi_stmt (tsi2))) 2047169689Skan break; 2048169689Skan } 2049169689Skan 2050169689Skan if (!tsi_end_p (tsi1) || ! tsi_end_p (tsi2)) 2051169689Skan return false; 2052169689Skan 2053169689Skan return true; 2054169689Skan} 2055169689Skan 2056169689Skan 2057169689Skan/* Allocate data structures used in analyze_edges_for_bb. */ 2058169689Skan 2059169689Skanstatic void 2060169689Skaninit_analyze_edges_for_bb (void) 2061169689Skan{ 2062169689Skan edge_leader = VEC_alloc (edge, heap, 25); 2063169689Skan stmt_list = VEC_alloc (tree, heap, 25); 2064169689Skan leader_has_match = BITMAP_ALLOC (NULL); 2065169689Skan} 2066169689Skan 2067169689Skan 2068169689Skan/* Free data structures used in analyze_edges_for_bb. */ 2069169689Skan 2070169689Skanstatic void 2071169689Skanfini_analyze_edges_for_bb (void) 2072169689Skan{ 2073169689Skan VEC_free (edge, heap, edge_leader); 2074169689Skan VEC_free (tree, heap, stmt_list); 2075169689Skan BITMAP_FREE (leader_has_match); 2076169689Skan} 2077169689Skan 2078169689Skan 2079169689Skan/* Look at all the incoming edges to block BB, and decide where the best place 2080169689Skan to insert the stmts on each edge are, and perform those insertions. */ 2081169689Skan 2082169689Skanstatic void 2083169689Skananalyze_edges_for_bb (basic_block bb) 2084169689Skan{ 2085169689Skan edge e; 2086169689Skan edge_iterator ei; 2087169689Skan int count; 2088169689Skan unsigned int x; 2089169689Skan bool have_opportunity; 2090169689Skan block_stmt_iterator bsi; 2091169689Skan tree stmt; 2092169689Skan edge single_edge = NULL; 2093169689Skan bool is_label; 2094169689Skan edge leader; 2095169689Skan 2096169689Skan count = 0; 2097169689Skan 2098169689Skan /* Blocks which contain at least one abnormal edge cannot use 2099169689Skan make_forwarder_block. Look for these blocks, and commit any PENDING_STMTs 2100169689Skan found on edges in these block. */ 2101169689Skan have_opportunity = true; 2102169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2103169689Skan if (e->flags & EDGE_ABNORMAL) 2104169689Skan { 2105169689Skan have_opportunity = false; 2106169689Skan break; 2107169689Skan } 2108169689Skan 2109169689Skan if (!have_opportunity) 2110169689Skan { 2111169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2112169689Skan if (PENDING_STMT (e)) 2113169689Skan bsi_commit_one_edge_insert (e, NULL); 2114169689Skan return; 2115169689Skan } 2116169689Skan /* Find out how many edges there are with interesting pending stmts on them. 2117169689Skan Commit the stmts on edges we are not interested in. */ 2118169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2119169689Skan { 2120169689Skan if (PENDING_STMT (e)) 2121169689Skan { 2122169689Skan gcc_assert (!(e->flags & EDGE_ABNORMAL)); 2123169689Skan if (e->flags & EDGE_FALLTHRU) 2124169689Skan { 2125169689Skan bsi = bsi_start (e->src); 2126169689Skan if (!bsi_end_p (bsi)) 2127169689Skan { 2128169689Skan stmt = bsi_stmt (bsi); 2129169689Skan bsi_next (&bsi); 2130169689Skan gcc_assert (stmt != NULL_TREE); 2131169689Skan is_label = (TREE_CODE (stmt) == LABEL_EXPR); 2132169689Skan /* Punt if it has non-label stmts, or isn't local. */ 2133169689Skan if (!is_label || DECL_NONLOCAL (TREE_OPERAND (stmt, 0)) 2134169689Skan || !bsi_end_p (bsi)) 2135169689Skan { 2136169689Skan bsi_commit_one_edge_insert (e, NULL); 2137169689Skan continue; 2138169689Skan } 2139169689Skan } 2140169689Skan } 2141169689Skan single_edge = e; 2142169689Skan count++; 2143169689Skan } 2144169689Skan } 2145169689Skan 2146169689Skan /* If there aren't at least 2 edges, no sharing will happen. */ 2147169689Skan if (count < 2) 2148169689Skan { 2149169689Skan if (single_edge) 2150169689Skan bsi_commit_one_edge_insert (single_edge, NULL); 2151169689Skan return; 2152169689Skan } 2153169689Skan 2154169689Skan /* Ensure that we have empty worklists. */ 2155169689Skan#ifdef ENABLE_CHECKING 2156169689Skan gcc_assert (VEC_length (edge, edge_leader) == 0); 2157169689Skan gcc_assert (VEC_length (tree, stmt_list) == 0); 2158169689Skan gcc_assert (bitmap_empty_p (leader_has_match)); 2159169689Skan#endif 2160169689Skan 2161169689Skan /* Find the "leader" block for each set of unique stmt lists. Preference is 2162169689Skan given to FALLTHRU blocks since they would need a GOTO to arrive at another 2163169689Skan block. The leader edge destination is the block which all the other edges 2164169689Skan with the same stmt list will be redirected to. */ 2165169689Skan have_opportunity = false; 2166169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2167169689Skan { 2168169689Skan if (PENDING_STMT (e)) 2169169689Skan { 2170169689Skan bool found = false; 2171169689Skan 2172169689Skan /* Look for the same stmt list in edge leaders list. */ 2173169689Skan for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) 2174169689Skan { 2175169689Skan if (identical_stmt_lists_p (leader, e)) 2176169689Skan { 2177169689Skan /* Give this edge the same stmt list pointer. */ 2178169689Skan PENDING_STMT (e) = NULL; 2179169689Skan e->aux = leader; 2180169689Skan bitmap_set_bit (leader_has_match, x); 2181169689Skan have_opportunity = found = true; 2182169689Skan break; 2183169689Skan } 2184169689Skan } 2185169689Skan 2186169689Skan /* If no similar stmt list, add this edge to the leader list. */ 2187169689Skan if (!found) 2188169689Skan { 2189169689Skan VEC_safe_push (edge, heap, edge_leader, e); 2190169689Skan VEC_safe_push (tree, heap, stmt_list, PENDING_STMT (e)); 2191169689Skan } 2192169689Skan } 2193169689Skan } 2194169689Skan 2195169689Skan /* If there are no similar lists, just issue the stmts. */ 2196169689Skan if (!have_opportunity) 2197169689Skan { 2198169689Skan for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) 2199169689Skan bsi_commit_one_edge_insert (leader, NULL); 2200169689Skan VEC_truncate (edge, edge_leader, 0); 2201169689Skan VEC_truncate (tree, stmt_list, 0); 2202169689Skan bitmap_clear (leader_has_match); 2203169689Skan return; 2204169689Skan } 2205169689Skan 2206169689Skan 2207169689Skan if (dump_file) 2208169689Skan fprintf (dump_file, "\nOpportunities in BB %d for stmt/block reduction:\n", 2209169689Skan bb->index); 2210169689Skan 2211169689Skan 2212169689Skan /* For each common list, create a forwarding block and issue the stmt's 2213169689Skan in that block. */ 2214169689Skan for (x = 0; VEC_iterate (edge, edge_leader, x, leader); x++) 2215169689Skan if (bitmap_bit_p (leader_has_match, x)) 2216169689Skan { 2217169689Skan edge new_edge; 2218169689Skan block_stmt_iterator bsi; 2219169689Skan tree curr_stmt_list; 2220169689Skan 2221169689Skan leader_match = leader; 2222169689Skan 2223169689Skan /* The tree_* cfg manipulation routines use the PENDING_EDGE field 2224169689Skan for various PHI manipulations, so it gets cleared when calls are 2225169689Skan made to make_forwarder_block(). So make sure the edge is clear, 2226169689Skan and use the saved stmt list. */ 2227169689Skan PENDING_STMT (leader) = NULL; 2228169689Skan leader->aux = leader; 2229169689Skan curr_stmt_list = VEC_index (tree, stmt_list, x); 2230169689Skan 2231169689Skan new_edge = make_forwarder_block (leader->dest, same_stmt_list_p, 2232169689Skan NULL); 2233169689Skan bb = new_edge->dest; 2234169689Skan if (dump_file) 2235169689Skan { 2236169689Skan fprintf (dump_file, "Splitting BB %d for Common stmt list. ", 2237169689Skan leader->dest->index); 2238169689Skan fprintf (dump_file, "Original block is now BB%d.\n", bb->index); 2239169689Skan print_generic_stmt (dump_file, curr_stmt_list, TDF_VOPS); 2240169689Skan } 2241169689Skan 2242169689Skan FOR_EACH_EDGE (e, ei, new_edge->src->preds) 2243169689Skan { 2244169689Skan e->aux = NULL; 2245169689Skan if (dump_file) 2246169689Skan fprintf (dump_file, " Edge (%d->%d) lands here.\n", 2247169689Skan e->src->index, e->dest->index); 2248169689Skan } 2249169689Skan 2250169689Skan bsi = bsi_last (leader->dest); 2251169689Skan bsi_insert_after (&bsi, curr_stmt_list, BSI_NEW_STMT); 2252169689Skan 2253169689Skan leader_match = NULL; 2254169689Skan /* We should never get a new block now. */ 2255169689Skan } 2256169689Skan else 2257169689Skan { 2258169689Skan PENDING_STMT (leader) = VEC_index (tree, stmt_list, x); 2259169689Skan bsi_commit_one_edge_insert (leader, NULL); 2260169689Skan } 2261169689Skan 2262169689Skan 2263169689Skan /* Clear the working data structures. */ 2264169689Skan VEC_truncate (edge, edge_leader, 0); 2265169689Skan VEC_truncate (tree, stmt_list, 0); 2266169689Skan bitmap_clear (leader_has_match); 2267169689Skan} 2268169689Skan 2269169689Skan 2270169689Skan/* This function will analyze the insertions which were performed on edges, 2271169689Skan and decide whether they should be left on that edge, or whether it is more 2272169689Skan efficient to emit some subset of them in a single block. All stmts are 2273169689Skan inserted somewhere. */ 2274169689Skan 2275169689Skanstatic void 2276169689Skanperform_edge_inserts (void) 2277169689Skan{ 2278169689Skan basic_block bb; 2279169689Skan 2280169689Skan if (dump_file) 2281169689Skan fprintf(dump_file, "Analyzing Edge Insertions.\n"); 2282169689Skan 2283169689Skan /* analyze_edges_for_bb calls make_forwarder_block, which tries to 2284169689Skan incrementally update the dominator information. Since we don't 2285169689Skan need dominator information after this pass, go ahead and free the 2286169689Skan dominator information. */ 2287169689Skan free_dominance_info (CDI_DOMINATORS); 2288169689Skan free_dominance_info (CDI_POST_DOMINATORS); 2289169689Skan 2290169689Skan /* Allocate data structures used in analyze_edges_for_bb. */ 2291169689Skan init_analyze_edges_for_bb (); 2292169689Skan 2293169689Skan FOR_EACH_BB (bb) 2294169689Skan analyze_edges_for_bb (bb); 2295169689Skan 2296169689Skan analyze_edges_for_bb (EXIT_BLOCK_PTR); 2297169689Skan 2298169689Skan /* Free data structures used in analyze_edges_for_bb. */ 2299169689Skan fini_analyze_edges_for_bb (); 2300169689Skan 2301169689Skan#ifdef ENABLE_CHECKING 2302169689Skan { 2303169689Skan edge_iterator ei; 2304169689Skan edge e; 2305169689Skan FOR_EACH_BB (bb) 2306169689Skan { 2307169689Skan FOR_EACH_EDGE (e, ei, bb->preds) 2308169689Skan { 2309169689Skan if (PENDING_STMT (e)) 2310169689Skan error (" Pending stmts not issued on PRED edge (%d, %d)\n", 2311169689Skan e->src->index, e->dest->index); 2312169689Skan } 2313169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 2314169689Skan { 2315169689Skan if (PENDING_STMT (e)) 2316169689Skan error (" Pending stmts not issued on SUCC edge (%d, %d)\n", 2317169689Skan e->src->index, e->dest->index); 2318169689Skan } 2319169689Skan } 2320169689Skan FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs) 2321169689Skan { 2322169689Skan if (PENDING_STMT (e)) 2323169689Skan error (" Pending stmts not issued on ENTRY edge (%d, %d)\n", 2324169689Skan e->src->index, e->dest->index); 2325169689Skan } 2326169689Skan FOR_EACH_EDGE (e, ei, EXIT_BLOCK_PTR->preds) 2327169689Skan { 2328169689Skan if (PENDING_STMT (e)) 2329169689Skan error (" Pending stmts not issued on EXIT edge (%d, %d)\n", 2330169689Skan e->src->index, e->dest->index); 2331169689Skan } 2332169689Skan } 2333169689Skan#endif 2334169689Skan} 2335169689Skan 2336169689Skan 2337169689Skan/* Remove the variables specified in MAP from SSA form. FLAGS indicate what 2338169689Skan options should be used. */ 2339169689Skan 2340169689Skanstatic void 2341169689Skanremove_ssa_form (var_map map, int flags) 2342169689Skan{ 2343169689Skan tree_live_info_p liveinfo; 2344169689Skan basic_block bb; 2345169689Skan tree phi, next; 2346169689Skan tree *values = NULL; 2347169689Skan 2348169689Skan /* If we are not combining temps, don't calculate live ranges for variables 2349169689Skan with only one SSA version. */ 2350169689Skan if ((flags & SSANORM_COMBINE_TEMPS) == 0) 2351169689Skan compact_var_map (map, VARMAP_NO_SINGLE_DEFS); 2352169689Skan else 2353169689Skan compact_var_map (map, VARMAP_NORMAL); 2354169689Skan 2355169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2356169689Skan dump_var_map (dump_file, map); 2357169689Skan 2358169689Skan liveinfo = coalesce_ssa_name (map, flags); 2359169689Skan 2360169689Skan /* Make sure even single occurrence variables are in the list now. */ 2361169689Skan if ((flags & SSANORM_COMBINE_TEMPS) == 0) 2362169689Skan compact_var_map (map, VARMAP_NORMAL); 2363169689Skan 2364169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2365169689Skan { 2366169689Skan fprintf (dump_file, "After Coalescing:\n"); 2367169689Skan dump_var_map (dump_file, map); 2368169689Skan } 2369169689Skan 2370169689Skan if (flags & SSANORM_PERFORM_TER) 2371169689Skan { 2372169689Skan values = find_replaceable_exprs (map); 2373169689Skan if (values && dump_file && (dump_flags & TDF_DETAILS)) 2374169689Skan dump_replaceable_exprs (dump_file, values); 2375169689Skan } 2376169689Skan 2377169689Skan /* Assign real variables to the partitions now. */ 2378169689Skan assign_vars (map); 2379169689Skan 2380169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2381169689Skan { 2382169689Skan fprintf (dump_file, "After Root variable replacement:\n"); 2383169689Skan dump_var_map (dump_file, map); 2384169689Skan } 2385169689Skan 2386169689Skan if ((flags & SSANORM_COMBINE_TEMPS) && liveinfo) 2387169689Skan { 2388169689Skan coalesce_vars (map, liveinfo); 2389169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2390169689Skan { 2391169689Skan fprintf (dump_file, "After variable memory coalescing:\n"); 2392169689Skan dump_var_map (dump_file, map); 2393169689Skan } 2394169689Skan } 2395169689Skan 2396169689Skan if (liveinfo) 2397169689Skan delete_tree_live_info (liveinfo); 2398169689Skan 2399169689Skan rewrite_trees (map, values); 2400169689Skan 2401169689Skan if (values) 2402169689Skan free (values); 2403169689Skan 2404169689Skan /* Remove phi nodes which have been translated back to real variables. */ 2405169689Skan FOR_EACH_BB (bb) 2406169689Skan { 2407169689Skan for (phi = phi_nodes (bb); phi; phi = next) 2408169689Skan { 2409169689Skan next = PHI_CHAIN (phi); 2410169689Skan remove_phi_node (phi, NULL_TREE); 2411169689Skan } 2412169689Skan } 2413169689Skan 2414169689Skan /* we no longer maintain the SSA operand cache at this point. */ 2415169689Skan fini_ssa_operands (); 2416169689Skan 2417169689Skan /* If any copies were inserted on edges, analyze and insert them now. */ 2418169689Skan perform_edge_inserts (); 2419169689Skan} 2420169689Skan 2421169689Skan/* Search every PHI node for arguments associated with backedges which 2422169689Skan we can trivially determine will need a copy (the argument is either 2423169689Skan not an SSA_NAME or the argument has a different underlying variable 2424169689Skan than the PHI result). 2425169689Skan 2426169689Skan Insert a copy from the PHI argument to a new destination at the 2427169689Skan end of the block with the backedge to the top of the loop. Update 2428169689Skan the PHI argument to reference this new destination. */ 2429169689Skan 2430169689Skanstatic void 2431169689Skaninsert_backedge_copies (void) 2432169689Skan{ 2433169689Skan basic_block bb; 2434169689Skan 2435169689Skan FOR_EACH_BB (bb) 2436169689Skan { 2437169689Skan tree phi; 2438169689Skan 2439169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 2440169689Skan { 2441169689Skan tree result = PHI_RESULT (phi); 2442169689Skan tree result_var; 2443169689Skan int i; 2444169689Skan 2445169689Skan if (!is_gimple_reg (result)) 2446169689Skan continue; 2447169689Skan 2448169689Skan result_var = SSA_NAME_VAR (result); 2449169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 2450169689Skan { 2451169689Skan tree arg = PHI_ARG_DEF (phi, i); 2452169689Skan edge e = PHI_ARG_EDGE (phi, i); 2453169689Skan 2454169689Skan /* If the argument is not an SSA_NAME, then we will 2455169689Skan need a constant initialization. If the argument is 2456169689Skan an SSA_NAME with a different underlying variable and 2457169689Skan we are not combining temporaries, then we will 2458169689Skan need a copy statement. */ 2459169689Skan if ((e->flags & EDGE_DFS_BACK) 2460169689Skan && (TREE_CODE (arg) != SSA_NAME 2461169689Skan || (!flag_tree_combine_temps 2462169689Skan && SSA_NAME_VAR (arg) != result_var))) 2463169689Skan { 2464169689Skan tree stmt, name, last = NULL; 2465169689Skan block_stmt_iterator bsi; 2466169689Skan 2467169689Skan bsi = bsi_last (PHI_ARG_EDGE (phi, i)->src); 2468169689Skan if (!bsi_end_p (bsi)) 2469169689Skan last = bsi_stmt (bsi); 2470169689Skan 2471169689Skan /* In theory the only way we ought to get back to the 2472169689Skan start of a loop should be with a COND_EXPR or GOTO_EXPR. 2473169689Skan However, better safe than sorry. 2474169689Skan 2475169689Skan If the block ends with a control statement or 2476169689Skan something that might throw, then we have to 2477169689Skan insert this assignment before the last 2478169689Skan statement. Else insert it after the last statement. */ 2479169689Skan if (last && stmt_ends_bb_p (last)) 2480169689Skan { 2481169689Skan /* If the last statement in the block is the definition 2482169689Skan site of the PHI argument, then we can't insert 2483169689Skan anything after it. */ 2484169689Skan if (TREE_CODE (arg) == SSA_NAME 2485169689Skan && SSA_NAME_DEF_STMT (arg) == last) 2486169689Skan continue; 2487169689Skan } 2488169689Skan 2489169689Skan /* Create a new instance of the underlying 2490169689Skan variable of the PHI result. */ 2491169689Skan stmt = build2 (MODIFY_EXPR, TREE_TYPE (result_var), 2492169689Skan NULL_TREE, PHI_ARG_DEF (phi, i)); 2493169689Skan name = make_ssa_name (result_var, stmt); 2494169689Skan TREE_OPERAND (stmt, 0) = name; 2495169689Skan 2496169689Skan /* Insert the new statement into the block and update 2497169689Skan the PHI node. */ 2498169689Skan if (last && stmt_ends_bb_p (last)) 2499169689Skan bsi_insert_before (&bsi, stmt, BSI_NEW_STMT); 2500169689Skan else 2501169689Skan bsi_insert_after (&bsi, stmt, BSI_NEW_STMT); 2502169689Skan SET_PHI_ARG_DEF (phi, i, name); 2503169689Skan } 2504169689Skan } 2505169689Skan } 2506169689Skan } 2507169689Skan} 2508169689Skan 2509169689Skan/* Take the current function out of SSA form, as described in 2510169689Skan R. Morgan, ``Building an Optimizing Compiler'', 2511169689Skan Butterworth-Heinemann, Boston, MA, 1998. pp 176-186. */ 2512169689Skan 2513169689Skanstatic unsigned int 2514169689Skanrewrite_out_of_ssa (void) 2515169689Skan{ 2516169689Skan var_map map; 2517169689Skan int var_flags = 0; 2518169689Skan int ssa_flags = 0; 2519169689Skan 2520169689Skan /* If elimination of a PHI requires inserting a copy on a backedge, 2521169689Skan then we will have to split the backedge which has numerous 2522169689Skan undesirable performance effects. 2523169689Skan 2524169689Skan A significant number of such cases can be handled here by inserting 2525169689Skan copies into the loop itself. */ 2526169689Skan insert_backedge_copies (); 2527169689Skan 2528169689Skan if (!flag_tree_live_range_split) 2529169689Skan ssa_flags |= SSANORM_COALESCE_PARTITIONS; 2530169689Skan 2531169689Skan eliminate_virtual_phis (); 2532169689Skan 2533169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2534169689Skan dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); 2535169689Skan 2536169689Skan /* We cannot allow unssa to un-gimplify trees before we instrument them. */ 2537169689Skan if (flag_tree_ter && !flag_mudflap) 2538169689Skan var_flags = SSA_VAR_MAP_REF_COUNT; 2539169689Skan 2540169689Skan map = create_ssa_var_map (var_flags); 2541169689Skan 2542169689Skan if (flag_tree_combine_temps) 2543169689Skan ssa_flags |= SSANORM_COMBINE_TEMPS; 2544169689Skan if (flag_tree_ter && !flag_mudflap) 2545169689Skan ssa_flags |= SSANORM_PERFORM_TER; 2546169689Skan 2547169689Skan remove_ssa_form (map, ssa_flags); 2548169689Skan 2549169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 2550169689Skan dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS); 2551169689Skan 2552169689Skan /* Flush out flow graph and SSA data. */ 2553169689Skan delete_var_map (map); 2554169689Skan 2555169689Skan in_ssa_p = false; 2556169689Skan return 0; 2557169689Skan} 2558169689Skan 2559169689Skan 2560169689Skan/* Define the parameters of the out of SSA pass. */ 2561169689Skan 2562169689Skanstruct tree_opt_pass pass_del_ssa = 2563169689Skan{ 2564169689Skan "optimized", /* name */ 2565169689Skan NULL, /* gate */ 2566169689Skan rewrite_out_of_ssa, /* execute */ 2567169689Skan NULL, /* sub */ 2568169689Skan NULL, /* next */ 2569169689Skan 0, /* static_pass_number */ 2570169689Skan TV_TREE_SSA_TO_NORMAL, /* tv_id */ 2571169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 2572169689Skan 0, /* properties_provided */ 2573169689Skan /* ??? If TER is enabled, we also kill gimple. */ 2574169689Skan PROP_ssa, /* properties_destroyed */ 2575169689Skan TODO_verify_ssa | TODO_verify_flow 2576169689Skan | TODO_verify_stmts, /* todo_flags_start */ 2577169689Skan TODO_dump_func 2578169689Skan | TODO_ggc_collect 2579169689Skan | TODO_remove_unused_locals, /* todo_flags_finish */ 2580169689Skan 0 /* letter */ 2581169689Skan}; 2582