2015-03-24 Paolo Carlini <paolo.carlini@oracle.com>
[official-gcc.git] / gcc / df-problems.c
blob3f4aacd20f56f55c19a2a408af81888195c3e25e
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2015 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 "hashtab.h"
33 #include "hash-set.h"
34 #include "vec.h"
35 #include "machmode.h"
36 #include "hard-reg-set.h"
37 #include "input.h"
38 #include "function.h"
39 #include "regs.h"
40 #include "alloc-pool.h"
41 #include "flags.h"
42 #include "predict.h"
43 #include "dominance.h"
44 #include "cfg.h"
45 #include "cfganal.h"
46 #include "basic-block.h"
47 #include "sbitmap.h"
48 #include "bitmap.h"
49 #include "target.h"
50 #include "timevar.h"
51 #include "df.h"
52 #include "except.h"
53 #include "dce.h"
54 #include "valtrack.h"
55 #include "dumpfile.h"
56 #include "rtl-iter.h"
58 /* Note that turning REG_DEAD_DEBUGGING on will cause
59 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
60 addresses in the dumps. */
61 #define REG_DEAD_DEBUGGING 0
63 #define DF_SPARSE_THRESHOLD 32
65 static bitmap_head seen_in_block;
66 static bitmap_head seen_in_insn;
68 /*----------------------------------------------------------------------------
69 Utility functions.
70 ----------------------------------------------------------------------------*/
72 /* Generic versions to get the void* version of the block info. Only
73 used inside the problem instance vectors. */
75 /* Dump a def-use or use-def chain for REF to FILE. */
77 void
78 df_chain_dump (struct df_link *link, FILE *file)
80 fprintf (file, "{ ");
81 for (; link; link = link->next)
83 fprintf (file, "%c%d(bb %d insn %d) ",
84 DF_REF_REG_DEF_P (link->ref)
85 ? 'd'
86 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
87 DF_REF_ID (link->ref),
88 DF_REF_BBNO (link->ref),
89 DF_REF_IS_ARTIFICIAL (link->ref)
90 ? -1 : DF_REF_INSN_UID (link->ref));
92 fprintf (file, "}");
96 /* Print some basic block info as part of df_dump. */
98 void
99 df_print_bb_index (basic_block bb, FILE *file)
101 edge e;
102 edge_iterator ei;
104 fprintf (file, "\n( ");
105 FOR_EACH_EDGE (e, ei, bb->preds)
107 basic_block pred = e->src;
108 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
110 fprintf (file, ")->[%d]->( ", bb->index);
111 FOR_EACH_EDGE (e, ei, bb->succs)
113 basic_block succ = e->dest;
114 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
116 fprintf (file, ")\n");
120 /*----------------------------------------------------------------------------
121 REACHING DEFINITIONS
123 Find the locations in the function where each definition site for a
124 pseudo reaches. In and out bitvectors are built for each basic
125 block. The id field in the ref is used to index into these sets.
126 See df.h for details.
128 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
129 existing uses are included in the global reaching DEFs set, or in other
130 words only DEFs that are still live. This is a kind of pruned version
131 of the traditional reaching definitions problem that is much less
132 complex to compute and produces enough information to compute UD-chains.
133 In this context, live must be interpreted in the DF_LR sense: Uses that
134 are upward exposed but maybe not initialized on all paths through the
135 CFG. For a USE that is not reached by a DEF on all paths, we still want
136 to make those DEFs that do reach the USE visible, and pruning based on
137 DF_LIVE would make that impossible.
138 ----------------------------------------------------------------------------*/
140 /* This problem plays a large number of games for the sake of
141 efficiency.
143 1) The order of the bits in the bitvectors. After the scanning
144 phase, all of the defs are sorted. All of the defs for the reg 0
145 are first, followed by all defs for reg 1 and so on.
147 2) There are two kill sets, one if the number of defs is less or
148 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
149 greater.
151 <= : Data is built directly in the kill set.
153 > : One level of indirection is used to keep from generating long
154 strings of 1 bits in the kill sets. Bitvectors that are indexed
155 by the regnum are used to represent that there is a killing def
156 for the register. The confluence and transfer functions use
157 these along with the bitmap_clear_range call to remove ranges of
158 bits without actually generating a knockout vector.
160 The kill and sparse_kill and the dense_invalidated_by_call and
161 sparse_invalidated_by_call both play this game. */
163 /* Private data used to compute the solution for this problem. These
164 data structures are not accessible outside of this module. */
165 struct df_rd_problem_data
167 /* The set of defs to regs invalidated by call. */
168 bitmap_head sparse_invalidated_by_call;
169 /* The set of defs to regs invalidate by call for rd. */
170 bitmap_head dense_invalidated_by_call;
171 /* An obstack for the bitmaps we need for this problem. */
172 bitmap_obstack rd_bitmaps;
176 /* Free basic block info. */
178 static void
179 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
180 void *vbb_info)
182 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
183 if (bb_info)
185 bitmap_clear (&bb_info->kill);
186 bitmap_clear (&bb_info->sparse_kill);
187 bitmap_clear (&bb_info->gen);
188 bitmap_clear (&bb_info->in);
189 bitmap_clear (&bb_info->out);
194 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
195 not touched unless the block is new. */
197 static void
198 df_rd_alloc (bitmap all_blocks)
200 unsigned int bb_index;
201 bitmap_iterator bi;
202 struct df_rd_problem_data *problem_data;
204 if (df_rd->problem_data)
206 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
207 bitmap_clear (&problem_data->sparse_invalidated_by_call);
208 bitmap_clear (&problem_data->dense_invalidated_by_call);
210 else
212 problem_data = XNEW (struct df_rd_problem_data);
213 df_rd->problem_data = problem_data;
215 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
216 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
217 &problem_data->rd_bitmaps);
218 bitmap_initialize (&problem_data->dense_invalidated_by_call,
219 &problem_data->rd_bitmaps);
222 df_grow_bb_info (df_rd);
224 /* Because of the clustering of all use sites for the same pseudo,
225 we have to process all of the blocks before doing the analysis. */
227 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
229 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
231 /* When bitmaps are already initialized, just clear them. */
232 if (bb_info->kill.obstack)
234 bitmap_clear (&bb_info->kill);
235 bitmap_clear (&bb_info->sparse_kill);
236 bitmap_clear (&bb_info->gen);
238 else
240 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
241 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
242 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
243 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
244 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
247 df_rd->optional_p = true;
251 /* Add the effect of the top artificial defs of BB to the reaching definitions
252 bitmap LOCAL_RD. */
254 void
255 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
257 int bb_index = bb->index;
258 df_ref def;
259 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
260 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
262 unsigned int dregno = DF_REF_REGNO (def);
263 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
264 bitmap_clear_range (local_rd,
265 DF_DEFS_BEGIN (dregno),
266 DF_DEFS_COUNT (dregno));
267 bitmap_set_bit (local_rd, DF_REF_ID (def));
271 /* Add the effect of the defs of INSN to the reaching definitions bitmap
272 LOCAL_RD. */
274 void
275 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
276 bitmap local_rd)
278 df_ref def;
280 FOR_EACH_INSN_DEF (def, insn)
282 unsigned int dregno = DF_REF_REGNO (def);
283 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
284 || (dregno >= FIRST_PSEUDO_REGISTER))
286 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
287 bitmap_clear_range (local_rd,
288 DF_DEFS_BEGIN (dregno),
289 DF_DEFS_COUNT (dregno));
290 if (!(DF_REF_FLAGS (def)
291 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
292 bitmap_set_bit (local_rd, DF_REF_ID (def));
297 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
298 more complicated than just simulating, because we must produce the
299 gen and kill sets and hence deal with the two possible representations
300 of kill sets. */
302 static void
303 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
304 df_ref def,
305 int top_flag)
307 for (; def; def = DF_REF_NEXT_LOC (def))
309 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
311 unsigned int regno = DF_REF_REGNO (def);
312 unsigned int begin = DF_DEFS_BEGIN (regno);
313 unsigned int n_defs = DF_DEFS_COUNT (regno);
315 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
316 || (regno >= FIRST_PSEUDO_REGISTER))
318 /* Only the last def(s) for a regno in the block has any
319 effect. */
320 if (!bitmap_bit_p (&seen_in_block, regno))
322 /* The first def for regno in insn gets to knock out the
323 defs from other instructions. */
324 if ((!bitmap_bit_p (&seen_in_insn, regno))
325 /* If the def is to only part of the reg, it does
326 not kill the other defs that reach here. */
327 && (!(DF_REF_FLAGS (def) &
328 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
330 if (n_defs > DF_SPARSE_THRESHOLD)
332 bitmap_set_bit (&bb_info->sparse_kill, regno);
333 bitmap_clear_range (&bb_info->gen, begin, n_defs);
335 else
337 bitmap_set_range (&bb_info->kill, begin, n_defs);
338 bitmap_clear_range (&bb_info->gen, begin, n_defs);
342 bitmap_set_bit (&seen_in_insn, regno);
343 /* All defs for regno in the instruction may be put into
344 the gen set. */
345 if (!(DF_REF_FLAGS (def)
346 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
347 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
354 /* Compute local reaching def info for basic block BB. */
356 static void
357 df_rd_bb_local_compute (unsigned int bb_index)
359 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
360 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
361 rtx_insn *insn;
363 bitmap_clear (&seen_in_block);
364 bitmap_clear (&seen_in_insn);
366 /* Artificials are only hard regs. */
367 if (!(df->changeable_flags & DF_NO_HARD_REGS))
368 df_rd_bb_local_compute_process_def (bb_info,
369 df_get_artificial_defs (bb_index),
372 FOR_BB_INSNS_REVERSE (bb, insn)
374 unsigned int uid = INSN_UID (insn);
376 if (!INSN_P (insn))
377 continue;
379 df_rd_bb_local_compute_process_def (bb_info,
380 DF_INSN_UID_DEFS (uid), 0);
382 /* This complex dance with the two bitmaps is required because
383 instructions can assign twice to the same pseudo. This
384 generally happens with calls that will have one def for the
385 result and another def for the clobber. If only one vector
386 is used and the clobber goes first, the result will be
387 lost. */
388 bitmap_ior_into (&seen_in_block, &seen_in_insn);
389 bitmap_clear (&seen_in_insn);
392 /* Process the artificial defs at the top of the block last since we
393 are going backwards through the block and these are logically at
394 the start. */
395 if (!(df->changeable_flags & DF_NO_HARD_REGS))
396 df_rd_bb_local_compute_process_def (bb_info,
397 df_get_artificial_defs (bb_index),
398 DF_REF_AT_TOP);
402 /* Compute local reaching def info for each basic block within BLOCKS. */
404 static void
405 df_rd_local_compute (bitmap all_blocks)
407 unsigned int bb_index;
408 bitmap_iterator bi;
409 unsigned int regno;
410 struct df_rd_problem_data *problem_data
411 = (struct df_rd_problem_data *) df_rd->problem_data;
412 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
413 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
415 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
416 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
418 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
420 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
422 df_rd_bb_local_compute (bb_index);
425 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
426 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
428 if (! HARD_REGISTER_NUM_P (regno)
429 || !(df->changeable_flags & DF_NO_HARD_REGS))
431 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
432 bitmap_set_bit (sparse_invalidated, regno);
433 else
434 bitmap_set_range (dense_invalidated,
435 DF_DEFS_BEGIN (regno),
436 DF_DEFS_COUNT (regno));
440 bitmap_clear (&seen_in_block);
441 bitmap_clear (&seen_in_insn);
445 /* Initialize the solution bit vectors for problem. */
447 static void
448 df_rd_init_solution (bitmap all_blocks)
450 unsigned int bb_index;
451 bitmap_iterator bi;
453 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
455 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
457 bitmap_copy (&bb_info->out, &bb_info->gen);
458 bitmap_clear (&bb_info->in);
462 /* In of target gets or of out of source. */
464 static bool
465 df_rd_confluence_n (edge e)
467 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
468 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
469 bool changed = false;
471 if (e->flags & EDGE_FAKE)
472 return false;
474 if (e->flags & EDGE_EH)
476 struct df_rd_problem_data *problem_data
477 = (struct df_rd_problem_data *) df_rd->problem_data;
478 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
479 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
480 bitmap_iterator bi;
481 unsigned int regno;
482 bitmap_head tmp;
484 bitmap_initialize (&tmp, &df_bitmap_obstack);
485 bitmap_and_compl (&tmp, op2, dense_invalidated);
487 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
489 bitmap_clear_range (&tmp,
490 DF_DEFS_BEGIN (regno),
491 DF_DEFS_COUNT (regno));
493 changed |= bitmap_ior_into (op1, &tmp);
494 bitmap_clear (&tmp);
495 return changed;
497 else
498 return bitmap_ior_into (op1, op2);
502 /* Transfer function. */
504 static bool
505 df_rd_transfer_function (int bb_index)
507 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
508 unsigned int regno;
509 bitmap_iterator bi;
510 bitmap in = &bb_info->in;
511 bitmap out = &bb_info->out;
512 bitmap gen = &bb_info->gen;
513 bitmap kill = &bb_info->kill;
514 bitmap sparse_kill = &bb_info->sparse_kill;
515 bool changed = false;
517 if (bitmap_empty_p (sparse_kill))
518 changed = bitmap_ior_and_compl (out, gen, in, kill);
519 else
521 struct df_rd_problem_data *problem_data;
522 bitmap_head tmp;
524 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
525 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
526 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
527 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
529 bitmap_and_compl (&tmp, in, kill);
530 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
532 bitmap_clear_range (&tmp,
533 DF_DEFS_BEGIN (regno),
534 DF_DEFS_COUNT (regno));
536 bitmap_ior_into (&tmp, gen);
537 changed = !bitmap_equal_p (&tmp, out);
538 if (changed)
540 bitmap_clear (out);
541 bb_info->out = tmp;
543 else
544 bitmap_clear (&tmp);
547 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
549 /* Create a mask of DEFs for all registers live at the end of this
550 basic block, and mask out DEFs of registers that are not live.
551 Computing the mask looks costly, but the benefit of the pruning
552 outweighs the cost. */
553 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
554 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
555 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
556 unsigned int regno;
557 bitmap_iterator bi;
559 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
560 bitmap_set_range (live_defs,
561 DF_DEFS_BEGIN (regno),
562 DF_DEFS_COUNT (regno));
563 changed |= bitmap_and_into (&bb_info->out, live_defs);
564 BITMAP_FREE (live_defs);
567 return changed;
570 /* Free all storage associated with the problem. */
572 static void
573 df_rd_free (void)
575 struct df_rd_problem_data *problem_data
576 = (struct df_rd_problem_data *) df_rd->problem_data;
578 if (problem_data)
580 bitmap_obstack_release (&problem_data->rd_bitmaps);
582 df_rd->block_info_size = 0;
583 free (df_rd->block_info);
584 df_rd->block_info = NULL;
585 free (df_rd->problem_data);
587 free (df_rd);
591 /* Debugging info. */
593 static void
594 df_rd_start_dump (FILE *file)
596 struct df_rd_problem_data *problem_data
597 = (struct df_rd_problem_data *) df_rd->problem_data;
598 unsigned int m = DF_REG_SIZE (df);
599 unsigned int regno;
601 if (!df_rd->block_info)
602 return;
604 fprintf (file, ";; Reaching defs:\n");
606 fprintf (file, ";; sparse invalidated \t");
607 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
608 fprintf (file, ";; dense invalidated \t");
609 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
611 fprintf (file, ";; reg->defs[] map:\t");
612 for (regno = 0; regno < m; regno++)
613 if (DF_DEFS_COUNT (regno))
614 fprintf (file, "%d[%d,%d] ", regno,
615 DF_DEFS_BEGIN (regno),
616 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
617 fprintf (file, "\n");
621 static void
622 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
624 bitmap_head tmp;
625 unsigned int regno;
626 unsigned int m = DF_REG_SIZE (df);
627 bool first_reg = true;
629 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
631 bitmap_initialize (&tmp, &df_bitmap_obstack);
632 for (regno = 0; regno < m; regno++)
634 if (HARD_REGISTER_NUM_P (regno)
635 && (df->changeable_flags & DF_NO_HARD_REGS))
636 continue;
637 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
638 bitmap_and_into (&tmp, defs_set);
639 if (! bitmap_empty_p (&tmp))
641 bitmap_iterator bi;
642 unsigned int ix;
643 bool first_def = true;
645 if (! first_reg)
646 fprintf (file, ",");
647 first_reg = false;
649 fprintf (file, "%u[", regno);
650 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
652 fprintf (file, "%s%u", first_def ? "" : ",", ix);
653 first_def = false;
655 fprintf (file, "]");
657 bitmap_clear (&tmp);
660 fprintf (file, "\n");
661 bitmap_clear (&tmp);
664 /* Debugging info at top of bb. */
666 static void
667 df_rd_top_dump (basic_block bb, FILE *file)
669 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
670 if (!bb_info)
671 return;
673 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
674 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
675 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
679 /* Debugging info at bottom of bb. */
681 static void
682 df_rd_bottom_dump (basic_block bb, FILE *file)
684 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
685 if (!bb_info)
686 return;
688 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
691 /* All of the information associated with every instance of the problem. */
693 static struct df_problem problem_RD =
695 DF_RD, /* Problem id. */
696 DF_FORWARD, /* Direction. */
697 df_rd_alloc, /* Allocate the problem specific data. */
698 NULL, /* Reset global information. */
699 df_rd_free_bb_info, /* Free basic block info. */
700 df_rd_local_compute, /* Local compute function. */
701 df_rd_init_solution, /* Init the solution specific data. */
702 df_worklist_dataflow, /* Worklist solver. */
703 NULL, /* Confluence operator 0. */
704 df_rd_confluence_n, /* Confluence operator n. */
705 df_rd_transfer_function, /* Transfer function. */
706 NULL, /* Finalize function. */
707 df_rd_free, /* Free all of the problem information. */
708 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
709 df_rd_start_dump, /* Debugging. */
710 df_rd_top_dump, /* Debugging start block. */
711 df_rd_bottom_dump, /* Debugging end block. */
712 NULL, /* Debugging start insn. */
713 NULL, /* Debugging end insn. */
714 NULL, /* Incremental solution verify start. */
715 NULL, /* Incremental solution verify end. */
716 NULL, /* Dependent problem. */
717 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */
718 TV_DF_RD, /* Timing variable. */
719 true /* Reset blocks on dropping out of blocks_to_analyze. */
724 /* Create a new RD instance and add it to the existing instance
725 of DF. */
727 void
728 df_rd_add_problem (void)
730 df_add_problem (&problem_RD);
735 /*----------------------------------------------------------------------------
736 LIVE REGISTERS
738 Find the locations in the function where any use of a pseudo can
739 reach in the backwards direction. In and out bitvectors are built
740 for each basic block. The regno is used to index into these sets.
741 See df.h for details.
742 ----------------------------------------------------------------------------*/
744 /* Private data used to verify the solution for this problem. */
745 struct df_lr_problem_data
747 bitmap_head *in;
748 bitmap_head *out;
749 /* An obstack for the bitmaps we need for this problem. */
750 bitmap_obstack lr_bitmaps;
753 /* Free basic block info. */
755 static void
756 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
757 void *vbb_info)
759 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
760 if (bb_info)
762 bitmap_clear (&bb_info->use);
763 bitmap_clear (&bb_info->def);
764 bitmap_clear (&bb_info->in);
765 bitmap_clear (&bb_info->out);
770 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
771 not touched unless the block is new. */
773 static void
774 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
776 unsigned int bb_index;
777 bitmap_iterator bi;
778 struct df_lr_problem_data *problem_data;
780 df_grow_bb_info (df_lr);
781 if (df_lr->problem_data)
782 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
783 else
785 problem_data = XNEW (struct df_lr_problem_data);
786 df_lr->problem_data = problem_data;
788 problem_data->out = NULL;
789 problem_data->in = NULL;
790 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
793 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
795 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
797 /* When bitmaps are already initialized, just clear them. */
798 if (bb_info->use.obstack)
800 bitmap_clear (&bb_info->def);
801 bitmap_clear (&bb_info->use);
803 else
805 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
806 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
807 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
808 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
812 df_lr->optional_p = false;
816 /* Reset the global solution for recalculation. */
818 static void
819 df_lr_reset (bitmap all_blocks)
821 unsigned int bb_index;
822 bitmap_iterator bi;
824 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
826 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
827 gcc_assert (bb_info);
828 bitmap_clear (&bb_info->in);
829 bitmap_clear (&bb_info->out);
834 /* Compute local live register info for basic block BB. */
836 static void
837 df_lr_bb_local_compute (unsigned int bb_index)
839 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
840 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
841 rtx_insn *insn;
842 df_ref def, use;
844 /* Process the registers set in an exception handler. */
845 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
846 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
848 unsigned int dregno = DF_REF_REGNO (def);
849 bitmap_set_bit (&bb_info->def, dregno);
850 bitmap_clear_bit (&bb_info->use, dregno);
853 /* Process the hardware registers that are always live. */
854 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
855 /* Add use to set of uses in this BB. */
856 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
857 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
859 FOR_BB_INSNS_REVERSE (bb, insn)
861 if (!NONDEBUG_INSN_P (insn))
862 continue;
864 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
865 FOR_EACH_INSN_INFO_DEF (def, insn_info)
866 /* If the def is to only part of the reg, it does
867 not kill the other defs that reach here. */
868 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
870 unsigned int dregno = DF_REF_REGNO (def);
871 bitmap_set_bit (&bb_info->def, dregno);
872 bitmap_clear_bit (&bb_info->use, dregno);
875 FOR_EACH_INSN_INFO_USE (use, insn_info)
876 /* Add use to set of uses in this BB. */
877 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
880 /* Process the registers set in an exception handler or the hard
881 frame pointer if this block is the target of a non local
882 goto. */
883 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
884 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
886 unsigned int dregno = DF_REF_REGNO (def);
887 bitmap_set_bit (&bb_info->def, dregno);
888 bitmap_clear_bit (&bb_info->use, dregno);
891 #ifdef EH_USES
892 /* Process the uses that are live into an exception handler. */
893 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
894 /* Add use to set of uses in this BB. */
895 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
896 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
897 #endif
899 /* If the df_live problem is not defined, such as at -O0 and -O1, we
900 still need to keep the luids up to date. This is normally done
901 in the df_live problem since this problem has a forwards
902 scan. */
903 if (!df_live)
904 df_recompute_luids (bb);
908 /* Compute local live register info for each basic block within BLOCKS. */
910 static void
911 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
913 unsigned int bb_index, i;
914 bitmap_iterator bi;
916 bitmap_clear (&df->hardware_regs_used);
918 /* The all-important stack pointer must always be live. */
919 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
921 /* Global regs are always live, too. */
922 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
923 if (global_regs[i])
924 bitmap_set_bit (&df->hardware_regs_used, i);
926 /* Before reload, there are a few registers that must be forced
927 live everywhere -- which might not already be the case for
928 blocks within infinite loops. */
929 if (!reload_completed)
931 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
932 /* Any reference to any pseudo before reload is a potential
933 reference of the frame pointer. */
934 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
936 #if FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
937 /* Pseudos with argument area equivalences may require
938 reloading via the argument pointer. */
939 if (fixed_regs[ARG_POINTER_REGNUM])
940 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
941 #endif
943 /* Any constant, or pseudo with constant equivalences, may
944 require reloading from memory using the pic register. */
945 if (pic_offset_table_regnum != INVALID_REGNUM
946 && fixed_regs[pic_offset_table_regnum])
947 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
950 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
952 if (bb_index == EXIT_BLOCK)
954 /* The exit block is special for this problem and its bits are
955 computed from thin air. */
956 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
957 bitmap_copy (&bb_info->use, df->exit_block_uses);
959 else
960 df_lr_bb_local_compute (bb_index);
963 bitmap_clear (df_lr->out_of_date_transfer_functions);
967 /* Initialize the solution vectors. */
969 static void
970 df_lr_init (bitmap all_blocks)
972 unsigned int bb_index;
973 bitmap_iterator bi;
975 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
977 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
978 bitmap_copy (&bb_info->in, &bb_info->use);
979 bitmap_clear (&bb_info->out);
984 /* Confluence function that processes infinite loops. This might be a
985 noreturn function that throws. And even if it isn't, getting the
986 unwind info right helps debugging. */
987 static void
988 df_lr_confluence_0 (basic_block bb)
990 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
991 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
992 bitmap_copy (op1, &df->hardware_regs_used);
996 /* Confluence function that ignores fake edges. */
998 static bool
999 df_lr_confluence_n (edge e)
1001 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
1002 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
1003 bool changed = false;
1005 /* Call-clobbered registers die across exception and call edges. */
1006 /* ??? Abnormal call edges ignored for the moment, as this gets
1007 confused by sibling call edges, which crashes reg-stack. */
1008 if (e->flags & EDGE_EH)
1009 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
1010 else
1011 changed = bitmap_ior_into (op1, op2);
1013 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
1014 return changed;
1018 /* Transfer function. */
1020 static bool
1021 df_lr_transfer_function (int bb_index)
1023 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1024 bitmap in = &bb_info->in;
1025 bitmap out = &bb_info->out;
1026 bitmap use = &bb_info->use;
1027 bitmap def = &bb_info->def;
1029 return bitmap_ior_and_compl (in, use, out, def);
1033 /* Run the fast dce as a side effect of building LR. */
1035 static void
1036 df_lr_finalize (bitmap all_blocks)
1038 df_lr->solutions_dirty = false;
1039 if (df->changeable_flags & DF_LR_RUN_DCE)
1041 run_fast_df_dce ();
1043 /* If dce deletes some instructions, we need to recompute the lr
1044 solution before proceeding further. The problem is that fast
1045 dce is a pessimestic dataflow algorithm. In the case where
1046 it deletes a statement S inside of a loop, the uses inside of
1047 S may not be deleted from the dataflow solution because they
1048 were carried around the loop. While it is conservatively
1049 correct to leave these extra bits, the standards of df
1050 require that we maintain the best possible (least fixed
1051 point) solution. The only way to do that is to redo the
1052 iteration from the beginning. See PR35805 for an
1053 example. */
1054 if (df_lr->solutions_dirty)
1056 df_clear_flags (DF_LR_RUN_DCE);
1057 df_lr_alloc (all_blocks);
1058 df_lr_local_compute (all_blocks);
1059 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1060 df_lr_finalize (all_blocks);
1061 df_set_flags (DF_LR_RUN_DCE);
1067 /* Free all storage associated with the problem. */
1069 static void
1070 df_lr_free (void)
1072 struct df_lr_problem_data *problem_data
1073 = (struct df_lr_problem_data *) df_lr->problem_data;
1074 if (df_lr->block_info)
1077 df_lr->block_info_size = 0;
1078 free (df_lr->block_info);
1079 df_lr->block_info = NULL;
1080 bitmap_obstack_release (&problem_data->lr_bitmaps);
1081 free (df_lr->problem_data);
1082 df_lr->problem_data = NULL;
1085 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1086 free (df_lr);
1090 /* Debugging info at top of bb. */
1092 static void
1093 df_lr_top_dump (basic_block bb, FILE *file)
1095 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1096 struct df_lr_problem_data *problem_data;
1097 if (!bb_info)
1098 return;
1100 fprintf (file, ";; lr in \t");
1101 df_print_regset (file, &bb_info->in);
1102 if (df_lr->problem_data)
1104 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1105 if (problem_data->in)
1107 fprintf (file, ";; old in \t");
1108 df_print_regset (file, &problem_data->in[bb->index]);
1111 fprintf (file, ";; lr use \t");
1112 df_print_regset (file, &bb_info->use);
1113 fprintf (file, ";; lr def \t");
1114 df_print_regset (file, &bb_info->def);
1118 /* Debugging info at bottom of bb. */
1120 static void
1121 df_lr_bottom_dump (basic_block bb, FILE *file)
1123 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1124 struct df_lr_problem_data *problem_data;
1125 if (!bb_info)
1126 return;
1128 fprintf (file, ";; lr out \t");
1129 df_print_regset (file, &bb_info->out);
1130 if (df_lr->problem_data)
1132 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1133 if (problem_data->out)
1135 fprintf (file, ";; old out \t");
1136 df_print_regset (file, &problem_data->out[bb->index]);
1142 /* Build the datastructure to verify that the solution to the dataflow
1143 equations is not dirty. */
1145 static void
1146 df_lr_verify_solution_start (void)
1148 basic_block bb;
1149 struct df_lr_problem_data *problem_data;
1150 if (df_lr->solutions_dirty)
1151 return;
1153 /* Set it true so that the solution is recomputed. */
1154 df_lr->solutions_dirty = true;
1156 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1157 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1158 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1160 FOR_ALL_BB_FN (bb, cfun)
1162 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1163 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1164 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1165 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1170 /* Compare the saved datastructure and the new solution to the dataflow
1171 equations. */
1173 static void
1174 df_lr_verify_solution_end (void)
1176 struct df_lr_problem_data *problem_data;
1177 basic_block bb;
1179 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1181 if (!problem_data->out)
1182 return;
1184 if (df_lr->solutions_dirty)
1185 /* Do not check if the solution is still dirty. See the comment
1186 in df_lr_finalize for details. */
1187 df_lr->solutions_dirty = false;
1188 else
1189 FOR_ALL_BB_FN (bb, cfun)
1191 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1192 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1194 /*df_dump (stderr);*/
1195 gcc_unreachable ();
1199 /* Cannot delete them immediately because you may want to dump them
1200 if the comparison fails. */
1201 FOR_ALL_BB_FN (bb, cfun)
1203 bitmap_clear (&problem_data->in[bb->index]);
1204 bitmap_clear (&problem_data->out[bb->index]);
1207 free (problem_data->in);
1208 free (problem_data->out);
1209 problem_data->in = NULL;
1210 problem_data->out = NULL;
1214 /* All of the information associated with every instance of the problem. */
1216 static struct df_problem problem_LR =
1218 DF_LR, /* Problem id. */
1219 DF_BACKWARD, /* Direction. */
1220 df_lr_alloc, /* Allocate the problem specific data. */
1221 df_lr_reset, /* Reset global information. */
1222 df_lr_free_bb_info, /* Free basic block info. */
1223 df_lr_local_compute, /* Local compute function. */
1224 df_lr_init, /* Init the solution specific data. */
1225 df_worklist_dataflow, /* Worklist solver. */
1226 df_lr_confluence_0, /* Confluence operator 0. */
1227 df_lr_confluence_n, /* Confluence operator n. */
1228 df_lr_transfer_function, /* Transfer function. */
1229 df_lr_finalize, /* Finalize function. */
1230 df_lr_free, /* Free all of the problem information. */
1231 NULL, /* Remove this problem from the stack of dataflow problems. */
1232 NULL, /* Debugging. */
1233 df_lr_top_dump, /* Debugging start block. */
1234 df_lr_bottom_dump, /* Debugging end block. */
1235 NULL, /* Debugging start insn. */
1236 NULL, /* Debugging end insn. */
1237 df_lr_verify_solution_start,/* Incremental solution verify start. */
1238 df_lr_verify_solution_end, /* Incremental solution verify end. */
1239 NULL, /* Dependent problem. */
1240 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1241 TV_DF_LR, /* Timing variable. */
1242 false /* Reset blocks on dropping out of blocks_to_analyze. */
1246 /* Create a new DATAFLOW instance and add it to an existing instance
1247 of DF. The returned structure is what is used to get at the
1248 solution. */
1250 void
1251 df_lr_add_problem (void)
1253 df_add_problem (&problem_LR);
1254 /* These will be initialized when df_scan_blocks processes each
1255 block. */
1256 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1260 /* Verify that all of the lr related info is consistent and
1261 correct. */
1263 void
1264 df_lr_verify_transfer_functions (void)
1266 basic_block bb;
1267 bitmap_head saved_def;
1268 bitmap_head saved_use;
1269 bitmap_head all_blocks;
1271 if (!df)
1272 return;
1274 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1275 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1276 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1278 FOR_ALL_BB_FN (bb, cfun)
1280 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1281 bitmap_set_bit (&all_blocks, bb->index);
1283 if (bb_info)
1285 /* Make a copy of the transfer functions and then compute
1286 new ones to see if the transfer functions have
1287 changed. */
1288 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1289 bb->index))
1291 bitmap_copy (&saved_def, &bb_info->def);
1292 bitmap_copy (&saved_use, &bb_info->use);
1293 bitmap_clear (&bb_info->def);
1294 bitmap_clear (&bb_info->use);
1296 df_lr_bb_local_compute (bb->index);
1297 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1298 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1301 else
1303 /* If we do not have basic block info, the block must be in
1304 the list of dirty blocks or else some one has added a
1305 block behind our backs. */
1306 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1307 bb->index));
1309 /* Make sure no one created a block without following
1310 procedures. */
1311 gcc_assert (df_scan_get_bb_info (bb->index));
1314 /* Make sure there are no dirty bits in blocks that have been deleted. */
1315 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1316 &all_blocks));
1318 bitmap_clear (&saved_def);
1319 bitmap_clear (&saved_use);
1320 bitmap_clear (&all_blocks);
1325 /*----------------------------------------------------------------------------
1326 LIVE AND MUST-INITIALIZED REGISTERS.
1328 This problem first computes the IN and OUT bitvectors for the
1329 must-initialized registers problems, which is a forward problem.
1330 It gives the set of registers for which we MUST have an available
1331 definition on any path from the entry block to the entry/exit of
1332 a basic block. Sets generate a definition, while clobbers kill
1333 a definition.
1335 In and out bitvectors are built for each basic block and are indexed by
1336 regnum (see df.h for details). In and out bitvectors in struct
1337 df_live_bb_info actually refers to the must-initialized problem;
1339 Then, the in and out sets for the LIVE problem itself are computed.
1340 These are the logical AND of the IN and OUT sets from the LR problem
1341 and the must-initialized problem.
1342 ----------------------------------------------------------------------------*/
1344 /* Private data used to verify the solution for this problem. */
1345 struct df_live_problem_data
1347 bitmap_head *in;
1348 bitmap_head *out;
1349 /* An obstack for the bitmaps we need for this problem. */
1350 bitmap_obstack live_bitmaps;
1353 /* Scratch var used by transfer functions. This is used to implement
1354 an optimization to reduce the amount of space used to compute the
1355 combined lr and live analysis. */
1356 static bitmap_head df_live_scratch;
1359 /* Free basic block info. */
1361 static void
1362 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1363 void *vbb_info)
1365 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1366 if (bb_info)
1368 bitmap_clear (&bb_info->gen);
1369 bitmap_clear (&bb_info->kill);
1370 bitmap_clear (&bb_info->in);
1371 bitmap_clear (&bb_info->out);
1376 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1377 not touched unless the block is new. */
1379 static void
1380 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1382 unsigned int bb_index;
1383 bitmap_iterator bi;
1384 struct df_live_problem_data *problem_data;
1386 if (df_live->problem_data)
1387 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1388 else
1390 problem_data = XNEW (struct df_live_problem_data);
1391 df_live->problem_data = problem_data;
1393 problem_data->out = NULL;
1394 problem_data->in = NULL;
1395 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1396 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1399 df_grow_bb_info (df_live);
1401 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1403 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1405 /* When bitmaps are already initialized, just clear them. */
1406 if (bb_info->kill.obstack)
1408 bitmap_clear (&bb_info->kill);
1409 bitmap_clear (&bb_info->gen);
1411 else
1413 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1414 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1415 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1416 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1419 df_live->optional_p = (optimize <= 1);
1423 /* Reset the global solution for recalculation. */
1425 static void
1426 df_live_reset (bitmap all_blocks)
1428 unsigned int bb_index;
1429 bitmap_iterator bi;
1431 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1433 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1434 gcc_assert (bb_info);
1435 bitmap_clear (&bb_info->in);
1436 bitmap_clear (&bb_info->out);
1441 /* Compute local uninitialized register info for basic block BB. */
1443 static void
1444 df_live_bb_local_compute (unsigned int bb_index)
1446 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1447 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1448 rtx_insn *insn;
1449 df_ref def;
1450 int luid = 0;
1452 FOR_BB_INSNS (bb, insn)
1454 unsigned int uid = INSN_UID (insn);
1455 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1457 /* Inserting labels does not always trigger the incremental
1458 rescanning. */
1459 if (!insn_info)
1461 gcc_assert (!INSN_P (insn));
1462 insn_info = df_insn_create_insn_record (insn);
1465 DF_INSN_INFO_LUID (insn_info) = luid;
1466 if (!INSN_P (insn))
1467 continue;
1469 luid++;
1470 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1472 unsigned int regno = DF_REF_REGNO (def);
1474 if (DF_REF_FLAGS_IS_SET (def,
1475 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1476 /* All partial or conditional def
1477 seen are included in the gen set. */
1478 bitmap_set_bit (&bb_info->gen, regno);
1479 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1480 /* Only must clobbers for the entire reg destroy the
1481 value. */
1482 bitmap_set_bit (&bb_info->kill, regno);
1483 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1484 bitmap_set_bit (&bb_info->gen, regno);
1488 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1489 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1493 /* Compute local uninitialized register info. */
1495 static void
1496 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1498 unsigned int bb_index;
1499 bitmap_iterator bi;
1501 df_grow_insn_info ();
1503 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1504 0, bb_index, bi)
1506 df_live_bb_local_compute (bb_index);
1509 bitmap_clear (df_live->out_of_date_transfer_functions);
1513 /* Initialize the solution vectors. */
1515 static void
1516 df_live_init (bitmap all_blocks)
1518 unsigned int bb_index;
1519 bitmap_iterator bi;
1521 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1523 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1524 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1526 /* No register may reach a location where it is not used. Thus
1527 we trim the rr result to the places where it is used. */
1528 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1529 bitmap_clear (&bb_info->in);
1533 /* Forward confluence function that ignores fake edges. */
1535 static bool
1536 df_live_confluence_n (edge e)
1538 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1539 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1541 if (e->flags & EDGE_FAKE)
1542 return false;
1544 return bitmap_ior_into (op1, op2);
1548 /* Transfer function for the forwards must-initialized problem. */
1550 static bool
1551 df_live_transfer_function (int bb_index)
1553 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1554 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1555 bitmap in = &bb_info->in;
1556 bitmap out = &bb_info->out;
1557 bitmap gen = &bb_info->gen;
1558 bitmap kill = &bb_info->kill;
1560 /* We need to use a scratch set here so that the value returned from this
1561 function invocation properly reflects whether the sets changed in a
1562 significant way; i.e. not just because the lr set was anded in. */
1563 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1564 /* No register may reach a location where it is not used. Thus
1565 we trim the rr result to the places where it is used. */
1566 bitmap_and_into (in, &bb_lr_info->in);
1568 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1572 /* And the LR info with the must-initialized registers, to produce the LIVE info. */
1574 static void
1575 df_live_finalize (bitmap all_blocks)
1578 if (df_live->solutions_dirty)
1580 bitmap_iterator bi;
1581 unsigned int bb_index;
1583 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1585 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1586 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1588 /* No register may reach a location where it is not used. Thus
1589 we trim the rr result to the places where it is used. */
1590 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1591 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1594 df_live->solutions_dirty = false;
1599 /* Free all storage associated with the problem. */
1601 static void
1602 df_live_free (void)
1604 struct df_live_problem_data *problem_data
1605 = (struct df_live_problem_data *) df_live->problem_data;
1606 if (df_live->block_info)
1608 df_live->block_info_size = 0;
1609 free (df_live->block_info);
1610 df_live->block_info = NULL;
1611 bitmap_clear (&df_live_scratch);
1612 bitmap_obstack_release (&problem_data->live_bitmaps);
1613 free (problem_data);
1614 df_live->problem_data = NULL;
1616 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1617 free (df_live);
1621 /* Debugging info at top of bb. */
1623 static void
1624 df_live_top_dump (basic_block bb, FILE *file)
1626 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1627 struct df_live_problem_data *problem_data;
1629 if (!bb_info)
1630 return;
1632 fprintf (file, ";; live in \t");
1633 df_print_regset (file, &bb_info->in);
1634 if (df_live->problem_data)
1636 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1637 if (problem_data->in)
1639 fprintf (file, ";; old in \t");
1640 df_print_regset (file, &problem_data->in[bb->index]);
1643 fprintf (file, ";; live gen \t");
1644 df_print_regset (file, &bb_info->gen);
1645 fprintf (file, ";; live kill\t");
1646 df_print_regset (file, &bb_info->kill);
1650 /* Debugging info at bottom of bb. */
1652 static void
1653 df_live_bottom_dump (basic_block bb, FILE *file)
1655 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1656 struct df_live_problem_data *problem_data;
1658 if (!bb_info)
1659 return;
1661 fprintf (file, ";; live out \t");
1662 df_print_regset (file, &bb_info->out);
1663 if (df_live->problem_data)
1665 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1666 if (problem_data->out)
1668 fprintf (file, ";; old out \t");
1669 df_print_regset (file, &problem_data->out[bb->index]);
1675 /* Build the datastructure to verify that the solution to the dataflow
1676 equations is not dirty. */
1678 static void
1679 df_live_verify_solution_start (void)
1681 basic_block bb;
1682 struct df_live_problem_data *problem_data;
1683 if (df_live->solutions_dirty)
1684 return;
1686 /* Set it true so that the solution is recomputed. */
1687 df_live->solutions_dirty = true;
1689 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1690 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1691 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1693 FOR_ALL_BB_FN (bb, cfun)
1695 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1696 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1697 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1698 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1703 /* Compare the saved datastructure and the new solution to the dataflow
1704 equations. */
1706 static void
1707 df_live_verify_solution_end (void)
1709 struct df_live_problem_data *problem_data;
1710 basic_block bb;
1712 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1713 if (!problem_data->out)
1714 return;
1716 FOR_ALL_BB_FN (bb, cfun)
1718 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1719 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1721 /*df_dump (stderr);*/
1722 gcc_unreachable ();
1726 /* Cannot delete them immediately because you may want to dump them
1727 if the comparison fails. */
1728 FOR_ALL_BB_FN (bb, cfun)
1730 bitmap_clear (&problem_data->in[bb->index]);
1731 bitmap_clear (&problem_data->out[bb->index]);
1734 free (problem_data->in);
1735 free (problem_data->out);
1736 free (problem_data);
1737 df_live->problem_data = NULL;
1741 /* All of the information associated with every instance of the problem. */
1743 static struct df_problem problem_LIVE =
1745 DF_LIVE, /* Problem id. */
1746 DF_FORWARD, /* Direction. */
1747 df_live_alloc, /* Allocate the problem specific data. */
1748 df_live_reset, /* Reset global information. */
1749 df_live_free_bb_info, /* Free basic block info. */
1750 df_live_local_compute, /* Local compute function. */
1751 df_live_init, /* Init the solution specific data. */
1752 df_worklist_dataflow, /* Worklist solver. */
1753 NULL, /* Confluence operator 0. */
1754 df_live_confluence_n, /* Confluence operator n. */
1755 df_live_transfer_function, /* Transfer function. */
1756 df_live_finalize, /* Finalize function. */
1757 df_live_free, /* Free all of the problem information. */
1758 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1759 NULL, /* Debugging. */
1760 df_live_top_dump, /* Debugging start block. */
1761 df_live_bottom_dump, /* Debugging end block. */
1762 NULL, /* Debugging start insn. */
1763 NULL, /* Debugging end insn. */
1764 df_live_verify_solution_start,/* Incremental solution verify start. */
1765 df_live_verify_solution_end, /* Incremental solution verify end. */
1766 &problem_LR, /* Dependent problem. */
1767 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1768 TV_DF_LIVE, /* Timing variable. */
1769 false /* Reset blocks on dropping out of blocks_to_analyze. */
1773 /* Create a new DATAFLOW instance and add it to an existing instance
1774 of DF. The returned structure is what is used to get at the
1775 solution. */
1777 void
1778 df_live_add_problem (void)
1780 df_add_problem (&problem_LIVE);
1781 /* These will be initialized when df_scan_blocks processes each
1782 block. */
1783 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1787 /* Set all of the blocks as dirty. This needs to be done if this
1788 problem is added after all of the insns have been scanned. */
1790 void
1791 df_live_set_all_dirty (void)
1793 basic_block bb;
1794 FOR_ALL_BB_FN (bb, cfun)
1795 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1796 bb->index);
1800 /* Verify that all of the lr related info is consistent and
1801 correct. */
1803 void
1804 df_live_verify_transfer_functions (void)
1806 basic_block bb;
1807 bitmap_head saved_gen;
1808 bitmap_head saved_kill;
1809 bitmap_head all_blocks;
1811 if (!df)
1812 return;
1814 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1815 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1816 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1818 df_grow_insn_info ();
1820 FOR_ALL_BB_FN (bb, cfun)
1822 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1823 bitmap_set_bit (&all_blocks, bb->index);
1825 if (bb_info)
1827 /* Make a copy of the transfer functions and then compute
1828 new ones to see if the transfer functions have
1829 changed. */
1830 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1831 bb->index))
1833 bitmap_copy (&saved_gen, &bb_info->gen);
1834 bitmap_copy (&saved_kill, &bb_info->kill);
1835 bitmap_clear (&bb_info->gen);
1836 bitmap_clear (&bb_info->kill);
1838 df_live_bb_local_compute (bb->index);
1839 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1840 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1843 else
1845 /* If we do not have basic block info, the block must be in
1846 the list of dirty blocks or else some one has added a
1847 block behind our backs. */
1848 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1849 bb->index));
1851 /* Make sure no one created a block without following
1852 procedures. */
1853 gcc_assert (df_scan_get_bb_info (bb->index));
1856 /* Make sure there are no dirty bits in blocks that have been deleted. */
1857 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1858 &all_blocks));
1859 bitmap_clear (&saved_gen);
1860 bitmap_clear (&saved_kill);
1861 bitmap_clear (&all_blocks);
1864 /*----------------------------------------------------------------------------
1865 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
1867 Link either the defs to the uses and / or the uses to the defs.
1869 These problems are set up like the other dataflow problems so that
1870 they nicely fit into the framework. They are much simpler and only
1871 involve a single traversal of instructions and an examination of
1872 the reaching defs information (the dependent problem).
1873 ----------------------------------------------------------------------------*/
1875 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
1877 /* Create a du or ud chain from SRC to DST and link it into SRC. */
1879 struct df_link *
1880 df_chain_create (df_ref src, df_ref dst)
1882 struct df_link *head = DF_REF_CHAIN (src);
1883 struct df_link *link = (struct df_link *) pool_alloc (df_chain->block_pool);
1885 DF_REF_CHAIN (src) = link;
1886 link->next = head;
1887 link->ref = dst;
1888 return link;
1892 /* Delete any du or ud chains that start at REF and point to
1893 TARGET. */
1894 static void
1895 df_chain_unlink_1 (df_ref ref, df_ref target)
1897 struct df_link *chain = DF_REF_CHAIN (ref);
1898 struct df_link *prev = NULL;
1900 while (chain)
1902 if (chain->ref == target)
1904 if (prev)
1905 prev->next = chain->next;
1906 else
1907 DF_REF_CHAIN (ref) = chain->next;
1908 pool_free (df_chain->block_pool, chain);
1909 return;
1911 prev = chain;
1912 chain = chain->next;
1917 /* Delete a du or ud chain that leave or point to REF. */
1919 void
1920 df_chain_unlink (df_ref ref)
1922 struct df_link *chain = DF_REF_CHAIN (ref);
1923 while (chain)
1925 struct df_link *next = chain->next;
1926 /* Delete the other side if it exists. */
1927 df_chain_unlink_1 (chain->ref, ref);
1928 pool_free (df_chain->block_pool, chain);
1929 chain = next;
1931 DF_REF_CHAIN (ref) = NULL;
1935 /* Copy the du or ud chain starting at FROM_REF and attach it to
1936 TO_REF. */
1938 void
1939 df_chain_copy (df_ref to_ref,
1940 struct df_link *from_ref)
1942 while (from_ref)
1944 df_chain_create (to_ref, from_ref->ref);
1945 from_ref = from_ref->next;
1950 /* Remove this problem from the stack of dataflow problems. */
1952 static void
1953 df_chain_remove_problem (void)
1955 bitmap_iterator bi;
1956 unsigned int bb_index;
1958 /* Wholesale destruction of the old chains. */
1959 if (df_chain->block_pool)
1960 free_alloc_pool (df_chain->block_pool);
1962 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
1964 rtx_insn *insn;
1965 df_ref def, use;
1966 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1968 if (df_chain_problem_p (DF_DU_CHAIN))
1969 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1970 DF_REF_CHAIN (def) = NULL;
1971 if (df_chain_problem_p (DF_UD_CHAIN))
1972 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
1973 DF_REF_CHAIN (use) = NULL;
1975 FOR_BB_INSNS (bb, insn)
1976 if (INSN_P (insn))
1978 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
1979 if (df_chain_problem_p (DF_DU_CHAIN))
1980 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1981 DF_REF_CHAIN (def) = NULL;
1982 if (df_chain_problem_p (DF_UD_CHAIN))
1984 FOR_EACH_INSN_INFO_USE (use, insn_info)
1985 DF_REF_CHAIN (use) = NULL;
1986 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
1987 DF_REF_CHAIN (use) = NULL;
1992 bitmap_clear (df_chain->out_of_date_transfer_functions);
1993 df_chain->block_pool = NULL;
1997 /* Remove the chain problem completely. */
1999 static void
2000 df_chain_fully_remove_problem (void)
2002 df_chain_remove_problem ();
2003 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2004 free (df_chain);
2008 /* Create def-use or use-def chains. */
2010 static void
2011 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2013 df_chain_remove_problem ();
2014 df_chain->block_pool = create_alloc_pool ("df_chain_block pool",
2015 sizeof (struct df_link), 50);
2016 df_chain->optional_p = true;
2020 /* Reset all of the chains when the set of basic blocks changes. */
2022 static void
2023 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2025 df_chain_remove_problem ();
2029 /* Create the chains for a list of USEs. */
2031 static void
2032 df_chain_create_bb_process_use (bitmap local_rd,
2033 df_ref use,
2034 int top_flag)
2036 bitmap_iterator bi;
2037 unsigned int def_index;
2039 for (; use; use = DF_REF_NEXT_LOC (use))
2041 unsigned int uregno = DF_REF_REGNO (use);
2042 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2043 || (uregno >= FIRST_PSEUDO_REGISTER))
2045 /* Do not want to go through this for an uninitialized var. */
2046 int count = DF_DEFS_COUNT (uregno);
2047 if (count)
2049 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2051 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2052 unsigned int last_index = first_index + count - 1;
2054 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2056 df_ref def;
2057 if (def_index > last_index)
2058 break;
2060 def = DF_DEFS_GET (def_index);
2061 if (df_chain_problem_p (DF_DU_CHAIN))
2062 df_chain_create (def, use);
2063 if (df_chain_problem_p (DF_UD_CHAIN))
2064 df_chain_create (use, def);
2073 /* Create chains from reaching defs bitmaps for basic block BB. */
2075 static void
2076 df_chain_create_bb (unsigned int bb_index)
2078 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2079 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2080 rtx_insn *insn;
2081 bitmap_head cpy;
2083 bitmap_initialize (&cpy, &bitmap_default_obstack);
2084 bitmap_copy (&cpy, &bb_info->in);
2085 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2087 /* Since we are going forwards, process the artificial uses first
2088 then the artificial defs second. */
2090 #ifdef EH_USES
2091 /* Create the chains for the artificial uses from the EH_USES at the
2092 beginning of the block. */
2094 /* Artificials are only hard regs. */
2095 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2096 df_chain_create_bb_process_use (&cpy,
2097 df_get_artificial_uses (bb->index),
2098 DF_REF_AT_TOP);
2099 #endif
2101 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2103 /* Process the regular instructions next. */
2104 FOR_BB_INSNS (bb, insn)
2105 if (INSN_P (insn))
2107 unsigned int uid = INSN_UID (insn);
2109 /* First scan the uses and link them up with the defs that remain
2110 in the cpy vector. */
2111 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2112 if (df->changeable_flags & DF_EQ_NOTES)
2113 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2115 /* Since we are going forwards, process the defs second. */
2116 df_rd_simulate_one_insn (bb, insn, &cpy);
2119 /* Create the chains for the artificial uses of the hard registers
2120 at the end of the block. */
2121 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2122 df_chain_create_bb_process_use (&cpy,
2123 df_get_artificial_uses (bb->index),
2126 bitmap_clear (&cpy);
2129 /* Create def-use chains from reaching use bitmaps for basic blocks
2130 in BLOCKS. */
2132 static void
2133 df_chain_finalize (bitmap all_blocks)
2135 unsigned int bb_index;
2136 bitmap_iterator bi;
2138 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2140 df_chain_create_bb (bb_index);
2145 /* Free all storage associated with the problem. */
2147 static void
2148 df_chain_free (void)
2150 free_alloc_pool (df_chain->block_pool);
2151 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2152 free (df_chain);
2156 /* Debugging info. */
2158 static void
2159 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2161 /* Artificials are only hard regs. */
2162 if (df->changeable_flags & DF_NO_HARD_REGS)
2163 return;
2164 if (df_chain_problem_p (DF_UD_CHAIN))
2166 df_ref use;
2168 fprintf (file,
2169 ";; UD chains for artificial uses at %s\n",
2170 top ? "top" : "bottom");
2171 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2172 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2173 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2175 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2176 df_chain_dump (DF_REF_CHAIN (use), file);
2177 fprintf (file, "\n");
2180 if (df_chain_problem_p (DF_DU_CHAIN))
2182 df_ref def;
2184 fprintf (file,
2185 ";; DU chains for artificial defs at %s\n",
2186 top ? "top" : "bottom");
2187 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2188 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2189 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2191 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2192 df_chain_dump (DF_REF_CHAIN (def), file);
2193 fprintf (file, "\n");
2198 static void
2199 df_chain_top_dump (basic_block bb, FILE *file)
2201 df_chain_bb_dump (bb, file, /*top=*/true);
2204 static void
2205 df_chain_bottom_dump (basic_block bb, FILE *file)
2207 df_chain_bb_dump (bb, file, /*top=*/false);
2210 static void
2211 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2213 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2215 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2216 df_ref use;
2218 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2219 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2220 FOR_EACH_INSN_INFO_USE (use, insn_info)
2221 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2222 || !(df->changeable_flags & DF_NO_HARD_REGS))
2224 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2225 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2226 fprintf (file, "read/write ");
2227 df_chain_dump (DF_REF_CHAIN (use), file);
2228 fprintf (file, "\n");
2230 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2231 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2232 || !(df->changeable_flags & DF_NO_HARD_REGS))
2234 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2235 df_chain_dump (DF_REF_CHAIN (use), file);
2236 fprintf (file, "\n");
2241 static void
2242 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2244 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2246 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2247 df_ref def;
2248 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2249 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2250 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2251 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2252 || !(df->changeable_flags & DF_NO_HARD_REGS))
2254 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2255 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2256 fprintf (file, "read/write ");
2257 df_chain_dump (DF_REF_CHAIN (def), file);
2258 fprintf (file, "\n");
2260 fprintf (file, "\n");
2264 static struct df_problem problem_CHAIN =
2266 DF_CHAIN, /* Problem id. */
2267 DF_NONE, /* Direction. */
2268 df_chain_alloc, /* Allocate the problem specific data. */
2269 df_chain_reset, /* Reset global information. */
2270 NULL, /* Free basic block info. */
2271 NULL, /* Local compute function. */
2272 NULL, /* Init the solution specific data. */
2273 NULL, /* Iterative solver. */
2274 NULL, /* Confluence operator 0. */
2275 NULL, /* Confluence operator n. */
2276 NULL, /* Transfer function. */
2277 df_chain_finalize, /* Finalize function. */
2278 df_chain_free, /* Free all of the problem information. */
2279 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2280 NULL, /* Debugging. */
2281 df_chain_top_dump, /* Debugging start block. */
2282 df_chain_bottom_dump, /* Debugging end block. */
2283 df_chain_insn_top_dump, /* Debugging start insn. */
2284 df_chain_insn_bottom_dump, /* Debugging end insn. */
2285 NULL, /* Incremental solution verify start. */
2286 NULL, /* Incremental solution verify end. */
2287 &problem_RD, /* Dependent problem. */
2288 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2289 TV_DF_CHAIN, /* Timing variable. */
2290 false /* Reset blocks on dropping out of blocks_to_analyze. */
2294 /* Create a new DATAFLOW instance and add it to an existing instance
2295 of DF. The returned structure is what is used to get at the
2296 solution. */
2298 void
2299 df_chain_add_problem (unsigned int chain_flags)
2301 df_add_problem (&problem_CHAIN);
2302 df_chain->local_flags = chain_flags;
2303 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2306 #undef df_chain_problem_p
2309 /*----------------------------------------------------------------------------
2310 WORD LEVEL LIVE REGISTERS
2312 Find the locations in the function where any use of a pseudo can
2313 reach in the backwards direction. In and out bitvectors are built
2314 for each basic block. We only track pseudo registers that have a
2315 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2316 contain two bits corresponding to each of the subwords.
2318 ----------------------------------------------------------------------------*/
2320 /* Private data used to verify the solution for this problem. */
2321 struct df_word_lr_problem_data
2323 /* An obstack for the bitmaps we need for this problem. */
2324 bitmap_obstack word_lr_bitmaps;
2328 /* Free basic block info. */
2330 static void
2331 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2332 void *vbb_info)
2334 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2335 if (bb_info)
2337 bitmap_clear (&bb_info->use);
2338 bitmap_clear (&bb_info->def);
2339 bitmap_clear (&bb_info->in);
2340 bitmap_clear (&bb_info->out);
2345 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2346 not touched unless the block is new. */
2348 static void
2349 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2351 unsigned int bb_index;
2352 bitmap_iterator bi;
2353 basic_block bb;
2354 struct df_word_lr_problem_data *problem_data
2355 = XNEW (struct df_word_lr_problem_data);
2357 df_word_lr->problem_data = problem_data;
2359 df_grow_bb_info (df_word_lr);
2361 /* Create the mapping from regnos to slots. This does not change
2362 unless the problem is destroyed and recreated. In particular, if
2363 we end up deleting the only insn that used a subreg, we do not
2364 want to redo the mapping because this would invalidate everything
2365 else. */
2367 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2369 FOR_EACH_BB_FN (bb, cfun)
2370 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2372 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2373 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2375 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2377 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2379 /* When bitmaps are already initialized, just clear them. */
2380 if (bb_info->use.obstack)
2382 bitmap_clear (&bb_info->def);
2383 bitmap_clear (&bb_info->use);
2385 else
2387 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2388 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2389 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2390 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2394 df_word_lr->optional_p = true;
2398 /* Reset the global solution for recalculation. */
2400 static void
2401 df_word_lr_reset (bitmap all_blocks)
2403 unsigned int bb_index;
2404 bitmap_iterator bi;
2406 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2408 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2409 gcc_assert (bb_info);
2410 bitmap_clear (&bb_info->in);
2411 bitmap_clear (&bb_info->out);
2415 /* Examine REF, and if it is for a reg we're interested in, set or
2416 clear the bits corresponding to its subwords from the bitmap
2417 according to IS_SET. LIVE is the bitmap we should update. We do
2418 not track hard regs or pseudos of any size other than 2 *
2419 UNITS_PER_WORD.
2420 We return true if we changed the bitmap, or if we encountered a register
2421 we're not tracking. */
2423 bool
2424 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2426 rtx orig_reg = DF_REF_REG (ref);
2427 rtx reg = orig_reg;
2428 machine_mode reg_mode;
2429 unsigned regno;
2430 /* Left at -1 for whole accesses. */
2431 int which_subword = -1;
2432 bool changed = false;
2434 if (GET_CODE (reg) == SUBREG)
2435 reg = SUBREG_REG (orig_reg);
2436 regno = REGNO (reg);
2437 reg_mode = GET_MODE (reg);
2438 if (regno < FIRST_PSEUDO_REGISTER
2439 || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
2440 return true;
2442 if (GET_CODE (orig_reg) == SUBREG
2443 && df_read_modify_subreg_p (orig_reg))
2445 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2446 if (subreg_lowpart_p (orig_reg))
2447 which_subword = 0;
2448 else
2449 which_subword = 1;
2451 if (is_set)
2453 if (which_subword != 1)
2454 changed |= bitmap_set_bit (live, regno * 2);
2455 if (which_subword != 0)
2456 changed |= bitmap_set_bit (live, regno * 2 + 1);
2458 else
2460 if (which_subword != 1)
2461 changed |= bitmap_clear_bit (live, regno * 2);
2462 if (which_subword != 0)
2463 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2465 return changed;
2468 /* Compute local live register info for basic block BB. */
2470 static void
2471 df_word_lr_bb_local_compute (unsigned int bb_index)
2473 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2474 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2475 rtx_insn *insn;
2476 df_ref def, use;
2478 /* Ensure that artificial refs don't contain references to pseudos. */
2479 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2480 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2482 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2483 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2485 FOR_BB_INSNS_REVERSE (bb, insn)
2487 if (!NONDEBUG_INSN_P (insn))
2488 continue;
2490 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2491 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2492 /* If the def is to only part of the reg, it does
2493 not kill the other defs that reach here. */
2494 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2496 df_word_lr_mark_ref (def, true, &bb_info->def);
2497 df_word_lr_mark_ref (def, false, &bb_info->use);
2499 FOR_EACH_INSN_INFO_USE (use, insn_info)
2500 df_word_lr_mark_ref (use, true, &bb_info->use);
2505 /* Compute local live register info for each basic block within BLOCKS. */
2507 static void
2508 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2510 unsigned int bb_index;
2511 bitmap_iterator bi;
2513 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2515 if (bb_index == EXIT_BLOCK)
2517 unsigned regno;
2518 bitmap_iterator bi;
2519 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2520 regno, bi)
2521 gcc_unreachable ();
2523 else
2524 df_word_lr_bb_local_compute (bb_index);
2527 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2531 /* Initialize the solution vectors. */
2533 static void
2534 df_word_lr_init (bitmap all_blocks)
2536 unsigned int bb_index;
2537 bitmap_iterator bi;
2539 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2541 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2542 bitmap_copy (&bb_info->in, &bb_info->use);
2543 bitmap_clear (&bb_info->out);
2548 /* Confluence function that ignores fake edges. */
2550 static bool
2551 df_word_lr_confluence_n (edge e)
2553 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2554 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2556 return bitmap_ior_into (op1, op2);
2560 /* Transfer function. */
2562 static bool
2563 df_word_lr_transfer_function (int bb_index)
2565 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2566 bitmap in = &bb_info->in;
2567 bitmap out = &bb_info->out;
2568 bitmap use = &bb_info->use;
2569 bitmap def = &bb_info->def;
2571 return bitmap_ior_and_compl (in, use, out, def);
2575 /* Free all storage associated with the problem. */
2577 static void
2578 df_word_lr_free (void)
2580 struct df_word_lr_problem_data *problem_data
2581 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2583 if (df_word_lr->block_info)
2585 df_word_lr->block_info_size = 0;
2586 free (df_word_lr->block_info);
2587 df_word_lr->block_info = NULL;
2590 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2591 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2592 free (problem_data);
2593 free (df_word_lr);
2597 /* Debugging info at top of bb. */
2599 static void
2600 df_word_lr_top_dump (basic_block bb, FILE *file)
2602 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2603 if (!bb_info)
2604 return;
2606 fprintf (file, ";; blr in \t");
2607 df_print_word_regset (file, &bb_info->in);
2608 fprintf (file, ";; blr use \t");
2609 df_print_word_regset (file, &bb_info->use);
2610 fprintf (file, ";; blr def \t");
2611 df_print_word_regset (file, &bb_info->def);
2615 /* Debugging info at bottom of bb. */
2617 static void
2618 df_word_lr_bottom_dump (basic_block bb, FILE *file)
2620 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2621 if (!bb_info)
2622 return;
2624 fprintf (file, ";; blr out \t");
2625 df_print_word_regset (file, &bb_info->out);
2629 /* All of the information associated with every instance of the problem. */
2631 static struct df_problem problem_WORD_LR =
2633 DF_WORD_LR, /* Problem id. */
2634 DF_BACKWARD, /* Direction. */
2635 df_word_lr_alloc, /* Allocate the problem specific data. */
2636 df_word_lr_reset, /* Reset global information. */
2637 df_word_lr_free_bb_info, /* Free basic block info. */
2638 df_word_lr_local_compute, /* Local compute function. */
2639 df_word_lr_init, /* Init the solution specific data. */
2640 df_worklist_dataflow, /* Worklist solver. */
2641 NULL, /* Confluence operator 0. */
2642 df_word_lr_confluence_n, /* Confluence operator n. */
2643 df_word_lr_transfer_function, /* Transfer function. */
2644 NULL, /* Finalize function. */
2645 df_word_lr_free, /* Free all of the problem information. */
2646 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
2647 NULL, /* Debugging. */
2648 df_word_lr_top_dump, /* Debugging start block. */
2649 df_word_lr_bottom_dump, /* Debugging end block. */
2650 NULL, /* Debugging start insn. */
2651 NULL, /* Debugging end insn. */
2652 NULL, /* Incremental solution verify start. */
2653 NULL, /* Incremental solution verify end. */
2654 NULL, /* Dependent problem. */
2655 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */
2656 TV_DF_WORD_LR, /* Timing variable. */
2657 false /* Reset blocks on dropping out of blocks_to_analyze. */
2661 /* Create a new DATAFLOW instance and add it to an existing instance
2662 of DF. The returned structure is what is used to get at the
2663 solution. */
2665 void
2666 df_word_lr_add_problem (void)
2668 df_add_problem (&problem_WORD_LR);
2669 /* These will be initialized when df_scan_blocks processes each
2670 block. */
2671 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2675 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
2676 any bits, which is used by the caller to determine whether a set is
2677 necessary. We also return true if there are other reasons not to delete
2678 an insn. */
2680 bool
2681 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
2683 bool changed = false;
2684 df_ref def;
2686 FOR_EACH_INSN_DEF (def, insn)
2687 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
2688 changed = true;
2689 else
2690 changed |= df_word_lr_mark_ref (def, false, live);
2691 return changed;
2695 /* Simulate the effects of the uses of INSN on LIVE. */
2697 void
2698 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
2700 df_ref use;
2702 FOR_EACH_INSN_USE (use, insn)
2703 df_word_lr_mark_ref (use, true, live);
2706 /*----------------------------------------------------------------------------
2707 This problem computes REG_DEAD and REG_UNUSED notes.
2708 ----------------------------------------------------------------------------*/
2710 static void
2711 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2713 df_note->optional_p = true;
2716 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
2717 static void
2718 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
2720 if (dump_file)
2722 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
2723 print_rtl (dump_file, note);
2724 fprintf (dump_file, "\n");
2729 /* After reg-stack, the x86 floating point stack regs are difficult to
2730 analyze because of all of the pushes, pops and rotations. Thus, we
2731 just leave the notes alone. */
2733 #ifdef STACK_REGS
2734 static inline bool
2735 df_ignore_stack_reg (int regno)
2737 return regstack_completed
2738 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
2740 #else
2741 static inline bool
2742 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
2744 return false;
2746 #endif
2749 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
2751 static void
2752 df_remove_dead_and_unused_notes (rtx_insn *insn)
2754 rtx *pprev = &REG_NOTES (insn);
2755 rtx link = *pprev;
2757 while (link)
2759 switch (REG_NOTE_KIND (link))
2761 case REG_DEAD:
2762 /* After reg-stack, we need to ignore any unused notes
2763 for the stack registers. */
2764 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2766 pprev = &XEXP (link, 1);
2767 link = *pprev;
2769 else
2771 rtx next = XEXP (link, 1);
2772 if (REG_DEAD_DEBUGGING)
2773 df_print_note ("deleting: ", insn, link);
2774 free_EXPR_LIST_node (link);
2775 *pprev = link = next;
2777 break;
2779 case REG_UNUSED:
2780 /* After reg-stack, we need to ignore any unused notes
2781 for the stack registers. */
2782 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
2784 pprev = &XEXP (link, 1);
2785 link = *pprev;
2787 else
2789 rtx next = XEXP (link, 1);
2790 if (REG_DEAD_DEBUGGING)
2791 df_print_note ("deleting: ", insn, link);
2792 free_EXPR_LIST_node (link);
2793 *pprev = link = next;
2795 break;
2797 default:
2798 pprev = &XEXP (link, 1);
2799 link = *pprev;
2800 break;
2805 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
2806 as the bitmap of currently live registers. */
2808 static void
2809 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
2811 rtx *pprev = &REG_NOTES (insn);
2812 rtx link = *pprev;
2814 while (link)
2816 switch (REG_NOTE_KIND (link))
2818 case REG_EQUAL:
2819 case REG_EQUIV:
2821 /* Remove the notes that refer to dead registers. As we have at most
2822 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
2823 so we need to purge the complete EQ_USES vector when removing
2824 the note using df_notes_rescan. */
2825 df_ref use;
2826 bool deleted = false;
2828 FOR_EACH_INSN_EQ_USE (use, insn)
2829 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
2830 && DF_REF_LOC (use)
2831 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
2832 && !bitmap_bit_p (live, DF_REF_REGNO (use))
2833 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
2835 deleted = true;
2836 break;
2838 if (deleted)
2840 rtx next;
2841 if (REG_DEAD_DEBUGGING)
2842 df_print_note ("deleting: ", insn, link);
2843 next = XEXP (link, 1);
2844 free_EXPR_LIST_node (link);
2845 *pprev = link = next;
2846 df_notes_rescan (insn);
2848 else
2850 pprev = &XEXP (link, 1);
2851 link = *pprev;
2853 break;
2856 default:
2857 pprev = &XEXP (link, 1);
2858 link = *pprev;
2859 break;
2864 /* Set a NOTE_TYPE note for REG in INSN. */
2866 static inline void
2867 df_set_note (enum reg_note note_type, rtx insn, rtx reg)
2869 gcc_checking_assert (!DEBUG_INSN_P (insn));
2870 add_reg_note (insn, note_type, reg);
2873 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
2874 arguments. Return true if the register value described by MWS's
2875 mw_reg is known to be completely unused, and if mw_reg can therefore
2876 be used in a REG_UNUSED note. */
2878 static bool
2879 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
2880 bitmap live, bitmap artificial_uses)
2882 unsigned int r;
2884 /* If MWS describes a partial reference, create REG_UNUSED notes for
2885 individual hard registers. */
2886 if (mws->flags & DF_REF_PARTIAL)
2887 return false;
2889 /* Likewise if some part of the register is used. */
2890 for (r = mws->start_regno; r <= mws->end_regno; r++)
2891 if (bitmap_bit_p (live, r)
2892 || bitmap_bit_p (artificial_uses, r))
2893 return false;
2895 gcc_assert (REG_P (mws->mw_reg));
2896 return true;
2900 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
2901 based on the bits in LIVE. Do not generate notes for registers in
2902 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
2903 not generated if the reg is both read and written by the
2904 instruction.
2907 static void
2908 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2909 bitmap live, bitmap do_not_gen,
2910 bitmap artificial_uses,
2911 struct dead_debug_local *debug)
2913 unsigned int r;
2915 if (REG_DEAD_DEBUGGING && dump_file)
2916 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
2917 mws->start_regno, mws->end_regno);
2919 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
2921 unsigned int regno = mws->start_regno;
2922 df_set_note (REG_UNUSED, insn, mws->mw_reg);
2923 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
2925 if (REG_DEAD_DEBUGGING)
2926 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
2928 bitmap_set_bit (do_not_gen, regno);
2929 /* Only do this if the value is totally dead. */
2931 else
2932 for (r = mws->start_regno; r <= mws->end_regno; r++)
2934 if (!bitmap_bit_p (live, r)
2935 && !bitmap_bit_p (artificial_uses, r))
2937 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
2938 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
2939 if (REG_DEAD_DEBUGGING)
2940 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
2942 bitmap_set_bit (do_not_gen, r);
2947 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
2948 arguments. Return true if the register value described by MWS's
2949 mw_reg is known to be completely dead, and if mw_reg can therefore
2950 be used in a REG_DEAD note. */
2952 static bool
2953 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
2954 bitmap live, bitmap artificial_uses,
2955 bitmap do_not_gen)
2957 unsigned int r;
2959 /* If MWS describes a partial reference, create REG_DEAD notes for
2960 individual hard registers. */
2961 if (mws->flags & DF_REF_PARTIAL)
2962 return false;
2964 /* Likewise if some part of the register is not dead. */
2965 for (r = mws->start_regno; r <= mws->end_regno; r++)
2966 if (bitmap_bit_p (live, r)
2967 || bitmap_bit_p (artificial_uses, r)
2968 || bitmap_bit_p (do_not_gen, r))
2969 return false;
2971 gcc_assert (REG_P (mws->mw_reg));
2972 return true;
2975 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
2976 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
2977 from being set if the instruction both reads and writes the
2978 register. */
2980 static void
2981 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
2982 bitmap live, bitmap do_not_gen,
2983 bitmap artificial_uses, bool *added_notes_p)
2985 unsigned int r;
2986 bool is_debug = *added_notes_p;
2988 *added_notes_p = false;
2990 if (REG_DEAD_DEBUGGING && dump_file)
2992 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
2993 mws->start_regno, mws->end_regno);
2994 df_print_regset (dump_file, do_not_gen);
2995 fprintf (dump_file, " live =");
2996 df_print_regset (dump_file, live);
2997 fprintf (dump_file, " artificial uses =");
2998 df_print_regset (dump_file, artificial_uses);
3001 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3003 if (is_debug)
3005 *added_notes_p = true;
3006 return;
3008 /* Add a dead note for the entire multi word register. */
3009 df_set_note (REG_DEAD, insn, mws->mw_reg);
3010 if (REG_DEAD_DEBUGGING)
3011 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3013 else
3015 for (r = mws->start_regno; r <= mws->end_regno; r++)
3016 if (!bitmap_bit_p (live, r)
3017 && !bitmap_bit_p (artificial_uses, r)
3018 && !bitmap_bit_p (do_not_gen, r))
3020 if (is_debug)
3022 *added_notes_p = true;
3023 return;
3025 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3026 if (REG_DEAD_DEBUGGING)
3027 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3030 return;
3034 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3035 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3037 static void
3038 df_create_unused_note (rtx_insn *insn, df_ref def,
3039 bitmap live, bitmap artificial_uses,
3040 struct dead_debug_local *debug)
3042 unsigned int dregno = DF_REF_REGNO (def);
3044 if (REG_DEAD_DEBUGGING && dump_file)
3046 fprintf (dump_file, " regular looking at def ");
3047 df_ref_debug (def, dump_file);
3050 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3051 || bitmap_bit_p (live, dregno)
3052 || bitmap_bit_p (artificial_uses, dregno)
3053 || df_ignore_stack_reg (dregno)))
3055 rtx reg = (DF_REF_LOC (def))
3056 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3057 df_set_note (REG_UNUSED, insn, reg);
3058 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3059 if (REG_DEAD_DEBUGGING)
3060 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3063 return;
3067 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3068 info: lifetime, bb, and number of defs and uses for basic block
3069 BB. The three bitvectors are scratch regs used here. */
3071 static void
3072 df_note_bb_compute (unsigned int bb_index,
3073 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3075 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3076 rtx_insn *insn;
3077 df_ref def, use;
3078 struct dead_debug_local debug;
3080 dead_debug_local_init (&debug, NULL, NULL);
3082 bitmap_copy (live, df_get_live_out (bb));
3083 bitmap_clear (artificial_uses);
3085 if (REG_DEAD_DEBUGGING && dump_file)
3087 fprintf (dump_file, "live at bottom ");
3088 df_print_regset (dump_file, live);
3091 /* Process the artificial defs and uses at the bottom of the block
3092 to begin processing. */
3093 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3095 if (REG_DEAD_DEBUGGING && dump_file)
3096 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3098 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3099 bitmap_clear_bit (live, DF_REF_REGNO (def));
3102 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3103 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3105 unsigned int regno = DF_REF_REGNO (use);
3106 bitmap_set_bit (live, regno);
3108 /* Notes are not generated for any of the artificial registers
3109 at the bottom of the block. */
3110 bitmap_set_bit (artificial_uses, regno);
3113 if (REG_DEAD_DEBUGGING && dump_file)
3115 fprintf (dump_file, "live before artificials out ");
3116 df_print_regset (dump_file, live);
3119 FOR_BB_INSNS_REVERSE (bb, insn)
3121 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3122 df_mw_hardreg *mw;
3123 int debug_insn;
3125 if (!INSN_P (insn))
3126 continue;
3128 debug_insn = DEBUG_INSN_P (insn);
3130 bitmap_clear (do_not_gen);
3131 df_remove_dead_and_unused_notes (insn);
3133 /* Process the defs. */
3134 if (CALL_P (insn))
3136 if (REG_DEAD_DEBUGGING && dump_file)
3138 fprintf (dump_file, "processing call %d\n live =",
3139 INSN_UID (insn));
3140 df_print_regset (dump_file, live);
3143 /* We only care about real sets for calls. Clobbers cannot
3144 be depended on to really die. */
3145 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3146 if ((DF_MWS_REG_DEF_P (mw))
3147 && !df_ignore_stack_reg (mw->start_regno))
3148 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3149 artificial_uses, &debug);
3151 /* All of the defs except the return value are some sort of
3152 clobber. This code is for the return. */
3153 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3155 unsigned int dregno = DF_REF_REGNO (def);
3156 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3158 df_create_unused_note (insn,
3159 def, live, artificial_uses, &debug);
3160 bitmap_set_bit (do_not_gen, dregno);
3163 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3164 bitmap_clear_bit (live, dregno);
3167 else
3169 /* Regular insn. */
3170 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3171 if (DF_MWS_REG_DEF_P (mw))
3172 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3173 artificial_uses, &debug);
3175 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3177 unsigned int dregno = DF_REF_REGNO (def);
3178 df_create_unused_note (insn,
3179 def, live, artificial_uses, &debug);
3181 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3182 bitmap_set_bit (do_not_gen, dregno);
3184 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3185 bitmap_clear_bit (live, dregno);
3189 /* Process the uses. */
3190 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3191 if (DF_MWS_REG_USE_P (mw)
3192 && !df_ignore_stack_reg (mw->start_regno))
3194 bool really_add_notes = debug_insn != 0;
3196 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3197 artificial_uses,
3198 &really_add_notes);
3200 if (really_add_notes)
3201 debug_insn = -1;
3204 FOR_EACH_INSN_INFO_USE (use, insn_info)
3206 unsigned int uregno = DF_REF_REGNO (use);
3208 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3210 fprintf (dump_file, " regular looking at use ");
3211 df_ref_debug (use, dump_file);
3214 if (!bitmap_bit_p (live, uregno))
3216 if (debug_insn)
3218 if (debug_insn > 0)
3220 /* We won't add REG_UNUSED or REG_DEAD notes for
3221 these, so we don't have to mess with them in
3222 debug insns either. */
3223 if (!bitmap_bit_p (artificial_uses, uregno)
3224 && !df_ignore_stack_reg (uregno))
3225 dead_debug_add (&debug, use, uregno);
3226 continue;
3228 break;
3230 else
3231 dead_debug_insert_temp (&debug, uregno, insn,
3232 DEBUG_TEMP_BEFORE_WITH_REG);
3234 if ( (!(DF_REF_FLAGS (use)
3235 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3236 && (!bitmap_bit_p (do_not_gen, uregno))
3237 && (!bitmap_bit_p (artificial_uses, uregno))
3238 && (!df_ignore_stack_reg (uregno)))
3240 rtx reg = (DF_REF_LOC (use))
3241 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3242 df_set_note (REG_DEAD, insn, reg);
3244 if (REG_DEAD_DEBUGGING)
3245 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3247 /* This register is now live. */
3248 bitmap_set_bit (live, uregno);
3252 df_remove_dead_eq_notes (insn, live);
3254 if (debug_insn == -1)
3256 /* ??? We could probably do better here, replacing dead
3257 registers with their definitions. */
3258 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3259 df_insn_rescan_debug_internal (insn);
3263 dead_debug_local_finish (&debug, NULL);
3267 /* Compute register info: lifetime, bb, and number of defs and uses. */
3268 static void
3269 df_note_compute (bitmap all_blocks)
3271 unsigned int bb_index;
3272 bitmap_iterator bi;
3273 bitmap_head live, do_not_gen, artificial_uses;
3275 bitmap_initialize (&live, &df_bitmap_obstack);
3276 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3277 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3279 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3281 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3282 pseudos in debug insns because we don't always (re)visit blocks
3283 with death points after visiting dead uses. Even changing this
3284 loop to postorder would still leave room for visiting a death
3285 point before visiting a subsequent debug use. */
3286 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3289 bitmap_clear (&live);
3290 bitmap_clear (&do_not_gen);
3291 bitmap_clear (&artificial_uses);
3295 /* Free all storage associated with the problem. */
3297 static void
3298 df_note_free (void)
3300 free (df_note);
3304 /* All of the information associated every instance of the problem. */
3306 static struct df_problem problem_NOTE =
3308 DF_NOTE, /* Problem id. */
3309 DF_NONE, /* Direction. */
3310 df_note_alloc, /* Allocate the problem specific data. */
3311 NULL, /* Reset global information. */
3312 NULL, /* Free basic block info. */
3313 df_note_compute, /* Local compute function. */
3314 NULL, /* Init the solution specific data. */
3315 NULL, /* Iterative solver. */
3316 NULL, /* Confluence operator 0. */
3317 NULL, /* Confluence operator n. */
3318 NULL, /* Transfer function. */
3319 NULL, /* Finalize function. */
3320 df_note_free, /* Free all of the problem information. */
3321 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3322 NULL, /* Debugging. */
3323 NULL, /* Debugging start block. */
3324 NULL, /* Debugging end block. */
3325 NULL, /* Debugging start insn. */
3326 NULL, /* Debugging end insn. */
3327 NULL, /* Incremental solution verify start. */
3328 NULL, /* Incremental solution verify end. */
3329 &problem_LR, /* Dependent problem. */
3330 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3331 TV_DF_NOTE, /* Timing variable. */
3332 false /* Reset blocks on dropping out of blocks_to_analyze. */
3336 /* Create a new DATAFLOW instance and add it to an existing instance
3337 of DF. The returned structure is what is used to get at the
3338 solution. */
3340 void
3341 df_note_add_problem (void)
3343 df_add_problem (&problem_NOTE);
3349 /*----------------------------------------------------------------------------
3350 Functions for simulating the effects of single insns.
3352 You can either simulate in the forwards direction, starting from
3353 the top of a block or the backwards direction from the end of the
3354 block. If you go backwards, defs are examined first to clear bits,
3355 then uses are examined to set bits. If you go forwards, defs are
3356 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3357 are examined to clear bits. In either case, the result of examining
3358 a def can be undone (respectively by a use or a REG_UNUSED note).
3360 If you start at the top of the block, use one of DF_LIVE_IN or
3361 DF_LR_IN. If you start at the bottom of the block use one of
3362 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3363 THEY WILL BE DESTROYED.
3364 ----------------------------------------------------------------------------*/
3367 /* Find the set of DEFs for INSN. */
3369 void
3370 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3372 df_ref def;
3374 FOR_EACH_INSN_DEF (def, insn)
3375 bitmap_set_bit (defs, DF_REF_REGNO (def));
3378 /* Find the set of uses for INSN. This includes partial defs. */
3380 static void
3381 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3383 df_ref def, use;
3384 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3386 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3387 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3388 bitmap_set_bit (uses, DF_REF_REGNO (def));
3389 FOR_EACH_INSN_INFO_USE (use, insn_info)
3390 bitmap_set_bit (uses, DF_REF_REGNO (use));
3393 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3395 void
3396 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3398 df_ref def;
3400 FOR_EACH_INSN_DEF (def, insn)
3401 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3402 bitmap_set_bit (defs, DF_REF_REGNO (def));
3406 /* Simulate the effects of the defs of INSN on LIVE. */
3408 void
3409 df_simulate_defs (rtx_insn *insn, bitmap live)
3411 df_ref def;
3413 FOR_EACH_INSN_DEF (def, insn)
3415 unsigned int dregno = DF_REF_REGNO (def);
3417 /* If the def is to only part of the reg, it does
3418 not kill the other defs that reach here. */
3419 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3420 bitmap_clear_bit (live, dregno);
3425 /* Simulate the effects of the uses of INSN on LIVE. */
3427 void
3428 df_simulate_uses (rtx_insn *insn, bitmap live)
3430 df_ref use;
3432 if (DEBUG_INSN_P (insn))
3433 return;
3435 FOR_EACH_INSN_USE (use, insn)
3436 /* Add use to set of uses in this BB. */
3437 bitmap_set_bit (live, DF_REF_REGNO (use));
3441 /* Add back the always live regs in BB to LIVE. */
3443 static inline void
3444 df_simulate_fixup_sets (basic_block bb, bitmap live)
3446 /* These regs are considered always live so if they end up dying
3447 because of some def, we need to bring the back again. */
3448 if (bb_has_eh_pred (bb))
3449 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3450 else
3451 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3455 /*----------------------------------------------------------------------------
3456 The following three functions are used only for BACKWARDS scanning:
3457 i.e. they process the defs before the uses.
3459 df_simulate_initialize_backwards should be called first with a
3460 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3461 df_simulate_one_insn_backwards should be called for each insn in
3462 the block, starting with the last one. Finally,
3463 df_simulate_finalize_backwards can be called to get a new value
3464 of the sets at the top of the block (this is rarely used).
3465 ----------------------------------------------------------------------------*/
3467 /* Apply the artificial uses and defs at the end of BB in a backwards
3468 direction. */
3470 void
3471 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3473 df_ref def, use;
3474 int bb_index = bb->index;
3476 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3477 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3478 bitmap_clear_bit (live, DF_REF_REGNO (def));
3480 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3481 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3482 bitmap_set_bit (live, DF_REF_REGNO (use));
3486 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3488 void
3489 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3491 if (!NONDEBUG_INSN_P (insn))
3492 return;
3494 df_simulate_defs (insn, live);
3495 df_simulate_uses (insn, live);
3496 df_simulate_fixup_sets (bb, live);
3500 /* Apply the artificial uses and defs at the top of BB in a backwards
3501 direction. */
3503 void
3504 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3506 df_ref def;
3507 #ifdef EH_USES
3508 df_ref use;
3509 #endif
3510 int bb_index = bb->index;
3512 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3513 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3514 bitmap_clear_bit (live, DF_REF_REGNO (def));
3516 #ifdef EH_USES
3517 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3518 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3519 bitmap_set_bit (live, DF_REF_REGNO (use));
3520 #endif
3522 /*----------------------------------------------------------------------------
3523 The following three functions are used only for FORWARDS scanning:
3524 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3525 Thus it is important to add the DF_NOTES problem to the stack of
3526 problems computed before using these functions.
3528 df_simulate_initialize_forwards should be called first with a
3529 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3530 df_simulate_one_insn_forwards should be called for each insn in
3531 the block, starting with the first one.
3532 ----------------------------------------------------------------------------*/
3534 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3535 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3536 defs live. */
3538 void
3539 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3541 df_ref def;
3542 int bb_index = bb->index;
3544 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3545 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3546 bitmap_set_bit (live, DF_REF_REGNO (def));
3549 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3551 void
3552 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3554 rtx link;
3555 if (! INSN_P (insn))
3556 return;
3558 /* Make sure that DF_NOTE really is an active df problem. */
3559 gcc_assert (df_note);
3561 /* Note that this is the opposite as how the problem is defined, because
3562 in the LR problem defs _kill_ liveness. However, they do so backwards,
3563 while here the scan is performed forwards! So, first assume that the
3564 def is live, and if this is not true REG_UNUSED notes will rectify the
3565 situation. */
3566 df_simulate_find_noclobber_defs (insn, live);
3568 /* Clear all of the registers that go dead. */
3569 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3571 switch (REG_NOTE_KIND (link))
3573 case REG_DEAD:
3574 case REG_UNUSED:
3576 rtx reg = XEXP (link, 0);
3577 int regno = REGNO (reg);
3578 if (HARD_REGISTER_NUM_P (regno))
3579 bitmap_clear_range (live, regno,
3580 hard_regno_nregs[regno][GET_MODE (reg)]);
3581 else
3582 bitmap_clear_bit (live, regno);
3584 break;
3585 default:
3586 break;
3589 df_simulate_fixup_sets (bb, live);
3592 /* Used by the next two functions to encode information about the
3593 memory references we found. */
3594 #define MEMREF_NORMAL 1
3595 #define MEMREF_VOLATILE 2
3597 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3599 static int
3600 find_memory (rtx insn)
3602 int flags = 0;
3603 subrtx_iterator::array_type array;
3604 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3606 const_rtx x = *iter;
3607 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3608 flags |= MEMREF_VOLATILE;
3609 else if (MEM_P (x))
3611 if (MEM_VOLATILE_P (x))
3612 flags |= MEMREF_VOLATILE;
3613 else if (!MEM_READONLY_P (x))
3614 flags |= MEMREF_NORMAL;
3617 return flags;
3620 /* A subroutine of can_move_insns_across_p called through note_stores.
3621 DATA points to an integer in which we set either the bit for
3622 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3623 of either kind. */
3625 static void
3626 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
3627 void *data ATTRIBUTE_UNUSED)
3629 int *pflags = (int *)data;
3630 if (GET_CODE (x) == SUBREG)
3631 x = XEXP (x, 0);
3632 /* Treat stores to SP as stores to memory, this will prevent problems
3633 when there are references to the stack frame. */
3634 if (x == stack_pointer_rtx)
3635 *pflags |= MEMREF_VOLATILE;
3636 if (!MEM_P (x))
3637 return;
3638 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
3641 /* Scan BB backwards, using df_simulate functions to keep track of
3642 lifetimes, up to insn POINT. The result is stored in LIVE. */
3644 void
3645 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
3647 rtx_insn *insn;
3648 bitmap_copy (live, df_get_live_out (bb));
3649 df_simulate_initialize_backwards (bb, live);
3651 /* Scan and update life information until we reach the point we're
3652 interested in. */
3653 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
3654 df_simulate_one_insn_backwards (bb, insn, live);
3657 /* Return true if it is safe to move a group of insns, described by
3658 the range FROM to TO, backwards across another group of insns,
3659 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
3660 are no insns between ACROSS_TO and FROM, but they may be in
3661 different basic blocks; MERGE_BB is the block from which the
3662 insns will be moved. The caller must pass in a regset MERGE_LIVE
3663 which specifies the registers live after TO.
3665 This function may be called in one of two cases: either we try to
3666 move identical instructions from all successor blocks into their
3667 predecessor, or we try to move from only one successor block. If
3668 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
3669 the second case. It should contain a set of registers live at the
3670 end of ACROSS_TO which must not be clobbered by moving the insns.
3671 In that case, we're also more careful about moving memory references
3672 and trapping insns.
3674 We return false if it is not safe to move the entire group, but it
3675 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
3676 is set to point at the last moveable insn in such a case. */
3678 bool
3679 can_move_insns_across (rtx_insn *from, rtx_insn *to,
3680 rtx_insn *across_from, rtx_insn *across_to,
3681 basic_block merge_bb, regset merge_live,
3682 regset other_branch_live, rtx_insn **pmove_upto)
3684 rtx_insn *insn, *next, *max_to;
3685 bitmap merge_set, merge_use, local_merge_live;
3686 bitmap test_set, test_use;
3687 unsigned i, fail = 0;
3688 bitmap_iterator bi;
3689 int memrefs_in_across = 0;
3690 int mem_sets_in_across = 0;
3691 bool trapping_insns_in_across = false;
3693 if (pmove_upto != NULL)
3694 *pmove_upto = NULL;
3696 /* Find real bounds, ignoring debug insns. */
3697 while (!NONDEBUG_INSN_P (from) && from != to)
3698 from = NEXT_INSN (from);
3699 while (!NONDEBUG_INSN_P (to) && from != to)
3700 to = PREV_INSN (to);
3702 for (insn = across_to; ; insn = next)
3704 if (CALL_P (insn))
3706 if (RTL_CONST_OR_PURE_CALL_P (insn))
3707 /* Pure functions can read from memory. Const functions can
3708 read from arguments that the ABI has forced onto the stack.
3709 Neither sort of read can be volatile. */
3710 memrefs_in_across |= MEMREF_NORMAL;
3711 else
3713 memrefs_in_across |= MEMREF_VOLATILE;
3714 mem_sets_in_across |= MEMREF_VOLATILE;
3717 if (NONDEBUG_INSN_P (insn))
3719 if (volatile_insn_p (PATTERN (insn)))
3720 return false;
3721 memrefs_in_across |= find_memory (insn);
3722 note_stores (PATTERN (insn), find_memory_stores,
3723 &mem_sets_in_across);
3724 /* This is used just to find sets of the stack pointer. */
3725 memrefs_in_across |= mem_sets_in_across;
3726 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
3728 next = PREV_INSN (insn);
3729 if (insn == across_from)
3730 break;
3733 /* Collect:
3734 MERGE_SET = set of registers set in MERGE_BB
3735 MERGE_USE = set of registers used in MERGE_BB and live at its top
3736 MERGE_LIVE = set of registers live at the point inside the MERGE
3737 range that we've reached during scanning
3738 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
3739 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
3740 and live before ACROSS_FROM. */
3742 merge_set = BITMAP_ALLOC (&reg_obstack);
3743 merge_use = BITMAP_ALLOC (&reg_obstack);
3744 local_merge_live = BITMAP_ALLOC (&reg_obstack);
3745 test_set = BITMAP_ALLOC (&reg_obstack);
3746 test_use = BITMAP_ALLOC (&reg_obstack);
3748 /* Compute the set of registers set and used in the ACROSS range. */
3749 if (other_branch_live != NULL)
3750 bitmap_copy (test_use, other_branch_live);
3751 df_simulate_initialize_backwards (merge_bb, test_use);
3752 for (insn = across_to; ; insn = next)
3754 if (NONDEBUG_INSN_P (insn))
3756 df_simulate_find_defs (insn, test_set);
3757 df_simulate_defs (insn, test_use);
3758 df_simulate_uses (insn, test_use);
3760 next = PREV_INSN (insn);
3761 if (insn == across_from)
3762 break;
3765 /* Compute an upper bound for the amount of insns moved, by finding
3766 the first insn in MERGE that sets a register in TEST_USE, or uses
3767 a register in TEST_SET. We also check for calls, trapping operations,
3768 and memory references. */
3769 max_to = NULL;
3770 for (insn = from; ; insn = next)
3772 if (CALL_P (insn))
3773 break;
3774 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
3775 break;
3776 if (NONDEBUG_INSN_P (insn))
3778 if (may_trap_or_fault_p (PATTERN (insn))
3779 && (trapping_insns_in_across
3780 || other_branch_live != NULL
3781 || volatile_insn_p (PATTERN (insn))))
3782 break;
3784 /* We cannot move memory stores past each other, or move memory
3785 reads past stores, at least not without tracking them and
3786 calling true_dependence on every pair.
3788 If there is no other branch and no memory references or
3789 sets in the ACROSS range, we can move memory references
3790 freely, even volatile ones.
3792 Otherwise, the rules are as follows: volatile memory
3793 references and stores can't be moved at all, and any type
3794 of memory reference can't be moved if there are volatile
3795 accesses or stores in the ACROSS range. That leaves
3796 normal reads, which can be moved, as the trapping case is
3797 dealt with elsewhere. */
3798 if (other_branch_live != NULL || memrefs_in_across != 0)
3800 int mem_ref_flags = 0;
3801 int mem_set_flags = 0;
3802 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
3803 mem_ref_flags = find_memory (insn);
3804 /* Catch sets of the stack pointer. */
3805 mem_ref_flags |= mem_set_flags;
3807 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
3808 break;
3809 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
3810 break;
3811 if (mem_set_flags != 0
3812 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
3813 break;
3815 df_simulate_find_uses (insn, merge_use);
3816 /* We're only interested in uses which use a value live at
3817 the top, not one previously set in this block. */
3818 bitmap_and_compl_into (merge_use, merge_set);
3819 df_simulate_find_defs (insn, merge_set);
3820 if (bitmap_intersect_p (merge_set, test_use)
3821 || bitmap_intersect_p (merge_use, test_set))
3822 break;
3823 #ifdef HAVE_cc0
3824 if (!sets_cc0_p (insn))
3825 #endif
3826 max_to = insn;
3828 next = NEXT_INSN (insn);
3829 if (insn == to)
3830 break;
3832 if (max_to != to)
3833 fail = 1;
3835 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
3836 goto out;
3838 /* Now, lower this upper bound by also taking into account that
3839 a range of insns moved across ACROSS must not leave a register
3840 live at the end that will be clobbered in ACROSS. We need to
3841 find a point where TEST_SET & LIVE == 0.
3843 Insns in the MERGE range that set registers which are also set
3844 in the ACROSS range may still be moved as long as we also move
3845 later insns which use the results of the set, and make the
3846 register dead again. This is verified by the condition stated
3847 above. We only need to test it for registers that are set in
3848 the moved region.
3850 MERGE_LIVE is provided by the caller and holds live registers after
3851 TO. */
3852 bitmap_copy (local_merge_live, merge_live);
3853 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
3854 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
3856 /* We're not interested in registers that aren't set in the moved
3857 region at all. */
3858 bitmap_and_into (local_merge_live, merge_set);
3859 for (;;)
3861 if (NONDEBUG_INSN_P (insn))
3863 if (!bitmap_intersect_p (test_set, local_merge_live)
3864 #ifdef HAVE_cc0
3865 && !sets_cc0_p (insn)
3866 #endif
3869 max_to = insn;
3870 break;
3873 df_simulate_one_insn_backwards (merge_bb, insn,
3874 local_merge_live);
3876 if (insn == from)
3878 fail = 1;
3879 goto out;
3881 insn = PREV_INSN (insn);
3884 if (max_to != to)
3885 fail = 1;
3887 if (pmove_upto)
3888 *pmove_upto = max_to;
3890 /* For small register class machines, don't lengthen lifetimes of
3891 hard registers before reload. */
3892 if (! reload_completed
3893 && targetm.small_register_classes_for_mode_p (VOIDmode))
3895 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
3897 if (i < FIRST_PSEUDO_REGISTER
3898 && ! fixed_regs[i]
3899 && ! global_regs[i])
3901 fail = 1;
3902 break;
3907 out:
3908 BITMAP_FREE (merge_set);
3909 BITMAP_FREE (merge_use);
3910 BITMAP_FREE (local_merge_live);
3911 BITMAP_FREE (test_set);
3912 BITMAP_FREE (test_use);
3914 return !fail;
3918 /*----------------------------------------------------------------------------
3919 MULTIPLE DEFINITIONS
3921 Find the locations in the function reached by multiple definition sites
3922 for a live pseudo. In and out bitvectors are built for each basic
3923 block. They are restricted for efficiency to live registers.
3925 The gen and kill sets for the problem are obvious. Together they
3926 include all defined registers in a basic block; the gen set includes
3927 registers where a partial or conditional or may-clobber definition is
3928 last in the BB, while the kill set includes registers with a complete
3929 definition coming last. However, the computation of the dataflow
3930 itself is interesting.
3932 The idea behind it comes from SSA form's iterated dominance frontier
3933 criterion for inserting PHI functions. Just like in that case, we can use
3934 the dominance frontier to find places where multiple definitions meet;
3935 a register X defined in a basic block BB1 has multiple definitions in
3936 basic blocks in BB1's dominance frontier.
3938 So, the in-set of a basic block BB2 is not just the union of the
3939 out-sets of BB2's predecessors, but includes some more bits that come
3940 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
3941 the previous paragraph). I called this set the init-set of BB2.
3943 (Note: I actually use the kill-set only to build the init-set.
3944 gen bits are anyway propagated from BB1 to BB2 by dataflow).
3946 For example, if you have
3948 BB1 : r10 = 0
3949 r11 = 0
3950 if <...> goto BB2 else goto BB3;
3952 BB2 : r10 = 1
3953 r12 = 1
3954 goto BB3;
3956 BB3 :
3958 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
3959 init-set of BB3 includes r10 and r12, but not r11. Note that we do
3960 not need to iterate the dominance frontier, because we do not insert
3961 anything like PHI functions there! Instead, dataflow will take care of
3962 propagating the information to BB3's successors.
3963 ---------------------------------------------------------------------------*/
3965 /* Private data used to verify the solution for this problem. */
3966 struct df_md_problem_data
3968 /* An obstack for the bitmaps we need for this problem. */
3969 bitmap_obstack md_bitmaps;
3972 /* Scratch var used by transfer functions. This is used to do md analysis
3973 only for live registers. */
3974 static bitmap_head df_md_scratch;
3977 static void
3978 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
3979 void *vbb_info)
3981 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
3982 if (bb_info)
3984 bitmap_clear (&bb_info->kill);
3985 bitmap_clear (&bb_info->gen);
3986 bitmap_clear (&bb_info->init);
3987 bitmap_clear (&bb_info->in);
3988 bitmap_clear (&bb_info->out);
3993 /* Allocate or reset bitmaps for DF_MD. The solution bits are
3994 not touched unless the block is new. */
3996 static void
3997 df_md_alloc (bitmap all_blocks)
3999 unsigned int bb_index;
4000 bitmap_iterator bi;
4001 struct df_md_problem_data *problem_data;
4003 df_grow_bb_info (df_md);
4004 if (df_md->problem_data)
4005 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4006 else
4008 problem_data = XNEW (struct df_md_problem_data);
4009 df_md->problem_data = problem_data;
4010 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4012 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4014 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4016 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4017 /* When bitmaps are already initialized, just clear them. */
4018 if (bb_info->init.obstack)
4020 bitmap_clear (&bb_info->init);
4021 bitmap_clear (&bb_info->gen);
4022 bitmap_clear (&bb_info->kill);
4023 bitmap_clear (&bb_info->in);
4024 bitmap_clear (&bb_info->out);
4026 else
4028 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4029 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4030 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4031 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4032 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4036 df_md->optional_p = true;
4039 /* Add the effect of the top artificial defs of BB to the multiple definitions
4040 bitmap LOCAL_MD. */
4042 void
4043 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4045 int bb_index = bb->index;
4046 df_ref def;
4047 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4048 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4050 unsigned int dregno = DF_REF_REGNO (def);
4051 if (DF_REF_FLAGS (def)
4052 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4053 bitmap_set_bit (local_md, dregno);
4054 else
4055 bitmap_clear_bit (local_md, dregno);
4060 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4061 LOCAL_MD. */
4063 void
4064 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4065 bitmap local_md)
4067 df_ref def;
4069 FOR_EACH_INSN_DEF (def, insn)
4071 unsigned int dregno = DF_REF_REGNO (def);
4072 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4073 || (dregno >= FIRST_PSEUDO_REGISTER))
4075 if (DF_REF_FLAGS (def)
4076 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4077 bitmap_set_bit (local_md, DF_REF_ID (def));
4078 else
4079 bitmap_clear_bit (local_md, DF_REF_ID (def));
4084 static void
4085 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4086 df_ref def,
4087 int top_flag)
4089 bitmap_clear (&seen_in_insn);
4091 for (; def; def = DF_REF_NEXT_LOC (def))
4093 unsigned int dregno = DF_REF_REGNO (def);
4094 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4095 || (dregno >= FIRST_PSEUDO_REGISTER))
4096 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4098 if (!bitmap_bit_p (&seen_in_insn, dregno))
4100 if (DF_REF_FLAGS (def)
4101 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4103 bitmap_set_bit (&bb_info->gen, dregno);
4104 bitmap_clear_bit (&bb_info->kill, dregno);
4106 else
4108 /* When we find a clobber and a regular def,
4109 make sure the regular def wins. */
4110 bitmap_set_bit (&seen_in_insn, dregno);
4111 bitmap_set_bit (&bb_info->kill, dregno);
4112 bitmap_clear_bit (&bb_info->gen, dregno);
4120 /* Compute local multiple def info for basic block BB. */
4122 static void
4123 df_md_bb_local_compute (unsigned int bb_index)
4125 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4126 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4127 rtx_insn *insn;
4129 /* Artificials are only hard regs. */
4130 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4131 df_md_bb_local_compute_process_def (bb_info,
4132 df_get_artificial_defs (bb_index),
4133 DF_REF_AT_TOP);
4135 FOR_BB_INSNS (bb, insn)
4137 unsigned int uid = INSN_UID (insn);
4138 if (!INSN_P (insn))
4139 continue;
4141 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4144 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4145 df_md_bb_local_compute_process_def (bb_info,
4146 df_get_artificial_defs (bb_index),
4150 /* Compute local reaching def info for each basic block within BLOCKS. */
4152 static void
4153 df_md_local_compute (bitmap all_blocks)
4155 unsigned int bb_index, df_bb_index;
4156 bitmap_iterator bi1, bi2;
4157 basic_block bb;
4158 bitmap_head *frontiers;
4160 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4162 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4164 df_md_bb_local_compute (bb_index);
4167 bitmap_clear (&seen_in_insn);
4169 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4170 FOR_ALL_BB_FN (bb, cfun)
4171 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4173 compute_dominance_frontiers (frontiers);
4175 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4176 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4178 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4179 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4181 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4182 if (bitmap_bit_p (all_blocks, df_bb_index))
4183 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4184 df_get_live_in (bb));
4188 FOR_ALL_BB_FN (bb, cfun)
4189 bitmap_clear (&frontiers[bb->index]);
4190 free (frontiers);
4194 /* Reset the global solution for recalculation. */
4196 static void
4197 df_md_reset (bitmap all_blocks)
4199 unsigned int bb_index;
4200 bitmap_iterator bi;
4202 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4204 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4205 gcc_assert (bb_info);
4206 bitmap_clear (&bb_info->in);
4207 bitmap_clear (&bb_info->out);
4211 static bool
4212 df_md_transfer_function (int bb_index)
4214 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4215 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4216 bitmap in = &bb_info->in;
4217 bitmap out = &bb_info->out;
4218 bitmap gen = &bb_info->gen;
4219 bitmap kill = &bb_info->kill;
4221 /* We need to use a scratch set here so that the value returned from this
4222 function invocation properly reflects whether the sets changed in a
4223 significant way; i.e. not just because the live set was anded in. */
4224 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4226 /* Multiple definitions of a register are not relevant if it is not
4227 live. Thus we trim the result to the places where it is live. */
4228 bitmap_and_into (in, df_get_live_in (bb));
4230 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4233 /* Initialize the solution bit vectors for problem. */
4235 static void
4236 df_md_init (bitmap all_blocks)
4238 unsigned int bb_index;
4239 bitmap_iterator bi;
4241 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4243 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4245 bitmap_copy (&bb_info->in, &bb_info->init);
4246 df_md_transfer_function (bb_index);
4250 static void
4251 df_md_confluence_0 (basic_block bb)
4253 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4254 bitmap_copy (&bb_info->in, &bb_info->init);
4257 /* In of target gets or of out of source. */
4259 static bool
4260 df_md_confluence_n (edge e)
4262 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4263 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4265 if (e->flags & EDGE_FAKE)
4266 return false;
4268 if (e->flags & EDGE_EH)
4269 return bitmap_ior_and_compl_into (op1, op2,
4270 regs_invalidated_by_call_regset);
4271 else
4272 return bitmap_ior_into (op1, op2);
4275 /* Free all storage associated with the problem. */
4277 static void
4278 df_md_free (void)
4280 struct df_md_problem_data *problem_data
4281 = (struct df_md_problem_data *) df_md->problem_data;
4283 bitmap_obstack_release (&problem_data->md_bitmaps);
4284 free (problem_data);
4285 df_md->problem_data = NULL;
4287 df_md->block_info_size = 0;
4288 free (df_md->block_info);
4289 df_md->block_info = NULL;
4290 free (df_md);
4294 /* Debugging info at top of bb. */
4296 static void
4297 df_md_top_dump (basic_block bb, FILE *file)
4299 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4300 if (!bb_info)
4301 return;
4303 fprintf (file, ";; md in \t");
4304 df_print_regset (file, &bb_info->in);
4305 fprintf (file, ";; md init \t");
4306 df_print_regset (file, &bb_info->init);
4307 fprintf (file, ";; md gen \t");
4308 df_print_regset (file, &bb_info->gen);
4309 fprintf (file, ";; md kill \t");
4310 df_print_regset (file, &bb_info->kill);
4313 /* Debugging info at bottom of bb. */
4315 static void
4316 df_md_bottom_dump (basic_block bb, FILE *file)
4318 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4319 if (!bb_info)
4320 return;
4322 fprintf (file, ";; md out \t");
4323 df_print_regset (file, &bb_info->out);
4326 static struct df_problem problem_MD =
4328 DF_MD, /* Problem id. */
4329 DF_FORWARD, /* Direction. */
4330 df_md_alloc, /* Allocate the problem specific data. */
4331 df_md_reset, /* Reset global information. */
4332 df_md_free_bb_info, /* Free basic block info. */
4333 df_md_local_compute, /* Local compute function. */
4334 df_md_init, /* Init the solution specific data. */
4335 df_worklist_dataflow, /* Worklist solver. */
4336 df_md_confluence_0, /* Confluence operator 0. */
4337 df_md_confluence_n, /* Confluence operator n. */
4338 df_md_transfer_function, /* Transfer function. */
4339 NULL, /* Finalize function. */
4340 df_md_free, /* Free all of the problem information. */
4341 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4342 NULL, /* Debugging. */
4343 df_md_top_dump, /* Debugging start block. */
4344 df_md_bottom_dump, /* Debugging end block. */
4345 NULL, /* Debugging start insn. */
4346 NULL, /* Debugging end insn. */
4347 NULL, /* Incremental solution verify start. */
4348 NULL, /* Incremental solution verify end. */
4349 NULL, /* Dependent problem. */
4350 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */
4351 TV_DF_MD, /* Timing variable. */
4352 false /* Reset blocks on dropping out of blocks_to_analyze. */
4355 /* Create a new MD instance and add it to the existing instance
4356 of DF. */
4358 void
4359 df_md_add_problem (void)
4361 df_add_problem (&problem_MD);