Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-sink.c @ 59:5b5b9ea5b220
fix
| author | Shinji KONO <kono@ie.u-ryukyu.ac.jp> |
|---|---|
| date | Mon, 15 Feb 2010 17:22:24 +0900 |
| parents | 77e2b8dfacca |
| children | b7f97abdc517 |
| rev | line source |
|---|---|
| 0 | 1 /* Code sinking for trees |
| 2 Copyright (C) 2001, 2002, 2003, 2004, 2007, 2008, 2009 | |
| 3 Free Software Foundation, Inc. | |
| 4 Contributed by Daniel Berlin <dan@dberlin.org> | |
| 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 "ggc.h" | |
| 27 #include "tree.h" | |
| 28 #include "basic-block.h" | |
| 29 #include "diagnostic.h" | |
| 30 #include "tree-inline.h" | |
| 31 #include "tree-flow.h" | |
| 32 #include "gimple.h" | |
| 33 #include "tree-dump.h" | |
| 34 #include "timevar.h" | |
| 35 #include "fibheap.h" | |
| 36 #include "hashtab.h" | |
| 37 #include "tree-iterator.h" | |
| 38 #include "real.h" | |
| 39 #include "alloc-pool.h" | |
| 40 #include "tree-pass.h" | |
| 41 #include "flags.h" | |
| 42 #include "bitmap.h" | |
| 43 #include "langhooks.h" | |
| 44 #include "cfgloop.h" | |
| 45 | |
| 46 /* TODO: | |
| 47 1. Sinking store only using scalar promotion (IE without moving the RHS): | |
| 48 | |
| 49 *q = p; | |
| 50 p = p + 1; | |
| 51 if (something) | |
| 52 *q = <not p>; | |
| 53 else | |
| 54 y = *q; | |
| 55 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
56 |
| 0 | 57 should become |
| 58 sinktemp = p; | |
| 59 p = p + 1; | |
| 60 if (something) | |
| 61 *q = <not p>; | |
| 62 else | |
| 63 { | |
| 64 *q = sinktemp; | |
| 65 y = *q | |
| 66 } | |
| 67 Store copy propagation will take care of the store elimination above. | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
68 |
| 0 | 69 |
| 70 2. Sinking using Partial Dead Code Elimination. */ | |
| 71 | |
| 72 | |
| 73 static struct | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
74 { |
| 0 | 75 /* The number of statements sunk down the flowgraph by code sinking. */ |
| 76 int sunk; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
77 |
| 0 | 78 } sink_stats; |
| 79 | |
| 80 | |
| 81 /* Given a PHI, and one of its arguments (DEF), find the edge for | |
| 82 that argument and return it. If the argument occurs twice in the PHI node, | |
| 83 we return NULL. */ | |
| 84 | |
| 85 static basic_block | |
| 86 find_bb_for_arg (gimple phi, tree def) | |
| 87 { | |
| 88 size_t i; | |
| 89 bool foundone = false; | |
| 90 basic_block result = NULL; | |
| 91 for (i = 0; i < gimple_phi_num_args (phi); i++) | |
| 92 if (PHI_ARG_DEF (phi, i) == def) | |
| 93 { | |
| 94 if (foundone) | |
| 95 return NULL; | |
| 96 foundone = true; | |
| 97 result = gimple_phi_arg_edge (phi, i)->src; | |
| 98 } | |
| 99 return result; | |
| 100 } | |
| 101 | |
| 102 /* When the first immediate use is in a statement, then return true if all | |
| 103 immediate uses in IMM are in the same statement. | |
| 104 We could also do the case where the first immediate use is in a phi node, | |
| 105 and all the other uses are in phis in the same basic block, but this | |
| 106 requires some expensive checking later (you have to make sure no def/vdef | |
| 107 in the statement occurs for multiple edges in the various phi nodes it's | |
| 108 used in, so that you only have one place you can sink it to. */ | |
| 109 | |
| 110 static bool | |
| 111 all_immediate_uses_same_place (gimple stmt) | |
| 112 { | |
| 113 gimple firstuse = NULL; | |
| 114 ssa_op_iter op_iter; | |
| 115 imm_use_iterator imm_iter; | |
| 116 use_operand_p use_p; | |
| 117 tree var; | |
| 118 | |
| 119 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) | |
| 120 { | |
| 121 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) | |
| 122 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
123 if (is_gimple_debug (USE_STMT (use_p))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
124 continue; |
| 0 | 125 if (firstuse == NULL) |
| 126 firstuse = USE_STMT (use_p); | |
| 127 else | |
| 128 if (firstuse != USE_STMT (use_p)) | |
| 129 return false; | |
| 130 } | |
| 131 } | |
| 132 | |
| 133 return true; | |
| 134 } | |
| 135 | |
| 136 /* Some global stores don't necessarily have VDEF's of global variables, | |
| 137 but we still must avoid moving them around. */ | |
| 138 | |
| 139 bool | |
| 140 is_hidden_global_store (gimple stmt) | |
| 141 { | |
| 142 /* Check virtual definitions. If we get here, the only virtual | |
| 143 definitions we should see are those generated by assignment or call | |
| 144 statements. */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
145 if (gimple_vdef (stmt)) |
| 0 | 146 { |
| 147 tree lhs; | |
| 148 | |
| 149 gcc_assert (is_gimple_assign (stmt) || is_gimple_call (stmt)); | |
| 150 | |
| 151 /* Note that we must not check the individual virtual operands | |
| 152 here. In particular, if this is an aliased store, we could | |
| 153 end up with something like the following (SSA notation | |
| 154 redacted for brevity): | |
| 155 | |
| 156 foo (int *p, int i) | |
| 157 { | |
| 158 int x; | |
| 159 p_1 = (i_2 > 3) ? &x : p; | |
| 160 | |
| 161 # x_4 = VDEF <x_3> | |
| 162 *p_1 = 5; | |
| 163 | |
| 164 return 2; | |
| 165 } | |
| 166 | |
| 167 Notice that the store to '*p_1' should be preserved, if we | |
| 168 were to check the virtual definitions in that store, we would | |
| 169 not mark it needed. This is because 'x' is not a global | |
| 170 variable. | |
| 171 | |
| 172 Therefore, we check the base address of the LHS. If the | |
| 173 address is a pointer, we check if its name tag or symbol tag is | |
| 174 a global variable. Otherwise, we check if the base variable | |
| 175 is a global. */ | |
| 176 lhs = gimple_get_lhs (stmt); | |
| 177 | |
| 178 if (REFERENCE_CLASS_P (lhs)) | |
| 179 lhs = get_base_address (lhs); | |
| 180 | |
| 181 if (lhs == NULL_TREE) | |
| 182 { | |
| 183 /* If LHS is NULL, it means that we couldn't get the base | |
| 184 address of the reference. In which case, we should not | |
| 185 move this store. */ | |
| 186 return true; | |
| 187 } | |
| 188 else if (DECL_P (lhs)) | |
| 189 { | |
| 190 /* If the store is to a global symbol, we need to keep it. */ | |
| 191 if (is_global_var (lhs)) | |
| 192 return true; | |
| 193 | |
| 194 } | |
| 195 else if (INDIRECT_REF_P (lhs)) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
196 return ptr_deref_may_alias_global_p (TREE_OPERAND (lhs, 0)); |
| 0 | 197 else |
| 198 gcc_unreachable (); | |
| 199 } | |
| 200 | |
| 201 return false; | |
| 202 } | |
| 203 | |
| 204 /* Find the nearest common dominator of all of the immediate uses in IMM. */ | |
| 205 | |
| 206 static basic_block | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
207 nearest_common_dominator_of_uses (gimple stmt, bool *debug_stmts) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
208 { |
| 0 | 209 bitmap blocks = BITMAP_ALLOC (NULL); |
| 210 basic_block commondom; | |
| 211 unsigned int j; | |
| 212 bitmap_iterator bi; | |
| 213 ssa_op_iter op_iter; | |
| 214 imm_use_iterator imm_iter; | |
| 215 use_operand_p use_p; | |
| 216 tree var; | |
| 217 | |
| 218 bitmap_clear (blocks); | |
| 219 FOR_EACH_SSA_TREE_OPERAND (var, stmt, op_iter, SSA_OP_ALL_DEFS) | |
| 220 { | |
| 221 FOR_EACH_IMM_USE_FAST (use_p, imm_iter, var) | |
| 222 { | |
| 223 gimple usestmt = USE_STMT (use_p); | |
| 224 basic_block useblock; | |
| 225 | |
| 226 if (gimple_code (usestmt) == GIMPLE_PHI) | |
| 227 { | |
| 228 int idx = PHI_ARG_INDEX_FROM_USE (use_p); | |
| 229 | |
| 230 useblock = gimple_phi_arg_edge (usestmt, idx)->src; | |
| 231 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
232 else if (is_gimple_debug (usestmt)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
233 { |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
234 *debug_stmts = true; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
235 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
236 } |
| 0 | 237 else |
| 238 { | |
| 239 useblock = gimple_bb (usestmt); | |
| 240 } | |
| 241 | |
| 242 /* Short circuit. Nothing dominates the entry block. */ | |
| 243 if (useblock == ENTRY_BLOCK_PTR) | |
| 244 { | |
| 245 BITMAP_FREE (blocks); | |
| 246 return NULL; | |
| 247 } | |
| 248 bitmap_set_bit (blocks, useblock->index); | |
| 249 } | |
| 250 } | |
| 251 commondom = BASIC_BLOCK (bitmap_first_set_bit (blocks)); | |
| 252 EXECUTE_IF_SET_IN_BITMAP (blocks, 0, j, bi) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
253 commondom = nearest_common_dominator (CDI_DOMINATORS, commondom, |
| 0 | 254 BASIC_BLOCK (j)); |
| 255 BITMAP_FREE (blocks); | |
| 256 return commondom; | |
| 257 } | |
| 258 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
259 /* Given a statement (STMT) and the basic block it is currently in (FROMBB), |
| 0 | 260 determine the location to sink the statement to, if any. |
| 261 Returns true if there is such location; in that case, TOGSI points to the | |
| 262 statement before that STMT should be moved. */ | |
| 263 | |
| 264 static bool | |
| 265 statement_sink_location (gimple stmt, basic_block frombb, | |
| 266 gimple_stmt_iterator *togsi) | |
| 267 { | |
| 268 gimple use; | |
| 269 tree def; | |
| 270 use_operand_p one_use = NULL_USE_OPERAND_P; | |
| 271 basic_block sinkbb; | |
| 272 use_operand_p use_p; | |
| 273 def_operand_p def_p; | |
| 274 ssa_op_iter iter; | |
| 275 imm_use_iterator imm_iter; | |
| 276 | |
| 277 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) | |
| 278 { | |
| 279 FOR_EACH_IMM_USE_FAST (one_use, imm_iter, def) | |
| 280 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
281 if (is_gimple_debug (USE_STMT (one_use))) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
282 continue; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
283 |
| 0 | 284 break; |
| 285 } | |
| 286 if (one_use != NULL_USE_OPERAND_P) | |
| 287 break; | |
| 288 } | |
| 289 | |
| 290 /* Return if there are no immediate uses of this stmt. */ | |
| 291 if (one_use == NULL_USE_OPERAND_P) | |
| 292 return false; | |
| 293 | |
| 294 if (gimple_code (stmt) != GIMPLE_ASSIGN) | |
| 295 return false; | |
| 296 | |
| 297 /* There are a few classes of things we can't or don't move, some because we | |
| 298 don't have code to handle it, some because it's not profitable and some | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
299 because it's not legal. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
300 |
| 0 | 301 We can't sink things that may be global stores, at least not without |
| 302 calculating a lot more information, because we may cause it to no longer | |
| 303 be seen by an external routine that needs it depending on where it gets | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
304 moved to. |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
305 |
| 0 | 306 We don't want to sink loads from memory. |
| 307 | |
| 308 We can't sink statements that end basic blocks without splitting the | |
| 309 incoming edge for the sink location to place it there. | |
| 310 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
311 We can't sink statements that have volatile operands. |
| 0 | 312 |
| 313 We don't want to sink dead code, so anything with 0 immediate uses is not | |
| 314 sunk. | |
| 315 | |
| 316 Don't sink BLKmode assignments if current function has any local explicit | |
| 317 register variables, as BLKmode assignments may involve memcpy or memset | |
| 318 calls or, on some targets, inline expansion thereof that sometimes need | |
| 319 to use specific hard registers. | |
| 320 | |
| 321 */ | |
| 322 if (stmt_ends_bb_p (stmt) | |
| 323 || gimple_has_side_effects (stmt) | |
| 324 || is_hidden_global_store (stmt) | |
| 325 || gimple_has_volatile_ops (stmt) | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
326 || gimple_vuse (stmt) |
| 0 | 327 || (cfun->has_local_explicit_reg_vars |
| 328 && TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt))) == BLKmode)) | |
| 329 return false; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
330 |
| 0 | 331 FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS) |
| 332 { | |
| 333 tree def = DEF_FROM_PTR (def_p); | |
| 334 if (is_global_var (SSA_NAME_VAR (def)) | |
| 335 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (def)) | |
| 336 return false; | |
| 337 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
338 |
| 0 | 339 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_ALL_USES) |
| 340 { | |
| 341 tree use = USE_FROM_PTR (use_p); | |
| 342 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (use)) | |
| 343 return false; | |
| 344 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
345 |
| 0 | 346 /* If all the immediate uses are not in the same place, find the nearest |
| 347 common dominator of all the immediate uses. For PHI nodes, we have to | |
| 348 find the nearest common dominator of all of the predecessor blocks, since | |
| 349 that is where insertion would have to take place. */ | |
| 350 if (!all_immediate_uses_same_place (stmt)) | |
| 351 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
352 bool debug_stmts = false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
353 basic_block commondom = nearest_common_dominator_of_uses (stmt, |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
354 &debug_stmts); |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
355 |
| 0 | 356 if (commondom == frombb) |
| 357 return false; | |
| 358 | |
| 359 /* Our common dominator has to be dominated by frombb in order to be a | |
| 360 trivially safe place to put this statement, since it has multiple | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
361 uses. */ |
| 0 | 362 if (!dominated_by_p (CDI_DOMINATORS, commondom, frombb)) |
| 363 return false; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
364 |
| 0 | 365 /* It doesn't make sense to move to a dominator that post-dominates |
| 366 frombb, because it means we've just moved it into a path that always | |
| 367 executes if frombb executes, instead of reducing the number of | |
| 368 executions . */ | |
| 369 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, commondom)) | |
| 370 { | |
| 371 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 372 fprintf (dump_file, "Not moving store, common dominator post-dominates from block.\n"); | |
| 373 return false; | |
| 374 } | |
| 375 | |
| 376 if (commondom == frombb || commondom->loop_depth > frombb->loop_depth) | |
| 377 return false; | |
| 378 if (dump_file && (dump_flags & TDF_DETAILS)) | |
| 379 { | |
| 380 fprintf (dump_file, "Common dominator of all uses is %d\n", | |
| 381 commondom->index); | |
| 382 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
383 |
| 0 | 384 *togsi = gsi_after_labels (commondom); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
385 |
| 0 | 386 return true; |
| 387 } | |
| 388 | |
| 389 use = USE_STMT (one_use); | |
| 390 if (gimple_code (use) != GIMPLE_PHI) | |
| 391 { | |
| 392 sinkbb = gimple_bb (use); | |
| 393 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth | |
| 394 || sinkbb->loop_father != frombb->loop_father) | |
| 395 return false; | |
| 396 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
397 /* Move the expression to a post dominator can't reduce the number of |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
398 executions. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
399 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
400 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
401 |
| 0 | 402 *togsi = gsi_for_stmt (use); |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
403 |
| 0 | 404 return true; |
| 405 } | |
| 406 | |
| 407 /* Note that at this point, all uses must be in the same statement, so it | |
| 408 doesn't matter which def op we choose, pick the first one. */ | |
| 409 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) | |
| 410 break; | |
| 411 | |
| 412 sinkbb = find_bb_for_arg (use, def); | |
| 413 if (!sinkbb) | |
| 414 return false; | |
| 415 | |
| 416 /* This will happen when you have | |
| 417 a_3 = PHI <a_13, a_26> | |
| 418 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
419 a_26 = VDEF <a_3> |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
420 |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
421 If the use is a phi, and is in the same bb as the def, |
| 0 | 422 we can't sink it. */ |
| 423 | |
| 424 if (gimple_bb (use) == frombb) | |
| 425 return false; | |
| 426 if (sinkbb == frombb || sinkbb->loop_depth > frombb->loop_depth | |
| 427 || sinkbb->loop_father != frombb->loop_father) | |
| 428 return false; | |
| 429 | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
430 /* Move the expression to a post dominator can't reduce the number of |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
431 executions. */ |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
432 if (dominated_by_p (CDI_POST_DOMINATORS, frombb, sinkbb)) |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
433 return false; |
|
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
434 |
| 0 | 435 *togsi = gsi_after_labels (sinkbb); |
| 436 | |
| 437 return true; | |
| 438 } | |
| 439 | |
| 440 /* Perform code sinking on BB */ | |
| 441 | |
| 442 static void | |
| 443 sink_code_in_bb (basic_block bb) | |
| 444 { | |
| 445 basic_block son; | |
| 446 gimple_stmt_iterator gsi; | |
| 447 edge_iterator ei; | |
| 448 edge e; | |
| 449 bool last = true; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
450 |
| 0 | 451 /* If this block doesn't dominate anything, there can't be any place to sink |
| 452 the statements to. */ | |
| 453 if (first_dom_son (CDI_DOMINATORS, bb) == NULL) | |
| 454 goto earlyout; | |
| 455 | |
| 456 /* We can't move things across abnormal edges, so don't try. */ | |
| 457 FOR_EACH_EDGE (e, ei, bb->succs) | |
| 458 if (e->flags & EDGE_ABNORMAL) | |
| 459 goto earlyout; | |
| 460 | |
| 461 for (gsi = gsi_last_bb (bb); !gsi_end_p (gsi);) | |
| 462 { | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
463 gimple stmt = gsi_stmt (gsi); |
| 0 | 464 gimple_stmt_iterator togsi; |
| 465 | |
| 466 if (!statement_sink_location (stmt, bb, &togsi)) | |
| 467 { | |
| 468 if (!gsi_end_p (gsi)) | |
| 469 gsi_prev (&gsi); | |
| 470 last = false; | |
| 471 continue; | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
472 } |
| 0 | 473 if (dump_file) |
| 474 { | |
| 475 fprintf (dump_file, "Sinking "); | |
| 476 print_gimple_stmt (dump_file, stmt, 0, TDF_VOPS); | |
| 477 fprintf (dump_file, " from bb %d to bb %d\n", | |
| 478 bb->index, (gsi_bb (togsi))->index); | |
| 479 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
480 |
| 0 | 481 /* If this is the end of the basic block, we need to insert at the end |
| 482 of the basic block. */ | |
| 483 if (gsi_end_p (togsi)) | |
| 484 gsi_move_to_bb_end (&gsi, gsi_bb (togsi)); | |
| 485 else | |
| 486 gsi_move_before (&gsi, &togsi); | |
| 487 | |
| 488 sink_stats.sunk++; | |
| 489 | |
| 490 /* If we've just removed the last statement of the BB, the | |
| 491 gsi_end_p() test below would fail, but gsi_prev() would have | |
| 492 succeeded, and we want it to succeed. So we keep track of | |
| 493 whether we're at the last statement and pick up the new last | |
| 494 statement. */ | |
| 495 if (last) | |
| 496 { | |
| 497 gsi = gsi_last_bb (bb); | |
| 498 continue; | |
| 499 } | |
| 500 | |
| 501 last = false; | |
| 502 if (!gsi_end_p (gsi)) | |
| 503 gsi_prev (&gsi); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
504 |
| 0 | 505 } |
| 506 earlyout: | |
| 507 for (son = first_dom_son (CDI_POST_DOMINATORS, bb); | |
| 508 son; | |
| 509 son = next_dom_son (CDI_POST_DOMINATORS, son)) | |
| 510 { | |
| 511 sink_code_in_bb (son); | |
| 512 } | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
513 } |
| 0 | 514 |
| 515 /* Perform code sinking. | |
| 516 This moves code down the flowgraph when we know it would be | |
| 517 profitable to do so, or it wouldn't increase the number of | |
| 518 executions of the statement. | |
| 519 | |
| 520 IE given | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
521 |
| 0 | 522 a_1 = b + c; |
| 523 if (<something>) | |
| 524 { | |
| 525 } | |
| 526 else | |
| 527 { | |
| 528 foo (&b, &c); | |
| 529 a_5 = b + c; | |
| 530 } | |
| 531 a_6 = PHI (a_5, a_1); | |
| 532 USE a_6. | |
| 533 | |
| 534 we'll transform this into: | |
| 535 | |
| 536 if (<something>) | |
| 537 { | |
| 538 a_1 = b + c; | |
| 539 } | |
| 540 else | |
| 541 { | |
| 542 foo (&b, &c); | |
| 543 a_5 = b + c; | |
| 544 } | |
| 545 a_6 = PHI (a_5, a_1); | |
| 546 USE a_6. | |
| 547 | |
| 548 Note that this reduces the number of computations of a = b + c to 1 | |
| 549 when we take the else edge, instead of 2. | |
| 550 */ | |
| 551 static void | |
| 552 execute_sink_code (void) | |
| 553 { | |
| 554 loop_optimizer_init (LOOPS_NORMAL); | |
| 555 | |
| 556 connect_infinite_loops_to_exit (); | |
| 557 memset (&sink_stats, 0, sizeof (sink_stats)); | |
| 558 calculate_dominance_info (CDI_DOMINATORS); | |
| 559 calculate_dominance_info (CDI_POST_DOMINATORS); | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
560 sink_code_in_bb (EXIT_BLOCK_PTR); |
| 0 | 561 statistics_counter_event (cfun, "Sunk statements", sink_stats.sunk); |
| 562 free_dominance_info (CDI_POST_DOMINATORS); | |
| 563 remove_fake_exit_edges (); | |
| 564 loop_optimizer_finalize (); | |
| 565 } | |
| 566 | |
| 567 /* Gate and execute functions for PRE. */ | |
| 568 | |
| 569 static unsigned int | |
| 570 do_sink (void) | |
| 571 { | |
| 572 execute_sink_code (); | |
| 573 return 0; | |
| 574 } | |
| 575 | |
| 576 static bool | |
| 577 gate_sink (void) | |
| 578 { | |
| 579 return flag_tree_sink != 0; | |
| 580 } | |
| 581 | |
| 582 struct gimple_opt_pass pass_sink_code = | |
| 583 { | |
| 584 { | |
| 585 GIMPLE_PASS, | |
| 586 "sink", /* name */ | |
| 587 gate_sink, /* gate */ | |
| 588 do_sink, /* execute */ | |
| 589 NULL, /* sub */ | |
| 590 NULL, /* next */ | |
| 591 0, /* static_pass_number */ | |
| 592 TV_TREE_SINK, /* tv_id */ | |
| 593 PROP_no_crit_edges | PROP_cfg | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
594 | PROP_ssa, /* properties_required */ |
| 0 | 595 0, /* properties_provided */ |
| 596 0, /* properties_destroyed */ | |
| 597 0, /* todo_flags_start */ | |
|
55
77e2b8dfacca
update it from 4.4.3 to 4.5.0
ryoma <e075725@ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
598 TODO_update_ssa |
| 0 | 599 | TODO_dump_func |
| 600 | TODO_ggc_collect | |
| 601 | TODO_verify_ssa /* todo_flags_finish */ | |
| 602 } | |
| 603 }; |