Mercurial > hg > CbC > CbC_gcc
annotate gcc/tree-ssa-math-opts.c @ 52:c156f1bd5cd9
Added tag gcc-4.4.3 for changeset ae3a4bfb450b
author | kent <kent@cr.ie.u-ryukyu.ac.jp> |
---|---|
date | Sun, 07 Feb 2010 18:28:00 +0900 |
parents | 3bfb6c00c1e0 |
children | 77e2b8dfacca |
rev | line source |
---|---|
0 | 1 /* Global, SSA-based optimizations using mathematical identities. |
2 Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc. | |
3 | |
4 This file is part of GCC. | |
5 | |
6 GCC is free software; you can redistribute it and/or modify it | |
7 under the terms of the GNU General Public License as published by the | |
8 Free Software Foundation; either version 3, or (at your option) any | |
9 later version. | |
10 | |
11 GCC is distributed in the hope that it will be useful, but WITHOUT | |
12 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
14 for more details. | |
15 | |
16 You should have received a copy of the GNU General Public License | |
17 along with GCC; see the file COPYING3. If not see | |
18 <http://www.gnu.org/licenses/>. */ | |
19 | |
20 /* Currently, the only mini-pass in this file tries to CSE reciprocal | |
21 operations. These are common in sequences such as this one: | |
22 | |
23 modulus = sqrt(x*x + y*y + z*z); | |
24 x = x / modulus; | |
25 y = y / modulus; | |
26 z = z / modulus; | |
27 | |
28 that can be optimized to | |
29 | |
30 modulus = sqrt(x*x + y*y + z*z); | |
31 rmodulus = 1.0 / modulus; | |
32 x = x * rmodulus; | |
33 y = y * rmodulus; | |
34 z = z * rmodulus; | |
35 | |
36 We do this for loop invariant divisors, and with this pass whenever | |
37 we notice that a division has the same divisor multiple times. | |
38 | |
39 Of course, like in PRE, we don't insert a division if a dominator | |
40 already has one. However, this cannot be done as an extension of | |
41 PRE for several reasons. | |
42 | |
43 First of all, with some experiments it was found out that the | |
44 transformation is not always useful if there are only two divisions | |
45 hy the same divisor. This is probably because modern processors | |
46 can pipeline the divisions; on older, in-order processors it should | |
47 still be effective to optimize two divisions by the same number. | |
48 We make this a param, and it shall be called N in the remainder of | |
49 this comment. | |
50 | |
51 Second, if trapping math is active, we have less freedom on where | |
52 to insert divisions: we can only do so in basic blocks that already | |
53 contain one. (If divisions don't trap, instead, we can insert | |
54 divisions elsewhere, which will be in blocks that are common dominators | |
55 of those that have the division). | |
56 | |
57 We really don't want to compute the reciprocal unless a division will | |
58 be found. To do this, we won't insert the division in a basic block | |
59 that has less than N divisions *post-dominating* it. | |
60 | |
61 The algorithm constructs a subset of the dominator tree, holding the | |
62 blocks containing the divisions and the common dominators to them, | |
63 and walk it twice. The first walk is in post-order, and it annotates | |
64 each block with the number of divisions that post-dominate it: this | |
65 gives information on where divisions can be inserted profitably. | |
66 The second walk is in pre-order, and it inserts divisions as explained | |
67 above, and replaces divisions by multiplications. | |
68 | |
69 In the best case, the cost of the pass is O(n_statements). In the | |
70 worst-case, the cost is due to creating the dominator tree subset, | |
71 with a cost of O(n_basic_blocks ^ 2); however this can only happen | |
72 for n_statements / n_basic_blocks statements. So, the amortized cost | |
73 of creating the dominator tree subset is O(n_basic_blocks) and the | |
74 worst-case cost of the pass is O(n_statements * n_basic_blocks). | |
75 | |
76 More practically, the cost will be small because there are few | |
77 divisions, and they tend to be in the same basic block, so insert_bb | |
78 is called very few times. | |
79 | |
80 If we did this using domwalk.c, an efficient implementation would have | |
81 to work on all the variables in a single pass, because we could not | |
82 work on just a subset of the dominator tree, as we do now, and the | |
83 cost would also be something like O(n_statements * n_basic_blocks). | |
84 The data structures would be more complex in order to work on all the | |
85 variables in a single pass. */ | |
86 | |
87 #include "config.h" | |
88 #include "system.h" | |
89 #include "coretypes.h" | |
90 #include "tm.h" | |
91 #include "flags.h" | |
92 #include "tree.h" | |
93 #include "tree-flow.h" | |
94 #include "real.h" | |
95 #include "timevar.h" | |
96 #include "tree-pass.h" | |
97 #include "alloc-pool.h" | |
98 #include "basic-block.h" | |
99 #include "target.h" | |
100 | |
101 | |
102 /* This structure represents one basic block that either computes a | |
103 division, or is a common dominator for basic block that compute a | |
104 division. */ | |
105 struct occurrence { | |
106 /* The basic block represented by this structure. */ | |
107 basic_block bb; | |
108 | |
109 /* If non-NULL, the SSA_NAME holding the definition for a reciprocal | |
110 inserted in BB. */ | |
111 tree recip_def; | |
112 | |
113 /* If non-NULL, the GIMPLE_ASSIGN for a reciprocal computation that | |
114 was inserted in BB. */ | |
115 gimple recip_def_stmt; | |
116 | |
117 /* Pointer to a list of "struct occurrence"s for blocks dominated | |
118 by BB. */ | |
119 struct occurrence *children; | |
120 | |
121 /* Pointer to the next "struct occurrence"s in the list of blocks | |
122 sharing a common dominator. */ | |
123 struct occurrence *next; | |
124 | |
125 /* The number of divisions that are in BB before compute_merit. The | |
126 number of divisions that are in BB or post-dominate it after | |
127 compute_merit. */ | |
128 int num_divisions; | |
129 | |
130 /* True if the basic block has a division, false if it is a common | |
131 dominator for basic blocks that do. If it is false and trapping | |
132 math is active, BB is not a candidate for inserting a reciprocal. */ | |
133 bool bb_has_division; | |
134 }; | |
135 | |
136 | |
137 /* The instance of "struct occurrence" representing the highest | |
138 interesting block in the dominator tree. */ | |
139 static struct occurrence *occ_head; | |
140 | |
141 /* Allocation pool for getting instances of "struct occurrence". */ | |
142 static alloc_pool occ_pool; | |
143 | |
144 | |
145 | |
146 /* Allocate and return a new struct occurrence for basic block BB, and | |
147 whose children list is headed by CHILDREN. */ | |
148 static struct occurrence * | |
149 occ_new (basic_block bb, struct occurrence *children) | |
150 { | |
151 struct occurrence *occ; | |
152 | |
153 bb->aux = occ = (struct occurrence *) pool_alloc (occ_pool); | |
154 memset (occ, 0, sizeof (struct occurrence)); | |
155 | |
156 occ->bb = bb; | |
157 occ->children = children; | |
158 return occ; | |
159 } | |
160 | |
161 | |
162 /* Insert NEW_OCC into our subset of the dominator tree. P_HEAD points to a | |
163 list of "struct occurrence"s, one per basic block, having IDOM as | |
164 their common dominator. | |
165 | |
166 We try to insert NEW_OCC as deep as possible in the tree, and we also | |
167 insert any other block that is a common dominator for BB and one | |
168 block already in the tree. */ | |
169 | |
170 static void | |
171 insert_bb (struct occurrence *new_occ, basic_block idom, | |
172 struct occurrence **p_head) | |
173 { | |
174 struct occurrence *occ, **p_occ; | |
175 | |
176 for (p_occ = p_head; (occ = *p_occ) != NULL; ) | |
177 { | |
178 basic_block bb = new_occ->bb, occ_bb = occ->bb; | |
179 basic_block dom = nearest_common_dominator (CDI_DOMINATORS, occ_bb, bb); | |
180 if (dom == bb) | |
181 { | |
182 /* BB dominates OCC_BB. OCC becomes NEW_OCC's child: remove OCC | |
183 from its list. */ | |
184 *p_occ = occ->next; | |
185 occ->next = new_occ->children; | |
186 new_occ->children = occ; | |
187 | |
188 /* Try the next block (it may as well be dominated by BB). */ | |
189 } | |
190 | |
191 else if (dom == occ_bb) | |
192 { | |
193 /* OCC_BB dominates BB. Tail recurse to look deeper. */ | |
194 insert_bb (new_occ, dom, &occ->children); | |
195 return; | |
196 } | |
197 | |
198 else if (dom != idom) | |
199 { | |
200 gcc_assert (!dom->aux); | |
201 | |
202 /* There is a dominator between IDOM and BB, add it and make | |
203 two children out of NEW_OCC and OCC. First, remove OCC from | |
204 its list. */ | |
205 *p_occ = occ->next; | |
206 new_occ->next = occ; | |
207 occ->next = NULL; | |
208 | |
209 /* None of the previous blocks has DOM as a dominator: if we tail | |
210 recursed, we would reexamine them uselessly. Just switch BB with | |
211 DOM, and go on looking for blocks dominated by DOM. */ | |
212 new_occ = occ_new (dom, new_occ); | |
213 } | |
214 | |
215 else | |
216 { | |
217 /* Nothing special, go on with the next element. */ | |
218 p_occ = &occ->next; | |
219 } | |
220 } | |
221 | |
222 /* No place was found as a child of IDOM. Make BB a sibling of IDOM. */ | |
223 new_occ->next = *p_head; | |
224 *p_head = new_occ; | |
225 } | |
226 | |
227 /* Register that we found a division in BB. */ | |
228 | |
229 static inline void | |
230 register_division_in (basic_block bb) | |
231 { | |
232 struct occurrence *occ; | |
233 | |
234 occ = (struct occurrence *) bb->aux; | |
235 if (!occ) | |
236 { | |
237 occ = occ_new (bb, NULL); | |
238 insert_bb (occ, ENTRY_BLOCK_PTR, &occ_head); | |
239 } | |
240 | |
241 occ->bb_has_division = true; | |
242 occ->num_divisions++; | |
243 } | |
244 | |
245 | |
246 /* Compute the number of divisions that postdominate each block in OCC and | |
247 its children. */ | |
248 | |
249 static void | |
250 compute_merit (struct occurrence *occ) | |
251 { | |
252 struct occurrence *occ_child; | |
253 basic_block dom = occ->bb; | |
254 | |
255 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) | |
256 { | |
257 basic_block bb; | |
258 if (occ_child->children) | |
259 compute_merit (occ_child); | |
260 | |
261 if (flag_exceptions) | |
262 bb = single_noncomplex_succ (dom); | |
263 else | |
264 bb = dom; | |
265 | |
266 if (dominated_by_p (CDI_POST_DOMINATORS, bb, occ_child->bb)) | |
267 occ->num_divisions += occ_child->num_divisions; | |
268 } | |
269 } | |
270 | |
271 | |
272 /* Return whether USE_STMT is a floating-point division by DEF. */ | |
273 static inline bool | |
274 is_division_by (gimple use_stmt, tree def) | |
275 { | |
276 return is_gimple_assign (use_stmt) | |
277 && gimple_assign_rhs_code (use_stmt) == RDIV_EXPR | |
278 && gimple_assign_rhs2 (use_stmt) == def | |
279 /* Do not recognize x / x as valid division, as we are getting | |
280 confused later by replacing all immediate uses x in such | |
281 a stmt. */ | |
282 && gimple_assign_rhs1 (use_stmt) != def; | |
283 } | |
284 | |
285 /* Walk the subset of the dominator tree rooted at OCC, setting the | |
286 RECIP_DEF field to a definition of 1.0 / DEF that can be used in | |
287 the given basic block. The field may be left NULL, of course, | |
288 if it is not possible or profitable to do the optimization. | |
289 | |
290 DEF_BSI is an iterator pointing at the statement defining DEF. | |
291 If RECIP_DEF is set, a dominator already has a computation that can | |
292 be used. */ | |
293 | |
294 static void | |
295 insert_reciprocals (gimple_stmt_iterator *def_gsi, struct occurrence *occ, | |
296 tree def, tree recip_def, int threshold) | |
297 { | |
298 tree type; | |
299 gimple new_stmt; | |
300 gimple_stmt_iterator gsi; | |
301 struct occurrence *occ_child; | |
302 | |
303 if (!recip_def | |
304 && (occ->bb_has_division || !flag_trapping_math) | |
305 && occ->num_divisions >= threshold) | |
306 { | |
307 /* Make a variable with the replacement and substitute it. */ | |
308 type = TREE_TYPE (def); | |
309 recip_def = make_rename_temp (type, "reciptmp"); | |
310 new_stmt = gimple_build_assign_with_ops (RDIV_EXPR, recip_def, | |
311 build_one_cst (type), def); | |
312 | |
313 if (occ->bb_has_division) | |
314 { | |
315 /* Case 1: insert before an existing division. */ | |
316 gsi = gsi_after_labels (occ->bb); | |
317 while (!gsi_end_p (gsi) && !is_division_by (gsi_stmt (gsi), def)) | |
318 gsi_next (&gsi); | |
319 | |
320 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); | |
321 } | |
322 else if (def_gsi && occ->bb == def_gsi->bb) | |
323 { | |
324 /* Case 2: insert right after the definition. Note that this will | |
325 never happen if the definition statement can throw, because in | |
326 that case the sole successor of the statement's basic block will | |
327 dominate all the uses as well. */ | |
328 gsi_insert_after (def_gsi, new_stmt, GSI_NEW_STMT); | |
329 } | |
330 else | |
331 { | |
332 /* Case 3: insert in a basic block not containing defs/uses. */ | |
333 gsi = gsi_after_labels (occ->bb); | |
334 gsi_insert_before (&gsi, new_stmt, GSI_SAME_STMT); | |
335 } | |
336 | |
337 occ->recip_def_stmt = new_stmt; | |
338 } | |
339 | |
340 occ->recip_def = recip_def; | |
341 for (occ_child = occ->children; occ_child; occ_child = occ_child->next) | |
342 insert_reciprocals (def_gsi, occ_child, def, recip_def, threshold); | |
343 } | |
344 | |
345 | |
346 /* Replace the division at USE_P with a multiplication by the reciprocal, if | |
347 possible. */ | |
348 | |
349 static inline void | |
350 replace_reciprocal (use_operand_p use_p) | |
351 { | |
352 gimple use_stmt = USE_STMT (use_p); | |
353 basic_block bb = gimple_bb (use_stmt); | |
354 struct occurrence *occ = (struct occurrence *) bb->aux; | |
355 | |
356 if (optimize_bb_for_speed_p (bb) | |
357 && occ->recip_def && use_stmt != occ->recip_def_stmt) | |
358 { | |
359 gimple_assign_set_rhs_code (use_stmt, MULT_EXPR); | |
360 SET_USE (use_p, occ->recip_def); | |
361 fold_stmt_inplace (use_stmt); | |
362 update_stmt (use_stmt); | |
363 } | |
364 } | |
365 | |
366 | |
367 /* Free OCC and return one more "struct occurrence" to be freed. */ | |
368 | |
369 static struct occurrence * | |
370 free_bb (struct occurrence *occ) | |
371 { | |
372 struct occurrence *child, *next; | |
373 | |
374 /* First get the two pointers hanging off OCC. */ | |
375 next = occ->next; | |
376 child = occ->children; | |
377 occ->bb->aux = NULL; | |
378 pool_free (occ_pool, occ); | |
379 | |
380 /* Now ensure that we don't recurse unless it is necessary. */ | |
381 if (!child) | |
382 return next; | |
383 else | |
384 { | |
385 while (next) | |
386 next = free_bb (next); | |
387 | |
388 return child; | |
389 } | |
390 } | |
391 | |
392 | |
393 /* Look for floating-point divisions among DEF's uses, and try to | |
394 replace them by multiplications with the reciprocal. Add | |
395 as many statements computing the reciprocal as needed. | |
396 | |
397 DEF must be a GIMPLE register of a floating-point type. */ | |
398 | |
399 static void | |
400 execute_cse_reciprocals_1 (gimple_stmt_iterator *def_gsi, tree def) | |
401 { | |
402 use_operand_p use_p; | |
403 imm_use_iterator use_iter; | |
404 struct occurrence *occ; | |
405 int count = 0, threshold; | |
406 | |
407 gcc_assert (FLOAT_TYPE_P (TREE_TYPE (def)) && is_gimple_reg (def)); | |
408 | |
409 FOR_EACH_IMM_USE_FAST (use_p, use_iter, def) | |
410 { | |
411 gimple use_stmt = USE_STMT (use_p); | |
412 if (is_division_by (use_stmt, def)) | |
413 { | |
414 register_division_in (gimple_bb (use_stmt)); | |
415 count++; | |
416 } | |
417 } | |
418 | |
419 /* Do the expensive part only if we can hope to optimize something. */ | |
420 threshold = targetm.min_divisions_for_recip_mul (TYPE_MODE (TREE_TYPE (def))); | |
421 if (count >= threshold) | |
422 { | |
423 gimple use_stmt; | |
424 for (occ = occ_head; occ; occ = occ->next) | |
425 { | |
426 compute_merit (occ); | |
427 insert_reciprocals (def_gsi, occ, def, NULL, threshold); | |
428 } | |
429 | |
430 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, def) | |
431 { | |
432 if (is_division_by (use_stmt, def)) | |
433 { | |
434 FOR_EACH_IMM_USE_ON_STMT (use_p, use_iter) | |
435 replace_reciprocal (use_p); | |
436 } | |
437 } | |
438 } | |
439 | |
440 for (occ = occ_head; occ; ) | |
441 occ = free_bb (occ); | |
442 | |
443 occ_head = NULL; | |
444 } | |
445 | |
446 static bool | |
447 gate_cse_reciprocals (void) | |
448 { | |
449 return optimize && flag_reciprocal_math; | |
450 } | |
451 | |
452 /* Go through all the floating-point SSA_NAMEs, and call | |
453 execute_cse_reciprocals_1 on each of them. */ | |
454 static unsigned int | |
455 execute_cse_reciprocals (void) | |
456 { | |
457 basic_block bb; | |
458 tree arg; | |
459 | |
460 occ_pool = create_alloc_pool ("dominators for recip", | |
461 sizeof (struct occurrence), | |
462 n_basic_blocks / 3 + 1); | |
463 | |
464 calculate_dominance_info (CDI_DOMINATORS); | |
465 calculate_dominance_info (CDI_POST_DOMINATORS); | |
466 | |
467 #ifdef ENABLE_CHECKING | |
468 FOR_EACH_BB (bb) | |
469 gcc_assert (!bb->aux); | |
470 #endif | |
471 | |
472 for (arg = DECL_ARGUMENTS (cfun->decl); arg; arg = TREE_CHAIN (arg)) | |
473 if (gimple_default_def (cfun, arg) | |
474 && FLOAT_TYPE_P (TREE_TYPE (arg)) | |
475 && is_gimple_reg (arg)) | |
476 execute_cse_reciprocals_1 (NULL, gimple_default_def (cfun, arg)); | |
477 | |
478 FOR_EACH_BB (bb) | |
479 { | |
480 gimple_stmt_iterator gsi; | |
481 gimple phi; | |
482 tree def; | |
483 | |
484 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
485 { | |
486 phi = gsi_stmt (gsi); | |
487 def = PHI_RESULT (phi); | |
488 if (FLOAT_TYPE_P (TREE_TYPE (def)) | |
489 && is_gimple_reg (def)) | |
490 execute_cse_reciprocals_1 (NULL, def); | |
491 } | |
492 | |
493 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
494 { | |
495 gimple stmt = gsi_stmt (gsi); | |
496 | |
497 if (gimple_has_lhs (stmt) | |
498 && (def = SINGLE_SSA_TREE_OPERAND (stmt, SSA_OP_DEF)) != NULL | |
499 && FLOAT_TYPE_P (TREE_TYPE (def)) | |
500 && TREE_CODE (def) == SSA_NAME) | |
501 execute_cse_reciprocals_1 (&gsi, def); | |
502 } | |
503 | |
504 if (optimize_bb_for_size_p (bb)) | |
505 continue; | |
506 | |
507 /* Scan for a/func(b) and convert it to reciprocal a*rfunc(b). */ | |
508 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
509 { | |
510 gimple stmt = gsi_stmt (gsi); | |
511 tree fndecl; | |
512 | |
513 if (is_gimple_assign (stmt) | |
514 && gimple_assign_rhs_code (stmt) == RDIV_EXPR) | |
515 { | |
516 tree arg1 = gimple_assign_rhs2 (stmt); | |
517 gimple stmt1; | |
518 | |
519 if (TREE_CODE (arg1) != SSA_NAME) | |
520 continue; | |
521 | |
522 stmt1 = SSA_NAME_DEF_STMT (arg1); | |
523 | |
524 if (is_gimple_call (stmt1) | |
525 && gimple_call_lhs (stmt1) | |
526 && (fndecl = gimple_call_fndecl (stmt1)) | |
527 && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL | |
528 || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD)) | |
529 { | |
530 enum built_in_function code; | |
47
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
531 bool md_code, fail; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
532 imm_use_iterator ui; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
533 use_operand_p use_p; |
0 | 534 |
535 code = DECL_FUNCTION_CODE (fndecl); | |
536 md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD; | |
537 | |
538 fndecl = targetm.builtin_reciprocal (code, md_code, false); | |
539 if (!fndecl) | |
540 continue; | |
541 | |
47
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
542 /* Check that all uses of the SSA name are divisions, |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
543 otherwise replacing the defining statement will do |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
544 the wrong thing. */ |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
545 fail = false; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
546 FOR_EACH_IMM_USE_FAST (use_p, ui, arg1) |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
547 { |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
548 gimple stmt2 = USE_STMT (use_p); |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
549 if (!is_gimple_assign (stmt2) |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
550 || gimple_assign_rhs_code (stmt2) != RDIV_EXPR |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
551 || gimple_assign_rhs1 (stmt2) == arg1 |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
552 || gimple_assign_rhs2 (stmt2) != arg1) |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
553 { |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
554 fail = true; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
555 break; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
556 } |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
557 } |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
558 if (fail) |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
559 continue; |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
560 |
0 | 561 gimple_call_set_fndecl (stmt1, fndecl); |
562 update_stmt (stmt1); | |
563 | |
47
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
564 FOR_EACH_IMM_USE_STMT (stmt, ui, arg1) |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
565 { |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
566 gimple_assign_set_rhs_code (stmt, MULT_EXPR); |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
567 fold_stmt_inplace (stmt); |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
568 update_stmt (stmt); |
3bfb6c00c1e0
update it from 4.4.2 to 4.4.3.
kent <kent@cr.ie.u-ryukyu.ac.jp>
parents:
0
diff
changeset
|
569 } |
0 | 570 } |
571 } | |
572 } | |
573 } | |
574 | |
575 free_dominance_info (CDI_DOMINATORS); | |
576 free_dominance_info (CDI_POST_DOMINATORS); | |
577 free_alloc_pool (occ_pool); | |
578 return 0; | |
579 } | |
580 | |
581 struct gimple_opt_pass pass_cse_reciprocals = | |
582 { | |
583 { | |
584 GIMPLE_PASS, | |
585 "recip", /* name */ | |
586 gate_cse_reciprocals, /* gate */ | |
587 execute_cse_reciprocals, /* execute */ | |
588 NULL, /* sub */ | |
589 NULL, /* next */ | |
590 0, /* static_pass_number */ | |
591 0, /* tv_id */ | |
592 PROP_ssa, /* properties_required */ | |
593 0, /* properties_provided */ | |
594 0, /* properties_destroyed */ | |
595 0, /* todo_flags_start */ | |
596 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa | |
597 | TODO_verify_stmts /* todo_flags_finish */ | |
598 } | |
599 }; | |
600 | |
601 /* Records an occurrence at statement USE_STMT in the vector of trees | |
602 STMTS if it is dominated by *TOP_BB or dominates it or this basic block | |
603 is not yet initialized. Returns true if the occurrence was pushed on | |
604 the vector. Adjusts *TOP_BB to be the basic block dominating all | |
605 statements in the vector. */ | |
606 | |
607 static bool | |
608 maybe_record_sincos (VEC(gimple, heap) **stmts, | |
609 basic_block *top_bb, gimple use_stmt) | |
610 { | |
611 basic_block use_bb = gimple_bb (use_stmt); | |
612 if (*top_bb | |
613 && (*top_bb == use_bb | |
614 || dominated_by_p (CDI_DOMINATORS, use_bb, *top_bb))) | |
615 VEC_safe_push (gimple, heap, *stmts, use_stmt); | |
616 else if (!*top_bb | |
617 || dominated_by_p (CDI_DOMINATORS, *top_bb, use_bb)) | |
618 { | |
619 VEC_safe_push (gimple, heap, *stmts, use_stmt); | |
620 *top_bb = use_bb; | |
621 } | |
622 else | |
623 return false; | |
624 | |
625 return true; | |
626 } | |
627 | |
628 /* Look for sin, cos and cexpi calls with the same argument NAME and | |
629 create a single call to cexpi CSEing the result in this case. | |
630 We first walk over all immediate uses of the argument collecting | |
631 statements that we can CSE in a vector and in a second pass replace | |
632 the statement rhs with a REALPART or IMAGPART expression on the | |
633 result of the cexpi call we insert before the use statement that | |
634 dominates all other candidates. */ | |
635 | |
636 static void | |
637 execute_cse_sincos_1 (tree name) | |
638 { | |
639 gimple_stmt_iterator gsi; | |
640 imm_use_iterator use_iter; | |
641 tree fndecl, res, type; | |
642 gimple def_stmt, use_stmt, stmt; | |
643 int seen_cos = 0, seen_sin = 0, seen_cexpi = 0; | |
644 VEC(gimple, heap) *stmts = NULL; | |
645 basic_block top_bb = NULL; | |
646 int i; | |
647 | |
648 type = TREE_TYPE (name); | |
649 FOR_EACH_IMM_USE_STMT (use_stmt, use_iter, name) | |
650 { | |
651 if (gimple_code (use_stmt) != GIMPLE_CALL | |
652 || !gimple_call_lhs (use_stmt) | |
653 || !(fndecl = gimple_call_fndecl (use_stmt)) | |
654 || DECL_BUILT_IN_CLASS (fndecl) != BUILT_IN_NORMAL) | |
655 continue; | |
656 | |
657 switch (DECL_FUNCTION_CODE (fndecl)) | |
658 { | |
659 CASE_FLT_FN (BUILT_IN_COS): | |
660 seen_cos |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; | |
661 break; | |
662 | |
663 CASE_FLT_FN (BUILT_IN_SIN): | |
664 seen_sin |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; | |
665 break; | |
666 | |
667 CASE_FLT_FN (BUILT_IN_CEXPI): | |
668 seen_cexpi |= maybe_record_sincos (&stmts, &top_bb, use_stmt) ? 1 : 0; | |
669 break; | |
670 | |
671 default:; | |
672 } | |
673 } | |
674 | |
675 if (seen_cos + seen_sin + seen_cexpi <= 1) | |
676 { | |
677 VEC_free(gimple, heap, stmts); | |
678 return; | |
679 } | |
680 | |
681 /* Simply insert cexpi at the beginning of top_bb but not earlier than | |
682 the name def statement. */ | |
683 fndecl = mathfn_built_in (type, BUILT_IN_CEXPI); | |
684 if (!fndecl) | |
685 return; | |
686 res = make_rename_temp (TREE_TYPE (TREE_TYPE (fndecl)), "sincostmp"); | |
687 stmt = gimple_build_call (fndecl, 1, name); | |
688 gimple_call_set_lhs (stmt, res); | |
689 | |
690 def_stmt = SSA_NAME_DEF_STMT (name); | |
691 if (!SSA_NAME_IS_DEFAULT_DEF (name) | |
692 && gimple_code (def_stmt) != GIMPLE_PHI | |
693 && gimple_bb (def_stmt) == top_bb) | |
694 { | |
695 gsi = gsi_for_stmt (def_stmt); | |
696 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT); | |
697 } | |
698 else | |
699 { | |
700 gsi = gsi_after_labels (top_bb); | |
701 gsi_insert_before (&gsi, stmt, GSI_SAME_STMT); | |
702 } | |
703 update_stmt (stmt); | |
704 | |
705 /* And adjust the recorded old call sites. */ | |
706 for (i = 0; VEC_iterate(gimple, stmts, i, use_stmt); ++i) | |
707 { | |
708 tree rhs = NULL; | |
709 fndecl = gimple_call_fndecl (use_stmt); | |
710 | |
711 switch (DECL_FUNCTION_CODE (fndecl)) | |
712 { | |
713 CASE_FLT_FN (BUILT_IN_COS): | |
714 rhs = fold_build1 (REALPART_EXPR, type, res); | |
715 break; | |
716 | |
717 CASE_FLT_FN (BUILT_IN_SIN): | |
718 rhs = fold_build1 (IMAGPART_EXPR, type, res); | |
719 break; | |
720 | |
721 CASE_FLT_FN (BUILT_IN_CEXPI): | |
722 rhs = res; | |
723 break; | |
724 | |
725 default:; | |
726 gcc_unreachable (); | |
727 } | |
728 | |
729 /* Replace call with a copy. */ | |
730 stmt = gimple_build_assign (gimple_call_lhs (use_stmt), rhs); | |
731 | |
732 gsi = gsi_for_stmt (use_stmt); | |
733 gsi_insert_after (&gsi, stmt, GSI_SAME_STMT); | |
734 gsi_remove (&gsi, true); | |
735 } | |
736 | |
737 VEC_free(gimple, heap, stmts); | |
738 } | |
739 | |
740 /* Go through all calls to sin, cos and cexpi and call execute_cse_sincos_1 | |
741 on the SSA_NAME argument of each of them. */ | |
742 | |
743 static unsigned int | |
744 execute_cse_sincos (void) | |
745 { | |
746 basic_block bb; | |
747 | |
748 calculate_dominance_info (CDI_DOMINATORS); | |
749 | |
750 FOR_EACH_BB (bb) | |
751 { | |
752 gimple_stmt_iterator gsi; | |
753 | |
754 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
755 { | |
756 gimple stmt = gsi_stmt (gsi); | |
757 tree fndecl; | |
758 | |
759 if (is_gimple_call (stmt) | |
760 && gimple_call_lhs (stmt) | |
761 && (fndecl = gimple_call_fndecl (stmt)) | |
762 && DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL) | |
763 { | |
764 tree arg; | |
765 | |
766 switch (DECL_FUNCTION_CODE (fndecl)) | |
767 { | |
768 CASE_FLT_FN (BUILT_IN_COS): | |
769 CASE_FLT_FN (BUILT_IN_SIN): | |
770 CASE_FLT_FN (BUILT_IN_CEXPI): | |
771 arg = gimple_call_arg (stmt, 0); | |
772 if (TREE_CODE (arg) == SSA_NAME) | |
773 execute_cse_sincos_1 (arg); | |
774 break; | |
775 | |
776 default:; | |
777 } | |
778 } | |
779 } | |
780 } | |
781 | |
782 free_dominance_info (CDI_DOMINATORS); | |
783 return 0; | |
784 } | |
785 | |
786 static bool | |
787 gate_cse_sincos (void) | |
788 { | |
789 /* Make sure we have either sincos or cexp. */ | |
790 return (TARGET_HAS_SINCOS | |
791 || TARGET_C99_FUNCTIONS) | |
792 && optimize; | |
793 } | |
794 | |
795 struct gimple_opt_pass pass_cse_sincos = | |
796 { | |
797 { | |
798 GIMPLE_PASS, | |
799 "sincos", /* name */ | |
800 gate_cse_sincos, /* gate */ | |
801 execute_cse_sincos, /* execute */ | |
802 NULL, /* sub */ | |
803 NULL, /* next */ | |
804 0, /* static_pass_number */ | |
805 0, /* tv_id */ | |
806 PROP_ssa, /* properties_required */ | |
807 0, /* properties_provided */ | |
808 0, /* properties_destroyed */ | |
809 0, /* todo_flags_start */ | |
810 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa | |
811 | TODO_verify_stmts /* todo_flags_finish */ | |
812 } | |
813 }; | |
814 | |
815 /* Find all expressions in the form of sqrt(a/b) and | |
816 convert them to rsqrt(b/a). */ | |
817 | |
818 static unsigned int | |
819 execute_convert_to_rsqrt (void) | |
820 { | |
821 basic_block bb; | |
822 | |
823 FOR_EACH_BB (bb) | |
824 { | |
825 gimple_stmt_iterator gsi; | |
826 | |
827 for (gsi = gsi_after_labels (bb); !gsi_end_p (gsi); gsi_next (&gsi)) | |
828 { | |
829 gimple stmt = gsi_stmt (gsi); | |
830 tree fndecl; | |
831 | |
832 if (is_gimple_call (stmt) | |
833 && gimple_call_lhs (stmt) | |
834 && (fndecl = gimple_call_fndecl (stmt)) | |
835 && (DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_NORMAL | |
836 || DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD)) | |
837 { | |
838 enum built_in_function code; | |
839 bool md_code; | |
840 tree arg1; | |
841 gimple stmt1; | |
842 | |
843 code = DECL_FUNCTION_CODE (fndecl); | |
844 md_code = DECL_BUILT_IN_CLASS (fndecl) == BUILT_IN_MD; | |
845 | |
846 fndecl = targetm.builtin_reciprocal (code, md_code, true); | |
847 if (!fndecl) | |
848 continue; | |
849 | |
850 arg1 = gimple_call_arg (stmt, 0); | |
851 | |
852 if (TREE_CODE (arg1) != SSA_NAME) | |
853 continue; | |
854 | |
855 stmt1 = SSA_NAME_DEF_STMT (arg1); | |
856 | |
857 if (is_gimple_assign (stmt1) | |
858 && gimple_assign_rhs_code (stmt1) == RDIV_EXPR) | |
859 { | |
860 tree arg10, arg11; | |
861 | |
862 arg10 = gimple_assign_rhs1 (stmt1); | |
863 arg11 = gimple_assign_rhs2 (stmt1); | |
864 | |
865 /* Swap operands of RDIV_EXPR. */ | |
866 gimple_assign_set_rhs1 (stmt1, arg11); | |
867 gimple_assign_set_rhs2 (stmt1, arg10); | |
868 fold_stmt_inplace (stmt1); | |
869 update_stmt (stmt1); | |
870 | |
871 gimple_call_set_fndecl (stmt, fndecl); | |
872 update_stmt (stmt); | |
873 } | |
874 } | |
875 } | |
876 } | |
877 | |
878 return 0; | |
879 } | |
880 | |
881 static bool | |
882 gate_convert_to_rsqrt (void) | |
883 { | |
884 return flag_unsafe_math_optimizations && optimize; | |
885 } | |
886 | |
887 struct gimple_opt_pass pass_convert_to_rsqrt = | |
888 { | |
889 { | |
890 GIMPLE_PASS, | |
891 "rsqrt", /* name */ | |
892 gate_convert_to_rsqrt, /* gate */ | |
893 execute_convert_to_rsqrt, /* execute */ | |
894 NULL, /* sub */ | |
895 NULL, /* next */ | |
896 0, /* static_pass_number */ | |
897 0, /* tv_id */ | |
898 PROP_ssa, /* properties_required */ | |
899 0, /* properties_provided */ | |
900 0, /* properties_destroyed */ | |
901 0, /* todo_flags_start */ | |
902 TODO_dump_func | TODO_update_ssa | TODO_verify_ssa | |
903 | TODO_verify_stmts /* todo_flags_finish */ | |
904 } | |
905 }; |