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