20180-12-08 Steven G. Kargl <kargl@gcc.gnu.org>
[official-gcc.git] / gcc / df-problems.c
blobccab9a96bd74ab3b9d312e2d45cdfc80ebc3cc1a
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2018 Free Software Foundation, Inc.
3 Originally contributed by Michael P. Hayes
4 (m.hayes@elec.canterbury.ac.nz, mhayes@redhat.com)
5 Major rewrite contributed by Danny Berlin (dberlin@dberlin.org)
6 and Kenneth Zadeck (zadeck@naturalbridge.com).
8 This file is part of GCC.
10 GCC is free software; you can redistribute it and/or modify it under
11 the terms of the GNU General Public License as published by the Free
12 Software Foundation; either version 3, or (at your option) any later
13 version.
15 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16 WARRANTY; without even the implied warranty of MERCHANTABILITY or
17 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 for more details.
20 You should have received a copy of the GNU General Public License
21 along with GCC; see the file COPYING3. If not see
22 <http://www.gnu.org/licenses/>. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "backend.h"
28 #include "target.h"
29 #include "rtl.h"
30 #include "df.h"
31 #include "memmodel.h"
32 #include "tm_p.h"
33 #include "insn-config.h"
34 #include "cfganal.h"
35 #include "dce.h"
36 #include "valtrack.h"
37 #include "dumpfile.h"
38 #include "rtl-iter.h"
40 /* Note that turning REG_DEAD_DEBUGGING on will cause
41 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
42 addresses in the dumps. */
43 #define REG_DEAD_DEBUGGING 0
45 #define DF_SPARSE_THRESHOLD 32
47 static bitmap_head seen_in_block;
48 static bitmap_head seen_in_insn;
50 /*----------------------------------------------------------------------------
51 Utility functions.
52 ----------------------------------------------------------------------------*/
54 /* Generic versions to get the void* version of the block info. Only
55 used inside the problem instance vectors. */
57 /* Dump a def-use or use-def chain for REF to FILE. */
59 void
60 df_chain_dump (struct df_link *link, FILE *file)
62 fprintf (file, "{ ");
63 for (; link; link = link->next)
65 fprintf (file, "%c%d(bb %d insn %d) ",
66 DF_REF_REG_DEF_P (link->ref)
67 ? 'd'
68 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
69 DF_REF_ID (link->ref),
70 DF_REF_BBNO (link->ref),
71 DF_REF_IS_ARTIFICIAL (link->ref)
72 ? -1 : DF_REF_INSN_UID (link->ref));
74 fprintf (file, "}");
78 /* Print some basic block info as part of df_dump. */
80 void
81 df_print_bb_index (basic_block bb, FILE *file)
83 edge e;
84 edge_iterator ei;
86 fprintf (file, "\n( ");
87 FOR_EACH_EDGE (e, ei, bb->preds)
89 basic_block pred = e->src;
90 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
92 fprintf (file, ")->[%d]->( ", bb->index);
93 FOR_EACH_EDGE (e, ei, bb->succs)
95 basic_block succ = e->dest;
96 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
98 fprintf (file, ")\n");
102 /*----------------------------------------------------------------------------
103 REACHING DEFINITIONS
105 Find the locations in the function where each definition site for a
106 pseudo reaches. In and out bitvectors are built for each basic
107 block. The id field in the ref is used to index into these sets.
108 See df.h for details.
110 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
111 existing uses are included in the global reaching DEFs set, or in other
112 words only DEFs that are still live. This is a kind of pruned version
113 of the traditional reaching definitions problem that is much less
114 complex to compute and produces enough information to compute UD-chains.
115 In this context, live must be interpreted in the DF_LR sense: Uses that
116 are upward exposed but maybe not initialized on all paths through the
117 CFG. For a USE that is not reached by a DEF on all paths, we still want
118 to make those DEFs that do reach the USE visible, and pruning based on
119 DF_LIVE would make that impossible.
120 ----------------------------------------------------------------------------*/
122 /* This problem plays a large number of games for the sake of
123 efficiency.
125 1) The order of the bits in the bitvectors. After the scanning
126 phase, all of the defs are sorted. All of the defs for the reg 0
127 are first, followed by all defs for reg 1 and so on.
129 2) There are two kill sets, one if the number of defs is less or
130 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
131 greater.
133 <= : Data is built directly in the kill set.
135 > : One level of indirection is used to keep from generating long
136 strings of 1 bits in the kill sets. Bitvectors that are indexed
137 by the regnum are used to represent that there is a killing def
138 for the register. The confluence and transfer functions use
139 these along with the bitmap_clear_range call to remove ranges of
140 bits without actually generating a knockout vector.
142 The kill and sparse_kill and the dense_invalidated_by_call and
143 sparse_invalidated_by_call both play this game. */
145 /* Private data used to compute the solution for this problem. These
146 data structures are not accessible outside of this module. */
147 struct df_rd_problem_data
149 /* The set of defs to regs invalidated by call. */
150 bitmap_head sparse_invalidated_by_call;
151 /* The set of defs to regs invalidate by call for rd. */
152 bitmap_head dense_invalidated_by_call;
153 /* An obstack for the bitmaps we need for this problem. */
154 bitmap_obstack rd_bitmaps;
158 /* Free basic block info. */
160 static void
161 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
162 void *vbb_info)
164 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
165 if (bb_info)
167 bitmap_clear (&bb_info->kill);
168 bitmap_clear (&bb_info->sparse_kill);
169 bitmap_clear (&bb_info->gen);
170 bitmap_clear (&bb_info->in);
171 bitmap_clear (&bb_info->out);
176 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
177 not touched unless the block is new. */
179 static void
180 df_rd_alloc (bitmap all_blocks)
182 unsigned int bb_index;
183 bitmap_iterator bi;
184 struct df_rd_problem_data *problem_data;
186 if (df_rd->problem_data)
188 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
189 bitmap_clear (&problem_data->sparse_invalidated_by_call);
190 bitmap_clear (&problem_data->dense_invalidated_by_call);
192 else
194 problem_data = XNEW (struct df_rd_problem_data);
195 df_rd->problem_data = problem_data;
197 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
198 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
199 &problem_data->rd_bitmaps);
200 bitmap_initialize (&problem_data->dense_invalidated_by_call,
201 &problem_data->rd_bitmaps);
204 df_grow_bb_info (df_rd);
206 /* Because of the clustering of all use sites for the same pseudo,
207 we have to process all of the blocks before doing the analysis. */
209 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
211 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
213 /* When bitmaps are already initialized, just clear them. */
214 if (bb_info->kill.obstack)
216 bitmap_clear (&bb_info->kill);
217 bitmap_clear (&bb_info->sparse_kill);
218 bitmap_clear (&bb_info->gen);
220 else
222 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
223 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
224 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
225 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
226 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
229 df_rd->optional_p = true;
233 /* Add the effect of the top artificial defs of BB to the reaching definitions
234 bitmap LOCAL_RD. */
236 void
237 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
239 int bb_index = bb->index;
240 df_ref def;
241 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
242 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
244 unsigned int dregno = DF_REF_REGNO (def);
245 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
246 bitmap_clear_range (local_rd,
247 DF_DEFS_BEGIN (dregno),
248 DF_DEFS_COUNT (dregno));
249 bitmap_set_bit (local_rd, DF_REF_ID (def));
253 /* Add the effect of the defs of INSN to the reaching definitions bitmap
254 LOCAL_RD. */
256 void
257 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
258 bitmap local_rd)
260 df_ref def;
262 FOR_EACH_INSN_DEF (def, insn)
264 unsigned int dregno = DF_REF_REGNO (def);
265 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
266 || (dregno >= FIRST_PSEUDO_REGISTER))
268 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
269 bitmap_clear_range (local_rd,
270 DF_DEFS_BEGIN (dregno),
271 DF_DEFS_COUNT (dregno));
272 if (!(DF_REF_FLAGS (def)
273 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
274 bitmap_set_bit (local_rd, DF_REF_ID (def));
279 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
280 more complicated than just simulating, because we must produce the
281 gen and kill sets and hence deal with the two possible representations
282 of kill sets. */
284 static void
285 df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
286 df_ref def,
287 int top_flag)
289 for (; def; def = DF_REF_NEXT_LOC (def))
291 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
293 unsigned int regno = DF_REF_REGNO (def);
294 unsigned int begin = DF_DEFS_BEGIN (regno);
295 unsigned int n_defs = DF_DEFS_COUNT (regno);
297 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
298 || (regno >= FIRST_PSEUDO_REGISTER))
300 /* Only the last def(s) for a regno in the block has any
301 effect. */
302 if (!bitmap_bit_p (&seen_in_block, regno))
304 /* The first def for regno in insn gets to knock out the
305 defs from other instructions. */
306 if ((!bitmap_bit_p (&seen_in_insn, regno))
307 /* If the def is to only part of the reg, it does
308 not kill the other defs that reach here. */
309 && (!(DF_REF_FLAGS (def) &
310 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
312 if (n_defs > DF_SPARSE_THRESHOLD)
314 bitmap_set_bit (&bb_info->sparse_kill, regno);
315 bitmap_clear_range (&bb_info->gen, begin, n_defs);
317 else
319 bitmap_set_range (&bb_info->kill, begin, n_defs);
320 bitmap_clear_range (&bb_info->gen, begin, n_defs);
324 bitmap_set_bit (&seen_in_insn, regno);
325 /* All defs for regno in the instruction may be put into
326 the gen set. */
327 if (!(DF_REF_FLAGS (def)
328 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
329 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
336 /* Compute local reaching def info for basic block BB. */
338 static void
339 df_rd_bb_local_compute (unsigned int bb_index)
341 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
342 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
343 rtx_insn *insn;
345 bitmap_clear (&seen_in_block);
346 bitmap_clear (&seen_in_insn);
348 /* Artificials are only hard regs. */
349 if (!(df->changeable_flags & DF_NO_HARD_REGS))
350 df_rd_bb_local_compute_process_def (bb_info,
351 df_get_artificial_defs (bb_index),
354 FOR_BB_INSNS_REVERSE (bb, insn)
356 unsigned int uid = INSN_UID (insn);
358 if (!INSN_P (insn))
359 continue;
361 df_rd_bb_local_compute_process_def (bb_info,
362 DF_INSN_UID_DEFS (uid), 0);
364 /* This complex dance with the two bitmaps is required because
365 instructions can assign twice to the same pseudo. This
366 generally happens with calls that will have one def for the
367 result and another def for the clobber. If only one vector
368 is used and the clobber goes first, the result will be
369 lost. */
370 bitmap_ior_into (&seen_in_block, &seen_in_insn);
371 bitmap_clear (&seen_in_insn);
374 /* Process the artificial defs at the top of the block last since we
375 are going backwards through the block and these are logically at
376 the start. */
377 if (!(df->changeable_flags & DF_NO_HARD_REGS))
378 df_rd_bb_local_compute_process_def (bb_info,
379 df_get_artificial_defs (bb_index),
380 DF_REF_AT_TOP);
384 /* Compute local reaching def info for each basic block within BLOCKS. */
386 static void
387 df_rd_local_compute (bitmap all_blocks)
389 unsigned int bb_index;
390 bitmap_iterator bi;
391 unsigned int regno;
392 struct df_rd_problem_data *problem_data
393 = (struct df_rd_problem_data *) df_rd->problem_data;
394 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
395 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
397 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
398 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
400 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
402 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
404 df_rd_bb_local_compute (bb_index);
407 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
408 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
410 if (! HARD_REGISTER_NUM_P (regno)
411 || !(df->changeable_flags & DF_NO_HARD_REGS))
413 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
414 bitmap_set_bit (sparse_invalidated, regno);
415 else
416 bitmap_set_range (dense_invalidated,
417 DF_DEFS_BEGIN (regno),
418 DF_DEFS_COUNT (regno));
422 bitmap_release (&seen_in_block);
423 bitmap_release (&seen_in_insn);
427 /* Initialize the solution bit vectors for problem. */
429 static void
430 df_rd_init_solution (bitmap all_blocks)
432 unsigned int bb_index;
433 bitmap_iterator bi;
435 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
437 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
439 bitmap_copy (&bb_info->out, &bb_info->gen);
440 bitmap_clear (&bb_info->in);
444 /* In of target gets or of out of source. */
446 static bool
447 df_rd_confluence_n (edge e)
449 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
450 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
451 bool changed = false;
453 if (e->flags & EDGE_FAKE)
454 return false;
456 if (e->flags & EDGE_EH)
458 struct df_rd_problem_data *problem_data
459 = (struct df_rd_problem_data *) df_rd->problem_data;
460 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
461 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
462 bitmap_iterator bi;
463 unsigned int regno;
465 auto_bitmap tmp (&df_bitmap_obstack);
466 bitmap_and_compl (tmp, op2, dense_invalidated);
468 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
470 bitmap_clear_range (tmp,
471 DF_DEFS_BEGIN (regno),
472 DF_DEFS_COUNT (regno));
474 changed |= bitmap_ior_into (op1, tmp);
475 return changed;
477 else
478 return bitmap_ior_into (op1, op2);
482 /* Transfer function. */
484 static bool
485 df_rd_transfer_function (int bb_index)
487 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
488 unsigned int regno;
489 bitmap_iterator bi;
490 bitmap in = &bb_info->in;
491 bitmap out = &bb_info->out;
492 bitmap gen = &bb_info->gen;
493 bitmap kill = &bb_info->kill;
494 bitmap sparse_kill = &bb_info->sparse_kill;
495 bool changed = false;
497 if (bitmap_empty_p (sparse_kill))
498 changed = bitmap_ior_and_compl (out, gen, in, kill);
499 else
501 struct df_rd_problem_data *problem_data;
502 bitmap_head tmp;
504 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
505 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
506 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
507 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
509 bitmap_and_compl (&tmp, in, kill);
510 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
512 bitmap_clear_range (&tmp,
513 DF_DEFS_BEGIN (regno),
514 DF_DEFS_COUNT (regno));
516 bitmap_ior_into (&tmp, gen);
517 changed = !bitmap_equal_p (&tmp, out);
518 if (changed)
519 bitmap_move (out, &tmp);
520 else
521 bitmap_clear (&tmp);
524 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
526 /* Create a mask of DEFs for all registers live at the end of this
527 basic block, and mask out DEFs of registers that are not live.
528 Computing the mask looks costly, but the benefit of the pruning
529 outweighs the cost. */
530 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
531 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
532 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
533 unsigned int regno;
534 bitmap_iterator bi;
536 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
537 bitmap_set_range (live_defs,
538 DF_DEFS_BEGIN (regno),
539 DF_DEFS_COUNT (regno));
540 changed |= bitmap_and_into (&bb_info->out, live_defs);
541 BITMAP_FREE (live_defs);
544 return changed;
547 /* Free all storage associated with the problem. */
549 static void
550 df_rd_free (void)
552 struct df_rd_problem_data *problem_data
553 = (struct df_rd_problem_data *) df_rd->problem_data;
555 if (problem_data)
557 bitmap_obstack_release (&problem_data->rd_bitmaps);
559 df_rd->block_info_size = 0;
560 free (df_rd->block_info);
561 df_rd->block_info = NULL;
562 free (df_rd->problem_data);
564 free (df_rd);
568 /* Debugging info. */
570 static void
571 df_rd_start_dump (FILE *file)
573 struct df_rd_problem_data *problem_data
574 = (struct df_rd_problem_data *) df_rd->problem_data;
575 unsigned int m = DF_REG_SIZE (df);
576 unsigned int regno;
578 if (!df_rd->block_info)
579 return;
581 fprintf (file, ";; Reaching defs:\n");
583 fprintf (file, ";; sparse invalidated \t");
584 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
585 fprintf (file, ";; dense invalidated \t");
586 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
588 fprintf (file, ";; reg->defs[] map:\t");
589 for (regno = 0; regno < m; regno++)
590 if (DF_DEFS_COUNT (regno))
591 fprintf (file, "%d[%d,%d] ", regno,
592 DF_DEFS_BEGIN (regno),
593 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
594 fprintf (file, "\n");
598 static void
599 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
601 bitmap_head tmp;
602 unsigned int regno;
603 unsigned int m = DF_REG_SIZE (df);
604 bool first_reg = true;
606 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
608 bitmap_initialize (&tmp, &df_bitmap_obstack);
609 for (regno = 0; regno < m; regno++)
611 if (HARD_REGISTER_NUM_P (regno)
612 && (df->changeable_flags & DF_NO_HARD_REGS))
613 continue;
614 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
615 bitmap_and_into (&tmp, defs_set);
616 if (! bitmap_empty_p (&tmp))
618 bitmap_iterator bi;
619 unsigned int ix;
620 bool first_def = true;
622 if (! first_reg)
623 fprintf (file, ",");
624 first_reg = false;
626 fprintf (file, "%u[", regno);
627 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
629 fprintf (file, "%s%u", first_def ? "" : ",", ix);
630 first_def = false;
632 fprintf (file, "]");
634 bitmap_clear (&tmp);
637 fprintf (file, "\n");
638 bitmap_clear (&tmp);
641 /* Debugging info at top of bb. */
643 static void
644 df_rd_top_dump (basic_block bb, FILE *file)
646 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
647 if (!bb_info)
648 return;
650 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
651 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
652 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
656 /* Debugging info at bottom of bb. */
658 static void
659 df_rd_bottom_dump (basic_block bb, FILE *file)
661 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
662 if (!bb_info)
663 return;
665 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
668 /* All of the information associated with every instance of the problem. */
670 static const struct df_problem problem_RD =
672 DF_RD, /* Problem id. */
673 DF_FORWARD, /* Direction. */
674 df_rd_alloc, /* Allocate the problem specific data. */
675 NULL, /* Reset global information. */
676 df_rd_free_bb_info, /* Free basic block info. */
677 df_rd_local_compute, /* Local compute function. */
678 df_rd_init_solution, /* Init the solution specific data. */
679 df_worklist_dataflow, /* Worklist solver. */
680 NULL, /* Confluence operator 0. */
681 df_rd_confluence_n, /* Confluence operator n. */
682 df_rd_transfer_function, /* Transfer function. */
683 NULL, /* Finalize function. */
684 df_rd_free, /* Free all of the problem information. */
685 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
686 df_rd_start_dump, /* Debugging. */
687 df_rd_top_dump, /* Debugging start block. */
688 df_rd_bottom_dump, /* Debugging end block. */
689 NULL, /* Debugging start insn. */
690 NULL, /* Debugging end insn. */
691 NULL, /* Incremental solution verify start. */
692 NULL, /* Incremental solution verify end. */
693 NULL, /* Dependent problem. */
694 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */
695 TV_DF_RD, /* Timing variable. */
696 true /* Reset blocks on dropping out of blocks_to_analyze. */
701 /* Create a new RD instance and add it to the existing instance
702 of DF. */
704 void
705 df_rd_add_problem (void)
707 df_add_problem (&problem_RD);
712 /*----------------------------------------------------------------------------
713 LIVE REGISTERS
715 Find the locations in the function where any use of a pseudo can
716 reach in the backwards direction. In and out bitvectors are built
717 for each basic block. The regno is used to index into these sets.
718 See df.h for details.
719 ----------------------------------------------------------------------------*/
721 /* Private data used to verify the solution for this problem. */
722 struct df_lr_problem_data
724 bitmap_head *in;
725 bitmap_head *out;
726 /* An obstack for the bitmaps we need for this problem. */
727 bitmap_obstack lr_bitmaps;
730 /* Free basic block info. */
732 static void
733 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
734 void *vbb_info)
736 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
737 if (bb_info)
739 bitmap_clear (&bb_info->use);
740 bitmap_clear (&bb_info->def);
741 bitmap_clear (&bb_info->in);
742 bitmap_clear (&bb_info->out);
747 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
748 not touched unless the block is new. */
750 static void
751 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
753 unsigned int bb_index;
754 bitmap_iterator bi;
755 struct df_lr_problem_data *problem_data;
757 df_grow_bb_info (df_lr);
758 if (df_lr->problem_data)
759 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
760 else
762 problem_data = XNEW (struct df_lr_problem_data);
763 df_lr->problem_data = problem_data;
765 problem_data->out = NULL;
766 problem_data->in = NULL;
767 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
770 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
772 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
774 /* When bitmaps are already initialized, just clear them. */
775 if (bb_info->use.obstack)
777 bitmap_clear (&bb_info->def);
778 bitmap_clear (&bb_info->use);
780 else
782 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
783 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
784 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
785 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
789 df_lr->optional_p = false;
793 /* Reset the global solution for recalculation. */
795 static void
796 df_lr_reset (bitmap all_blocks)
798 unsigned int bb_index;
799 bitmap_iterator bi;
801 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
803 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
804 gcc_assert (bb_info);
805 bitmap_clear (&bb_info->in);
806 bitmap_clear (&bb_info->out);
811 /* Compute local live register info for basic block BB. */
813 static void
814 df_lr_bb_local_compute (unsigned int bb_index)
816 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
817 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
818 rtx_insn *insn;
819 df_ref def, use;
821 /* Process the registers set in an exception handler. */
822 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
823 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
825 unsigned int dregno = DF_REF_REGNO (def);
826 bitmap_set_bit (&bb_info->def, dregno);
827 bitmap_clear_bit (&bb_info->use, dregno);
830 /* Process the hardware registers that are always live. */
831 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
832 /* Add use to set of uses in this BB. */
833 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
834 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
836 FOR_BB_INSNS_REVERSE (bb, insn)
838 if (!NONDEBUG_INSN_P (insn))
839 continue;
841 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
842 FOR_EACH_INSN_INFO_DEF (def, insn_info)
843 /* If the def is to only part of the reg, it does
844 not kill the other defs that reach here. */
845 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
847 unsigned int dregno = DF_REF_REGNO (def);
848 bitmap_set_bit (&bb_info->def, dregno);
849 bitmap_clear_bit (&bb_info->use, dregno);
852 FOR_EACH_INSN_INFO_USE (use, insn_info)
853 /* Add use to set of uses in this BB. */
854 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
857 /* Process the registers set in an exception handler or the hard
858 frame pointer if this block is the target of a non local
859 goto. */
860 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
861 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
863 unsigned int dregno = DF_REF_REGNO (def);
864 bitmap_set_bit (&bb_info->def, dregno);
865 bitmap_clear_bit (&bb_info->use, dregno);
868 #ifdef EH_USES
869 /* Process the uses that are live into an exception handler. */
870 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
871 /* Add use to set of uses in this BB. */
872 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
873 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
874 #endif
876 /* If the df_live problem is not defined, such as at -O0 and -O1, we
877 still need to keep the luids up to date. This is normally done
878 in the df_live problem since this problem has a forwards
879 scan. */
880 if (!df_live)
881 df_recompute_luids (bb);
885 /* Compute local live register info for each basic block within BLOCKS. */
887 static void
888 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
890 unsigned int bb_index, i;
891 bitmap_iterator bi;
893 bitmap_clear (&df->hardware_regs_used);
895 /* The all-important stack pointer must always be live. */
896 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
898 /* Global regs are always live, too. */
899 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
900 if (global_regs[i])
901 bitmap_set_bit (&df->hardware_regs_used, i);
903 /* Before reload, there are a few registers that must be forced
904 live everywhere -- which might not already be the case for
905 blocks within infinite loops. */
906 if (!reload_completed)
908 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
909 /* Any reference to any pseudo before reload is a potential
910 reference of the frame pointer. */
911 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
913 /* Pseudos with argument area equivalences may require
914 reloading via the argument pointer. */
915 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
916 && fixed_regs[ARG_POINTER_REGNUM])
917 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
919 /* Any constant, or pseudo with constant equivalences, may
920 require reloading from memory using the pic register. */
921 if (pic_offset_table_regnum != INVALID_REGNUM
922 && fixed_regs[pic_offset_table_regnum])
923 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
926 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
928 if (bb_index == EXIT_BLOCK)
930 /* The exit block is special for this problem and its bits are
931 computed from thin air. */
932 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
933 bitmap_copy (&bb_info->use, df->exit_block_uses);
935 else
936 df_lr_bb_local_compute (bb_index);
939 bitmap_clear (df_lr->out_of_date_transfer_functions);
943 /* Initialize the solution vectors. */
945 static void
946 df_lr_init (bitmap all_blocks)
948 unsigned int bb_index;
949 bitmap_iterator bi;
951 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
953 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
954 bitmap_copy (&bb_info->in, &bb_info->use);
955 bitmap_clear (&bb_info->out);
960 /* Confluence function that processes infinite loops. This might be a
961 noreturn function that throws. And even if it isn't, getting the
962 unwind info right helps debugging. */
963 static void
964 df_lr_confluence_0 (basic_block bb)
966 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
967 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
968 bitmap_copy (op1, &df->hardware_regs_used);
972 /* Confluence function that ignores fake edges. */
974 static bool
975 df_lr_confluence_n (edge e)
977 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
978 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
979 bool changed = false;
981 /* Call-clobbered registers die across exception and call edges. */
982 /* ??? Abnormal call edges ignored for the moment, as this gets
983 confused by sibling call edges, which crashes reg-stack. */
984 if (e->flags & EDGE_EH)
985 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
986 else
987 changed = bitmap_ior_into (op1, op2);
989 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
990 return changed;
994 /* Transfer function. */
996 static bool
997 df_lr_transfer_function (int bb_index)
999 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1000 bitmap in = &bb_info->in;
1001 bitmap out = &bb_info->out;
1002 bitmap use = &bb_info->use;
1003 bitmap def = &bb_info->def;
1005 return bitmap_ior_and_compl (in, use, out, def);
1009 /* Run the fast dce as a side effect of building LR. */
1011 static void
1012 df_lr_finalize (bitmap all_blocks)
1014 df_lr->solutions_dirty = false;
1015 if (df->changeable_flags & DF_LR_RUN_DCE)
1017 run_fast_df_dce ();
1019 /* If dce deletes some instructions, we need to recompute the lr
1020 solution before proceeding further. The problem is that fast
1021 dce is a pessimestic dataflow algorithm. In the case where
1022 it deletes a statement S inside of a loop, the uses inside of
1023 S may not be deleted from the dataflow solution because they
1024 were carried around the loop. While it is conservatively
1025 correct to leave these extra bits, the standards of df
1026 require that we maintain the best possible (least fixed
1027 point) solution. The only way to do that is to redo the
1028 iteration from the beginning. See PR35805 for an
1029 example. */
1030 if (df_lr->solutions_dirty)
1032 df_clear_flags (DF_LR_RUN_DCE);
1033 df_lr_alloc (all_blocks);
1034 df_lr_local_compute (all_blocks);
1035 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1036 df_lr_finalize (all_blocks);
1037 df_set_flags (DF_LR_RUN_DCE);
1043 /* Free all storage associated with the problem. */
1045 static void
1046 df_lr_free (void)
1048 struct df_lr_problem_data *problem_data
1049 = (struct df_lr_problem_data *) df_lr->problem_data;
1050 if (df_lr->block_info)
1053 df_lr->block_info_size = 0;
1054 free (df_lr->block_info);
1055 df_lr->block_info = NULL;
1056 bitmap_obstack_release (&problem_data->lr_bitmaps);
1057 free (df_lr->problem_data);
1058 df_lr->problem_data = NULL;
1061 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1062 free (df_lr);
1066 /* Debugging info at top of bb. */
1068 static void
1069 df_lr_top_dump (basic_block bb, FILE *file)
1071 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1072 struct df_lr_problem_data *problem_data;
1073 if (!bb_info)
1074 return;
1076 fprintf (file, ";; lr in \t");
1077 df_print_regset (file, &bb_info->in);
1078 if (df_lr->problem_data)
1080 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1081 if (problem_data->in)
1083 fprintf (file, ";; old in \t");
1084 df_print_regset (file, &problem_data->in[bb->index]);
1087 fprintf (file, ";; lr use \t");
1088 df_print_regset (file, &bb_info->use);
1089 fprintf (file, ";; lr def \t");
1090 df_print_regset (file, &bb_info->def);
1094 /* Debugging info at bottom of bb. */
1096 static void
1097 df_lr_bottom_dump (basic_block bb, FILE *file)
1099 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1100 struct df_lr_problem_data *problem_data;
1101 if (!bb_info)
1102 return;
1104 fprintf (file, ";; lr out \t");
1105 df_print_regset (file, &bb_info->out);
1106 if (df_lr->problem_data)
1108 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1109 if (problem_data->out)
1111 fprintf (file, ";; old out \t");
1112 df_print_regset (file, &problem_data->out[bb->index]);
1118 /* Build the datastructure to verify that the solution to the dataflow
1119 equations is not dirty. */
1121 static void
1122 df_lr_verify_solution_start (void)
1124 basic_block bb;
1125 struct df_lr_problem_data *problem_data;
1126 if (df_lr->solutions_dirty)
1127 return;
1129 /* Set it true so that the solution is recomputed. */
1130 df_lr->solutions_dirty = true;
1132 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1133 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1134 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1136 FOR_ALL_BB_FN (bb, cfun)
1138 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1139 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1140 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1141 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1146 /* Compare the saved datastructure and the new solution to the dataflow
1147 equations. */
1149 static void
1150 df_lr_verify_solution_end (void)
1152 struct df_lr_problem_data *problem_data;
1153 basic_block bb;
1155 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1157 if (!problem_data->out)
1158 return;
1160 if (df_lr->solutions_dirty)
1161 /* Do not check if the solution is still dirty. See the comment
1162 in df_lr_finalize for details. */
1163 df_lr->solutions_dirty = false;
1164 else
1165 FOR_ALL_BB_FN (bb, cfun)
1167 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1168 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1170 /*df_dump (stderr);*/
1171 gcc_unreachable ();
1175 /* Cannot delete them immediately because you may want to dump them
1176 if the comparison fails. */
1177 FOR_ALL_BB_FN (bb, cfun)
1179 bitmap_clear (&problem_data->in[bb->index]);
1180 bitmap_clear (&problem_data->out[bb->index]);
1183 free (problem_data->in);
1184 free (problem_data->out);
1185 problem_data->in = NULL;
1186 problem_data->out = NULL;
1190 /* All of the information associated with every instance of the problem. */
1192 static const struct df_problem problem_LR =
1194 DF_LR, /* Problem id. */
1195 DF_BACKWARD, /* Direction. */
1196 df_lr_alloc, /* Allocate the problem specific data. */
1197 df_lr_reset, /* Reset global information. */
1198 df_lr_free_bb_info, /* Free basic block info. */
1199 df_lr_local_compute, /* Local compute function. */
1200 df_lr_init, /* Init the solution specific data. */
1201 df_worklist_dataflow, /* Worklist solver. */
1202 df_lr_confluence_0, /* Confluence operator 0. */
1203 df_lr_confluence_n, /* Confluence operator n. */
1204 df_lr_transfer_function, /* Transfer function. */
1205 df_lr_finalize, /* Finalize function. */
1206 df_lr_free, /* Free all of the problem information. */
1207 NULL, /* Remove this problem from the stack of dataflow problems. */
1208 NULL, /* Debugging. */
1209 df_lr_top_dump, /* Debugging start block. */
1210 df_lr_bottom_dump, /* Debugging end block. */
1211 NULL, /* Debugging start insn. */
1212 NULL, /* Debugging end insn. */
1213 df_lr_verify_solution_start,/* Incremental solution verify start. */
1214 df_lr_verify_solution_end, /* Incremental solution verify end. */
1215 NULL, /* Dependent problem. */
1216 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1217 TV_DF_LR, /* Timing variable. */
1218 false /* Reset blocks on dropping out of blocks_to_analyze. */
1222 /* Create a new DATAFLOW instance and add it to an existing instance
1223 of DF. The returned structure is what is used to get at the
1224 solution. */
1226 void
1227 df_lr_add_problem (void)
1229 df_add_problem (&problem_LR);
1230 /* These will be initialized when df_scan_blocks processes each
1231 block. */
1232 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1236 /* Verify that all of the lr related info is consistent and
1237 correct. */
1239 void
1240 df_lr_verify_transfer_functions (void)
1242 basic_block bb;
1243 bitmap_head saved_def;
1244 bitmap_head saved_use;
1245 bitmap_head all_blocks;
1247 if (!df)
1248 return;
1250 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1251 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1252 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1254 FOR_ALL_BB_FN (bb, cfun)
1256 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1257 bitmap_set_bit (&all_blocks, bb->index);
1259 if (bb_info)
1261 /* Make a copy of the transfer functions and then compute
1262 new ones to see if the transfer functions have
1263 changed. */
1264 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1265 bb->index))
1267 bitmap_copy (&saved_def, &bb_info->def);
1268 bitmap_copy (&saved_use, &bb_info->use);
1269 bitmap_clear (&bb_info->def);
1270 bitmap_clear (&bb_info->use);
1272 df_lr_bb_local_compute (bb->index);
1273 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1274 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1277 else
1279 /* If we do not have basic block info, the block must be in
1280 the list of dirty blocks or else some one has added a
1281 block behind our backs. */
1282 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1283 bb->index));
1285 /* Make sure no one created a block without following
1286 procedures. */
1287 gcc_assert (df_scan_get_bb_info (bb->index));
1290 /* Make sure there are no dirty bits in blocks that have been deleted. */
1291 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1292 &all_blocks));
1294 bitmap_clear (&saved_def);
1295 bitmap_clear (&saved_use);
1296 bitmap_clear (&all_blocks);
1301 /*----------------------------------------------------------------------------
1302 LIVE AND MAY-INITIALIZED REGISTERS.
1304 This problem first computes the IN and OUT bitvectors for the
1305 may-initialized registers problems, which is a forward problem.
1306 It gives the set of registers for which we MAY have an available
1307 definition, i.e. for which there is an available definition on
1308 at least one path from the entry block to the entry/exit of a
1309 basic block. Sets generate a definition, while clobbers kill
1310 a definition.
1312 In and out bitvectors are built for each basic block and are indexed by
1313 regnum (see df.h for details). In and out bitvectors in struct
1314 df_live_bb_info actually refers to the may-initialized problem;
1316 Then, the in and out sets for the LIVE problem itself are computed.
1317 These are the logical AND of the IN and OUT sets from the LR problem
1318 and the may-initialized problem.
1319 ----------------------------------------------------------------------------*/
1321 /* Private data used to verify the solution for this problem. */
1322 struct df_live_problem_data
1324 bitmap_head *in;
1325 bitmap_head *out;
1326 /* An obstack for the bitmaps we need for this problem. */
1327 bitmap_obstack live_bitmaps;
1330 /* Scratch var used by transfer functions. This is used to implement
1331 an optimization to reduce the amount of space used to compute the
1332 combined lr and live analysis. */
1333 static bitmap_head df_live_scratch;
1336 /* Free basic block info. */
1338 static void
1339 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1340 void *vbb_info)
1342 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1343 if (bb_info)
1345 bitmap_clear (&bb_info->gen);
1346 bitmap_clear (&bb_info->kill);
1347 bitmap_clear (&bb_info->in);
1348 bitmap_clear (&bb_info->out);
1353 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1354 not touched unless the block is new. */
1356 static void
1357 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1359 unsigned int bb_index;
1360 bitmap_iterator bi;
1361 struct df_live_problem_data *problem_data;
1363 if (df_live->problem_data)
1364 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1365 else
1367 problem_data = XNEW (struct df_live_problem_data);
1368 df_live->problem_data = problem_data;
1370 problem_data->out = NULL;
1371 problem_data->in = NULL;
1372 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1373 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1376 df_grow_bb_info (df_live);
1378 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1380 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1382 /* When bitmaps are already initialized, just clear them. */
1383 if (bb_info->kill.obstack)
1385 bitmap_clear (&bb_info->kill);
1386 bitmap_clear (&bb_info->gen);
1388 else
1390 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1391 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1392 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1393 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1396 df_live->optional_p = (optimize <= 1);
1400 /* Reset the global solution for recalculation. */
1402 static void
1403 df_live_reset (bitmap all_blocks)
1405 unsigned int bb_index;
1406 bitmap_iterator bi;
1408 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1410 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1411 gcc_assert (bb_info);
1412 bitmap_clear (&bb_info->in);
1413 bitmap_clear (&bb_info->out);
1418 /* Compute local uninitialized register info for basic block BB. */
1420 static void
1421 df_live_bb_local_compute (unsigned int bb_index)
1423 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1424 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1425 rtx_insn *insn;
1426 df_ref def;
1427 int luid = 0;
1429 FOR_BB_INSNS (bb, insn)
1431 unsigned int uid = INSN_UID (insn);
1432 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1434 /* Inserting labels does not always trigger the incremental
1435 rescanning. */
1436 if (!insn_info)
1438 gcc_assert (!INSN_P (insn));
1439 insn_info = df_insn_create_insn_record (insn);
1442 DF_INSN_INFO_LUID (insn_info) = luid;
1443 if (!INSN_P (insn))
1444 continue;
1446 luid++;
1447 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1449 unsigned int regno = DF_REF_REGNO (def);
1451 if (DF_REF_FLAGS_IS_SET (def,
1452 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1453 /* All partial or conditional def
1454 seen are included in the gen set. */
1455 bitmap_set_bit (&bb_info->gen, regno);
1456 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1457 /* Only must clobbers for the entire reg destroy the
1458 value. */
1459 bitmap_set_bit (&bb_info->kill, regno);
1460 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1461 bitmap_set_bit (&bb_info->gen, regno);
1465 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1466 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1470 /* Compute local uninitialized register info. */
1472 static void
1473 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1475 unsigned int bb_index;
1476 bitmap_iterator bi;
1478 df_grow_insn_info ();
1480 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1481 0, bb_index, bi)
1483 df_live_bb_local_compute (bb_index);
1486 bitmap_clear (df_live->out_of_date_transfer_functions);
1490 /* Initialize the solution vectors. */
1492 static void
1493 df_live_init (bitmap all_blocks)
1495 unsigned int bb_index;
1496 bitmap_iterator bi;
1498 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1500 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1501 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1503 /* No register may reach a location where it is not used. Thus
1504 we trim the rr result to the places where it is used. */
1505 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1506 bitmap_clear (&bb_info->in);
1510 /* Forward confluence function that ignores fake edges. */
1512 static bool
1513 df_live_confluence_n (edge e)
1515 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1516 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1518 if (e->flags & EDGE_FAKE)
1519 return false;
1521 return bitmap_ior_into (op1, op2);
1525 /* Transfer function for the forwards may-initialized problem. */
1527 static bool
1528 df_live_transfer_function (int bb_index)
1530 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1531 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1532 bitmap in = &bb_info->in;
1533 bitmap out = &bb_info->out;
1534 bitmap gen = &bb_info->gen;
1535 bitmap kill = &bb_info->kill;
1537 /* We need to use a scratch set here so that the value returned from this
1538 function invocation properly reflects whether the sets changed in a
1539 significant way; i.e. not just because the lr set was anded in. */
1540 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1541 /* No register may reach a location where it is not used. Thus
1542 we trim the rr result to the places where it is used. */
1543 bitmap_and_into (in, &bb_lr_info->in);
1545 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1549 /* And the LR info with the may-initialized registers to produce the LIVE info. */
1551 static void
1552 df_live_finalize (bitmap all_blocks)
1555 if (df_live->solutions_dirty)
1557 bitmap_iterator bi;
1558 unsigned int bb_index;
1560 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1562 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1563 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1565 /* No register may reach a location where it is not used. Thus
1566 we trim the rr result to the places where it is used. */
1567 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1568 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1571 df_live->solutions_dirty = false;
1576 /* Free all storage associated with the problem. */
1578 static void
1579 df_live_free (void)
1581 struct df_live_problem_data *problem_data
1582 = (struct df_live_problem_data *) df_live->problem_data;
1583 if (df_live->block_info)
1585 df_live->block_info_size = 0;
1586 free (df_live->block_info);
1587 df_live->block_info = NULL;
1588 bitmap_release (&df_live_scratch);
1589 bitmap_obstack_release (&problem_data->live_bitmaps);
1590 free (problem_data);
1591 df_live->problem_data = NULL;
1593 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1594 free (df_live);
1598 /* Debugging info at top of bb. */
1600 static void
1601 df_live_top_dump (basic_block bb, FILE *file)
1603 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1604 struct df_live_problem_data *problem_data;
1606 if (!bb_info)
1607 return;
1609 fprintf (file, ";; live in \t");
1610 df_print_regset (file, &bb_info->in);
1611 if (df_live->problem_data)
1613 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1614 if (problem_data->in)
1616 fprintf (file, ";; old in \t");
1617 df_print_regset (file, &problem_data->in[bb->index]);
1620 fprintf (file, ";; live gen \t");
1621 df_print_regset (file, &bb_info->gen);
1622 fprintf (file, ";; live kill\t");
1623 df_print_regset (file, &bb_info->kill);
1627 /* Debugging info at bottom of bb. */
1629 static void
1630 df_live_bottom_dump (basic_block bb, FILE *file)
1632 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1633 struct df_live_problem_data *problem_data;
1635 if (!bb_info)
1636 return;
1638 fprintf (file, ";; live out \t");
1639 df_print_regset (file, &bb_info->out);
1640 if (df_live->problem_data)
1642 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1643 if (problem_data->out)
1645 fprintf (file, ";; old out \t");
1646 df_print_regset (file, &problem_data->out[bb->index]);
1652 /* Build the datastructure to verify that the solution to the dataflow
1653 equations is not dirty. */
1655 static void
1656 df_live_verify_solution_start (void)
1658 basic_block bb;
1659 struct df_live_problem_data *problem_data;
1660 if (df_live->solutions_dirty)
1661 return;
1663 /* Set it true so that the solution is recomputed. */
1664 df_live->solutions_dirty = true;
1666 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1667 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1668 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1670 FOR_ALL_BB_FN (bb, cfun)
1672 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1673 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1674 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1675 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1680 /* Compare the saved datastructure and the new solution to the dataflow
1681 equations. */
1683 static void
1684 df_live_verify_solution_end (void)
1686 struct df_live_problem_data *problem_data;
1687 basic_block bb;
1689 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1690 if (!problem_data->out)
1691 return;
1693 FOR_ALL_BB_FN (bb, cfun)
1695 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1696 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1698 /*df_dump (stderr);*/
1699 gcc_unreachable ();
1703 /* Cannot delete them immediately because you may want to dump them
1704 if the comparison fails. */
1705 FOR_ALL_BB_FN (bb, cfun)
1707 bitmap_clear (&problem_data->in[bb->index]);
1708 bitmap_clear (&problem_data->out[bb->index]);
1711 free (problem_data->in);
1712 free (problem_data->out);
1713 free (problem_data);
1714 df_live->problem_data = NULL;
1718 /* All of the information associated with every instance of the problem. */
1720 static const struct df_problem problem_LIVE =
1722 DF_LIVE, /* Problem id. */
1723 DF_FORWARD, /* Direction. */
1724 df_live_alloc, /* Allocate the problem specific data. */
1725 df_live_reset, /* Reset global information. */
1726 df_live_free_bb_info, /* Free basic block info. */
1727 df_live_local_compute, /* Local compute function. */
1728 df_live_init, /* Init the solution specific data. */
1729 df_worklist_dataflow, /* Worklist solver. */
1730 NULL, /* Confluence operator 0. */
1731 df_live_confluence_n, /* Confluence operator n. */
1732 df_live_transfer_function, /* Transfer function. */
1733 df_live_finalize, /* Finalize function. */
1734 df_live_free, /* Free all of the problem information. */
1735 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1736 NULL, /* Debugging. */
1737 df_live_top_dump, /* Debugging start block. */
1738 df_live_bottom_dump, /* Debugging end block. */
1739 NULL, /* Debugging start insn. */
1740 NULL, /* Debugging end insn. */
1741 df_live_verify_solution_start,/* Incremental solution verify start. */
1742 df_live_verify_solution_end, /* Incremental solution verify end. */
1743 &problem_LR, /* Dependent problem. */
1744 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1745 TV_DF_LIVE, /* Timing variable. */
1746 false /* Reset blocks on dropping out of blocks_to_analyze. */
1750 /* Create a new DATAFLOW instance and add it to an existing instance
1751 of DF. The returned structure is what is used to get at the
1752 solution. */
1754 void
1755 df_live_add_problem (void)
1757 df_add_problem (&problem_LIVE);
1758 /* These will be initialized when df_scan_blocks processes each
1759 block. */
1760 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1764 /* Set all of the blocks as dirty. This needs to be done if this
1765 problem is added after all of the insns have been scanned. */
1767 void
1768 df_live_set_all_dirty (void)
1770 basic_block bb;
1771 FOR_ALL_BB_FN (bb, cfun)
1772 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1773 bb->index);
1777 /* Verify that all of the lr related info is consistent and
1778 correct. */
1780 void
1781 df_live_verify_transfer_functions (void)
1783 basic_block bb;
1784 bitmap_head saved_gen;
1785 bitmap_head saved_kill;
1786 bitmap_head all_blocks;
1788 if (!df)
1789 return;
1791 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1792 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1793 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1795 df_grow_insn_info ();
1797 FOR_ALL_BB_FN (bb, cfun)
1799 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1800 bitmap_set_bit (&all_blocks, bb->index);
1802 if (bb_info)
1804 /* Make a copy of the transfer functions and then compute
1805 new ones to see if the transfer functions have
1806 changed. */
1807 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1808 bb->index))
1810 bitmap_copy (&saved_gen, &bb_info->gen);
1811 bitmap_copy (&saved_kill, &bb_info->kill);
1812 bitmap_clear (&bb_info->gen);
1813 bitmap_clear (&bb_info->kill);
1815 df_live_bb_local_compute (bb->index);
1816 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1817 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1820 else
1822 /* If we do not have basic block info, the block must be in
1823 the list of dirty blocks or else some one has added a
1824 block behind our backs. */
1825 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1826 bb->index));
1828 /* Make sure no one created a block without following
1829 procedures. */
1830 gcc_assert (df_scan_get_bb_info (bb->index));
1833 /* Make sure there are no dirty bits in blocks that have been deleted. */
1834 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1835 &all_blocks));
1836 bitmap_clear (&saved_gen);
1837 bitmap_clear (&saved_kill);
1838 bitmap_clear (&all_blocks);
1841 /*----------------------------------------------------------------------------
1842 MUST-INITIALIZED REGISTERS.
1843 ----------------------------------------------------------------------------*/
1845 /* Private data used to verify the solution for this problem. */
1846 struct df_mir_problem_data
1848 bitmap_head *in;
1849 bitmap_head *out;
1850 /* An obstack for the bitmaps we need for this problem. */
1851 bitmap_obstack mir_bitmaps;
1855 /* Free basic block info. */
1857 static void
1858 df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1859 void *vbb_info)
1861 struct df_mir_bb_info *bb_info = (struct df_mir_bb_info *) vbb_info;
1862 if (bb_info)
1864 bitmap_clear (&bb_info->gen);
1865 bitmap_clear (&bb_info->kill);
1866 bitmap_clear (&bb_info->in);
1867 bitmap_clear (&bb_info->out);
1872 /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
1873 not touched unless the block is new. */
1875 static void
1876 df_mir_alloc (bitmap all_blocks)
1878 unsigned int bb_index;
1879 bitmap_iterator bi;
1880 struct df_mir_problem_data *problem_data;
1882 if (df_mir->problem_data)
1883 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1884 else
1886 problem_data = XNEW (struct df_mir_problem_data);
1887 df_mir->problem_data = problem_data;
1889 problem_data->out = NULL;
1890 problem_data->in = NULL;
1891 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1894 df_grow_bb_info (df_mir);
1896 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1898 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1900 /* When bitmaps are already initialized, just clear them. */
1901 if (bb_info->kill.obstack)
1903 bitmap_clear (&bb_info->kill);
1904 bitmap_clear (&bb_info->gen);
1906 else
1908 bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1909 bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1910 bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1911 bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1912 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1913 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1917 df_mir->optional_p = 1;
1921 /* Reset the global solution for recalculation. */
1923 static void
1924 df_mir_reset (bitmap all_blocks)
1926 unsigned int bb_index;
1927 bitmap_iterator bi;
1929 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1931 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1933 gcc_assert (bb_info);
1935 bitmap_clear (&bb_info->in);
1936 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1937 bitmap_clear (&bb_info->out);
1938 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1943 /* Compute local uninitialized register info for basic block BB. */
1945 static void
1946 df_mir_bb_local_compute (unsigned int bb_index)
1948 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1949 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1950 rtx_insn *insn;
1951 int luid = 0;
1953 /* Ignoring artificial defs is intentional: these often pretend that some
1954 registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
1955 though they are not used for that. As a result, conservatively assume
1956 they may be uninitialized. */
1958 FOR_BB_INSNS (bb, insn)
1960 unsigned int uid = INSN_UID (insn);
1961 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1963 /* Inserting labels does not always trigger the incremental
1964 rescanning. */
1965 if (!insn_info)
1967 gcc_assert (!INSN_P (insn));
1968 insn_info = df_insn_create_insn_record (insn);
1971 DF_INSN_INFO_LUID (insn_info) = luid;
1972 if (!INSN_P (insn))
1973 continue;
1975 luid++;
1976 df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
1981 /* Compute local uninitialized register info. */
1983 static void
1984 df_mir_local_compute (bitmap all_blocks)
1986 unsigned int bb_index;
1987 bitmap_iterator bi;
1989 df_grow_insn_info ();
1991 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1993 df_mir_bb_local_compute (bb_index);
1998 /* Initialize the solution vectors. */
2000 static void
2001 df_mir_init (bitmap all_blocks)
2003 df_mir_reset (all_blocks);
2007 /* Initialize IN sets for blocks with no predecessors: when landing on such
2008 blocks, assume all registers are uninitialized. */
2010 static void
2011 df_mir_confluence_0 (basic_block bb)
2013 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2015 bitmap_clear (&bb_info->in);
2019 /* Forward confluence function that ignores fake edges. */
2021 static bool
2022 df_mir_confluence_n (edge e)
2024 bitmap op1 = &df_mir_get_bb_info (e->dest->index)->in;
2025 bitmap op2 = &df_mir_get_bb_info (e->src->index)->out;
2027 if (e->flags & EDGE_FAKE)
2028 return false;
2030 /* A register is must-initialized at the entry of a basic block iff it is
2031 must-initialized at the exit of all the predecessors. */
2032 return bitmap_and_into (op1, op2);
2036 /* Transfer function for the forwards must-initialized problem. */
2038 static bool
2039 df_mir_transfer_function (int bb_index)
2041 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2042 bitmap in = &bb_info->in;
2043 bitmap out = &bb_info->out;
2044 bitmap gen = &bb_info->gen;
2045 bitmap kill = &bb_info->kill;
2047 return bitmap_ior_and_compl (out, gen, in, kill);
2051 /* Free all storage associated with the problem. */
2053 static void
2054 df_mir_free (void)
2056 struct df_mir_problem_data *problem_data
2057 = (struct df_mir_problem_data *) df_mir->problem_data;
2058 if (df_mir->block_info)
2060 df_mir->block_info_size = 0;
2061 free (df_mir->block_info);
2062 df_mir->block_info = NULL;
2063 bitmap_obstack_release (&problem_data->mir_bitmaps);
2064 free (problem_data);
2065 df_mir->problem_data = NULL;
2067 free (df_mir);
2071 /* Debugging info at top of bb. */
2073 static void
2074 df_mir_top_dump (basic_block bb, FILE *file)
2076 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2078 if (!bb_info)
2079 return;
2081 fprintf (file, ";; mir in \t");
2082 df_print_regset (file, &bb_info->in);
2083 fprintf (file, ";; mir kill\t");
2084 df_print_regset (file, &bb_info->kill);
2085 fprintf (file, ";; mir gen \t");
2086 df_print_regset (file, &bb_info->gen);
2089 /* Debugging info at bottom of bb. */
2091 static void
2092 df_mir_bottom_dump (basic_block bb, FILE *file)
2094 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2096 if (!bb_info)
2097 return;
2099 fprintf (file, ";; mir out \t");
2100 df_print_regset (file, &bb_info->out);
2104 /* Build the datastructure to verify that the solution to the dataflow
2105 equations is not dirty. */
2107 static void
2108 df_mir_verify_solution_start (void)
2110 basic_block bb;
2111 struct df_mir_problem_data *problem_data;
2112 if (df_mir->solutions_dirty)
2113 return;
2115 /* Set it true so that the solution is recomputed. */
2116 df_mir->solutions_dirty = true;
2118 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2119 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2120 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2121 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2123 FOR_ALL_BB_FN (bb, cfun)
2125 bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
2126 bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
2127 bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2128 bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2133 /* Compare the saved datastructure and the new solution to the dataflow
2134 equations. */
2136 static void
2137 df_mir_verify_solution_end (void)
2139 struct df_mir_problem_data *problem_data;
2140 basic_block bb;
2142 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2143 if (!problem_data->out)
2144 return;
2146 FOR_ALL_BB_FN (bb, cfun)
2148 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2149 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2150 gcc_unreachable ();
2153 /* Cannot delete them immediately because you may want to dump them
2154 if the comparison fails. */
2155 FOR_ALL_BB_FN (bb, cfun)
2157 bitmap_clear (&problem_data->in[bb->index]);
2158 bitmap_clear (&problem_data->out[bb->index]);
2161 free (problem_data->in);
2162 free (problem_data->out);
2163 bitmap_obstack_release (&problem_data->mir_bitmaps);
2164 free (problem_data);
2165 df_mir->problem_data = NULL;
2169 /* All of the information associated with every instance of the problem. */
2171 static const struct df_problem problem_MIR =
2173 DF_MIR, /* Problem id. */
2174 DF_FORWARD, /* Direction. */
2175 df_mir_alloc, /* Allocate the problem specific data. */
2176 df_mir_reset, /* Reset global information. */
2177 df_mir_free_bb_info, /* Free basic block info. */
2178 df_mir_local_compute, /* Local compute function. */
2179 df_mir_init, /* Init the solution specific data. */
2180 df_worklist_dataflow, /* Worklist solver. */
2181 df_mir_confluence_0, /* Confluence operator 0. */
2182 df_mir_confluence_n, /* Confluence operator n. */
2183 df_mir_transfer_function, /* Transfer function. */
2184 NULL, /* Finalize function. */
2185 df_mir_free, /* Free all of the problem information. */
2186 df_mir_free, /* Remove this problem from the stack of dataflow problems. */
2187 NULL, /* Debugging. */
2188 df_mir_top_dump, /* Debugging start block. */
2189 df_mir_bottom_dump, /* Debugging end block. */
2190 NULL, /* Debugging start insn. */
2191 NULL, /* Debugging end insn. */
2192 df_mir_verify_solution_start, /* Incremental solution verify start. */
2193 df_mir_verify_solution_end, /* Incremental solution verify end. */
2194 NULL, /* Dependent problem. */
2195 sizeof (struct df_mir_bb_info),/* Size of entry of block_info array. */
2196 TV_DF_MIR, /* Timing variable. */
2197 false /* Reset blocks on dropping out of blocks_to_analyze. */
2201 /* Create a new DATAFLOW instance and add it to an existing instance
2202 of DF. */
2204 void
2205 df_mir_add_problem (void)
2207 df_add_problem (&problem_MIR);
2208 /* These will be initialized when df_scan_blocks processes each
2209 block. */
2210 df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2214 /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2216 void
2217 df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2218 bitmap kill, bitmap gen)
2220 df_ref def;
2222 FOR_EACH_INSN_DEF (def, insn)
2224 unsigned int regno = DF_REF_REGNO (def);
2226 /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
2227 previous gen is irrelevant (and reciprocally). Also, claim that a
2228 register is GEN only if it is in all cases. */
2229 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2231 bitmap_set_bit (kill, regno);
2232 bitmap_clear_bit (gen, regno);
2234 /* In the worst case, partial and conditional defs can leave bits
2235 uninitialized, so assume they do not change anything. */
2236 else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2238 bitmap_set_bit (gen, regno);
2239 bitmap_clear_bit (kill, regno);
2244 /*----------------------------------------------------------------------------
2245 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2247 Link either the defs to the uses and / or the uses to the defs.
2249 These problems are set up like the other dataflow problems so that
2250 they nicely fit into the framework. They are much simpler and only
2251 involve a single traversal of instructions and an examination of
2252 the reaching defs information (the dependent problem).
2253 ----------------------------------------------------------------------------*/
2255 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2257 /* Create a du or ud chain from SRC to DST and link it into SRC. */
2259 struct df_link *
2260 df_chain_create (df_ref src, df_ref dst)
2262 struct df_link *head = DF_REF_CHAIN (src);
2263 struct df_link *link = df_chain->block_pool->allocate ();
2265 DF_REF_CHAIN (src) = link;
2266 link->next = head;
2267 link->ref = dst;
2268 return link;
2272 /* Delete any du or ud chains that start at REF and point to
2273 TARGET. */
2274 static void
2275 df_chain_unlink_1 (df_ref ref, df_ref target)
2277 struct df_link *chain = DF_REF_CHAIN (ref);
2278 struct df_link *prev = NULL;
2280 while (chain)
2282 if (chain->ref == target)
2284 if (prev)
2285 prev->next = chain->next;
2286 else
2287 DF_REF_CHAIN (ref) = chain->next;
2288 df_chain->block_pool->remove (chain);
2289 return;
2291 prev = chain;
2292 chain = chain->next;
2297 /* Delete a du or ud chain that leave or point to REF. */
2299 void
2300 df_chain_unlink (df_ref ref)
2302 struct df_link *chain = DF_REF_CHAIN (ref);
2303 while (chain)
2305 struct df_link *next = chain->next;
2306 /* Delete the other side if it exists. */
2307 df_chain_unlink_1 (chain->ref, ref);
2308 df_chain->block_pool->remove (chain);
2309 chain = next;
2311 DF_REF_CHAIN (ref) = NULL;
2315 /* Copy the du or ud chain starting at FROM_REF and attach it to
2316 TO_REF. */
2318 void
2319 df_chain_copy (df_ref to_ref,
2320 struct df_link *from_ref)
2322 while (from_ref)
2324 df_chain_create (to_ref, from_ref->ref);
2325 from_ref = from_ref->next;
2330 /* Remove this problem from the stack of dataflow problems. */
2332 static void
2333 df_chain_remove_problem (void)
2335 bitmap_iterator bi;
2336 unsigned int bb_index;
2338 /* Wholesale destruction of the old chains. */
2339 if (df_chain->block_pool)
2340 delete df_chain->block_pool;
2342 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2344 rtx_insn *insn;
2345 df_ref def, use;
2346 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2348 if (df_chain_problem_p (DF_DU_CHAIN))
2349 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2350 DF_REF_CHAIN (def) = NULL;
2351 if (df_chain_problem_p (DF_UD_CHAIN))
2352 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2353 DF_REF_CHAIN (use) = NULL;
2355 FOR_BB_INSNS (bb, insn)
2356 if (INSN_P (insn))
2358 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2359 if (df_chain_problem_p (DF_DU_CHAIN))
2360 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2361 DF_REF_CHAIN (def) = NULL;
2362 if (df_chain_problem_p (DF_UD_CHAIN))
2364 FOR_EACH_INSN_INFO_USE (use, insn_info)
2365 DF_REF_CHAIN (use) = NULL;
2366 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2367 DF_REF_CHAIN (use) = NULL;
2372 bitmap_clear (df_chain->out_of_date_transfer_functions);
2373 df_chain->block_pool = NULL;
2377 /* Remove the chain problem completely. */
2379 static void
2380 df_chain_fully_remove_problem (void)
2382 df_chain_remove_problem ();
2383 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2384 free (df_chain);
2388 /* Create def-use or use-def chains. */
2390 static void
2391 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2393 df_chain_remove_problem ();
2394 df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2395 df_chain->optional_p = true;
2399 /* Reset all of the chains when the set of basic blocks changes. */
2401 static void
2402 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2404 df_chain_remove_problem ();
2408 /* Create the chains for a list of USEs. */
2410 static void
2411 df_chain_create_bb_process_use (bitmap local_rd,
2412 df_ref use,
2413 int top_flag)
2415 bitmap_iterator bi;
2416 unsigned int def_index;
2418 for (; use; use = DF_REF_NEXT_LOC (use))
2420 unsigned int uregno = DF_REF_REGNO (use);
2421 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2422 || (uregno >= FIRST_PSEUDO_REGISTER))
2424 /* Do not want to go through this for an uninitialized var. */
2425 int count = DF_DEFS_COUNT (uregno);
2426 if (count)
2428 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2430 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2431 unsigned int last_index = first_index + count - 1;
2433 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2435 df_ref def;
2436 if (def_index > last_index)
2437 break;
2439 def = DF_DEFS_GET (def_index);
2440 if (df_chain_problem_p (DF_DU_CHAIN))
2441 df_chain_create (def, use);
2442 if (df_chain_problem_p (DF_UD_CHAIN))
2443 df_chain_create (use, def);
2452 /* Create chains from reaching defs bitmaps for basic block BB. */
2454 static void
2455 df_chain_create_bb (unsigned int bb_index)
2457 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2458 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2459 rtx_insn *insn;
2460 bitmap_head cpy;
2462 bitmap_initialize (&cpy, &bitmap_default_obstack);
2463 bitmap_copy (&cpy, &bb_info->in);
2464 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2466 /* Since we are going forwards, process the artificial uses first
2467 then the artificial defs second. */
2469 #ifdef EH_USES
2470 /* Create the chains for the artificial uses from the EH_USES at the
2471 beginning of the block. */
2473 /* Artificials are only hard regs. */
2474 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2475 df_chain_create_bb_process_use (&cpy,
2476 df_get_artificial_uses (bb->index),
2477 DF_REF_AT_TOP);
2478 #endif
2480 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2482 /* Process the regular instructions next. */
2483 FOR_BB_INSNS (bb, insn)
2484 if (INSN_P (insn))
2486 unsigned int uid = INSN_UID (insn);
2488 /* First scan the uses and link them up with the defs that remain
2489 in the cpy vector. */
2490 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2491 if (df->changeable_flags & DF_EQ_NOTES)
2492 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2494 /* Since we are going forwards, process the defs second. */
2495 df_rd_simulate_one_insn (bb, insn, &cpy);
2498 /* Create the chains for the artificial uses of the hard registers
2499 at the end of the block. */
2500 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2501 df_chain_create_bb_process_use (&cpy,
2502 df_get_artificial_uses (bb->index),
2505 bitmap_clear (&cpy);
2508 /* Create def-use chains from reaching use bitmaps for basic blocks
2509 in BLOCKS. */
2511 static void
2512 df_chain_finalize (bitmap all_blocks)
2514 unsigned int bb_index;
2515 bitmap_iterator bi;
2517 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2519 df_chain_create_bb (bb_index);
2524 /* Free all storage associated with the problem. */
2526 static void
2527 df_chain_free (void)
2529 delete df_chain->block_pool;
2530 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2531 free (df_chain);
2535 /* Debugging info. */
2537 static void
2538 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2540 /* Artificials are only hard regs. */
2541 if (df->changeable_flags & DF_NO_HARD_REGS)
2542 return;
2543 if (df_chain_problem_p (DF_UD_CHAIN))
2545 df_ref use;
2547 fprintf (file,
2548 ";; UD chains for artificial uses at %s\n",
2549 top ? "top" : "bottom");
2550 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2551 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2552 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2554 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2555 df_chain_dump (DF_REF_CHAIN (use), file);
2556 fprintf (file, "\n");
2559 if (df_chain_problem_p (DF_DU_CHAIN))
2561 df_ref def;
2563 fprintf (file,
2564 ";; DU chains for artificial defs at %s\n",
2565 top ? "top" : "bottom");
2566 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2567 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2568 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2570 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2571 df_chain_dump (DF_REF_CHAIN (def), file);
2572 fprintf (file, "\n");
2577 static void
2578 df_chain_top_dump (basic_block bb, FILE *file)
2580 df_chain_bb_dump (bb, file, /*top=*/true);
2583 static void
2584 df_chain_bottom_dump (basic_block bb, FILE *file)
2586 df_chain_bb_dump (bb, file, /*top=*/false);
2589 static void
2590 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2592 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2594 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2595 df_ref use;
2597 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2598 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2599 FOR_EACH_INSN_INFO_USE (use, insn_info)
2600 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2601 || !(df->changeable_flags & DF_NO_HARD_REGS))
2603 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2604 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2605 fprintf (file, "read/write ");
2606 df_chain_dump (DF_REF_CHAIN (use), file);
2607 fprintf (file, "\n");
2609 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2610 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2611 || !(df->changeable_flags & DF_NO_HARD_REGS))
2613 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2614 df_chain_dump (DF_REF_CHAIN (use), file);
2615 fprintf (file, "\n");
2620 static void
2621 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2623 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2625 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2626 df_ref def;
2627 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2628 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2629 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2630 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2631 || !(df->changeable_flags & DF_NO_HARD_REGS))
2633 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2634 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2635 fprintf (file, "read/write ");
2636 df_chain_dump (DF_REF_CHAIN (def), file);
2637 fprintf (file, "\n");
2639 fprintf (file, "\n");
2643 static const struct df_problem problem_CHAIN =
2645 DF_CHAIN, /* Problem id. */
2646 DF_NONE, /* Direction. */
2647 df_chain_alloc, /* Allocate the problem specific data. */
2648 df_chain_reset, /* Reset global information. */
2649 NULL, /* Free basic block info. */
2650 NULL, /* Local compute function. */
2651 NULL, /* Init the solution specific data. */
2652 NULL, /* Iterative solver. */
2653 NULL, /* Confluence operator 0. */
2654 NULL, /* Confluence operator n. */
2655 NULL, /* Transfer function. */
2656 df_chain_finalize, /* Finalize function. */
2657 df_chain_free, /* Free all of the problem information. */
2658 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2659 NULL, /* Debugging. */
2660 df_chain_top_dump, /* Debugging start block. */
2661 df_chain_bottom_dump, /* Debugging end block. */
2662 df_chain_insn_top_dump, /* Debugging start insn. */
2663 df_chain_insn_bottom_dump, /* Debugging end insn. */
2664 NULL, /* Incremental solution verify start. */
2665 NULL, /* Incremental solution verify end. */
2666 &problem_RD, /* Dependent problem. */
2667 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2668 TV_DF_CHAIN, /* Timing variable. */
2669 false /* Reset blocks on dropping out of blocks_to_analyze. */
2673 /* Create a new DATAFLOW instance and add it to an existing instance
2674 of DF. The returned structure is what is used to get at the
2675 solution. */
2677 void
2678 df_chain_add_problem (unsigned int chain_flags)
2680 df_add_problem (&problem_CHAIN);
2681 df_chain->local_flags = chain_flags;
2682 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2685 #undef df_chain_problem_p
2688 /*----------------------------------------------------------------------------
2689 WORD LEVEL LIVE REGISTERS
2691 Find the locations in the function where any use of a pseudo can
2692 reach in the backwards direction. In and out bitvectors are built
2693 for each basic block. We only track pseudo registers that have a
2694 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2695 contain two bits corresponding to each of the subwords.
2697 ----------------------------------------------------------------------------*/
2699 /* Private data used to verify the solution for this problem. */
2700 struct df_word_lr_problem_data
2702 /* An obstack for the bitmaps we need for this problem. */
2703 bitmap_obstack word_lr_bitmaps;
2707 /* Free basic block info. */
2709 static void
2710 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2711 void *vbb_info)
2713 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2714 if (bb_info)
2716 bitmap_clear (&bb_info->use);
2717 bitmap_clear (&bb_info->def);
2718 bitmap_clear (&bb_info->in);
2719 bitmap_clear (&bb_info->out);
2724 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2725 not touched unless the block is new. */
2727 static void
2728 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2730 unsigned int bb_index;
2731 bitmap_iterator bi;
2732 basic_block bb;
2733 struct df_word_lr_problem_data *problem_data
2734 = XNEW (struct df_word_lr_problem_data);
2736 df_word_lr->problem_data = problem_data;
2738 df_grow_bb_info (df_word_lr);
2740 /* Create the mapping from regnos to slots. This does not change
2741 unless the problem is destroyed and recreated. In particular, if
2742 we end up deleting the only insn that used a subreg, we do not
2743 want to redo the mapping because this would invalidate everything
2744 else. */
2746 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2748 FOR_EACH_BB_FN (bb, cfun)
2749 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2751 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2752 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2754 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2756 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2758 /* When bitmaps are already initialized, just clear them. */
2759 if (bb_info->use.obstack)
2761 bitmap_clear (&bb_info->def);
2762 bitmap_clear (&bb_info->use);
2764 else
2766 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2767 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2768 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2769 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2773 df_word_lr->optional_p = true;
2777 /* Reset the global solution for recalculation. */
2779 static void
2780 df_word_lr_reset (bitmap all_blocks)
2782 unsigned int bb_index;
2783 bitmap_iterator bi;
2785 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2787 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2788 gcc_assert (bb_info);
2789 bitmap_clear (&bb_info->in);
2790 bitmap_clear (&bb_info->out);
2794 /* Examine REF, and if it is for a reg we're interested in, set or
2795 clear the bits corresponding to its subwords from the bitmap
2796 according to IS_SET. LIVE is the bitmap we should update. We do
2797 not track hard regs or pseudos of any size other than 2 *
2798 UNITS_PER_WORD.
2799 We return true if we changed the bitmap, or if we encountered a register
2800 we're not tracking. */
2802 bool
2803 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2805 rtx orig_reg = DF_REF_REG (ref);
2806 rtx reg = orig_reg;
2807 machine_mode reg_mode;
2808 unsigned regno;
2809 /* Left at -1 for whole accesses. */
2810 int which_subword = -1;
2811 bool changed = false;
2813 if (GET_CODE (reg) == SUBREG)
2814 reg = SUBREG_REG (orig_reg);
2815 regno = REGNO (reg);
2816 reg_mode = GET_MODE (reg);
2817 if (regno < FIRST_PSEUDO_REGISTER
2818 || maybe_ne (GET_MODE_SIZE (reg_mode), 2 * UNITS_PER_WORD))
2819 return true;
2821 if (GET_CODE (orig_reg) == SUBREG
2822 && read_modify_subreg_p (orig_reg))
2824 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2825 if (subreg_lowpart_p (orig_reg))
2826 which_subword = 0;
2827 else
2828 which_subword = 1;
2830 if (is_set)
2832 if (which_subword != 1)
2833 changed |= bitmap_set_bit (live, regno * 2);
2834 if (which_subword != 0)
2835 changed |= bitmap_set_bit (live, regno * 2 + 1);
2837 else
2839 if (which_subword != 1)
2840 changed |= bitmap_clear_bit (live, regno * 2);
2841 if (which_subword != 0)
2842 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2844 return changed;
2847 /* Compute local live register info for basic block BB. */
2849 static void
2850 df_word_lr_bb_local_compute (unsigned int bb_index)
2852 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2853 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2854 rtx_insn *insn;
2855 df_ref def, use;
2857 /* Ensure that artificial refs don't contain references to pseudos. */
2858 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2859 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2861 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2862 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2864 FOR_BB_INSNS_REVERSE (bb, insn)
2866 if (!NONDEBUG_INSN_P (insn))
2867 continue;
2869 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2870 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2871 /* If the def is to only part of the reg, it does
2872 not kill the other defs that reach here. */
2873 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2875 df_word_lr_mark_ref (def, true, &bb_info->def);
2876 df_word_lr_mark_ref (def, false, &bb_info->use);
2878 FOR_EACH_INSN_INFO_USE (use, insn_info)
2879 df_word_lr_mark_ref (use, true, &bb_info->use);
2884 /* Compute local live register info for each basic block within BLOCKS. */
2886 static void
2887 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2889 unsigned int bb_index;
2890 bitmap_iterator bi;
2892 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2894 if (bb_index == EXIT_BLOCK)
2896 unsigned regno;
2897 bitmap_iterator bi;
2898 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2899 regno, bi)
2900 gcc_unreachable ();
2902 else
2903 df_word_lr_bb_local_compute (bb_index);
2906 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2910 /* Initialize the solution vectors. */
2912 static void
2913 df_word_lr_init (bitmap all_blocks)
2915 unsigned int bb_index;
2916 bitmap_iterator bi;
2918 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2920 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2921 bitmap_copy (&bb_info->in, &bb_info->use);
2922 bitmap_clear (&bb_info->out);
2927 /* Confluence function that ignores fake edges. */
2929 static bool
2930 df_word_lr_confluence_n (edge e)
2932 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2933 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2935 return bitmap_ior_into (op1, op2);
2939 /* Transfer function. */
2941 static bool
2942 df_word_lr_transfer_function (int bb_index)
2944 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2945 bitmap in = &bb_info->in;
2946 bitmap out = &bb_info->out;
2947 bitmap use = &bb_info->use;
2948 bitmap def = &bb_info->def;
2950 return bitmap_ior_and_compl (in, use, out, def);
2954 /* Free all storage associated with the problem. */
2956 static void
2957 df_word_lr_free (void)
2959 struct df_word_lr_problem_data *problem_data
2960 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2962 if (df_word_lr->block_info)
2964 df_word_lr->block_info_size = 0;
2965 free (df_word_lr->block_info);
2966 df_word_lr->block_info = NULL;
2969 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2970 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2971 free (problem_data);
2972 free (df_word_lr);
2976 /* Debugging info at top of bb. */
2978 static void
2979 df_word_lr_top_dump (basic_block bb, FILE *file)
2981 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2982 if (!bb_info)
2983 return;
2985 fprintf (file, ";; blr in \t");
2986 df_print_word_regset (file, &bb_info->in);
2987 fprintf (file, ";; blr use \t");
2988 df_print_word_regset (file, &bb_info->use);
2989 fprintf (file, ";; blr def \t");
2990 df_print_word_regset (file, &bb_info->def);
2994 /* Debugging info at bottom of bb. */
2996 static void
2997 df_word_lr_bottom_dump (basic_block bb, FILE *file)
2999 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3000 if (!bb_info)
3001 return;
3003 fprintf (file, ";; blr out \t");
3004 df_print_word_regset (file, &bb_info->out);
3008 /* All of the information associated with every instance of the problem. */
3010 static const struct df_problem problem_WORD_LR =
3012 DF_WORD_LR, /* Problem id. */
3013 DF_BACKWARD, /* Direction. */
3014 df_word_lr_alloc, /* Allocate the problem specific data. */
3015 df_word_lr_reset, /* Reset global information. */
3016 df_word_lr_free_bb_info, /* Free basic block info. */
3017 df_word_lr_local_compute, /* Local compute function. */
3018 df_word_lr_init, /* Init the solution specific data. */
3019 df_worklist_dataflow, /* Worklist solver. */
3020 NULL, /* Confluence operator 0. */
3021 df_word_lr_confluence_n, /* Confluence operator n. */
3022 df_word_lr_transfer_function, /* Transfer function. */
3023 NULL, /* Finalize function. */
3024 df_word_lr_free, /* Free all of the problem information. */
3025 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
3026 NULL, /* Debugging. */
3027 df_word_lr_top_dump, /* Debugging start block. */
3028 df_word_lr_bottom_dump, /* Debugging end block. */
3029 NULL, /* Debugging start insn. */
3030 NULL, /* Debugging end insn. */
3031 NULL, /* Incremental solution verify start. */
3032 NULL, /* Incremental solution verify end. */
3033 NULL, /* Dependent problem. */
3034 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */
3035 TV_DF_WORD_LR, /* Timing variable. */
3036 false /* Reset blocks on dropping out of blocks_to_analyze. */
3040 /* Create a new DATAFLOW instance and add it to an existing instance
3041 of DF. The returned structure is what is used to get at the
3042 solution. */
3044 void
3045 df_word_lr_add_problem (void)
3047 df_add_problem (&problem_WORD_LR);
3048 /* These will be initialized when df_scan_blocks processes each
3049 block. */
3050 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3054 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
3055 any bits, which is used by the caller to determine whether a set is
3056 necessary. We also return true if there are other reasons not to delete
3057 an insn. */
3059 bool
3060 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3062 bool changed = false;
3063 df_ref def;
3065 FOR_EACH_INSN_DEF (def, insn)
3066 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3067 changed = true;
3068 else
3069 changed |= df_word_lr_mark_ref (def, false, live);
3070 return changed;
3074 /* Simulate the effects of the uses of INSN on LIVE. */
3076 void
3077 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3079 df_ref use;
3081 FOR_EACH_INSN_USE (use, insn)
3082 df_word_lr_mark_ref (use, true, live);
3085 /*----------------------------------------------------------------------------
3086 This problem computes REG_DEAD and REG_UNUSED notes.
3087 ----------------------------------------------------------------------------*/
3089 static void
3090 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3092 df_note->optional_p = true;
3095 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
3096 static void
3097 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
3099 if (dump_file)
3101 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3102 print_rtl (dump_file, note);
3103 fprintf (dump_file, "\n");
3108 /* After reg-stack, the x86 floating point stack regs are difficult to
3109 analyze because of all of the pushes, pops and rotations. Thus, we
3110 just leave the notes alone. */
3112 #ifdef STACK_REGS
3113 static inline bool
3114 df_ignore_stack_reg (int regno)
3116 return regstack_completed
3117 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3119 #else
3120 static inline bool
3121 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3123 return false;
3125 #endif
3128 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
3130 static void
3131 df_remove_dead_and_unused_notes (rtx_insn *insn)
3133 rtx *pprev = &REG_NOTES (insn);
3134 rtx link = *pprev;
3136 while (link)
3138 switch (REG_NOTE_KIND (link))
3140 case REG_DEAD:
3141 /* After reg-stack, we need to ignore any unused notes
3142 for the stack registers. */
3143 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3145 pprev = &XEXP (link, 1);
3146 link = *pprev;
3148 else
3150 rtx next = XEXP (link, 1);
3151 if (REG_DEAD_DEBUGGING)
3152 df_print_note ("deleting: ", insn, link);
3153 free_EXPR_LIST_node (link);
3154 *pprev = link = next;
3156 break;
3158 case REG_UNUSED:
3159 /* After reg-stack, we need to ignore any unused notes
3160 for the stack registers. */
3161 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3163 pprev = &XEXP (link, 1);
3164 link = *pprev;
3166 else
3168 rtx next = XEXP (link, 1);
3169 if (REG_DEAD_DEBUGGING)
3170 df_print_note ("deleting: ", insn, link);
3171 free_EXPR_LIST_node (link);
3172 *pprev = link = next;
3174 break;
3176 default:
3177 pprev = &XEXP (link, 1);
3178 link = *pprev;
3179 break;
3184 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
3185 as the bitmap of currently live registers. */
3187 static void
3188 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3190 rtx *pprev = &REG_NOTES (insn);
3191 rtx link = *pprev;
3193 while (link)
3195 switch (REG_NOTE_KIND (link))
3197 case REG_EQUAL:
3198 case REG_EQUIV:
3200 /* Remove the notes that refer to dead registers. As we have at most
3201 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3202 so we need to purge the complete EQ_USES vector when removing
3203 the note using df_notes_rescan. */
3204 df_ref use;
3205 bool deleted = false;
3207 FOR_EACH_INSN_EQ_USE (use, insn)
3208 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
3209 && DF_REF_LOC (use)
3210 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3211 && !bitmap_bit_p (live, DF_REF_REGNO (use))
3212 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3214 deleted = true;
3215 break;
3217 if (deleted)
3219 rtx next;
3220 if (REG_DEAD_DEBUGGING)
3221 df_print_note ("deleting: ", insn, link);
3222 next = XEXP (link, 1);
3223 free_EXPR_LIST_node (link);
3224 *pprev = link = next;
3225 df_notes_rescan (insn);
3227 else
3229 pprev = &XEXP (link, 1);
3230 link = *pprev;
3232 break;
3235 default:
3236 pprev = &XEXP (link, 1);
3237 link = *pprev;
3238 break;
3243 /* Set a NOTE_TYPE note for REG in INSN. */
3245 static inline void
3246 df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3248 gcc_checking_assert (!DEBUG_INSN_P (insn));
3249 add_reg_note (insn, note_type, reg);
3252 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3253 arguments. Return true if the register value described by MWS's
3254 mw_reg is known to be completely unused, and if mw_reg can therefore
3255 be used in a REG_UNUSED note. */
3257 static bool
3258 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3259 bitmap live, bitmap artificial_uses)
3261 unsigned int r;
3263 /* If MWS describes a partial reference, create REG_UNUSED notes for
3264 individual hard registers. */
3265 if (mws->flags & DF_REF_PARTIAL)
3266 return false;
3268 /* Likewise if some part of the register is used. */
3269 for (r = mws->start_regno; r <= mws->end_regno; r++)
3270 if (bitmap_bit_p (live, r)
3271 || bitmap_bit_p (artificial_uses, r))
3272 return false;
3274 gcc_assert (REG_P (mws->mw_reg));
3275 return true;
3279 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3280 based on the bits in LIVE. Do not generate notes for registers in
3281 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3282 not generated if the reg is both read and written by the
3283 instruction.
3286 static void
3287 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3288 bitmap live, bitmap do_not_gen,
3289 bitmap artificial_uses,
3290 struct dead_debug_local *debug)
3292 unsigned int r;
3294 if (REG_DEAD_DEBUGGING && dump_file)
3295 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3296 mws->start_regno, mws->end_regno);
3298 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3300 unsigned int regno = mws->start_regno;
3301 df_set_note (REG_UNUSED, insn, mws->mw_reg);
3302 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3304 if (REG_DEAD_DEBUGGING)
3305 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3307 bitmap_set_bit (do_not_gen, regno);
3308 /* Only do this if the value is totally dead. */
3310 else
3311 for (r = mws->start_regno; r <= mws->end_regno; r++)
3313 if (!bitmap_bit_p (live, r)
3314 && !bitmap_bit_p (artificial_uses, r))
3316 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3317 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3318 if (REG_DEAD_DEBUGGING)
3319 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3321 bitmap_set_bit (do_not_gen, r);
3326 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3327 arguments. Return true if the register value described by MWS's
3328 mw_reg is known to be completely dead, and if mw_reg can therefore
3329 be used in a REG_DEAD note. */
3331 static bool
3332 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3333 bitmap live, bitmap artificial_uses,
3334 bitmap do_not_gen)
3336 unsigned int r;
3338 /* If MWS describes a partial reference, create REG_DEAD notes for
3339 individual hard registers. */
3340 if (mws->flags & DF_REF_PARTIAL)
3341 return false;
3343 /* Likewise if some part of the register is not dead. */
3344 for (r = mws->start_regno; r <= mws->end_regno; r++)
3345 if (bitmap_bit_p (live, r)
3346 || bitmap_bit_p (artificial_uses, r)
3347 || bitmap_bit_p (do_not_gen, r))
3348 return false;
3350 gcc_assert (REG_P (mws->mw_reg));
3351 return true;
3354 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3355 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3356 from being set if the instruction both reads and writes the
3357 register. */
3359 static void
3360 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3361 bitmap live, bitmap do_not_gen,
3362 bitmap artificial_uses, bool *added_notes_p)
3364 unsigned int r;
3365 bool is_debug = *added_notes_p;
3367 *added_notes_p = false;
3369 if (REG_DEAD_DEBUGGING && dump_file)
3371 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3372 mws->start_regno, mws->end_regno);
3373 df_print_regset (dump_file, do_not_gen);
3374 fprintf (dump_file, " live =");
3375 df_print_regset (dump_file, live);
3376 fprintf (dump_file, " artificial uses =");
3377 df_print_regset (dump_file, artificial_uses);
3380 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3382 if (is_debug)
3384 *added_notes_p = true;
3385 return;
3387 /* Add a dead note for the entire multi word register. */
3388 df_set_note (REG_DEAD, insn, mws->mw_reg);
3389 if (REG_DEAD_DEBUGGING)
3390 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3392 else
3394 for (r = mws->start_regno; r <= mws->end_regno; r++)
3395 if (!bitmap_bit_p (live, r)
3396 && !bitmap_bit_p (artificial_uses, r)
3397 && !bitmap_bit_p (do_not_gen, r))
3399 if (is_debug)
3401 *added_notes_p = true;
3402 return;
3404 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3405 if (REG_DEAD_DEBUGGING)
3406 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3409 return;
3413 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3414 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3416 static void
3417 df_create_unused_note (rtx_insn *insn, df_ref def,
3418 bitmap live, bitmap artificial_uses,
3419 struct dead_debug_local *debug)
3421 unsigned int dregno = DF_REF_REGNO (def);
3423 if (REG_DEAD_DEBUGGING && dump_file)
3425 fprintf (dump_file, " regular looking at def ");
3426 df_ref_debug (def, dump_file);
3429 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3430 || bitmap_bit_p (live, dregno)
3431 || bitmap_bit_p (artificial_uses, dregno)
3432 || df_ignore_stack_reg (dregno)))
3434 rtx reg = (DF_REF_LOC (def))
3435 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3436 df_set_note (REG_UNUSED, insn, reg);
3437 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3438 if (REG_DEAD_DEBUGGING)
3439 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3442 return;
3446 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3447 info: lifetime, bb, and number of defs and uses for basic block
3448 BB. The three bitvectors are scratch regs used here. */
3450 static void
3451 df_note_bb_compute (unsigned int bb_index,
3452 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3454 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3455 rtx_insn *insn;
3456 df_ref def, use;
3457 struct dead_debug_local debug;
3459 dead_debug_local_init (&debug, NULL, NULL);
3461 bitmap_copy (live, df_get_live_out (bb));
3462 bitmap_clear (artificial_uses);
3464 if (REG_DEAD_DEBUGGING && dump_file)
3466 fprintf (dump_file, "live at bottom ");
3467 df_print_regset (dump_file, live);
3470 /* Process the artificial defs and uses at the bottom of the block
3471 to begin processing. */
3472 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3474 if (REG_DEAD_DEBUGGING && dump_file)
3475 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3477 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3478 bitmap_clear_bit (live, DF_REF_REGNO (def));
3481 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3482 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3484 unsigned int regno = DF_REF_REGNO (use);
3485 bitmap_set_bit (live, regno);
3487 /* Notes are not generated for any of the artificial registers
3488 at the bottom of the block. */
3489 bitmap_set_bit (artificial_uses, regno);
3492 if (REG_DEAD_DEBUGGING && dump_file)
3494 fprintf (dump_file, "live before artificials out ");
3495 df_print_regset (dump_file, live);
3498 FOR_BB_INSNS_REVERSE (bb, insn)
3500 if (!INSN_P (insn))
3501 continue;
3503 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3504 df_mw_hardreg *mw;
3505 int debug_insn;
3507 debug_insn = DEBUG_INSN_P (insn);
3509 bitmap_clear (do_not_gen);
3510 df_remove_dead_and_unused_notes (insn);
3512 /* Process the defs. */
3513 if (CALL_P (insn))
3515 if (REG_DEAD_DEBUGGING && dump_file)
3517 fprintf (dump_file, "processing call %d\n live =",
3518 INSN_UID (insn));
3519 df_print_regset (dump_file, live);
3522 /* We only care about real sets for calls. Clobbers cannot
3523 be depended on to really die. */
3524 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3525 if ((DF_MWS_REG_DEF_P (mw))
3526 && !df_ignore_stack_reg (mw->start_regno))
3527 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3528 artificial_uses, &debug);
3530 /* All of the defs except the return value are some sort of
3531 clobber. This code is for the return. */
3532 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3534 unsigned int dregno = DF_REF_REGNO (def);
3535 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3537 df_create_unused_note (insn,
3538 def, live, artificial_uses, &debug);
3539 bitmap_set_bit (do_not_gen, dregno);
3542 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3543 bitmap_clear_bit (live, dregno);
3546 else
3548 /* Regular insn. */
3549 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3550 if (DF_MWS_REG_DEF_P (mw))
3551 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3552 artificial_uses, &debug);
3554 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3556 unsigned int dregno = DF_REF_REGNO (def);
3557 df_create_unused_note (insn,
3558 def, live, artificial_uses, &debug);
3560 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3561 bitmap_set_bit (do_not_gen, dregno);
3563 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3564 bitmap_clear_bit (live, dregno);
3568 /* Process the uses. */
3569 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3570 if (DF_MWS_REG_USE_P (mw)
3571 && !df_ignore_stack_reg (mw->start_regno))
3573 bool really_add_notes = debug_insn != 0;
3575 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3576 artificial_uses,
3577 &really_add_notes);
3579 if (really_add_notes)
3580 debug_insn = -1;
3583 FOR_EACH_INSN_INFO_USE (use, insn_info)
3585 unsigned int uregno = DF_REF_REGNO (use);
3587 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3589 fprintf (dump_file, " regular looking at use ");
3590 df_ref_debug (use, dump_file);
3593 if (!bitmap_bit_p (live, uregno))
3595 if (debug_insn)
3597 if (debug_insn > 0)
3599 /* We won't add REG_UNUSED or REG_DEAD notes for
3600 these, so we don't have to mess with them in
3601 debug insns either. */
3602 if (!bitmap_bit_p (artificial_uses, uregno)
3603 && !df_ignore_stack_reg (uregno))
3604 dead_debug_add (&debug, use, uregno);
3605 continue;
3607 break;
3609 else
3610 dead_debug_insert_temp (&debug, uregno, insn,
3611 DEBUG_TEMP_BEFORE_WITH_REG);
3613 if ( (!(DF_REF_FLAGS (use)
3614 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3615 && (!bitmap_bit_p (do_not_gen, uregno))
3616 && (!bitmap_bit_p (artificial_uses, uregno))
3617 && (!df_ignore_stack_reg (uregno)))
3619 rtx reg = (DF_REF_LOC (use))
3620 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3621 df_set_note (REG_DEAD, insn, reg);
3623 if (REG_DEAD_DEBUGGING)
3624 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3626 /* This register is now live. */
3627 bitmap_set_bit (live, uregno);
3631 df_remove_dead_eq_notes (insn, live);
3633 if (debug_insn == -1)
3635 /* ??? We could probably do better here, replacing dead
3636 registers with their definitions. */
3637 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3638 df_insn_rescan_debug_internal (insn);
3642 dead_debug_local_finish (&debug, NULL);
3646 /* Compute register info: lifetime, bb, and number of defs and uses. */
3647 static void
3648 df_note_compute (bitmap all_blocks)
3650 unsigned int bb_index;
3651 bitmap_iterator bi;
3652 bitmap_head live, do_not_gen, artificial_uses;
3654 bitmap_initialize (&live, &df_bitmap_obstack);
3655 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3656 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3658 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3660 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3661 pseudos in debug insns because we don't always (re)visit blocks
3662 with death points after visiting dead uses. Even changing this
3663 loop to postorder would still leave room for visiting a death
3664 point before visiting a subsequent debug use. */
3665 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3668 bitmap_clear (&live);
3669 bitmap_clear (&do_not_gen);
3670 bitmap_clear (&artificial_uses);
3674 /* Free all storage associated with the problem. */
3676 static void
3677 df_note_free (void)
3679 free (df_note);
3683 /* All of the information associated every instance of the problem. */
3685 static const struct df_problem problem_NOTE =
3687 DF_NOTE, /* Problem id. */
3688 DF_NONE, /* Direction. */
3689 df_note_alloc, /* Allocate the problem specific data. */
3690 NULL, /* Reset global information. */
3691 NULL, /* Free basic block info. */
3692 df_note_compute, /* Local compute function. */
3693 NULL, /* Init the solution specific data. */
3694 NULL, /* Iterative solver. */
3695 NULL, /* Confluence operator 0. */
3696 NULL, /* Confluence operator n. */
3697 NULL, /* Transfer function. */
3698 NULL, /* Finalize function. */
3699 df_note_free, /* Free all of the problem information. */
3700 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3701 NULL, /* Debugging. */
3702 NULL, /* Debugging start block. */
3703 NULL, /* Debugging end block. */
3704 NULL, /* Debugging start insn. */
3705 NULL, /* Debugging end insn. */
3706 NULL, /* Incremental solution verify start. */
3707 NULL, /* Incremental solution verify end. */
3708 &problem_LR, /* Dependent problem. */
3709 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3710 TV_DF_NOTE, /* Timing variable. */
3711 false /* Reset blocks on dropping out of blocks_to_analyze. */
3715 /* Create a new DATAFLOW instance and add it to an existing instance
3716 of DF. The returned structure is what is used to get at the
3717 solution. */
3719 void
3720 df_note_add_problem (void)
3722 df_add_problem (&problem_NOTE);
3728 /*----------------------------------------------------------------------------
3729 Functions for simulating the effects of single insns.
3731 You can either simulate in the forwards direction, starting from
3732 the top of a block or the backwards direction from the end of the
3733 block. If you go backwards, defs are examined first to clear bits,
3734 then uses are examined to set bits. If you go forwards, defs are
3735 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3736 are examined to clear bits. In either case, the result of examining
3737 a def can be undone (respectively by a use or a REG_UNUSED note).
3739 If you start at the top of the block, use one of DF_LIVE_IN or
3740 DF_LR_IN. If you start at the bottom of the block use one of
3741 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3742 THEY WILL BE DESTROYED.
3743 ----------------------------------------------------------------------------*/
3746 /* Find the set of DEFs for INSN. */
3748 void
3749 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3751 df_ref def;
3753 FOR_EACH_INSN_DEF (def, insn)
3754 bitmap_set_bit (defs, DF_REF_REGNO (def));
3757 /* Find the set of uses for INSN. This includes partial defs. */
3759 static void
3760 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3762 df_ref def, use;
3763 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3765 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3766 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3767 bitmap_set_bit (uses, DF_REF_REGNO (def));
3768 FOR_EACH_INSN_INFO_USE (use, insn_info)
3769 bitmap_set_bit (uses, DF_REF_REGNO (use));
3772 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3774 void
3775 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3777 df_ref def;
3779 FOR_EACH_INSN_DEF (def, insn)
3780 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3781 bitmap_set_bit (defs, DF_REF_REGNO (def));
3785 /* Simulate the effects of the defs of INSN on LIVE. */
3787 void
3788 df_simulate_defs (rtx_insn *insn, bitmap live)
3790 df_ref def;
3792 FOR_EACH_INSN_DEF (def, insn)
3794 unsigned int dregno = DF_REF_REGNO (def);
3796 /* If the def is to only part of the reg, it does
3797 not kill the other defs that reach here. */
3798 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3799 bitmap_clear_bit (live, dregno);
3804 /* Simulate the effects of the uses of INSN on LIVE. */
3806 void
3807 df_simulate_uses (rtx_insn *insn, bitmap live)
3809 df_ref use;
3811 if (DEBUG_INSN_P (insn))
3812 return;
3814 FOR_EACH_INSN_USE (use, insn)
3815 /* Add use to set of uses in this BB. */
3816 bitmap_set_bit (live, DF_REF_REGNO (use));
3820 /* Add back the always live regs in BB to LIVE. */
3822 static inline void
3823 df_simulate_fixup_sets (basic_block bb, bitmap live)
3825 /* These regs are considered always live so if they end up dying
3826 because of some def, we need to bring the back again. */
3827 if (bb_has_eh_pred (bb))
3828 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3829 else
3830 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3834 /*----------------------------------------------------------------------------
3835 The following three functions are used only for BACKWARDS scanning:
3836 i.e. they process the defs before the uses.
3838 df_simulate_initialize_backwards should be called first with a
3839 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3840 df_simulate_one_insn_backwards should be called for each insn in
3841 the block, starting with the last one. Finally,
3842 df_simulate_finalize_backwards can be called to get a new value
3843 of the sets at the top of the block (this is rarely used).
3844 ----------------------------------------------------------------------------*/
3846 /* Apply the artificial uses and defs at the end of BB in a backwards
3847 direction. */
3849 void
3850 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3852 df_ref def, use;
3853 int bb_index = bb->index;
3855 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3856 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3857 bitmap_clear_bit (live, DF_REF_REGNO (def));
3859 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3860 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3861 bitmap_set_bit (live, DF_REF_REGNO (use));
3865 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3867 void
3868 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3870 if (!NONDEBUG_INSN_P (insn))
3871 return;
3873 df_simulate_defs (insn, live);
3874 df_simulate_uses (insn, live);
3875 df_simulate_fixup_sets (bb, live);
3879 /* Apply the artificial uses and defs at the top of BB in a backwards
3880 direction. */
3882 void
3883 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3885 df_ref def;
3886 #ifdef EH_USES
3887 df_ref use;
3888 #endif
3889 int bb_index = bb->index;
3891 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3892 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3893 bitmap_clear_bit (live, DF_REF_REGNO (def));
3895 #ifdef EH_USES
3896 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3897 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3898 bitmap_set_bit (live, DF_REF_REGNO (use));
3899 #endif
3901 /*----------------------------------------------------------------------------
3902 The following three functions are used only for FORWARDS scanning:
3903 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3904 Thus it is important to add the DF_NOTES problem to the stack of
3905 problems computed before using these functions.
3907 df_simulate_initialize_forwards should be called first with a
3908 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3909 df_simulate_one_insn_forwards should be called for each insn in
3910 the block, starting with the first one.
3911 ----------------------------------------------------------------------------*/
3913 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3914 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3915 defs live. */
3917 void
3918 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3920 df_ref def;
3921 int bb_index = bb->index;
3923 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3924 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3925 bitmap_set_bit (live, DF_REF_REGNO (def));
3928 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3930 void
3931 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3933 rtx link;
3934 if (! INSN_P (insn))
3935 return;
3937 /* Make sure that DF_NOTE really is an active df problem. */
3938 gcc_assert (df_note);
3940 /* Note that this is the opposite as how the problem is defined, because
3941 in the LR problem defs _kill_ liveness. However, they do so backwards,
3942 while here the scan is performed forwards! So, first assume that the
3943 def is live, and if this is not true REG_UNUSED notes will rectify the
3944 situation. */
3945 df_simulate_find_noclobber_defs (insn, live);
3947 /* Clear all of the registers that go dead. */
3948 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3950 switch (REG_NOTE_KIND (link))
3952 case REG_DEAD:
3953 case REG_UNUSED:
3955 rtx reg = XEXP (link, 0);
3956 bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
3958 break;
3959 default:
3960 break;
3963 df_simulate_fixup_sets (bb, live);
3966 /* Used by the next two functions to encode information about the
3967 memory references we found. */
3968 #define MEMREF_NORMAL 1
3969 #define MEMREF_VOLATILE 2
3971 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3973 static int
3974 find_memory (rtx_insn *insn)
3976 int flags = 0;
3977 subrtx_iterator::array_type array;
3978 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3980 const_rtx x = *iter;
3981 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3982 flags |= MEMREF_VOLATILE;
3983 else if (MEM_P (x))
3985 if (MEM_VOLATILE_P (x))
3986 flags |= MEMREF_VOLATILE;
3987 else if (!MEM_READONLY_P (x))
3988 flags |= MEMREF_NORMAL;
3991 return flags;
3994 /* A subroutine of can_move_insns_across_p called through note_stores.
3995 DATA points to an integer in which we set either the bit for
3996 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3997 of either kind. */
3999 static void
4000 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4001 void *data ATTRIBUTE_UNUSED)
4003 int *pflags = (int *)data;
4004 if (GET_CODE (x) == SUBREG)
4005 x = XEXP (x, 0);
4006 /* Treat stores to SP as stores to memory, this will prevent problems
4007 when there are references to the stack frame. */
4008 if (x == stack_pointer_rtx)
4009 *pflags |= MEMREF_VOLATILE;
4010 if (!MEM_P (x))
4011 return;
4012 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4015 /* Scan BB backwards, using df_simulate functions to keep track of
4016 lifetimes, up to insn POINT. The result is stored in LIVE. */
4018 void
4019 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4021 rtx_insn *insn;
4022 bitmap_copy (live, df_get_live_out (bb));
4023 df_simulate_initialize_backwards (bb, live);
4025 /* Scan and update life information until we reach the point we're
4026 interested in. */
4027 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4028 df_simulate_one_insn_backwards (bb, insn, live);
4031 /* Return true if it is safe to move a group of insns, described by
4032 the range FROM to TO, backwards across another group of insns,
4033 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4034 are no insns between ACROSS_TO and FROM, but they may be in
4035 different basic blocks; MERGE_BB is the block from which the
4036 insns will be moved. The caller must pass in a regset MERGE_LIVE
4037 which specifies the registers live after TO.
4039 This function may be called in one of two cases: either we try to
4040 move identical instructions from all successor blocks into their
4041 predecessor, or we try to move from only one successor block. If
4042 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4043 the second case. It should contain a set of registers live at the
4044 end of ACROSS_TO which must not be clobbered by moving the insns.
4045 In that case, we're also more careful about moving memory references
4046 and trapping insns.
4048 We return false if it is not safe to move the entire group, but it
4049 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4050 is set to point at the last moveable insn in such a case. */
4052 bool
4053 can_move_insns_across (rtx_insn *from, rtx_insn *to,
4054 rtx_insn *across_from, rtx_insn *across_to,
4055 basic_block merge_bb, regset merge_live,
4056 regset other_branch_live, rtx_insn **pmove_upto)
4058 rtx_insn *insn, *next, *max_to;
4059 bitmap merge_set, merge_use, local_merge_live;
4060 bitmap test_set, test_use;
4061 unsigned i, fail = 0;
4062 bitmap_iterator bi;
4063 int memrefs_in_across = 0;
4064 int mem_sets_in_across = 0;
4065 bool trapping_insns_in_across = false;
4067 if (pmove_upto != NULL)
4068 *pmove_upto = NULL;
4070 /* Find real bounds, ignoring debug insns. */
4071 while (!NONDEBUG_INSN_P (from) && from != to)
4072 from = NEXT_INSN (from);
4073 while (!NONDEBUG_INSN_P (to) && from != to)
4074 to = PREV_INSN (to);
4076 for (insn = across_to; ; insn = next)
4078 if (CALL_P (insn))
4080 if (RTL_CONST_OR_PURE_CALL_P (insn))
4081 /* Pure functions can read from memory. Const functions can
4082 read from arguments that the ABI has forced onto the stack.
4083 Neither sort of read can be volatile. */
4084 memrefs_in_across |= MEMREF_NORMAL;
4085 else
4087 memrefs_in_across |= MEMREF_VOLATILE;
4088 mem_sets_in_across |= MEMREF_VOLATILE;
4091 if (NONDEBUG_INSN_P (insn))
4093 if (volatile_insn_p (PATTERN (insn)))
4094 return false;
4095 memrefs_in_across |= find_memory (insn);
4096 note_stores (PATTERN (insn), find_memory_stores,
4097 &mem_sets_in_across);
4098 /* This is used just to find sets of the stack pointer. */
4099 memrefs_in_across |= mem_sets_in_across;
4100 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4102 next = PREV_INSN (insn);
4103 if (insn == across_from)
4104 break;
4107 /* Collect:
4108 MERGE_SET = set of registers set in MERGE_BB
4109 MERGE_USE = set of registers used in MERGE_BB and live at its top
4110 MERGE_LIVE = set of registers live at the point inside the MERGE
4111 range that we've reached during scanning
4112 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4113 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4114 and live before ACROSS_FROM. */
4116 merge_set = BITMAP_ALLOC (&reg_obstack);
4117 merge_use = BITMAP_ALLOC (&reg_obstack);
4118 local_merge_live = BITMAP_ALLOC (&reg_obstack);
4119 test_set = BITMAP_ALLOC (&reg_obstack);
4120 test_use = BITMAP_ALLOC (&reg_obstack);
4122 /* Compute the set of registers set and used in the ACROSS range. */
4123 if (other_branch_live != NULL)
4124 bitmap_copy (test_use, other_branch_live);
4125 df_simulate_initialize_backwards (merge_bb, test_use);
4126 for (insn = across_to; ; insn = next)
4128 if (NONDEBUG_INSN_P (insn))
4130 df_simulate_find_defs (insn, test_set);
4131 df_simulate_defs (insn, test_use);
4132 df_simulate_uses (insn, test_use);
4134 next = PREV_INSN (insn);
4135 if (insn == across_from)
4136 break;
4139 /* Compute an upper bound for the amount of insns moved, by finding
4140 the first insn in MERGE that sets a register in TEST_USE, or uses
4141 a register in TEST_SET. We also check for calls, trapping operations,
4142 and memory references. */
4143 max_to = NULL;
4144 for (insn = from; ; insn = next)
4146 if (CALL_P (insn))
4147 break;
4148 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4149 break;
4150 if (NONDEBUG_INSN_P (insn))
4152 if (may_trap_or_fault_p (PATTERN (insn))
4153 && (trapping_insns_in_across
4154 || other_branch_live != NULL
4155 || volatile_insn_p (PATTERN (insn))))
4156 break;
4158 /* We cannot move memory stores past each other, or move memory
4159 reads past stores, at least not without tracking them and
4160 calling true_dependence on every pair.
4162 If there is no other branch and no memory references or
4163 sets in the ACROSS range, we can move memory references
4164 freely, even volatile ones.
4166 Otherwise, the rules are as follows: volatile memory
4167 references and stores can't be moved at all, and any type
4168 of memory reference can't be moved if there are volatile
4169 accesses or stores in the ACROSS range. That leaves
4170 normal reads, which can be moved, as the trapping case is
4171 dealt with elsewhere. */
4172 if (other_branch_live != NULL || memrefs_in_across != 0)
4174 int mem_ref_flags = 0;
4175 int mem_set_flags = 0;
4176 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
4177 mem_ref_flags = find_memory (insn);
4178 /* Catch sets of the stack pointer. */
4179 mem_ref_flags |= mem_set_flags;
4181 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4182 break;
4183 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4184 break;
4185 if (mem_set_flags != 0
4186 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4187 break;
4189 df_simulate_find_uses (insn, merge_use);
4190 /* We're only interested in uses which use a value live at
4191 the top, not one previously set in this block. */
4192 bitmap_and_compl_into (merge_use, merge_set);
4193 df_simulate_find_defs (insn, merge_set);
4194 if (bitmap_intersect_p (merge_set, test_use)
4195 || bitmap_intersect_p (merge_use, test_set))
4196 break;
4197 if (!HAVE_cc0 || !sets_cc0_p (insn))
4198 max_to = insn;
4200 next = NEXT_INSN (insn);
4201 if (insn == to)
4202 break;
4204 if (max_to != to)
4205 fail = 1;
4207 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4208 goto out;
4210 /* Now, lower this upper bound by also taking into account that
4211 a range of insns moved across ACROSS must not leave a register
4212 live at the end that will be clobbered in ACROSS. We need to
4213 find a point where TEST_SET & LIVE == 0.
4215 Insns in the MERGE range that set registers which are also set
4216 in the ACROSS range may still be moved as long as we also move
4217 later insns which use the results of the set, and make the
4218 register dead again. This is verified by the condition stated
4219 above. We only need to test it for registers that are set in
4220 the moved region.
4222 MERGE_LIVE is provided by the caller and holds live registers after
4223 TO. */
4224 bitmap_copy (local_merge_live, merge_live);
4225 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4226 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4228 /* We're not interested in registers that aren't set in the moved
4229 region at all. */
4230 bitmap_and_into (local_merge_live, merge_set);
4231 for (;;)
4233 if (NONDEBUG_INSN_P (insn))
4235 if (!bitmap_intersect_p (test_set, local_merge_live)
4236 && (!HAVE_cc0 || !sets_cc0_p (insn)))
4238 max_to = insn;
4239 break;
4242 df_simulate_one_insn_backwards (merge_bb, insn,
4243 local_merge_live);
4245 if (insn == from)
4247 fail = 1;
4248 goto out;
4250 insn = PREV_INSN (insn);
4253 if (max_to != to)
4254 fail = 1;
4256 if (pmove_upto)
4257 *pmove_upto = max_to;
4259 /* For small register class machines, don't lengthen lifetimes of
4260 hard registers before reload. */
4261 if (! reload_completed
4262 && targetm.small_register_classes_for_mode_p (VOIDmode))
4264 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4266 if (i < FIRST_PSEUDO_REGISTER
4267 && ! fixed_regs[i]
4268 && ! global_regs[i])
4270 fail = 1;
4271 break;
4276 out:
4277 BITMAP_FREE (merge_set);
4278 BITMAP_FREE (merge_use);
4279 BITMAP_FREE (local_merge_live);
4280 BITMAP_FREE (test_set);
4281 BITMAP_FREE (test_use);
4283 return !fail;
4287 /*----------------------------------------------------------------------------
4288 MULTIPLE DEFINITIONS
4290 Find the locations in the function reached by multiple definition sites
4291 for a live pseudo. In and out bitvectors are built for each basic
4292 block. They are restricted for efficiency to live registers.
4294 The gen and kill sets for the problem are obvious. Together they
4295 include all defined registers in a basic block; the gen set includes
4296 registers where a partial or conditional or may-clobber definition is
4297 last in the BB, while the kill set includes registers with a complete
4298 definition coming last. However, the computation of the dataflow
4299 itself is interesting.
4301 The idea behind it comes from SSA form's iterated dominance frontier
4302 criterion for inserting PHI functions. Just like in that case, we can use
4303 the dominance frontier to find places where multiple definitions meet;
4304 a register X defined in a basic block BB1 has multiple definitions in
4305 basic blocks in BB1's dominance frontier.
4307 So, the in-set of a basic block BB2 is not just the union of the
4308 out-sets of BB2's predecessors, but includes some more bits that come
4309 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4310 the previous paragraph). I called this set the init-set of BB2.
4312 (Note: I actually use the kill-set only to build the init-set.
4313 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4315 For example, if you have
4317 BB1 : r10 = 0
4318 r11 = 0
4319 if <...> goto BB2 else goto BB3;
4321 BB2 : r10 = 1
4322 r12 = 1
4323 goto BB3;
4325 BB3 :
4327 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4328 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4329 not need to iterate the dominance frontier, because we do not insert
4330 anything like PHI functions there! Instead, dataflow will take care of
4331 propagating the information to BB3's successors.
4332 ---------------------------------------------------------------------------*/
4334 /* Private data used to verify the solution for this problem. */
4335 struct df_md_problem_data
4337 /* An obstack for the bitmaps we need for this problem. */
4338 bitmap_obstack md_bitmaps;
4341 /* Scratch var used by transfer functions. This is used to do md analysis
4342 only for live registers. */
4343 static bitmap_head df_md_scratch;
4346 static void
4347 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4348 void *vbb_info)
4350 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4351 if (bb_info)
4353 bitmap_clear (&bb_info->kill);
4354 bitmap_clear (&bb_info->gen);
4355 bitmap_clear (&bb_info->init);
4356 bitmap_clear (&bb_info->in);
4357 bitmap_clear (&bb_info->out);
4362 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4363 not touched unless the block is new. */
4365 static void
4366 df_md_alloc (bitmap all_blocks)
4368 unsigned int bb_index;
4369 bitmap_iterator bi;
4370 struct df_md_problem_data *problem_data;
4372 df_grow_bb_info (df_md);
4373 if (df_md->problem_data)
4374 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4375 else
4377 problem_data = XNEW (struct df_md_problem_data);
4378 df_md->problem_data = problem_data;
4379 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4381 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4383 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4385 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4386 /* When bitmaps are already initialized, just clear them. */
4387 if (bb_info->init.obstack)
4389 bitmap_clear (&bb_info->init);
4390 bitmap_clear (&bb_info->gen);
4391 bitmap_clear (&bb_info->kill);
4392 bitmap_clear (&bb_info->in);
4393 bitmap_clear (&bb_info->out);
4395 else
4397 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4398 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4399 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4400 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4401 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4405 df_md->optional_p = true;
4408 /* Add the effect of the top artificial defs of BB to the multiple definitions
4409 bitmap LOCAL_MD. */
4411 void
4412 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4414 int bb_index = bb->index;
4415 df_ref def;
4416 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4417 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4419 unsigned int dregno = DF_REF_REGNO (def);
4420 if (DF_REF_FLAGS (def)
4421 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4422 bitmap_set_bit (local_md, dregno);
4423 else
4424 bitmap_clear_bit (local_md, dregno);
4429 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4430 LOCAL_MD. */
4432 void
4433 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4434 bitmap local_md)
4436 df_ref def;
4438 FOR_EACH_INSN_DEF (def, insn)
4440 unsigned int dregno = DF_REF_REGNO (def);
4441 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4442 || (dregno >= FIRST_PSEUDO_REGISTER))
4444 if (DF_REF_FLAGS (def)
4445 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4446 bitmap_set_bit (local_md, DF_REF_ID (def));
4447 else
4448 bitmap_clear_bit (local_md, DF_REF_ID (def));
4453 static void
4454 df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4455 df_ref def,
4456 int top_flag)
4458 bitmap_clear (&seen_in_insn);
4460 for (; def; def = DF_REF_NEXT_LOC (def))
4462 unsigned int dregno = DF_REF_REGNO (def);
4463 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4464 || (dregno >= FIRST_PSEUDO_REGISTER))
4465 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4467 if (!bitmap_bit_p (&seen_in_insn, dregno))
4469 if (DF_REF_FLAGS (def)
4470 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4472 bitmap_set_bit (&bb_info->gen, dregno);
4473 bitmap_clear_bit (&bb_info->kill, dregno);
4475 else
4477 /* When we find a clobber and a regular def,
4478 make sure the regular def wins. */
4479 bitmap_set_bit (&seen_in_insn, dregno);
4480 bitmap_set_bit (&bb_info->kill, dregno);
4481 bitmap_clear_bit (&bb_info->gen, dregno);
4489 /* Compute local multiple def info for basic block BB. */
4491 static void
4492 df_md_bb_local_compute (unsigned int bb_index)
4494 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4495 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4496 rtx_insn *insn;
4498 /* Artificials are only hard regs. */
4499 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4500 df_md_bb_local_compute_process_def (bb_info,
4501 df_get_artificial_defs (bb_index),
4502 DF_REF_AT_TOP);
4504 FOR_BB_INSNS (bb, insn)
4506 unsigned int uid = INSN_UID (insn);
4507 if (!INSN_P (insn))
4508 continue;
4510 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4513 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4514 df_md_bb_local_compute_process_def (bb_info,
4515 df_get_artificial_defs (bb_index),
4519 /* Compute local reaching def info for each basic block within BLOCKS. */
4521 static void
4522 df_md_local_compute (bitmap all_blocks)
4524 unsigned int bb_index, df_bb_index;
4525 bitmap_iterator bi1, bi2;
4526 basic_block bb;
4527 bitmap_head *frontiers;
4529 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4531 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4533 df_md_bb_local_compute (bb_index);
4536 bitmap_release (&seen_in_insn);
4538 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4539 FOR_ALL_BB_FN (bb, cfun)
4540 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4542 compute_dominance_frontiers (frontiers);
4544 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4545 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4547 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4548 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4550 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4551 if (bitmap_bit_p (all_blocks, df_bb_index))
4552 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4553 df_get_live_in (bb));
4557 FOR_ALL_BB_FN (bb, cfun)
4558 bitmap_clear (&frontiers[bb->index]);
4559 free (frontiers);
4563 /* Reset the global solution for recalculation. */
4565 static void
4566 df_md_reset (bitmap all_blocks)
4568 unsigned int bb_index;
4569 bitmap_iterator bi;
4571 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4573 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4574 gcc_assert (bb_info);
4575 bitmap_clear (&bb_info->in);
4576 bitmap_clear (&bb_info->out);
4580 static bool
4581 df_md_transfer_function (int bb_index)
4583 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4584 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4585 bitmap in = &bb_info->in;
4586 bitmap out = &bb_info->out;
4587 bitmap gen = &bb_info->gen;
4588 bitmap kill = &bb_info->kill;
4590 /* We need to use a scratch set here so that the value returned from this
4591 function invocation properly reflects whether the sets changed in a
4592 significant way; i.e. not just because the live set was anded in. */
4593 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4595 /* Multiple definitions of a register are not relevant if it is not
4596 live. Thus we trim the result to the places where it is live. */
4597 bitmap_and_into (in, df_get_live_in (bb));
4599 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4602 /* Initialize the solution bit vectors for problem. */
4604 static void
4605 df_md_init (bitmap all_blocks)
4607 unsigned int bb_index;
4608 bitmap_iterator bi;
4610 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4612 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4614 bitmap_copy (&bb_info->in, &bb_info->init);
4615 df_md_transfer_function (bb_index);
4619 static void
4620 df_md_confluence_0 (basic_block bb)
4622 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4623 bitmap_copy (&bb_info->in, &bb_info->init);
4626 /* In of target gets or of out of source. */
4628 static bool
4629 df_md_confluence_n (edge e)
4631 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4632 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4634 if (e->flags & EDGE_FAKE)
4635 return false;
4637 if (e->flags & EDGE_EH)
4638 return bitmap_ior_and_compl_into (op1, op2,
4639 regs_invalidated_by_call_regset);
4640 else
4641 return bitmap_ior_into (op1, op2);
4644 /* Free all storage associated with the problem. */
4646 static void
4647 df_md_free (void)
4649 struct df_md_problem_data *problem_data
4650 = (struct df_md_problem_data *) df_md->problem_data;
4652 bitmap_release (&df_md_scratch);
4653 bitmap_obstack_release (&problem_data->md_bitmaps);
4654 free (problem_data);
4655 df_md->problem_data = NULL;
4657 df_md->block_info_size = 0;
4658 free (df_md->block_info);
4659 df_md->block_info = NULL;
4660 free (df_md);
4664 /* Debugging info at top of bb. */
4666 static void
4667 df_md_top_dump (basic_block bb, FILE *file)
4669 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4670 if (!bb_info)
4671 return;
4673 fprintf (file, ";; md in \t");
4674 df_print_regset (file, &bb_info->in);
4675 fprintf (file, ";; md init \t");
4676 df_print_regset (file, &bb_info->init);
4677 fprintf (file, ";; md gen \t");
4678 df_print_regset (file, &bb_info->gen);
4679 fprintf (file, ";; md kill \t");
4680 df_print_regset (file, &bb_info->kill);
4683 /* Debugging info at bottom of bb. */
4685 static void
4686 df_md_bottom_dump (basic_block bb, FILE *file)
4688 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4689 if (!bb_info)
4690 return;
4692 fprintf (file, ";; md out \t");
4693 df_print_regset (file, &bb_info->out);
4696 static const struct df_problem problem_MD =
4698 DF_MD, /* Problem id. */
4699 DF_FORWARD, /* Direction. */
4700 df_md_alloc, /* Allocate the problem specific data. */
4701 df_md_reset, /* Reset global information. */
4702 df_md_free_bb_info, /* Free basic block info. */
4703 df_md_local_compute, /* Local compute function. */
4704 df_md_init, /* Init the solution specific data. */
4705 df_worklist_dataflow, /* Worklist solver. */
4706 df_md_confluence_0, /* Confluence operator 0. */
4707 df_md_confluence_n, /* Confluence operator n. */
4708 df_md_transfer_function, /* Transfer function. */
4709 NULL, /* Finalize function. */
4710 df_md_free, /* Free all of the problem information. */
4711 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4712 NULL, /* Debugging. */
4713 df_md_top_dump, /* Debugging start block. */
4714 df_md_bottom_dump, /* Debugging end block. */
4715 NULL, /* Debugging start insn. */
4716 NULL, /* Debugging end insn. */
4717 NULL, /* Incremental solution verify start. */
4718 NULL, /* Incremental solution verify end. */
4719 NULL, /* Dependent problem. */
4720 sizeof (struct df_md_bb_info),/* Size of entry of block_info array. */
4721 TV_DF_MD, /* Timing variable. */
4722 false /* Reset blocks on dropping out of blocks_to_analyze. */
4725 /* Create a new MD instance and add it to the existing instance
4726 of DF. */
4728 void
4729 df_md_add_problem (void)
4731 df_add_problem (&problem_MD);