|
0
|
1 /* Generic SSA value propagation engine.
|
|
|
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
|
|
|
3 Contributed by Diego Novillo <dnovillo@redhat.com>
|
|
|
4
|
|
|
5 This file is part of GCC.
|
|
|
6
|
|
|
7 GCC is free software; you can redistribute it and/or modify it
|
|
|
8 under the terms of the GNU General Public License as published by the
|
|
|
9 Free Software Foundation; either version 3, or (at your option) any
|
|
|
10 later version.
|
|
|
11
|
|
|
12 GCC is distributed in the hope that it will be useful, but WITHOUT
|
|
|
13 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
|
|
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
|
|
15 for more details.
|
|
|
16
|
|
|
17 You should have received a copy of the GNU General Public License
|
|
|
18 along with GCC; see the file COPYING3. If not see
|
|
|
19 <http://www.gnu.org/licenses/>. */
|
|
|
20
|
|
|
21 #include "config.h"
|
|
|
22 #include "system.h"
|
|
|
23 #include "coretypes.h"
|
|
|
24 #include "tm.h"
|
|
|
25 #include "tree.h"
|
|
|
26 #include "flags.h"
|
|
|
27 #include "rtl.h"
|
|
|
28 #include "tm_p.h"
|
|
|
29 #include "ggc.h"
|
|
|
30 #include "basic-block.h"
|
|
|
31 #include "output.h"
|
|
|
32 #include "expr.h"
|
|
|
33 #include "function.h"
|
|
|
34 #include "diagnostic.h"
|
|
|
35 #include "timevar.h"
|
|
|
36 #include "tree-dump.h"
|
|
|
37 #include "tree-flow.h"
|
|
|
38 #include "tree-pass.h"
|
|
|
39 #include "tree-ssa-propagate.h"
|
|
|
40 #include "langhooks.h"
|
|
|
41 #include "varray.h"
|
|
|
42 #include "vec.h"
|
|
|
43 #include "value-prof.h"
|
|
|
44 #include "gimple.h"
|
|
|
45
|
|
|
46 /* This file implements a generic value propagation engine based on
|
|
|
47 the same propagation used by the SSA-CCP algorithm [1].
|
|
|
48
|
|
|
49 Propagation is performed by simulating the execution of every
|
|
|
50 statement that produces the value being propagated. Simulation
|
|
|
51 proceeds as follows:
|
|
|
52
|
|
|
53 1- Initially, all edges of the CFG are marked not executable and
|
|
|
54 the CFG worklist is seeded with all the statements in the entry
|
|
|
55 basic block (block 0).
|
|
|
56
|
|
|
57 2- Every statement S is simulated with a call to the call-back
|
|
|
58 function SSA_PROP_VISIT_STMT. This evaluation may produce 3
|
|
|
59 results:
|
|
|
60
|
|
|
61 SSA_PROP_NOT_INTERESTING: Statement S produces nothing of
|
|
|
62 interest and does not affect any of the work lists.
|
|
|
63
|
|
|
64 SSA_PROP_VARYING: The value produced by S cannot be determined
|
|
|
65 at compile time. Further simulation of S is not required.
|
|
|
66 If S is a conditional jump, all the outgoing edges for the
|
|
|
67 block are considered executable and added to the work
|
|
|
68 list.
|
|
|
69
|
|
|
70 SSA_PROP_INTERESTING: S produces a value that can be computed
|
|
|
71 at compile time. Its result can be propagated into the
|
|
|
72 statements that feed from S. Furthermore, if S is a
|
|
|
73 conditional jump, only the edge known to be taken is added
|
|
|
74 to the work list. Edges that are known not to execute are
|
|
|
75 never simulated.
|
|
|
76
|
|
|
77 3- PHI nodes are simulated with a call to SSA_PROP_VISIT_PHI. The
|
|
|
78 return value from SSA_PROP_VISIT_PHI has the same semantics as
|
|
|
79 described in #2.
|
|
|
80
|
|
|
81 4- Three work lists are kept. Statements are only added to these
|
|
|
82 lists if they produce one of SSA_PROP_INTERESTING or
|
|
|
83 SSA_PROP_VARYING.
|
|
|
84
|
|
|
85 CFG_BLOCKS contains the list of blocks to be simulated.
|
|
|
86 Blocks are added to this list if their incoming edges are
|
|
|
87 found executable.
|
|
|
88
|
|
|
89 VARYING_SSA_EDGES contains the list of statements that feed
|
|
|
90 from statements that produce an SSA_PROP_VARYING result.
|
|
|
91 These are simulated first to speed up processing.
|
|
|
92
|
|
|
93 INTERESTING_SSA_EDGES contains the list of statements that
|
|
|
94 feed from statements that produce an SSA_PROP_INTERESTING
|
|
|
95 result.
|
|
|
96
|
|
|
97 5- Simulation terminates when all three work lists are drained.
|
|
|
98
|
|
|
99 Before calling ssa_propagate, it is important to clear
|
|
|
100 prop_simulate_again_p for all the statements in the program that
|
|
|
101 should be simulated. This initialization allows an implementation
|
|
|
102 to specify which statements should never be simulated.
|
|
|
103
|
|
|
104 It is also important to compute def-use information before calling
|
|
|
105 ssa_propagate.
|
|
|
106
|
|
|
107 References:
|
|
|
108
|
|
|
109 [1] Constant propagation with conditional branches,
|
|
|
110 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
|
|
|
111
|
|
|
112 [2] Building an Optimizing Compiler,
|
|
|
113 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
|
|
|
114
|
|
|
115 [3] Advanced Compiler Design and Implementation,
|
|
|
116 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
|
|
|
117
|
|
|
118 /* Function pointers used to parameterize the propagation engine. */
|
|
|
119 static ssa_prop_visit_stmt_fn ssa_prop_visit_stmt;
|
|
|
120 static ssa_prop_visit_phi_fn ssa_prop_visit_phi;
|
|
|
121
|
|
|
122 /* Keep track of statements that have been added to one of the SSA
|
|
|
123 edges worklists. This flag is used to avoid visiting statements
|
|
|
124 unnecessarily when draining an SSA edge worklist. If while
|
|
|
125 simulating a basic block, we find a statement with
|
|
|
126 STMT_IN_SSA_EDGE_WORKLIST set, we clear it to prevent SSA edge
|
|
|
127 processing from visiting it again.
|
|
|
128
|
|
|
129 NOTE: users of the propagation engine are not allowed to use
|
|
|
130 the GF_PLF_1 flag. */
|
|
|
131 #define STMT_IN_SSA_EDGE_WORKLIST GF_PLF_1
|
|
|
132
|
|
|
133 /* A bitmap to keep track of executable blocks in the CFG. */
|
|
|
134 static sbitmap executable_blocks;
|
|
|
135
|
|
|
136 /* Array of control flow edges on the worklist. */
|
|
|
137 static VEC(basic_block,heap) *cfg_blocks;
|
|
|
138
|
|
|
139 static unsigned int cfg_blocks_num = 0;
|
|
|
140 static int cfg_blocks_tail;
|
|
|
141 static int cfg_blocks_head;
|
|
|
142
|
|
|
143 static sbitmap bb_in_list;
|
|
|
144
|
|
|
145 /* Worklist of SSA edges which will need reexamination as their
|
|
|
146 definition has changed. SSA edges are def-use edges in the SSA
|
|
|
147 web. For each D-U edge, we store the target statement or PHI node
|
|
|
148 U. */
|
|
|
149 static GTY(()) VEC(gimple,gc) *interesting_ssa_edges;
|
|
|
150
|
|
|
151 /* Identical to INTERESTING_SSA_EDGES. For performance reasons, the
|
|
|
152 list of SSA edges is split into two. One contains all SSA edges
|
|
|
153 who need to be reexamined because their lattice value changed to
|
|
|
154 varying (this worklist), and the other contains all other SSA edges
|
|
|
155 to be reexamined (INTERESTING_SSA_EDGES).
|
|
|
156
|
|
|
157 Since most values in the program are VARYING, the ideal situation
|
|
|
158 is to move them to that lattice value as quickly as possible.
|
|
|
159 Thus, it doesn't make sense to process any other type of lattice
|
|
|
160 value until all VARYING values are propagated fully, which is one
|
|
|
161 thing using the VARYING worklist achieves. In addition, if we
|
|
|
162 don't use a separate worklist for VARYING edges, we end up with
|
|
|
163 situations where lattice values move from
|
|
|
164 UNDEFINED->INTERESTING->VARYING instead of UNDEFINED->VARYING. */
|
|
|
165 static GTY(()) VEC(gimple,gc) *varying_ssa_edges;
|
|
|
166
|
|
|
167
|
|
|
168 /* Return true if the block worklist empty. */
|
|
|
169
|
|
|
170 static inline bool
|
|
|
171 cfg_blocks_empty_p (void)
|
|
|
172 {
|
|
|
173 return (cfg_blocks_num == 0);
|
|
|
174 }
|
|
|
175
|
|
|
176
|
|
|
177 /* Add a basic block to the worklist. The block must not be already
|
|
|
178 in the worklist, and it must not be the ENTRY or EXIT block. */
|
|
|
179
|
|
|
180 static void
|
|
|
181 cfg_blocks_add (basic_block bb)
|
|
|
182 {
|
|
|
183 bool head = false;
|
|
|
184
|
|
|
185 gcc_assert (bb != ENTRY_BLOCK_PTR && bb != EXIT_BLOCK_PTR);
|
|
|
186 gcc_assert (!TEST_BIT (bb_in_list, bb->index));
|
|
|
187
|
|
|
188 if (cfg_blocks_empty_p ())
|
|
|
189 {
|
|
|
190 cfg_blocks_tail = cfg_blocks_head = 0;
|
|
|
191 cfg_blocks_num = 1;
|
|
|
192 }
|
|
|
193 else
|
|
|
194 {
|
|
|
195 cfg_blocks_num++;
|
|
|
196 if (cfg_blocks_num > VEC_length (basic_block, cfg_blocks))
|
|
|
197 {
|
|
|
198 /* We have to grow the array now. Adjust to queue to occupy
|
|
|
199 the full space of the original array. We do not need to
|
|
|
200 initialize the newly allocated portion of the array
|
|
|
201 because we keep track of CFG_BLOCKS_HEAD and
|
|
|
202 CFG_BLOCKS_HEAD. */
|
|
|
203 cfg_blocks_tail = VEC_length (basic_block, cfg_blocks);
|
|
|
204 cfg_blocks_head = 0;
|
|
|
205 VEC_safe_grow (basic_block, heap, cfg_blocks, 2 * cfg_blocks_tail);
|
|
|
206 }
|
|
|
207 /* Minor optimization: we prefer to see blocks with more
|
|
|
208 predecessors later, because there is more of a chance that
|
|
|
209 the incoming edges will be executable. */
|
|
|
210 else if (EDGE_COUNT (bb->preds)
|
|
|
211 >= EDGE_COUNT (VEC_index (basic_block, cfg_blocks,
|
|
|
212 cfg_blocks_head)->preds))
|
|
|
213 cfg_blocks_tail = ((cfg_blocks_tail + 1)
|
|
|
214 % VEC_length (basic_block, cfg_blocks));
|
|
|
215 else
|
|
|
216 {
|
|
|
217 if (cfg_blocks_head == 0)
|
|
|
218 cfg_blocks_head = VEC_length (basic_block, cfg_blocks);
|
|
|
219 --cfg_blocks_head;
|
|
|
220 head = true;
|
|
|
221 }
|
|
|
222 }
|
|
|
223
|
|
|
224 VEC_replace (basic_block, cfg_blocks,
|
|
|
225 head ? cfg_blocks_head : cfg_blocks_tail,
|
|
|
226 bb);
|
|
|
227 SET_BIT (bb_in_list, bb->index);
|
|
|
228 }
|
|
|
229
|
|
|
230
|
|
|
231 /* Remove a block from the worklist. */
|
|
|
232
|
|
|
233 static basic_block
|
|
|
234 cfg_blocks_get (void)
|
|
|
235 {
|
|
|
236 basic_block bb;
|
|
|
237
|
|
|
238 bb = VEC_index (basic_block, cfg_blocks, cfg_blocks_head);
|
|
|
239
|
|
|
240 gcc_assert (!cfg_blocks_empty_p ());
|
|
|
241 gcc_assert (bb);
|
|
|
242
|
|
|
243 cfg_blocks_head = ((cfg_blocks_head + 1)
|
|
|
244 % VEC_length (basic_block, cfg_blocks));
|
|
|
245 --cfg_blocks_num;
|
|
|
246 RESET_BIT (bb_in_list, bb->index);
|
|
|
247
|
|
|
248 return bb;
|
|
|
249 }
|
|
|
250
|
|
|
251
|
|
|
252 /* We have just defined a new value for VAR. If IS_VARYING is true,
|
|
|
253 add all immediate uses of VAR to VARYING_SSA_EDGES, otherwise add
|
|
|
254 them to INTERESTING_SSA_EDGES. */
|
|
|
255
|
|
|
256 static void
|
|
|
257 add_ssa_edge (tree var, bool is_varying)
|
|
|
258 {
|
|
|
259 imm_use_iterator iter;
|
|
|
260 use_operand_p use_p;
|
|
|
261
|
|
|
262 FOR_EACH_IMM_USE_FAST (use_p, iter, var)
|
|
|
263 {
|
|
|
264 gimple use_stmt = USE_STMT (use_p);
|
|
|
265
|
|
|
266 if (prop_simulate_again_p (use_stmt)
|
|
|
267 && !gimple_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST))
|
|
|
268 {
|
|
|
269 gimple_set_plf (use_stmt, STMT_IN_SSA_EDGE_WORKLIST, true);
|
|
|
270 if (is_varying)
|
|
|
271 VEC_safe_push (gimple, gc, varying_ssa_edges, use_stmt);
|
|
|
272 else
|
|
|
273 VEC_safe_push (gimple, gc, interesting_ssa_edges, use_stmt);
|
|
|
274 }
|
|
|
275 }
|
|
|
276 }
|
|
|
277
|
|
|
278
|
|
|
279 /* Add edge E to the control flow worklist. */
|
|
|
280
|
|
|
281 static void
|
|
|
282 add_control_edge (edge e)
|
|
|
283 {
|
|
|
284 basic_block bb = e->dest;
|
|
|
285 if (bb == EXIT_BLOCK_PTR)
|
|
|
286 return;
|
|
|
287
|
|
|
288 /* If the edge had already been executed, skip it. */
|
|
|
289 if (e->flags & EDGE_EXECUTABLE)
|
|
|
290 return;
|
|
|
291
|
|
|
292 e->flags |= EDGE_EXECUTABLE;
|
|
|
293
|
|
|
294 /* If the block is already in the list, we're done. */
|
|
|
295 if (TEST_BIT (bb_in_list, bb->index))
|
|
|
296 return;
|
|
|
297
|
|
|
298 cfg_blocks_add (bb);
|
|
|
299
|
|
|
300 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
301 fprintf (dump_file, "Adding Destination of edge (%d -> %d) to worklist\n\n",
|
|
|
302 e->src->index, e->dest->index);
|
|
|
303 }
|
|
|
304
|
|
|
305
|
|
|
306 /* Simulate the execution of STMT and update the work lists accordingly. */
|
|
|
307
|
|
|
308 static void
|
|
|
309 simulate_stmt (gimple stmt)
|
|
|
310 {
|
|
|
311 enum ssa_prop_result val = SSA_PROP_NOT_INTERESTING;
|
|
|
312 edge taken_edge = NULL;
|
|
|
313 tree output_name = NULL_TREE;
|
|
|
314
|
|
|
315 /* Don't bother visiting statements that are already
|
|
|
316 considered varying by the propagator. */
|
|
|
317 if (!prop_simulate_again_p (stmt))
|
|
|
318 return;
|
|
|
319
|
|
|
320 if (gimple_code (stmt) == GIMPLE_PHI)
|
|
|
321 {
|
|
|
322 val = ssa_prop_visit_phi (stmt);
|
|
|
323 output_name = gimple_phi_result (stmt);
|
|
|
324 }
|
|
|
325 else
|
|
|
326 val = ssa_prop_visit_stmt (stmt, &taken_edge, &output_name);
|
|
|
327
|
|
|
328 if (val == SSA_PROP_VARYING)
|
|
|
329 {
|
|
|
330 prop_set_simulate_again (stmt, false);
|
|
|
331
|
|
|
332 /* If the statement produced a new varying value, add the SSA
|
|
|
333 edges coming out of OUTPUT_NAME. */
|
|
|
334 if (output_name)
|
|
|
335 add_ssa_edge (output_name, true);
|
|
|
336
|
|
|
337 /* If STMT transfers control out of its basic block, add
|
|
|
338 all outgoing edges to the work list. */
|
|
|
339 if (stmt_ends_bb_p (stmt))
|
|
|
340 {
|
|
|
341 edge e;
|
|
|
342 edge_iterator ei;
|
|
|
343 basic_block bb = gimple_bb (stmt);
|
|
|
344 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
345 add_control_edge (e);
|
|
|
346 }
|
|
|
347 }
|
|
|
348 else if (val == SSA_PROP_INTERESTING)
|
|
|
349 {
|
|
|
350 /* If the statement produced new value, add the SSA edges coming
|
|
|
351 out of OUTPUT_NAME. */
|
|
|
352 if (output_name)
|
|
|
353 add_ssa_edge (output_name, false);
|
|
|
354
|
|
|
355 /* If we know which edge is going to be taken out of this block,
|
|
|
356 add it to the CFG work list. */
|
|
|
357 if (taken_edge)
|
|
|
358 add_control_edge (taken_edge);
|
|
|
359 }
|
|
|
360 }
|
|
|
361
|
|
|
362 /* Process an SSA edge worklist. WORKLIST is the SSA edge worklist to
|
|
|
363 drain. This pops statements off the given WORKLIST and processes
|
|
|
364 them until there are no more statements on WORKLIST.
|
|
|
365 We take a pointer to WORKLIST because it may be reallocated when an
|
|
|
366 SSA edge is added to it in simulate_stmt. */
|
|
|
367
|
|
|
368 static void
|
|
|
369 process_ssa_edge_worklist (VEC(gimple,gc) **worklist)
|
|
|
370 {
|
|
|
371 /* Drain the entire worklist. */
|
|
|
372 while (VEC_length (gimple, *worklist) > 0)
|
|
|
373 {
|
|
|
374 basic_block bb;
|
|
|
375
|
|
|
376 /* Pull the statement to simulate off the worklist. */
|
|
|
377 gimple stmt = VEC_pop (gimple, *worklist);
|
|
|
378
|
|
|
379 /* If this statement was already visited by simulate_block, then
|
|
|
380 we don't need to visit it again here. */
|
|
|
381 if (!gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
|
|
|
382 continue;
|
|
|
383
|
|
|
384 /* STMT is no longer in a worklist. */
|
|
|
385 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
|
|
|
386
|
|
|
387 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
388 {
|
|
|
389 fprintf (dump_file, "\nSimulating statement (from ssa_edges): ");
|
|
|
390 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
|
|
|
391 }
|
|
|
392
|
|
|
393 bb = gimple_bb (stmt);
|
|
|
394
|
|
|
395 /* PHI nodes are always visited, regardless of whether or not
|
|
|
396 the destination block is executable. Otherwise, visit the
|
|
|
397 statement only if its block is marked executable. */
|
|
|
398 if (gimple_code (stmt) == GIMPLE_PHI
|
|
|
399 || TEST_BIT (executable_blocks, bb->index))
|
|
|
400 simulate_stmt (stmt);
|
|
|
401 }
|
|
|
402 }
|
|
|
403
|
|
|
404
|
|
|
405 /* Simulate the execution of BLOCK. Evaluate the statement associated
|
|
|
406 with each variable reference inside the block. */
|
|
|
407
|
|
|
408 static void
|
|
|
409 simulate_block (basic_block block)
|
|
|
410 {
|
|
|
411 gimple_stmt_iterator gsi;
|
|
|
412
|
|
|
413 /* There is nothing to do for the exit block. */
|
|
|
414 if (block == EXIT_BLOCK_PTR)
|
|
|
415 return;
|
|
|
416
|
|
|
417 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
418 fprintf (dump_file, "\nSimulating block %d\n", block->index);
|
|
|
419
|
|
|
420 /* Always simulate PHI nodes, even if we have simulated this block
|
|
|
421 before. */
|
|
|
422 for (gsi = gsi_start_phis (block); !gsi_end_p (gsi); gsi_next (&gsi))
|
|
|
423 simulate_stmt (gsi_stmt (gsi));
|
|
|
424
|
|
|
425 /* If this is the first time we've simulated this block, then we
|
|
|
426 must simulate each of its statements. */
|
|
|
427 if (!TEST_BIT (executable_blocks, block->index))
|
|
|
428 {
|
|
|
429 gimple_stmt_iterator j;
|
|
|
430 unsigned int normal_edge_count;
|
|
|
431 edge e, normal_edge;
|
|
|
432 edge_iterator ei;
|
|
|
433
|
|
|
434 /* Note that we have simulated this block. */
|
|
|
435 SET_BIT (executable_blocks, block->index);
|
|
|
436
|
|
|
437 for (j = gsi_start_bb (block); !gsi_end_p (j); gsi_next (&j))
|
|
|
438 {
|
|
|
439 gimple stmt = gsi_stmt (j);
|
|
|
440
|
|
|
441 /* If this statement is already in the worklist then
|
|
|
442 "cancel" it. The reevaluation implied by the worklist
|
|
|
443 entry will produce the same value we generate here and
|
|
|
444 thus reevaluating it again from the worklist is
|
|
|
445 pointless. */
|
|
|
446 if (gimple_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST))
|
|
|
447 gimple_set_plf (stmt, STMT_IN_SSA_EDGE_WORKLIST, false);
|
|
|
448
|
|
|
449 simulate_stmt (stmt);
|
|
|
450 }
|
|
|
451
|
|
|
452 /* We can not predict when abnormal edges will be executed, so
|
|
|
453 once a block is considered executable, we consider any
|
|
|
454 outgoing abnormal edges as executable.
|
|
|
455
|
|
|
456 At the same time, if this block has only one successor that is
|
|
|
457 reached by non-abnormal edges, then add that successor to the
|
|
|
458 worklist. */
|
|
|
459 normal_edge_count = 0;
|
|
|
460 normal_edge = NULL;
|
|
|
461 FOR_EACH_EDGE (e, ei, block->succs)
|
|
|
462 {
|
|
|
463 if (e->flags & EDGE_ABNORMAL)
|
|
|
464 add_control_edge (e);
|
|
|
465 else
|
|
|
466 {
|
|
|
467 normal_edge_count++;
|
|
|
468 normal_edge = e;
|
|
|
469 }
|
|
|
470 }
|
|
|
471
|
|
|
472 if (normal_edge_count == 1)
|
|
|
473 add_control_edge (normal_edge);
|
|
|
474 }
|
|
|
475 }
|
|
|
476
|
|
|
477
|
|
|
478 /* Initialize local data structures and work lists. */
|
|
|
479
|
|
|
480 static void
|
|
|
481 ssa_prop_init (void)
|
|
|
482 {
|
|
|
483 edge e;
|
|
|
484 edge_iterator ei;
|
|
|
485 basic_block bb;
|
|
|
486 size_t i;
|
|
|
487
|
|
|
488 /* Worklists of SSA edges. */
|
|
|
489 interesting_ssa_edges = VEC_alloc (gimple, gc, 20);
|
|
|
490 varying_ssa_edges = VEC_alloc (gimple, gc, 20);
|
|
|
491
|
|
|
492 executable_blocks = sbitmap_alloc (last_basic_block);
|
|
|
493 sbitmap_zero (executable_blocks);
|
|
|
494
|
|
|
495 bb_in_list = sbitmap_alloc (last_basic_block);
|
|
|
496 sbitmap_zero (bb_in_list);
|
|
|
497
|
|
|
498 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
499 dump_immediate_uses (dump_file);
|
|
|
500
|
|
|
501 cfg_blocks = VEC_alloc (basic_block, heap, 20);
|
|
|
502 VEC_safe_grow (basic_block, heap, cfg_blocks, 20);
|
|
|
503
|
|
|
504 /* Initialize the values for every SSA_NAME. */
|
|
|
505 for (i = 1; i < num_ssa_names; i++)
|
|
|
506 if (ssa_name (i))
|
|
|
507 SSA_NAME_VALUE (ssa_name (i)) = NULL_TREE;
|
|
|
508
|
|
|
509 /* Initially assume that every edge in the CFG is not executable.
|
|
|
510 (including the edges coming out of ENTRY_BLOCK_PTR). */
|
|
|
511 FOR_ALL_BB (bb)
|
|
|
512 {
|
|
|
513 gimple_stmt_iterator si;
|
|
|
514
|
|
|
515 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
516 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
|
|
|
517
|
|
|
518 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
|
|
|
519 gimple_set_plf (gsi_stmt (si), STMT_IN_SSA_EDGE_WORKLIST, false);
|
|
|
520
|
|
|
521 FOR_EACH_EDGE (e, ei, bb->succs)
|
|
|
522 e->flags &= ~EDGE_EXECUTABLE;
|
|
|
523 }
|
|
|
524
|
|
|
525 /* Seed the algorithm by adding the successors of the entry block to the
|
|
|
526 edge worklist. */
|
|
|
527 FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
|
|
|
528 add_control_edge (e);
|
|
|
529 }
|
|
|
530
|
|
|
531
|
|
|
532 /* Free allocated storage. */
|
|
|
533
|
|
|
534 static void
|
|
|
535 ssa_prop_fini (void)
|
|
|
536 {
|
|
|
537 VEC_free (gimple, gc, interesting_ssa_edges);
|
|
|
538 VEC_free (gimple, gc, varying_ssa_edges);
|
|
|
539 VEC_free (basic_block, heap, cfg_blocks);
|
|
|
540 cfg_blocks = NULL;
|
|
|
541 sbitmap_free (bb_in_list);
|
|
|
542 sbitmap_free (executable_blocks);
|
|
|
543 }
|
|
|
544
|
|
|
545
|
|
|
546 /* Return true if EXPR is an acceptable right-hand-side for a
|
|
|
547 GIMPLE assignment. We validate the entire tree, not just
|
|
|
548 the root node, thus catching expressions that embed complex
|
|
|
549 operands that are not permitted in GIMPLE. This function
|
|
|
550 is needed because the folding routines in fold-const.c
|
|
|
551 may return such expressions in some cases, e.g., an array
|
|
|
552 access with an embedded index addition. It may make more
|
|
|
553 sense to have folding routines that are sensitive to the
|
|
|
554 constraints on GIMPLE operands, rather than abandoning any
|
|
|
555 any attempt to fold if the usual folding turns out to be too
|
|
|
556 aggressive. */
|
|
|
557
|
|
|
558 bool
|
|
|
559 valid_gimple_rhs_p (tree expr)
|
|
|
560 {
|
|
|
561 enum tree_code code = TREE_CODE (expr);
|
|
|
562
|
|
|
563 switch (TREE_CODE_CLASS (code))
|
|
|
564 {
|
|
|
565 case tcc_declaration:
|
|
|
566 if (!is_gimple_variable (expr))
|
|
|
567 return false;
|
|
|
568 break;
|
|
|
569
|
|
|
570 case tcc_constant:
|
|
|
571 /* All constants are ok. */
|
|
|
572 break;
|
|
|
573
|
|
|
574 case tcc_binary:
|
|
|
575 case tcc_comparison:
|
|
|
576 if (!is_gimple_val (TREE_OPERAND (expr, 0))
|
|
|
577 || !is_gimple_val (TREE_OPERAND (expr, 1)))
|
|
|
578 return false;
|
|
|
579 break;
|
|
|
580
|
|
|
581 case tcc_unary:
|
|
|
582 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
|
|
|
583 return false;
|
|
|
584 break;
|
|
|
585
|
|
|
586 case tcc_expression:
|
|
|
587 switch (code)
|
|
|
588 {
|
|
|
589 case ADDR_EXPR:
|
|
|
590 {
|
|
|
591 tree t;
|
|
|
592 if (is_gimple_min_invariant (expr))
|
|
|
593 return true;
|
|
|
594 t = TREE_OPERAND (expr, 0);
|
|
|
595 while (handled_component_p (t))
|
|
|
596 {
|
|
|
597 /* ??? More checks needed, see the GIMPLE verifier. */
|
|
|
598 if ((TREE_CODE (t) == ARRAY_REF
|
|
|
599 || TREE_CODE (t) == ARRAY_RANGE_REF)
|
|
|
600 && !is_gimple_val (TREE_OPERAND (t, 1)))
|
|
|
601 return false;
|
|
|
602 t = TREE_OPERAND (t, 0);
|
|
|
603 }
|
|
|
604 if (!is_gimple_id (t))
|
|
|
605 return false;
|
|
|
606 }
|
|
|
607 break;
|
|
|
608
|
|
|
609 case TRUTH_NOT_EXPR:
|
|
|
610 if (!is_gimple_val (TREE_OPERAND (expr, 0)))
|
|
|
611 return false;
|
|
|
612 break;
|
|
|
613
|
|
|
614 case TRUTH_AND_EXPR:
|
|
|
615 case TRUTH_XOR_EXPR:
|
|
|
616 case TRUTH_OR_EXPR:
|
|
|
617 if (!is_gimple_val (TREE_OPERAND (expr, 0))
|
|
|
618 || !is_gimple_val (TREE_OPERAND (expr, 1)))
|
|
|
619 return false;
|
|
|
620 break;
|
|
|
621
|
|
|
622 case EXC_PTR_EXPR:
|
|
|
623 case FILTER_EXPR:
|
|
|
624 break;
|
|
|
625
|
|
|
626 default:
|
|
|
627 return false;
|
|
|
628 }
|
|
|
629 break;
|
|
|
630
|
|
|
631 case tcc_vl_exp:
|
|
|
632 return false;
|
|
|
633
|
|
|
634 case tcc_exceptional:
|
|
|
635 if (code != SSA_NAME)
|
|
|
636 return false;
|
|
|
637 break;
|
|
|
638
|
|
|
639 default:
|
|
|
640 return false;
|
|
|
641 }
|
|
|
642
|
|
|
643 return true;
|
|
|
644 }
|
|
|
645
|
|
|
646
|
|
|
647 /* Return true if EXPR is a CALL_EXPR suitable for representation
|
|
|
648 as a single GIMPLE_CALL statement. If the arguments require
|
|
|
649 further gimplification, return false. */
|
|
|
650
|
|
|
651 bool
|
|
|
652 valid_gimple_call_p (tree expr)
|
|
|
653 {
|
|
|
654 unsigned i, nargs;
|
|
|
655
|
|
|
656 if (TREE_CODE (expr) != CALL_EXPR)
|
|
|
657 return false;
|
|
|
658
|
|
|
659 nargs = call_expr_nargs (expr);
|
|
|
660 for (i = 0; i < nargs; i++)
|
|
|
661 if (! is_gimple_operand (CALL_EXPR_ARG (expr, i)))
|
|
|
662 return false;
|
|
|
663
|
|
|
664 return true;
|
|
|
665 }
|
|
|
666
|
|
|
667
|
|
|
668 /* Make SSA names defined by OLD_STMT point to NEW_STMT
|
|
|
669 as their defining statement. */
|
|
|
670
|
|
|
671 void
|
|
|
672 move_ssa_defining_stmt_for_defs (gimple new_stmt, gimple old_stmt)
|
|
|
673 {
|
|
|
674 tree var;
|
|
|
675 ssa_op_iter iter;
|
|
|
676
|
|
|
677 if (gimple_in_ssa_p (cfun))
|
|
|
678 {
|
|
|
679 /* Make defined SSA_NAMEs point to the new
|
|
|
680 statement as their definition. */
|
|
|
681 FOR_EACH_SSA_TREE_OPERAND (var, old_stmt, iter, SSA_OP_ALL_DEFS)
|
|
|
682 {
|
|
|
683 if (TREE_CODE (var) == SSA_NAME)
|
|
|
684 SSA_NAME_DEF_STMT (var) = new_stmt;
|
|
|
685 }
|
|
|
686 }
|
|
|
687 }
|
|
|
688
|
|
|
689
|
|
|
690 /* Update a GIMPLE_CALL statement at iterator *SI_P to reflect the
|
|
|
691 value of EXPR, which is expected to be the result of folding the
|
|
|
692 call. This can only be done if EXPR is a CALL_EXPR with valid
|
|
|
693 GIMPLE operands as arguments, or if it is a suitable RHS expression
|
|
|
694 for a GIMPLE_ASSIGN. More complex expressions will require
|
|
|
695 gimplification, which will introduce addtional statements. In this
|
|
|
696 event, no update is performed, and the function returns false.
|
|
|
697 Note that we cannot mutate a GIMPLE_CALL in-place, so we always
|
|
|
698 replace the statement at *SI_P with an entirely new statement.
|
|
|
699 The new statement need not be a call, e.g., if the original call
|
|
|
700 folded to a constant. */
|
|
|
701
|
|
|
702 bool
|
|
|
703 update_call_from_tree (gimple_stmt_iterator *si_p, tree expr)
|
|
|
704 {
|
|
|
705 tree lhs;
|
|
|
706
|
|
|
707 gimple stmt = gsi_stmt (*si_p);
|
|
|
708
|
|
|
709 gcc_assert (is_gimple_call (stmt));
|
|
|
710
|
|
|
711 lhs = gimple_call_lhs (stmt);
|
|
|
712
|
|
|
713 if (valid_gimple_call_p (expr))
|
|
|
714 {
|
|
|
715 /* The call has simplified to another call. */
|
|
|
716 tree fn = CALL_EXPR_FN (expr);
|
|
|
717 unsigned i;
|
|
|
718 unsigned nargs = call_expr_nargs (expr);
|
|
|
719 VEC(tree, heap) *args = NULL;
|
|
|
720 gimple new_stmt;
|
|
|
721
|
|
|
722 if (nargs > 0)
|
|
|
723 {
|
|
|
724 args = VEC_alloc (tree, heap, nargs);
|
|
|
725 VEC_safe_grow (tree, heap, args, nargs);
|
|
|
726
|
|
|
727 for (i = 0; i < nargs; i++)
|
|
|
728 VEC_replace (tree, args, i, CALL_EXPR_ARG (expr, i));
|
|
|
729 }
|
|
|
730
|
|
|
731 new_stmt = gimple_build_call_vec (fn, args);
|
|
|
732 gimple_call_set_lhs (new_stmt, lhs);
|
|
|
733 copy_virtual_operands (new_stmt, stmt);
|
|
|
734 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
|
|
|
735 gimple_set_location (new_stmt, gimple_location (stmt));
|
|
|
736 gsi_replace (si_p, new_stmt, false);
|
|
|
737 VEC_free (tree, heap, args);
|
|
|
738
|
|
|
739 return true;
|
|
|
740 }
|
|
|
741 else if (valid_gimple_rhs_p (expr))
|
|
|
742 {
|
|
|
743 gimple new_stmt;
|
|
|
744
|
|
|
745 /* The call has simplified to an expression
|
|
|
746 that cannot be represented as a GIMPLE_CALL. */
|
|
|
747 if (lhs)
|
|
|
748 {
|
|
|
749 /* A value is expected.
|
|
|
750 Introduce a new GIMPLE_ASSIGN statement. */
|
|
|
751 STRIP_USELESS_TYPE_CONVERSION (expr);
|
|
|
752 new_stmt = gimple_build_assign (lhs, expr);
|
|
|
753 copy_virtual_operands (new_stmt, stmt);
|
|
|
754 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
|
|
|
755 }
|
|
|
756 else if (!TREE_SIDE_EFFECTS (expr))
|
|
|
757 {
|
|
|
758 /* No value is expected, and EXPR has no effect.
|
|
|
759 Replace it with an empty statement. */
|
|
|
760 new_stmt = gimple_build_nop ();
|
|
|
761 }
|
|
|
762 else
|
|
|
763 {
|
|
|
764 /* No value is expected, but EXPR has an effect,
|
|
|
765 e.g., it could be a reference to a volatile
|
|
|
766 variable. Create an assignment statement
|
|
|
767 with a dummy (unused) lhs variable. */
|
|
|
768 STRIP_USELESS_TYPE_CONVERSION (expr);
|
|
|
769 lhs = create_tmp_var (TREE_TYPE (expr), NULL);
|
|
|
770 new_stmt = gimple_build_assign (lhs, expr);
|
|
|
771 add_referenced_var (lhs);
|
|
|
772 lhs = make_ssa_name (lhs, new_stmt);
|
|
|
773 gimple_assign_set_lhs (new_stmt, lhs);
|
|
|
774 copy_virtual_operands (new_stmt, stmt);
|
|
|
775 move_ssa_defining_stmt_for_defs (new_stmt, stmt);
|
|
|
776 }
|
|
|
777 gimple_set_location (new_stmt, gimple_location (stmt));
|
|
|
778 gsi_replace (si_p, new_stmt, false);
|
|
|
779 return true;
|
|
|
780 }
|
|
|
781 else
|
|
|
782 /* The call simplified to an expression that is
|
|
|
783 not a valid GIMPLE RHS. */
|
|
|
784 return false;
|
|
|
785 }
|
|
|
786
|
|
|
787
|
|
|
788 /* Entry point to the propagation engine.
|
|
|
789
|
|
|
790 VISIT_STMT is called for every statement visited.
|
|
|
791 VISIT_PHI is called for every PHI node visited. */
|
|
|
792
|
|
|
793 void
|
|
|
794 ssa_propagate (ssa_prop_visit_stmt_fn visit_stmt,
|
|
|
795 ssa_prop_visit_phi_fn visit_phi)
|
|
|
796 {
|
|
|
797 ssa_prop_visit_stmt = visit_stmt;
|
|
|
798 ssa_prop_visit_phi = visit_phi;
|
|
|
799
|
|
|
800 ssa_prop_init ();
|
|
|
801
|
|
|
802 /* Iterate until the worklists are empty. */
|
|
|
803 while (!cfg_blocks_empty_p ()
|
|
|
804 || VEC_length (gimple, interesting_ssa_edges) > 0
|
|
|
805 || VEC_length (gimple, varying_ssa_edges) > 0)
|
|
|
806 {
|
|
|
807 if (!cfg_blocks_empty_p ())
|
|
|
808 {
|
|
|
809 /* Pull the next block to simulate off the worklist. */
|
|
|
810 basic_block dest_block = cfg_blocks_get ();
|
|
|
811 simulate_block (dest_block);
|
|
|
812 }
|
|
|
813
|
|
|
814 /* In order to move things to varying as quickly as
|
|
|
815 possible,process the VARYING_SSA_EDGES worklist first. */
|
|
|
816 process_ssa_edge_worklist (&varying_ssa_edges);
|
|
|
817
|
|
|
818 /* Now process the INTERESTING_SSA_EDGES worklist. */
|
|
|
819 process_ssa_edge_worklist (&interesting_ssa_edges);
|
|
|
820 }
|
|
|
821
|
|
|
822 ssa_prop_fini ();
|
|
|
823 }
|
|
|
824
|
|
|
825
|
|
|
826 /* Return true if STMT is of the form 'LHS = mem_ref', where 'mem_ref'
|
|
|
827 is a non-volatile pointer dereference, a structure reference or a
|
|
|
828 reference to a single _DECL. Ignore volatile memory references
|
|
|
829 because they are not interesting for the optimizers. */
|
|
|
830
|
|
|
831 bool
|
|
|
832 stmt_makes_single_load (gimple stmt)
|
|
|
833 {
|
|
|
834 tree rhs;
|
|
|
835
|
|
|
836 if (gimple_code (stmt) != GIMPLE_ASSIGN)
|
|
|
837 return false;
|
|
|
838
|
|
|
839 /* Only a GIMPLE_SINGLE_RHS assignment may have a
|
|
|
840 declaration or reference as its RHS. */
|
|
|
841 if (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
|
|
|
842 != GIMPLE_SINGLE_RHS)
|
|
|
843 return false;
|
|
|
844
|
|
|
845 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF|SSA_OP_VUSE))
|
|
|
846 return false;
|
|
|
847
|
|
|
848 rhs = gimple_assign_rhs1 (stmt);
|
|
|
849
|
|
|
850 return (!TREE_THIS_VOLATILE (rhs)
|
|
|
851 && (DECL_P (rhs)
|
|
|
852 || REFERENCE_CLASS_P (rhs)));
|
|
|
853 }
|
|
|
854
|
|
|
855
|
|
|
856 /* Return true if STMT is of the form 'mem_ref = RHS', where 'mem_ref'
|
|
|
857 is a non-volatile pointer dereference, a structure reference or a
|
|
|
858 reference to a single _DECL. Ignore volatile memory references
|
|
|
859 because they are not interesting for the optimizers. */
|
|
|
860
|
|
|
861 bool
|
|
|
862 stmt_makes_single_store (gimple stmt)
|
|
|
863 {
|
|
|
864 tree lhs;
|
|
|
865
|
|
|
866 if (gimple_code (stmt) != GIMPLE_ASSIGN
|
|
|
867 && gimple_code (stmt) != GIMPLE_CALL)
|
|
|
868 return false;
|
|
|
869
|
|
|
870 if (ZERO_SSA_OPERANDS (stmt, SSA_OP_VDEF))
|
|
|
871 return false;
|
|
|
872
|
|
|
873 lhs = gimple_get_lhs (stmt);
|
|
|
874
|
|
|
875 /* A call statement may have a null LHS. */
|
|
|
876 if (!lhs)
|
|
|
877 return false;
|
|
|
878
|
|
|
879 return (!TREE_THIS_VOLATILE (lhs)
|
|
|
880 && (DECL_P (lhs)
|
|
|
881 || REFERENCE_CLASS_P (lhs)));
|
|
|
882 }
|
|
|
883
|
|
|
884
|
|
|
885 /* Propagation statistics. */
|
|
|
886 struct prop_stats_d
|
|
|
887 {
|
|
|
888 long num_const_prop;
|
|
|
889 long num_copy_prop;
|
|
|
890 long num_pred_folded;
|
|
|
891 long num_dce;
|
|
|
892 };
|
|
|
893
|
|
|
894 static struct prop_stats_d prop_stats;
|
|
|
895
|
|
|
896 /* Replace USE references in statement STMT with the values stored in
|
|
|
897 PROP_VALUE. Return true if at least one reference was replaced. */
|
|
|
898
|
|
|
899 static bool
|
|
|
900 replace_uses_in (gimple stmt, prop_value_t *prop_value)
|
|
|
901 {
|
|
|
902 bool replaced = false;
|
|
|
903 use_operand_p use;
|
|
|
904 ssa_op_iter iter;
|
|
|
905
|
|
|
906 FOR_EACH_SSA_USE_OPERAND (use, stmt, iter, SSA_OP_USE)
|
|
|
907 {
|
|
|
908 tree tuse = USE_FROM_PTR (use);
|
|
|
909 tree val = prop_value[SSA_NAME_VERSION (tuse)].value;
|
|
|
910
|
|
|
911 if (val == tuse || val == NULL_TREE)
|
|
|
912 continue;
|
|
|
913
|
|
|
914 if (gimple_code (stmt) == GIMPLE_ASM
|
|
|
915 && !may_propagate_copy_into_asm (tuse))
|
|
|
916 continue;
|
|
|
917
|
|
|
918 if (!may_propagate_copy (tuse, val))
|
|
|
919 continue;
|
|
|
920
|
|
|
921 if (TREE_CODE (val) != SSA_NAME)
|
|
|
922 prop_stats.num_const_prop++;
|
|
|
923 else
|
|
|
924 prop_stats.num_copy_prop++;
|
|
|
925
|
|
|
926 propagate_value (use, val);
|
|
|
927
|
|
|
928 replaced = true;
|
|
|
929 }
|
|
|
930
|
|
|
931 return replaced;
|
|
|
932 }
|
|
|
933
|
|
|
934
|
|
|
935 /* Replace propagated values into all the arguments for PHI using the
|
|
|
936 values from PROP_VALUE. */
|
|
|
937
|
|
|
938 static void
|
|
|
939 replace_phi_args_in (gimple phi, prop_value_t *prop_value)
|
|
|
940 {
|
|
|
941 size_t i;
|
|
|
942 bool replaced = false;
|
|
|
943
|
|
|
944 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
945 {
|
|
|
946 fprintf (dump_file, "Folding PHI node: ");
|
|
|
947 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
|
|
948 }
|
|
|
949
|
|
|
950 for (i = 0; i < gimple_phi_num_args (phi); i++)
|
|
|
951 {
|
|
|
952 tree arg = gimple_phi_arg_def (phi, i);
|
|
|
953
|
|
|
954 if (TREE_CODE (arg) == SSA_NAME)
|
|
|
955 {
|
|
|
956 tree val = prop_value[SSA_NAME_VERSION (arg)].value;
|
|
|
957
|
|
|
958 if (val && val != arg && may_propagate_copy (arg, val))
|
|
|
959 {
|
|
|
960 if (TREE_CODE (val) != SSA_NAME)
|
|
|
961 prop_stats.num_const_prop++;
|
|
|
962 else
|
|
|
963 prop_stats.num_copy_prop++;
|
|
|
964
|
|
|
965 propagate_value (PHI_ARG_DEF_PTR (phi, i), val);
|
|
|
966 replaced = true;
|
|
|
967
|
|
|
968 /* If we propagated a copy and this argument flows
|
|
|
969 through an abnormal edge, update the replacement
|
|
|
970 accordingly. */
|
|
|
971 if (TREE_CODE (val) == SSA_NAME
|
|
|
972 && gimple_phi_arg_edge (phi, i)->flags & EDGE_ABNORMAL)
|
|
|
973 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (val) = 1;
|
|
|
974 }
|
|
|
975 }
|
|
|
976 }
|
|
|
977
|
|
|
978 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
979 {
|
|
|
980 if (!replaced)
|
|
|
981 fprintf (dump_file, "No folding possible\n");
|
|
|
982 else
|
|
|
983 {
|
|
|
984 fprintf (dump_file, "Folded into: ");
|
|
|
985 print_gimple_stmt (dump_file, phi, 0, TDF_SLIM);
|
|
|
986 fprintf (dump_file, "\n");
|
|
|
987 }
|
|
|
988 }
|
|
|
989 }
|
|
|
990
|
|
|
991
|
|
|
992 /* If the statement pointed by SI has a predicate whose value can be
|
|
|
993 computed using the value range information computed by VRP, compute
|
|
|
994 its value and return true. Otherwise, return false. */
|
|
|
995
|
|
|
996 static bool
|
|
|
997 fold_predicate_in (gimple_stmt_iterator *si)
|
|
|
998 {
|
|
|
999 bool assignment_p = false;
|
|
|
1000 tree val;
|
|
|
1001 gimple stmt = gsi_stmt (*si);
|
|
|
1002
|
|
|
1003 if (is_gimple_assign (stmt)
|
|
|
1004 && TREE_CODE_CLASS (gimple_assign_rhs_code (stmt)) == tcc_comparison)
|
|
|
1005 {
|
|
|
1006 assignment_p = true;
|
|
|
1007 val = vrp_evaluate_conditional (gimple_assign_rhs_code (stmt),
|
|
|
1008 gimple_assign_rhs1 (stmt),
|
|
|
1009 gimple_assign_rhs2 (stmt),
|
|
|
1010 stmt);
|
|
|
1011 }
|
|
|
1012 else if (gimple_code (stmt) == GIMPLE_COND)
|
|
|
1013 val = vrp_evaluate_conditional (gimple_cond_code (stmt),
|
|
|
1014 gimple_cond_lhs (stmt),
|
|
|
1015 gimple_cond_rhs (stmt),
|
|
|
1016 stmt);
|
|
|
1017 else
|
|
|
1018 return false;
|
|
|
1019
|
|
|
1020
|
|
|
1021 if (val)
|
|
|
1022 {
|
|
|
1023 if (assignment_p)
|
|
|
1024 val = fold_convert (gimple_expr_type (stmt), val);
|
|
|
1025
|
|
|
1026 if (dump_file)
|
|
|
1027 {
|
|
|
1028 fprintf (dump_file, "Folding predicate ");
|
|
|
1029 print_gimple_expr (dump_file, stmt, 0, 0);
|
|
|
1030 fprintf (dump_file, " to ");
|
|
|
1031 print_generic_expr (dump_file, val, 0);
|
|
|
1032 fprintf (dump_file, "\n");
|
|
|
1033 }
|
|
|
1034
|
|
|
1035 prop_stats.num_pred_folded++;
|
|
|
1036
|
|
|
1037 if (is_gimple_assign (stmt))
|
|
|
1038 gimple_assign_set_rhs_from_tree (si, val);
|
|
|
1039 else
|
|
|
1040 {
|
|
|
1041 gcc_assert (gimple_code (stmt) == GIMPLE_COND);
|
|
|
1042 if (integer_zerop (val))
|
|
|
1043 gimple_cond_make_false (stmt);
|
|
|
1044 else if (integer_onep (val))
|
|
|
1045 gimple_cond_make_true (stmt);
|
|
|
1046 else
|
|
|
1047 gcc_unreachable ();
|
|
|
1048 }
|
|
|
1049
|
|
|
1050 return true;
|
|
|
1051 }
|
|
|
1052
|
|
|
1053 return false;
|
|
|
1054 }
|
|
|
1055
|
|
|
1056
|
|
|
1057 /* Perform final substitution and folding of propagated values.
|
|
|
1058
|
|
|
1059 PROP_VALUE[I] contains the single value that should be substituted
|
|
|
1060 at every use of SSA name N_I. If PROP_VALUE is NULL, no values are
|
|
|
1061 substituted.
|
|
|
1062
|
|
|
1063 If USE_RANGES_P is true, statements that contain predicate
|
|
|
1064 expressions are evaluated with a call to vrp_evaluate_conditional.
|
|
|
1065 This will only give meaningful results when called from tree-vrp.c
|
|
|
1066 (the information used by vrp_evaluate_conditional is built by the
|
|
|
1067 VRP pass).
|
|
|
1068
|
|
|
1069 Return TRUE when something changed. */
|
|
|
1070
|
|
|
1071 bool
|
|
|
1072 substitute_and_fold (prop_value_t *prop_value, bool use_ranges_p)
|
|
|
1073 {
|
|
|
1074 basic_block bb;
|
|
|
1075 bool something_changed = false;
|
|
|
1076
|
|
|
1077 if (prop_value == NULL && !use_ranges_p)
|
|
|
1078 return false;
|
|
|
1079
|
|
|
1080 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1081 fprintf (dump_file, "\nSubstituting values and folding statements\n\n");
|
|
|
1082
|
|
|
1083 memset (&prop_stats, 0, sizeof (prop_stats));
|
|
|
1084
|
|
|
1085 /* Substitute values in every statement of every basic block. */
|
|
|
1086 FOR_EACH_BB (bb)
|
|
|
1087 {
|
|
|
1088 gimple_stmt_iterator i;
|
|
|
1089
|
|
|
1090 /* Propagate known values into PHI nodes. */
|
|
|
1091 if (prop_value)
|
|
|
1092 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
|
|
|
1093 replace_phi_args_in (gsi_stmt (i), prop_value);
|
|
|
1094
|
|
|
1095 /* Propagate known values into stmts. Do a backward walk to expose
|
|
|
1096 more trivially deletable stmts. */
|
|
|
1097 for (i = gsi_last_bb (bb); !gsi_end_p (i);)
|
|
|
1098 {
|
|
|
1099 bool did_replace;
|
|
|
1100 gimple stmt = gsi_stmt (i);
|
|
|
1101 gimple old_stmt;
|
|
|
1102 enum gimple_code code = gimple_code (stmt);
|
|
|
1103
|
|
|
1104 /* Ignore ASSERT_EXPRs. They are used by VRP to generate
|
|
|
1105 range information for names and they are discarded
|
|
|
1106 afterwards. */
|
|
|
1107
|
|
|
1108 if (code == GIMPLE_ASSIGN
|
|
|
1109 && TREE_CODE (gimple_assign_rhs1 (stmt)) == ASSERT_EXPR)
|
|
|
1110 {
|
|
|
1111 gsi_prev (&i);
|
|
|
1112 continue;
|
|
|
1113 }
|
|
|
1114
|
|
|
1115 /* No point propagating into a stmt whose result is not used,
|
|
|
1116 but instead we might be able to remove a trivially dead stmt. */
|
|
|
1117 if (gimple_get_lhs (stmt)
|
|
|
1118 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME
|
|
|
1119 && has_zero_uses (gimple_get_lhs (stmt))
|
|
|
1120 && !stmt_could_throw_p (stmt)
|
|
|
1121 && !gimple_has_side_effects (stmt))
|
|
|
1122 {
|
|
|
1123 gimple_stmt_iterator i2;
|
|
|
1124
|
|
|
1125 if (dump_file && dump_flags & TDF_DETAILS)
|
|
|
1126 {
|
|
|
1127 fprintf (dump_file, "Removing dead stmt ");
|
|
|
1128 print_gimple_stmt (dump_file, stmt, 0, 0);
|
|
|
1129 fprintf (dump_file, "\n");
|
|
|
1130 }
|
|
|
1131 prop_stats.num_dce++;
|
|
|
1132 gsi_prev (&i);
|
|
|
1133 i2 = gsi_for_stmt (stmt);
|
|
|
1134 gsi_remove (&i2, true);
|
|
|
1135 release_defs (stmt);
|
|
|
1136 continue;
|
|
|
1137 }
|
|
|
1138
|
|
|
1139 /* Record the state of the statement before replacements. */
|
|
|
1140 push_stmt_changes (gsi_stmt_ptr (&i));
|
|
|
1141
|
|
|
1142 /* Replace the statement with its folded version and mark it
|
|
|
1143 folded. */
|
|
|
1144 did_replace = false;
|
|
|
1145 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1146 {
|
|
|
1147 fprintf (dump_file, "Folding statement: ");
|
|
|
1148 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
1149 }
|
|
|
1150
|
|
|
1151 /* If we have range information, see if we can fold
|
|
|
1152 predicate expressions. */
|
|
|
1153 if (use_ranges_p)
|
|
|
1154 {
|
|
|
1155 did_replace = fold_predicate_in (&i);
|
|
|
1156 /* fold_predicate_in should not have reallocated STMT. */
|
|
|
1157 gcc_assert (gsi_stmt (i) == stmt);
|
|
|
1158 }
|
|
|
1159
|
|
|
1160 /* Only replace real uses if we couldn't fold the
|
|
|
1161 statement using value range information. */
|
|
|
1162 if (prop_value
|
|
|
1163 && !did_replace)
|
|
|
1164 did_replace |= replace_uses_in (stmt, prop_value);
|
|
|
1165
|
|
|
1166 /* If we made a replacement, fold the statement. */
|
|
|
1167
|
|
|
1168 old_stmt = stmt;
|
|
|
1169 if (did_replace)
|
|
|
1170 fold_stmt (&i);
|
|
|
1171
|
|
|
1172 /* Some statements may be simplified using ranges. For
|
|
|
1173 example, division may be replaced by shifts, modulo
|
|
|
1174 replaced with bitwise and, etc. Do this after
|
|
|
1175 substituting constants, folding, etc so that we're
|
|
|
1176 presented with a fully propagated, canonicalized
|
|
|
1177 statement. */
|
|
|
1178 if (use_ranges_p)
|
|
|
1179 did_replace |= simplify_stmt_using_ranges (&i);
|
|
|
1180
|
|
|
1181 /* Now cleanup. */
|
|
|
1182 if (did_replace)
|
|
|
1183 {
|
|
|
1184 stmt = gsi_stmt (i);
|
|
|
1185
|
|
|
1186 /* If we cleaned up EH information from the statement,
|
|
|
1187 remove EH edges. */
|
|
|
1188 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt))
|
|
|
1189 gimple_purge_dead_eh_edges (bb);
|
|
|
1190
|
|
|
1191 if (is_gimple_assign (stmt)
|
|
|
1192 && (get_gimple_rhs_class (gimple_assign_rhs_code (stmt))
|
|
|
1193 == GIMPLE_SINGLE_RHS))
|
|
|
1194 {
|
|
|
1195 tree rhs = gimple_assign_rhs1 (stmt);
|
|
|
1196
|
|
|
1197 if (TREE_CODE (rhs) == ADDR_EXPR)
|
|
|
1198 recompute_tree_invariant_for_addr_expr (rhs);
|
|
|
1199 }
|
|
|
1200
|
|
|
1201 /* Determine what needs to be done to update the SSA form. */
|
|
|
1202 pop_stmt_changes (gsi_stmt_ptr (&i));
|
|
|
1203 something_changed = true;
|
|
|
1204 }
|
|
|
1205 else
|
|
|
1206 {
|
|
|
1207 /* The statement was not modified, discard the change buffer. */
|
|
|
1208 discard_stmt_changes (gsi_stmt_ptr (&i));
|
|
|
1209 }
|
|
|
1210
|
|
|
1211 if (dump_file && (dump_flags & TDF_DETAILS))
|
|
|
1212 {
|
|
|
1213 if (did_replace)
|
|
|
1214 {
|
|
|
1215 fprintf (dump_file, "Folded into: ");
|
|
|
1216 print_gimple_stmt (dump_file, stmt, 0, TDF_SLIM);
|
|
|
1217 fprintf (dump_file, "\n");
|
|
|
1218 }
|
|
|
1219 else
|
|
|
1220 fprintf (dump_file, "Not folded\n");
|
|
|
1221 }
|
|
|
1222
|
|
|
1223 gsi_prev (&i);
|
|
|
1224 }
|
|
|
1225 }
|
|
|
1226
|
|
|
1227 statistics_counter_event (cfun, "Constants propagated",
|
|
|
1228 prop_stats.num_const_prop);
|
|
|
1229 statistics_counter_event (cfun, "Copies propagated",
|
|
|
1230 prop_stats.num_copy_prop);
|
|
|
1231 statistics_counter_event (cfun, "Predicates folded",
|
|
|
1232 prop_stats.num_pred_folded);
|
|
|
1233 statistics_counter_event (cfun, "Statements deleted",
|
|
|
1234 prop_stats.num_dce);
|
|
|
1235 return something_changed;
|
|
|
1236 }
|
|
|
1237
|
|
|
1238 #include "gt-tree-ssa-propagate.h"
|
