1/* Standard problems for dataflow support routines.
2 Copyright (C) 1999-2017 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).
7
8This file is part of GCC.
9
10GCC is free software; you can redistribute it and/or modify it under
11the terms of the GNU General Public License as published by the Free
12Software Foundation; either version 3, or (at your option) any later
13version.
14
15GCC is distributed in the hope that it will be useful, but WITHOUT ANY
16WARRANTY; without even the implied warranty of MERCHANTABILITY or
17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18for more details.
19
20You should have received a copy of the GNU General Public License
21along with GCC; see the file COPYING3. If not see
22<http://www.gnu.org/licenses/>. */
23
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
40/* Note that turning REG_DEAD_DEBUGGING on will cause
41 gcc.c-torture/unsorted/dump-noaddr.c to fail because it prints
42 addresses in the dumps. */
43#define REG_DEAD_DEBUGGING 0
44
45#define DF_SPARSE_THRESHOLD 32
46
47static bitmap_head seen_in_block;
48static bitmap_head seen_in_insn;
49
50/*----------------------------------------------------------------------------
51 Utility functions.
52----------------------------------------------------------------------------*/
53
54/* Generic versions to get the void* version of the block info. Only
55 used inside the problem instance vectors. */
56
57/* Dump a def-use or use-def chain for REF to FILE. */
58
59void
60df_chain_dump (struct df_link *link, FILE *file)
61{
62 fprintf (file, "{ ");
63 for (; link; link = link->next)
64 {
65 fprintf (file, "%c%d(bb %d insn %d) ",
66 DF_REF_REG_DEF_P (link->ref)
67 ? 'd'
68 : (DF_REF_FLAGS (link->ref) & DF_REF_IN_NOTE) ? 'e' : 'u',
69 DF_REF_ID (link->ref),
70 DF_REF_BBNO (link->ref),
71 DF_REF_IS_ARTIFICIAL (link->ref)
72 ? -1 : DF_REF_INSN_UID (link->ref));
73 }
74 fprintf (file, "}");
75}
76
77
78/* Print some basic block info as part of df_dump. */
79
80void
81df_print_bb_index (basic_block bb, FILE *file)
82{
83 edge e;
84 edge_iterator ei;
85
86 fprintf (file, "\n( ");
87 FOR_EACH_EDGE (e, ei, bb->preds)
88 {
89 basic_block pred = e->src;
90 fprintf (file, "%d%s ", pred->index, e->flags & EDGE_EH ? "(EH)" : "");
91 }
92 fprintf (file, ")->[%d]->( ", bb->index);
93 FOR_EACH_EDGE (e, ei, bb->succs)
94 {
95 basic_block succ = e->dest;
96 fprintf (file, "%d%s ", succ->index, e->flags & EDGE_EH ? "(EH)" : "");
97 }
98 fprintf (file, ")\n");
99}
100
101
102/*----------------------------------------------------------------------------
103 REACHING DEFINITIONS
104
105 Find the locations in the function where each definition site for a
106 pseudo reaches. In and out bitvectors are built for each basic
107 block. The id field in the ref is used to index into these sets.
108 See df.h for details.
109
110 If the DF_RD_PRUNE_DEAD_DEFS changeable flag is set, only DEFs reaching
111 existing uses are included in the global reaching DEFs set, or in other
112 words only DEFs that are still live. This is a kind of pruned version
113 of the traditional reaching definitions problem that is much less
114 complex to compute and produces enough information to compute UD-chains.
115 In this context, live must be interpreted in the DF_LR sense: Uses that
116 are upward exposed but maybe not initialized on all paths through the
117 CFG. For a USE that is not reached by a DEF on all paths, we still want
118 to make those DEFs that do reach the USE visible, and pruning based on
119 DF_LIVE would make that impossible.
120 ----------------------------------------------------------------------------*/
121
122/* This problem plays a large number of games for the sake of
123 efficiency.
124
125 1) The order of the bits in the bitvectors. After the scanning
126 phase, all of the defs are sorted. All of the defs for the reg 0
127 are first, followed by all defs for reg 1 and so on.
128
129 2) There are two kill sets, one if the number of defs is less or
130 equal to DF_SPARSE_THRESHOLD and another if the number of defs is
131 greater.
132
133 <= : Data is built directly in the kill set.
134
135 > : One level of indirection is used to keep from generating long
136 strings of 1 bits in the kill sets. Bitvectors that are indexed
137 by the regnum are used to represent that there is a killing def
138 for the register. The confluence and transfer functions use
139 these along with the bitmap_clear_range call to remove ranges of
140 bits without actually generating a knockout vector.
141
142 The kill and sparse_kill and the dense_invalidated_by_call and
143 sparse_invalidated_by_call both play this game. */
144
145/* Private data used to compute the solution for this problem. These
146 data structures are not accessible outside of this module. */
147struct df_rd_problem_data
148{
149 /* The set of defs to regs invalidated by call. */
150 bitmap_head sparse_invalidated_by_call;
151 /* The set of defs to regs invalidate by call for rd. */
152 bitmap_head dense_invalidated_by_call;
153 /* An obstack for the bitmaps we need for this problem. */
154 bitmap_obstack rd_bitmaps;
155};
156
157
158/* Free basic block info. */
159
160static void
161df_rd_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
162 void *vbb_info)
163{
164 struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
165 if (bb_info)
166 {
167 bitmap_clear (&bb_info->kill);
168 bitmap_clear (&bb_info->sparse_kill);
169 bitmap_clear (&bb_info->gen);
170 bitmap_clear (&bb_info->in);
171 bitmap_clear (&bb_info->out);
172 }
173}
174
175
176/* Allocate or reset bitmaps for DF_RD blocks. The solution bits are
177 not touched unless the block is new. */
178
179static void
180df_rd_alloc (bitmap all_blocks)
181{
182 unsigned int bb_index;
183 bitmap_iterator bi;
184 struct df_rd_problem_data *problem_data;
185
186 if (df_rd->problem_data)
187 {
188 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
189 bitmap_clear (&problem_data->sparse_invalidated_by_call);
190 bitmap_clear (&problem_data->dense_invalidated_by_call);
191 }
192 else
193 {
194 problem_data = XNEW (struct df_rd_problem_data);
195 df_rd->problem_data = problem_data;
196
197 bitmap_obstack_initialize (&problem_data->rd_bitmaps);
198 bitmap_initialize (&problem_data->sparse_invalidated_by_call,
199 &problem_data->rd_bitmaps);
200 bitmap_initialize (&problem_data->dense_invalidated_by_call,
201 &problem_data->rd_bitmaps);
202 }
203
204 df_grow_bb_info (df_rd);
205
206 /* Because of the clustering of all use sites for the same pseudo,
207 we have to process all of the blocks before doing the analysis. */
208
209 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
210 {
211 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
212
213 /* When bitmaps are already initialized, just clear them. */
214 if (bb_info->kill.obstack)
215 {
216 bitmap_clear (&bb_info->kill);
217 bitmap_clear (&bb_info->sparse_kill);
218 bitmap_clear (&bb_info->gen);
219 }
220 else
221 {
222 bitmap_initialize (&bb_info->kill, &problem_data->rd_bitmaps);
223 bitmap_initialize (&bb_info->sparse_kill, &problem_data->rd_bitmaps);
224 bitmap_initialize (&bb_info->gen, &problem_data->rd_bitmaps);
225 bitmap_initialize (&bb_info->in, &problem_data->rd_bitmaps);
226 bitmap_initialize (&bb_info->out, &problem_data->rd_bitmaps);
227 }
228 }
229 df_rd->optional_p = true;
230}
231
232
233/* Add the effect of the top artificial defs of BB to the reaching definitions
234 bitmap LOCAL_RD. */
235
236void
237df_rd_simulate_artificial_defs_at_top (basic_block bb, bitmap local_rd)
238{
239 int bb_index = bb->index;
240 df_ref def;
241 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
242 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
243 {
244 unsigned int dregno = DF_REF_REGNO (def);
245 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
246 bitmap_clear_range (local_rd,
247 DF_DEFS_BEGIN (dregno),
248 DF_DEFS_COUNT (dregno));
249 bitmap_set_bit (local_rd, DF_REF_ID (def));
250 }
251}
252
253/* Add the effect of the defs of INSN to the reaching definitions bitmap
254 LOCAL_RD. */
255
256void
257df_rd_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
258 bitmap local_rd)
259{
260 df_ref def;
261
262 FOR_EACH_INSN_DEF (def, insn)
263 {
264 unsigned int dregno = DF_REF_REGNO (def);
265 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
266 || (dregno >= FIRST_PSEUDO_REGISTER))
267 {
268 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
269 bitmap_clear_range (local_rd,
270 DF_DEFS_BEGIN (dregno),
271 DF_DEFS_COUNT (dregno));
272 if (!(DF_REF_FLAGS (def)
273 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
274 bitmap_set_bit (local_rd, DF_REF_ID (def));
275 }
276 }
277}
278
279/* Process a list of DEFs for df_rd_bb_local_compute. This is a bit
280 more complicated than just simulating, because we must produce the
281 gen and kill sets and hence deal with the two possible representations
282 of kill sets. */
283
284static void
285df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
286 df_ref def,
287 int top_flag)
288{
289 for (; def; def = DF_REF_NEXT_LOC (def))
290 {
291 if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
292 {
293 unsigned int regno = DF_REF_REGNO (def);
294 unsigned int begin = DF_DEFS_BEGIN (regno);
295 unsigned int n_defs = DF_DEFS_COUNT (regno);
296
297 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
298 || (regno >= FIRST_PSEUDO_REGISTER))
299 {
300 /* Only the last def(s) for a regno in the block has any
301 effect. */
302 if (!bitmap_bit_p (&seen_in_block, regno))
303 {
304 /* The first def for regno in insn gets to knock out the
305 defs from other instructions. */
306 if ((!bitmap_bit_p (&seen_in_insn, regno))
307 /* If the def is to only part of the reg, it does
308 not kill the other defs that reach here. */
309 && (!(DF_REF_FLAGS (def) &
310 (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
311 {
312 if (n_defs > DF_SPARSE_THRESHOLD)
313 {
314 bitmap_set_bit (&bb_info->sparse_kill, regno);
315 bitmap_clear_range (&bb_info->gen, begin, n_defs);
316 }
317 else
318 {
319 bitmap_set_range (&bb_info->kill, begin, n_defs);
320 bitmap_clear_range (&bb_info->gen, begin, n_defs);
321 }
322 }
323
324 bitmap_set_bit (&seen_in_insn, regno);
325 /* All defs for regno in the instruction may be put into
326 the gen set. */
327 if (!(DF_REF_FLAGS (def)
328 & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
329 bitmap_set_bit (&bb_info->gen, DF_REF_ID (def));
330 }
331 }
332 }
333 }
334}
335
336/* Compute local reaching def info for basic block BB. */
337
338static void
339df_rd_bb_local_compute (unsigned int bb_index)
340{
341 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
342 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
343 rtx_insn *insn;
344
345 bitmap_clear (&seen_in_block);
346 bitmap_clear (&seen_in_insn);
347
348 /* Artificials are only hard regs. */
349 if (!(df->changeable_flags & DF_NO_HARD_REGS))
350 df_rd_bb_local_compute_process_def (bb_info,
351 df_get_artificial_defs (bb_index),
352 0);
353
354 FOR_BB_INSNS_REVERSE (bb, insn)
355 {
356 unsigned int uid = INSN_UID (insn);
357
358 if (!INSN_P (insn))
359 continue;
360
361 df_rd_bb_local_compute_process_def (bb_info,
362 DF_INSN_UID_DEFS (uid), 0);
363
364 /* This complex dance with the two bitmaps is required because
365 instructions can assign twice to the same pseudo. This
366 generally happens with calls that will have one def for the
367 result and another def for the clobber. If only one vector
368 is used and the clobber goes first, the result will be
369 lost. */
370 bitmap_ior_into (&seen_in_block, &seen_in_insn);
371 bitmap_clear (&seen_in_insn);
372 }
373
374 /* Process the artificial defs at the top of the block last since we
375 are going backwards through the block and these are logically at
376 the start. */
377 if (!(df->changeable_flags & DF_NO_HARD_REGS))
378 df_rd_bb_local_compute_process_def (bb_info,
379 df_get_artificial_defs (bb_index),
380 DF_REF_AT_TOP);
381}
382
383
384/* Compute local reaching def info for each basic block within BLOCKS. */
385
386static void
387df_rd_local_compute (bitmap all_blocks)
388{
389 unsigned int bb_index;
390 bitmap_iterator bi;
391 unsigned int regno;
392 struct df_rd_problem_data *problem_data
393 = (struct df_rd_problem_data *) df_rd->problem_data;
394 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
395 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
396
397 bitmap_initialize (&seen_in_block, &df_bitmap_obstack);
398 bitmap_initialize (&seen_in_insn, &df_bitmap_obstack);
399
400 df_maybe_reorganize_def_refs (DF_REF_ORDER_BY_REG);
401
402 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
403 {
404 df_rd_bb_local_compute (bb_index);
405 }
406
407 /* Set up the knockout bit vectors to be applied across EH_EDGES. */
408 EXECUTE_IF_SET_IN_BITMAP (regs_invalidated_by_call_regset, 0, regno, bi)
409 {
410 if (! HARD_REGISTER_NUM_P (regno)
411 || !(df->changeable_flags & DF_NO_HARD_REGS))
412 {
413 if (DF_DEFS_COUNT (regno) > DF_SPARSE_THRESHOLD)
414 bitmap_set_bit (sparse_invalidated, regno);
415 else
416 bitmap_set_range (dense_invalidated,
417 DF_DEFS_BEGIN (regno),
418 DF_DEFS_COUNT (regno));
419 }
420 }
421
422 bitmap_clear (&seen_in_block);
423 bitmap_clear (&seen_in_insn);
424}
425
426
427/* Initialize the solution bit vectors for problem. */
428
429static void
430df_rd_init_solution (bitmap all_blocks)
431{
432 unsigned int bb_index;
433 bitmap_iterator bi;
434
435 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
436 {
437 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
438
439 bitmap_copy (&bb_info->out, &bb_info->gen);
440 bitmap_clear (&bb_info->in);
441 }
442}
443
444/* In of target gets or of out of source. */
445
446static bool
447df_rd_confluence_n (edge e)
448{
449 bitmap op1 = &df_rd_get_bb_info (e->dest->index)->in;
450 bitmap op2 = &df_rd_get_bb_info (e->src->index)->out;
451 bool changed = false;
452
453 if (e->flags & EDGE_FAKE)
454 return false;
455
456 if (e->flags & EDGE_EH)
457 {
458 struct df_rd_problem_data *problem_data
459 = (struct df_rd_problem_data *) df_rd->problem_data;
460 bitmap sparse_invalidated = &problem_data->sparse_invalidated_by_call;
461 bitmap dense_invalidated = &problem_data->dense_invalidated_by_call;
462 bitmap_iterator bi;
463 unsigned int regno;
464
465 auto_bitmap tmp (&df_bitmap_obstack);
466 bitmap_and_compl (tmp, op2, dense_invalidated);
467
468 EXECUTE_IF_SET_IN_BITMAP (sparse_invalidated, 0, regno, bi)
469 {
470 bitmap_clear_range (tmp,
471 DF_DEFS_BEGIN (regno),
472 DF_DEFS_COUNT (regno));
473 }
474 changed |= bitmap_ior_into (op1, tmp);
475 return changed;
476 }
477 else
478 return bitmap_ior_into (op1, op2);
479}
480
481
482/* Transfer function. */
483
484static bool
485df_rd_transfer_function (int bb_index)
486{
487 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
488 unsigned int regno;
489 bitmap_iterator bi;
490 bitmap in = &bb_info->in;
491 bitmap out = &bb_info->out;
492 bitmap gen = &bb_info->gen;
493 bitmap kill = &bb_info->kill;
494 bitmap sparse_kill = &bb_info->sparse_kill;
495 bool changed = false;
496
497 if (bitmap_empty_p (sparse_kill))
498 changed = bitmap_ior_and_compl (out, gen, in, kill);
499 else
500 {
501 struct df_rd_problem_data *problem_data;
502 bitmap_head tmp;
503
504 /* Note that TMP is _not_ a temporary bitmap if we end up replacing
505 OUT with TMP. Therefore, allocate TMP in the RD bitmaps obstack. */
506 problem_data = (struct df_rd_problem_data *) df_rd->problem_data;
507 bitmap_initialize (&tmp, &problem_data->rd_bitmaps);
508
509 bitmap_and_compl (&tmp, in, kill);
510 EXECUTE_IF_SET_IN_BITMAP (sparse_kill, 0, regno, bi)
511 {
512 bitmap_clear_range (&tmp,
513 DF_DEFS_BEGIN (regno),
514 DF_DEFS_COUNT (regno));
515 }
516 bitmap_ior_into (&tmp, gen);
517 changed = !bitmap_equal_p (&tmp, out);
518 if (changed)
519 bitmap_move (out, &tmp);
520 else
521 bitmap_clear (&tmp);
522 }
523
524 if (df->changeable_flags & DF_RD_PRUNE_DEAD_DEFS)
525 {
526 /* Create a mask of DEFs for all registers live at the end of this
527 basic block, and mask out DEFs of registers that are not live.
528 Computing the mask looks costly, but the benefit of the pruning
529 outweighs the cost. */
530 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
531 bitmap regs_live_out = &df_lr_get_bb_info (bb_index)->out;
532 bitmap live_defs = BITMAP_ALLOC (&df_bitmap_obstack);
533 unsigned int regno;
534 bitmap_iterator bi;
535
536 EXECUTE_IF_SET_IN_BITMAP (regs_live_out, 0, regno, bi)
537 bitmap_set_range (live_defs,
538 DF_DEFS_BEGIN (regno),
539 DF_DEFS_COUNT (regno));
540 changed |= bitmap_and_into (&bb_info->out, live_defs);
541 BITMAP_FREE (live_defs);
542 }
543
544 return changed;
545}
546
547/* Free all storage associated with the problem. */
548
549static void
550df_rd_free (void)
551{
552 struct df_rd_problem_data *problem_data
553 = (struct df_rd_problem_data *) df_rd->problem_data;
554
555 if (problem_data)
556 {
557 bitmap_obstack_release (&problem_data->rd_bitmaps);
558
559 df_rd->block_info_size = 0;
560 free (df_rd->block_info);
561 df_rd->block_info = NULL;
562 free (df_rd->problem_data);
563 }
564 free (df_rd);
565}
566
567
568/* Debugging info. */
569
570static void
571df_rd_start_dump (FILE *file)
572{
573 struct df_rd_problem_data *problem_data
574 = (struct df_rd_problem_data *) df_rd->problem_data;
575 unsigned int m = DF_REG_SIZE (df);
576 unsigned int regno;
577
578 if (!df_rd->block_info)
579 return;
580
581 fprintf (file, ";; Reaching defs:\n");
582
583 fprintf (file, ";; sparse invalidated \t");
584 dump_bitmap (file, &problem_data->sparse_invalidated_by_call);
585 fprintf (file, ";; dense invalidated \t");
586 dump_bitmap (file, &problem_data->dense_invalidated_by_call);
587
588 fprintf (file, ";; reg->defs[] map:\t");
589 for (regno = 0; regno < m; regno++)
590 if (DF_DEFS_COUNT (regno))
591 fprintf (file, "%d[%d,%d] ", regno,
592 DF_DEFS_BEGIN (regno),
593 DF_DEFS_BEGIN (regno) + DF_DEFS_COUNT (regno) - 1);
594 fprintf (file, "\n");
595}
596
597
598static void
599df_rd_dump_defs_set (bitmap defs_set, const char *prefix, FILE *file)
600{
601 bitmap_head tmp;
602 unsigned int regno;
603 unsigned int m = DF_REG_SIZE (df);
604 bool first_reg = true;
605
606 fprintf (file, "%s\t(%d) ", prefix, (int) bitmap_count_bits (defs_set));
607
608 bitmap_initialize (&tmp, &df_bitmap_obstack);
609 for (regno = 0; regno < m; regno++)
610 {
611 if (HARD_REGISTER_NUM_P (regno)
612 && (df->changeable_flags & DF_NO_HARD_REGS))
613 continue;
614 bitmap_set_range (&tmp, DF_DEFS_BEGIN (regno), DF_DEFS_COUNT (regno));
615 bitmap_and_into (&tmp, defs_set);
616 if (! bitmap_empty_p (&tmp))
617 {
618 bitmap_iterator bi;
619 unsigned int ix;
620 bool first_def = true;
621
622 if (! first_reg)
623 fprintf (file, ",");
624 first_reg = false;
625
626 fprintf (file, "%u[", regno);
627 EXECUTE_IF_SET_IN_BITMAP (&tmp, 0, ix, bi)
628 {
629 fprintf (file, "%s%u", first_def ? "" : ",", ix);
630 first_def = false;
631 }
632 fprintf (file, "]");
633 }
634 bitmap_clear (&tmp);
635 }
636
637 fprintf (file, "\n");
638 bitmap_clear (&tmp);
639}
640
641/* Debugging info at top of bb. */
642
643static void
644df_rd_top_dump (basic_block bb, FILE *file)
645{
646 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
647 if (!bb_info)
648 return;
649
650 df_rd_dump_defs_set (&bb_info->in, ";; rd in ", file);
651 df_rd_dump_defs_set (&bb_info->gen, ";; rd gen ", file);
652 df_rd_dump_defs_set (&bb_info->kill, ";; rd kill", file);
653}
654
655
656/* Debugging info at bottom of bb. */
657
658static void
659df_rd_bottom_dump (basic_block bb, FILE *file)
660{
661 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb->index);
662 if (!bb_info)
663 return;
664
665 df_rd_dump_defs_set (&bb_info->out, ";; rd out ", file);
666}
667
668/* All of the information associated with every instance of the problem. */
669
670static const struct df_problem problem_RD =
671{
672 DF_RD, /* Problem id. */
673 DF_FORWARD, /* Direction. */
674 df_rd_alloc, /* Allocate the problem specific data. */
675 NULL, /* Reset global information. */
676 df_rd_free_bb_info, /* Free basic block info. */
677 df_rd_local_compute, /* Local compute function. */
678 df_rd_init_solution, /* Init the solution specific data. */
679 df_worklist_dataflow, /* Worklist solver. */
680 NULL, /* Confluence operator 0. */
681 df_rd_confluence_n, /* Confluence operator n. */
682 df_rd_transfer_function, /* Transfer function. */
683 NULL, /* Finalize function. */
684 df_rd_free, /* Free all of the problem information. */
685 df_rd_free, /* Remove this problem from the stack of dataflow problems. */
686 df_rd_start_dump, /* Debugging. */
687 df_rd_top_dump, /* Debugging start block. */
688 df_rd_bottom_dump, /* Debugging end block. */
689 NULL, /* Debugging start insn. */
690 NULL, /* Debugging end insn. */
691 NULL, /* Incremental solution verify start. */
692 NULL, /* Incremental solution verify end. */
693 NULL, /* Dependent problem. */
694 sizeof (struct df_rd_bb_info),/* Size of entry of block_info array. */
695 TV_DF_RD, /* Timing variable. */
696 true /* Reset blocks on dropping out of blocks_to_analyze. */
697};
698
699
700
701/* Create a new RD instance and add it to the existing instance
702 of DF. */
703
704void
705df_rd_add_problem (void)
706{
707 df_add_problem (&problem_RD);
708}
709
710
711
712/*----------------------------------------------------------------------------
713 LIVE REGISTERS
714
715 Find the locations in the function where any use of a pseudo can
716 reach in the backwards direction. In and out bitvectors are built
717 for each basic block. The regno is used to index into these sets.
718 See df.h for details.
719 ----------------------------------------------------------------------------*/
720
721/* Private data used to verify the solution for this problem. */
722struct df_lr_problem_data
723{
724 bitmap_head *in;
725 bitmap_head *out;
726 /* An obstack for the bitmaps we need for this problem. */
727 bitmap_obstack lr_bitmaps;
728};
729
730/* Free basic block info. */
731
732static void
733df_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
734 void *vbb_info)
735{
736 struct df_lr_bb_info *bb_info = (struct df_lr_bb_info *) vbb_info;
737 if (bb_info)
738 {
739 bitmap_clear (&bb_info->use);
740 bitmap_clear (&bb_info->def);
741 bitmap_clear (&bb_info->in);
742 bitmap_clear (&bb_info->out);
743 }
744}
745
746
747/* Allocate or reset bitmaps for DF_LR blocks. The solution bits are
748 not touched unless the block is new. */
749
750static void
751df_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
752{
753 unsigned int bb_index;
754 bitmap_iterator bi;
755 struct df_lr_problem_data *problem_data;
756
757 df_grow_bb_info (df_lr);
758 if (df_lr->problem_data)
759 problem_data = (struct df_lr_problem_data *) df_lr->problem_data;
760 else
761 {
762 problem_data = XNEW (struct df_lr_problem_data);
763 df_lr->problem_data = problem_data;
764
765 problem_data->out = NULL;
766 problem_data->in = NULL;
767 bitmap_obstack_initialize (&problem_data->lr_bitmaps);
768 }
769
770 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
771 {
772 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
773
774 /* When bitmaps are already initialized, just clear them. */
775 if (bb_info->use.obstack)
776 {
777 bitmap_clear (&bb_info->def);
778 bitmap_clear (&bb_info->use);
779 }
780 else
781 {
782 bitmap_initialize (&bb_info->use, &problem_data->lr_bitmaps);
783 bitmap_initialize (&bb_info->def, &problem_data->lr_bitmaps);
784 bitmap_initialize (&bb_info->in, &problem_data->lr_bitmaps);
785 bitmap_initialize (&bb_info->out, &problem_data->lr_bitmaps);
786 }
787 }
788
789 df_lr->optional_p = false;
790}
791
792
793/* Reset the global solution for recalculation. */
794
795static void
796df_lr_reset (bitmap all_blocks)
797{
798 unsigned int bb_index;
799 bitmap_iterator bi;
800
801 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
802 {
803 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
804 gcc_assert (bb_info);
805 bitmap_clear (&bb_info->in);
806 bitmap_clear (&bb_info->out);
807 }
808}
809
810
811/* Compute local live register info for basic block BB. */
812
813static void
814df_lr_bb_local_compute (unsigned int bb_index)
815{
816 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
817 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
818 rtx_insn *insn;
819 df_ref def, use;
820
821 /* Process the registers set in an exception handler. */
822 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
823 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
824 {
825 unsigned int dregno = DF_REF_REGNO (def);
826 bitmap_set_bit (&bb_info->def, dregno);
827 bitmap_clear_bit (&bb_info->use, dregno);
828 }
829
830 /* Process the hardware registers that are always live. */
831 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
832 /* Add use to set of uses in this BB. */
833 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
834 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
835
836 FOR_BB_INSNS_REVERSE (bb, insn)
837 {
838 if (!NONDEBUG_INSN_P (insn))
839 continue;
840
841 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
842 FOR_EACH_INSN_INFO_DEF (def, insn_info)
843 /* If the def is to only part of the reg, it does
844 not kill the other defs that reach here. */
845 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
846 {
847 unsigned int dregno = DF_REF_REGNO (def);
848 bitmap_set_bit (&bb_info->def, dregno);
849 bitmap_clear_bit (&bb_info->use, dregno);
850 }
851
852 FOR_EACH_INSN_INFO_USE (use, insn_info)
853 /* Add use to set of uses in this BB. */
854 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
855 }
856
857 /* Process the registers set in an exception handler or the hard
858 frame pointer if this block is the target of a non local
859 goto. */
860 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
861 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
862 {
863 unsigned int dregno = DF_REF_REGNO (def);
864 bitmap_set_bit (&bb_info->def, dregno);
865 bitmap_clear_bit (&bb_info->use, dregno);
866 }
867
868#ifdef EH_USES
869 /* Process the uses that are live into an exception handler. */
870 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
871 /* Add use to set of uses in this BB. */
872 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
873 bitmap_set_bit (&bb_info->use, DF_REF_REGNO (use));
874#endif
875
876 /* If the df_live problem is not defined, such as at -O0 and -O1, we
877 still need to keep the luids up to date. This is normally done
878 in the df_live problem since this problem has a forwards
879 scan. */
880 if (!df_live)
881 df_recompute_luids (bb);
882}
883
884
885/* Compute local live register info for each basic block within BLOCKS. */
886
887static void
888df_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
889{
890 unsigned int bb_index, i;
891 bitmap_iterator bi;
892
893 bitmap_clear (&df->hardware_regs_used);
894
895 /* The all-important stack pointer must always be live. */
896 bitmap_set_bit (&df->hardware_regs_used, STACK_POINTER_REGNUM);
897
898 /* Global regs are always live, too. */
899 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
900 if (global_regs[i])
901 bitmap_set_bit (&df->hardware_regs_used, i);
902
903 /* Before reload, there are a few registers that must be forced
904 live everywhere -- which might not already be the case for
905 blocks within infinite loops. */
906 if (!reload_completed)
907 {
908 unsigned int pic_offset_table_regnum = PIC_OFFSET_TABLE_REGNUM;
909 /* Any reference to any pseudo before reload is a potential
910 reference of the frame pointer. */
911 bitmap_set_bit (&df->hardware_regs_used, FRAME_POINTER_REGNUM);
912
913 /* Pseudos with argument area equivalences may require
914 reloading via the argument pointer. */
915 if (FRAME_POINTER_REGNUM != ARG_POINTER_REGNUM
916 && fixed_regs[ARG_POINTER_REGNUM])
917 bitmap_set_bit (&df->hardware_regs_used, ARG_POINTER_REGNUM);
918
919 /* Any constant, or pseudo with constant equivalences, may
920 require reloading from memory using the pic register. */
921 if (pic_offset_table_regnum != INVALID_REGNUM
922 && fixed_regs[pic_offset_table_regnum])
923 bitmap_set_bit (&df->hardware_regs_used, pic_offset_table_regnum);
924 }
925
926 EXECUTE_IF_SET_IN_BITMAP (df_lr->out_of_date_transfer_functions, 0, bb_index, bi)
927 {
928 if (bb_index == EXIT_BLOCK)
929 {
930 /* The exit block is special for this problem and its bits are
931 computed from thin air. */
932 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (EXIT_BLOCK);
933 bitmap_copy (&bb_info->use, df->exit_block_uses);
934 }
935 else
936 df_lr_bb_local_compute (bb_index);
937 }
938
939 bitmap_clear (df_lr->out_of_date_transfer_functions);
940}
941
942
943/* Initialize the solution vectors. */
944
945static void
946df_lr_init (bitmap all_blocks)
947{
948 unsigned int bb_index;
949 bitmap_iterator bi;
950
951 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
952 {
953 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
954 bitmap_copy (&bb_info->in, &bb_info->use);
955 bitmap_clear (&bb_info->out);
956 }
957}
958
959
960/* Confluence function that processes infinite loops. This might be a
961 noreturn function that throws. And even if it isn't, getting the
962 unwind info right helps debugging. */
963static void
964df_lr_confluence_0 (basic_block bb)
965{
966 bitmap op1 = &df_lr_get_bb_info (bb->index)->out;
967 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
968 bitmap_copy (op1, &df->hardware_regs_used);
969}
970
971
972/* Confluence function that ignores fake edges. */
973
974static bool
975df_lr_confluence_n (edge e)
976{
977 bitmap op1 = &df_lr_get_bb_info (e->src->index)->out;
978 bitmap op2 = &df_lr_get_bb_info (e->dest->index)->in;
979 bool changed = false;
980
981 /* Call-clobbered registers die across exception and call edges. */
982 /* ??? Abnormal call edges ignored for the moment, as this gets
983 confused by sibling call edges, which crashes reg-stack. */
984 if (e->flags & EDGE_EH)
985 changed = bitmap_ior_and_compl_into (op1, op2, regs_invalidated_by_call_regset);
986 else
987 changed = bitmap_ior_into (op1, op2);
988
989 changed |= bitmap_ior_into (op1, &df->hardware_regs_used);
990 return changed;
991}
992
993
994/* Transfer function. */
995
996static bool
997df_lr_transfer_function (int bb_index)
998{
999 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
1000 bitmap in = &bb_info->in;
1001 bitmap out = &bb_info->out;
1002 bitmap use = &bb_info->use;
1003 bitmap def = &bb_info->def;
1004
1005 return bitmap_ior_and_compl (in, use, out, def);
1006}
1007
1008
1009/* Run the fast dce as a side effect of building LR. */
1010
1011static void
1012df_lr_finalize (bitmap all_blocks)
1013{
1014 df_lr->solutions_dirty = false;
1015 if (df->changeable_flags & DF_LR_RUN_DCE)
1016 {
1017 run_fast_df_dce ();
1018
1019 /* If dce deletes some instructions, we need to recompute the lr
1020 solution before proceeding further. The problem is that fast
1021 dce is a pessimestic dataflow algorithm. In the case where
1022 it deletes a statement S inside of a loop, the uses inside of
1023 S may not be deleted from the dataflow solution because they
1024 were carried around the loop. While it is conservatively
1025 correct to leave these extra bits, the standards of df
1026 require that we maintain the best possible (least fixed
1027 point) solution. The only way to do that is to redo the
1028 iteration from the beginning. See PR35805 for an
1029 example. */
1030 if (df_lr->solutions_dirty)
1031 {
1032 df_clear_flags (DF_LR_RUN_DCE);
1033 df_lr_alloc (all_blocks);
1034 df_lr_local_compute (all_blocks);
1035 df_worklist_dataflow (df_lr, all_blocks, df->postorder, df->n_blocks);
1036 df_lr_finalize (all_blocks);
1037 df_set_flags (DF_LR_RUN_DCE);
1038 }
1039 }
1040}
1041
1042
1043/* Free all storage associated with the problem. */
1044
1045static void
1046df_lr_free (void)
1047{
1048 struct df_lr_problem_data *problem_data
1049 = (struct df_lr_problem_data *) df_lr->problem_data;
1050 if (df_lr->block_info)
1051 {
1052
1053 df_lr->block_info_size = 0;
1054 free (df_lr->block_info);
1055 df_lr->block_info = NULL;
1056 bitmap_obstack_release (&problem_data->lr_bitmaps);
1057 free (df_lr->problem_data);
1058 df_lr->problem_data = NULL;
1059 }
1060
1061 BITMAP_FREE (df_lr->out_of_date_transfer_functions);
1062 free (df_lr);
1063}
1064
1065
1066/* Debugging info at top of bb. */
1067
1068static void
1069df_lr_top_dump (basic_block bb, FILE *file)
1070{
1071 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1072 struct df_lr_problem_data *problem_data;
1073 if (!bb_info)
1074 return;
1075
1076 fprintf (file, ";; lr in \t");
1077 df_print_regset (file, &bb_info->in);
1078 if (df_lr->problem_data)
1079 {
1080 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1081 if (problem_data->in)
1082 {
1083 fprintf (file, ";; old in \t");
1084 df_print_regset (file, &problem_data->in[bb->index]);
1085 }
1086 }
1087 fprintf (file, ";; lr use \t");
1088 df_print_regset (file, &bb_info->use);
1089 fprintf (file, ";; lr def \t");
1090 df_print_regset (file, &bb_info->def);
1091}
1092
1093
1094/* Debugging info at bottom of bb. */
1095
1096static void
1097df_lr_bottom_dump (basic_block bb, FILE *file)
1098{
1099 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1100 struct df_lr_problem_data *problem_data;
1101 if (!bb_info)
1102 return;
1103
1104 fprintf (file, ";; lr out \t");
1105 df_print_regset (file, &bb_info->out);
1106 if (df_lr->problem_data)
1107 {
1108 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1109 if (problem_data->out)
1110 {
1111 fprintf (file, ";; old out \t");
1112 df_print_regset (file, &problem_data->out[bb->index]);
1113 }
1114 }
1115}
1116
1117
1118/* Build the datastructure to verify that the solution to the dataflow
1119 equations is not dirty. */
1120
1121static void
1122df_lr_verify_solution_start (void)
1123{
1124 basic_block bb;
1125 struct df_lr_problem_data *problem_data;
1126 if (df_lr->solutions_dirty)
1127 return;
1128
1129 /* Set it true so that the solution is recomputed. */
1130 df_lr->solutions_dirty = true;
1131
1132 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1133 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1134 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1135
1136 FOR_ALL_BB_FN (bb, cfun)
1137 {
1138 bitmap_initialize (&problem_data->in[bb->index], &problem_data->lr_bitmaps);
1139 bitmap_initialize (&problem_data->out[bb->index], &problem_data->lr_bitmaps);
1140 bitmap_copy (&problem_data->in[bb->index], DF_LR_IN (bb));
1141 bitmap_copy (&problem_data->out[bb->index], DF_LR_OUT (bb));
1142 }
1143}
1144
1145
1146/* Compare the saved datastructure and the new solution to the dataflow
1147 equations. */
1148
1149static void
1150df_lr_verify_solution_end (void)
1151{
1152 struct df_lr_problem_data *problem_data;
1153 basic_block bb;
1154
1155 problem_data = (struct df_lr_problem_data *)df_lr->problem_data;
1156
1157 if (!problem_data->out)
1158 return;
1159
1160 if (df_lr->solutions_dirty)
1161 /* Do not check if the solution is still dirty. See the comment
1162 in df_lr_finalize for details. */
1163 df_lr->solutions_dirty = false;
1164 else
1165 FOR_ALL_BB_FN (bb, cfun)
1166 {
1167 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LR_IN (bb)))
1168 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LR_OUT (bb))))
1169 {
1170 /*df_dump (stderr);*/
1171 gcc_unreachable ();
1172 }
1173 }
1174
1175 /* Cannot delete them immediately because you may want to dump them
1176 if the comparison fails. */
1177 FOR_ALL_BB_FN (bb, cfun)
1178 {
1179 bitmap_clear (&problem_data->in[bb->index]);
1180 bitmap_clear (&problem_data->out[bb->index]);
1181 }
1182
1183 free (problem_data->in);
1184 free (problem_data->out);
1185 problem_data->in = NULL;
1186 problem_data->out = NULL;
1187}
1188
1189
1190/* All of the information associated with every instance of the problem. */
1191
1192static const struct df_problem problem_LR =
1193{
1194 DF_LR, /* Problem id. */
1195 DF_BACKWARD, /* Direction. */
1196 df_lr_alloc, /* Allocate the problem specific data. */
1197 df_lr_reset, /* Reset global information. */
1198 df_lr_free_bb_info, /* Free basic block info. */
1199 df_lr_local_compute, /* Local compute function. */
1200 df_lr_init, /* Init the solution specific data. */
1201 df_worklist_dataflow, /* Worklist solver. */
1202 df_lr_confluence_0, /* Confluence operator 0. */
1203 df_lr_confluence_n, /* Confluence operator n. */
1204 df_lr_transfer_function, /* Transfer function. */
1205 df_lr_finalize, /* Finalize function. */
1206 df_lr_free, /* Free all of the problem information. */
1207 NULL, /* Remove this problem from the stack of dataflow problems. */
1208 NULL, /* Debugging. */
1209 df_lr_top_dump, /* Debugging start block. */
1210 df_lr_bottom_dump, /* Debugging end block. */
1211 NULL, /* Debugging start insn. */
1212 NULL, /* Debugging end insn. */
1213 df_lr_verify_solution_start,/* Incremental solution verify start. */
1214 df_lr_verify_solution_end, /* Incremental solution verify end. */
1215 NULL, /* Dependent problem. */
1216 sizeof (struct df_lr_bb_info),/* Size of entry of block_info array. */
1217 TV_DF_LR, /* Timing variable. */
1218 false /* Reset blocks on dropping out of blocks_to_analyze. */
1219};
1220
1221
1222/* Create a new DATAFLOW instance and add it to an existing instance
1223 of DF. The returned structure is what is used to get at the
1224 solution. */
1225
1226void
1227df_lr_add_problem (void)
1228{
1229 df_add_problem (&problem_LR);
1230 /* These will be initialized when df_scan_blocks processes each
1231 block. */
1232 df_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1233}
1234
1235
1236/* Verify that all of the lr related info is consistent and
1237 correct. */
1238
1239void
1240df_lr_verify_transfer_functions (void)
1241{
1242 basic_block bb;
1243 bitmap_head saved_def;
1244 bitmap_head saved_use;
1245 bitmap_head all_blocks;
1246
1247 if (!df)
1248 return;
1249
1250 bitmap_initialize (&saved_def, &bitmap_default_obstack);
1251 bitmap_initialize (&saved_use, &bitmap_default_obstack);
1252 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1253
1254 FOR_ALL_BB_FN (bb, cfun)
1255 {
1256 struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb->index);
1257 bitmap_set_bit (&all_blocks, bb->index);
1258
1259 if (bb_info)
1260 {
1261 /* Make a copy of the transfer functions and then compute
1262 new ones to see if the transfer functions have
1263 changed. */
1264 if (!bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1265 bb->index))
1266 {
1267 bitmap_copy (&saved_def, &bb_info->def);
1268 bitmap_copy (&saved_use, &bb_info->use);
1269 bitmap_clear (&bb_info->def);
1270 bitmap_clear (&bb_info->use);
1271
1272 df_lr_bb_local_compute (bb->index);
1273 gcc_assert (bitmap_equal_p (&saved_def, &bb_info->def));
1274 gcc_assert (bitmap_equal_p (&saved_use, &bb_info->use));
1275 }
1276 }
1277 else
1278 {
1279 /* If we do not have basic block info, the block must be in
1280 the list of dirty blocks or else some one has added a
1281 block behind our backs. */
1282 gcc_assert (bitmap_bit_p (df_lr->out_of_date_transfer_functions,
1283 bb->index));
1284 }
1285 /* Make sure no one created a block without following
1286 procedures. */
1287 gcc_assert (df_scan_get_bb_info (bb->index));
1288 }
1289
1290 /* Make sure there are no dirty bits in blocks that have been deleted. */
1291 gcc_assert (!bitmap_intersect_compl_p (df_lr->out_of_date_transfer_functions,
1292 &all_blocks));
1293
1294 bitmap_clear (&saved_def);
1295 bitmap_clear (&saved_use);
1296 bitmap_clear (&all_blocks);
1297}
1298
1299
1300
1301/*----------------------------------------------------------------------------
1302 LIVE AND MAY-INITIALIZED REGISTERS.
1303
1304 This problem first computes the IN and OUT bitvectors for the
1305 may-initialized registers problems, which is a forward problem.
1306 It gives the set of registers for which we MAY have an available
1307 definition, i.e. for which there is an available definition on
1308 at least one path from the entry block to the entry/exit of a
1309 basic block. Sets generate a definition, while clobbers kill
1310 a definition.
1311
1312 In and out bitvectors are built for each basic block and are indexed by
1313 regnum (see df.h for details). In and out bitvectors in struct
1314 df_live_bb_info actually refers to the may-initialized problem;
1315
1316 Then, the in and out sets for the LIVE problem itself are computed.
1317 These are the logical AND of the IN and OUT sets from the LR problem
1318 and the may-initialized problem.
1319----------------------------------------------------------------------------*/
1320
1321/* Private data used to verify the solution for this problem. */
1322struct df_live_problem_data
1323{
1324 bitmap_head *in;
1325 bitmap_head *out;
1326 /* An obstack for the bitmaps we need for this problem. */
1327 bitmap_obstack live_bitmaps;
1328};
1329
1330/* Scratch var used by transfer functions. This is used to implement
1331 an optimization to reduce the amount of space used to compute the
1332 combined lr and live analysis. */
1333static bitmap_head df_live_scratch;
1334
1335
1336/* Free basic block info. */
1337
1338static void
1339df_live_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1340 void *vbb_info)
1341{
1342 struct df_live_bb_info *bb_info = (struct df_live_bb_info *) vbb_info;
1343 if (bb_info)
1344 {
1345 bitmap_clear (&bb_info->gen);
1346 bitmap_clear (&bb_info->kill);
1347 bitmap_clear (&bb_info->in);
1348 bitmap_clear (&bb_info->out);
1349 }
1350}
1351
1352
1353/* Allocate or reset bitmaps for DF_LIVE blocks. The solution bits are
1354 not touched unless the block is new. */
1355
1356static void
1357df_live_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
1358{
1359 unsigned int bb_index;
1360 bitmap_iterator bi;
1361 struct df_live_problem_data *problem_data;
1362
1363 if (df_live->problem_data)
1364 problem_data = (struct df_live_problem_data *) df_live->problem_data;
1365 else
1366 {
1367 problem_data = XNEW (struct df_live_problem_data);
1368 df_live->problem_data = problem_data;
1369
1370 problem_data->out = NULL;
1371 problem_data->in = NULL;
1372 bitmap_obstack_initialize (&problem_data->live_bitmaps);
1373 bitmap_initialize (&df_live_scratch, &problem_data->live_bitmaps);
1374 }
1375
1376 df_grow_bb_info (df_live);
1377
1378 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions, 0, bb_index, bi)
1379 {
1380 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1381
1382 /* When bitmaps are already initialized, just clear them. */
1383 if (bb_info->kill.obstack)
1384 {
1385 bitmap_clear (&bb_info->kill);
1386 bitmap_clear (&bb_info->gen);
1387 }
1388 else
1389 {
1390 bitmap_initialize (&bb_info->kill, &problem_data->live_bitmaps);
1391 bitmap_initialize (&bb_info->gen, &problem_data->live_bitmaps);
1392 bitmap_initialize (&bb_info->in, &problem_data->live_bitmaps);
1393 bitmap_initialize (&bb_info->out, &problem_data->live_bitmaps);
1394 }
1395 }
1396 df_live->optional_p = (optimize <= 1);
1397}
1398
1399
1400/* Reset the global solution for recalculation. */
1401
1402static void
1403df_live_reset (bitmap all_blocks)
1404{
1405 unsigned int bb_index;
1406 bitmap_iterator bi;
1407
1408 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1409 {
1410 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1411 gcc_assert (bb_info);
1412 bitmap_clear (&bb_info->in);
1413 bitmap_clear (&bb_info->out);
1414 }
1415}
1416
1417
1418/* Compute local uninitialized register info for basic block BB. */
1419
1420static void
1421df_live_bb_local_compute (unsigned int bb_index)
1422{
1423 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1424 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1425 rtx_insn *insn;
1426 df_ref def;
1427 int luid = 0;
1428
1429 FOR_BB_INSNS (bb, insn)
1430 {
1431 unsigned int uid = INSN_UID (insn);
1432 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1433
1434 /* Inserting labels does not always trigger the incremental
1435 rescanning. */
1436 if (!insn_info)
1437 {
1438 gcc_assert (!INSN_P (insn));
1439 insn_info = df_insn_create_insn_record (insn);
1440 }
1441
1442 DF_INSN_INFO_LUID (insn_info) = luid;
1443 if (!INSN_P (insn))
1444 continue;
1445
1446 luid++;
1447 FOR_EACH_INSN_INFO_DEF (def, insn_info)
1448 {
1449 unsigned int regno = DF_REF_REGNO (def);
1450
1451 if (DF_REF_FLAGS_IS_SET (def,
1452 DF_REF_PARTIAL | DF_REF_CONDITIONAL))
1453 /* All partial or conditional def
1454 seen are included in the gen set. */
1455 bitmap_set_bit (&bb_info->gen, regno);
1456 else if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER))
1457 /* Only must clobbers for the entire reg destroy the
1458 value. */
1459 bitmap_set_bit (&bb_info->kill, regno);
1460 else if (! DF_REF_FLAGS_IS_SET (def, DF_REF_MAY_CLOBBER))
1461 bitmap_set_bit (&bb_info->gen, regno);
1462 }
1463 }
1464
1465 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
1466 bitmap_set_bit (&bb_info->gen, DF_REF_REGNO (def));
1467}
1468
1469
1470/* Compute local uninitialized register info. */
1471
1472static void
1473df_live_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
1474{
1475 unsigned int bb_index;
1476 bitmap_iterator bi;
1477
1478 df_grow_insn_info ();
1479
1480 EXECUTE_IF_SET_IN_BITMAP (df_live->out_of_date_transfer_functions,
1481 0, bb_index, bi)
1482 {
1483 df_live_bb_local_compute (bb_index);
1484 }
1485
1486 bitmap_clear (df_live->out_of_date_transfer_functions);
1487}
1488
1489
1490/* Initialize the solution vectors. */
1491
1492static void
1493df_live_init (bitmap all_blocks)
1494{
1495 unsigned int bb_index;
1496 bitmap_iterator bi;
1497
1498 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1499 {
1500 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1501 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1502
1503 /* No register may reach a location where it is not used. Thus
1504 we trim the rr result to the places where it is used. */
1505 bitmap_and (&bb_info->out, &bb_info->gen, &bb_lr_info->out);
1506 bitmap_clear (&bb_info->in);
1507 }
1508}
1509
1510/* Forward confluence function that ignores fake edges. */
1511
1512static bool
1513df_live_confluence_n (edge e)
1514{
1515 bitmap op1 = &df_live_get_bb_info (e->dest->index)->in;
1516 bitmap op2 = &df_live_get_bb_info (e->src->index)->out;
1517
1518 if (e->flags & EDGE_FAKE)
1519 return false;
1520
1521 return bitmap_ior_into (op1, op2);
1522}
1523
1524
1525/* Transfer function for the forwards may-initialized problem. */
1526
1527static bool
1528df_live_transfer_function (int bb_index)
1529{
1530 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
1531 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1532 bitmap in = &bb_info->in;
1533 bitmap out = &bb_info->out;
1534 bitmap gen = &bb_info->gen;
1535 bitmap kill = &bb_info->kill;
1536
1537 /* We need to use a scratch set here so that the value returned from this
1538 function invocation properly reflects whether the sets changed in a
1539 significant way; i.e. not just because the lr set was anded in. */
1540 bitmap_and (&df_live_scratch, gen, &bb_lr_info->out);
1541 /* No register may reach a location where it is not used. Thus
1542 we trim the rr result to the places where it is used. */
1543 bitmap_and_into (in, &bb_lr_info->in);
1544
1545 return bitmap_ior_and_compl (out, &df_live_scratch, in, kill);
1546}
1547
1548
1549/* And the LR info with the may-initialized registers to produce the LIVE info. */
1550
1551static void
1552df_live_finalize (bitmap all_blocks)
1553{
1554
1555 if (df_live->solutions_dirty)
1556 {
1557 bitmap_iterator bi;
1558 unsigned int bb_index;
1559
1560 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1561 {
1562 struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
1563 struct df_live_bb_info *bb_live_info = df_live_get_bb_info (bb_index);
1564
1565 /* No register may reach a location where it is not used. Thus
1566 we trim the rr result to the places where it is used. */
1567 bitmap_and_into (&bb_live_info->in, &bb_lr_info->in);
1568 bitmap_and_into (&bb_live_info->out, &bb_lr_info->out);
1569 }
1570
1571 df_live->solutions_dirty = false;
1572 }
1573}
1574
1575
1576/* Free all storage associated with the problem. */
1577
1578static void
1579df_live_free (void)
1580{
1581 struct df_live_problem_data *problem_data
1582 = (struct df_live_problem_data *) df_live->problem_data;
1583 if (df_live->block_info)
1584 {
1585 df_live->block_info_size = 0;
1586 free (df_live->block_info);
1587 df_live->block_info = NULL;
1588 bitmap_clear (&df_live_scratch);
1589 bitmap_obstack_release (&problem_data->live_bitmaps);
1590 free (problem_data);
1591 df_live->problem_data = NULL;
1592 }
1593 BITMAP_FREE (df_live->out_of_date_transfer_functions);
1594 free (df_live);
1595}
1596
1597
1598/* Debugging info at top of bb. */
1599
1600static void
1601df_live_top_dump (basic_block bb, FILE *file)
1602{
1603 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1604 struct df_live_problem_data *problem_data;
1605
1606 if (!bb_info)
1607 return;
1608
1609 fprintf (file, ";; live in \t");
1610 df_print_regset (file, &bb_info->in);
1611 if (df_live->problem_data)
1612 {
1613 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1614 if (problem_data->in)
1615 {
1616 fprintf (file, ";; old in \t");
1617 df_print_regset (file, &problem_data->in[bb->index]);
1618 }
1619 }
1620 fprintf (file, ";; live gen \t");
1621 df_print_regset (file, &bb_info->gen);
1622 fprintf (file, ";; live kill\t");
1623 df_print_regset (file, &bb_info->kill);
1624}
1625
1626
1627/* Debugging info at bottom of bb. */
1628
1629static void
1630df_live_bottom_dump (basic_block bb, FILE *file)
1631{
1632 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1633 struct df_live_problem_data *problem_data;
1634
1635 if (!bb_info)
1636 return;
1637
1638 fprintf (file, ";; live out \t");
1639 df_print_regset (file, &bb_info->out);
1640 if (df_live->problem_data)
1641 {
1642 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1643 if (problem_data->out)
1644 {
1645 fprintf (file, ";; old out \t");
1646 df_print_regset (file, &problem_data->out[bb->index]);
1647 }
1648 }
1649}
1650
1651
1652/* Build the datastructure to verify that the solution to the dataflow
1653 equations is not dirty. */
1654
1655static void
1656df_live_verify_solution_start (void)
1657{
1658 basic_block bb;
1659 struct df_live_problem_data *problem_data;
1660 if (df_live->solutions_dirty)
1661 return;
1662
1663 /* Set it true so that the solution is recomputed. */
1664 df_live->solutions_dirty = true;
1665
1666 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1667 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1668 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
1669
1670 FOR_ALL_BB_FN (bb, cfun)
1671 {
1672 bitmap_initialize (&problem_data->in[bb->index], &problem_data->live_bitmaps);
1673 bitmap_initialize (&problem_data->out[bb->index], &problem_data->live_bitmaps);
1674 bitmap_copy (&problem_data->in[bb->index], DF_LIVE_IN (bb));
1675 bitmap_copy (&problem_data->out[bb->index], DF_LIVE_OUT (bb));
1676 }
1677}
1678
1679
1680/* Compare the saved datastructure and the new solution to the dataflow
1681 equations. */
1682
1683static void
1684df_live_verify_solution_end (void)
1685{
1686 struct df_live_problem_data *problem_data;
1687 basic_block bb;
1688
1689 problem_data = (struct df_live_problem_data *)df_live->problem_data;
1690 if (!problem_data->out)
1691 return;
1692
1693 FOR_ALL_BB_FN (bb, cfun)
1694 {
1695 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_LIVE_IN (bb)))
1696 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_LIVE_OUT (bb))))
1697 {
1698 /*df_dump (stderr);*/
1699 gcc_unreachable ();
1700 }
1701 }
1702
1703 /* Cannot delete them immediately because you may want to dump them
1704 if the comparison fails. */
1705 FOR_ALL_BB_FN (bb, cfun)
1706 {
1707 bitmap_clear (&problem_data->in[bb->index]);
1708 bitmap_clear (&problem_data->out[bb->index]);
1709 }
1710
1711 free (problem_data->in);
1712 free (problem_data->out);
1713 free (problem_data);
1714 df_live->problem_data = NULL;
1715}
1716
1717
1718/* All of the information associated with every instance of the problem. */
1719
1720static const struct df_problem problem_LIVE =
1721{
1722 DF_LIVE, /* Problem id. */
1723 DF_FORWARD, /* Direction. */
1724 df_live_alloc, /* Allocate the problem specific data. */
1725 df_live_reset, /* Reset global information. */
1726 df_live_free_bb_info, /* Free basic block info. */
1727 df_live_local_compute, /* Local compute function. */
1728 df_live_init, /* Init the solution specific data. */
1729 df_worklist_dataflow, /* Worklist solver. */
1730 NULL, /* Confluence operator 0. */
1731 df_live_confluence_n, /* Confluence operator n. */
1732 df_live_transfer_function, /* Transfer function. */
1733 df_live_finalize, /* Finalize function. */
1734 df_live_free, /* Free all of the problem information. */
1735 df_live_free, /* Remove this problem from the stack of dataflow problems. */
1736 NULL, /* Debugging. */
1737 df_live_top_dump, /* Debugging start block. */
1738 df_live_bottom_dump, /* Debugging end block. */
1739 NULL, /* Debugging start insn. */
1740 NULL, /* Debugging end insn. */
1741 df_live_verify_solution_start,/* Incremental solution verify start. */
1742 df_live_verify_solution_end, /* Incremental solution verify end. */
1743 &problem_LR, /* Dependent problem. */
1744 sizeof (struct df_live_bb_info),/* Size of entry of block_info array. */
1745 TV_DF_LIVE, /* Timing variable. */
1746 false /* Reset blocks on dropping out of blocks_to_analyze. */
1747};
1748
1749
1750/* Create a new DATAFLOW instance and add it to an existing instance
1751 of DF. The returned structure is what is used to get at the
1752 solution. */
1753
1754void
1755df_live_add_problem (void)
1756{
1757 df_add_problem (&problem_LIVE);
1758 /* These will be initialized when df_scan_blocks processes each
1759 block. */
1760 df_live->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
1761}
1762
1763
1764/* Set all of the blocks as dirty. This needs to be done if this
1765 problem is added after all of the insns have been scanned. */
1766
1767void
1768df_live_set_all_dirty (void)
1769{
1770 basic_block bb;
1771 FOR_ALL_BB_FN (bb, cfun)
1772 bitmap_set_bit (df_live->out_of_date_transfer_functions,
1773 bb->index);
1774}
1775
1776
1777/* Verify that all of the lr related info is consistent and
1778 correct. */
1779
1780void
1781df_live_verify_transfer_functions (void)
1782{
1783 basic_block bb;
1784 bitmap_head saved_gen;
1785 bitmap_head saved_kill;
1786 bitmap_head all_blocks;
1787
1788 if (!df)
1789 return;
1790
1791 bitmap_initialize (&saved_gen, &bitmap_default_obstack);
1792 bitmap_initialize (&saved_kill, &bitmap_default_obstack);
1793 bitmap_initialize (&all_blocks, &bitmap_default_obstack);
1794
1795 df_grow_insn_info ();
1796
1797 FOR_ALL_BB_FN (bb, cfun)
1798 {
1799 struct df_live_bb_info *bb_info = df_live_get_bb_info (bb->index);
1800 bitmap_set_bit (&all_blocks, bb->index);
1801
1802 if (bb_info)
1803 {
1804 /* Make a copy of the transfer functions and then compute
1805 new ones to see if the transfer functions have
1806 changed. */
1807 if (!bitmap_bit_p (df_live->out_of_date_transfer_functions,
1808 bb->index))
1809 {
1810 bitmap_copy (&saved_gen, &bb_info->gen);
1811 bitmap_copy (&saved_kill, &bb_info->kill);
1812 bitmap_clear (&bb_info->gen);
1813 bitmap_clear (&bb_info->kill);
1814
1815 df_live_bb_local_compute (bb->index);
1816 gcc_assert (bitmap_equal_p (&saved_gen, &bb_info->gen));
1817 gcc_assert (bitmap_equal_p (&saved_kill, &bb_info->kill));
1818 }
1819 }
1820 else
1821 {
1822 /* If we do not have basic block info, the block must be in
1823 the list of dirty blocks or else some one has added a
1824 block behind our backs. */
1825 gcc_assert (bitmap_bit_p (df_live->out_of_date_transfer_functions,
1826 bb->index));
1827 }
1828 /* Make sure no one created a block without following
1829 procedures. */
1830 gcc_assert (df_scan_get_bb_info (bb->index));
1831 }
1832
1833 /* Make sure there are no dirty bits in blocks that have been deleted. */
1834 gcc_assert (!bitmap_intersect_compl_p (df_live->out_of_date_transfer_functions,
1835 &all_blocks));
1836 bitmap_clear (&saved_gen);
1837 bitmap_clear (&saved_kill);
1838 bitmap_clear (&all_blocks);
1839}
1840
1841/*----------------------------------------------------------------------------
1842 MUST-INITIALIZED REGISTERS.
1843----------------------------------------------------------------------------*/
1844
1845/* Private data used to verify the solution for this problem. */
1846struct df_mir_problem_data
1847{
1848 bitmap_head *in;
1849 bitmap_head *out;
1850 /* An obstack for the bitmaps we need for this problem. */
1851 bitmap_obstack mir_bitmaps;
1852};
1853
1854
1855/* Free basic block info. */
1856
1857static void
1858df_mir_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
1859 void *vbb_info)
1860{
1861 struct df_mir_bb_info *bb_info = (struct df_mir_bb_info *) vbb_info;
1862 if (bb_info)
1863 {
1864 bitmap_clear (&bb_info->gen);
1865 bitmap_clear (&bb_info->kill);
1866 bitmap_clear (&bb_info->in);
1867 bitmap_clear (&bb_info->out);
1868 }
1869}
1870
1871
1872/* Allocate or reset bitmaps for DF_MIR blocks. The solution bits are
1873 not touched unless the block is new. */
1874
1875static void
1876df_mir_alloc (bitmap all_blocks)
1877{
1878 unsigned int bb_index;
1879 bitmap_iterator bi;
1880 struct df_mir_problem_data *problem_data;
1881
1882 if (df_mir->problem_data)
1883 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
1884 else
1885 {
1886 problem_data = XNEW (struct df_mir_problem_data);
1887 df_mir->problem_data = problem_data;
1888
1889 problem_data->out = NULL;
1890 problem_data->in = NULL;
1891 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
1892 }
1893
1894 df_grow_bb_info (df_mir);
1895
1896 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1897 {
1898 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1899
1900 /* When bitmaps are already initialized, just clear them. */
1901 if (bb_info->kill.obstack)
1902 {
1903 bitmap_clear (&bb_info->kill);
1904 bitmap_clear (&bb_info->gen);
1905 }
1906 else
1907 {
1908 bitmap_initialize (&bb_info->kill, &problem_data->mir_bitmaps);
1909 bitmap_initialize (&bb_info->gen, &problem_data->mir_bitmaps);
1910 bitmap_initialize (&bb_info->in, &problem_data->mir_bitmaps);
1911 bitmap_initialize (&bb_info->out, &problem_data->mir_bitmaps);
1912 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1913 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1914 }
1915 }
1916
1917 df_mir->optional_p = 1;
1918}
1919
1920
1921/* Reset the global solution for recalculation. */
1922
1923static void
1924df_mir_reset (bitmap all_blocks)
1925{
1926 unsigned int bb_index;
1927 bitmap_iterator bi;
1928
1929 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1930 {
1931 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1932
1933 gcc_assert (bb_info);
1934
1935 bitmap_clear (&bb_info->in);
1936 bitmap_set_range (&bb_info->in, 0, DF_REG_SIZE (df));
1937 bitmap_clear (&bb_info->out);
1938 bitmap_set_range (&bb_info->out, 0, DF_REG_SIZE (df));
1939 }
1940}
1941
1942
1943/* Compute local uninitialized register info for basic block BB. */
1944
1945static void
1946df_mir_bb_local_compute (unsigned int bb_index)
1947{
1948 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
1949 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
1950 rtx_insn *insn;
1951 int luid = 0;
1952
1953 /* Ignoring artificial defs is intentional: these often pretend that some
1954 registers carry incoming arguments (when they are FUNCTION_ARG_REGNO) even
1955 though they are not used for that. As a result, conservatively assume
1956 they may be uninitialized. */
1957
1958 FOR_BB_INSNS (bb, insn)
1959 {
1960 unsigned int uid = INSN_UID (insn);
1961 struct df_insn_info *insn_info = DF_INSN_UID_GET (uid);
1962
1963 /* Inserting labels does not always trigger the incremental
1964 rescanning. */
1965 if (!insn_info)
1966 {
1967 gcc_assert (!INSN_P (insn));
1968 insn_info = df_insn_create_insn_record (insn);
1969 }
1970
1971 DF_INSN_INFO_LUID (insn_info) = luid;
1972 if (!INSN_P (insn))
1973 continue;
1974
1975 luid++;
1976 df_mir_simulate_one_insn (bb, insn, &bb_info->kill, &bb_info->gen);
1977 }
1978}
1979
1980
1981/* Compute local uninitialized register info. */
1982
1983static void
1984df_mir_local_compute (bitmap all_blocks)
1985{
1986 unsigned int bb_index;
1987 bitmap_iterator bi;
1988
1989 df_grow_insn_info ();
1990
1991 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
1992 {
1993 df_mir_bb_local_compute (bb_index);
1994 }
1995}
1996
1997
1998/* Initialize the solution vectors. */
1999
2000static void
2001df_mir_init (bitmap all_blocks)
2002{
2003 df_mir_reset (all_blocks);
2004}
2005
2006
2007/* Initialize IN sets for blocks with no predecessors: when landing on such
2008 blocks, assume all registers are uninitialized. */
2009
2010static void
2011df_mir_confluence_0 (basic_block bb)
2012{
2013 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2014
2015 bitmap_clear (&bb_info->in);
2016}
2017
2018
2019/* Forward confluence function that ignores fake edges. */
2020
2021static bool
2022df_mir_confluence_n (edge e)
2023{
2024 bitmap op1 = &df_mir_get_bb_info (e->dest->index)->in;
2025 bitmap op2 = &df_mir_get_bb_info (e->src->index)->out;
2026
2027 if (e->flags & EDGE_FAKE)
2028 return false;
2029
2030 /* A register is must-initialized at the entry of a basic block iff it is
2031 must-initialized at the exit of all the predecessors. */
2032 return bitmap_and_into (op1, op2);
2033}
2034
2035
2036/* Transfer function for the forwards must-initialized problem. */
2037
2038static bool
2039df_mir_transfer_function (int bb_index)
2040{
2041 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb_index);
2042 bitmap in = &bb_info->in;
2043 bitmap out = &bb_info->out;
2044 bitmap gen = &bb_info->gen;
2045 bitmap kill = &bb_info->kill;
2046
2047 return bitmap_ior_and_compl (out, gen, in, kill);
2048}
2049
2050
2051/* Free all storage associated with the problem. */
2052
2053static void
2054df_mir_free (void)
2055{
2056 struct df_mir_problem_data *problem_data
2057 = (struct df_mir_problem_data *) df_mir->problem_data;
2058 if (df_mir->block_info)
2059 {
2060 df_mir->block_info_size = 0;
2061 free (df_mir->block_info);
2062 df_mir->block_info = NULL;
2063 bitmap_obstack_release (&problem_data->mir_bitmaps);
2064 free (problem_data);
2065 df_mir->problem_data = NULL;
2066 }
2067 free (df_mir);
2068}
2069
2070
2071/* Debugging info at top of bb. */
2072
2073static void
2074df_mir_top_dump (basic_block bb, FILE *file)
2075{
2076 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2077
2078 if (!bb_info)
2079 return;
2080
2081 fprintf (file, ";; mir in \t");
2082 df_print_regset (file, &bb_info->in);
2083 fprintf (file, ";; mir kill\t");
2084 df_print_regset (file, &bb_info->kill);
2085 fprintf (file, ";; mir gen \t");
2086 df_print_regset (file, &bb_info->gen);
2087}
2088
2089/* Debugging info at bottom of bb. */
2090
2091static void
2092df_mir_bottom_dump (basic_block bb, FILE *file)
2093{
2094 struct df_mir_bb_info *bb_info = df_mir_get_bb_info (bb->index);
2095
2096 if (!bb_info)
2097 return;
2098
2099 fprintf (file, ";; mir out \t");
2100 df_print_regset (file, &bb_info->out);
2101}
2102
2103
2104/* Build the datastructure to verify that the solution to the dataflow
2105 equations is not dirty. */
2106
2107static void
2108df_mir_verify_solution_start (void)
2109{
2110 basic_block bb;
2111 struct df_mir_problem_data *problem_data;
2112 if (df_mir->solutions_dirty)
2113 return;
2114
2115 /* Set it true so that the solution is recomputed. */
2116 df_mir->solutions_dirty = true;
2117
2118 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2119 problem_data->in = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2120 problem_data->out = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
2121 bitmap_obstack_initialize (&problem_data->mir_bitmaps);
2122
2123 FOR_ALL_BB_FN (bb, cfun)
2124 {
2125 bitmap_initialize (&problem_data->in[bb->index], &problem_data->mir_bitmaps);
2126 bitmap_initialize (&problem_data->out[bb->index], &problem_data->mir_bitmaps);
2127 bitmap_copy (&problem_data->in[bb->index], DF_MIR_IN (bb));
2128 bitmap_copy (&problem_data->out[bb->index], DF_MIR_OUT (bb));
2129 }
2130}
2131
2132
2133/* Compare the saved datastructure and the new solution to the dataflow
2134 equations. */
2135
2136static void
2137df_mir_verify_solution_end (void)
2138{
2139 struct df_mir_problem_data *problem_data;
2140 basic_block bb;
2141
2142 problem_data = (struct df_mir_problem_data *) df_mir->problem_data;
2143 if (!problem_data->out)
2144 return;
2145
2146 FOR_ALL_BB_FN (bb, cfun)
2147 {
2148 if ((!bitmap_equal_p (&problem_data->in[bb->index], DF_MIR_IN (bb)))
2149 || (!bitmap_equal_p (&problem_data->out[bb->index], DF_MIR_OUT (bb))))
2150 gcc_unreachable ();
2151 }
2152
2153 /* Cannot delete them immediately because you may want to dump them
2154 if the comparison fails. */
2155 FOR_ALL_BB_FN (bb, cfun)
2156 {
2157 bitmap_clear (&problem_data->in[bb->index]);
2158 bitmap_clear (&problem_data->out[bb->index]);
2159 }
2160
2161 free (problem_data->in);
2162 free (problem_data->out);
2163 bitmap_obstack_release (&problem_data->mir_bitmaps);
2164 free (problem_data);
2165 df_mir->problem_data = NULL;
2166}
2167
2168
2169/* All of the information associated with every instance of the problem. */
2170
2171static const struct df_problem problem_MIR =
2172{
2173 DF_MIR, /* Problem id. */
2174 DF_FORWARD, /* Direction. */
2175 df_mir_alloc, /* Allocate the problem specific data. */
2176 df_mir_reset, /* Reset global information. */
2177 df_mir_free_bb_info, /* Free basic block info. */
2178 df_mir_local_compute, /* Local compute function. */
2179 df_mir_init, /* Init the solution specific data. */
2180 df_worklist_dataflow, /* Worklist solver. */
2181 df_mir_confluence_0, /* Confluence operator 0. */
2182 df_mir_confluence_n, /* Confluence operator n. */
2183 df_mir_transfer_function, /* Transfer function. */
2184 NULL, /* Finalize function. */
2185 df_mir_free, /* Free all of the problem information. */
2186 df_mir_free, /* Remove this problem from the stack of dataflow problems. */
2187 NULL, /* Debugging. */
2188 df_mir_top_dump, /* Debugging start block. */
2189 df_mir_bottom_dump, /* Debugging end block. */
2190 NULL, /* Debugging start insn. */
2191 NULL, /* Debugging end insn. */
2192 df_mir_verify_solution_start, /* Incremental solution verify start. */
2193 df_mir_verify_solution_end, /* Incremental solution verify end. */
2194 NULL, /* Dependent problem. */
2195 sizeof (struct df_mir_bb_info),/* Size of entry of block_info array. */
2196 TV_DF_MIR, /* Timing variable. */
2197 false /* Reset blocks on dropping out of blocks_to_analyze. */
2198};
2199
2200
2201/* Create a new DATAFLOW instance and add it to an existing instance
2202 of DF. */
2203
2204void
2205df_mir_add_problem (void)
2206{
2207 df_add_problem (&problem_MIR);
2208 /* These will be initialized when df_scan_blocks processes each
2209 block. */
2210 df_mir->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2211}
2212
2213
2214/* Apply the effects of the gen/kills in INSN to the corresponding bitmaps. */
2215
2216void
2217df_mir_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
2218 bitmap kill, bitmap gen)
2219{
2220 df_ref def;
2221
2222 FOR_EACH_INSN_DEF (def, insn)
2223 {
2224 unsigned int regno = DF_REF_REGNO (def);
2225
2226 /* The order of GENs/KILLs matters, so if this def clobbers a reg, any
2227 previous gen is irrelevant (and reciprocally). Also, claim that a
2228 register is GEN only if it is in all cases. */
2229 if (DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
2230 {
2231 bitmap_set_bit (kill, regno);
2232 bitmap_clear_bit (gen, regno);
2233 }
2234 /* In the worst case, partial and conditional defs can leave bits
2235 uninitialized, so assume they do not change anything. */
2236 else if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
2237 {
2238 bitmap_set_bit (gen, regno);
2239 bitmap_clear_bit (kill, regno);
2240 }
2241 }
2242}
2243
2244/*----------------------------------------------------------------------------
2245 CREATE DEF_USE (DU) and / or USE_DEF (UD) CHAINS
2246
2247 Link either the defs to the uses and / or the uses to the defs.
2248
2249 These problems are set up like the other dataflow problems so that
2250 they nicely fit into the framework. They are much simpler and only
2251 involve a single traversal of instructions and an examination of
2252 the reaching defs information (the dependent problem).
2253----------------------------------------------------------------------------*/
2254
2255#define df_chain_problem_p(FLAG) (((enum df_chain_flags)df_chain->local_flags)&(FLAG))
2256
2257/* Create a du or ud chain from SRC to DST and link it into SRC. */
2258
2259struct df_link *
2260df_chain_create (df_ref src, df_ref dst)
2261{
2262 struct df_link *head = DF_REF_CHAIN (src);
2263 struct df_link *link = df_chain->block_pool->allocate ();
2264
2265 DF_REF_CHAIN (src) = link;
2266 link->next = head;
2267 link->ref = dst;
2268 return link;
2269}
2270
2271
2272/* Delete any du or ud chains that start at REF and point to
2273 TARGET. */
2274static void
2275df_chain_unlink_1 (df_ref ref, df_ref target)
2276{
2277 struct df_link *chain = DF_REF_CHAIN (ref);
2278 struct df_link *prev = NULL;
2279
2280 while (chain)
2281 {
2282 if (chain->ref == target)
2283 {
2284 if (prev)
2285 prev->next = chain->next;
2286 else
2287 DF_REF_CHAIN (ref) = chain->next;
2288 df_chain->block_pool->remove (chain);
2289 return;
2290 }
2291 prev = chain;
2292 chain = chain->next;
2293 }
2294}
2295
2296
2297/* Delete a du or ud chain that leave or point to REF. */
2298
2299void
2300df_chain_unlink (df_ref ref)
2301{
2302 struct df_link *chain = DF_REF_CHAIN (ref);
2303 while (chain)
2304 {
2305 struct df_link *next = chain->next;
2306 /* Delete the other side if it exists. */
2307 df_chain_unlink_1 (chain->ref, ref);
2308 df_chain->block_pool->remove (chain);
2309 chain = next;
2310 }
2311 DF_REF_CHAIN (ref) = NULL;
2312}
2313
2314
2315/* Copy the du or ud chain starting at FROM_REF and attach it to
2316 TO_REF. */
2317
2318void
2319df_chain_copy (df_ref to_ref,
2320 struct df_link *from_ref)
2321{
2322 while (from_ref)
2323 {
2324 df_chain_create (to_ref, from_ref->ref);
2325 from_ref = from_ref->next;
2326 }
2327}
2328
2329
2330/* Remove this problem from the stack of dataflow problems. */
2331
2332static void
2333df_chain_remove_problem (void)
2334{
2335 bitmap_iterator bi;
2336 unsigned int bb_index;
2337
2338 /* Wholesale destruction of the old chains. */
2339 if (df_chain->block_pool)
2340 delete df_chain->block_pool;
2341
2342 EXECUTE_IF_SET_IN_BITMAP (df_chain->out_of_date_transfer_functions, 0, bb_index, bi)
2343 {
2344 rtx_insn *insn;
2345 df_ref def, use;
2346 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2347
2348 if (df_chain_problem_p (DF_DU_CHAIN))
2349 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2350 DF_REF_CHAIN (def) = NULL;
2351 if (df_chain_problem_p (DF_UD_CHAIN))
2352 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2353 DF_REF_CHAIN (use) = NULL;
2354
2355 FOR_BB_INSNS (bb, insn)
2356 if (INSN_P (insn))
2357 {
2358 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2359 if (df_chain_problem_p (DF_DU_CHAIN))
2360 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2361 DF_REF_CHAIN (def) = NULL;
2362 if (df_chain_problem_p (DF_UD_CHAIN))
2363 {
2364 FOR_EACH_INSN_INFO_USE (use, insn_info)
2365 DF_REF_CHAIN (use) = NULL;
2366 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2367 DF_REF_CHAIN (use) = NULL;
2368 }
2369 }
2370 }
2371
2372 bitmap_clear (df_chain->out_of_date_transfer_functions);
2373 df_chain->block_pool = NULL;
2374}
2375
2376
2377/* Remove the chain problem completely. */
2378
2379static void
2380df_chain_fully_remove_problem (void)
2381{
2382 df_chain_remove_problem ();
2383 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2384 free (df_chain);
2385}
2386
2387
2388/* Create def-use or use-def chains. */
2389
2390static void
2391df_chain_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2392{
2393 df_chain_remove_problem ();
2394 df_chain->block_pool = new object_allocator<df_link> ("df_chain_block pool");
2395 df_chain->optional_p = true;
2396}
2397
2398
2399/* Reset all of the chains when the set of basic blocks changes. */
2400
2401static void
2402df_chain_reset (bitmap blocks_to_clear ATTRIBUTE_UNUSED)
2403{
2404 df_chain_remove_problem ();
2405}
2406
2407
2408/* Create the chains for a list of USEs. */
2409
2410static void
2411df_chain_create_bb_process_use (bitmap local_rd,
2412 df_ref use,
2413 int top_flag)
2414{
2415 bitmap_iterator bi;
2416 unsigned int def_index;
2417
2418 for (; use; use = DF_REF_NEXT_LOC (use))
2419 {
2420 unsigned int uregno = DF_REF_REGNO (use);
2421 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
2422 || (uregno >= FIRST_PSEUDO_REGISTER))
2423 {
2424 /* Do not want to go through this for an uninitialized var. */
2425 int count = DF_DEFS_COUNT (uregno);
2426 if (count)
2427 {
2428 if (top_flag == (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2429 {
2430 unsigned int first_index = DF_DEFS_BEGIN (uregno);
2431 unsigned int last_index = first_index + count - 1;
2432
2433 EXECUTE_IF_SET_IN_BITMAP (local_rd, first_index, def_index, bi)
2434 {
2435 df_ref def;
2436 if (def_index > last_index)
2437 break;
2438
2439 def = DF_DEFS_GET (def_index);
2440 if (df_chain_problem_p (DF_DU_CHAIN))
2441 df_chain_create (def, use);
2442 if (df_chain_problem_p (DF_UD_CHAIN))
2443 df_chain_create (use, def);
2444 }
2445 }
2446 }
2447 }
2448 }
2449}
2450
2451
2452/* Create chains from reaching defs bitmaps for basic block BB. */
2453
2454static void
2455df_chain_create_bb (unsigned int bb_index)
2456{
2457 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2458 struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
2459 rtx_insn *insn;
2460 bitmap_head cpy;
2461
2462 bitmap_initialize (&cpy, &bitmap_default_obstack);
2463 bitmap_copy (&cpy, &bb_info->in);
2464 bitmap_set_bit (df_chain->out_of_date_transfer_functions, bb_index);
2465
2466 /* Since we are going forwards, process the artificial uses first
2467 then the artificial defs second. */
2468
2469#ifdef EH_USES
2470 /* Create the chains for the artificial uses from the EH_USES at the
2471 beginning of the block. */
2472
2473 /* Artificials are only hard regs. */
2474 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2475 df_chain_create_bb_process_use (&cpy,
2476 df_get_artificial_uses (bb->index),
2477 DF_REF_AT_TOP);
2478#endif
2479
2480 df_rd_simulate_artificial_defs_at_top (bb, &cpy);
2481
2482 /* Process the regular instructions next. */
2483 FOR_BB_INSNS (bb, insn)
2484 if (INSN_P (insn))
2485 {
2486 unsigned int uid = INSN_UID (insn);
2487
2488 /* First scan the uses and link them up with the defs that remain
2489 in the cpy vector. */
2490 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_USES (uid), 0);
2491 if (df->changeable_flags & DF_EQ_NOTES)
2492 df_chain_create_bb_process_use (&cpy, DF_INSN_UID_EQ_USES (uid), 0);
2493
2494 /* Since we are going forwards, process the defs second. */
2495 df_rd_simulate_one_insn (bb, insn, &cpy);
2496 }
2497
2498 /* Create the chains for the artificial uses of the hard registers
2499 at the end of the block. */
2500 if (!(df->changeable_flags & DF_NO_HARD_REGS))
2501 df_chain_create_bb_process_use (&cpy,
2502 df_get_artificial_uses (bb->index),
2503 0);
2504
2505 bitmap_clear (&cpy);
2506}
2507
2508/* Create def-use chains from reaching use bitmaps for basic blocks
2509 in BLOCKS. */
2510
2511static void
2512df_chain_finalize (bitmap all_blocks)
2513{
2514 unsigned int bb_index;
2515 bitmap_iterator bi;
2516
2517 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2518 {
2519 df_chain_create_bb (bb_index);
2520 }
2521}
2522
2523
2524/* Free all storage associated with the problem. */
2525
2526static void
2527df_chain_free (void)
2528{
2529 delete df_chain->block_pool;
2530 BITMAP_FREE (df_chain->out_of_date_transfer_functions);
2531 free (df_chain);
2532}
2533
2534
2535/* Debugging info. */
2536
2537static void
2538df_chain_bb_dump (basic_block bb, FILE *file, bool top)
2539{
2540 /* Artificials are only hard regs. */
2541 if (df->changeable_flags & DF_NO_HARD_REGS)
2542 return;
2543 if (df_chain_problem_p (DF_UD_CHAIN))
2544 {
2545 df_ref use;
2546
2547 fprintf (file,
2548 ";; UD chains for artificial uses at %s\n",
2549 top ? "top" : "bottom");
2550 FOR_EACH_ARTIFICIAL_USE (use, bb->index)
2551 if ((top && (DF_REF_FLAGS (use) & DF_REF_AT_TOP))
2552 || (!top && !(DF_REF_FLAGS (use) & DF_REF_AT_TOP)))
2553 {
2554 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2555 df_chain_dump (DF_REF_CHAIN (use), file);
2556 fprintf (file, "\n");
2557 }
2558 }
2559 if (df_chain_problem_p (DF_DU_CHAIN))
2560 {
2561 df_ref def;
2562
2563 fprintf (file,
2564 ";; DU chains for artificial defs at %s\n",
2565 top ? "top" : "bottom");
2566 FOR_EACH_ARTIFICIAL_DEF (def, bb->index)
2567 if ((top && (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
2568 || (!top && !(DF_REF_FLAGS (def) & DF_REF_AT_TOP)))
2569 {
2570 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2571 df_chain_dump (DF_REF_CHAIN (def), file);
2572 fprintf (file, "\n");
2573 }
2574 }
2575}
2576
2577static void
2578df_chain_top_dump (basic_block bb, FILE *file)
2579{
2580 df_chain_bb_dump (bb, file, /*top=*/true);
2581}
2582
2583static void
2584df_chain_bottom_dump (basic_block bb, FILE *file)
2585{
2586 df_chain_bb_dump (bb, file, /*top=*/false);
2587}
2588
2589static void
2590df_chain_insn_top_dump (const rtx_insn *insn, FILE *file)
2591{
2592 if (df_chain_problem_p (DF_UD_CHAIN) && INSN_P (insn))
2593 {
2594 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2595 df_ref use;
2596
2597 fprintf (file, ";; UD chains for insn luid %d uid %d\n",
2598 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2599 FOR_EACH_INSN_INFO_USE (use, insn_info)
2600 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2601 || !(df->changeable_flags & DF_NO_HARD_REGS))
2602 {
2603 fprintf (file, ";; reg %d ", DF_REF_REGNO (use));
2604 if (DF_REF_FLAGS (use) & DF_REF_READ_WRITE)
2605 fprintf (file, "read/write ");
2606 df_chain_dump (DF_REF_CHAIN (use), file);
2607 fprintf (file, "\n");
2608 }
2609 FOR_EACH_INSN_INFO_EQ_USE (use, insn_info)
2610 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (use))
2611 || !(df->changeable_flags & DF_NO_HARD_REGS))
2612 {
2613 fprintf (file, ";; eq_note reg %d ", DF_REF_REGNO (use));
2614 df_chain_dump (DF_REF_CHAIN (use), file);
2615 fprintf (file, "\n");
2616 }
2617 }
2618}
2619
2620static void
2621df_chain_insn_bottom_dump (const rtx_insn *insn, FILE *file)
2622{
2623 if (df_chain_problem_p (DF_DU_CHAIN) && INSN_P (insn))
2624 {
2625 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2626 df_ref def;
2627 fprintf (file, ";; DU chains for insn luid %d uid %d\n",
2628 DF_INSN_INFO_LUID (insn_info), INSN_UID (insn));
2629 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2630 if (!HARD_REGISTER_NUM_P (DF_REF_REGNO (def))
2631 || !(df->changeable_flags & DF_NO_HARD_REGS))
2632 {
2633 fprintf (file, ";; reg %d ", DF_REF_REGNO (def));
2634 if (DF_REF_FLAGS (def) & DF_REF_READ_WRITE)
2635 fprintf (file, "read/write ");
2636 df_chain_dump (DF_REF_CHAIN (def), file);
2637 fprintf (file, "\n");
2638 }
2639 fprintf (file, "\n");
2640 }
2641}
2642
2643static const struct df_problem problem_CHAIN =
2644{
2645 DF_CHAIN, /* Problem id. */
2646 DF_NONE, /* Direction. */
2647 df_chain_alloc, /* Allocate the problem specific data. */
2648 df_chain_reset, /* Reset global information. */
2649 NULL, /* Free basic block info. */
2650 NULL, /* Local compute function. */
2651 NULL, /* Init the solution specific data. */
2652 NULL, /* Iterative solver. */
2653 NULL, /* Confluence operator 0. */
2654 NULL, /* Confluence operator n. */
2655 NULL, /* Transfer function. */
2656 df_chain_finalize, /* Finalize function. */
2657 df_chain_free, /* Free all of the problem information. */
2658 df_chain_fully_remove_problem,/* Remove this problem from the stack of dataflow problems. */
2659 NULL, /* Debugging. */
2660 df_chain_top_dump, /* Debugging start block. */
2661 df_chain_bottom_dump, /* Debugging end block. */
2662 df_chain_insn_top_dump, /* Debugging start insn. */
2663 df_chain_insn_bottom_dump, /* Debugging end insn. */
2664 NULL, /* Incremental solution verify start. */
2665 NULL, /* Incremental solution verify end. */
2666 &problem_RD, /* Dependent problem. */
2667 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
2668 TV_DF_CHAIN, /* Timing variable. */
2669 false /* Reset blocks on dropping out of blocks_to_analyze. */
2670};
2671
2672
2673/* Create a new DATAFLOW instance and add it to an existing instance
2674 of DF. The returned structure is what is used to get at the
2675 solution. */
2676
2677void
2678df_chain_add_problem (unsigned int chain_flags)
2679{
2680 df_add_problem (&problem_CHAIN);
2681 df_chain->local_flags = chain_flags;
2682 df_chain->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
2683}
2684
2685#undef df_chain_problem_p
2686
2687
2688/*----------------------------------------------------------------------------
2689 WORD LEVEL LIVE REGISTERS
2690
2691 Find the locations in the function where any use of a pseudo can
2692 reach in the backwards direction. In and out bitvectors are built
2693 for each basic block. We only track pseudo registers that have a
2694 size of 2 * UNITS_PER_WORD; bitmaps are indexed by 2 * regno and
2695 contain two bits corresponding to each of the subwords.
2696
2697 ----------------------------------------------------------------------------*/
2698
2699/* Private data used to verify the solution for this problem. */
2700struct df_word_lr_problem_data
2701{
2702 /* An obstack for the bitmaps we need for this problem. */
2703 bitmap_obstack word_lr_bitmaps;
2704};
2705
2706
2707/* Free basic block info. */
2708
2709static void
2710df_word_lr_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
2711 void *vbb_info)
2712{
2713 struct df_word_lr_bb_info *bb_info = (struct df_word_lr_bb_info *) vbb_info;
2714 if (bb_info)
2715 {
2716 bitmap_clear (&bb_info->use);
2717 bitmap_clear (&bb_info->def);
2718 bitmap_clear (&bb_info->in);
2719 bitmap_clear (&bb_info->out);
2720 }
2721}
2722
2723
2724/* Allocate or reset bitmaps for DF_WORD_LR blocks. The solution bits are
2725 not touched unless the block is new. */
2726
2727static void
2728df_word_lr_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
2729{
2730 unsigned int bb_index;
2731 bitmap_iterator bi;
2732 basic_block bb;
2733 struct df_word_lr_problem_data *problem_data
2734 = XNEW (struct df_word_lr_problem_data);
2735
2736 df_word_lr->problem_data = problem_data;
2737
2738 df_grow_bb_info (df_word_lr);
2739
2740 /* Create the mapping from regnos to slots. This does not change
2741 unless the problem is destroyed and recreated. In particular, if
2742 we end up deleting the only insn that used a subreg, we do not
2743 want to redo the mapping because this would invalidate everything
2744 else. */
2745
2746 bitmap_obstack_initialize (&problem_data->word_lr_bitmaps);
2747
2748 FOR_EACH_BB_FN (bb, cfun)
2749 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, bb->index);
2750
2751 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, ENTRY_BLOCK);
2752 bitmap_set_bit (df_word_lr->out_of_date_transfer_functions, EXIT_BLOCK);
2753
2754 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2755 {
2756 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2757
2758 /* When bitmaps are already initialized, just clear them. */
2759 if (bb_info->use.obstack)
2760 {
2761 bitmap_clear (&bb_info->def);
2762 bitmap_clear (&bb_info->use);
2763 }
2764 else
2765 {
2766 bitmap_initialize (&bb_info->use, &problem_data->word_lr_bitmaps);
2767 bitmap_initialize (&bb_info->def, &problem_data->word_lr_bitmaps);
2768 bitmap_initialize (&bb_info->in, &problem_data->word_lr_bitmaps);
2769 bitmap_initialize (&bb_info->out, &problem_data->word_lr_bitmaps);
2770 }
2771 }
2772
2773 df_word_lr->optional_p = true;
2774}
2775
2776
2777/* Reset the global solution for recalculation. */
2778
2779static void
2780df_word_lr_reset (bitmap all_blocks)
2781{
2782 unsigned int bb_index;
2783 bitmap_iterator bi;
2784
2785 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2786 {
2787 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2788 gcc_assert (bb_info);
2789 bitmap_clear (&bb_info->in);
2790 bitmap_clear (&bb_info->out);
2791 }
2792}
2793
2794/* Examine REF, and if it is for a reg we're interested in, set or
2795 clear the bits corresponding to its subwords from the bitmap
2796 according to IS_SET. LIVE is the bitmap we should update. We do
2797 not track hard regs or pseudos of any size other than 2 *
2798 UNITS_PER_WORD.
2799 We return true if we changed the bitmap, or if we encountered a register
2800 we're not tracking. */
2801
2802bool
2803df_word_lr_mark_ref (df_ref ref, bool is_set, regset live)
2804{
2805 rtx orig_reg = DF_REF_REG (ref);
2806 rtx reg = orig_reg;
2807 machine_mode reg_mode;
2808 unsigned regno;
2809 /* Left at -1 for whole accesses. */
2810 int which_subword = -1;
2811 bool changed = false;
2812
2813 if (GET_CODE (reg) == SUBREG)
2814 reg = SUBREG_REG (orig_reg);
2815 regno = REGNO (reg);
2816 reg_mode = GET_MODE (reg);
2817 if (regno < FIRST_PSEUDO_REGISTER
2818 || GET_MODE_SIZE (reg_mode) != 2 * UNITS_PER_WORD)
2819 return true;
2820
2821 if (GET_CODE (orig_reg) == SUBREG
2822 && read_modify_subreg_p (orig_reg))
2823 {
2824 gcc_assert (DF_REF_FLAGS_IS_SET (ref, DF_REF_PARTIAL));
2825 if (subreg_lowpart_p (orig_reg))
2826 which_subword = 0;
2827 else
2828 which_subword = 1;
2829 }
2830 if (is_set)
2831 {
2832 if (which_subword != 1)
2833 changed |= bitmap_set_bit (live, regno * 2);
2834 if (which_subword != 0)
2835 changed |= bitmap_set_bit (live, regno * 2 + 1);
2836 }
2837 else
2838 {
2839 if (which_subword != 1)
2840 changed |= bitmap_clear_bit (live, regno * 2);
2841 if (which_subword != 0)
2842 changed |= bitmap_clear_bit (live, regno * 2 + 1);
2843 }
2844 return changed;
2845}
2846
2847/* Compute local live register info for basic block BB. */
2848
2849static void
2850df_word_lr_bb_local_compute (unsigned int bb_index)
2851{
2852 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
2853 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2854 rtx_insn *insn;
2855 df_ref def, use;
2856
2857 /* Ensure that artificial refs don't contain references to pseudos. */
2858 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
2859 gcc_assert (DF_REF_REGNO (def) < FIRST_PSEUDO_REGISTER);
2860
2861 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
2862 gcc_assert (DF_REF_REGNO (use) < FIRST_PSEUDO_REGISTER);
2863
2864 FOR_BB_INSNS_REVERSE (bb, insn)
2865 {
2866 if (!NONDEBUG_INSN_P (insn))
2867 continue;
2868
2869 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
2870 FOR_EACH_INSN_INFO_DEF (def, insn_info)
2871 /* If the def is to only part of the reg, it does
2872 not kill the other defs that reach here. */
2873 if (!(DF_REF_FLAGS (def) & (DF_REF_CONDITIONAL)))
2874 {
2875 df_word_lr_mark_ref (def, true, &bb_info->def);
2876 df_word_lr_mark_ref (def, false, &bb_info->use);
2877 }
2878 FOR_EACH_INSN_INFO_USE (use, insn_info)
2879 df_word_lr_mark_ref (use, true, &bb_info->use);
2880 }
2881}
2882
2883
2884/* Compute local live register info for each basic block within BLOCKS. */
2885
2886static void
2887df_word_lr_local_compute (bitmap all_blocks ATTRIBUTE_UNUSED)
2888{
2889 unsigned int bb_index;
2890 bitmap_iterator bi;
2891
2892 EXECUTE_IF_SET_IN_BITMAP (df_word_lr->out_of_date_transfer_functions, 0, bb_index, bi)
2893 {
2894 if (bb_index == EXIT_BLOCK)
2895 {
2896 unsigned regno;
2897 bitmap_iterator bi;
2898 EXECUTE_IF_SET_IN_BITMAP (df->exit_block_uses, FIRST_PSEUDO_REGISTER,
2899 regno, bi)
2900 gcc_unreachable ();
2901 }
2902 else
2903 df_word_lr_bb_local_compute (bb_index);
2904 }
2905
2906 bitmap_clear (df_word_lr->out_of_date_transfer_functions);
2907}
2908
2909
2910/* Initialize the solution vectors. */
2911
2912static void
2913df_word_lr_init (bitmap all_blocks)
2914{
2915 unsigned int bb_index;
2916 bitmap_iterator bi;
2917
2918 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
2919 {
2920 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2921 bitmap_copy (&bb_info->in, &bb_info->use);
2922 bitmap_clear (&bb_info->out);
2923 }
2924}
2925
2926
2927/* Confluence function that ignores fake edges. */
2928
2929static bool
2930df_word_lr_confluence_n (edge e)
2931{
2932 bitmap op1 = &df_word_lr_get_bb_info (e->src->index)->out;
2933 bitmap op2 = &df_word_lr_get_bb_info (e->dest->index)->in;
2934
2935 return bitmap_ior_into (op1, op2);
2936}
2937
2938
2939/* Transfer function. */
2940
2941static bool
2942df_word_lr_transfer_function (int bb_index)
2943{
2944 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb_index);
2945 bitmap in = &bb_info->in;
2946 bitmap out = &bb_info->out;
2947 bitmap use = &bb_info->use;
2948 bitmap def = &bb_info->def;
2949
2950 return bitmap_ior_and_compl (in, use, out, def);
2951}
2952
2953
2954/* Free all storage associated with the problem. */
2955
2956static void
2957df_word_lr_free (void)
2958{
2959 struct df_word_lr_problem_data *problem_data
2960 = (struct df_word_lr_problem_data *)df_word_lr->problem_data;
2961
2962 if (df_word_lr->block_info)
2963 {
2964 df_word_lr->block_info_size = 0;
2965 free (df_word_lr->block_info);
2966 df_word_lr->block_info = NULL;
2967 }
2968
2969 BITMAP_FREE (df_word_lr->out_of_date_transfer_functions);
2970 bitmap_obstack_release (&problem_data->word_lr_bitmaps);
2971 free (problem_data);
2972 free (df_word_lr);
2973}
2974
2975
2976/* Debugging info at top of bb. */
2977
2978static void
2979df_word_lr_top_dump (basic_block bb, FILE *file)
2980{
2981 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
2982 if (!bb_info)
2983 return;
2984
2985 fprintf (file, ";; blr in \t");
2986 df_print_word_regset (file, &bb_info->in);
2987 fprintf (file, ";; blr use \t");
2988 df_print_word_regset (file, &bb_info->use);
2989 fprintf (file, ";; blr def \t");
2990 df_print_word_regset (file, &bb_info->def);
2991}
2992
2993
2994/* Debugging info at bottom of bb. */
2995
2996static void
2997df_word_lr_bottom_dump (basic_block bb, FILE *file)
2998{
2999 struct df_word_lr_bb_info *bb_info = df_word_lr_get_bb_info (bb->index);
3000 if (!bb_info)
3001 return;
3002
3003 fprintf (file, ";; blr out \t");
3004 df_print_word_regset (file, &bb_info->out);
3005}
3006
3007
3008/* All of the information associated with every instance of the problem. */
3009
3010static const struct df_problem problem_WORD_LR =
3011{
3012 DF_WORD_LR, /* Problem id. */
3013 DF_BACKWARD, /* Direction. */
3014 df_word_lr_alloc, /* Allocate the problem specific data. */
3015 df_word_lr_reset, /* Reset global information. */
3016 df_word_lr_free_bb_info, /* Free basic block info. */
3017 df_word_lr_local_compute, /* Local compute function. */
3018 df_word_lr_init, /* Init the solution specific data. */
3019 df_worklist_dataflow, /* Worklist solver. */
3020 NULL, /* Confluence operator 0. */
3021 df_word_lr_confluence_n, /* Confluence operator n. */
3022 df_word_lr_transfer_function, /* Transfer function. */
3023 NULL, /* Finalize function. */
3024 df_word_lr_free, /* Free all of the problem information. */
3025 df_word_lr_free, /* Remove this problem from the stack of dataflow problems. */
3026 NULL, /* Debugging. */
3027 df_word_lr_top_dump, /* Debugging start block. */
3028 df_word_lr_bottom_dump, /* Debugging end block. */
3029 NULL, /* Debugging start insn. */
3030 NULL, /* Debugging end insn. */
3031 NULL, /* Incremental solution verify start. */
3032 NULL, /* Incremental solution verify end. */
3033 NULL, /* Dependent problem. */
3034 sizeof (struct df_word_lr_bb_info),/* Size of entry of block_info array. */
3035 TV_DF_WORD_LR, /* Timing variable. */
3036 false /* Reset blocks on dropping out of blocks_to_analyze. */
3037};
3038
3039
3040/* Create a new DATAFLOW instance and add it to an existing instance
3041 of DF. The returned structure is what is used to get at the
3042 solution. */
3043
3044void
3045df_word_lr_add_problem (void)
3046{
3047 df_add_problem (&problem_WORD_LR);
3048 /* These will be initialized when df_scan_blocks processes each
3049 block. */
3050 df_word_lr->out_of_date_transfer_functions = BITMAP_ALLOC (&df_bitmap_obstack);
3051}
3052
3053
3054/* Simulate the effects of the defs of INSN on LIVE. Return true if we changed
3055 any bits, which is used by the caller to determine whether a set is
3056 necessary. We also return true if there are other reasons not to delete
3057 an insn. */
3058
3059bool
3060df_word_lr_simulate_defs (rtx_insn *insn, bitmap live)
3061{
3062 bool changed = false;
3063 df_ref def;
3064
3065 FOR_EACH_INSN_DEF (def, insn)
3066 if (DF_REF_FLAGS (def) & DF_REF_CONDITIONAL)
3067 changed = true;
3068 else
3069 changed |= df_word_lr_mark_ref (def, false, live);
3070 return changed;
3071}
3072
3073
3074/* Simulate the effects of the uses of INSN on LIVE. */
3075
3076void
3077df_word_lr_simulate_uses (rtx_insn *insn, bitmap live)
3078{
3079 df_ref use;
3080
3081 FOR_EACH_INSN_USE (use, insn)
3082 df_word_lr_mark_ref (use, true, live);
3083}
3084
3085/*----------------------------------------------------------------------------
3086 This problem computes REG_DEAD and REG_UNUSED notes.
3087 ----------------------------------------------------------------------------*/
3088
3089static void
3090df_note_alloc (bitmap all_blocks ATTRIBUTE_UNUSED)
3091{
3092 df_note->optional_p = true;
3093}
3094
3095/* This is only used if REG_DEAD_DEBUGGING is in effect. */
3096static void
3097df_print_note (const char *prefix, rtx_insn *insn, rtx note)
3098{
3099 if (dump_file)
3100 {
3101 fprintf (dump_file, "%s %d ", prefix, INSN_UID (insn));
3102 print_rtl (dump_file, note);
3103 fprintf (dump_file, "\n");
3104 }
3105}
3106
3107
3108/* After reg-stack, the x86 floating point stack regs are difficult to
3109 analyze because of all of the pushes, pops and rotations. Thus, we
3110 just leave the notes alone. */
3111
3112#ifdef STACK_REGS
3113static inline bool
3114df_ignore_stack_reg (int regno)
3115{
3116 return regstack_completed
3117 && IN_RANGE (regno, FIRST_STACK_REG, LAST_STACK_REG);
3118}
3119#else
3120static inline bool
3121df_ignore_stack_reg (int regno ATTRIBUTE_UNUSED)
3122{
3123 return false;
3124}
3125#endif
3126
3127
3128/* Remove all of the REG_DEAD or REG_UNUSED notes from INSN. */
3129
3130static void
3131df_remove_dead_and_unused_notes (rtx_insn *insn)
3132{
3133 rtx *pprev = &REG_NOTES (insn);
3134 rtx link = *pprev;
3135
3136 while (link)
3137 {
3138 switch (REG_NOTE_KIND (link))
3139 {
3140 case REG_DEAD:
3141 /* After reg-stack, we need to ignore any unused notes
3142 for the stack registers. */
3143 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3144 {
3145 pprev = &XEXP (link, 1);
3146 link = *pprev;
3147 }
3148 else
3149 {
3150 rtx next = XEXP (link, 1);
3151 if (REG_DEAD_DEBUGGING)
3152 df_print_note ("deleting: ", insn, link);
3153 free_EXPR_LIST_node (link);
3154 *pprev = link = next;
3155 }
3156 break;
3157
3158 case REG_UNUSED:
3159 /* After reg-stack, we need to ignore any unused notes
3160 for the stack registers. */
3161 if (df_ignore_stack_reg (REGNO (XEXP (link, 0))))
3162 {
3163 pprev = &XEXP (link, 1);
3164 link = *pprev;
3165 }
3166 else
3167 {
3168 rtx next = XEXP (link, 1);
3169 if (REG_DEAD_DEBUGGING)
3170 df_print_note ("deleting: ", insn, link);
3171 free_EXPR_LIST_node (link);
3172 *pprev = link = next;
3173 }
3174 break;
3175
3176 default:
3177 pprev = &XEXP (link, 1);
3178 link = *pprev;
3179 break;
3180 }
3181 }
3182}
3183
3184/* Remove REG_EQUAL/REG_EQUIV notes referring to dead pseudos using LIVE
3185 as the bitmap of currently live registers. */
3186
3187static void
3188df_remove_dead_eq_notes (rtx_insn *insn, bitmap live)
3189{
3190 rtx *pprev = &REG_NOTES (insn);
3191 rtx link = *pprev;
3192
3193 while (link)
3194 {
3195 switch (REG_NOTE_KIND (link))
3196 {
3197 case REG_EQUAL:
3198 case REG_EQUIV:
3199 {
3200 /* Remove the notes that refer to dead registers. As we have at most
3201 one REG_EQUAL/EQUIV note, all of EQ_USES will refer to this note
3202 so we need to purge the complete EQ_USES vector when removing
3203 the note using df_notes_rescan. */
3204 df_ref use;
3205 bool deleted = false;
3206
3207 FOR_EACH_INSN_EQ_USE (use, insn)
3208 if (DF_REF_REGNO (use) > FIRST_PSEUDO_REGISTER
3209 && DF_REF_LOC (use)
3210 && (DF_REF_FLAGS (use) & DF_REF_IN_NOTE)
3211 && !bitmap_bit_p (live, DF_REF_REGNO (use))
3212 && loc_mentioned_in_p (DF_REF_LOC (use), XEXP (link, 0)))
3213 {
3214 deleted = true;
3215 break;
3216 }
3217 if (deleted)
3218 {
3219 rtx next;
3220 if (REG_DEAD_DEBUGGING)
3221 df_print_note ("deleting: ", insn, link);
3222 next = XEXP (link, 1);
3223 free_EXPR_LIST_node (link);
3224 *pprev = link = next;
3225 df_notes_rescan (insn);
3226 }
3227 else
3228 {
3229 pprev = &XEXP (link, 1);
3230 link = *pprev;
3231 }
3232 break;
3233 }
3234
3235 default:
3236 pprev = &XEXP (link, 1);
3237 link = *pprev;
3238 break;
3239 }
3240 }
3241}
3242
3243/* Set a NOTE_TYPE note for REG in INSN. */
3244
3245static inline void
3246df_set_note (enum reg_note note_type, rtx_insn *insn, rtx reg)
3247{
3248 gcc_checking_assert (!DEBUG_INSN_P (insn));
3249 add_reg_note (insn, note_type, reg);
3250}
3251
3252/* A subroutine of df_set_unused_notes_for_mw, with a selection of its
3253 arguments. Return true if the register value described by MWS's
3254 mw_reg is known to be completely unused, and if mw_reg can therefore
3255 be used in a REG_UNUSED note. */
3256
3257static bool
3258df_whole_mw_reg_unused_p (struct df_mw_hardreg *mws,
3259 bitmap live, bitmap artificial_uses)
3260{
3261 unsigned int r;
3262
3263 /* If MWS describes a partial reference, create REG_UNUSED notes for
3264 individual hard registers. */
3265 if (mws->flags & DF_REF_PARTIAL)
3266 return false;
3267
3268 /* Likewise if some part of the register is used. */
3269 for (r = mws->start_regno; r <= mws->end_regno; r++)
3270 if (bitmap_bit_p (live, r)
3271 || bitmap_bit_p (artificial_uses, r))
3272 return false;
3273
3274 gcc_assert (REG_P (mws->mw_reg));
3275 return true;
3276}
3277
3278
3279/* Set the REG_UNUSED notes for the multiword hardreg defs in INSN
3280 based on the bits in LIVE. Do not generate notes for registers in
3281 artificial uses. DO_NOT_GEN is updated so that REG_DEAD notes are
3282 not generated if the reg is both read and written by the
3283 instruction.
3284*/
3285
3286static void
3287df_set_unused_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3288 bitmap live, bitmap do_not_gen,
3289 bitmap artificial_uses,
3290 struct dead_debug_local *debug)
3291{
3292 unsigned int r;
3293
3294 if (REG_DEAD_DEBUGGING && dump_file)
3295 fprintf (dump_file, "mw_set_unused looking at mws[%d..%d]\n",
3296 mws->start_regno, mws->end_regno);
3297
3298 if (df_whole_mw_reg_unused_p (mws, live, artificial_uses))
3299 {
3300 unsigned int regno = mws->start_regno;
3301 df_set_note (REG_UNUSED, insn, mws->mw_reg);
3302 dead_debug_insert_temp (debug, regno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3303
3304 if (REG_DEAD_DEBUGGING)
3305 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3306
3307 bitmap_set_bit (do_not_gen, regno);
3308 /* Only do this if the value is totally dead. */
3309 }
3310 else
3311 for (r = mws->start_regno; r <= mws->end_regno; r++)
3312 {
3313 if (!bitmap_bit_p (live, r)
3314 && !bitmap_bit_p (artificial_uses, r))
3315 {
3316 df_set_note (REG_UNUSED, insn, regno_reg_rtx[r]);
3317 dead_debug_insert_temp (debug, r, insn, DEBUG_TEMP_AFTER_WITH_REG);
3318 if (REG_DEAD_DEBUGGING)
3319 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3320 }
3321 bitmap_set_bit (do_not_gen, r);
3322 }
3323}
3324
3325
3326/* A subroutine of df_set_dead_notes_for_mw, with a selection of its
3327 arguments. Return true if the register value described by MWS's
3328 mw_reg is known to be completely dead, and if mw_reg can therefore
3329 be used in a REG_DEAD note. */
3330
3331static bool
3332df_whole_mw_reg_dead_p (struct df_mw_hardreg *mws,
3333 bitmap live, bitmap artificial_uses,
3334 bitmap do_not_gen)
3335{
3336 unsigned int r;
3337
3338 /* If MWS describes a partial reference, create REG_DEAD notes for
3339 individual hard registers. */
3340 if (mws->flags & DF_REF_PARTIAL)
3341 return false;
3342
3343 /* Likewise if some part of the register is not dead. */
3344 for (r = mws->start_regno; r <= mws->end_regno; r++)
3345 if (bitmap_bit_p (live, r)
3346 || bitmap_bit_p (artificial_uses, r)
3347 || bitmap_bit_p (do_not_gen, r))
3348 return false;
3349
3350 gcc_assert (REG_P (mws->mw_reg));
3351 return true;
3352}
3353
3354/* Set the REG_DEAD notes for the multiword hardreg use in INSN based
3355 on the bits in LIVE. DO_NOT_GEN is used to keep REG_DEAD notes
3356 from being set if the instruction both reads and writes the
3357 register. */
3358
3359static void
3360df_set_dead_notes_for_mw (rtx_insn *insn, struct df_mw_hardreg *mws,
3361 bitmap live, bitmap do_not_gen,
3362 bitmap artificial_uses, bool *added_notes_p)
3363{
3364 unsigned int r;
3365 bool is_debug = *added_notes_p;
3366
3367 *added_notes_p = false;
3368
3369 if (REG_DEAD_DEBUGGING && dump_file)
3370 {
3371 fprintf (dump_file, "mw_set_dead looking at mws[%d..%d]\n do_not_gen =",
3372 mws->start_regno, mws->end_regno);
3373 df_print_regset (dump_file, do_not_gen);
3374 fprintf (dump_file, " live =");
3375 df_print_regset (dump_file, live);
3376 fprintf (dump_file, " artificial uses =");
3377 df_print_regset (dump_file, artificial_uses);
3378 }
3379
3380 if (df_whole_mw_reg_dead_p (mws, live, artificial_uses, do_not_gen))
3381 {
3382 if (is_debug)
3383 {
3384 *added_notes_p = true;
3385 return;
3386 }
3387 /* Add a dead note for the entire multi word register. */
3388 df_set_note (REG_DEAD, insn, mws->mw_reg);
3389 if (REG_DEAD_DEBUGGING)
3390 df_print_note ("adding 1: ", insn, REG_NOTES (insn));
3391 }
3392 else
3393 {
3394 for (r = mws->start_regno; r <= mws->end_regno; r++)
3395 if (!bitmap_bit_p (live, r)
3396 && !bitmap_bit_p (artificial_uses, r)
3397 && !bitmap_bit_p (do_not_gen, r))
3398 {
3399 if (is_debug)
3400 {
3401 *added_notes_p = true;
3402 return;
3403 }
3404 df_set_note (REG_DEAD, insn, regno_reg_rtx[r]);
3405 if (REG_DEAD_DEBUGGING)
3406 df_print_note ("adding 2: ", insn, REG_NOTES (insn));
3407 }
3408 }
3409 return;
3410}
3411
3412
3413/* Create a REG_UNUSED note if necessary for DEF in INSN updating
3414 LIVE. Do not generate notes for registers in ARTIFICIAL_USES. */
3415
3416static void
3417df_create_unused_note (rtx_insn *insn, df_ref def,
3418 bitmap live, bitmap artificial_uses,
3419 struct dead_debug_local *debug)
3420{
3421 unsigned int dregno = DF_REF_REGNO (def);
3422
3423 if (REG_DEAD_DEBUGGING && dump_file)
3424 {
3425 fprintf (dump_file, " regular looking at def ");
3426 df_ref_debug (def, dump_file);
3427 }
3428
3429 if (!((DF_REF_FLAGS (def) & DF_REF_MW_HARDREG)
3430 || bitmap_bit_p (live, dregno)
3431 || bitmap_bit_p (artificial_uses, dregno)
3432 || df_ignore_stack_reg (dregno)))
3433 {
3434 rtx reg = (DF_REF_LOC (def))
3435 ? *DF_REF_REAL_LOC (def): DF_REF_REG (def);
3436 df_set_note (REG_UNUSED, insn, reg);
3437 dead_debug_insert_temp (debug, dregno, insn, DEBUG_TEMP_AFTER_WITH_REG);
3438 if (REG_DEAD_DEBUGGING)
3439 df_print_note ("adding 3: ", insn, REG_NOTES (insn));
3440 }
3441
3442 return;
3443}
3444
3445
3446/* Recompute the REG_DEAD and REG_UNUSED notes and compute register
3447 info: lifetime, bb, and number of defs and uses for basic block
3448 BB. The three bitvectors are scratch regs used here. */
3449
3450static void
3451df_note_bb_compute (unsigned int bb_index,
3452 bitmap live, bitmap do_not_gen, bitmap artificial_uses)
3453{
3454 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
3455 rtx_insn *insn;
3456 df_ref def, use;
3457 struct dead_debug_local debug;
3458
3459 dead_debug_local_init (&debug, NULL, NULL);
3460
3461 bitmap_copy (live, df_get_live_out (bb));
3462 bitmap_clear (artificial_uses);
3463
3464 if (REG_DEAD_DEBUGGING && dump_file)
3465 {
3466 fprintf (dump_file, "live at bottom ");
3467 df_print_regset (dump_file, live);
3468 }
3469
3470 /* Process the artificial defs and uses at the bottom of the block
3471 to begin processing. */
3472 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3473 {
3474 if (REG_DEAD_DEBUGGING && dump_file)
3475 fprintf (dump_file, "artificial def %d\n", DF_REF_REGNO (def));
3476
3477 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3478 bitmap_clear_bit (live, DF_REF_REGNO (def));
3479 }
3480
3481 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3482 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3483 {
3484 unsigned int regno = DF_REF_REGNO (use);
3485 bitmap_set_bit (live, regno);
3486
3487 /* Notes are not generated for any of the artificial registers
3488 at the bottom of the block. */
3489 bitmap_set_bit (artificial_uses, regno);
3490 }
3491
3492 if (REG_DEAD_DEBUGGING && dump_file)
3493 {
3494 fprintf (dump_file, "live before artificials out ");
3495 df_print_regset (dump_file, live);
3496 }
3497
3498 FOR_BB_INSNS_REVERSE (bb, insn)
3499 {
3500 if (!INSN_P (insn))
3501 continue;
3502
3503 df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3504 df_mw_hardreg *mw;
3505 int debug_insn;
3506
3507 debug_insn = DEBUG_INSN_P (insn);
3508
3509 bitmap_clear (do_not_gen);
3510 df_remove_dead_and_unused_notes (insn);
3511
3512 /* Process the defs. */
3513 if (CALL_P (insn))
3514 {
3515 if (REG_DEAD_DEBUGGING && dump_file)
3516 {
3517 fprintf (dump_file, "processing call %d\n live =",
3518 INSN_UID (insn));
3519 df_print_regset (dump_file, live);
3520 }
3521
3522 /* We only care about real sets for calls. Clobbers cannot
3523 be depended on to really die. */
3524 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3525 if ((DF_MWS_REG_DEF_P (mw))
3526 && !df_ignore_stack_reg (mw->start_regno))
3527 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3528 artificial_uses, &debug);
3529
3530 /* All of the defs except the return value are some sort of
3531 clobber. This code is for the return. */
3532 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3533 {
3534 unsigned int dregno = DF_REF_REGNO (def);
3535 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3536 {
3537 df_create_unused_note (insn,
3538 def, live, artificial_uses, &debug);
3539 bitmap_set_bit (do_not_gen, dregno);
3540 }
3541
3542 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3543 bitmap_clear_bit (live, dregno);
3544 }
3545 }
3546 else
3547 {
3548 /* Regular insn. */
3549 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3550 if (DF_MWS_REG_DEF_P (mw))
3551 df_set_unused_notes_for_mw (insn, mw, live, do_not_gen,
3552 artificial_uses, &debug);
3553
3554 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3555 {
3556 unsigned int dregno = DF_REF_REGNO (def);
3557 df_create_unused_note (insn,
3558 def, live, artificial_uses, &debug);
3559
3560 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER))
3561 bitmap_set_bit (do_not_gen, dregno);
3562
3563 if (!DF_REF_FLAGS_IS_SET (def, DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3564 bitmap_clear_bit (live, dregno);
3565 }
3566 }
3567
3568 /* Process the uses. */
3569 FOR_EACH_INSN_INFO_MW (mw, insn_info)
3570 if (DF_MWS_REG_USE_P (mw)
3571 && !df_ignore_stack_reg (mw->start_regno))
3572 {
3573 bool really_add_notes = debug_insn != 0;
3574
3575 df_set_dead_notes_for_mw (insn, mw, live, do_not_gen,
3576 artificial_uses,
3577 &really_add_notes);
3578
3579 if (really_add_notes)
3580 debug_insn = -1;
3581 }
3582
3583 FOR_EACH_INSN_INFO_USE (use, insn_info)
3584 {
3585 unsigned int uregno = DF_REF_REGNO (use);
3586
3587 if (REG_DEAD_DEBUGGING && dump_file && !debug_insn)
3588 {
3589 fprintf (dump_file, " regular looking at use ");
3590 df_ref_debug (use, dump_file);
3591 }
3592
3593 if (!bitmap_bit_p (live, uregno))
3594 {
3595 if (debug_insn)
3596 {
3597 if (debug_insn > 0)
3598 {
3599 /* We won't add REG_UNUSED or REG_DEAD notes for
3600 these, so we don't have to mess with them in
3601 debug insns either. */
3602 if (!bitmap_bit_p (artificial_uses, uregno)
3603 && !df_ignore_stack_reg (uregno))
3604 dead_debug_add (&debug, use, uregno);
3605 continue;
3606 }
3607 break;
3608 }
3609 else
3610 dead_debug_insert_temp (&debug, uregno, insn,
3611 DEBUG_TEMP_BEFORE_WITH_REG);
3612
3613 if ( (!(DF_REF_FLAGS (use)
3614 & (DF_REF_MW_HARDREG | DF_REF_READ_WRITE)))
3615 && (!bitmap_bit_p (do_not_gen, uregno))
3616 && (!bitmap_bit_p (artificial_uses, uregno))
3617 && (!df_ignore_stack_reg (uregno)))
3618 {
3619 rtx reg = (DF_REF_LOC (use))
3620 ? *DF_REF_REAL_LOC (use) : DF_REF_REG (use);
3621 df_set_note (REG_DEAD, insn, reg);
3622
3623 if (REG_DEAD_DEBUGGING)
3624 df_print_note ("adding 4: ", insn, REG_NOTES (insn));
3625 }
3626 /* This register is now live. */
3627 bitmap_set_bit (live, uregno);
3628 }
3629 }
3630
3631 df_remove_dead_eq_notes (insn, live);
3632
3633 if (debug_insn == -1)
3634 {
3635 /* ??? We could probably do better here, replacing dead
3636 registers with their definitions. */
3637 INSN_VAR_LOCATION_LOC (insn) = gen_rtx_UNKNOWN_VAR_LOC ();
3638 df_insn_rescan_debug_internal (insn);
3639 }
3640 }
3641
3642 dead_debug_local_finish (&debug, NULL);
3643}
3644
3645
3646/* Compute register info: lifetime, bb, and number of defs and uses. */
3647static void
3648df_note_compute (bitmap all_blocks)
3649{
3650 unsigned int bb_index;
3651 bitmap_iterator bi;
3652 bitmap_head live, do_not_gen, artificial_uses;
3653
3654 bitmap_initialize (&live, &df_bitmap_obstack);
3655 bitmap_initialize (&do_not_gen, &df_bitmap_obstack);
3656 bitmap_initialize (&artificial_uses, &df_bitmap_obstack);
3657
3658 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
3659 {
3660 /* ??? Unlike fast DCE, we don't use global_debug for uses of dead
3661 pseudos in debug insns because we don't always (re)visit blocks
3662 with death points after visiting dead uses. Even changing this
3663 loop to postorder would still leave room for visiting a death
3664 point before visiting a subsequent debug use. */
3665 df_note_bb_compute (bb_index, &live, &do_not_gen, &artificial_uses);
3666 }
3667
3668 bitmap_clear (&live);
3669 bitmap_clear (&do_not_gen);
3670 bitmap_clear (&artificial_uses);
3671}
3672
3673
3674/* Free all storage associated with the problem. */
3675
3676static void
3677df_note_free (void)
3678{
3679 free (df_note);
3680}
3681
3682
3683/* All of the information associated every instance of the problem. */
3684
3685static const struct df_problem problem_NOTE =
3686{
3687 DF_NOTE, /* Problem id. */
3688 DF_NONE, /* Direction. */
3689 df_note_alloc, /* Allocate the problem specific data. */
3690 NULL, /* Reset global information. */
3691 NULL, /* Free basic block info. */
3692 df_note_compute, /* Local compute function. */
3693 NULL, /* Init the solution specific data. */
3694 NULL, /* Iterative solver. */
3695 NULL, /* Confluence operator 0. */
3696 NULL, /* Confluence operator n. */
3697 NULL, /* Transfer function. */
3698 NULL, /* Finalize function. */
3699 df_note_free, /* Free all of the problem information. */
3700 df_note_free, /* Remove this problem from the stack of dataflow problems. */
3701 NULL, /* Debugging. */
3702 NULL, /* Debugging start block. */
3703 NULL, /* Debugging end block. */
3704 NULL, /* Debugging start insn. */
3705 NULL, /* Debugging end insn. */
3706 NULL, /* Incremental solution verify start. */
3707 NULL, /* Incremental solution verify end. */
3708 &problem_LR, /* Dependent problem. */
3709 sizeof (struct df_scan_bb_info),/* Size of entry of block_info array. */
3710 TV_DF_NOTE, /* Timing variable. */
3711 false /* Reset blocks on dropping out of blocks_to_analyze. */
3712};
3713
3714
3715/* Create a new DATAFLOW instance and add it to an existing instance
3716 of DF. The returned structure is what is used to get at the
3717 solution. */
3718
3719void
3720df_note_add_problem (void)
3721{
3722 df_add_problem (&problem_NOTE);
3723}
3724
3725
3726
3727
3728/*----------------------------------------------------------------------------
3729 Functions for simulating the effects of single insns.
3730
3731 You can either simulate in the forwards direction, starting from
3732 the top of a block or the backwards direction from the end of the
3733 block. If you go backwards, defs are examined first to clear bits,
3734 then uses are examined to set bits. If you go forwards, defs are
3735 examined first to set bits, then REG_DEAD and REG_UNUSED notes
3736 are examined to clear bits. In either case, the result of examining
3737 a def can be undone (respectively by a use or a REG_UNUSED note).
3738
3739 If you start at the top of the block, use one of DF_LIVE_IN or
3740 DF_LR_IN. If you start at the bottom of the block use one of
3741 DF_LIVE_OUT or DF_LR_OUT. BE SURE TO PASS A COPY OF THESE SETS,
3742 THEY WILL BE DESTROYED.
3743----------------------------------------------------------------------------*/
3744
3745
3746/* Find the set of DEFs for INSN. */
3747
3748void
3749df_simulate_find_defs (rtx_insn *insn, bitmap defs)
3750{
3751 df_ref def;
3752
3753 FOR_EACH_INSN_DEF (def, insn)
3754 bitmap_set_bit (defs, DF_REF_REGNO (def));
3755}
3756
3757/* Find the set of uses for INSN. This includes partial defs. */
3758
3759static void
3760df_simulate_find_uses (rtx_insn *insn, bitmap uses)
3761{
3762 df_ref def, use;
3763 struct df_insn_info *insn_info = DF_INSN_INFO_GET (insn);
3764
3765 FOR_EACH_INSN_INFO_DEF (def, insn_info)
3766 if (DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL))
3767 bitmap_set_bit (uses, DF_REF_REGNO (def));
3768 FOR_EACH_INSN_INFO_USE (use, insn_info)
3769 bitmap_set_bit (uses, DF_REF_REGNO (use));
3770}
3771
3772/* Find the set of real DEFs, which are not clobbers, for INSN. */
3773
3774void
3775df_simulate_find_noclobber_defs (rtx_insn *insn, bitmap defs)
3776{
3777 df_ref def;
3778
3779 FOR_EACH_INSN_DEF (def, insn)
3780 if (!(DF_REF_FLAGS (def) & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
3781 bitmap_set_bit (defs, DF_REF_REGNO (def));
3782}
3783
3784
3785/* Simulate the effects of the defs of INSN on LIVE. */
3786
3787void
3788df_simulate_defs (rtx_insn *insn, bitmap live)
3789{
3790 df_ref def;
3791
3792 FOR_EACH_INSN_DEF (def, insn)
3793 {
3794 unsigned int dregno = DF_REF_REGNO (def);
3795
3796 /* If the def is to only part of the reg, it does
3797 not kill the other defs that reach here. */
3798 if (!(DF_REF_FLAGS (def) & (DF_REF_PARTIAL | DF_REF_CONDITIONAL)))
3799 bitmap_clear_bit (live, dregno);
3800 }
3801}
3802
3803
3804/* Simulate the effects of the uses of INSN on LIVE. */
3805
3806void
3807df_simulate_uses (rtx_insn *insn, bitmap live)
3808{
3809 df_ref use;
3810
3811 if (DEBUG_INSN_P (insn))
3812 return;
3813
3814 FOR_EACH_INSN_USE (use, insn)
3815 /* Add use to set of uses in this BB. */
3816 bitmap_set_bit (live, DF_REF_REGNO (use));
3817}
3818
3819
3820/* Add back the always live regs in BB to LIVE. */
3821
3822static inline void
3823df_simulate_fixup_sets (basic_block bb, bitmap live)
3824{
3825 /* These regs are considered always live so if they end up dying
3826 because of some def, we need to bring the back again. */
3827 if (bb_has_eh_pred (bb))
3828 bitmap_ior_into (live, &df->eh_block_artificial_uses);
3829 else
3830 bitmap_ior_into (live, &df->regular_block_artificial_uses);
3831}
3832
3833
3834/*----------------------------------------------------------------------------
3835 The following three functions are used only for BACKWARDS scanning:
3836 i.e. they process the defs before the uses.
3837
3838 df_simulate_initialize_backwards should be called first with a
3839 bitvector copyied from the DF_LIVE_OUT or DF_LR_OUT. Then
3840 df_simulate_one_insn_backwards should be called for each insn in
3841 the block, starting with the last one. Finally,
3842 df_simulate_finalize_backwards can be called to get a new value
3843 of the sets at the top of the block (this is rarely used).
3844 ----------------------------------------------------------------------------*/
3845
3846/* Apply the artificial uses and defs at the end of BB in a backwards
3847 direction. */
3848
3849void
3850df_simulate_initialize_backwards (basic_block bb, bitmap live)
3851{
3852 df_ref def, use;
3853 int bb_index = bb->index;
3854
3855 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3856 if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
3857 bitmap_clear_bit (live, DF_REF_REGNO (def));
3858
3859 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3860 if ((DF_REF_FLAGS (use) & DF_REF_AT_TOP) == 0)
3861 bitmap_set_bit (live, DF_REF_REGNO (use));
3862}
3863
3864
3865/* Simulate the backwards effects of INSN on the bitmap LIVE. */
3866
3867void
3868df_simulate_one_insn_backwards (basic_block bb, rtx_insn *insn, bitmap live)
3869{
3870 if (!NONDEBUG_INSN_P (insn))
3871 return;
3872
3873 df_simulate_defs (insn, live);
3874 df_simulate_uses (insn, live);
3875 df_simulate_fixup_sets (bb, live);
3876}
3877
3878
3879/* Apply the artificial uses and defs at the top of BB in a backwards
3880 direction. */
3881
3882void
3883df_simulate_finalize_backwards (basic_block bb, bitmap live)
3884{
3885 df_ref def;
3886#ifdef EH_USES
3887 df_ref use;
3888#endif
3889 int bb_index = bb->index;
3890
3891 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3892 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3893 bitmap_clear_bit (live, DF_REF_REGNO (def));
3894
3895#ifdef EH_USES
3896 FOR_EACH_ARTIFICIAL_USE (use, bb_index)
3897 if (DF_REF_FLAGS (use) & DF_REF_AT_TOP)
3898 bitmap_set_bit (live, DF_REF_REGNO (use));
3899#endif
3900}
3901/*----------------------------------------------------------------------------
3902 The following three functions are used only for FORWARDS scanning:
3903 i.e. they process the defs and the REG_DEAD and REG_UNUSED notes.
3904 Thus it is important to add the DF_NOTES problem to the stack of
3905 problems computed before using these functions.
3906
3907 df_simulate_initialize_forwards should be called first with a
3908 bitvector copyied from the DF_LIVE_IN or DF_LR_IN. Then
3909 df_simulate_one_insn_forwards should be called for each insn in
3910 the block, starting with the first one.
3911 ----------------------------------------------------------------------------*/
3912
3913/* Initialize the LIVE bitmap, which should be copied from DF_LIVE_IN or
3914 DF_LR_IN for basic block BB, for forward scanning by marking artificial
3915 defs live. */
3916
3917void
3918df_simulate_initialize_forwards (basic_block bb, bitmap live)
3919{
3920 df_ref def;
3921 int bb_index = bb->index;
3922
3923 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
3924 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
3925 bitmap_set_bit (live, DF_REF_REGNO (def));
3926}
3927
3928/* Simulate the forwards effects of INSN on the bitmap LIVE. */
3929
3930void
3931df_simulate_one_insn_forwards (basic_block bb, rtx_insn *insn, bitmap live)
3932{
3933 rtx link;
3934 if (! INSN_P (insn))
3935 return;
3936
3937 /* Make sure that DF_NOTE really is an active df problem. */
3938 gcc_assert (df_note);
3939
3940 /* Note that this is the opposite as how the problem is defined, because
3941 in the LR problem defs _kill_ liveness. However, they do so backwards,
3942 while here the scan is performed forwards! So, first assume that the
3943 def is live, and if this is not true REG_UNUSED notes will rectify the
3944 situation. */
3945 df_simulate_find_noclobber_defs (insn, live);
3946
3947 /* Clear all of the registers that go dead. */
3948 for (link = REG_NOTES (insn); link; link = XEXP (link, 1))
3949 {
3950 switch (REG_NOTE_KIND (link))
3951 {
3952 case REG_DEAD:
3953 case REG_UNUSED:
3954 {
3955 rtx reg = XEXP (link, 0);
3956 bitmap_clear_range (live, REGNO (reg), REG_NREGS (reg));
3957 }
3958 break;
3959 default:
3960 break;
3961 }
3962 }
3963 df_simulate_fixup_sets (bb, live);
3964}
3965
3966/* Used by the next two functions to encode information about the
3967 memory references we found. */
3968#define MEMREF_NORMAL 1
3969#define MEMREF_VOLATILE 2
3970
3971/* Return an OR of MEMREF_NORMAL or MEMREF_VOLATILE for the MEMs in X. */
3972
3973static int
3974find_memory (rtx_insn *insn)
3975{
3976 int flags = 0;
3977 subrtx_iterator::array_type array;
3978 FOR_EACH_SUBRTX (iter, array, PATTERN (insn), NONCONST)
3979 {
3980 const_rtx x = *iter;
3981 if (GET_CODE (x) == ASM_OPERANDS && MEM_VOLATILE_P (x))
3982 flags |= MEMREF_VOLATILE;
3983 else if (MEM_P (x))
3984 {
3985 if (MEM_VOLATILE_P (x))
3986 flags |= MEMREF_VOLATILE;
3987 else if (!MEM_READONLY_P (x))
3988 flags |= MEMREF_NORMAL;
3989 }
3990 }
3991 return flags;
3992}
3993
3994/* A subroutine of can_move_insns_across_p called through note_stores.
3995 DATA points to an integer in which we set either the bit for
3996 MEMREF_NORMAL or the bit for MEMREF_VOLATILE if we find a MEM
3997 of either kind. */
3998
3999static void
4000find_memory_stores (rtx x, const_rtx pat ATTRIBUTE_UNUSED,
4001 void *data ATTRIBUTE_UNUSED)
4002{
4003 int *pflags = (int *)data;
4004 if (GET_CODE (x) == SUBREG)
4005 x = XEXP (x, 0);
4006 /* Treat stores to SP as stores to memory, this will prevent problems
4007 when there are references to the stack frame. */
4008 if (x == stack_pointer_rtx)
4009 *pflags |= MEMREF_VOLATILE;
4010 if (!MEM_P (x))
4011 return;
4012 *pflags |= MEM_VOLATILE_P (x) ? MEMREF_VOLATILE : MEMREF_NORMAL;
4013}
4014
4015/* Scan BB backwards, using df_simulate functions to keep track of
4016 lifetimes, up to insn POINT. The result is stored in LIVE. */
4017
4018void
4019simulate_backwards_to_point (basic_block bb, regset live, rtx point)
4020{
4021 rtx_insn *insn;
4022 bitmap_copy (live, df_get_live_out (bb));
4023 df_simulate_initialize_backwards (bb, live);
4024
4025 /* Scan and update life information until we reach the point we're
4026 interested in. */
4027 for (insn = BB_END (bb); insn != point; insn = PREV_INSN (insn))
4028 df_simulate_one_insn_backwards (bb, insn, live);
4029}
4030
4031/* Return true if it is safe to move a group of insns, described by
4032 the range FROM to TO, backwards across another group of insns,
4033 described by ACROSS_FROM to ACROSS_TO. It is assumed that there
4034 are no insns between ACROSS_TO and FROM, but they may be in
4035 different basic blocks; MERGE_BB is the block from which the
4036 insns will be moved. The caller must pass in a regset MERGE_LIVE
4037 which specifies the registers live after TO.
4038
4039 This function may be called in one of two cases: either we try to
4040 move identical instructions from all successor blocks into their
4041 predecessor, or we try to move from only one successor block. If
4042 OTHER_BRANCH_LIVE is nonnull, it indicates that we're dealing with
4043 the second case. It should contain a set of registers live at the
4044 end of ACROSS_TO which must not be clobbered by moving the insns.
4045 In that case, we're also more careful about moving memory references
4046 and trapping insns.
4047
4048 We return false if it is not safe to move the entire group, but it
4049 may still be possible to move a subgroup. PMOVE_UPTO, if nonnull,
4050 is set to point at the last moveable insn in such a case. */
4051
4052bool
4053can_move_insns_across (rtx_insn *from, rtx_insn *to,
4054 rtx_insn *across_from, rtx_insn *across_to,
4055 basic_block merge_bb, regset merge_live,
4056 regset other_branch_live, rtx_insn **pmove_upto)
4057{
4058 rtx_insn *insn, *next, *max_to;
4059 bitmap merge_set, merge_use, local_merge_live;
4060 bitmap test_set, test_use;
4061 unsigned i, fail = 0;
4062 bitmap_iterator bi;
4063 int memrefs_in_across = 0;
4064 int mem_sets_in_across = 0;
4065 bool trapping_insns_in_across = false;
4066
4067 if (pmove_upto != NULL)
4068 *pmove_upto = NULL;
4069
4070 /* Find real bounds, ignoring debug insns. */
4071 while (!NONDEBUG_INSN_P (from) && from != to)
4072 from = NEXT_INSN (from);
4073 while (!NONDEBUG_INSN_P (to) && from != to)
4074 to = PREV_INSN (to);
4075
4076 for (insn = across_to; ; insn = next)
4077 {
4078 if (CALL_P (insn))
4079 {
4080 if (RTL_CONST_OR_PURE_CALL_P (insn))
4081 /* Pure functions can read from memory. Const functions can
4082 read from arguments that the ABI has forced onto the stack.
4083 Neither sort of read can be volatile. */
4084 memrefs_in_across |= MEMREF_NORMAL;
4085 else
4086 {
4087 memrefs_in_across |= MEMREF_VOLATILE;
4088 mem_sets_in_across |= MEMREF_VOLATILE;
4089 }
4090 }
4091 if (NONDEBUG_INSN_P (insn))
4092 {
4093 if (volatile_insn_p (PATTERN (insn)))
4094 return false;
4095 memrefs_in_across |= find_memory (insn);
4096 note_stores (PATTERN (insn), find_memory_stores,
4097 &mem_sets_in_across);
4098 /* This is used just to find sets of the stack pointer. */
4099 memrefs_in_across |= mem_sets_in_across;
4100 trapping_insns_in_across |= may_trap_p (PATTERN (insn));
4101 }
4102 next = PREV_INSN (insn);
4103 if (insn == across_from)
4104 break;
4105 }
4106
4107 /* Collect:
4108 MERGE_SET = set of registers set in MERGE_BB
4109 MERGE_USE = set of registers used in MERGE_BB and live at its top
4110 MERGE_LIVE = set of registers live at the point inside the MERGE
4111 range that we've reached during scanning
4112 TEST_SET = set of registers set between ACROSS_FROM and ACROSS_END.
4113 TEST_USE = set of registers used between ACROSS_FROM and ACROSS_END,
4114 and live before ACROSS_FROM. */
4115
4116 merge_set = BITMAP_ALLOC (&reg_obstack);
4117 merge_use = BITMAP_ALLOC (&reg_obstack);
4118 local_merge_live = BITMAP_ALLOC (&reg_obstack);
4119 test_set = BITMAP_ALLOC (&reg_obstack);
4120 test_use = BITMAP_ALLOC (&reg_obstack);
4121
4122 /* Compute the set of registers set and used in the ACROSS range. */
4123 if (other_branch_live != NULL)
4124 bitmap_copy (test_use, other_branch_live);
4125 df_simulate_initialize_backwards (merge_bb, test_use);
4126 for (insn = across_to; ; insn = next)
4127 {
4128 if (NONDEBUG_INSN_P (insn))
4129 {
4130 df_simulate_find_defs (insn, test_set);
4131 df_simulate_defs (insn, test_use);
4132 df_simulate_uses (insn, test_use);
4133 }
4134 next = PREV_INSN (insn);
4135 if (insn == across_from)
4136 break;
4137 }
4138
4139 /* Compute an upper bound for the amount of insns moved, by finding
4140 the first insn in MERGE that sets a register in TEST_USE, or uses
4141 a register in TEST_SET. We also check for calls, trapping operations,
4142 and memory references. */
4143 max_to = NULL;
4144 for (insn = from; ; insn = next)
4145 {
4146 if (CALL_P (insn))
4147 break;
4148 if (NOTE_P (insn) && NOTE_KIND (insn) == NOTE_INSN_EPILOGUE_BEG)
4149 break;
4150 if (NONDEBUG_INSN_P (insn))
4151 {
4152 if (may_trap_or_fault_p (PATTERN (insn))
4153 && (trapping_insns_in_across
4154 || other_branch_live != NULL
4155 || volatile_insn_p (PATTERN (insn))))
4156 break;
4157
4158 /* We cannot move memory stores past each other, or move memory
4159 reads past stores, at least not without tracking them and
4160 calling true_dependence on every pair.
4161
4162 If there is no other branch and no memory references or
4163 sets in the ACROSS range, we can move memory references
4164 freely, even volatile ones.
4165
4166 Otherwise, the rules are as follows: volatile memory
4167 references and stores can't be moved at all, and any type
4168 of memory reference can't be moved if there are volatile
4169 accesses or stores in the ACROSS range. That leaves
4170 normal reads, which can be moved, as the trapping case is
4171 dealt with elsewhere. */
4172 if (other_branch_live != NULL || memrefs_in_across != 0)
4173 {
4174 int mem_ref_flags = 0;
4175 int mem_set_flags = 0;
4176 note_stores (PATTERN (insn), find_memory_stores, &mem_set_flags);
4177 mem_ref_flags = find_memory (insn);
4178 /* Catch sets of the stack pointer. */
4179 mem_ref_flags |= mem_set_flags;
4180
4181 if ((mem_ref_flags | mem_set_flags) & MEMREF_VOLATILE)
4182 break;
4183 if ((memrefs_in_across & MEMREF_VOLATILE) && mem_ref_flags != 0)
4184 break;
4185 if (mem_set_flags != 0
4186 || (mem_sets_in_across != 0 && mem_ref_flags != 0))
4187 break;
4188 }
4189 df_simulate_find_uses (insn, merge_use);
4190 /* We're only interested in uses which use a value live at
4191 the top, not one previously set in this block. */
4192 bitmap_and_compl_into (merge_use, merge_set);
4193 df_simulate_find_defs (insn, merge_set);
4194 if (bitmap_intersect_p (merge_set, test_use)
4195 || bitmap_intersect_p (merge_use, test_set))
4196 break;
4197 if (!HAVE_cc0 || !sets_cc0_p (insn))
4198 max_to = insn;
4199 }
4200 next = NEXT_INSN (insn);
4201 if (insn == to)
4202 break;
4203 }
4204 if (max_to != to)
4205 fail = 1;
4206
4207 if (max_to == NULL_RTX || (fail && pmove_upto == NULL))
4208 goto out;
4209
4210 /* Now, lower this upper bound by also taking into account that
4211 a range of insns moved across ACROSS must not leave a register
4212 live at the end that will be clobbered in ACROSS. We need to
4213 find a point where TEST_SET & LIVE == 0.
4214
4215 Insns in the MERGE range that set registers which are also set
4216 in the ACROSS range may still be moved as long as we also move
4217 later insns which use the results of the set, and make the
4218 register dead again. This is verified by the condition stated
4219 above. We only need to test it for registers that are set in
4220 the moved region.
4221
4222 MERGE_LIVE is provided by the caller and holds live registers after
4223 TO. */
4224 bitmap_copy (local_merge_live, merge_live);
4225 for (insn = to; insn != max_to; insn = PREV_INSN (insn))
4226 df_simulate_one_insn_backwards (merge_bb, insn, local_merge_live);
4227
4228 /* We're not interested in registers that aren't set in the moved
4229 region at all. */
4230 bitmap_and_into (local_merge_live, merge_set);
4231 for (;;)
4232 {
4233 if (NONDEBUG_INSN_P (insn))
4234 {
4235 if (!bitmap_intersect_p (test_set, local_merge_live)
4236 && (!HAVE_cc0 || !sets_cc0_p (insn)))
4237 {
4238 max_to = insn;
4239 break;
4240 }
4241
4242 df_simulate_one_insn_backwards (merge_bb, insn,
4243 local_merge_live);
4244 }
4245 if (insn == from)
4246 {
4247 fail = 1;
4248 goto out;
4249 }
4250 insn = PREV_INSN (insn);
4251 }
4252
4253 if (max_to != to)
4254 fail = 1;
4255
4256 if (pmove_upto)
4257 *pmove_upto = max_to;
4258
4259 /* For small register class machines, don't lengthen lifetimes of
4260 hard registers before reload. */
4261 if (! reload_completed
4262 && targetm.small_register_classes_for_mode_p (VOIDmode))
4263 {
4264 EXECUTE_IF_SET_IN_BITMAP (merge_set, 0, i, bi)
4265 {
4266 if (i < FIRST_PSEUDO_REGISTER
4267 && ! fixed_regs[i]
4268 && ! global_regs[i])
4269 {
4270 fail = 1;
4271 break;
4272 }
4273 }
4274 }
4275
4276 out:
4277 BITMAP_FREE (merge_set);
4278 BITMAP_FREE (merge_use);
4279 BITMAP_FREE (local_merge_live);
4280 BITMAP_FREE (test_set);
4281 BITMAP_FREE (test_use);
4282
4283 return !fail;
4284}
4285
4286
4287/*----------------------------------------------------------------------------
4288 MULTIPLE DEFINITIONS
4289
4290 Find the locations in the function reached by multiple definition sites
4291 for a live pseudo. In and out bitvectors are built for each basic
4292 block. They are restricted for efficiency to live registers.
4293
4294 The gen and kill sets for the problem are obvious. Together they
4295 include all defined registers in a basic block; the gen set includes
4296 registers where a partial or conditional or may-clobber definition is
4297 last in the BB, while the kill set includes registers with a complete
4298 definition coming last. However, the computation of the dataflow
4299 itself is interesting.
4300
4301 The idea behind it comes from SSA form's iterated dominance frontier
4302 criterion for inserting PHI functions. Just like in that case, we can use
4303 the dominance frontier to find places where multiple definitions meet;
4304 a register X defined in a basic block BB1 has multiple definitions in
4305 basic blocks in BB1's dominance frontier.
4306
4307 So, the in-set of a basic block BB2 is not just the union of the
4308 out-sets of BB2's predecessors, but includes some more bits that come
4309 from the basic blocks of whose dominance frontier BB2 is part (BB1 in
4310 the previous paragraph). I called this set the init-set of BB2.
4311
4312 (Note: I actually use the kill-set only to build the init-set.
4313 gen bits are anyway propagated from BB1 to BB2 by dataflow).
4314
4315 For example, if you have
4316
4317 BB1 : r10 = 0
4318 r11 = 0
4319 if <...> goto BB2 else goto BB3;
4320
4321 BB2 : r10 = 1
4322 r12 = 1
4323 goto BB3;
4324
4325 BB3 :
4326
4327 you have BB3 in BB2's dominance frontier but not in BB1's, so that the
4328 init-set of BB3 includes r10 and r12, but not r11. Note that we do
4329 not need to iterate the dominance frontier, because we do not insert
4330 anything like PHI functions there! Instead, dataflow will take care of
4331 propagating the information to BB3's successors.
4332 ---------------------------------------------------------------------------*/
4333
4334/* Private data used to verify the solution for this problem. */
4335struct df_md_problem_data
4336{
4337 /* An obstack for the bitmaps we need for this problem. */
4338 bitmap_obstack md_bitmaps;
4339};
4340
4341/* Scratch var used by transfer functions. This is used to do md analysis
4342 only for live registers. */
4343static bitmap_head df_md_scratch;
4344
4345
4346static void
4347df_md_free_bb_info (basic_block bb ATTRIBUTE_UNUSED,
4348 void *vbb_info)
4349{
4350 struct df_md_bb_info *bb_info = (struct df_md_bb_info *) vbb_info;
4351 if (bb_info)
4352 {
4353 bitmap_clear (&bb_info->kill);
4354 bitmap_clear (&bb_info->gen);
4355 bitmap_clear (&bb_info->init);
4356 bitmap_clear (&bb_info->in);
4357 bitmap_clear (&bb_info->out);
4358 }
4359}
4360
4361
4362/* Allocate or reset bitmaps for DF_MD. The solution bits are
4363 not touched unless the block is new. */
4364
4365static void
4366df_md_alloc (bitmap all_blocks)
4367{
4368 unsigned int bb_index;
4369 bitmap_iterator bi;
4370 struct df_md_problem_data *problem_data;
4371
4372 df_grow_bb_info (df_md);
4373 if (df_md->problem_data)
4374 problem_data = (struct df_md_problem_data *) df_md->problem_data;
4375 else
4376 {
4377 problem_data = XNEW (struct df_md_problem_data);
4378 df_md->problem_data = problem_data;
4379 bitmap_obstack_initialize (&problem_data->md_bitmaps);
4380 }
4381 bitmap_initialize (&df_md_scratch, &problem_data->md_bitmaps);
4382
4383 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4384 {
4385 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4386 /* When bitmaps are already initialized, just clear them. */
4387 if (bb_info->init.obstack)
4388 {
4389 bitmap_clear (&bb_info->init);
4390 bitmap_clear (&bb_info->gen);
4391 bitmap_clear (&bb_info->kill);
4392 bitmap_clear (&bb_info->in);
4393 bitmap_clear (&bb_info->out);
4394 }
4395 else
4396 {
4397 bitmap_initialize (&bb_info->init, &problem_data->md_bitmaps);
4398 bitmap_initialize (&bb_info->gen, &problem_data->md_bitmaps);
4399 bitmap_initialize (&bb_info->kill, &problem_data->md_bitmaps);
4400 bitmap_initialize (&bb_info->in, &problem_data->md_bitmaps);
4401 bitmap_initialize (&bb_info->out, &problem_data->md_bitmaps);
4402 }
4403 }
4404
4405 df_md->optional_p = true;
4406}
4407
4408/* Add the effect of the top artificial defs of BB to the multiple definitions
4409 bitmap LOCAL_MD. */
4410
4411void
4412df_md_simulate_artificial_defs_at_top (basic_block bb, bitmap local_md)
4413{
4414 int bb_index = bb->index;
4415 df_ref def;
4416 FOR_EACH_ARTIFICIAL_DEF (def, bb_index)
4417 if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
4418 {
4419 unsigned int dregno = DF_REF_REGNO (def);
4420 if (DF_REF_FLAGS (def)
4421 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4422 bitmap_set_bit (local_md, dregno);
4423 else
4424 bitmap_clear_bit (local_md, dregno);
4425 }
4426}
4427
4428
4429/* Add the effect of the defs of INSN to the reaching definitions bitmap
4430 LOCAL_MD. */
4431
4432void
4433df_md_simulate_one_insn (basic_block bb ATTRIBUTE_UNUSED, rtx_insn *insn,
4434 bitmap local_md)
4435{
4436 df_ref def;
4437
4438 FOR_EACH_INSN_DEF (def, insn)
4439 {
4440 unsigned int dregno = DF_REF_REGNO (def);
4441 if ((!(df->changeable_flags & DF_NO_HARD_REGS))
4442 || (dregno >= FIRST_PSEUDO_REGISTER))
4443 {
4444 if (DF_REF_FLAGS (def)
4445 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4446 bitmap_set_bit (local_md, DF_REF_ID (def));
4447 else
4448 bitmap_clear_bit (local_md, DF_REF_ID (def));
4449 }
4450 }
4451}
4452
4453static void
4454df_md_bb_local_compute_process_def (struct df_md_bb_info *bb_info,
4455 df_ref def,
4456 int top_flag)
4457{
4458 bitmap_clear (&seen_in_insn);
4459
4460 for (; def; def = DF_REF_NEXT_LOC (def))
4461 {
4462 unsigned int dregno = DF_REF_REGNO (def);
4463 if (((!(df->changeable_flags & DF_NO_HARD_REGS))
4464 || (dregno >= FIRST_PSEUDO_REGISTER))
4465 && top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
4466 {
4467 if (!bitmap_bit_p (&seen_in_insn, dregno))
4468 {
4469 if (DF_REF_FLAGS (def)
4470 & (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))
4471 {
4472 bitmap_set_bit (&bb_info->gen, dregno);
4473 bitmap_clear_bit (&bb_info->kill, dregno);
4474 }
4475 else
4476 {
4477 /* When we find a clobber and a regular def,
4478 make sure the regular def wins. */
4479 bitmap_set_bit (&seen_in_insn, dregno);
4480 bitmap_set_bit (&bb_info->kill, dregno);
4481 bitmap_clear_bit (&bb_info->gen, dregno);
4482 }
4483 }
4484 }
4485 }
4486}
4487
4488
4489/* Compute local multiple def info for basic block BB. */
4490
4491static void
4492df_md_bb_local_compute (unsigned int bb_index)
4493{
4494 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4495 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4496 rtx_insn *insn;
4497
4498 /* Artificials are only hard regs. */
4499 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4500 df_md_bb_local_compute_process_def (bb_info,
4501 df_get_artificial_defs (bb_index),
4502 DF_REF_AT_TOP);
4503
4504 FOR_BB_INSNS (bb, insn)
4505 {
4506 unsigned int uid = INSN_UID (insn);
4507 if (!INSN_P (insn))
4508 continue;
4509
4510 df_md_bb_local_compute_process_def (bb_info, DF_INSN_UID_DEFS (uid), 0);
4511 }
4512
4513 if (!(df->changeable_flags & DF_NO_HARD_REGS))
4514 df_md_bb_local_compute_process_def (bb_info,
4515 df_get_artificial_defs (bb_index),
4516 0);
4517}
4518
4519/* Compute local reaching def info for each basic block within BLOCKS. */
4520
4521static void
4522df_md_local_compute (bitmap all_blocks)
4523{
4524 unsigned int bb_index, df_bb_index;
4525 bitmap_iterator bi1, bi2;
4526 basic_block bb;
4527 bitmap_head *frontiers;
4528
4529 bitmap_initialize (&seen_in_insn, &bitmap_default_obstack);
4530
4531 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4532 {
4533 df_md_bb_local_compute (bb_index);
4534 }
4535
4536 bitmap_clear (&seen_in_insn);
4537
4538 frontiers = XNEWVEC (bitmap_head, last_basic_block_for_fn (cfun));
4539 FOR_ALL_BB_FN (bb, cfun)
4540 bitmap_initialize (&frontiers[bb->index], &bitmap_default_obstack);
4541
4542 compute_dominance_frontiers (frontiers);
4543
4544 /* Add each basic block's kills to the nodes in the frontier of the BB. */
4545 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi1)
4546 {
4547 bitmap kill = &df_md_get_bb_info (bb_index)->kill;
4548 EXECUTE_IF_SET_IN_BITMAP (&frontiers[bb_index], 0, df_bb_index, bi2)
4549 {
4550 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, df_bb_index);
4551 if (bitmap_bit_p (all_blocks, df_bb_index))
4552 bitmap_ior_and_into (&df_md_get_bb_info (df_bb_index)->init, kill,
4553 df_get_live_in (bb));
4554 }
4555 }
4556
4557 FOR_ALL_BB_FN (bb, cfun)
4558 bitmap_clear (&frontiers[bb->index]);
4559 free (frontiers);
4560}
4561
4562
4563/* Reset the global solution for recalculation. */
4564
4565static void
4566df_md_reset (bitmap all_blocks)
4567{
4568 unsigned int bb_index;
4569 bitmap_iterator bi;
4570
4571 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4572 {
4573 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4574 gcc_assert (bb_info);
4575 bitmap_clear (&bb_info->in);
4576 bitmap_clear (&bb_info->out);
4577 }
4578}
4579
4580static bool
4581df_md_transfer_function (int bb_index)
4582{
4583 basic_block bb = BASIC_BLOCK_FOR_FN (cfun, bb_index);
4584 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4585 bitmap in = &bb_info->in;
4586 bitmap out = &bb_info->out;
4587 bitmap gen = &bb_info->gen;
4588 bitmap kill = &bb_info->kill;
4589
4590 /* We need to use a scratch set here so that the value returned from this
4591 function invocation properly reflects whether the sets changed in a
4592 significant way; i.e. not just because the live set was anded in. */
4593 bitmap_and (&df_md_scratch, gen, df_get_live_out (bb));
4594
4595 /* Multiple definitions of a register are not relevant if it is not
4596 live. Thus we trim the result to the places where it is live. */
4597 bitmap_and_into (in, df_get_live_in (bb));
4598
4599 return bitmap_ior_and_compl (out, &df_md_scratch, in, kill);
4600}
4601
4602/* Initialize the solution bit vectors for problem. */
4603
4604static void
4605df_md_init (bitmap all_blocks)
4606{
4607 unsigned int bb_index;
4608 bitmap_iterator bi;
4609
4610 EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
4611 {
4612 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb_index);
4613
4614 bitmap_copy (&bb_info->in, &bb_info->init);
4615 df_md_transfer_function (bb_index);
4616 }
4617}
4618
4619static void
4620df_md_confluence_0 (basic_block bb)
4621{
4622 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4623 bitmap_copy (&bb_info->in, &bb_info->init);
4624}
4625
4626/* In of target gets or of out of source. */
4627
4628static bool
4629df_md_confluence_n (edge e)
4630{
4631 bitmap op1 = &df_md_get_bb_info (e->dest->index)->in;
4632 bitmap op2 = &df_md_get_bb_info (e->src->index)->out;
4633
4634 if (e->flags & EDGE_FAKE)
4635 return false;
4636
4637 if (e->flags & EDGE_EH)
4638 return bitmap_ior_and_compl_into (op1, op2,
4639 regs_invalidated_by_call_regset);
4640 else
4641 return bitmap_ior_into (op1, op2);
4642}
4643
4644/* Free all storage associated with the problem. */
4645
4646static void
4647df_md_free (void)
4648{
4649 struct df_md_problem_data *problem_data
4650 = (struct df_md_problem_data *) df_md->problem_data;
4651
4652 bitmap_obstack_release (&problem_data->md_bitmaps);
4653 free (problem_data);
4654 df_md->problem_data = NULL;
4655
4656 df_md->block_info_size = 0;
4657 free (df_md->block_info);
4658 df_md->block_info = NULL;
4659 free (df_md);
4660}
4661
4662
4663/* Debugging info at top of bb. */
4664
4665static void
4666df_md_top_dump (basic_block bb, FILE *file)
4667{
4668 struct df_md_bb_info *bb_info = df_md_get_bb_info (bb->index);
4669 if (!bb_info)
4670 return;
4671
4672 fprintf (file, ";; md in \t");
4673 df_print_regset (file, &bb_info->in);
4674 fprintf (file, ";; md init \t");
4675 df_print_regset (file, &bb_info->init);
4676 fprintf (file, ";; md gen \t");
4677 df_print_regset (file, &bb_info->gen);
4678 fprintf (file, ";; md kill \t");
4679 df_print_regset (file, &bb_info->