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