]>
Commit | Line | Data |
---|---|---|
7fc2f613 | 1 | /* Back-propagation of usage information to definitions. |
fbd26352 | 2 | Copyright (C) 2015-2019 Free Software Foundation, Inc. |
7fc2f613 | 3 | |
4 | This file is part of GCC. | |
5 | ||
6 | GCC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 3, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GCC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License 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 | /* This pass propagates information that is common to all uses of an SSA | |
21 | name back up through the sequence of statements that generate it, | |
22 | simplifying the statements where possible. Sometimes this can expose | |
23 | fully or partially dead code, but the main focus is simplifying | |
24 | computations. | |
25 | ||
26 | At the moment the pass only handles one piece of information: whether the | |
27 | sign of a value matters, and therefore whether sign-changing operations | |
28 | can be skipped. The pass could be extended to more interesting | |
29 | information in future, such as which bits of an integer are significant. | |
30 | ||
31 | For example, take the function: | |
32 | ||
33 | double | |
34 | f (double *a, int n, double start) | |
35 | { | |
36 | double x = fabs (start); | |
37 | for (int i = 0; i < n; ++i) | |
38 | x *= a[i]; | |
39 | return __builtin_cos (x); | |
40 | } | |
41 | ||
42 | cos(x) == cos(-x), so the sign of the final x doesn't matter. | |
43 | That x is the result of a series of multiplications, and if | |
44 | the sign of the result of a multiplication doesn't matter, | |
45 | the signs of the inputs don't matter either. | |
46 | ||
47 | The pass would replace the incoming value of x (i.e. fabs(start)) | |
48 | with start. Since there are no other uses of the fabs result, | |
49 | the call would get deleted as dead. | |
50 | ||
51 | The algorithm is: | |
52 | ||
53 | (1) Do a post-order traversal of the blocks in the function, walking | |
54 | each block backwards. For each potentially-simplifiable statement | |
55 | that defines an SSA name X, examine all uses of X to see what | |
56 | information is actually significant. Record this as INFO_MAP[X]. | |
57 | Optimistically ignore for now any back-edge references to | |
58 | unprocessed phis. | |
59 | ||
60 | (An alternative would be to record each use when we visit its | |
61 | statement and take the intersection as we go along. However, | |
62 | this would lead to more SSA names being entered into INFO_MAP | |
63 | unnecessarily, only to be taken out again later. At the moment | |
64 | very few SSA names end up with useful information.) | |
65 | ||
66 | (2) Iteratively reduce the optimistic result of (1) until we reach | |
67 | a maximal fixed point (which at the moment would mean revisiting | |
68 | statements at most once). First push all SSA names that used an | |
69 | optimistic assumption about a backedge phi onto a worklist. | |
70 | While the worklist is nonempty, pick off an SSA name X and recompute | |
71 | INFO_MAP[X]. If the value changes, push all SSA names used in the | |
72 | definition of X onto the worklist. | |
73 | ||
74 | (3) Iterate over each SSA name X with info in INFO_MAP, in the | |
75 | opposite order to (1), i.e. a forward reverse-post-order walk. | |
76 | Try to optimize the definition of X using INFO_MAP[X] and fold | |
77 | the result. (This ensures that we fold definitions before uses.) | |
78 | ||
79 | (4) Iterate over each SSA name X with info in INFO_MAP, in the same | |
80 | order as (1), and delete any statements that are now dead. | |
81 | (This ensures that if a sequence of statements is dead, | |
82 | we delete the last statement first.) | |
83 | ||
84 | Note that this pass does not deal with direct redundancies, | |
85 | such as cos(-x)->cos(x). match.pd handles those cases instead. */ | |
86 | ||
87 | #include "config.h" | |
88 | #include "system.h" | |
89 | #include "coretypes.h" | |
90 | #include "backend.h" | |
91 | #include "tree.h" | |
92 | #include "gimple.h" | |
93 | #include "gimple-iterator.h" | |
94 | #include "ssa.h" | |
95 | #include "fold-const.h" | |
96 | #include "tree-pass.h" | |
97 | #include "cfganal.h" | |
98 | #include "gimple-pretty-print.h" | |
99 | #include "tree-cfg.h" | |
100 | #include "tree-ssa.h" | |
101 | #include "tree-ssa-propagate.h" | |
102 | #include "gimple-fold.h" | |
103 | #include "alloc-pool.h" | |
104 | #include "tree-hash-traits.h" | |
7a366e88 | 105 | #include "case-cfn-macros.h" |
7fc2f613 | 106 | |
107 | namespace { | |
108 | ||
109 | /* Information about a group of uses of an SSA name. */ | |
110 | struct usage_info | |
111 | { | |
112 | usage_info () : flag_word (0) {} | |
113 | usage_info &operator &= (const usage_info &); | |
114 | usage_info operator & (const usage_info &) const; | |
115 | bool operator == (const usage_info &) const; | |
116 | bool operator != (const usage_info &) const; | |
117 | bool is_useful () const; | |
118 | ||
119 | static usage_info intersection_identity (); | |
120 | ||
121 | union | |
122 | { | |
123 | struct | |
124 | { | |
125 | /* True if the uses treat x and -x in the same way. */ | |
126 | unsigned int ignore_sign : 1; | |
127 | } flags; | |
128 | /* All the flag bits as a single int. */ | |
129 | unsigned int flag_word; | |
130 | }; | |
131 | }; | |
132 | ||
133 | /* Return an X such that X & Y == Y for all Y. This is the most | |
134 | optimistic assumption possible. */ | |
135 | ||
136 | usage_info | |
137 | usage_info::intersection_identity () | |
138 | { | |
139 | usage_info ret; | |
140 | ret.flag_word = -1; | |
141 | return ret; | |
142 | } | |
143 | ||
144 | /* Intersect *THIS with OTHER, so that *THIS describes all uses covered | |
145 | by the original *THIS and OTHER. */ | |
146 | ||
147 | usage_info & | |
148 | usage_info::operator &= (const usage_info &other) | |
149 | { | |
150 | flag_word &= other.flag_word; | |
151 | return *this; | |
152 | } | |
153 | ||
154 | /* Return the intersection of *THIS and OTHER, i.e. a structure that | |
155 | describes all uses covered by *THIS and OTHER. */ | |
156 | ||
157 | usage_info | |
158 | usage_info::operator & (const usage_info &other) const | |
159 | { | |
160 | usage_info info (*this); | |
161 | info &= other; | |
162 | return info; | |
163 | } | |
164 | ||
165 | bool | |
166 | usage_info::operator == (const usage_info &other) const | |
167 | { | |
168 | return flag_word == other.flag_word; | |
169 | } | |
170 | ||
171 | bool | |
172 | usage_info::operator != (const usage_info &other) const | |
173 | { | |
174 | return !operator == (other); | |
175 | } | |
176 | ||
177 | /* Return true if *THIS is not simply the default, safe assumption. */ | |
178 | ||
179 | bool | |
180 | usage_info::is_useful () const | |
181 | { | |
182 | return flag_word != 0; | |
183 | } | |
184 | ||
185 | /* Start a dump line about SSA name VAR. */ | |
186 | ||
187 | static void | |
188 | dump_usage_prefix (FILE *file, tree var) | |
189 | { | |
190 | fprintf (file, " "); | |
1ffa4346 | 191 | print_generic_expr (file, var); |
7fc2f613 | 192 | fprintf (file, ": "); |
193 | } | |
194 | ||
195 | /* Print INFO to FILE. */ | |
196 | ||
197 | static void | |
198 | dump_usage_info (FILE *file, tree var, usage_info *info) | |
199 | { | |
200 | if (info->flags.ignore_sign) | |
201 | { | |
202 | dump_usage_prefix (file, var); | |
203 | fprintf (file, "sign bit not important\n"); | |
204 | } | |
205 | } | |
206 | ||
207 | /* Represents one execution of the pass. */ | |
208 | class backprop | |
209 | { | |
210 | public: | |
211 | backprop (function *); | |
212 | ~backprop (); | |
213 | ||
214 | void execute (); | |
215 | ||
216 | private: | |
217 | const usage_info *lookup_operand (tree); | |
218 | ||
219 | void push_to_worklist (tree); | |
220 | tree pop_from_worklist (); | |
221 | ||
222 | void process_builtin_call_use (gcall *, tree, usage_info *); | |
223 | void process_assign_use (gassign *, tree, usage_info *); | |
224 | void process_phi_use (gphi *, usage_info *); | |
225 | void process_use (gimple *, tree, usage_info *); | |
226 | bool intersect_uses (tree, usage_info *); | |
227 | void reprocess_inputs (gimple *); | |
228 | void process_var (tree); | |
229 | void process_block (basic_block); | |
230 | ||
231 | void prepare_change (tree); | |
232 | void complete_change (gimple *); | |
233 | void optimize_builtin_call (gcall *, tree, const usage_info *); | |
234 | void replace_assign_rhs (gassign *, tree, tree, tree, tree); | |
235 | void optimize_assign (gassign *, tree, const usage_info *); | |
236 | void optimize_phi (gphi *, tree, const usage_info *); | |
237 | ||
238 | typedef hash_map <tree_ssa_name_hash, usage_info *> info_map_type; | |
239 | typedef std::pair <tree, usage_info *> var_info_pair; | |
240 | ||
241 | /* The function we're optimizing. */ | |
242 | function *m_fn; | |
243 | ||
244 | /* Pool for allocating usage_info structures. */ | |
245 | object_allocator <usage_info> m_info_pool; | |
246 | ||
247 | /* Maps an SSA name to a description of all uses of that SSA name. | |
248 | All the usage_infos satisfy is_useful. | |
249 | ||
250 | We use a hash_map because the map is expected to be sparse | |
251 | (i.e. most SSA names won't have useful information attached to them). | |
252 | We could move to a directly-indexed array if that situation changes. */ | |
253 | info_map_type m_info_map; | |
254 | ||
255 | /* Post-ordered list of all potentially-interesting SSA names, | |
256 | along with information that describes all uses. */ | |
257 | auto_vec <var_info_pair, 128> m_vars; | |
258 | ||
259 | /* A bitmap of blocks that we have finished processing in the initial | |
260 | post-order walk. */ | |
3c6549f8 | 261 | auto_sbitmap m_visited_blocks; |
7fc2f613 | 262 | |
8a789665 | 263 | /* A bitmap of phis that we have finished processing in the initial |
264 | post-order walk, excluding those from blocks mentioned in | |
265 | M_VISITED_BLOCKS. */ | |
266 | auto_bitmap m_visited_phis; | |
267 | ||
7fc2f613 | 268 | /* A worklist of SSA names whose definitions need to be reconsidered. */ |
269 | auto_vec <tree, 64> m_worklist; | |
270 | ||
271 | /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION. | |
272 | We use a bitmap rather than an sbitmap because most SSA names are | |
273 | never added to the worklist. */ | |
274 | bitmap m_worklist_names; | |
275 | }; | |
276 | ||
277 | backprop::backprop (function *fn) | |
278 | : m_fn (fn), | |
279 | m_info_pool ("usage_info"), | |
3c6549f8 | 280 | m_visited_blocks (last_basic_block_for_fn (m_fn)), |
7fc2f613 | 281 | m_worklist_names (BITMAP_ALLOC (NULL)) |
282 | { | |
283 | bitmap_clear (m_visited_blocks); | |
284 | } | |
285 | ||
286 | backprop::~backprop () | |
287 | { | |
288 | BITMAP_FREE (m_worklist_names); | |
7fc2f613 | 289 | m_info_pool.release (); |
290 | } | |
291 | ||
292 | /* Return usage information for general operand OP, or null if none. */ | |
293 | ||
294 | const usage_info * | |
295 | backprop::lookup_operand (tree op) | |
296 | { | |
297 | if (op && TREE_CODE (op) == SSA_NAME) | |
298 | { | |
299 | usage_info **slot = m_info_map.get (op); | |
300 | if (slot) | |
301 | return *slot; | |
302 | } | |
303 | return NULL; | |
304 | } | |
305 | ||
306 | /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */ | |
307 | ||
308 | void | |
309 | backprop::push_to_worklist (tree var) | |
310 | { | |
311 | if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var))) | |
312 | return; | |
313 | m_worklist.safe_push (var); | |
314 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
315 | { | |
316 | fprintf (dump_file, "[WORKLIST] Pushing "); | |
1ffa4346 | 317 | print_generic_expr (dump_file, var); |
7fc2f613 | 318 | fprintf (dump_file, "\n"); |
319 | } | |
320 | } | |
321 | ||
322 | /* Remove and return the next SSA name from the worklist. The worklist | |
323 | is known to be nonempty. */ | |
324 | ||
325 | tree | |
326 | backprop::pop_from_worklist () | |
327 | { | |
328 | tree var = m_worklist.pop (); | |
329 | bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var)); | |
330 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
331 | { | |
332 | fprintf (dump_file, "[WORKLIST] Popping "); | |
1ffa4346 | 333 | print_generic_expr (dump_file, var); |
7fc2f613 | 334 | fprintf (dump_file, "\n"); |
335 | } | |
336 | return var; | |
337 | } | |
338 | ||
339 | /* Make INFO describe all uses of RHS in CALL, which is a call to a | |
340 | built-in function. */ | |
341 | ||
342 | void | |
343 | backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info) | |
344 | { | |
7a366e88 | 345 | combined_fn fn = gimple_call_combined_fn (call); |
7fc2f613 | 346 | tree lhs = gimple_call_lhs (call); |
347 | switch (fn) | |
348 | { | |
7a366e88 | 349 | case CFN_LAST: |
350 | break; | |
351 | ||
352 | CASE_CFN_COS: | |
353 | CASE_CFN_COSH: | |
354 | CASE_CFN_CCOS: | |
355 | CASE_CFN_CCOSH: | |
356 | CASE_CFN_HYPOT: | |
7fc2f613 | 357 | /* The signs of all inputs are ignored. */ |
358 | info->flags.ignore_sign = true; | |
359 | break; | |
360 | ||
7a366e88 | 361 | CASE_CFN_COPYSIGN: |
8c32188e | 362 | CASE_CFN_COPYSIGN_FN: |
7fc2f613 | 363 | /* The sign of the first input is ignored. */ |
364 | if (rhs != gimple_call_arg (call, 1)) | |
365 | info->flags.ignore_sign = true; | |
366 | break; | |
367 | ||
7a366e88 | 368 | CASE_CFN_POW: |
7fc2f613 | 369 | { |
370 | /* The sign of the first input is ignored as long as the second | |
371 | input is an even real. */ | |
372 | tree power = gimple_call_arg (call, 1); | |
373 | HOST_WIDE_INT n; | |
374 | if (TREE_CODE (power) == REAL_CST | |
375 | && real_isinteger (&TREE_REAL_CST (power), &n) | |
376 | && (n & 1) == 0) | |
377 | info->flags.ignore_sign = true; | |
378 | break; | |
379 | } | |
380 | ||
7a366e88 | 381 | CASE_CFN_FMA: |
8c32188e | 382 | CASE_CFN_FMA_FN: |
143c3c9a | 383 | case CFN_FMS: |
384 | case CFN_FNMA: | |
385 | case CFN_FNMS: | |
7fc2f613 | 386 | /* In X * X + Y, where Y is distinct from X, the sign of X doesn't |
387 | matter. */ | |
388 | if (gimple_call_arg (call, 0) == rhs | |
389 | && gimple_call_arg (call, 1) == rhs | |
390 | && gimple_call_arg (call, 2) != rhs) | |
391 | info->flags.ignore_sign = true; | |
392 | break; | |
393 | ||
394 | default: | |
395 | if (negate_mathfn_p (fn)) | |
396 | { | |
397 | /* The sign of the (single) input doesn't matter provided | |
398 | that the sign of the output doesn't matter. */ | |
399 | const usage_info *lhs_info = lookup_operand (lhs); | |
400 | if (lhs_info) | |
401 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
402 | } | |
403 | break; | |
404 | } | |
405 | } | |
406 | ||
407 | /* Make INFO describe all uses of RHS in ASSIGN. */ | |
408 | ||
409 | void | |
410 | backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) | |
411 | { | |
412 | tree lhs = gimple_assign_lhs (assign); | |
413 | switch (gimple_assign_rhs_code (assign)) | |
414 | { | |
415 | case ABS_EXPR: | |
1c67942e | 416 | case ABSU_EXPR: |
7fc2f613 | 417 | /* The sign of the input doesn't matter. */ |
418 | info->flags.ignore_sign = true; | |
419 | break; | |
420 | ||
421 | case COND_EXPR: | |
422 | /* For A = B ? C : D, propagate information about all uses of A | |
423 | to C and D. */ | |
424 | if (rhs != gimple_assign_rhs1 (assign)) | |
425 | { | |
426 | const usage_info *lhs_info = lookup_operand (lhs); | |
427 | if (lhs_info) | |
428 | *info = *lhs_info; | |
429 | } | |
430 | break; | |
431 | ||
7fc2f613 | 432 | case MULT_EXPR: |
433 | /* In X * X, the sign of X doesn't matter. */ | |
434 | if (gimple_assign_rhs1 (assign) == rhs | |
435 | && gimple_assign_rhs2 (assign) == rhs) | |
436 | info->flags.ignore_sign = true; | |
437 | /* Fall through. */ | |
438 | ||
439 | case NEGATE_EXPR: | |
440 | case RDIV_EXPR: | |
441 | /* If the sign of the result doesn't matter, the sign of the inputs | |
442 | doesn't matter either. */ | |
443 | if (FLOAT_TYPE_P (TREE_TYPE (rhs))) | |
444 | { | |
445 | const usage_info *lhs_info = lookup_operand (lhs); | |
446 | if (lhs_info) | |
447 | info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
448 | } | |
449 | break; | |
450 | ||
451 | default: | |
452 | break; | |
453 | } | |
454 | } | |
455 | ||
456 | /* Make INFO describe the uses of PHI's result. */ | |
457 | ||
458 | void | |
459 | backprop::process_phi_use (gphi *phi, usage_info *info) | |
460 | { | |
461 | tree result = gimple_phi_result (phi); | |
462 | if (const usage_info *result_info = lookup_operand (result)) | |
463 | *info = *result_info; | |
464 | } | |
465 | ||
466 | /* Make INFO describe all uses of RHS in STMT. */ | |
467 | ||
468 | void | |
469 | backprop::process_use (gimple *stmt, tree rhs, usage_info *info) | |
470 | { | |
471 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
472 | { | |
473 | fprintf (dump_file, "[USE] "); | |
1ffa4346 | 474 | print_generic_expr (dump_file, rhs); |
7fc2f613 | 475 | fprintf (dump_file, " in "); |
476 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
477 | } | |
478 | ||
479 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
7a366e88 | 480 | process_builtin_call_use (call, rhs, info); |
7fc2f613 | 481 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
482 | process_assign_use (assign, rhs, info); | |
483 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
484 | process_phi_use (phi, info); | |
485 | ||
486 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
487 | dump_usage_info (dump_file, rhs, info); | |
488 | } | |
489 | ||
490 | /* Make INFO describe all uses of VAR, returning true if the result | |
491 | is useful. If the uses include phis that haven't been processed yet, | |
492 | make the most optimistic assumption possible, so that we aim for | |
493 | a maximum rather than a minimum fixed point. */ | |
494 | ||
495 | bool | |
496 | backprop::intersect_uses (tree var, usage_info *info) | |
497 | { | |
498 | imm_use_iterator iter; | |
68c330dc | 499 | use_operand_p use_p; |
7fc2f613 | 500 | *info = usage_info::intersection_identity (); |
68c330dc | 501 | FOR_EACH_IMM_USE_FAST (use_p, iter, var) |
7fc2f613 | 502 | { |
68c330dc | 503 | gimple *stmt = USE_STMT (use_p); |
7fc2f613 | 504 | if (is_gimple_debug (stmt)) |
505 | continue; | |
8a789665 | 506 | gphi *phi = dyn_cast <gphi *> (stmt); |
507 | if (phi | |
508 | && !bitmap_bit_p (m_visited_blocks, gimple_bb (phi)->index) | |
509 | && !bitmap_bit_p (m_visited_phis, | |
510 | SSA_NAME_VERSION (gimple_phi_result (phi)))) | |
7fc2f613 | 511 | { |
512 | /* Skip unprocessed phis. */ | |
513 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
514 | { | |
515 | fprintf (dump_file, "[BACKEDGE] "); | |
1ffa4346 | 516 | print_generic_expr (dump_file, var); |
7fc2f613 | 517 | fprintf (dump_file, " in "); |
8a789665 | 518 | print_gimple_stmt (dump_file, phi, 0, TDF_SLIM); |
7fc2f613 | 519 | } |
520 | } | |
521 | else | |
522 | { | |
523 | usage_info subinfo; | |
524 | process_use (stmt, var, &subinfo); | |
525 | *info &= subinfo; | |
526 | if (!info->is_useful ()) | |
68c330dc | 527 | return false; |
7fc2f613 | 528 | } |
529 | } | |
530 | return true; | |
531 | } | |
532 | ||
533 | /* Queue for reconsideration any input of STMT that has information | |
534 | associated with it. This is used if that information might be | |
535 | too optimistic. */ | |
536 | ||
537 | void | |
538 | backprop::reprocess_inputs (gimple *stmt) | |
539 | { | |
540 | use_operand_p use_p; | |
541 | ssa_op_iter oi; | |
542 | FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) | |
543 | { | |
544 | tree var = get_use_from_ptr (use_p); | |
545 | if (lookup_operand (var)) | |
546 | push_to_worklist (var); | |
547 | } | |
548 | } | |
549 | ||
550 | /* Say that we're recording INFO for SSA name VAR, or that we're deleting | |
551 | existing information if INFO is null. INTRO describes the change. */ | |
552 | ||
553 | static void | |
554 | dump_var_info (tree var, usage_info *info, const char *intro) | |
555 | { | |
556 | fprintf (dump_file, "[DEF] %s for ", intro); | |
557 | print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); | |
558 | if (info) | |
559 | dump_usage_info (dump_file, var, info); | |
560 | } | |
561 | ||
562 | /* Process all uses of VAR and record or update the result in | |
563 | M_INFO_MAP and M_VARS. */ | |
564 | ||
565 | void | |
566 | backprop::process_var (tree var) | |
567 | { | |
568 | if (has_zero_uses (var)) | |
569 | return; | |
570 | ||
571 | usage_info info; | |
572 | intersect_uses (var, &info); | |
573 | ||
574 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
575 | if (info.is_useful ()) | |
576 | { | |
577 | bool existed; | |
578 | usage_info *&map_info = m_info_map.get_or_insert (var, &existed); | |
579 | if (!existed) | |
580 | { | |
581 | /* Recording information about VAR for the first time. */ | |
582 | map_info = m_info_pool.allocate (); | |
583 | *map_info = info; | |
584 | m_vars.safe_push (var_info_pair (var, map_info)); | |
585 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
586 | dump_var_info (var, map_info, "Recording new information"); | |
587 | ||
588 | /* If STMT is a phi, reprocess any backedge uses. This is a | |
589 | no-op for other uses, which won't have any information | |
590 | associated with them. */ | |
591 | if (is_a <gphi *> (stmt)) | |
592 | reprocess_inputs (stmt); | |
593 | } | |
594 | else if (info != *map_info) | |
595 | { | |
596 | /* Recording information that is less optimistic than before. */ | |
597 | gcc_checking_assert ((info & *map_info) == info); | |
598 | *map_info = info; | |
599 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
600 | dump_var_info (var, map_info, "Updating information"); | |
601 | reprocess_inputs (stmt); | |
602 | } | |
603 | } | |
604 | else | |
605 | { | |
606 | if (usage_info **slot = m_info_map.get (var)) | |
607 | { | |
608 | /* Removing previously-recorded information. */ | |
609 | **slot = info; | |
610 | m_info_map.remove (var); | |
611 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
612 | dump_var_info (var, NULL, "Deleting information"); | |
613 | reprocess_inputs (stmt); | |
614 | } | |
615 | else | |
616 | { | |
617 | /* If STMT is a phi, remove any information recorded for | |
618 | its arguments. */ | |
619 | if (is_a <gphi *> (stmt)) | |
620 | reprocess_inputs (stmt); | |
621 | } | |
622 | } | |
623 | } | |
624 | ||
625 | /* Process all statements and phis in BB, during the first post-order walk. */ | |
626 | ||
627 | void | |
628 | backprop::process_block (basic_block bb) | |
629 | { | |
630 | for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); | |
631 | gsi_prev (&gsi)) | |
632 | { | |
633 | tree lhs = gimple_get_lhs (gsi_stmt (gsi)); | |
634 | if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
635 | process_var (lhs); | |
636 | } | |
637 | for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); | |
638 | gsi_next (&gpi)) | |
8a789665 | 639 | { |
640 | tree result = gimple_phi_result (gpi.phi ()); | |
641 | process_var (result); | |
642 | bitmap_set_bit (m_visited_phis, SSA_NAME_VERSION (result)); | |
643 | } | |
644 | bitmap_clear (m_visited_phis); | |
7fc2f613 | 645 | } |
646 | ||
647 | /* Delete the definition of VAR, which has no uses. */ | |
648 | ||
649 | static void | |
650 | remove_unused_var (tree var) | |
651 | { | |
652 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
653 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
654 | { | |
655 | fprintf (dump_file, "Deleting "); | |
656 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
657 | } | |
658 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
659 | gsi_remove (&gsi, true); | |
660 | release_defs (stmt); | |
661 | } | |
662 | ||
663 | /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ | |
664 | ||
665 | static void | |
666 | note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) | |
667 | { | |
668 | fprintf (dump_file, "Replacing use of "); | |
1ffa4346 | 669 | print_generic_expr (dump_file, old_rhs); |
7fc2f613 | 670 | fprintf (dump_file, " with "); |
1ffa4346 | 671 | print_generic_expr (dump_file, new_rhs); |
7fc2f613 | 672 | fprintf (dump_file, " in "); |
673 | print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
674 | } | |
675 | ||
676 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
677 | return that other value, otherwise return null. */ | |
678 | ||
679 | static tree | |
680 | strip_sign_op_1 (tree rhs) | |
681 | { | |
682 | if (TREE_CODE (rhs) != SSA_NAME) | |
683 | return NULL_TREE; | |
684 | ||
685 | gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); | |
686 | if (gassign *assign = dyn_cast <gassign *> (def_stmt)) | |
687 | switch (gimple_assign_rhs_code (assign)) | |
688 | { | |
689 | case ABS_EXPR: | |
1c67942e | 690 | case ABSU_EXPR: |
7fc2f613 | 691 | case NEGATE_EXPR: |
692 | return gimple_assign_rhs1 (assign); | |
693 | ||
694 | default: | |
695 | break; | |
696 | } | |
697 | else if (gcall *call = dyn_cast <gcall *> (def_stmt)) | |
7a366e88 | 698 | switch (gimple_call_combined_fn (call)) |
699 | { | |
700 | CASE_CFN_COPYSIGN: | |
8c32188e | 701 | CASE_CFN_COPYSIGN_FN: |
7a366e88 | 702 | return gimple_call_arg (call, 0); |
703 | ||
704 | default: | |
705 | break; | |
706 | } | |
7fc2f613 | 707 | |
708 | return NULL_TREE; | |
709 | } | |
710 | ||
711 | /* If RHS is an SSA name whose definition just changes the sign of a value, | |
712 | strip all such operations and return the ultimate input to them. | |
713 | Return null otherwise. | |
714 | ||
715 | Although this could in principle lead to quadratic searching, | |
716 | in practice a long sequence of sign manipulations should already | |
717 | have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search | |
718 | for more than one operation in order to catch cases like -abs(x). */ | |
719 | ||
720 | static tree | |
721 | strip_sign_op (tree rhs) | |
722 | { | |
723 | tree new_rhs = strip_sign_op_1 (rhs); | |
724 | if (!new_rhs) | |
725 | return NULL_TREE; | |
726 | while (tree next = strip_sign_op_1 (new_rhs)) | |
727 | new_rhs = next; | |
728 | return new_rhs; | |
729 | } | |
730 | ||
731 | /* Start a change in the value of VAR that is suitable for all non-debug | |
732 | uses of VAR. We need to make sure that debug statements continue to | |
733 | use the original definition of VAR where possible, or are nullified | |
734 | otherwise. */ | |
735 | ||
736 | void | |
737 | backprop::prepare_change (tree var) | |
738 | { | |
c64f38bf | 739 | if (MAY_HAVE_DEBUG_BIND_STMTS) |
7fc2f613 | 740 | insert_debug_temp_for_var_def (NULL, var); |
7cacafcf | 741 | reset_flow_sensitive_info (var); |
7fc2f613 | 742 | } |
743 | ||
744 | /* STMT has been changed. Give the fold machinery a chance to simplify | |
745 | and canonicalize it (e.g. by ensuring that commutative operands have | |
746 | the right order), then record the updates. */ | |
747 | ||
748 | void | |
749 | backprop::complete_change (gimple *stmt) | |
750 | { | |
751 | gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
752 | if (fold_stmt (&gsi)) | |
753 | { | |
754 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
755 | { | |
756 | fprintf (dump_file, " which folds to: "); | |
757 | print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); | |
758 | } | |
759 | } | |
760 | update_stmt (gsi_stmt (gsi)); | |
761 | } | |
762 | ||
763 | /* Optimize CALL, a call to a built-in function with lhs LHS, on the | |
764 | basis that INFO describes all uses of LHS. */ | |
765 | ||
766 | void | |
767 | backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info) | |
768 | { | |
7fc2f613 | 769 | /* If we have an f such that -f(x) = f(-x), and if the sign of the result |
770 | doesn't matter, strip any sign operations from the input. */ | |
7a366e88 | 771 | if (info->flags.ignore_sign |
772 | && negate_mathfn_p (gimple_call_combined_fn (call))) | |
7fc2f613 | 773 | { |
774 | tree new_arg = strip_sign_op (gimple_call_arg (call, 0)); | |
775 | if (new_arg) | |
776 | { | |
777 | prepare_change (lhs); | |
778 | gimple_call_set_arg (call, 0, new_arg); | |
779 | complete_change (call); | |
780 | } | |
781 | } | |
782 | } | |
783 | ||
784 | /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N | |
785 | with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */ | |
786 | ||
787 | void | |
788 | backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1, | |
789 | tree rhs2, tree rhs3) | |
790 | { | |
791 | if (!rhs1 && !rhs2 && !rhs3) | |
792 | return; | |
793 | ||
794 | prepare_change (lhs); | |
795 | if (rhs1) | |
796 | gimple_assign_set_rhs1 (assign, rhs1); | |
797 | if (rhs2) | |
798 | gimple_assign_set_rhs2 (assign, rhs2); | |
799 | if (rhs3) | |
800 | gimple_assign_set_rhs3 (assign, rhs3); | |
801 | complete_change (assign); | |
802 | } | |
803 | ||
804 | /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO | |
805 | describes all uses of LHS. */ | |
806 | ||
807 | void | |
808 | backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info) | |
809 | { | |
810 | switch (gimple_assign_rhs_code (assign)) | |
811 | { | |
812 | case MULT_EXPR: | |
813 | case RDIV_EXPR: | |
814 | /* If the sign of the result doesn't matter, strip sign operations | |
815 | from both inputs. */ | |
816 | if (info->flags.ignore_sign) | |
817 | replace_assign_rhs (assign, lhs, | |
818 | strip_sign_op (gimple_assign_rhs1 (assign)), | |
819 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
820 | NULL_TREE); | |
821 | break; | |
822 | ||
823 | case COND_EXPR: | |
824 | /* If the sign of A ? B : C doesn't matter, strip sign operations | |
825 | from both B and C. */ | |
826 | if (info->flags.ignore_sign) | |
827 | replace_assign_rhs (assign, lhs, | |
828 | NULL_TREE, | |
829 | strip_sign_op (gimple_assign_rhs2 (assign)), | |
830 | strip_sign_op (gimple_assign_rhs3 (assign))); | |
831 | break; | |
832 | ||
833 | default: | |
834 | break; | |
835 | } | |
836 | } | |
837 | ||
838 | /* Optimize PHI, which defines VAR, on the basis that INFO describes all | |
839 | uses of the result. */ | |
840 | ||
841 | void | |
842 | backprop::optimize_phi (gphi *phi, tree var, const usage_info *info) | |
843 | { | |
781996ad | 844 | /* If the sign of the result doesn't matter, try to strip sign operations |
845 | from arguments. */ | |
7fc2f613 | 846 | if (info->flags.ignore_sign) |
847 | { | |
781996ad | 848 | basic_block bb = gimple_bb (phi); |
7fc2f613 | 849 | use_operand_p use; |
850 | ssa_op_iter oi; | |
851 | bool replaced = false; | |
852 | FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) | |
853 | { | |
781996ad | 854 | /* Propagating along abnormal edges is delicate, punt for now. */ |
855 | const int index = PHI_ARG_INDEX_FROM_USE (use); | |
856 | if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL) | |
857 | continue; | |
858 | ||
7fc2f613 | 859 | tree new_arg = strip_sign_op (USE_FROM_PTR (use)); |
860 | if (new_arg) | |
861 | { | |
862 | if (!replaced) | |
863 | prepare_change (var); | |
864 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
865 | note_replacement (phi, USE_FROM_PTR (use), new_arg); | |
866 | replace_exp (use, new_arg); | |
867 | replaced = true; | |
868 | } | |
869 | } | |
870 | } | |
871 | } | |
872 | ||
873 | void | |
874 | backprop::execute () | |
875 | { | |
876 | /* Phase 1: Traverse the function, making optimistic assumptions | |
877 | about any phi whose definition we haven't seen. */ | |
878 | int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); | |
879 | unsigned int postorder_num = post_order_compute (postorder, false, false); | |
880 | for (unsigned int i = 0; i < postorder_num; ++i) | |
881 | { | |
882 | process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); | |
883 | bitmap_set_bit (m_visited_blocks, postorder[i]); | |
884 | } | |
885 | XDELETEVEC (postorder); | |
886 | ||
887 | /* Phase 2: Use the initial (perhaps overly optimistic) information | |
888 | to create a maximal fixed point solution. */ | |
889 | while (!m_worklist.is_empty ()) | |
890 | process_var (pop_from_worklist ()); | |
891 | ||
892 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
893 | fprintf (dump_file, "\n"); | |
894 | ||
895 | /* Phase 3: Do a reverse post-order walk, using information about | |
896 | the uses of SSA names to optimize their definitions. */ | |
897 | for (unsigned int i = m_vars.length (); i-- > 0;) | |
898 | { | |
899 | usage_info *info = m_vars[i].second; | |
900 | if (info->is_useful ()) | |
901 | { | |
902 | tree var = m_vars[i].first; | |
903 | gimple *stmt = SSA_NAME_DEF_STMT (var); | |
904 | if (gcall *call = dyn_cast <gcall *> (stmt)) | |
7a366e88 | 905 | optimize_builtin_call (call, var, info); |
7fc2f613 | 906 | else if (gassign *assign = dyn_cast <gassign *> (stmt)) |
907 | optimize_assign (assign, var, info); | |
908 | else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
909 | optimize_phi (phi, var, info); | |
910 | } | |
911 | } | |
912 | ||
913 | /* Phase 4: Do a post-order walk, deleting statements that are no | |
914 | longer needed. */ | |
915 | for (unsigned int i = 0; i < m_vars.length (); ++i) | |
916 | { | |
917 | tree var = m_vars[i].first; | |
918 | if (has_zero_uses (var)) | |
919 | remove_unused_var (var); | |
920 | } | |
921 | ||
922 | if (dump_file && (dump_flags & TDF_DETAILS)) | |
923 | fprintf (dump_file, "\n"); | |
924 | } | |
925 | ||
926 | const pass_data pass_data_backprop = | |
927 | { | |
928 | GIMPLE_PASS, /* type */ | |
929 | "backprop", /* name */ | |
930 | OPTGROUP_NONE, /* optinfo_flags */ | |
931 | TV_TREE_BACKPROP, /* tv_id */ | |
932 | ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
933 | 0, /* properties_provided */ | |
934 | 0, /* properties_destroyed */ | |
935 | 0, /* todo_flags_start */ | |
936 | 0, /* todo_flags_finish */ | |
937 | }; | |
938 | ||
939 | class pass_backprop : public gimple_opt_pass | |
940 | { | |
941 | public: | |
942 | pass_backprop (gcc::context *ctxt) | |
943 | : gimple_opt_pass (pass_data_backprop, ctxt) | |
944 | {} | |
945 | ||
946 | /* opt_pass methods: */ | |
947 | opt_pass * clone () { return new pass_backprop (m_ctxt); } | |
948 | virtual bool gate (function *) { return flag_ssa_backprop; } | |
949 | virtual unsigned int execute (function *); | |
950 | ||
951 | }; // class pass_backprop | |
952 | ||
953 | unsigned int | |
954 | pass_backprop::execute (function *fn) | |
955 | { | |
956 | backprop (fn).execute (); | |
957 | return 0; | |
958 | } | |
959 | ||
960 | } // anon namespace | |
961 | ||
962 | gimple_opt_pass * | |
963 | make_pass_backprop (gcc::context *ctxt) | |
964 | { | |
965 | return new pass_backprop (ctxt); | |
966 | } |