Branch data Line data Source code
1 : : /* Standard problems for dataflow support routines.
2 : : Copyright (C) 1999-2025 Free Software Foundation, Inc.
3 : : Originally contributed by Michael P. Hayes
4 : : (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 : : Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 : : and Kenneth Zadeck (zadeck@naturalbridge.com).
7 : :
8 : : This file is part of GCC.
9 : :
10 : : GCC is free software; you can redistribute it and/or modify it under
11 : : the terms of the GNU General Public License as published by the Free
12 : : Software Foundation; either version 3, or (at your option) any later
13 : : version.
14 : :
15 : : GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 : : WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 : : FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 : : for more details.
19 : :
20 : : You should have received a copy of the GNU General Public License
21 : : along with GCC; see the file COPYING3. If not see
22 : : <http://www.gnu.org/licenses/>. */
23 : :
24 : : #include "config.h"
25 : : #include "system.h"
26 : : #include "coretypes.h"
27 : : #include "backend.h"
28 : : #include "target.h"
29 : : #include "rtl.h"
30 : : #include "df.h"
31 : : #include "memmodel.h"
32 : : #include "tm_p.h"
33 : : #include "insn-config.h"
34 : : #include "cfganal.h"
35 : : #include "dce.h"
36 : : #include "valtrack.h"
37 : : #include "dumpfile.h"
38 : : #include "rtl-iter.h"
39 : : #include "regs.h"
40 : : #include "function-abi.h"
41 : :
42 : : /* Note that turning REG_DEAD_DEBUGGING on will cause
43 : : gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
44 : : addresses in the dumps. */
45 : : #define REG_DEAD_DEBUGGING 0
46 : :
47 : : #define DF_SPARSE_THRESHOLD 32
48 : :
49 : : static bitmap_head seen_in_block;
50 : : static bitmap_head seen_in_insn;
51 : :
52 : : /*----------------------------------------------------------------------------
53 : : Utility functions.
54 : : ----------------------------------------------------------------------------*/
55 : :
56 : : /* Generic versions to get the void* version of the block info. Only
57 : : used inside the problem instance vectors. */
58 : :
59 : : /* Dump a def-use or use-def chain for REF to FILE. */
60 : :
61 : : void
62 : 28702 : df_chain_dump (struct df_link *link, FILE *file)
63 : : {
64 : 28702 : fprintf (file, "{ ");
65 : 60389 : for (; link; link = link->next)
66 : : {
67 : 4366 : fprintf (file, "%c%d(bb %d insn %d) ",
68 : 2985 : DF_REF_REG_DEF_P (link->ref)
69 : 0 : ? 'd'
70 : 0 : : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
71 : : DF_REF_ID (link->ref),
72 : 2985 : DF_REF_BBNO (link->ref),
73 : 2985 : DF_REF_IS_ARTIFICIAL (link->ref)
74 : 1381 : ? -1 : DF_REF_INSN_UID (link->ref));
75 : : }
76 : 28702 : fprintf (file, "}");
77 : 28702 : }
78 : :
79 : :
80 : : /* Print some basic block info as part of df_dump. */
81 : :
82 : : void
83 : 4354 : df_print_bb_index (basic_block bb, FILE *file)
84 : : {
85 : 4354 : edge e;
86 : 4354 : edge_iterator ei;
87 : :
88 : 4354 : fprintf (file, "\n( ");
89 : 9824 : FOR_EACH_EDGE (e, ei, bb->preds)
90 : : {
91 : 5470 : basic_block pred = e->src;
92 : 10940 : fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
93 : : }
94 : 4354 : fprintf (file, ")->[%d]->( ", bb->index);
95 : 9824 : FOR_EACH_EDGE (e, ei, bb->succs)
96 : : {
97 : 5470 : basic_block succ = e->dest;
98 : 10940 : fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
99 : : }
100 : 4354 : fprintf (file, ")\n");
101 : 4354 : }
102 : :
103 : :
104 : : /*----------------------------------------------------------------------------
105 : : REACHING DEFINITIONS
106 : :
107 : : Find the locations in the function where each definition site for a
108 : : pseudo reaches. In and out bitvectors are built for each basic
109 : : block. The id field in the ref is used to index into these sets.
110 : : See df.h for details.
111 : :
112 : : If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
113 : : existing uses are included in the global reaching DEFs set, or in other
114 : : words only DEFs that are still live. This is a kind of pruned version
115 : : of the traditional reaching definitions problem that is much less
116 : : complex to compute and produces enough information to compute UD-chains.
117 : : In this context, live must be interpreted in the DF_LR sense: Uses that
118 : : are upward exposed but maybe not initialized on all paths through the
119 : : CFG. For a USE that is not reached by a DEF on all paths, we still want
120 : : to make those DEFs that do reach the USE visible, and pruning based on
121 : : DF_LIVE would make that impossible.
122 : : ----------------------------------------------------------------------------*/
123 : :
124 : : /* This problem plays a large number of games for the sake of
125 : : efficiency.
126 : :
127 : : 1) The order of the bits in the bitvectors. After the scanning
128 : : phase, all of the defs are sorted. All of the defs for the reg 0
129 : : are first, followed by all defs for reg 1 and so on.
130 : :
131 : : 2) There are two kill sets, one if the number of defs is less or
132 : : equal to DF_SPARSE_THRESHOLD and another if the number of defs is
133 : : greater.
134 : :
135 : : <= : Data is built directly in the kill set.
136 : :
137 : : > : One level of indirection is used to keep from generating long
138 : : strings of 1 bits in the kill sets. Bitvectors that are indexed
139 : : by the regnum are used to represent that there is a killing def
140 : : for the register. The confluence and transfer functions use
141 : : these along with the bitmap_clear_range call to remove ranges of
142 : : bits without actually generating a knockout vector.
143 : :
144 : : The kill and sparse_kill and the dense_invalidated_by_eh and
145 : : sparse_invalidated_by_eh both play this game. */
146 : :
147 : : /* Private data used to compute the solution for this problem. These
148 : : data structures are not accessible outside of this module. */
149 : : class df_rd_problem_data
150 : : {
151 : : public:
152 : : /* The set of defs to regs invalidated by EH edges. */
153 : : bitmap_head sparse_invalidated_by_eh;
154 : : bitmap_head dense_invalidated_by_eh;
155 : : /* An obstack for the bitmaps we need for this problem. */
156 : : bitmap_obstack rd_bitmaps;
157 : : };
158 : :
159 : :
160 : : /* Free basic block info. */
161 : :
162 : : static void
163 : 3271620 : df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
164 : : void *vbb_info)
165 : : {
166 : 3271620 : class df_rd_bb_info *bb_info = (class df_rd_bb_info *) vbb_info;
167 : 3271620 : if (bb_info)
168 : : {
169 : 3271620 : bitmap_clear (&bb_info->kill);
170 : 3271620 : bitmap_clear (&bb_info->sparse_kill);
171 : 3271620 : bitmap_clear (&bb_info->gen);
172 : 3271620 : bitmap_clear (&bb_info->in);
173 : 3271620 : bitmap_clear (&bb_info->out);
174 : : }
175 : 3271620 : }
176 : :
177 : :
178 : : /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
179 : : not touched unless the block is new. */
180 : :
181 : : static void
182 : 5763650 : df_rd_alloc (bitmap all_blocks)
183 : : {
184 : 5763650 : unsigned int bb_index;
185 : 5763650 : bitmap_iterator bi;
186 : 5763650 : class df_rd_problem_data *problem_data;
187 : :
188 : 5763650 : if (df_rd->problem_data)
189 : : {
190 : 838535 : problem_data = (class df_rd_problem_data *) df_rd->problem_data;
191 : 838535 : bitmap_clear (&problem_data->sparse_invalidated_by_eh);
192 : 838535 : bitmap_clear (&problem_data->dense_invalidated_by_eh);
193 : : }
194 : : else
195 : : {
196 : 4925115 : problem_data = XNEW (class df_rd_problem_data);
197 : 4925115 : df_rd->problem_data = problem_data;
198 : :
199 : 4925115 : bitmap_obstack_initialize (&problem_data->rd_bitmaps);
200 : 4925115 : bitmap_initialize (&problem_data->sparse_invalidated_by_eh,
201 : : &problem_data->rd_bitmaps);
202 : 4925115 : bitmap_initialize (&problem_data->dense_invalidated_by_eh,
203 : : &problem_data->rd_bitmaps);
204 : : }
205 : :
206 : 5763650 : df_grow_bb_info (df_rd);
207 : :
208 : : /* Because of the clustering of all use sites for the same pseudo,
209 : : we have to process all of the blocks before doing the analysis. */
210 : :
211 : 68877110 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
212 : : {
213 : 63113460 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
214 : :
215 : : /* When bitmaps are already initialized, just clear them. */
216 : 63113460 : if (bb_info->kill.obstack)
217 : : {
218 : 1383085 : bitmap_clear (&bb_info->kill);
219 : 1383085 : bitmap_clear (&bb_info->sparse_kill);
220 : 1383085 : bitmap_clear (&bb_info->gen);
221 : : }
222 : : else
223 : : {
224 : 61730375 : bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
225 : 61730375 : bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
226 : 61730375 : bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
227 : 61730375 : bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
228 : 61730375 : bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
229 : : }
230 : : }
231 : 5763650 : df_rd->optional_p = true;
232 : 5763650 : }
233 : :
234 : :
235 : : /* Add the effect of the top artificial defs of BB to the reaching definitions
236 : : bitmap LOCAL_RD. */
237 : :
238 : : void
239 : 63113460 : df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
240 : : {
241 : 63113460 : int bb_index = bb->index;
242 : 63113460 : df_ref def;
243 : 206610014 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
244 : 80383094 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
245 : : {
246 : 1877137 : unsigned int dregno = DF_REF_REGNO (def);
247 : 1877137 : if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
248 : 1877137 : bitmap_clear_range (local_rd,
249 : 1877137 : DF_DEFS_BEGIN (dregno),
250 : 1877137 : DF_DEFS_COUNT (dregno));
251 : 1877137 : bitmap_set_bit (local_rd, DF_REF_ID (def));
252 : : }
253 : 63113460 : }
254 : :
255 : : /* Add the effect of the defs of INSN to the reaching definitions bitmap
256 : : LOCAL_RD. */
257 : :
258 : : void
259 : 525384377 : df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
260 : : bitmap local_rd)
261 : : {
262 : 525384377 : df_ref def;
263 : :
264 : 2555660777 : FOR_EACH_INSN_DEF (def, insn)
265 : : {
266 : 2030276400 : unsigned int dregno = DF_REF_REGNO (def);
267 : 2030276400 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
268 : 14862770 : || (dregno >= FIRST_PSEUDO_REGISTER))
269 : : {
270 : 2017159294 : if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
271 : 2016451073 : bitmap_clear_range (local_rd,
272 : 2016451073 : DF_DEFS_BEGIN (dregno),
273 : 2016451073 : DF_DEFS_COUNT (dregno));
274 : 2017159294 : if (!(DF_REF_FLAGS (def)
275 : : & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
276 : 212514131 : bitmap_set_bit (local_rd, DF_REF_ID (def));
277 : : }
278 : : }
279 : 525384377 : }
280 : :
281 : : /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
282 : : more complicated than just simulating, because we must produce the
283 : : gen and kill sets and hence deal with the two possible representations
284 : : of kill sets. */
285 : :
286 : : static void
287 : 650506055 : df_rd_bb_local_compute_process_def (class df_rd_bb_info *bb_info,
288 : : df_ref def,
289 : : int top_flag)
290 : : {
291 : 2840723061 : for (; def; def = DF_REF_NEXT_LOC (def))
292 : : {
293 : 2190217006 : if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
294 : : {
295 : 2110246703 : unsigned int regno = DF_REF_REGNO (def);
296 : 2110246703 : unsigned int begin = DF_DEFS_BEGIN (regno);
297 : 2110246703 : unsigned int n_defs = DF_DEFS_COUNT (regno);
298 : :
299 : 2110246703 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
300 : 14862770 : || (regno >= FIRST_PSEUDO_REGISTER))
301 : : {
302 : : /* Only the last def(s) for a regno in the block has any
303 : : effect. */
304 : 2097129597 : if (!bitmap_bit_p (&seen_in_block, regno))
305 : : {
306 : : /* The first def for regno in insn gets to knock out the
307 : : defs from other instructions. */
308 : 1519418217 : if ((!bitmap_bit_p (&seen_in_insn, regno))
309 : : /* If the def is to only part of the reg, it does
310 : : not kill the other defs that reach here. */
311 : 1519418217 : && (!(DF_REF_FLAGS (def) &
312 : : (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
313 : : {
314 : 223364512 : if (n_defs > DF_SPARSE_THRESHOLD)
315 : : {
316 : 38203025 : bitmap_set_bit (&bb_info->sparse_kill, regno);
317 : 38203025 : bitmap_clear_range (&bb_info->gen, begin, n_defs);
318 : : }
319 : : else
320 : : {
321 : 185161487 : bitmap_set_range (&bb_info->kill, begin, n_defs);
322 : 185161487 : bitmap_clear_range (&bb_info->gen, begin, n_defs);
323 : : }
324 : : }
325 : :
326 : 1519418217 : bitmap_set_bit (&seen_in_insn, regno);
327 : : /* All defs for regno in the instruction may be put into
328 : : the gen set. */
329 : 1519418217 : if (!(DF_REF_FLAGS (def)
330 : : & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
331 : 216908054 : bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
332 : : }
333 : : }
334 : : }
335 : : }
336 : 650506055 : }
337 : :
338 : : /* Compute local reaching def info for basic block BB. */
339 : :
340 : : static void
341 : 63113460 : df_rd_bb_local_compute (unsigned int bb_index)
342 : : {
343 : 63113460 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
344 : 63113460 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
345 : 63113460 : rtx_insn *insn;
346 : :
347 : 63113460 : bitmap_clear (&seen_in_block);
348 : 63113460 : bitmap_clear (&seen_in_insn);
349 : :
350 : : /* Artificials are only hard regs. */
351 : 63113460 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
352 : 125121678 : df_rd_bb_local_compute_process_def (bb_info,
353 : : df_get_artificial_defs (bb_index),
354 : : 0);
355 : :
356 : 689854145 : FOR_BB_INSNS_REVERSE (bb, insn)
357 : : {
358 : 626740685 : unsigned int uid = INSN_UID (insn);
359 : :
360 : 626740685 : if (!INSN_P (insn))
361 : 101356308 : continue;
362 : :
363 : 525384377 : df_rd_bb_local_compute_process_def (bb_info,
364 : 525384377 : DF_INSN_UID_DEFS (uid), 0);
365 : :
366 : : /* This complex dance with the two bitmaps is required because
367 : : instructions can assign twice to the same pseudo. This
368 : : generally happens with calls that will have one def for the
369 : : result and another def for the clobber. If only one vector
370 : : is used and the clobber goes first, the result will be
371 : : lost. */
372 : 525384377 : bitmap_ior_into (&seen_in_block, &seen_in_insn);
373 : 525384377 : bitmap_clear (&seen_in_insn);
374 : : }
375 : :
376 : : /* Process the artificial defs at the top of the block last since we
377 : : are going backwards through the block and these are logically at
378 : : the start. */
379 : 63113460 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
380 : 125121678 : df_rd_bb_local_compute_process_def (bb_info,
381 : : df_get_artificial_defs (bb_index),
382 : : DF_REF_AT_TOP);
383 : 63113460 : }
384 : :
385 : :
386 : : /* Compute local reaching def info for each basic block within BLOCKS. */
387 : :
388 : : static void
389 : 5763650 : df_rd_local_compute (bitmap all_blocks)
390 : : {
391 : 5763650 : unsigned int bb_index;
392 : 5763650 : bitmap_iterator bi;
393 : 5763650 : class df_rd_problem_data *problem_data
394 : 5763650 : = (class df_rd_problem_data *) df_rd->problem_data;
395 : 5763650 : bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
396 : 5763650 : bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
397 : :
398 : 5763650 : bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
399 : 5763650 : bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
400 : :
401 : 5763650 : df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
402 : :
403 : 68877110 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
404 : : {
405 : 63113460 : df_rd_bb_local_compute (bb_index);
406 : : }
407 : :
408 : : /* Set up the knockout bit vectors to be applied across EH_EDGES.
409 : : Conservatively treat partially-clobbered registers as surviving
410 : : across the EH edge, i.e. assume that definitions before the edge
411 : : is taken *might* reach uses after it has been taken. */
412 : 5763650 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
413 : 533996514 : for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
414 : 528254616 : if (eh_edge_abi.clobbers_full_reg_p (regno))
415 : : {
416 : 476511577 : if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
417 : 9820644 : bitmap_set_bit (sparse_invalidated, regno);
418 : : else
419 : 466690933 : bitmap_set_range (dense_invalidated,
420 : 466690933 : DF_DEFS_BEGIN (regno),
421 : : DF_DEFS_COUNT (regno));
422 : : }
423 : :
424 : 5763650 : bitmap_release (&seen_in_block);
425 : 5763650 : bitmap_release (&seen_in_insn);
426 : 5763650 : }
427 : :
428 : :
429 : : /* Initialize the solution bit vectors for problem. */
430 : :
431 : : static void
432 : 5763650 : df_rd_init_solution (bitmap all_blocks)
433 : : {
434 : 5763650 : unsigned int bb_index;
435 : 5763650 : bitmap_iterator bi;
436 : :
437 : 68877110 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
438 : : {
439 : 63113460 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
440 : :
441 : 63113460 : bitmap_copy (&bb_info->out, &bb_info->gen);
442 : 63113460 : bitmap_clear (&bb_info->in);
443 : : }
444 : 5763650 : }
445 : :
446 : : /* In of target gets or of out of source. */
447 : :
448 : : static bool
449 : 102316011 : df_rd_confluence_n (edge e)
450 : : {
451 : 102316011 : bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
452 : 102316011 : bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
453 : 102316011 : bool changed = false;
454 : :
455 : 102316011 : if (e->flags & EDGE_FAKE)
456 : : return false;
457 : :
458 : 102316011 : if (e->flags & EDGE_EH)
459 : : {
460 : 3413565 : class df_rd_problem_data *problem_data
461 : : = (class df_rd_problem_data *) df_rd->problem_data;
462 : 3413565 : bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
463 : 3413565 : bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
464 : 3413565 : bitmap_iterator bi;
465 : 3413565 : unsigned int regno;
466 : :
467 : 3413565 : auto_bitmap tmp (&df_bitmap_obstack);
468 : 3413565 : bitmap_and_compl (tmp, op2, dense_invalidated);
469 : :
470 : 191434081 : EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
471 : : {
472 : 188020516 : bitmap_clear_range (tmp,
473 : 188020516 : DF_DEFS_BEGIN (regno),
474 : 188020516 : DF_DEFS_COUNT (regno));
475 : : }
476 : 3413565 : changed |= bitmap_ior_into (op1, tmp);
477 : 3413565 : return changed;
478 : 3413565 : }
479 : : else
480 : 98902446 : return bitmap_ior_into (op1, op2);
481 : : }
482 : :
483 : :
484 : : /* Transfer function. */
485 : :
486 : : static bool
487 : 73808287 : df_rd_transfer_function (int bb_index)
488 : : {
489 : 73808287 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
490 : 73808287 : unsigned int regno;
491 : 73808287 : bitmap_iterator bi;
492 : 73808287 : bitmap in = &bb_info->in;
493 : 73808287 : bitmap out = &bb_info->out;
494 : 73808287 : bitmap gen = &bb_info->gen;
495 : 73808287 : bitmap kill = &bb_info->kill;
496 : 73808287 : bitmap sparse_kill = &bb_info->sparse_kill;
497 : 73808287 : bool changed = false;
498 : :
499 : 73808287 : if (bitmap_empty_p (sparse_kill))
500 : 44544965 : changed = bitmap_ior_and_compl (out, gen, in, kill);
501 : : else
502 : : {
503 : 29263322 : class df_rd_problem_data *problem_data;
504 : 29263322 : bitmap_head tmp;
505 : :
506 : : /* Note that TMP is _not_ a temporary bitmap if we end up replacing
507 : : OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
508 : 29263322 : problem_data = (class df_rd_problem_data *) df_rd->problem_data;
509 : 29263322 : bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
510 : :
511 : 29263322 : bitmap_and_compl (&tmp, in, kill);
512 : 74638633 : EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
513 : : {
514 : 45375311 : bitmap_clear_range (&tmp,
515 : 45375311 : DF_DEFS_BEGIN (regno),
516 : 45375311 : DF_DEFS_COUNT (regno));
517 : : }
518 : 29263322 : bitmap_ior_into (&tmp, gen);
519 : 29263322 : changed = !bitmap_equal_p (&tmp, out);
520 : 29263322 : if (changed)
521 : 28675781 : bitmap_move (out, &tmp);
522 : : else
523 : 587541 : bitmap_clear (&tmp);
524 : : }
525 : :
526 : 73808287 : if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
527 : : {
528 : : /* Create a mask of DEFs for all registers live at the end of this
529 : : basic block, and mask out DEFs of registers that are not live.
530 : : Computing the mask looks costly, but the benefit of the pruning
531 : : outweighs the cost. */
532 : 73807217 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
533 : 73807217 : bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
534 : 73807217 : bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
535 : 73807217 : unsigned int regno;
536 : 73807217 : bitmap_iterator bi;
537 : :
538 : 782272703 : EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
539 : 708465486 : bitmap_set_range (live_defs,
540 : 708465486 : DF_DEFS_BEGIN (regno),
541 : 708465486 : DF_DEFS_COUNT (regno));
542 : 73807217 : changed |= bitmap_and_into (&bb_info->out, live_defs);
543 : 73807217 : BITMAP_FREE (live_defs);
544 : : }
545 : :
546 : 73808287 : return changed;
547 : : }
548 : :
549 : : /* Free all storage associated with the problem. */
550 : :
551 : : static void
552 : 4925115 : df_rd_free (void)
553 : : {
554 : 4925115 : class df_rd_problem_data *problem_data
555 : 4925115 : = (class df_rd_problem_data *) df_rd->problem_data;
556 : :
557 : 4925115 : if (problem_data)
558 : : {
559 : 4925115 : bitmap_obstack_release (&problem_data->rd_bitmaps);
560 : :
561 : 4925115 : df_rd->block_info_size = 0;
562 : 4925115 : free (df_rd->block_info);
563 : 4925115 : df_rd->block_info = NULL;
564 : 4925115 : free (df_rd->problem_data);
565 : : }
566 : 4925115 : free (df_rd);
567 : 4925115 : }
568 : :
569 : :
570 : : /* Debugging info. */
571 : :
572 : : static void
573 : 217 : df_rd_start_dump (FILE *file)
574 : : {
575 : 217 : class df_rd_problem_data *problem_data
576 : 217 : = (class df_rd_problem_data *) df_rd->problem_data;
577 : 217 : unsigned int m = DF_REG_SIZE (df);
578 : 217 : unsigned int regno;
579 : :
580 : 217 : if (!df_rd->block_info)
581 : : return;
582 : :
583 : 217 : fprintf (file, ";; Reaching defs:\n");
584 : :
585 : 217 : fprintf (file, ";; sparse invalidated \t");
586 : 217 : dump_bitmap (file, &problem_data->sparse_invalidated_by_eh);
587 : 217 : fprintf (file, ";; dense invalidated \t");
588 : 217 : dump_bitmap (file, &problem_data->dense_invalidated_by_eh);
589 : :
590 : 217 : fprintf (file, ";; reg->defs[] map:\t");
591 : 27887 : for (regno = 0; regno < m; regno++)
592 : 27453 : if (DF_DEFS_COUNT (regno))
593 : 13983 : fprintf (file, "%d[%d,%d] ", regno,
594 : : DF_DEFS_BEGIN (regno),
595 : 13983 : DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
596 : 217 : fprintf (file, "\n");
597 : : }
598 : :
599 : :
600 : : static void
601 : 2552 : df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
602 : : {
603 : 2552 : bitmap_head tmp;
604 : 2552 : unsigned int regno;
605 : 2552 : unsigned int m = DF_REG_SIZE (df);
606 : 2552 : bool first_reg = true;
607 : :
608 : 2552 : fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
609 : :
610 : 2552 : bitmap_initialize (&tmp, &df_bitmap_obstack);
611 : 379380 : for (regno = 0; regno < m; regno++)
612 : : {
613 : 376828 : if (HARD_REGISTER_NUM_P (regno)
614 : 234784 : && (df->changeable_flags & DF_NO_HARD_REGS))
615 : 0 : continue;
616 : 376828 : bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
617 : 376828 : bitmap_and_into (&tmp, defs_set);
618 : 376828 : if (! bitmap_empty_p (&tmp))
619 : : {
620 : 8671 : bitmap_iterator bi;
621 : 8671 : unsigned int ix;
622 : 8671 : bool first_def = true;
623 : :
624 : 8671 : if (! first_reg)
625 : 6618 : fprintf (file, ",");
626 : 8671 : first_reg = false;
627 : :
628 : 8671 : fprintf (file, "%u[", regno);
629 : 19270 : EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
630 : : {
631 : 12527 : fprintf (file, "%s%u", first_def ? "" : ",", ix);
632 : 10599 : first_def = false;
633 : : }
634 : 8671 : fprintf (file, "]");
635 : : }
636 : 376828 : bitmap_clear (&tmp);
637 : : }
638 : :
639 : 2552 : fprintf (file, "\n");
640 : 2552 : bitmap_clear (&tmp);
641 : 2552 : }
642 : :
643 : : /* Debugging info at top of bb. */
644 : :
645 : : static void
646 : 638 : df_rd_top_dump (basic_block bb, FILE *file)
647 : : {
648 : 638 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
649 : 638 : if (!bb_info)
650 : : return;
651 : :
652 : 638 : df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
653 : 638 : df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
654 : 638 : df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
655 : : }
656 : :
657 : :
658 : : /* Debugging info at bottom of bb. */
659 : :
660 : : static void
661 : 638 : df_rd_bottom_dump (basic_block bb, FILE *file)
662 : : {
663 : 638 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
664 : 638 : if (!bb_info)
665 : : return;
666 : :
667 : 638 : df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
668 : : }
669 : :
670 : : /* All of the information associated with every instance of the problem. */
671 : :
672 : : static const struct df_problem problem_RD =
673 : : {
674 : : DF_RD, /* Problem id. */
675 : : DF_FORWARD, /* Direction. */
676 : : df_rd_alloc, /* Allocate the problem specific data. */
677 : : NULL, /* Reset global information. */
678 : : df_rd_free_bb_info, /* Free basic block info. */
679 : : df_rd_local_compute, /* Local compute function. */
680 : : df_rd_init_solution, /* Init the solution specific data. */
681 : : df_worklist_dataflow, /* Worklist solver. */
682 : : NULL, /* Confluence operator 0. */
683 : : df_rd_confluence_n, /* Confluence operator n. */
684 : : df_rd_transfer_function, /* Transfer function. */
685 : : NULL, /* Finalize function. */
686 : : df_rd_free, /* Free all of the problem information. */
687 : : df_rd_free, /* Remove this problem from the stack of dataflow problems. */
688 : : df_rd_start_dump, /* Debugging. */
689 : : df_rd_top_dump, /* Debugging start block. */
690 : : df_rd_bottom_dump, /* Debugging end block. */
691 : : NULL, /* Debugging start insn. */
692 : : NULL, /* Debugging end insn. */
693 : : NULL, /* Incremental solution verify start. */
694 : : NULL, /* Incremental solution verify end. */
695 : : NULL, /* Dependent problem. */
696 : : sizeof (class df_rd_bb_info),/* Size of entry of block_info array. */
697 : : TV_DF_RD, /* Timing variable. */
698 : : true /* Reset blocks on dropping out of blocks_to_analyze. */
699 : : };
700 : :
701 : :
702 : :
703 : : /* Create a new RD instance and add it to the existing instance
704 : : of DF. */
705 : :
706 : : void
707 : 104 : df_rd_add_problem (void)
708 : : {
709 : 104 : df_add_problem (&problem_RD);
710 : 104 : }
711 : :
712 : :
713 : :
714 : : /*----------------------------------------------------------------------------
715 : : LIVE REGISTERS
716 : :
717 : : Find the locations in the function where any use of a pseudo can
718 : : reach in the backwards direction. In and out bitvectors are built
719 : : for each basic block. The regno is used to index into these sets.
720 : : See df.h for details.
721 : : ----------------------------------------------------------------------------*/
722 : :
723 : : /* Private data used to verify the solution for this problem. */
724 : : struct df_lr_problem_data
725 : : {
726 : : bitmap_head *in;
727 : : bitmap_head *out;
728 : : /* An obstack for the bitmaps we need for this problem. */
729 : : bitmap_obstack lr_bitmaps;
730 : : };
731 : :
732 : : /* Free basic block info. */
733 : :
734 : : static void
735 : 6297625 : df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
736 : : void *vbb_info)
737 : : {
738 : 6297625 : class df_lr_bb_info *bb_info = (class df_lr_bb_info *) vbb_info;
739 : 6297625 : if (bb_info)
740 : : {
741 : 6297625 : bitmap_clear (&bb_info->use);
742 : 6297625 : bitmap_clear (&bb_info->def);
743 : 6297625 : bitmap_clear (&bb_info->in);
744 : 6297625 : bitmap_clear (&bb_info->out);
745 : : }
746 : 6297625 : }
747 : :
748 : :
749 : : /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
750 : : not touched unless the block is new. */
751 : :
752 : : static void
753 : 14858886 : df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
754 : : {
755 : 14858886 : unsigned int bb_index;
756 : 14858886 : bitmap_iterator bi;
757 : 14858886 : struct df_lr_problem_data *problem_data;
758 : :
759 : 14858886 : df_grow_bb_info (df_lr);
760 : 14858886 : if (df_lr->problem_data)
761 : : problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
762 : : else
763 : : {
764 : 1435842 : problem_data = XNEW (struct df_lr_problem_data);
765 : 1435842 : df_lr->problem_data = problem_data;
766 : :
767 : 1435842 : problem_data->out = NULL;
768 : 1435842 : problem_data->in = NULL;
769 : 1435842 : bitmap_obstack_initialize (&problem_data->lr_bitmaps);
770 : : }
771 : :
772 : 100150132 : EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
773 : : {
774 : 85291246 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
775 : :
776 : : /* When bitmaps are already initialized, just clear them. */
777 : 85291246 : if (bb_info->use.obstack)
778 : : {
779 : 63566204 : bitmap_clear (&bb_info->def);
780 : 63566204 : bitmap_clear (&bb_info->use);
781 : : }
782 : : else
783 : : {
784 : 21725042 : bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
785 : 21725042 : bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
786 : 21725042 : bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
787 : 21725042 : bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
788 : : }
789 : : }
790 : :
791 : 14858886 : df_lr->optional_p = false;
792 : 14858886 : }
793 : :
794 : :
795 : : /* Reset the global solution for recalculation. */
796 : :
797 : : static void
798 : 0 : df_lr_reset (bitmap all_blocks)
799 : : {
800 : 0 : unsigned int bb_index;
801 : 0 : bitmap_iterator bi;
802 : :
803 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
804 : : {
805 : 0 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
806 : 0 : gcc_assert (bb_info);
807 : 0 : bitmap_clear (&bb_info->in);
808 : 0 : bitmap_clear (&bb_info->out);
809 : : }
810 : 0 : }
811 : :
812 : :
813 : : /* Compute local live register info for basic block BB. */
814 : :
815 : : static void
816 : 81972496 : df_lr_bb_local_compute (unsigned int bb_index)
817 : : {
818 : 81972496 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
819 : 81972496 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
820 : 81972496 : rtx_insn *insn;
821 : 81972496 : df_ref def, use;
822 : :
823 : : /* Process the registers set in an exception handler. */
824 : 223110878 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
825 : 59165886 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
826 : : {
827 : 57204549 : unsigned int dregno = DF_REF_REGNO (def);
828 : 57204549 : bitmap_set_bit (&bb_info->def, dregno);
829 : 57204549 : bitmap_clear_bit (&bb_info->use, dregno);
830 : : }
831 : :
832 : : /* Process the hardware registers that are always live. */
833 : 397132110 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
834 : : /* Add use to set of uses in this BB. */
835 : 233187118 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
836 : 233187118 : bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
837 : :
838 : 1175208987 : FOR_BB_INSNS_REVERSE (bb, insn)
839 : : {
840 : 1093236491 : if (!NONDEBUG_INSN_P (insn))
841 : 511743194 : continue;
842 : :
843 : 581493297 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844 : 4340422417 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
845 : : {
846 : : /* If the definition is to only part of the register, it will
847 : : usually have a corresponding use. For example, stores to one
848 : : word of a multiword register R have both a use and a partial
849 : : definition of R.
850 : :
851 : : In those cases, the LR confluence function:
852 : :
853 : : IN = (OUT & ~DEF) | USE
854 : :
855 : : is unaffected by whether we count the partial definition or not.
856 : : However, it's more convenient for consumers if DEF contains
857 : : *all* the registers defined in a block.
858 : :
859 : : The only current case in which we record a partial definition
860 : : without a corresponding use is if the destination is the
861 : : multi-register subreg of a hard register. An artificial
862 : : example of this is:
863 : :
864 : : (set (subreg:TI (reg:V8HI x0) 0) (const_int -1))
865 : :
866 : : on AArch64. This is described as a DF_REF_PARTIAL
867 : : definition of x0 and x1 with no corresponding uses.
868 : : In previous versions of GCC, the instruction had no
869 : : effect on LR (that is, LR acted as though the instruction
870 : : didn't exist).
871 : :
872 : : It seems suspect that this case is treated differently.
873 : : Either the instruction should be a full definition of x0 and x1,
874 : : or the definition should be treated in the same way as other
875 : : partial definitions, such as strict_lowparts or subregs that
876 : : satisfy read_modify_subreg_p.
877 : :
878 : : Fortunately, multi-register subregs of hard registers should
879 : : be rare. They should be folded into a plain REG if the target
880 : : allows that (as AArch64 does for example above).
881 : :
882 : : Here we treat the cases alike by forcing a use even in the rare
883 : : case that no DF_REF_REG_USE is recorded. That is, we model all
884 : : partial definitions as both a use and a definition of the
885 : : register. */
886 : 3758929120 : unsigned int dregno = DF_REF_REGNO (def);
887 : 3758929120 : bitmap_set_bit (&bb_info->def, dregno);
888 : 3758929120 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
889 : 2250324 : bitmap_set_bit (&bb_info->use, dregno);
890 : : else
891 : 3756678796 : bitmap_clear_bit (&bb_info->use, dregno);
892 : : }
893 : :
894 : 1318108776 : FOR_EACH_INSN_INFO_USE (use, insn_info)
895 : : /* Add use to set of uses in this BB. */
896 : 736615479 : bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
897 : : }
898 : :
899 : : /* Process the registers set in an exception handler or the hard
900 : : frame pointer if this block is the target of a non local
901 : : goto. */
902 : 223110878 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
903 : 59165886 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
904 : : {
905 : 1961337 : unsigned int dregno = DF_REF_REGNO (def);
906 : 1961337 : bitmap_set_bit (&bb_info->def, dregno);
907 : 1961337 : bitmap_clear_bit (&bb_info->use, dregno);
908 : : }
909 : :
910 : : #ifdef EH_USES
911 : : /* Process the uses that are live into an exception handler. */
912 : : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
913 : : /* Add use to set of uses in this BB. */
914 : : if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
915 : : bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
916 : : #endif
917 : :
918 : : /* If the df_live problem is not defined, such as at -O0 and -O1, we
919 : : still need to keep the luids up to date. This is normally done
920 : : in the df_live problem since this problem has a forwards
921 : : scan. */
922 : 81972496 : if (!df_live)
923 : 12982019 : df_recompute_luids (bb);
924 : 81972496 : }
925 : :
926 : :
927 : : /* Compute local live register info for each basic block within BLOCKS. */
928 : :
929 : : static void
930 : 14858886 : df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
931 : : {
932 : 14858886 : unsigned int bb_index, i;
933 : 14858886 : bitmap_iterator bi;
934 : :
935 : 14858886 : bitmap_clear (&df->hardware_regs_used);
936 : :
937 : : /* The all-important stack pointer must always be live. */
938 : 14858886 : bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
939 : :
940 : : /* Global regs are always live, too. */
941 : 1396735284 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
942 : 1367017512 : if (global_regs[i])
943 : 1195 : bitmap_set_bit (&df->hardware_regs_used, i);
944 : :
945 : : /* Before reload, there are a few registers that must be forced
946 : : live everywhere -- which might not already be the case for
947 : : blocks within infinite loops. */
948 : 14858886 : if (!reload_completed)
949 : : {
950 : 9691150 : unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
951 : : /* Any reference to any pseudo before reload is a potential
952 : : reference of the frame pointer. */
953 : 9691150 : bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
954 : :
955 : : /* Pseudos with argument area equivalences may require
956 : : reloading via the argument pointer. */
957 : 9691150 : if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
958 : 9691150 : && fixed_regs[ARG_POINTER_REGNUM])
959 : 9691150 : bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
960 : :
961 : : /* Any constant, or pseudo with constant equivalences, may
962 : : require reloading from memory using the pic register. */
963 : 9691150 : if (pic_offset_table_regnum != INVALID_REGNUM
964 : 0 : && fixed_regs[pic_offset_table_regnum])
965 : 0 : bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
966 : : }
967 : :
968 : 100150132 : EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
969 : : {
970 : 85291246 : if (bb_index == EXIT_BLOCK)
971 : : {
972 : : /* The exit block is special for this problem and its bits are
973 : : computed from thin air. */
974 : 3318750 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
975 : 3318750 : bitmap_copy (&bb_info->use, df->exit_block_uses);
976 : : }
977 : : else
978 : 81972496 : df_lr_bb_local_compute (bb_index);
979 : : }
980 : :
981 : 14858886 : bitmap_clear (df_lr->out_of_date_transfer_functions);
982 : 14858886 : }
983 : :
984 : :
985 : : /* Initialize the solution vectors. */
986 : :
987 : : static void
988 : 14858886 : df_lr_init (bitmap all_blocks)
989 : : {
990 : 14858886 : unsigned int bb_index;
991 : 14858886 : bitmap_iterator bi;
992 : :
993 : 332491473 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
994 : : {
995 : 317632587 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
996 : 317632587 : bitmap_copy (&bb_info->in, &bb_info->use);
997 : 317632587 : bitmap_clear (&bb_info->out);
998 : : }
999 : 14858886 : }
1000 : :
1001 : :
1002 : : /* Confluence function that processes infinite loops. This might be a
1003 : : noreturn function that throws. And even if it isn't, getting the
1004 : : unwind info right helps debugging. */
1005 : : static void
1006 : 25292720 : df_lr_confluence_0 (basic_block bb)
1007 : : {
1008 : 25292720 : bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
1009 : 25292720 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1010 : 11646819 : bitmap_copy (op1, &df->hardware_regs_used);
1011 : 25292720 : }
1012 : :
1013 : :
1014 : : /* Confluence function that ignores fake edges. */
1015 : :
1016 : : static bool
1017 : 513196797 : df_lr_confluence_n (edge e)
1018 : : {
1019 : 513196797 : bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
1020 : 513196797 : bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
1021 : 513196797 : bool changed = false;
1022 : :
1023 : : /* Call-clobbered registers die across exception and call edges.
1024 : : Conservatively treat partially-clobbered registers as surviving
1025 : : across the edges; they might or might not, depending on what
1026 : : mode they have. */
1027 : : /* ??? Abnormal call edges ignored for the moment, as this gets
1028 : : confused by sibling call edges, which crashes reg-stack. */
1029 : 513196797 : if (e->flags & EDGE_EH)
1030 : : {
1031 : 22592063 : bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
1032 : 22592063 : changed = bitmap_ior_and_compl_into (op1, op2, eh_kills);
1033 : : }
1034 : : else
1035 : 490604734 : changed = bitmap_ior_into (op1, op2);
1036 : :
1037 : 513196797 : changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
1038 : 513196797 : return changed;
1039 : : }
1040 : :
1041 : :
1042 : : /* Transfer function. */
1043 : :
1044 : : static bool
1045 : 360588129 : df_lr_transfer_function (int bb_index)
1046 : : {
1047 : 360588129 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1048 : 360588129 : bitmap in = &bb_info->in;
1049 : 360588129 : bitmap out = &bb_info->out;
1050 : 360588129 : bitmap use = &bb_info->use;
1051 : 360588129 : bitmap def = &bb_info->def;
1052 : :
1053 : 360588129 : return bitmap_ior_and_compl (in, use, out, def);
1054 : : }
1055 : :
1056 : :
1057 : : static void
1058 : 14858886 : df_lr_finalize (bitmap)
1059 : : {
1060 : 14858886 : df_lr->solutions_dirty = false;
1061 : 14189777 : }
1062 : :
1063 : :
1064 : : /* Free all storage associated with the problem. */
1065 : :
1066 : : static void
1067 : 1435844 : df_lr_free (void)
1068 : : {
1069 : 1435844 : struct df_lr_problem_data *problem_data
1070 : 1435844 : = (struct df_lr_problem_data *) df_lr->problem_data;
1071 : 1435844 : if (df_lr->block_info)
1072 : : {
1073 : :
1074 : 1435842 : df_lr->block_info_size = 0;
1075 : 1435842 : free (df_lr->block_info);
1076 : 1435842 : df_lr->block_info = NULL;
1077 : 1435842 : bitmap_obstack_release (&problem_data->lr_bitmaps);
1078 : 1435842 : free (df_lr->problem_data);
1079 : 1435842 : df_lr->problem_data = NULL;
1080 : : }
1081 : :
1082 : 1435844 : BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1083 : 1435844 : free (df_lr);
1084 : 1435844 : }
1085 : :
1086 : :
1087 : : /* Debugging info at top of bb. */
1088 : :
1089 : : static void
1090 : 5545 : df_lr_top_dump (basic_block bb, FILE *file)
1091 : : {
1092 : 5545 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1093 : 5449 : struct df_lr_problem_data *problem_data;
1094 : 5449 : if (!bb_info)
1095 : : return;
1096 : :
1097 : 5449 : fprintf (file, ";; lr in \t");
1098 : 5449 : df_print_regset (file, &bb_info->in);
1099 : 5449 : if (df_lr->problem_data)
1100 : : {
1101 : 5449 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1102 : 5449 : if (problem_data->in)
1103 : : {
1104 : 0 : fprintf (file, ";; old in \t");
1105 : 0 : df_print_regset (file, &problem_data->in[bb->index]);
1106 : : }
1107 : : }
1108 : 5449 : fprintf (file, ";; lr use \t");
1109 : 5449 : df_print_regset (file, &bb_info->use);
1110 : 5449 : fprintf (file, ";; lr def \t");
1111 : 5449 : df_print_regset (file, &bb_info->def);
1112 : : }
1113 : :
1114 : :
1115 : : /* Debugging info at bottom of bb. */
1116 : :
1117 : : static void
1118 : 5545 : df_lr_bottom_dump (basic_block bb, FILE *file)
1119 : : {
1120 : 5545 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1121 : 5449 : struct df_lr_problem_data *problem_data;
1122 : 5449 : if (!bb_info)
1123 : : return;
1124 : :
1125 : 5449 : fprintf (file, ";; lr out \t");
1126 : 5449 : df_print_regset (file, &bb_info->out);
1127 : 5449 : if (df_lr->problem_data)
1128 : : {
1129 : 5449 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1130 : 5449 : if (problem_data->out)
1131 : : {
1132 : 0 : fprintf (file, ";; old out \t");
1133 : 0 : df_print_regset (file, &problem_data->out[bb->index]);
1134 : : }
1135 : : }
1136 : : }
1137 : :
1138 : :
1139 : : /* Build the datastructure to verify that the solution to the dataflow
1140 : : equations is not dirty. */
1141 : :
1142 : : static void
1143 : 0 : df_lr_verify_solution_start (void)
1144 : : {
1145 : 0 : basic_block bb;
1146 : 0 : struct df_lr_problem_data *problem_data;
1147 : 0 : if (df_lr->solutions_dirty)
1148 : : return;
1149 : :
1150 : : /* Set it true so that the solution is recomputed. */
1151 : 0 : df_lr->solutions_dirty = true;
1152 : :
1153 : 0 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1154 : 0 : problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1155 : 0 : problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1156 : :
1157 : 0 : FOR_ALL_BB_FN (bb, cfun)
1158 : : {
1159 : 0 : bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1160 : 0 : bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1161 : 0 : bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1162 : 0 : bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1163 : : }
1164 : : }
1165 : :
1166 : :
1167 : : /* Compare the saved datastructure and the new solution to the dataflow
1168 : : equations. */
1169 : :
1170 : : static void
1171 : 0 : df_lr_verify_solution_end (void)
1172 : : {
1173 : 0 : struct df_lr_problem_data *problem_data;
1174 : 0 : basic_block bb;
1175 : :
1176 : 0 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1177 : :
1178 : 0 : if (!problem_data->out)
1179 : : return;
1180 : :
1181 : 0 : if (df_lr->solutions_dirty)
1182 : : /* Do not check if the solution is still dirty. See the comment
1183 : : in df_lr_finalize for details. */
1184 : 0 : df_lr->solutions_dirty = false;
1185 : : else
1186 : 0 : FOR_ALL_BB_FN (bb, cfun)
1187 : : {
1188 : 0 : if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1189 : 0 : || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1190 : : {
1191 : : /*df_dump (stderr);*/
1192 : 0 : gcc_unreachable ();
1193 : : }
1194 : : }
1195 : :
1196 : : /* Cannot delete them immediately because you may want to dump them
1197 : : if the comparison fails. */
1198 : 0 : FOR_ALL_BB_FN (bb, cfun)
1199 : : {
1200 : 0 : bitmap_clear (&problem_data->in[bb->index]);
1201 : 0 : bitmap_clear (&problem_data->out[bb->index]);
1202 : : }
1203 : :
1204 : 0 : free (problem_data->in);
1205 : 0 : free (problem_data->out);
1206 : 0 : problem_data->in = NULL;
1207 : 0 : problem_data->out = NULL;
1208 : : }
1209 : :
1210 : :
1211 : : /* All of the information associated with every instance of the problem. */
1212 : :
1213 : : static const struct df_problem problem_LR =
1214 : : {
1215 : : DF_LR, /* Problem id. */
1216 : : DF_BACKWARD, /* Direction. */
1217 : : df_lr_alloc, /* Allocate the problem specific data. */
1218 : : df_lr_reset, /* Reset global information. */
1219 : : df_lr_free_bb_info, /* Free basic block info. */
1220 : : df_lr_local_compute, /* Local compute function. */
1221 : : df_lr_init, /* Init the solution specific data. */
1222 : : df_worklist_dataflow, /* Worklist solver. */
1223 : : df_lr_confluence_0, /* Confluence operator 0. */
1224 : : df_lr_confluence_n, /* Confluence operator n. */
1225 : : df_lr_transfer_function, /* Transfer function. */
1226 : : df_lr_finalize, /* Finalize function. */
1227 : : df_lr_free, /* Free all of the problem information. */
1228 : : NULL, /* Remove this problem from the stack of dataflow problems. */
1229 : : NULL, /* Debugging. */
1230 : : df_lr_top_dump, /* Debugging start block. */
1231 : : df_lr_bottom_dump, /* Debugging end block. */
1232 : : NULL, /* Debugging start insn. */
1233 : : NULL, /* Debugging end insn. */
1234 : : df_lr_verify_solution_start,/* Incremental solution verify start. */
1235 : : df_lr_verify_solution_end, /* Incremental solution verify end. */
1236 : : NULL, /* Dependent problem. */
1237 : : sizeof (class df_lr_bb_info),/* Size of entry of block_info array. */
1238 : : TV_DF_LR, /* Timing variable. */
1239 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
1240 : : };
1241 : :
1242 : : /* Run the fast DCE after building LR. This is a separate problem so that
1243 : : the "dirty" flag is only cleared after a DCE pass is actually run. */
1244 : :
1245 : : static void
1246 : 21725722 : df_lr_dce_finalize (bitmap all_blocks)
1247 : : {
1248 : 21725722 : if (!(df->changeable_flags & DF_LR_RUN_DCE))
1249 : : return;
1250 : :
1251 : : /* Also clears df_lr_dce->solutions_dirty. */
1252 : 8332462 : run_fast_df_dce ();
1253 : :
1254 : : /* If dce deletes some instructions, we need to recompute the lr
1255 : : solution before proceeding further. The problem is that fast
1256 : : dce is a pessimestic dataflow algorithm. In the case where
1257 : : it deletes a statement S inside of a loop, the uses inside of
1258 : : S may not be deleted from the dataflow solution because they
1259 : : were carried around the loop. While it is conservatively
1260 : : correct to leave these extra bits, the standards of df
1261 : : require that we maintain the best possible (least fixed
1262 : : point) solution. The only way to do that is to redo the
1263 : : iteration from the beginning. See PR35805 for an
1264 : : example. */
1265 : 8332462 : if (df_lr->solutions_dirty)
1266 : : {
1267 : 669109 : df_clear_flags (DF_LR_RUN_DCE);
1268 : 669109 : df_lr_alloc (all_blocks);
1269 : 669109 : df_lr_local_compute (all_blocks);
1270 : 669109 : df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1271 : 669109 : df_lr_finalize (all_blocks);
1272 : 669109 : df_set_flags (DF_LR_RUN_DCE);
1273 : : }
1274 : : }
1275 : :
1276 : : static const struct df_problem problem_LR_DCE
1277 : : {
1278 : : DF_LR_DCE, /* Problem id. */
1279 : : DF_BACKWARD, /* Direction (arbitrary). */
1280 : : NULL, /* Allocate the problem specific data. */
1281 : : NULL, /* Reset global information. */
1282 : : NULL, /* Free basic block info. */
1283 : : NULL, /* Local compute function. */
1284 : : NULL, /* Init the solution specific data. */
1285 : : NULL, /* Worklist solver. */
1286 : : NULL, /* Confluence operator 0. */
1287 : : NULL, /* Confluence operator n. */
1288 : : NULL, /* Transfer function. */
1289 : : df_lr_dce_finalize, /* Finalize function. */
1290 : : NULL, /* Free all of the problem information. */
1291 : : NULL, /* Remove this problem from the stack of dataflow problems. */
1292 : : NULL, /* Debugging. */
1293 : : NULL, /* Debugging start block. */
1294 : : NULL, /* Debugging end block. */
1295 : : NULL, /* Debugging start insn. */
1296 : : NULL, /* Debugging end insn. */
1297 : : NULL, /* Incremental solution verify start. */
1298 : : NULL, /* Incremental solution verify end. */
1299 : : &problem_LR, /* Dependent problem. */
1300 : : 0, /* Size of entry of block_info array. */
1301 : : TV_DF_LR, /* Timing variable. */
1302 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
1303 : : };
1304 : :
1305 : :
1306 : : /* Create a new DATAFLOW instance and add it to an existing instance
1307 : : of DF. The returned structure is what is used to get at the
1308 : : solution. */
1309 : :
1310 : : void
1311 : 1435844 : df_lr_add_problem (void)
1312 : : {
1313 : : /* Also add the fast DCE problem. It is then conditionally enabled by
1314 : : the DF_LR_RUN_DCE flag. */
1315 : 1435844 : df_add_problem (&problem_LR_DCE);
1316 : : /* These will be initialized when df_scan_blocks processes each
1317 : : block. */
1318 : 1435844 : df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1319 : 1435844 : }
1320 : :
1321 : :
1322 : : /* Verify that all of the lr related info is consistent and
1323 : : correct. */
1324 : :
1325 : : void
1326 : 0 : df_lr_verify_transfer_functions (void)
1327 : : {
1328 : 0 : basic_block bb;
1329 : 0 : bitmap_head saved_def;
1330 : 0 : bitmap_head saved_use;
1331 : 0 : bitmap_head all_blocks;
1332 : :
1333 : 0 : if (!df)
1334 : 0 : return;
1335 : :
1336 : 0 : bitmap_initialize (&saved_def, &bitmap_default_obstack);
1337 : 0 : bitmap_initialize (&saved_use, &bitmap_default_obstack);
1338 : 0 : bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1339 : :
1340 : 0 : FOR_ALL_BB_FN (bb, cfun)
1341 : : {
1342 : 0 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1343 : 0 : bitmap_set_bit (&all_blocks, bb->index);
1344 : :
1345 : 0 : if (bb_info)
1346 : : {
1347 : : /* Make a copy of the transfer functions and then compute
1348 : : new ones to see if the transfer functions have
1349 : : changed. */
1350 : 0 : if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1351 : : bb->index))
1352 : : {
1353 : 0 : bitmap_copy (&saved_def, &bb_info->def);
1354 : 0 : bitmap_copy (&saved_use, &bb_info->use);
1355 : 0 : bitmap_clear (&bb_info->def);
1356 : 0 : bitmap_clear (&bb_info->use);
1357 : :
1358 : 0 : df_lr_bb_local_compute (bb->index);
1359 : 0 : gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1360 : 0 : gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1361 : : }
1362 : : }
1363 : : else
1364 : : {
1365 : : /* If we do not have basic block info, the block must be in
1366 : : the list of dirty blocks or else some one has added a
1367 : : block behind our backs. */
1368 : 0 : gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1369 : : bb->index));
1370 : : }
1371 : : /* Make sure no one created a block without following
1372 : : procedures. */
1373 : 0 : gcc_assert (df_scan_get_bb_info (bb->index));
1374 : : }
1375 : :
1376 : : /* Make sure there are no dirty bits in blocks that have been deleted. */
1377 : 0 : gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1378 : : &all_blocks));
1379 : :
1380 : 0 : bitmap_clear (&saved_def);
1381 : 0 : bitmap_clear (&saved_use);
1382 : 0 : bitmap_clear (&all_blocks);
1383 : : }
1384 : :
1385 : :
1386 : :
1387 : : /*----------------------------------------------------------------------------
1388 : : LIVE AND MAY-INITIALIZED REGISTERS.
1389 : :
1390 : : This problem first computes the IN and OUT bitvectors for the
1391 : : may-initialized registers problems, which is a forward problem.
1392 : : It gives the set of registers for which we MAY have an available
1393 : : definition, i.e. for which there is an available definition on
1394 : : at least one path from the entry block to the entry/exit of a
1395 : : basic block. Sets generate a definition, while clobbers kill
1396 : : a definition.
1397 : :
1398 : : In and out bitvectors are built for each basic block and are indexed by
1399 : : regnum (see df.h for details). In and out bitvectors in struct
1400 : : df_live_bb_info actually refers to the may-initialized problem;
1401 : :
1402 : : Then, the in and out sets for the LIVE problem itself are computed.
1403 : : These are the logical AND of the IN and OUT sets from the LR problem
1404 : : and the may-initialized problem.
1405 : : ----------------------------------------------------------------------------*/
1406 : :
1407 : : /* Private data used to verify the solution for this problem. */
1408 : : struct df_live_problem_data
1409 : : {
1410 : : bitmap_head *in;
1411 : : bitmap_head *out;
1412 : : /* An obstack for the bitmaps we need for this problem. */
1413 : : bitmap_obstack live_bitmaps;
1414 : : };
1415 : :
1416 : : /* Scratch var used by transfer functions. This is used to implement
1417 : : an optimization to reduce the amount of space used to compute the
1418 : : combined lr and live analysis. */
1419 : : static bitmap_head df_live_scratch;
1420 : :
1421 : :
1422 : : /* Free basic block info. */
1423 : :
1424 : : static void
1425 : 5900736 : df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1426 : : void *vbb_info)
1427 : : {
1428 : 5900736 : class df_live_bb_info *bb_info = (class df_live_bb_info *) vbb_info;
1429 : 5900736 : if (bb_info)
1430 : : {
1431 : 5900736 : bitmap_clear (&bb_info->gen);
1432 : 5900736 : bitmap_clear (&bb_info->kill);
1433 : 5900736 : bitmap_clear (&bb_info->in);
1434 : 5900736 : bitmap_clear (&bb_info->out);
1435 : : }
1436 : 5900736 : }
1437 : :
1438 : :
1439 : : /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1440 : : not touched unless the block is new. */
1441 : :
1442 : : static void
1443 : 12656278 : df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1444 : : {
1445 : 12656278 : unsigned int bb_index;
1446 : 12656278 : bitmap_iterator bi;
1447 : 12656278 : struct df_live_problem_data *problem_data;
1448 : :
1449 : 12656278 : if (df_live->problem_data)
1450 : : problem_data = (struct df_live_problem_data *) df_live->problem_data;
1451 : : else
1452 : : {
1453 : 2173344 : problem_data = XNEW (struct df_live_problem_data);
1454 : 2173344 : df_live->problem_data = problem_data;
1455 : :
1456 : 2173344 : problem_data->out = NULL;
1457 : 2173344 : problem_data->in = NULL;
1458 : 2173344 : bitmap_obstack_initialize (&problem_data->live_bitmaps);
1459 : 2173344 : bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1460 : : }
1461 : :
1462 : 12656278 : df_grow_bb_info (df_live);
1463 : :
1464 : 90946177 : EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1465 : : {
1466 : 78289899 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1467 : :
1468 : : /* When bitmaps are already initialized, just clear them. */
1469 : 78289899 : if (bb_info->kill.obstack)
1470 : : {
1471 : 47405013 : bitmap_clear (&bb_info->kill);
1472 : 47405013 : bitmap_clear (&bb_info->gen);
1473 : : }
1474 : : else
1475 : : {
1476 : 30884886 : bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1477 : 30884886 : bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1478 : 30884886 : bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1479 : 30884886 : bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1480 : : }
1481 : : }
1482 : 12656278 : df_live->optional_p = (optimize <= 1);
1483 : 12656278 : }
1484 : :
1485 : :
1486 : : /* Reset the global solution for recalculation. */
1487 : :
1488 : : static void
1489 : 27993 : df_live_reset (bitmap all_blocks)
1490 : : {
1491 : 27993 : unsigned int bb_index;
1492 : 27993 : bitmap_iterator bi;
1493 : :
1494 : 167771 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1495 : : {
1496 : 139778 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1497 : 139778 : gcc_assert (bb_info);
1498 : 139778 : bitmap_clear (&bb_info->in);
1499 : 139778 : bitmap_clear (&bb_info->out);
1500 : : }
1501 : 27993 : }
1502 : :
1503 : :
1504 : : /* Compute local uninitialized register info for basic block BB. */
1505 : :
1506 : : static void
1507 : 78289899 : df_live_bb_local_compute (unsigned int bb_index)
1508 : : {
1509 : 78289899 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1510 : 78289899 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1511 : 78289899 : rtx_insn *insn;
1512 : 78289899 : df_ref def;
1513 : 78289899 : int luid = 0;
1514 : :
1515 : 1081933054 : FOR_BB_INSNS (bb, insn)
1516 : : {
1517 : 1003643155 : unsigned int uid = INSN_UID (insn);
1518 : 1003643155 : struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1519 : :
1520 : : /* Inserting labels does not always trigger the incremental
1521 : : rescanning. */
1522 : 1003643155 : if (!insn_info)
1523 : : {
1524 : 12685808 : gcc_assert (!INSN_P (insn));
1525 : 12685808 : insn_info = df_insn_create_insn_record (insn);
1526 : : }
1527 : :
1528 : 1003643155 : DF_INSN_INFO_LUID (insn_info) = luid;
1529 : 1003643155 : if (!INSN_P (insn))
1530 : 143165305 : continue;
1531 : :
1532 : 860477850 : luid++;
1533 : 4268193805 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
1534 : : {
1535 : 3407715955 : unsigned int regno = DF_REF_REGNO (def);
1536 : :
1537 : 3407715955 : if (DF_REF_FLAGS_IS_SET (def,
1538 : : DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1539 : : /* All partial or conditional def
1540 : : seen are included in the gen set. */
1541 : 1996039 : bitmap_set_bit (&bb_info->gen, regno);
1542 : 3405719916 : else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1543 : : /* Only must clobbers for the entire reg destroy the
1544 : : value. */
1545 : 76369327 : bitmap_set_bit (&bb_info->kill, regno);
1546 : 3329350589 : else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1547 : 379307976 : bitmap_set_bit (&bb_info->gen, regno);
1548 : : }
1549 : : }
1550 : :
1551 : 206627718 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1552 : 50047920 : bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1553 : 78289899 : }
1554 : :
1555 : :
1556 : : /* Compute local uninitialized register info. */
1557 : :
1558 : : static void
1559 : 12656278 : df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1560 : : {
1561 : 12656278 : unsigned int bb_index;
1562 : 12656278 : bitmap_iterator bi;
1563 : :
1564 : 12656278 : df_grow_insn_info ();
1565 : :
1566 : 90946177 : EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1567 : : 0, bb_index, bi)
1568 : : {
1569 : 78289899 : df_live_bb_local_compute (bb_index);
1570 : : }
1571 : :
1572 : 12656278 : bitmap_clear (df_live->out_of_date_transfer_functions);
1573 : 12656278 : }
1574 : :
1575 : :
1576 : : /* Initialize the solution vectors. */
1577 : :
1578 : : static void
1579 : 12656278 : df_live_init (bitmap all_blocks)
1580 : : {
1581 : 12656278 : unsigned int bb_index;
1582 : 12656278 : bitmap_iterator bi;
1583 : :
1584 : 270892678 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1585 : : {
1586 : 258236400 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1587 : 258236400 : class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1588 : :
1589 : : /* No register may reach a location where it is not used. Thus
1590 : : we trim the rr result to the places where it is used. */
1591 : 258236400 : bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1592 : 258236400 : bitmap_clear (&bb_info->in);
1593 : : }
1594 : 12656278 : }
1595 : :
1596 : : /* Forward confluence function that ignores fake edges. */
1597 : :
1598 : : static bool
1599 : 390607221 : df_live_confluence_n (edge e)
1600 : : {
1601 : 390607221 : bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1602 : 390607221 : bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1603 : :
1604 : 390607221 : if (e->flags & EDGE_FAKE)
1605 : : return false;
1606 : :
1607 : 390360429 : return bitmap_ior_into (op1, op2);
1608 : : }
1609 : :
1610 : :
1611 : : /* Transfer function for the forwards may-initialized problem. */
1612 : :
1613 : : static bool
1614 : 272056221 : df_live_transfer_function (int bb_index)
1615 : : {
1616 : 272056221 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1617 : 272056221 : class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1618 : 272056221 : bitmap in = &bb_info->in;
1619 : 272056221 : bitmap out = &bb_info->out;
1620 : 272056221 : bitmap gen = &bb_info->gen;
1621 : 272056221 : bitmap kill = &bb_info->kill;
1622 : :
1623 : : /* We need to use a scratch set here so that the value returned from this
1624 : : function invocation properly reflects whether the sets changed in a
1625 : : significant way; i.e. not just because the lr set was anded in. */
1626 : 272056221 : bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1627 : : /* No register may reach a location where it is not used. Thus
1628 : : we trim the rr result to the places where it is used. */
1629 : 272056221 : bitmap_and_into (in, &bb_lr_info->in);
1630 : :
1631 : 272056221 : return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1632 : : }
1633 : :
1634 : :
1635 : : /* And the LR info with the may-initialized registers to produce the LIVE info. */
1636 : :
1637 : : static void
1638 : 12656278 : df_live_finalize (bitmap all_blocks)
1639 : : {
1640 : :
1641 : 12656278 : if (df_live->solutions_dirty)
1642 : : {
1643 : 12656278 : bitmap_iterator bi;
1644 : 12656278 : unsigned int bb_index;
1645 : :
1646 : 270892678 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1647 : : {
1648 : 258236400 : class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1649 : 258236400 : class df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1650 : :
1651 : : /* No register may reach a location where it is not used. Thus
1652 : : we trim the rr result to the places where it is used. */
1653 : 258236400 : bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1654 : 258236400 : bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1655 : : }
1656 : :
1657 : 12656278 : df_live->solutions_dirty = false;
1658 : : }
1659 : 12656278 : }
1660 : :
1661 : :
1662 : : /* Free all storage associated with the problem. */
1663 : :
1664 : : static void
1665 : 2175792 : df_live_free (void)
1666 : : {
1667 : 2175792 : struct df_live_problem_data *problem_data
1668 : 2175792 : = (struct df_live_problem_data *) df_live->problem_data;
1669 : 2175792 : if (df_live->block_info)
1670 : : {
1671 : 2173344 : df_live->block_info_size = 0;
1672 : 2173344 : free (df_live->block_info);
1673 : 2173344 : df_live->block_info = NULL;
1674 : 2173344 : bitmap_release (&df_live_scratch);
1675 : 2173344 : bitmap_obstack_release (&problem_data->live_bitmaps);
1676 : 2173344 : free (problem_data);
1677 : 2173344 : df_live->problem_data = NULL;
1678 : : }
1679 : 2175792 : BITMAP_FREE (df_live->out_of_date_transfer_functions);
1680 : 2175792 : free (df_live);
1681 : 2175792 : }
1682 : :
1683 : :
1684 : : /* Debugging info at top of bb. */
1685 : :
1686 : : static void
1687 : 4185 : df_live_top_dump (basic_block bb, FILE *file)
1688 : : {
1689 : 4185 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1690 : 4089 : struct df_live_problem_data *problem_data;
1691 : :
1692 : 4089 : if (!bb_info)
1693 : : return;
1694 : :
1695 : 4089 : fprintf (file, ";; live in \t");
1696 : 4089 : df_print_regset (file, &bb_info->in);
1697 : 4089 : if (df_live->problem_data)
1698 : : {
1699 : 4089 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1700 : 4089 : if (problem_data->in)
1701 : : {
1702 : 0 : fprintf (file, ";; old in \t");
1703 : 0 : df_print_regset (file, &problem_data->in[bb->index]);
1704 : : }
1705 : : }
1706 : 4089 : fprintf (file, ";; live gen \t");
1707 : 4089 : df_print_regset (file, &bb_info->gen);
1708 : 4089 : fprintf (file, ";; live kill\t");
1709 : 4089 : df_print_regset (file, &bb_info->kill);
1710 : : }
1711 : :
1712 : :
1713 : : /* Debugging info at bottom of bb. */
1714 : :
1715 : : static void
1716 : 4185 : df_live_bottom_dump (basic_block bb, FILE *file)
1717 : : {
1718 : 4185 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1719 : 4089 : struct df_live_problem_data *problem_data;
1720 : :
1721 : 4089 : if (!bb_info)
1722 : : return;
1723 : :
1724 : 4089 : fprintf (file, ";; live out \t");
1725 : 4089 : df_print_regset (file, &bb_info->out);
1726 : 4089 : if (df_live->problem_data)
1727 : : {
1728 : 4089 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1729 : 4089 : if (problem_data->out)
1730 : : {
1731 : 0 : fprintf (file, ";; old out \t");
1732 : 0 : df_print_regset (file, &problem_data->out[bb->index]);
1733 : : }
1734 : : }
1735 : : }
1736 : :
1737 : :
1738 : : /* Build the datastructure to verify that the solution to the dataflow
1739 : : equations is not dirty. */
1740 : :
1741 : : static void
1742 : 0 : df_live_verify_solution_start (void)
1743 : : {
1744 : 0 : basic_block bb;
1745 : 0 : struct df_live_problem_data *problem_data;
1746 : 0 : if (df_live->solutions_dirty)
1747 : : return;
1748 : :
1749 : : /* Set it true so that the solution is recomputed. */
1750 : 0 : df_live->solutions_dirty = true;
1751 : :
1752 : 0 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1753 : 0 : problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1754 : 0 : problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1755 : :
1756 : 0 : FOR_ALL_BB_FN (bb, cfun)
1757 : : {
1758 : 0 : bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1759 : 0 : bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1760 : 0 : bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1761 : 0 : bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1762 : : }
1763 : : }
1764 : :
1765 : :
1766 : : /* Compare the saved datastructure and the new solution to the dataflow
1767 : : equations. */
1768 : :
1769 : : static void
1770 : 0 : df_live_verify_solution_end (void)
1771 : : {
1772 : 0 : struct df_live_problem_data *problem_data;
1773 : 0 : basic_block bb;
1774 : :
1775 : 0 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1776 : 0 : if (!problem_data->out)
1777 : : return;
1778 : :
1779 : 0 : FOR_ALL_BB_FN (bb, cfun)
1780 : : {
1781 : 0 : if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1782 : 0 : || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1783 : : {
1784 : : /*df_dump (stderr);*/
1785 : 0 : gcc_unreachable ();
1786 : : }
1787 : : }
1788 : :
1789 : : /* Cannot delete them immediately because you may want to dump them
1790 : : if the comparison fails. */
1791 : 0 : FOR_ALL_BB_FN (bb, cfun)
1792 : : {
1793 : 0 : bitmap_clear (&problem_data->in[bb->index]);
1794 : 0 : bitmap_clear (&problem_data->out[bb->index]);
1795 : : }
1796 : :
1797 : 0 : free (problem_data->in);
1798 : 0 : free (problem_data->out);
1799 : 0 : free (problem_data);
1800 : 0 : df_live->problem_data = NULL;
1801 : : }
1802 : :
1803 : :
1804 : : /* All of the information associated with every instance of the problem. */
1805 : :
1806 : : static const struct df_problem problem_LIVE =
1807 : : {
1808 : : DF_LIVE, /* Problem id. */
1809 : : DF_FORWARD, /* Direction. */
1810 : : df_live_alloc, /* Allocate the problem specific data. */
1811 : : df_live_reset, /* Reset global information. */
1812 : : df_live_free_bb_info, /* Free basic block info. */
1813 : : df_live_local_compute, /* Local compute function. */
1814 : : df_live_init, /* Init the solution specific data. */
1815 : : df_worklist_dataflow, /* Worklist solver. */
1816 : : NULL, /* Confluence operator 0. */
1817 : : df_live_confluence_n, /* Confluence operator n. */
1818 : : df_live_transfer_function, /* Transfer function. */
1819 : : df_live_finalize, /* Finalize function. */
1820 : : df_live_free, /* Free all of the problem information. */
1821 : : df_live_free, /* Remove this problem from the stack of dataflow problems. */
1822 : : NULL, /* Debugging. */
1823 : : df_live_top_dump, /* Debugging start block. */
1824 : : df_live_bottom_dump, /* Debugging end block. */
1825 : : NULL, /* Debugging start insn. */
1826 : : NULL, /* Debugging end insn. */
1827 : : df_live_verify_solution_start,/* Incremental solution verify start. */
1828 : : df_live_verify_solution_end, /* Incremental solution verify end. */
1829 : : &problem_LR, /* Dependent problem. */
1830 : : sizeof (class df_live_bb_info),/* Size of entry of block_info array. */
1831 : : TV_DF_LIVE, /* Timing variable. */
1832 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
1833 : : };
1834 : :
1835 : :
1836 : : /* Create a new DATAFLOW instance and add it to an existing instance
1837 : : of DF. The returned structure is what is used to get at the
1838 : : solution. */
1839 : :
1840 : : void
1841 : 2175792 : df_live_add_problem (void)
1842 : : {
1843 : 2175792 : df_add_problem (&problem_LIVE);
1844 : : /* These will be initialized when df_scan_blocks processes each
1845 : : block. */
1846 : 2175792 : df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1847 : 2175792 : }
1848 : :
1849 : :
1850 : : /* Set all of the blocks as dirty. This needs to be done if this
1851 : : problem is added after all of the insns have been scanned. */
1852 : :
1853 : : void
1854 : 1460394 : df_live_set_all_dirty (void)
1855 : : {
1856 : 1460394 : basic_block bb;
1857 : 23017829 : FOR_ALL_BB_FN (bb, cfun)
1858 : 21557435 : bitmap_set_bit (df_live->out_of_date_transfer_functions,
1859 : : bb->index);
1860 : 1460394 : }
1861 : :
1862 : :
1863 : : /* Verify that all of the lr related info is consistent and
1864 : : correct. */
1865 : :
1866 : : void
1867 : 0 : df_live_verify_transfer_functions (void)
1868 : : {
1869 : 0 : basic_block bb;
1870 : 0 : bitmap_head saved_gen;
1871 : 0 : bitmap_head saved_kill;
1872 : 0 : bitmap_head all_blocks;
1873 : :
1874 : 0 : if (!df)
1875 : 0 : return;
1876 : :
1877 : 0 : bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1878 : 0 : bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1879 : 0 : bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1880 : :
1881 : 0 : df_grow_insn_info ();
1882 : :
1883 : 0 : FOR_ALL_BB_FN (bb, cfun)
1884 : : {
1885 : 0 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1886 : 0 : bitmap_set_bit (&all_blocks, bb->index);
1887 : :
1888 : 0 : if (bb_info)
1889 : : {
1890 : : /* Make a copy of the transfer functions and then compute
1891 : : new ones to see if the transfer functions have
1892 : : changed. */
1893 : 0 : if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1894 : : bb->index))
1895 : : {
1896 : 0 : bitmap_copy (&saved_gen, &bb_info->gen);
1897 : 0 : bitmap_copy (&saved_kill, &bb_info->kill);
1898 : 0 : bitmap_clear (&bb_info->gen);
1899 : 0 : bitmap_clear (&bb_info->kill);
1900 : :
1901 : 0 : df_live_bb_local_compute (bb->index);
1902 : 0 : gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1903 : 0 : gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1904 : : }
1905 : : }
1906 : : else
1907 : : {
1908 : : /* If we do not have basic block info, the block must be in
1909 : : the list of dirty blocks or else some one has added a
1910 : : block behind our backs. */
1911 : 0 : gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1912 : : bb->index));
1913 : : }
1914 : : /* Make sure no one created a block without following
1915 : : procedures. */
1916 : 0 : gcc_assert (df_scan_get_bb_info (bb->index));
1917 : : }
1918 : :
1919 : : /* Make sure there are no dirty bits in blocks that have been deleted. */
1920 : 0 : gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1921 : : &all_blocks));
1922 : 0 : bitmap_clear (&saved_gen);
1923 : 0 : bitmap_clear (&saved_kill);
1924 : 0 : bitmap_clear (&all_blocks);
1925 : : }
1926 : :
1927 : : /*----------------------------------------------------------------------------
1928 : : MUST-INITIALIZED REGISTERS.
1929 : : ----------------------------------------------------------------------------*/
1930 : :
1931 : : /* Private data used to verify the solution for this problem. */
1932 : : struct df_mir_problem_data
1933 : : {
1934 : : bitmap_head *in;
1935 : : bitmap_head *out;
1936 : : /* An obstack for the bitmaps we need for this problem. */
1937 : : bitmap_obstack mir_bitmaps;
1938 : : };
1939 : :
1940 : :
1941 : : /* Free basic block info. */
1942 : :
1943 : : static void
1944 : 0 : df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1945 : : void *vbb_info)
1946 : : {
1947 : 0 : class df_mir_bb_info *bb_info = (class df_mir_bb_info *) vbb_info;
1948 : 0 : if (bb_info)
1949 : : {
1950 : 0 : bitmap_clear (&bb_info->gen);
1951 : 0 : bitmap_clear (&bb_info->kill);
1952 : 0 : bitmap_clear (&bb_info->in);
1953 : 0 : bitmap_clear (&bb_info->out);
1954 : : }
1955 : 0 : }
1956 : :
1957 : :
1958 : : /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
1959 : : not touched unless the block is new. */
1960 : :
1961 : : static void
1962 : 933053 : df_mir_alloc (bitmap all_blocks)
1963 : : {
1964 : 933053 : unsigned int bb_index;
1965 : 933053 : bitmap_iterator bi;
1966 : 933053 : struct df_mir_problem_data *problem_data;
1967 : :
1968 : 933053 : if (df_mir->problem_data)
1969 : : problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1970 : : else
1971 : : {
1972 : 933053 : problem_data = XNEW (struct df_mir_problem_data);
1973 : 933053 : df_mir->problem_data = problem_data;
1974 : :
1975 : 933053 : problem_data->out = NULL;
1976 : 933053 : problem_data->in = NULL;
1977 : 933053 : bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1978 : : }
1979 : :
1980 : 933053 : df_grow_bb_info (df_mir);
1981 : :
1982 : 12600211 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1983 : : {
1984 : 11667158 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1985 : :
1986 : : /* When bitmaps are already initialized, just clear them. */
1987 : 11667158 : if (bb_info->kill.obstack)
1988 : : {
1989 : 0 : bitmap_clear (&bb_info->kill);
1990 : 0 : bitmap_clear (&bb_info->gen);
1991 : : }
1992 : : else
1993 : : {
1994 : 11667158 : bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1995 : 11667158 : bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1996 : 11667158 : bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1997 : 11667158 : bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1998 : 11667158 : bb_info->con_visited = false;
1999 : : }
2000 : : }
2001 : :
2002 : 933053 : df_mir->optional_p = 1;
2003 : 933053 : }
2004 : :
2005 : :
2006 : : /* Reset the global solution for recalculation. */
2007 : :
2008 : : static void
2009 : 933053 : df_mir_reset (bitmap all_blocks)
2010 : : {
2011 : 933053 : unsigned int bb_index;
2012 : 933053 : bitmap_iterator bi;
2013 : :
2014 : 12600211 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2015 : : {
2016 : 11667158 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2017 : :
2018 : 11667158 : gcc_assert (bb_info);
2019 : :
2020 : 11667158 : bitmap_clear (&bb_info->in);
2021 : 11667158 : bitmap_clear (&bb_info->out);
2022 : 11667158 : bb_info->con_visited = false;
2023 : : }
2024 : 933053 : }
2025 : :
2026 : :
2027 : : /* Compute local uninitialized register info for basic block BB. */
2028 : :
2029 : : static void
2030 : 11667158 : df_mir_bb_local_compute (unsigned int bb_index)
2031 : : {
2032 : 11667158 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2033 : 11667158 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2034 : 11667158 : rtx_insn *insn;
2035 : 11667158 : int luid = 0;
2036 : :
2037 : : /* Ignoring artificial defs is intentional: these often pretend that some
2038 : : registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
2039 : : though they are not used for that. As a result, conservatively assume
2040 : : they may be uninitialized. */
2041 : :
2042 : 126218631 : FOR_BB_INSNS (bb, insn)
2043 : : {
2044 : 114551473 : unsigned int uid = INSN_UID (insn);
2045 : 114551473 : struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2046 : :
2047 : : /* Inserting labels does not always trigger the incremental
2048 : : rescanning. */
2049 : 114551473 : if (!insn_info)
2050 : : {
2051 : 3241 : gcc_assert (!INSN_P (insn));
2052 : 3241 : insn_info = df_insn_create_insn_record (insn);
2053 : : }
2054 : :
2055 : 114551473 : DF_INSN_INFO_LUID (insn_info) = luid;
2056 : 114551473 : if (!INSN_P (insn))
2057 : 20415936 : continue;
2058 : :
2059 : 94135537 : luid++;
2060 : 94135537 : df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
2061 : : }
2062 : 11667158 : }
2063 : :
2064 : :
2065 : : /* Compute local uninitialized register info. */
2066 : :
2067 : : static void
2068 : 933053 : df_mir_local_compute (bitmap all_blocks)
2069 : : {
2070 : 933053 : unsigned int bb_index;
2071 : 933053 : bitmap_iterator bi;
2072 : :
2073 : 933053 : df_grow_insn_info ();
2074 : :
2075 : 12600211 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2076 : : {
2077 : 11667158 : df_mir_bb_local_compute (bb_index);
2078 : : }
2079 : 933053 : }
2080 : :
2081 : :
2082 : : /* Initialize the solution vectors. */
2083 : :
2084 : : static void
2085 : 933053 : df_mir_init (bitmap all_blocks)
2086 : : {
2087 : 933053 : df_mir_reset (all_blocks);
2088 : 933053 : }
2089 : :
2090 : :
2091 : : /* Initialize IN sets for blocks with no predecessors: when landing on such
2092 : : blocks, assume all registers are uninitialized. */
2093 : :
2094 : : static void
2095 : 955346 : df_mir_confluence_0 (basic_block bb)
2096 : : {
2097 : 955346 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2098 : :
2099 : 955346 : bitmap_clear (&bb_info->in);
2100 : 955346 : bb_info->con_visited = true;
2101 : 955346 : }
2102 : :
2103 : :
2104 : : /* Forward confluence function that ignores fake edges. */
2105 : :
2106 : : static bool
2107 : 16165577 : df_mir_confluence_n (edge e)
2108 : : {
2109 : 16165577 : if (e->flags & EDGE_FAKE)
2110 : : return false;
2111 : :
2112 : 16165577 : df_mir_bb_info *src_info = df_mir_get_bb_info (e->src->index);
2113 : : /* If SRC was not visited yet then we'll and with all-ones which
2114 : : means no changes. Do not consider DST con_visited by this
2115 : : operation alone either. */
2116 : 16165577 : if (!src_info->con_visited)
2117 : : return false;
2118 : :
2119 : 15652196 : df_mir_bb_info *dst_info = df_mir_get_bb_info (e->dest->index);
2120 : 15652196 : bitmap op1 = &dst_info->in;
2121 : 15652196 : bitmap op2 = &src_info->out;
2122 : : /* If DEST was not visited yet just copy the SRC bitmap. */
2123 : 15652196 : if (!dst_info->con_visited)
2124 : : {
2125 : 10711812 : dst_info->con_visited = true;
2126 : 10711812 : bitmap_copy (op1, op2);
2127 : 10711812 : return true;
2128 : : }
2129 : :
2130 : : /* A register is must-initialized at the entry of a basic block iff it is
2131 : : must-initialized at the exit of all the predecessors. */
2132 : 4940384 : return bitmap_and_into (op1, op2);
2133 : : }
2134 : :
2135 : :
2136 : : /* Transfer function for the forwards must-initialized problem. */
2137 : :
2138 : : static bool
2139 : 12034843 : df_mir_transfer_function (int bb_index)
2140 : : {
2141 : 12034843 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2142 : 12034843 : bitmap in = &bb_info->in;
2143 : 12034843 : bitmap out = &bb_info->out;
2144 : 12034843 : bitmap gen = &bb_info->gen;
2145 : 12034843 : bitmap kill = &bb_info->kill;
2146 : :
2147 : 12034843 : return bitmap_ior_and_compl (out, gen, in, kill);
2148 : : }
2149 : :
2150 : :
2151 : : /* Free all storage associated with the problem. */
2152 : :
2153 : : static void
2154 : 933053 : df_mir_free (void)
2155 : : {
2156 : 933053 : struct df_mir_problem_data *problem_data
2157 : 933053 : = (struct df_mir_problem_data *) df_mir->problem_data;
2158 : 933053 : if (df_mir->block_info)
2159 : : {
2160 : 933053 : df_mir->block_info_size = 0;
2161 : 933053 : free (df_mir->block_info);
2162 : 933053 : df_mir->block_info = NULL;
2163 : 933053 : bitmap_obstack_release (&problem_data->mir_bitmaps);
2164 : 933053 : free (problem_data);
2165 : 933053 : df_mir->problem_data = NULL;
2166 : : }
2167 : 933053 : free (df_mir);
2168 : 933053 : }
2169 : :
2170 : :
2171 : : /* Debugging info at top of bb. */
2172 : :
2173 : : static void
2174 : 0 : df_mir_top_dump (basic_block bb, FILE *file)
2175 : : {
2176 : 0 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2177 : :
2178 : 0 : if (!bb_info)
2179 : : return;
2180 : :
2181 : 0 : fprintf (file, ";; mir in \t");
2182 : 0 : df_print_regset (file, &bb_info->in);
2183 : 0 : fprintf (file, ";; mir kill\t");
2184 : 0 : df_print_regset (file, &bb_info->kill);
2185 : 0 : fprintf (file, ";; mir gen \t");
2186 : 0 : df_print_regset (file, &bb_info->gen);
2187 : : }
2188 : :
2189 : : /* Debugging info at bottom of bb. */
2190 : :
2191 : : static void
2192 : 0 : df_mir_bottom_dump (basic_block bb, FILE *file)
2193 : : {
2194 : 0 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2195 : :
2196 : 0 : if (!bb_info)
2197 : : return;
2198 : :
2199 : 0 : fprintf (file, ";; mir out \t");
2200 : 0 : df_print_regset (file, &bb_info->out);
2201 : : }
2202 : :
2203 : :
2204 : : /* Build the datastructure to verify that the solution to the dataflow
2205 : : equations is not dirty. */
2206 : :
2207 : : static void
2208 : 0 : df_mir_verify_solution_start (void)
2209 : : {
2210 : 0 : basic_block bb;
2211 : 0 : struct df_mir_problem_data *problem_data;
2212 : 0 : if (df_mir->solutions_dirty)
2213 : : return;
2214 : :
2215 : : /* Set it true so that the solution is recomputed. */
2216 : 0 : df_mir->solutions_dirty = true;
2217 : :
2218 : 0 : problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2219 : 0 : problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2220 : 0 : problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2221 : 0 : bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2222 : :
2223 : 0 : FOR_ALL_BB_FN (bb, cfun)
2224 : : {
2225 : 0 : bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
2226 : 0 : bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
2227 : 0 : bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2228 : 0 : bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2229 : : }
2230 : : }
2231 : :
2232 : :
2233 : : /* Compare the saved datastructure and the new solution to the dataflow
2234 : : equations. */
2235 : :
2236 : : static void
2237 : 0 : df_mir_verify_solution_end (void)
2238 : : {
2239 : 0 : struct df_mir_problem_data *problem_data;
2240 : 0 : basic_block bb;
2241 : :
2242 : 0 : problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2243 : 0 : if (!problem_data->out)
2244 : : return;
2245 : :
2246 : 0 : FOR_ALL_BB_FN (bb, cfun)
2247 : : {
2248 : 0 : if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2249 : 0 : || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2250 : 0 : gcc_unreachable ();
2251 : : }
2252 : :
2253 : : /* Cannot delete them immediately because you may want to dump them
2254 : : if the comparison fails. */
2255 : 0 : FOR_ALL_BB_FN (bb, cfun)
2256 : : {
2257 : 0 : bitmap_clear (&problem_data->in[bb->index]);
2258 : 0 : bitmap_clear (&problem_data->out[bb->index]);
2259 : : }
2260 : :
2261 : 0 : free (problem_data->in);
2262 : 0 : free (problem_data->out);
2263 : 0 : bitmap_obstack_release (&problem_data->mir_bitmaps);
2264 : 0 : free (problem_data);
2265 : 0 : df_mir->problem_data = NULL;
2266 : : }
2267 : :
2268 : :
2269 : : /* All of the information associated with every instance of the problem. */
2270 : :
2271 : : static const struct df_problem problem_MIR =
2272 : : {
2273 : : DF_MIR, /* Problem id. */
2274 : : DF_FORWARD, /* Direction. */
2275 : : df_mir_alloc, /* Allocate the problem specific data. */
2276 : : df_mir_reset, /* Reset global information. */
2277 : : df_mir_free_bb_info, /* Free basic block info. */
2278 : : df_mir_local_compute, /* Local compute function. */
2279 : : df_mir_init, /* Init the solution specific data. */
2280 : : df_worklist_dataflow, /* Worklist solver. */
2281 : : df_mir_confluence_0, /* Confluence operator 0. */
2282 : : df_mir_confluence_n, /* Confluence operator n. */
2283 : : df_mir_transfer_function, /* Transfer function. */
2284 : : NULL, /* Finalize function. */
2285 : : df_mir_free, /* Free all of the problem information. */
2286 : : df_mir_free, /* Remove this problem from the stack of dataflow problems. */
2287 : : NULL, /* Debugging. */
2288 : : df_mir_top_dump, /* Debugging start block. */
2289 : : df_mir_bottom_dump, /* Debugging end block. */
2290 : : NULL, /* Debugging start insn. */
2291 : : NULL, /* Debugging end insn. */
2292 : : df_mir_verify_solution_start, /* Incremental solution verify start. */
2293 : : df_mir_verify_solution_end, /* Incremental solution verify end. */
2294 : : NULL, /* Dependent problem. */
2295 : : sizeof (class df_mir_bb_info),/* Size of entry of block_info array. */
2296 : : TV_DF_MIR, /* Timing variable. */
2297 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
2298 : : };
2299 : :
2300 : :
2301 : : /* Create a new DATAFLOW instance and add it to an existing instance
2302 : : of DF. */
2303 : :
2304 : : void
2305 : 933053 : df_mir_add_problem (void)
2306 : : {
2307 : 933053 : df_add_problem (&problem_MIR);
2308 : : /* These will be initialized when df_scan_blocks processes each
2309 : : block. */
2310 : 933053 : df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2311 : 933053 : }
2312 : :
2313 : :
2314 : : /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2315 : :
2316 : : void
2317 : 146313450 : df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2318 : : bitmap kill, bitmap gen)
2319 : : {
2320 : 146313450 : df_ref def;
2321 : :
2322 : 909171968 : FOR_EACH_INSN_DEF (def, insn)
2323 : : {
2324 : 762858518 : unsigned int regno = DF_REF_REGNO (def);
2325 : :
2326 : : /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
2327 : : previous gen is irrelevant (and reciprocally). Also, claim that a
2328 : : register is GEN only if it is in all cases. */
2329 : 762858518 : if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2330 : : {
2331 : 691070700 : bitmap_set_bit (kill, regno);
2332 : 691070700 : bitmap_clear_bit (gen, regno);
2333 : : }
2334 : : /* In the worst case, partial and conditional defs can leave bits
2335 : : uninitialized, so assume they do not change anything. */
2336 : 71787818 : else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2337 : : {
2338 : 71755324 : bitmap_set_bit (gen, regno);
2339 : 71755324 : bitmap_clear_bit (kill, regno);
2340 : : }
2341 : : }
2342 : 146313450 : }
2343 : :
2344 : : /*----------------------------------------------------------------------------
2345 : : CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2346 : :
2347 : : Link either the defs to the uses and / or the uses to the defs.
2348 : :
2349 : : These problems are set up like the other dataflow problems so that
2350 : : they nicely fit into the framework. They are much simpler and only
2351 : : involve a single traversal of instructions and an examination of
2352 : : the reaching defs information (the dependent problem).
2353 : : ----------------------------------------------------------------------------*/
2354 : :
2355 : : #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2356 : :
2357 : : /* Create a du or ud chain from SRC to DST and link it into SRC. */
2358 : :
2359 : : struct df_link *
2360 : 1112130464 : df_chain_create (df_ref src, df_ref dst)
2361 : : {
2362 : 1112130464 : struct df_link *head = DF_REF_CHAIN (src);
2363 : 1112130464 : struct df_link *link = df_chain->block_pool->allocate ();
2364 : :
2365 : 1112130464 : DF_REF_CHAIN (src) = link;
2366 : 1112130464 : link->next = head;
2367 : 1112130464 : link->ref = dst;
2368 : 1112130464 : return link;
2369 : : }
2370 : :
2371 : :
2372 : : /* Delete any du or ud chains that start at REF and point to
2373 : : TARGET. */
2374 : : static void
2375 : 695159 : df_chain_unlink_1 (df_ref ref, df_ref target)
2376 : : {
2377 : 695159 : struct df_link *chain = DF_REF_CHAIN (ref);
2378 : 695159 : struct df_link *prev = NULL;
2379 : :
2380 : 27822594 : while (chain)
2381 : : {
2382 : 27808094 : if (chain->ref == target)
2383 : : {
2384 : 680659 : if (prev)
2385 : 256256 : prev->next = chain->next;
2386 : : else
2387 : 424403 : DF_REF_CHAIN (ref) = chain->next;
2388 : 680659 : df_chain->block_pool->remove (chain);
2389 : 680659 : return;
2390 : : }
2391 : 27127435 : prev = chain;
2392 : 27127435 : chain = chain->next;
2393 : : }
2394 : : }
2395 : :
2396 : :
2397 : : /* Delete a du or ud chain that leave or point to REF. */
2398 : :
2399 : : void
2400 : 492764 : df_chain_unlink (df_ref ref)
2401 : : {
2402 : 492764 : struct df_link *chain = DF_REF_CHAIN (ref);
2403 : 1187923 : while (chain)
2404 : : {
2405 : 695159 : struct df_link *next = chain->next;
2406 : : /* Delete the other side if it exists. */
2407 : 695159 : df_chain_unlink_1 (chain->ref, ref);
2408 : 695159 : df_chain->block_pool->remove (chain);
2409 : 695159 : chain = next;
2410 : : }
2411 : 492764 : DF_REF_CHAIN (ref) = NULL;
2412 : 492764 : }
2413 : :
2414 : :
2415 : : /* Copy the du or ud chain starting at FROM_REF and attach it to
2416 : : TO_REF. */
2417 : :
2418 : : void
2419 : 0 : df_chain_copy (df_ref to_ref,
2420 : : struct df_link *from_ref)
2421 : : {
2422 : 0 : while (from_ref)
2423 : : {
2424 : 0 : df_chain_create (to_ref, from_ref->ref);
2425 : 0 : from_ref = from_ref->next;
2426 : : }
2427 : 0 : }
2428 : :
2429 : :
2430 : : /* Remove this problem from the stack of dataflow problems. */
2431 : :
2432 : : static void
2433 : 11527300 : df_chain_remove_problem (void)
2434 : : {
2435 : 11527300 : bitmap_iterator bi;
2436 : 11527300 : unsigned int bb_index;
2437 : :
2438 : : /* Wholesale destruction of the old chains. */
2439 : 11527300 : if (df_chain->block_pool)
2440 : 5763650 : delete df_chain->block_pool;
2441 : :
2442 : 75407014 : EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2443 : : {
2444 : 63879714 : rtx_insn *insn;
2445 : 63879714 : df_ref def, use;
2446 : 63879714 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2447 : :
2448 : 63879714 : if (df_chain_problem_p (DF_DU_CHAIN))
2449 : 150793666 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2450 : 62717388 : DF_REF_CHAIN (def) = NULL;
2451 : 63879714 : if (df_chain_problem_p (DF_UD_CHAIN))
2452 : 303977621 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2453 : 176218193 : DF_REF_CHAIN (use) = NULL;
2454 : :
2455 : 695601112 : FOR_BB_INSNS (bb, insn)
2456 : 631721398 : if (INSN_P (insn))
2457 : : {
2458 : 529268803 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2459 : 529268803 : if (df_chain_problem_p (DF_DU_CHAIN))
2460 : 1839292047 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2461 : 1475774677 : DF_REF_CHAIN (def) = NULL;
2462 : 529268803 : if (df_chain_problem_p (DF_UD_CHAIN))
2463 : : {
2464 : 950731840 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2465 : 421463037 : DF_REF_CHAIN (use) = NULL;
2466 : 542118249 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2467 : 12849446 : DF_REF_CHAIN (use) = NULL;
2468 : : }
2469 : : }
2470 : : }
2471 : :
2472 : 11527300 : bitmap_clear (df_chain->out_of_date_transfer_functions);
2473 : 11527300 : df_chain->block_pool = NULL;
2474 : 11527300 : }
2475 : :
2476 : :
2477 : : /* Remove the chain problem completely. */
2478 : :
2479 : : static void
2480 : 5763650 : df_chain_fully_remove_problem (void)
2481 : : {
2482 : 5763650 : df_chain_remove_problem ();
2483 : 5763650 : BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2484 : 5763650 : free (df_chain);
2485 : 5763650 : }
2486 : :
2487 : :
2488 : : /* Create def-use or use-def chains. */
2489 : :
2490 : : static void
2491 : 5763650 : df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2492 : : {
2493 : 5763650 : df_chain_remove_problem ();
2494 : 5763650 : df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2495 : 5763650 : df_chain->optional_p = true;
2496 : 5763650 : }
2497 : :
2498 : :
2499 : : /* Reset all of the chains when the set of basic blocks changes. */
2500 : :
2501 : : static void
2502 : 0 : df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2503 : : {
2504 : 0 : df_chain_remove_problem ();
2505 : 0 : }
2506 : :
2507 : :
2508 : : /* Create the chains for a list of USEs. */
2509 : :
2510 : : static void
2511 : 753658857 : df_chain_create_bb_process_use (bitmap local_rd,
2512 : : df_ref use,
2513 : : int top_flag)
2514 : : {
2515 : 753658857 : bitmap_iterator bi;
2516 : 753658857 : unsigned int def_index;
2517 : :
2518 : 1348664047 : for (; use; use = DF_REF_NEXT_LOC (use))
2519 : : {
2520 : 595005190 : unsigned int uregno = DF_REF_REGNO (use);
2521 : 595005190 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2522 : 4896272 : || (uregno >= FIRST_PSEUDO_REGISTER))
2523 : : {
2524 : : /* Do not want to go through this for an uninitialized var. */
2525 : 593690726 : int count = DF_DEFS_COUNT (uregno);
2526 : 593690726 : if (count)
2527 : : {
2528 : 553014848 : if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2529 : : {
2530 : 553014848 : unsigned int first_index = DF_DEFS_BEGIN (uregno);
2531 : 553014848 : unsigned int last_index = first_index + count - 1;
2532 : :
2533 : 1207320458 : EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2534 : : {
2535 : 1134983281 : df_ref def;
2536 : 1134983281 : if (def_index > last_index)
2537 : : break;
2538 : :
2539 : 654305610 : def = DF_DEFS_GET (def_index);
2540 : 654305610 : if (df_chain_problem_p (DF_DU_CHAIN))
2541 : 457824854 : df_chain_create (def, use);
2542 : 654305610 : if (df_chain_problem_p (DF_UD_CHAIN))
2543 : 654305610 : df_chain_create (use, def);
2544 : : }
2545 : : }
2546 : : }
2547 : : }
2548 : : }
2549 : 753658857 : }
2550 : :
2551 : :
2552 : : /* Create chains from reaching defs bitmaps for basic block BB. */
2553 : :
2554 : : static void
2555 : 63113460 : df_chain_create_bb (unsigned int bb_index)
2556 : : {
2557 : 63113460 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2558 : 63113460 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2559 : 63113460 : rtx_insn *insn;
2560 : 63113460 : bitmap_head cpy;
2561 : :
2562 : 63113460 : bitmap_initialize (&cpy, &bitmap_default_obstack);
2563 : 63113460 : bitmap_copy (&cpy, &bb_info->in);
2564 : 63113460 : bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2565 : :
2566 : : /* Since we are going forwards, process the artificial uses first
2567 : : then the artificial defs second. */
2568 : :
2569 : : #ifdef EH_USES
2570 : : /* Create the chains for the artificial uses from the EH_USES at the
2571 : : beginning of the block. */
2572 : :
2573 : : /* Artificials are only hard regs. */
2574 : : if (!(df->changeable_flags & DF_NO_HARD_REGS))
2575 : : df_chain_create_bb_process_use (&cpy,
2576 : : df_get_artificial_uses (bb->index),
2577 : : DF_REF_AT_TOP);
2578 : : #endif
2579 : :
2580 : 63113460 : df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2581 : :
2582 : : /* Process the regular instructions next. */
2583 : 689854145 : FOR_BB_INSNS (bb, insn)
2584 : 626740685 : if (INSN_P (insn))
2585 : : {
2586 : 525384377 : unsigned int uid = INSN_UID (insn);
2587 : :
2588 : : /* First scan the uses and link them up with the defs that remain
2589 : : in the cpy vector. */
2590 : 525384377 : df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2591 : 525384377 : if (df->changeable_flags & DF_EQ_NOTES)
2592 : 165713641 : df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2593 : :
2594 : : /* Since we are going forwards, process the defs second. */
2595 : 525384377 : df_rd_simulate_one_insn (bb, insn, &cpy);
2596 : : }
2597 : :
2598 : : /* Create the chains for the artificial uses of the hard registers
2599 : : at the end of the block. */
2600 : 63113460 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
2601 : 62560839 : df_chain_create_bb_process_use (&cpy,
2602 : 62560839 : df_get_artificial_uses (bb->index),
2603 : : 0);
2604 : :
2605 : 63113460 : bitmap_clear (&cpy);
2606 : 63113460 : }
2607 : :
2608 : : /* Create def-use chains from reaching use bitmaps for basic blocks
2609 : : in BLOCKS. */
2610 : :
2611 : : static void
2612 : 5763650 : df_chain_finalize (bitmap all_blocks)
2613 : : {
2614 : 5763650 : unsigned int bb_index;
2615 : 5763650 : bitmap_iterator bi;
2616 : :
2617 : 68877110 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2618 : : {
2619 : 63113460 : df_chain_create_bb (bb_index);
2620 : : }
2621 : 5763650 : }
2622 : :
2623 : :
2624 : : /* Free all storage associated with the problem. */
2625 : :
2626 : : static void
2627 : 0 : df_chain_free (void)
2628 : : {
2629 : 0 : delete df_chain->block_pool;
2630 : 0 : BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2631 : 0 : free (df_chain);
2632 : 0 : }
2633 : :
2634 : :
2635 : : /* Debugging info. */
2636 : :
2637 : : static void
2638 : 1276 : df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2639 : : {
2640 : : /* Artificials are only hard regs. */
2641 : 1276 : if (df->changeable_flags & DF_NO_HARD_REGS)
2642 : : return;
2643 : 1276 : if (df_chain_problem_p (DF_UD_CHAIN))
2644 : : {
2645 : 1276 : df_ref use;
2646 : :
2647 : 1914 : fprintf (file,
2648 : : ";; UD chains for artificial uses at %s\n",
2649 : : top ? "top" : "bottom");
2650 : 7480 : FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2651 : 4928 : if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2652 : 2464 : || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2653 : : {
2654 : 2464 : fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2655 : 2464 : df_chain_dump (DF_REF_CHAIN (use), file);
2656 : 2464 : fprintf (file, "\n");
2657 : : }
2658 : : }
2659 : 1276 : if (df_chain_problem_p (DF_DU_CHAIN))
2660 : : {
2661 : 0 : df_ref def;
2662 : :
2663 : 0 : fprintf (file,
2664 : : ";; DU chains for artificial defs at %s\n",
2665 : : top ? "top" : "bottom");
2666 : 0 : FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2667 : 0 : if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2668 : 0 : || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2669 : : {
2670 : 0 : fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2671 : 0 : df_chain_dump (DF_REF_CHAIN (def), file);
2672 : 0 : fprintf (file, "\n");
2673 : : }
2674 : : }
2675 : : }
2676 : :
2677 : : static void
2678 : 638 : df_chain_top_dump (basic_block bb, FILE *file)
2679 : : {
2680 : 638 : df_chain_bb_dump (bb, file, /*top=*/true);
2681 : 638 : }
2682 : :
2683 : : static void
2684 : 638 : df_chain_bottom_dump (basic_block bb, FILE *file)
2685 : : {
2686 : 638 : df_chain_bb_dump (bb, file, /*top=*/false);
2687 : 638 : }
2688 : :
2689 : : static void
2690 : 2157 : df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2691 : : {
2692 : 2157 : if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2693 : : {
2694 : 1349 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2695 : 1349 : df_ref use;
2696 : :
2697 : 1349 : fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2698 : : DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2699 : 3007 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2700 : 1658 : if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2701 : 517 : || !(df->changeable_flags & DF_NO_HARD_REGS))
2702 : : {
2703 : 1658 : fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2704 : 1658 : if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2705 : 0 : fprintf (file, "read/write ");
2706 : 1658 : df_chain_dump (DF_REF_CHAIN (use), file);
2707 : 1658 : fprintf (file, "\n");
2708 : : }
2709 : 1421 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2710 : 72 : if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2711 : 9 : || !(df->changeable_flags & DF_NO_HARD_REGS))
2712 : : {
2713 : 72 : fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2714 : 72 : df_chain_dump (DF_REF_CHAIN (use), file);
2715 : 72 : fprintf (file, "\n");
2716 : : }
2717 : : }
2718 : 2157 : }
2719 : :
2720 : : static void
2721 : 2157 : df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2722 : : {
2723 : 2157 : if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2724 : : {
2725 : 0 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2726 : 0 : df_ref def;
2727 : 0 : fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2728 : : DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2729 : 0 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2730 : 0 : if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2731 : 0 : || !(df->changeable_flags & DF_NO_HARD_REGS))
2732 : : {
2733 : 0 : fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2734 : 0 : if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2735 : 0 : fprintf (file, "read/write ");
2736 : 0 : df_chain_dump (DF_REF_CHAIN (def), file);
2737 : 0 : fprintf (file, "\n");
2738 : : }
2739 : 0 : fprintf (file, "\n");
2740 : : }
2741 : 2157 : }
2742 : :
2743 : : static const struct df_problem problem_CHAIN =
2744 : : {
2745 : : DF_CHAIN, /* Problem id. */
2746 : : DF_NONE, /* Direction. */
2747 : : df_chain_alloc, /* Allocate the problem specific data. */
2748 : : df_chain_reset, /* Reset global information. */
2749 : : NULL, /* Free basic block info. */
2750 : : NULL, /* Local compute function. */
2751 : : NULL, /* Init the solution specific data. */
2752 : : NULL, /* Iterative solver. */
2753 : : NULL, /* Confluence operator 0. */
2754 : : NULL, /* Confluence operator n. */
2755 : : NULL, /* Transfer function. */
2756 : : df_chain_finalize, /* Finalize function. */
2757 : : df_chain_free, /* Free all of the problem information. */
2758 : : df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2759 : : NULL, /* Debugging. */
2760 : : df_chain_top_dump, /* Debugging start block. */
2761 : : df_chain_bottom_dump, /* Debugging end block. */
2762 : : df_chain_insn_top_dump, /* Debugging start insn. */
2763 : : df_chain_insn_bottom_dump, /* Debugging end insn. */
2764 : : NULL, /* Incremental solution verify start. */
2765 : : NULL, /* Incremental solution verify end. */
2766 : : &problem_RD, /* Dependent problem. */
2767 : : sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2768 : : TV_DF_CHAIN, /* Timing variable. */
2769 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
2770 : : };
2771 : :
2772 : :
2773 : : /* Create a new DATAFLOW instance and add it to an existing instance
2774 : : of DF. The returned structure is what is used to get at the
2775 : : solution. */
2776 : :
2777 : : void
2778 : 5763650 : df_chain_add_problem (unsigned int chain_flags)
2779 : : {
2780 : 5763650 : df_add_problem (&problem_CHAIN);
2781 : 5763650 : df_chain->local_flags = chain_flags;
2782 : 5763650 : df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2783 : 5763650 : }
2784 : :
2785 : : #undef df_chain_problem_p
2786 : :
2787 : :
2788 : : /*----------------------------------------------------------------------------
2789 : : WORD LEVEL LIVE REGISTERS
2790 : :
2791 : : Find the locations in the function where any use of a pseudo can
2792 : : reach in the backwards direction. In and out bitvectors are built
2793 : : for each basic block. We only track pseudo registers that have a
2794 : : size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2795 : : contain two bits corresponding to each of the subwords.
2796 : :
2797 : : ----------------------------------------------------------------------------*/
2798 : :
2799 : : /* Private data used to verify the solution for this problem. */
2800 : : struct df_word_lr_problem_data
2801 : : {
2802 : : /* An obstack for the bitmaps we need for this problem. */
2803 : : bitmap_obstack word_lr_bitmaps;
2804 : : };
2805 : :
2806 : :
2807 : : /* Free basic block info. */
2808 : :
2809 : : static void
2810 : 0 : df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2811 : : void *vbb_info)
2812 : : {
2813 : 0 : class df_word_lr_bb_info *bb_info = (class df_word_lr_bb_info *) vbb_info;
2814 : 0 : if (bb_info)
2815 : : {
2816 : 0 : bitmap_clear (&bb_info->use);
2817 : 0 : bitmap_clear (&bb_info->def);
2818 : 0 : bitmap_clear (&bb_info->in);
2819 : 0 : bitmap_clear (&bb_info->out);
2820 : : }
2821 : 0 : }
2822 : :
2823 : :
2824 : : /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2825 : : not touched unless the block is new. */
2826 : :
2827 : : static void
2828 : 144122 : df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2829 : : {
2830 : 144122 : unsigned int bb_index;
2831 : 144122 : bitmap_iterator bi;
2832 : 144122 : basic_block bb;
2833 : 144122 : struct df_word_lr_problem_data *problem_data
2834 : 144122 : = XNEW (struct df_word_lr_problem_data);
2835 : :
2836 : 144122 : df_word_lr->problem_data = problem_data;
2837 : :
2838 : 144122 : df_grow_bb_info (df_word_lr);
2839 : :
2840 : : /* Create the mapping from regnos to slots. This does not change
2841 : : unless the problem is destroyed and recreated. In particular, if
2842 : : we end up deleting the only insn that used a subreg, we do not
2843 : : want to redo the mapping because this would invalidate everything
2844 : : else. */
2845 : :
2846 : 144122 : bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2847 : :
2848 : 3726573 : FOR_EACH_BB_FN (bb, cfun)
2849 : 3582451 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2850 : :
2851 : 144122 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2852 : 144122 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2853 : :
2854 : 4014817 : EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2855 : : {
2856 : 3870695 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2857 : :
2858 : : /* When bitmaps are already initialized, just clear them. */
2859 : 3870695 : if (bb_info->use.obstack)
2860 : : {
2861 : 0 : bitmap_clear (&bb_info->def);
2862 : 0 : bitmap_clear (&bb_info->use);
2863 : : }
2864 : : else
2865 : : {
2866 : 3870695 : bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2867 : 3870695 : bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2868 : 3870695 : bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2869 : 3870695 : bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2870 : : }
2871 : : }
2872 : :
2873 : 144122 : df_word_lr->optional_p = true;
2874 : 144122 : }
2875 : :
2876 : :
2877 : : /* Reset the global solution for recalculation. */
2878 : :
2879 : : static void
2880 : 0 : df_word_lr_reset (bitmap all_blocks)
2881 : : {
2882 : 0 : unsigned int bb_index;
2883 : 0 : bitmap_iterator bi;
2884 : :
2885 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2886 : : {
2887 : 0 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2888 : 0 : gcc_assert (bb_info);
2889 : 0 : bitmap_clear (&bb_info->in);
2890 : 0 : bitmap_clear (&bb_info->out);
2891 : : }
2892 : 0 : }
2893 : :
2894 : : /* Examine REF, and if it is for a reg we're interested in, set or
2895 : : clear the bits corresponding to its subwords from the bitmap
2896 : : according to IS_SET. LIVE is the bitmap we should update. We do
2897 : : not track hard regs or pseudos of any size other than 2 *
2898 : : UNITS_PER_WORD.
2899 : : We return true if we changed the bitmap, or if we encountered a register
2900 : : we're not tracking. */
2901 : :
2902 : : bool
2903 : 502138075 : df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2904 : : {
2905 : 502138075 : rtx orig_reg = DF_REF_REG (ref);
2906 : 502138075 : rtx reg = orig_reg;
2907 : 502138075 : machine_mode reg_mode;
2908 : 502138075 : unsigned regno;
2909 : : /* Left at -1 for whole accesses. */
2910 : 502138075 : int which_subword = -1;
2911 : 502138075 : bool changed = false;
2912 : :
2913 : 502138075 : if (GET_CODE (reg) == SUBREG)
2914 : 3985269 : reg = SUBREG_REG (orig_reg);
2915 : 502138075 : regno = REGNO (reg);
2916 : 502138075 : reg_mode = GET_MODE (reg);
2917 : 502138075 : if (regno < FIRST_PSEUDO_REGISTER
2918 : 567581188 : || maybe_ne (GET_MODE_SIZE (reg_mode), 2 * UNITS_PER_WORD))
2919 : : return true;
2920 : :
2921 : 9630339 : if (GET_CODE (orig_reg) == SUBREG
2922 : 9630339 : && read_modify_subreg_p (orig_reg))
2923 : : {
2924 : 1600839 : gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2925 : 1600839 : if (subreg_lowpart_p (orig_reg))
2926 : : which_subword = 0;
2927 : : else
2928 : 755308 : which_subword = 1;
2929 : : }
2930 : 9630339 : if (is_set)
2931 : : {
2932 : 6204657 : if (which_subword != 1)
2933 : 5690959 : changed |= bitmap_set_bit (live, regno * 2);
2934 : 5690959 : if (which_subword != 0)
2935 : 5653524 : changed |= bitmap_set_bit (live, regno * 2 + 1);
2936 : : }
2937 : : else
2938 : : {
2939 : 3425682 : if (which_subword != 1)
2940 : 3184072 : changed |= bitmap_clear_bit (live, regno * 2);
2941 : 3184072 : if (which_subword != 0)
2942 : 3131284 : changed |= bitmap_clear_bit (live, regno * 2 + 1);
2943 : : }
2944 : : return changed;
2945 : : }
2946 : :
2947 : : /* Compute local live register info for basic block BB. */
2948 : :
2949 : : static void
2950 : 3726573 : df_word_lr_bb_local_compute (unsigned int bb_index)
2951 : : {
2952 : 3726573 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2953 : 3726573 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2954 : 3726573 : rtx_insn *insn;
2955 : 3726573 : df_ref def, use;
2956 : :
2957 : : /* Ensure that artificial refs don't contain references to pseudos. */
2958 : 10037021 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2959 : 2583875 : gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2960 : :
2961 : 18056377 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2962 : 14329804 : gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2963 : :
2964 : 46427411 : FOR_BB_INSNS_REVERSE (bb, insn)
2965 : : {
2966 : 42700838 : if (!NONDEBUG_INSN_P (insn))
2967 : 21985788 : continue;
2968 : :
2969 : 20715050 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2970 : 170477105 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2971 : : /* If the def is to only part of the reg, it does
2972 : : not kill the other defs that reach here. */
2973 : 149762055 : if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2974 : : {
2975 : 149762055 : df_word_lr_mark_ref (def, true, &bb_info->def);
2976 : 149762055 : df_word_lr_mark_ref (def, false, &bb_info->use);
2977 : : }
2978 : 47150400 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2979 : 26435350 : df_word_lr_mark_ref (use, true, &bb_info->use);
2980 : : }
2981 : 3726573 : }
2982 : :
2983 : :
2984 : : /* Compute local live register info for each basic block within BLOCKS. */
2985 : :
2986 : : static void
2987 : 144122 : df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2988 : : {
2989 : 144122 : unsigned int bb_index;
2990 : 144122 : bitmap_iterator bi;
2991 : :
2992 : 4014817 : EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2993 : : {
2994 : 3870695 : if (bb_index == EXIT_BLOCK)
2995 : : {
2996 : 144122 : unsigned regno;
2997 : 144122 : bitmap_iterator bi;
2998 : 144122 : EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2999 : : regno, bi)
3000 : 0 : gcc_unreachable ();
3001 : : }
3002 : : else
3003 : 3726573 : df_word_lr_bb_local_compute (bb_index);
3004 : : }
3005 : :
3006 : 144122 : bitmap_clear (df_word_lr->out_of_date_transfer_functions);
3007 : 144122 : }
3008 : :
3009 : :
3010 : : /* Initialize the solution vectors. */
3011 : :
3012 : : static void
3013 : 144122 : df_word_lr_init (bitmap all_blocks)
3014 : : {
3015 : 144122 : unsigned int bb_index;
3016 : 144122 : bitmap_iterator bi;
3017 : :
3018 : 4014817 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3019 : : {
3020 : 3870695 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
3021 : 3870695 : bitmap_copy (&bb_info->in, &bb_info->use);
3022 : 3870695 : bitmap_clear (&bb_info->out);
3023 : : }
3024 : 144122 : }
3025 : :
3026 : :
3027 : : /* Confluence function that ignores fake edges. */
3028 : :
3029 : : static bool
3030 : 5948535 : df_word_lr_confluence_n (edge e)
3031 : : {
3032 : 5948535 : bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
3033 : 5948535 : bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
3034 : :
3035 : 5948535 : return bitmap_ior_into (op1, op2);
3036 : : }
3037 : :
3038 : :
3039 : : /* Transfer function. */
3040 : :
3041 : : static bool
3042 : 4218351 : df_word_lr_transfer_function (int bb_index)
3043 : : {
3044 : 4218351 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
3045 : 4218351 : bitmap in = &bb_info->in;
3046 : 4218351 : bitmap out = &bb_info->out;
3047 : 4218351 : bitmap use = &bb_info->use;
3048 : 4218351 : bitmap def = &bb_info->def;
3049 : :
3050 : 4218351 : return bitmap_ior_and_compl (in, use, out, def);
3051 : : }
3052 : :
3053 : :
3054 : : /* Free all storage associated with the problem. */
3055 : :
3056 : : static void
3057 : 144122 : df_word_lr_free (void)
3058 : : {
3059 : 144122 : struct df_word_lr_problem_data *problem_data
3060 : 144122 : = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
3061 : :
3062 : 144122 : if (df_word_lr->block_info)
3063 : : {
3064 : 144122 : df_word_lr->block_info_size = 0;
3065 : 144122 : free (df_word_lr->block_info);
3066 : 144122 : df_word_lr->block_info = NULL;
3067 : : }
3068 : :
3069 : 144122 : BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
3070 : 144122 : bitmap_obstack_release (&problem_data->word_lr_bitmaps);
3071 : 144122 : free (problem_data);
3072 : 144122 : free (df_word_lr);
3073 : 144122 : }
3074 : :
3075 : :
3076 : : /* Debugging info at top of bb. */
3077 : :
3078 : : static void
3079 : 0 : df_word_lr_top_dump (basic_block bb, FILE *file)
3080 : : {
3081 : 0 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3082 : 0 : if (!bb_info)
3083 : : return;
3084 : :
3085 : 0 : fprintf (file, ";; blr in \t");
3086 : 0 : df_print_word_regset (file, &bb_info->in);
3087 : 0 : fprintf (file, ";; blr use \t");
3088 : 0 : df_print_word_regset (file, &bb_info->use);
3089 : 0 : fprintf (file, ";; blr def \t");
3090 : 0 : df_print_word_regset (file, &bb_info->def);
3091 : : }
3092 : :
3093 : :
3094 : : /* Debugging info at bottom of bb. */
3095 : :
3096 : : static void
3097 : 0 : df_word_lr_bottom_dump (basic_block bb, FILE *file)
3098 : : {
3099 : 0 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3100 : 0 : if (!bb_info)
3101 : : return;
3102 : :
3103 : 0 : fprintf (file, ";; blr out \t");
3104 : 0 : df_print_word_regset (file, &bb_info->out);
3105 : : }
3106 : :
3107 : :
3108 : : /* All of the information associated with every instance of the problem. */
3109 : :
3110 : : static const struct df_problem problem_WORD_LR =
3111 : : {
3112 : : DF_WORD_LR, /* Problem id. */
3113 : : DF_BACKWARD, /* Direction. */
3114 : : df_word_lr_alloc, /* Allocate the problem specific data. */
3115 : : df_word_lr_reset, /* Reset global information. */
3116 : : df_word_lr_free_bb_info, /* Free basic block info. */
3117 : : df_word_lr_local_compute, /* Local compute function. */
3118 : : df_word_lr_init, /* Init the solution specific data. */
3119 : : df_worklist_dataflow, /* Worklist solver. */
3120 : : NULL, /* Confluence operator 0. */
3121 : : df_word_lr_confluence_n, /* Confluence operator n. */
3122 : : df_word_lr_transfer_function, /* Transfer function. */
3123 : : NULL, /* Finalize function. */
3124 : : df_word_lr_free, /* Free all of the problem information. */
3125 : : df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
3126 : : NULL, /* Debugging. */
3127 : : df_word_lr_top_dump, /* Debugging start block. */
3128 : : df_word_lr_bottom_dump, /* Debugging end block. */
3129 : : NULL, /* Debugging start insn. */
3130 : : NULL, /* Debugging end insn. */
3131 : : NULL, /* Incremental solution verify start. */
3132 : : NULL, /* Incremental solution verify end. */
3133 : : NULL, /* Dependent problem. */
3134 : : sizeof (class df_word_lr_bb_info),/* Size of entry of block_info array. */
3135 : : TV_DF_WORD_LR, /* Timing variable. */
3136 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
3137 : : };
3138 : :
3139 : :
3140 : : /* Create a new DATAFLOW instance and add it to an existing instance
3141 : : of DF. The returned structure is what is used to get at the
3142 : : solution. */
3143 : :
3144 : : void
3145 : 144122 : df_word_lr_add_problem (void)
3146 : : {
3147 : 144122 : df_add_problem (&problem_WORD_LR);
3148 : : /* These will be initialized when df_scan_blocks processes each
3149 : : block. */
3150 : 144122 : df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3151 : 144122 : }
3152 : :
3153 : :
3154 : : /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
3155 : : any bits, which is used by the caller to determine whether a set is
3156 : : necessary. We also return true if there are other reasons not to delete
3157 : : an insn. */
3158 : :
3159 : : bool
3160 : 20715050 : df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3161 : : {
3162 : 20715050 : bool changed = false;
3163 : 20715050 : df_ref def;
3164 : :
3165 : 170477105 : FOR_EACH_INSN_DEF (def, insn)
3166 : 149762055 : if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3167 : : changed = true;
3168 : : else
3169 : 149762055 : changed |= df_word_lr_mark_ref (def, false, live);
3170 : 20715050 : return changed;
3171 : : }
3172 : :
3173 : :
3174 : : /* Simulate the effects of the uses of INSN on LIVE. */
3175 : :
3176 : : void
3177 : 20704387 : df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3178 : : {
3179 : 20704387 : df_ref use;
3180 : :
3181 : 47120947 : FOR_EACH_INSN_USE (use, insn)
3182 : 26416560 : df_word_lr_mark_ref (use, true, live);
3183 : 20704387 : }
3184 : :
3185 : : /*----------------------------------------------------------------------------
3186 : : This problem computes REG_DEAD and REG_UNUSED notes.
3187 : : ----------------------------------------------------------------------------*/
3188 : :
3189 : : static void
3190 : 15228660 : df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3191 : : {
3192 : 15228660 : df_note->optional_p = true;
3193 : 15228660 : }
3194 : :
3195 : : /* This is only used if REG_DEAD_DEBUGGING is in effect. */
3196 : : static void
3197 : 0 : df_print_note (const char *prefix, rtx_insn *insn, rtx note)
3198 : : {
3199 : 0 : if (dump_file)
3200 : : {
3201 : 0 : fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3202 : 0 : print_rtl (dump_file, note);
3203 : 0 : fprintf (dump_file, "\n");
3204 : : }
3205 : 0 : }
3206 : :
3207 : :
3208 : : /* After reg-stack, the x86 floating point stack regs are difficult to
3209 : : analyze because of all of the pushes, pops and rotations. Thus, we
3210 : : just leave the notes alone. */
3211 : :
3212 : : #ifdef STACK_REGS
3213 : : static inline bool
3214 : 1221837734 : df_ignore_stack_reg (int regno)
3215 : : {
3216 : 1221837734 : return regstack_completed
3217 : 548752759 : && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3218 : : }
3219 : : #else
3220 : : static inline bool
3221 : : df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3222 : : {
3223 : : return false;
3224 : : }
3225 : : #endif
3226 : :
3227 : :
3228 : : /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
3229 : :
3230 : : static void
3231 : 1652928301 : df_remove_dead_and_unused_notes (rtx_insn *insn)
3232 : : {
3233 : 1652928301 : rtx *pprev = ®_NOTES (insn);
3234 : 1652928301 : rtx link = *pprev;
3235 : :
3236 : 2539786690 : while (link)
3237 : : {
3238 : 886858389 : switch (REG_NOTE_KIND (link))
3239 : : {
3240 : 435270873 : case REG_DEAD:
3241 : : /* After reg-stack, we need to ignore any unused notes
3242 : : for the stack registers. */
3243 : 435270873 : if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3244 : : {
3245 : 0 : pprev = &XEXP (link, 1);
3246 : 0 : link = *pprev;
3247 : : }
3248 : : else
3249 : : {
3250 : 435270873 : rtx next = XEXP (link, 1);
3251 : 435270873 : if (REG_DEAD_DEBUGGING)
3252 : : df_print_note ("deleting: ", insn, link);
3253 : 435270873 : free_EXPR_LIST_node (link);
3254 : 435270873 : *pprev = link = next;
3255 : : }
3256 : : break;
3257 : :
3258 : 113481886 : case REG_UNUSED:
3259 : : /* After reg-stack, we need to ignore any unused notes
3260 : : for the stack registers. */
3261 : 113481886 : if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3262 : : {
3263 : 0 : pprev = &XEXP (link, 1);
3264 : 0 : link = *pprev;
3265 : : }
3266 : : else
3267 : : {
3268 : 113481886 : rtx next = XEXP (link, 1);
3269 : 113481886 : if (REG_DEAD_DEBUGGING)
3270 : : df_print_note ("deleting: ", insn, link);
3271 : 113481886 : free_EXPR_LIST_node (link);
3272 : 113481886 : *pprev = link = next;
3273 : : }
3274 : : break;
3275 : :
3276 : 338105630 : default:
3277 : 338105630 : pprev = &XEXP (link, 1);
3278 : 338105630 : link = *pprev;
3279 : 338105630 : break;
3280 : : }
3281 : : }
3282 : 1652928301 : }
3283 : :
3284 : : /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
3285 : : as the bitmap of currently live registers. */
3286 : :
3287 : : static void
3288 : 1652928301 : df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3289 : : {
3290 : 1652928301 : rtx *pprev = ®_NOTES (insn);
3291 : 1652928301 : rtx link = *pprev;
3292 : :
3293 : 2661667010 : while (link)
3294 : : {
3295 : 1008738709 : switch (REG_NOTE_KIND (link))
3296 : : {
3297 : 67412933 : case REG_EQUAL:
3298 : 67412933 : case REG_EQUIV:
3299 : 67412933 : {
3300 : : /* Remove the notes that refer to dead registers. As we have at most
3301 : : one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3302 : : so we need to purge the complete EQ_USES vector when removing
3303 : : the note using df_notes_rescan. */
3304 : 67412933 : df_ref use;
3305 : 67412933 : bool deleted = false;
3306 : :
3307 : 113735170 : FOR_EACH_INSN_EQ_USE (use, insn)
3308 : 46676119 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
3309 : 9330632 : && DF_REF_LOC (use)
3310 : 9330632 : && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3311 : 9330632 : && !bitmap_bit_p (live, DF_REF_REGNO (use))
3312 : 47032762 : && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3313 : : {
3314 : : deleted = true;
3315 : : break;
3316 : : }
3317 : 67412933 : if (deleted)
3318 : : {
3319 : 353882 : rtx next;
3320 : 353882 : if (REG_DEAD_DEBUGGING)
3321 : : df_print_note ("deleting: ", insn, link);
3322 : 353882 : next = XEXP (link, 1);
3323 : 353882 : free_EXPR_LIST_node (link);
3324 : 353882 : *pprev = link = next;
3325 : 353882 : df_notes_rescan (insn);
3326 : : }
3327 : : else
3328 : : {
3329 : 67059051 : pprev = &XEXP (link, 1);
3330 : 67059051 : link = *pprev;
3331 : : }
3332 : : break;
3333 : : }
3334 : :
3335 : 941325776 : default:
3336 : 941325776 : pprev = &XEXP (link, 1);
3337 : 941325776 : link = *pprev;
3338 : 941325776 : break;
3339 : : }
3340 : : }
3341 : 1652928301 : }
3342 : :
3343 : : /* Set a NOTE_TYPE note for REG in INSN. */
3344 : :
3345 : : static inline void
3346 : 670633079 : df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3347 : : {
3348 : 670633079 : gcc_checking_assert (!DEBUG_INSN_P (insn));
3349 : 670633079 : add_reg_note (insn, note_type, reg);
3350 : 670633079 : }
3351 : :
3352 : : /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3353 : : arguments. Return true if the register value described by MWS's
3354 : : mw_reg is known to be completely unused, and if mw_reg can therefore
3355 : : be used in a REG_UNUSED note. */
3356 : :
3357 : : static bool
3358 : 2618924 : df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3359 : : bitmap live, bitmap artificial_uses)
3360 : : {
3361 : 2618924 : unsigned int r;
3362 : :
3363 : : /* If MWS describes a partial reference, create REG_UNUSED notes for
3364 : : individual hard registers. */
3365 : 2618924 : if (mws->flags & DF_REF_PARTIAL)
3366 : : return false;
3367 : :
3368 : : /* Likewise if some part of the register is used. */
3369 : 2961424 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3370 : 2803807 : if (bitmap_bit_p (live, r)
3371 : 2803807 : || bitmap_bit_p (artificial_uses, r))
3372 : 2461307 : return false;
3373 : :
3374 : 157617 : gcc_assert (REG_P (mws->mw_reg));
3375 : : return true;
3376 : : }
3377 : :
3378 : :
3379 : : /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3380 : : based on the bits in LIVE. Do not generate notes for registers in
3381 : : artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3382 : : not generated if the reg is both read and written by the
3383 : : instruction.
3384 : : */
3385 : :
3386 : : static void
3387 : 2618924 : df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3388 : : bitmap live, bitmap do_not_gen,
3389 : : bitmap artificial_uses,
3390 : : struct dead_debug_local *debug)
3391 : : {
3392 : 2618924 : unsigned int r;
3393 : :
3394 : 2618924 : if (REG_DEAD_DEBUGGING && dump_file)
3395 : : fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3396 : : mws->start_regno, mws->end_regno);
3397 : :
3398 : 2618924 : if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3399 : : {
3400 : 157617 : unsigned int regno = mws->start_regno;
3401 : 157617 : df_set_note (REG_UNUSED, insn, mws->mw_reg);
3402 : 157617 : dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3403 : :
3404 : 157617 : if (REG_DEAD_DEBUGGING)
3405 : : df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3406 : :
3407 : 157617 : bitmap_set_bit (do_not_gen, regno);
3408 : : /* Only do this if the value is totally dead. */
3409 : : }
3410 : : else
3411 : 7383921 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3412 : : {
3413 : 4922614 : if (!bitmap_bit_p (live, r)
3414 : 4922614 : && !bitmap_bit_p (artificial_uses, r))
3415 : : {
3416 : 125378 : df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3417 : 125378 : dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3418 : 125378 : if (REG_DEAD_DEBUGGING)
3419 : : df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3420 : : }
3421 : 4922614 : bitmap_set_bit (do_not_gen, r);
3422 : : }
3423 : 2618924 : }
3424 : :
3425 : :
3426 : : /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3427 : : arguments. Return true if the register value described by MWS's
3428 : : mw_reg is known to be completely dead, and if mw_reg can therefore
3429 : : be used in a REG_DEAD note. */
3430 : :
3431 : : static bool
3432 : 1981595 : df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3433 : : bitmap live, bitmap artificial_uses,
3434 : : bitmap do_not_gen)
3435 : : {
3436 : 1981595 : unsigned int r;
3437 : :
3438 : : /* If MWS describes a partial reference, create REG_DEAD notes for
3439 : : individual hard registers. */
3440 : 1981595 : if (mws->flags & DF_REF_PARTIAL)
3441 : : return false;
3442 : :
3443 : : /* Likewise if some part of the register is not dead. */
3444 : 4159417 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3445 : 3070436 : if (bitmap_bit_p (live, r)
3446 : 2399128 : || bitmap_bit_p (artificial_uses, r)
3447 : 5469564 : || bitmap_bit_p (do_not_gen, r))
3448 : 891649 : return false;
3449 : :
3450 : 1088981 : gcc_assert (REG_P (mws->mw_reg));
3451 : : return true;
3452 : : }
3453 : :
3454 : : /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3455 : : on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3456 : : from being set if the instruction both reads and writes the
3457 : : register. */
3458 : :
3459 : : static void
3460 : 1981595 : df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3461 : : bitmap live, bitmap do_not_gen,
3462 : : bitmap artificial_uses, bool *added_notes_p)
3463 : : {
3464 : 1981595 : unsigned int r;
3465 : 1981595 : bool is_debug = *added_notes_p;
3466 : :
3467 : 1981595 : *added_notes_p = false;
3468 : :
3469 : 1981595 : if (REG_DEAD_DEBUGGING && dump_file)
3470 : : {
3471 : : fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3472 : : mws->start_regno, mws->end_regno);
3473 : : df_print_regset (dump_file, do_not_gen);
3474 : : fprintf (dump_file, " live =");
3475 : : df_print_regset (dump_file, live);
3476 : : fprintf (dump_file, " artificial uses =");
3477 : : df_print_regset (dump_file, artificial_uses);
3478 : : }
3479 : :
3480 : 1981595 : if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3481 : : {
3482 : 1088981 : if (is_debug)
3483 : : {
3484 : 336 : *added_notes_p = true;
3485 : 336 : return;
3486 : : }
3487 : : /* Add a dead note for the entire multi word register. */
3488 : 1088645 : df_set_note (REG_DEAD, insn, mws->mw_reg);
3489 : 1088645 : if (REG_DEAD_DEBUGGING)
3490 : : df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3491 : : }
3492 : : else
3493 : : {
3494 : 2675215 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3495 : 1784406 : if (!bitmap_bit_p (live, r)
3496 : 442411 : && !bitmap_bit_p (artificial_uses, r)
3497 : 2226817 : && !bitmap_bit_p (do_not_gen, r))
3498 : : {
3499 : 157482 : if (is_debug)
3500 : : {
3501 : 1805 : *added_notes_p = true;
3502 : 1805 : return;
3503 : : }
3504 : 155677 : df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3505 : 155677 : if (REG_DEAD_DEBUGGING)
3506 : : df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3507 : : }
3508 : : }
3509 : : return;
3510 : : }
3511 : :
3512 : :
3513 : : /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3514 : : LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3515 : :
3516 : : static void
3517 : 832761957 : df_create_unused_note (rtx_insn *insn, df_ref def,
3518 : : bitmap live, bitmap artificial_uses,
3519 : : struct dead_debug_local *debug)
3520 : : {
3521 : 832761957 : unsigned int dregno = DF_REF_REGNO (def);
3522 : :
3523 : 832761957 : if (REG_DEAD_DEBUGGING && dump_file)
3524 : : {
3525 : : fprintf (dump_file, " regular looking at def ");
3526 : : df_ref_debug (def, dump_file);
3527 : : }
3528 : :
3529 : 832761957 : if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3530 : 827524109 : || bitmap_bit_p (live, dregno)
3531 : 138455498 : || bitmap_bit_p (artificial_uses, dregno)
3532 : 138440229 : || df_ignore_stack_reg (dregno)))
3533 : : {
3534 : 138440229 : rtx reg = (DF_REF_LOC (def))
3535 : 138440229 : ? *DF_REF_REAL_LOC (def) : DF_REF_REG (def);
3536 : 138440229 : df_set_note (REG_UNUSED, insn, reg);
3537 : 138440229 : dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3538 : 138440229 : if (REG_DEAD_DEBUGGING)
3539 : : df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3540 : : }
3541 : :
3542 : 832761957 : return;
3543 : : }
3544 : :
3545 : :
3546 : : /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3547 : : info: lifetime, bb, and number of defs and uses for basic block
3548 : : BB. The three bitvectors are scratch regs used here. */
3549 : :
3550 : : static void
3551 : 200301876 : df_note_bb_compute (unsigned int bb_index,
3552 : : bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3553 : : {
3554 : 200301876 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3555 : 200301876 : rtx_insn *insn;
3556 : 200301876 : df_ref def, use;
3557 : 200301876 : struct dead_debug_local debug;
3558 : :
3559 : 200301876 : dead_debug_local_init (&debug, NULL, NULL);
3560 : :
3561 : 200301876 : bitmap_copy (live, df_get_live_out (bb));
3562 : 200301876 : bitmap_clear (artificial_uses);
3563 : :
3564 : 200301876 : if (REG_DEAD_DEBUGGING && dump_file)
3565 : : {
3566 : : fprintf (dump_file, "live at bottom ");
3567 : : df_print_regset (dump_file, live);
3568 : : }
3569 : :
3570 : : /* Process the artificial defs and uses at the bottom of the block
3571 : : to begin processing. */
3572 : 661774758 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3573 : : {
3574 : 261171006 : if (REG_DEAD_DEBUGGING && dump_file)
3575 : : fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3576 : :
3577 : 261171006 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3578 : 254962299 : bitmap_clear_bit (live, DF_REF_REGNO (def));
3579 : : }
3580 : :
3581 : 926980384 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3582 : 526376632 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3583 : : {
3584 : 526376632 : unsigned int regno = DF_REF_REGNO (use);
3585 : 526376632 : bitmap_set_bit (live, regno);
3586 : :
3587 : : /* Notes are not generated for any of the artificial registers
3588 : : at the bottom of the block. */
3589 : 526376632 : bitmap_set_bit (artificial_uses, regno);
3590 : : }
3591 : :
3592 : 200301876 : if (REG_DEAD_DEBUGGING && dump_file)
3593 : : {
3594 : : fprintf (dump_file, "live before artificials out ");
3595 : : df_print_regset (dump_file, live);
3596 : : }
3597 : :
3598 : 2183059747 : FOR_BB_INSNS_REVERSE (bb, insn)
3599 : : {
3600 : 2312587441 : if (!INSN_P (insn))
3601 : 329829570 : continue;
3602 : :
3603 : 1652928301 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3604 : 1652928301 : df_mw_hardreg *mw;
3605 : 1652928301 : int debug_insn;
3606 : :
3607 : 1652928301 : debug_insn = DEBUG_INSN_P (insn);
3608 : :
3609 : 1652928301 : bitmap_clear (do_not_gen);
3610 : 1652928301 : df_remove_dead_and_unused_notes (insn);
3611 : :
3612 : : /* Process the defs. */
3613 : 1652928301 : if (CALL_P (insn))
3614 : : {
3615 : 72061888 : if (REG_DEAD_DEBUGGING && dump_file)
3616 : : {
3617 : : fprintf (dump_file, "processing call %d\n live =",
3618 : : INSN_UID (insn));
3619 : : df_print_regset (dump_file, live);
3620 : : }
3621 : :
3622 : : /* We only care about real sets for calls. Clobbers cannot
3623 : : be depended on to really die. */
3624 : 74742993 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3625 : 2681105 : if ((DF_MWS_REG_DEF_P (mw))
3626 : 4500390 : && !df_ignore_stack_reg (mw->start_regno))
3627 : 1819285 : df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3628 : : artificial_uses, &debug);
3629 : :
3630 : : /* All of the defs except the return value are some sort of
3631 : : clobber. This code is for the return. */
3632 : 5968859032 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3633 : : {
3634 : 5896797144 : unsigned int dregno = DF_REF_REGNO (def);
3635 : 5896797144 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3636 : : {
3637 : 33998237 : df_create_unused_note (insn,
3638 : : def, live, artificial_uses, &debug);
3639 : 33998237 : bitmap_set_bit (do_not_gen, dregno);
3640 : : }
3641 : :
3642 : 5896797144 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3643 : 5896797144 : bitmap_clear_bit (live, dregno);
3644 : : }
3645 : : }
3646 : : else
3647 : : {
3648 : : /* Regular insn. */
3649 : 1582785827 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3650 : 1919414 : if (DF_MWS_REG_DEF_P (mw))
3651 : 799639 : df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3652 : : artificial_uses, &debug);
3653 : :
3654 : 2379630133 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3655 : : {
3656 : 798763720 : unsigned int dregno = DF_REF_REGNO (def);
3657 : 798763720 : df_create_unused_note (insn,
3658 : : def, live, artificial_uses, &debug);
3659 : :
3660 : 798763720 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3661 : 671860871 : bitmap_set_bit (do_not_gen, dregno);
3662 : :
3663 : 798763720 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3664 : 796049293 : bitmap_clear_bit (live, dregno);
3665 : : }
3666 : : }
3667 : :
3668 : : /* Process the uses. */
3669 : 1657528820 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3670 : 4600519 : if (DF_MWS_REG_USE_P (mw)
3671 : 6582114 : && !df_ignore_stack_reg (mw->start_regno))
3672 : : {
3673 : 1981595 : bool really_add_notes = debug_insn != 0;
3674 : :
3675 : 1981595 : df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3676 : : artificial_uses,
3677 : : &really_add_notes);
3678 : :
3679 : 1981595 : if (really_add_notes)
3680 : 2141 : debug_insn = -1;
3681 : : }
3682 : :
3683 : 3006893685 : FOR_EACH_INSN_INFO_USE (use, insn_info)
3684 : : {
3685 : 1353967525 : unsigned int uregno = DF_REF_REGNO (use);
3686 : :
3687 : 1353967525 : if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3688 : : {
3689 : : fprintf (dump_file, " regular looking at use ");
3690 : : df_ref_debug (use, dump_file);
3691 : : }
3692 : :
3693 : 1353967525 : if (!bitmap_bit_p (live, uregno))
3694 : : {
3695 : 672653054 : if (debug_insn)
3696 : : {
3697 : 180502 : if (debug_insn > 0)
3698 : : {
3699 : : /* We won't add REG_UNUSED or REG_DEAD notes for
3700 : : these, so we don't have to mess with them in
3701 : : debug insns either. */
3702 : 178361 : if (!bitmap_bit_p (artificial_uses, uregno)
3703 : 178361 : && !df_ignore_stack_reg (uregno))
3704 : 178333 : dead_debug_add (&debug, use, uregno);
3705 : 178361 : continue;
3706 : : }
3707 : : break;
3708 : : }
3709 : : else
3710 : 672472552 : dead_debug_insert_temp (&debug, uregno, insn,
3711 : : DEBUG_TEMP_BEFORE_WITH_REG);
3712 : :
3713 : 672472552 : if ( (!(DF_REF_FLAGS (use)
3714 : : & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3715 : 669852985 : && (!bitmap_bit_p (do_not_gen, uregno))
3716 : 531145887 : && (!bitmap_bit_p (artificial_uses, uregno))
3717 : 1203138085 : && (!df_ignore_stack_reg (uregno)))
3718 : : {
3719 : 530665533 : rtx reg = (DF_REF_LOC (use))
3720 : 530665533 : ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3721 : 530665533 : df_set_note (REG_DEAD, insn, reg);
3722 : :
3723 : 530665533 : if (REG_DEAD_DEBUGGING)
3724 : : df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3725 : : }
3726 : : /* This register is now live. */
3727 : 672472552 : bitmap_set_bit (live, uregno);
3728 : : }
3729 : : }
3730 : :
3731 : 1652928301 : df_remove_dead_eq_notes (insn, live);
3732 : :
3733 : 1652928301 : if (debug_insn == -1)
3734 : : {
3735 : : /* ??? We could probably do better here, replacing dead
3736 : : registers with their definitions. */
3737 : 2141 : INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3738 : 2141 : df_insn_rescan_debug_internal (insn);
3739 : : }
3740 : : }
3741 : :
3742 : 200301876 : dead_debug_local_finish (&debug, NULL);
3743 : 200301876 : }
3744 : :
3745 : :
3746 : : /* Compute register info: lifetime, bb, and number of defs and uses. */
3747 : : static void
3748 : 15228660 : df_note_compute (bitmap all_blocks)
3749 : : {
3750 : 15228660 : unsigned int bb_index;
3751 : 15228660 : bitmap_iterator bi;
3752 : 15228660 : bitmap_head live, do_not_gen, artificial_uses;
3753 : :
3754 : 15228660 : bitmap_initialize (&live, &df_bitmap_obstack);
3755 : 15228660 : bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3756 : 15228660 : bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3757 : :
3758 : 215530536 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3759 : : {
3760 : : /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3761 : : pseudos in debug insns because we don't always (re)visit blocks
3762 : : with death points after visiting dead uses. Even changing this
3763 : : loop to postorder would still leave room for visiting a death
3764 : : point before visiting a subsequent debug use. */
3765 : 200301876 : df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3766 : : }
3767 : :
3768 : 15228660 : bitmap_clear (&live);
3769 : 15228660 : bitmap_clear (&do_not_gen);
3770 : 15228660 : bitmap_clear (&artificial_uses);
3771 : 15228660 : }
3772 : :
3773 : :
3774 : : /* Free all storage associated with the problem. */
3775 : :
3776 : : static void
3777 : 10871033 : df_note_free (void)
3778 : : {
3779 : 10871033 : free (df_note);
3780 : 10871033 : }
3781 : :
3782 : :
3783 : : /* All of the information associated every instance of the problem. */
3784 : :
3785 : : static const struct df_problem problem_NOTE =
3786 : : {
3787 : : DF_NOTE, /* Problem id. */
3788 : : DF_NONE, /* Direction. */
3789 : : df_note_alloc, /* Allocate the problem specific data. */
3790 : : NULL, /* Reset global information. */
3791 : : NULL, /* Free basic block info. */
3792 : : df_note_compute, /* Local compute function. */
3793 : : NULL, /* Init the solution specific data. */
3794 : : NULL, /* Iterative solver. */
3795 : : NULL, /* Confluence operator 0. */
3796 : : NULL, /* Confluence operator n. */
3797 : : NULL, /* Transfer function. */
3798 : : NULL, /* Finalize function. */
3799 : : df_note_free, /* Free all of the problem information. */
3800 : : df_note_free, /* Remove this problem from the stack of dataflow problems. */
3801 : : NULL, /* Debugging. */
3802 : : NULL, /* Debugging start block. */
3803 : : NULL, /* Debugging end block. */
3804 : : NULL, /* Debugging start insn. */
3805 : : NULL, /* Debugging end insn. */
3806 : : NULL, /* Incremental solution verify start. */
3807 : : NULL, /* Incremental solution verify end. */
3808 : : &problem_LR, /* Dependent problem. */
3809 : : sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3810 : : TV_DF_NOTE, /* Timing variable. */
3811 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
3812 : : };
3813 : :
3814 : :
3815 : : /* Create a new DATAFLOW instance and add it to an existing instance
3816 : : of DF. The returned structure is what is used to get at the
3817 : : solution. */
3818 : :
3819 : : void
3820 : 11291742 : df_note_add_problem (void)
3821 : : {
3822 : 11291742 : df_add_problem (&problem_NOTE);
3823 : 11291742 : }
3824 : :
3825 : :
3826 : :
3827 : :
3828 : : /*----------------------------------------------------------------------------
3829 : : Functions for simulating the effects of single insns.
3830 : :
3831 : : You can either simulate in the forwards direction, starting from
3832 : : the top of a block or the backwards direction from the end of the
3833 : : block. If you go backwards, defs are examined first to clear bits,
3834 : : then uses are examined to set bits. If you go forwards, defs are
3835 : : examined first to set bits, then REG_DEAD and REG_UNUSED notes
3836 : : are examined to clear bits. In either case, the result of examining
3837 : : a def can be undone (respectively by a use or a REG_UNUSED note).
3838 : :
3839 : : If you start at the top of the block, use one of DF_LIVE_IN or
3840 : : DF_LR_IN. If you start at the bottom of the block use one of
3841 : : DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3842 : : THEY WILL BE DESTROYED.
3843 : : ----------------------------------------------------------------------------*/
3844 : :
3845 : :
3846 : : /* Find the set of DEFs for INSN. */
3847 : :
3848 : : void
3849 : 1910493 : df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3850 : : {
3851 : 1910493 : df_ref def;
3852 : :
3853 : 3375752 : FOR_EACH_INSN_DEF (def, insn)
3854 : 1465259 : bitmap_set_bit (defs, DF_REF_REGNO (def));
3855 : 1910493 : }
3856 : :
3857 : : /* Find the set of uses for INSN. This includes partial defs. */
3858 : :
3859 : : static void
3860 : 488321 : df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3861 : : {
3862 : 488321 : df_ref def, use;
3863 : 488321 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3864 : :
3865 : 1029732 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3866 : 541411 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3867 : 397 : bitmap_set_bit (uses, DF_REF_REGNO (def));
3868 : 820718 : FOR_EACH_INSN_INFO_USE (use, insn_info)
3869 : 332397 : bitmap_set_bit (uses, DF_REF_REGNO (use));
3870 : 488321 : }
3871 : :
3872 : : /* Find the set of real DEFs, which are not clobbers, for INSN. */
3873 : :
3874 : : void
3875 : 360510584 : df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3876 : : {
3877 : 360510584 : df_ref def;
3878 : :
3879 : 2035182730 : FOR_EACH_INSN_DEF (def, insn)
3880 : 1674672146 : if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3881 : 167507198 : bitmap_set_bit (defs, DF_REF_REGNO (def));
3882 : 360510584 : }
3883 : :
3884 : :
3885 : : /* Simulate the effects of the defs of INSN on LIVE. */
3886 : :
3887 : : void
3888 : 866830818 : df_simulate_defs (rtx_insn *insn, bitmap live)
3889 : : {
3890 : 866830818 : df_ref def;
3891 : :
3892 : 6949646534 : FOR_EACH_INSN_DEF (def, insn)
3893 : : {
3894 : 6082815716 : unsigned int dregno = DF_REF_REGNO (def);
3895 : :
3896 : : /* If the def is to only part of the reg, model it as a RMW operation
3897 : : by marking it live. It only kills the reg if it is a complete def. */
3898 : 6082815716 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3899 : 2772596 : bitmap_set_bit (live, dregno);
3900 : : else
3901 : 6080043120 : bitmap_clear_bit (live, dregno);
3902 : : }
3903 : 866830818 : }
3904 : :
3905 : :
3906 : : /* Simulate the effects of the uses of INSN on LIVE. */
3907 : :
3908 : : void
3909 : 863596027 : df_simulate_uses (rtx_insn *insn, bitmap live)
3910 : : {
3911 : 863596027 : df_ref use;
3912 : :
3913 : 863596027 : if (DEBUG_INSN_P (insn))
3914 : : return;
3915 : :
3916 : 1947275085 : FOR_EACH_INSN_USE (use, insn)
3917 : : /* Add use to set of uses in this BB. */
3918 : 1083679058 : bitmap_set_bit (live, DF_REF_REGNO (use));
3919 : : }
3920 : :
3921 : :
3922 : : /* Add back the always live regs in BB to LIVE. */
3923 : :
3924 : : static inline void
3925 : 363904972 : df_simulate_fixup_sets (basic_block bb, bitmap live)
3926 : : {
3927 : : /* These regs are considered always live so if they end up dying
3928 : : because of some def, we need to bring the back again. */
3929 : 363904972 : if (bb_has_eh_pred (bb))
3930 : 1447350 : bitmap_ior_into (live, &df->eh_block_artificial_uses);
3931 : : else
3932 : 362457622 : bitmap_ior_into (live, &df->regular_block_artificial_uses);
3933 : 363904972 : }
3934 : :
3935 : :
3936 : : /*----------------------------------------------------------------------------
3937 : : The following three functions are used only for BACKWARDS scanning:
3938 : : i.e. they process the defs before the uses.
3939 : :
3940 : : df_simulate_initialize_backwards should be called first with a
3941 : : bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3942 : : df_simulate_one_insn_backwards should be called for each insn in
3943 : : the block, starting with the last one. Finally,
3944 : : df_simulate_finalize_backwards can be called to get a new value
3945 : : of the sets at the top of the block (this is rarely used).
3946 : : ----------------------------------------------------------------------------*/
3947 : :
3948 : : /* Apply the artificial uses and defs at the end of BB in a backwards
3949 : : direction. */
3950 : :
3951 : : void
3952 : 161836803 : df_simulate_initialize_backwards (basic_block bb, bitmap live)
3953 : : {
3954 : 161836803 : df_ref def, use;
3955 : 161836803 : int bb_index = bb->index;
3956 : :
3957 : 330472583 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3958 : 6798977 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3959 : 0 : bitmap_clear_bit (live, DF_REF_REGNO (def));
3960 : :
3961 : 811135876 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3962 : 487462270 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3963 : 487462270 : bitmap_set_bit (live, DF_REF_REGNO (use));
3964 : 161836803 : }
3965 : :
3966 : :
3967 : : /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3968 : :
3969 : : void
3970 : 3798218 : df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3971 : : {
3972 : 3798218 : if (!NONDEBUG_INSN_P (insn))
3973 : : return;
3974 : :
3975 : 3394388 : df_simulate_defs (insn, live);
3976 : 3394388 : df_simulate_uses (insn, live);
3977 : 3394388 : df_simulate_fixup_sets (bb, live);
3978 : : }
3979 : :
3980 : :
3981 : : /* Apply the artificial uses and defs at the top of BB in a backwards
3982 : : direction. */
3983 : :
3984 : : void
3985 : 160574552 : df_simulate_finalize_backwards (basic_block bb, bitmap live)
3986 : : {
3987 : 160574552 : df_ref def;
3988 : : #ifdef EH_USES
3989 : : df_ref use;
3990 : : #endif
3991 : 160574552 : int bb_index = bb->index;
3992 : :
3993 : 327948081 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3994 : 6798977 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3995 : 6798977 : bitmap_clear_bit (live, DF_REF_REGNO (def));
3996 : :
3997 : : #ifdef EH_USES
3998 : : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3999 : : if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
4000 : : bitmap_set_bit (live, DF_REF_REGNO (use));
4001 : : #endif
4002 : 160574552 : }
4003 : : /*----------------------------------------------------------------------------
4004 : : The following three functions are used only for FORWARDS scanning:
4005 : : i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
4006 : : Thus it is important to add the DF_NOTES problem to the stack of
4007 : : problems computed before using these functions.
4008 : :
4009 : : df_simulate_initialize_forwards should be called first with a
4010 : : bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
4011 : : df_simulate_one_insn_forwards should be called for each insn in
4012 : : the block, starting with the first one.
4013 : : ----------------------------------------------------------------------------*/
4014 : :
4015 : : /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
4016 : : DF_LR_IN for basic block BB, for forward scanning by marking artificial
4017 : : defs live. */
4018 : :
4019 : : void
4020 : 45667359 : df_simulate_initialize_forwards (basic_block bb, bitmap live)
4021 : : {
4022 : 45667359 : df_ref def;
4023 : 45667359 : int bb_index = bb->index;
4024 : :
4025 : 127546413 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4026 : 36211695 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4027 : 1506064 : bitmap_set_bit (live, DF_REF_REGNO (def));
4028 : 45667359 : }
4029 : :
4030 : : /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4031 : :
4032 : : void
4033 : 360510584 : df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
4034 : : {
4035 : 360510584 : rtx link;
4036 : 360510584 : if (! INSN_P (insn))
4037 : : return;
4038 : :
4039 : : /* Make sure that DF_NOTE really is an active df problem. */
4040 : 360510584 : gcc_assert (df_note);
4041 : :
4042 : : /* Note that this is the opposite as how the problem is defined, because
4043 : : in the LR problem defs _kill_ liveness. However, they do so backwards,
4044 : : while here the scan is performed forwards! So, first assume that the
4045 : : def is live, and if this is not true REG_UNUSED notes will rectify the
4046 : : situation. */
4047 : 360510584 : df_simulate_find_noclobber_defs (insn, live);
4048 : :
4049 : : /* Clear all of the registers that go dead. */
4050 : 594100669 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4051 : : {
4052 : 233590085 : switch (REG_NOTE_KIND (link))
4053 : : {
4054 : 144541288 : case REG_DEAD:
4055 : 144541288 : case REG_UNUSED:
4056 : 144541288 : {
4057 : 144541288 : rtx reg = XEXP (link, 0);
4058 : 144541288 : bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
4059 : : }
4060 : 144541288 : break;
4061 : : default:
4062 : : break;
4063 : : }
4064 : : }
4065 : 360510584 : df_simulate_fixup_sets (bb, live);
4066 : : }
4067 : :
4068 : : /* Used by the next two functions to encode information about the
4069 : : memory references we found. */
4070 : : #define MEMREF_NORMAL 1
4071 : : #define MEMREF_VOLATILE 2
4072 : :
4073 : : /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
4074 : :
4075 : : static int
4076 : 1557290 : find_memory (rtx_insn *insn)
4077 : : {
4078 : 1557290 : int flags = 0;
4079 : 1557290 : subrtx_iterator::array_type array;
4080 : 11152708 : FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
4081 : : {
4082 : 9595418 : const_rtx x = *iter;
4083 : 9595418 : if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
4084 : 0 : flags |= MEMREF_VOLATILE;
4085 : 9595418 : else if (MEM_P (x))
4086 : : {
4087 : 151722 : if (MEM_VOLATILE_P (x))
4088 : 315 : flags |= MEMREF_VOLATILE;
4089 : 151407 : else if (!MEM_READONLY_P (x))
4090 : 145160 : flags |= MEMREF_NORMAL;
4091 : : }
4092 : : }
4093 : 1557290 : return flags;
4094 : 1557290 : }
4095 : :
4096 : : /* A subroutine of can_move_insns_across_p called through note_stores.
4097 : : DATA points to an integer in which we set either the bit for
4098 : : MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
4099 : : of either kind. */
4100 : :
4101 : : static void
4102 : 1617875 : find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4103 : : void *data ATTRIBUTE_UNUSED)
4104 : : {
4105 : 1617875 : int *pflags = (int *)data;
4106 : 1617875 : if (GET_CODE (x) == SUBREG)
4107 : 0 : x = XEXP (x, 0);
4108 : : /* Treat stores to SP as stores to memory, this will prevent problems
4109 : : when there are references to the stack frame. */
4110 : 1617875 : if (x == stack_pointer_rtx)
4111 : 2346 : *pflags |= MEMREF_VOLATILE;
4112 : 1617875 : if (!MEM_P (x))
4113 : : return;
4114 : 57699 : *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4115 : : }
4116 : :
4117 : : /* Scan BB backwards, using df_simulate functions to keep track of
4118 : : lifetimes, up to insn POINT. The result is stored in LIVE. */
4119 : :
4120 : : void
4121 : 648462 : simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4122 : : {
4123 : 648462 : rtx_insn *insn;
4124 : 648462 : bitmap_copy (live, df_get_live_out (bb));
4125 : 648462 : df_simulate_initialize_backwards (bb, live);
4126 : :
4127 : : /* Scan and update life information until we reach the point we're
4128 : : interested in. */
4129 : 1669057 : for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4130 : 1020595 : df_simulate_one_insn_backwards (bb, insn, live);
4131 : 648462 : }
4132 : :
4133 : : /* Return true if it is safe to move a group of insns, described by
4134 : : the range FROM to TO, backwards across another group of insns,
4135 : : described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4136 : : are no insns between ACROSS_TO and FROM, but they may be in
4137 : : different basic blocks; MERGE_BB is the block from which the
4138 : : insns will be moved. The caller must pass in a regset MERGE_LIVE
4139 : : which specifies the registers live after TO.
4140 : :
4141 : : This function may be called in one of two cases: either we try to
4142 : : move identical instructions from all successor blocks into their
4143 : : predecessor, or we try to move from only one successor block. If
4144 : : OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4145 : : the second case. It should contain a set of registers live at the
4146 : : end of ACROSS_TO which must not be clobbered by moving the insns.
4147 : : In that case, we're also more careful about moving memory references
4148 : : and trapping insns.
4149 : :
4150 : : We return false if it is not safe to move the entire group, but it
4151 : : may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4152 : : is set to point at the last moveable insn in such a case. */
4153 : :
4154 : : bool
4155 : 612818 : can_move_insns_across (rtx_insn *from, rtx_insn *to,
4156 : : rtx_insn *across_from, rtx_insn *across_to,
4157 : : basic_block merge_bb, regset merge_live,
4158 : : regset other_branch_live, rtx_insn **pmove_upto)
4159 : : {
4160 : 612818 : rtx_insn *insn, *next, *max_to;
4161 : 612818 : bitmap merge_set, merge_use, local_merge_live;
4162 : 612818 : bitmap test_set, test_use;
4163 : 612818 : unsigned i, fail = 0;
4164 : 612818 : bitmap_iterator bi;
4165 : 612818 : int memrefs_in_across = 0;
4166 : 612818 : int mem_sets_in_across = 0;
4167 : 612818 : bool trapping_insns_in_across = false;
4168 : :
4169 : 612818 : if (pmove_upto != NULL)
4170 : 153836 : *pmove_upto = NULL;
4171 : :
4172 : : /* Find real bounds, ignoring debug insns. */
4173 : 619019 : while (!NONDEBUG_INSN_P (from) && from != to)
4174 : 6201 : from = NEXT_INSN (from);
4175 : 613864 : while (!NONDEBUG_INSN_P (to) && from != to)
4176 : 1046 : to = PREV_INSN (to);
4177 : :
4178 : : for (insn = across_to; ; insn = next)
4179 : : {
4180 : 1185525 : if (CALL_P (insn))
4181 : : {
4182 : 1345 : if (RTL_CONST_OR_PURE_CALL_P (insn))
4183 : : /* Pure functions can read from memory. Const functions can
4184 : : read from arguments that the ABI has forced onto the stack.
4185 : : Neither sort of read can be volatile. */
4186 : 361 : memrefs_in_across |= MEMREF_NORMAL;
4187 : : else
4188 : : {
4189 : 984 : memrefs_in_across |= MEMREF_VOLATILE;
4190 : 984 : mem_sets_in_across |= MEMREF_VOLATILE;
4191 : : }
4192 : : }
4193 : 1185525 : if (NONDEBUG_INSN_P (insn))
4194 : : {
4195 : 1172863 : if (volatile_insn_p (PATTERN (insn)))
4196 : : return false;
4197 : 1172862 : memrefs_in_across |= find_memory (insn);
4198 : 1172862 : note_stores (insn, find_memory_stores, &mem_sets_in_across);
4199 : : /* This is used just to find sets of the stack pointer. */
4200 : 1172862 : memrefs_in_across |= mem_sets_in_across;
4201 : 1172862 : trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4202 : : }
4203 : 1185524 : next = PREV_INSN (insn);
4204 : 1185524 : if (insn == across_from)
4205 : : break;
4206 : : }
4207 : :
4208 : : /* Collect:
4209 : : MERGE_SET = set of registers set in MERGE_BB
4210 : : MERGE_USE = set of registers used in MERGE_BB and live at its top
4211 : : MERGE_LIVE = set of registers live at the point inside the MERGE
4212 : : range that we've reached during scanning
4213 : : TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4214 : : TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4215 : : and live before ACROSS_FROM. */
4216 : :
4217 : 612817 : merge_set = BITMAP_ALLOC (®_obstack);
4218 : 612817 : merge_use = BITMAP_ALLOC (®_obstack);
4219 : 612817 : local_merge_live = BITMAP_ALLOC (®_obstack);
4220 : 612817 : test_set = BITMAP_ALLOC (®_obstack);
4221 : 612817 : test_use = BITMAP_ALLOC (®_obstack);
4222 : :
4223 : : /* Compute the set of registers set and used in the ACROSS range. */
4224 : 612817 : if (other_branch_live != NULL)
4225 : 458982 : bitmap_copy (test_use, other_branch_live);
4226 : 612817 : df_simulate_initialize_backwards (merge_bb, test_use);
4227 : 612817 : for (insn = across_to; ; insn = next)
4228 : : {
4229 : 1185524 : if (NONDEBUG_INSN_P (insn))
4230 : : {
4231 : 1172862 : df_simulate_find_defs (insn, test_set);
4232 : 1172862 : df_simulate_defs (insn, test_use);
4233 : 1172862 : df_simulate_uses (insn, test_use);
4234 : : }
4235 : 1185524 : next = PREV_INSN (insn);
4236 : 1185524 : if (insn == across_from)
4237 : : break;
4238 : : }
4239 : :
4240 : : /* Compute an upper bound for the amount of insns moved, by finding
4241 : : the first insn in MERGE that sets a register in TEST_USE, or uses
4242 : : a register in TEST_SET. We also check for calls, trapping operations,
4243 : : and memory references. */
4244 : : max_to = NULL;
4245 : : for (insn = from; ; insn = next)
4246 : : {
4247 : 688863 : if (CALL_P (insn))
4248 : : break;
4249 : 674971 : if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4250 : : break;
4251 : 674971 : if (NONDEBUG_INSN_P (insn))
4252 : : {
4253 : 659049 : if (may_trap_or_fault_p (PATTERN (insn))
4254 : 659049 : && (trapping_insns_in_across
4255 : 149416 : || other_branch_live != NULL
4256 : 7434 : || volatile_insn_p (PATTERN (insn))))
4257 : : break;
4258 : :
4259 : : /* We cannot move memory stores past each other, or move memory
4260 : : reads past stores, at least not without tracking them and
4261 : : calling true_dependence on every pair.
4262 : :
4263 : : If there is no other branch and no memory references or
4264 : : sets in the ACROSS range, we can move memory references
4265 : : freely, even volatile ones.
4266 : :
4267 : : Otherwise, the rules are as follows: volatile memory
4268 : : references and stores can't be moved at all, and any type
4269 : : of memory reference can't be moved if there are volatile
4270 : : accesses or stores in the ACROSS range. That leaves
4271 : : normal reads, which can be moved, as the trapping case is
4272 : : dealt with elsewhere. */
4273 : 516954 : if (other_branch_live != NULL || memrefs_in_across != 0)
4274 : : {
4275 : 384428 : int mem_ref_flags = 0;
4276 : 384428 : int mem_set_flags = 0;
4277 : 384428 : note_stores (insn, find_memory_stores, &mem_set_flags);
4278 : 384428 : mem_ref_flags = find_memory (insn);
4279 : : /* Catch sets of the stack pointer. */
4280 : 384428 : mem_ref_flags |= mem_set_flags;
4281 : :
4282 : 384428 : if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4283 : : break;
4284 : 382204 : if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4285 : : break;
4286 : 381842 : if (mem_set_flags != 0
4287 : 355915 : || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4288 : : break;
4289 : : }
4290 : 488321 : df_simulate_find_uses (insn, merge_use);
4291 : : /* We're only interested in uses which use a value live at
4292 : : the top, not one previously set in this block. */
4293 : 488321 : bitmap_and_compl_into (merge_use, merge_set);
4294 : 488321 : df_simulate_find_defs (insn, merge_set);
4295 : 488321 : if (bitmap_intersect_p (merge_set, test_use)
4296 : 488321 : || bitmap_intersect_p (merge_use, test_set))
4297 : : break;
4298 : : max_to = insn;
4299 : : }
4300 : 349397 : next = NEXT_INSN (insn);
4301 : 349397 : if (insn == to)
4302 : : break;
4303 : : }
4304 : 612817 : if (max_to != to)
4305 : 339502 : fail = 1;
4306 : :
4307 : 612817 : if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4308 : 335678 : goto out;
4309 : :
4310 : : /* Now, lower this upper bound by also taking into account that
4311 : : a range of insns moved across ACROSS must not leave a register
4312 : : live at the end that will be clobbered in ACROSS. We need to
4313 : : find a point where TEST_SET & LIVE == 0.
4314 : :
4315 : : Insns in the MERGE range that set registers which are also set
4316 : : in the ACROSS range may still be moved as long as we also move
4317 : : later insns which use the results of the set, and make the
4318 : : register dead again. This is verified by the condition stated
4319 : : above. We only need to test it for registers that are set in
4320 : : the moved region.
4321 : :
4322 : : MERGE_LIVE is provided by the caller and holds live registers after
4323 : : TO. */
4324 : 277139 : bitmap_copy (local_merge_live, merge_live);
4325 : 571834 : for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4326 : 17556 : df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4327 : :
4328 : : /* We're not interested in registers that aren't set in the moved
4329 : : region at all. */
4330 : 277139 : bitmap_and_into (local_merge_live, merge_set);
4331 : 2132 : for (;;)
4332 : : {
4333 : 279271 : if (NONDEBUG_INSN_P (insn))
4334 : : {
4335 : 278544 : if (!bitmap_intersect_p (test_set, local_merge_live))
4336 : : {
4337 : 235466 : max_to = insn;
4338 : 235466 : break;
4339 : : }
4340 : :
4341 : 43078 : df_simulate_one_insn_backwards (merge_bb, insn,
4342 : : local_merge_live);
4343 : : }
4344 : 43805 : if (insn == from)
4345 : : {
4346 : 41673 : fail = 1;
4347 : 41673 : goto out;
4348 : : }
4349 : 2132 : insn = PREV_INSN (insn);
4350 : : }
4351 : :
4352 : 235466 : if (max_to != to)
4353 : 4334 : fail = 1;
4354 : :
4355 : 235466 : if (pmove_upto)
4356 : 35117 : *pmove_upto = max_to;
4357 : :
4358 : : /* For small register class machines, don't lengthen lifetimes of
4359 : : hard registers before reload. */
4360 : 235466 : if (! reload_completed
4361 : 235466 : && targetm.small_register_classes_for_mode_p (VOIDmode))
4362 : : {
4363 : 378308 : EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4364 : : {
4365 : 206856 : if (i < FIRST_PSEUDO_REGISTER
4366 : 10240 : && ! fixed_regs[i]
4367 : 0 : && ! global_regs[i])
4368 : : {
4369 : : fail = 1;
4370 : : break;
4371 : : }
4372 : : }
4373 : : }
4374 : :
4375 : 612817 : out:
4376 : 612817 : BITMAP_FREE (merge_set);
4377 : 612817 : BITMAP_FREE (merge_use);
4378 : 612817 : BITMAP_FREE (local_merge_live);
4379 : 612817 : BITMAP_FREE (test_set);
4380 : 612817 : BITMAP_FREE (test_use);
4381 : :
4382 : 612817 : return !fail;
4383 : : }
4384 : :
4385 : :
4386 : : /*----------------------------------------------------------------------------
4387 : : MULTIPLE DEFINITIONS
4388 : :
4389 : : Find the locations in the function reached by multiple definition sites
4390 : : for a live pseudo. In and out bitvectors are built for each basic
4391 : : block. They are restricted for efficiency to live registers.
4392 : :
4393 : : The gen and kill sets for the problem are obvious. Together they
4394 : : include all defined registers in a basic block; the gen set includes
4395 : : registers where a partial or conditional or may-clobber definition is
4396 : : last in the BB, while the kill set includes registers with a complete
4397 : : definition coming last. However, the computation of the dataflow
4398 : : itself is interesting.
4399 : :
4400 : : The idea behind it comes from SSA form's iterated dominance frontier
4401 : : criterion for inserting PHI functions. Just like in that case, we can use
4402 : : the dominance frontier to find places where multiple definitions meet;
4403 : : a register X defined in a basic block BB1 has multiple definitions in
4404 : : basic blocks in BB1's dominance frontier.
4405 : :
4406 : : So, the in-set of a basic block BB2 is not just the union of the
4407 : : out-sets of BB2's predecessors, but includes some more bits that come
4408 : : from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4409 : : the previous paragraph). I called this set the init-set of BB2.
4410 : :
4411 : : (Note: I actually use the kill-set only to build the init-set.
4412 : : gen bits are anyway propagated from BB1 to BB2 by dataflow).
4413 : :
4414 : : For example, if you have
4415 : :
4416 : : BB1 : r10 = 0
4417 : : r11 = 0
4418 : : if <...> goto BB2 else goto BB3;
4419 : :
4420 : : BB2 : r10 = 1
4421 : : r12 = 1
4422 : : goto BB3;
4423 : :
4424 : : BB3 :
4425 : :
4426 : : you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4427 : : init-set of BB3 includes r10 and r12, but not r11. Note that we do
4428 : : not need to iterate the dominance frontier, because we do not insert
4429 : : anything like PHI functions there! Instead, dataflow will take care of
4430 : : propagating the information to BB3's successors.
4431 : : ---------------------------------------------------------------------------*/
4432 : :
4433 : : /* Private data used to verify the solution for this problem. */
4434 : : struct df_md_problem_data
4435 : : {
4436 : : /* An obstack for the bitmaps we need for this problem. */
4437 : : bitmap_obstack md_bitmaps;
4438 : : };
4439 : :
4440 : : /* Scratch var used by transfer functions. This is used to do md analysis
4441 : : only for live registers. */
4442 : : static bitmap_head df_md_scratch;
4443 : :
4444 : :
4445 : : static void
4446 : 0 : df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4447 : : void *vbb_info)
4448 : : {
4449 : 0 : class df_md_bb_info *bb_info = (class df_md_bb_info *) vbb_info;
4450 : 0 : if (bb_info)
4451 : : {
4452 : 0 : bitmap_clear (&bb_info->kill);
4453 : 0 : bitmap_clear (&bb_info->gen);
4454 : 0 : bitmap_clear (&bb_info->init);
4455 : 0 : bitmap_clear (&bb_info->in);
4456 : 0 : bitmap_clear (&bb_info->out);
4457 : : }
4458 : 0 : }
4459 : :
4460 : :
4461 : : /* Allocate or reset bitmaps for DF_MD. The solution bits are
4462 : : not touched unless the block is new. */
4463 : :
4464 : : static void
4465 : 0 : df_md_alloc (bitmap all_blocks)
4466 : : {
4467 : 0 : unsigned int bb_index;
4468 : 0 : bitmap_iterator bi;
4469 : 0 : struct df_md_problem_data *problem_data;
4470 : :
4471 : 0 : df_grow_bb_info (df_md);
4472 : 0 : if (df_md->problem_data)
4473 : : problem_data = (struct df_md_problem_data *) df_md->problem_data;
4474 : : else
4475 : : {
4476 : 0 : problem_data = XNEW (struct df_md_problem_data);
4477 : 0 : df_md->problem_data = problem_data;
4478 : 0 : bitmap_obstack_initialize (&problem_data->md_bitmaps);
4479 : : }
4480 : 0 : bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4481 : :
4482 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4483 : : {
4484 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4485 : : /* When bitmaps are already initialized, just clear them. */
4486 : 0 : if (bb_info->init.obstack)
4487 : : {
4488 : 0 : bitmap_clear (&bb_info->init);
4489 : 0 : bitmap_clear (&bb_info->gen);
4490 : 0 : bitmap_clear (&bb_info->kill);
4491 : 0 : bitmap_clear (&bb_info->in);
4492 : 0 : bitmap_clear (&bb_info->out);
4493 : : }
4494 : : else
4495 : : {
4496 : 0 : bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4497 : 0 : bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4498 : 0 : bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4499 : 0 : bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4500 : 0 : bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4501 : : }
4502 : : }
4503 : :
4504 : 0 : df_md->optional_p = true;
4505 : 0 : }
4506 : :
4507 : : /* Add the effect of the top artificial defs of BB to the multiple definitions
4508 : : bitmap LOCAL_MD. */
4509 : :
4510 : : void
4511 : 0 : df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4512 : : {
4513 : 0 : int bb_index = bb->index;
4514 : 0 : df_ref def;
4515 : 0 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4516 : 0 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4517 : : {
4518 : 0 : unsigned int dregno = DF_REF_REGNO (def);
4519 : 0 : if (DF_REF_FLAGS (def)
4520 : : & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4521 : 0 : bitmap_set_bit (local_md, dregno);
4522 : : else
4523 : 0 : bitmap_clear_bit (local_md, dregno);
4524 : : }
4525 : 0 : }
4526 : :
4527 : :
4528 : : /* Add the effect of the defs of INSN to the reaching definitions bitmap
4529 : : LOCAL_MD. */
4530 : :
4531 : : void
4532 : 0 : df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4533 : : bitmap local_md)
4534 : : {
4535 : 0 : df_ref def;
4536 : :
4537 : 0 : FOR_EACH_INSN_DEF (def, insn)
4538 : : {
4539 : 0 : unsigned int dregno = DF_REF_REGNO (def);
4540 : 0 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4541 : 0 : || (dregno >= FIRST_PSEUDO_REGISTER))
4542 : : {
4543 : 0 : if (DF_REF_FLAGS (def)
4544 : : & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4545 : 0 : bitmap_set_bit (local_md, DF_REF_ID (def));
4546 : : else
4547 : 0 : bitmap_clear_bit (local_md, DF_REF_ID (def));
4548 : : }
4549 : : }
4550 : 0 : }
4551 : :
4552 : : static void
4553 : 0 : df_md_bb_local_compute_process_def (class df_md_bb_info *bb_info,
4554 : : df_ref def,
4555 : : int top_flag)
4556 : : {
4557 : 0 : bitmap_clear (&seen_in_insn);
4558 : :
4559 : 0 : for (; def; def = DF_REF_NEXT_LOC (def))
4560 : : {
4561 : 0 : unsigned int dregno = DF_REF_REGNO (def);
4562 : 0 : if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4563 : 0 : || (dregno >= FIRST_PSEUDO_REGISTER))
4564 : 0 : && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4565 : : {
4566 : 0 : if (!bitmap_bit_p (&seen_in_insn, dregno))
4567 : : {
4568 : 0 : if (DF_REF_FLAGS (def)
4569 : : & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4570 : : {
4571 : 0 : bitmap_set_bit (&bb_info->gen, dregno);
4572 : 0 : bitmap_clear_bit (&bb_info->kill, dregno);
4573 : : }
4574 : : else
4575 : : {
4576 : : /* When we find a clobber and a regular def,
4577 : : make sure the regular def wins. */
4578 : 0 : bitmap_set_bit (&seen_in_insn, dregno);
4579 : 0 : bitmap_set_bit (&bb_info->kill, dregno);
4580 : 0 : bitmap_clear_bit (&bb_info->gen, dregno);
4581 : : }
4582 : : }
4583 : : }
4584 : : }
4585 : 0 : }
4586 : :
4587 : :
4588 : : /* Compute local multiple def info for basic block BB. */
4589 : :
4590 : : static void
4591 : 0 : df_md_bb_local_compute (unsigned int bb_index)
4592 : : {
4593 : 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4594 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4595 : 0 : rtx_insn *insn;
4596 : :
4597 : : /* Artificials are only hard regs. */
4598 : 0 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
4599 : 0 : df_md_bb_local_compute_process_def (bb_info,
4600 : : df_get_artificial_defs (bb_index),
4601 : : DF_REF_AT_TOP);
4602 : :
4603 : 0 : FOR_BB_INSNS (bb, insn)
4604 : : {
4605 : 0 : unsigned int uid = INSN_UID (insn);
4606 : 0 : if (!INSN_P (insn))
4607 : 0 : continue;
4608 : :
4609 : 0 : df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4610 : : }
4611 : :
4612 : 0 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
4613 : 0 : df_md_bb_local_compute_process_def (bb_info,
4614 : : df_get_artificial_defs (bb_index),
4615 : : 0);
4616 : 0 : }
4617 : :
4618 : : /* Compute local reaching def info for each basic block within BLOCKS. */
4619 : :
4620 : : static void
4621 : 0 : df_md_local_compute (bitmap all_blocks)
4622 : : {
4623 : 0 : unsigned int bb_index, df_bb_index;
4624 : 0 : bitmap_iterator bi1, bi2;
4625 : 0 : basic_block bb;
4626 : 0 : bitmap_head *frontiers;
4627 : :
4628 : 0 : bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4629 : :
4630 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4631 : : {
4632 : 0 : df_md_bb_local_compute (bb_index);
4633 : : }
4634 : :
4635 : 0 : bitmap_release (&seen_in_insn);
4636 : :
4637 : 0 : frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4638 : 0 : FOR_ALL_BB_FN (bb, cfun)
4639 : 0 : bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4640 : :
4641 : 0 : compute_dominance_frontiers (frontiers);
4642 : :
4643 : : /* Add each basic block's kills to the nodes in the frontier of the BB. */
4644 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4645 : : {
4646 : 0 : bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4647 : 0 : EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4648 : : {
4649 : 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4650 : 0 : if (bitmap_bit_p (all_blocks, df_bb_index))
4651 : 0 : bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4652 : 0 : df_get_live_in (bb));
4653 : : }
4654 : : }
4655 : :
4656 : 0 : FOR_ALL_BB_FN (bb, cfun)
4657 : 0 : bitmap_clear (&frontiers[bb->index]);
4658 : 0 : free (frontiers);
4659 : 0 : }
4660 : :
4661 : :
4662 : : /* Reset the global solution for recalculation. */
4663 : :
4664 : : static void
4665 : 0 : df_md_reset (bitmap all_blocks)
4666 : : {
4667 : 0 : unsigned int bb_index;
4668 : 0 : bitmap_iterator bi;
4669 : :
4670 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4671 : : {
4672 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4673 : 0 : gcc_assert (bb_info);
4674 : 0 : bitmap_clear (&bb_info->in);
4675 : 0 : bitmap_clear (&bb_info->out);
4676 : : }
4677 : 0 : }
4678 : :
4679 : : static bool
4680 : 0 : df_md_transfer_function (int bb_index)
4681 : : {
4682 : 0 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4683 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4684 : 0 : bitmap in = &bb_info->in;
4685 : 0 : bitmap out = &bb_info->out;
4686 : 0 : bitmap gen = &bb_info->gen;
4687 : 0 : bitmap kill = &bb_info->kill;
4688 : :
4689 : : /* We need to use a scratch set here so that the value returned from this
4690 : : function invocation properly reflects whether the sets changed in a
4691 : : significant way; i.e. not just because the live set was anded in. */
4692 : 0 : bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4693 : :
4694 : : /* Multiple definitions of a register are not relevant if it is not
4695 : : live. Thus we trim the result to the places where it is live. */
4696 : 0 : bitmap_and_into (in, df_get_live_in (bb));
4697 : :
4698 : 0 : return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4699 : : }
4700 : :
4701 : : /* Initialize the solution bit vectors for problem. */
4702 : :
4703 : : static void
4704 : 0 : df_md_init (bitmap all_blocks)
4705 : : {
4706 : 0 : unsigned int bb_index;
4707 : 0 : bitmap_iterator bi;
4708 : :
4709 : 0 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4710 : : {
4711 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4712 : :
4713 : 0 : bitmap_copy (&bb_info->in, &bb_info->init);
4714 : 0 : df_md_transfer_function (bb_index);
4715 : : }
4716 : 0 : }
4717 : :
4718 : : static void
4719 : 0 : df_md_confluence_0 (basic_block bb)
4720 : : {
4721 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4722 : 0 : bitmap_copy (&bb_info->in, &bb_info->init);
4723 : 0 : }
4724 : :
4725 : : /* In of target gets or of out of source. */
4726 : :
4727 : : static bool
4728 : 0 : df_md_confluence_n (edge e)
4729 : : {
4730 : 0 : bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4731 : 0 : bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4732 : :
4733 : 0 : if (e->flags & EDGE_FAKE)
4734 : : return false;
4735 : :
4736 : 0 : if (e->flags & EDGE_EH)
4737 : : {
4738 : : /* Conservatively treat partially-clobbered registers as surviving
4739 : : across the edge; they might or might not, depending on what mode
4740 : : they have. */
4741 : 0 : bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
4742 : 0 : return bitmap_ior_and_compl_into (op1, op2, eh_kills);
4743 : : }
4744 : : else
4745 : 0 : return bitmap_ior_into (op1, op2);
4746 : : }
4747 : :
4748 : : /* Free all storage associated with the problem. */
4749 : :
4750 : : static void
4751 : 0 : df_md_free (void)
4752 : : {
4753 : 0 : struct df_md_problem_data *problem_data
4754 : 0 : = (struct df_md_problem_data *) df_md->problem_data;
4755 : :
4756 : 0 : bitmap_release (&df_md_scratch);
4757 : 0 : bitmap_obstack_release (&problem_data->md_bitmaps);
4758 : 0 : free (problem_data);
4759 : 0 : df_md->problem_data = NULL;
4760 : :
4761 : 0 : df_md->block_info_size = 0;
4762 : 0 : free (df_md->block_info);
4763 : 0 : df_md->block_info = NULL;
4764 : 0 : free (df_md);
4765 : 0 : }
4766 : :
4767 : :
4768 : : /* Debugging info at top of bb. */
4769 : :
4770 : : static void
4771 : 0 : df_md_top_dump (basic_block bb, FILE *file)
4772 : : {
4773 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4774 : 0 : if (!bb_info)
4775 : : return;
4776 : :
4777 : 0 : fprintf (file, ";; md in \t");
4778 : 0 : df_print_regset (file, &bb_info->in);
4779 : 0 : fprintf (file, ";; md init \t");
4780 : 0 : df_print_regset (file, &bb_info->init);
4781 : 0 : fprintf (file, ";; md gen \t");
4782 : 0 : df_print_regset (file, &bb_info->gen);
4783 : 0 : fprintf (file, ";; md kill \t");
4784 : 0 : df_print_regset (file, &bb_info->kill);
4785 : : }
4786 : :
4787 : : /* Debugging info at bottom of bb. */
4788 : :
4789 : : static void
4790 : 0 : df_md_bottom_dump (basic_block bb, FILE *file)
4791 : : {
4792 : 0 : class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4793 : 0 : if (!bb_info)
4794 : : return;
4795 : :
4796 : 0 : fprintf (file, ";; md out \t");
4797 : 0 : df_print_regset (file, &bb_info->out);
4798 : : }
4799 : :
4800 : : static const struct df_problem problem_MD =
4801 : : {
4802 : : DF_MD, /* Problem id. */
4803 : : DF_FORWARD, /* Direction. */
4804 : : df_md_alloc, /* Allocate the problem specific data. */
4805 : : df_md_reset, /* Reset global information. */
4806 : : df_md_free_bb_info, /* Free basic block info. */
4807 : : df_md_local_compute, /* Local compute function. */
4808 : : df_md_init, /* Init the solution specific data. */
4809 : : df_worklist_dataflow, /* Worklist solver. */
4810 : : df_md_confluence_0, /* Confluence operator 0. */
4811 : : df_md_confluence_n, /* Confluence operator n. */
4812 : : df_md_transfer_function, /* Transfer function. */
4813 : : NULL, /* Finalize function. */
4814 : : df_md_free, /* Free all of the problem information. */
4815 : : df_md_free, /* Remove this problem from the stack of dataflow problems. */
4816 : : NULL, /* Debugging. */
4817 : : df_md_top_dump, /* Debugging start block. */
4818 : : df_md_bottom_dump, /* Debugging end block. */
4819 : : NULL, /* Debugging start insn. */
4820 : : NULL, /* Debugging end insn. */
4821 : : NULL, /* Incremental solution verify start. */
4822 : : NULL, /* Incremental solution verify end. */
4823 : : NULL, /* Dependent problem. */
4824 : : sizeof (class df_md_bb_info),/* Size of entry of block_info array. */
4825 : : TV_DF_MD, /* Timing variable. */
4826 : : false /* Reset blocks on dropping out of blocks_to_analyze. */
4827 : : };
4828 : :
4829 : : /* Create a new MD instance and add it to the existing instance
4830 : : of DF. */
4831 : :
4832 : : void
4833 : 0 : df_md_add_problem (void)
4834 : : {
4835 : 0 : df_add_problem (&problem_MD);
4836 : 0 : }
4837 : :
4838 : :
4839 : :
|
