tree-ssa-copyrename.c revision 267654
1/* Rename SSA copies. 2 Copyright (C) 2004 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 2, 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 COPYING. If not, write to 19the Free Software Foundation, 51 Franklin Street, Fifth Floor, 20Boston, MA 02110-1301, USA. */ 21 22#include "config.h" 23#include "system.h" 24#include "coretypes.h" 25#include "tm.h" 26#include "tree.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 "tree-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 void 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 var_ann_t ann1, ann2, ann3; 119 bool ign1, ign2, abnorm; 120 121 gcc_assert (TREE_CODE (var1) == SSA_NAME); 122 gcc_assert (TREE_CODE (var2) == SSA_NAME); 123 124 register_ssa_partition (map, var1, false); 125 register_ssa_partition (map, var2, true); 126 127 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 128 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 129 130 if (debug) 131 { 132 fprintf (debug, "Try : "); 133 print_generic_expr (debug, var1, TDF_SLIM); 134 fprintf (debug, "(P%d) & ", p1); 135 print_generic_expr (debug, var2, TDF_SLIM); 136 fprintf (debug, "(P%d)", p2); 137 } 138 139 gcc_assert (p1 != NO_PARTITION); 140 gcc_assert (p2 != NO_PARTITION); 141 142 rep1 = partition_to_var (map, p1); 143 rep2 = partition_to_var (map, p2); 144 root1 = SSA_NAME_VAR (rep1); 145 root2 = SSA_NAME_VAR (rep2); 146 147 ann1 = var_ann (root1); 148 ann2 = var_ann (root2); 149 150 if (p1 == p2) 151 { 152 if (debug) 153 fprintf (debug, " : Already coalesced.\n"); 154 return; 155 } 156 157 /* Don't coalesce if one of the variables occurs in an abnormal PHI. */ 158 abnorm = (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep1) 159 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (rep2)); 160 if (abnorm) 161 { 162 if (debug) 163 fprintf (debug, " : Abnormal PHI barrier. No coalesce.\n"); 164 return; 165 } 166 167 /* Partitions already have the same root, simply merge them. */ 168 if (root1 == root2) 169 { 170 p1 = partition_union (map->var_partition, p1, p2); 171 if (debug) 172 fprintf (debug, " : Same root, coalesced --> P%d.\n", p1); 173 return; 174 } 175 176 /* Never attempt to coalesce 2 difference parameters. */ 177 if (TREE_CODE (root1) == PARM_DECL && TREE_CODE (root2) == PARM_DECL) 178 { 179 if (debug) 180 fprintf (debug, " : 2 different PARM_DECLS. No coalesce.\n"); 181 return; 182 } 183 184 if ((TREE_CODE (root1) == RESULT_DECL) != (TREE_CODE (root2) == RESULT_DECL)) 185 { 186 if (debug) 187 fprintf (debug, " : One root a RESULT_DECL. No coalesce.\n"); 188 return; 189 } 190 191 ign1 = TREE_CODE (root1) == VAR_DECL && DECL_IGNORED_P (root1); 192 ign2 = TREE_CODE (root2) == VAR_DECL && DECL_IGNORED_P (root2); 193 194 /* Never attempt to coalesce 2 user variables unless one is an inline 195 variable. */ 196 if (!ign1 && !ign2) 197 { 198 if (DECL_FROM_INLINE (root2)) 199 ign2 = true; 200 else if (DECL_FROM_INLINE (root1)) 201 ign1 = true; 202 else 203 { 204 if (debug) 205 fprintf (debug, " : 2 different USER vars. No coalesce.\n"); 206 return; 207 } 208 } 209 210 /* Don't coalesce if there are two different memory tags. */ 211 if (ann1->symbol_mem_tag 212 && ann2->symbol_mem_tag 213 && ann1->symbol_mem_tag != ann2->symbol_mem_tag) 214 { 215 if (debug) 216 fprintf (debug, " : 2 memory tags. No coalesce.\n"); 217 return; 218 } 219 220 /* If both values have default defs, we can't coalesce. If only one has a 221 tag, make sure that variable is the new root partition. */ 222 if (default_def (root1)) 223 { 224 if (default_def (root2)) 225 { 226 if (debug) 227 fprintf (debug, " : 2 default defs. No coalesce.\n"); 228 return; 229 } 230 else 231 { 232 ign2 = true; 233 ign1 = false; 234 } 235 } 236 else if (default_def (root2)) 237 { 238 ign1 = true; 239 ign2 = false; 240 } 241 242 /* Don't coalesce if the two variables aren't type compatible. */ 243 if (!lang_hooks.types_compatible_p (TREE_TYPE (root1), TREE_TYPE (root2))) 244 { 245 if (debug) 246 fprintf (debug, " : Incompatible types. No coalesce.\n"); 247 return; 248 } 249 250 /* Don't coalesce if the aliasing sets of the types are different. */ 251 if (POINTER_TYPE_P (TREE_TYPE (root1)) 252 && POINTER_TYPE_P (TREE_TYPE (root2)) 253 && get_alias_set (TREE_TYPE (TREE_TYPE (root1))) 254 != get_alias_set (TREE_TYPE (TREE_TYPE (root2)))) 255 { 256 if (debug) 257 fprintf (debug, " : 2 different aliasing sets. No coalesce.\n"); 258 return; 259 } 260 261 262 /* Merge the two partitions. */ 263 p3 = partition_union (map->var_partition, p1, p2); 264 265 /* Set the root variable of the partition to the better choice, if there is 266 one. */ 267 if (!ign2) 268 replace_ssa_name_symbol (partition_to_var (map, p3), root2); 269 else if (!ign1) 270 replace_ssa_name_symbol (partition_to_var (map, p3), root1); 271 272 /* Update the various flag widgitry of the current base representative. */ 273 ann3 = var_ann (SSA_NAME_VAR (partition_to_var (map, p3))); 274 if (ann1->symbol_mem_tag) 275 ann3->symbol_mem_tag = ann1->symbol_mem_tag; 276 else 277 ann3->symbol_mem_tag = ann2->symbol_mem_tag; 278 279 if (debug) 280 { 281 fprintf (debug, " --> P%d ", p3); 282 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)), 283 TDF_SLIM); 284 fprintf (debug, "\n"); 285 } 286} 287 288 289/* This function will make a pass through the IL, and attempt to coalesce any 290 SSA versions which occur in PHI's or copies. Coalescing is accomplished by 291 changing the underlying root variable of all coalesced version. This will 292 then cause the SSA->normal pass to attempt to coalesce them all to the same 293 variable. */ 294 295static unsigned int 296rename_ssa_copies (void) 297{ 298 var_map map; 299 basic_block bb; 300 block_stmt_iterator bsi; 301 tree phi, stmt, var, part_var; 302 unsigned x; 303 FILE *debug; 304 305 if (dump_file && (dump_flags & TDF_DETAILS)) 306 debug = dump_file; 307 else 308 debug = NULL; 309 310 map = init_var_map (num_ssa_names + 1); 311 312 FOR_EACH_BB (bb) 313 { 314 /* Scan for real copies. */ 315 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi)) 316 { 317 stmt = bsi_stmt (bsi); 318 if (TREE_CODE (stmt) == MODIFY_EXPR) 319 { 320 tree lhs = TREE_OPERAND (stmt, 0); 321 tree rhs = TREE_OPERAND (stmt, 1); 322 323 if (TREE_CODE (lhs) == SSA_NAME && TREE_CODE (rhs) == SSA_NAME) 324 copy_rename_partition_coalesce (map, lhs, rhs, debug); 325 } 326 } 327 } 328 329 FOR_EACH_BB (bb) 330 { 331 /* Treat PHI nodes as copies between the result and each argument. */ 332 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) 333 { 334 int i; 335 tree res = PHI_RESULT (phi); 336 337 /* Do not process virtual SSA_NAMES. */ 338 if (!is_gimple_reg (SSA_NAME_VAR (res))) 339 continue; 340 341 for (i = 0; i < PHI_NUM_ARGS (phi); i++) 342 { 343 tree arg = PHI_ARG_DEF (phi, i); 344 if (TREE_CODE (arg) == SSA_NAME) 345 copy_rename_partition_coalesce (map, res, arg, debug); 346 } 347 } 348 } 349 350 if (debug) 351 dump_var_map (debug, map); 352 353 /* Now one more pass to make all elements of a partition share the same 354 root variable. */ 355 356 for (x = 1; x <= num_ssa_names; x++) 357 { 358 part_var = partition_to_var (map, x); 359 if (!part_var) 360 continue; 361 var = map->partition_to_var[x]; 362 if (debug) 363 { 364 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var)) 365 { 366 fprintf (debug, "Coalesced "); 367 print_generic_expr (debug, var, TDF_SLIM); 368 fprintf (debug, " to "); 369 print_generic_expr (debug, part_var, TDF_SLIM); 370 fprintf (debug, "\n"); 371 } 372 } 373 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var)); 374 } 375 376 delete_var_map (map); 377 return 0; 378} 379 380/* Return true if copy rename is to be performed. */ 381 382static bool 383gate_copyrename (void) 384{ 385 return flag_tree_copyrename != 0; 386} 387 388struct tree_opt_pass pass_rename_ssa_copies = 389{ 390 "copyrename", /* name */ 391 gate_copyrename, /* gate */ 392 rename_ssa_copies, /* execute */ 393 NULL, /* sub */ 394 NULL, /* next */ 395 0, /* static_pass_number */ 396 TV_TREE_COPY_RENAME, /* tv_id */ 397 PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 398 0, /* properties_provided */ 399 0, /* properties_destroyed */ 400 0, /* todo_flags_start */ 401 TODO_dump_func | TODO_verify_ssa, /* todo_flags_finish */ 402 0 /* letter */ 403}; 404 405