gcc/testsuite
[official-gcc.git] / gcc / df-problems.c
blob6dbc126b69861fc8f5e88a1e20a13e32ee3a215f
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2016 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).
8 This file is part of GCC.
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.
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.
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/>. */
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"
40 /* Note that turning REG_DEAD_DEBUGGING on will cause
41 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
42 addresses in the dumps. */
43 #define REG_DEAD_DEBUGGING 0
45 #define DF_SPARSE_THRESHOLD 32
47 static bitmap_head seen_in_block;
48 static bitmap_head seen_in_insn;
50 /*----------------------------------------------------------------------------
51 Utility functions.
52 ----------------------------------------------------------------------------*/
54 /* Generic versions to get the void* version of the block info. Only
55 used inside the problem instance vectors. */
57 /* Dump a def-use or use-def chain for REF to FILE. */
59 void
60 df_chain_dump (struct df_link *link, FILE *file)
62 fprintf (file, "{ ");
63 for (; link; link = link->next)
65 fprintf (file, "%c%d(bb %d insn %d) ",
66 DF_REF_REG_DEF_P (link->ref)
67 ? 'd'
68 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
69 DF_REF_ID (link->ref),
70 DF_REF_BBNO (link->ref),
71 DF_REF_IS_ARTIFICIAL (link->ref)
72 ? -1 : DF_REF_INSN_UID (link->ref));
74 fprintf (file, "}");
78 /* Print some basic block info as part of df_dump. */
80 void
81 df_print_bb_index (basic_block bb, FILE *file)
83 edge e;
84 edge_iterator ei;
86 fprintf (file, "\n( ");
87 FOR_EACH_EDGE (e, ei, bb->preds)
89 basic_block pred = e->src;
90 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
92 fprintf (file, ")->[%d]->( ", bb->index);
93 FOR_EACH_EDGE (e, ei, bb->succs)
95 basic_block succ = e->dest;
96 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
98 fprintf (file, ")\n");
102 /*----------------------------------------------------------------------------
103 REACHING DEFINITIONS
105 Find the locations in the function where each definition site for a
106 pseudo reaches. In and out bitvectors are built for each basic
107 block. The id field in the ref is used to index into these sets.
108 See df.h for details.
110 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
111 existing uses are included in the global reaching DEFs set, or in other
112 words only DEFs that are still live. This is a kind of pruned version
113 of the traditional reaching definitions problem that is much less
114 complex to compute and produces enough information to compute UD-chains.
115 In this context, live must be interpreted in the DF_LR sense: Uses that
116 are upward exposed but maybe not initialized on all paths through the
117 CFG. For a USE that is not reached by a DEF on all paths, we still want
118 to make those DEFs that do reach the USE visible, and pruning based on
119 DF_LIVE would make that impossible.
120 ----------------------------------------------------------------------------*/
122 /* This problem plays a large number of games for the sake of
123 efficiency.
125 1) The order of the bits in the bitvectors. After the scanning
126 phase, all of the defs are sorted. All of the defs for the reg 0
127 are first, followed by all defs for reg 1 and so on.
129 2) There are two kill sets, one if the number of defs is less or
130 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
131 greater.
133 <= : Data is built directly in the kill set.
135 > : One level of indirection is used to keep from generating long
136 strings of 1 bits in the kill sets. Bitvectors that are indexed
137 by the regnum are used to represent that there is a killing def
138 for the register. The confluence and transfer functions use
139 these along with the bitmap_clear_range call to remove ranges of
140 bits without actually generating a knockout vector.
142 The kill and sparse_kill and the dense_invalidated_by_call and
143 sparse_invalidated_by_call both play this game. */
145 /* Private data used to compute the solution for this problem. These
146 data structures are not accessible outside of this module. */
147 struct df_rd_problem_data
149 /* The set of defs to regs invalidated by call. */
150 bitmap_head sparse_invalidated_by_call;
151 /* The set of defs to regs invalidate by call for rd. */
152 bitmap_head dense_invalidated_by_call;
153 /* An obstack for the bitmaps we need for this problem. */
154 bitmap_obstack rd_bitmaps;
158 /* Free basic block info. */
160 static void
161 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
162 void *vbb_info)
164 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
165 if (bb_info)
167 bitmap_clear (&bb_info->kill);
168 bitmap_clear (&bb_info->sparse_kill);
169 bitmap_clear (&bb_info->gen);
170 bitmap_clear (&bb_info->in);
171 bitmap_clear (&bb_info->out);
176 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
177 not touched unless the block is new. */
179 static void
180 df_rd_alloc (bitmap all_blocks)
182 unsigned int bb_index;
183 bitmap_iterator bi;
184 struct df_rd_problem_data *problem_data;
186 if (df_rd->problem_data)
188 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
189 bitmap_clear (&problem_data->sparse_invalidated_by_call);
190 bitmap_clear (&problem_data->dense_invalidated_by_call);
192 else
194 problem_data = XNEW (struct df_rd_problem_data);
195 df_rd->problem_data = problem_data;
197 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
198 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
199 &problem_data->rd_bitmaps);
200 bitmap_initialize (&problem_data->dense_invalidated_by_call,
201 &problem_data->rd_bitmaps);
204 df_grow_bb_info (df_rd);
206 /* Because of the clustering of all use sites for the same pseudo,
207 we have to process all of the blocks before doing the analysis. */
209 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
211 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
213 /* When bitmaps are already initialized, just clear them. */
214 if (bb_info->kill.obstack)
216 bitmap_clear (&bb_info->kill);
217 bitmap_clear (&bb_info->sparse_kill);
218 bitmap_clear (&bb_info->gen);
220 else
222 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
223 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
224 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
225 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
226 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
229 df_rd->optional_p = true;
233 /* Add the effect of the top artificial defs of BB to the reaching definitions
234 bitmap LOCAL_RD. */
236 void
237 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
239 int bb_index = bb->index;
240 df_ref def;
241 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
242 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
244 unsigned int dregno = DF_REF_REGNO (def);
245 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
246 bitmap_clear_range (local_rd,
247 DF_DEFS_BEGIN (dregno),
248 DF_DEFS_COUNT (dregno));
249 bitmap_set_bit (local_rd, DF_REF_ID (def));
253 /* Add the effect of the defs of INSN to the reaching definitions bitmap
254 LOCAL_RD. */
256 void
257 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
258 bitmap local_rd)
260 df_ref def;
262 FOR_EACH_INSN_DEF (def, insn)
264 unsigned int dregno = DF_REF_REGNO (def);
265 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
266 || (dregno >= FIRST_PSEUDO_REGISTER))
268 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
269 bitmap_clear_range (local_rd,
270 DF_DEFS_BEGIN (dregno),
271 DF_DEFS_COUNT (dregno));
272 if (!(DF_REF_FLAGS (def)
273 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
274 bitmap_set_bit (local_rd, DF_REF_ID (def));
279 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
280 more complicated than just simulating, because we must produce the
281 gen and kill sets and hence deal with the two possible representations
282 of kill sets. */
284 static void
285 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
286 df_ref def,
287 int top_flag)
289 for (; def; def = DF_REF_NEXT_LOC (def))
291 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
293 unsigned int regno = DF_REF_REGNO (def);
294 unsigned int begin = DF_DEFS_BEGIN (regno);
295 unsigned int n_defs = DF_DEFS_COUNT (regno);
297 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
298 || (regno >= FIRST_PSEUDO_REGISTER))
300 /* Only the last def(s) for a regno in the block has any
301 effect. */
302 if (!bitmap_bit_p (&seen_in_block, regno))
304 /* The first def for regno in insn gets to knock out the
305 defs from other instructions. */
306 if ((!bitmap_bit_p (&seen_in_insn, regno))
307 /* If the def is to only part of the reg, it does
308 not kill the other defs that reach here. */
309 && (!(DF_REF_FLAGS (def) &
310 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
312 if (n_defs > DF_SPARSE_THRESHOLD)
314 bitmap_set_bit (&bb_info->sparse_kill, regno);
315 bitmap_clear_range (&bb_info->gen, begin, n_defs);
317 else
319 bitmap_set_range (&bb_info->kill, begin, n_defs);
320 bitmap_clear_range (&bb_info->gen, begin, n_defs);
324 bitmap_set_bit (&seen_in_insn, regno);
325 /* All defs for regno in the instruction may be put into
326 the gen set. */
327 if (!(DF_REF_FLAGS (def)
328 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
329 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
336 /* Compute local reaching def info for basic block BB. */
338 static void
339 df_rd_bb_local_compute (unsigned int bb_index)
341 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
342 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
343 rtx_insn *insn;
345 bitmap_clear (&seen_in_block);
346 bitmap_clear (&seen_in_insn);
348 /* Artificials are only hard regs. */
349 if (!(df->changeable_flags & DF_NO_HARD_REGS))
350 df_rd_bb_local_compute_process_def (bb_info,
351 df_get_artificial_defs (bb_index),
354 FOR_BB_INSNS_REVERSE (bb, insn)
356 unsigned int uid = INSN_UID (insn);
358 if (!INSN_P (insn))
359 continue;
361 df_rd_bb_local_compute_process_def (bb_info,
362 DF_INSN_UID_DEFS (uid), 0);
364 /* This complex dance with the two bitmaps is required because
365 instructions can assign twice to the same pseudo. This
366 generally happens with calls that will have one def for the
367 result and another def for the clobber. If only one vector
368 is used and the clobber goes first, the result will be
369 lost. */
370 bitmap_ior_into (&seen_in_block, &seen_in_insn);
371 bitmap_clear (&seen_in_insn);
374 /* Process the artificial defs at the top of the block last since we
375 are going backwards through the block and these are logically at
376 the start. */
377 if (!(df->changeable_flags & DF_NO_HARD_REGS))
378 df_rd_bb_local_compute_process_def (bb_info,
379 df_get_artificial_defs (bb_index),
380 DF_REF_AT_TOP);
384 /* Compute local reaching def info for each basic block within BLOCKS. */
386 static void
387 df_rd_local_compute (bitmap all_blocks)
389 unsigned int bb_index;
390 bitmap_iterator bi;
391 unsigned int regno;
392 struct df_rd_problem_data *problem_data
393 = (struct df_rd_problem_data *) df_rd->problem_data;
394 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
395 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
397 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
398 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
400 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
402 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
404 df_rd_bb_local_compute (bb_index);
407 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
408 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
410 if (! HARD_REGISTER_NUM_P (regno)
411 || !(df->changeable_flags & DF_NO_HARD_REGS))
413 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
414 bitmap_set_bit (sparse_invalidated, regno);
415 else
416 bitmap_set_range (dense_invalidated,
417 DF_DEFS_BEGIN (regno),
418 DF_DEFS_COUNT (regno));
422 bitmap_clear (&seen_in_block);
423 bitmap_clear (&seen_in_insn);
427 /* Initialize the solution bit vectors for problem. */
429 static void
430 df_rd_init_solution (bitmap all_blocks)
432 unsigned int bb_index;
433 bitmap_iterator bi;
435 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
437 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
439 bitmap_copy (&bb_info->out, &bb_info->gen);
440 bitmap_clear (&bb_info->in);
444 /* In of target gets or of out of source. */
446 static bool
447 df_rd_confluence_n (edge e)
449 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
450 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
451 bool changed = false;
453 if (e->flags & EDGE_FAKE)
454 return false;
456 if (e->flags & EDGE_EH)
458 struct df_rd_problem_data *problem_data
459 = (struct df_rd_problem_data *) df_rd->problem_data;
460 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
461 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
462 bitmap_iterator bi;
463 unsigned int regno;
464 bitmap_head tmp;
466 bitmap_initialize (&tmp, &df_bitmap_obstack);
467 bitmap_and_compl (&tmp, op2, dense_invalidated);
469 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
471 bitmap_clear_range (&tmp,
472 DF_DEFS_BEGIN (regno),
473 DF_DEFS_COUNT (regno));
475 changed |= bitmap_ior_into (op1, &tmp);
476 bitmap_clear (&tmp);
477 return changed;
479 else
480 return bitmap_ior_into (op1, op2);
484 /* Transfer function. */
486 static bool
487 df_rd_transfer_function (int bb_index)
489 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
490 unsigned int regno;
491 bitmap_iterator bi;
492 bitmap in = &bb_info->in;
493 bitmap out = &bb_info->out;
494 bitmap gen = &bb_info->gen;
495 bitmap kill = &bb_info->kill;
496 bitmap sparse_kill = &bb_info->sparse_kill;
497 bool changed = false;
499 if (bitmap_empty_p (sparse_kill))
500 changed = bitmap_ior_and_compl (out, gen, in, kill);
501 else
503 struct df_rd_problem_data *problem_data;
504 bitmap_head tmp;
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 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
509 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
511 bitmap_and_compl (&tmp, in, kill);
512 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
514 bitmap_clear_range (&tmp,
515 DF_DEFS_BEGIN (regno),
516 DF_DEFS_COUNT (regno));
518 bitmap_ior_into (&tmp, gen);
519 changed = !bitmap_equal_p (&tmp, out);
520 if (changed)
521 bitmap_move (out, &tmp);
522 else
523 bitmap_clear (&tmp);
526 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
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 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
533 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
534 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
535 unsigned int regno;
536 bitmap_iterator bi;
538 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
539 bitmap_set_range (live_defs,
540 DF_DEFS_BEGIN (regno),
541 DF_DEFS_COUNT (regno));
542 changed |= bitmap_and_into (&bb_info->out, live_defs);
543 BITMAP_FREE (live_defs);
546 return changed;
549 /* Free all storage associated with the problem. */
551 static void
552 df_rd_free (void)
554 struct df_rd_problem_data *problem_data
555 = (struct df_rd_problem_data *) df_rd->problem_data;
557 if (problem_data)
559 bitmap_obstack_release (&problem_data->rd_bitmaps);
561 df_rd->block_info_size = 0;
562 free (df_rd->block_info);
563 df_rd->block_info = NULL;
564 free (df_rd->problem_data);
566 free (df_rd);
570 /* Debugging info. */
572 static void
573 df_rd_start_dump (FILE *file)
575 struct df_rd_problem_data *problem_data
576 = (struct df_rd_problem_data *) df_rd->problem_data;
577 unsigned int m = DF_REG_SIZE (df);
578 unsigned int regno;
580 if (!df_rd->block_info)
581 return;
583 fprintf (file, ";; Reaching defs:\n");
585 fprintf (file, ";; sparse invalidated \t");
586 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
587 fprintf (file, ";; dense invalidated \t");
588 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
590 fprintf (file, ";; reg->defs[] map:\t");
591 for (regno = 0; regno < m; regno++)
592 if (DF_DEFS_COUNT (regno))
593 fprintf (file, "%d[%d,%d] ", regno,
594 DF_DEFS_BEGIN (regno),
595 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
596 fprintf (file, "\n");
600 static void
601 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
603 bitmap_head tmp;
604 unsigned int regno;
605 unsigned int m = DF_REG_SIZE (df);
606 bool first_reg = true;
608 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
610 bitmap_initialize (&tmp, &df_bitmap_obstack);
611 for (regno = 0; regno < m; regno++)
613 if (HARD_REGISTER_NUM_P (regno)
614 && (df->changeable_flags & DF_NO_HARD_REGS))
615 continue;
616 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
617 bitmap_and_into (&tmp, defs_set);
618 if (! bitmap_empty_p (&tmp))
620 bitmap_iterator bi;
621 unsigned int ix;
622 bool first_def = true;
624 if (! first_reg)
625 fprintf (file, ",");
626 first_reg = false;
628 fprintf (file, "%u[", regno);
629 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
631 fprintf (file, "%s%u", first_def ? "" : ",", ix);
632 first_def = false;
634 fprintf (file, "]");
636 bitmap_clear (&tmp);
639 fprintf (file, "\n");
640 bitmap_clear (&tmp);
643 /* Debugging info at top of bb. */
645 static void
646 df_rd_top_dump (basic_block bb, FILE *file)
648 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
649 if (!bb_info)
650 return;
652 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
653 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
654 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
658 /* Debugging info at bottom of bb. */
660 static void
661 df_rd_bottom_dump (basic_block bb, FILE *file)
663 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
664 if (!bb_info)
665 return;
667 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
670 /* All of the information associated with every instance of the problem. */
672 static const struct df_problem problem_RD =
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 (struct 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. */
703 /* Create a new RD instance and add it to the existing instance
704 of DF. */
706 void
707 df_rd_add_problem (void)
709 df_add_problem (&problem_RD);
714 /*----------------------------------------------------------------------------
715 LIVE REGISTERS
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 ----------------------------------------------------------------------------*/
723 /* Private data used to verify the solution for this problem. */
724 struct df_lr_problem_data
726 bitmap_head *in;
727 bitmap_head *out;
728 /* An obstack for the bitmaps we need for this problem. */
729 bitmap_obstack lr_bitmaps;
732 /* Free basic block info. */
734 static void
735 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
736 void *vbb_info)
738 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
739 if (bb_info)
741 bitmap_clear (&bb_info->use);
742 bitmap_clear (&bb_info->def);
743 bitmap_clear (&bb_info->in);
744 bitmap_clear (&bb_info->out);
749 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
750 not touched unless the block is new. */
752 static void
753 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
755 unsigned int bb_index;
756 bitmap_iterator bi;
757 struct df_lr_problem_data *problem_data;
759 df_grow_bb_info (df_lr);
760 if (df_lr->problem_data)
761 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
762 else
764 problem_data = XNEW (struct df_lr_problem_data);
765 df_lr->problem_data = problem_data;
767 problem_data->out = NULL;
768 problem_data->in = NULL;
769 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
772 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
774 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
776 /* When bitmaps are already initialized, just clear them. */
777 if (bb_info->use.obstack)
779 bitmap_clear (&bb_info->def);
780 bitmap_clear (&bb_info->use);
782 else
784 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
785 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
786 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
787 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
791 df_lr->optional_p = false;
795 /* Reset the global solution for recalculation. */
797 static void
798 df_lr_reset (bitmap all_blocks)
800 unsigned int bb_index;
801 bitmap_iterator bi;
803 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
805 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
806 gcc_assert (bb_info);
807 bitmap_clear (&bb_info->in);
808 bitmap_clear (&bb_info->out);
813 /* Compute local live register info for basic block BB. */
815 static void
816 df_lr_bb_local_compute (unsigned int bb_index)
818 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
819 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
820 rtx_insn *insn;
821 df_ref def, use;
823 /* Process the registers set in an exception handler. */
824 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
825 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
827 unsigned int dregno = DF_REF_REGNO (def);
828 bitmap_set_bit (&bb_info->def, dregno);
829 bitmap_clear_bit (&bb_info->use, dregno);
832 /* Process the hardware registers that are always live. */
833 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
834 /* Add use to set of uses in this BB. */
835 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
836 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
838 FOR_BB_INSNS_REVERSE (bb, insn)
840 if (!NONDEBUG_INSN_P (insn))
841 continue;
843 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844 FOR_EACH_INSN_INFO_DEF (def, insn_info)
845 /* If the def is to only part of the reg, it does
846 not kill the other defs that reach here. */
847 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
849 unsigned int dregno = DF_REF_REGNO (def);
850 bitmap_set_bit (&bb_info->def, dregno);
851 bitmap_clear_bit (&bb_info->use, dregno);
854 FOR_EACH_INSN_INFO_USE (use, insn_info)
855 /* Add use to set of uses in this BB. */
856 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
859 /* Process the registers set in an exception handler or the hard
860 frame pointer if this block is the target of a non local
861 goto. */
862 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
863 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
865 unsigned int dregno = DF_REF_REGNO (def);
866 bitmap_set_bit (&bb_info->def, dregno);
867 bitmap_clear_bit (&bb_info->use, dregno);
870 #ifdef EH_USES
871 /* Process the uses that are live into an exception handler. */
872 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
873 /* Add use to set of uses in this BB. */
874 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
875 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
876 #endif
878 /* If the df_live problem is not defined, such as at -O0 and -O1, we
879 still need to keep the luids up to date. This is normally done
880 in the df_live problem since this problem has a forwards
881 scan. */
882 if (!df_live)
883 df_recompute_luids (bb);
887 /* Compute local live register info for each basic block within BLOCKS. */
889 static void
890 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
892 unsigned int bb_index, i;
893 bitmap_iterator bi;
895 bitmap_clear (&df->hardware_regs_used);
897 /* The all-important stack pointer must always be live. */
898 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
900 /* Global regs are always live, too. */
901 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
902 if (global_regs[i])
903 bitmap_set_bit (&df->hardware_regs_used, i);
905 /* Before reload, there are a few registers that must be forced
906 live everywhere -- which might not already be the case for
907 blocks within infinite loops. */
908 if (!reload_completed)
910 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
911 /* Any reference to any pseudo before reload is a potential
912 reference of the frame pointer. */
913 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
915 /* Pseudos with argument area equivalences may require
916 reloading via the argument pointer. */
917 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
918 && fixed_regs[ARG_POINTER_REGNUM])
919 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
921 /* Any constant, or pseudo with constant equivalences, may
922 require reloading from memory using the pic register. */
923 if (pic_offset_table_regnum != INVALID_REGNUM
924 && fixed_regs[pic_offset_table_regnum])
925 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
928 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
930 if (bb_index == EXIT_BLOCK)
932 /* The exit block is special for this problem and its bits are
933 computed from thin air. */
934 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
935 bitmap_copy (&bb_info->use, df->exit_block_uses);
937 else
938 df_lr_bb_local_compute (bb_index);
941 bitmap_clear (df_lr->out_of_date_transfer_functions);
945 /* Initialize the solution vectors. */
947 static void
948 df_lr_init (bitmap all_blocks)
950 unsigned int bb_index;
951 bitmap_iterator bi;
953 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
955 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
956 bitmap_copy (&bb_info->in, &bb_info->use);
957 bitmap_clear (&bb_info->out);
962 /* Confluence function that processes infinite loops. This might be a
963 noreturn function that throws. And even if it isn't, getting the
964 unwind info right helps debugging. */
965 static void
966 df_lr_confluence_0 (basic_block bb)
968 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
969 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
970 bitmap_copy (op1, &df->hardware_regs_used);
974 /* Confluence function that ignores fake edges. */
976 static bool
977 df_lr_confluence_n (edge e)
979 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
980 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
981 bool changed = false;
983 /* Call-clobbered registers die across exception and call edges. */
984 /* ??? Abnormal call edges ignored for the moment, as this gets
985 confused by sibling call edges, which crashes reg-stack. */
986 if (e->flags & EDGE_EH)
987 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
988 else
989 changed = bitmap_ior_into (op1, op2);
991 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
992 return changed;
996 /* Transfer function. */
998 static bool
999 df_lr_transfer_function (int bb_index)
1001 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1002 bitmap in = &bb_info->in;
1003 bitmap out = &bb_info->out;
1004 bitmap use = &bb_info->use;
1005 bitmap def = &bb_info->def;
1007 return bitmap_ior_and_compl (in, use, out, def);
1011 /* Run the fast dce as a side effect of building LR. */
1013 static void
1014 df_lr_finalize (bitmap all_blocks)
1016 df_lr->solutions_dirty = false;
1017 if (df->changeable_flags & DF_LR_RUN_DCE)
1019 run_fast_df_dce ();
1021 /* If dce deletes some instructions, we need to recompute the lr
1022 solution before proceeding further. The problem is that fast
1023 dce is a pessimestic dataflow algorithm. In the case where
1024 it deletes a statement S inside of a loop, the uses inside of
1025 S may not be deleted from the dataflow solution because they
1026 were carried around the loop. While it is conservatively
1027 correct to leave these extra bits, the standards of df
1028 require that we maintain the best possible (least fixed
1029 point) solution. The only way to do that is to redo the
1030 iteration from the beginning. See PR35805 for an
1031 example. */
1032 if (df_lr->solutions_dirty)
1034 df_clear_flags (DF_LR_RUN_DCE);
1035 df_lr_alloc (all_blocks);
1036 df_lr_local_compute (all_blocks);
1037 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1038 df_lr_finalize (all_blocks);
1039 df_set_flags (DF_LR_RUN_DCE);
1045 /* Free all storage associated with the problem. */
1047 static void
1048 df_lr_free (void)
1050 struct df_lr_problem_data *problem_data
1051 = (struct df_lr_problem_data *) df_lr->problem_data;
1052 if (df_lr->block_info)
1055 df_lr->block_info_size = 0;
1056 free (df_lr->block_info);
1057 df_lr->block_info = NULL;
1058 bitmap_obstack_release (&problem_data->lr_bitmaps);
1059 free (df_lr->problem_data);
1060 df_lr->problem_data = NULL;
1063 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1064 free (df_lr);
1068 /* Debugging info at top of bb. */
1070 static void
1071 df_lr_top_dump (basic_block bb, FILE *file)
1073 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1074 struct df_lr_problem_data *problem_data;
1075 if (!bb_info)
1076 return;
1078 fprintf (file, ";; lr in \t");
1079 df_print_regset (file, &bb_info->in);
1080 if (df_lr->problem_data)
1082 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1083 if (problem_data->in)
1085 fprintf (file, ";; old in \t");
1086 df_print_regset (file, &problem_data->in[bb->index]);
1089 fprintf (file, ";; lr use \t");
1090 df_print_regset (file, &bb_info->use);
1091 fprintf (file, ";; lr def \t");
1092 df_print_regset (file, &bb_info->def);
1096 /* Debugging info at bottom of bb. */
1098 static void
1099 df_lr_bottom_dump (basic_block bb, FILE *file)
1101 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1102 struct df_lr_problem_data *problem_data;
1103 if (!bb_info)
1104 return;
1106 fprintf (file, ";; lr out \t");
1107 df_print_regset (file, &bb_info->out);
1108 if (df_lr->problem_data)
1110 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1111 if (problem_data->out)
1113 fprintf (file, ";; old out \t");
1114 df_print_regset (file, &problem_data->out[bb->index]);
1120 /* Build the datastructure to verify that the solution to the dataflow
1121 equations is not dirty. */
1123 static void
1124 df_lr_verify_solution_start (void)
1126 basic_block bb;
1127 struct df_lr_problem_data *problem_data;
1128 if (df_lr->solutions_dirty)
1129 return;
1131 /* Set it true so that the solution is recomputed. */
1132 df_lr->solutions_dirty = true;
1134 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1135 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1136 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1138 FOR_ALL_BB_FN (bb, cfun)
1140 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1141 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1142 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1143 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1148 /* Compare the saved datastructure and the new solution to the dataflow
1149 equations. */
1151 static void
1152 df_lr_verify_solution_end (void)
1154 struct df_lr_problem_data *problem_data;
1155 basic_block bb;
1157 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1159 if (!problem_data->out)
1160 return;
1162 if (df_lr->solutions_dirty)
1163 /* Do not check if the solution is still dirty. See the comment
1164 in df_lr_finalize for details. */
1165 df_lr->solutions_dirty = false;
1166 else
1167 FOR_ALL_BB_FN (bb, cfun)
1169 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1170 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1172 /*df_dump (stderr);*/
1173 gcc_unreachable ();
1177 /* Cannot delete them immediately because you may want to dump them
1178 if the comparison fails. */
1179 FOR_ALL_BB_FN (bb, cfun)
1181 bitmap_clear (&problem_data->in[bb->index]);
1182 bitmap_clear (&problem_data->out[bb->index]);
1185 free (problem_data->in);
1186 free (problem_data->out);
1187 problem_data->in = NULL;
1188 problem_data->out = NULL;
1192 /* All of the information associated with every instance of the problem. */
1194 static const struct df_problem problem_LR =
1196 DF_LR, /* Problem id. */
1197 DF_BACKWARD, /* Direction. */
1198 df_lr_alloc, /* Allocate the problem specific data. */
1199 df_lr_reset, /* Reset global information. */
1200 df_lr_free_bb_info, /* Free basic block info. */
1201 df_lr_local_compute, /* Local compute function. */
1202 df_lr_init, /* Init the solution specific data. */
1203 df_worklist_dataflow, /* Worklist solver. */
1204 df_lr_confluence_0, /* Confluence operator 0. */
1205 df_lr_confluence_n, /* Confluence operator n. */
1206 df_lr_transfer_function, /* Transfer function. */
1207 df_lr_finalize, /* Finalize function. */
1208 df_lr_free, /* Free all of the problem information. */
1209 NULL, /* Remove this problem from the stack of dataflow problems. */
1210 NULL, /* Debugging. */
1211 df_lr_top_dump, /* Debugging start block. */
1212 df_lr_bottom_dump, /* Debugging end block. */
1213 NULL, /* Debugging start insn. */
1214 NULL, /* Debugging end insn. */
1215 df_lr_verify_solution_start,/* Incremental solution verify start. */
1216 df_lr_verify_solution_end, /* Incremental solution verify end. */
1217 NULL, /* Dependent problem. */
1218 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1219 TV_DF_LR, /* Timing variable. */
1220 false /* Reset blocks on dropping out of blocks_to_analyze. */
1224 /* Create a new DATAFLOW instance and add it to an existing instance
1225 of DF. The returned structure is what is used to get at the
1226 solution. */
1228 void
1229 df_lr_add_problem (void)
1231 df_add_problem (&problem_LR);
1232 /* These will be initialized when df_scan_blocks processes each
1233 block. */
1234 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1238 /* Verify that all of the lr related info is consistent and
1239 correct. */
1241 void
1242 df_lr_verify_transfer_functions (void)
1244 basic_block bb;
1245 bitmap_head saved_def;
1246 bitmap_head saved_use;
1247 bitmap_head all_blocks;
1249 if (!df)
1250 return;
1252 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1253 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1254 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1256 FOR_ALL_BB_FN (bb, cfun)
1258 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1259 bitmap_set_bit (&all_blocks, bb->index);
1261 if (bb_info)
1263 /* Make a copy of the transfer functions and then compute
1264 new ones to see if the transfer functions have
1265 changed. */
1266 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1267 bb->index))
1269 bitmap_copy (&saved_def, &bb_info->def);
1270 bitmap_copy (&saved_use, &bb_info->use);
1271 bitmap_clear (&bb_info->def);
1272 bitmap_clear (&bb_info->use);
1274 df_lr_bb_local_compute (bb->index);
1275 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1276 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1279 else
1281 /* If we do not have basic block info, the block must be in
1282 the list of dirty blocks or else some one has added a
1283 block behind our backs. */
1284 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1285 bb->index));
1287 /* Make sure no one created a block without following
1288 procedures. */
1289 gcc_assert (df_scan_get_bb_info (bb->index));
1292 /* Make sure there are no dirty bits in blocks that have been deleted. */
1293 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1294 &all_blocks));
1296 bitmap_clear (&saved_def);
1297 bitmap_clear (&saved_use);
1298 bitmap_clear (&all_blocks);
1303 /*----------------------------------------------------------------------------
1304 LIVE AND MAY-INITIALIZED REGISTERS.
1306 This problem first computes the IN and OUT bitvectors for the
1307 may-initialized registers problems, which is a forward problem.
1308 It gives the set of registers for which we MAY have an available
1309 definition, i.e. for which there is an available definition on
1310 at least one path from the entry block to the entry/exit of a
1311 basic block. Sets generate a definition, while clobbers kill
1312 a definition.
1314 In and out bitvectors are built for each basic block and are indexed by
1315 regnum (see df.h for details). In and out bitvectors in struct
1316 df_live_bb_info actually refers to the may-initialized problem;
1318 Then, the in and out sets for the LIVE problem itself are computed.
1319 These are the logical AND of the IN and OUT sets from the LR problem
1320 and the may-initialized problem.
1321 ----------------------------------------------------------------------------*/
1323 /* Private data used to verify the solution for this problem. */
1324 struct df_live_problem_data
1326 bitmap_head *in;
1327 bitmap_head *out;
1328 /* An obstack for the bitmaps we need for this problem. */
1329 bitmap_obstack live_bitmaps;
1332 /* Scratch var used by transfer functions. This is used to implement
1333 an optimization to reduce the amount of space used to compute the
1334 combined lr and live analysis. */
1335 static bitmap_head df_live_scratch;
1338 /* Free basic block info. */
1340 static void
1341 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1342 void *vbb_info)
1344 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1345 if (bb_info)
1347 bitmap_clear (&bb_info->gen);
1348 bitmap_clear (&bb_info->kill);
1349 bitmap_clear (&bb_info->in);
1350 bitmap_clear (&bb_info->out);
1355 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1356 not touched unless the block is new. */
1358 static void
1359 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1361 unsigned int bb_index;
1362 bitmap_iterator bi;
1363 struct df_live_problem_data *problem_data;
1365 if (df_live->problem_data)
1366 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1367 else
1369 problem_data = XNEW (struct df_live_problem_data);
1370 df_live->problem_data = problem_data;
1372 problem_data->out = NULL;
1373 problem_data->in = NULL;
1374 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1375 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1378 df_grow_bb_info (df_live);
1380 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1382 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1384 /* When bitmaps are already initialized, just clear them. */
1385 if (bb_info->kill.obstack)
1387 bitmap_clear (&bb_info->kill);
1388 bitmap_clear (&bb_info->gen);
1390 else
1392 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1393 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1394 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1395 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1398 df_live->optional_p = (optimize <= 1);
1402 /* Reset the global solution for recalculation. */
1404 static void
1405 df_live_reset (bitmap all_blocks)
1407 unsigned int bb_index;
1408 bitmap_iterator bi;
1410 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1412 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1413 gcc_assert (bb_info);
1414 bitmap_clear (&bb_info->in);
1415 bitmap_clear (&bb_info->out);
1420 /* Compute local uninitialized register info for basic block BB. */
1422 static void
1423 df_live_bb_local_compute (unsigned int bb_index)
1425 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1426 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1427 rtx_insn *insn;
1428 df_ref def;
1429 int luid = 0;
1431 FOR_BB_INSNS (bb, insn)
1433 unsigned int uid = INSN_UID (insn);
1434 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1436 /* Inserting labels does not always trigger the incremental
1437 rescanning. */
1438 if (!insn_info)
1440 gcc_assert (!INSN_P (insn));
1441 insn_info = df_insn_create_insn_record (insn);
1444 DF_INSN_INFO_LUID (insn_info) = luid;
1445 if (!INSN_P (insn))
1446 continue;
1448 luid++;
1449 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1451 unsigned int regno = DF_REF_REGNO (def);
1453 if (DF_REF_FLAGS_IS_SET (def,
1454 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1455 /* All partial or conditional def
1456 seen are included in the gen set. */
1457 bitmap_set_bit (&bb_info->gen, regno);
1458 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1459 /* Only must clobbers for the entire reg destroy the
1460 value. */
1461 bitmap_set_bit (&bb_info->kill, regno);
1462 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1463 bitmap_set_bit (&bb_info->gen, regno);
1467 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1468 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1472 /* Compute local uninitialized register info. */
1474 static void
1475 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1477 unsigned int bb_index;
1478 bitmap_iterator bi;
1480 df_grow_insn_info ();
1482 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1483 0, bb_index, bi)
1485 df_live_bb_local_compute (bb_index);
1488 bitmap_clear (df_live->out_of_date_transfer_functions);
1492 /* Initialize the solution vectors. */
1494 static void
1495 df_live_init (bitmap all_blocks)
1497 unsigned int bb_index;
1498 bitmap_iterator bi;
1500 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1502 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1503 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1505 /* No register may reach a location where it is not used. Thus
1506 we trim the rr result to the places where it is used. */
1507 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1508 bitmap_clear (&bb_info->in);
1512 /* Forward confluence function that ignores fake edges. */
1514 static bool
1515 df_live_confluence_n (edge e)
1517 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1518 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1520 if (e->flags & EDGE_FAKE)
1521 return false;
1523 return bitmap_ior_into (op1, op2);
1527 /* Transfer function for the forwards may-initialized problem. */
1529 static bool
1530 df_live_transfer_function (int bb_index)
1532 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1533 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1534 bitmap in = &bb_info->in;
1535 bitmap out = &bb_info->out;
1536 bitmap gen = &bb_info->gen;
1537 bitmap kill = &bb_info->kill;
1539 /* We need to use a scratch set here so that the value returned from this
1540 function invocation properly reflects whether the sets changed in a
1541 significant way; i.e. not just because the lr set was anded in. */
1542 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1543 /* No register may reach a location where it is not used. Thus
1544 we trim the rr result to the places where it is used. */
1545 bitmap_and_into (in, &bb_lr_info->in);
1547 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1551 /* And the LR info with the may-initialized registers to produce the LIVE info. */
1553 static void
1554 df_live_finalize (bitmap all_blocks)
1557 if (df_live->solutions_dirty)
1559 bitmap_iterator bi;
1560 unsigned int bb_index;
1562 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1564 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1565 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1567 /* No register may reach a location where it is not used. Thus
1568 we trim the rr result to the places where it is used. */
1569 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1570 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1573 df_live->solutions_dirty = false;
1578 /* Free all storage associated with the problem. */
1580 static void
1581 df_live_free (void)
1583 struct df_live_problem_data *problem_data
1584 = (struct df_live_problem_data *) df_live->problem_data;
1585 if (df_live->block_info)
1587 df_live->block_info_size = 0;
1588 free (df_live->block_info);
1589 df_live->block_info = NULL;
1590 bitmap_clear (&df_live_scratch);
1591 bitmap_obstack_release (&problem_data->live_bitmaps);
1592 free (problem_data);
1593 df_live->problem_data = NULL;
1595 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1596 free (df_live);
1600 /* Debugging info at top of bb. */
1602 static void
1603 df_live_top_dump (basic_block bb, FILE *file)
1605 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1606 struct df_live_problem_data *problem_data;
1608 if (!bb_info)
1609 return;
1611 fprintf (file, ";; live in \t");
1612 df_print_regset (file, &bb_info->in);
1613 if (df_live->problem_data)
1615 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1616 if (problem_data->in)
1618 fprintf (file, ";; old in \t");
1619 df_print_regset (file, &problem_data->in[bb->index]);
1622 fprintf (file, ";; live gen \t");
1623 df_print_regset (file, &bb_info->gen);
1624 fprintf (file, ";; live kill\t");
1625 df_print_regset (file, &bb_info->kill);
1629 /* Debugging info at bottom of bb. */
1631 static void
1632 df_live_bottom_dump (basic_block bb, FILE *file)
1634 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1635 struct df_live_problem_data *problem_data;
1637 if (!bb_info)
1638 return;
1640 fprintf (file, ";; live out \t");
1641 df_print_regset (file, &bb_info->out);
1642 if (df_live->problem_data)
1644 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1645 if (problem_data->out)
1647 fprintf (file, ";; old out \t");
1648 df_print_regset (file, &problem_data->out[bb->index]);
1654 /* Build the datastructure to verify that the solution to the dataflow
1655 equations is not dirty. */
1657 static void
1658 df_live_verify_solution_start (void)
1660 basic_block bb;
1661 struct df_live_problem_data *problem_data;
1662 if (df_live->solutions_dirty)
1663 return;
1665 /* Set it true so that the solution is recomputed. */
1666 df_live->solutions_dirty = true;
1668 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1669 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1670 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1672 FOR_ALL_BB_FN (bb, cfun)
1674 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1675 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1676 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1677 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1682 /* Compare the saved datastructure and the new solution to the dataflow
1683 equations. */
1685 static void
1686 df_live_verify_solution_end (void)
1688 struct df_live_problem_data *problem_data;
1689 basic_block bb;
1691 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1692 if (!problem_data->out)
1693 return;
1695 FOR_ALL_BB_FN (bb, cfun)
1697 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1698 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1700 /*df_dump (stderr);*/
1701 gcc_unreachable ();
1705 /* Cannot delete them immediately because you may want to dump them
1706 if the comparison fails. */
1707 FOR_ALL_BB_FN (bb, cfun)
1709 bitmap_clear (&problem_data->in[bb->index]);
1710 bitmap_clear (&problem_data->out[bb->index]);
1713 free (problem_data->in);
1714 free (problem_data->out);
1715 free (problem_data);
1716 df_live->problem_data = NULL;
1720 /* All of the information associated with every instance of the problem. */
1722 static const struct df_problem problem_LIVE =
1724 DF_LIVE, /* Problem id. */
1725 DF_FORWARD, /* Direction. */
1726 df_live_alloc, /* Allocate the problem specific data. */
1727 df_live_reset, /* Reset global information. */
1728 df_live_free_bb_info, /* Free basic block info. */
1729 df_live_local_compute, /* Local compute function. */
1730 df_live_init, /* Init the solution specific data. */
1731 df_worklist_dataflow, /* Worklist solver. */
1732 NULL, /* Confluence operator 0. */
1733 df_live_confluence_n, /* Confluence operator n. */
1734 df_live_transfer_function, /* Transfer function. */
1735 df_live_finalize, /* Finalize function. */
1736 df_live_free, /* Free all of the problem information. */
1737 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1738 NULL, /* Debugging. */
1739 df_live_top_dump, /* Debugging start block. */
1740 df_live_bottom_dump, /* Debugging end block. */
1741 NULL, /* Debugging start insn. */
1742 NULL, /* Debugging end insn. */
1743 df_live_verify_solution_start,/* Incremental solution verify start. */
1744 df_live_verify_solution_end, /* Incremental solution verify end. */
1745 &problem_LR, /* Dependent problem. */
1746 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1747 TV_DF_LIVE, /* Timing variable. */
1748 false /* Reset blocks on dropping out of blocks_to_analyze. */
1752 /* Create a new DATAFLOW instance and add it to an existing instance
1753 of DF. The returned structure is what is used to get at the
1754 solution. */
1756 void
1757 df_live_add_problem (void)
1759 df_add_problem (&problem_LIVE);
1760 /* These will be initialized when df_scan_blocks processes each
1761 block. */
1762 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1766 /* Set all of the blocks as dirty. This needs to be done if this
1767 problem is added after all of the insns have been scanned. */
1769 void
1770 df_live_set_all_dirty (void)
1772 basic_block bb;
1773 FOR_ALL_BB_FN (bb, cfun)
1774 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1775 bb->index);
1779 /* Verify that all of the lr related info is consistent and
1780 correct. */
1782 void
1783 df_live_verify_transfer_functions (void)
1785 basic_block bb;
1786 bitmap_head saved_gen;
1787 bitmap_head saved_kill;
1788 bitmap_head all_blocks;
1790 if (!df)
1791 return;
1793 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1794 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1795 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1797 df_grow_insn_info ();
1799 FOR_ALL_BB_FN (bb, cfun)
1801 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1802 bitmap_set_bit (&all_blocks, bb->index);
1804 if (bb_info)
1806 /* Make a copy of the transfer functions and then compute
1807 new ones to see if the transfer functions have
1808 changed. */
1809 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1810 bb->index))
1812 bitmap_copy (&saved_gen, &bb_info->gen);
1813 bitmap_copy (&saved_kill, &bb_info->kill);
1814 bitmap_clear (&bb_info->gen);
1815 bitmap_clear (&bb_info->kill);
1817 df_live_bb_local_compute (bb->index);
1818 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1819 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1822 else
1824 /* If we do not have basic block info, the block must be in
1825 the list of dirty blocks or else some one has added a
1826 block behind our backs. */
1827 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1828 bb->index));
1830 /* Make sure no one created a block without following
1831 procedures. */
1832 gcc_assert (df_scan_get_bb_info (bb->index));
1835 /* Make sure there are no dirty bits in blocks that have been deleted. */
1836 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1837 &all_blocks));
1838 bitmap_clear (&saved_gen);
1839 bitmap_clear (&saved_kill);
1840 bitmap_clear (&all_blocks);
1843 /*----------------------------------------------------------------------------
1844 MUST-INITIALIZED REGISTERS.
1845 ----------------------------------------------------------------------------*/
1847 /* Private data used to verify the solution for this problem. */
1848 struct df_mir_problem_data
1850 bitmap_head *in;
1851 bitmap_head *out;
1852 /* An obstack for the bitmaps we need for this problem. */
1853 bitmap_obstack mir_bitmaps;
1857 /* Free basic block info. */
1859 static void
1860 df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1861 void *vbb_info)
1863 struct df_mir_bb_info *bb_info = (struct df_mir_bb_info *) vbb_info;
1864 if (bb_info)
1866 bitmap_clear (&bb_info->gen);
1867 bitmap_clear (&bb_info->kill);
1868 bitmap_clear (&bb_info->in);
1869 bitmap_clear (&bb_info->out);
1874 /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
1875 not touched unless the block is new. */
1877 static void
1878 df_mir_alloc (bitmap all_blocks)
1880 unsigned int bb_index;
1881 bitmap_iterator bi;
1882 struct df_mir_problem_data *problem_data;
1884 if (df_mir->problem_data)
1885 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1886 else
1888 problem_data = XNEW (struct df_mir_problem_data);
1889 df_mir->problem_data = problem_data;
1891 problem_data->out = NULL;
1892 problem_data->in = NULL;
1893 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1896 df_grow_bb_info (df_mir);
1898 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1900 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1902 /* When bitmaps are already initialized, just clear them. */
1903 if (bb_info->kill.obstack)
1905 bitmap_clear (&bb_info->kill);
1906 bitmap_clear (&bb_info->gen);
1908 else
1910 bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1911 bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1912 bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1913 bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1914 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1915 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1919 df_mir->optional_p = 1;
1923 /* Reset the global solution for recalculation. */
1925 static void
1926 df_mir_reset (bitmap all_blocks)
1928 unsigned int bb_index;
1929 bitmap_iterator bi;
1931 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1933 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1935 gcc_assert (bb_info);
1937 bitmap_clear (&bb_info->in);
1938 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1939 bitmap_clear (&bb_info->out);
1940 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1945 /* Compute local uninitialized register info for basic block BB. */
1947 static void
1948 df_mir_bb_local_compute (unsigned int bb_index)
1950 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1951 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1952 rtx_insn *insn;
1953 int luid = 0;
1955 /* Ignoring artificial defs is intentional: these often pretend that some
1956 registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
1957 though they are not used for that. As a result, conservatively assume
1958 they may be uninitialized. */
1960 FOR_BB_INSNS (bb, insn)
1962 unsigned int uid = INSN_UID (insn);
1963 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1965 /* Inserting labels does not always trigger the incremental
1966 rescanning. */
1967 if (!insn_info)
1969 gcc_assert (!INSN_P (insn));
1970 insn_info = df_insn_create_insn_record (insn);
1973 DF_INSN_INFO_LUID (insn_info) = luid;
1974 if (!INSN_P (insn))
1975 continue;
1977 luid++;
1978 df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
1983 /* Compute local uninitialized register info. */
1985 static void
1986 df_mir_local_compute (bitmap all_blocks)
1988 unsigned int bb_index;
1989 bitmap_iterator bi;
1991 df_grow_insn_info ();
1993 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1995 df_mir_bb_local_compute (bb_index);
2000 /* Initialize the solution vectors. */
2002 static void
2003 df_mir_init (bitmap all_blocks)
2005 df_mir_reset (all_blocks);
2009 /* Initialize IN sets for blocks with no predecessors: when landing on such
2010 blocks, assume all registers are uninitialized. */
2012 static void
2013 df_mir_confluence_0 (basic_block bb)
2015 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2017 bitmap_clear (&bb_info->in);
2021 /* Forward confluence function that ignores fake edges. */
2023 static bool
2024 df_mir_confluence_n (edge e)
2026 bitmap op1 = &df_mir_get_bb_info (e->dest->index)->in;
2027 bitmap op2 = &df_mir_get_bb_info (e->src->index)->out;
2029 if (e->flags & EDGE_FAKE)
2030 return false;
2032 /* A register is must-initialized at the entry of a basic block iff it is
2033 must-initialized at the exit of all the predecessors. */
2034 return bitmap_and_into (op1, op2);
2038 /* Transfer function for the forwards must-initialized problem. */
2040 static bool
2041 df_mir_transfer_function (int bb_index)
2043 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2044 bitmap in = &bb_info->in;
2045 bitmap out = &bb_info->out;
2046 bitmap gen = &bb_info->gen;
2047 bitmap kill = &bb_info->kill;
2049 return bitmap_ior_and_compl (out, gen, in, kill);
2053 /* Free all storage associated with the problem. */
2055 static void
2056 df_mir_free (void)
2058 struct df_mir_problem_data *problem_data
2059 = (struct df_mir_problem_data *) df_mir->problem_data;
2060 if (df_mir->block_info)
2062 df_mir->block_info_size = 0;
2063 free (df_mir->block_info);
2064 df_mir->block_info = NULL;
2065 bitmap_obstack_release (&problem_data->mir_bitmaps);
2066 free (problem_data);
2067 df_mir->problem_data = NULL;
2069 free (df_mir);
2073 /* Debugging info at top of bb. */
2075 static void
2076 df_mir_top_dump (basic_block bb, FILE *file)
2078 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2080 if (!bb_info)
2081 return;
2083 fprintf (file, ";; mir in \t");
2084 df_print_regset (file, &bb_info->in);
2085 fprintf (file, ";; mir kill\t");
2086 df_print_regset (file, &bb_info->kill);
2087 fprintf (file, ";; mir gen \t");
2088 df_print_regset (file, &bb_info->gen);
2091 /* Debugging info at bottom of bb. */
2093 static void
2094 df_mir_bottom_dump (basic_block bb, FILE *file)
2096 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2098 if (!bb_info)
2099 return;
2101 fprintf (file, ";; mir out \t");
2102 df_print_regset (file, &bb_info->out);
2106 /* Build the datastructure to verify that the solution to the dataflow
2107 equations is not dirty. */
2109 static void
2110 df_mir_verify_solution_start (void)
2112 basic_block bb;
2113 struct df_mir_problem_data *problem_data;
2114 if (df_mir->solutions_dirty)
2115 return;
2117 /* Set it true so that the solution is recomputed. */
2118 df_mir->solutions_dirty = true;
2120 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2121 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2122 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2123 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2125 FOR_ALL_BB_FN (bb, cfun)
2127 bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
2128 bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
2129 bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2130 bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2135 /* Compare the saved datastructure and the new solution to the dataflow
2136 equations. */
2138 static void
2139 df_mir_verify_solution_end (void)
2141 struct df_mir_problem_data *problem_data;
2142 basic_block bb;
2144 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2145 if (!problem_data->out)
2146 return;
2148 FOR_ALL_BB_FN (bb, cfun)
2150 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2151 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2152 gcc_unreachable ();
2155 /* Cannot delete them immediately because you may want to dump them
2156 if the comparison fails. */
2157 FOR_ALL_BB_FN (bb, cfun)
2159 bitmap_clear (&problem_data->in[bb->index]);
2160 bitmap_clear (&problem_data->out[bb->index]);
2163 free (problem_data->in);
2164 free (problem_data->out);
2165 bitmap_obstack_release (&problem_data->mir_bitmaps);
2166 free (problem_data);
2167 df_mir->problem_data = NULL;
2171 /* All of the information associated with every instance of the problem. */
2173 static const struct df_problem problem_MIR =
2175 DF_MIR, /* Problem id. */
2176 DF_FORWARD, /* Direction. */
2177 df_mir_alloc, /* Allocate the problem specific data. */
2178 df_mir_reset, /* Reset global information. */
2179 df_mir_free_bb_info, /* Free basic block info. */
2180 df_mir_local_compute, /* Local compute function. */
2181 df_mir_init, /* Init the solution specific data. */
2182 df_worklist_dataflow, /* Worklist solver. */
2183 df_mir_confluence_0, /* Confluence operator 0. */
2184 df_mir_confluence_n, /* Confluence operator n. */
2185 df_mir_transfer_function, /* Transfer function. */
2186 NULL, /* Finalize function. */
2187 df_mir_free, /* Free all of the problem information. */
2188 df_mir_free, /* Remove this problem from the stack of dataflow problems. */
2189 NULL, /* Debugging. */
2190 df_mir_top_dump, /* Debugging start block. */
2191 df_mir_bottom_dump, /* Debugging end block. */
2192 NULL, /* Debugging start insn. */
2193 NULL, /* Debugging end insn. */
2194 df_mir_verify_solution_start, /* Incremental solution verify start. */
2195 df_mir_verify_solution_end, /* Incremental solution verify end. */
2196 NULL, /* Dependent problem. */
2197 sizeof (struct df_mir_bb_info),/* Size of entry of block_info array. */
2198 TV_DF_MIR, /* Timing variable. */
2199 false /* Reset blocks on dropping out of blocks_to_analyze. */
2203 /* Create a new DATAFLOW instance and add it to an existing instance
2204 of DF. */
2206 void
2207 df_mir_add_problem (void)
2209 df_add_problem (&problem_MIR);
2210 /* These will be initialized when df_scan_blocks processes each
2211 block. */
2212 df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2216 /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2218 void
2219 df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2220 bitmap kill, bitmap gen)
2222 df_ref def;
2224 FOR_EACH_INSN_DEF (def, insn)
2226 unsigned int regno = DF_REF_REGNO (def);
2228 /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
2229 previous gen is irrelevant (and reciprocally). Also, claim that a
2230 register is GEN only if it is in all cases. */
2231 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2233 bitmap_set_bit (kill, regno);
2234 bitmap_clear_bit (gen, regno);
2236 /* In the worst case, partial and conditional defs can leave bits
2237 uninitialized, so assume they do not change anything. */
2238 else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2240 bitmap_set_bit (gen, regno);
2241 bitmap_clear_bit (kill, regno);
2246 /*----------------------------------------------------------------------------
2247 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2249 Link either the defs to the uses and / or the uses to the defs.
2251 These problems are set up like the other dataflow problems so that
2252 they nicely fit into the framework. They are much simpler and only
2253 involve a single traversal of instructions and an examination of
2254 the reaching defs information (the dependent problem).
2255 ----------------------------------------------------------------------------*/
2257 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2259 /* Create a du or ud chain from SRC to DST and link it into SRC. */
2261 struct df_link *
2262 df_chain_create (df_ref src, df_ref dst)
2264 struct df_link *head = DF_REF_CHAIN (src);
2265 struct df_link *link = df_chain->block_pool->allocate ();
2267 DF_REF_CHAIN (src) = link;
2268 link->next = head;
2269 link->ref = dst;
2270 return link;
2274 /* Delete any du or ud chains that start at REF and point to
2275 TARGET. */
2276 static void
2277 df_chain_unlink_1 (df_ref ref, df_ref target)
2279 struct df_link *chain = DF_REF_CHAIN (ref);
2280 struct df_link *prev = NULL;
2282 while (chain)
2284 if (chain->ref == target)
2286 if (prev)
2287 prev->next = chain->next;
2288 else
2289 DF_REF_CHAIN (ref) = chain->next;
2290 df_chain->block_pool->remove (chain);
2291 return;
2293 prev = chain;
2294 chain = chain->next;
2299 /* Delete a du or ud chain that leave or point to REF. */
2301 void
2302 df_chain_unlink (df_ref ref)
2304 struct df_link *chain = DF_REF_CHAIN (ref);
2305 while (chain)
2307 struct df_link *next = chain->next;
2308 /* Delete the other side if it exists. */
2309 df_chain_unlink_1 (chain->ref, ref);
2310 df_chain->block_pool->remove (chain);
2311 chain = next;
2313 DF_REF_CHAIN (ref) = NULL;
2317 /* Copy the du or ud chain starting at FROM_REF and attach it to
2318 TO_REF. */
2320 void
2321 df_chain_copy (df_ref to_ref,
2322 struct df_link *from_ref)
2324 while (from_ref)
2326 df_chain_create (to_ref, from_ref->ref);
2327 from_ref = from_ref->next;
2332 /* Remove this problem from the stack of dataflow problems. */
2334 static void
2335 df_chain_remove_problem (void)
2337 bitmap_iterator bi;
2338 unsigned int bb_index;
2340 /* Wholesale destruction of the old chains. */
2341 if (df_chain->block_pool)
2342 delete df_chain->block_pool;
2344 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2346 rtx_insn *insn;
2347 df_ref def, use;
2348 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2350 if (df_chain_problem_p (DF_DU_CHAIN))
2351 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2352 DF_REF_CHAIN (def) = NULL;
2353 if (df_chain_problem_p (DF_UD_CHAIN))
2354 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2355 DF_REF_CHAIN (use) = NULL;
2357 FOR_BB_INSNS (bb, insn)
2358 if (INSN_P (insn))
2360 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2361 if (df_chain_problem_p (DF_DU_CHAIN))
2362 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2363 DF_REF_CHAIN (def) = NULL;
2364 if (df_chain_problem_p (DF_UD_CHAIN))
2366 FOR_EACH_INSN_INFO_USE (use, insn_info)
2367 DF_REF_CHAIN (use) = NULL;
2368 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2369 DF_REF_CHAIN (use) = NULL;
2374 bitmap_clear (df_chain->out_of_date_transfer_functions);
2375 df_chain->block_pool = NULL;
2379 /* Remove the chain problem completely. */
2381 static void
2382 df_chain_fully_remove_problem (void)
2384 df_chain_remove_problem ();
2385 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2386 free (df_chain);
2390 /* Create def-use or use-def chains. */
2392 static void
2393 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2395 df_chain_remove_problem ();
2396 df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2397 df_chain->optional_p = true;
2401 /* Reset all of the chains when the set of basic blocks changes. */
2403 static void
2404 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2406 df_chain_remove_problem ();
2410 /* Create the chains for a list of USEs. */
2412 static void
2413 df_chain_create_bb_process_use (bitmap local_rd,
2414 df_ref use,
2415 int top_flag)
2417 bitmap_iterator bi;
2418 unsigned int def_index;
2420 for (; use; use = DF_REF_NEXT_LOC (use))
2422 unsigned int uregno = DF_REF_REGNO (use);
2423 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2424 || (uregno >= FIRST_PSEUDO_REGISTER))
2426 /* Do not want to go through this for an uninitialized var. */
2427 int count = DF_DEFS_COUNT (uregno);
2428 if (count)
2430 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2432 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2433 unsigned int last_index = first_index + count - 1;
2435 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2437 df_ref def;
2438 if (def_index > last_index)
2439 break;
2441 def = DF_DEFS_GET (def_index);
2442 if (df_chain_problem_p (DF_DU_CHAIN))
2443 df_chain_create (def, use);
2444 if (df_chain_problem_p (DF_UD_CHAIN))
2445 df_chain_create (use, def);
2454 /* Create chains from reaching defs bitmaps for basic block BB. */
2456 static void
2457 df_chain_create_bb (unsigned int bb_index)
2459 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2460 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2461 rtx_insn *insn;
2462 bitmap_head cpy;
2464 bitmap_initialize (&cpy, &bitmap_default_obstack);
2465 bitmap_copy (&cpy, &bb_info->in);
2466 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2468 /* Since we are going forwards, process the artificial uses first
2469 then the artificial defs second. */
2471 #ifdef EH_USES
2472 /* Create the chains for the artificial uses from the EH_USES at the
2473 beginning of the block. */
2475 /* Artificials are only hard regs. */
2476 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2477 df_chain_create_bb_process_use (&cpy,
2478 df_get_artificial_uses (bb->index),
2479 DF_REF_AT_TOP);
2480 #endif
2482 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2484 /* Process the regular instructions next. */
2485 FOR_BB_INSNS (bb, insn)
2486 if (INSN_P (insn))
2488 unsigned int uid = INSN_UID (insn);
2490 /* First scan the uses and link them up with the defs that remain
2491 in the cpy vector. */
2492 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2493 if (df->changeable_flags & DF_EQ_NOTES)
2494 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2496 /* Since we are going forwards, process the defs second. */
2497 df_rd_simulate_one_insn (bb, insn, &cpy);
2500 /* Create the chains for the artificial uses of the hard registers
2501 at the end of the block. */
2502 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2503 df_chain_create_bb_process_use (&cpy,
2504 df_get_artificial_uses (bb->index),
2507 bitmap_clear (&cpy);
2510 /* Create def-use chains from reaching use bitmaps for basic blocks
2511 in BLOCKS. */
2513 static void
2514 df_chain_finalize (bitmap all_blocks)
2516 unsigned int bb_index;
2517 bitmap_iterator bi;
2519 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2521 df_chain_create_bb (bb_index);
2526 /* Free all storage associated with the problem. */
2528 static void
2529 df_chain_free (void)
2531 delete df_chain->block_pool;
2532 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2533 free (df_chain);
2537 /* Debugging info. */
2539 static void
2540 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2542 /* Artificials are only hard regs. */
2543 if (df->changeable_flags & DF_NO_HARD_REGS)
2544 return;
2545 if (df_chain_problem_p (DF_UD_CHAIN))
2547 df_ref use;
2549 fprintf (file,
2550 ";; UD chains for artificial uses at %s\n",
2551 top ? "top" : "bottom");
2552 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2553 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2554 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2556 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2557 df_chain_dump (DF_REF_CHAIN (use), file);
2558 fprintf (file, "\n");
2561 if (df_chain_problem_p (DF_DU_CHAIN))
2563 df_ref def;
2565 fprintf (file,
2566 ";; DU chains for artificial defs at %s\n",
2567 top ? "top" : "bottom");
2568 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2569 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2570 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2572 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2573 df_chain_dump (DF_REF_CHAIN (def), file);
2574 fprintf (file, "\n");
2579 static void
2580 df_chain_top_dump (basic_block bb, FILE *file)
2582 df_chain_bb_dump (bb, file, /*top=*/true);
2585 static void
2586 df_chain_bottom_dump (basic_block bb, FILE *file)
2588 df_chain_bb_dump (bb, file, /*top=*/false);
2591 static void
2592 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2594 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2596 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2597 df_ref use;
2599 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2600 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2601 FOR_EACH_INSN_INFO_USE (use, insn_info)
2602 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2603 || !(df->changeable_flags & DF_NO_HARD_REGS))
2605 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2606 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2607 fprintf (file, "read/write ");
2608 df_chain_dump (DF_REF_CHAIN (use), file);
2609 fprintf (file, "\n");
2611 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2612 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2613 || !(df->changeable_flags & DF_NO_HARD_REGS))
2615 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2616 df_chain_dump (DF_REF_CHAIN (use), file);
2617 fprintf (file, "\n");
2622 static void
2623 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2625 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2627 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2628 df_ref def;
2629 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2630 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2631 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2632 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2633 || !(df->changeable_flags & DF_NO_HARD_REGS))
2635 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2636 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2637 fprintf (file, "read/write ");
2638 df_chain_dump (DF_REF_CHAIN (def), file);
2639 fprintf (file, "\n");
2641 fprintf (file, "\n");
2645 static const struct df_problem problem_CHAIN =
2647 DF_CHAIN, /* Problem id. */
2648 DF_NONE, /* Direction. */
2649 df_chain_alloc, /* Allocate the problem specific data. */
2650 df_chain_reset, /* Reset global information. */
2651 NULL, /* Free basic block info. */
2652 NULL, /* Local compute function. */
2653 NULL, /* Init the solution specific data. */
2654 NULL, /* Iterative solver. */
2655 NULL, /* Confluence operator 0. */
2656 NULL, /* Confluence operator n. */
2657 NULL, /* Transfer function. */
2658 df_chain_finalize, /* Finalize function. */
2659 df_chain_free, /* Free all of the problem information. */
2660 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2661 NULL, /* Debugging. */
2662 df_chain_top_dump, /* Debugging start block. */
2663 df_chain_bottom_dump, /* Debugging end block. */
2664 df_chain_insn_top_dump, /* Debugging start insn. */
2665 df_chain_insn_bottom_dump, /* Debugging end insn. */
2666 NULL, /* Incremental solution verify start. */
2667 NULL, /* Incremental solution verify end. */
2668 &problem_RD, /* Dependent problem. */
2669 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2670 TV_DF_CHAIN, /* Timing variable. */
2671 false /* Reset blocks on dropping out of blocks_to_analyze. */
2675 /* Create a new DATAFLOW instance and add it to an existing instance
2676 of DF. The returned structure is what is used to get at the
2677 solution. */
2679 void
2680 df_chain_add_problem (unsigned int chain_flags)
2682 df_add_problem (&problem_CHAIN);
2683 df_chain->local_flags = chain_flags;
2684 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2687 #undef df_chain_problem_p
2690 /*----------------------------------------------------------------------------
2691 WORD LEVEL LIVE REGISTERS
2693 Find the locations in the function where any use of a pseudo can
2694 reach in the backwards direction. In and out bitvectors are built
2695 for each basic block. We only track pseudo registers that have a
2696 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2697 contain two bits corresponding to each of the subwords.
2699 ----------------------------------------------------------------------------*/
2701 /* Private data used to verify the solution for this problem. */
2702 struct df_word_lr_problem_data
2704 /* An obstack for the bitmaps we need for this problem. */
2705 bitmap_obstack word_lr_bitmaps;
2709 /* Free basic block info. */
2711 static void
2712 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2713 void *vbb_info)
2715 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2716 if (bb_info)
2718 bitmap_clear (&bb_info->use);
2719 bitmap_clear (&bb_info->def);
2720 bitmap_clear (&bb_info->in);
2721 bitmap_clear (&bb_info->out);
2726 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2727 not touched unless the block is new. */
2729 static void
2730 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2732 unsigned int bb_index;
2733 bitmap_iterator bi;
2734 basic_block bb;
2735 struct df_word_lr_problem_data *problem_data
2736 = XNEW (struct df_word_lr_problem_data);
2738 df_word_lr->problem_data = problem_data;
2740 df_grow_bb_info (df_word_lr);
2742 /* Create the mapping from regnos to slots. This does not change
2743 unless the problem is destroyed and recreated. In particular, if
2744 we end up deleting the only insn that used a subreg, we do not
2745 want to redo the mapping because this would invalidate everything
2746 else. */
2748 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2750 FOR_EACH_BB_FN (bb, cfun)
2751 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2753 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2754 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2756 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2758 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2760 /* When bitmaps are already initialized, just clear them. */
2761 if (bb_info->use.obstack)
2763 bitmap_clear (&bb_info->def);
2764 bitmap_clear (&bb_info->use);
2766 else
2768 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2769 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2770 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2771 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2775 df_word_lr->optional_p = true;
2779 /* Reset the global solution for recalculation. */
2781 static void
2782 df_word_lr_reset (bitmap all_blocks)
2784 unsigned int bb_index;
2785 bitmap_iterator bi;
2787 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2789 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2790 gcc_assert (bb_info);
2791 bitmap_clear (&bb_info->in);
2792 bitmap_clear (&bb_info->out);
2796 /* Examine REF, and if it is for a reg we're interested in, set or
2797 clear the bits corresponding to its subwords from the bitmap
2798 according to IS_SET. LIVE is the bitmap we should update. We do
2799 not track hard regs or pseudos of any size other than 2 *
2800 UNITS_PER_WORD.
2801 We return true if we changed the bitmap, or if we encountered a register
2802 we're not tracking. */
2804 bool
2805 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2807 rtx orig_reg = DF_REF_REG (ref);
2808 rtx reg = orig_reg;
2809 machine_mode reg_mode;
2810 unsigned regno;
2811 /* Left at -1 for whole accesses. */
2812 int which_subword = -1;
2813 bool changed = false;
2815 if (GET_CODE (reg) == SUBREG)
2816 reg = SUBREG_REG (orig_reg);
2817 regno = REGNO (reg);
2818 reg_mode = GET_MODE (reg);
2819 if (regno < FIRST_PSEUDO_REGISTER
2820 || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
2821 return true;
2823 if (GET_CODE (orig_reg) == SUBREG
2824 && df_read_modify_subreg_p (orig_reg))
2826 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2827 if (subreg_lowpart_p (orig_reg))
2828 which_subword = 0;
2829 else
2830 which_subword = 1;
2832 if (is_set)
2834 if (which_subword != 1)
2835 changed |= bitmap_set_bit (live, regno * 2);
2836 if (which_subword != 0)
2837 changed |= bitmap_set_bit (live, regno * 2 + 1);
2839 else
2841 if (which_subword != 1)
2842 changed |= bitmap_clear_bit (live, regno * 2);
2843 if (which_subword != 0)
2844 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2846 return changed;
2849 /* Compute local live register info for basic block BB. */
2851 static void
2852 df_word_lr_bb_local_compute (unsigned int bb_index)
2854 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2855 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2856 rtx_insn *insn;
2857 df_ref def, use;
2859 /* Ensure that artificial refs don't contain references to pseudos. */
2860 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2861 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2863 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2864 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2866 FOR_BB_INSNS_REVERSE (bb, insn)
2868 if (!NONDEBUG_INSN_P (insn))
2869 continue;
2871 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2872 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2873 /* If the def is to only part of the reg, it does
2874 not kill the other defs that reach here. */
2875 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2877 df_word_lr_mark_ref (def, true, &bb_info->def);
2878 df_word_lr_mark_ref (def, false, &bb_info->use);
2880 FOR_EACH_INSN_INFO_USE (use, insn_info)
2881 df_word_lr_mark_ref (use, true, &bb_info->use);
2886 /* Compute local live register info for each basic block within BLOCKS. */
2888 static void
2889 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2891 unsigned int bb_index;
2892 bitmap_iterator bi;
2894 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2896 if (bb_index == EXIT_BLOCK)
2898 unsigned regno;
2899 bitmap_iterator bi;
2900 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2901 regno, bi)
2902 gcc_unreachable ();
2904 else
2905 df_word_lr_bb_local_compute (bb_index);
2908 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2912 /* Initialize the solution vectors. */
2914 static void
2915 df_word_lr_init (bitmap all_blocks)
2917 unsigned int bb_index;
2918 bitmap_iterator bi;
2920 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2922 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2923 bitmap_copy (&bb_info->in, &bb_info->use);
2924 bitmap_clear (&bb_info->out);
2929 /* Confluence function that ignores fake edges. */
2931 static bool
2932 df_word_lr_confluence_n (edge e)
2934 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2935 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2937 return bitmap_ior_into (op1, op2);
2941 /* Transfer function. */
2943 static bool
2944 df_word_lr_transfer_function (int bb_index)
2946 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2947 bitmap in = &bb_info->in;
2948 bitmap out = &bb_info->out;
2949 bitmap use = &bb_info->use;
2950 bitmap def = &bb_info->def;
2952 return bitmap_ior_and_compl (in, use, out, def);
2956 /* Free all storage associated with the problem. */
2958 static void
2959 df_word_lr_free (void)
2961 struct df_word_lr_problem_data *problem_data
2962 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2964 if (df_word_lr->block_info)
2966 df_word_lr->block_info_size = 0;
2967 free (df_word_lr->block_info);
2968 df_word_lr->block_info = NULL;
2971 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2972 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2973 free (problem_data);
2974 free (df_word_lr);
2978 /* Debugging info at top of bb. */
2980 static void
2981 df_word_lr_top_dump (basic_block bb, FILE *file)
2983 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2984 if (!bb_info)
2985 return;
2987 fprintf (file, ";; blr in \t");
2988 df_print_word_regset (file, &bb_info->in);
2989 fprintf (file, ";; blr use \t");
2990 df_print_word_regset (file, &bb_info->use);
2991 fprintf (file, ";; blr def \t");
2992 df_print_word_regset (file, &bb_info->def);
2996 /* Debugging info at bottom of bb. */
2998 static void
2999 df_word_lr_bottom_dump (basic_block bb, FILE *file)
3001 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3002 if (!bb_info)
3003 return;
3005 fprintf (file, ";; blr out \t");
3006 df_print_word_regset (file, &bb_info->out);
3010 /* All of the information associated with every instance of the problem. */
3012 static const struct df_problem problem_WORD_LR =
3014 DF_WORD_LR, /* Problem id. */
3015 DF_BACKWARD, /* Direction. */
3016 df_word_lr_alloc, /* Allocate the problem specific data. */
3017 df_word_lr_reset, /* Reset global information. */
3018 df_word_lr_free_bb_info, /* Free basic block info. */
3019 df_word_lr_local_compute, /* Local compute function. */
3020 df_word_lr_init, /* Init the solution specific data. */
3021 df_worklist_dataflow, /* Worklist solver. */
3022 NULL, /* Confluence operator 0. */
3023 df_word_lr_confluence_n, /* Confluence operator n. */
3024 df_word_lr_transfer_function, /* Transfer function. */
3025 NULL, /* Finalize function. */
3026 df_word_lr_free, /* Free all of the problem information. */
3027 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
3028 NULL, /* Debugging. */
3029 df_word_lr_top_dump, /* Debugging start block. */
3030 df_word_lr_bottom_dump, /* Debugging end block. */
3031 NULL, /* Debugging start insn. */
3032 NULL, /* Debugging end insn. */
3033 NULL, /* Incremental solution verify start. */
3034 NULL, /* Incremental solution verify end. */
3035 NULL, /* Dependent problem. */
3036 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */
3037 TV_DF_WORD_LR, /* Timing variable. */
3038 false /* Reset blocks on dropping out of blocks_to_analyze. */
3042 /* Create a new DATAFLOW instance and add it to an existing instance
3043 of DF. The returned structure is what is used to get at the
3044 solution. */
3046 void
3047 df_word_lr_add_problem (void)
3049 df_add_problem (&problem_WORD_LR);
3050 /* These will be initialized when df_scan_blocks processes each
3051 block. */
3052 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3056 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
3057 any bits, which is used by the caller to determine whether a set is
3058 necessary. We also return true if there are other reasons not to delete
3059 an insn. */
3061 bool
3062 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3064 bool changed = false;
3065 df_ref def;
3067 FOR_EACH_INSN_DEF (def, insn)
3068 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3069 changed = true;
3070 else
3071 changed |= df_word_lr_mark_ref (def, false, live);
3072 return changed;
3076 /* Simulate the effects of the uses of INSN on LIVE. */
3078 void
3079 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3081 df_ref use;
3083 FOR_EACH_INSN_USE (use, insn)
3084 df_word_lr_mark_ref (use, true, live);
3087 /*----------------------------------------------------------------------------
3088 This problem computes REG_DEAD and REG_UNUSED notes.
3089 ----------------------------------------------------------------------------*/
3091 static void
3092 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3094 df_note->optional_p = true;
3097 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
3098 static void
3099 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
3101 if (dump_file)
3103 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3104 print_rtl (dump_file, note);
3105 fprintf (dump_file, "\n");
3110 /* After reg-stack, the x86 floating point stack regs are difficult to
3111 analyze because of all of the pushes, pops and rotations. Thus, we
3112 just leave the notes alone. */
3114 #ifdef STACK_REGS
3115 static inline bool
3116 df_ignore_stack_reg (int regno)
3118 return regstack_completed
3119 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3121 #else
3122 static inline bool
3123 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3125 return false;
3127 #endif
3130 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
3132 static void
3133 df_remove_dead_and_unused_notes (rtx_insn *insn)
3135 rtx *pprev = &REG_NOTES (insn);
3136 rtx link = *pprev;
3138 while (link)
3140 switch (REG_NOTE_KIND (link))
3142 case REG_DEAD:
3143 /* After reg-stack, we need to ignore any unused notes
3144 for the stack registers. */
3145 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3147 pprev = &XEXP (link, 1);
3148 link = *pprev;
3150 else
3152 rtx next = XEXP (link, 1);
3153 if (REG_DEAD_DEBUGGING)
3154 df_print_note ("deleting: ", insn, link);
3155 free_EXPR_LIST_node (link);
3156 *pprev = link = next;
3158 break;
3160 case REG_UNUSED:
3161 /* After reg-stack, we need to ignore any unused notes
3162 for the stack registers. */
3163 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3165 pprev = &XEXP (link, 1);
3166 link = *pprev;
3168 else
3170 rtx next = XEXP (link, 1);
3171 if (REG_DEAD_DEBUGGING)
3172 df_print_note ("deleting: ", insn, link);
3173 free_EXPR_LIST_node (link);
3174 *pprev = link = next;
3176 break;
3178 default:
3179 pprev = &XEXP (link, 1);
3180 link = *pprev;
3181 break;
3186 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
3187 as the bitmap of currently live registers. */
3189 static void
3190 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3192 rtx *pprev = &REG_NOTES (insn);
3193 rtx link = *pprev;
3195 while (link)
3197 switch (REG_NOTE_KIND (link))
3199 case REG_EQUAL:
3200 case REG_EQUIV:
3202 /* Remove the notes that refer to dead registers. As we have at most
3203 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3204 so we need to purge the complete EQ_USES vector when removing
3205 the note using df_notes_rescan. */
3206 df_ref use;
3207 bool deleted = false;
3209 FOR_EACH_INSN_EQ_USE (use, insn)
3210 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
3211 && DF_REF_LOC (use)
3212 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3213 && !bitmap_bit_p (live, DF_REF_REGNO (use))
3214 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3216 deleted = true;
3217 break;
3219 if (deleted)
3221 rtx next;
3222 if (REG_DEAD_DEBUGGING)
3223 df_print_note ("deleting: ", insn, link);
3224 next = XEXP (link, 1);
3225 free_EXPR_LIST_node (link);
3226 *pprev = link = next;
3227 df_notes_rescan (insn);
3229 else
3231 pprev = &XEXP (link, 1);
3232 link = *pprev;
3234 break;
3237 default:
3238 pprev = &XEXP (link, 1);
3239 link = *pprev;
3240 break;
3245 /* Set a NOTE_TYPE note for REG in INSN. */
3247 static inline void
3248 df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3250 gcc_checking_assert (!DEBUG_INSN_P (insn));
3251 add_reg_note (insn, note_type, reg);
3254 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3255 arguments. Return true if the register value described by MWS's
3256 mw_reg is known to be completely unused, and if mw_reg can therefore
3257 be used in a REG_UNUSED note. */
3259 static bool
3260 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3261 bitmap live, bitmap artificial_uses)
3263 unsigned int r;
3265 /* If MWS describes a partial reference, create REG_UNUSED notes for
3266 individual hard registers. */
3267 if (mws->flags & DF_REF_PARTIAL)
3268 return false;
3270 /* Likewise if some part of the register is used. */
3271 for (r = mws->start_regno; r <= mws->end_regno; r++)
3272 if (bitmap_bit_p (live, r)
3273 || bitmap_bit_p (artificial_uses, r))
3274 return false;
3276 gcc_assert (REG_P (mws->mw_reg));
3277 return true;
3281 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3282 based on the bits in LIVE. Do not generate notes for registers in
3283 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3284 not generated if the reg is both read and written by the
3285 instruction.
3288 static void
3289 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3290 bitmap live, bitmap do_not_gen,
3291 bitmap artificial_uses,
3292 struct dead_debug_local *debug)
3294 unsigned int r;
3296 if (REG_DEAD_DEBUGGING && dump_file)
3297 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3298 mws->start_regno, mws->end_regno);
3300 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3302 unsigned int regno = mws->start_regno;
3303 df_set_note (REG_UNUSED, insn, mws->mw_reg);
3304 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3306 if (REG_DEAD_DEBUGGING)
3307 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3309 bitmap_set_bit (do_not_gen, regno);
3310 /* Only do this if the value is totally dead. */
3312 else
3313 for (r = mws->start_regno; r <= mws->end_regno; r++)
3315 if (!bitmap_bit_p (live, r)
3316 && !bitmap_bit_p (artificial_uses, r))
3318 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3319 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3320 if (REG_DEAD_DEBUGGING)
3321 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3323 bitmap_set_bit (do_not_gen, r);
3328 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3329 arguments. Return true if the register value described by MWS's
3330 mw_reg is known to be completely dead, and if mw_reg can therefore
3331 be used in a REG_DEAD note. */
3333 static bool
3334 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3335 bitmap live, bitmap artificial_uses,
3336 bitmap do_not_gen)
3338 unsigned int r;
3340 /* If MWS describes a partial reference, create REG_DEAD notes for
3341 individual hard registers. */
3342 if (mws->flags & DF_REF_PARTIAL)
3343 return false;
3345 /* Likewise if some part of the register is not dead. */
3346 for (r = mws->start_regno; r <= mws->end_regno; r++)
3347 if (bitmap_bit_p (live, r)
3348 || bitmap_bit_p (artificial_uses, r)
3349 || bitmap_bit_p (do_not_gen, r))
3350 return false;
3352 gcc_assert (REG_P (mws->mw_reg));
3353 return true;
3356 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3357 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3358 from being set if the instruction both reads and writes the
3359 register. */
3361 static void
3362 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3363 bitmap live, bitmap do_not_gen,
3364 bitmap artificial_uses, bool *added_notes_p)
3366 unsigned int r;
3367 bool is_debug = *added_notes_p;
3369 *added_notes_p = false;
3371 if (REG_DEAD_DEBUGGING && dump_file)
3373 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3374 mws->start_regno, mws->end_regno);
3375 df_print_regset (dump_file, do_not_gen);
3376 fprintf (dump_file, " live =");
3377 df_print_regset (dump_file, live);
3378 fprintf (dump_file, " artificial uses =");
3379 df_print_regset (dump_file, artificial_uses);
3382 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3384 if (is_debug)
3386 *added_notes_p = true;
3387 return;
3389 /* Add a dead note for the entire multi word register. */
3390 df_set_note (REG_DEAD, insn, mws->mw_reg);
3391 if (REG_DEAD_DEBUGGING)
3392 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3394 else
3396 for (r = mws->start_regno; r <= mws->end_regno; r++)
3397 if (!bitmap_bit_p (live, r)
3398 && !bitmap_bit_p (artificial_uses, r)
3399 && !bitmap_bit_p (do_not_gen, r))
3401 if (is_debug)
3403 *added_notes_p = true;
3404 return;
3406 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3407 if (REG_DEAD_DEBUGGING)
3408 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3411 return;
3415 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3416 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3418 static void
3419 df_create_unused_note (rtx_insn *insn, df_ref def,
3420 bitmap live, bitmap artificial_uses,
3421 struct dead_debug_local *debug)
3423 unsigned int dregno = DF_REF_REGNO (def);
3425 if (REG_DEAD_DEBUGGING && dump_file)
3427 fprintf (dump_file, " regular looking at def ");
3428 df_ref_debug (def, dump_file);
3431 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3432 || bitmap_bit_p (live, dregno)
3433 || bitmap_bit_p (artificial_uses, dregno)
3434 || df_ignore_stack_reg (dregno)))
3436 rtx reg = (DF_REF_LOC (def))
3437 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3438 df_set_note (REG_UNUSED, insn, reg);
3439 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3440 if (REG_DEAD_DEBUGGING)
3441 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3444 return;
3448 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3449 info: lifetime, bb, and number of defs and uses for basic block
3450 BB. The three bitvectors are scratch regs used here. */
3452 static void
3453 df_note_bb_compute (unsigned int bb_index,
3454 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3456 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3457 rtx_insn *insn;
3458 df_ref def, use;
3459 struct dead_debug_local debug;
3461 dead_debug_local_init (&debug, NULL, NULL);
3463 bitmap_copy (live, df_get_live_out (bb));
3464 bitmap_clear (artificial_uses);
3466 if (REG_DEAD_DEBUGGING && dump_file)
3468 fprintf (dump_file, "live at bottom ");
3469 df_print_regset (dump_file, live);
3472 /* Process the artificial defs and uses at the bottom of the block
3473 to begin processing. */
3474 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3476 if (REG_DEAD_DEBUGGING && dump_file)
3477 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3479 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3480 bitmap_clear_bit (live, DF_REF_REGNO (def));
3483 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3484 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3486 unsigned int regno = DF_REF_REGNO (use);
3487 bitmap_set_bit (live, regno);
3489 /* Notes are not generated for any of the artificial registers
3490 at the bottom of the block. */
3491 bitmap_set_bit (artificial_uses, regno);
3494 if (REG_DEAD_DEBUGGING && dump_file)
3496 fprintf (dump_file, "live before artificials out ");
3497 df_print_regset (dump_file, live);
3500 FOR_BB_INSNS_REVERSE (bb, insn)
3502 if (!INSN_P (insn))
3503 continue;
3505 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3506 df_mw_hardreg *mw;
3507 int debug_insn;
3509 debug_insn = DEBUG_INSN_P (insn);
3511 bitmap_clear (do_not_gen);
3512 df_remove_dead_and_unused_notes (insn);
3514 /* Process the defs. */
3515 if (CALL_P (insn))
3517 if (REG_DEAD_DEBUGGING && dump_file)
3519 fprintf (dump_file, "processing call %d\n live =",
3520 INSN_UID (insn));
3521 df_print_regset (dump_file, live);
3524 /* We only care about real sets for calls. Clobbers cannot
3525 be depended on to really die. */
3526 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3527 if ((DF_MWS_REG_DEF_P (mw))
3528 && !df_ignore_stack_reg (mw->start_regno))
3529 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3530 artificial_uses, &debug);
3532 /* All of the defs except the return value are some sort of
3533 clobber. This code is for the return. */
3534 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3536 unsigned int dregno = DF_REF_REGNO (def);
3537 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3539 df_create_unused_note (insn,
3540 def, live, artificial_uses, &debug);
3541 bitmap_set_bit (do_not_gen, dregno);
3544 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3545 bitmap_clear_bit (live, dregno);
3548 else
3550 /* Regular insn. */
3551 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3552 if (DF_MWS_REG_DEF_P (mw))
3553 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3554 artificial_uses, &debug);
3556 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3558 unsigned int dregno = DF_REF_REGNO (def);
3559 df_create_unused_note (insn,
3560 def, live, artificial_uses, &debug);
3562 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3563 bitmap_set_bit (do_not_gen, dregno);
3565 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3566 bitmap_clear_bit (live, dregno);
3570 /* Process the uses. */
3571 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3572 if (DF_MWS_REG_USE_P (mw)
3573 && !df_ignore_stack_reg (mw->start_regno))
3575 bool really_add_notes = debug_insn != 0;
3577 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3578 artificial_uses,
3579 &really_add_notes);
3581 if (really_add_notes)
3582 debug_insn = -1;
3585 FOR_EACH_INSN_INFO_USE (use, insn_info)
3587 unsigned int uregno = DF_REF_REGNO (use);
3589 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3591 fprintf (dump_file, " regular looking at use ");
3592 df_ref_debug (use, dump_file);
3595 if (!bitmap_bit_p (live, uregno))
3597 if (debug_insn)
3599 if (debug_insn > 0)
3601 /* We won't add REG_UNUSED or REG_DEAD notes for
3602 these, so we don't have to mess with them in
3603 debug insns either. */
3604 if (!bitmap_bit_p (artificial_uses, uregno)
3605 && !df_ignore_stack_reg (uregno))
3606 dead_debug_add (&debug, use, uregno);
3607 continue;
3609 break;
3611 else
3612 dead_debug_insert_temp (&debug, uregno, insn,
3613 DEBUG_TEMP_BEFORE_WITH_REG);
3615 if ( (!(DF_REF_FLAGS (use)
3616 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3617 && (!bitmap_bit_p (do_not_gen, uregno))
3618 && (!bitmap_bit_p (artificial_uses, uregno))
3619 && (!df_ignore_stack_reg (uregno)))
3621 rtx reg = (DF_REF_LOC (use))
3622 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3623 df_set_note (REG_DEAD, insn, reg);
3625 if (REG_DEAD_DEBUGGING)
3626 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3628 /* This register is now live. */
3629 bitmap_set_bit (live, uregno);
3633 df_remove_dead_eq_notes (insn, live);
3635 if (debug_insn == -1)
3637 /* ??? We could probably do better here, replacing dead
3638 registers with their definitions. */
3639 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3640 df_insn_rescan_debug_internal (insn);
3644 dead_debug_local_finish (&debug, NULL);
3648 /* Compute register info: lifetime, bb, and number of defs and uses. */
3649 static void
3650 df_note_compute (bitmap all_blocks)
3652 unsigned int bb_index;
3653 bitmap_iterator bi;
3654 bitmap_head live, do_not_gen, artificial_uses;
3656 bitmap_initialize (&live, &df_bitmap_obstack);
3657 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3658 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3660 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3662 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3663 pseudos in debug insns because we don't always (re)visit blocks
3664 with death points after visiting dead uses. Even changing this
3665 loop to postorder would still leave room for visiting a death
3666 point before visiting a subsequent debug use. */
3667 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3670 bitmap_clear (&live);
3671 bitmap_clear (&do_not_gen);
3672 bitmap_clear (&artificial_uses);
3676 /* Free all storage associated with the problem. */
3678 static void
3679 df_note_free (void)
3681 free (df_note);
3685 /* All of the information associated every instance of the problem. */
3687 static const struct df_problem problem_NOTE =
3689 DF_NOTE, /* Problem id. */
3690 DF_NONE, /* Direction. */
3691 df_note_alloc, /* Allocate the problem specific data. */
3692 NULL, /* Reset global information. */
3693 NULL, /* Free basic block info. */
3694 df_note_compute, /* Local compute function. */
3695 NULL, /* Init the solution specific data. */
3696 NULL, /* Iterative solver. */
3697 NULL, /* Confluence operator 0. */
3698 NULL, /* Confluence operator n. */
3699 NULL, /* Transfer function. */
3700 NULL, /* Finalize function. */
3701 df_note_free, /* Free all of the problem information. */
3702 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3703 NULL, /* Debugging. */
3704 NULL, /* Debugging start block. */
3705 NULL, /* Debugging end block. */
3706 NULL, /* Debugging start insn. */
3707 NULL, /* Debugging end insn. */
3708 NULL, /* Incremental solution verify start. */
3709 NULL, /* Incremental solution verify end. */
3710 &problem_LR, /* Dependent problem. */
3711 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3712 TV_DF_NOTE, /* Timing variable. */
3713 false /* Reset blocks on dropping out of blocks_to_analyze. */
3717 /* Create a new DATAFLOW instance and add it to an existing instance
3718 of DF. The returned structure is what is used to get at the
3719 solution. */
3721 void
3722 df_note_add_problem (void)
3724 df_add_problem (&problem_NOTE);
3730 /*----------------------------------------------------------------------------
3731 Functions for simulating the effects of single insns.
3733 You can either simulate in the forwards direction, starting from
3734 the top of a block or the backwards direction from the end of the
3735 block. If you go backwards, defs are examined first to clear bits,
3736 then uses are examined to set bits. If you go forwards, defs are
3737 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3738 are examined to clear bits. In either case, the result of examining
3739 a def can be undone (respectively by a use or a REG_UNUSED note).
3741 If you start at the top of the block, use one of DF_LIVE_IN or
3742 DF_LR_IN. If you start at the bottom of the block use one of
3743 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3744 THEY WILL BE DESTROYED.
3745 ----------------------------------------------------------------------------*/
3748 /* Find the set of DEFs for INSN. */
3750 void
3751 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3753 df_ref def;
3755 FOR_EACH_INSN_DEF (def, insn)
3756 bitmap_set_bit (defs, DF_REF_REGNO (def));
3759 /* Find the set of uses for INSN. This includes partial defs. */
3761 static void
3762 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3764 df_ref def, use;
3765 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3767 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3768 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3769 bitmap_set_bit (uses, DF_REF_REGNO (def));
3770 FOR_EACH_INSN_INFO_USE (use, insn_info)
3771 bitmap_set_bit (uses, DF_REF_REGNO (use));
3774 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3776 void
3777 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3779 df_ref def;
3781 FOR_EACH_INSN_DEF (def, insn)
3782 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3783 bitmap_set_bit (defs, DF_REF_REGNO (def));
3787 /* Simulate the effects of the defs of INSN on LIVE. */
3789 void
3790 df_simulate_defs (rtx_insn *insn, bitmap live)
3792 df_ref def;
3794 FOR_EACH_INSN_DEF (def, insn)
3796 unsigned int dregno = DF_REF_REGNO (def);
3798 /* If the def is to only part of the reg, it does
3799 not kill the other defs that reach here. */
3800 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3801 bitmap_clear_bit (live, dregno);
3806 /* Simulate the effects of the uses of INSN on LIVE. */
3808 void
3809 df_simulate_uses (rtx_insn *insn, bitmap live)
3811 df_ref use;
3813 if (DEBUG_INSN_P (insn))
3814 return;
3816 FOR_EACH_INSN_USE (use, insn)
3817 /* Add use to set of uses in this BB. */
3818 bitmap_set_bit (live, DF_REF_REGNO (use));
3822 /* Add back the always live regs in BB to LIVE. */
3824 static inline void
3825 df_simulate_fixup_sets (basic_block bb, bitmap live)
3827 /* These regs are considered always live so if they end up dying
3828 because of some def, we need to bring the back again. */
3829 if (bb_has_eh_pred (bb))
3830 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3831 else
3832 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3836 /*----------------------------------------------------------------------------
3837 The following three functions are used only for BACKWARDS scanning:
3838 i.e. they process the defs before the uses.
3840 df_simulate_initialize_backwards should be called first with a
3841 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3842 df_simulate_one_insn_backwards should be called for each insn in
3843 the block, starting with the last one. Finally,
3844 df_simulate_finalize_backwards can be called to get a new value
3845 of the sets at the top of the block (this is rarely used).
3846 ----------------------------------------------------------------------------*/
3848 /* Apply the artificial uses and defs at the end of BB in a backwards
3849 direction. */
3851 void
3852 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3854 df_ref def, use;
3855 int bb_index = bb->index;
3857 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3858 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3859 bitmap_clear_bit (live, DF_REF_REGNO (def));
3861 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3862 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3863 bitmap_set_bit (live, DF_REF_REGNO (use));
3867 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3869 void
3870 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3872 if (!NONDEBUG_INSN_P (insn))
3873 return;
3875 df_simulate_defs (insn, live);
3876 df_simulate_uses (insn, live);
3877 df_simulate_fixup_sets (bb, live);
3881 /* Apply the artificial uses and defs at the top of BB in a backwards
3882 direction. */
3884 void
3885 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3887 df_ref def;
3888 #ifdef EH_USES
3889 df_ref use;
3890 #endif
3891 int bb_index = bb->index;
3893 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3894 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3895 bitmap_clear_bit (live, DF_REF_REGNO (def));
3897 #ifdef EH_USES
3898 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3899 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3900 bitmap_set_bit (live, DF_REF_REGNO (use));
3901 #endif
3903 /*----------------------------------------------------------------------------
3904 The following three functions are used only for FORWARDS scanning:
3905 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3906 Thus it is important to add the DF_NOTES problem to the stack of
3907 problems computed before using these functions.
3909 df_simulate_initialize_forwards should be called first with a
3910 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3911 df_simulate_one_insn_forwards should be called for each insn in
3912 the block, starting with the first one.
3913 ----------------------------------------------------------------------------*/
3915 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3916 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3917 defs live. */
3919 void
3920 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3922 df_ref def;
3923 int bb_index = bb->index;
3925 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3926 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3927 bitmap_set_bit (live, DF_REF_REGNO (def));
3930 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3932 void
3933 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3935 rtx link;
3936 if (! INSN_P (insn))
3937 return;
3939 /* Make sure that DF_NOTE really is an active df problem. */
3940 gcc_assert (df_note);
3942 /* Note that this is the opposite as how the problem is defined, because
3943 in the LR problem defs _kill_ liveness. However, they do so backwards,
3944 while here the scan is performed forwards! So, first assume that the
3945 def is live, and if this is not true REG_UNUSED notes will rectify the
3946 situation. */
3947 df_simulate_find_noclobber_defs (insn, live);
3949 /* Clear all of the registers that go dead. */
3950 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3952 switch (REG_NOTE_KIND (link))
3954 case REG_DEAD:
3955 case REG_UNUSED:
3957 rtx reg = XEXP (link, 0);
3958 bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
3960 break;
3961 default:
3962 break;
3965 df_simulate_fixup_sets (bb, live);
3968 /* Used by the next two functions to encode information about the
3969 memory references we found. */
3970 #define MEMREF_NORMAL 1
3971 #define MEMREF_VOLATILE 2
3973 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3975 static int
3976 find_memory (rtx_insn *insn)
3978 int flags = 0;
3979 subrtx_iterator::array_type array;
3980 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3982 const_rtx x = *iter;
3983 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3984 flags |= MEMREF_VOLATILE;
3985 else if (MEM_P (x))
3987 if (MEM_VOLATILE_P (x))
3988 flags |= MEMREF_VOLATILE;
3989 else if (!MEM_READONLY_P (x))
3990 flags |= MEMREF_NORMAL;
3993 return flags;
3996 /* A subroutine of can_move_insns_across_p called through note_stores.
3997 DATA points to an integer in which we set either the bit for
3998 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3999 of either kind. */
4001 static void
4002 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4003 void *data ATTRIBUTE_UNUSED)
4005 int *pflags = (int *)data;
4006 if (GET_CODE (x) == SUBREG)
4007 x = XEXP (x, 0);
4008 /* Treat stores to SP as stores to memory, this will prevent problems
4009 when there are references to the stack frame. */
4010 if (x == stack_pointer_rtx)
4011 *pflags |= MEMREF_VOLATILE;
4012 if (!MEM_P (x))
4013 return;
4014 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4017 /* Scan BB backwards, using df_simulate functions to keep track of
4018 lifetimes, up to insn POINT. The result is stored in LIVE. */
4020 void
4021 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4023 rtx_insn *insn;
4024 bitmap_copy (live, df_get_live_out (bb));
4025 df_simulate_initialize_backwards (bb, live);
4027 /* Scan and update life information until we reach the point we're
4028 interested in. */
4029 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4030 df_simulate_one_insn_backwards (bb, insn, live);
4033 /* Return true if it is safe to move a group of insns, described by
4034 the range FROM to TO, backwards across another group of insns,
4035 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4036 are no insns between ACROSS_TO and FROM, but they may be in
4037 different basic blocks; MERGE_BB is the block from which the
4038 insns will be moved. The caller must pass in a regset MERGE_LIVE
4039 which specifies the registers live after TO.
4041 This function may be called in one of two cases: either we try to
4042 move identical instructions from all successor blocks into their
4043 predecessor, or we try to move from only one successor block. If
4044 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4045 the second case. It should contain a set of registers live at the
4046 end of ACROSS_TO which must not be clobbered by moving the insns.
4047 In that case, we're also more careful about moving memory references
4048 and trapping insns.
4050 We return false if it is not safe to move the entire group, but it
4051 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4052 is set to point at the last moveable insn in such a case. */
4054 bool
4055 can_move_insns_across (rtx_insn *from, rtx_insn *to,
4056 rtx_insn *across_from, rtx_insn *across_to,
4057 basic_block merge_bb, regset merge_live,
4058 regset other_branch_live, rtx_insn **pmove_upto)
4060 rtx_insn *insn, *next, *max_to;
4061 bitmap merge_set, merge_use, local_merge_live;
4062 bitmap test_set, test_use;
4063 unsigned i, fail = 0;
4064 bitmap_iterator bi;
4065 int memrefs_in_across = 0;
4066 int mem_sets_in_across = 0;
4067 bool trapping_insns_in_across = false;
4069 if (pmove_upto != NULL)
4070 *pmove_upto = NULL;
4072 /* Find real bounds, ignoring debug insns. */
4073 while (!NONDEBUG_INSN_P (from) && from != to)
4074 from = NEXT_INSN (from);
4075 while (!NONDEBUG_INSN_P (to) && from != to)
4076 to = PREV_INSN (to);
4078 for (insn = across_to; ; insn = next)
4080 if (CALL_P (insn))
4082 if (RTL_CONST_OR_PURE_CALL_P (insn))
4083 /* Pure functions can read from memory. Const functions can
4084 read from arguments that the ABI has forced onto the stack.
4085 Neither sort of read can be volatile. */
4086 memrefs_in_across |= MEMREF_NORMAL;
4087 else
4089 memrefs_in_across |= MEMREF_VOLATILE;
4090 mem_sets_in_across |= MEMREF_VOLATILE;
4093 if (NONDEBUG_INSN_P (insn))
4095 if (volatile_insn_p (PATTERN (insn)))
4096 return false;
4097 memrefs_in_across |= find_memory (insn);
4098 note_stores (PATTERN (insn), find_memory_stores,
4099 &mem_sets_in_across);
4100 /* This is used just to find sets of the stack pointer. */
4101 memrefs_in_across |= mem_sets_in_across;
4102 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4104 next = PREV_INSN (insn);
4105 if (insn == across_from)
4106 break;
4109 /* Collect:
4110 MERGE_SET = set of registers set in MERGE_BB
4111 MERGE_USE = set of registers used in MERGE_BB and live at its top
4112 MERGE_LIVE = set of registers live at the point inside the MERGE
4113 range that we've reached during scanning
4114 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4115 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4116 and live before ACROSS_FROM. */
4118 merge_set = BITMAP_ALLOC (&reg_obstack);
4119 merge_use = BITMAP_ALLOC (&reg_obstack);
4120 local_merge_live = BITMAP_ALLOC (&reg_obstack);
4121 test_set = BITMAP_ALLOC (&reg_obstack);
4122 test_use = BITMAP_ALLOC (&reg_obstack);
4124 /* Compute the set of registers set and used in the ACROSS range. */
4125 if (other_branch_live != NULL)
4126 bitmap_copy (test_use, other_branch_live);
4127 df_simulate_initialize_backwards (merge_bb, test_use);
4128 for (insn = across_to; ; insn = next)
4130 if (NONDEBUG_INSN_P (insn))
4132 df_simulate_find_defs (insn, test_set);
4133 df_simulate_defs (insn, test_use);
4134 df_simulate_uses (insn, test_use);
4136 next = PREV_INSN (insn);
4137 if (insn == across_from)
4138 break;
4141 /* Compute an upper bound for the amount of insns moved, by finding
4142 the first insn in MERGE that sets a register in TEST_USE, or uses
4143 a register in TEST_SET. We also check for calls, trapping operations,
4144 and memory references. */
4145 max_to = NULL;
4146 for (insn = from; ; insn = next)
4148 if (CALL_P (insn))
4149 break;
4150 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4151 break;
4152 if (NONDEBUG_INSN_P (insn))
4154 if (may_trap_or_fault_p (PATTERN (insn))
4155 && (trapping_insns_in_across
4156 || other_branch_live != NULL
4157 || volatile_insn_p (PATTERN (insn))))
4158 break;
4160 /* We cannot move memory stores past each other, or move memory
4161 reads past stores, at least not without tracking them and
4162 calling true_dependence on every pair.
4164 If there is no other branch and no memory references or
4165 sets in the ACROSS range, we can move memory references
4166 freely, even volatile ones.
4168 Otherwise, the rules are as follows: volatile memory
4169 references and stores can't be moved at all, and any type
4170 of memory reference can't be moved if there are volatile
4171 accesses or stores in the ACROSS range. That leaves
4172 normal reads, which can be moved, as the trapping case is
4173 dealt with elsewhere. */
4174 if (other_branch_live != NULL || memrefs_in_across != 0)
4176 int mem_ref_flags = 0;
4177 int mem_set_flags = 0;
4178 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
4179 mem_ref_flags = find_memory (insn);
4180 /* Catch sets of the stack pointer. */
4181 mem_ref_flags |= mem_set_flags;
4183 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4184 break;
4185 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4186 break;
4187 if (mem_set_flags != 0
4188 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4189 break;
4191 df_simulate_find_uses (insn, merge_use);
4192 /* We're only interested in uses which use a value live at
4193 the top, not one previously set in this block. */
4194 bitmap_and_compl_into (merge_use, merge_set);
4195 df_simulate_find_defs (insn, merge_set);
4196 if (bitmap_intersect_p (merge_set, test_use)
4197 || bitmap_intersect_p (merge_use, test_set))
4198 break;
4199 if (!HAVE_cc0 || !sets_cc0_p (insn))
4200 max_to = insn;
4202 next = NEXT_INSN (insn);
4203 if (insn == to)
4204 break;
4206 if (max_to != to)
4207 fail = 1;
4209 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4210 goto out;
4212 /* Now, lower this upper bound by also taking into account that
4213 a range of insns moved across ACROSS must not leave a register
4214 live at the end that will be clobbered in ACROSS. We need to
4215 find a point where TEST_SET & LIVE == 0.
4217 Insns in the MERGE range that set registers which are also set
4218 in the ACROSS range may still be moved as long as we also move
4219 later insns which use the results of the set, and make the
4220 register dead again. This is verified by the condition stated
4221 above. We only need to test it for registers that are set in
4222 the moved region.
4224 MERGE_LIVE is provided by the caller and holds live registers after
4225 TO. */
4226 bitmap_copy (local_merge_live, merge_live);
4227 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4228 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4230 /* We're not interested in registers that aren't set in the moved
4231 region at all. */
4232 bitmap_and_into (local_merge_live, merge_set);
4233 for (;;)
4235 if (NONDEBUG_INSN_P (insn))
4237 if (!bitmap_intersect_p (test_set, local_merge_live)
4238 && (!HAVE_cc0 || !sets_cc0_p (insn)))
4240 max_to = insn;
4241 break;
4244 df_simulate_one_insn_backwards (merge_bb, insn,
4245 local_merge_live);
4247 if (insn == from)
4249 fail = 1;
4250 goto out;
4252 insn = PREV_INSN (insn);
4255 if (max_to != to)
4256 fail = 1;
4258 if (pmove_upto)
4259 *pmove_upto = max_to;
4261 /* For small register class machines, don't lengthen lifetimes of
4262 hard registers before reload. */
4263 if (! reload_completed
4264 && targetm.small_register_classes_for_mode_p (VOIDmode))
4266 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4268 if (i < FIRST_PSEUDO_REGISTER
4269 && ! fixed_regs[i]
4270 && ! global_regs[i])
4272 fail = 1;
4273 break;
4278 out:
4279 BITMAP_FREE (merge_set);
4280 BITMAP_FREE (merge_use);
4281 BITMAP_FREE (local_merge_live);
4282 BITMAP_FREE (test_set);
4283 BITMAP_FREE (test_use);
4285 return !fail;
4289 /*----------------------------------------------------------------------------
4290 MULTIPLE DEFINITIONS
4292 Find the locations in the function reached by multiple definition sites
4293 for a live pseudo. In and out bitvectors are built for each basic
4294 block. They are restricted for efficiency to live registers.
4296 The gen and kill sets for the problem are obvious. Together they
4297 include all defined registers in a basic block; the gen set includes
4298 registers where a partial or conditional or may-clobber definition is
4299 last in the BB, while the kill set includes registers with a complete
4300 definition coming last. However, the computation of the dataflow
4301 itself is interesting.
4303 The idea behind it comes from SSA form's iterated dominance frontier
4304 criterion for inserting PHI functions. Just like in that case, we can use
4305 the dominance frontier to find places where multiple definitions meet;
4306 a register X defined in a basic block BB1 has multiple definitions in
4307 basic blocks in BB1's dominance frontier.
4309 So, the in-set of a basic block BB2 is not just the union of the
4310 out-sets of BB2's predecessors, but includes some more bits that come
4311 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4312 the previous paragraph). I called this set the init-set of BB2.
4314 (Note: I actually use the kill-set only to build the init-set.
4315 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4317 For example, if you have
4319 BB1 : r10 = 0
4320 r11 = 0
4321 if <...> goto BB2 else goto BB3;
4323 BB2 : r10 = 1
4324 r12 = 1
4325 goto BB3;
4327 BB3 :
4329 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4330 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4331 not need to iterate the dominance frontier, because we do not insert
4332 anything like PHI functions there! Instead, dataflow will take care of
4333 propagating the information to BB3's successors.
4334 ---------------------------------------------------------------------------*/
4336 /* Private data used to verify the solution for this problem. */
4337 struct df_md_problem_data
4339 /* An obstack for the bitmaps we need for this problem. */
4340 bitmap_obstack md_bitmaps;
4343 /* Scratch var used by transfer functions. This is used to do md analysis
4344 only for live registers. */
4345 static bitmap_head df_md_scratch;
4348 static void
4349 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4350 void *vbb_info)
4352 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4353 if (bb_info)
4355 bitmap_clear (&bb_info->kill);
4356 bitmap_clear (&bb_info->gen);
4357 bitmap_clear (&bb_info->init);
4358 bitmap_clear (&bb_info->in);
4359 bitmap_clear (&bb_info->out);
4364 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4365 not touched unless the block is new. */
4367 static void
4368 df_md_alloc (bitmap all_blocks)
4370 unsigned int bb_index;
4371 bitmap_iterator bi;
4372 struct df_md_problem_data *problem_data;
4374 df_grow_bb_info (df_md);
4375 if (df_md->problem_data)
4376 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4377 else
4379 problem_data = XNEW (struct df_md_problem_data);
4380 df_md->problem_data = problem_data;
4381 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4383 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4385 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4387 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4388 /* When bitmaps are already initialized, just clear them. */
4389 if (bb_info->init.obstack)
4391 bitmap_clear (&bb_info->init);
4392 bitmap_clear (&bb_info->gen);
4393 bitmap_clear (&bb_info->kill);
4394 bitmap_clear (&bb_info->in);
4395 bitmap_clear (&bb_info->out);
4397 else
4399 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4400 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4401 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4402 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4403 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4407 df_md->optional_p = true;
4410 /* Add the effect of the top artificial defs of BB to the multiple definitions
4411 bitmap LOCAL_MD. */
4413 void
4414 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4416 int bb_index = bb->index;
4417 df_ref def;
4418 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4419 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4421 unsigned int dregno = DF_REF_REGNO (def);
4422 if (DF_REF_FLAGS (def)
4423 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4424 bitmap_set_bit (local_md, dregno);
4425 else
4426 bitmap_clear_bit (local_md, dregno);
4431 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4432 LOCAL_MD. */
4434 void
4435 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4436 bitmap local_md)
4438 df_ref def;
4440 FOR_EACH_INSN_DEF (def, insn)
4442 unsigned int dregno = DF_REF_REGNO (def);
4443 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4444 || (dregno >= FIRST_PSEUDO_REGISTER))
4446 if (DF_REF_FLAGS (def)
4447 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4448 bitmap_set_bit (local_md, DF_REF_ID (def));
4449 else
4450 bitmap_clear_bit (local_md, DF_REF_ID (def));
4455 static void
4456 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4457 df_ref def,
4458 int top_flag)
4460 bitmap_clear (&seen_in_insn);
4462 for (; def; def = DF_REF_NEXT_LOC (def))
4464 unsigned int dregno = DF_REF_REGNO (def);
4465 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4466 || (dregno >= FIRST_PSEUDO_REGISTER))
4467 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4469 if (!bitmap_bit_p (&seen_in_insn, dregno))
4471 if (DF_REF_FLAGS (def)
4472 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4474 bitmap_set_bit (&bb_info->gen, dregno);
4475 bitmap_clear_bit (&bb_info->kill, dregno);
4477 else
4479 /* When we find a clobber and a regular def,
4480 make sure the regular def wins. */
4481 bitmap_set_bit (&seen_in_insn, dregno);
4482 bitmap_set_bit (&bb_info->kill, dregno);
4483 bitmap_clear_bit (&bb_info->gen, dregno);
4491 /* Compute local multiple def info for basic block BB. */
4493 static void
4494 df_md_bb_local_compute (unsigned int bb_index)
4496 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4497 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4498 rtx_insn *insn;
4500 /* Artificials are only hard regs. */
4501 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4502 df_md_bb_local_compute_process_def (bb_info,
4503 df_get_artificial_defs (bb_index),
4504 DF_REF_AT_TOP);
4506 FOR_BB_INSNS (bb, insn)
4508 unsigned int uid = INSN_UID (insn);
4509 if (!INSN_P (insn))
4510 continue;
4512 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4515 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4516 df_md_bb_local_compute_process_def (bb_info,
4517 df_get_artificial_defs (bb_index),
4521 /* Compute local reaching def info for each basic block within BLOCKS. */
4523 static void
4524 df_md_local_compute (bitmap all_blocks)
4526 unsigned int bb_index, df_bb_index;
4527 bitmap_iterator bi1, bi2;
4528 basic_block bb;
4529 bitmap_head *frontiers;
4531 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4533 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4535 df_md_bb_local_compute (bb_index);
4538 bitmap_clear (&seen_in_insn);
4540 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4541 FOR_ALL_BB_FN (bb, cfun)
4542 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4544 compute_dominance_frontiers (frontiers);
4546 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4547 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4549 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4550 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4552 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4553 if (bitmap_bit_p (all_blocks, df_bb_index))
4554 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4555 df_get_live_in (bb));
4559 FOR_ALL_BB_FN (bb, cfun)
4560 bitmap_clear (&frontiers[bb->index]);
4561 free (frontiers);
4565 /* Reset the global solution for recalculation. */
4567 static void
4568 df_md_reset (bitmap all_blocks)
4570 unsigned int bb_index;
4571 bitmap_iterator bi;
4573 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4575 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4576 gcc_assert (bb_info);
4577 bitmap_clear (&bb_info->in);
4578 bitmap_clear (&bb_info->out);
4582 static bool
4583 df_md_transfer_function (int bb_index)
4585 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4586 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4587 bitmap in = &bb_info->in;
4588 bitmap out = &bb_info->out;
4589 bitmap gen = &bb_info->gen;
4590 bitmap kill = &bb_info->kill;
4592 /* We need to use a scratch set here so that the value returned from this
4593 function invocation properly reflects whether the sets changed in a
4594 significant way; i.e. not just because the live set was anded in. */
4595 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4597 /* Multiple definitions of a register are not relevant if it is not
4598 live. Thus we trim the result to the places where it is live. */
4599 bitmap_and_into (in, df_get_live_in (bb));
4601 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4604 /* Initialize the solution bit vectors for problem. */
4606 static void
4607 df_md_init (bitmap all_blocks)
4609 unsigned int bb_index;
4610 bitmap_iterator bi;
4612 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4614 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4616 bitmap_copy (&bb_info->in, &bb_info->init);
4617 df_md_transfer_function (bb_index);
4621 static void
4622 df_md_confluence_0 (basic_block bb)
4624 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4625 bitmap_copy (&bb_info->in, &bb_info->init);
4628 /* In of target gets or of out of source. */
4630 static bool
4631 df_md_confluence_n (edge e)
4633 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4634 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4636 if (e->flags & EDGE_FAKE)
4637 return false;
4639 if (e->flags & EDGE_EH)
4640 return bitmap_ior_and_compl_into (op1, op2,
4641 regs_invalidated_by_call_regset);
4642 else
4643 return bitmap_ior_into (op1, op2);
4646 /* Free all storage associated with the problem. */
4648 static void
4649 df_md_free (void)
4651 struct df_md_problem_data *problem_data
4652 = (struct df_md_problem_data *) df_md->problem_data;
4654 bitmap_obstack_release (&problem_data->md_bitmaps);
4655 free (problem_data);
4656 df_md->problem_data = NULL;
4658 df_md->block_info_size = 0;
4659 free (df_md->block_info);
4660 df_md->block_info = NULL;
4661 free (df_md);
4665 /* Debugging info at top of bb. */
4667 static void
4668 df_md_top_dump (basic_block bb, FILE *file)
4670 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4671 if (!bb_info)
4672 return;
4674 fprintf (file, ";; md in \t");
4675 df_print_regset (file, &bb_info->in);
4676 fprintf (file, ";; md init \t");
4677 df_print_regset (file, &bb_info->init);
4678 fprintf (file, ";; md gen \t");
4679 df_print_regset (file, &bb_info->gen);
4680 fprintf (file, ";; md kill \t");
4681 df_print_regset (file, &bb_info->kill);
4684 /* Debugging info at bottom of bb. */
4686 static void
4687 df_md_bottom_dump (basic_block bb, FILE *file)
4689 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4690 if (!bb_info)
4691 return;
4693 fprintf (file, ";; md out \t");
4694 df_print_regset (file, &bb_info->out);
4697 static const struct df_problem problem_MD =
4699 DF_MD, /* Problem id. */
4700 DF_FORWARD, /* Direction. */
4701 df_md_alloc, /* Allocate the problem specific data. */
4702 df_md_reset, /* Reset global information. */
4703 df_md_free_bb_info, /* Free basic block info. */
4704 df_md_local_compute, /* Local compute function. */
4705 df_md_init, /* Init the solution specific data. */
4706 df_worklist_dataflow, /* Worklist solver. */
4707 df_md_confluence_0, /* Confluence operator 0. */
4708 df_md_confluence_n, /* Confluence operator n. */
4709 df_md_transfer_function, /* Transfer function. */
4710 NULL, /* Finalize function. */
4711 df_md_free, /* Free all of the problem information. */
4712 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4713 NULL, /* Debugging. */
4714 df_md_top_dump, /* Debugging start block. */
4715 df_md_bottom_dump, /* Debugging end block. */
4716 NULL, /* Debugging start insn. */
4717 NULL, /* Debugging end insn. */
4718 NULL, /* Incremental solution verify start. */
4719 NULL, /* Incremental solution verify end. */
4720 NULL, /* Dependent problem. */
4721 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */
4722 TV_DF_MD, /* Timing variable. */
4723 false /* Reset blocks on dropping out of blocks_to_analyze. */
4726 /* Create a new MD instance and add it to the existing instance
4727 of DF. */
4729 void
4730 df_md_add_problem (void)
4732 df_add_problem (&problem_MD);