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