Line data Source code
1 : /* Standard problems for dataflow support routines.
2 : Copyright (C) 1999-2026 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 27892 : df_chain_dump (struct df_link *link, FILE *file)
63 : {
64 27892 : fprintf (file, "{ ");
65 58769 : 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 27892 : fprintf (file, "}");
77 27892 : }
78 :
79 :
80 : /* Print some basic block info as part of df_dump. */
81 :
82 : void
83 4170 : df_print_bb_index (basic_block bb, FILE *file)
84 : {
85 4170 : edge e;
86 4170 : edge_iterator ei;
87 :
88 4170 : fprintf (file, "\n( ");
89 9400 : FOR_EACH_EDGE (e, ei, bb->preds)
90 : {
91 5230 : basic_block pred = e->src;
92 10460 : fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
93 : }
94 4170 : fprintf (file, ")->[%d]->( ", bb->index);
95 9400 : FOR_EACH_EDGE (e, ei, bb->succs)
96 : {
97 5230 : basic_block succ = e->dest;
98 10460 : fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
99 : }
100 4170 : fprintf (file, ")\n");
101 4170 : }
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 3659209 : df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
164 : void *vbb_info)
165 : {
166 3659209 : class df_rd_bb_info *bb_info = (class df_rd_bb_info *) vbb_info;
167 3659209 : if (bb_info)
168 : {
169 3659209 : bitmap_clear (&bb_info->kill);
170 3659209 : bitmap_clear (&bb_info->sparse_kill);
171 3659209 : bitmap_clear (&bb_info->gen);
172 3659209 : bitmap_clear (&bb_info->in);
173 3659209 : bitmap_clear (&bb_info->out);
174 : }
175 3659209 : }
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 6009284 : df_rd_alloc (bitmap all_blocks)
183 : {
184 6009284 : unsigned int bb_index;
185 6009284 : bitmap_iterator bi;
186 6009284 : class df_rd_problem_data *problem_data;
187 :
188 6009284 : if (df_rd->problem_data)
189 : {
190 910387 : problem_data = (class df_rd_problem_data *) df_rd->problem_data;
191 910387 : bitmap_clear (&problem_data->sparse_invalidated_by_eh);
192 910387 : bitmap_clear (&problem_data->dense_invalidated_by_eh);
193 : }
194 : else
195 : {
196 5098897 : problem_data = XNEW (class df_rd_problem_data);
197 5098897 : df_rd->problem_data = problem_data;
198 :
199 5098897 : bitmap_obstack_initialize (&problem_data->rd_bitmaps);
200 5098897 : bitmap_initialize (&problem_data->sparse_invalidated_by_eh,
201 : &problem_data->rd_bitmaps);
202 5098897 : bitmap_initialize (&problem_data->dense_invalidated_by_eh,
203 : &problem_data->rd_bitmaps);
204 : }
205 :
206 6009284 : 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 73036559 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
212 : {
213 67027275 : 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 67027275 : if (bb_info->kill.obstack)
217 : {
218 1456350 : bitmap_clear (&bb_info->kill);
219 1456350 : bitmap_clear (&bb_info->sparse_kill);
220 1456350 : bitmap_clear (&bb_info->gen);
221 : }
222 : else
223 : {
224 65570925 : bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
225 65570925 : bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
226 65570925 : bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
227 65570925 : bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
228 65570925 : bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
229 : }
230 : }
231 6009284 : df_rd->optional_p = true;
232 6009284 : }
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 67027275 : df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
240 : {
241 67027275 : int bb_index = bb->index;
242 67027275 : df_ref def;
243 217113286 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
244 83058736 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
245 : {
246 1801247 : unsigned int dregno = DF_REF_REGNO (def);
247 1801247 : if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
248 1801247 : bitmap_clear_range (local_rd,
249 1801247 : DF_DEFS_BEGIN (dregno),
250 1801247 : DF_DEFS_COUNT (dregno));
251 1801247 : bitmap_set_bit (local_rd, DF_REF_ID (def));
252 : }
253 67027275 : }
254 :
255 : /* Add the effect of the defs of INSN to the reaching definitions bitmap
256 : LOCAL_RD. */
257 :
258 : void
259 578189377 : df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
260 : bitmap local_rd)
261 : {
262 578189377 : df_ref def;
263 :
264 2682995044 : FOR_EACH_INSN_DEF (def, insn)
265 : {
266 2104805667 : unsigned int dregno = DF_REF_REGNO (def);
267 2104805667 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
268 15480092 : || (dregno >= FIRST_PSEUDO_REGISTER))
269 : {
270 2091141430 : if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
271 2090470436 : bitmap_clear_range (local_rd,
272 2090470436 : DF_DEFS_BEGIN (dregno),
273 2090470436 : DF_DEFS_COUNT (dregno));
274 2091141430 : if (!(DF_REF_FLAGS (def)
275 : & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
276 221277454 : bitmap_set_bit (local_rd, DF_REF_ID (def));
277 : }
278 : }
279 578189377 : }
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 711096325 : df_rd_bb_local_compute_process_def (class df_rd_bb_info *bb_info,
288 : df_ref def,
289 : int top_flag)
290 : {
291 2981169800 : for (; def; def = DF_REF_NEXT_LOC (def))
292 : {
293 2270073475 : if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
294 : {
295 2187439571 : unsigned int regno = DF_REF_REGNO (def);
296 2187439571 : unsigned int begin = DF_DEFS_BEGIN (regno);
297 2187439571 : unsigned int n_defs = DF_DEFS_COUNT (regno);
298 :
299 2187439571 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
300 15480092 : || (regno >= FIRST_PSEUDO_REGISTER))
301 : {
302 : /* Only the last def(s) for a regno in the block has any
303 : effect. */
304 2173775334 : 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 1578760238 : 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 1578760238 : && (!(DF_REF_FLAGS (def) &
312 : (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
313 : {
314 234104378 : if (n_defs > DF_SPARSE_THRESHOLD)
315 : {
316 40925865 : bitmap_set_bit (&bb_info->sparse_kill, regno);
317 40925865 : bitmap_clear_range (&bb_info->gen, begin, n_defs);
318 : }
319 : else
320 : {
321 193178513 : bitmap_set_range (&bb_info->kill, begin, n_defs);
322 193178513 : bitmap_clear_range (&bb_info->gen, begin, n_defs);
323 : }
324 : }
325 :
326 1578760238 : bitmap_set_bit (&seen_in_insn, regno);
327 : /* All defs for regno in the instruction may be put into
328 : the gen set. */
329 1578760238 : if (!(DF_REF_FLAGS (def)
330 : & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
331 227308544 : bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
332 : }
333 : }
334 : }
335 : }
336 711096325 : }
337 :
338 : /* Compute local reaching def info for basic block BB. */
339 :
340 : static void
341 67027275 : df_rd_bb_local_compute (unsigned int bb_index)
342 : {
343 67027275 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
344 67027275 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
345 67027275 : rtx_insn *insn;
346 :
347 67027275 : bitmap_clear (&seen_in_block);
348 67027275 : bitmap_clear (&seen_in_insn);
349 :
350 : /* Artificials are only hard regs. */
351 67027275 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
352 132906948 : df_rd_bb_local_compute_process_def (bb_info,
353 : df_get_artificial_defs (bb_index),
354 : 0);
355 :
356 753083342 : FOR_BB_INSNS_REVERSE (bb, insn)
357 : {
358 686056067 : unsigned int uid = INSN_UID (insn);
359 :
360 686056067 : if (!INSN_P (insn))
361 107866690 : continue;
362 :
363 578189377 : df_rd_bb_local_compute_process_def (bb_info,
364 578189377 : 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 578189377 : bitmap_ior_into (&seen_in_block, &seen_in_insn);
373 578189377 : 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 67027275 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
380 132906948 : df_rd_bb_local_compute_process_def (bb_info,
381 : df_get_artificial_defs (bb_index),
382 : DF_REF_AT_TOP);
383 67027275 : }
384 :
385 :
386 : /* Compute local reaching def info for each basic block within BLOCKS. */
387 :
388 : static void
389 6009284 : df_rd_local_compute (bitmap all_blocks)
390 : {
391 6009284 : unsigned int bb_index;
392 6009284 : bitmap_iterator bi;
393 6009284 : class df_rd_problem_data *problem_data
394 6009284 : = (class df_rd_problem_data *) df_rd->problem_data;
395 6009284 : bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
396 6009284 : bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
397 :
398 6009284 : bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
399 6009284 : bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
400 :
401 6009284 : df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
402 :
403 73036559 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
404 : {
405 67027275 : 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 6009284 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
413 556781607 : for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
414 550794708 : if (eh_edge_abi.clobbers_full_reg_p (regno))
415 : {
416 496861967 : if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
417 10166821 : bitmap_set_bit (sparse_invalidated, regno);
418 : else
419 486695146 : bitmap_set_range (dense_invalidated,
420 486695146 : DF_DEFS_BEGIN (regno),
421 : DF_DEFS_COUNT (regno));
422 : }
423 :
424 6009284 : bitmap_release (&seen_in_block);
425 6009284 : bitmap_release (&seen_in_insn);
426 6009284 : }
427 :
428 :
429 : /* Initialize the solution bit vectors for problem. */
430 :
431 : static void
432 6009284 : df_rd_init_solution (bitmap all_blocks)
433 : {
434 6009284 : unsigned int bb_index;
435 6009284 : bitmap_iterator bi;
436 :
437 73036559 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
438 : {
439 67027275 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
440 :
441 67027275 : bitmap_copy (&bb_info->out, &bb_info->gen);
442 67027275 : bitmap_clear (&bb_info->in);
443 : }
444 6009284 : }
445 :
446 : /* In of target gets or of out of source. */
447 :
448 : static bool
449 108928016 : df_rd_confluence_n (edge e)
450 : {
451 108928016 : bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
452 108928016 : bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
453 108928016 : bool changed = false;
454 :
455 108928016 : if (e->flags & EDGE_FAKE)
456 : return false;
457 :
458 108928016 : if (e->flags & EDGE_EH)
459 : {
460 3248735 : class df_rd_problem_data *problem_data
461 : = (class df_rd_problem_data *) df_rd->problem_data;
462 3248735 : bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
463 3248735 : bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
464 3248735 : bitmap_iterator bi;
465 3248735 : unsigned int regno;
466 :
467 3248735 : auto_bitmap tmp (&df_bitmap_obstack);
468 3248735 : bitmap_and_compl (tmp, op2, dense_invalidated);
469 :
470 173668920 : EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
471 : {
472 170420185 : bitmap_clear_range (tmp,
473 170420185 : DF_DEFS_BEGIN (regno),
474 170420185 : DF_DEFS_COUNT (regno));
475 : }
476 3248735 : changed |= bitmap_ior_into (op1, tmp);
477 3248735 : return changed;
478 3248735 : }
479 : else
480 105679281 : return bitmap_ior_into (op1, op2);
481 : }
482 :
483 :
484 : /* Transfer function. */
485 :
486 : static bool
487 78250042 : df_rd_transfer_function (int bb_index)
488 : {
489 78250042 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
490 78250042 : unsigned int regno;
491 78250042 : bitmap_iterator bi;
492 78250042 : bitmap in = &bb_info->in;
493 78250042 : bitmap out = &bb_info->out;
494 78250042 : bitmap gen = &bb_info->gen;
495 78250042 : bitmap kill = &bb_info->kill;
496 78250042 : bitmap sparse_kill = &bb_info->sparse_kill;
497 78250042 : bool changed = false;
498 :
499 78250042 : if (bitmap_empty_p (sparse_kill))
500 46555887 : changed = bitmap_ior_and_compl (out, gen, in, kill);
501 : else
502 : {
503 31694155 : class df_rd_problem_data *problem_data;
504 31694155 : 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 31694155 : problem_data = (class df_rd_problem_data *) df_rd->problem_data;
509 31694155 : bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
510 :
511 31694155 : bitmap_and_compl (&tmp, in, kill);
512 80276106 : EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
513 : {
514 48581951 : bitmap_clear_range (&tmp,
515 48581951 : DF_DEFS_BEGIN (regno),
516 48581951 : DF_DEFS_COUNT (regno));
517 : }
518 31694155 : bitmap_ior_into (&tmp, gen);
519 31694155 : changed = !bitmap_equal_p (&tmp, out);
520 31694155 : if (changed)
521 31076922 : bitmap_move (out, &tmp);
522 : else
523 617233 : bitmap_clear (&tmp);
524 : }
525 :
526 78250042 : 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 78247328 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
533 78247328 : bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
534 78247328 : bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
535 78247328 : unsigned int regno;
536 78247328 : bitmap_iterator bi;
537 :
538 831815264 : EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
539 753567936 : bitmap_set_range (live_defs,
540 753567936 : DF_DEFS_BEGIN (regno),
541 753567936 : DF_DEFS_COUNT (regno));
542 78247328 : changed |= bitmap_and_into (&bb_info->out, live_defs);
543 78247328 : BITMAP_FREE (live_defs);
544 : }
545 :
546 78250042 : return changed;
547 : }
548 :
549 : /* Free all storage associated with the problem. */
550 :
551 : static void
552 5098897 : df_rd_free (void)
553 : {
554 5098897 : class df_rd_problem_data *problem_data
555 5098897 : = (class df_rd_problem_data *) df_rd->problem_data;
556 :
557 5098897 : if (problem_data)
558 : {
559 5098897 : bitmap_obstack_release (&problem_data->rd_bitmaps);
560 :
561 5098897 : df_rd->block_info_size = 0;
562 5098897 : free (df_rd->block_info);
563 5098897 : df_rd->block_info = NULL;
564 5098897 : free (df_rd->problem_data);
565 : }
566 5098897 : free (df_rd);
567 5098897 : }
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 27800 : for (regno = 0; regno < m; regno++)
592 27366 : if (DF_DEFS_COUNT (regno))
593 13971 : fprintf (file, "%d[%d,%d] ", regno,
594 : DF_DEFS_BEGIN (regno),
595 13971 : 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 376452 : for (regno = 0; regno < m; regno++)
612 : {
613 373900 : if (HARD_REGISTER_NUM_P (regno)
614 234784 : && (df->changeable_flags & DF_NO_HARD_REGS))
615 0 : continue;
616 373900 : bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
617 373900 : bitmap_and_into (&tmp, defs_set);
618 373900 : if (! bitmap_empty_p (&tmp))
619 : {
620 8723 : bitmap_iterator bi;
621 8723 : unsigned int ix;
622 8723 : bool first_def = true;
623 :
624 8723 : if (! first_reg)
625 6670 : fprintf (file, ",");
626 8723 : first_reg = false;
627 :
628 8723 : fprintf (file, "%u[", regno);
629 19334 : EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
630 : {
631 12499 : fprintf (file, "%s%u", first_def ? "" : ",", ix);
632 10611 : first_def = false;
633 : }
634 8723 : fprintf (file, "]");
635 : }
636 373900 : 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 267 : df_rd_add_problem (void)
708 : {
709 267 : df_add_problem (&problem_RD);
710 267 : }
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 6671159 : df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
736 : void *vbb_info)
737 : {
738 6671159 : class df_lr_bb_info *bb_info = (class df_lr_bb_info *) vbb_info;
739 6671159 : if (bb_info)
740 : {
741 6671159 : bitmap_clear (&bb_info->use);
742 6671159 : bitmap_clear (&bb_info->def);
743 6671159 : bitmap_clear (&bb_info->in);
744 6671159 : bitmap_clear (&bb_info->out);
745 : }
746 6671159 : }
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 16794272 : df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
754 : {
755 16794272 : unsigned int bb_index;
756 16794272 : bitmap_iterator bi;
757 16794272 : struct df_lr_problem_data *problem_data;
758 :
759 16794272 : df_grow_bb_info (df_lr);
760 16794272 : if (df_lr->problem_data)
761 : problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
762 : else
763 : {
764 1471363 : problem_data = XNEW (struct df_lr_problem_data);
765 1471363 : df_lr->problem_data = problem_data;
766 :
767 1471363 : problem_data->out = NULL;
768 1471363 : problem_data->in = NULL;
769 1471363 : bitmap_obstack_initialize (&problem_data->lr_bitmaps);
770 : }
771 :
772 109902457 : EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
773 : {
774 93108185 : 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 93108185 : if (bb_info->use.obstack)
778 : {
779 70166537 : bitmap_clear (&bb_info->def);
780 70166537 : bitmap_clear (&bb_info->use);
781 : }
782 : else
783 : {
784 22941648 : bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
785 22941648 : bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
786 22941648 : bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
787 22941648 : bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
788 : }
789 : }
790 :
791 16794272 : df_lr->optional_p = false;
792 16794272 : }
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 88236001 : df_lr_bb_local_compute (unsigned int bb_index)
817 : {
818 88236001 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
819 88236001 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
820 88236001 : rtx_insn *insn;
821 88236001 : df_ref def, use;
822 :
823 : /* Process the registers set in an exception handler. */
824 248519911 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
825 72047909 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
826 : {
827 70165424 : unsigned int dregno = DF_REF_REGNO (def);
828 70165424 : bitmap_set_bit (&bb_info->def, dregno);
829 70165424 : bitmap_clear_bit (&bb_info->use, dregno);
830 : }
831 :
832 : /* Process the hardware registers that are always live. */
833 421897961 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
834 : /* Add use to set of uses in this BB. */
835 245425959 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
836 245425959 : bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
837 :
838 1268164651 : FOR_BB_INSNS_REVERSE (bb, insn)
839 : {
840 1179928650 : if (!NONDEBUG_INSN_P (insn))
841 573910692 : continue;
842 :
843 606017958 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844 4470977570 : 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 3864959612 : unsigned int dregno = DF_REF_REGNO (def);
887 3864959612 : bitmap_set_bit (&bb_info->def, dregno);
888 3864959612 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
889 2084362 : bitmap_set_bit (&bb_info->use, dregno);
890 : else
891 3862875250 : bitmap_clear_bit (&bb_info->use, dregno);
892 : }
893 :
894 1381581474 : FOR_EACH_INSN_INFO_USE (use, insn_info)
895 : /* Add use to set of uses in this BB. */
896 775563516 : 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 248519911 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
903 72047909 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
904 : {
905 1882485 : unsigned int dregno = DF_REF_REGNO (def);
906 1882485 : bitmap_set_bit (&bb_info->def, dregno);
907 1882485 : 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 88236001 : if (!df_live)
923 11667904 : df_recompute_luids (bb);
924 88236001 : }
925 :
926 :
927 : /* Compute local live register info for each basic block within BLOCKS. */
928 :
929 : static void
930 16794272 : df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
931 : {
932 16794272 : unsigned int bb_index, i;
933 16794272 : bitmap_iterator bi;
934 :
935 16794272 : bitmap_clear (&df->hardware_regs_used);
936 :
937 : /* The all-important stack pointer must always be live. */
938 16794272 : bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
939 :
940 : /* Global regs are always live, too. */
941 1578661568 : for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
942 1545073024 : if (global_regs[i])
943 1416 : 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 16794272 : if (!reload_completed)
949 : {
950 10010096 : 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 10010096 : 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 10010096 : if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
958 10010096 : && fixed_regs[ARG_POINTER_REGNUM])
959 10010096 : 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 10010096 : 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 109902457 : EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
969 : {
970 93108185 : 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 4872184 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
975 4872184 : bitmap_copy (&bb_info->use, df->exit_block_uses);
976 : }
977 : else
978 88236001 : df_lr_bb_local_compute (bb_index);
979 : }
980 :
981 16794272 : bitmap_clear (df_lr->out_of_date_transfer_functions);
982 16794272 : }
983 :
984 :
985 : /* Initialize the solution vectors. */
986 :
987 : static void
988 16794272 : df_lr_init (bitmap all_blocks)
989 : {
990 16794272 : unsigned int bb_index;
991 16794272 : bitmap_iterator bi;
992 :
993 372387874 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
994 : {
995 355593602 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
996 355593602 : bitmap_copy (&bb_info->in, &bb_info->use);
997 355593602 : bitmap_clear (&bb_info->out);
998 : }
999 16794272 : }
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 28512525 : df_lr_confluence_0 (basic_block bb)
1007 : {
1008 28512525 : bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
1009 28512525 : if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1010 13022441 : bitmap_copy (op1, &df->hardware_regs_used);
1011 28512525 : }
1012 :
1013 :
1014 : /* Confluence function that ignores fake edges. */
1015 :
1016 : static bool
1017 571876871 : df_lr_confluence_n (edge e)
1018 : {
1019 571876871 : bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
1020 571876871 : bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
1021 571876871 : 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 571876871 : if (e->flags & EDGE_EH)
1030 : {
1031 22818141 : bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
1032 22818141 : changed = bitmap_ior_and_compl_into (op1, op2, eh_kills);
1033 : }
1034 : else
1035 549058730 : changed = bitmap_ior_into (op1, op2);
1036 :
1037 571876871 : changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
1038 571876871 : return changed;
1039 : }
1040 :
1041 :
1042 : /* Transfer function. */
1043 :
1044 : static bool
1045 400992253 : df_lr_transfer_function (int bb_index)
1046 : {
1047 400992253 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1048 400992253 : bitmap in = &bb_info->in;
1049 400992253 : bitmap out = &bb_info->out;
1050 400992253 : bitmap use = &bb_info->use;
1051 400992253 : bitmap def = &bb_info->def;
1052 :
1053 400992253 : return bitmap_ior_and_compl (in, use, out, def);
1054 : }
1055 :
1056 :
1057 : static void
1058 16794272 : df_lr_finalize (bitmap)
1059 : {
1060 16794272 : df_lr->solutions_dirty = false;
1061 16117115 : }
1062 :
1063 :
1064 : /* Free all storage associated with the problem. */
1065 :
1066 : static void
1067 1471365 : df_lr_free (void)
1068 : {
1069 1471365 : struct df_lr_problem_data *problem_data
1070 1471365 : = (struct df_lr_problem_data *) df_lr->problem_data;
1071 1471365 : if (df_lr->block_info)
1072 : {
1073 :
1074 1471363 : df_lr->block_info_size = 0;
1075 1471363 : free (df_lr->block_info);
1076 1471363 : df_lr->block_info = NULL;
1077 1471363 : bitmap_obstack_release (&problem_data->lr_bitmaps);
1078 1471363 : free (df_lr->problem_data);
1079 1471363 : df_lr->problem_data = NULL;
1080 : }
1081 :
1082 1471365 : BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1083 1471365 : free (df_lr);
1084 1471365 : }
1085 :
1086 :
1087 : /* Debugging info at top of bb. */
1088 :
1089 : static void
1090 5354 : df_lr_top_dump (basic_block bb, FILE *file)
1091 : {
1092 5354 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1093 5258 : struct df_lr_problem_data *problem_data;
1094 5258 : if (!bb_info)
1095 : return;
1096 :
1097 5258 : fprintf (file, ";; lr in \t");
1098 5258 : df_print_regset (file, &bb_info->in);
1099 5258 : if (df_lr->problem_data)
1100 : {
1101 5258 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1102 5258 : 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 5258 : fprintf (file, ";; lr use \t");
1109 5258 : df_print_regset (file, &bb_info->use);
1110 5258 : fprintf (file, ";; lr def \t");
1111 5258 : df_print_regset (file, &bb_info->def);
1112 : }
1113 :
1114 :
1115 : /* Debugging info at bottom of bb. */
1116 :
1117 : static void
1118 5354 : df_lr_bottom_dump (basic_block bb, FILE *file)
1119 : {
1120 5354 : class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1121 5258 : struct df_lr_problem_data *problem_data;
1122 5258 : if (!bb_info)
1123 : return;
1124 :
1125 5258 : fprintf (file, ";; lr out \t");
1126 5258 : df_print_regset (file, &bb_info->out);
1127 5258 : if (df_lr->problem_data)
1128 : {
1129 5258 : problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1130 5258 : 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 24160247 : df_lr_dce_finalize (bitmap all_blocks)
1247 : {
1248 24160247 : if (!(df->changeable_flags & DF_LR_RUN_DCE))
1249 : return;
1250 :
1251 : /* Also clears df_lr_dce->solutions_dirty. */
1252 8612102 : 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 8612102 : if (df_lr->solutions_dirty)
1266 : {
1267 677157 : df_clear_flags (DF_LR_RUN_DCE);
1268 677157 : df_lr_alloc (all_blocks);
1269 677157 : df_lr_local_compute (all_blocks);
1270 677157 : df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1271 677157 : df_lr_finalize (all_blocks);
1272 677157 : 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 1471365 : 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 1471365 : df_add_problem (&problem_LR_DCE);
1316 : /* These will be initialized when df_scan_blocks processes each
1317 : block. */
1318 1471365 : df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1319 1471365 : }
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 6274242 : df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1426 : void *vbb_info)
1427 : {
1428 6274242 : class df_live_bb_info *bb_info = (class df_live_bb_info *) vbb_info;
1429 6274242 : if (bb_info)
1430 : {
1431 6274242 : bitmap_clear (&bb_info->gen);
1432 6274242 : bitmap_clear (&bb_info->kill);
1433 6274242 : bitmap_clear (&bb_info->in);
1434 6274242 : bitmap_clear (&bb_info->out);
1435 : }
1436 6274242 : }
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 14823599 : df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1444 : {
1445 14823599 : unsigned int bb_index;
1446 14823599 : bitmap_iterator bi;
1447 14823599 : struct df_live_problem_data *problem_data;
1448 :
1449 14823599 : if (df_live->problem_data)
1450 : problem_data = (struct df_live_problem_data *) df_live->problem_data;
1451 : else
1452 : {
1453 2323543 : problem_data = XNEW (struct df_live_problem_data);
1454 2323543 : df_live->problem_data = problem_data;
1455 :
1456 2323543 : problem_data->out = NULL;
1457 2323543 : problem_data->in = NULL;
1458 2323543 : bitmap_obstack_initialize (&problem_data->live_bitmaps);
1459 2323543 : bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1460 : }
1461 :
1462 14823599 : df_grow_bb_info (df_live);
1463 :
1464 118316636 : EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1465 : {
1466 103493037 : 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 103493037 : if (bb_info->kill.obstack)
1470 : {
1471 69512454 : bitmap_clear (&bb_info->kill);
1472 69512454 : bitmap_clear (&bb_info->gen);
1473 : }
1474 : else
1475 : {
1476 33980583 : bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1477 33980583 : bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1478 33980583 : bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1479 33980583 : bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1480 : }
1481 : }
1482 14823599 : df_live->optional_p = (optimize <= 1);
1483 14823599 : }
1484 :
1485 :
1486 : /* Reset the global solution for recalculation. */
1487 :
1488 : static void
1489 29672 : df_live_reset (bitmap all_blocks)
1490 : {
1491 29672 : unsigned int bb_index;
1492 29672 : bitmap_iterator bi;
1493 :
1494 181779 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1495 : {
1496 152107 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1497 152107 : gcc_assert (bb_info);
1498 152107 : bitmap_clear (&bb_info->in);
1499 152107 : bitmap_clear (&bb_info->out);
1500 : }
1501 29672 : }
1502 :
1503 :
1504 : /* Compute local uninitialized register info for basic block BB. */
1505 :
1506 : static void
1507 103493037 : df_live_bb_local_compute (unsigned int bb_index)
1508 : {
1509 103493037 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1510 103493037 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1511 103493037 : rtx_insn *insn;
1512 103493037 : df_ref def;
1513 103493037 : int luid = 0;
1514 :
1515 1410099489 : FOR_BB_INSNS (bb, insn)
1516 : {
1517 1306606452 : unsigned int uid = INSN_UID (insn);
1518 1306606452 : struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1519 :
1520 : /* Inserting labels does not always trigger the incremental
1521 : rescanning. */
1522 1306606452 : if (!insn_info)
1523 : {
1524 14285935 : gcc_assert (!INSN_P (insn));
1525 14285935 : insn_info = df_insn_create_insn_record (insn);
1526 : }
1527 :
1528 1306606452 : DF_INSN_INFO_LUID (insn_info) = luid;
1529 1306606452 : if (!INSN_P (insn))
1530 187756619 : continue;
1531 :
1532 1118849833 : luid++;
1533 5213840932 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
1534 : {
1535 4094991099 : unsigned int regno = DF_REF_REGNO (def);
1536 :
1537 4094991099 : 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 1887858 : bitmap_set_bit (&bb_info->gen, regno);
1542 4093103241 : 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 87242665 : bitmap_set_bit (&bb_info->kill, regno);
1546 4005860576 : else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1547 450317901 : bitmap_set_bit (&bb_info->gen, regno);
1548 : }
1549 : }
1550 :
1551 270806662 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1552 63820588 : bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1553 103493037 : }
1554 :
1555 :
1556 : /* Compute local uninitialized register info. */
1557 :
1558 : static void
1559 14823599 : df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1560 : {
1561 14823599 : unsigned int bb_index;
1562 14823599 : bitmap_iterator bi;
1563 :
1564 14823599 : df_grow_insn_info ();
1565 :
1566 118316636 : EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1567 : 0, bb_index, bi)
1568 : {
1569 103493037 : df_live_bb_local_compute (bb_index);
1570 : }
1571 :
1572 14823599 : bitmap_clear (df_live->out_of_date_transfer_functions);
1573 14823599 : }
1574 :
1575 :
1576 : /* Initialize the solution vectors. */
1577 :
1578 : static void
1579 14823599 : df_live_init (bitmap all_blocks)
1580 : {
1581 14823599 : unsigned int bb_index;
1582 14823599 : bitmap_iterator bi;
1583 :
1584 315206146 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1585 : {
1586 300382547 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1587 300382547 : 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 300382547 : bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1592 300382547 : bitmap_clear (&bb_info->in);
1593 : }
1594 14823599 : }
1595 :
1596 : /* Forward confluence function that ignores fake edges. */
1597 :
1598 : static bool
1599 450579096 : df_live_confluence_n (edge e)
1600 : {
1601 450579096 : bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1602 450579096 : bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1603 :
1604 450579096 : if (e->flags & EDGE_FAKE)
1605 : return false;
1606 :
1607 450304852 : return bitmap_ior_into (op1, op2);
1608 : }
1609 :
1610 :
1611 : /* Transfer function for the forwards may-initialized problem. */
1612 :
1613 : static bool
1614 313764603 : df_live_transfer_function (int bb_index)
1615 : {
1616 313764603 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1617 313764603 : class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1618 313764603 : bitmap in = &bb_info->in;
1619 313764603 : bitmap out = &bb_info->out;
1620 313764603 : bitmap gen = &bb_info->gen;
1621 313764603 : 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 313764603 : 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 313764603 : bitmap_and_into (in, &bb_lr_info->in);
1630 :
1631 313764603 : 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 14823599 : df_live_finalize (bitmap all_blocks)
1639 : {
1640 :
1641 14823599 : if (df_live->solutions_dirty)
1642 : {
1643 14823599 : bitmap_iterator bi;
1644 14823599 : unsigned int bb_index;
1645 :
1646 315206146 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1647 : {
1648 300382547 : class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1649 300382547 : 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 300382547 : bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1654 300382547 : bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1655 : }
1656 :
1657 14823599 : df_live->solutions_dirty = false;
1658 : }
1659 14823599 : }
1660 :
1661 :
1662 : /* Free all storage associated with the problem. */
1663 :
1664 : static void
1665 2326085 : df_live_free (void)
1666 : {
1667 2326085 : struct df_live_problem_data *problem_data
1668 2326085 : = (struct df_live_problem_data *) df_live->problem_data;
1669 2326085 : if (df_live->block_info)
1670 : {
1671 2323543 : df_live->block_info_size = 0;
1672 2323543 : free (df_live->block_info);
1673 2323543 : df_live->block_info = NULL;
1674 2323543 : bitmap_release (&df_live_scratch);
1675 2323543 : bitmap_obstack_release (&problem_data->live_bitmaps);
1676 2323543 : free (problem_data);
1677 2323543 : df_live->problem_data = NULL;
1678 : }
1679 2326085 : BITMAP_FREE (df_live->out_of_date_transfer_functions);
1680 2326085 : free (df_live);
1681 2326085 : }
1682 :
1683 :
1684 : /* Debugging info at top of bb. */
1685 :
1686 : static void
1687 4044 : df_live_top_dump (basic_block bb, FILE *file)
1688 : {
1689 4044 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1690 3948 : struct df_live_problem_data *problem_data;
1691 :
1692 3948 : if (!bb_info)
1693 : return;
1694 :
1695 3948 : fprintf (file, ";; live in \t");
1696 3948 : df_print_regset (file, &bb_info->in);
1697 3948 : if (df_live->problem_data)
1698 : {
1699 3948 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1700 3948 : 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 3948 : fprintf (file, ";; live gen \t");
1707 3948 : df_print_regset (file, &bb_info->gen);
1708 3948 : fprintf (file, ";; live kill\t");
1709 3948 : df_print_regset (file, &bb_info->kill);
1710 : }
1711 :
1712 :
1713 : /* Debugging info at bottom of bb. */
1714 :
1715 : static void
1716 4044 : df_live_bottom_dump (basic_block bb, FILE *file)
1717 : {
1718 4044 : class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1719 3948 : struct df_live_problem_data *problem_data;
1720 :
1721 3948 : if (!bb_info)
1722 : return;
1723 :
1724 3948 : fprintf (file, ";; live out \t");
1725 3948 : df_print_regset (file, &bb_info->out);
1726 3948 : if (df_live->problem_data)
1727 : {
1728 3948 : problem_data = (struct df_live_problem_data *)df_live->problem_data;
1729 3948 : 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 2991038 : df_live_add_problem (void)
1842 : {
1843 2991038 : df_add_problem (&problem_LIVE);
1844 : /* These will be initialized when df_scan_blocks processes each
1845 : block. */
1846 2991038 : df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1847 2991038 : }
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 2992943 : df_live_set_all_dirty (void)
1855 : {
1856 2992943 : basic_block bb;
1857 45058357 : FOR_ALL_BB_FN (bb, cfun)
1858 42065414 : bitmap_set_bit (df_live->out_of_date_transfer_functions,
1859 : bb->index);
1860 2992943 : }
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 963990 : df_mir_alloc (bitmap all_blocks)
1963 : {
1964 963990 : unsigned int bb_index;
1965 963990 : bitmap_iterator bi;
1966 963990 : struct df_mir_problem_data *problem_data;
1967 :
1968 963990 : if (df_mir->problem_data)
1969 : problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1970 : else
1971 : {
1972 963990 : problem_data = XNEW (struct df_mir_problem_data);
1973 963990 : df_mir->problem_data = problem_data;
1974 :
1975 963990 : problem_data->out = NULL;
1976 963990 : problem_data->in = NULL;
1977 963990 : bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1978 : }
1979 :
1980 963990 : df_grow_bb_info (df_mir);
1981 :
1982 13303003 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1983 : {
1984 12339013 : 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 12339013 : 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 12339013 : bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1995 12339013 : bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1996 12339013 : bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1997 12339013 : bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1998 12339013 : bb_info->con_visited = false;
1999 : }
2000 : }
2001 :
2002 963990 : df_mir->optional_p = 1;
2003 963990 : }
2004 :
2005 :
2006 : /* Reset the global solution for recalculation. */
2007 :
2008 : static void
2009 963990 : df_mir_reset (bitmap all_blocks)
2010 : {
2011 963990 : unsigned int bb_index;
2012 963990 : bitmap_iterator bi;
2013 :
2014 13303003 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2015 : {
2016 12339013 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2017 :
2018 12339013 : gcc_assert (bb_info);
2019 :
2020 12339013 : bitmap_clear (&bb_info->in);
2021 12339013 : bitmap_clear (&bb_info->out);
2022 12339013 : bb_info->con_visited = false;
2023 : }
2024 963990 : }
2025 :
2026 :
2027 : /* Compute local uninitialized register info for basic block BB. */
2028 :
2029 : static void
2030 12339013 : df_mir_bb_local_compute (unsigned int bb_index)
2031 : {
2032 12339013 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2033 12339013 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2034 12339013 : rtx_insn *insn;
2035 12339013 : 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 137630701 : FOR_BB_INSNS (bb, insn)
2043 : {
2044 125291688 : unsigned int uid = INSN_UID (insn);
2045 125291688 : struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2046 :
2047 : /* Inserting labels does not always trigger the incremental
2048 : rescanning. */
2049 125291688 : if (!insn_info)
2050 : {
2051 4037 : gcc_assert (!INSN_P (insn));
2052 4037 : insn_info = df_insn_create_insn_record (insn);
2053 : }
2054 :
2055 125291688 : DF_INSN_INFO_LUID (insn_info) = luid;
2056 125291688 : if (!INSN_P (insn))
2057 21648643 : continue;
2058 :
2059 103643045 : luid++;
2060 103643045 : df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
2061 : }
2062 12339013 : }
2063 :
2064 :
2065 : /* Compute local uninitialized register info. */
2066 :
2067 : static void
2068 963990 : df_mir_local_compute (bitmap all_blocks)
2069 : {
2070 963990 : unsigned int bb_index;
2071 963990 : bitmap_iterator bi;
2072 :
2073 963990 : df_grow_insn_info ();
2074 :
2075 13303003 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2076 : {
2077 12339013 : df_mir_bb_local_compute (bb_index);
2078 : }
2079 963990 : }
2080 :
2081 :
2082 : /* Initialize the solution vectors. */
2083 :
2084 : static void
2085 963990 : df_mir_init (bitmap all_blocks)
2086 : {
2087 963990 : df_mir_reset (all_blocks);
2088 963990 : }
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 989326 : df_mir_confluence_0 (basic_block bb)
2096 : {
2097 989326 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2098 :
2099 989326 : bitmap_clear (&bb_info->in);
2100 989326 : bb_info->con_visited = true;
2101 989326 : }
2102 :
2103 :
2104 : /* Forward confluence function that ignores fake edges. */
2105 :
2106 : static bool
2107 17224043 : df_mir_confluence_n (edge e)
2108 : {
2109 17224043 : if (e->flags & EDGE_FAKE)
2110 : return false;
2111 :
2112 17224043 : 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 17224043 : if (!src_info->con_visited)
2117 : return false;
2118 :
2119 16672094 : df_mir_bb_info *dst_info = df_mir_get_bb_info (e->dest->index);
2120 16672094 : bitmap op1 = &dst_info->in;
2121 16672094 : bitmap op2 = &src_info->out;
2122 : /* If DEST was not visited yet just copy the SRC bitmap. */
2123 16672094 : if (!dst_info->con_visited)
2124 : {
2125 11349687 : dst_info->con_visited = true;
2126 11349687 : bitmap_copy (op1, op2);
2127 11349687 : 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 5322407 : return bitmap_and_into (op1, op2);
2133 : }
2134 :
2135 :
2136 : /* Transfer function for the forwards must-initialized problem. */
2137 :
2138 : static bool
2139 12733896 : df_mir_transfer_function (int bb_index)
2140 : {
2141 12733896 : class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2142 12733896 : bitmap in = &bb_info->in;
2143 12733896 : bitmap out = &bb_info->out;
2144 12733896 : bitmap gen = &bb_info->gen;
2145 12733896 : bitmap kill = &bb_info->kill;
2146 :
2147 12733896 : 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 963990 : df_mir_free (void)
2155 : {
2156 963990 : struct df_mir_problem_data *problem_data
2157 963990 : = (struct df_mir_problem_data *) df_mir->problem_data;
2158 963990 : if (df_mir->block_info)
2159 : {
2160 963990 : df_mir->block_info_size = 0;
2161 963990 : free (df_mir->block_info);
2162 963990 : df_mir->block_info = NULL;
2163 963990 : bitmap_obstack_release (&problem_data->mir_bitmaps);
2164 963990 : free (problem_data);
2165 963990 : df_mir->problem_data = NULL;
2166 : }
2167 963990 : free (df_mir);
2168 963990 : }
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 963990 : df_mir_add_problem (void)
2306 : {
2307 963990 : df_add_problem (&problem_MIR);
2308 : /* These will be initialized when df_scan_blocks processes each
2309 : block. */
2310 963990 : df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2311 963990 : }
2312 :
2313 :
2314 : /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2315 :
2316 : void
2317 158523520 : df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2318 : bitmap kill, bitmap gen)
2319 : {
2320 158523520 : df_ref def;
2321 :
2322 949871428 : FOR_EACH_INSN_DEF (def, insn)
2323 : {
2324 791347908 : 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 791347908 : if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2330 : {
2331 716555924 : bitmap_set_bit (kill, regno);
2332 716555924 : 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 74791984 : else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2337 : {
2338 74761430 : bitmap_set_bit (gen, regno);
2339 74761430 : bitmap_clear_bit (kill, regno);
2340 : }
2341 : }
2342 158523520 : }
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 1205290888 : df_chain_create (df_ref src, df_ref dst)
2361 : {
2362 1205290888 : struct df_link *head = DF_REF_CHAIN (src);
2363 1205290888 : struct df_link *link = df_chain->block_pool->allocate ();
2364 :
2365 1205290888 : DF_REF_CHAIN (src) = link;
2366 1205290888 : link->next = head;
2367 1205290888 : link->ref = dst;
2368 1205290888 : 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 667869 : df_chain_unlink_1 (df_ref ref, df_ref target)
2376 : {
2377 667869 : struct df_link *chain = DF_REF_CHAIN (ref);
2378 667869 : struct df_link *prev = NULL;
2379 :
2380 26757138 : while (chain)
2381 : {
2382 26743700 : if (chain->ref == target)
2383 : {
2384 654431 : if (prev)
2385 246497 : prev->next = chain->next;
2386 : else
2387 407934 : DF_REF_CHAIN (ref) = chain->next;
2388 654431 : df_chain->block_pool->remove (chain);
2389 654431 : return;
2390 : }
2391 26089269 : prev = chain;
2392 26089269 : chain = chain->next;
2393 : }
2394 : }
2395 :
2396 :
2397 : /* Delete a du or ud chain that leave or point to REF. */
2398 :
2399 : void
2400 483924 : df_chain_unlink (df_ref ref)
2401 : {
2402 483924 : struct df_link *chain = DF_REF_CHAIN (ref);
2403 1151793 : while (chain)
2404 : {
2405 667869 : struct df_link *next = chain->next;
2406 : /* Delete the other side if it exists. */
2407 667869 : df_chain_unlink_1 (chain->ref, ref);
2408 667869 : df_chain->block_pool->remove (chain);
2409 667869 : chain = next;
2410 : }
2411 483924 : DF_REF_CHAIN (ref) = NULL;
2412 483924 : }
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 12018568 : df_chain_remove_problem (void)
2434 : {
2435 12018568 : bitmap_iterator bi;
2436 12018568 : unsigned int bb_index;
2437 :
2438 : /* Wholesale destruction of the old chains. */
2439 12018568 : if (df_chain->block_pool)
2440 6009284 : delete df_chain->block_pool;
2441 :
2442 79827673 : EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2443 : {
2444 67809105 : rtx_insn *insn;
2445 67809105 : df_ref def, use;
2446 67809105 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2447 :
2448 67809105 : if (df_chain_problem_p (DF_DU_CHAIN))
2449 158296266 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2450 64817754 : DF_REF_CHAIN (def) = NULL;
2451 67809105 : if (df_chain_problem_p (DF_UD_CHAIN))
2452 322941945 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2453 187323735 : DF_REF_CHAIN (use) = NULL;
2454 :
2455 759072069 : FOR_BB_INSNS (bb, insn)
2456 691262964 : if (INSN_P (insn))
2457 : {
2458 582287240 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2459 582287240 : if (df_chain_problem_p (DF_DU_CHAIN))
2460 1934970181 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
2461 1533431488 : DF_REF_CHAIN (def) = NULL;
2462 582287240 : if (df_chain_problem_p (DF_UD_CHAIN))
2463 : {
2464 1036799182 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2465 454511942 : DF_REF_CHAIN (use) = NULL;
2466 595705934 : FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2467 13418694 : DF_REF_CHAIN (use) = NULL;
2468 : }
2469 : }
2470 : }
2471 :
2472 12018568 : bitmap_clear (df_chain->out_of_date_transfer_functions);
2473 12018568 : df_chain->block_pool = NULL;
2474 12018568 : }
2475 :
2476 :
2477 : /* Remove the chain problem completely. */
2478 :
2479 : static void
2480 6009284 : df_chain_fully_remove_problem (void)
2481 : {
2482 6009284 : df_chain_remove_problem ();
2483 6009284 : BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2484 6009284 : free (df_chain);
2485 6009284 : }
2486 :
2487 :
2488 : /* Create def-use or use-def chains. */
2489 :
2490 : static void
2491 6009284 : df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2492 : {
2493 6009284 : df_chain_remove_problem ();
2494 6009284 : df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2495 6009284 : df_chain->optional_p = true;
2496 6009284 : }
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 825486298 : df_chain_create_bb_process_use (bitmap local_rd,
2512 : df_ref use,
2513 : int top_flag)
2514 : {
2515 825486298 : bitmap_iterator bi;
2516 825486298 : unsigned int def_index;
2517 :
2518 1464656486 : for (; use; use = DF_REF_NEXT_LOC (use))
2519 : {
2520 639170188 : unsigned int uregno = DF_REF_REGNO (use);
2521 639170188 : if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2522 5132526 : || (uregno >= FIRST_PSEUDO_REGISTER))
2523 : {
2524 : /* Do not want to go through this for an uninitialized var. */
2525 637805071 : int count = DF_DEFS_COUNT (uregno);
2526 637805071 : if (count)
2527 : {
2528 594592108 : if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2529 : {
2530 594592108 : unsigned int first_index = DF_DEFS_BEGIN (uregno);
2531 594592108 : unsigned int last_index = first_index + count - 1;
2532 :
2533 1303777087 : EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2534 : {
2535 1228233247 : df_ref def;
2536 1228233247 : if (def_index > last_index)
2537 : break;
2538 :
2539 709184979 : def = DF_DEFS_GET (def_index);
2540 709184979 : if (df_chain_problem_p (DF_DU_CHAIN))
2541 496105909 : df_chain_create (def, use);
2542 709184979 : if (df_chain_problem_p (DF_UD_CHAIN))
2543 709184979 : df_chain_create (use, def);
2544 : }
2545 : }
2546 : }
2547 : }
2548 : }
2549 825486298 : }
2550 :
2551 :
2552 : /* Create chains from reaching defs bitmaps for basic block BB. */
2553 :
2554 : static void
2555 67027275 : df_chain_create_bb (unsigned int bb_index)
2556 : {
2557 67027275 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2558 67027275 : class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2559 67027275 : rtx_insn *insn;
2560 67027275 : bitmap_head cpy;
2561 :
2562 67027275 : bitmap_initialize (&cpy, &bitmap_default_obstack);
2563 67027275 : bitmap_copy (&cpy, &bb_info->in);
2564 67027275 : 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 67027275 : df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2581 :
2582 : /* Process the regular instructions next. */
2583 753083342 : FOR_BB_INSNS (bb, insn)
2584 686056067 : if (INSN_P (insn))
2585 : {
2586 578189377 : 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 578189377 : df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2591 578189377 : if (df->changeable_flags & DF_EQ_NOTES)
2592 180843447 : 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 578189377 : 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 67027275 : if (!(df->changeable_flags & DF_NO_HARD_REGS))
2601 66453474 : df_chain_create_bb_process_use (&cpy,
2602 66453474 : df_get_artificial_uses (bb->index),
2603 : 0);
2604 :
2605 67027275 : bitmap_clear (&cpy);
2606 67027275 : }
2607 :
2608 : /* Create def-use chains from reaching use bitmaps for basic blocks
2609 : in BLOCKS. */
2610 :
2611 : static void
2612 6009284 : df_chain_finalize (bitmap all_blocks)
2613 : {
2614 6009284 : unsigned int bb_index;
2615 6009284 : bitmap_iterator bi;
2616 :
2617 73036559 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2618 : {
2619 67027275 : df_chain_create_bb (bb_index);
2620 : }
2621 6009284 : }
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 6009284 : df_chain_add_problem (unsigned int chain_flags)
2779 : {
2780 6009284 : df_add_problem (&problem_CHAIN);
2781 6009284 : df_chain->local_flags = chain_flags;
2782 6009284 : df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2783 6009284 : }
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 146633 : df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2829 : {
2830 146633 : unsigned int bb_index;
2831 146633 : bitmap_iterator bi;
2832 146633 : basic_block bb;
2833 146633 : struct df_word_lr_problem_data *problem_data
2834 146633 : = XNEW (struct df_word_lr_problem_data);
2835 :
2836 146633 : df_word_lr->problem_data = problem_data;
2837 :
2838 146633 : 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 146633 : bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2847 :
2848 3789508 : FOR_EACH_BB_FN (bb, cfun)
2849 3642875 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2850 :
2851 146633 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2852 146633 : bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2853 :
2854 4082774 : EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2855 : {
2856 3936141 : 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 3936141 : 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 3936141 : bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2867 3936141 : bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2868 3936141 : bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2869 3936141 : bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2870 : }
2871 : }
2872 :
2873 146633 : df_word_lr->optional_p = true;
2874 146633 : }
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 506945917 : df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2904 : {
2905 506945917 : rtx orig_reg = DF_REF_REG (ref);
2906 506945917 : rtx reg = orig_reg;
2907 506945917 : machine_mode reg_mode;
2908 506945917 : unsigned regno;
2909 : /* Left at -1 for whole accesses. */
2910 506945917 : int which_subword = -1;
2911 506945917 : bool changed = false;
2912 :
2913 506945917 : if (GET_CODE (reg) == SUBREG)
2914 3882797 : reg = SUBREG_REG (orig_reg);
2915 506945917 : regno = REGNO (reg);
2916 506945917 : reg_mode = GET_MODE (reg);
2917 506945917 : if (regno < FIRST_PSEUDO_REGISTER
2918 574324386 : || maybe_ne (GET_MODE_SIZE (reg_mode), 2 * UNITS_PER_WORD))
2919 : return true;
2920 :
2921 9886558 : if (GET_CODE (orig_reg) == SUBREG
2922 9886558 : && read_modify_subreg_p (orig_reg))
2923 : {
2924 1558833 : gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2925 1558833 : if (subreg_lowpart_p (orig_reg))
2926 : which_subword = 0;
2927 : else
2928 743491 : which_subword = 1;
2929 : }
2930 9886558 : if (is_set)
2931 : {
2932 6402342 : if (which_subword != 1)
2933 5896659 : changed |= bitmap_set_bit (live, regno * 2);
2934 5896659 : if (which_subword != 0)
2935 5859800 : changed |= bitmap_set_bit (live, regno * 2 + 1);
2936 : }
2937 : else
2938 : {
2939 3484216 : if (which_subword != 1)
2940 3246408 : changed |= bitmap_clear_bit (live, regno * 2);
2941 3246408 : if (which_subword != 0)
2942 3211416 : 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 3789508 : df_word_lr_bb_local_compute (unsigned int bb_index)
2951 : {
2952 3789508 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2953 3789508 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2954 3789508 : rtx_insn *insn;
2955 3789508 : df_ref def, use;
2956 :
2957 : /* Ensure that artificial refs don't contain references to pseudos. */
2958 10184288 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2959 2605272 : gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2960 :
2961 18361008 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2962 14571500 : gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2963 :
2964 47184518 : FOR_BB_INSNS_REVERSE (bb, insn)
2965 : {
2966 43395010 : if (!NONDEBUG_INSN_P (insn))
2967 22131591 : continue;
2968 :
2969 21263419 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2970 171708142 : 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 150444723 : if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2974 : {
2975 150444723 : df_word_lr_mark_ref (def, true, &bb_info->def);
2976 150444723 : df_word_lr_mark_ref (def, false, &bb_info->use);
2977 : }
2978 49080469 : FOR_EACH_INSN_INFO_USE (use, insn_info)
2979 27817050 : df_word_lr_mark_ref (use, true, &bb_info->use);
2980 : }
2981 3789508 : }
2982 :
2983 :
2984 : /* Compute local live register info for each basic block within BLOCKS. */
2985 :
2986 : static void
2987 146633 : df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2988 : {
2989 146633 : unsigned int bb_index;
2990 146633 : bitmap_iterator bi;
2991 :
2992 4082774 : EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2993 : {
2994 3936141 : if (bb_index == EXIT_BLOCK)
2995 : {
2996 146633 : unsigned regno;
2997 146633 : bitmap_iterator bi;
2998 146633 : EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2999 : regno, bi)
3000 0 : gcc_unreachable ();
3001 : }
3002 : else
3003 3789508 : df_word_lr_bb_local_compute (bb_index);
3004 : }
3005 :
3006 146633 : bitmap_clear (df_word_lr->out_of_date_transfer_functions);
3007 146633 : }
3008 :
3009 :
3010 : /* Initialize the solution vectors. */
3011 :
3012 : static void
3013 146633 : df_word_lr_init (bitmap all_blocks)
3014 : {
3015 146633 : unsigned int bb_index;
3016 146633 : bitmap_iterator bi;
3017 :
3018 4082774 : EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3019 : {
3020 3936141 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
3021 3936141 : bitmap_copy (&bb_info->in, &bb_info->use);
3022 3936141 : bitmap_clear (&bb_info->out);
3023 : }
3024 146633 : }
3025 :
3026 :
3027 : /* Confluence function that ignores fake edges. */
3028 :
3029 : static bool
3030 6049339 : df_word_lr_confluence_n (edge e)
3031 : {
3032 6049339 : bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
3033 6049339 : bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
3034 :
3035 6049339 : return bitmap_ior_into (op1, op2);
3036 : }
3037 :
3038 :
3039 : /* Transfer function. */
3040 :
3041 : static bool
3042 4263617 : df_word_lr_transfer_function (int bb_index)
3043 : {
3044 4263617 : class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
3045 4263617 : bitmap in = &bb_info->in;
3046 4263617 : bitmap out = &bb_info->out;
3047 4263617 : bitmap use = &bb_info->use;
3048 4263617 : bitmap def = &bb_info->def;
3049 :
3050 4263617 : 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 146633 : df_word_lr_free (void)
3058 : {
3059 146633 : struct df_word_lr_problem_data *problem_data
3060 146633 : = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
3061 :
3062 146633 : if (df_word_lr->block_info)
3063 : {
3064 146633 : df_word_lr->block_info_size = 0;
3065 146633 : free (df_word_lr->block_info);
3066 146633 : df_word_lr->block_info = NULL;
3067 : }
3068 :
3069 146633 : BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
3070 146633 : bitmap_obstack_release (&problem_data->word_lr_bitmaps);
3071 146633 : free (problem_data);
3072 146633 : free (df_word_lr);
3073 146633 : }
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 146633 : df_word_lr_add_problem (void)
3146 : {
3147 146633 : df_add_problem (&problem_WORD_LR);
3148 : /* These will be initialized when df_scan_blocks processes each
3149 : block. */
3150 146633 : df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3151 146633 : }
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 21263419 : df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3161 : {
3162 21263419 : bool changed = false;
3163 21263419 : df_ref def;
3164 :
3165 171708142 : FOR_EACH_INSN_DEF (def, insn)
3166 150444723 : if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3167 : changed = true;
3168 : else
3169 150444723 : changed |= df_word_lr_mark_ref (def, false, live);
3170 21263419 : return changed;
3171 : }
3172 :
3173 :
3174 : /* Simulate the effects of the uses of INSN on LIVE. */
3175 :
3176 : void
3177 21249143 : df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3178 : {
3179 21249143 : df_ref use;
3180 :
3181 49043841 : FOR_EACH_INSN_USE (use, insn)
3182 27794698 : df_word_lr_mark_ref (use, true, live);
3183 21249143 : }
3184 :
3185 : /*----------------------------------------------------------------------------
3186 : This problem computes REG_DEAD and REG_UNUSED notes.
3187 : ----------------------------------------------------------------------------*/
3188 :
3189 : static void
3190 15746900 : df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3191 : {
3192 15746900 : df_note->optional_p = true;
3193 15746900 : }
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 1269846549 : df_ignore_stack_reg (int regno)
3215 : {
3216 1269846549 : return regstack_completed
3217 566492769 : && 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 1810873401 : df_remove_dead_and_unused_notes (rtx_insn *insn)
3232 : {
3233 1810873401 : rtx *pprev = ®_NOTES (insn);
3234 1810873401 : rtx link = *pprev;
3235 :
3236 2733561742 : while (link)
3237 : {
3238 922688341 : switch (REG_NOTE_KIND (link))
3239 : {
3240 448834758 : case REG_DEAD:
3241 : /* After reg-stack, we need to ignore any unused notes
3242 : for the stack registers. */
3243 448834758 : 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 448834758 : rtx next = XEXP (link, 1);
3251 448834758 : if (REG_DEAD_DEBUGGING)
3252 : df_print_note ("deleting: ", insn, link);
3253 448834758 : free_EXPR_LIST_node (link);
3254 448834758 : *pprev = link = next;
3255 : }
3256 : break;
3257 :
3258 117658011 : case REG_UNUSED:
3259 : /* After reg-stack, we need to ignore any unused notes
3260 : for the stack registers. */
3261 117658011 : 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 117658011 : rtx next = XEXP (link, 1);
3269 117658011 : if (REG_DEAD_DEBUGGING)
3270 : df_print_note ("deleting: ", insn, link);
3271 117658011 : free_EXPR_LIST_node (link);
3272 117658011 : *pprev = link = next;
3273 : }
3274 : break;
3275 :
3276 356195572 : default:
3277 356195572 : pprev = &XEXP (link, 1);
3278 356195572 : link = *pprev;
3279 356195572 : break;
3280 : }
3281 : }
3282 1810873401 : }
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 1810873401 : df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3289 : {
3290 1810873401 : rtx *pprev = ®_NOTES (insn);
3291 1810873401 : rtx link = *pprev;
3292 :
3293 2867895071 : while (link)
3294 : {
3295 1057021670 : switch (REG_NOTE_KIND (link))
3296 : {
3297 69106040 : case REG_EQUAL:
3298 69106040 : case REG_EQUIV:
3299 69106040 : {
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 69106040 : df_ref use;
3305 69106040 : bool deleted = false;
3306 :
3307 117539646 : FOR_EACH_INSN_EQ_USE (use, insn)
3308 48797792 : if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
3309 10026253 : && DF_REF_LOC (use)
3310 10026253 : && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3311 10026253 : && !bitmap_bit_p (live, DF_REF_REGNO (use))
3312 49163451 : && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3313 : {
3314 : deleted = true;
3315 : break;
3316 : }
3317 69106040 : if (deleted)
3318 : {
3319 364186 : rtx next;
3320 364186 : if (REG_DEAD_DEBUGGING)
3321 : df_print_note ("deleting: ", insn, link);
3322 364186 : next = XEXP (link, 1);
3323 364186 : free_EXPR_LIST_node (link);
3324 364186 : *pprev = link = next;
3325 364186 : df_notes_rescan (insn);
3326 : }
3327 : else
3328 : {
3329 68741854 : pprev = &XEXP (link, 1);
3330 68741854 : link = *pprev;
3331 : }
3332 : break;
3333 : }
3334 :
3335 987915630 : default:
3336 987915630 : pprev = &XEXP (link, 1);
3337 987915630 : link = *pprev;
3338 987915630 : break;
3339 : }
3340 : }
3341 1810873401 : }
3342 :
3343 : /* Set a NOTE_TYPE note for REG in INSN. */
3344 :
3345 : static inline void
3346 700826098 : df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3347 : {
3348 700826098 : gcc_checking_assert (!DEBUG_INSN_P (insn));
3349 700826098 : add_reg_note (insn, note_type, reg);
3350 700826098 : }
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 2589817 : df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3359 : bitmap live, bitmap artificial_uses)
3360 : {
3361 2589817 : unsigned int r;
3362 :
3363 : /* If MWS describes a partial reference, create REG_UNUSED notes for
3364 : individual hard registers. */
3365 2589817 : if (mws->flags & DF_REF_PARTIAL)
3366 : return false;
3367 :
3368 : /* Likewise if some part of the register is used. */
3369 2936325 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3370 2775655 : if (bitmap_bit_p (live, r)
3371 2775655 : || bitmap_bit_p (artificial_uses, r))
3372 2429147 : return false;
3373 :
3374 160670 : 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 2589817 : 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 2589817 : unsigned int r;
3393 :
3394 2589817 : 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 2589817 : if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3399 : {
3400 160670 : unsigned int regno = mws->start_regno;
3401 160670 : df_set_note (REG_UNUSED, insn, mws->mw_reg);
3402 160670 : dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3403 :
3404 160670 : if (REG_DEAD_DEBUGGING)
3405 : df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3406 :
3407 160670 : bitmap_set_bit (do_not_gen, regno);
3408 : /* Only do this if the value is totally dead. */
3409 : }
3410 : else
3411 7287441 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3412 : {
3413 4858294 : if (!bitmap_bit_p (live, r)
3414 4858294 : && !bitmap_bit_p (artificial_uses, r))
3415 : {
3416 105734 : df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3417 105734 : dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3418 105734 : if (REG_DEAD_DEBUGGING)
3419 : df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3420 : }
3421 4858294 : bitmap_set_bit (do_not_gen, r);
3422 : }
3423 2589817 : }
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 2062158 : df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3433 : bitmap live, bitmap artificial_uses,
3434 : bitmap do_not_gen)
3435 : {
3436 2062158 : unsigned int r;
3437 :
3438 : /* If MWS describes a partial reference, create REG_DEAD notes for
3439 : individual hard registers. */
3440 2062158 : if (mws->flags & DF_REF_PARTIAL)
3441 : return false;
3442 :
3443 : /* Likewise if some part of the register is not dead. */
3444 4310507 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3445 3186233 : if (bitmap_bit_p (live, r)
3446 2472127 : || bitmap_bit_p (artificial_uses, r)
3447 5658360 : || bitmap_bit_p (do_not_gen, r))
3448 936787 : return false;
3449 :
3450 1124274 : 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 2062158 : 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 2062158 : unsigned int r;
3465 2062158 : bool is_debug = *added_notes_p;
3466 :
3467 2062158 : *added_notes_p = false;
3468 :
3469 2062158 : 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 2062158 : if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3481 : {
3482 1124274 : if (is_debug)
3483 : {
3484 388 : *added_notes_p = true;
3485 388 : return;
3486 : }
3487 : /* Add a dead note for the entire multi word register. */
3488 1123886 : df_set_note (REG_DEAD, insn, mws->mw_reg);
3489 1123886 : if (REG_DEAD_DEBUGGING)
3490 : df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3491 : }
3492 : else
3493 : {
3494 2810908 : for (r = mws->start_regno; r <= mws->end_regno; r++)
3495 1874886 : if (!bitmap_bit_p (live, r)
3496 447144 : && !bitmap_bit_p (artificial_uses, r)
3497 2322030 : && !bitmap_bit_p (do_not_gen, r))
3498 : {
3499 151548 : if (is_debug)
3500 : {
3501 1862 : *added_notes_p = true;
3502 1862 : return;
3503 : }
3504 149686 : df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3505 149686 : 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 863735534 : df_create_unused_note (rtx_insn *insn, df_ref def,
3518 : bitmap live, bitmap artificial_uses,
3519 : struct dead_debug_local *debug)
3520 : {
3521 863735534 : unsigned int dregno = DF_REF_REGNO (def);
3522 :
3523 863735534 : 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 863735534 : if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3530 858555900 : || bitmap_bit_p (live, dregno)
3531 143548482 : || bitmap_bit_p (artificial_uses, dregno)
3532 143533220 : || df_ignore_stack_reg (dregno)))
3533 : {
3534 287066440 : rtx reg = (DF_REF_LOC (def))
3535 143533220 : ? *DF_REF_REAL_LOC (def) : DF_REF_REG (def);
3536 143533220 : df_set_note (REG_UNUSED, insn, reg);
3537 143533220 : dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3538 143533220 : if (REG_DEAD_DEBUGGING)
3539 : df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3540 : }
3541 :
3542 863735534 : 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 211885512 : df_note_bb_compute (unsigned int bb_index,
3552 : bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3553 : {
3554 211885512 : basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3555 211885512 : rtx_insn *insn;
3556 211885512 : df_ref def, use;
3557 211885512 : struct dead_debug_local debug;
3558 :
3559 211885512 : dead_debug_local_init (&debug, NULL, NULL);
3560 :
3561 211885512 : bitmap_copy (live, df_get_live_out (bb));
3562 211885512 : bitmap_clear (artificial_uses);
3563 :
3564 211885512 : 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 693151117 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3573 : {
3574 269380093 : if (REG_DEAD_DEBUGGING && dump_file)
3575 : fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3576 :
3577 269380093 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3578 263450868 : bitmap_clear_bit (live, DF_REF_REGNO (def));
3579 : }
3580 :
3581 979930444 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3582 556159420 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3583 : {
3584 556159420 : unsigned int regno = DF_REF_REGNO (use);
3585 556159420 : 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 556159420 : bitmap_set_bit (artificial_uses, regno);
3590 : }
3591 :
3592 211885512 : 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 2372734807 : FOR_BB_INSNS_REVERSE (bb, insn)
3599 : {
3600 2510825189 : if (!INSN_P (insn))
3601 349975894 : continue;
3602 :
3603 1810873401 : df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3604 1810873401 : df_mw_hardreg *mw;
3605 1810873401 : int debug_insn;
3606 :
3607 1810873401 : debug_insn = DEBUG_INSN_P (insn);
3608 :
3609 1810873401 : bitmap_clear (do_not_gen);
3610 1810873401 : df_remove_dead_and_unused_notes (insn);
3611 :
3612 : /* Process the defs. */
3613 1810873401 : if (CALL_P (insn))
3614 : {
3615 74406854 : 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 77051930 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3625 2645076 : if ((DF_MWS_REG_DEF_P (mw))
3626 4460281 : && !df_ignore_stack_reg (mw->start_regno))
3627 1815205 : 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 6161769370 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3633 : {
3634 6087362516 : unsigned int dregno = DF_REF_REGNO (def);
3635 6087362516 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3636 : {
3637 35199164 : df_create_unused_note (insn,
3638 : def, live, artificial_uses, &debug);
3639 35199164 : bitmap_set_bit (do_not_gen, dregno);
3640 : }
3641 :
3642 6087362516 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3643 6087362516 : bitmap_clear_bit (live, dregno);
3644 : }
3645 : }
3646 : else
3647 : {
3648 : /* Regular insn. */
3649 1738473446 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3650 2006899 : if (DF_MWS_REG_DEF_P (mw))
3651 774612 : df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3652 : artificial_uses, &debug);
3653 :
3654 2565002917 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3655 : {
3656 828536370 : unsigned int dregno = DF_REF_REGNO (def);
3657 828536370 : df_create_unused_note (insn,
3658 : def, live, artificial_uses, &debug);
3659 :
3660 828536370 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3661 696663411 : bitmap_set_bit (do_not_gen, dregno);
3662 :
3663 828536370 : if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3664 825943447 : bitmap_clear_bit (live, dregno);
3665 : }
3666 : }
3667 :
3668 : /* Process the uses. */
3669 1815525376 : FOR_EACH_INSN_INFO_MW (mw, insn_info)
3670 4651975 : if (DF_MWS_REG_USE_P (mw)
3671 6714133 : && !df_ignore_stack_reg (mw->start_regno))
3672 : {
3673 2062158 : bool really_add_notes = debug_insn != 0;
3674 :
3675 2062158 : df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3676 : artificial_uses,
3677 : &really_add_notes);
3678 :
3679 2062158 : if (really_add_notes)
3680 2250 : debug_insn = -1;
3681 : }
3682 :
3683 3266989667 : FOR_EACH_INSN_INFO_USE (use, insn_info)
3684 : {
3685 1456118516 : unsigned int uregno = DF_REF_REGNO (use);
3686 :
3687 1456118516 : 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 1456118516 : if (!bitmap_bit_p (live, uregno))
3694 : {
3695 698221747 : if (debug_insn)
3696 : {
3697 192545 : 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 190295 : if (!bitmap_bit_p (artificial_uses, uregno)
3703 190295 : && !df_ignore_stack_reg (uregno))
3704 190295 : dead_debug_add (&debug, use, uregno);
3705 190295 : continue;
3706 : }
3707 : break;
3708 : }
3709 : else
3710 698029202 : dead_debug_insert_temp (&debug, uregno, insn,
3711 : DEBUG_TEMP_BEFORE_WITH_REG);
3712 :
3713 698029202 : if ( (!(DF_REF_FLAGS (use)
3714 : & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3715 695334538 : && (!bitmap_bit_p (do_not_gen, uregno))
3716 556236251 : && (!bitmap_bit_p (artificial_uses, uregno))
3717 1253782104 : && (!df_ignore_stack_reg (uregno)))
3718 : {
3719 1111501877 : rtx reg = (DF_REF_LOC (use))
3720 555748975 : ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3721 555752902 : df_set_note (REG_DEAD, insn, reg);
3722 :
3723 555752902 : if (REG_DEAD_DEBUGGING)
3724 : df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3725 : }
3726 : /* This register is now live. */
3727 698029202 : bitmap_set_bit (live, uregno);
3728 : }
3729 : }
3730 :
3731 1810873401 : df_remove_dead_eq_notes (insn, live);
3732 :
3733 1810873401 : if (debug_insn == -1)
3734 : {
3735 : /* ??? We could probably do better here, replacing dead
3736 : registers with their definitions. */
3737 2250 : INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3738 2250 : df_insn_rescan_debug_internal (insn);
3739 : }
3740 : }
3741 :
3742 211885512 : dead_debug_local_finish (&debug, NULL);
3743 211885512 : }
3744 :
3745 :
3746 : /* Compute register info: lifetime, bb, and number of defs and uses. */
3747 : static void
3748 15746900 : df_note_compute (bitmap all_blocks)
3749 : {
3750 15746900 : unsigned int bb_index;
3751 15746900 : bitmap_iterator bi;
3752 15746900 : bitmap_head live, do_not_gen, artificial_uses;
3753 :
3754 15746900 : bitmap_initialize (&live, &df_bitmap_obstack);
3755 15746900 : bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3756 15746900 : bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3757 :
3758 227632412 : 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 211885512 : df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3766 : }
3767 :
3768 15746900 : bitmap_clear (&live);
3769 15746900 : bitmap_clear (&do_not_gen);
3770 15746900 : bitmap_clear (&artificial_uses);
3771 15746900 : }
3772 :
3773 :
3774 : /* Free all storage associated with the problem. */
3775 :
3776 : static void
3777 11231096 : df_note_free (void)
3778 : {
3779 11231096 : free (df_note);
3780 11231096 : }
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 11687587 : df_note_add_problem (void)
3821 : {
3822 11687587 : df_add_problem (&problem_NOTE);
3823 11687587 : }
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 1872851 : df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3850 : {
3851 1872851 : df_ref def;
3852 :
3853 3264460 : FOR_EACH_INSN_DEF (def, insn)
3854 1391609 : bitmap_set_bit (defs, DF_REF_REGNO (def));
3855 1872851 : }
3856 :
3857 : /* Find the set of uses for INSN. This includes partial defs. */
3858 :
3859 : static void
3860 479501 : df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3861 : {
3862 479501 : df_ref def, use;
3863 479501 : struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3864 :
3865 1007644 : FOR_EACH_INSN_INFO_DEF (def, insn_info)
3866 528143 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3867 478 : bitmap_set_bit (uses, DF_REF_REGNO (def));
3868 871901 : FOR_EACH_INSN_INFO_USE (use, insn_info)
3869 392400 : bitmap_set_bit (uses, DF_REF_REGNO (use));
3870 479501 : }
3871 :
3872 : /* Find the set of real DEFs, which are not clobbers, for INSN. */
3873 :
3874 : void
3875 393324987 : df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3876 : {
3877 393324987 : df_ref def;
3878 :
3879 2121748519 : FOR_EACH_INSN_DEF (def, insn)
3880 1728423532 : if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3881 173405381 : bitmap_set_bit (defs, DF_REF_REGNO (def));
3882 393324987 : }
3883 :
3884 :
3885 : /* Simulate the effects of the defs of INSN on LIVE. */
3886 :
3887 : void
3888 916777505 : df_simulate_defs (rtx_insn *insn, bitmap live)
3889 : {
3890 916777505 : df_ref def;
3891 :
3892 7235271531 : FOR_EACH_INSN_DEF (def, insn)
3893 : {
3894 6318494026 : 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 6318494026 : if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3899 2657047 : bitmap_set_bit (live, dregno);
3900 : else
3901 6315836979 : bitmap_clear_bit (live, dregno);
3902 : }
3903 916777505 : }
3904 :
3905 :
3906 : /* Simulate the effects of the uses of INSN on LIVE. */
3907 :
3908 : void
3909 913431999 : df_simulate_uses (rtx_insn *insn, bitmap live)
3910 : {
3911 913431999 : df_ref use;
3912 :
3913 913431999 : if (DEBUG_INSN_P (insn))
3914 : return;
3915 :
3916 2076234732 : FOR_EACH_INSN_USE (use, insn)
3917 : /* Add use to set of uses in this BB. */
3918 1162802733 : 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 397045590 : 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 397045590 : if (bb_has_eh_pred (bb))
3930 1339276 : bitmap_ior_into (live, &df->eh_block_artificial_uses);
3931 : else
3932 395706314 : bitmap_ior_into (live, &df->regular_block_artificial_uses);
3933 397045590 : }
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 173251721 : df_simulate_initialize_backwards (basic_block bb, bitmap live)
3953 : {
3954 173251721 : df_ref def, use;
3955 173251721 : int bb_index = bb->index;
3956 :
3957 352961731 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3958 6458289 : if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3959 0 : bitmap_clear_bit (live, DF_REF_REGNO (def));
3960 :
3961 867402974 : FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3962 520899532 : if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3963 520899532 : bitmap_set_bit (live, DF_REF_REGNO (use));
3964 173251721 : }
3965 :
3966 :
3967 : /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3968 :
3969 : void
3970 4372873 : df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3971 : {
3972 4372873 : if (!NONDEBUG_INSN_P (insn))
3973 : return;
3974 :
3975 3720603 : df_simulate_defs (insn, live);
3976 3720603 : df_simulate_uses (insn, live);
3977 3720603 : 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 171952330 : df_simulate_finalize_backwards (basic_block bb, bitmap live)
3986 : {
3987 171952330 : df_ref def;
3988 : #ifdef EH_USES
3989 : df_ref use;
3990 : #endif
3991 171952330 : int bb_index = bb->index;
3992 :
3993 350362949 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3994 6458289 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3995 6458289 : 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 171952330 : }
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 48546428 : df_simulate_initialize_forwards (basic_block bb, bitmap live)
4021 : {
4022 48546428 : df_ref def;
4023 48546428 : int bb_index = bb->index;
4024 :
4025 134491759 : FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4026 37398903 : if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4027 1444928 : bitmap_set_bit (live, DF_REF_REGNO (def));
4028 48546428 : }
4029 :
4030 : /* Simulate the forwards effects of INSN on the bitmap LIVE. */
4031 :
4032 : void
4033 393324987 : df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
4034 : {
4035 393324987 : rtx link;
4036 393324987 : if (! INSN_P (insn))
4037 : return;
4038 :
4039 : /* Make sure that DF_NOTE really is an active df problem. */
4040 393324987 : 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 393324987 : df_simulate_find_noclobber_defs (insn, live);
4048 :
4049 : /* Clear all of the registers that go dead. */
4050 637408265 : for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4051 : {
4052 244083278 : switch (REG_NOTE_KIND (link))
4053 : {
4054 151139822 : case REG_DEAD:
4055 151139822 : case REG_UNUSED:
4056 151139822 : {
4057 151139822 : rtx reg = XEXP (link, 0);
4058 151139822 : bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
4059 : }
4060 151139822 : break;
4061 : default:
4062 : break;
4063 : }
4064 : }
4065 393324987 : 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 1542005 : find_memory (rtx_insn *insn)
4077 : {
4078 1542005 : int flags = 0;
4079 1542005 : subrtx_iterator::array_type array;
4080 11227171 : FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
4081 : {
4082 9685166 : const_rtx x = *iter;
4083 9685166 : if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
4084 0 : flags |= MEMREF_VOLATILE;
4085 9685166 : else if (MEM_P (x))
4086 : {
4087 161293 : if (MEM_VOLATILE_P (x))
4088 823 : flags |= MEMREF_VOLATILE;
4089 160470 : else if (!MEM_READONLY_P (x))
4090 155341 : flags |= MEMREF_NORMAL;
4091 : }
4092 : }
4093 1542005 : return flags;
4094 1542005 : }
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 1605191 : find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4103 : void *data ATTRIBUTE_UNUSED)
4104 : {
4105 1605191 : int *pflags = (int *)data;
4106 1605191 : 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 1605191 : if (x == stack_pointer_rtx)
4111 3200 : *pflags |= MEMREF_VOLATILE;
4112 1605191 : if (!MEM_P (x))
4113 : return;
4114 62592 : *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 669441 : simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4122 : {
4123 669441 : rtx_insn *insn;
4124 669441 : bitmap_copy (live, df_get_live_out (bb));
4125 669441 : df_simulate_initialize_backwards (bb, live);
4126 :
4127 : /* Scan and update life information until we reach the point we're
4128 : interested in. */
4129 2096566 : for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4130 1427125 : df_simulate_one_insn_backwards (bb, insn, live);
4131 669441 : }
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 628995 : 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 628995 : rtx_insn *insn, *next, *max_to;
4161 628995 : bitmap merge_set, merge_use, local_merge_live;
4162 628995 : bitmap test_set, test_use;
4163 628995 : unsigned i, fail = 0;
4164 628995 : bitmap_iterator bi;
4165 628995 : int memrefs_in_across = 0;
4166 628995 : int mem_sets_in_across = 0;
4167 628995 : bool trapping_insns_in_across = false;
4168 :
4169 628995 : if (pmove_upto != NULL)
4170 187996 : *pmove_upto = NULL;
4171 :
4172 : /* Find real bounds, ignoring debug insns. */
4173 636636 : while (!NONDEBUG_INSN_P (from) && from != to)
4174 7641 : from = NEXT_INSN (from);
4175 630286 : while (!NONDEBUG_INSN_P (to) && from != to)
4176 1291 : to = PREV_INSN (to);
4177 :
4178 : for (insn = across_to; ; insn = next)
4179 : {
4180 1207776 : if (CALL_P (insn))
4181 : {
4182 1218 : 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 166 : memrefs_in_across |= MEMREF_NORMAL;
4187 : else
4188 : {
4189 1052 : memrefs_in_across |= MEMREF_VOLATILE;
4190 1052 : mem_sets_in_across |= MEMREF_VOLATILE;
4191 : }
4192 : }
4193 1207776 : if (NONDEBUG_INSN_P (insn))
4194 : {
4195 1196543 : if (volatile_insn_p (PATTERN (insn)))
4196 : return false;
4197 1196537 : memrefs_in_across |= find_memory (insn);
4198 1196537 : note_stores (insn, find_memory_stores, &mem_sets_in_across);
4199 : /* This is used just to find sets of the stack pointer. */
4200 1196537 : memrefs_in_across |= mem_sets_in_across;
4201 1196537 : trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4202 : }
4203 1207770 : next = PREV_INSN (insn);
4204 1207770 : 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 628989 : merge_set = BITMAP_ALLOC (®_obstack);
4218 628989 : merge_use = BITMAP_ALLOC (®_obstack);
4219 628989 : local_merge_live = BITMAP_ALLOC (®_obstack);
4220 628989 : test_set = BITMAP_ALLOC (®_obstack);
4221 628989 : test_use = BITMAP_ALLOC (®_obstack);
4222 :
4223 : /* Compute the set of registers set and used in the ACROSS range. */
4224 628989 : if (other_branch_live != NULL)
4225 440999 : bitmap_copy (test_use, other_branch_live);
4226 628989 : df_simulate_initialize_backwards (merge_bb, test_use);
4227 628989 : for (insn = across_to; ; insn = next)
4228 : {
4229 1207750 : if (NONDEBUG_INSN_P (insn))
4230 : {
4231 1196535 : df_simulate_find_defs (insn, test_set);
4232 1196535 : df_simulate_defs (insn, test_use);
4233 1196535 : df_simulate_uses (insn, test_use);
4234 : }
4235 1207750 : next = PREV_INSN (insn);
4236 1207750 : 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 713876 : if (CALL_P (insn))
4248 : break;
4249 697708 : if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4250 : break;
4251 697708 : if (NONDEBUG_INSN_P (insn))
4252 : {
4253 672370 : if (may_trap_or_fault_p (PATTERN (insn))
4254 672370 : && (trapping_insns_in_across
4255 169214 : || other_branch_live != NULL
4256 8062 : || 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 511079 : if (other_branch_live != NULL || memrefs_in_across != 0)
4274 : {
4275 345468 : int mem_ref_flags = 0;
4276 345468 : int mem_set_flags = 0;
4277 345468 : note_stores (insn, find_memory_stores, &mem_set_flags);
4278 345468 : mem_ref_flags = find_memory (insn);
4279 : /* Catch sets of the stack pointer. */
4280 345468 : mem_ref_flags |= mem_set_flags;
4281 :
4282 345468 : if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4283 : break;
4284 342504 : if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4285 : break;
4286 342060 : if (mem_set_flags != 0
4287 313989 : || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4288 : break;
4289 : }
4290 479501 : 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 479501 : bitmap_and_compl_into (merge_use, merge_set);
4294 479501 : df_simulate_find_defs (insn, merge_set);
4295 479501 : if (bitmap_intersect_p (merge_set, test_use)
4296 479501 : || bitmap_intersect_p (merge_use, test_set))
4297 : break;
4298 : max_to = insn;
4299 : }
4300 325398 : next = NEXT_INSN (insn);
4301 325398 : if (insn == to)
4302 : break;
4303 : }
4304 628989 : if (max_to != to)
4305 388500 : fail = 1;
4306 :
4307 628989 : if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4308 384277 : 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 244712 : bitmap_copy (local_merge_live, merge_live);
4325 509283 : for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4326 19859 : 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 244712 : bitmap_and_into (local_merge_live, merge_set);
4331 2600 : for (;;)
4332 : {
4333 247312 : if (NONDEBUG_INSN_P (insn))
4334 : {
4335 246453 : if (!bitmap_intersect_p (test_set, local_merge_live))
4336 : {
4337 192470 : max_to = insn;
4338 192470 : break;
4339 : }
4340 :
4341 53983 : df_simulate_one_insn_backwards (merge_bb, insn,
4342 : local_merge_live);
4343 : }
4344 54842 : if (insn == from)
4345 : {
4346 52242 : fail = 1;
4347 52242 : goto out;
4348 : }
4349 2600 : insn = PREV_INSN (insn);
4350 : }
4351 :
4352 192470 : if (max_to != to)
4353 5261 : fail = 1;
4354 :
4355 192470 : if (pmove_upto)
4356 42747 : *pmove_upto = max_to;
4357 :
4358 : /* For small register class machines, don't lengthen lifetimes of
4359 : hard registers before reload. */
4360 192470 : if (! reload_completed
4361 192470 : && targetm.small_register_classes_for_mode_p (VOIDmode))
4362 : {
4363 260947 : EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4364 : {
4365 143544 : if (i < FIRST_PSEUDO_REGISTER
4366 8511 : && ! fixed_regs[i]
4367 0 : && ! global_regs[i])
4368 : {
4369 : fail = 1;
4370 : break;
4371 : }
4372 : }
4373 : }
4374 :
4375 628989 : out:
4376 628989 : BITMAP_FREE (merge_set);
4377 628989 : BITMAP_FREE (merge_use);
4378 628989 : BITMAP_FREE (local_merge_live);
4379 628989 : BITMAP_FREE (test_set);
4380 628989 : BITMAP_FREE (test_use);
4381 :
4382 628989 : 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 :
|
