1169689Skan/* Rename SSA copies. 2169689Skan Copyright (C) 2004 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 "basic-block.h" 29169689Skan#include "function.h" 30169689Skan#include "diagnostic.h" 31169689Skan#include "bitmap.h" 32169689Skan#include "tree-flow.h" 33169689Skan#include "tree-gimple.h" 34169689Skan#include "tree-inline.h" 35169689Skan#include "timevar.h" 36169689Skan#include "hashtab.h" 37169689Skan#include "tree-dump.h" 38169689Skan#include "tree-ssa-live.h" 39169689Skan#include "tree-pass.h" 40169689Skan#include "langhooks.h" 41169689Skan 42169689Skan/* The following routines implement the SSA copy renaming phase. 43169689Skan 44169689Skan This optimization looks for copies between 2 SSA_NAMES, either through a 45169689Skan direct copy, or an implicit one via a PHI node result and its arguments. 46169689Skan 47169689Skan Each copy is examined to determine if it is possible to rename the base 48169689Skan variable of one of the operands to the same variable as the other operand. 49169689Skan i.e. 50169689Skan T.3_5 = <blah> 51169689Skan a_1 = T.3_5 52169689Skan 53169689Skan If this copy couldn't be copy propagated, it could possibly remain in the 54169689Skan program throughout the optimization phases. After SSA->normal, it would 55169689Skan become: 56169689Skan 57169689Skan T.3 = <blah> 58169689Skan a = T.3 59169689Skan 60169689Skan Since T.3_5 is distinct from all other SSA versions of T.3, there is no 61169689Skan fundamental reason why the base variable needs to be T.3, subject to 62169689Skan certain restrictions. This optimization attempts to determine if we can 63169689Skan change the base variable on copies like this, and result in code such as: 64169689Skan 65169689Skan a_5 = <blah> 66169689Skan a_1 = a_5 67169689Skan 68169689Skan This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is 69169689Skan possible, the copy goes away completely. If it isn't possible, a new temp 70169689Skan will be created for a_5, and you will end up with the exact same code: 71169689Skan 72169689Skan a.8 = <blah> 73169689Skan a = a.8 74169689Skan 75169689Skan The other benefit of performing this optimization relates to what variables 76169689Skan are chosen in copies. Gimplification of the program uses temporaries for 77169689Skan a lot of things. expressions like 78169689Skan 79169689Skan a_1 = <blah> 80169689Skan <blah2> = a_1 81169689Skan 82169689Skan get turned into 83169689Skan 84169689Skan T.3_5 = <blah> 85169689Skan a_1 = T.3_5 86169689Skan <blah2> = a_1 87169689Skan 88169689Skan Copy propagation is done in a forward direction, and if we can propagate 89169689Skan through the copy, we end up with: 90169689Skan 91169689Skan T.3_5 = <blah> 92169689Skan <blah2> = T.3_5 93169689Skan 94169689Skan The copy is gone, but so is all reference to the user variable 'a'. By 95169689Skan performing this optimization, we would see the sequence: 96169689Skan 97169689Skan a_5 = <blah> 98169689Skan a_1 = a_5 99169689Skan <blah2> = a_1 100169689Skan 101169689Skan which copy propagation would then turn into: 102169689Skan 103169689Skan a_5 = <blah> 104169689Skan <blah2> = a_5 105169689Skan 106169689Skan and so we still retain the user variable whenever possible. */ 107169689Skan 108169689Skan 109169689Skan/* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid. 110169689Skan Choose a representative for the partition, and send debug info to DEBUG. */ 111169689Skan 112169689Skanstatic void 113169689Skancopy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug) 114169689Skan{ 115169689Skan int p1, p2, p3; 116169689Skan tree root1, root2; 117169689Skan tree rep1, rep2; 118169689Skan var_ann_t ann1, ann2, ann3; 119169689Skan bool ign1, ign2, abnorm; 120169689Skan 121169689Skan gcc_assert (TREE_CODE (var1) == SSA_NAME); 122169689Skan gcc_assert (TREE_CODE (var2) == SSA_NAME); 123169689Skan 124169689Skan register_ssa_partition (map, var1, false); 125169689Skan register_ssa_partition (map, var2, true); 126169689Skan 127169689Skan p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 128169689Skan p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 129169689Skan 130169689Skan if (debug) 131169689Skan { 132169689Skan fprintf (debug, "Try : "); 133169689Skan print_generic_expr (debug, var1, TDF_SLIM); 134169689Skan fprintf (debug, "(P%d) & ", p1); 135169689Skan print_generic_expr (debug, var2, TDF_SLIM); 136169689Skan fprintf (debug, "(P%d)", p2); 137169689Skan } 138169689Skan 139169689Skan gcc_assert (p1 != NO_PARTITION); 140169689Skan gcc_assert (p2 != NO_PARTITION); 141169689Skan 142169689Skan rep1 = partition_to_var (map, p1); 143169689Skan rep2 = partition_to_var (map, p2); 144169689Skan root1 = SSA_NAME_VAR (rep1); 145169689Skan root2 = SSA_NAME_VAR (rep2); 146169689Skan 147169689Skan ann1 = var_ann (root1); 148169689Skan ann2 = var_ann (root2); 149169689Skan 150169689Skan if (p1 == p2) 151169689Skan { 152169689Skan if (debug) 153169689Skan fprintf (debug, " : Already coalesced.\n"); 154169689Skan return; 155169689Skan } 156169689Skan 157169689Skan /* Don't coalesce if one of the variables occurs in an abnormal PHI. */ 158169689Skan abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1) 159169689Skan || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2)); 160169689Skan if (abnorm) 161169689Skan { 162169689Skan if (debug) 163169689Skan fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n"); 164169689Skan return; 165169689Skan } 166169689Skan 167169689Skan /* Partitions already have the same root, simply merge them. */ 168169689Skan if (root1 == root2) 169169689Skan { 170169689Skan p1 = partition_union (map->var_partition, p1, p2); 171169689Skan if (debug) 172169689Skan fprintf (debug, " : Same root, coalesced --> P%d.\n", p1); 173169689Skan return; 174169689Skan } 175169689Skan 176169689Skan /* Never attempt to coalesce 2 difference parameters. */ 177169689Skan if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL) 178169689Skan { 179169689Skan if (debug) 180169689Skan fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n"); 181169689Skan return; 182169689Skan } 183169689Skan 184169689Skan if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL)) 185169689Skan { 186169689Skan if (debug) 187169689Skan fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n"); 188169689Skan return; 189169689Skan } 190169689Skan 191169689Skan ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1); 192169689Skan ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2); 193169689Skan 194169689Skan /* Never attempt to coalesce 2 user variables unless one is an inline 195169689Skan variable. */ 196169689Skan if (!ign1 && !ign2) 197169689Skan { 198169689Skan if (DECL_FROM_INLINE (root2)) 199169689Skan ign2 = true; 200169689Skan else if (DECL_FROM_INLINE (root1)) 201169689Skan ign1 = true; 202169689Skan else 203169689Skan { 204169689Skan if (debug) 205169689Skan fprintf (debug, " : 2 different USER vars. No coalesce.\n"); 206169689Skan return; 207169689Skan } 208169689Skan } 209169689Skan 210169689Skan /* Don't coalesce if there are two different memory tags. */ 211169689Skan if (ann1->symbol_mem_tag 212169689Skan && ann2->symbol_mem_tag 213169689Skan && ann1->symbol_mem_tag != ann2->symbol_mem_tag) 214169689Skan { 215169689Skan if (debug) 216169689Skan fprintf (debug, " : 2 memory tags. No coalesce.\n"); 217169689Skan return; 218169689Skan } 219169689Skan 220169689Skan /* If both values have default defs, we can't coalesce. If only one has a 221169689Skan tag, make sure that variable is the new root partition. */ 222169689Skan if (default_def (root1)) 223169689Skan { 224169689Skan if (default_def (root2)) 225169689Skan { 226169689Skan if (debug) 227169689Skan fprintf (debug, " : 2 default defs. No coalesce.\n"); 228169689Skan return; 229169689Skan } 230169689Skan else 231169689Skan { 232169689Skan ign2 = true; 233169689Skan ign1 = false; 234169689Skan } 235169689Skan } 236169689Skan else if (default_def (root2)) 237169689Skan { 238169689Skan ign1 = true; 239169689Skan ign2 = false; 240169689Skan } 241169689Skan 242169689Skan /* Don't coalesce if the two variables aren't type compatible. */ 243169689Skan if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2))) 244169689Skan { 245169689Skan if (debug) 246169689Skan fprintf (debug, " : Incompatible types. No coalesce.\n"); 247169689Skan return; 248169689Skan } 249169689Skan 250169689Skan /* Don't coalesce if the aliasing sets of the types are different. */ 251169689Skan if (POINTER_TYPE_P (TREE_TYPE (root1)) 252169689Skan && POINTER_TYPE_P (TREE_TYPE (root2)) 253169689Skan && get_alias_set (TREE_TYPE (TREE_TYPE (root1))) 254169689Skan != get_alias_set (TREE_TYPE (TREE_TYPE (root2)))) 255169689Skan { 256169689Skan if (debug) 257169689Skan fprintf (debug, " : 2 different aliasing sets. No coalesce.\n"); 258169689Skan return; 259169689Skan } 260169689Skan 261169689Skan 262169689Skan /* Merge the two partitions. */ 263169689Skan p3 = partition_union (map->var_partition, p1, p2); 264169689Skan 265169689Skan /* Set the root variable of the partition to the better choice, if there is 266169689Skan one. */ 267169689Skan if (!ign2) 268169689Skan replace_ssa_name_symbol (partition_to_var (map, p3), root2); 269169689Skan else if (!ign1) 270169689Skan replace_ssa_name_symbol (partition_to_var (map, p3), root1); 271169689Skan 272169689Skan /* Update the various flag widgitry of the current base representative. */ 273169689Skan ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3))); 274169689Skan if (ann1->symbol_mem_tag) 275169689Skan ann3->symbol_mem_tag = ann1->symbol_mem_tag; 276169689Skan else 277169689Skan ann3->symbol_mem_tag = ann2->symbol_mem_tag; 278169689Skan 279169689Skan if (debug) 280169689Skan { 281169689Skan fprintf (debug, " --> P%d ", p3); 282169689Skan print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)), 283169689Skan TDF_SLIM); 284169689Skan fprintf (debug, "\n"); 285169689Skan } 286169689Skan} 287169689Skan 288169689Skan 289169689Skan/* This function will make a pass through the IL, and attempt to coalesce any 290169689Skan SSA versions which occur in PHI's or copies. Coalescing is accomplished by 291169689Skan changing the underlying root variable of all coalesced version. This will 292169689Skan then cause the SSA->normal pass to attempt to coalesce them all to the same 293169689Skan variable. */ 294169689Skan 295169689Skanstatic unsigned int 296169689Skanrename_ssa_copies (void) 297169689Skan{ 298169689Skan var_map map; 299169689Skan basic_block bb; 300169689Skan block_stmt_iterator bsi; 301169689Skan tree phi, stmt, var, part_var; 302169689Skan unsigned x; 303169689Skan FILE *debug; 304169689Skan 305169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 306169689Skan debug = dump_file; 307169689Skan else 308169689Skan debug = NULL; 309169689Skan 310169689Skan map = init_var_map (num_ssa_names + 1); 311169689Skan 312169689Skan FOR_EACH_BB (bb) 313169689Skan { 314169689Skan /* Scan for real copies. */ 315169689Skan for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 316169689Skan { 317169689Skan stmt = bsi_stmt (bsi); 318169689Skan if (TREE_CODE (stmt) == MODIFY_EXPR) 319169689Skan { 320169689Skan tree lhs = TREE_OPERAND (stmt, 0); 321169689Skan tree rhs = TREE_OPERAND (stmt, 1); 322169689Skan 323169689Skan if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) 324169689Skan copy_rename_partition_coalesce (map, lhs, rhs, debug); 325169689Skan } 326169689Skan } 327169689Skan } 328169689Skan 329169689Skan FOR_EACH_BB (bb) 330169689Skan { 331169689Skan /* Treat PHI nodes as copies between the result and each argument. */ 332169689Skan for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 333169689Skan { 334169689Skan int i; 335169689Skan tree res = PHI_RESULT (phi); 336169689Skan 337169689Skan /* Do not process virtual SSA_NAMES. */ 338169689Skan if (!is_gimple_reg (SSA_NAME_VAR (res))) 339169689Skan continue; 340169689Skan 341169689Skan for (i = 0; i < PHI_NUM_ARGS (phi); i++) 342169689Skan { 343169689Skan tree arg = PHI_ARG_DEF (phi, i); 344169689Skan if (TREE_CODE (arg) == SSA_NAME) 345169689Skan copy_rename_partition_coalesce (map, res, arg, debug); 346169689Skan } 347169689Skan } 348169689Skan } 349169689Skan 350169689Skan if (debug) 351169689Skan dump_var_map (debug, map); 352169689Skan 353169689Skan /* Now one more pass to make all elements of a partition share the same 354169689Skan root variable. */ 355169689Skan 356169689Skan for (x = 1; x <= num_ssa_names; x++) 357169689Skan { 358169689Skan part_var = partition_to_var (map, x); 359169689Skan if (!part_var) 360169689Skan continue; 361169689Skan var = map->partition_to_var[x]; 362169689Skan if (debug) 363169689Skan { 364169689Skan if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var)) 365169689Skan { 366169689Skan fprintf (debug, "Coalesced "); 367169689Skan print_generic_expr (debug, var, TDF_SLIM); 368169689Skan fprintf (debug, " to "); 369169689Skan print_generic_expr (debug, part_var, TDF_SLIM); 370169689Skan fprintf (debug, "\n"); 371169689Skan } 372169689Skan } 373169689Skan replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var)); 374169689Skan } 375169689Skan 376169689Skan delete_var_map (map); 377169689Skan return 0; 378169689Skan} 379169689Skan 380169689Skan/* Return true if copy rename is to be performed. */ 381169689Skan 382169689Skanstatic bool 383169689Skangate_copyrename (void) 384169689Skan{ 385169689Skan return flag_tree_copyrename != 0; 386169689Skan} 387169689Skan 388169689Skanstruct tree_opt_pass pass_rename_ssa_copies = 389169689Skan{ 390169689Skan "copyrename", /* name */ 391169689Skan gate_copyrename, /* gate */ 392169689Skan rename_ssa_copies, /* execute */ 393169689Skan NULL, /* sub */ 394169689Skan NULL, /* next */ 395169689Skan 0, /* static_pass_number */ 396169689Skan TV_TREE_COPY_RENAME, /* tv_id */ 397169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 398169689Skan 0, /* properties_provided */ 399169689Skan 0, /* properties_destroyed */ 400169689Skan 0, /* todo_flags_start */ 401169689Skan TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 402169689Skan 0 /* letter */ 403169689Skan}; 404169689Skan 405