Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-copyrename.c @ 56:3c8a44c06a95
Added tag gcc-4.4.5 for changeset 77e2b8dfacca
| author | ryoma <e075725@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Fri, 12 Feb 2010 23:41:23 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Rename SSA copies. |
| 2 Copyright (C) 2004, 2006, 2007, 2008 Free Software Foundation, Inc. | |
| 3 Contributed by Andrew MacLeod <amacleod@redhat.com> | |
| 4 | |
| 5 This file is part of GCC. | |
| 6 | |
| 7 GCC is free software; you can redistribute it and/or modify | |
| 8 it under the terms of the GNU General Public License as published by | |
| 9 the Free Software Foundation; either version 3, or (at your option) | |
| 10 any later version. | |
| 11 | |
| 12 GCC is distributed in the hope that it will be useful, | |
| 13 but WITHOUT ANY WARRANTY; without even the implied warranty of | |
| 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
| 15 GNU General Public License for more details. | |
| 16 | |
| 17 You should have received a copy of the GNU General Public License | |
| 18 along 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
53 If this copy couldn't be copy propagated, it could possibly remain in the |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
54 program throughout the optimization phases. After SSA->normal, it would |
| 0 | 55 become: |
| 56 | |
| 57 T.3 = <blah> | |
| 58 a = T.3 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
59 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
60 Since T.3_5 is distinct from all other SSA versions of T.3, there is no |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
61 fundamental reason why the base variable needs to be T.3, subject to |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
62 certain restrictions. This optimization attempts to determine if we can |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
68 This gives the SSA->normal pass a shot at coalescing a_1 and a_5. If it is |
| 0 | 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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
82 get turned into |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
83 |
| 0 | 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: | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
102 |
| 0 | 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 | |
| 112 static bool | |
| 113 copy_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 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
190 /* Never attempt to coalesce 2 user variables unless one is an inline |
| 0 | 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; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
198 else |
| 0 | 199 { |
| 200 if (debug) | |
| 201 fprintf (debug, " : 2 different USER vars. No coalesce.\n"); | |
| 202 return false; | |
| 203 } | |
| 204 } | |
| 205 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
206 /* If both values have default defs, we can't coalesce. If only one has a |
| 0 | 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 { | |
| 231 if (debug) | |
| 232 fprintf (debug, " : Incompatible types. No coalesce.\n"); | |
| 233 return false; | |
| 234 } | |
| 235 | |
| 236 /* Merge the two partitions. */ | |
| 237 p3 = partition_union (map->var_partition, p1, p2); | |
| 238 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
239 /* Set the root variable of the partition to the better choice, if there is |
| 0 | 240 one. */ |
| 241 if (!ign2) | |
| 242 replace_ssa_name_symbol (partition_to_var (map, p3), root2); | |
| 243 else if (!ign1) | |
| 244 replace_ssa_name_symbol (partition_to_var (map, p3), root1); | |
| 245 | |
| 246 if (debug) | |
| 247 { | |
| 248 fprintf (debug, " --> P%d ", p3); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
249 print_generic_expr (debug, SSA_NAME_VAR (partition_to_var (map, p3)), |
| 0 | 250 TDF_SLIM); |
| 251 fprintf (debug, "\n"); | |
| 252 } | |
| 253 return true; | |
| 254 } | |
| 255 | |
| 256 | |
| 257 /* This function will make a pass through the IL, and attempt to coalesce any | |
| 258 SSA versions which occur in PHI's or copies. Coalescing is accomplished by | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
259 changing the underlying root variable of all coalesced version. This will |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
260 then cause the SSA->normal pass to attempt to coalesce them all to the same |
| 0 | 261 variable. */ |
| 262 | |
| 263 static unsigned int | |
| 264 rename_ssa_copies (void) | |
| 265 { | |
| 266 var_map map; | |
| 267 basic_block bb; | |
| 268 gimple_stmt_iterator gsi; | |
| 269 tree var, part_var; | |
| 270 gimple stmt, phi; | |
| 271 unsigned x; | |
| 272 FILE *debug; | |
| 273 bool updated = false; | |
| 274 | |
| 275 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 276 debug = dump_file; | |
| 277 else | |
| 278 debug = NULL; | |
| 279 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
280 map = init_var_map (num_ssa_names); |
| 0 | 281 |
| 282 FOR_EACH_BB (bb) | |
| 283 { | |
| 284 /* Scan for real copies. */ | |
| 285 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 286 { | |
| 287 stmt = gsi_stmt (gsi); | |
| 288 if (gimple_assign_ssa_name_copy_p (stmt)) | |
| 289 { | |
| 290 tree lhs = gimple_assign_lhs (stmt); | |
| 291 tree rhs = gimple_assign_rhs1 (stmt); | |
| 292 | |
| 293 updated |= copy_rename_partition_coalesce (map, lhs, rhs, debug); | |
| 294 } | |
| 295 } | |
| 296 } | |
| 297 | |
| 298 FOR_EACH_BB (bb) | |
| 299 { | |
| 300 /* Treat PHI nodes as copies between the result and each argument. */ | |
| 301 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
| 302 { | |
| 303 size_t i; | |
| 304 tree res; | |
| 305 | |
| 306 phi = gsi_stmt (gsi); | |
| 307 res = gimple_phi_result (phi); | |
| 308 | |
| 309 /* Do not process virtual SSA_NAMES. */ | |
| 310 if (!is_gimple_reg (SSA_NAME_VAR (res))) | |
| 311 continue; | |
| 312 | |
| 313 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 314 { | |
| 315 tree arg = gimple_phi_arg (phi, i)->def; | |
| 316 if (TREE_CODE (arg) == SSA_NAME) | |
| 317 updated |= copy_rename_partition_coalesce (map, res, arg, debug); | |
| 318 } | |
| 319 } | |
| 320 } | |
| 321 | |
| 322 if (debug) | |
| 323 dump_var_map (debug, map); | |
| 324 | |
| 325 /* Now one more pass to make all elements of a partition share the same | |
| 326 root variable. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
327 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
328 for (x = 1; x < num_ssa_names; x++) |
| 0 | 329 { |
| 330 part_var = partition_to_var (map, x); | |
| 331 if (!part_var) | |
| 332 continue; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
333 var = ssa_name (x); |
| 0 | 334 if (debug) |
| 335 { | |
| 336 if (SSA_NAME_VAR (var) != SSA_NAME_VAR (part_var)) | |
| 337 { | |
| 338 fprintf (debug, "Coalesced "); | |
| 339 print_generic_expr (debug, var, TDF_SLIM); | |
| 340 fprintf (debug, " to "); | |
| 341 print_generic_expr (debug, part_var, TDF_SLIM); | |
| 342 fprintf (debug, "\n"); | |
| 343 } | |
| 344 } | |
| 345 replace_ssa_name_symbol (var, SSA_NAME_VAR (part_var)); | |
| 346 } | |
| 347 | |
| 348 delete_var_map (map); | |
| 349 return updated ? TODO_remove_unused_locals : 0; | |
| 350 } | |
| 351 | |
| 352 /* Return true if copy rename is to be performed. */ | |
| 353 | |
| 354 static bool | |
| 355 gate_copyrename (void) | |
| 356 { | |
| 357 return flag_tree_copyrename != 0; | |
| 358 } | |
| 359 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
360 struct gimple_opt_pass pass_rename_ssa_copies = |
| 0 | 361 { |
| 362 { | |
| 363 GIMPLE_PASS, | |
| 364 "copyrename", /* name */ | |
| 365 gate_copyrename, /* gate */ | |
| 366 rename_ssa_copies, /* execute */ | |
| 367 NULL, /* sub */ | |
| 368 NULL, /* next */ | |
| 369 0, /* static_pass_number */ | |
| 370 TV_TREE_COPY_RENAME, /* tv_id */ | |
| 371 PROP_cfg | PROP_ssa, /* properties_required */ | |
| 372 0, /* properties_provided */ | |
| 373 0, /* properties_destroyed */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
374 0, /* todo_flags_start */ |
| 0 | 375 TODO_dump_func | TODO_verify_ssa /* todo_flags_finish */ |
| 376 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
377 }; |