Daily bump.
[official-gcc.git] / gcc / df-problems.c
blobd7a4914a3afc87d8c88e35e06de1e5f584185b14
1 /* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2021 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"
39 #include "regs.h"
40 #include "function-abi.h"
42 /* Note that turning REG_DEAD_DEBUGGING on will cause
43 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
44 addresses in the dumps. */
45 #define REG_DEAD_DEBUGGING 0
47 #define DF_SPARSE_THRESHOLD 32
49 static bitmap_head seen_in_block;
50 static bitmap_head seen_in_insn;
52 /*----------------------------------------------------------------------------
53 Utility functions.
54 ----------------------------------------------------------------------------*/
56 /* Generic versions to get the void* version of the block info. Only
57 used inside the problem instance vectors. */
59 /* Dump a def-use or use-def chain for REF to FILE. */
61 void
62 df_chain_dump (struct df_link *link, FILE *file)
64 fprintf (file, "{ ");
65 for (; link; link = link->next)
67 fprintf (file, "%c%d(bb %d insn %d) ",
68 DF_REF_REG_DEF_P (link->ref)
69 ? 'd'
70 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
71 DF_REF_ID (link->ref),
72 DF_REF_BBNO (link->ref),
73 DF_REF_IS_ARTIFICIAL (link->ref)
74 ? -1 : DF_REF_INSN_UID (link->ref));
76 fprintf (file, "}");
80 /* Print some basic block info as part of df_dump. */
82 void
83 df_print_bb_index (basic_block bb, FILE *file)
85 edge e;
86 edge_iterator ei;
88 fprintf (file, "\n( ");
89 FOR_EACH_EDGE (e, ei, bb->preds)
91 basic_block pred = e->src;
92 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
94 fprintf (file, ")->[%d]->( ", bb->index);
95 FOR_EACH_EDGE (e, ei, bb->succs)
97 basic_block succ = e->dest;
98 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
100 fprintf (file, ")\n");
104 /*----------------------------------------------------------------------------
105 REACHING DEFINITIONS
107 Find the locations in the function where each definition site for a
108 pseudo reaches. In and out bitvectors are built for each basic
109 block. The id field in the ref is used to index into these sets.
110 See df.h for details.
112 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
113 existing uses are included in the global reaching DEFs set, or in other
114 words only DEFs that are still live. This is a kind of pruned version
115 of the traditional reaching definitions problem that is much less
116 complex to compute and produces enough information to compute UD-chains.
117 In this context, live must be interpreted in the DF_LR sense: Uses that
118 are upward exposed but maybe not initialized on all paths through the
119 CFG. For a USE that is not reached by a DEF on all paths, we still want
120 to make those DEFs that do reach the USE visible, and pruning based on
121 DF_LIVE would make that impossible.
122 ----------------------------------------------------------------------------*/
124 /* This problem plays a large number of games for the sake of
125 efficiency.
127 1) The order of the bits in the bitvectors. After the scanning
128 phase, all of the defs are sorted. All of the defs for the reg 0
129 are first, followed by all defs for reg 1 and so on.
131 2) There are two kill sets, one if the number of defs is less or
132 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
133 greater.
135 <= : Data is built directly in the kill set.
137 > : One level of indirection is used to keep from generating long
138 strings of 1 bits in the kill sets. Bitvectors that are indexed
139 by the regnum are used to represent that there is a killing def
140 for the register. The confluence and transfer functions use
141 these along with the bitmap_clear_range call to remove ranges of
142 bits without actually generating a knockout vector.
144 The kill and sparse_kill and the dense_invalidated_by_eh and
145 sparse_invalidated_by_eh both play this game. */
147 /* Private data used to compute the solution for this problem. These
148 data structures are not accessible outside of this module. */
149 class df_rd_problem_data
151 public:
152 /* The set of defs to regs invalidated by EH edges. */
153 bitmap_head sparse_invalidated_by_eh;
154 bitmap_head dense_invalidated_by_eh;
155 /* An obstack for the bitmaps we need for this problem. */
156 bitmap_obstack rd_bitmaps;
160 /* Free basic block info. */
162 static void
163 df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
164 void *vbb_info)
166 class df_rd_bb_info *bb_info = (class df_rd_bb_info *) vbb_info;
167 if (bb_info)
169 bitmap_clear (&bb_info->kill);
170 bitmap_clear (&bb_info->sparse_kill);
171 bitmap_clear (&bb_info->gen);
172 bitmap_clear (&bb_info->in);
173 bitmap_clear (&bb_info->out);
178 /* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
179 not touched unless the block is new. */
181 static void
182 df_rd_alloc (bitmap all_blocks)
184 unsigned int bb_index;
185 bitmap_iterator bi;
186 class df_rd_problem_data *problem_data;
188 if (df_rd->problem_data)
190 problem_data = (class df_rd_problem_data *) df_rd->problem_data;
191 bitmap_clear (&problem_data->sparse_invalidated_by_eh);
192 bitmap_clear (&problem_data->dense_invalidated_by_eh);
194 else
196 problem_data = XNEW (class df_rd_problem_data);
197 df_rd->problem_data = problem_data;
199 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
200 bitmap_initialize (&problem_data->sparse_invalidated_by_eh,
201 &problem_data->rd_bitmaps);
202 bitmap_initialize (&problem_data->dense_invalidated_by_eh,
203 &problem_data->rd_bitmaps);
206 df_grow_bb_info (df_rd);
208 /* Because of the clustering of all use sites for the same pseudo,
209 we have to process all of the blocks before doing the analysis. */
211 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
213 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
215 /* When bitmaps are already initialized, just clear them. */
216 if (bb_info->kill.obstack)
218 bitmap_clear (&bb_info->kill);
219 bitmap_clear (&bb_info->sparse_kill);
220 bitmap_clear (&bb_info->gen);
222 else
224 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
225 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
226 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
227 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
228 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
231 df_rd->optional_p = true;
235 /* Add the effect of the top artificial defs of BB to the reaching definitions
236 bitmap LOCAL_RD. */
238 void
239 df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
241 int bb_index = bb->index;
242 df_ref def;
243 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
244 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
246 unsigned int dregno = DF_REF_REGNO (def);
247 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
248 bitmap_clear_range (local_rd,
249 DF_DEFS_BEGIN (dregno),
250 DF_DEFS_COUNT (dregno));
251 bitmap_set_bit (local_rd, DF_REF_ID (def));
255 /* Add the effect of the defs of INSN to the reaching definitions bitmap
256 LOCAL_RD. */
258 void
259 df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
260 bitmap local_rd)
262 df_ref def;
264 FOR_EACH_INSN_DEF (def, insn)
266 unsigned int dregno = DF_REF_REGNO (def);
267 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
268 || (dregno >= FIRST_PSEUDO_REGISTER))
270 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
271 bitmap_clear_range (local_rd,
272 DF_DEFS_BEGIN (dregno),
273 DF_DEFS_COUNT (dregno));
274 if (!(DF_REF_FLAGS (def)
275 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
276 bitmap_set_bit (local_rd, DF_REF_ID (def));
281 /* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
282 more complicated than just simulating, because we must produce the
283 gen and kill sets and hence deal with the two possible representations
284 of kill sets. */
286 static void
287 df_rd_bb_local_compute_process_def (class df_rd_bb_info *bb_info,
288 df_ref def,
289 int top_flag)
291 for (; def; def = DF_REF_NEXT_LOC (def))
293 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
295 unsigned int regno = DF_REF_REGNO (def);
296 unsigned int begin = DF_DEFS_BEGIN (regno);
297 unsigned int n_defs = DF_DEFS_COUNT (regno);
299 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
300 || (regno >= FIRST_PSEUDO_REGISTER))
302 /* Only the last def(s) for a regno in the block has any
303 effect. */
304 if (!bitmap_bit_p (&seen_in_block, regno))
306 /* The first def for regno in insn gets to knock out the
307 defs from other instructions. */
308 if ((!bitmap_bit_p (&seen_in_insn, regno))
309 /* If the def is to only part of the reg, it does
310 not kill the other defs that reach here. */
311 && (!(DF_REF_FLAGS (def) &
312 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
314 if (n_defs > DF_SPARSE_THRESHOLD)
316 bitmap_set_bit (&bb_info->sparse_kill, regno);
317 bitmap_clear_range (&bb_info->gen, begin, n_defs);
319 else
321 bitmap_set_range (&bb_info->kill, begin, n_defs);
322 bitmap_clear_range (&bb_info->gen, begin, n_defs);
326 bitmap_set_bit (&seen_in_insn, regno);
327 /* All defs for regno in the instruction may be put into
328 the gen set. */
329 if (!(DF_REF_FLAGS (def)
330 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
331 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
338 /* Compute local reaching def info for basic block BB. */
340 static void
341 df_rd_bb_local_compute (unsigned int bb_index)
343 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
344 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
345 rtx_insn *insn;
347 bitmap_clear (&seen_in_block);
348 bitmap_clear (&seen_in_insn);
350 /* Artificials are only hard regs. */
351 if (!(df->changeable_flags & DF_NO_HARD_REGS))
352 df_rd_bb_local_compute_process_def (bb_info,
353 df_get_artificial_defs (bb_index),
356 FOR_BB_INSNS_REVERSE (bb, insn)
358 unsigned int uid = INSN_UID (insn);
360 if (!INSN_P (insn))
361 continue;
363 df_rd_bb_local_compute_process_def (bb_info,
364 DF_INSN_UID_DEFS (uid), 0);
366 /* This complex dance with the two bitmaps is required because
367 instructions can assign twice to the same pseudo. This
368 generally happens with calls that will have one def for the
369 result and another def for the clobber. If only one vector
370 is used and the clobber goes first, the result will be
371 lost. */
372 bitmap_ior_into (&seen_in_block, &seen_in_insn);
373 bitmap_clear (&seen_in_insn);
376 /* Process the artificial defs at the top of the block last since we
377 are going backwards through the block and these are logically at
378 the start. */
379 if (!(df->changeable_flags & DF_NO_HARD_REGS))
380 df_rd_bb_local_compute_process_def (bb_info,
381 df_get_artificial_defs (bb_index),
382 DF_REF_AT_TOP);
386 /* Compute local reaching def info for each basic block within BLOCKS. */
388 static void
389 df_rd_local_compute (bitmap all_blocks)
391 unsigned int bb_index;
392 bitmap_iterator bi;
393 class df_rd_problem_data *problem_data
394 = (class df_rd_problem_data *) df_rd->problem_data;
395 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
396 bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
398 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
399 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
401 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
403 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
405 df_rd_bb_local_compute (bb_index);
408 /* Set up the knockout bit vectors to be applied across EH_EDGES.
409 Conservatively treat partially-clobbered registers as surviving
410 across the EH edge, i.e. assume that definitions before the edge
411 is taken *might* reach uses after it has been taken. */
412 if (!(df->changeable_flags & DF_NO_HARD_REGS))
413 for (unsigned int regno = 0; regno < FIRST_PSEUDO_REGISTER; ++regno)
414 if (eh_edge_abi.clobbers_full_reg_p (regno))
416 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
417 bitmap_set_bit (sparse_invalidated, regno);
418 else
419 bitmap_set_range (dense_invalidated,
420 DF_DEFS_BEGIN (regno),
421 DF_DEFS_COUNT (regno));
424 bitmap_release (&seen_in_block);
425 bitmap_release (&seen_in_insn);
429 /* Initialize the solution bit vectors for problem. */
431 static void
432 df_rd_init_solution (bitmap all_blocks)
434 unsigned int bb_index;
435 bitmap_iterator bi;
437 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
439 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
441 bitmap_copy (&bb_info->out, &bb_info->gen);
442 bitmap_clear (&bb_info->in);
446 /* In of target gets or of out of source. */
448 static bool
449 df_rd_confluence_n (edge e)
451 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
452 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
453 bool changed = false;
455 if (e->flags & EDGE_FAKE)
456 return false;
458 if (e->flags & EDGE_EH)
460 class df_rd_problem_data *problem_data
461 = (class df_rd_problem_data *) df_rd->problem_data;
462 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_eh;
463 bitmap dense_invalidated = &problem_data->dense_invalidated_by_eh;
464 bitmap_iterator bi;
465 unsigned int regno;
467 auto_bitmap tmp (&df_bitmap_obstack);
468 bitmap_and_compl (tmp, op2, dense_invalidated);
470 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
472 bitmap_clear_range (tmp,
473 DF_DEFS_BEGIN (regno),
474 DF_DEFS_COUNT (regno));
476 changed |= bitmap_ior_into (op1, tmp);
477 return changed;
479 else
480 return bitmap_ior_into (op1, op2);
484 /* Transfer function. */
486 static bool
487 df_rd_transfer_function (int bb_index)
489 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
490 unsigned int regno;
491 bitmap_iterator bi;
492 bitmap in = &bb_info->in;
493 bitmap out = &bb_info->out;
494 bitmap gen = &bb_info->gen;
495 bitmap kill = &bb_info->kill;
496 bitmap sparse_kill = &bb_info->sparse_kill;
497 bool changed = false;
499 if (bitmap_empty_p (sparse_kill))
500 changed = bitmap_ior_and_compl (out, gen, in, kill);
501 else
503 class df_rd_problem_data *problem_data;
504 bitmap_head tmp;
506 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
507 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
508 problem_data = (class df_rd_problem_data *) df_rd->problem_data;
509 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
511 bitmap_and_compl (&tmp, in, kill);
512 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
514 bitmap_clear_range (&tmp,
515 DF_DEFS_BEGIN (regno),
516 DF_DEFS_COUNT (regno));
518 bitmap_ior_into (&tmp, gen);
519 changed = !bitmap_equal_p (&tmp, out);
520 if (changed)
521 bitmap_move (out, &tmp);
522 else
523 bitmap_clear (&tmp);
526 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
528 /* Create a mask of DEFs for all registers live at the end of this
529 basic block, and mask out DEFs of registers that are not live.
530 Computing the mask looks costly, but the benefit of the pruning
531 outweighs the cost. */
532 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
533 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
534 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
535 unsigned int regno;
536 bitmap_iterator bi;
538 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
539 bitmap_set_range (live_defs,
540 DF_DEFS_BEGIN (regno),
541 DF_DEFS_COUNT (regno));
542 changed |= bitmap_and_into (&bb_info->out, live_defs);
543 BITMAP_FREE (live_defs);
546 return changed;
549 /* Free all storage associated with the problem. */
551 static void
552 df_rd_free (void)
554 class df_rd_problem_data *problem_data
555 = (class df_rd_problem_data *) df_rd->problem_data;
557 if (problem_data)
559 bitmap_obstack_release (&problem_data->rd_bitmaps);
561 df_rd->block_info_size = 0;
562 free (df_rd->block_info);
563 df_rd->block_info = NULL;
564 free (df_rd->problem_data);
566 free (df_rd);
570 /* Debugging info. */
572 static void
573 df_rd_start_dump (FILE *file)
575 class df_rd_problem_data *problem_data
576 = (class df_rd_problem_data *) df_rd->problem_data;
577 unsigned int m = DF_REG_SIZE (df);
578 unsigned int regno;
580 if (!df_rd->block_info)
581 return;
583 fprintf (file, ";; Reaching defs:\n");
585 fprintf (file, ";; sparse invalidated \t");
586 dump_bitmap (file, &problem_data->sparse_invalidated_by_eh);
587 fprintf (file, ";; dense invalidated \t");
588 dump_bitmap (file, &problem_data->dense_invalidated_by_eh);
590 fprintf (file, ";; reg->defs[] map:\t");
591 for (regno = 0; regno < m; regno++)
592 if (DF_DEFS_COUNT (regno))
593 fprintf (file, "%d[%d,%d] ", regno,
594 DF_DEFS_BEGIN (regno),
595 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
596 fprintf (file, "\n");
600 static void
601 df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
603 bitmap_head tmp;
604 unsigned int regno;
605 unsigned int m = DF_REG_SIZE (df);
606 bool first_reg = true;
608 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
610 bitmap_initialize (&tmp, &df_bitmap_obstack);
611 for (regno = 0; regno < m; regno++)
613 if (HARD_REGISTER_NUM_P (regno)
614 && (df->changeable_flags & DF_NO_HARD_REGS))
615 continue;
616 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
617 bitmap_and_into (&tmp, defs_set);
618 if (! bitmap_empty_p (&tmp))
620 bitmap_iterator bi;
621 unsigned int ix;
622 bool first_def = true;
624 if (! first_reg)
625 fprintf (file, ",");
626 first_reg = false;
628 fprintf (file, "%u[", regno);
629 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
631 fprintf (file, "%s%u", first_def ? "" : ",", ix);
632 first_def = false;
634 fprintf (file, "]");
636 bitmap_clear (&tmp);
639 fprintf (file, "\n");
640 bitmap_clear (&tmp);
643 /* Debugging info at top of bb. */
645 static void
646 df_rd_top_dump (basic_block bb, FILE *file)
648 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
649 if (!bb_info)
650 return;
652 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
653 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
654 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
658 /* Debugging info at bottom of bb. */
660 static void
661 df_rd_bottom_dump (basic_block bb, FILE *file)
663 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
664 if (!bb_info)
665 return;
667 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
670 /* All of the information associated with every instance of the problem. */
672 static const struct df_problem problem_RD =
674 DF_RD, /* Problem id. */
675 DF_FORWARD, /* Direction. */
676 df_rd_alloc, /* Allocate the problem specific data. */
677 NULL, /* Reset global information. */
678 df_rd_free_bb_info, /* Free basic block info. */
679 df_rd_local_compute, /* Local compute function. */
680 df_rd_init_solution, /* Init the solution specific data. */
681 df_worklist_dataflow, /* Worklist solver. */
682 NULL, /* Confluence operator 0. */
683 df_rd_confluence_n, /* Confluence operator n. */
684 df_rd_transfer_function, /* Transfer function. */
685 NULL, /* Finalize function. */
686 df_rd_free, /* Free all of the problem information. */
687 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
688 df_rd_start_dump, /* Debugging. */
689 df_rd_top_dump, /* Debugging start block. */
690 df_rd_bottom_dump, /* Debugging end block. */
691 NULL, /* Debugging start insn. */
692 NULL, /* Debugging end insn. */
693 NULL, /* Incremental solution verify start. */
694 NULL, /* Incremental solution verify end. */
695 NULL, /* Dependent problem. */
696 sizeof (class df_rd_bb_info),/* Size of entry of block_info array. */
697 TV_DF_RD, /* Timing variable. */
698 true /* Reset blocks on dropping out of blocks_to_analyze. */
703 /* Create a new RD instance and add it to the existing instance
704 of DF. */
706 void
707 df_rd_add_problem (void)
709 df_add_problem (&problem_RD);
714 /*----------------------------------------------------------------------------
715 LIVE REGISTERS
717 Find the locations in the function where any use of a pseudo can
718 reach in the backwards direction. In and out bitvectors are built
719 for each basic block. The regno is used to index into these sets.
720 See df.h for details.
721 ----------------------------------------------------------------------------*/
723 /* Private data used to verify the solution for this problem. */
724 struct df_lr_problem_data
726 bitmap_head *in;
727 bitmap_head *out;
728 /* An obstack for the bitmaps we need for this problem. */
729 bitmap_obstack lr_bitmaps;
732 /* Free basic block info. */
734 static void
735 df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
736 void *vbb_info)
738 class df_lr_bb_info *bb_info = (class df_lr_bb_info *) vbb_info;
739 if (bb_info)
741 bitmap_clear (&bb_info->use);
742 bitmap_clear (&bb_info->def);
743 bitmap_clear (&bb_info->in);
744 bitmap_clear (&bb_info->out);
749 /* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
750 not touched unless the block is new. */
752 static void
753 df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
755 unsigned int bb_index;
756 bitmap_iterator bi;
757 struct df_lr_problem_data *problem_data;
759 df_grow_bb_info (df_lr);
760 if (df_lr->problem_data)
761 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
762 else
764 problem_data = XNEW (struct df_lr_problem_data);
765 df_lr->problem_data = problem_data;
767 problem_data->out = NULL;
768 problem_data->in = NULL;
769 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
772 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
774 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
776 /* When bitmaps are already initialized, just clear them. */
777 if (bb_info->use.obstack)
779 bitmap_clear (&bb_info->def);
780 bitmap_clear (&bb_info->use);
782 else
784 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
785 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
786 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
787 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
791 df_lr->optional_p = false;
795 /* Reset the global solution for recalculation. */
797 static void
798 df_lr_reset (bitmap all_blocks)
800 unsigned int bb_index;
801 bitmap_iterator bi;
803 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
805 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
806 gcc_assert (bb_info);
807 bitmap_clear (&bb_info->in);
808 bitmap_clear (&bb_info->out);
813 /* Compute local live register info for basic block BB. */
815 static void
816 df_lr_bb_local_compute (unsigned int bb_index)
818 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
819 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
820 rtx_insn *insn;
821 df_ref def, use;
823 /* Process the registers set in an exception handler. */
824 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
825 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
827 unsigned int dregno = DF_REF_REGNO (def);
828 bitmap_set_bit (&bb_info->def, dregno);
829 bitmap_clear_bit (&bb_info->use, dregno);
832 /* Process the hardware registers that are always live. */
833 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
834 /* Add use to set of uses in this BB. */
835 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
836 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
838 FOR_BB_INSNS_REVERSE (bb, insn)
840 if (!NONDEBUG_INSN_P (insn))
841 continue;
843 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
844 FOR_EACH_INSN_INFO_DEF (def, insn_info)
846 /* If the definition is to only part of the register, it will
847 usually have a corresponding use. For example, stores to one
848 word of a multiword register R have both a use and a partial
849 definition of R.
851 In those cases, the LR confluence function:
853 IN = (OUT & ~DEF) | USE
855 is unaffected by whether we count the partial definition or not.
856 However, it's more convenient for consumers if DEF contains
857 *all* the registers defined in a block.
859 The only current case in which we record a partial definition
860 without a corresponding use is if the destination is the
861 multi-register subreg of a hard register. An artificial
862 example of this is:
864 (set (subreg:TI (reg:V8HI x0) 0) (const_int -1))
866 on AArch64. This is described as a DF_REF_PARTIAL
867 definition of x0 and x1 with no corresponding uses.
868 In previous versions of GCC, the instruction had no
869 effect on LR (that is, LR acted as though the instruction
870 didn't exist).
872 It seems suspect that this case is treated differently.
873 Either the instruction should be a full definition of x0 and x1,
874 or the definition should be treated in the same way as other
875 partial definitions, such as strict_lowparts or subregs that
876 satisfy read_modify_subreg_p.
878 Fortunately, multi-register subregs of hard registers should
879 be rare. They should be folded into a plain REG if the target
880 allows that (as AArch64 does for example above).
882 Here we treat the cases alike by forcing a use even in the rare
883 case that no DF_REF_REG_USE is recorded. That is, we model all
884 partial definitions as both a use and a definition of the
885 register. */
886 unsigned int dregno = DF_REF_REGNO (def);
887 bitmap_set_bit (&bb_info->def, dregno);
888 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
889 bitmap_set_bit (&bb_info->use, dregno);
890 else
891 bitmap_clear_bit (&bb_info->use, dregno);
894 FOR_EACH_INSN_INFO_USE (use, insn_info)
895 /* Add use to set of uses in this BB. */
896 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
899 /* Process the registers set in an exception handler or the hard
900 frame pointer if this block is the target of a non local
901 goto. */
902 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
903 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
905 unsigned int dregno = DF_REF_REGNO (def);
906 bitmap_set_bit (&bb_info->def, dregno);
907 bitmap_clear_bit (&bb_info->use, dregno);
910 #ifdef EH_USES
911 /* Process the uses that are live into an exception handler. */
912 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
913 /* Add use to set of uses in this BB. */
914 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
915 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
916 #endif
918 /* If the df_live problem is not defined, such as at -O0 and -O1, we
919 still need to keep the luids up to date. This is normally done
920 in the df_live problem since this problem has a forwards
921 scan. */
922 if (!df_live)
923 df_recompute_luids (bb);
927 /* Compute local live register info for each basic block within BLOCKS. */
929 static void
930 df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
932 unsigned int bb_index, i;
933 bitmap_iterator bi;
935 bitmap_clear (&df->hardware_regs_used);
937 /* The all-important stack pointer must always be live. */
938 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
940 /* Global regs are always live, too. */
941 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
942 if (global_regs[i])
943 bitmap_set_bit (&df->hardware_regs_used, i);
945 /* Before reload, there are a few registers that must be forced
946 live everywhere -- which might not already be the case for
947 blocks within infinite loops. */
948 if (!reload_completed)
950 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
951 /* Any reference to any pseudo before reload is a potential
952 reference of the frame pointer. */
953 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
955 /* Pseudos with argument area equivalences may require
956 reloading via the argument pointer. */
957 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
958 && fixed_regs[ARG_POINTER_REGNUM])
959 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
961 /* Any constant, or pseudo with constant equivalences, may
962 require reloading from memory using the pic register. */
963 if (pic_offset_table_regnum != INVALID_REGNUM
964 && fixed_regs[pic_offset_table_regnum])
965 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
968 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
970 if (bb_index == EXIT_BLOCK)
972 /* The exit block is special for this problem and its bits are
973 computed from thin air. */
974 class df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
975 bitmap_copy (&bb_info->use, df->exit_block_uses);
977 else
978 df_lr_bb_local_compute (bb_index);
981 bitmap_clear (df_lr->out_of_date_transfer_functions);
985 /* Initialize the solution vectors. */
987 static void
988 df_lr_init (bitmap all_blocks)
990 unsigned int bb_index;
991 bitmap_iterator bi;
993 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
995 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
996 bitmap_copy (&bb_info->in, &bb_info->use);
997 bitmap_clear (&bb_info->out);
1002 /* Confluence function that processes infinite loops. This might be a
1003 noreturn function that throws. And even if it isn't, getting the
1004 unwind info right helps debugging. */
1005 static void
1006 df_lr_confluence_0 (basic_block bb)
1008 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
1009 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
1010 bitmap_copy (op1, &df->hardware_regs_used);
1014 /* Confluence function that ignores fake edges. */
1016 static bool
1017 df_lr_confluence_n (edge e)
1019 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
1020 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
1021 bool changed = false;
1023 /* Call-clobbered registers die across exception and call edges.
1024 Conservatively treat partially-clobbered registers as surviving
1025 across the edges; they might or might not, depending on what
1026 mode they have. */
1027 /* ??? Abnormal call edges ignored for the moment, as this gets
1028 confused by sibling call edges, which crashes reg-stack. */
1029 if (e->flags & EDGE_EH)
1031 bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
1032 changed = bitmap_ior_and_compl_into (op1, op2, eh_kills);
1034 else
1035 changed = bitmap_ior_into (op1, op2);
1037 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
1038 return changed;
1042 /* Transfer function. */
1044 static bool
1045 df_lr_transfer_function (int bb_index)
1047 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1048 bitmap in = &bb_info->in;
1049 bitmap out = &bb_info->out;
1050 bitmap use = &bb_info->use;
1051 bitmap def = &bb_info->def;
1053 return bitmap_ior_and_compl (in, use, out, def);
1057 /* Run the fast dce as a side effect of building LR. */
1059 static void
1060 df_lr_finalize (bitmap all_blocks)
1062 df_lr->solutions_dirty = false;
1063 if (df->changeable_flags & DF_LR_RUN_DCE)
1065 run_fast_df_dce ();
1067 /* If dce deletes some instructions, we need to recompute the lr
1068 solution before proceeding further. The problem is that fast
1069 dce is a pessimestic dataflow algorithm. In the case where
1070 it deletes a statement S inside of a loop, the uses inside of
1071 S may not be deleted from the dataflow solution because they
1072 were carried around the loop. While it is conservatively
1073 correct to leave these extra bits, the standards of df
1074 require that we maintain the best possible (least fixed
1075 point) solution. The only way to do that is to redo the
1076 iteration from the beginning. See PR35805 for an
1077 example. */
1078 if (df_lr->solutions_dirty)
1080 df_clear_flags (DF_LR_RUN_DCE);
1081 df_lr_alloc (all_blocks);
1082 df_lr_local_compute (all_blocks);
1083 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1084 df_lr_finalize (all_blocks);
1085 df_set_flags (DF_LR_RUN_DCE);
1091 /* Free all storage associated with the problem. */
1093 static void
1094 df_lr_free (void)
1096 struct df_lr_problem_data *problem_data
1097 = (struct df_lr_problem_data *) df_lr->problem_data;
1098 if (df_lr->block_info)
1101 df_lr->block_info_size = 0;
1102 free (df_lr->block_info);
1103 df_lr->block_info = NULL;
1104 bitmap_obstack_release (&problem_data->lr_bitmaps);
1105 free (df_lr->problem_data);
1106 df_lr->problem_data = NULL;
1109 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1110 free (df_lr);
1114 /* Debugging info at top of bb. */
1116 static void
1117 df_lr_top_dump (basic_block bb, FILE *file)
1119 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1120 struct df_lr_problem_data *problem_data;
1121 if (!bb_info)
1122 return;
1124 fprintf (file, ";; lr in \t");
1125 df_print_regset (file, &bb_info->in);
1126 if (df_lr->problem_data)
1128 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1129 if (problem_data->in)
1131 fprintf (file, ";; old in \t");
1132 df_print_regset (file, &problem_data->in[bb->index]);
1135 fprintf (file, ";; lr use \t");
1136 df_print_regset (file, &bb_info->use);
1137 fprintf (file, ";; lr def \t");
1138 df_print_regset (file, &bb_info->def);
1142 /* Debugging info at bottom of bb. */
1144 static void
1145 df_lr_bottom_dump (basic_block bb, FILE *file)
1147 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1148 struct df_lr_problem_data *problem_data;
1149 if (!bb_info)
1150 return;
1152 fprintf (file, ";; lr out \t");
1153 df_print_regset (file, &bb_info->out);
1154 if (df_lr->problem_data)
1156 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1157 if (problem_data->out)
1159 fprintf (file, ";; old out \t");
1160 df_print_regset (file, &problem_data->out[bb->index]);
1166 /* Build the datastructure to verify that the solution to the dataflow
1167 equations is not dirty. */
1169 static void
1170 df_lr_verify_solution_start (void)
1172 basic_block bb;
1173 struct df_lr_problem_data *problem_data;
1174 if (df_lr->solutions_dirty)
1175 return;
1177 /* Set it true so that the solution is recomputed. */
1178 df_lr->solutions_dirty = true;
1180 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1181 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1182 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1184 FOR_ALL_BB_FN (bb, cfun)
1186 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1187 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1188 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1189 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1194 /* Compare the saved datastructure and the new solution to the dataflow
1195 equations. */
1197 static void
1198 df_lr_verify_solution_end (void)
1200 struct df_lr_problem_data *problem_data;
1201 basic_block bb;
1203 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1205 if (!problem_data->out)
1206 return;
1208 if (df_lr->solutions_dirty)
1209 /* Do not check if the solution is still dirty. See the comment
1210 in df_lr_finalize for details. */
1211 df_lr->solutions_dirty = false;
1212 else
1213 FOR_ALL_BB_FN (bb, cfun)
1215 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1216 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1218 /*df_dump (stderr);*/
1219 gcc_unreachable ();
1223 /* Cannot delete them immediately because you may want to dump them
1224 if the comparison fails. */
1225 FOR_ALL_BB_FN (bb, cfun)
1227 bitmap_clear (&problem_data->in[bb->index]);
1228 bitmap_clear (&problem_data->out[bb->index]);
1231 free (problem_data->in);
1232 free (problem_data->out);
1233 problem_data->in = NULL;
1234 problem_data->out = NULL;
1238 /* All of the information associated with every instance of the problem. */
1240 static const struct df_problem problem_LR =
1242 DF_LR, /* Problem id. */
1243 DF_BACKWARD, /* Direction. */
1244 df_lr_alloc, /* Allocate the problem specific data. */
1245 df_lr_reset, /* Reset global information. */
1246 df_lr_free_bb_info, /* Free basic block info. */
1247 df_lr_local_compute, /* Local compute function. */
1248 df_lr_init, /* Init the solution specific data. */
1249 df_worklist_dataflow, /* Worklist solver. */
1250 df_lr_confluence_0, /* Confluence operator 0. */
1251 df_lr_confluence_n, /* Confluence operator n. */
1252 df_lr_transfer_function, /* Transfer function. */
1253 df_lr_finalize, /* Finalize function. */
1254 df_lr_free, /* Free all of the problem information. */
1255 NULL, /* Remove this problem from the stack of dataflow problems. */
1256 NULL, /* Debugging. */
1257 df_lr_top_dump, /* Debugging start block. */
1258 df_lr_bottom_dump, /* Debugging end block. */
1259 NULL, /* Debugging start insn. */
1260 NULL, /* Debugging end insn. */
1261 df_lr_verify_solution_start,/* Incremental solution verify start. */
1262 df_lr_verify_solution_end, /* Incremental solution verify end. */
1263 NULL, /* Dependent problem. */
1264 sizeof (class df_lr_bb_info),/* Size of entry of block_info array. */
1265 TV_DF_LR, /* Timing variable. */
1266 false /* Reset blocks on dropping out of blocks_to_analyze. */
1270 /* Create a new DATAFLOW instance and add it to an existing instance
1271 of DF. The returned structure is what is used to get at the
1272 solution. */
1274 void
1275 df_lr_add_problem (void)
1277 df_add_problem (&problem_LR);
1278 /* These will be initialized when df_scan_blocks processes each
1279 block. */
1280 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1284 /* Verify that all of the lr related info is consistent and
1285 correct. */
1287 void
1288 df_lr_verify_transfer_functions (void)
1290 basic_block bb;
1291 bitmap_head saved_def;
1292 bitmap_head saved_use;
1293 bitmap_head all_blocks;
1295 if (!df)
1296 return;
1298 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1299 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1300 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1302 FOR_ALL_BB_FN (bb, cfun)
1304 class df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1305 bitmap_set_bit (&all_blocks, bb->index);
1307 if (bb_info)
1309 /* Make a copy of the transfer functions and then compute
1310 new ones to see if the transfer functions have
1311 changed. */
1312 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1313 bb->index))
1315 bitmap_copy (&saved_def, &bb_info->def);
1316 bitmap_copy (&saved_use, &bb_info->use);
1317 bitmap_clear (&bb_info->def);
1318 bitmap_clear (&bb_info->use);
1320 df_lr_bb_local_compute (bb->index);
1321 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1322 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1325 else
1327 /* If we do not have basic block info, the block must be in
1328 the list of dirty blocks or else some one has added a
1329 block behind our backs. */
1330 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1331 bb->index));
1333 /* Make sure no one created a block without following
1334 procedures. */
1335 gcc_assert (df_scan_get_bb_info (bb->index));
1338 /* Make sure there are no dirty bits in blocks that have been deleted. */
1339 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1340 &all_blocks));
1342 bitmap_clear (&saved_def);
1343 bitmap_clear (&saved_use);
1344 bitmap_clear (&all_blocks);
1349 /*----------------------------------------------------------------------------
1350 LIVE AND MAY-INITIALIZED REGISTERS.
1352 This problem first computes the IN and OUT bitvectors for the
1353 may-initialized registers problems, which is a forward problem.
1354 It gives the set of registers for which we MAY have an available
1355 definition, i.e. for which there is an available definition on
1356 at least one path from the entry block to the entry/exit of a
1357 basic block. Sets generate a definition, while clobbers kill
1358 a definition.
1360 In and out bitvectors are built for each basic block and are indexed by
1361 regnum (see df.h for details). In and out bitvectors in struct
1362 df_live_bb_info actually refers to the may-initialized problem;
1364 Then, the in and out sets for the LIVE problem itself are computed.
1365 These are the logical AND of the IN and OUT sets from the LR problem
1366 and the may-initialized problem.
1367 ----------------------------------------------------------------------------*/
1369 /* Private data used to verify the solution for this problem. */
1370 struct df_live_problem_data
1372 bitmap_head *in;
1373 bitmap_head *out;
1374 /* An obstack for the bitmaps we need for this problem. */
1375 bitmap_obstack live_bitmaps;
1378 /* Scratch var used by transfer functions. This is used to implement
1379 an optimization to reduce the amount of space used to compute the
1380 combined lr and live analysis. */
1381 static bitmap_head df_live_scratch;
1384 /* Free basic block info. */
1386 static void
1387 df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1388 void *vbb_info)
1390 class df_live_bb_info *bb_info = (class df_live_bb_info *) vbb_info;
1391 if (bb_info)
1393 bitmap_clear (&bb_info->gen);
1394 bitmap_clear (&bb_info->kill);
1395 bitmap_clear (&bb_info->in);
1396 bitmap_clear (&bb_info->out);
1401 /* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1402 not touched unless the block is new. */
1404 static void
1405 df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1407 unsigned int bb_index;
1408 bitmap_iterator bi;
1409 struct df_live_problem_data *problem_data;
1411 if (df_live->problem_data)
1412 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1413 else
1415 problem_data = XNEW (struct df_live_problem_data);
1416 df_live->problem_data = problem_data;
1418 problem_data->out = NULL;
1419 problem_data->in = NULL;
1420 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1421 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1424 df_grow_bb_info (df_live);
1426 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1428 class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1430 /* When bitmaps are already initialized, just clear them. */
1431 if (bb_info->kill.obstack)
1433 bitmap_clear (&bb_info->kill);
1434 bitmap_clear (&bb_info->gen);
1436 else
1438 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1439 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1440 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1441 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1444 df_live->optional_p = (optimize <= 1);
1448 /* Reset the global solution for recalculation. */
1450 static void
1451 df_live_reset (bitmap all_blocks)
1453 unsigned int bb_index;
1454 bitmap_iterator bi;
1456 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1458 class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1459 gcc_assert (bb_info);
1460 bitmap_clear (&bb_info->in);
1461 bitmap_clear (&bb_info->out);
1466 /* Compute local uninitialized register info for basic block BB. */
1468 static void
1469 df_live_bb_local_compute (unsigned int bb_index)
1471 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1472 class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1473 rtx_insn *insn;
1474 df_ref def;
1475 int luid = 0;
1477 FOR_BB_INSNS (bb, insn)
1479 unsigned int uid = INSN_UID (insn);
1480 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1482 /* Inserting labels does not always trigger the incremental
1483 rescanning. */
1484 if (!insn_info)
1486 gcc_assert (!INSN_P (insn));
1487 insn_info = df_insn_create_insn_record (insn);
1490 DF_INSN_INFO_LUID (insn_info) = luid;
1491 if (!INSN_P (insn))
1492 continue;
1494 luid++;
1495 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1497 unsigned int regno = DF_REF_REGNO (def);
1499 if (DF_REF_FLAGS_IS_SET (def,
1500 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1501 /* All partial or conditional def
1502 seen are included in the gen set. */
1503 bitmap_set_bit (&bb_info->gen, regno);
1504 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1505 /* Only must clobbers for the entire reg destroy the
1506 value. */
1507 bitmap_set_bit (&bb_info->kill, regno);
1508 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1509 bitmap_set_bit (&bb_info->gen, regno);
1513 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1514 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1518 /* Compute local uninitialized register info. */
1520 static void
1521 df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1523 unsigned int bb_index;
1524 bitmap_iterator bi;
1526 df_grow_insn_info ();
1528 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1529 0, bb_index, bi)
1531 df_live_bb_local_compute (bb_index);
1534 bitmap_clear (df_live->out_of_date_transfer_functions);
1538 /* Initialize the solution vectors. */
1540 static void
1541 df_live_init (bitmap all_blocks)
1543 unsigned int bb_index;
1544 bitmap_iterator bi;
1546 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1548 class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1549 class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1551 /* No register may reach a location where it is not used. Thus
1552 we trim the rr result to the places where it is used. */
1553 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1554 bitmap_clear (&bb_info->in);
1558 /* Forward confluence function that ignores fake edges. */
1560 static bool
1561 df_live_confluence_n (edge e)
1563 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1564 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1566 if (e->flags & EDGE_FAKE)
1567 return false;
1569 return bitmap_ior_into (op1, op2);
1573 /* Transfer function for the forwards may-initialized problem. */
1575 static bool
1576 df_live_transfer_function (int bb_index)
1578 class df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1579 class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1580 bitmap in = &bb_info->in;
1581 bitmap out = &bb_info->out;
1582 bitmap gen = &bb_info->gen;
1583 bitmap kill = &bb_info->kill;
1585 /* We need to use a scratch set here so that the value returned from this
1586 function invocation properly reflects whether the sets changed in a
1587 significant way; i.e. not just because the lr set was anded in. */
1588 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1589 /* No register may reach a location where it is not used. Thus
1590 we trim the rr result to the places where it is used. */
1591 bitmap_and_into (in, &bb_lr_info->in);
1593 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1597 /* And the LR info with the may-initialized registers to produce the LIVE info. */
1599 static void
1600 df_live_finalize (bitmap all_blocks)
1603 if (df_live->solutions_dirty)
1605 bitmap_iterator bi;
1606 unsigned int bb_index;
1608 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1610 class df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1611 class df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1613 /* No register may reach a location where it is not used. Thus
1614 we trim the rr result to the places where it is used. */
1615 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1616 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1619 df_live->solutions_dirty = false;
1624 /* Free all storage associated with the problem. */
1626 static void
1627 df_live_free (void)
1629 struct df_live_problem_data *problem_data
1630 = (struct df_live_problem_data *) df_live->problem_data;
1631 if (df_live->block_info)
1633 df_live->block_info_size = 0;
1634 free (df_live->block_info);
1635 df_live->block_info = NULL;
1636 bitmap_release (&df_live_scratch);
1637 bitmap_obstack_release (&problem_data->live_bitmaps);
1638 free (problem_data);
1639 df_live->problem_data = NULL;
1641 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1642 free (df_live);
1646 /* Debugging info at top of bb. */
1648 static void
1649 df_live_top_dump (basic_block bb, FILE *file)
1651 class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1652 struct df_live_problem_data *problem_data;
1654 if (!bb_info)
1655 return;
1657 fprintf (file, ";; live in \t");
1658 df_print_regset (file, &bb_info->in);
1659 if (df_live->problem_data)
1661 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1662 if (problem_data->in)
1664 fprintf (file, ";; old in \t");
1665 df_print_regset (file, &problem_data->in[bb->index]);
1668 fprintf (file, ";; live gen \t");
1669 df_print_regset (file, &bb_info->gen);
1670 fprintf (file, ";; live kill\t");
1671 df_print_regset (file, &bb_info->kill);
1675 /* Debugging info at bottom of bb. */
1677 static void
1678 df_live_bottom_dump (basic_block bb, FILE *file)
1680 class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1681 struct df_live_problem_data *problem_data;
1683 if (!bb_info)
1684 return;
1686 fprintf (file, ";; live out \t");
1687 df_print_regset (file, &bb_info->out);
1688 if (df_live->problem_data)
1690 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1691 if (problem_data->out)
1693 fprintf (file, ";; old out \t");
1694 df_print_regset (file, &problem_data->out[bb->index]);
1700 /* Build the datastructure to verify that the solution to the dataflow
1701 equations is not dirty. */
1703 static void
1704 df_live_verify_solution_start (void)
1706 basic_block bb;
1707 struct df_live_problem_data *problem_data;
1708 if (df_live->solutions_dirty)
1709 return;
1711 /* Set it true so that the solution is recomputed. */
1712 df_live->solutions_dirty = true;
1714 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1715 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1716 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1718 FOR_ALL_BB_FN (bb, cfun)
1720 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1721 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1722 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1723 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1728 /* Compare the saved datastructure and the new solution to the dataflow
1729 equations. */
1731 static void
1732 df_live_verify_solution_end (void)
1734 struct df_live_problem_data *problem_data;
1735 basic_block bb;
1737 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1738 if (!problem_data->out)
1739 return;
1741 FOR_ALL_BB_FN (bb, cfun)
1743 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1744 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1746 /*df_dump (stderr);*/
1747 gcc_unreachable ();
1751 /* Cannot delete them immediately because you may want to dump them
1752 if the comparison fails. */
1753 FOR_ALL_BB_FN (bb, cfun)
1755 bitmap_clear (&problem_data->in[bb->index]);
1756 bitmap_clear (&problem_data->out[bb->index]);
1759 free (problem_data->in);
1760 free (problem_data->out);
1761 free (problem_data);
1762 df_live->problem_data = NULL;
1766 /* All of the information associated with every instance of the problem. */
1768 static const struct df_problem problem_LIVE =
1770 DF_LIVE, /* Problem id. */
1771 DF_FORWARD, /* Direction. */
1772 df_live_alloc, /* Allocate the problem specific data. */
1773 df_live_reset, /* Reset global information. */
1774 df_live_free_bb_info, /* Free basic block info. */
1775 df_live_local_compute, /* Local compute function. */
1776 df_live_init, /* Init the solution specific data. */
1777 df_worklist_dataflow, /* Worklist solver. */
1778 NULL, /* Confluence operator 0. */
1779 df_live_confluence_n, /* Confluence operator n. */
1780 df_live_transfer_function, /* Transfer function. */
1781 df_live_finalize, /* Finalize function. */
1782 df_live_free, /* Free all of the problem information. */
1783 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1784 NULL, /* Debugging. */
1785 df_live_top_dump, /* Debugging start block. */
1786 df_live_bottom_dump, /* Debugging end block. */
1787 NULL, /* Debugging start insn. */
1788 NULL, /* Debugging end insn. */
1789 df_live_verify_solution_start,/* Incremental solution verify start. */
1790 df_live_verify_solution_end, /* Incremental solution verify end. */
1791 &problem_LR, /* Dependent problem. */
1792 sizeof (class df_live_bb_info),/* Size of entry of block_info array. */
1793 TV_DF_LIVE, /* Timing variable. */
1794 false /* Reset blocks on dropping out of blocks_to_analyze. */
1798 /* Create a new DATAFLOW instance and add it to an existing instance
1799 of DF. The returned structure is what is used to get at the
1800 solution. */
1802 void
1803 df_live_add_problem (void)
1805 df_add_problem (&problem_LIVE);
1806 /* These will be initialized when df_scan_blocks processes each
1807 block. */
1808 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1812 /* Set all of the blocks as dirty. This needs to be done if this
1813 problem is added after all of the insns have been scanned. */
1815 void
1816 df_live_set_all_dirty (void)
1818 basic_block bb;
1819 FOR_ALL_BB_FN (bb, cfun)
1820 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1821 bb->index);
1825 /* Verify that all of the lr related info is consistent and
1826 correct. */
1828 void
1829 df_live_verify_transfer_functions (void)
1831 basic_block bb;
1832 bitmap_head saved_gen;
1833 bitmap_head saved_kill;
1834 bitmap_head all_blocks;
1836 if (!df)
1837 return;
1839 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1840 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1841 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1843 df_grow_insn_info ();
1845 FOR_ALL_BB_FN (bb, cfun)
1847 class df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1848 bitmap_set_bit (&all_blocks, bb->index);
1850 if (bb_info)
1852 /* Make a copy of the transfer functions and then compute
1853 new ones to see if the transfer functions have
1854 changed. */
1855 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1856 bb->index))
1858 bitmap_copy (&saved_gen, &bb_info->gen);
1859 bitmap_copy (&saved_kill, &bb_info->kill);
1860 bitmap_clear (&bb_info->gen);
1861 bitmap_clear (&bb_info->kill);
1863 df_live_bb_local_compute (bb->index);
1864 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1865 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1868 else
1870 /* If we do not have basic block info, the block must be in
1871 the list of dirty blocks or else some one has added a
1872 block behind our backs. */
1873 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1874 bb->index));
1876 /* Make sure no one created a block without following
1877 procedures. */
1878 gcc_assert (df_scan_get_bb_info (bb->index));
1881 /* Make sure there are no dirty bits in blocks that have been deleted. */
1882 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1883 &all_blocks));
1884 bitmap_clear (&saved_gen);
1885 bitmap_clear (&saved_kill);
1886 bitmap_clear (&all_blocks);
1889 /*----------------------------------------------------------------------------
1890 MUST-INITIALIZED REGISTERS.
1891 ----------------------------------------------------------------------------*/
1893 /* Private data used to verify the solution for this problem. */
1894 struct df_mir_problem_data
1896 bitmap_head *in;
1897 bitmap_head *out;
1898 /* An obstack for the bitmaps we need for this problem. */
1899 bitmap_obstack mir_bitmaps;
1903 /* Free basic block info. */
1905 static void
1906 df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1907 void *vbb_info)
1909 class df_mir_bb_info *bb_info = (class df_mir_bb_info *) vbb_info;
1910 if (bb_info)
1912 bitmap_clear (&bb_info->gen);
1913 bitmap_clear (&bb_info->kill);
1914 bitmap_clear (&bb_info->in);
1915 bitmap_clear (&bb_info->out);
1920 /* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
1921 not touched unless the block is new. */
1923 static void
1924 df_mir_alloc (bitmap all_blocks)
1926 unsigned int bb_index;
1927 bitmap_iterator bi;
1928 struct df_mir_problem_data *problem_data;
1930 if (df_mir->problem_data)
1931 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1932 else
1934 problem_data = XNEW (struct df_mir_problem_data);
1935 df_mir->problem_data = problem_data;
1937 problem_data->out = NULL;
1938 problem_data->in = NULL;
1939 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1942 df_grow_bb_info (df_mir);
1944 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1946 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1948 /* When bitmaps are already initialized, just clear them. */
1949 if (bb_info->kill.obstack)
1951 bitmap_clear (&bb_info->kill);
1952 bitmap_clear (&bb_info->gen);
1954 else
1956 bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1957 bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1958 bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1959 bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1960 bb_info->con_visited = false;
1964 df_mir->optional_p = 1;
1968 /* Reset the global solution for recalculation. */
1970 static void
1971 df_mir_reset (bitmap all_blocks)
1973 unsigned int bb_index;
1974 bitmap_iterator bi;
1976 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1978 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1980 gcc_assert (bb_info);
1982 bitmap_clear (&bb_info->in);
1983 bitmap_clear (&bb_info->out);
1984 bb_info->con_visited = false;
1989 /* Compute local uninitialized register info for basic block BB. */
1991 static void
1992 df_mir_bb_local_compute (unsigned int bb_index)
1994 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1995 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1996 rtx_insn *insn;
1997 int luid = 0;
1999 /* Ignoring artificial defs is intentional: these often pretend that some
2000 registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
2001 though they are not used for that. As a result, conservatively assume
2002 they may be uninitialized. */
2004 FOR_BB_INSNS (bb, insn)
2006 unsigned int uid = INSN_UID (insn);
2007 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
2009 /* Inserting labels does not always trigger the incremental
2010 rescanning. */
2011 if (!insn_info)
2013 gcc_assert (!INSN_P (insn));
2014 insn_info = df_insn_create_insn_record (insn);
2017 DF_INSN_INFO_LUID (insn_info) = luid;
2018 if (!INSN_P (insn))
2019 continue;
2021 luid++;
2022 df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
2027 /* Compute local uninitialized register info. */
2029 static void
2030 df_mir_local_compute (bitmap all_blocks)
2032 unsigned int bb_index;
2033 bitmap_iterator bi;
2035 df_grow_insn_info ();
2037 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2039 df_mir_bb_local_compute (bb_index);
2044 /* Initialize the solution vectors. */
2046 static void
2047 df_mir_init (bitmap all_blocks)
2049 df_mir_reset (all_blocks);
2053 /* Initialize IN sets for blocks with no predecessors: when landing on such
2054 blocks, assume all registers are uninitialized. */
2056 static void
2057 df_mir_confluence_0 (basic_block bb)
2059 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2061 bitmap_clear (&bb_info->in);
2062 bb_info->con_visited = true;
2066 /* Forward confluence function that ignores fake edges. */
2068 static bool
2069 df_mir_confluence_n (edge e)
2071 if (e->flags & EDGE_FAKE)
2072 return false;
2074 df_mir_bb_info *src_info = df_mir_get_bb_info (e->src->index);
2075 /* If SRC was not visited yet then we'll and with all-ones which
2076 means no changes. Do not consider DST con_visited by this
2077 operation alone either. */
2078 if (!src_info->con_visited)
2079 return false;
2081 df_mir_bb_info *dst_info = df_mir_get_bb_info (e->dest->index);
2082 bitmap op1 = &dst_info->in;
2083 bitmap op2 = &src_info->out;
2084 /* If DEST was not visited yet just copy the SRC bitmap. */
2085 if (!dst_info->con_visited)
2087 dst_info->con_visited = true;
2088 bitmap_copy (op1, op2);
2089 return true;
2092 /* A register is must-initialized at the entry of a basic block iff it is
2093 must-initialized at the exit of all the predecessors. */
2094 return bitmap_and_into (op1, op2);
2098 /* Transfer function for the forwards must-initialized problem. */
2100 static bool
2101 df_mir_transfer_function (int bb_index)
2103 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2104 bitmap in = &bb_info->in;
2105 bitmap out = &bb_info->out;
2106 bitmap gen = &bb_info->gen;
2107 bitmap kill = &bb_info->kill;
2109 return bitmap_ior_and_compl (out, gen, in, kill);
2113 /* Free all storage associated with the problem. */
2115 static void
2116 df_mir_free (void)
2118 struct df_mir_problem_data *problem_data
2119 = (struct df_mir_problem_data *) df_mir->problem_data;
2120 if (df_mir->block_info)
2122 df_mir->block_info_size = 0;
2123 free (df_mir->block_info);
2124 df_mir->block_info = NULL;
2125 bitmap_obstack_release (&problem_data->mir_bitmaps);
2126 free (problem_data);
2127 df_mir->problem_data = NULL;
2129 free (df_mir);
2133 /* Debugging info at top of bb. */
2135 static void
2136 df_mir_top_dump (basic_block bb, FILE *file)
2138 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2140 if (!bb_info)
2141 return;
2143 fprintf (file, ";; mir in \t");
2144 df_print_regset (file, &bb_info->in);
2145 fprintf (file, ";; mir kill\t");
2146 df_print_regset (file, &bb_info->kill);
2147 fprintf (file, ";; mir gen \t");
2148 df_print_regset (file, &bb_info->gen);
2151 /* Debugging info at bottom of bb. */
2153 static void
2154 df_mir_bottom_dump (basic_block bb, FILE *file)
2156 class df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2158 if (!bb_info)
2159 return;
2161 fprintf (file, ";; mir out \t");
2162 df_print_regset (file, &bb_info->out);
2166 /* Build the datastructure to verify that the solution to the dataflow
2167 equations is not dirty. */
2169 static void
2170 df_mir_verify_solution_start (void)
2172 basic_block bb;
2173 struct df_mir_problem_data *problem_data;
2174 if (df_mir->solutions_dirty)
2175 return;
2177 /* Set it true so that the solution is recomputed. */
2178 df_mir->solutions_dirty = true;
2180 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2181 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2182 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2183 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2185 FOR_ALL_BB_FN (bb, cfun)
2187 bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
2188 bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
2189 bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2190 bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2195 /* Compare the saved datastructure and the new solution to the dataflow
2196 equations. */
2198 static void
2199 df_mir_verify_solution_end (void)
2201 struct df_mir_problem_data *problem_data;
2202 basic_block bb;
2204 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2205 if (!problem_data->out)
2206 return;
2208 FOR_ALL_BB_FN (bb, cfun)
2210 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2211 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2212 gcc_unreachable ();
2215 /* Cannot delete them immediately because you may want to dump them
2216 if the comparison fails. */
2217 FOR_ALL_BB_FN (bb, cfun)
2219 bitmap_clear (&problem_data->in[bb->index]);
2220 bitmap_clear (&problem_data->out[bb->index]);
2223 free (problem_data->in);
2224 free (problem_data->out);
2225 bitmap_obstack_release (&problem_data->mir_bitmaps);
2226 free (problem_data);
2227 df_mir->problem_data = NULL;
2231 /* All of the information associated with every instance of the problem. */
2233 static const struct df_problem problem_MIR =
2235 DF_MIR, /* Problem id. */
2236 DF_FORWARD, /* Direction. */
2237 df_mir_alloc, /* Allocate the problem specific data. */
2238 df_mir_reset, /* Reset global information. */
2239 df_mir_free_bb_info, /* Free basic block info. */
2240 df_mir_local_compute, /* Local compute function. */
2241 df_mir_init, /* Init the solution specific data. */
2242 df_worklist_dataflow, /* Worklist solver. */
2243 df_mir_confluence_0, /* Confluence operator 0. */
2244 df_mir_confluence_n, /* Confluence operator n. */
2245 df_mir_transfer_function, /* Transfer function. */
2246 NULL, /* Finalize function. */
2247 df_mir_free, /* Free all of the problem information. */
2248 df_mir_free, /* Remove this problem from the stack of dataflow problems. */
2249 NULL, /* Debugging. */
2250 df_mir_top_dump, /* Debugging start block. */
2251 df_mir_bottom_dump, /* Debugging end block. */
2252 NULL, /* Debugging start insn. */
2253 NULL, /* Debugging end insn. */
2254 df_mir_verify_solution_start, /* Incremental solution verify start. */
2255 df_mir_verify_solution_end, /* Incremental solution verify end. */
2256 NULL, /* Dependent problem. */
2257 sizeof (class df_mir_bb_info),/* Size of entry of block_info array. */
2258 TV_DF_MIR, /* Timing variable. */
2259 false /* Reset blocks on dropping out of blocks_to_analyze. */
2263 /* Create a new DATAFLOW instance and add it to an existing instance
2264 of DF. */
2266 void
2267 df_mir_add_problem (void)
2269 df_add_problem (&problem_MIR);
2270 /* These will be initialized when df_scan_blocks processes each
2271 block. */
2272 df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2276 /* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2278 void
2279 df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2280 bitmap kill, bitmap gen)
2282 df_ref def;
2284 FOR_EACH_INSN_DEF (def, insn)
2286 unsigned int regno = DF_REF_REGNO (def);
2288 /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
2289 previous gen is irrelevant (and reciprocally). Also, claim that a
2290 register is GEN only if it is in all cases. */
2291 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2293 bitmap_set_bit (kill, regno);
2294 bitmap_clear_bit (gen, regno);
2296 /* In the worst case, partial and conditional defs can leave bits
2297 uninitialized, so assume they do not change anything. */
2298 else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2300 bitmap_set_bit (gen, regno);
2301 bitmap_clear_bit (kill, regno);
2306 /*----------------------------------------------------------------------------
2307 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2309 Link either the defs to the uses and / or the uses to the defs.
2311 These problems are set up like the other dataflow problems so that
2312 they nicely fit into the framework. They are much simpler and only
2313 involve a single traversal of instructions and an examination of
2314 the reaching defs information (the dependent problem).
2315 ----------------------------------------------------------------------------*/
2317 #define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2319 /* Create a du or ud chain from SRC to DST and link it into SRC. */
2321 struct df_link *
2322 df_chain_create (df_ref src, df_ref dst)
2324 struct df_link *head = DF_REF_CHAIN (src);
2325 struct df_link *link = df_chain->block_pool->allocate ();
2327 DF_REF_CHAIN (src) = link;
2328 link->next = head;
2329 link->ref = dst;
2330 return link;
2334 /* Delete any du or ud chains that start at REF and point to
2335 TARGET. */
2336 static void
2337 df_chain_unlink_1 (df_ref ref, df_ref target)
2339 struct df_link *chain = DF_REF_CHAIN (ref);
2340 struct df_link *prev = NULL;
2342 while (chain)
2344 if (chain->ref == target)
2346 if (prev)
2347 prev->next = chain->next;
2348 else
2349 DF_REF_CHAIN (ref) = chain->next;
2350 df_chain->block_pool->remove (chain);
2351 return;
2353 prev = chain;
2354 chain = chain->next;
2359 /* Delete a du or ud chain that leave or point to REF. */
2361 void
2362 df_chain_unlink (df_ref ref)
2364 struct df_link *chain = DF_REF_CHAIN (ref);
2365 while (chain)
2367 struct df_link *next = chain->next;
2368 /* Delete the other side if it exists. */
2369 df_chain_unlink_1 (chain->ref, ref);
2370 df_chain->block_pool->remove (chain);
2371 chain = next;
2373 DF_REF_CHAIN (ref) = NULL;
2377 /* Copy the du or ud chain starting at FROM_REF and attach it to
2378 TO_REF. */
2380 void
2381 df_chain_copy (df_ref to_ref,
2382 struct df_link *from_ref)
2384 while (from_ref)
2386 df_chain_create (to_ref, from_ref->ref);
2387 from_ref = from_ref->next;
2392 /* Remove this problem from the stack of dataflow problems. */
2394 static void
2395 df_chain_remove_problem (void)
2397 bitmap_iterator bi;
2398 unsigned int bb_index;
2400 /* Wholesale destruction of the old chains. */
2401 if (df_chain->block_pool)
2402 delete df_chain->block_pool;
2404 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2406 rtx_insn *insn;
2407 df_ref def, use;
2408 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2410 if (df_chain_problem_p (DF_DU_CHAIN))
2411 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2412 DF_REF_CHAIN (def) = NULL;
2413 if (df_chain_problem_p (DF_UD_CHAIN))
2414 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2415 DF_REF_CHAIN (use) = NULL;
2417 FOR_BB_INSNS (bb, insn)
2418 if (INSN_P (insn))
2420 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2421 if (df_chain_problem_p (DF_DU_CHAIN))
2422 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2423 DF_REF_CHAIN (def) = NULL;
2424 if (df_chain_problem_p (DF_UD_CHAIN))
2426 FOR_EACH_INSN_INFO_USE (use, insn_info)
2427 DF_REF_CHAIN (use) = NULL;
2428 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2429 DF_REF_CHAIN (use) = NULL;
2434 bitmap_clear (df_chain->out_of_date_transfer_functions);
2435 df_chain->block_pool = NULL;
2439 /* Remove the chain problem completely. */
2441 static void
2442 df_chain_fully_remove_problem (void)
2444 df_chain_remove_problem ();
2445 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2446 free (df_chain);
2450 /* Create def-use or use-def chains. */
2452 static void
2453 df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2455 df_chain_remove_problem ();
2456 df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2457 df_chain->optional_p = true;
2461 /* Reset all of the chains when the set of basic blocks changes. */
2463 static void
2464 df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2466 df_chain_remove_problem ();
2470 /* Create the chains for a list of USEs. */
2472 static void
2473 df_chain_create_bb_process_use (bitmap local_rd,
2474 df_ref use,
2475 int top_flag)
2477 bitmap_iterator bi;
2478 unsigned int def_index;
2480 for (; use; use = DF_REF_NEXT_LOC (use))
2482 unsigned int uregno = DF_REF_REGNO (use);
2483 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2484 || (uregno >= FIRST_PSEUDO_REGISTER))
2486 /* Do not want to go through this for an uninitialized var. */
2487 int count = DF_DEFS_COUNT (uregno);
2488 if (count)
2490 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2492 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2493 unsigned int last_index = first_index + count - 1;
2495 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2497 df_ref def;
2498 if (def_index > last_index)
2499 break;
2501 def = DF_DEFS_GET (def_index);
2502 if (df_chain_problem_p (DF_DU_CHAIN))
2503 df_chain_create (def, use);
2504 if (df_chain_problem_p (DF_UD_CHAIN))
2505 df_chain_create (use, def);
2514 /* Create chains from reaching defs bitmaps for basic block BB. */
2516 static void
2517 df_chain_create_bb (unsigned int bb_index)
2519 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2520 class df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2521 rtx_insn *insn;
2522 bitmap_head cpy;
2524 bitmap_initialize (&cpy, &bitmap_default_obstack);
2525 bitmap_copy (&cpy, &bb_info->in);
2526 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2528 /* Since we are going forwards, process the artificial uses first
2529 then the artificial defs second. */
2531 #ifdef EH_USES
2532 /* Create the chains for the artificial uses from the EH_USES at the
2533 beginning of the block. */
2535 /* Artificials are only hard regs. */
2536 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2537 df_chain_create_bb_process_use (&cpy,
2538 df_get_artificial_uses (bb->index),
2539 DF_REF_AT_TOP);
2540 #endif
2542 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2544 /* Process the regular instructions next. */
2545 FOR_BB_INSNS (bb, insn)
2546 if (INSN_P (insn))
2548 unsigned int uid = INSN_UID (insn);
2550 /* First scan the uses and link them up with the defs that remain
2551 in the cpy vector. */
2552 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2553 if (df->changeable_flags & DF_EQ_NOTES)
2554 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2556 /* Since we are going forwards, process the defs second. */
2557 df_rd_simulate_one_insn (bb, insn, &cpy);
2560 /* Create the chains for the artificial uses of the hard registers
2561 at the end of the block. */
2562 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2563 df_chain_create_bb_process_use (&cpy,
2564 df_get_artificial_uses (bb->index),
2567 bitmap_clear (&cpy);
2570 /* Create def-use chains from reaching use bitmaps for basic blocks
2571 in BLOCKS. */
2573 static void
2574 df_chain_finalize (bitmap all_blocks)
2576 unsigned int bb_index;
2577 bitmap_iterator bi;
2579 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2581 df_chain_create_bb (bb_index);
2586 /* Free all storage associated with the problem. */
2588 static void
2589 df_chain_free (void)
2591 delete df_chain->block_pool;
2592 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2593 free (df_chain);
2597 /* Debugging info. */
2599 static void
2600 df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2602 /* Artificials are only hard regs. */
2603 if (df->changeable_flags & DF_NO_HARD_REGS)
2604 return;
2605 if (df_chain_problem_p (DF_UD_CHAIN))
2607 df_ref use;
2609 fprintf (file,
2610 ";; UD chains for artificial uses at %s\n",
2611 top ? "top" : "bottom");
2612 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2613 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2614 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2616 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2617 df_chain_dump (DF_REF_CHAIN (use), file);
2618 fprintf (file, "\n");
2621 if (df_chain_problem_p (DF_DU_CHAIN))
2623 df_ref def;
2625 fprintf (file,
2626 ";; DU chains for artificial defs at %s\n",
2627 top ? "top" : "bottom");
2628 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2629 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2630 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2632 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2633 df_chain_dump (DF_REF_CHAIN (def), file);
2634 fprintf (file, "\n");
2639 static void
2640 df_chain_top_dump (basic_block bb, FILE *file)
2642 df_chain_bb_dump (bb, file, /*top=*/true);
2645 static void
2646 df_chain_bottom_dump (basic_block bb, FILE *file)
2648 df_chain_bb_dump (bb, file, /*top=*/false);
2651 static void
2652 df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2654 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2656 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2657 df_ref use;
2659 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2660 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2661 FOR_EACH_INSN_INFO_USE (use, insn_info)
2662 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2663 || !(df->changeable_flags & DF_NO_HARD_REGS))
2665 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2666 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2667 fprintf (file, "read/write ");
2668 df_chain_dump (DF_REF_CHAIN (use), file);
2669 fprintf (file, "\n");
2671 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2672 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2673 || !(df->changeable_flags & DF_NO_HARD_REGS))
2675 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2676 df_chain_dump (DF_REF_CHAIN (use), file);
2677 fprintf (file, "\n");
2682 static void
2683 df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2685 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2687 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2688 df_ref def;
2689 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2690 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2691 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2692 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2693 || !(df->changeable_flags & DF_NO_HARD_REGS))
2695 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2696 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2697 fprintf (file, "read/write ");
2698 df_chain_dump (DF_REF_CHAIN (def), file);
2699 fprintf (file, "\n");
2701 fprintf (file, "\n");
2705 static const struct df_problem problem_CHAIN =
2707 DF_CHAIN, /* Problem id. */
2708 DF_NONE, /* Direction. */
2709 df_chain_alloc, /* Allocate the problem specific data. */
2710 df_chain_reset, /* Reset global information. */
2711 NULL, /* Free basic block info. */
2712 NULL, /* Local compute function. */
2713 NULL, /* Init the solution specific data. */
2714 NULL, /* Iterative solver. */
2715 NULL, /* Confluence operator 0. */
2716 NULL, /* Confluence operator n. */
2717 NULL, /* Transfer function. */
2718 df_chain_finalize, /* Finalize function. */
2719 df_chain_free, /* Free all of the problem information. */
2720 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2721 NULL, /* Debugging. */
2722 df_chain_top_dump, /* Debugging start block. */
2723 df_chain_bottom_dump, /* Debugging end block. */
2724 df_chain_insn_top_dump, /* Debugging start insn. */
2725 df_chain_insn_bottom_dump, /* Debugging end insn. */
2726 NULL, /* Incremental solution verify start. */
2727 NULL, /* Incremental solution verify end. */
2728 &problem_RD, /* Dependent problem. */
2729 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2730 TV_DF_CHAIN, /* Timing variable. */
2731 false /* Reset blocks on dropping out of blocks_to_analyze. */
2735 /* Create a new DATAFLOW instance and add it to an existing instance
2736 of DF. The returned structure is what is used to get at the
2737 solution. */
2739 void
2740 df_chain_add_problem (unsigned int chain_flags)
2742 df_add_problem (&problem_CHAIN);
2743 df_chain->local_flags = chain_flags;
2744 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2747 #undef df_chain_problem_p
2750 /*----------------------------------------------------------------------------
2751 WORD LEVEL LIVE REGISTERS
2753 Find the locations in the function where any use of a pseudo can
2754 reach in the backwards direction. In and out bitvectors are built
2755 for each basic block. We only track pseudo registers that have a
2756 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2757 contain two bits corresponding to each of the subwords.
2759 ----------------------------------------------------------------------------*/
2761 /* Private data used to verify the solution for this problem. */
2762 struct df_word_lr_problem_data
2764 /* An obstack for the bitmaps we need for this problem. */
2765 bitmap_obstack word_lr_bitmaps;
2769 /* Free basic block info. */
2771 static void
2772 df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2773 void *vbb_info)
2775 class df_word_lr_bb_info *bb_info = (class df_word_lr_bb_info *) vbb_info;
2776 if (bb_info)
2778 bitmap_clear (&bb_info->use);
2779 bitmap_clear (&bb_info->def);
2780 bitmap_clear (&bb_info->in);
2781 bitmap_clear (&bb_info->out);
2786 /* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2787 not touched unless the block is new. */
2789 static void
2790 df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2792 unsigned int bb_index;
2793 bitmap_iterator bi;
2794 basic_block bb;
2795 struct df_word_lr_problem_data *problem_data
2796 = XNEW (struct df_word_lr_problem_data);
2798 df_word_lr->problem_data = problem_data;
2800 df_grow_bb_info (df_word_lr);
2802 /* Create the mapping from regnos to slots. This does not change
2803 unless the problem is destroyed and recreated. In particular, if
2804 we end up deleting the only insn that used a subreg, we do not
2805 want to redo the mapping because this would invalidate everything
2806 else. */
2808 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2810 FOR_EACH_BB_FN (bb, cfun)
2811 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2813 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2814 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2816 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2818 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2820 /* When bitmaps are already initialized, just clear them. */
2821 if (bb_info->use.obstack)
2823 bitmap_clear (&bb_info->def);
2824 bitmap_clear (&bb_info->use);
2826 else
2828 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2829 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2830 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2831 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2835 df_word_lr->optional_p = true;
2839 /* Reset the global solution for recalculation. */
2841 static void
2842 df_word_lr_reset (bitmap all_blocks)
2844 unsigned int bb_index;
2845 bitmap_iterator bi;
2847 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2849 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2850 gcc_assert (bb_info);
2851 bitmap_clear (&bb_info->in);
2852 bitmap_clear (&bb_info->out);
2856 /* Examine REF, and if it is for a reg we're interested in, set or
2857 clear the bits corresponding to its subwords from the bitmap
2858 according to IS_SET. LIVE is the bitmap we should update. We do
2859 not track hard regs or pseudos of any size other than 2 *
2860 UNITS_PER_WORD.
2861 We return true if we changed the bitmap, or if we encountered a register
2862 we're not tracking. */
2864 bool
2865 df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2867 rtx orig_reg = DF_REF_REG (ref);
2868 rtx reg = orig_reg;
2869 machine_mode reg_mode;
2870 unsigned regno;
2871 /* Left at -1 for whole accesses. */
2872 int which_subword = -1;
2873 bool changed = false;
2875 if (GET_CODE (reg) == SUBREG)
2876 reg = SUBREG_REG (orig_reg);
2877 regno = REGNO (reg);
2878 reg_mode = GET_MODE (reg);
2879 if (regno < FIRST_PSEUDO_REGISTER
2880 || maybe_ne (GET_MODE_SIZE (reg_mode), 2 * UNITS_PER_WORD))
2881 return true;
2883 if (GET_CODE (orig_reg) == SUBREG
2884 && read_modify_subreg_p (orig_reg))
2886 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2887 if (subreg_lowpart_p (orig_reg))
2888 which_subword = 0;
2889 else
2890 which_subword = 1;
2892 if (is_set)
2894 if (which_subword != 1)
2895 changed |= bitmap_set_bit (live, regno * 2);
2896 if (which_subword != 0)
2897 changed |= bitmap_set_bit (live, regno * 2 + 1);
2899 else
2901 if (which_subword != 1)
2902 changed |= bitmap_clear_bit (live, regno * 2);
2903 if (which_subword != 0)
2904 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2906 return changed;
2909 /* Compute local live register info for basic block BB. */
2911 static void
2912 df_word_lr_bb_local_compute (unsigned int bb_index)
2914 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2915 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2916 rtx_insn *insn;
2917 df_ref def, use;
2919 /* Ensure that artificial refs don't contain references to pseudos. */
2920 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2921 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2923 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2924 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2926 FOR_BB_INSNS_REVERSE (bb, insn)
2928 if (!NONDEBUG_INSN_P (insn))
2929 continue;
2931 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2932 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2933 /* If the def is to only part of the reg, it does
2934 not kill the other defs that reach here. */
2935 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2937 df_word_lr_mark_ref (def, true, &bb_info->def);
2938 df_word_lr_mark_ref (def, false, &bb_info->use);
2940 FOR_EACH_INSN_INFO_USE (use, insn_info)
2941 df_word_lr_mark_ref (use, true, &bb_info->use);
2946 /* Compute local live register info for each basic block within BLOCKS. */
2948 static void
2949 df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2951 unsigned int bb_index;
2952 bitmap_iterator bi;
2954 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2956 if (bb_index == EXIT_BLOCK)
2958 unsigned regno;
2959 bitmap_iterator bi;
2960 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2961 regno, bi)
2962 gcc_unreachable ();
2964 else
2965 df_word_lr_bb_local_compute (bb_index);
2968 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2972 /* Initialize the solution vectors. */
2974 static void
2975 df_word_lr_init (bitmap all_blocks)
2977 unsigned int bb_index;
2978 bitmap_iterator bi;
2980 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2982 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2983 bitmap_copy (&bb_info->in, &bb_info->use);
2984 bitmap_clear (&bb_info->out);
2989 /* Confluence function that ignores fake edges. */
2991 static bool
2992 df_word_lr_confluence_n (edge e)
2994 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2995 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2997 return bitmap_ior_into (op1, op2);
3001 /* Transfer function. */
3003 static bool
3004 df_word_lr_transfer_function (int bb_index)
3006 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
3007 bitmap in = &bb_info->in;
3008 bitmap out = &bb_info->out;
3009 bitmap use = &bb_info->use;
3010 bitmap def = &bb_info->def;
3012 return bitmap_ior_and_compl (in, use, out, def);
3016 /* Free all storage associated with the problem. */
3018 static void
3019 df_word_lr_free (void)
3021 struct df_word_lr_problem_data *problem_data
3022 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
3024 if (df_word_lr->block_info)
3026 df_word_lr->block_info_size = 0;
3027 free (df_word_lr->block_info);
3028 df_word_lr->block_info = NULL;
3031 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
3032 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
3033 free (problem_data);
3034 free (df_word_lr);
3038 /* Debugging info at top of bb. */
3040 static void
3041 df_word_lr_top_dump (basic_block bb, FILE *file)
3043 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3044 if (!bb_info)
3045 return;
3047 fprintf (file, ";; blr in \t");
3048 df_print_word_regset (file, &bb_info->in);
3049 fprintf (file, ";; blr use \t");
3050 df_print_word_regset (file, &bb_info->use);
3051 fprintf (file, ";; blr def \t");
3052 df_print_word_regset (file, &bb_info->def);
3056 /* Debugging info at bottom of bb. */
3058 static void
3059 df_word_lr_bottom_dump (basic_block bb, FILE *file)
3061 class df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3062 if (!bb_info)
3063 return;
3065 fprintf (file, ";; blr out \t");
3066 df_print_word_regset (file, &bb_info->out);
3070 /* All of the information associated with every instance of the problem. */
3072 static const struct df_problem problem_WORD_LR =
3074 DF_WORD_LR, /* Problem id. */
3075 DF_BACKWARD, /* Direction. */
3076 df_word_lr_alloc, /* Allocate the problem specific data. */
3077 df_word_lr_reset, /* Reset global information. */
3078 df_word_lr_free_bb_info, /* Free basic block info. */
3079 df_word_lr_local_compute, /* Local compute function. */
3080 df_word_lr_init, /* Init the solution specific data. */
3081 df_worklist_dataflow, /* Worklist solver. */
3082 NULL, /* Confluence operator 0. */
3083 df_word_lr_confluence_n, /* Confluence operator n. */
3084 df_word_lr_transfer_function, /* Transfer function. */
3085 NULL, /* Finalize function. */
3086 df_word_lr_free, /* Free all of the problem information. */
3087 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
3088 NULL, /* Debugging. */
3089 df_word_lr_top_dump, /* Debugging start block. */
3090 df_word_lr_bottom_dump, /* Debugging end block. */
3091 NULL, /* Debugging start insn. */
3092 NULL, /* Debugging end insn. */
3093 NULL, /* Incremental solution verify start. */
3094 NULL, /* Incremental solution verify end. */
3095 NULL, /* Dependent problem. */
3096 sizeof (class df_word_lr_bb_info),/* Size of entry of block_info array. */
3097 TV_DF_WORD_LR, /* Timing variable. */
3098 false /* Reset blocks on dropping out of blocks_to_analyze. */
3102 /* Create a new DATAFLOW instance and add it to an existing instance
3103 of DF. The returned structure is what is used to get at the
3104 solution. */
3106 void
3107 df_word_lr_add_problem (void)
3109 df_add_problem (&problem_WORD_LR);
3110 /* These will be initialized when df_scan_blocks processes each
3111 block. */
3112 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3116 /* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
3117 any bits, which is used by the caller to determine whether a set is
3118 necessary. We also return true if there are other reasons not to delete
3119 an insn. */
3121 bool
3122 df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3124 bool changed = false;
3125 df_ref def;
3127 FOR_EACH_INSN_DEF (def, insn)
3128 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3129 changed = true;
3130 else
3131 changed |= df_word_lr_mark_ref (def, false, live);
3132 return changed;
3136 /* Simulate the effects of the uses of INSN on LIVE. */
3138 void
3139 df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3141 df_ref use;
3143 FOR_EACH_INSN_USE (use, insn)
3144 df_word_lr_mark_ref (use, true, live);
3147 /*----------------------------------------------------------------------------
3148 This problem computes REG_DEAD and REG_UNUSED notes.
3149 ----------------------------------------------------------------------------*/
3151 static void
3152 df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3154 df_note->optional_p = true;
3157 /* This is only used if REG_DEAD_DEBUGGING is in effect. */
3158 static void
3159 df_print_note (const char *prefix, rtx_insn *insn, rtx note)
3161 if (dump_file)
3163 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3164 print_rtl (dump_file, note);
3165 fprintf (dump_file, "\n");
3170 /* After reg-stack, the x86 floating point stack regs are difficult to
3171 analyze because of all of the pushes, pops and rotations. Thus, we
3172 just leave the notes alone. */
3174 #ifdef STACK_REGS
3175 static inline bool
3176 df_ignore_stack_reg (int regno)
3178 return regstack_completed
3179 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3181 #else
3182 static inline bool
3183 df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3185 return false;
3187 #endif
3190 /* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
3192 static void
3193 df_remove_dead_and_unused_notes (rtx_insn *insn)
3195 rtx *pprev = &REG_NOTES (insn);
3196 rtx link = *pprev;
3198 while (link)
3200 switch (REG_NOTE_KIND (link))
3202 case REG_DEAD:
3203 /* After reg-stack, we need to ignore any unused notes
3204 for the stack registers. */
3205 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3207 pprev = &XEXP (link, 1);
3208 link = *pprev;
3210 else
3212 rtx next = XEXP (link, 1);
3213 if (REG_DEAD_DEBUGGING)
3214 df_print_note ("deleting: ", insn, link);
3215 free_EXPR_LIST_node (link);
3216 *pprev = link = next;
3218 break;
3220 case REG_UNUSED:
3221 /* After reg-stack, we need to ignore any unused notes
3222 for the stack registers. */
3223 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3225 pprev = &XEXP (link, 1);
3226 link = *pprev;
3228 else
3230 rtx next = XEXP (link, 1);
3231 if (REG_DEAD_DEBUGGING)
3232 df_print_note ("deleting: ", insn, link);
3233 free_EXPR_LIST_node (link);
3234 *pprev = link = next;
3236 break;
3238 default:
3239 pprev = &XEXP (link, 1);
3240 link = *pprev;
3241 break;
3246 /* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
3247 as the bitmap of currently live registers. */
3249 static void
3250 df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3252 rtx *pprev = &REG_NOTES (insn);
3253 rtx link = *pprev;
3255 while (link)
3257 switch (REG_NOTE_KIND (link))
3259 case REG_EQUAL:
3260 case REG_EQUIV:
3262 /* Remove the notes that refer to dead registers. As we have at most
3263 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3264 so we need to purge the complete EQ_USES vector when removing
3265 the note using df_notes_rescan. */
3266 df_ref use;
3267 bool deleted = false;
3269 FOR_EACH_INSN_EQ_USE (use, insn)
3270 if (DF_REF_REGNO (use) >= FIRST_PSEUDO_REGISTER
3271 && DF_REF_LOC (use)
3272 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3273 && !bitmap_bit_p (live, DF_REF_REGNO (use))
3274 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3276 deleted = true;
3277 break;
3279 if (deleted)
3281 rtx next;
3282 if (REG_DEAD_DEBUGGING)
3283 df_print_note ("deleting: ", insn, link);
3284 next = XEXP (link, 1);
3285 free_EXPR_LIST_node (link);
3286 *pprev = link = next;
3287 df_notes_rescan (insn);
3289 else
3291 pprev = &XEXP (link, 1);
3292 link = *pprev;
3294 break;
3297 default:
3298 pprev = &XEXP (link, 1);
3299 link = *pprev;
3300 break;
3305 /* Set a NOTE_TYPE note for REG in INSN. */
3307 static inline void
3308 df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3310 gcc_checking_assert (!DEBUG_INSN_P (insn));
3311 add_reg_note (insn, note_type, reg);
3314 /* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3315 arguments. Return true if the register value described by MWS's
3316 mw_reg is known to be completely unused, and if mw_reg can therefore
3317 be used in a REG_UNUSED note. */
3319 static bool
3320 df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3321 bitmap live, bitmap artificial_uses)
3323 unsigned int r;
3325 /* If MWS describes a partial reference, create REG_UNUSED notes for
3326 individual hard registers. */
3327 if (mws->flags & DF_REF_PARTIAL)
3328 return false;
3330 /* Likewise if some part of the register is used. */
3331 for (r = mws->start_regno; r <= mws->end_regno; r++)
3332 if (bitmap_bit_p (live, r)
3333 || bitmap_bit_p (artificial_uses, r))
3334 return false;
3336 gcc_assert (REG_P (mws->mw_reg));
3337 return true;
3341 /* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3342 based on the bits in LIVE. Do not generate notes for registers in
3343 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3344 not generated if the reg is both read and written by the
3345 instruction.
3348 static void
3349 df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3350 bitmap live, bitmap do_not_gen,
3351 bitmap artificial_uses,
3352 struct dead_debug_local *debug)
3354 unsigned int r;
3356 if (REG_DEAD_DEBUGGING && dump_file)
3357 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3358 mws->start_regno, mws->end_regno);
3360 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3362 unsigned int regno = mws->start_regno;
3363 df_set_note (REG_UNUSED, insn, mws->mw_reg);
3364 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3366 if (REG_DEAD_DEBUGGING)
3367 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3369 bitmap_set_bit (do_not_gen, regno);
3370 /* Only do this if the value is totally dead. */
3372 else
3373 for (r = mws->start_regno; r <= mws->end_regno; r++)
3375 if (!bitmap_bit_p (live, r)
3376 && !bitmap_bit_p (artificial_uses, r))
3378 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3379 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3380 if (REG_DEAD_DEBUGGING)
3381 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3383 bitmap_set_bit (do_not_gen, r);
3388 /* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3389 arguments. Return true if the register value described by MWS's
3390 mw_reg is known to be completely dead, and if mw_reg can therefore
3391 be used in a REG_DEAD note. */
3393 static bool
3394 df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3395 bitmap live, bitmap artificial_uses,
3396 bitmap do_not_gen)
3398 unsigned int r;
3400 /* If MWS describes a partial reference, create REG_DEAD notes for
3401 individual hard registers. */
3402 if (mws->flags & DF_REF_PARTIAL)
3403 return false;
3405 /* Likewise if some part of the register is not dead. */
3406 for (r = mws->start_regno; r <= mws->end_regno; r++)
3407 if (bitmap_bit_p (live, r)
3408 || bitmap_bit_p (artificial_uses, r)
3409 || bitmap_bit_p (do_not_gen, r))
3410 return false;
3412 gcc_assert (REG_P (mws->mw_reg));
3413 return true;
3416 /* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3417 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3418 from being set if the instruction both reads and writes the
3419 register. */
3421 static void
3422 df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3423 bitmap live, bitmap do_not_gen,
3424 bitmap artificial_uses, bool *added_notes_p)
3426 unsigned int r;
3427 bool is_debug = *added_notes_p;
3429 *added_notes_p = false;
3431 if (REG_DEAD_DEBUGGING && dump_file)
3433 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3434 mws->start_regno, mws->end_regno);
3435 df_print_regset (dump_file, do_not_gen);
3436 fprintf (dump_file, " live =");
3437 df_print_regset (dump_file, live);
3438 fprintf (dump_file, " artificial uses =");
3439 df_print_regset (dump_file, artificial_uses);
3442 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3444 if (is_debug)
3446 *added_notes_p = true;
3447 return;
3449 /* Add a dead note for the entire multi word register. */
3450 df_set_note (REG_DEAD, insn, mws->mw_reg);
3451 if (REG_DEAD_DEBUGGING)
3452 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3454 else
3456 for (r = mws->start_regno; r <= mws->end_regno; r++)
3457 if (!bitmap_bit_p (live, r)
3458 && !bitmap_bit_p (artificial_uses, r)
3459 && !bitmap_bit_p (do_not_gen, r))
3461 if (is_debug)
3463 *added_notes_p = true;
3464 return;
3466 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3467 if (REG_DEAD_DEBUGGING)
3468 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3471 return;
3475 /* Create a REG_UNUSED note if necessary for DEF in INSN updating
3476 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3478 static void
3479 df_create_unused_note (rtx_insn *insn, df_ref def,
3480 bitmap live, bitmap artificial_uses,
3481 struct dead_debug_local *debug)
3483 unsigned int dregno = DF_REF_REGNO (def);
3485 if (REG_DEAD_DEBUGGING && dump_file)
3487 fprintf (dump_file, " regular looking at def ");
3488 df_ref_debug (def, dump_file);
3491 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3492 || bitmap_bit_p (live, dregno)
3493 || bitmap_bit_p (artificial_uses, dregno)
3494 || df_ignore_stack_reg (dregno)))
3496 rtx reg = (DF_REF_LOC (def))
3497 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3498 df_set_note (REG_UNUSED, insn, reg);
3499 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3500 if (REG_DEAD_DEBUGGING)
3501 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3504 return;
3508 /* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3509 info: lifetime, bb, and number of defs and uses for basic block
3510 BB. The three bitvectors are scratch regs used here. */
3512 static void
3513 df_note_bb_compute (unsigned int bb_index,
3514 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3516 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3517 rtx_insn *insn;
3518 df_ref def, use;
3519 struct dead_debug_local debug;
3521 dead_debug_local_init (&debug, NULL, NULL);
3523 bitmap_copy (live, df_get_live_out (bb));
3524 bitmap_clear (artificial_uses);
3526 if (REG_DEAD_DEBUGGING && dump_file)
3528 fprintf (dump_file, "live at bottom ");
3529 df_print_regset (dump_file, live);
3532 /* Process the artificial defs and uses at the bottom of the block
3533 to begin processing. */
3534 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3536 if (REG_DEAD_DEBUGGING && dump_file)
3537 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3539 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3540 bitmap_clear_bit (live, DF_REF_REGNO (def));
3543 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3544 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3546 unsigned int regno = DF_REF_REGNO (use);
3547 bitmap_set_bit (live, regno);
3549 /* Notes are not generated for any of the artificial registers
3550 at the bottom of the block. */
3551 bitmap_set_bit (artificial_uses, regno);
3554 if (REG_DEAD_DEBUGGING && dump_file)
3556 fprintf (dump_file, "live before artificials out ");
3557 df_print_regset (dump_file, live);
3560 FOR_BB_INSNS_REVERSE (bb, insn)
3562 if (!INSN_P (insn))
3563 continue;
3565 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3566 df_mw_hardreg *mw;
3567 int debug_insn;
3569 debug_insn = DEBUG_INSN_P (insn);
3571 bitmap_clear (do_not_gen);
3572 df_remove_dead_and_unused_notes (insn);
3574 /* Process the defs. */
3575 if (CALL_P (insn))
3577 if (REG_DEAD_DEBUGGING && dump_file)
3579 fprintf (dump_file, "processing call %d\n live =",
3580 INSN_UID (insn));
3581 df_print_regset (dump_file, live);
3584 /* We only care about real sets for calls. Clobbers cannot
3585 be depended on to really die. */
3586 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3587 if ((DF_MWS_REG_DEF_P (mw))
3588 && !df_ignore_stack_reg (mw->start_regno))
3589 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3590 artificial_uses, &debug);
3592 /* All of the defs except the return value are some sort of
3593 clobber. This code is for the return. */
3594 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3596 unsigned int dregno = DF_REF_REGNO (def);
3597 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3599 df_create_unused_note (insn,
3600 def, live, artificial_uses, &debug);
3601 bitmap_set_bit (do_not_gen, dregno);
3604 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3605 bitmap_clear_bit (live, dregno);
3608 else
3610 /* Regular insn. */
3611 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3612 if (DF_MWS_REG_DEF_P (mw))
3613 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3614 artificial_uses, &debug);
3616 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3618 unsigned int dregno = DF_REF_REGNO (def);
3619 df_create_unused_note (insn,
3620 def, live, artificial_uses, &debug);
3622 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3623 bitmap_set_bit (do_not_gen, dregno);
3625 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3626 bitmap_clear_bit (live, dregno);
3630 /* Process the uses. */
3631 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3632 if (DF_MWS_REG_USE_P (mw)
3633 && !df_ignore_stack_reg (mw->start_regno))
3635 bool really_add_notes = debug_insn != 0;
3637 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3638 artificial_uses,
3639 &really_add_notes);
3641 if (really_add_notes)
3642 debug_insn = -1;
3645 FOR_EACH_INSN_INFO_USE (use, insn_info)
3647 unsigned int uregno = DF_REF_REGNO (use);
3649 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3651 fprintf (dump_file, " regular looking at use ");
3652 df_ref_debug (use, dump_file);
3655 if (!bitmap_bit_p (live, uregno))
3657 if (debug_insn)
3659 if (debug_insn > 0)
3661 /* We won't add REG_UNUSED or REG_DEAD notes for
3662 these, so we don't have to mess with them in
3663 debug insns either. */
3664 if (!bitmap_bit_p (artificial_uses, uregno)
3665 && !df_ignore_stack_reg (uregno))
3666 dead_debug_add (&debug, use, uregno);
3667 continue;
3669 break;
3671 else
3672 dead_debug_insert_temp (&debug, uregno, insn,
3673 DEBUG_TEMP_BEFORE_WITH_REG);
3675 if ( (!(DF_REF_FLAGS (use)
3676 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3677 && (!bitmap_bit_p (do_not_gen, uregno))
3678 && (!bitmap_bit_p (artificial_uses, uregno))
3679 && (!df_ignore_stack_reg (uregno)))
3681 rtx reg = (DF_REF_LOC (use))
3682 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3683 df_set_note (REG_DEAD, insn, reg);
3685 if (REG_DEAD_DEBUGGING)
3686 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3688 /* This register is now live. */
3689 bitmap_set_bit (live, uregno);
3693 df_remove_dead_eq_notes (insn, live);
3695 if (debug_insn == -1)
3697 /* ??? We could probably do better here, replacing dead
3698 registers with their definitions. */
3699 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3700 df_insn_rescan_debug_internal (insn);
3704 dead_debug_local_finish (&debug, NULL);
3708 /* Compute register info: lifetime, bb, and number of defs and uses. */
3709 static void
3710 df_note_compute (bitmap all_blocks)
3712 unsigned int bb_index;
3713 bitmap_iterator bi;
3714 bitmap_head live, do_not_gen, artificial_uses;
3716 bitmap_initialize (&live, &df_bitmap_obstack);
3717 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3718 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3720 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3722 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3723 pseudos in debug insns because we don't always (re)visit blocks
3724 with death points after visiting dead uses. Even changing this
3725 loop to postorder would still leave room for visiting a death
3726 point before visiting a subsequent debug use. */
3727 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3730 bitmap_clear (&live);
3731 bitmap_clear (&do_not_gen);
3732 bitmap_clear (&artificial_uses);
3736 /* Free all storage associated with the problem. */
3738 static void
3739 df_note_free (void)
3741 free (df_note);
3745 /* All of the information associated every instance of the problem. */
3747 static const struct df_problem problem_NOTE =
3749 DF_NOTE, /* Problem id. */
3750 DF_NONE, /* Direction. */
3751 df_note_alloc, /* Allocate the problem specific data. */
3752 NULL, /* Reset global information. */
3753 NULL, /* Free basic block info. */
3754 df_note_compute, /* Local compute function. */
3755 NULL, /* Init the solution specific data. */
3756 NULL, /* Iterative solver. */
3757 NULL, /* Confluence operator 0. */
3758 NULL, /* Confluence operator n. */
3759 NULL, /* Transfer function. */
3760 NULL, /* Finalize function. */
3761 df_note_free, /* Free all of the problem information. */
3762 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3763 NULL, /* Debugging. */
3764 NULL, /* Debugging start block. */
3765 NULL, /* Debugging end block. */
3766 NULL, /* Debugging start insn. */
3767 NULL, /* Debugging end insn. */
3768 NULL, /* Incremental solution verify start. */
3769 NULL, /* Incremental solution verify end. */
3770 &problem_LR, /* Dependent problem. */
3771 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3772 TV_DF_NOTE, /* Timing variable. */
3773 false /* Reset blocks on dropping out of blocks_to_analyze. */
3777 /* Create a new DATAFLOW instance and add it to an existing instance
3778 of DF. The returned structure is what is used to get at the
3779 solution. */
3781 void
3782 df_note_add_problem (void)
3784 df_add_problem (&problem_NOTE);
3790 /*----------------------------------------------------------------------------
3791 Functions for simulating the effects of single insns.
3793 You can either simulate in the forwards direction, starting from
3794 the top of a block or the backwards direction from the end of the
3795 block. If you go backwards, defs are examined first to clear bits,
3796 then uses are examined to set bits. If you go forwards, defs are
3797 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3798 are examined to clear bits. In either case, the result of examining
3799 a def can be undone (respectively by a use or a REG_UNUSED note).
3801 If you start at the top of the block, use one of DF_LIVE_IN or
3802 DF_LR_IN. If you start at the bottom of the block use one of
3803 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3804 THEY WILL BE DESTROYED.
3805 ----------------------------------------------------------------------------*/
3808 /* Find the set of DEFs for INSN. */
3810 void
3811 df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3813 df_ref def;
3815 FOR_EACH_INSN_DEF (def, insn)
3816 bitmap_set_bit (defs, DF_REF_REGNO (def));
3819 /* Find the set of uses for INSN. This includes partial defs. */
3821 static void
3822 df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3824 df_ref def, use;
3825 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3827 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3828 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3829 bitmap_set_bit (uses, DF_REF_REGNO (def));
3830 FOR_EACH_INSN_INFO_USE (use, insn_info)
3831 bitmap_set_bit (uses, DF_REF_REGNO (use));
3834 /* Find the set of real DEFs, which are not clobbers, for INSN. */
3836 void
3837 df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3839 df_ref def;
3841 FOR_EACH_INSN_DEF (def, insn)
3842 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3843 bitmap_set_bit (defs, DF_REF_REGNO (def));
3847 /* Simulate the effects of the defs of INSN on LIVE. */
3849 void
3850 df_simulate_defs (rtx_insn *insn, bitmap live)
3852 df_ref def;
3854 FOR_EACH_INSN_DEF (def, insn)
3856 unsigned int dregno = DF_REF_REGNO (def);
3858 /* If the def is to only part of the reg, it does
3859 not kill the other defs that reach here. */
3860 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3861 bitmap_clear_bit (live, dregno);
3866 /* Simulate the effects of the uses of INSN on LIVE. */
3868 void
3869 df_simulate_uses (rtx_insn *insn, bitmap live)
3871 df_ref use;
3873 if (DEBUG_INSN_P (insn))
3874 return;
3876 FOR_EACH_INSN_USE (use, insn)
3877 /* Add use to set of uses in this BB. */
3878 bitmap_set_bit (live, DF_REF_REGNO (use));
3882 /* Add back the always live regs in BB to LIVE. */
3884 static inline void
3885 df_simulate_fixup_sets (basic_block bb, bitmap live)
3887 /* These regs are considered always live so if they end up dying
3888 because of some def, we need to bring the back again. */
3889 if (bb_has_eh_pred (bb))
3890 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3891 else
3892 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3896 /*----------------------------------------------------------------------------
3897 The following three functions are used only for BACKWARDS scanning:
3898 i.e. they process the defs before the uses.
3900 df_simulate_initialize_backwards should be called first with a
3901 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3902 df_simulate_one_insn_backwards should be called for each insn in
3903 the block, starting with the last one. Finally,
3904 df_simulate_finalize_backwards can be called to get a new value
3905 of the sets at the top of the block (this is rarely used).
3906 ----------------------------------------------------------------------------*/
3908 /* Apply the artificial uses and defs at the end of BB in a backwards
3909 direction. */
3911 void
3912 df_simulate_initialize_backwards (basic_block bb, bitmap live)
3914 df_ref def, use;
3915 int bb_index = bb->index;
3917 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3918 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3919 bitmap_clear_bit (live, DF_REF_REGNO (def));
3921 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3922 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3923 bitmap_set_bit (live, DF_REF_REGNO (use));
3927 /* Simulate the backwards effects of INSN on the bitmap LIVE. */
3929 void
3930 df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3932 if (!NONDEBUG_INSN_P (insn))
3933 return;
3935 df_simulate_defs (insn, live);
3936 df_simulate_uses (insn, live);
3937 df_simulate_fixup_sets (bb, live);
3941 /* Apply the artificial uses and defs at the top of BB in a backwards
3942 direction. */
3944 void
3945 df_simulate_finalize_backwards (basic_block bb, bitmap live)
3947 df_ref def;
3948 #ifdef EH_USES
3949 df_ref use;
3950 #endif
3951 int bb_index = bb->index;
3953 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3954 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3955 bitmap_clear_bit (live, DF_REF_REGNO (def));
3957 #ifdef EH_USES
3958 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3959 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3960 bitmap_set_bit (live, DF_REF_REGNO (use));
3961 #endif
3963 /*----------------------------------------------------------------------------
3964 The following three functions are used only for FORWARDS scanning:
3965 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3966 Thus it is important to add the DF_NOTES problem to the stack of
3967 problems computed before using these functions.
3969 df_simulate_initialize_forwards should be called first with a
3970 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3971 df_simulate_one_insn_forwards should be called for each insn in
3972 the block, starting with the first one.
3973 ----------------------------------------------------------------------------*/
3975 /* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3976 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3977 defs live. */
3979 void
3980 df_simulate_initialize_forwards (basic_block bb, bitmap live)
3982 df_ref def;
3983 int bb_index = bb->index;
3985 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3986 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3987 bitmap_set_bit (live, DF_REF_REGNO (def));
3990 /* Simulate the forwards effects of INSN on the bitmap LIVE. */
3992 void
3993 df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3995 rtx link;
3996 if (! INSN_P (insn))
3997 return;
3999 /* Make sure that DF_NOTE really is an active df problem. */
4000 gcc_assert (df_note);
4002 /* Note that this is the opposite as how the problem is defined, because
4003 in the LR problem defs _kill_ liveness. However, they do so backwards,
4004 while here the scan is performed forwards! So, first assume that the
4005 def is live, and if this is not true REG_UNUSED notes will rectify the
4006 situation. */
4007 df_simulate_find_noclobber_defs (insn, live);
4009 /* Clear all of the registers that go dead. */
4010 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
4012 switch (REG_NOTE_KIND (link))
4014 case REG_DEAD:
4015 case REG_UNUSED:
4017 rtx reg = XEXP (link, 0);
4018 bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
4020 break;
4021 default:
4022 break;
4025 df_simulate_fixup_sets (bb, live);
4028 /* Used by the next two functions to encode information about the
4029 memory references we found. */
4030 #define MEMREF_NORMAL 1
4031 #define MEMREF_VOLATILE 2
4033 /* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
4035 static int
4036 find_memory (rtx_insn *insn)
4038 int flags = 0;
4039 subrtx_iterator::array_type array;
4040 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
4042 const_rtx x = *iter;
4043 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
4044 flags |= MEMREF_VOLATILE;
4045 else if (MEM_P (x))
4047 if (MEM_VOLATILE_P (x))
4048 flags |= MEMREF_VOLATILE;
4049 else if (!MEM_READONLY_P (x))
4050 flags |= MEMREF_NORMAL;
4053 return flags;
4056 /* A subroutine of can_move_insns_across_p called through note_stores.
4057 DATA points to an integer in which we set either the bit for
4058 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
4059 of either kind. */
4061 static void
4062 find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4063 void *data ATTRIBUTE_UNUSED)
4065 int *pflags = (int *)data;
4066 if (GET_CODE (x) == SUBREG)
4067 x = XEXP (x, 0);
4068 /* Treat stores to SP as stores to memory, this will prevent problems
4069 when there are references to the stack frame. */
4070 if (x == stack_pointer_rtx)
4071 *pflags |= MEMREF_VOLATILE;
4072 if (!MEM_P (x))
4073 return;
4074 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4077 /* Scan BB backwards, using df_simulate functions to keep track of
4078 lifetimes, up to insn POINT. The result is stored in LIVE. */
4080 void
4081 simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4083 rtx_insn *insn;
4084 bitmap_copy (live, df_get_live_out (bb));
4085 df_simulate_initialize_backwards (bb, live);
4087 /* Scan and update life information until we reach the point we're
4088 interested in. */
4089 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4090 df_simulate_one_insn_backwards (bb, insn, live);
4093 /* Return true if it is safe to move a group of insns, described by
4094 the range FROM to TO, backwards across another group of insns,
4095 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4096 are no insns between ACROSS_TO and FROM, but they may be in
4097 different basic blocks; MERGE_BB is the block from which the
4098 insns will be moved. The caller must pass in a regset MERGE_LIVE
4099 which specifies the registers live after TO.
4101 This function may be called in one of two cases: either we try to
4102 move identical instructions from all successor blocks into their
4103 predecessor, or we try to move from only one successor block. If
4104 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4105 the second case. It should contain a set of registers live at the
4106 end of ACROSS_TO which must not be clobbered by moving the insns.
4107 In that case, we're also more careful about moving memory references
4108 and trapping insns.
4110 We return false if it is not safe to move the entire group, but it
4111 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4112 is set to point at the last moveable insn in such a case. */
4114 bool
4115 can_move_insns_across (rtx_insn *from, rtx_insn *to,
4116 rtx_insn *across_from, rtx_insn *across_to,
4117 basic_block merge_bb, regset merge_live,
4118 regset other_branch_live, rtx_insn **pmove_upto)
4120 rtx_insn *insn, *next, *max_to;
4121 bitmap merge_set, merge_use, local_merge_live;
4122 bitmap test_set, test_use;
4123 unsigned i, fail = 0;
4124 bitmap_iterator bi;
4125 int memrefs_in_across = 0;
4126 int mem_sets_in_across = 0;
4127 bool trapping_insns_in_across = false;
4129 if (pmove_upto != NULL)
4130 *pmove_upto = NULL;
4132 /* Find real bounds, ignoring debug insns. */
4133 while (!NONDEBUG_INSN_P (from) && from != to)
4134 from = NEXT_INSN (from);
4135 while (!NONDEBUG_INSN_P (to) && from != to)
4136 to = PREV_INSN (to);
4138 for (insn = across_to; ; insn = next)
4140 if (CALL_P (insn))
4142 if (RTL_CONST_OR_PURE_CALL_P (insn))
4143 /* Pure functions can read from memory. Const functions can
4144 read from arguments that the ABI has forced onto the stack.
4145 Neither sort of read can be volatile. */
4146 memrefs_in_across |= MEMREF_NORMAL;
4147 else
4149 memrefs_in_across |= MEMREF_VOLATILE;
4150 mem_sets_in_across |= MEMREF_VOLATILE;
4153 if (NONDEBUG_INSN_P (insn))
4155 if (volatile_insn_p (PATTERN (insn)))
4156 return false;
4157 memrefs_in_across |= find_memory (insn);
4158 note_stores (insn, find_memory_stores, &mem_sets_in_across);
4159 /* This is used just to find sets of the stack pointer. */
4160 memrefs_in_across |= mem_sets_in_across;
4161 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4163 next = PREV_INSN (insn);
4164 if (insn == across_from)
4165 break;
4168 /* Collect:
4169 MERGE_SET = set of registers set in MERGE_BB
4170 MERGE_USE = set of registers used in MERGE_BB and live at its top
4171 MERGE_LIVE = set of registers live at the point inside the MERGE
4172 range that we've reached during scanning
4173 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4174 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4175 and live before ACROSS_FROM. */
4177 merge_set = BITMAP_ALLOC (&reg_obstack);
4178 merge_use = BITMAP_ALLOC (&reg_obstack);
4179 local_merge_live = BITMAP_ALLOC (&reg_obstack);
4180 test_set = BITMAP_ALLOC (&reg_obstack);
4181 test_use = BITMAP_ALLOC (&reg_obstack);
4183 /* Compute the set of registers set and used in the ACROSS range. */
4184 if (other_branch_live != NULL)
4185 bitmap_copy (test_use, other_branch_live);
4186 df_simulate_initialize_backwards (merge_bb, test_use);
4187 for (insn = across_to; ; insn = next)
4189 if (NONDEBUG_INSN_P (insn))
4191 df_simulate_find_defs (insn, test_set);
4192 df_simulate_defs (insn, test_use);
4193 df_simulate_uses (insn, test_use);
4195 next = PREV_INSN (insn);
4196 if (insn == across_from)
4197 break;
4200 /* Compute an upper bound for the amount of insns moved, by finding
4201 the first insn in MERGE that sets a register in TEST_USE, or uses
4202 a register in TEST_SET. We also check for calls, trapping operations,
4203 and memory references. */
4204 max_to = NULL;
4205 for (insn = from; ; insn = next)
4207 if (CALL_P (insn))
4208 break;
4209 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4210 break;
4211 if (NONDEBUG_INSN_P (insn))
4213 if (may_trap_or_fault_p (PATTERN (insn))
4214 && (trapping_insns_in_across
4215 || other_branch_live != NULL
4216 || volatile_insn_p (PATTERN (insn))))
4217 break;
4219 /* We cannot move memory stores past each other, or move memory
4220 reads past stores, at least not without tracking them and
4221 calling true_dependence on every pair.
4223 If there is no other branch and no memory references or
4224 sets in the ACROSS range, we can move memory references
4225 freely, even volatile ones.
4227 Otherwise, the rules are as follows: volatile memory
4228 references and stores can't be moved at all, and any type
4229 of memory reference can't be moved if there are volatile
4230 accesses or stores in the ACROSS range. That leaves
4231 normal reads, which can be moved, as the trapping case is
4232 dealt with elsewhere. */
4233 if (other_branch_live != NULL || memrefs_in_across != 0)
4235 int mem_ref_flags = 0;
4236 int mem_set_flags = 0;
4237 note_stores (insn, find_memory_stores, &mem_set_flags);
4238 mem_ref_flags = find_memory (insn);
4239 /* Catch sets of the stack pointer. */
4240 mem_ref_flags |= mem_set_flags;
4242 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4243 break;
4244 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4245 break;
4246 if (mem_set_flags != 0
4247 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4248 break;
4250 df_simulate_find_uses (insn, merge_use);
4251 /* We're only interested in uses which use a value live at
4252 the top, not one previously set in this block. */
4253 bitmap_and_compl_into (merge_use, merge_set);
4254 df_simulate_find_defs (insn, merge_set);
4255 if (bitmap_intersect_p (merge_set, test_use)
4256 || bitmap_intersect_p (merge_use, test_set))
4257 break;
4258 max_to = insn;
4260 next = NEXT_INSN (insn);
4261 if (insn == to)
4262 break;
4264 if (max_to != to)
4265 fail = 1;
4267 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4268 goto out;
4270 /* Now, lower this upper bound by also taking into account that
4271 a range of insns moved across ACROSS must not leave a register
4272 live at the end that will be clobbered in ACROSS. We need to
4273 find a point where TEST_SET & LIVE == 0.
4275 Insns in the MERGE range that set registers which are also set
4276 in the ACROSS range may still be moved as long as we also move
4277 later insns which use the results of the set, and make the
4278 register dead again. This is verified by the condition stated
4279 above. We only need to test it for registers that are set in
4280 the moved region.
4282 MERGE_LIVE is provided by the caller and holds live registers after
4283 TO. */
4284 bitmap_copy (local_merge_live, merge_live);
4285 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4286 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4288 /* We're not interested in registers that aren't set in the moved
4289 region at all. */
4290 bitmap_and_into (local_merge_live, merge_set);
4291 for (;;)
4293 if (NONDEBUG_INSN_P (insn))
4295 if (!bitmap_intersect_p (test_set, local_merge_live))
4297 max_to = insn;
4298 break;
4301 df_simulate_one_insn_backwards (merge_bb, insn,
4302 local_merge_live);
4304 if (insn == from)
4306 fail = 1;
4307 goto out;
4309 insn = PREV_INSN (insn);
4312 if (max_to != to)
4313 fail = 1;
4315 if (pmove_upto)
4316 *pmove_upto = max_to;
4318 /* For small register class machines, don't lengthen lifetimes of
4319 hard registers before reload. */
4320 if (! reload_completed
4321 && targetm.small_register_classes_for_mode_p (VOIDmode))
4323 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4325 if (i < FIRST_PSEUDO_REGISTER
4326 && ! fixed_regs[i]
4327 && ! global_regs[i])
4329 fail = 1;
4330 break;
4335 out:
4336 BITMAP_FREE (merge_set);
4337 BITMAP_FREE (merge_use);
4338 BITMAP_FREE (local_merge_live);
4339 BITMAP_FREE (test_set);
4340 BITMAP_FREE (test_use);
4342 return !fail;
4346 /*----------------------------------------------------------------------------
4347 MULTIPLE DEFINITIONS
4349 Find the locations in the function reached by multiple definition sites
4350 for a live pseudo. In and out bitvectors are built for each basic
4351 block. They are restricted for efficiency to live registers.
4353 The gen and kill sets for the problem are obvious. Together they
4354 include all defined registers in a basic block; the gen set includes
4355 registers where a partial or conditional or may-clobber definition is
4356 last in the BB, while the kill set includes registers with a complete
4357 definition coming last. However, the computation of the dataflow
4358 itself is interesting.
4360 The idea behind it comes from SSA form's iterated dominance frontier
4361 criterion for inserting PHI functions. Just like in that case, we can use
4362 the dominance frontier to find places where multiple definitions meet;
4363 a register X defined in a basic block BB1 has multiple definitions in
4364 basic blocks in BB1's dominance frontier.
4366 So, the in-set of a basic block BB2 is not just the union of the
4367 out-sets of BB2's predecessors, but includes some more bits that come
4368 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4369 the previous paragraph). I called this set the init-set of BB2.
4371 (Note: I actually use the kill-set only to build the init-set.
4372 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4374 For example, if you have
4376 BB1 : r10 = 0
4377 r11 = 0
4378 if <...> goto BB2 else goto BB3;
4380 BB2 : r10 = 1
4381 r12 = 1
4382 goto BB3;
4384 BB3 :
4386 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4387 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4388 not need to iterate the dominance frontier, because we do not insert
4389 anything like PHI functions there! Instead, dataflow will take care of
4390 propagating the information to BB3's successors.
4391 ---------------------------------------------------------------------------*/
4393 /* Private data used to verify the solution for this problem. */
4394 struct df_md_problem_data
4396 /* An obstack for the bitmaps we need for this problem. */
4397 bitmap_obstack md_bitmaps;
4400 /* Scratch var used by transfer functions. This is used to do md analysis
4401 only for live registers. */
4402 static bitmap_head df_md_scratch;
4405 static void
4406 df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4407 void *vbb_info)
4409 class df_md_bb_info *bb_info = (class df_md_bb_info *) vbb_info;
4410 if (bb_info)
4412 bitmap_clear (&bb_info->kill);
4413 bitmap_clear (&bb_info->gen);
4414 bitmap_clear (&bb_info->init);
4415 bitmap_clear (&bb_info->in);
4416 bitmap_clear (&bb_info->out);
4421 /* Allocate or reset bitmaps for DF_MD. The solution bits are
4422 not touched unless the block is new. */
4424 static void
4425 df_md_alloc (bitmap all_blocks)
4427 unsigned int bb_index;
4428 bitmap_iterator bi;
4429 struct df_md_problem_data *problem_data;
4431 df_grow_bb_info (df_md);
4432 if (df_md->problem_data)
4433 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4434 else
4436 problem_data = XNEW (struct df_md_problem_data);
4437 df_md->problem_data = problem_data;
4438 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4440 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4442 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4444 class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4445 /* When bitmaps are already initialized, just clear them. */
4446 if (bb_info->init.obstack)
4448 bitmap_clear (&bb_info->init);
4449 bitmap_clear (&bb_info->gen);
4450 bitmap_clear (&bb_info->kill);
4451 bitmap_clear (&bb_info->in);
4452 bitmap_clear (&bb_info->out);
4454 else
4456 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4457 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4458 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4459 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4460 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4464 df_md->optional_p = true;
4467 /* Add the effect of the top artificial defs of BB to the multiple definitions
4468 bitmap LOCAL_MD. */
4470 void
4471 df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4473 int bb_index = bb->index;
4474 df_ref def;
4475 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4476 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4478 unsigned int dregno = DF_REF_REGNO (def);
4479 if (DF_REF_FLAGS (def)
4480 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4481 bitmap_set_bit (local_md, dregno);
4482 else
4483 bitmap_clear_bit (local_md, dregno);
4488 /* Add the effect of the defs of INSN to the reaching definitions bitmap
4489 LOCAL_MD. */
4491 void
4492 df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4493 bitmap local_md)
4495 df_ref def;
4497 FOR_EACH_INSN_DEF (def, insn)
4499 unsigned int dregno = DF_REF_REGNO (def);
4500 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4501 || (dregno >= FIRST_PSEUDO_REGISTER))
4503 if (DF_REF_FLAGS (def)
4504 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4505 bitmap_set_bit (local_md, DF_REF_ID (def));
4506 else
4507 bitmap_clear_bit (local_md, DF_REF_ID (def));
4512 static void
4513 df_md_bb_local_compute_process_def (class df_md_bb_info *bb_info,
4514 df_ref def,
4515 int top_flag)
4517 bitmap_clear (&seen_in_insn);
4519 for (; def; def = DF_REF_NEXT_LOC (def))
4521 unsigned int dregno = DF_REF_REGNO (def);
4522 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4523 || (dregno >= FIRST_PSEUDO_REGISTER))
4524 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4526 if (!bitmap_bit_p (&seen_in_insn, dregno))
4528 if (DF_REF_FLAGS (def)
4529 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4531 bitmap_set_bit (&bb_info->gen, dregno);
4532 bitmap_clear_bit (&bb_info->kill, dregno);
4534 else
4536 /* When we find a clobber and a regular def,
4537 make sure the regular def wins. */
4538 bitmap_set_bit (&seen_in_insn, dregno);
4539 bitmap_set_bit (&bb_info->kill, dregno);
4540 bitmap_clear_bit (&bb_info->gen, dregno);
4548 /* Compute local multiple def info for basic block BB. */
4550 static void
4551 df_md_bb_local_compute (unsigned int bb_index)
4553 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4554 class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4555 rtx_insn *insn;
4557 /* Artificials are only hard regs. */
4558 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4559 df_md_bb_local_compute_process_def (bb_info,
4560 df_get_artificial_defs (bb_index),
4561 DF_REF_AT_TOP);
4563 FOR_BB_INSNS (bb, insn)
4565 unsigned int uid = INSN_UID (insn);
4566 if (!INSN_P (insn))
4567 continue;
4569 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4572 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4573 df_md_bb_local_compute_process_def (bb_info,
4574 df_get_artificial_defs (bb_index),
4578 /* Compute local reaching def info for each basic block within BLOCKS. */
4580 static void
4581 df_md_local_compute (bitmap all_blocks)
4583 unsigned int bb_index, df_bb_index;
4584 bitmap_iterator bi1, bi2;
4585 basic_block bb;
4586 bitmap_head *frontiers;
4588 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4590 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4592 df_md_bb_local_compute (bb_index);
4595 bitmap_release (&seen_in_insn);
4597 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4598 FOR_ALL_BB_FN (bb, cfun)
4599 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4601 compute_dominance_frontiers (frontiers);
4603 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4604 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4606 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4607 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4609 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4610 if (bitmap_bit_p (all_blocks, df_bb_index))
4611 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4612 df_get_live_in (bb));
4616 FOR_ALL_BB_FN (bb, cfun)
4617 bitmap_clear (&frontiers[bb->index]);
4618 free (frontiers);
4622 /* Reset the global solution for recalculation. */
4624 static void
4625 df_md_reset (bitmap all_blocks)
4627 unsigned int bb_index;
4628 bitmap_iterator bi;
4630 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4632 class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4633 gcc_assert (bb_info);
4634 bitmap_clear (&bb_info->in);
4635 bitmap_clear (&bb_info->out);
4639 static bool
4640 df_md_transfer_function (int bb_index)
4642 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4643 class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4644 bitmap in = &bb_info->in;
4645 bitmap out = &bb_info->out;
4646 bitmap gen = &bb_info->gen;
4647 bitmap kill = &bb_info->kill;
4649 /* We need to use a scratch set here so that the value returned from this
4650 function invocation properly reflects whether the sets changed in a
4651 significant way; i.e. not just because the live set was anded in. */
4652 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4654 /* Multiple definitions of a register are not relevant if it is not
4655 live. Thus we trim the result to the places where it is live. */
4656 bitmap_and_into (in, df_get_live_in (bb));
4658 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4661 /* Initialize the solution bit vectors for problem. */
4663 static void
4664 df_md_init (bitmap all_blocks)
4666 unsigned int bb_index;
4667 bitmap_iterator bi;
4669 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4671 class df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4673 bitmap_copy (&bb_info->in, &bb_info->init);
4674 df_md_transfer_function (bb_index);
4678 static void
4679 df_md_confluence_0 (basic_block bb)
4681 class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4682 bitmap_copy (&bb_info->in, &bb_info->init);
4685 /* In of target gets or of out of source. */
4687 static bool
4688 df_md_confluence_n (edge e)
4690 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4691 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4693 if (e->flags & EDGE_FAKE)
4694 return false;
4696 if (e->flags & EDGE_EH)
4698 /* Conservatively treat partially-clobbered registers as surviving
4699 across the edge; they might or might not, depending on what mode
4700 they have. */
4701 bitmap_view<HARD_REG_SET> eh_kills (eh_edge_abi.full_reg_clobbers ());
4702 return bitmap_ior_and_compl_into (op1, op2, eh_kills);
4704 else
4705 return bitmap_ior_into (op1, op2);
4708 /* Free all storage associated with the problem. */
4710 static void
4711 df_md_free (void)
4713 struct df_md_problem_data *problem_data
4714 = (struct df_md_problem_data *) df_md->problem_data;
4716 bitmap_release (&df_md_scratch);
4717 bitmap_obstack_release (&problem_data->md_bitmaps);
4718 free (problem_data);
4719 df_md->problem_data = NULL;
4721 df_md->block_info_size = 0;
4722 free (df_md->block_info);
4723 df_md->block_info = NULL;
4724 free (df_md);
4728 /* Debugging info at top of bb. */
4730 static void
4731 df_md_top_dump (basic_block bb, FILE *file)
4733 class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4734 if (!bb_info)
4735 return;
4737 fprintf (file, ";; md in \t");
4738 df_print_regset (file, &bb_info->in);
4739 fprintf (file, ";; md init \t");
4740 df_print_regset (file, &bb_info->init);
4741 fprintf (file, ";; md gen \t");
4742 df_print_regset (file, &bb_info->gen);
4743 fprintf (file, ";; md kill \t");
4744 df_print_regset (file, &bb_info->kill);
4747 /* Debugging info at bottom of bb. */
4749 static void
4750 df_md_bottom_dump (basic_block bb, FILE *file)
4752 class df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4753 if (!bb_info)
4754 return;
4756 fprintf (file, ";; md out \t");
4757 df_print_regset (file, &bb_info->out);
4760 static const struct df_problem problem_MD =
4762 DF_MD, /* Problem id. */
4763 DF_FORWARD, /* Direction. */
4764 df_md_alloc, /* Allocate the problem specific data. */
4765 df_md_reset, /* Reset global information. */
4766 df_md_free_bb_info, /* Free basic block info. */
4767 df_md_local_compute, /* Local compute function. */
4768 df_md_init, /* Init the solution specific data. */
4769 df_worklist_dataflow, /* Worklist solver. */
4770 df_md_confluence_0, /* Confluence operator 0. */
4771 df_md_confluence_n, /* Confluence operator n. */
4772 df_md_transfer_function, /* Transfer function. */
4773 NULL, /* Finalize function. */
4774 df_md_free, /* Free all of the problem information. */
4775 df_md_free, /* Remove this problem from the stack of dataflow problems. */
4776 NULL, /* Debugging. */
4777 df_md_top_dump, /* Debugging start block. */
4778 df_md_bottom_dump, /* Debugging end block. */
4779 NULL, /* Debugging start insn. */
4780 NULL, /* Debugging end insn. */
4781 NULL, /* Incremental solution verify start. */
4782 NULL, /* Incremental solution verify end. */
4783 NULL, /* Dependent problem. */
4784 sizeof (class df_md_bb_info),/* Size of entry of block_info array. */
4785 TV_DF_MD, /* Timing variable. */
4786 false /* Reset blocks on dropping out of blocks_to_analyze. */
4789 /* Create a new MD instance and add it to the existing instance
4790 of DF. */
4792 void
4793 df_md_add_problem (void)
4795 df_add_problem (&problem_MD);