Mercurial > hg > CbC > CbC_gcc
comparison gcc/gimple-ssa-backprop.c @ 111:04ced10e8804
gcc 7
author | kono |
---|---|
date | Fri, 27 Oct 2017 22:46:09 +0900 |
parents | |
children | 84e7813d76e9 |
comparison
equal
deleted
inserted
replaced
68:561a7518be6b | 111:04ced10e8804 |
---|---|
1 /* Back-propagation of usage information to definitions. | |
2 Copyright (C) 2015-2017 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 | |
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" | |
105 #include "case-cfn-macros.h" | |
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, " "); | |
191 print_generic_expr (file, var); | |
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. */ | |
261 auto_sbitmap m_visited_blocks; | |
262 | |
263 /* A worklist of SSA names whose definitions need to be reconsidered. */ | |
264 auto_vec <tree, 64> m_worklist; | |
265 | |
266 /* The SSA names in M_WORKLIST, identified by their SSA_NAME_VERSION. | |
267 We use a bitmap rather than an sbitmap because most SSA names are | |
268 never added to the worklist. */ | |
269 bitmap m_worklist_names; | |
270 }; | |
271 | |
272 backprop::backprop (function *fn) | |
273 : m_fn (fn), | |
274 m_info_pool ("usage_info"), | |
275 m_visited_blocks (last_basic_block_for_fn (m_fn)), | |
276 m_worklist_names (BITMAP_ALLOC (NULL)) | |
277 { | |
278 bitmap_clear (m_visited_blocks); | |
279 } | |
280 | |
281 backprop::~backprop () | |
282 { | |
283 BITMAP_FREE (m_worklist_names); | |
284 m_info_pool.release (); | |
285 } | |
286 | |
287 /* Return usage information for general operand OP, or null if none. */ | |
288 | |
289 const usage_info * | |
290 backprop::lookup_operand (tree op) | |
291 { | |
292 if (op && TREE_CODE (op) == SSA_NAME) | |
293 { | |
294 usage_info **slot = m_info_map.get (op); | |
295 if (slot) | |
296 return *slot; | |
297 } | |
298 return NULL; | |
299 } | |
300 | |
301 /* Add SSA name VAR to the worklist, if it isn't on the worklist already. */ | |
302 | |
303 void | |
304 backprop::push_to_worklist (tree var) | |
305 { | |
306 if (!bitmap_set_bit (m_worklist_names, SSA_NAME_VERSION (var))) | |
307 return; | |
308 m_worklist.safe_push (var); | |
309 if (dump_file && (dump_flags & TDF_DETAILS)) | |
310 { | |
311 fprintf (dump_file, "[WORKLIST] Pushing "); | |
312 print_generic_expr (dump_file, var); | |
313 fprintf (dump_file, "\n"); | |
314 } | |
315 } | |
316 | |
317 /* Remove and return the next SSA name from the worklist. The worklist | |
318 is known to be nonempty. */ | |
319 | |
320 tree | |
321 backprop::pop_from_worklist () | |
322 { | |
323 tree var = m_worklist.pop (); | |
324 bitmap_clear_bit (m_worklist_names, SSA_NAME_VERSION (var)); | |
325 if (dump_file && (dump_flags & TDF_DETAILS)) | |
326 { | |
327 fprintf (dump_file, "[WORKLIST] Popping "); | |
328 print_generic_expr (dump_file, var); | |
329 fprintf (dump_file, "\n"); | |
330 } | |
331 return var; | |
332 } | |
333 | |
334 /* Make INFO describe all uses of RHS in CALL, which is a call to a | |
335 built-in function. */ | |
336 | |
337 void | |
338 backprop::process_builtin_call_use (gcall *call, tree rhs, usage_info *info) | |
339 { | |
340 combined_fn fn = gimple_call_combined_fn (call); | |
341 tree lhs = gimple_call_lhs (call); | |
342 switch (fn) | |
343 { | |
344 case CFN_LAST: | |
345 break; | |
346 | |
347 CASE_CFN_COS: | |
348 CASE_CFN_COSH: | |
349 CASE_CFN_CCOS: | |
350 CASE_CFN_CCOSH: | |
351 CASE_CFN_HYPOT: | |
352 /* The signs of all inputs are ignored. */ | |
353 info->flags.ignore_sign = true; | |
354 break; | |
355 | |
356 CASE_CFN_COPYSIGN: | |
357 /* The sign of the first input is ignored. */ | |
358 if (rhs != gimple_call_arg (call, 1)) | |
359 info->flags.ignore_sign = true; | |
360 break; | |
361 | |
362 CASE_CFN_POW: | |
363 { | |
364 /* The sign of the first input is ignored as long as the second | |
365 input is an even real. */ | |
366 tree power = gimple_call_arg (call, 1); | |
367 HOST_WIDE_INT n; | |
368 if (TREE_CODE (power) == REAL_CST | |
369 && real_isinteger (&TREE_REAL_CST (power), &n) | |
370 && (n & 1) == 0) | |
371 info->flags.ignore_sign = true; | |
372 break; | |
373 } | |
374 | |
375 CASE_CFN_FMA: | |
376 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't | |
377 matter. */ | |
378 if (gimple_call_arg (call, 0) == rhs | |
379 && gimple_call_arg (call, 1) == rhs | |
380 && gimple_call_arg (call, 2) != rhs) | |
381 info->flags.ignore_sign = true; | |
382 break; | |
383 | |
384 default: | |
385 if (negate_mathfn_p (fn)) | |
386 { | |
387 /* The sign of the (single) input doesn't matter provided | |
388 that the sign of the output doesn't matter. */ | |
389 const usage_info *lhs_info = lookup_operand (lhs); | |
390 if (lhs_info) | |
391 info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
392 } | |
393 break; | |
394 } | |
395 } | |
396 | |
397 /* Make INFO describe all uses of RHS in ASSIGN. */ | |
398 | |
399 void | |
400 backprop::process_assign_use (gassign *assign, tree rhs, usage_info *info) | |
401 { | |
402 tree lhs = gimple_assign_lhs (assign); | |
403 switch (gimple_assign_rhs_code (assign)) | |
404 { | |
405 case ABS_EXPR: | |
406 /* The sign of the input doesn't matter. */ | |
407 info->flags.ignore_sign = true; | |
408 break; | |
409 | |
410 case COND_EXPR: | |
411 /* For A = B ? C : D, propagate information about all uses of A | |
412 to C and D. */ | |
413 if (rhs != gimple_assign_rhs1 (assign)) | |
414 { | |
415 const usage_info *lhs_info = lookup_operand (lhs); | |
416 if (lhs_info) | |
417 *info = *lhs_info; | |
418 } | |
419 break; | |
420 | |
421 case FMA_EXPR: | |
422 /* In X * X + Y, where Y is distinct from X, the sign of X doesn't | |
423 matter. */ | |
424 if (gimple_assign_rhs1 (assign) == rhs | |
425 && gimple_assign_rhs2 (assign) == rhs | |
426 && gimple_assign_rhs3 (assign) != rhs) | |
427 info->flags.ignore_sign = true; | |
428 break; | |
429 | |
430 case MULT_EXPR: | |
431 /* In X * X, the sign of X doesn't matter. */ | |
432 if (gimple_assign_rhs1 (assign) == rhs | |
433 && gimple_assign_rhs2 (assign) == rhs) | |
434 info->flags.ignore_sign = true; | |
435 /* Fall through. */ | |
436 | |
437 case NEGATE_EXPR: | |
438 case RDIV_EXPR: | |
439 /* If the sign of the result doesn't matter, the sign of the inputs | |
440 doesn't matter either. */ | |
441 if (FLOAT_TYPE_P (TREE_TYPE (rhs))) | |
442 { | |
443 const usage_info *lhs_info = lookup_operand (lhs); | |
444 if (lhs_info) | |
445 info->flags.ignore_sign = lhs_info->flags.ignore_sign; | |
446 } | |
447 break; | |
448 | |
449 default: | |
450 break; | |
451 } | |
452 } | |
453 | |
454 /* Make INFO describe the uses of PHI's result. */ | |
455 | |
456 void | |
457 backprop::process_phi_use (gphi *phi, usage_info *info) | |
458 { | |
459 tree result = gimple_phi_result (phi); | |
460 if (const usage_info *result_info = lookup_operand (result)) | |
461 *info = *result_info; | |
462 } | |
463 | |
464 /* Make INFO describe all uses of RHS in STMT. */ | |
465 | |
466 void | |
467 backprop::process_use (gimple *stmt, tree rhs, usage_info *info) | |
468 { | |
469 if (dump_file && (dump_flags & TDF_DETAILS)) | |
470 { | |
471 fprintf (dump_file, "[USE] "); | |
472 print_generic_expr (dump_file, rhs); | |
473 fprintf (dump_file, " in "); | |
474 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
475 } | |
476 | |
477 if (gcall *call = dyn_cast <gcall *> (stmt)) | |
478 process_builtin_call_use (call, rhs, info); | |
479 else if (gassign *assign = dyn_cast <gassign *> (stmt)) | |
480 process_assign_use (assign, rhs, info); | |
481 else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
482 process_phi_use (phi, info); | |
483 | |
484 if (dump_file && (dump_flags & TDF_DETAILS)) | |
485 dump_usage_info (dump_file, rhs, info); | |
486 } | |
487 | |
488 /* Make INFO describe all uses of VAR, returning true if the result | |
489 is useful. If the uses include phis that haven't been processed yet, | |
490 make the most optimistic assumption possible, so that we aim for | |
491 a maximum rather than a minimum fixed point. */ | |
492 | |
493 bool | |
494 backprop::intersect_uses (tree var, usage_info *info) | |
495 { | |
496 imm_use_iterator iter; | |
497 gimple *stmt; | |
498 *info = usage_info::intersection_identity (); | |
499 FOR_EACH_IMM_USE_STMT (stmt, iter, var) | |
500 { | |
501 if (is_gimple_debug (stmt)) | |
502 continue; | |
503 if (is_a <gphi *> (stmt) | |
504 && !bitmap_bit_p (m_visited_blocks, gimple_bb (stmt)->index)) | |
505 { | |
506 /* Skip unprocessed phis. */ | |
507 if (dump_file && (dump_flags & TDF_DETAILS)) | |
508 { | |
509 fprintf (dump_file, "[BACKEDGE] "); | |
510 print_generic_expr (dump_file, var); | |
511 fprintf (dump_file, " in "); | |
512 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
513 } | |
514 } | |
515 else | |
516 { | |
517 usage_info subinfo; | |
518 process_use (stmt, var, &subinfo); | |
519 *info &= subinfo; | |
520 if (!info->is_useful ()) | |
521 { | |
522 BREAK_FROM_IMM_USE_STMT (iter); | |
523 return false; | |
524 } | |
525 } | |
526 } | |
527 return true; | |
528 } | |
529 | |
530 /* Queue for reconsideration any input of STMT that has information | |
531 associated with it. This is used if that information might be | |
532 too optimistic. */ | |
533 | |
534 void | |
535 backprop::reprocess_inputs (gimple *stmt) | |
536 { | |
537 use_operand_p use_p; | |
538 ssa_op_iter oi; | |
539 FOR_EACH_PHI_OR_STMT_USE (use_p, stmt, oi, SSA_OP_USE) | |
540 { | |
541 tree var = get_use_from_ptr (use_p); | |
542 if (lookup_operand (var)) | |
543 push_to_worklist (var); | |
544 } | |
545 } | |
546 | |
547 /* Say that we're recording INFO for SSA name VAR, or that we're deleting | |
548 existing information if INFO is null. INTRO describes the change. */ | |
549 | |
550 static void | |
551 dump_var_info (tree var, usage_info *info, const char *intro) | |
552 { | |
553 fprintf (dump_file, "[DEF] %s for ", intro); | |
554 print_gimple_stmt (dump_file, SSA_NAME_DEF_STMT (var), 0, TDF_SLIM); | |
555 if (info) | |
556 dump_usage_info (dump_file, var, info); | |
557 } | |
558 | |
559 /* Process all uses of VAR and record or update the result in | |
560 M_INFO_MAP and M_VARS. */ | |
561 | |
562 void | |
563 backprop::process_var (tree var) | |
564 { | |
565 if (has_zero_uses (var)) | |
566 return; | |
567 | |
568 usage_info info; | |
569 intersect_uses (var, &info); | |
570 | |
571 gimple *stmt = SSA_NAME_DEF_STMT (var); | |
572 if (info.is_useful ()) | |
573 { | |
574 bool existed; | |
575 usage_info *&map_info = m_info_map.get_or_insert (var, &existed); | |
576 if (!existed) | |
577 { | |
578 /* Recording information about VAR for the first time. */ | |
579 map_info = m_info_pool.allocate (); | |
580 *map_info = info; | |
581 m_vars.safe_push (var_info_pair (var, map_info)); | |
582 if (dump_file && (dump_flags & TDF_DETAILS)) | |
583 dump_var_info (var, map_info, "Recording new information"); | |
584 | |
585 /* If STMT is a phi, reprocess any backedge uses. This is a | |
586 no-op for other uses, which won't have any information | |
587 associated with them. */ | |
588 if (is_a <gphi *> (stmt)) | |
589 reprocess_inputs (stmt); | |
590 } | |
591 else if (info != *map_info) | |
592 { | |
593 /* Recording information that is less optimistic than before. */ | |
594 gcc_checking_assert ((info & *map_info) == info); | |
595 *map_info = info; | |
596 if (dump_file && (dump_flags & TDF_DETAILS)) | |
597 dump_var_info (var, map_info, "Updating information"); | |
598 reprocess_inputs (stmt); | |
599 } | |
600 } | |
601 else | |
602 { | |
603 if (usage_info **slot = m_info_map.get (var)) | |
604 { | |
605 /* Removing previously-recorded information. */ | |
606 **slot = info; | |
607 m_info_map.remove (var); | |
608 if (dump_file && (dump_flags & TDF_DETAILS)) | |
609 dump_var_info (var, NULL, "Deleting information"); | |
610 reprocess_inputs (stmt); | |
611 } | |
612 else | |
613 { | |
614 /* If STMT is a phi, remove any information recorded for | |
615 its arguments. */ | |
616 if (is_a <gphi *> (stmt)) | |
617 reprocess_inputs (stmt); | |
618 } | |
619 } | |
620 } | |
621 | |
622 /* Process all statements and phis in BB, during the first post-order walk. */ | |
623 | |
624 void | |
625 backprop::process_block (basic_block bb) | |
626 { | |
627 for (gimple_stmt_iterator gsi = gsi_last_bb (bb); !gsi_end_p (gsi); | |
628 gsi_prev (&gsi)) | |
629 { | |
630 tree lhs = gimple_get_lhs (gsi_stmt (gsi)); | |
631 if (lhs && TREE_CODE (lhs) == SSA_NAME) | |
632 process_var (lhs); | |
633 } | |
634 for (gphi_iterator gpi = gsi_start_phis (bb); !gsi_end_p (gpi); | |
635 gsi_next (&gpi)) | |
636 process_var (gimple_phi_result (gpi.phi ())); | |
637 } | |
638 | |
639 /* Delete the definition of VAR, which has no uses. */ | |
640 | |
641 static void | |
642 remove_unused_var (tree var) | |
643 { | |
644 gimple *stmt = SSA_NAME_DEF_STMT (var); | |
645 if (dump_file && (dump_flags & TDF_DETAILS)) | |
646 { | |
647 fprintf (dump_file, "Deleting "); | |
648 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
649 } | |
650 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
651 gsi_remove (&gsi, true); | |
652 release_defs (stmt); | |
653 } | |
654 | |
655 /* Note that we're replacing OLD_RHS with NEW_RHS in STMT. */ | |
656 | |
657 static void | |
658 note_replacement (gimple *stmt, tree old_rhs, tree new_rhs) | |
659 { | |
660 fprintf (dump_file, "Replacing use of "); | |
661 print_generic_expr (dump_file, old_rhs); | |
662 fprintf (dump_file, " with "); | |
663 print_generic_expr (dump_file, new_rhs); | |
664 fprintf (dump_file, " in "); | |
665 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM); | |
666 } | |
667 | |
668 /* If RHS is an SSA name whose definition just changes the sign of a value, | |
669 return that other value, otherwise return null. */ | |
670 | |
671 static tree | |
672 strip_sign_op_1 (tree rhs) | |
673 { | |
674 if (TREE_CODE (rhs) != SSA_NAME) | |
675 return NULL_TREE; | |
676 | |
677 gimple *def_stmt = SSA_NAME_DEF_STMT (rhs); | |
678 if (gassign *assign = dyn_cast <gassign *> (def_stmt)) | |
679 switch (gimple_assign_rhs_code (assign)) | |
680 { | |
681 case ABS_EXPR: | |
682 case NEGATE_EXPR: | |
683 return gimple_assign_rhs1 (assign); | |
684 | |
685 default: | |
686 break; | |
687 } | |
688 else if (gcall *call = dyn_cast <gcall *> (def_stmt)) | |
689 switch (gimple_call_combined_fn (call)) | |
690 { | |
691 CASE_CFN_COPYSIGN: | |
692 return gimple_call_arg (call, 0); | |
693 | |
694 default: | |
695 break; | |
696 } | |
697 | |
698 return NULL_TREE; | |
699 } | |
700 | |
701 /* If RHS is an SSA name whose definition just changes the sign of a value, | |
702 strip all such operations and return the ultimate input to them. | |
703 Return null otherwise. | |
704 | |
705 Although this could in principle lead to quadratic searching, | |
706 in practice a long sequence of sign manipulations should already | |
707 have been folded down. E.g. --x -> x, abs(-x) -> abs(x). We search | |
708 for more than one operation in order to catch cases like -abs(x). */ | |
709 | |
710 static tree | |
711 strip_sign_op (tree rhs) | |
712 { | |
713 tree new_rhs = strip_sign_op_1 (rhs); | |
714 if (!new_rhs) | |
715 return NULL_TREE; | |
716 while (tree next = strip_sign_op_1 (new_rhs)) | |
717 new_rhs = next; | |
718 return new_rhs; | |
719 } | |
720 | |
721 /* Start a change in the value of VAR that is suitable for all non-debug | |
722 uses of VAR. We need to make sure that debug statements continue to | |
723 use the original definition of VAR where possible, or are nullified | |
724 otherwise. */ | |
725 | |
726 void | |
727 backprop::prepare_change (tree var) | |
728 { | |
729 if (MAY_HAVE_DEBUG_STMTS) | |
730 insert_debug_temp_for_var_def (NULL, var); | |
731 reset_flow_sensitive_info (var); | |
732 } | |
733 | |
734 /* STMT has been changed. Give the fold machinery a chance to simplify | |
735 and canonicalize it (e.g. by ensuring that commutative operands have | |
736 the right order), then record the updates. */ | |
737 | |
738 void | |
739 backprop::complete_change (gimple *stmt) | |
740 { | |
741 gimple_stmt_iterator gsi = gsi_for_stmt (stmt); | |
742 if (fold_stmt (&gsi)) | |
743 { | |
744 if (dump_file && (dump_flags & TDF_DETAILS)) | |
745 { | |
746 fprintf (dump_file, " which folds to: "); | |
747 print_gimple_stmt (dump_file, gsi_stmt (gsi), 0, TDF_SLIM); | |
748 } | |
749 } | |
750 update_stmt (gsi_stmt (gsi)); | |
751 } | |
752 | |
753 /* Optimize CALL, a call to a built-in function with lhs LHS, on the | |
754 basis that INFO describes all uses of LHS. */ | |
755 | |
756 void | |
757 backprop::optimize_builtin_call (gcall *call, tree lhs, const usage_info *info) | |
758 { | |
759 /* If we have an f such that -f(x) = f(-x), and if the sign of the result | |
760 doesn't matter, strip any sign operations from the input. */ | |
761 if (info->flags.ignore_sign | |
762 && negate_mathfn_p (gimple_call_combined_fn (call))) | |
763 { | |
764 tree new_arg = strip_sign_op (gimple_call_arg (call, 0)); | |
765 if (new_arg) | |
766 { | |
767 prepare_change (lhs); | |
768 gimple_call_set_arg (call, 0, new_arg); | |
769 complete_change (call); | |
770 } | |
771 } | |
772 } | |
773 | |
774 /* Optimize ASSIGN, an assignment to LHS, by replacing rhs operand N | |
775 with RHS<N>, if RHS<N> is nonnull. This may change the value of LHS. */ | |
776 | |
777 void | |
778 backprop::replace_assign_rhs (gassign *assign, tree lhs, tree rhs1, | |
779 tree rhs2, tree rhs3) | |
780 { | |
781 if (!rhs1 && !rhs2 && !rhs3) | |
782 return; | |
783 | |
784 prepare_change (lhs); | |
785 if (rhs1) | |
786 gimple_assign_set_rhs1 (assign, rhs1); | |
787 if (rhs2) | |
788 gimple_assign_set_rhs2 (assign, rhs2); | |
789 if (rhs3) | |
790 gimple_assign_set_rhs3 (assign, rhs3); | |
791 complete_change (assign); | |
792 } | |
793 | |
794 /* Optimize ASSIGN, an assignment to LHS, on the basis that INFO | |
795 describes all uses of LHS. */ | |
796 | |
797 void | |
798 backprop::optimize_assign (gassign *assign, tree lhs, const usage_info *info) | |
799 { | |
800 switch (gimple_assign_rhs_code (assign)) | |
801 { | |
802 case MULT_EXPR: | |
803 case RDIV_EXPR: | |
804 /* If the sign of the result doesn't matter, strip sign operations | |
805 from both inputs. */ | |
806 if (info->flags.ignore_sign) | |
807 replace_assign_rhs (assign, lhs, | |
808 strip_sign_op (gimple_assign_rhs1 (assign)), | |
809 strip_sign_op (gimple_assign_rhs2 (assign)), | |
810 NULL_TREE); | |
811 break; | |
812 | |
813 case COND_EXPR: | |
814 /* If the sign of A ? B : C doesn't matter, strip sign operations | |
815 from both B and C. */ | |
816 if (info->flags.ignore_sign) | |
817 replace_assign_rhs (assign, lhs, | |
818 NULL_TREE, | |
819 strip_sign_op (gimple_assign_rhs2 (assign)), | |
820 strip_sign_op (gimple_assign_rhs3 (assign))); | |
821 break; | |
822 | |
823 default: | |
824 break; | |
825 } | |
826 } | |
827 | |
828 /* Optimize PHI, which defines VAR, on the basis that INFO describes all | |
829 uses of the result. */ | |
830 | |
831 void | |
832 backprop::optimize_phi (gphi *phi, tree var, const usage_info *info) | |
833 { | |
834 /* If the sign of the result doesn't matter, try to strip sign operations | |
835 from arguments. */ | |
836 if (info->flags.ignore_sign) | |
837 { | |
838 basic_block bb = gimple_bb (phi); | |
839 use_operand_p use; | |
840 ssa_op_iter oi; | |
841 bool replaced = false; | |
842 FOR_EACH_PHI_ARG (use, phi, oi, SSA_OP_USE) | |
843 { | |
844 /* Propagating along abnormal edges is delicate, punt for now. */ | |
845 const int index = PHI_ARG_INDEX_FROM_USE (use); | |
846 if (EDGE_PRED (bb, index)->flags & EDGE_ABNORMAL) | |
847 continue; | |
848 | |
849 tree new_arg = strip_sign_op (USE_FROM_PTR (use)); | |
850 if (new_arg) | |
851 { | |
852 if (!replaced) | |
853 prepare_change (var); | |
854 if (dump_file && (dump_flags & TDF_DETAILS)) | |
855 note_replacement (phi, USE_FROM_PTR (use), new_arg); | |
856 replace_exp (use, new_arg); | |
857 replaced = true; | |
858 } | |
859 } | |
860 } | |
861 } | |
862 | |
863 void | |
864 backprop::execute () | |
865 { | |
866 /* Phase 1: Traverse the function, making optimistic assumptions | |
867 about any phi whose definition we haven't seen. */ | |
868 int *postorder = XNEWVEC (int, n_basic_blocks_for_fn (m_fn)); | |
869 unsigned int postorder_num = post_order_compute (postorder, false, false); | |
870 for (unsigned int i = 0; i < postorder_num; ++i) | |
871 { | |
872 process_block (BASIC_BLOCK_FOR_FN (m_fn, postorder[i])); | |
873 bitmap_set_bit (m_visited_blocks, postorder[i]); | |
874 } | |
875 XDELETEVEC (postorder); | |
876 | |
877 /* Phase 2: Use the initial (perhaps overly optimistic) information | |
878 to create a maximal fixed point solution. */ | |
879 while (!m_worklist.is_empty ()) | |
880 process_var (pop_from_worklist ()); | |
881 | |
882 if (dump_file && (dump_flags & TDF_DETAILS)) | |
883 fprintf (dump_file, "\n"); | |
884 | |
885 /* Phase 3: Do a reverse post-order walk, using information about | |
886 the uses of SSA names to optimize their definitions. */ | |
887 for (unsigned int i = m_vars.length (); i-- > 0;) | |
888 { | |
889 usage_info *info = m_vars[i].second; | |
890 if (info->is_useful ()) | |
891 { | |
892 tree var = m_vars[i].first; | |
893 gimple *stmt = SSA_NAME_DEF_STMT (var); | |
894 if (gcall *call = dyn_cast <gcall *> (stmt)) | |
895 optimize_builtin_call (call, var, info); | |
896 else if (gassign *assign = dyn_cast <gassign *> (stmt)) | |
897 optimize_assign (assign, var, info); | |
898 else if (gphi *phi = dyn_cast <gphi *> (stmt)) | |
899 optimize_phi (phi, var, info); | |
900 } | |
901 } | |
902 | |
903 /* Phase 4: Do a post-order walk, deleting statements that are no | |
904 longer needed. */ | |
905 for (unsigned int i = 0; i < m_vars.length (); ++i) | |
906 { | |
907 tree var = m_vars[i].first; | |
908 if (has_zero_uses (var)) | |
909 remove_unused_var (var); | |
910 } | |
911 | |
912 if (dump_file && (dump_flags & TDF_DETAILS)) | |
913 fprintf (dump_file, "\n"); | |
914 } | |
915 | |
916 const pass_data pass_data_backprop = | |
917 { | |
918 GIMPLE_PASS, /* type */ | |
919 "backprop", /* name */ | |
920 OPTGROUP_NONE, /* optinfo_flags */ | |
921 TV_TREE_BACKPROP, /* tv_id */ | |
922 ( PROP_cfg | PROP_ssa ), /* properties_required */ | |
923 0, /* properties_provided */ | |
924 0, /* properties_destroyed */ | |
925 0, /* todo_flags_start */ | |
926 0, /* todo_flags_finish */ | |
927 }; | |
928 | |
929 class pass_backprop : public gimple_opt_pass | |
930 { | |
931 public: | |
932 pass_backprop (gcc::context *ctxt) | |
933 : gimple_opt_pass (pass_data_backprop, ctxt) | |
934 {} | |
935 | |
936 /* opt_pass methods: */ | |
937 opt_pass * clone () { return new pass_backprop (m_ctxt); } | |
938 virtual bool gate (function *) { return flag_ssa_backprop; } | |
939 virtual unsigned int execute (function *); | |
940 | |
941 }; // class pass_backprop | |
942 | |
943 unsigned int | |
944 pass_backprop::execute (function *fn) | |
945 { | |
946 backprop (fn).execute (); | |
947 return 0; | |
948 } | |
949 | |
950 } // anon namespace | |
951 | |
952 gimple_opt_pass * | |
953 make_pass_backprop (gcc::context *ctxt) | |
954 { | |
955 return new pass_backprop (ctxt); | |
956 } |