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