Update gimple.texi class hierarchy diagram
[official-gcc.git] / gcc / df-problems.c
blobbf8800f9affcdaaa49da1dfbe97d5dddac0d0307
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2014 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 "tm.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "insn-config.h"
31 #include "recog.h"
32 #include "function.h"
33 #include "regs.h"
34 #include "alloc-pool.h"
35 #include "flags.h"
36 #include "hard-reg-set.h"
37 #include "basic-block.h"
38 #include "sbitmap.h"
39 #include "bitmap.h"
40 #include "target.h"
41 #include "timevar.h"
42 #include "df.h"
43 #include "except.h"
44 #include "dce.h"
45 #include "valtrack.h"
46 #include "dumpfile.h"
47 #include "rtl-iter.h"
49 /* Note that turning REG_DEAD_DEBUGGING on will cause
50 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
51 addresses in the dumps. */
52 #define REG_DEAD_DEBUGGING 0
54 #define DF_SPARSE_THRESHOLD 32
56 static bitmap_head seen_in_block;
57 static bitmap_head seen_in_insn;
59 /*----------------------------------------------------------------------------
60 Utility functions.
61 ----------------------------------------------------------------------------*/
63 /* Generic versions to get the void* version of the block info. Only
64 used inside the problem instance vectors. */
66 /* Dump a def-use or use-def chain for REF to FILE. */
68 void
69 df_chain_dump (struct df_link *link, FILE *file)
71 fprintf (file, "{ ");
72 for (; link; link = link->next)
74 fprintf (file, "%c%d(bb %d insn %d) ",
75 DF_REF_REG_DEF_P (link->ref)
76 ? 'd'
77 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
78 DF_REF_ID (link->ref),
79 DF_REF_BBNO (link->ref),
80 DF_REF_IS_ARTIFICIAL (link->ref)
81 ? -1 : DF_REF_INSN_UID (link->ref));
83 fprintf (file, "}");
87 /* Print some basic block info as part of df_dump. */
89 void
90 df_print_bb_index (basic_block bb, FILE *file)
92 edge e;
93 edge_iterator ei;
95 fprintf (file, "\n( ");
96 FOR_EACH_EDGE (e, ei, bb->preds)
98 basic_block pred = e->src;
99 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
101 fprintf (file, ")->[%d]->( ", bb->index);
102 FOR_EACH_EDGE (e, ei, bb->succs)
104 basic_block succ = e->dest;
105 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
107 fprintf (file, ")\n");
111 /*----------------------------------------------------------------------------
112 REACHING DEFINITIONS
114 Find the locations in the function where each definition site for a
115 pseudo reaches. In and out bitvectors are built for each basic
116 block. The id field in the ref is used to index into these sets.
117 See df.h for details.
119 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
120 existing uses are included in the global reaching DEFs set, or in other
121 words only DEFs that are still live. This is a kind of pruned version
122 of the traditional reaching definitions problem that is much less
123 complex to compute and produces enough information to compute UD-chains.
124 In this context, live must be interpreted in the DF_LR sense: Uses that
125 are upward exposed but maybe not initialized on all paths through the
126 CFG. For a USE that is not reached by a DEF on all paths, we still want
127 to make those DEFs that do reach the USE visible, and pruning based on
128 DF_LIVE would make that impossible.
129 ----------------------------------------------------------------------------*/
131 /* This problem plays a large number of games for the sake of
132 efficiency.
134 1) The order of the bits in the bitvectors. After the scanning
135 phase, all of the defs are sorted. All of the defs for the reg 0
136 are first, followed by all defs for reg 1 and so on.
138 2) There are two kill sets, one if the number of defs is less or
139 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
140 greater.
142 <= : Data is built directly in the kill set.
144 > : One level of indirection is used to keep from generating long
145 strings of 1 bits in the kill sets. Bitvectors that are indexed
146 by the regnum are used to represent that there is a killing def
147 for the register. The confluence and transfer functions use
148 these along with the bitmap_clear_range call to remove ranges of
149 bits without actually generating a knockout vector.
151 The kill and sparse_kill and the dense_invalidated_by_call and
152 sparse_invalidated_by_call both play this game. */
154 /* Private data used to compute the solution for this problem. These
155 data structures are not accessible outside of this module. */
156 struct df_rd_problem_data
158 /* The set of defs to regs invalidated by call. */
159 bitmap_head sparse_invalidated_by_call;
160 /* The set of defs to regs invalidate by call for rd. */
161 bitmap_head dense_invalidated_by_call;
162 /* An obstack for the bitmaps we need for this problem. */
163 bitmap_obstack rd_bitmaps;
167 /* Free basic block info. */
169 static void
170 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
171 void *vbb_info)
173 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
174 if (bb_info)
176 bitmap_clear (&bb_info->kill);
177 bitmap_clear (&bb_info->sparse_kill);
178 bitmap_clear (&bb_info->gen);
179 bitmap_clear (&bb_info->in);
180 bitmap_clear (&bb_info->out);
185 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
186 not touched unless the block is new. */
188 static void
189 df_rd_alloc (bitmap all_blocks)
191 unsigned int bb_index;
192 bitmap_iterator bi;
193 struct df_rd_problem_data *problem_data;
195 if (df_rd->problem_data)
197 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
198 bitmap_clear (&problem_data->sparse_invalidated_by_call);
199 bitmap_clear (&problem_data->dense_invalidated_by_call);
201 else
203 problem_data = XNEW (struct df_rd_problem_data);
204 df_rd->problem_data = problem_data;
206 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
207 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
208 &problem_data->rd_bitmaps);
209 bitmap_initialize (&problem_data->dense_invalidated_by_call,
210 &problem_data->rd_bitmaps);
213 df_grow_bb_info (df_rd);
215 /* Because of the clustering of all use sites for the same pseudo,
216 we have to process all of the blocks before doing the analysis. */
218 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
220 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
222 /* When bitmaps are already initialized, just clear them. */
223 if (bb_info->kill.obstack)
225 bitmap_clear (&bb_info->kill);
226 bitmap_clear (&bb_info->sparse_kill);
227 bitmap_clear (&bb_info->gen);
229 else
231 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
232 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
233 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
234 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
235 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
238 df_rd->optional_p = true;
242 /* Add the effect of the top artificial defs of BB to the reaching definitions
243 bitmap LOCAL_RD. */
245 void
246 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
248 int bb_index = bb->index;
249 df_ref def;
250 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
251 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
253 unsigned int dregno = DF_REF_REGNO (def);
254 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
255 bitmap_clear_range (local_rd,
256 DF_DEFS_BEGIN (dregno),
257 DF_DEFS_COUNT (dregno));
258 bitmap_set_bit (local_rd, DF_REF_ID (def));
262 /* Add the effect of the defs of INSN to the reaching definitions bitmap
263 LOCAL_RD. */
265 void
266 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
267 bitmap local_rd)
269 df_ref def;
271 FOR_EACH_INSN_DEF (def, insn)
273 unsigned int dregno = DF_REF_REGNO (def);
274 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
275 || (dregno >= FIRST_PSEUDO_REGISTER))
277 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
278 bitmap_clear_range (local_rd,
279 DF_DEFS_BEGIN (dregno),
280 DF_DEFS_COUNT (dregno));
281 if (!(DF_REF_FLAGS (def)
282 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
283 bitmap_set_bit (local_rd, DF_REF_ID (def));
288 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
289 more complicated than just simulating, because we must produce the
290 gen and kill sets and hence deal with the two possible representations
291 of kill sets. */
293 static void
294 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
295 df_ref def,
296 int top_flag)
298 for (; def; def = DF_REF_NEXT_LOC (def))
300 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
302 unsigned int regno = DF_REF_REGNO (def);
303 unsigned int begin = DF_DEFS_BEGIN (regno);
304 unsigned int n_defs = DF_DEFS_COUNT (regno);
306 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
307 || (regno >= FIRST_PSEUDO_REGISTER))
309 /* Only the last def(s) for a regno in the block has any
310 effect. */
311 if (!bitmap_bit_p (&seen_in_block, regno))
313 /* The first def for regno in insn gets to knock out the
314 defs from other instructions. */
315 if ((!bitmap_bit_p (&seen_in_insn, regno))
316 /* If the def is to only part of the reg, it does
317 not kill the other defs that reach here. */
318 && (!(DF_REF_FLAGS (def) &
319 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
321 if (n_defs > DF_SPARSE_THRESHOLD)
323 bitmap_set_bit (&bb_info->sparse_kill, regno);
324 bitmap_clear_range (&bb_info->gen, begin, n_defs);
326 else
328 bitmap_set_range (&bb_info->kill, begin, n_defs);
329 bitmap_clear_range (&bb_info->gen, begin, n_defs);
333 bitmap_set_bit (&seen_in_insn, regno);
334 /* All defs for regno in the instruction may be put into
335 the gen set. */
336 if (!(DF_REF_FLAGS (def)
337 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
338 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
345 /* Compute local reaching def info for basic block BB. */
347 static void
348 df_rd_bb_local_compute (unsigned int bb_index)
350 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
351 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
352 rtx_insn *insn;
354 bitmap_clear (&seen_in_block);
355 bitmap_clear (&seen_in_insn);
357 /* Artificials are only hard regs. */
358 if (!(df->changeable_flags & DF_NO_HARD_REGS))
359 df_rd_bb_local_compute_process_def (bb_info,
360 df_get_artificial_defs (bb_index),
363 FOR_BB_INSNS_REVERSE (bb, insn)
365 unsigned int uid = INSN_UID (insn);
367 if (!INSN_P (insn))
368 continue;
370 df_rd_bb_local_compute_process_def (bb_info,
371 DF_INSN_UID_DEFS (uid), 0);
373 /* This complex dance with the two bitmaps is required because
374 instructions can assign twice to the same pseudo. This
375 generally happens with calls that will have one def for the
376 result and another def for the clobber. If only one vector
377 is used and the clobber goes first, the result will be
378 lost. */
379 bitmap_ior_into (&seen_in_block, &seen_in_insn);
380 bitmap_clear (&seen_in_insn);
383 /* Process the artificial defs at the top of the block last since we
384 are going backwards through the block and these are logically at
385 the start. */
386 if (!(df->changeable_flags & DF_NO_HARD_REGS))
387 df_rd_bb_local_compute_process_def (bb_info,
388 df_get_artificial_defs (bb_index),
389 DF_REF_AT_TOP);
393 /* Compute local reaching def info for each basic block within BLOCKS. */
395 static void
396 df_rd_local_compute (bitmap all_blocks)
398 unsigned int bb_index;
399 bitmap_iterator bi;
400 unsigned int regno;
401 struct df_rd_problem_data *problem_data
402 = (struct df_rd_problem_data *) df_rd->problem_data;
403 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
404 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
406 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
407 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
409 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
411 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
413 df_rd_bb_local_compute (bb_index);
416 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
417 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
419 if (! HARD_REGISTER_NUM_P (regno)
420 || !(df->changeable_flags & DF_NO_HARD_REGS))
422 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
423 bitmap_set_bit (sparse_invalidated, regno);
424 else
425 bitmap_set_range (dense_invalidated,
426 DF_DEFS_BEGIN (regno),
427 DF_DEFS_COUNT (regno));
431 bitmap_clear (&seen_in_block);
432 bitmap_clear (&seen_in_insn);
436 /* Initialize the solution bit vectors for problem. */
438 static void
439 df_rd_init_solution (bitmap all_blocks)
441 unsigned int bb_index;
442 bitmap_iterator bi;
444 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
446 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
448 bitmap_copy (&bb_info->out, &bb_info->gen);
449 bitmap_clear (&bb_info->in);
453 /* In of target gets or of out of source. */
455 static bool
456 df_rd_confluence_n (edge e)
458 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
459 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
460 bool changed = false;
462 if (e->flags & EDGE_FAKE)
463 return false;
465 if (e->flags & EDGE_EH)
467 struct df_rd_problem_data *problem_data
468 = (struct df_rd_problem_data *) df_rd->problem_data;
469 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
470 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
471 bitmap_iterator bi;
472 unsigned int regno;
473 bitmap_head tmp;
475 bitmap_initialize (&tmp, &df_bitmap_obstack);
476 bitmap_and_compl (&tmp, op2, dense_invalidated);
478 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
480 bitmap_clear_range (&tmp,
481 DF_DEFS_BEGIN (regno),
482 DF_DEFS_COUNT (regno));
484 changed |= bitmap_ior_into (op1, &tmp);
485 bitmap_clear (&tmp);
486 return changed;
488 else
489 return bitmap_ior_into (op1, op2);
493 /* Transfer function. */
495 static bool
496 df_rd_transfer_function (int bb_index)
498 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
499 unsigned int regno;
500 bitmap_iterator bi;
501 bitmap in = &bb_info->in;
502 bitmap out = &bb_info->out;
503 bitmap gen = &bb_info->gen;
504 bitmap kill = &bb_info->kill;
505 bitmap sparse_kill = &bb_info->sparse_kill;
506 bool changed = false;
508 if (bitmap_empty_p (sparse_kill))
509 changed = bitmap_ior_and_compl (out, gen, in, kill);
510 else
512 struct df_rd_problem_data *problem_data;
513 bitmap_head tmp;
515 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
516 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
517 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
518 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
520 bitmap_and_compl (&tmp, in, kill);
521 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
523 bitmap_clear_range (&tmp,
524 DF_DEFS_BEGIN (regno),
525 DF_DEFS_COUNT (regno));
527 bitmap_ior_into (&tmp, gen);
528 changed = !bitmap_equal_p (&tmp, out);
529 if (changed)
531 bitmap_clear (out);
532 bb_info->out = tmp;
534 else
535 bitmap_clear (&tmp);
538 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
540 /* Create a mask of DEFs for all registers live at the end of this
541 basic block, and mask out DEFs of registers that are not live.
542 Computing the mask looks costly, but the benefit of the pruning
543 outweighs the cost. */
544 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
545 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
546 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
547 unsigned int regno;
548 bitmap_iterator bi;
550 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
551 bitmap_set_range (live_defs,
552 DF_DEFS_BEGIN (regno),
553 DF_DEFS_COUNT (regno));
554 changed |= bitmap_and_into (&bb_info->out, live_defs);
555 BITMAP_FREE (live_defs);
558 return changed;
561 /* Free all storage associated with the problem. */
563 static void
564 df_rd_free (void)
566 struct df_rd_problem_data *problem_data
567 = (struct df_rd_problem_data *) df_rd->problem_data;
569 if (problem_data)
571 bitmap_obstack_release (&problem_data->rd_bitmaps);
573 df_rd->block_info_size = 0;
574 free (df_rd->block_info);
575 df_rd->block_info = NULL;
576 free (df_rd->problem_data);
578 free (df_rd);
582 /* Debugging info. */
584 static void
585 df_rd_start_dump (FILE *file)
587 struct df_rd_problem_data *problem_data
588 = (struct df_rd_problem_data *) df_rd->problem_data;
589 unsigned int m = DF_REG_SIZE (df);
590 unsigned int regno;
592 if (!df_rd->block_info)
593 return;
595 fprintf (file, ";; Reaching defs:\n");
597 fprintf (file, ";; sparse invalidated \t");
598 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
599 fprintf (file, ";; dense invalidated \t");
600 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
602 fprintf (file, ";; reg->defs[] map:\t");
603 for (regno = 0; regno < m; regno++)
604 if (DF_DEFS_COUNT (regno))
605 fprintf (file, "%d[%d,%d] ", regno,
606 DF_DEFS_BEGIN (regno),
607 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
608 fprintf (file, "\n");
612 static void
613 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
615 bitmap_head tmp;
616 unsigned int regno;
617 unsigned int m = DF_REG_SIZE (df);
618 bool first_reg = true;
620 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
622 bitmap_initialize (&tmp, &df_bitmap_obstack);
623 for (regno = 0; regno < m; regno++)
625 if (HARD_REGISTER_NUM_P (regno)
626 && (df->changeable_flags & DF_NO_HARD_REGS))
627 continue;
628 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
629 bitmap_and_into (&tmp, defs_set);
630 if (! bitmap_empty_p (&tmp))
632 bitmap_iterator bi;
633 unsigned int ix;
634 bool first_def = true;
636 if (! first_reg)
637 fprintf (file, ",");
638 first_reg = false;
640 fprintf (file, "%u[", regno);
641 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
643 fprintf (file, "%s%u", first_def ? "" : ",", ix);
644 first_def = false;
646 fprintf (file, "]");
648 bitmap_clear (&tmp);
651 fprintf (file, "\n");
652 bitmap_clear (&tmp);
655 /* Debugging info at top of bb. */
657 static void
658 df_rd_top_dump (basic_block bb, FILE *file)
660 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
661 if (!bb_info)
662 return;
664 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
665 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
666 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
670 /* Debugging info at bottom of bb. */
672 static void
673 df_rd_bottom_dump (basic_block bb, FILE *file)
675 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
676 if (!bb_info)
677 return;
679 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
682 /* All of the information associated with every instance of the problem. */
684 static struct df_problem problem_RD =
686 DF_RD, /* Problem id. */
687 DF_FORWARD, /* Direction. */
688 df_rd_alloc, /* Allocate the problem specific data. */
689 NULL, /* Reset global information. */
690 df_rd_free_bb_info, /* Free basic block info. */
691 df_rd_local_compute, /* Local compute function. */
692 df_rd_init_solution, /* Init the solution specific data. */
693 df_worklist_dataflow, /* Worklist solver. */
694 NULL, /* Confluence operator 0. */
695 df_rd_confluence_n, /* Confluence operator n. */
696 df_rd_transfer_function, /* Transfer function. */
697 NULL, /* Finalize function. */
698 df_rd_free, /* Free all of the problem information. */
699 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
700 df_rd_start_dump, /* Debugging. */
701 df_rd_top_dump, /* Debugging start block. */
702 df_rd_bottom_dump, /* Debugging end block. */
703 NULL, /* Debugging start insn. */
704 NULL, /* Debugging end insn. */
705 NULL, /* Incremental solution verify start. */
706 NULL, /* Incremental solution verify end. */
707 NULL, /* Dependent problem. */
708 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */
709 TV_DF_RD, /* Timing variable. */
710 true /* Reset blocks on dropping out of blocks_to_analyze. */
715 /* Create a new RD instance and add it to the existing instance
716 of DF. */
718 void
719 df_rd_add_problem (void)
721 df_add_problem (&problem_RD);
726 /*----------------------------------------------------------------------------
727 LIVE REGISTERS
729 Find the locations in the function where any use of a pseudo can
730 reach in the backwards direction. In and out bitvectors are built
731 for each basic block. The regno is used to index into these sets.
732 See df.h for details.
733 ----------------------------------------------------------------------------*/
735 /* Private data used to verify the solution for this problem. */
736 struct df_lr_problem_data
738 bitmap_head *in;
739 bitmap_head *out;
740 /* An obstack for the bitmaps we need for this problem. */
741 bitmap_obstack lr_bitmaps;
744 /* Free basic block info. */
746 static void
747 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
748 void *vbb_info)
750 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
751 if (bb_info)
753 bitmap_clear (&bb_info->use);
754 bitmap_clear (&bb_info->def);
755 bitmap_clear (&bb_info->in);
756 bitmap_clear (&bb_info->out);
761 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
762 not touched unless the block is new. */
764 static void
765 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
767 unsigned int bb_index;
768 bitmap_iterator bi;
769 struct df_lr_problem_data *problem_data;
771 df_grow_bb_info (df_lr);
772 if (df_lr->problem_data)
773 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
774 else
776 problem_data = XNEW (struct df_lr_problem_data);
777 df_lr->problem_data = problem_data;
779 problem_data->out = NULL;
780 problem_data->in = NULL;
781 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
784 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
786 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
788 /* When bitmaps are already initialized, just clear them. */
789 if (bb_info->use.obstack)
791 bitmap_clear (&bb_info->def);
792 bitmap_clear (&bb_info->use);
794 else
796 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
797 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
798 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
799 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
803 df_lr->optional_p = false;
807 /* Reset the global solution for recalculation. */
809 static void
810 df_lr_reset (bitmap all_blocks)
812 unsigned int bb_index;
813 bitmap_iterator bi;
815 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
817 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
818 gcc_assert (bb_info);
819 bitmap_clear (&bb_info->in);
820 bitmap_clear (&bb_info->out);
825 /* Compute local live register info for basic block BB. */
827 static void
828 df_lr_bb_local_compute (unsigned int bb_index)
830 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
831 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
832 rtx_insn *insn;
833 df_ref def, use;
835 /* Process the registers set in an exception handler. */
836 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
837 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
839 unsigned int dregno = DF_REF_REGNO (def);
840 bitmap_set_bit (&bb_info->def, dregno);
841 bitmap_clear_bit (&bb_info->use, dregno);
844 /* Process the hardware registers that are always live. */
845 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
846 /* Add use to set of uses in this BB. */
847 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
848 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
850 FOR_BB_INSNS_REVERSE (bb, insn)
852 if (!NONDEBUG_INSN_P (insn))
853 continue;
855 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
856 FOR_EACH_INSN_INFO_DEF (def, insn_info)
857 /* If the def is to only part of the reg, it does
858 not kill the other defs that reach here. */
859 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
861 unsigned int dregno = DF_REF_REGNO (def);
862 bitmap_set_bit (&bb_info->def, dregno);
863 bitmap_clear_bit (&bb_info->use, dregno);
866 FOR_EACH_INSN_INFO_USE (use, insn_info)
867 /* Add use to set of uses in this BB. */
868 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
871 /* Process the registers set in an exception handler or the hard
872 frame pointer if this block is the target of a non local
873 goto. */
874 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
875 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
877 unsigned int dregno = DF_REF_REGNO (def);
878 bitmap_set_bit (&bb_info->def, dregno);
879 bitmap_clear_bit (&bb_info->use, dregno);
882 #ifdef EH_USES
883 /* Process the uses that are live into an exception handler. */
884 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
885 /* Add use to set of uses in this BB. */
886 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
887 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
888 #endif
890 /* If the df_live problem is not defined, such as at -O0 and -O1, we
891 still need to keep the luids up to date. This is normally done
892 in the df_live problem since this problem has a forwards
893 scan. */
894 if (!df_live)
895 df_recompute_luids (bb);
899 /* Compute local live register info for each basic block within BLOCKS. */
901 static void
902 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
904 unsigned int bb_index, i;
905 bitmap_iterator bi;
907 bitmap_clear (&df->hardware_regs_used);
909 /* The all-important stack pointer must always be live. */
910 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
912 /* Global regs are always live, too. */
913 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
914 if (global_regs[i])
915 bitmap_set_bit (&df->hardware_regs_used, i);
917 /* Before reload, there are a few registers that must be forced
918 live everywhere -- which might not already be the case for
919 blocks within infinite loops. */
920 if (!reload_completed)
922 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
923 /* Any reference to any pseudo before reload is a potential
924 reference of the frame pointer. */
925 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
927 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
928 /* Pseudos with argument area equivalences may require
929 reloading via the argument pointer. */
930 if (fixed_regs[ARG_POINTER_REGNUM])
931 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
932 #endif
934 /* Any constant, or pseudo with constant equivalences, may
935 require reloading from memory using the pic register. */
936 if (pic_offset_table_regnum != INVALID_REGNUM
937 && fixed_regs[pic_offset_table_regnum])
938 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
941 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
943 if (bb_index == EXIT_BLOCK)
945 /* The exit block is special for this problem and its bits are
946 computed from thin air. */
947 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
948 bitmap_copy (&bb_info->use, df->exit_block_uses);
950 else
951 df_lr_bb_local_compute (bb_index);
954 bitmap_clear (df_lr->out_of_date_transfer_functions);
958 /* Initialize the solution vectors. */
960 static void
961 df_lr_init (bitmap all_blocks)
963 unsigned int bb_index;
964 bitmap_iterator bi;
966 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
968 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
969 bitmap_copy (&bb_info->in, &bb_info->use);
970 bitmap_clear (&bb_info->out);
975 /* Confluence function that processes infinite loops. This might be a
976 noreturn function that throws. And even if it isn't, getting the
977 unwind info right helps debugging. */
978 static void
979 df_lr_confluence_0 (basic_block bb)
981 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
982 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
983 bitmap_copy (op1, &df->hardware_regs_used);
987 /* Confluence function that ignores fake edges. */
989 static bool
990 df_lr_confluence_n (edge e)
992 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
993 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
994 bool changed = false;
996 /* Call-clobbered registers die across exception and call edges. */
997 /* ??? Abnormal call edges ignored for the moment, as this gets
998 confused by sibling call edges, which crashes reg-stack. */
999 if (e->flags & EDGE_EH)
1000 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
1001 else
1002 changed = bitmap_ior_into (op1, op2);
1004 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
1005 return changed;
1009 /* Transfer function. */
1011 static bool
1012 df_lr_transfer_function (int bb_index)
1014 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1015 bitmap in = &bb_info->in;
1016 bitmap out = &bb_info->out;
1017 bitmap use = &bb_info->use;
1018 bitmap def = &bb_info->def;
1020 return bitmap_ior_and_compl (in, use, out, def);
1024 /* Run the fast dce as a side effect of building LR. */
1026 static void
1027 df_lr_finalize (bitmap all_blocks)
1029 df_lr->solutions_dirty = false;
1030 if (df->changeable_flags & DF_LR_RUN_DCE)
1032 run_fast_df_dce ();
1034 /* If dce deletes some instructions, we need to recompute the lr
1035 solution before proceeding further. The problem is that fast
1036 dce is a pessimestic dataflow algorithm. In the case where
1037 it deletes a statement S inside of a loop, the uses inside of
1038 S may not be deleted from the dataflow solution because they
1039 were carried around the loop. While it is conservatively
1040 correct to leave these extra bits, the standards of df
1041 require that we maintain the best possible (least fixed
1042 point) solution. The only way to do that is to redo the
1043 iteration from the beginning. See PR35805 for an
1044 example. */
1045 if (df_lr->solutions_dirty)
1047 df_clear_flags (DF_LR_RUN_DCE);
1048 df_lr_alloc (all_blocks);
1049 df_lr_local_compute (all_blocks);
1050 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1051 df_lr_finalize (all_blocks);
1052 df_set_flags (DF_LR_RUN_DCE);
1058 /* Free all storage associated with the problem. */
1060 static void
1061 df_lr_free (void)
1063 struct df_lr_problem_data *problem_data
1064 = (struct df_lr_problem_data *) df_lr->problem_data;
1065 if (df_lr->block_info)
1068 df_lr->block_info_size = 0;
1069 free (df_lr->block_info);
1070 df_lr->block_info = NULL;
1071 bitmap_obstack_release (&problem_data->lr_bitmaps);
1072 free (df_lr->problem_data);
1073 df_lr->problem_data = NULL;
1076 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1077 free (df_lr);
1081 /* Debugging info at top of bb. */
1083 static void
1084 df_lr_top_dump (basic_block bb, FILE *file)
1086 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1087 struct df_lr_problem_data *problem_data;
1088 if (!bb_info)
1089 return;
1091 fprintf (file, ";; lr in \t");
1092 df_print_regset (file, &bb_info->in);
1093 if (df_lr->problem_data)
1095 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1096 if (problem_data->in)
1098 fprintf (file, ";; old in \t");
1099 df_print_regset (file, &problem_data->in[bb->index]);
1102 fprintf (file, ";; lr use \t");
1103 df_print_regset (file, &bb_info->use);
1104 fprintf (file, ";; lr def \t");
1105 df_print_regset (file, &bb_info->def);
1109 /* Debugging info at bottom of bb. */
1111 static void
1112 df_lr_bottom_dump (basic_block bb, FILE *file)
1114 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1115 struct df_lr_problem_data *problem_data;
1116 if (!bb_info)
1117 return;
1119 fprintf (file, ";; lr out \t");
1120 df_print_regset (file, &bb_info->out);
1121 if (df_lr->problem_data)
1123 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1124 if (problem_data->out)
1126 fprintf (file, ";; old out \t");
1127 df_print_regset (file, &problem_data->out[bb->index]);
1133 /* Build the datastructure to verify that the solution to the dataflow
1134 equations is not dirty. */
1136 static void
1137 df_lr_verify_solution_start (void)
1139 basic_block bb;
1140 struct df_lr_problem_data *problem_data;
1141 if (df_lr->solutions_dirty)
1142 return;
1144 /* Set it true so that the solution is recomputed. */
1145 df_lr->solutions_dirty = true;
1147 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1148 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1149 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1151 FOR_ALL_BB_FN (bb, cfun)
1153 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1154 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1155 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1156 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1161 /* Compare the saved datastructure and the new solution to the dataflow
1162 equations. */
1164 static void
1165 df_lr_verify_solution_end (void)
1167 struct df_lr_problem_data *problem_data;
1168 basic_block bb;
1170 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1172 if (!problem_data->out)
1173 return;
1175 if (df_lr->solutions_dirty)
1176 /* Do not check if the solution is still dirty. See the comment
1177 in df_lr_finalize for details. */
1178 df_lr->solutions_dirty = false;
1179 else
1180 FOR_ALL_BB_FN (bb, cfun)
1182 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1183 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1185 /*df_dump (stderr);*/
1186 gcc_unreachable ();
1190 /* Cannot delete them immediately because you may want to dump them
1191 if the comparison fails. */
1192 FOR_ALL_BB_FN (bb, cfun)
1194 bitmap_clear (&problem_data->in[bb->index]);
1195 bitmap_clear (&problem_data->out[bb->index]);
1198 free (problem_data->in);
1199 free (problem_data->out);
1200 problem_data->in = NULL;
1201 problem_data->out = NULL;
1205 /* All of the information associated with every instance of the problem. */
1207 static struct df_problem problem_LR =
1209 DF_LR, /* Problem id. */
1210 DF_BACKWARD, /* Direction. */
1211 df_lr_alloc, /* Allocate the problem specific data. */
1212 df_lr_reset, /* Reset global information. */
1213 df_lr_free_bb_info, /* Free basic block info. */
1214 df_lr_local_compute, /* Local compute function. */
1215 df_lr_init, /* Init the solution specific data. */
1216 df_worklist_dataflow, /* Worklist solver. */
1217 df_lr_confluence_0, /* Confluence operator 0. */
1218 df_lr_confluence_n, /* Confluence operator n. */
1219 df_lr_transfer_function, /* Transfer function. */
1220 df_lr_finalize, /* Finalize function. */
1221 df_lr_free, /* Free all of the problem information. */
1222 NULL, /* Remove this problem from the stack of dataflow problems. */
1223 NULL, /* Debugging. */
1224 df_lr_top_dump, /* Debugging start block. */
1225 df_lr_bottom_dump, /* Debugging end block. */
1226 NULL, /* Debugging start insn. */
1227 NULL, /* Debugging end insn. */
1228 df_lr_verify_solution_start,/* Incremental solution verify start. */
1229 df_lr_verify_solution_end, /* Incremental solution verify end. */
1230 NULL, /* Dependent problem. */
1231 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1232 TV_DF_LR, /* Timing variable. */
1233 false /* Reset blocks on dropping out of blocks_to_analyze. */
1237 /* Create a new DATAFLOW instance and add it to an existing instance
1238 of DF. The returned structure is what is used to get at the
1239 solution. */
1241 void
1242 df_lr_add_problem (void)
1244 df_add_problem (&problem_LR);
1245 /* These will be initialized when df_scan_blocks processes each
1246 block. */
1247 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1251 /* Verify that all of the lr related info is consistent and
1252 correct. */
1254 void
1255 df_lr_verify_transfer_functions (void)
1257 basic_block bb;
1258 bitmap_head saved_def;
1259 bitmap_head saved_use;
1260 bitmap_head all_blocks;
1262 if (!df)
1263 return;
1265 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1266 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1267 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1269 FOR_ALL_BB_FN (bb, cfun)
1271 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1272 bitmap_set_bit (&all_blocks, bb->index);
1274 if (bb_info)
1276 /* Make a copy of the transfer functions and then compute
1277 new ones to see if the transfer functions have
1278 changed. */
1279 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1280 bb->index))
1282 bitmap_copy (&saved_def, &bb_info->def);
1283 bitmap_copy (&saved_use, &bb_info->use);
1284 bitmap_clear (&bb_info->def);
1285 bitmap_clear (&bb_info->use);
1287 df_lr_bb_local_compute (bb->index);
1288 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1289 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1292 else
1294 /* If we do not have basic block info, the block must be in
1295 the list of dirty blocks or else some one has added a
1296 block behind our backs. */
1297 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1298 bb->index));
1300 /* Make sure no one created a block without following
1301 procedures. */
1302 gcc_assert (df_scan_get_bb_info (bb->index));
1305 /* Make sure there are no dirty bits in blocks that have been deleted. */
1306 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1307 &all_blocks));
1309 bitmap_clear (&saved_def);
1310 bitmap_clear (&saved_use);
1311 bitmap_clear (&all_blocks);
1316 /*----------------------------------------------------------------------------
1317 LIVE AND MUST-INITIALIZED REGISTERS.
1319 This problem first computes the IN and OUT bitvectors for the
1320 must-initialized registers problems, which is a forward problem.
1321 It gives the set of registers for which we MUST have an available
1322 definition on any path from the entry block to the entry/exit of
1323 a basic block. Sets generate a definition, while clobbers kill
1324 a definition.
1326 In and out bitvectors are built for each basic block and are indexed by
1327 regnum (see df.h for details). In and out bitvectors in struct
1328 df_live_bb_info actually refers to the must-initialized problem;
1330 Then, the in and out sets for the LIVE problem itself are computed.
1331 These are the logical AND of the IN and OUT sets from the LR problem
1332 and the must-initialized problem.
1333 ----------------------------------------------------------------------------*/
1335 /* Private data used to verify the solution for this problem. */
1336 struct df_live_problem_data
1338 bitmap_head *in;
1339 bitmap_head *out;
1340 /* An obstack for the bitmaps we need for this problem. */
1341 bitmap_obstack live_bitmaps;
1344 /* Scratch var used by transfer functions. This is used to implement
1345 an optimization to reduce the amount of space used to compute the
1346 combined lr and live analysis. */
1347 static bitmap_head df_live_scratch;
1350 /* Free basic block info. */
1352 static void
1353 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1354 void *vbb_info)
1356 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1357 if (bb_info)
1359 bitmap_clear (&bb_info->gen);
1360 bitmap_clear (&bb_info->kill);
1361 bitmap_clear (&bb_info->in);
1362 bitmap_clear (&bb_info->out);
1367 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1368 not touched unless the block is new. */
1370 static void
1371 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1373 unsigned int bb_index;
1374 bitmap_iterator bi;
1375 struct df_live_problem_data *problem_data;
1377 if (df_live->problem_data)
1378 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1379 else
1381 problem_data = XNEW (struct df_live_problem_data);
1382 df_live->problem_data = problem_data;
1384 problem_data->out = NULL;
1385 problem_data->in = NULL;
1386 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1387 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1390 df_grow_bb_info (df_live);
1392 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1394 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1396 /* When bitmaps are already initialized, just clear them. */
1397 if (bb_info->kill.obstack)
1399 bitmap_clear (&bb_info->kill);
1400 bitmap_clear (&bb_info->gen);
1402 else
1404 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1405 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1406 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1407 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1410 df_live->optional_p = (optimize <= 1);
1414 /* Reset the global solution for recalculation. */
1416 static void
1417 df_live_reset (bitmap all_blocks)
1419 unsigned int bb_index;
1420 bitmap_iterator bi;
1422 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1424 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1425 gcc_assert (bb_info);
1426 bitmap_clear (&bb_info->in);
1427 bitmap_clear (&bb_info->out);
1432 /* Compute local uninitialized register info for basic block BB. */
1434 static void
1435 df_live_bb_local_compute (unsigned int bb_index)
1437 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1438 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1439 rtx_insn *insn;
1440 df_ref def;
1441 int luid = 0;
1443 FOR_BB_INSNS (bb, insn)
1445 unsigned int uid = INSN_UID (insn);
1446 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1448 /* Inserting labels does not always trigger the incremental
1449 rescanning. */
1450 if (!insn_info)
1452 gcc_assert (!INSN_P (insn));
1453 insn_info = df_insn_create_insn_record (insn);
1456 DF_INSN_INFO_LUID (insn_info) = luid;
1457 if (!INSN_P (insn))
1458 continue;
1460 luid++;
1461 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1463 unsigned int regno = DF_REF_REGNO (def);
1465 if (DF_REF_FLAGS_IS_SET (def,
1466 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1467 /* All partial or conditional def
1468 seen are included in the gen set. */
1469 bitmap_set_bit (&bb_info->gen, regno);
1470 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1471 /* Only must clobbers for the entire reg destroy the
1472 value. */
1473 bitmap_set_bit (&bb_info->kill, regno);
1474 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1475 bitmap_set_bit (&bb_info->gen, regno);
1479 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1480 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1484 /* Compute local uninitialized register info. */
1486 static void
1487 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1489 unsigned int bb_index;
1490 bitmap_iterator bi;
1492 df_grow_insn_info ();
1494 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1495 0, bb_index, bi)
1497 df_live_bb_local_compute (bb_index);
1500 bitmap_clear (df_live->out_of_date_transfer_functions);
1504 /* Initialize the solution vectors. */
1506 static void
1507 df_live_init (bitmap all_blocks)
1509 unsigned int bb_index;
1510 bitmap_iterator bi;
1512 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1514 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1515 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1517 /* No register may reach a location where it is not used. Thus
1518 we trim the rr result to the places where it is used. */
1519 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1520 bitmap_clear (&bb_info->in);
1524 /* Forward confluence function that ignores fake edges. */
1526 static bool
1527 df_live_confluence_n (edge e)
1529 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1530 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1532 if (e->flags & EDGE_FAKE)
1533 return false;
1535 return bitmap_ior_into (op1, op2);
1539 /* Transfer function for the forwards must-initialized problem. */
1541 static bool
1542 df_live_transfer_function (int bb_index)
1544 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1545 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1546 bitmap in = &bb_info->in;
1547 bitmap out = &bb_info->out;
1548 bitmap gen = &bb_info->gen;
1549 bitmap kill = &bb_info->kill;
1551 /* We need to use a scratch set here so that the value returned from this
1552 function invocation properly reflects whether the sets changed in a
1553 significant way; i.e. not just because the lr set was anded in. */
1554 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1555 /* No register may reach a location where it is not used. Thus
1556 we trim the rr result to the places where it is used. */
1557 bitmap_and_into (in, &bb_lr_info->in);
1559 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1563 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1565 static void
1566 df_live_finalize (bitmap all_blocks)
1569 if (df_live->solutions_dirty)
1571 bitmap_iterator bi;
1572 unsigned int bb_index;
1574 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1576 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1577 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1579 /* No register may reach a location where it is not used. Thus
1580 we trim the rr result to the places where it is used. */
1581 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1582 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1585 df_live->solutions_dirty = false;
1590 /* Free all storage associated with the problem. */
1592 static void
1593 df_live_free (void)
1595 struct df_live_problem_data *problem_data
1596 = (struct df_live_problem_data *) df_live->problem_data;
1597 if (df_live->block_info)
1599 df_live->block_info_size = 0;
1600 free (df_live->block_info);
1601 df_live->block_info = NULL;
1602 bitmap_clear (&df_live_scratch);
1603 bitmap_obstack_release (&problem_data->live_bitmaps);
1604 free (problem_data);
1605 df_live->problem_data = NULL;
1607 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1608 free (df_live);
1612 /* Debugging info at top of bb. */
1614 static void
1615 df_live_top_dump (basic_block bb, FILE *file)
1617 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1618 struct df_live_problem_data *problem_data;
1620 if (!bb_info)
1621 return;
1623 fprintf (file, ";; live in \t");
1624 df_print_regset (file, &bb_info->in);
1625 if (df_live->problem_data)
1627 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1628 if (problem_data->in)
1630 fprintf (file, ";; old in \t");
1631 df_print_regset (file, &problem_data->in[bb->index]);
1634 fprintf (file, ";; live gen \t");
1635 df_print_regset (file, &bb_info->gen);
1636 fprintf (file, ";; live kill\t");
1637 df_print_regset (file, &bb_info->kill);
1641 /* Debugging info at bottom of bb. */
1643 static void
1644 df_live_bottom_dump (basic_block bb, FILE *file)
1646 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1647 struct df_live_problem_data *problem_data;
1649 if (!bb_info)
1650 return;
1652 fprintf (file, ";; live out \t");
1653 df_print_regset (file, &bb_info->out);
1654 if (df_live->problem_data)
1656 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1657 if (problem_data->out)
1659 fprintf (file, ";; old out \t");
1660 df_print_regset (file, &problem_data->out[bb->index]);
1666 /* Build the datastructure to verify that the solution to the dataflow
1667 equations is not dirty. */
1669 static void
1670 df_live_verify_solution_start (void)
1672 basic_block bb;
1673 struct df_live_problem_data *problem_data;
1674 if (df_live->solutions_dirty)
1675 return;
1677 /* Set it true so that the solution is recomputed. */
1678 df_live->solutions_dirty = true;
1680 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1681 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1682 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1684 FOR_ALL_BB_FN (bb, cfun)
1686 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1687 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1688 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1689 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1694 /* Compare the saved datastructure and the new solution to the dataflow
1695 equations. */
1697 static void
1698 df_live_verify_solution_end (void)
1700 struct df_live_problem_data *problem_data;
1701 basic_block bb;
1703 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1704 if (!problem_data->out)
1705 return;
1707 FOR_ALL_BB_FN (bb, cfun)
1709 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1710 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1712 /*df_dump (stderr);*/
1713 gcc_unreachable ();
1717 /* Cannot delete them immediately because you may want to dump them
1718 if the comparison fails. */
1719 FOR_ALL_BB_FN (bb, cfun)
1721 bitmap_clear (&problem_data->in[bb->index]);
1722 bitmap_clear (&problem_data->out[bb->index]);
1725 free (problem_data->in);
1726 free (problem_data->out);
1727 free (problem_data);
1728 df_live->problem_data = NULL;
1732 /* All of the information associated with every instance of the problem. */
1734 static struct df_problem problem_LIVE =
1736 DF_LIVE, /* Problem id. */
1737 DF_FORWARD, /* Direction. */
1738 df_live_alloc, /* Allocate the problem specific data. */
1739 df_live_reset, /* Reset global information. */
1740 df_live_free_bb_info, /* Free basic block info. */
1741 df_live_local_compute, /* Local compute function. */
1742 df_live_init, /* Init the solution specific data. */
1743 df_worklist_dataflow, /* Worklist solver. */
1744 NULL, /* Confluence operator 0. */
1745 df_live_confluence_n, /* Confluence operator n. */
1746 df_live_transfer_function, /* Transfer function. */
1747 df_live_finalize, /* Finalize function. */
1748 df_live_free, /* Free all of the problem information. */
1749 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1750 NULL, /* Debugging. */
1751 df_live_top_dump, /* Debugging start block. */
1752 df_live_bottom_dump, /* Debugging end block. */
1753 NULL, /* Debugging start insn. */
1754 NULL, /* Debugging end insn. */
1755 df_live_verify_solution_start,/* Incremental solution verify start. */
1756 df_live_verify_solution_end, /* Incremental solution verify end. */
1757 &problem_LR, /* Dependent problem. */
1758 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1759 TV_DF_LIVE, /* Timing variable. */
1760 false /* Reset blocks on dropping out of blocks_to_analyze. */
1764 /* Create a new DATAFLOW instance and add it to an existing instance
1765 of DF. The returned structure is what is used to get at the
1766 solution. */
1768 void
1769 df_live_add_problem (void)
1771 df_add_problem (&problem_LIVE);
1772 /* These will be initialized when df_scan_blocks processes each
1773 block. */
1774 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1778 /* Set all of the blocks as dirty. This needs to be done if this
1779 problem is added after all of the insns have been scanned. */
1781 void
1782 df_live_set_all_dirty (void)
1784 basic_block bb;
1785 FOR_ALL_BB_FN (bb, cfun)
1786 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1787 bb->index);
1791 /* Verify that all of the lr related info is consistent and
1792 correct. */
1794 void
1795 df_live_verify_transfer_functions (void)
1797 basic_block bb;
1798 bitmap_head saved_gen;
1799 bitmap_head saved_kill;
1800 bitmap_head all_blocks;
1802 if (!df)
1803 return;
1805 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1806 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1807 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1809 df_grow_insn_info ();
1811 FOR_ALL_BB_FN (bb, cfun)
1813 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1814 bitmap_set_bit (&all_blocks, bb->index);
1816 if (bb_info)
1818 /* Make a copy of the transfer functions and then compute
1819 new ones to see if the transfer functions have
1820 changed. */
1821 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1822 bb->index))
1824 bitmap_copy (&saved_gen, &bb_info->gen);
1825 bitmap_copy (&saved_kill, &bb_info->kill);
1826 bitmap_clear (&bb_info->gen);
1827 bitmap_clear (&bb_info->kill);
1829 df_live_bb_local_compute (bb->index);
1830 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1831 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1834 else
1836 /* If we do not have basic block info, the block must be in
1837 the list of dirty blocks or else some one has added a
1838 block behind our backs. */
1839 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1840 bb->index));
1842 /* Make sure no one created a block without following
1843 procedures. */
1844 gcc_assert (df_scan_get_bb_info (bb->index));
1847 /* Make sure there are no dirty bits in blocks that have been deleted. */
1848 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1849 &all_blocks));
1850 bitmap_clear (&saved_gen);
1851 bitmap_clear (&saved_kill);
1852 bitmap_clear (&all_blocks);
1855 /*----------------------------------------------------------------------------
1856 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1858 Link either the defs to the uses and / or the uses to the defs.
1860 These problems are set up like the other dataflow problems so that
1861 they nicely fit into the framework. They are much simpler and only
1862 involve a single traversal of instructions and an examination of
1863 the reaching defs information (the dependent problem).
1864 ----------------------------------------------------------------------------*/
1866 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1868 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1870 struct df_link *
1871 df_chain_create (df_ref src, df_ref dst)
1873 struct df_link *head = DF_REF_CHAIN (src);
1874 struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1876 DF_REF_CHAIN (src) = link;
1877 link->next = head;
1878 link->ref = dst;
1879 return link;
1883 /* Delete any du or ud chains that start at REF and point to
1884 TARGET. */
1885 static void
1886 df_chain_unlink_1 (df_ref ref, df_ref target)
1888 struct df_link *chain = DF_REF_CHAIN (ref);
1889 struct df_link *prev = NULL;
1891 while (chain)
1893 if (chain->ref == target)
1895 if (prev)
1896 prev->next = chain->next;
1897 else
1898 DF_REF_CHAIN (ref) = chain->next;
1899 pool_free (df_chain->block_pool, chain);
1900 return;
1902 prev = chain;
1903 chain = chain->next;
1908 /* Delete a du or ud chain that leave or point to REF. */
1910 void
1911 df_chain_unlink (df_ref ref)
1913 struct df_link *chain = DF_REF_CHAIN (ref);
1914 while (chain)
1916 struct df_link *next = chain->next;
1917 /* Delete the other side if it exists. */
1918 df_chain_unlink_1 (chain->ref, ref);
1919 pool_free (df_chain->block_pool, chain);
1920 chain = next;
1922 DF_REF_CHAIN (ref) = NULL;
1926 /* Copy the du or ud chain starting at FROM_REF and attach it to
1927 TO_REF. */
1929 void
1930 df_chain_copy (df_ref to_ref,
1931 struct df_link *from_ref)
1933 while (from_ref)
1935 df_chain_create (to_ref, from_ref->ref);
1936 from_ref = from_ref->next;
1941 /* Remove this problem from the stack of dataflow problems. */
1943 static void
1944 df_chain_remove_problem (void)
1946 bitmap_iterator bi;
1947 unsigned int bb_index;
1949 /* Wholesale destruction of the old chains. */
1950 if (df_chain->block_pool)
1951 free_alloc_pool (df_chain->block_pool);
1953 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1955 rtx_insn *insn;
1956 df_ref def, use;
1957 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1959 if (df_chain_problem_p (DF_DU_CHAIN))
1960 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1961 DF_REF_CHAIN (def) = NULL;
1962 if (df_chain_problem_p (DF_UD_CHAIN))
1963 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1964 DF_REF_CHAIN (use) = NULL;
1966 FOR_BB_INSNS (bb, insn)
1967 if (INSN_P (insn))
1969 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1970 if (df_chain_problem_p (DF_DU_CHAIN))
1971 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1972 DF_REF_CHAIN (def) = NULL;
1973 if (df_chain_problem_p (DF_UD_CHAIN))
1975 FOR_EACH_INSN_INFO_USE (use, insn_info)
1976 DF_REF_CHAIN (use) = NULL;
1977 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1978 DF_REF_CHAIN (use) = NULL;
1983 bitmap_clear (df_chain->out_of_date_transfer_functions);
1984 df_chain->block_pool = NULL;
1988 /* Remove the chain problem completely. */
1990 static void
1991 df_chain_fully_remove_problem (void)
1993 df_chain_remove_problem ();
1994 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
1995 free (df_chain);
1999 /* Create def-use or use-def chains. */
2001 static void
2002 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2004 df_chain_remove_problem ();
2005 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2006 sizeof (struct df_link), 50);
2007 df_chain->optional_p = true;
2011 /* Reset all of the chains when the set of basic blocks changes. */
2013 static void
2014 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2016 df_chain_remove_problem ();
2020 /* Create the chains for a list of USEs. */
2022 static void
2023 df_chain_create_bb_process_use (bitmap local_rd,
2024 df_ref use,
2025 int top_flag)
2027 bitmap_iterator bi;
2028 unsigned int def_index;
2030 for (; use; use = DF_REF_NEXT_LOC (use))
2032 unsigned int uregno = DF_REF_REGNO (use);
2033 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2034 || (uregno >= FIRST_PSEUDO_REGISTER))
2036 /* Do not want to go through this for an uninitialized var. */
2037 int count = DF_DEFS_COUNT (uregno);
2038 if (count)
2040 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2042 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2043 unsigned int last_index = first_index + count - 1;
2045 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2047 df_ref def;
2048 if (def_index > last_index)
2049 break;
2051 def = DF_DEFS_GET (def_index);
2052 if (df_chain_problem_p (DF_DU_CHAIN))
2053 df_chain_create (def, use);
2054 if (df_chain_problem_p (DF_UD_CHAIN))
2055 df_chain_create (use, def);
2064 /* Create chains from reaching defs bitmaps for basic block BB. */
2066 static void
2067 df_chain_create_bb (unsigned int bb_index)
2069 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2070 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2071 rtx_insn *insn;
2072 bitmap_head cpy;
2074 bitmap_initialize (&cpy, &bitmap_default_obstack);
2075 bitmap_copy (&cpy, &bb_info->in);
2076 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2078 /* Since we are going forwards, process the artificial uses first
2079 then the artificial defs second. */
2081 #ifdef EH_USES
2082 /* Create the chains for the artificial uses from the EH_USES at the
2083 beginning of the block. */
2085 /* Artificials are only hard regs. */
2086 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2087 df_chain_create_bb_process_use (&cpy,
2088 df_get_artificial_uses (bb->index),
2089 DF_REF_AT_TOP);
2090 #endif
2092 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2094 /* Process the regular instructions next. */
2095 FOR_BB_INSNS (bb, insn)
2096 if (INSN_P (insn))
2098 unsigned int uid = INSN_UID (insn);
2100 /* First scan the uses and link them up with the defs that remain
2101 in the cpy vector. */
2102 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2103 if (df->changeable_flags & DF_EQ_NOTES)
2104 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2106 /* Since we are going forwards, process the defs second. */
2107 df_rd_simulate_one_insn (bb, insn, &cpy);
2110 /* Create the chains for the artificial uses of the hard registers
2111 at the end of the block. */
2112 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2113 df_chain_create_bb_process_use (&cpy,
2114 df_get_artificial_uses (bb->index),
2117 bitmap_clear (&cpy);
2120 /* Create def-use chains from reaching use bitmaps for basic blocks
2121 in BLOCKS. */
2123 static void
2124 df_chain_finalize (bitmap all_blocks)
2126 unsigned int bb_index;
2127 bitmap_iterator bi;
2129 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2131 df_chain_create_bb (bb_index);
2136 /* Free all storage associated with the problem. */
2138 static void
2139 df_chain_free (void)
2141 free_alloc_pool (df_chain->block_pool);
2142 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2143 free (df_chain);
2147 /* Debugging info. */
2149 static void
2150 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2152 /* Artificials are only hard regs. */
2153 if (df->changeable_flags & DF_NO_HARD_REGS)
2154 return;
2155 if (df_chain_problem_p (DF_UD_CHAIN))
2157 df_ref use;
2159 fprintf (file,
2160 ";; UD chains for artificial uses at %s\n",
2161 top ? "top" : "bottom");
2162 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2163 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2164 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2166 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2167 df_chain_dump (DF_REF_CHAIN (use), file);
2168 fprintf (file, "\n");
2171 if (df_chain_problem_p (DF_DU_CHAIN))
2173 df_ref def;
2175 fprintf (file,
2176 ";; DU chains for artificial defs at %s\n",
2177 top ? "top" : "bottom");
2178 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2179 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2180 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2182 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2183 df_chain_dump (DF_REF_CHAIN (def), file);
2184 fprintf (file, "\n");
2189 static void
2190 df_chain_top_dump (basic_block bb, FILE *file)
2192 df_chain_bb_dump (bb, file, /*top=*/true);
2195 static void
2196 df_chain_bottom_dump (basic_block bb, FILE *file)
2198 df_chain_bb_dump (bb, file, /*top=*/false);
2201 static void
2202 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2204 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2206 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2207 df_ref use;
2209 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2210 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2211 FOR_EACH_INSN_INFO_USE (use, insn_info)
2212 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2213 || !(df->changeable_flags & DF_NO_HARD_REGS))
2215 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2216 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2217 fprintf (file, "read/write ");
2218 df_chain_dump (DF_REF_CHAIN (use), file);
2219 fprintf (file, "\n");
2221 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2222 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2223 || !(df->changeable_flags & DF_NO_HARD_REGS))
2225 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2226 df_chain_dump (DF_REF_CHAIN (use), file);
2227 fprintf (file, "\n");
2232 static void
2233 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2235 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2237 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2238 df_ref def;
2239 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2240 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2241 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2242 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2243 || !(df->changeable_flags & DF_NO_HARD_REGS))
2245 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2246 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2247 fprintf (file, "read/write ");
2248 df_chain_dump (DF_REF_CHAIN (def), file);
2249 fprintf (file, "\n");
2251 fprintf (file, "\n");
2255 static struct df_problem problem_CHAIN =
2257 DF_CHAIN, /* Problem id. */
2258 DF_NONE, /* Direction. */
2259 df_chain_alloc, /* Allocate the problem specific data. */
2260 df_chain_reset, /* Reset global information. */
2261 NULL, /* Free basic block info. */
2262 NULL, /* Local compute function. */
2263 NULL, /* Init the solution specific data. */
2264 NULL, /* Iterative solver. */
2265 NULL, /* Confluence operator 0. */
2266 NULL, /* Confluence operator n. */
2267 NULL, /* Transfer function. */
2268 df_chain_finalize, /* Finalize function. */
2269 df_chain_free, /* Free all of the problem information. */
2270 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2271 NULL, /* Debugging. */
2272 df_chain_top_dump, /* Debugging start block. */
2273 df_chain_bottom_dump, /* Debugging end block. */
2274 df_chain_insn_top_dump, /* Debugging start insn. */
2275 df_chain_insn_bottom_dump, /* Debugging end insn. */
2276 NULL, /* Incremental solution verify start. */
2277 NULL, /* Incremental solution verify end. */
2278 &problem_RD, /* Dependent problem. */
2279 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2280 TV_DF_CHAIN, /* Timing variable. */
2281 false /* Reset blocks on dropping out of blocks_to_analyze. */
2285 /* Create a new DATAFLOW instance and add it to an existing instance
2286 of DF. The returned structure is what is used to get at the
2287 solution. */
2289 void
2290 df_chain_add_problem (unsigned int chain_flags)
2292 df_add_problem (&problem_CHAIN);
2293 df_chain->local_flags = chain_flags;
2294 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2297 #undef df_chain_problem_p
2300 /*----------------------------------------------------------------------------
2301 WORD LEVEL LIVE REGISTERS
2303 Find the locations in the function where any use of a pseudo can
2304 reach in the backwards direction. In and out bitvectors are built
2305 for each basic block. We only track pseudo registers that have a
2306 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2307 contain two bits corresponding to each of the subwords.
2309 ----------------------------------------------------------------------------*/
2311 /* Private data used to verify the solution for this problem. */
2312 struct df_word_lr_problem_data
2314 /* An obstack for the bitmaps we need for this problem. */
2315 bitmap_obstack word_lr_bitmaps;
2319 /* Free basic block info. */
2321 static void
2322 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2323 void *vbb_info)
2325 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2326 if (bb_info)
2328 bitmap_clear (&bb_info->use);
2329 bitmap_clear (&bb_info->def);
2330 bitmap_clear (&bb_info->in);
2331 bitmap_clear (&bb_info->out);
2336 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2337 not touched unless the block is new. */
2339 static void
2340 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2342 unsigned int bb_index;
2343 bitmap_iterator bi;
2344 basic_block bb;
2345 struct df_word_lr_problem_data *problem_data
2346 = XNEW (struct df_word_lr_problem_data);
2348 df_word_lr->problem_data = problem_data;
2350 df_grow_bb_info (df_word_lr);
2352 /* Create the mapping from regnos to slots. This does not change
2353 unless the problem is destroyed and recreated. In particular, if
2354 we end up deleting the only insn that used a subreg, we do not
2355 want to redo the mapping because this would invalidate everything
2356 else. */
2358 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2360 FOR_EACH_BB_FN (bb, cfun)
2361 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2363 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2364 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2366 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2368 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2370 /* When bitmaps are already initialized, just clear them. */
2371 if (bb_info->use.obstack)
2373 bitmap_clear (&bb_info->def);
2374 bitmap_clear (&bb_info->use);
2376 else
2378 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2379 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2380 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2381 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2385 df_word_lr->optional_p = true;
2389 /* Reset the global solution for recalculation. */
2391 static void
2392 df_word_lr_reset (bitmap all_blocks)
2394 unsigned int bb_index;
2395 bitmap_iterator bi;
2397 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2399 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2400 gcc_assert (bb_info);
2401 bitmap_clear (&bb_info->in);
2402 bitmap_clear (&bb_info->out);
2406 /* Examine REF, and if it is for a reg we're interested in, set or
2407 clear the bits corresponding to its subwords from the bitmap
2408 according to IS_SET. LIVE is the bitmap we should update. We do
2409 not track hard regs or pseudos of any size other than 2 *
2410 UNITS_PER_WORD.
2411 We return true if we changed the bitmap, or if we encountered a register
2412 we're not tracking. */
2414 bool
2415 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2417 rtx orig_reg = DF_REF_REG (ref);
2418 rtx reg = orig_reg;
2419 enum machine_mode reg_mode;
2420 unsigned regno;
2421 /* Left at -1 for whole accesses. */
2422 int which_subword = -1;
2423 bool changed = false;
2425 if (GET_CODE (reg) == SUBREG)
2426 reg = SUBREG_REG (orig_reg);
2427 regno = REGNO (reg);
2428 reg_mode = GET_MODE (reg);
2429 if (regno < FIRST_PSEUDO_REGISTER
2430 || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
2431 return true;
2433 if (GET_CODE (orig_reg) == SUBREG
2434 && df_read_modify_subreg_p (orig_reg))
2436 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2437 if (subreg_lowpart_p (orig_reg))
2438 which_subword = 0;
2439 else
2440 which_subword = 1;
2442 if (is_set)
2444 if (which_subword != 1)
2445 changed |= bitmap_set_bit (live, regno * 2);
2446 if (which_subword != 0)
2447 changed |= bitmap_set_bit (live, regno * 2 + 1);
2449 else
2451 if (which_subword != 1)
2452 changed |= bitmap_clear_bit (live, regno * 2);
2453 if (which_subword != 0)
2454 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2456 return changed;
2459 /* Compute local live register info for basic block BB. */
2461 static void
2462 df_word_lr_bb_local_compute (unsigned int bb_index)
2464 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2465 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2466 rtx_insn *insn;
2467 df_ref def, use;
2469 /* Ensure that artificial refs don't contain references to pseudos. */
2470 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2471 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2473 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2474 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2476 FOR_BB_INSNS_REVERSE (bb, insn)
2478 if (!NONDEBUG_INSN_P (insn))
2479 continue;
2481 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2482 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2483 /* If the def is to only part of the reg, it does
2484 not kill the other defs that reach here. */
2485 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2487 df_word_lr_mark_ref (def, true, &bb_info->def);
2488 df_word_lr_mark_ref (def, false, &bb_info->use);
2490 FOR_EACH_INSN_INFO_USE (use, insn_info)
2491 df_word_lr_mark_ref (use, true, &bb_info->use);
2496 /* Compute local live register info for each basic block within BLOCKS. */
2498 static void
2499 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2501 unsigned int bb_index;
2502 bitmap_iterator bi;
2504 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2506 if (bb_index == EXIT_BLOCK)
2508 unsigned regno;
2509 bitmap_iterator bi;
2510 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2511 regno, bi)
2512 gcc_unreachable ();
2514 else
2515 df_word_lr_bb_local_compute (bb_index);
2518 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2522 /* Initialize the solution vectors. */
2524 static void
2525 df_word_lr_init (bitmap all_blocks)
2527 unsigned int bb_index;
2528 bitmap_iterator bi;
2530 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2532 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2533 bitmap_copy (&bb_info->in, &bb_info->use);
2534 bitmap_clear (&bb_info->out);
2539 /* Confluence function that ignores fake edges. */
2541 static bool
2542 df_word_lr_confluence_n (edge e)
2544 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2545 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2547 return bitmap_ior_into (op1, op2);
2551 /* Transfer function. */
2553 static bool
2554 df_word_lr_transfer_function (int bb_index)
2556 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2557 bitmap in = &bb_info->in;
2558 bitmap out = &bb_info->out;
2559 bitmap use = &bb_info->use;
2560 bitmap def = &bb_info->def;
2562 return bitmap_ior_and_compl (in, use, out, def);
2566 /* Free all storage associated with the problem. */
2568 static void
2569 df_word_lr_free (void)
2571 struct df_word_lr_problem_data *problem_data
2572 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2574 if (df_word_lr->block_info)
2576 df_word_lr->block_info_size = 0;
2577 free (df_word_lr->block_info);
2578 df_word_lr->block_info = NULL;
2581 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2582 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2583 free (problem_data);
2584 free (df_word_lr);
2588 /* Debugging info at top of bb. */
2590 static void
2591 df_word_lr_top_dump (basic_block bb, FILE *file)
2593 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2594 if (!bb_info)
2595 return;
2597 fprintf (file, ";; blr in \t");
2598 df_print_word_regset (file, &bb_info->in);
2599 fprintf (file, ";; blr use \t");
2600 df_print_word_regset (file, &bb_info->use);
2601 fprintf (file, ";; blr def \t");
2602 df_print_word_regset (file, &bb_info->def);
2606 /* Debugging info at bottom of bb. */
2608 static void
2609 df_word_lr_bottom_dump (basic_block bb, FILE *file)
2611 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2612 if (!bb_info)
2613 return;
2615 fprintf (file, ";; blr out \t");
2616 df_print_word_regset (file, &bb_info->out);
2620 /* All of the information associated with every instance of the problem. */
2622 static struct df_problem problem_WORD_LR =
2624 DF_WORD_LR, /* Problem id. */
2625 DF_BACKWARD, /* Direction. */
2626 df_word_lr_alloc, /* Allocate the problem specific data. */
2627 df_word_lr_reset, /* Reset global information. */
2628 df_word_lr_free_bb_info, /* Free basic block info. */
2629 df_word_lr_local_compute, /* Local compute function. */
2630 df_word_lr_init, /* Init the solution specific data. */
2631 df_worklist_dataflow, /* Worklist solver. */
2632 NULL, /* Confluence operator 0. */
2633 df_word_lr_confluence_n, /* Confluence operator n. */
2634 df_word_lr_transfer_function, /* Transfer function. */
2635 NULL, /* Finalize function. */
2636 df_word_lr_free, /* Free all of the problem information. */
2637 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
2638 NULL, /* Debugging. */
2639 df_word_lr_top_dump, /* Debugging start block. */
2640 df_word_lr_bottom_dump, /* Debugging end block. */
2641 NULL, /* Debugging start insn. */
2642 NULL, /* Debugging end insn. */
2643 NULL, /* Incremental solution verify start. */
2644 NULL, /* Incremental solution verify end. */
2645 NULL, /* Dependent problem. */
2646 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */
2647 TV_DF_WORD_LR, /* Timing variable. */
2648 false /* Reset blocks on dropping out of blocks_to_analyze. */
2652 /* Create a new DATAFLOW instance and add it to an existing instance
2653 of DF. The returned structure is what is used to get at the
2654 solution. */
2656 void
2657 df_word_lr_add_problem (void)
2659 df_add_problem (&problem_WORD_LR);
2660 /* These will be initialized when df_scan_blocks processes each
2661 block. */
2662 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2666 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2667 any bits, which is used by the caller to determine whether a set is
2668 necessary. We also return true if there are other reasons not to delete
2669 an insn. */
2671 bool
2672 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
2674 bool changed = false;
2675 df_ref def;
2677 FOR_EACH_INSN_DEF (def, insn)
2678 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
2679 changed = true;
2680 else
2681 changed |= df_word_lr_mark_ref (def, false, live);
2682 return changed;
2686 /* Simulate the effects of the uses of INSN on LIVE. */
2688 void
2689 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
2691 df_ref use;
2693 FOR_EACH_INSN_USE (use, insn)
2694 df_word_lr_mark_ref (use, true, live);
2697 /*----------------------------------------------------------------------------
2698 This problem computes REG_DEAD and REG_UNUSED notes.
2699 ----------------------------------------------------------------------------*/
2701 static void
2702 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2704 df_note->optional_p = true;
2707 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2708 static void
2709 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
2711 if (dump_file)
2713 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2714 print_rtl (dump_file, note);
2715 fprintf (dump_file, "\n");
2720 /* After reg-stack, the x86 floating point stack regs are difficult to
2721 analyze because of all of the pushes, pops and rotations. Thus, we
2722 just leave the notes alone. */
2724 #ifdef STACK_REGS
2725 static inline bool
2726 df_ignore_stack_reg (int regno)
2728 return regstack_completed
2729 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2731 #else
2732 static inline bool
2733 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2735 return false;
2737 #endif
2740 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
2742 static void
2743 df_remove_dead_and_unused_notes (rtx_insn *insn)
2745 rtx *pprev = &REG_NOTES (insn);
2746 rtx link = *pprev;
2748 while (link)
2750 switch (REG_NOTE_KIND (link))
2752 case REG_DEAD:
2753 /* After reg-stack, we need to ignore any unused notes
2754 for the stack registers. */
2755 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2757 pprev = &XEXP (link, 1);
2758 link = *pprev;
2760 else
2762 rtx next = XEXP (link, 1);
2763 if (REG_DEAD_DEBUGGING)
2764 df_print_note ("deleting: ", insn, link);
2765 free_EXPR_LIST_node (link);
2766 *pprev = link = next;
2768 break;
2770 case REG_UNUSED:
2771 /* After reg-stack, we need to ignore any unused notes
2772 for the stack registers. */
2773 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2775 pprev = &XEXP (link, 1);
2776 link = *pprev;
2778 else
2780 rtx next = XEXP (link, 1);
2781 if (REG_DEAD_DEBUGGING)
2782 df_print_note ("deleting: ", insn, link);
2783 free_EXPR_LIST_node (link);
2784 *pprev = link = next;
2786 break;
2788 default:
2789 pprev = &XEXP (link, 1);
2790 link = *pprev;
2791 break;
2796 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2797 as the bitmap of currently live registers. */
2799 static void
2800 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
2802 rtx *pprev = &REG_NOTES (insn);
2803 rtx link = *pprev;
2805 while (link)
2807 switch (REG_NOTE_KIND (link))
2809 case REG_EQUAL:
2810 case REG_EQUIV:
2812 /* Remove the notes that refer to dead registers. As we have at most
2813 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2814 so we need to purge the complete EQ_USES vector when removing
2815 the note using df_notes_rescan. */
2816 df_ref use;
2817 bool deleted = false;
2819 FOR_EACH_INSN_EQ_USE (use, insn)
2820 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
2821 && DF_REF_LOC (use)
2822 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
2823 && !bitmap_bit_p (live, DF_REF_REGNO (use))
2824 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
2826 deleted = true;
2827 break;
2829 if (deleted)
2831 rtx next;
2832 if (REG_DEAD_DEBUGGING)
2833 df_print_note ("deleting: ", insn, link);
2834 next = XEXP (link, 1);
2835 free_EXPR_LIST_node (link);
2836 *pprev = link = next;
2837 df_notes_rescan (insn);
2839 else
2841 pprev = &XEXP (link, 1);
2842 link = *pprev;
2844 break;
2847 default:
2848 pprev = &XEXP (link, 1);
2849 link = *pprev;
2850 break;
2855 /* Set a NOTE_TYPE note for REG in INSN. */
2857 static inline void
2858 df_set_note (enum reg_note note_type, rtx insn, rtx reg)
2860 gcc_checking_assert (!DEBUG_INSN_P (insn));
2861 add_reg_note (insn, note_type, reg);
2864 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2865 arguments. Return true if the register value described by MWS's
2866 mw_reg is known to be completely unused, and if mw_reg can therefore
2867 be used in a REG_UNUSED note. */
2869 static bool
2870 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2871 bitmap live, bitmap artificial_uses)
2873 unsigned int r;
2875 /* If MWS describes a partial reference, create REG_UNUSED notes for
2876 individual hard registers. */
2877 if (mws->flags & DF_REF_PARTIAL)
2878 return false;
2880 /* Likewise if some part of the register is used. */
2881 for (r = mws->start_regno; r <= mws->end_regno; r++)
2882 if (bitmap_bit_p (live, r)
2883 || bitmap_bit_p (artificial_uses, r))
2884 return false;
2886 gcc_assert (REG_P (mws->mw_reg));
2887 return true;
2891 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2892 based on the bits in LIVE. Do not generate notes for registers in
2893 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
2894 not generated if the reg is both read and written by the
2895 instruction.
2898 static void
2899 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2900 bitmap live, bitmap do_not_gen,
2901 bitmap artificial_uses,
2902 struct dead_debug_local *debug)
2904 unsigned int r;
2906 if (REG_DEAD_DEBUGGING && dump_file)
2907 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2908 mws->start_regno, mws->end_regno);
2910 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2912 unsigned int regno = mws->start_regno;
2913 df_set_note (REG_UNUSED, insn, mws->mw_reg);
2914 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
2916 if (REG_DEAD_DEBUGGING)
2917 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2919 bitmap_set_bit (do_not_gen, regno);
2920 /* Only do this if the value is totally dead. */
2922 else
2923 for (r = mws->start_regno; r <= mws->end_regno; r++)
2925 if (!bitmap_bit_p (live, r)
2926 && !bitmap_bit_p (artificial_uses, r))
2928 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
2929 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
2930 if (REG_DEAD_DEBUGGING)
2931 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2933 bitmap_set_bit (do_not_gen, r);
2938 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2939 arguments. Return true if the register value described by MWS's
2940 mw_reg is known to be completely dead, and if mw_reg can therefore
2941 be used in a REG_DEAD note. */
2943 static bool
2944 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2945 bitmap live, bitmap artificial_uses,
2946 bitmap do_not_gen)
2948 unsigned int r;
2950 /* If MWS describes a partial reference, create REG_DEAD notes for
2951 individual hard registers. */
2952 if (mws->flags & DF_REF_PARTIAL)
2953 return false;
2955 /* Likewise if some part of the register is not dead. */
2956 for (r = mws->start_regno; r <= mws->end_regno; r++)
2957 if (bitmap_bit_p (live, r)
2958 || bitmap_bit_p (artificial_uses, r)
2959 || bitmap_bit_p (do_not_gen, r))
2960 return false;
2962 gcc_assert (REG_P (mws->mw_reg));
2963 return true;
2966 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2967 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
2968 from being set if the instruction both reads and writes the
2969 register. */
2971 static void
2972 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2973 bitmap live, bitmap do_not_gen,
2974 bitmap artificial_uses, bool *added_notes_p)
2976 unsigned int r;
2977 bool is_debug = *added_notes_p;
2979 *added_notes_p = false;
2981 if (REG_DEAD_DEBUGGING && dump_file)
2983 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
2984 mws->start_regno, mws->end_regno);
2985 df_print_regset (dump_file, do_not_gen);
2986 fprintf (dump_file, " live =");
2987 df_print_regset (dump_file, live);
2988 fprintf (dump_file, " artificial uses =");
2989 df_print_regset (dump_file, artificial_uses);
2992 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
2994 if (is_debug)
2996 *added_notes_p = true;
2997 return;
2999 /* Add a dead note for the entire multi word register. */
3000 df_set_note (REG_DEAD, insn, mws->mw_reg);
3001 if (REG_DEAD_DEBUGGING)
3002 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3004 else
3006 for (r = mws->start_regno; r <= mws->end_regno; r++)
3007 if (!bitmap_bit_p (live, r)
3008 && !bitmap_bit_p (artificial_uses, r)
3009 && !bitmap_bit_p (do_not_gen, r))
3011 if (is_debug)
3013 *added_notes_p = true;
3014 return;
3016 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3017 if (REG_DEAD_DEBUGGING)
3018 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3021 return;
3025 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3026 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3028 static void
3029 df_create_unused_note (rtx_insn *insn, df_ref def,
3030 bitmap live, bitmap artificial_uses,
3031 struct dead_debug_local *debug)
3033 unsigned int dregno = DF_REF_REGNO (def);
3035 if (REG_DEAD_DEBUGGING && dump_file)
3037 fprintf (dump_file, " regular looking at def ");
3038 df_ref_debug (def, dump_file);
3041 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3042 || bitmap_bit_p (live, dregno)
3043 || bitmap_bit_p (artificial_uses, dregno)
3044 || df_ignore_stack_reg (dregno)))
3046 rtx reg = (DF_REF_LOC (def))
3047 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3048 df_set_note (REG_UNUSED, insn, reg);
3049 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3050 if (REG_DEAD_DEBUGGING)
3051 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3054 return;
3058 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3059 info: lifetime, bb, and number of defs and uses for basic block
3060 BB. The three bitvectors are scratch regs used here. */
3062 static void
3063 df_note_bb_compute (unsigned int bb_index,
3064 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3066 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3067 rtx_insn *insn;
3068 df_ref def, use;
3069 struct dead_debug_local debug;
3071 dead_debug_local_init (&debug, NULL, NULL);
3073 bitmap_copy (live, df_get_live_out (bb));
3074 bitmap_clear (artificial_uses);
3076 if (REG_DEAD_DEBUGGING && dump_file)
3078 fprintf (dump_file, "live at bottom ");
3079 df_print_regset (dump_file, live);
3082 /* Process the artificial defs and uses at the bottom of the block
3083 to begin processing. */
3084 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3086 if (REG_DEAD_DEBUGGING && dump_file)
3087 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3089 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3090 bitmap_clear_bit (live, DF_REF_REGNO (def));
3093 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3094 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3096 unsigned int regno = DF_REF_REGNO (use);
3097 bitmap_set_bit (live, regno);
3099 /* Notes are not generated for any of the artificial registers
3100 at the bottom of the block. */
3101 bitmap_set_bit (artificial_uses, regno);
3104 if (REG_DEAD_DEBUGGING && dump_file)
3106 fprintf (dump_file, "live before artificials out ");
3107 df_print_regset (dump_file, live);
3110 FOR_BB_INSNS_REVERSE (bb, insn)
3112 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3113 df_mw_hardreg *mw;
3114 int debug_insn;
3116 if (!INSN_P (insn))
3117 continue;
3119 debug_insn = DEBUG_INSN_P (insn);
3121 bitmap_clear (do_not_gen);
3122 df_remove_dead_and_unused_notes (insn);
3124 /* Process the defs. */
3125 if (CALL_P (insn))
3127 if (REG_DEAD_DEBUGGING && dump_file)
3129 fprintf (dump_file, "processing call %d\n live =",
3130 INSN_UID (insn));
3131 df_print_regset (dump_file, live);
3134 /* We only care about real sets for calls. Clobbers cannot
3135 be depended on to really die. */
3136 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3137 if ((DF_MWS_REG_DEF_P (mw))
3138 && !df_ignore_stack_reg (mw->start_regno))
3139 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3140 artificial_uses, &debug);
3142 /* All of the defs except the return value are some sort of
3143 clobber. This code is for the return. */
3144 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3146 unsigned int dregno = DF_REF_REGNO (def);
3147 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3149 df_create_unused_note (insn,
3150 def, live, artificial_uses, &debug);
3151 bitmap_set_bit (do_not_gen, dregno);
3154 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3155 bitmap_clear_bit (live, dregno);
3158 else
3160 /* Regular insn. */
3161 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3162 if (DF_MWS_REG_DEF_P (mw))
3163 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3164 artificial_uses, &debug);
3166 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3168 unsigned int dregno = DF_REF_REGNO (def);
3169 df_create_unused_note (insn,
3170 def, live, artificial_uses, &debug);
3172 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3173 bitmap_set_bit (do_not_gen, dregno);
3175 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3176 bitmap_clear_bit (live, dregno);
3180 /* Process the uses. */
3181 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3182 if (DF_MWS_REG_USE_P (mw)
3183 && !df_ignore_stack_reg (mw->start_regno))
3185 bool really_add_notes = debug_insn != 0;
3187 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3188 artificial_uses,
3189 &really_add_notes);
3191 if (really_add_notes)
3192 debug_insn = -1;
3195 FOR_EACH_INSN_INFO_USE (use, insn_info)
3197 unsigned int uregno = DF_REF_REGNO (use);
3199 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3201 fprintf (dump_file, " regular looking at use ");
3202 df_ref_debug (use, dump_file);
3205 if (!bitmap_bit_p (live, uregno))
3207 if (debug_insn)
3209 if (debug_insn > 0)
3211 /* We won't add REG_UNUSED or REG_DEAD notes for
3212 these, so we don't have to mess with them in
3213 debug insns either. */
3214 if (!bitmap_bit_p (artificial_uses, uregno)
3215 && !df_ignore_stack_reg (uregno))
3216 dead_debug_add (&debug, use, uregno);
3217 continue;
3219 break;
3221 else
3222 dead_debug_insert_temp (&debug, uregno, insn,
3223 DEBUG_TEMP_BEFORE_WITH_REG);
3225 if ( (!(DF_REF_FLAGS (use)
3226 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3227 && (!bitmap_bit_p (do_not_gen, uregno))
3228 && (!bitmap_bit_p (artificial_uses, uregno))
3229 && (!df_ignore_stack_reg (uregno)))
3231 rtx reg = (DF_REF_LOC (use))
3232 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3233 df_set_note (REG_DEAD, insn, reg);
3235 if (REG_DEAD_DEBUGGING)
3236 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3238 /* This register is now live. */
3239 bitmap_set_bit (live, uregno);
3243 df_remove_dead_eq_notes (insn, live);
3245 if (debug_insn == -1)
3247 /* ??? We could probably do better here, replacing dead
3248 registers with their definitions. */
3249 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3250 df_insn_rescan_debug_internal (insn);
3254 dead_debug_local_finish (&debug, NULL);
3258 /* Compute register info: lifetime, bb, and number of defs and uses. */
3259 static void
3260 df_note_compute (bitmap all_blocks)
3262 unsigned int bb_index;
3263 bitmap_iterator bi;
3264 bitmap_head live, do_not_gen, artificial_uses;
3266 bitmap_initialize (&live, &df_bitmap_obstack);
3267 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3268 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3270 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3272 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3273 pseudos in debug insns because we don't always (re)visit blocks
3274 with death points after visiting dead uses. Even changing this
3275 loop to postorder would still leave room for visiting a death
3276 point before visiting a subsequent debug use. */
3277 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3280 bitmap_clear (&live);
3281 bitmap_clear (&do_not_gen);
3282 bitmap_clear (&artificial_uses);
3286 /* Free all storage associated with the problem. */
3288 static void
3289 df_note_free (void)
3291 free (df_note);
3295 /* All of the information associated every instance of the problem. */
3297 static struct df_problem problem_NOTE =
3299 DF_NOTE, /* Problem id. */
3300 DF_NONE, /* Direction. */
3301 df_note_alloc, /* Allocate the problem specific data. */
3302 NULL, /* Reset global information. */
3303 NULL, /* Free basic block info. */
3304 df_note_compute, /* Local compute function. */
3305 NULL, /* Init the solution specific data. */
3306 NULL, /* Iterative solver. */
3307 NULL, /* Confluence operator 0. */
3308 NULL, /* Confluence operator n. */
3309 NULL, /* Transfer function. */
3310 NULL, /* Finalize function. */
3311 df_note_free, /* Free all of the problem information. */
3312 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3313 NULL, /* Debugging. */
3314 NULL, /* Debugging start block. */
3315 NULL, /* Debugging end block. */
3316 NULL, /* Debugging start insn. */
3317 NULL, /* Debugging end insn. */
3318 NULL, /* Incremental solution verify start. */
3319 NULL, /* Incremental solution verify end. */
3320 &problem_LR, /* Dependent problem. */
3321 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3322 TV_DF_NOTE, /* Timing variable. */
3323 false /* Reset blocks on dropping out of blocks_to_analyze. */
3327 /* Create a new DATAFLOW instance and add it to an existing instance
3328 of DF. The returned structure is what is used to get at the
3329 solution. */
3331 void
3332 df_note_add_problem (void)
3334 df_add_problem (&problem_NOTE);
3340 /*----------------------------------------------------------------------------
3341 Functions for simulating the effects of single insns.
3343 You can either simulate in the forwards direction, starting from
3344 the top of a block or the backwards direction from the end of the
3345 block. If you go backwards, defs are examined first to clear bits,
3346 then uses are examined to set bits. If you go forwards, defs are
3347 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3348 are examined to clear bits. In either case, the result of examining
3349 a def can be undone (respectively by a use or a REG_UNUSED note).
3351 If you start at the top of the block, use one of DF_LIVE_IN or
3352 DF_LR_IN. If you start at the bottom of the block use one of
3353 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3354 THEY WILL BE DESTROYED.
3355 ----------------------------------------------------------------------------*/
3358 /* Find the set of DEFs for INSN. */
3360 void
3361 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3363 df_ref def;
3365 FOR_EACH_INSN_DEF (def, insn)
3366 bitmap_set_bit (defs, DF_REF_REGNO (def));
3369 /* Find the set of uses for INSN. This includes partial defs. */
3371 static void
3372 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3374 df_ref def, use;
3375 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3377 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3378 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3379 bitmap_set_bit (uses, DF_REF_REGNO (def));
3380 FOR_EACH_INSN_INFO_USE (use, insn_info)
3381 bitmap_set_bit (uses, DF_REF_REGNO (use));
3384 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3386 void
3387 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3389 df_ref def;
3391 FOR_EACH_INSN_DEF (def, insn)
3392 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3393 bitmap_set_bit (defs, DF_REF_REGNO (def));
3397 /* Simulate the effects of the defs of INSN on LIVE. */
3399 void
3400 df_simulate_defs (rtx_insn *insn, bitmap live)
3402 df_ref def;
3404 FOR_EACH_INSN_DEF (def, insn)
3406 unsigned int dregno = DF_REF_REGNO (def);
3408 /* If the def is to only part of the reg, it does
3409 not kill the other defs that reach here. */
3410 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3411 bitmap_clear_bit (live, dregno);
3416 /* Simulate the effects of the uses of INSN on LIVE. */
3418 void
3419 df_simulate_uses (rtx_insn *insn, bitmap live)
3421 df_ref use;
3423 if (DEBUG_INSN_P (insn))
3424 return;
3426 FOR_EACH_INSN_USE (use, insn)
3427 /* Add use to set of uses in this BB. */
3428 bitmap_set_bit (live, DF_REF_REGNO (use));
3432 /* Add back the always live regs in BB to LIVE. */
3434 static inline void
3435 df_simulate_fixup_sets (basic_block bb, bitmap live)
3437 /* These regs are considered always live so if they end up dying
3438 because of some def, we need to bring the back again. */
3439 if (bb_has_eh_pred (bb))
3440 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3441 else
3442 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3446 /*----------------------------------------------------------------------------
3447 The following three functions are used only for BACKWARDS scanning:
3448 i.e. they process the defs before the uses.
3450 df_simulate_initialize_backwards should be called first with a
3451 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3452 df_simulate_one_insn_backwards should be called for each insn in
3453 the block, starting with the last one. Finally,
3454 df_simulate_finalize_backwards can be called to get a new value
3455 of the sets at the top of the block (this is rarely used).
3456 ----------------------------------------------------------------------------*/
3458 /* Apply the artificial uses and defs at the end of BB in a backwards
3459 direction. */
3461 void
3462 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3464 df_ref def, use;
3465 int bb_index = bb->index;
3467 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3468 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3469 bitmap_clear_bit (live, DF_REF_REGNO (def));
3471 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3472 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3473 bitmap_set_bit (live, DF_REF_REGNO (use));
3477 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3479 void
3480 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3482 if (!NONDEBUG_INSN_P (insn))
3483 return;
3485 df_simulate_defs (insn, live);
3486 df_simulate_uses (insn, live);
3487 df_simulate_fixup_sets (bb, live);
3491 /* Apply the artificial uses and defs at the top of BB in a backwards
3492 direction. */
3494 void
3495 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3497 df_ref def;
3498 #ifdef EH_USES
3499 df_ref use;
3500 #endif
3501 int bb_index = bb->index;
3503 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3504 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3505 bitmap_clear_bit (live, DF_REF_REGNO (def));
3507 #ifdef EH_USES
3508 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3509 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3510 bitmap_set_bit (live, DF_REF_REGNO (use));
3511 #endif
3513 /*----------------------------------------------------------------------------
3514 The following three functions are used only for FORWARDS scanning:
3515 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3516 Thus it is important to add the DF_NOTES problem to the stack of
3517 problems computed before using these functions.
3519 df_simulate_initialize_forwards should be called first with a
3520 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3521 df_simulate_one_insn_forwards should be called for each insn in
3522 the block, starting with the first one.
3523 ----------------------------------------------------------------------------*/
3525 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3526 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3527 defs live. */
3529 void
3530 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3532 df_ref def;
3533 int bb_index = bb->index;
3535 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3536 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3537 bitmap_set_bit (live, DF_REF_REGNO (def));
3540 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3542 void
3543 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3545 rtx link;
3546 if (! INSN_P (insn))
3547 return;
3549 /* Make sure that DF_NOTE really is an active df problem. */
3550 gcc_assert (df_note);
3552 /* Note that this is the opposite as how the problem is defined, because
3553 in the LR problem defs _kill_ liveness. However, they do so backwards,
3554 while here the scan is performed forwards! So, first assume that the
3555 def is live, and if this is not true REG_UNUSED notes will rectify the
3556 situation. */
3557 df_simulate_find_noclobber_defs (insn, live);
3559 /* Clear all of the registers that go dead. */
3560 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3562 switch (REG_NOTE_KIND (link))
3564 case REG_DEAD:
3565 case REG_UNUSED:
3567 rtx reg = XEXP (link, 0);
3568 int regno = REGNO (reg);
3569 if (HARD_REGISTER_NUM_P (regno))
3570 bitmap_clear_range (live, regno,
3571 hard_regno_nregs[regno][GET_MODE (reg)]);
3572 else
3573 bitmap_clear_bit (live, regno);
3575 break;
3576 default:
3577 break;
3580 df_simulate_fixup_sets (bb, live);
3583 /* Used by the next two functions to encode information about the
3584 memory references we found. */
3585 #define MEMREF_NORMAL 1
3586 #define MEMREF_VOLATILE 2
3588 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3590 static int
3591 find_memory (rtx insn)
3593 int flags = 0;
3594 subrtx_iterator::array_type array;
3595 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3597 const_rtx x = *iter;
3598 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3599 flags |= MEMREF_VOLATILE;
3600 else if (MEM_P (x))
3602 if (MEM_VOLATILE_P (x))
3603 flags |= MEMREF_VOLATILE;
3604 else if (!MEM_READONLY_P (x))
3605 flags |= MEMREF_NORMAL;
3608 return flags;
3611 /* A subroutine of can_move_insns_across_p called through note_stores.
3612 DATA points to an integer in which we set either the bit for
3613 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3614 of either kind. */
3616 static void
3617 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
3618 void *data ATTRIBUTE_UNUSED)
3620 int *pflags = (int *)data;
3621 if (GET_CODE (x) == SUBREG)
3622 x = XEXP (x, 0);
3623 /* Treat stores to SP as stores to memory, this will prevent problems
3624 when there are references to the stack frame. */
3625 if (x == stack_pointer_rtx)
3626 *pflags |= MEMREF_VOLATILE;
3627 if (!MEM_P (x))
3628 return;
3629 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
3632 /* Scan BB backwards, using df_simulate functions to keep track of
3633 lifetimes, up to insn POINT. The result is stored in LIVE. */
3635 void
3636 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
3638 rtx_insn *insn;
3639 bitmap_copy (live, df_get_live_out (bb));
3640 df_simulate_initialize_backwards (bb, live);
3642 /* Scan and update life information until we reach the point we're
3643 interested in. */
3644 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
3645 df_simulate_one_insn_backwards (bb, insn, live);
3648 /* Return true if it is safe to move a group of insns, described by
3649 the range FROM to TO, backwards across another group of insns,
3650 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
3651 are no insns between ACROSS_TO and FROM, but they may be in
3652 different basic blocks; MERGE_BB is the block from which the
3653 insns will be moved. The caller must pass in a regset MERGE_LIVE
3654 which specifies the registers live after TO.
3656 This function may be called in one of two cases: either we try to
3657 move identical instructions from all successor blocks into their
3658 predecessor, or we try to move from only one successor block. If
3659 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3660 the second case. It should contain a set of registers live at the
3661 end of ACROSS_TO which must not be clobbered by moving the insns.
3662 In that case, we're also more careful about moving memory references
3663 and trapping insns.
3665 We return false if it is not safe to move the entire group, but it
3666 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
3667 is set to point at the last moveable insn in such a case. */
3669 bool
3670 can_move_insns_across (rtx_insn *from, rtx_insn *to,
3671 rtx_insn *across_from, rtx_insn *across_to,
3672 basic_block merge_bb, regset merge_live,
3673 regset other_branch_live, rtx_insn **pmove_upto)
3675 rtx_insn *insn, *next, *max_to;
3676 bitmap merge_set, merge_use, local_merge_live;
3677 bitmap test_set, test_use;
3678 unsigned i, fail = 0;
3679 bitmap_iterator bi;
3680 int memrefs_in_across = 0;
3681 int mem_sets_in_across = 0;
3682 bool trapping_insns_in_across = false;
3684 if (pmove_upto != NULL)
3685 *pmove_upto = NULL;
3687 /* Find real bounds, ignoring debug insns. */
3688 while (!NONDEBUG_INSN_P (from) && from != to)
3689 from = NEXT_INSN (from);
3690 while (!NONDEBUG_INSN_P (to) && from != to)
3691 to = PREV_INSN (to);
3693 for (insn = across_to; ; insn = next)
3695 if (CALL_P (insn))
3697 if (RTL_CONST_OR_PURE_CALL_P (insn))
3698 /* Pure functions can read from memory. Const functions can
3699 read from arguments that the ABI has forced onto the stack.
3700 Neither sort of read can be volatile. */
3701 memrefs_in_across |= MEMREF_NORMAL;
3702 else
3704 memrefs_in_across |= MEMREF_VOLATILE;
3705 mem_sets_in_across |= MEMREF_VOLATILE;
3708 if (NONDEBUG_INSN_P (insn))
3710 if (volatile_insn_p (PATTERN (insn)))
3711 return false;
3712 memrefs_in_across |= find_memory (insn);
3713 note_stores (PATTERN (insn), find_memory_stores,
3714 &mem_sets_in_across);
3715 /* This is used just to find sets of the stack pointer. */
3716 memrefs_in_across |= mem_sets_in_across;
3717 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
3719 next = PREV_INSN (insn);
3720 if (insn == across_from)
3721 break;
3724 /* Collect:
3725 MERGE_SET = set of registers set in MERGE_BB
3726 MERGE_USE = set of registers used in MERGE_BB and live at its top
3727 MERGE_LIVE = set of registers live at the point inside the MERGE
3728 range that we've reached during scanning
3729 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3730 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3731 and live before ACROSS_FROM. */
3733 merge_set = BITMAP_ALLOC (&reg_obstack);
3734 merge_use = BITMAP_ALLOC (&reg_obstack);
3735 local_merge_live = BITMAP_ALLOC (&reg_obstack);
3736 test_set = BITMAP_ALLOC (&reg_obstack);
3737 test_use = BITMAP_ALLOC (&reg_obstack);
3739 /* Compute the set of registers set and used in the ACROSS range. */
3740 if (other_branch_live != NULL)
3741 bitmap_copy (test_use, other_branch_live);
3742 df_simulate_initialize_backwards (merge_bb, test_use);
3743 for (insn = across_to; ; insn = next)
3745 if (NONDEBUG_INSN_P (insn))
3747 df_simulate_find_defs (insn, test_set);
3748 df_simulate_defs (insn, test_use);
3749 df_simulate_uses (insn, test_use);
3751 next = PREV_INSN (insn);
3752 if (insn == across_from)
3753 break;
3756 /* Compute an upper bound for the amount of insns moved, by finding
3757 the first insn in MERGE that sets a register in TEST_USE, or uses
3758 a register in TEST_SET. We also check for calls, trapping operations,
3759 and memory references. */
3760 max_to = NULL;
3761 for (insn = from; ; insn = next)
3763 if (CALL_P (insn))
3764 break;
3765 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
3766 break;
3767 if (NONDEBUG_INSN_P (insn))
3769 if (may_trap_or_fault_p (PATTERN (insn))
3770 && (trapping_insns_in_across
3771 || other_branch_live != NULL
3772 || volatile_insn_p (PATTERN (insn))))
3773 break;
3775 /* We cannot move memory stores past each other, or move memory
3776 reads past stores, at least not without tracking them and
3777 calling true_dependence on every pair.
3779 If there is no other branch and no memory references or
3780 sets in the ACROSS range, we can move memory references
3781 freely, even volatile ones.
3783 Otherwise, the rules are as follows: volatile memory
3784 references and stores can't be moved at all, and any type
3785 of memory reference can't be moved if there are volatile
3786 accesses or stores in the ACROSS range. That leaves
3787 normal reads, which can be moved, as the trapping case is
3788 dealt with elsewhere. */
3789 if (other_branch_live != NULL || memrefs_in_across != 0)
3791 int mem_ref_flags = 0;
3792 int mem_set_flags = 0;
3793 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
3794 mem_ref_flags = find_memory (insn);
3795 /* Catch sets of the stack pointer. */
3796 mem_ref_flags |= mem_set_flags;
3798 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
3799 break;
3800 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
3801 break;
3802 if (mem_set_flags != 0
3803 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
3804 break;
3806 df_simulate_find_uses (insn, merge_use);
3807 /* We're only interested in uses which use a value live at
3808 the top, not one previously set in this block. */
3809 bitmap_and_compl_into (merge_use, merge_set);
3810 df_simulate_find_defs (insn, merge_set);
3811 if (bitmap_intersect_p (merge_set, test_use)
3812 || bitmap_intersect_p (merge_use, test_set))
3813 break;
3814 #ifdef HAVE_cc0
3815 if (!sets_cc0_p (insn))
3816 #endif
3817 max_to = insn;
3819 next = NEXT_INSN (insn);
3820 if (insn == to)
3821 break;
3823 if (max_to != to)
3824 fail = 1;
3826 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
3827 goto out;
3829 /* Now, lower this upper bound by also taking into account that
3830 a range of insns moved across ACROSS must not leave a register
3831 live at the end that will be clobbered in ACROSS. We need to
3832 find a point where TEST_SET & LIVE == 0.
3834 Insns in the MERGE range that set registers which are also set
3835 in the ACROSS range may still be moved as long as we also move
3836 later insns which use the results of the set, and make the
3837 register dead again. This is verified by the condition stated
3838 above. We only need to test it for registers that are set in
3839 the moved region.
3841 MERGE_LIVE is provided by the caller and holds live registers after
3842 TO. */
3843 bitmap_copy (local_merge_live, merge_live);
3844 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
3845 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
3847 /* We're not interested in registers that aren't set in the moved
3848 region at all. */
3849 bitmap_and_into (local_merge_live, merge_set);
3850 for (;;)
3852 if (NONDEBUG_INSN_P (insn))
3854 if (!bitmap_intersect_p (test_set, local_merge_live)
3855 #ifdef HAVE_cc0
3856 && !sets_cc0_p (insn)
3857 #endif
3860 max_to = insn;
3861 break;
3864 df_simulate_one_insn_backwards (merge_bb, insn,
3865 local_merge_live);
3867 if (insn == from)
3869 fail = 1;
3870 goto out;
3872 insn = PREV_INSN (insn);
3875 if (max_to != to)
3876 fail = 1;
3878 if (pmove_upto)
3879 *pmove_upto = max_to;
3881 /* For small register class machines, don't lengthen lifetimes of
3882 hard registers before reload. */
3883 if (! reload_completed
3884 && targetm.small_register_classes_for_mode_p (VOIDmode))
3886 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3888 if (i < FIRST_PSEUDO_REGISTER
3889 && ! fixed_regs[i]
3890 && ! global_regs[i])
3892 fail = 1;
3893 break;
3898 out:
3899 BITMAP_FREE (merge_set);
3900 BITMAP_FREE (merge_use);
3901 BITMAP_FREE (local_merge_live);
3902 BITMAP_FREE (test_set);
3903 BITMAP_FREE (test_use);
3905 return !fail;
3909 /*----------------------------------------------------------------------------
3910 MULTIPLE DEFINITIONS
3912 Find the locations in the function reached by multiple definition sites
3913 for a live pseudo. In and out bitvectors are built for each basic
3914 block. They are restricted for efficiency to live registers.
3916 The gen and kill sets for the problem are obvious. Together they
3917 include all defined registers in a basic block; the gen set includes
3918 registers where a partial or conditional or may-clobber definition is
3919 last in the BB, while the kill set includes registers with a complete
3920 definition coming last. However, the computation of the dataflow
3921 itself is interesting.
3923 The idea behind it comes from SSA form's iterated dominance frontier
3924 criterion for inserting PHI functions. Just like in that case, we can use
3925 the dominance frontier to find places where multiple definitions meet;
3926 a register X defined in a basic block BB1 has multiple definitions in
3927 basic blocks in BB1's dominance frontier.
3929 So, the in-set of a basic block BB2 is not just the union of the
3930 out-sets of BB2's predecessors, but includes some more bits that come
3931 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3932 the previous paragraph). I called this set the init-set of BB2.
3934 (Note: I actually use the kill-set only to build the init-set.
3935 gen bits are anyway propagated from BB1 to BB2 by dataflow).
3937 For example, if you have
3939 BB1 : r10 = 0
3940 r11 = 0
3941 if <...> goto BB2 else goto BB3;
3943 BB2 : r10 = 1
3944 r12 = 1
3945 goto BB3;
3947 BB3 :
3949 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3950 init-set of BB3 includes r10 and r12, but not r11. Note that we do
3951 not need to iterate the dominance frontier, because we do not insert
3952 anything like PHI functions there! Instead, dataflow will take care of
3953 propagating the information to BB3's successors.
3954 ---------------------------------------------------------------------------*/
3956 /* Private data used to verify the solution for this problem. */
3957 struct df_md_problem_data
3959 /* An obstack for the bitmaps we need for this problem. */
3960 bitmap_obstack md_bitmaps;
3963 /* Scratch var used by transfer functions. This is used to do md analysis
3964 only for live registers. */
3965 static bitmap_head df_md_scratch;
3968 static void
3969 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3970 void *vbb_info)
3972 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
3973 if (bb_info)
3975 bitmap_clear (&bb_info->kill);
3976 bitmap_clear (&bb_info->gen);
3977 bitmap_clear (&bb_info->init);
3978 bitmap_clear (&bb_info->in);
3979 bitmap_clear (&bb_info->out);
3984 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3985 not touched unless the block is new. */
3987 static void
3988 df_md_alloc (bitmap all_blocks)
3990 unsigned int bb_index;
3991 bitmap_iterator bi;
3992 struct df_md_problem_data *problem_data;
3994 df_grow_bb_info (df_md);
3995 if (df_md->problem_data)
3996 problem_data = (struct df_md_problem_data *) df_md->problem_data;
3997 else
3999 problem_data = XNEW (struct df_md_problem_data);
4000 df_md->problem_data = problem_data;
4001 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4003 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4005 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4007 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4008 /* When bitmaps are already initialized, just clear them. */
4009 if (bb_info->init.obstack)
4011 bitmap_clear (&bb_info->init);
4012 bitmap_clear (&bb_info->gen);
4013 bitmap_clear (&bb_info->kill);
4014 bitmap_clear (&bb_info->in);
4015 bitmap_clear (&bb_info->out);
4017 else
4019 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4020 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4021 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4022 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4023 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4027 df_md->optional_p = true;
4030 /* Add the effect of the top artificial defs of BB to the multiple definitions
4031 bitmap LOCAL_MD. */
4033 void
4034 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4036 int bb_index = bb->index;
4037 df_ref def;
4038 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4039 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4041 unsigned int dregno = DF_REF_REGNO (def);
4042 if (DF_REF_FLAGS (def)
4043 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4044 bitmap_set_bit (local_md, dregno);
4045 else
4046 bitmap_clear_bit (local_md, dregno);
4051 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4052 LOCAL_MD. */
4054 void
4055 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4056 bitmap local_md)
4058 df_ref def;
4060 FOR_EACH_INSN_DEF (def, insn)
4062 unsigned int dregno = DF_REF_REGNO (def);
4063 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4064 || (dregno >= FIRST_PSEUDO_REGISTER))
4066 if (DF_REF_FLAGS (def)
4067 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4068 bitmap_set_bit (local_md, DF_REF_ID (def));
4069 else
4070 bitmap_clear_bit (local_md, DF_REF_ID (def));
4075 static void
4076 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4077 df_ref def,
4078 int top_flag)
4080 bitmap_clear (&seen_in_insn);
4082 for (; def; def = DF_REF_NEXT_LOC (def))
4084 unsigned int dregno = DF_REF_REGNO (def);
4085 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4086 || (dregno >= FIRST_PSEUDO_REGISTER))
4087 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4089 if (!bitmap_bit_p (&seen_in_insn, dregno))
4091 if (DF_REF_FLAGS (def)
4092 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4094 bitmap_set_bit (&bb_info->gen, dregno);
4095 bitmap_clear_bit (&bb_info->kill, dregno);
4097 else
4099 /* When we find a clobber and a regular def,
4100 make sure the regular def wins. */
4101 bitmap_set_bit (&seen_in_insn, dregno);
4102 bitmap_set_bit (&bb_info->kill, dregno);
4103 bitmap_clear_bit (&bb_info->gen, dregno);
4111 /* Compute local multiple def info for basic block BB. */
4113 static void
4114 df_md_bb_local_compute (unsigned int bb_index)
4116 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4117 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4118 rtx_insn *insn;
4120 /* Artificials are only hard regs. */
4121 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4122 df_md_bb_local_compute_process_def (bb_info,
4123 df_get_artificial_defs (bb_index),
4124 DF_REF_AT_TOP);
4126 FOR_BB_INSNS (bb, insn)
4128 unsigned int uid = INSN_UID (insn);
4129 if (!INSN_P (insn))
4130 continue;
4132 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4135 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4136 df_md_bb_local_compute_process_def (bb_info,
4137 df_get_artificial_defs (bb_index),
4141 /* Compute local reaching def info for each basic block within BLOCKS. */
4143 static void
4144 df_md_local_compute (bitmap all_blocks)
4146 unsigned int bb_index, df_bb_index;
4147 bitmap_iterator bi1, bi2;
4148 basic_block bb;
4149 bitmap_head *frontiers;
4151 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4153 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4155 df_md_bb_local_compute (bb_index);
4158 bitmap_clear (&seen_in_insn);
4160 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4161 FOR_ALL_BB_FN (bb, cfun)
4162 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4164 compute_dominance_frontiers (frontiers);
4166 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4167 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4169 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4170 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4172 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4173 if (bitmap_bit_p (all_blocks, df_bb_index))
4174 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4175 df_get_live_in (bb));
4179 FOR_ALL_BB_FN (bb, cfun)
4180 bitmap_clear (&frontiers[bb->index]);
4181 free (frontiers);
4185 /* Reset the global solution for recalculation. */
4187 static void
4188 df_md_reset (bitmap all_blocks)
4190 unsigned int bb_index;
4191 bitmap_iterator bi;
4193 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4195 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4196 gcc_assert (bb_info);
4197 bitmap_clear (&bb_info->in);
4198 bitmap_clear (&bb_info->out);
4202 static bool
4203 df_md_transfer_function (int bb_index)
4205 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4206 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4207 bitmap in = &bb_info->in;
4208 bitmap out = &bb_info->out;
4209 bitmap gen = &bb_info->gen;
4210 bitmap kill = &bb_info->kill;
4212 /* We need to use a scratch set here so that the value returned from this
4213 function invocation properly reflects whether the sets changed in a
4214 significant way; i.e. not just because the live set was anded in. */
4215 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4217 /* Multiple definitions of a register are not relevant if it is not
4218 live. Thus we trim the result to the places where it is live. */
4219 bitmap_and_into (in, df_get_live_in (bb));
4221 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4224 /* Initialize the solution bit vectors for problem. */
4226 static void
4227 df_md_init (bitmap all_blocks)
4229 unsigned int bb_index;
4230 bitmap_iterator bi;
4232 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4234 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4236 bitmap_copy (&bb_info->in, &bb_info->init);
4237 df_md_transfer_function (bb_index);
4241 static void
4242 df_md_confluence_0 (basic_block bb)
4244 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4245 bitmap_copy (&bb_info->in, &bb_info->init);
4248 /* In of target gets or of out of source. */
4250 static bool
4251 df_md_confluence_n (edge e)
4253 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4254 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4256 if (e->flags & EDGE_FAKE)
4257 return false;
4259 if (e->flags & EDGE_EH)
4260 return bitmap_ior_and_compl_into (op1, op2,
4261 regs_invalidated_by_call_regset);
4262 else
4263 return bitmap_ior_into (op1, op2);
4266 /* Free all storage associated with the problem. */
4268 static void
4269 df_md_free (void)
4271 struct df_md_problem_data *problem_data
4272 = (struct df_md_problem_data *) df_md->problem_data;
4274 bitmap_obstack_release (&problem_data->md_bitmaps);
4275 free (problem_data);
4276 df_md->problem_data = NULL;
4278 df_md->block_info_size = 0;
4279 free (df_md->block_info);
4280 df_md->block_info = NULL;
4281 free (df_md);
4285 /* Debugging info at top of bb. */
4287 static void
4288 df_md_top_dump (basic_block bb, FILE *file)
4290 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4291 if (!bb_info)
4292 return;
4294 fprintf (file, ";; md in \t");
4295 df_print_regset (file, &bb_info->in);
4296 fprintf (file, ";; md init \t");
4297 df_print_regset (file, &bb_info->init);
4298 fprintf (file, ";; md gen \t");
4299 df_print_regset (file, &bb_info->gen);
4300 fprintf (file, ";; md kill \t");
4301 df_print_regset (file, &bb_info->kill);
4304 /* Debugging info at bottom of bb. */
4306 static void
4307 df_md_bottom_dump (basic_block bb, FILE *file)
4309 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4310 if (!bb_info)
4311 return;
4313 fprintf (file, ";; md out \t");
4314 df_print_regset (file, &bb_info->out);
4317 static struct df_problem problem_MD =
4319 DF_MD, /* Problem id. */
4320 DF_FORWARD, /* Direction. */
4321 df_md_alloc, /* Allocate the problem specific data. */
4322 df_md_reset, /* Reset global information. */
4323 df_md_free_bb_info, /* Free basic block info. */
4324 df_md_local_compute, /* Local compute function. */
4325 df_md_init, /* Init the solution specific data. */
4326 df_worklist_dataflow, /* Worklist solver. */
4327 df_md_confluence_0, /* Confluence operator 0. */
4328 df_md_confluence_n, /* Confluence operator n. */
4329 df_md_transfer_function, /* Transfer function. */
4330 NULL, /* Finalize function. */
4331 df_md_free, /* Free all of the problem information. */
4332 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4333 NULL, /* Debugging. */
4334 df_md_top_dump, /* Debugging start block. */
4335 df_md_bottom_dump, /* Debugging end block. */
4336 NULL, /* Debugging start insn. */
4337 NULL, /* Debugging end insn. */
4338 NULL, /* Incremental solution verify start. */
4339 NULL, /* Incremental solution verify end. */
4340 NULL, /* Dependent problem. */
4341 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */
4342 TV_DF_MD, /* Timing variable. */
4343 false /* Reset blocks on dropping out of blocks_to_analyze. */
4346 /* Create a new MD instance and add it to the existing instance
4347 of DF. */
4349 void
4350 df_md_add_problem (void)
4352 df_add_problem (&problem_MD);