1/* Rename SSA copies. 2 Copyright (C) 2004-2015 Free Software Foundation, Inc. 3 Contributed by Andrew MacLeod <amacleod@redhat.com> 4 5This file is part of GCC. 6 7GCC is free software; you can redistribute it and/or modify 8it under the terms of the GNU General Public License as published by 9the Free Software Foundation; either version 3, or (at your option) 10any later version. 11 12GCC is distributed in the hope that it will be useful, 13but WITHOUT ANY WARRANTY; without even the implied warranty of 14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15GNU General Public License for more details. 16 17You should have received a copy of the GNU General Public License 18along with GCC; see the file COPYING3. If not see 19<http://www.gnu.org/licenses/>. */ 20 21#include "config.h" 22#include "system.h" 23#include "coretypes.h" 24#include "tm.h" 25#include "hash-set.h" 26#include "machmode.h" 27#include "vec.h" 28#include "double-int.h" 29#include "input.h" 30#include "alias.h" 31#include "symtab.h" 32#include "wide-int.h" 33#include "inchash.h" 34#include "tree.h" 35#include "fold-const.h" 36#include "predict.h" 37#include "hard-reg-set.h" 38#include "function.h" 39#include "dominance.h" 40#include "cfg.h" 41#include "basic-block.h" 42#include "tree-ssa-alias.h" 43#include "internal-fn.h" 44#include "gimple-expr.h" 45#include "is-a.h" 46#include "gimple.h" 47#include "gimple-iterator.h" 48#include "flags.h" 49#include "tree-pretty-print.h" 50#include "bitmap.h" 51#include "gimple-ssa.h" 52#include "stringpool.h" 53#include "tree-ssanames.h" 54#include "hashtab.h" 55#include "rtl.h" 56#include "statistics.h" 57#include "real.h" 58#include "fixed-value.h" 59#include "insn-config.h" 60#include "expmed.h" 61#include "dojump.h" 62#include "explow.h" 63#include "calls.h" 64#include "emit-rtl.h" 65#include "varasm.h" 66#include "stmt.h" 67#include "expr.h" 68#include "tree-dfa.h" 69#include "tree-inline.h" 70#include "tree-ssa-live.h" 71#include "tree-pass.h" 72#include "langhooks.h" 73 74static struct 75{ 76 /* Number of copies coalesced. */ 77 int coalesced; 78} stats; 79 80/* The following routines implement the SSA copy renaming phase. 81 82 This optimization looks for copies between 2 SSA_NAMES, either through a 83 direct copy, or an implicit one via a PHI node result and its arguments. 84 85 Each copy is examined to determine if it is possible to rename the base 86 variable of one of the operands to the same variable as the other operand. 87 i.e. 88 T.3_5 = <blah> 89 a_1 = T.3_5 90 91 If this copy couldn't be copy propagated, it could possibly remain in the 92 program throughout the optimization phases. After SSA->normal, it would 93 become: 94 95 T.3 = <blah> 96 a = T.3 97 98 Since T.3_5 is distinct from all other SSA versions of T.3, there is no 99 fundamental reason why the base variable needs to be T.3, subject to 100 certain restrictions. This optimization attempts to determine if we can 101 change the base variable on copies like this, and result in code such as: 102 103 a_5 = <blah> 104 a_1 = a_5 105 106 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is 107 possible, the copy goes away completely. If it isn't possible, a new temp 108 will be created for a_5, and you will end up with the exact same code: 109 110 a.8 = <blah> 111 a = a.8 112 113 The other benefit of performing this optimization relates to what variables 114 are chosen in copies. Gimplification of the program uses temporaries for 115 a lot of things. expressions like 116 117 a_1 = <blah> 118 <blah2> = a_1 119 120 get turned into 121 122 T.3_5 = <blah> 123 a_1 = T.3_5 124 <blah2> = a_1 125 126 Copy propagation is done in a forward direction, and if we can propagate 127 through the copy, we end up with: 128 129 T.3_5 = <blah> 130 <blah2> = T.3_5 131 132 The copy is gone, but so is all reference to the user variable 'a'. By 133 performing this optimization, we would see the sequence: 134 135 a_5 = <blah> 136 a_1 = a_5 137 <blah2> = a_1 138 139 which copy propagation would then turn into: 140 141 a_5 = <blah> 142 <blah2> = a_5 143 144 and so we still retain the user variable whenever possible. */ 145 146 147/* Coalesce the partitions in MAP representing VAR1 and VAR2 if it is valid. 148 Choose a representative for the partition, and send debug info to DEBUG. */ 149 150static void 151copy_rename_partition_coalesce (var_map map, tree var1, tree var2, FILE *debug) 152{ 153 int p1, p2, p3; 154 tree root1, root2; 155 tree rep1, rep2; 156 bool ign1, ign2, abnorm; 157 158 gcc_assert (TREE_CODE (var1) == SSA_NAME); 159 gcc_assert (TREE_CODE (var2) == SSA_NAME); 160 161 register_ssa_partition (map, var1); 162 register_ssa_partition (map, var2); 163 164 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 165 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 166 167 if (debug) 168 { 169 fprintf (debug, "Try : "); 170 print_generic_expr (debug, var1, TDF_SLIM); 171 fprintf (debug, "(P%d) & ", p1); 172 print_generic_expr (debug, var2, TDF_SLIM); 173 fprintf (debug, "(P%d)", p2); 174 } 175 176 gcc_assert (p1 != NO_PARTITION); 177 gcc_assert (p2 != NO_PARTITION); 178 179 if (p1 == p2) 180 { 181 if (debug) 182 fprintf (debug, " : Already coalesced.\n"); 183 return; 184 } 185 186 rep1 = partition_to_var (map, p1); 187 rep2 = partition_to_var (map, p2); 188 root1 = SSA_NAME_VAR (rep1); 189 root2 = SSA_NAME_VAR (rep2); 190 if (!root1 && !root2) 191 return; 192 193 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */ 194 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1) 195 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2)); 196 if (abnorm) 197 { 198 if (debug) 199 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n"); 200 return; 201 } 202 203 /* Partitions already have the same root, simply merge them. */ 204 if (root1 == root2) 205 { 206 p1 = partition_union (map->var_partition, p1, p2); 207 if (debug) 208 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1); 209 return; 210 } 211 212 /* Never attempt to coalesce 2 different parameters. */ 213 if ((root1 && TREE_CODE (root1) == PARM_DECL) 214 && (root2 && TREE_CODE (root2) == PARM_DECL)) 215 { 216 if (debug) 217 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n"); 218 return; 219 } 220 221 if ((root1 && TREE_CODE (root1) == RESULT_DECL) 222 != (root2 && TREE_CODE (root2) == RESULT_DECL)) 223 { 224 if (debug) 225 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n"); 226 return; 227 } 228 229 ign1 = !root1 || (TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1)); 230 ign2 = !root2 || (TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2)); 231 232 /* Refrain from coalescing user variables, if requested. */ 233 if (!ign1 && !ign2) 234 { 235 if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root2)) 236 ign2 = true; 237 else if (flag_ssa_coalesce_vars && DECL_FROM_INLINE (root1)) 238 ign1 = true; 239 else if (flag_ssa_coalesce_vars != 2) 240 { 241 if (debug) 242 fprintf (debug, " : 2 different USER vars. No coalesce.\n"); 243 return; 244 } 245 else 246 ign2 = true; 247 } 248 249 /* If both values have default defs, we can't coalesce. If only one has a 250 tag, make sure that variable is the new root partition. */ 251 if (root1 && ssa_default_def (cfun, root1)) 252 { 253 if (root2 && ssa_default_def (cfun, root2)) 254 { 255 if (debug) 256 fprintf (debug, " : 2 default defs. No coalesce.\n"); 257 return; 258 } 259 else 260 { 261 ign2 = true; 262 ign1 = false; 263 } 264 } 265 else if (root2 && ssa_default_def (cfun, root2)) 266 { 267 ign1 = true; 268 ign2 = false; 269 } 270 271 /* Do not coalesce if we cannot assign a symbol to the partition. */ 272 if (!(!ign2 && root2) 273 && !(!ign1 && root1)) 274 { 275 if (debug) 276 fprintf (debug, " : Choosen variable has no root. No coalesce.\n"); 277 return; 278 } 279 280 /* Don't coalesce if the new chosen root variable would be read-only. 281 If both ign1 && ign2, then the root var of the larger partition 282 wins, so reject in that case if any of the root vars is TREE_READONLY. 283 Otherwise reject only if the root var, on which replace_ssa_name_symbol 284 will be called below, is readonly. */ 285 if (((root1 && TREE_READONLY (root1)) && ign2) 286 || ((root2 && TREE_READONLY (root2)) && ign1)) 287 { 288 if (debug) 289 fprintf (debug, " : Readonly variable. No coalesce.\n"); 290 return; 291 } 292 293 /* Don't coalesce if the two variables aren't type compatible . */ 294 if (!types_compatible_p (TREE_TYPE (var1), TREE_TYPE (var2)) 295 /* There is a disconnect between the middle-end type-system and 296 VRP, avoid coalescing enum types with different bounds. */ 297 || ((TREE_CODE (TREE_TYPE (var1)) == ENUMERAL_TYPE 298 || TREE_CODE (TREE_TYPE (var2)) == ENUMERAL_TYPE) 299 && TREE_TYPE (var1) != TREE_TYPE (var2))) 300 { 301 if (debug) 302 fprintf (debug, " : Incompatible types. No coalesce.\n"); 303 return; 304 } 305 306 /* Merge the two partitions. */ 307 p3 = partition_union (map->var_partition, p1, p2); 308 309 /* Set the root variable of the partition to the better choice, if there is 310 one. */ 311 if (!ign2 && root2) 312 replace_ssa_name_symbol (partition_to_var (map, p3), root2); 313 else if (!ign1 && root1) 314 replace_ssa_name_symbol (partition_to_var (map, p3), root1); 315 else 316 gcc_unreachable (); 317 318 if (debug) 319 { 320 fprintf (debug, " --> P%d ", p3); 321 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)), 322 TDF_SLIM); 323 fprintf (debug, "\n"); 324 } 325} 326 327 328namespace { 329 330const pass_data pass_data_rename_ssa_copies = 331{ 332 GIMPLE_PASS, /* type */ 333 "copyrename", /* name */ 334 OPTGROUP_NONE, /* optinfo_flags */ 335 TV_TREE_COPY_RENAME, /* tv_id */ 336 ( PROP_cfg | PROP_ssa ), /* properties_required */ 337 0, /* properties_provided */ 338 0, /* properties_destroyed */ 339 0, /* todo_flags_start */ 340 0, /* todo_flags_finish */ 341}; 342 343class pass_rename_ssa_copies : public gimple_opt_pass 344{ 345public: 346 pass_rename_ssa_copies (gcc::context *ctxt) 347 : gimple_opt_pass (pass_data_rename_ssa_copies, ctxt) 348 {} 349 350 /* opt_pass methods: */ 351 opt_pass * clone () { return new pass_rename_ssa_copies (m_ctxt); } 352 virtual bool gate (function *) { return flag_tree_copyrename != 0; } 353 virtual unsigned int execute (function *); 354 355}; // class pass_rename_ssa_copies 356 357/* This function will make a pass through the IL, and attempt to coalesce any 358 SSA versions which occur in PHI's or copies. Coalescing is accomplished by 359 changing the underlying root variable of all coalesced version. This will 360 then cause the SSA->normal pass to attempt to coalesce them all to the same 361 variable. */ 362 363unsigned int 364pass_rename_ssa_copies::execute (function *fun) 365{ 366 var_map map; 367 basic_block bb; 368 tree var, part_var; 369 gimple stmt; 370 unsigned x; 371 FILE *debug; 372 373 memset (&stats, 0, sizeof (stats)); 374 375 if (dump_file && (dump_flags & TDF_DETAILS)) 376 debug = dump_file; 377 else 378 debug = NULL; 379 380 map = init_var_map (num_ssa_names); 381 382 FOR_EACH_BB_FN (bb, fun) 383 { 384 /* Scan for real copies. */ 385 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 386 gsi_next (&gsi)) 387 { 388 stmt = gsi_stmt (gsi); 389 if (gimple_assign_ssa_name_copy_p (stmt)) 390 { 391 tree lhs = gimple_assign_lhs (stmt); 392 tree rhs = gimple_assign_rhs1 (stmt); 393 394 copy_rename_partition_coalesce (map, lhs, rhs, debug); 395 } 396 } 397 } 398 399 FOR_EACH_BB_FN (bb, fun) 400 { 401 /* Treat PHI nodes as copies between the result and each argument. */ 402 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 403 gsi_next (&gsi)) 404 { 405 size_t i; 406 tree res; 407 gphi *phi = gsi.phi (); 408 res = gimple_phi_result (phi); 409 410 /* Do not process virtual SSA_NAMES. */ 411 if (virtual_operand_p (res)) 412 continue; 413 414 /* Make sure to only use the same partition for an argument 415 as the result but never the other way around. */ 416 if (SSA_NAME_VAR (res) 417 && !DECL_IGNORED_P (SSA_NAME_VAR (res))) 418 for (i = 0; i < gimple_phi_num_args (phi); i++) 419 { 420 tree arg = PHI_ARG_DEF (phi, i); 421 if (TREE_CODE (arg) == SSA_NAME) 422 copy_rename_partition_coalesce (map, res, arg, 423 debug); 424 } 425 /* Else if all arguments are in the same partition try to merge 426 it with the result. */ 427 else 428 { 429 int all_p_same = -1; 430 int p = -1; 431 for (i = 0; i < gimple_phi_num_args (phi); i++) 432 { 433 tree arg = PHI_ARG_DEF (phi, i); 434 if (TREE_CODE (arg) != SSA_NAME) 435 { 436 all_p_same = 0; 437 break; 438 } 439 else if (all_p_same == -1) 440 { 441 p = partition_find (map->var_partition, 442 SSA_NAME_VERSION (arg)); 443 all_p_same = 1; 444 } 445 else if (all_p_same == 1 446 && p != partition_find (map->var_partition, 447 SSA_NAME_VERSION (arg))) 448 { 449 all_p_same = 0; 450 break; 451 } 452 } 453 if (all_p_same == 1) 454 copy_rename_partition_coalesce (map, res, 455 PHI_ARG_DEF (phi, 0), 456 debug); 457 } 458 } 459 } 460 461 if (debug) 462 dump_var_map (debug, map); 463 464 /* Now one more pass to make all elements of a partition share the same 465 root variable. */ 466 467 for (x = 1; x < num_ssa_names; x++) 468 { 469 part_var = partition_to_var (map, x); 470 if (!part_var) 471 continue; 472 var = ssa_name (x); 473 if (SSA_NAME_VAR (var) == SSA_NAME_VAR (part_var)) 474 continue; 475 if (debug) 476 { 477 fprintf (debug, "Coalesced "); 478 print_generic_expr (debug, var, TDF_SLIM); 479 fprintf (debug, " to "); 480 print_generic_expr (debug, part_var, TDF_SLIM); 481 fprintf (debug, "\n"); 482 } 483 stats.coalesced++; 484 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var)); 485 } 486 487 statistics_counter_event (fun, "copies coalesced", 488 stats.coalesced); 489 delete_var_map (map); 490 return 0; 491} 492 493} // anon namespace 494 495gimple_opt_pass * 496make_pass_rename_ssa_copies (gcc::context *ctxt) 497{ 498 return new pass_rename_ssa_copies (ctxt); 499} 500